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 vcountof(huf)

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