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 5941
vhd_set_state(struct vhd_decode *d, enum vhd_state_e state)
93
{
94 5941
        AN(d);
95 5941
        assert(state > VHD_S__MIN && state < VHD_S__MAX);
96 5941
        d->state = state;
97 5941
        d->first = 1;
98 5941
}
99
100
static void
101 4184
vhd_next_state(struct vhd_decode *d)
102
{
103 4184
        AN(d);
104 4184
        assert(d->state + 1 < VHD_S__MAX);
105 4184
        vhd_set_state(d, d->state + 1);
106 4184
}
107
108
/* State functions */
109
static enum vhd_ret_e v_matchproto_(vhd_state_f)
110 1052
vhd_skip(struct vhd_ctx *ctx, unsigned first)
111
{
112 1052
        AN(ctx);
113 1052
        AN(first);
114 1052
        vhd_next_state(ctx->d);
115 1052
        return (VHD_AGAIN);
116
}
117
118
static enum vhd_ret_e v_matchproto_(vhd_state_f)
119 970
vhd_goto(struct vhd_ctx *ctx, unsigned first)
120
{
121
        const struct vhd_state *s;
122
123 970
        AN(ctx);
124 970
        AN(first);
125 970
        assert(ctx->d->state < VHD_S__MAX);
126 970
        s = &vhd_states[ctx->d->state];
127 970
        assert(s->arg1 < VHD_S__MAX);
128 970
        vhd_set_state(ctx->d, s->arg1);
129 970
        return (VHD_AGAIN);
130
}
131
132
static enum vhd_ret_e v_matchproto_(vhd_state_f)
133 605
vhd_idle(struct vhd_ctx *ctx, unsigned first)
134
{
135
        uint8_t c;
136
137 605
        AN(ctx);
138
        (void)first;
139
140 1210
        while (ctx->in < ctx->in_e) {
141 459
                c = *ctx->in;
142 459
                if ((c & 0x80) == 0x80)
143 150
                        vhd_set_state(ctx->d, VHD_S_HP61_START);
144 309
                else if ((c & 0xc0) == 0x40)
145 96
                        vhd_set_state(ctx->d, VHD_S_HP621_START);
146 213
                else if ((c & 0xf0) == 0x00)
147 208
                        vhd_set_state(ctx->d, VHD_S_HP622_START);
148 5
                else if ((c & 0xf0) == 0x10)
149 5
                        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 459
                return (VHD_AGAIN);
155
        }
156
157 146
        return (VHD_OK);
158
}
159
160
static enum vhd_ret_e v_matchproto_(vhd_state_f)
161 1073
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 1073
        AN(ctx);
171 1073
        assert(ctx->d->state < VHD_S__MAX);
172 1073
        s = &vhd_states[ctx->d->state];
173 1073
        i = ctx->d->integer;
174
175 1073
        if (first) {
176 1049
                INIT_OBJ(i, VHD_INT_MAGIC);
177 1049
                i->pfx = s->arg1;
178 1049
                assert(i->pfx >= 4 && i->pfx <= 7);
179
        }
180 1073
        CHECK_OBJ_NOTNULL(i, VHD_INT_MAGIC);
181
182 2205
        while (ctx->in < ctx->in_e) {
183 1108
                c = *ctx->in;
184 1108
                ctx->in++;
185 1108
                if (i->pfx) {
186 1049
                        mask = (1U << i->pfx) - 1;
187 1049
                        i->pfx = 0;
188 1049
                        i->v = c & mask;
189 1049
                        if (i->v < mask) {
190 1034
                                vhd_next_state(ctx->d);
191 1034
                                return (VHD_AGAIN);
192
                        }
193
                } else {
194 59
                        if ((i->m == 28 && (c & 0x78)) || i->m > 28)
195 6
                                return (VHD_ERR_INT);
196 53
                        i->v += (c & 0x7f) * ((uint32_t)1 << i->m);
197 53
                        i->m += 7;
198 53
                        if (!(c & 0x80)) {
199 9
                                vhd_next_state(ctx->d);
200 9
                                return (VHD_AGAIN);
201
                        }
202
                }
203
        }
204 24
        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 457
vhd_set_idx(struct vhd_ctx *ctx, unsigned first)
223
{
224 457
        AN(ctx);
225 457
        AN(first);
226 457
        CHECK_OBJ_NOTNULL(ctx->d->integer, VHD_INT_MAGIC);
227 457
        ctx->d->index = ctx->d->integer->v;
228 457
        vhd_next_state(ctx->d);
229 457
        return (VHD_AGAIN);
230
}
231
232
static enum vhd_ret_e v_matchproto_(vhd_state_f)
233 1748
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 1748
        AN(ctx);
241 1748
        assert(ctx->d->state < VHD_S__MAX);
242 1748
        s = &vhd_states[ctx->d->state];
243 1748
        lu = ctx->d->lookup;
244
245 1748
        if (first)
246 384
                INIT_OBJ(lu, VHD_LOOKUP_MAGIC);
247 1748
        CHECK_OBJ_NOTNULL(lu, VHD_LOOKUP_MAGIC);
248
249 1748
        switch (s->arg1) {
250
        case VHD_NAME:
251
        case VHD_NAME_SEC:
252 1036
                p = VHT_LookupName(ctx->tbl, ctx->d->index, &l);
253 1036
                break;
254
        case VHD_VALUE:
255
        case VHD_VALUE_SEC:
256 712
                p = VHT_LookupValue(ctx->tbl, ctx->d->index, &l);
257 712
                break;
258
        default:
259 0
                WRONG("vhd_lookup wrong arg1");
260
                break;
261
        }
262 1748
        if (first && p == NULL)
263 0
                return (VHD_ERR_IDX);
264 1748
        AN(p);
265 1748
        assert(l <= UINT_MAX);
266 1748
        if (first)
267 384
                lu->l = l;
268
269 1748
        assert(lu->l <= l);
270 1748
        p += l - lu->l;
271 1748
        l = lu->l;
272 1748
        if (l > ctx->out_e - ctx->out)
273 1364
                l = ctx->out_e - ctx->out;
274 1748
        memcpy(ctx->out, p, l);
275 1748
        ctx->out += l;
276 1748
        lu->l -= l;
277
278 1748
        if (lu->l == 0) {
279 384
                vhd_next_state(ctx->d);
280 384
                return (s->arg1);
281
        }
282 1364
        assert(ctx->out == ctx->out_e);
283 1364
        return (VHD_BUF);
284
}
285
286
static enum vhd_ret_e v_matchproto_(vhd_state_f)
287 13
vhd_new(struct vhd_ctx *ctx, unsigned first)
288
{
289 13
        AN(ctx);
290 13
        AN(first);
291 13
        if (ctx->tbl != NULL)
292 9
                VHT_NewEntry(ctx->tbl);
293 13
        vhd_next_state(ctx->d);
294 13
        return (VHD_AGAIN);
295
}
296
297
static enum vhd_ret_e v_matchproto_(vhd_state_f)
298 83
vhd_new_idx(struct vhd_ctx *ctx, unsigned first)
299
{
300 83
        AN(ctx);
301 83
        AN(first);
302 83
        if (ctx->tbl != NULL) {
303 83
                if (VHT_NewEntry_Indexed(ctx->tbl, ctx->d->index))
304 0
                        return (VHD_ERR_IDX);
305
        }
306 83
        vhd_next_state(ctx->d);
307 83
        return (VHD_AGAIN);
308
}
309
310
static enum vhd_ret_e v_matchproto_(vhd_state_f)
311 309
vhd_branch_zidx(struct vhd_ctx *ctx, unsigned first)
312
{
313
        const struct vhd_state *s;
314
315 309
        AN(ctx);
316
        (void)first;
317 309
        assert(ctx->d->state < VHD_S__MAX);
318 309
        s = &vhd_states[ctx->d->state];
319 309
        assert(s->arg1 < VHD_S__MAX);
320
321 309
        if (ctx->d->index == 0)
322 221
                vhd_set_state(ctx->d, s->arg1);
323
        else
324 88
                vhd_next_state(ctx->d);
325 309
        return (VHD_AGAIN);
326
}
327
328
static enum vhd_ret_e v_matchproto_(vhd_state_f)
329 582
vhd_branch_bit0(struct vhd_ctx *ctx, unsigned first)
330
{
331
        const struct vhd_state *s;
332
333 582
        AN(ctx);
334
        (void)first;
335 582
        assert(ctx->d->state < VHD_S__MAX);
336 582
        s = &vhd_states[ctx->d->state];
337 582
        assert(s->arg1 < VHD_S__MAX);
338
339 582
        if (ctx->in == ctx->in_e)
340 8
                return (VHD_MORE);
341
342 574
        if (*ctx->in & 0x80)
343 67
                vhd_set_state(ctx->d, s->arg1);
344
        else
345 507
                vhd_next_state(ctx->d);
346 574
        return (VHD_AGAIN);
347
}
348
349
static enum vhd_ret_e v_matchproto_(vhd_state_f)
350 1309
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 1309
        AN(ctx);
357 1309
        assert(ctx->d->state < VHD_S__MAX);
358 1309
        s = &vhd_states[ctx->d->state];
359
360 1309
        raw = ctx->d->raw;
361 1309
        if (first) {
362 507
                CHECK_OBJ_NOTNULL(ctx->d->integer, VHD_INT_MAGIC);
363 507
                l2 = ctx->d->integer->v;
364 507
                INIT_OBJ(raw, VHD_RAW_MAGIC);
365 507
                raw->l = l2;
366
        }
367 1309
        CHECK_OBJ_NOTNULL(raw, VHD_RAW_MAGIC);
368
369 3877
        while (raw->l > 0) {
370 2066
                l2 = raw->l;
371 2066
                if (l2 > (ctx->in_e - ctx->in))
372 1060
                        l2 = ctx->in_e - ctx->in;
373 2066
                if (l2 == 0)
374 555
                        return (VHD_MORE);
375 1511
                if (l2 > (ctx->out_e - ctx->out))
376 504
                        l2 = ctx->out_e - ctx->out;
377 1511
                if (l2 == 0)
378 252
                        return (VHD_BUF);
379 1259
                memcpy(ctx->out, ctx->in, l2);
380 1259
                ctx->in += l2;
381 1259
                if (ctx->tbl != NULL && (s->arg2 & VHD_INCREMENTAL)) {
382 611
                        switch (s->arg1) {
383
                        case VHD_NAME:
384 31
                                VHT_AppendName(ctx->tbl, ctx->out, l2);
385 31
                                break;
386
                        case VHD_VALUE:
387 580
                                VHT_AppendValue(ctx->tbl, ctx->out, l2);
388 580
                                break;
389
                        default:
390 0
                                WRONG("vhd_raw wrong arg1");
391
                                break;
392
                        }
393
                }
394 1259
                ctx->out += l2;
395 1259
                raw->l -= l2;
396
        }
397 502
        vhd_next_state(ctx->d);
398 502
        return (s->arg1);
399
}
400
401
static enum vhd_ret_e v_matchproto_(vhd_state_f)
402 658
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 658
        AN(ctx);
410 658
        assert(ctx->d->state < VHD_S__MAX);
411 658
        s = &vhd_states[ctx->d->state];
412
413 658
        huf = ctx->d->huffman;
414 658
        if (first) {
415 67
                CHECK_OBJ_NOTNULL(ctx->d->integer, VHD_INT_MAGIC);
416 67
                l = ctx->d->integer->v;
417 67
                INIT_OBJ(huf, VHD_HUFFMAN_MAGIC);
418 67
                huf->len = l;
419
        }
420 658
        CHECK_OBJ_NOTNULL(huf, VHD_HUFFMAN_MAGIC);
421
422 658
        r = VHD_OK;
423 658
        l = 0;
424
        while (1) {
425 2498
                assert(huf->pos < HUFDEC_LEN);
426 1578
                assert(hufdec[huf->pos].mask > 0);
427 1578
                assert(hufdec[huf->pos].mask <= 8);
428
429 1578
                if (huf->len > 0 && huf->blen < hufdec[huf->pos].mask) {
430
                        /* Refill from input */
431 935
                        if (ctx->in == ctx->in_e) {
432 228
                                r = VHD_MORE;
433 228
                                break;
434
                        }
435 707
                        huf->bits = (huf->bits << 8) | *ctx->in;
436 707
                        huf->blen += 8;
437 707
                        huf->len--;
438 707
                        ctx->in++;
439
                }
440
441 1435
                if (huf->len == 0 && huf->pos == 0 && huf->blen <= 7 &&
442 85
                    huf->bits == (1U << huf->blen) - 1U) {
443
                        /* End of stream */
444 55
                        r = s->arg1;
445 55
                        vhd_next_state(ctx->d);
446 55
                        break;
447
                }
448
449 1295
                if (ctx->out + l == ctx->out_e) {
450 367
                        r = VHD_BUF;
451 367
                        break;
452
                }
453
454 928
                if (huf->blen >= hufdec[huf->pos].mask)
455 904
                        u = huf->bits >> (huf->blen - hufdec[huf->pos].mask);
456
                else
457 24
                        u = huf->bits << (hufdec[huf->pos].mask - huf->blen);
458 928
                huf->pos += u;
459 928
                assert(huf->pos < HUFDEC_LEN);
460
461 1852
                if (hufdec[huf->pos].len == 0 ||
462 924
                    hufdec[huf->pos].len > huf->blen) {
463
                        /* Invalid or incomplete code */
464 8
                        r = VHD_ERR_HUF;
465 8
                        break;
466
                }
467
468 920
                huf->blen -= hufdec[huf->pos].len;
469 920
                huf->bits &= (1U << huf->blen) - 1U;
470
471 920
                if (hufdec[huf->pos].jump) {
472 36
                        huf->pos += hufdec[huf->pos].jump;
473 36
                        assert(huf->pos < HUFDEC_LEN);
474
                } else {
475 884
                        ctx->out[l++] = hufdec[huf->pos].chr;
476 884
                        huf->pos = 0;
477
                }
478
        }
479
480 658
        if (l > 0 && ctx->tbl != NULL && (s->arg2 & VHD_INCREMENTAL)) {
481 567
                switch (s->arg1) {
482
                case VHD_NAME:
483 30
                        VHT_AppendName(ctx->tbl, ctx->out, l);
484 30
                        break;
485
                case VHD_VALUE:
486 537
                        VHT_AppendValue(ctx->tbl, ctx->out, l);
487 537
                        break;
488
                default:
489 0
                        WRONG("vhd_raw wrong arg1");
490
                        break;
491
                }
492
        }
493 658
        ctx->out += l;
494
495 658
        assert(r != VHD_OK);
496 658
        return (r);
497
}
498
499
/* Public interface */
500
501
const char *
502 9
VHD_Error(enum vhd_ret_e r)
503
{
504 9
        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 3899
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 3899
        CHECK_OBJ_NOTNULL(d, VHD_DECODE_MAGIC);
525 3899
        CHECK_OBJ_ORNULL(tbl, VHT_TABLE_MAGIC);
526 3899
        AN(in);
527 3899
        AN(p_inused);
528 3899
        AN(out);
529 3899
        AN(p_outused);
530
531 3899
        if (d->error < 0)
532 0
                return (d->error);
533
534 3899
        assert(*p_inused <= inlen);
535 3899
        assert(*p_outused <= outlen);
536
537 3899
        ctx->d = d;
538 3899
        ctx->tbl = tbl;
539 3899
        ctx->in = in + *p_inused;
540 3899
        ctx->in_e = in + inlen;
541 3899
        ctx->out = out + *p_outused;
542 3899
        ctx->out_e = out + outlen;
543
544
        do {
545 8859
                first = d->first;
546 8859
                d->first = 0;
547 8859
                assert(d->state < VHD_S__MAX);
548 8859
                s = &vhd_states[d->state];
549 8859
                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 8859
        } while (ret == VHD_AGAIN);
560
561 3899
        if (ret < 0)
562 14
                d->error = ret;
563
564 3899
        assert(in + *p_inused <= ctx->in);
565 3899
        *p_inused += ctx->in - (in + *p_inused);
566 3899
        assert(out + *p_outused <= ctx->out);
567 3899
        *p_outused += ctx->out - (out + *p_outused);
568
569 3899
        return (ret);
570
}
571
572
void
573 127
VHD_Init(struct vhd_decode *d)
574
{
575
576 127
        AN(d);
577
        assert(VHD_S__MAX <= UINT16_MAX);
578
        assert(HUFDEC_LEN <= UINT16_MAX);
579 127
        INIT_OBJ(d, VHD_DECODE_MAGIC);
580 127
        d->state = VHD_S_IDLE;
581 127
        d->first = 1;
582 127
}
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 104
hexbuf(uint8_t *buf, size_t buflen, const char *h)
595
{
596
        size_t l;
597
        uint8_t u;
598
599 104
        AN(h);
600 104
        AN(buf);
601
602 104
        l = 0;
603 5596
        for (; *h != '\0'; h++) {
604 5492
                if (l == buflen * 2)
605 0
                        WRONG("Too small buffer");
606 5492
                if (isspace(*h))
607 996
                        continue;
608 4496
                if (*h >= '0' && *h <= '9')
609 3380
                        u = *h - '0';
610 1116
                else if (*h >= 'a' && *h <= 'f')
611 1116
                        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 4496
                assert(u <= 0xf);
617 4496
                if (l % 2 == 0) {
618 2248
                        u <<= 4;
619 2248
                        buf[l / 2] = u;
620
                } else {
621 2248
                        buf[l / 2] |= u;
622
                }
623 4496
                l++;
624
        }
625 104
        AZ(l % 2);
626 104
        return (l / 2);
627
}
628
629
static int
630 72
match(const char *b, size_t l, ...)
631
{
632
        va_list ap;
633
        const char *e;
634
        const char *m;
635 72
        int r = 0;
636
637 72
        va_start(ap, l);
638 72
        e = b + l;
639
        while (1) {
640 1064
                m = va_arg(ap, const char *);
641 568
                if (m == NULL)
642 72
                        break;
643 496
                l = strlen(m);
644 496
                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 496
                } else if (verbose) {
649 0
                        printf("%s == %s\n", b, m);
650
                }
651 496
                b += l + 1;
652
        }
653 72
        va_end(ap);
654 72
        return (r);
655
}
656
657
#define M_1IN (1U << 0)
658
#define M_1OUT (1U << 1)
659
660
static enum vhd_ret_e
661 104
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 104
        CHECK_OBJ_NOTNULL(d, VHD_DECODE_MAGIC);
668 104
        AN(in);
669 104
        AN(out);
670
671 104
        in_u = 0;
672 104
        out_u = 0;
673
674
        while (1) {
675 14692
                r = VHD_Decode(d, tbl, in,
676 5361
                    (m & M_1IN ? (in_l > in_u ? in_u + 1 : in_u) : in_l),
677
                    &in_u,
678
                    out,
679 6034
                    (m & M_1OUT ? (out_l > out_u ? out_u + 1 : out_u) : out_l),
680
                    &out_u);
681 3401
                assert(in_u <= in_l);
682 3401
                assert(out_u <= out_l);
683 3401
                if (r < VHD_OK)
684 12
                        return (r);
685
686 3389
                switch (r) {
687
                case VHD_OK:
688 84
                        return (r);
689
690
                case VHD_MORE:
691 814
                        if (in_u == in_l)
692 8
                                return (r);
693 806
                        break;
694
695
                case VHD_BUF:
696 1983
                        if (out_u == out_l)
697 0
                                return (r);
698 1983
                        break;
699
700
                case VHD_NAME:
701
                case VHD_NAME_SEC:
702 260
                        assert(out_l - out_u > 0);
703 260
                        out[out_u++] = '\0';
704 260
                        if (verbose)
705 0
                                printf("Name%s: '%s'\n",
706
                                    (r == VHD_NAME_SEC ? " (sec)" : ""),
707
                                    out);
708 260
                        out += out_u;
709 260
                        out_l -= out_u;
710 260
                        out_u = 0;
711 260
                        break;
712
713
                case VHD_VALUE:
714
                case VHD_VALUE_SEC:
715 248
                        assert(out_l - out_u > 0);
716 248
                        out[out_u++] = '\0';
717 248
                        if (verbose)
718 0
                                printf("Value%s: '%s'\n",
719
                                    (r == VHD_VALUE_SEC ? " (sec)" : ""),
720
                                    out);
721 248
                        out += out_u;
722 248
                        out_l -= out_u;
723 248
                        out_u = 0;
724 248
                        break;
725
726
                default:
727 0
                        WRONG("Wrong return code");
728
                        break;
729
                }
730
        }
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 4
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 4
        VHD_Init(d);
768 4
        vhd_set_state(d, VHD_S_TEST_INT5);
769 4
        in_l = hexbuf(in, sizeof in, "1e");
770 4
        r = decode(d, NULL, in, in_l, out, sizeof out, mode);
771 4
        CHECK_RET(r, VHD_OK);
772 4
        CHECK_INT(d, 30);
773
774
        /* Test multibyte decoding */
775 4
        VHD_Init(d);
776 4
        vhd_set_state(d, VHD_S_TEST_INT5);
777 4
        in_l = hexbuf(in, sizeof in, "ff 9a 0a");
778 4
        r = decode(d, NULL, in, in_l, out, sizeof out, mode);
779 4
        CHECK_RET(r, VHD_OK);
780 4
        CHECK_INT(d, 1337);
781
782
        /* Test max size we allow */
783 4
        VHD_Init(d);
784 4
        vhd_set_state(d, VHD_S_TEST_INT5);
785 4
        in_l = hexbuf(in, sizeof in, "1f ff ff ff ff 07");
786 4
        r = decode(d, NULL, in, in_l, out, sizeof out, mode);
787 4
        CHECK_RET(r, VHD_OK);
788 4
        CHECK_INT(d, 0x8000001E);
789
790
        /* Test overflow */
791 4
        VHD_Init(d);
792 4
        vhd_set_state(d, VHD_S_TEST_INT5);
793 4
        in_l = hexbuf(in, sizeof in, "1f ff ff ff ff 08");
794 4
        r = decode(d, NULL, in, in_l, out, sizeof out, mode);
795 4
        CHECK_RET(r, VHD_ERR_INT);
796 4
}
797
798
static void
799 4
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 4
        VHD_Init(d);
809 4
        vhd_set_state(d, VHD_S_TEST_LITERAL);
810 4
        in_l = hexbuf(in, sizeof in,
811
            "0a63 7573 746f 6d2d 6b65 790d 6375 7374 6f6d 2d68 6561 6465 72");
812 4
        r = decode(d, NULL, in, in_l, out, sizeof out, mode);
813 4
        CHECK_RET(r, VHD_OK);
814 4
        AZ(match(out, sizeof out, "custom-key", "custom-header", NULL));
815
816
        /* Test too short input */
817 4
        VHD_Init(d);
818 4
        vhd_set_state(d, VHD_S_TEST_LITERAL);
819 4
        in_l = hexbuf(in, sizeof in,
820
            "02");
821 4
        r = decode(d, NULL, in, in_l, out, sizeof out, mode);
822 4
        CHECK_RET(r, VHD_MORE);
823 4
}
824
825
static void
826 4
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 4
        VHD_Init(d);
836 4
        in_l = hexbuf(in, sizeof in,
837
            "0141 8cf1 e3c2 e5f2 3a6b a0ab 90f4 ff");
838 4
        vhd_set_state(d, VHD_S_TEST_LITERAL);
839 4
        r = decode(d, NULL, in, in_l, out, sizeof out, mode);
840 4
        CHECK_RET(r, VHD_OK);
841 4
        AZ(match(out, sizeof out, "A", "www.example.com", NULL));
842
843
        /* Decode an incomplete input buffer */
844 4
        VHD_Init(d);
845 4
        in_l = hexbuf(in, sizeof in,
846
            "0141 81");
847 4
        vhd_set_state(d, VHD_S_TEST_LITERAL);
848 4
        r = decode(d, NULL, in, in_l, out, sizeof out, mode);
849 4
        CHECK_RET(r, VHD_MORE);
850
851
        /* Decode an incomplete huffman code */
852 4
        VHD_Init(d);
853 4
        in_l = hexbuf(in, sizeof in,
854
            "0141 81 fe");
855 4
        vhd_set_state(d, VHD_S_TEST_LITERAL);
856 4
        r = decode(d, NULL, in, in_l, out, sizeof out, mode);
857 4
        CHECK_RET(r, VHD_ERR_HUF);
858
859
        /* Decode an invalid huffman code */
860 4
        VHD_Init(d);
861 4
        in_l = hexbuf(in, sizeof in,
862
            "0141 84 ff ff ff ff");
863 4
        vhd_set_state(d, VHD_S_TEST_LITERAL);
864 4
        r = decode(d, NULL, in, in_l, out, sizeof out, mode);
865 4
        CHECK_RET(r, VHD_ERR_HUF);
866 4
}
867
868
static void
869 4
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 4
        VHD_Init(d);
880
881
        /* C.2.1 */
882 4
        in_l = hexbuf(in, sizeof in,
883
            "400a 6375 7374 6f6d 2d6b 6579 0d63 7573"
884
            "746f 6d2d 6865 6164 6572");
885 4
        r = decode(d, NULL, in, in_l, out, sizeof out, mode);
886 4
        CHECK_RET(r, VHD_OK);
887 4
        AZ(match(out, sizeof out,
888
                "custom-key", "custom-header",
889
                NULL));
890
891
        /* C.2.2 */
892 4
        in_l = hexbuf(in, sizeof in,
893
            "040c 2f73 616d 706c 652f 7061 7468");
894 4
        r = decode(d, NULL, in, in_l, out, sizeof out, mode);
895 4
        CHECK_RET(r, VHD_OK);
896 4
        AZ(match(out, sizeof out,
897
                ":path", "/sample/path",
898
                NULL));
899
900
        /* C.2.3 */
901 4
        in_l = hexbuf(in, sizeof in,
902
            "1008 7061 7373 776f 7264 0673 6563 7265"
903
            "74");
904 4
        r = decode(d, NULL, in, in_l, out, sizeof out, mode);
905 4
        CHECK_RET(r, VHD_OK);
906 4
        AZ(match(out, sizeof out,
907
                "password", "secret",
908
                NULL));
909
910
        /* C.2.4 */
911 4
        in_l = hexbuf(in, sizeof in,
912
            "82");
913 4
        r = decode(d, NULL, in, in_l, out, sizeof out, mode);
914 4
        CHECK_RET(r, VHD_OK);
915 4
        AZ(match(out, sizeof out,
916
                ":method", "GET",
917
                NULL));
918 4
}
919
920
static void
921 4
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 4
        AZ(VHT_Init(t, 4096));
933 4
        VHD_Init(d);
934
935
        /* C.3.1 */
936 4
        in_l = hexbuf(in, sizeof in,
937
            "8286 8441 0f77 7777 2e65 7861 6d70 6c65"
938
            "2e63 6f6d");
939 4
        r = decode(d, t, in, in_l, out, sizeof out, mode);
940 4
        CHECK_RET(r, VHD_OK);
941 4
        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 4
        in_l = hexbuf(in, sizeof in,
950
            "8286 84be 5808 6e6f 2d63 6163 6865");
951 4
        r = decode(d, t, in, in_l, out, sizeof out, mode);
952 4
        CHECK_RET(r, VHD_OK);
953 4
        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 4
        in_l = hexbuf(in, sizeof in,
963
            "8287 85bf 400a 6375 7374 6f6d 2d6b 6579"
964
            "0c63 7573 746f 6d2d 7661 6c75 65");
965 4
        r = decode(d, t, in, in_l, out, sizeof out, mode);
966 4
        CHECK_RET(r, VHD_OK);
967 4
        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 4
        VHT_Fini(t);
976 4
}
977
978
static void
979 4
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 4
        AZ(VHT_Init(t, 4096));
991 4
        VHD_Init(d);
992
993
        /* C.4.1 */
994 4
        in_l = hexbuf(in, sizeof in,
995
            "8286 8441 8cf1 e3c2 e5f2 3a6b a0ab 90f4 ff");
996 4
        r = decode(d, t, in, in_l, out, sizeof out, mode);
997 4
        CHECK_RET(r, VHD_OK);
998 4
        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 4
        in_l = hexbuf(in, sizeof in,
1007
            "8286 84be 5886 a8eb 1064 9cbf");
1008 4
        r = decode(d, t, in, in_l, out, sizeof out, mode);
1009 4
        CHECK_RET(r, VHD_OK);
1010 4
        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 4
        in_l = hexbuf(in, sizeof in,
1020
            "8287 85bf 4088 25a8 49e9 5ba9 7d7f 8925"
1021
            "a849 e95b b8e8 b4bf");
1022 4
        r = decode(d, t, in, in_l, out, sizeof out, mode);
1023 4
        CHECK_RET(r, VHD_OK);
1024 4
        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 4
        VHT_Fini(t);
1033 4
}
1034
1035
static void
1036 4
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 4
        AZ(VHT_Init(t, 256));
1048 4
        VHD_Init(d);
1049
1050
        /* C.5.1 */
1051 4
        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 4
        r = decode(d, t, in, in_l, out, sizeof out, mode);
1058 4
        CHECK_RET(r, VHD_OK);
1059 4
        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 4
        in_l = hexbuf(in, sizeof in,
1068
            "4803 3330 37c1 c0bf");
1069 4
        r = decode(d, t, in, in_l, out, sizeof out, mode);
1070 4
        CHECK_RET(r, VHD_OK);
1071 4
        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 4
        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 4
        r = decode(d, t, in, in_l, out, sizeof out, mode);
1088 4
        CHECK_RET(r, VHD_OK);
1089 4
        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 4
        VHT_Fini(t);
1100 4
}
1101
1102
static void
1103 4
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 4
        AZ(VHT_Init(t, 256));
1115 4
        VHD_Init(d);
1116
1117
        /* C.6.1 */
1118 4
        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 4
        r = decode(d, t, in, in_l, out, sizeof out, mode);
1124 4
        CHECK_RET(r, VHD_OK);
1125 4
        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 4
        in_l = hexbuf(in, sizeof in,
1134
            "4883 640e ffc1 c0bf");
1135 4
        r = decode(d, t, in, in_l, out, sizeof out, mode);
1136 4
        CHECK_RET(r, VHD_OK);
1137 4
        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 4
        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 4
        r = decode(d, t, in, in_l, out, sizeof out, mode);
1152 4
        CHECK_RET(r, VHD_OK);
1153 4
        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 4
        VHT_Fini(t);
1164 4
}
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 1
main(int argc, char **argv)
1181
{
1182 1
        if (argc == 2 && !strcmp(argv[1], "-v"))
1183 0
                verbose = 1;
1184 1
        else if (argc != 1) {
1185 0
                fprintf(stderr, "Usage: %s [-v]\n", argv[0]);
1186 0
                return (1);
1187
        }
1188
1189 1
        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 1
        do_test(test_integer);
1203 1
        do_test(test_raw);
1204 1
        do_test(test_huffman);
1205
1206 1
        do_test(test_c2);
1207 1
        do_test(test_c3);
1208 1
        do_test(test_c4);
1209 1
        do_test(test_c5);
1210 1
        do_test(test_c6);
1211
1212 1
        return (0);
1213
}
1214
1215
#endif  /* DECODE_TEST_DRIVER */