blob: 62c6652024e070f89d11a1e0853abebf1e7d6684 [file] [log] [blame]
Willy Tarreau1be4f3d2017-09-21 14:35:57 +02001/*
2 * HPACK decompressor (RFC7541)
3 *
4 * Copyright (C) 2014-2017 Willy Tarreau <willy@haproxy.org>
5 * Copyright (C) 2017 HAProxy Technologies
6 *
7 * Permission is hereby granted, free of charge, to any person obtaining
8 * a copy of this software and associated documentation files (the
9 * "Software"), to deal in the Software without restriction, including
10 * without limitation the rights to use, copy, modify, merge, publish,
11 * distribute, sublicense, and/or sell copies of the Software, and to
12 * permit persons to whom the Software is furnished to do so, subject to
13 * the following conditions:
14 *
15 * The above copyright notice and this permission notice shall be
16 * included in all copies or substantial portions of the Software.
17 *
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
19 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
20 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
21 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
22 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
23 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
24 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
25 * OTHER DEALINGS IN THE SOFTWARE.
26 */
27
Willy Tarreaua1bd1fa2019-03-29 17:26:33 +010028#include <inttypes.h>
Willy Tarreau1be4f3d2017-09-21 14:35:57 +020029#include <stdio.h>
30#include <stdlib.h>
31#include <string.h>
32
Willy Tarreaube327fa2020-06-03 09:09:57 +020033#include <haproxy/hpack-enc.h>
Willy Tarreau0017be02020-06-02 19:25:28 +020034#include <haproxy/http-hdr-t.h>
Willy Tarreaueb6f7012020-05-27 16:21:26 +020035#include <import/ist.h>
Willy Tarreau1be4f3d2017-09-21 14:35:57 +020036
37#include <types/global.h>
38
Willy Tarreau2c313942018-12-10 15:19:14 +010039/*
40 * HPACK encoding: these tables were generated using gen-enc.c
41 */
42
43/* encoding of stream of compressed headers. This stream is composed of series
44 * of <len:8b> <index:8b> <name:<len>*8b>.
45 */
46const char hpack_enc_stream[666] = {
47 /* 0: */ 0x03, 0x15, 0x61, 0x67, 0x65, 0x03, 0x3c, 0x76,
48 /* 8: */ 0x69, 0x61, 0x04, 0x21, 0x64, 0x61, 0x74, 0x65,
49 /* 16: */ 0x04, 0x26, 0x68, 0x6f, 0x73, 0x74, 0x04, 0x22,
50 /* 24: */ 0x65, 0x74, 0x61, 0x67, 0x04, 0x25, 0x66, 0x72,
51 /* 32: */ 0x6f, 0x6d, 0x04, 0x2d, 0x6c, 0x69, 0x6e, 0x6b,
52 /* 40: */ 0x04, 0x3b, 0x76, 0x61, 0x72, 0x79, 0x05, 0x04,
53 /* 48: */ 0x3a, 0x70, 0x61, 0x74, 0x68, 0x05, 0x16, 0x61,
54 /* 56: */ 0x6c, 0x6c, 0x6f, 0x77, 0x05, 0x32, 0x72, 0x61,
55 /* 64: */ 0x6e, 0x67, 0x65, 0x06, 0x13, 0x61, 0x63, 0x63,
56 /* 72: */ 0x65, 0x70, 0x74, 0x06, 0x36, 0x73, 0x65, 0x72,
57 /* 80: */ 0x76, 0x65, 0x72, 0x06, 0x20, 0x63, 0x6f, 0x6f,
58 /* 88: */ 0x6b, 0x69, 0x65, 0x06, 0x23, 0x65, 0x78, 0x70,
59 /* 96: */ 0x65, 0x63, 0x74, 0x07, 0x33, 0x72, 0x65, 0x66,
60 /* 104: */ 0x65, 0x72, 0x65, 0x72, 0x07, 0x24, 0x65, 0x78,
61 /* 112: */ 0x70, 0x69, 0x72, 0x65, 0x73, 0x07, 0x02, 0x3a,
62 /* 120: */ 0x6d, 0x65, 0x74, 0x68, 0x6f, 0x64, 0x07, 0x06,
63 /* 128: */ 0x3a, 0x73, 0x63, 0x68, 0x65, 0x6d, 0x65, 0x07,
64 /* 136: */ 0x08, 0x3a, 0x73, 0x74, 0x61, 0x74, 0x75, 0x73,
65 /* 144: */ 0x07, 0x34, 0x72, 0x65, 0x66, 0x72, 0x65, 0x73,
66 /* 152: */ 0x68, 0x08, 0x2e, 0x6c, 0x6f, 0x63, 0x61, 0x74,
67 /* 160: */ 0x69, 0x6f, 0x6e, 0x08, 0x27, 0x69, 0x66, 0x2d,
68 /* 168: */ 0x6d, 0x61, 0x74, 0x63, 0x68, 0x08, 0x2a, 0x69,
69 /* 176: */ 0x66, 0x2d, 0x72, 0x61, 0x6e, 0x67, 0x65, 0x0a,
70 /* 184: */ 0x3a, 0x75, 0x73, 0x65, 0x72, 0x2d, 0x61, 0x67,
71 /* 192: */ 0x65, 0x6e, 0x74, 0x0a, 0x37, 0x73, 0x65, 0x74,
72 /* 200: */ 0x2d, 0x63, 0x6f, 0x6f, 0x6b, 0x69, 0x65, 0x0a,
73 /* 208: */ 0x01, 0x3a, 0x61, 0x75, 0x74, 0x68, 0x6f, 0x72,
74 /* 216: */ 0x69, 0x74, 0x79, 0x0b, 0x35, 0x72, 0x65, 0x74,
75 /* 224: */ 0x72, 0x79, 0x2d, 0x61, 0x66, 0x74, 0x65, 0x72,
76 /* 232: */ 0x0c, 0x1f, 0x63, 0x6f, 0x6e, 0x74, 0x65, 0x6e,
77 /* 240: */ 0x74, 0x2d, 0x74, 0x79, 0x70, 0x65, 0x0c, 0x2f,
78 /* 248: */ 0x6d, 0x61, 0x78, 0x2d, 0x66, 0x6f, 0x72, 0x77,
79 /* 256: */ 0x61, 0x72, 0x64, 0x73, 0x0d, 0x18, 0x63, 0x61,
80 /* 264: */ 0x63, 0x68, 0x65, 0x2d, 0x63, 0x6f, 0x6e, 0x74,
81 /* 272: */ 0x72, 0x6f, 0x6c, 0x0d, 0x2c, 0x6c, 0x61, 0x73,
82 /* 280: */ 0x74, 0x2d, 0x6d, 0x6f, 0x64, 0x69, 0x66, 0x69,
83 /* 288: */ 0x65, 0x64, 0x0d, 0x12, 0x61, 0x63, 0x63, 0x65,
84 /* 296: */ 0x70, 0x74, 0x2d, 0x72, 0x61, 0x6e, 0x67, 0x65,
85 /* 304: */ 0x73, 0x0d, 0x29, 0x69, 0x66, 0x2d, 0x6e, 0x6f,
86 /* 312: */ 0x6e, 0x65, 0x2d, 0x6d, 0x61, 0x74, 0x63, 0x68,
87 /* 320: */ 0x0d, 0x17, 0x61, 0x75, 0x74, 0x68, 0x6f, 0x72,
88 /* 328: */ 0x69, 0x7a, 0x61, 0x74, 0x69, 0x6f, 0x6e, 0x0d,
89 /* 336: */ 0x1e, 0x63, 0x6f, 0x6e, 0x74, 0x65, 0x6e, 0x74,
90 /* 344: */ 0x2d, 0x72, 0x61, 0x6e, 0x67, 0x65, 0x0e, 0x1c,
91 /* 352: */ 0x63, 0x6f, 0x6e, 0x74, 0x65, 0x6e, 0x74, 0x2d,
92 /* 360: */ 0x6c, 0x65, 0x6e, 0x67, 0x74, 0x68, 0x0e, 0x0f,
93 /* 368: */ 0x61, 0x63, 0x63, 0x65, 0x70, 0x74, 0x2d, 0x63,
94 /* 376: */ 0x68, 0x61, 0x72, 0x73, 0x65, 0x74, 0x0f, 0x10,
95 /* 384: */ 0x61, 0x63, 0x63, 0x65, 0x70, 0x74, 0x2d, 0x65,
96 /* 392: */ 0x6e, 0x63, 0x6f, 0x64, 0x69, 0x6e, 0x67, 0x0f,
97 /* 400: */ 0x11, 0x61, 0x63, 0x63, 0x65, 0x70, 0x74, 0x2d,
98 /* 408: */ 0x6c, 0x61, 0x6e, 0x67, 0x75, 0x61, 0x67, 0x65,
99 /* 416: */ 0x10, 0x1a, 0x63, 0x6f, 0x6e, 0x74, 0x65, 0x6e,
100 /* 424: */ 0x74, 0x2d, 0x65, 0x6e, 0x63, 0x6f, 0x64, 0x69,
101 /* 432: */ 0x6e, 0x67, 0x10, 0x1b, 0x63, 0x6f, 0x6e, 0x74,
102 /* 440: */ 0x65, 0x6e, 0x74, 0x2d, 0x6c, 0x61, 0x6e, 0x67,
103 /* 448: */ 0x75, 0x61, 0x67, 0x65, 0x10, 0x1d, 0x63, 0x6f,
104 /* 456: */ 0x6e, 0x74, 0x65, 0x6e, 0x74, 0x2d, 0x6c, 0x6f,
105 /* 464: */ 0x63, 0x61, 0x74, 0x69, 0x6f, 0x6e, 0x10, 0x3d,
106 /* 472: */ 0x77, 0x77, 0x77, 0x2d, 0x61, 0x75, 0x74, 0x68,
107 /* 480: */ 0x65, 0x6e, 0x74, 0x69, 0x63, 0x61, 0x74, 0x65,
108 /* 488: */ 0x11, 0x39, 0x74, 0x72, 0x61, 0x6e, 0x73, 0x66,
109 /* 496: */ 0x65, 0x72, 0x2d, 0x65, 0x6e, 0x63, 0x6f, 0x64,
110 /* 504: */ 0x69, 0x6e, 0x67, 0x11, 0x28, 0x69, 0x66, 0x2d,
111 /* 512: */ 0x6d, 0x6f, 0x64, 0x69, 0x66, 0x69, 0x65, 0x64,
112 /* 520: */ 0x2d, 0x73, 0x69, 0x6e, 0x63, 0x65, 0x12, 0x30,
113 /* 528: */ 0x70, 0x72, 0x6f, 0x78, 0x79, 0x2d, 0x61, 0x75,
114 /* 536: */ 0x74, 0x68, 0x65, 0x6e, 0x74, 0x69, 0x63, 0x61,
115 /* 544: */ 0x74, 0x65, 0x13, 0x19, 0x63, 0x6f, 0x6e, 0x74,
116 /* 552: */ 0x65, 0x6e, 0x74, 0x2d, 0x64, 0x69, 0x73, 0x70,
117 /* 560: */ 0x6f, 0x73, 0x69, 0x74, 0x69, 0x6f, 0x6e, 0x13,
118 /* 568: */ 0x2b, 0x69, 0x66, 0x2d, 0x75, 0x6e, 0x6d, 0x6f,
119 /* 576: */ 0x64, 0x69, 0x66, 0x69, 0x65, 0x64, 0x2d, 0x73,
120 /* 584: */ 0x69, 0x6e, 0x63, 0x65, 0x13, 0x31, 0x70, 0x72,
121 /* 592: */ 0x6f, 0x78, 0x79, 0x2d, 0x61, 0x75, 0x74, 0x68,
122 /* 600: */ 0x6f, 0x72, 0x69, 0x7a, 0x61, 0x74, 0x69, 0x6f,
123 /* 608: */ 0x6e, 0x19, 0x38, 0x73, 0x74, 0x72, 0x69, 0x63,
124 /* 616: */ 0x74, 0x2d, 0x74, 0x72, 0x61, 0x6e, 0x73, 0x70,
125 /* 624: */ 0x6f, 0x72, 0x74, 0x2d, 0x73, 0x65, 0x63, 0x75,
126 /* 632: */ 0x72, 0x69, 0x74, 0x79, 0x1b, 0x14, 0x61, 0x63,
127 /* 640: */ 0x63, 0x65, 0x73, 0x73, 0x2d, 0x63, 0x6f, 0x6e,
128 /* 648: */ 0x74, 0x72, 0x6f, 0x6c, 0x2d, 0x61, 0x6c, 0x6c,
129 /* 656: */ 0x6f, 0x77, 0x2d, 0x6f, 0x72, 0x69, 0x67, 0x69,
130 /* 664: */ 0x6e, 0x00,
131};
132
133/* This points to the first position in table hpack_enc_stream[] of a header
134 * of the same length.
135 */
136const signed short hpack_pos_len[32] = {
137 /* 0: */ -1, -1, -1, 0, 10, 46, 67, 99,
138 /* 8: */ 153, -1, 183, 219, 232, 260, 350, 382,
139 /* 16: */ 416, 488, 526, 546, -1, -1, -1, -1,
140 /* 24: */ -1, 609, -1, 636, -1, -1, -1, -1,
141};
142
Willy Tarreau1be4f3d2017-09-21 14:35:57 +0200143/* Tries to encode header whose name is <n> and value <v> into the chunk <out>.
144 * Returns non-zero on success, 0 on failure (buffer full).
145 */
Willy Tarreau83061a82018-07-13 11:56:34 +0200146int hpack_encode_header(struct buffer *out, const struct ist n,
147 const struct ist v)
Willy Tarreau1be4f3d2017-09-21 14:35:57 +0200148{
Willy Tarreau843b7cb2018-07-13 10:54:26 +0200149 int len = out->data;
Willy Tarreau1be4f3d2017-09-21 14:35:57 +0200150 int size = out->size;
Willy Tarreau2c313942018-12-10 15:19:14 +0100151 int pos;
Willy Tarreau1be4f3d2017-09-21 14:35:57 +0200152
153 if (len >= size)
154 return 0;
155
Willy Tarreau2c313942018-12-10 15:19:14 +0100156 /* look for the header field <n> in the static table */
157 if (n.len >= sizeof(hpack_pos_len) / sizeof(hpack_pos_len[0]))
158 goto make_literal;
159
160 pos = hpack_pos_len[n.len];
161 if (pos >= 0) {
162 /* At least one header field of this length exist */
163 do {
164 char idx;
165
166 pos++;
167 idx = hpack_enc_stream[pos++];
168 pos += n.len;
169 if (isteq(ist2(&hpack_enc_stream[pos - n.len], n.len), n)) {
170 /* emit literal with indexing (7541#6.2.1) :
171 * [ 0 | 1 | Index (6+) ]
172 */
173 out->area[len++] = idx | 0x40;
174 goto emit_value;
175 }
176 } while ((unsigned char)hpack_enc_stream[pos] == n.len);
177 }
178
179 make_literal:
Willy Tarreau0dc1b842018-12-16 09:38:30 +0100180 if (likely(n.len < 127 && len + 2 + n.len <= size)) {
Willy Tarreau19ed92b2018-12-11 06:42:01 +0100181 out->area[len++] = 0x00; /* literal without indexing -- new name */
182 out->area[len++] = n.len; /* single-byte length encoding */
183 ist2bin(out->area + len, n);
184 len += n.len;
185 }
Willy Tarreaubad0a382018-12-11 07:44:00 +0100186 else if (hpack_len_to_bytes(n.len) &&
187 len + 1 + hpack_len_to_bytes(n.len) + n.len <= size) {
Willy Tarreau843b7cb2018-07-13 10:54:26 +0200188 out->area[len++] = 0x00; /* literal without indexing -- new name */
Willy Tarreau843b7cb2018-07-13 10:54:26 +0200189 len = hpack_encode_len(out->area, len, n.len);
Willy Tarreauac73ae02018-12-11 06:27:06 +0100190 ist2bin(out->area + len, n);
Willy Tarreau1be4f3d2017-09-21 14:35:57 +0200191 len += n.len;
192 }
193 else {
194 /* header field name too large for the buffer */
195 return 0;
196 }
197
Willy Tarreau2c313942018-12-10 15:19:14 +0100198 emit_value:
Willy Tarreau1be4f3d2017-09-21 14:35:57 +0200199 /* copy literal header field value */
Willy Tarreaubad0a382018-12-11 07:44:00 +0100200 if (!hpack_len_to_bytes(v.len) ||
201 len + hpack_len_to_bytes(v.len) + v.len > size) {
Willy Tarreau1be4f3d2017-09-21 14:35:57 +0200202 /* header value too large for the buffer */
203 return 0;
204 }
205
Willy Tarreau843b7cb2018-07-13 10:54:26 +0200206 len = hpack_encode_len(out->area, len, v.len);
207 memcpy(out->area + len, v.ptr, v.len);
Willy Tarreau1be4f3d2017-09-21 14:35:57 +0200208 len += v.len;
209
Willy Tarreau843b7cb2018-07-13 10:54:26 +0200210 out->data = len;
Willy Tarreau1be4f3d2017-09-21 14:35:57 +0200211 return 1;
212}