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 116
tbl_new(unsigned mask)
76
{
77
        unsigned n;
78
        size_t size;
79
        struct tbl *tbl;
80
81 116
        assert(mask > 0);
82 116
        assert(mask <= 8);
83 116
        n = 1U << mask;
84 116
        size = sizeof (struct tbl) + n * sizeof (struct cod);
85 116
        tbl = calloc(1, size);
86 116
        AN(tbl);
87 116
        memset(tbl, 0, size);
88 116
        tbl->mask = mask;
89 116
        tbl->n = n;
90 116
        tbl->idx = idx;
91 116
        idx += n;
92 116
        return (tbl);
93
}
94
95
static void
96 2470
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 2470
        AN(tbl);
103 2470
        assert(codelen > 0);
104 2470
        assert(codelen <= maxlen);
105 2470
        assert(len > 0);
106 2470
        assert(tbl->mask > 0);
107
108 2470
        if (len > tbl->mask) {
109
                /* Does not belong in this table */
110 1958
                b = bits >> (len - tbl->mask);
111 1958
                bits &= (1U << (len - tbl->mask)) - 1;
112 1958
                if (tbl->e[b].next == NULL) {
113 114
                        tbl->e[b].len = tbl->mask;
114 114
                        tbl->e[b].next = tbl_new(len - tbl->mask);
115 114
                        AN(tbl->e[b].next);
116
117 114
                        tbl->e[b].next->masked = tbl->masked + tbl->mask;
118 114
                        tbl->e[b].next->code = code;
119 114
                        tbl->e[b].next->lvl = tbl->lvl + 1;
120 114
                        tbl->e[b].next->p_idx = tbl->idx + b;
121
                }
122 1958
                AN(tbl->e[b].next);
123 3916
                tbl_add(tbl->e[b].next, code, codelen,
124 1958
                    bits, len - tbl->mask, chr);
125 1958
                return;
126
        }
127
128 512
        bits = bits << (tbl->mask - len);
129 1384
        for (u = 0; u < (1U << (tbl->mask - len)); u++) {
130 872
                b = bits | u;
131 872
                assert(b < tbl->n);
132 872
                AZ(tbl->e[b].len);
133 872
                AZ(tbl->e[b].next);
134 872
                tbl->e[b].len = len;
135 872
                tbl->e[b].chr = chr;
136
        }
137
}
138
139
static void
140 1962
print_lsb(uint32_t c, int l)
141
{
142 1962
        assert(l <= 32);
143
144 18824
        while (l > 0) {
145 14900
                if (c & (1U << (l - 1)))
146 11706
                        printf("1");
147
                else
148 3194
                        printf("0");
149 14900
                l--;
150
        }
151 1962
}
152
153
static void
154 116
tbl_print(const struct tbl *tbl)
155
{
156
        unsigned u;
157
158 116
        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 1104
        for (u = 0; u < tbl->n; u++) {
161 988
                printf("/* %3u: ", tbl->idx + u);
162 988
                printf("%*s", maxlen - tbl->mask - tbl->masked, "");
163 988
                printf("%*s", tbl->mask - tbl->e[u].len, "");
164
165 988
                if (tbl->masked > 0) {
166 476
                        printf("(");
167 476
                        print_lsb(tbl->code >> tbl->mask, tbl->masked);
168 476
                        printf(") ");
169
                } else
170 512
                        printf("   ");
171 988
                if (tbl->e[u].len < tbl->mask) {
172 498
                        print_lsb(u >> (tbl->mask - tbl->e[u].len),
173 498
                            tbl->e[u].len);
174 498
                        printf(" (");
175 498
                        print_lsb(u, tbl->mask - tbl->e[u].len);
176 498
                        printf(")");
177
                } else {
178 490
                        assert(tbl->e[u].len == tbl->mask);
179 490
                        print_lsb(u, tbl->e[u].len);
180 490
                        printf("   ");
181
                }
182 988
                printf("%*s", 3 - (tbl->mask - tbl->e[u].len), "");
183 988
                printf(" */ ");
184
185 988
                if (tbl->e[u].next) {
186
                        /* Jump to next table */
187 114
                        assert(tbl->e[u].next->idx - (tbl->idx + u)
188
                            <= UINT8_MAX);
189 114
                        printf("{ .len = %u, .jump = %u },",
190
                            tbl->e[u].len,
191 114
                            tbl->e[u].next->idx - (tbl->idx + u));
192 114
                        printf(" /* Next: %u */", tbl->e[u].next->idx);
193 874
                } else if (tbl->e[u].len) {
194 872
                        printf("{ ");
195 872
                        printf(".len = %u", tbl->e[u].len);
196 872
                        printf(", .chr = (char)0x%02x", tbl->e[u].chr);
197 872
                        if (isgraph(tbl->e[u].chr))
198 542
                                printf(" /* '%c' */", tbl->e[u].chr);
199 872
                        if (u == 0)
200
                                /* First in table, set mask */
201 116
                                printf(", .mask = %u", tbl->mask);
202 872
                        printf(" },");
203
                } else
204 2
                        printf("{ .len = 0 }, /* invalid */");
205 988
                printf("\n");
206
        }
207
208 1104
        for (u = 0; u < tbl->n; u++)
209 988
                if (tbl->e[u].next)
210 114
                        tbl_print(tbl->e[u].next);
211 116
}
212
213
int
214 2
main(int argc, const char **argv)
215
{
216
        struct tbl *top;
217
        unsigned u;
218
219
        (void)argc;
220
        (void)argv;
221
222 514
        for (u = 0; u < HUF_LEN; u++) {
223 512
                if (maxlen < huf[u].blen)
224 42
                        maxlen = huf[u].blen;
225 512
                if (minlen > huf[u].blen)
226 2
                        minlen = huf[u].blen;
227
        }
228
229 2
        top = tbl_new(8);
230 2
        AN(top);
231
232 514
        for (u = 0; u < HUF_LEN; u++)
233 512
                tbl_add(top, huf[u].code, huf[u].blen,
234 512
                    huf[u].code, huf[u].blen, huf[u].chr);
235
236 2
        printf("/*\n");
237 2
        printf(" * NB: This file is machine generated, DO NOT EDIT!\n");
238 2
        printf(" */\n\n");
239
240 2
        printf("#define HUFDEC_LEN %u\n", idx);
241 2
        printf("#define HUFDEC_MIN %u\n", minlen);
242 2
        printf("#define HUFDEC_MAX %u\n\n", maxlen);
243
244 2
        printf("static const struct {\n");
245 2
        printf("\tuint8_t\tmask;\n");
246 2
        printf("\tuint8_t\tlen;\n");
247 2
        printf("\tuint8_t\tjump;\n");
248 2
        printf("\tchar\tchr;\n");
249 2
        printf("} hufdec[HUFDEC_LEN] = {\n");
250 2
        tbl_print(top);
251 2
        printf("};\n");
252
253 2
        return (0);
254
}