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[] v_counted_by_(n);
};

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