varnish-cache/bin/varnishd/hpack/vhp_gen_hufdec.c
1
/*-
2
 * Copyright (c) 2016 Varnish Software AS
3
 * All rights reserved.
4
 *
5
 * Martin Blix Grydeland <martin@varnish-software.com>
6
 *
7
 * Redistribution and use in source and binary forms, with or without
8
 * modification, are permitted provided that the following conditions
9
 * are met:
10
 * 1. Redistributions of source code must retain the above copyright
11
 *    notice, this list of conditions and the following disclaimer.
12
 * 2. Redistributions in binary form must reproduce the above copyright
13
 *    notice, this list of conditions and the following disclaimer in the
14
 *    documentation and/or other materials provided with the distribution.
15
 *
16
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
17
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19
 * ARE DISCLAIMED.  IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
20
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
22
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26
 * SUCH DAMAGE.
27
 */
28
29
#include <stdlib.h>
30
#include <ctype.h>
31
#include <stdint.h>
32
#include <stdio.h>
33
#include <string.h>
34
#include <limits.h>
35
36
#include "vdef.h"
37
#include "vas.h"
38
39
static unsigned minlen = UINT_MAX;
40
static unsigned maxlen = 0;
41
static unsigned idx = 0;
42
43
static const struct {
44
        uint32_t        code;
45
        unsigned        blen;
46
        char            chr;
47
} huf[] = {
48
#define HPH(c, h, l) { h, l, (char)c },
49
#include "tbl/vhp_huffman.h"
50
};
51
52
#define HUF_LEN (sizeof huf / sizeof huf[0])
53
54
struct tbl;
55
56
struct cod {
57
        uint32_t                bits;
58
        unsigned                len;
59
        uint8_t                 chr;
60
        struct tbl              *next;
61
};
62
63
struct tbl {
64
        unsigned                mask;
65
        uint32_t                code;
66
        unsigned                masked;
67
        unsigned                n;
68
        unsigned                idx;
69
        unsigned                lvl;
70
        unsigned                p_idx;
71
        struct cod              e[];
72
};
73
74
static struct tbl *
75 58
tbl_new(unsigned mask)
76
{
77
        unsigned n;
78
        size_t size;
79
        struct tbl *tbl;
80
81 58
        assert(mask > 0);
82 58
        assert(mask <= 8);
83 58
        n = 1U << mask;
84 58
        size = sizeof (struct tbl) + n * sizeof (struct cod);
85 58
        tbl = calloc(1, size);
86 58
        AN(tbl);
87 58
        memset(tbl, 0, size);
88 58
        tbl->mask = mask;
89 58
        tbl->n = n;
90 58
        tbl->idx = idx;
91 58
        idx += n;
92 58
        return (tbl);
93
}
94
95
static void
96 1235
tbl_add(struct tbl *tbl, uint32_t code, unsigned codelen,
97
    uint32_t bits, unsigned len, char chr)
98
{
99
        uint32_t b;
100
        unsigned u;
101
102 1235
        AN(tbl);
103 1235
        assert(codelen > 0);
104 1235
        assert(codelen <= maxlen);
105 1235
        assert(len > 0);
106 1235
        assert(tbl->mask > 0);
107
108 1235
        if (len > tbl->mask) {
109
                /* Does not belong in this table */
110 979
                b = bits >> (len - tbl->mask);
111 979
                bits &= (1U << (len - tbl->mask)) - 1;
112 979
                if (tbl->e[b].next == NULL) {
113 57
                        tbl->e[b].len = tbl->mask;
114 57
                        tbl->e[b].next = tbl_new(len - tbl->mask);
115 57
                        AN(tbl->e[b].next);
116
117 57
                        tbl->e[b].next->masked = tbl->masked + tbl->mask;
118 57
                        tbl->e[b].next->code = code;
119 57
                        tbl->e[b].next->lvl = tbl->lvl + 1;
120 57
                        tbl->e[b].next->p_idx = tbl->idx + b;
121
                }
122 979
                AN(tbl->e[b].next);
123 1958
                tbl_add(tbl->e[b].next, code, codelen,
124 979
                    bits, len - tbl->mask, chr);
125 2214
                return;
126
        }
127
128 256
        bits = bits << (tbl->mask - len);
129 692
        for (u = 0; u < (1U << (tbl->mask - len)); u++) {
130 436
                b = bits | u;
131 436
                assert(b < tbl->n);
132 436
                AZ(tbl->e[b].len);
133 436
                AZ(tbl->e[b].next);
134 436
                tbl->e[b].len = len;
135 436
                tbl->e[b].chr = chr;
136
        }
137
}
138
139
static void
140 981
print_lsb(uint32_t c, int l)
141
{
142 981
        assert(l <= 32);
143
144 9412
        while (l > 0) {
145 7450
                if (c & (1U << (l - 1)))
146 5853
                        printf("1");
147
                else
148 1597
                        printf("0");
149 7450
                l--;
150
        }
151 981
}
152
153
static void
154 58
tbl_print(const struct tbl *tbl)
155
{
156
        unsigned u;
157
158 58
        printf("/* Table: lvl=%u p_idx=%u n=%u mask=%u masked=%u */\n",
159
            tbl->lvl, tbl->p_idx, tbl->n, tbl->mask, tbl->masked);
160 552
        for (u = 0; u < tbl->n; u++) {
161 494
                printf("/* %3u: ", tbl->idx + u);
162 494
                printf("%*s", maxlen - tbl->mask - tbl->masked, "");
163 494
                printf("%*s", tbl->mask - tbl->e[u].len, "");
164
165 494
                if (tbl->masked > 0) {
166 238
                        printf("(");
167 238
                        print_lsb(tbl->code >> tbl->mask, tbl->masked);
168 238
                        printf(") ");
169
                } else
170 256
                        printf("   ");
171 494
                if (tbl->e[u].len < tbl->mask) {
172 249
                        print_lsb(u >> (tbl->mask - tbl->e[u].len),
173 249
                            tbl->e[u].len);
174 249
                        printf(" (");
175 249
                        print_lsb(u, tbl->mask - tbl->e[u].len);
176 249
                        printf(")");
177
                } else {
178 245
                        assert(tbl->e[u].len == tbl->mask);
179 245
                        print_lsb(u, tbl->e[u].len);
180 245
                        printf("   ");
181
                }
182 494
                printf("%*s", 3 - (tbl->mask - tbl->e[u].len), "");
183 494
                printf(" */ ");
184
185 494
                if (tbl->e[u].next) {
186
                        /* Jump to next table */
187 57
                        assert(tbl->e[u].next->idx - (tbl->idx + u)
188
                            <= UINT8_MAX);
189 57
                        printf("{ .len = %u, .jump = %u },",
190
                            tbl->e[u].len,
191 57
                            tbl->e[u].next->idx - (tbl->idx + u));
192 57
                        printf(" /* Next: %u */", tbl->e[u].next->idx);
193 437
                } else if (tbl->e[u].len) {
194 436
                        printf("{ ");
195 436
                        printf(".len = %u", tbl->e[u].len);
196 436
                        printf(", .chr = (char)0x%02x", tbl->e[u].chr);
197 436
                        if (isgraph(tbl->e[u].chr))
198 271
                                printf(" /* '%c' */", tbl->e[u].chr);
199 436
                        if (u == 0)
200
                                /* First in table, set mask */
201 58
                                printf(", .mask = %u", tbl->mask);
202 436
                        printf(" },");
203
                } else
204 1
                        printf("{ .len = 0 }, /* invalid */");
205 494
                printf("\n");
206
        }
207
208 552
        for (u = 0; u < tbl->n; u++)
209 494
                if (tbl->e[u].next)
210 57
                        tbl_print(tbl->e[u].next);
211 58
}
212
213
int
214 1
main(int argc, const char **argv)
215
{
216
        struct tbl *top;
217
        unsigned u;
218
219
        (void)argc;
220
        (void)argv;
221
222 257
        for (u = 0; u < HUF_LEN; u++) {
223 256
                if (maxlen < huf[u].blen)
224 21
                        maxlen = huf[u].blen;
225 256
                if (minlen > huf[u].blen)
226 1
                        minlen = huf[u].blen;
227
        }
228
229 1
        top = tbl_new(8);
230 1
        AN(top);
231
232 257
        for (u = 0; u < HUF_LEN; u++)
233 256
                tbl_add(top, huf[u].code, huf[u].blen,
234 256
                    huf[u].code, huf[u].blen, huf[u].chr);
235
236 1
        printf("/*\n");
237 1
        printf(" * NB: This file is machine generated, DO NOT EDIT!\n");
238 1
        printf(" */\n\n");
239
240 1
        printf("#define HUFDEC_LEN %u\n", idx);
241 1
        printf("#define HUFDEC_MIN %u\n", minlen);
242 1
        printf("#define HUFDEC_MAX %u\n\n", maxlen);
243
244 1
        printf("static const struct {\n");
245 1
        printf("\tuint8_t\tmask;\n");
246 1
        printf("\tuint8_t\tlen;\n");
247 1
        printf("\tuint8_t\tjump;\n");
248 1
        printf("\tchar\tchr;\n");
249 1
        printf("} hufdec[HUFDEC_LEN] = {\n");
250 1
        tbl_print(top);
251 1
        printf("};\n");
252
253 1
        return (0);
254
}