xref: /unit/src/nxt_http_parse.c (revision 2139:99d792169ffb)
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, const u_char *end);
12 static nxt_int_t nxt_http_parse_request_line(nxt_http_request_parse_t *rp,
13     u_char **pos, const u_char *end);
14 static nxt_int_t nxt_http_parse_field_name(nxt_http_request_parse_t *rp,
15     u_char **pos, const u_char *end);
16 static nxt_int_t nxt_http_parse_field_value(nxt_http_request_parse_t *rp,
17     u_char **pos, const u_char *end);
18 static u_char *nxt_http_lookup_field_end(u_char *p, const u_char *end);
19 static nxt_int_t nxt_http_parse_field_end(nxt_http_request_parse_t *rp,
20     u_char **pos, const 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, const 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     const 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     const 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     const 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     const 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, const 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     const 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 nxt_http_is_normal(c)                                                 \
831     (nxt_fast_path((nxt_http_normal[c / 8] & (1 << (c & 7))) != 0))
832 
833 
834 static const uint8_t  nxt_http_normal[32]  nxt_aligned(32) = {
835 
836                              /*        \0   \r  \n                         */
837     0xFE, 0xDB, 0xFF, 0xFF,  /* 1111 1110  1101 1011  1111 1111  1111 1111 */
838 
839                              /* '&%$ #"!   /.-, |*)(  7654 3210  ?>=< ;:98 */
840     0xD6, 0x37, 0xFF, 0x7F,  /* 1101 0110  0011 0111  1111 1111  0111 1111 */
841 
842                              /* GFED CBA@  ONML KJIH  WVUT SRQP  _^]\ [ZYX */
843     0xFF, 0xFF, 0xFF, 0xFF,  /* 1111 1111  1111 1111  1111 1111  1111 1111 */
844 
845                              /* gfed cba`  onml kjih  wvut srqp   ~}| {zyx */
846     0xFF, 0xFF, 0xFF, 0xFF,  /* 1111 1111  1111 1111  1111 1111  1111 1111 */
847 
848     0xFF, 0xFF, 0xFF, 0xFF,  /* 1111 1111  1111 1111  1111 1111  1111 1111 */
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 };
853 
854 
855 static nxt_int_t
856 nxt_http_parse_complex_target(nxt_http_request_parse_t *rp)
857 {
858     u_char  *p, *u, c, ch, high, *args;
859 
860     enum {
861         sw_normal = 0,
862         sw_slash,
863         sw_dot,
864         sw_dot_dot,
865         sw_quoted,
866         sw_quoted_second,
867     } state, saved_state;
868 
869     nxt_prefetch(nxt_http_normal);
870 
871     state = sw_normal;
872     saved_state = sw_normal;
873     p = rp->target_start;
874 
875     u = nxt_mp_alloc(rp->mem_pool, rp->target_end - p + 1);
876     if (nxt_slow_path(u == NULL)) {
877         return NXT_ERROR;
878     }
879 
880     rp->path.length = 0;
881     rp->path.start = u;
882 
883     high = '\0';
884     args = NULL;
885 
886     while (p < rp->target_end) {
887 
888         ch = *p++;
889 
890     again:
891 
892         switch (state) {
893 
894         case sw_normal:
895 
896             if (nxt_http_is_normal(ch)) {
897                 *u++ = ch;
898                 continue;
899             }
900 
901             switch (ch) {
902             case '/':
903                 state = sw_slash;
904                 *u++ = ch;
905                 continue;
906             case '%':
907                 saved_state = state;
908                 state = sw_quoted;
909                 continue;
910             case '?':
911                 args = p;
912                 goto args;
913             case '#':
914                 goto done;
915             default:
916                 *u++ = ch;
917                 continue;
918             }
919 
920             break;
921 
922         case sw_slash:
923 
924             if (nxt_http_is_normal(ch)) {
925                 state = sw_normal;
926                 *u++ = ch;
927                 continue;
928             }
929 
930             switch (ch) {
931             case '/':
932                 continue;
933             case '.':
934                 state = sw_dot;
935                 *u++ = ch;
936                 continue;
937             case '%':
938                 saved_state = state;
939                 state = sw_quoted;
940                 continue;
941             case '?':
942                 args = p;
943                 goto args;
944             case '#':
945                 goto done;
946             default:
947                 state = sw_normal;
948                 *u++ = ch;
949                 continue;
950             }
951 
952             break;
953 
954         case sw_dot:
955 
956             if (nxt_http_is_normal(ch)) {
957                 state = sw_normal;
958                 *u++ = ch;
959                 continue;
960             }
961 
962             switch (ch) {
963             case '/':
964                 state = sw_slash;
965                 u--;
966                 continue;
967             case '.':
968                 state = sw_dot_dot;
969                 *u++ = ch;
970                 continue;
971             case '%':
972                 saved_state = state;
973                 state = sw_quoted;
974                 continue;
975             case '?':
976                 u--;
977                 args = p;
978                 goto args;
979             case '#':
980                 u--;
981                 goto done;
982             default:
983                 state = sw_normal;
984                 *u++ = ch;
985                 continue;
986             }
987 
988             break;
989 
990         case sw_dot_dot:
991 
992             if (nxt_http_is_normal(ch)) {
993                 state = sw_normal;
994                 *u++ = ch;
995                 continue;
996             }
997 
998             switch (ch) {
999 
1000             case '/':
1001             case '?':
1002             case '#':
1003                 u -= 5;
1004 
1005                 for ( ;; ) {
1006                     if (u < rp->path.start) {
1007                         return NXT_HTTP_PARSE_INVALID;
1008                     }
1009 
1010                     if (*u == '/') {
1011                         u++;
1012                         break;
1013                     }
1014 
1015                     u--;
1016                 }
1017 
1018                 if (ch == '?') {
1019                     args = p;
1020                     goto args;
1021                 }
1022 
1023                 if (ch == '#') {
1024                     goto done;
1025                 }
1026 
1027                 state = sw_slash;
1028                 break;
1029 
1030             case '%':
1031                 saved_state = state;
1032                 state = sw_quoted;
1033                 continue;
1034 
1035             default:
1036                 state = sw_normal;
1037                 *u++ = ch;
1038                 continue;
1039             }
1040 
1041             break;
1042 
1043         case sw_quoted:
1044             //rp->quoted_target = 1;
1045 
1046             if (ch >= '0' && ch <= '9') {
1047                 high = (u_char) (ch - '0');
1048                 state = sw_quoted_second;
1049                 continue;
1050             }
1051 
1052             c = (u_char) (ch | 0x20);
1053             if (c >= 'a' && c <= 'f') {
1054                 high = (u_char) (c - 'a' + 10);
1055                 state = sw_quoted_second;
1056                 continue;
1057             }
1058 
1059             return NXT_HTTP_PARSE_INVALID;
1060 
1061         case sw_quoted_second:
1062             if (ch >= '0' && ch <= '9') {
1063                 ch = (u_char) ((high << 4) + ch - '0');
1064 
1065                 if (ch == '%') {
1066                     state = sw_normal;
1067                     *u++ = '%';
1068 
1069                     if (rp->encoded_slashes) {
1070                         *u++ = '2';
1071                         *u++ = '5';
1072                     }
1073 
1074                     continue;
1075                 }
1076 
1077                 if (ch == '#') {
1078                     state = sw_normal;
1079                     *u++ = '#';
1080                     continue;
1081                 }
1082 
1083                 if (ch == '\0') {
1084                     return NXT_HTTP_PARSE_INVALID;
1085                 }
1086 
1087                 state = saved_state;
1088                 goto again;
1089             }
1090 
1091             c = (u_char) (ch | 0x20);
1092             if (c >= 'a' && c <= 'f') {
1093                 ch = (u_char) ((high << 4) + c - 'a' + 10);
1094 
1095                 if (ch == '?') {
1096                     state = sw_normal;
1097                     *u++ = ch;
1098                     continue;
1099                 }
1100 
1101                 if (ch == '/' && rp->encoded_slashes) {
1102                     state = sw_normal;
1103                     *u++ = '%';
1104                     *u++ = '2';
1105                     *u++ = p[-1];  /* 'f' or 'F' */
1106                     continue;
1107                 }
1108 
1109                 state = saved_state;
1110                 goto again;
1111             }
1112 
1113             return NXT_HTTP_PARSE_INVALID;
1114         }
1115     }
1116 
1117     if (state >= sw_dot) {
1118         if (state >= sw_quoted) {
1119             return NXT_HTTP_PARSE_INVALID;
1120         }
1121 
1122         /* "/." and "/.." must be normalized similar to "/./" and "/../". */
1123         ch = '/';
1124         goto again;
1125     }
1126 
1127 args:
1128 
1129     for (/* void */; p < rp->target_end; p++) {
1130         if (*p == '#') {
1131             break;
1132         }
1133     }
1134 
1135     if (args != NULL) {
1136         rp->args.length = p - args;
1137         rp->args.start = args;
1138     }
1139 
1140 done:
1141 
1142     rp->path.length = u - rp->path.start;
1143 
1144     return NXT_OK;
1145 }
1146 
1147 
1148 const nxt_lvlhsh_proto_t  nxt_http_fields_hash_proto  nxt_aligned(64) = {
1149     NXT_LVLHSH_BUCKET_SIZE(64),
1150     { NXT_HTTP_FIELD_LVLHSH_SHIFT, 0, 0, 0, 0, 0, 0, 0 },
1151     nxt_http_field_hash_test,
1152     nxt_lvlhsh_alloc,
1153     nxt_lvlhsh_free,
1154 };
1155 
1156 
1157 static nxt_int_t
1158 nxt_http_field_hash_test(nxt_lvlhsh_query_t *lhq, void *data)
1159 {
1160     nxt_http_field_proc_t  *field;
1161 
1162     field = data;
1163 
1164     if (nxt_strcasestr_eq(&lhq->key, &field->name)) {
1165         return NXT_OK;
1166     }
1167 
1168     return NXT_DECLINED;
1169 }
1170 
1171 
1172 static nxt_int_t
1173 nxt_http_field_hash_collision(nxt_lvlhsh_query_t *lhq, void *data)
1174 {
1175     return NXT_OK;
1176 }
1177 
1178 
1179 nxt_int_t
1180 nxt_http_fields_hash(nxt_lvlhsh_t *hash,
1181     nxt_http_field_proc_t items[], nxt_uint_t count)
1182 {
1183     u_char              ch;
1184     uint32_t            key;
1185     nxt_str_t           *name;
1186     nxt_int_t           ret;
1187     nxt_uint_t          i, j;
1188     nxt_lvlhsh_query_t  lhq;
1189 
1190     lhq.replace = 0;
1191     lhq.proto = &nxt_http_fields_hash_proto;
1192 
1193     for (i = 0; i < count; i++) {
1194         key = NXT_HTTP_FIELD_HASH_INIT;
1195         name = &items[i].name;
1196 
1197         for (j = 0; j < name->length; j++) {
1198             ch = nxt_lowcase(name->start[j]);
1199             key = nxt_http_field_hash_char(key, ch);
1200         }
1201 
1202         lhq.key_hash = nxt_http_field_hash_end(key) & 0xFFFF;
1203         lhq.key = *name;
1204         lhq.value = &items[i];
1205 
1206         ret = nxt_lvlhsh_insert(hash, &lhq);
1207 
1208         if (nxt_slow_path(ret != NXT_OK)) {
1209             return NXT_ERROR;
1210         }
1211     }
1212 
1213     return NXT_OK;
1214 }
1215 
1216 
1217 nxt_uint_t
1218 nxt_http_fields_hash_collisions(nxt_lvlhsh_t *hash,
1219     nxt_http_field_proc_t items[], nxt_uint_t count, nxt_bool_t level)
1220 {
1221     u_char              ch;
1222     uint32_t            key, mask;
1223     nxt_str_t           *name;
1224     nxt_uint_t          colls, i, j;
1225     nxt_lvlhsh_proto_t  proto;
1226     nxt_lvlhsh_query_t  lhq;
1227 
1228     proto = nxt_http_fields_hash_proto;
1229     proto.test = nxt_http_field_hash_collision;
1230 
1231     lhq.replace = 0;
1232     lhq.proto = &proto;
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