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