1/* 2 * lsqpack.c -- LiteSpeed QPACK Compression Library: encoder and decoder. 3 */ 4/* 5MIT License 6 7Copyright (c) 2018 - 2022 LiteSpeed Technologies Inc 8 9Permission is hereby granted, free of charge, to any person obtaining a copy 10of this software and associated documentation files (the "Software"), to deal 11in the Software without restriction, including without limitation the rights 12to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 13copies of the Software, and to permit persons to whom the Software is 14furnished to do so, subject to the following conditions: 15 16The above copyright notice and this permission notice shall be included in all 17copies or substantial portions of the Software. 18 19THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 20IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 21FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 22AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 23LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 24OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 25SOFTWARE. 26*/ 27 28#ifndef LS_QPACK_USE_LARGE_TABLES 29#define LS_QPACK_USE_LARGE_TABLES 1 30#endif 31 32#include <assert.h> 33#include <errno.h> 34#include <math.h> 35#include <stdint.h> 36#include <stdlib.h> 37#include <string.h> 38#include <sys/queue.h> 39#include <sys/types.h> 40#include <inttypes.h> 41 42#include "lsqpack.h" 43#include "lsxpack_header.h" 44 45#ifdef XXH_HEADER_NAME 46#include XXH_HEADER_NAME 47#else 48#include <xxhash.h> 49#endif 50 51#include "huff-tables.h" 52 53#define MIN(a, b) ((a) < (b) ? (a) : (b)) 54#define MAX(a, b) ((a) > (b) ? (a) : (b)) 55 56static unsigned char * 57qenc_huffman_enc (const unsigned char *, const unsigned char *const, unsigned char *); 58 59static unsigned 60qenc_enc_str_size (const unsigned char *, unsigned); 61 62struct static_table_entry 63{ 64 const char *name; 65 const char *val; 66 unsigned name_len; 67 unsigned val_len; 68}; 69 70/* [draft-ietf-quic-qpack-03] Appendix A */ 71static const struct static_table_entry static_table[] = 72{ 73 {":authority", "", 10, 0,}, 74 {":path", "/", 5, 1,}, 75 {"age", "0", 3, 1,}, 76 {"content-disposition", "", 19, 0,}, 77 {"content-length", "0", 14, 1,}, 78 {"cookie", "", 6, 0,}, 79 {"date", "", 4, 0,}, 80 {"etag", "", 4, 0,}, 81 {"if-modified-since", "", 17, 0,}, 82 {"if-none-match", "", 13, 0,}, 83 {"last-modified", "", 13, 0,}, 84 {"link", "", 4, 0,}, 85 {"location", "", 8, 0,}, 86 {"referer", "", 7, 0,}, 87 {"set-cookie", "", 10, 0,}, 88 {":method", "CONNECT", 7, 7,}, 89 {":method", "DELETE", 7, 6,}, 90 {":method", "GET", 7, 3,}, 91 {":method", "HEAD", 7, 4,}, 92 {":method", "OPTIONS", 7, 7,}, 93 {":method", "POST", 7, 4,}, 94 {":method", "PUT", 7, 3,}, 95 {":scheme", "http", 7, 4,}, 96 {":scheme", "https", 7, 5,}, 97 {":status", "103", 7, 3,}, 98 {":status", "200", 7, 3,}, 99 {":status", "304", 7, 3,}, 100 {":status", "404", 7, 3,}, 101 {":status", "503", 7, 3,}, 102 {"accept", "*/*", 6, 3,}, 103 {"accept", "application/dns-message", 6, 23,}, 104 {"accept-encoding", "gzip, deflate, br", 15, 17,}, 105 {"accept-ranges", "bytes", 13, 5,}, 106 {"access-control-allow-headers", "cache-control", 28, 13,}, 107 {"access-control-allow-headers", "content-type", 28, 12,}, 108 {"access-control-allow-origin", "*", 27, 1,}, 109 {"cache-control", "max-age=0", 13, 9,}, 110 {"cache-control", "max-age=2592000", 13, 15,}, 111 {"cache-control", "max-age=604800", 13, 14,}, 112 {"cache-control", "no-cache", 13, 8,}, 113 {"cache-control", "no-store", 13, 8,}, 114 {"cache-control", "public, max-age=31536000", 13, 24,}, 115 {"content-encoding", "br", 16, 2,}, 116 {"content-encoding", "gzip", 16, 4,}, 117 {"content-type", "application/dns-message", 12, 23,}, 118 {"content-type", "application/javascript", 12, 22,}, 119 {"content-type", "application/json", 12, 16,}, 120 {"content-type", "application/x-www-form-urlencoded", 12, 33,}, 121 {"content-type", "image/gif", 12, 9,}, 122 {"content-type", "image/jpeg", 12, 10,}, 123 {"content-type", "image/png", 12, 9,}, 124 {"content-type", "text/css", 12, 8,}, 125 {"content-type", "text/html; charset=utf-8", 12, 24,}, 126 {"content-type", "text/plain", 12, 10,}, 127 {"content-type", "text/plain;charset=utf-8", 12, 24,}, 128 {"range", "bytes=0-", 5, 8,}, 129 {"strict-transport-security", "max-age=31536000", 25, 16,}, 130 {"strict-transport-security", "max-age=31536000; includesubdomains", 131 25, 35,}, 132 {"strict-transport-security", 133 "max-age=31536000; includesubdomains; preload", 25, 44,}, 134 {"vary", "accept-encoding", 4, 15,}, 135 {"vary", "origin", 4, 6,}, 136 {"x-content-type-options", "nosniff", 22, 7,}, 137 {"x-xss-protection", "1; mode=block", 16, 13,}, 138 {":status", "100", 7, 3,}, 139 {":status", "204", 7, 3,}, 140 {":status", "206", 7, 3,}, 141 {":status", "302", 7, 3,}, 142 {":status", "400", 7, 3,}, 143 {":status", "403", 7, 3,}, 144 {":status", "421", 7, 3,}, 145 {":status", "425", 7, 3,}, 146 {":status", "500", 7, 3,}, 147 {"accept-language", "", 15, 0,}, 148 {"access-control-allow-credentials", "FALSE", 32, 5,}, 149 {"access-control-allow-credentials", "TRUE", 32, 4,}, 150 {"access-control-allow-headers", "*", 28, 1,}, 151 {"access-control-allow-methods", "get", 28, 3,}, 152 {"access-control-allow-methods", "get, post, options", 28, 18,}, 153 {"access-control-allow-methods", "options", 28, 7,}, 154 {"access-control-expose-headers", "content-length", 29, 14,}, 155 {"access-control-request-headers", "content-type", 30, 12,}, 156 {"access-control-request-method", "get", 29, 3,}, 157 {"access-control-request-method", "post", 29, 4,}, 158 {"alt-svc", "clear", 7, 5,}, 159 {"authorization", "", 13, 0,}, 160 {"content-security-policy", 161 "script-src 'none'; object-src 'none'; base-uri 'none'", 23, 53,}, 162 {"early-data", "1", 10, 1,}, 163 {"expect-ct", "", 9, 0,}, 164 {"forwarded", "", 9, 0,}, 165 {"if-range", "", 8, 0,}, 166 {"origin", "", 6, 0,}, 167 {"purpose", "prefetch", 7, 8,}, 168 {"server", "", 6, 0,}, 169 {"timing-allow-origin", "*", 19, 1,}, 170 {"upgrade-insecure-requests", "1", 25, 1,}, 171 {"user-agent", "", 10, 0,}, 172 {"x-forwarded-for", "", 15, 0,}, 173 {"x-frame-options", "deny", 15, 4,}, 174 {"x-frame-options", "sameorigin", 15, 10,}, 175}; 176 177#define QPACK_STATIC_TABLE_SIZE (sizeof(static_table) / sizeof(static_table[0])) 178 179/* RFC 7541, Section 4.1: 180 * 181 * " The size of the dynamic table is the sum of the size of its entries. 182 * " 183 * " The size of an entry is the sum of its name's length in octets (as 184 * " defined in Section 5.2), its value's length in octets, and 32. 185 */ 186#define DYNAMIC_ENTRY_OVERHEAD 32u 187 188/* Initial guess at number of header fields per list: */ 189#define GUESS_N_HEADER_FIELDS 12 190 191#define MAX_QUIC_STREAM_ID ((1ull << 62) - 1) 192 193#ifdef LSQPACK_ENC_LOGGER_HEADER 194#include LSQPACK_ENC_LOGGER_HEADER 195#else 196#define E_LOG(prefix, ...) do { \ 197 if (enc->qpe_logger_ctx) { \ 198 fprintf(enc->qpe_logger_ctx, prefix); \ 199 fprintf(enc->qpe_logger_ctx, __VA_ARGS__); \ 200 fprintf(enc->qpe_logger_ctx, "\n"); \ 201 } \ 202} while (0) 203#define E_DEBUG(...) E_LOG("qenc: debug: ", __VA_ARGS__) 204#define E_INFO(...) E_LOG("qenc: info: ", __VA_ARGS__) 205#define E_WARN(...) E_LOG("qenc: warn: ", __VA_ARGS__) 206#define E_ERROR(...) E_LOG("qenc: error: ", __VA_ARGS__) 207#endif 208 209/* Entries in the encoder's dynamic table are hashed 1) by name and 2) by 210 * name and value. Instead of having two arrays of buckets, the encoder 211 * keeps just one, but each bucket has two heads. 212 */ 213struct lsqpack_double_enc_head 214{ 215 struct lsqpack_enc_head by_name; 216 struct lsqpack_enc_head by_nameval; 217}; 218 219struct lsqpack_enc_table_entry 220{ 221 /* An entry always lives on all three lists */ 222 STAILQ_ENTRY(lsqpack_enc_table_entry) 223 ete_next_nameval, 224 ete_next_name, 225 ete_next_all; 226 lsqpack_abs_id_t ete_id; 227 unsigned ete_when_added_used; 228 unsigned ete_when_added_dropped; 229 unsigned ete_n_reffd; 230 unsigned ete_nameval_hash; 231 unsigned ete_name_hash; 232 unsigned ete_name_len; 233 unsigned ete_val_len; 234 char ete_buf[0]; 235}; 236 237#define ETE_NAME(ete) ((ete)->ete_buf) 238#define ETE_VALUE(ete) (&(ete)->ete_buf[(ete)->ete_name_len]) 239#define ENTRY_COST(name_len, value_len) (DYNAMIC_ENTRY_OVERHEAD + \ 240 name_len + value_len) 241#define ETE_SIZE(ete) ENTRY_COST((ete)->ete_name_len, (ete)->ete_val_len) 242 243 244#define N_BUCKETS(n_bits) (1U << (n_bits)) 245#define BUCKNO(n_bits, hash) ((hash) & (N_BUCKETS(n_bits) - 1)) 246 247struct lsqpack_header_info 248{ 249 TAILQ_ENTRY(lsqpack_header_info) qhi_next_all; 250 TAILQ_ENTRY(lsqpack_header_info) qhi_next_risked; 251 struct lsqpack_header_info *qhi_same_stream_id; /* Circular list */ 252 uint64_t qhi_stream_id; 253 unsigned qhi_seqno; 254 unsigned qhi_bytes_inserted; 255 lsqpack_abs_id_t qhi_min_id; 256 lsqpack_abs_id_t qhi_max_id; 257}; 258 259/* Absolute index starts with 1. 0 indicates that the value is not set */ 260#define HINFO_IDS_SET(hinfo) ((hinfo)->qhi_max_id != 0) 261 262/* Header info structures are kept in a list of arrays, which is faster than 263 * searching through a linked list whose elements may be all over the place 264 * in memory. This is important because we need to look up header infos by 265 * stream ID and also calculate the minimum absolute ID. If not sequential 266 * search, we would need to implement a hybrid of min-heap and a hash (or 267 * search tree) and that seems to be an overkill for something that is not 268 * likely to have more than a few hundred elements at the most. 269 */ 270struct lsqpack_header_info_arr 271{ 272 STAILQ_ENTRY(lsqpack_header_info_arr) hia_next; 273 uint64_t hia_slots; 274 struct lsqpack_header_info hia_hinfos[64]; 275}; 276 277static unsigned 278find_free_slot (uint64_t slots) 279{ 280#if __GNUC__ 281 return __builtin_ffsll(~slots) - 1; 282#else 283 unsigned n; 284 285 slots =~ slots; 286 n = 0; 287 288 if (0 == (slots & ((1ULL << 32) - 1))) { n += 32; slots >>= 32; } 289 if (0 == (slots & ((1ULL << 16) - 1))) { n += 16; slots >>= 16; } 290 if (0 == (slots & ((1ULL << 8) - 1))) { n += 8; slots >>= 8; } 291 if (0 == (slots & ((1ULL << 4) - 1))) { n += 4; slots >>= 4; } 292 if (0 == (slots & ((1ULL << 2) - 1))) { n += 2; slots >>= 2; } 293 if (0 == (slots & ((1ULL << 1) - 1))) { n += 1; slots >>= 1; } 294 return n; 295#endif 296} 297 298static struct lsqpack_header_info * 299enc_alloc_hinfo (struct lsqpack_enc *enc) 300{ 301 struct lsqpack_header_info_arr *hiarr; 302 struct lsqpack_header_info *hinfo; 303 unsigned slot; 304 305 STAILQ_FOREACH(hiarr, &enc->qpe_hinfo_arrs, hia_next) 306 if (hiarr->hia_slots != ~0ULL) 307 break; 308 309 if (!hiarr) 310 { 311 if (0 == (enc->qpe_flags & LSQPACK_ENC_NO_MEM_GUARD) 312 && enc->qpe_hinfo_arrs_count * sizeof(*hiarr) 313 >= enc->qpe_cur_max_capacity) 314 return NULL; 315 hiarr = malloc(sizeof(*hiarr)); 316 if (!hiarr) 317 return NULL; 318 hiarr->hia_slots = 0; 319 STAILQ_INSERT_TAIL(&enc->qpe_hinfo_arrs, hiarr, hia_next); 320 ++enc->qpe_hinfo_arrs_count; 321 } 322 323 slot = find_free_slot(hiarr->hia_slots); 324 hiarr->hia_slots |= 1ULL << slot; 325 hinfo = &hiarr->hia_hinfos[ slot ]; 326 memset(hinfo, 0, sizeof(*hinfo)); 327 hinfo->qhi_same_stream_id = hinfo; 328 TAILQ_INSERT_TAIL(&enc->qpe_all_hinfos, hinfo, qhi_next_all); 329 return hinfo; 330} 331 332static void 333enc_free_hinfo (struct lsqpack_enc *enc, struct lsqpack_header_info *hinfo) 334{ 335 struct lsqpack_header_info_arr *hiarr; 336 unsigned slot; 337 338 STAILQ_FOREACH(hiarr, &enc->qpe_hinfo_arrs, hia_next) 339 if (hinfo >= hiarr->hia_hinfos && hinfo < &hiarr->hia_hinfos[64]) 340 { 341 slot = hinfo - hiarr->hia_hinfos; 342 hiarr->hia_slots &= ~(1ULL << slot); 343 TAILQ_REMOVE(&enc->qpe_all_hinfos, &hiarr->hia_hinfos[slot], qhi_next_all); 344 return; 345 } 346 347 assert(0); 348} 349 350static int 351enc_use_dynamic_table (const struct lsqpack_enc *enc) 352{ 353 return enc->qpe_max_entries > 0 354 && enc->qpe_cur_header.hinfo != NULL 355 && enc->qpe_cur_header.hinfo->qhi_bytes_inserted 356 < enc->qpe_cur_max_capacity / 2; 357} 358 359 360enum he { HE_NAME, HE_NAMEVAL, N_HES }; 361 362 363struct lsqpack_hist_el { 364 unsigned he_hashes[N_HES]; 365}; 366 367 368static void 369qenc_hist_update_size (struct lsqpack_enc *enc, unsigned new_size) 370{ 371 struct lsqpack_hist_el *els; 372 unsigned first, count, i, j; 373 374 if (new_size == enc->qpe_hist_nels) 375 return; 376 377 if (new_size == 0) 378 { 379 enc->qpe_hist_nels = 0; 380 enc->qpe_hist_idx = 0; 381 enc->qpe_hist_wrapped = 0; 382 return; 383 } 384 385 els = malloc(sizeof(els[0]) * (new_size + 1)); 386 if (!els) 387 return; 388 389 E_DEBUG("history size change from %u to %u", enc->qpe_hist_nels, new_size); 390 391 if (enc->qpe_hist_wrapped) 392 { 393 first = (enc->qpe_hist_idx + 1) % enc->qpe_hist_nels; 394 count = enc->qpe_hist_nels; 395 } 396 else 397 { 398 first = 0; 399 count = enc->qpe_hist_idx; 400 } 401 for (i = 0, j = 0; count > 0 && j < new_size; ++i, ++j, --count) 402 els[j] = enc->qpe_hist_els[ (first + i) % enc->qpe_hist_nels ]; 403 enc->qpe_hist_nels = new_size; 404 enc->qpe_hist_idx = j % new_size; 405 enc->qpe_hist_wrapped = enc->qpe_hist_idx == 0; 406 free(enc->qpe_hist_els); 407 enc->qpe_hist_els = els; 408} 409 410 411static void 412qenc_hist_add (struct lsqpack_enc *enc, unsigned name_hash, 413 unsigned nameval_hash) 414{ 415 if (enc->qpe_hist_nels) 416 { 417 enc->qpe_hist_els[ enc->qpe_hist_idx ].he_hashes[HE_NAME] = name_hash; 418 enc->qpe_hist_els[ enc->qpe_hist_idx ].he_hashes[HE_NAMEVAL] 419 = nameval_hash; 420 enc->qpe_hist_idx = (enc->qpe_hist_idx + 1) % enc->qpe_hist_nels; 421 enc->qpe_hist_wrapped |= enc->qpe_hist_idx == 0; 422 } 423} 424 425 426static int 427qenc_hist_seen (struct lsqpack_enc *enc, enum he he, unsigned hash) 428{ 429 const struct lsqpack_hist_el *el; 430 unsigned last_idx; 431 432 if (enc->qpe_hist_els) 433 { 434 if (enc->qpe_hist_wrapped) 435 last_idx = enc->qpe_hist_nels; 436 else 437 last_idx = enc->qpe_hist_idx; 438 enc->qpe_hist_els[ last_idx ].he_hashes[he] = hash; 439 for (el = enc->qpe_hist_els; el->he_hashes[he] != hash; ++el) 440 ; 441 return el < &enc->qpe_hist_els[ last_idx ]; 442 } 443 else 444 return 1; 445} 446 447 448unsigned char * 449lsqpack_enc_int (unsigned char *, unsigned char *const, uint64_t, unsigned); 450 451 452void 453lsqpack_enc_preinit (struct lsqpack_enc *enc, void *logger_ctx) 454{ 455 memset(enc, 0, sizeof(*enc)); 456 STAILQ_INIT(&enc->qpe_all_entries); 457 STAILQ_INIT(&enc->qpe_hinfo_arrs); 458 TAILQ_INIT(&enc->qpe_all_hinfos); 459 TAILQ_INIT(&enc->qpe_risked_hinfos); 460 enc->qpe_logger_ctx = logger_ctx; 461 E_DEBUG("preinitialized"); 462}; 463 464 465int 466lsqpack_enc_init (struct lsqpack_enc *enc, void *logger_ctx, 467 unsigned max_table_size, unsigned dyn_table_size, 468 unsigned max_risked_streams, enum lsqpack_enc_opts enc_opts, 469 unsigned char *tsu_buf, size_t *tsu_buf_sz) 470{ 471 struct lsqpack_double_enc_head *buckets; 472 unsigned char *p; 473 unsigned nbits = 2; 474 unsigned i; 475 476 if (dyn_table_size > max_table_size) 477 { 478 errno = EINVAL; 479 return -1; 480 } 481 482 if (!(enc_opts & LSQPACK_ENC_OPT_STAGE_2)) 483 lsqpack_enc_preinit(enc, logger_ctx); 484 485 if (dyn_table_size != LSQPACK_DEF_DYN_TABLE_SIZE) 486 { 487 if (!(tsu_buf && tsu_buf_sz && *tsu_buf_sz)) 488 { 489 errno = EINVAL; 490 return -1; 491 } 492 p = tsu_buf; 493 *p = 0x20; 494 p = lsqpack_enc_int(p, tsu_buf + *tsu_buf_sz, dyn_table_size, 5); 495 if (p <= tsu_buf) 496 { 497 errno = ENOBUFS; 498 return -1; 499 } 500 E_DEBUG("generated TSU=%u instruction %zd byte%.*s in size", 501 dyn_table_size, p - tsu_buf, p - tsu_buf != 1, "s"); 502 *tsu_buf_sz = p - tsu_buf; 503 } 504 else if (tsu_buf_sz) 505 *tsu_buf_sz = 0; 506 507 if (!(enc_opts & LSQPACK_ENC_OPT_IX_AGGR)) 508 { 509 enc->qpe_hist_nels = MAX( 510 /* Initial guess at number of entries in dynamic table: */ 511 dyn_table_size / DYNAMIC_ENTRY_OVERHEAD / 3, 512 GUESS_N_HEADER_FIELDS 513 ); 514 enc->qpe_hist_els = malloc(sizeof(enc->qpe_hist_els[0]) * (enc->qpe_hist_nels + 1)); 515 if (!enc->qpe_hist_els) 516 return -1; 517 } 518 else 519 { 520 enc->qpe_hist_nels = 0; 521 enc->qpe_hist_els = NULL; 522 } 523 524 if (max_table_size / DYNAMIC_ENTRY_OVERHEAD) 525 { 526 nbits = 2; 527 buckets = malloc(sizeof(buckets[0]) * N_BUCKETS(nbits)); 528 if (!buckets) 529 { 530 free(enc->qpe_hist_els); 531 return -1; 532 } 533 534 for (i = 0; i < N_BUCKETS(nbits); ++i) 535 { 536 STAILQ_INIT(&buckets[i].by_name); 537 STAILQ_INIT(&buckets[i].by_nameval); 538 } 539 } 540 else 541 { 542 nbits = 0; 543 buckets = NULL; 544 } 545 546 enc->qpe_max_entries = max_table_size / DYNAMIC_ENTRY_OVERHEAD; 547 enc->qpe_real_max_capacity = max_table_size; 548 enc->qpe_cur_max_capacity = dyn_table_size; 549 enc->qpe_max_risked_streams = max_risked_streams; 550 enc->qpe_buckets = buckets; 551 enc->qpe_nbits = nbits; 552 enc->qpe_logger_ctx = logger_ctx; 553 if (!(enc_opts & LSQPACK_ENC_OPT_NO_DUP)) 554 enc->qpe_flags |= LSQPACK_ENC_USE_DUP; 555 if (enc_opts & LSQPACK_ENC_OPT_NO_MEM_GUARD) 556 enc->qpe_flags |= LSQPACK_ENC_NO_MEM_GUARD; 557 E_DEBUG("initialized. opts: 0x%X; max capacity: %u; max risked " 558 "streams: %u.", enc_opts, enc->qpe_cur_max_capacity, 559 enc->qpe_max_risked_streams); 560 561 return 0; 562} 563 564 565void 566lsqpack_enc_cleanup (struct lsqpack_enc *enc) 567{ 568 struct lsqpack_enc_table_entry *entry, *next; 569 struct lsqpack_header_info_arr *hiarr, *next_hiarr; 570 571 for (entry = STAILQ_FIRST(&enc->qpe_all_entries); entry; entry = next) 572 { 573 next = STAILQ_NEXT(entry, ete_next_all); 574 free(entry); 575 } 576 577 for (hiarr = STAILQ_FIRST(&enc->qpe_hinfo_arrs); hiarr; hiarr = next_hiarr) 578 { 579 next_hiarr = STAILQ_NEXT(hiarr, hia_next); 580 free(hiarr); 581 } 582 583 free(enc->qpe_buckets); 584 free(enc->qpe_hist_els); 585 E_DEBUG("cleaned up"); 586} 587 588 589#define LSQPACK_XXH_SEED 39378473 590#define XXH_NAME_WIDTH 9 591#define XXH_NAME_SHIFT 0 592#define XXH_NAMEVAL_WIDTH 9 593#define XXH_NAMEVAL_SHIFT 0 594 595static const unsigned char name2id_plus_one[ 1 << XXH_NAME_WIDTH ] = 596{ 597 [347] = 1, [397] = 2, [64] = 3, [144] = 4, [25] = 5, 598 [216] = 6, [361] = 7, [442] = 8, [190] = 9, [404] = 10, 599 [181] = 11, [210] = 12, [38] = 13, [51] = 14, [318] = 15, 600 [484] = 16, [81] = 23, [83] = 25, [248] = 30, [169] = 32, 601 [456] = 33, [479] = 34, [59] = 36, [498] = 37, [401] = 43, 602 [453] = 45, [266] = 56, [88] = 57, [317] = 60, [74] = 62, 603 [189] = 63, [211] = 73, [334] = 74, [365] = 77, [382] = 80, 604 [377] = 81, [257] = 82, [56] = 84, [321] = 85, [79] = 86, 605 [384] = 87, [357] = 88, [438] = 89, [84] = 90, [264] = 91, 606 [146] = 92, [225] = 93, [490] = 94, [305] = 95, [362] = 96, 607 [486] = 97, [497] = 98, 608}; 609 610static const unsigned char nameval2id_plus_one[ 1 << XXH_NAMEVAL_WIDTH ] = 611{ 612 [150] = 1, [502] = 2, [353] = 3, [262] = 4, [443] = 5, 613 [164] = 6, [463] = 7, [84] = 8, [205] = 9, [228] = 10, 614 [451] = 11, [444] = 12, [176] = 13, [75] = 14, [399] = 15, 615 [56] = 16, [384] = 17, [21] = 18, [484] = 19, [382] = 20, 616 [439] = 21, [329] = 22, [360] = 23, [67] = 24, [105] = 25, 617 [342] = 26, [457] = 27, [161] = 28, [337] = 29, [135] = 30, 618 [314] = 31, [370] = 32, [404] = 33, [184] = 34, [156] = 35, 619 [139] = 36, [339] = 37, [508] = 38, [267] = 39, [375] = 40, 620 [122] = 41, [297] = 42, [144] = 43, [85] = 44, [466] = 45, 621 [38] = 46, [320] = 47, [273] = 48, [277] = 49, [136] = 50, 622 [454] = 51, [477] = 52, [91] = 53, [227] = 54, [301] = 55, 623 [272] = 56, [319] = 57, [142] = 58, [268] = 59, [65] = 60, 624 [410] = 61, [4] = 62, [373] = 63, [1] = 64, [210] = 65, 625 [224] = 66, [423] = 67, [222] = 68, [386] = 69, [12] = 70, 626 [7] = 71, [391] = 72, [73] = 73, [307] = 74, [27] = 75, 627 [256] = 76, [154] = 77, [204] = 78, [310] = 79, [198] = 80, 628 [162] = 81, [334] = 82, [438] = 83, [69] = 84, [188] = 85, 629 [244] = 86, [190] = 87, [465] = 88, [468] = 89, [417] = 90, 630 [110] = 91, [107] = 92, [368] = 93, [460] = 94, [54] = 95, 631 [492] = 96, [402] = 97, [196] = 98, [383] = 99, 632}; 633 634 635static const uint32_t name_hashes[] = 636{ 637 0x653A915Bu, 0x3513518Du, 0xBEC8E440u, 0x16020A90u, 0x48F5CC19u, 638 0x0B486ED8u, 0x1A7AA369u, 0x6DE855BAu, 0xF2BADABEu, 0xD8CA2594u, 639 0x6B86C0B5u, 0xC62FECD2u, 0x8DA64A26u, 0x01F10233u, 0x8F7E493Eu, 640 0xC7742BE4u, 0xC7742BE4u, 0xC7742BE4u, 0xC7742BE4u, 0xC7742BE4u, 641 0xC7742BE4u, 0xC7742BE4u, 0xF49F1451u, 0xF49F1451u, 0x672BDA53u, 642 0x672BDA53u, 0x672BDA53u, 0x672BDA53u, 0x672BDA53u, 0x1AB214F8u, 643 0x1AB214F8u, 0xF93AD8A9u, 0x1DC691C8u, 0x7C21CFDFu, 0x7C21CFDFu, 644 0x7D3B7A3Bu, 0xC25511F2u, 0xC25511F2u, 0xC25511F2u, 0xC25511F2u, 645 0xC25511F2u, 0xC25511F2u, 0x48011191u, 0x48011191u, 0x085EF7C5u, 646 0x085EF7C5u, 0x085EF7C5u, 0x085EF7C5u, 0x085EF7C5u, 0x085EF7C5u, 647 0x085EF7C5u, 0x085EF7C5u, 0x085EF7C5u, 0x085EF7C5u, 0x085EF7C5u, 648 0xB396750Au, 0x85E74C58u, 0x85E74C58u, 0x85E74C58u, 0x1A04DF3Du, 649 0x1A04DF3Du, 0x28686A4Au, 0x9F8BCEBDu, 0x672BDA53u, 0x672BDA53u, 650 0x672BDA53u, 0x672BDA53u, 0x672BDA53u, 0x672BDA53u, 0x672BDA53u, 651 0x672BDA53u, 0x672BDA53u, 0x98BD32D3u, 0x0A829D4Eu, 0x0A829D4Eu, 652 0x7C21CFDFu, 0x363F796Du, 0x363F796Du, 0x363F796Du, 0xD8A0B17Eu, 653 0xAAF9FD79u, 0x617E4501u, 0x617E4501u, 0x1E6DBE38u, 0x19D88141u, 654 0x3392084Fu, 0x5579EF80u, 0x8F3D7765u, 0x7EDC71B6u, 0xFBA64C54u, 655 0x3ECDA708u, 0xEBA96E92u, 0x82E1B4E1u, 0x5AD275EAu, 0xDD09E931u, 656 0x34C0456Au, 0x5EF889E6u, 0x4B1BB7F1u, 0x4B1BB7F1u, 657}; 658 659 660static const uint32_t nameval_hashes[] = 661{ 662 0xF8614896u, 0xC8C267F6u, 0xF4617F61u, 0x8410A906u, 0xC8D109BBu, 663 0x51D448A4u, 0x52C167CFu, 0xFB22AA54u, 0x4F5272CDu, 0x9D4170E4u, 664 0x4E8C1DC3u, 0x684BDDBCu, 0xE113A2B0u, 0x5010D24Bu, 0xBCA5998Fu, 665 0xC8490E38u, 0x19094780u, 0x25D95A15u, 0x342283E4u, 0x15893F7Eu, 666 0x33968BB7u, 0x4C856F49u, 0x98573F68u, 0x16DDE443u, 0x813C3469u, 667 0x352A6556u, 0xD7988BC9u, 0x65E6ECA1u, 0x7EEE2551u, 0x77EBAE87u, 668 0xBDF5A53Au, 0x7F49F172u, 0xC06A7994u, 0xDB2FBCB8u, 0x343EA49Cu, 669 0xD143768Bu, 0x3E2D8753u, 0xA2EA09FCu, 0x467B5D0Bu, 0xCEB7F977u, 670 0x7119DC7Au, 0xDEFDA129u, 0x3F6EBC90u, 0x14E09A55u, 0x43C8B9D2u, 671 0xA707C426u, 0xFE372940u, 0x77591711u, 0xA6410F15u, 0xEACDE488u, 672 0x8B2C4DC6u, 0x8C2B11DDu, 0x9703CE5Bu, 0x0FAA28E3u, 0x13CCE32Du, 673 0xDCD68310u, 0x416F0B3Fu, 0x3BB4D68Eu, 0xF81F070Cu, 0xBDD89641u, 674 0x3915039Au, 0xF609E604u, 0x1C9DBB75u, 0x7ACD6A01u, 0xD4F462D2u, 675 0x125E66E0u, 0x0AD44FA7u, 0x4C3C90DEu, 0x27AD6982u, 0x0673640Cu, 676 0x65C03607u, 0xB05B7B87u, 0x97E01849u, 0xBA18BD33u, 0xDEF6041Bu, 677 0xE227F500u, 0x8A871E9Au, 0xCB120ACCu, 0x4B1B6336u, 0xEBDA42C6u, 678 0xFF166CA2u, 0x3A5E054Eu, 0x027207B6u, 0x04E3E645u, 0xAA95A0BCu, 679 0x77BFA4F4u, 0x3C95E0BEu, 0xD506A9D1u, 0x443EDFD4u, 0xD4E28BA1u, 680 0xA60BF66Eu, 0x46201E6Bu, 0xB2DE5570u, 0xF19F5DCCu, 0x73B6C636u, 681 0xDC83E7ECu, 0xAA333392u, 0x4EDB46C4u, 0xF64F937Fu, 682}; 683 684 685/* -1 means not found */ 686static int 687find_in_static_full (uint32_t nameval_hash, const char *name, 688 unsigned name_len, const char *val, unsigned val_len) 689{ 690 unsigned id; 691 692 id = nameval2id_plus_one[ (nameval_hash >> XXH_NAMEVAL_SHIFT) 693 & ((1 << XXH_NAMEVAL_WIDTH) - 1) ]; 694 695 if (id == 0) 696 return -1; 697 698 --id; 699 if (static_table[id].name_len == name_len 700 && static_table[id].val_len == val_len 701 && memcmp(static_table[id].name, name, name_len) == 0 702 && memcmp(static_table[id].val, val, val_len) == 0) 703 return id; 704 else 705 return -1; 706} 707 708 709#ifdef NDEBUG 710static 711#endif 712int 713lsqpack_find_in_static_headers (uint32_t name_hash, const char *name, 714 unsigned name_len) 715{ 716 unsigned id; 717 718 id = name2id_plus_one[ (name_hash >> XXH_NAME_SHIFT) 719 & ((1 << XXH_NAME_WIDTH) - 1) ]; 720 721 if (id == 0) 722 return -1; 723 724 --id; 725 if (static_table[id].name_len == name_len 726 && memcmp(static_table[id].name, name, name_len) == 0) 727 return id; 728 else 729 return -1; 730} 731 732 733static unsigned 734lsqpack_val2len (uint64_t value, unsigned prefix_bits) 735{ 736 uint64_t mask = (1ULL << prefix_bits) - 1; 737 return 1 738 + (value >= mask ) 739 + (value >= ((1ULL << 7) + mask)) 740 + (value >= ((1ULL << 14) + mask)) 741 + (value >= ((1ULL << 21) + mask)) 742 + (value >= ((1ULL << 28) + mask)) 743 + (value >= ((1ULL << 35) + mask)) 744 + (value >= ((1ULL << 42) + mask)) 745 + (value >= ((1ULL << 49) + mask)) 746 + (value >= ((1ULL << 56) + mask)) 747 + (value >= ((1ULL << 63) + mask)) 748 ; 749} 750 751 752unsigned char * 753lsqpack_enc_int (unsigned char *dst, unsigned char *const end, uint64_t value, 754 unsigned prefix_bits) 755{ 756 unsigned char *const dst_orig = dst; 757 758 /* This function assumes that at least one byte is available */ 759 assert(dst < end); 760 if (value < ((uint64_t)1 << prefix_bits) - 1) 761 *dst++ |= value; 762 else 763 { 764 *dst++ |= (1 << prefix_bits) - 1; 765 value -= (1 << prefix_bits) - 1; 766 while (value >= 128) 767 { 768 if (dst < end) 769 { 770 *dst++ = 0x80 | (unsigned char) value; 771 value >>= 7; 772 } 773 else 774 return dst_orig; 775 } 776 if (dst < end) 777 *dst++ = (unsigned char) value; 778 else 779 return dst_orig; 780 } 781 return dst; 782} 783 784 785static void 786lsqpack_enc_int_nocheck (unsigned char *dst, uint64_t value, 787 unsigned prefix_bits) 788{ 789 if (value < ((uint64_t)1 << prefix_bits) - 1) 790 *dst++ |= value; 791 else 792 { 793 *dst++ |= (1 << prefix_bits) - 1; 794 value -= (1 << prefix_bits) - 1; 795 while (value >= 128) 796 { 797 *dst++ = 0x80 | (unsigned char) value; 798 value >>= 7; 799 } 800 *dst++ = (unsigned char) value; 801 } 802} 803 804 805int 806lsqpack_enc_enc_str (unsigned prefix_bits, unsigned char *const dst, 807 size_t dst_len, const unsigned char *str, unsigned str_len) 808{ 809 unsigned char *p; 810 unsigned enc_size_bytes, len_size; 811 812 enc_size_bytes = qenc_enc_str_size(str, str_len); 813 814 if (enc_size_bytes < str_len) 815 { 816 len_size = lsqpack_val2len(enc_size_bytes, prefix_bits); 817 if (len_size + enc_size_bytes <= dst_len) 818 { 819 *dst &= ~((1 << (prefix_bits + 1)) - 1); 820 *dst |= 1 << prefix_bits; 821 lsqpack_enc_int_nocheck(dst, enc_size_bytes, prefix_bits); 822 p = qenc_huffman_enc(str, str + str_len, dst + len_size); 823 assert((unsigned) (p - dst) == len_size + enc_size_bytes); 824 return p - dst; 825 } 826 else 827 return -1; 828 } 829 else 830 { 831 len_size = lsqpack_val2len(str_len, prefix_bits); 832 if (len_size + str_len <= dst_len) 833 { 834 *dst &= ~((1 << (prefix_bits + 1)) - 1); 835 lsqpack_enc_int_nocheck(dst, str_len, prefix_bits); 836 memcpy(dst + len_size, str, str_len); 837 return len_size + str_len; 838 } 839 else 840 return -1; 841 } 842} 843 844 845static void 846qenc_drop_oldest_entry (struct lsqpack_enc *enc) 847{ 848 struct lsqpack_enc_table_entry *entry; 849 unsigned buckno; 850 851 entry = STAILQ_FIRST(&enc->qpe_all_entries); 852 assert(entry); 853 E_DEBUG("drop entry %u (`%.*s': `%.*s'), nelem: %u; capacity: %u", 854 entry->ete_id, (int) entry->ete_name_len, ETE_NAME(entry), 855 (int) entry->ete_val_len, ETE_VALUE(entry), enc->qpe_nelem - 1, 856 enc->qpe_cur_bytes_used - ETE_SIZE(entry)); 857 STAILQ_REMOVE_HEAD(&enc->qpe_all_entries, ete_next_all); 858 buckno = BUCKNO(enc->qpe_nbits, entry->ete_nameval_hash); 859 assert(entry == STAILQ_FIRST(&enc->qpe_buckets[buckno].by_nameval)); 860 STAILQ_REMOVE_HEAD(&enc->qpe_buckets[buckno].by_nameval, ete_next_nameval); 861 buckno = BUCKNO(enc->qpe_nbits, entry->ete_name_hash); 862 assert(entry == STAILQ_FIRST(&enc->qpe_buckets[buckno].by_name)); 863 STAILQ_REMOVE_HEAD(&enc->qpe_buckets[buckno].by_name, ete_next_name); 864 865 enc->qpe_dropped += ETE_SIZE(entry); 866 enc->qpe_cur_bytes_used -= ETE_SIZE(entry); 867 --enc->qpe_nelem; 868 free(entry); 869} 870 871 872static float 873qenc_effective_fill (const struct lsqpack_enc *enc) 874{ 875 struct lsqpack_enc_table_entry *entry, *dup; 876 unsigned dups_size = 0; 877 878 assert(enc->qpe_cur_max_capacity); 879 880 STAILQ_FOREACH(entry, &enc->qpe_all_entries, ete_next_all) 881 for (dup = STAILQ_NEXT(entry, ete_next_all); dup; 882 dup = STAILQ_NEXT(dup, ete_next_all)) 883 if (dup->ete_name_len == entry->ete_name_len && 884 dup->ete_val_len == entry->ete_val_len && 885 0 == memcmp(ETE_NAME(dup), ETE_NAME(entry), 886 dup->ete_name_len + dup->ete_val_len)) 887 { 888 dups_size += ETE_SIZE(dup); 889 break; 890 } 891 892 return (float) (enc->qpe_cur_bytes_used - dups_size) 893 / (float) enc->qpe_cur_max_capacity; 894} 895 896 897static void 898update_ema (float *val, unsigned new) 899{ 900 if (*val) 901 *val = (new - *val) * 0.4 + *val; 902 else 903 *val = new; 904} 905 906 907static void 908qenc_sample_table_size (struct lsqpack_enc *enc) 909{ 910 update_ema(&enc->qpe_table_nelem_ema, enc->qpe_nelem); 911 E_DEBUG("table size actual: %u; exponential moving average: %.3f", 912 enc->qpe_nelem, enc->qpe_table_nelem_ema); 913} 914 915 916static void 917qenc_sample_header_count (struct lsqpack_enc *enc) 918{ 919 update_ema(&enc->qpe_header_count_ema, 920 enc->qpe_cur_header.n_hdr_added_to_hist); 921 E_DEBUG("header count actual: %u; exponential moving average: %.3f", 922 enc->qpe_cur_header.n_hdr_added_to_hist, enc->qpe_header_count_ema); 923} 924 925 926static void 927qenc_remove_overflow_entries (struct lsqpack_enc *enc) 928{ 929 int dropped; 930 931 dropped = 0; 932 while (enc->qpe_cur_bytes_used > enc->qpe_cur_max_capacity) 933 { 934 qenc_drop_oldest_entry(enc); 935 ++dropped; 936 } 937 938 if (enc->qpe_logger_ctx && enc->qpe_cur_max_capacity) 939 { 940 if (enc->qpe_flags & LSQPACK_ENC_USE_DUP) 941 E_DEBUG("fill: %.2f; effective fill: %.2f", 942 (float) enc->qpe_cur_bytes_used / (float) enc->qpe_cur_max_capacity, 943 qenc_effective_fill(enc)); 944 else 945 E_DEBUG("fill: %.2f", 946 (float) enc->qpe_cur_bytes_used / (float) enc->qpe_cur_max_capacity); 947 } 948 949 /* It's important to sample only when entries have been dropped: that 950 * indicates that the table is being cycled through. 951 */ 952 if (dropped && enc->qpe_hist_els) 953 qenc_sample_table_size(enc); 954} 955 956 957static int 958qenc_grow_tables (struct lsqpack_enc *enc) 959{ 960 struct lsqpack_double_enc_head *new_buckets, *new[2]; 961 struct lsqpack_enc_table_entry *entry; 962 unsigned n, old_nbits; 963 int idx; 964 965 old_nbits = enc->qpe_nbits; 966 new_buckets = malloc(sizeof(enc->qpe_buckets[0]) 967 * N_BUCKETS(old_nbits + 1)); 968 if (!new_buckets) 969 return -1; 970 971 for (n = 0; n < N_BUCKETS(old_nbits); ++n) 972 { 973 new[0] = &new_buckets[n]; 974 new[1] = &new_buckets[n + N_BUCKETS(old_nbits)]; 975 STAILQ_INIT(&new[0]->by_name); 976 STAILQ_INIT(&new[1]->by_name); 977 STAILQ_INIT(&new[0]->by_nameval); 978 STAILQ_INIT(&new[1]->by_nameval); 979 while (entry = STAILQ_FIRST(&enc->qpe_buckets[n].by_name), entry != NULL) 980 { 981 STAILQ_REMOVE_HEAD(&enc->qpe_buckets[n].by_name, ete_next_name); 982 idx = (BUCKNO(old_nbits + 1, entry->ete_name_hash) 983 >> old_nbits) & 1; 984 STAILQ_INSERT_TAIL(&new[idx]->by_name, entry, ete_next_name); 985 } 986 while (entry = STAILQ_FIRST(&enc->qpe_buckets[n].by_nameval), entry != NULL) 987 { 988 STAILQ_REMOVE_HEAD(&enc->qpe_buckets[n].by_nameval, 989 ete_next_nameval); 990 idx = (BUCKNO(old_nbits + 1, entry->ete_nameval_hash) 991 >> old_nbits) & 1; 992 STAILQ_INSERT_TAIL(&new[idx]->by_nameval, entry, 993 ete_next_nameval); 994 } 995 } 996 997 free(enc->qpe_buckets); 998 enc->qpe_nbits = old_nbits + 1; 999 enc->qpe_buckets = new_buckets; 1000 return 0; 1001} 1002 1003 1004static struct lsqpack_enc_table_entry * 1005lsqpack_enc_push_entry (struct lsqpack_enc *enc, uint32_t name_hash, 1006 uint32_t nameval_hash, const char *name, unsigned name_len, 1007 const char *value, unsigned value_len) 1008{ 1009 struct lsqpack_enc_table_entry *entry; 1010 unsigned buckno; 1011 size_t size; 1012 1013 if (enc->qpe_nelem >= N_BUCKETS(enc->qpe_nbits) / 2 && 1014 0 != qenc_grow_tables(enc)) 1015 return NULL; 1016 1017 size = sizeof(*entry) + name_len + value_len; 1018 entry = malloc(size); 1019 if (!entry) 1020 return NULL; 1021 1022 entry->ete_name_hash = name_hash; 1023 entry->ete_nameval_hash = nameval_hash; 1024 entry->ete_name_len = name_len; 1025 entry->ete_val_len = value_len; 1026 entry->ete_when_added_used = enc->qpe_cur_bytes_used; 1027 entry->ete_when_added_dropped = enc->qpe_dropped; 1028 entry->ete_id = 1 + enc->qpe_ins_count++; 1029 memcpy(ETE_NAME(entry), name, name_len); 1030 memcpy(ETE_VALUE(entry), value, value_len); 1031 1032 STAILQ_INSERT_TAIL(&enc->qpe_all_entries, entry, ete_next_all); 1033 buckno = BUCKNO(enc->qpe_nbits, nameval_hash); 1034 STAILQ_INSERT_TAIL(&enc->qpe_buckets[buckno].by_nameval, entry, 1035 ete_next_nameval); 1036 buckno = BUCKNO(enc->qpe_nbits, name_hash); 1037 STAILQ_INSERT_TAIL(&enc->qpe_buckets[buckno].by_name, entry, 1038 ete_next_name); 1039 1040 enc->qpe_cur_bytes_used += ENTRY_COST(name_len, value_len); 1041 ++enc->qpe_nelem; 1042 E_DEBUG("pushed entry %u (`%.*s': `%.*s'), nelem: %u; capacity: %u", 1043 entry->ete_id, (int) entry->ete_name_len, ETE_NAME(entry), 1044 (int) entry->ete_val_len, ETE_VALUE(entry), enc->qpe_nelem, 1045 enc->qpe_cur_bytes_used); 1046 return entry; 1047} 1048 1049 1050int 1051lsqpack_enc_start_header (struct lsqpack_enc *enc, uint64_t stream_id, 1052 unsigned seqno) 1053{ 1054 struct lsqpack_header_info *hinfo; 1055 1056 if (enc->qpe_flags & LSQPACK_ENC_HEADER) 1057 return -1; 1058 1059 E_DEBUG("Start header for stream %"PRIu64, stream_id); 1060 1061 enc->qpe_cur_header.hinfo = enc_alloc_hinfo(enc); 1062 if (enc->qpe_cur_header.hinfo) 1063 { 1064 enc->qpe_cur_header.hinfo->qhi_stream_id = stream_id; 1065 enc->qpe_cur_header.hinfo->qhi_seqno = seqno; 1066 } 1067 else 1068 E_INFO("could not allocate hinfo for stream %"PRIu64, stream_id); 1069 enc->qpe_cur_header.flags = 0; 1070 enc->qpe_cur_header.other_at_risk = NULL; 1071 enc->qpe_cur_header.n_hdr_added_to_hist = 0; 1072 enc->qpe_cur_header.base_idx = enc->qpe_ins_count; 1073 1074 /* Check if there are other header blocks with the same stream ID that 1075 * are at risk. 1076 */ 1077 if (seqno && enc->qpe_cur_header.hinfo) 1078 TAILQ_FOREACH(hinfo, &enc->qpe_risked_hinfos, qhi_next_risked) 1079 if (hinfo->qhi_stream_id == stream_id) 1080 { 1081 enc->qpe_cur_header.other_at_risk = hinfo; 1082 break; 1083 } 1084 1085 enc->qpe_flags |= LSQPACK_ENC_HEADER; 1086 1087 return 0; 1088} 1089 1090 1091/* 1092 * Each header block is prefixed with two integers. The Required Insert 1093 * Count is encoded as an integer with an 8-bit prefix. The Base is encoded 1094 * as sign- and-modulus integer, using a single sign bit and a value with a 1095 * 7-bit prefix. 1096 * 1097 * 0 1 2 3 4 5 6 7 1098 * +---+---+---+---+---+---+---+---+ 1099 * | Required Insert Count (8+) | 1100 * +---+---------------------------+ 1101 * | S | Delta Base (7+) | 1102 * +---+---------------------------+ 1103 * | Compressed Headers ... 1104 * +-------------------------------+ 1105 */ 1106size_t 1107lsqpack_enc_header_block_prefix_size (const struct lsqpack_enc *enc) 1108{ 1109 unsigned req_ins_count_len, delta_base_len; 1110 1111 req_ins_count_len = lsqpack_val2len(2 * enc->qpe_max_entries, 8); 1112 delta_base_len = lsqpack_val2len(2 * enc->qpe_max_entries, 7); 1113 return req_ins_count_len + delta_base_len; 1114} 1115 1116 1117int 1118lsqpack_enc_cancel_header (struct lsqpack_enc *enc) 1119{ 1120 /* No header has been started. */ 1121 if (!(enc->qpe_flags & LSQPACK_ENC_HEADER)) 1122 return -1; 1123 1124 /* Cancellation is not (yet) allowed if the dynamic table is used since 1125 * ls-qpack's state is changed when the dynamic table is used. 1126 */ 1127 if (enc->qpe_cur_header.hinfo && HINFO_IDS_SET(enc->qpe_cur_header.hinfo)) 1128 return -1; 1129 1130 if (enc->qpe_cur_header.hinfo) { 1131 enc_free_hinfo(enc, enc->qpe_cur_header.hinfo); 1132 enc->qpe_cur_header.hinfo = NULL; 1133 } 1134 1135 enc->qpe_flags &= ~LSQPACK_ENC_HEADER; 1136 1137 return 0; 1138} 1139 1140 1141static void 1142qenc_add_to_risked_list (struct lsqpack_enc *enc, 1143 struct lsqpack_header_info *hinfo) 1144{ 1145 TAILQ_INSERT_TAIL(&enc->qpe_risked_hinfos, hinfo, qhi_next_risked); 1146 if (enc->qpe_cur_header.other_at_risk) 1147 { 1148 hinfo->qhi_same_stream_id 1149 = enc->qpe_cur_header.other_at_risk->qhi_same_stream_id; 1150 enc->qpe_cur_header.other_at_risk->qhi_same_stream_id = hinfo; 1151 } 1152 else 1153 { 1154 ++enc->qpe_cur_streams_at_risk; 1155 E_DEBUG("streams at risk: %u", enc->qpe_cur_streams_at_risk); 1156 assert(enc->qpe_cur_streams_at_risk <= enc->qpe_max_risked_streams); 1157 } 1158} 1159 1160 1161static void 1162qenc_remove_from_risked_list (struct lsqpack_enc *enc, 1163 struct lsqpack_header_info *hinfo) 1164{ 1165 struct lsqpack_header_info *prev; 1166 TAILQ_REMOVE(&enc->qpe_risked_hinfos, hinfo, qhi_next_risked); 1167 if (hinfo->qhi_same_stream_id == hinfo) 1168 { 1169 assert(enc->qpe_cur_streams_at_risk > 0); 1170 --enc->qpe_cur_streams_at_risk; 1171 E_DEBUG("streams at risk: %u", enc->qpe_cur_streams_at_risk); 1172 } 1173 else 1174 { 1175 for (prev = hinfo->qhi_same_stream_id; 1176 prev->qhi_same_stream_id != hinfo; prev = prev->qhi_same_stream_id) 1177 ; 1178 prev->qhi_same_stream_id = hinfo->qhi_same_stream_id; 1179 hinfo->qhi_same_stream_id = hinfo; 1180 } 1181} 1182 1183 1184static int 1185qenc_hinfo_at_risk (const struct lsqpack_enc *enc, 1186 const struct lsqpack_header_info *hinfo) 1187{ 1188 return hinfo->qhi_max_id > enc->qpe_max_acked_id; 1189} 1190 1191 1192ssize_t 1193lsqpack_enc_end_header (struct lsqpack_enc *enc, unsigned char *buf, size_t sz, 1194 enum lsqpack_enc_header_flags *header_flags) 1195{ 1196 struct lsqpack_header_info *hinfo; 1197 unsigned char *dst, *end; 1198 lsqpack_abs_id_t diff, encoded_largest_ref; 1199 unsigned sign, nelem; 1200 float count_diff; 1201 1202 if (sz == 0) 1203 return -1; 1204 1205 if (!(enc->qpe_flags & LSQPACK_ENC_HEADER)) 1206 return -1; 1207 1208 if (enc->qpe_hist_els) 1209 { 1210 qenc_sample_header_count(enc); 1211 if (enc->qpe_table_nelem_ema 1212 /* History size should not be smaller than the average number of 1213 * header fields in a header list. 1214 */ 1215 && enc->qpe_table_nelem_ema > enc->qpe_header_count_ema) 1216 { 1217 count_diff = fabsf(enc->qpe_hist_nels - enc->qpe_table_nelem_ema); 1218 /* If difference is 2 or 10%: */ 1219 if (count_diff >= 1.5 1220 || count_diff / enc->qpe_table_nelem_ema >= 0.1) 1221 { 1222 nelem = (unsigned) round(enc->qpe_table_nelem_ema); 1223 qenc_hist_update_size(enc, nelem); 1224 } 1225 } 1226 } 1227 1228 if (enc->qpe_cur_header.hinfo && HINFO_IDS_SET(enc->qpe_cur_header.hinfo)) 1229 { 1230 hinfo = enc->qpe_cur_header.hinfo; /* shorthand */ 1231 end = buf + sz; 1232 1233 *buf = 0; 1234 encoded_largest_ref = hinfo->qhi_max_id 1235 % (2 * enc->qpe_max_entries) + 1; 1236 E_DEBUG("LargestRef for stream %"PRIu64" is encoded as %u", 1237 hinfo->qhi_stream_id, encoded_largest_ref); 1238 dst = lsqpack_enc_int(buf, end, encoded_largest_ref, 8); 1239 if (dst <= buf) 1240 return 0; 1241 1242 if (dst >= end) 1243 return 0; 1244 1245 buf = dst; 1246 if (enc->qpe_cur_header.base_idx >= hinfo->qhi_max_id) 1247 { 1248 sign = 0; 1249 diff = enc->qpe_cur_header.base_idx - hinfo->qhi_max_id; 1250 } 1251 else 1252 { 1253 sign = 1; 1254 diff = hinfo->qhi_max_id - enc->qpe_cur_header.base_idx - 1; 1255 } 1256 *buf = (unsigned char) (sign << 7); 1257 dst = lsqpack_enc_int(buf, end, diff, 7); 1258 if (dst <= buf) 1259 return 0; 1260 1261 if (qenc_hinfo_at_risk(enc, hinfo)) 1262 qenc_add_to_risked_list(enc, hinfo); 1263 1264 E_DEBUG("ended header for stream %"PRIu64"; max ref: %u encoded as %u; " 1265 "risked: %d", hinfo->qhi_stream_id, hinfo->qhi_max_id, 1266 encoded_largest_ref, qenc_hinfo_at_risk(enc, hinfo)); 1267 1268 enc->qpe_cur_header.hinfo = NULL; 1269 enc->qpe_flags &= ~LSQPACK_ENC_HEADER; 1270 if (header_flags) 1271 { 1272 *header_flags = enc->qpe_cur_header.flags; 1273 if (qenc_hinfo_at_risk(enc, hinfo)) 1274 *header_flags |= LSQECH_REF_AT_RISK; 1275 } 1276 enc->qpe_bytes_out += dst - end + sz; 1277 return dst - end + sz; 1278 } 1279 1280 if (sz >= 2) 1281 { 1282 memset(buf, 0, 2); 1283 if (enc->qpe_cur_header.hinfo) 1284 { 1285 E_DEBUG("ended header for stream %"PRIu64"; dynamic table not " 1286 "referenced", enc->qpe_cur_header.hinfo->qhi_stream_id); 1287 enc_free_hinfo(enc, enc->qpe_cur_header.hinfo); 1288 enc->qpe_cur_header.hinfo = NULL; 1289 } 1290 else 1291 E_DEBUG("ended header; hinfo absent"); 1292 enc->qpe_flags &= ~LSQPACK_ENC_HEADER; 1293 if (header_flags) 1294 *header_flags = enc->qpe_cur_header.flags; 1295 enc->qpe_bytes_out += 2; 1296 return 2; 1297 } 1298 else 1299 return 0; 1300} 1301 1302 1303struct encode_program 1304{ 1305 enum enc_stream_action { /* What to do on encoder stream */ 1306 EEA_NONE, 1307 EEA_DUP, 1308 EEA_INS_NAMEREF_STATIC, 1309 EEA_INS_NAMEREF_DYNAMIC, 1310 EEA_INS_LIT, 1311 EEA_INS_LIT_NAME, 1312 } ep_enc_action; 1313 enum hea_block_action { /* What to output to header block */ 1314 EHA_INDEXED_NEW, 1315 EHA_INDEXED_STAT, 1316 EHA_INDEXED_DYN, 1317 EHA_LIT_WITH_NAME_STAT, 1318 EHA_LIT_WITH_NAME_DYN, 1319 EHA_LIT_WITH_NAME_NEW, 1320 EHA_LIT, 1321 } ep_hea_action; 1322 enum dyn_table_action { /* Any changes to the dynamic table */ 1323 ETA_NOOP, 1324 ETA_NEW, 1325 ETA_NEW_NAME, 1326 } ep_tab_action; 1327 enum ref_flags { /* Which entries to take references to */ 1328 EPF_REF_FOUND = 1 << 1, 1329 EPF_REF_NEW = 1 << 2, 1330 } ep_flags; 1331}; 1332 1333 1334static const char *const eea2str[] = 1335{ 1336 [EEA_NONE] = "EEA_NONE", 1337 [EEA_DUP] = "EEA_DUP", 1338 [EEA_INS_NAMEREF_STATIC] = "EEA_INS_NAMEREF_STATIC", 1339 [EEA_INS_NAMEREF_DYNAMIC] = "EEA_INS_NAMEREF_DYNAMIC", 1340 [EEA_INS_LIT] = "EEA_INS_LIT", 1341 [EEA_INS_LIT_NAME] = "EEA_INS_LIT_NAME", 1342}; 1343 1344 1345static const char *const eha2str[] = 1346{ 1347 [EHA_INDEXED_NEW] = "EHA_INDEXED_NEW", 1348 [EHA_INDEXED_STAT] = "EHA_INDEXED_STAT", 1349 [EHA_INDEXED_DYN] = "EHA_INDEXED_DYN", 1350 [EHA_LIT_WITH_NAME_STAT] = "EHA_LIT_WITH_NAME_STAT", 1351 [EHA_LIT_WITH_NAME_DYN] = "EHA_LIT_WITH_NAME_DYN", 1352 [EHA_LIT_WITH_NAME_NEW] = "EHA_LIT_WITH_NAME_NEW", 1353 [EHA_LIT] = "EHA_LIT", 1354}; 1355 1356 1357static const char *const eta2str[] = 1358{ 1359 [ETA_NOOP] = "ETA_NOOP", 1360 [ETA_NEW] = "ETA_NEW", 1361 [ETA_NEW_NAME] = "ETA_NEW_NAME", 1362}; 1363 1364 1365static lsqpack_abs_id_t 1366qenc_min_reffed_id (struct lsqpack_enc *enc) 1367{ 1368 const struct lsqpack_header_info *hinfo; 1369 lsqpack_abs_id_t min_id; 1370 1371 if (enc->qpe_cur_header.flags & LSQECH_MINREF_CACHED) 1372 min_id = enc->qpe_cur_header.min_reffed; 1373 else 1374 { 1375 min_id = 0; 1376 TAILQ_FOREACH(hinfo, &enc->qpe_all_hinfos, qhi_next_all) 1377 if (min_id == 0 || 1378 (hinfo->qhi_min_id != 0 && hinfo->qhi_min_id < min_id)) 1379 { 1380 min_id = hinfo->qhi_min_id; 1381 } 1382 enc->qpe_cur_header.min_reffed = min_id; 1383 enc->qpe_cur_header.flags |= LSQECH_MINREF_CACHED; 1384 } 1385 1386 if (enc->qpe_cur_header.hinfo 1387 && (min_id == 0 || (enc->qpe_cur_header.hinfo->qhi_min_id != 0 1388 && enc->qpe_cur_header.hinfo->qhi_min_id < min_id))) 1389 min_id = enc->qpe_cur_header.hinfo->qhi_min_id; 1390 1391 return min_id; 1392} 1393 1394 1395static int 1396qenc_safe_to_dup (const struct lsqpack_enc *enc, 1397 const struct lsqpack_enc_table_entry *const pinned_entry) 1398{ 1399 const struct lsqpack_enc_table_entry *entry; 1400 unsigned bytes_used; 1401 1402 bytes_used = enc->qpe_cur_bytes_used + ETE_SIZE(pinned_entry); 1403 if (bytes_used <= enc->qpe_cur_max_capacity) 1404 return 1; 1405 1406 for (entry = STAILQ_FIRST(&enc->qpe_all_entries); entry != pinned_entry; 1407 entry = STAILQ_NEXT(entry, ete_next_all)) 1408 { 1409 bytes_used -= ETE_SIZE(entry); 1410 if (bytes_used <= enc->qpe_cur_max_capacity) 1411 return 1; 1412 } 1413 1414 return 0; 1415} 1416 1417 1418static int 1419qenc_has_or_can_evict_at_least (struct lsqpack_enc *enc, size_t new_entry_size) 1420{ 1421 const struct lsqpack_enc_table_entry *entry; 1422 lsqpack_abs_id_t min_id; 1423 size_t avail; 1424 1425 avail = enc->qpe_cur_max_capacity - enc->qpe_cur_bytes_used; 1426 if (avail >= new_entry_size) 1427 return 1; 1428 1429 min_id = qenc_min_reffed_id(enc); 1430 1431 STAILQ_FOREACH(entry, &enc->qpe_all_entries, ete_next_all) 1432 if ((min_id == 0 || entry->ete_id < min_id) 1433 && entry->ete_id <= enc->qpe_max_acked_id) 1434 { 1435 avail += ETE_SIZE(entry); 1436 if (avail >= new_entry_size) 1437 return 1; 1438 } 1439 else 1440 break; 1441 1442 return avail >= new_entry_size; 1443} 1444 1445 1446static int 1447qenc_duplicable_entry (struct lsqpack_enc *enc, 1448 const struct lsqpack_enc_table_entry *const entry) 1449{ 1450 float fill, fraction; 1451 unsigned off; 1452 1453 if (!(enc->qpe_flags & LSQPACK_ENC_USE_DUP)) 1454 return 0; 1455 1456 fill = (float) (enc->qpe_cur_bytes_used + ETE_SIZE(entry)) 1457 / (float) enc->qpe_cur_max_capacity; 1458 if (fill < 0.8) 1459 return 0; 1460 1461 off = entry->ete_when_added_used 1462 - (enc->qpe_dropped - entry->ete_when_added_dropped); 1463 fraction = (float) off / (float) enc->qpe_cur_max_capacity; 1464 return fraction < 0.2f 1465 && qenc_has_or_can_evict_at_least(enc, ETE_SIZE(entry)); 1466} 1467 1468 1469static void 1470qenc_maybe_update_hinfo_min_max (struct lsqpack_header_info *hinfo, 1471 lsqpack_abs_id_t dyn_id) 1472{ 1473 if (HINFO_IDS_SET(hinfo)) 1474 { 1475 if (dyn_id > hinfo->qhi_max_id) 1476 hinfo->qhi_max_id = dyn_id; 1477 else if (dyn_id < hinfo->qhi_min_id) 1478 hinfo->qhi_min_id = dyn_id; 1479 } 1480 else 1481 { 1482 hinfo->qhi_max_id = dyn_id; 1483 hinfo->qhi_min_id = dyn_id; 1484 } 1485} 1486 1487 1488static int 1489qenc_entry_is_draining (const struct lsqpack_enc *enc, 1490 const struct lsqpack_enc_table_entry *entry) 1491{ 1492 unsigned dist; 1493 1494 dist = entry->ete_when_added_used 1495 - (enc->qpe_dropped - entry->ete_when_added_dropped); 1496 dist += enc->qpe_cur_max_capacity - enc->qpe_cur_bytes_used; 1497 return dist < enc->qpe_cur_max_capacity / 4; 1498} 1499 1500 1501static int 1502qenc_can_risk (const struct lsqpack_enc *enc) 1503{ 1504 return enc->qpe_cur_header.other_at_risk 1505 || enc->qpe_cur_streams_at_risk < enc->qpe_max_risked_streams 1506 || (enc->qpe_cur_header.hinfo 1507 && qenc_hinfo_at_risk(enc, enc->qpe_cur_header.hinfo)) 1508 ; 1509} 1510 1511 1512/* Returns number of bytes written to enc_buf if an entry was duplicated, 0 if 1513 * it wasn't. 1514 */ 1515static unsigned 1516qenc_dup_draining (struct lsqpack_enc *enc, unsigned char *enc_buf, 1517 size_t enc_buf_sz) 1518{ 1519 struct lsqpack_enc_table_entry *entry, *candidate, *next; 1520 unsigned char *dst; 1521 1522 if (enc_buf_sz == 0 1523 || !(enc->qpe_flags & LSQPACK_ENC_USE_DUP) 1524 || enc->qpe_ins_count == LSQPACK_MAX_ABS_ID) 1525 return 0; 1526 if ((enc->qpe_table_nelem_ema || qenc_can_risk(enc)) 1527 && enc->qpe_table_nelem_ema < enc->qpe_header_count_ema) 1528 return 0; 1529 1530 candidate = NULL; 1531 STAILQ_FOREACH(entry, &enc->qpe_all_entries, ete_next_all) 1532 { 1533 if (!qenc_entry_is_draining(enc, entry)) 1534 break; 1535 /* 1536 if (ETE_SIZE(entry) > enc->qpe_cur_max_capacity / 4) 1537 continue; 1538 if (ETE_SIZE(entry) < DYNAMIC_ENTRY_OVERHEAD + 20) 1539 continue; 1540 */ 1541 if (candidate && ETE_SIZE(entry) < ETE_SIZE(candidate)) 1542 continue; 1543 for (next = STAILQ_NEXT(entry, ete_next_nameval); next; 1544 next = STAILQ_NEXT(next, ete_next_nameval)) 1545 if (next->ete_nameval_hash == entry->ete_nameval_hash 1546 && next->ete_name_len == entry->ete_name_len 1547 && next->ete_val_len == entry->ete_val_len 1548 && 0 == memcmp(ETE_NAME(next), ETE_NAME(entry), 1549 next->ete_name_len) 1550 && 0 == memcmp(ETE_VALUE(next), ETE_VALUE(entry), 1551 next->ete_val_len)) 1552 break; 1553 if (!next 1554 && qenc_hist_seen(enc, HE_NAMEVAL, entry->ete_nameval_hash) 1555 && qenc_has_or_can_evict_at_least(enc, ETE_SIZE(entry))) 1556 candidate = entry; 1557 } 1558 1559 if (!candidate) 1560 return 0; 1561 1562 E_DEBUG("dup draining"); 1563 1564 *enc_buf = 0; 1565 dst = lsqpack_enc_int(enc_buf, enc_buf + enc_buf_sz, 1566 enc->qpe_ins_count - candidate->ete_id, 5); 1567 if (dst <= enc_buf) 1568 return 0; 1569 1570 entry = lsqpack_enc_push_entry(enc, candidate->ete_name_hash, 1571 candidate->ete_nameval_hash, ETE_NAME(candidate), 1572 candidate->ete_name_len, ETE_VALUE(candidate), 1573 candidate->ete_val_len); 1574 if (!entry) 1575 return 0; 1576 1577 return (unsigned) (dst - enc_buf); 1578} 1579 1580 1581/* Clang does not produce incorrect "may be used uninitialized" warnings 1582 * in the function below, but gcc 5.4.0 does. 1583 */ 1584#ifdef __clang__ 1585#define USE_USELESS_INITIALIZATION 0 1586#else 1587#define USE_USELESS_INITIALIZATION 1 1588#endif 1589 1590 1591enum lsqpack_enc_status 1592lsqpack_enc_encode (struct lsqpack_enc *enc, 1593 unsigned char *enc_buf, size_t *enc_sz_p, 1594 unsigned char *hea_buf, size_t *hea_sz_p, 1595 const struct lsxpack_header *xhdr, 1596 enum lsqpack_enc_flags flags) 1597{ 1598 unsigned char *const enc_buf_end = enc_buf + *enc_sz_p; 1599 unsigned char *const hea_buf_end = hea_buf + *hea_sz_p; 1600 struct lsqpack_enc_table_entry *entry, *new_entry; 1601 struct lsqpack_enc_table_entry *candidates[2]; 1602 struct encode_program prog; 1603 int index, risk, use_dyn_table, static_id, enough_room, seen_nameval; 1604 int update_hist; 1605 unsigned name_hash, nameval_hash, buckno; 1606 1607 size_t enc_sz, hea_sz, sz; 1608 unsigned char *dst; 1609 lsqpack_abs_id_t id; 1610 unsigned n_cand; 1611 int r; 1612 1613 const char *const name = lsxpack_header_get_name(xhdr); 1614 const char *const value = lsxpack_header_get_value(xhdr); 1615 const unsigned name_len = xhdr->name_len; 1616 const unsigned value_len = xhdr->val_len; 1617 1618 E_DEBUG("encode `%.*s': `%.*s'", (int) name_len, name, 1619 (int) value_len, value); 1620 1621 /* Encoding always outputs at least a byte to the header block. If 1622 * no bytes are available, encoding cannot proceed. 1623 */ 1624 if (hea_buf == hea_buf_end) 1625 return LQES_NOBUF_HEAD; 1626 1627 if (xhdr->flags & LSXPACK_NEVER_INDEX) 1628 flags |= LQEF_NEVER_INDEX; 1629 1630 /* Look for a full match in the static table */ 1631 if ((xhdr->flags & (LSXPACK_QPACK_IDX|LSXPACK_VAL_MATCHED)) 1632 != (LSXPACK_QPACK_IDX|LSXPACK_VAL_MATCHED)) 1633 { 1634 /* Hash calculation is delayed until we really have to do it */ 1635 if (xhdr->flags & LSXPACK_NAME_HASH) 1636 name_hash = xhdr->name_hash; 1637 else if (xhdr->flags & LSXPACK_QPACK_IDX) 1638 name_hash = name_hashes[ xhdr->qpack_index ]; 1639 else 1640 name_hash = XXH32(name, name_len, LSQPACK_XXH_SEED); 1641 if (xhdr->flags & LSXPACK_NAMEVAL_HASH) 1642 nameval_hash = xhdr->nameval_hash; 1643 else 1644 nameval_hash = XXH32(value, value_len, name_hash); 1645 E_DEBUG("name hash: 0x%X; nameval hash: 0x%X", name_hash, nameval_hash); 1646 static_id = find_in_static_full(nameval_hash, name, name_len, value, 1647 value_len); 1648 } 1649 else 1650 { 1651 static_id = xhdr->qpack_index; 1652 goto static_nameval_match; 1653 } 1654 if (static_id >= 0) 1655 { 1656 static_nameval_match: 1657 id = static_id; 1658 prog = (struct encode_program) { 1659 .ep_enc_action = EEA_NONE, 1660 .ep_hea_action = EHA_INDEXED_STAT, 1661 .ep_tab_action = ETA_NOOP, 1662 .ep_flags = 0, 1663 }; 1664 update_hist = 0; 1665#if USE_USELESS_INITIALIZATION 1666 nameval_hash = 0; 1667 name_hash = 0; 1668 use_dyn_table = 0; 1669 risk = 0; 1670 entry = NULL; 1671 index = 0; 1672#endif 1673 goto execute_program; 1674 } 1675#if USE_USELESS_INITIALIZATION 1676 else 1677 id = 0; 1678#endif 1679 1680 use_dyn_table = !(flags & LQEF_NO_DYN) 1681 && enc_use_dynamic_table(enc) 1682 ; 1683 1684 index = !(flags & (LQEF_NO_INDEX|LQEF_NEVER_INDEX|LQEF_NO_DYN)) 1685 && use_dyn_table 1686 && enc->qpe_ins_count < LSQPACK_MAX_ABS_ID 1687 ; 1688 1689 risk = qenc_can_risk(enc); 1690 1691 /* Add header to history if it exists. Defer updating history until we 1692 * know the function will return success. 1693 */ 1694 update_hist = enc->qpe_hist_els != NULL && !(flags & LQEF_NO_HIST_UPD); 1695 1696 restart: 1697 /* Look for a full match in the dynamic table */ 1698 if (use_dyn_table) 1699 { 1700 buckno = BUCKNO(enc->qpe_nbits, nameval_hash); 1701 n_cand = 0; 1702 STAILQ_FOREACH(entry, &enc->qpe_buckets[buckno].by_nameval, 1703 ete_next_nameval) 1704 if (nameval_hash == entry->ete_nameval_hash && 1705 name_len == entry->ete_name_len && 1706 value_len == entry->ete_val_len && 1707 0 == memcmp(name, ETE_NAME(entry), name_len) && 1708 0 == memcmp(value, ETE_VALUE(entry), value_len)) 1709 { 1710 candidates[ n_cand++ ] = entry; 1711 if (n_cand >= sizeof(candidates) / sizeof(candidates[0])) 1712 break; 1713 } 1714 1715 switch (n_cand) 1716 { 1717 case 1: 1718 entry = candidates[0]; 1719 id = entry->ete_id; 1720 if ((risk || entry->ete_id <= enc->qpe_max_acked_id) && index && qenc_duplicable_entry(enc, entry)) 1721 { 1722 if (risk) 1723 prog = (struct encode_program) { 1724 .ep_enc_action = EEA_DUP, 1725 .ep_hea_action = EHA_INDEXED_NEW, 1726 .ep_tab_action = ETA_NEW, 1727 .ep_flags = EPF_REF_FOUND | EPF_REF_NEW, 1728 }; 1729 else if (!qenc_entry_is_draining(enc, entry)) 1730 { 1731 if (qenc_safe_to_dup(enc, entry)) 1732 prog = (struct encode_program) { 1733 .ep_enc_action = EEA_DUP, 1734 .ep_hea_action = EHA_INDEXED_DYN, 1735 .ep_tab_action = ETA_NEW, 1736 .ep_flags = EPF_REF_FOUND, 1737 }; 1738 else 1739 prog = (struct encode_program) { 1740 .ep_enc_action = EEA_NONE, 1741 .ep_hea_action = EHA_INDEXED_DYN, 1742 .ep_tab_action = ETA_NOOP, 1743 .ep_flags = EPF_REF_FOUND, 1744 }; 1745 } 1746 else 1747 break; 1748 } 1749 else if ((risk || entry->ete_id <= enc->qpe_max_acked_id) 1750 && !qenc_entry_is_draining(enc, entry)) 1751 prog = (struct encode_program) { 1752 .ep_enc_action = EEA_NONE, 1753 .ep_hea_action = EHA_INDEXED_DYN, 1754 .ep_tab_action = ETA_NOOP, 1755 .ep_flags = EPF_REF_FOUND, 1756 }; 1757 else 1758 break; 1759 goto execute_program; 1760 case 2: 1761 /* The order holds due to the way hash table is structured: */ 1762 assert(candidates[1]->ete_id > candidates[0]->ete_id); 1763 if (risk) 1764 /* TODO: make this smarter? Perhaps it may be preferable 1765 * to use an acknowledged entry if it is not in the "about 1766 * to be evicted" range? 1767 */ 1768 entry = candidates[1]; 1769 else if (candidates[1]->ete_id <= enc->qpe_max_acked_id) 1770 entry = candidates[1]; 1771 else if (candidates[0]->ete_id <= enc->qpe_max_acked_id 1772 && !qenc_entry_is_draining(enc, candidates[0])) 1773 entry = candidates[0]; 1774 else 1775 break; 1776 id = entry->ete_id; 1777 prog = (struct encode_program) { 1778 .ep_enc_action = EEA_NONE, 1779 .ep_hea_action = EHA_INDEXED_DYN, 1780 .ep_tab_action = ETA_NOOP, 1781 .ep_flags = EPF_REF_FOUND, 1782 }; 1783 goto execute_program; 1784 } 1785 } 1786#if USE_USELESS_INITIALIZATION 1787 else 1788 { 1789 entry = NULL; 1790 n_cand = 0; 1791 } 1792#endif 1793 1794 /* Look for name-only match in the static table */ 1795 if (xhdr->flags & LSXPACK_QPACK_IDX) 1796 { 1797 static_id = xhdr->qpack_index; 1798 goto static_name_match; 1799 } 1800 else 1801 static_id = lsqpack_find_in_static_headers(name_hash, name, name_len); 1802 if (static_id >= 0) 1803 { 1804 static_name_match: 1805 id = static_id; 1806 if (index && (enough_room = qenc_has_or_can_evict_at_least(enc, 1807 ENTRY_COST(name_len, value_len)), enough_room != 0)) 1808 { 1809 static const struct encode_program programs[2][2][2] = { 1810 [0][0][0] = { EEA_NONE, EHA_LIT_WITH_NAME_STAT, ETA_NOOP, 0, }, 1811 [0][0][1] = { EEA_NONE, EHA_LIT_WITH_NAME_STAT, ETA_NOOP, 0, }, 1812 [0][1][0] = { EEA_NONE, EHA_LIT_WITH_NAME_STAT, ETA_NOOP, 0, }, 1813 [0][1][1] = { EEA_NONE, EHA_LIT_WITH_NAME_STAT, ETA_NOOP, 0, }, 1814 [1][0][0] = { EEA_INS_NAMEREF_STATIC, EHA_LIT_WITH_NAME_STAT, ETA_NEW, 0, }, 1815 [1][0][1] = { EEA_NONE, EHA_LIT_WITH_NAME_STAT, ETA_NOOP, 0, }, 1816 [1][1][0] = { EEA_INS_NAMEREF_STATIC, EHA_INDEXED_NEW, ETA_NEW, EPF_REF_NEW, }, 1817 [1][1][1] = { EEA_NONE, EHA_LIT_WITH_NAME_STAT, ETA_NOOP, 0, }, /* Invalid state */ 1818 }; 1819 seen_nameval = qenc_hist_seen(enc, HE_NAMEVAL, nameval_hash); 1820 prog = programs[seen_nameval][risk][use_dyn_table && n_cand > 0]; 1821 } 1822 else 1823 prog = (struct encode_program) { EEA_NONE, EHA_LIT_WITH_NAME_STAT, ETA_NOOP, 0, }; 1824 goto execute_program; 1825 } 1826 1827 seen_nameval = -1; 1828 /* Look for name-only match in the dynamic table */ 1829 /* TODO We may want to duplicate a dynamic entry whose name matches. 1830 * In that case, we'd follow similar logic as above: select candidates 1831 * and pick among them based on some factors. 1832 */ 1833 enough_room = -1; 1834 if (use_dyn_table) 1835 { 1836 buckno = BUCKNO(enc->qpe_nbits, name_hash); 1837 STAILQ_FOREACH(entry, &enc->qpe_buckets[buckno].by_name, ete_next_name) 1838 if (name_hash == entry->ete_name_hash && 1839 !qenc_entry_is_draining(enc, entry) && 1840 name_len == entry->ete_name_len && 1841 (risk || entry->ete_id <= enc->qpe_max_acked_id) && 1842 (!index || 1843 (enough_room < 0 ? 1844 (enough_room = qenc_has_or_can_evict_at_least(enc, 1845 ENTRY_COST(name_len, value_len))) 1846 : enough_room)) 1847 && 1848 0 == memcmp(name, ETE_NAME(entry), name_len)) 1849 { 1850 id = entry->ete_id; 1851 if (index && enough_room && risk 1852 && qenc_hist_seen(enc, HE_NAMEVAL, nameval_hash)) 1853 prog = (struct encode_program) { EEA_INS_NAMEREF_DYNAMIC, 1854 EHA_INDEXED_NEW, ETA_NEW, 1855 EPF_REF_NEW|EPF_REF_FOUND, }; 1856 else 1857 prog = (struct encode_program) { EEA_NONE, 1858 EHA_LIT_WITH_NAME_DYN, ETA_NOOP, EPF_REF_FOUND, }; 1859 goto execute_program; 1860 } 1861 } 1862 1863 /* No matches found */ 1864 if (index 1865 && (seen_nameval < 0 ? (seen_nameval 1866 = qenc_hist_seen(enc, HE_NAMEVAL, nameval_hash)) : seen_nameval) 1867 && (enough_room < 0 ? 1868 (enough_room = qenc_has_or_can_evict_at_least(enc, 1869 ENTRY_COST(name_len, value_len))) : enough_room)) 1870 { 1871 static const struct encode_program programs[2][2] = { 1872 [0][0] = { EEA_INS_LIT, EHA_LIT, ETA_NEW, 0, }, 1873 [0][1] = { EEA_NONE, EHA_LIT, ETA_NOOP, 0, }, 1874 [1][0] = { EEA_INS_LIT, EHA_INDEXED_NEW, ETA_NEW, EPF_REF_NEW, }, 1875 [1][1] = { EEA_NONE, EHA_LIT, ETA_NOOP, 0, }, /* Invalid state */ 1876 }; 1877 prog = programs[risk][use_dyn_table && n_cand > 0]; 1878 } 1879 else if (index && qenc_hist_seen(enc, HE_NAME, name_hash) 1880 && qenc_has_or_can_evict_at_least(enc, ENTRY_COST(name_len, 0))) 1881 { 1882 static const struct encode_program programs[2] = { 1883 [0] = { EEA_INS_LIT_NAME, EHA_LIT, ETA_NEW_NAME, 0, }, 1884 [1] = { EEA_INS_LIT_NAME, EHA_LIT_WITH_NAME_NEW, ETA_NEW_NAME, EPF_REF_NEW, }, 1885 }; 1886 prog = programs[ risk ]; 1887 } 1888 else 1889 prog = (struct encode_program) { EEA_NONE, EHA_LIT, ETA_NOOP, 0, }; 1890 1891 execute_program: 1892 if (((1 << prog.ep_enc_action) & 1893 ((1 << EEA_INS_NAMEREF_STATIC) | 1894 (1 << EEA_INS_NAMEREF_DYNAMIC) | 1895 (1 << EEA_INS_LIT) | 1896 (1 << EEA_INS_LIT_NAME))) 1897 && 1898 ((1 << prog.ep_hea_action) & 1899 ((1 << EHA_LIT) | 1900 (1 << EHA_LIT_WITH_NAME_STAT) | 1901 (1 << EHA_LIT_WITH_NAME_DYN) | 1902 (1 << EHA_LIT_WITH_NAME_NEW)))) 1903 { 1904 unsigned bytes_out, bytes_in; 1905 bytes_out = enc->qpe_bytes_out 1906 + qenc_enc_str_size((unsigned char *) name, name_len) 1907 + qenc_enc_str_size((unsigned char *) value, value_len) 1908 ; 1909 bytes_in = enc->qpe_bytes_in + name_len + value_len; 1910 if ((float) bytes_out / (float) bytes_in > 0.95) 1911 { 1912 assert(index); 1913 index = 0; 1914 E_DEBUG("double lit would result in ratio > 0.95, reset"); 1915 goto restart; 1916 } 1917 } 1918 1919 E_DEBUG("program: %s; %s; %s; flags: 0x%X", 1920 eea2str[ prog.ep_enc_action ], eha2str[ prog.ep_hea_action ], 1921 eta2str[ prog.ep_tab_action ], prog.ep_flags); 1922 switch (prog.ep_enc_action) 1923 { 1924 case EEA_DUP: 1925 if (enc_buf >= enc_buf_end) 1926 return LQES_NOBUF_ENC; 1927 dst = enc_buf; 1928 *dst = 0; 1929 dst = lsqpack_enc_int(dst, enc_buf_end, enc->qpe_ins_count - id, 5); 1930 if (dst <= enc_buf) 1931 return LQES_NOBUF_ENC; 1932 enc_sz = dst - enc_buf; 1933 break; 1934 case EEA_INS_NAMEREF_STATIC: 1935 if (enc_buf >= enc_buf_end) 1936 return LQES_NOBUF_ENC; 1937 dst = enc_buf; 1938 *dst = 0x80 | 0x40; 1939 dst = lsqpack_enc_int(dst, enc_buf_end, id, 6); 1940 if (dst <= enc_buf) 1941 return LQES_NOBUF_ENC; 1942 r = lsqpack_enc_enc_str(7, dst, enc_buf_end - dst, 1943 (const unsigned char *) value, value_len); 1944 if (r < 0) 1945 return LQES_NOBUF_ENC; 1946 dst += (unsigned) r; 1947 enc_sz = dst - enc_buf; 1948 break; 1949 case EEA_INS_NAMEREF_DYNAMIC: 1950 if (enc_buf >= enc_buf_end) 1951 return LQES_NOBUF_ENC; 1952 dst = enc_buf; 1953 *dst = 0x80; 1954 dst = lsqpack_enc_int(dst, enc_buf_end, enc->qpe_ins_count - id, 6); 1955 if (dst <= enc_buf) 1956 return LQES_NOBUF_ENC; 1957 r = lsqpack_enc_enc_str(7, dst, enc_buf_end - dst, 1958 (const unsigned char *) value, value_len); 1959 if (r < 0) 1960 return LQES_NOBUF_ENC; 1961 dst += (unsigned) r; 1962 enc_sz = dst - enc_buf; 1963 break; 1964 case EEA_INS_LIT: 1965 case EEA_INS_LIT_NAME: 1966 if (enc_buf >= enc_buf_end) 1967 return LQES_NOBUF_ENC; 1968 dst = enc_buf; 1969 *dst = 0x40; 1970 r = lsqpack_enc_enc_str(5, dst, enc_buf_end - dst, 1971 (const unsigned char *) name, name_len); 1972 if (r < 0) 1973 return LQES_NOBUF_ENC; 1974 dst += r; 1975 r = lsqpack_enc_enc_str(7, dst, enc_buf_end - dst, 1976 (const unsigned char *) value, 1977 prog.ep_enc_action == EEA_INS_LIT ? value_len : 0); 1978 if (r < 0) 1979 return LQES_NOBUF_ENC; 1980 dst += r; 1981 enc_sz = dst - enc_buf; 1982 break; 1983 default: 1984 assert(EEA_NONE == prog.ep_enc_action); 1985 enc_sz = 0; 1986 break; 1987 } 1988 1989 dst = hea_buf; 1990 switch (prog.ep_hea_action) 1991 { 1992 case EHA_INDEXED_STAT: 1993 *dst = 0x80 | 0x40; 1994 dst = lsqpack_enc_int(dst, hea_buf_end, id, 6); 1995 if (dst <= hea_buf) 1996 return LQES_NOBUF_HEAD; 1997 hea_sz = dst - hea_buf; 1998 break; 1999 case EHA_INDEXED_NEW: 2000 id = enc->qpe_ins_count + 1; 2001 post_base_idx: 2002 *dst = 0x10; 2003 assert(id > enc->qpe_cur_header.base_idx); 2004 dst = lsqpack_enc_int(dst, hea_buf_end, 2005 id - enc->qpe_cur_header.base_idx - 1, 4); 2006 if (dst <= hea_buf) 2007 return LQES_NOBUF_HEAD; 2008 hea_sz = dst - hea_buf; 2009 break; 2010 case EHA_INDEXED_DYN: 2011 if (id > enc->qpe_cur_header.base_idx) 2012 goto post_base_idx; 2013 *dst = 0x80; 2014 dst = lsqpack_enc_int(dst, hea_buf_end, 2015 enc->qpe_cur_header.base_idx - id, 6); 2016 if (dst <= hea_buf) 2017 return LQES_NOBUF_HEAD; 2018 hea_sz = dst - hea_buf; 2019 break; 2020 case EHA_LIT: 2021 *dst = 0x20 2022 | (((flags & LQEF_NEVER_INDEX) > 0) << 4) 2023 ; 2024 r = lsqpack_enc_enc_str(3, dst, hea_buf_end - dst, 2025 (const unsigned char *) name, name_len); 2026 if (r < 0) 2027 return LQES_NOBUF_HEAD; 2028 dst += r; 2029 r = lsqpack_enc_enc_str(7, dst, hea_buf_end - dst, 2030 (const unsigned char *) value, value_len); 2031 if (r < 0) 2032 return LQES_NOBUF_HEAD; 2033 dst += r; 2034 hea_sz = dst - hea_buf; 2035 break; 2036 case EHA_LIT_WITH_NAME_NEW: 2037 id = enc->qpe_ins_count + 1; 2038 post_base_name_ref: 2039 *dst = (((flags & LQEF_NEVER_INDEX) > 0) << 3); 2040 assert(id > enc->qpe_cur_header.base_idx); 2041 dst = lsqpack_enc_int(dst, hea_buf_end, 2042 id - enc->qpe_cur_header.base_idx - 1, 3); 2043 if (dst <= hea_buf) 2044 return LQES_NOBUF_HEAD; 2045 r = lsqpack_enc_enc_str(7, dst, hea_buf_end - dst, 2046 (const unsigned char *) value, value_len); 2047 if (r < 0) 2048 return LQES_NOBUF_HEAD; 2049 dst += (unsigned) r; 2050 hea_sz = dst - hea_buf; 2051 break; 2052 case EHA_LIT_WITH_NAME_DYN: 2053 if (id > enc->qpe_cur_header.base_idx) 2054 goto post_base_name_ref; 2055 *dst = 0x40 2056 | (((flags & LQEF_NEVER_INDEX) > 0) << 5) 2057 ; 2058 dst = lsqpack_enc_int(dst, hea_buf_end, 2059 enc->qpe_cur_header.base_idx - id, 4); 2060 if (dst <= hea_buf) 2061 return LQES_NOBUF_HEAD; 2062 r = lsqpack_enc_enc_str(7, dst, hea_buf_end - dst, 2063 (const unsigned char *) value, value_len); 2064 if (r < 0) 2065 return LQES_NOBUF_HEAD; 2066 dst += (unsigned) r; 2067 hea_sz = dst - hea_buf; 2068 break; 2069 default: 2070 assert(prog.ep_hea_action == EHA_LIT_WITH_NAME_STAT); 2071 *dst = 0x40 2072 | (((flags & LQEF_NEVER_INDEX) > 0) << 5) 2073 | 0x10 2074 ; 2075 dst = lsqpack_enc_int(dst, hea_buf_end, id, 4); 2076 if (dst <= hea_buf) 2077 return LQES_NOBUF_HEAD; 2078 r = lsqpack_enc_enc_str(7, dst, hea_buf_end - dst, 2079 (const unsigned char *) value, value_len); 2080 if (r < 0) 2081 return LQES_NOBUF_HEAD; 2082 dst += (unsigned) r; 2083 hea_sz = dst - hea_buf; 2084 break; 2085 } 2086 2087 switch (prog.ep_tab_action) 2088 { 2089 case ETA_NEW: 2090 case ETA_NEW_NAME: 2091 new_entry = lsqpack_enc_push_entry(enc, name_hash, nameval_hash, name, 2092 name_len, value, prog.ep_tab_action == ETA_NEW ? value_len : 0); 2093 if (!new_entry) 2094 { /* Push can only fail due to inability to allocate memory. 2095 * In this case, fall back on encoding without indexing. 2096 */ 2097 index = 0; 2098 goto restart; 2099 } 2100 enc->qpe_cur_header.hinfo->qhi_bytes_inserted += ETE_SIZE(new_entry); 2101 if (prog.ep_flags & EPF_REF_NEW) 2102 { 2103 ++new_entry->ete_n_reffd; 2104 enc->qpe_cur_header.flags |= LSQECH_REF_NEW_ENTRIES; 2105 if (HINFO_IDS_SET(enc->qpe_cur_header.hinfo)) 2106 assert(new_entry->ete_id > enc->qpe_cur_header.hinfo->qhi_max_id); 2107 qenc_maybe_update_hinfo_min_max(enc->qpe_cur_header.hinfo, 2108 new_entry->ete_id); 2109 } 2110 break; 2111 default: 2112 assert(prog.ep_tab_action == ETA_NOOP); 2113 break; 2114 } 2115 2116 if (prog.ep_flags & EPF_REF_FOUND) 2117 { 2118 ++entry->ete_n_reffd; 2119 qenc_maybe_update_hinfo_min_max(enc->qpe_cur_header.hinfo, 2120 entry->ete_id); 2121 } 2122 2123 qenc_remove_overflow_entries(enc); 2124 2125 if (update_hist) 2126 { 2127 assert(enc->qpe_hist_els); 2128 if (enc->qpe_cur_header.n_hdr_added_to_hist >= enc->qpe_hist_nels) 2129 qenc_hist_update_size(enc, enc->qpe_hist_nels + 4); 2130 qenc_hist_add(enc, name_hash, nameval_hash); 2131 ++enc->qpe_cur_header.n_hdr_added_to_hist; 2132 } 2133 2134 while (sz = qenc_dup_draining(enc, enc_buf + enc_sz, 2135 enc_buf_end - enc_buf - enc_sz), sz > 0) 2136 { 2137 enc_sz += sz; 2138 qenc_remove_overflow_entries(enc); 2139 } 2140 2141 enc->qpe_bytes_in += name_len + value_len; 2142 enc->qpe_bytes_out += enc_sz + hea_sz; 2143 if (enc->qpe_bytes_out > (1u << (sizeof(enc->qpe_bytes_out) * 8 - 1))) 2144 { 2145 enc->qpe_bytes_in = (float) enc->qpe_bytes_in 2146 / (float) enc->qpe_bytes_out * 1000; 2147 enc->qpe_bytes_out = 1000; 2148 E_DEBUG("reset bytes in/out counters, ratio: %.3f", 2149 lsqpack_enc_ratio(enc)); 2150 } 2151 2152 *enc_sz_p = enc_sz; 2153 *hea_sz_p = hea_sz; 2154 return LQES_OK; 2155} 2156 2157 2158int 2159lsqpack_enc_set_max_capacity (struct lsqpack_enc *enc, unsigned capacity, 2160 unsigned char *tsu_buf, size_t *tsu_buf_sz) 2161{ 2162 unsigned char *p; 2163 2164 if (capacity > enc->qpe_real_max_capacity) 2165 { 2166 errno = EINVAL; 2167 return -1; 2168 } 2169 2170 if (capacity == enc->qpe_cur_max_capacity) 2171 { 2172 E_DEBUG("set_capacity: capacity stays unchanged at %u", capacity); 2173 *tsu_buf_sz = 0; 2174 return 0; 2175 } 2176 2177 if (!(tsu_buf && tsu_buf_sz)) 2178 { 2179 errno = EINVAL; 2180 return -1; 2181 } 2182 p = tsu_buf; 2183 *p = 0x20; 2184 p = lsqpack_enc_int(p, tsu_buf + *tsu_buf_sz, capacity, 5); 2185 if (p <= tsu_buf) 2186 { 2187 errno = ENOBUFS; 2188 return -1; 2189 } 2190 *tsu_buf_sz = p - tsu_buf; 2191 2192 E_DEBUG("maximum capacity goes from %u to %u", enc->qpe_cur_max_capacity, 2193 capacity); 2194 enc->qpe_cur_max_capacity = capacity; 2195 qenc_remove_overflow_entries(enc); 2196 return 0; 2197} 2198 2199 2200static void 2201qenc_update_risked_list (struct lsqpack_enc *enc) 2202{ 2203 struct lsqpack_header_info *hinfo, *next; 2204 2205 for (hinfo = TAILQ_FIRST(&enc->qpe_risked_hinfos); hinfo; hinfo = next) 2206 { 2207 next = TAILQ_NEXT(hinfo, qhi_next_risked); 2208 if (!qenc_hinfo_at_risk(enc, hinfo)) 2209 qenc_remove_from_risked_list(enc, hinfo); 2210 } 2211} 2212 2213 2214static int 2215enc_proc_header_ack (struct lsqpack_enc *enc, uint64_t stream_id) 2216{ 2217 struct lsqpack_header_info *hinfo; 2218 2219 E_DEBUG("got Header Ack instruction, stream=%"PRIu64, stream_id); 2220 if (stream_id > MAX_QUIC_STREAM_ID) 2221 return -1; 2222 2223 TAILQ_FOREACH(hinfo, &enc->qpe_all_hinfos, qhi_next_all) 2224 if (stream_id == hinfo->qhi_stream_id) 2225 break; 2226 2227 /* 2228 * XXX if an ACK comes in while a header is being encoded, it will not 2229 * have any effect because the the `qhi_max_id` is 0 until the header 2230 * encoding is finished (see enc_end_header()). 2231 */ 2232 2233 if (!hinfo) 2234 return -1; 2235 2236 if (hinfo->qhi_max_id > enc->qpe_max_acked_id) 2237 { 2238 qenc_remove_from_risked_list(enc, hinfo); 2239 enc->qpe_max_acked_id = hinfo->qhi_max_id; 2240 qenc_update_risked_list(enc); 2241 E_DEBUG("max acked ID is now %u", enc->qpe_max_acked_id); 2242 } 2243 2244 enc_free_hinfo(enc, hinfo); 2245 return 0; 2246} 2247 2248 2249static int 2250enc_proc_ici (struct lsqpack_enc *enc, uint64_t ins_count) 2251{ 2252 lsqpack_abs_id_t max_acked; 2253 2254 E_DEBUG("got ICI instruction, count=%"PRIu64, ins_count); 2255 if (ins_count == 0) 2256 { 2257 E_INFO("ICI=0 is an error"); 2258 return -1; 2259 } 2260 2261 if (ins_count > LSQPACK_MAX_ABS_ID) 2262 { 2263 /* We never insert this many */ 2264 E_INFO("insertion count too high: %"PRIu64, ins_count); 2265 return -1; 2266 } 2267 2268 max_acked = (lsqpack_abs_id_t) ins_count + enc->qpe_last_ici; 2269 if (max_acked > enc->qpe_ins_count) 2270 { 2271 E_DEBUG("ICI: max_acked %u is larger than number of inserts %u", 2272 max_acked, enc->qpe_ins_count); 2273 return -1; 2274 } 2275 2276 if (max_acked > enc->qpe_max_acked_id) 2277 { 2278 enc->qpe_last_ici = max_acked; 2279 enc->qpe_max_acked_id = max_acked; 2280 E_DEBUG("max acked ID is now %u", enc->qpe_max_acked_id); 2281 qenc_update_risked_list(enc); 2282 } 2283 else 2284 { 2285 E_DEBUG("duplicate ICI: %u", max_acked); 2286 } 2287 return 0; 2288} 2289 2290 2291static int 2292enc_proc_stream_cancel (struct lsqpack_enc *enc, uint64_t stream_id) 2293{ 2294 struct lsqpack_header_info *hinfo, *next; 2295 unsigned count; 2296 2297 E_DEBUG("got Cancel Stream instruction; stream=%"PRIu64, stream_id); 2298 2299 if (stream_id > MAX_QUIC_STREAM_ID) 2300 { 2301 E_INFO("Invalid stream ID %"PRIu64" in Cancel Stream", stream_id); 2302 return -1; 2303 } 2304 2305 count = 0; 2306 for (hinfo = TAILQ_FIRST(&enc->qpe_all_hinfos); hinfo; hinfo = next) 2307 { 2308 next = TAILQ_NEXT(hinfo, qhi_next_all); 2309 if (hinfo->qhi_stream_id == stream_id) 2310 { 2311 E_DEBUG("cancel header block for stream %"PRIu64", seqno %u", 2312 stream_id, hinfo->qhi_seqno); 2313 if (qenc_hinfo_at_risk(enc, hinfo)) 2314 qenc_remove_from_risked_list(enc, hinfo); 2315 enc_free_hinfo(enc, hinfo); 2316 ++count; 2317 } 2318 } 2319 2320 E_DEBUG("cancelled %u header block%.*s of stream %"PRIu64, 2321 count, count != 1, "s", stream_id); 2322 return 0; 2323} 2324 2325 2326/* Assumption: we have at least one byte to work with */ 2327/* Return value: 2328 * 0 OK 2329 * -1 Out of input 2330 * -2 Value cannot be represented as 64-bit integer (overflow) 2331 */ 2332int 2333lsqpack_dec_int (const unsigned char **src_p, const unsigned char *src_end, 2334 unsigned prefix_bits, uint64_t *value_p, 2335 struct lsqpack_dec_int_state *state) 2336{ 2337 const unsigned char *const orig_src = *src_p; 2338 const unsigned char *src; 2339 unsigned char prefix_max; 2340 unsigned M, nread; 2341 uint64_t val, B; 2342 2343 src = *src_p; 2344 2345 if (state->resume) 2346 { 2347 val = state->val; 2348 M = state->M; 2349 goto resume; 2350 } 2351 2352 prefix_max = (1 << prefix_bits) - 1; 2353 val = *src++; 2354 val &= prefix_max; 2355 2356 if (val < prefix_max) 2357 { 2358 *src_p = src; 2359 *value_p = val; 2360 return 0; 2361 } 2362 2363 M = 0; 2364 do 2365 { 2366 if (src < src_end) 2367 { 2368 resume: B = *src++; 2369 val = val + ((B & 0x7f) << M); 2370 M += 7; 2371 } 2372 else 2373 { 2374 nread = (state->resume ? state->nread : 0) + (src - orig_src); 2375 if (nread < LSQPACK_UINT64_ENC_SZ) 2376 { 2377 state->val = val; 2378 state->M = M; 2379 state->nread = nread; 2380 state->resume = 1; 2381 return -1; 2382 } 2383 else 2384 return -2; 2385 } 2386 } 2387 while (B & 0x80); 2388 2389 if (M <= 63 || (M == 70 && src[-1] <= 1 && (val & (1ull << 63)))) 2390 { 2391 *src_p = src; 2392 *value_p = val; 2393 return 0; 2394 } 2395 else 2396 return -2; 2397} 2398 2399 2400typedef char unsigned_is_32bits[(sizeof(unsigned) == 4) ? 1 : -1]; 2401 2402/* TODO: rewrite as a standalone function */ 2403int 2404lsqpack_dec_int24 (const unsigned char **src_p, const unsigned char *src_end, 2405 unsigned prefix_bits, unsigned *value_p, 2406 struct lsqpack_dec_int_state *state) 2407{ 2408 uint64_t val; 2409 int r; 2410 2411 r = lsqpack_dec_int(src_p, src_end, prefix_bits, &val, state); 2412 if (r == 0 && val < (1u << 24)) 2413 { 2414 *value_p = (unsigned int) val; 2415 return 0; 2416 } 2417 else if (r != 0) 2418 return r; 2419 else 2420 return -2; 2421} 2422 2423 2424int 2425lsqpack_enc_decoder_in (struct lsqpack_enc *enc, 2426 const unsigned char *buf, size_t buf_sz) 2427{ 2428 const unsigned char *const end = buf + buf_sz; 2429 uint64_t val; 2430 int r; 2431 unsigned prefix_bits = ~0u; /* This can be any value in a resumed call 2432 * to the integer decoder -- it is only 2433 * used in the first call. 2434 */ 2435 E_DEBUG("got %zu bytes of decoder stream", buf_sz); 2436 2437 while (buf < end) 2438 { 2439 switch (enc->qpe_dec_stream_state.dec_int_state.resume) 2440 { 2441 case 0: 2442 if (buf[0] & 0x80) /* Header ACK */ 2443 { 2444 prefix_bits = 7; 2445 enc->qpe_dec_stream_state.handler = enc_proc_header_ack; 2446 } 2447 else if ((buf[0] & 0xC0) == 0) /* Insert Count Increment */ 2448 { 2449 prefix_bits = 6; 2450 enc->qpe_dec_stream_state.handler = enc_proc_ici; 2451 } 2452 else /* Stream Cancellation */ 2453 { 2454 assert((buf[0] & 0xC0) == 0x40); 2455 prefix_bits = 6; 2456 enc->qpe_dec_stream_state.handler = enc_proc_stream_cancel; 2457 } 2458 /* fall through */ 2459 case 1: 2460 r = lsqpack_dec_int(&buf, end, prefix_bits, &val, 2461 &enc->qpe_dec_stream_state.dec_int_state); 2462 if (r == 0) 2463 { 2464 r = enc->qpe_dec_stream_state.handler(enc, val); 2465 if (r != 0) 2466 return -1; 2467 enc->qpe_dec_stream_state.dec_int_state.resume = 0; 2468 } 2469 else if (r == -1) 2470 { 2471 enc->qpe_dec_stream_state.dec_int_state.resume = 1; 2472 return 0; 2473 } 2474 else 2475 return -1; 2476 break; 2477 } 2478 } 2479 enc->qpe_bytes_out += buf_sz; 2480 2481 return 0; 2482} 2483 2484 2485float 2486lsqpack_enc_ratio (const struct lsqpack_enc *enc) 2487{ 2488 float ratio; 2489 2490 if (enc->qpe_bytes_in) 2491 { 2492 ratio = (float) enc->qpe_bytes_out / (float) enc->qpe_bytes_in; 2493 E_DEBUG("bytes out: %u; bytes in: %u, ratio: %.3f", 2494 enc->qpe_bytes_out, enc->qpe_bytes_in, ratio); 2495 return ratio; 2496 } 2497 else 2498 return 0; 2499} 2500 2501 2502#ifdef LSQPACK_DEC_LOGGER_HEADER 2503#include LSQPACK_DEC_LOGGER_HEADER 2504#else 2505#define D_LOG(prefix, ...) do { \ 2506 if (dec->qpd_logger_ctx) { \ 2507 fprintf(dec->qpd_logger_ctx, prefix); \ 2508 fprintf(dec->qpd_logger_ctx, __VA_ARGS__); \ 2509 fprintf(dec->qpd_logger_ctx, "\n"); \ 2510 } \ 2511} while (0) 2512#define D_DEBUG(...) D_LOG("qdec: debug: ", __VA_ARGS__) 2513#define D_INFO(...) D_LOG("qdec: info: ", __VA_ARGS__) 2514#define D_WARN(...) D_LOG("qdec: warn: ", __VA_ARGS__) 2515#define D_ERROR(...) D_LOG("qdec: error: ", __VA_ARGS__) 2516#endif 2517 2518 2519/* Dynamic table entry: */ 2520struct lsqpack_dec_table_entry 2521{ 2522 unsigned dte_name_len; 2523 unsigned dte_val_len; 2524 unsigned dte_refcnt; 2525 unsigned dte_name_hash; 2526 unsigned dte_nameval_hash; 2527 unsigned dte_name_idx; 2528 enum { 2529 DTEF_NAME_HASH = 1 << 0, 2530 DTEF_NAMEVAL_HASH = 1 << 1, 2531 DTEF_NAME_IDX = 1 << 2, 2532 } dte_flags; 2533 char dte_buf[0]; /* Contains both name and value */ 2534}; 2535 2536#define DTE_NAME(dte) ((dte)->dte_buf) 2537#define DTE_VALUE(dte) (&(dte)->dte_buf[(dte)->dte_name_len]) 2538#define DTE_SIZE(dte) ENTRY_COST((dte)->dte_name_len, (dte)->dte_val_len) 2539 2540enum 2541{ 2542 HPACK_HUFFMAN_FLAG_ACCEPTED = 0x01, 2543 HPACK_HUFFMAN_FLAG_SYM = 0x02, 2544 HPACK_HUFFMAN_FLAG_FAIL = 0x04, 2545}; 2546 2547 2548#if LSQPACK_DEVEL_MODE 2549# define STATIC 2550#else 2551# define STATIC static 2552#endif 2553 2554STATIC unsigned 2555ringbuf_count (const struct lsqpack_ringbuf *rbuf) 2556{ 2557 if (rbuf->rb_nalloc) 2558 { 2559 if (rbuf->rb_head >= rbuf->rb_tail) 2560 return rbuf->rb_head - rbuf->rb_tail; 2561 else 2562 return rbuf->rb_nalloc - (rbuf->rb_tail - rbuf->rb_head); 2563 } 2564 else 2565 return 0; 2566} 2567 2568 2569STATIC int 2570ringbuf_full (const struct lsqpack_ringbuf *rbuf) 2571{ 2572 return rbuf->rb_nalloc == 0 2573 || (rbuf->rb_head + 1) % rbuf->rb_nalloc == rbuf->rb_tail; 2574} 2575 2576 2577STATIC int 2578ringbuf_empty (const struct lsqpack_ringbuf *rbuf) 2579{ 2580 return rbuf->rb_head == rbuf->rb_tail; 2581} 2582 2583 2584struct ringbuf_iter 2585{ 2586 const struct lsqpack_ringbuf *rbuf; 2587 unsigned next, end; 2588}; 2589 2590 2591STATIC void * 2592ringbuf_iter_next (struct ringbuf_iter *iter) 2593{ 2594 void *el; 2595 2596 if (iter->next != iter->rbuf->rb_head) 2597 { 2598 el = iter->rbuf->rb_els[ iter->next ]; 2599 iter->next = (iter->next + 1) % iter->rbuf->rb_nalloc; 2600 return el; 2601 } 2602 else 2603 return NULL; 2604} 2605 2606 2607STATIC void * 2608ringbuf_iter_first (struct ringbuf_iter *iter, 2609 const struct lsqpack_ringbuf *rbuf) 2610{ 2611 if (!ringbuf_empty(rbuf)) 2612 { 2613 iter->rbuf = rbuf; 2614 iter->next = rbuf->rb_tail; 2615 return ringbuf_iter_next(iter); 2616 } 2617 else 2618 return NULL; 2619} 2620 2621 2622static void 2623ringbuf_cleanup (struct lsqpack_ringbuf *rbuf) 2624{ 2625 free(rbuf->rb_els); 2626 memset(rbuf, 0, sizeof(*rbuf)); 2627} 2628 2629 2630static void * 2631ringbuf_get_head (const struct lsqpack_ringbuf *rbuf, unsigned off) 2632{ 2633 unsigned i; 2634 2635 i = (rbuf->rb_nalloc + rbuf->rb_head - off) % rbuf->rb_nalloc; 2636 return rbuf->rb_els[i]; 2637} 2638 2639 2640static void * 2641ringbuf_advance_tail (struct lsqpack_ringbuf *rbuf) 2642{ 2643 void *el; 2644 2645 el = rbuf->rb_els[rbuf->rb_tail]; 2646 rbuf->rb_tail = (rbuf->rb_tail + 1) % rbuf->rb_nalloc; 2647 return el; 2648} 2649 2650 2651static int 2652ringbuf_add (struct lsqpack_ringbuf *rbuf, void *el) 2653{ 2654 void **els; 2655 unsigned count; 2656 2657 if (!ringbuf_full(rbuf)) 2658 { 2659 insert: 2660 rbuf->rb_els[ rbuf->rb_head ] = el; 2661 rbuf->rb_head = (rbuf->rb_head + 1) % rbuf->rb_nalloc; 2662 return 0; 2663 } 2664 2665 if (rbuf->rb_nalloc) 2666 { 2667 els = malloc(rbuf->rb_nalloc * 2 * sizeof(rbuf->rb_els[0])); 2668 if (els) 2669 { 2670 if (rbuf->rb_head >= rbuf->rb_tail) 2671 { 2672 count = rbuf->rb_head - rbuf->rb_tail + 1; 2673 memcpy(els, rbuf->rb_els + rbuf->rb_tail, 2674 count * sizeof(rbuf->rb_els[0])); 2675 rbuf->rb_tail = 0; 2676 rbuf->rb_head = count - 1; 2677 } 2678 else 2679 { 2680 memcpy(els, rbuf->rb_els, 2681 (rbuf->rb_head + 1) * sizeof(rbuf->rb_els[0])); 2682 memcpy(els + rbuf->rb_nalloc + rbuf->rb_tail, 2683 rbuf->rb_els + rbuf->rb_tail, 2684 (rbuf->rb_nalloc - rbuf->rb_tail) 2685 * sizeof(rbuf->rb_els[0])); 2686 rbuf->rb_tail += rbuf->rb_nalloc; 2687 2688 } 2689 free(rbuf->rb_els); 2690 rbuf->rb_els = els; 2691 rbuf->rb_nalloc *= 2; 2692 goto insert; 2693 } 2694 return -1; 2695 } 2696 else 2697 { 2698 /* First time */ 2699 rbuf->rb_els = malloc(4 * sizeof(rbuf->rb_els[0])); 2700 if (rbuf->rb_els) 2701 { 2702 rbuf->rb_nalloc = 4; 2703 goto insert; 2704 } 2705 return -1; 2706 } 2707} 2708 2709 2710#define ID_MINUS(a, b) ( (dec)->qpd_max_entries ? \ 2711 ((a) + (dec)->qpd_max_entries * 2 - (b)) % ((dec)->qpd_max_entries * 2) : 0) 2712 2713#define ID_PLUS(a, b) ( (dec)->qpd_max_entries ? \ 2714 ((a) + (b)) % ((dec)->qpd_max_entries * 2) : 0 ) 2715 2716static struct lsqpack_dec_table_entry * 2717qdec_get_table_entry_rel (const struct lsqpack_dec *dec, 2718 lsqpack_abs_id_t relative_idx) 2719{ 2720 ++relative_idx; 2721 if (ringbuf_count(&dec->qpd_dyn_table) >= relative_idx) 2722 return ringbuf_get_head(&dec->qpd_dyn_table, relative_idx); 2723 else 2724 return NULL; 2725} 2726 2727 2728static struct lsqpack_dec_table_entry * 2729qdec_get_table_entry_abs (const struct lsqpack_dec *dec, 2730 lsqpack_abs_id_t abs_idx) 2731{ 2732 unsigned off; 2733 2734 off = ID_MINUS(dec->qpd_last_id, abs_idx); 2735 return qdec_get_table_entry_rel(dec, off); 2736} 2737 2738 2739void 2740lsqpack_dec_init (struct lsqpack_dec *dec, void *logger_ctx, 2741 unsigned dyn_table_size, unsigned max_risked_streams, 2742 const struct lsqpack_dec_hset_if *dh_if, enum lsqpack_dec_opts opts) 2743{ 2744 unsigned i; 2745 memset(dec, 0, sizeof(*dec)); 2746 dec->qpd_opts = opts; 2747 dec->qpd_logger_ctx = logger_ctx; 2748 dec->qpd_max_capacity = dyn_table_size; 2749 dec->qpd_cur_max_capacity = dyn_table_size; 2750 dec->qpd_max_entries = dec->qpd_max_capacity / DYNAMIC_ENTRY_OVERHEAD; 2751 dec->qpd_last_id = dec->qpd_max_entries * 2 - 1; 2752 dec->qpd_largest_known_id = dec->qpd_max_entries * 2 - 1; 2753 dec->qpd_max_risked_streams = max_risked_streams; 2754 dec->qpd_dh_if = dh_if; 2755 TAILQ_INIT(&dec->qpd_hbrcs); 2756 for (i = 0; i < (1 << LSQPACK_DEC_BLOCKED_BITS); ++i) 2757 TAILQ_INIT(&dec->qpd_blocked_headers[i]); 2758 D_DEBUG("initialized. max capacity=%u; max risked streams=%u", 2759 dec->qpd_max_capacity, dec->qpd_max_risked_streams); 2760} 2761 2762 2763static void 2764qdec_decref_entry (struct lsqpack_dec_table_entry *entry) 2765{ 2766 --entry->dte_refcnt; 2767 if (0 == entry->dte_refcnt) 2768 free(entry); 2769} 2770 2771 2772enum { 2773 DEI_NEXT_INST, 2774 DEI_WINR_READ_NAME_IDX, 2775 DEI_WINR_BEGIN_READ_VAL_LEN, 2776 DEI_WINR_READ_VAL_LEN, 2777 DEI_WINR_READ_VALUE_PLAIN, 2778 DEI_WINR_READ_VALUE_HUFFMAN, 2779 DEI_DUP_READ_IDX, 2780 DEI_SIZE_UPD_READ_IDX, 2781 DEI_WONR_READ_NAME_LEN, 2782 DEI_WONR_READ_NAME_HUFFMAN, 2783 DEI_WONR_READ_NAME_PLAIN, 2784 DEI_WONR_BEGIN_READ_VAL_LEN, 2785 DEI_WONR_READ_VAL_LEN, 2786 DEI_WONR_READ_VALUE_HUFFMAN, 2787 DEI_WONR_READ_VALUE_PLAIN, 2788}; 2789 2790struct header_block_read_ctx 2791{ 2792 TAILQ_ENTRY(header_block_read_ctx) hbrc_next_all, 2793 hbrc_next_blocked; 2794 void *hbrc_hblock; 2795 uint64_t hbrc_stream_id; 2796 size_t hbrc_orig_size; /* To report error offset */ 2797 size_t hbrc_size; 2798 lsqpack_abs_id_t hbrc_largest_ref; /* Parsed from prefix */ 2799 lsqpack_abs_id_t hbrc_base_index; /* Parsed from prefix */ 2800 unsigned hbrc_header_count; 2801 2802 struct { 2803 struct lsxpack_header *xhdr; /* Current header */ 2804 enum { 2805 XOUT_NAME, /* Writing name */ 2806 XOUT_VALUE, /* Writing value */ 2807 } state; 2808 unsigned off; /* How much has been written */ 2809 } hbrc_out; 2810 2811 /* There are two parsing phases: reading the prefix and reading the 2812 * instruction stream. 2813 */ 2814 enum lsqpack_read_header_status (*hbrc_parse) (struct lsqpack_dec *, 2815 struct header_block_read_ctx *, const unsigned char *, size_t); 2816 2817 enum { 2818 HBRC_LARGEST_REF_READ = 1 << 0, 2819 HBRC_LARGEST_REF_SET = 1 << 1, /* hbrc_largest_ref is an actual ID */ 2820 HBRC_BLOCKED = 1 << 2, 2821 HBRC_DINST = 1 << 3, 2822 HBRC_ON_LIST = 1 << 4, 2823#define LARGEST_USED_SHIFT 5 2824 HBRC_LARGEST_REF_USED = 1 << LARGEST_USED_SHIFT, 2825 HBRC_DYN_USED_IN_ERR = 1 << 6, 2826 } hbrc_flags; 2827 2828 struct hbrc_buf { 2829 const unsigned char *buf; 2830 size_t sz; 2831 size_t off; 2832 } hbrc_buf; 2833 2834 union { 2835 struct { 2836 enum { 2837 PREFIX_STATE_BEGIN_READING_LARGEST_REF, 2838 PREFIX_STATE_READ_LARGEST_REF, 2839 PREFIX_STATE_BEGIN_READING_BASE_IDX, 2840 PREFIX_STATE_READ_DELTA_BASE_IDX, 2841 } state; 2842 union { 2843 /* Required Insert Count */ 2844 struct { 2845 struct lsqpack_dec_int_state dec_int_state; 2846 uint64_t value; 2847 } ric; 2848 /* Delta Base */ 2849 struct { 2850 struct lsqpack_dec_int_state dec_int_state; 2851 uint64_t value; 2852 int sign; 2853 } delb; 2854 } u; 2855 } prefix; 2856 struct { 2857 enum { 2858 DATA_STATE_NEXT_INSTRUCTION, 2859 DATA_STATE_READ_IHF_IDX, 2860 DATA_STATE_READ_IPBI_IDX, 2861 DATA_STATE_READ_LFINR_IDX, 2862 DATA_STATE_BEGIN_READ_VAL_LEN, 2863 DATA_STATE_READ_VAL_LEN, 2864 DATA_STATE_READ_VAL_HUFFMAN, 2865 DATA_STATE_READ_VAL_PLAIN, 2866 DATA_STATE_READ_LFONR_NAME_LEN, 2867 DATA_STATE_READ_NAME_HUFFMAN, 2868 DATA_STATE_READ_NAME_PLAIN, 2869 DATA_STATE_READ_LFPBNR_IDX, 2870 DATA_STATE_BEGIN_READ_LFPBNR_VAL_LEN, 2871 DATA_STATE_READ_LFPBNR_VAL_LEN, 2872 } state; 2873 2874 /* We decode one string at a time, header name or header value. */ 2875 unsigned left; /* Left to read */ 2876 int is_static; 2877 int is_never; 2878 int is_huffman; 2879 struct lsqpack_dec_int_state dec_int_state; 2880 struct lsqpack_huff_decode_state dec_huff_state; 2881 } data; 2882 } hbrc_parse_ctx_u; 2883}; 2884 2885 2886static enum lsqpack_read_header_status 2887parse_header_data (struct lsqpack_dec *, 2888 struct header_block_read_ctx *, const unsigned char *, size_t); 2889 2890 2891float 2892lsqpack_dec_ratio (const struct lsqpack_dec *dec) 2893{ 2894 float ratio; 2895 2896 if (dec->qpd_bytes_out) 2897 { 2898 ratio = (float) dec->qpd_bytes_in / (float) dec->qpd_bytes_out; 2899 D_DEBUG("bytes in: %u; bytes out: %u, ratio: %.3f", 2900 dec->qpd_bytes_out, dec->qpd_bytes_in, ratio); 2901 return ratio; 2902 } 2903 else 2904 return 0; 2905} 2906 2907 2908void 2909lsqpack_dec_cleanup (struct lsqpack_dec *dec) 2910{ 2911 struct lsqpack_dec_table_entry *entry; 2912 struct header_block_read_ctx *read_ctx, *next_read_ctx; 2913 2914 for (read_ctx = TAILQ_FIRST(&dec->qpd_hbrcs); read_ctx; 2915 read_ctx = next_read_ctx) 2916 { 2917 next_read_ctx = TAILQ_NEXT(read_ctx, hbrc_next_all); 2918 free(read_ctx); 2919 } 2920 2921 if (dec->qpd_enc_state.resume >= DEI_WINR_READ_NAME_IDX 2922 && dec->qpd_enc_state.resume <= DEI_WINR_READ_VALUE_HUFFMAN) 2923 { 2924 if (dec->qpd_enc_state.ctx_u.with_namref.entry) 2925 free(dec->qpd_enc_state.ctx_u.with_namref.entry); 2926 } 2927 else if (dec->qpd_enc_state.resume >= DEI_WONR_READ_NAME_LEN 2928 && dec->qpd_enc_state.resume <= DEI_WONR_READ_VALUE_PLAIN) 2929 { 2930 if (dec->qpd_enc_state.ctx_u.wo_namref.entry) 2931 free(dec->qpd_enc_state.ctx_u.wo_namref.entry); 2932 } 2933 2934 while (!ringbuf_empty(&dec->qpd_dyn_table)) 2935 { 2936 entry = ringbuf_advance_tail(&dec->qpd_dyn_table); 2937 qdec_decref_entry(entry); 2938 } 2939 ringbuf_cleanup(&dec->qpd_dyn_table); 2940 D_DEBUG("cleaned up"); 2941} 2942 2943 2944static void 2945qdec_maybe_update_entry_hashes (const struct lsqpack_dec *dec, 2946 struct lsqpack_dec_table_entry *entry) 2947{ 2948 if ((dec->qpd_opts & (LSQPACK_DEC_OPT_HASH_NAME 2949 |LSQPACK_DEC_OPT_HASH_NAMEVAL)) 2950 && !(entry->dte_flags & DTEF_NAME_HASH)) 2951 { 2952 entry->dte_flags |= DTEF_NAME_HASH; 2953 entry->dte_name_hash = XXH32(DTE_NAME(entry), entry->dte_name_len, 2954 LSQPACK_XXH_SEED); 2955 } 2956 if ((dec->qpd_opts & LSQPACK_DEC_OPT_HASH_NAMEVAL) 2957 && !(entry->dte_flags & DTEF_NAMEVAL_HASH)) 2958 { 2959 assert(entry->dte_flags & DTEF_NAME_HASH); 2960 entry->dte_flags |= DTEF_NAMEVAL_HASH; 2961 entry->dte_nameval_hash = XXH32(DTE_VALUE(entry), entry->dte_val_len, 2962 entry->dte_name_hash); 2963 } 2964} 2965 2966 2967static int 2968header_out_static_entry (struct lsqpack_dec *dec, 2969 struct header_block_read_ctx *read_ctx, uint64_t idx) 2970{ 2971 struct lsxpack_header *xhdr; 2972 size_t need, http1x; 2973 char *dst; 2974 int r; 2975 2976 if (idx >= QPACK_STATIC_TABLE_SIZE) 2977 return -1; 2978 2979 http1x = !!(dec->qpd_opts & LSQPACK_DEC_OPT_HTTP1X) << 2; /* 0 or 4 */ 2980 need = static_table[ idx ].name_len + static_table[ idx ].val_len + http1x; 2981 xhdr = dec->qpd_dh_if->dhi_prepare_decode(read_ctx->hbrc_hblock, NULL, 2982 need); 2983 if (!xhdr) 2984 return -1; 2985 2986 xhdr->dec_overhead = http1x; 2987 xhdr->qpack_index = idx; 2988 xhdr->flags |= LSXPACK_VAL_MATCHED | LSXPACK_QPACK_IDX 2989 | LSXPACK_NAME_HASH | LSXPACK_NAMEVAL_HASH; 2990 xhdr->name_len = static_table[ idx ].name_len; 2991 xhdr->val_len = static_table[ idx ].val_len; 2992 xhdr->name_hash = name_hashes[ idx ]; 2993 xhdr->nameval_hash = nameval_hashes[ idx ]; 2994 dst = xhdr->buf + xhdr->name_offset; 2995 memcpy(dst, static_table[ idx ].name, static_table[ idx ].name_len); 2996 dst += static_table[ idx ].name_len; 2997 if (http1x) 2998 { 2999 memcpy(dst, ": ", 2); 3000 dst += 2; 3001 } 3002 xhdr->val_offset = dst - xhdr->buf; 3003 memcpy(dst, static_table[ idx ].val, static_table[ idx ].val_len); 3004 dst += static_table[ idx ].val_len; 3005 if (http1x) 3006 memcpy(dst, "\r\n", 2); 3007 r = dec->qpd_dh_if->dhi_process_header(read_ctx->hbrc_hblock, xhdr); 3008 if (r == 0) 3009 dec->qpd_bytes_out += static_table[ idx ].name_len 3010 + static_table[ idx ].val_len; 3011 return r; 3012} 3013 3014 3015static int 3016header_out_dynamic_entry (struct lsqpack_dec *dec, 3017 struct header_block_read_ctx *read_ctx, lsqpack_abs_id_t idx) 3018{ 3019 struct lsqpack_dec_table_entry *entry; 3020 struct lsxpack_header *xhdr; 3021 size_t need, http1x; 3022 char *dst; 3023 int r; 3024 3025 entry = qdec_get_table_entry_abs(dec, idx); 3026 if (!entry) 3027 return -1; 3028 3029 http1x = !!(dec->qpd_opts & LSQPACK_DEC_OPT_HTTP1X) << 2; /* 0 or 4 */ 3030 need = entry->dte_name_len + entry->dte_val_len + http1x; 3031 xhdr = dec->qpd_dh_if->dhi_prepare_decode(read_ctx->hbrc_hblock, NULL, 3032 need); 3033 if (!xhdr) 3034 return -1; 3035 3036 qdec_maybe_update_entry_hashes(dec, entry); 3037 if (entry->dte_flags & DTEF_NAME_HASH) 3038 { 3039 xhdr->flags |= LSXPACK_NAME_HASH; 3040 xhdr->name_hash = entry->dte_name_hash; 3041 } 3042 if (entry->dte_flags & DTEF_NAMEVAL_HASH) 3043 { 3044 xhdr->flags |= LSXPACK_NAMEVAL_HASH; 3045 xhdr->nameval_hash = entry->dte_nameval_hash; 3046 } 3047 if (entry->dte_flags & DTEF_NAME_IDX) 3048 { 3049 xhdr->flags |= LSXPACK_QPACK_IDX; 3050 xhdr->qpack_index = entry->dte_name_idx; 3051 } 3052 xhdr->dec_overhead = http1x; 3053 xhdr->name_len = entry->dte_name_len; 3054 xhdr->val_len = entry->dte_val_len; 3055 dst = xhdr->buf + xhdr->name_offset; 3056 memcpy(dst, DTE_NAME(entry), entry->dte_name_len); 3057 dst += entry->dte_name_len; 3058 if (http1x) 3059 { 3060 memcpy(dst, ": ", 2); 3061 dst += 2; 3062 } 3063 xhdr->val_offset = dst - xhdr->buf; 3064 memcpy(dst, DTE_VALUE(entry), entry->dte_val_len); 3065 dst += entry->dte_val_len; 3066 if (http1x) 3067 memcpy(dst, "\r\n", 2); 3068 r = dec->qpd_dh_if->dhi_process_header(read_ctx->hbrc_hblock, xhdr); 3069 if (r == 0) 3070 dec->qpd_bytes_out += entry->dte_name_len + entry->dte_val_len; 3071 return r; 3072} 3073 3074 3075static int 3076header_out_begin_static_nameref (struct lsqpack_dec *dec, 3077 struct header_block_read_ctx *read_ctx, unsigned idx, int is_never) 3078{ 3079 struct lsxpack_header *xhdr; /* Shorthand */ 3080 size_t need, http1x; 3081 char *dst; 3082 3083 assert(!read_ctx->hbrc_out.xhdr); 3084 3085 if (idx >= QPACK_STATIC_TABLE_SIZE) 3086 return -1; 3087 3088 http1x = !!(dec->qpd_opts & LSQPACK_DEC_OPT_HTTP1X) << 2; /* 0 or 4 */ 3089 need = static_table[ idx ].name_len + http1x; 3090 read_ctx->hbrc_out.xhdr = xhdr = dec->qpd_dh_if->dhi_prepare_decode( 3091 read_ctx->hbrc_hblock, NULL, need); 3092 if (!xhdr) 3093 return -1; 3094 3095 xhdr->dec_overhead = http1x; 3096 xhdr->qpack_index = idx; 3097 xhdr->flags |= LSXPACK_QPACK_IDX | LSXPACK_NAME_HASH; 3098 xhdr->name_hash = name_hashes[ idx ]; 3099 if (is_never) 3100 xhdr->flags |= LSXPACK_NEVER_INDEX; 3101 xhdr->name_len = static_table[ idx ].name_len; 3102 dst = xhdr->buf + xhdr->name_offset; 3103 memcpy(dst, static_table[ idx ].name, static_table[ idx ].name_len); 3104 dst += static_table[ idx ].name_len; 3105 if (http1x) 3106 { 3107 memcpy(dst, ": ", 2); 3108 dst += 2; 3109 } 3110 xhdr->val_offset = dst - xhdr->buf; 3111 read_ctx->hbrc_out.state = XOUT_VALUE; 3112 read_ctx->hbrc_out.off = 0; 3113 return 0; 3114} 3115 3116 3117static int 3118header_out_begin_dynamic_nameref (struct lsqpack_dec *dec, 3119 struct header_block_read_ctx *read_ctx, 3120 struct lsqpack_dec_table_entry *entry, int is_never) 3121{ 3122 struct lsxpack_header *xhdr; /* Shorthand */ 3123 size_t need, http1x; 3124 char *dst; 3125 3126 assert(!read_ctx->hbrc_out.xhdr); 3127 3128 http1x = !!(dec->qpd_opts & LSQPACK_DEC_OPT_HTTP1X) << 2; /* 0 or 4 */ 3129 need = entry->dte_name_len + http1x; 3130 read_ctx->hbrc_out.xhdr = xhdr = dec->qpd_dh_if->dhi_prepare_decode( 3131 read_ctx->hbrc_hblock, NULL, need); 3132 if (!xhdr) 3133 return -1; 3134 3135 xhdr->dec_overhead = http1x; 3136 if (is_never) 3137 xhdr->flags |= LSXPACK_NEVER_INDEX; 3138 qdec_maybe_update_entry_hashes(dec, entry); 3139 if (entry->dte_flags & DTEF_NAME_HASH) 3140 { 3141 xhdr->flags |= LSXPACK_NAME_HASH; 3142 xhdr->name_hash = entry->dte_name_hash; 3143 } 3144 if (entry->dte_flags & DTEF_NAME_IDX) 3145 { 3146 xhdr->flags |= LSXPACK_QPACK_IDX; 3147 xhdr->qpack_index = entry->dte_name_idx; 3148 } 3149 xhdr->name_len = entry->dte_name_len; 3150 dst = xhdr->buf + xhdr->name_offset; 3151 memcpy(dst, DTE_NAME(entry), entry->dte_name_len); 3152 dst += entry->dte_name_len; 3153 if (http1x) 3154 { 3155 memcpy(dst, ": ", 2); 3156 dst += 2; 3157 } 3158 xhdr->val_offset = dst - xhdr->buf; 3159 read_ctx->hbrc_out.state = XOUT_VALUE; 3160 read_ctx->hbrc_out.off = 0; 3161 return 0; 3162} 3163 3164 3165static int 3166header_out_begin_literal (struct lsqpack_dec *dec, 3167 struct header_block_read_ctx *read_ctx, size_t need, int is_never) 3168{ 3169 struct lsxpack_header *xhdr; /* Shorthand */ 3170 size_t http1x; 3171 3172 assert(!read_ctx->hbrc_out.xhdr); 3173 3174 http1x = !!(dec->qpd_opts & LSQPACK_DEC_OPT_HTTP1X) << 2; /* 0 or 4 */ 3175 need += http1x; 3176 read_ctx->hbrc_out.xhdr = xhdr = dec->qpd_dh_if->dhi_prepare_decode( 3177 read_ctx->hbrc_hblock, NULL, need); 3178 if (!xhdr) 3179 return -1; 3180 3181 xhdr->dec_overhead = http1x; 3182 if (is_never) 3183 xhdr->flags |= LSXPACK_NEVER_INDEX; 3184 read_ctx->hbrc_out.state = XOUT_NAME; 3185 read_ctx->hbrc_out.off = 0; 3186 return 0; 3187} 3188 3189 3190static int 3191header_out_write_name (struct lsqpack_dec *dec, 3192 struct header_block_read_ctx *read_ctx, size_t nwritten, int done) 3193{ 3194 struct lsxpack_header *xhdr; /* Shorthand */ 3195 3196 read_ctx->hbrc_out.off += nwritten; 3197 3198 if (done) 3199 { 3200 xhdr = read_ctx->hbrc_out.xhdr; 3201 if (dec->qpd_opts & LSQPACK_DEC_OPT_HTTP1X) 3202 { 3203 if (read_ctx->hbrc_out.off + 2 > xhdr->val_len) 3204 { 3205 read_ctx->hbrc_out.xhdr = xhdr = dec->qpd_dh_if 3206 ->dhi_prepare_decode(read_ctx->hbrc_hblock, xhdr, 3207 read_ctx->hbrc_out.off + 2); 3208 if (!xhdr) 3209 return -1; 3210 } 3211 memcpy(xhdr->buf + xhdr->name_offset + read_ctx->hbrc_out.off, 3212 ": ", 2); 3213 xhdr->val_offset = xhdr->name_offset + read_ctx->hbrc_out.off + 2; 3214 } 3215 else 3216 xhdr->val_offset = xhdr->name_offset + read_ctx->hbrc_out.off; 3217 xhdr->name_len = read_ctx->hbrc_out.off; 3218 read_ctx->hbrc_out.state = XOUT_VALUE; 3219 read_ctx->hbrc_out.off = 0; 3220 if (dec->qpd_opts & (LSQPACK_DEC_OPT_HASH_NAME 3221 |LSQPACK_DEC_OPT_HASH_NAMEVAL)) 3222 { 3223 xhdr->name_hash = XXH32(xhdr->buf + xhdr->name_offset, 3224 xhdr->name_len, LSQPACK_XXH_SEED); 3225 xhdr->flags |= LSXPACK_NAME_HASH; 3226 } 3227 } 3228 3229 return 0; 3230} 3231 3232 3233static int 3234header_out_write_value (struct lsqpack_dec *dec, 3235 struct header_block_read_ctx *read_ctx, size_t nwritten, int done) 3236{ 3237 struct lsxpack_header *xhdr; /* Shorthand */ 3238 int r; 3239 3240 read_ctx->hbrc_out.off += nwritten; 3241 3242 if (done) 3243 { 3244 xhdr = read_ctx->hbrc_out.xhdr; 3245 if (dec->qpd_opts & LSQPACK_DEC_OPT_HTTP1X) 3246 { 3247 if (xhdr->val_offset + read_ctx->hbrc_out.off + 2 > xhdr->val_len) 3248 { 3249 read_ctx->hbrc_out.xhdr = xhdr = dec->qpd_dh_if 3250 ->dhi_prepare_decode(read_ctx->hbrc_hblock, xhdr, 3251 xhdr->val_offset + read_ctx->hbrc_out.off + 2); 3252 if (!xhdr) 3253 return -1; 3254 } 3255 memcpy(xhdr->buf + xhdr->val_offset + read_ctx->hbrc_out.off, 3256 "\r\n", 2); 3257 } 3258 xhdr->val_len = read_ctx->hbrc_out.off; 3259 if (dec->qpd_opts & LSQPACK_DEC_OPT_HASH_NAME) 3260 { 3261 assert(xhdr->flags & LSXPACK_NAME_HASH); 3262 xhdr->nameval_hash = XXH32(xhdr->buf + xhdr->val_offset, 3263 xhdr->val_len, xhdr->name_hash); 3264 xhdr->flags |= LSXPACK_NAMEVAL_HASH; 3265 } 3266 r = dec->qpd_dh_if->dhi_process_header(read_ctx->hbrc_hblock, xhdr); 3267 if (r == 0) 3268 dec->qpd_bytes_out += xhdr->name_len + xhdr->val_len; 3269 ++read_ctx->hbrc_header_count; 3270 memset(&read_ctx->hbrc_out, 0, sizeof(read_ctx->hbrc_out)); 3271 if (r != 0) 3272 return -1; 3273 } 3274 3275 return 0; 3276} 3277 3278 3279static int 3280header_out_grow_buf (struct lsqpack_dec *dec, 3281 struct header_block_read_ctx *read_ctx) 3282{ 3283 size_t size, need; 3284 unsigned off; 3285 3286 assert(read_ctx->hbrc_out.xhdr); 3287 if (read_ctx->hbrc_out.state == XOUT_NAME) 3288 off = read_ctx->hbrc_out.off; 3289 else 3290 off = read_ctx->hbrc_out.xhdr->val_offset 3291 - read_ctx->hbrc_out.xhdr->name_offset + read_ctx->hbrc_out.off; 3292 3293 /* name_off and val_off are not set until the whole string has been 3294 * written. Thus, `size' represents the number of bytes that was 3295 * not enough to write either the name or the value. We multiply this 3296 * number by 1.5. 3297 */ 3298 assert(read_ctx->hbrc_out.xhdr->val_len >= off); 3299 size = read_ctx->hbrc_out.xhdr->val_len - off; 3300 if (size < 2) 3301 size = 2; 3302 need = read_ctx->hbrc_out.xhdr->val_len + size / 2; 3303 if (need > LSXPACK_MAX_STRLEN) 3304 need = LSXPACK_MAX_STRLEN; 3305 read_ctx->hbrc_out.xhdr = dec->qpd_dh_if->dhi_prepare_decode( 3306 read_ctx->hbrc_hblock, read_ctx->hbrc_out.xhdr, need); 3307 if (!read_ctx->hbrc_out.xhdr) 3308 return -1; 3309 if (read_ctx->hbrc_out.xhdr->val_len < need) 3310 { 3311 D_INFO("allocated xhdr size (%zd) is smaller than requested (%zd)", 3312 (size_t) read_ctx->hbrc_out.xhdr->val_len, need); 3313 memset(&read_ctx->hbrc_out, 0, sizeof(read_ctx->hbrc_out)); 3314 return -1; 3315 } 3316 return 0; 3317} 3318 3319 3320static int 3321guarantee_out_bytes (struct lsqpack_dec *dec, 3322 struct header_block_read_ctx *read_ctx, size_t extra) 3323{ 3324 size_t avail, need; 3325 unsigned off; 3326 3327 assert(read_ctx->hbrc_out.xhdr); 3328 assert(read_ctx->hbrc_out.state == XOUT_VALUE); 3329 assert(read_ctx->hbrc_out.xhdr->val_offset 3330 >= read_ctx->hbrc_out.xhdr->name_offset); 3331 off = read_ctx->hbrc_out.xhdr->val_offset 3332 - read_ctx->hbrc_out.xhdr->name_offset + read_ctx->hbrc_out.off; 3333 3334 assert(read_ctx->hbrc_out.xhdr->val_len >= off); 3335 avail = read_ctx->hbrc_out.xhdr->val_len - off; 3336 if (avail < extra) 3337 { 3338 need = read_ctx->hbrc_out.xhdr->val_len + extra - avail; 3339 read_ctx->hbrc_out.xhdr = dec->qpd_dh_if->dhi_prepare_decode( 3340 read_ctx->hbrc_hblock, read_ctx->hbrc_out.xhdr, need); 3341 if (!read_ctx->hbrc_out.xhdr) 3342 return -1; 3343 } 3344 return 0; 3345} 3346 3347 3348static unsigned char * 3349get_dst (struct lsqpack_dec *dec, 3350 struct header_block_read_ctx *read_ctx, size_t *dst_size) 3351{ 3352 unsigned off; 3353 3354 assert(read_ctx->hbrc_out.xhdr); 3355 if (read_ctx->hbrc_out.state == XOUT_NAME) 3356 off = read_ctx->hbrc_out.off; 3357 else 3358 off = read_ctx->hbrc_out.xhdr->val_offset 3359 - read_ctx->hbrc_out.xhdr->name_offset + read_ctx->hbrc_out.off; 3360 3361 assert(read_ctx->hbrc_out.xhdr->val_len >= off); 3362 *dst_size = read_ctx->hbrc_out.xhdr->val_len - off; 3363 return (unsigned char *) read_ctx->hbrc_out.xhdr->buf 3364 + read_ctx->hbrc_out.xhdr->name_offset + off; 3365} 3366 3367 3368static unsigned char * 3369qdec_huff_dec4bits (uint8_t, unsigned char *, struct lsqpack_decode_status *); 3370 3371 3372struct huff_decode_retval 3373{ 3374 enum 3375 { 3376 HUFF_DEC_OK, 3377 HUFF_DEC_END_SRC, 3378 HUFF_DEC_END_DST, 3379 HUFF_DEC_ERROR, 3380 } status; 3381 unsigned n_dst; 3382 unsigned n_src; 3383}; 3384 3385 3386#if LS_QPACK_USE_LARGE_TABLES 3387static struct huff_decode_retval 3388huff_decode_fast (const unsigned char *src, int src_len, 3389 unsigned char *dst, int dst_len, 3390 struct lsqpack_huff_decode_state *state, int final); 3391#else 3392#define lsqpack_huff_decode_full lsqpack_huff_decode 3393#endif 3394 3395struct huff_decode_retval 3396lsqpack_huff_decode_full (const unsigned char *src, int src_len, 3397 unsigned char *dst, int dst_len, 3398 struct lsqpack_huff_decode_state *state, int final) 3399{ 3400 const unsigned char *p_src = src; 3401 const unsigned char *const src_end = src + src_len; 3402 unsigned char *p_dst = dst; 3403 unsigned char *dst_end = dst + dst_len; 3404 3405 if (dst_len == 0) 3406 return (struct huff_decode_retval) { 3407 .status = HUFF_DEC_END_DST, 3408 .n_dst = 0, 3409 .n_src = 0, 3410 }; 3411 3412 switch (state->resume) 3413 { 3414 case 0: 3415 state->status.state = 0; 3416 state->status.eos = 1; 3417 case 1: 3418 while (p_src != src_end) 3419 { 3420 if (p_dst == dst_end) 3421 { 3422 state->resume = 2; 3423 return (const struct huff_decode_retval) { 3424 .status = HUFF_DEC_END_DST, 3425 .n_dst = dst_len, 3426 .n_src = p_src - src, 3427 }; 3428 } 3429 case 2: 3430 if ((p_dst = qdec_huff_dec4bits(*p_src >> 4, p_dst, &state->status)) 3431 == NULL) 3432 return (struct huff_decode_retval) { 3433 .status = HUFF_DEC_ERROR, }; 3434 if (p_dst == dst_end) 3435 { 3436 state->resume = 3; 3437 return (struct huff_decode_retval) { 3438 .status = HUFF_DEC_END_DST, 3439 .n_dst = dst_len, 3440 .n_src = p_src - src, 3441 }; 3442 } 3443 case 3: 3444 if ((p_dst = qdec_huff_dec4bits(*p_src & 0xf, p_dst, &state->status)) 3445 == NULL) 3446 return (struct huff_decode_retval) { .status = HUFF_DEC_ERROR, }; 3447 ++p_src; 3448 } 3449 } 3450 3451 if (final) 3452 return (struct huff_decode_retval) { 3453 .status = state->status.eos ? HUFF_DEC_OK : HUFF_DEC_ERROR, 3454 .n_dst = p_dst - dst, 3455 .n_src = p_src - src, 3456 }; 3457 else 3458 { 3459 state->resume = 1; 3460 return (struct huff_decode_retval) { 3461 .status = HUFF_DEC_END_SRC, 3462 .n_dst = p_dst - dst, 3463 .n_src = p_src - src, 3464 }; 3465 } 3466} 3467 3468 3469#if LS_QPACK_USE_LARGE_TABLES 3470static struct huff_decode_retval 3471lsqpack_huff_decode (const unsigned char *src, int src_len, 3472 unsigned char *dst, int dst_len, 3473 struct lsqpack_huff_decode_state *state, int final) 3474{ 3475 if (state->resume == 0 && final) 3476 return huff_decode_fast(src, src_len, dst, dst_len, state, final); 3477 else 3478 return lsqpack_huff_decode_full(src, src_len, dst, dst_len, state, 3479 final); 3480} 3481#endif 3482 3483 3484static void 3485check_dyn_table_errors (struct header_block_read_ctx *read_ctx, 3486 lsqpack_abs_id_t id) 3487{ 3488 if (read_ctx->hbrc_flags & HBRC_LARGEST_REF_SET) 3489 read_ctx->hbrc_flags |= 3490 (id == read_ctx->hbrc_largest_ref) << LARGEST_USED_SHIFT; 3491 else 3492 read_ctx->hbrc_flags |= HBRC_DYN_USED_IN_ERR; 3493} 3494 3495 3496static enum lsqpack_read_header_status 3497parse_header_data (struct lsqpack_dec *dec, 3498 struct header_block_read_ctx *read_ctx, const unsigned char *buf, 3499 size_t bufsz) 3500{ 3501#define DATA read_ctx->hbrc_parse_ctx_u.data 3502 const unsigned char *const end = buf + bufsz; 3503 struct lsqpack_dec_table_entry *entry; 3504 struct huff_decode_retval hdr; 3505 unsigned value; 3506 size_t size, dst_size; 3507 unsigned char *dst; 3508 unsigned prefix_bits = ~0u; 3509 int r; 3510 3511#define RETURN_ERROR() do { dec->qpd_err.line = __LINE__; goto err; } while (0) 3512 3513 while (buf < end) 3514 { 3515 switch (DATA.state) 3516 { 3517 case DATA_STATE_NEXT_INSTRUCTION: 3518 if (buf[0] & 0x80) 3519 { 3520 prefix_bits = 6; 3521 DATA.is_static = buf[0] & 0x40; 3522 DATA.dec_int_state.resume = 0; 3523 DATA.state = DATA_STATE_READ_IHF_IDX; 3524 goto data_state_read_ihf_idx; 3525 } 3526 /* Literal Header Field With Name Reference */ 3527 else if (buf[0] & 0x40) 3528 { 3529 prefix_bits = 4; 3530 DATA.is_never = buf[0] & 0x20; 3531 DATA.is_static = buf[0] & 0x10; 3532 DATA.dec_int_state.resume = 0; 3533 DATA.state = DATA_STATE_READ_LFINR_IDX; 3534 goto data_state_read_lfinr_idx; 3535 } 3536 /* Literal Header Field Without Name Reference */ 3537 else if (buf[0] & 0x20) 3538 { 3539 prefix_bits = 3; 3540 DATA.is_never = buf[0] & 0x10; 3541 DATA.is_huffman = buf[0] & 0x08; 3542 DATA.dec_int_state.resume = 0; 3543 DATA.state = DATA_STATE_READ_LFONR_NAME_LEN; 3544 goto data_state_read_lfonr_name_len; 3545 } 3546 /* Indexed Header Field With Post-Base Index */ 3547 else if (buf[0] & 0x10) 3548 { 3549 prefix_bits = 4; 3550 DATA.dec_int_state.resume = 0; 3551 DATA.state = DATA_STATE_READ_IPBI_IDX; 3552 goto data_state_read_ipbi_idx; 3553 } 3554 /* Literal Header Field With Post-Base Name Reference */ 3555 else 3556 { 3557 prefix_bits = 3; 3558 DATA.is_never = buf[0] & 0x08; 3559 DATA.dec_int_state.resume = 0; 3560 DATA.state = DATA_STATE_READ_LFPBNR_IDX; 3561 goto data_state_read_lfpbnr_idx; 3562 } 3563 case DATA_STATE_READ_IHF_IDX: 3564 data_state_read_ihf_idx: 3565 r = lsqpack_dec_int24(&buf, end, prefix_bits, &value, 3566 &DATA.dec_int_state); 3567 if (r == 0) 3568 { 3569 if (DATA.is_static) 3570 r = header_out_static_entry(dec, read_ctx, value); 3571 else 3572 { 3573 value = ID_MINUS(read_ctx->hbrc_base_index, value); 3574 r = header_out_dynamic_entry(dec, read_ctx, value); 3575 check_dyn_table_errors(read_ctx, value); 3576 } 3577 if (r == 0) 3578 DATA.state = DATA_STATE_NEXT_INSTRUCTION; 3579 else 3580 RETURN_ERROR(); 3581 } 3582 else if (r == -1) 3583 return LQRHS_NEED; 3584 else 3585 RETURN_ERROR(); 3586 break; 3587 case DATA_STATE_READ_LFINR_IDX: 3588 data_state_read_lfinr_idx: 3589 r = lsqpack_dec_int24(&buf, end, prefix_bits, &value, 3590 &DATA.dec_int_state); 3591 if (r == 0) 3592 { 3593 if (DATA.is_static) 3594 { 3595 if (0 != header_out_begin_static_nameref(dec, 3596 read_ctx, value, DATA.is_never)) 3597 RETURN_ERROR(); 3598 } 3599 else 3600 { 3601 value = ID_MINUS(read_ctx->hbrc_base_index, value); 3602 entry = qdec_get_table_entry_abs(dec, value); 3603 if (!entry) 3604 RETURN_ERROR(); 3605 check_dyn_table_errors(read_ctx, value); 3606 if (0 != header_out_begin_dynamic_nameref(dec, 3607 read_ctx, entry, DATA.is_never)) 3608 RETURN_ERROR(); 3609 } 3610 DATA.state = DATA_STATE_BEGIN_READ_VAL_LEN; 3611 break; 3612 } 3613 else if (r == -1) 3614 return LQRHS_NEED; 3615 else 3616 RETURN_ERROR(); 3617 case DATA_STATE_BEGIN_READ_VAL_LEN: 3618 DATA.is_huffman = buf[0] & 0x80; 3619 prefix_bits = 7; 3620 DATA.dec_int_state.resume = 0; 3621 DATA.state = DATA_STATE_READ_VAL_LEN; 3622 /* Fall-through */ 3623 case DATA_STATE_READ_VAL_LEN: 3624 r = lsqpack_dec_int24(&buf, end, prefix_bits, &DATA.left, 3625 &DATA.dec_int_state); 3626 if (r == 0) 3627 { 3628 if (DATA.left) 3629 { 3630 if (DATA.is_huffman) 3631 { 3632 if (0 != guarantee_out_bytes(dec, read_ctx, 3633 DATA.left + DATA.left / 2)) 3634 RETURN_ERROR(); 3635 DATA.dec_huff_state.resume = 0; 3636 DATA.state = DATA_STATE_READ_VAL_HUFFMAN; 3637 } 3638 else 3639 { 3640 if (0 != guarantee_out_bytes(dec, read_ctx, DATA.left)) 3641 RETURN_ERROR(); 3642 DATA.state = DATA_STATE_READ_VAL_PLAIN; 3643 } 3644 } 3645 else if (0 == header_out_write_value(dec, read_ctx, 0, 1)) 3646 DATA.state = DATA_STATE_NEXT_INSTRUCTION; 3647 else 3648 RETURN_ERROR(); 3649 } 3650 else if (r == -1) 3651 return LQRHS_NEED; 3652 else 3653 RETURN_ERROR(); 3654 break; 3655 case DATA_STATE_READ_VAL_HUFFMAN: 3656 size = MIN((unsigned) (end - buf), DATA.left); 3657 if (size == 0) 3658 RETURN_ERROR(); 3659 dst = get_dst(dec, read_ctx, &dst_size); 3660 hdr = lsqpack_huff_decode(buf, size, dst, dst_size, 3661 &DATA.dec_huff_state, DATA.left == size); 3662 buf += hdr.n_src; 3663 DATA.left -= hdr.n_src; 3664 switch (hdr.status) 3665 { 3666 case HUFF_DEC_OK: 3667 if (0 != header_out_write_value(dec, read_ctx, hdr.n_dst, 3668 DATA.left == 0)) 3669 RETURN_ERROR(); 3670 if (DATA.left == 0) 3671 DATA.state = DATA_STATE_NEXT_INSTRUCTION; 3672 break; 3673 case HUFF_DEC_END_SRC: 3674 if (hdr.n_dst && 0 != header_out_write_value(dec, read_ctx, 3675 hdr.n_dst, 0)) 3676 RETURN_ERROR(); 3677 break; 3678 case HUFF_DEC_END_DST: 3679 if (hdr.n_dst && 0 != header_out_write_value(dec, read_ctx, 3680 hdr.n_dst, 0)) 3681 RETURN_ERROR(); 3682 if (0 != header_out_grow_buf(dec, read_ctx)) 3683 RETURN_ERROR(); 3684 break; 3685 default: 3686 RETURN_ERROR(); 3687 } 3688 break; 3689 case DATA_STATE_READ_VAL_PLAIN: 3690 size = MIN((unsigned) (end - buf), DATA.left); 3691 if (size == 0) 3692 RETURN_ERROR(); 3693 dst = get_dst(dec, read_ctx, &dst_size); 3694 if (size > dst_size) 3695 RETURN_ERROR(); 3696 memcpy(dst, buf, size); 3697 if (0 != header_out_write_value(dec, read_ctx, 3698 size, DATA.left == size)) 3699 RETURN_ERROR(); 3700 DATA.left -= size; 3701 buf += size; 3702 if (DATA.left == 0) 3703 DATA.state = DATA_STATE_NEXT_INSTRUCTION; 3704 break; 3705 case DATA_STATE_READ_LFONR_NAME_LEN: 3706 data_state_read_lfonr_name_len: 3707 r = lsqpack_dec_int24(&buf, end, prefix_bits, &DATA.left, 3708 &DATA.dec_int_state); 3709 if (r == 0) 3710 { 3711 size = DATA.is_huffman ? DATA.left + DATA.left / 2 : DATA.left; 3712 if (0 != header_out_begin_literal(dec, read_ctx, size, 3713 DATA.is_never)) 3714 RETURN_ERROR(); 3715 if (DATA.is_huffman) 3716 { 3717 DATA.dec_huff_state.resume = 0; 3718 DATA.state = DATA_STATE_READ_NAME_HUFFMAN; 3719 } 3720 else 3721 DATA.state = DATA_STATE_READ_NAME_PLAIN; 3722 } 3723 else if (r == -1) 3724 return LQRHS_NEED; 3725 else 3726 RETURN_ERROR(); 3727 break; 3728 case DATA_STATE_READ_NAME_HUFFMAN: 3729 size = MIN((unsigned) (end - buf), DATA.left); 3730 if (size == 0) 3731 RETURN_ERROR(); 3732 dst = get_dst(dec, read_ctx, &dst_size); 3733 hdr = lsqpack_huff_decode(buf, size, dst, dst_size, 3734 &DATA.dec_huff_state, DATA.left == size); 3735 buf += hdr.n_src; 3736 DATA.left -= hdr.n_src; 3737 switch (hdr.status) 3738 { 3739 case HUFF_DEC_OK: 3740 if (0 != header_out_write_name(dec, read_ctx, hdr.n_dst, 3741 DATA.left == 0)) 3742 RETURN_ERROR(); 3743 if (DATA.left == 0) 3744 DATA.state = DATA_STATE_BEGIN_READ_VAL_LEN; 3745 break; 3746 case HUFF_DEC_END_SRC: 3747 if (hdr.n_dst && 0 != header_out_write_name(dec, read_ctx, 3748 hdr.n_dst, 0)) 3749 RETURN_ERROR(); 3750 break; 3751 case HUFF_DEC_END_DST: 3752 if (hdr.n_dst && 0 != header_out_write_name(dec, read_ctx, 3753 hdr.n_dst, 0)) 3754 RETURN_ERROR(); 3755 if (0 != header_out_grow_buf(dec, read_ctx)) 3756 RETURN_ERROR(); 3757 break; 3758 default: 3759 RETURN_ERROR(); 3760 } 3761 break; 3762 case DATA_STATE_READ_NAME_PLAIN: 3763 size = MIN((unsigned) (end - buf), DATA.left); 3764 if (size == 0) 3765 RETURN_ERROR(); 3766 dst = get_dst(dec, read_ctx, &dst_size); 3767 if (size > dst_size) 3768 RETURN_ERROR(); 3769 memcpy(dst, buf, size); 3770 if (0 != header_out_write_name(dec, read_ctx, 3771 size, DATA.left == size)) 3772 RETURN_ERROR(); 3773 DATA.left -= size; 3774 buf += size; 3775 if (DATA.left == 0) 3776 DATA.state = DATA_STATE_BEGIN_READ_VAL_LEN; 3777 break; 3778 case DATA_STATE_READ_LFPBNR_IDX: 3779 data_state_read_lfpbnr_idx: 3780 r = lsqpack_dec_int24(&buf, end, prefix_bits, &value, 3781 &DATA.dec_int_state); 3782 if (r == 0) 3783 { 3784 value = ID_PLUS(value, read_ctx->hbrc_base_index + 1); 3785 entry = qdec_get_table_entry_abs(dec, value); 3786 if (!entry) 3787 RETURN_ERROR(); 3788 check_dyn_table_errors(read_ctx, value); 3789 if (0 != header_out_begin_dynamic_nameref(dec, 3790 read_ctx, entry, DATA.is_never)) 3791 RETURN_ERROR(); 3792 DATA.state = DATA_STATE_BEGIN_READ_VAL_LEN; 3793 } 3794 else if (r == -1) 3795 return LQRHS_NEED; 3796 else 3797 RETURN_ERROR(); 3798 break; 3799 case DATA_STATE_READ_IPBI_IDX: 3800 data_state_read_ipbi_idx: 3801 r = lsqpack_dec_int24(&buf, end, prefix_bits, &value, 3802 &DATA.dec_int_state); 3803 if (r == 0) 3804 { 3805 value = ID_PLUS(read_ctx->hbrc_base_index, value + 1); 3806 r = header_out_dynamic_entry(dec, read_ctx, value); 3807 check_dyn_table_errors(read_ctx, value); 3808 if (r == 0) 3809 DATA.state = DATA_STATE_NEXT_INSTRUCTION; 3810 else 3811 RETURN_ERROR(); 3812 } 3813 else if (r == -1) 3814 return LQRHS_NEED; 3815 else 3816 RETURN_ERROR(); 3817 break; 3818 default: 3819 assert(0); 3820 RETURN_ERROR(); 3821 } 3822 } 3823 3824 if (read_ctx->hbrc_size > 0) 3825 return LQRHS_NEED; 3826 else if (DATA.state == DATA_STATE_NEXT_INSTRUCTION) { 3827 if ((read_ctx->hbrc_flags 3828 & (HBRC_LARGEST_REF_SET|HBRC_LARGEST_REF_USED)) 3829 == HBRC_LARGEST_REF_SET) 3830 RETURN_ERROR(); 3831 if (read_ctx->hbrc_flags & HBRC_DYN_USED_IN_ERR) 3832 RETURN_ERROR(); 3833 return LQRHS_DONE; 3834 } 3835 else 3836 RETURN_ERROR(); 3837 3838 err: 3839 dec->qpd_err.type = LSQPACK_DEC_ERR_LOC_HEADER_BLOCK; 3840 dec->qpd_err.off = read_ctx->hbrc_orig_size - read_ctx->hbrc_size 3841 + (buf - (end - bufsz)); 3842 dec->qpd_err.stream_id = read_ctx->hbrc_stream_id; 3843 D_DEBUG("header block error on line %d, offset %"PRIu64", stream id " 3844 "%"PRIu64, dec->qpd_err.line, dec->qpd_err.off, dec->qpd_err.stream_id); 3845 return LQRHS_ERROR; 3846#undef DATA 3847} 3848 3849 3850static int 3851qdec_in_future (const struct lsqpack_dec *dec, lsqpack_abs_id_t id) 3852{ 3853 if (dec->qpd_last_id < dec->qpd_max_entries) 3854 return id > dec->qpd_last_id 3855 && id <= dec->qpd_last_id + dec->qpd_max_entries; 3856 else 3857 return !(id <= dec->qpd_last_id 3858 && id >= dec->qpd_last_id - dec->qpd_max_entries + 1); 3859} 3860 3861 3862/* 3863 * [draft-ietf-quic-qpack-09], Section 4.5.1.1: 3864 * 3865 * The encoder transforms the Required Insert Count as follows before 3866 * encoding: 3867 * 3868 * if ReqInsertCount == 0: 3869 * EncInsertCount = 0 3870 * else: 3871 * EncInsertCount = (ReqInsertCount mod (2 * MaxEntries)) + 1 3872 */ 3873static lsqpack_abs_id_t 3874dec_max_encoded_RIC (const struct lsqpack_dec *dec) 3875{ 3876 return dec->qpd_max_entries * 2; 3877} 3878 3879 3880static enum lsqpack_read_header_status 3881parse_header_prefix (struct lsqpack_dec *dec, 3882 struct header_block_read_ctx *read_ctx, const unsigned char *buf, 3883 size_t bufsz) 3884{ 3885 const unsigned char *const end = buf + bufsz; 3886 unsigned prefix_bits = ~0u; 3887 int r; 3888 3889#define RIC read_ctx->hbrc_parse_ctx_u.prefix.u.ric 3890#define DELB read_ctx->hbrc_parse_ctx_u.prefix.u.delb 3891 3892 while (buf < end) 3893 { 3894 switch (read_ctx->hbrc_parse_ctx_u.prefix.state) 3895 { 3896 case PREFIX_STATE_BEGIN_READING_LARGEST_REF: 3897 prefix_bits = 8; 3898 DELB.dec_int_state.resume = 0; 3899 read_ctx->hbrc_parse_ctx_u.prefix.state = 3900 PREFIX_STATE_READ_LARGEST_REF; 3901 /* Fall-through */ 3902 case PREFIX_STATE_READ_LARGEST_REF: 3903 r = lsqpack_dec_int(&buf, end, prefix_bits, &RIC.value, 3904 &RIC.dec_int_state); 3905 if (r == 0) 3906 { 3907 if (RIC.value) 3908 { 3909 if (RIC.value > dec_max_encoded_RIC(dec)) 3910 return LQRHS_ERROR; 3911 read_ctx->hbrc_largest_ref = ID_MINUS(RIC.value, 2); 3912 read_ctx->hbrc_flags |= 3913 HBRC_LARGEST_REF_READ|HBRC_LARGEST_REF_SET; 3914 read_ctx->hbrc_parse_ctx_u.prefix.state 3915 = PREFIX_STATE_BEGIN_READING_BASE_IDX; 3916 if (qdec_in_future(dec, read_ctx->hbrc_largest_ref)) 3917 return LQRHS_BLOCKED; 3918 else 3919 break; 3920 } 3921 else 3922 { 3923 read_ctx->hbrc_flags |= HBRC_LARGEST_REF_READ; 3924 read_ctx->hbrc_parse_ctx_u.prefix.state 3925 = PREFIX_STATE_BEGIN_READING_BASE_IDX; 3926 break; 3927 } 3928 } 3929 else if (r == -1) 3930 { 3931 if (read_ctx->hbrc_orig_size - read_ctx->hbrc_size 3932 <= lsqpack_val2len(dec_max_encoded_RIC(dec), 8)) 3933 return LQRHS_NEED; 3934 else 3935 return LQRHS_ERROR; 3936 } 3937 else 3938 return LQRHS_ERROR; 3939 case PREFIX_STATE_BEGIN_READING_BASE_IDX: 3940 DELB.sign = (buf[0] & 0x80) > 0; 3941 DELB.dec_int_state.resume = 0; 3942 prefix_bits = 7; 3943 read_ctx->hbrc_parse_ctx_u.prefix.state = 3944 PREFIX_STATE_READ_DELTA_BASE_IDX; 3945 /* Fall-through */ 3946 case PREFIX_STATE_READ_DELTA_BASE_IDX: 3947 r = lsqpack_dec_int(&buf, end, prefix_bits, &DELB.value, 3948 &DELB.dec_int_state); 3949 if (r == 0) 3950 { 3951 if (read_ctx->hbrc_flags & HBRC_LARGEST_REF_SET) 3952 { 3953 if (DELB.sign) 3954 read_ctx->hbrc_base_index = 3955 ID_MINUS(read_ctx->hbrc_largest_ref, DELB.value + 1); 3956 else 3957 read_ctx->hbrc_base_index = 3958 ID_PLUS(read_ctx->hbrc_largest_ref, DELB.value); 3959 } 3960 else /* From qpack-03: "A header block that does not 3961 * reference the dynamic table can use any value 3962 * for Base Index" 3963 */ 3964 read_ctx->hbrc_base_index = 0; 3965 read_ctx->hbrc_parse = parse_header_data; 3966 read_ctx->hbrc_parse_ctx_u.data.state 3967 = DATA_STATE_NEXT_INSTRUCTION; 3968 if (end - buf) 3969 return parse_header_data(dec, read_ctx, buf, end - buf); 3970 else 3971 return LQRHS_NEED; 3972 } 3973 else if (r == -1) 3974 { 3975 return LQRHS_NEED; 3976 } 3977 else 3978 return LQRHS_ERROR; 3979 default: 3980 assert(0); 3981 return LQRHS_ERROR; 3982 } 3983 } 3984 3985#undef RIC 3986#undef DELB 3987 3988 if (read_ctx->hbrc_size > 0) 3989 return LQRHS_NEED; 3990 else 3991 return LQRHS_ERROR; 3992} 3993 3994 3995static size_t 3996max_to_read (const struct header_block_read_ctx *read_ctx) 3997{ 3998 if (read_ctx->hbrc_flags & HBRC_LARGEST_REF_READ) 3999 return read_ctx->hbrc_size; 4000 else 4001 return 1; 4002} 4003 4004 4005static size_t 4006qdec_read_header_block (struct hbrc_buf *hbrc_buf, 4007 const unsigned char **buf, size_t sz) 4008{ 4009 if (sz > hbrc_buf->sz - hbrc_buf->off) 4010 sz = hbrc_buf->sz - hbrc_buf->off; 4011 *buf = hbrc_buf->buf + hbrc_buf->off; 4012 hbrc_buf->off += sz; 4013 return sz; 4014} 4015 4016 4017static enum lsqpack_read_header_status 4018qdec_read_header (struct lsqpack_dec *dec, 4019 struct header_block_read_ctx *read_ctx) 4020{ 4021 const unsigned char *buf; 4022 enum lsqpack_read_header_status st; 4023 size_t n_to_read; 4024 size_t buf_sz; 4025 4026 while (read_ctx->hbrc_size > 0) 4027 { 4028 n_to_read = max_to_read(read_ctx); 4029 buf_sz = qdec_read_header_block(&read_ctx->hbrc_buf, &buf, n_to_read); 4030 if (buf_sz > 0) 4031 { 4032 read_ctx->hbrc_size -= buf_sz; 4033 st = read_ctx->hbrc_parse(dec, read_ctx, buf, buf_sz); 4034 if (st == LQRHS_NEED) 4035 { 4036 if (read_ctx->hbrc_size == 0) 4037 return LQRHS_ERROR; 4038 } 4039 else 4040 return st; 4041 } 4042 else 4043 return LQRHS_NEED; 4044 } 4045 4046 return LQRHS_DONE; 4047} 4048 4049 4050static void 4051destroy_header_block_read_ctx (struct lsqpack_dec *dec, 4052 struct header_block_read_ctx *read_ctx) 4053{ 4054 lsqpack_abs_id_t id; 4055 4056 TAILQ_REMOVE(&dec->qpd_hbrcs, read_ctx, hbrc_next_all); 4057 if (read_ctx->hbrc_flags & HBRC_BLOCKED) 4058 { 4059 id = read_ctx->hbrc_largest_ref & ((1 << LSQPACK_DEC_BLOCKED_BITS) - 1); 4060 TAILQ_REMOVE(&dec->qpd_blocked_headers[id], read_ctx, hbrc_next_blocked); 4061 --dec->qpd_n_blocked; 4062 } 4063 free(read_ctx); 4064} 4065 4066 4067static void 4068qdec_insert_header_block (struct lsqpack_dec *dec, 4069 struct header_block_read_ctx *read_ctx) 4070{ 4071 TAILQ_INSERT_TAIL(&dec->qpd_hbrcs, read_ctx, hbrc_next_all); 4072 read_ctx->hbrc_flags |= HBRC_ON_LIST; 4073} 4074 4075 4076static void 4077qdec_remove_header_block (struct lsqpack_dec *dec, 4078 struct header_block_read_ctx *read_ctx) 4079{ 4080 TAILQ_REMOVE(&dec->qpd_hbrcs, read_ctx, hbrc_next_all); 4081 read_ctx->hbrc_flags &= ~HBRC_ON_LIST; 4082} 4083 4084 4085static int 4086stash_blocked_header (struct lsqpack_dec *dec, 4087 struct header_block_read_ctx *read_ctx) 4088{ 4089 lsqpack_abs_id_t id; 4090 4091 if (dec->qpd_n_blocked < dec->qpd_max_risked_streams) 4092 { 4093 id = read_ctx->hbrc_largest_ref & ((1 << LSQPACK_DEC_BLOCKED_BITS) - 1); 4094 TAILQ_INSERT_TAIL(&dec->qpd_blocked_headers[id], read_ctx, hbrc_next_blocked); 4095 ++dec->qpd_n_blocked; 4096 read_ctx->hbrc_flags |= HBRC_BLOCKED; 4097 return 0; 4098 } 4099 else 4100 { 4101 D_INFO("cannot block another header: reached maximum of %u", 4102 dec->qpd_max_risked_streams); 4103 return -1; 4104 } 4105} 4106 4107 4108static struct header_block_read_ctx * 4109find_header_block_read_ctx (struct lsqpack_dec *dec, void *hblock) 4110{ 4111 struct header_block_read_ctx *read_ctx; 4112 4113 TAILQ_FOREACH(read_ctx, &dec->qpd_hbrcs, hbrc_next_all) 4114 if (read_ctx->hbrc_hblock == hblock) 4115 return read_ctx; 4116 4117 return NULL; 4118} 4119 4120 4121static int 4122qdec_try_writing_header_ack (struct lsqpack_dec *dec, uint64_t stream_id, 4123 unsigned char *dec_buf, size_t *dec_buf_sz) 4124{ 4125 unsigned char *p = dec_buf; 4126 4127 if (*dec_buf_sz > 0) 4128 { 4129 *dec_buf = 0x80; 4130 p = lsqpack_enc_int(p, p + *dec_buf_sz, stream_id, 7); 4131 if (p > dec_buf) 4132 { 4133 *dec_buf_sz = p - dec_buf; 4134 dec->qpd_bytes_in += p - dec_buf; 4135 return 0; 4136 } 4137 } 4138 4139 return -1; 4140} 4141 4142 4143static void 4144qdec_maybe_update_largest_known (struct lsqpack_dec *dec, lsqpack_abs_id_t id) 4145{ 4146 lsqpack_abs_id_t diff; 4147 4148 diff = ID_MINUS(id, dec->qpd_largest_known_id); 4149 if (diff > 0 && diff <= dec->qpd_max_entries) 4150 dec->qpd_largest_known_id = id; 4151} 4152 4153 4154static enum lsqpack_read_header_status 4155qdec_header_process (struct lsqpack_dec *dec, 4156 struct header_block_read_ctx *read_ctx, 4157 const unsigned char **buf, size_t bufsz, 4158 unsigned char *dec_buf, size_t *dec_buf_sz) 4159{ 4160 struct header_block_read_ctx *read_ctx_copy; 4161 enum lsqpack_read_header_status st; 4162 4163 read_ctx->hbrc_buf = (struct hbrc_buf) { *buf, bufsz, 0, }; 4164 st = qdec_read_header(dec, read_ctx); 4165 switch (st) 4166 { 4167 case LQRHS_DONE: 4168 update_ema(&dec->qpd_hlist_size_ema, read_ctx->hbrc_header_count); 4169 if ((read_ctx->hbrc_flags & HBRC_LARGEST_REF_SET) 4170 && dec_buf && dec_buf_sz) 4171 { 4172 if (0 == qdec_try_writing_header_ack(dec, read_ctx->hbrc_stream_id, 4173 dec_buf, dec_buf_sz)) 4174 qdec_maybe_update_largest_known(dec, 4175 read_ctx->hbrc_largest_ref); 4176 else 4177 { 4178 st = LQRHS_ERROR; 4179 break; 4180 } 4181 } 4182 else if (dec_buf_sz) 4183 *dec_buf_sz = 0; 4184 *buf = *buf + read_ctx->hbrc_buf.off; 4185 dec->qpd_bytes_in += read_ctx->hbrc_orig_size; 4186 if (dec->qpd_bytes_out > (1u << (sizeof(dec->qpd_bytes_out) * 8 - 1))) 4187 { 4188 dec->qpd_bytes_in = (float) dec->qpd_bytes_in 4189 / (float) dec->qpd_bytes_out * 1000; 4190 dec->qpd_bytes_out = 1000; 4191 D_DEBUG("reset bytes in/out counters, ratio: %.3f", 4192 lsqpack_dec_ratio(dec)); 4193 } 4194 D_DEBUG("header block for stream %"PRIu64" is done", 4195 read_ctx->hbrc_stream_id); 4196 break; 4197 case LQRHS_NEED: 4198 case LQRHS_BLOCKED: 4199 if (!(read_ctx->hbrc_flags & HBRC_ON_LIST)) 4200 { 4201 read_ctx_copy = malloc(sizeof(*read_ctx_copy)); 4202 if (!read_ctx_copy) 4203 { 4204 st = LQRHS_ERROR; 4205 break; 4206 } 4207 memcpy(read_ctx_copy, read_ctx, sizeof(*read_ctx)); 4208 read_ctx = read_ctx_copy; 4209 qdec_insert_header_block(dec, read_ctx); 4210 } 4211 if (st == LQRHS_BLOCKED && 0 != stash_blocked_header(dec, read_ctx)) 4212 { 4213 st = LQRHS_ERROR; 4214 break; 4215 } 4216 *buf = *buf + read_ctx->hbrc_buf.off; 4217 if (st == LQRHS_NEED) 4218 D_DEBUG("header block for stream %"PRIu64" needs more bytes", 4219 read_ctx->hbrc_stream_id); 4220 else 4221 D_DEBUG("header block for stream %"PRIu64" is blocked", 4222 read_ctx->hbrc_stream_id); 4223 return st; 4224 default: 4225 assert(st == LQRHS_ERROR); 4226 D_DEBUG("header block for stream %"PRIu64" has had an error", 4227 read_ctx->hbrc_stream_id); 4228 break; 4229 } 4230 4231 if (read_ctx->hbrc_flags & HBRC_ON_LIST) 4232 { 4233 qdec_remove_header_block(dec, read_ctx); 4234 free(read_ctx); 4235 } 4236 4237 return st; 4238} 4239 4240 4241enum lsqpack_read_header_status 4242lsqpack_dec_header_read (struct lsqpack_dec *dec, void *hblock, 4243 const unsigned char **buf, size_t bufsz, 4244 unsigned char *dec_buf, size_t *dec_buf_sz) 4245{ 4246 struct header_block_read_ctx *read_ctx; 4247 4248 read_ctx = find_header_block_read_ctx(dec, hblock); 4249 if (read_ctx) 4250 { 4251 D_DEBUG("continue reading header block for stream %"PRIu64, 4252 read_ctx->hbrc_stream_id); 4253 return qdec_header_process(dec, read_ctx, buf, bufsz, 4254 dec_buf, dec_buf_sz); 4255 } 4256 else 4257 { 4258 D_INFO("could not find header block to continue reading"); 4259 return LQRHS_ERROR; 4260 } 4261} 4262 4263 4264enum lsqpack_read_header_status 4265lsqpack_dec_header_in (struct lsqpack_dec *dec, void *hblock, 4266 uint64_t stream_id, size_t header_size, const unsigned char **buf, 4267 size_t bufsz, unsigned char *dec_buf, size_t *dec_buf_sz) 4268{ 4269 if (header_size < 2) 4270 { 4271 D_DEBUG("header block for stream %"PRIu64" is too short " 4272 "(%zd byte%.*s)", stream_id, header_size, header_size != 1, "s"); 4273 dec->qpd_err = (struct lsqpack_dec_err) { 4274 .line = __LINE__, 4275 .type = LSQPACK_DEC_ERR_LOC_HEADER_BLOCK, 4276 .off = 0, 4277 .stream_id = stream_id, 4278 }; 4279 return LQRHS_ERROR; 4280 } 4281 4282 struct header_block_read_ctx read_ctx = { 4283 .hbrc_stream_id = stream_id, 4284 .hbrc_hblock = hblock, 4285 .hbrc_size = header_size, 4286 .hbrc_orig_size = header_size, 4287 .hbrc_parse = parse_header_prefix, 4288 }; 4289 4290 D_DEBUG("begin reading header block for stream %"PRIu64, stream_id); 4291 return qdec_header_process(dec, &read_ctx, buf, bufsz, 4292 dec_buf, dec_buf_sz); 4293} 4294 4295 4296static void 4297qdec_drop_oldest_entry (struct lsqpack_dec *dec) 4298{ 4299 struct lsqpack_dec_table_entry *entry; 4300 4301 entry = ringbuf_advance_tail(&dec->qpd_dyn_table); 4302 dec->qpd_cur_capacity -= DTE_SIZE(entry); 4303 qdec_decref_entry(entry); 4304} 4305 4306 4307static void 4308qdec_remove_overflow_entries (struct lsqpack_dec *dec) 4309{ 4310 while (dec->qpd_cur_capacity > dec->qpd_cur_max_capacity) 4311 { 4312 D_DEBUG("capacity %u, drop entry", dec->qpd_cur_capacity); 4313 qdec_drop_oldest_entry(dec); 4314 } 4315} 4316 4317 4318static void 4319qdec_update_max_capacity (struct lsqpack_dec *dec, unsigned new_capacity) 4320{ 4321 dec->qpd_cur_max_capacity = new_capacity; 4322 qdec_remove_overflow_entries(dec); 4323} 4324 4325 4326static void 4327qdec_process_blocked_headers (struct lsqpack_dec *dec) 4328{ 4329 struct header_block_read_ctx *read_ctx, *next; 4330 lsqpack_abs_id_t id; 4331 4332 id = dec->qpd_last_id & ((1 << LSQPACK_DEC_BLOCKED_BITS) - 1); 4333 for (read_ctx = TAILQ_FIRST(&dec->qpd_blocked_headers[id]); read_ctx; 4334 read_ctx = next) 4335 { 4336 next = TAILQ_NEXT(read_ctx, hbrc_next_blocked); 4337 if (read_ctx->hbrc_largest_ref == dec->qpd_last_id) 4338 { 4339 read_ctx->hbrc_flags &= ~HBRC_BLOCKED; 4340 TAILQ_REMOVE(&dec->qpd_blocked_headers[id], read_ctx, 4341 hbrc_next_blocked); 4342 --dec->qpd_n_blocked; 4343 D_DEBUG("header block for stream %"PRIu64" has become unblocked", 4344 read_ctx->hbrc_stream_id); 4345 dec->qpd_dh_if->dhi_unblocked(read_ctx->hbrc_hblock); 4346 } 4347 } 4348} 4349 4350 4351int 4352lsqpack_dec_ici_pending (const struct lsqpack_dec *dec) 4353{ 4354 return dec->qpd_last_id != dec->qpd_largest_known_id; 4355} 4356 4357 4358ssize_t 4359lsqpack_dec_write_ici (struct lsqpack_dec *dec, unsigned char *buf, size_t sz) 4360{ 4361 unsigned char *p; 4362 unsigned count; 4363 4364 if (dec->qpd_last_id != dec->qpd_largest_known_id) 4365 { 4366 if (sz == 0) 4367 return -1; 4368 count = ID_MINUS(dec->qpd_last_id, dec->qpd_largest_known_id); 4369 *buf = 0; 4370 p = lsqpack_enc_int(buf, buf + sz, count, 6); 4371 if (p > buf) 4372 { 4373 D_DEBUG("wrote ICI: count=%u", count); 4374 dec->qpd_largest_known_id = dec->qpd_last_id; 4375 dec->qpd_bytes_in += p - buf; 4376 return p - buf; 4377 } 4378 else 4379 return -1; 4380 } 4381 else 4382 { 4383 D_DEBUG("no ICI instruction necessary: emitting zero bytes"); 4384 return 0; 4385 } 4386} 4387 4388 4389int 4390lsqpack_dec_unref_stream (struct lsqpack_dec *dec, void *hblock) 4391{ 4392 struct header_block_read_ctx *read_ctx; 4393 4394 read_ctx = find_header_block_read_ctx(dec, hblock); 4395 if (read_ctx) 4396 { 4397 D_DEBUG("unreffed header block for stream %"PRIu64, 4398 read_ctx->hbrc_stream_id); 4399 destroy_header_block_read_ctx(dec, read_ctx); 4400 return 0; 4401 } 4402 else 4403 { 4404 D_INFO("could not find header block to unref"); 4405 return -1; 4406 } 4407} 4408 4409 4410ssize_t 4411lsqpack_dec_cancel_stream (struct lsqpack_dec *dec, void *hblock, 4412 unsigned char *buf, size_t buf_sz) 4413{ 4414 struct header_block_read_ctx *read_ctx; 4415 unsigned char *p; 4416 4417 read_ctx = find_header_block_read_ctx(dec, hblock); 4418 if (!read_ctx) 4419 { 4420 D_INFO("could not find stream to cancel"); 4421 return 0; 4422 } 4423 4424 if (buf_sz == 0) 4425 return -1; 4426 4427 *buf = 0x40; 4428 p = lsqpack_enc_int(buf, buf + buf_sz, read_ctx->hbrc_stream_id, 6); 4429 if (p > buf) 4430 { 4431 D_DEBUG("cancelled stream %"PRIu64"; generate instruction of %u bytes", 4432 read_ctx->hbrc_stream_id, (unsigned) (p - buf)); 4433 destroy_header_block_read_ctx(dec, read_ctx); 4434 dec->qpd_bytes_in += p - buf; 4435 return p - buf; 4436 } 4437 else 4438 { 4439 D_WARN("cannot generate Cancel Stream instruction for stream %"PRIu64 4440 "; buf size=%zu", read_ctx->hbrc_stream_id, buf_sz); 4441 return -1; 4442 } 4443} 4444 4445 4446ssize_t 4447lsqpack_dec_cancel_stream_id (struct lsqpack_dec *dec, uint64_t stream_id, 4448 unsigned char *buf, size_t buf_sz) 4449{ 4450 unsigned char *p; 4451 4452 /* From qpack-14: "A decoder with a maximum dynamic table capacity 4453 * equal to zero MAY omit sending Stream Cancellations..." 4454 */ 4455 if (dec->qpd_max_capacity == 0) 4456 return 0; 4457 4458 if (buf_sz == 0) 4459 return -1; 4460 4461 *buf = 0x40; 4462 p = lsqpack_enc_int(buf, buf + buf_sz, stream_id, 6); 4463 if (p > buf) 4464 { 4465 D_DEBUG("generate Cancel Stream %"PRIu64" instruction of %u bytes", 4466 stream_id, (unsigned) (p - buf)); 4467 dec->qpd_bytes_in += p - buf; 4468 return p - buf; 4469 } 4470 else 4471 { 4472 D_DEBUG("cannot generate Cancel Stream instruction for stream %"PRIu64 4473 "; buf size=%zu", stream_id, buf_sz); 4474 return -1; 4475 } 4476} 4477 4478 4479static int 4480lsqpack_dec_push_entry (struct lsqpack_dec *dec, 4481 struct lsqpack_dec_table_entry *entry) 4482{ 4483 if (0 == ringbuf_add(&dec->qpd_dyn_table, entry)) 4484 { 4485 dec->qpd_cur_capacity += DTE_SIZE(entry); 4486 D_DEBUG("push entry:(`%.*s': `%.*s'), capacity %u", 4487 (int) entry->dte_name_len, DTE_NAME(entry), 4488 (int) entry->dte_val_len, DTE_VALUE(entry), 4489 dec->qpd_cur_capacity); 4490 dec->qpd_last_id = ID_PLUS(dec->qpd_last_id, 1); 4491 qdec_remove_overflow_entries(dec); 4492 qdec_process_blocked_headers(dec); 4493 if (dec->qpd_cur_capacity <= dec->qpd_cur_max_capacity) 4494 return 0; 4495 } 4496 4497 return -1; 4498} 4499 4500 4501int 4502lsqpack_dec_enc_in (struct lsqpack_dec *dec, const unsigned char *buf, 4503 size_t buf_sz) 4504{ 4505 const unsigned char *const end = buf + buf_sz; 4506 struct lsqpack_dec_table_entry *entry, *new_entry; 4507 struct huff_decode_retval hdr; 4508 unsigned prefix_bits = ~0u; 4509 size_t size; 4510 int r; 4511 4512 D_DEBUG("got %zu bytes of encoder stream", buf_sz); 4513 dec->qpd_bytes_in += buf_sz; 4514 4515#define WINR dec->qpd_enc_state.ctx_u.with_namref 4516#define WONR dec->qpd_enc_state.ctx_u.wo_namref 4517#define DUPL dec->qpd_enc_state.ctx_u.duplicate 4518#define SDTC dec->qpd_enc_state.ctx_u.sdtc 4519 4520 while (buf < end) 4521 { 4522 switch (dec->qpd_enc_state.resume) 4523 { 4524 case DEI_NEXT_INST: 4525 if (buf[0] & 0x80) 4526 { 4527 WINR.is_static = (buf[0] & 0x40) > 0; 4528 WINR.dec_int_state.resume = 0; 4529 WINR.reffed_entry = NULL; 4530 WINR.entry = NULL; 4531 dec->qpd_enc_state.resume = DEI_WINR_READ_NAME_IDX; 4532 prefix_bits = 6; 4533 goto dei_winr_read_name_idx; 4534 } 4535 else if (buf[0] & 0x40) 4536 { 4537 WONR.is_huffman = (buf[0] & 0x20) > 0; 4538 WONR.dec_int_state.resume = 0; 4539 WONR.entry = NULL; 4540 dec->qpd_enc_state.resume = DEI_WONR_READ_NAME_LEN; 4541 prefix_bits = 5; 4542 goto dei_wonr_read_name_idx; 4543 } 4544 else if (buf[0] & 0x20) 4545 { 4546 SDTC.dec_int_state.resume = 0; 4547 dec->qpd_enc_state.resume = DEI_SIZE_UPD_READ_IDX; 4548 prefix_bits = 5; 4549 goto dei_size_upd_read_idx; 4550 } 4551 else 4552 { 4553 DUPL.dec_int_state.resume = 0; 4554 dec->qpd_enc_state.resume = DEI_DUP_READ_IDX; 4555 prefix_bits = 5; 4556 goto dei_dup_read_idx; 4557 } 4558 case DEI_WINR_READ_NAME_IDX: 4559 dei_winr_read_name_idx: 4560 r = lsqpack_dec_int24(&buf, end, prefix_bits, 4561 &WINR.name_idx, &WINR.dec_int_state); 4562 if (r == 0) 4563 { 4564 if (WINR.is_static) 4565 { 4566 if (WINR.name_idx < QPACK_STATIC_TABLE_SIZE) 4567 WINR.reffed_entry = NULL; 4568 else 4569 return -1; 4570 } 4571 else 4572 { 4573 WINR.reffed_entry = qdec_get_table_entry_rel(dec, 4574 WINR.name_idx); 4575 if (!WINR.reffed_entry) 4576 return -1; 4577 ++WINR.reffed_entry->dte_refcnt; 4578 } 4579 dec->qpd_enc_state.resume = DEI_WINR_BEGIN_READ_VAL_LEN; 4580 break; 4581 } 4582 else if (r == -1) 4583 return 0; 4584 else 4585 return -1; 4586 case DEI_WINR_BEGIN_READ_VAL_LEN: 4587 WINR.is_huffman = (buf[0] & 0x80) > 0; 4588 WINR.dec_int_state.resume = 0; 4589 dec->qpd_enc_state.resume = DEI_WINR_READ_VAL_LEN; 4590 prefix_bits = 7; 4591 /* fall-through */ 4592 case DEI_WINR_READ_VAL_LEN: 4593 r = lsqpack_dec_int24(&buf, end, prefix_bits, &WINR.val_len, 4594 &WINR.dec_int_state); 4595 if (r == 0) 4596 { 4597 if (WINR.is_static) 4598 { 4599 WINR.name_len = static_table[WINR.name_idx].name_len; 4600 WINR.name = static_table[WINR.name_idx].name; 4601 } 4602 else 4603 { 4604 WINR.name_len = WINR.reffed_entry->dte_name_len; 4605 WINR.name = DTE_NAME(WINR.reffed_entry); 4606 } 4607 /* This check accounts for the fact that Huffman-encoded string 4608 * can shrink. 4609 */ 4610 if (WINR.val_len > ((dec->qpd_cur_max_capacity 4611 - WINR.name_len) << (WINR.is_huffman << 1))) 4612 return -1; 4613 if (WINR.is_huffman) 4614 WINR.alloced_val_len = WINR.val_len + WINR.val_len / 2; 4615 else 4616 WINR.alloced_val_len = WINR.val_len; 4617 WINR.entry = malloc(sizeof(*WINR.entry) + WINR.name_len 4618 + WINR.alloced_val_len); 4619 if (!WINR.entry) 4620 return -1; 4621 if (WINR.is_static) 4622 { 4623 WINR.entry->dte_flags = DTEF_NAME_HASH | DTEF_NAME_IDX; 4624 WINR.entry->dte_name_hash = name_hashes[WINR.name_idx]; 4625 WINR.entry->dte_name_idx = WINR.name_idx; 4626 } 4627 else 4628 { 4629 WINR.entry->dte_flags = WINR.reffed_entry->dte_flags 4630 & (DTEF_NAME_HASH|DTEF_NAME_IDX); 4631 WINR.entry->dte_name_hash 4632 = WINR.reffed_entry->dte_name_hash; 4633 WINR.entry->dte_name_idx = WINR.reffed_entry->dte_name_idx; 4634 } 4635 WINR.entry->dte_name_len = WINR.name_len; 4636 WINR.nread = 0; 4637 WINR.val_off = 0; 4638 if (WINR.val_len) 4639 { 4640 if (WINR.is_huffman) 4641 { 4642 dec->qpd_enc_state.resume = DEI_WINR_READ_VALUE_HUFFMAN; 4643 WINR.dec_huff_state.resume = 0; 4644 } 4645 else 4646 dec->qpd_enc_state.resume = DEI_WINR_READ_VALUE_PLAIN; 4647 } 4648 else 4649 goto winr_insert_entry; 4650 } 4651 else if (r == -1) 4652 return 0; 4653 else 4654 return -1; 4655 break; 4656 case DEI_WINR_READ_VALUE_HUFFMAN: 4657 size = MIN((unsigned) (end - buf), WINR.val_len - WINR.nread); 4658 hdr = lsqpack_huff_decode(buf, size, 4659 (unsigned char *) DTE_VALUE(WINR.entry) + WINR.val_off, 4660 WINR.alloced_val_len - WINR.val_off, 4661 &WINR.dec_huff_state, WINR.nread + size == WINR.val_len); 4662 switch (hdr.status) 4663 { 4664 case HUFF_DEC_OK: 4665 buf += hdr.n_src; 4666 WINR.entry->dte_val_len = WINR.val_off + hdr.n_dst; 4667 WINR.entry->dte_refcnt = 1; 4668 memcpy(DTE_NAME(WINR.entry), WINR.name, WINR.name_len); 4669 if (WINR.reffed_entry) 4670 { 4671 qdec_decref_entry(WINR.reffed_entry); 4672 WINR.reffed_entry = NULL; 4673 } 4674 r = lsqpack_dec_push_entry(dec, WINR.entry); 4675 if (0 == r) 4676 { 4677 dec->qpd_enc_state.resume = 0; 4678 WINR.entry = NULL; 4679 break; 4680 } 4681 qdec_decref_entry(WINR.entry); 4682 WINR.entry = NULL; 4683 return -1; 4684 case HUFF_DEC_END_SRC: 4685 buf += hdr.n_src; 4686 WINR.nread += hdr.n_src; 4687 WINR.val_off += hdr.n_dst; 4688 break; 4689 case HUFF_DEC_END_DST: 4690 WINR.alloced_val_len *= 2; 4691 entry = realloc(WINR.entry, sizeof(*WINR.entry) 4692 + WINR.name_len + WINR.alloced_val_len); 4693 if (!entry) 4694 return -1; 4695 WINR.entry = entry; 4696 buf += hdr.n_src; 4697 WINR.nread += hdr.n_src; 4698 WINR.val_off += hdr.n_dst; 4699 break; 4700 default: 4701 return -1; 4702 } 4703 break; 4704 case DEI_WINR_READ_VALUE_PLAIN: 4705 assert(WINR.alloced_val_len >= WINR.val_len); 4706 size = MIN((unsigned) (end - buf), WINR.val_len - WINR.val_off); 4707 memcpy(DTE_VALUE(WINR.entry) + WINR.val_off, buf, size); 4708 WINR.val_off += size; 4709 buf += size; 4710 if (WINR.val_off == WINR.val_len) 4711 { 4712 winr_insert_entry: 4713 WINR.entry->dte_val_len = WINR.val_off; 4714 WINR.entry->dte_refcnt = 1; 4715 memcpy(DTE_NAME(WINR.entry), WINR.name, WINR.name_len); 4716 if (WINR.reffed_entry) 4717 { 4718 qdec_decref_entry(WINR.reffed_entry); 4719 WINR.reffed_entry = NULL; 4720 } 4721 r = lsqpack_dec_push_entry(dec, WINR.entry); 4722 if (0 == r) 4723 { 4724 dec->qpd_enc_state.resume = 0; 4725 WINR.entry = NULL; 4726 break; 4727 } 4728 qdec_decref_entry(WINR.entry); 4729 WINR.entry = NULL; 4730 return -1; 4731 } 4732 break; 4733 case DEI_WONR_READ_NAME_LEN: 4734 dei_wonr_read_name_idx: 4735 r = lsqpack_dec_int24(&buf, end, prefix_bits, &WONR.str_len, 4736 &DUPL.dec_int_state); 4737 if (r == 0) 4738 { 4739 /* This check accounts for the fact that Huffman-encoded string 4740 * can shrink. 4741 */ 4742 if (WONR.str_len > (dec->qpd_cur_max_capacity 4743 << (WONR.is_huffman << 1))) 4744 return -1; 4745 WONR.alloced_len = WONR.str_len ? WONR.str_len + WONR.str_len / 2 : 16; 4746 size = sizeof(*new_entry) + WONR.alloced_len; 4747 WONR.entry = malloc(size); 4748 if (!WONR.entry) 4749 return -1; 4750 WONR.entry->dte_flags = 0; 4751 WONR.nread = 0; 4752 WONR.str_off = 0; 4753 if (WONR.is_huffman) 4754 { 4755 dec->qpd_enc_state.resume = DEI_WONR_READ_NAME_HUFFMAN; 4756 WONR.dec_huff_state.resume = 0; 4757 } 4758 else 4759 dec->qpd_enc_state.resume = DEI_WONR_READ_NAME_PLAIN; 4760 break; 4761 } 4762 else if (r == -1) 4763 return 0; 4764 else 4765 return -1; 4766 case DEI_WONR_READ_NAME_HUFFMAN: 4767 size = MIN((unsigned) (end - buf), WONR.str_len - WONR.nread); 4768 hdr = lsqpack_huff_decode(buf, size, 4769 (unsigned char *) DTE_NAME(WONR.entry) + WONR.str_off, 4770 WONR.alloced_len - WONR.str_off, 4771 &WONR.dec_huff_state, WONR.nread + size == WONR.str_len); 4772 switch (hdr.status) 4773 { 4774 case HUFF_DEC_OK: 4775 buf += hdr.n_src; 4776 WONR.entry->dte_name_len = WONR.str_off + hdr.n_dst; 4777 dec->qpd_enc_state.resume = DEI_WONR_BEGIN_READ_VAL_LEN; 4778 break; 4779 case HUFF_DEC_END_SRC: 4780 buf += hdr.n_src; 4781 WONR.nread += hdr.n_src; 4782 WONR.str_off += hdr.n_dst; 4783 break; 4784 case HUFF_DEC_END_DST: 4785 WONR.alloced_len *= 2; 4786 entry = realloc(WONR.entry, sizeof(*WONR.entry) 4787 + WONR.alloced_len); 4788 if (!entry) 4789 return -1; 4790 WONR.entry = entry; 4791 buf += hdr.n_src; 4792 WONR.nread += hdr.n_src; 4793 WONR.str_off += hdr.n_dst; 4794 break; 4795 default: 4796 return -1; 4797 } 4798 break; 4799 case DEI_WONR_READ_NAME_PLAIN: 4800 assert(WONR.alloced_len >= WONR.str_len); 4801 size = MIN((unsigned) (end - buf), WONR.str_len - WONR.str_off); 4802 memcpy(DTE_NAME(WONR.entry) + WONR.str_off, buf, size); 4803 WONR.str_off += size; 4804 buf += size; 4805 if (WONR.str_off == WONR.str_len) 4806 { 4807 WONR.entry->dte_name_len = WONR.str_off; 4808 dec->qpd_enc_state.resume = DEI_WONR_BEGIN_READ_VAL_LEN; 4809 } 4810 break; 4811 case DEI_WONR_BEGIN_READ_VAL_LEN: 4812 WONR.is_huffman = (buf[0] & 0x80) > 0; 4813 WONR.dec_int_state.resume = 0; 4814 dec->qpd_enc_state.resume = DEI_WONR_READ_VAL_LEN; 4815 prefix_bits = 7; 4816 /* fall-through */ 4817 case DEI_WONR_READ_VAL_LEN: 4818 r = lsqpack_dec_int24(&buf, end, prefix_bits, &WONR.str_len, 4819 &WONR.dec_int_state); 4820 if (r == 0) 4821 { 4822 /* This check accounts for the fact that Huffman-encoded string 4823 * can shrink. 4824 */ 4825 if (WONR.str_len > ((dec->qpd_cur_max_capacity 4826 - WONR.entry->dte_name_len) << (WONR.is_huffman << 1))) 4827 return -1; 4828 WONR.nread = 0; 4829 WONR.str_off = 0; 4830 if (WONR.str_len) 4831 { 4832 if (WONR.is_huffman) 4833 { 4834 dec->qpd_enc_state.resume = DEI_WONR_READ_VALUE_HUFFMAN; 4835 WONR.dec_huff_state.resume = 0; 4836 } 4837 else 4838 dec->qpd_enc_state.resume = DEI_WONR_READ_VALUE_PLAIN; 4839 } 4840 else 4841 goto wonr_insert_entry; 4842 } 4843 else if (r == -1) 4844 return 0; 4845 else 4846 return -1; 4847 break; 4848 case DEI_WONR_READ_VALUE_HUFFMAN: 4849 size = MIN((unsigned) (end - buf), WONR.str_len - WONR.nread); 4850 hdr = lsqpack_huff_decode(buf, size, 4851 (unsigned char *) DTE_VALUE(WONR.entry) + WONR.str_off, 4852 WONR.alloced_len - WONR.entry->dte_name_len - WONR.str_off, 4853 &WONR.dec_huff_state, WONR.nread + size == WONR.str_len); 4854 switch (hdr.status) 4855 { 4856 case HUFF_DEC_OK: 4857 buf += hdr.n_src; 4858 WONR.entry->dte_val_len = WONR.str_off + hdr.n_dst; 4859 WONR.entry->dte_refcnt = 1; 4860 r = lsqpack_dec_push_entry(dec, WONR.entry); 4861 if (0 == r) 4862 { 4863 dec->qpd_enc_state.resume = 0; 4864 WONR.entry = NULL; 4865 break; 4866 } 4867 qdec_decref_entry(WONR.entry); 4868 WONR.entry = NULL; 4869 return -1; 4870 case HUFF_DEC_END_SRC: 4871 buf += hdr.n_src; 4872 WONR.nread += hdr.n_src; 4873 WONR.str_off += hdr.n_dst; 4874 break; 4875 case HUFF_DEC_END_DST: 4876 assert(WONR.alloced_len); 4877 WONR.alloced_len *= 2; 4878 entry = realloc(WONR.entry, sizeof(*WONR.entry) 4879 + WONR.alloced_len); 4880 if (!entry) 4881 return -1; 4882 WONR.entry = entry; 4883 buf += hdr.n_src; 4884 WONR.nread += hdr.n_src; 4885 WONR.str_off += hdr.n_dst; 4886 break; 4887 default: 4888 return -1; 4889 } 4890 break; 4891 case DEI_WONR_READ_VALUE_PLAIN: 4892 if (WONR.alloced_len < WONR.entry->dte_name_len + WONR.str_len) 4893 { 4894 WONR.alloced_len = WONR.entry->dte_name_len + WONR.str_len; 4895 entry = realloc(WONR.entry, sizeof(*WONR.entry) 4896 + WONR.alloced_len); 4897 if (entry) 4898 WONR.entry = entry; 4899 else 4900 return -1; 4901 } 4902 size = MIN((unsigned) (end - buf), WONR.str_len - WONR.str_off); 4903 memcpy(DTE_VALUE(WONR.entry) + WONR.str_off, buf, size); 4904 WONR.str_off += size; 4905 buf += size; 4906 if (WONR.str_off == WONR.str_len) 4907 { 4908 wonr_insert_entry: 4909 WONR.entry->dte_val_len = WONR.str_off; 4910 WONR.entry->dte_refcnt = 1; 4911 r = lsqpack_dec_push_entry(dec, WONR.entry); 4912 if (0 == r) 4913 { 4914 dec->qpd_enc_state.resume = 0; 4915 WONR.entry = NULL; 4916 break; 4917 } 4918 qdec_decref_entry(WONR.entry); 4919 WONR.entry = NULL; 4920 return -1; 4921 } 4922 break; 4923 case DEI_DUP_READ_IDX: 4924 dei_dup_read_idx: 4925 r = lsqpack_dec_int24(&buf, end, prefix_bits, &DUPL.index, 4926 &DUPL.dec_int_state); 4927 if (r == 0) 4928 { 4929 entry = qdec_get_table_entry_rel(dec, DUPL.index); 4930 if (!entry) 4931 return -1; 4932 size = sizeof(*new_entry) + entry->dte_name_len 4933 + entry->dte_val_len; 4934 new_entry = malloc(size); 4935 if (!new_entry) 4936 return -1; 4937 memcpy(new_entry, entry, size); 4938 new_entry->dte_refcnt = 1; 4939 if (0 == lsqpack_dec_push_entry(dec, new_entry)) 4940 { 4941 dec->qpd_enc_state.resume = 0; 4942 break; 4943 } 4944 qdec_decref_entry(new_entry); 4945 return -1; 4946 } 4947 else if (r == -1) 4948 return 0; 4949 else 4950 return -1; 4951 case DEI_SIZE_UPD_READ_IDX: 4952 dei_size_upd_read_idx: 4953 r = lsqpack_dec_int(&buf, end, prefix_bits, &SDTC.new_size, 4954 &SDTC.dec_int_state); 4955 if (r == 0) 4956 { 4957 if (SDTC.new_size <= dec->qpd_max_capacity) 4958 { 4959 dec->qpd_enc_state.resume = 0; 4960 D_DEBUG("got TSU=%"PRIu64, SDTC.new_size); 4961 qdec_update_max_capacity(dec, (unsigned int) SDTC.new_size); 4962 break; 4963 } 4964 else 4965 return -1; 4966 } 4967 else if (r == -1) 4968 return 0; 4969 else 4970 return -1; 4971 default: 4972 assert(0); 4973 } 4974 } 4975 4976#undef WINR 4977#undef WONR 4978#undef DUPL 4979#undef SDTC 4980 4981 return 0; 4982} 4983 4984 4985void 4986lsqpack_dec_print_table (const struct lsqpack_dec *dec, FILE *out) 4987{ 4988 const struct lsqpack_dec_table_entry *entry; 4989 struct ringbuf_iter riter; 4990 lsqpack_abs_id_t id; 4991 4992 fprintf(out, "Printing decoder table state.\n"); 4993 fprintf(out, "Max capacity: %u; current capacity: %u\n", 4994 dec->qpd_cur_max_capacity, dec->qpd_cur_capacity); 4995 id = ID_MINUS(dec->qpd_last_id + 1, ringbuf_count(&dec->qpd_dyn_table)); 4996 for (entry = ringbuf_iter_first(&riter, &dec->qpd_dyn_table); 4997 entry; entry= ringbuf_iter_next(&riter)) 4998 { 4999 fprintf(out, "%u) %.*s: %.*s\n", id, 5000 entry->dte_name_len, DTE_NAME(entry), 5001 entry->dte_val_len, DTE_VALUE(entry)); 5002 id = ID_PLUS(id, 1); 5003 } 5004 fprintf(out, "\n"); 5005} 5006 5007 5008const struct lsqpack_dec_err * 5009lsqpack_dec_get_err_info (const struct lsqpack_dec *dec) 5010{ 5011 return &dec->qpd_err; 5012} 5013 5014#define SHORTEST_CODE 5 5015 5016/* This whole pragma business has to do with turning off uninitialized warnings. 5017 * We do it for gcc and clang. Other compilers get slightly slower code, where 5018 * unnecessary initialization is performed. 5019 */ 5020#if __GNUC__ 5021#pragma GCC diagnostic ignored "-Wunknown-pragmas" 5022#if __clang__ 5023#pragma GCC diagnostic ignored "-Wunknown-warning-option" 5024#endif 5025#endif 5026 5027static unsigned char * 5028qenc_huffman_enc (const unsigned char *src, const unsigned char *const src_end, 5029 unsigned char *dst) 5030{ 5031 uintptr_t bits; /* OK not to initialize this variable */ 5032 unsigned bits_used = 0, adj; 5033 struct encode_el cur_enc_code; 5034#if __GNUC__ 5035#pragma GCC diagnostic push 5036#pragma GCC diagnostic ignored "-Wmaybe-uninitialized" 5037#pragma GCC diagnostic ignored "-Wuninitialized" 5038#else 5039 bits = 0; 5040#endif 5041#if LS_QPACK_USE_LARGE_TABLES 5042 const struct henc *henc; 5043 uint16_t idx; 5044 5045 while (src + sizeof(bits) * 8 / SHORTEST_CODE + sizeof(idx) < src_end) 5046 { 5047 memcpy(&idx, src, 2); 5048 henc = &hencs[idx]; 5049 src += 2; 5050 while (bits_used + henc->lens < sizeof(bits) * 8) 5051 { 5052 bits <<= henc->lens; 5053 bits |= henc->code; 5054 bits_used += henc->lens; 5055 memcpy(&idx, src, 2); 5056 henc = &hencs[idx]; 5057 src += 2; 5058 } 5059 if (henc->lens < 64) 5060 { 5061 bits <<= sizeof(bits) * 8 - bits_used; 5062 bits_used = henc->lens - (sizeof(bits) * 8 - bits_used); 5063 bits |= henc->code >> bits_used; 5064#if UINTPTR_MAX == 18446744073709551615ull 5065 *dst++ = bits >> 56; 5066 *dst++ = bits >> 48; 5067 *dst++ = bits >> 40; 5068 *dst++ = bits >> 32; 5069#endif 5070 *dst++ = bits >> 24; 5071 *dst++ = bits >> 16; 5072 *dst++ = bits >> 8; 5073 *dst++ = bits; 5074 bits = henc->code; /* OK not to clear high bits */ 5075 } 5076 else 5077 { 5078 src -= 2; 5079 break; 5080 } 5081 } 5082#endif 5083 5084 while (src != src_end) 5085 { 5086 cur_enc_code = encode_table[*src++]; 5087 if (bits_used + cur_enc_code.bits < sizeof(bits) * 8) 5088 { 5089 bits <<= cur_enc_code.bits; 5090 bits |= cur_enc_code.code; 5091 bits_used += cur_enc_code.bits; 5092 continue; 5093 } 5094 else 5095 { 5096 bits <<= sizeof(bits) * 8 - bits_used; 5097 bits_used = cur_enc_code.bits - (sizeof(bits) * 8 - bits_used); 5098 bits |= cur_enc_code.code >> bits_used; 5099#if UINTPTR_MAX == 18446744073709551615ull 5100 *dst++ = bits >> 56; 5101 *dst++ = bits >> 48; 5102 *dst++ = bits >> 40; 5103 *dst++ = bits >> 32; 5104#endif 5105 *dst++ = bits >> 24; 5106 *dst++ = bits >> 16; 5107 *dst++ = bits >> 8; 5108 *dst++ = bits; 5109 bits = cur_enc_code.code; /* OK not to clear high bits */ 5110 } 5111 } 5112 5113 if (bits_used) 5114 { 5115 adj = (bits_used + 7) & -8; /* Round up to 8 */ 5116 bits <<= adj - bits_used; /* Align to byte boundary */ 5117 bits |= ((1 << (adj - bits_used)) - 1); /* EOF */ 5118 switch (adj >> 3) 5119 { /* Write out */ 5120#if UINTPTR_MAX == 18446744073709551615ull 5121 case 8: *dst++ = bits >> 56; 5122 case 7: *dst++ = bits >> 48; 5123 case 6: *dst++ = bits >> 40; 5124 case 5: *dst++ = bits >> 32; 5125#endif 5126 case 4: *dst++ = bits >> 24; 5127 case 3: *dst++ = bits >> 16; 5128 case 2: *dst++ = bits >> 8; 5129 default: *dst++ = bits; 5130 } 5131 } 5132#if __GNUC__ 5133#pragma GCC diagnostic pop 5134#endif 5135 5136 return dst; 5137} 5138 5139 5140static unsigned 5141qenc_enc_str_size (const unsigned char *str, unsigned str_len) 5142{ 5143 unsigned const char *const end = str + str_len; 5144 unsigned enc_size_bits, enc_size_bytes; 5145 5146 enc_size_bits = 0; 5147 while (str < end) 5148 enc_size_bits += encode_table[*str++].bits; 5149 enc_size_bytes = enc_size_bits / 8 + ((enc_size_bits & 7) != 0); 5150 5151 return enc_size_bytes; 5152} 5153 5154 5155static unsigned char * 5156qdec_huff_dec4bits (uint8_t src_4bits, unsigned char *dst, 5157 struct lsqpack_decode_status *status) 5158{ 5159 const struct decode_el cur_dec_code = 5160 decode_tables[status->state][src_4bits]; 5161 if (cur_dec_code.flags & HPACK_HUFFMAN_FLAG_FAIL) { 5162 return NULL; //failed 5163 } 5164 if (cur_dec_code.flags & HPACK_HUFFMAN_FLAG_SYM) 5165 { 5166 *dst = cur_dec_code.sym; 5167 dst++; 5168 } 5169 5170 status->state = cur_dec_code.state; 5171 status->eos = ((cur_dec_code.flags & HPACK_HUFFMAN_FLAG_ACCEPTED) != 0); 5172 return dst; 5173} 5174 5175 5176#if LS_QPACK_USE_LARGE_TABLES 5177/* The decoder is optimized for the common case. Most of the time, we decode 5178 * data whose encoding is 16 bits or shorter. This lets us use a 64 KB table 5179 * indexed by two bytes of input and outputs 1, 2, or 3 bytes at a time. 5180 * 5181 * In the case a longer code is encoutered, we fall back to the original 5182 * Huffman decoder that supports all code lengths. 5183 */ 5184static struct huff_decode_retval 5185huff_decode_fast (const unsigned char *src, int src_len, 5186 unsigned char *dst, int dst_len, 5187 struct lsqpack_huff_decode_state *state, int final) 5188{ 5189 unsigned char *const orig_dst = dst; 5190 const unsigned char *const src_end = src + src_len; 5191 unsigned char *const dst_end = dst + dst_len; 5192 uintptr_t buf; /* OK not to initialize the buffer */ 5193 unsigned avail_bits, len; 5194 struct huff_decode_retval rv; 5195 struct hdec hdec; 5196 uint16_t idx; 5197 5198#if __GNUC__ 5199#pragma GCC diagnostic push 5200#pragma GCC diagnostic ignored "-Wmaybe-uninitialized" 5201#pragma GCC diagnostic ignored "-Wuninitialized" 5202#else 5203 buf = 0; 5204#endif 5205 5206 avail_bits = 0; 5207 while (1) 5208 { 5209 if (src + sizeof(buf) <= src_end) 5210 { 5211 len = (sizeof(buf) * 8 - avail_bits) >> 3; 5212 avail_bits += len << 3; 5213 switch (len) 5214 { 5215#if UINTPTR_MAX == 18446744073709551615ull 5216 case 8: 5217 buf <<= 8; 5218 buf |= (uintptr_t) *src++; 5219 case 7: 5220 buf <<= 8; 5221 buf |= (uintptr_t) *src++; 5222 default: 5223 buf <<= 48; 5224 buf |= (uintptr_t) *src++ << 40; 5225 buf |= (uintptr_t) *src++ << 32; 5226 buf |= (uintptr_t) *src++ << 24; 5227 buf |= (uintptr_t) *src++ << 16; 5228#else 5229 case 4: 5230 buf <<= 8; 5231 buf |= (uintptr_t) *src++; 5232 case 3: 5233 buf <<= 8; 5234 buf |= (uintptr_t) *src++; 5235 default: 5236 buf <<= 16; 5237#endif 5238 buf |= (uintptr_t) *src++ << 8; 5239 buf |= (uintptr_t) *src++ << 0; 5240 } 5241 } 5242 else if (src < src_end) 5243 do 5244 { 5245 buf <<= 8; 5246 buf |= (uintptr_t) *src++; 5247 avail_bits += 8; 5248 } 5249 while (src < src_end && avail_bits <= sizeof(buf) * 8 - 8); 5250 else 5251 break; /* Normal case terminating condition: out of input */ 5252 5253 if (dst_end - dst >= (ptrdiff_t) (8 * sizeof(buf) / SHORTEST_CODE) 5254 && avail_bits >= 16) 5255 { 5256 /* Fast path: don't check destination bounds */ 5257 do 5258 { 5259 idx = buf >> (avail_bits - 16); 5260 hdec = hdecs[idx]; 5261 dst[0] = hdec.out[0]; 5262 dst[1] = hdec.out[1]; 5263 dst[2] = hdec.out[2]; 5264 dst += hdec.lens & 3; 5265 avail_bits -= hdec.lens >> 2; 5266 } 5267 while (avail_bits >= 16 && hdec.lens); 5268 if (avail_bits < 16) 5269 continue; 5270 goto slow_path; 5271 } 5272 else 5273 while (avail_bits >= 16) 5274 { 5275 idx = buf >> (avail_bits - 16); 5276 hdec = hdecs[idx]; 5277 len = hdec.lens & 3; 5278 if (len && dst + len <= dst_end) 5279 { 5280 switch (len) 5281 { 5282 case 3: 5283 *dst++ = hdec.out[0]; 5284 *dst++ = hdec.out[1]; 5285 *dst++ = hdec.out[2]; 5286 break; 5287 case 2: 5288 *dst++ = hdec.out[0]; 5289 *dst++ = hdec.out[1]; 5290 break; 5291 default: 5292 *dst++ = hdec.out[0]; 5293 break; 5294 } 5295 avail_bits -= hdec.lens >> 2; 5296 } 5297 else if (dst + len > dst_end) 5298 goto dst_ended; 5299 else 5300 goto slow_path; 5301 } 5302 } 5303 5304 if (avail_bits >= SHORTEST_CODE) 5305 { 5306 idx = buf << (16 - avail_bits); 5307 idx |= (1 << (16 - avail_bits)) - 1; /* EOF */ 5308 if (idx == 0xFFFF && avail_bits < 8) 5309 goto end; 5310 /* If a byte or more of input is left, this mean there is a valid 5311 * encoding, not just EOF. 5312 */ 5313 hdec = hdecs[idx]; 5314 len = hdec.lens & 3; 5315 if ((hdec.lens >> 2) > avail_bits) 5316 return (struct huff_decode_retval) { 5317 .status = HUFF_DEC_ERROR, 5318 .n_dst = 0, 5319 .n_src = 0, 5320 }; 5321 if (len && dst + len <= dst_end) 5322 { 5323 switch (len) 5324 { 5325 case 3: 5326 *dst++ = hdec.out[0]; 5327 *dst++ = hdec.out[1]; 5328 *dst++ = hdec.out[2]; 5329 break; 5330 case 2: 5331 *dst++ = hdec.out[0]; 5332 *dst++ = hdec.out[1]; 5333 break; 5334 default: 5335 *dst++ = hdec.out[0]; 5336 break; 5337 } 5338 avail_bits -= hdec.lens >> 2; 5339 } 5340 else if (dst + len > dst_end) 5341 goto dst_ended; 5342 else 5343 /* This must be an invalid code, otherwise it would have fit */ 5344 return (struct huff_decode_retval) { 5345 .status = HUFF_DEC_ERROR, 5346 .n_dst = 0, 5347 .n_src = 0, 5348 }; 5349 } 5350 5351 if (avail_bits > 0) 5352 { 5353 if (((1u << avail_bits) - 1) != (buf & ((1u << avail_bits) - 1))) 5354 return (struct huff_decode_retval) { /* Not EOF as expected */ 5355 .status = HUFF_DEC_ERROR, 5356 .n_dst = 0, 5357 .n_src = 0, 5358 }; 5359 } 5360#if __GNUC__ 5361#pragma GCC diagnostic pop 5362#endif 5363 5364 end: 5365 return (struct huff_decode_retval) { 5366 .status = HUFF_DEC_OK, 5367 .n_dst = dst - orig_dst, 5368 .n_src = src_len - (src_end - src), 5369 }; 5370 5371 dst_ended: 5372 /* Find previous byte boundary. It is OK not to consume all input, as we 5373 * always grow the destination buffer and try again. 5374 */ 5375 while ((avail_bits & 7) && dst > orig_dst) 5376 avail_bits += encode_table[ *--dst ].bits; 5377 assert((avail_bits & 7) == 0); 5378 src -= avail_bits >> 3; 5379 return (struct huff_decode_retval) { 5380 .status = HUFF_DEC_END_DST, 5381 .n_dst = dst_len - (dst_end - dst), 5382 .n_src = src_len - (src_end - src), 5383 }; 5384 5385 slow_path: 5386 /* Find previous byte boundary and finish decoding thence. */ 5387 while ((avail_bits & 7) && dst > orig_dst) 5388 avail_bits += encode_table[ *--dst ].bits; 5389 assert((avail_bits & 7) == 0); 5390 src -= avail_bits >> 3; 5391 rv = lsqpack_huff_decode_full(src, src_end - src, dst, dst_end - dst, 5392 state, final); 5393 if (rv.status == HUFF_DEC_OK || rv.status == HUFF_DEC_END_DST) 5394 { 5395 rv.n_dst += dst_len - (dst_end - dst); 5396 rv.n_src += src_len - (src_end - src); 5397 } 5398 return rv; 5399} 5400#endif 5401#if __GNUC__ 5402#pragma GCC diagnostic pop /* -Wunknown-pragmas */ 5403#endif 5404