Debian Codegraph @

src/attic/Zip/ImplodeDecompressor.cpp

raw
1 /* Copyright (C) Teemu Suutari */
2
3 #include <cstdint>
4 #include <cstring>
5
6 #include "ImplodeDecompressor.hpp"
7 #include "../InputStream.hpp"
8 #include "../OutputStream.hpp"
9 #include "../HuffmanDecoder.hpp"
10
11
12 namespace ancient::internal
13 {
14
15 ImplodeDecompressor::ImplodeDecompressor(const Buffer &packedData,uint32_t flags) :
16 _packedData(packedData),
17 _flags(flags)
18 {
19
20 }
21
22 ImplodeDecompressor::~ImplodeDecompressor()
23 {
24 // nothing needed
25 }
26
27 size_t ImplodeDecompressor::getRawSize() const noexcept
28 {
29 // N/A
30 return 0;
31 }
32
33 size_t ImplodeDecompressor::getPackedSize() const noexcept
34 {
35 // N/A
36 return 0;
37 }
38
39 const std::string &ImplodeDecompressor::getName() const noexcept
40 {
41 static std::string name="Zip: Implode";
42 return name;
43 }
44
45 void ImplodeDecompressor::decompressImpl(Buffer &rawData,bool verify)
46 {
47 ForwardInputStream inputStream(_packedData,0,_packedData.size());
48 LSBBitReader<ForwardInputStream> bitReader(inputStream);
49 auto readBits=[&](uint32_t count)->uint32_t
50 {
51 return bitReader.readBits8(count);
52 };
53 auto readBit=[&]()->uint32_t
54 {
55 return bitReader.readBits8(1);
56 };
57
58 ForwardOutputStream outputStream(rawData,0,rawData.size());
59
60 // Although Implode uses Fannon-Shano, Huffman decoder can be used
61 typedef HuffmanDecoder<uint8_t> ImplodeHuffmanDecoder;
62
63 auto createDecoder=[&](ImplodeHuffmanDecoder &dec,uint32_t maxValue)
64 {
65 uint32_t length=readBits(8)+1;
66 uint8_t bitLengths[257];
67 uint8_t counts[257];
68 uint8_t offsets[257];
69 uint8_t minDepth=32,maxDepth=0;
70
71 for (uint32_t i=0;i<length;i++)
72 {
73 bitLengths[i]=readBits(4)+1;
74 counts[i]=readBits(4)+1;
75 offsets[i]=i?offsets[i-1]+counts[i-1]:0;
76 if (bitLengths[i]<minDepth) minDepth=bitLengths[i];
77 if (bitLengths[i]>maxDepth) maxDepth=bitLengths[i];
78 }
79 if (static_cast<uint32_t>(offsets[length-1]+counts[length-1])>maxValue) throw DecompressionError();
80
81 uint32_t code=0;
82 for (uint32_t depth=maxDepth;depth>=minDepth;depth--)
83 {
84 for (int32_t i=length-1;i>=0;i--)
85 {
86 if (depth!=bitLengths[i]) continue;
87 for (uint32_t j=counts[i];j>0;j--)
88 {
89 dec.insert(HuffmanCode<uint8_t>{depth,code>>(maxDepth-depth),uint8_t(offsets[i]+j-1)});
90 code+=1<<(maxDepth-depth);
91 }
92 }
93 }
94 };
95
96 ImplodeHuffmanDecoder lengthDecoder,distanceDecoder,litDecoder;
97
98 uint32_t extraDistanceBits=(_flags&2)?7:6;
99 bool literalDecPresent=_flags&4;
100 uint32_t lengthAddition=2;
101
102 if (literalDecPresent)
103 {
104 createDecoder(litDecoder,256);
105 lengthAddition++;
106 }
107 createDecoder(lengthDecoder,64);
108 createDecoder(distanceDecoder,64);
109
110 while (!outputStream.eof())
111 {
112 if (readBit())
113 {
114 if (literalDecPresent) outputStream.writeByte(litDecoder.decode(readBit));
115 else outputStream.writeByte(readBits(8));
116 } else {
117 uint32_t distance=readBits(extraDistanceBits);
118 distance|=uint32_t(distanceDecoder.decode(readBit))<<extraDistanceBits;
119 distance++;
120
121 uint32_t count=lengthDecoder.decode(readBit);
122 if (count==63) count+=readBits(8);
123 count+=lengthAddition;
124
125 outputStream.copy(distance,count,0);
126 }
127 }
128 }
129
130 }