varnish-cache/bin/varnishd/hpack/vhp_decode.c
1
/*-
2
 * Copyright (c) 2016 Varnish Software
3
 * All rights reserved.
4
 *
5
 * Author: Martin Blix Grydeland <martin@varnish-software.com>
6
 * Author: Dridi Boukelmoune <dridi.boukelmoune@gmail.com>
7
 *
8
 * Redistribution and use in source and binary forms, with or without
9
 * modification, are permitted provided that the following conditions
10
 * are met:
11
 * 1. Redistributions of source code must retain the above copyright
12
 *    notice, this list of conditions and the following disclaimer.
13
 * 2. Redistributions in binary form must reproduce the above copyright
14
 *    notice, this list of conditions and the following disclaimer in the
15
 *    documentation and/or other materials provided with the distribution.
16
 *
17
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
18
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20
 * ARE DISCLAIMED.  IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
21
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27
 * SUCH DAMAGE.
28
 *
29
 */
30
31
#include "config.h"
32
33
#include <stdio.h>
34
#include <string.h>
35
#include <limits.h>
36
#include <stdlib.h>
37
38
#include "vdef.h"
39
#include "vas.h"
40
#include "miniobj.h"
41
42
#include "hpack/vhp.h"
43
44
#include "vhp_hufdec.h"
45
46
struct vhd_ctx {
47
        struct vhd_decode *d;
48
        struct vht_table *tbl;
49
        const uint8_t *in;
50
        const uint8_t *in_e;
51
        char *out;
52
        char *out_e;
53
};
54
55
typedef enum vhd_ret_e vhd_state_f(struct vhd_ctx *ctx, unsigned first);
56
57
/* Function flags */
58
#define VHD_INCREMENTAL (1U << 0)
59
60
/* Functions */
61
enum vhd_func_e {
62
#define VHD_FSM_FUNC(NAME, func)                \
63
        VHD_F_##NAME,
64
#include "tbl/vhd_fsm_funcs.h"
65
        VHD_F__MAX,
66
};
67
#define VHD_FSM_FUNC(NAME, func)                \
68
        static vhd_state_f func;
69
#include "tbl/vhd_fsm_funcs.h"
70
71
/* States */
72
enum vhd_state_e {
73
        VHD_S__MIN = -1,
74
#define VHD_FSM(STATE, FUNC, arg1, arg2)        \
75
        VHD_S_##STATE,
76
#include "tbl/vhd_fsm.h"
77
        VHD_S__MAX,
78
};
79
static const struct vhd_state {
80
        const char              *name;
81
        enum vhd_func_e         func;
82
        unsigned                arg1;
83
        unsigned                arg2;
84
} vhd_states[VHD_S__MAX] = {
85
#define VHD_FSM(STATE, FUNC, arg1, arg2)        \
86
        [VHD_S_##STATE] = { #STATE, VHD_F_##FUNC, arg1, arg2 },
87
#include "tbl/vhd_fsm.h"
88
};
89
90
/* Utility functions */
91
static void
92 9916
vhd_set_state(struct vhd_decode *d, enum vhd_state_e state)
93
{
94 9916
        AN(d);
95 9916
        assert(state > VHD_S__MIN && state < VHD_S__MAX);
96 9916
        d->state = state;
97 9916
        d->first = 1;
98 9916
}
99
100
static void
101 7010
vhd_next_state(struct vhd_decode *d)
102
{
103 7010
        AN(d);
104 7010
        assert(d->state + 1 < VHD_S__MAX);
105 7010
        vhd_set_state(d, d->state + 1);
106 7010
}
107
108
/* State functions */
109
static enum vhd_ret_e v_matchproto_(vhd_state_f)
110 1738
vhd_skip(struct vhd_ctx *ctx, unsigned first)
111
{
112 1738
        AN(ctx);
113 1738
        AN(first);
114 1738
        vhd_next_state(ctx->d);
115 1738
        return (VHD_AGAIN);
116
}
117
118
static enum vhd_ret_e v_matchproto_(vhd_state_f)
119 1580
vhd_goto(struct vhd_ctx *ctx, unsigned first)
120
{
121
        const struct vhd_state *s;
122
123 1580
        AN(ctx);
124 1580
        AN(first);
125 1580
        assert(ctx->d->state < VHD_S__MAX);
126 1580
        s = &vhd_states[ctx->d->state];
127 1580
        assert(s->arg1 < VHD_S__MAX);
128 1580
        vhd_set_state(ctx->d, s->arg1);
129 1580
        return (VHD_AGAIN);
130
}
131
132
static enum vhd_ret_e v_matchproto_(vhd_state_f)
133 1048
vhd_idle(struct vhd_ctx *ctx, unsigned first)
134
{
135
        uint8_t c;
136
137 1048
        AN(ctx);
138
        (void)first;
139
140 2096
        while (ctx->in < ctx->in_e) {
141 794
                c = *ctx->in;
142 794
                if ((c & 0x80) == 0x80)
143 300
                        vhd_set_state(ctx->d, VHD_S_HP61_START);
144 494
                else if ((c & 0xc0) == 0x40)
145 192
                        vhd_set_state(ctx->d, VHD_S_HP621_START);
146 302
                else if ((c & 0xf0) == 0x00)
147 292
                        vhd_set_state(ctx->d, VHD_S_HP622_START);
148 10
                else if ((c & 0xf0) == 0x10)
149 10
                        vhd_set_state(ctx->d, VHD_S_HP623_START);
150 0
                else if ((c & 0xe0) == 0x20)
151 0
                        vhd_set_state(ctx->d, VHD_S_HP63_START);
152
                else
153 0
                        return (VHD_ERR_ARG);
154 794
                return (VHD_AGAIN);
155
        }
156
157 254
        return (VHD_OK);
158
}
159
160
static enum vhd_ret_e v_matchproto_(vhd_state_f)
161 1774
vhd_integer(struct vhd_ctx *ctx, unsigned first)
162
{
163
        const struct vhd_state *s;
164
        struct vhd_int *i;
165
        uint8_t c;
166
        unsigned mask;
167
168
        assert(UINT_MAX >= UINT32_MAX);
169
170 1774
        AN(ctx);
171 1774
        assert(ctx->d->state < VHD_S__MAX);
172 1774
        s = &vhd_states[ctx->d->state];
173 1774
        i = ctx->d->integer;
174
175 1774
        if (first) {
176 1726
                INIT_OBJ(i, VHD_INT_MAGIC);
177 1726
                i->pfx = s->arg1;
178 1726
                assert(i->pfx >= 4 && i->pfx <= 7);
179
        }
180 1774
        CHECK_OBJ_NOTNULL(i, VHD_INT_MAGIC);
181
182 3666
        while (ctx->in < ctx->in_e) {
183 1844
                c = *ctx->in;
184 1844
                ctx->in++;
185 1844
                if (i->pfx) {
186 1726
                        mask = (1U << i->pfx) - 1;
187 1726
                        i->pfx = 0;
188 1726
                        i->v = c & mask;
189 1726
                        if (i->v < mask) {
190 1696
                                vhd_next_state(ctx->d);
191 1696
                                return (VHD_AGAIN);
192
                        }
193
                } else {
194 118
                        if ((i->m == 28 && (c & 0x78)) || i->m > 28)
195 12
                                return (VHD_ERR_INT);
196 106
                        i->v += (c & 0x7f) * ((uint32_t)1 << i->m);
197 106
                        i->m += 7;
198 106
                        if (!(c & 0x80)) {
199 18
                                vhd_next_state(ctx->d);
200 18
                                return (VHD_AGAIN);
201
                        }
202
                }
203
        }
204 48
        return (VHD_MORE);
205
}
206
207
static enum vhd_ret_e v_matchproto_(vhd_state_f)
208 0
vhd_set_max(struct vhd_ctx *ctx, unsigned first)
209
{
210 0
        AN(ctx);
211 0
        AN(first);
212 0
        CHECK_OBJ_NOTNULL(ctx->d->integer, VHD_INT_MAGIC);
213 0
        if (ctx->tbl == NULL)
214 0
                return (VHD_ERR_UPD);
215 0
        if (VHT_SetMaxTableSize(ctx->tbl, ctx->d->integer->v))
216 0
                return (VHD_ERR_UPD);
217 0
        vhd_next_state(ctx->d);
218 0
        return (VHD_AGAIN);
219
}
220
221
static enum vhd_ret_e v_matchproto_(vhd_state_f)
222 790
vhd_set_idx(struct vhd_ctx *ctx, unsigned first)
223
{
224 790
        AN(ctx);
225 790
        AN(first);
226 790
        CHECK_OBJ_NOTNULL(ctx->d->integer, VHD_INT_MAGIC);
227 790
        ctx->d->index = ctx->d->integer->v;
228 790
        vhd_next_state(ctx->d);
229 790
        return (VHD_AGAIN);
230
}
231
232
static enum vhd_ret_e v_matchproto_(vhd_state_f)
233 3496
vhd_lookup(struct vhd_ctx *ctx, unsigned first)
234
{
235
        const struct vhd_state *s;
236
        struct vhd_lookup *lu;
237
        const char *p;
238
        size_t l;
239
240 3496
        AN(ctx);
241 3496
        assert(ctx->d->state < VHD_S__MAX);
242 3496
        s = &vhd_states[ctx->d->state];
243 3496
        lu = ctx->d->lookup;
244
245 3496
        if (first)
246 768
                INIT_OBJ(lu, VHD_LOOKUP_MAGIC);
247 3496
        CHECK_OBJ_NOTNULL(lu, VHD_LOOKUP_MAGIC);
248
249 3496
        switch (s->arg1) {
250
        case VHD_NAME:
251
        case VHD_NAME_SEC:
252 2072
                p = VHT_LookupName(ctx->tbl, ctx->d->index, &l);
253 2072
                break;
254
        case VHD_VALUE:
255
        case VHD_VALUE_SEC:
256 1424
                p = VHT_LookupValue(ctx->tbl, ctx->d->index, &l);
257 1424
                break;
258
        default:
259 0
                WRONG("vhd_lookup wrong arg1");
260
                break;
261
        }
262 3496
        if (first && p == NULL)
263 0
                return (VHD_ERR_IDX);
264 3496
        AN(p);
265 3496
        assert(l <= UINT_MAX);
266 3496
        if (first)
267 768
                lu->l = l;
268
269 3496
        assert(lu->l <= l);
270 3496
        p += l - lu->l;
271 3496
        l = lu->l;
272 3496
        if (l > ctx->out_e - ctx->out)
273 2728
                l = ctx->out_e - ctx->out;
274 3496
        memcpy(ctx->out, p, l);
275 3496
        ctx->out += l;
276 3496
        lu->l -= l;
277
278 3496
        if (lu->l == 0) {
279 768
                vhd_next_state(ctx->d);
280 768
                return (s->arg1);
281
        }
282 2728
        assert(ctx->out == ctx->out_e);
283 2728
        return (VHD_BUF);
284
}
285
286
static enum vhd_ret_e v_matchproto_(vhd_state_f)
287 26
vhd_new(struct vhd_ctx *ctx, unsigned first)
288
{
289 26
        AN(ctx);
290 26
        AN(first);
291 26
        if (ctx->tbl != NULL)
292 18
                VHT_NewEntry(ctx->tbl);
293 26
        vhd_next_state(ctx->d);
294 26
        return (VHD_AGAIN);
295
}
296
297
static enum vhd_ret_e v_matchproto_(vhd_state_f)
298 166
vhd_new_idx(struct vhd_ctx *ctx, unsigned first)
299
{
300 166
        AN(ctx);
301 166
        AN(first);
302 166
        if (ctx->tbl != NULL) {
303 166
                if (VHT_NewEntry_Indexed(ctx->tbl, ctx->d->index))
304 0
                        return (VHD_ERR_IDX);
305
        }
306 166
        vhd_next_state(ctx->d);
307 166
        return (VHD_AGAIN);
308
}
309
310
static enum vhd_ret_e v_matchproto_(vhd_state_f)
311 494
vhd_branch_zidx(struct vhd_ctx *ctx, unsigned first)
312
{
313
        const struct vhd_state *s;
314
315 494
        AN(ctx);
316
        (void)first;
317 494
        assert(ctx->d->state < VHD_S__MAX);
318 494
        s = &vhd_states[ctx->d->state];
319 494
        assert(s->arg1 < VHD_S__MAX);
320
321 494
        if (ctx->d->index == 0)
322 318
                vhd_set_state(ctx->d, s->arg1);
323
        else
324 176
                vhd_next_state(ctx->d);
325 494
        return (VHD_AGAIN);
326
}
327
328
static enum vhd_ret_e v_matchproto_(vhd_state_f)
329 916
vhd_branch_bit0(struct vhd_ctx *ctx, unsigned first)
330
{
331
        const struct vhd_state *s;
332
333 916
        AN(ctx);
334
        (void)first;
335 916
        assert(ctx->d->state < VHD_S__MAX);
336 916
        s = &vhd_states[ctx->d->state];
337 916
        assert(s->arg1 < VHD_S__MAX);
338
339 916
        if (ctx->in == ctx->in_e)
340 16
                return (VHD_MORE);
341
342 900
        if (*ctx->in & 0x80)
343 134
                vhd_set_state(ctx->d, s->arg1);
344
        else
345 766
                vhd_next_state(ctx->d);
346 900
        return (VHD_AGAIN);
347
}
348
349
static enum vhd_ret_e v_matchproto_(vhd_state_f)
350 2370
vhd_raw(struct vhd_ctx *ctx, unsigned first)
351
{
352
        const struct vhd_state *s;
353
        struct vhd_raw *raw;
354
        size_t l2;
355
356 2370
        AN(ctx);
357 2370
        assert(ctx->d->state < VHD_S__MAX);
358 2370
        s = &vhd_states[ctx->d->state];
359
360 2370
        raw = ctx->d->raw;
361 2370
        if (first) {
362 766
                CHECK_OBJ_NOTNULL(ctx->d->integer, VHD_INT_MAGIC);
363 766
                l2 = ctx->d->integer->v;
364 766
                INIT_OBJ(raw, VHD_RAW_MAGIC);
365 766
                raw->l = l2;
366
        }
367 2370
        CHECK_OBJ_NOTNULL(raw, VHD_RAW_MAGIC);
368
369 7010
        while (raw->l > 0) {
370 3884
                l2 = raw->l;
371 3884
                if (l2 > (ctx->in_e - ctx->in))
372 2120
                        l2 = ctx->in_e - ctx->in;
373 3884
                if (l2 == 0)
374 1110
                        return (VHD_MORE);
375 2774
                if (l2 > (ctx->out_e - ctx->out))
376 1008
                        l2 = ctx->out_e - ctx->out;
377 2774
                if (l2 == 0)
378 504
                        return (VHD_BUF);
379 2270
                memcpy(ctx->out, ctx->in, l2);
380 2270
                ctx->in += l2;
381 2270
                if (ctx->tbl != NULL && (s->arg2 & VHD_INCREMENTAL)) {
382 1222
                        switch (s->arg1) {
383
                        case VHD_NAME:
384 62
                                VHT_AppendName(ctx->tbl, ctx->out, l2);
385 62
                                break;
386
                        case VHD_VALUE:
387 1160
                                VHT_AppendValue(ctx->tbl, ctx->out, l2);
388 1160
                                break;
389
                        default:
390 0
                                WRONG("vhd_raw wrong arg1");
391
                                break;
392
                        }
393
                }
394 2270
                ctx->out += l2;
395 2270
                raw->l -= l2;
396
        }
397 756
        vhd_next_state(ctx->d);
398 756
        return (s->arg1);
399
}
400
401
static enum vhd_ret_e v_matchproto_(vhd_state_f)
402 1316
vhd_huffman(struct vhd_ctx *ctx, unsigned first)
403
{
404
        const struct vhd_state *s;
405
        struct vhd_huffman *huf;
406
        enum vhd_ret_e r;
407
        unsigned u, l;
408
409 1316
        AN(ctx);
410 1316
        assert(ctx->d->state < VHD_S__MAX);
411 1316
        s = &vhd_states[ctx->d->state];
412
413 1316
        huf = ctx->d->huffman;
414 1316
        if (first) {
415 134
                CHECK_OBJ_NOTNULL(ctx->d->integer, VHD_INT_MAGIC);
416 134
                l = ctx->d->integer->v;
417 134
                INIT_OBJ(huf, VHD_HUFFMAN_MAGIC);
418 134
                huf->len = l;
419
        }
420 1316
        CHECK_OBJ_NOTNULL(huf, VHD_HUFFMAN_MAGIC);
421
422 1316
        r = VHD_OK;
423 1316
        l = 0;
424
        while (1) {
425 3156
                assert(huf->pos < HUFDEC_LEN);
426 3156
                assert(hufdec[huf->pos].mask > 0);
427 3156
                assert(hufdec[huf->pos].mask <= 8);
428
429 3156
                if (huf->len > 0 && huf->blen < hufdec[huf->pos].mask) {
430
                        /* Refill from input */
431 1870
                        if (ctx->in == ctx->in_e) {
432 456
                                r = VHD_MORE;
433 456
                                break;
434
                        }
435 1414
                        huf->bits = (huf->bits << 8) | *ctx->in;
436 1414
                        huf->blen += 8;
437 1414
                        huf->len--;
438 1414
                        ctx->in++;
439
                }
440
441 2870
                if (huf->len == 0 && huf->pos == 0 && huf->blen <= 7 &&
442 170
                    huf->bits == (1U << huf->blen) - 1U) {
443
                        /* End of stream */
444 110
                        r = s->arg1;
445 110
                        vhd_next_state(ctx->d);
446 110
                        break;
447
                }
448
449 2590
                if (ctx->out + l == ctx->out_e) {
450 734
                        r = VHD_BUF;
451 734
                        break;
452
                }
453
454 1856
                if (huf->blen >= hufdec[huf->pos].mask)
455 1808
                        u = huf->bits >> (huf->blen - hufdec[huf->pos].mask);
456
                else
457 48
                        u = huf->bits << (hufdec[huf->pos].mask - huf->blen);
458 1856
                huf->pos += u;
459 1856
                assert(huf->pos < HUFDEC_LEN);
460
461 3704
                if (hufdec[huf->pos].len == 0 ||
462 1848
                    hufdec[huf->pos].len > huf->blen) {
463
                        /* Invalid or incomplete code */
464 16
                        r = VHD_ERR_HUF;
465 16
                        break;
466
                }
467
468 1840
                huf->blen -= hufdec[huf->pos].len;
469 1840
                huf->bits &= (1U << huf->blen) - 1U;
470
471 1840
                if (hufdec[huf->pos].jump) {
472 72
                        huf->pos += hufdec[huf->pos].jump;
473 72
                        assert(huf->pos < HUFDEC_LEN);
474
                } else {
475 1768
                        ctx->out[l++] = hufdec[huf->pos].chr;
476 1768
                        huf->pos = 0;
477
                }
478 1840
        }
479
480 1316
        if (l > 0 && ctx->tbl != NULL && (s->arg2 & VHD_INCREMENTAL)) {
481 1134
                switch (s->arg1) {
482
                case VHD_NAME:
483 60
                        VHT_AppendName(ctx->tbl, ctx->out, l);
484 60
                        break;
485
                case VHD_VALUE:
486 1074
                        VHT_AppendValue(ctx->tbl, ctx->out, l);
487 1074
                        break;
488
                default:
489 0
                        WRONG("vhd_raw wrong arg1");
490
                        break;
491
                }
492
        }
493 1316
        ctx->out += l;
494
495 1316
        assert(r != VHD_OK);
496 1316
        return (r);
497
}
498
499
/* Public interface */
500
501
const char *
502 12
VHD_Error(enum vhd_ret_e r)
503
{
504 12
        switch (r) {
505
#define VHD_RET(NAME, VAL, DESC)                        \
506
        case VHD_##NAME:                                \
507
                return ("VHD_" #NAME " (" DESC ")");
508
#include "tbl/vhd_return.h"
509
        default:
510 0
                return ("VHD_UNKNOWN");
511
        }
512
}
513
514
enum vhd_ret_e
515 7512
VHD_Decode(struct vhd_decode *d, struct vht_table *tbl,
516
    const uint8_t *in, size_t inlen, size_t *p_inused,
517
    char *out, size_t outlen, size_t *p_outused)
518
{
519
        const struct vhd_state *s;
520
        struct vhd_ctx ctx[1];
521
        enum vhd_ret_e ret;
522
        unsigned first;
523
524 7512
        CHECK_OBJ_NOTNULL(d, VHD_DECODE_MAGIC);
525 7512
        CHECK_OBJ_ORNULL(tbl, VHT_TABLE_MAGIC);
526 7512
        AN(in);
527 7512
        AN(p_inused);
528 7512
        AN(out);
529 7512
        AN(p_outused);
530
531 7512
        if (d->error < 0)
532 0
                return (d->error);
533
534 7512
        assert(*p_inused <= inlen);
535 7512
        assert(*p_outused <= outlen);
536
537 7512
        ctx->d = d;
538 7512
        ctx->tbl = tbl;
539 7512
        ctx->in = in + *p_inused;
540 7512
        ctx->in_e = in + inlen;
541 7512
        ctx->out = out + *p_outused;
542 7512
        ctx->out_e = out + outlen;
543
544
        do {
545 15714
                first = d->first;
546 15714
                d->first = 0;
547 15714
                assert(d->state < VHD_S__MAX);
548 15714
                s = &vhd_states[d->state];
549 15714
                switch (s->func) {
550
#define VHD_FSM_FUNC(NAME, func)                \
551
                case VHD_F_##NAME:              \
552
                        ret = func(ctx, first); \
553
                        break;
554
#include "tbl/vhd_fsm_funcs.h"
555
                default:
556 0
                        WRONG("Undefined vhd function");
557
                        break;
558
                }
559 15714
        } while (ret == VHD_AGAIN);
560
561 7512
        if (ret < 0)
562 28
                d->error = ret;
563
564 7512
        assert(in + *p_inused <= ctx->in);
565 7512
        *p_inused += ctx->in - (in + *p_inused);
566 7512
        assert(out + *p_outused <= ctx->out);
567 7512
        *p_outused += ctx->out - (out + *p_outused);
568
569 7512
        return (ret);
570
}
571
572
void
573 210
VHD_Init(struct vhd_decode *d)
574
{
575
576 210
        AN(d);
577
        assert(VHD_S__MAX <= UINT16_MAX);
578
        assert(HUFDEC_LEN <= UINT16_MAX);
579 210
        INIT_OBJ(d, VHD_DECODE_MAGIC);
580 210
        d->state = VHD_S_IDLE;
581 210
        d->first = 1;
582 210
}
583
584
/* Test driver */
585
586
#ifdef DECODE_TEST_DRIVER
587
588
#include <ctype.h>
589
#include <stdarg.h>
590
591
static int verbose = 0;
592
593
static size_t
594 208
hexbuf(uint8_t *buf, size_t buflen, const char *h)
595
{
596
        size_t l;
597
        uint8_t u;
598
599 208
        AN(h);
600 208
        AN(buf);
601
602 208
        l = 0;
603 11192
        for (; *h != '\0'; h++) {
604 10984
                if (l == buflen * 2)
605 0
                        WRONG("Too small buffer");
606 10984
                if (isspace(*h))
607 1992
                        continue;
608 8992
                if (*h >= '0' && *h <= '9')
609 6760
                        u = *h - '0';
610 2232
                else if (*h >= 'a' && *h <= 'f')
611 2232
                        u = 0xa + *h - 'a';
612 0
                else if (*h >= 'A' && *h <= 'F')
613 0
                        u = 0xa + *h - 'A';
614
                else
615 0
                        WRONG("Bad input character");
616 8992
                assert(u <= 0xf);
617 8992
                if (l % 2 == 0) {
618 4496
                        u <<= 4;
619 4496
                        buf[l / 2] = u;
620
                } else {
621 4496
                        buf[l / 2] |= u;
622
                }
623 8992
                l++;
624
        }
625 208
        AZ(l % 2);
626 208
        return (l / 2);
627
}
628
629
static int
630 144
match(const char *b, size_t l, ...)
631
{
632
        va_list ap;
633
        const char *e;
634
        const char *m;
635 144
        int r = 0;
636
637 144
        va_start(ap, l);
638 144
        e = b + l;
639
        while (1) {
640 1136
                m = va_arg(ap, const char *);
641 1136
                if (m == NULL)
642 144
                        break;
643 992
                l = strlen(m);
644 992
                if (e - b <= l || b[l] != '\0' || strncmp(b, m, l)) {
645 0
                        printf("%.*s != %s\n", (int)(e - b), b, m);
646 0
                        r = -1;
647 0
                        break;
648 992
                } else if (verbose) {
649 0
                        printf("%s == %s\n", b, m);
650
                }
651 992
                b += l + 1;
652 992
        }
653 144
        va_end(ap);
654 144
        return (r);
655
}
656
657
#define M_1IN (1U << 0)
658
#define M_1OUT (1U << 1)
659
660
static enum vhd_ret_e
661 208
decode(struct vhd_decode *d, struct vht_table *tbl, uint8_t *in, size_t in_l,
662
    char *out, size_t out_l, unsigned m)
663
{
664
        size_t in_u, out_u;
665
        enum vhd_ret_e r;
666
667 208
        CHECK_OBJ_NOTNULL(d, VHD_DECODE_MAGIC);
668 208
        AN(in);
669 208
        AN(out);
670
671 208
        in_u = 0;
672 208
        out_u = 0;
673
674
        while (1) {
675 22790
                r = VHD_Decode(d, tbl, in,
676 10722
                    (m & M_1IN ? (in_l > in_u ? in_u + 1 : in_u) : in_l),
677
                    &in_u,
678
                    out,
679 12068
                    (m & M_1OUT ? (out_l > out_u ? out_u + 1 : out_u) : out_l),
680
                    &out_u);
681 6802
                assert(in_u <= in_l);
682 6802
                assert(out_u <= out_l);
683 6802
                if (r < VHD_OK)
684 24
                        return (r);
685
686 6778
                switch (r) {
687
                case VHD_OK:
688 168
                        return (r);
689
690
                case VHD_MORE:
691 1628
                        if (in_u == in_l)
692 16
                                return (r);
693 1612
                        break;
694
695
                case VHD_BUF:
696 3966
                        if (out_u == out_l)
697 0
                                return (r);
698 3966
                        break;
699
700
                case VHD_NAME:
701
                case VHD_NAME_SEC:
702 520
                        assert(out_l - out_u > 0);
703 520
                        out[out_u++] = '\0';
704 520
                        if (verbose)
705 0
                                printf("Name%s: '%s'\n",
706
                                    (r == VHD_NAME_SEC ? " (sec)" : ""),
707
                                    out);
708 520
                        out += out_u;
709 520
                        out_l -= out_u;
710 520
                        out_u = 0;
711 520
                        break;
712
713
                case VHD_VALUE:
714
                case VHD_VALUE_SEC:
715 496
                        assert(out_l - out_u > 0);
716 496
                        out[out_u++] = '\0';
717 496
                        if (verbose)
718 0
                                printf("Value%s: '%s'\n",
719
                                    (r == VHD_VALUE_SEC ? " (sec)" : ""),
720
                                    out);
721 496
                        out += out_u;
722 496
                        out_l -= out_u;
723 496
                        out_u = 0;
724 496
                        break;
725
726
                default:
727 0
                        WRONG("Wrong return code");
728
                        break;
729
                }
730 6594
        }
731
732
        NEEDLESS(return (VHD_OK));
733
}
734
735
#define CHECK_RET(r, e)                                 \
736
        do {                                            \
737
                if (verbose || r != e) {                \
738
                        printf("%s %s %s\n",            \
739
                            VHD_Error(r),               \
740
                            (r == e ? "==" : "!="),     \
741
                            VHD_Error(e));              \
742
                }                                       \
743
                assert(r == e);                         \
744
        } while (0)
745
746
#define CHECK_INT(d, u)                                                 \
747
        do {                                                            \
748
                CHECK_OBJ_NOTNULL(d->integer, VHD_INT_MAGIC);           \
749
                if (verbose || d->integer->v != u) {                    \
750
                        printf("%u %s %u\n", d->integer->v,             \
751
                            (d->integer->v == u ? "==" : "!="),         \
752
                            u);                                         \
753
                }                                                       \
754
                assert(d->integer->v == u);                             \
755
        } while (0)
756
757
static void
758 8
test_integer(unsigned mode)
759
{
760
        struct vhd_decode d[1];
761
        uint8_t in[128];
762
        size_t in_l;
763
        char out[128];
764
        enum vhd_ret_e r;
765
766
        /* Test single byte decoding */
767 8
        VHD_Init(d);
768 8
        vhd_set_state(d, VHD_S_TEST_INT5);
769 8
        in_l = hexbuf(in, sizeof in, "1e");
770 8
        r = decode(d, NULL, in, in_l, out, sizeof out, mode);
771 8
        CHECK_RET(r, VHD_OK);
772 8
        CHECK_INT(d, 30);
773
774
        /* Test multibyte decoding */
775 8
        VHD_Init(d);
776 8
        vhd_set_state(d, VHD_S_TEST_INT5);
777 8
        in_l = hexbuf(in, sizeof in, "ff 9a 0a");
778 8
        r = decode(d, NULL, in, in_l, out, sizeof out, mode);
779 8
        CHECK_RET(r, VHD_OK);
780 8
        CHECK_INT(d, 1337);
781
782
        /* Test max size we allow */
783 8
        VHD_Init(d);
784 8
        vhd_set_state(d, VHD_S_TEST_INT5);
785 8
        in_l = hexbuf(in, sizeof in, "1f ff ff ff ff 07");
786 8
        r = decode(d, NULL, in, in_l, out, sizeof out, mode);
787 8
        CHECK_RET(r, VHD_OK);
788 8
        CHECK_INT(d, 0x8000001E);
789
790
        /* Test overflow */
791 8
        VHD_Init(d);
792 8
        vhd_set_state(d, VHD_S_TEST_INT5);
793 8
        in_l = hexbuf(in, sizeof in, "1f ff ff ff ff 08");
794 8
        r = decode(d, NULL, in, in_l, out, sizeof out, mode);
795 8
        CHECK_RET(r, VHD_ERR_INT);
796 8
}
797
798
static void
799 8
test_raw(unsigned mode)
800
{
801
        struct vhd_decode d[1];
802
        uint8_t in[128];
803
        size_t in_l;
804
        char out[128];
805
        enum vhd_ret_e r;
806
807
        /* Test raw encoding */
808 8
        VHD_Init(d);
809 8
        vhd_set_state(d, VHD_S_TEST_LITERAL);
810 8
        in_l = hexbuf(in, sizeof in,
811
            "0a63 7573 746f 6d2d 6b65 790d 6375 7374 6f6d 2d68 6561 6465 72");
812 8
        r = decode(d, NULL, in, in_l, out, sizeof out, mode);
813 8
        CHECK_RET(r, VHD_OK);
814 8
        AZ(match(out, sizeof out, "custom-key", "custom-header", NULL));
815
816
        /* Test too short input */
817 8
        VHD_Init(d);
818 8
        vhd_set_state(d, VHD_S_TEST_LITERAL);
819 8
        in_l = hexbuf(in, sizeof in,
820
            "02");
821 8
        r = decode(d, NULL, in, in_l, out, sizeof out, mode);
822 8
        CHECK_RET(r, VHD_MORE);
823 8
}
824
825
static void
826 8
test_huffman(unsigned mode)
827
{
828
        struct vhd_decode d[1];
829
        uint8_t in[256];
830
        size_t in_l;
831
        char out[256];
832
        enum vhd_ret_e r;
833
834
        /* Decode a huffman encoded value */
835 8
        VHD_Init(d);
836 8
        in_l = hexbuf(in, sizeof in,
837
            "0141 8cf1 e3c2 e5f2 3a6b a0ab 90f4 ff");
838 8
        vhd_set_state(d, VHD_S_TEST_LITERAL);
839 8
        r = decode(d, NULL, in, in_l, out, sizeof out, mode);
840 8
        CHECK_RET(r, VHD_OK);
841 8
        AZ(match(out, sizeof out, "A", "www.example.com", NULL));
842
843
        /* Decode an incomplete input buffer */
844 8
        VHD_Init(d);
845 8
        in_l = hexbuf(in, sizeof in,
846
            "0141 81");
847 8
        vhd_set_state(d, VHD_S_TEST_LITERAL);
848 8
        r = decode(d, NULL, in, in_l, out, sizeof out, mode);
849 8
        CHECK_RET(r, VHD_MORE);
850
851
        /* Decode an incomplete huffman code */
852 8
        VHD_Init(d);
853 8
        in_l = hexbuf(in, sizeof in,
854
            "0141 81 fe");
855 8
        vhd_set_state(d, VHD_S_TEST_LITERAL);
856 8
        r = decode(d, NULL, in, in_l, out, sizeof out, mode);
857 8
        CHECK_RET(r, VHD_ERR_HUF);
858
859
        /* Decode an invalid huffman code */
860 8
        VHD_Init(d);
861 8
        in_l = hexbuf(in, sizeof in,
862
            "0141 84 ff ff ff ff");
863 8
        vhd_set_state(d, VHD_S_TEST_LITERAL);
864 8
        r = decode(d, NULL, in, in_l, out, sizeof out, mode);
865 8
        CHECK_RET(r, VHD_ERR_HUF);
866 8
}
867
868
static void
869 8
test_c2(unsigned mode)
870
{
871
        struct vhd_decode d[1];
872
        uint8_t in[256];
873
        size_t in_l;
874
        char out[256];
875
        enum vhd_ret_e r;
876
877
        /* See RFC 7541 Appendix C.2 */
878
879 8
        VHD_Init(d);
880
881
        /* C.2.1 */
882 8
        in_l = hexbuf(in, sizeof in,
883
            "400a 6375 7374 6f6d 2d6b 6579 0d63 7573"
884
            "746f 6d2d 6865 6164 6572");
885 8
        r = decode(d, NULL, in, in_l, out, sizeof out, mode);
886 8
        CHECK_RET(r, VHD_OK);
887 8
        AZ(match(out, sizeof out,
888
                "custom-key", "custom-header",
889
                NULL));
890
891
        /* C.2.2 */
892 8
        in_l = hexbuf(in, sizeof in,
893
            "040c 2f73 616d 706c 652f 7061 7468");
894 8
        r = decode(d, NULL, in, in_l, out, sizeof out, mode);
895 8
        CHECK_RET(r, VHD_OK);
896 8
        AZ(match(out, sizeof out,
897
                ":path", "/sample/path",
898
                NULL));
899
900
        /* C.2.3 */
901 8
        in_l = hexbuf(in, sizeof in,
902
            "1008 7061 7373 776f 7264 0673 6563 7265"
903
            "74");
904 8
        r = decode(d, NULL, in, in_l, out, sizeof out, mode);
905 8
        CHECK_RET(r, VHD_OK);
906 8
        AZ(match(out, sizeof out,
907
                "password", "secret",
908
                NULL));
909
910
        /* C.2.4 */
911 8
        in_l = hexbuf(in, sizeof in,
912
            "82");
913 8
        r = decode(d, NULL, in, in_l, out, sizeof out, mode);
914 8
        CHECK_RET(r, VHD_OK);
915 8
        AZ(match(out, sizeof out,
916
                ":method", "GET",
917
                NULL));
918 8
}
919
920
static void
921 8
test_c3(unsigned mode)
922
{
923
        struct vht_table t[1];
924
        struct vhd_decode d[1];
925
        uint8_t in[256];
926
        size_t in_l;
927
        char out[256];
928
        enum vhd_ret_e r;
929
930
        /* See RFC 7541 Appendix C.3 */
931
932 8
        AZ(VHT_Init(t, 4096));
933 8
        VHD_Init(d);
934
935
        /* C.3.1 */
936 8
        in_l = hexbuf(in, sizeof in,
937
            "8286 8441 0f77 7777 2e65 7861 6d70 6c65"
938
            "2e63 6f6d");
939 8
        r = decode(d, t, in, in_l, out, sizeof out, mode);
940 8
        CHECK_RET(r, VHD_OK);
941 8
        AZ(match(out, sizeof out,
942
                ":method", "GET",
943
                ":scheme", "http",
944
                ":path", "/",
945
                ":authority", "www.example.com",
946
                NULL));
947
948
        /* C.3.2 */
949 8
        in_l = hexbuf(in, sizeof in,
950
            "8286 84be 5808 6e6f 2d63 6163 6865");
951 8
        r = decode(d, t, in, in_l, out, sizeof out, mode);
952 8
        CHECK_RET(r, VHD_OK);
953 8
        AZ(match(out, sizeof out,
954
                ":method", "GET",
955
                ":scheme", "http",
956
                ":path", "/",
957
                ":authority", "www.example.com",
958
                "cache-control", "no-cache",
959
                NULL));
960
961
        /* C.3.3 */
962 8
        in_l = hexbuf(in, sizeof in,
963
            "8287 85bf 400a 6375 7374 6f6d 2d6b 6579"
964
            "0c63 7573 746f 6d2d 7661 6c75 65");
965 8
        r = decode(d, t, in, in_l, out, sizeof out, mode);
966 8
        CHECK_RET(r, VHD_OK);
967 8
        AZ(match(out, sizeof out,
968
                ":method", "GET",
969
                ":scheme", "https",
970
                ":path", "/index.html",
971
                ":authority", "www.example.com",
972
                "custom-key", "custom-value",
973
                NULL));
974
975 8
        VHT_Fini(t);
976 8
}
977
978
static void
979 8
test_c4(unsigned mode)
980
{
981
        struct vht_table t[1];
982
        struct vhd_decode d[1];
983
        uint8_t in[256];
984
        size_t in_l;
985
        char out[256];
986
        enum vhd_ret_e r;
987
988
        /* See RFC 7541 Appendix C.4 */
989
990 8
        AZ(VHT_Init(t, 4096));
991 8
        VHD_Init(d);
992
993
        /* C.4.1 */
994 8
        in_l = hexbuf(in, sizeof in,
995
            "8286 8441 8cf1 e3c2 e5f2 3a6b a0ab 90f4 ff");
996 8
        r = decode(d, t, in, in_l, out, sizeof out, mode);
997 8
        CHECK_RET(r, VHD_OK);
998 8
        AZ(match(out, sizeof out,
999
                ":method", "GET",
1000
                ":scheme", "http",
1001
                ":path", "/",
1002
                ":authority", "www.example.com",
1003
                NULL));
1004
1005
        /* C.4.2 */
1006 8
        in_l = hexbuf(in, sizeof in,
1007
            "8286 84be 5886 a8eb 1064 9cbf");
1008 8
        r = decode(d, t, in, in_l, out, sizeof out, mode);
1009 8
        CHECK_RET(r, VHD_OK);
1010 8
        AZ(match(out, sizeof out,
1011
                ":method", "GET",
1012
                ":scheme", "http",
1013
                ":path", "/",
1014
                ":authority", "www.example.com",
1015
                "cache-control", "no-cache",
1016
                NULL));
1017
1018
        /* C.4.3 */
1019 8
        in_l = hexbuf(in, sizeof in,
1020
            "8287 85bf 4088 25a8 49e9 5ba9 7d7f 8925"
1021
            "a849 e95b b8e8 b4bf");
1022 8
        r = decode(d, t, in, in_l, out, sizeof out, mode);
1023 8
        CHECK_RET(r, VHD_OK);
1024 8
        AZ(match(out, sizeof out,
1025
                ":method", "GET",
1026
                ":scheme", "https",
1027
                ":path", "/index.html",
1028
                ":authority", "www.example.com",
1029
                "custom-key", "custom-value",
1030
                NULL));
1031
1032 8
        VHT_Fini(t);
1033 8
}
1034
1035
static void
1036 8
test_c5(unsigned mode)
1037
{
1038
        struct vht_table t[1];
1039
        struct vhd_decode d[1];
1040
        uint8_t in[256];
1041
        size_t in_l;
1042
        char out[256];
1043
        enum vhd_ret_e r;
1044
1045
        /* See RFC 7541 Appendix C.5 */
1046
1047 8
        AZ(VHT_Init(t, 256));
1048 8
        VHD_Init(d);
1049
1050
        /* C.5.1 */
1051 8
        in_l = hexbuf(in, sizeof in,
1052
            "4803 3330 3258 0770 7269 7661 7465 611d"
1053
            "4d6f 6e2c 2032 3120 4f63 7420 3230 3133"
1054
            "2032 303a 3133 3a32 3120 474d 546e 1768"
1055
            "7474 7073 3a2f 2f77 7777 2e65 7861 6d70"
1056
            "6c65 2e63 6f6d");
1057 8
        r = decode(d, t, in, in_l, out, sizeof out, mode);
1058 8
        CHECK_RET(r, VHD_OK);
1059 8
        AZ(match(out, sizeof out,
1060
                ":status", "302",
1061
                "cache-control", "private",
1062
                "date", "Mon, 21 Oct 2013 20:13:21 GMT",
1063
                "location", "https://www.example.com",
1064
                NULL));
1065
1066
        /* C.5.2 */
1067 8
        in_l = hexbuf(in, sizeof in,
1068
            "4803 3330 37c1 c0bf");
1069 8
        r = decode(d, t, in, in_l, out, sizeof out, mode);
1070 8
        CHECK_RET(r, VHD_OK);
1071 8
        AZ(match(out, sizeof out,
1072
                ":status", "307",
1073
                "cache-control", "private",
1074
                "date", "Mon, 21 Oct 2013 20:13:21 GMT",
1075
                "location", "https://www.example.com",
1076
                NULL));
1077
1078
        /* C.5.3 */
1079 8
        in_l = hexbuf(in, sizeof in,
1080
            "88c1 611d 4d6f 6e2c 2032 3120 4f63 7420"
1081
            "3230 3133 2032 303a 3133 3a32 3220 474d"
1082
            "54c0 5a04 677a 6970 7738 666f 6f3d 4153"
1083
            "444a 4b48 514b 425a 584f 5157 454f 5049"
1084
            "5541 5851 5745 4f49 553b 206d 6178 2d61"
1085
            "6765 3d33 3630 303b 2076 6572 7369 6f6e"
1086
            "3d31");
1087 8
        r = decode(d, t, in, in_l, out, sizeof out, mode);
1088 8
        CHECK_RET(r, VHD_OK);
1089 8
        AZ(match(out, sizeof out,
1090
                ":status", "200",
1091
                "cache-control", "private",
1092
                "date", "Mon, 21 Oct 2013 20:13:22 GMT",
1093
                "location", "https://www.example.com",
1094
                "content-encoding", "gzip",
1095
                "set-cookie",
1096
                "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1",
1097
                NULL));
1098
1099 8
        VHT_Fini(t);
1100 8
}
1101
1102
static void
1103 8
test_c6(unsigned mode)
1104
{
1105
        struct vht_table t[1];
1106
        struct vhd_decode d[1];
1107
        uint8_t in[256];
1108
        size_t in_l;
1109
        char out[256];
1110
        enum vhd_ret_e r;
1111
1112
        /* See RFC 7541 Appendix C.6 */
1113
1114 8
        AZ(VHT_Init(t, 256));
1115 8
        VHD_Init(d);
1116
1117
        /* C.6.1 */
1118 8
        in_l = hexbuf(in, sizeof in,
1119
            "4882 6402 5885 aec3 771a 4b61 96d0 7abe"
1120
            "9410 54d4 44a8 2005 9504 0b81 66e0 82a6"
1121
            "2d1b ff6e 919d 29ad 1718 63c7 8f0b 97c8"
1122
            "e9ae 82ae 43d3");
1123 8
        r = decode(d, t, in, in_l, out, sizeof out, mode);
1124 8
        CHECK_RET(r, VHD_OK);
1125 8
        AZ(match(out, sizeof out,
1126
                ":status", "302",
1127
                "cache-control", "private",
1128
                "date", "Mon, 21 Oct 2013 20:13:21 GMT",
1129
                "location", "https://www.example.com",
1130
                NULL));
1131
1132
        /* C.6.2 */
1133 8
        in_l = hexbuf(in, sizeof in,
1134
            "4883 640e ffc1 c0bf");
1135 8
        r = decode(d, t, in, in_l, out, sizeof out, mode);
1136 8
        CHECK_RET(r, VHD_OK);
1137 8
        AZ(match(out, sizeof out,
1138
                ":status", "307",
1139
                "cache-control", "private",
1140
                "date", "Mon, 21 Oct 2013 20:13:21 GMT",
1141
                "location", "https://www.example.com",
1142
                NULL));
1143
1144
        /* C.6.3 */
1145 8
        in_l = hexbuf(in, sizeof in,
1146
            "88c1 6196 d07a be94 1054 d444 a820 0595"
1147
            "040b 8166 e084 a62d 1bff c05a 839b d9ab"
1148
            "77ad 94e7 821d d7f2 e6c7 b335 dfdf cd5b"
1149
            "3960 d5af 2708 7f36 72c1 ab27 0fb5 291f"
1150
            "9587 3160 65c0 03ed 4ee5 b106 3d50 07");
1151 8
        r = decode(d, t, in, in_l, out, sizeof out, mode);
1152 8
        CHECK_RET(r, VHD_OK);
1153 8
        AZ(match(out, sizeof out,
1154
                ":status", "200",
1155
                "cache-control", "private",
1156
                "date", "Mon, 21 Oct 2013 20:13:22 GMT",
1157
                "location", "https://www.example.com",
1158
                "content-encoding", "gzip",
1159
                "set-cookie",
1160
                "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1",
1161
                NULL));
1162
1163 8
        VHT_Fini(t);
1164 8
}
1165
1166
#define do_test(name)                                           \
1167
        do {                                                    \
1168
                printf("Doing test: %s\n", #name);              \
1169
                name(0);                                        \
1170
                printf("Doing test: %s 1IN\n", #name);          \
1171
                name(M_1IN);                                    \
1172
                printf("Doing test: %s 1OUT\n", #name);         \
1173
                name(M_1OUT);                                   \
1174
                printf("Doing test: %s 1IN|1OUT\n", #name);     \
1175
                name(M_1IN|M_1OUT);                             \
1176
                printf("Test finished: %s\n\n", #name);         \
1177
        } while (0)
1178
1179
int
1180 2
main(int argc, char **argv)
1181
{
1182 2
        if (argc == 2 && !strcmp(argv[1], "-v"))
1183 0
                verbose = 1;
1184 2
        else if (argc != 1) {
1185 0
                fprintf(stderr, "Usage: %s [-v]\n", argv[0]);
1186 0
                return (1);
1187
        }
1188
1189 2
        if (verbose) {
1190 0
                printf("sizeof (struct vhd_int)=%zu\n",
1191
                    sizeof (struct vhd_int));
1192 0
                printf("sizeof (struct vhd_lookup)=%zu\n",
1193
                    sizeof (struct vhd_lookup));
1194 0
                printf("sizeof (struct vhd_raw)=%zu\n",
1195
                    sizeof (struct vhd_raw));
1196 0
                printf("sizeof (struct vhd_huffman)=%zu\n",
1197
                    sizeof (struct vhd_huffman));
1198 0
                printf("sizeof (struct vhd_decode)=%zu\n",
1199
                    sizeof (struct vhd_decode));
1200
        }
1201
1202 2
        do_test(test_integer);
1203 2
        do_test(test_raw);
1204 2
        do_test(test_huffman);
1205
1206 2
        do_test(test_c2);
1207 2
        do_test(test_c3);
1208 2
        do_test(test_c4);
1209 2
        do_test(test_c5);
1210 2
        do_test(test_c6);
1211
1212 2
        return (0);
1213
}
1214
1215
#endif  /* DECODE_TEST_DRIVER */