xref: /unit/src/nxt_http_parse.c (revision 1270:9efa309be18b)
1 
2 /*
3  * Copyright (C) NGINX, Inc.
4  * Copyright (C) Valentin V. Bartenev
5  */
6 
7 #include <nxt_main.h>
8 
9 
10 static nxt_int_t nxt_http_parse_unusual_target(nxt_http_request_parse_t *rp,
11     u_char **pos, u_char *end);
12 static nxt_int_t nxt_http_parse_request_line(nxt_http_request_parse_t *rp,
13     u_char **pos, u_char *end);
14 static nxt_int_t nxt_http_parse_field_name(nxt_http_request_parse_t *rp,
15     u_char **pos, u_char *end);
16 static nxt_int_t nxt_http_parse_field_value(nxt_http_request_parse_t *rp,
17     u_char **pos, u_char *end);
18 static u_char *nxt_http_lookup_field_end(u_char *p, u_char *end);
19 static nxt_int_t nxt_http_parse_field_end(nxt_http_request_parse_t *rp,
20     u_char **pos, u_char *end);
21 
22 static nxt_int_t nxt_http_parse_complex_target(nxt_http_request_parse_t *rp);
23 
24 static nxt_int_t nxt_http_field_hash_test(nxt_lvlhsh_query_t *lhq, void *data);
25 static void *nxt_http_field_hash_alloc(void *pool, size_t size);
26 static void nxt_http_field_hash_free(void *pool, void *p);
27 
28 static nxt_int_t nxt_http_field_hash_collision(nxt_lvlhsh_query_t *lhq,
29     void *data);
30 
31 
32 #define NXT_HTTP_MAX_FIELD_NAME         0xFF
33 #define NXT_HTTP_MAX_FIELD_VALUE        NXT_INT32_T_MAX
34 
35 #define NXT_HTTP_FIELD_LVLHSH_SHIFT     5
36 
37 
38 typedef enum {
39     NXT_HTTP_TARGET_SPACE = 1,   /* \s  */
40     NXT_HTTP_TARGET_HASH,        /*  #  */
41     NXT_HTTP_TARGET_AGAIN,
42     NXT_HTTP_TARGET_BAD,         /* \0\r\n */
43 
44     /* traps below are used for extended check only */
45 
46     NXT_HTTP_TARGET_SLASH = 5,   /*  /  */
47     NXT_HTTP_TARGET_DOT,         /*  .  */
48     NXT_HTTP_TARGET_ARGS_MARK,   /*  ?  */
49     NXT_HTTP_TARGET_QUOTE_MARK,  /*  %  */
50 } nxt_http_target_traps_e;
51 
52 
53 static const uint8_t  nxt_http_target_chars[256] nxt_aligned(64) = {
54     /* \0                               \n        \r       */
55         4, 0, 0, 0,  0, 0, 0, 0,   0, 0, 4, 0,  0, 4, 0, 0,
56         0, 0, 0, 0,  0, 0, 0, 0,   0, 0, 0, 0,  0, 0, 0, 0,
57 
58     /* \s  !  "  #   $  %  &  '    (  )  *  +   ,  -  .  / */
59         1, 0, 0, 2,  0, 8, 0, 0,   0, 0, 0, 0,  0, 0, 6, 5,
60 
61     /*  0  1  2  3   4  5  6  7    8  9  :  ;   <  =  >  ? */
62         0, 0, 0, 0,  0, 0, 0, 0,   0, 0, 0, 0,  0, 0, 0, 7,
63 };
64 
65 
66 nxt_inline nxt_http_target_traps_e
67 nxt_http_parse_target(u_char **pos, u_char *end)
68 {
69     u_char      *p;
70     nxt_uint_t  trap;
71 
72     p = *pos;
73 
74     while (nxt_fast_path(end - p >= 10)) {
75 
76 #define nxt_target_test_char(ch)                                              \
77                                                                               \
78         trap = nxt_http_target_chars[ch];                                     \
79                                                                               \
80         if (nxt_slow_path(trap != 0)) {                                       \
81             *pos = &(ch);                                                     \
82             return trap;                                                      \
83         }
84 
85 /* enddef */
86 
87         nxt_target_test_char(p[0]);
88         nxt_target_test_char(p[1]);
89         nxt_target_test_char(p[2]);
90         nxt_target_test_char(p[3]);
91 
92         nxt_target_test_char(p[4]);
93         nxt_target_test_char(p[5]);
94         nxt_target_test_char(p[6]);
95         nxt_target_test_char(p[7]);
96 
97         nxt_target_test_char(p[8]);
98         nxt_target_test_char(p[9]);
99 
100         p += 10;
101     }
102 
103     while (p != end) {
104         nxt_target_test_char(*p); p++;
105     }
106 
107     return NXT_HTTP_TARGET_AGAIN;
108 }
109 
110 
111 nxt_int_t
112 nxt_http_parse_request_init(nxt_http_request_parse_t *rp, nxt_mp_t *mp)
113 {
114     rp->mem_pool = mp;
115 
116     rp->fields = nxt_list_create(mp, 8, sizeof(nxt_http_field_t));
117     if (nxt_slow_path(rp->fields == NULL)) {
118         return NXT_ERROR;
119     }
120 
121     rp->field_hash = NXT_HTTP_FIELD_HASH_INIT;
122 
123     return NXT_OK;
124 }
125 
126 
127 nxt_int_t
128 nxt_http_parse_request(nxt_http_request_parse_t *rp, nxt_buf_mem_t *b)
129 {
130     nxt_int_t  rc;
131 
132     if (rp->handler == NULL) {
133         rp->handler = &nxt_http_parse_request_line;
134     }
135 
136     do {
137         rc = rp->handler(rp, &b->pos, b->free);
138     } while (rc == NXT_OK);
139 
140     return rc;
141 }
142 
143 
144 nxt_int_t
145 nxt_http_parse_fields(nxt_http_request_parse_t *rp, nxt_buf_mem_t *b)
146 {
147     nxt_int_t  rc;
148 
149     if (rp->handler == NULL) {
150         rp->handler = &nxt_http_parse_field_name;
151     }
152 
153     do {
154         rc = rp->handler(rp, &b->pos, b->free);
155     } while (rc == NXT_OK);
156 
157     return rc;
158 }
159 
160 
161 static nxt_int_t
162 nxt_http_parse_request_line(nxt_http_request_parse_t *rp, u_char **pos,
163     u_char *end)
164 {
165     u_char                   *p, ch, *after_slash, *args;
166     nxt_int_t                rc;
167     nxt_bool_t               rest;
168     nxt_http_ver_t           ver;
169     nxt_http_target_traps_e  trap;
170 
171     static const nxt_http_ver_t  http11 = { "HTTP/1.1" };
172     static const nxt_http_ver_t  http10 = { "HTTP/1.0" };
173 
174     p = *pos;
175 
176     rp->method.start = p;
177 
178     for ( ;; ) {
179 
180         while (nxt_fast_path(end - p >= 8)) {
181 
182 #define nxt_method_test_char(ch)                                              \
183                                                                               \
184             if (nxt_slow_path((ch) < 'A' || (ch) > 'Z')) {                    \
185                 p = &(ch);                                                    \
186                 goto method_unusual_char;                                     \
187             }
188 
189 /* enddef */
190 
191             nxt_method_test_char(p[0]);
192             nxt_method_test_char(p[1]);
193             nxt_method_test_char(p[2]);
194             nxt_method_test_char(p[3]);
195 
196             nxt_method_test_char(p[4]);
197             nxt_method_test_char(p[5]);
198             nxt_method_test_char(p[6]);
199             nxt_method_test_char(p[7]);
200 
201             p += 8;
202         }
203 
204         while (p != end) {
205             nxt_method_test_char(*p); p++;
206         }
207 
208         rp->method.length = p - rp->method.start;
209 
210         return NXT_AGAIN;
211 
212     method_unusual_char:
213 
214         ch = *p;
215 
216         if (nxt_fast_path(ch == ' ')) {
217             rp->method.length = p - rp->method.start;
218             break;
219         }
220 
221         if (ch == '_' || ch == '-') {
222             p++;
223             continue;
224         }
225 
226         if (rp->method.start == p && (ch == '\r' || ch == '\n')) {
227             rp->method.start++;
228             p++;
229             continue;
230         }
231 
232         rp->method.length = p - rp->method.start;
233 
234         return NXT_HTTP_PARSE_INVALID;
235     }
236 
237     p++;
238 
239     if (nxt_slow_path(p == end)) {
240         return NXT_AGAIN;
241     }
242 
243     /* target */
244 
245     ch = *p;
246 
247     if (nxt_slow_path(ch != '/')) {
248         rc = nxt_http_parse_unusual_target(rp, &p, end);
249 
250         if (nxt_slow_path(rc != NXT_OK)) {
251             return rc;
252         }
253     }
254 
255     rp->target_start = p;
256 
257     after_slash = p + 1;
258     args = NULL;
259     rest = 0;
260 
261 continue_target:
262 
263     for ( ;; ) {
264         p++;
265 
266         trap = nxt_http_parse_target(&p, end);
267 
268         switch (trap) {
269         case NXT_HTTP_TARGET_SLASH:
270             if (nxt_slow_path(after_slash == p)) {
271                 rp->complex_target = 1;
272                 goto rest_of_target;
273             }
274 
275             after_slash = p + 1;
276             continue;
277 
278         case NXT_HTTP_TARGET_DOT:
279             if (nxt_slow_path(after_slash == p)) {
280                 rp->complex_target = 1;
281                 goto rest_of_target;
282             }
283 
284             continue;
285 
286         case NXT_HTTP_TARGET_ARGS_MARK:
287             args = p + 1;
288             goto rest_of_target;
289 
290         case NXT_HTTP_TARGET_SPACE:
291             rp->target_end = p;
292             goto space_after_target;
293 
294         case NXT_HTTP_TARGET_QUOTE_MARK:
295             rp->quoted_target = 1;
296             goto rest_of_target;
297 
298         case NXT_HTTP_TARGET_HASH:
299             rp->complex_target = 1;
300             goto rest_of_target;
301 
302         case NXT_HTTP_TARGET_AGAIN:
303             rp->target_end = p;
304             return NXT_AGAIN;
305 
306         case NXT_HTTP_TARGET_BAD:
307             rp->target_end = p;
308             return NXT_HTTP_PARSE_INVALID;
309         }
310 
311         nxt_unreachable();
312     }
313 
314 rest_of_target:
315 
316     rest = 1;
317 
318     for ( ;; ) {
319         p++;
320 
321         trap = nxt_http_parse_target(&p, end);
322 
323         switch (trap) {
324         case NXT_HTTP_TARGET_SPACE:
325             rp->target_end = p;
326             goto space_after_target;
327 
328         case NXT_HTTP_TARGET_HASH:
329             rp->complex_target = 1;
330             continue;
331 
332         case NXT_HTTP_TARGET_AGAIN:
333             rp->target_end = p;
334             return NXT_AGAIN;
335 
336         case NXT_HTTP_TARGET_BAD:
337             rp->target_end = p;
338             return NXT_HTTP_PARSE_INVALID;
339 
340         default:
341             continue;
342         }
343 
344         nxt_unreachable();
345     }
346 
347 space_after_target:
348 
349     if (nxt_slow_path(end - p < 10)) {
350 
351         do {
352             p++;
353 
354             if (p == end) {
355                 return NXT_AGAIN;
356             }
357 
358         } while (*p == ' ');
359 
360         if (nxt_memcmp(p, "HTTP/", nxt_min(end - p, 5)) == 0) {
361 
362             switch (end - p) {
363             case 8:
364                 if (p[7] < '0' || p[7] > '9') {
365                     break;
366                 }
367                 /* Fall through. */
368             case 7:
369                 if (p[6] != '.') {
370                     break;
371                 }
372                 /* Fall through. */
373             case 6:
374                 if (p[5] < '0' || p[5] > '9') {
375                     break;
376                 }
377                 /* Fall through. */
378             default:
379                 return NXT_AGAIN;
380             }
381         }
382 
383         rp->space_in_target = 1;
384 
385         if (rest) {
386             goto rest_of_target;
387         }
388 
389         goto continue_target;
390     }
391 
392     /* " HTTP/1.1\r\n" or " HTTP/1.1\n" */
393 
394     if (nxt_slow_path(p[9] != '\r' && p[9] != '\n')) {
395 
396         if (p[1] == ' ') {
397             /* surplus space after tartet */
398             p++;
399             goto space_after_target;
400         }
401 
402         rp->space_in_target = 1;
403 
404         if (rest) {
405             goto rest_of_target;
406         }
407 
408         goto continue_target;
409     }
410 
411     nxt_memcpy(ver.str, &p[1], 8);
412 
413     if (nxt_fast_path(ver.ui64 == http11.ui64
414                       || ver.ui64 == http10.ui64
415                       || (nxt_memcmp(ver.str, "HTTP/1.", 7) == 0
416                           && ver.s.minor >= '0' && ver.s.minor <= '9')))
417     {
418         rp->version.ui64 = ver.ui64;
419 
420         if (nxt_fast_path(p[9] == '\r')) {
421             p += 10;
422 
423             if (nxt_slow_path(p == end)) {
424                 return NXT_AGAIN;
425             }
426 
427             if (nxt_slow_path(*p != '\n')) {
428                 return NXT_HTTP_PARSE_INVALID;
429             }
430 
431             *pos = p + 1;
432 
433         } else {
434             *pos = p + 10;
435         }
436 
437         if (rp->complex_target != 0 || rp->quoted_target != 0) {
438             rc = nxt_http_parse_complex_target(rp);
439 
440             if (nxt_slow_path(rc != NXT_OK)) {
441                 return rc;
442             }
443 
444             return nxt_http_parse_field_name(rp, pos, end);
445         }
446 
447         rp->path.start = rp->target_start;
448 
449         if (args != NULL) {
450             rp->path.length = args - rp->target_start - 1;
451 
452             rp->args.length = rp->target_end - args;
453             rp->args.start = args;
454 
455         } else {
456             rp->path.length = rp->target_end - rp->target_start;
457         }
458 
459         return nxt_http_parse_field_name(rp, pos, end);
460     }
461 
462     if (nxt_memcmp(ver.s.prefix, "HTTP/", 5) == 0
463         && ver.s.major >= '0' && ver.s.major <= '9'
464         && ver.s.point == '.'
465         && ver.s.minor >= '0' && ver.s.minor <= '9')
466     {
467         rp->version.ui64 = ver.ui64;
468         return NXT_HTTP_PARSE_UNSUPPORTED_VERSION;
469     }
470 
471     return NXT_HTTP_PARSE_INVALID;
472 }
473 
474 
475 static nxt_int_t
476 nxt_http_parse_unusual_target(nxt_http_request_parse_t *rp, u_char **pos,
477     u_char *end)
478 {
479     u_char  *p, ch;
480 
481     p = *pos;
482 
483     ch = *p;
484 
485     if (ch == ' ') {
486         /* skip surplus spaces before target */
487 
488         do {
489             p++;
490 
491             if (nxt_slow_path(p == end)) {
492                 return NXT_AGAIN;
493             }
494 
495             ch = *p;
496 
497         } while (ch == ' ');
498 
499         if (ch == '/') {
500             *pos = p;
501             return NXT_OK;
502         }
503     }
504 
505     /* absolute path or '*' */
506 
507     /* TODO */
508 
509     return NXT_HTTP_PARSE_INVALID;
510 }
511 
512 
513 static nxt_int_t
514 nxt_http_parse_field_name(nxt_http_request_parse_t *rp, u_char **pos,
515     u_char *end)
516 {
517     u_char    *p, c;
518     size_t    len;
519     uint32_t  hash;
520 
521     static const u_char  normal[256]  nxt_aligned(64) =
522         "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"
523         "\0\0\0\0\0\0\0\0\0\0\0\0\0-\0\0" "0123456789\0\0\0\0\0\0"
524 
525         /* These 64 bytes should reside in one cache line. */
526         "\0abcdefghijklmnopqrstuvwxyz\0\0\0\0_"
527         "\0abcdefghijklmnopqrstuvwxyz\0\0\0\0\0"
528 
529         "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"
530         "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"
531         "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"
532         "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0";
533 
534     p = *pos + rp->field_name.length;
535     hash = rp->field_hash;
536 
537     while (nxt_fast_path(end - p >= 8)) {
538 
539 #define nxt_field_name_test_char(ch)                                          \
540                                                                               \
541         c = normal[ch];                                                       \
542                                                                               \
543         if (nxt_slow_path(c == '\0')) {                                       \
544             p = &(ch);                                                        \
545             goto name_end;                                                    \
546         }                                                                     \
547                                                                               \
548         hash = nxt_http_field_hash_char(hash, c);
549 
550 /* enddef */
551 
552         nxt_field_name_test_char(p[0]);
553         nxt_field_name_test_char(p[1]);
554         nxt_field_name_test_char(p[2]);
555         nxt_field_name_test_char(p[3]);
556 
557         nxt_field_name_test_char(p[4]);
558         nxt_field_name_test_char(p[5]);
559         nxt_field_name_test_char(p[6]);
560         nxt_field_name_test_char(p[7]);
561 
562         p += 8;
563     }
564 
565     while (nxt_fast_path(p != end)) {
566         nxt_field_name_test_char(*p); p++;
567     }
568 
569     len = p - *pos;
570 
571     if (nxt_slow_path(len > NXT_HTTP_MAX_FIELD_NAME)) {
572         return NXT_HTTP_PARSE_TOO_LARGE_FIELD;
573     }
574 
575     rp->field_hash = hash;
576     rp->field_name.length = len;
577 
578     rp->handler = &nxt_http_parse_field_name;
579 
580     return NXT_AGAIN;
581 
582 name_end:
583 
584     if (nxt_fast_path(*p == ':')) {
585         if (nxt_slow_path(p == *pos)) {
586             return NXT_HTTP_PARSE_INVALID;
587         }
588 
589         len = p - *pos;
590 
591         if (nxt_slow_path(len > NXT_HTTP_MAX_FIELD_NAME)) {
592             return NXT_HTTP_PARSE_TOO_LARGE_FIELD;
593         }
594 
595         rp->field_hash = hash;
596 
597         rp->field_name.length = len;
598         rp->field_name.start = *pos;
599 
600         *pos = p + 1;
601 
602         return nxt_http_parse_field_value(rp, pos, end);
603     }
604 
605     if (nxt_slow_path(p != *pos)) {
606         return NXT_HTTP_PARSE_INVALID;
607     }
608 
609     return nxt_http_parse_field_end(rp, pos, end);
610 }
611 
612 
613 static nxt_int_t
614 nxt_http_parse_field_value(nxt_http_request_parse_t *rp, u_char **pos,
615     u_char *end)
616 {
617     u_char  *p, *start, ch;
618     size_t  len;
619 
620     p = *pos;
621 
622     for ( ;; ) {
623         if (nxt_slow_path(p == end)) {
624             *pos = p;
625             rp->handler = &nxt_http_parse_field_value;
626             return NXT_AGAIN;
627         }
628 
629         ch = *p;
630 
631         if (ch != ' ' && ch != '\t') {
632             break;
633         }
634 
635         p++;
636     }
637 
638     start = p;
639 
640     p += rp->field_value.length;
641 
642     for ( ;; ) {
643         p = nxt_http_lookup_field_end(p, end);
644 
645         if (nxt_slow_path(p == end)) {
646             *pos = start;
647 
648             len = p - start;
649 
650             if (nxt_slow_path(len > NXT_HTTP_MAX_FIELD_VALUE)) {
651                 return NXT_HTTP_PARSE_TOO_LARGE_FIELD;
652             }
653 
654             rp->field_value.length = len;
655             rp->handler = &nxt_http_parse_field_value;
656             return NXT_AGAIN;
657         }
658 
659         ch = *p;
660 
661         if (nxt_fast_path(ch == '\r' || ch == '\n')) {
662             break;
663         }
664 
665         if (ch != '\t') {
666             return NXT_HTTP_PARSE_INVALID;
667         }
668 
669         p++;
670     }
671 
672     *pos = p;
673 
674     if (nxt_fast_path(p != start)) {
675 
676         while (p[-1] == ' ' || p[-1] == '\t') {
677             p--;
678         }
679     }
680 
681     len = p - start;
682 
683     if (nxt_slow_path(len > NXT_HTTP_MAX_FIELD_VALUE)) {
684         return NXT_HTTP_PARSE_TOO_LARGE_FIELD;
685     }
686 
687     rp->field_value.length = len;
688     rp->field_value.start = start;
689 
690     return nxt_http_parse_field_end(rp, pos, end);
691 }
692 
693 
694 static u_char *
695 nxt_http_lookup_field_end(u_char *p, u_char *end)
696 {
697     while (nxt_fast_path(end - p >= 16)) {
698 
699 #define nxt_field_end_test_char(ch)                                           \
700                                                                               \
701         if (nxt_slow_path((ch) < 0x20)) {                                     \
702             return &(ch);                                                     \
703         }
704 
705 /* enddef */
706 
707         nxt_field_end_test_char(p[0]);
708         nxt_field_end_test_char(p[1]);
709         nxt_field_end_test_char(p[2]);
710         nxt_field_end_test_char(p[3]);
711 
712         nxt_field_end_test_char(p[4]);
713         nxt_field_end_test_char(p[5]);
714         nxt_field_end_test_char(p[6]);
715         nxt_field_end_test_char(p[7]);
716 
717         nxt_field_end_test_char(p[8]);
718         nxt_field_end_test_char(p[9]);
719         nxt_field_end_test_char(p[10]);
720         nxt_field_end_test_char(p[11]);
721 
722         nxt_field_end_test_char(p[12]);
723         nxt_field_end_test_char(p[13]);
724         nxt_field_end_test_char(p[14]);
725         nxt_field_end_test_char(p[15]);
726 
727         p += 16;
728     }
729 
730     while (nxt_fast_path(end - p >= 4)) {
731 
732         nxt_field_end_test_char(p[0]);
733         nxt_field_end_test_char(p[1]);
734         nxt_field_end_test_char(p[2]);
735         nxt_field_end_test_char(p[3]);
736 
737         p += 4;
738     }
739 
740     switch (end - p) {
741     case 3:
742         nxt_field_end_test_char(*p); p++;
743         /* Fall through. */
744     case 2:
745         nxt_field_end_test_char(*p); p++;
746         /* Fall through. */
747     case 1:
748         nxt_field_end_test_char(*p); p++;
749         /* Fall through. */
750     case 0:
751         break;
752     default:
753         nxt_unreachable();
754     }
755 
756     return p;
757 }
758 
759 
760 static nxt_int_t
761 nxt_http_parse_field_end(nxt_http_request_parse_t *rp, u_char **pos,
762     u_char *end)
763 {
764     u_char            *p;
765     nxt_http_field_t  *field;
766 
767     p = *pos;
768 
769     if (nxt_fast_path(*p == '\r')) {
770         p++;
771 
772         if (nxt_slow_path(p == end)) {
773             rp->handler = &nxt_http_parse_field_end;
774             return NXT_AGAIN;
775         }
776     }
777 
778     if (nxt_fast_path(*p == '\n')) {
779         *pos = p + 1;
780 
781         if (rp->field_name.length != 0) {
782             field = nxt_list_add(rp->fields);
783 
784             if (nxt_slow_path(field == NULL)) {
785                 return NXT_ERROR;
786             }
787 
788             field->hash = nxt_http_field_hash_end(rp->field_hash);
789             field->skip = 0;
790             field->hopbyhop = 0;
791 
792             field->name_length = rp->field_name.length;
793             field->value_length = rp->field_value.length;
794             field->name = rp->field_name.start;
795             field->value = rp->field_value.start;
796 
797             rp->field_hash = NXT_HTTP_FIELD_HASH_INIT;
798 
799             rp->field_name.length = 0;
800             rp->field_value.length = 0;
801 
802             rp->handler = &nxt_http_parse_field_name;
803             return NXT_OK;
804         }
805 
806         return NXT_DONE;
807     }
808 
809     return NXT_HTTP_PARSE_INVALID;
810 }
811 
812 
813 #define                                                                       \
814 nxt_http_is_normal(c)                                                         \
815     (nxt_fast_path((nxt_http_normal[c / 8] & (1 << (c & 7))) != 0))
816 
817 
818 static const uint8_t  nxt_http_normal[32]  nxt_aligned(32) = {
819 
820                              /*        \0   \r  \n                         */
821     0xFE, 0xDB, 0xFF, 0xFF,  /* 1111 1110  1101 1011  1111 1111  1111 1111 */
822 
823                              /* '&%$ #"!   /.-, |*)(  7654 3210  ?>=< ;:98 */
824     0xD6, 0x37, 0xFF, 0x7F,  /* 1101 0110  0011 0111  1111 1111  0111 1111 */
825 
826                              /* GFED CBA@  ONML KJIH  WVUT SRQP  _^]\ [ZYX */
827     0xFF, 0xFF, 0xFF, 0xFF,  /* 1111 1111  1111 1111  1111 1111  1111 1111 */
828 
829                              /* gfed cba`  onml kjih  wvut srqp   ~}| {zyx */
830     0xFF, 0xFF, 0xFF, 0xFF,  /* 1111 1111  1111 1111  1111 1111  1111 1111 */
831 
832     0xFF, 0xFF, 0xFF, 0xFF,  /* 1111 1111  1111 1111  1111 1111  1111 1111 */
833     0xFF, 0xFF, 0xFF, 0xFF,  /* 1111 1111  1111 1111  1111 1111  1111 1111 */
834     0xFF, 0xFF, 0xFF, 0xFF,  /* 1111 1111  1111 1111  1111 1111  1111 1111 */
835     0xFF, 0xFF, 0xFF, 0xFF,  /* 1111 1111  1111 1111  1111 1111  1111 1111 */
836 };
837 
838 
839 static nxt_int_t
840 nxt_http_parse_complex_target(nxt_http_request_parse_t *rp)
841 {
842     u_char  *p, *u, c, ch, high, *args;
843 
844     enum {
845         sw_normal = 0,
846         sw_slash,
847         sw_dot,
848         sw_dot_dot,
849         sw_quoted,
850         sw_quoted_second,
851     } state, saved_state;
852 
853     nxt_prefetch(nxt_http_normal);
854 
855     state = sw_normal;
856     saved_state = sw_normal;
857     p = rp->target_start;
858 
859     u = nxt_mp_alloc(rp->mem_pool, rp->target_end - p + 1);
860     if (nxt_slow_path(u == NULL)) {
861         return NXT_ERROR;
862     }
863 
864     rp->path.length = 0;
865     rp->path.start = u;
866 
867     high = '\0';
868     args = NULL;
869 
870     while (p < rp->target_end) {
871 
872         ch = *p++;
873 
874     again:
875 
876         switch (state) {
877 
878         case sw_normal:
879 
880             if (nxt_http_is_normal(ch)) {
881                 *u++ = ch;
882                 continue;
883             }
884 
885             switch (ch) {
886             case '/':
887                 state = sw_slash;
888                 *u++ = ch;
889                 continue;
890             case '%':
891                 saved_state = state;
892                 state = sw_quoted;
893                 continue;
894             case '?':
895                 args = p;
896                 goto args;
897             case '#':
898                 goto done;
899             default:
900                 *u++ = ch;
901                 continue;
902             }
903 
904             break;
905 
906         case sw_slash:
907 
908             if (nxt_http_is_normal(ch)) {
909                 state = sw_normal;
910                 *u++ = ch;
911                 continue;
912             }
913 
914             switch (ch) {
915             case '/':
916                 continue;
917             case '.':
918                 state = sw_dot;
919                 *u++ = ch;
920                 continue;
921             case '%':
922                 saved_state = state;
923                 state = sw_quoted;
924                 continue;
925             case '?':
926                 args = p;
927                 goto args;
928             case '#':
929                 goto done;
930             default:
931                 state = sw_normal;
932                 *u++ = ch;
933                 continue;
934             }
935 
936             break;
937 
938         case sw_dot:
939 
940             if (nxt_http_is_normal(ch)) {
941                 state = sw_normal;
942                 *u++ = ch;
943                 continue;
944             }
945 
946             switch (ch) {
947             case '/':
948                 state = sw_slash;
949                 u--;
950                 continue;
951             case '.':
952                 state = sw_dot_dot;
953                 *u++ = ch;
954                 continue;
955             case '%':
956                 saved_state = state;
957                 state = sw_quoted;
958                 continue;
959             case '?':
960                 u--;
961                 args = p;
962                 goto args;
963             case '#':
964                 u--;
965                 goto done;
966             default:
967                 state = sw_normal;
968                 *u++ = ch;
969                 continue;
970             }
971 
972             break;
973 
974         case sw_dot_dot:
975 
976             if (nxt_http_is_normal(ch)) {
977                 state = sw_normal;
978                 *u++ = ch;
979                 continue;
980             }
981 
982             switch (ch) {
983 
984             case '/':
985             case '?':
986             case '#':
987                 u -= 5;
988 
989                 for ( ;; ) {
990                     if (u < rp->path.start) {
991                         return NXT_HTTP_PARSE_INVALID;
992                     }
993 
994                     if (*u == '/') {
995                         u++;
996                         break;
997                     }
998 
999                     u--;
1000                 }
1001 
1002                 if (ch == '?') {
1003                     args = p;
1004                     goto args;
1005                 }
1006 
1007                 if (ch == '#') {
1008                     goto done;
1009                 }
1010 
1011                 state = sw_slash;
1012                 break;
1013 
1014             case '%':
1015                 saved_state = state;
1016                 state = sw_quoted;
1017                 continue;
1018 
1019             default:
1020                 state = sw_normal;
1021                 *u++ = ch;
1022                 continue;
1023             }
1024 
1025             break;
1026 
1027         case sw_quoted:
1028             rp->quoted_target = 1;
1029 
1030             if (ch >= '0' && ch <= '9') {
1031                 high = (u_char) (ch - '0');
1032                 state = sw_quoted_second;
1033                 continue;
1034             }
1035 
1036             c = (u_char) (ch | 0x20);
1037             if (c >= 'a' && c <= 'f') {
1038                 high = (u_char) (c - 'a' + 10);
1039                 state = sw_quoted_second;
1040                 continue;
1041             }
1042 
1043             return NXT_HTTP_PARSE_INVALID;
1044 
1045         case sw_quoted_second:
1046             if (ch >= '0' && ch <= '9') {
1047                 ch = (u_char) ((high << 4) + ch - '0');
1048 
1049                 if (ch == '%') {
1050                     state = sw_normal;
1051                     *u++ = '%';
1052 
1053                     if (rp->encoded_slashes) {
1054                         *u++ = '2';
1055                         *u++ = '5';
1056                     }
1057 
1058                     continue;
1059                 }
1060 
1061                 if (ch == '#') {
1062                     state = sw_normal;
1063                     *u++ = '#';
1064                     continue;
1065                 }
1066 
1067                 if (ch == '\0') {
1068                     return NXT_HTTP_PARSE_INVALID;
1069                 }
1070 
1071                 state = saved_state;
1072                 goto again;
1073             }
1074 
1075             c = (u_char) (ch | 0x20);
1076             if (c >= 'a' && c <= 'f') {
1077                 ch = (u_char) ((high << 4) + c - 'a' + 10);
1078 
1079                 if (ch == '?') {
1080                     state = sw_normal;
1081                     *u++ = ch;
1082                     continue;
1083                 }
1084 
1085                 if (ch == '/' && rp->encoded_slashes) {
1086                     state = sw_normal;
1087                     *u++ = '%';
1088                     *u++ = '2';
1089                     *u++ = p[-1];  /* 'f' or 'F' */
1090                     continue;
1091                 }
1092 
1093                 state = saved_state;
1094                 goto again;
1095             }
1096 
1097             return NXT_HTTP_PARSE_INVALID;
1098         }
1099     }
1100 
1101     if (state >= sw_dot) {
1102         if (state >= sw_quoted) {
1103             return NXT_HTTP_PARSE_INVALID;
1104         }
1105 
1106         /* "/." and "/.." must be normalized similar to "/./" and "/../". */
1107         ch = '/';
1108         goto again;
1109     }
1110 
1111 args:
1112 
1113     for (/* void */; p < rp->target_end; p++) {
1114         if (*p == '#') {
1115             break;
1116         }
1117     }
1118 
1119     if (args != NULL) {
1120         rp->args.length = p - args;
1121         rp->args.start = args;
1122     }
1123 
1124 done:
1125 
1126     rp->path.length = u - rp->path.start;
1127 
1128     return NXT_OK;
1129 }
1130 
1131 
1132 const nxt_lvlhsh_proto_t  nxt_http_fields_hash_proto  nxt_aligned(64) = {
1133     NXT_LVLHSH_BUCKET_SIZE(64),
1134     { NXT_HTTP_FIELD_LVLHSH_SHIFT, 0, 0, 0, 0, 0, 0, 0 },
1135     nxt_http_field_hash_test,
1136     nxt_http_field_hash_alloc,
1137     nxt_http_field_hash_free,
1138 };
1139 
1140 
1141 static nxt_int_t
1142 nxt_http_field_hash_test(nxt_lvlhsh_query_t *lhq, void *data)
1143 {
1144     nxt_http_field_proc_t  *field;
1145 
1146     field = data;
1147 
1148     if (nxt_strcasestr_eq(&lhq->key, &field->name)) {
1149         return NXT_OK;
1150     }
1151 
1152     return NXT_DECLINED;
1153 }
1154 
1155 
1156 static void *
1157 nxt_http_field_hash_alloc(void *pool, size_t size)
1158 {
1159     return nxt_mp_align(pool, size, size);
1160 }
1161 
1162 
1163 static void
1164 nxt_http_field_hash_free(void *pool, void *p)
1165 {
1166     nxt_mp_free(pool, p);
1167 }
1168 
1169 
1170 static nxt_int_t
1171 nxt_http_field_hash_collision(nxt_lvlhsh_query_t *lhq, void *data)
1172 {
1173     return NXT_OK;
1174 }
1175 
1176 
1177 nxt_int_t
1178 nxt_http_fields_hash(nxt_lvlhsh_t *hash, nxt_mp_t *mp,
1179     nxt_http_field_proc_t items[], nxt_uint_t count)
1180 {
1181     u_char              ch;
1182     uint32_t            key;
1183     nxt_str_t           *name;
1184     nxt_int_t           ret;
1185     nxt_uint_t          i, j;
1186     nxt_lvlhsh_query_t  lhq;
1187 
1188     lhq.replace = 0;
1189     lhq.proto = &nxt_http_fields_hash_proto;
1190     lhq.pool = mp;
1191 
1192     for (i = 0; i < count; i++) {
1193         key = NXT_HTTP_FIELD_HASH_INIT;
1194         name = &items[i].name;
1195 
1196         for (j = 0; j < name->length; j++) {
1197             ch = nxt_lowcase(name->start[j]);
1198             key = nxt_http_field_hash_char(key, ch);
1199         }
1200 
1201         lhq.key_hash = nxt_http_field_hash_end(key) & 0xFFFF;
1202         lhq.key = *name;
1203         lhq.value = &items[i];
1204 
1205         ret = nxt_lvlhsh_insert(hash, &lhq);
1206 
1207         if (nxt_slow_path(ret != NXT_OK)) {
1208             return NXT_ERROR;
1209         }
1210     }
1211 
1212     return NXT_OK;
1213 }
1214 
1215 
1216 nxt_uint_t
1217 nxt_http_fields_hash_collisions(nxt_lvlhsh_t *hash, nxt_mp_t *mp,
1218     nxt_http_field_proc_t items[], nxt_uint_t count, nxt_bool_t level)
1219 {
1220     u_char              ch;
1221     uint32_t            key, mask;
1222     nxt_str_t           *name;
1223     nxt_uint_t          colls, i, j;
1224     nxt_lvlhsh_proto_t  proto;
1225     nxt_lvlhsh_query_t  lhq;
1226 
1227     proto = nxt_http_fields_hash_proto;
1228     proto.test = nxt_http_field_hash_collision;
1229 
1230     lhq.replace = 0;
1231     lhq.proto = &proto;
1232     lhq.pool = mp;
1233 
1234     mask = level ? (1 << NXT_HTTP_FIELD_LVLHSH_SHIFT) - 1 : 0xFFFF;
1235 
1236     colls = 0;
1237 
1238     for (i = 0; i < count; i++) {
1239         key = NXT_HTTP_FIELD_HASH_INIT;
1240         name = &items[i].name;
1241 
1242         for (j = 0; j < name->length; j++) {
1243             ch = nxt_lowcase(name->start[j]);
1244             key = nxt_http_field_hash_char(key, ch);
1245         }
1246 
1247         lhq.key_hash = nxt_http_field_hash_end(key) & mask;
1248         lhq.value = &items[i];
1249 
1250         if (nxt_lvlhsh_insert(hash, &lhq) == NXT_DECLINED) {
1251             colls++;
1252         }
1253     }
1254 
1255     return colls;
1256 }
1257 
1258 
1259 nxt_int_t
1260 nxt_http_fields_process(nxt_list_t *fields, nxt_lvlhsh_t *hash, void *ctx)
1261 {
1262     nxt_int_t         ret;
1263     nxt_http_field_t  *field;
1264 
1265     nxt_list_each(field, fields) {
1266 
1267         ret = nxt_http_field_process(field, hash, ctx);
1268         if (nxt_slow_path(ret != NXT_OK)) {
1269             return ret;
1270         }
1271 
1272     } nxt_list_loop;
1273 
1274     return NXT_OK;
1275 }
1276