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