/src/nghttp2/lib/nghttp2_hd_huffman.c
Line | Count | Source (jump to first uncovered line) |
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 | | |
34 | 0 | size_t nghttp2_hd_huff_encode_count(const uint8_t *src, size_t len) { |
35 | 0 | size_t i; |
36 | 0 | size_t nbits = 0; |
37 | |
|
38 | 0 | for (i = 0; i < len; ++i) { |
39 | 0 | nbits += huff_sym_table[src[i]].nbits; |
40 | 0 | } |
41 | | /* pad the prefix of EOS (256) */ |
42 | 0 | return (nbits + 7) / 8; |
43 | 0 | } |
44 | | |
45 | | int nghttp2_hd_huff_encode(nghttp2_bufs *bufs, const uint8_t *src, |
46 | 0 | size_t srclen) { |
47 | 0 | const nghttp2_huff_sym *sym; |
48 | 0 | const uint8_t *end = src + srclen; |
49 | 0 | uint64_t code = 0; |
50 | 0 | uint32_t x; |
51 | 0 | size_t nbits = 0; |
52 | 0 | size_t avail; |
53 | 0 | int rv; |
54 | |
|
55 | 0 | avail = nghttp2_bufs_cur_avail(bufs); |
56 | |
|
57 | 0 | for (; src != end;) { |
58 | 0 | sym = &huff_sym_table[*src++]; |
59 | 0 | code |= (uint64_t)sym->code << (32 - nbits); |
60 | 0 | nbits += sym->nbits; |
61 | 0 | if (nbits < 32) { |
62 | 0 | continue; |
63 | 0 | } |
64 | 0 | if (avail >= 4) { |
65 | 0 | x = htonl((uint32_t)(code >> 32)); |
66 | 0 | memcpy(bufs->cur->buf.last, &x, 4); |
67 | 0 | bufs->cur->buf.last += 4; |
68 | 0 | avail -= 4; |
69 | 0 | code <<= 32; |
70 | 0 | nbits -= 32; |
71 | 0 | continue; |
72 | 0 | } |
73 | | |
74 | 0 | for (; nbits >= 8;) { |
75 | 0 | rv = nghttp2_bufs_addb(bufs, (uint8_t)(code >> 56)); |
76 | 0 | if (rv != 0) { |
77 | 0 | return rv; |
78 | 0 | } |
79 | 0 | code <<= 8; |
80 | 0 | nbits -= 8; |
81 | 0 | } |
82 | | |
83 | 0 | avail = nghttp2_bufs_cur_avail(bufs); |
84 | 0 | } |
85 | | |
86 | 0 | for (; nbits >= 8;) { |
87 | 0 | rv = nghttp2_bufs_addb(bufs, (uint8_t)(code >> 56)); |
88 | 0 | if (rv != 0) { |
89 | 0 | return rv; |
90 | 0 | } |
91 | 0 | code <<= 8; |
92 | 0 | nbits -= 8; |
93 | 0 | } |
94 | | |
95 | 0 | if (nbits) { |
96 | 0 | rv = nghttp2_bufs_addb( |
97 | 0 | bufs, (uint8_t)((uint8_t)(code >> 56) | ((1 << (8 - nbits)) - 1))); |
98 | 0 | if (rv != 0) { |
99 | 0 | return rv; |
100 | 0 | } |
101 | 0 | } |
102 | | |
103 | 0 | return 0; |
104 | 0 | } |
105 | | |
106 | 0 | void nghttp2_hd_huff_decode_context_init(nghttp2_hd_huff_decode_context *ctx) { |
107 | 0 | ctx->fstate = NGHTTP2_HUFF_ACCEPTED; |
108 | 0 | } |
109 | | |
110 | | ssize_t nghttp2_hd_huff_decode(nghttp2_hd_huff_decode_context *ctx, |
111 | | nghttp2_buf *buf, const uint8_t *src, |
112 | 0 | size_t srclen, int final) { |
113 | 0 | const uint8_t *end = src + srclen; |
114 | 0 | nghttp2_huff_decode node = {ctx->fstate, 0}; |
115 | 0 | const nghttp2_huff_decode *t = &node; |
116 | 0 | uint8_t c; |
117 | | |
118 | | /* We use the decoding algorithm described in |
119 | | http://graphics.ics.uci.edu/pub/Prefix.pdf */ |
120 | 0 | for (; src != end;) { |
121 | 0 | c = *src++; |
122 | 0 | t = &huff_decode_table[t->fstate & 0x1ff][c >> 4]; |
123 | 0 | if (t->fstate & NGHTTP2_HUFF_SYM) { |
124 | 0 | *buf->last++ = t->sym; |
125 | 0 | } |
126 | |
|
127 | 0 | t = &huff_decode_table[t->fstate & 0x1ff][c & 0xf]; |
128 | 0 | if (t->fstate & NGHTTP2_HUFF_SYM) { |
129 | 0 | *buf->last++ = t->sym; |
130 | 0 | } |
131 | 0 | } |
132 | |
|
133 | 0 | ctx->fstate = t->fstate; |
134 | |
|
135 | 0 | if (final && !(ctx->fstate & NGHTTP2_HUFF_ACCEPTED)) { |
136 | 0 | return NGHTTP2_ERR_HEADER_COMP; |
137 | 0 | } |
138 | | |
139 | 0 | return (ssize_t)srclen; |
140 | 0 | } |
141 | | |
142 | 0 | int nghttp2_hd_huff_decode_failure_state(nghttp2_hd_huff_decode_context *ctx) { |
143 | 0 | return ctx->fstate == 0x100; |
144 | 0 | } |