1 /*
2 * nghttp3
3 *
4 * Copyright (c) 2019 nghttp3 contributors
5 * Copyright (c) 2013 nghttp2 contributors
6 *
7 * Permission is hereby granted, free of charge, to any person obtaining
8 * a copy of this software and associated documentation files (the
9 * "Software"), to deal in the Software without restriction, including
10 * without limitation the rights to use, copy, modify, merge, publish,
11 * distribute, sublicense, and/or sell copies of the Software, and to
12 * permit persons to whom the Software is furnished to do so, subject to
13 * the following conditions:
14 *
15 * The above copyright notice and this permission notice shall be
16 * included in all copies or substantial portions of the Software.
17 *
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
19 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
20 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
21 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
22 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
23 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
24 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
25 */
26 #include "nghttp3_qpack_huffman.h"
27
28 #include <string.h>
29 #include <assert.h>
30 #include <stdio.h>
31
32 #include "nghttp3_conv.h"
33
nghttp3_qpack_huffman_encode_count(const uint8_t * src,size_t len)34 size_t nghttp3_qpack_huffman_encode_count(const uint8_t *src, size_t len) {
35 size_t i;
36 size_t nbits = 0;
37
38 for (i = 0; i < len; ++i) {
39 nbits += huffman_sym_table[src[i]].nbits;
40 }
41 /* pad the prefix of EOS (256) */
42 return (nbits + 7) / 8;
43 }
44
nghttp3_qpack_huffman_encode(uint8_t * dest,const uint8_t * src,size_t srclen)45 uint8_t *nghttp3_qpack_huffman_encode(uint8_t *dest, const uint8_t *src,
46 size_t srclen) {
47 const nghttp3_qpack_huffman_sym *sym;
48 const uint8_t *end = src + srclen;
49 uint64_t code = 0;
50 size_t nbits = 0;
51 uint32_t x;
52
53 for (; src != end;) {
54 sym = &huffman_sym_table[*src++];
55 code |= (uint64_t)sym->code << (32 - nbits);
56 nbits += sym->nbits;
57 if (nbits < 32) {
58 continue;
59 }
60 x = htonl((uint32_t)(code >> 32));
61 memcpy(dest, &x, 4);
62 dest += 4;
63 code <<= 32;
64 nbits -= 32;
65 }
66
67 for (; nbits >= 8;) {
68 *dest++ = (uint8_t)(code >> 56);
69 code <<= 8;
70 nbits -= 8;
71 }
72
73 if (nbits) {
74 *dest++ = (uint8_t)((uint8_t)(code >> 56) | ((1 << (8 - nbits)) - 1));
75 }
76
77 return dest;
78 }
79
nghttp3_qpack_huffman_decode_context_init(nghttp3_qpack_huffman_decode_context * ctx)80 void nghttp3_qpack_huffman_decode_context_init(
81 nghttp3_qpack_huffman_decode_context *ctx) {
82 ctx->fstate = NGHTTP3_QPACK_HUFFMAN_ACCEPTED;
83 }
84
85 nghttp3_ssize
nghttp3_qpack_huffman_decode(nghttp3_qpack_huffman_decode_context * ctx,uint8_t * dest,const uint8_t * src,size_t srclen,int fin)86 nghttp3_qpack_huffman_decode(nghttp3_qpack_huffman_decode_context *ctx,
87 uint8_t *dest, const uint8_t *src, size_t srclen,
88 int fin) {
89 uint8_t *p = dest;
90 const uint8_t *end = src + srclen;
91 nghttp3_qpack_huffman_decode_node node = {ctx->fstate, 0};
92 const nghttp3_qpack_huffman_decode_node *t = &node;
93 uint8_t c;
94
95 /* We use the decoding algorithm described in
96 http://graphics.ics.uci.edu/pub/Prefix.pdf */
97 for (; src != end;) {
98 c = *src++;
99 t = &qpack_huffman_decode_table[t->fstate & 0x1ff][c >> 4];
100 if (t->fstate & NGHTTP3_QPACK_HUFFMAN_SYM) {
101 *p++ = t->sym;
102 }
103
104 t = &qpack_huffman_decode_table[t->fstate & 0x1ff][c & 0xf];
105 if (t->fstate & NGHTTP3_QPACK_HUFFMAN_SYM) {
106 *p++ = t->sym;
107 }
108 }
109
110 ctx->fstate = t->fstate;
111
112 if (fin && !(ctx->fstate & NGHTTP3_QPACK_HUFFMAN_ACCEPTED)) {
113 return NGHTTP3_ERR_QPACK_FATAL;
114 }
115
116 return p - dest;
117 }
118
nghttp3_qpack_huffman_decode_failure_state(nghttp3_qpack_huffman_decode_context * ctx)119 int nghttp3_qpack_huffman_decode_failure_state(
120 nghttp3_qpack_huffman_decode_context *ctx) {
121 return ctx->fstate == 0x100;
122 }
123