varnish-cache/bin/varnishtest/vtc_h2_hpack.c
1
/*-
2
 * Copyright (c) 2008-2016 Varnish Software AS
3
 * All rights reserved.
4
 *
5
 * Author: Guillaume Quintard <guillaume.quintard@gmail.com>
6
 *
7
 * Redistribution and use in source and binary forms, with or without
8
 * modification, are permitted provided that the following conditions
9
 * are met:
10
 * 1. Redistributions of source code must retain the above copyright
11
 *    notice, this list of conditions and the following disclaimer.
12
 * 2. Redistributions in binary form must reproduce the above copyright
13
 *    notice, this list of conditions and the following disclaimer in the
14
 *    documentation and/or other materials provided with the distribution.
15
 *
16
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
17
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19
 * ARE DISCLAIMED.  IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
20
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
22
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26
 * SUCH DAMAGE.
27
 */
28
29
#include <stdint.h>
30
#include <stdio.h>
31
#include <stdlib.h>
32
#include <string.h>
33
34
35
#include "vdef.h"
36
37
#include "vas.h"
38
#include "vqueue.h"
39
40
#include "hpack.h"
41
#include "vtc_h2_priv.h"
42
43
struct symbol {
44
        uint32_t        val;
45
        uint8_t         size;
46
};
47
48
static const struct symbol coding_table[] = {
49
#define HPACK(i, v, l) {v, l},
50
#include "vtc_h2_enctbl.h"
51
#undef HPACK
52
        {0, 0}
53
};
54
55
#include "vtc_h2_dectbl.h"
56
57
#define MASK(pack, n) (pack >> (64 - n))
58
static int
59 176
huff_decode(char *str, int nm, struct hpk_iter *iter, int ilen)
60
{
61 176
        int l = 0;
62 176
        uint64_t pack = 0;
63 176
        unsigned pl = 0; /* pack length*/
64 176
        struct stbl *tbl = &tbl_0;
65
        struct ssym *sym;
66
67 176
        (void)nm;
68 2032
        while (ilen > 0 || pl != 0) {
69
                /* make sure we have enough data*/
70 2032
                if (pl < tbl->msk) {
71 432
                        if (ilen == 0) {
72 176
                                if (pl == 0 || (MASK(pack, pl) ==
73 176
                                                (unsigned)((1U << pl) - 1U))) {
74 176
                                        assert(tbl == &tbl_0);
75 176
                                        return (l);
76
                                }
77 0
                        }
78
                        /* fit as many bytes as we can in pack */
79 1712
                        while (pl <= 56 && ilen > 0) {
80 2912
                                pack |= (uint64_t)(*iter->buf & 0xff)
81 1456
                                        << (56 - pl);
82 1456
                                pl += 8;
83 1456
                                iter->buf++;
84 1456
                                ilen--;
85
                        }
86 256
                }
87 1856
                assert(tbl);
88 1856
                assert(tbl->msk);
89 1856
                sym = &tbl->syms[MASK(pack, tbl->msk)];
90
91 1856
                assert(sym->csm <= tbl->msk);
92
93 1856
                if (sym->csm == 0 || pl < sym->csm)
94 0
                        return (0);
95
96 1856
                assert(sym->csm <= 8);
97 1856
                pack <<= sym->csm;
98 1856
                assert(sym->csm <= pl);
99 1856
                pl -= sym->csm;
100 1856
                if (sym->nxt) {
101 0
                        tbl = sym->nxt;
102 0
                        continue;
103
                }
104 1856
                str[l++] = sym->chr;
105 1856
                tbl = &tbl_0;
106
        }
107 0
        return (l);
108 176
}
109
110
/* inspired from Dridi Boukelmoune's cashpack. */
111
static enum hpk_result
112 224
huff_encode(struct hpk_iter *iter, const char *str, int len)
113
{
114 224
        uint64_t pack = 0;
115 224
        int pl = 0; /* pack length*/
116
        uint32_t        v;
117
        uint8_t         s;
118
119 224
        assert(iter->buf < iter->end);
120
121 2528
        while (len--) {
122 2304
                v = coding_table[(uint8_t)*str].val;
123 2304
                s = coding_table[(uint8_t)*str].size;
124
125 2304
                pl += s;
126 2304
                pack |= (uint64_t)v << (64 - pl);
127
128 3904
                while (pl >= 8) {
129 1600
                        if (iter->buf == iter->end)
130 0
                                return (hpk_done);
131 1600
                        *iter->buf = (char)(pack >> 56);
132 1600
                        iter->buf++;
133 1600
                        pack <<= 8;
134 1600
                        pl -= 8;
135
                }
136 2304
                str++;
137
        }
138
139
        /* padding */
140 224
        if (pl) {
141 224
                assert(pl < 8);
142 224
                if (iter->buf == iter->end)
143 0
                        return (hpk_done);
144 224
                pl += 8;
145 224
                pack |= (uint64_t)0xff << (64 - pl);
146 224
                *iter->buf = (char)(pack >> 56);
147 224
                iter->buf++;
148 224
        }
149
150 224
        return (hpk_more);
151 224
}
152
153
static int
154 16288
huff_simulate(const char *str, int ilen, int huff)
155
{
156 16288
        int olen = 0;
157 16288
        if (!huff || !ilen)
158 16064
                return (ilen);
159 2528
        while (ilen--) {
160 2304
                olen += coding_table[(unsigned char)*str].size;
161 2304
                str++;
162
        }
163 224
        return ((olen + 7) / 8);
164 16288
}
165
166
static enum hpk_result
167 23552
num_decode(uint32_t *result, struct hpk_iter *iter, uint8_t prefix)
168
{
169 23552
        uint8_t shift = 0;
170
171 23552
        assert(iter->buf < iter->end);
172 23552
        assert(prefix);
173 23552
        assert(prefix <= 8);
174
175 23552
        *result = 0;
176 23552
        *result = *iter->buf & (0xff >> (8-prefix));
177 23552
        if (*result < (1U << prefix) - 1U) {
178 18880
                iter->buf++;
179 18880
                return (ITER_DONE(iter));
180
        }
181 4672
        do {
182 4736
                iter->buf++;
183 4736
                if (iter->end == iter->buf)
184 0
                        return (hpk_err);
185
                /* check for overflow */
186 4736
                if ((UINT32_MAX - *result) >> shift < (*iter->buf & 0x7f))
187 0
                        return (hpk_err);
188
189 4736
                *result += (uint32_t)(*iter->buf & 0x7f) << shift;
190 4736
                shift += 7;
191 4736
        } while (*iter->buf & 0x80);
192 4672
        iter->buf++;
193
194 4672
        return (ITER_DONE(iter));
195 23552
}
196
197
static enum hpk_result
198 17216
num_encode(struct hpk_iter *iter, uint8_t prefix, uint32_t num)
199
{
200 17216
        assert(prefix);
201 17216
        assert(prefix <= 8);
202 17216
        assert(iter->buf < iter->end);
203
204 17216
        uint8_t pmax = (1U << prefix) - 1U;
205
206 17216
        *iter->buf &= 0xffU << prefix;
207 17216
        if (num <=  pmax) {
208 17200
                *iter->buf++ |= num;
209 17200
                return (ITER_DONE(iter));
210 16
        } else if (iter->end - iter->buf < 2)
211 0
                return (hpk_err);
212
213 16
        iter->buf[0] |= pmax;
214 16
        num -= pmax;
215 16
        do {
216 16
                iter->buf++;
217 16
                if (iter->end == iter->buf)
218 0
                        return (hpk_err);
219 16
                *iter->buf = num % 128;
220 16
                *iter->buf |= 0x80;
221 16
                num /= 128;
222 16
        } while (num);
223 16
        *iter->buf++ &= 127;
224 16
        return (ITER_DONE(iter));
225 17216
}
226
227
static enum hpk_result
228 16288
str_encode(struct hpk_iter *iter, const struct txt *t)
229
{
230 16288
        int slen = huff_simulate(t->ptr, t->len, t->huff);
231 16288
        assert(iter->buf < iter->end);
232 16288
        if (t->huff)
233 224
                *iter->buf = 0x80;
234
        else
235 16064
                *iter->buf = 0;
236
237 16288
        if (hpk_err == num_encode(iter, 7, slen))
238 0
                return (hpk_err);
239
240 16288
        if (slen > iter->end - iter->buf)
241 0
                return (hpk_err);
242
243 16288
        if (t->huff) {
244 224
                return (huff_encode(iter, t->ptr, t->len));
245
        } else {
246 16064
                memcpy(iter->buf, t->ptr, slen);
247 16064
                iter->buf += slen;
248 16064
                return (ITER_DONE(iter));
249
        }
250 16288
}
251
252
static enum hpk_result
253 13056
str_decode(struct hpk_iter *iter, struct txt *t)
254
{
255
        uint32_t num;
256
        int huff;
257
258 13056
        assert(iter->buf < iter->end);
259
260 13056
        huff = (*iter->buf & 0x80);
261 13056
        if (hpk_more != num_decode(&num, iter, 7))
262 0
                return (hpk_err);
263 13056
        assert(iter->buf < iter->end);
264 13056
        if (num > (unsigned)(iter->end - iter->buf))
265 0
                return (hpk_err);
266 13056
        if (huff) { /*Huffman encoding */
267 176
                t->ptr = malloc((num * 8L) / 5L + 1L);
268 176
                AN(t->ptr);
269 176
                num = huff_decode(t->ptr, (num * 8) / 5, iter, num);
270 176
                if (!num) {
271 0
                        free(t->ptr);
272 0
                        return (hpk_err);
273
                }
274 176
                t->huff = 1;
275
                /* XXX: do we care? */
276 176
                t->ptr = realloc(t->ptr, num + 1L);
277 176
                AN(t->ptr);
278 176
        } else { /* literal string */
279 12880
                t->huff = 0;
280 12880
                t->ptr = malloc(num + 1L);
281 12880
                AN(t->ptr);
282 12880
                memcpy(t->ptr, iter->buf, num);
283 12880
                iter->buf += num;
284
        }
285
286 13056
        t->ptr[num] = '\0';
287 13056
        t->len = num;
288
289 13056
        return (ITER_DONE(iter));
290 13056
}
291
292
static inline void
293 7872
txtcpy(struct txt *to, const struct txt *from)
294
{
295
        //AZ(to->ptr);
296 7872
        to->ptr = malloc(from->len + 1L);
297 7872
        AN(to->ptr);
298 7872
        memcpy(to->ptr, from->ptr, from->len + 1L);
299 7872
        to->len = from->len;
300 7872
}
301
302
int
303 3008
gethpk_iterLen(const struct hpk_iter *iter)
304
{
305 3008
        return (iter->buf - iter->orig);
306
}
307
308
enum hpk_result
309 10496
HPK_DecHdr(struct hpk_iter *iter, struct hpk_hdr *header)
310
{
311 10496
        int pref = 0;
312
        const struct txt *t;
313
        uint32_t num;
314 10496
        int must_index = 0;
315 10496
        assert(iter);
316 10496
        assert(iter->buf < iter->end);
317
        /* Indexed Header Field */
318 10496
        if (*iter->buf & 128) {
319 1520
                header->t = hpk_idx;
320 1520
                if (hpk_err == num_decode(&num, iter, 7))
321 0
                        return (hpk_err);
322
323 1520
                if (num) { /* indexed key and value*/
324 1520
                        t = tbl_get_key(iter->ctx, num);
325 1520
                        if (!t)
326 32
                                return (hpk_err);
327 1488
                        txtcpy(&header->key, t);
328
329 1488
                        t = tbl_get_value(iter->ctx, num);
330 1488
                        if (!t) {
331 0
                                free(header->key.ptr);
332 0
                                return (hpk_err);
333
                        }
334
335 1488
                        txtcpy(&header->value, t);
336
337 1488
                        if (iter->buf < iter->end)
338 1472
                                return (hpk_more);
339
                        else
340 16
                                return (hpk_done);
341
                } else
342 0
                        return (hpk_err);
343
344
        }
345
        /* Literal Header Field with Incremental Indexing */
346 8976
        else if (*iter->buf >> 6 == 1) {
347 288
                header->t = hpk_inc;
348 288
                pref = 6;
349 288
                must_index = 1;
350 288
        }
351
        /* Literal Header Field without Indexing */
352 8688
        else if (*iter->buf >> 4 == 0) {
353 2976
                header->t = hpk_not;
354 2976
                pref = 4;
355 2976
        }
356
        /* Literal Header Field never Indexed */
357 5712
        else if (*iter->buf >> 4 == 1) {
358 5712
                header->t = hpk_never;
359 5712
                pref = 4;
360 5712
        }
361
        /* Dynamic Table Size Update */
362
        /* XXX if under max allowed value */
363 0
        else if (*iter->buf >> 5 == 1) {
364 0
                if (hpk_done != num_decode(&num, iter, 5))
365 0
                        return (hpk_err);
366 0
                return (HPK_ResizeTbl(iter->ctx, num));
367
        } else {
368 0
                return (hpk_err);
369
        }
370
371 8976
        assert(pref);
372 8976
        if (hpk_more != num_decode(&num, iter, pref))
373 0
                return (hpk_err);
374
375 8976
        header->i = num;
376 8976
        if (num) { /* indexed key */
377 4896
                t = tbl_get_key(iter->ctx, num);
378 4896
                if (!t)
379 0
                        return (hpk_err);
380 4896
                txtcpy(&header->key, t);
381 4896
        } else {
382 4080
                if (hpk_more != str_decode(iter, &header->key))
383 0
                        return (hpk_err);
384
        }
385
386 8976
        if (hpk_err == str_decode(iter, &header->value))
387 0
                return (hpk_err);
388
389 8976
        if (must_index)
390 288
                push_header(iter->ctx, header);
391 8976
        return (ITER_DONE(iter));
392 10496
}
393
394
enum hpk_result
395 8943
HPK_EncHdr(struct hpk_iter *iter, const struct hpk_hdr *h)
396
{
397
        int pref;
398 8943
        int must_index = 0;
399
        enum hpk_result ret;
400 8943
        switch (h->t) {
401
                case hpk_idx:
402 672
                        *iter->buf = 0x80;
403 672
                        assert(num_encode(iter, 7, h->i) != hpk_err);
404 672
                        return (ITER_DONE(iter));
405
                case hpk_inc:
406 352
                        *iter->buf = 0x40;
407 352
                        pref = 6;
408 352
                        must_index = 1;
409 352
                        break;
410
                case hpk_not:
411 7904
                        *iter->buf = 0x00;
412 7904
                        pref = 4;
413 7904
                        break;
414
                case hpk_never:
415 16
                        *iter->buf = 0x10;
416 16
                        pref = 4;
417 16
                        break;
418
                default:
419 0
                        INCOMPL();
420 0
        }
421 8272
        if (h->i) {
422 256
                if (hpk_more != num_encode(iter, pref, h->i))
423 0
                        return (hpk_err);
424 256
        } else {
425 8016
                iter->buf++;
426 8016
                if (hpk_more != str_encode(iter, &h->key))
427 0
                        return (hpk_err);
428
        }
429 8272
        ret = str_encode(iter, &h->value);
430 8272
        if (ret == hpk_err)
431 0
                return (hpk_err);
432 8272
        if (must_index)
433 352
                push_header(iter->ctx, h);
434 8272
        return (ret);
435
436 8944
}