Back to home page

Nginx displayed by LXR

Source navigation ]
Diff markup ]
Identifier search ]
general search ]
 
 
Version: nginx-1.15.11 ]​[ nginx-1.14.2 ]​

0001 
0002 /*
0003  * Copyright (C) Igor Sysoev
0004  * Copyright (C) Nginx, Inc.
0005  */
0006 
0007 
0008 #include <ngx_config.h>
0009 #include <ngx_core.h>
0010 
0011 
0012 static u_char *ngx_sprintf_num(u_char *buf, u_char *last, uint64_t ui64,
0013     u_char zero, ngx_uint_t hexadecimal, ngx_uint_t width);
0014 static void ngx_encode_base64_internal(ngx_str_t *dst, ngx_str_t *src,
0015     const u_char *basis, ngx_uint_t padding);
0016 static ngx_int_t ngx_decode_base64_internal(ngx_str_t *dst, ngx_str_t *src,
0017     const u_char *basis);
0018 
0019 
0020 void
0021 ngx_strlow(u_char *dst, u_char *src, size_t n)
0022 {
0023     while (n) {
0024         *dst = ngx_tolower(*src);
0025         dst++;
0026         src++;
0027         n--;
0028     }
0029 }
0030 
0031 
0032 size_t
0033 ngx_strnlen(u_char *p, size_t n)
0034 {
0035     size_t  i;
0036 
0037     for (i = 0; i < n; i++) {
0038 
0039         if (p[i] == '\0') {
0040             return i;
0041         }
0042     }
0043 
0044     return n;
0045 }
0046 
0047 
0048 u_char *
0049 ngx_cpystrn(u_char *dst, u_char *src, size_t n)
0050 {
0051     if (n == 0) {
0052         return dst;
0053     }
0054 
0055     while (--n) {
0056         *dst = *src;
0057 
0058         if (*dst == '\0') {
0059             return dst;
0060         }
0061 
0062         dst++;
0063         src++;
0064     }
0065 
0066     *dst = '\0';
0067 
0068     return dst;
0069 }
0070 
0071 
0072 u_char *
0073 ngx_pstrdup(ngx_pool_t *pool, ngx_str_t *src)
0074 {
0075     u_char  *dst;
0076 
0077     dst = ngx_pnalloc(pool, src->len);
0078     if (dst == NULL) {
0079         return NULL;
0080     }
0081 
0082     ngx_memcpy(dst, src->data, src->len);
0083 
0084     return dst;
0085 }
0086 
0087 
0088 /*
0089  * supported formats:
0090  *    %[0][width][x][X]O        off_t
0091  *    %[0][width]T              time_t
0092  *    %[0][width][u][x|X]z      ssize_t/size_t
0093  *    %[0][width][u][x|X]d      int/u_int
0094  *    %[0][width][u][x|X]l      long
0095  *    %[0][width|m][u][x|X]i    ngx_int_t/ngx_uint_t
0096  *    %[0][width][u][x|X]D      int32_t/uint32_t
0097  *    %[0][width][u][x|X]L      int64_t/uint64_t
0098  *    %[0][width|m][u][x|X]A    ngx_atomic_int_t/ngx_atomic_uint_t
0099  *    %[0][width][.width]f      double, max valid number fits to %18.15f
0100  *    %P                        ngx_pid_t
0101  *    %M                        ngx_msec_t
0102  *    %r                        rlim_t
0103  *    %p                        void *
0104  *    %V                        ngx_str_t *
0105  *    %v                        ngx_variable_value_t *
0106  *    %s                        null-terminated string
0107  *    %*s                       length and string
0108  *    %Z                        '\0'
0109  *    %N                        '\n'
0110  *    %c                        char
0111  *    %%                        %
0112  *
0113  *  reserved:
0114  *    %t                        ptrdiff_t
0115  *    %S                        null-terminated wchar string
0116  *    %C                        wchar
0117  */
0118 
0119 
0120 u_char * ngx_cdecl
0121 ngx_sprintf(u_char *buf, const char *fmt, ...)
0122 {
0123     u_char   *p;
0124     va_list   args;
0125 
0126     va_start(args, fmt);
0127     p = ngx_vslprintf(buf, (void *) -1, fmt, args);
0128     va_end(args);
0129 
0130     return p;
0131 }
0132 
0133 
0134 u_char * ngx_cdecl
0135 ngx_snprintf(u_char *buf, size_t max, const char *fmt, ...)
0136 {
0137     u_char   *p;
0138     va_list   args;
0139 
0140     va_start(args, fmt);
0141     p = ngx_vslprintf(buf, buf + max, fmt, args);
0142     va_end(args);
0143 
0144     return p;
0145 }
0146 
0147 
0148 u_char * ngx_cdecl
0149 ngx_slprintf(u_char *buf, u_char *last, const char *fmt, ...)
0150 {
0151     u_char   *p;
0152     va_list   args;
0153 
0154     va_start(args, fmt);
0155     p = ngx_vslprintf(buf, last, fmt, args);
0156     va_end(args);
0157 
0158     return p;
0159 }
0160 
0161 
0162 u_char *
0163 ngx_vslprintf(u_char *buf, u_char *last, const char *fmt, va_list args)
0164 {
0165     u_char                *p, zero;
0166     int                    d;
0167     double                 f;
0168     size_t                 len, slen;
0169     int64_t                i64;
0170     uint64_t               ui64, frac;
0171     ngx_msec_t             ms;
0172     ngx_uint_t             width, sign, hex, max_width, frac_width, scale, n;
0173     ngx_str_t             *v;
0174     ngx_variable_value_t  *vv;
0175 
0176     while (*fmt && buf < last) {
0177 
0178         /*
0179          * "buf < last" means that we could copy at least one character:
0180          * the plain character, "%%", "%c", and minus without the checking
0181          */
0182 
0183         if (*fmt == '%') {
0184 
0185             i64 = 0;
0186             ui64 = 0;
0187 
0188             zero = (u_char) ((*++fmt == '0') ? '0' : ' ');
0189             width = 0;
0190             sign = 1;
0191             hex = 0;
0192             max_width = 0;
0193             frac_width = 0;
0194             slen = (size_t) -1;
0195 
0196             while (*fmt >= '0' && *fmt <= '9') {
0197                 width = width * 10 + (*fmt++ - '0');
0198             }
0199 
0200 
0201             for ( ;; ) {
0202                 switch (*fmt) {
0203 
0204                 case 'u':
0205                     sign = 0;
0206                     fmt++;
0207                     continue;
0208 
0209                 case 'm':
0210                     max_width = 1;
0211                     fmt++;
0212                     continue;
0213 
0214                 case 'X':
0215                     hex = 2;
0216                     sign = 0;
0217                     fmt++;
0218                     continue;
0219 
0220                 case 'x':
0221                     hex = 1;
0222                     sign = 0;
0223                     fmt++;
0224                     continue;
0225 
0226                 case '.':
0227                     fmt++;
0228 
0229                     while (*fmt >= '0' && *fmt <= '9') {
0230                         frac_width = frac_width * 10 + (*fmt++ - '0');
0231                     }
0232 
0233                     break;
0234 
0235                 case '*':
0236                     slen = va_arg(args, size_t);
0237                     fmt++;
0238                     continue;
0239 
0240                 default:
0241                     break;
0242                 }
0243 
0244                 break;
0245             }
0246 
0247 
0248             switch (*fmt) {
0249 
0250             case 'V':
0251                 v = va_arg(args, ngx_str_t *);
0252 
0253                 len = ngx_min(((size_t) (last - buf)), v->len);
0254                 buf = ngx_cpymem(buf, v->data, len);
0255                 fmt++;
0256 
0257                 continue;
0258 
0259             case 'v':
0260                 vv = va_arg(args, ngx_variable_value_t *);
0261 
0262                 len = ngx_min(((size_t) (last - buf)), vv->len);
0263                 buf = ngx_cpymem(buf, vv->data, len);
0264                 fmt++;
0265 
0266                 continue;
0267 
0268             case 's':
0269                 p = va_arg(args, u_char *);
0270 
0271                 if (slen == (size_t) -1) {
0272                     while (*p && buf < last) {
0273                         *buf++ = *p++;
0274                     }
0275 
0276                 } else {
0277                     len = ngx_min(((size_t) (last - buf)), slen);
0278                     buf = ngx_cpymem(buf, p, len);
0279                 }
0280 
0281                 fmt++;
0282 
0283                 continue;
0284 
0285             case 'O':
0286                 i64 = (int64_t) va_arg(args, off_t);
0287                 sign = 1;
0288                 break;
0289 
0290             case 'P':
0291                 i64 = (int64_t) va_arg(args, ngx_pid_t);
0292                 sign = 1;
0293                 break;
0294 
0295             case 'T':
0296                 i64 = (int64_t) va_arg(args, time_t);
0297                 sign = 1;
0298                 break;
0299 
0300             case 'M':
0301                 ms = (ngx_msec_t) va_arg(args, ngx_msec_t);
0302                 if ((ngx_msec_int_t) ms == -1) {
0303                     sign = 1;
0304                     i64 = -1;
0305                 } else {
0306                     sign = 0;
0307                     ui64 = (uint64_t) ms;
0308                 }
0309                 break;
0310 
0311             case 'z':
0312                 if (sign) {
0313                     i64 = (int64_t) va_arg(args, ssize_t);
0314                 } else {
0315                     ui64 = (uint64_t) va_arg(args, size_t);
0316                 }
0317                 break;
0318 
0319             case 'i':
0320                 if (sign) {
0321                     i64 = (int64_t) va_arg(args, ngx_int_t);
0322                 } else {
0323                     ui64 = (uint64_t) va_arg(args, ngx_uint_t);
0324                 }
0325 
0326                 if (max_width) {
0327                     width = NGX_INT_T_LEN;
0328                 }
0329 
0330                 break;
0331 
0332             case 'd':
0333                 if (sign) {
0334                     i64 = (int64_t) va_arg(args, int);
0335                 } else {
0336                     ui64 = (uint64_t) va_arg(args, u_int);
0337                 }
0338                 break;
0339 
0340             case 'l':
0341                 if (sign) {
0342                     i64 = (int64_t) va_arg(args, long);
0343                 } else {
0344                     ui64 = (uint64_t) va_arg(args, u_long);
0345                 }
0346                 break;
0347 
0348             case 'D':
0349                 if (sign) {
0350                     i64 = (int64_t) va_arg(args, int32_t);
0351                 } else {
0352                     ui64 = (uint64_t) va_arg(args, uint32_t);
0353                 }
0354                 break;
0355 
0356             case 'L':
0357                 if (sign) {
0358                     i64 = va_arg(args, int64_t);
0359                 } else {
0360                     ui64 = va_arg(args, uint64_t);
0361                 }
0362                 break;
0363 
0364             case 'A':
0365                 if (sign) {
0366                     i64 = (int64_t) va_arg(args, ngx_atomic_int_t);
0367                 } else {
0368                     ui64 = (uint64_t) va_arg(args, ngx_atomic_uint_t);
0369                 }
0370 
0371                 if (max_width) {
0372                     width = NGX_ATOMIC_T_LEN;
0373                 }
0374 
0375                 break;
0376 
0377             case 'f':
0378                 f = va_arg(args, double);
0379 
0380                 if (f < 0) {
0381                     *buf++ = '-';
0382                     f = -f;
0383                 }
0384 
0385                 ui64 = (int64_t) f;
0386                 frac = 0;
0387 
0388                 if (frac_width) {
0389 
0390                     scale = 1;
0391                     for (n = frac_width; n; n--) {
0392                         scale *= 10;
0393                     }
0394 
0395                     frac = (uint64_t) ((f - (double) ui64) * scale + 0.5);
0396 
0397                     if (frac == scale) {
0398                         ui64++;
0399                         frac = 0;
0400                     }
0401                 }
0402 
0403                 buf = ngx_sprintf_num(buf, last, ui64, zero, 0, width);
0404 
0405                 if (frac_width) {
0406                     if (buf < last) {
0407                         *buf++ = '.';
0408                     }
0409 
0410                     buf = ngx_sprintf_num(buf, last, frac, '0', 0, frac_width);
0411                 }
0412 
0413                 fmt++;
0414 
0415                 continue;
0416 
0417 #if !(NGX_WIN32)
0418             case 'r':
0419                 i64 = (int64_t) va_arg(args, rlim_t);
0420                 sign = 1;
0421                 break;
0422 #endif
0423 
0424             case 'p':
0425                 ui64 = (uintptr_t) va_arg(args, void *);
0426                 hex = 2;
0427                 sign = 0;
0428                 zero = '0';
0429                 width = 2 * sizeof(void *);
0430                 break;
0431 
0432             case 'c':
0433                 d = va_arg(args, int);
0434                 *buf++ = (u_char) (d & 0xff);
0435                 fmt++;
0436 
0437                 continue;
0438 
0439             case 'Z':
0440                 *buf++ = '\0';
0441                 fmt++;
0442 
0443                 continue;
0444 
0445             case 'N':
0446 #if (NGX_WIN32)
0447                 *buf++ = CR;
0448                 if (buf < last) {
0449                     *buf++ = LF;
0450                 }
0451 #else
0452                 *buf++ = LF;
0453 #endif
0454                 fmt++;
0455 
0456                 continue;
0457 
0458             case '%':
0459                 *buf++ = '%';
0460                 fmt++;
0461 
0462                 continue;
0463 
0464             default:
0465                 *buf++ = *fmt++;
0466 
0467                 continue;
0468             }
0469 
0470             if (sign) {
0471                 if (i64 < 0) {
0472                     *buf++ = '-';
0473                     ui64 = (uint64_t) -i64;
0474 
0475                 } else {
0476                     ui64 = (uint64_t) i64;
0477                 }
0478             }
0479 
0480             buf = ngx_sprintf_num(buf, last, ui64, zero, hex, width);
0481 
0482             fmt++;
0483 
0484         } else {
0485             *buf++ = *fmt++;
0486         }
0487     }
0488 
0489     return buf;
0490 }
0491 
0492 
0493 static u_char *
0494 ngx_sprintf_num(u_char *buf, u_char *last, uint64_t ui64, u_char zero,
0495     ngx_uint_t hexadecimal, ngx_uint_t width)
0496 {
0497     u_char         *p, temp[NGX_INT64_LEN + 1];
0498                        /*
0499                         * we need temp[NGX_INT64_LEN] only,
0500                         * but icc issues the warning
0501                         */
0502     size_t          len;
0503     uint32_t        ui32;
0504     static u_char   hex[] = "0123456789abcdef";
0505     static u_char   HEX[] = "0123456789ABCDEF";
0506 
0507     p = temp + NGX_INT64_LEN;
0508 
0509     if (hexadecimal == 0) {
0510 
0511         if (ui64 <= (uint64_t) NGX_MAX_UINT32_VALUE) {
0512 
0513             /*
0514              * To divide 64-bit numbers and to find remainders
0515              * on the x86 platform gcc and icc call the libc functions
0516              * [u]divdi3() and [u]moddi3(), they call another function
0517              * in its turn.  On FreeBSD it is the qdivrem() function,
0518              * its source code is about 170 lines of the code.
0519              * The glibc counterpart is about 150 lines of the code.
0520              *
0521              * For 32-bit numbers and some divisors gcc and icc use
0522              * a inlined multiplication and shifts.  For example,
0523              * unsigned "i32 / 10" is compiled to
0524              *
0525              *     (i32 * 0xCCCCCCCD) >> 35
0526              */
0527 
0528             ui32 = (uint32_t) ui64;
0529 
0530             do {
0531                 *--p = (u_char) (ui32 % 10 + '0');
0532             } while (ui32 /= 10);
0533 
0534         } else {
0535             do {
0536                 *--p = (u_char) (ui64 % 10 + '0');
0537             } while (ui64 /= 10);
0538         }
0539 
0540     } else if (hexadecimal == 1) {
0541 
0542         do {
0543 
0544             /* the "(uint32_t)" cast disables the BCC's warning */
0545             *--p = hex[(uint32_t) (ui64 & 0xf)];
0546 
0547         } while (ui64 >>= 4);
0548 
0549     } else { /* hexadecimal == 2 */
0550 
0551         do {
0552 
0553             /* the "(uint32_t)" cast disables the BCC's warning */
0554             *--p = HEX[(uint32_t) (ui64 & 0xf)];
0555 
0556         } while (ui64 >>= 4);
0557     }
0558 
0559     /* zero or space padding */
0560 
0561     len = (temp + NGX_INT64_LEN) - p;
0562 
0563     while (len++ < width && buf < last) {
0564         *buf++ = zero;
0565     }
0566 
0567     /* number safe copy */
0568 
0569     len = (temp + NGX_INT64_LEN) - p;
0570 
0571     if (buf + len > last) {
0572         len = last - buf;
0573     }
0574 
0575     return ngx_cpymem(buf, p, len);
0576 }
0577 
0578 
0579 /*
0580  * We use ngx_strcasecmp()/ngx_strncasecmp() for 7-bit ASCII strings only,
0581  * and implement our own ngx_strcasecmp()/ngx_strncasecmp()
0582  * to avoid libc locale overhead.  Besides, we use the ngx_uint_t's
0583  * instead of the u_char's, because they are slightly faster.
0584  */
0585 
0586 ngx_int_t
0587 ngx_strcasecmp(u_char *s1, u_char *s2)
0588 {
0589     ngx_uint_t  c1, c2;
0590 
0591     for ( ;; ) {
0592         c1 = (ngx_uint_t) *s1++;
0593         c2 = (ngx_uint_t) *s2++;
0594 
0595         c1 = (c1 >= 'A' && c1 <= 'Z') ? (c1 | 0x20) : c1;
0596         c2 = (c2 >= 'A' && c2 <= 'Z') ? (c2 | 0x20) : c2;
0597 
0598         if (c1 == c2) {
0599 
0600             if (c1) {
0601                 continue;
0602             }
0603 
0604             return 0;
0605         }
0606 
0607         return c1 - c2;
0608     }
0609 }
0610 
0611 
0612 ngx_int_t
0613 ngx_strncasecmp(u_char *s1, u_char *s2, size_t n)
0614 {
0615     ngx_uint_t  c1, c2;
0616 
0617     while (n) {
0618         c1 = (ngx_uint_t) *s1++;
0619         c2 = (ngx_uint_t) *s2++;
0620 
0621         c1 = (c1 >= 'A' && c1 <= 'Z') ? (c1 | 0x20) : c1;
0622         c2 = (c2 >= 'A' && c2 <= 'Z') ? (c2 | 0x20) : c2;
0623 
0624         if (c1 == c2) {
0625 
0626             if (c1) {
0627                 n--;
0628                 continue;
0629             }
0630 
0631             return 0;
0632         }
0633 
0634         return c1 - c2;
0635     }
0636 
0637     return 0;
0638 }
0639 
0640 
0641 u_char *
0642 ngx_strnstr(u_char *s1, char *s2, size_t len)
0643 {
0644     u_char  c1, c2;
0645     size_t  n;
0646 
0647     c2 = *(u_char *) s2++;
0648 
0649     n = ngx_strlen(s2);
0650 
0651     do {
0652         do {
0653             if (len-- == 0) {
0654                 return NULL;
0655             }
0656 
0657             c1 = *s1++;
0658 
0659             if (c1 == 0) {
0660                 return NULL;
0661             }
0662 
0663         } while (c1 != c2);
0664 
0665         if (n > len) {
0666             return NULL;
0667         }
0668 
0669     } while (ngx_strncmp(s1, (u_char *) s2, n) != 0);
0670 
0671     return --s1;
0672 }
0673 
0674 
0675 /*
0676  * ngx_strstrn() and ngx_strcasestrn() are intended to search for static
0677  * substring with known length in null-terminated string. The argument n
0678  * must be length of the second substring - 1.
0679  */
0680 
0681 u_char *
0682 ngx_strstrn(u_char *s1, char *s2, size_t n)
0683 {
0684     u_char  c1, c2;
0685 
0686     c2 = *(u_char *) s2++;
0687 
0688     do {
0689         do {
0690             c1 = *s1++;
0691 
0692             if (c1 == 0) {
0693                 return NULL;
0694             }
0695 
0696         } while (c1 != c2);
0697 
0698     } while (ngx_strncmp(s1, (u_char *) s2, n) != 0);
0699 
0700     return --s1;
0701 }
0702 
0703 
0704 u_char *
0705 ngx_strcasestrn(u_char *s1, char *s2, size_t n)
0706 {
0707     ngx_uint_t  c1, c2;
0708 
0709     c2 = (ngx_uint_t) *s2++;
0710     c2 = (c2 >= 'A' && c2 <= 'Z') ? (c2 | 0x20) : c2;
0711 
0712     do {
0713         do {
0714             c1 = (ngx_uint_t) *s1++;
0715 
0716             if (c1 == 0) {
0717                 return NULL;
0718             }
0719 
0720             c1 = (c1 >= 'A' && c1 <= 'Z') ? (c1 | 0x20) : c1;
0721 
0722         } while (c1 != c2);
0723 
0724     } while (ngx_strncasecmp(s1, (u_char *) s2, n) != 0);
0725 
0726     return --s1;
0727 }
0728 
0729 
0730 /*
0731  * ngx_strlcasestrn() is intended to search for static substring
0732  * with known length in string until the argument last. The argument n
0733  * must be length of the second substring - 1.
0734  */
0735 
0736 u_char *
0737 ngx_strlcasestrn(u_char *s1, u_char *last, u_char *s2, size_t n)
0738 {
0739     ngx_uint_t  c1, c2;
0740 
0741     c2 = (ngx_uint_t) *s2++;
0742     c2 = (c2 >= 'A' && c2 <= 'Z') ? (c2 | 0x20) : c2;
0743     last -= n;
0744 
0745     do {
0746         do {
0747             if (s1 >= last) {
0748                 return NULL;
0749             }
0750 
0751             c1 = (ngx_uint_t) *s1++;
0752 
0753             c1 = (c1 >= 'A' && c1 <= 'Z') ? (c1 | 0x20) : c1;
0754 
0755         } while (c1 != c2);
0756 
0757     } while (ngx_strncasecmp(s1, s2, n) != 0);
0758 
0759     return --s1;
0760 }
0761 
0762 
0763 ngx_int_t
0764 ngx_rstrncmp(u_char *s1, u_char *s2, size_t n)
0765 {
0766     if (n == 0) {
0767         return 0;
0768     }
0769 
0770     n--;
0771 
0772     for ( ;; ) {
0773         if (s1[n] != s2[n]) {
0774             return s1[n] - s2[n];
0775         }
0776 
0777         if (n == 0) {
0778             return 0;
0779         }
0780 
0781         n--;
0782     }
0783 }
0784 
0785 
0786 ngx_int_t
0787 ngx_rstrncasecmp(u_char *s1, u_char *s2, size_t n)
0788 {
0789     u_char  c1, c2;
0790 
0791     if (n == 0) {
0792         return 0;
0793     }
0794 
0795     n--;
0796 
0797     for ( ;; ) {
0798         c1 = s1[n];
0799         if (c1 >= 'a' && c1 <= 'z') {
0800             c1 -= 'a' - 'A';
0801         }
0802 
0803         c2 = s2[n];
0804         if (c2 >= 'a' && c2 <= 'z') {
0805             c2 -= 'a' - 'A';
0806         }
0807 
0808         if (c1 != c2) {
0809             return c1 - c2;
0810         }
0811 
0812         if (n == 0) {
0813             return 0;
0814         }
0815 
0816         n--;
0817     }
0818 }
0819 
0820 
0821 ngx_int_t
0822 ngx_memn2cmp(u_char *s1, u_char *s2, size_t n1, size_t n2)
0823 {
0824     size_t     n;
0825     ngx_int_t  m, z;
0826 
0827     if (n1 <= n2) {
0828         n = n1;
0829         z = -1;
0830 
0831     } else {
0832         n = n2;
0833         z = 1;
0834     }
0835 
0836     m = ngx_memcmp(s1, s2, n);
0837 
0838     if (m || n1 == n2) {
0839         return m;
0840     }
0841 
0842     return z;
0843 }
0844 
0845 
0846 ngx_int_t
0847 ngx_dns_strcmp(u_char *s1, u_char *s2)
0848 {
0849     ngx_uint_t  c1, c2;
0850 
0851     for ( ;; ) {
0852         c1 = (ngx_uint_t) *s1++;
0853         c2 = (ngx_uint_t) *s2++;
0854 
0855         c1 = (c1 >= 'A' && c1 <= 'Z') ? (c1 | 0x20) : c1;
0856         c2 = (c2 >= 'A' && c2 <= 'Z') ? (c2 | 0x20) : c2;
0857 
0858         if (c1 == c2) {
0859 
0860             if (c1) {
0861                 continue;
0862             }
0863 
0864             return 0;
0865         }
0866 
0867         /* in ASCII '.' > '-', but we need '.' to be the lowest character */
0868 
0869         c1 = (c1 == '.') ? ' ' : c1;
0870         c2 = (c2 == '.') ? ' ' : c2;
0871 
0872         return c1 - c2;
0873     }
0874 }
0875 
0876 
0877 ngx_int_t
0878 ngx_filename_cmp(u_char *s1, u_char *s2, size_t n)
0879 {
0880     ngx_uint_t  c1, c2;
0881 
0882     while (n) {
0883         c1 = (ngx_uint_t) *s1++;
0884         c2 = (ngx_uint_t) *s2++;
0885 
0886 #if (NGX_HAVE_CASELESS_FILESYSTEM)
0887         c1 = tolower(c1);
0888         c2 = tolower(c2);
0889 #endif
0890 
0891         if (c1 == c2) {
0892 
0893             if (c1) {
0894                 n--;
0895                 continue;
0896             }
0897 
0898             return 0;
0899         }
0900 
0901         /* we need '/' to be the lowest character */
0902 
0903         if (c1 == 0 || c2 == 0) {
0904             return c1 - c2;
0905         }
0906 
0907         c1 = (c1 == '/') ? 0 : c1;
0908         c2 = (c2 == '/') ? 0 : c2;
0909 
0910         return c1 - c2;
0911     }
0912 
0913     return 0;
0914 }
0915 
0916 
0917 ngx_int_t
0918 ngx_atoi(u_char *line, size_t n)
0919 {
0920     ngx_int_t  value, cutoff, cutlim;
0921 
0922     if (n == 0) {
0923         return NGX_ERROR;
0924     }
0925 
0926     cutoff = NGX_MAX_INT_T_VALUE / 10;
0927     cutlim = NGX_MAX_INT_T_VALUE % 10;
0928 
0929     for (value = 0; n--; line++) {
0930         if (*line < '0' || *line > '9') {
0931             return NGX_ERROR;
0932         }
0933 
0934         if (value >= cutoff && (value > cutoff || *line - '0' > cutlim)) {
0935             return NGX_ERROR;
0936         }
0937 
0938         value = value * 10 + (*line - '0');
0939     }
0940 
0941     return value;
0942 }
0943 
0944 
0945 /* parse a fixed point number, e.g., ngx_atofp("10.5", 4, 2) returns 1050 */
0946 
0947 ngx_int_t
0948 ngx_atofp(u_char *line, size_t n, size_t point)
0949 {
0950     ngx_int_t   value, cutoff, cutlim;
0951     ngx_uint_t  dot;
0952 
0953     if (n == 0) {
0954         return NGX_ERROR;
0955     }
0956 
0957     cutoff = NGX_MAX_INT_T_VALUE / 10;
0958     cutlim = NGX_MAX_INT_T_VALUE % 10;
0959 
0960     dot = 0;
0961 
0962     for (value = 0; n--; line++) {
0963 
0964         if (point == 0) {
0965             return NGX_ERROR;
0966         }
0967 
0968         if (*line == '.') {
0969             if (dot) {
0970                 return NGX_ERROR;
0971             }
0972 
0973             dot = 1;
0974             continue;
0975         }
0976 
0977         if (*line < '0' || *line > '9') {
0978             return NGX_ERROR;
0979         }
0980 
0981         if (value >= cutoff && (value > cutoff || *line - '0' > cutlim)) {
0982             return NGX_ERROR;
0983         }
0984 
0985         value = value * 10 + (*line - '0');
0986         point -= dot;
0987     }
0988 
0989     while (point--) {
0990         if (value > cutoff) {
0991             return NGX_ERROR;
0992         }
0993 
0994         value = value * 10;
0995     }
0996 
0997     return value;
0998 }
0999 
1000 
1001 ssize_t
1002 ngx_atosz(u_char *line, size_t n)
1003 {
1004     ssize_t  value, cutoff, cutlim;
1005 
1006     if (n == 0) {
1007         return NGX_ERROR;
1008     }
1009 
1010     cutoff = NGX_MAX_SIZE_T_VALUE / 10;
1011     cutlim = NGX_MAX_SIZE_T_VALUE % 10;
1012 
1013     for (value = 0; n--; line++) {
1014         if (*line < '0' || *line > '9') {
1015             return NGX_ERROR;
1016         }
1017 
1018         if (value >= cutoff && (value > cutoff || *line - '0' > cutlim)) {
1019             return NGX_ERROR;
1020         }
1021 
1022         value = value * 10 + (*line - '0');
1023     }
1024 
1025     return value;
1026 }
1027 
1028 
1029 off_t
1030 ngx_atoof(u_char *line, size_t n)
1031 {
1032     off_t  value, cutoff, cutlim;
1033 
1034     if (n == 0) {
1035         return NGX_ERROR;
1036     }
1037 
1038     cutoff = NGX_MAX_OFF_T_VALUE / 10;
1039     cutlim = NGX_MAX_OFF_T_VALUE % 10;
1040 
1041     for (value = 0; n--; line++) {
1042         if (*line < '0' || *line > '9') {
1043             return NGX_ERROR;
1044         }
1045 
1046         if (value >= cutoff && (value > cutoff || *line - '0' > cutlim)) {
1047             return NGX_ERROR;
1048         }
1049 
1050         value = value * 10 + (*line - '0');
1051     }
1052 
1053     return value;
1054 }
1055 
1056 
1057 time_t
1058 ngx_atotm(u_char *line, size_t n)
1059 {
1060     time_t  value, cutoff, cutlim;
1061 
1062     if (n == 0) {
1063         return NGX_ERROR;
1064     }
1065 
1066     cutoff = NGX_MAX_TIME_T_VALUE / 10;
1067     cutlim = NGX_MAX_TIME_T_VALUE % 10;
1068 
1069     for (value = 0; n--; line++) {
1070         if (*line < '0' || *line > '9') {
1071             return NGX_ERROR;
1072         }
1073 
1074         if (value >= cutoff && (value > cutoff || *line - '0' > cutlim)) {
1075             return NGX_ERROR;
1076         }
1077 
1078         value = value * 10 + (*line - '0');
1079     }
1080 
1081     return value;
1082 }
1083 
1084 
1085 ngx_int_t
1086 ngx_hextoi(u_char *line, size_t n)
1087 {
1088     u_char     c, ch;
1089     ngx_int_t  value, cutoff;
1090 
1091     if (n == 0) {
1092         return NGX_ERROR;
1093     }
1094 
1095     cutoff = NGX_MAX_INT_T_VALUE / 16;
1096 
1097     for (value = 0; n--; line++) {
1098         if (value > cutoff) {
1099             return NGX_ERROR;
1100         }
1101 
1102         ch = *line;
1103 
1104         if (ch >= '0' && ch <= '9') {
1105             value = value * 16 + (ch - '0');
1106             continue;
1107         }
1108 
1109         c = (u_char) (ch | 0x20);
1110 
1111         if (c >= 'a' && c <= 'f') {
1112             value = value * 16 + (c - 'a' + 10);
1113             continue;
1114         }
1115 
1116         return NGX_ERROR;
1117     }
1118 
1119     return value;
1120 }
1121 
1122 
1123 u_char *
1124 ngx_hex_dump(u_char *dst, u_char *src, size_t len)
1125 {
1126     static u_char  hex[] = "0123456789abcdef";
1127 
1128     while (len--) {
1129         *dst++ = hex[*src >> 4];
1130         *dst++ = hex[*src++ & 0xf];
1131     }
1132 
1133     return dst;
1134 }
1135 
1136 
1137 void
1138 ngx_encode_base64(ngx_str_t *dst, ngx_str_t *src)
1139 {
1140     static u_char   basis64[] =
1141             "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
1142 
1143     ngx_encode_base64_internal(dst, src, basis64, 1);
1144 }
1145 
1146 
1147 void
1148 ngx_encode_base64url(ngx_str_t *dst, ngx_str_t *src)
1149 {
1150     static u_char   basis64[] =
1151             "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_";
1152 
1153     ngx_encode_base64_internal(dst, src, basis64, 0);
1154 }
1155 
1156 
1157 static void
1158 ngx_encode_base64_internal(ngx_str_t *dst, ngx_str_t *src, const u_char *basis,
1159     ngx_uint_t padding)
1160 {
1161     u_char         *d, *s;
1162     size_t          len;
1163 
1164     len = src->len;
1165     s = src->data;
1166     d = dst->data;
1167 
1168     while (len > 2) {
1169         *d++ = basis[(s[0] >> 2) & 0x3f];
1170         *d++ = basis[((s[0] & 3) << 4) | (s[1] >> 4)];
1171         *d++ = basis[((s[1] & 0x0f) << 2) | (s[2] >> 6)];
1172         *d++ = basis[s[2] & 0x3f];
1173 
1174         s += 3;
1175         len -= 3;
1176     }
1177 
1178     if (len) {
1179         *d++ = basis[(s[0] >> 2) & 0x3f];
1180 
1181         if (len == 1) {
1182             *d++ = basis[(s[0] & 3) << 4];
1183             if (padding) {
1184                 *d++ = '=';
1185             }
1186 
1187         } else {
1188             *d++ = basis[((s[0] & 3) << 4) | (s[1] >> 4)];
1189             *d++ = basis[(s[1] & 0x0f) << 2];
1190         }
1191 
1192         if (padding) {
1193             *d++ = '=';
1194         }
1195     }
1196 
1197     dst->len = d - dst->data;
1198 }
1199 
1200 
1201 ngx_int_t
1202 ngx_decode_base64(ngx_str_t *dst, ngx_str_t *src)
1203 {
1204     static u_char   basis64[] = {
1205         77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
1206         77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
1207         77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 62, 77, 77, 77, 63,
1208         52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 77, 77, 77, 77, 77, 77,
1209         77,  0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14,
1210         15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 77, 77, 77, 77, 77,
1211         77, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
1212         41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 77, 77, 77, 77, 77,
1213 
1214         77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
1215         77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
1216         77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
1217         77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
1218         77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
1219         77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
1220         77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
1221         77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77
1222     };
1223 
1224     return ngx_decode_base64_internal(dst, src, basis64);
1225 }
1226 
1227 
1228 ngx_int_t
1229 ngx_decode_base64url(ngx_str_t *dst, ngx_str_t *src)
1230 {
1231     static u_char   basis64[] = {
1232         77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
1233         77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
1234         77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 62, 77, 77,
1235         52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 77, 77, 77, 77, 77, 77,
1236         77,  0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14,
1237         15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 77, 77, 77, 77, 63,
1238         77, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
1239         41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 77, 77, 77, 77, 77,
1240 
1241         77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
1242         77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
1243         77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
1244         77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
1245         77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
1246         77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
1247         77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
1248         77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77
1249     };
1250 
1251     return ngx_decode_base64_internal(dst, src, basis64);
1252 }
1253 
1254 
1255 static ngx_int_t
1256 ngx_decode_base64_internal(ngx_str_t *dst, ngx_str_t *src, const u_char *basis)
1257 {
1258     size_t          len;
1259     u_char         *d, *s;
1260 
1261     for (len = 0; len < src->len; len++) {
1262         if (src->data[len] == '=') {
1263             break;
1264         }
1265 
1266         if (basis[src->data[len]] == 77) {
1267             return NGX_ERROR;
1268         }
1269     }
1270 
1271     if (len % 4 == 1) {
1272         return NGX_ERROR;
1273     }
1274 
1275     s = src->data;
1276     d = dst->data;
1277 
1278     while (len > 3) {
1279         *d++ = (u_char) (basis[s[0]] << 2 | basis[s[1]] >> 4);
1280         *d++ = (u_char) (basis[s[1]] << 4 | basis[s[2]] >> 2);
1281         *d++ = (u_char) (basis[s[2]] << 6 | basis[s[3]]);
1282 
1283         s += 4;
1284         len -= 4;
1285     }
1286 
1287     if (len > 1) {
1288         *d++ = (u_char) (basis[s[0]] << 2 | basis[s[1]] >> 4);
1289     }
1290 
1291     if (len > 2) {
1292         *d++ = (u_char) (basis[s[1]] << 4 | basis[s[2]] >> 2);
1293     }
1294 
1295     dst->len = d - dst->data;
1296 
1297     return NGX_OK;
1298 }
1299 
1300 
1301 /*
1302  * ngx_utf8_decode() decodes two and more bytes UTF sequences only
1303  * the return values:
1304  *    0x80 - 0x10ffff         valid character
1305  *    0x110000 - 0xfffffffd   invalid sequence
1306  *    0xfffffffe              incomplete sequence
1307  *    0xffffffff              error
1308  */
1309 
1310 uint32_t
1311 ngx_utf8_decode(u_char **p, size_t n)
1312 {
1313     size_t    len;
1314     uint32_t  u, i, valid;
1315 
1316     u = **p;
1317 
1318     if (u >= 0xf0) {
1319 
1320         u &= 0x07;
1321         valid = 0xffff;
1322         len = 3;
1323 
1324     } else if (u >= 0xe0) {
1325 
1326         u &= 0x0f;
1327         valid = 0x7ff;
1328         len = 2;
1329 
1330     } else if (u >= 0xc2) {
1331 
1332         u &= 0x1f;
1333         valid = 0x7f;
1334         len = 1;
1335 
1336     } else {
1337         (*p)++;
1338         return 0xffffffff;
1339     }
1340 
1341     if (n - 1 < len) {
1342         return 0xfffffffe;
1343     }
1344 
1345     (*p)++;
1346 
1347     while (len) {
1348         i = *(*p)++;
1349 
1350         if (i < 0x80) {
1351             return 0xffffffff;
1352         }
1353 
1354         u = (u << 6) | (i & 0x3f);
1355 
1356         len--;
1357     }
1358 
1359     if (u > valid) {
1360         return u;
1361     }
1362 
1363     return 0xffffffff;
1364 }
1365 
1366 
1367 size_t
1368 ngx_utf8_length(u_char *p, size_t n)
1369 {
1370     u_char  c, *last;
1371     size_t  len;
1372 
1373     last = p + n;
1374 
1375     for (len = 0; p < last; len++) {
1376 
1377         c = *p;
1378 
1379         if (c < 0x80) {
1380             p++;
1381             continue;
1382         }
1383 
1384         if (ngx_utf8_decode(&p, n) > 0x10ffff) {
1385             /* invalid UTF-8 */
1386             return n;
1387         }
1388     }
1389 
1390     return len;
1391 }
1392 
1393 
1394 u_char *
1395 ngx_utf8_cpystrn(u_char *dst, u_char *src, size_t n, size_t len)
1396 {
1397     u_char  c, *next;
1398 
1399     if (n == 0) {
1400         return dst;
1401     }
1402 
1403     while (--n) {
1404 
1405         c = *src;
1406         *dst = c;
1407 
1408         if (c < 0x80) {
1409 
1410             if (c != '\0') {
1411                 dst++;
1412                 src++;
1413                 len--;
1414 
1415                 continue;
1416             }
1417 
1418             return dst;
1419         }
1420 
1421         next = src;
1422 
1423         if (ngx_utf8_decode(&next, len) > 0x10ffff) {
1424             /* invalid UTF-8 */
1425             break;
1426         }
1427 
1428         while (src < next) {
1429             *dst++ = *src++;
1430             len--;
1431         }
1432     }
1433 
1434     *dst = '\0';
1435 
1436     return dst;
1437 }
1438 
1439 
1440 uintptr_t
1441 ngx_escape_uri(u_char *dst, u_char *src, size_t size, ngx_uint_t type)
1442 {
1443     ngx_uint_t      n;
1444     uint32_t       *escape;
1445     static u_char   hex[] = "0123456789ABCDEF";
1446 
1447                     /* " ", "#", "%", "?", %00-%1F, %7F-%FF */
1448 
1449     static uint32_t   uri[] = {
1450         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1451 
1452                     /* ?>=< ;:98 7654 3210  /.-, +*)( '&%$ #"!  */
1453         0x80000029, /* 1000 0000 0000 0000  0000 0000 0010 1001 */
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         0x80000000, /* 1000 0000 0000 0000  0000 0000 0000 0000 */
1460 
1461         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1462         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1463         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1464         0xffffffff  /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1465     };
1466 
1467                     /* " ", "#", "%", "&", "+", "?", %00-%1F, %7F-%FF */
1468 
1469     static uint32_t   args[] = {
1470         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1471 
1472                     /* ?>=< ;:98 7654 3210  /.-, +*)( '&%$ #"!  */
1473         0x88000869, /* 1000 1000 0000 0000  0000 1000 0110 1001 */
1474 
1475                     /* _^]\ [ZYX WVUT SRQP  ONML KJIH GFED CBA@ */
1476         0x00000000, /* 0000 0000 0000 0000  0000 0000 0000 0000 */
1477 
1478                     /*  ~}| {zyx wvut srqp  onml kjih gfed cba` */
1479         0x80000000, /* 1000 0000 0000 0000  0000 0000 0000 0000 */
1480 
1481         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1482         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1483         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1484         0xffffffff  /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1485     };
1486 
1487                     /* not ALPHA, DIGIT, "-", ".", "_", "~" */
1488 
1489     static uint32_t   uri_component[] = {
1490         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1491 
1492                     /* ?>=< ;:98 7654 3210  /.-, +*)( '&%$ #"!  */
1493         0xfc009fff, /* 1111 1100 0000 0000  1001 1111 1111 1111 */
1494 
1495                     /* _^]\ [ZYX WVUT SRQP  ONML KJIH GFED CBA@ */
1496         0x78000001, /* 0111 1000 0000 0000  0000 0000 0000 0001 */
1497 
1498                     /*  ~}| {zyx wvut srqp  onml kjih gfed cba` */
1499         0xb8000001, /* 1011 1000 0000 0000  0000 0000 0000 0001 */
1500 
1501         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1502         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1503         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1504         0xffffffff  /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1505     };
1506 
1507                     /* " ", "#", """, "%", "'", %00-%1F, %7F-%FF */
1508 
1509     static uint32_t   html[] = {
1510         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1511 
1512                     /* ?>=< ;:98 7654 3210  /.-, +*)( '&%$ #"!  */
1513         0x000000ad, /* 0000 0000 0000 0000  0000 0000 1010 1101 */
1514 
1515                     /* _^]\ [ZYX WVUT SRQP  ONML KJIH GFED CBA@ */
1516         0x00000000, /* 0000 0000 0000 0000  0000 0000 0000 0000 */
1517 
1518                     /*  ~}| {zyx wvut srqp  onml kjih gfed cba` */
1519         0x80000000, /* 1000 0000 0000 0000  0000 0000 0000 0000 */
1520 
1521         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1522         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1523         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1524         0xffffffff  /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1525     };
1526 
1527                     /* " ", """, "%", "'", %00-%1F, %7F-%FF */
1528 
1529     static uint32_t   refresh[] = {
1530         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1531 
1532                     /* ?>=< ;:98 7654 3210  /.-, +*)( '&%$ #"!  */
1533         0x00000085, /* 0000 0000 0000 0000  0000 0000 1000 0101 */
1534 
1535                     /* _^]\ [ZYX WVUT SRQP  ONML KJIH GFED CBA@ */
1536         0x00000000, /* 0000 0000 0000 0000  0000 0000 0000 0000 */
1537 
1538                     /*  ~}| {zyx wvut srqp  onml kjih gfed cba` */
1539         0x80000000, /* 1000 0000 0000 0000  0000 0000 0000 0000 */
1540 
1541         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1542         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1543         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1544         0xffffffff  /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1545     };
1546 
1547                     /* " ", "%", %00-%1F */
1548 
1549     static uint32_t   memcached[] = {
1550         0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1551 
1552                     /* ?>=< ;:98 7654 3210  /.-, +*)( '&%$ #"!  */
1553         0x00000021, /* 0000 0000 0000 0000  0000 0000 0010 0001 */
1554 
1555                     /* _^]\ [ZYX WVUT SRQP  ONML KJIH GFED CBA@ */
1556         0x00000000, /* 0000 0000 0000 0000  0000 0000 0000 0000 */
1557 
1558                     /*  ~}| {zyx wvut srqp  onml kjih gfed cba` */
1559         0x00000000, /* 0000 0000 0000 0000  0000 0000 0000 0000 */
1560 
1561         0x00000000, /* 0000 0000 0000 0000  0000 0000 0000 0000 */
1562         0x00000000, /* 0000 0000 0000 0000  0000 0000 0000 0000 */
1563         0x00000000, /* 0000 0000 0000 0000  0000 0000 0000 0000 */
1564         0x00000000, /* 0000 0000 0000 0000  0000 0000 0000 0000 */
1565     };
1566 
1567                     /* mail_auth is the same as memcached */
1568 
1569     static uint32_t  *map[] =
1570         { uri, args, uri_component, html, refresh, memcached, memcached };
1571 
1572 
1573     escape = map[type];
1574 
1575     if (dst == NULL) {
1576 
1577         /* find the number of the characters to be escaped */
1578 
1579         n = 0;
1580 
1581         while (size) {
1582             if (escape[*src >> 5] & (1U << (*src & 0x1f))) {
1583                 n++;
1584             }
1585             src++;
1586             size--;
1587         }
1588 
1589         return (uintptr_t) n;
1590     }
1591 
1592     while (size) {
1593         if (escape[*src >> 5] & (1U << (*src & 0x1f))) {
1594             *dst++ = '%';
1595             *dst++ = hex[*src >> 4];
1596             *dst++ = hex[*src & 0xf];
1597             src++;
1598 
1599         } else {
1600             *dst++ = *src++;
1601         }
1602         size--;
1603     }
1604 
1605     return (uintptr_t) dst;
1606 }
1607 
1608 
1609 void
1610 ngx_unescape_uri(u_char **dst, u_char **src, size_t size, ngx_uint_t type)
1611 {
1612     u_char  *d, *s, ch, c, decoded;
1613     enum {
1614         sw_usual = 0,
1615         sw_quoted,
1616         sw_quoted_second
1617     } state;
1618 
1619     d = *dst;
1620     s = *src;
1621 
1622     state = 0;
1623     decoded = 0;
1624 
1625     while (size--) {
1626 
1627         ch = *s++;
1628 
1629         switch (state) {
1630         case sw_usual:
1631             if (ch == '?'
1632                 && (type & (NGX_UNESCAPE_URI|NGX_UNESCAPE_REDIRECT)))
1633             {
1634                 *d++ = ch;
1635                 goto done;
1636             }
1637 
1638             if (ch == '%') {
1639                 state = sw_quoted;
1640                 break;
1641             }
1642 
1643             *d++ = ch;
1644             break;
1645 
1646         case sw_quoted:
1647 
1648             if (ch >= '0' && ch <= '9') {
1649                 decoded = (u_char) (ch - '0');
1650                 state = sw_quoted_second;
1651                 break;
1652             }
1653 
1654             c = (u_char) (ch | 0x20);
1655             if (c >= 'a' && c <= 'f') {
1656                 decoded = (u_char) (c - 'a' + 10);
1657                 state = sw_quoted_second;
1658                 break;
1659             }
1660 
1661             /* the invalid quoted character */
1662 
1663             state = sw_usual;
1664 
1665             *d++ = ch;
1666 
1667             break;
1668 
1669         case sw_quoted_second:
1670 
1671             state = sw_usual;
1672 
1673             if (ch >= '0' && ch <= '9') {
1674                 ch = (u_char) ((decoded << 4) + (ch - '0'));
1675 
1676                 if (type & NGX_UNESCAPE_REDIRECT) {
1677                     if (ch > '%' && ch < 0x7f) {
1678                         *d++ = ch;
1679                         break;
1680                     }
1681 
1682                     *d++ = '%'; *d++ = *(s - 2); *d++ = *(s - 1);
1683 
1684                     break;
1685                 }
1686 
1687                 *d++ = ch;
1688 
1689                 break;
1690             }
1691 
1692             c = (u_char) (ch | 0x20);
1693             if (c >= 'a' && c <= 'f') {
1694                 ch = (u_char) ((decoded << 4) + (c - 'a') + 10);
1695 
1696                 if (type & NGX_UNESCAPE_URI) {
1697                     if (ch == '?') {
1698                         *d++ = ch;
1699                         goto done;
1700                     }
1701 
1702                     *d++ = ch;
1703                     break;
1704                 }
1705 
1706                 if (type & NGX_UNESCAPE_REDIRECT) {
1707                     if (ch == '?') {
1708                         *d++ = ch;
1709                         goto done;
1710                     }
1711 
1712                     if (ch > '%' && ch < 0x7f) {
1713                         *d++ = ch;
1714                         break;
1715                     }
1716 
1717                     *d++ = '%'; *d++ = *(s - 2); *d++ = *(s - 1);
1718                     break;
1719                 }
1720 
1721                 *d++ = ch;
1722 
1723                 break;
1724             }
1725 
1726             /* the invalid quoted character */
1727 
1728             break;
1729         }
1730     }
1731 
1732 done:
1733 
1734     *dst = d;
1735     *src = s;
1736 }
1737 
1738 
1739 uintptr_t
1740 ngx_escape_html(u_char *dst, u_char *src, size_t size)
1741 {
1742     u_char      ch;
1743     ngx_uint_t  len;
1744 
1745     if (dst == NULL) {
1746 
1747         len = 0;
1748 
1749         while (size) {
1750             switch (*src++) {
1751 
1752             case '<':
1753                 len += sizeof("&lt;") - 2;
1754                 break;
1755 
1756             case '>':
1757                 len += sizeof("&gt;") - 2;
1758                 break;
1759 
1760             case '&':
1761                 len += sizeof("&amp;") - 2;
1762                 break;
1763 
1764             case '"':
1765                 len += sizeof("&quot;") - 2;
1766                 break;
1767 
1768             default:
1769                 break;
1770             }
1771             size--;
1772         }
1773 
1774         return (uintptr_t) len;
1775     }
1776 
1777     while (size) {
1778         ch = *src++;
1779 
1780         switch (ch) {
1781 
1782         case '<':
1783             *dst++ = '&'; *dst++ = 'l'; *dst++ = 't'; *dst++ = ';';
1784             break;
1785 
1786         case '>':
1787             *dst++ = '&'; *dst++ = 'g'; *dst++ = 't'; *dst++ = ';';
1788             break;
1789 
1790         case '&':
1791             *dst++ = '&'; *dst++ = 'a'; *dst++ = 'm'; *dst++ = 'p';
1792             *dst++ = ';';
1793             break;
1794 
1795         case '"':
1796             *dst++ = '&'; *dst++ = 'q'; *dst++ = 'u'; *dst++ = 'o';
1797             *dst++ = 't'; *dst++ = ';';
1798             break;
1799 
1800         default:
1801             *dst++ = ch;
1802             break;
1803         }
1804         size--;
1805     }
1806 
1807     return (uintptr_t) dst;
1808 }
1809 
1810 
1811 uintptr_t
1812 ngx_escape_json(u_char *dst, u_char *src, size_t size)
1813 {
1814     u_char      ch;
1815     ngx_uint_t  len;
1816 
1817     if (dst == NULL) {
1818         len = 0;
1819 
1820         while (size) {
1821             ch = *src++;
1822 
1823             if (ch == '\\' || ch == '"') {
1824                 len++;
1825 
1826             } else if (ch <= 0x1f) {
1827 
1828                 switch (ch) {
1829                 case '\n':
1830                 case '\r':
1831                 case '\t':
1832                 case '\b':
1833                 case '\f':
1834                     len++;
1835                     break;
1836 
1837                 default:
1838                     len += sizeof("\\u001F") - 2;
1839                 }
1840             }
1841 
1842             size--;
1843         }
1844 
1845         return (uintptr_t) len;
1846     }
1847 
1848     while (size) {
1849         ch = *src++;
1850 
1851         if (ch > 0x1f) {
1852 
1853             if (ch == '\\' || ch == '"') {
1854                 *dst++ = '\\';
1855             }
1856 
1857             *dst++ = ch;
1858 
1859         } else {
1860             *dst++ = '\\';
1861 
1862             switch (ch) {
1863             case '\n':
1864                 *dst++ = 'n';
1865                 break;
1866 
1867             case '\r':
1868                 *dst++ = 'r';
1869                 break;
1870 
1871             case '\t':
1872                 *dst++ = 't';
1873                 break;
1874 
1875             case '\b':
1876                 *dst++ = 'b';
1877                 break;
1878 
1879             case '\f':
1880                 *dst++ = 'f';
1881                 break;
1882 
1883             default:
1884                 *dst++ = 'u'; *dst++ = '0'; *dst++ = '0';
1885                 *dst++ = '0' + (ch >> 4);
1886 
1887                 ch &= 0xf;
1888 
1889                 *dst++ = (ch < 10) ? ('0' + ch) : ('A' + ch - 10);
1890             }
1891         }
1892 
1893         size--;
1894     }
1895 
1896     return (uintptr_t) dst;
1897 }
1898 
1899 
1900 void
1901 ngx_str_rbtree_insert_value(ngx_rbtree_node_t *temp,
1902     ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel)
1903 {
1904     ngx_str_node_t      *n, *t;
1905     ngx_rbtree_node_t  **p;
1906 
1907     for ( ;; ) {
1908 
1909         n = (ngx_str_node_t *) node;
1910         t = (ngx_str_node_t *) temp;
1911 
1912         if (node->key != temp->key) {
1913 
1914             p = (node->key < temp->key) ? &temp->left : &temp->right;
1915 
1916         } else if (n->str.len != t->str.len) {
1917 
1918             p = (n->str.len < t->str.len) ? &temp->left : &temp->right;
1919 
1920         } else {
1921             p = (ngx_memcmp(n->str.data, t->str.data, n->str.len) < 0)
1922                  ? &temp->left : &temp->right;
1923         }
1924 
1925         if (*p == sentinel) {
1926             break;
1927         }
1928 
1929         temp = *p;
1930     }
1931 
1932     *p = node;
1933     node->parent = temp;
1934     node->left = sentinel;
1935     node->right = sentinel;
1936     ngx_rbt_red(node);
1937 }
1938 
1939 
1940 ngx_str_node_t *
1941 ngx_str_rbtree_lookup(ngx_rbtree_t *rbtree, ngx_str_t *val, uint32_t hash)
1942 {
1943     ngx_int_t           rc;
1944     ngx_str_node_t     *n;
1945     ngx_rbtree_node_t  *node, *sentinel;
1946 
1947     node = rbtree->root;
1948     sentinel = rbtree->sentinel;
1949 
1950     while (node != sentinel) {
1951 
1952         n = (ngx_str_node_t *) node;
1953 
1954         if (hash != node->key) {
1955             node = (hash < node->key) ? node->left : node->right;
1956             continue;
1957         }
1958 
1959         if (val->len != n->str.len) {
1960             node = (val->len < n->str.len) ? node->left : node->right;
1961             continue;
1962         }
1963 
1964         rc = ngx_memcmp(val->data, n->str.data, val->len);
1965 
1966         if (rc < 0) {
1967             node = node->left;
1968             continue;
1969         }
1970 
1971         if (rc > 0) {
1972             node = node->right;
1973             continue;
1974         }
1975 
1976         return n;
1977     }
1978 
1979     return NULL;
1980 }
1981 
1982 
1983 /* ngx_sort() is implemented as insertion sort because we need stable sort */
1984 
1985 void
1986 ngx_sort(void *base, size_t n, size_t size,
1987     ngx_int_t (*cmp)(const void *, const void *))
1988 {
1989     u_char  *p1, *p2, *p;
1990 
1991     p = ngx_alloc(size, ngx_cycle->log);
1992     if (p == NULL) {
1993         return;
1994     }
1995 
1996     for (p1 = (u_char *) base + size;
1997          p1 < (u_char *) base + n * size;
1998          p1 += size)
1999     {
2000         ngx_memcpy(p, p1, size);
2001 
2002         for (p2 = p1;
2003              p2 > (u_char *) base && cmp(p2 - size, p) > 0;
2004              p2 -= size)
2005         {
2006             ngx_memcpy(p2, p2 - size, size);
2007         }
2008 
2009         ngx_memcpy(p2, p, size);
2010     }
2011 
2012     ngx_free(p);
2013 }
2014 
2015 
2016 void
2017 ngx_explicit_memzero(void *buf, size_t n)
2018 {
2019     ngx_memzero(buf, n);
2020     ngx_memory_barrier();
2021 }
2022 
2023 
2024 #if (NGX_MEMCPY_LIMIT)
2025 
2026 void *
2027 ngx_memcpy(void *dst, const void *src, size_t n)
2028 {
2029     if (n > NGX_MEMCPY_LIMIT) {
2030         ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "memcpy %uz bytes", n);
2031         ngx_debug_point();
2032     }
2033 
2034     return memcpy(dst, src, n);
2035 }
2036 
2037 #endif