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