mhd_hpack_codec.c (243042B)
1 /* SPDX-License-Identifier: LGPL-2.1-or-later OR (GPL-2.0-or-later WITH eCos-exception-2.0) */ 2 /* 3 This file is part of GNU libmicrohttpd. 4 Copyright (C) 2025 Evgeny Grin (Karlson2k) 5 6 GNU libmicrohttpd is free software; you can redistribute it and/or 7 modify it under the terms of the GNU Lesser General Public 8 License as published by the Free Software Foundation; either 9 version 2.1 of the License, or (at your option) any later version. 10 11 GNU libmicrohttpd is distributed in the hope that it will be useful, 12 but WITHOUT ANY WARRANTY; without even the implied warranty of 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14 Lesser General Public License for more details. 15 16 Alternatively, you can redistribute GNU libmicrohttpd and/or 17 modify it under the terms of the GNU General Public License as 18 published by the Free Software Foundation; either version 2 of 19 the License, or (at your option) any later version, together 20 with the eCos exception, as follows: 21 22 As a special exception, if other files instantiate templates or 23 use macros or inline functions from this file, or you compile this 24 file and link it with other works to produce a work based on this 25 file, this file does not by itself cause the resulting work to be 26 covered by the GNU General Public License. However the source code 27 for this file must still be made available in accordance with 28 section (3) of the GNU General Public License v2. 29 30 This exception does not invalidate any other reasons why a work 31 based on this file might be covered by the GNU General Public 32 License. 33 34 You should have received copies of the GNU Lesser General Public 35 License and the GNU General Public License along with this library; 36 if not, see <https://www.gnu.org/licenses/>. 37 */ 38 39 /** 40 * @file src/mhd2/h2/hpack/mhd_hpack_codec.c 41 * @brief The implementation of the HPACK header-compression codec functions. 42 * @author Karlson2k (Evgeny Grin) 43 * 44 * The sizes of all strings are intentionally limited to 32 bits (4GiB). 45 * The sizes of all strings in the dynamic table are limited to 32 or 16 bits, 46 * depending on value of #mhd_HPACK_DTBL_BITS macro. 47 */ 48 49 #include "mhd_sys_options.h" 50 51 #include "sys_bool_type.h" 52 #include "sys_base_types.h" 53 #include "sys_malloc.h" 54 #include <string.h> 55 56 #include "mhd_constexpr.h" 57 #include "mhd_align.h" 58 59 #include "mhd_assert.h" 60 #include "mhd_unreachable.h" 61 #include "mhd_predict.h" 62 63 #include "mhd_bithelpers.h" 64 65 #include "mhd_str_types.h" 66 #include "mhd_str_macros.h" 67 #include "mhd_buffer.h" 68 69 #include "mhd_tristate.h" 70 #include "mhd_hpack_dec_types.h" 71 #include "mhd_hpack_enc_types.h" 72 73 #include "mhd_hpack_codec.h" 74 #if ! defined(mhd_HPACK_TESTING_TABLES_ONLY) || ! defined(MHD_UNIT_TESTING) 75 # include "h2_huffman_codec.h" 76 # include "h2_huffman_est.h" 77 #endif 78 79 80 /** 81 * Number of entries in the static table 82 */ 83 #define mhd_HPACK_STBL_ENTRIES (61u) 84 85 /** 86 * The last HPACK index number in the static table 87 */ 88 #define mhd_HPACK_STBL_LAST_IDX mhd_HPACK_STBL_ENTRIES 89 90 91 /* ****** ----------------- Dynamic table handling ----------------- ****** */ 92 93 /* ======================================================================== 94 * 95 * The dynamic tables should be accessed only by mhd_* functions. 96 * 97 * All functions prefixed with dtbl_* are internal helpers and should not 98 * be used directly. 99 * 100 * ======================================================================== 101 */ 102 103 #if mhd_HPACK_DTBL_BITS == 32 104 /** 105 * A type used to store sizes of dynamic table elements. 106 * 107 * This is a compact type; it uses the minimal amount of memory. 108 */ 109 typedef uint_least32_t dtbl_size_t; 110 /** 111 * A type used to operate on sizes of dynamic and static table elements 112 * 113 * This type should be more friendly for faster processing by CPU. 114 * It could be the same underlying type as @a dtbl_size_t 115 */ 116 typedef uint_fast32_t dtbl_size_ft; 117 /** 118 * A type used to store the number of dynamic and static table elements 119 * 120 * This is a compact type; it uses the minimal amount of memory. 121 */ 122 typedef uint_least32_t dtbl_idx_t; 123 /** 124 * A type used to operate and address dynamic and static table elements 125 * 126 * This type should be more friendly for faster processing by CPU. 127 * It could be the same underlying type as @a dtbl_idx_t 128 */ 129 typedef uint_fast32_t dtbl_idx_ft; 130 /** 131 * Check whether value @a val fits 32 bits type. 132 * 133 * If any non-zero bit is set above the lowest 32 bits, the macro returns 134 * boolean false. 135 * 136 * This macro strictly checks whether the provided value is suitable for use 137 * in dynamic table elements. Even if the underlying type uint_least32_t is 138 * wider than 32 bits, this macro enforces the limit to 32 bits only. 139 * 140 * This macro is designed to work only with unsigned types. No signed types 141 * are used in dynamic table data. 142 * 143 * The parameter is evaluated only once. 144 */ 145 # define mhd_DTBL_VALUE_FITS(val) (0xFFFFFFFFu == ((val) | 0xFFFFFFFFu)) 146 #elif mhd_HPACK_DTBL_BITS == 16 147 /** 148 * A type used to store sizes of dynamic table elements. 149 * 150 * This is a compact type; it uses the minimal amount of memory. 151 */ 152 typedef uint_least16_t dtbl_size_t; 153 /** 154 * A type used to operate sizes of dynamic and static table elements 155 * 156 * This type should be more friendly for faster processing by CPU. 157 * It could be the same underlying type as @a dtbl_size_t 158 */ 159 typedef uint_fast16_t dtbl_size_ft; 160 /** 161 * A type used to store the number of dynamic and static table elements 162 * 163 * This is a compact type; it uses the minimal amount of memory. 164 */ 165 typedef uint_least16_t dtbl_idx_t; 166 /** 167 * A type used to operate and address dynamic and static table elements 168 * 169 * This type should be more friendly for faster processing by CPU. 170 * It could be the same underlying type as @a dtbl_idx_t 171 */ 172 typedef uint_fast16_t dtbl_idx_ft; 173 /** 174 * Check whether value @a val fits 16 bits type. 175 * 176 * If any non-zero bit is set above the lowest 16 bits, the macro returns 177 * boolean false. 178 * 179 * This macro strictly checks whether the provided value is suitable for use 180 * in dynamic table elements. Even if the underlying type uint_least16_t is 181 * wider than 16 bits, this macro enforces the limit to 16 bits only. 182 * 183 * This macro is designed to work only with unsigned types. No signed types 184 * are used in dynamic table data. 185 * 186 * The parameter is evaluated only once. 187 */ 188 # define mhd_DTBL_VALUE_FITS(val) (0xFFFFu == ((val) | 0xFFFFu)) 189 #else 190 #error Unsupported mhd_HPACK_DTBL_BITS value 191 #endif 192 193 194 /** 195 * The data for a dynamic table entry 196 */ 197 struct mhd_HpackDTblEntryInfo 198 { 199 /** 200 * The offset of the name in the buffer 201 */ 202 dtbl_size_t offset; 203 /** 204 * The length of the name string. 205 * The name string is not zero-terminated. 206 */ 207 dtbl_size_t name_len; 208 /** 209 * The length of the value string. 210 * The value is located at @a offset + @a name_len. 211 * The value string is not zero-terminated. 212 */ 213 dtbl_size_t val_len; 214 }; 215 216 /** 217 * Size (in bytes) of one dynamic-table entry-information record. 218 */ 219 #define mhd_DTBL_ENTRY_INFO_SIZE \ 220 ((dtbl_size_t) (sizeof(struct mhd_HpackDTblEntryInfo))) 221 222 /** 223 * HPACK dynamic-table per-entry overhead, in bytes (RFC 7541 4.1). 224 * 225 * The macro is needed to statically initialise mhd_dtbl_entry_slack 226 * in C11 mode (as 'static const' variable). 227 */ 228 #define mhd_HPACK_ENTRY_OVERHEAD (32u) 229 230 /** 231 * HPACK dynamic-table per-entry overhead, in bytes (RFC 7541 4.1). 232 * The size of a dynamic-table entry is: 233 * 32 + length(header field name) + length(header field value), 234 * where both lengths are in bytes as defined in RFC 7541 5.2. 235 */ 236 mhd_constexpr dtbl_size_t mhd_dtbl_entry_overhead = 237 mhd_HPACK_ENTRY_OVERHEAD; 238 239 240 /** 241 * The extra slack between entries in the strings buffer. 242 * Used when there is extra space while adding a new entry. 243 * This extra slack reduces the need to move strings in the buffer when the 244 * entry is evicted and the strings are replaced with the new entry's strings. 245 * 246 * If strings are placed optimally (with this slack), then one entry took 247 * exactly the formal HPACK size in the buffer (strings + entry information 248 * data). 249 */ 250 mhd_constexpr dtbl_size_t mhd_dtbl_entry_slack = 251 mhd_HPACK_ENTRY_OVERHEAD - mhd_DTBL_ENTRY_INFO_SIZE; 252 253 /** 254 * The first HPACK index in the dynamic table 255 */ 256 mhd_constexpr dtbl_idx_t mhd_dtbl_hpack_idx_offset = 257 mhd_HPACK_STBL_LAST_IDX + 1u; 258 259 /** 260 * The maximum possible HPACK index when largest possible size of the dynamic 261 * table is used 262 */ 263 #define mhd_HPACK_MAX_POSSIBLE_IDX \ 264 ((mhd_DTBL_MAX_SIZE / mhd_HPACK_ENTRY_OVERHEAD) \ 265 + mhd_HPACK_STBL_LAST_IDX) 266 267 /** 268 * Get the formal HPACK size of the potential new entry. 269 * @param strings_len the total size of the strings (the length of the name of 270 * the field + the length of the value of the field) 271 * @return the formal HPACK size of the potential new entry 272 */ 273 MHD_FN_PURE_ mhd_static_inline dtbl_size_t 274 dtbl_new_entry_strs_size_formal (dtbl_size_ft strings_len) 275 { 276 dtbl_size_ft formal_size = strings_len + mhd_dtbl_entry_overhead; 277 mhd_assert (strings_len < formal_size); 278 mhd_assert (mhd_DTBL_VALUE_FITS (strings_len)); 279 mhd_assert (mhd_DTBL_VALUE_FITS (formal_size)); 280 return (dtbl_size_t) formal_size; 281 } 282 283 284 /** 285 * Get the formal HPACK size of the potential new entry. 286 * @param name_len the length of the name of the field 287 * @param val_len the length of the value of the field 288 * @return the formal HPACK size of the potential new entry 289 */ 290 MHD_FN_PURE_ mhd_static_inline dtbl_size_t 291 dtbl_new_entry_size_formal (dtbl_size_ft name_len, 292 dtbl_size_ft val_len) 293 { 294 const dtbl_size_ft entry_strs_size = name_len + val_len; 295 mhd_assert (val_len <= entry_strs_size); 296 mhd_assert (mhd_DTBL_VALUE_FITS (entry_strs_size)); 297 mhd_assert (mhd_DTBL_VALUE_FITS (name_len)); 298 mhd_assert (mhd_DTBL_VALUE_FITS (val_len)); 299 return dtbl_new_entry_strs_size_formal (entry_strs_size); 300 } 301 302 303 /** 304 * Get the total size of the strings of the entry. 305 * This is the minimal size required for the entry in the strings buffer. 306 * @param entr_inf the pointer to the entry info 307 * @return the total size of the strings of the entry 308 */ 309 MHD_FN_PURE_ mhd_static_inline dtbl_size_t 310 dtbl_entr_strs_size_min (const struct mhd_HpackDTblEntryInfo *entr_inf) 311 { 312 return entr_inf->name_len + entr_inf->val_len; 313 } 314 315 316 /** 317 * Get the total size of the strings of the entry plus standard slack size. 318 * This is the optimal size used for the entry in the strings buffer when the 319 * current insertion slot has enough space. 320 * @param entr_inf the pointer to the entry info 321 * @return the total size of the strings of the entry plus standard slack size 322 */ 323 MHD_FN_PURE_ mhd_static_inline dtbl_size_t 324 dtbl_entr_strs_size_optm (const struct mhd_HpackDTblEntryInfo *entr_inf) 325 { 326 return dtbl_entr_strs_size_min (entr_inf) + mhd_dtbl_entry_slack; 327 } 328 329 330 /** 331 * Get the formal HPACK size of the entry. 332 * The formal size of the entry is the size of the strings plus fixed 333 * HPACK per-entry overhead. 334 * @param entr_inf the pointer to the entry info 335 * @return the formal HPACK size of the entry 336 */ 337 MHD_FN_PURE_ mhd_static_inline dtbl_size_t 338 dtbl_entr_size_formal (const struct mhd_HpackDTblEntryInfo *entr_inf) 339 { 340 const dtbl_size_t ret = dtbl_new_entry_size_formal (entr_inf->name_len, 341 entr_inf->val_len); 342 mhd_assert (dtbl_entr_strs_size_min (entr_inf) + mhd_dtbl_entry_overhead == \ 343 ret); 344 return ret; 345 } 346 347 348 /** 349 * Get the position (offset) of the (inclusive) start of the entry's strings 350 * in the strings buffer. 351 * This points to the first byte of the entry's strings. If the entry has 352 * zero-length strings, the pointer denotes a (possibly zero-sized) area 353 * that may coincide with the start of the entry's slack (if any) or with 354 * the next entry's strings start (if present). 355 * @param entr_inf the pointer to the entry info 356 * @return the position (offset) of the (inclusive) start of the entry's strings 357 */ 358 MHD_FN_PURE_ mhd_static_inline dtbl_size_t 359 dtbl_entr_strs_start (const struct mhd_HpackDTblEntryInfo *entr_inf) 360 { 361 return entr_inf->offset; 362 } 363 364 365 /** 366 * Get the position of the (exclusive) end of the entry's strings in the 367 * strings buffer. 368 * This points to the next char (byte) after the strings of the entry. 369 * @param entr_inf the pointer to the entry info 370 * @return the position of the end of the entry's strings in the strings buffer 371 */ 372 MHD_FN_PURE_ mhd_static_inline dtbl_size_t 373 dtbl_entr_strs_end_min (const struct mhd_HpackDTblEntryInfo *entr_inf) 374 { 375 return dtbl_entr_strs_start (entr_inf) + dtbl_entr_strs_size_min (entr_inf); 376 } 377 378 379 /** 380 * Get the position (offset) immediately after the standard slack following the 381 * end of the entry's strings in the strings buffer. 382 * This points to the preferred position of the next entry's strings. 383 * @param entr_inf the pointer to the entry info 384 * @return the position (offset) immediately after the standard slack 385 */ 386 MHD_FN_PURE_ mhd_static_inline dtbl_size_t 387 dtbl_entr_strs_end_optm (const struct mhd_HpackDTblEntryInfo *entr_inf) 388 { 389 return dtbl_entr_strs_start (entr_inf) + dtbl_entr_strs_size_optm (entr_inf); 390 } 391 392 393 /* 394 * The dynamic HPACK table is organised as follows: 395 * + The shared buffer is placed immediately after mhd_HpackDTblContext in 396 * memory. 397 * + The buffer stores both the strings (names and values) and the entry info 398 * data (one mhd_HpackDTblEntryInfo per entry). 399 * + Strings grow upward from the bottom of the buffer (lower addresses), while 400 * entry-info data grow downward from the top of the buffer (higher 401 * addresses). 402 * + Because the buffer is shared, the same area may be used either by strings 403 * (few entries with large strings) or by entry info data (many entries with 404 * small strings). 405 * + The topmost entry info data corresponds to the bottommost strings, and 406 * vice versa. 407 * + Both regions (strings and entry info data) effectively form two circular 408 * buffers that dynamically share the same memory space region: the bottom 409 * part is strings area (filled from bottom to up) and the upper part is 410 * entries info data area (filled from top to down). See also "zero position" 411 * and the "edge entry" below. 412 * + The table data tracks the newest entry; the new entries are added at 413 * higher (than the newest entry) location numbers. 414 * + HPACK indices are counted in the opposite direction (the smallest HPACK 415 * index refers to the newest entry; the next entry's location number is the 416 * newest location minus one). 417 * + Because the size of an entry info (sizeof(struct mhd_HpackDTblEntryInfo)) 418 * is smaller than the mandatory HPACK per-entry overhead (32 bytes), 419 * strings are inserted with an additional slack when there is enough space 420 * before the next entry's strings. 421 * 422 * Terminology used below: 423 * + "entry info" (or "entry information data") -- mhd_HpackDTblEntryInfo data. 424 * + "zero position entry" -- the entry whose strings are at the bottom of the 425 * buffer and whose entry info data is at the very top of the buffer. This 426 * is the first entry added to an empty table. 427 * + "edge entry" -- the entry whose strings lie above all other strings and 428 * whose entry info data lies below all other entry info data. Any space 429 * between this entry's strings and its entry info data is not used by 430 * other entries. 431 * + "newest" (or latest) entry -- the most recently added entry (the 432 * lowest HPACK index). 433 * + "oldest" entry -- the entry added before all other current entries; its 434 * strings immediately follow the newest entry's strings (or are at location 435 * zero if the newest entry is the edge entry). Its entry info data 436 * immediately precedes the newest entry's data (or is at the top if the 437 * newest entry is the edge entry). 438 */ 439 440 /** 441 * Dynamic HPACK table data 442 */ 443 struct mhd_HpackDTblContext 444 { 445 /** 446 * The size of the allocated buffer. 447 * The buffer is located in memory right after this structure. 448 */ 449 dtbl_size_t buf_alloc_size; 450 451 /** 452 * The current number of entries used 453 */ 454 dtbl_idx_t num_entries; 455 456 /** 457 * Offset of the current newest (most recently added) entry; it also has 458 * the lowest HPACK index. 459 * The "next" entry (newest_pos + 1, or 0 when the newest entry is the 460 * edge entry (newest_pos == num_entries - 1)) is the oldest entry and 461 * is evicted first if needed. 462 * When a new entry is added, newest_pos is incremented or wrapped to 0 463 * (when the newest entry is at the edge and insertion wraps). 464 */ 465 dtbl_idx_t newest_pos; 466 467 /** 468 * The cached value of the official table size (as defined by HPACK). 469 * Used to speed up calculations. Can be re-created from entries information. 470 */ 471 dtbl_size_t cur_size; 472 473 /** 474 * The dynamic table size limit as defined by HPACK 475 */ 476 dtbl_size_t size_limit; 477 }; 478 479 480 /* **** ---------- Dynamic table internal helpers -------------- **** */ 481 482 /* ** Basic table information ** */ 483 484 485 /** 486 * Get the number of entries in the table 487 * @param dyn the pointer to the dynamic table structure 488 * @return the number of entries in the table 489 */ 490 MHD_FN_PURE_ mhd_static_inline dtbl_idx_t 491 dtbl_get_num_entries (const struct mhd_HpackDTblContext *dyn) 492 { 493 return dyn->num_entries; 494 } 495 496 497 /** 498 * Check whether the table is empty (no entries) 499 * @param dyn the pointer to the dynamic table structure 500 * @return 'true' if table has no entries, 501 * 'false' otherwise 502 */ 503 MHD_FN_PURE_ mhd_static_inline bool 504 dtbl_is_empty (const struct mhd_HpackDTblContext *dyn) 505 { 506 mhd_assert ((0u == dyn->num_entries) == (0u == dyn->cur_size)); 507 return (0u == dtbl_get_num_entries (dyn)); 508 } 509 510 511 /** 512 * Get the pointer to the strings buffer 513 * @param dyn the pointer to the dynamic table structure 514 * @return the pointer to the strings buffer 515 */ 516 MHD_FN_CONST_ mhd_static_inline char * 517 dtbl_get_strs_buff (struct mhd_HpackDTblContext *dyn) 518 { 519 return (char*) 520 (dyn + 1u); 521 } 522 523 524 /** 525 * Get a const pointer to the strings buffer 526 * @param dyn the pointer to the dynamic table structure 527 * @return const pointer to the strings buffer 528 */ 529 MHD_FN_CONST_ mhd_static_inline const char * 530 dtbl_get_strs_buffc (const struct mhd_HpackDTblContext *dyn) 531 { 532 return (const char*) 533 (dyn + 1u); 534 } 535 536 537 /** 538 * Get the pointer to the top (by location in memory) dynamic table entry data. 539 * The entries info data grow downward. 540 * @param dyn the pointer to the dynamic table structure 541 * @return the pointer to the top (by location in memory) entry data 542 */ 543 MHD_FN_PURE_ mhd_static_inline struct mhd_HpackDTblEntryInfo * 544 dtbl_get_infos (struct mhd_HpackDTblContext *dyn) 545 { 546 return ((struct mhd_HpackDTblEntryInfo *) 547 (void *) 548 (dtbl_get_strs_buff (dyn) + dyn->buf_alloc_size)) - 1u; 549 } 550 551 552 /** 553 * Get a const pointer to the top (by location in memory) dynamic table entry 554 * data. 555 * The entries info data grow downward. 556 * @param dyn const pointer to the dynamic table structure 557 * @return const pointer to the top (by location in memory) entry data 558 */ 559 MHD_FN_PURE_ mhd_static_inline const struct mhd_HpackDTblEntryInfo * 560 dtbl_get_infosc (const struct mhd_HpackDTblContext *dyn) 561 { 562 return ((const struct mhd_HpackDTblEntryInfo *) 563 (const void *) 564 (dtbl_get_strs_buffc (dyn) + dyn->buf_alloc_size)) - 1u; 565 } 566 567 568 /** 569 * Get the position of the entry located at the edge of the buffer. 570 * 571 * This is the entry with the strings located above all other strings 572 * and the entry information data located below all other entries information 573 * data. 574 * 575 * If any space is left between entry's strings data and information data, this 576 * space is not used by other entries. 577 * 578 * The result is undefined if the table has no entries. 579 * @param dyn the pointer to the dynamic table structure 580 * @return the position of the edge entry, 581 * undefined if the table has no entries 582 */ 583 MHD_FN_PURE_ mhd_static_inline dtbl_idx_t 584 dtbl_get_pos_edge (const struct mhd_HpackDTblContext *dyn) 585 { 586 mhd_assert (! dtbl_is_empty (dyn)); 587 mhd_assert (dyn->buf_alloc_size >= 588 mhd_DTBL_ENTRY_INFO_SIZE * dyn->num_entries); 589 return (dtbl_idx_t) (dyn->num_entries - 1u); 590 } 591 592 593 /** 594 * Get the position of the previous entry for the specified entry position. 595 * 596 * This is a position of the entry previous to the specified entry position. 597 * The returned value is one less than the specified position or wraps to the 598 * edge position when the specified position is zero. 599 * 600 * The result is undefined if the table has no entries. 601 * @param dyn the pointer to the dynamic table structure 602 * @param loc_pos the number of location position 603 * @return the position of the previous entry for specified entry position, 604 * undefined if the table has no entries 605 */ 606 MHD_FN_PURE_ mhd_static_inline dtbl_idx_t 607 dtbl_get_pos_prev (const struct mhd_HpackDTblContext *dyn, 608 dtbl_idx_ft loc_pos) 609 { 610 mhd_assert (! dtbl_is_empty (dyn)); 611 mhd_assert (loc_pos <= dtbl_get_pos_edge (dyn)); 612 #ifdef MHD_USE_CODE_HARDENING 613 if (0u == loc_pos) 614 return dtbl_get_pos_edge (dyn); 615 return (dtbl_idx_t) (loc_pos - 1u); 616 #else /* ! MHD_USE_CODE_HARDENING */ 617 return (dtbl_idx_t) ((dyn->num_entries + loc_pos - 1u) % dyn->num_entries); 618 #endif /* ! MHD_USE_CODE_HARDENING */ 619 } 620 621 622 /** 623 * Get the position of the next entry for the specified entry position. 624 * 625 * This is a position of the entry next to the specified entry position. 626 * The returned value is greater by one than specified position or wraps to 627 * zero if the specified position is edge position. 628 * 629 * The result is undefined if the table has no entries. 630 * @param dyn the pointer to the dynamic table structure 631 * @param loc_pos the number of location position 632 * @return the position of the next entry for the specified entry position, 633 * undefined if the table has no entries 634 */ 635 MHD_FN_PURE_ mhd_static_inline dtbl_idx_t 636 dtbl_get_pos_next (const struct mhd_HpackDTblContext *dyn, 637 dtbl_idx_ft loc_pos) 638 { 639 mhd_assert (! dtbl_is_empty (dyn)); 640 mhd_assert (loc_pos <= dtbl_get_pos_edge (dyn)); 641 #ifdef MHD_USE_CODE_HARDENING 642 if (dtbl_get_pos_edge (dyn) == loc_pos) 643 return 0u; 644 return (dtbl_idx_t) (loc_pos + 1u); 645 #else /* ! MHD_USE_CODE_HARDENING */ 646 return (dtbl_idx_t) ((dyn->num_entries + loc_pos + 1u) % dyn->num_entries); 647 #endif /* ! MHD_USE_CODE_HARDENING */ 648 } 649 650 651 /** 652 * Get the position of the newest entry. 653 * 654 * This is a position of the last added entry. 655 * 656 * The result is undefined if the table has no entries. 657 * @param dyn the pointer to the dynamic table structure 658 * @return the position of the newest entry, 659 * undefined if the table has no entries 660 */ 661 MHD_FN_PURE_ mhd_static_inline dtbl_idx_t 662 dtbl_get_pos_newest (const struct mhd_HpackDTblContext *dyn) 663 { 664 mhd_assert (! dtbl_is_empty (dyn)); 665 return dyn->newest_pos; 666 } 667 668 669 /** 670 * Get the position of the oldest entry. 671 * 672 * This is a position of the current oldest entry in the table. This entry 673 * is evicted first if eviction is needed. 674 * 675 * The result is undefined if the table has no entries. 676 * @param dyn the pointer to the dynamic table structure 677 * @return the position of the oldest entry, 678 * undefined if the table has no entries 679 */ 680 MHD_FN_PURE_ mhd_static_inline dtbl_idx_t 681 dtbl_get_pos_oldest (const struct mhd_HpackDTblContext *dyn) 682 { 683 return dtbl_get_pos_next (dyn, 684 dtbl_get_pos_newest (dyn)); 685 } 686 687 688 /** 689 * Convert an HPACK table index to the position number in the dynamic table. 690 * 691 * The result is undefined if the specified index is less than or equal to the 692 * number of entries in the static table. 693 * The result is undefined if the specified index is larger than the last valid 694 * HPACK index in the table. 695 * @param dyn the pointer to the dynamic table structure 696 * @param hpack_idx the HPACK index of the entry 697 * @return the position of the requested entry in the table, 698 * undefined if the @a hpack_idx is not valid for the table 699 */ 700 MHD_FN_PURE_ mhd_static_inline dtbl_idx_t 701 dtbl_get_pos_from_hpack_idx (const struct mhd_HpackDTblContext *dyn, 702 dtbl_idx_ft hpack_idx) 703 { 704 dtbl_idx_ft pos_back_from_newest = 705 (dtbl_idx_ft) (hpack_idx - mhd_dtbl_hpack_idx_offset); 706 mhd_assert (mhd_DTBL_VALUE_FITS (hpack_idx)); 707 mhd_assert (mhd_HPACK_STBL_LAST_IDX < hpack_idx); 708 mhd_assert (dtbl_get_num_entries (dyn) + mhd_dtbl_hpack_idx_offset > \ 709 hpack_idx); 710 711 #ifdef MHD_USE_CODE_HARDENING 712 if (dtbl_get_pos_newest (dyn) >= pos_back_from_newest) 713 return (dtbl_idx_t) (dtbl_get_pos_newest (dyn) - pos_back_from_newest); 714 return (dtbl_idx_t) (dtbl_get_num_entries (dyn) + dtbl_get_pos_newest (dyn) 715 - pos_back_from_newest); 716 #else /* ! MHD_USE_CODE_HARDENING */ 717 return 718 (dtbl_idx_t) 719 ((dtbl_get_num_entries (dyn) 720 + dtbl_get_pos_newest (dyn) - pos_back_from_newest) 721 % dtbl_get_num_entries (dyn)); 722 #endif /* ! MHD_USE_CODE_HARDENING */ 723 } 724 725 726 /** 727 * Convert a dynamic-table location position to the corresponding HPACK index. 728 * 729 * This is the inverse of #dtbl_get_pos_from_hpack_idx(). 730 * The returned HPACK index is strictly greater than the last index in the 731 * static table (#mhd_HPACK_STBL_LAST_IDX). 732 * 733 * Behaviour is undefined if @a loc_pos is not a valid position for @a dyn. 734 * @param dyn the pointer to the dynamic table structure 735 * @param loc_pos the location position number (0 .. #dtbl_get_pos_edge()) 736 * @return the HPACK index corresponding to @a loc_pos 737 * undefined if the @a loc_pos is not valid for the table 738 */ 739 MHD_FN_PURE_ mhd_static_inline dtbl_idx_t 740 dtbl_get_hpack_idx_from_pos (const struct mhd_HpackDTblContext *dyn, 741 dtbl_idx_ft loc_pos) 742 { 743 mhd_assert (mhd_DTBL_VALUE_FITS (loc_pos)); 744 mhd_assert (dtbl_get_pos_edge (dyn) >= loc_pos); 745 746 #ifdef MHD_USE_CODE_HARDENING 747 if (dtbl_get_pos_newest (dyn) >= loc_pos) 748 return (dtbl_idx_t) (dtbl_get_pos_newest (dyn) - loc_pos 749 + mhd_dtbl_hpack_idx_offset); 750 return (dtbl_idx_t) (dtbl_get_num_entries (dyn) + dtbl_get_pos_newest (dyn) 751 - loc_pos + mhd_dtbl_hpack_idx_offset); 752 #else /* ! MHD_USE_CODE_HARDENING */ 753 return 754 (dtbl_idx_t) 755 (((dtbl_get_num_entries (dyn) + dtbl_get_pos_newest (dyn) - loc_pos)) 756 % dtbl_get_num_entries (dyn) + mhd_dtbl_hpack_idx_offset); 757 #endif /* ! MHD_USE_CODE_HARDENING */ 758 } 759 760 761 /** 762 * Get the current exclusive upper bound (in bytes) for valid offsets 763 * within the strings region. 764 765 * This equals the distance from the start of the strings region to the first 766 * byte occupied by entry-information data. As more entry information is added, 767 * this limit decreases. For an empty table, the limit equals buf_alloc_size. 768 * @param dyn the pointer to the dynamic table structure 769 * @return the current exclusive upper bound for offsets in the strings region 770 */ 771 MHD_FN_PURE_ mhd_static_inline dtbl_size_t 772 dtbl_get_strs_ceiling (const struct mhd_HpackDTblContext *dyn) 773 { 774 dtbl_size_ft ceiling = 775 dyn->buf_alloc_size 776 - (dtbl_size_ft) mhd_DTBL_ENTRY_INFO_SIZE * dyn->num_entries; 777 778 mhd_assert (dyn->buf_alloc_size >= 779 mhd_DTBL_ENTRY_INFO_SIZE * dyn->num_entries); 780 mhd_assert (mhd_DTBL_VALUE_FITS (ceiling)); 781 782 return (dtbl_size_t) ceiling; 783 } 784 785 786 /** 787 * Get the formal maximum HPACK size in the table. 788 * @param dyn the pointer to the dynamic table structure 789 * @return the formal HPACK size in the table 790 */ 791 MHD_FN_PURE_ mhd_static_inline dtbl_size_t 792 dtbl_get_size_max_formal (const struct mhd_HpackDTblContext *dyn) 793 { 794 return dyn->size_limit; 795 } 796 797 798 /** 799 * Get the amount of formal HPACK free space in the table. 800 * @param dyn the pointer to the dynamic table structure 801 * @return the formal HPACK free space in the table 802 */ 803 MHD_FN_PURE_ mhd_static_inline dtbl_size_t 804 dtbl_get_free_formal (const struct mhd_HpackDTblContext *dyn) 805 { 806 mhd_assert (dyn->size_limit >= dyn->cur_size); 807 return dyn->size_limit - dyn->cur_size; 808 } 809 810 811 /** 812 * Get the amount of formal HPACK used space in the table. 813 * @param dyn the pointer to the dynamic table structure 814 * @return the formal HPACK used space in the table 815 */ 816 MHD_FN_PURE_ mhd_static_inline dtbl_size_t 817 dtbl_get_used_formal (const struct mhd_HpackDTblContext *dyn) 818 { 819 mhd_assert (dyn->size_limit >= dyn->cur_size); 820 return dyn->cur_size; 821 } 822 823 824 /* ** Location of entry information data based on entry position in the 825 table ** */ 826 827 /** 828 * Get the pointer to the dynamic table entry by location position number. 829 * This is not the same as HPACK index. 830 * The result is undefined if the table has no entries. 831 * @param dyn the pointer to the dynamic table structure 832 * @param loc_pos the number of location position 833 * @return the pointer to the dynamic table entry, 834 * undefined if the table has no entries 835 */ 836 MHD_FN_PURE_ mhd_static_inline struct mhd_HpackDTblEntryInfo * 837 dtbl_pos_entry_info (struct mhd_HpackDTblContext *dyn, 838 dtbl_idx_ft loc_pos) 839 { 840 mhd_assert (mhd_DTBL_VALUE_FITS (loc_pos)); 841 mhd_assert (! dtbl_is_empty (dyn)); 842 mhd_assert (dyn->num_entries > loc_pos); 843 mhd_assert (dyn->buf_alloc_size >= 844 mhd_DTBL_ENTRY_INFO_SIZE * dyn->num_entries); 845 return dtbl_get_infos (dyn) - loc_pos; 846 } 847 848 849 /** 850 * Get a const pointer to the dynamic table entry by location position number. 851 * This is not the same as HPACK index. 852 * The result is undefined if the table has no entries. 853 * @param dyn const pointer to the dynamic table structure 854 * @param loc_pos the number of location position 855 * @return the pointer to the dynamic table entry, 856 * undefined if the table has no entries 857 */ 858 MHD_FN_PURE_ mhd_static_inline const struct mhd_HpackDTblEntryInfo * 859 dtbl_pos_entry_infoc (const struct mhd_HpackDTblContext *dyn, 860 dtbl_idx_ft loc_pos) 861 { 862 mhd_assert (mhd_DTBL_VALUE_FITS (loc_pos)); 863 mhd_assert (! dtbl_is_empty (dyn)); 864 mhd_assert (dyn->num_entries > loc_pos); 865 mhd_assert (dyn->buf_alloc_size >= 866 mhd_DTBL_ENTRY_INFO_SIZE * dyn->num_entries); 867 return dtbl_get_infosc (dyn) - loc_pos; 868 } 869 870 871 /** 872 * Get the pointer to the zero location entry information data. 873 * This is the highest address of the entries data location in the table. 874 * The result is undefined if the table has no entries. 875 * @param dyn the pointer to the dynamic table structure 876 * @return the pointer to the zero location entry info data, 877 * undefined if the table has no entries 878 */ 879 MHD_FN_PURE_ mhd_static_inline struct mhd_HpackDTblEntryInfo * 880 dtbl_zero_entry_info (struct mhd_HpackDTblContext *dyn) 881 { 882 return dtbl_pos_entry_info (dyn, 883 0u); 884 } 885 886 887 /** 888 * Get a const pointer to the zero location entry information data. 889 * This is the highest address of the entries data location in the table. 890 * The result is undefined if the table has no entries. 891 * @param dyn the pointer to the dynamic table structure 892 * @return const pointer to the zero location entry information data, 893 * undefined if the table has no entries 894 */ 895 MHD_FN_PURE_ mhd_static_inline const struct mhd_HpackDTblEntryInfo * 896 dtbl_zero_entry_infoc (const struct mhd_HpackDTblContext *dyn) 897 { 898 return dtbl_pos_entry_infoc (dyn, 899 0u); 900 } 901 902 903 /** 904 * Get the pointer to the table's edge entry information data. 905 * This is the lowest address of the entries data location in the table. 906 * The result is undefined if the table has no entries. 907 * @param dyn the pointer to the dynamic table structure 908 * @return the pointer to the table's edge entry information data, 909 * undefined if the table has no entries 910 */ 911 MHD_FN_PURE_ mhd_static_inline struct mhd_HpackDTblEntryInfo * 912 dtbl_edge_entry_info (struct mhd_HpackDTblContext *dyn) 913 { 914 struct mhd_HpackDTblEntryInfo *const ptr = 915 dtbl_pos_entry_info (dyn, 916 dtbl_get_pos_edge (dyn)); 917 mhd_assert (((const void *) ptr) == \ 918 ((const void *) (dtbl_get_strs_buffc (dyn) 919 + dtbl_get_strs_ceiling (dyn)))); 920 return ptr; 921 } 922 923 924 /** 925 * Get a const pointer to the table edge entry information data. 926 * This is the lowest address of the entries data location in the table. 927 * The result is undefined if the table has no entries. 928 * @param dyn the pointer to the dynamic table structure 929 * @return const pointer to the table edge entry information data, 930 * undefined if the table has no entries 931 */ 932 MHD_FN_PURE_ mhd_static_inline const struct mhd_HpackDTblEntryInfo * 933 dtbl_edge_entry_infoc (const struct mhd_HpackDTblContext *dyn) 934 { 935 const struct mhd_HpackDTblEntryInfo *const ptr = 936 dtbl_pos_entry_infoc (dyn, 937 dtbl_get_pos_edge (dyn)); 938 mhd_assert (((const void *) ptr) == \ 939 ((const void *) (dtbl_get_strs_buffc (dyn) 940 + dtbl_get_strs_ceiling (dyn)))); 941 return ptr; 942 } 943 944 945 /** 946 * Get the pointer to the newest entry information data. 947 * The result is undefined if the table has no entries. 948 * @param dyn the pointer to the dynamic table structure 949 * @return the pointer to the newest entry information data, 950 * undefined if the table has no entries 951 */ 952 MHD_FN_PURE_ mhd_static_inline struct mhd_HpackDTblEntryInfo * 953 dtbl_newest_entry_info (struct mhd_HpackDTblContext *dyn) 954 { 955 return dtbl_pos_entry_info (dyn, 956 dtbl_get_pos_newest (dyn)); 957 } 958 959 960 /** 961 * Get a const pointer to the newest entry information data. 962 * The result is undefined if the table has no entries. 963 * @param dyn const pointer to the dynamic table structure 964 * @return const pointer to the newest entry information data, 965 * undefined if the table has no entries 966 */ 967 MHD_FN_PURE_ mhd_static_inline const struct mhd_HpackDTblEntryInfo * 968 dtbl_newest_entry_infoc (const struct mhd_HpackDTblContext *dyn) 969 { 970 return dtbl_pos_entry_infoc (dyn, 971 dtbl_get_pos_newest (dyn)); 972 } 973 974 975 /** 976 * Get the pointer to the oldest entry information data. 977 * The result is undefined if the table has no entries. 978 * @param dyn the pointer to the dynamic table structure 979 * @return the pointer to the oldest entry information data, 980 * undefined if the table has no entries 981 */ 982 MHD_FN_PURE_ mhd_static_inline struct mhd_HpackDTblEntryInfo * 983 dtbl_oldest_entry_info (struct mhd_HpackDTblContext *dyn) 984 { 985 return dtbl_pos_entry_info (dyn, 986 dtbl_get_pos_oldest (dyn)); 987 } 988 989 990 /** 991 * Get a const pointer to the oldest entry information data. 992 * The result is undefined if the table has no entries. 993 * @param dyn const pointer to the dynamic table structure 994 * @return const pointer to the oldest entry information data, 995 * undefined if the table has no entries 996 */ 997 MHD_FN_PURE_ mhd_static_inline const struct mhd_HpackDTblEntryInfo * 998 dtbl_oldest_entry_infoc (const struct mhd_HpackDTblContext *dyn) 999 { 1000 return dtbl_pos_entry_infoc (dyn, 1001 dtbl_get_pos_oldest (dyn)); 1002 } 1003 1004 1005 /* ** Entries strings information based on the entry position in the table ** */ 1006 1007 /** 1008 * Get the total size of the strings of the entry. 1009 * This is the minimal size required for the entry in the strings buffer. 1010 * @param dyn the pointer to the dynamic table structure 1011 * @param loc_pos the number of location position 1012 * @return the total size of the strings of the entry 1013 */ 1014 MHD_FN_PURE_ mhd_static_inline dtbl_size_t 1015 dtbl_pos_strs_size_min (const struct mhd_HpackDTblContext *dyn, 1016 dtbl_idx_ft loc_pos) 1017 { 1018 return dtbl_entr_strs_size_min (dtbl_pos_entry_infoc (dyn, 1019 loc_pos)); 1020 } 1021 1022 1023 /** 1024 * Get the total size of the strings of the entry plus standard slack size. 1025 * This is the optimal size used for the entry in the strings buffer when the 1026 * current insertion slot has enough space. 1027 * @param dyn the pointer to the dynamic table structure 1028 * @param loc_pos the number of location position 1029 * @return the total size of the strings of the entry plus standard slack size 1030 */ 1031 MHD_FN_PURE_ mhd_static_inline dtbl_size_t 1032 dtbl_pos_strs_size_optm (const struct mhd_HpackDTblContext *dyn, 1033 dtbl_idx_ft loc_pos) 1034 { 1035 return dtbl_entr_strs_size_optm (dtbl_pos_entry_infoc (dyn, 1036 loc_pos)); 1037 } 1038 1039 1040 /** 1041 * Get the formal HPACK size of the entry. 1042 * The formal size of the entry is the size of the strings plus fixed 1043 * HPACK per-entry overhead. 1044 * @param dyn the pointer to the dynamic table structure 1045 * @param loc_pos the number of location position 1046 * @return the formal HPACK size of the entry 1047 */ 1048 MHD_FN_PURE_ mhd_static_inline dtbl_size_t 1049 dtbl_pos_size_formal (const struct mhd_HpackDTblContext *dyn, 1050 dtbl_idx_ft loc_pos) 1051 { 1052 return dtbl_entr_size_formal (dtbl_pos_entry_infoc (dyn, 1053 loc_pos)); 1054 } 1055 1056 1057 /** 1058 * Get the position (offset) of the (inclusive) start of the entry's strings 1059 * in the strings buffer. 1060 * This points to the first byte of the entry's strings. If the entry has 1061 * zero-length strings, the pointer denotes a (possibly zero-sized) area 1062 * that may coincide with the start of the entry's slack (if any) or with 1063 * the next entry's strings start (if present). 1064 * @param dyn the pointer to the dynamic table structure 1065 * @param loc_pos the number of location position 1066 * @return the position (offset) of the (inclusive) start of the entry's strings 1067 */ 1068 MHD_FN_PURE_ mhd_static_inline dtbl_size_t 1069 dtbl_pos_strs_start (const struct mhd_HpackDTblContext *dyn, 1070 dtbl_idx_ft loc_pos) 1071 { 1072 return dtbl_entr_strs_start (dtbl_pos_entry_infoc (dyn, 1073 loc_pos)); 1074 } 1075 1076 1077 /** 1078 * Get the position of the (exclusive) end of the entry's strings in the 1079 * strings buffer. 1080 * This points to the next char (byte) after the strings of the entry. 1081 * @param dyn the pointer to the dynamic table structure 1082 * @param loc_pos the number of location position 1083 * @return the position of the end of the entry's strings in the strings buffer 1084 */ 1085 MHD_FN_PURE_ mhd_static_inline dtbl_size_t 1086 dtbl_pos_strs_end_min (const struct mhd_HpackDTblContext *dyn, 1087 dtbl_idx_ft loc_pos) 1088 { 1089 return dtbl_entr_strs_end_min (dtbl_pos_entry_infoc (dyn, 1090 loc_pos)); 1091 } 1092 1093 1094 /** 1095 * Get the position after standard slack after the end of the entry's strings 1096 * in the strings buffer. 1097 * This points to the preferred position of the next entry's strings. 1098 * @param dyn the pointer to the dynamic table structure 1099 * @param loc_pos the number of location position 1100 * @return the position of the end of the entry's strings in the strings buffer 1101 */ 1102 MHD_FN_PURE_ mhd_static_inline dtbl_size_t 1103 dtbl_pos_strs_end_optm (const struct mhd_HpackDTblContext *dyn, 1104 dtbl_idx_ft loc_pos) 1105 { 1106 return dtbl_entr_strs_end_optm (dtbl_pos_entry_infoc (dyn, 1107 loc_pos)); 1108 } 1109 1110 1111 /* ** Entries strings location information based on the pointer to the 1112 entry ** */ 1113 1114 /** 1115 * Get a pointer to the (inclusive) start of the entry's strings in the 1116 * strings buffer. 1117 * This points to the first byte of the entry's strings. If the entry has 1118 * zero-length strings, the pointer denotes a (possibly zero-sized) area 1119 * that may coincide with the start of the entry's slack (if any) or with 1120 * the next entry's strings start (if present). 1121 * The result is undefined if the entry is not in the table. 1122 * @param dyn the pointer to the dynamic table structure 1123 * @param entr_inf the pointer to the entry information 1124 * @return the pointer of the (inclusive) start of the entry's strings, 1125 * result is undefined if the entry is not in the table 1126 */ 1127 MHD_FN_PURE_ mhd_static_inline char * 1128 dtbl_entr_strs_ptr_start (struct mhd_HpackDTblContext *dyn, 1129 const struct mhd_HpackDTblEntryInfo *entr_inf) 1130 { 1131 mhd_assert (dtbl_zero_entry_infoc (dyn) >= entr_inf); 1132 mhd_assert (dtbl_edge_entry_infoc (dyn) <= entr_inf); 1133 return dtbl_get_strs_buff (dyn) + dtbl_entr_strs_start (entr_inf); 1134 } 1135 1136 1137 /** 1138 * Get const pointer to the (inclusive) start of the entry's strings in the 1139 * strings buffer. 1140 * This points to the first byte of the entry's strings. If the entry has 1141 * zero-length strings, the pointer denotes a (possibly zero-sized) area 1142 * that may coincide with the start of the entry's slack (if any) or with 1143 * the next entry's strings start (if present). 1144 * The result is undefined if the entry is not in the table. 1145 * @param dyn the pointer to the dynamic table structure 1146 * @param entr_inf the pointer to the entry information 1147 * @return const pointer of the (inclusive) start of the entry's strings, 1148 * result is undefined if the entry is not in the table 1149 */ 1150 MHD_FN_PURE_ mhd_static_inline const char * 1151 dtbl_entr_strs_ptr_startc (const struct mhd_HpackDTblContext *dyn, 1152 const struct mhd_HpackDTblEntryInfo *entr_inf) 1153 { 1154 mhd_assert (dtbl_zero_entry_infoc (dyn) >= entr_inf); 1155 mhd_assert (dtbl_edge_entry_infoc (dyn) <= entr_inf); 1156 return dtbl_get_strs_buffc (dyn) + dtbl_entr_strs_start (entr_inf); 1157 } 1158 1159 1160 /** 1161 * Get a pointer to the (exclusive) end of the entry's strings in the 1162 * strings buffer. 1163 * This points to the next char (byte) after the strings of the entry. 1164 * The result is undefined if the entry is not in the table. 1165 * @param dyn the pointer to the dynamic table structure 1166 * @param entr_inf the pointer to the entry information 1167 * @return the pointer to the (exclusive) end of the entry's strings, 1168 * result is undefined if the entry is not in the table 1169 */ 1170 MHD_FN_PURE_ mhd_static_inline char * 1171 dtbl_entr_strs_ptr_end (struct mhd_HpackDTblContext *dyn, 1172 const struct mhd_HpackDTblEntryInfo *entr_inf) 1173 { 1174 mhd_assert (dtbl_zero_entry_infoc (dyn) >= entr_inf); 1175 mhd_assert (dtbl_edge_entry_infoc (dyn) <= entr_inf); 1176 return dtbl_get_strs_buff (dyn) + dtbl_entr_strs_end_min (entr_inf); 1177 } 1178 1179 1180 /** 1181 * Get a const pointer to the (exclusive) end of the entry's strings in the 1182 * strings buffer. 1183 * This points to the next char (byte) after the strings of the entry. 1184 * The result is undefined if the entry is not in the table. 1185 * @param dyn const pointer to the dynamic table structure 1186 * @param entr_inf const pointer to the entry information 1187 * @return const pointer to the (exclusive) end of the entry's strings, 1188 * result is undefined if the entry is not in the table 1189 */ 1190 MHD_FN_PURE_ mhd_static_inline const char * 1191 dtbl_entr_strs_ptr_endc (const struct mhd_HpackDTblContext *dyn, 1192 const struct mhd_HpackDTblEntryInfo *entr_inf) 1193 { 1194 mhd_assert (dtbl_zero_entry_infoc (dyn) >= entr_inf); 1195 mhd_assert (dtbl_edge_entry_infoc (dyn) <= entr_inf); 1196 return dtbl_get_strs_buffc (dyn) + dtbl_entr_strs_end_min (entr_inf); 1197 } 1198 1199 1200 /** 1201 * Get a const pointer to the (exclusive) end of the entry's standard slack 1202 * after the entry's strings in the strings buffer. 1203 * This points to the preferred location of the next entry's strings. 1204 * The result is undefined if the entry is not in the table. 1205 * @param dyn const pointer to the dynamic table structure 1206 * @param entr_inf const pointer to the entry information 1207 * @return const pointer to the (exclusive) end of the entry's standard slack, 1208 * result is undefined if the entry is not in the table 1209 */ 1210 MHD_FN_PURE_ mhd_static_inline const char * 1211 dtbl_entr_strs_ptr_end_slackc (const struct mhd_HpackDTblContext *dyn, 1212 const struct mhd_HpackDTblEntryInfo *entr_inf) 1213 { 1214 mhd_assert (dtbl_zero_entry_infoc (dyn) >= entr_inf); 1215 mhd_assert (dtbl_edge_entry_infoc (dyn) <= entr_inf); 1216 return dtbl_get_strs_buffc (dyn) + dtbl_entr_strs_end_optm (entr_inf); 1217 } 1218 1219 1220 /** 1221 * Get const pointer to the entry's name. 1222 * This points to the first byte of the entry's name. If the entry has 1223 * zero-length name, the pointer denotes a zero-sized area. 1224 * The result is undefined if the entry is not in the table. 1225 * @param dyn the pointer to the dynamic table structure 1226 * @param entr_inf the pointer to the entry information 1227 * @return const pointer to the entry's name, 1228 * result is undefined if the entry is not in the table 1229 */ 1230 MHD_FN_PURE_ mhd_static_inline const char * 1231 dtbl_entr_strs_ptr_namec (const struct mhd_HpackDTblContext *dyn, 1232 const struct mhd_HpackDTblEntryInfo *entr_inf) 1233 { 1234 return dtbl_entr_strs_ptr_startc (dyn, 1235 entr_inf); 1236 } 1237 1238 1239 /** 1240 * Get const pointer to the entry's value. 1241 * This points to the first byte of the entry's value. If the entry has 1242 * zero-length value, the pointer denotes a zero-sized area. 1243 * The result is undefined if the entry is not in the table. 1244 * @param dyn the pointer to the dynamic table structure 1245 * @param entr_inf the pointer to the entry information 1246 * @return const pointer to the entry's value, 1247 * result is undefined if the entry is not in the table 1248 */ 1249 MHD_FN_PURE_ mhd_static_inline const char * 1250 dtbl_entr_strs_ptr_valuec (const struct mhd_HpackDTblContext *dyn, 1251 const struct mhd_HpackDTblEntryInfo *entr_inf) 1252 { 1253 return dtbl_entr_strs_ptr_startc (dyn, 1254 entr_inf) + entr_inf->name_len; 1255 } 1256 1257 1258 /* ** Information about the entry in the table based on the pointer to 1259 the entry ** */ 1260 1261 /** 1262 * Get the size of the space between entry's strings and entry information data 1263 * as if the provided entry were an edge entry. 1264 * The gap could be zero in some conditions. 1265 * The result is undefined if the entry is not in the table. 1266 * @param dyn const pointer to the dynamic table structure 1267 * @param entr_inf const pointer to the entry information 1268 * @return the size of the space between entry's strings and information, 1269 * result is undefined if the entry is not in the table 1270 */ 1271 MHD_FN_PURE_ mhd_static_inline dtbl_size_t 1272 dtbl_entr_as_edge_get_gap (const struct mhd_HpackDTblContext *dyn, 1273 const struct mhd_HpackDTblEntryInfo *entr_inf) 1274 { 1275 const char *upper_ptr = (const char *) entr_inf; 1276 const char *lower_ptr = dtbl_entr_strs_ptr_endc (dyn, entr_inf); 1277 const dtbl_size_ft gap = (dtbl_size_ft) (upper_ptr - lower_ptr); 1278 1279 mhd_assert (dtbl_zero_entry_infoc (dyn) >= entr_inf); 1280 mhd_assert (dtbl_edge_entry_infoc (dyn) <= entr_inf); 1281 mhd_assert (lower_ptr <= upper_ptr); 1282 mhd_assert (mhd_DTBL_VALUE_FITS (gap)); 1283 mhd_assert (gap < dyn->buf_alloc_size); 1284 1285 return (dtbl_size_t) gap; 1286 } 1287 1288 1289 /* ** Entries strings location information based on entry position in 1290 the table ** */ 1291 1292 /** 1293 * Get a pointer to the (inclusive) start of the entry's strings in the 1294 * strings buffer. 1295 * This points to the first char (byte) of the entry's strings. If the entry 1296 * has zero-length strings then this points to the first byte of entry slack 1297 * (if any) or the first char of the next entry's strings (if any). 1298 * The result is undefined if the location number is equal to or greater than 1299 * the number of entries in the table. 1300 * @param dyn the pointer to the dynamic table structure 1301 * @param loc_pos the number of location position 1302 * @return the pointer to the (inclusive) start of the entry's strings 1303 */ 1304 MHD_FN_PURE_ mhd_static_inline char * 1305 dtbl_pos_strs_ptr_start (struct mhd_HpackDTblContext *dyn, 1306 dtbl_idx_ft loc_pos) 1307 { 1308 return dtbl_entr_strs_ptr_start (dyn, 1309 dtbl_pos_entry_info (dyn, 1310 loc_pos)); 1311 } 1312 1313 1314 /** 1315 * Get a const pointer to the (inclusive) start of the entry's strings in the 1316 * strings buffer. 1317 * This points to the first char (byte) of the entry's strings. If the entry 1318 * has zero-length strings then this points to the first byte of entry slack 1319 * (if any) or the first char of the next entry's strings (if any). 1320 * The result is undefined if the location number is equal to or greater than 1321 * the number of entries in the table. 1322 * @param dyn const pointer to the dynamic table structure 1323 * @param loc_pos the number of location position 1324 * @return const pointer to the (inclusive) start of the entry's strings, 1325 * result is undefined if the entry is not in the table 1326 */ 1327 MHD_FN_PURE_ mhd_static_inline const char * 1328 dtbl_pos_strs_ptr_startc (const struct mhd_HpackDTblContext *dyn, 1329 dtbl_idx_ft loc_pos) 1330 { 1331 return dtbl_entr_strs_ptr_startc (dyn, 1332 dtbl_pos_entry_infoc (dyn, 1333 loc_pos)); 1334 } 1335 1336 1337 /** 1338 * Get a pointer to the (exclusive) end of the entry's strings in the 1339 * strings buffer. 1340 * This points to the next char (byte) after the strings of the entry. 1341 * The result is undefined if the location number is equal or greater than the 1342 * number of entries in the table. 1343 * @param dyn the pointer to the dynamic table structure 1344 * @param loc_pos the number of location position 1345 * @return the pointer to the (exclusive) end of the entry's strings 1346 */ 1347 MHD_FN_PURE_ mhd_static_inline char * 1348 dtbl_pos_strs_ptr_end (struct mhd_HpackDTblContext *dyn, 1349 dtbl_idx_ft loc_pos) 1350 { 1351 return dtbl_entr_strs_ptr_end (dyn, 1352 dtbl_pos_entry_info (dyn, 1353 loc_pos)); 1354 } 1355 1356 1357 /** 1358 * Get a const pointer to the (exclusive) end of the entry's strings in the 1359 * strings buffer. 1360 * This points to the next char (byte) after the strings of the entry. 1361 * The result is undefined if the location number is equal or greater than the 1362 * number of entries in the table. 1363 * @param dyn const pointer to the dynamic table structure 1364 * @param loc_pos the number of location position 1365 * @return const pointer to the (exclusive) end of the entry's strings 1366 */ 1367 MHD_FN_PURE_ mhd_static_inline const char * 1368 dtbl_pos_strs_ptr_endc (const struct mhd_HpackDTblContext *dyn, 1369 dtbl_idx_ft loc_pos) 1370 { 1371 return dtbl_entr_strs_ptr_endc (dyn, 1372 dtbl_pos_entry_infoc (dyn, 1373 loc_pos)); 1374 } 1375 1376 1377 /** 1378 * Get a const pointer to the (exclusive) end of the entry's standard slack 1379 * after the entry's strings in the strings buffer. 1380 * This points to the preferred location of the next entry's strings. 1381 * The result is undefined if the location number is equal or greater than the 1382 * number of entries in the table. 1383 * @param dyn const pointer to the dynamic table structure 1384 * @param loc_pos the number of location position 1385 * @return const pointer to the (exclusive) end of the entry's standard slack 1386 */ 1387 MHD_FN_PURE_ mhd_static_inline const char * 1388 dtbl_pos_strs_ptr_end_slackc (const struct mhd_HpackDTblContext *dyn, 1389 dtbl_idx_ft loc_pos) 1390 { 1391 return dtbl_entr_strs_ptr_end_slackc (dyn, 1392 dtbl_pos_entry_infoc (dyn, 1393 loc_pos)); 1394 } 1395 1396 1397 /* ** Information about the entry in the table based on entry position in 1398 the table ** */ 1399 1400 /** 1401 * Get the size of the space between entry's strings and entry information data 1402 * as if the provided entry were an edge entry. 1403 * The gap could be zero in some conditions. 1404 * The result is undefined if the location number is equal or greater than the 1405 * number of entries in the table. 1406 * @param dyn const pointer to the dynamic table structure 1407 * @param loc_pos the number of location position 1408 * @return the size of the space between entry's strings and information 1409 */ 1410 MHD_FN_PURE_ mhd_static_inline dtbl_size_t 1411 dtbl_pos_as_edge_get_gap (const struct mhd_HpackDTblContext *dyn, 1412 dtbl_idx_ft loc_pos) 1413 { 1414 return dtbl_entr_as_edge_get_gap (dyn, 1415 dtbl_pos_entry_infoc (dyn, 1416 loc_pos)); 1417 } 1418 1419 1420 /* ** Additional means of access to the entries information ** */ 1421 1422 /** 1423 * Get table's entries information as a pointer to an array. 1424 * 1425 * The returned array has #dtbl_get_num_entries() elements. 1426 * The returned pointer becomes invalid if any entry is added or evicted 1427 * from the table. 1428 * 1429 * Behaviour is undefined if table is empty. 1430 * @param dyn the pointer to the dynamic table structure 1431 * @return table's entries information as a pointer to an array 1432 */ 1433 MHD_FN_PURE_ mhd_static_inline struct mhd_HpackDTblEntryInfo * 1434 dtbl_get_infos_as_array (struct mhd_HpackDTblContext *dyn) 1435 { 1436 return dtbl_edge_entry_info (dyn); 1437 } 1438 1439 1440 /** 1441 * Get table's entries information as a pointer to a const array. 1442 * 1443 * The returned array has #dtbl_get_num_entries() elements. 1444 * 1445 * The first (zero index) item in the array is the edge entry, the last item 1446 * in the array is zero position entry. 1447 * 1448 * The returned pointer becomes invalid if any entry is added or evicted 1449 * from the table. 1450 * 1451 * Behaviour is undefined if table is empty. 1452 * @param dyn the pointer to the dynamic table structure 1453 * @return table's entries information as a pointer to a const array 1454 */ 1455 MHD_FN_PURE_ mhd_static_inline const struct mhd_HpackDTblEntryInfo * 1456 dtbl_get_infos_as_arrayc (const struct mhd_HpackDTblContext *dyn) 1457 { 1458 return dtbl_edge_entry_infoc (dyn); 1459 } 1460 1461 1462 /* ** Additional information about the table ** */ 1463 1464 /** 1465 * Get the size of the free space available for new entries (including 1466 * entry's strings, entry info data, and per-entry slack) between the 1467 * string region and the entry-info region in the shared buffer. 1468 * 1469 * The gap could be zero in some conditions. 1470 1471 * Unlike #dtbl_bottom_gap(), this space is used for both strings data and 1472 * entries info data when adding new entries. 1473 * 1474 * This is not the formal HPACK free size. 1475 * @param dyn const pointer to the dynamic table structure 1476 * @return the size of the space available at the edge of the table 1477 */ 1478 MHD_FN_PURE_ mhd_static_inline dtbl_size_t 1479 dtbl_edge_gap (const struct mhd_HpackDTblContext *dyn) 1480 { 1481 if (dtbl_is_empty (dyn)) 1482 return dyn->buf_alloc_size; 1483 1484 return dtbl_entr_as_edge_get_gap (dyn, 1485 dtbl_edge_entry_infoc (dyn)); 1486 } 1487 1488 1489 /** 1490 * Get the size of the free space available for strings at the bottom of 1491 * the shared buffer. 1492 * 1493 * Unlike #dtbl_edge_gap(), if table is not empty, this space can be used only 1494 * for the strings data for an entry added at zero position. 1495 * 1496 * @param dyn const pointer to the dynamic table structure 1497 * @return the size of the space available at the bottom of the table 1498 */ 1499 MHD_FN_PURE_ mhd_static_inline dtbl_size_t 1500 dtbl_bottom_gap (const struct mhd_HpackDTblContext *dyn) 1501 { 1502 if (dtbl_is_empty (dyn)) 1503 return dyn->buf_alloc_size; 1504 1505 return dtbl_pos_strs_start (dyn, 0u); 1506 } 1507 1508 1509 /* ** Manipulating strings in the dynamic table ** */ 1510 1511 /** 1512 * Choose the offset of the strings in the strings buffer for a new entry 1513 * following another entry (non-zero position). 1514 * 1515 * If enough space is available, up to the standard slack bytes are left 1516 * between entries' strings. 1517 * 1518 * Result is undefined if @a size_of_space is less than @a entry_strs_size. 1519 * @param space_start the offset of the start (inclusive) of free space in 1520 * the buffer 1521 * @param size_of_space the amount of free space at the @a space_start offset 1522 * @param entry_strs_size the size of new entries strings 1523 * @return the offset to put entries strings in the buffer 1524 */ 1525 MHD_FN_CONST_ mhd_static_inline dtbl_size_t 1526 dtbl_choose_strs_offset_for_size (dtbl_size_ft space_start, 1527 dtbl_size_ft size_of_space, 1528 dtbl_size_ft entry_strs_size) 1529 { 1530 const dtbl_size_ft extra_space = size_of_space - entry_strs_size; 1531 1532 mhd_assert (size_of_space >= entry_strs_size); 1533 mhd_assert (mhd_DTBL_VALUE_FITS (space_start)); 1534 mhd_assert (mhd_DTBL_VALUE_FITS (size_of_space)); 1535 mhd_assert (mhd_DTBL_VALUE_FITS (entry_strs_size)); 1536 1537 if (mhd_dtbl_entry_slack <= extra_space) 1538 return (dtbl_size_t) (space_start + mhd_dtbl_entry_slack); 1539 1540 return (dtbl_size_t) (space_start + extra_space); 1541 } 1542 1543 1544 /** 1545 * Completely reset dynamic table data. 1546 * This fully removes all entries from the table, leaving the size of the table 1547 * and the table allocation the same. 1548 * @param dyn the pointer to the dynamic table structure 1549 */ 1550 mhd_static_inline void 1551 dtbl_reset (struct mhd_HpackDTblContext *dyn) 1552 { 1553 dyn->num_entries = 0u; 1554 dyn->newest_pos = 0u; 1555 dyn->cur_size = 0u; 1556 } 1557 1558 1559 /** 1560 * Move selected entries' strings in the strings buffer down (to the start of 1561 * the buffer). 1562 * The strings are moved for all entries from @a from_pos up to the 1563 * edge (highest number) entry. 1564 * @param dyn the pointer to the dynamic table structure 1565 * @param from_pos the first entry position to move strings 1566 * @param shift_down_size the amount of bytes to shift 1567 */ 1568 static void 1569 dtbl_move_strs_down (struct mhd_HpackDTblContext *dyn, 1570 dtbl_idx_ft from_pos, 1571 dtbl_size_ft shift_down_size) 1572 { 1573 char *move_area_src = dtbl_pos_strs_ptr_start (dyn, 1574 from_pos); 1575 size_t move_area_size = 1576 (size_t) 1577 (dtbl_pos_strs_ptr_endc (dyn, 1578 dtbl_get_pos_edge (dyn)) - move_area_src); 1579 dtbl_idx_ft i; 1580 1581 mhd_assert (mhd_DTBL_VALUE_FITS (from_pos)); 1582 mhd_assert (mhd_DTBL_VALUE_FITS (shift_down_size)); 1583 mhd_assert (0u != shift_down_size); 1584 mhd_assert (dtbl_get_pos_edge (dyn) >= from_pos); 1585 mhd_assert (shift_down_size <= dtbl_pos_strs_start (dyn, from_pos)); 1586 mhd_assert ((0u == from_pos) || \ 1587 (dtbl_pos_strs_end_min (dyn, from_pos - 1u) <= \ 1588 dtbl_pos_strs_start (dyn, from_pos) - shift_down_size)); 1589 mhd_assert ((0u != from_pos) || \ 1590 (dtbl_bottom_gap (dyn) >= shift_down_size)); 1591 mhd_assert (dtbl_edge_gap (dyn) < dyn->buf_alloc_size); 1592 mhd_assert (dyn->buf_alloc_size > move_area_size); 1593 1594 /* Optimisation ideas: instead of shifting all entries uniformly, they 1595 * can be "compressed" by eliminating the slack between some of the top 1596 * entries. This will require more processing, more movements on the next 1597 * rounds, but saves a lot if the dynamic table is large. */ 1598 1599 /* Move all strings in the buffer for selected entries */ 1600 memmove (move_area_src - shift_down_size, 1601 move_area_src, 1602 move_area_size); 1603 1604 #ifndef NDEBUG 1605 /* Zero-out standard string slack of the last entry strings */ 1606 if (mhd_dtbl_entry_slack <= shift_down_size) 1607 memset (move_area_src - shift_down_size + move_area_size, 1608 0, 1609 mhd_dtbl_entry_slack); 1610 else 1611 memset (move_area_src - shift_down_size + move_area_size, 1612 0, 1613 shift_down_size); 1614 #endif /* ! NDEBUG */ 1615 1616 for (i = from_pos; dtbl_get_pos_edge (dyn) >= i; ++i) 1617 dtbl_pos_entry_info (dyn, 1618 i)->offset -= (dtbl_size_t) shift_down_size; 1619 } 1620 1621 1622 /** 1623 * Move selected entries' strings in the strings buffer up (to the entries 1624 * information data). 1625 * The strings are moved for all entries from @a from_entry up to the 1626 * edge (highest number) entry. 1627 * @param dyn the pointer to the dynamic table structure 1628 * @param from_pos the first entry position to move strings 1629 * @param shift_up_size the amount of bytes to shift 1630 */ 1631 static void 1632 dtbl_move_strs_up (struct mhd_HpackDTblContext *dyn, 1633 dtbl_idx_ft from_pos, 1634 dtbl_size_ft shift_up_size) 1635 { 1636 char *move_area_src = dtbl_pos_strs_ptr_start (dyn, 1637 from_pos); 1638 size_t move_area_size = 1639 (size_t) 1640 (dtbl_pos_strs_ptr_endc (dyn, 1641 dtbl_get_pos_edge (dyn)) - move_area_src); 1642 dtbl_idx_ft i; 1643 1644 mhd_assert (mhd_DTBL_VALUE_FITS (shift_up_size)); 1645 mhd_assert (0u != shift_up_size); 1646 mhd_assert (dtbl_get_pos_edge (dyn) >= from_pos); 1647 mhd_assert (shift_up_size < (dyn->buf_alloc_size)); 1648 mhd_assert (dtbl_edge_gap (dyn) >= shift_up_size); 1649 mhd_assert (dyn->buf_alloc_size > move_area_size); 1650 1651 /* Optimisation ideas: instead of shifting all entries uniformly, they 1652 * can be "compacted" by eliminating the slack between some of the bottom 1653 * entries. This will require more processing and probably more movements on 1654 * the next rounds, but saves a lot if the dynamic table is large. */ 1655 1656 #ifndef NDEBUG 1657 /* Zero-out standard string slack of the last entry strings AFTER the moved 1658 data if space is available */ 1659 if (1) 1660 { 1661 const dtbl_size_ft top_gap_final = dtbl_edge_gap (dyn) - shift_up_size; 1662 1663 if (mhd_dtbl_entry_slack <= top_gap_final) 1664 memset (move_area_src + shift_up_size + move_area_size, 1665 0, 1666 mhd_dtbl_entry_slack); 1667 else if (0u != top_gap_final) 1668 memset (move_area_src + shift_up_size + move_area_size, 1669 0, 1670 top_gap_final); 1671 } 1672 #endif /* ! NDEBUG */ 1673 1674 /* Move all strings in the buffer for selected entries */ 1675 memmove (move_area_src + shift_up_size, 1676 move_area_src, 1677 move_area_size); 1678 1679 for (i = from_pos; dtbl_get_pos_edge (dyn) >= i; ++i) 1680 dtbl_pos_entry_info (dyn, 1681 i)->offset += (dtbl_size_t) shift_up_size; 1682 } 1683 1684 1685 /** 1686 * Compact strings in the shared buffer so that all currently unused space 1687 * is located at the edge (between the strings region and entry information 1688 * data region). 1689 * 1690 * If the newest entry is not the edge entry, the function removes any extra 1691 * gap between the newest and the oldest entries, keeping only the standard 1692 * slack. Otherwise, the extra gap at the bottom of the buffer is eliminated. 1693 * 1694 * The function does not change the number of entries or their formal sizes. 1695 * Behaviour is undefined if table's internal data is not consistent. 1696 * @param dyn the pointer to the dynamic table structure 1697 */ 1698 static void 1699 dtbl_compact_strs (struct mhd_HpackDTblContext *dyn) 1700 { 1701 if (dtbl_get_pos_edge (dyn) != dtbl_get_pos_newest (dyn)) 1702 { 1703 /* Remove extra space between the newest and the oldest, 1704 leave the standard slack only. */ 1705 const dtbl_size_t strs_start_optimal = 1706 dtbl_pos_strs_end_optm (dyn, 1707 dtbl_get_pos_newest (dyn)); 1708 const dtbl_size_t strs_start_current = 1709 dtbl_pos_strs_start (dyn, 1710 dtbl_get_pos_oldest (dyn)); 1711 if (strs_start_current > strs_start_optimal) 1712 { 1713 /* There is an extra slack */ 1714 const dtbl_size_t shift_size = strs_start_current - strs_start_optimal; 1715 dtbl_move_strs_down (dyn, 1716 dtbl_get_pos_oldest (dyn), 1717 shift_size); 1718 } 1719 } 1720 else 1721 { 1722 /* Remove extra space at the bottom of the strings */ 1723 const dtbl_size_t shift_size = dtbl_pos_strs_start (dyn, 1724 0u); 1725 1726 /* If there is an extra space - remove it */ 1727 if (0u != shift_size) 1728 dtbl_move_strs_down (dyn, 1729 0u, 1730 shift_size); 1731 } 1732 /* All the free space must be at the edge of the buffer. 1733 The buffer allocation is larger than the formal table size. */ 1734 mhd_assert (dtbl_edge_gap (dyn) > dtbl_get_free_formal (dyn)); 1735 } 1736 1737 1738 /** 1739 * Choose the offset of the strings in the strings buffer for a new entry 1740 * following another entry (non-zero position). 1741 * 1742 * If enough space is available, leave up to the standard slack between 1743 * entries' strings. 1744 * 1745 * Result is undefined if @a space_end is less than @a space_start. 1746 * Result is undefined if not enough space for @a entry_strs_size is in 1747 * between @a space_start and @a space_end. 1748 * @param space_start the offset of the start (inclusive) of free space in 1749 * the buffer 1750 * @param space_end the offset of the end (exclusive) of free space in 1751 * the buffer 1752 * @param entry_strs_size the size of new entries strings 1753 * @return the offset to put entries strings in the buffer 1754 */ 1755 MHD_FN_CONST_ mhd_static_inline dtbl_size_t 1756 dtbl_choose_strs_offset (dtbl_size_ft space_start, 1757 dtbl_size_ft space_end, 1758 dtbl_size_ft entry_strs_size) 1759 { 1760 const dtbl_size_ft space_size = space_end - space_start; 1761 1762 mhd_assert (space_start <= space_end); 1763 mhd_assert (mhd_DTBL_VALUE_FITS (space_start)); 1764 mhd_assert (mhd_DTBL_VALUE_FITS (space_end)); 1765 mhd_assert (mhd_DTBL_VALUE_FITS (space_size)); 1766 mhd_assert (space_end >= space_size); 1767 1768 return (dtbl_size_t) dtbl_choose_strs_offset_for_size (space_start, 1769 space_size, 1770 entry_strs_size); 1771 } 1772 1773 1774 #ifndef NDEBUG 1775 1776 /** 1777 * Zero-out end up to mhd_dtbl_entry_slack at the end of the strings of some 1778 * entry. 1779 * The input data is a pointer to the end of strings and available space. 1780 * @param entr_strs_end_ptr the pointer to the end of the strings 1781 * @param space_available amount of space before next used memory area 1782 */ 1783 mhd_static_inline void 1784 dtbl_zeroout_strs_slack_ptr_space (char *entr_strs_end_ptr, 1785 dtbl_size_ft space_available) 1786 { 1787 const dtbl_size_ft zero_out_size = 1788 (mhd_dtbl_entry_slack <= space_available) ? 1789 mhd_dtbl_entry_slack : space_available; 1790 mhd_assert (mhd_DTBL_VALUE_FITS (space_available)); 1791 1792 if (0u != space_available) 1793 memset (entr_strs_end_ptr, 1794 0, 1795 zero_out_size); 1796 } 1797 1798 1799 /** 1800 * Zero-out end up to mhd_dtbl_entry_slack at the end of the strings of some 1801 * entry. 1802 * The input data is an offset of the end of strings and available space. 1803 * @param dyn pointer to the dynamic table structure 1804 * @param entr_strs_end_offset the offset of the end of the strings 1805 * @param space_available amount of space before next used memory area 1806 */ 1807 mhd_static_inline void 1808 dtbl_zeroout_strs_slack_offset_space (struct mhd_HpackDTblContext *dyn, 1809 dtbl_size_ft entr_strs_end_offset, 1810 dtbl_size_ft space_available) 1811 { 1812 mhd_assert (dyn->buf_alloc_size >= entr_strs_end_offset); 1813 mhd_assert (dyn->buf_alloc_size >= space_available); 1814 mhd_assert (dyn->buf_alloc_size >= (entr_strs_end_offset + space_available)); 1815 dtbl_zeroout_strs_slack_ptr_space (dtbl_get_strs_buff (dyn) 1816 + entr_strs_end_offset, 1817 space_available); 1818 } 1819 1820 1821 /** 1822 * Zero-out end up to mhd_dtbl_entry_slack at the end of the strings of some 1823 * entry. 1824 * The input data is dynamic table struct, an offset of the end of strings and 1825 * offset of the next data in the buffer. 1826 * @param dyn pointer to the dynamic table structure 1827 * @param entr_strs_end_offset the offset of the end of the strings 1828 * @param next_data_offset the offset of the next used memory area in the 1829 * buffer 1830 */ 1831 mhd_static_inline void 1832 dtbl_zeroout_strs_slack_offset_next (struct mhd_HpackDTblContext *dyn, 1833 dtbl_size_ft entr_strs_end_offset, 1834 dtbl_size_ft next_data_offset) 1835 { 1836 mhd_assert (dyn->buf_alloc_size >= entr_strs_end_offset); 1837 mhd_assert (dyn->buf_alloc_size >= next_data_offset); 1838 mhd_assert (next_data_offset >= entr_strs_end_offset); 1839 dtbl_zeroout_strs_slack_offset_space (dyn, 1840 entr_strs_end_offset, 1841 next_data_offset 1842 - entr_strs_end_offset); 1843 } 1844 1845 1846 /** 1847 * Zero-out end up to mhd_dtbl_entry_slack at the end of the strings of some 1848 * entry. 1849 * @param dyn pointer to the dynamic table structure 1850 * @param entry the pointer to the entry information data 1851 * @param space_available amount of space before next used memory area 1852 */ 1853 mhd_static_inline void 1854 dtbl_zeroout_strs_slack_entry_space (struct mhd_HpackDTblContext *dyn, 1855 const struct mhd_HpackDTblEntryInfo *entry, 1856 dtbl_size_ft space_available) 1857 { 1858 mhd_assert (dyn->buf_alloc_size >= space_available); 1859 dtbl_zeroout_strs_slack_ptr_space (dtbl_entr_strs_ptr_end (dyn, entry), 1860 space_available); 1861 } 1862 1863 1864 /** 1865 * Zero-out end up to mhd_dtbl_entry_slack at the end of the strings of some 1866 * entry. 1867 * @param dyn pointer to the dynamic table structure 1868 * @param entry the pointer to the entry information data 1869 * @param next_data_offset the offset of the next used memory area in the 1870 * buffer 1871 */ 1872 mhd_static_inline void 1873 dtbl_zeroout_strs_slack_entry_next (struct mhd_HpackDTblContext *dyn, 1874 const struct mhd_HpackDTblEntryInfo *entry, 1875 dtbl_size_ft next_data_offset) 1876 { 1877 mhd_assert (dyn->buf_alloc_size >= next_data_offset); 1878 dtbl_zeroout_strs_slack_offset_next (dyn, 1879 dtbl_entr_strs_end_min (entry), 1880 next_data_offset); 1881 } 1882 1883 1884 /** 1885 * Zero-out end up to mhd_dtbl_entry_slack at the end of the strings of some 1886 * entry. 1887 * @param dyn pointer to the dynamic table structure 1888 * @param loc_pos the number of location position 1889 */ 1890 mhd_static_inline void 1891 dtbl_zeroout_strs_slack_pos (struct mhd_HpackDTblContext *dyn, 1892 dtbl_idx_ft loc_pos) 1893 { 1894 if (dtbl_get_pos_edge (dyn) == loc_pos) 1895 dtbl_zeroout_strs_slack_entry_space (dyn, 1896 dtbl_pos_entry_infoc (dyn, 1897 loc_pos), 1898 dtbl_edge_gap (dyn)); 1899 else 1900 dtbl_zeroout_strs_slack_offset_next (dyn, 1901 dtbl_pos_strs_end_min (dyn, 1902 loc_pos), 1903 dtbl_pos_strs_start (dyn, 1904 loc_pos + 1u)); 1905 } 1906 1907 1908 #else /* NDEBUG */ 1909 1910 /** 1911 * No-op macro in non-debug builds. 1912 */ 1913 #define dtbl_zeroout_strs_slack_ptr_space(ptr,space) ((void) 0) 1914 1915 /** 1916 * No-op macro in non-debug builds. 1917 */ 1918 #define dtbl_zeroout_strs_slack_offset_space(dyn,offset,space) ((void) 0) 1919 1920 /** 1921 * No-op macro in non-debug builds. 1922 */ 1923 #define dtbl_zeroout_strs_slack_offset_next(dyn,offset,next_offset) ((void) 0) 1924 1925 /** 1926 * No-op macro in non-debug builds. 1927 */ 1928 #define dtbl_zeroout_strs_slack_entry_space(dyn,entry,space) ((void) 0) 1929 1930 /** 1931 * No-op macro in non-debug builds. 1932 */ 1933 #define dtbl_zeroout_strs_slack_entry_next(dyn,entry,next_offset) ((void) 0) 1934 1935 /** 1936 * No-op macro in non-debug builds. 1937 */ 1938 #define dtbl_zeroout_strs_slack_pos(dyn,loc_pos) ((void) 0) 1939 1940 #endif /* NDEBUG */ 1941 1942 /** 1943 * Copy strings to the strings buffer for a potential new entry. 1944 * 1945 * This function ONLY copies strings to the strings buffer. 1946 * It does not create a new entry, nor update any numbers or limits. 1947 * 1948 * The caller may create a new entry pointing to copied strings and update 1949 * related data in the dynamic table structure following the call of this 1950 * function. 1951 * 1952 * The table data must be in consistent and valid state. 1953 * 1954 * In debug builds the function checks whether the copied data does not 1955 * overwrite any other used data in the buffer. 1956 * 1957 * @param dyn pointer to the dynamic table structure 1958 * @param name the name of the header, does NOT need to be zero-terminated 1959 * @param val the value of the header, does NOT need to be zero terminated 1960 * @param new_entry the pointer to the newly created entry; this entry must not 1961 * be in the table; must contain the lengths of the name 1962 * and the value corresponding to the strings pointed to by 1963 * @a name and @a val respectively. 1964 */ 1965 static void 1966 dtbl_new_entry_copy_entr_strs ( 1967 struct mhd_HpackDTblContext *restrict dyn, 1968 const char *restrict name, 1969 const char *restrict val, 1970 const struct mhd_HpackDTblEntryInfo *restrict new_entry) 1971 { 1972 char *const strs_buff = dtbl_get_strs_buff (dyn); 1973 1974 #ifndef __SANITIZE_ADDRESS__ 1975 # ifdef HAVE_UINTPTR_T 1976 /* The new entry must not be in the table */ 1977 mhd_assert (dtbl_is_empty (dyn) || 1978 (((uintptr_t) (const void*) dtbl_zero_entry_infoc (dyn)) < \ 1979 (uintptr_t) (const void*) new_entry) || \ 1980 (((uintptr_t) (const void*) dtbl_zero_entry_infoc (dyn)) > \ 1981 (uintptr_t) (const void*) new_entry)); 1982 # endif /* HAVE_UINTPTR_T */ 1983 #endif /* ! __SANITIZE_ADDRESS__*/ 1984 1985 #ifndef NDEBUG 1986 if (1) 1987 { 1988 /* Find position of the entry which string is located after the new copied 1989 strings. */ 1990 dtbl_idx_ft i; 1991 dtbl_size_ft next_data_offset = 0u; 1992 for (i = 0u; dyn->num_entries > i; ++i) 1993 { 1994 /* Check whether the buffer area referenced in the new entry is not used 1995 by other entries */ 1996 mhd_assert ((0u == dtbl_pos_strs_size_min (dyn, i)) || \ 1997 (dtbl_pos_strs_end_min (dyn, i) <= \ 1998 dtbl_entr_strs_start (new_entry)) || \ 1999 (dtbl_entr_strs_end_min (new_entry) <= \ 2000 dtbl_pos_strs_start (dyn, i))); 2001 2002 if (dtbl_entr_strs_end_min (new_entry) <= \ 2003 dtbl_pos_strs_start (dyn, i)) 2004 { 2005 next_data_offset = dtbl_pos_strs_start (dyn, i); 2006 break; 2007 } 2008 } 2009 if (dyn->num_entries == i) 2010 { 2011 /* Adding strings are at the edge of the strings buffer */ 2012 mhd_assert (0u == next_data_offset); 2013 mhd_assert (dtbl_entr_strs_end_min (new_entry) <= \ 2014 dtbl_get_strs_ceiling (dyn)); 2015 next_data_offset = dtbl_get_strs_ceiling (dyn); 2016 } 2017 mhd_assert (dtbl_entr_strs_end_min (new_entry) <= next_data_offset); 2018 dtbl_zeroout_strs_slack_entry_next (dyn, 2019 new_entry, 2020 next_data_offset); 2021 } 2022 #endif 2023 2024 /* Do not use dtbl_entr_strs_ptr_start() here as it does not work with 2025 entries outside the table. */ 2026 if (0u != new_entry->name_len) 2027 memcpy (strs_buff + dtbl_entr_strs_start (new_entry), 2028 name, 2029 new_entry->name_len); 2030 if (0u != new_entry->val_len) 2031 memcpy (strs_buff + dtbl_entr_strs_start (new_entry) + new_entry->name_len, 2032 val, 2033 new_entry->val_len); 2034 } 2035 2036 2037 /** 2038 * Return a pointer to the slot for the next entry info. 2039 * The new slot is assumed to be located at the next edge location (below 2040 * the current edge entry location). 2041 * This function neither modifies the table nor reserves memory. 2042 * The returned pointer refers to writable but not yet initialised space 2043 * inside the table buffer; the caller must fill it and then increment 2044 * dyn->num_entries. 2045 * The result is undefined if there is no space in the buffer for the 2046 * additional entry info. 2047 * @param dyn pointer to the dynamic table structure 2048 * @return pointer to writable memory for the next entry info 2049 */ 2050 MHD_FN_PURE_ mhd_static_inline struct mhd_HpackDTblEntryInfo * 2051 dtbl_new_edge_peek_slot (struct mhd_HpackDTblContext *dyn) 2052 { 2053 mhd_assert (mhd_DTBL_ENTRY_INFO_SIZE <= dtbl_edge_gap (dyn)); 2054 /* Do not call dtbl_pos_entry_info() as it works only with valid position 2055 * numbers, while the new position number is not valid yet. */ 2056 return dtbl_get_infos (dyn) - dyn->num_entries; 2057 } 2058 2059 2060 /* ** Intrusive dangerous functions ** */ 2061 2062 /** 2063 * Shift entries info data toward higher location positions by one location 2064 * position, starting at the specified location position and INCLUDING the 2065 * edge entry (i.e., the block [insert_pos_loc .. edge] is moved to 2066 * [insert_pos_loc + 1 .. edge + 1]). The entry information at 2067 * @a insert_pos_loc becomes uninitialised. 2068 * 2069 * Only entries information data are moved; strings in the buffer are not 2070 * modified. 2071 * 2072 * Note: this function internally moves data downward as higher location 2073 * numbers correspond to lower entry info addresses. 2074 * 2075 * This function does not update any table's data. The caller is responsible 2076 * for setting a valid entry data at the @a insert_pos_loc position, updating 2077 * the number of entries in the table, correcting the total size of the data 2078 * in the table and probably updating the position of the newest entry. 2079 * 2080 * Behaviour is undefined if @a insert_pos_loc is not a valid position in the 2081 * table or if the location of the next edge position is already used by the 2082 * strings in the buffer. 2083 * 2084 * @warning This function leaves table's data in an inconsistent state, the 2085 * caller should update the table's data properly. Until the data is fixed, 2086 * many dynamic table helper functions will work incorrectly. 2087 * 2088 * @param dyn pointer to the dynamic table structure 2089 * @param insert_pos_loc the location position of the first entry data to move 2090 */ 2091 mhd_static_inline void 2092 dtbl_move_infos_up (struct mhd_HpackDTblContext *dyn, 2093 const dtbl_idx_ft insert_pos_loc) 2094 { 2095 mhd_assert (dtbl_get_pos_edge (dyn) >= insert_pos_loc); 2096 mhd_assert (dtbl_edge_gap (dyn) >= mhd_DTBL_ENTRY_INFO_SIZE); 2097 memmove (dtbl_new_edge_peek_slot (dyn), 2098 dtbl_edge_entry_infoc (dyn), 2099 (size_t) 2100 ((dtbl_get_pos_edge (dyn) - insert_pos_loc + 1u) 2101 * mhd_DTBL_ENTRY_INFO_SIZE)); 2102 } 2103 2104 2105 /** 2106 * Shift entries info data for a contiguous range of locations toward lower 2107 * location positions to the specified location position. 2108 * The block [first .. last] is moved to [final .. final + last - first]. 2109 * Depending on direction of the move, the entry-info slots in the range 2110 * (final + last - first .. last] or in the range [first .. final) become 2111 * uninitialised. 2112 * 2113 * Only entries information data are moved; strings in the buffer are not 2114 * modified. 2115 * 2116 * This function does not update any table's data. The caller is responsible 2117 * for updating the number of entries in the table, correcting the total size 2118 * of the data in the table and probably updating the position of the newest 2119 * entry. 2120 * 2121 * Behaviour is undefined if the specified positions are not valid for the 2122 * table. 2123 * 2124 * @warning This function leaves table's data in inconsistent state, the caller 2125 * should update the table's data properly. Until the data is fixed, many 2126 * dynamic table helper functions will work incorrectly. 2127 * 2128 * @param dyn pointer to the dynamic table structure 2129 * @param range_first_loc the first inclusive (lowest-numbered) entry position 2130 * to move 2131 * @param range_last_loc the last inclusive (higher number) entry position to 2132 * move, could be equal to @a range_first_loc 2133 * @param final_first_loc the final position location number of the first entry 2134 */ 2135 mhd_static_inline void 2136 dtbl_move_infos_pos (struct mhd_HpackDTblContext *dyn, 2137 const dtbl_idx_ft range_first_loc, 2138 const dtbl_idx_ft range_last_loc, 2139 const dtbl_idx_ft final_first_loc) 2140 { 2141 /** Number of elements to move, including both the last and the first */ 2142 const dtbl_idx_ft num_elements = range_last_loc - range_first_loc + 1u; 2143 /** The final position location number of the last entry */ 2144 const dtbl_idx_ft final_last_loc = final_first_loc + num_elements - 1u; 2145 /* Do not use dtbl_pos_entry_info() here to avoid triggering asserts as 2146 the table data can be inconsistent */ 2147 struct mhd_HpackDTblEntryInfo *const zero_info_pos = dtbl_get_infos (dyn); 2148 const struct mhd_HpackDTblEntryInfo *const src = 2149 zero_info_pos - range_last_loc; 2150 struct mhd_HpackDTblEntryInfo *const dst = zero_info_pos - final_last_loc; 2151 mhd_assert ((dyn->buf_alloc_size / mhd_DTBL_ENTRY_INFO_SIZE) \ 2152 >= range_first_loc); 2153 mhd_assert ((dyn->buf_alloc_size / mhd_DTBL_ENTRY_INFO_SIZE) \ 2154 >= range_last_loc); 2155 mhd_assert ((dyn->buf_alloc_size / mhd_DTBL_ENTRY_INFO_SIZE) \ 2156 >= final_first_loc); 2157 mhd_assert ((dyn->buf_alloc_size / mhd_DTBL_ENTRY_INFO_SIZE) \ 2158 >= final_last_loc); 2159 mhd_assert (range_first_loc <= range_last_loc); 2160 2161 if (range_first_loc == final_first_loc) 2162 return; 2163 2164 memmove (dst, 2165 src, 2166 (size_t) (num_elements * mhd_DTBL_ENTRY_INFO_SIZE)); 2167 } 2168 2169 2170 /* ** Manipulating functions ** */ 2171 2172 #ifndef NDEBUG 2173 /** 2174 * Check internal consistency of the dynamic table internal data. 2175 * @param dyn the pointer to the dynamic table structure to check 2176 */ 2177 static void 2178 dtbl_check_internals (const struct mhd_HpackDTblContext *dyn) 2179 { 2180 mhd_assert (0u != dyn->buf_alloc_size); 2181 mhd_assert (dyn->buf_alloc_size > dyn->size_limit); 2182 mhd_assert (dyn->cur_size <= dyn->size_limit); 2183 mhd_assert (dyn->buf_alloc_size >= \ 2184 (dyn->num_entries * mhd_DTBL_ENTRY_INFO_SIZE)); 2185 mhd_assert (dyn->newest_pos <= dyn->num_entries); 2186 if (dtbl_is_empty (dyn)) 2187 { 2188 mhd_assert (0u == dyn->cur_size); 2189 mhd_assert (0u == dyn->newest_pos); 2190 } 2191 else 2192 { 2193 const struct mhd_HpackDTblEntryInfo *const zero_entry = 2194 dtbl_zero_entry_infoc (dyn); 2195 dtbl_size_ft counted_size = 0u; 2196 dtbl_idx_ft i; 2197 2198 mhd_assert (dyn->newest_pos < dyn->num_entries); 2199 mhd_assert ((0u != dyn->cur_size) && \ 2200 "Each entry has minimal size, even with zero-length strings"); 2201 mhd_assert (dyn->cur_size >= \ 2202 (dyn->num_entries * mhd_dtbl_entry_overhead)); 2203 mhd_assert (dtbl_edge_gap (dyn) <= dyn->buf_alloc_size); 2204 2205 /* Check zero entry individually */ 2206 /* If the newest entry is the edge entry, zero entry may have gap 2207 at the start of the buffer. */ 2208 if (0u != dtbl_get_pos_oldest (dyn)) 2209 { 2210 mhd_assert ((0u == zero_entry->offset) && \ 2211 "The extra gap between entries' strings is allowed only " \ 2212 "between the newest and the oldest entries"); 2213 } 2214 mhd_assert (zero_entry->offset < dyn->buf_alloc_size); 2215 mhd_assert (zero_entry->name_len < dyn->buf_alloc_size); 2216 mhd_assert (zero_entry->val_len < dyn->buf_alloc_size); 2217 mhd_assert (dtbl_entr_strs_end_min (zero_entry) < dyn->buf_alloc_size); 2218 mhd_assert (dtbl_entr_strs_ptr_endc (dyn, zero_entry) <= \ 2219 (const char*) dtbl_edge_entry_infoc (dyn)); 2220 counted_size += dtbl_entr_size_formal (zero_entry); 2221 mhd_assert (counted_size <= dyn->cur_size); 2222 2223 for (i = 1u; i <= dtbl_get_pos_edge (dyn); ++i) 2224 { 2225 const struct mhd_HpackDTblEntryInfo *const check_entry = 2226 dtbl_pos_entry_infoc (dyn, 2227 i); 2228 2229 mhd_assert ((dtbl_pos_strs_end_min (dyn, i - 1u) <= \ 2230 dtbl_pos_strs_start (dyn, i)) && \ 2231 "Strings data cannot overlap between entries"); 2232 2233 if (dtbl_get_pos_oldest (dyn) != i) 2234 mhd_assert ((dtbl_pos_strs_end_optm (dyn, i - 1u) >= \ 2235 dtbl_pos_strs_start (dyn, i)) && \ 2236 "The extra gap between entries' strings is allowed only " \ 2237 "between the newest and the oldest entries"); 2238 2239 mhd_assert (dtbl_pos_strs_start (dyn, i) < dyn->buf_alloc_size); 2240 mhd_assert (check_entry->name_len < dyn->buf_alloc_size); 2241 mhd_assert (check_entry->val_len < dyn->buf_alloc_size); 2242 mhd_assert (dtbl_entr_strs_end_min (check_entry) < dyn->buf_alloc_size); 2243 mhd_assert (dtbl_entr_strs_ptr_endc (dyn, check_entry) <= \ 2244 (const char*) dtbl_edge_entry_infoc (dyn)); 2245 if (dtbl_get_pos_edge (dyn) != i) 2246 mhd_assert (0u != dtbl_pos_as_edge_get_gap (dyn, i)); 2247 2248 counted_size += dtbl_entr_size_formal (check_entry); 2249 mhd_assert (counted_size <= dyn->cur_size); 2250 } 2251 2252 mhd_assert (dyn->cur_size == counted_size); 2253 } 2254 } 2255 2256 2257 #else /* NDEBUG */ 2258 /* No-op in non-debug builds */ 2259 #define dtbl_check_internals(dyn) ((void) 0) 2260 #endif /* NDEBUG */ 2261 2262 /** 2263 * Add the first entry to the table 2264 * 2265 * The table must be empty otherwise the behaviour is undefined. 2266 * The table must have enough space for the new entry. 2267 * 2268 * @param dyn the pointer to the dynamic table structure 2269 * @param name_len the length of the @a name 2270 * @param name the name of the header, does NOT need to be zero-terminated 2271 * @param val_len the length of the @a val 2272 * @param val the value of the header, does NOT need to be zero terminated 2273 */ 2274 static MHD_FN_PAR_IN_SIZE_ (3,2) MHD_FN_PAR_IN_SIZE_ (5,4) void 2275 dtbl_add_first_entry (struct mhd_HpackDTblContext *restrict dyn, 2276 const dtbl_size_ft name_len, 2277 const char *restrict name, 2278 const dtbl_size_ft val_len, 2279 const char *restrict val) 2280 { 2281 const dtbl_size_ft entry_strs_size = name_len + val_len; 2282 struct mhd_HpackDTblEntryInfo new_entry; 2283 2284 /* Check parameters */ 2285 mhd_assert (mhd_DTBL_VALUE_FITS (name_len)); 2286 mhd_assert (mhd_DTBL_VALUE_FITS (val_len)); 2287 mhd_assert (mhd_DTBL_VALUE_FITS (entry_strs_size)); 2288 mhd_assert (entry_strs_size >= name_len); 2289 mhd_assert (entry_strs_size >= val_len); 2290 2291 /* Check conditions */ 2292 mhd_assert (dtbl_is_empty (dyn)); 2293 2294 dtbl_check_internals (dyn); 2295 2296 new_entry.name_len = (dtbl_size_t) name_len; 2297 new_entry.val_len = (dtbl_size_t) val_len; 2298 new_entry.offset = 0u; 2299 2300 mhd_assert (dtbl_get_free_formal (dyn) >= \ 2301 dtbl_entr_size_formal (&new_entry)); 2302 mhd_assert (dtbl_edge_gap (dyn) == dtbl_get_strs_ceiling (dyn)); 2303 mhd_assert (dtbl_get_strs_ceiling (dyn) >= \ 2304 (dtbl_entr_strs_size_min (&new_entry) \ 2305 + mhd_DTBL_ENTRY_INFO_SIZE)); 2306 2307 dtbl_new_entry_copy_entr_strs (dyn, 2308 name, 2309 val, 2310 &new_entry); 2311 2312 *(dtbl_new_edge_peek_slot (dyn)) = new_entry; 2313 dyn->num_entries = 1u; 2314 dyn->cur_size = dtbl_entr_size_formal (&new_entry); 2315 mhd_assert (0u == dtbl_get_pos_newest (dyn)); 2316 } 2317 2318 2319 /** 2320 * Add new entry into the table at the new edge position 2321 * 2322 * This function adds a new entry after the existing edge-position entry, 2323 * updates all internal table data. 2324 * The function does NOT move strings in the strings buffer. The table's 2325 * buffer must have enough space for the new entry's strings and the new 2326 * entry data. 2327 * 2328 * The newest entry must be the edge entry. 2329 * The table must have enough space for the new entry. 2330 * The table must not be empty otherwise behaviour is undefined. 2331 * 2332 * @param dyn the pointer to the dynamic table structure 2333 * @param name_len the length of the @a name 2334 * @param name the name of the header, does NOT need to be zero-terminated 2335 * @param val_len the length of the @a val 2336 * @param val the value of the header, does NOT need to be zero terminated 2337 */ 2338 static MHD_FN_PAR_IN_SIZE_ (3,2) MHD_FN_PAR_IN_SIZE_ (5,4) void 2339 dtbl_add_new_entry_at_new_edge (struct mhd_HpackDTblContext *restrict dyn, 2340 const dtbl_size_ft name_len, 2341 const char *restrict name, 2342 const dtbl_size_ft val_len, 2343 const char *restrict val) 2344 { 2345 /** The total size of the strings of the new entry */ 2346 const dtbl_size_ft entry_strs_size = name_len + val_len; 2347 struct mhd_HpackDTblEntryInfo new_entry; 2348 2349 /* Check parameters */ 2350 mhd_assert (mhd_DTBL_VALUE_FITS (name_len)); 2351 mhd_assert (mhd_DTBL_VALUE_FITS (val_len)); 2352 mhd_assert (mhd_DTBL_VALUE_FITS (entry_strs_size)); 2353 mhd_assert (entry_strs_size >= name_len); 2354 mhd_assert (entry_strs_size >= val_len); 2355 mhd_assert (dtbl_get_free_formal (dyn) >= \ 2356 dtbl_new_entry_size_formal (name_len, val_len)); 2357 2358 /* Check conditions */ 2359 mhd_assert (! dtbl_is_empty (dyn)); 2360 mhd_assert (dtbl_get_pos_edge (dyn) == dtbl_get_pos_newest (dyn)); 2361 mhd_assert (dtbl_edge_gap (dyn) >= \ 2362 entry_strs_size + mhd_DTBL_ENTRY_INFO_SIZE); 2363 2364 dtbl_check_internals (dyn); 2365 2366 /* Inserting at the edge */ 2367 /* The simple case: just add new data at the edge. The previous entry 2368 * exists. */ 2369 /* Both strings and the entry info data must be stored in this memory 2370 area (edge gap). */ 2371 2372 new_entry.name_len = (dtbl_size_t) name_len; 2373 new_entry.val_len = (dtbl_size_t) val_len; 2374 new_entry.offset = 2375 dtbl_choose_strs_offset (dtbl_pos_strs_end_min (dyn, 2376 dtbl_get_pos_edge (dyn)), 2377 dtbl_get_strs_ceiling (dyn) 2378 - mhd_DTBL_ENTRY_INFO_SIZE, 2379 entry_strs_size); 2380 2381 mhd_assert (dtbl_edge_gap (dyn) >= \ 2382 dtbl_entr_strs_size_min (&new_entry) + mhd_DTBL_ENTRY_INFO_SIZE); 2383 2384 dtbl_new_entry_copy_entr_strs (dyn, 2385 name, 2386 val, 2387 &new_entry); 2388 2389 *(dtbl_new_edge_peek_slot (dyn)) = new_entry; 2390 dyn->newest_pos = dyn->num_entries; 2391 ++(dyn->num_entries); 2392 dyn->cur_size += dtbl_entr_size_formal (&new_entry); 2393 2394 mhd_assert (dyn->cur_size > dtbl_entr_size_formal (&new_entry)); 2395 mhd_assert (! dtbl_is_empty (dyn)); 2396 mhd_assert (0u != dyn->newest_pos); 2397 mhd_assert (dyn->size_limit >= dyn->cur_size); 2398 /* The next assert evaluates dtbl_edge_gap(), which also checks the 2399 strings/infos do not overlap. */ 2400 mhd_assert (dyn->buf_alloc_size > dtbl_edge_gap (dyn)); 2401 } 2402 2403 2404 /** 2405 * Insert new entry into the table after the current newest (latest added) 2406 * entry. If the latest entry is at the edge, then the new entry is inserted 2407 * at zero position. 2408 * 2409 * This function inserts a new entry, moving entries information data as 2410 * necessary, updates all internal table data. 2411 * The function does NOT move strings in the strings buffer. The strings 2412 * buffer after the latest entry must have enough space for the new entry 2413 * strings. 2414 * 2415 * This function never inserts an entry at the edge (zero position is used 2416 * instead). 2417 * The table must have enough space for the new entry. 2418 * The table must not be empty otherwise behaviour is undefined. 2419 * 2420 * @param dyn the pointer to the dynamic table structure 2421 * @param name_len the length of the @a name 2422 * @param name the name of the header, does NOT need to be zero-terminated 2423 * @param val_len the length of the @a val 2424 * @param val the value of the header, does NOT need to be zero terminated 2425 */ 2426 static void 2427 dtbl_insert_next_new_entry (struct mhd_HpackDTblContext *restrict dyn, 2428 const dtbl_size_ft name_len, 2429 const char *restrict name, 2430 const dtbl_size_ft val_len, 2431 const char *restrict val) 2432 { 2433 /** The total size of the strings of the new entry */ 2434 const dtbl_size_ft entry_strs_size = name_len + val_len; 2435 const dtbl_idx_ft loc_pos = dtbl_get_pos_oldest (dyn); 2436 const bool insert_at_zero = (0u == loc_pos); 2437 /** The pointer to the insert entry. 2438 The entry information data will be moved (together with higher numbered 2439 entries) and new entry will be inserted to this location. */ 2440 struct mhd_HpackDTblEntryInfo *const insert_entry_ptr = 2441 dtbl_oldest_entry_info (dyn); 2442 /** The offset of the start of the available space */ 2443 const dtbl_size_ft avail_space_start = 2444 insert_at_zero ? 0u : dtbl_entr_strs_end_min (dtbl_newest_entry_info (dyn)); 2445 /** The offset of the end of the available space */ 2446 const dtbl_size_ft avail_space_end = 2447 dtbl_entr_strs_start (dtbl_oldest_entry_infoc (dyn)); 2448 struct mhd_HpackDTblEntryInfo new_entry; 2449 2450 /* Check parameters */ 2451 mhd_assert (mhd_DTBL_VALUE_FITS (name_len)); 2452 mhd_assert (mhd_DTBL_VALUE_FITS (val_len)); 2453 mhd_assert (mhd_DTBL_VALUE_FITS (entry_strs_size)); 2454 mhd_assert (entry_strs_size >= name_len); 2455 mhd_assert (entry_strs_size >= val_len); 2456 mhd_assert (dtbl_get_pos_prev (dyn, loc_pos) == dtbl_get_pos_newest (dyn)); 2457 mhd_assert (dtbl_get_pos_edge (dyn) >= loc_pos); 2458 /* Insertion as zero position is possible only if the newest entry 2459 is the edge entry (and the insertion wraps to the other side of 2460 the buffer). */ 2461 mhd_assert (insert_at_zero == 2462 (dtbl_get_pos_newest (dyn) == dtbl_get_pos_edge (dyn))); 2463 2464 /* Check conditions */ 2465 mhd_assert (! dtbl_is_empty (dyn)); 2466 2467 dtbl_check_internals (dyn); 2468 2469 /* The new entry must be inserted either between two entries or at zero 2470 location position. The inserted entry is not at the edge (is followed by 2471 another entry). */ 2472 mhd_assert (avail_space_end >= avail_space_start); 2473 2474 new_entry.name_len = (dtbl_size_t) name_len; 2475 new_entry.val_len = (dtbl_size_t) val_len; 2476 new_entry.offset = 2477 insert_at_zero ? 0u : dtbl_choose_strs_offset (avail_space_start, 2478 avail_space_end, 2479 entry_strs_size); 2480 2481 mhd_assert (avail_space_start <= new_entry.offset); 2482 mhd_assert (avail_space_end >= new_entry.offset); 2483 mhd_assert (avail_space_end >= new_entry.offset + entry_strs_size); 2484 mhd_assert (avail_space_end >= dtbl_entr_strs_end_min (&new_entry)); 2485 mhd_assert (dtbl_get_free_formal (dyn) >= \ 2486 dtbl_entr_size_formal (&new_entry)); 2487 2488 dtbl_new_entry_copy_entr_strs (dyn, 2489 name, 2490 val, 2491 &new_entry); 2492 2493 /* Move entries info data as the new entry data must be inserted */ 2494 dtbl_move_infos_up (dyn, 2495 loc_pos); 2496 2497 *insert_entry_ptr = new_entry; 2498 ++(dyn->num_entries); 2499 dyn->newest_pos = (dtbl_idx_t) loc_pos; 2500 dyn->cur_size += dtbl_entr_size_formal (&new_entry); 2501 2502 mhd_assert (dyn->cur_size > dtbl_entr_size_formal (&new_entry)); 2503 mhd_assert (dtbl_get_pos_edge (dyn) > dtbl_get_pos_newest (dyn)); 2504 mhd_assert (! dtbl_is_empty (dyn)); 2505 mhd_assert (dyn->size_limit >= dyn->cur_size); 2506 /* The next assert calls dtbl_edge_gap() which force checking non-overlap 2507 of entries and strings. */ 2508 mhd_assert (dyn->buf_alloc_size > dtbl_edge_gap (dyn)); 2509 } 2510 2511 2512 /** 2513 * Extend the table by inserting a new entry without prior eviction. 2514 * 2515 * The table must have enough formal free space for the new entry. 2516 * Behaviour is undefined if table's internal data is not consistent. 2517 * @param dyn the pointer to the dynamic table structure 2518 * @param name_len the length of the @a name 2519 * @param name the name of the header, does NOT need to be zero-terminated 2520 * @param val_len the length of the @a val 2521 * @param val the value of the header, does NOT need to be zero terminated 2522 */ 2523 static void 2524 dtbl_extend_with_entry (struct mhd_HpackDTblContext *restrict dyn, 2525 const dtbl_size_ft name_len, 2526 const char *restrict name, 2527 const dtbl_size_ft val_len, 2528 const char *restrict val) 2529 { 2530 const dtbl_size_ft entry_strs_size = name_len + val_len; 2531 2532 mhd_assert (mhd_DTBL_VALUE_FITS (name_len)); 2533 mhd_assert (mhd_DTBL_VALUE_FITS (val_len)); 2534 mhd_assert (mhd_DTBL_VALUE_FITS (entry_strs_size)); 2535 mhd_assert (entry_strs_size >= name_len); 2536 mhd_assert (entry_strs_size >= val_len); 2537 mhd_assert (dtbl_get_free_formal (dyn) >= \ 2538 dtbl_new_entry_size_formal (name_len, val_len)); 2539 2540 dtbl_check_internals (dyn); 2541 2542 if (dtbl_is_empty (dyn)) 2543 { 2544 /* Empty table */ 2545 dtbl_add_first_entry (dyn, 2546 name_len, 2547 name, 2548 val_len, 2549 val); 2550 2551 return; /* Inserted at zero position */ 2552 } 2553 else if (dtbl_get_pos_newest (dyn) == dtbl_get_pos_edge (dyn)) 2554 { 2555 /* Current insert position is at the edge */ 2556 2557 /* This section selects where to add a new entry. There are two options: 2558 + insert at the edge; 2559 + insert at the bottom (position wrap). */ 2560 2561 /** The space left on the top for strings and the new entry info */ 2562 const dtbl_size_ft top_gap = dtbl_edge_gap (dyn); 2563 /** The space left on the bottom for strings */ 2564 const dtbl_size_ft bottom_gap = dtbl_bottom_gap (dyn); 2565 /* 'true' to insert at the edge, 'false' to insert at the bottom */ 2566 bool insert_at_the_edge; 2567 mhd_assert (! dtbl_is_empty (dyn)); 2568 mhd_assert (0u != dyn->cur_size); 2569 2570 if (mhd_DTBL_ENTRY_INFO_SIZE > top_gap) 2571 { 2572 /* Not enough space to add new entry info data */ 2573 mhd_assert (0u != bottom_gap); 2574 mhd_assert (top_gap + bottom_gap >= \ 2575 mhd_DTBL_ENTRY_INFO_SIZE + entry_strs_size); 2576 dtbl_move_strs_down (dyn, 2577 0u, 2578 bottom_gap); 2579 mhd_assert (0u == dtbl_bottom_gap (dyn)); 2580 insert_at_the_edge = true; 2581 } 2582 else if (entry_strs_size + mhd_dtbl_entry_slack <= bottom_gap) 2583 { 2584 /* The new strings and the standard slack fully fit the bottom space 2585 * in the buffer, the top space is enough for the new entry info. */ 2586 insert_at_the_edge = false; 2587 } 2588 else if (entry_strs_size + mhd_dtbl_entry_slack 2589 + mhd_DTBL_ENTRY_INFO_SIZE <= top_gap) 2590 { 2591 /* The new strings, the new entry info and the standard slack fully fit 2592 * the top space in the buffer. */ 2593 insert_at_the_edge = true; 2594 } 2595 else if (entry_strs_size <= bottom_gap) 2596 { 2597 /* The new strings without the standard slack fully fit the bottom space 2598 * in the buffer, the top space is enough for the new entry info. */ 2599 insert_at_the_edge = false; 2600 } 2601 else if (entry_strs_size + mhd_DTBL_ENTRY_INFO_SIZE <= top_gap) 2602 { 2603 /* The new strings without the standard slack and the new entry info 2604 * fully fit the top space in the buffer. */ 2605 insert_at_the_edge = true; 2606 } 2607 else 2608 { 2609 /* Neither top nor bottom of the buffer is enough for the new entry. 2610 * The buffer needs to be moved. */ 2611 /* Strings could be moved either down or up */ 2612 /* As the strings must be moved in any case, move strings to the bottom 2613 to insert the new entry at the edge and thus avoid moving entries 2614 info data in memory. */ 2615 mhd_assert (top_gap < entry_strs_size \ 2616 + mhd_dtbl_entry_slack + mhd_DTBL_ENTRY_INFO_SIZE); 2617 mhd_assert ((top_gap + bottom_gap >= \ 2618 mhd_dtbl_entry_slack \ 2619 + entry_strs_size \ 2620 + mhd_dtbl_entry_slack + mhd_DTBL_ENTRY_INFO_SIZE) && \ 2621 "The total allocation size of the buffer is larger than " \ 2622 "required for strict HPACK. All extra size should be now " \ 2623 "on the top and on the bottom, as all other strings " \ 2624 "should now be place optimally or denser. The total free " \ 2625 "space must be enough for the previous entry slack and " \ 2626 "for complete new entry, including slack and info data."); 2627 2628 dtbl_move_strs_down (dyn, 2629 0u, 2630 bottom_gap); 2631 2632 mhd_assert (dtbl_edge_gap (dyn) >= \ 2633 entry_strs_size + mhd_DTBL_ENTRY_INFO_SIZE); 2634 mhd_assert ((dtbl_edge_gap (dyn) >= \ 2635 mhd_dtbl_entry_slack \ 2636 + entry_strs_size \ 2637 + mhd_dtbl_entry_slack + mhd_DTBL_ENTRY_INFO_SIZE) && \ 2638 "Strings have been compacted up to optimal space or " 2639 "denser. The free space should be enough for optimal " 2640 "placement."); 2641 insert_at_the_edge = true; 2642 } 2643 2644 if (insert_at_the_edge) 2645 { 2646 dtbl_add_new_entry_at_new_edge (dyn, 2647 name_len, 2648 name, 2649 val_len, 2650 val); 2651 2652 return; /* Inserted at new edge position */ 2653 } 2654 } 2655 else 2656 { 2657 /* Current insert position is in between two entries */ 2658 2659 /** The end of the strings of the newest entry */ 2660 const dtbl_size_ft newest_entry_end = 2661 dtbl_pos_strs_end_min (dyn, 2662 dtbl_get_pos_newest (dyn)); 2663 /** The gap between the newest entry and the oldest entry */ 2664 /** The start of the strings of the newest entry */ 2665 const dtbl_size_ft oldest_entry_start = 2666 dtbl_pos_strs_start (dyn, 2667 dtbl_get_pos_oldest (dyn)); 2668 const dtbl_size_ft inbetween_gap = 2669 oldest_entry_start - newest_entry_end; 2670 /** The space left on the top for the new entry info data */ 2671 const dtbl_size_ft top_gap = dtbl_edge_gap (dyn); 2672 /** The optimal space to place a new entry. 2673 The size consist of standard slack for previous entry string, 2674 the new entry strings and the standard slack for this entry. */ 2675 const dtbl_size_ft optimal_inbetween_size = 2676 mhd_dtbl_entry_slack + entry_strs_size + mhd_dtbl_entry_slack; 2677 2678 mhd_assert (dtbl_get_pos_edge (dyn) != dtbl_get_pos_newest (dyn)); 2679 mhd_assert (dtbl_get_pos_oldest (dyn) > dtbl_get_pos_newest (dyn)); 2680 mhd_assert (oldest_entry_start >= newest_entry_end); 2681 mhd_assert (0u != dtbl_get_pos_oldest (dyn)); 2682 mhd_assert (0u != dyn->cur_size); 2683 2684 mhd_assert (top_gap + inbetween_gap >= \ 2685 entry_strs_size + mhd_DTBL_ENTRY_INFO_SIZE); 2686 mhd_assert ((top_gap + inbetween_gap >= \ 2687 optimal_inbetween_size + mhd_DTBL_ENTRY_INFO_SIZE) && \ 2688 "This is not required for the insertion of the entry " \ 2689 "but this is guaranteed by the checking the overall size " \ 2690 "of the buffer before the insertion, so this is a check " \ 2691 "for the overall handling logic."); 2692 2693 if (mhd_DTBL_ENTRY_INFO_SIZE > top_gap) 2694 { 2695 /* Not enough space to add new entry info data */ 2696 /* Shrink in-between space to the optimal entry strings size */ 2697 const dtbl_size_ft shift_size = inbetween_gap - optimal_inbetween_size; 2698 2699 mhd_assert (inbetween_gap > optimal_inbetween_size); 2700 mhd_assert (top_gap + shift_size >= mhd_DTBL_ENTRY_INFO_SIZE); 2701 2702 dtbl_move_strs_down (dyn, 2703 dtbl_get_pos_oldest (dyn), 2704 shift_size); 2705 } 2706 else if (inbetween_gap < entry_strs_size) 2707 { 2708 /* Not enough space to add new entry strings */ 2709 /* Grow in-between space to the standard step */ 2710 const dtbl_size_ft shift_size = optimal_inbetween_size - inbetween_gap; 2711 2712 mhd_assert (inbetween_gap < optimal_inbetween_size); 2713 mhd_assert (top_gap - shift_size >= mhd_DTBL_ENTRY_INFO_SIZE); 2714 2715 dtbl_move_strs_up (dyn, 2716 dtbl_get_pos_oldest (dyn), 2717 shift_size); 2718 } 2719 } 2720 2721 /* The new entry must be inserted either between two entries or at zero 2722 location position. The inserted entry is not at the edge (is followed by 2723 another entry). */ 2724 /* Insertion to the empty table and insertion at the edge are handled 2725 earlier. */ 2726 dtbl_insert_next_new_entry (dyn, 2727 name_len, 2728 name, 2729 val_len, 2730 val); 2731 } 2732 2733 2734 /** 2735 * Evict the oldest entries as needed and add a new entry. 2736 * 2737 * The formal size of the new entry must be less than or equal to the table 2738 * maximum formal size. 2739 * The table must NOT have enough free space to add a new entry without 2740 * eviction. 2741 * 2742 * Behaviour is undefined if table's internal data is not consistent. 2743 * @param dyn the pointer to the dynamic table structure 2744 * @param name_len the length of the @a name 2745 * @param name the name of the header, does NOT need to be zero-terminated 2746 * @param val_len the length of the @a val 2747 * @param val the value of the header, does NOT need to be zero terminated 2748 */ 2749 static MHD_FN_PAR_IN_SIZE_ (3,2) MHD_FN_PAR_IN_SIZE_ (5,4) void 2750 dtbl_evict_add_entry (struct mhd_HpackDTblContext *restrict dyn, 2751 const dtbl_size_ft name_len, 2752 const char *restrict name, 2753 const dtbl_size_ft val_len, 2754 const char *restrict val) 2755 { 2756 /** The total size of the strings of the new entry */ 2757 const dtbl_size_ft entry_strs_size = name_len + val_len; 2758 /** The starting eviction position */ 2759 const dtbl_idx_ft eviction_start = 2760 dtbl_get_pos_oldest (dyn); 2761 /** The final (inclusive) eviction entry */ 2762 dtbl_idx_ft eviction_end; 2763 const dtbl_size_ft needed_evict_min = 2764 dtbl_new_entry_size_formal (name_len, val_len) - dtbl_get_free_formal (dyn); 2765 dtbl_size_ft evicted_size; 2766 /** The total number of entries to evict */ 2767 dtbl_idx_ft num_to_evict; 2768 2769 mhd_assert (mhd_DTBL_VALUE_FITS (name_len)); 2770 mhd_assert (mhd_DTBL_VALUE_FITS (val_len)); 2771 mhd_assert (0u != dyn->cur_size); 2772 mhd_assert (! dtbl_is_empty (dyn)); 2773 mhd_assert (mhd_DTBL_VALUE_FITS (entry_strs_size)); 2774 mhd_assert (entry_strs_size >= name_len); 2775 mhd_assert (entry_strs_size >= val_len); 2776 mhd_assert (dtbl_get_free_formal (dyn) < \ 2777 dtbl_new_entry_size_formal (name_len, val_len)); 2778 mhd_assert (dtbl_get_size_max_formal (dyn) >= \ 2779 dtbl_new_entry_size_formal (name_len, val_len)); 2780 mhd_assert (0u != needed_evict_min); 2781 mhd_assert (needed_evict_min <= dyn->cur_size); 2782 dtbl_check_internals (dyn); 2783 2784 eviction_end = eviction_start; 2785 evicted_size = dtbl_pos_size_formal (dyn, 2786 eviction_end); 2787 2788 while (needed_evict_min > evicted_size) 2789 { 2790 eviction_end = dtbl_get_pos_next (dyn, 2791 eviction_end); 2792 2793 mhd_assert (eviction_start != eviction_end); 2794 2795 evicted_size += dtbl_pos_size_formal (dyn, 2796 eviction_end); 2797 } 2798 mhd_assert (needed_evict_min <= evicted_size); 2799 #ifdef MHD_USE_CODE_HARDENING 2800 if (eviction_start > eviction_end) 2801 num_to_evict = 2802 eviction_end + dtbl_get_num_entries (dyn) - eviction_start + 1u; 2803 else 2804 num_to_evict = eviction_end - eviction_start + 1u; 2805 #else /* ! MHD_USE_CODE_HARDENING */ 2806 num_to_evict = 2807 ((dtbl_get_num_entries (dyn) + eviction_end 2808 - eviction_start) % dtbl_get_num_entries (dyn)) + 1u; 2809 #endif /* ! MHD_USE_CODE_HARDENING */ 2810 mhd_assert (0u != num_to_evict); 2811 mhd_assert (dtbl_get_num_entries (dyn) >= num_to_evict); 2812 2813 if (mhd_COND_ALMOST_NEVER (dtbl_get_num_entries (dyn) == num_to_evict)) 2814 { 2815 /* Simplest situation: evicted all existing entries completely */ 2816 /* Processing: 2817 + reset the table, 2818 + add the new first entry */ 2819 dtbl_reset (dyn); 2820 dtbl_add_first_entry (dyn, 2821 name_len, 2822 name, 2823 val_len, 2824 val); 2825 return; 2826 } 2827 else if (dtbl_get_pos_edge (dyn) == eviction_end) 2828 { 2829 /* Eviction area ends at the edge, at least one entry is not evicted. */ 2830 /* Processing: 2831 + reduce the number of entries in the table (evicted entries become 2832 ignored), 2833 + reduce the official size of the table, 2834 + add the new entry at the edge. 2835 No need to move the data in the table's buffer. */ 2836 mhd_assert (eviction_end >= eviction_start); 2837 mhd_assert ((0u == dtbl_pos_strs_start (dyn, 0u)) && \ 2838 "An extra gap is allowed only between the newest and the " \ 2839 "oldest entries. The newest entry was not the edge entry " \ 2840 "before the eviction."); 2841 mhd_assert (dtbl_get_pos_newest (dyn) == (eviction_start - 1u)); 2842 2843 dyn->cur_size -= (dtbl_size_t) evicted_size; 2844 dyn->num_entries = (dtbl_idx_t) eviction_start; 2845 2846 dtbl_add_new_entry_at_new_edge (dyn, 2847 name_len, 2848 name, 2849 val_len, 2850 val); 2851 return; 2852 } 2853 else if ((0u != eviction_start) && 2854 (eviction_end >= eviction_start)) 2855 { 2856 /* Entries are evicted in between other entries, at least two entries 2857 are not evicted (at the start and at the edge). */ 2858 /* Processing: 2859 + set strings size of the first evicted entry to zero (will be replaced 2860 with new entry strings), 2861 + remove other evicted entries information data (if any) by moving 2862 higher numbered entries, 2863 + reduce the official size of the table, 2864 + move strings data in the buffer (if needed), 2865 + replace the first evicted entry with the new entry. */ 2866 struct mhd_HpackDTblEntryInfo *replace_entry_ptr = 2867 dtbl_pos_entry_info (dyn, 2868 eviction_start); 2869 /** The last entry to keep before the evicted entries */ 2870 dtbl_idx_ft last_entry_keep = dtbl_get_pos_prev (dyn, 2871 eviction_start); 2872 /** The first entry to keep after the evicted entries */ 2873 dtbl_idx_ft first_entry_keep = dtbl_get_pos_next (dyn, 2874 eviction_end); 2875 /** Number of entries to keep at the edge (after evicted entries) */ 2876 dtbl_idx_ft num_keep_at_edge = 2877 dtbl_get_pos_edge (dyn) - first_entry_keep + 1u; 2878 /** The position of the start of the space for the new entry strings */ 2879 const dtbl_size_ft space_start = dtbl_pos_strs_end_min (dyn, 2880 last_entry_keep); 2881 /** The position of the end of the space for the new entry strings */ 2882 dtbl_size_ft space_end = dtbl_pos_strs_start (dyn, 2883 first_entry_keep); 2884 dtbl_size_ft space_size = space_end - space_start; 2885 struct mhd_HpackDTblEntryInfo new_entry; 2886 2887 mhd_assert (first_entry_keep > last_entry_keep); 2888 mhd_assert (dtbl_get_num_entries (dyn) - num_to_evict >= 2u); 2889 mhd_assert (dtbl_get_pos_edge (dyn) >= first_entry_keep); 2890 mhd_assert (0u != num_keep_at_edge); 2891 mhd_assert (dtbl_get_num_entries (dyn) > num_keep_at_edge); 2892 mhd_assert (space_end >= space_start); 2893 mhd_assert (dyn->buf_alloc_size > space_size); 2894 2895 replace_entry_ptr->name_len = 0u; 2896 replace_entry_ptr->val_len = 0u; 2897 /* Keep the entry to be replaced and move not evicted entries at the edge */ 2898 dtbl_move_infos_pos (dyn, 2899 first_entry_keep, 2900 dtbl_get_pos_edge (dyn), 2901 eviction_start + 1u); 2902 /* Keep the standard overhead of the entry being replaced */ 2903 dyn->cur_size -= (dtbl_size_t) (evicted_size - mhd_dtbl_entry_overhead); 2904 dyn->num_entries -= (dtbl_idx_t) (num_to_evict - 1u); 2905 2906 if (space_size < entry_strs_size) 2907 { 2908 /* No space to put the new entry strings. 2909 * Need to move strings in the buffer. */ 2910 const dtbl_size_ft shift_size = 2911 mhd_dtbl_entry_slack + entry_strs_size + mhd_dtbl_entry_slack 2912 - space_size; 2913 mhd_assert (dtbl_edge_gap (dyn) > shift_size); 2914 dtbl_move_strs_up (dyn, 2915 eviction_start + 1u, 2916 shift_size); 2917 space_size = 2918 mhd_dtbl_entry_slack + entry_strs_size + mhd_dtbl_entry_slack; 2919 } 2920 2921 mhd_assert (space_size >= entry_strs_size); 2922 2923 new_entry.name_len = (dtbl_size_t) name_len; 2924 new_entry.val_len = (dtbl_size_t) val_len; 2925 new_entry.offset = dtbl_choose_strs_offset_for_size (space_start, 2926 space_size, 2927 entry_strs_size); 2928 2929 mhd_assert (dtbl_get_num_entries (dyn) > (eviction_start + 1u)); 2930 mhd_assert (dtbl_entr_strs_end_min (&new_entry) <= \ 2931 dtbl_pos_strs_start (dyn, eviction_start + 1u)); 2932 2933 dtbl_new_entry_copy_entr_strs (dyn, 2934 name, 2935 val, 2936 &new_entry); 2937 *replace_entry_ptr = new_entry; 2938 /* Keep the standard overhead of the entry being replaced */ 2939 dyn->cur_size += (dtbl_size_t) entry_strs_size; 2940 mhd_assert ((dyn->newest_pos + 1u) == eviction_start); 2941 dyn->newest_pos = (dtbl_idx_t) eviction_start; 2942 2943 return; 2944 } 2945 else 2946 { 2947 /* Eviction area includes zero position entry, at least one entry is not 2948 evicted. 2949 The most complex case: some free space is at the bottom of the 2950 buffer and some free space can be at the edge of the buffer. 2951 The code should choose where to insert a new entry: at the bottom or 2952 at the edge. */ 2953 /* Processing: 2954 + if bottom area is large enough insert at the bottom (no need to move 2955 strings (typically large), only entries info data may need to be 2956 moved (fast as it is typically smaller and is always aligned), 2957 + otherwise remove evicted info data with low numbers, move strings 2958 in the buffer (if needed) and add the new entry at the edge. */ 2959 /** The first entry to keep */ 2960 dtbl_idx_ft first_entry_keep = dtbl_get_pos_next (dyn, 2961 eviction_end); 2962 /** The last entry to keep */ 2963 dtbl_idx_ft last_entry_keep = dtbl_get_pos_prev (dyn, 2964 eviction_start); 2965 dtbl_idx_ft num_to_keep = 2966 ((dtbl_idx_ft) (last_entry_keep - first_entry_keep) + 1u); 2967 /** The available space at the bottom of the strings buffer after 2968 eviction of the entries */ 2969 dtbl_size_ft new_bottom_gap = dtbl_pos_strs_start (dyn, 2970 first_entry_keep); 2971 2972 mhd_assert (dtbl_get_pos_edge (dyn) != eviction_end); 2973 mhd_assert (last_entry_keep >= first_entry_keep); 2974 mhd_assert (0u != num_to_keep); 2975 mhd_assert (dtbl_get_num_entries (dyn) > num_to_keep); 2976 mhd_assert (num_to_keep + num_to_evict == dtbl_get_num_entries (dyn)); 2977 2978 if (new_bottom_gap >= entry_strs_size) 2979 { 2980 /* Enough space at the bottom to put the new entry strings */ 2981 /* No need to check the space for the entries information data as 2982 new entry replaces evicted zero position entry. */ 2983 struct mhd_HpackDTblEntryInfo *replace_entry_ptr = 2984 dtbl_zero_entry_info (dyn); 2985 struct mhd_HpackDTblEntryInfo new_entry; 2986 2987 /* Keep data correct and asserts quite */ 2988 replace_entry_ptr->name_len = 0u; 2989 replace_entry_ptr->val_len = 0u; 2990 /* Move entries information data if needed, 2991 the zero position entry information will be overwritten with 2992 a new data. */ 2993 dtbl_move_infos_pos (dyn, 2994 first_entry_keep, 2995 last_entry_keep, 2996 1u); 2997 /* Keep the standard overhead of the entry being replaced */ 2998 dyn->cur_size -= (dtbl_size_t) (evicted_size - mhd_dtbl_entry_overhead); 2999 dyn->num_entries = (dtbl_idx_t) num_to_keep + 1u; /* Plus replaced zero position */ 3000 3001 new_entry.name_len = (dtbl_size_t) name_len; 3002 new_entry.val_len = (dtbl_size_t) val_len; 3003 new_entry.offset = 0u; 3004 3005 mhd_assert (dtbl_entr_strs_end_min (&new_entry) <= \ 3006 dtbl_pos_strs_start (dyn, 1u)); 3007 3008 dtbl_new_entry_copy_entr_strs (dyn, 3009 name, 3010 val, 3011 &new_entry); 3012 *replace_entry_ptr = new_entry; 3013 /* Keep the standard overhead of the entry being replaced */ 3014 dyn->cur_size += (dtbl_size_t) entry_strs_size; 3015 dyn->newest_pos = 0u; 3016 3017 dtbl_zeroout_strs_slack_pos (dyn, 3018 dtbl_get_pos_newest (dyn)); 3019 3020 return; 3021 } 3022 else 3023 { 3024 /* Not enough space at zero position in the buffer */ 3025 /* The new entry will be added at the edge of the buffer after 3026 eviction */ 3027 /** The available space at the top of the strings buffer after moving 3028 entries information data */ 3029 const dtbl_size_ft new_top_gap = 3030 dtbl_pos_as_edge_get_gap (dyn, 3031 last_entry_keep) /* The gap after the last kept entry */ 3032 + (first_entry_keep * mhd_DTBL_ENTRY_INFO_SIZE); /* 'first_entry_keep' will be evicted at zero position */ 3033 3034 mhd_assert (1u <= first_entry_keep); 3035 mhd_assert (new_top_gap + new_bottom_gap >= \ 3036 entry_strs_size + mhd_DTBL_ENTRY_INFO_SIZE); 3037 mhd_assert ((new_top_gap + new_bottom_gap >= \ 3038 mhd_dtbl_entry_slack + entry_strs_size 3039 + mhd_dtbl_entry_slack + mhd_DTBL_ENTRY_INFO_SIZE) && \ 3040 "This is not required for the insertion of the entry " \ 3041 "but this is guaranteed by the checking the overall size " \ 3042 "of the buffer before the insertion, so this is a check " \ 3043 "for the overall handling logic."); 3044 3045 /* Move entries information data first to free some space */ 3046 /* No slot kept in evicted entries as the new entry will be added 3047 at the edge */ 3048 dtbl_move_infos_pos (dyn, 3049 first_entry_keep, 3050 last_entry_keep, 3051 0u); 3052 /* Keep the table internal data correct */ 3053 dyn->num_entries = (dtbl_idx_t) num_to_keep; 3054 dyn->newest_pos = (dtbl_idx_t) (num_to_keep - 1u); 3055 dyn->cur_size -= (dtbl_size_t) evicted_size; 3056 3057 mhd_assert (new_top_gap == dtbl_edge_gap (dyn)); 3058 3059 if (new_top_gap < (entry_strs_size + mhd_DTBL_ENTRY_INFO_SIZE)) 3060 { 3061 /* Not enough space on the top of the buffer (checked earlier), 3062 not enough space at the bottom of the buffer. 3063 The strings in the buffer need to be moved. 3064 Eliminate all space at the bottom. */ 3065 const dtbl_size_ft shift_size = new_bottom_gap; 3066 mhd_assert (0u != new_bottom_gap); 3067 mhd_assert (new_bottom_gap == dtbl_bottom_gap (dyn)); 3068 3069 dtbl_move_strs_down (dyn, 3070 0u, 3071 shift_size); 3072 mhd_assert (0u == dtbl_bottom_gap (dyn)); 3073 mhd_assert (new_top_gap + shift_size == dtbl_edge_gap (dyn)); 3074 mhd_assert (dtbl_edge_gap (dyn) >= \ 3075 mhd_dtbl_entry_slack \ 3076 + dtbl_new_entry_strs_size_formal (entry_strs_size) && \ 3077 "All strings have been compacted, the free space must " \ 3078 "be enough for the previous entry slack and for " \ 3079 "a complete new entry, including slack and info data."); 3080 } 3081 3082 /* The entries have been evicted. 3083 The edge of the buffer (top of the strings buffer) has enough space 3084 for the new strings and the new entry info */ 3085 dtbl_add_new_entry_at_new_edge (dyn, 3086 name_len, 3087 name, 3088 val_len, 3089 val); 3090 3091 return; 3092 } 3093 } 3094 } 3095 3096 3097 /** 3098 * Evict entries to reach the specified final formal table size. 3099 * 3100 * The function evicts the oldest entries until the formal used size is less 3101 * than or equal to @a final_formal_size. 3102 * 3103 * The table must not be empty. 3104 * Behaviour is undefined if @a final_formal_size is not less than the current 3105 * formal used size. 3106 * @param dyn the pointer to the dynamic table structure 3107 * @param max_used_final the target formal size of data in the table 3108 */ 3109 static void 3110 dtbl_evict_to_size (struct mhd_HpackDTblContext *restrict dyn, 3111 dtbl_size_ft max_used_final) 3112 { 3113 const dtbl_size_ft needed_evict_min = 3114 dtbl_get_used_formal (dyn) - max_used_final; 3115 /** The starting eviction position */ 3116 const dtbl_idx_ft eviction_start = 3117 dtbl_get_pos_oldest (dyn); 3118 /** The final (inclusive) eviction entry */ 3119 dtbl_idx_ft eviction_end; 3120 3121 dtbl_size_ft evicted_size; 3122 /** The total number of entries to evict */ 3123 dtbl_idx_ft num_to_evict; 3124 3125 mhd_assert (dtbl_get_used_formal (dyn) > max_used_final); 3126 mhd_assert (0u != dyn->cur_size); 3127 mhd_assert (! dtbl_is_empty (dyn)); 3128 mhd_assert (0u != needed_evict_min); 3129 mhd_assert (needed_evict_min <= dyn->cur_size); 3130 3131 eviction_end = eviction_start; 3132 evicted_size = dtbl_pos_size_formal (dyn, 3133 eviction_end); 3134 3135 while (needed_evict_min > evicted_size) 3136 { 3137 eviction_end = dtbl_get_pos_next (dyn, 3138 eviction_end); 3139 3140 mhd_assert (eviction_start != eviction_end); 3141 3142 evicted_size += dtbl_pos_size_formal (dyn, 3143 eviction_end); 3144 } 3145 3146 mhd_assert (needed_evict_min <= evicted_size); 3147 num_to_evict = 3148 (dtbl_get_num_entries (dyn) + eviction_end 3149 - eviction_start) % dtbl_get_num_entries (dyn) + 1u; 3150 mhd_assert (0u != num_to_evict); 3151 mhd_assert (dtbl_get_num_entries (dyn) >= num_to_evict); 3152 3153 if (mhd_COND_ALMOST_NEVER (dtbl_get_num_entries (dyn) == num_to_evict)) 3154 { 3155 /* Simplest situation: evicted all existing entries completely */ 3156 dtbl_reset (dyn); 3157 return; 3158 } 3159 else if (dtbl_get_pos_edge (dyn) == eviction_end) 3160 { 3161 /* Eviction area ends at the edge, at least one entry is not evicted. */ 3162 mhd_assert (eviction_end >= eviction_start); 3163 mhd_assert (dtbl_get_pos_newest (dyn) == (eviction_start - 1u)); 3164 3165 dyn->cur_size -= (dtbl_size_t) evicted_size; 3166 dyn->num_entries = (dtbl_idx_t) eviction_start; 3167 3168 return; 3169 } 3170 else if ((0u != eviction_start) && 3171 (eviction_end >= eviction_start)) 3172 { 3173 /* Entries are evicted in-between of other entries, at least two entries 3174 are not evicted (at the start and at the edge). */ 3175 /** The last entry to keep before the evicted entries */ 3176 dtbl_idx_ft last_entry_keep = dtbl_get_pos_prev (dyn, 3177 eviction_start); 3178 /** The first entry to keep after the evicted entries */ 3179 dtbl_idx_ft first_entry_keep = dtbl_get_pos_next (dyn, 3180 eviction_end); 3181 3182 mhd_assert (first_entry_keep > last_entry_keep); 3183 mhd_assert (dtbl_get_num_entries (dyn) - num_to_evict >= 2u); 3184 mhd_assert (dtbl_get_pos_edge (dyn) >= first_entry_keep); 3185 3186 /* Move not evicted entries at the edge */ 3187 dtbl_move_infos_pos (dyn, 3188 first_entry_keep, 3189 dtbl_get_pos_edge (dyn), 3190 eviction_start); 3191 dyn->cur_size -= (dtbl_size_t) evicted_size; 3192 dyn->num_entries -= (dtbl_idx_t) num_to_evict; 3193 mhd_assert (dtbl_get_pos_edge (dyn) >= dtbl_get_pos_newest (dyn)); 3194 3195 return; 3196 } 3197 else 3198 { 3199 /* Eviction area includes zero position entry, at least one entry is not 3200 evicted. */ 3201 /** The first entry to keep */ 3202 dtbl_idx_ft first_entry_keep = dtbl_get_pos_next (dyn, 3203 eviction_end); 3204 /** The last entry to keep */ 3205 dtbl_idx_ft last_entry_keep = dtbl_get_pos_prev (dyn, 3206 eviction_start); 3207 dtbl_idx_ft num_to_keep = 3208 ((dtbl_idx_ft) (last_entry_keep - first_entry_keep) + 1u); 3209 3210 mhd_assert (dtbl_get_pos_edge (dyn) != eviction_end); 3211 mhd_assert (0u != num_to_keep); 3212 mhd_assert (dtbl_get_num_entries (dyn) > num_to_keep); 3213 mhd_assert (num_to_keep + num_to_evict == dtbl_get_num_entries (dyn)); 3214 3215 dtbl_move_infos_pos (dyn, 3216 first_entry_keep, 3217 last_entry_keep, 3218 0u); 3219 dyn->cur_size -= (dtbl_size_t) evicted_size; 3220 dyn->num_entries = (dtbl_idx_t) num_to_keep; 3221 dyn->newest_pos = dtbl_get_pos_edge (dyn); 3222 3223 return; 3224 } 3225 } 3226 3227 3228 /** 3229 * Adapt the in-memory layout to a new allocation and/or formal size. 3230 * 3231 * The function updates @a dyn to match @a new_alloc_size and 3232 * @a new_formal_size, moving entries information data as needed. 3233 * 3234 * The @a new_formal_size must be larger than or equal to the current formal 3235 * size of the entries in the table. 3236 * The table must not be empty. 3237 * @param dyn the pointer to the dynamic table structure 3238 * @param new_alloc_size the new size of the shared buffer allocation 3239 * @param new_formal_size the new formal HPACK table size limit 3240 */ 3241 static void 3242 dtbl_perform_resize (struct mhd_HpackDTblContext *restrict dyn, 3243 const dtbl_size_ft new_alloc_size, 3244 const dtbl_size_ft new_formal_size) 3245 { 3246 /* Obtain the data from the old table state */ 3247 const struct mhd_HpackDTblEntryInfo *const infos_old_ptr = 3248 dtbl_edge_entry_infoc (dyn); 3249 struct mhd_HpackDTblEntryInfo *infos_new_ptr; 3250 const dtbl_size_ft entries_total_size = 3251 dtbl_get_num_entries (dyn) * mhd_DTBL_ENTRY_INFO_SIZE; 3252 3253 mhd_assert (! dtbl_is_empty (dyn)); 3254 mhd_assert (mhd_DTBL_VALUE_FITS (new_alloc_size)); 3255 mhd_assert (mhd_DTBL_VALUE_FITS (new_formal_size)); 3256 mhd_assert (new_formal_size <= mhd_DTBL_MAX_SIZE); 3257 mhd_assert (new_formal_size < new_alloc_size); 3258 mhd_assert (dtbl_get_used_formal (dyn) <= new_formal_size); 3259 3260 if (dyn->buf_alloc_size > new_alloc_size) 3261 { 3262 /* Shrinking the buffer */ 3263 mhd_assert (dtbl_get_size_max_formal (dyn) > new_formal_size); 3264 mhd_assert (((dyn->buf_alloc_size - new_alloc_size) \ 3265 % mhd_ALIGNOF (struct mhd_HpackDTblEntryInfo)) == 0); 3266 3267 if (dtbl_edge_gap (dyn) < (dyn->buf_alloc_size - new_alloc_size)) 3268 dtbl_compact_strs (dyn); 3269 3270 mhd_assert (dtbl_edge_gap (dyn) >= (dyn->buf_alloc_size - new_alloc_size)); 3271 3272 } 3273 else if (mhd_COND_ALMOST_NEVER (new_alloc_size == dyn->buf_alloc_size)) 3274 { 3275 dyn->size_limit = (dtbl_size_t) new_formal_size; 3276 return; /* Just update the formal size */ 3277 } 3278 else 3279 { 3280 /* Growing the buffer */ 3281 mhd_assert (dtbl_get_size_max_formal (dyn) < new_formal_size); 3282 mhd_assert (((new_alloc_size - dyn->buf_alloc_size) \ 3283 % mhd_ALIGNOF (struct mhd_HpackDTblEntryInfo)) == 0); 3284 } 3285 3286 /* Set the new table size */ 3287 dyn->size_limit = (dtbl_size_t) new_formal_size; 3288 dyn->buf_alloc_size = (dtbl_size_t) new_alloc_size; 3289 3290 /* Get the data location based on the new table size */ 3291 infos_new_ptr = dtbl_edge_entry_info (dyn); 3292 memmove (infos_new_ptr, 3293 infos_old_ptr, 3294 (size_t) entries_total_size); 3295 } 3296 3297 3298 /** 3299 * Adapt the in-memory layout to a new allocation and/or formal size. 3300 * 3301 * The function updates @a dyn to match @a new_alloc_size and 3302 * @a new_formal_size, moving entries information data as needed. 3303 * 3304 * The @a new_formal_size must be larger than or equal to the current formal 3305 * size of the entries in the table. 3306 * @param dyn the pointer to the dynamic table structure 3307 * @param new_alloc_size the new size of the shared buffer allocation 3308 * @param new_formal_size the new formal HPACK table size limit 3309 */ 3310 static void 3311 dtbl_adapt_to_new_size (struct mhd_HpackDTblContext *restrict dyn, 3312 const dtbl_size_ft new_alloc_size, 3313 const dtbl_size_ft new_formal_size) 3314 { 3315 mhd_assert (mhd_DTBL_VALUE_FITS (new_alloc_size)); 3316 mhd_assert (mhd_DTBL_VALUE_FITS (new_formal_size)); 3317 mhd_assert (new_formal_size <= mhd_DTBL_MAX_SIZE); 3318 mhd_assert (new_formal_size < new_alloc_size); 3319 3320 if (! dtbl_is_empty (dyn)) 3321 { 3322 dtbl_perform_resize (dyn, 3323 new_alloc_size, 3324 new_formal_size); 3325 return; /* Internal structure has been fully updated */ 3326 } 3327 3328 /* Just set the new table size */ 3329 dyn->size_limit = (dtbl_size_t) new_formal_size; 3330 dyn->buf_alloc_size = (dtbl_size_t) new_alloc_size; 3331 3332 } 3333 3334 3335 /* ** Allocation helpers ** */ 3336 3337 /** 3338 * Calculate the buffer allocation size from the requested formal table size. 3339 * 3340 * The returned size includes additional slack to reduce the need for frequent 3341 * compaction and is rounded up to alignment suitable for entry information 3342 * data. The size accounts for the alignment difference between the context 3343 * structure and the entry information data. 3344 * 3345 * @param formal_size the requested formal HPACK table size 3346 * @return the allocation size for the strings/infos shared buffer 3347 */ 3348 mhd_static_inline dtbl_size_t 3349 dtbl_calc_alloc_size (dtbl_size_ft formal_size) 3350 { 3351 dtbl_size_ft dyn_table_alloc_size; 3352 3353 mhd_assert (mhd_DTBL_VALUE_FITS (formal_size)); 3354 3355 dyn_table_alloc_size = formal_size; 3356 /* Add some slack to lower the need for the buffer compaction */ 3357 dyn_table_alloc_size += formal_size / 64; 3358 dyn_table_alloc_size += 2 * mhd_DTBL_ENTRY_INFO_SIZE; 3359 /* Round up to alignment of the entry info data, which is placed at the 3360 end of the buffer. */ 3361 dyn_table_alloc_size = 3362 ((dyn_table_alloc_size + mhd_ALIGNOF (struct mhd_HpackDTblEntryInfo) - 1u) 3363 / mhd_ALIGNOF (struct mhd_HpackDTblEntryInfo)) 3364 * mhd_ALIGNOF (struct mhd_HpackDTblEntryInfo); 3365 /* Adjust the size of the allocation in case the alignment of 3366 mhd_HpackDTblEntryInfo is stricter than that of mhd_HpackDTblContext */ 3367 dyn_table_alloc_size += 3368 (mhd_ALIGNOF (struct mhd_HpackDTblEntryInfo) 3369 - (sizeof(struct mhd_HpackDTblContext) 3370 % mhd_ALIGNOF (struct mhd_HpackDTblEntryInfo))) 3371 % mhd_ALIGNOF (struct mhd_HpackDTblEntryInfo); 3372 3373 mhd_assert (mhd_DTBL_VALUE_FITS (dyn_table_alloc_size)); 3374 3375 return (dtbl_size_t) dyn_table_alloc_size; 3376 } 3377 3378 3379 /* ** Entries finders ** */ 3380 3381 /** 3382 * Find an entry in the dynamic table that exactly matches the given 3383 * name and value. 3384 * 3385 * The @a name and @a val do not need to be zero-terminated. 3386 * The table must not be empty. 3387 * 3388 * @param dyn const pointer to the dynamic table structure 3389 * @param name_len length of @a name in bytes 3390 * @param name pointer to the header field name 3391 * @param val_len length of @a val in bytes 3392 * @param val pointer to the header field value 3393 * @return the HPACK index (> #mhd_HPACK_STBL_LAST_IDX) of the matching entry, 3394 * or 0 if not found 3395 */ 3396 static MHD_FN_PAR_IN_SIZE_ (3,2) MHD_FN_PAR_IN_SIZE_ (5,4) dtbl_idx_t 3397 dtbl_find_entry (const struct mhd_HpackDTblContext *restrict dyn, 3398 dtbl_size_ft name_len, 3399 const char *restrict name, 3400 dtbl_size_ft val_len, 3401 const char *restrict val) 3402 { 3403 /* The table must not be empty */ 3404 const struct mhd_HpackDTblEntryInfo *entries = 3405 dtbl_get_infos_as_arrayc (dyn); 3406 dtbl_idx_ft i; 3407 for (i = 0u; i < dtbl_get_num_entries (dyn); ++i) 3408 { 3409 const struct mhd_HpackDTblEntryInfo *const entry = entries + i; 3410 3411 if (name_len != entry->name_len) 3412 continue; 3413 if (val_len != entry->val_len) 3414 continue; 3415 if (((0u == name_len) || 3416 (0 == memcmp (name, 3417 dtbl_entr_strs_ptr_namec (dyn, 3418 entry), 3419 name_len))) 3420 && 3421 ((0u == val_len) || 3422 (0 == memcmp (val, 3423 dtbl_entr_strs_ptr_valuec (dyn, 3424 entry), 3425 val_len)))) 3426 { /* Found the entry */ 3427 return dtbl_get_hpack_idx_from_pos (dyn, 3428 dtbl_get_pos_edge (dyn) - i); 3429 } 3430 } 3431 return 0u; /* Not found */ 3432 } 3433 3434 3435 /** 3436 * Find an entry in the dynamic table whose name exactly matches @a name. 3437 * 3438 * The @a name does not need to be zero-terminated. 3439 * The table must not be empty. 3440 * 3441 * @param dyn const pointer to the dynamic table structure 3442 * @param name_len length of @a name in bytes 3443 * @param name pointer to the header field name 3444 * @return the HPACK index (> #mhd_HPACK_STBL_LAST_IDX) of the matching entry, 3445 * or 0 if not found 3446 */ 3447 static MHD_FN_PAR_IN_SIZE_ (3,2) dtbl_idx_t 3448 dtbl_find_name (const struct mhd_HpackDTblContext *restrict dyn, 3449 dtbl_size_ft name_len, 3450 const char *restrict name) 3451 { 3452 /* The table must not be empty */ 3453 const struct mhd_HpackDTblEntryInfo *entries = 3454 dtbl_get_infos_as_arrayc (dyn); 3455 dtbl_idx_ft i; 3456 for (i = 0u; i < dtbl_get_num_entries (dyn); ++i) 3457 { 3458 const struct mhd_HpackDTblEntryInfo *const entry = entries + i; 3459 3460 if (name_len != entry->name_len) 3461 continue; 3462 if ((0u == name_len) || 3463 (0 == memcmp (name, 3464 dtbl_entr_strs_ptr_namec (dyn, 3465 entry), 3466 name_len))) 3467 { /* Found the entry */ 3468 return dtbl_get_hpack_idx_from_pos (dyn, 3469 dtbl_get_pos_edge (dyn) - i); 3470 } 3471 } 3472 return 0u; /* Not found */ 3473 } 3474 3475 3476 /* **** ________________ End of dynamic table helpers _________________ **** */ 3477 3478 /* ****** ------------------- Dynamic table API --------------------- ****** */ 3479 3480 /* 3481 * The API is designed to be used by one thread only. 3482 * If any thread is modifying the data in the dynamic table, then any access 3483 * in any other thread at the same time is not safe! 3484 */ 3485 3486 3487 /** 3488 * Create a dynamic HPACK table context with the specified formal size limit. 3489 * 3490 * The allocation includes the context and a shared buffer. The table is 3491 * initialised to an empty state. The function allocates slightly more than 3492 * @a dyn_table_size due to the internal overhead. 3493 * 3494 * @param dyn_table_size the requested formal HPACK table size limit 3495 * @return pointer to the newly created context on success, 3496 * NULL on allocation failure 3497 */ 3498 static mhd_FN_RET_UNALIASED 3499 struct mhd_HpackDTblContext * 3500 mhd_dtbl_create (size_t dyn_table_size) 3501 { 3502 struct mhd_HpackDTblContext*dyn; 3503 dtbl_size_ft alloc_size; 3504 mhd_assert (mhd_DTBL_MAX_SIZE >= dyn_table_size); 3505 mhd_assert (mhd_DTBL_VALUE_FITS (dyn_table_size)); 3506 3507 alloc_size = dtbl_calc_alloc_size ((dtbl_size_ft) dyn_table_size); 3508 3509 dyn = (struct mhd_HpackDTblContext*) malloc (sizeof(*dyn) 3510 + (size_t) alloc_size); 3511 if (NULL == dyn) 3512 return NULL; /* Failure exit point */ 3513 3514 dyn->buf_alloc_size = (dtbl_size_t) alloc_size; 3515 dyn->size_limit = (dtbl_size_t) dyn_table_size; 3516 dtbl_reset (dyn); 3517 3518 dtbl_check_internals (dyn); 3519 3520 return dyn; 3521 } 3522 3523 3524 /** 3525 * Destroy a dynamic HPACK table context and free all associated memory. 3526 * 3527 * @param dyn the pointer to the dynamic table structure to destroy 3528 */ 3529 mhd_static_inline MHD_FN_PAR_NONNULL_ALL_ void 3530 mhd_dtbl_destroy (struct mhd_HpackDTblContext *dyn) 3531 { 3532 dtbl_check_internals (dyn); 3533 /* Everything is in a single memory allocation, just free it */ 3534 free (dyn); 3535 } 3536 3537 3538 /** 3539 * Get the current formal maximum table size (the HPACK size limit). 3540 * @param dyn the pointer to the dynamic table structure 3541 * @return the formal maximum size of the table 3542 */ 3543 static MHD_FN_PURE_ size_t 3544 mhd_dtbl_get_table_max_size (const struct mhd_HpackDTblContext *dyn) 3545 { 3546 return (size_t) dtbl_get_size_max_formal (dyn); 3547 } 3548 3549 3550 /** 3551 * Get the current amount of formal used space in the table. 3552 * @param dyn the pointer to the dynamic table structure 3553 * @return the formal used space in the table 3554 */ 3555 static MHD_FN_PURE_ size_t 3556 mhd_dtbl_get_table_used (const struct mhd_HpackDTblContext *dyn) 3557 { 3558 return (size_t) dtbl_get_used_formal (dyn); 3559 } 3560 3561 3562 /** 3563 * Get the current number of entries in the table. 3564 * @param dyn the pointer to the dynamic table structure 3565 * @return the number of entries in the table 3566 */ 3567 static MHD_FN_PURE_ size_t 3568 mhd_dtbl_get_num_entries (const struct mhd_HpackDTblContext *dyn) 3569 { 3570 return (size_t) dtbl_get_num_entries (dyn); 3571 } 3572 3573 3574 /** 3575 * Evict the oldest dynamic-table entries until the formal (HPACK) used size 3576 * becomes less than or equal to the requested value. 3577 * 3578 * If the table is already within the limit, nothing is changed. 3579 * 3580 * The function does not change the formal maximum table size and does not 3581 * allocate memory. 3582 * 3583 * @param dyn the pointer to the dynamic table structure 3584 * @param max_used_formal the target upper bound (in bytes) for the formal 3585 * used size after eviction 3586 */ 3587 static void 3588 mhd_dtbl_evict_to_size (struct mhd_HpackDTblContext *dyn, 3589 size_t max_used_formal) 3590 { 3591 if (dtbl_is_empty (dyn)) 3592 return; 3593 else if (0u == max_used_formal) 3594 dtbl_reset (dyn); 3595 else if (dtbl_get_used_formal (dyn) <= max_used_formal) 3596 return; 3597 else 3598 dtbl_evict_to_size (dyn, 3599 (dtbl_size_t) max_used_formal); 3600 3601 dtbl_check_internals (dyn); 3602 } 3603 3604 3605 /** 3606 * Resize the dynamic HPACK table. 3607 * 3608 * On allocation failure when growing, the original table is unchanged. 3609 * The shrinking of the table never fails. 3610 * 3611 * @param dyn_pp the pointer to the variable holding the pointer dynamic 3612 * table structure, the value of the variable could be updated 3613 * @param dyn_table_size the new formal HPACK table size limit 3614 * @return 'true' on success (the variable pointer by @a dyn_pp could be 3615 * updated), 3616 * 'false' if growing failed (the dynamic table remains valid, but 3617 * not resized) 3618 */ 3619 static bool 3620 mhd_dtbl_resize (struct mhd_HpackDTblContext** const dyn_pp, 3621 size_t dyn_table_size) 3622 { 3623 const dtbl_size_ft old_official_size = dtbl_get_size_max_formal (*dyn_pp); 3624 dtbl_size_ft new_alloc_size; 3625 struct mhd_HpackDTblContext *new_dyn; 3626 mhd_assert (mhd_DTBL_MAX_SIZE >= dyn_table_size); 3627 mhd_assert (mhd_DTBL_VALUE_FITS (dyn_table_size)); 3628 3629 if (old_official_size == dyn_table_size) 3630 return true; /* Do nothing */ 3631 3632 new_alloc_size = dtbl_calc_alloc_size ((dtbl_size_ft) dyn_table_size); 3633 3634 if (old_official_size < dyn_table_size) 3635 { 3636 /* Growing table size */ 3637 /* No need to evict */ 3638 new_dyn = (struct mhd_HpackDTblContext*) 3639 realloc (*dyn_pp, 3640 sizeof(**dyn_pp) + (size_t) new_alloc_size); 3641 if (NULL == new_dyn) 3642 return false; /* No table resize */ 3643 *dyn_pp = new_dyn; 3644 3645 /* Adapt the table data to the larger size */ 3646 dtbl_adapt_to_new_size (new_dyn, 3647 new_alloc_size, 3648 (dtbl_size_ft) dyn_table_size); 3649 } 3650 else 3651 { 3652 /* Shrinking table size */ 3653 mhd_dtbl_evict_to_size (*dyn_pp, 3654 (dtbl_size_ft) dyn_table_size); 3655 3656 /* Adapt table data before resizing */ 3657 dtbl_adapt_to_new_size (*dyn_pp, 3658 new_alloc_size, 3659 (dtbl_size_ft) dyn_table_size); 3660 3661 /* Try to reduce the allocated memory */ 3662 new_dyn = (struct mhd_HpackDTblContext*) 3663 realloc (*dyn_pp, 3664 sizeof(**dyn_pp) + (size_t) new_alloc_size); 3665 3666 /* If realloc() failed, just use the previous allocation. 3667 The table will use the new (reduced) size anyway, while the allocation 3668 will be kept larger than needed. */ 3669 if (mhd_COND_VIRTUALLY_ALWAYS (NULL != new_dyn)) 3670 *dyn_pp = new_dyn; 3671 } 3672 3673 dtbl_check_internals (new_dyn); 3674 3675 return true; 3676 } 3677 3678 3679 /** 3680 * Check whether the new entry may fit the dynamic table 3681 * @param dyn the pointer to the dynamic table structure 3682 * @param name_len the length of the name of the new entry 3683 * @param val_len the length of the value of the new entry 3684 * @return 'true' if the new entry may be stored in the @a dyn dynamic table, 3685 * 'false' if the new entry formal size is larger than @a dyn may hold. 3686 */ 3687 static bool 3688 mhd_dtbl_check_entry_fit (struct mhd_HpackDTblContext *restrict dyn, 3689 size_t name_len, 3690 size_t val_len) 3691 { 3692 size_t entry_size; 3693 /* Carefully check the values, taking into account possible type overflow 3694 when performing calculations */ 3695 entry_size = name_len + val_len; 3696 if (mhd_COND_HARDLY_EVER (entry_size < val_len)) 3697 return false; 3698 entry_size += mhd_dtbl_entry_overhead; 3699 if (mhd_COND_HARDLY_EVER (entry_size < mhd_dtbl_entry_overhead)) 3700 return false; 3701 3702 return (dtbl_get_size_max_formal (dyn) >= entry_size); 3703 } 3704 3705 3706 /** 3707 * Add a new entry to the dynamic table. 3708 * 3709 * If the entry cannot fit the table size limit, the table is reset to the 3710 * empty state and the entry is discarded. 3711 * If there is enough formal free space, the entry is inserted. Otherwise, the 3712 * oldest entries are evicted and the new entry is inserted. 3713 * 3714 * The function copies the provided strings into the table's buffer. 3715 * @param dyn the pointer to the dynamic table structure 3716 * @param name_len the length of the @a name, must fit #mhd_HPACK_DTBL_BITS bits 3717 * @param name the name of the header, does NOT need to be zero-terminated 3718 * @param val_len the length of the @a val, must fit #mhd_HPACK_DTBL_BITS bits 3719 * @param val the value of the header, does NOT need to be zero terminated 3720 */ 3721 static MHD_FN_PAR_IN_SIZE_ (3,2) MHD_FN_PAR_IN_SIZE_ (5,4) void 3722 mhd_dtbl_new_entry (struct mhd_HpackDTblContext *restrict dyn, 3723 size_t name_len, 3724 const char *restrict name, 3725 size_t val_len, 3726 const char *restrict val) 3727 { 3728 if (mhd_COND_ALMOST_NEVER (! mhd_dtbl_check_entry_fit (dyn, 3729 name_len, 3730 val_len))) 3731 { 3732 /* The entry cannot fit the table. 3733 * Reset table to empty state (need to evict all entries). */ 3734 dtbl_reset (dyn); 3735 3736 } 3737 else if (dtbl_get_free_formal (dyn) 3738 >= dtbl_new_entry_size_formal ((dtbl_size_ft) name_len, 3739 (dtbl_size_ft) val_len)) 3740 { 3741 /* Enough space. Insert new entry. */ 3742 mhd_assert (mhd_DTBL_VALUE_FITS (name_len)); 3743 mhd_assert (mhd_DTBL_VALUE_FITS (val_len)); 3744 dtbl_extend_with_entry (dyn, 3745 (dtbl_size_ft) name_len, 3746 name, 3747 (dtbl_size_ft) val_len, 3748 val); 3749 } 3750 else 3751 { 3752 /* Not enough free space, but the new entry fit the table after eviction. 3753 * Evict some entries and add a new one. */ 3754 mhd_assert (mhd_DTBL_VALUE_FITS (name_len)); 3755 mhd_assert (mhd_DTBL_VALUE_FITS (val_len)); 3756 dtbl_evict_add_entry (dyn, 3757 (dtbl_size_ft) name_len, 3758 name, 3759 (dtbl_size_ft) val_len, 3760 val); 3761 } 3762 3763 dtbl_check_internals (dyn); 3764 } 3765 3766 3767 /** 3768 * Get a dynamic-table entry by HPACK index. 3769 * 3770 * The HPACK index must refer to the dynamic table (greater than the number 3771 * of entries in the static table). On success, the function returns pointers 3772 * to the non-zero-terminated name and value buffers inside the table and 3773 * their lengths. 3774 * 3775 * The strings returned (on success) in @a name_out and @a value_out must be 3776 * used/processed before any other actions with the dynamic table. Any change 3777 * in the dynamic table may invalidate pointers in @a name_out and 3778 * @a value_out. 3779 * 3780 * Behaviour is undefined if @a idx is less or equal to #mhd_HPACK_STBL_LAST_IDX 3781 * 3782 * @param dyn const pointer to the dynamic table structure 3783 * @param idx the HPACK index of the requested entry, must be strictly larger 3784 * than #mhd_HPACK_STBL_LAST_IDX 3785 * @param[out] name_out the output buffer for the header name, 3786 * the result is NOT zero-terminated 3787 * @param[out] value_out the output buffer for the header value, 3788 * the result is NOT zero-terminated 3789 * @return 'true' if the entry exists and output buffers are set, 3790 * 'false' otherwise 3791 */ 3792 static MHD_FN_PAR_OUT_ (3) MHD_FN_PAR_OUT_ (4) bool 3793 mhd_dtbl_get_entry (const struct mhd_HpackDTblContext *restrict dyn, 3794 dtbl_idx_ft idx, 3795 struct mhd_BufferConst *restrict name_out, 3796 struct mhd_BufferConst *restrict value_out) 3797 { 3798 const struct mhd_HpackDTblEntryInfo *entry; 3799 mhd_assert (mhd_HPACK_STBL_LAST_IDX < idx); 3800 if (dtbl_is_empty (dyn)) 3801 return false; 3802 if (dtbl_get_pos_edge (dyn) < (idx - mhd_dtbl_hpack_idx_offset)) 3803 return false; 3804 3805 entry = dtbl_pos_entry_infoc (dyn, 3806 dtbl_get_pos_from_hpack_idx (dyn, 3807 idx)); 3808 name_out->size = (size_t) entry->name_len; 3809 name_out->data = dtbl_entr_strs_ptr_startc (dyn, 3810 entry); 3811 value_out->size = (size_t) entry->val_len; 3812 value_out->data = name_out->data + name_out->size; 3813 3814 return true; 3815 } 3816 3817 3818 /** 3819 * Look up a dynamic-table entry equal to the provided name and value. 3820 * 3821 * If the table is empty or no exact match is found, 0 is returned. 3822 * The input strings do not need to be zero-terminated. 3823 * 3824 * @param dyn const pointer to the dynamic table structure 3825 * @param name_len length of @a name in bytes 3826 * @param name pointer to the header field name, 3827 * does NOT need to be zero-terminated 3828 * @param val_len length of @a val in bytes 3829 * @param val pointer to the header field value, 3830 * does NOT need to be zero-terminated 3831 * @return the HPACK index (> #mhd_HPACK_STBL_LAST_IDX) of the matching entry, 3832 * or 0 if not found 3833 */ 3834 static MHD_FN_PAR_IN_SIZE_ (3,2) MHD_FN_PAR_IN_SIZE_ (5,4) dtbl_idx_t 3835 mhd_dtbl_find_entry (const struct mhd_HpackDTblContext *restrict dyn, 3836 size_t name_len, 3837 const char *restrict name, 3838 size_t val_len, 3839 const char *restrict val) 3840 { 3841 if (dtbl_is_empty (dyn)) 3842 return 0u; 3843 3844 if (mhd_COND_HARDLY_EVER (! mhd_DTBL_VALUE_FITS (name_len))) 3845 return 0u; 3846 if (mhd_COND_HARDLY_EVER (! mhd_DTBL_VALUE_FITS (val_len))) 3847 return 0u; 3848 3849 return dtbl_find_entry (dyn, 3850 (dtbl_size_ft) name_len, 3851 name, 3852 (dtbl_size_ft) val_len, 3853 val); 3854 } 3855 3856 3857 /** 3858 * Look up a dynamic-table entry whose name equals @a name. 3859 * 3860 * If the table is empty or no match is found, 0 is returned. 3861 * The input string does not need to be zero-terminated. 3862 * 3863 * @param dyn const pointer to the dynamic table structure 3864 * @param name_len length of @a name in bytes 3865 * @param name pointer to the header field name, 3866 * does NOT need to be zero-terminated 3867 * @return the HPACK index (> #mhd_HPACK_STBL_LAST_IDX) of the matching entry, 3868 * or 0 if not found 3869 */ 3870 static MHD_FN_PAR_IN_SIZE_ (3,2) dtbl_idx_t 3871 mhd_dtbl_find_name (const struct mhd_HpackDTblContext *restrict dyn, 3872 size_t name_len, 3873 const char *restrict name) 3874 { 3875 if (dtbl_is_empty (dyn)) 3876 return 0u; 3877 3878 if (mhd_COND_HARDLY_EVER (! mhd_DTBL_VALUE_FITS (name_len))) 3879 return 0u; 3880 3881 return dtbl_find_name (dyn, 3882 (dtbl_size_ft) name_len, 3883 name); 3884 } 3885 3886 3887 /* ****** ----------------- Static table handling ----------------- ****** */ 3888 /* ======================================================================== 3889 * 3890 * The static table data should be accessed only by mhd_* functions. 3891 * 3892 * All functions prefixed with stbl_* are internal helpers and should not 3893 * be used directly. 3894 * 3895 * ======================================================================== 3896 */ 3897 3898 /** 3899 * HPACK static table element 3900 */ 3901 struct mhd_HpackStaticEntry 3902 { 3903 /** 3904 * The name of the header field 3905 */ 3906 const struct MHD_String name; 3907 /** 3908 * The value of the header field. 3909 */ 3910 const struct MHD_String value; 3911 }; 3912 3913 /* The next variable cannot be declared as 'mhd_constexpr' as it contains 3914 pointers to the strings */ 3915 /** 3916 * HPACK static table. 3917 * Add 1 to the array index to obtain the HPACK index. 3918 * 3919 * This table is extracted (and transformed) from RFC 7541. 3920 * See https://datatracker.ietf.org/doc/html/rfc7541#appendix-A 3921 */ 3922 static const struct mhd_HpackStaticEntry 3923 mhd_hpack_static[mhd_HPACK_STBL_ENTRIES] = { 3924 /* 1 */ { mhd_MSTR_INIT (":authority"), mhd_MSTR_INIT ("") }, 3925 /* 2 */ { mhd_MSTR_INIT (":method"), mhd_MSTR_INIT ("GET") }, 3926 /* 3 */ { mhd_MSTR_INIT (":method"), mhd_MSTR_INIT ("POST") }, 3927 /* 4 */ { mhd_MSTR_INIT (":path"), mhd_MSTR_INIT ("/") }, 3928 /* 5 */ { mhd_MSTR_INIT (":path"), mhd_MSTR_INIT ("/index.html") }, 3929 /* 6 */ { mhd_MSTR_INIT (":scheme"), mhd_MSTR_INIT ("http") }, 3930 /* 7 */ { mhd_MSTR_INIT (":scheme"), mhd_MSTR_INIT ("https") }, 3931 /* 8 */ { mhd_MSTR_INIT (":status"), mhd_MSTR_INIT ("200") }, 3932 /* 9 */ { mhd_MSTR_INIT (":status"), mhd_MSTR_INIT ("204") }, 3933 /* 10 */ { mhd_MSTR_INIT (":status"), mhd_MSTR_INIT ("206") }, 3934 /* 11 */ { mhd_MSTR_INIT (":status"), mhd_MSTR_INIT ("304") }, 3935 /* 12 */ { mhd_MSTR_INIT (":status"), mhd_MSTR_INIT ("400") }, 3936 /* 13 */ { mhd_MSTR_INIT (":status"), mhd_MSTR_INIT ("404") }, 3937 /* 14 */ { mhd_MSTR_INIT (":status"), mhd_MSTR_INIT ("500") }, 3938 /* 15 */ { mhd_MSTR_INIT ("accept-charset"), mhd_MSTR_INIT ("") }, 3939 /* 16 */ { mhd_MSTR_INIT ("accept-encoding"), 3940 mhd_MSTR_INIT ("gzip, deflate") }, 3941 /* 17 */ { mhd_MSTR_INIT ("accept-language"), mhd_MSTR_INIT ("") }, 3942 /* 18 */ { mhd_MSTR_INIT ("accept-ranges"), mhd_MSTR_INIT ("") }, 3943 /* 19 */ { mhd_MSTR_INIT ("accept"), mhd_MSTR_INIT ("") }, 3944 /* 20 */ { mhd_MSTR_INIT ("access-control-allow-origin"), 3945 mhd_MSTR_INIT ("") }, 3946 /* 21 */ { mhd_MSTR_INIT ("age"), mhd_MSTR_INIT ("") }, 3947 /* 22 */ { mhd_MSTR_INIT ("allow"), mhd_MSTR_INIT ("") }, 3948 /* 23 */ { mhd_MSTR_INIT ("authorization"), mhd_MSTR_INIT ("") }, 3949 /* 24 */ { mhd_MSTR_INIT ("cache-control"), mhd_MSTR_INIT ("") }, 3950 /* 25 */ { mhd_MSTR_INIT ("content-disposition"), mhd_MSTR_INIT ("") }, 3951 /* 26 */ { mhd_MSTR_INIT ("content-encoding"), mhd_MSTR_INIT ("") }, 3952 /* 27 */ { mhd_MSTR_INIT ("content-language"), mhd_MSTR_INIT ("") }, 3953 /* 28 */ { mhd_MSTR_INIT ("content-length"), mhd_MSTR_INIT ("") }, 3954 /* 29 */ { mhd_MSTR_INIT ("content-location"), mhd_MSTR_INIT ("") }, 3955 /* 30 */ { mhd_MSTR_INIT ("content-range"), mhd_MSTR_INIT ("") }, 3956 /* 31 */ { mhd_MSTR_INIT ("content-type"), mhd_MSTR_INIT ("") }, 3957 /* 32 */ { mhd_MSTR_INIT ("cookie"), mhd_MSTR_INIT ("") }, 3958 /* 33 */ { mhd_MSTR_INIT ("date"), mhd_MSTR_INIT ("") }, 3959 /* 34 */ { mhd_MSTR_INIT ("etag"), mhd_MSTR_INIT ("") }, 3960 /* 35 */ { mhd_MSTR_INIT ("expect"), mhd_MSTR_INIT ("") }, 3961 /* 36 */ { mhd_MSTR_INIT ("expires"), mhd_MSTR_INIT ("") }, 3962 /* 37 */ { mhd_MSTR_INIT ("from"), mhd_MSTR_INIT ("") }, 3963 /* 38 */ { mhd_MSTR_INIT ("host"), mhd_MSTR_INIT ("") }, 3964 /* 39 */ { mhd_MSTR_INIT ("if-match"), mhd_MSTR_INIT ("") }, 3965 /* 40 */ { mhd_MSTR_INIT ("if-modified-since"), mhd_MSTR_INIT ("") }, 3966 /* 41 */ { mhd_MSTR_INIT ("if-none-match"), mhd_MSTR_INIT ("") }, 3967 /* 42 */ { mhd_MSTR_INIT ("if-range"), mhd_MSTR_INIT ("") }, 3968 /* 43 */ { mhd_MSTR_INIT ("if-unmodified-since"), mhd_MSTR_INIT ("") }, 3969 /* 44 */ { mhd_MSTR_INIT ("last-modified"), mhd_MSTR_INIT ("") }, 3970 /* 45 */ { mhd_MSTR_INIT ("link"), mhd_MSTR_INIT ("") }, 3971 /* 46 */ { mhd_MSTR_INIT ("location"), mhd_MSTR_INIT ("") }, 3972 /* 47 */ { mhd_MSTR_INIT ("max-forwards"), mhd_MSTR_INIT ("") }, 3973 /* 48 */ { mhd_MSTR_INIT ("proxy-authenticate"), mhd_MSTR_INIT ("") }, 3974 /* 49 */ { mhd_MSTR_INIT ("proxy-authorization"), mhd_MSTR_INIT ("") }, 3975 /* 50 */ { mhd_MSTR_INIT ("range"), mhd_MSTR_INIT ("") }, 3976 /* 51 */ { mhd_MSTR_INIT ("referer"), mhd_MSTR_INIT ("") }, 3977 /* 52 */ { mhd_MSTR_INIT ("refresh"), mhd_MSTR_INIT ("") }, 3978 /* 53 */ { mhd_MSTR_INIT ("retry-after"), mhd_MSTR_INIT ("") }, 3979 /* 54 */ { mhd_MSTR_INIT ("server"), mhd_MSTR_INIT ("") }, 3980 /* 55 */ { mhd_MSTR_INIT ("set-cookie"), mhd_MSTR_INIT ("") }, 3981 /* 56 */ { mhd_MSTR_INIT ("strict-transport-security"), mhd_MSTR_INIT ("") }, 3982 /* 57 */ { mhd_MSTR_INIT ("transfer-encoding"), mhd_MSTR_INIT ("") }, 3983 /* 58 */ { mhd_MSTR_INIT ("user-agent"), mhd_MSTR_INIT ("") }, 3984 /* 59 */ { mhd_MSTR_INIT ("vary"), mhd_MSTR_INIT ("") }, 3985 /* 60 */ { mhd_MSTR_INIT ("via"), mhd_MSTR_INIT ("") }, 3986 /* 61 */ { mhd_MSTR_INIT ("www-authenticate"), mhd_MSTR_INIT ("") } 3987 }; 3988 3989 /** 3990 * The position of the first ":status" pseud-header field in the 3991 * @a mhd_hpack_static table 3992 */ 3993 #define mhd_HPACK_STBL_PF_STATUS_START_POS (8u) 3994 3995 /** 3996 * Convert an HPACK index (matching the static table) to a 0-based position in 3997 * the static table data. 3998 * 3999 * Behaviour is undefined if @a hpack_idx is 0 or greater than 4000 * #mhd_HPACK_STBL_LAST_IDX. 4001 * @param hpack_idx the HPACK index of the static-table entry 4002 * (1 .. #mhd_HPACK_STBL_LAST_IDX) 4003 * @return the 0-based position corresponding to @a hpack_idx 4004 */ 4005 MHD_FN_CONST_ mhd_static_inline dtbl_idx_t 4006 stbl_get_pos_from_hpack_idx (dtbl_idx_ft hpack_idx) 4007 { 4008 mhd_assert (0u != hpack_idx); 4009 mhd_assert (mhd_HPACK_STBL_LAST_IDX >= hpack_idx); 4010 return (dtbl_idx_t) (hpack_idx - 1u); 4011 } 4012 4013 4014 /** 4015 * Convert a 0-based static table position to the HPACK index. 4016 * 4017 * The returned index is in the range 1 .. #mhd_HPACK_STBL_LAST_IDX. 4018 * 4019 * Behaviour is undefined if @a loc_pos is not a valid static-table position, 4020 * i.e. if it is greater than or equal to #mhd_HPACK_STBL_ENTRIES. 4021 * @param loc_pos the 0-based position in the static table 4022 * @return the HPACK index corresponding to @a loc_pos 4023 */ 4024 MHD_FN_CONST_ mhd_static_inline dtbl_idx_t 4025 stbl_get_hpack_idx_from_pos (dtbl_idx_ft loc_pos) 4026 { 4027 mhd_assert (mhd_HPACK_STBL_LAST_IDX > loc_pos); 4028 return (dtbl_idx_t) (loc_pos + 1u); 4029 } 4030 4031 4032 /** 4033 * Get a pointer to the static table entry by its 0-based position. 4034 * 4035 * Behaviour is undefined if @a loc_pos is not a valid static-table position, 4036 * i.e. if it is greater than or equal to #mhd_HPACK_STBL_ENTRIES. 4037 * @param loc_pos the 0-based position in the static table 4038 * @return const pointer to the static entry descriptor 4039 */ 4040 MHD_FN_CONST_ mhd_static_inline const struct mhd_HpackStaticEntry * 4041 stbl_pos_entry_info (dtbl_idx_ft loc_pos) 4042 { 4043 mhd_assert (sizeof(mhd_hpack_static) / sizeof(mhd_hpack_static[0]) \ 4044 == mhd_HPACK_STBL_ENTRIES); 4045 mhd_assert (mhd_HPACK_STBL_ENTRIES > loc_pos); 4046 return mhd_hpack_static + loc_pos; 4047 } 4048 4049 4050 /** 4051 * Get a pointer to the static table entry by its HPACK index. 4052 * 4053 * Behaviour is undefined if @a hpack_idx is 0 or greater than 4054 * #mhd_HPACK_STBL_LAST_IDX. 4055 * @param hpack_idx the HPACK index of the entry 4056 * @return const pointer to the static entry descriptor 4057 */ 4058 MHD_FN_CONST_ mhd_static_inline const struct mhd_HpackStaticEntry * 4059 stbl_idx_entry_info (dtbl_idx_ft hpack_idx) 4060 { 4061 return stbl_pos_entry_info (stbl_get_pos_from_hpack_idx (hpack_idx)); 4062 } 4063 4064 4065 /* **** _____________ End of static table data helpers ______________ ****** */ 4066 4067 /* ****------------------- Static table data API ---------------------****** */ 4068 /** 4069 * The position of the first real (non-pseudo) header in the 4070 * @a mhd_hpack_static table 4071 */ 4072 #define mhd_HPACK_STBL_NORM_START_POS (14u) 4073 4074 /** 4075 * The position of the only real (non-pseudo) header with a non-empty value in 4076 * the @a mhd_hpack_static table 4077 */ 4078 #define mhd_HPACK_STBL_NORM_WITH_VALUE_POS (15u) 4079 4080 /** 4081 * Get a static-table entry by HPACK index. 4082 * 4083 * The index @a idx must refer to the static table 4084 * (i.e. 1 .. #mhd_HPACK_STBL_LAST_IDX). 4085 * On return, @a name_out and @a value_out are set to point to the entry 4086 * data and their lengths. 4087 * 4088 * Behaviour is undefined if @a idx is 0 or greater 4089 * than #mhd_HPACK_STBL_LAST_IDX. 4090 * @param idx the HPACK index within the static table 4091 * @param[out] name_out output buffer for the header name 4092 * @param[out] value_out output buffer for the header value 4093 */ 4094 static MHD_FN_PAR_OUT_ (2) MHD_FN_PAR_OUT_ (3) void 4095 mhd_stbl_get_entry (dtbl_idx_ft idx, 4096 struct mhd_BufferConst *restrict name_out, 4097 struct mhd_BufferConst *restrict value_out) 4098 { 4099 const struct mhd_HpackStaticEntry *const entry = stbl_idx_entry_info (idx); 4100 4101 name_out->size = entry->name.len; 4102 name_out->data = entry->name.cstr; 4103 value_out->size = entry->value.len; 4104 value_out->data = entry->value.cstr; 4105 } 4106 4107 4108 /** 4109 * Find a static-table entry among "real" (non-pseudo) headers that exactly 4110 * matches the given name and value. 4111 * 4112 * The header name must not start with ':'. 4113 * The input strings do not need to be zero-terminated. 4114 * 4115 * @param name_len length of @a name in bytes, 4116 * must not be zero 4117 * @param name pointer to the header field name, 4118 * does NOT need to be zero-terminated 4119 * @param val_len length of @a val in bytes 4120 * @param val pointer to the header field value, 4121 * does NOT need to be zero-terminated 4122 * @return the HPACK index (<= #mhd_HPACK_STBL_LAST_IDX) of the matching 4123 * static entry, or 0 if not found 4124 */ 4125 static MHD_FN_PAR_IN_SIZE_ (2,1) MHD_FN_PAR_IN_SIZE_ (4,3) dtbl_idx_t 4126 mhd_stbl_find_entry_real (size_t name_len, 4127 const char *restrict name, 4128 size_t val_len, 4129 const char *restrict val) 4130 { 4131 #ifndef MHD_UNIT_TESTING /* Do not abort on a wrong name when unit-testing */ 4132 mhd_assert (0u != name_len); 4133 mhd_assert (':' != name[0]); 4134 #endif /* ! MHD_UNIT_TESTING */ 4135 #ifndef MHD_FAVOR_SMALL_CODE 4136 if (mhd_COND_ALMOST_ALWAYS (0u != val_len)) 4137 { /* non-empty 'value' */ 4138 /* Process the only normal (real header) entry that has non-empty value */ 4139 mhd_constexpr dtbl_idx_ft i = mhd_HPACK_STBL_NORM_WITH_VALUE_POS; 4140 do 4141 { 4142 const struct mhd_HpackStaticEntry *const entry = stbl_pos_entry_info (i); 4143 4144 if (name_len != entry->name.len) 4145 continue; 4146 mhd_assert (0u != entry->name.len); 4147 mhd_assert (0u != entry->value.len); 4148 4149 if (0 == memcmp (name, 4150 entry->name.cstr, 4151 name_len)) 4152 { /* 'name' matches */ 4153 if (0 == memcmp (val, 4154 entry->value.cstr, 4155 val_len)) 4156 { /* 'value' matches */ 4157 /* Full match found, return the HPACK index */ 4158 return stbl_get_hpack_idx_from_pos (i); 4159 } 4160 } 4161 4162 4163 } while (0); 4164 } 4165 else 4166 { /* (0u == val_len) */ 4167 /* empty 'value' */ 4168 dtbl_idx_ft i; 4169 mhd_assert (0u == val_len); 4170 for (i = mhd_HPACK_STBL_NORM_START_POS; i < mhd_HPACK_STBL_ENTRIES; ++i) 4171 { 4172 const struct mhd_HpackStaticEntry *const entry = stbl_pos_entry_info (i); 4173 4174 if (mhd_HPACK_STBL_NORM_WITH_VALUE_POS == i) 4175 continue; 4176 4177 if (name_len != entry->name.len) 4178 continue; 4179 mhd_assert (0u != entry->name.len); 4180 mhd_assert (0u == entry->value.len); 4181 if (0 == memcmp (name, 4182 entry->name.cstr, 4183 name_len)) 4184 { /* 'name' matches (and 'value' is empty) */ 4185 /* Full match found, return the HPACK index */ 4186 return stbl_get_hpack_idx_from_pos (i); 4187 } 4188 } 4189 } 4190 #else /* ! MHD_FAVOR_SMALL_CODE */ 4191 if (1) 4192 { 4193 dtbl_idx_ft i; 4194 for (i = mhd_HPACK_STBL_NORM_START_POS; i < mhd_HPACK_STBL_ENTRIES; ++i) 4195 { 4196 const struct mhd_HpackStaticEntry *const entry = stbl_pos_entry_info (i); 4197 if (name_len != entry->name.len) 4198 continue; 4199 if (val_len != entry->value.len) 4200 continue; 4201 mhd_assert (0u != entry->name.len); 4202 if (0 == memcmp (name, 4203 entry->name.cstr, 4204 name_len)) 4205 { /* 'name' matches */ 4206 if ((0u == val_len) || 4207 (0 == memcmp (val, 4208 entry->value.cstr, 4209 val_len))) 4210 { /* 'value' matches (empty or identical) */ 4211 /* Full match found, return the HPACK index */ 4212 return stbl_get_hpack_idx_from_pos (i); 4213 } 4214 } 4215 } 4216 } 4217 #endif /* !MHD_FAVOR_SMALL_CODE */ 4218 4219 return 0u; /* Not found */ 4220 } 4221 4222 4223 /** 4224 * Find a static-table entry among "real" (non-pseudo) headers whose name 4225 * exactly matches @a name. 4226 * 4227 * The header name must not start with ':'. 4228 * The input string does not need to be zero-terminated. 4229 * 4230 * @param name_len length of @a name in bytes, 4231 * must NOT be zero 4232 * @param name pointer to the header field name, 4233 * does NOT need to be zero-terminated 4234 * @return the HPACK index (<= #mhd_HPACK_STBL_LAST_IDX) of the matching 4235 * static entry, or 0 if not found 4236 */ 4237 static MHD_FN_PAR_IN_SIZE_ (2,1) dtbl_idx_t 4238 mhd_stbl_find_name_real (size_t name_len, 4239 const char *restrict name) 4240 { 4241 dtbl_idx_ft i; 4242 #ifndef MHD_UNIT_TESTING /* Do not abort on a wrong name when unit-testing */ 4243 mhd_assert (0u != name_len); 4244 mhd_assert (':' != name[0]); 4245 #endif /* ! MHD_UNIT_TESTING */ 4246 for (i = mhd_HPACK_STBL_NORM_START_POS; i < mhd_HPACK_STBL_ENTRIES; ++i) 4247 { 4248 const struct mhd_HpackStaticEntry *const entry = stbl_pos_entry_info (i); 4249 4250 if (name_len != entry->name.len) 4251 continue; 4252 mhd_assert (0u != entry->name.len); 4253 if (0 == memcmp (name, 4254 entry->name.cstr, 4255 name_len)) 4256 { /* Found the entry, return the HPACK index */ 4257 return stbl_get_hpack_idx_from_pos (i); 4258 } 4259 } 4260 4261 return 0u; /* Not found */ 4262 } 4263 4264 4265 /* ****** -------------- HPACK header tables handling -------------- ****** */ 4266 /* 4267 * mhd_htbl_ functions are handling combination of HPACK static and dynamic 4268 * tables. 4269 * Functions need a pointer to a dynamic table instance. 4270 * 4271 * These functions are just convenient wrappers for some operations; they are 4272 * not designed to cover all operations with static and dynamic tables. 4273 * Some operations must be performed directly on static or dynamic tables. 4274 */ 4275 /** 4276 * Get a header-table entry (static or dynamic) by HPACK index. 4277 * 4278 * On success, @a name_out and @a value_out are set to point to the entry 4279 * data and their lengths. The returned buffers are not guaranteed to be 4280 * zero-terminated and must not be relied upon as C strings. 4281 * 4282 * @param dyn const pointer to the dynamic table context 4283 * @param idx the HPACK index (static or dynamic) 4284 * @param[out] name_out output buffer for the header name 4285 * @param[out] value_out output buffer for the header value 4286 * @return 'true' if the entry exists and outputs are set, 4287 * 'false' otherwise 4288 */ 4289 static MHD_FN_PAR_OUT_ (3) MHD_FN_PAR_OUT_ (4) bool 4290 mhd_htbl_get_entry (const struct mhd_HpackDTblContext *restrict dyn, 4291 dtbl_idx_ft idx, 4292 struct mhd_BufferConst *restrict name_out, 4293 struct mhd_BufferConst *restrict value_out) 4294 { 4295 if (mhd_COND_HARDLY_EVER (0u == idx)) 4296 return false; 4297 if (mhd_HPACK_STBL_LAST_IDX >= idx) 4298 { 4299 mhd_stbl_get_entry (idx, 4300 name_out, 4301 value_out); 4302 return true; 4303 } 4304 4305 return mhd_dtbl_get_entry (dyn, 4306 idx, 4307 name_out, 4308 value_out); 4309 } 4310 4311 4312 /** 4313 * Look up a header-table entry (static "real" headers first, then dynamic) 4314 * that exactly matches the given name and value. 4315 * 4316 * Pseudo-headers (names starting with ':') are not searched. The input 4317 * strings do not need to be zero-terminated. 4318 * 4319 * @param dyn const pointer to the dynamic table context 4320 * @param name_len length of @a name in bytes 4321 * @param name pointer to the header field name, must not start with ':', 4322 * does NOT need to be zero-terminated 4323 * @param val_len length of @a val in bytes 4324 * @param val pointer to the header field value, 4325 * does NOT need to be zero-terminated 4326 * @return the HPACK index of the matching entry (either static or dynamic), 4327 * or 0 if not found 4328 */ 4329 static MHD_FN_PAR_IN_SIZE_ (3,2) MHD_FN_PAR_IN_SIZE_ (5,4) dtbl_idx_t 4330 mhd_htbl_find_entry_real (const struct mhd_HpackDTblContext *restrict dyn, 4331 size_t name_len, 4332 const char *restrict name, 4333 size_t val_len, 4334 const char *restrict val) 4335 { 4336 dtbl_idx_ft idx; 4337 #ifndef MHD_UNIT_TESTING /* Do not abort on a wrong name when unit-testing */ 4338 mhd_assert ((0u == name_len) || (':' != name[0])); 4339 #endif /* ! MHD_UNIT_TESTING */ 4340 4341 if (0u != name_len) 4342 idx = mhd_stbl_find_entry_real (name_len, 4343 name, 4344 val_len, 4345 val); 4346 else 4347 idx = 0u; 4348 4349 if (0u == idx) 4350 idx = mhd_dtbl_find_entry (dyn, 4351 name_len, 4352 name, 4353 val_len, 4354 val); 4355 4356 return (dtbl_idx_t) idx; 4357 } 4358 4359 4360 /** 4361 * Look up a header-table entry (static "real" headers first, then dynamic) 4362 * whose name exactly matches @a name. 4363 * 4364 * Pseudo-headers (names starting with ':') are not searched. The input 4365 * string does not need to be zero-terminated. 4366 * 4367 * @param dyn const pointer to the dynamic table context 4368 * @param name_len length of @a name in bytes 4369 * @param name pointer to the header field name, must not start with ':', 4370 * does NOT need to be zero-terminated 4371 * @return the HPACK index of the matching entry (either static or dynamic), 4372 * or 0 if not found 4373 */ 4374 static MHD_FN_PAR_IN_SIZE_ (3,2) dtbl_idx_t 4375 mhd_htbl_find_name_real (const struct mhd_HpackDTblContext *restrict dyn, 4376 size_t name_len, 4377 const char *restrict name) 4378 { 4379 dtbl_idx_ft idx; 4380 #ifndef MHD_UNIT_TESTING /* Do not abort on a wrong name when unit-testing */ 4381 mhd_assert ((0u == name_len) || (':' != name[0])); 4382 #endif /* ! MHD_UNIT_TESTING */ 4383 4384 if (0u != name_len) 4385 idx = mhd_stbl_find_name_real (name_len, 4386 name); 4387 else 4388 idx = 0u; 4389 4390 if (0u == idx) 4391 idx = mhd_dtbl_find_name (dyn, 4392 name_len, 4393 name); 4394 4395 return (dtbl_idx_t) idx; 4396 } 4397 4398 4399 /* **** ___________ End of HPACK header tables handling ____________ ****** */ 4400 4401 /** 4402 * H2 HPACK default maximum size of the dynamic table 4403 */ 4404 mhd_constexpr size_t mhd_hpack_def_dyn_table_size = 4096u; 4405 4406 #if ! defined(mhd_HPACK_TESTING_TABLES_ONLY) || ! defined(MHD_UNIT_TESTING) 4407 4408 /** 4409 * Exactly eight bits all set (to one). 4410 */ 4411 mhd_constexpr uint8_t b8ones = 0xFFu; 4412 4413 /** 4414 * The maximum number of bytes allowed to encode numbers in HPACK. 4415 * 4416 * Current implementation supports only 32-bit numbers for strings and indices, 4417 * but extra zeros at the end of the encoded numbers can be safely processed. 4418 * This value limits the number of extra zero bytes at the end to a reasonable 4419 * value. It is enough to process the output of some weak encoder which may 4420 * encode numbers always as 64-bit-long values with some extra zero bytes at 4421 * the end of the encoded form. 4422 */ 4423 mhd_constexpr uint_fast8_t mhd_hpack_num_max_bytes = 12u; 4424 4425 /* ****** ----------------- HPACK headers decoding ----------------- ****** */ 4426 4427 /** 4428 * Result of hpack_dec_number() 4429 */ 4430 enum MHD_FIXED_ENUM_ mhd_HpackGetNumResult 4431 { 4432 mhd_HPACK_GET_NUM_RES_NO_ERROR, /**< Success */ 4433 mhd_HPACK_GET_NUM_RES_INCOMPLETE,/**< Not enough data in the input buffer */ 4434 mhd_HPACK_GET_NUM_RES_TOO_LARGE, /**< The decoded integer is too large for 32-bit */ 4435 mhd_HPACK_GET_NUM_RES_TOO_LONG /**< The tail of the encoded number has too many extra zero bytes */ 4436 }; 4437 4438 /** 4439 * Decode an HPACK integer number from the input buffer using a prefix in 4440 * the first byte. 4441 * @param first_byte_prefix_bits number of prefix bits in the first byte (1..7) 4442 * @param buf_size the size of @a buf 4443 * @param buf the input buffer 4444 * @param[out] num_out where to store the decoded value (fits into 32-bit range) 4445 * @param[out] bytes_decoded where to store the number of decoded bytes 4446 * @return #mhd_HPACK_GET_NUM_RES_NO_ERROR on success, 4447 * error code otherwise 4448 */ 4449 static MHD_FN_PAR_NONNULL_ALL_ 4450 MHD_FN_PAR_IN_SIZE_ (3,2) 4451 MHD_FN_PAR_OUT_ (4) MHD_FN_PAR_OUT_ (5) enum mhd_HpackGetNumResult 4452 hpack_dec_number (uint_fast8_t first_byte_prefix_bits, 4453 const size_t buf_size, 4454 const uint8_t buf[MHD_FN_PAR_DYN_ARR_SIZE_ (buf_size)], 4455 uint_fast32_t *restrict num_out, 4456 size_t *restrict bytes_decoded) 4457 { 4458 /** The maximum value of the first byte. Also the mask for the first byte. */ 4459 const uint_fast8_t first_byte_val_max = 4460 (uint_fast8_t) (b8ones >> first_byte_prefix_bits); 4461 uint_fast8_t first_byte; 4462 uint_fast32_t dec_num; 4463 uint_fast8_t i; 4464 4465 mhd_assert (0 != first_byte_prefix_bits); 4466 mhd_assert (8 > first_byte_prefix_bits); 4467 4468 first_byte = (buf[0] & first_byte_val_max); 4469 if (first_byte_val_max != first_byte) 4470 { 4471 *num_out = (uint_fast32_t) first_byte; 4472 *bytes_decoded = 1u; 4473 return mhd_HPACK_GET_NUM_RES_NO_ERROR; /* Success exit point */ 4474 } 4475 dec_num = first_byte; 4476 4477 #ifndef MHD_FAVOR_SMALL_CODE 4478 /* Unrolled loop */ 4479 i = 1u; 4480 if (buf_size == i) 4481 return mhd_HPACK_GET_NUM_RES_INCOMPLETE; /* Failure exit point */ 4482 else 4483 { 4484 const uint_fast8_t cur_byte = buf[i]; 4485 const bool is_final = (0u == (cur_byte & 0x80u)); 4486 const uint_fast8_t byte_val = (uint_fast8_t) (cur_byte & 0x7Fu); 4487 dec_num += (uint_fast32_t) (((uint_fast32_t) byte_val) << (7u * (i - 1u))); 4488 if (is_final) 4489 { 4490 *num_out = dec_num; 4491 *bytes_decoded = (size_t) (i + 1u); 4492 return mhd_HPACK_GET_NUM_RES_NO_ERROR; /* Success exit point */ 4493 } 4494 } 4495 4496 i = 2u; 4497 if (buf_size == i) 4498 return mhd_HPACK_GET_NUM_RES_INCOMPLETE; /* Failure exit point */ 4499 else 4500 { 4501 const uint_fast8_t cur_byte = buf[i]; 4502 const bool is_final = (0u == (cur_byte & 0x80u)); 4503 const uint_fast8_t byte_val = (uint_fast8_t) (cur_byte & 0x7Fu); 4504 dec_num += (uint_fast32_t) (((uint_fast32_t) byte_val) << (7u * (i - 1u))); 4505 if (is_final) 4506 { 4507 *num_out = dec_num; 4508 *bytes_decoded = (size_t) (i + 1u); 4509 return mhd_HPACK_GET_NUM_RES_NO_ERROR; /* Success exit point */ 4510 } 4511 } 4512 4513 i = 3u; 4514 if (buf_size == i) 4515 return mhd_HPACK_GET_NUM_RES_INCOMPLETE; /* Failure exit point */ 4516 else 4517 { 4518 const uint_fast8_t cur_byte = buf[i]; 4519 const bool is_final = (0u == (cur_byte & 0x80u)); 4520 const uint_fast8_t byte_val = (uint_fast8_t) (cur_byte & 0x7Fu); 4521 dec_num += (uint_fast32_t) (((uint_fast32_t) byte_val) << (7u * (i - 1u))); 4522 if (is_final) 4523 { 4524 *num_out = dec_num; 4525 *bytes_decoded = (size_t) (i + 1u); 4526 return mhd_HPACK_GET_NUM_RES_NO_ERROR; /* Success exit point */ 4527 } 4528 } 4529 4530 i = 4u; 4531 if (buf_size == i) 4532 return mhd_HPACK_GET_NUM_RES_INCOMPLETE; /* Failure exit point */ 4533 else 4534 { 4535 const uint_fast8_t cur_byte = buf[i]; 4536 const bool is_final = (0u == (cur_byte & 0x80u)); 4537 const uint_fast8_t byte_val = (uint_fast8_t) (cur_byte & 0x7Fu); 4538 dec_num += (uint_fast32_t) (((uint_fast32_t) byte_val) << (7u * (i - 1u))); 4539 if (is_final) 4540 { 4541 *num_out = dec_num; 4542 *bytes_decoded = (size_t) (i + 1u); 4543 return mhd_HPACK_GET_NUM_RES_NO_ERROR; /* Success exit point */ 4544 } 4545 } 4546 4547 i = 5u; 4548 #else /* MHD_FAVOR_SMALL_CODE */ 4549 /* First four bytes cannot overflow the output */ 4550 for (i = 1u; 4u >= i; ++i) 4551 { 4552 if (buf_size == i) 4553 return mhd_HPACK_GET_NUM_RES_INCOMPLETE; /* Failure exit point */ 4554 else 4555 { 4556 const uint_fast8_t cur_byte = buf[i]; 4557 const bool is_final = (0u == (cur_byte & 0x80u)); 4558 const uint_fast8_t byte_val = (uint_fast8_t) (cur_byte & 0x7Fu); 4559 dec_num += (uint_fast32_t) (((uint_fast32_t) byte_val) << (7u * (i - 1u))) 4560 ; 4561 if (is_final) 4562 { 4563 *num_out = dec_num; 4564 *bytes_decoded = (size_t) (i + 1u); 4565 return mhd_HPACK_GET_NUM_RES_NO_ERROR; /* Success exit point */ 4566 } 4567 } 4568 } 4569 #endif /* MHD_FAVOR_SMALL_CODE */ 4570 4571 mhd_assert (0u == (dec_num >> 29u)); 4572 mhd_assert (5u == i); 4573 if (buf_size == i) 4574 return mhd_HPACK_GET_NUM_RES_INCOMPLETE; /* Failure exit point */ 4575 else 4576 { /* Handle the fifth byte with overflow checks */ 4577 const uint_fast8_t cur_byte = buf[i]; 4578 const bool is_final = (0u == (cur_byte & 0x80u)); 4579 const uint_fast8_t byte_val = (uint_fast8_t) (cur_byte & 0x7Fu); 4580 const uint_fast32_t add_val = 4581 (uint_fast32_t) (((uint_fast32_t) byte_val) << (7u * (i - 1u))); 4582 if (byte_val != ((add_val & 0xFFFFFFFFu) >> (7u * (i - 1u)))) 4583 return mhd_HPACK_GET_NUM_RES_TOO_LARGE; /* Failure exit point */ 4584 dec_num += add_val; 4585 if ((dec_num & 0xFFFFFFFFu) < add_val) 4586 return mhd_HPACK_GET_NUM_RES_TOO_LARGE; /* Failure exit point */ 4587 else if (is_final) 4588 { 4589 *num_out = dec_num; 4590 *bytes_decoded = (size_t) (i + 1u); 4591 return mhd_HPACK_GET_NUM_RES_NO_ERROR; /* Success exit point */ 4592 } 4593 } 4594 4595 /* Process possible extra zero-valued tail bytes */ 4596 while (++i <= mhd_hpack_num_max_bytes) 4597 { 4598 if (buf_size == i) 4599 return mhd_HPACK_GET_NUM_RES_INCOMPLETE; /* Failure exit point */ 4600 else 4601 { 4602 const uint_fast8_t cur_byte = buf[i]; 4603 const bool is_final = (0u == (cur_byte & 0x80u)); 4604 const uint_fast8_t byte_val = (uint_fast8_t) (cur_byte & 0x7Fu); 4605 if (0u != byte_val) 4606 return mhd_HPACK_GET_NUM_RES_TOO_LARGE; /* Failure exit point */ 4607 else if (is_final) 4608 { 4609 *num_out = dec_num; 4610 *bytes_decoded = (size_t) (i + 1u); 4611 return mhd_HPACK_GET_NUM_RES_NO_ERROR; /* Success exit point */ 4612 } 4613 } 4614 } 4615 4616 return mhd_HPACK_GET_NUM_RES_TOO_LONG; /* Failure exit point */ 4617 } 4618 4619 4620 MHD_INTERNAL MHD_FN_PAR_NONNULL_ALL_ 4621 MHD_FN_PAR_OUT_ (1) bool 4622 mhd_hpack_dec_init (struct mhd_HpackDecContext *hk_dec) 4623 { 4624 hk_dec->dyn = mhd_dtbl_create (mhd_hpack_def_dyn_table_size); 4625 4626 if (NULL == hk_dec->dyn) 4627 return false; /* Failure exit point */ 4628 4629 mhd_assert (mhd_hpack_def_dyn_table_size == \ 4630 mhd_dtbl_get_table_max_size (hk_dec->dyn)); 4631 4632 hk_dec->max_allowed_dyn_size = mhd_hpack_def_dyn_table_size; 4633 hk_dec->last_remote_dyn_size = hk_dec->max_allowed_dyn_size; 4634 4635 return true; /* Success exit point */ 4636 } 4637 4638 4639 MHD_INTERNAL MHD_FN_PAR_NONNULL_ALL_ 4640 MHD_FN_PAR_INOUT_ (1) void 4641 mhd_hpack_dec_deinit (struct mhd_HpackDecContext *hk_dec) 4642 { 4643 if (NULL == hk_dec->dyn) 4644 return; /* Nothing to de-initialise */ 4645 4646 mhd_dtbl_destroy (hk_dec->dyn); 4647 hk_dec->dyn = NULL; 4648 } 4649 4650 4651 MHD_INTERNAL MHD_FN_PAR_NONNULL_ALL_ 4652 MHD_FN_PAR_INOUT_ (1) void 4653 mhd_hpack_dec_set_allowed_dyn_size (struct mhd_HpackDecContext *hk_dec, 4654 size_t new_allowed_dyn_size) 4655 { 4656 mhd_assert (mhd_DTBL_MAX_SIZE >= new_allowed_dyn_size); 4657 hk_dec->max_allowed_dyn_size = new_allowed_dyn_size; 4658 } 4659 4660 4661 /** 4662 * Ensure that any pending dynamic table resize is applied before decoding 4663 * fields. 4664 * Also check for possible missing Dynamic Table Size Update messages (after 4665 * reception of ACK for settings reducing the maximum table size). 4666 * @param hk_dec pointer to the decoder context 4667 * @return non-error decoder result on success; 4668 * an error code if resize is disallowed or memory allocation fails 4669 */ 4670 static enum mhd_HpackDecResult 4671 dec_check_resize_pending (struct mhd_HpackDecContext *restrict hk_dec) 4672 { 4673 mhd_assert (mhd_DTBL_MAX_SIZE >= hk_dec->last_remote_dyn_size); 4674 if (hk_dec->max_allowed_dyn_size < hk_dec->last_remote_dyn_size) 4675 return mhd_HPACK_DEC_RES_DYN_SIZE_UPD_MISSING; /* Failure exit point */ 4676 4677 if (mhd_dtbl_get_table_max_size (hk_dec->dyn) != hk_dec->last_remote_dyn_size) 4678 { 4679 /* Resize must be performed before processing any headers data */ 4680 if (! mhd_dtbl_resize (&(hk_dec->dyn), 4681 hk_dec->last_remote_dyn_size)) 4682 return mhd_HPACK_DEC_RES_ALLOC_ERR; /* Failure exit point */ 4683 } 4684 4685 mhd_assert (mhd_dtbl_get_table_max_size (hk_dec->dyn) \ 4686 == hk_dec->last_remote_dyn_size); 4687 return mhd_HPACK_DEC_RES_NEW_FIELD; /* Success, return any non-error code */ 4688 } 4689 4690 4691 /** 4692 * Decode an indexed header field and write "name\0value\0" to @a out_buff. 4693 * @param hk_dec the decoder context 4694 * @param enc_data_size the size of @a enc_data 4695 * @param enc_data the encoded data 4696 * @param out_buff_size the size of @a out_buff 4697 * @param[out] out_buff the output buffer for "name\0value\0" 4698 * @param[out] name_len set to the length of the name, not counting 4699 * terminating zero 4700 * @param[out] val_len set to the length of the value, not counting 4701 * terminating zero 4702 * @param[out] bytes_decoded set to the number of decoded bytes 4703 * @return #mhd_HPACK_DEC_RES_NEW_FIELD on success or an error code 4704 */ 4705 static MHD_FN_PAR_NONNULL_ALL_ 4706 MHD_FN_PAR_IN_SIZE_ (3,2) MHD_FN_PAR_OUT_SIZE_ (5,4) 4707 MHD_FN_PAR_OUT_ (6) MHD_FN_PAR_OUT_ (7) 4708 MHD_FN_PAR_OUT_ (8) enum mhd_HpackDecResult 4709 hpack_dec_field_indexed (struct mhd_HpackDecContext *restrict hk_dec, 4710 size_t enc_data_size, 4711 const uint8_t *restrict enc_data, 4712 size_t out_buff_size, 4713 char *restrict out_buff, 4714 size_t *restrict name_len, 4715 size_t *restrict val_len, 4716 size_t *restrict bytes_decoded) 4717 { 4718 enum mhd_HpackDecResult res; 4719 enum mhd_HpackGetNumResult dec_res; 4720 size_t idx_enc_len; 4721 uint_fast32_t field_idx; 4722 struct mhd_BufferConst idx_name; 4723 struct mhd_BufferConst idx_value; 4724 4725 mhd_assert (1u == (enc_data[0] >> 7u)); 4726 mhd_assert (0u != out_buff_size); 4727 4728 /* If any dynamic table resize is pending, it must be performed before 4729 header strings processing. */ 4730 res = dec_check_resize_pending (hk_dec); 4731 if (mhd_HPACK_DEC_RES_IS_ERR (res)) 4732 return res; 4733 4734 dec_res = hpack_dec_number (1u, 4735 enc_data_size, 4736 enc_data, 4737 &field_idx, 4738 &idx_enc_len); 4739 switch (dec_res) 4740 { 4741 case mhd_HPACK_GET_NUM_RES_INCOMPLETE: 4742 return mhd_HPACK_DEC_RES_INCOMPLETE; /* Failure exit point */ 4743 case mhd_HPACK_GET_NUM_RES_TOO_LARGE: 4744 return mhd_HPACK_DEC_RES_HPACK_BAD_IDX; /* Failure exit point */ 4745 case mhd_HPACK_GET_NUM_RES_TOO_LONG: 4746 return mhd_HPACK_DEC_RES_NUMBER_TOO_LONG; /* Failure exit point */ 4747 case mhd_HPACK_GET_NUM_RES_NO_ERROR: 4748 break; 4749 default: 4750 mhd_UNREACHABLE (); 4751 return mhd_HPACK_DEC_RES_INTERNAL_ERR; /* Failure exit point */ 4752 } 4753 4754 mhd_assert (0u != idx_enc_len); 4755 4756 if (mhd_COND_HARDLY_EVER (mhd_HPACK_MAX_POSSIBLE_IDX < field_idx)) 4757 return mhd_HPACK_DEC_RES_HPACK_BAD_IDX; /* Failure exit point */ 4758 4759 if (! mhd_htbl_get_entry (hk_dec->dyn, 4760 (dtbl_idx_ft) field_idx, 4761 &idx_name, 4762 &idx_value)) 4763 return mhd_HPACK_DEC_RES_HPACK_BAD_IDX; /* Failure exit point */ 4764 4765 /* No math overflow check is needed here as both strings are already stored 4766 in memory together with pointers. */ 4767 if (out_buff_size < (idx_name.size + idx_value.size + 2u)) 4768 return mhd_HPACK_DEC_RES_BUFFER_TOO_SMALL; /* Failure exit point */ 4769 4770 memcpy (out_buff, 4771 idx_name.data, 4772 idx_name.size); 4773 out_buff[idx_name.size] = '\0'; /* Zero-terminate field name */ 4774 4775 memcpy (out_buff + idx_name.size + 1u, 4776 idx_value.data, 4777 idx_value.size); 4778 out_buff[idx_name.size + 1u + idx_value.size] = '\0'; /* Zero-terminate field value */ 4779 4780 *name_len = idx_name.size; 4781 *val_len = idx_value.size; 4782 *bytes_decoded = idx_enc_len; 4783 4784 return mhd_HPACK_DEC_RES_NEW_FIELD; 4785 } 4786 4787 4788 /** 4789 * Decode an HPACK string literal (with or without Huffman coding). 4790 * The output string in @a out_buff is zero-terminated. 4791 * @param enc_data_size the size of @a enc_data 4792 * @param enc_data the pointer to the encoded data 4793 * @param out_buff_size the size of @a out_buff 4794 * @param[out] out_buff the output buffer for the decoded string, 4795 * the output is zero-terminated 4796 * @param[out] out_len set to the decoded string length, 4797 * not counting zero-termination 4798 * @param[out] bytes_decoded set to the number of decoded bytes 4799 * @return #mhd_HPACK_DEC_RES_NEW_FIELD on success, 4800 * error code otherwise 4801 */ 4802 static MHD_FN_PAR_NONNULL_ALL_ 4803 MHD_FN_PAR_IN_SIZE_ (2,1) MHD_FN_PAR_OUT_SIZE_ (4,3) 4804 MHD_FN_PAR_OUT_ (5) MHD_FN_PAR_OUT_ (6) enum mhd_HpackDecResult 4805 hpack_dec_string_literal (size_t enc_data_size, 4806 const uint8_t *restrict enc_data, 4807 size_t out_buff_size, 4808 char *restrict out_buff, 4809 size_t *restrict out_len, 4810 size_t *restrict bytes_decoded) 4811 { 4812 const bool is_huff_enc = (0u != (enc_data[0] & 0x80u)); 4813 uint_fast32_t enc_str_len; 4814 enum mhd_HpackGetNumResult dec_res; 4815 size_t enc_num_len; 4816 size_t dec_str_len; 4817 4818 mhd_assert (0u != enc_data_size); 4819 mhd_assert (0u != out_buff_size); 4820 4821 dec_res = hpack_dec_number (1u, 4822 enc_data_size, 4823 enc_data, 4824 &enc_str_len, 4825 &enc_num_len); 4826 switch (dec_res) 4827 { 4828 case mhd_HPACK_GET_NUM_RES_INCOMPLETE: 4829 return mhd_HPACK_DEC_RES_INCOMPLETE;/* Failure exit point */ 4830 case mhd_HPACK_GET_NUM_RES_TOO_LARGE: 4831 return mhd_HPACK_DEC_RES_STRING_TOO_LONG; /* Failure exit point */ 4832 case mhd_HPACK_GET_NUM_RES_TOO_LONG: 4833 return mhd_HPACK_DEC_RES_NUMBER_TOO_LONG; /* Failure exit point */ 4834 case mhd_HPACK_GET_NUM_RES_NO_ERROR: 4835 break; 4836 default: 4837 mhd_UNREACHABLE (); 4838 return mhd_HPACK_DEC_RES_INTERNAL_ERR; /* Failure exit point */ 4839 } 4840 4841 mhd_assert (0u != enc_num_len); 4842 mhd_assert (enc_num_len <= enc_data_size); 4843 4844 if ((enc_data_size - enc_num_len) < enc_str_len) 4845 return mhd_HPACK_DEC_RES_INCOMPLETE; /* Failure exit point */ 4846 4847 if (mhd_COND_HARDLY_EVER (0u == enc_str_len)) 4848 dec_str_len = 0; /* Zero length string, can be Huffman-encoded or not */ 4849 else if (is_huff_enc) 4850 { /* String with Huffman encoding */ 4851 enum mhd_H2HuffDecodeRes huff_dec_res; 4852 4853 /* mhd_h2_huffman_decode() will check whether the output buffer is large 4854 enough. */ 4855 dec_str_len = mhd_h2_huffman_decode ((size_t) enc_str_len, 4856 enc_data + enc_num_len, 4857 out_buff_size - 1u, /* leave one byte for zero-termination */ 4858 out_buff, 4859 &huff_dec_res); 4860 switch (huff_dec_res) 4861 { 4862 case MHD_H2_HUFF_DEC_RES_NO_SPACE: 4863 return mhd_HPACK_DEC_RES_BUFFER_TOO_SMALL; /* Failure exit point */ 4864 case MHD_H2_HUFF_DEC_RES_BROKEN_DATA: 4865 return mhd_HPACK_DEC_RES_HUFFMAN_ERR; /* Failure exit point */ 4866 break; 4867 case MHD_H2_HUFF_DEC_RES_OK: 4868 break; 4869 default: 4870 mhd_UNREACHABLE (); 4871 return mhd_HPACK_DEC_RES_INTERNAL_ERR; /* Failure exit point */ 4872 } 4873 mhd_assert (0u != dec_str_len); 4874 mhd_assert (MHD_H2_HUFF_DEC_RES_OK == huff_dec_res); 4875 mhd_assert (dec_str_len < out_buff_size); 4876 } 4877 else 4878 { /* String without Huffman encoding */ 4879 if (out_buff_size <= enc_str_len) /* leave one byte for zero-termination */ 4880 return mhd_HPACK_DEC_RES_BUFFER_TOO_SMALL; /* Failure exit point */ 4881 4882 dec_str_len = (size_t) enc_str_len; 4883 memcpy (out_buff, 4884 enc_data + enc_num_len, 4885 dec_str_len); 4886 } 4887 4888 mhd_assert (out_buff_size > dec_str_len); 4889 4890 out_buff[dec_str_len] = '\0'; /* Zero-terminate the result */ 4891 *out_len = dec_str_len; 4892 *bytes_decoded = enc_num_len + (size_t) enc_str_len; 4893 return mhd_HPACK_DEC_RES_NEW_FIELD; /* Return any non-error code */ 4894 } 4895 4896 4897 /** 4898 * Decode a literal header field (with or without indexing) and write 4899 * "name\0value\0" to the output buffer @a out_buff. 4900 * If @a with_indexing is 'true', the decoded field is inserted into the 4901 * dynamic table. 4902 * @param hk_dec the decoder context 4903 * @param enc_data_size the size of @a enc_data 4904 * @param enc_data the encoded data 4905 * @param out_buff_size the size of @a out_buff 4906 * @param with_indexing non-zero to insert the field into the dynamic table 4907 * @param[out] out_buff output the buffer for the decoded strings 4908 * @param[out] name_len set to the length of the name, not counting 4909 * zero-terminating 4910 * @param[out] val_len set to the length of the value, not counting 4911 * zero-terminating 4912 * @param[out] bytes_decoded set to the number of decoded bytes 4913 * @return #mhd_HPACK_DEC_RES_NEW_FIELD on success, 4914 * error code otherwise 4915 */ 4916 static MHD_FN_PAR_NONNULL_ALL_ 4917 MHD_FN_PAR_IN_SIZE_ (3,2) MHD_FN_PAR_OUT_SIZE_ (6,5) 4918 MHD_FN_PAR_OUT_ (7) MHD_FN_PAR_OUT_ (8) 4919 MHD_FN_PAR_OUT_ (9) enum mhd_HpackDecResult 4920 hpack_dec_field_literal (struct mhd_HpackDecContext *restrict hk_dec, 4921 size_t enc_data_size, 4922 const uint8_t *restrict enc_data, 4923 bool with_indexing, 4924 size_t out_buff_size, 4925 char *restrict out_buff, 4926 size_t *restrict name_len, 4927 size_t *restrict val_len, 4928 size_t *restrict bytes_decoded) 4929 { 4930 const uint_fast8_t prfx_bits = (with_indexing ? 2u : 4u); 4931 enum mhd_HpackDecResult res; 4932 size_t pos; 4933 size_t pos_incr; 4934 uint_fast32_t name_idx; 4935 4936 mhd_assert (with_indexing || \ 4937 (1u == (enc_data[0] >> 4u)) || (0u == (enc_data[0] >> 4u))); 4938 mhd_assert (! with_indexing || \ 4939 (1u == (enc_data[0] >> 6u))); 4940 mhd_assert (0u != enc_data_size); 4941 mhd_assert (2u <= out_buff_size); 4942 4943 /* If any dynamic table resize is pending, it must be performed before 4944 headers strings processing. */ 4945 res = dec_check_resize_pending (hk_dec); 4946 if (mhd_HPACK_DEC_RES_IS_ERR (res)) 4947 return res; 4948 4949 pos = 0u; 4950 #ifndef MHD_FAVOR_SMALL_CODE 4951 if (0u == (enc_data[0] & (b8ones >> prfx_bits))) 4952 { 4953 name_idx = 0u; /* Shortcut for frequent case */ 4954 pos_incr = 1u; 4955 } 4956 else 4957 #endif /* ! MHD_FAVOR_SMALL_CODE */ 4958 if (1) 4959 { 4960 enum mhd_HpackGetNumResult dec_res; 4961 dec_res = hpack_dec_number (prfx_bits, 4962 enc_data_size, 4963 enc_data, 4964 &name_idx, 4965 &pos_incr); 4966 switch (dec_res) 4967 { 4968 case mhd_HPACK_GET_NUM_RES_INCOMPLETE: 4969 return mhd_HPACK_DEC_RES_INCOMPLETE; /* Failure exit point */ 4970 case mhd_HPACK_GET_NUM_RES_TOO_LARGE: 4971 return mhd_HPACK_DEC_RES_HPACK_BAD_IDX; /* Failure exit point */ 4972 case mhd_HPACK_GET_NUM_RES_TOO_LONG: 4973 return mhd_HPACK_DEC_RES_NUMBER_TOO_LONG; /* Failure exit point */ 4974 case mhd_HPACK_GET_NUM_RES_NO_ERROR: 4975 break; 4976 default: 4977 mhd_UNREACHABLE (); 4978 return mhd_HPACK_DEC_RES_INTERNAL_ERR; /* Failure exit point */ 4979 } 4980 4981 mhd_assert (0u != pos_incr); 4982 #ifndef MHD_FAVOR_SMALL_CODE 4983 mhd_assert (0u != name_idx); 4984 #endif /* ! MHD_FAVOR_SMALL_CODE */ 4985 } 4986 4987 pos += pos_incr; 4988 mhd_assert (0u != pos); 4989 4990 if (enc_data_size == pos) 4991 return mhd_HPACK_DEC_RES_INCOMPLETE; /* Failure exit point */ 4992 4993 if (0u == name_idx) 4994 { /* Literal name */ 4995 mhd_assert (1u == pos); 4996 pos = 1u; /* Help compiler to optimise */ 4997 4998 res = hpack_dec_string_literal (enc_data_size - pos, 4999 enc_data + pos, 5000 out_buff_size - 1u, /* At least one char for the value string */ 5001 out_buff, 5002 name_len, 5003 &pos_incr); 5004 if (mhd_HPACK_DEC_RES_IS_ERR (res)) 5005 return res; /* Failure exit point */ 5006 } 5007 else 5008 { /* Indexed name */ 5009 struct mhd_BufferConst idx_name; 5010 struct mhd_BufferConst idx_value; /* extracted value is unused */ 5011 5012 if (mhd_COND_HARDLY_EVER (mhd_HPACK_MAX_POSSIBLE_IDX < name_idx)) 5013 return mhd_HPACK_DEC_RES_HPACK_BAD_IDX; /* Failure exit point */ 5014 5015 if (! mhd_htbl_get_entry (hk_dec->dyn, 5016 (dtbl_idx_ft) name_idx, 5017 &idx_name, 5018 &idx_value)) 5019 return mhd_HPACK_DEC_RES_HPACK_BAD_IDX; /* Failure exit point */ 5020 5021 if (idx_name.size >= (out_buff_size - 1u)) 5022 return mhd_HPACK_DEC_RES_BUFFER_TOO_SMALL; /* Failure exit point */ 5023 5024 memcpy (out_buff, 5025 idx_name.data, 5026 idx_name.size); 5027 out_buff[idx_name.size] = '\0'; /* Zero-terminate resulting string */ 5028 *name_len = idx_name.size; 5029 5030 pos_incr = 0u; 5031 } 5032 pos += pos_incr; 5033 5034 if (enc_data_size == pos) 5035 return mhd_HPACK_DEC_RES_INCOMPLETE; /* Failure exit point */ 5036 5037 mhd_assert (out_buff_size >= (*name_len + 2u)); 5038 res = hpack_dec_string_literal (enc_data_size - pos, 5039 enc_data + pos, 5040 out_buff_size - (*name_len + 1u), 5041 out_buff + (*name_len + 1u), 5042 val_len, 5043 &pos_incr); 5044 if (mhd_HPACK_DEC_RES_IS_ERR (res)) 5045 return res; /* Failure exit point */ 5046 5047 pos += pos_incr; 5048 *bytes_decoded = pos; 5049 5050 if (with_indexing) 5051 mhd_dtbl_new_entry (hk_dec->dyn, 5052 *name_len, 5053 out_buff, 5054 *val_len, 5055 out_buff + (*name_len) + 1u); 5056 5057 return mhd_HPACK_DEC_RES_NEW_FIELD; 5058 } 5059 5060 5061 /** 5062 * Decode and apply a Dynamic Table Size Update. 5063 * Performs eviction only; actual resize is deferred until before first header 5064 * decoding. 5065 * @param hk_dec the decoder context 5066 * @param enc_data_size the size of @a enc_data 5067 * @param enc_data the encoded data 5068 * @param[out] bytes_decoded set to the number of decoded bytes 5069 * @return #mhd_HPACK_DEC_RES_NO_NEW_FIELD on success, 5070 * error code otherwise 5071 */ 5072 static MHD_FN_PAR_IN_SIZE_ (3,2) 5073 MHD_FN_PAR_OUT_ (4) enum mhd_HpackDecResult 5074 dec_update_dyn_size (struct mhd_HpackDecContext *restrict hk_dec, 5075 const size_t enc_data_size, 5076 const uint8_t *restrict enc_data, 5077 size_t *restrict bytes_decoded) 5078 { 5079 uint_fast32_t new_dyn_size; 5080 size_t used_bytes; 5081 enum mhd_HpackGetNumResult dec_res; 5082 5083 mhd_assert ((1u == (enc_data[0] >> 5u)) && \ 5084 "the first byte must be the dynamic table update signal"); 5085 dec_res = hpack_dec_number (3u, 5086 enc_data_size, 5087 enc_data, 5088 &new_dyn_size, 5089 &used_bytes); 5090 switch (dec_res) 5091 { 5092 case mhd_HPACK_GET_NUM_RES_INCOMPLETE: 5093 return mhd_HPACK_DEC_RES_INCOMPLETE; /* Failure exit point */ 5094 case mhd_HPACK_GET_NUM_RES_TOO_LARGE: 5095 return mhd_HPACK_DEC_RES_DYN_SIZE_UPD_TOO_LARGE; /* Failure exit point */ 5096 case mhd_HPACK_GET_NUM_RES_TOO_LONG: 5097 return mhd_HPACK_DEC_RES_NUMBER_TOO_LONG; /* Failure exit point */ 5098 case mhd_HPACK_GET_NUM_RES_NO_ERROR: 5099 break; 5100 default: 5101 mhd_UNREACHABLE (); 5102 return mhd_HPACK_DEC_RES_INTERNAL_ERR; /* Failure exit point */ 5103 } 5104 mhd_assert (0u != used_bytes); 5105 5106 if (hk_dec->max_allowed_dyn_size < new_dyn_size) 5107 return mhd_HPACK_DEC_RES_DYN_SIZE_UPD_TOO_LARGE; /* Failure exit point */ 5108 5109 mhd_assert (mhd_DTBL_MAX_SIZE >= new_dyn_size); 5110 5111 /* Only evict here, no resize yet to avoid repetitive realloc() calls if 5112 remote sends multiple table size updates in a row. */ 5113 mhd_dtbl_evict_to_size (hk_dec->dyn, 5114 (size_t) new_dyn_size); 5115 5116 hk_dec->last_remote_dyn_size = (size_t) new_dyn_size; 5117 5118 *bytes_decoded = used_bytes; 5119 return mhd_HPACK_DEC_RES_NO_NEW_FIELD; /* Success exit point */ 5120 } 5121 5122 5123 MHD_INTERNAL MHD_FN_PAR_NONNULL_ALL_ 5124 MHD_FN_PAR_INOUT_ (1) 5125 MHD_FN_PAR_IN_SIZE_ (3, 2) 5126 MHD_FN_PAR_OUT_SIZE_ (5, 4) 5127 MHD_FN_PAR_OUT_ (6) MHD_FN_PAR_OUT_ (7) 5128 MHD_FN_PAR_OUT_ (8) enum mhd_HpackDecResult 5129 mhd_hpack_dec_data (struct mhd_HpackDecContext *restrict hk_dec, 5130 size_t enc_data_size, 5131 const uint8_t *restrict enc_data, 5132 size_t out_buff_size, 5133 char *restrict out_buff, 5134 size_t *restrict name_len, 5135 size_t *restrict val_len, 5136 size_t *restrict bytes_decoded) 5137 { 5138 uint_fast8_t action_id; 5139 5140 mhd_assert (0u != enc_data_size); 5141 mhd_assert (2u <= out_buff_size); 5142 5143 action_id = enc_data[0] >> 4u; 5144 5145 switch (action_id) 5146 { 5147 case (1u << 3u) + 0u: 5148 case (1u << 3u) + 1u: 5149 case (1u << 3u) + 2u: 5150 case (1u << 3u) + 3u: 5151 case (1u << 3u) + 4u: 5152 case (1u << 3u) + 5u: 5153 case (1u << 3u) + 6u: 5154 case (1u << 3u) + 7u: 5155 /* Indexed field */ 5156 return hpack_dec_field_indexed (hk_dec, 5157 enc_data_size, 5158 enc_data, 5159 out_buff_size, 5160 out_buff, 5161 name_len, 5162 val_len, 5163 bytes_decoded); 5164 case (1u << 2u) + 0u: 5165 case (1u << 2u) + 1u: 5166 case (1u << 2u) + 2u: 5167 case (1u << 2u) + 3u: 5168 /* Literal field with indexing */ 5169 return hpack_dec_field_literal (hk_dec, 5170 enc_data_size, 5171 enc_data, 5172 true, 5173 out_buff_size, 5174 out_buff, 5175 name_len, 5176 val_len, 5177 bytes_decoded); 5178 case 0u << 0u: 5179 /* Literal field without indexing */ 5180 return hpack_dec_field_literal (hk_dec, 5181 enc_data_size, 5182 enc_data, 5183 false, 5184 out_buff_size, 5185 out_buff, 5186 name_len, 5187 val_len, 5188 bytes_decoded); 5189 case 1u << 0u: 5190 /* Literal field never indexed */ 5191 return hpack_dec_field_literal (hk_dec, 5192 enc_data_size, 5193 enc_data, 5194 false, 5195 out_buff_size, 5196 out_buff, 5197 name_len, 5198 val_len, 5199 bytes_decoded); 5200 case (1u << 1u) + 0u: 5201 case (1u << 1u) + 1u: 5202 /* Dynamic table size update */ 5203 return dec_update_dyn_size (hk_dec, 5204 enc_data_size, 5205 enc_data, 5206 bytes_decoded); 5207 default: 5208 break; 5209 } 5210 mhd_UNREACHABLE (); 5211 return mhd_HPACK_DEC_RES_INTERNAL_ERR; 5212 } 5213 5214 5215 /* ****** _____________ End of HPACK headers decoding ______________ ****** */ 5216 5217 /* ****** ----------------- HPACK headers encoding ----------------- ****** */ 5218 5219 /** 5220 * Compute the number of bytes required to encode an HPACK integer. 5221 * 5222 * Implements the integer encoding algorithm from RFC 7541, Section 5.1. 5223 * The @a prefix_bits parameter specifies the count of fixed most-significant 5224 * bits in the first byte (e.g., 1 for "1xxxxxxx", 2 for "01xxxxxx", 5225 * 3 for "001xxxxx", 4 for "0000xxxx"/"0001xxxx"). 5226 * The number of value bits available in the first byte is (8 - @a prefix_bits). 5227 * 5228 * @param[in] prefix_bits the count of fixed high-order bits in the first byte; 5229 * must be greater than zero and less than 8 5230 * @param[in] number the value to encode, must fit 32 bits 5231 * @return the total number of bytes needed (always non-zero) 5232 */ 5233 static size_t 5234 hpack_number_len (uint_fast8_t prefix_bits, 5235 uint_fast32_t number) 5236 { 5237 const uint_fast8_t first_byte_val_max = 5238 (uint_fast8_t) (b8ones >> prefix_bits); 5239 uint_least32_t val_for_next_bytes; 5240 5241 mhd_assert (0u != prefix_bits); 5242 mhd_assert (8u > prefix_bits); 5243 mhd_assert ((number & 0xFFFFFFFFu) == number); 5244 5245 if (first_byte_val_max > number) /* the number must be strictly less than */ 5246 return 1u; 5247 val_for_next_bytes = (uint_least32_t) (number - first_byte_val_max); 5248 if (0 == val_for_next_bytes) 5249 return 2u; 5250 return (uint_fast8_t) \ 5251 ((mhd_BIT_WIDTH32NZ (val_for_next_bytes) + 6u) / 7u) + 1u; 5252 } 5253 5254 5255 /** 5256 * Encode an HPACK integer into the provided output buffer. 5257 * 5258 * Encodes @a number according to RFC 7541, Section 5.1 using the given 5259 * first-byte prefix. The @a first_byte_prefix must have its lowest 5260 * (8 - @a first_byte_prefix_bits) bits cleared; these bits will be filled 5261 * with the encoded value. 5262 * 5263 * @param[in] first_byte_prefix the first byte with fixed MSB pattern set; 5264 * lower value bits must be zero 5265 * @param[in] first_byte_prefix_bits the count of fixed MSBs in the first byte 5266 * (1 for 1xxxxxxx, 2 for 01xxxxxx, etc.) 5267 * @param[in] number the value to encode, must fit 32 bits 5268 * @param[in] buf_size the size of @a buf in bytes, 5269 * must not be zero 5270 * @param[out] buf the output buffer to write the encoded bytes 5271 * @return the number of bytes written on success; 5272 * zero if output buffer is too small to fit the number encoded 5273 */ 5274 static MHD_FN_PAR_OUT_SIZE_ (5,4) size_t 5275 hpack_put_number_to_buf (uint_fast8_t first_byte_prefix, 5276 uint_fast8_t first_byte_prefix_bits, 5277 uint_fast32_t number, 5278 size_t buf_size, 5279 uint8_t buf[MHD_FN_PAR_DYN_ARR_SIZE_ (buf_size)]) 5280 { 5281 const uint_fast8_t first_byte_val_max = 5282 (uint_fast8_t) (b8ones >> first_byte_prefix_bits); 5283 uint_fast32_t number_left; 5284 uint_fast8_t i; 5285 5286 mhd_assert (0u == (first_byte_prefix & first_byte_val_max)); 5287 mhd_assert (0u == ((first_byte_prefix >> 4u) >> 4u)); 5288 mhd_assert (0u != first_byte_prefix_bits); 5289 mhd_assert (8u > first_byte_prefix_bits); 5290 mhd_assert ((number & 0xFFFFFFFFu) == number); 5291 mhd_assert (0u != buf_size); 5292 5293 if (first_byte_val_max > number) /* the number must be strictly less than */ 5294 { 5295 buf[0] = (uint8_t) (first_byte_prefix | (uint8_t) number); 5296 return 1u; 5297 } 5298 buf[0] = (uint8_t) (first_byte_prefix | first_byte_val_max); 5299 number_left = number - first_byte_val_max; 5300 for (i = 1u; mhd_COND_PREDOMINANTLY (i < buf_size); ++i) 5301 { 5302 const uint8_t cur_byte = (uint8_t) (number_left & 0x7Fu); 5303 number_left >>= 7u; 5304 if (0 == number_left) 5305 { 5306 mhd_assert (0u == (cur_byte & 0x80u)); 5307 buf[i] = cur_byte; 5308 return i + 1u; /* Success exit point */ 5309 } 5310 buf[i] = (uint8_t) (cur_byte | 0x80u); 5311 mhd_assert (6u > i); 5312 } 5313 return 0u; /* Not enough space */ 5314 } 5315 5316 5317 MHD_INTERNAL MHD_FN_PAR_NONNULL_ALL_ 5318 MHD_FN_PAR_OUT_ (1) bool 5319 mhd_hpack_enc_init (struct mhd_HpackEncContext *hk_enc) 5320 { 5321 hk_enc->dyn = mhd_dtbl_create (mhd_hpack_def_dyn_table_size); 5322 5323 if (NULL == hk_enc->dyn) 5324 return false; /* Failure exit point */ 5325 5326 mhd_assert (mhd_hpack_def_dyn_table_size == \ 5327 mhd_dtbl_get_table_max_size (hk_enc->dyn)); 5328 5329 /* Set all sizes to the same initial value */ 5330 hk_enc->dyn_size_peer = mhd_hpack_def_dyn_table_size; 5331 hk_enc->dyn_size_new = hk_enc->dyn_size_peer; 5332 hk_enc->dyn_size_smallest = hk_enc->dyn_size_peer; 5333 5334 return true; /* Success exit point */ 5335 } 5336 5337 5338 MHD_INTERNAL MHD_FN_PAR_NONNULL_ALL_ 5339 MHD_FN_PAR_INOUT_ (1) void 5340 mhd_hpack_enc_deinit (struct mhd_HpackEncContext *hk_enc) 5341 { 5342 if (NULL == hk_enc->dyn) 5343 return; /* Nothing to deinit */ 5344 5345 mhd_dtbl_destroy (hk_enc->dyn); 5346 hk_enc->dyn = NULL; 5347 } 5348 5349 5350 MHD_INTERNAL MHD_FN_PAR_NONNULL_ALL_ 5351 MHD_FN_PAR_INOUT_ (1) void 5352 mhd_hpack_enc_set_dyn_size (struct mhd_HpackEncContext *hk_enc, 5353 size_t new_dyn_size) 5354 { 5355 mhd_assert (mhd_DTBL_MAX_SIZE >= new_dyn_size); 5356 if (hk_enc->dyn_size_smallest > new_dyn_size) 5357 hk_enc->dyn_size_smallest = new_dyn_size; 5358 5359 /* Postpone actual table resize to avoid several realloc() calls if 5360 multiple table resizes are performed. */ 5361 hk_enc->dyn_size_new = new_dyn_size; 5362 } 5363 5364 5365 MHD_INTERNAL MHD_FN_PAR_NONNULL_ALL_ 5366 MHD_FN_PAR_INOUT_ (1) bool 5367 mhd_hpack_enc_dyn_resize (struct mhd_HpackEncContext *hk_enc) 5368 { 5369 mhd_assert (hk_enc->dyn_size_new >= hk_enc->dyn_size_smallest); 5370 5371 if (mhd_dtbl_get_table_max_size (hk_enc->dyn) != hk_enc->dyn_size_new) 5372 { 5373 #ifndef MHD_FAVOR_SMALL_CODE 5374 /* This is just an optimisation to simplify eviction later */ 5375 mhd_dtbl_evict_to_size (hk_enc->dyn, 5376 hk_enc->dyn_size_smallest); 5377 #endif /* ! MHD_FAVOR_SMALL_CODE */ 5378 5379 if (mhd_COND_HARDLY_EVER (! mhd_dtbl_resize (&(hk_enc->dyn), \ 5380 hk_enc->dyn_size_new))) 5381 return false; 5382 5383 mhd_assert (mhd_dtbl_get_table_max_size (hk_enc->dyn) == \ 5384 hk_enc->dyn_size_new); 5385 } 5386 5387 return true; 5388 } 5389 5390 5391 /** 5392 * Encode an indexed field representation (RFC 7541, Section 6.1). 5393 * 5394 * @param[in] idx the 1-based field index, must be non-zero 5395 * @param[in] out_buff_size the size of @a out_buff in bytes, 5396 * must not be zero 5397 * @param[out] out_buff the output buffer to write the encoded field 5398 * @param[out] bytes_encoded to be set to the number of bytes written to the 5399 * @a out_buff 5400 * @return 'true' on success; 5401 * 'false' if the output buffer is too small 5402 */ 5403 static MHD_FN_PAR_NONNULL_ALL_ 5404 MHD_FN_PAR_OUT_SIZE_ (3,2) MHD_FN_PAR_OUT_ (4) bool 5405 hpack_enc_field_indexed (dtbl_idx_ft idx, 5406 const size_t out_buff_size, 5407 uint8_t *restrict out_buff, 5408 size_t *restrict bytes_encoded) 5409 { 5410 mhd_constexpr uint_fast8_t field_indexed_prfx = (uint_fast8_t) (1u << 7u); 5411 mhd_constexpr uint_fast8_t field_indexed_prfx_bits = 1u; 5412 size_t pos; 5413 5414 mhd_assert (0u != idx); 5415 mhd_assert (mhd_HPACK_MAX_POSSIBLE_IDX >= idx); 5416 mhd_assert (0u != out_buff_size); 5417 5418 pos = hpack_put_number_to_buf (field_indexed_prfx, 5419 field_indexed_prfx_bits, 5420 idx, 5421 out_buff_size, 5422 out_buff); 5423 5424 if (0u == pos) 5425 return false; /* Not enough space in the output buffer */ 5426 5427 *bytes_encoded = pos; 5428 return true; 5429 } 5430 5431 5432 /** 5433 * Literal header indexing type for HPACK literal representations. 5434 * 5435 * Selects which literal form to use (RFC 7541, Sections 6.2.1-6.2.3). 5436 */ 5437 enum MHD_FIXED_ENUM_ mhd_HpackEncLitIndexingType 5438 { 5439 /** 5440 * "Literal Header Field with Incremental Indexing" 5441 * RFC 7541, Section 6.2.1. 5442 */ 5443 mhd_HPACK_ENC_LIT_IDX_TYPE_INDEXING, 5444 /** 5445 * "Literal Header Field without Indexing" 5446 * RFC 7541, Section 6.2.2. 5447 */ 5448 mhd_HPACK_ENC_LIT_IDX_TYPE_NOT_INDEXING, 5449 /** 5450 * "Literal Header Field Never Indexed" 5451 * RFC 7541, Section 6.2.3. 5452 */ 5453 mhd_HPACK_ENC_LIT_IDX_TYPE_NEVER_INDEXING 5454 }; 5455 5456 5457 /** 5458 * Encode a string literal with optional Huffman coding (RFC 7541, Section 5.2). 5459 * 5460 * @param[in,out] hk_enc the encoder context 5461 * @param[in] str_data the field string to encode 5462 * @param[in] huffman_allowed set to 'true' to allow Huffman encoding 5463 * @param[in] out_buff_size the size of @a out_buff in bytes, could be zero 5464 * @param[out] out_buff the output buffer 5465 * @param[out] bytes_encoded to be set to the size of the encoded data 5466 * written to the @a out_buff 5467 * @return 'true' on success; 5468 * 'false' if the output buffer is too small 5469 */ 5470 static MHD_FN_PAR_NONNULL_ALL_ 5471 MHD_FN_PAR_IN_ (1) 5472 MHD_FN_PAR_OUT_SIZE_ (4,3) MHD_FN_PAR_OUT_ (5) bool 5473 hpack_enc_string_literal (const struct mhd_BufferConst *restrict str_data, 5474 bool huffman_allowed, 5475 const size_t out_buff_size, 5476 uint8_t *restrict out_buff, 5477 size_t *restrict bytes_encoded) 5478 { 5479 /** The prefix for Huffman-encoded string */ 5480 mhd_constexpr uint8_t huff_on_prfx = (uint8_t) (1u << 7u); 5481 /** The prefix for literal string without Huffman encoding */ 5482 mhd_constexpr uint8_t huff_off_prfx = (uint8_t) (0u << 7u); 5483 mhd_constexpr uint8_t huff_prfx_bits = 1u; 5484 size_t enc_size; 5485 size_t enc_size_enc_len; 5486 5487 mhd_assert ((str_data->size & 0xFFFFFFFFu) == str_data->size); 5488 5489 if (mhd_COND_ALMOST_NEVER (0u == str_data->size)) 5490 { 5491 if (0u == out_buff_size) 5492 return false; 5493 /* If Huffman is allowed, encode zero size as "Huffman encoded" for 5494 consistency. */ 5495 out_buff[0] = (huffman_allowed ? huff_on_prfx : huff_off_prfx); 5496 *bytes_encoded = 1u; 5497 return true; 5498 } 5499 5500 if (huffman_allowed) 5501 { 5502 uint_fast32_t est_enc_size; 5503 size_t est_enc_size_enc_len; 5504 bool is_limited_by_buff_size; 5505 5506 est_enc_size = 5507 mhd_h2_huffman_est_avg_size ((uint_fast32_t) str_data->size); 5508 est_enc_size_enc_len = hpack_number_len (huff_prfx_bits, 5509 est_enc_size); 5510 if ((out_buff_size <= est_enc_size_enc_len) || 5511 ((out_buff_size - est_enc_size_enc_len) < est_enc_size)) 5512 { 5513 /* Probably the buffer is not large enough to encode the string */ 5514 /* Try as if the string were compressible to a minimal size */ 5515 est_enc_size = 5516 mhd_h2_huffman_est_min_size ((uint_fast32_t) str_data->size); 5517 est_enc_size_enc_len = hpack_number_len (huff_prfx_bits, 5518 est_enc_size); 5519 if (out_buff_size < (est_enc_size_enc_len + est_enc_size)) 5520 return false; /* The output buffer is not large enough */ 5521 is_limited_by_buff_size = true; 5522 } 5523 else 5524 is_limited_by_buff_size = 5525 ((out_buff_size - est_enc_size_enc_len) < str_data->size); 5526 5527 mhd_assert (out_buff_size > est_enc_size_enc_len); 5528 mhd_assert ((out_buff_size - est_enc_size_enc_len) \ 5529 >= est_enc_size); 5530 mhd_assert (is_limited_by_buff_size || \ 5531 ((out_buff_size - est_enc_size_enc_len) >= str_data->size)); 5532 5533 /* Limit the size of the buffer for the encoded string to the size of 5534 the original (not encoded) string or the size of the buffer (whatever 5535 is smaller). By limiting the size of the buffer to the size of the 5536 original string, Huffman encoding that grows larger than the original 5537 is aborted early. */ 5538 enc_size = 5539 mhd_h2_huffman_encode (str_data->size, 5540 str_data->data, 5541 (size_t) 5542 (is_limited_by_buff_size ? 5543 (out_buff_size - est_enc_size_enc_len) : 5544 str_data->size), 5545 out_buff + est_enc_size_enc_len); 5546 5547 mhd_assert (out_buff_size - est_enc_size_enc_len >= enc_size); 5548 5549 if (0u != enc_size) 5550 { 5551 /* Successfully Huffman-encoded the string */ 5552 enc_size_enc_len = 5553 hpack_put_number_to_buf (huff_on_prfx, 5554 huff_prfx_bits, 5555 (uint_fast32_t) enc_size, 5556 est_enc_size_enc_len, 5557 out_buff); 5558 if (mhd_COND_ALMOST_NEVER (0u == enc_size_enc_len)) 5559 { 5560 /* The actual encoded size is larger than estimated */ 5561 size_t calc_enc_size_enc_len; 5562 5563 mhd_assert (est_enc_size < enc_size); 5564 5565 calc_enc_size_enc_len = hpack_number_len (huff_prfx_bits, 5566 (uint_fast32_t) enc_size); 5567 if ((out_buff_size - enc_size) < calc_enc_size_enc_len) 5568 return false; /* The output buffer is not large enough */ 5569 5570 memmove (out_buff + calc_enc_size_enc_len, 5571 out_buff + est_enc_size_enc_len, 5572 enc_size); 5573 5574 enc_size_enc_len = 5575 hpack_put_number_to_buf (huff_on_prfx, 5576 huff_prfx_bits, 5577 (uint_fast32_t) enc_size, 5578 calc_enc_size_enc_len, 5579 out_buff); 5580 mhd_assert (calc_enc_size_enc_len == enc_size_enc_len); 5581 } 5582 else if (est_enc_size_enc_len != enc_size_enc_len) 5583 { 5584 mhd_assert (est_enc_size_enc_len > enc_size_enc_len); 5585 memmove (out_buff + enc_size_enc_len, 5586 out_buff + est_enc_size_enc_len, 5587 enc_size); 5588 } 5589 5590 *bytes_encoded = (enc_size_enc_len + enc_size); 5591 return true; /* Success exit point */ 5592 } 5593 else /* 0u == enc_size */ 5594 { 5595 /* Huffman-encoded version needs more space than provided */ 5596 /* If available space was less than needed to put the string without 5597 Huffman encoding, then return failure here. */ 5598 if (is_limited_by_buff_size) 5599 return false; 5600 } 5601 /* Retry without Huffman encoding */ 5602 } 5603 5604 /* Put string without Huffman encoding */ 5605 enc_size = str_data->size; 5606 5607 if (enc_size >= out_buff_size) 5608 return false; /* The output buffer is not large enough */ 5609 5610 enc_size_enc_len = 5611 hpack_put_number_to_buf (huff_off_prfx, 5612 huff_prfx_bits, 5613 (uint_fast32_t) enc_size, 5614 out_buff_size - enc_size, 5615 out_buff); 5616 5617 if (0u == enc_size_enc_len) 5618 return false; /* The output buffer is not large enough */ 5619 5620 mhd_assert ((out_buff_size - enc_size_enc_len) >= enc_size); 5621 5622 memcpy (out_buff + enc_size_enc_len, 5623 str_data->data, 5624 enc_size); 5625 5626 *bytes_encoded = (enc_size_enc_len + enc_size); 5627 return true; /* Success exit point */ 5628 } 5629 5630 5631 /** 5632 * Encode a literal field (name by index reference or literal; value 5633 * always literal). 5634 * 5635 * Produces one of the literal field representations (RFC 7541, 5636 * Sections 6.2.1-6.2.3). 5637 * The name may be encoded by index reference (if allowed) or literally; the 5638 * value is always encoded literally. 5639 * String representations may use Huffman coding if permitted. 5640 * 5641 * @param[in,out] hk_enc the encoder context 5642 * @param[in] name the field name bytes and size 5643 * @param[in] name_idx the field name index if known and indexed name is 5644 * allowed, 5645 * zero if index is not known or indexed name is not 5646 * allowed 5647 * @param[in] value the field value bytes and size 5648 * @param[in] msg_type the literal representation kind to use 5649 * @param[in] name_idx_stat_allowed set to 'true' if name encoding as a 5650 * reference to the static table is allowed 5651 * @param[in] name_idx_dyn_allowed set to 'true' if name encoding as a 5652 * reference to the dynamic table is allowed 5653 * @param[in] huffman_allowed set to 'true' if Huffman coding is allowed 5654 * @param[in] out_buff_size the size of @a out_buff in bytes, 5655 * could be zero (the function will always fail 5656 * if it is less than two) 5657 * @param[out] out_buff the output buffer for the encoded field 5658 * @param[out] bytes_encoded to be set to the number of bytes written to 5659 * the @a out_buff 5660 * @return 'true' on success; 5661 * 'false' if the output buffer is too small 5662 */ 5663 static MHD_FN_PAR_NONNULL_ALL_ 5664 MHD_FN_PAR_INOUT_ (1) 5665 MHD_FN_PAR_IN_ (2) MHD_FN_PAR_IN_ (4) 5666 MHD_FN_PAR_OUT_SIZE_ (10,9) MHD_FN_PAR_OUT_ (11) bool 5667 hpack_enc_field_literal (struct mhd_HpackEncContext *restrict hk_enc, 5668 const struct mhd_BufferConst *restrict name, 5669 dtbl_idx_ft name_idx, 5670 const struct mhd_BufferConst *restrict value, 5671 enum mhd_HpackEncLitIndexingType msg_type, 5672 bool name_idx_stat_allowed, 5673 bool name_idx_dyn_allowed, 5674 bool huffman_allowed, 5675 const size_t out_buff_size, 5676 uint8_t *restrict out_buff, 5677 size_t *restrict bytes_encoded) 5678 { 5679 mhd_constexpr uint_fast8_t field_indexing_prfx = (uint_fast8_t) (1u << 6u); 5680 mhd_constexpr uint_fast8_t field_indexing_prfx_bits = 2u; 5681 mhd_constexpr uint_fast8_t field_not_idxng_prfx = (uint_fast8_t) (0u << 4u); 5682 mhd_constexpr uint_fast8_t field_not_idxng_prfx_bits = 4u; 5683 mhd_constexpr uint_fast8_t field_never_idxng_prfx = (uint_fast8_t) (1u << 4u); 5684 mhd_constexpr uint_fast8_t field_never_idxng_prfx_bits = 4u; 5685 struct mhd_HpackDTblContext const *restrict dyn = hk_enc->dyn; 5686 uint_fast8_t first_byte_prefix; 5687 uint_fast8_t first_byte_prefix_bits; 5688 size_t pos; 5689 size_t pos_incr; 5690 5691 mhd_assert ((0u == name->size) || (':' != name->data[0])); 5692 5693 if (2u > out_buff_size) 5694 return false; /* No space even for the minimal field */ 5695 5696 switch (msg_type) 5697 { 5698 case mhd_HPACK_ENC_LIT_IDX_TYPE_INDEXING: 5699 first_byte_prefix = field_indexing_prfx; 5700 first_byte_prefix_bits = field_indexing_prfx_bits; 5701 break; 5702 case mhd_HPACK_ENC_LIT_IDX_TYPE_NOT_INDEXING: 5703 first_byte_prefix = field_not_idxng_prfx; 5704 first_byte_prefix_bits = field_not_idxng_prfx_bits; 5705 break; 5706 case mhd_HPACK_ENC_LIT_IDX_TYPE_NEVER_INDEXING: 5707 first_byte_prefix = field_never_idxng_prfx; 5708 first_byte_prefix_bits = field_never_idxng_prfx_bits; 5709 break; 5710 default: 5711 mhd_UNREACHABLE (); 5712 return false; 5713 } 5714 5715 if (0u == name_idx) 5716 { 5717 if (name_idx_stat_allowed && name_idx_dyn_allowed) 5718 name_idx = mhd_htbl_find_name_real (dyn, 5719 name->size, 5720 name->data); 5721 else if (name_idx_stat_allowed && (0u != name->size)) 5722 name_idx = mhd_stbl_find_name_real (name->size, 5723 name->data); 5724 else if (mhd_COND_ALMOST_NEVER (name_idx_dyn_allowed)) 5725 name_idx = mhd_dtbl_find_name (dyn, 5726 name->size, 5727 name->data); 5728 } 5729 else 5730 { 5731 mhd_assert (name_idx_stat_allowed || \ 5732 (mhd_HPACK_STBL_LAST_IDX < name_idx)); 5733 mhd_assert (name_idx_dyn_allowed || \ 5734 (mhd_HPACK_STBL_LAST_IDX >= name_idx)); 5735 } 5736 5737 pos = 0u; 5738 5739 if (0u != name_idx) 5740 { 5741 /* Add name as a reference */ 5742 mhd_assert (name_idx_dyn_allowed || name_idx_stat_allowed); 5743 pos_incr = hpack_put_number_to_buf (first_byte_prefix, 5744 first_byte_prefix_bits, 5745 name_idx, 5746 out_buff_size - pos - 1u, /* Reserve one byte for the field value */ 5747 out_buff + pos); 5748 if (0u == pos_incr) 5749 return false; /* Not enough space */ 5750 pos += pos_incr; 5751 } 5752 else 5753 { 5754 /* Add name literally */ 5755 5756 /* Use 'zero' index to indicate literal name */ 5757 out_buff[pos++] = (uint8_t) first_byte_prefix; 5758 5759 /* The buffer has at least one byte (or more) available; 5760 the next call will fail if only one byte is available. */ 5761 if (! hpack_enc_string_literal (name, 5762 huffman_allowed, 5763 out_buff_size - pos - 1u, /* Reserve one byte for the field value */ 5764 out_buff + pos, 5765 &pos_incr)) 5766 return false; /* Not enough space */ 5767 5768 pos += pos_incr; 5769 } 5770 5771 /* The output buffer should have at least one byte of space available */ 5772 mhd_assert (out_buff_size > pos); 5773 5774 /* Add value literally */ 5775 5776 if (! hpack_enc_string_literal (value, 5777 huffman_allowed, 5778 out_buff_size - pos, 5779 out_buff + pos, 5780 &pos_incr)) 5781 return false; /* Not enough space */ 5782 5783 pos += pos_incr; 5784 mhd_assert (out_buff_size >= pos); 5785 5786 *bytes_encoded = pos; 5787 return true; 5788 } 5789 5790 5791 /** 5792 * Internal per-field encoding result. 5793 */ 5794 enum MHD_FIXED_ENUM_ mhd_HpackEncResultInternal 5795 { 5796 /** 5797 * The output buffer is too small 5798 */ 5799 mhd_ENC_RESULT_INT_NO_SPACE = 0, 5800 /** 5801 * The field is encoded successfully, do not add the field to the dynamic 5802 * table 5803 */ 5804 mhd_ENC_RESULT_INT_OK_NO_ADD_TO_DYN, 5805 /** 5806 * The field is encoded successfully, add the field to the dynamic table 5807 */ 5808 mhd_ENC_RESULT_INT_OK_ADD_TO_DYN 5809 }; 5810 5811 /** 5812 * Encode one field according to the requested indexing policy. 5813 * 5814 * Chooses between indexed and literal representations based on table contents 5815 * and the @a enc_pol policy, and decides whether to add the field to the 5816 * dynamic table (using simple size-based heuristics when not explicitly 5817 * forced). 5818 * 5819 * @param[in,out] hk_enc the encoder context 5820 * @param[in] name the header name 5821 * @param[in] value the header value 5822 * @param[in] enc_pol the encoding policy to apply 5823 * @param[in] out_buff_size the size of @a out_buff in bytes, 5824 * must not be zero 5825 * @param[out] out_buff the output buffer 5826 * @param[out] bytes_encoded to be set to the number of bytes written to 5827 * the @a out_buff 5828 * @return #mhd_ENC_RESULT_INT_NO_SPACE on insufficient buffer; 5829 * #mhd_ENC_RESULT_INT_OK_NO_ADD_TO_DYN or 5830 * #mhd_ENC_RESULT_INT_OK_ADD_TO_DYN on success 5831 */ 5832 static MHD_FN_PAR_NONNULL_ALL_ 5833 MHD_FN_PAR_INOUT_ (1) 5834 MHD_FN_PAR_IN_ (2) MHD_FN_PAR_IN_ (3) 5835 MHD_FN_PAR_OUT_SIZE_ (6,5) MHD_FN_PAR_OUT_ (7) enum mhd_HpackEncResultInternal 5836 hpack_enc_field (struct mhd_HpackEncContext *restrict hk_enc, 5837 const struct mhd_BufferConst *restrict name, 5838 const struct mhd_BufferConst *restrict value, 5839 enum mhd_HpackEncPolicy enc_pol, 5840 const size_t out_buff_size, 5841 uint8_t *restrict out_buff, 5842 size_t *restrict bytes_encoded) 5843 { 5844 mhd_assert (0u != out_buff_size); 5845 mhd_assert ((name->size & 0xFFFFFFFFu) == name->size); 5846 mhd_assert ((value->size & 0xFFFFFFFFu) == value->size); 5847 5848 /* Check the enum values order */ 5849 // TODO: replace with static asserts 5850 mhd_assert (mhd_HPACK_ENC_POL_FORCED_NEW_IDX < mhd_HPACK_ENC_POL_FORCED); 5851 mhd_assert (mhd_HPACK_ENC_POL_ALWAYS_IF_FIT < mhd_HPACK_ENC_POL_NOT_INDEXED); 5852 mhd_assert (mhd_HPACK_ENC_POL_ALWAYS_IF_FIT < mhd_HPACK_ENC_POL_DESIRABLE); 5853 mhd_assert (mhd_HPACK_ENC_POL_DESIRABLE < mhd_HPACK_ENC_POL_LOWEST_PRIO); 5854 mhd_assert (mhd_HPACK_ENC_POL_LOWEST_PRIO < mhd_HPACK_ENC_POL_AVOID_NEW_IDX); 5855 mhd_assert (mhd_HPACK_ENC_POL_AVOID_NEW_IDX < mhd_HPACK_ENC_POL_NOT_INDEXED); 5856 mhd_assert (mhd_HPACK_ENC_POL_NOT_INDEXED < \ 5857 mhd_HPACK_ENC_POL_NEVER_W_NAME_IDX); 5858 mhd_assert (mhd_HPACK_ENC_POL_NEVER_W_NAME_IDX < \ 5859 mhd_HPACK_ENC_POL_NEVER_W_NAME_LIT_NO_HUFFMAN); 5860 5861 if ((mhd_HPACK_ENC_POL_FORCED <= enc_pol) 5862 && (mhd_HPACK_ENC_POL_AVOID_NEW_IDX >= enc_pol)) 5863 { 5864 const dtbl_idx_ft field_idx = 5865 mhd_htbl_find_entry_real (hk_enc->dyn, 5866 name->size, 5867 name->data, 5868 value->size, 5869 value->data); 5870 5871 if (0u != field_idx) 5872 { 5873 if (! hpack_enc_field_indexed (field_idx, 5874 out_buff_size, 5875 out_buff, 5876 bytes_encoded)) 5877 return mhd_ENC_RESULT_INT_NO_SPACE; 5878 5879 return mhd_ENC_RESULT_INT_OK_NO_ADD_TO_DYN; 5880 } 5881 } 5882 5883 /* The field is not in the tables or should not be added as an indexed 5884 field */ 5885 5886 /* Add the field literally */ 5887 5888 if (mhd_HPACK_ENC_POL_NEVER_W_NAME_IDX <= enc_pol) 5889 { 5890 /* Add field literally as "never indexed" */ 5891 const bool name_idx_stat_allowed = 5892 (mhd_HPACK_ENC_POL_NEVER_W_NAME_IDX_STATIC >= enc_pol); 5893 const bool name_idx_dyn_allowed = 5894 (mhd_HPACK_ENC_POL_NEVER_W_NAME_IDX_STATIC > enc_pol); 5895 const bool huffman_allowed = 5896 (mhd_HPACK_ENC_POL_NEVER_W_NAME_LIT_NO_HUFFMAN > enc_pol); 5897 if (! hpack_enc_field_literal (hk_enc, 5898 name, 5899 0u, 5900 value, 5901 mhd_HPACK_ENC_LIT_IDX_TYPE_NEVER_INDEXING, 5902 name_idx_stat_allowed, 5903 name_idx_dyn_allowed, 5904 huffman_allowed, 5905 out_buff_size, 5906 out_buff, 5907 bytes_encoded)) 5908 return mhd_ENC_RESULT_INT_NO_SPACE; 5909 5910 return mhd_ENC_RESULT_INT_OK_NO_ADD_TO_DYN; 5911 } 5912 5913 if (mhd_HPACK_ENC_POL_AVOID_NEW_IDX <= enc_pol) 5914 { 5915 /* Adding to the tables is not allowed */ 5916 mhd_assert (mhd_HPACK_ENC_POL_NOT_INDEXED >= enc_pol); 5917 5918 if (! hpack_enc_field_literal (hk_enc, 5919 name, 5920 0u, 5921 value, 5922 mhd_HPACK_ENC_LIT_IDX_TYPE_NOT_INDEXING, 5923 true, 5924 true, 5925 true, 5926 out_buff_size, 5927 out_buff, 5928 bytes_encoded)) 5929 return mhd_ENC_RESULT_INT_NO_SPACE; 5930 5931 return mhd_ENC_RESULT_INT_OK_NO_ADD_TO_DYN; 5932 } 5933 5934 if (mhd_HPACK_ENC_POL_ALWAYS_IF_FIT >= enc_pol) 5935 { 5936 bool add_to_idx; 5937 if ((mhd_HPACK_ENC_POL_FORCED == enc_pol) || 5938 (mhd_HPACK_ENC_POL_FORCED_NEW_IDX == enc_pol)) 5939 add_to_idx = true; 5940 else 5941 add_to_idx = mhd_dtbl_check_entry_fit (hk_enc->dyn, 5942 name->size, 5943 value->size); 5944 5945 if (! hpack_enc_field_literal (hk_enc, 5946 name, 5947 0u, 5948 value, 5949 add_to_idx ? 5950 mhd_HPACK_ENC_LIT_IDX_TYPE_INDEXING : 5951 mhd_HPACK_ENC_LIT_IDX_TYPE_NOT_INDEXING, 5952 true, 5953 true, 5954 true, 5955 out_buff_size, 5956 out_buff, 5957 bytes_encoded)) 5958 return mhd_ENC_RESULT_INT_NO_SPACE; 5959 5960 return add_to_idx ? 5961 mhd_ENC_RESULT_INT_OK_ADD_TO_DYN : 5962 mhd_ENC_RESULT_INT_OK_NO_ADD_TO_DYN; 5963 } 5964 5965 /* Indexing or not indexing is not forced. 5966 Need to decide whether to add the field to the index based on some 5967 heuristics. 5968 Use only field size and buffer data when deciding. Do not analyse the 5969 field name or value (it should be performed by caller). */ 5970 5971 mhd_assert (mhd_HPACK_ENC_POL_DESIRABLE <= enc_pol); 5972 mhd_assert (mhd_HPACK_ENC_POL_LOWEST_PRIO >= enc_pol); 5973 5974 if (1) /* For local scope */ 5975 { 5976 enum mhd_Tristate add_to_idx; 5977 5978 add_to_idx = 5979 mhd_dtbl_check_entry_fit (hk_enc->dyn, 5980 name->size, 5981 value->size) ? mhd_T_MAYBE : mhd_T_NO; 5982 5983 /* The following algorithm is simplified and can be improved */ 5984 5985 if (mhd_T_IS_MAYBE (add_to_idx)) 5986 { 5987 const size_t field_size = 5988 name->size + value->size + mhd_dtbl_entry_overhead; 5989 const size_t dyn_size = hk_enc->dyn_size_new; 5990 const size_t dyn_used = mhd_dtbl_get_table_used (hk_enc->dyn); 5991 const size_t dyn_free = dyn_size - dyn_used; 5992 const size_t num_entries = mhd_dtbl_get_num_entries (hk_enc->dyn); 5993 5994 mhd_assert (dyn_size >= dyn_used); 5995 5996 if (512u > dyn_size) 5997 { 5998 /* Very small table, use very basic logic */ 5999 add_to_idx = 6000 (mhd_HPACK_ENC_POL_NEUTRAL >= enc_pol) ? mhd_T_YES : mhd_T_NO; 6001 } 6002 else if (mhd_HPACK_ENC_POL_DESIRABLE >= enc_pol) 6003 { 6004 mhd_assert (mhd_HPACK_ENC_POL_DESIRABLE == enc_pol); 6005 if (field_size <= dyn_free) 6006 add_to_idx = mhd_T_YES; 6007 else if (field_size <= (dyn_size - dyn_size / 4)) 6008 add_to_idx = mhd_T_YES; 6009 else if (2u >= num_entries) 6010 add_to_idx = mhd_T_YES; 6011 else 6012 add_to_idx = mhd_T_NO; 6013 } 6014 else if (mhd_HPACK_ENC_POL_NEUTRAL == enc_pol) 6015 { 6016 if (field_size <= dyn_free / 4) 6017 add_to_idx = mhd_T_YES; 6018 else if (field_size <= dyn_size / 32) 6019 add_to_idx = mhd_T_YES; 6020 else if ((field_size <= dyn_size / 4) 6021 && ((field_size / 2) >= (dyn_used / num_entries))) 6022 add_to_idx = mhd_T_YES; 6023 else 6024 add_to_idx = mhd_T_NO; 6025 } 6026 else if (mhd_HPACK_ENC_POL_LOW_PRIO == enc_pol) 6027 { 6028 if (field_size <= dyn_free / 16) 6029 add_to_idx = mhd_T_YES; 6030 else if (field_size <= dyn_size / 128) 6031 add_to_idx = mhd_T_YES; 6032 else 6033 add_to_idx = mhd_T_NO; 6034 } 6035 else if (mhd_HPACK_ENC_POL_LOWEST_PRIO == enc_pol) 6036 { 6037 if (field_size <= dyn_free / 64) 6038 add_to_idx = mhd_T_YES; 6039 else if (field_size <= dyn_size / 512) 6040 add_to_idx = mhd_T_YES; 6041 else 6042 add_to_idx = mhd_T_NO; 6043 } 6044 else 6045 { 6046 mhd_UNREACHABLE (); 6047 add_to_idx = mhd_T_NO; 6048 } 6049 } 6050 mhd_assert (mhd_T_IS_NOT_MAYBE (add_to_idx)); 6051 6052 if (mhd_T_IS_YES (add_to_idx)) 6053 { 6054 if (! hpack_enc_field_literal (hk_enc, 6055 name, 6056 0u, 6057 value, 6058 mhd_HPACK_ENC_LIT_IDX_TYPE_INDEXING, 6059 true, 6060 true, 6061 true, 6062 out_buff_size, 6063 out_buff, 6064 bytes_encoded)) 6065 return mhd_ENC_RESULT_INT_NO_SPACE; 6066 6067 return mhd_ENC_RESULT_INT_OK_ADD_TO_DYN; 6068 } 6069 } 6070 6071 if (! hpack_enc_field_literal (hk_enc, 6072 name, 6073 0u, 6074 value, 6075 mhd_HPACK_ENC_LIT_IDX_TYPE_NOT_INDEXING, 6076 true, 6077 true, 6078 true, 6079 out_buff_size, 6080 out_buff, 6081 bytes_encoded)) 6082 return mhd_ENC_RESULT_INT_NO_SPACE; 6083 6084 return mhd_ENC_RESULT_INT_OK_NO_ADD_TO_DYN; 6085 } 6086 6087 6088 /** 6089 * Emit Dynamic Table Size Update representation(s) if needed. 6090 * 6091 * If the current dynamic table size differs from the pending minimal/final 6092 * sizes accumulated in @a hk_enc, this function encodes one or two size 6093 * updates, and performs local eviction down to the minimal size for 6094 * consistency. 6095 * 6096 * @param[in,out] hk_enc the encoder context 6097 * @param[in] out_buff_size the size of @a out_buff in bytes, 6098 * could be zero 6099 * @param[out] out_buff the output buffer to write encoded messages 6100 * @param[out] bytes_encoded the output variable to be set to the number of 6101 * bytes written 6102 * @return 'true' on success; 6103 * 'false' if the output buffer is too small 6104 */ 6105 static MHD_FN_PAR_OUT_SIZE_ (3,2) MHD_FN_PAR_OUT_ (4) bool 6106 hpack_enc_check_dyn_size_update ( 6107 struct mhd_HpackEncContext *restrict hk_enc, 6108 size_t out_buff_size, 6109 uint8_t *restrict out_buff, 6110 size_t *restrict bytes_encoded) 6111 { 6112 /** The prefix for Dynamic Table Size Update message */ 6113 mhd_constexpr uint_fast8_t dyn_size_upd_msg_prfx = (uint_fast8_t) (1u << 5u); 6114 mhd_constexpr uint_fast8_t dyn_size_upd_msg_prfx_bits = 3u; 6115 size_t pos; 6116 size_t pos_incr; 6117 struct mhd_HpackDTblContext *restrict const dyn = hk_enc->dyn; 6118 6119 mhd_assert (mhd_DTBL_MAX_SIZE >= hk_enc->dyn_size_smallest); 6120 mhd_assert (mhd_DTBL_MAX_SIZE >= hk_enc->dyn_size_new); 6121 mhd_assert (hk_enc->dyn_size_peer >= hk_enc->dyn_size_smallest); 6122 mhd_assert (hk_enc->dyn_size_new >= hk_enc->dyn_size_smallest); 6123 mhd_assert (mhd_dtbl_get_table_max_size (dyn) \ 6124 >= hk_enc->dyn_size_smallest); 6125 6126 if (mhd_dtbl_get_table_max_size (dyn) != hk_enc->dyn_size_smallest) 6127 mhd_dtbl_evict_to_size (dyn, 6128 hk_enc->dyn_size_smallest); 6129 6130 if ((hk_enc->dyn_size_smallest == hk_enc->dyn_size_peer) && 6131 (hk_enc->dyn_size_new == hk_enc->dyn_size_peer)) 6132 { 6133 *bytes_encoded = 0u; 6134 return true; /* No resize signal needed */ 6135 } 6136 6137 /* Need to create a "Dynamic Table Size Update" signal */ 6138 if (0u == out_buff_size) 6139 return false; /* Not enough space */ 6140 6141 pos = 0u; 6142 6143 if (hk_enc->dyn_size_peer != hk_enc->dyn_size_smallest) 6144 { 6145 /* Signal the minimal size so the peer evicts entries */ 6146 pos_incr = 6147 hpack_put_number_to_buf (dyn_size_upd_msg_prfx, 6148 dyn_size_upd_msg_prfx_bits, 6149 (uint_fast32_t) hk_enc->dyn_size_smallest, 6150 out_buff_size, 6151 out_buff); 6152 6153 if (0u == pos_incr) 6154 return false; /* Not enough space */ 6155 6156 pos += pos_incr; 6157 } 6158 6159 if (hk_enc->dyn_size_new != hk_enc->dyn_size_smallest) 6160 { 6161 if (pos == out_buff_size) 6162 return false; /* Not enough space for the second resize message */ 6163 6164 /* Signal the final dynamic table size */ 6165 pos_incr = 6166 hpack_put_number_to_buf (dyn_size_upd_msg_prfx, 6167 dyn_size_upd_msg_prfx_bits, 6168 (uint_fast32_t) hk_enc->dyn_size_new, 6169 out_buff_size - pos, 6170 out_buff + pos); 6171 6172 if (0u == pos_incr) 6173 return false; /* Not enough space */ 6174 6175 pos += pos_incr; 6176 } 6177 6178 mhd_assert (0u != pos); 6179 *bytes_encoded = pos; 6180 return true; 6181 } 6182 6183 6184 /** 6185 * Apply a pending Dynamic Table Size Update for the encoder. 6186 * 6187 * Resizes the dynamic table to @a hk_enc->new_dyn_size if needed and updates 6188 * hk_enc data accordingly. 6189 * 6190 * @param[in,out] hk_enc the encoder context 6191 * @return 'true' on success; 6192 * 'false' on allocation error 6193 */ 6194 static bool 6195 hpack_enc_perform_dyn_size_update (struct mhd_HpackEncContext *restrict hk_enc) 6196 { 6197 mhd_assert (mhd_dtbl_get_table_used (hk_enc->dyn) 6198 <= hk_enc->dyn_size_smallest); 6199 if (mhd_dtbl_get_table_max_size (hk_enc->dyn) != hk_enc->dyn_size_new) 6200 { 6201 if (mhd_COND_HARDLY_EVER (! mhd_dtbl_resize (&(hk_enc->dyn), \ 6202 hk_enc->dyn_size_new))) 6203 return false; 6204 6205 mhd_assert (mhd_dtbl_get_table_max_size (hk_enc->dyn) == \ 6206 hk_enc->dyn_size_new); 6207 } 6208 6209 hk_enc->dyn_size_smallest = hk_enc->dyn_size_new; 6210 hk_enc->dyn_size_peer = hk_enc->dyn_size_new; 6211 6212 return true; 6213 } 6214 6215 6216 MHD_INTERNAL MHD_FN_PAR_NONNULL_ALL_ 6217 MHD_FN_PAR_INOUT_ (1) 6218 MHD_FN_PAR_IN_ (2) MHD_FN_PAR_IN_ (3) 6219 MHD_FN_PAR_OUT_SIZE_ (6,5) MHD_FN_PAR_OUT_ (7) enum mhd_HpackEncResult 6220 mhd_hpack_enc_field (struct mhd_HpackEncContext *restrict hk_enc, 6221 const struct mhd_BufferConst *restrict name, 6222 const struct mhd_BufferConst *restrict value, 6223 enum mhd_HpackEncPolicy enc_pol, 6224 const size_t out_buff_size, 6225 uint8_t *restrict out_buff, 6226 size_t *restrict bytes_encoded) 6227 { 6228 size_t pos; 6229 size_t pos_incr; 6230 enum mhd_HpackEncResultInternal enc_field_res; 6231 6232 mhd_assert ((name->size & 0xFFFFFFFFu) == name->size); 6233 mhd_assert ((value->size & 0xFFFFFFFFu) == value->size); 6234 mhd_assert ((0u == name->size) || (':' != name->data[0])); 6235 6236 if (0u == out_buff_size) 6237 return mhd_HPACK_ENC_BUFFER_TOO_SMALL; 6238 6239 pos = 0u; 6240 6241 /* Add Dynamic Table Size Update message if needed */ 6242 if (! hpack_enc_check_dyn_size_update (hk_enc, 6243 out_buff_size - 1u, /* Reserve one byte for minimal field size */ 6244 out_buff, 6245 &pos_incr)) 6246 return mhd_HPACK_ENC_BUFFER_TOO_SMALL; 6247 6248 pos += pos_incr; 6249 mhd_assert (pos < out_buff_size); 6250 6251 enc_field_res = 6252 hpack_enc_field (hk_enc, 6253 name, 6254 value, 6255 enc_pol, 6256 out_buff_size - pos, 6257 out_buff + pos, 6258 &pos_incr); 6259 6260 if (mhd_ENC_RESULT_INT_NO_SPACE == enc_field_res) 6261 return mhd_HPACK_ENC_BUFFER_TOO_SMALL; 6262 6263 pos += pos_incr; 6264 6265 /* Finally resize the dynamic table (if resize is pending) */ 6266 if (! hpack_enc_perform_dyn_size_update (hk_enc)) 6267 return mhd_HPACK_ENC_RES_ALLOC_ERR; 6268 6269 /* Add the field (if needed) only after dynamic table resizing (if any) */ 6270 if (mhd_ENC_RESULT_INT_OK_ADD_TO_DYN == enc_field_res) 6271 mhd_dtbl_new_entry (hk_enc->dyn, 6272 name->size, 6273 name->data, 6274 value->size, 6275 value->data); 6276 else 6277 mhd_assert (mhd_ENC_RESULT_INT_OK_NO_ADD_TO_DYN == enc_field_res); 6278 6279 *bytes_encoded = pos; 6280 return mhd_HPACK_ENC_RES_OK; 6281 } 6282 6283 6284 /** 6285 * Convert an HTTP status @a code to a three-character decimal string. 6286 * 6287 * @param code the status code; must be >= 100 and <= 699 6288 * @param[out] code_str destination buffer of exactly 3 bytes; 6289 * receives the decimal digits of @a code 6290 */ 6291 mhd_static_inline 6292 MHD_FN_PAR_OUT_ (2) void 6293 status_to_str (uint_fast16_t code, 6294 char code_str[3]) 6295 { 6296 mhd_assert (100u <= code); 6297 mhd_assert (699u >= code); 6298 6299 code_str[0] = (char) ('0' + (char) (uint8_t) ((code / 100u) % 10)); 6300 code_str[1] = (char) ('0' + (char) (uint8_t) ((code / 10u) % 10)); 6301 code_str[2] = (char) ('0' + (char) (uint8_t) ((code / 1u) % 10)); 6302 } 6303 6304 6305 /** 6306 * Pseudo-header ":status" name in the string form 6307 */ 6308 static const struct mhd_BufferConst pf_status_str = mhd_MSTR_INIT (":status"); 6309 6310 /** 6311 * Encode one pseudo-header ":status" according to the requested indexing 6312 * policy. 6313 * 6314 * Chooses between indexed and literal representations based on table contents 6315 * and the @a enc_pol policy, and decides whether to add the field to the 6316 * dynamic table (using simple size-based heuristics when not explicitly 6317 * forced). 6318 * 6319 * @param[in,out] hk_enc the encoder context 6320 * @param[in] code the status code, must be >= 100 and <= 699 6321 * @param[in] enc_pol the encoding policy to apply 6322 * @param[out] code_str where the string representation of the @a code 6323 * to be written if literal encoding is used 6324 * @param[in] out_buff_size the size of @a out_buff in bytes, 6325 * must not be zero 6326 * @param[out] out_buff the output buffer 6327 * @param[out] bytes_encoded to be set to the number of bytes written to 6328 * the @a out_buff 6329 * @return #mhd_ENC_RESULT_INT_NO_SPACE on insufficient buffer; 6330 * #mhd_ENC_RESULT_INT_OK_NO_ADD_TO_DYN or 6331 * #mhd_ENC_RESULT_INT_OK_ADD_TO_DYN on success 6332 */ 6333 static MHD_FN_PAR_NONNULL_ALL_ 6334 MHD_FN_PAR_INOUT_ (1) 6335 MHD_FN_PAR_OUT_ (4) 6336 MHD_FN_PAR_OUT_SIZE_ (6,5) MHD_FN_PAR_OUT_ (7) enum mhd_HpackEncResultInternal 6337 hpack_enc_pf_status (struct mhd_HpackEncContext *restrict hk_enc, 6338 uint_fast16_t code, 6339 enum mhd_HpackEncPFieldStatusPolicy enc_pol, 6340 char code_str[3], 6341 const size_t out_buff_size, 6342 uint8_t *restrict out_buff, 6343 size_t *restrict bytes_encoded) 6344 { 6345 mhd_constexpr dtbl_idx_ft pf_status_first_idx = 6346 mhd_HPACK_STBL_PF_STATUS_START_POS; 6347 mhd_constexpr dtbl_idx_ft pf_status_200_idx = pf_status_first_idx + 0u; 6348 mhd_constexpr dtbl_idx_ft pf_status_204_idx = pf_status_first_idx + 1u; 6349 mhd_constexpr dtbl_idx_ft pf_status_206_idx = pf_status_first_idx + 2u; 6350 mhd_constexpr dtbl_idx_ft pf_status_304_idx = pf_status_first_idx + 3u; 6351 mhd_constexpr dtbl_idx_ft pf_status_400_idx = pf_status_first_idx + 4u; 6352 mhd_constexpr dtbl_idx_ft pf_status_404_idx = pf_status_first_idx + 5u; 6353 mhd_constexpr dtbl_idx_ft pf_status_500_idx = pf_status_first_idx + 6u; 6354 struct mhd_BufferConst code_val; 6355 6356 mhd_assert (14u == pf_status_500_idx); 6357 6358 mhd_assert (0u != out_buff_size); 6359 6360 /* Check the enum values order */ 6361 // TODO: replace with static asserts 6362 mhd_assert (mhd_HPACK_ENC_PFS_POL_ALWAYS_NEW_IDX_IF_FIT < \ 6363 mhd_HPACK_ENC_PFS_POL_NORMAL); 6364 mhd_assert (mhd_HPACK_ENC_PFS_POL_NORMAL < \ 6365 mhd_HPACK_ENC_PFS_POL_AVOID_NEW_IDX); 6366 mhd_assert (mhd_HPACK_ENC_PFS_POL_AVOID_NEW_IDX < \ 6367 mhd_HPACK_ENC_PFS_POL_STATIC_IDX); 6368 mhd_assert (mhd_HPACK_ENC_PFS_POL_STATIC_IDX < \ 6369 mhd_HPACK_ENC_PFS_POL_NOT_INDEXED); 6370 mhd_assert (mhd_HPACK_ENC_PFS_POL_NOT_INDEXED < \ 6371 mhd_HPACK_ENC_PFS_POL_NEVER_W_NAME_IDX); 6372 mhd_assert (mhd_HPACK_ENC_PFS_POL_NEVER_W_NAME_IDX < \ 6373 mhd_HPACK_ENC_PFS_POL_NEVER_W_NAME_LIT_FORCED); 6374 mhd_assert (mhd_HPACK_ENC_PFS_POL_NEVER_W_NAME_LIT_FORCED < \ 6375 mhd_HPACK_ENC_PFS_POL_NEVER_W_NAME_LIT_NO_HUFFMAN); 6376 6377 6378 if ((mhd_HPACK_ENC_PFS_POL_NORMAL <= enc_pol) 6379 && (mhd_HPACK_ENC_PFS_POL_STATIC_IDX >= enc_pol)) 6380 { 6381 dtbl_idx_ft field_idx; 6382 switch (code) 6383 { 6384 case 200u: 6385 field_idx = pf_status_200_idx; 6386 break; 6387 case 204u: 6388 field_idx = pf_status_204_idx; 6389 break; 6390 case 206u: 6391 field_idx = pf_status_206_idx; 6392 break; 6393 case 304u: 6394 field_idx = pf_status_304_idx; 6395 break; 6396 case 400u: 6397 field_idx = pf_status_400_idx; 6398 break; 6399 case 404u: 6400 field_idx = pf_status_404_idx; 6401 break; 6402 case 500u: 6403 field_idx = pf_status_500_idx; 6404 break; 6405 default: 6406 field_idx = 0u; 6407 break; 6408 } 6409 6410 if (0u != field_idx) 6411 { 6412 if (! hpack_enc_field_indexed (field_idx, 6413 out_buff_size, 6414 out_buff, 6415 bytes_encoded)) 6416 return mhd_ENC_RESULT_INT_NO_SPACE; 6417 6418 return mhd_ENC_RESULT_INT_OK_NO_ADD_TO_DYN; 6419 } 6420 } 6421 6422 /* The pseudo-header is not in the static table or should not be added as an 6423 indexed field */ 6424 6425 /* Create a string representation of the code */ 6426 status_to_str (code, code_str); 6427 code_val.data = code_str; 6428 code_val.size = 3u; 6429 6430 if ((mhd_HPACK_ENC_PFS_POL_NORMAL <= enc_pol) 6431 && (mhd_HPACK_ENC_PFS_POL_AVOID_NEW_IDX >= enc_pol)) 6432 { 6433 const dtbl_idx_ft field_idx = 6434 mhd_dtbl_find_entry (hk_enc->dyn, 6435 pf_status_str.size, 6436 pf_status_str.data, 6437 3u, 6438 code_str); 6439 6440 if (0u != field_idx) 6441 { 6442 if (! hpack_enc_field_indexed (field_idx, 6443 out_buff_size, 6444 out_buff, 6445 bytes_encoded)) 6446 return mhd_ENC_RESULT_INT_NO_SPACE; 6447 6448 return mhd_ENC_RESULT_INT_OK_NO_ADD_TO_DYN; 6449 } 6450 } 6451 6452 /* The field is not in the tables or should not be added as an indexed 6453 field */ 6454 6455 /* Add the field literally */ 6456 6457 if (mhd_HPACK_ENC_PFS_POL_NEVER_W_NAME_IDX <= enc_pol) 6458 { 6459 /* Add field literally as "never indexed" */ 6460 const bool name_idx_stat_allowed = 6461 (mhd_HPACK_ENC_PFS_POL_NEVER_W_NAME_IDX == enc_pol); 6462 const bool huffman_allowed = 6463 (mhd_HPACK_ENC_PFS_POL_NEVER_W_NAME_LIT_NO_HUFFMAN > enc_pol); 6464 if (! hpack_enc_field_literal (hk_enc, 6465 &pf_status_str, 6466 name_idx_stat_allowed ? 6467 pf_status_first_idx : 0u, 6468 &code_val, 6469 mhd_HPACK_ENC_LIT_IDX_TYPE_NEVER_INDEXING, 6470 name_idx_stat_allowed, 6471 false, 6472 huffman_allowed, 6473 out_buff_size, 6474 out_buff, 6475 bytes_encoded)) 6476 return mhd_ENC_RESULT_INT_NO_SPACE; 6477 6478 return mhd_ENC_RESULT_INT_OK_NO_ADD_TO_DYN; 6479 } 6480 6481 if (mhd_HPACK_ENC_PFS_POL_AVOID_NEW_IDX <= enc_pol) 6482 { 6483 /* Adding to the tables is not allowed */ 6484 mhd_assert (mhd_HPACK_ENC_PFS_POL_NOT_INDEXED >= enc_pol); 6485 6486 if (! hpack_enc_field_literal (hk_enc, 6487 &pf_status_str, 6488 pf_status_first_idx, 6489 &code_val, 6490 mhd_HPACK_ENC_LIT_IDX_TYPE_NOT_INDEXING, 6491 true, 6492 false, 6493 true, 6494 out_buff_size, 6495 out_buff, 6496 bytes_encoded)) 6497 return mhd_ENC_RESULT_INT_NO_SPACE; 6498 6499 return mhd_ENC_RESULT_INT_OK_NO_ADD_TO_DYN; 6500 } 6501 6502 mhd_assert (mhd_HPACK_ENC_PFS_POL_ALWAYS_NEW_IDX_IF_FIT <= enc_pol); 6503 mhd_assert (mhd_HPACK_ENC_PFS_POL_NORMAL >= enc_pol); 6504 6505 if (1) /* For local scope */ 6506 { 6507 const bool add_to_idx = 6508 mhd_dtbl_check_entry_fit (hk_enc->dyn, 6509 pf_status_str.size, 6510 3u); 6511 6512 if (hpack_enc_field_literal (hk_enc, 6513 &pf_status_str, 6514 pf_status_first_idx, 6515 &code_val, 6516 add_to_idx ? 6517 mhd_HPACK_ENC_LIT_IDX_TYPE_INDEXING : 6518 mhd_HPACK_ENC_LIT_IDX_TYPE_NOT_INDEXING, 6519 true, 6520 false, 6521 true, 6522 out_buff_size, 6523 out_buff, 6524 bytes_encoded)) 6525 return add_to_idx ? 6526 mhd_ENC_RESULT_INT_OK_ADD_TO_DYN : 6527 mhd_ENC_RESULT_INT_OK_NO_ADD_TO_DYN; 6528 6529 } 6530 6531 return mhd_ENC_RESULT_INT_NO_SPACE; 6532 } 6533 6534 6535 MHD_INTERNAL MHD_FN_PAR_NONNULL_ALL_ 6536 MHD_FN_PAR_INOUT_ (1) 6537 MHD_FN_PAR_OUT_SIZE_ (5,4) MHD_FN_PAR_OUT_ (6) enum mhd_HpackEncResult 6538 mhd_hpack_enc_ph_status (struct mhd_HpackEncContext *restrict hk_enc, 6539 uint_fast16_t code, 6540 enum mhd_HpackEncPFieldStatusPolicy enc_pol, 6541 const size_t out_buff_size, 6542 uint8_t *restrict out_buff, 6543 size_t *restrict bytes_encoded) 6544 { 6545 char code_str[3] = ""; 6546 size_t pos; 6547 size_t pos_incr; 6548 enum mhd_HpackEncResultInternal enc_field_res; 6549 6550 mhd_assert (100u <= code); 6551 mhd_assert (699u >= code); 6552 6553 if (0u == out_buff_size) 6554 return mhd_HPACK_ENC_BUFFER_TOO_SMALL; 6555 6556 pos = 0u; 6557 6558 /* Add Dynamic Table Size Update message if needed */ 6559 if (! hpack_enc_check_dyn_size_update (hk_enc, 6560 out_buff_size - 1u, /* Reserve one byte for minimal field size */ 6561 out_buff, 6562 &pos_incr)) 6563 return mhd_HPACK_ENC_BUFFER_TOO_SMALL; 6564 6565 pos += pos_incr; 6566 mhd_assert (pos < out_buff_size); 6567 6568 enc_field_res = 6569 hpack_enc_pf_status (hk_enc, 6570 code, 6571 enc_pol, 6572 code_str, 6573 out_buff_size, 6574 out_buff, 6575 &pos_incr); 6576 6577 if (mhd_ENC_RESULT_INT_NO_SPACE == enc_field_res) 6578 return mhd_HPACK_ENC_BUFFER_TOO_SMALL; 6579 6580 pos += pos_incr; 6581 6582 /* Finally resize the dynamic table (if resize is pending) */ 6583 if (! hpack_enc_perform_dyn_size_update (hk_enc)) 6584 return mhd_HPACK_ENC_RES_ALLOC_ERR; 6585 6586 /* Add the field (if needed) only after dynamic table resizing (if any) */ 6587 if (mhd_ENC_RESULT_INT_OK_ADD_TO_DYN == enc_field_res) 6588 { 6589 mhd_assert ('1' <= code_str[0]); 6590 mhd_assert ('6' >= code_str[0]); 6591 mhd_assert ('0' == code_str[1]); 6592 mhd_dtbl_new_entry (hk_enc->dyn, 6593 pf_status_str.size, 6594 pf_status_str.data, 6595 sizeof(code_str) / sizeof(char), 6596 code_str); 6597 } 6598 else 6599 mhd_assert (mhd_ENC_RESULT_INT_OK_NO_ADD_TO_DYN == enc_field_res); 6600 6601 *bytes_encoded = pos; 6602 return mhd_HPACK_ENC_RES_OK; 6603 } 6604 6605 6606 /* ****** _____________ End of HPACK headers encoding ______________ ****** */ 6607 6608 #endif /* ! mhd_HPACK_TESTING_TABLES_ONLY || ! MHD_UNIT_TESTING */