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