GCOV - Varnish Cache


/*-
 * Copyright (c) 2016 Varnish Software AS
 * All rights reserved.
 *
 * Martin Blix Grydeland <martin@varnish-software.com>
 *
 * SPDX-License-Identifier: BSD-2-Clause
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include "config.h"

#include <stdlib.h>
#include <ctype.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <limits.h>

#include "vdef.h"
#include "vas.h"

static unsigned minlen = UINT_MAX;
static unsigned maxlen = 0;
static unsigned idx = 0;

static const struct {
        uint32_t        code;
        unsigned        blen;
        char            chr;
} huf[] = {
#define HPH(c, h, l) { h, l, (char)c },
#include "tbl/vhp_huffman.h"
};

#define HUF_LEN (sizeof huf / sizeof huf[0])

struct tbl;

struct cod {
        uint32_t                bits;
        unsigned                len;
        uint8_t                 chr;
        struct tbl              *next;
};

struct tbl {
        unsigned                mask;
        uint32_t                code;
        unsigned                masked;
        unsigned                n;
        unsigned                idx;
        unsigned                lvl;
        unsigned                p_idx;
        struct cod              e[];
};

static struct tbl *
tbl_new(unsigned mask)
{
        unsigned n;
        size_t size;
        struct tbl *tbl;

        assert(mask > 0);
        assert(mask <= 8);
        n = 1U << mask;
        size = sizeof (struct tbl) + n * sizeof (struct cod);
        tbl = calloc(1, size);
        AN(tbl);
        memset(tbl, 0, size);
        tbl->mask = mask;
        tbl->n = n;
        tbl->idx = idx;
        idx += n;
        return (tbl);
}

static void
tbl_free(struct tbl* table)
{
        for (unsigned i = 0; i < table->n; i++) {
                if (table->e[i].next != NULL)
                        tbl_free(table->e[i].next);
        }
        free(table);
}

static void
tbl_add(struct tbl *tbl, uint32_t code, unsigned codelen,
    uint32_t bits, unsigned len, char chr)
{
        uint32_t b;
        unsigned u;

        AN(tbl);
        assert(codelen > 0);
        assert(codelen <= maxlen);
        assert(len > 0);
        assert(tbl->mask > 0);

        if (len > tbl->mask) {
                /* Does not belong in this table */
                b = bits >> (len - tbl->mask);
                bits &= (1U << (len - tbl->mask)) - 1;
                if (tbl->e[b].next == NULL) {
                        tbl->e[b].len = tbl->mask;
                        tbl->e[b].next = tbl_new(len - tbl->mask);
                        AN(tbl->e[b].next);

                        tbl->e[b].next->masked = tbl->masked + tbl->mask;
                        tbl->e[b].next->code = code;
                        tbl->e[b].next->lvl = tbl->lvl + 1;
                        tbl->e[b].next->p_idx = tbl->idx + b;
                }
                AN(tbl->e[b].next);
                tbl_add(tbl->e[b].next, code, codelen,
                    bits, len - tbl->mask, chr);
                return;
        }

        bits = bits << (tbl->mask - len);
        for (u = 0; u < (1U << (tbl->mask - len)); u++) {
                b = bits | u;
                assert(b < tbl->n);
                AZ(tbl->e[b].len);
                AZ(tbl->e[b].next);
                tbl->e[b].len = len;
                tbl->e[b].chr = chr;
        }
}

static void
print_lsb(uint32_t c, int l)
{
        assert(l <= 32);

        while (l > 0) {
                if (c & (1U << (l - 1)))
                        printf("1");
                else
                        printf("0");
                l--;
        }
}

static void
tbl_print(const struct tbl *tbl)
{
        unsigned u;

        printf("/* Table: lvl=%u p_idx=%u n=%u mask=%u masked=%u */\n",
            tbl->lvl, tbl->p_idx, tbl->n, tbl->mask, tbl->masked);
        for (u = 0; u < tbl->n; u++) {
                printf("/* %3u: ", tbl->idx + u);
                printf("%*s", maxlen - tbl->mask - tbl->masked, "");
                printf("%*s", tbl->mask - tbl->e[u].len, "");

                if (tbl->masked > 0) {
                        printf("(");
                        print_lsb(tbl->code >> tbl->mask, tbl->masked);
                        printf(") ");
                } else
                        printf("   ");
                if (tbl->e[u].len < tbl->mask) {
                        print_lsb(u >> (tbl->mask - tbl->e[u].len),
                            tbl->e[u].len);
                        printf(" (");
                        print_lsb(u, tbl->mask - tbl->e[u].len);
                        printf(")");
                } else {
                        assert(tbl->e[u].len == tbl->mask);
                        print_lsb(u, tbl->e[u].len);
                        printf("   ");
                }
                printf("%*s", 3 - (tbl->mask - tbl->e[u].len), "");
                printf(" */ ");

                if (tbl->e[u].next) {
                        /* Jump to next table */
                        assert(tbl->e[u].next->idx - (tbl->idx + u)
                            <= UINT8_MAX);
                        printf("{ .len = %u, .jump = %u },",
                            tbl->e[u].len,
                            tbl->e[u].next->idx - (tbl->idx + u));
                        printf(" /* Next: %u */", tbl->e[u].next->idx);
                } else if (tbl->e[u].len) {
                        printf("{ ");
                        printf(".len = %u", tbl->e[u].len);
                        printf(", .chr = (char)0x%02x", tbl->e[u].chr);
                        if (isgraph(tbl->e[u].chr))
                                printf(" /* '%c' */", tbl->e[u].chr);
                        if (u == 0)
                                /* First in table, set mask */
                                printf(", .mask = %u", tbl->mask);
                        printf(" },");
                } else
                        printf("{ .len = 0 }, /* invalid */");
                printf("\n");
        }

        for (u = 0; u < tbl->n; u++)
                if (tbl->e[u].next)
                        tbl_print(tbl->e[u].next);
}

int
main(int argc, const char **argv)
{
        struct tbl *top;
        unsigned u;

        (void)argc;
        (void)argv;

        for (u = 0; u < HUF_LEN; u++) {
                maxlen = vmax(maxlen, huf[u].blen);
                minlen = vmin(minlen, huf[u].blen);
        }

        top = tbl_new(8);
        AN(top);

        for (u = 0; u < HUF_LEN; u++)
                tbl_add(top, huf[u].code, huf[u].blen,
                    huf[u].code, huf[u].blen, huf[u].chr);

        printf("/*\n");
        printf(" * NB:  This file is machine generated, DO NOT EDIT!\n");
        printf(" *\n");
        printf(" */\n\n");

        printf("#define HUFDEC_LEN %u\n", idx);
        printf("#define HUFDEC_MIN %u\n", minlen);
        printf("#define HUFDEC_MAX %u\n\n", maxlen);

        printf("static const struct {\n");
        printf("\tuint8_t\tmask;\n");
        printf("\tuint8_t\tlen;\n");
        printf("\tuint8_t\tjump;\n");
        printf("\tchar\tchr;\n");
        printf("} hufdec[HUFDEC_LEN] = {\n");
        tbl_print(top);
        printf("};\n");

        tbl_free(top);
        return (0);
}

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