Code Coverage: vinyl-cache/bin/vinyltest/vtest2/src/vtc_h2_hpack.c
 
82217aa4fc7094b3610340078afaf78cd95a8ec9
 
0
/*-
1
 * Copyright (c) 2008-2016 Varnish Software AS
2
 * All rights reserved.
3
 *
4
 * Author: Guillaume Quintard <guillaume.quintard@gmail.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 <stdint.h>
31
#include <stdio.h>
32
#include <stdlib.h>
33
#include <string.h>
34
35
36
#include "vdef.h"
37
38
#include "vas.h"
39
#include "vqueue.h"
40
41
#include "hpack.h"
42
#include "vtc_h2_priv.h"
43
44
struct symbol {
45
        uint32_t        val;
46
        uint8_t         size;
47
};
48
49
static const struct symbol coding_table[] = {
50
#define HPACK(i, v, l) {v, l},
51
#include "vtc_h2_enctbl.h"
52
#undef HPACK
53
        {0, 0}
54
};
55
56
#include "vtc_h2_dectbl.h"
57
58 127
#define MASK(pack, n) (pack >> (64 - n))
59
static int
60
huff_decode(char *str, int nm, struct hpk_iter *iter, int ilen)
61 11
{
62 11
        int l = 0;
63 11
        uint64_t pack = 0;
64 11
        unsigned pl = 0; /* pack length*/
65 11
        struct stbl *tbl = &tbl_0;
66 11
        struct ssym *sym;
67
68 11
        (void)nm;
69 127
        while (ilen > 0 || pl != 0) {
70
                /* make sure we have enough data*/
71 127
                if (pl < tbl->msk) {
72 27
                        if (ilen == 0) {
73 11
                                if (pl == 0 || (MASK(pack, pl) ==
74 11
                                                (unsigned)((1U << pl) - 1U))) {
75 11
                                        assert(tbl == &tbl_0);
76 11
                                        return (l);
77 11
                                }
78 11
                        }
79
                        /* fit as many bytes as we can in pack */
80 107
                        while (pl <= 56 && ilen > 0) {
81 91
                                pack |= (uint64_t)(*iter->buf & 0xff)
82 91
                                        << (56 - pl);
83 91
                                pl += 8;
84 91
                                iter->buf++;
85 91
                                ilen--;
86 91
                        }
87 16
                }
88 116
                assert(tbl);
89 116
                assert(tbl->msk);
90 116
                sym = &tbl->syms[MASK(pack, tbl->msk)];
91
92 116
                assert(sym->csm <= tbl->msk);
93
94 116
                if (sym->csm == 0 || pl < sym->csm)
95 0
                        return (0);
96
97 116
                assert(sym->csm <= 8);
98 116
                pack <<= sym->csm;
99 116
                assert(sym->csm <= pl);
100 116
                pl -= sym->csm;
101 116
                if (sym->nxt) {
102 0
                        tbl = sym->nxt;
103 0
                        continue;
104 0
                }
105 116
                str[l++] = sym->chr;
106 116
                tbl = &tbl_0;
107 116
        }
108 0
        return (l);
109 11
}
110
111
/* inspired from Dridi Boukelmoune's cashpack. */
112
static enum hpk_result
113
huff_encode(struct hpk_iter *iter, const char *str, int len)
114 14
{
115 14
        uint64_t pack = 0;
116 14
        int pl = 0; /* pack length*/
117 14
        uint32_t        v;
118 14
        uint8_t         s;
119
120 14
        assert(iter->buf < iter->end);
121
122 158
        while (len--) {
123 144
                v = coding_table[(uint8_t)*str].val;
124 144
                s = coding_table[(uint8_t)*str].size;
125
126 144
                pl += s;
127 144
                pack |= (uint64_t)v << (64 - pl);
128
129 244
                while (pl >= 8) {
130 100
                        if (iter->buf == iter->end)
131 0
                                return (hpk_done);
132 100
                        *iter->buf = (char)(pack >> 56);
133 100
                        iter->buf++;
134 100
                        pack <<= 8;
135 100
                        pl -= 8;
136 100
                }
137 144
                str++;
138 144
        }
139
140
        /* padding */
141 14
        if (pl) {
142 14
                assert(pl < 8);
143 14
                if (iter->buf == iter->end)
144 0
                        return (hpk_done);
145 14
                pl += 8;
146 14
                pack |= (uint64_t)0xff << (64 - pl);
147 14
                *iter->buf = (char)(pack >> 56);
148 14
                iter->buf++;
149 14
        }
150
151 14
        return (hpk_more);
152 14
}
153
154
static int
155
huff_simulate(const char *str, int ilen, int huff)
156 3894
{
157 3894
        int olen = 0;
158 3894
        if (!huff || !ilen)
159 3880
                return (ilen);
160 158
        while (ilen--) {
161 144
                olen += coding_table[(unsigned char)*str].size;
162 144
                str++;
163 144
        }
164 14
        return ((olen + 7) / 8);
165 3894
}
166
167
static enum hpk_result
168
num_decode(uint32_t *result, struct hpk_iter *iter, uint8_t prefix)
169 2624
{
170 2624
        uint8_t shift = 0;
171
172 2624
        assert(iter->buf < iter->end);
173 2624
        assert(prefix);
174 2624
        assert(prefix <= 8);
175
176 2624
        *result = 0;
177 2624
        *result = *iter->buf & (0xff >> (8-prefix));
178 2624
        if (*result < (1U << prefix) - 1U) {
179 2030
                iter->buf++;
180 2030
                return (ITER_DONE(iter));
181 2030
        }
182 598
        do {
183 598
                iter->buf++;
184 598
                if (iter->end == iter->buf)
185 0
                        return (hpk_err);
186
                /* check for overflow */
187 598
                if ((UINT32_MAX - *result) >> shift < (*iter->buf & 0x7f))
188 0
                        return (hpk_err);
189
190 598
                *result += (uint32_t)(*iter->buf & 0x7f) << shift;
191 598
                shift += 7;
192 598
        } while (*iter->buf & 0x80);
193 594
        iter->buf++;
194
195 594
        return (ITER_DONE(iter));
196 594
}
197
198
static enum hpk_result
199
num_encode(struct hpk_iter *iter, uint8_t prefix, uint32_t num)
200 3952
{
201 3952
        assert(prefix);
202 3952
        assert(prefix <= 8);
203 3952
        assert(iter->buf < iter->end);
204
205 3952
        uint8_t pmax = (1U << prefix) - 1U;
206
207 3952
        *iter->buf &= 0xffU << prefix;
208 3952
        if (num <= pmax) {
209 2951
                *iter->buf++ |= num;
210 2951
                return (ITER_DONE(iter));
211 2951
        } else if (iter->end - iter->buf < 2)
212 0
                return (hpk_err);
213
214 1001
        iter->buf[0] |= pmax;
215 1001
        num -= pmax;
216 2001
        do {
217 2001
                iter->buf++;
218 2001
                if (iter->end == iter->buf)
219 0
                        return (hpk_err);
220 2001
                *iter->buf = num % 128;
221 2001
                *iter->buf |= 0x80;
222 2001
                num /= 128;
223 2001
        } while (num);
224 1001
        *iter->buf++ &= 127;
225 1001
        return (ITER_DONE(iter));
226 1001
}
227
228
static enum hpk_result
229
str_encode(struct hpk_iter *iter, const struct hpk_txt *t)
230 3894
{
231 3894
        int slen = huff_simulate(t->ptr, t->len, t->huff);
232 3894
        assert(iter->buf < iter->end);
233 3894
        if (t->huff)
234 14
                *iter->buf = 0x80;
235 3880
        else
236 3880
                *iter->buf = 0;
237
238 3894
        if (hpk_err == num_encode(iter, 7, slen))
239 0
                return (hpk_err);
240
241 3894
        if (slen > iter->end - iter->buf)
242 0
                return (hpk_err);
243
244 3894
        if (t->huff) {
245 14
                return (huff_encode(iter, t->ptr, t->len));
246 3880
        } else {
247 3880
                vmemcpy(iter->buf, t->ptr, slen);
248 3880
                iter->buf += slen;
249 3880
                return (ITER_DONE(iter));
250 3880
        }
251 3894
}
252
253
static enum hpk_result
254
str_decode(struct hpk_iter *iter, struct hpk_txt *t)
255 1453
{
256 1453
        uint32_t num;
257 1453
        int huff;
258
259 1453
        assert(iter->buf < iter->end);
260
261 1453
        huff = (*iter->buf & 0x80);
262 1453
        if (hpk_more != num_decode(&num, iter, 7))
263 0
                return (hpk_err);
264 1453
        assert(iter->buf < iter->end);
265 1453
        if (num > (unsigned)(iter->end - iter->buf))
266 0
                return (hpk_err);
267 1453
        if (huff) { /*Huffman encoding */
268 11
                t->ptr = malloc((num * 8L) / 5L + 1L);
269 11
                AN(t->ptr);
270 11
                num = huff_decode(t->ptr, (num * 8) / 5, iter, num);
271 11
                if (!num) {
272 0
                        free(t->ptr);
273 0
                        return (hpk_err);
274 0
                }
275 11
                t->huff = 1;
276
                /* XXX: do we care? */
277 11
                t->ptr = realloc(t->ptr, num + 1L);
278 11
                AN(t->ptr);
279 1442
        } else { /* literal string */
280 1442
                t->huff = 0;
281 1442
                t->ptr = malloc(num + 1L);
282 1442
                AN(t->ptr);
283 1442
                vmemcpy(t->ptr, iter->buf, num);
284 1442
                iter->buf += num;
285 1442
        }
286
287 1453
        t->ptr[num] = '\0';
288 1453
        t->len = num;
289
290 1453
        return (ITER_DONE(iter));
291 1453
}
292
293
static inline void
294
txtcpy(struct hpk_txt *to, const struct hpk_txt *from)
295 885
{
296
        //AZ(to->ptr);
297 885
        to->ptr = malloc(from->len + 1L);
298 885
        AN(to->ptr);
299 885
        vmemcpy(to->ptr, from->ptr, from->len + 1L);
300 885
        to->len = from->len;
301 885
}
302
303
int
304
gethpk_iterLen(const struct hpk_iter *iter)
305 1302
{
306 1302
        return (iter->buf - iter->orig);
307 1302
}
308
309
enum hpk_result
310
HPK_DecHdr(struct hpk_iter *iter, struct hpk_hdr *header)
311 1171
{
312 1171
        int pref = 0;
313 1171
        const struct hpk_txt *t;
314 1171
        uint32_t num;
315 1171
        int must_index = 0;
316 1171
        assert(iter);
317 1171
        assert(iter->buf < iter->end);
318
        /* Indexed Header Field */
319 1171
        if (*iter->buf & 128) {
320 138
                header->t = hpk_idx;
321 138
                if (hpk_err == num_decode(&num, iter, 7))
322 0
                        return (hpk_err);
323
324 138
                if (num) { /* indexed key and value*/
325 138
                        t = tbl_get_key(iter->ctx, num);
326 138
                        if (!t)
327 2
                                return (hpk_err);
328 136
                        txtcpy(&header->key, t);
329
330 136
                        t = tbl_get_value(iter->ctx, num);
331 136
                        if (!t) {
332 0
                                free(header->key.ptr);
333 0
                                return (hpk_err);
334 0
                        }
335
336 136
                        txtcpy(&header->value, t);
337
338 136
                        if (iter->buf < iter->end)
339 134
                                return (hpk_more);
340 2
                        else
341 2
                                return (hpk_done);
342 136
                } else
343 0
                        return (hpk_err);
344
345 138
        }
346
        /* Literal Header Field with Incremental Indexing */
347 1033
        else if (*iter->buf >> 6 == 1) {
348 18
                header->t = hpk_inc;
349 18
                pref = 6;
350 18
                must_index = 1;
351 18
        }
352
        /* Literal Header Field without Indexing */
353 1015
        else if (*iter->buf >> 4 == 0) {
354 210
                header->t = hpk_not;
355 210
                pref = 4;
356 210
        }
357
        /* Literal Header Field never Indexed */
358 805
        else if (*iter->buf >> 4 == 1) {
359 805
                header->t = hpk_never;
360 805
                pref = 4;
361 805
        }
362
        /* Dynamic Table Size Update */
363
        /* XXX if under max allowed value */
364 0
        else if (*iter->buf >> 5 == 1) {
365 0
                if (hpk_done != num_decode(&num, iter, 5))
366 0
                        return (hpk_err);
367 0
                return (HPK_ResizeTbl(iter->ctx, num));
368 0
        } else {
369 0
                return (hpk_err);
370 0
        }
371
372 1033
        assert(pref);
373 1033
        if (hpk_more != num_decode(&num, iter, pref))
374 0
                return (hpk_err);
375
376 1033
        header->i = num;
377 1033
        if (num) { /* indexed key */
378 613
                t = tbl_get_key(iter->ctx, num);
379 613
                if (!t)
380 0
                        return (hpk_err);
381 613
                txtcpy(&header->key, t);
382 613
        } else {
383 420
                if (hpk_more != str_decode(iter, &header->key)) {
384 0
                        free(header->key.ptr);
385 0
                        return (hpk_err);
386 0
                }
387 420
        }
388
389 1033
        if (hpk_err == str_decode(iter, &header->value)) {
390 0
                free(header->key.ptr);
391 0
                return (hpk_err);
392 0
        }
393
394 1033
        if (must_index)
395 18
                push_header(iter->ctx, header);
396 1033
        return (ITER_DONE(iter));
397 1033
}
398
399
enum hpk_result
400
HPK_EncHdr(struct hpk_iter *iter, const struct hpk_hdr *h)
401 1997
{
402 1997
        int pref;
403 1997
        int must_index = 0;
404 1997
        enum hpk_result ret;
405 1997
        switch (h->t) {
406 42
                case hpk_idx:
407 42
                        *iter->buf = 0x80;
408 42
                        assert(num_encode(iter, 7, h->i) != hpk_err);
409 42
                        return (ITER_DONE(iter));
410 22
                case hpk_inc:
411 22
                        *iter->buf = 0x40;
412 22
                        pref = 6;
413 22
                        must_index = 1;
414 22
                        break;
415 1932
                case hpk_not:
416 1932
                        *iter->buf = 0x00;
417 1932
                        pref = 4;
418 1932
                        break;
419 1
                case hpk_never:
420 1
                        *iter->buf = 0x10;
421 1
                        pref = 4;
422 1
                        break;
423 0
                default:
424 0
                        INCOMPL();
425 1997
        }
426 1955
        if (h->i) {
427 16
                if (hpk_more != num_encode(iter, pref, h->i))
428 0
                        return (hpk_err);
429 1939
        } else {
430 1939
                iter->buf++;
431 1939
                if (hpk_more != str_encode(iter, &h->key))
432 0
                        return (hpk_err);
433 1939
        }
434 1955
        ret = str_encode(iter, &h->value);
435 1955
        if (ret == hpk_err)
436 0
                return (hpk_err);
437 1955
        if (must_index)
438 22
                push_header(iter->ctx, h);
439 1955
        return (ret);
440
441 1955
}