1/* Generate table for fast Huffman decoding */ 2 3#include <inttypes.h> 4#include <stdint.h> 5#include <stdio.h> 6#include <stdlib.h> 7 8 9struct el 10{ 11 uint16_t code; 12 unsigned bits; 13 uint8_t out; 14}; 15 16static const struct el els[] = 17{ 18 { 0x0, 5, 48, }, 19 { 0x1, 5, 49, }, 20 { 0x2, 5, 50, }, 21 { 0x3, 5, 97, }, 22 { 0x4, 5, 99, }, 23 { 0x5, 5, 101, }, 24 { 0x6, 5, 105, }, 25 { 0x7, 5, 111, }, 26 { 0x8, 5, 115, }, 27 { 0x9, 5, 116, }, 28 { 0x14, 6, 32, }, 29 { 0x15, 6, 37, }, 30 { 0x16, 6, 45, }, 31 { 0x17, 6, 46, }, 32 { 0x18, 6, 47, }, 33 { 0x19, 6, 51, }, 34 { 0x1a, 6, 52, }, 35 { 0x1b, 6, 53, }, 36 { 0x1c, 6, 54, }, 37 { 0x1d, 6, 55, }, 38 { 0x1e, 6, 56, }, 39 { 0x1f, 6, 57, }, 40 { 0x20, 6, 61, }, 41 { 0x21, 6, 65, }, 42 { 0x22, 6, 95, }, 43 { 0x23, 6, 98, }, 44 { 0x24, 6, 100, }, 45 { 0x25, 6, 102, }, 46 { 0x26, 6, 103, }, 47 { 0x27, 6, 104, }, 48 { 0x28, 6, 108, }, 49 { 0x29, 6, 109, }, 50 { 0x2a, 6, 110, }, 51 { 0x2b, 6, 112, }, 52 { 0x2c, 6, 114, }, 53 { 0x2d, 6, 117, }, 54 { 0x5c, 7, 58, }, 55 { 0x5d, 7, 66, }, 56 { 0x5e, 7, 67, }, 57 { 0x5f, 7, 68, }, 58 { 0x60, 7, 69, }, 59 { 0x61, 7, 70, }, 60 { 0x62, 7, 71, }, 61 { 0x63, 7, 72, }, 62 { 0x64, 7, 73, }, 63 { 0x65, 7, 74, }, 64 { 0x66, 7, 75, }, 65 { 0x67, 7, 76, }, 66 { 0x68, 7, 77, }, 67 { 0x69, 7, 78, }, 68 { 0x6a, 7, 79, }, 69 { 0x6b, 7, 80, }, 70 { 0x6c, 7, 81, }, 71 { 0x6d, 7, 82, }, 72 { 0x6e, 7, 83, }, 73 { 0x6f, 7, 84, }, 74 { 0x70, 7, 85, }, 75 { 0x71, 7, 86, }, 76 { 0x72, 7, 87, }, 77 { 0x73, 7, 89, }, 78 { 0x74, 7, 106, }, 79 { 0x75, 7, 107, }, 80 { 0x76, 7, 113, }, 81 { 0x77, 7, 118, }, 82 { 0x78, 7, 119, }, 83 { 0x79, 7, 120, }, 84 { 0x7a, 7, 121, }, 85 { 0x7b, 7, 122, }, 86 { 0xf8, 8, 38, }, 87 { 0xf9, 8, 42, }, 88 { 0xfa, 8, 44, }, 89 { 0xfb, 8, 59, }, 90 { 0xfc, 8, 88, }, 91 { 0xfd, 8, 90, }, 92 { 0x3f8, 10, 33, }, 93 { 0x3f9, 10, 34, }, 94 { 0x3fa, 10, 40, }, 95 { 0x3fb, 10, 41, }, 96 { 0x3fc, 10, 63, }, 97 { 0x7fa, 11, 39, }, 98 { 0x7fb, 11, 43, }, 99 { 0x7fc, 11, 124, }, 100 { 0xffa, 12, 35, }, 101 { 0xffb, 12, 62, }, 102 { 0x1ff8, 13, 0, }, 103 { 0x1ff9, 13, 36, }, 104 { 0x1ffa, 13, 64, }, 105 { 0x1ffb, 13, 91, }, 106 { 0x1ffc, 13, 93, }, 107 { 0x1ffd, 13, 126, }, 108 { 0x3ffc, 14, 94, }, 109 { 0x3ffd, 14, 125, }, 110 { 0x7ffc, 15, 60, }, 111 { 0x7ffd, 15, 96, }, 112 { 0x7ffe, 15, 123, }, 113}; 114 115 116static void 117generate_entry (uint16_t idx) 118{ 119 unsigned int bits_left, n_outs; 120 const struct el *el; 121 uint8_t outs[3]; 122 123 bits_left = 16; 124 n_outs = 0; 125 do 126 { 127 for (el = els; el < els + sizeof(els) 128 / sizeof(els[0]) && el->bits <= bits_left; ++el) 129 if (el->code == (uint32_t) ((idx >> (bits_left - el->bits)) & ((1 << el->bits) - 1))) 130 break; 131 if (el >= els + sizeof(els) / sizeof(els[0]) || el->bits > bits_left) 132 break; 133 outs[n_outs++] = el->out; 134 bits_left -= el->bits; 135 } 136 while (bits_left >= 5 /* shortest code */); 137 138 printf("/* %"PRIu16" */ ", idx); 139 if (n_outs) 140 { 141 printf("{(%u<<2)|%u,{", 16 - bits_left, n_outs); 142 switch (n_outs) 143 { 144 case 3: 145 printf("%u,%u,%u", outs[0], outs[1], outs[2]); 146 break; 147 case 2: 148 printf("%u,%u,0", outs[0], outs[1]); 149 break; 150 case 1: 151 printf("%u,0,0", outs[0]); 152 break; 153 default: exit(EXIT_FAILURE); 154 } 155 printf("}}"); 156 } 157 else 158 printf("{0,0,0,0,}"); 159 printf(",\n"); 160} 161 162 163int 164main (void) 165{ 166 unsigned idx; 167 168 printf("static const struct hdec { uint8_t lens; uint8_t out[3]; } " 169 "hdecs[] =\n{\n"); 170 for (idx = 0; idx <= UINT16_MAX; ++idx) 171 generate_entry(idx); 172 printf("};\n"); 173 174 return 0; 175} 176