Debian Codegraph @

src/attic/Zip/ShrinkDecompressor.cpp

raw
1 /* Copyright (C) Teemu Suutari */
2
3 #include <cstdint>
4 #include <cstring>
5 #include <vector>
6
7 #include "ShrinkDecompressor.hpp"
8 #include "../InputStream.hpp"
9 #include "../OutputStream.hpp"
10
11
12 namespace ancient::internal
13 {
14
15 ShrinkDecompressor::ShrinkDecompressor(const Buffer &packedData) :
16 _packedData(packedData)
17 {
18
19 }
20
21 ShrinkDecompressor::~ShrinkDecompressor()
22 {
23 // nothing needed
24 }
25
26 size_t ShrinkDecompressor::getRawSize() const noexcept
27 {
28 // N/A
29 return 0;
30 }
31
32 size_t ShrinkDecompressor::getPackedSize() const noexcept
33 {
34 // N/A
35 return 0;
36 }
37
38 const std::string &ShrinkDecompressor::getName() const noexcept
39 {
40 static std::string name="Zip: Shrink";
41 return name;
42 }
43
44 void ShrinkDecompressor::decompressImpl(Buffer &rawData,bool verify)
45 {
46 ForwardInputStream inputStream(_packedData,0,_packedData.size());
47 LSBBitReader<ForwardInputStream> bitReader(inputStream);
48 auto readBits=[&](uint32_t count)->uint32_t
49 {
50 return bitReader.readBits8(count);
51 };
52
53 ForwardOutputStream outputStream(rawData,0,rawData.size());
54
55 const uint32_t maxCode=0x2000U;
56 auto prefix=std::make_unique<uint32_t[]>(maxCode-257);
57 auto suffix=std::make_unique<uint8_t[]>(maxCode-257);
58 auto stack=std::make_unique<uint8_t[]>(maxCode-257);
59
60 uint32_t freeIndex,codeBits,prevCode,newCode;
61
62 auto suffixLookup=[&](uint32_t code)->uint32_t
63 {
64 // main protection against negative values
65 if (code>=maxCode) throw DecompressionError();
66 return (code<257)?code:suffix[code-257];
67 };
68
69 auto insert=[&](uint32_t code)
70 {
71 uint32_t stackPos=0;
72 newCode=suffixLookup(code);
73 while (code>=257)
74 {
75 if (stackPos+1>=maxCode-257) throw DecompressionError();
76 stack[stackPos++]=newCode;
77 code=prefix[code-257];
78 newCode=suffixLookup(code);
79 }
80 stack[stackPos++]=newCode;
81 while (stackPos) outputStream.writeByte(stack[--stackPos]);
82 };
83
84 for (uint32_t i=0;i<maxCode-257;i++) prefix[i]=~0U;
85 codeBits=9;
86 freeIndex=257;
87 prevCode=readBits(codeBits);
88 insert(prevCode);
89
90 while (!outputStream.eof())
91 {
92 uint32_t code=readBits(codeBits);
93 if (code==256)
94 {
95 uint32_t tmp=readBits(codeBits);
96 if (tmp==1)
97 {
98 if (codeBits!=13) codeBits++;
99 } else if (tmp==2) {
100 std::vector<bool> usageMap(freeIndex-257,false);
101 for (uint32_t i=257;i<freeIndex;i++) {
102 uint32_t tmp=prefix[i-257];
103 if (!(tmp&0x8000'0000U) && tmp>=257) usageMap[tmp-257]=true;
104 }
105 uint32_t firstEmpty=freeIndex;
106 for (uint32_t i=257;i<freeIndex;i++)
107 {
108 if (!usageMap[i-257])
109 {
110 prefix[i-257]=~0U;
111 suffix[i-257]=0;
112 if (i<firstEmpty) firstEmpty=i;
113 }
114 }
115 freeIndex=firstEmpty;
116 } else throw DecompressionError();
117 } else {
118 if (code>=257 && (prefix[code-257]&0x8000'0000U))
119 {
120 uint32_t tmp=newCode;
121 insert(prevCode);
122 outputStream.writeByte(tmp);
123 } else insert(code);
124 while (!(prefix[freeIndex-257]&0x8000'0000U) && freeIndex<maxCode)
125 freeIndex++;
126 if (freeIndex<maxCode)
127 {
128 suffix[freeIndex-257]=newCode;
129 prefix[freeIndex-257]=prevCode;
130 freeIndex++;
131 }
132 prevCode=code;
133 }
134 }
135 }
136
137 }