1 /* 2 * nghttp3 3 * 4 * Copyright (c) 2019 nghttp3 contributors 5 * Copyright (c) 2013 nghttp2 contributors 6 * 7 * Permission is hereby granted, free of charge, to any person obtaining 8 * a copy of this software and associated documentation files (the 9 * "Software"), to deal in the Software without restriction, including 10 * without limitation the rights to use, copy, modify, merge, publish, 11 * distribute, sublicense, and/or sell copies of the Software, and to 12 * permit persons to whom the Software is furnished to do so, subject to 13 * the following conditions: 14 * 15 * The above copyright notice and this permission notice shall be 16 * included in all copies or substantial portions of the Software. 17 * 18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 19 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 20 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 21 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 22 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 23 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 24 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 25 */ 26 #ifndef NGHTTP3_QPACK_H 27 #define NGHTTP3_QPACK_H 28 29 #ifdef HAVE_CONFIG_H 30 # include <config.h> 31 #endif /* HAVE_CONFIG_H */ 32 33 #include <nghttp3/nghttp3.h> 34 35 #include "nghttp3_rcbuf.h" 36 #include "nghttp3_map.h" 37 #include "nghttp3_pq.h" 38 #include "nghttp3_ringbuf.h" 39 #include "nghttp3_buf.h" 40 #include "nghttp3_ksl.h" 41 #include "nghttp3_qpack_huffman.h" 42 43 #define NGHTTP3_QPACK_INT_MAX ((1ull << 62) - 1) 44 45 /* NGHTTP3_QPACK_MAX_NAMELEN is the maximum (compressed) length of 46 header name this library can decode. */ 47 #define NGHTTP3_QPACK_MAX_NAMELEN 256 48 /* NGHTTP3_QPACK_MAX_VALUELEN is the maximum (compressed) length of 49 header value this library can decode. */ 50 #define NGHTTP3_QPACK_MAX_VALUELEN 65536 51 52 /* nghttp3_qpack_indexing_mode is a indexing strategy. */ 53 typedef enum nghttp3_qpack_indexing_mode { 54 /* NGHTTP3_QPACK_INDEXING_MODE_LITERAL means that header field 55 should not be inserted into dynamic table. */ 56 NGHTTP3_QPACK_INDEXING_MODE_LITERAL, 57 /* NGHTTP3_QPACK_INDEXING_MODE_STORE means that header field can be 58 inserted into dynamic table. */ 59 NGHTTP3_QPACK_INDEXING_MODE_STORE, 60 /* NGHTTP3_QPACK_INDEXING_MODE_NEVER means that header field should 61 not be inserted into dynamic table and this must be true for all 62 forwarding paths. */ 63 NGHTTP3_QPACK_INDEXING_MODE_NEVER, 64 } nghttp3_qpack_indexing_mode; 65 66 typedef struct nghttp3_qpack_entry nghttp3_qpack_entry; 67 68 struct nghttp3_qpack_entry { 69 /* The header field name/value pair */ 70 nghttp3_qpack_nv nv; 71 /* map_next points to the entry which shares same bucket in hash 72 table. */ 73 nghttp3_qpack_entry *map_next; 74 /* sum is the sum of all entries inserted up to this entry. This 75 value does not contain the space required for this entry. */ 76 size_t sum; 77 /* absidx is the absolute index of this entry. */ 78 uint64_t absidx; 79 /* The hash value for header name (nv.name). */ 80 uint32_t hash; 81 }; 82 83 /* The entry used for static table. */ 84 typedef struct nghttp3_qpack_static_entry { 85 uint64_t absidx; 86 int32_t token; 87 uint32_t hash; 88 } nghttp3_qpack_static_entry; 89 90 typedef struct nghttp3_qpack_static_header { 91 nghttp3_rcbuf name; 92 nghttp3_rcbuf value; 93 int32_t token; 94 } nghttp3_qpack_static_header; 95 96 /* 97 * nghttp3_qpack_header_block_ref is created per encoded header block 98 * and includes the required insert count and the minimum insert count 99 * of dynamic table entry it refers to. 100 */ 101 typedef struct nghttp3_qpack_header_block_ref { 102 nghttp3_pq_entry max_cnts_pe; 103 nghttp3_pq_entry min_cnts_pe; 104 /* max_cnt is the required insert count. */ 105 uint64_t max_cnt; 106 /* min_cnt is the minimum insert count of dynamic table entry it 107 refers to. In other words, this is the minimum absolute index of 108 dynamic header table entry this encoded block refers to plus 109 1. */ 110 uint64_t min_cnt; 111 } nghttp3_qpack_header_block_ref; 112 113 int nghttp3_qpack_header_block_ref_new(nghttp3_qpack_header_block_ref **pref, 114 uint64_t max_cnt, uint64_t min_cnt, 115 const nghttp3_mem *mem); 116 117 void nghttp3_qpack_header_block_ref_del(nghttp3_qpack_header_block_ref *ref, 118 const nghttp3_mem *mem); 119 120 typedef struct nghttp3_qpack_stream { 121 int64_t stream_id; 122 /* refs is an array of pointer to nghttp3_qpack_header_block_ref in 123 the order of the time they are encoded. HTTP/3 allows multiple 124 header blocks (e.g., non-final response headers, final response 125 headers, trailers, and push promises) per stream. */ 126 nghttp3_ringbuf refs; 127 /* max_cnts is a priority queue sorted by descending order of 128 max_cnt of nghttp3_qpack_header_block_ref. */ 129 nghttp3_pq max_cnts; 130 } nghttp3_qpack_stream; 131 132 int nghttp3_qpack_stream_new(nghttp3_qpack_stream **pstream, int64_t stream_id, 133 const nghttp3_mem *mem); 134 135 void nghttp3_qpack_stream_del(nghttp3_qpack_stream *stream, 136 const nghttp3_mem *mem); 137 138 uint64_t nghttp3_qpack_stream_get_max_cnt(const nghttp3_qpack_stream *stream); 139 140 int nghttp3_qpack_stream_add_ref(nghttp3_qpack_stream *stream, 141 nghttp3_qpack_header_block_ref *ref); 142 143 void nghttp3_qpack_stream_pop_ref(nghttp3_qpack_stream *stream); 144 145 #define NGHTTP3_QPACK_ENTRY_OVERHEAD 32 146 147 typedef struct nghttp3_qpack_context { 148 /* dtable is a dynamic table */ 149 nghttp3_ringbuf dtable; 150 /* mem is memory allocator */ 151 const nghttp3_mem *mem; 152 /* dtable_size is abstracted buffer size of dtable as described in 153 the spec. This is the sum of length of name/value in dtable + 154 NGHTTP3_QPACK_ENTRY_OVERHEAD bytes overhead per each entry. */ 155 size_t dtable_size; 156 size_t dtable_sum; 157 /* hard_max_dtable_capacity is the upper bound of 158 max_dtable_capacity. */ 159 size_t hard_max_dtable_capacity; 160 /* max_dtable_capacity is the maximum capacity of the dynamic 161 table. */ 162 size_t max_dtable_capacity; 163 /* max_blocked_streams is the maximum number of stream which can be 164 blocked. */ 165 size_t max_blocked_streams; 166 /* next_absidx is the next absolute index for nghttp3_qpack_entry. 167 It is equivalent to insert count. */ 168 uint64_t next_absidx; 169 /* If inflate/deflate error occurred, this value is set to 1 and 170 further invocation of inflate/deflate will fail with 171 NGHTTP3_ERR_QPACK_FATAL. */ 172 uint8_t bad; 173 } nghttp3_qpack_context; 174 175 typedef struct nghttp3_qpack_read_state { 176 nghttp3_qpack_huffman_decode_context huffman_ctx; 177 nghttp3_buf namebuf; 178 nghttp3_buf valuebuf; 179 nghttp3_rcbuf *name; 180 nghttp3_rcbuf *value; 181 uint64_t left; 182 size_t prefix; 183 size_t shift; 184 uint64_t absidx; 185 int never; 186 int dynamic; 187 int huffman_encoded; 188 } nghttp3_qpack_read_state; 189 190 void nghttp3_qpack_read_state_free(nghttp3_qpack_read_state *rstate); 191 192 void nghttp3_qpack_read_state_reset(nghttp3_qpack_read_state *rstate); 193 194 #define NGHTTP3_QPACK_MAP_SIZE 64 195 196 typedef struct nghttp3_qpack_map { 197 nghttp3_qpack_entry *table[NGHTTP3_QPACK_MAP_SIZE]; 198 } nghttp3_qpack_map; 199 200 /* nghttp3_qpack_decoder_stream_state is a set of states when decoding 201 decoder stream. */ 202 typedef enum nghttp3_qpack_decoder_stream_state { 203 NGHTTP3_QPACK_DS_STATE_OPCODE, 204 NGHTTP3_QPACK_DS_STATE_READ_NUMBER, 205 } nghttp3_qpack_decoder_stream_state; 206 207 /* nghttp3_qpack_decoder_stream_opcode is opcode used in decoder 208 stream. */ 209 typedef enum nghttp3_qpack_decoder_stream_opcode { 210 NGHTTP3_QPACK_DS_OPCODE_ICNT_INCREMENT, 211 NGHTTP3_QPACK_DS_OPCODE_SECTION_ACK, 212 NGHTTP3_QPACK_DS_OPCODE_STREAM_CANCEL, 213 } nghttp3_qpack_decoder_stream_opcode; 214 215 /* QPACK encoder flags */ 216 217 /* NGHTTP3_QPACK_ENCODER_FLAG_NONE indicates that no flag is set. */ 218 #define NGHTTP3_QPACK_ENCODER_FLAG_NONE 0x00u 219 /* NGHTTP3_QPACK_ENCODER_FLAG_PENDING_SET_DTABLE_CAP indicates that 220 Set Dynamic Table Capacity is required. */ 221 #define NGHTTP3_QPACK_ENCODER_FLAG_PENDING_SET_DTABLE_CAP 0x01u 222 223 struct nghttp3_qpack_encoder { 224 nghttp3_qpack_context ctx; 225 /* dtable_map is a map of hash to nghttp3_qpack_entry to provide 226 fast access to an entry in dynamic table. */ 227 nghttp3_qpack_map dtable_map; 228 /* streams is a map of stream ID to nghttp3_qpack_stream to keep 229 track of unacknowledged streams. */ 230 nghttp3_map streams; 231 /* blocked_streams is an ordered list of nghttp3_qpack_stream, in 232 descending order of max_cnt, to search the unblocked streams by 233 received known count. */ 234 nghttp3_ksl blocked_streams; 235 /* min_cnts is a priority queue of nghttp3_qpack_header_block_ref 236 sorted by ascending order of min_cnt to know that an entry can be 237 evicted from dynamic table. */ 238 nghttp3_pq min_cnts; 239 /* krcnt is Known Received Count. */ 240 uint64_t krcnt; 241 /* state is a current state of reading decoder stream. */ 242 nghttp3_qpack_decoder_stream_state state; 243 /* opcode is a decoder stream opcode being processed. */ 244 nghttp3_qpack_decoder_stream_opcode opcode; 245 /* rstate is a set of intermediate state which are used to process 246 decoder stream. */ 247 nghttp3_qpack_read_state rstate; 248 /* min_dtable_update is the minimum dynamic table size required. */ 249 size_t min_dtable_update; 250 /* last_max_dtable_update is the dynamic table size last 251 requested. */ 252 size_t last_max_dtable_update; 253 /* flags is bitwise OR of zero or more of 254 NGHTTP3_QPACK_ENCODER_FLAG_*. */ 255 uint8_t flags; 256 }; 257 258 /* 259 * nghttp3_qpack_encoder_init initializes |encoder|. 260 * |hard_max_dtable_capacity| is the upper bound of the dynamic table 261 * capacity. |mem| is a memory allocator. 262 * 263 * This function returns 0 if it succeeds, or one of the following 264 * negative error codes: 265 * 266 * NGHTTP3_ERR_NOMEM 267 * Out of memory. 268 */ 269 int nghttp3_qpack_encoder_init(nghttp3_qpack_encoder *encoder, 270 size_t hard_max_dtable_capacity, 271 const nghttp3_mem *mem); 272 273 /* 274 * nghttp3_qpack_encoder_free frees memory allocated for |encoder|. 275 * This function does not free memory pointed by |encoder|. 276 */ 277 void nghttp3_qpack_encoder_free(nghttp3_qpack_encoder *encoder); 278 279 /* 280 * nghttp3_qpack_encoder_encode_nv encodes |nv|. It writes request 281 * stream into |rbuf| and writes encoder stream into |ebuf|. |nv| is 282 * a header field to encode. |base| is base. |allow_blocking| is 283 * nonzero if this stream can be blocked (or it has been blocked 284 * already). 285 * 286 * This function returns 0 if it succeeds, or one of the following 287 * negative error codes: 288 * 289 * NGHTTP3_ERR_NOMEM 290 * Out of memory. 291 */ 292 int nghttp3_qpack_encoder_encode_nv(nghttp3_qpack_encoder *encoder, 293 uint64_t *pmax_cnt, uint64_t *pmin_cnt, 294 nghttp3_buf *rbuf, nghttp3_buf *ebuf, 295 const nghttp3_nv *nv, uint64_t base, 296 int allow_blocking); 297 298 /* nghttp3_qpack_lookup_result stores a result of table lookup. */ 299 typedef struct nghttp3_qpack_lookup_result { 300 /* index is an index of matched entry. -1 if no match is made. */ 301 nghttp3_ssize index; 302 /* name_value_match is nonzero if both name and value are 303 matched. */ 304 int name_value_match; 305 /* pb_index is the absolute index of matched post-based dynamic 306 table entry. -1 if no such entry exists. */ 307 nghttp3_ssize pb_index; 308 } nghttp3_qpack_lookup_result; 309 310 /* 311 * nghttp3_qpack_lookup_stable searches |nv| in static table. |token| 312 * is a token of nv->name and it is -1 if there is no corresponding 313 * token defined. |indexing_mode| provides indexing strategy. 314 */ 315 nghttp3_qpack_lookup_result 316 nghttp3_qpack_lookup_stable(const nghttp3_nv *nv, int32_t token, 317 nghttp3_qpack_indexing_mode indexing_mode); 318 319 /* 320 * nghttp3_qpack_encoder_lookup_dtable searches |nv| in dynamic table. 321 * |token| is a token of nv->name and it is -1 if there is no 322 * corresponding token defined. |hash| is a hash of nv->name. 323 * |indexing_mode| provides indexing strategy. |krcnt| is Known 324 * Received Count. |allow_blocking| is nonzero if this stream can be 325 * blocked (or it has been blocked already). 326 */ 327 nghttp3_qpack_lookup_result nghttp3_qpack_encoder_lookup_dtable( 328 nghttp3_qpack_encoder *encoder, const nghttp3_nv *nv, int32_t token, 329 uint32_t hash, nghttp3_qpack_indexing_mode indexing_mode, uint64_t krcnt, 330 int allow_blocking); 331 332 /* 333 * nghttp3_qpack_encoder_write_field_section_prefix writes Encoded 334 * Field Section Prefix into |pbuf|. |ricnt| is Required Insert 335 * Count. |base| is Base. 336 * 337 * This function returns 0 if it succeeds, or one of the following 338 * negative error codes: 339 * 340 * NGHTTP3_ERR_NOMEM 341 * Out of memory. 342 */ 343 int nghttp3_qpack_encoder_write_field_section_prefix( 344 nghttp3_qpack_encoder *encoder, nghttp3_buf *pbuf, uint64_t ricnt, 345 uint64_t base); 346 347 /* 348 * nghttp3_qpack_encoder_write_static_indexed writes Indexed Header 349 * Field to |rbuf|. |absidx| is an absolute index into static table. 350 * 351 * This function returns 0 if it succeeds, or one of the following 352 * negative error codes: 353 * 354 * NGHTTP3_ERR_NOMEM 355 * Out of memory. 356 */ 357 int nghttp3_qpack_encoder_write_static_indexed(nghttp3_qpack_encoder *encoder, 358 nghttp3_buf *rbuf, 359 uint64_t absidx); 360 361 /* 362 * nghttp3_qpack_encoder_write_dynamic_indexed writes Indexed Header 363 * Field to |rbuf|. |absidx| is an absolute index into dynamic table. 364 * |base| is base. 365 * 366 * This function returns 0 if it succeeds, or one of the following 367 * negative error codes: 368 * 369 * NGHTTP3_ERR_NOMEM 370 * Out of memory. 371 */ 372 int nghttp3_qpack_encoder_write_dynamic_indexed(nghttp3_qpack_encoder *encoder, 373 nghttp3_buf *rbuf, 374 uint64_t absidx, uint64_t base); 375 376 /* 377 * nghttp3_qpack_encoder_write_static_indexed writes Literal Header 378 * Field With Name Reference to |rbuf|. |absidx| is an absolute index 379 * into static table to reference a name. |nv| is a header field to 380 * encode. 381 * 382 * This function returns 0 if it succeeds, or one of the following 383 * negative error codes: 384 * 385 * NGHTTP3_ERR_NOMEM 386 * Out of memory. 387 */ 388 int nghttp3_qpack_encoder_write_static_indexed_name( 389 nghttp3_qpack_encoder *encoder, nghttp3_buf *rbuf, uint64_t absidx, 390 const nghttp3_nv *nv); 391 392 /* 393 * nghttp3_qpack_encoder_write_dynamic_indexed writes Literal Header 394 * Field With Name Reference to |rbuf|. |absidx| is an absolute index 395 * into dynamic table to reference a name. |base| is a base. |nv| is 396 * a header field to encode. 397 * 398 * This function returns 0 if it succeeds, or one of the following 399 * negative error codes: 400 * 401 * NGHTTP3_ERR_NOMEM 402 * Out of memory. 403 */ 404 int nghttp3_qpack_encoder_write_dynamic_indexed_name( 405 nghttp3_qpack_encoder *encoder, nghttp3_buf *rbuf, uint64_t absidx, 406 uint64_t base, const nghttp3_nv *nv); 407 408 /* 409 * nghttp3_qpack_encoder_write_literal writes Literal Header Field 410 * With Literal Name to |rbuf|. |nv| is a header field to encode. 411 * 412 * This function returns 0 if it succeeds, or one of the following 413 * negative error codes: 414 * 415 * NGHTTP3_ERR_NOMEM 416 * Out of memory. 417 */ 418 int nghttp3_qpack_encoder_write_literal(nghttp3_qpack_encoder *encoder, 419 nghttp3_buf *rbuf, 420 const nghttp3_nv *nv); 421 422 /* 423 * nghttp3_qpack_encoder_write_static_insert writes Insert With Name 424 * Reference to |ebuf|. |absidx| is an absolute index into static 425 * table to reference a name. |nv| is a header field to insert. 426 * 427 * This function returns 0 if it succeeds, or one of the following 428 * negative error codes: 429 * 430 * NGHTTP3_ERR_NOMEM 431 * Out of memory. 432 */ 433 int nghttp3_qpack_encoder_write_static_insert(nghttp3_qpack_encoder *encoder, 434 nghttp3_buf *ebuf, 435 uint64_t absidx, 436 const nghttp3_nv *nv); 437 438 /* 439 * nghttp3_qpack_encoder_write_dynamic_insert writes Insert With Name 440 * Reference to |ebuf|. |absidx| is an absolute index into dynamic 441 * table to reference a name. |nv| is a header field to insert. 442 * 443 * This function returns 0 if it succeeds, or one of the following 444 * negative error codes: 445 * 446 * NGHTTP3_ERR_NOMEM 447 * Out of memory. 448 */ 449 int nghttp3_qpack_encoder_write_dynamic_insert(nghttp3_qpack_encoder *encoder, 450 nghttp3_buf *ebuf, 451 uint64_t absidx, 452 const nghttp3_nv *nv); 453 454 /* 455 * nghttp3_qpack_encoder_write_duplicate_insert writes Duplicate to 456 * |ebuf|. |absidx| is an absolute index into dynamic table to 457 * reference an entry. 458 * 459 * This function returns 0 if it succeeds, or one of the following 460 * negative error codes: 461 * 462 * NGHTTP3_ERR_NOMEM 463 * Out of memory. 464 */ 465 int nghttp3_qpack_encoder_write_duplicate_insert(nghttp3_qpack_encoder *encoder, 466 nghttp3_buf *ebuf, 467 uint64_t absidx); 468 469 /* 470 * nghttp3_qpack_encoder_write_literal_insert writes Insert With 471 * Literal Name to |ebuf|. |nv| is a header field to insert. 472 * 473 * This function returns 0 if it succeeds, or one of the following 474 * negative error codes: 475 * 476 * NGHTTP3_ERR_NOMEM 477 * Out of memory. 478 */ 479 int nghttp3_qpack_encoder_write_literal_insert(nghttp3_qpack_encoder *encoder, 480 nghttp3_buf *ebuf, 481 const nghttp3_nv *nv); 482 483 int nghttp3_qpack_encoder_stream_is_blocked(nghttp3_qpack_encoder *encoder, 484 nghttp3_qpack_stream *stream); 485 486 /* 487 * nghttp3_qpack_encoder_block_stream blocks |stream|. 488 * 489 * This function returns 0 if it succeeds, or one of the following 490 * negative error codes: 491 * 492 * NGHTTP3_ERR_NOMEM 493 * Out of memory. 494 */ 495 int nghttp3_qpack_encoder_block_stream(nghttp3_qpack_encoder *encoder, 496 nghttp3_qpack_stream *stream); 497 498 /* 499 * nghttp3_qpack_encoder_unblock_stream unblocks |stream|. 500 */ 501 void nghttp3_qpack_encoder_unblock_stream(nghttp3_qpack_encoder *encoder, 502 nghttp3_qpack_stream *stream); 503 504 /* 505 * nghttp3_qpack_encoder_unblock unblocks stream whose max_cnt is less 506 * than or equal to |max_cnt|. 507 */ 508 void nghttp3_qpack_encoder_unblock(nghttp3_qpack_encoder *encoder, 509 uint64_t max_cnt); 510 511 /* 512 * nghttp3_qpack_encoder_find_stream returns stream whose stream ID is 513 * |stream_id|. This function returns NULL if there is no such 514 * stream. 515 */ 516 nghttp3_qpack_stream * 517 nghttp3_qpack_encoder_find_stream(nghttp3_qpack_encoder *encoder, 518 int64_t stream_id); 519 520 uint64_t nghttp3_qpack_encoder_get_min_cnt(nghttp3_qpack_encoder *encoder); 521 522 /* 523 * nghttp3_qpack_encoder_shrink_dtable shrinks dynamic table so that 524 * the dynamic table size is less than or equal to maximum size. 525 */ 526 void nghttp3_qpack_encoder_shrink_dtable(nghttp3_qpack_encoder *encoder); 527 528 /* 529 * nghttp3_qpack_encoder_process_dtable_update processes pending 530 * dynamic table size update. It might write encoder stream into 531 * |ebuf|. 532 * 533 * This function returns 0 if it succeeds, or one of the following 534 * negative error codes: 535 * 536 * NGHTTP3_ERR_NOMEM 537 * Out of memory. 538 */ 539 int nghttp3_qpack_encoder_process_dtable_update(nghttp3_qpack_encoder *encoder, 540 nghttp3_buf *ebuf); 541 542 /* 543 * nghttp3_qpack_encoder_write_set_dtable_cap writes Set Dynamic Table 544 * Capacity. to |ebuf|. |cap| is the capacity of dynamic table. 545 * 546 * This function returns 0 if it succeeds, or one of the following 547 * negative error codes: 548 * 549 * NGHTTP3_ERR_NOMEM 550 * Out of memory. 551 */ 552 int nghttp3_qpack_encoder_write_set_dtable_cap(nghttp3_qpack_encoder *encoder, 553 nghttp3_buf *ebuf, size_t cap); 554 555 /* 556 * nghttp3_qpack_context_dtable_add adds |qnv| to dynamic table. If 557 * |ctx| is a part of encoder, |dtable_map| is not NULL. |hash| is a 558 * hash value of name. 559 * 560 * This function returns 0 if it succeeds, or one of the following 561 * negative error codes: 562 * 563 * NGHTTP3_ERR_NOMEM 564 * Out of memory. 565 */ 566 int nghttp3_qpack_context_dtable_add(nghttp3_qpack_context *ctx, 567 nghttp3_qpack_nv *qnv, 568 nghttp3_qpack_map *dtable_map, 569 uint32_t hash); 570 571 /* 572 * nghttp3_qpack_encoder_dtable_static_add adds |nv| to dynamic table 573 * by referencing static table entry at an absolute index |absidx|. 574 * The hash of name is given as |hash|. 575 * 576 * This function returns 0 if it succeeds, or one of the following 577 * negative error codes: 578 * 579 * NGHTTP3_ERR_NOMEM 580 * Out of memory. 581 */ 582 int nghttp3_qpack_encoder_dtable_static_add(nghttp3_qpack_encoder *encoder, 583 uint64_t absidx, 584 const nghttp3_nv *nv, 585 uint32_t hash); 586 587 /* 588 * nghttp3_qpack_encoder_dtable_dynamic_add adds |nv| to dynamic table 589 * by referencing dynamic table entry at an absolute index |absidx|. 590 * The hash of name is given as |hash|. 591 * 592 * This function returns 0 if it succeeds, or one of the following 593 * negative error codes: 594 * 595 * NGHTTP3_ERR_NOMEM 596 * Out of memory. 597 */ 598 int nghttp3_qpack_encoder_dtable_dynamic_add(nghttp3_qpack_encoder *encoder, 599 uint64_t absidx, 600 const nghttp3_nv *nv, 601 uint32_t hash); 602 603 /* 604 * nghttp3_qpack_encoder_dtable_duplicate_add duplicates dynamic table 605 * entry at an absolute index |absidx|. 606 * 607 * This function returns 0 if it succeeds, or one of the following 608 * negative error codes: 609 * 610 * NGHTTP3_ERR_NOMEM 611 * Out of memory. 612 */ 613 int nghttp3_qpack_encoder_dtable_duplicate_add(nghttp3_qpack_encoder *encoder, 614 uint64_t absidx); 615 616 /* 617 * nghttp3_qpack_encoder_dtable_literal_add adds |nv| to dynamic 618 * table. |token| is a token of name and is -1 if it has no token 619 * value defined. |hash| is a hash of name. 620 * 621 * NGHTTP3_ERR_NOMEM Out of memory. 622 */ 623 int nghttp3_qpack_encoder_dtable_literal_add(nghttp3_qpack_encoder *encoder, 624 const nghttp3_nv *nv, 625 int32_t token, uint32_t hash); 626 627 /* 628 * `nghttp3_qpack_encoder_ack_header` tells |encoder| that header 629 * block for a stream denoted by |stream_id| was acknowledged by 630 * decoder. 631 * 632 * This function returns 0 if it succeeds, or one of the following 633 * negative error codes: 634 * 635 * :macro:`NGHTTP3_ERR_QPACK_DECODER_STREAM_ERROR` 636 * Section Acknowledgement for a stream denoted by |stream_id| is 637 * unexpected. 638 */ 639 int nghttp3_qpack_encoder_ack_header(nghttp3_qpack_encoder *encoder, 640 int64_t stream_id); 641 642 /* 643 * `nghttp3_qpack_encoder_add_icnt` increments known received count of 644 * |encoder| by |n|. 645 * 646 * This function returns 0 if it succeeds, or one of the following 647 * negative error codes: 648 * 649 * :macro:`NGHTTP3_ERR_NOMEM` 650 * Out of memory. 651 * :macro:`NGHTTP3_ERR_QPACK_DECODER_STREAM_ERROR` 652 * |n| is too large. 653 */ 654 int nghttp3_qpack_encoder_add_icnt(nghttp3_qpack_encoder *encoder, uint64_t n); 655 656 /* 657 * `nghttp3_qpack_encoder_cancel_stream` tells |encoder| that stream 658 * denoted by |stream_id| is cancelled. This function is provided for 659 * debugging purpose only. In HTTP/3, |encoder| knows this by reading 660 * decoder stream with `nghttp3_qpack_encoder_read_decoder()`. 661 */ 662 void nghttp3_qpack_encoder_cancel_stream(nghttp3_qpack_encoder *encoder, 663 int64_t stream_id); 664 665 /* 666 * nghttp3_qpack_context_dtable_get returns dynamic table entry whose 667 * absolute index is |absidx|. This function assumes that such entry 668 * exists. 669 */ 670 nghttp3_qpack_entry * 671 nghttp3_qpack_context_dtable_get(nghttp3_qpack_context *ctx, uint64_t absidx); 672 673 /* 674 * nghttp3_qpack_context_dtable_top returns latest dynamic table 675 * entry. This function assumes dynamic table is not empty. 676 */ 677 nghttp3_qpack_entry * 678 nghttp3_qpack_context_dtable_top(nghttp3_qpack_context *ctx); 679 680 /* 681 * nghttp3_qpack_entry_init initializes |ent|. |qnv| is a header 682 * field. |sum| is the sum of table space occupied by all entries 683 * inserted so far. It does not include this entry. |absidx| is an 684 * absolute index of this entry. |hash| is a hash of header field 685 * name. This function increases reference count of qnv->nv.name and 686 * qnv->nv.value. 687 */ 688 void nghttp3_qpack_entry_init(nghttp3_qpack_entry *ent, nghttp3_qpack_nv *qnv, 689 size_t sum, uint64_t absidx, uint32_t hash); 690 691 /* 692 * nghttp3_qpack_entry_free frees memory allocated for |ent|. 693 */ 694 void nghttp3_qpack_entry_free(nghttp3_qpack_entry *ent); 695 696 /* 697 * nghttp3_qpack_put_varint_len returns the required number of bytes 698 * to encode |n| with |prefix| bits. 699 */ 700 size_t nghttp3_qpack_put_varint_len(uint64_t n, size_t prefix); 701 702 /* 703 * nghttp3_qpack_put_varint encodes |n| using variable integer 704 * encoding with |prefix| bits into |buf|. This function assumes the 705 * buffer pointed by |buf| has enough space. This function returns 706 * the one byte beyond the last write (buf + 707 * nghttp3_qpack_put_varint_len(n, prefix)). 708 */ 709 uint8_t *nghttp3_qpack_put_varint(uint8_t *buf, uint64_t n, size_t prefix); 710 711 /* nghttp3_qpack_encoder_stream_state is a set of states for encoder 712 stream decoding. */ 713 typedef enum nghttp3_qpack_encoder_stream_state { 714 NGHTTP3_QPACK_ES_STATE_OPCODE, 715 NGHTTP3_QPACK_ES_STATE_READ_INDEX, 716 NGHTTP3_QPACK_ES_STATE_CHECK_NAME_HUFFMAN, 717 NGHTTP3_QPACK_ES_STATE_READ_NAMELEN, 718 NGHTTP3_QPACK_ES_STATE_READ_NAME_HUFFMAN, 719 NGHTTP3_QPACK_ES_STATE_READ_NAME, 720 NGHTTP3_QPACK_ES_STATE_CHECK_VALUE_HUFFMAN, 721 NGHTTP3_QPACK_ES_STATE_READ_VALUELEN, 722 NGHTTP3_QPACK_ES_STATE_READ_VALUE_HUFFMAN, 723 NGHTTP3_QPACK_ES_STATE_READ_VALUE, 724 } nghttp3_qpack_encoder_stream_state; 725 726 /* nghttp3_qpack_encoder_stream_opcode is a set of opcodes used in 727 encoder stream. */ 728 typedef enum nghttp3_qpack_encoder_stream_opcode { 729 NGHTTP3_QPACK_ES_OPCODE_INSERT_INDEXED, 730 NGHTTP3_QPACK_ES_OPCODE_INSERT, 731 NGHTTP3_QPACK_ES_OPCODE_DUPLICATE, 732 NGHTTP3_QPACK_ES_OPCODE_SET_DTABLE_CAP, 733 } nghttp3_qpack_encoder_stream_opcode; 734 735 /* nghttp3_qpack_request_stream_state is a set of states for request 736 stream decoding. */ 737 typedef enum nghttp3_qpack_request_stream_state { 738 NGHTTP3_QPACK_RS_STATE_RICNT, 739 NGHTTP3_QPACK_RS_STATE_DBASE_SIGN, 740 NGHTTP3_QPACK_RS_STATE_DBASE, 741 NGHTTP3_QPACK_RS_STATE_OPCODE, 742 NGHTTP3_QPACK_RS_STATE_READ_INDEX, 743 NGHTTP3_QPACK_RS_STATE_CHECK_NAME_HUFFMAN, 744 NGHTTP3_QPACK_RS_STATE_READ_NAMELEN, 745 NGHTTP3_QPACK_RS_STATE_READ_NAME_HUFFMAN, 746 NGHTTP3_QPACK_RS_STATE_READ_NAME, 747 NGHTTP3_QPACK_RS_STATE_CHECK_VALUE_HUFFMAN, 748 NGHTTP3_QPACK_RS_STATE_READ_VALUELEN, 749 NGHTTP3_QPACK_RS_STATE_READ_VALUE_HUFFMAN, 750 NGHTTP3_QPACK_RS_STATE_READ_VALUE, 751 NGHTTP3_QPACK_RS_STATE_BLOCKED, 752 } nghttp3_qpack_request_stream_state; 753 754 /* nghttp3_qpack_request_stream_opcode is a set of opcodes used in 755 request stream. */ 756 typedef enum nghttp3_qpack_request_stream_opcode { 757 NGHTTP3_QPACK_RS_OPCODE_INDEXED, 758 NGHTTP3_QPACK_RS_OPCODE_INDEXED_PB, 759 NGHTTP3_QPACK_RS_OPCODE_INDEXED_NAME, 760 NGHTTP3_QPACK_RS_OPCODE_INDEXED_NAME_PB, 761 NGHTTP3_QPACK_RS_OPCODE_LITERAL, 762 } nghttp3_qpack_request_stream_opcode; 763 764 struct nghttp3_qpack_decoder { 765 nghttp3_qpack_context ctx; 766 /* state is a current state of reading encoder stream. */ 767 nghttp3_qpack_encoder_stream_state state; 768 /* opcode is an encoder stream opcode being processed. */ 769 nghttp3_qpack_encoder_stream_opcode opcode; 770 /* rstate is a set of intermediate state which are used to process 771 encoder stream. */ 772 nghttp3_qpack_read_state rstate; 773 /* dbuf is decoder stream. */ 774 nghttp3_buf dbuf; 775 /* written_icnt is Insert Count written to decoder stream so far. */ 776 uint64_t written_icnt; 777 /* max_concurrent_streams is the number of concurrent streams that a 778 remote endpoint can open, including both bidirectional and 779 unidirectional streams which potentially receives QPACK encoded 780 HEADER frame. */ 781 size_t max_concurrent_streams; 782 }; 783 784 /* 785 * nghttp3_qpack_decoder_init initializes |decoder|. 786 * |hard_max_dtable_capacity| is the upper bound of the dynamic table 787 * capacity. |max_blocked_streams| is the maximum number of stream 788 * which can be blocked. |mem| is a memory allocator. 789 * 790 * This function returns 0 if it succeeds, or one of the following 791 * negative error codes: 792 * 793 * NGHTTP3_ERR_NOMEM 794 * Out of memory. 795 */ 796 int nghttp3_qpack_decoder_init(nghttp3_qpack_decoder *decoder, 797 size_t hard_max_dtable_capacity, 798 size_t max_blocked_streams, 799 const nghttp3_mem *mem); 800 801 /* 802 * nghttp3_qpack_decoder_free frees memory allocated for |decoder|. 803 * This function does not free memory pointed by |decoder|. 804 */ 805 void nghttp3_qpack_decoder_free(nghttp3_qpack_decoder *decoder); 806 807 /* 808 * nghttp3_qpack_decoder_dtable_indexed_add adds entry received in 809 * Insert With Name Reference to dynamic table. 810 * 811 * This function returns 0 if it succeeds, or one of the following 812 * negative error codes: 813 * 814 * NGHTTP3_ERR_NOMEM 815 * Out of memory. 816 * NGHTTP3_ERR_QPACK_ENCODER_STREAM 817 * Space required for a decoded entry exceeds max dynamic table 818 * size. 819 */ 820 int nghttp3_qpack_decoder_dtable_indexed_add(nghttp3_qpack_decoder *decoder); 821 822 /* 823 * nghttp3_qpack_decoder_dtable_static_add adds entry received in 824 * Insert With Name Reference (static) to dynamic table. 825 * 826 * This function returns 0 if it succeeds, or one of the following 827 * negative error codes: 828 * 829 * NGHTTP3_ERR_NOMEM 830 * Out of memory. 831 * NGHTTP3_ERR_QPACK_ENCODER_STREAM 832 * Space required for a decoded entry exceeds max dynamic table 833 * size. 834 */ 835 int nghttp3_qpack_decoder_dtable_static_add(nghttp3_qpack_decoder *decoder); 836 837 /* 838 * nghttp3_qpack_decoder_dtable_dynamic_add adds entry received in 839 * Insert With Name Reference (dynamic) to dynamic table. 840 * 841 * This function returns 0 if it succeeds, or one of the following 842 * negative error codes: 843 * 844 * NGHTTP3_ERR_NOMEM 845 * Out of memory. 846 * NGHTTP3_ERR_QPACK_ENCODER_STREAM 847 * Space required for a decoded entry exceeds max dynamic table 848 * size. 849 */ 850 int nghttp3_qpack_decoder_dtable_dynamic_add(nghttp3_qpack_decoder *decoder); 851 852 /* 853 * nghttp3_qpack_decoder_dtable_duplicate_add adds entry received in 854 * Duplicate to dynamic table. 855 * 856 * This function returns 0 if it succeeds, or one of the following 857 * negative error codes: 858 * 859 * NGHTTP3_ERR_NOMEM 860 * Out of memory. 861 * NGHTTP3_ERR_QPACK_ENCODER_STREAM 862 * Space required for a decoded entry exceeds max dynamic table 863 * size. 864 */ 865 int nghttp3_qpack_decoder_dtable_duplicate_add(nghttp3_qpack_decoder *decoder); 866 867 /* 868 * nghttp3_qpack_decoder_dtable_literal_add adds entry received in 869 * Insert With Literal Name to dynamic table. 870 * 871 * This function returns 0 if it succeeds, or one of the following 872 * negative error codes: 873 * 874 * NGHTTP3_ERR_NOMEM 875 * Out of memory. 876 * NGHTTP3_ERR_QPACK_ENCODER_STREAM 877 * Space required for a decoded entry exceeds max dynamic table 878 * size. 879 */ 880 int nghttp3_qpack_decoder_dtable_literal_add(nghttp3_qpack_decoder *decoder); 881 882 struct nghttp3_qpack_stream_context { 883 /* state is a current state of reading request stream. */ 884 nghttp3_qpack_request_stream_state state; 885 /* rstate is a set of intermediate state which are used to process 886 request stream. */ 887 nghttp3_qpack_read_state rstate; 888 const nghttp3_mem *mem; 889 /* opcode is a request stream opcode being processed. */ 890 nghttp3_qpack_request_stream_opcode opcode; 891 int64_t stream_id; 892 /* ricnt is Required Insert Count to decode this header block. */ 893 uint64_t ricnt; 894 /* base is Base in Header Block Prefix. */ 895 uint64_t base; 896 /* dbase_sign is the delta base sign in Header Block Prefix. */ 897 int dbase_sign; 898 }; 899 900 /* 901 * nghttp3_qpack_stream_context_init initializes |sctx|. 902 */ 903 void nghttp3_qpack_stream_context_init(nghttp3_qpack_stream_context *sctx, 904 int64_t stream_id, 905 const nghttp3_mem *mem); 906 907 /* 908 * nghttp3_qpack_stream_context_free frees memory allocated for 909 * |sctx|. This function does not free memory pointed by |sctx|. 910 */ 911 void nghttp3_qpack_stream_context_free(nghttp3_qpack_stream_context *sctx); 912 913 /* 914 * nghttp3_qpack_decoder_reconstruct_ricnt reconstructs Required 915 * Insert Count from the encoded form |encricnt| and stores Required 916 * Insert Count in |*dest|. 917 * 918 * This function returns 0 if it succeeds, or one of the following 919 * negative error codes: 920 * 921 * NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED 922 * Unable to reconstruct Required Insert Count. 923 */ 924 int nghttp3_qpack_decoder_reconstruct_ricnt(nghttp3_qpack_decoder *decoder, 925 uint64_t *dest, uint64_t encricnt); 926 927 /* 928 * nghttp3_qpack_decoder_rel2abs converts relative index rstate->left 929 * received in encoder stream to absolute index and stores it in 930 * rstate->absidx. 931 * 932 * This function returns 0 if it succeeds, or one of the following 933 * negative error codes: 934 * 935 * NGHTTP3_ERR_QPACK_ENCODER_STREAM 936 * Relative index is invalid. 937 */ 938 int nghttp3_qpack_decoder_rel2abs(nghttp3_qpack_decoder *decoder, 939 nghttp3_qpack_read_state *rstate); 940 941 /* 942 * nghttp3_qpack_decoder_brel2abs converts Base relative index 943 * rstate->left received in request stream to absolute index and 944 * stores it in rstate->absidx. 945 * 946 * This function returns 0 if it succeeds, or one of the following 947 * negative error codes: 948 * 949 * NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED 950 * Base relative index is invalid. 951 */ 952 int nghttp3_qpack_decoder_brel2abs(nghttp3_qpack_decoder *decoder, 953 nghttp3_qpack_stream_context *sctx); 954 955 /* 956 * nghttp3_qpack_decoder_pbrel2abs converts Post-Base relative index 957 * rstate->left received in request stream to absolute index and 958 * stores it in rstate->absidx. 959 * 960 * This function returns 0 if it succeeds, or one of the following 961 * negative error codes: 962 * 963 * NGHTTP3_ERR_QPACK_DECOMPRESSION_FAILED 964 * Post-Base relative index is invalid. 965 */ 966 int nghttp3_qpack_decoder_pbrel2abs(nghttp3_qpack_decoder *decoder, 967 nghttp3_qpack_stream_context *sctx); 968 969 void nghttp3_qpack_decoder_emit_indexed(nghttp3_qpack_decoder *decoder, 970 nghttp3_qpack_stream_context *sctx, 971 nghttp3_qpack_nv *nv); 972 973 int nghttp3_qpack_decoder_emit_indexed_name(nghttp3_qpack_decoder *decoder, 974 nghttp3_qpack_stream_context *sctx, 975 nghttp3_qpack_nv *nv); 976 977 void nghttp3_qpack_decoder_emit_literal(nghttp3_qpack_decoder *decoder, 978 nghttp3_qpack_stream_context *sctx, 979 nghttp3_qpack_nv *nv); 980 981 /* 982 * nghttp3_qpack_decoder_write_section_ack writes Section 983 * Acknowledgement to decoder stream. 984 * 985 * This function returns 0 if it succeeds, or one of the following 986 * negative error codes: 987 * 988 * NGHTTP3_ERR_NOMEM 989 * Out of memory. 990 * NGHTTP3_ERR_QPACK_FATAL 991 * Decoder stream overflow. 992 */ 993 int nghttp3_qpack_decoder_write_section_ack( 994 nghttp3_qpack_decoder *decoder, const nghttp3_qpack_stream_context *sctx); 995 996 #endif /* NGHTTP3_QPACK_H */ 997