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 132
huff_decode(char *str, int nm, struct hpk_iter *iter, int ilen)
60
{
61 132
        int l = 0;
62 132
        uint64_t pack = 0;
63 132
        unsigned pl = 0; /* pack length*/
64 132
        struct stbl *tbl = &byte0;
65
        struct ssym *sym;
66
67
        (void)nm;
68 1656
        while (ilen > 0 || pl != 0) {
69
                /* make sure we have enough data*/
70 1524
                if (pl < tbl->msk) {
71 324
                        if (ilen == 0) {
72 264
                                if (pl == 0 || (MASK(pack, pl) ==
73 132
                                                (unsigned)((1U << pl) - 1U))) {
74 132
                                        assert(tbl == &byte0);
75 132
                                        return (l);
76
                                }
77
                        }
78
                        /* fit as many bytes as we can in pack */
79 1476
                        while (pl <= 56 && ilen > 0) {
80 2184
                                pack |= (uint64_t)(*iter->buf & 0xff)
81 1092
                                        << (56 - pl);
82 1092
                                pl += 8;
83 1092
                                iter->buf++;
84 1092
                                ilen--;
85
                        }
86
                }
87 1392
                assert(tbl);
88 1392
                assert(tbl->msk);
89 1392
                sym = &tbl->syms[MASK(pack, tbl->msk)];
90
91 1392
                assert(sym->csm <= tbl->msk);
92
93 1392
                if (sym->csm == 0 || pl < sym->csm)
94 0
                        return (0);
95
96 1392
                assert(sym->csm <= 8);
97 1392
                pack <<= sym->csm;
98 1392
                assert(sym->csm <= pl);
99 1392
                pl -= sym->csm;
100 1392
                if (sym->nxt) {
101 0
                        tbl = sym->nxt;
102 0
                        continue;
103
                }
104 1392
                str[l++] = sym->chr;
105 1392
                tbl = &byte0;
106
        }
107 0
        return (l);
108
}
109
110
/* inspired from Dridi Boukelmoune's cashpack. */
111
static enum hpk_result
112 168
huff_encode(struct hpk_iter *iter, const char *str, int len)
113
{
114 168
        uint64_t pack = 0;
115 168
        int pl = 0; /* pack length*/
116
        uint32_t        v;
117
        uint8_t         s;
118
119 168
        assert(iter->buf < iter->end);
120
121 2064
        while (len--) {
122 1728
                v = coding_table[(uint8_t)*str].val;
123 1728
                s = coding_table[(uint8_t)*str].size;
124
125 1728
                pl += s;
126 1728
                pack |= (uint64_t)v << (64 - pl);
127
128 4656
                while (pl >= 8) {
129 1200
                        if (iter->buf == iter->end)
130 0
                                return (hpk_done);
131 1200
                        *iter->buf = (char)(pack >> 56);
132 1200
                        iter->buf++;
133 1200
                        pack <<= 8;
134 1200
                        pl -= 8;
135
                }
136 1728
                str++;
137
        }
138
139
        /* padding */
140 168
        if (pl) {
141 168
                assert(pl < 8);
142 168
                if (iter->buf == iter->end)
143 0
                        return (hpk_done);
144 168
                pl += 8;
145 168
                pack |= (uint64_t)0xff << (64 - pl);
146 168
                *iter->buf = (char)(pack >> 56);
147 168
                iter->buf++;
148
        }
149
150 168
        return (hpk_more);
151
}
152
153
static int
154 10176
huff_simulate(const char *str, int ilen, int huff)
155
{
156 10176
        int olen = 0;
157 10176
        if (!huff || !ilen)
158 10008
                return (ilen);
159 2064
        while (ilen--) {
160 1728
                olen += coding_table[(unsigned char)*str].size;
161 1728
                str++;
162
        }
163 168
        return ((olen+7)/8);
164
}
165
166
static enum hpk_result
167 15024
num_decode(uint32_t *result, struct hpk_iter *iter, uint8_t prefix)
168
{
169 15024
        uint8_t shift = 0;
170
171 15024
        assert(iter->buf < iter->end);
172 15024
        assert(prefix);
173 15024
        assert(prefix <= 8);
174
175 15024
        *result = 0;
176 15024
        *result = *iter->buf & (0xff >> (8-prefix));
177 15024
        if (*result < (1U << prefix) - 1U) {
178 12276
                iter->buf++;
179 12276
                return (ITER_DONE(iter));
180
        }
181
        do {
182 2796
                iter->buf++;
183 2796
                if (iter->end == iter->buf)
184 0
                        return (hpk_err);
185
                /* check for overflow */
186 2796
                if ((UINT32_MAX - *result) >> shift < (*iter->buf & 0x7f))
187 0
                        return (hpk_err);
188
189 2796
                *result += (uint32_t)(*iter->buf & 0x7f) << shift;
190 2796
                shift += 7;
191 2796
        } while (*iter->buf & 0x80);
192 2748
        iter->buf++;
193
194 2748
        return (ITER_DONE(iter));
195
}
196
197
static enum hpk_result
198 10872
num_encode(struct hpk_iter *iter, uint8_t prefix, uint32_t num)
199
{
200 10872
        assert(prefix);
201 10872
        assert(prefix <= 8);
202 10872
        assert(iter->buf < iter->end);
203
204 10872
        uint8_t pmax = (1U << prefix) - 1U;
205
206 10872
        *iter->buf &= 0xffU << prefix;
207 10872
        if (num <=  pmax) {
208 10860
                *iter->buf++ |= num;
209 10860
                return (ITER_DONE(iter));
210 12
        } else if (iter->end - iter->buf < 2)
211 0
                return (hpk_err);
212
213 12
        iter->buf[0] |= pmax;
214 12
        num -= pmax;
215
        do {
216 12
                iter->buf++;
217 12
                if (iter->end == iter->buf)
218 0
                        return (hpk_err);
219 12
                *iter->buf = num % 128;
220 12
                *iter->buf |= 0x80;
221 12
                num /= 128;
222 12
        } while (num);
223 12
        *iter->buf++ &= 127;
224 12
        return (ITER_DONE(iter));
225
}
226
227
static enum hpk_result
228 10176
str_encode(struct hpk_iter *iter, const struct txt *t)
229
{
230 10176
        int slen = huff_simulate(t->ptr, t->len, t->huff);
231 10176
        assert(iter->buf < iter->end);
232 10176
        if (t->huff)
233 168
                *iter->buf = 0x80;
234
        else
235 10008
                *iter->buf = 0;
236
237 10176
        if (hpk_err == num_encode(iter, 7, slen))
238 0
                return (hpk_err);
239
240 10176
        if (slen > iter->end - iter->buf)
241 0
                return (hpk_err);
242
243 10176
        if (t->huff) {
244 168
                return (huff_encode(iter, t->ptr, t->len));
245
        } else {
246 10008
                memcpy(iter->buf, t->ptr, slen);
247 10008
                iter->buf += slen;
248 10008
                return (ITER_DONE(iter));
249
        }
250
}
251
252
static enum hpk_result
253 8388
str_decode(struct hpk_iter *iter, struct txt *t)
254
{
255
        uint32_t num;
256
        int huff;
257 8388
        assert(iter->buf < iter->end);
258 8388
        huff = (*iter->buf & 0x80);
259 8388
        if (hpk_more != num_decode(&num, iter, 7))
260 0
                return (hpk_err);
261 8388
        if (num > iter->end - iter->buf)
262 0
                return (hpk_err);
263 8388
        if (huff) { /*Huffman encoding */
264 132
                t->ptr = malloc((num * 8L) / 5L + 1L);
265 132
                AN(t->ptr);
266 132
                num = huff_decode(t->ptr, (num * 8) / 5, iter, num);
267 132
                if (!num) {
268 0
                        free(t->ptr);
269 0
                        return (hpk_err);
270
                }
271 132
                t->huff = 1;
272
                /* XXX: do we care? */
273 132
                t->ptr = realloc(t->ptr, num + 1L);
274 132
                AN(t->ptr);
275
        } else { /* literal string */
276 8256
                t->huff = 0;
277 8256
                t->ptr = malloc(num + 1L);
278 8256
                AN(t->ptr);
279 8256
                memcpy(t->ptr, iter->buf, num);
280 8256
                iter->buf += num;
281
        }
282
283 8388
        t->ptr[num] = '\0';
284 8388
        t->len = num;
285
286 8388
        return (ITER_DONE(iter));
287
}
288
289
static inline void
290 4836
txtcpy(struct txt *to, const struct txt *from)
291
{
292
        //AZ(to->ptr);
293 4836
        to->ptr = malloc(from->len + 1L);
294 4836
        AN(to->ptr);
295 4836
        memcpy(to->ptr, from->ptr, from->len + 1L);
296 4836
        to->len = from->len;
297 4836
}
298
299
int
300 1908
gethpk_iterLen(const struct hpk_iter *iter)
301
{
302 1908
        return (iter->buf - iter->orig);
303
}
304
305
enum hpk_result
306 6636
HPK_DecHdr(struct hpk_iter *iter, struct hpk_hdr *header)
307
{
308 6636
        int pref = 0;
309
        const struct txt *t;
310
        uint32_t num;
311 6636
        int must_index = 0;
312 6636
        assert(iter);
313 6636
        assert(iter->buf < iter->end);
314
        /* Indexed Header Field */
315 6636
        if (*iter->buf & 128) {
316 984
                header->t = hpk_idx;
317 984
                if (hpk_err == num_decode(&num, iter, 7))
318 0
                        return (hpk_err);
319
320 984
                if (num) { /* indexed key and value*/
321 984
                        t = tbl_get_key(iter->ctx, num);
322 984
                        if (!t)
323 24
                                return (hpk_err);
324 960
                        txtcpy(&header->key, t);
325
326 960
                        t = tbl_get_value(iter->ctx, num);
327 960
                        if (!t) {
328 0
                                free(header->key.ptr);
329 0
                                return (hpk_err);
330
                        }
331
332 960
                        txtcpy(&header->value, t);
333
334 960
                        if (iter->buf < iter->end)
335 948
                                return (hpk_more);
336
                        else
337 12
                                return (hpk_done);
338
                } else
339 0
                        return (hpk_err);
340
341
        }
342
        /* Literal Header Field with Incremental Indexing */
343 5652
        else if (*iter->buf >> 6 == 1) {
344 216
                header->t = hpk_inc;
345 216
                pref = 6;
346 216
                must_index = 1;
347
        }
348
        /* Literal Header Field without Indexing */
349 5436
        else if (*iter->buf >> 4 == 0) {
350 2064
                header->t = hpk_not;
351 2064
                pref = 4;
352
        }
353
        /* Literal Header Field never Indexed */
354 3372
        else if (*iter->buf >> 4 == 1) {
355 3372
                header->t = hpk_never;
356 3372
                pref = 4;
357
        }
358
        /* Dynamic Table Size Update */
359
        /* XXX if under max allowed value */
360 0
        else if (*iter->buf >> 5 == 1) {
361 0
                if (hpk_done != num_decode(&num, iter, 5))
362 0
                        return (hpk_err);
363 0
                return HPK_ResizeTbl(iter->ctx, num);
364
        } else {
365 0
                return (hpk_err);
366
        }
367
368 5652
        assert(pref);
369 5652
        if (hpk_more != num_decode(&num, iter, pref))
370 0
                return (hpk_err);
371
372 5652
        header->i = num;
373 5652
        if (num) { /* indexed key */
374 2916
                t = tbl_get_key(iter->ctx, num);
375 2916
                if (!t)
376 0
                        return (hpk_err);
377 2916
                txtcpy(&header->key, t);
378
        } else {
379 2736
                if (hpk_more != str_decode(iter, &header->key))
380 0
                        return (hpk_err);
381
        }
382
383 5652
        if (hpk_err == str_decode(iter, &header->value))
384 0
                return (hpk_err);
385
386 5652
        if (must_index)
387 216
                push_header(iter->ctx, header);
388 5652
        return (ITER_DONE(iter));
389
}
390
391
enum hpk_result
392 5688
HPK_EncHdr(struct hpk_iter *iter, const struct hpk_hdr *h)
393
{
394
        int pref;
395 5688
        int must_index = 0;
396
        enum hpk_result ret;
397 5688
        switch (h->t) {
398
                case hpk_idx:
399 504
                        *iter->buf = 0x80;
400 504
                        assert(num_encode(iter, 7, h->i) != hpk_err);
401 504
                        return (ITER_DONE(iter));
402
                case hpk_inc:
403 264
                        *iter->buf = 0x40;
404 264
                        pref = 6;
405 264
                        must_index = 1;
406 264
                        break;
407
                case hpk_not:
408 4908
                        *iter->buf = 0x00;
409 4908
                        pref = 4;
410 4908
                        break;
411
                case hpk_never:
412 12
                        *iter->buf = 0x10;
413 12
                        pref = 4;
414 12
                        break;
415
                default:
416 0
                        INCOMPL();
417
        }
418 5184
        if (h->i) {
419 192
                if (hpk_more != num_encode(iter, pref, h->i))
420 0
                        return (hpk_err);
421
        } else {
422 4992
                iter->buf++;
423 4992
                if (hpk_more != str_encode(iter, &h->key))
424 0
                        return (hpk_err);
425
        }
426 5184
        ret = str_encode(iter, &h->value);
427 5184
        if (ret == hpk_err)
428 0
                return (hpk_err);
429 5184
        if (must_index)
430 264
                push_header(iter->ctx, h);
431 5184
        return (ret);
432
433
}