That Terminal
A terminal emulator designed for video making purposes.
gunzip.hh
Go to the documentation of this file.
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 */
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.
47 //
50 //
54 //
61 //
62 template<typename InputFunctor, typename OutputFunctor, typename WindowFunctor>
63 int Deflate(InputFunctor&& input, OutputFunctor&& output, WindowFunctor&& outputcopy);
64 
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 
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 
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 
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 
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 
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) | 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 
948  // Bit-by-bit input routine
949  #define DummyGetBits(numbits) do { \
950  auto p = state.template GetBits<bool(Abortable&Flag_InputAbortable)>(std::forward<InputFunctor>(input), numbits); \
951  if((Abortable & Flag_InputAbortable) && !~p) return -2; \
952  } while(0)
953 
954  #define GetBits(numbits, target) \
955  auto p = state.template GetBits<bool(Abortable&Flag_InputAbortable)>(std::forward<InputFunctor>(input), numbits); \
956  if((Abortable & Flag_InputAbortable) && !~p) return -2; \
957  target = p
958 
959  // Huffman tree read routine.
960  #define HuffRead(tree, target) \
961  auto p = state.template HuffRead<bool(Abortable&Flag_InputAbortable)>(std::forward<InputFunctor>(input), tree); \
962  if((Abortable & Flag_InputAbortable) && !~p) return -2; \
963  target = p
964 
965  #define Fail_If(condition) do { \
966  /*assert(!(condition));*/ \
967  if(condition) return -1; \
968  } while(0)
969 
970  // Read stream header
971  GetBits(16, std::uint_least16_t header);
972  // ^ Read deflate header: method[4] ; winsize[4] ; checksum[8]
973  if(header == 0x8B1F) // Is it actually a gzip header?
974  {
975  // Get format identifier, flags, MTIME, XFL and OS
976  GetBits(64, header); Fail_If((header & 0xFF) != 8); // Format identifier should be 8
977  if(header&0x0400) // Skip extra fields as indicated by FEXTRA
978  { GetBits(16, std::uint_fast16_t q); DummyGetBits(8*q); }
979  if(header&0x0800) for(;;) { GetBits(8, bool q); if(!q) break; } // NAME: Skip filename if FNAME was present
980  if(header&0x1000) for(;;) { GetBits(8, bool q); if(!q) break; } // COMMENT: Skip comment if FCOMMENT was present
981  if(header&0x0200) { DummyGetBits(16); } // HCRC: Skip FCRC if was present
982  outputcopy(0, 32768u); // GZIP always uses 32k window
983  }
984  else // No. Deflate header?
985  {
986  Fail_If((header & 0x208F) != 0x0008 || ((((header<<8)+(header>>8))&0xFFFF)%31) != 0);
987  outputcopy(0, 256 << ((header >> 4) & 0xF)); // Preset dictionary (0x2000) is not supported
988  }
989 
990  // Read compressed blocks
991  for(;;)
992  {
993  GetBits(3, header);
994  //fprintf(stderr, "header=%d\n", header);
995  if(header & 4) // Dynamic block
996  {
997  Fail_If(header & 2);
998  std::uint_least16_t nlen_ndist_ncode;
999  GetBits(14, nlen_ndist_ncode);
1000 
1001  #define nlen (((nlen_ndist_ncode >> 0u) & 0x1Fu) + 257u) // 257..288
1002  #define ndist (((nlen_ndist_ncode >> 5u) & 0x1Fu) + 1u) // 1..32
1003 
1004 
1005  std::uint_least8_t ncode = ((nlen_ndist_ncode >> 10u) + 4u); // 4..19
1006  {std::uint_fast64_t lenlens; GetBits(ncode*3, lenlens); // Max: 19*3 = 57 bits
1007  #ifdef DO_DEFDB_DUMPING
1008  fprintf(stderr, " [5] HLIT%5d (val:%d)\n [5] HDIST%4d (val:%d)\n [4] HCLEN%4d (val:%d)\n",
1009  nlen,nlen-257, ndist,ndist-1, ncode,ncode-4);
1010  for(unsigned a=0; a<19; ++a)
1011  for(unsigned b=0; b<19; ++b)
1012  if(rshift(b) == 3*a)
1013  {
1014  if(a < ncode)
1015  fprintf(stderr, " [3]%3d CLL (val: %d)\n", b, int((lenlens >> rshift(b)) & 7));
1016  else
1017  fprintf(stderr, " [_]%3d CLL (val: %d)\n", b, int((lenlens >> rshift(b)) & 7));
1018  }
1019  #endif
1020 
1021  auto lltree_fun = [=](unsigned a) -> unsigned char { return (lenlens >> rshift(a)) & 7; };
1022  while(CreateHuffmanTree<bool(Abortable&Flag_InputAbortable)>("Len Lengths", state.lltree, 19, lltree_fun)) { return -2; }}
1023 
1024  {auto ltree_fun = state.template DynTreeFunc<bool(Abortable&Flag_InputAbortable)>(std::forward<InputFunctor>(input), nlen, std::forward<BacktrackFunctor>(backtrack), false);
1025  while(CreateHuffmanTree<bool(Abortable&Flag_InputAbortable)>("Dyn Lengths", state.ltree, nlen, ltree_fun)) { return -2; }}
1026 
1027  {auto dtree_fun = state.template DynTreeFunc<bool(Abortable&Flag_InputAbortable)>(std::forward<InputFunctor>(input), ndist, std::forward<BacktrackFunctor>(backtrack), true);
1028  while(CreateHuffmanTree<bool(Abortable&Flag_InputAbortable)>("Dyn Dists", state.dtree, ndist, dtree_fun)) { return -2; }}
1029 
1030  #undef nlen
1031  #undef ndist
1032  }
1033  else // Fixed block
1034  {
1035  if(header < 2) // Copy stored block data
1036  {
1037  DummyGetBits(state.BitCount%8); // Go to byte boundary (discard a few bits)
1038  GetBits(32, std::uint_least32_t a);
1039  Fail_If(((a ^ (a >> 16)) & 0xFFFF) != 0xFFFF);
1040  #ifdef DO_DEFDB_DUMPING
1041  fprintf(stderr, "raw block of %d bytes (0x%X)\n", (unsigned short)a, a);
1042  #endif
1043  // Note: It is valid for (lower 16 bits of) "a" to be 0 here.
1044  // It is sometimes used for aligning the stream to byte boundary.
1045  while(a-- & 0xFFFF)
1046  {
1047  GetBits(8, unsigned char octet);
1048  while(OutputHelper<bool(Abortable&Flag_OutputAbortable)>::output(output, octet)) { return -3; }
1049  }
1050  goto skipdef;
1051  }
1052 
1053  unsigned char (*ltree_fun)(unsigned) = [](unsigned n)->unsigned char{return (n<0x90 || n>=0x118) ? 8u : (n<0x100 ? 9u : 7u); };
1054  unsigned char (*dtree_fun)(unsigned) = [](unsigned )->unsigned char{return 5u;};
1055  while(CreateHuffmanTree<false>("Stat Lengths", state.ltree, 288, ltree_fun)) { return -2; }
1056  while(CreateHuffmanTree<false>("Stat Dists", state.dtree, 32, dtree_fun)) { return -2; }
1057  }
1058  // Do actual deflating.
1059  for(;;)
1060  {
1061  #ifdef DO_DEFDB_DUMPING
1062  unsigned a=bitcounter;
1063  #endif
1064  HuffRead(state.ltree, std::uint_least16_t lencode); // 0..287
1065  if(!(lencode & -256)) // 0..255: literal byte
1066  {
1067  #ifdef DO_DEFDB_DUMPING
1068  {char tmp[64];sprintf(tmp,"[%d]",bitcounter-a); fprintf(stderr, "%4s %02X\n", tmp, lencode);}
1069  #endif
1070  while(OutputHelper<bool(Abortable&Flag_OutputAbortable)>::output(output, lencode)) { return -3; }
1071  }
1072  else if(!(lencode & 0xFF)) break; // 256=end
1073  else // 257..287: length code for backwards reference
1074  {
1075  GetBits(lbits(lencode), std::uint_least16_t length); length += lbase(lencode);
1076  {HuffRead(state.dtree, std::uint_least8_t distcode); // Read distance code (0..31)
1077  {GetBits(dbits(distcode), std::uint_least32_t offset); offset += dbase(distcode);
1078  #ifdef DO_DEFDB_DUMPING
1079  {char tmp[64];sprintf(tmp,"[%d]",bitcounter-a); fprintf(stderr, "%4s (%d,%d)\n", tmp,length,offset);}
1080  #endif
1081  while(OutputHelper<bool(Abortable&Flag_OutputAbortable)>::outputcopy(outputcopy,length,offset)) { return -4; }}}
1082  }
1083  }
1084  skipdef:if(header & 1) break; // last block flag
1085  }
1086  // Note: after this, may come a checksum, and a trailer. Ignoring them.
1087  #undef GetBits
1088  #undef DummyGetBits
1089  #undef Fail_If
1090  #undef HuffRead
1091  return 0;
1092  }
1093 }//ns
1094 
1095 
1096 /*
1097 `InputParams` may be one of the following sets of parameters:
1098 
1099 * InputFunctor input `(5)` `(14)`
1100 * InputIterator begin `(7)` `(14)`
1101 * InputIterator begin, InputIterator end `(6)` `(14)`
1102 * InputIterator begin, SizeType length `(8)` `(14)`
1103 * BidirectionalIterator begin, SizeType length `(8)` `(15)`
1104 * ForwardIterator begin `(7)` `(14)`
1105 * BidirectionalIterator begin `(7)` `(15)`
1106 * RandomAccessIterator begin `(7)` `(15)`
1107 * ForwardIterator begin, ForwardIterator end `(6)` `(15)`
1108 * BidirectionalIterator begin, BidirectionalIterator end `(6)` `(15)`
1109 * RandomAccessIterator begin, RandomAccessIterator end `(6)` `(15)`
1110 
1111 `OutputParams` may be one of the following sets of parameters:
1112 
1113 * OutputFunctor output `(1)` `(9)`
1114 * OutputFunctor output, WindowFunctor window `(2)`
1115 * OutputIterator target `(9)`
1116 * RandomAccessIterator target `(10)`
1117 * RandomAccessIterator target, SizeType target_limit `(3)` `(10)`
1118 * RandomAccessIterator target, RandomAccessIterator target_end `(4)` `(10)`
1119 */
1120 
1121 namespace gunzip_ns
1122 {
1123  #ifdef DEFLATE_ALLOCATION_AUTOMATIC
1124  #define DeflDeclWindow gunzip_ns::DeflateWindow window;
1125  #elif defined(DEFLATE_ALLOCATION_STATIC)
1126  #define DeflDeclWindow auto& window = gunzip_ns::GetStaticObj<gunzip_ns::DeflateWindow>();
1127  #elif defined(DEFLATE_ALLOCATION_DYNAMIC)
1128  #define DeflDeclWindow std::unique_ptr<gunzip_ns::DeflateWindow> winptr(new gunzip_ns::DeflateWindow); \
1129  auto& window = *winptr;
1130  #endif
1131 
1132  template<unsigned char code, typename I,typename O,typename C,typename B>
1133  auto DeflateDispatchFinal(I&& i, O&& o, C&& c, B&& b)
1134  {
1135  if constexpr(code & (Flag_TrackIn | Flag_TrackOut))
1136  {
1137  //fprintf(stderr, "both track flag\n");
1138  SizeTracker<DeflateTrackBothSize> tracker;
1139  return tracker(Gunzip<code & Flag_NoTrackFlagMask>
1140  (tracker.template ForwardInput(i), tracker.template ForwardOutput(o), tracker.template ForwardWindow(c), std::forward<B>(b)));
1141  }
1142  else if constexpr(code & Flag_TrackIn)
1143  {
1144  //fprintf(stderr, "in track flag\n");
1145  SizeTracker<DeflateTrackInSize> tracker;
1146  return tracker(Gunzip<code & Flag_NoTrackFlagMask>
1147  (tracker.template ForwardInput(i),std::forward<O>(o),std::forward<C>(c),std::forward<B>(b)));
1148  }
1149  else if constexpr(code & Flag_TrackOut)
1150  {
1151  //fprintf(stderr, "out track flag\n");
1152  SizeTracker<DeflateTrackOutSize> tracker;
1153  return tracker(Gunzip<code & Flag_NoTrackFlagMask>
1154  (std::forward<I>(i), tracker.template ForwardOutput(o), tracker.template ForwardWindow(c), std::forward<B>(b)));
1155  }
1156  else
1157  {
1158  //fprintf(stderr, "no track flag\n");
1159  return Gunzip<code & Flag_NoTrackFlagMask>(std::forward<I>(i),std::forward<O>(o),std::forward<C>(c),std::forward<B>(b));
1160  }
1161  }
1162 
1163  // One-parameter output dispatch:
1164  template<unsigned char code, typename BtFun, typename InFun, typename T1>
1165  auto DeflateOutputDispatch(BtFun&& bt, InFun&& infun, T1&& param1)
1166  {
1167  // Is param1 a random access iterator?
1168  if constexpr(is_random_iterator_v<T1>)
1169  {
1170  //fprintf(stderr, "random iterator\n");
1171  auto output = [&](unsigned char l) { *param1 = l; ++param1; };
1172  auto outputcopy = [&](std::uint_least16_t length, std::uint_fast32_t offs)
1173  {
1174  /* length=0 means that offs is the size of the window. */
1175  for(; length--; ++param1) { *param1 = *(param1-offs); }
1176  };
1177  return DeflateDispatchFinal<code>(std::forward<InFun>(infun), output, outputcopy, std::forward<BtFun>(bt));
1178  }
1179  // Is param1 an output iterator?
1180  else if constexpr(is_output_iterator_v<T1>)
1181  {
1182  //fprintf(stderr, "output iterator\n");
1183  DeflDeclWindow
1184  auto output = [&](unsigned char l)
1185  {
1186  window.Data[window.Head++ % MAX_WINDOW_SIZE] = l;
1187  *param1 = l; ++param1;
1188  };
1189  auto outputcopy = [&](std::uint_least16_t length, std::uint_fast32_t offs)
1190  {
1191  /* length=0 means that offs is the size of the window. */
1192  for(; length>0; --length)
1193  {
1194  unsigned char byte = window.Data[(window.Head - offs) % MAX_WINDOW_SIZE];
1195  output(byte);
1196  }
1197  return false;
1198  };
1199  return DeflateDispatchFinal<code>(std::forward<InFun>(infun), output, outputcopy, std::forward<BtFun>(bt));
1200  }
1201  // param1 must be an output functor, then.
1202  else if constexpr(is_output_functor_v<T1>)
1203  {
1204  //fprintf(stderr, "output functor\n");
1205  DeflDeclWindow
1206  auto output = [&](unsigned char l)
1207  {
1208  window.Data[window.Head++ % MAX_WINDOW_SIZE] = l;
1209  return param1(l);
1210  };
1211  auto outputcopy = [&](std::uint_least16_t length, std::uint_fast32_t offs)
1212  {
1213  /* length=0 means that offs is the size of the window. */
1214  for(; length>0; --length)
1215  {
1216  unsigned char byte = window.Data[(window.Head - offs) % MAX_WINDOW_SIZE];
1217  if(OutputHelper<DeflAbortable_OutFun<T1>>::output(output, byte))
1218  break;
1219  }
1220  return length;
1221  };
1222  return DeflateDispatchFinal
1223  <code | (DeflAbortable_OutFun<T1> ? Flag_OutputAbortable : 0)>
1224  (std::forward<InFun>(infun), output, outputcopy, std::forward<BtFun>(bt));
1225  }
1226  else
1227  {
1228  //fprintf(stderr, "unreached code 1\n");
1229  static_assert(code==0xFF, "Deflate: Unknown output parameter type");
1230  }
1231  }
1232 
1233  // Two-parameter output dispatch:
1234  template<unsigned char code, typename BtFun, typename InFun, typename T1, typename T2>
1235  auto DeflateOutputDispatch(BtFun&& bt, InFun&& infun, T1&& param1, T2&& param2)
1236  {
1237  if constexpr(std::is_same_v<remove_cvref_t<T2>, DeflateTrackNoSize>)
1238  {
1239  //fprintf(stderr, "no track flag...\n");
1240  return DeflateOutputDispatch<code> (std::forward<BtFun>(bt), std::forward<InFun>(infun), std::forward<T1>(param1));
1241  }
1242  else if constexpr(std::is_same_v<remove_cvref_t<T2>, DeflateTrackInSize>)
1243  {
1244  //fprintf(stderr, "in track flag...\n");
1245  return DeflateOutputDispatch<code | Flag_TrackIn> (std::forward<BtFun>(bt), std::forward<InFun>(infun), std::forward<T1>(param1));
1246  }
1247  else if constexpr(std::is_same_v<remove_cvref_t<T2>, DeflateTrackOutSize>)
1248  {
1249  //fprintf(stderr, "out track flag...\n");
1250  return DeflateOutputDispatch<code | Flag_TrackOut> (std::forward<BtFun>(bt), std::forward<InFun>(infun), std::forward<T1>(param1));
1251  }
1252  else if constexpr(std::is_same_v<remove_cvref_t<T2>, DeflateTrackBothSize>)
1253  {
1254  //fprintf(stderr, "both track flag...\n");
1255  return DeflateOutputDispatch<code | Flag_TrackIn | Flag_TrackOut> (std::forward<BtFun>(bt), std::forward<InFun>(infun), std::forward<T1>(param1));
1256  }
1257  // Are param1 and param2 both random access iterators?
1258  else if constexpr(std::is_same_v<T1,T2> && is_random_iterator_v<T1>)
1259  {
1260  //fprintf(stderr, "random iterator + random iterator\n");
1261  auto output = [&](unsigned char l)
1262  {
1263  if(param1 == param2) return true;
1264  *param1 = l; ++param1;
1265  return false;
1266  };
1267  auto outputcopy = [&](std::uint_least16_t length, std::uint_fast32_t offs)
1268  {
1269  /* length=0 means that offs is the size of the window. */
1270  for(; length > 0 && !(param1 == param2); --length, ++param1)
1271  {
1272  *param1 = *(param1 - offs);
1273  }
1274  return length;
1275  };
1276  return DeflateDispatchFinal<code | Flag_OutputAbortable>(std::forward<InFun>(infun), output, outputcopy, std::forward<BtFun>(bt));
1277  }
1278  // Is param1 a random access iterator and param2 a size?
1279  else if constexpr(is_size_type_v<T2> && is_random_iterator_v<T1>)
1280  {
1281  //fprintf(stderr, "random iterator + size\n");
1282  typename std::iterator_traits<remove_cvref_t<T1>>::difference_type used{}, cap=param2;
1283  auto output = [&](unsigned char l)
1284  {
1285  if(used >= cap) return true;
1286  param1[used] = l; ++used;
1287  return false;
1288  };
1289  auto outputcopy = [&](std::uint_least16_t length, std::uint_fast32_t offs)
1290  {
1291  /* length=0 means that offs is the size of the window. */
1292  for(; length > 0 && used < cap; ++used, --length)
1293  {
1294  param1[used] = param1[used - offs];
1295  }
1296  return length;
1297  };
1298  return DeflateDispatchFinal<code | Flag_OutputAbortable>(std::forward<InFun>(infun), output, outputcopy, std::forward<BtFun>(bt));
1299  }
1300  // Then, param1 must be an output functor and param2 a window functor.
1301  else if constexpr(is_output_functor_v<T1> && is_window_functor_v<T2>)
1302  {
1303  //fprintf(stderr, "output functor + window functor\n");
1304  return DeflateDispatchFinal
1305  <code | ( (DeflAbortable_OutFun<T1> && DeflAbortable_WinFun<T2>) ? Flag_OutputAbortable : 0 ) >
1306  (std::forward<InFun>(infun), std::forward<T1>(param1), std::forward<T2>(param2), std::forward<BtFun>(bt));
1307  }
1308  else
1309  {
1310  //fprintf(stderr, "unreached code 2\n");
1311  static_assert(code==0xFF, "Deflate: Unknown output parameter type");
1312  }
1313  }
1314 
1315  // Three-parameter output dispatch:
1316  template<unsigned char code, typename BtFun, typename InFun, typename T1, typename T2, typename T3>
1317  auto DeflateOutputDispatch(BtFun&& bt, InFun&& infun, T1&& p1, T2&& p2, T3)
1318  {
1319  if constexpr(std::is_same_v<remove_cvref_t<T3>, DeflateTrackNoSize>)
1320  {
1321  //fprintf(stderr, "no track flag...\n");
1322  return DeflateOutputDispatch<code> (std::forward<BtFun>(bt), std::forward<InFun>(infun), std::forward<T1>(p1), std::forward<T2>(p2));
1323  }
1324  else if constexpr(std::is_same_v<remove_cvref_t<T3>, DeflateTrackInSize>)
1325  {
1326  //fprintf(stderr, "in track flag...\n");
1327  return DeflateOutputDispatch<code | Flag_TrackIn> (std::forward<BtFun>(bt), std::forward<InFun>(infun), std::forward<T1>(p1), std::forward<T2>(p2));
1328  }
1329  else if constexpr(std::is_same_v<remove_cvref_t<T3>, DeflateTrackOutSize>)
1330  {
1331  //fprintf(stderr, "out track flag...\n");
1332  return DeflateOutputDispatch<code | Flag_TrackOut> (std::forward<BtFun>(bt), std::forward<InFun>(infun), std::forward<T1>(p1), std::forward<T2>(p2));
1333  }
1334  else if constexpr(std::is_same_v<remove_cvref_t<T3>, DeflateTrackBothSize>)
1335  {
1336  //fprintf(stderr, "both track flag...\n");
1337  return DeflateOutputDispatch<code | Flag_TrackIn | Flag_TrackOut> (std::forward<BtFun>(bt), std::forward<InFun>(infun), std::forward<T1>(p1), std::forward<T2>(p2));
1338  }
1339  else
1340  {
1341  //fprintf(stderr, "unreached code 3\n");
1342  static_assert(code==0xFF, "Deflate: Mismatched parameters. Expected last parameter to be a DeflateTrack option.");
1343  }
1344  }
1345 
1346  // One or two parameter input dispatch:
1347  template<unsigned char code, typename BtFun, typename T1, typename T2, typename... T>
1348  auto DeflateInputDispatch(BtFun&& bt, T1&& param1, T2&& param2, T&&... args)
1349  {
1350  using namespace gunzip_ns;
1351  // Are param1 and param2 an input iterator pair?
1352  if constexpr(std::is_same_v<T1, T2> && is_input_iterator_v<T1>)
1353  {
1354  //fprintf(stderr, "input iterator + input iterator\n");
1355  auto inputfun = [&]() -> std::common_type_t<int, decltype(*param1)>
1356  { if(param1 == param2) { return -1; } int r = *param1; ++param1; return r; };
1357  return DeflateOutputDispatch<code|Flag_InputAbortable>(std::forward<BtFun>(bt), inputfun, std::forward<T>(args)...);
1358  }
1359  // Are param1 and param2 a pair of bidirectional input iterators (forward, bidir, random)?
1360  else if constexpr(std::is_same_v<T1, T2> && is_bidir_input_v<T1>)
1361  {
1362  //fprintf(stderr, "bidir input + bidir input\n");
1363  remove_cvref_t<T1> saved{param1};
1364  auto btfun = [&](bool act) { if(act) param1 = saved; else saved = std::move(param1); };
1365  auto inputfun = [&]() -> std::common_type_t<int, decltype(*param1)>
1366  { if(param1 == param2) { return -1; } int r = *param1; ++param1; return r; };
1367  return DeflateOutputDispatch<code|Flag_InputAbortable>(btfun, inputfun, std::forward<T>(args)...);
1368  }
1369  // Is param1 an input iterator and param2 a size?
1370  else if constexpr(is_size_type_v<T2> && is_input_iterator_v<T1>)
1371  {
1372  //fprintf(stderr, "input iterator + size\n");
1373  typename std::iterator_traits<remove_cvref_t<T1>>::difference_type remain{param2};
1374  auto inputfun = [&]() -> std::common_type_t<int, decltype(*param1)>
1375  { if(!remain) return -1; --remain; int r = *param1; ++param1; return r; };
1376  return DeflateOutputDispatch<code|Flag_InputAbortable>(std::forward<BtFun>(bt), inputfun, std::forward<T>(args)...);
1377  }
1378  // Is param1 a bidirectional input iterator (forward, bidir, random) and param2 a size?
1379  else if constexpr(is_size_type_v<T2> && is_bidir_input_v<T1>)
1380  {
1381  //fprintf(stderr, "bidir input + size\n");
1382  typename std::iterator_traits<remove_cvref_t<T1>>::difference_type remain{param2}, savestate{};
1383  auto btfun = [&](bool act) { if(act) { param1 -= (savestate-remain); remain = savestate; } else savestate = remain; };
1384  auto inputfun = [&]() -> std::common_type_t<int, decltype(*param1)>
1385  { if(!remain) return -1; --remain; int r = *param1; ++param1; return r; };
1386  return DeflateOutputDispatch<code|Flag_InputAbortable>(btfun, inputfun, std::forward<T>(args)...);
1387  }
1388  // Is param1 an input iterator?
1389  else if constexpr(is_input_iterator_v<T1>)
1390  {
1391  //fprintf(stderr, "input iterator\n");
1392  auto inputfun = [&]() -> std::remove_cv_t<decltype(*param1)> { auto r = *param1; ++param1; return r; };
1393  return DeflateOutputDispatch
1394  <code | ( is_abortable_input_type_v<remove_cvref_t<decltype(*param1)>> ? Flag_InputAbortable : 0 ) >
1395  (std::forward<BtFun>(bt), inputfun, std::forward<T2>(param2), std::forward<T>(args)...);
1396  }
1397  // Is param1 a bidirectional input iterator (forward, bidir, random)?
1398  else if constexpr(is_bidir_input_v<T1>)
1399  {
1400  //fprintf(stderr, "bidir input\n");
1401  remove_cvref_t<T1> saved{param1};
1402  auto btfun = [&](bool act) { if(act) param1 = saved; else saved = std::move(param1); };
1403  auto inputfun = [&]() -> std::remove_cv_t<decltype(*param1)> { auto r = *param1; ++param1; return r; };
1404  return DeflateOutputDispatch<code>(btfun, inputfun, std::forward<T2>(param2), std::forward<T>(args)...);
1405  }
1406  // param1 must be an input functor, then. Let's move on to param2 testing!
1407  else if constexpr(is_input_functor_v<T1>)
1408  {
1409  //fprintf(stderr, "input functor\n");
1410  return DeflateOutputDispatch
1411  <code | ( DeflAbortable_InFun<T1> ? Flag_InputAbortable : 0 ) >
1412  (std::forward<BtFun>(bt), std::forward<T1>(param1), std::forward<T2>(param2), std::forward<T>(args)...);
1413  }
1414  else
1415  {
1416  //fprintf(stderr, "unreached code 0\n");
1417  static_assert(code==0xFF, "Deflate: Mismatched parameters. Expected something for an input.");
1418  }
1419  }
1420  #undef DeflDeclWindow
1421 }
1422 
1423 
1424 template<typename... T>
1425 auto Deflate(T&&... args)
1426 {
1427  return gunzip_ns::DeflateInputDispatch<0>(gunzip_ns::dummy{}, std::forward<T>(args)...);
1428 }
1429 
1430 #endif /* #ifndef DOXYGEN_SHOULD_SKIP_THIS */
DeflateTrackBothSize
Definition: gunzip.hh:73
DeflateTrackInSize
Definition: gunzip.hh:71
DeflateTrackNoSize
Definition: gunzip.hh:70
DeflateTrackOutSize
Definition: gunzip.hh:72
DeflateTrackTagBase
Definition: gunzip.hh:69