Line 0
Link Here
|
|
|
1 |
/* My tiny gzip decompressor without using zlib. - Joel Yliluoma |
2 |
* http://iki.fi/bisqwit/ , http://youtube.com/user/Bisqwit |
3 |
* Inspired and influenced by a 13th IOCCC winner program by Ron McFarland */ |
4 |
/* Further optimized based on ideas from tinf library by Joergen Ibsen */ |
5 |
/** @file gunzip.hh @brief TinyDeflate */ |
6 |
|
7 |
/* Fun fact: Contains zero new/delete, and no STL data structures */ |
8 |
/* Distributed under the terms of the Zlib license: |
9 |
|
10 |
Copyright (C) 2018 Joel Yliluoma |
11 |
|
12 |
This software is provided 'as-is', without any express or implied |
13 |
warranty. In no event will the authors be held liable for any damages |
14 |
arising from the use of this software. |
15 |
|
16 |
Permission is granted to anyone to use this software for any purpose, |
17 |
including commercial applications, and to alter it and redistribute it |
18 |
freely, subject to the following restrictions: |
19 |
|
20 |
1. The origin of this software must not be misrepresented; you must not |
21 |
claim that you wrote the original software. If you use this software |
22 |
in a product, an acknowledgment in the product documentation would be |
23 |
appreciated but is not required. |
24 |
2. Altered source versions must be plainly marked as such, and must not be |
25 |
misrepresented as being the original software. |
26 |
3. This notice may not be removed or altered from any source distribution. |
27 |
*/ |
28 |
#include <assert.h> |
29 |
#include <utility> // std::forward |
30 |
#include <cstdint> // integer sizes |
31 |
#include <type_traits> |
32 |
#include <iterator> |
33 |
|
34 |
#if !1 //Documentation purposes only; the actual prototypes are littered with std::enable_ifs. |
35 |
/// Deflate(): This is the public method declared (later) in this file. |
36 |
/// Decompresses (inflates) deflate-compressed data, with a gzip or deflate header. |
37 |
/// User-supplied functors: |
38 |
/// @param input() returns the next byte from the (compressed) input. |
39 |
/// @param output(byte) outputs one uncompressed byte. |
40 |
/// @param outputcopy(length, offset) copies length uncompressed bytes from offset, |
41 |
/// Offset is always >= 1. |
42 |
/// offset 1 means previous byte, |
43 |
/// offset 2 means previous before that and so on. |
44 |
/// Note that (offset < length) is not an error and in fact happens frequently. |
45 |
/// If length=0, offset indicates the largest look-behind window length that |
46 |
/// you need to be prepared for. The length is a power-of-two in range 256..32768. |
47 |
// |
48 |
/// If you want to implement range checking in input, return a negative value |
49 |
/// from input() when there is no more input. |
50 |
// |
51 |
/// If you want to implement range checking in output, add a return value |
52 |
/// in output(): false=ok, true=abort; and a return value in outputcopy(): |
53 |
/// 0=ok, nonzero=one or more bytes were not writable. |
54 |
// |
55 |
/// @returns: |
56 |
/// 0 = decompression complete |
57 |
/// -1 = data error |
58 |
/// -2 = input functor returned a value outside 0x00..0xFF range |
59 |
/// -3 = output functor returned nonzero / bool true value |
60 |
/// -4 = outputcopy functor returned nonzero remaining length value |
61 |
// |
62 |
template<typename InputFunctor, typename OutputFunctor, typename WindowFunctor> |
63 |
int Deflate(InputFunctor&& input, OutputFunctor&& output, WindowFunctor&& outputcopy); |
64 |
|
65 |
/// Check README.md for the full list of versions of Deflate() available. |
66 |
|
67 |
#endif |
68 |
|
69 |
struct DeflateTrackTagBase{}; |
70 |
struct DeflateTrackNoSize: public DeflateTrackTagBase{}; |
71 |
struct DeflateTrackInSize: public DeflateTrackTagBase{}; |
72 |
struct DeflateTrackOutSize: public DeflateTrackTagBase{}; |
73 |
struct DeflateTrackBothSize: public DeflateTrackTagBase{}; |
74 |
|
75 |
|
76 |
/// The rest of the file is just for the curious about implementation. |
77 |
#ifndef DOXYGEN_SHOULD_SKIP_THIS |
78 |
namespace gunzip_ns |
79 |
{ |
80 |
//#define DO_DEFDB_DUMPING |
81 |
|
82 |
// If you want more performance at the expense of RAM use, |
83 |
// Turn one or more of these settings to false: |
84 |
static constexpr bool USE_BITARRAY_TEMPORARY_IN_HUFFMAN_CREATION = false; /* 8 bytes save */ |
85 |
static constexpr bool USE_BITARRAY_FOR_LENGTHS = false; /* 160 bytes save */ |
86 |
static constexpr bool USE_BITARRAY_FOR_HUFFNODES = false; /* 392 bytes save */ |
87 |
|
88 |
static constexpr unsigned MAX_WINDOW_SIZE = 32768u; |
89 |
|
90 |
static_assert(MAX_WINDOW_SIZE >= 1, "Max window size should be >= 1"); |
91 |
static_assert(MAX_WINDOW_SIZE <= 32768u, "Window sizes larger than 32768 are not supported by deflate standard. Edit the source code to remove this assert if you need it."); |
92 |
|
93 |
// |
94 |
#define DEFLATE_USE_DATA_TABLES |
95 |
|
96 |
#if !defined(DEFLATE_ALLOCATION_AUTOMATIC) && !defined(DEFLATE_ALLOCATION_STATIC) && !defined(DEFLATE_ALLOCATION_DYNAMIC) |
97 |
// Choose one: |
98 |
#define DEFLATE_ALLOCATION_AUTOMATIC |
99 |
//#define DEFLATE_ALLOCATION_STATIC |
100 |
//#define DEFLATE_ALLOCATION_DYNAMIC |
101 |
#endif |
102 |
|
103 |
constexpr unsigned Flag_InputAbortable = 0x01; |
104 |
constexpr unsigned Flag_OutputAbortable = 0x02; |
105 |
constexpr unsigned Flag_TrackIn = 0x40; |
106 |
constexpr unsigned Flag_TrackOut = 0x80; |
107 |
constexpr unsigned Flag_NoTrackFlagMask = 0x03; |
108 |
} |
109 |
|
110 |
#ifdef DEFLATE_ALLOCATION_DYNAMIC |
111 |
# include <memory> |
112 |
#endif |
113 |
|
114 |
// RandomAccessBitArray: An engine for arrays of data items that are not byte-aligned |
115 |
template<typename U = std::uint_least64_t> |
116 |
struct RandomAccessBitArrayBase |
117 |
{ |
118 |
private: |
119 |
static constexpr unsigned Ubytes = sizeof(U), Ubits = Ubytes*8; |
120 |
|
121 |
static std::uint_fast64_t Get_Unclean(unsigned Size, const U* data, unsigned index) throw() |
122 |
{ |
123 |
unsigned bitpos = index*Size, unitpos = bitpos / Ubits, shift = bitpos % Ubits; |
124 |
std::uint_fast64_t result = data[unitpos] >> shift; |
125 |
//assert(Size <= sizeof(result)*8); |
126 |
unsigned acquired = Ubits - shift; |
127 |
for(; acquired < Size; acquired += Ubits) |
128 |
{ |
129 |
result += (std::uint_fast64_t)data[++unitpos] << acquired; |
130 |
} |
131 |
return result; |
132 |
} |
133 |
public: |
134 |
template<unsigned Size> |
135 |
static std::uint_fast64_t Get(const U* data, unsigned index) throw() |
136 |
{ |
137 |
std::uint_fast64_t result = Get_Unclean(Size,data,index); |
138 |
return (Size >= sizeof(result)*8) ? result : (result & ((std::uint64_t(1) << Size)-1)); |
139 |
} |
140 |
|
141 |
template<unsigned Size, bool update = false> |
142 |
static void Set(U* data, unsigned index, std::uint_fast64_t value) throw() |
143 |
{ |
144 |
unsigned bitpos = index*Size, unitpos = bitpos / Ubits, eat = 0; |
145 |
// Make sure our storage unit is at least as bit as value |
146 |
//assert(Ubits >= sizeof(value)*8); |
147 |
//assert(Size >= sizeof(value)*8 || value < (std::uint64_t(1) << Size)); |
148 |
|
149 |
if(Size % Ubits != 0) |
150 |
{ |
151 |
unsigned shift = bitpos % Ubits; |
152 |
eat = Ubits - shift; if(eat > Size) eat = Size; |
153 |
|
154 |
//assert(eat < sizeof(std::uint_fast64_t)*8); |
155 |
//assert(shift + eat <= Ubits); |
156 |
std::uint_fast64_t vmask = (std::uint64_t(1) << eat)-1; |
157 |
if(update) |
158 |
data[unitpos] = (data[unitpos] & ~(vmask << shift)) | (value << shift); |
159 |
else |
160 |
data[unitpos] |= value << shift; |
161 |
//assert(eat < sizeof(value)*8); |
162 |
value >>= eat; |
163 |
++unitpos; |
164 |
} |
165 |
if(eat < Size) |
166 |
for(unsigned remain = Size-eat; ; ++unitpos) |
167 |
{ |
168 |
eat = Ubits; |
169 |
if(eat > remain) |
170 |
{ |
171 |
eat = remain; |
172 |
if(update) |
173 |
{ |
174 |
std::uint_fast64_t vmask = ((std::uint64_t(1) << eat)-1); |
175 |
data[unitpos] = (data[unitpos] & ~vmask) | value; |
176 |
} |
177 |
else |
178 |
{ |
179 |
data[unitpos] |= value; |
180 |
} |
181 |
break; |
182 |
} |
183 |
else |
184 |
{ |
185 |
data[unitpos] = value; |
186 |
value >>= Ubits/2; value >>= Ubits/2; |
187 |
remain -= Ubits; |
188 |
if(!remain) break; |
189 |
} |
190 |
} |
191 |
} |
192 |
}; |
193 |
|
194 |
template<unsigned Nbits, typename U = std::uint_least64_t> |
195 |
struct RandomAccessBitArray |
196 |
{ |
197 |
static constexpr unsigned Ubytes = sizeof(U), Ubits = Ubytes*8, Nunits = (Nbits+Ubits-1)/Ubits; |
198 |
U data[Nunits]; |
199 |
|
200 |
template<unsigned Size> |
201 |
inline std::uint_fast64_t Get(unsigned index) const throw() |
202 |
{ |
203 |
return RandomAccessBitArrayBase<U>::template Get<Size>(data, index); |
204 |
} |
205 |
|
206 |
template<unsigned Size, bool update = false> |
207 |
inline void Set(unsigned index, std::uint_fast64_t value) throw() |
208 |
{ |
209 |
RandomAccessBitArrayBase<U>::template Set<Size,update>(data, index, value); |
210 |
} |
211 |
}; |
212 |
|
213 |
namespace gunzip_ns |
214 |
{ |
215 |
struct dummy{}; |
216 |
|
217 |
/// Utility: ceil(log2(n)) |
218 |
template<unsigned long N> struct CeilLog2_s{ static constexpr unsigned result = 1+CeilLog2_s<(N+1)/2>::result; }; |
219 |
template<> struct CeilLog2_s<0> { static constexpr unsigned result = 0; }; |
220 |
template<> struct CeilLog2_s<1> { static constexpr unsigned result = 0; }; |
221 |
template<unsigned long N> static constexpr unsigned CeilLog2 = CeilLog2_s<N>::result; |
222 |
|
223 |
/// Utility: floor(log2(n)) |
224 |
template<unsigned long N> struct FloorLog2_s{ static constexpr unsigned result = 1+FloorLog2_s<N/2>::result; }; |
225 |
template<> struct FloorLog2_s<0> { static constexpr unsigned result = 0; }; |
226 |
template<> struct FloorLog2_s<1> { static constexpr unsigned result = 0; }; |
227 |
template<unsigned long N> static constexpr unsigned FloorLog2 = FloorLog2_s<N>::result; |
228 |
|
229 |
/// Utility: smallest unsigned integer type that can store n-bit value |
230 |
template<unsigned bits> |
231 |
using SmallestType = std::conditional_t< (bits<=16), |
232 |
std::conditional_t< (bits<= 8), std::uint_least8_t, std::uint_least16_t>, |
233 |
std::conditional_t< (bits<=32), std::uint_least32_t, std::uint_least64_t>>; |
234 |
|
235 |
/// testcases |
236 |
static_assert(FloorLog2<1> == 0, "FloorLog2 fail"); static_assert(CeilLog2<1> == 0, "CeilLog2 fail"); |
237 |
static_assert(FloorLog2<2> == 1, "FloorLog2 fail"); static_assert(CeilLog2<2> == 1, "CeilLog2 fail"); |
238 |
static_assert(FloorLog2<3> == 1, "FloorLog2 fail"); static_assert(CeilLog2<3> == 2, "CeilLog2 fail"); |
239 |
static_assert(FloorLog2<4> == 2, "FloorLog2 fail"); static_assert(CeilLog2<4> == 2, "CeilLog2 fail"); |
240 |
static_assert(FloorLog2<5> == 2, "FloorLog2 fail"); static_assert(CeilLog2<5> == 3, "CeilLog2 fail"); |
241 |
static_assert(FloorLog2<6> == 2, "FloorLog2 fail"); static_assert(CeilLog2<6> == 3, "CeilLog2 fail"); |
242 |
static_assert(FloorLog2<7> == 2, "FloorLog2 fail"); static_assert(CeilLog2<7> == 3, "CeilLog2 fail"); |
243 |
static_assert(FloorLog2<8> == 3, "FloorLog2 fail"); static_assert(CeilLog2<8> == 3, "CeilLog2 fail"); |
244 |
static_assert(FloorLog2<9> == 3, "FloorLog2 fail"); static_assert(CeilLog2<9> == 4, "CeilLog2 fail"); |
245 |
|
246 |
template<bool packed, unsigned Dimension, unsigned ElementSize> |
247 |
struct RandomAccessArray {}; |
248 |
|
249 |
template<unsigned Dim, unsigned Elem> |
250 |
struct RandomAccessArray<true, Dim, Elem> |
251 |
{ |
252 |
RandomAccessBitArray<Dim*Elem> impl; |
253 |
inline std::uint_fast64_t Get(unsigned index) const { return impl.template Get<Elem>(index); } |
254 |
inline void Set(unsigned index, std::uint_fast32_t value) { impl.template Set<Elem,true>(index, value); } |
255 |
inline void QSet(unsigned index, std::uint_fast32_t value) { impl.template Set<Elem,false>(index, value); } |
256 |
template<unsigned Bits> |
257 |
inline void WSet(unsigned index, std::uint_fast64_t value) { impl.template Set<Bits,true>(index, value); } |
258 |
}; |
259 |
|
260 |
template<unsigned Dim, unsigned Elem> |
261 |
struct RandomAccessArray<false, Dim, Elem> |
262 |
{ |
263 |
typedef SmallestType<Elem> E; |
264 |
E data[Dim]; |
265 |
inline E Get(unsigned index) const { return data[index]; } |
266 |
inline void Set(unsigned index, E value) { data[index] = value; } |
267 |
inline void QSet(unsigned index, E value) { data[index] = value; } |
268 |
template<unsigned Bits> |
269 |
inline void WSet(unsigned index, std::uint_fast64_t value) |
270 |
{ |
271 |
index *= Bits/Elem; |
272 |
for(unsigned b=0; b<Bits; b+=Elem, value>>=Elem) |
273 |
QSet(index++, (value % (1u << Elem))); |
274 |
} |
275 |
}; |
276 |
} |
277 |
|
278 |
|
279 |
namespace gunzip_ns |
280 |
{ |
281 |
//#define DEFL_DO_HUFF_STATS |
282 |
template<bool Abortable, unsigned A,unsigned B, typename LengthFunctor> |
283 |
bool CreateHuffmanTree(const char* |
284 |
#ifdef DEFL_DO_HUFF_STATS |
285 |
why |
286 |
#endif |
287 |
, RandomAccessArray<USE_BITARRAY_FOR_HUFFNODES,A,B>& tree, |
288 |
unsigned num_values, |
289 |
LengthFunctor&& ReadLength) throw() |
290 |
{ |
291 |
/* Lengths[] needs to be scanned exactly twice, in forward order. |
292 |
* Technically we could use a functor instead of a table, |
293 |
* but this would require that the dynamic tree generator |
294 |
* can read sections of the compressed data twice, |
295 |
* which we currently do not support. |
296 |
*/ |
297 |
|
298 |
constexpr unsigned ElemBits = CeilLog2<A-15>; // ceil(log2(A-15)) where A-15 is max value of num_values |
299 |
static_assert((1u << B) >= (A-15), "B is too small"); |
300 |
assert(num_values <= (A-15)); |
301 |
|
302 |
RandomAccessArray<USE_BITARRAY_TEMPORARY_IN_HUFFMAN_CREATION, 15, ElemBits> offs{}; // 24 or 16 bytes. |
303 |
// Theoretically 15.32 bytes for 288 num_values, 9.375 for 32 num_values, 7.97 for 19 num_values. |
304 |
|
305 |
// Clear code length count table |
306 |
tree.template WSet<(15*B + 63) & ~63>(0, 0); // First 15 needed, but round to nice unit |
307 |
// Scan symbol length, and sum code length counts |
308 |
#ifdef DEFL_DO_HUFF_STATS |
309 |
unsigned largest_treetable_value = 0, largest_offs = 0, smallest_treetable_value = ~0u; |
310 |
unsigned largest_treetrans_index=0, largest_treetrans_value=0; |
311 |
unsigned longest_length = 0; |
312 |
#endif |
313 |
for(unsigned a = 0; a < num_values; ++a) |
314 |
{ |
315 |
int length = ReadLength(a); // Note: Can be zero. |
316 |
if(Abortable && length < 0) return true; |
317 |
if(length) |
318 |
{ |
319 |
unsigned v = tree.Get(0 + length-1)+1; |
320 |
#ifdef DEFL_DO_HUFF_STATS |
321 |
largest_treetable_value = std::max(largest_treetable_value, v); |
322 |
longest_length = std::max(longest_length, unsigned(length)); |
323 |
#endif |
324 |
//fprintf(stderr, " [%d]%3d CLL (val: %d)\n", length, v, v); |
325 |
tree.Set(0 + length-1, v); |
326 |
} |
327 |
else |
328 |
{ |
329 |
//fprintf(stderr, " [_]%3d CLL (val: 0)\n", 0); |
330 |
} |
331 |
} |
332 |
|
333 |
// Compute offset table for distribution sort |
334 |
for(unsigned sum=0, a = 1; a < 16; ++a) |
335 |
{ |
336 |
offs.QSet(a-1, sum); // starting offset for values that have length "a" |
337 |
sum += tree.Get(0 + a-1); // number of values that have length "a" |
338 |
} |
339 |
#ifdef DEFL_DO_HUFF_STATS |
340 |
for(unsigned a=1; a<=longest_length; ++a) |
341 |
smallest_treetable_value = std::min(smallest_treetable_value, (unsigned)tree.Get(0 + a-1)); |
342 |
#endif |
343 |
|
344 |
// Create code->symbol translation table (symbols sorted by code) |
345 |
for(unsigned value = 0; value < num_values; ++value) |
346 |
{ |
347 |
int length = ReadLength(value); // Note: Can be zero. |
348 |
if(Abortable && length < 0) return true; |
349 |
if(length) |
350 |
{ |
351 |
unsigned q = offs.Get(length-1); offs.Set(length-1, q+1); // q = offset[length]++; |
352 |
#ifdef DEFL_DO_HUFF_STATS |
353 |
largest_offs = std::max(q, largest_offs); |
354 |
largest_treetrans_index = std::max(largest_treetrans_index, q); |
355 |
largest_treetrans_value = std::max(largest_treetrans_value, value); |
356 |
#endif |
357 |
assert(q < num_values /*&& value < num_values*/); |
358 |
//fprintf(stderr, " [x]%3d CLL %d\n", 15+q, value); |
359 |
tree.Set(15 + q, value); |
360 |
} |
361 |
} |
362 |
#ifdef DEFL_DO_HUFF_STATS |
363 |
std::fprintf(stderr, "Largest \"%12s\"(treetable_value=%4u..%4u, offs=%4u, treetrans_index=%4u, treetrans_value=%4u)\n", |
364 |
why, smallest_treetable_value,largest_treetable_value, |
365 |
largest_offs, largest_treetrans_index, largest_treetrans_value); |
366 |
#endif |
367 |
|
368 |
// Largest values observed in the wild: |
369 |
|
370 |
// Dyn Lengths: Max treetable_value =255, max offs =285, max treetrans_index =285, max treetrans_value =285 |
371 |
// Stat Lengths:Max treetable_value =152, max offs =287, max treetrans_index =287, max treetrans_value =287 |
372 |
|
373 |
// Len Lengths: Max treetable_value = 13, max offs = 18, max treetrans_index = 18, max treetrans_value = 18 |
374 |
// Dyn Dists: Max treetable_value = 19, max offs = 29, max treetrans_index = 29, max treetrans_value = 29 |
375 |
// Stat Dists: Max treetable_value = 32, max offs = 31, max treetrans_index = 31, max treetrans_value = 31 |
376 |
return false; |
377 |
} |
378 |
|
379 |
#ifdef DEFLATE_USE_DATA_TABLES |
380 |
template<bool=0> // Using a dummy template parameter makes this function and its data weak, |
381 |
inline const std::uint_least8_t* GetBTable() throw() // removing linker problems in multi-module use |
382 |
{ |
383 |
static const std::uint_least8_t data[] { |
384 |
// Length bases (0-31) |
385 |
0,1,2,3,4,5,6,7,8,10,12,14,16,20,24,28,32,40,48,56,64,80,96,112,128,160,192,224,255, 0,0,0, |
386 |
// Length bits and distance bits (29-60) (overlap 3 bytes) |
387 |
// 0x00,0x01,0x01,0x02,0x02,0x13,0x13,0x14,0x14,0x25,0x25,0x26,0x26, |
388 |
//0x37,0x37,0x38,0x38,0x49,0x49,0x4A,0x4A,0x5B,0x5B,0x5C,0x5C,0x0D,0x0D,0x00,0x00 |
389 |
// Reverse-order table |
390 |
3*3,17*3,15*3,13*3,11*3,9*3,7*3,5*3,4*3,6*3,8*3,10*3,12*3,14*3,16*3,18*3,0*3,1*3,2*3 |
391 |
}; |
392 |
return data; |
393 |
} |
394 |
//template<bool=0> |
395 |
//inline const std::uint_least16_t* GetWTable() throw() |
396 |
//{ |
397 |
// static const std::uint_least16_t data[32] { |
398 |
// 1,2,3,4,5,7,9,13,17,25,33,49,65,97,129,193,257,385,513,769,1025,1537,2049,3073,4097,6145,8193,12289,16385,24577, 0,0 }; |
399 |
// return data; |
400 |
//} |
401 |
|
402 |
//inline unsigned dbase(unsigned distcode) { return GetWTable<>()[distcode]; } |
403 |
inline unsigned lbase(unsigned lencode) { return GetBTable<>()[lencode-257+0] + 3; } |
404 |
//inline unsigned dbits(unsigned distcode) { return GetBTable<>()[distcode+29] & 0xF; } |
405 |
//inline unsigned lbits(unsigned lencode) { return GetBTable<>()[lencode-257+29] >> 4; } |
406 |
inline unsigned rshift(unsigned a) { return GetBTable<>()[a + 32]; } |
407 |
#else |
408 |
inline unsigned lbase(unsigned lencode) { return (lencode > 285 ? 3 : ((lencode >= 265) ? (((lencode-257)%4+4) << ((lencode-257)/4-1)) + (lencode==285 ? 2 : 3) : (lencode-254))); } |
409 |
inline unsigned rshift(unsigned a) { if(!a) return 3*3; else if(a>=16) return (a-16)*3; int r = 12 + 7*(a<8) - a*2; return (r<0 ? -r : r)*3; } |
410 |
#endif |
411 |
inline unsigned dbase(unsigned distcode) { return (1 + (distcode>=4 ? ((2+distcode%2) << (distcode/2-1)) : distcode)); } |
412 |
inline unsigned dbits(unsigned distcode) { return distcode>=4 ? distcode/2-1 : 0; } |
413 |
inline unsigned lbits(unsigned lencode) { return ((lencode>=265 && lencode<285) ? ((lencode-265)/4+1) : 0); } |
414 |
//inline unsigned order(unsigned index) { return index<3 ? (index+16) : ((index%2) ? (1-index/2)&7 : (6+index/2)); } |
415 |
|
416 |
// Cortex-M0+ Cortex-M4 x86_64 |
417 |
// dbase with table 12+64 = 76 12+64 = 76 14+64 = 78 |
418 |
// dbase with func 24 22 26 |
419 |
// lbase with table 12+32 = 48 12+32 = 48 21+64 = 76 |
420 |
// lbase with func 54 56 64 |
421 |
// dbits+lbits with table 12+16+29 = 57 12+16+29 = 57 17+21+29 = 67 |
422 |
// dbits+lbits with func 14+18 = 32 14+18 = 32 13+20 = 33 |
423 |
|
424 |
// Support for pre-c++20 |
425 |
template<typename T> |
426 |
using remove_cvref_t = std::remove_reference_t<std::remove_cv_t<T>>; |
427 |
// Support for pre-c++20 (result_of is removed in c++20, invoke_result is added in c++17, so neither can be used exclusively) |
428 |
template <class T> |
429 |
struct result_of { // explain usage |
430 |
static_assert((T)false, "result_of<CallableType> is invalid; use " |
431 |
"result_of<CallableType(zero or more argument types)> instead."); |
432 |
}; |
433 |
#if __cplusplus > 202000UL |
434 |
template <typename F, typename... Args> |
435 |
struct result_of<F(Args...)> : std::invoke_result<F, Args...> {}; |
436 |
#else |
437 |
template <typename F, typename... Args> |
438 |
struct result_of<F(Args...)> : std::result_of<F(Args...)> {}; |
439 |
#endif |
440 |
template <class T> |
441 |
using result_of_t = typename result_of<T>::type; |
442 |
|
443 |
#define BEGIN_COND(name) \ |
444 |
template<typename T, typename=void> struct name : public std::false_type {}; \ |
445 |
template<typename T> struct name<T, std::enable_if_t< |
446 |
#define END_COND(name) \ |
447 |
, void>> : public std::true_type {}; \ |
448 |
template<typename T> \ |
449 |
inline constexpr bool name ## _v = name<T>::value; \ |
450 |
|
451 |
// Input parameter condition testers: |
452 |
BEGIN_COND(is_input_functor) |
453 |
std::is_convertible_v<result_of_t<remove_cvref_t<T>()>,int> |
454 |
END_COND(is_input_functor) |
455 |
BEGIN_COND(is_input_iterator) |
456 |
std::is_convertible_v<typename std::iterator_traits<remove_cvref_t<T>>::value_type, unsigned char> |
457 |
&& std::is_same_v<typename std::iterator_traits<remove_cvref_t<T>>::iterator_category, std::input_iterator_tag> |
458 |
END_COND(is_input_iterator) |
459 |
BEGIN_COND(is_bidir_input) |
460 |
std::is_convertible_v<typename std::iterator_traits<remove_cvref_t<T>>::value_type, unsigned char> |
461 |
&& (std::is_same_v<typename std::iterator_traits<remove_cvref_t<T>>::iterator_category, std::forward_iterator_tag> |
462 |
|| std::is_same_v<typename std::iterator_traits<remove_cvref_t<T>>::iterator_category, std::bidirectional_iterator_tag> |
463 |
|| std::is_same_v<typename std::iterator_traits<remove_cvref_t<T>>::iterator_category, std::random_access_iterator_tag>) |
464 |
END_COND(is_bidir_input) |
465 |
BEGIN_COND(is_size_type) |
466 |
std::is_convertible_v<remove_cvref_t<T>, std::size_t> && !std::is_pointer_v<remove_cvref_t<T>> |
467 |
END_COND(is_size_type) |
468 |
// Output parameter condition testers: |
469 |
BEGIN_COND(is_random_iterator) |
470 |
std::is_convertible_v<typename std::iterator_traits<remove_cvref_t<T>>::value_type, unsigned char> |
471 |
&& !std::is_const_v<typename std::iterator_traits<remove_cvref_t<T>>::reference> |
472 |
&& std::is_same_v<typename std::iterator_traits<remove_cvref_t<T>>::iterator_category, std::random_access_iterator_tag> |
473 |
END_COND(is_random_iterator) |
474 |
BEGIN_COND(is_output_iterator) |
475 |
std::is_convertible_v<typename std::iterator_traits<remove_cvref_t<T>>::value_type, unsigned char> |
476 |
&& !std::is_const_v<typename std::iterator_traits<remove_cvref_t<T>>::reference> |
477 |
&& !std::is_pointer_v<remove_cvref_t<T>> |
478 |
&& (std::is_same_v<typename std::iterator_traits<remove_cvref_t<T>>::iterator_category, std::output_iterator_tag> |
479 |
|| std::is_same_v<typename std::iterator_traits<remove_cvref_t<T>>::iterator_category, std::forward_iterator_tag> |
480 |
|| std::is_same_v<typename std::iterator_traits<remove_cvref_t<T>>::iterator_category, std::bidirectional_iterator_tag>) |
481 |
END_COND(is_output_iterator) |
482 |
// Output functor & window functor: Returns void or something that can be converted to bool |
483 |
BEGIN_COND(is_output_functor) |
484 |
std::is_same_v<result_of_t<remove_cvref_t<T>(int)>,void> || std::is_convertible_v<result_of_t<remove_cvref_t<T>(int)>,bool> |
485 |
END_COND(is_output_functor) |
486 |
BEGIN_COND(is_window_functor) |
487 |
std::is_same_v<result_of_t<remove_cvref_t<T>(int,int)>,void> || std::is_convertible_v<result_of_t<remove_cvref_t<T>(int,int)>,int> |
488 |
END_COND(is_window_functor) |
489 |
|
490 |
BEGIN_COND(is_abortable_input_type) |
491 |
!(std::is_same_v<T, unsigned char> || std::is_same_v<T, signed char> || std::is_same_v<T, char>) |
492 |
END_COND(is_abortable_input_type) |
493 |
|
494 |
#undef END_COND |
495 |
#undef BEGIN_COND |
496 |
|
497 |
template<typename T> |
498 |
constexpr bool DeflAbortable_InFun = is_abortable_input_type_v<remove_cvref_t<result_of_t<T()>>>; |
499 |
template<typename T> |
500 |
constexpr bool DeflAbortable_OutFun = std::is_same_v<result_of_t<T(int)>, bool>; |
501 |
template<typename T> |
502 |
constexpr bool DeflAbortable_WinFun = std::is_convertible_v<remove_cvref_t<result_of_t<T(int,int)>>, int>; |
503 |
|
504 |
template<bool Abortable> |
505 |
struct OutputHelper |
506 |
{ |
507 |
template<typename OutputFunctor> |
508 |
static inline bool output(OutputFunctor&& output, unsigned char byte) |
509 |
{ |
510 |
output(byte); |
511 |
return false; |
512 |
} |
513 |
template<typename WindowFunctor> |
514 |
static inline bool outputcopy(WindowFunctor&& outputcopy, std::uint_least16_t length, std::uint_fast32_t offset) |
515 |
{ |
516 |
outputcopy(length, offset); |
517 |
return false; |
518 |
} |
519 |
}; |
520 |
|
521 |
template<> |
522 |
struct OutputHelper<true> |
523 |
{ |
524 |
template<typename OutputFunctor> |
525 |
static inline bool output(OutputFunctor&& output, unsigned char byte) |
526 |
{ |
527 |
return output(byte); |
528 |
} |
529 |
template<typename WindowFunctor> |
530 |
static inline bool outputcopy(WindowFunctor&& outputcopy, std::uint_least16_t& length, std::uint_fast32_t offset) |
531 |
{ |
532 |
length = outputcopy(length, offset); |
533 |
return length != 0; |
534 |
} |
535 |
}; |
536 |
|
537 |
struct SizeTracker_NoOutput |
538 |
{ |
539 |
inline void OutByte() { } |
540 |
inline void OutBytes(std::uint_fast64_t) { } |
541 |
|
542 |
// Dummy forwarders. Do the same as std::forward. |
543 |
template<typename T> |
544 |
static inline constexpr T&& ForwardOutput(std::remove_reference_t<T>& fun) { return static_cast<T&&>(fun); } |
545 |
template<typename T> |
546 |
static inline constexpr T&& ForwardOutput(std::remove_reference_t<T>&& fun) { return static_cast<T&&>(fun); } |
547 |
|
548 |
template<typename T> |
549 |
static inline constexpr T&& ForwardWindow(std::remove_reference_t<T>& fun) { return static_cast<T&&>(fun); } |
550 |
template<typename T> |
551 |
static inline constexpr T&& ForwardWindow(std::remove_reference_t<T>&& fun) { return static_cast<T&&>(fun); } |
552 |
}; |
553 |
struct SizeTracker_NoInput |
554 |
{ |
555 |
inline void InByte() { } |
556 |
inline void InBytes(std::uint_fast64_t) { } |
557 |
|
558 |
template<typename T> |
559 |
static inline constexpr T&& ForwardInput(std::remove_reference_t<T>& fun) { return static_cast<T&&>(fun); } |
560 |
template<typename T> |
561 |
static inline constexpr T&& ForwardInput(std::remove_reference_t<T>&& fun) { return static_cast<T&&>(fun); } |
562 |
}; |
563 |
struct SizeTracker_DoInput |
564 |
{ |
565 |
std::uint_fast64_t insize=0; |
566 |
|
567 |
inline void InByte() { ++insize; } |
568 |
inline void InBytes(std::uint_fast64_t n) { insize += n; } |
569 |
|
570 |
template<typename InputFunctor, std::enable_if_t<!DeflAbortable_InFun<InputFunctor>,gunzip_ns::dummy>...> |
571 |
auto ForwardInput(const InputFunctor& input) |
572 |
{ |
573 |
return [&]() { InByte(); return input(); }; |
574 |
} |
575 |
|
576 |
template<typename InputFunctor, std::enable_if_t<DeflAbortable_InFun<InputFunctor>,gunzip_ns::dummy>...> |
577 |
auto ForwardInput(const InputFunctor& input) |
578 |
{ |
579 |
return [&]() { auto r = input(); if(!(r & ~0xFF)) { InByte(); } return r; }; |
580 |
} |
581 |
}; |
582 |
struct SizeTracker_DoOutput |
583 |
{ |
584 |
std::uint_fast64_t outsize=0; |
585 |
|
586 |
inline void OutByte() { ++outsize; } |
587 |
inline void OutBytes(std::uint_fast64_t n) { outsize += n; } |
588 |
|
589 |
template<typename OutputFunctor, std::enable_if_t<!DeflAbortable_OutFun<OutputFunctor>,gunzip_ns::dummy>...> |
590 |
auto ForwardOutput(const OutputFunctor& output) |
591 |
{ |
592 |
return [&](unsigned char byte) { OutByte(); return output(byte); }; |
593 |
} |
594 |
|
595 |
template<typename OutputFunctor, std::enable_if_t<DeflAbortable_OutFun<OutputFunctor>,gunzip_ns::dummy>...> |
596 |
auto ForwardOutput(const OutputFunctor& output) |
597 |
{ |
598 |
return [&](unsigned char byte) { auto r = output(byte); if(!r) { OutByte(); } return r; }; |
599 |
} |
600 |
|
601 |
template<typename WindowFunctor, std::enable_if_t<!DeflAbortable_WinFun<WindowFunctor>,gunzip_ns::dummy>...> |
602 |
auto ForwardWindow(const WindowFunctor& outputcopy) |
603 |
{ |
604 |
return [&](std::uint_least16_t length, std::uint_fast32_t offset) |
605 |
{ |
606 |
OutBytes(length); |
607 |
return outputcopy(length, offset); |
608 |
}; |
609 |
} |
610 |
|
611 |
template<typename WindowFunctor, std::enable_if_t<DeflAbortable_WinFun<WindowFunctor>,gunzip_ns::dummy>...> |
612 |
auto ForwardWindow(const WindowFunctor& outputcopy) |
613 |
{ |
614 |
return [&](std::uint_least16_t length, std::uint_fast32_t offset) |
615 |
{ |
616 |
auto remain = outputcopy(length, offset); |
617 |
OutBytes(length - remain); |
618 |
return remain; |
619 |
}; |
620 |
} |
621 |
}; |
622 |
|
623 |
template<typename TrackType> |
624 |
struct SizeTracker: public SizeTracker_NoOutput, public SizeTracker_NoInput |
625 |
{ |
626 |
inline int operator() (int returncode) const { return returncode; } |
627 |
}; |
628 |
template<> |
629 |
struct SizeTracker<DeflateTrackOutSize>: public SizeTracker_NoInput, public SizeTracker_DoOutput |
630 |
{ |
631 |
typedef std::pair<int,std::uint_fast64_t> result; |
632 |
inline result operator() (int returncode) const { return result{returncode,outsize}; } |
633 |
}; |
634 |
template<> |
635 |
struct SizeTracker<DeflateTrackInSize>: public SizeTracker_NoOutput, public SizeTracker_DoInput |
636 |
{ |
637 |
typedef std::pair<int,std::uint_fast64_t> result; |
638 |
inline result operator() (int returncode) const { return result{returncode,insize}; } |
639 |
}; |
640 |
template<> |
641 |
struct SizeTracker<DeflateTrackBothSize>: public SizeTracker_DoInput, public SizeTracker_DoOutput |
642 |
{ |
643 |
typedef std::pair<int, std::pair<std::uint_fast64_t,std::uint_fast64_t>> result; |
644 |
inline result operator() (int returncode) const { return result{returncode,std::make_pair(insize,outsize)}; } |
645 |
}; |
646 |
|
647 |
#ifdef DO_DEFDB_DUMPING |
648 |
unsigned bitcounter=0; |
649 |
#endif |
650 |
struct DeflateBitCache |
651 |
{ |
652 |
std::uint_least8_t BitCache = 0, BitCount = 0; |
653 |
|
654 |
template<bool Abortable, typename InputFunctor> |
655 |
std::uint_least64_t GetBits(InputFunctor&& input, unsigned numbits) |
656 |
{ |
657 |
#ifdef DO_DEFDB_DUMPING |
658 |
bitcounter += numbits; |
659 |
#endif |
660 |
std::uint_fast64_t result = BitCache; |
661 |
if(numbits <= BitCount) |
662 |
{ |
663 |
BitCount -= numbits; |
664 |
BitCache >>= numbits; |
665 |
result &= ((1u << numbits)-1); // 0-8 |
666 |
return result; |
667 |
} |
668 |
for(unsigned acquired = BitCount; ; acquired += 8) |
669 |
{ |
670 |
unsigned byte = input(); |
671 |
if(Abortable && (byte & ~0xFFu)) |
672 |
{ |
673 |
// Note: Throws away bits already eaten from BitCache |
674 |
return ~std::uint_least64_t(0); // error |
675 |
} |
676 |
unsigned eat = numbits-acquired; |
677 |
byte &= 0xFF; |
678 |
if(eat <= 8) |
679 |
{ |
680 |
result |= ((std::uint_fast64_t)(byte & ((1u << eat)-1))) << acquired; |
681 |
BitCount = 8-eat; |
682 |
BitCache = byte >> eat; |
683 |
return result; |
684 |
} |
685 |
result |= ((std::uint_fast64_t)(byte)) << acquired; |
686 |
} |
687 |
} |
688 |
|
689 |
template<bool Abortable, typename InputFunctor, unsigned A,unsigned B> |
690 |
std::uint_least32_t HuffRead(InputFunctor&& input, |
691 |
RandomAccessArray<USE_BITARRAY_FOR_HUFFNODES,A,B>& tree) |
692 |
{ |
693 |
int sum=0, cur=0, len=0; |
694 |
#ifdef DEFL_DO_HUFF_STATS |
695 |
static int maxlen = 0; |
696 |
#endif |
697 |
// Get more bits while code value is above sum |
698 |
do { |
699 |
auto p = GetBits<Abortable>(std::forward<InputFunctor>(input), 1); |
700 |
if(Abortable && !~p) |
701 |
{ |
702 |
// Note: Throws away progress already made traversing the tree |
703 |
return ~std::uint_least32_t(0); // error flag |
704 |
} |
705 |
cur = (unsigned(cur) << 1) | unsigned(bool(p)); |
706 |
#ifdef DEFL_DO_HUFF_STATS |
707 |
if(len > maxlen) |
708 |
{ |
709 |
maxlen = len; |
710 |
std::fprintf(stderr, "maxlen access: %d (%d)\n", maxlen, (int)tree.Get(0 + len)); |
711 |
} |
712 |
#endif |
713 |
auto v = tree.Get(0 + len++); |
714 |
sum += v; |
715 |
cur -= v; |
716 |
} while(cur >= 0); |
717 |
return tree.Get(15 + sum + cur); |
718 |
} |
719 |
}; |
720 |
|
721 |
template<bool Backtrackable> |
722 |
struct DeflateState: public DeflateBitCache |
723 |
{ |
724 |
std::uint_least8_t lencode = 0, num = 0; // used in DynTreeFunc |
725 |
|
726 |
// Lengths are in 0..15 range. |
727 |
RandomAccessArray<USE_BITARRAY_FOR_LENGTHS, 288, CeilLog2<16>> Lengths; // 144 bytes |
728 |
// Length tree |
729 |
// Values up to 288 in indexes 0-14. (Table) (255 is max observed in wild) |
730 |
// Values up to 287 in indexes 15-302. (Trans) |
731 |
RandomAccessArray<USE_BITARRAY_FOR_HUFFNODES, 15+288, CeilLog2<289>> ltree; // 341->344 bytes |
732 |
// Distance tree |
733 |
// Values up to 32 in indexes 0-14. (Table) |
734 |
// Values up to 31 in indexes 15-46. (Trans) |
735 |
RandomAccessArray<USE_BITARRAY_FOR_HUFFNODES, 15+32, CeilLog2<33>> dtree; // 36->40 bytes |
736 |
|
737 |
RandomAccessArray<USE_BITARRAY_FOR_HUFFNODES, 15+32, CeilLog2<33>>& lltree = dtree; |
738 |
|
739 |
// Theoretical minimum memory use: |
740 |
// (15*log2(289) + 288*log2(288))/8 = 309.45 bytes for ltree |
741 |
// (15*log2(33) + 32 *log2(32))/8 = 29.46 bytes for dtree |
742 |
// 144.00 bytes for lengths |
743 |
// total 482.91 bytes |
744 |
|
745 |
template<bool Abortable, typename InputFunctor, typename BacktrackFunctor> |
746 |
auto DynTreeFunc(InputFunctor&& input, std::uint_fast16_t length, BacktrackFunctor&& /*backtrack*/, |
747 |
bool |
748 |
#ifdef DO_DEFDB_DUMPING |
749 |
dists |
750 |
#endif |
751 |
) |
752 |
{ |
753 |
Lengths = {}; // clear at least length nibbles; easiest to clear it all |
754 |
bool error = false; |
755 |
for(std::uint_fast16_t code = 0; ; ) |
756 |
{ |
757 |
#ifdef DO_DEFDB_DUMPING |
758 |
unsigned bits_before=bitcounter; |
759 |
#endif |
760 |
if(!num) |
761 |
{ |
762 |
auto p = HuffRead<Abortable>(std::forward<InputFunctor>(input), lltree); |
763 |
if(Abortable && !~p) { error = true; goto done; } |
764 |
std::uint_least8_t what = p; // 0-18 |
765 |
|
766 |
if(!(what & 16)) { lencode = what * 0x11u; what = 0x01; } // 1 times (what < 16) (use what, set prev) |
767 |
else if(what < 17) { lencode = (lencode >> 4) * 0x11u; what = 0x23; } // 3..6 (use prev) |
768 |
else if(what == 17) { lencode = 0; what = 0x33; } // 3..10 (use 0, set prev) |
769 |
else { lencode = 0; what = 0x7B; } // 11..138 (use 0, set prev) |
770 |
|
771 |
p = GetBits<Abortable>(std::forward<InputFunctor>(input), what >> 4); // 0, 2, 3 or 7 bits |
772 |
#ifdef DO_DEFDB_DUMPING |
773 |
if(what>>4) |
774 |
{ |
775 |
char tmp[64]="[_]"; sprintf(tmp, "[%d]", int(bitcounter-bits_before)); |
776 |
fprintf(stderr, "%4s %cREP (%d times)\n", tmp, (lencode&0xF)?'L':'Z', p+(what&0xF)); |
777 |
} |
778 |
#endif |
779 |
|
780 |
if(Abortable && !~p) { error = true; goto done; } |
781 |
num = p + (what & 0xF); // 1..138 |
782 |
} |
783 |
|
784 |
#ifdef DO_DEFDB_DUMPING |
785 |
bool rep=num>1; |
786 |
#endif |
787 |
do { |
788 |
#ifdef DO_DEFDB_DUMPING |
789 |
char tmp[64]="[_]"; if(!rep) sprintf(tmp, "[%d]", int(bitcounter-bits_before)); |
790 |
if(code == 0x100) |
791 |
fprintf(stderr, "%4s EofB CL (val:%2d)\n", tmp, int(lencode&0xF)); |
792 |
else if(dists) |
793 |
fprintf(stderr, "%4s d_%02d CL (val:%2d)\n", tmp, int(code), int(lencode&0xF)); |
794 |
else if(code > 0x100) |
795 |
fprintf(stderr, "%4s l_%02d CL (val:%2d)\n", tmp, int(code- 0x101), int(lencode&0xF)); |
796 |
else |
797 |
fprintf(stderr, "%4s 0x%02X CL (val:%2d)\n", tmp, (int)code, int(lencode&0xF)); |
798 |
#endif |
799 |
|
800 |
--num; |
801 |
Lengths.QSet(code++, lencode & 0xF); |
802 |
if(code == length) { goto done; } |
803 |
} while(num > 0); |
804 |
} |
805 |
done:; |
806 |
return [this,error](unsigned index) -> std::conditional_t<Abortable, int, unsigned char> |
807 |
{ |
808 |
if(Abortable && error) return -1; |
809 |
return Lengths.Get(index); |
810 |
}; |
811 |
} |
812 |
}; |
813 |
|
814 |
template<> |
815 |
struct DeflateState<true>: public DeflateBitCache |
816 |
{ |
817 |
// Length tree |
818 |
// Values up to 288 in indexes 0-14. (Table) (255 is max observed in wild) |
819 |
// Values up to 287 in indexes 15-302. (Trans) |
820 |
RandomAccessArray<USE_BITARRAY_FOR_HUFFNODES, 15+288, CeilLog2<289>> ltree; // 341->344 bytes |
821 |
|
822 |
// Distance tree |
823 |
// Values up to 32 in indexes 0-14. (Table) |
824 |
// Values up to 31 in indexes 15-46. (Trans) |
825 |
RandomAccessArray<USE_BITARRAY_FOR_HUFFNODES, 15+32, CeilLog2<33>> dtree; // 36->40 bytes |
826 |
|
827 |
// Length-lengths tree |
828 |
// Values up to 19 in indexes 0-14. (Table) (13 is max observed in wild) |
829 |
// Values up to 18 in indexes 15-33. (Trans) |
830 |
RandomAccessArray<USE_BITARRAY_FOR_HUFFNODES, 15+19, CeilLog2<20>> lltree; // 22->24 bytes |
831 |
|
832 |
// Theoretical minimum memory use: |
833 |
// (15*log2(289) + 288*log2(288))/8 = 309.45 bytes for ltree |
834 |
// (15*log2(33) + 32 *log2(32))/8 = 29.46 bytes for dtree |
835 |
// (15*log2(20) + 19 *log2(19))/8 = 18.19 bytes for lltree |
836 |
// total 357.10 bytes |
837 |
|
838 |
std::uint_least8_t lencode, num; // used in DynTreeFunc |
839 |
std::uint_least8_t checkpoint_lencode, checkpoint_num; |
840 |
std::uint_least8_t checkpoint_BitCache, checkpoint_BitCount; |
841 |
|
842 |
template<bool Abortable, typename InputFunctor, typename BacktrackFunctor> |
843 |
auto DynTreeFunc(InputFunctor&& input, std::uint_fast16_t /*length*/, BacktrackFunctor&& backtrack, |
844 |
bool |
845 |
#ifdef DO_DEFDB_DUMPING |
846 |
dists |
847 |
#endif |
848 |
) |
849 |
{ |
850 |
// Create checkpoint |
851 |
checkpoint_lencode = 0; |
852 |
checkpoint_num = 0; |
853 |
checkpoint_BitCache = BitCache; |
854 |
checkpoint_BitCount = BitCount; |
855 |
backtrack(false); |
856 |
|
857 |
return [this,&input,&backtrack](unsigned index) -> std::conditional_t<Abortable, int, unsigned char> |
858 |
{ |
859 |
if(index == 0) |
860 |
{ |
861 |
// Restore checkpoint |
862 |
lencode = checkpoint_lencode; |
863 |
num = checkpoint_num; |
864 |
BitCache = checkpoint_BitCache; |
865 |
BitCount = checkpoint_BitCount; |
866 |
backtrack(true); |
867 |
} |
868 |
|
869 |
if(Abortable && (num==0xFF)) return -1; |
870 |
|
871 |
if(!num) |
872 |
{ |
873 |
auto p = HuffRead<Abortable>(std::forward<InputFunctor>(input), lltree); |
874 |
if(Abortable && !~p) { num = 0xFF; return -1; } // If p== ~uint64_t() |
875 |
std::uint_least8_t what = p; // 0-18 |
876 |
|
877 |
if(!(what & 16)) { lencode = what * 0x11u; what = 0x01; } // 1 times (what < 16) (use what, set prev) |
878 |
else if(what < 17) { lencode = (lencode >> 4) * 0x11u; what = 0x23; } // 3..6 (use prev) |
879 |
else if(what == 17) { lencode = 0; what = 0x33; } // 3..10 (use 0, set prev) |
880 |
else { lencode = 0; what = 0x7B; } // 11..138 (use 0, set prev) |
881 |
|
882 |
p = GetBits<Abortable>(std::forward<InputFunctor>(input), what >> 4); // 0, 2, 3 or 7 bits |
883 |
|
884 |
if(Abortable && !~p) { num = 0xFF; return -1; } // If p== ~uint64_t() |
885 |
num = p + (what & 0xF); // 1..138 |
886 |
} |
887 |
--num; |
888 |
return (lencode & 0xF); |
889 |
}; |
890 |
} |
891 |
}; |
892 |
|
893 |
struct DeflateWindow |
894 |
{ |
895 |
unsigned char Data[gunzip_ns::MAX_WINDOW_SIZE]; |
896 |
SmallestType<CeilLog2<gunzip_ns::MAX_WINDOW_SIZE>> Head = 0; |
897 |
}; |
898 |
|
899 |
#ifdef DEFLATE_ALLOCATION_STATIC |
900 |
template<typename ObjectType> |
901 |
ObjectType& GetStaticObj() |
902 |
{ |
903 |
static thread_local ObjectType obj; |
904 |
obj.~ObjectType(); |
905 |
new(&obj) ObjectType(); |
906 |
return obj; |
907 |
} |
908 |
#endif |
909 |
|
910 |
/* Values of Abortable: |
911 |
* Input abortable = &1 |
912 |
* Output abortable = &2 |
913 |
* Resumable = &4 |
914 |
* |
915 |
* Input abortable Output abortable Resumable Value |
916 |
* no no no 0 |
917 |
* yes no no 1 |
918 |
* no yes no 2 |
919 |
* yes yes no 3 |
920 |
* 4 = invalid |
921 |
* yes no yes 5 |
922 |
* no yes yes 6 |
923 |
* yes yes yes 7 |
924 |
*/ |
925 |
template<unsigned char Abortable, |
926 |
typename InputFunctor, typename OutputFunctor, typename WindowFunctor, |
927 |
typename BacktrackFunctor> |
928 |
int Gunzip(InputFunctor&& input, |
929 |
OutputFunctor&& output, |
930 |
WindowFunctor&& outputcopy, |
931 |
BacktrackFunctor&& backtrack) |
932 |
{ |
933 |
using namespace gunzip_ns; |
934 |
|
935 |
typedef DeflateState<!std::is_same_v<remove_cvref_t<BacktrackFunctor>,dummy>> StateType; |
936 |
#ifdef DEFLATE_ALLOCATION_AUTOMATIC |
937 |
StateType state; |
938 |
#elif defined(DEFLATE_ALLOCATION_STATIC) |
939 |
auto& state = gunzip_ns::GetStaticObj<StateType>(); |
940 |
#elif defined(DEFLATE_ALLOCATION_DYNAMIC) |
941 |
std::unique_ptr<StateType> stateptr(new StateType); |
942 |
auto& state = *stateptr; |
943 |
#endif |
944 |
|
945 |
// The following routines are macros rather than e.g. lambda functions, |
946 |
// in order to make them inlined in the function structure, and breakable/resumable. |
947 |
#define CONCAT(a, b) a##b |
948 |
|
949 |
// Bit-by-bit input routine |
950 |
#define DummyGetBits_(line,numbits) do { \ |
951 |
auto CONCAT(pd,line) = state.template GetBits<bool(Abortable&Flag_InputAbortable)>(std::forward<InputFunctor>(input), numbits); \ |
952 |
if((Abortable & Flag_InputAbortable) && !~CONCAT(pd,line)) return -2; \ |
953 |
} while(0) |
954 |
#define DummyGetBits(numbits) DummyGetBits_(__LINE__, numbits) |
955 |
|
956 |
#define GetBits_(line,numbits, target) \ |
957 |
auto CONCAT(pb,line) = state.template GetBits<bool(Abortable&Flag_InputAbortable)>(std::forward<InputFunctor>(input), numbits); \ |
958 |
if((Abortable & Flag_InputAbortable) && !~CONCAT(pb,line)) return -2; \ |
959 |
target = CONCAT(pb,line) |
960 |
#define GetBits(numbits, target) GetBits_(__LINE__, numbits, target) |
961 |
|
962 |
// Huffman tree read routine. |
963 |
#define HuffRead_(line, tree, target) \ |
964 |
auto CONCAT(ph,line) = state.template HuffRead<bool(Abortable&Flag_InputAbortable)>(std::forward<InputFunctor>(input), tree); \ |
965 |
if((Abortable & Flag_InputAbortable) && !~CONCAT(ph,line)) return -2; \ |
966 |
target = CONCAT(ph,line) |
967 |
#define HuffRead(tree, target) HuffRead_(__LINE__, tree, target) |
968 |
|
969 |
#define Fail_If(condition) do { \ |
970 |
/*assert(!(condition));*/ \ |
971 |
if(condition) return -1; \ |
972 |
} while(0) |
973 |
|
974 |
// Read stream header |
975 |
GetBits(16, std::uint_least16_t header); |
976 |
// ^ Read deflate header: method[4] ; winsize[4] ; checksum[8] |
977 |
if(header == 0x8B1F) // Is it actually a gzip header? |
978 |
{ |
979 |
// Get format identifier, flags, MTIME, XFL and OS |
980 |
GetBits(64, header); Fail_If((header & 0xFF) != 8); // Format identifier should be 8 |
981 |
if(header&0x0400) // Skip extra fields as indicated by FEXTRA |
982 |
{ GetBits(16, std::uint_fast16_t q); DummyGetBits(8*q); } |
983 |
if(header&0x0800) for(;;) { GetBits(8, bool q); if(!q) break; } // NAME: Skip filename if FNAME was present |
984 |
if(header&0x1000) for(;;) { GetBits(8, bool q); if(!q) break; } // COMMENT: Skip comment if FCOMMENT was present |
985 |
if(header&0x0200) { DummyGetBits(16); } // HCRC: Skip FCRC if was present |
986 |
outputcopy(0, 32768u); // GZIP always uses 32k window |
987 |
} |
988 |
else // No. Deflate header? |
989 |
{ |
990 |
Fail_If((header & 0x208F) != 0x0008 || ((((header<<8)+(header>>8))&0xFFFF)%31) != 0); |
991 |
outputcopy(0, 256 << ((header >> 4) & 0xF)); // Preset dictionary (0x2000) is not supported |
992 |
} |
993 |
|
994 |
// Read compressed blocks |
995 |
for(;;) |
996 |
{ |
997 |
GetBits(3, header); |
998 |
//fprintf(stderr, "header=%d\n", header); |
999 |
if(header & 4) // Dynamic block |
1000 |
{ |
1001 |
Fail_If(header & 2); |
1002 |
std::uint_least16_t nlen_ndist_ncode; |
1003 |
GetBits(14, nlen_ndist_ncode); |
1004 |
|
1005 |
#define nlen (((nlen_ndist_ncode >> 0u) & 0x1Fu) + 257u) // 257..288 |
1006 |
#define ndist (((nlen_ndist_ncode >> 5u) & 0x1Fu) + 1u) // 1..32 |
1007 |
|
1008 |
|
1009 |
std::uint_least8_t ncode = ((nlen_ndist_ncode >> 10u) + 4u); // 4..19 |
1010 |
{std::uint_fast64_t lenlens; GetBits(ncode*3, lenlens); // Max: 19*3 = 57 bits |
1011 |
#ifdef DO_DEFDB_DUMPING |
1012 |
fprintf(stderr, " [5] HLIT%5d (val:%d)\n [5] HDIST%4d (val:%d)\n [4] HCLEN%4d (val:%d)\n", |
1013 |
nlen,nlen-257, ndist,ndist-1, ncode,ncode-4); |
1014 |
for(unsigned a=0; a<19; ++a) |
1015 |
for(unsigned b=0; b<19; ++b) |
1016 |
if(rshift(b) == 3*a) |
1017 |
{ |
1018 |
if(a < ncode) |
1019 |
fprintf(stderr, " [3]%3d CLL (val: %d)\n", b, int((lenlens >> rshift(b)) & 7)); |
1020 |
else |
1021 |
fprintf(stderr, " [_]%3d CLL (val: %d)\n", b, int((lenlens >> rshift(b)) & 7)); |
1022 |
} |
1023 |
#endif |
1024 |
|
1025 |
auto lltree_fun = [=](unsigned a) -> unsigned char { return (lenlens >> rshift(a)) & 7; }; |
1026 |
while(CreateHuffmanTree<bool(Abortable&Flag_InputAbortable)>("Len Lengths", state.lltree, 19, lltree_fun)) { return -2; }} |
1027 |
|
1028 |
{auto ltree_fun = state.template DynTreeFunc<bool(Abortable&Flag_InputAbortable)>(std::forward<InputFunctor>(input), nlen, std::forward<BacktrackFunctor>(backtrack), false); |
1029 |
while(CreateHuffmanTree<bool(Abortable&Flag_InputAbortable)>("Dyn Lengths", state.ltree, nlen, ltree_fun)) { return -2; }} |
1030 |
|
1031 |
{auto dtree_fun = state.template DynTreeFunc<bool(Abortable&Flag_InputAbortable)>(std::forward<InputFunctor>(input), ndist, std::forward<BacktrackFunctor>(backtrack), true); |
1032 |
while(CreateHuffmanTree<bool(Abortable&Flag_InputAbortable)>("Dyn Dists", state.dtree, ndist, dtree_fun)) { return -2; }} |
1033 |
|
1034 |
#undef nlen |
1035 |
#undef ndist |
1036 |
} |
1037 |
else // Fixed block |
1038 |
{ |
1039 |
if(header < 2) // Copy stored block data |
1040 |
{ |
1041 |
DummyGetBits(state.BitCount%8); // Go to byte boundary (discard a few bits) |
1042 |
GetBits(32, std::uint_least32_t a); |
1043 |
Fail_If(((a ^ (a >> 16)) & 0xFFFF) != 0xFFFF); |
1044 |
#ifdef DO_DEFDB_DUMPING |
1045 |
fprintf(stderr, "raw block of %d bytes (0x%X)\n", (unsigned short)a, a); |
1046 |
#endif |
1047 |
// Note: It is valid for (lower 16 bits of) "a" to be 0 here. |
1048 |
// It is sometimes used for aligning the stream to byte boundary. |
1049 |
while(a-- & 0xFFFF) |
1050 |
{ |
1051 |
GetBits(8, unsigned char octet); |
1052 |
while(OutputHelper<bool(Abortable&Flag_OutputAbortable)>::output(output, octet)) { return -3; } |
1053 |
} |
1054 |
goto skipdef; |
1055 |
} |
1056 |
|
1057 |
unsigned char (*ltree_fun)(unsigned) = [](unsigned n)->unsigned char{return (n<0x90 || n>=0x118) ? 8u : (n<0x100 ? 9u : 7u); }; |
1058 |
unsigned char (*dtree_fun)(unsigned) = [](unsigned )->unsigned char{return 5u;}; |
1059 |
while(CreateHuffmanTree<false>("Stat Lengths", state.ltree, 288, ltree_fun)) { return -2; } |
1060 |
while(CreateHuffmanTree<false>("Stat Dists", state.dtree, 32, dtree_fun)) { return -2; } |
1061 |
} |
1062 |
// Do actual deflating. |
1063 |
for(;;) |
1064 |
{ |
1065 |
#ifdef DO_DEFDB_DUMPING |
1066 |
unsigned a=bitcounter; |
1067 |
#endif |
1068 |
HuffRead(state.ltree, std::uint_least16_t lencode); // 0..287 |
1069 |
if(!(lencode & -256)) // 0..255: literal byte |
1070 |
{ |
1071 |
#ifdef DO_DEFDB_DUMPING |
1072 |
{char tmp[64];sprintf(tmp,"[%d]",bitcounter-a); fprintf(stderr, "%4s %02X\n", tmp, lencode);} |
1073 |
#endif |
1074 |
while(OutputHelper<bool(Abortable&Flag_OutputAbortable)>::output(output, lencode)) { return -3; } |
1075 |
} |
1076 |
else if(!(lencode & 0xFF)) break; // 256=end |
1077 |
else // 257..287: length code for backwards reference |
1078 |
{ |
1079 |
GetBits(lbits(lencode), std::uint_least16_t length); length += lbase(lencode); |
1080 |
{HuffRead(state.dtree, std::uint_least8_t distcode); // Read distance code (0..31) |
1081 |
{GetBits(dbits(distcode), std::uint_least32_t offset); offset += dbase(distcode); |
1082 |
#ifdef DO_DEFDB_DUMPING |
1083 |
{char tmp[64];sprintf(tmp,"[%d]",bitcounter-a); fprintf(stderr, "%4s (%d,%d)\n", tmp,length,offset);} |
1084 |
#endif |
1085 |
while(OutputHelper<bool(Abortable&Flag_OutputAbortable)>::outputcopy(outputcopy,length,offset)) { return -4; }}} |
1086 |
} |
1087 |
} |
1088 |
skipdef:if(header & 1) break; // last block flag |
1089 |
} |
1090 |
// Note: after this, may come a checksum, and a trailer. Ignoring them. |
1091 |
#undef GetBits |
1092 |
#undef DummyGetBits |
1093 |
#undef Fail_If |
1094 |
#undef HuffRead |
1095 |
return 0; |
1096 |
} |
1097 |
}//ns |
1098 |
|
1099 |
|
1100 |
/* |
1101 |
`InputParams` may be one of the following sets of parameters: |
1102 |
|
1103 |
* InputFunctor input `(5)` `(14)` |
1104 |
* InputIterator begin `(7)` `(14)` |
1105 |
* InputIterator begin, InputIterator end `(6)` `(14)` |
1106 |
* InputIterator begin, SizeType length `(8)` `(14)` |
1107 |
* BidirectionalIterator begin, SizeType length `(8)` `(15)` |
1108 |
* ForwardIterator begin `(7)` `(14)` |
1109 |
* BidirectionalIterator begin `(7)` `(15)` |
1110 |
* RandomAccessIterator begin `(7)` `(15)` |
1111 |
* ForwardIterator begin, ForwardIterator end `(6)` `(15)` |
1112 |
* BidirectionalIterator begin, BidirectionalIterator end `(6)` `(15)` |
1113 |
* RandomAccessIterator begin, RandomAccessIterator end `(6)` `(15)` |
1114 |
|
1115 |
`OutputParams` may be one of the following sets of parameters: |
1116 |
|
1117 |
* OutputFunctor output `(1)` `(9)` |
1118 |
* OutputFunctor output, WindowFunctor window `(2)` |
1119 |
* OutputIterator target `(9)` |
1120 |
* RandomAccessIterator target `(10)` |
1121 |
* RandomAccessIterator target, SizeType target_limit `(3)` `(10)` |
1122 |
* RandomAccessIterator target, RandomAccessIterator target_end `(4)` `(10)` |
1123 |
*/ |
1124 |
|
1125 |
namespace gunzip_ns |
1126 |
{ |
1127 |
#ifdef DEFLATE_ALLOCATION_AUTOMATIC |
1128 |
#define DeflDeclWindow gunzip_ns::DeflateWindow window; |
1129 |
#elif defined(DEFLATE_ALLOCATION_STATIC) |
1130 |
#define DeflDeclWindow auto& window = gunzip_ns::GetStaticObj<gunzip_ns::DeflateWindow>(); |
1131 |
#elif defined(DEFLATE_ALLOCATION_DYNAMIC) |
1132 |
#define DeflDeclWindow std::unique_ptr<gunzip_ns::DeflateWindow> winptr(new gunzip_ns::DeflateWindow); \ |
1133 |
auto& window = *winptr; |
1134 |
#endif |
1135 |
|
1136 |
template<unsigned char code, typename I,typename O,typename C,typename B> |
1137 |
auto DeflateDispatchFinal(I&& i, O&& o, C&& c, B&& b) |
1138 |
{ |
1139 |
if constexpr(code & (Flag_TrackIn | Flag_TrackOut)) |
1140 |
{ |
1141 |
//fprintf(stderr, "both track flag\n"); |
1142 |
SizeTracker<DeflateTrackBothSize> tracker; |
1143 |
return tracker(Gunzip<code & Flag_NoTrackFlagMask> |
1144 |
(tracker.template ForwardInput(i), tracker.template ForwardOutput(o), tracker.template ForwardWindow(c), std::forward<B>(b))); |
1145 |
} |
1146 |
else if constexpr(code & Flag_TrackIn) |
1147 |
{ |
1148 |
//fprintf(stderr, "in track flag\n"); |
1149 |
SizeTracker<DeflateTrackInSize> tracker; |
1150 |
return tracker(Gunzip<code & Flag_NoTrackFlagMask> |
1151 |
(tracker.template ForwardInput(i),std::forward<O>(o),std::forward<C>(c),std::forward<B>(b))); |
1152 |
} |
1153 |
else if constexpr(code & Flag_TrackOut) |
1154 |
{ |
1155 |
//fprintf(stderr, "out track flag\n"); |
1156 |
SizeTracker<DeflateTrackOutSize> tracker; |
1157 |
return tracker(Gunzip<code & Flag_NoTrackFlagMask> |
1158 |
(std::forward<I>(i), tracker.template ForwardOutput(o), tracker.template ForwardWindow(c), std::forward<B>(b))); |
1159 |
} |
1160 |
else |
1161 |
{ |
1162 |
//fprintf(stderr, "no track flag\n"); |
1163 |
return Gunzip<code & Flag_NoTrackFlagMask>(std::forward<I>(i),std::forward<O>(o),std::forward<C>(c),std::forward<B>(b)); |
1164 |
} |
1165 |
} |
1166 |
|
1167 |
// One-parameter output dispatch: |
1168 |
template<unsigned char code, typename BtFun, typename InFun, typename T1> |
1169 |
auto DeflateOutputDispatch(BtFun&& bt, InFun&& infun, T1&& param1) |
1170 |
{ |
1171 |
// Is param1 a random access iterator? |
1172 |
if constexpr(is_random_iterator_v<T1>) |
1173 |
{ |
1174 |
//fprintf(stderr, "random iterator\n"); |
1175 |
auto output = [&](unsigned char l) { *param1 = l; ++param1; }; |
1176 |
auto outputcopy = [&](std::uint_least16_t length, std::uint_fast32_t offs) |
1177 |
{ |
1178 |
/* length=0 means that offs is the size of the window. */ |
1179 |
for(; length--; ++param1) { *param1 = *(param1-offs); } |
1180 |
}; |
1181 |
return DeflateDispatchFinal<code>(std::forward<InFun>(infun), output, outputcopy, std::forward<BtFun>(bt)); |
1182 |
} |
1183 |
// Is param1 an output iterator? |
1184 |
else if constexpr(is_output_iterator_v<T1>) |
1185 |
{ |
1186 |
//fprintf(stderr, "output iterator\n"); |
1187 |
DeflDeclWindow |
1188 |
auto output = [&](unsigned char l) |
1189 |
{ |
1190 |
window.Data[window.Head++ % MAX_WINDOW_SIZE] = l; |
1191 |
*param1 = l; ++param1; |
1192 |
}; |
1193 |
auto outputcopy = [&](std::uint_least16_t length, std::uint_fast32_t offs) |
1194 |
{ |
1195 |
/* length=0 means that offs is the size of the window. */ |
1196 |
for(; length>0; --length) |
1197 |
{ |
1198 |
unsigned char byte = window.Data[(window.Head - offs) % MAX_WINDOW_SIZE]; |
1199 |
output(byte); |
1200 |
} |
1201 |
return false; |
1202 |
}; |
1203 |
return DeflateDispatchFinal<code>(std::forward<InFun>(infun), output, outputcopy, std::forward<BtFun>(bt)); |
1204 |
} |
1205 |
// param1 must be an output functor, then. |
1206 |
else if constexpr(is_output_functor_v<T1>) |
1207 |
{ |
1208 |
//fprintf(stderr, "output functor\n"); |
1209 |
DeflDeclWindow |
1210 |
auto output = [&](unsigned char l) |
1211 |
{ |
1212 |
window.Data[window.Head++ % MAX_WINDOW_SIZE] = l; |
1213 |
return param1(l); |
1214 |
}; |
1215 |
auto outputcopy = [&](std::uint_least16_t length, std::uint_fast32_t offs) |
1216 |
{ |
1217 |
/* length=0 means that offs is the size of the window. */ |
1218 |
for(; length>0; --length) |
1219 |
{ |
1220 |
unsigned char byte = window.Data[(window.Head - offs) % MAX_WINDOW_SIZE]; |
1221 |
if(OutputHelper<DeflAbortable_OutFun<T1>>::output(output, byte)) |
1222 |
break; |
1223 |
} |
1224 |
return length; |
1225 |
}; |
1226 |
return DeflateDispatchFinal |
1227 |
<code | (DeflAbortable_OutFun<T1> ? Flag_OutputAbortable : 0)> |
1228 |
(std::forward<InFun>(infun), output, outputcopy, std::forward<BtFun>(bt)); |
1229 |
} |
1230 |
else |
1231 |
{ |
1232 |
//fprintf(stderr, "unreached code 1\n"); |
1233 |
static_assert(code==0xFF, "Deflate: Unknown output parameter type"); |
1234 |
} |
1235 |
} |
1236 |
|
1237 |
// Two-parameter output dispatch: |
1238 |
template<unsigned char code, typename BtFun, typename InFun, typename T1, typename T2> |
1239 |
auto DeflateOutputDispatch(BtFun&& bt, InFun&& infun, T1&& param1, T2&& param2) |
1240 |
{ |
1241 |
if constexpr(std::is_same_v<remove_cvref_t<T2>, DeflateTrackNoSize>) |
1242 |
{ |
1243 |
//fprintf(stderr, "no track flag...\n"); |
1244 |
return DeflateOutputDispatch<code> (std::forward<BtFun>(bt), std::forward<InFun>(infun), std::forward<T1>(param1)); |
1245 |
} |
1246 |
else if constexpr(std::is_same_v<remove_cvref_t<T2>, DeflateTrackInSize>) |
1247 |
{ |
1248 |
//fprintf(stderr, "in track flag...\n"); |
1249 |
return DeflateOutputDispatch<code | Flag_TrackIn> (std::forward<BtFun>(bt), std::forward<InFun>(infun), std::forward<T1>(param1)); |
1250 |
} |
1251 |
else if constexpr(std::is_same_v<remove_cvref_t<T2>, DeflateTrackOutSize>) |
1252 |
{ |
1253 |
//fprintf(stderr, "out track flag...\n"); |
1254 |
return DeflateOutputDispatch<code | Flag_TrackOut> (std::forward<BtFun>(bt), std::forward<InFun>(infun), std::forward<T1>(param1)); |
1255 |
} |
1256 |
else if constexpr(std::is_same_v<remove_cvref_t<T2>, DeflateTrackBothSize>) |
1257 |
{ |
1258 |
//fprintf(stderr, "both track flag...\n"); |
1259 |
return DeflateOutputDispatch<code | Flag_TrackIn | Flag_TrackOut> (std::forward<BtFun>(bt), std::forward<InFun>(infun), std::forward<T1>(param1)); |
1260 |
} |
1261 |
// Are param1 and param2 both random access iterators? |
1262 |
else if constexpr(std::is_same_v<T1,T2> && is_random_iterator_v<T1>) |
1263 |
{ |
1264 |
//fprintf(stderr, "random iterator + random iterator\n"); |
1265 |
auto output = [&](unsigned char l) |
1266 |
{ |
1267 |
if(param1 == param2) return true; |
1268 |
*param1 = l; ++param1; |
1269 |
return false; |
1270 |
}; |
1271 |
auto outputcopy = [&](std::uint_least16_t length, std::uint_fast32_t offs) |
1272 |
{ |
1273 |
/* length=0 means that offs is the size of the window. */ |
1274 |
for(; length > 0 && !(param1 == param2); --length, ++param1) |
1275 |
{ |
1276 |
*param1 = *(param1 - offs); |
1277 |
} |
1278 |
return length; |
1279 |
}; |
1280 |
return DeflateDispatchFinal<code | Flag_OutputAbortable>(std::forward<InFun>(infun), output, outputcopy, std::forward<BtFun>(bt)); |
1281 |
} |
1282 |
// Is param1 a random access iterator and param2 a size? |
1283 |
else if constexpr(is_size_type_v<T2> && is_random_iterator_v<T1>) |
1284 |
{ |
1285 |
//fprintf(stderr, "random iterator + size\n"); |
1286 |
typename std::iterator_traits<remove_cvref_t<T1>>::difference_type used{}, cap=param2; |
1287 |
auto output = [&](unsigned char l) |
1288 |
{ |
1289 |
if(used >= cap) return true; |
1290 |
param1[used] = l; ++used; |
1291 |
return false; |
1292 |
}; |
1293 |
auto outputcopy = [&](std::uint_least16_t length, std::uint_fast32_t offs) |
1294 |
{ |
1295 |
/* length=0 means that offs is the size of the window. */ |
1296 |
for(; length > 0 && used < cap; ++used, --length) |
1297 |
{ |
1298 |
param1[used] = param1[used - offs]; |
1299 |
} |
1300 |
return length; |
1301 |
}; |
1302 |
return DeflateDispatchFinal<code | Flag_OutputAbortable>(std::forward<InFun>(infun), output, outputcopy, std::forward<BtFun>(bt)); |
1303 |
} |
1304 |
// Then, param1 must be an output functor and param2 a window functor. |
1305 |
else if constexpr(is_output_functor_v<T1> && is_window_functor_v<T2>) |
1306 |
{ |
1307 |
//fprintf(stderr, "output functor + window functor\n"); |
1308 |
return DeflateDispatchFinal |
1309 |
<code | ( (DeflAbortable_OutFun<T1> && DeflAbortable_WinFun<T2>) ? Flag_OutputAbortable : 0 ) > |
1310 |
(std::forward<InFun>(infun), std::forward<T1>(param1), std::forward<T2>(param2), std::forward<BtFun>(bt)); |
1311 |
} |
1312 |
else |
1313 |
{ |
1314 |
//fprintf(stderr, "unreached code 2\n"); |
1315 |
static_assert(code==0xFF, "Deflate: Unknown output parameter type"); |
1316 |
} |
1317 |
} |
1318 |
|
1319 |
// Three-parameter output dispatch: |
1320 |
template<unsigned char code, typename BtFun, typename InFun, typename T1, typename T2, typename T3> |
1321 |
auto DeflateOutputDispatch(BtFun&& bt, InFun&& infun, T1&& p1, T2&& p2, T3) |
1322 |
{ |
1323 |
if constexpr(std::is_same_v<remove_cvref_t<T3>, DeflateTrackNoSize>) |
1324 |
{ |
1325 |
//fprintf(stderr, "no track flag...\n"); |
1326 |
return DeflateOutputDispatch<code> (std::forward<BtFun>(bt), std::forward<InFun>(infun), std::forward<T1>(p1), std::forward<T2>(p2)); |
1327 |
} |
1328 |
else if constexpr(std::is_same_v<remove_cvref_t<T3>, DeflateTrackInSize>) |
1329 |
{ |
1330 |
//fprintf(stderr, "in track flag...\n"); |
1331 |
return DeflateOutputDispatch<code | Flag_TrackIn> (std::forward<BtFun>(bt), std::forward<InFun>(infun), std::forward<T1>(p1), std::forward<T2>(p2)); |
1332 |
} |
1333 |
else if constexpr(std::is_same_v<remove_cvref_t<T3>, DeflateTrackOutSize>) |
1334 |
{ |
1335 |
//fprintf(stderr, "out track flag...\n"); |
1336 |
return DeflateOutputDispatch<code | Flag_TrackOut> (std::forward<BtFun>(bt), std::forward<InFun>(infun), std::forward<T1>(p1), std::forward<T2>(p2)); |
1337 |
} |
1338 |
else if constexpr(std::is_same_v<remove_cvref_t<T3>, DeflateTrackBothSize>) |
1339 |
{ |
1340 |
//fprintf(stderr, "both track flag...\n"); |
1341 |
return DeflateOutputDispatch<code | Flag_TrackIn | Flag_TrackOut> (std::forward<BtFun>(bt), std::forward<InFun>(infun), std::forward<T1>(p1), std::forward<T2>(p2)); |
1342 |
} |
1343 |
else |
1344 |
{ |
1345 |
//fprintf(stderr, "unreached code 3\n"); |
1346 |
static_assert(code==0xFF, "Deflate: Mismatched parameters. Expected last parameter to be a DeflateTrack option."); |
1347 |
} |
1348 |
} |
1349 |
|
1350 |
// One or two parameter input dispatch: |
1351 |
template<unsigned char code, typename BtFun, typename T1, typename T2, typename... T> |
1352 |
auto DeflateInputDispatch(BtFun&& bt, T1&& param1, T2&& param2, T&&... args) |
1353 |
{ |
1354 |
using namespace gunzip_ns; |
1355 |
// Are param1 and param2 an input iterator pair? |
1356 |
if constexpr(std::is_same_v<T1, T2> && is_input_iterator_v<T1>) |
1357 |
{ |
1358 |
//fprintf(stderr, "input iterator + input iterator\n"); |
1359 |
auto inputfun = [&]() -> std::common_type_t<int, decltype(*param1)> |
1360 |
{ if(param1 == param2) { return -1; } int r = *param1; ++param1; return r; }; |
1361 |
return DeflateOutputDispatch<code|Flag_InputAbortable>(std::forward<BtFun>(bt), inputfun, std::forward<T>(args)...); |
1362 |
} |
1363 |
// Are param1 and param2 a pair of bidirectional input iterators (forward, bidir, random)? |
1364 |
else if constexpr(std::is_same_v<T1, T2> && is_bidir_input_v<T1>) |
1365 |
{ |
1366 |
//fprintf(stderr, "bidir input + bidir input\n"); |
1367 |
remove_cvref_t<T1> saved{param1}; |
1368 |
auto btfun = [&](bool act) { if(act) param1 = saved; else saved = std::move(param1); }; |
1369 |
auto inputfun = [&]() -> std::common_type_t<int, decltype(*param1)> |
1370 |
{ if(param1 == param2) { return -1; } int r = *param1; ++param1; return r; }; |
1371 |
return DeflateOutputDispatch<code|Flag_InputAbortable>(btfun, inputfun, std::forward<T>(args)...); |
1372 |
} |
1373 |
// Is param1 an input iterator and param2 a size? |
1374 |
else if constexpr(is_size_type_v<T2> && is_input_iterator_v<T1>) |
1375 |
{ |
1376 |
//fprintf(stderr, "input iterator + size\n"); |
1377 |
typename std::iterator_traits<remove_cvref_t<T1>>::difference_type remain{param2}; |
1378 |
auto inputfun = [&]() -> std::common_type_t<int, decltype(*param1)> |
1379 |
{ if(!remain) return -1; --remain; int r = *param1; ++param1; return r; }; |
1380 |
return DeflateOutputDispatch<code|Flag_InputAbortable>(std::forward<BtFun>(bt), inputfun, std::forward<T>(args)...); |
1381 |
} |
1382 |
// Is param1 a bidirectional input iterator (forward, bidir, random) and param2 a size? |
1383 |
else if constexpr(is_size_type_v<T2> && is_bidir_input_v<T1>) |
1384 |
{ |
1385 |
//fprintf(stderr, "bidir input + size\n"); |
1386 |
typename std::iterator_traits<remove_cvref_t<T1>>::difference_type remain{param2}, savestate{}; |
1387 |
auto btfun = [&](bool act) { if(act) { param1 -= (savestate-remain); remain = savestate; } else savestate = remain; }; |
1388 |
auto inputfun = [&]() -> std::common_type_t<int, decltype(*param1)> |
1389 |
{ if(!remain) return -1; --remain; int r = *param1; ++param1; return r; }; |
1390 |
return DeflateOutputDispatch<code|Flag_InputAbortable>(btfun, inputfun, std::forward<T>(args)...); |
1391 |
} |
1392 |
// Is param1 an input iterator? |
1393 |
else if constexpr(is_input_iterator_v<T1>) |
1394 |
{ |
1395 |
//fprintf(stderr, "input iterator\n"); |
1396 |
auto inputfun = [&]() -> std::remove_cv_t<decltype(*param1)> { auto r = *param1; ++param1; return r; }; |
1397 |
return DeflateOutputDispatch |
1398 |
<code | ( is_abortable_input_type_v<remove_cvref_t<decltype(*param1)>> ? Flag_InputAbortable : 0 ) > |
1399 |
(std::forward<BtFun>(bt), inputfun, std::forward<T2>(param2), std::forward<T>(args)...); |
1400 |
} |
1401 |
// Is param1 a bidirectional input iterator (forward, bidir, random)? |
1402 |
else if constexpr(is_bidir_input_v<T1>) |
1403 |
{ |
1404 |
//fprintf(stderr, "bidir input\n"); |
1405 |
remove_cvref_t<T1> saved{param1}; |
1406 |
auto btfun = [&](bool act) { if(act) param1 = saved; else saved = std::move(param1); }; |
1407 |
auto inputfun = [&]() -> std::remove_cv_t<decltype(*param1)> { auto r = *param1; ++param1; return r; }; |
1408 |
return DeflateOutputDispatch<code>(btfun, inputfun, std::forward<T2>(param2), std::forward<T>(args)...); |
1409 |
} |
1410 |
// param1 must be an input functor, then. Let's move on to param2 testing! |
1411 |
else if constexpr(is_input_functor_v<T1>) |
1412 |
{ |
1413 |
//fprintf(stderr, "input functor\n"); |
1414 |
return DeflateOutputDispatch |
1415 |
<code | ( DeflAbortable_InFun<T1> ? Flag_InputAbortable : 0 ) > |
1416 |
(std::forward<BtFun>(bt), std::forward<T1>(param1), std::forward<T2>(param2), std::forward<T>(args)...); |
1417 |
} |
1418 |
else |
1419 |
{ |
1420 |
//fprintf(stderr, "unreached code 0\n"); |
1421 |
static_assert(code==0xFF, "Deflate: Mismatched parameters. Expected something for an input."); |
1422 |
} |
1423 |
} |
1424 |
#undef DeflDeclWindow |
1425 |
} |
1426 |
|
1427 |
|
1428 |
template<typename... T> |
1429 |
auto Deflate(T&&... args) |
1430 |
{ |
1431 |
return gunzip_ns::DeflateInputDispatch<0>(gunzip_ns::dummy{}, std::forward<T>(args)...); |
1432 |
} |
1433 |
|
1434 |
#endif /* #ifndef DOXYGEN_SHOULD_SKIP_THIS */ |