Ada 4.1.1
Fast spec-compliant URL parser
Loading...
Searching...
No Matches
raw_inflate.hpp
Go to the documentation of this file.
1#pragma once
2// Minimal raw DEFLATE inflater (RFC 1951), enough for zlib raw streams.
3// Returns number of output bytes written, or 0 on failure.
4#include <cstdint>
5#include <cstring>
6
7namespace ada::idna::deflate {
8
9struct BitReader {
10 const uint8_t* p;
11 const uint8_t* end;
12 uint32_t acc = 0;
13 int bits = 0;
14
15 explicit BitReader(const uint8_t* data, size_t len)
16 : p(data), end(data + len) {}
17
18 bool ensure(int n) {
19 while (bits < n) {
20 if (p >= end) return false;
21 acc |= uint32_t(*p++) << bits;
22 bits += 8;
23 }
24 return true;
25 }
26 uint32_t get(int n) {
27 if (!ensure(n)) return UINT32_MAX;
28 uint32_t v = acc & ((1u << n) - 1);
29 acc >>= n;
30 bits -= n;
31 return v;
32 }
33 void align_byte() {
34 acc >>= (bits & 7);
35 bits -= (bits & 7);
36 }
37};
38
39struct Huff {
40 // canonical codes: for each length, list of symbols
41 // Fast path: table for codes up to max_bits
42 static constexpr int MAXBITS = 15;
43 uint8_t lengths[288]{};
44 int counts[MAXBITS + 1]{};
45 int first_code[MAXBITS + 1]{};
46 int16_t symbols[288]{};
47 int nsymbols = 0;
48 int max_bits = 0;
49
50 // Base index into symbols[] for each code length (used by decode).
51 int base_idx[MAXBITS + 1]{};
52
53 bool build(const uint8_t* lens, int n) {
54 std::memset(counts, 0, sizeof(counts));
55 std::memset(first_code, 0, sizeof(first_code));
56 std::memset(base_idx, 0, sizeof(base_idx));
57 nsymbols = n;
58 max_bits = 0;
59 for (int i = 0; i < n; i++) {
60 lengths[i] = lens[i];
61 if (lens[i]) {
62 counts[lens[i]]++;
63 if (lens[i] > max_bits) max_bits = lens[i];
64 }
65 }
66 // Canonical first code for each bit length (RFC 1951).
67 int code = 0;
68 for (int bits = 1; bits <= MAXBITS; bits++) {
69 code = (code + counts[bits - 1]) << 1;
70 first_code[bits] = code;
71 }
72 int idx = 0;
73 for (int bits = 1; bits <= max_bits; bits++) {
74 base_idx[bits] = idx;
75 // assign symbols in symbol order for codes of this length
76 for (int sym = 0; sym < n; sym++) {
77 if (lengths[sym] == bits) {
78 symbols[idx++] = static_cast<int16_t>(sym);
79 }
80 }
81 }
82 return true;
83 }
84
85 int decode(BitReader& br) const {
86 if (max_bits == 0) return -1;
87 int code = 0;
88 for (int len = 1; len <= max_bits; len++) {
89 uint32_t b = br.get(1);
90 if (b == UINT32_MAX) return -1;
91 code = (code << 1) | int(b);
92 int first = first_code[len];
93 int cnt = counts[len];
94 if (cnt && code - first < cnt) {
95 return symbols[base_idx[len] + (code - first)];
96 }
97 }
98 return -1;
99 }
100};
101
102// Fixed Huffman tables are built once at dynamic initialization (before main /
103// single-threaded), so concurrent first-use of inflate cannot race.
104inline Huff make_fixed_litlen_huff() {
105 Huff h;
106 uint8_t lens[288];
107 // Fixed Huffman: 0-143:8, 144-255:9, 256-279:7, 280-287:8
108 for (int i = 0; i <= 143; i++) lens[i] = 8;
109 for (int i = 144; i <= 255; i++) lens[i] = 9;
110 for (int i = 256; i <= 279; i++) lens[i] = 7;
111 for (int i = 280; i <= 287; i++) lens[i] = 8;
112 h.build(lens, 288);
113 return h;
114}
115
116inline Huff make_fixed_dist_huff() {
117 Huff h;
118 uint8_t lens[32];
119 for (int i = 0; i < 32; i++) lens[i] = 5;
120 h.build(lens, 32);
121 return h;
122}
123
124// NOLINTNEXTLINE(cert-err58-cpp) -- intentional process-lifetime tables
125inline const Huff kFixedLitLenHuff = make_fixed_litlen_huff();
126// NOLINTNEXTLINE(cert-err58-cpp)
127inline const Huff kFixedDistHuff = make_fixed_dist_huff();
128
129inline int fixed_litlen(BitReader& br) { return kFixedLitLenHuff.decode(br); }
130
131inline int fixed_dist(BitReader& br) { return kFixedDistHuff.decode(br); }
132
133// length and distance base tables
134static const uint16_t len_base[29] = {
135 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27,
136 31, 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258};
137static const uint8_t len_extra[29] = {0, 0, 0, 0, 0, 0, 0, 0, 1, 1,
138 1, 1, 2, 2, 2, 2, 3, 3, 3, 3,
139 4, 4, 4, 4, 5, 5, 5, 5, 0};
140static const uint16_t dist_base[30] = {
141 1, 2, 3, 4, 5, 7, 9, 13, 17, 25,
142 33, 49, 65, 97, 129, 193, 257, 385, 513, 769,
143 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577};
144static const uint8_t dist_extra[30] = {0, 0, 0, 0, 1, 1, 2, 2, 3, 3,
145 4, 4, 5, 5, 6, 6, 7, 7, 8, 8,
146 9, 9, 10, 10, 11, 11, 12, 12, 13, 13};
147
148inline size_t inflate_raw(const uint8_t* src, size_t src_len, uint8_t* dst,
149 size_t dst_cap) {
150 BitReader br(src, src_len);
151 size_t out = 0;
152 for (;;) {
153 uint32_t bfinal = br.get(1);
154 uint32_t btype = br.get(2);
155 if (bfinal == UINT32_MAX || btype == UINT32_MAX) return 0;
156 if (btype == 0) {
157 // stored
158 br.align_byte();
159 if (!br.ensure(16)) return 0;
160 // read 16+16 from bit buffer awkwardly - use byte path
161 // Align: bits is multiple of 8
162 // Get len from remaining bits then bytes
163 uint32_t len = br.get(16);
164 uint32_t nlen = br.get(16);
165 if (len == UINT32_MAX || nlen == UINT32_MAX) return 0;
166 if ((len ^ 0xFFFF) != nlen) return 0;
167 // After get, may have bits in acc from previous - for stored, should be
168 // byte aligned Copy len bytes from p
169 if (br.bits != 0) {
170 // leftover bits should be 0 if aligned
171 }
172 if (size_t(br.end - br.p) < len) return 0;
173 if (out + len > dst_cap) return 0;
174 std::memcpy(dst + out, br.p, len);
175 br.p += len;
176 out += len;
177 } else if (btype == 1 || btype == 2) {
178 Huff lit, dist;
179 if (btype == 1) {
180 // use fixed via functions
181 } else {
182 // dynamic
183 uint32_t hlit = br.get(5);
184 if (hlit == UINT32_MAX) return 0;
185 hlit += 257;
186 uint32_t hdist = br.get(5);
187 if (hdist == UINT32_MAX) return 0;
188 hdist += 1;
189 uint32_t hclen = br.get(4);
190 if (hclen == UINT32_MAX) return 0;
191 hclen += 4;
192 static const int order[19] = {16, 17, 18, 0, 8, 7, 9, 6, 10, 5,
193 11, 4, 12, 3, 13, 2, 14, 1, 15};
194 uint8_t clen[19]{};
195 for (uint32_t i = 0; i < hclen; i++) {
196 uint32_t v = br.get(3);
197 if (v == UINT32_MAX) return 0;
198 clen[order[i]] = uint8_t(v);
199 }
200 Huff cl;
201 if (!cl.build(clen, 19)) return 0;
202 uint8_t lens[288 + 32]{};
203 uint32_t n = hlit + hdist;
204 for (uint32_t i = 0; i < n;) {
205 int sym = cl.decode(br);
206 if (sym < 0) return 0;
207 if (sym < 16) {
208 lens[i++] = uint8_t(sym);
209 } else if (sym == 16) {
210 uint32_t rep = br.get(2);
211 if (rep == UINT32_MAX) return 0;
212 rep += 3;
213 if (i == 0) return 0;
214 uint8_t v = lens[i - 1];
215 while (rep--) lens[i++] = v;
216 } else if (sym == 17) {
217 uint32_t rep = br.get(3);
218 if (rep == UINT32_MAX) return 0;
219 rep += 3;
220 while (rep--) lens[i++] = 0;
221 } else if (sym == 18) {
222 uint32_t rep = br.get(7);
223 if (rep == UINT32_MAX) return 0;
224 rep += 11;
225 while (rep--) lens[i++] = 0;
226 } else
227 return 0;
228 }
229 if (!lit.build(lens, int(hlit))) return 0;
230 if (!dist.build(lens + hlit, int(hdist))) return 0;
231 }
232 for (;;) {
233 int sym;
234 if (btype == 1)
235 sym = fixed_litlen(br);
236 else
237 sym = lit.decode(br);
238 if (sym < 0) return 0;
239 if (sym < 256) {
240 if (out >= dst_cap) return 0;
241 dst[out++] = uint8_t(sym);
242 } else if (sym == 256) {
243 break;
244 } else {
245 int len_code = sym - 257;
246 if (len_code < 0 || len_code > 28) return 0;
247 uint32_t extra = br.get(len_extra[len_code]);
248 if (len_extra[len_code] && extra == UINT32_MAX) return 0;
249 uint32_t length =
250 len_base[len_code] + (len_extra[len_code] ? extra : 0);
251 int dsym;
252 if (btype == 1)
253 dsym = fixed_dist(br);
254 else
255 dsym = dist.decode(br);
256 if (dsym < 0 || dsym > 29) return 0;
257 uint32_t dextra = br.get(dist_extra[dsym]);
258 if (dist_extra[dsym] && dextra == UINT32_MAX) return 0;
259 uint32_t distance = dist_base[dsym] + (dist_extra[dsym] ? dextra : 0);
260 if (distance > out || out + length > dst_cap) return 0;
261 for (uint32_t k = 0; k < length; k++) {
262 dst[out] = dst[out - distance];
263 out++;
264 }
265 }
266 }
267 } else {
268 return 0; // reserved
269 }
270 if (bfinal) break;
271 }
272 return out;
273}
274
275} // namespace ada::idna::deflate
static const uint16_t dist_base[30]
Definition ada_idna.cpp:387
Huff make_fixed_dist_huff()
Definition ada_idna.cpp:363
static const uint8_t len_extra[29]
Definition ada_idna.cpp:384
int fixed_litlen(BitReader &br)
Definition ada_idna.cpp:376
int fixed_dist(BitReader &br)
Definition ada_idna.cpp:378
const Huff kFixedLitLenHuff
Definition ada_idna.cpp:372
const Huff kFixedDistHuff
Definition ada_idna.cpp:374
Huff make_fixed_litlen_huff()
Definition ada_idna.cpp:351
static const uint16_t len_base[29]
Definition ada_idna.cpp:381
size_t inflate_raw(const uint8_t *src, size_t src_len, uint8_t *dst, size_t dst_cap)
Definition ada_idna.cpp:395
static const uint8_t dist_extra[30]
Definition ada_idna.cpp:391
BitReader(const uint8_t *data, size_t len)
bool build(const uint8_t *lens, int n)
int base_idx[MAXBITS+1]
Definition ada_idna.cpp:298
int decode(BitReader &br) const
int first_code[MAXBITS+1]
Definition ada_idna.cpp:292
int counts[MAXBITS+1]
Definition ada_idna.cpp:291
static constexpr int MAXBITS
Definition ada_idna.cpp:289