common/utils.c

   1 /*
   2  *  Dolda Connect - Modular multiuser Direct Connect-style client
   3  *  Copyright (C) 2004 Fredrik Tolf <fredrik@dolda2000.com>
   4  *
   5  *  This program is free software; you can redistribute it and/or modify
   6  *  it under the terms of the GNU General Public License as published by
   7  *  the Free Software Foundation; either version 2 of the License, or
   8  *  (at your option) any later version.
   9  *
  10  *  This program is distributed in the hope that it will be useful,
  11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  *  GNU General Public License for more details.
  14  *
  15  *  You should have received a copy of the GNU General Public License
  16  *  along with this program; if not, write to the Free Software
  17  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  18 */
  19 #include <stdlib.h>
  20 #include <stdarg.h>
  21 #include <stdio.h>
  22 #include <wchar.h>
  23 #include <iconv.h>
  24 #include <errno.h>
  25 #include <string.h>
  26 #include <wctype.h>
  27 #include <langinfo.h>
  28 #include <pwd.h>
  29 #include <unistd.h>
  30 #include <sys/time.h>
  31 #include <netinet/in.h>
  32 #include <alloca.h>
  33
  34 #ifdef HAVE_CONFIG_H
  35 #include <config.h>
  36 #endif
  37 #include <utils.h>
  38 #include <log.h>
  39
  40 struct treeiter {
  41     struct {
  42         struct btree *n;
  43         int s;
  44     } *st;
  45     size_t stsize, sp;
  46 };
  47
  48 static char *base64set = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
  49 static int base64rev[] = {
  50     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  51     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  52     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 62, -1, -1, -1, 63,
  53     52, 53, 54, 55, 56, 57, 58, 59, 60, 61, -1, -1, -1, -1, -1, -1,
  54     -1,  0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14,
  55     15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, -1, -1, -1, -1, -1,
  56     -1, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
  57     41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, -1, -1, -1, -1, -1,
  58     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  59     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  60     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  61     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  62     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  63     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  64     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  65     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  66 };
  67 static char *base32set = "ABCDEFGHIJKLMNOPQRSTUVWXYZ234567";
  68 static int base32rev[] = {
  69     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  70     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  71     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  72     -1, -1, 26, 27, 28, 29, 30, 31, -1, -1, -1, -1, -1, -1, -1, -1,
  73     -1,  0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14,
  74     15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, -1, -1, -1, -1, -1,
  75     -1,  0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14,
  76     15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, -1, -1, -1, -1, -1,
  77     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  78     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  79     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  80     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  81     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  82     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  83     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  84     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  85 };
  86
  87 char *vsprintf2(char *format, va_list al)
  88 {
  89     int ret;
  90     char *buf;
  91     va_list al2;
  92
  93     va_copy(al2, al);
  94     ret = vsnprintf(NULL, 0, format, al2);
  95     va_end(al2);
  96     if((buf = malloc(ret + 1)) == NULL)
  97     {
  98         LOGOOM(ret + 1);
  99         return(NULL);
 100     }
 101     va_copy(al2, al);
 102     vsnprintf(buf, ret + 1, format, al2);
 103     va_end(al2);
 104     return(buf);
 105 }
 106
 107 char *sprintf2(char *format, ...)
 108 {
 109     va_list args;
 110     char *buf;
 111
 112     va_start(args, format);
 113     buf = vsprintf2(format, args);
 114     va_end(args);
 115     return(buf);
 116 }
 117
 118 wchar_t *vswprintf2(wchar_t *format, va_list al)
 119 {
 120     int ret;
 121     wchar_t *buf;
 122     size_t bufsize;
 123     va_list al2;
 124
 125     buf = smalloc(sizeof(wchar_t) * (bufsize = 1024));
 126     while(1)
 127     {
 128         va_copy(al2, al);
 129         ret = vswprintf(buf, bufsize, format, al2);
 130         va_end(al2);
 131         if(ret >= 0)
 132             break;
 133         buf = srealloc(buf, sizeof(wchar_t) * (bufsize *= 2));
 134     }
 135     if(bufsize > ret + 1)
 136         buf = srealloc(buf, sizeof(wchar_t) * (ret + 1));
 137     return(buf);
 138 }
 139
 140 wchar_t *swprintf2(wchar_t *format, ...)
 141 {
 142     va_list args;
 143     wchar_t *buf;
 144
 145     va_start(args, format);
 146     buf = vswprintf2(format, args);
 147     va_end(args);
 148     return(buf);
 149 }
 150
 151 int havecharset(char *charset)
 152 {
 153     iconv_t cd;
 154
 155     if((cd = iconv_open("wchar_t", charset)) == (iconv_t)-1)
 156         return(0);
 157     iconv_close(cd);
 158     if((cd = iconv_open(charset, "wchar_t")) == (iconv_t)-1)
 159         return(0);
 160     iconv_close(cd);
 161     return(1);
 162 }
 163
 164 wchar_t *icmbstowcs(char *mbs, char *charset)
 165 {
 166     int ret;
 167     char *buf;
 168     char *p, *p2;
 169     size_t len1, len2, bufsize, data;
 170     iconv_t cd;
 171
 172     len1 = strlen(mbs) + 1;
 173     bufsize = len2 = len1 * sizeof(wchar_t);
 174     if((buf = malloc(bufsize)) == NULL)
 175     {
 176         LOGOOM(bufsize);
 177         return(NULL);
 178     }
 179     if(charset == NULL)
 180         charset = nl_langinfo(CODESET);
 181     if((cd = iconv_open("wchar_t", charset)) == (iconv_t)-1)
 182     {
 183 #ifdef DAEMON
 184         flog(LOG_ERR, "icmbstowcs: could not open iconv structure for %s: %s", charset, strerror(errno));
 185 #endif
 186         free(buf);
 187         return(NULL);
 188     }
 189     p = buf;
 190     while(len1 > 0)
 191     {
 192         ret = iconv(cd, &mbs, &len1, &p, &len2);
 193         if(ret < 0)
 194         {
 195             if(errno == E2BIG)
 196             {
 197                 data = p - buf;
 198                 len2 += 128;
 199                 bufsize += 128;
 200                 if((p2 = realloc(buf, bufsize)) == NULL)
 201                 {
 202                     LOGOOM(bufsize);
 203                     free(buf);
 204                     iconv_close(cd);
 205                     return(NULL);
 206                 }
 207                 buf = p2;
 208                 p = buf + data;
 209             } else {
 210                 free(buf);
 211                 iconv_close(cd);
 212                 return(NULL);
 213             }
 214         }
 215     }
 216     if(len2 > 0)
 217         buf = realloc(buf, p - buf);
 218     iconv_close(cd);
 219     return((wchar_t *)buf);
 220 }
 221
 222 wchar_t *icsmbstowcs(char *mbs, char *charset, wchar_t *def)
 223 {
 224     static wchar_t *buf = NULL;
 225
 226     if(buf != NULL)
 227         free(buf);
 228     if((buf = icmbstowcs(mbs, charset)) == NULL)
 229     {
 230         if((def != NULL) && (*def == L'~'))
 231         {
 232 #ifdef DAEMON
 233             flog(LOG_WARNING, "icsmbstowcs: could not convert wcs string into charset %s: %s", charset, strerror(errno));
 234 #endif
 235             def++;
 236         }
 237         return(def);
 238     }
 239     return(buf);
 240 }
 241
 242 char *icwcstombs(wchar_t *wcs, char *charset)
 243 {
 244     int ret;
 245     char *buf;
 246     char *p, *p2;
 247     size_t len1, len2, bufsize, data;
 248     iconv_t cd;
 249
 250     len1 = sizeof(wchar_t) * (wcslen(wcs) + 1);
 251     bufsize = len2 = len1;
 252     if((buf = malloc(bufsize)) == NULL)
 253     {
 254 #ifdef DAEMON
 255         LOGOOM(bufsize);
 256 #endif
 257         return(NULL);
 258     }
 259     if(charset == NULL)
 260         charset = nl_langinfo(CODESET);
 261     if((cd = iconv_open(charset, "wchar_t")) == (iconv_t)-1)
 262     {
 263 #ifdef DAEMON
 264         flog(LOG_ERR, "icwcstombs: could not open iconv structure for %s: %s", charset, strerror(errno));
 265 #endif
 266         free(buf);
 267         return(NULL);
 268     }
 269     p = buf;
 270     while(len1 > 0)
 271     {
 272         ret = iconv(cd, (char **)&wcs, &len1, &p, &len2);
 273         if(ret < 0)
 274         {
 275             if(errno == E2BIG)
 276             {
 277                 data = p - buf;
 278                 len2 += 128;
 279                 bufsize += 128;
 280                 if((p2 = realloc(buf, bufsize)) == NULL)
 281                 {
 282                     LOGOOM(bufsize);
 283                     free(buf);
 284                     iconv_close(cd);
 285                     return(NULL);
 286                 }
 287                 buf = p2;
 288                 p = buf + data;
 289             } else {
 290                 free(buf);
 291                 iconv_close(cd);
 292                 return(NULL);
 293             }
 294         }
 295     }
 296     if(len2 > 0)
 297         buf = realloc(buf, p - buf);
 298     iconv_close(cd);
 299     return(buf);
 300 }
 301
 302 char *icswcstombs(wchar_t *wcs, char *charset, char *def)
 303 {
 304     static char *buf = NULL;
 305
 306     if(buf != NULL)
 307         free(buf);
 308     if((buf = icwcstombs(wcs, charset)) == NULL)
 309     {
 310         if((def != NULL) && (*def == '~'))
 311         {
 312 #ifdef DAEMON
 313             flog(LOG_WARNING, "icswcstombs: could not convert mbs string from charset %s: %s", charset, strerror(errno));
 314 #endif
 315             def++;
 316         }
 317         return(def);
 318     }
 319     return(buf);
 320 }
 321
 322 wchar_t *wcstolower(wchar_t *wcs)
 323 {
 324     wchar_t *p;
 325
 326     for(p = wcs; *p != L'\0'; p++)
 327         *p = towlower(*p);
 328     return(wcs);
 329 }
 330
 331 wchar_t ucptowc(int ucp)
 332 {
 333     int ret;
 334     unsigned long ucpbuf;
 335     char *buf;
 336     char *mbsp, *p, *p2;
 337     wchar_t res;
 338     size_t len1, len2, bufsize, data;
 339     iconv_t cd;
 340
 341     ucpbuf = htonl(ucp);
 342     mbsp = (char *)&ucpbuf;
 343     len1 = 4;
 344     bufsize = len2 = len1 * sizeof(wchar_t);
 345     if((buf = malloc(bufsize)) == NULL)
 346     {
 347         LOGOOM(bufsize);
 348         return(L'\0');
 349     }
 350     if((cd = iconv_open("wchar_t", "UCS-4BE")) == (iconv_t)-1)
 351     {
 352 #ifdef DAEMON
 353         flog(LOG_ERR, "ucptowc: could not open iconv structure for UCS-4BE: %s", strerror(errno));
 354 #endif
 355         free(buf);
 356         return(L'\0');
 357     }
 358     p = buf;
 359     while(len1 > 0)
 360     {
 361         ret = iconv(cd, &mbsp, &len1, &p, &len2);
 362         if(ret < 0)
 363         {
 364             if(errno == E2BIG)
 365             {
 366                 data = p - buf;
 367                 len2 += 128;
 368                 bufsize += 128;
 369                 if((p2 = realloc(buf, bufsize)) == NULL)
 370                 {
 371                     LOGOOM(bufsize);
 372                     free(buf);
 373                     iconv_close(cd);
 374                     return(L'\0');
 375                 }
 376                 buf = p2;
 377                 p = buf + data;
 378             } else {
 379                 free(buf);
 380                 iconv_close(cd);
 381                 return(L'\0');
 382             }
 383         }
 384     }
 385     if(len2 > 0)
 386         buf = realloc(buf, p - buf);
 387     iconv_close(cd);
 388     res = *(wchar_t *)buf;
 389     free(buf);
 390     return(res);
 391 }
 392
 393 void _sizebuf(void **buf, size_t *bufsize, size_t reqsize, size_t elsize, int algo)
 394 {
 395     if(*bufsize >= reqsize)
 396         return;
 397     switch(algo)
 398     {
 399     case 0:
 400         *buf = srealloc(*buf, elsize * ((*bufsize) = reqsize));
 401         break;
 402     case 1:
 403         if(*bufsize == 0)
 404             *bufsize = 1;
 405         while(*bufsize < reqsize)
 406             *bufsize <<= 1;
 407         *buf = srealloc(*buf, elsize * (*bufsize));
 408         break;
 409     }
 410 }
 411
 412 double ntime(void)
 413 {
 414     struct timeval tv;
 415
 416     gettimeofday(&tv, NULL);
 417     return((double)tv.tv_sec + ((double)tv.tv_usec / 1000000.0));
 418 }
 419
 420 int wcsexists(wchar_t *h, wchar_t *n)
 421 {
 422     int i, o, nl, hl;
 423     wchar_t *ln, *lh;
 424
 425     ln = alloca(sizeof(*ln) * (nl = wcslen(n)));
 426     for(i = 0; i < nl; i++)
 427         ln[i] = towlower(n[i]);
 428     lh = alloca(sizeof(*lh) * (hl = wcslen(h)));
 429     if(nl > hl)
 430         return(0);
 431     for(i = 0; i < nl; i++)
 432         lh[i] = towlower(h[i]);
 433     i = 0;
 434     while(1)
 435     {
 436         for(o = 0; o < nl; o++)
 437         {
 438             if(lh[i + o] != ln[o])
 439                 break;
 440         }
 441         if(o == nl)
 442             return(1);
 443         if(i == hl - nl)
 444             return(0);
 445         lh[i + nl] = towlower(h[i + nl]);
 446         i++;
 447     }
 448 }
 449
 450 #ifndef HAVE_WCSCASECMP
 451 int wcscasecmp(const wchar_t *s1, const wchar_t *s2)
 452 {
 453     for(; (towlower(*s1) == towlower(*s2)) && (*s1 != L'\0'); s1++, s2++);
 454     return(towlower(*s1) - towlower(*s2));
 455 }
 456 #endif
 457
 458 char *hexencode(char *data, size_t datalen)
 459 {
 460     char *buf, this;
 461     size_t bufsize, bufdata;
 462     int dig;
 463
 464     buf = NULL;
 465     bufsize = bufdata = 0;
 466     for(; datalen > 0; datalen--, data++)
 467     {
 468         dig = (*data & 0xF0) >> 4;
 469         if(dig > 9)
 470             this = 'A' + dig - 10;
 471         else
 472             this = dig + '0';
 473         addtobuf(buf, this);
 474         dig = *data & 0x0F;
 475         if(dig > 9)
 476             this = 'A' + dig - 10;
 477         else
 478             this = dig + '0';
 479         addtobuf(buf, this);
 480     }
 481     addtobuf(buf, 0);
 482     return(buf);
 483 }
 484
 485 char *hexdecode(char *data, size_t *len)
 486 {
 487     char *buf, this, bit;
 488     size_t bufsize, bufdata;
 489
 490     buf = NULL;
 491     bufsize = bufdata = 0;
 492     for(bit = 4, this = 0; *data; data++)
 493     {
 494         if((*data >= 'A') && (*data <= 'F'))
 495         {
 496             this |= (this & 0x0F) | ((*data - 'A' + 10) << bit);
 497         } else if((*data >= 'a') && (*data <= 'f')) {
 498             this |= (this & 0x0F) | ((*data - 'a' + 10) << bit);
 499         } else if((*data >= '0') && (*data <= '9')) {
 500             this |= (this & 0x0F) | ((*data - '0') << bit);
 501         } else if(*data == '\n') {
 502             continue;
 503         } else {
 504             if(buf != NULL)
 505                 free(buf);
 506             return(NULL);
 507         }
 508         if(bit == 4) {
 509             bit = 0;
 510         } else {
 511             bit = 4;
 512             addtobuf(buf, this);
 513             this = 0;
 514         }
 515     }
 516     if(bit != 4) {
 517         if(buf != NULL)
 518             free(buf);
 519         return(NULL);
 520     }
 521     addtobuf(buf, 0);
 522     if(len != NULL)
 523         *len = bufdata - 1;
 524     return(buf);
 525 }
 526
 527 char *base64encode(char *data, size_t datalen)
 528 {
 529     char *buf;
 530     size_t bufsize, bufdata;
 531
 532     if(datalen == 0)
 533         return(sstrdup(""));
 534     buf = NULL;
 535     bufsize = bufdata = 0;
 536     while(datalen >= 3)
 537     {
 538         addtobuf(buf, base64set[(data[0] & 0xfc) >> 2]);
 539         addtobuf(buf, base64set[((data[0] & 0x03) << 4) | ((data[1] & 0xf0) >> 4)]);
 540         addtobuf(buf, base64set[((data[1] & 0x0f) << 2) | ((data[2] & 0xc0) >> 6)]);
 541         addtobuf(buf, base64set[data[2] & 0x3f]);
 542         datalen -= 3;
 543         data += 3;
 544     }
 545     if(datalen == 1)
 546     {
 547         addtobuf(buf, base64set[(data[0] & 0xfc) >> 2]);
 548         addtobuf(buf, base64set[(data[0] & 0x03) << 4]);
 549         bufcat(buf, "==", 2);
 550     }
 551     if(datalen == 2)
 552     {
 553         addtobuf(buf, base64set[(data[0] & 0xfc) >> 2]);
 554         addtobuf(buf, base64set[((data[0] & 0x03) << 4) | ((data[1] & 0xf0) >> 4)]);
 555         addtobuf(buf, base64set[(data[1] & 0x0f) << 2]);
 556         addtobuf(buf, '=');
 557     }
 558     addtobuf(buf, 0);
 559     return(buf);
 560 }
 561
 562 char *base64decode(char *data, size_t *datalen)
 563 {
 564     int b, c;
 565     char *buf, cur;
 566     size_t bufsize, bufdata;
 567
 568     buf = NULL;
 569     bufsize = bufdata = 0;
 570     cur = 0;
 571     b = 8;
 572     for(; *data > 0; data++)
 573     {
 574         c = (int)(unsigned char)*data;
 575         if(c == '=')
 576             break;
 577         if(c == '\n')
 578             continue;
 579         if(base64rev[c] == -1)
 580         {
 581             if(buf != NULL)
 582                 free(buf);
 583             return(NULL);
 584         }
 585         b -= 6;
 586         if(b <= 0)
 587         {
 588             cur |= base64rev[c] >> -b;
 589             addtobuf(buf, cur);
 590             b += 8;
 591             cur = 0;
 592         }
 593         cur |= base64rev[c] << b;
 594     }
 595     if(datalen != NULL)
 596         *datalen = bufdata;
 597     addtobuf(buf, 0);
 598     return(buf);
 599 }
 600
 601 char *base32encode(char *data, size_t datalen)
 602 {
 603     char *buf;
 604     size_t bufsize, bufdata;
 605
 606     if(datalen == 0)
 607         return(sstrdup(""));
 608     buf = NULL;
 609     bufsize = bufdata = 0;
 610     while(datalen >= 5)
 611     {
 612         addtobuf(buf, base32set[((data[0] & 0xf8) >> 3)]);
 613         addtobuf(buf, base32set[((data[0] & 0x07) << 2) | ((data[1] & 0xc0) >> 6)]);
 614         addtobuf(buf, base32set[((data[1] & 0x3e) >> 1)]);
 615         addtobuf(buf, base32set[((data[1] & 0x01) << 4) | ((data[2] & 0xf0) >> 4)]);
 616         addtobuf(buf, base32set[((data[2] & 0x0f) << 1) | ((data[3] & 0x80) >> 7)]);
 617         addtobuf(buf, base32set[((data[3] & 0x7c) >> 2)]);
 618         addtobuf(buf, base32set[((data[3] & 0x03) << 3) | ((data[4] & 0xe0) >> 5)]);
 619         addtobuf(buf, base32set[data[4] & 0x1f]);
 620         datalen -= 5;
 621         data += 5;
 622     }
 623     if(datalen == 1)
 624     {
 625         addtobuf(buf, base32set[((data[0] & 0xf8) >> 3)]);
 626         addtobuf(buf, base32set[((data[0] & 0x07) << 2)]);
 627         bufcat(buf, "======", 6);
 628     }
 629     if(datalen == 2)
 630     {
 631         addtobuf(buf, base32set[((data[0] & 0xf8) >> 3)]);
 632         addtobuf(buf, base32set[((data[0] & 0x07) << 2) | ((data[1] & 0xc0) >> 6)]);
 633         addtobuf(buf, base32set[((data[1] & 0x3e) >> 1)]);
 634         addtobuf(buf, base32set[((data[1] & 0x01) << 4)]);
 635         bufcat(buf, "====", 4);
 636     }
 637     if(datalen == 3)
 638     {
 639         addtobuf(buf, base32set[((data[0] & 0xf8) >> 3)]);
 640         addtobuf(buf, base32set[((data[0] & 0x07) << 2) | ((data[1] & 0xc0) >> 6)]);
 641         addtobuf(buf, base32set[((data[1] & 0x3e) >> 1)]);
 642         addtobuf(buf, base32set[((data[1] & 0x01) << 4) | ((data[2] & 0xf0) >> 4)]);
 643         addtobuf(buf, base32set[((data[2] & 0x0f) << 1)]);
 644         bufcat(buf, "===", 3);
 645     }
 646     if(datalen == 4)
 647     {
 648         addtobuf(buf, base32set[((data[0] & 0xf8) >> 3)]);
 649         addtobuf(buf, base32set[((data[0] & 0x07) << 2) | ((data[1] & 0xc0) >> 6)]);
 650         addtobuf(buf, base32set[((data[1] & 0x3e) >> 1)]);
 651         addtobuf(buf, base32set[((data[1] & 0x01) << 4) | ((data[2] & 0xf0) >> 4)]);
 652         addtobuf(buf, base32set[((data[2] & 0x0f) << 1) | ((data[3] & 0x80) >> 7)]);
 653         addtobuf(buf, base32set[((data[3] & 0x7c) >> 2)]);
 654         addtobuf(buf, base32set[((data[3] & 0x03) << 3)]);
 655         bufcat(buf, "=", 1);
 656     }
 657     addtobuf(buf, 0);
 658     return(buf);
 659 }
 660
 661 char *base32decode(char *data, size_t *datalen)
 662 {
 663     int b, c;
 664     char *buf, cur;
 665     size_t bufsize, bufdata;
 666
 667     buf = NULL;
 668     bufsize = bufdata = 0;
 669     cur = 0;
 670     b = 8;
 671     for(; *data > 0; data++)
 672     {
 673         c = (int)(unsigned char)*data;
 674         if(c == '=')
 675             break;
 676         if(c == '\n')
 677             continue;
 678         if(base32rev[c] == -1)
 679         {
 680             if(buf != NULL)
 681                 free(buf);
 682             return(NULL);
 683         }
 684         b -= 5;
 685         if(b <= 0)
 686         {
 687             cur |= base32rev[c] >> -b;
 688             addtobuf(buf, cur);
 689             b += 8;
 690             cur = 0;
 691         }
 692         cur |= base32rev[c] << b;
 693     }
 694     if(datalen != NULL)
 695         *datalen = bufdata;
 696     addtobuf(buf, 0);
 697     return(buf);
 698 }
 699
 700 void _freeparr(void **arr)
 701 {
 702     void **buf;
 703
 704     if(arr == NULL)
 705         return;
 706     for(buf = arr; *buf != NULL; buf++)
 707         free(*buf);
 708     free(arr);
 709 }
 710
 711 int _parrlen(void **arr)
 712 {
 713     int i;
 714
 715     if(arr == NULL)
 716         return(0);
 717     for(i = 0; *arr != NULL; arr++)
 718         i++;
 719     return(i);
 720 }
 721
 722 char *getetcpath(char *binpath)
 723 {
 724     int f;
 725     char *etcpath, *p;
 726     size_t etcpathsize, etcpathdata;
 727
 728     etcpath = NULL;
 729     etcpathsize = etcpathdata = 0;
 730     f = 1;
 731     do
 732     {
 733         if(f)
 734             f = 0;
 735         else
 736             binpath++;
 737         for(p = binpath; *p && (*p != ':'); p++);
 738         for(; (p >= binpath) && (*p != '/'); p--);
 739         if(p >= binpath)
 740         {
 741             if(etcpathdata > 0)
 742                 addtobuf(etcpath, ':');
 743             bufcat(etcpath, binpath, p - binpath + 1);
 744             bufcat(etcpath, "etc", 3);
 745         }
 746     } while((binpath = strchr(binpath, ':')) != NULL);
 747     addtobuf(etcpath, 0);
 748     return(etcpath);
 749 }
 750
 751 char *findfile(char *name, char *homedir, int filldef)
 752 {
 753     char *path, *binpath, *etcpath, *p;
 754     struct passwd *pw;
 755     int mode, homeonly;
 756
 757     if(name == NULL)
 758         return(NULL);
 759
 760     mode = R_OK | (filldef ? W_OK : 0);
 761     homeonly = homedir != NULL;
 762
 763     if(!strchr(name, '/'))
 764     {
 765         if(homedir == NULL)
 766             homedir = getenv("HOME");
 767         if((homedir == NULL) && ((pw = getpwuid(getuid())) != NULL))
 768             homedir = pw->pw_dir;
 769         if((homedir != NULL) && ((path = sprintf2("%s/.%s", homedir, name)) != NULL))
 770         {
 771             if(!access(path, mode))
 772                 return(path);
 773             free(path);
 774         }
 775     }
 776
 777     if(!homeonly)
 778     {
 779         if(strchr(name, '/') != NULL)
 780         {
 781             if(!access(name, mode))
 782                 return(sstrdup(name));
 783         } else {
 784             if((binpath = getenv("PATH")) == NULL)
 785                 etcpath = sstrdup("/usr/local/etc:/etc:/usr/etc");
 786             else
 787                 etcpath = getetcpath(binpath);
 788             for(p = strtok(etcpath, ":"); p != NULL; p = strtok(NULL, ":"))
 789             {
 790                 if((path = sprintf2("%s/%s", p, name)) != NULL)
 791                 {
 792                     if(!access(path, mode))
 793                     {
 794                         free(etcpath);
 795                         return(path);
 796                     }
 797                     free(path);
 798                 }
 799             }
 800             free(etcpath);
 801         }
 802     }
 803
 804     if(filldef) {
 805         if(homedir)
 806             return(sprintf2("%s/.%s", homedir, name));
 807         return(sprintf2("/etc/%s", name));
 808     } else {
 809         return(NULL);
 810     }
 811 }
 812
 813 struct strpair *newstrpair(char *key, char *val, struct strpair **list)
 814 {
 815     struct strpair *pair;
 816
 817     pair = smalloc(sizeof(*pair));
 818     memset(pair, 0, sizeof(*pair));
 819     if(key != NULL)
 820         pair->key = sstrdup(key);
 821     if(val != NULL)
 822         pair->val = sstrdup(val);
 823     if(list != NULL)
 824     {
 825         pair->next = *list;
 826         *list = pair;
 827     }
 828     return(pair);
 829 }
 830
 831 void freestrpair(struct strpair *pair, struct strpair **list)
 832 {
 833     struct strpair *cur;
 834
 835     for(cur = *list; cur != NULL; list = &(cur->next), cur = cur->next)
 836     {
 837         if(cur == pair)
 838         {
 839             *list = cur->next;
 840             break;
 841         }
 842     }
 843     free(pair->key);
 844     free(pair->val);
 845     free(pair);
 846 }
 847
 848 char *spfind(struct strpair *list, char *key)
 849 {
 850     for(; list != NULL; list = list->next)
 851     {
 852         if(!strcmp(list->key, key))
 853             return(list->val);
 854     }
 855     return(NULL);
 856 }
 857
 858 struct wcspair *newwcspair(wchar_t *key, wchar_t *val, struct wcspair **list)
 859 {
 860     struct wcspair *pair;
 861
 862     pair = smalloc(sizeof(*pair));
 863     memset(pair, 0, sizeof(*pair));
 864     if(key != NULL)
 865         pair->key = swcsdup(key);
 866     if(val != NULL)
 867         pair->val = swcsdup(val);
 868     if(list != NULL)
 869     {
 870         pair->next = *list;
 871         *list = pair;
 872     }
 873     return(pair);
 874 }
 875
 876 void freewcspair(struct wcspair *pair, struct wcspair **list)
 877 {
 878     struct wcspair *cur;
 879
 880     for(cur = *list; cur != NULL; list = &(cur->next), cur = cur->next)
 881     {
 882         if(cur == pair)
 883         {
 884             *list = cur->next;
 885             break;
 886         }
 887     }
 888     free(pair->key);
 889     free(pair->val);
 890     free(pair);
 891 }
 892
 893 wchar_t *wpfind(struct wcspair *list, wchar_t *key)
 894 {
 895     for(; list != NULL; list = list->next)
 896     {
 897         if(!wcscmp(list->key, key))
 898             return(list->val);
 899     }
 900     return(NULL);
 901 }
 902
 903 static int btheight(struct btree *tree)
 904 {
 905     if(tree == NULL)
 906         return(0);
 907     return(tree->h);
 908 }
 909
 910 static void btsetheight(struct btree *tree)
 911 {
 912     int lh, rh;
 913
 914     if(tree == NULL)
 915         return;
 916     lh = btheight(tree->l);
 917     rh = btheight(tree->r);
 918     tree->h = ((lh > rh)?lh:rh) + 1;
 919 }
 920
 921 static void bbtrl(struct btree **tree);
 922
 923 static void bbtrr(struct btree **tree)
 924 {
 925     struct btree *m, *l, *r;
 926
 927     if(btheight((*tree)->l->r) > btheight((*tree)->l->l))
 928         bbtrl(&(*tree)->l);
 929     r = (*tree);
 930     l = r->l;
 931     m = l->r;
 932     r->l = m;
 933     btsetheight(r);
 934     l->r = r;
 935     btsetheight(l);
 936     *tree = l;
 937 }
 938
 939 static void bbtrl(struct btree **tree)
 940 {
 941     struct btree *m, *l, *r;
 942
 943     if(btheight((*tree)->r->l) > btheight((*tree)->r->r))
 944         bbtrr(&(*tree)->r);
 945     l = (*tree);
 946     r = l->r;
 947     m = r->l;
 948     l->r = m;
 949     btsetheight(l);
 950     r->l = l;
 951     btsetheight(r);
 952     *tree = r;
 953 }
 954
 955 int bbtreedel(struct btree **tree, void *item, int (*cmp)(void *, void *))
 956 {
 957     int c, r;
 958     struct btree *s, **sp, *o;
 959
 960     if(*tree == NULL)
 961         return(0);
 962     if((c = cmp(item, (*tree)->d)) < 0) {
 963         r = bbtreedel(&(*tree)->l, item, cmp);
 964     } else if(c > 0) {
 965         r = bbtreedel(&(*tree)->r, item, cmp);
 966     } else {
 967         r = 1;
 968         o = *tree;
 969         if(((*tree)->r != NULL) && ((*tree)->l != NULL)) {
 970             sp = &(*tree)->r;
 971             s = *sp;
 972             while(s->l != NULL) {
 973                 sp = &(s->l);
 974                 s = *sp;
 975             }
 976             *sp = NULL;
 977             s->l = (*tree)->l;
 978             s->r = (*tree)->r;
 979             *tree = s;
 980         } else if((*tree)->l != NULL) {
 981             *tree = (*tree)->l;
 982         } else if((*tree)->r != NULL) {
 983             *tree = (*tree)->r;
 984         } else {
 985             *tree = NULL;
 986         }
 987         free(o);
 988     }
 989     if(*tree != NULL) {
 990         btsetheight(*tree);
 991         if(btheight((*tree)->l) > btheight((*tree)->r) + 1)
 992             bbtrr(tree);
 993         if(btheight((*tree)->r) > btheight((*tree)->l) + 1)
 994             bbtrl(tree);
 995     }
 996     return(r);
 997 }
 998
 999 int bbtreeput(struct btree **tree, void *item, int (*cmp)(void *, void *))
1000 {
1001     int c, r;
1002
1003     if(*tree == NULL) {
1004         *tree = smalloc(sizeof(**tree));
1005         (*tree)->l = (*tree)->r = NULL;
1006         (*tree)->d = item;
1007         (*tree)->h = 1;
1008         return(1);
1009     }
1010     if((c = cmp(item, (*tree)->d)) < 0)
1011         r = bbtreeput(&(*tree)->l, item, cmp);
1012     else if(c > 0)
1013         r = bbtreeput(&(*tree)->r, item, cmp);
1014     else
1015         return(0);
1016     btsetheight(*tree);
1017     if(btheight((*tree)->l) > btheight((*tree)->r) + 1)
1018         bbtrr(tree);
1019     if(btheight((*tree)->r) > btheight((*tree)->l) + 1)
1020         bbtrl(tree);
1021     return(r);
1022 }
1023
1024 void *btreeget(struct btree *tree, void *key, int (*cmp)(void *, void *))
1025 {
1026     int c;
1027
1028     while(1) {
1029         if(tree == NULL)
1030             return(NULL);
1031         c = cmp(key, tree->d);
1032         if(c < 0)
1033             tree = tree->l;
1034         else if(c > 0)
1035             tree = tree->r;
1036         else
1037             return(tree->d);
1038     }
1039 }
1040
1041 void btreefree(struct btree *tree)
1042 {
1043     if(tree == NULL)
1044         return;
1045     btreefree(tree->l);
1046     btreefree(tree->r);
1047     free(tree);
1048 }
1049
1050 static void *btreenext(void **iterp)
1051 {
1052     struct treeiter *iter;
1053     int s;
1054     struct btree *n;
1055
1056     if((iter = *iterp) == NULL)
1057         return(NULL);
1058     while(1) {
1059         s = iter->st[iter->sp].s;
1060         n = iter->st[iter->sp].n;
1061         if(s == 0) {
1062             iter->st[iter->sp].s = 1;
1063             if(n->l != NULL) {
1064                 iter->sp++;
1065                 sizebuf2(iter->st, iter->sp + 1, 1);
1066                 iter->st[iter->sp].s = 0;
1067                 iter->st[iter->sp].n = n->l;
1068             }
1069         } else if(s == 1) {
1070             iter->st[iter->sp].s = 2;
1071             return(iter->st[iter->sp].n->d);
1072         } else if(s == 2) {
1073             iter->st[iter->sp].s = 3;
1074             if(n->r != NULL) {
1075                 iter->sp++;
1076                 sizebuf2(iter->st, iter->sp + 1, 1);
1077                 iter->st[iter->sp].s = 0;
1078                 iter->st[iter->sp].n = n->r;
1079             }
1080         } else {
1081             iter->sp--;
1082             if(iter->sp < 0) {
1083                 free(iter->st);
1084                 free(iter);
1085                 *iterp = NULL;
1086                 return(NULL);
1087             }
1088         }
1089     }
1090 }
1091
1092 static void *btreefirst(struct btree *tree, void **iterp)
1093 {
1094     struct treeiter *iter;
1095
1096     if(tree == NULL) {
1097         *iterp = NULL;
1098         return(NULL);
1099     }
1100     *iterp = iter = memset(smalloc(sizeof(*iter)), 0, sizeof(*iter));
1101     sizebuf2(iter->st, 1, 1);
1102     iter->st[0].n = tree;
1103     iter->st[0].s = 0;
1104     return(btreenext(iterp));
1105 }
1106
1107 static void btreestop(void **iterp)
1108 {
1109     struct treeiter *iter;
1110
1111     if((iter = *iterp) == NULL)
1112         return;
1113     if(iter->st != NULL)
1114         free(iter->st);
1115     free(iter);
1116     *iterp = NULL;
1117 }
1118
1119 void *btreeiter(struct btree *tree)
1120 {
1121     static void *iter = NULL;
1122
1123     if(tree == NULL) {
1124         return(btreenext(&iter));
1125     } else {
1126         if(iter != NULL)
1127             btreestop(&iter);
1128         return(btreefirst(tree, &iter));
1129     }
1130 }