xref: /unit/src/nxt_http_parse.c (revision 1459:358b957ca294)
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 
292         case NXT_HTTP_TARGET_QUOTE_MARK:
293             rp->quoted_target = 1;
294             goto rest_of_target;
295 
296         case NXT_HTTP_TARGET_HASH:
297             rp->complex_target = 1;
298             goto rest_of_target;
299 
300         case NXT_HTTP_TARGET_AGAIN:
301             rp->target_end = p;
302             return NXT_AGAIN;
303 
304         case NXT_HTTP_TARGET_BAD:
305             rp->target_end = p;
306             return NXT_HTTP_PARSE_INVALID;
307         }
308 
309         nxt_unreachable();
310     }
311 
312 rest_of_target:
313 
314     rest = 1;
315 
316     for ( ;; ) {
317         p++;
318 
319         trap = nxt_http_parse_target(&p, end);
320 
321         switch (trap) {
322         case NXT_HTTP_TARGET_SPACE:
323             rp->target_end = p;
324             goto space_after_target;
325 
326         case NXT_HTTP_TARGET_HASH:
327             rp->complex_target = 1;
328             continue;
329 
330         case NXT_HTTP_TARGET_AGAIN:
331             rp->target_end = p;
332             return NXT_AGAIN;
333 
334         case NXT_HTTP_TARGET_BAD:
335             rp->target_end = p;
336             return NXT_HTTP_PARSE_INVALID;
337 
338         default:
339             continue;
340         }
341 
342         nxt_unreachable();
343     }
344 
345 space_after_target:
346 
347     if (nxt_slow_path(end - p < 10)) {
348 
349         do {
350             p++;
351 
352             if (p == end) {
353                 return NXT_AGAIN;
354             }
355 
356         } while (*p == ' ');
357 
358         if (nxt_memcmp(p, "HTTP/", nxt_min(end - p, 5)) == 0) {
359 
360             switch (end - p) {
361             case 8:
362                 if (p[7] < '0' || p[7] > '9') {
363                     break;
364                 }
365                 /* Fall through. */
366             case 7:
367                 if (p[6] != '.') {
368                     break;
369                 }
370                 /* Fall through. */
371             case 6:
372                 if (p[5] < '0' || p[5] > '9') {
373                     break;
374                 }
375                 /* Fall through. */
376             default:
377                 return NXT_AGAIN;
378             }
379         }
380 
381         rp->space_in_target = 1;
382 
383         if (rest) {
384             goto rest_of_target;
385         }
386 
387         goto continue_target;
388     }
389 
390     /* " HTTP/1.1\r\n" or " HTTP/1.1\n" */
391 
392     if (nxt_slow_path(p[9] != '\r' && p[9] != '\n')) {
393 
394         if (p[1] == ' ') {
395             /* surplus space after tartet */
396             p++;
397             goto space_after_target;
398         }
399 
400         rp->space_in_target = 1;
401 
402         if (rest) {
403             goto rest_of_target;
404         }
405 
406         goto continue_target;
407     }
408 
409     nxt_memcpy(ver.str, &p[1], 8);
410 
411     if (nxt_fast_path(ver.ui64 == http11.ui64
412                       || ver.ui64 == http10.ui64
413                       || (nxt_memcmp(ver.str, "HTTP/1.", 7) == 0
414                           && ver.s.minor >= '0' && ver.s.minor <= '9')))
415     {
416         rp->version.ui64 = ver.ui64;
417 
418         if (nxt_fast_path(p[9] == '\r')) {
419             p += 10;
420 
421             if (nxt_slow_path(p == end)) {
422                 return NXT_AGAIN;
423             }
424 
425             if (nxt_slow_path(*p != '\n')) {
426                 return NXT_HTTP_PARSE_INVALID;
427             }
428 
429             *pos = p + 1;
430 
431         } else {
432             *pos = p + 10;
433         }
434 
435         if (rp->complex_target != 0 || rp->quoted_target != 0) {
436             rc = nxt_http_parse_complex_target(rp);
437 
438             if (nxt_slow_path(rc != NXT_OK)) {
439                 return rc;
440             }
441 
442             return nxt_http_parse_field_name(rp, pos, end);
443         }
444 
445         rp->path.start = rp->target_start;
446 
447         if (args != NULL) {
448             rp->path.length = args - rp->target_start - 1;
449 
450             rp->args.length = rp->target_end - args;
451             rp->args.start = args;
452 
453         } else {
454             rp->path.length = rp->target_end - rp->target_start;
455         }
456 
457         return nxt_http_parse_field_name(rp, pos, end);
458     }
459 
460     if (nxt_memcmp(ver.s.prefix, "HTTP/", 5) == 0
461         && ver.s.major >= '0' && ver.s.major <= '9'
462         && ver.s.point == '.'
463         && ver.s.minor >= '0' && ver.s.minor <= '9')
464     {
465         rp->version.ui64 = ver.ui64;
466         return NXT_HTTP_PARSE_UNSUPPORTED_VERSION;
467     }
468 
469     return NXT_HTTP_PARSE_INVALID;
470 }
471 
472 
473 static nxt_int_t
474 nxt_http_parse_unusual_target(nxt_http_request_parse_t *rp, u_char **pos,
475     u_char *end)
476 {
477     u_char  *p, ch;
478 
479     p = *pos;
480 
481     ch = *p;
482 
483     if (ch == ' ') {
484         /* skip surplus spaces before target */
485 
486         do {
487             p++;
488 
489             if (nxt_slow_path(p == end)) {
490                 return NXT_AGAIN;
491             }
492 
493             ch = *p;
494 
495         } while (ch == ' ');
496 
497         if (ch == '/') {
498             *pos = p;
499             return NXT_OK;
500         }
501     }
502 
503     /* absolute path or '*' */
504 
505     /* TODO */
506 
507     return NXT_HTTP_PARSE_INVALID;
508 }
509 
510 
511 static nxt_int_t
512 nxt_http_parse_field_name(nxt_http_request_parse_t *rp, u_char **pos,
513     u_char *end)
514 {
515     u_char    *p, c;
516     size_t    len;
517     uint32_t  hash;
518 
519     static const u_char  normal[256]  nxt_aligned(64) =
520         "\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"
521         "\0\0\0\0\0\0\0\0\0\0\0\0\0-\0\0" "0123456789\0\0\0\0\0\0"
522 
523         /* These 64 bytes should reside in one cache line. */
524         "\0abcdefghijklmnopqrstuvwxyz\0\0\0\0_"
525         "\0abcdefghijklmnopqrstuvwxyz\0\0\0\0\0"
526 
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         "\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"
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 
532     p = *pos + rp->field_name.length;
533     hash = rp->field_hash;
534 
535     while (nxt_fast_path(end - p >= 8)) {
536 
537 #define nxt_field_name_test_char(ch)                                          \
538                                                                               \
539         c = normal[ch];                                                       \
540                                                                               \
541         if (nxt_slow_path(c == '\0')) {                                       \
542             p = &(ch);                                                        \
543             goto name_end;                                                    \
544         }                                                                     \
545                                                                               \
546         hash = nxt_http_field_hash_char(hash, c);
547 
548 /* enddef */
549 
550         nxt_field_name_test_char(p[0]);
551         nxt_field_name_test_char(p[1]);
552         nxt_field_name_test_char(p[2]);
553         nxt_field_name_test_char(p[3]);
554 
555         nxt_field_name_test_char(p[4]);
556         nxt_field_name_test_char(p[5]);
557         nxt_field_name_test_char(p[6]);
558         nxt_field_name_test_char(p[7]);
559 
560         p += 8;
561     }
562 
563     while (nxt_fast_path(p != end)) {
564         nxt_field_name_test_char(*p); p++;
565     }
566 
567     len = p - *pos;
568 
569     if (nxt_slow_path(len > NXT_HTTP_MAX_FIELD_NAME)) {
570         return NXT_HTTP_PARSE_TOO_LARGE_FIELD;
571     }
572 
573     rp->field_hash = hash;
574     rp->field_name.length = len;
575 
576     rp->handler = &nxt_http_parse_field_name;
577 
578     return NXT_AGAIN;
579 
580 name_end:
581 
582     if (nxt_fast_path(*p == ':')) {
583         if (nxt_slow_path(p == *pos)) {
584             return NXT_HTTP_PARSE_INVALID;
585         }
586 
587         len = p - *pos;
588 
589         if (nxt_slow_path(len > NXT_HTTP_MAX_FIELD_NAME)) {
590             return NXT_HTTP_PARSE_TOO_LARGE_FIELD;
591         }
592 
593         rp->field_hash = hash;
594 
595         rp->field_name.length = len;
596         rp->field_name.start = *pos;
597 
598         *pos = p + 1;
599 
600         return nxt_http_parse_field_value(rp, pos, end);
601     }
602 
603     if (nxt_slow_path(p != *pos)) {
604         return NXT_HTTP_PARSE_INVALID;
605     }
606 
607     return nxt_http_parse_field_end(rp, pos, end);
608 }
609 
610 
611 static nxt_int_t
612 nxt_http_parse_field_value(nxt_http_request_parse_t *rp, u_char **pos,
613     u_char *end)
614 {
615     u_char  *p, *start, ch;
616     size_t  len;
617 
618     p = *pos;
619 
620     for ( ;; ) {
621         if (nxt_slow_path(p == end)) {
622             *pos = p;
623             rp->handler = &nxt_http_parse_field_value;
624             return NXT_AGAIN;
625         }
626 
627         ch = *p;
628 
629         if (ch != ' ' && ch != '\t') {
630             break;
631         }
632 
633         p++;
634     }
635 
636     start = p;
637 
638     p += rp->field_value.length;
639 
640     for ( ;; ) {
641         p = nxt_http_lookup_field_end(p, end);
642 
643         if (nxt_slow_path(p == end)) {
644             *pos = start;
645 
646             len = p - start;
647 
648             if (nxt_slow_path(len > NXT_HTTP_MAX_FIELD_VALUE)) {
649                 return NXT_HTTP_PARSE_TOO_LARGE_FIELD;
650             }
651 
652             rp->field_value.length = len;
653             rp->handler = &nxt_http_parse_field_value;
654             return NXT_AGAIN;
655         }
656 
657         ch = *p;
658 
659         if (nxt_fast_path(ch == '\r' || ch == '\n')) {
660             break;
661         }
662 
663         if (ch != '\t') {
664             return NXT_HTTP_PARSE_INVALID;
665         }
666 
667         p++;
668     }
669 
670     *pos = p;
671 
672     if (nxt_fast_path(p != start)) {
673 
674         while (p[-1] == ' ' || p[-1] == '\t') {
675             p--;
676         }
677     }
678 
679     len = p - start;
680 
681     if (nxt_slow_path(len > NXT_HTTP_MAX_FIELD_VALUE)) {
682         return NXT_HTTP_PARSE_TOO_LARGE_FIELD;
683     }
684 
685     rp->field_value.length = len;
686     rp->field_value.start = start;
687 
688     return nxt_http_parse_field_end(rp, pos, end);
689 }
690 
691 
692 static u_char *
693 nxt_http_lookup_field_end(u_char *p, u_char *end)
694 {
695     while (nxt_fast_path(end - p >= 16)) {
696 
697 #define nxt_field_end_test_char(ch)                                           \
698                                                                               \
699         if (nxt_slow_path((ch) < 0x20)) {                                     \
700             return &(ch);                                                     \
701         }
702 
703 /* enddef */
704 
705         nxt_field_end_test_char(p[0]);
706         nxt_field_end_test_char(p[1]);
707         nxt_field_end_test_char(p[2]);
708         nxt_field_end_test_char(p[3]);
709 
710         nxt_field_end_test_char(p[4]);
711         nxt_field_end_test_char(p[5]);
712         nxt_field_end_test_char(p[6]);
713         nxt_field_end_test_char(p[7]);
714 
715         nxt_field_end_test_char(p[8]);
716         nxt_field_end_test_char(p[9]);
717         nxt_field_end_test_char(p[10]);
718         nxt_field_end_test_char(p[11]);
719 
720         nxt_field_end_test_char(p[12]);
721         nxt_field_end_test_char(p[13]);
722         nxt_field_end_test_char(p[14]);
723         nxt_field_end_test_char(p[15]);
724 
725         p += 16;
726     }
727 
728     while (nxt_fast_path(end - p >= 4)) {
729 
730         nxt_field_end_test_char(p[0]);
731         nxt_field_end_test_char(p[1]);
732         nxt_field_end_test_char(p[2]);
733         nxt_field_end_test_char(p[3]);
734 
735         p += 4;
736     }
737 
738     switch (end - p) {
739     case 3:
740         nxt_field_end_test_char(*p); p++;
741         /* Fall through. */
742     case 2:
743         nxt_field_end_test_char(*p); p++;
744         /* Fall through. */
745     case 1:
746         nxt_field_end_test_char(*p); p++;
747         /* Fall through. */
748     case 0:
749         break;
750     default:
751         nxt_unreachable();
752     }
753 
754     return p;
755 }
756 
757 
758 static nxt_int_t
759 nxt_http_parse_field_end(nxt_http_request_parse_t *rp, u_char **pos,
760     u_char *end)
761 {
762     u_char            *p;
763     nxt_http_field_t  *field;
764 
765     p = *pos;
766 
767     if (nxt_fast_path(*p == '\r')) {
768         p++;
769 
770         if (nxt_slow_path(p == end)) {
771             rp->handler = &nxt_http_parse_field_end;
772             return NXT_AGAIN;
773         }
774     }
775 
776     if (nxt_fast_path(*p == '\n')) {
777         *pos = p + 1;
778 
779         if (rp->field_name.length != 0) {
780             field = nxt_list_add(rp->fields);
781 
782             if (nxt_slow_path(field == NULL)) {
783                 return NXT_ERROR;
784             }
785 
786             field->hash = nxt_http_field_hash_end(rp->field_hash);
787             field->skip = 0;
788             field->hopbyhop = 0;
789 
790             field->name_length = rp->field_name.length;
791             field->value_length = rp->field_value.length;
792             field->name = rp->field_name.start;
793             field->value = rp->field_value.start;
794 
795             rp->field_hash = NXT_HTTP_FIELD_HASH_INIT;
796 
797             rp->field_name.length = 0;
798             rp->field_value.length = 0;
799 
800             rp->handler = &nxt_http_parse_field_name;
801             return NXT_OK;
802         }
803 
804         return NXT_DONE;
805     }
806 
807     return NXT_HTTP_PARSE_INVALID;
808 }
809 
810 
811 #define                                                                       \
812 nxt_http_is_normal(c)                                                         \
813     (nxt_fast_path((nxt_http_normal[c / 8] & (1 << (c & 7))) != 0))
814 
815 
816 static const uint8_t  nxt_http_normal[32]  nxt_aligned(32) = {
817 
818                              /*        \0   \r  \n                         */
819     0xFE, 0xDB, 0xFF, 0xFF,  /* 1111 1110  1101 1011  1111 1111  1111 1111 */
820 
821                              /* '&%$ #"!   /.-, |*)(  7654 3210  ?>=< ;:98 */
822     0xD6, 0x37, 0xFF, 0x7F,  /* 1101 0110  0011 0111  1111 1111  0111 1111 */
823 
824                              /* GFED CBA@  ONML KJIH  WVUT SRQP  _^]\ [ZYX */
825     0xFF, 0xFF, 0xFF, 0xFF,  /* 1111 1111  1111 1111  1111 1111  1111 1111 */
826 
827                              /* gfed cba`  onml kjih  wvut srqp   ~}| {zyx */
828     0xFF, 0xFF, 0xFF, 0xFF,  /* 1111 1111  1111 1111  1111 1111  1111 1111 */
829 
830     0xFF, 0xFF, 0xFF, 0xFF,  /* 1111 1111  1111 1111  1111 1111  1111 1111 */
831     0xFF, 0xFF, 0xFF, 0xFF,  /* 1111 1111  1111 1111  1111 1111  1111 1111 */
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 };
835 
836 
837 static nxt_int_t
838 nxt_http_parse_complex_target(nxt_http_request_parse_t *rp)
839 {
840     u_char  *p, *u, c, ch, high, *args;
841 
842     enum {
843         sw_normal = 0,
844         sw_slash,
845         sw_dot,
846         sw_dot_dot,
847         sw_quoted,
848         sw_quoted_second,
849     } state, saved_state;
850 
851     nxt_prefetch(nxt_http_normal);
852 
853     state = sw_normal;
854     saved_state = sw_normal;
855     p = rp->target_start;
856 
857     u = nxt_mp_alloc(rp->mem_pool, rp->target_end - p + 1);
858     if (nxt_slow_path(u == NULL)) {
859         return NXT_ERROR;
860     }
861 
862     rp->path.length = 0;
863     rp->path.start = u;
864 
865     high = '\0';
866     args = NULL;
867 
868     while (p < rp->target_end) {
869 
870         ch = *p++;
871 
872     again:
873 
874         switch (state) {
875 
876         case sw_normal:
877 
878             if (nxt_http_is_normal(ch)) {
879                 *u++ = ch;
880                 continue;
881             }
882 
883             switch (ch) {
884             case '/':
885                 state = sw_slash;
886                 *u++ = ch;
887                 continue;
888             case '%':
889                 saved_state = state;
890                 state = sw_quoted;
891                 continue;
892             case '?':
893                 args = p;
894                 goto args;
895             case '#':
896                 goto done;
897             default:
898                 *u++ = ch;
899                 continue;
900             }
901 
902             break;
903 
904         case sw_slash:
905 
906             if (nxt_http_is_normal(ch)) {
907                 state = sw_normal;
908                 *u++ = ch;
909                 continue;
910             }
911 
912             switch (ch) {
913             case '/':
914                 continue;
915             case '.':
916                 state = sw_dot;
917                 *u++ = ch;
918                 continue;
919             case '%':
920                 saved_state = state;
921                 state = sw_quoted;
922                 continue;
923             case '?':
924                 args = p;
925                 goto args;
926             case '#':
927                 goto done;
928             default:
929                 state = sw_normal;
930                 *u++ = ch;
931                 continue;
932             }
933 
934             break;
935 
936         case sw_dot:
937 
938             if (nxt_http_is_normal(ch)) {
939                 state = sw_normal;
940                 *u++ = ch;
941                 continue;
942             }
943 
944             switch (ch) {
945             case '/':
946                 state = sw_slash;
947                 u--;
948                 continue;
949             case '.':
950                 state = sw_dot_dot;
951                 *u++ = ch;
952                 continue;
953             case '%':
954                 saved_state = state;
955                 state = sw_quoted;
956                 continue;
957             case '?':
958                 u--;
959                 args = p;
960                 goto args;
961             case '#':
962                 u--;
963                 goto done;
964             default:
965                 state = sw_normal;
966                 *u++ = ch;
967                 continue;
968             }
969 
970             break;
971 
972         case sw_dot_dot:
973 
974             if (nxt_http_is_normal(ch)) {
975                 state = sw_normal;
976                 *u++ = ch;
977                 continue;
978             }
979 
980             switch (ch) {
981 
982             case '/':
983             case '?':
984             case '#':
985                 u -= 5;
986 
987                 for ( ;; ) {
988                     if (u < rp->path.start) {
989                         return NXT_HTTP_PARSE_INVALID;
990                     }
991 
992                     if (*u == '/') {
993                         u++;
994                         break;
995                     }
996 
997                     u--;
998                 }
999 
1000                 if (ch == '?') {
1001                     args = p;
1002                     goto args;
1003                 }
1004 
1005                 if (ch == '#') {
1006                     goto done;
1007                 }
1008 
1009                 state = sw_slash;
1010                 break;
1011 
1012             case '%':
1013                 saved_state = state;
1014                 state = sw_quoted;
1015                 continue;
1016 
1017             default:
1018                 state = sw_normal;
1019                 *u++ = ch;
1020                 continue;
1021             }
1022 
1023             break;
1024 
1025         case sw_quoted:
1026             rp->quoted_target = 1;
1027 
1028             if (ch >= '0' && ch <= '9') {
1029                 high = (u_char) (ch - '0');
1030                 state = sw_quoted_second;
1031                 continue;
1032             }
1033 
1034             c = (u_char) (ch | 0x20);
1035             if (c >= 'a' && c <= 'f') {
1036                 high = (u_char) (c - 'a' + 10);
1037                 state = sw_quoted_second;
1038                 continue;
1039             }
1040 
1041             return NXT_HTTP_PARSE_INVALID;
1042 
1043         case sw_quoted_second:
1044             if (ch >= '0' && ch <= '9') {
1045                 ch = (u_char) ((high << 4) + ch - '0');
1046 
1047                 if (ch == '%') {
1048                     state = sw_normal;
1049                     *u++ = '%';
1050 
1051                     if (rp->encoded_slashes) {
1052                         *u++ = '2';
1053                         *u++ = '5';
1054                     }
1055 
1056                     continue;
1057                 }
1058 
1059                 if (ch == '#') {
1060                     state = sw_normal;
1061                     *u++ = '#';
1062                     continue;
1063                 }
1064 
1065                 if (ch == '\0') {
1066                     return NXT_HTTP_PARSE_INVALID;
1067                 }
1068 
1069                 state = saved_state;
1070                 goto again;
1071             }
1072 
1073             c = (u_char) (ch | 0x20);
1074             if (c >= 'a' && c <= 'f') {
1075                 ch = (u_char) ((high << 4) + c - 'a' + 10);
1076 
1077                 if (ch == '?') {
1078                     state = sw_normal;
1079                     *u++ = ch;
1080                     continue;
1081                 }
1082 
1083                 if (ch == '/' && rp->encoded_slashes) {
1084                     state = sw_normal;
1085                     *u++ = '%';
1086                     *u++ = '2';
1087                     *u++ = p[-1];  /* 'f' or 'F' */
1088                     continue;
1089                 }
1090 
1091                 state = saved_state;
1092                 goto again;
1093             }
1094 
1095             return NXT_HTTP_PARSE_INVALID;
1096         }
1097     }
1098 
1099     if (state >= sw_dot) {
1100         if (state >= sw_quoted) {
1101             return NXT_HTTP_PARSE_INVALID;
1102         }
1103 
1104         /* "/." and "/.." must be normalized similar to "/./" and "/../". */
1105         ch = '/';
1106         goto again;
1107     }
1108 
1109 args:
1110 
1111     for (/* void */; p < rp->target_end; p++) {
1112         if (*p == '#') {
1113             break;
1114         }
1115     }
1116 
1117     if (args != NULL) {
1118         rp->args.length = p - args;
1119         rp->args.start = args;
1120     }
1121 
1122 done:
1123 
1124     rp->path.length = u - rp->path.start;
1125 
1126     return NXT_OK;
1127 }
1128 
1129 
1130 const nxt_lvlhsh_proto_t  nxt_http_fields_hash_proto  nxt_aligned(64) = {
1131     NXT_LVLHSH_BUCKET_SIZE(64),
1132     { NXT_HTTP_FIELD_LVLHSH_SHIFT, 0, 0, 0, 0, 0, 0, 0 },
1133     nxt_http_field_hash_test,
1134     nxt_lvlhsh_alloc,
1135     nxt_lvlhsh_free,
1136 };
1137 
1138 
1139 static nxt_int_t
1140 nxt_http_field_hash_test(nxt_lvlhsh_query_t *lhq, void *data)
1141 {
1142     nxt_http_field_proc_t  *field;
1143 
1144     field = data;
1145 
1146     if (nxt_strcasestr_eq(&lhq->key, &field->name)) {
1147         return NXT_OK;
1148     }
1149 
1150     return NXT_DECLINED;
1151 }
1152 
1153 
1154 static nxt_int_t
1155 nxt_http_field_hash_collision(nxt_lvlhsh_query_t *lhq, void *data)
1156 {
1157     return NXT_OK;
1158 }
1159 
1160 
1161 nxt_int_t
1162 nxt_http_fields_hash(nxt_lvlhsh_t *hash,
1163     nxt_http_field_proc_t items[], nxt_uint_t count)
1164 {
1165     u_char              ch;
1166     uint32_t            key;
1167     nxt_str_t           *name;
1168     nxt_int_t           ret;
1169     nxt_uint_t          i, j;
1170     nxt_lvlhsh_query_t  lhq;
1171 
1172     lhq.replace = 0;
1173     lhq.proto = &nxt_http_fields_hash_proto;
1174 
1175     for (i = 0; i < count; i++) {
1176         key = NXT_HTTP_FIELD_HASH_INIT;
1177         name = &items[i].name;
1178 
1179         for (j = 0; j < name->length; j++) {
1180             ch = nxt_lowcase(name->start[j]);
1181             key = nxt_http_field_hash_char(key, ch);
1182         }
1183 
1184         lhq.key_hash = nxt_http_field_hash_end(key) & 0xFFFF;
1185         lhq.key = *name;
1186         lhq.value = &items[i];
1187 
1188         ret = nxt_lvlhsh_insert(hash, &lhq);
1189 
1190         if (nxt_slow_path(ret != NXT_OK)) {
1191             return NXT_ERROR;
1192         }
1193     }
1194 
1195     return NXT_OK;
1196 }
1197 
1198 
1199 nxt_uint_t
1200 nxt_http_fields_hash_collisions(nxt_lvlhsh_t *hash,
1201     nxt_http_field_proc_t items[], nxt_uint_t count, nxt_bool_t level)
1202 {
1203     u_char              ch;
1204     uint32_t            key, mask;
1205     nxt_str_t           *name;
1206     nxt_uint_t          colls, i, j;
1207     nxt_lvlhsh_proto_t  proto;
1208     nxt_lvlhsh_query_t  lhq;
1209 
1210     proto = nxt_http_fields_hash_proto;
1211     proto.test = nxt_http_field_hash_collision;
1212 
1213     lhq.replace = 0;
1214     lhq.proto = &proto;
1215 
1216     mask = level ? (1 << NXT_HTTP_FIELD_LVLHSH_SHIFT) - 1 : 0xFFFF;
1217 
1218     colls = 0;
1219 
1220     for (i = 0; i < count; i++) {
1221         key = NXT_HTTP_FIELD_HASH_INIT;
1222         name = &items[i].name;
1223 
1224         for (j = 0; j < name->length; j++) {
1225             ch = nxt_lowcase(name->start[j]);
1226             key = nxt_http_field_hash_char(key, ch);
1227         }
1228 
1229         lhq.key_hash = nxt_http_field_hash_end(key) & mask;
1230         lhq.value = &items[i];
1231 
1232         if (nxt_lvlhsh_insert(hash, &lhq) == NXT_DECLINED) {
1233             colls++;
1234         }
1235     }
1236 
1237     return colls;
1238 }
1239 
1240 
1241 nxt_int_t
1242 nxt_http_fields_process(nxt_list_t *fields, nxt_lvlhsh_t *hash, void *ctx)
1243 {
1244     nxt_int_t         ret;
1245     nxt_http_field_t  *field;
1246 
1247     nxt_list_each(field, fields) {
1248 
1249         ret = nxt_http_field_process(field, hash, ctx);
1250         if (nxt_slow_path(ret != NXT_OK)) {
1251             return ret;
1252         }
1253 
1254     } nxt_list_loop;
1255 
1256     return NXT_OK;
1257 }
1258