1/* Generate table for fast Huffman encoding */ 2 3#include <inttypes.h> 4#include <stdint.h> 5#include <stdio.h> 6#include <stdlib.h> 7 8struct encode_el 9{ 10 uint32_t code; 11 int bits; 12}; 13 14static const struct encode_el encode_table[257] = 15{ 16 { 0x1ff8, 13}, // ( 0) 17 { 0x7fffd8, 23}, // ( 1) 18 { 0xfffffe2, 28}, // ( 2) 19 { 0xfffffe3, 28}, // ( 3) 20 { 0xfffffe4, 28}, // ( 4) 21 { 0xfffffe5, 28}, // ( 5) 22 { 0xfffffe6, 28}, // ( 6) 23 { 0xfffffe7, 28}, // ( 7) 24 { 0xfffffe8, 28}, // ( 8) 25 { 0xffffea, 24}, // ( 9) 26 { 0x3ffffffc, 30}, // ( 10) 27 { 0xfffffe9, 28}, // ( 11) 28 { 0xfffffea, 28}, // ( 12) 29 { 0x3ffffffd, 30}, // ( 13) 30 { 0xfffffeb, 28}, // ( 14) 31 { 0xfffffec, 28}, // ( 15) 32 { 0xfffffed, 28}, // ( 16) 33 { 0xfffffee, 28}, // ( 17) 34 { 0xfffffef, 28}, // ( 18) 35 { 0xffffff0, 28}, // ( 19) 36 { 0xffffff1, 28}, // ( 20) 37 { 0xffffff2, 28}, // ( 21) 38 { 0x3ffffffe, 30}, // ( 22) 39 { 0xffffff3, 28}, // ( 23) 40 { 0xffffff4, 28}, // ( 24) 41 { 0xffffff5, 28}, // ( 25) 42 { 0xffffff6, 28}, // ( 26) 43 { 0xffffff7, 28}, // ( 27) 44 { 0xffffff8, 28}, // ( 28) 45 { 0xffffff9, 28}, // ( 29) 46 { 0xffffffa, 28}, // ( 30) 47 { 0xffffffb, 28}, // ( 31) 48 { 0x14, 6}, // ' ' ( 32) 49 { 0x3f8, 10}, // '!' ( 33) 50 { 0x3f9, 10}, // '"' ( 34) 51 { 0xffa, 12}, // '#' ( 35) 52 { 0x1ff9, 13}, // '$' ( 36) 53 { 0x15, 6}, // '%' ( 37) 54 { 0xf8, 8}, // '&' ( 38) 55 { 0x7fa, 11}, // ''' ( 39) 56 { 0x3fa, 10}, // '(' ( 40) 57 { 0x3fb, 10}, // ')' ( 41) 58 { 0xf9, 8}, // '*' ( 42) 59 { 0x7fb, 11}, // '+' ( 43) 60 { 0xfa, 8}, // ',' ( 44) 61 { 0x16, 6}, // '-' ( 45) 62 { 0x17, 6}, // '.' ( 46) 63 { 0x18, 6}, // '/' ( 47) 64 { 0x0, 5}, // '0' ( 48) 65 { 0x1, 5}, // '1' ( 49) 66 { 0x2, 5}, // '2' ( 50) 67 { 0x19, 6}, // '3' ( 51) 68 { 0x1a, 6}, // '4' ( 52) 69 { 0x1b, 6}, // '5' ( 53) 70 { 0x1c, 6}, // '6' ( 54) 71 { 0x1d, 6}, // '7' ( 55) 72 { 0x1e, 6}, // '8' ( 56) 73 { 0x1f, 6}, // '9' ( 57) 74 { 0x5c, 7}, // ':' ( 58) 75 { 0xfb, 8}, // ';' ( 59) 76 { 0x7ffc, 15}, // '<' ( 60) 77 { 0x20, 6}, // '=' ( 61) 78 { 0xffb, 12}, // '>' ( 62) 79 { 0x3fc, 10}, // '?' ( 63) 80 { 0x1ffa, 13}, // '@' ( 64) 81 { 0x21, 6}, // 'A' ( 65) 82 { 0x5d, 7}, // 'B' ( 66) 83 { 0x5e, 7}, // 'C' ( 67) 84 { 0x5f, 7}, // 'D' ( 68) 85 { 0x60, 7}, // 'E' ( 69) 86 { 0x61, 7}, // 'F' ( 70) 87 { 0x62, 7}, // 'G' ( 71) 88 { 0x63, 7}, // 'H' ( 72) 89 { 0x64, 7}, // 'I' ( 73) 90 { 0x65, 7}, // 'J' ( 74) 91 { 0x66, 7}, // 'K' ( 75) 92 { 0x67, 7}, // 'L' ( 76) 93 { 0x68, 7}, // 'M' ( 77) 94 { 0x69, 7}, // 'N' ( 78) 95 { 0x6a, 7}, // 'O' ( 79) 96 { 0x6b, 7}, // 'P' ( 80) 97 { 0x6c, 7}, // 'Q' ( 81) 98 { 0x6d, 7}, // 'R' ( 82) 99 { 0x6e, 7}, // 'S' ( 83) 100 { 0x6f, 7}, // 'T' ( 84) 101 { 0x70, 7}, // 'U' ( 85) 102 { 0x71, 7}, // 'V' ( 86) 103 { 0x72, 7}, // 'W' ( 87) 104 { 0xfc, 8}, // 'X' ( 88) 105 { 0x73, 7}, // 'Y' ( 89) 106 { 0xfd, 8}, // 'Z' ( 90) 107 { 0x1ffb, 13}, // '[' ( 91) 108 { 0x7fff0, 19}, // '\' ( 92) 109 { 0x1ffc, 13}, // ']' ( 93) 110 { 0x3ffc, 14}, // '^' ( 94) 111 { 0x22, 6}, // '_' ( 95) 112 { 0x7ffd, 15}, // '`' ( 96) 113 { 0x3, 5}, // 'a' ( 97) 114 { 0x23, 6}, // 'b' ( 98) 115 { 0x4, 5}, // 'c' ( 99) 116 { 0x24, 6}, // 'd' (100) 117 { 0x5, 5}, // 'e' (101) 118 { 0x25, 6}, // 'f' (102) 119 { 0x26, 6}, // 'g' (103) 120 { 0x27, 6}, // 'h' (104) 121 { 0x6, 5}, // 'i' (105) 122 { 0x74, 7}, // 'j' (106) 123 { 0x75, 7}, // 'k' (107) 124 { 0x28, 6}, // 'l' (108) 125 { 0x29, 6}, // 'm' (109) 126 { 0x2a, 6}, // 'n' (110) 127 { 0x7, 5}, // 'o' (111) 128 { 0x2b, 6}, // 'p' (112) 129 { 0x76, 7}, // 'q' (113) 130 { 0x2c, 6}, // 'r' (114) 131 { 0x8, 5}, // 's' (115) 132 { 0x9, 5}, // 't' (116) 133 { 0x2d, 6}, // 'u' (117) 134 { 0x77, 7}, // 'v' (118) 135 { 0x78, 7}, // 'w' (119) 136 { 0x79, 7}, // 'x' (120) 137 { 0x7a, 7}, // 'y' (121) 138 { 0x7b, 7}, // 'z' (122) 139 { 0x7ffe, 15}, // '{' (123) 140 { 0x7fc, 11}, // '|' (124) 141 { 0x3ffd, 14}, // '}' (125) 142 { 0x1ffd, 13}, // '~' (126) 143 { 0xffffffc, 28}, // (127) 144 { 0xfffe6, 20}, // (128) 145 { 0x3fffd2, 22}, // (129) 146 { 0xfffe7, 20}, // (130) 147 { 0xfffe8, 20}, // (131) 148 { 0x3fffd3, 22}, // (132) 149 { 0x3fffd4, 22}, // (133) 150 { 0x3fffd5, 22}, // (134) 151 { 0x7fffd9, 23}, // (135) 152 { 0x3fffd6, 22}, // (136) 153 { 0x7fffda, 23}, // (137) 154 { 0x7fffdb, 23}, // (138) 155 { 0x7fffdc, 23}, // (139) 156 { 0x7fffdd, 23}, // (140) 157 { 0x7fffde, 23}, // (141) 158 { 0xffffeb, 24}, // (142) 159 { 0x7fffdf, 23}, // (143) 160 { 0xffffec, 24}, // (144) 161 { 0xffffed, 24}, // (145) 162 { 0x3fffd7, 22}, // (146) 163 { 0x7fffe0, 23}, // (147) 164 { 0xffffee, 24}, // (148) 165 { 0x7fffe1, 23}, // (149) 166 { 0x7fffe2, 23}, // (150) 167 { 0x7fffe3, 23}, // (151) 168 { 0x7fffe4, 23}, // (152) 169 { 0x1fffdc, 21}, // (153) 170 { 0x3fffd8, 22}, // (154) 171 { 0x7fffe5, 23}, // (155) 172 { 0x3fffd9, 22}, // (156) 173 { 0x7fffe6, 23}, // (157) 174 { 0x7fffe7, 23}, // (158) 175 { 0xffffef, 24}, // (159) 176 { 0x3fffda, 22}, // (160) 177 { 0x1fffdd, 21}, // (161) 178 { 0xfffe9, 20}, // (162) 179 { 0x3fffdb, 22}, // (163) 180 { 0x3fffdc, 22}, // (164) 181 { 0x7fffe8, 23}, // (165) 182 { 0x7fffe9, 23}, // (166) 183 { 0x1fffde, 21}, // (167) 184 { 0x7fffea, 23}, // (168) 185 { 0x3fffdd, 22}, // (169) 186 { 0x3fffde, 22}, // (170) 187 { 0xfffff0, 24}, // (171) 188 { 0x1fffdf, 21}, // (172) 189 { 0x3fffdf, 22}, // (173) 190 { 0x7fffeb, 23}, // (174) 191 { 0x7fffec, 23}, // (175) 192 { 0x1fffe0, 21}, // (176) 193 { 0x1fffe1, 21}, // (177) 194 { 0x3fffe0, 22}, // (178) 195 { 0x1fffe2, 21}, // (179) 196 { 0x7fffed, 23}, // (180) 197 { 0x3fffe1, 22}, // (181) 198 { 0x7fffee, 23}, // (182) 199 { 0x7fffef, 23}, // (183) 200 { 0xfffea, 20}, // (184) 201 { 0x3fffe2, 22}, // (185) 202 { 0x3fffe3, 22}, // (186) 203 { 0x3fffe4, 22}, // (187) 204 { 0x7ffff0, 23}, // (188) 205 { 0x3fffe5, 22}, // (189) 206 { 0x3fffe6, 22}, // (190) 207 { 0x7ffff1, 23}, // (191) 208 { 0x3ffffe0, 26}, // (192) 209 { 0x3ffffe1, 26}, // (193) 210 { 0xfffeb, 20}, // (194) 211 { 0x7fff1, 19}, // (195) 212 { 0x3fffe7, 22}, // (196) 213 { 0x7ffff2, 23}, // (197) 214 { 0x3fffe8, 22}, // (198) 215 { 0x1ffffec, 25}, // (199) 216 { 0x3ffffe2, 26}, // (200) 217 { 0x3ffffe3, 26}, // (201) 218 { 0x3ffffe4, 26}, // (202) 219 { 0x7ffffde, 27}, // (203) 220 { 0x7ffffdf, 27}, // (204) 221 { 0x3ffffe5, 26}, // (205) 222 { 0xfffff1, 24}, // (206) 223 { 0x1ffffed, 25}, // (207) 224 { 0x7fff2, 19}, // (208) 225 { 0x1fffe3, 21}, // (209) 226 { 0x3ffffe6, 26}, // (210) 227 { 0x7ffffe0, 27}, // (211) 228 { 0x7ffffe1, 27}, // (212) 229 { 0x3ffffe7, 26}, // (213) 230 { 0x7ffffe2, 27}, // (214) 231 { 0xfffff2, 24}, // (215) 232 { 0x1fffe4, 21}, // (216) 233 { 0x1fffe5, 21}, // (217) 234 { 0x3ffffe8, 26}, // (218) 235 { 0x3ffffe9, 26}, // (219) 236 { 0xffffffd, 28}, // (220) 237 { 0x7ffffe3, 27}, // (221) 238 { 0x7ffffe4, 27}, // (222) 239 { 0x7ffffe5, 27}, // (223) 240 { 0xfffec, 20}, // (224) 241 { 0xfffff3, 24}, // (225) 242 { 0xfffed, 20}, // (226) 243 { 0x1fffe6, 21}, // (227) 244 { 0x3fffe9, 22}, // (228) 245 { 0x1fffe7, 21}, // (229) 246 { 0x1fffe8, 21}, // (230) 247 { 0x7ffff3, 23}, // (231) 248 { 0x3fffea, 22}, // (232) 249 { 0x3fffeb, 22}, // (233) 250 { 0x1ffffee, 25}, // (234) 251 { 0x1ffffef, 25}, // (235) 252 { 0xfffff4, 24}, // (236) 253 { 0xfffff5, 24}, // (237) 254 { 0x3ffffea, 26}, // (238) 255 { 0x7ffff4, 23}, // (239) 256 { 0x3ffffeb, 26}, // (240) 257 { 0x7ffffe6, 27}, // (241) 258 { 0x3ffffec, 26}, // (242) 259 { 0x3ffffed, 26}, // (243) 260 { 0x7ffffe7, 27}, // (244) 261 { 0x7ffffe8, 27}, // (245) 262 { 0x7ffffe9, 27}, // (246) 263 { 0x7ffffea, 27}, // (247) 264 { 0x7ffffeb, 27}, // (248) 265 { 0xffffffe, 28}, // (249) 266 { 0x7ffffec, 27}, // (250) 267 { 0x7ffffed, 27}, // (251) 268 { 0x7ffffee, 27}, // (252) 269 { 0x7ffffef, 27}, // (253) 270 { 0x7fffff0, 27}, // (254) 271 { 0x3ffffee, 26}, // (255) 272 { 0x3fffffff, 30} // EOS (256) 273}; 274 275 276static void 277generate_entry (uint16_t idx) 278{ 279 uint8_t i, j; 280 281 j = idx >> 8; 282 i = idx; 283 284 if (encode_table[i].bits + encode_table[j].bits <= 32) 285 printf(" [I(%hhu,%hhu)] = {%u,0x%X},\n", 286 i, j, 287 encode_table[i].bits + encode_table[j].bits, 288 (encode_table[i].code << encode_table[j].bits) 289 | encode_table[j].code); 290 else 291 printf(" [I(%hhu,%hhu)] = {64,0},\n", i, j); 292} 293 294 295int 296main (void) 297{ 298 unsigned idx; 299 300 printf( 301 "#if __BYTE_ORDER == __LITTLE_ENDIAN\n" 302 "#define I(i,j) ((j<<8)|i)\n" 303 "#else\n" 304 "#define I(i,j) ((i<<8)|j)\n" 305 "#endif\n" 306 ); 307 printf("static const struct henc { unsigned lens; uint32_t code; } " 308 "hencs[] =\n{\n"); 309 for (idx = 0; idx <= UINT16_MAX; ++idx) 310 generate_entry(idx); 311 printf("};\n"); 312 printf("#undef I\n"); 313 314 return 0; 315} 316