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