← Back to branch summary

~ubuntu-branches/ubuntu/trusty/nginx/trusty-proposed

« back to all changes in this revision

Viewing changes to src/core/ngx_string.c

  • Committer: Package Import Robot
  • Author(s): Kartik Mistry
  • Date: 2013-04-25 12:51:45 UTC
  • mfrom: (1.3.28)
  • mto: (1.3.29) (15.1.2 experimental)
  • mto: This revision was merged to the branch mainline in revision 64.
  • Revision ID: package-import@ubuntu.com-20130425125145-ugl0wor6bq0u5eae
Tags: upstream-1.4.0
Import upstream version 1.4.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/core/ngx_string.c
1
1
 
2
2
/*
3
3
 * Copyright (C) Igor Sysoev
 
4
 * Copyright (C) Nginx, Inc.
4
5
 */
5
6
 
6
7
 
8
9
#include <ngx_core.h>
9
10
 
10
11
 
 
12
static u_char *ngx_sprintf_num(u_char *buf, u_char *last, uint64_t ui64,
 
13
    u_char zero, ngx_uint_t hexadecimal, ngx_uint_t width);
 
14
static ngx_int_t ngx_decode_base64_internal(ngx_str_t *dst, ngx_str_t *src,
 
15
    const u_char *basis);
 
16
 
 
17
 
 
18
void
 
19
ngx_strlow(u_char *dst, u_char *src, size_t n)
 
20
{
 
21
    while (n) {
 
22
        *dst = ngx_tolower(*src);
 
23
        dst++;
 
24
        src++;
 
25
        n--;
 
26
    }
 
27
}
 
28
 
 
29
 
11
30
u_char *
12
31
ngx_cpystrn(u_char *dst, u_char *src, size_t n)
13
32
{
15
34
        return dst;
16
35
    }
17
36
 
18
 
    for ( /* void */ ; --n; dst++, src++) {
 
37
    while (--n) {
19
38
        *dst = *src;
20
39
 
21
40
        if (*dst == '\0') {
22
41
            return dst;
23
42
        }
 
43
 
 
44
        dst++;
 
45
        src++;
24
46
    }
25
47
 
26
48
    *dst = '\0';
34
56
{
35
57
    u_char  *dst;
36
58
 
37
 
    dst = ngx_palloc(pool, src->len);
 
59
    dst = ngx_pnalloc(pool, src->len);
38
60
    if (dst == NULL) {
39
61
        return NULL;
40
62
    }
56
78
 *    %[0][width][u][x|X]D      int32_t/uint32_t
57
79
 *    %[0][width][u][x|X]L      int64_t/uint64_t
58
80
 *    %[0][width|m][u][x|X]A    ngx_atomic_int_t/ngx_atomic_uint_t
 
81
 *    %[0][width][.width]f      double, max valid number fits to %18.15f
59
82
 *    %P                        ngx_pid_t
60
83
 *    %M                        ngx_msec_t
61
84
 *    %r                        rlim_t
71
94
 *
72
95
 *  reserved:
73
96
 *    %t                        ptrdiff_t
74
 
 *    %S                        null-teminated wchar string
 
97
 *    %S                        null-terminated wchar string
75
98
 *    %C                        wchar
76
99
 */
77
100
 
83
106
    va_list   args;
84
107
 
85
108
    va_start(args, fmt);
86
 
    p = ngx_vsnprintf(buf, /* STUB */ 65536, fmt, args);
 
109
    p = ngx_vslprintf(buf, (void *) -1, fmt, args);
87
110
    va_end(args);
88
111
 
89
112
    return p;
97
120
    va_list   args;
98
121
 
99
122
    va_start(args, fmt);
100
 
    p = ngx_vsnprintf(buf, max, fmt, args);
 
123
    p = ngx_vslprintf(buf, buf + max, fmt, args);
 
124
    va_end(args);
 
125
 
 
126
    return p;
 
127
}
 
128
 
 
129
 
 
130
u_char * ngx_cdecl
 
131
ngx_slprintf(u_char *buf, u_char *last, const char *fmt, ...)
 
132
{
 
133
    u_char   *p;
 
134
    va_list   args;
 
135
 
 
136
    va_start(args, fmt);
 
137
    p = ngx_vslprintf(buf, last, fmt, args);
101
138
    va_end(args);
102
139
 
103
140
    return p;
105
142
 
106
143
 
107
144
u_char *
108
 
ngx_vsnprintf(u_char *buf, size_t max, const char *fmt, va_list args)
 
145
ngx_vslprintf(u_char *buf, u_char *last, const char *fmt, va_list args)
109
146
{
110
 
    u_char                *p, zero, *last, temp[NGX_INT64_LEN + 1];
111
 
                                    /*
112
 
                                     * really we need temp[NGX_INT64_LEN] only,
113
 
                                     * but icc issues the warning
114
 
                                     */
 
147
    u_char                *p, zero;
115
148
    int                    d;
 
149
    double                 f;
116
150
    size_t                 len, slen;
117
 
    uint32_t               ui32;
118
151
    int64_t                i64;
119
 
    uint64_t               ui64;
 
152
    uint64_t               ui64, frac;
120
153
    ngx_msec_t             ms;
121
 
    ngx_uint_t             width, sign, hexadecimal, max_width;
 
154
    ngx_uint_t             width, sign, hex, max_width, frac_width, scale, n;
122
155
    ngx_str_t             *v;
123
156
    ngx_variable_value_t  *vv;
124
 
    static u_char          hex[] = "0123456789abcdef";
125
 
    static u_char          HEX[] = "0123456789ABCDEF";
126
 
 
127
 
    if (max == 0) {
128
 
        return buf;
129
 
    }
130
 
 
131
 
    last = buf + max;
132
157
 
133
158
    while (*fmt && buf < last) {
134
159
 
145
170
            zero = (u_char) ((*++fmt == '0') ? '0' : ' ');
146
171
            width = 0;
147
172
            sign = 1;
148
 
            hexadecimal = 0;
 
173
            hex = 0;
149
174
            max_width = 0;
 
175
            frac_width = 0;
150
176
            slen = (size_t) -1;
151
177
 
152
 
            p = temp + NGX_INT64_LEN;
153
 
 
154
178
            while (*fmt >= '0' && *fmt <= '9') {
155
179
                width = width * 10 + *fmt++ - '0';
156
180
            }
170
194
                    continue;
171
195
 
172
196
                case 'X':
173
 
                    hexadecimal = 2;
 
197
                    hex = 2;
174
198
                    sign = 0;
175
199
                    fmt++;
176
200
                    continue;
177
201
 
178
202
                case 'x':
179
 
                    hexadecimal = 1;
 
203
                    hex = 1;
180
204
                    sign = 0;
181
205
                    fmt++;
182
206
                    continue;
183
207
 
 
208
                case '.':
 
209
                    fmt++;
 
210
 
 
211
                    while (*fmt >= '0' && *fmt <= '9') {
 
212
                        frac_width = frac_width * 10 + *fmt++ - '0';
 
213
                    }
 
214
 
 
215
                    break;
 
216
 
184
217
                case '*':
185
218
                    slen = va_arg(args, size_t);
186
219
                    fmt++;
199
232
            case 'V':
200
233
                v = va_arg(args, ngx_str_t *);
201
234
 
202
 
                len = v->len;
203
 
                len = (buf + len < last) ? len : (size_t) (last - buf);
204
 
 
 
235
                len = ngx_min(((size_t) (last - buf)), v->len);
205
236
                buf = ngx_cpymem(buf, v->data, len);
206
237
                fmt++;
207
238
 
210
241
            case 'v':
211
242
                vv = va_arg(args, ngx_variable_value_t *);
212
243
 
213
 
                len = vv->len;
214
 
                len = (buf + len < last) ? len : (size_t) (last - buf);
215
 
 
 
244
                len = ngx_min(((size_t) (last - buf)), vv->len);
216
245
                buf = ngx_cpymem(buf, vv->data, len);
217
246
                fmt++;
218
247
 
227
256
                    }
228
257
 
229
258
                } else {
230
 
                    len = (buf + slen < last) ? slen : (size_t) (last - buf);
231
 
 
 
259
                    len = ngx_min(((size_t) (last - buf)), slen);
232
260
                    buf = ngx_cpymem(buf, p, len);
233
261
                }
234
262
 
328
356
 
329
357
                break;
330
358
 
 
359
            case 'f':
 
360
                f = va_arg(args, double);
 
361
 
 
362
                if (f < 0) {
 
363
                    *buf++ = '-';
 
364
                    f = -f;
 
365
                }
 
366
 
 
367
                ui64 = (int64_t) f;
 
368
                frac = 0;
 
369
 
 
370
                if (frac_width) {
 
371
 
 
372
                    scale = 1;
 
373
                    for (n = frac_width; n; n--) {
 
374
                        scale *= 10;
 
375
                    }
 
376
 
 
377
                    frac = (uint64_t) ((f - (double) ui64) * scale + 0.5);
 
378
 
 
379
                    if (frac == scale) {
 
380
                        ui64++;
 
381
                        frac = 0;
 
382
                    }
 
383
                }
 
384
 
 
385
                buf = ngx_sprintf_num(buf, last, ui64, zero, 0, width);
 
386
 
 
387
                if (frac_width) {
 
388
                    if (buf < last) {
 
389
                        *buf++ = '.';
 
390
                    }
 
391
 
 
392
                    buf = ngx_sprintf_num(buf, last, frac, '0', 0, frac_width);
 
393
                }
 
394
 
 
395
                fmt++;
 
396
 
 
397
                continue;
 
398
 
331
399
#if !(NGX_WIN32)
332
400
            case 'r':
333
401
                i64 = (int64_t) va_arg(args, rlim_t);
337
405
 
338
406
            case 'p':
339
407
                ui64 = (uintptr_t) va_arg(args, void *);
340
 
                hexadecimal = 2;
 
408
                hex = 2;
341
409
                sign = 0;
342
410
                zero = '0';
343
411
                width = NGX_PTR_SIZE * 2;
387
455
                }
388
456
            }
389
457
 
390
 
            if (hexadecimal == 1) {
391
 
                do {
392
 
 
393
 
                    /* the "(uint32_t)" cast disables the BCC's warning */
394
 
                    *--p = hex[(uint32_t) (ui64 & 0xf)];
395
 
 
396
 
                } while (ui64 >>= 4);
397
 
 
398
 
            } else if (hexadecimal == 2) {
399
 
                do {
400
 
 
401
 
                    /* the "(uint32_t)" cast disables the BCC's warning */
402
 
                    *--p = HEX[(uint32_t) (ui64 & 0xf)];
403
 
 
404
 
                } while (ui64 >>= 4);
405
 
 
406
 
            } else if (ui64 <= NGX_MAX_UINT32_VALUE) {
407
 
 
408
 
                /*
409
 
                 * To divide 64-bit number and to find the remainder
410
 
                 * on the x86 platform gcc and icc call the libc functions
411
 
                 * [u]divdi3() and [u]moddi3(), they call another function
412
 
                 * in its turn.  On FreeBSD it is the qdivrem() function,
413
 
                 * its source code is about 170 lines of the code.
414
 
                 * The glibc counterpart is about 150 lines of the code.
415
 
                 *
416
 
                 * For 32-bit numbers and some divisors gcc and icc use
417
 
                 * the inlined multiplication and shifts.  For example,
418
 
                 * unsigned "i32 / 10" is compiled to
419
 
                 *
420
 
                 *     (i32 * 0xCCCCCCCD) >> 35
421
 
                 */
422
 
 
423
 
                ui32 = (uint32_t) ui64;
424
 
 
425
 
                do {
426
 
                    *--p = (u_char) (ui32 % 10 + '0');
427
 
                } while (ui32 /= 10);
428
 
 
429
 
            } else {
430
 
                do {
431
 
                    *--p = (u_char) (ui64 % 10 + '0');
432
 
                } while (ui64 /= 10);
433
 
            }
434
 
 
435
 
            len = (temp + NGX_INT64_LEN) - p;
436
 
 
437
 
            while (len++ < width && buf < last) {
438
 
                *buf++ = zero;
439
 
            }
440
 
 
441
 
            len = (temp + NGX_INT64_LEN) - p;
442
 
            if (buf + len > last) {
443
 
                len = last - buf;
444
 
            }
445
 
 
446
 
            buf = ngx_cpymem(buf, p, len);
 
458
            buf = ngx_sprintf_num(buf, last, ui64, zero, hex, width);
447
459
 
448
460
            fmt++;
449
461
 
456
468
}
457
469
 
458
470
 
 
471
static u_char *
 
472
ngx_sprintf_num(u_char *buf, u_char *last, uint64_t ui64, u_char zero,
 
473
    ngx_uint_t hexadecimal, ngx_uint_t width)
 
474
{
 
475
    u_char         *p, temp[NGX_INT64_LEN + 1];
 
476
                       /*
 
477
                        * we need temp[NGX_INT64_LEN] only,
 
478
                        * but icc issues the warning
 
479
                        */
 
480
    size_t          len;
 
481
    uint32_t        ui32;
 
482
    static u_char   hex[] = "0123456789abcdef";
 
483
    static u_char   HEX[] = "0123456789ABCDEF";
 
484
 
 
485
    p = temp + NGX_INT64_LEN;
 
486
 
 
487
    if (hexadecimal == 0) {
 
488
 
 
489
        if (ui64 <= NGX_MAX_UINT32_VALUE) {
 
490
 
 
491
            /*
 
492
             * To divide 64-bit numbers and to find remainders
 
493
             * on the x86 platform gcc and icc call the libc functions
 
494
             * [u]divdi3() and [u]moddi3(), they call another function
 
495
             * in its turn.  On FreeBSD it is the qdivrem() function,
 
496
             * its source code is about 170 lines of the code.
 
497
             * The glibc counterpart is about 150 lines of the code.
 
498
             *
 
499
             * For 32-bit numbers and some divisors gcc and icc use
 
500
             * a inlined multiplication and shifts.  For example,
 
501
             * unsigned "i32 / 10" is compiled to
 
502
             *
 
503
             *     (i32 * 0xCCCCCCCD) >> 35
 
504
             */
 
505
 
 
506
            ui32 = (uint32_t) ui64;
 
507
 
 
508
            do {
 
509
                *--p = (u_char) (ui32 % 10 + '0');
 
510
            } while (ui32 /= 10);
 
511
 
 
512
        } else {
 
513
            do {
 
514
                *--p = (u_char) (ui64 % 10 + '0');
 
515
            } while (ui64 /= 10);
 
516
        }
 
517
 
 
518
    } else if (hexadecimal == 1) {
 
519
 
 
520
        do {
 
521
 
 
522
            /* the "(uint32_t)" cast disables the BCC's warning */
 
523
            *--p = hex[(uint32_t) (ui64 & 0xf)];
 
524
 
 
525
        } while (ui64 >>= 4);
 
526
 
 
527
    } else { /* hexadecimal == 2 */
 
528
 
 
529
        do {
 
530
 
 
531
            /* the "(uint32_t)" cast disables the BCC's warning */
 
532
            *--p = HEX[(uint32_t) (ui64 & 0xf)];
 
533
 
 
534
        } while (ui64 >>= 4);
 
535
    }
 
536
 
 
537
    /* zero or space padding */
 
538
 
 
539
    len = (temp + NGX_INT64_LEN) - p;
 
540
 
 
541
    while (len++ < width && buf < last) {
 
542
        *buf++ = zero;
 
543
    }
 
544
 
 
545
    /* number safe copy */
 
546
 
 
547
    len = (temp + NGX_INT64_LEN) - p;
 
548
 
 
549
    if (buf + len > last) {
 
550
        len = last - buf;
 
551
    }
 
552
 
 
553
    return ngx_cpymem(buf, p, len);
 
554
}
 
555
 
 
556
 
459
557
/*
460
558
 * We use ngx_strcasecmp()/ngx_strncasecmp() for 7-bit ASCII strings only,
461
559
 * and implement our own ngx_strcasecmp()/ngx_strncasecmp()
472
570
        c1 = (ngx_uint_t) *s1++;
473
571
        c2 = (ngx_uint_t) *s2++;
474
572
 
475
 
        c1  = (c1 >= 'A' && c1 <= 'Z') ? (c1 | 0x20) : c1;
476
 
        c2  = (c2 >= 'A' && c2 <= 'Z') ? (c2 | 0x20) : c2;
 
573
        c1 = (c1 >= 'A' && c1 <= 'Z') ? (c1 | 0x20) : c1;
 
574
        c2 = (c2 >= 'A' && c2 <= 'Z') ? (c2 | 0x20) : c2;
477
575
 
478
576
        if (c1 == c2) {
479
577
 
498
596
        c1 = (ngx_uint_t) *s1++;
499
597
        c2 = (ngx_uint_t) *s2++;
500
598
 
501
 
        c1  = (c1 >= 'A' && c1 <= 'Z') ? (c1 | 0x20) : c1;
502
 
        c2  = (c2 >= 'A' && c2 <= 'Z') ? (c2 | 0x20) : c2;
 
599
        c1 = (c1 >= 'A' && c1 <= 'Z') ? (c1 | 0x20) : c1;
 
600
        c2 = (c2 >= 'A' && c2 <= 'Z') ? (c2 | 0x20) : c2;
503
601
 
504
602
        if (c1 == c2) {
505
603
 
587
685
    ngx_uint_t  c1, c2;
588
686
 
589
687
    c2 = (ngx_uint_t) *s2++;
590
 
    c2  = (c2 >= 'A' && c2 <= 'Z') ? (c2 | 0x20) : c2;
 
688
    c2 = (c2 >= 'A' && c2 <= 'Z') ? (c2 | 0x20) : c2;
591
689
 
592
690
    do {
593
691
        do {
597
695
                return NULL;
598
696
            }
599
697
 
600
 
            c1  = (c1 >= 'A' && c1 <= 'Z') ? (c1 | 0x20) : c1;
 
698
            c1 = (c1 >= 'A' && c1 <= 'Z') ? (c1 | 0x20) : c1;
601
699
 
602
700
        } while (c1 != c2);
603
701
 
607
705
}
608
706
 
609
707
 
 
708
/*
 
709
 * ngx_strlcasestrn() is intended to search for static substring
 
710
 * with known length in string until the argument last. The argument n
 
711
 * must be length of the second substring - 1.
 
712
 */
 
713
 
 
714
u_char *
 
715
ngx_strlcasestrn(u_char *s1, u_char *last, u_char *s2, size_t n)
 
716
{
 
717
    ngx_uint_t  c1, c2;
 
718
 
 
719
    c2 = (ngx_uint_t) *s2++;
 
720
    c2 = (c2 >= 'A' && c2 <= 'Z') ? (c2 | 0x20) : c2;
 
721
    last -= n;
 
722
 
 
723
    do {
 
724
        do {
 
725
            if (s1 >= last) {
 
726
                return NULL;
 
727
            }
 
728
 
 
729
            c1 = (ngx_uint_t) *s1++;
 
730
 
 
731
            c1 = (c1 >= 'A' && c1 <= 'Z') ? (c1 | 0x20) : c1;
 
732
 
 
733
        } while (c1 != c2);
 
734
 
 
735
    } while (ngx_strncasecmp(s1, s2, n) != 0);
 
736
 
 
737
    return --s1;
 
738
}
 
739
 
 
740
 
610
741
ngx_int_t
611
742
ngx_rstrncmp(u_char *s1, u_char *s2, size_t n)
612
743
{
691
822
 
692
823
 
693
824
ngx_int_t
 
825
ngx_dns_strcmp(u_char *s1, u_char *s2)
 
826
{
 
827
    ngx_uint_t  c1, c2;
 
828
 
 
829
    for ( ;; ) {
 
830
        c1 = (ngx_uint_t) *s1++;
 
831
        c2 = (ngx_uint_t) *s2++;
 
832
 
 
833
        c1 = (c1 >= 'A' && c1 <= 'Z') ? (c1 | 0x20) : c1;
 
834
        c2 = (c2 >= 'A' && c2 <= 'Z') ? (c2 | 0x20) : c2;
 
835
 
 
836
        if (c1 == c2) {
 
837
 
 
838
            if (c1) {
 
839
                continue;
 
840
            }
 
841
 
 
842
            return 0;
 
843
        }
 
844
 
 
845
        /* in ASCII '.' > '-', but we need '.' to be the lowest character */
 
846
 
 
847
        c1 = (c1 == '.') ? ' ' : c1;
 
848
        c2 = (c2 == '.') ? ' ' : c2;
 
849
 
 
850
        return c1 - c2;
 
851
    }
 
852
}
 
853
 
 
854
 
 
855
ngx_int_t
694
856
ngx_atoi(u_char *line, size_t n)
695
857
{
696
858
    ngx_int_t  value;
716
878
}
717
879
 
718
880
 
 
881
/* parse a fixed point number, e.g., ngx_atofp("10.5", 4, 2) returns 1050 */
 
882
 
 
883
ngx_int_t
 
884
ngx_atofp(u_char *line, size_t n, size_t point)
 
885
{
 
886
    ngx_int_t   value;
 
887
    ngx_uint_t  dot;
 
888
 
 
889
    if (n == 0) {
 
890
        return NGX_ERROR;
 
891
    }
 
892
 
 
893
    dot = 0;
 
894
 
 
895
    for (value = 0; n--; line++) {
 
896
 
 
897
        if (point == 0) {
 
898
            return NGX_ERROR;
 
899
        }
 
900
 
 
901
        if (*line == '.') {
 
902
            if (dot) {
 
903
                return NGX_ERROR;
 
904
            }
 
905
 
 
906
            dot = 1;
 
907
            continue;
 
908
        }
 
909
 
 
910
        if (*line < '0' || *line > '9') {
 
911
            return NGX_ERROR;
 
912
        }
 
913
 
 
914
        value = value * 10 + (*line - '0');
 
915
        point -= dot;
 
916
    }
 
917
 
 
918
    while (point--) {
 
919
        value = value * 10;
 
920
    }
 
921
 
 
922
    if (value < 0) {
 
923
        return NGX_ERROR;
 
924
 
 
925
    } else {
 
926
        return value;
 
927
    }
 
928
}
 
929
 
 
930
 
719
931
ssize_t
720
932
ngx_atosz(u_char *line, size_t n)
721
933
{
889
1101
ngx_int_t
890
1102
ngx_decode_base64(ngx_str_t *dst, ngx_str_t *src)
891
1103
{
892
 
    size_t          len;
893
 
    u_char         *d, *s;
894
1104
    static u_char   basis64[] = {
895
1105
        77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
896
1106
        77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
911
1121
        77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77
912
1122
    };
913
1123
 
 
1124
    return ngx_decode_base64_internal(dst, src, basis64);
 
1125
}
 
1126
 
 
1127
 
 
1128
ngx_int_t
 
1129
ngx_decode_base64url(ngx_str_t *dst, ngx_str_t *src)
 
1130
{
 
1131
    static u_char   basis64[] = {
 
1132
        77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
 
1133
        77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
 
1134
        77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 62, 77, 77,
 
1135
        52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 77, 77, 77, 77, 77, 77,
 
1136
        77,  0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14,
 
1137
        15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 77, 77, 77, 77, 63,
 
1138
        77, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
 
1139
        41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 77, 77, 77, 77, 77,
 
1140
 
 
1141
        77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
 
1142
        77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
 
1143
        77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
 
1144
        77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
 
1145
        77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
 
1146
        77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
 
1147
        77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
 
1148
        77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77
 
1149
    };
 
1150
 
 
1151
    return ngx_decode_base64_internal(dst, src, basis64);
 
1152
}
 
1153
 
 
1154
 
 
1155
static ngx_int_t
 
1156
ngx_decode_base64_internal(ngx_str_t *dst, ngx_str_t *src, const u_char *basis)
 
1157
{
 
1158
    size_t          len;
 
1159
    u_char         *d, *s;
 
1160
 
914
1161
    for (len = 0; len < src->len; len++) {
915
1162
        if (src->data[len] == '=') {
916
1163
            break;
917
1164
        }
918
1165
 
919
 
        if (basis64[src->data[len]] == 77) {
 
1166
        if (basis[src->data[len]] == 77) {
920
1167
            return NGX_ERROR;
921
1168
        }
922
1169
    }
929
1176
    d = dst->data;
930
1177
 
931
1178
    while (len > 3) {
932
 
        *d++ = (u_char) (basis64[s[0]] << 2 | basis64[s[1]] >> 4);
933
 
        *d++ = (u_char) (basis64[s[1]] << 4 | basis64[s[2]] >> 2);
934
 
        *d++ = (u_char) (basis64[s[2]] << 6 | basis64[s[3]]);
 
1179
        *d++ = (u_char) (basis[s[0]] << 2 | basis[s[1]] >> 4);
 
1180
        *d++ = (u_char) (basis[s[1]] << 4 | basis[s[2]] >> 2);
 
1181
        *d++ = (u_char) (basis[s[2]] << 6 | basis[s[3]]);
935
1182
 
936
1183
        s += 4;
937
1184
        len -= 4;
938
1185
    }
939
1186
 
940
1187
    if (len > 1) {
941
 
        *d++ = (u_char) (basis64[s[0]] << 2 | basis64[s[1]] >> 4);
 
1188
        *d++ = (u_char) (basis[s[0]] << 2 | basis[s[1]] >> 4);
942
1189
    }
943
1190
 
944
1191
    if (len > 2) {
945
 
        *d++ = (u_char) (basis64[s[1]] << 4 | basis64[s[2]] >> 2);
 
1192
        *d++ = (u_char) (basis[s[1]] << 4 | basis[s[2]] >> 2);
946
1193
    }
947
1194
 
948
1195
    dst->len = d - dst->data;
952
1199
 
953
1200
 
954
1201
/*
955
 
 * ngx_utf_decode() decodes two and more bytes UTF sequences only
 
1202
 * ngx_utf8_decode() decodes two and more bytes UTF sequences only
956
1203
 * the return values:
957
1204
 *    0x80 - 0x10ffff         valid character
958
 
 *    0x10ffff - 0xfffffffd   invalid sequence
 
1205
 *    0x110000 - 0xfffffffd   invalid sequence
959
1206
 *    0xfffffffe              incomplete sequence
960
1207
 *    0xffffffff              error
961
1208
 */
962
1209
 
963
1210
uint32_t
964
 
ngx_utf_decode(u_char **p, size_t n)
 
1211
ngx_utf8_decode(u_char **p, size_t n)
965
1212
{
966
1213
    size_t    len;
967
1214
    uint32_t  u, i, valid;
968
1215
 
969
1216
    u = **p;
970
1217
 
971
 
    if (u > 0xf0) {
 
1218
    if (u >= 0xf0) {
972
1219
 
973
1220
        u &= 0x07;
974
1221
        valid = 0xffff;
975
1222
        len = 3;
976
1223
 
977
 
    } else if (u > 0xe0) {
 
1224
    } else if (u >= 0xe0) {
978
1225
 
979
1226
        u &= 0x0f;
980
1227
        valid = 0x7ff;
981
1228
        len = 2;
982
1229
 
983
 
    } else if (u > 0xc0) {
 
1230
    } else if (u >= 0xc2) {
984
1231
 
985
1232
        u &= 0x1f;
986
1233
        valid = 0x7f;
1018
1265
 
1019
1266
 
1020
1267
size_t
1021
 
ngx_utf_length(u_char *p, size_t n)
 
1268
ngx_utf8_length(u_char *p, size_t n)
1022
1269
{
1023
 
    u_char      c;
1024
 
    size_t      len;
1025
 
    ngx_uint_t  i;
1026
 
 
1027
 
    for (len = 0, i = 0; i < n; len++, i++) {
1028
 
 
1029
 
        c = p[i];
 
1270
    u_char  c, *last;
 
1271
    size_t  len;
 
1272
 
 
1273
    last = p + n;
 
1274
 
 
1275
    for (len = 0; p < last; len++) {
 
1276
 
 
1277
        c = *p;
1030
1278
 
1031
1279
        if (c < 0x80) {
1032
 
            continue;
1033
 
        }
1034
 
 
1035
 
        if (c >= 0xc0) {
1036
 
            for (c <<= 1; c & 0x80; c <<= 1) {
1037
 
                i++;
1038
 
            }
1039
 
 
1040
 
            continue;
1041
 
        }
1042
 
 
1043
 
        /* invalid utf */
1044
 
 
1045
 
        return n;
 
1280
            p++;
 
1281
            continue;
 
1282
        }
 
1283
 
 
1284
        if (ngx_utf8_decode(&p, n) > 0x10ffff) {
 
1285
            /* invalid UTF-8 */
 
1286
            return n;
 
1287
        }
1046
1288
    }
1047
1289
 
1048
1290
    return len;
1050
1292
 
1051
1293
 
1052
1294
u_char *
1053
 
ngx_utf_cpystrn(u_char *dst, u_char *src, size_t n)
 
1295
ngx_utf8_cpystrn(u_char *dst, u_char *src, size_t n, size_t len)
1054
1296
{
1055
 
    u_char  c;
 
1297
    u_char  c, *next;
1056
1298
 
1057
1299
    if (n == 0) {
1058
1300
        return dst;
1059
1301
    }
1060
1302
 
1061
 
    for ( /* void */ ; --n; dst++, src++) {
 
1303
    while (--n) {
1062
1304
 
1063
1305
        c = *src;
1064
1306
        *dst = c;
1065
1307
 
1066
1308
        if (c < 0x80) {
1067
 
            if (*dst != '\0') {
 
1309
 
 
1310
            if (c != '\0') {
 
1311
                dst++;
 
1312
                src++;
 
1313
                len--;
 
1314
 
1068
1315
                continue;
1069
1316
            }
1070
1317
 
1071
1318
            return dst;
1072
1319
        }
1073
1320
 
1074
 
        if (c >= 0xc0) {
1075
 
            for (c <<= 1; c & 0x80; c <<= 1) {
1076
 
               *++dst = *++src;
1077
 
            }
1078
 
 
1079
 
            continue;
1080
 
        }
1081
 
 
1082
 
        /* invalid utf */
 
1321
        next = src;
 
1322
 
 
1323
        if (ngx_utf8_decode(&next, len) > 0x10ffff) {
 
1324
            /* invalid UTF-8 */
 
1325
            break;
 
1326
        }
 
1327
 
 
1328
        while (src < next) {
 
1329
            *dst++ = *src++;
 
1330
            len--;
 
1331
        }
1083
1332
    }
1084
1333
 
1085
1334
    *dst = '\0';
1091
1340
uintptr_t
1092
1341
ngx_escape_uri(u_char *dst, u_char *src, size_t size, ngx_uint_t type)
1093
1342
{
1094
 
    ngx_uint_t      i, n;
 
1343
    ngx_uint_t      n;
1095
1344
    uint32_t       *escape;
1096
1345
    static u_char   hex[] = "0123456789abcdef";
1097
1346
 
1115
1364
        0xffffffff  /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1116
1365
    };
1117
1366
 
1118
 
                    /* " ", "#", "%", "+", "?", %00-%1F, %7F-%FF */
 
1367
                    /* " ", "#", "%", "&", "+", "?", %00-%1F, %7F-%FF */
1119
1368
 
1120
1369
    static uint32_t   args[] = {
1121
1370
        0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1122
1371
 
1123
1372
                    /* ?>=< ;:98 7654 3210  /.-, +*)( '&%$ #"!  */
1124
 
        0x80000829, /* 1000 0000 0000 0000  0000 1000 0010 1001 */
 
1373
        0x88000869, /* 1000 1000 0000 0000  0000 1000 0110 1001 */
1125
1374
 
1126
1375
                    /* _^]\ [ZYX WVUT SRQP  ONML KJIH GFED CBA@ */
1127
1376
        0x00000000, /* 0000 0000 0000 0000  0000 0000 0000 0000 */
1135
1384
        0xffffffff  /* 1111 1111 1111 1111  1111 1111 1111 1111 */
1136
1385
    };
1137
1386
 
 
1387
                    /* not ALPHA, DIGIT, "-", ".", "_", "~" */
 
1388
 
 
1389
    static uint32_t   uri_component[] = {
 
1390
        0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
 
1391
 
 
1392
                    /* ?>=< ;:98 7654 3210  /.-, +*)( '&%$ #"!  */
 
1393
        0xfc009fff, /* 1111 1100 0000 0000  1001 1111 1111 1111 */
 
1394
 
 
1395
                    /* _^]\ [ZYX WVUT SRQP  ONML KJIH GFED CBA@ */
 
1396
        0x78000001, /* 0111 1000 0000 0000  0000 0000 0000 0001 */
 
1397
 
 
1398
                    /*  ~}| {zyx wvut srqp  onml kjih gfed cba` */
 
1399
        0xb8000001, /* 1011 1000 0000 0000  0000 0000 0000 0001 */
 
1400
 
 
1401
        0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
 
1402
        0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
 
1403
        0xffffffff, /* 1111 1111 1111 1111  1111 1111 1111 1111 */
 
1404
        0xffffffff  /* 1111 1111 1111 1111  1111 1111 1111 1111 */
 
1405
    };
 
1406
 
1138
1407
                    /* " ", "#", """, "%", "'", %00-%1F, %7F-%FF */
1139
1408
 
1140
1409
    static uint32_t   html[] = {
1198
1467
                    /* mail_auth is the same as memcached */
1199
1468
 
1200
1469
    static uint32_t  *map[] =
1201
 
        { uri, args, html, refresh, memcached, memcached };
 
1470
        { uri, args, uri_component, html, refresh, memcached, memcached };
1202
1471
 
1203
1472
 
1204
1473
    escape = map[type];
1207
1476
 
1208
1477
        /* find the number of the characters to be escaped */
1209
1478
 
1210
 
        n  = 0;
 
1479
        n = 0;
1211
1480
 
1212
 
        for (i = 0; i < size; i++) {
 
1481
        while (size) {
1213
1482
            if (escape[*src >> 5] & (1 << (*src & 0x1f))) {
1214
1483
                n++;
1215
1484
            }
1216
1485
            src++;
 
1486
            size--;
1217
1487
        }
1218
1488
 
1219
1489
        return (uintptr_t) n;
1220
1490
    }
1221
1491
 
1222
 
    for (i = 0; i < size; i++) {
 
1492
    while (size) {
1223
1493
        if (escape[*src >> 5] & (1 << (*src & 0x1f))) {
1224
1494
            *dst++ = '%';
1225
1495
            *dst++ = hex[*src >> 4];
1229
1499
        } else {
1230
1500
            *dst++ = *src++;
1231
1501
        }
 
1502
        size--;
1232
1503
    }
1233
1504
 
1234
1505
    return (uintptr_t) dst;
1369
1640
ngx_escape_html(u_char *dst, u_char *src, size_t size)
1370
1641
{
1371
1642
    u_char      ch;
1372
 
    ngx_uint_t  i, len;
 
1643
    ngx_uint_t  len;
1373
1644
 
1374
1645
    if (dst == NULL) {
1375
1646
 
1376
1647
        len = 0;
1377
1648
 
1378
 
        for (i = 0; i < size; i++) {
 
1649
        while (size) {
1379
1650
            switch (*src++) {
1380
1651
 
1381
1652
            case '<':
1390
1661
                len += sizeof("&amp;") - 2;
1391
1662
                break;
1392
1663
 
 
1664
            case '"':
 
1665
                len += sizeof("&quot;") - 2;
 
1666
                break;
 
1667
 
1393
1668
            default:
1394
1669
                break;
1395
1670
            }
 
1671
            size--;
1396
1672
        }
1397
1673
 
1398
1674
        return (uintptr_t) len;
1399
1675
    }
1400
1676
 
1401
 
    for (i = 0; i < size; i++) {
 
1677
    while (size) {
1402
1678
        ch = *src++;
1403
1679
 
1404
1680
        switch (ch) {
1416
1692
            *dst++ = ';';
1417
1693
            break;
1418
1694
 
 
1695
        case '"':
 
1696
            *dst++ = '&'; *dst++ = 'q'; *dst++ = 'u'; *dst++ = 'o';
 
1697
            *dst++ = 't'; *dst++ = ';';
 
1698
            break;
 
1699
 
1419
1700
        default:
1420
1701
            *dst++ = ch;
1421
1702
            break;
1422
1703
        }
 
1704
        size--;
1423
1705
    }
1424
1706
 
1425
1707
    return (uintptr_t) dst;
1426
1708
}
1427
1709
 
1428
1710
 
 
1711
void
 
1712
ngx_str_rbtree_insert_value(ngx_rbtree_node_t *temp,
 
1713
    ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel)
 
1714
{
 
1715
    ngx_str_node_t      *n, *t;
 
1716
    ngx_rbtree_node_t  **p;
 
1717
 
 
1718
    for ( ;; ) {
 
1719
 
 
1720
        n = (ngx_str_node_t *) node;
 
1721
        t = (ngx_str_node_t *) temp;
 
1722
 
 
1723
        if (node->key != temp->key) {
 
1724
 
 
1725
            p = (node->key < temp->key) ? &temp->left : &temp->right;
 
1726
 
 
1727
        } else if (n->str.len != t->str.len) {
 
1728
 
 
1729
            p = (n->str.len < t->str.len) ? &temp->left : &temp->right;
 
1730
 
 
1731
        } else {
 
1732
            p = (ngx_memcmp(n->str.data, t->str.data, n->str.len) < 0)
 
1733
                 ? &temp->left : &temp->right;
 
1734
        }
 
1735
 
 
1736
        if (*p == sentinel) {
 
1737
            break;
 
1738
        }
 
1739
 
 
1740
        temp = *p;
 
1741
    }
 
1742
 
 
1743
    *p = node;
 
1744
    node->parent = temp;
 
1745
    node->left = sentinel;
 
1746
    node->right = sentinel;
 
1747
    ngx_rbt_red(node);
 
1748
}
 
1749
 
 
1750
 
 
1751
ngx_str_node_t *
 
1752
ngx_str_rbtree_lookup(ngx_rbtree_t *rbtree, ngx_str_t *val, uint32_t hash)
 
1753
{
 
1754
    ngx_int_t           rc;
 
1755
    ngx_str_node_t     *n;
 
1756
    ngx_rbtree_node_t  *node, *sentinel;
 
1757
 
 
1758
    node = rbtree->root;
 
1759
    sentinel = rbtree->sentinel;
 
1760
 
 
1761
    while (node != sentinel) {
 
1762
 
 
1763
        n = (ngx_str_node_t *) node;
 
1764
 
 
1765
        if (hash != node->key) {
 
1766
            node = (hash < node->key) ? node->left : node->right;
 
1767
            continue;
 
1768
        }
 
1769
 
 
1770
        if (val->len != n->str.len) {
 
1771
            node = (val->len < n->str.len) ? node->left : node->right;
 
1772
            continue;
 
1773
        }
 
1774
 
 
1775
        rc = ngx_memcmp(val->data, n->str.data, val->len);
 
1776
 
 
1777
        if (rc < 0) {
 
1778
            node = node->left;
 
1779
            continue;
 
1780
        }
 
1781
 
 
1782
        if (rc > 0) {
 
1783
            node = node->right;
 
1784
            continue;
 
1785
        }
 
1786
 
 
1787
        return n;
 
1788
    }
 
1789
 
 
1790
    return NULL;
 
1791
}
 
1792
 
 
1793
 
1429
1794
/* ngx_sort() is implemented as insertion sort because we need stable sort */
1430
1795
 
1431
1796
void
1462
1827
#if (NGX_MEMCPY_LIMIT)
1463
1828
 
1464
1829
void *
1465
 
ngx_memcpy(void *dst, void *src, size_t n)
 
1830
ngx_memcpy(void *dst, const void *src, size_t n)
1466
1831
{
1467
1832
    if (n > NGX_MEMCPY_LIMIT) {
1468
1833
        ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "memcpy %uz bytes", n);