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