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