Debian Codegraph @

src/attic/Lzh/PMDecompressor.cpp

raw
1 /* Copyright (C) Teemu Suutari */
2
3 #include "PMDecompressor.hpp"
4
5 #include "../HuffmanDecoder.hpp"
6 #include "../InputStream.hpp"
7 #include "../OutputStream.hpp"
8
9
10 namespace ancient::internal
11 {
12
13 PMDecompressor::PMDecompressor(const Buffer &packedData,uint32_t version) :
14 _packedData(packedData),
15 _version(version)
16 {
17 if (version!=1 && version!=2) throw InvalidFormatError();
18 }
19
20 PMDecompressor::~PMDecompressor()
21 {
22 // nothing needed
23 }
24
25 size_t PMDecompressor::getRawSize() const noexcept
26 {
27 // N/A
28 return 0;
29 }
30
31 size_t PMDecompressor::getPackedSize() const noexcept
32 {
33 // N/A
34 return 0;
35 }
36
37 const std::string &PMDecompressor::getName() const noexcept
38 {
39 static std::string name="LHA: PM1, PM2";
40 return name;
41 }
42
43 uint8_t PMDecompressor::decodeMTF(uint8_t value,uint8_t map[])
44 {
45 return map[value];
46 }
47
48 void PMDecompressor::updateMTF(uint8_t value,uint8_t map[])
49 {
50 for (uint32_t i=0;;i++)
51 {
52 if (map[i]==value)
53 {
54 value=i;
55 break;
56 }
57 }
58 if (value)
59 {
60 uint8_t tmp=map[value];
61 for (uint32_t i=value;i;i--)
62 map[i]=map[i-1];
63 map[0]=tmp;
64 }
65 }
66
67 void PMDecompressor::createMTFMap(uint8_t map[])
68 {
69 for (uint32_t i=0,j=0x20;j<0x80;i++,j++) map[i]=j;
70 for (uint32_t i=0x60,j=0;j<0x20;i++,j++) map[i]=j;
71 for (uint32_t i=0x80,j=0xa0;j<0xe0;i++,j++) map[i]=j;
72 for (uint32_t i=0xc0,j=0x80;j<0xa0;i++,j++) map[i]=j;
73 for (uint32_t i=0xe0,j=0xe0;j<0x100;i++,j++) map[i]=j;
74 }
75
76 void PMDecompressor::decompressImpl(Buffer &rawData,bool verify)
77 {
78 if (_version==1) decompressImplPM1(rawData,verify);
79 else decompressImplPM2(rawData,verify);
80 }
81
82 void PMDecompressor::decompressImplPM1(Buffer &rawData,bool verify)
83 {
84 static const struct {
85 uint8_t length;
86 uint8_t code;
87 } treeDefinitions[32][6] {
88 // This is madness, I had to write a special program to decode this.
89 // Also, in the original there is a bug @ index 17, as identified by
90 // lhasa (we fix it when creating the decoder)
91 {{4, 0b0000},{4, 0b0001},{3, 0b001},{2, 0b01},{2, 0b10},{2, 0b11}},
92 {{3, 0b000},{3, 0b001},{3, 0b010},{2, 0b10},{2, 0b11},{3, 0b011}},
93 {{3, 0b000},{3, 0b001},{2, 0b01},{2, 0b10},{3, 0b110},{3, 0b111}},
94 {{2, 0b00},{3, 0b010},{3, 0b011},{2, 0b10},{3, 0b110},{3, 0b111}},
95 {{2, 0b00},{3, 0b010},{2, 0b10},{3, 0b011},{3, 0b110},{3, 0b111}},
96 {{2, 0b00},{3, 0b010},{2, 0b10},{2, 0b11},{4, 0b0110},{4, 0b0111}},
97 {{2, 0b00},{2, 0b01},{3, 0b100},{3, 0b101},{3, 0b110},{3, 0b111}},
98 {{2, 0b00},{2, 0b01},{3, 0b100},{2, 0b11},{4, 0b1010},{4, 0b1011}},
99
100 {{2, 0b00},{2, 0b01},{2, 0b10},{3, 0b110},{4, 0b1110},{4, 0b1111}},
101 {{1, 0b0},{4, 0b1000},{3, 0b101},{3, 0b110},{3, 0b111},{4, 0b1001}},
102 {{1, 0b0},{4, 0b1000},{3, 0b101},{2, 0b11},{5,0b10010},{5,0b10011}},
103 {{1, 0b0},{4, 0b1000},{4, 0b1001},{3, 0b101},{3, 0b110},{3, 0b111}},
104 {{1, 0b0},{3, 0b100},{4, 0b1010},{3, 0b110},{3, 0b111},{4, 0b1011}},
105 {{1, 0b0},{3, 0b100},{3, 0b101},{3, 0b110},{4, 0b1110},{4, 0b1111}},
106 {{1, 0b0},{3, 0b100},{2, 0b11},{4, 0b1010},{5,0b10110},{5,0b10111}},
107 {{1, 0b0},{2, 0b10},{4, 0b1100},{4, 0b1101},{4, 0b1110},{4, 0b1111}},
108
109 {{1, 0b0},{2, 0b10},{3, 0b110},{4, 0b1110},{5,0b11110},{5,0b11111}},
110 {{3, 0b000},{3, 0b001},{2, 0b01},{2, 0b10},{2, 0b11},{0, 0b0}},
111 {{2, 0b00},{3, 0b010},{2, 0b10},{2, 0b11},{3, 0b011},{0, 0b0}},
112 {{2, 0b00},{2, 0b01},{2, 0b10},{3, 0b110},{3, 0b111},{0, 0b0}},
113 {{1, 0b0},{4, 0b1000},{3, 0b101},{2, 0b11},{4, 0b1001},{0, 0b0}},
114 {{1, 0b0},{3, 0b100},{3, 0b101},{3, 0b110},{3, 0b111},{0, 0b0}},
115 {{1, 0b0},{3, 0b100},{2, 0b11},{4, 0b1010},{4, 0b1011},{0, 0b0}},
116 {{1, 0b0},{2, 0b10},{3, 0b110},{4, 0b1110},{4, 0b1111},{0, 0b0}},
117
118 {{3, 0b000},{3, 0b001},{2, 0b01},{1, 0b1},{0, 0b0},{0, 0b0}},
119 {{2, 0b00},{3, 0b010},{1, 0b1},{3, 0b011},{0, 0b0},{0, 0b0}},
120 {{2, 0b00},{2, 0b01},{2, 0b10},{2, 0b11},{0, 0b0},{0, 0b0}},
121 {{1, 0b0},{3, 0b100},{2, 0b11},{3, 0b101},{0, 0b0},{0, 0b0}},
122 {{1, 0b0},{2, 0b10},{3, 0b110},{3, 0b111},{0, 0b0},{0, 0b0}},
123 {{1, 0b0},{2, 0b10},{2, 0b11},{0, 0b0},{0, 0b0},{0, 0b0}},
124 {{1, 0b0},{1, 0b1},{0, 0b0},{0, 0b0},{0, 0b0},{0, 0b0}},
125 {{0, 0b0},{1, 0b1},{0, 0b0},{0, 0b0},{0, 0b0},{0, 0b0}}
126 };
127
128 ForwardInputStream inputStream(_packedData,0,_packedData.size(),true);
129
130 MSBBitReader<ForwardInputStream> bitReader(inputStream);
131 auto readBits=[&](uint32_t count)->uint32_t
132 {
133 return bitReader.readBits8(count);
134 };
135 auto readBit=[&]()->uint32_t
136 {
137 return bitReader.readBits8(1);
138 };
139
140 size_t rawSize=rawData.size();
141 ForwardOutputStream outputStream(rawData,0,rawSize);
142
143 OptionalHuffmanDecoder<uint32_t> decoder;
144 {
145 uint32_t treeIndex=readBits(5);
146 for (uint32_t i=0;i<6;i++)
147 {
148 uint32_t length=treeDefinitions[treeIndex][i].length;
149 uint32_t code=treeDefinitions[treeIndex][i].code;
150 if (!length)
151 {
152 if (!i) decoder.setEmpty(0);
153 break;
154 }
155 if (treeIndex==17 && i<2) decoder.insert(HuffmanCode<uint32_t>{length,code,i+3});
156 else decoder.insert(HuffmanCode<uint32_t>{length,code,i});
157 }
158 }
159
160 uint8_t dataMTFMap[256];
161 createMTFMap(dataMTFMap);
162
163 auto processOutput=[&](uint8_t value)->uint8_t
164 {
165 updateMTF(value,dataMTFMap);
166 return value;
167 };
168
169 while (!outputStream.eof())
170 {
171 bool doCopy=true;
172 if (readBit())
173 {
174 uint32_t count=readBits(2)+1;
175 if (count==4)
176 {
177 count=readBits(3)+4;
178 if (count==11)
179 {
180 count=readBits(4)+11;
181 if (count==25)
182 {
183 count=readBits(6)+25;
184 } else if (count==26) {
185 count=readBits(7)+89;
186 }
187 }
188 }
189
190 count=std::min(count,uint32_t(rawSize-outputStream.getOffset()));
191 for (uint32_t i=0;i<count;i++)
192 {
193 uint32_t code=decoder.decode(readBit);
194 static const uint32_t symbolAdditions[6]={0,16,32,64,128,192};
195 static const uint32_t symbolBits[6]={4,4,5,6,6,6};
196 outputStream.writeByte(processOutput(decodeMTF(readBits(symbolBits[code])+symbolAdditions[code],dataMTFMap)));
197 }
198 doCopy=count!=216&&!outputStream.eof();
199 }
200 if (doCopy)
201 {
202 uint32_t offset=uint32_t(outputStream.getOffset());
203 uint32_t count,code;
204 if (!readBit())
205 {
206 if (offset>=0x240?readBit():0)
207 {
208 code=4;
209 if (offset<0x340) code=7;
210 else if (offset<0x440) code=8;
211 else if (offset<0x640) code=9;
212 } else {
213 code=offset>=0x40?readBit():0;
214 count=2;
215 }
216 } else {
217 if (offset>=0x40?!readBit():0)
218 {
219 code=3;
220 if (offset<0x140) code=6;
221 } else if (offset>=0xa40?readBit():1) {
222 code=2;
223 } else {
224 code=5;
225 if (offset<0xb40) code=10;
226 else if (offset<0xc40) code=11;
227 else if (offset<0xe40) code=12;
228 else if (offset<0x1240) code=13;
229 else if (offset<0x1a40) code=14;
230 }
231 }
232 if (code>=2)
233 {
234 count=readBits(2)+3;
235 if (count==6)
236 {
237 count=readBits(3)+6;
238 if (count==11)
239 {
240 count=readBits(2)+11;
241 } else if (count==12) {
242 count=readBits(3)+15;
243 } else if (count==13) {
244 count=readBits(6)+23;
245 if (count==85) {
246 count=readBits(5)+85;
247 } else if (count==86)
248 count=readBits(7)+117;
249 }
250 }
251 }
252 static const uint32_t distanceAdditions[15]={
253 1,0x41,1,0x41,0x241,0xa41,0x41,0x241,0x241,0x241,0xa41,0xa41,0xa41,0xa41,0xa41};
254 static const uint32_t distanceBits[15]={
255 6,8,6,9,11,13,8,8,9,10,8,9,10,11,12};
256 uint32_t distance=readBits(distanceBits[code])+distanceAdditions[code];
257
258 count=std::min(count,uint32_t(rawSize-outputStream.getOffset()));
259 outputStream.copy(distance,count,0x20);
260 const uint8_t *block=outputStream.history(count);
261 for (uint32_t i=0;i<count;i++)
262 processOutput(block[i]);
263 }
264 }
265 }
266
267 void PMDecompressor::decompressImplPM2(Buffer &rawData,bool verify)
268 {
269 ForwardInputStream inputStream(_packedData,0,_packedData.size());
270
271 MSBBitReader<ForwardInputStream> bitReader(inputStream);
272 auto readBits=[&](uint32_t count)->uint32_t
273 {
274 return bitReader.readBits8(count);
275 };
276 auto readBit=[&]()->uint32_t
277 {
278 return bitReader.readBits8(1);
279 };
280
281 ForwardOutputStream outputStream(rawData,0,rawData.size());
282
283 OptionalHuffmanDecoder<uint32_t> decoder;
284 OptionalHuffmanDecoder<uint32_t> distanceDecoder;
285
286 auto createDecoder=[&]()->bool
287 {
288 decoder.reset();
289
290 // codes beyond 29 are going to fault anyway, but maybe they are not used?
291 uint8_t symbols[31];
292 uint32_t numCodes=readBits(5);
293 uint32_t minLength=readBits(3);
294
295 bool ret=(numCodes>=10)&&(numCodes!=29||minLength);
296
297 if (!minLength)
298 {
299 if (!numCodes) throw DecompressionError();
300 decoder.setEmpty(numCodes-1);
301 } else {
302 uint32_t codeLength=readBits(3);
303 for (uint32_t i=0;i<numCodes;i++)
304 {
305 uint32_t value=readBits(codeLength);
306 symbols[i]=value?minLength+value-1:0;
307 }
308 decoder.createOrderlyHuffmanTable(symbols,numCodes);
309 }
310 return ret;
311 };
312
313 auto createDistanceDecoder=[&](uint32_t numCodes)
314 {
315 distanceDecoder.reset();
316
317 uint8_t distances[8];
318
319 uint32_t last=0,total=0;
320 for (uint32_t i=0;i<numCodes;i++)
321 {
322 uint32_t length=readBits(3);
323 distances[i]=length;
324 if (length)
325 {
326 total++;
327 last=i;
328 }
329 }
330 if (!total)
331 {
332 throw DecompressionError();
333 } else if (total==1) {
334 distanceDecoder.setEmpty(last);
335 } else {
336 distanceDecoder.createOrderlyHuffmanTable(distances,numCodes);
337 }
338 };
339
340 uint8_t dataMTFMap[256];
341 createMTFMap(dataMTFMap);
342
343 bool distanceTreeRequired;
344 auto processOutput=[&](size_t offset,uint8_t value)->uint8_t
345 {
346 offset++; // we are interested offset after the update
347 updateMTF(value,dataMTFMap);
348 if (!(offset&0x3ffU))
349 {
350 switch (offset>>10)
351 {
352 case 1:
353 if (distanceTreeRequired) createDistanceDecoder(6);
354 break;
355
356 case 2:
357 if (distanceTreeRequired) createDistanceDecoder(7);
358 break;
359
360 case 4:
361 if (readBit()) distanceTreeRequired=createDecoder();
362 if (distanceTreeRequired) createDistanceDecoder(8);
363 break;
364
365 default:
366 if (!(offset&0xfffU) && (offset>>12)>=2)
367 {
368 if (readBit())
369 {
370 distanceTreeRequired=createDecoder();
371 if (distanceTreeRequired) createDistanceDecoder(8);
372 }
373 }
374 break;
375 }
376 }
377 return value;
378 };
379
380 readBit(); // ignore first bit
381 distanceTreeRequired=createDecoder();
382 if (distanceTreeRequired) createDistanceDecoder(5);
383 while (!outputStream.eof())
384 {
385 uint32_t code=decoder.decode(readBit);
386 if (code<8)
387 {
388 static const uint32_t symbolAdditions[8]={0,8,16,32,64,96,128,192};
389 static const uint32_t symbolBits[8]={3,3,4,5,5,5,6,6};
390 outputStream.writeByte(processOutput(outputStream.getOffset(),decodeMTF(readBits(symbolBits[code])+symbolAdditions[code],dataMTFMap)));
391 } else {
392 code-=8;
393
394 uint32_t count;
395 if (code<15)
396 {
397 count=code+2;
398 } else {
399 if (code>=21) throw DecompressionError();
400 static const uint32_t countAdditions[6]={17,25,33,65,129,256};
401 static const uint32_t countBits[6]={3,3,5,6,7,0};
402 count=readBits(countBits[code-15])+countAdditions[code-15];
403 }
404
405 uint32_t distance;
406 if (!code)
407 {
408 distance=readBits(6)+1;
409 } else if (code<20) {
410 uint32_t tmp=distanceDecoder.decode(readBit);
411 if (!tmp) distance=readBits(6)+1;
412 else distance=readBits(tmp+5)+(1<<(tmp+5))+1;
413 } else distance=1;
414
415 outputStream.copy(distance,count,0x20);
416 const uint8_t *block=outputStream.history(count);
417 size_t offset=outputStream.getOffset()-count;
418 for (uint32_t i=0;i<count;i++)
419 processOutput(offset+i,block[i]);
420 }
421 }
422 }
423
424 }