1 /*
2 MIT License
3
4 Copyright (c) 2018 - 2023 LiteSpeed Technologies Inc
5
6 Permission is hereby granted, free of charge, to any person obtaining a copy
7 of this software and associated documentation files (the "Software"), to deal
8 in the Software without restriction, including without limitation the rights
9 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10 copies of the Software, and to permit persons to whom the Software is
11 furnished to do so, subject to the following conditions:
12
13 The above copyright notice and this permission notice shall be included in all
14 copies or substantial portions of the Software.
15
16 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22 SOFTWARE.
23 */
24
25 /*(lighttpd customization)*/
26 #ifndef XXH_HEADER_NAME
27 #define XXH_HEADER_NAME "algo_xxhash.h"
28 #endif
29 #ifndef LS_HPACK_USE_LARGE_TABLES
30 #define LS_HPACK_USE_LARGE_TABLES 0
31 #endif
32 #ifndef NDEBUG
33 #define NDEBUG
34 #endif
35
36 #include <assert.h>
37 #include <stdint.h>
38 #include <stdlib.h>
39 #include <string.h>
40 #include <sys/queue.h>
41
42 #include "lshpack.h"
43 #if LS_HPACK_EMIT_TEST_CODE
44 #include "lshpack-test.h"
45 #endif
46 #include XXH_HEADER_NAME
47
48 #ifndef LS_HPACK_USE_LARGE_TABLES
49 #define LS_HPACK_USE_LARGE_TABLES 1
50 #endif
51
52 #include "huff-tables.h"
53
54 #define HPACK_STATIC_TABLE_SIZE 61
55 #define INITIAL_DYNAMIC_TABLE_SIZE 4096
56
57 /* RFC 7541, Section 4.1:
58 *
59 * " The size of the dynamic table is the sum of the size of its entries.
60 * "
61 * " The size of an entry is the sum of its name's length in octets (as
62 * " defined in Section 5.2), its value's length in octets, and 32.
63 */
64 #define DYNAMIC_ENTRY_OVERHEAD 32
65
66 #define NAME_VAL(a, b) sizeof(a) - 1, sizeof(b) - 1, (a), (b)
67
68 static const struct
69 {
70 unsigned name_len;
71 unsigned val_len;
72 const char *name;
73 const char *val;
74 }
75 static_table[HPACK_STATIC_TABLE_SIZE] =
76 {
77 { NAME_VAL(":authority", "") },
78 { NAME_VAL(":method", "GET") },
79 { NAME_VAL(":method", "POST") },
80 { NAME_VAL(":path", "/") },
81 { NAME_VAL(":path", "/index.html") },
82 { NAME_VAL(":scheme", "http") },
83 { NAME_VAL(":scheme", "https") },
84 { NAME_VAL(":status", "200") },
85 { NAME_VAL(":status", "204") },
86 { NAME_VAL(":status", "206") },
87 { NAME_VAL(":status", "304") },
88 { NAME_VAL(":status", "400") },
89 { NAME_VAL(":status", "404") },
90 { NAME_VAL(":status", "500") },
91 { NAME_VAL("accept-charset", "") },
92 { NAME_VAL("accept-encoding", "gzip, deflate") },
93 { NAME_VAL("accept-language", "") },
94 { NAME_VAL("accept-ranges", "") },
95 { NAME_VAL("accept", "") },
96 { NAME_VAL("access-control-allow-origin", "") },
97 { NAME_VAL("age", "") },
98 { NAME_VAL("allow", "") },
99 { NAME_VAL("authorization", "") },
100 { NAME_VAL("cache-control", "") },
101 { NAME_VAL("content-disposition", "") },
102 { NAME_VAL("content-encoding", "") },
103 { NAME_VAL("content-language", "") },
104 { NAME_VAL("content-length", "") },
105 { NAME_VAL("content-location", "") },
106 { NAME_VAL("content-range", "") },
107 { NAME_VAL("content-type", "") },
108 { NAME_VAL("cookie", "") },
109 { NAME_VAL("date", "") },
110 { NAME_VAL("etag", "") },
111 { NAME_VAL("expect", "") },
112 { NAME_VAL("expires", "") },
113 { NAME_VAL("from", "") },
114 { NAME_VAL("host", "") },
115 { NAME_VAL("if-match", "") },
116 { NAME_VAL("if-modified-since", "") },
117 { NAME_VAL("if-none-match", "") },
118 { NAME_VAL("if-range", "") },
119 { NAME_VAL("if-unmodified-since", "") },
120 { NAME_VAL("last-modified", "") },
121 { NAME_VAL("link", "") },
122 { NAME_VAL("location", "") },
123 { NAME_VAL("max-forwards", "") },
124 { NAME_VAL("proxy-authenticate", "") },
125 { NAME_VAL("proxy-authorization", "") },
126 { NAME_VAL("range", "") },
127 { NAME_VAL("referer", "") },
128 { NAME_VAL("refresh", "") },
129 { NAME_VAL("retry-after", "") },
130 { NAME_VAL("server", "") },
131 { NAME_VAL("set-cookie", "") },
132 { NAME_VAL("strict-transport-security", "") },
133 { NAME_VAL("transfer-encoding", "") },
134 { NAME_VAL("user-agent", "") },
135 { NAME_VAL("vary", "") },
136 { NAME_VAL("via", "") },
137 { NAME_VAL("www-authenticate", "") }
138 };
139
140
141 static const uint32_t static_table_name_hash[HPACK_STATIC_TABLE_SIZE] =
142 {
143 0x653A915Bu, 0xC7742BE4u, 0xC7742BE4u, 0x3513518Du, 0x3513518Du,
144 0xF49F1451u, 0xF49F1451u, 0x672BDA53u, 0x672BDA53u, 0x672BDA53u,
145 0x672BDA53u, 0x672BDA53u, 0x672BDA53u, 0x672BDA53u, 0xCD2C0296u,
146 0xF93AD8A9u, 0x98BD32D3u, 0x1DC691C8u, 0x1AB214F8u, 0x7D3B7A3Bu,
147 0xBEC8E440u, 0xE9C1D9E1u, 0x19D88141u, 0xC25511F2u, 0x16020A90u,
148 0x48011191u, 0x7D9AAB7Eu, 0x48F5CC19u, 0x8847A08Cu, 0x0D19F766u,
149 0x085EF7C5u, 0x0B486ED8u, 0x1A7AA369u, 0x6DE855BAu, 0xA6006EFDu,
150 0xA1BB4284u, 0xAE56E25Fu, 0xB6787110u, 0x791C6A0Du, 0xF2BADABEu,
151 0xD8CA2594u, 0xFBA64C54u, 0x4BEB0951u, 0x6B86C0B5u, 0xC62FECD2u,
152 0x8DA64A26u, 0x6CA35045u, 0xF614D165u, 0xE4D1DF14u, 0xB396750Au,
153 0x01F10233u, 0x798BEE18u, 0x5239F142u, 0x82E1B4E1u, 0x8F7E493Eu,
154 0x85E74C58u, 0xBD17F160u, 0x34C0456Au, 0x1A04DF3Du, 0xB1B15AB2u,
155 0xDDDAB6FFu,
156 };
157
158
159 static const uint32_t static_table_nameval_hash[HPACK_STATIC_TABLE_SIZE] =
160 {
161 0xF8614896u, 0x25D95A15u, 0x33968BB7u, 0xC8C267F6u, 0x8351136Fu,
162 0x98573F68u, 0x16DDE443u, 0x352A6556u, 0xD4F462D2u, 0x125E66E0u,
163 0xD7988BC9u, 0x4C3C90DEu, 0x65E6ECA1u, 0xB05B7B87u, 0x96816317u,
164 0x8BBF5398u, 0x97E01849u, 0xD7B48DD4u, 0x9C180569u, 0xC7C63B45u,
165 0xF4223EE5u, 0x12C8A744u, 0xAA95A0BCu, 0x14F65730u, 0x8410A906u,
166 0x98F440DDu, 0x627E4803u, 0x5A5CC325u, 0x137FC223u, 0x1529262Fu,
167 0x7950B9BDu, 0x51D448A4u, 0x52C167CFu, 0xFB22AA54u, 0x540DB9FEu,
168 0x75A6C685u, 0xE1C54196u, 0xDC0C3733u, 0x6D78CB84u, 0x4F5272CDu,
169 0x9D4170E4u, 0xD4E28BA1u, 0x028C7846u, 0x4E8C1DC3u, 0x684BDDBCu,
170 0xE113A2B0u, 0x55F7BBD1u, 0x15BD3710u, 0xE82B715Du, 0x3674BC1Fu,
171 0x5010D24Bu, 0x953DE1CBu, 0x9F2C92D9u, 0xB2DE5570u, 0xBCA5998Fu,
172 0x0FF5B88Eu, 0x1FED156Bu, 0xDC83E7ECu, 0x07B79E35u, 0xA6D145A9u,
173 0x43638CBAu,
174 };
175
176
177 #define lshpack_arr_init(a) do { \
178 memset((a), 0, sizeof(*(a))); \
179 } while (0)
180
181 #define lshpack_arr_cleanup(a) do { \
182 free((a)->els); \
183 memset((a), 0, sizeof(*(a))); \
184 } while (0)
185
186 #define lshpack_arr_get(a, i) ( \
187 assert((i) < (a)->nelem), \
188 (a)->els[(a)->off + (i)] \
189 )
190
191 #define lshpack_arr_shift(a) ( \
192 assert((a)->nelem > 0), \
193 (a)->nelem -= 1, \
194 (a)->els[(a)->off++] \
195 )
196
197 #define lshpack_arr_pop(a) ( \
198 assert((a)->nelem > 0), \
199 (a)->nelem -= 1, \
200 (a)->els[(a)->off + (a)->nelem] \
201 )
202
203 #define lshpack_arr_count(a) (+(a)->nelem)
204
205 static int
lshpack_arr_push(struct lshpack_arr * arr,uintptr_t val)206 lshpack_arr_push (struct lshpack_arr *arr, uintptr_t val)
207 {
208 uintptr_t *new_els;
209 unsigned n;
210
211 if (arr->off + arr->nelem < arr->nalloc)
212 {
213 arr->els[arr->off + arr->nelem] = val;
214 ++arr->nelem;
215 return 0;
216 }
217
218 if (arr->off > arr->nalloc / 2)
219 {
220 memmove(arr->els, arr->els + arr->off,
221 sizeof(arr->els[0]) * arr->nelem);
222 arr->off = 0;
223 arr->els[arr->nelem] = val;
224 ++arr->nelem;
225 return 0;
226 }
227
228 if (arr->nalloc)
229 n = arr->nalloc * 2;
230 else
231 n = 64;
232 new_els = malloc(n * sizeof(arr->els[0]));
233 if (!new_els)
234 return -1;
235 memcpy(new_els, arr->els + arr->off, sizeof(arr->els[0]) * arr->nelem);
236 free(arr->els);
237 arr->off = 0;
238 arr->els = new_els;
239 arr->nalloc = n;
240 arr->els[arr->off + arr->nelem] = val;
241 ++arr->nelem;
242 return 0;
243 }
244
245 struct lshpack_double_enc_head
246 {
247 struct lshpack_enc_head by_name;
248 struct lshpack_enc_head by_nameval;
249 };
250
251 struct lshpack_enc_table_entry
252 {
253 /* An entry always lives on the `all' and `nameval' lists. If its name
254 * is not in the static table, it also lives on the `name' list.
255 */
256 STAILQ_ENTRY(lshpack_enc_table_entry)
257 ete_next_nameval,
258 ete_next_name,
259 ete_next_all;
260 unsigned ete_id;
261 unsigned ete_nameval_hash;
262 unsigned ete_name_hash;
263 unsigned ete_name_len;
264 unsigned ete_val_len;
265 char ete_buf[];
266 };
267
268 #define ETE_NAME(ete) ((ete)->ete_buf)
269 #define ETE_VALUE(ete) (&(ete)->ete_buf[(ete)->ete_name_len])
270
271
272 #define N_BUCKETS(n_bits) (1U << (n_bits))
273 #define BUCKNO(n_bits, hash) ((hash) & (N_BUCKETS(n_bits) - 1))
274
275
276 /* We estimate average number of entries in the dynamic table to be 1/3
277 * of the theoretical maximum. This number is used to size the history
278 * buffer: we want it large enough to cover recent entries, yet not too
279 * large to cover entries that appear with a period larger than the
280 * dynamic table.
281 */
282 static unsigned
henc_hist_size(unsigned max_capacity)283 henc_hist_size (unsigned max_capacity)
284 {
285 return max_capacity / DYNAMIC_ENTRY_OVERHEAD / 3;
286 }
287
288
289 int
lshpack_enc_init(struct lshpack_enc * enc)290 lshpack_enc_init (struct lshpack_enc *enc)
291 {
292 struct lshpack_double_enc_head *buckets;
293 unsigned nbits = 2;
294 unsigned i;
295
296 buckets = malloc(sizeof(buckets[0]) * N_BUCKETS(nbits));
297 if (!buckets)
298 return -1;
299
300 for (i = 0; i < N_BUCKETS(nbits); ++i)
301 {
302 STAILQ_INIT(&buckets[i].by_name);
303 STAILQ_INIT(&buckets[i].by_nameval);
304 }
305
306 memset(enc, 0, sizeof(*enc));
307 STAILQ_INIT(&enc->hpe_all_entries);
308 enc->hpe_max_capacity = INITIAL_DYNAMIC_TABLE_SIZE;
309 enc->hpe_buckets = buckets;
310 /* The initial value of the entry ID is completely arbitrary. As long as
311 * there are fewer than 2^32 dynamic table entries, the math to calculate
312 * the entry ID works. To prove to ourselves that the wraparound works
313 * and to have the unit tests cover it, we initialize the next ID so that
314 * it is just about to wrap around.
315 */
316 enc->hpe_next_id = ~0 - 3;
317 enc->hpe_nbits = nbits;
318 enc->hpe_nelem = 0;
319 return 0;
320 }
321
322
323 void
lshpack_enc_cleanup(struct lshpack_enc * enc)324 lshpack_enc_cleanup (struct lshpack_enc *enc)
325 {
326 struct lshpack_enc_table_entry *entry, *next;
327 for (entry = STAILQ_FIRST(&enc->hpe_all_entries); entry; entry = next)
328 {
329 next = STAILQ_NEXT(entry, ete_next_all);
330 free(entry);
331 }
332 free(enc->hpe_hist_buf);
333 free(enc->hpe_buckets);
334 }
335
336
337 static int
henc_use_hist(struct lshpack_enc * enc)338 henc_use_hist (struct lshpack_enc *enc)
339 {
340 unsigned hist_size;
341
342 if (enc->hpe_hist_buf)
343 return 0;
344
345 hist_size = henc_hist_size(INITIAL_DYNAMIC_TABLE_SIZE);
346 if (!hist_size)
347 return 0;
348
349 enc->hpe_hist_buf = malloc(sizeof(enc->hpe_hist_buf[0]) * (hist_size + 1));
350 if (!enc->hpe_hist_buf)
351 return -1;
352
353 enc->hpe_hist_size = hist_size;
354 enc->hpe_flags |= LSHPACK_ENC_USE_HIST;
355 return 0;
356 }
357
358
359 int
lshpack_enc_use_hist(struct lshpack_enc * enc,int on)360 lshpack_enc_use_hist (struct lshpack_enc *enc, int on)
361 {
362 if (on)
363 return henc_use_hist(enc);
364 else
365 {
366 enc->hpe_flags &= ~LSHPACK_ENC_USE_HIST;
367 free(enc->hpe_hist_buf);
368 enc->hpe_hist_buf = NULL;
369 enc->hpe_hist_size = 0;
370 enc->hpe_hist_idx = 0;
371 enc->hpe_hist_wrapped = 0;
372 return 0;
373 }
374 }
375
376
377 int
lshpack_enc_hist_used(const struct lshpack_enc * enc)378 lshpack_enc_hist_used (const struct lshpack_enc *enc)
379 {
380 return (enc->hpe_flags & LSHPACK_ENC_USE_HIST) != 0;
381 }
382
383
384 #define LSHPACK_XXH_SEED 39378473
385 #define XXH_NAMEVAL_WIDTH 9
386 #define XXH_NAMEVAL_SHIFT 0
387 #define XXH_NAME_WIDTH 9
388 #define XXH_NAME_SHIFT 0
389
390 static const unsigned char nameval2id[ 1 << XXH_NAMEVAL_WIDTH ] =
391 {
392 [150] = 1, [21] = 2, [439] = 3, [502] = 4, [367] = 5,
393 [360] = 6, [67] = 7, [342] = 8, [210] = 9, [224] = 10,
394 [457] = 11, [222] = 12, [161] = 13, [391] = 14, [279] = 15,
395 [408] = 16, [73] = 17, [468] = 18, [361] = 19, [325] = 20,
396 [229] = 21, [324] = 22, [188] = 23, [304] = 24, [262] = 25,
397 [221] = 26, [3] = 27, [293] = 28, [35] = 29, [47] = 30,
398 [445] = 31, [164] = 32, [463] = 33, [84] = 34, [510] = 35,
399 [133] = 36, [406] = 37, [307] = 38, [388] = 39, [205] = 40,
400 [228] = 41, [417] = 42, [70] = 43, [451] = 44, [444] = 45,
401 [176] = 46, [465] = 47, [272] = 48, [349] = 49, [31] = 50,
402 [75] = 51, [459] = 52, [217] = 53, [368] = 54, [399] = 55,
403 [142] = 56, [363] = 57, [492] = 58, [53] = 59, [425] = 60,
404 [186] = 61,
405 };
406
407 static const unsigned char name2id[ 1 << XXH_NAME_WIDTH ] =
408 {
409 [347] = 1, [484] = 2, [397] = 4, [81] = 6, [83] = 8,
410 [150] = 15, [169] = 16, [211] = 17, [456] = 18, [248] = 19,
411 [59] = 20, [64] = 21, [481] = 22, [321] = 23, [498] = 24,
412 [144] = 25, [401] = 26, [382] = 27, [25] = 28, [140] = 29,
413 [358] = 30, [453] = 31, [216] = 32, [361] = 33, [442] = 34,
414 [253] = 35, [132] = 36, [95] = 37, [272] = 38, [13] = 39,
415 [190] = 40, [404] = 41, [84] = 42, [337] = 43, [181] = 44,
416 [210] = 45, [38] = 46, [69] = 47, [357] = 48, [276] = 49,
417 [266] = 50, [51] = 51, [24] = 52, [322] = 53, [225] = 54,
418 [318] = 55, [88] = 56, [352] = 57, [362] = 58, [317] = 59,
419 [178] = 60, [255] = 61,
420 };
421
422 //not find return 0, otherwise return the index
423 #if !LS_HPACK_EMIT_TEST_CODE
424 static
425 #endif
426 unsigned
lshpack_enc_get_static_nameval(const struct lsxpack_header * input)427 lshpack_enc_get_static_nameval (const struct lsxpack_header *input)
428 {
429 unsigned i;
430
431 assert(input->name_len > 0);
432 assert(input->flags & LSXPACK_NAMEVAL_HASH);
433 i = (input->nameval_hash >> XXH_NAMEVAL_SHIFT) & ((1 << XXH_NAMEVAL_WIDTH) - 1);
434 if (nameval2id[i])
435 {
436 i = nameval2id[i] - 1;
437 if (static_table[i].name_len == input->name_len
438 && static_table[i].val_len == input->val_len
439 && memcmp(lsxpack_header_get_name(input), static_table[i].name, input->name_len) == 0
440 && memcmp(lsxpack_header_get_value(input), static_table[i].val, input->val_len) == 0)
441 {
442 return i + 1;
443 }
444 }
445
446 return 0;
447 }
448
449 #if !LS_HPACK_EMIT_TEST_CODE
450 static
451 #endif
452 unsigned
lshpack_enc_get_static_name(const struct lsxpack_header * input)453 lshpack_enc_get_static_name (const struct lsxpack_header *input)
454 {
455 unsigned i;
456
457 assert(input->flags & LSXPACK_NAME_HASH);
458 i = (input->name_hash >> XXH_NAME_SHIFT) & ((1 << XXH_NAME_WIDTH) - 1);
459 if (name2id[i])
460 {
461 i = name2id[i] - 1;
462 if (static_table[i].name_len == input->name_len
463 && memcmp(lsxpack_header_get_name(input), static_table[i].name,
464 input->name_len) == 0)
465 {
466 return i + 1;
467 }
468 }
469
470 return 0;
471 }
472
473
474 static void
update_hash(struct lsxpack_header * input)475 update_hash (struct lsxpack_header *input)
476 {
477 if (!(input->flags & LSXPACK_NAME_HASH))
478 input->name_hash = XXH32(lsxpack_header_get_name(input),
479 input->name_len, LSHPACK_XXH_SEED);
480 else
481 assert(input->name_hash == XXH32(lsxpack_header_get_name(input),
482 input->name_len, LSHPACK_XXH_SEED));
483
484 if (!(input->flags & LSXPACK_NAMEVAL_HASH))
485 input->nameval_hash = XXH32(input->buf + input->val_offset,
486 input->val_len, input->name_hash);
487 else
488 assert(input->nameval_hash == XXH32(input->buf + input->val_offset,
489 input->val_len, input->name_hash));
490
491 input->flags |= (LSXPACK_NAME_HASH | LSXPACK_NAMEVAL_HASH);
492 }
493
494
495 unsigned
lshpack_enc_get_stx_tab_id(struct lsxpack_header * input)496 lshpack_enc_get_stx_tab_id (struct lsxpack_header *input)
497 {
498 unsigned i;
499
500 update_hash(input);
501
502 i = (input->nameval_hash >> XXH_NAMEVAL_SHIFT) & ((1 << XXH_NAMEVAL_WIDTH) - 1);
503 if (nameval2id[i])
504 {
505 i = nameval2id[i] - 1;
506 if (static_table[i].name_len == input->name_len
507 && static_table[i].val_len == input->val_len
508 && memcmp(lsxpack_header_get_name(input), static_table[i].name,
509 input->name_len) == 0
510 && memcmp(input->buf + input->val_offset, static_table[i].val,
511 input->val_len) == 0)
512 {
513 return i + 1;
514 }
515 }
516
517 i = (input->name_hash >> XXH_NAME_SHIFT) & ((1 << XXH_NAME_WIDTH) - 1);
518 if (name2id[i])
519 {
520 i = name2id[i] - 1;
521 if (static_table[i].name_len == input->name_len
522 && memcmp(lsxpack_header_get_name(input), static_table[i].name,
523 input->name_len) == 0)
524 {
525 return i + 1;
526 }
527 }
528
529 return 0;
530 }
531
532
533 /* Given a dynamic entry, return its table ID */
534 static unsigned
henc_calc_table_id(const struct lshpack_enc * enc,const struct lshpack_enc_table_entry * entry)535 henc_calc_table_id (const struct lshpack_enc *enc,
536 const struct lshpack_enc_table_entry *entry)
537 {
538 return HPACK_STATIC_TABLE_SIZE
539 + (enc->hpe_next_id - entry->ete_id)
540 ;
541 }
542
543
544 static unsigned
henc_find_table_id(struct lshpack_enc * enc,lsxpack_header_t * input,int * val_matched)545 henc_find_table_id (struct lshpack_enc *enc, lsxpack_header_t *input,
546 int *val_matched)
547 {
548 struct lshpack_enc_table_entry *entry;
549 unsigned buckno, id;
550 const char *val_ptr = input->buf + input->val_offset;
551 const char *name;
552 unsigned int name_len;
553
554 name_len = input->name_len;
555 name = lsxpack_header_get_name(input);
556
557 /* First, look for a match in the static table: */
558 if (input->hpack_index)
559 {
560 id = input->hpack_index - 1;
561 #ifndef NDEBUG
562 if (name_len)
563 {
564 lsxpack_header_t input_copy = *input;
565 const unsigned hpack_index = lshpack_enc_get_stx_tab_id(&input_copy);
566 assert(input_copy.hpack_index == hpack_index);
567 }
568 #endif
569 if (id <= LSHPACK_HDR_ACCEPT_ENCODING || input->val_len == 0)
570 {
571 if (static_table[id].val_len == input->val_len
572 && memcmp(val_ptr, static_table[id].val, input->val_len) == 0)
573 {
574 input->flags |= LSXPACK_HPACK_VAL_MATCHED;
575 *val_matched = 1;
576 return input->hpack_index;
577 }
578 }
579 if (!name_len)
580 {
581 name = static_table[id].name;
582 name_len = static_table[id].name_len;
583 }
584
585 if (!(input->flags & LSXPACK_NAME_HASH))
586 input->name_hash = static_table_name_hash[id];
587 else
588 assert(input->name_hash == static_table_name_hash[id]);
589 if (!(input->flags & LSXPACK_NAMEVAL_HASH))
590 input->nameval_hash = XXH32(val_ptr, input->val_len,
591 input->name_hash);
592 else
593 assert(input->nameval_hash == XXH32(val_ptr, input->val_len,
594 input->name_hash));
595 input->flags |= (LSXPACK_NAME_HASH | LSXPACK_NAMEVAL_HASH);
596 }
597 else
598 {
599 update_hash(input);
600 input->hpack_index = lshpack_enc_get_static_nameval(input);
601 if (input->hpack_index != LSHPACK_HDR_UNKNOWN)
602 {
603 input->flags |= LSXPACK_HPACK_VAL_MATCHED;
604 *val_matched = 1;
605 return input->hpack_index;
606 }
607 }
608
609 /* Search by name and value: */
610 buckno = BUCKNO(enc->hpe_nbits, input->nameval_hash);
611 STAILQ_FOREACH(entry, &enc->hpe_buckets[buckno].by_nameval,
612 ete_next_nameval)
613 if (input->nameval_hash == entry->ete_nameval_hash &&
614 name_len == entry->ete_name_len &&
615 input->val_len == entry->ete_val_len &&
616 0 == memcmp(name, ETE_NAME(entry), name_len) &&
617 0 == memcmp(val_ptr, ETE_VALUE(entry), input->val_len))
618 {
619 *val_matched = 1;
620 return henc_calc_table_id(enc, entry);
621 }
622
623 /* Name/value match is not found, look for header: */
624 if (input->hpack_index == LSHPACK_HDR_UNKNOWN)
625 input->hpack_index = lshpack_enc_get_static_name(input);
626 if (input->hpack_index != LSHPACK_HDR_UNKNOWN)
627 {
628 input->flags &= ~LSXPACK_HPACK_VAL_MATCHED;
629 return input->hpack_index;
630 }
631
632 /* Search by name only: */
633 buckno = BUCKNO(enc->hpe_nbits, input->name_hash);
634 STAILQ_FOREACH(entry, &enc->hpe_buckets[buckno].by_name, ete_next_name)
635 if (input->name_hash == entry->ete_name_hash &&
636 input->name_len == entry->ete_name_len &&
637 0 == memcmp(name, ETE_NAME(entry), name_len))
638 {
639 input->flags &= ~LSXPACK_HPACK_VAL_MATCHED;
640 return henc_calc_table_id(enc, entry);
641 }
642
643 return 0;
644 }
645
646
647 #if !LS_HPACK_EMIT_TEST_CODE
648 static
649 #endif
650 unsigned char *
lshpack_enc_enc_int(unsigned char * dst,unsigned char * const end,uint32_t value,uint8_t prefix_bits)651 lshpack_enc_enc_int (unsigned char *dst, unsigned char *const end,
652 uint32_t value, uint8_t prefix_bits)
653 {
654 unsigned char *const dst_orig = dst;
655
656 /* This function assumes that at least one byte is available */
657 assert(dst < end);
658 if (value < (uint32_t)(1 << prefix_bits) - 1)
659 *dst++ |= value;
660 else
661 {
662 *dst++ |= (1 << prefix_bits) - 1;
663 value -= (1 << prefix_bits) - 1;
664 while (value >= 128)
665 {
666 if (dst < end)
667 {
668 *dst++ = (0x80 | value);
669 value >>= 7;
670 }
671 else
672 return dst_orig;
673 }
674 if (dst < end)
675 *dst++ = value;
676 else
677 return dst_orig;
678 }
679 return dst;
680 }
681
682
683 /* This whole pragma business has to do with turning off uninitialized warnings.
684 * We do it for gcc and clang. Other compilers get slightly slower code, where
685 * unnecessary initialization is performed.
686 */
687 #if __GNUC__
688 #pragma GCC diagnostic ignored "-Wunknown-pragmas"
689 #pragma GCC diagnostic ignored "-Wimplicit-fallthrough"
690 #if __clang__
691 #pragma GCC diagnostic ignored "-Wunknown-warning-option"
692 #endif
693 #endif
694
695
696 static int
lshpack_enc_huff_encode(const unsigned char * src,const unsigned char * const src_end,unsigned char * const dst,int dst_len)697 lshpack_enc_huff_encode (const unsigned char *src,
698 const unsigned char *const src_end, unsigned char *const dst, int dst_len)
699 {
700 unsigned char *p_dst = dst;
701 unsigned char *dst_end = p_dst + dst_len;
702 uintptr_t bits; /* OK not to initialize this variable */
703 unsigned bits_used = 0, adj;
704 struct encode_el cur_enc_code;
705 #if __GNUC__ && __GNUC__ >= 5 && !defined(__COVERITY__)
706 #pragma GCC diagnostic push
707 #pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
708 #pragma GCC diagnostic ignored "-Wuninitialized"
709 #else
710 bits = 0;
711 #endif
712 #if LS_HPACK_USE_LARGE_TABLES
713 const struct henc *henc;
714 uint16_t idx;
715
716 while (src + sizeof(bits) * 8 / 5 + sizeof(idx) < src_end
717 && p_dst + sizeof(bits) <= dst_end)
718 {
719 memcpy(&idx, src, 2);
720 henc = &hencs[idx];
721 src += 2;
722 while (bits_used + henc->lens < sizeof(bits) * 8)
723 {
724 bits <<= henc->lens;
725 bits |= henc->code;
726 bits_used += henc->lens;
727 memcpy(&idx, src, 2);
728 henc = &hencs[idx];
729 src += 2;
730 }
731 if (henc->lens < 64)
732 {
733 bits <<= sizeof(bits) * 8 - bits_used;
734 bits_used = henc->lens - (sizeof(bits) * 8 - bits_used);
735 bits |= henc->code >> bits_used;
736 #if UINTPTR_MAX == 18446744073709551615ull
737 *p_dst++ = bits >> 56;
738 *p_dst++ = bits >> 48;
739 *p_dst++ = bits >> 40;
740 *p_dst++ = bits >> 32;
741 #endif
742 *p_dst++ = bits >> 24;
743 *p_dst++ = bits >> 16;
744 *p_dst++ = bits >> 8;
745 *p_dst++ = bits;
746 bits = henc->code; /* OK not to clear high bits */
747 }
748 else
749 {
750 src -= 2;
751 break;
752 }
753 }
754 #endif
755
756 while (src != src_end)
757 {
758 cur_enc_code = encode_table[*src++];
759 if (bits_used + cur_enc_code.bits < sizeof(bits) * 8)
760 {
761 bits <<= cur_enc_code.bits;
762 bits |= cur_enc_code.code;
763 bits_used += cur_enc_code.bits;
764 continue;
765 }
766 else if (p_dst + sizeof(bits) <= dst_end)
767 {
768 #ifdef __COVERITY__
769 assert(bits_used > 0);
770 if (0 == bits_used || bits_used >= sizeof(bits)*8) abort();
771 #endif
772 bits <<= sizeof(bits) * 8 - bits_used;
773 bits_used = cur_enc_code.bits - (sizeof(bits) * 8 - bits_used);
774 bits |= cur_enc_code.code >> bits_used;
775 #if UINTPTR_MAX == 18446744073709551615ull
776 *p_dst++ = bits >> 56;
777 *p_dst++ = bits >> 48;
778 *p_dst++ = bits >> 40;
779 *p_dst++ = bits >> 32;
780 #endif
781 *p_dst++ = bits >> 24;
782 *p_dst++ = bits >> 16;
783 *p_dst++ = bits >> 8;
784 *p_dst++ = bits;
785 bits = cur_enc_code.code; /* OK not to clear high bits */
786 }
787 else
788 return -1;
789 }
790
791 adj = bits_used + (-bits_used & 7); /* Round up to 8 */
792 if (bits_used && p_dst + (adj >> 3) <= dst_end)
793 {
794 bits <<= -bits_used & 7; /* Align to byte boundary */
795 bits |= ((1 << (-bits_used & 7)) - 1); /* EOF */
796 switch (adj >> 3)
797 { /* Write out */
798 #if UINTPTR_MAX == 18446744073709551615ull
799 case 8: *p_dst++ = bits >> 56;
800 /* fall through */
801 case 7: *p_dst++ = bits >> 48;
802 /* fall through */
803 case 6: *p_dst++ = bits >> 40;
804 /* fall through */
805 case 5: *p_dst++ = bits >> 32;
806 #endif
807 /* fall through */
808 case 4: *p_dst++ = bits >> 24;
809 /* fall through */
810 case 3: *p_dst++ = bits >> 16;
811 /* fall through */
812 case 2: *p_dst++ = bits >> 8;
813 /* fall through */
814 default: *p_dst++ = bits;
815 }
816 return p_dst - dst;
817 }
818 else if (p_dst + (adj >> 3) <= dst_end)
819 return p_dst - dst;
820 else
821 return -1;
822 #if __GNUC__ && __GNUC__ >= 5 && !defined(__COVERITY__)
823 #pragma GCC diagnostic pop
824 #endif
825 }
826
827
828 #if !LS_HPACK_EMIT_TEST_CODE
829 static
830 #endif
831 int
lshpack_enc_enc_str(unsigned char * const dst,size_t dst_len,const unsigned char * str,unsigned str_len)832 lshpack_enc_enc_str (unsigned char *const dst, size_t dst_len,
833 const unsigned char *str, unsigned str_len)
834 {
835 unsigned char size_buf[4];
836 unsigned char *p;
837 unsigned size_len;
838 int rc;
839
840 if (dst_len > 1)
841 /* We guess that the string size fits into a single byte -- meaning
842 * compressed string of size 126 and smaller -- which is the normal
843 * case. Thus, we immediately write compressed string to the output
844 * buffer. If our guess is not correct, we fix it later.
845 */
846 rc = lshpack_enc_huff_encode(str, str + str_len, dst + 1, dst_len - 1);
847 else if (dst_len == 1)
848 /* Here, the call can only succeed if the string to encode is empty. */
849 rc = 0;
850 else
851 return -1;
852
853 /*
854 * Check if need huffman encoding or not
855 * Comment: (size_t)rc <= str_len = means if same length, still use
856 * Huffman
857 * ^
858 */
859 if (rc > 0 && (size_t)rc <= str_len)
860 {
861 if (rc < 127)
862 {
863 *dst = 0x80 | rc;
864 return 1 + rc;
865 }
866 size_buf[0] = 0x80;
867 str_len = rc;
868 str = dst + 1;
869 }
870 else if (str_len <= dst_len - 1)
871 {
872 if (str_len < 127)
873 {
874 *dst = (unsigned char) str_len;
875 memcpy(dst + 1, str, str_len);
876 return 1 + str_len;
877 }
878 size_buf[0] = 0x00;
879 }
880 else
881 return -1;
882
883 /* The guess of one-byte size was incorrect. Perform necessary
884 * adjustments.
885 */
886 p = lshpack_enc_enc_int(size_buf, size_buf + sizeof(size_buf), str_len, 7);
887 if (p == size_buf)
888 return -1;
889
890 size_len = p - size_buf;
891 assert(size_len > 1);
892
893 /* Check if there is enough room in the output buffer for both
894 * encoded size and the string.
895 */
896 if (size_len + str_len > dst_len)
897 return -1;
898
899 memmove(dst + size_len, str, str_len);
900 memcpy(dst, size_buf, size_len);
901 return size_len + str_len;
902 }
903
904
905 static void
henc_drop_oldest_entry(struct lshpack_enc * enc)906 henc_drop_oldest_entry (struct lshpack_enc *enc)
907 {
908 struct lshpack_enc_table_entry *entry;
909 unsigned buckno;
910
911 entry = STAILQ_FIRST(&enc->hpe_all_entries);
912 assert(entry);
913 STAILQ_REMOVE_HEAD(&enc->hpe_all_entries, ete_next_all);
914 buckno = BUCKNO(enc->hpe_nbits, entry->ete_nameval_hash);
915 assert(entry == STAILQ_FIRST(&enc->hpe_buckets[buckno].by_nameval));
916 STAILQ_REMOVE_HEAD(&enc->hpe_buckets[buckno].by_nameval, ete_next_nameval);
917 buckno = BUCKNO(enc->hpe_nbits, entry->ete_name_hash);
918 if (entry == STAILQ_FIRST(&enc->hpe_buckets[buckno].by_name))
919 STAILQ_REMOVE_HEAD(&enc->hpe_buckets[buckno].by_name, ete_next_name);
920
921 enc->hpe_cur_capacity -= DYNAMIC_ENTRY_OVERHEAD + entry->ete_name_len
922 + entry->ete_val_len;
923 --enc->hpe_nelem;
924 free(entry);
925 }
926
927
928 static void
henc_remove_overflow_entries(struct lshpack_enc * enc)929 henc_remove_overflow_entries (struct lshpack_enc *enc)
930 {
931 while (enc->hpe_cur_capacity > enc->hpe_max_capacity)
932 henc_drop_oldest_entry(enc);
933 }
934
935
936 static int
henc_grow_tables(struct lshpack_enc * enc)937 henc_grow_tables (struct lshpack_enc *enc)
938 {
939 struct lshpack_double_enc_head *new_buckets, *new[2];
940 struct lshpack_enc_table_entry *entry;
941 unsigned n, old_nbits;
942 int idx;
943
944 old_nbits = enc->hpe_nbits;
945 new_buckets = malloc(sizeof(enc->hpe_buckets[0])
946 * N_BUCKETS(old_nbits + 1));
947 if (!new_buckets)
948 return -1;
949
950 for (n = 0; n < N_BUCKETS(old_nbits); ++n)
951 {
952 new[0] = &new_buckets[n];
953 new[1] = &new_buckets[n + N_BUCKETS(old_nbits)];
954 STAILQ_INIT(&new[0]->by_name);
955 STAILQ_INIT(&new[1]->by_name);
956 STAILQ_INIT(&new[0]->by_nameval);
957 STAILQ_INIT(&new[1]->by_nameval);
958 while ((entry = STAILQ_FIRST(&enc->hpe_buckets[n].by_name)))
959 {
960 STAILQ_REMOVE_HEAD(&enc->hpe_buckets[n].by_name, ete_next_name);
961 idx = (BUCKNO(old_nbits + 1, entry->ete_name_hash)
962 >> old_nbits) & 1;
963 STAILQ_INSERT_TAIL(&new[idx]->by_name, entry, ete_next_name);
964 }
965 while ((entry = STAILQ_FIRST(&enc->hpe_buckets[n].by_nameval)))
966 {
967 STAILQ_REMOVE_HEAD(&enc->hpe_buckets[n].by_nameval,
968 ete_next_nameval);
969 idx = (BUCKNO(old_nbits + 1, entry->ete_nameval_hash)
970 >> old_nbits) & 1;
971 STAILQ_INSERT_TAIL(&new[idx]->by_nameval, entry,
972 ete_next_nameval);
973 }
974 }
975
976 free(enc->hpe_buckets);
977 enc->hpe_nbits = old_nbits + 1;
978 enc->hpe_buckets = new_buckets;
979 return 0;
980 }
981
982
983 #if !LS_HPACK_EMIT_TEST_CODE
984 static
985 #endif
986 int
lshpack_enc_push_entry(struct lshpack_enc * enc,const struct lsxpack_header * input)987 lshpack_enc_push_entry (struct lshpack_enc *enc,
988 const struct lsxpack_header *input)
989 {
990 unsigned buckno;
991 struct lshpack_enc_table_entry *entry;
992 size_t size;
993 const char *name;
994 unsigned int name_len;
995
996 if (enc->hpe_nelem >= N_BUCKETS(enc->hpe_nbits) / 2 &&
997 0 != henc_grow_tables(enc))
998 return -1;
999 name_len = input->name_len;
1000 if (name_len == 0)
1001 {
1002 assert(input->hpack_index != LSHPACK_HDR_UNKNOWN);
1003 name = static_table[input->hpack_index - 1].name;
1004 name_len = static_table[input->hpack_index - 1].name_len;
1005 }
1006 else
1007 name = lsxpack_header_get_name(input);
1008 size = sizeof(*entry) + name_len + input->val_len;
1009 entry = malloc(size);
1010 if (!entry)
1011 return -1;
1012
1013 entry->ete_name_hash = input->name_hash;
1014 entry->ete_nameval_hash = input->nameval_hash;
1015 entry->ete_name_len = name_len;
1016 entry->ete_val_len = input->val_len;
1017 entry->ete_id = enc->hpe_next_id++;
1018 memcpy(ETE_NAME(entry), name, name_len);
1019 memcpy(ETE_VALUE(entry), input->buf + input->val_offset, input->val_len);
1020
1021 STAILQ_INSERT_TAIL(&enc->hpe_all_entries, entry, ete_next_all);
1022 buckno = BUCKNO(enc->hpe_nbits, input->nameval_hash);
1023 STAILQ_INSERT_TAIL(&enc->hpe_buckets[buckno].by_nameval, entry,
1024 ete_next_nameval);
1025 if (input->hpack_index == LSHPACK_HDR_UNKNOWN)
1026 {
1027 buckno = BUCKNO(enc->hpe_nbits, input->name_hash);
1028 STAILQ_INSERT_TAIL(&enc->hpe_buckets[buckno].by_name, entry,
1029 ete_next_name);
1030 }
1031 enc->hpe_cur_capacity += DYNAMIC_ENTRY_OVERHEAD + name_len
1032 + input->val_len;
1033 ++enc->hpe_nelem;
1034 henc_remove_overflow_entries(enc);
1035 return 0;
1036 }
1037
1038
1039 static void
henc_resize_history(struct lshpack_enc * enc)1040 henc_resize_history (struct lshpack_enc *enc)
1041 {
1042 uint32_t *hist_buf;
1043 unsigned hist_size, first, count, i, j;
1044
1045 hist_size = henc_hist_size(enc->hpe_max_capacity);
1046
1047 if (hist_size == enc->hpe_hist_size)
1048 return;
1049
1050 if (hist_size == 0)
1051 {
1052 free(enc->hpe_hist_buf);
1053 enc->hpe_hist_buf = NULL;
1054 enc->hpe_hist_size = 0;
1055 enc->hpe_hist_idx = 0;
1056 enc->hpe_hist_wrapped = 0;
1057 return;
1058 }
1059
1060 hist_buf = malloc(sizeof(hist_buf[0]) * (hist_size + 1));
1061 if (!hist_buf)
1062 return;
1063
1064 if (enc->hpe_hist_wrapped)
1065 {
1066 first = (enc->hpe_hist_idx + 1) % enc->hpe_hist_size;
1067 count = enc->hpe_hist_size;
1068 }
1069 else
1070 {
1071 first = 0;
1072 count = enc->hpe_hist_idx;
1073 }
1074 for (i = 0, j = 0; count > 0 && j < hist_size; ++i, ++j, --count)
1075 hist_buf[j] = enc->hpe_hist_buf[ (first + i) % enc->hpe_hist_size ];
1076 enc->hpe_hist_size = hist_size;
1077 enc->hpe_hist_idx = j % hist_size;
1078 enc->hpe_hist_wrapped = enc->hpe_hist_idx == 0;
1079 free(enc->hpe_hist_buf);
1080 enc->hpe_hist_buf = hist_buf;
1081 }
1082
1083
1084 /* Returns true if `nameval_hash' was already in history, false otherwise. */
1085 static int
henc_hist_add(struct lshpack_enc * enc,uint32_t nameval_hash)1086 henc_hist_add (struct lshpack_enc *enc, uint32_t nameval_hash)
1087 {
1088 unsigned last;
1089 uint32_t *p;
1090
1091 if (enc->hpe_hist_wrapped)
1092 last = enc->hpe_hist_size;
1093 else
1094 last = enc->hpe_hist_idx;
1095
1096 enc->hpe_hist_buf[ last ] = nameval_hash;
1097 for (p = enc->hpe_hist_buf; *p != nameval_hash; ++p)
1098 ;
1099 enc->hpe_hist_buf[ enc->hpe_hist_idx ] = nameval_hash;
1100 enc->hpe_hist_idx = (enc->hpe_hist_idx + 1) % enc->hpe_hist_size;
1101 enc->hpe_hist_wrapped |= enc->hpe_hist_idx == 0;
1102
1103 return p < enc->hpe_hist_buf + last;
1104 }
1105
1106
1107 unsigned char *
lshpack_enc_encode(struct lshpack_enc * enc,unsigned char * dst,unsigned char * dst_end,lsxpack_header_t * input)1108 lshpack_enc_encode (struct lshpack_enc *enc, unsigned char *dst,
1109 unsigned char *dst_end, lsxpack_header_t *input)
1110 {
1111 //indexed_type: 0, Add, 1,: without, 2: never
1112 static const char indexed_prefix_number[] = {0x40, 0x00, 0x10};
1113 unsigned char *const dst_org = dst;
1114 int rc;
1115 int val_matched = 0;
1116 unsigned table_id;
1117
1118 if (dst_end <= dst)
1119 return dst_org;
1120
1121 if (input->flags & LSXPACK_HPACK_VAL_MATCHED)
1122 {
1123 assert(input->hpack_index != LSHPACK_HDR_UNKNOWN);
1124 assert(input->val_len == static_table[input->hpack_index - 1].val_len);
1125 assert(memcmp(lsxpack_header_get_value(input),
1126 static_table[input->hpack_index - 1].val,
1127 input->val_len) == 0);
1128 table_id = input->hpack_index;
1129 val_matched = 1;
1130 }
1131 else
1132 {
1133 if (input->flags & LSXPACK_NEVER_INDEX)
1134 input->indexed_type = 2;
1135 table_id = henc_find_table_id(enc, input, &val_matched);
1136 if (enc->hpe_hist_buf)
1137 {
1138 rc = henc_hist_add(enc, input->nameval_hash);
1139 if (!rc && enc->hpe_hist_wrapped && input->indexed_type == 0)
1140 input->indexed_type = 1;
1141 }
1142 }
1143
1144 if (table_id > 0)
1145 {
1146 if (val_matched)
1147 {
1148 // LSXPACK_VAL_MATCHED MUST NOT set for dynamic table
1149 // otherwise, it may cause trouble when feed the input to a different encoder.
1150 if (table_id > HPACK_STATIC_TABLE_SIZE)
1151 assert(!(input->flags & LSXPACK_HPACK_VAL_MATCHED));
1152
1153 *dst = 0x80;
1154 dst = lshpack_enc_enc_int(dst, dst_end, table_id, 7);
1155 /* No need to check return value: we pass it up as-is because
1156 * the behavior is the same.
1157 */
1158 return dst;
1159 }
1160 else
1161 {
1162 *dst = indexed_prefix_number[input->indexed_type];
1163 dst = lshpack_enc_enc_int(dst, dst_end, table_id,
1164 ((input->indexed_type == 0) ? 6 : 4));
1165 if (dst == dst_org)
1166 return dst_org;
1167 }
1168 }
1169 else
1170 {
1171 assert(input->name_len > 0);
1172 *dst++ = indexed_prefix_number[input->indexed_type];
1173 rc = lshpack_enc_enc_str(dst, dst_end - dst,
1174 (unsigned char *)lsxpack_header_get_name(input),
1175 input->name_len);
1176 if (rc < 0)
1177 return dst_org; //Failed to enc this header, return unchanged ptr.
1178 dst += rc;
1179 }
1180
1181 rc = lshpack_enc_enc_str(dst, dst_end - dst,
1182 (const unsigned char *)input->buf + input->val_offset,
1183 input->val_len);
1184 if (rc < 0)
1185 return dst_org; //Failed to enc this header, return unchanged ptr.
1186 dst += rc;
1187
1188 if (input->indexed_type == 0)
1189 {
1190 rc = lshpack_enc_push_entry(enc, input);
1191 if (rc != 0)
1192 return dst_org; //Failed to enc this header, return unchanged ptr.
1193 }
1194
1195 return dst;
1196 }
1197
1198
1199 void
lshpack_enc_set_max_capacity(struct lshpack_enc * enc,unsigned max_capacity)1200 lshpack_enc_set_max_capacity (struct lshpack_enc *enc, unsigned max_capacity)
1201 {
1202 enc->hpe_max_capacity = max_capacity;
1203 henc_remove_overflow_entries(enc);
1204 if (lshpack_enc_hist_used(enc))
1205 henc_resize_history(enc);
1206 }
1207
1208 #if LS_HPACK_EMIT_TEST_CODE
1209 void
lshpack_enc_iter_init(struct lshpack_enc * enc,void ** iter)1210 lshpack_enc_iter_init (struct lshpack_enc *enc, void **iter)
1211 {
1212 *iter = STAILQ_FIRST(&enc->hpe_all_entries);
1213 }
1214
1215
1216 /* Returns 0 if entry is found */
1217 int
lshpack_enc_iter_next(struct lshpack_enc * enc,void ** iter,struct enc_dyn_table_entry * retval)1218 lshpack_enc_iter_next (struct lshpack_enc *enc, void **iter,
1219 struct enc_dyn_table_entry *retval)
1220 {
1221 const struct lshpack_enc_table_entry *entry;
1222
1223 entry = *iter;
1224 if (!entry)
1225 return -1;
1226
1227 *iter = STAILQ_NEXT(entry, ete_next_all);
1228
1229 retval->name = ETE_NAME(entry);
1230 retval->value = ETE_VALUE(entry);
1231 retval->name_len = entry->ete_name_len;
1232 retval->value_len = entry->ete_val_len;
1233 retval->entry_id = henc_calc_table_id(enc, entry);
1234 return 0;
1235 }
1236 #endif
1237
1238
1239 /* Dynamic table entry: */
1240 struct dec_table_entry
1241 {
1242 unsigned dte_name_len;
1243 unsigned dte_val_len;
1244 #if LSHPACK_DEC_CALC_HASH
1245 uint32_t dte_name_hash;
1246 uint32_t dte_nameval_hash;
1247 enum {
1248 DTEF_NAME_HASH = LSXPACK_NAME_HASH,
1249 DTEF_NAMEVAL_HASH = LSXPACK_NAMEVAL_HASH,
1250 } dte_flags:8;
1251 #endif
1252 uint8_t dte_name_idx;
1253 char dte_buf[]; /* Contains both name and value */
1254 };
1255
1256 #define DTE_NAME(dte) ((dte)->dte_buf)
1257 #define DTE_VALUE(dte) (&(dte)->dte_buf[(dte)->dte_name_len])
1258
1259 enum
1260 {
1261 HPACK_HUFFMAN_FLAG_ACCEPTED = 0x01,
1262 HPACK_HUFFMAN_FLAG_SYM = 0x02,
1263 HPACK_HUFFMAN_FLAG_FAIL = 0x04,
1264 };
1265
1266 struct decode_status
1267 {
1268 uint8_t state;
1269 uint8_t eos;
1270 };
1271
1272
1273 void
lshpack_dec_init(struct lshpack_dec * dec)1274 lshpack_dec_init (struct lshpack_dec *dec)
1275 {
1276 memset(dec, 0, sizeof(*dec));
1277 dec->hpd_max_capacity = INITIAL_DYNAMIC_TABLE_SIZE;
1278 dec->hpd_cur_max_capacity = INITIAL_DYNAMIC_TABLE_SIZE;
1279 lshpack_arr_init(&dec->hpd_dyn_table);
1280 }
1281
1282
1283 void
lshpack_dec_cleanup(struct lshpack_dec * dec)1284 lshpack_dec_cleanup (struct lshpack_dec *dec)
1285 {
1286 uintptr_t val;
1287
1288 while (lshpack_arr_count(&dec->hpd_dyn_table) > 0)
1289 {
1290 val = lshpack_arr_pop(&dec->hpd_dyn_table);
1291 free((struct dec_table_entry *) val);
1292 }
1293 lshpack_arr_cleanup(&dec->hpd_dyn_table);
1294 }
1295
1296
1297 /* Maximum number of bytes required to encode a 32-bit integer */
1298 #define LSHPACK_UINT32_ENC_SZ 6
1299
1300
1301 /* Assumption: we have at least one byte to work with */
1302 #if !LS_HPACK_EMIT_TEST_CODE
1303 static
1304 #endif
1305 int
lshpack_dec_dec_int(const unsigned char ** src_p,const unsigned char * src_end,unsigned prefix_bits,uint32_t * value_p)1306 lshpack_dec_dec_int (const unsigned char **src_p, const unsigned char *src_end,
1307 unsigned prefix_bits, uint32_t *value_p)
1308 {
1309 const unsigned char *const orig_src = *src_p;
1310 const unsigned char *src;
1311 unsigned prefix_max, M;
1312 uint32_t val, B;
1313
1314 src = *src_p;
1315
1316 prefix_max = (1 << prefix_bits) - 1;
1317 val = *src++;
1318 val &= prefix_max;
1319
1320 if (val < prefix_max)
1321 {
1322 *src_p = src;
1323 *value_p = val;
1324 return 0;
1325 }
1326
1327 M = 0;
1328 do
1329 {
1330 if (src < src_end)
1331 {
1332 B = *src++;
1333 val = val + ((B & 0x7f) << M);
1334 M += 7;
1335 }
1336 else if (src - orig_src < LSHPACK_UINT32_ENC_SZ)
1337 return -1;
1338 else
1339 return -2;
1340 }
1341 while (B & 0x80);
1342
1343 if (M <= 28 || (M == 35 && src[-1] <= 0xF && val - (src[-1] << 28) < val))
1344 {
1345 *src_p = src;
1346 *value_p = val;
1347 return 0;
1348 }
1349 else
1350 return -2;
1351 }
1352
1353
1354 static void
hdec_drop_oldest_entry(struct lshpack_dec * dec)1355 hdec_drop_oldest_entry (struct lshpack_dec *dec)
1356 {
1357 struct dec_table_entry *entry;
1358 entry = (void *) lshpack_arr_shift(&dec->hpd_dyn_table);
1359 dec->hpd_cur_capacity -= DYNAMIC_ENTRY_OVERHEAD + entry->dte_name_len
1360 + entry->dte_val_len;
1361 ++dec->hpd_state;
1362 free(entry);
1363 }
1364
1365
1366 static void
hdec_remove_overflow_entries(struct lshpack_dec * dec)1367 hdec_remove_overflow_entries (struct lshpack_dec *dec)
1368 {
1369 while (dec->hpd_cur_capacity > dec->hpd_cur_max_capacity)
1370 hdec_drop_oldest_entry(dec);
1371 }
1372
1373
1374 static void
hdec_update_max_capacity(struct lshpack_dec * dec,uint32_t new_capacity)1375 hdec_update_max_capacity (struct lshpack_dec *dec, uint32_t new_capacity)
1376 {
1377 dec->hpd_cur_max_capacity = new_capacity;
1378 hdec_remove_overflow_entries(dec);
1379 }
1380
1381
1382 void
lshpack_dec_set_max_capacity(struct lshpack_dec * dec,unsigned max_capacity)1383 lshpack_dec_set_max_capacity (struct lshpack_dec *dec, unsigned max_capacity)
1384 {
1385 dec->hpd_max_capacity = max_capacity;
1386 hdec_update_max_capacity(dec, max_capacity);
1387 }
1388
1389
1390 static unsigned char *
hdec_huff_dec4bits(uint8_t src_4bits,unsigned char * dst,struct decode_status * status)1391 hdec_huff_dec4bits (uint8_t src_4bits, unsigned char *dst,
1392 struct decode_status *status)
1393 {
1394 const struct decode_el cur_dec_code =
1395 decode_tables[status->state][src_4bits];
1396 if (cur_dec_code.flags & HPACK_HUFFMAN_FLAG_FAIL) {
1397 return NULL; //failed
1398 }
1399 if (cur_dec_code.flags & HPACK_HUFFMAN_FLAG_SYM)
1400 {
1401 *dst = cur_dec_code.sym;
1402 dst++;
1403 }
1404
1405 status->state = cur_dec_code.state;
1406 status->eos = ((cur_dec_code.flags & HPACK_HUFFMAN_FLAG_ACCEPTED) != 0);
1407 return dst;
1408 }
1409
1410
1411 #if !LS_HPACK_USE_LARGE_TABLES
1412 #define lshpack_dec_huff_decode_full lshpack_dec_huff_decode
1413 #endif
1414
1415 static int
lshpack_dec_huff_decode_full(const unsigned char * src,int src_len,unsigned char * dst,int dst_len)1416 lshpack_dec_huff_decode_full (const unsigned char *src, int src_len,
1417 unsigned char *dst, int dst_len)
1418 {
1419 const unsigned char *p_src = src;
1420 const unsigned char *const src_end = src + src_len;
1421 unsigned char *p_dst = dst;
1422 unsigned char *dst_end = dst + dst_len;
1423 struct decode_status status = { 0, 1 };
1424
1425 while (p_src != src_end)
1426 {
1427 if (p_dst == dst_end)
1428 return LSHPACK_ERR_MORE_BUF;
1429 if ((p_dst = hdec_huff_dec4bits(*p_src >> 4, p_dst, &status))
1430 == NULL)
1431 return -1;
1432 if (p_dst == dst_end)
1433 return LSHPACK_ERR_MORE_BUF;
1434 if ((p_dst = hdec_huff_dec4bits(*p_src & 0xf, p_dst, &status))
1435 == NULL)
1436 return -1;
1437 ++p_src;
1438 }
1439
1440 if (!status.eos)
1441 return -1;
1442
1443 return p_dst - dst;
1444 }
1445
1446
1447 static int
1448 lshpack_dec_huff_decode (const unsigned char *src, int src_len,
1449 unsigned char *dst, int dst_len);
1450
1451
1452 //reutrn the length in the dst, also update the src
1453 #if !LS_HPACK_EMIT_TEST_CODE
1454 static
1455 #endif
1456 int
hdec_dec_str(unsigned char * dst,size_t dst_len,const unsigned char ** src,const unsigned char * src_end)1457 hdec_dec_str (unsigned char *dst, size_t dst_len, const unsigned char **src,
1458 const unsigned char *src_end)
1459 {
1460 if ((*src) == src_end)
1461 return 0;
1462
1463 int is_huffman = (*(*src) & 0x80);
1464 uint32_t len;
1465 if (0 != lshpack_dec_dec_int(src, src_end, 7, &len))
1466 return LSHPACK_ERR_BAD_DATA; //wrong int
1467
1468 int ret = 0;
1469 if ((uint32_t)(src_end - (*src)) < len) {
1470 return LSHPACK_ERR_BAD_DATA; //wrong int
1471 }
1472
1473 if (is_huffman)
1474 {
1475 ret = lshpack_dec_huff_decode(*src, len, dst, dst_len);
1476 if (ret < 0)
1477 return ret; //Wrong code
1478
1479 (*src) += len;
1480 }
1481 else
1482 {
1483 if (dst_len < len)
1484 {
1485 ret = dst_len - len;
1486 if (ret > LSHPACK_ERR_MORE_BUF)
1487 ret = LSHPACK_ERR_MORE_BUF; //dst not enough space
1488 }
1489 else
1490 {
1491 memcpy(dst, (*src), len);
1492 (*src) += len;
1493 ret = len;
1494 }
1495 }
1496
1497 return ret;
1498 }
1499
1500
1501 /* hpd_dyn_table is a dynamic array. New entries are pushed onto it,
1502 * while old entries are shifted from it.
1503 */
1504 static struct dec_table_entry *
hdec_get_table_entry(struct lshpack_dec * dec,uint32_t index)1505 hdec_get_table_entry (struct lshpack_dec *dec, uint32_t index)
1506 {
1507 uintptr_t val;
1508
1509 index -= HPACK_STATIC_TABLE_SIZE;
1510 if (index == 0 || index > lshpack_arr_count(&dec->hpd_dyn_table))
1511 return NULL;
1512
1513 index = lshpack_arr_count(&dec->hpd_dyn_table) - index;
1514 val = lshpack_arr_get(&dec->hpd_dyn_table, index);
1515 return (struct dec_table_entry *) val;
1516 }
1517
1518
1519 #if !LS_HPACK_EMIT_TEST_CODE
1520 static
1521 #endif
1522 int
lshpack_dec_push_entry(struct lshpack_dec * dec,const struct lsxpack_header * xhdr)1523 lshpack_dec_push_entry (struct lshpack_dec *dec,
1524 const struct lsxpack_header *xhdr)
1525 {
1526 struct dec_table_entry *entry;
1527 unsigned name_len, val_len;
1528 size_t size;
1529
1530 name_len = xhdr->name_len;
1531 val_len = xhdr->val_len;
1532
1533 size = sizeof(*entry) + name_len + val_len;
1534 entry = malloc(size);
1535 if (!entry)
1536 return -1;
1537
1538 if (0 != lshpack_arr_push(&dec->hpd_dyn_table, (uintptr_t) entry))
1539 {
1540 free(entry);
1541 return -1;
1542 }
1543 ++dec->hpd_state;
1544 dec->hpd_cur_capacity += DYNAMIC_ENTRY_OVERHEAD + name_len + val_len;
1545 entry->dte_name_len = name_len;
1546 entry->dte_val_len = val_len;
1547 entry->dte_name_idx = xhdr->hpack_index;
1548 #if LSHPACK_DEC_CALC_HASH
1549 entry->dte_flags = xhdr->flags & (LSXPACK_NAME_HASH|LSXPACK_NAMEVAL_HASH);
1550 entry->dte_name_hash = xhdr->name_hash;
1551 entry->dte_nameval_hash = xhdr->nameval_hash;
1552 #endif
1553 memcpy(DTE_NAME(entry), lsxpack_header_get_name(xhdr), name_len);
1554 memcpy(DTE_VALUE(entry), lsxpack_header_get_value(xhdr), val_len);
1555
1556 hdec_remove_overflow_entries(dec);
1557 return 0;
1558 }
1559
1560
1561 static int
lshpack_dec_copy_value(lsxpack_header_t * output,char * dest,const char * val,unsigned val_len)1562 lshpack_dec_copy_value (lsxpack_header_t *output, char *dest, const char *val,
1563 unsigned val_len)
1564 {
1565 if (val_len + LSHPACK_DEC_HTTP1X_EXTRA > (unsigned)output->val_len)
1566 return LSHPACK_ERR_MORE_BUF;
1567 output->val_offset = output->name_offset + output->name_len
1568 + LSHPACK_DEC_HTTP1X_EXTRA;
1569
1570 assert(dest == output->buf + output->val_offset);
1571 output->val_len = val_len;
1572 memcpy(dest, val, output->val_len);
1573 dest += output->val_len;
1574 #if LSHPACK_DEC_HTTP1X_OUTPUT
1575 *dest++ = '\r';
1576 *dest++ = '\n';
1577 #endif
1578 return 0;
1579 }
1580
1581
1582 static int
lshpack_dec_copy_name(lsxpack_header_t * output,char ** dest,const char * name,unsigned name_len)1583 lshpack_dec_copy_name (lsxpack_header_t *output, char **dest, const char *name,
1584 unsigned name_len)
1585 {
1586 if (name_len + LSHPACK_DEC_HTTP1X_EXTRA > (unsigned)output->val_len)
1587 return LSHPACK_ERR_MORE_BUF;
1588 output->val_len -= name_len + LSHPACK_DEC_HTTP1X_EXTRA;
1589 output->name_len = name_len;
1590 memcpy(*dest, name, name_len);
1591 *dest += name_len;
1592 #if LSHPACK_DEC_HTTP1X_OUTPUT
1593 *(*dest)++ = ':';
1594 *(*dest)++ = ' ';
1595 #endif
1596 return 0;
1597 }
1598
1599
1600 enum
1601 {
1602 LSHPACK_ADD_INDEX = 0,
1603 LSHPACK_NO_INDEX = 1,
1604 LSHPACK_NEVER_INDEX = 2,
1605 LSHPACK_VAL_INDEX = 3,
1606 };
1607
1608
1609 int
lshpack_dec_decode(struct lshpack_dec * dec,const unsigned char ** src,const unsigned char * src_end,struct lsxpack_header * output)1610 lshpack_dec_decode (struct lshpack_dec *dec,
1611 const unsigned char **src, const unsigned char *src_end,
1612 struct lsxpack_header *output)
1613 {
1614 struct dec_table_entry *entry;
1615 uint32_t index, new_capacity;
1616 int indexed_type, len;
1617 const unsigned char *s;
1618 size_t buf_len = output->val_len;
1619 size_t extra_buf = 0;
1620
1621 if ((*src) == src_end)
1622 return LSHPACK_ERR_BAD_DATA;
1623
1624 buf_len = output->val_len;
1625 extra_buf = 0;
1626 s = *src;
1627 while ((*s & 0xe0) == 0x20) //001 xxxxx
1628 {
1629 if (0 != lshpack_dec_dec_int(&s, src_end, 5, &new_capacity))
1630 return LSHPACK_ERR_BAD_DATA;
1631 if (new_capacity > dec->hpd_max_capacity)
1632 return LSHPACK_ERR_BAD_DATA;
1633 hdec_update_max_capacity(dec, new_capacity);
1634 if (s == src_end)
1635 return LSHPACK_ERR_BAD_DATA;
1636 }
1637
1638 /* lshpack_dec_dec_int() sets `index' and advances `src'. If we do not
1639 * call it, we set `index' and advance `src' ourselves:
1640 */
1641 if (*s & 0x80) //1 xxxxxxx
1642 {
1643 if (0 != lshpack_dec_dec_int(&s, src_end, 7, &index))
1644 return LSHPACK_ERR_BAD_DATA;
1645 if (index == 0)
1646 return LSHPACK_ERR_BAD_DATA;
1647 indexed_type = LSHPACK_VAL_INDEX; //need to parse value
1648 }
1649 else if (*s > 0x40) //01 xxxxxx
1650 {
1651 if (0 != lshpack_dec_dec_int(&s, src_end, 6, &index))
1652 return LSHPACK_ERR_BAD_DATA;
1653
1654 indexed_type = LSHPACK_ADD_INDEX;
1655 }
1656 else if (*s == 0x40) //custmized //0100 0000
1657 {
1658 indexed_type = LSHPACK_ADD_INDEX;
1659 index = LSHPACK_HDR_UNKNOWN;
1660 ++s;
1661 }
1662
1663 //Never indexed
1664 else if (*s == 0x10) //00010000
1665 {
1666 indexed_type = LSHPACK_NEVER_INDEX;
1667 output->flags |= LSXPACK_NEVER_INDEX;
1668 index = LSHPACK_HDR_UNKNOWN;
1669 ++s;
1670 }
1671 else if ((*s & 0xf0) == 0x10) //0001 xxxx
1672 {
1673 if (0 != lshpack_dec_dec_int(&s, src_end, 4, &index))
1674 return LSHPACK_ERR_BAD_DATA;
1675
1676 indexed_type = LSHPACK_NEVER_INDEX;
1677 output->flags |= LSXPACK_NEVER_INDEX;
1678 }
1679
1680 //without indexed
1681 else if (*s == 0x00) //0000 0000
1682 {
1683 indexed_type = LSHPACK_NO_INDEX;
1684 index = LSHPACK_HDR_UNKNOWN;
1685 ++s;
1686 }
1687 else // 0000 xxxx
1688 {
1689 if (0 != lshpack_dec_dec_int(&s, src_end, 4, &index))
1690 return LSHPACK_ERR_BAD_DATA;
1691
1692 indexed_type = LSHPACK_NO_INDEX;
1693 }
1694 if (index != LSHPACK_HDR_UNKNOWN && index <= LSHPACK_HDR_WWW_AUTHENTICATE)
1695 {
1696 output->hpack_index = index;
1697 }
1698
1699 char *name = output->buf + output->name_offset;
1700 if (index > 0)
1701 {
1702 if (index <= HPACK_STATIC_TABLE_SIZE) //static table
1703 {
1704 if (lshpack_dec_copy_name(output, &name,
1705 static_table[index - 1].name,
1706 static_table[index - 1].name_len) == LSHPACK_ERR_MORE_BUF)
1707 {
1708 extra_buf = static_table[index - 1].name_len
1709 + LSHPACK_DEC_HTTP1X_EXTRA;
1710 goto need_more_buf;
1711 }
1712 output->flags |= LSXPACK_NAME_HASH;
1713 output->name_hash = static_table_name_hash[index - 1];
1714
1715 if (indexed_type == LSHPACK_VAL_INDEX)
1716 {
1717 if (lshpack_dec_copy_value(output, name,
1718 static_table[index - 1].val,
1719 static_table[index - 1].val_len) == 0)
1720 {
1721 output->flags |= LSXPACK_NAMEVAL_HASH;
1722 output->nameval_hash = static_table_nameval_hash[index - 1];
1723 goto decode_end;
1724 }
1725 else
1726 {
1727 extra_buf = static_table[index - 1].val_len
1728 + LSHPACK_DEC_HTTP1X_EXTRA;
1729 goto need_more_buf;
1730 }
1731 }
1732 }
1733 else
1734 {
1735 entry = hdec_get_table_entry(dec, index);
1736 if (entry == NULL)
1737 return LSHPACK_ERR_BAD_DATA;
1738 if (lshpack_dec_copy_name(output, &name, DTE_NAME(entry),
1739 entry->dte_name_len) == LSHPACK_ERR_MORE_BUF)
1740 {
1741 extra_buf = entry->dte_name_len + LSHPACK_DEC_HTTP1X_EXTRA;
1742 goto need_more_buf;
1743 }
1744
1745 if (entry->dte_name_idx)
1746 output->hpack_index = entry->dte_name_idx;
1747 else
1748 output->hpack_index = LSHPACK_HDR_UNKNOWN;
1749 #if LSHPACK_DEC_CALC_HASH
1750 output->flags |= entry->dte_flags & DTEF_NAME_HASH;
1751 output->name_hash = entry->dte_name_hash;
1752 #endif
1753 if (indexed_type == LSHPACK_VAL_INDEX)
1754 {
1755 if (lshpack_dec_copy_value(output, name, DTE_VALUE(entry),
1756 entry->dte_val_len) == 0)
1757 {
1758 #if LSHPACK_DEC_CALC_HASH
1759 output->flags |= entry->dte_flags & DTEF_NAMEVAL_HASH;
1760 output->nameval_hash = entry->dte_nameval_hash;
1761 #endif
1762 goto decode_end;
1763 }
1764 else
1765 {
1766 extra_buf = entry->dte_val_len + LSHPACK_DEC_HTTP1X_EXTRA;
1767 goto need_more_buf;
1768 }
1769 }
1770 }
1771 }
1772 else
1773 {
1774 len = hdec_dec_str((unsigned char *)name, output->val_len,
1775 &s, src_end);
1776 if (len < 0)
1777 {
1778 if (len <= LSHPACK_ERR_MORE_BUF)
1779 {
1780 extra_buf = -len;
1781 goto need_more_buf;
1782 }
1783 return len; //error
1784 }
1785 if (len > UINT16_MAX)
1786 return LSHPACK_ERR_TOO_LARGE;
1787 #if LSHPACK_DEC_CALC_HASH
1788 output->flags |= LSXPACK_NAME_HASH;
1789 output->name_hash = XXH32(name, (size_t) len, LSHPACK_XXH_SEED);
1790 #endif
1791 output->name_len = len;
1792 name += output->name_len;
1793 #if LSHPACK_DEC_HTTP1X_OUTPUT
1794 if (output->name_len + 2 <= output->val_len)
1795 {
1796 *name++ = ':';
1797 *name++ = ' ';
1798 }
1799 else
1800 {
1801 extra_buf = 2;
1802 goto need_more_buf;
1803 }
1804 #endif
1805 output->val_len -= len + LSHPACK_DEC_HTTP1X_EXTRA;
1806 }
1807
1808 len = hdec_dec_str((unsigned char *)name, output->val_len, &s, src_end);
1809 if (len < 0)
1810 {
1811 if (len <= LSHPACK_ERR_MORE_BUF)
1812 {
1813 extra_buf = -len;
1814 goto need_more_buf;
1815 }
1816 return len; //error
1817 }
1818 if (len > UINT16_MAX)
1819 return LSHPACK_ERR_TOO_LARGE;
1820 #if LSHPACK_DEC_CALC_HASH
1821 assert(output->flags & LSXPACK_NAME_HASH);
1822 output->flags |= LSXPACK_NAMEVAL_HASH;
1823 output->nameval_hash = XXH32(name, (size_t) len, output->name_hash);
1824 #endif
1825 #if LSHPACK_DEC_HTTP1X_OUTPUT
1826 if ((unsigned) len + 2 <= output->val_len)
1827 memcpy(name + len, "\r\n", 2);
1828 else
1829 {
1830 extra_buf = 2;
1831 goto need_more_buf;
1832 }
1833 #endif
1834 output->val_offset = output->name_offset + output->name_len
1835 + LSHPACK_DEC_HTTP1X_EXTRA;
1836 output->val_len = len;
1837
1838 if (indexed_type == LSHPACK_ADD_INDEX &&
1839 0 != lshpack_dec_push_entry(dec, output))
1840 return LSHPACK_ERR_BAD_DATA; //error
1841 decode_end:
1842 *src = s;
1843 #if LSHPACK_DEC_HTTP1X_OUTPUT
1844 output->dec_overhead = 4;
1845 #endif
1846 return 0;
1847 need_more_buf:
1848 buf_len += extra_buf;
1849 output->val_len = buf_len;
1850 return LSHPACK_ERR_MORE_BUF;
1851 }
1852
1853
1854 #if LS_HPACK_USE_LARGE_TABLES
1855 #define SHORTEST_CODE 5
1856
1857
1858 /* The decoder is optimized for the common case. Most of the time, we decode
1859 * data whose encoding is 16 bits or shorter. This lets us use a 64 KB table
1860 * indexed by two bytes of input and outputs 1, 2, or 3 bytes at a time.
1861 *
1862 * In the case a longer code is encoutered, we fall back to the original
1863 * Huffman decoder that supports all code lengths.
1864 */
1865 static int
lshpack_dec_huff_decode(const unsigned char * src,int src_len,unsigned char * dst,int dst_len)1866 lshpack_dec_huff_decode (const unsigned char *src, int src_len,
1867 unsigned char *dst, int dst_len)
1868 {
1869 unsigned char *const orig_dst = dst;
1870 const unsigned char *const src_end = src + src_len;
1871 unsigned char *const dst_end = dst + dst_len;
1872 uintptr_t buf; /* OK not to initialize the buffer */
1873 unsigned avail_bits, len;
1874 struct hdec hdec;
1875 uint16_t idx;
1876 int r;
1877
1878 #if __GNUC__ && __GNUC__ >= 5 && !defined(__COVERITY__)
1879 #pragma GCC diagnostic push
1880 #pragma GCC diagnostic ignored "-Wmaybe-uninitialized"
1881 #pragma GCC diagnostic ignored "-Wuninitialized"
1882 #else
1883 buf = 0;
1884 #endif
1885
1886 avail_bits = 0;
1887 while (1)
1888 {
1889 if (src + sizeof(buf) <= src_end)
1890 {
1891 len = (sizeof(buf) * 8 - avail_bits) >> 3;
1892 avail_bits += len << 3;
1893 switch (len)
1894 {
1895 #if UINTPTR_MAX == 18446744073709551615ull
1896 case 8:
1897 buf <<= 8;
1898 buf |= (uintptr_t) *src++;
1899 /* fall through */
1900 case 7:
1901 buf <<= 8;
1902 buf |= (uintptr_t) *src++;
1903 /* fall through */
1904 default:
1905 buf <<= 48;
1906 buf |= (uintptr_t) *src++ << 40;
1907 buf |= (uintptr_t) *src++ << 32;
1908 buf |= (uintptr_t) *src++ << 24;
1909 buf |= (uintptr_t) *src++ << 16;
1910 #else
1911 /* fall through */
1912 case 4:
1913 buf <<= 8;
1914 buf |= (uintptr_t) *src++;
1915 /* fall through */
1916 case 3:
1917 buf <<= 8;
1918 buf |= (uintptr_t) *src++;
1919 /* fall through */
1920 default:
1921 buf <<= 16;
1922 #endif
1923 buf |= (uintptr_t) *src++ << 8;
1924 buf |= (uintptr_t) *src++ << 0;
1925 }
1926 }
1927 else if (src < src_end)
1928 do
1929 {
1930 buf <<= 8;
1931 buf |= (uintptr_t) *src++;
1932 avail_bits += 8;
1933 }
1934 while (src < src_end && avail_bits <= sizeof(buf) * 8 - 8);
1935 else
1936 break; /* Normal case terminating condition: out of input */
1937
1938 if (dst_end - dst >= (ptrdiff_t) (8 * sizeof(buf) / SHORTEST_CODE)
1939 && avail_bits >= 16)
1940 {
1941 /* Fast path: don't check destination bounds */
1942 do
1943 {
1944 idx = buf >> (avail_bits - 16);
1945 hdec = hdecs[idx];
1946 dst[0] = hdec.out[0];
1947 dst[1] = hdec.out[1];
1948 dst[2] = hdec.out[2];
1949 dst += hdec.lens & 3;
1950 avail_bits -= hdec.lens >> 2;
1951 }
1952 while (avail_bits >= 16 && hdec.lens);
1953 if (avail_bits < 16)
1954 continue;
1955 goto slow_path;
1956 }
1957 else
1958 while (avail_bits >= 16)
1959 {
1960 idx = buf >> (avail_bits - 16);
1961 hdec = hdecs[idx];
1962 len = hdec.lens & 3;
1963 if (len && dst + len <= dst_end)
1964 {
1965 switch (len)
1966 {
1967 case 3:
1968 *dst++ = hdec.out[0];
1969 *dst++ = hdec.out[1];
1970 *dst++ = hdec.out[2];
1971 break;
1972 case 2:
1973 *dst++ = hdec.out[0];
1974 *dst++ = hdec.out[1];
1975 break;
1976 default:
1977 *dst++ = hdec.out[0];
1978 break;
1979 }
1980 avail_bits -= hdec.lens >> 2;
1981 }
1982 else if (dst + len > dst_end)
1983 {
1984 r = dst_end - dst - len;
1985 if (r > LSHPACK_ERR_MORE_BUF)
1986 r = LSHPACK_ERR_MORE_BUF;
1987 return r;
1988 }
1989 else
1990 goto slow_path;
1991 }
1992 }
1993
1994 if (avail_bits >= SHORTEST_CODE)
1995 {
1996 idx = buf << (16 - avail_bits);
1997 idx |= (1 << (16 - avail_bits)) - 1; /* EOF */
1998 if (idx == 0xFFFF && avail_bits < 8)
1999 goto end;
2000 /* If a byte or more of input is left, this mean there is a valid
2001 * encoding, not just EOF.
2002 */
2003 hdec = hdecs[idx];
2004 len = hdec.lens & 3;
2005 if (((unsigned) hdec.lens >> 2) > avail_bits)
2006 return -1;
2007 if (len && dst + len <= dst_end)
2008 {
2009 switch (len)
2010 {
2011 case 3:
2012 *dst++ = hdec.out[0];
2013 *dst++ = hdec.out[1];
2014 *dst++ = hdec.out[2];
2015 break;
2016 case 2:
2017 *dst++ = hdec.out[0];
2018 *dst++ = hdec.out[1];
2019 break;
2020 default:
2021 *dst++ = hdec.out[0];
2022 break;
2023 }
2024 avail_bits -= hdec.lens >> 2;
2025 }
2026 else if (dst + len > dst_end)
2027 {
2028 r = dst_end - dst - len;
2029 if (r > LSHPACK_ERR_MORE_BUF)
2030 r = LSHPACK_ERR_MORE_BUF;
2031 return r;
2032 }
2033 else
2034 /* This must be an invalid code, otherwise it would have fit */
2035 return -1;
2036 }
2037
2038 if (avail_bits > 0)
2039 {
2040 if (((1u << avail_bits) - 1) != (buf & ((1u << avail_bits) - 1)))
2041 return -1; /* Not EOF as expected */
2042 }
2043 #if __GNUC__ && __GNUC__ >= 5 && !defined(__COVERITY__)
2044 #pragma GCC diagnostic pop
2045 #endif
2046
2047 end:
2048 return dst - orig_dst;
2049
2050 slow_path:
2051 /* Find previous byte boundary and finish decoding thence. */
2052 while ((avail_bits & 7) && dst > orig_dst)
2053 avail_bits += encode_table[ *--dst ].bits;
2054 assert((avail_bits & 7) == 0);
2055 src -= avail_bits >> 3;
2056 r = lshpack_dec_huff_decode_full(src, src_end - src, dst, dst_end - dst);
2057 if (r >= 0)
2058 return dst - orig_dst + r;
2059 else
2060 return r;
2061 }
2062 #endif
2063 #if __GNUC__ && (__GNUC__ >= 5 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 6))
2064 #pragma GCC diagnostic pop /* -Wunknown-pragmas */
2065 #endif
2066