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