h2_huffman_codec.c (48092B)
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/h2_huffman_codec.c 41 * @brief The implementation of HTTP/2 Huffman encoding and decoding functions 42 * @author Karlson2k (Evgeny Grin) 43 */ 44 45 46 #include "mhd_sys_options.h" 47 48 #include "sys_bool_type.h" 49 #include "sys_base_types.h" 50 #include <string.h> 51 52 #include "mhd_assert.h" 53 54 #include "mhd_constexpr.h" 55 #include "mhd_predict.h" 56 #include "mhd_align.h" 57 58 #include "mhd_bithelpers.h" 59 60 #include "h2_huffman_codec.h" 61 62 /** 63 * @def MHD_USE_CODE_HARDENING 64 * Enable additional code-hardening checks. 65 * 66 * Automatically enabled when unit-testing. 67 */ 68 #if defined(MHD_UNIT_TESTING) 69 # if ! defined(MHD_USE_CODE_HARDENING) 70 # define MHD_USE_CODE_HARDENING 1 71 # endif 72 #endif 73 74 75 /** 76 * HTTP/2 static Huffman codes from RFC 7541 77 * 78 * Index is the character value (0..255). 79 * The table values are codes that are left-algined (MSB-aligned) to 80 * the 32 bit value. 81 * See https://www.rfc-editor.org/rfc/rfc7541.html#appendix-B 82 * 83 * @note The table does not include EOS code. 84 */ 85 mhd_constexpr uint_least32_t mhd_h2huff_code_by_sym[256] = { 86 /* ( 0) */ 0xFFC00000u, 87 /* ( 1) */ 0xFFFFB000u, 88 /* ( 2) */ 0xFFFFFE20u, 89 /* ( 3) */ 0xFFFFFE30u, 90 /* ( 4) */ 0xFFFFFE40u, 91 /* ( 5) */ 0xFFFFFE50u, 92 /* ( 6) */ 0xFFFFFE60u, 93 /* ( 7) */ 0xFFFFFE70u, 94 /* ( 8) */ 0xFFFFFE80u, 95 /* ( 9) */ 0xFFFFEA00u, 96 /* ( 10) */ 0xFFFFFFF0u, 97 /* ( 11) */ 0xFFFFFE90u, 98 /* ( 12) */ 0xFFFFFEA0u, 99 /* ( 13) */ 0xFFFFFFF4u, 100 /* ( 14) */ 0xFFFFFEB0u, 101 /* ( 15) */ 0xFFFFFEC0u, 102 /* ( 16) */ 0xFFFFFED0u, 103 /* ( 17) */ 0xFFFFFEE0u, 104 /* ( 18) */ 0xFFFFFEF0u, 105 /* ( 19) */ 0xFFFFFF00u, 106 /* ( 20) */ 0xFFFFFF10u, 107 /* ( 21) */ 0xFFFFFF20u, 108 /* ( 22) */ 0xFFFFFFF8u, 109 /* ( 23) */ 0xFFFFFF30u, 110 /* ( 24) */ 0xFFFFFF40u, 111 /* ( 25) */ 0xFFFFFF50u, 112 /* ( 26) */ 0xFFFFFF60u, 113 /* ( 27) */ 0xFFFFFF70u, 114 /* ( 28) */ 0xFFFFFF80u, 115 /* ( 29) */ 0xFFFFFF90u, 116 /* ( 30) */ 0xFFFFFFA0u, 117 /* ( 31) */ 0xFFFFFFB0u, 118 /* ' ' ( 32) */ 0x50000000u, 119 /* '!' ( 33) */ 0xFE000000u, 120 /* '"' ( 34) */ 0xFE400000u, 121 /* '#' ( 35) */ 0xFFA00000u, 122 /* '$' ( 36) */ 0xFFC80000u, 123 /* '%' ( 37) */ 0x54000000u, 124 /* '&' ( 38) */ 0xF8000000u, 125 /* ''' ( 39) */ 0xFF400000u, 126 /* '(' ( 40) */ 0xFE800000u, 127 /* ')' ( 41) */ 0xFEC00000u, 128 /* '*' ( 42) */ 0xF9000000u, 129 /* '+' ( 43) */ 0xFF600000u, 130 /* ',' ( 44) */ 0xFA000000u, 131 /* '-' ( 45) */ 0x58000000u, 132 /* '.' ( 46) */ 0x5C000000u, 133 /* '/' ( 47) */ 0x60000000u, 134 /* '0' ( 48) */ 0x00000000u, 135 /* '1' ( 49) */ 0x08000000u, 136 /* '2' ( 50) */ 0x10000000u, 137 /* '3' ( 51) */ 0x64000000u, 138 /* '4' ( 52) */ 0x68000000u, 139 /* '5' ( 53) */ 0x6C000000u, 140 /* '6' ( 54) */ 0x70000000u, 141 /* '7' ( 55) */ 0x74000000u, 142 /* '8' ( 56) */ 0x78000000u, 143 /* '9' ( 57) */ 0x7C000000u, 144 /* ':' ( 58) */ 0xB8000000u, 145 /* ';' ( 59) */ 0xFB000000u, 146 /* '<' ( 60) */ 0xFFF80000u, 147 /* '=' ( 61) */ 0x80000000u, 148 /* '>' ( 62) */ 0xFFB00000u, 149 /* '?' ( 63) */ 0xFF000000u, 150 /* '@' ( 64) */ 0xFFD00000u, 151 /* 'A' ( 65) */ 0x84000000u, 152 /* 'B' ( 66) */ 0xBA000000u, 153 /* 'C' ( 67) */ 0xBC000000u, 154 /* 'D' ( 68) */ 0xBE000000u, 155 /* 'E' ( 69) */ 0xC0000000u, 156 /* 'F' ( 70) */ 0xC2000000u, 157 /* 'G' ( 71) */ 0xC4000000u, 158 /* 'H' ( 72) */ 0xC6000000u, 159 /* 'I' ( 73) */ 0xC8000000u, 160 /* 'J' ( 74) */ 0xCA000000u, 161 /* 'K' ( 75) */ 0xCC000000u, 162 /* 'L' ( 76) */ 0xCE000000u, 163 /* 'M' ( 77) */ 0xD0000000u, 164 /* 'N' ( 78) */ 0xD2000000u, 165 /* 'O' ( 79) */ 0xD4000000u, 166 /* 'P' ( 80) */ 0xD6000000u, 167 /* 'Q' ( 81) */ 0xD8000000u, 168 /* 'R' ( 82) */ 0xDA000000u, 169 /* 'S' ( 83) */ 0xDC000000u, 170 /* 'T' ( 84) */ 0xDE000000u, 171 /* 'U' ( 85) */ 0xE0000000u, 172 /* 'V' ( 86) */ 0xE2000000u, 173 /* 'W' ( 87) */ 0xE4000000u, 174 /* 'X' ( 88) */ 0xFC000000u, 175 /* 'Y' ( 89) */ 0xE6000000u, 176 /* 'Z' ( 90) */ 0xFD000000u, 177 /* '[' ( 91) */ 0xFFD80000u, 178 /* '\' ( 92) */ 0xFFFE0000u, 179 /* ']' ( 93) */ 0xFFE00000u, 180 /* '^' ( 94) */ 0xFFF00000u, 181 /* '_' ( 95) */ 0x88000000u, 182 /* '`' ( 96) */ 0xFFFA0000u, 183 /* 'a' ( 97) */ 0x18000000u, 184 /* 'b' ( 98) */ 0x8C000000u, 185 /* 'c' ( 99) */ 0x20000000u, 186 /* 'd' (100) */ 0x90000000u, 187 /* 'e' (101) */ 0x28000000u, 188 /* 'f' (102) */ 0x94000000u, 189 /* 'g' (103) */ 0x98000000u, 190 /* 'h' (104) */ 0x9C000000u, 191 /* 'i' (105) */ 0x30000000u, 192 /* 'j' (106) */ 0xE8000000u, 193 /* 'k' (107) */ 0xEA000000u, 194 /* 'l' (108) */ 0xA0000000u, 195 /* 'm' (109) */ 0xA4000000u, 196 /* 'n' (110) */ 0xA8000000u, 197 /* 'o' (111) */ 0x38000000u, 198 /* 'p' (112) */ 0xAC000000u, 199 /* 'q' (113) */ 0xEC000000u, 200 /* 'r' (114) */ 0xB0000000u, 201 /* 's' (115) */ 0x40000000u, 202 /* 't' (116) */ 0x48000000u, 203 /* 'u' (117) */ 0xB4000000u, 204 /* 'v' (118) */ 0xEE000000u, 205 /* 'w' (119) */ 0xF0000000u, 206 /* 'x' (120) */ 0xF2000000u, 207 /* 'y' (121) */ 0xF4000000u, 208 /* 'z' (122) */ 0xF6000000u, 209 /* '{' (123) */ 0xFFFC0000u, 210 /* '|' (124) */ 0xFF800000u, 211 /* '}' (125) */ 0xFFF40000u, 212 /* '~' (126) */ 0xFFE80000u, 213 /* (127) */ 0xFFFFFFC0u, 214 /* (128) */ 0xFFFE6000u, 215 /* (129) */ 0xFFFF4800u, 216 /* (130) */ 0xFFFE7000u, 217 /* (131) */ 0xFFFE8000u, 218 /* (132) */ 0xFFFF4C00u, 219 /* (133) */ 0xFFFF5000u, 220 /* (134) */ 0xFFFF5400u, 221 /* (135) */ 0xFFFFB200u, 222 /* (136) */ 0xFFFF5800u, 223 /* (137) */ 0xFFFFB400u, 224 /* (138) */ 0xFFFFB600u, 225 /* (139) */ 0xFFFFB800u, 226 /* (140) */ 0xFFFFBA00u, 227 /* (141) */ 0xFFFFBC00u, 228 /* (142) */ 0xFFFFEB00u, 229 /* (143) */ 0xFFFFBE00u, 230 /* (144) */ 0xFFFFEC00u, 231 /* (145) */ 0xFFFFED00u, 232 /* (146) */ 0xFFFF5C00u, 233 /* (147) */ 0xFFFFC000u, 234 /* (148) */ 0xFFFFEE00u, 235 /* (149) */ 0xFFFFC200u, 236 /* (150) */ 0xFFFFC400u, 237 /* (151) */ 0xFFFFC600u, 238 /* (152) */ 0xFFFFC800u, 239 /* (153) */ 0xFFFEE000u, 240 /* (154) */ 0xFFFF6000u, 241 /* (155) */ 0xFFFFCA00u, 242 /* (156) */ 0xFFFF6400u, 243 /* (157) */ 0xFFFFCC00u, 244 /* (158) */ 0xFFFFCE00u, 245 /* (159) */ 0xFFFFEF00u, 246 /* (160) */ 0xFFFF6800u, 247 /* (161) */ 0xFFFEE800u, 248 /* (162) */ 0xFFFE9000u, 249 /* (163) */ 0xFFFF6C00u, 250 /* (164) */ 0xFFFF7000u, 251 /* (165) */ 0xFFFFD000u, 252 /* (166) */ 0xFFFFD200u, 253 /* (167) */ 0xFFFEF000u, 254 /* (168) */ 0xFFFFD400u, 255 /* (169) */ 0xFFFF7400u, 256 /* (170) */ 0xFFFF7800u, 257 /* (171) */ 0xFFFFF000u, 258 /* (172) */ 0xFFFEF800u, 259 /* (173) */ 0xFFFF7C00u, 260 /* (174) */ 0xFFFFD600u, 261 /* (175) */ 0xFFFFD800u, 262 /* (176) */ 0xFFFF0000u, 263 /* (177) */ 0xFFFF0800u, 264 /* (178) */ 0xFFFF8000u, 265 /* (179) */ 0xFFFF1000u, 266 /* (180) */ 0xFFFFDA00u, 267 /* (181) */ 0xFFFF8400u, 268 /* (182) */ 0xFFFFDC00u, 269 /* (183) */ 0xFFFFDE00u, 270 /* (184) */ 0xFFFEA000u, 271 /* (185) */ 0xFFFF8800u, 272 /* (186) */ 0xFFFF8C00u, 273 /* (187) */ 0xFFFF9000u, 274 /* (188) */ 0xFFFFE000u, 275 /* (189) */ 0xFFFF9400u, 276 /* (190) */ 0xFFFF9800u, 277 /* (191) */ 0xFFFFE200u, 278 /* (192) */ 0xFFFFF800u, 279 /* (193) */ 0xFFFFF840u, 280 /* (194) */ 0xFFFEB000u, 281 /* (195) */ 0xFFFE2000u, 282 /* (196) */ 0xFFFF9C00u, 283 /* (197) */ 0xFFFFE400u, 284 /* (198) */ 0xFFFFA000u, 285 /* (199) */ 0xFFFFF600u, 286 /* (200) */ 0xFFFFF880u, 287 /* (201) */ 0xFFFFF8C0u, 288 /* (202) */ 0xFFFFF900u, 289 /* (203) */ 0xFFFFFBC0u, 290 /* (204) */ 0xFFFFFBE0u, 291 /* (205) */ 0xFFFFF940u, 292 /* (206) */ 0xFFFFF100u, 293 /* (207) */ 0xFFFFF680u, 294 /* (208) */ 0xFFFE4000u, 295 /* (209) */ 0xFFFF1800u, 296 /* (210) */ 0xFFFFF980u, 297 /* (211) */ 0xFFFFFC00u, 298 /* (212) */ 0xFFFFFC20u, 299 /* (213) */ 0xFFFFF9C0u, 300 /* (214) */ 0xFFFFFC40u, 301 /* (215) */ 0xFFFFF200u, 302 /* (216) */ 0xFFFF2000u, 303 /* (217) */ 0xFFFF2800u, 304 /* (218) */ 0xFFFFFA00u, 305 /* (219) */ 0xFFFFFA40u, 306 /* (220) */ 0xFFFFFFD0u, 307 /* (221) */ 0xFFFFFC60u, 308 /* (222) */ 0xFFFFFC80u, 309 /* (223) */ 0xFFFFFCA0u, 310 /* (224) */ 0xFFFEC000u, 311 /* (225) */ 0xFFFFF300u, 312 /* (226) */ 0xFFFED000u, 313 /* (227) */ 0xFFFF3000u, 314 /* (228) */ 0xFFFFA400u, 315 /* (229) */ 0xFFFF3800u, 316 /* (230) */ 0xFFFF4000u, 317 /* (231) */ 0xFFFFE600u, 318 /* (232) */ 0xFFFFA800u, 319 /* (233) */ 0xFFFFAC00u, 320 /* (234) */ 0xFFFFF700u, 321 /* (235) */ 0xFFFFF780u, 322 /* (236) */ 0xFFFFF400u, 323 /* (237) */ 0xFFFFF500u, 324 /* (238) */ 0xFFFFFA80u, 325 /* (239) */ 0xFFFFE800u, 326 /* (240) */ 0xFFFFFAC0u, 327 /* (241) */ 0xFFFFFCC0u, 328 /* (242) */ 0xFFFFFB00u, 329 /* (243) */ 0xFFFFFB40u, 330 /* (244) */ 0xFFFFFCE0u, 331 /* (245) */ 0xFFFFFD00u, 332 /* (246) */ 0xFFFFFD20u, 333 /* (247) */ 0xFFFFFD40u, 334 /* (248) */ 0xFFFFFD60u, 335 /* (249) */ 0xFFFFFFE0u, 336 /* (250) */ 0xFFFFFD80u, 337 /* (251) */ 0xFFFFFDA0u, 338 /* (252) */ 0xFFFFFDC0u, 339 /* (253) */ 0xFFFFFDE0u, 340 /* (254) */ 0xFFFFFE00u, 341 /* (255) */ 0xFFFFFB80u 342 }; 343 344 345 /** 346 * HTTP/2 static Huffman codes length in bits from RFC 7541 347 * See https://www.rfc-editor.org/rfc/rfc7541.html#appendix-B 348 * 349 * Index is the character value (0..255). 350 * The table values are lengths of the code in bits. 351 * See https://www.rfc-editor.org/rfc/rfc7541.html#appendix-B 352 * 353 * @note The table does not include EOS code. 354 */ 355 mhd_constexpr uint8_t mhd_h2huff_bitlen_by_sym[256] = { 356 /* ( 0) */ 13u, 357 /* ( 1) */ 23u, 358 /* ( 2) */ 28u, 359 /* ( 3) */ 28u, 360 /* ( 4) */ 28u, 361 /* ( 5) */ 28u, 362 /* ( 6) */ 28u, 363 /* ( 7) */ 28u, 364 /* ( 8) */ 28u, 365 /* ( 9) */ 24u, 366 /* ( 10) */ 30u, 367 /* ( 11) */ 28u, 368 /* ( 12) */ 28u, 369 /* ( 13) */ 30u, 370 /* ( 14) */ 28u, 371 /* ( 15) */ 28u, 372 /* ( 16) */ 28u, 373 /* ( 17) */ 28u, 374 /* ( 18) */ 28u, 375 /* ( 19) */ 28u, 376 /* ( 20) */ 28u, 377 /* ( 21) */ 28u, 378 /* ( 22) */ 30u, 379 /* ( 23) */ 28u, 380 /* ( 24) */ 28u, 381 /* ( 25) */ 28u, 382 /* ( 26) */ 28u, 383 /* ( 27) */ 28u, 384 /* ( 28) */ 28u, 385 /* ( 29) */ 28u, 386 /* ( 30) */ 28u, 387 /* ( 31) */ 28u, 388 /* ' ' ( 32) */ 6u, 389 /* '!' ( 33) */ 10u, 390 /* '"' ( 34) */ 10u, 391 /* '#' ( 35) */ 12u, 392 /* '$' ( 36) */ 13u, 393 /* '%' ( 37) */ 6u, 394 /* '&' ( 38) */ 8u, 395 /* ''' ( 39) */ 11u, 396 /* '(' ( 40) */ 10u, 397 /* ')' ( 41) */ 10u, 398 /* '*' ( 42) */ 8u, 399 /* '+' ( 43) */ 11u, 400 /* ',' ( 44) */ 8u, 401 /* '-' ( 45) */ 6u, 402 /* '.' ( 46) */ 6u, 403 /* '/' ( 47) */ 6u, 404 /* '0' ( 48) */ 5u, 405 /* '1' ( 49) */ 5u, 406 /* '2' ( 50) */ 5u, 407 /* '3' ( 51) */ 6u, 408 /* '4' ( 52) */ 6u, 409 /* '5' ( 53) */ 6u, 410 /* '6' ( 54) */ 6u, 411 /* '7' ( 55) */ 6u, 412 /* '8' ( 56) */ 6u, 413 /* '9' ( 57) */ 6u, 414 /* ':' ( 58) */ 7u, 415 /* ';' ( 59) */ 8u, 416 /* '<' ( 60) */ 15u, 417 /* '=' ( 61) */ 6u, 418 /* '>' ( 62) */ 12u, 419 /* '?' ( 63) */ 10u, 420 /* '@' ( 64) */ 13u, 421 /* 'A' ( 65) */ 6u, 422 /* 'B' ( 66) */ 7u, 423 /* 'C' ( 67) */ 7u, 424 /* 'D' ( 68) */ 7u, 425 /* 'E' ( 69) */ 7u, 426 /* 'F' ( 70) */ 7u, 427 /* 'G' ( 71) */ 7u, 428 /* 'H' ( 72) */ 7u, 429 /* 'I' ( 73) */ 7u, 430 /* 'J' ( 74) */ 7u, 431 /* 'K' ( 75) */ 7u, 432 /* 'L' ( 76) */ 7u, 433 /* 'M' ( 77) */ 7u, 434 /* 'N' ( 78) */ 7u, 435 /* 'O' ( 79) */ 7u, 436 /* 'P' ( 80) */ 7u, 437 /* 'Q' ( 81) */ 7u, 438 /* 'R' ( 82) */ 7u, 439 /* 'S' ( 83) */ 7u, 440 /* 'T' ( 84) */ 7u, 441 /* 'U' ( 85) */ 7u, 442 /* 'V' ( 86) */ 7u, 443 /* 'W' ( 87) */ 7u, 444 /* 'X' ( 88) */ 8u, 445 /* 'Y' ( 89) */ 7u, 446 /* 'Z' ( 90) */ 8u, 447 /* '[' ( 91) */ 13u, 448 /* '\' ( 92) */ 19u, 449 /* ']' ( 93) */ 13u, 450 /* '^' ( 94) */ 14u, 451 /* '_' ( 95) */ 6u, 452 /* '`' ( 96) */ 15u, 453 /* 'a' ( 97) */ 5u, 454 /* 'b' ( 98) */ 6u, 455 /* 'c' ( 99) */ 5u, 456 /* 'd' (100) */ 6u, 457 /* 'e' (101) */ 5u, 458 /* 'f' (102) */ 6u, 459 /* 'g' (103) */ 6u, 460 /* 'h' (104) */ 6u, 461 /* 'i' (105) */ 5u, 462 /* 'j' (106) */ 7u, 463 /* 'k' (107) */ 7u, 464 /* 'l' (108) */ 6u, 465 /* 'm' (109) */ 6u, 466 /* 'n' (110) */ 6u, 467 /* 'o' (111) */ 5u, 468 /* 'p' (112) */ 6u, 469 /* 'q' (113) */ 7u, 470 /* 'r' (114) */ 6u, 471 /* 's' (115) */ 5u, 472 /* 't' (116) */ 5u, 473 /* 'u' (117) */ 6u, 474 /* 'v' (118) */ 7u, 475 /* 'w' (119) */ 7u, 476 /* 'x' (120) */ 7u, 477 /* 'y' (121) */ 7u, 478 /* 'z' (122) */ 7u, 479 /* '{' (123) */ 15u, 480 /* '|' (124) */ 11u, 481 /* '}' (125) */ 14u, 482 /* '~' (126) */ 13u, 483 /* (127) */ 28u, 484 /* (128) */ 20u, 485 /* (129) */ 22u, 486 /* (130) */ 20u, 487 /* (131) */ 20u, 488 /* (132) */ 22u, 489 /* (133) */ 22u, 490 /* (134) */ 22u, 491 /* (135) */ 23u, 492 /* (136) */ 22u, 493 /* (137) */ 23u, 494 /* (138) */ 23u, 495 /* (139) */ 23u, 496 /* (140) */ 23u, 497 /* (141) */ 23u, 498 /* (142) */ 24u, 499 /* (143) */ 23u, 500 /* (144) */ 24u, 501 /* (145) */ 24u, 502 /* (146) */ 22u, 503 /* (147) */ 23u, 504 /* (148) */ 24u, 505 /* (149) */ 23u, 506 /* (150) */ 23u, 507 /* (151) */ 23u, 508 /* (152) */ 23u, 509 /* (153) */ 21u, 510 /* (154) */ 22u, 511 /* (155) */ 23u, 512 /* (156) */ 22u, 513 /* (157) */ 23u, 514 /* (158) */ 23u, 515 /* (159) */ 24u, 516 /* (160) */ 22u, 517 /* (161) */ 21u, 518 /* (162) */ 20u, 519 /* (163) */ 22u, 520 /* (164) */ 22u, 521 /* (165) */ 23u, 522 /* (166) */ 23u, 523 /* (167) */ 21u, 524 /* (168) */ 23u, 525 /* (169) */ 22u, 526 /* (170) */ 22u, 527 /* (171) */ 24u, 528 /* (172) */ 21u, 529 /* (173) */ 22u, 530 /* (174) */ 23u, 531 /* (175) */ 23u, 532 /* (176) */ 21u, 533 /* (177) */ 21u, 534 /* (178) */ 22u, 535 /* (179) */ 21u, 536 /* (180) */ 23u, 537 /* (181) */ 22u, 538 /* (182) */ 23u, 539 /* (183) */ 23u, 540 /* (184) */ 20u, 541 /* (185) */ 22u, 542 /* (186) */ 22u, 543 /* (187) */ 22u, 544 /* (188) */ 23u, 545 /* (189) */ 22u, 546 /* (190) */ 22u, 547 /* (191) */ 23u, 548 /* (192) */ 26u, 549 /* (193) */ 26u, 550 /* (194) */ 20u, 551 /* (195) */ 19u, 552 /* (196) */ 22u, 553 /* (197) */ 23u, 554 /* (198) */ 22u, 555 /* (199) */ 25u, 556 /* (200) */ 26u, 557 /* (201) */ 26u, 558 /* (202) */ 26u, 559 /* (203) */ 27u, 560 /* (204) */ 27u, 561 /* (205) */ 26u, 562 /* (206) */ 24u, 563 /* (207) */ 25u, 564 /* (208) */ 19u, 565 /* (209) */ 21u, 566 /* (210) */ 26u, 567 /* (211) */ 27u, 568 /* (212) */ 27u, 569 /* (213) */ 26u, 570 /* (214) */ 27u, 571 /* (215) */ 24u, 572 /* (216) */ 21u, 573 /* (217) */ 21u, 574 /* (218) */ 26u, 575 /* (219) */ 26u, 576 /* (220) */ 28u, 577 /* (221) */ 27u, 578 /* (222) */ 27u, 579 /* (223) */ 27u, 580 /* (224) */ 20u, 581 /* (225) */ 24u, 582 /* (226) */ 20u, 583 /* (227) */ 21u, 584 /* (228) */ 22u, 585 /* (229) */ 21u, 586 /* (230) */ 21u, 587 /* (231) */ 23u, 588 /* (232) */ 22u, 589 /* (233) */ 22u, 590 /* (234) */ 25u, 591 /* (235) */ 25u, 592 /* (236) */ 24u, 593 /* (237) */ 24u, 594 /* (238) */ 26u, 595 /* (239) */ 23u, 596 /* (240) */ 26u, 597 /* (241) */ 27u, 598 /* (242) */ 26u, 599 /* (243) */ 26u, 600 /* (244) */ 27u, 601 /* (245) */ 27u, 602 /* (246) */ 27u, 603 /* (247) */ 27u, 604 /* (248) */ 27u, 605 /* (249) */ 28u, 606 /* (250) */ 27u, 607 /* (251) */ 27u, 608 /* (252) */ 27u, 609 /* (253) */ 27u, 610 /* (254) */ 27u, 611 /* (255) */ 26u 612 }; 613 614 /** 615 * The symbol with the longest H2 Huffman code 616 */ 617 #define mhd_H2HUFF_LONGEST_CODE_SYM 22u 618 619 /** 620 * Get MSB-aligned 32-bit code and widen to @c uint_fast32_t, keeping it 621 * MSB-aligned on the wider type. 622 * @param idx Symbol (0..255) 623 */ 624 #define mhd_GET_H2HUFF_CODE_AS_UINTFAST32_ALG(idx) \ 625 (((uint_fast32_t) mhd_h2huff_code_by_sym[(idx)]) << \ 626 ((sizeof(uint_fast32_t) - 4u) * 8u)) 627 628 629 MHD_INTERNAL MHD_FN_PAR_NONNULL_ALL_ 630 MHD_FN_PAR_IN_SIZE_ (2,1) MHD_FN_PAR_OUT_SIZE_ (4,3) size_t 631 mhd_h2_huffman_encode (size_t str_len, 632 const char *restrict str, 633 size_t out_buf_size, 634 void *restrict out_buf) 635 { 636 mhd_constexpr uint_fast32_t uif32_all_ones = 637 (uint_fast32_t) (~((uint_fast32_t) 0u)); 638 /** The width of the @a acc_out. */ 639 mhd_constexpr uint_fast8_t acc_out_bits_width = 640 (uint_fast8_t) (sizeof(uint_fast32_t) * 8u); 641 uint8_t *const out_b = (uint8_t *) out_buf; 642 /** 32-bit (or wider) output accumulator. 643 Filled completely with encoded data and then the data is pushed to the 644 output buffer. */ 645 uint_fast32_t acc_out; 646 /** The number of MSB bits currently used in the @a acc_out */ 647 uint_fast8_t acc_out_used_bits; 648 size_t str_idx; 649 size_t out_idx; 650 651 #ifndef MHD_UNIT_TESTING 652 /* DO check the input for validity if NOT unit-testing */ 653 mhd_assert (0 != str_len); 654 mhd_assert (0 != out_buf_size); 655 #endif /* MHD_UNIT_TESTING */ 656 #ifdef BUILDING_MHD_LIB 657 mhd_assert (out_buf_size <= str_len); 658 #endif /* ! BUILDING_MHD_LIB */ 659 mhd_assert (out_buf_size <= ((~((size_t) (0))) - sizeof(acc_out))); 660 661 for (str_idx = 0u, out_idx = 0u, 662 acc_out = 0u, acc_out_used_bits = 0u; str_idx < str_len; ++str_idx) 663 { 664 const uint_fast8_t sym = (uint_fast8_t) (unsigned char) str[str_idx]; 665 const uint_fast32_t sym_code = 666 mhd_GET_H2HUFF_CODE_AS_UINTFAST32_ALG (sym); 667 const uint_fast8_t sym_code_bits = 668 (uint_fast8_t) mhd_h2huff_bitlen_by_sym[sym]; 669 670 mhd_assert (acc_out_bits_width > acc_out_used_bits); 671 mhd_assert (0 == (acc_out & (uif32_all_ones >> acc_out_used_bits))); 672 mhd_assert (5u <= sym_code_bits); 673 mhd_assert (30u >= sym_code_bits); 674 mhd_assert (0 == (sym_code & (uif32_all_ones >> sym_code_bits))); 675 676 acc_out |= (sym_code >> acc_out_used_bits); 677 acc_out_used_bits += sym_code_bits; 678 679 if (mhd_COND_PRED_FALSE_P (acc_out_used_bits >= acc_out_bits_width, 0.81)) 680 { /* The accumulator 'acc_out' must be written to the output buffer. */ 681 uint_fast32_t data_out; 682 size_t next_out_idx; 683 /* Number of bits in the 'sym_code' that does not fit into 'acc_out' */ 684 const uint_fast8_t sym_code_bits_left = 685 acc_out_used_bits - acc_out_bits_width; 686 /* The number of bits from 'sym_code' to be flushed to the output buffer */ 687 const uint_fast8_t sym_code_bits_to_flush = 688 sym_code_bits - sym_code_bits_left; 689 690 mhd_assert (29 >= sym_code_bits_left); 691 692 next_out_idx = out_idx + sizeof(acc_out); 693 if (mhd_COND_HARDLY_EVER (sizeof(acc_out) > next_out_idx)) 694 return 0; /* 'out_idx' overflow */ 695 if (mhd_COND_ALMOST_NEVER (out_buf_size < next_out_idx)) 696 return 0; /* Not enough space in the "out_buf" */ 697 698 mhd_PUT_UINTFAST32_BE (&data_out, acc_out); 699 memcpy (out_b + out_idx, &data_out, sizeof(data_out)); 700 out_idx = next_out_idx; 701 702 mhd_assert (0 != sym_code_bits_to_flush); 703 /* The shift performed in two steps to avoid branches and 704 undefined behaviour */ 705 mhd_assert (sym_code_bits >= sym_code_bits_to_flush); 706 acc_out = (sym_code << 1u) << (sym_code_bits_to_flush - 1u); 707 mhd_assert (0 == (acc_out & (uif32_all_ones >> sym_code_bits_left))); 708 acc_out_used_bits = sym_code_bits_left; 709 } 710 } 711 mhd_assert (acc_out_bits_width > acc_out_used_bits); 712 mhd_assert (0 == (acc_out & (uif32_all_ones >> acc_out_used_bits))); 713 714 if (mhd_COND_PRED_TRUE_P (0 != acc_out_used_bits, \ 715 (sizeof(uint_fast32_t) - 1.0) \ 716 / ((double) sizeof(uint_fast32_t)))) 717 { /* The accumulator 'acc_out' must be flushed to the output buffer. */ 718 const uint_fast8_t tail_bytes = 719 (uint_fast8_t) (acc_out_used_bits + 7u) >> 3u; 720 size_t next_out_idx; 721 uint_fast32_t data_out; 722 723 mhd_assert (sizeof(acc_out) >= tail_bytes); 724 mhd_assert (0 != tail_bytes); 725 726 next_out_idx = out_idx + tail_bytes; 727 if (mhd_COND_HARDLY_EVER (tail_bytes > next_out_idx)) 728 return 0; /* 'out_idx' overflow */ 729 if (mhd_COND_ALMOST_NEVER (out_buf_size < next_out_idx)) 730 return 0; /* Not enough space in the "out_buf" */ 731 732 acc_out |= uif32_all_ones >> acc_out_used_bits; 733 mhd_PUT_UINTFAST32_BE (&data_out, acc_out); 734 memcpy (out_b + out_idx, &data_out, tail_bytes); 735 out_idx = next_out_idx; 736 } 737 738 mhd_assert (out_buf_size >= out_idx); 739 740 return out_idx; 741 } 742 743 744 #ifndef NDEBUG 745 /** 746 * Track decoding table initialisation. 747 */ 748 static bool h2huff_decode_inited = false; 749 #endif 750 751 /** 752 * @def MHD_USE_HUFFMAN_DECODE_TABLES_TAIL_GAP 753 * Omit the unreachable tail part of some decode tables to save memory. 754 * 755 * When enabled, a decode table may be allocated with a shortened size that 756 * excludes entries that are never addressed by valid codes (given the 757 * prefix/next-prefix boundaries). 758 * 759 * If not defined then enabled for code hardening and for debug builds. 760 */ 761 #ifndef MHD_USE_HUFFMAN_DECODE_TABLES_TAIL_GAP 762 # if defined(MHD_USE_CODE_HARDENING) || ! defined(NDEBUG) 763 # define MHD_USE_HUFFMAN_DECODE_TABLES_TAIL_GAP 1 764 # else 765 # define MHD_USE_HUFFMAN_DECODE_TABLES_TAIL_GAP 0 766 # endif 767 #endif 768 769 770 /** 771 * @def HUFF_DTBL_SIZE_ROUNDED 772 * Full table size for a given index width @a twidth (no tail gap). 773 */ 774 #define HUFF_DTBL_SIZE_ROUNDED(twidth) (1u << (twidth)) 775 776 /** 777 * @def HUFF_DTBL_ENTRIES 778 * Number of actually used entries for a table with prefix width 779 * @a pwidth, table index width @a twidth, and the next table prefix width 780 * @a next_pwidth. 781 * 782 * This corresponds to the addressable range of codes for that table, 783 * excluding the part that belongs to the next table deeper in the chain. 784 */ 785 #define HUFF_DTBL_ENTRIES(pwidth,twidth,next_pwidth) \ 786 (HUFF_DTBL_SIZE_ROUNDED (twidth) \ 787 - (1u << ((pwidth) + (twidth) - (next_pwidth))) ) 788 789 /** 790 * @def HUFF_DTBL_SIZE 791 * Actual allocation size for the decode table (may include extra space). 792 */ 793 #if MHD_USE_HUFFMAN_DECODE_TABLES_TAIL_GAP 794 # define HUFF_DTBL_SIZE(pwidth,twidth,next_pwidth) \ 795 HUFF_DTBL_ENTRIES (pwidth,twidth,next_pwidth) 796 #else 797 # define HUFF_DTBL_SIZE(pwidth,twidth,next_pwidth) \ 798 HUFF_DTBL_SIZE_ROUNDED (twidth) 799 #endif 800 801 802 /* Decode table for prefix 0 bits, table width 8 bits. 803 Codes: 804 '0' ( 48) 00000xxx [ 5] 805 '1' ( 49) 00001xxx [ 5] 806 '2' ( 50) 00010xxx [ 5] 807 ... 808 ... 809 ';' ( 59) 11111011 [ 8] 810 'X' ( 88) 11111100 [ 8] 811 'Z' ( 90) 11111101 [ 8] 812 */ 813 static mhd_ALIGNED_64 814 uint_least16_t mhd_h2huff_SL_by_code_0p8c[HUFF_DTBL_SIZE (0, 8, 7)]; 815 816 /* Decode table for prefix 7 bits, table width 6 bits. 817 Codes: 818 '!' ( 33) 1111111 000xxx [10] 819 '"' ( 34) 1111111 001xxx [10] 820 '(' ( 40) 1111111 010xxx [10] 821 ... 822 ... 823 '[' ( 91) 1111111 111011 [13] 824 ']' ( 93) 1111111 111100 [13] 825 '~' (126) 1111111 111101 [13] 826 */ 827 static mhd_ALIGNED_64 828 uint_least16_t mhd_h2huff_SL_by_code_7p6c[HUFF_DTBL_SIZE (7, 6, 12)]; 829 830 /* Decode table for prefix 12 bits, table width 3 bits. 831 Codes: 832 '^' ( 94) 111111111111 00x [14] 833 '}' (125) 111111111111 01x [14] 834 '<' ( 60) 111111111111 100 [15] 835 '`' ( 96) 111111111111 101 [15] 836 '{' (123) 111111111111 110 [15] 837 */ 838 static mhd_ALIGNED_8 839 uint_least16_t mhd_h2huff_SL_by_code_12p3c[HUFF_DTBL_SIZE (12,3,15)]; 840 841 /* Decode table for prefix 15 bits, table width 7 bits. 842 Codes: 843 '\' ( 92) 111111111111111 0000xxx [19] 844 (195) 111111111111111 0001xxx [19] 845 (208) 111111111111111 0010xxx [19] 846 ... 847 ... 848 (169) 111111111111111 1011101 [22] 849 (170) 111111111111111 1011110 [22] 850 (173) 111111111111111 1011111 [22] 851 */ 852 static mhd_ALIGNED_16 853 uint_least16_t mhd_h2huff_SL_by_code_15p7c[HUFF_DTBL_SIZE (15,7,17)]; 854 855 /* Decode table for prefix 17 bits, table width 6 bits. 856 Codes: 857 (188) 1111111111111111111 0000xx [23] 858 (191) 1111111111111111111 0001xx [23] 859 (197) 1111111111111111111 0010xx [23] 860 ... 861 ... 862 (207) 1111111111111111111 101101 [25] 863 (234) 1111111111111111111 101110 [25] 864 (235) 1111111111111111111 101111 [25] 865 */ 866 static mhd_ALIGNED_16 867 uint_least16_t mhd_h2huff_SL_by_code_17p6c[HUFF_DTBL_SIZE (17,6,19)]; 868 869 /* Decode table for prefix 19 bits, table width 6 bits. 870 Codes: 871 (192) 111111111111111111111 00000x [26] 872 (193) 111111111111111111111 00001x [26] 873 (200) 111111111111111111111 00010x [26] 874 ... 875 ... 876 (251) 111111111111111111111 101101 [27] 877 (252) 111111111111111111111 101110 [27] 878 (253) 111111111111111111111 101111 [27] 879 */ 880 static mhd_ALIGNED_16 881 uint_least16_t mhd_h2huff_SL_by_code_19p6c[HUFF_DTBL_SIZE (19,6,21)]; 882 883 /* Decode table for prefix 21 bits, table width 6 bits. 884 Codes: 885 (192) 111111111111111111111 00000x [26] 886 (193) 111111111111111111111 00001x [26] 887 (200) 111111111111111111111 00010x [26] 888 ... 889 ... 890 (251) 111111111111111111111 101101 [27] 891 (252) 111111111111111111111 101110 [27] 892 (253) 111111111111111111111 101111 [27] 893 */ 894 static mhd_ALIGNED_16 895 uint_least16_t mhd_h2huff_SL_by_code_21p6c[HUFF_DTBL_SIZE (21,6,23)]; 896 897 /* Decode table for prefix 23 bits, table width 5 bits. 898 Codes: 899 (254) 11111111111111111111111 0000x [27] 900 ( 2) 11111111111111111111111 00010 [28] 901 ( 3) 11111111111111111111111 00011 [28] 902 ... 903 ... 904 (127) 11111111111111111111111 11100 [28] 905 (220) 11111111111111111111111 11101 [28] 906 (249) 11111111111111111111111 11110 [28] 907 */ 908 static mhd_ALIGNED_16 909 uint_least16_t mhd_h2huff_SL_by_code_23p5c[HUFF_DTBL_SIZE (23,5,28)]; 910 911 /* Decode table for prefix 28 bits, table width 2 bits. 912 Codes: 913 ( 10) 1111111111111111111111111111 00 [30] 914 ( 13) 1111111111111111111111111111 01 [30] 915 ( 22) 1111111111111111111111111111 10 [30] 916 */ 917 static mhd_ALIGNED_8 918 uint_least16_t mhd_h2huff_SL_by_code_28p2c[HUFF_DTBL_SIZE (28,2,30)]; 919 920 921 /** 922 * Populate entries for a single symbol within a particular decode table. 923 * 924 * A decode table covers a window of codes that share a fixed @a pbits prefix 925 * (all-ones in MSB-aligned representation) and differ in up to @a tbits 926 * following bits. This writes the appropriate range of entries for 927 * a particular @a code / @a codebits pair into @a table_to_fill. 928 * 929 * @param sym the symbol (0..255) 930 * @param code the MSB-aligned 32-bit code 931 * @param codebits the @a code length in bits (5..30) 932 * @param pbits the prefix width in bits (all-one MSB prefix) 933 * @param tbits the table-index width in bits 934 * @param next_pbits the next table prefix width 935 * @param[out] table_to_fill the pointer to the target decode table. 936 */ 937 MHD_FN_PAR_INOUT_ (7) MHD_FN_PAR_NONNULL_ALL_ static inline void 938 init_decode_table_entries_per_sym ( 939 const uint_fast8_t sym, 940 const uint_least32_t code, 941 const uint_fast8_t codebits, 942 const uint_fast8_t pbits, 943 const uint_fast8_t tbits, 944 const uint_fast8_t next_pbits, 945 uint_least16_t table_to_fill[ 946 MHD_FN_PAR_DYN_ARR_SIZE_ (HUFF_DTBL_SIZE (pbits,tbits,next_pbits))]) 947 { 948 mhd_constexpr uint_least32_t b32ones = 0xFFFFFFFFu; /**< 32 all-ones bits */ 949 const uint_least16_t sym_and_blen = 950 (uint_least16_t) (((uint_least16_t) codebits) << 8u | sym); 951 uint_least32_t i_tbl; 952 uint_least32_t i_tbl_end; 953 954 #ifdef NDEBUG 955 (void) next_pbits; /* Mute compiler warning */ 956 #endif /* NDEBUG */ 957 958 mhd_assert ((codebits <= 30u) && "The longest code is 30 bits"); 959 mhd_assert ((pbits < codebits) && \ 960 "The prefix must not be wider than the code"); 961 mhd_assert ((pbits + tbits) >= codebits && "The width of the code cannot " \ 962 "be larger than the total width of the prefix plus the " \ 963 "width of the table"); 964 mhd_assert (code == (code & b32ones) && \ 965 "The code cannot have bits higher than 32 bits"); 966 mhd_assert (0u == (code & (b32ones >> codebits)) && \ 967 "The unused part of the code must be zero"); 968 mhd_assert ((0u == pbits) || \ 969 ((b32ones >> (32u - pbits)) == (code >> (32u - pbits)) && \ 970 "The prefix bits in the code must be all set")); 971 mhd_assert ((b32ones >> (32u - codebits)) != (code >> (32u - codebits)) && \ 972 "The bits in the code after the prefix cannot be all set"); 973 974 i_tbl = ((code & (b32ones >> pbits)) >> (32u - (pbits + tbits))); 975 mhd_assert (HUFF_DTBL_ENTRIES (pbits, tbits, next_pbits) > i_tbl); 976 i_tbl_end = i_tbl + (1u << ((pbits + tbits) - codebits)) - 1u; 977 mhd_assert (i_tbl <= i_tbl_end); 978 mhd_assert (HUFF_DTBL_ENTRIES (pbits, tbits, next_pbits) > i_tbl_end); 979 980 do 981 { 982 mhd_assert (HUFF_DTBL_ENTRIES (pbits, tbits, next_pbits) > i_tbl); 983 mhd_assert (0 == table_to_fill[i_tbl] && \ 984 "No entry must be written twice"); 985 table_to_fill[i_tbl] = sym_and_blen; 986 } while (i_tbl++ < i_tbl_end); 987 } 988 989 990 /** 991 * Build one decode table for a particular (prefix, width, next-prefix) triple. 992 * 993 * @param pbits the number of bits in prefix, i.e. the static part common 994 * to all codes in the table (all-one bits) 995 * @param tbits the width of the table index in bits, i.e. the variable part 996 * of the code 997 * @param next_pbits the next table prefix width 998 * @param[out] table_to_fill the pointer to the table to fill 999 */ 1000 MHD_FN_PAR_INOUT_ (4) MHD_FN_PAR_NONNULL_ALL_ static void 1001 init_decode_table ( 1002 const uint_fast8_t pbits, 1003 const uint_fast8_t tbits, 1004 const uint_fast8_t next_pbits, 1005 uint_least16_t table_to_fill[ 1006 MHD_FN_PAR_DYN_ARR_SIZE_ (HUFF_DTBL_SIZE (pbits,tbits,next_pbits))]) 1007 { 1008 mhd_constexpr uint_least32_t b32ones = 0xFFFFFFFFu; /**< 32 all-ones bits */ 1009 uint_fast8_t sym; 1010 1011 mhd_assert (30 >= pbits + tbits); 1012 mhd_assert (5 <= pbits + tbits); 1013 mhd_assert (next_pbits > pbits); 1014 mhd_assert (next_pbits <= (pbits + tbits)); 1015 1016 memset (table_to_fill, 1017 0, 1018 HUFF_DTBL_SIZE (pbits,tbits,next_pbits) * sizeof(*table_to_fill)); /* Zero the table completely, including unused entries */ 1019 1020 sym = 0; 1021 do 1022 { 1023 uint_least32_t code = mhd_h2huff_code_by_sym[sym]; 1024 const uint_fast8_t codebits = mhd_h2huff_bitlen_by_sym[sym]; 1025 1026 mhd_assert ((code <= mhd_h2huff_code_by_sym[mhd_H2HUFF_LONGEST_CODE_SYM]) \ 1027 && "Huffman code must be less than or equal to the largest " \ 1028 "Huffman code in the table."); 1029 mhd_assert (codebits <= 30); 1030 mhd_assert (0 == (code & (b32ones >> codebits)) && \ 1031 "The unused part of the code must be zero"); 1032 1033 if ((0 != pbits) && 1034 (((b32ones << (32u - pbits)) & b32ones) > code)) 1035 continue; 1036 1037 if (((b32ones << (32u - next_pbits)) & b32ones) <= code) 1038 continue; 1039 1040 mhd_assert ((pbits + tbits) >= codebits); 1041 1042 init_decode_table_entries_per_sym (sym, 1043 code, 1044 codebits, 1045 pbits, 1046 tbits, 1047 next_pbits, 1048 table_to_fill); 1049 } while (255 > sym++); 1050 1051 #ifndef NDEBUG 1052 if (1) 1053 { /* Check the table */ 1054 uint_least32_t i; 1055 for (i = 0; 1056 i < HUFF_DTBL_ENTRIES (pbits,tbits,next_pbits); 1057 ++i) 1058 mhd_assert ((0u != table_to_fill[i]) && \ 1059 "All valid entries must be used"); 1060 # if MHD_USE_HUFFMAN_DECODE_TABLES_TAIL_GAP 1061 for (i = HUFF_DTBL_ENTRIES (pbits,tbits,next_pbits); 1062 i < HUFF_DTBL_SIZE (pbits,tbits,next_pbits); 1063 ++i) 1064 mhd_assert ((0u == table_to_fill[i]) && \ 1065 "All unused entries must be zero"); 1066 # endif /* MHD_USE_HUFFMAN_DECODE_TABLES_TAIL_GAP */ 1067 } 1068 #endif /* ! NDEBUG */ 1069 } 1070 1071 1072 MHD_INTERNAL void 1073 mhd_h2_huffman_init (void) 1074 { 1075 init_decode_table (0, 8, 7, mhd_h2huff_SL_by_code_0p8c); 1076 init_decode_table (7, 6, 12, mhd_h2huff_SL_by_code_7p6c); 1077 init_decode_table (12, 3, 15, mhd_h2huff_SL_by_code_12p3c); 1078 init_decode_table (15, 7, 17, mhd_h2huff_SL_by_code_15p7c); 1079 init_decode_table (17, 6, 19, mhd_h2huff_SL_by_code_17p6c); 1080 init_decode_table (19, 6, 21, mhd_h2huff_SL_by_code_19p6c); 1081 init_decode_table (21, 6, 23, mhd_h2huff_SL_by_code_21p6c); 1082 init_decode_table (23, 5, 28, mhd_h2huff_SL_by_code_23p5c); 1083 init_decode_table (28, 2, 30, mhd_h2huff_SL_by_code_28p2c); 1084 1085 #ifndef NDEBUG 1086 h2huff_decode_inited = true; 1087 #endif 1088 } 1089 1090 1091 /* 1092 * Additional decoding optimisation ideas. 1093 * Decode by two symbols at once (limited subset of the most used symbols). 1094 * To keep the decoding table small, decode only 5-7 bits codes, put symbols 1095 * value to the 'uint16_t' value, where 14 bits encode symbols value (all 1096 * symbols have high bits zero), zero value means missing second symbol; 1097 * top two bits encode length of the code pair: 10-13 bits length if first 1098 * code bit is zero or 11-14 bits if first code bit is zero; for missing 1099 * second symbol: 5-7 bits length of the symbol. 1100 */ 1101 1102 /** 1103 * @def mhd_HF_DEC64 1104 * Use 64-bit accumulator for decoding on 64-bit platforms. 1105 */ 1106 #if SIZEOF_UINT_FAST32_T >= 8 || SIZEOF_VOIDP >= 8 1107 # define mhd_HF_DEC64 1 1108 #endif 1109 1110 MHD_INTERNAL MHD_FN_PAR_NONNULL_ALL_ 1111 MHD_FN_PAR_IN_SIZE_ (2,1) MHD_FN_PAR_OUT_SIZE_ (4,3) size_t 1112 mhd_h2_huffman_decode (size_t encoded_size, 1113 const void *restrict encoded, 1114 size_t out_buf_size, 1115 char *restrict out_buf, 1116 enum mhd_H2HuffDecodeRes *restrict decode_result) 1117 { 1118 mhd_constexpr uint_least32_t b32ones = 0xFFFFFFFFu; /**< 32 all-ones bits */ 1119 #ifdef mhd_HF_DEC64 1120 mhd_constexpr uint_least64_t b64ones = 0xFFFFFFFFFFFFFFFFu; /**< 64 bits all set to one */ 1121 /** The width of the @a enc_chunk */ 1122 mhd_constexpr uint_fast8_t enc_chunk_width = 64u; 1123 /** The chunk of the encoded data to be decoded. */ 1124 uint_least64_t enc_chunk; 1125 /** The next bytes of the encoded data. 1126 Moved as needed to the @a enc_chunk by 32-bits portions. */ 1127 uint_least64_t enc_shadow; 1128 /**< The number of valid bits in the @a enc_shadow */ 1129 uint_fast8_t enc_shadow_bits; 1130 #else /* ! mhd_HF_DEC64 */ 1131 /** The width of the @a enc_chunk */ 1132 mhd_constexpr uint_fast8_t enc_chunk_width = 32u; 1133 /** The chunk of the encoded data to be decoded. */ 1134 uint_least32_t enc_chunk; 1135 /** The next bytes of the encoded data. 1136 Moved as needed to the @a enc_chunk by bits. */ 1137 uint_least32_t enc_chunk_next; 1138 #endif /* ! mhd_HF_DEC64 */ 1139 /** The total number of valid bits in @a enc_chunk and @a enc_chunk_next */ 1140 uint_fast8_t enc_chunk_bits; 1141 const uint8_t *const enc_b = (const uint8_t *) encoded; 1142 size_t enc_idx; 1143 size_t out_idx; 1144 1145 mhd_assert (h2huff_decode_inited); 1146 #ifndef MHD_UNIT_TESTING 1147 /* DO check the input for validity if NOT unit-testing */ 1148 mhd_assert (0 != encoded_size); 1149 mhd_assert (0 != out_buf_size); 1150 #endif /* ! MHD_UNIT_TESTING */ 1151 mhd_assert (out_buf_size <= ((~((size_t) (0))) - sizeof(uint_least32_t))); 1152 1153 /* Pre-load data */ 1154 if (1) 1155 { 1156 uint_least64_t data_in; 1157 size_t load_bytes; 1158 uint_least64_t enc_chunk64; 1159 data_in = 0; 1160 load_bytes = ((8u > encoded_size) ? encoded_size : 8u); 1161 memcpy (&data_in, enc_b, load_bytes); 1162 enc_chunk64 = mhd_GET_64BIT_BE (&data_in); 1163 #ifdef mhd_HF_DEC64 1164 enc_chunk = enc_chunk64; 1165 #else /* ! mhd_HF_DEC64 */ 1166 enc_chunk = ((uint_least32_t) (enc_chunk64 >> 32u)) & b32ones; 1167 enc_chunk_next = ((uint_least32_t) enc_chunk64) & b32ones; 1168 #endif /* ! mhd_HF_DEC64 */ 1169 enc_chunk_bits = (uint_fast8_t) (load_bytes << 3u); 1170 enc_idx = load_bytes; 1171 #ifdef mhd_HF_DEC64 1172 if (enc_idx < encoded_size) 1173 { 1174 data_in = 0; 1175 load_bytes = encoded_size - enc_idx; 1176 if (8 < load_bytes) 1177 load_bytes = 8u; 1178 memcpy (&data_in, enc_b + enc_idx, load_bytes); 1179 enc_shadow = mhd_GET_64BIT_BE (&data_in); 1180 enc_shadow_bits = (uint_fast8_t) (load_bytes << 3u); 1181 enc_idx += load_bytes; 1182 } 1183 else 1184 { 1185 enc_shadow = 0u; 1186 enc_shadow_bits = 0u; 1187 } 1188 #endif /* mhd_HF_DEC64 */ 1189 } 1190 out_idx = 0; 1191 1192 while (7 < enc_chunk_bits) 1193 { 1194 /* 32 bit MSB-aligned current decoding code */ 1195 const uint_least32_t cur_code = 1196 #ifdef mhd_HF_DEC64 1197 (uint_least32_t) (((uint_least32_t) (enc_chunk >> 32u)) & b32ones) 1198 #else /* ! mhd_HF_DEC64 */ 1199 enc_chunk 1200 #endif /* ! mhd_HF_DEC64 */ 1201 ; 1202 uint_fast8_t pbits; 1203 uint_fast8_t tbits; 1204 uint_fast8_t next_pbits; 1205 const uint_least16_t *dec_table; 1206 uint_least16_t sym_and_blen; 1207 uint8_t sym; 1208 uint_fast8_t sym_bits; 1209 uint_least32_t tbl_pos; 1210 1211 mhd_assert (encoded_size >= enc_idx); 1212 mhd_assert (64u >= enc_chunk_bits); 1213 1214 #ifdef mhd_HF_DEC64 1215 mhd_assert ((64u == enc_chunk_bits) || \ 1216 (0 == ((enc_chunk << enc_chunk_bits) & b64ones))); 1217 mhd_assert (enc_chunk == (enc_chunk & b64ones)); 1218 #else /* ! mhd_HF_DEC64 */ 1219 mhd_assert ((32u <= enc_chunk_bits) || \ 1220 (0 == ((enc_chunk << enc_chunk_bits) & b32ones))); 1221 mhd_assert ((32u > enc_chunk_bits) || (64u == enc_chunk_bits) || \ 1222 (0 == ((enc_chunk_next << (enc_chunk_bits - 32u)) & b32ones))); 1223 mhd_assert (enc_chunk == (enc_chunk & b32ones)); 1224 #endif /* ! mhd_HF_DEC64 */ 1225 1226 /** 1227 * Build an the starting code for the table as 32-bit MSB-aligned value. 1228 * @param pbits the table prefix width in bits. 1229 */ 1230 #define HUFF_DTBL_START(pbits) ((b32ones << (32u - (pbits)))&b32ones) 1231 1232 pbits = 0u; 1233 tbits = 8u; 1234 dec_table = mhd_h2huff_SL_by_code_0p8c; 1235 next_pbits = 7u; 1236 if (mhd_COND_PRED_FALSE_P (HUFF_DTBL_START (next_pbits) <= cur_code, 0.8)) 1237 { 1238 pbits = next_pbits; 1239 tbits = 6u; 1240 dec_table = mhd_h2huff_SL_by_code_7p6c; 1241 next_pbits = 12u; 1242 if (mhd_COND_RARELY (HUFF_DTBL_START (next_pbits) <= cur_code)) 1243 { 1244 pbits = next_pbits; 1245 tbits = 3u; 1246 dec_table = mhd_h2huff_SL_by_code_12p3c; 1247 next_pbits = 15u; 1248 if (HUFF_DTBL_START (next_pbits) <= cur_code) 1249 { 1250 pbits = next_pbits; 1251 tbits = 7u; 1252 dec_table = mhd_h2huff_SL_by_code_15p7c; 1253 next_pbits = 17u; 1254 if (HUFF_DTBL_START (next_pbits) <= cur_code) 1255 { 1256 pbits = next_pbits; 1257 tbits = 6u; 1258 dec_table = mhd_h2huff_SL_by_code_17p6c; 1259 next_pbits = 19u; 1260 if (HUFF_DTBL_START (next_pbits) <= cur_code) 1261 { 1262 pbits = next_pbits; 1263 tbits = 6u; 1264 dec_table = mhd_h2huff_SL_by_code_19p6c; 1265 next_pbits = 21u; 1266 if (HUFF_DTBL_START (next_pbits) <= cur_code) 1267 { 1268 pbits = next_pbits; 1269 tbits = 6u; 1270 dec_table = mhd_h2huff_SL_by_code_21p6c; 1271 next_pbits = 23u; 1272 if (HUFF_DTBL_START (next_pbits) <= cur_code) 1273 { 1274 pbits = next_pbits; 1275 tbits = 5u; 1276 dec_table = mhd_h2huff_SL_by_code_23p5c; 1277 next_pbits = 28u; 1278 if (HUFF_DTBL_START (next_pbits) <= cur_code) 1279 { 1280 pbits = next_pbits; 1281 tbits = 2u; 1282 dec_table = mhd_h2huff_SL_by_code_28p2c; 1283 next_pbits = 30u; 1284 if (HUFF_DTBL_START (next_pbits) <= cur_code) 1285 { 1286 *decode_result = MHD_H2_HUFF_DEC_RES_BROKEN_DATA; 1287 return 0; 1288 } 1289 } 1290 } 1291 } 1292 } 1293 } 1294 } 1295 } 1296 #ifndef MHD_FAVOR_SMALL_CODE 1297 tbl_pos = ((cur_code << pbits) & b32ones) >> (32u - tbits); 1298 #endif /* ! MHD_FAVOR_SMALL_CODE */ 1299 } 1300 #ifndef MHD_FAVOR_SMALL_CODE 1301 else 1302 { 1303 tbl_pos = cur_code >> (32u - tbits); 1304 (void) pbits; 1305 } 1306 #endif /* ! MHD_FAVOR_SMALL_CODE */ 1307 1308 #undef HUFF_DTBL_START 1309 1310 mhd_assert (5u <= (pbits + tbits)); 1311 mhd_assert (30u >= (pbits + tbits)); 1312 1313 #ifdef MHD_FAVOR_SMALL_CODE 1314 tbl_pos = ((cur_code << pbits) & b32ones) >> (32u - tbits); 1315 #endif /* MHD_FAVOR_SMALL_CODE */ 1316 1317 mhd_assert (HUFF_DTBL_ENTRIES (pbits, tbits, next_pbits) > tbl_pos); 1318 sym_and_blen = dec_table[tbl_pos]; 1319 1320 mhd_assert (0u != sym_and_blen); 1321 1322 sym = (uint8_t) (sym_and_blen & 0xFFu); 1323 sym_bits = (uint_fast8_t) (sym_and_blen >> 8u); 1324 1325 mhd_assert (0u != sym_bits); 1326 mhd_assert (5u <= sym_bits); 1327 mhd_assert (30u >= sym_bits); 1328 mhd_assert (pbits <= sym_bits); 1329 mhd_assert ((pbits + tbits) >= sym_bits); 1330 mhd_assert (mhd_h2huff_bitlen_by_sym[sym] == sym_bits); 1331 1332 if (mhd_COND_VERY_RARELY (enc_chunk_bits < sym_bits)) 1333 { 1334 *decode_result = MHD_H2_HUFF_DEC_RES_BROKEN_DATA; 1335 return 0; 1336 } 1337 enc_chunk_bits -= sym_bits; 1338 #ifdef mhd_HF_DEC64 1339 enc_chunk = (enc_chunk << sym_bits) & b64ones; 1340 #else /* ! mhd_HF_DEC64 */ 1341 enc_chunk = ((enc_chunk << sym_bits) & b32ones); 1342 enc_chunk |= enc_chunk_next >> (32u - sym_bits); 1343 enc_chunk_next = ((enc_chunk_next << sym_bits) & b32ones); 1344 #endif /* ! mhd_HF_DEC64 */ 1345 1346 if (mhd_COND_VERY_RARELY (out_buf_size == out_idx)) 1347 { 1348 *decode_result = MHD_H2_HUFF_DEC_RES_NO_SPACE; 1349 return 0; 1350 } 1351 out_buf[out_idx++] = (char) sym; 1352 1353 if (mhd_COND_PRED_FALSE_P (32u > enc_chunk_bits, 0.84)) 1354 { 1355 /* Load new chunk of encoded data */ 1356 #ifdef mhd_HF_DEC64 1357 if (enc_shadow_bits != 0) 1358 { 1359 const uint_fast8_t free_bits = (uint_fast8_t) (64u - enc_chunk_bits); 1360 const uint_fast8_t move_bits = 1361 (enc_shadow_bits > free_bits) ? free_bits : enc_shadow_bits; 1362 mhd_assert (0u != enc_chunk_bits && \ 1363 "A single symbol cannot be more than 30 bits. If on " \ 1364 "the previous step 'enc_chunk' has not been filled to " \ 1365 "more than 32 bits it means that 'enc_shadow' is " \ 1366 "already empty."); 1367 mhd_assert (0 != move_bits); 1368 1369 enc_chunk |= enc_shadow >> enc_chunk_bits; 1370 enc_chunk_bits += move_bits; 1371 enc_shadow <<= move_bits; 1372 enc_shadow_bits -= move_bits; 1373 mhd_assert ((64u == enc_chunk_bits) || \ 1374 (0 == ((enc_chunk << enc_chunk_bits) & b64ones))); 1375 } 1376 if ((0u == enc_shadow_bits) \ 1377 && (encoded_size > enc_idx)) 1378 { 1379 uint_least64_t data_in; 1380 size_t load_bytes; 1381 1382 data_in = 0; 1383 load_bytes = encoded_size - enc_idx; 1384 if (8u < load_bytes) 1385 load_bytes = 8u; 1386 memcpy (&data_in, enc_b + enc_idx, load_bytes); 1387 enc_idx += load_bytes; 1388 enc_shadow = mhd_GET_64BIT_BE (&data_in); 1389 enc_shadow_bits = (uint_fast8_t) (load_bytes << 3u); 1390 1391 if (mhd_COND_RARELY (32u > enc_chunk_bits)) 1392 { 1393 const uint_fast8_t free_bits = (uint_fast8_t) (64u - enc_chunk_bits); 1394 const uint_fast8_t use_bits = 1395 (enc_shadow_bits > free_bits) ? free_bits : enc_shadow_bits; 1396 1397 mhd_assert (0u != enc_chunk_bits); 1398 enc_chunk |= enc_shadow >> enc_chunk_bits; 1399 enc_chunk_bits += use_bits; 1400 enc_shadow <<= use_bits; 1401 enc_shadow_bits -= use_bits; 1402 } 1403 } 1404 #else /* ! mhd_HF_DEC64 */ 1405 if (encoded_size > enc_idx) 1406 { 1407 uint_least32_t data_in; 1408 size_t load_bytes; 1409 uint_least32_t enc_data_load; 1410 1411 mhd_assert (0u != enc_chunk_bits && \ 1412 "A single symbol cannot be more than 30 bits. If more " \ 1413 "data to decode is present, then buffer would be filled " \ 1414 "on the previous step."); 1415 mhd_assert (0 == (enc_chunk & (b32ones >> enc_chunk_bits))); 1416 mhd_assert (0 == enc_chunk_next); 1417 1418 data_in = 0; 1419 load_bytes = (encoded_size - enc_idx); 1420 if (4 < load_bytes) 1421 load_bytes = 4; 1422 memcpy (&data_in, enc_b + enc_idx, load_bytes); 1423 enc_idx += load_bytes; 1424 enc_data_load = mhd_GET_32BIT_BE (&data_in); 1425 1426 enc_chunk |= ((enc_data_load >> enc_chunk_bits) & b32ones); 1427 enc_chunk_next = ((enc_data_load << (32u - enc_chunk_bits)) & b32ones); 1428 enc_chunk_bits += (uint_fast8_t) (load_bytes << 3u); 1429 } 1430 #endif /* mhd_HF_DEC64 */ 1431 } 1432 } 1433 1434 if (0 != enc_chunk_bits) 1435 { /* Decode the last portion of the encoded data */ 1436 1437 /** The last portion of the data one-padded on the right */ 1438 const uint_least8_t last_byte = 1439 (uint_least8_t) ((enc_chunk >> (enc_chunk_width - 8u)) 1440 | (0xFFu >> enc_chunk_bits)); 1441 mhd_assert (7 >= enc_chunk_bits); 1442 1443 if (0xFFu != last_byte) 1444 { /* The encoded data is not pure EOS */ 1445 uint_least16_t sym_and_blen; 1446 uint8_t sym; 1447 uint_fast8_t sym_bits; 1448 1449 sym_and_blen = mhd_h2huff_SL_by_code_0p8c[last_byte]; 1450 1451 mhd_assert (0u != sym_and_blen); 1452 1453 sym = (uint8_t) (sym_and_blen & 0xFFu); 1454 sym_bits = (uint_fast8_t) (sym_and_blen >> 8u); 1455 mhd_assert (sym_bits <= 8u); 1456 1457 if (mhd_COND_VERY_RARELY (enc_chunk_bits < sym_bits)) 1458 { 1459 *decode_result = MHD_H2_HUFF_DEC_RES_BROKEN_DATA; 1460 return 0; 1461 } 1462 1463 if (sym_bits != enc_chunk_bits) 1464 { /* Check whether the tail is EOS */ 1465 if (mhd_COND_VERY_RARELY (((uint_least8_t) (0xFFu >> sym_bits)) != 1466 (last_byte 1467 & (uint_least8_t) (0xFFu >> sym_bits)))) 1468 { 1469 *decode_result = MHD_H2_HUFF_DEC_RES_BROKEN_DATA; 1470 return 0; 1471 } 1472 } 1473 1474 if (mhd_COND_VERY_RARELY (out_buf_size == out_idx)) 1475 { 1476 *decode_result = MHD_H2_HUFF_DEC_RES_NO_SPACE; 1477 return 0; 1478 } 1479 out_buf[out_idx++] = (char) sym; 1480 } 1481 } 1482 *decode_result = MHD_H2_HUFF_DEC_RES_OK; 1483 return out_idx; 1484 }