src/core/ngx_string.c

   1
   2 /*
   3  * Copyright (C) Igor Sysoev
   4  */
   5
   6
   7 #include <ngx_config.h>
   8 #include <ngx_core.h>
   9
  10
  11 void
  12 ngx_strlow(u_char *dst, u_char *src, size_t n)
  13 {
  14     while (n--) {
  15         *dst = ngx_tolower(*src);
  16         dst++;
  17         src++;
  18     }
  19 }
  20
  21
  22 u_char *
  23 ngx_cpystrn(u_char *dst, u_char *src, size_t n)
  24 {
  25     if (n == 0) {
  26         return dst;
  27     }
  28
  29     for ( /* void */ ; --n; dst++, src++) {
  30         *dst = *src;
  31
  32         if (*dst == '\0') {
  33             return dst;
  34         }
  35     }
  36
  37     *dst = '\0';
  38
  39     return dst;
  40 }
  41
  42
  43 u_char *
  44 ngx_pstrdup(ngx_pool_t *pool, ngx_str_t *src)
  45 {
  46     u_char  *dst;
  47
  48     dst = ngx_pnalloc(pool, src->len);
  49     if (dst == NULL) {
  50         return NULL;
  51     }
  52
  53     ngx_memcpy(dst, src->data, src->len);
  54
  55     return dst;
  56 }
  57
  58
  59 /*
  60  * supported formats:
  61  *    %[0][width][x][X]O        off_t
  62  *    %[0][width]T              time_t
  63  *    %[0][width][u][x|X]z      ssize_t/size_t
  64  *    %[0][width][u][x|X]d      int/u_int
  65  *    %[0][width][u][x|X]l      long
  66  *    %[0][width|m][u][x|X]i    ngx_int_t/ngx_uint_t
  67  *    %[0][width][u][x|X]D      int32_t/uint32_t
  68  *    %[0][width][u][x|X]L      int64_t/uint64_t
  69  *    %[0][width|m][u][x|X]A    ngx_atomic_int_t/ngx_atomic_uint_t
  70  *    %P                        ngx_pid_t
  71  *    %M                        ngx_msec_t
  72  *    %r                        rlim_t
  73  *    %p                        void *
  74  *    %V                        ngx_str_t *
  75  *    %v                        ngx_variable_value_t *
  76  *    %s                        null-terminated string
  77  *    %*s                       length and string
  78  *    %Z                        '\0'
  79  *    %N                        '\n'
  80  *    %c                        char
  81  *    %%                        %
  82  *
  83  *  reserved:
  84  *    %t                        ptrdiff_t
  85  *    %S                        null-teminated wchar string
  86  *    %C                        wchar
  87  */
  88
  89
  90 u_char * ngx_cdecl
  91 ngx_sprintf(u_char *buf, const char *fmt, ...)
  92 {
  93     u_char   *p;
  94     va_list   args;
  95
  96     va_start(args, fmt);
  97     p = ngx_vsnprintf(buf, /* STUB */ 65536, fmt, args);
  98     va_end(args);
  99
 100     return p;
 101 }
 102
 103
 104 u_char * ngx_cdecl
 105 ngx_snprintf(u_char *buf, size_t max, const char *fmt, ...)
 106 {
 107     u_char   *p;
 108     va_list   args;
 109
 110     va_start(args, fmt);
 111     p = ngx_vsnprintf(buf, max, fmt, args);
 112     va_end(args);
 113
 114     return p;
 115 }
 116
 117
 118 u_char *
 119 ngx_vsnprintf(u_char *buf, size_t max, const char *fmt, va_list args)
 120 {
 121     u_char                *p, zero, *last, temp[NGX_INT64_LEN + 1];
 122                                     /*
 123                                      * really we need temp[NGX_INT64_LEN] only,
 124                                      * but icc issues the warning
 125                                      */
 126     int                    d;
 127     size_t                 len, slen;
 128     uint32_t               ui32;
 129     int64_t                i64;
 130     uint64_t               ui64;
 131     ngx_msec_t             ms;
 132     ngx_uint_t             width, sign, hexadecimal, max_width;
 133     ngx_str_t             *v;
 134     ngx_variable_value_t  *vv;
 135     static u_char          hex[] = "0123456789abcdef";
 136     static u_char          HEX[] = "0123456789ABCDEF";
 137
 138     if (max == 0) {
 139         return buf;
 140     }
 141
 142     last = buf + max;
 143
 144     while (*fmt && buf < last) {
 145
 146         /*
 147          * "buf < last" means that we could copy at least one character:
 148          * the plain character, "%%", "%c", and minus without the checking
 149          */
 150
 151         if (*fmt == '%') {
 152
 153             i64 = 0;
 154             ui64 = 0;
 155
 156             zero = (u_char) ((*++fmt == '0') ? '0' : ' ');
 157             width = 0;
 158             sign = 1;
 159             hexadecimal = 0;
 160             max_width = 0;
 161             slen = (size_t) -1;
 162
 163             p = temp + NGX_INT64_LEN;
 164
 165             while (*fmt >= '0' && *fmt <= '9') {
 166                 width = width * 10 + *fmt++ - '0';
 167             }
 168
 169
 170             for ( ;; ) {
 171                 switch (*fmt) {
 172
 173                 case 'u':
 174                     sign = 0;
 175                     fmt++;
 176                     continue;
 177
 178                 case 'm':
 179                     max_width = 1;
 180                     fmt++;
 181                     continue;
 182
 183                 case 'X':
 184                     hexadecimal = 2;
 185                     sign = 0;
 186                     fmt++;
 187                     continue;
 188
 189                 case 'x':
 190                     hexadecimal = 1;
 191                     sign = 0;
 192                     fmt++;
 193                     continue;
 194
 195                 case '*':
 196                     slen = va_arg(args, size_t);
 197                     fmt++;
 198                     continue;
 199
 200                 default:
 201                     break;
 202                 }
 203
 204                 break;
 205             }
 206
 207
 208             switch (*fmt) {
 209
 210             case 'V':
 211                 v = va_arg(args, ngx_str_t *);
 212
 213                 len = v->len;
 214                 len = (buf + len < last) ? len : (size_t) (last - buf);
 215
 216                 buf = ngx_cpymem(buf, v->data, len);
 217                 fmt++;
 218
 219                 continue;
 220
 221             case 'v':
 222                 vv = va_arg(args, ngx_variable_value_t *);
 223
 224                 len = vv->len;
 225                 len = (buf + len < last) ? len : (size_t) (last - buf);
 226
 227                 buf = ngx_cpymem(buf, vv->data, len);
 228                 fmt++;
 229
 230                 continue;
 231
 232             case 's':
 233                 p = va_arg(args, u_char *);
 234
 235                 if (slen == (size_t) -1) {
 236                     while (*p && buf < last) {
 237                         *buf++ = *p++;
 238                     }
 239
 240                 } else {
 241                     len = (buf + slen < last) ? slen : (size_t) (last - buf);
 242
 243                     buf = ngx_cpymem(buf, p, len);
 244                 }
 245
 246                 fmt++;
 247
 248                 continue;
 249
 250             case 'O':
 251                 i64 = (int64_t) va_arg(args, off_t);
 252                 sign = 1;
 253                 break;
 254
 255             case 'P':
 256                 i64 = (int64_t) va_arg(args, ngx_pid_t);
 257                 sign = 1;
 258                 break;
 259
 260             case 'T':
 261                 i64 = (int64_t) va_arg(args, time_t);
 262                 sign = 1;
 263                 break;
 264
 265             case 'M':
 266                 ms = (ngx_msec_t) va_arg(args, ngx_msec_t);
 267                 if ((ngx_msec_int_t) ms == -1) {
 268                     sign = 1;
 269                     i64 = -1;
 270                 } else {
 271                     sign = 0;
 272                     ui64 = (uint64_t) ms;
 273                 }
 274                 break;
 275
 276             case 'z':
 277                 if (sign) {
 278                     i64 = (int64_t) va_arg(args, ssize_t);
 279                 } else {
 280                     ui64 = (uint64_t) va_arg(args, size_t);
 281                 }
 282                 break;
 283
 284             case 'i':
 285                 if (sign) {
 286                     i64 = (int64_t) va_arg(args, ngx_int_t);
 287                 } else {
 288                     ui64 = (uint64_t) va_arg(args, ngx_uint_t);
 289                 }
 290
 291                 if (max_width) {
 292                     width = NGX_INT_T_LEN;
 293                 }
 294
 295                 break;
 296
 297             case 'd':
 298                 if (sign) {
 299                     i64 = (int64_t) va_arg(args, int);
 300                 } else {
 301                     ui64 = (uint64_t) va_arg(args, u_int);
 302                 }
 303                 break;
 304
 305             case 'l':
 306                 if (sign) {
 307                     i64 = (int64_t) va_arg(args, long);
 308                 } else {
 309                     ui64 = (uint64_t) va_arg(args, u_long);
 310                 }
 311                 break;
 312
 313             case 'D':
 314                 if (sign) {
 315                     i64 = (int64_t) va_arg(args, int32_t);
 316                 } else {
 317                     ui64 = (uint64_t) va_arg(args, uint32_t);
 318                 }
 319                 break;
 320
 321             case 'L':
 322                 if (sign) {
 323                     i64 = va_arg(args, int64_t);
 324                 } else {
 325                     ui64 = va_arg(args, uint64_t);
 326                 }
 327                 break;
 328
 329             case 'A':
 330                 if (sign) {
 331                     i64 = (int64_t) va_arg(args, ngx_atomic_int_t);
 332                 } else {
 333                     ui64 = (uint64_t) va_arg(args, ngx_atomic_uint_t);
 334                 }
 335
 336                 if (max_width) {
 337                     width = NGX_ATOMIC_T_LEN;
 338                 }
 339
 340                 break;
 341
 342 #if !(NGX_WIN32)
 343             case 'r':
 344                 i64 = (int64_t) va_arg(args, rlim_t);
 345                 sign = 1;
 346                 break;
 347 #endif
 348
 349             case 'p':
 350                 ui64 = (uintptr_t) va_arg(args, void *);
 351                 hexadecimal = 2;
 352                 sign = 0;
 353                 zero = '0';
 354                 width = NGX_PTR_SIZE * 2;
 355                 break;
 356
 357             case 'c':
 358                 d = va_arg(args, int);
 359                 *buf++ = (u_char) (d & 0xff);
 360                 fmt++;
 361
 362                 continue;
 363
 364             case 'Z':
 365                 *buf++ = '\0';
 366                 fmt++;
 367
 368                 continue;
 369
 370             case 'N':
 371 #if (NGX_WIN32)
 372                 *buf++ = CR;
 373 #endif
 374                 *buf++ = LF;
 375                 fmt++;
 376
 377                 continue;
 378
 379             case '%':
 380                 *buf++ = '%';
 381                 fmt++;
 382
 383                 continue;
 384
 385             default:
 386                 *buf++ = *fmt++;
 387
 388                 continue;
 389             }
 390
 391             if (sign) {
 392                 if (i64 < 0) {
 393                     *buf++ = '-';
 394                     ui64 = (uint64_t) -i64;
 395
 396                 } else {
 397                     ui64 = (uint64_t) i64;
 398                 }
 399             }
 400
 401             if (hexadecimal == 1) {
 402                 do {
 403
 404                     /* the "(uint32_t)" cast disables the BCC's warning */
 405                     *--p = hex[(uint32_t) (ui64 & 0xf)];
 406
 407                 } while (ui64 >>= 4);
 408
 409             } else if (hexadecimal == 2) {
 410                 do {
 411
 412                     /* the "(uint32_t)" cast disables the BCC's warning */
 413                     *--p = HEX[(uint32_t) (ui64 & 0xf)];
 414
 415                 } while (ui64 >>= 4);
 416
 417             } else if (ui64 <= NGX_MAX_UINT32_VALUE) {
 418
 419                 /*
 420                  * To divide 64-bit number and to find the remainder
 421                  * on the x86 platform gcc and icc call the libc functions
 422                  * [u]divdi3() and [u]moddi3(), they call another function
 423                  * in its turn.  On FreeBSD it is the qdivrem() function,
 424                  * its source code is about 170 lines of the code.
 425                  * The glibc counterpart is about 150 lines of the code.
 426                  *
 427                  * For 32-bit numbers and some divisors gcc and icc use
 428                  * the inlined multiplication and shifts.  For example,
 429                  * unsigned "i32 / 10" is compiled to
 430                  *
 431                  *     (i32 * 0xCCCCCCCD) >> 35
 432                  */
 433
 434                 ui32 = (uint32_t) ui64;
 435
 436                 do {
 437                     *--p = (u_char) (ui32 % 10 + '0');
 438                 } while (ui32 /= 10);
 439
 440             } else {
 441                 do {
 442                     *--p = (u_char) (ui64 % 10 + '0');
 443                 } while (ui64 /= 10);
 444             }
 445
 446             len = (temp + NGX_INT64_LEN) - p;
 447
 448             while (len++ < width && buf < last) {
 449                 *buf++ = zero;
 450             }
 451
 452             len = (temp + NGX_INT64_LEN) - p;
 453             if (buf + len > last) {
 454                 len = last - buf;
 455             }
 456
 457             buf = ngx_cpymem(buf, p, len);
 458
 459             fmt++;
 460
 461         } else {
 462             *buf++ = *fmt++;
 463         }
 464     }
 465
 466     return buf;
 467 }
 468
 469
 470 /*
 471  * We use ngx_strcasecmp()/ngx_strncasecmp() for 7-bit ASCII strings only,
 472  * and implement our own ngx_strcasecmp()/ngx_strncasecmp()
 473  * to avoid libc locale overhead.  Besides, we use the ngx_uint_t's
 474  * instead of the u_char's, because they are slightly faster.
 475  */
 476
 477 ngx_int_t
 478 ngx_strcasecmp(u_char *s1, u_char *s2)
 479 {
 480     ngx_uint_t  c1, c2;
 481
 482     for ( ;; ) {
 483         c1 = (ngx_uint_t) *s1++;
 484         c2 = (ngx_uint_t) *s2++;
 485
 486         c1  = (c1 >= 'A' && c1 <= 'Z') ? (c1 | 0x20) : c1;
 487         c2  = (c2 >= 'A' && c2 <= 'Z') ? (c2 | 0x20) : c2;
 488
 489         if (c1 == c2) {
 490
 491             if (c1) {
 492                 continue;
 493             }
 494
 495             return 0;
 496         }
 497
 498         return c1 - c2;
 499     }
 500 }
 501
 502
 503 ngx_int_t
 504 ngx_strncasecmp(u_char *s1, u_char *s2, size_t n)
 505 {
 506     ngx_uint_t  c1, c2;
 507
 508     while (n) {
 509         c1 = (ngx_uint_t) *s1++;
 510         c2 = (ngx_uint_t) *s2++;
 511
 512         c1  = (c1 >= 'A' && c1 <= 'Z') ? (c1 | 0x20) : c1;
 513         c2  = (c2 >= 'A' && c2 <= 'Z') ? (c2 | 0x20) : c2;
 514
 515         if (c1 == c2) {
 516
 517             if (c1) {
 518                 n--;
 519                 continue;
 520             }
 521
 522             return 0;
 523         }
 524
 525         return c1 - c2;
 526     }
 527
 528     return 0;
 529 }
 530
 531
 532 u_char *
 533 ngx_strnstr(u_char *s1, char *s2, size_t len)
 534 {
 535     u_char  c1, c2;
 536     size_t  n;
 537
 538     c2 = *(u_char *) s2++;
 539
 540     n = ngx_strlen(s2);
 541
 542     do {
 543         do {
 544             if (len-- == 0) {
 545                 return NULL;
 546             }
 547
 548             c1 = *s1++;
 549
 550             if (c1 == 0) {
 551                 return NULL;
 552             }
 553
 554         } while (c1 != c2);
 555
 556         if (n > len) {
 557             return NULL;
 558         }
 559
 560     } while (ngx_strncmp(s1, (u_char *) s2, n) != 0);
 561
 562     return --s1;
 563 }
 564
 565
 566 /*
 567  * ngx_strstrn() and ngx_strcasestrn() are intended to search for static
 568  * substring with known length in null-terminated string. The argument n
 569  * must be length of the second substring - 1.
 570  */
 571
 572 u_char *
 573 ngx_strstrn(u_char *s1, char *s2, size_t n)
 574 {
 575     u_char  c1, c2;
 576
 577     c2 = *(u_char *) s2++;
 578
 579     do {
 580         do {
 581             c1 = *s1++;
 582
 583             if (c1 == 0) {
 584                 return NULL;
 585             }
 586
 587         } while (c1 != c2);
 588
 589     } while (ngx_strncmp(s1, (u_char *) s2, n) != 0);
 590
 591     return --s1;
 592 }
 593
 594
 595 u_char *
 596 ngx_strcasestrn(u_char *s1, char *s2, size_t n)
 597 {
 598     ngx_uint_t  c1, c2;
 599
 600     c2 = (ngx_uint_t) *s2++;
 601     c2  = (c2 >= 'A' && c2 <= 'Z') ? (c2 | 0x20) : c2;
 602
 603     do {
 604         do {
 605             c1 = (ngx_uint_t) *s1++;
 606
 607             if (c1 == 0) {
 608                 return NULL;
 609             }
 610
 611             c1  = (c1 >= 'A' && c1 <= 'Z') ? (c1 | 0x20) : c1;
 612
 613         } while (c1 != c2);
 614
 615     } while (ngx_strncasecmp(s1, (u_char *) s2, n) != 0);
 616
 617     return --s1;
 618 }
 619
 620
 621 ngx_int_t
 622 ngx_rstrncmp(u_char *s1, u_char *s2, size_t n)
 623 {
 624     if (n == 0) {
 625         return 0;
 626     }
 627
 628     n--;
 629
 630     for ( ;; ) {
 631         if (s1[n] != s2[n]) {
 632             return s1[n] - s2[n];
 633         }
 634
 635         if (n == 0) {
 636             return 0;
 637         }
 638
 639         n--;
 640     }
 641 }
 642
 643
 644 ngx_int_t
 645 ngx_rstrncasecmp(u_char *s1, u_char *s2, size_t n)
 646 {
 647     u_char  c1, c2;
 648
 649     if (n == 0) {
 650         return 0;
 651     }
 652
 653     n--;
 654
 655     for ( ;; ) {
 656         c1 = s1[n];
 657         if (c1 >= 'a' && c1 <= 'z') {
 658             c1 -= 'a' - 'A';
 659         }
 660
 661         c2 = s2[n];
 662         if (c2 >= 'a' && c2 <= 'z') {
 663             c2 -= 'a' - 'A';
 664         }
 665
 666         if (c1 != c2) {
 667             return c1 - c2;
 668         }
 669
 670         if (n == 0) {
 671             return 0;
 672         }
 673
 674         n--;
 675     }
 676 }
 677
 678
 679 ngx_int_t
 680 ngx_memn2cmp(u_char *s1, u_char *s2, size_t n1, size_t n2)
 681 {
 682     size_t     n;
 683     ngx_int_t  m, z;
 684
 685     if (n1 <= n2) {
 686         n = n1;
 687         z = -1;
 688
 689     } else {
 690         n = n2;
 691         z = 1;
 692     }
 693
 694     m = ngx_memcmp(s1, s2, n);
 695
 696     if (m || n1 == n2) {
 697         return m;
 698     }
 699
 700     return z;
 701 }
 702
 703
 704 ngx_int_t
 705 ngx_atoi(u_char *line, size_t n)
 706 {
 707     ngx_int_t  value;
 708
 709     if (n == 0) {
 710         return NGX_ERROR;
 711     }
 712
 713     for (value = 0; n--; line++) {
 714         if (*line < '0' || *line > '9') {
 715             return NGX_ERROR;
 716         }
 717
 718         value = value * 10 + (*line - '0');
 719     }
 720
 721     if (value < 0) {
 722         return NGX_ERROR;
 723
 724     } else {
 725         return value;
 726     }
 727 }
 728
 729
 730 ssize_t
 731 ngx_atosz(u_char *line, size_t n)
 732 {
 733     ssize_t  value;
 734
 735     if (n == 0) {
 736         return NGX_ERROR;
 737     }
 738
 739     for (value = 0; n--; line++) {
 740         if (*line < '0' || *line > '9') {
 741             return NGX_ERROR;
 742         }
 743
 744         value = value * 10 + (*line - '0');
 745     }
 746
 747     if (value < 0) {
 748         return NGX_ERROR;
 749
 750     } else {
 751         return value;
 752     }
 753 }
 754
 755
 756 off_t
 757 ngx_atoof(u_char *line, size_t n)
 758 {
 759     off_t  value;
 760
 761     if (n == 0) {
 762         return NGX_ERROR;
 763     }
 764
 765     for (value = 0; n--; line++) {
 766         if (*line < '0' || *line > '9') {
 767             return NGX_ERROR;
 768         }
 769
 770         value = value * 10 + (*line - '0');
 771     }
 772
 773     if (value < 0) {
 774         return NGX_ERROR;
 775
 776     } else {
 777         return value;
 778     }
 779 }
 780
 781
 782 time_t
 783 ngx_atotm(u_char *line, size_t n)
 784 {
 785     time_t  value;
 786
 787     if (n == 0) {
 788         return NGX_ERROR;
 789     }
 790
 791     for (value = 0; n--; line++) {
 792         if (*line < '0' || *line > '9') {
 793             return NGX_ERROR;
 794         }
 795
 796         value = value * 10 + (*line - '0');
 797     }
 798
 799     if (value < 0) {
 800         return NGX_ERROR;
 801
 802     } else {
 803         return value;
 804     }
 805 }
 806
 807
 808 ngx_int_t
 809 ngx_hextoi(u_char *line, size_t n)
 810 {
 811     u_char     c, ch;
 812     ngx_int_t  value;
 813
 814     if (n == 0) {
 815         return NGX_ERROR;
 816     }
 817
 818     for (value = 0; n--; line++) {
 819         ch = *line;
 820
 821         if (ch >= '0' && ch <= '9') {
 822             value = value * 16 + (ch - '0');
 823             continue;
 824         }
 825
 826         c = (u_char) (ch | 0x20);
 827
 828         if (c >= 'a' && c <= 'f') {
 829             value = value * 16 + (c - 'a' + 10);
 830             continue;
 831         }
 832
 833         return NGX_ERROR;
 834     }
 835
 836     if (value < 0) {
 837         return NGX_ERROR;
 838
 839     } else {
 840         return value;
 841     }
 842 }
 843
 844
 845 u_char *
 846 ngx_hex_dump(u_char *dst, u_char *src, size_t len)
 847 {
 848     static u_char  hex[] = "0123456789abcdef";
 849
 850     while (len--) {
 851         *dst++ = hex[*src >> 4];
 852         *dst++ = hex[*src++ & 0xf];
 853     }
 854
 855     return dst;
 856 }
 857
 858
 859 void
 860 ngx_encode_base64(ngx_str_t *dst, ngx_str_t *src)
 861 {
 862     u_char         *d, *s;
 863     size_t          len;
 864     static u_char   basis64[] =
 865             "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
 866
 867     len = src->len;
 868     s = src->data;
 869     d = dst->data;
 870
 871     while (len > 2) {
 872         *d++ = basis64[(s[0] >> 2) & 0x3f];
 873         *d++ = basis64[((s[0] & 3) << 4) | (s[1] >> 4)];
 874         *d++ = basis64[((s[1] & 0x0f) << 2) | (s[2] >> 6)];
 875         *d++ = basis64[s[2] & 0x3f];
 876
 877         s += 3;
 878         len -= 3;
 879     }
 880
 881     if (len) {
 882         *d++ = basis64[(s[0] >> 2) & 0x3f];
 883
 884         if (len == 1) {
 885             *d++ = basis64[(s[0] & 3) << 4];
 886             *d++ = '=';
 887
 888         } else {
 889             *d++ = basis64[((s[0] & 3) << 4) | (s[1] >> 4)];
 890             *d++ = basis64[(s[1] & 0x0f) << 2];
 891         }
 892
 893         *d++ = '=';
 894     }
 895
 896     dst->len = d - dst->data;
 897 }
 898
 899
 900 ngx_int_t
 901 ngx_decode_base64(ngx_str_t *dst, ngx_str_t *src)
 902 {
 903     size_t          len;
 904     u_char         *d, *s;
 905     static u_char   basis64[] = {
 906         77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
 907         77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
 908         77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 62, 77, 77, 77, 63,
 909         52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 77, 77, 77, 77, 77, 77,
 910         77,  0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14,
 911         15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 77, 77, 77, 77, 77,
 912         77, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
 913         41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 77, 77, 77, 77, 77,
 914
 915         77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
 916         77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
 917         77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
 918         77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
 919         77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
 920         77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
 921         77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
 922         77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77
 923     };
 924
 925     for (len = 0; len < src->len; len++) {
 926         if (src->data[len] == '=') {
 927             break;
 928         }
 929
 930         if (basis64[src->data[len]] == 77) {
 931             return NGX_ERROR;
 932         }
 933     }
 934
 935     if (len % 4 == 1) {
 936         return NGX_ERROR;
 937     }
 938
 939     s = src->data;
 940     d = dst->data;
 941
 942     while (len > 3) {
 943         *d++ = (u_char) (basis64[s[0]] << 2 | basis64[s[1]] >> 4);
 944         *d++ = (u_char) (basis64[s[1]] << 4 | basis64[s[2]] >> 2);
 945         *d++ = (u_char) (basis64[s[2]] << 6 | basis64[s[3]]);
 946
 947         s += 4;
 948         len -= 4;
 949     }
 950
 951     if (len > 1) {
 952         *d++ = (u_char) (basis64[s[0]] << 2 | basis64[s[1]] >> 4);
 953     }
 954
 955     if (len > 2) {
 956         *d++ = (u_char) (basis64[s[1]] << 4 | basis64[s[2]] >> 2);
 957     }
 958
 959     dst->len = d - dst->data;
 960
 961     return NGX_OK;
 962 }
 963
 964
 965 /*
 966  * ngx_utf8_decode() decodes two and more bytes UTF sequences only
 967  * the return values:
 968  *    0x80 - 0x10ffff         valid character
 969  *    0x110000 - 0xfffffffd   invalid sequence
 970  *    0xfffffffe              incomplete sequence
 971  *    0xffffffff              error
 972  */
 973
 974 uint32_t
 975 ngx_utf8_decode(u_char **p, size_t n)
 976 {
 977     size_t    len;
 978     uint32_t  u, i, valid;
 979
 980     u = **p;
 981
 982     if (u > 0xf0) {
 983
 984         u &= 0x07;
 985         valid = 0xffff;
 986         len = 3;
 987
 988     } else if (u > 0xe0) {
 989
 990         u &= 0x0f;
 991         valid = 0x7ff;
 992         len = 2;
 993
 994     } else if (u > 0xc0) {
 995
 996         u &= 0x1f;
 997         valid = 0x7f;
 998         len = 1;
 999
1000     } else {
1001         (*p)++;
1002         return 0xffffffff;
1003     }
1004
1005     if (n - 1 < len) {
1006         return 0xfffffffe;
1007     }
1008
1009     (*p)++;
1010
1011     while (len) {
1012         i = *(*p)++;
1013
1014         if (i < 0x80) {
1015             return 0xffffffff;
1016         }
1017
1018         u = (u << 6) | (i & 0x3f);
1019
1020         len--;
1021     }
1022
1023     if (u > valid) {
1024         return u;
1025     }
1026
1027     return 0xffffffff;
1028 }
1029
1030
1031 size_t
1032 ngx_utf8_length(u_char *p, size_t n)
1033 {
1034     u_char  c, *last;
1035     size_t  len;
1036
1037     last = p + n;
1038
1039     for (len = 0; p < last; len++) {
1040
1041         c = *p;
1042
1043         if (c < 0x80) {
1044             p++;
1045             continue;
1046         }
1047
1048         if (ngx_utf8_decode(&p, n) > 0x10ffff) {
1049             /* invalid UTF-8 */
1050             return n;
1051         }
1052     }
1053
1054     return len;
1055 }
1056
1057
1058 u_char *
1059 ngx_utf8_cpystrn(u_char *dst, u_char *src, size_t n, size_t len)
1060 {
1061     u_char  c, *next;
1062
1063     if (n == 0) {
1064         return dst;
1065     }
1066
1067     while (--n) {
1068
1069         c = *src;
1070         *dst = c;
1071
1072         if (c < 0x80) {
1073
1074             if (c != '\0') {
1075                 dst++;
1076                 src++;
1077                 len--;
1078
1079                 continue;
1080             }
1081
1082             return dst;
1083         }
1084
1085         next = src;
1086
1087         if (ngx_utf8_decode(&next, len) > 0x10ffff) {
1088             /* invalid UTF-8 */
1089             break;
1090         }
1091
1092         len--;
1093
1094         while (src < next) {
1095             *++dst = *++src;
1096             len--;
1097         }
1098     }
1099
1100     *dst = '\0';
1101
1102     return dst;
1103 }
1104
1105
1106 uintptr_t
1107 ngx_escape_uri(u_char *dst, u_char *src, size_t size, ngx_uint_t type)
1108 {
1109     ngx_uint_t      i, n;
1110     uint32_t       *escape;
1111     static u_char   hex[] = "0123456789abcdef";
1112
1113                     /* " ", "#", "%", "?", %00-%1F, %7F-%FF */
1114
1115     static uint32_t   uri[] = {
1116         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1117
1118                     /* ?>=< ;:98 7654 3210  /.-, +*)( '&%$ #"!  */
1119         0x80000029, /* 1000 0000 0000 0000  0000 0000 0010 1001 */
1120
1121                     /* _^]\ [ZYX WVUT SRQP  ONML KJIH GFED CBA@ */
1122         0x00000000, /* 0000 0000 0000 0000  0000 0000 0000 0000 */
1123
1124                     /*  ~}| {zyx wvut srqp  onml kjih gfed cba` */
1125         0x80000000, /* 1000 0000 0000 0000  0000 0000 0000 0000 */
1126
1127         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1128         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1129         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1130         0xffffffff  /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1131     };
1132
1133                     /* " ", "#", "%", "+", "?", %00-%1F, %7F-%FF */
1134
1135     static uint32_t   args[] = {
1136         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1137
1138                     /* ?>=< ;:98 7654 3210  /.-, +*)( '&%$ #"!  */
1139         0x80000829, /* 1000 0000 0000 0000  0000 1000 0010 1001 */
1140
1141                     /* _^]\ [ZYX WVUT SRQP  ONML KJIH GFED CBA@ */
1142         0x00000000, /* 0000 0000 0000 0000  0000 0000 0000 0000 */
1143
1144                     /*  ~}| {zyx wvut srqp  onml kjih gfed cba` */
1145         0x80000000, /* 1000 0000 0000 0000  0000 0000 0000 0000 */
1146
1147         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1148         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1149         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1150         0xffffffff  /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1151     };
1152
1153                     /* " ", "#", """, "%", "'", %00-%1F, %7F-%FF */
1154
1155     static uint32_t   html[] = {
1156         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1157
1158                     /* ?>=< ;:98 7654 3210  /.-, +*)( '&%$ #"!  */
1159         0x000000ad, /* 0000 0000 0000 0000  0000 0000 1010 1101 */
1160
1161                     /* _^]\ [ZYX WVUT SRQP  ONML KJIH GFED CBA@ */
1162         0x00000000, /* 0000 0000 0000 0000  0000 0000 0000 0000 */
1163
1164                     /*  ~}| {zyx wvut srqp  onml kjih gfed cba` */
1165         0x80000000, /* 1000 0000 0000 0000  0000 0000 0000 0000 */
1166
1167         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1168         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1169         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1170         0xffffffff  /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1171     };
1172
1173                     /* " ", """, "%", "'", %00-%1F, %7F-%FF */
1174
1175     static uint32_t   refresh[] = {
1176         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1177
1178                     /* ?>=< ;:98 7654 3210  /.-, +*)( '&%$ #"!  */
1179         0x00000085, /* 0000 0000 0000 0000  0000 0000 1000 0101 */
1180
1181                     /* _^]\ [ZYX WVUT SRQP  ONML KJIH GFED CBA@ */
1182         0x00000000, /* 0000 0000 0000 0000  0000 0000 0000 0000 */
1183
1184                     /*  ~}| {zyx wvut srqp  onml kjih gfed cba` */
1185         0x80000000, /* 1000 0000 0000 0000  0000 0000 0000 0000 */
1186
1187         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1188         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1189         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1190         0xffffffff  /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1191     };
1192
1193                     /* " ", "%", %00-%1F */
1194
1195     static uint32_t   memcached[] = {
1196         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1197
1198                     /* ?>=< ;:98 7654 3210  /.-, +*)( '&%$ #"!  */
1199         0x00000021, /* 0000 0000 0000 0000  0000 0000 0010 0001 */
1200
1201                     /* _^]\ [ZYX WVUT SRQP  ONML KJIH GFED CBA@ */
1202         0x00000000, /* 0000 0000 0000 0000  0000 0000 0000 0000 */
1203
1204                     /*  ~}| {zyx wvut srqp  onml kjih gfed cba` */
1205         0x00000000, /* 0000 0000 0000 0000  0000 0000 0000 0000 */
1206
1207         0x00000000, /* 0000 0000 0000 0000  0000 0000 0000 0000 */
1208         0x00000000, /* 0000 0000 0000 0000  0000 0000 0000 0000 */
1209         0x00000000, /* 0000 0000 0000 0000  0000 0000 0000 0000 */
1210         0x00000000, /* 0000 0000 0000 0000  0000 0000 0000 0000 */
1211     };
1212
1213                     /* mail_auth is the same as memcached */
1214
1215     static uint32_t  *map[] =
1216         { uri, args, html, refresh, memcached, memcached };
1217
1218
1219     escape = map[type];
1220
1221     if (dst == NULL) {
1222
1223         /* find the number of the characters to be escaped */
1224
1225         n  = 0;
1226
1227         for (i = 0; i < size; i++) {
1228             if (escape[*src >> 5] & (1 << (*src & 0x1f))) {
1229                 n++;
1230             }
1231             src++;
1232         }
1233
1234         return (uintptr_t) n;
1235     }
1236
1237     for (i = 0; i < size; i++) {
1238         if (escape[*src >> 5] & (1 << (*src & 0x1f))) {
1239             *dst++ = '%';
1240             *dst++ = hex[*src >> 4];
1241             *dst++ = hex[*src & 0xf];
1242             src++;
1243
1244         } else {
1245             *dst++ = *src++;
1246         }
1247     }
1248
1249     return (uintptr_t) dst;
1250 }
1251
1252
1253 void
1254 ngx_unescape_uri(u_char **dst, u_char **src, size_t size, ngx_uint_t type)
1255 {
1256     u_char  *d, *s, ch, c, decoded;
1257     enum {
1258         sw_usual = 0,
1259         sw_quoted,
1260         sw_quoted_second
1261     } state;
1262
1263     d = *dst;
1264     s = *src;
1265
1266     state = 0;
1267     decoded = 0;
1268
1269     while (size--) {
1270
1271         ch = *s++;
1272
1273         switch (state) {
1274         case sw_usual:
1275             if (ch == '?'
1276                 && (type & (NGX_UNESCAPE_URI|NGX_UNESCAPE_REDIRECT)))
1277             {
1278                 *d++ = ch;
1279                 goto done;
1280             }
1281
1282             if (ch == '%') {
1283                 state = sw_quoted;
1284                 break;
1285             }
1286
1287             *d++ = ch;
1288             break;
1289
1290         case sw_quoted:
1291
1292             if (ch >= '0' && ch <= '9') {
1293                 decoded = (u_char) (ch - '0');
1294                 state = sw_quoted_second;
1295                 break;
1296             }
1297
1298             c = (u_char) (ch | 0x20);
1299             if (c >= 'a' && c <= 'f') {
1300                 decoded = (u_char) (c - 'a' + 10);
1301                 state = sw_quoted_second;
1302                 break;
1303             }
1304
1305             /* the invalid quoted character */
1306
1307             state = sw_usual;
1308
1309             *d++ = ch;
1310
1311             break;
1312
1313         case sw_quoted_second:
1314
1315             state = sw_usual;
1316
1317             if (ch >= '0' && ch <= '9') {
1318                 ch = (u_char) ((decoded << 4) + ch - '0');
1319
1320                 if (type & NGX_UNESCAPE_REDIRECT) {
1321                     if (ch > '%' && ch < 0x7f) {
1322                         *d++ = ch;
1323                         break;
1324                     }
1325
1326                     *d++ = '%'; *d++ = *(s - 2); *d++ = *(s - 1);
1327
1328                     break;
1329                 }
1330
1331                 *d++ = ch;
1332
1333                 break;
1334             }
1335
1336             c = (u_char) (ch | 0x20);
1337             if (c >= 'a' && c <= 'f') {
1338                 ch = (u_char) ((decoded << 4) + c - 'a' + 10);
1339
1340                 if (type & NGX_UNESCAPE_URI) {
1341                     if (ch == '?') {
1342                         *d++ = ch;
1343                         goto done;
1344                     }
1345
1346                     *d++ = ch;
1347                     break;
1348                 }
1349
1350                 if (type & NGX_UNESCAPE_REDIRECT) {
1351                     if (ch == '?') {
1352                         *d++ = ch;
1353                         goto done;
1354                     }
1355
1356                     if (ch > '%' && ch < 0x7f) {
1357                         *d++ = ch;
1358                         break;
1359                     }
1360
1361                     *d++ = '%'; *d++ = *(s - 2); *d++ = *(s - 1);
1362                     break;
1363                 }
1364
1365                 *d++ = ch;
1366
1367                 break;
1368             }
1369
1370             /* the invalid quoted character */
1371
1372             break;
1373         }
1374     }
1375
1376 done:
1377
1378     *dst = d;
1379     *src = s;
1380 }
1381
1382
1383 uintptr_t
1384 ngx_escape_html(u_char *dst, u_char *src, size_t size)
1385 {
1386     u_char      ch;
1387     ngx_uint_t  i, len;
1388
1389     if (dst == NULL) {
1390
1391         len = 0;
1392
1393         for (i = 0; i < size; i++) {
1394             switch (*src++) {
1395
1396             case '<':
1397                 len += sizeof("&lt;") - 2;
1398                 break;
1399
1400             case '>':
1401                 len += sizeof("&gt;") - 2;
1402                 break;
1403
1404             case '&':
1405                 len += sizeof("&amp;") - 2;
1406                 break;
1407
1408             default:
1409                 break;
1410             }
1411         }
1412
1413         return (uintptr_t) len;
1414     }
1415
1416     for (i = 0; i < size; i++) {
1417         ch = *src++;
1418
1419         switch (ch) {
1420
1421         case '<':
1422             *dst++ = '&'; *dst++ = 'l'; *dst++ = 't'; *dst++ = ';';
1423             break;
1424
1425         case '>':
1426             *dst++ = '&'; *dst++ = 'g'; *dst++ = 't'; *dst++ = ';';
1427             break;
1428
1429         case '&':
1430             *dst++ = '&'; *dst++ = 'a'; *dst++ = 'm'; *dst++ = 'p';
1431             *dst++ = ';';
1432             break;
1433
1434         default:
1435             *dst++ = ch;
1436             break;
1437         }
1438     }
1439
1440     return (uintptr_t) dst;
1441 }
1442
1443
1444 /* ngx_sort() is implemented as insertion sort because we need stable sort */
1445
1446 void
1447 ngx_sort(void *base, size_t n, size_t size,
1448     ngx_int_t (*cmp)(const void *, const void *))
1449 {
1450     u_char  *p1, *p2, *p;
1451
1452     p = ngx_alloc(size, ngx_cycle->log);
1453     if (p == NULL) {
1454         return;
1455     }
1456
1457     for (p1 = (u_char *) base + size;
1458          p1 < (u_char *) base + n * size;
1459          p1 += size)
1460     {
1461         ngx_memcpy(p, p1, size);
1462
1463         for (p2 = p1;
1464              p2 > (u_char *) base && cmp(p2 - size, p) > 0;
1465              p2 -= size)
1466         {
1467             ngx_memcpy(p2, p2 - size, size);
1468         }
1469
1470         ngx_memcpy(p2, p, size);
1471     }
1472
1473     ngx_free(p);
1474 }
1475
1476
1477 #if (NGX_MEMCPY_LIMIT)
1478
1479 void *
1480 ngx_memcpy(void *dst, void *src, size_t n)
1481 {
1482     if (n > NGX_MEMCPY_LIMIT) {
1483         ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "memcpy %uz bytes", n);
1484         ngx_debug_point();
1485     }
1486
1487     return memcpy(dst, src, n);
1488 }
1489
1490 #endif