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