1 /*
2 * nghttp2 - HTTP/2 C Library
3 *
4 * Copyright (c) 2013 Tatsuhiro Tsujikawa
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining
7 * a copy of this software and associated documentation files (the
8 * "Software"), to deal in the Software without restriction, including
9 * without limitation the rights to use, copy, modify, merge, publish,
10 * distribute, sublicense, and/or sell copies of the Software, and to
11 * permit persons to whom the Software is furnished to do so, subject to
12 * the following conditions:
13 *
14 * The above copyright notice and this permission notice shall be
15 * included in all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
19 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
21 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
22 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
23 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
24 */
25 #include "nghttp2_hd_huffman.h"
26
27 #include <string.h>
28 #include <assert.h>
29 #include <stdio.h>
30
31 #include "nghttp2_hd.h"
32 #include "nghttp2_net.h"
33
nghttp2_hd_huff_encode_count(const uint8_t * src,size_t len)34 size_t nghttp2_hd_huff_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 += huff_sym_table[src[i]].nbits;
40 }
41 /* pad the prefix of EOS (256) */
42 return (nbits + 7) / 8;
43 }
44
nghttp2_hd_huff_encode(nghttp2_bufs * bufs,const uint8_t * src,size_t srclen)45 int nghttp2_hd_huff_encode(nghttp2_bufs *bufs, const uint8_t *src,
46 size_t srclen) {
47 const nghttp2_huff_sym *sym;
48 const uint8_t *end = src + srclen;
49 uint64_t code = 0;
50 uint32_t x;
51 size_t nbits = 0;
52 size_t avail;
53 int rv;
54
55 avail = nghttp2_bufs_cur_avail(bufs);
56
57 for (; src != end;) {
58 sym = &huff_sym_table[*src++];
59 code |= (uint64_t)sym->code << (32 - nbits);
60 nbits += sym->nbits;
61 if (nbits < 32) {
62 continue;
63 }
64 if (avail >= 4) {
65 x = htonl((uint32_t)(code >> 32));
66 memcpy(bufs->cur->buf.last, &x, 4);
67 bufs->cur->buf.last += 4;
68 avail -= 4;
69 code <<= 32;
70 nbits -= 32;
71 continue;
72 }
73
74 for (; nbits >= 8;) {
75 rv = nghttp2_bufs_addb(bufs, (uint8_t)(code >> 56));
76 if (rv != 0) {
77 return rv;
78 }
79 code <<= 8;
80 nbits -= 8;
81 }
82
83 avail = nghttp2_bufs_cur_avail(bufs);
84 }
85
86 for (; nbits >= 8;) {
87 rv = nghttp2_bufs_addb(bufs, (uint8_t)(code >> 56));
88 if (rv != 0) {
89 return rv;
90 }
91 code <<= 8;
92 nbits -= 8;
93 }
94
95 if (nbits) {
96 rv = nghttp2_bufs_addb(
97 bufs, (uint8_t)((uint8_t)(code >> 56) | ((1 << (8 - nbits)) - 1)));
98 if (rv != 0) {
99 return rv;
100 }
101 }
102
103 return 0;
104 }
105
nghttp2_hd_huff_decode_context_init(nghttp2_hd_huff_decode_context * ctx)106 void nghttp2_hd_huff_decode_context_init(nghttp2_hd_huff_decode_context *ctx) {
107 ctx->fstate = NGHTTP2_HUFF_ACCEPTED;
108 }
109
nghttp2_hd_huff_decode(nghttp2_hd_huff_decode_context * ctx,nghttp2_buf * buf,const uint8_t * src,size_t srclen,int final)110 nghttp2_ssize nghttp2_hd_huff_decode(nghttp2_hd_huff_decode_context *ctx,
111 nghttp2_buf *buf, const uint8_t *src,
112 size_t srclen, int final) {
113 const uint8_t *end = src + srclen;
114 nghttp2_huff_decode node = {ctx->fstate, 0};
115 const nghttp2_huff_decode *t = &node;
116 uint8_t c;
117
118 /* We use the decoding algorithm described in
119 - http://graphics.ics.uci.edu/pub/Prefix.pdf [!!! NO LONGER VALID !!!]
120 - https://ics.uci.edu/~dan/pubs/Prefix.pdf
121 - https://github.com/nghttp2/nghttp2/files/15141264/Prefix.pdf */
122 for (; src != end;) {
123 c = *src++;
124 t = &huff_decode_table[t->fstate & 0x1ff][c >> 4];
125 if (t->fstate & NGHTTP2_HUFF_SYM) {
126 *buf->last++ = t->sym;
127 }
128
129 t = &huff_decode_table[t->fstate & 0x1ff][c & 0xf];
130 if (t->fstate & NGHTTP2_HUFF_SYM) {
131 *buf->last++ = t->sym;
132 }
133 }
134
135 ctx->fstate = t->fstate;
136
137 if (final && !(ctx->fstate & NGHTTP2_HUFF_ACCEPTED)) {
138 return NGHTTP2_ERR_HEADER_COMP;
139 }
140
141 return (nghttp2_ssize)srclen;
142 }
143
nghttp2_hd_huff_decode_failure_state(nghttp2_hd_huff_decode_context * ctx)144 int nghttp2_hd_huff_decode_failure_state(nghttp2_hd_huff_decode_context *ctx) {
145 return ctx->fstate == 0x100;
146 }
147