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__ && !defined(__COVERITY__) 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 #ifdef __COVERITY__ 766 assert(bits_used > 0); 767 if (0 == bits_used || bits_used >= sizeof(bits)*8) abort(); 768 #endif 769 bits <<= sizeof(bits) * 8 - bits_used; 770 bits_used = cur_enc_code.bits - (sizeof(bits) * 8 - bits_used); 771 bits |= cur_enc_code.code >> bits_used; 772 #if UINTPTR_MAX == 18446744073709551615ull 773 *p_dst++ = bits >> 56; 774 *p_dst++ = bits >> 48; 775 *p_dst++ = bits >> 40; 776 *p_dst++ = bits >> 32; 777 #endif 778 *p_dst++ = bits >> 24; 779 *p_dst++ = bits >> 16; 780 *p_dst++ = bits >> 8; 781 *p_dst++ = bits; 782 bits = cur_enc_code.code; /* OK not to clear high bits */ 783 } 784 else 785 return -1; 786 } 787 788 adj = bits_used + (-bits_used & 7); /* Round up to 8 */ 789 if (bits_used && p_dst + (adj >> 3) <= dst_end) 790 { 791 bits <<= -bits_used & 7; /* Align to byte boundary */ 792 bits |= ((1 << (-bits_used & 7)) - 1); /* EOF */ 793 switch (adj >> 3) 794 { /* Write out */ 795 #if UINTPTR_MAX == 18446744073709551615ull 796 case 8: *p_dst++ = bits >> 56; 797 /* fall through */ 798 case 7: *p_dst++ = bits >> 48; 799 /* fall through */ 800 case 6: *p_dst++ = bits >> 40; 801 /* fall through */ 802 case 5: *p_dst++ = bits >> 32; 803 #endif 804 /* fall through */ 805 case 4: *p_dst++ = bits >> 24; 806 /* fall through */ 807 case 3: *p_dst++ = bits >> 16; 808 /* fall through */ 809 case 2: *p_dst++ = bits >> 8; 810 /* fall through */ 811 default: *p_dst++ = bits; 812 } 813 return p_dst - dst; 814 } 815 else if (p_dst + (adj >> 3) <= dst_end) 816 return p_dst - dst; 817 else 818 return -1; 819 #if __GNUC__ 820 #pragma GCC diagnostic pop 821 #endif 822 } 823 824 825 #if !LS_HPACK_EMIT_TEST_CODE 826 static 827 #endif 828 int 829 lshpack_enc_enc_str (unsigned char *const dst, size_t dst_len, 830 const unsigned char *str, unsigned str_len) 831 { 832 unsigned char size_buf[4]; 833 unsigned char *p; 834 unsigned size_len; 835 int rc; 836 837 if (dst_len > 1) 838 /* We guess that the string size fits into a single byte -- meaning 839 * compressed string of size 126 and smaller -- which is the normal 840 * case. Thus, we immediately write compressed string to the output 841 * buffer. If our guess is not correct, we fix it later. 842 */ 843 rc = lshpack_enc_huff_encode(str, str + str_len, dst + 1, dst_len - 1); 844 else if (dst_len == 1) 845 /* Here, the call can only succeed if the string to encode is empty. */ 846 rc = 0; 847 else 848 return -1; 849 850 /* 851 * Check if need huffman encoding or not 852 * Comment: (size_t)rc <= str_len = means if same length, still use 853 * Huffman 854 * ^ 855 */ 856 if (rc > 0 && (size_t)rc <= str_len) 857 { 858 if (rc < 127) 859 { 860 *dst = 0x80 | rc; 861 return 1 + rc; 862 } 863 size_buf[0] = 0x80; 864 str_len = rc; 865 str = dst + 1; 866 } 867 else if (str_len <= dst_len - 1) 868 { 869 if (str_len < 127) 870 { 871 *dst = (unsigned char) str_len; 872 memcpy(dst + 1, str, str_len); 873 return 1 + str_len; 874 } 875 size_buf[0] = 0x00; 876 } 877 else 878 return -1; 879 880 /* The guess of one-byte size was incorrect. Perform necessary 881 * adjustments. 882 */ 883 p = lshpack_enc_enc_int(size_buf, size_buf + sizeof(size_buf), str_len, 7); 884 if (p == size_buf) 885 return -1; 886 887 size_len = p - size_buf; 888 assert(size_len > 1); 889 890 /* Check if there is enough room in the output buffer for both 891 * encoded size and the string. 892 */ 893 if (size_len + str_len > dst_len) 894 return -1; 895 896 memmove(dst + size_len, str, str_len); 897 memcpy(dst, size_buf, size_len); 898 return size_len + str_len; 899 } 900 901 902 static void 903 henc_drop_oldest_entry (struct lshpack_enc *enc) 904 { 905 struct lshpack_enc_table_entry *entry; 906 unsigned buckno; 907 908 entry = STAILQ_FIRST(&enc->hpe_all_entries); 909 assert(entry); 910 STAILQ_REMOVE_HEAD(&enc->hpe_all_entries, ete_next_all); 911 buckno = BUCKNO(enc->hpe_nbits, entry->ete_nameval_hash); 912 assert(entry == STAILQ_FIRST(&enc->hpe_buckets[buckno].by_nameval)); 913 STAILQ_REMOVE_HEAD(&enc->hpe_buckets[buckno].by_nameval, ete_next_nameval); 914 buckno = BUCKNO(enc->hpe_nbits, entry->ete_name_hash); 915 if (entry == STAILQ_FIRST(&enc->hpe_buckets[buckno].by_name)) 916 STAILQ_REMOVE_HEAD(&enc->hpe_buckets[buckno].by_name, ete_next_name); 917 918 enc->hpe_cur_capacity -= DYNAMIC_ENTRY_OVERHEAD + entry->ete_name_len 919 + entry->ete_val_len; 920 --enc->hpe_nelem; 921 free(entry); 922 } 923 924 925 static void 926 henc_remove_overflow_entries (struct lshpack_enc *enc) 927 { 928 while (enc->hpe_cur_capacity > enc->hpe_max_capacity) 929 henc_drop_oldest_entry(enc); 930 } 931 932 933 static int 934 henc_grow_tables (struct lshpack_enc *enc) 935 { 936 struct lshpack_double_enc_head *new_buckets, *new[2]; 937 struct lshpack_enc_table_entry *entry; 938 unsigned n, old_nbits; 939 int idx; 940 941 old_nbits = enc->hpe_nbits; 942 new_buckets = malloc(sizeof(enc->hpe_buckets[0]) 943 * N_BUCKETS(old_nbits + 1)); 944 if (!new_buckets) 945 return -1; 946 947 for (n = 0; n < N_BUCKETS(old_nbits); ++n) 948 { 949 new[0] = &new_buckets[n]; 950 new[1] = &new_buckets[n + N_BUCKETS(old_nbits)]; 951 STAILQ_INIT(&new[0]->by_name); 952 STAILQ_INIT(&new[1]->by_name); 953 STAILQ_INIT(&new[0]->by_nameval); 954 STAILQ_INIT(&new[1]->by_nameval); 955 while ((entry = STAILQ_FIRST(&enc->hpe_buckets[n].by_name))) 956 { 957 STAILQ_REMOVE_HEAD(&enc->hpe_buckets[n].by_name, ete_next_name); 958 idx = (BUCKNO(old_nbits + 1, entry->ete_name_hash) 959 >> old_nbits) & 1; 960 STAILQ_INSERT_TAIL(&new[idx]->by_name, entry, ete_next_name); 961 } 962 while ((entry = STAILQ_FIRST(&enc->hpe_buckets[n].by_nameval))) 963 { 964 STAILQ_REMOVE_HEAD(&enc->hpe_buckets[n].by_nameval, 965 ete_next_nameval); 966 idx = (BUCKNO(old_nbits + 1, entry->ete_nameval_hash) 967 >> old_nbits) & 1; 968 STAILQ_INSERT_TAIL(&new[idx]->by_nameval, entry, 969 ete_next_nameval); 970 } 971 } 972 973 free(enc->hpe_buckets); 974 enc->hpe_nbits = old_nbits + 1; 975 enc->hpe_buckets = new_buckets; 976 return 0; 977 } 978 979 980 #if !LS_HPACK_EMIT_TEST_CODE 981 static 982 #endif 983 int 984 lshpack_enc_push_entry (struct lshpack_enc *enc, 985 const struct lsxpack_header *input) 986 { 987 unsigned buckno; 988 struct lshpack_enc_table_entry *entry; 989 size_t size; 990 const char *name; 991 unsigned int name_len; 992 993 if (enc->hpe_nelem >= N_BUCKETS(enc->hpe_nbits) / 2 && 994 0 != henc_grow_tables(enc)) 995 return -1; 996 name_len = input->name_len; 997 if (name_len == 0) 998 { 999 assert(input->hpack_index != LSHPACK_HDR_UNKNOWN); 1000 name = static_table[input->hpack_index - 1].name; 1001 name_len = static_table[input->hpack_index - 1].name_len; 1002 } 1003 else 1004 name = lsxpack_header_get_name(input); 1005 size = sizeof(*entry) + name_len + input->val_len; 1006 entry = malloc(size); 1007 if (!entry) 1008 return -1; 1009 1010 entry->ete_name_hash = input->name_hash; 1011 entry->ete_nameval_hash = input->nameval_hash; 1012 entry->ete_name_len = name_len; 1013 entry->ete_val_len = input->val_len; 1014 entry->ete_id = enc->hpe_next_id++; 1015 memcpy(ETE_NAME(entry), name, name_len); 1016 memcpy(ETE_VALUE(entry), input->buf + input->val_offset, input->val_len); 1017 1018 STAILQ_INSERT_TAIL(&enc->hpe_all_entries, entry, ete_next_all); 1019 buckno = BUCKNO(enc->hpe_nbits, input->nameval_hash); 1020 STAILQ_INSERT_TAIL(&enc->hpe_buckets[buckno].by_nameval, entry, 1021 ete_next_nameval); 1022 if (input->hpack_index == LSHPACK_HDR_UNKNOWN) 1023 { 1024 buckno = BUCKNO(enc->hpe_nbits, input->name_hash); 1025 STAILQ_INSERT_TAIL(&enc->hpe_buckets[buckno].by_name, entry, 1026 ete_next_name); 1027 } 1028 enc->hpe_cur_capacity += DYNAMIC_ENTRY_OVERHEAD + name_len 1029 + input->val_len; 1030 ++enc->hpe_nelem; 1031 henc_remove_overflow_entries(enc); 1032 return 0; 1033 } 1034 1035 1036 static void 1037 henc_resize_history (struct lshpack_enc *enc) 1038 { 1039 uint32_t *hist_buf; 1040 unsigned hist_size, first, count, i, j; 1041 1042 hist_size = henc_hist_size(enc->hpe_max_capacity); 1043 1044 if (hist_size == enc->hpe_hist_size) 1045 return; 1046 1047 if (hist_size == 0) 1048 { 1049 free(enc->hpe_hist_buf); 1050 enc->hpe_hist_buf = NULL; 1051 enc->hpe_hist_size = 0; 1052 enc->hpe_hist_idx = 0; 1053 enc->hpe_hist_wrapped = 0; 1054 return; 1055 } 1056 1057 hist_buf = malloc(sizeof(hist_buf[0]) * (hist_size + 1)); 1058 if (!hist_buf) 1059 return; 1060 1061 if (enc->hpe_hist_wrapped) 1062 { 1063 first = (enc->hpe_hist_idx + 1) % enc->hpe_hist_size; 1064 count = enc->hpe_hist_size; 1065 } 1066 else 1067 { 1068 first = 0; 1069 count = enc->hpe_hist_idx; 1070 } 1071 for (i = 0, j = 0; count > 0 && j < hist_size; ++i, ++j, --count) 1072 hist_buf[j] = enc->hpe_hist_buf[ (first + i) % enc->hpe_hist_size ]; 1073 enc->hpe_hist_size = hist_size; 1074 enc->hpe_hist_idx = j % hist_size; 1075 enc->hpe_hist_wrapped = enc->hpe_hist_idx == 0; 1076 free(enc->hpe_hist_buf); 1077 enc->hpe_hist_buf = hist_buf; 1078 } 1079 1080 1081 /* Returns true if `nameval_hash' was already in history, false otherwise. */ 1082 static int 1083 henc_hist_add (struct lshpack_enc *enc, uint32_t nameval_hash) 1084 { 1085 unsigned last; 1086 uint32_t *p; 1087 1088 if (enc->hpe_hist_wrapped) 1089 last = enc->hpe_hist_size; 1090 else 1091 last = enc->hpe_hist_idx; 1092 1093 enc->hpe_hist_buf[ last ] = nameval_hash; 1094 for (p = enc->hpe_hist_buf; *p != nameval_hash; ++p) 1095 ; 1096 enc->hpe_hist_buf[ enc->hpe_hist_idx ] = nameval_hash; 1097 enc->hpe_hist_idx = (enc->hpe_hist_idx + 1) % enc->hpe_hist_size; 1098 enc->hpe_hist_wrapped |= enc->hpe_hist_idx == 0; 1099 1100 return p < enc->hpe_hist_buf + last; 1101 } 1102 1103 1104 unsigned char * 1105 lshpack_enc_encode (struct lshpack_enc *enc, unsigned char *dst, 1106 unsigned char *dst_end, lsxpack_header_t *input) 1107 { 1108 //indexed_type: 0, Add, 1,: without, 2: never 1109 static const char indexed_prefix_number[] = {0x40, 0x00, 0x10}; 1110 unsigned char *const dst_org = dst; 1111 int rc; 1112 int val_matched = 0; 1113 unsigned table_id; 1114 1115 if (dst_end <= dst) 1116 return dst_org; 1117 1118 if (input->flags & LSXPACK_HPACK_VAL_MATCHED) 1119 { 1120 assert(input->hpack_index != LSHPACK_HDR_UNKNOWN); 1121 assert(input->val_len == static_table[input->hpack_index - 1].val_len); 1122 assert(memcmp(lsxpack_header_get_value(input), 1123 static_table[input->hpack_index - 1].val, 1124 input->val_len) == 0); 1125 table_id = input->hpack_index; 1126 val_matched = 1; 1127 } 1128 else 1129 { 1130 if (input->flags & LSXPACK_NEVER_INDEX) 1131 input->indexed_type = 2; 1132 table_id = henc_find_table_id(enc, input, &val_matched); 1133 if (enc->hpe_hist_buf) 1134 { 1135 rc = henc_hist_add(enc, input->nameval_hash); 1136 if (!rc && enc->hpe_hist_wrapped && input->indexed_type == 0) 1137 input->indexed_type = 1; 1138 } 1139 } 1140 1141 if (table_id > 0) 1142 { 1143 if (val_matched) 1144 { 1145 // LSXPACK_VAL_MATCHED MUST NOT set for dynamic table 1146 // otherwise, it may cause trouble when feed the input to a different encoder. 1147 if (table_id > HPACK_STATIC_TABLE_SIZE) 1148 assert(!(input->flags & LSXPACK_HPACK_VAL_MATCHED)); 1149 1150 *dst = 0x80; 1151 dst = lshpack_enc_enc_int(dst, dst_end, table_id, 7); 1152 /* No need to check return value: we pass it up as-is because 1153 * the behavior is the same. 1154 */ 1155 return dst; 1156 } 1157 else 1158 { 1159 *dst = indexed_prefix_number[input->indexed_type]; 1160 dst = lshpack_enc_enc_int(dst, dst_end, table_id, 1161 ((input->indexed_type == 0) ? 6 : 4)); 1162 if (dst == dst_org) 1163 return dst_org; 1164 } 1165 } 1166 else 1167 { 1168 assert(input->name_len > 0); 1169 *dst++ = indexed_prefix_number[input->indexed_type]; 1170 rc = lshpack_enc_enc_str(dst, dst_end - dst, 1171 (unsigned char *)lsxpack_header_get_name(input), 1172 input->name_len); 1173 if (rc < 0) 1174 return dst_org; //Failed to enc this header, return unchanged ptr. 1175 dst += rc; 1176 } 1177 1178 rc = lshpack_enc_enc_str(dst, dst_end - dst, 1179 (const unsigned char *)input->buf + input->val_offset, 1180 input->val_len); 1181 if (rc < 0) 1182 return dst_org; //Failed to enc this header, return unchanged ptr. 1183 dst += rc; 1184 1185 if (input->indexed_type == 0) 1186 { 1187 rc = lshpack_enc_push_entry(enc, input); 1188 if (rc != 0) 1189 return dst_org; //Failed to enc this header, return unchanged ptr. 1190 } 1191 1192 return dst; 1193 } 1194 1195 1196 void 1197 lshpack_enc_set_max_capacity (struct lshpack_enc *enc, unsigned max_capacity) 1198 { 1199 enc->hpe_max_capacity = max_capacity; 1200 henc_remove_overflow_entries(enc); 1201 if (lshpack_enc_hist_used(enc)) 1202 henc_resize_history(enc); 1203 } 1204 1205 #if LS_HPACK_EMIT_TEST_CODE 1206 void 1207 lshpack_enc_iter_init (struct lshpack_enc *enc, void **iter) 1208 { 1209 *iter = STAILQ_FIRST(&enc->hpe_all_entries); 1210 } 1211 1212 1213 /* Returns 0 if entry is found */ 1214 int 1215 lshpack_enc_iter_next (struct lshpack_enc *enc, void **iter, 1216 struct enc_dyn_table_entry *retval) 1217 { 1218 const struct lshpack_enc_table_entry *entry; 1219 1220 entry = *iter; 1221 if (!entry) 1222 return -1; 1223 1224 *iter = STAILQ_NEXT(entry, ete_next_all); 1225 1226 retval->name = ETE_NAME(entry); 1227 retval->value = ETE_VALUE(entry); 1228 retval->name_len = entry->ete_name_len; 1229 retval->value_len = entry->ete_val_len; 1230 retval->entry_id = henc_calc_table_id(enc, entry); 1231 return 0; 1232 } 1233 #endif 1234 1235 1236 /* Dynamic table entry: */ 1237 struct dec_table_entry 1238 { 1239 unsigned dte_name_len; 1240 unsigned dte_val_len; 1241 #if LSHPACK_DEC_CALC_HASH 1242 uint32_t dte_name_hash; 1243 uint32_t dte_nameval_hash; 1244 enum { 1245 DTEF_NAME_HASH = LSXPACK_NAME_HASH, 1246 DTEF_NAMEVAL_HASH = LSXPACK_NAMEVAL_HASH, 1247 } dte_flags:8; 1248 #endif 1249 uint8_t dte_name_idx; 1250 char dte_buf[]; /* Contains both name and value */ 1251 }; 1252 1253 #define DTE_NAME(dte) ((dte)->dte_buf) 1254 #define DTE_VALUE(dte) (&(dte)->dte_buf[(dte)->dte_name_len]) 1255 1256 enum 1257 { 1258 HPACK_HUFFMAN_FLAG_ACCEPTED = 0x01, 1259 HPACK_HUFFMAN_FLAG_SYM = 0x02, 1260 HPACK_HUFFMAN_FLAG_FAIL = 0x04, 1261 }; 1262 1263 struct decode_status 1264 { 1265 uint8_t state; 1266 uint8_t eos; 1267 }; 1268 1269 1270 void 1271 lshpack_dec_init (struct lshpack_dec *dec) 1272 { 1273 memset(dec, 0, sizeof(*dec)); 1274 dec->hpd_max_capacity = INITIAL_DYNAMIC_TABLE_SIZE; 1275 dec->hpd_cur_max_capacity = INITIAL_DYNAMIC_TABLE_SIZE; 1276 lshpack_arr_init(&dec->hpd_dyn_table); 1277 } 1278 1279 1280 void 1281 lshpack_dec_cleanup (struct lshpack_dec *dec) 1282 { 1283 uintptr_t val; 1284 1285 while (lshpack_arr_count(&dec->hpd_dyn_table) > 0) 1286 { 1287 val = lshpack_arr_pop(&dec->hpd_dyn_table); 1288 free((struct dec_table_entry *) val); 1289 } 1290 lshpack_arr_cleanup(&dec->hpd_dyn_table); 1291 } 1292 1293 1294 /* Maximum number of bytes required to encode a 32-bit integer */ 1295 #define LSHPACK_UINT32_ENC_SZ 6 1296 1297 1298 /* Assumption: we have at least one byte to work with */ 1299 #if !LS_HPACK_EMIT_TEST_CODE 1300 static 1301 #endif 1302 int 1303 lshpack_dec_dec_int (const unsigned char **src_p, const unsigned char *src_end, 1304 unsigned prefix_bits, uint32_t *value_p) 1305 { 1306 const unsigned char *const orig_src = *src_p; 1307 const unsigned char *src; 1308 unsigned prefix_max, M; 1309 uint32_t val, B; 1310 1311 src = *src_p; 1312 1313 prefix_max = (1 << prefix_bits) - 1; 1314 val = *src++; 1315 val &= prefix_max; 1316 1317 if (val < prefix_max) 1318 { 1319 *src_p = src; 1320 *value_p = val; 1321 return 0; 1322 } 1323 1324 M = 0; 1325 do 1326 { 1327 if (src < src_end) 1328 { 1329 B = *src++; 1330 val = val + ((B & 0x7f) << M); 1331 M += 7; 1332 } 1333 else if (src - orig_src < LSHPACK_UINT32_ENC_SZ) 1334 return -1; 1335 else 1336 return -2; 1337 } 1338 while (B & 0x80); 1339 1340 if (M <= 28 || (M == 35 && src[-1] <= 0xF && val - (src[-1] << 28) < val)) 1341 { 1342 *src_p = src; 1343 *value_p = val; 1344 return 0; 1345 } 1346 else 1347 return -2; 1348 } 1349 1350 1351 static void 1352 hdec_drop_oldest_entry (struct lshpack_dec *dec) 1353 { 1354 struct dec_table_entry *entry; 1355 entry = (void *) lshpack_arr_shift(&dec->hpd_dyn_table); 1356 dec->hpd_cur_capacity -= DYNAMIC_ENTRY_OVERHEAD + entry->dte_name_len 1357 + entry->dte_val_len; 1358 ++dec->hpd_state; 1359 free(entry); 1360 } 1361 1362 1363 static void 1364 hdec_remove_overflow_entries (struct lshpack_dec *dec) 1365 { 1366 while (dec->hpd_cur_capacity > dec->hpd_cur_max_capacity) 1367 hdec_drop_oldest_entry(dec); 1368 } 1369 1370 1371 static void 1372 hdec_update_max_capacity (struct lshpack_dec *dec, uint32_t new_capacity) 1373 { 1374 dec->hpd_cur_max_capacity = new_capacity; 1375 hdec_remove_overflow_entries(dec); 1376 } 1377 1378 1379 void 1380 lshpack_dec_set_max_capacity (struct lshpack_dec *dec, unsigned max_capacity) 1381 { 1382 dec->hpd_max_capacity = max_capacity; 1383 hdec_update_max_capacity(dec, max_capacity); 1384 } 1385 1386 1387 static unsigned char * 1388 hdec_huff_dec4bits (uint8_t src_4bits, unsigned char *dst, 1389 struct decode_status *status) 1390 { 1391 const struct decode_el cur_dec_code = 1392 decode_tables[status->state][src_4bits]; 1393 if (cur_dec_code.flags & HPACK_HUFFMAN_FLAG_FAIL) { 1394 return NULL; //failed 1395 } 1396 if (cur_dec_code.flags & HPACK_HUFFMAN_FLAG_SYM) 1397 { 1398 *dst = cur_dec_code.sym; 1399 dst++; 1400 } 1401 1402 status->state = cur_dec_code.state; 1403 status->eos = ((cur_dec_code.flags & HPACK_HUFFMAN_FLAG_ACCEPTED) != 0); 1404 return dst; 1405 } 1406 1407 1408 #if !LS_HPACK_USE_LARGE_TABLES 1409 #define lshpack_dec_huff_decode_full lshpack_dec_huff_decode 1410 #endif 1411 1412 static int 1413 lshpack_dec_huff_decode_full (const unsigned char *src, int src_len, 1414 unsigned char *dst, int dst_len) 1415 { 1416 const unsigned char *p_src = src; 1417 const unsigned char *const src_end = src + src_len; 1418 unsigned char *p_dst = dst; 1419 unsigned char *dst_end = dst + dst_len; 1420 struct decode_status status = { 0, 1 }; 1421 1422 while (p_src != src_end) 1423 { 1424 if (p_dst == dst_end) 1425 return LSHPACK_ERR_MORE_BUF; 1426 if ((p_dst = hdec_huff_dec4bits(*p_src >> 4, p_dst, &status)) 1427 == NULL) 1428 return -1; 1429 if (p_dst == dst_end) 1430 return LSHPACK_ERR_MORE_BUF; 1431 if ((p_dst = hdec_huff_dec4bits(*p_src & 0xf, p_dst, &status)) 1432 == NULL) 1433 return -1; 1434 ++p_src; 1435 } 1436 1437 if (!status.eos) 1438 return -1; 1439 1440 return p_dst - dst; 1441 } 1442 1443 1444 static int 1445 lshpack_dec_huff_decode (const unsigned char *src, int src_len, 1446 unsigned char *dst, int dst_len); 1447 1448 1449 //reutrn the length in the dst, also update the src 1450 #if !LS_HPACK_EMIT_TEST_CODE 1451 static 1452 #endif 1453 int 1454 hdec_dec_str (unsigned char *dst, size_t dst_len, const unsigned char **src, 1455 const unsigned char *src_end) 1456 { 1457 if ((*src) == src_end) 1458 return 0; 1459 1460 int is_huffman = (*(*src) & 0x80); 1461 uint32_t len; 1462 if (0 != lshpack_dec_dec_int(src, src_end, 7, &len)) 1463 return LSHPACK_ERR_BAD_DATA; //wrong int 1464 1465 int ret = 0; 1466 if ((uint32_t)(src_end - (*src)) < len) { 1467 return LSHPACK_ERR_BAD_DATA; //wrong int 1468 } 1469 1470 if (is_huffman) 1471 { 1472 ret = lshpack_dec_huff_decode(*src, len, dst, dst_len); 1473 if (ret < 0) 1474 return ret; //Wrong code 1475 1476 (*src) += len; 1477 } 1478 else 1479 { 1480 if (dst_len < len) 1481 { 1482 ret = dst_len - len; 1483 if (ret > LSHPACK_ERR_MORE_BUF) 1484 ret = LSHPACK_ERR_MORE_BUF; //dst not enough space 1485 } 1486 else 1487 { 1488 memcpy(dst, (*src), len); 1489 (*src) += len; 1490 ret = len; 1491 } 1492 } 1493 1494 return ret; 1495 } 1496 1497 1498 /* hpd_dyn_table is a dynamic array. New entries are pushed onto it, 1499 * while old entries are shifted from it. 1500 */ 1501 static struct dec_table_entry * 1502 hdec_get_table_entry (struct lshpack_dec *dec, uint32_t index) 1503 { 1504 uintptr_t val; 1505 1506 index -= HPACK_STATIC_TABLE_SIZE; 1507 if (index == 0 || index > lshpack_arr_count(&dec->hpd_dyn_table)) 1508 return NULL; 1509 1510 index = lshpack_arr_count(&dec->hpd_dyn_table) - index; 1511 val = lshpack_arr_get(&dec->hpd_dyn_table, index); 1512 return (struct dec_table_entry *) val; 1513 } 1514 1515 1516 #if !LS_HPACK_EMIT_TEST_CODE 1517 static 1518 #endif 1519 int 1520 lshpack_dec_push_entry (struct lshpack_dec *dec, 1521 const struct lsxpack_header *xhdr) 1522 { 1523 struct dec_table_entry *entry; 1524 unsigned name_len, val_len; 1525 size_t size; 1526 1527 name_len = xhdr->name_len; 1528 val_len = xhdr->val_len; 1529 1530 size = sizeof(*entry) + name_len + val_len; 1531 entry = malloc(size); 1532 if (!entry) 1533 return -1; 1534 1535 if (0 != lshpack_arr_push(&dec->hpd_dyn_table, (uintptr_t) entry)) 1536 { 1537 free(entry); 1538 return -1; 1539 } 1540 ++dec->hpd_state; 1541 dec->hpd_cur_capacity += DYNAMIC_ENTRY_OVERHEAD + name_len + val_len; 1542 entry->dte_name_len = name_len; 1543 entry->dte_val_len = val_len; 1544 entry->dte_name_idx = xhdr->hpack_index; 1545 #if LSHPACK_DEC_CALC_HASH 1546 entry->dte_flags = xhdr->flags & (LSXPACK_NAME_HASH|LSXPACK_NAMEVAL_HASH); 1547 entry->dte_name_hash = xhdr->name_hash; 1548 entry->dte_nameval_hash = xhdr->nameval_hash; 1549 #endif 1550 memcpy(DTE_NAME(entry), lsxpack_header_get_name(xhdr), name_len); 1551 memcpy(DTE_VALUE(entry), lsxpack_header_get_value(xhdr), val_len); 1552 return 0; 1553 } 1554 1555 1556 static int 1557 lshpack_dec_copy_value (lsxpack_header_t *output, char *dest, const char *val, 1558 unsigned val_len) 1559 { 1560 if (val_len + LSHPACK_DEC_HTTP1X_EXTRA > (unsigned)output->val_len) 1561 return LSHPACK_ERR_MORE_BUF; 1562 output->val_offset = output->name_offset + output->name_len 1563 + LSHPACK_DEC_HTTP1X_EXTRA; 1564 1565 assert(dest == output->buf + output->val_offset); 1566 output->val_len = val_len; 1567 memcpy(dest, val, output->val_len); 1568 dest += output->val_len; 1569 #if LSHPACK_DEC_HTTP1X_OUTPUT 1570 *dest++ = '\r'; 1571 *dest++ = '\n'; 1572 #endif 1573 return 0; 1574 } 1575 1576 1577 static int 1578 lshpack_dec_copy_name (lsxpack_header_t *output, char **dest, const char *name, 1579 unsigned name_len) 1580 { 1581 if (name_len + LSHPACK_DEC_HTTP1X_EXTRA > (unsigned)output->val_len) 1582 return LSHPACK_ERR_MORE_BUF; 1583 output->val_len -= name_len + LSHPACK_DEC_HTTP1X_EXTRA; 1584 output->name_len = name_len; 1585 memcpy(*dest, name, name_len); 1586 *dest += name_len; 1587 #if LSHPACK_DEC_HTTP1X_OUTPUT 1588 *(*dest)++ = ':'; 1589 *(*dest)++ = ' '; 1590 #endif 1591 return 0; 1592 } 1593 1594 1595 enum 1596 { 1597 LSHPACK_ADD_INDEX = 0, 1598 LSHPACK_NO_INDEX = 1, 1599 LSHPACK_NEVER_INDEX = 2, 1600 LSHPACK_VAL_INDEX = 3, 1601 }; 1602 1603 1604 int 1605 lshpack_dec_decode (struct lshpack_dec *dec, 1606 const unsigned char **src, const unsigned char *src_end, 1607 struct lsxpack_header *output) 1608 { 1609 struct dec_table_entry *entry; 1610 uint32_t index, new_capacity; 1611 int indexed_type, len; 1612 const unsigned char *s; 1613 size_t buf_len = output->val_len; 1614 size_t extra_buf = 0; 1615 1616 if ((*src) == src_end) 1617 return LSHPACK_ERR_BAD_DATA; 1618 1619 buf_len = output->val_len; 1620 extra_buf = 0; 1621 s = *src; 1622 while ((*s & 0xe0) == 0x20) //001 xxxxx 1623 { 1624 if (0 != lshpack_dec_dec_int(&s, src_end, 5, &new_capacity)) 1625 return LSHPACK_ERR_BAD_DATA; 1626 if (new_capacity > dec->hpd_max_capacity) 1627 return LSHPACK_ERR_BAD_DATA; 1628 hdec_update_max_capacity(dec, new_capacity); 1629 if (s == src_end) 1630 return LSHPACK_ERR_BAD_DATA; 1631 } 1632 1633 /* lshpack_dec_dec_int() sets `index' and advances `src'. If we do not 1634 * call it, we set `index' and advance `src' ourselves: 1635 */ 1636 if (*s & 0x80) //1 xxxxxxx 1637 { 1638 if (0 != lshpack_dec_dec_int(&s, src_end, 7, &index)) 1639 return LSHPACK_ERR_BAD_DATA; 1640 if (index == 0) 1641 return LSHPACK_ERR_BAD_DATA; 1642 indexed_type = LSHPACK_VAL_INDEX; //need to parse value 1643 } 1644 else if (*s > 0x40) //01 xxxxxx 1645 { 1646 if (0 != lshpack_dec_dec_int(&s, src_end, 6, &index)) 1647 return LSHPACK_ERR_BAD_DATA; 1648 1649 indexed_type = LSHPACK_ADD_INDEX; 1650 } 1651 else if (*s == 0x40) //custmized //0100 0000 1652 { 1653 indexed_type = LSHPACK_ADD_INDEX; 1654 index = LSHPACK_HDR_UNKNOWN; 1655 ++s; 1656 } 1657 1658 //Never indexed 1659 else if (*s == 0x10) //00010000 1660 { 1661 indexed_type = LSHPACK_NEVER_INDEX; 1662 output->flags |= LSXPACK_NEVER_INDEX; 1663 index = LSHPACK_HDR_UNKNOWN; 1664 ++s; 1665 } 1666 else if ((*s & 0xf0) == 0x10) //0001 xxxx 1667 { 1668 if (0 != lshpack_dec_dec_int(&s, src_end, 4, &index)) 1669 return LSHPACK_ERR_BAD_DATA; 1670 1671 indexed_type = LSHPACK_NEVER_INDEX; 1672 output->flags |= LSXPACK_NEVER_INDEX; 1673 } 1674 1675 //without indexed 1676 else if (*s == 0x00) //0000 0000 1677 { 1678 indexed_type = LSHPACK_NO_INDEX; 1679 index = LSHPACK_HDR_UNKNOWN; 1680 ++s; 1681 } 1682 else // 0000 xxxx 1683 { 1684 if (0 != lshpack_dec_dec_int(&s, src_end, 4, &index)) 1685 return LSHPACK_ERR_BAD_DATA; 1686 1687 indexed_type = LSHPACK_NO_INDEX; 1688 } 1689 if (index != LSHPACK_HDR_UNKNOWN && index <= LSHPACK_HDR_WWW_AUTHENTICATE) 1690 { 1691 output->hpack_index = index; 1692 } 1693 1694 char *name = output->buf + output->name_offset; 1695 if (index > 0) 1696 { 1697 if (index <= HPACK_STATIC_TABLE_SIZE) //static table 1698 { 1699 if (lshpack_dec_copy_name(output, &name, 1700 static_table[index - 1].name, 1701 static_table[index - 1].name_len) == LSHPACK_ERR_MORE_BUF) 1702 { 1703 extra_buf = static_table[index - 1].name_len 1704 + LSHPACK_DEC_HTTP1X_EXTRA; 1705 goto need_more_buf; 1706 } 1707 output->flags |= LSXPACK_NAME_HASH; 1708 output->name_hash = static_table_name_hash[index - 1]; 1709 1710 if (indexed_type == LSHPACK_VAL_INDEX) 1711 { 1712 if (lshpack_dec_copy_value(output, name, 1713 static_table[index - 1].val, 1714 static_table[index - 1].val_len) == 0) 1715 { 1716 output->flags |= LSXPACK_NAMEVAL_HASH; 1717 output->nameval_hash = static_table_nameval_hash[index - 1]; 1718 goto decode_end; 1719 } 1720 else 1721 { 1722 extra_buf = static_table[index - 1].val_len 1723 + LSHPACK_DEC_HTTP1X_EXTRA; 1724 goto need_more_buf; 1725 } 1726 } 1727 } 1728 else 1729 { 1730 entry = hdec_get_table_entry(dec, index); 1731 if (entry == NULL) 1732 return LSHPACK_ERR_BAD_DATA; 1733 if (lshpack_dec_copy_name(output, &name, DTE_NAME(entry), 1734 entry->dte_name_len) == LSHPACK_ERR_MORE_BUF) 1735 { 1736 extra_buf = entry->dte_name_len + LSHPACK_DEC_HTTP1X_EXTRA; 1737 goto need_more_buf; 1738 } 1739 1740 if (entry->dte_name_idx) 1741 output->hpack_index = entry->dte_name_idx; 1742 else 1743 output->hpack_index = LSHPACK_HDR_UNKNOWN; 1744 #if LSHPACK_DEC_CALC_HASH 1745 output->flags |= entry->dte_flags & DTEF_NAME_HASH; 1746 output->name_hash = entry->dte_name_hash; 1747 #endif 1748 if (indexed_type == LSHPACK_VAL_INDEX) 1749 { 1750 if (lshpack_dec_copy_value(output, name, DTE_VALUE(entry), 1751 entry->dte_val_len) == 0) 1752 { 1753 #if LSHPACK_DEC_CALC_HASH 1754 output->flags |= entry->dte_flags & DTEF_NAMEVAL_HASH; 1755 output->nameval_hash = entry->dte_nameval_hash; 1756 #endif 1757 goto decode_end; 1758 } 1759 else 1760 { 1761 extra_buf = entry->dte_val_len + LSHPACK_DEC_HTTP1X_EXTRA; 1762 goto need_more_buf; 1763 } 1764 } 1765 } 1766 } 1767 else 1768 { 1769 len = hdec_dec_str((unsigned char *)name, output->val_len, 1770 &s, src_end); 1771 if (len < 0) 1772 { 1773 if (len <= LSHPACK_ERR_MORE_BUF) 1774 { 1775 extra_buf = -len; 1776 goto need_more_buf; 1777 } 1778 return len; //error 1779 } 1780 if (len > UINT16_MAX) 1781 return LSHPACK_ERR_TOO_LARGE; 1782 #if LSHPACK_DEC_CALC_HASH 1783 output->flags |= LSXPACK_NAME_HASH; 1784 output->name_hash = XXH32(name, (size_t) len, LSHPACK_XXH_SEED); 1785 #endif 1786 output->name_len = len; 1787 name += output->name_len; 1788 #if LSHPACK_DEC_HTTP1X_OUTPUT 1789 if (output->name_len + 2 <= output->val_len) 1790 { 1791 *name++ = ':'; 1792 *name++ = ' '; 1793 } 1794 else 1795 { 1796 extra_buf = 2; 1797 goto need_more_buf; 1798 } 1799 #endif 1800 output->val_len -= len + LSHPACK_DEC_HTTP1X_EXTRA; 1801 } 1802 1803 len = hdec_dec_str((unsigned char *)name, output->val_len, &s, src_end); 1804 if (len < 0) 1805 { 1806 if (len <= LSHPACK_ERR_MORE_BUF) 1807 { 1808 extra_buf = -len; 1809 goto need_more_buf; 1810 } 1811 return len; //error 1812 } 1813 if (len > UINT16_MAX) 1814 return LSHPACK_ERR_TOO_LARGE; 1815 #if LSHPACK_DEC_CALC_HASH 1816 assert(output->flags & LSXPACK_NAME_HASH); 1817 output->flags |= LSXPACK_NAMEVAL_HASH; 1818 output->nameval_hash = XXH32(name, (size_t) len, output->name_hash); 1819 #endif 1820 #if LSHPACK_DEC_HTTP1X_OUTPUT 1821 if ((unsigned) len + 2 <= output->val_len) 1822 memcpy(name + len, "\r\n", 2); 1823 else 1824 { 1825 extra_buf = 2; 1826 goto need_more_buf; 1827 } 1828 #endif 1829 output->val_offset = output->name_offset + output->name_len 1830 + LSHPACK_DEC_HTTP1X_EXTRA; 1831 output->val_len = len; 1832 1833 if (indexed_type == LSHPACK_ADD_INDEX && 1834 0 != lshpack_dec_push_entry(dec, output)) 1835 return LSHPACK_ERR_BAD_DATA; //error 1836 decode_end: 1837 *src = s; 1838 #if LSHPACK_DEC_HTTP1X_OUTPUT 1839 output->dec_overhead = 4; 1840 #endif 1841 return 0; 1842 need_more_buf: 1843 buf_len += extra_buf; 1844 output->val_len = buf_len; 1845 return LSHPACK_ERR_MORE_BUF; 1846 } 1847 1848 1849 #if LS_HPACK_USE_LARGE_TABLES 1850 #define SHORTEST_CODE 5 1851 1852 1853 /* The decoder is optimized for the common case. Most of the time, we decode 1854 * data whose encoding is 16 bits or shorter. This lets us use a 64 KB table 1855 * indexed by two bytes of input and outputs 1, 2, or 3 bytes at a time. 1856 * 1857 * In the case a longer code is encoutered, we fall back to the original 1858 * Huffman decoder that supports all code lengths. 1859 */ 1860 static int 1861 lshpack_dec_huff_decode (const unsigned char *src, int src_len, 1862 unsigned char *dst, int dst_len) 1863 { 1864 unsigned char *const orig_dst = dst; 1865 const unsigned char *const src_end = src + src_len; 1866 unsigned char *const dst_end = dst + dst_len; 1867 uintptr_t buf; /* OK not to initialize the buffer */ 1868 unsigned avail_bits, len; 1869 struct hdec hdec; 1870 uint16_t idx; 1871 int r; 1872 1873 #if __GNUC__ 1874 #pragma GCC diagnostic push 1875 #pragma GCC diagnostic ignored "-Wmaybe-uninitialized" 1876 #pragma GCC diagnostic ignored "-Wuninitialized" 1877 #else 1878 buf = 0; 1879 #endif 1880 1881 avail_bits = 0; 1882 while (1) 1883 { 1884 if (src + sizeof(buf) <= src_end) 1885 { 1886 len = (sizeof(buf) * 8 - avail_bits) >> 3; 1887 avail_bits += len << 3; 1888 switch (len) 1889 { 1890 #if UINTPTR_MAX == 18446744073709551615ull 1891 case 8: 1892 buf <<= 8; 1893 buf |= (uintptr_t) *src++; 1894 /* fall through */ 1895 case 7: 1896 buf <<= 8; 1897 buf |= (uintptr_t) *src++; 1898 /* fall through */ 1899 default: 1900 buf <<= 48; 1901 buf |= (uintptr_t) *src++ << 40; 1902 buf |= (uintptr_t) *src++ << 32; 1903 buf |= (uintptr_t) *src++ << 24; 1904 buf |= (uintptr_t) *src++ << 16; 1905 #else 1906 /* fall through */ 1907 case 4: 1908 buf <<= 8; 1909 buf |= (uintptr_t) *src++; 1910 /* fall through */ 1911 case 3: 1912 buf <<= 8; 1913 buf |= (uintptr_t) *src++; 1914 /* fall through */ 1915 default: 1916 buf <<= 16; 1917 #endif 1918 buf |= (uintptr_t) *src++ << 8; 1919 buf |= (uintptr_t) *src++ << 0; 1920 } 1921 } 1922 else if (src < src_end) 1923 do 1924 { 1925 buf <<= 8; 1926 buf |= (uintptr_t) *src++; 1927 avail_bits += 8; 1928 } 1929 while (src < src_end && avail_bits <= sizeof(buf) * 8 - 8); 1930 else 1931 break; /* Normal case terminating condition: out of input */ 1932 1933 if (dst_end - dst >= (ptrdiff_t) (8 * sizeof(buf) / SHORTEST_CODE) 1934 && avail_bits >= 16) 1935 { 1936 /* Fast path: don't check destination bounds */ 1937 do 1938 { 1939 idx = buf >> (avail_bits - 16); 1940 hdec = hdecs[idx]; 1941 dst[0] = hdec.out[0]; 1942 dst[1] = hdec.out[1]; 1943 dst[2] = hdec.out[2]; 1944 dst += hdec.lens & 3; 1945 avail_bits -= hdec.lens >> 2; 1946 } 1947 while (avail_bits >= 16 && hdec.lens); 1948 if (avail_bits < 16) 1949 continue; 1950 goto slow_path; 1951 } 1952 else 1953 while (avail_bits >= 16) 1954 { 1955 idx = buf >> (avail_bits - 16); 1956 hdec = hdecs[idx]; 1957 len = hdec.lens & 3; 1958 if (len && dst + len <= dst_end) 1959 { 1960 switch (len) 1961 { 1962 case 3: 1963 *dst++ = hdec.out[0]; 1964 *dst++ = hdec.out[1]; 1965 *dst++ = hdec.out[2]; 1966 break; 1967 case 2: 1968 *dst++ = hdec.out[0]; 1969 *dst++ = hdec.out[1]; 1970 break; 1971 default: 1972 *dst++ = hdec.out[0]; 1973 break; 1974 } 1975 avail_bits -= hdec.lens >> 2; 1976 } 1977 else if (dst + len > dst_end) 1978 { 1979 r = dst_end - dst - len; 1980 if (r > LSHPACK_ERR_MORE_BUF) 1981 r = LSHPACK_ERR_MORE_BUF; 1982 return r; 1983 } 1984 else 1985 goto slow_path; 1986 } 1987 } 1988 1989 if (avail_bits >= SHORTEST_CODE) 1990 { 1991 idx = buf << (16 - avail_bits); 1992 idx |= (1 << (16 - avail_bits)) - 1; /* EOF */ 1993 if (idx == 0xFFFF && avail_bits < 8) 1994 goto end; 1995 /* If a byte or more of input is left, this mean there is a valid 1996 * encoding, not just EOF. 1997 */ 1998 hdec = hdecs[idx]; 1999 len = hdec.lens & 3; 2000 if (((unsigned) hdec.lens >> 2) > avail_bits) 2001 return -1; 2002 if (len && dst + len <= dst_end) 2003 { 2004 switch (len) 2005 { 2006 case 3: 2007 *dst++ = hdec.out[0]; 2008 *dst++ = hdec.out[1]; 2009 *dst++ = hdec.out[2]; 2010 break; 2011 case 2: 2012 *dst++ = hdec.out[0]; 2013 *dst++ = hdec.out[1]; 2014 break; 2015 default: 2016 *dst++ = hdec.out[0]; 2017 break; 2018 } 2019 avail_bits -= hdec.lens >> 2; 2020 } 2021 else if (dst + len > dst_end) 2022 { 2023 r = dst_end - dst - len; 2024 if (r > LSHPACK_ERR_MORE_BUF) 2025 r = LSHPACK_ERR_MORE_BUF; 2026 return r; 2027 } 2028 else 2029 /* This must be an invalid code, otherwise it would have fit */ 2030 return -1; 2031 } 2032 2033 if (avail_bits > 0) 2034 { 2035 if (((1u << avail_bits) - 1) != (buf & ((1u << avail_bits) - 1))) 2036 return -1; /* Not EOF as expected */ 2037 } 2038 #if __GNUC__ 2039 #pragma GCC diagnostic pop 2040 #endif 2041 2042 end: 2043 return dst - orig_dst; 2044 2045 slow_path: 2046 /* Find previous byte boundary and finish decoding thence. */ 2047 while ((avail_bits & 7) && dst > orig_dst) 2048 avail_bits += encode_table[ *--dst ].bits; 2049 assert((avail_bits & 7) == 0); 2050 src -= avail_bits >> 3; 2051 r = lshpack_dec_huff_decode_full(src, src_end - src, dst, dst_end - dst); 2052 if (r >= 0) 2053 return dst - orig_dst + r; 2054 else 2055 return r; 2056 } 2057 #endif 2058 #if __GNUC__ 2059 #pragma GCC diagnostic pop /* -Wunknown-pragmas */ 2060 #endif 2061