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