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