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