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