release/src/router/nginx/src/core/ngx_string.c

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