util.c

   1 /*
   2 Copyright (c) 2003-2006 by Juliusz Chroboczek
   3
   4 Permission is hereby granted, free of charge, to any person obtaining a copy
   5 of this software and associated documentation files (the "Software"), to deal
   6 in the Software without restriction, including without limitation the rights
   7 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   8 copies of the Software, and to permit persons to whom the Software is
   9 furnished to do so, subject to the following conditions:
  10
  11 The above copyright notice and this permission notice shall be included in
  12 all copies or substantial portions of the Software.
  13
  14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
  17 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  18 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  19 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  20 THE SOFTWARE.
  21 */
  22
  23 #include "polipo.h"
  24
  25 /* Note that this is different from GNU's strndup(3). */
  26 char *
  27 strdup_n(const char *restrict buf, int n)
  28 {
  29     char *s;
  30     s = malloc(n + 1);
  31     if(s == NULL)
  32         return NULL;
  33     memcpy(s, buf, n);
  34     s[n] = '\0';
  35     return s;
  36 }
  37
  38 int
  39 snnprintf(char *restrict buf, int n, int len, const char *format, ...)
  40 {
  41     va_list args;
  42     int rc = -1;
  43     if(n < 0) return -2;
  44     va_start(args, format);
  45     if(n < len)
  46         rc = vsnprintf(buf + n, len - n, format, args);
  47     va_end(args);
  48     if(rc >= 0 && n + rc <= len)
  49         return n + rc;
  50     else
  51         return -1;
  52 }
  53
  54 int
  55 snnprint_n(char *restrict buf, int n, int len, const char *s, int slen)
  56 {
  57     int i = 0;
  58     if(n < 0) return -2;
  59     while(i < slen && n < len)
  60         buf[n++] = s[i++];
  61     if(n < len)
  62         return n;
  63     else
  64         return -1;
  65 }
  66
  67 int
  68 strcmp_n(const char *string, const char *buf, int n)
  69 {
  70     int i;
  71     i = 0;
  72     while(string[i] != '\0' && i < n) {
  73         if(string[i] < buf[i])
  74             return -1;
  75         else if(string[i] > buf[i])
  76             return 1;
  77         i++;
  78     }
  79     if(string[i] == '\0' || i == n)
  80         return 0;
  81     else if(i == n)
  82         return 1;
  83     else
  84         return -1;
  85 }
  86
  87 int
  88 letter(char c)
  89 {
  90     if(c >= 'A' && c <= 'Z') return 1;
  91     if(c >= 'a' && c <= 'z') return 1;
  92     return 0;
  93 }
  94
  95 int
  96 digit(char c)
  97 {
  98     if(c >= '0' && c <= '9')
  99         return 1;
 100     return 0;
 101 }
 102
 103 char
 104 lwr(char a)
 105 {
 106     if(a >= 'A' && a <= 'Z')
 107         return a | 0x20;
 108     else
 109         return a;
 110 }
 111
 112 char *
 113 lwrcpy(char *restrict dst, const char *restrict src, int n)
 114 {
 115     int i;
 116     for(i = 0; i < n; i++)
 117         dst[i] = lwr(src[i]);
 118     return dst;
 119 }
 120
 121 int
 122 lwrcmp(const char *as, const char *bs, int n)
 123 {
 124     int i;
 125     for(i = 0; i < n; i++) {
 126         char a = lwr(as[i]), b = lwr(bs[i]);
 127         if(a < b)
 128             return -1;
 129         else if(a > b)
 130             return 1;
 131     }
 132     return 0;
 133 }
 134
 135 int
 136 strcasecmp_n(const char *string, const char *buf, int n)
 137 {
 138     int i;
 139     i = 0;
 140     while(string[i] != '\0' && i < n) {
 141         char a = lwr(string[i]), b = lwr(buf[i]);
 142         if(a < b)
 143             return -1;
 144         else if(a > b)
 145             return 1;
 146         i++;
 147     }
 148     if(string[i] == '\0' && i == n)
 149         return 0;
 150     else if(i == n)
 151         return 1;
 152     else
 153         return -1;
 154 }
 155
 156 int
 157 atoi_n(const char *restrict string, int n, int len, int *value_return)
 158 {
 159     int i = n;
 160     int val = 0;
 161
 162     if(i >= len || !digit(string[i]))
 163         return -1;
 164
 165     while(i < len && digit(string[i])) {
 166         val = val * 10 + (string[i] - '0');
 167         i++;
 168     }
 169     *value_return = val;
 170     return i;
 171 }
 172
 173 int
 174 isWhitespace(const char *string)
 175 {
 176     while(*string != '\0') {
 177         if(*string == ' ' || *string == '\t')
 178             string++;
 179         else
 180             return 0;
 181     }
 182     return 1;
 183 }
 184
 185 #ifndef HAVE_MEMRCHR
 186 void *
 187 memrchr(const void *s, int c, size_t n)
 188 {
 189     const unsigned char *ss = s;
 190     unsigned char cc = c;
 191     size_t i;
 192     for(i = n - 1; i >= 0; i--)
 193         if(ss[i] == cc)
 194             return (void*)(ss + i);
 195     return NULL;
 196 }
 197 #endif
 198
 199 int
 200 h2i(char h)
 201 {
 202     if(h >= '0' && h <= '9')
 203         return h - '0';
 204     else if(h >= 'a' && h <= 'f')
 205         return h - 'a' + 10;
 206     else if(h >= 'A' && h <= 'F')
 207         return h - 'A' + 10;
 208     else
 209         return -1;
 210 }
 211
 212 char
 213 i2h(int i)
 214 {
 215     if(i < 0 || i >= 16)
 216         return '?';
 217     if(i < 10)
 218         return i + '0';
 219     else
 220         return i - 10 + 'A';
 221 }
 222
 223 /* floor(log2(x)) */
 224 int
 225 log2_floor(int x)
 226 {
 227     int i, j;
 228
 229     assert(x > 0);
 230
 231     i = 0;
 232     j = 1;
 233     while(2 * j <= x) {
 234         i++;
 235         j *= 2;
 236     }
 237     return i;
 238 }
 239
 240 /* ceil(log2(x)) */
 241 int
 242 log2_ceil(int x)
 243 {
 244     int i, j;
 245
 246     assert(x > 0);
 247
 248     i = 0;
 249     j = 1;
 250     while(j < x) {
 251         i++;
 252         j *= 2;
 253     }
 254     return i;
 255 }
 256
 257 #ifdef HAVE_ASPRINTF
 258 char *
 259 vsprintf_a(const char *f, va_list args)
 260 {
 261     char *r;
 262     int rc;
 263     rc = vasprintf(&r, f, args);
 264     if(rc < 0)
 265         return NULL;
 266     return r;
 267
 268 }
 269 #else
 270 char*
 271 vsprintf_a(const char *f, va_list args)
 272 {
 273     int n, size;
 274     char buf[64];
 275     char *string;
 276
 277     n = vsnprintf(buf, 64, f, args);
 278     if(n >= 0 && n < 64) {
 279         return strdup_n(buf, n);
 280     }
 281     if(n >= 64)
 282         size = n + 1;
 283     else
 284         size = 96;
 285
 286     while(1) {
 287         string = malloc(size);
 288         if(!string)
 289             return NULL;
 290         n = vsnprintf(string, size, f, args);
 291         if(n >= 0 && n < size)
 292             return string;
 293         else if(n >= size)
 294             size = n + 1;
 295         else
 296             size = size * 3 / 2;
 297         free(string);
 298         if(size > 16 * 1024)
 299             return NULL;
 300     }
 301     /* NOTREACHED */
 302 }
 303 #endif
 304
 305 char*
 306 sprintf_a(const char *f, ...)
 307 {
 308     char *s;
 309     va_list args;
 310     va_start(args, f);
 311     s = vsprintf_a(f, args);
 312     va_end(args);
 313     return s;
 314 }
 315
 316 unsigned int
 317 hash(unsigned int seed, const void *restrict key, int key_size,
 318      unsigned int hash_size)
 319 {
 320     int i;
 321     unsigned int h;
 322
 323     h = seed;
 324     for(i = 0; i < key_size; i++)
 325         h = (h << 5) + (h >> (hash_size - 5)) +
 326             ((unsigned char*)key)[i];
 327     return h & ((1 << hash_size) - 1);
 328 }
 329
 330 char *
 331 pstrerror(int e)
 332 {
 333     char *s;
 334     static char buf[20];
 335
 336     switch(e) {
 337     case EDOSHUTDOWN: s = "Immediate shutdown requested"; break;
 338     case EDOGRACEFUL: s = "Graceful shutdown requested"; break;
 339     case EDOTIMEOUT: s = "Timeout"; break;
 340     case ECLIENTRESET: s = "Connection reset by client"; break;
 341     case ESYNTAX: s = "Incorrect syntax"; break;
 342     case EREDIRECTOR: s = "Redirector error"; break;
 343     case EDNS_HOST_NOT_FOUND: s = "Host not found"; break;
 344     case EDNS_NO_ADDRESS: s = "No address"; break;
 345     case EDNS_NO_RECOVERY: s = "Permanent name server failure"; break;
 346     case EDNS_TRY_AGAIN: s = "Temporary name server failure"; break;
 347     case EDNS_INVALID: s = "Invalid reply from name server"; break;
 348     case EDNS_UNSUPPORTED: s = "Unsupported DNS reply"; break;
 349     case EDNS_FORMAT: s = "Invalid DNS query"; break;
 350     case EDNS_REFUSED: s = "DNS query refused by server"; break;
 351     case EDNS_CNAME_LOOP: s = "DNS CNAME loop"; break;
 352 #ifndef NO_SOCKS
 353     case ESOCKS_PROTOCOL: s = "SOCKS protocol error"; break;
 354     case ESOCKS_REJECT_FAIL: s = "SOCKS request rejected or failed"; break;
 355     case ESOCKS_REJECT_IDENTD: s = "SOCKS request rejected: "
 356                                    "server couldn't connect to identd";
 357     case ESOCKS_REJECT_UID_MISMATCH: s = "SOCKS request rejected: "
 358                                          "uid mismatch";
 359         break;
 360     case ESOCKS5_BASE: s = "SOCKS success"; break;
 361     case ESOCKS5_BASE + 1: s = "General SOCKS server failure"; break;
 362     case ESOCKS5_BASE + 2: s = "SOCKS connection not allowed"; break;
 363     case ESOCKS5_BASE + 3: s = "SOCKS error: network unreachable"; break;
 364     case ESOCKS5_BASE + 4: s = "SOCKS error: host unreachable"; break;
 365     case ESOCKS5_BASE + 5: s = "SOCKS error: connection refused"; break;
 366     case ESOCKS5_BASE + 6: s = "SOCKS error: TTL expired"; break;
 367     case ESOCKS5_BASE + 7: s = "SOCKS command not supported"; break;
 368     case ESOCKS5_BASE + 8: s = "SOCKS error: address type not supported";
 369         break;
 370 #endif
 371     case EUNKNOWN: s = "Unknown error"; break;
 372     default: s = NULL; break;
 373     }
 374     if(!s) s = strerror(e);
 375 #ifdef MINGW
 376     if(!s) {
 377         if(e >= WSABASEERR && e <= WSABASEERR + 2000) {
 378             /* This should be okay, as long as the caller discards the
 379                pointer before another error occurs. */
 380             snprintf(buf, 20, "Winsock error %d", e);
 381             s = buf;
 382         }
 383     }
 384 #endif
 385     if(!s) {
 386         snprintf(buf, 20, "Unknown error %d", e);
 387         s = buf;
 388     }
 389     return s;
 390 }
 391
 392 /* Like mktime(3), but UTC rather than local time */
 393 #if defined(HAVE_TIMEGM)
 394 time_t
 395 mktime_gmt(struct tm *tm)
 396 {
 397     return timegm(tm);
 398 }
 399 #elif defined(HAVE_TM_GMTOFF)
 400 time_t
 401 mktime_gmt(struct tm *tm)
 402 {
 403     time_t t;
 404     struct tm *ltm;
 405
 406     t = mktime(tm);
 407     if(t < 0)
 408         return -1;
 409     ltm = localtime(&t);
 410     if(ltm == NULL)
 411         return -1;
 412     return t + ltm->tm_gmtoff;
 413 }
 414 #elif defined(HAVE_TZSET)
 415 #ifdef HAVE_SETENV
 416 /* Taken from the Linux timegm(3) man page. */
 417 time_t
 418 mktime_gmt(struct tm *tm)
 419 {
 420     time_t t;
 421     char *tz;
 422
 423     tz = getenv("TZ");
 424     setenv("TZ", "", 1);
 425     tzset();
 426     t = mktime(tm);
 427     if(tz)
 428         setenv("TZ", tz, 1);
 429     else
 430         unsetenv("TZ");
 431     tzset();
 432     return t;
 433 }
 434 #else
 435 time_t
 436 mktime_gmt(struct tm *tm)
 437 {
 438     time_t t;
 439     char *tz;
 440     static char *old_tz = NULL;
 441
 442     tz = getenv("TZ");
 443     putenv("TZ=");
 444     tzset();
 445     t = mktime(tm);
 446     if(old_tz)
 447         free(old_tz);
 448     if(tz)
 449         old_tz = sprintf_a("TZ=%s", tz);
 450     else
 451         old_tz = strdup("TZ");  /* XXX - non-portable? */
 452     if(old_tz)
 453         putenv(old_tz);
 454     tzset();
 455     return t;
 456 }
 457 #endif
 458 #else
 459 #error no mktime_gmt implementation on this platform
 460 #endif
 461
 462
 463 AtomPtr
 464 expandTilde(AtomPtr filename)
 465 {
 466     char *buf;
 467     char *home;
 468     int len;
 469     AtomPtr ret;
 470
 471     if(filename == NULL || filename->length < 1 ||
 472        filename->string[0] != '~' || filename->string[1] != '/')
 473         return filename;
 474
 475     home = getenv("HOME");
 476     if(home == NULL) {
 477         return NULL;
 478     }
 479     len = strlen(home);
 480     buf = malloc(len + 1 + 1 + filename->length - 2);
 481     if(buf == NULL) {
 482         do_log(L_ERROR, "Could not allocate buffer.\n");
 483         return NULL;
 484     }
 485
 486     memcpy(buf, home, len);
 487     if(buf[len - 1] != '/')
 488         buf[len++] = '/';
 489     memcpy(buf + len, filename->string + 2, filename->length - 2);
 490     len += filename->length - 2;
 491     ret = internAtomN(buf, len);
 492     free(buf);
 493     if(ret != NULL)
 494         releaseAtom(filename);
 495     return ret;
 496 }
 497
 498 #ifdef HAVE_FORK
 499 void
 500 do_daemonise(int noclose)
 501 {
 502     int rc;
 503
 504     fflush(stdout);
 505     fflush(stderr);
 506
 507     rc = fork();
 508     if(rc < 0) {
 509         do_log_error(L_ERROR, errno, "Couldn't fork");
 510         exit(1);
 511     }
 512
 513     if(rc > 0)
 514         exit(0);
 515
 516     if(!noclose) {
 517         close(0);
 518         close(1);
 519         close(2);
 520     }
 521     rc = setsid();
 522     if(rc < 0) {
 523         do_log_error(L_ERROR, errno, "Couldn't create new session");
 524         exit(1);
 525     }
 526 }
 527
 528 #else
 529
 530 void
 531 do_daemonise(int noclose)
 532 {
 533     do_log(L_ERROR, "Cannot daemonise on this platform");
 534     exit(1);
 535 }
 536 #endif
 537
 538
 539 void
 540 writePid(char *pidfile)
 541 {
 542     int fd, n, rc;
 543     char buf[16];
 544
 545     fd = open(pidfile, O_WRONLY | O_CREAT | O_EXCL, 0666);
 546     if(fd < 0) {
 547         do_log_error(L_ERROR, errno,
 548                      "Couldn't create pid file %s", pidfile);
 549         exit(1);
 550     }
 551     n = snprintf(buf, 16, "%ld\n", (long)getpid());
 552     if(n < 0 || n >= 16) {
 553         close(fd);
 554         unlink(pidfile);
 555         do_log(L_ERROR, "Couldn't format pid.\n");
 556         exit(1);
 557     }
 558     rc = write(fd, buf, n);
 559     if(rc != n) {
 560         close(fd);
 561         unlink(pidfile);
 562         do_log_error(L_ERROR, errno, "Couldn't write pid");
 563         exit(1);
 564     }
 565
 566     close(fd);
 567     return;
 568 }
 569
 570 static const char b64[64] =
 571 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
 572
 573 /* "/" replaced with "-" */
 574 static const char b64fss[64] =
 575 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+-";
 576
 577 int
 578 b64cpy(char *restrict dst, const char *restrict src, int n, int fss)
 579 {
 580     const char *b = fss ? b64fss: b64;
 581     int i, j;
 582
 583     j = 0;
 584     for(i = 0; i < n; i += 3) {
 585         unsigned char a0, a1, a2;
 586         a0 = src[i];
 587         a1 = i < n - 1 ? src[i + 1] : 0;
 588         a2 = i < n - 2 ? src[i + 2] : 0;
 589         dst[j++] = b[(a0 >> 2) & 0x3F];
 590         dst[j++] = b[((a0 << 4) & 0x30) | ((a1 >> 4) & 0x0F)];
 591         if(i < n - 1)
 592             dst[j++] = b[((a1 << 2) & 0x3C) | ((a2 >> 6) & 0x03)];
 593         else
 594             dst[j++] = '=';
 595         if(i < n - 2)
 596             dst[j++] = b[a2 & 0x3F];
 597         else
 598             dst[j++] = '=';
 599     }
 600     return j;
 601 }
 602
 603 int
 604 b64cmp(const char *restrict a, int an, const char *restrict b, int bn)
 605 {
 606     char *buf;
 607     int r;
 608
 609     if(an % 4 != 0)
 610         return -1;
 611     if((bn + 2) / 3 != an / 4)
 612         return -1;
 613     buf = malloc(an);
 614     if(buf == NULL)
 615         return -1;
 616     b64cpy(buf, b, bn, 0);
 617     r = memcmp(buf, a, an);
 618     free(buf);
 619     return r;
 620 }
 621
 622 IntListPtr
 623 makeIntList(int size)
 624 {
 625     IntListPtr list;
 626     if(size <= 0)
 627         size = 4;
 628
 629     list = malloc(sizeof(IntListRec));
 630     if(list == NULL)
 631         return NULL;
 632
 633     list->ranges = malloc(size * sizeof(IntRangeRec));
 634     if(list->ranges == NULL) {
 635         free(list);
 636         return NULL;
 637     }
 638
 639     list->length = 0;
 640     list->size = size;
 641     return list;
 642 }
 643
 644 void
 645 destroyIntList(IntListPtr list)
 646 {
 647     free(list->ranges);
 648     free(list);
 649 }
 650
 651 int
 652 intListMember(int n, IntListPtr list)
 653 {
 654     int lo = 0, hi = list->length - 1;
 655     int mid;
 656     while(hi >= lo) {
 657         mid = (hi + lo) / 2;
 658         if(list->ranges[mid].from > n)
 659             hi = mid - 1;
 660         else if(list->ranges[mid].to < n)
 661             lo = mid + 1;
 662         else
 663             return 1;
 664     }
 665     return 0;
 666 }
 667
 668 static int
 669 deleteRange(IntListPtr list, int i)
 670 {
 671     assert(list->length > i);
 672     if(list->length > i + 1)
 673         memmove(list->ranges + i, list->ranges + i + 1,
 674                 (list->length - i - 1) * sizeof(IntRangeRec));
 675     list->length--;
 676     return 1;
 677 }
 678
 679 static int
 680 insertRange(int from, int to, IntListPtr list, int i)
 681 {
 682     assert(i >= 0 && i <= list->length);
 683     assert(i == 0 || list->ranges[i - 1].to < from - 1);
 684     assert(i == list->length || list->ranges[i].from > to + 1);
 685
 686     if(list->length >= list->size) {
 687         int newsize = list->size * 2 + 1;
 688         IntRangePtr newranges =
 689             realloc(list->ranges, newsize * sizeof(IntRangeRec));
 690         if(newranges == NULL)
 691             return -1;
 692         list->size = newsize;
 693         list->ranges = newranges;
 694     }
 695
 696     if(i < list->length)
 697         memmove(list->ranges + i + 1, list->ranges + i,
 698                 list->length - i);
 699     list->length++;
 700     list->ranges[i].from = from;
 701     list->ranges[i].to = to;
 702     return 1;
 703 }
 704
 705 static int
 706 maybeMergeRanges(IntListPtr list, int i)
 707 {
 708     int rc;
 709
 710     while(i > 0 && list->ranges[i].from <= list->ranges[i - 1].to + 1) {
 711             list->ranges[i - 1].from =
 712                 MIN(list->ranges[i - 1].from, list->ranges[i].from);
 713             list->ranges[i - 1].to =
 714                 MAX(list->ranges[i - 1].to, list->ranges[i].to);
 715             rc = deleteRange(list, i);
 716             if(rc < 0) return -1;
 717             i--;
 718     }
 719
 720     while(i < list->length - 1 &&
 721           list->ranges[i].to >= list->ranges[i + 1].from - 1) {
 722             list->ranges[i + 1].from =
 723                 MIN(list->ranges[i + 1].from, list->ranges[i].from);
 724             list->ranges[i - 1].to =
 725                 MAX(list->ranges[i + 1].to, list->ranges[i].to);
 726             rc = deleteRange(list, i);
 727             if(rc < 0) return -1;
 728     }
 729     return 1;
 730 }
 731
 732 int
 733 intListCons(int from, int to, IntListPtr list)
 734 {
 735     int i;
 736
 737     /* Don't bother with the dichotomy. */
 738     for(i = 0; i < list->length; i++) {
 739         if(list->ranges[i].to >= from - 1)
 740             break;
 741     }
 742
 743     if(i < list->length &&
 744        (from >= list->ranges[i].from - 1 || to <= list->ranges[i].to + 1)) {
 745         if(from <= list->ranges[i].from)
 746             list->ranges[i].from = from;
 747         if(to >= list->ranges[i].to)
 748             list->ranges[i].to = to;
 749         return maybeMergeRanges(list, i);
 750     }
 751     return insertRange(from, to, list, i);
 752 }