16 :
p(data),
end(data + len) {}
20 if (
p >=
end)
return false;
27 if (!
ensure(n))
return UINT32_MAX;
28 uint32_t v =
acc & ((1u << n) - 1);
42 static constexpr int MAXBITS = 15;
53 bool build(
const uint8_t* lens,
int n) {
59 for (
int i = 0; i < n; i++) {
68 for (
int bits = 1; bits <=
MAXBITS; bits++) {
69 code = (code +
counts[bits - 1]) << 1;
73 for (
int bits = 1; bits <=
max_bits; bits++) {
76 for (
int sym = 0; sym < n; sym++) {
78 symbols[idx++] =
static_cast<int16_t
>(sym);
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);
94 if (cnt && code - first < cnt) {
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;
119 for (
int i = 0; i < 32; i++) lens[i] = 5;
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};
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};
148inline size_t inflate_raw(
const uint8_t* src,
size_t src_len, uint8_t* dst,
150 BitReader br(src, src_len);
153 uint32_t bfinal = br.get(1);
154 uint32_t btype = br.get(2);
155 if (bfinal == UINT32_MAX || btype == UINT32_MAX)
return 0;
159 if (!br.ensure(16))
return 0;
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;
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);
177 }
else if (btype == 1 || btype == 2) {
183 uint32_t hlit = br.get(5);
184 if (hlit == UINT32_MAX)
return 0;
186 uint32_t hdist = br.get(5);
187 if (hdist == UINT32_MAX)
return 0;
189 uint32_t hclen = br.get(4);
190 if (hclen == UINT32_MAX)
return 0;
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};
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);
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;
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;
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;
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;
225 while (rep--) lens[i++] = 0;
229 if (!lit.build(lens,
int(hlit)))
return 0;
230 if (!dist.build(lens + hlit,
int(hdist)))
return 0;
237 sym = lit.decode(br);
238 if (sym < 0)
return 0;
240 if (out >= dst_cap)
return 0;
241 dst[out++] = uint8_t(sym);
242 }
else if (sym == 256) {
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;
255 dsym = dist.decode(br);
256 if (dsym < 0 || dsym > 29)
return 0;
258 if (
dist_extra[dsym] && dextra == UINT32_MAX)
return 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];
static const uint16_t dist_base[30]
Huff make_fixed_dist_huff()
static const uint8_t len_extra[29]
int fixed_litlen(BitReader &br)
int fixed_dist(BitReader &br)
const Huff kFixedLitLenHuff
const Huff kFixedDistHuff
Huff make_fixed_litlen_huff()
static const uint16_t len_base[29]
size_t inflate_raw(const uint8_t *src, size_t src_len, uint8_t *dst, size_t dst_cap)
static const uint8_t dist_extra[30]
BitReader(const uint8_t *data, size_t len)
bool build(const uint8_t *lens, int n)
int decode(BitReader &br) const
int first_code[MAXBITS+1]
static constexpr int MAXBITS