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