openMSX
XSADiskImage.cc
Go to the documentation of this file.
1#include "XSADiskImage.hh"
2#include "DiskExceptions.hh"
3#include "File.hh"
4#include "narrow.hh"
5#include "xrange.hh"
6#include <array>
7#include <utility>
8
9namespace openmsx {
10
12{
13public:
14 explicit XSAExtractor(File& file);
15 std::pair<MemBuffer<SectorBuffer>, unsigned> extractData();
16
17private:
18 static constexpr int MAX_STR_LEN = 254;
19 static constexpr int TBL_SIZE = 16;
20 static constexpr int MAX_HUF_CNT = 127;
21
22 [[nodiscard]] inline uint8_t charIn();
23 void chkHeader();
24 void unLz77();
25 [[nodiscard]] unsigned rdStrLen();
26 [[nodiscard]] int rdStrPos();
27 [[nodiscard]] bool bitIn();
28 void initHufInfo();
29 void mkHufTbl();
30
31 struct HufNode {
32 HufNode* child1;
33 HufNode* child2;
34 int weight;
35 };
36
37private:
38 MemBuffer<SectorBuffer> outBuf; // the output buffer
39 std::span<const uint8_t>::iterator inBufPos; // pos in input buffer
40 std::span<const uint8_t>::iterator inBufEnd;
41 unsigned sectors;
42
43 int updHufCnt;
44 std::array<int, TBL_SIZE + 1> cpDist;
45 std::array<int, TBL_SIZE> cpdBmask;
46 std::array<int, TBL_SIZE> tblSizes;
47 std::array<HufNode, 2 * TBL_SIZE - 1> hufTbl;
48
49 uint8_t bitFlg; // flag with the bits
50 uint8_t bitCnt; // nb bits left
51
52 static constexpr std::array<int, TBL_SIZE> cpdExt = { // Extra bits for distance codes
53 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
54 };
55};
56
57
58// XSADiskImage
59
61 : SectorBasedDisk(filename)
62{
63 XSAExtractor extractor(file);
64 auto [d, sectors] = extractor.extractData();
65 data = std::move(d);
66 setNbSectors(sectors);
67}
68
69void XSADiskImage::readSectorsImpl(
70 std::span<SectorBuffer> buffers, size_t startSector)
71{
72 ranges::copy(std::span{&data[startSector], buffers.size()}, buffers);
73}
74
75void XSADiskImage::writeSectorImpl(size_t /*sector*/, const SectorBuffer& /*buf*/)
76{
77 throw WriteProtectedException("Write protected");
78}
79
80bool XSADiskImage::isWriteProtectedImpl() const
81{
82 return true;
83}
84
85
86// XSAExtractor
87
89{
90 auto mmap = file.mmap();
91 inBufPos = mmap.begin();
92 inBufEnd = mmap.end();
93
94 if ((charIn() != 'P') || (charIn() != 'C') ||
95 (charIn() != 'K') || (charIn() != '\010')) {
96 throw MSXException("Not an XSA image");
97 }
98
99 chkHeader();
100 initHufInfo(); // initialize the cpDist tables
101 unLz77();
102}
103
104std::pair<MemBuffer<SectorBuffer>, unsigned> XSAExtractor::extractData()
105{
106 // destroys internal outBuf, but that's ok
107 return {std::move(outBuf), sectors};
108}
109
110// Get the next character from the input buffer
111uint8_t XSAExtractor::charIn()
112{
113 if (inBufPos >= inBufEnd) {
114 throw MSXException("Corrupt XSA image: unexpected end of file");
115 }
116 return *inBufPos++;
117}
118
119// check fileheader
120void XSAExtractor::chkHeader()
121{
122 // read original length (little endian)
123 unsigned outBufLen = 0;
124 for (auto i : xrange(4)) {
125 outBufLen |= charIn() << (8 * i);
126 }
127 sectors = (outBufLen + 511) / 512;
128 outBuf.resize(sectors);
129
130 // skip compressed length
131 inBufPos += 4;
132
133 // skip original filename
134 while (charIn()) /*empty*/;
135}
136
137// the actual decompression algorithm itself
138void XSAExtractor::unLz77()
139{
140 bitCnt = 0; // no bits read yet
141
142 size_t remaining = sectors * sizeof(SectorBuffer);
143 std::span out = outBuf.data()->raw;
144 size_t outIdx = 0;
145 while (true) {
146 if (bitIn()) {
147 // 1-bit
148 unsigned strLen = rdStrLen();
149 if (strLen == (MAX_STR_LEN + 1)) {
150 return;
151 }
152 unsigned strPos = rdStrPos();
153 if ((strPos == 0) || (strPos > outIdx)) {
154 throw MSXException(
155 "Corrupt XSA image: invalid offset");
156 }
157 if (remaining < strLen) {
158 throw MSXException(
159 "Invalid XSA image: too small output buffer");
160 }
161 remaining -= strLen;
162 while (strLen--) {
163 out[outIdx] = out[outIdx - strPos];
164 ++outIdx;
165 }
166 } else {
167 // 0-bit
168 if (remaining == 0) {
169 throw MSXException(
170 "Invalid XSA image: too small output buffer");
171 }
172 --remaining;
173 out[outIdx++] = charIn();
174 }
175 }
176}
177
178// read string length
179unsigned XSAExtractor::rdStrLen()
180{
181 if (!bitIn()) return 2;
182 if (!bitIn()) return 3;
183 if (!bitIn()) return 4;
184
185 uint8_t nrBits = 2;
186 while ((nrBits != 7) && bitIn()) {
187 ++nrBits;
188 }
189
190 unsigned len = 1;
191 while (nrBits--) {
192 len = (len << 1) | (bitIn() ? 1 : 0);
193 }
194 return (len + 1);
195}
196
197// read string pos
198int XSAExtractor::rdStrPos()
199{
200 HufNode* hufPos = &hufTbl[2 * TBL_SIZE - 2];
201
202 while (hufPos->child1) {
203 if (bitIn()) {
204 hufPos = hufPos->child2;
205 } else {
206 hufPos = hufPos->child1;
207 }
208 }
209 auto cpdIndex = narrow<uint8_t>(hufPos - &hufTbl[0]);
210 ++tblSizes[cpdIndex];
211
212 int strPos = [&] {
213 if (cpdBmask[cpdIndex] >= 256) {
214 uint8_t strPosLsb = charIn();
215 uint8_t strPosMsb = 0;
216 for (uint8_t nrBits = cpdExt[cpdIndex] - 8; nrBits--;
217 strPosMsb |= (bitIn() ? 1 : 0)) {
218 strPosMsb <<= 1;
219 }
220 return strPosLsb + 256 * strPosMsb;
221 } else {
222 int pos = 0;
223 for (uint8_t nrBits = cpdExt[cpdIndex]; nrBits--;
224 pos |= (bitIn() ? 1 : 0)) {
225 pos <<= 1;
226 }
227 return pos;
228 }
229 }();
230 if ((updHufCnt--) == 0) {
231 mkHufTbl(); // make the huffman table
232 }
233 return strPos + cpDist[cpdIndex];
234}
235
236// read a bit from the input file
237bool XSAExtractor::bitIn()
238{
239 if (bitCnt == 0) {
240 bitFlg = charIn(); // read bitFlg
241 bitCnt = 8; // 8 bits left
242 }
243 bool temp = bitFlg & 1;
244 --bitCnt; // 1 bit less
245 bitFlg >>= 1;
246
247 return temp;
248}
249
250// initialize the huffman info tables
251void XSAExtractor::initHufInfo()
252{
253 int offs = 1;
254 for (auto i : xrange(TBL_SIZE)) {
255 cpDist[i] = offs;
256 cpdBmask[i] = 1 << cpdExt[i];
257 offs += cpdBmask[i];
258 }
259 cpDist[TBL_SIZE] = offs;
260
261 for (auto i : xrange(TBL_SIZE)) {
262 tblSizes[i] = 0; // reset the table counters
263 hufTbl[i].child1 = nullptr; // mark the leave nodes
264 }
265 mkHufTbl(); // make the huffman table
266}
267
268// Make huffman coding info
269void XSAExtractor::mkHufTbl()
270{
271 // Initialize the huffman tree
272 HufNode* hufPos = &hufTbl[0];
273 for (auto i : xrange(TBL_SIZE)) {
274 (hufPos++)->weight = 1 + (tblSizes[i] >>= 1);
275 }
276 for (int i = TBL_SIZE; i != 2 * TBL_SIZE - 1; ++i) {
277 (hufPos++)->weight = -1;
278 }
279 // Place the nodes in the correct manner in the tree
280 while (hufTbl[2 * TBL_SIZE - 2].weight == -1) {
281 for (hufPos = &hufTbl[0]; !(hufPos->weight); ++hufPos) {
282 // nothing
283 }
284 HufNode* l1Pos = hufPos++;
285 while (!(hufPos->weight)) {
286 ++hufPos;
287 }
288 HufNode* l2Pos = [&] {
289 if (hufPos->weight < l1Pos->weight) {
290 auto* tmp = l1Pos;
291 l1Pos = hufPos++;
292 return tmp;
293 } else {
294 return hufPos++;
295 }
296 }();
297 int tempW;
298 while ((tempW = hufPos->weight) != -1) {
299 if (tempW) {
300 if (tempW < l1Pos->weight) {
301 l2Pos = l1Pos;
302 l1Pos = hufPos;
303 } else if (tempW < l2Pos->weight) {
304 l2Pos = hufPos;
305 }
306 }
307 ++hufPos;
308 }
309 hufPos->weight = l1Pos->weight + l2Pos->weight;
310 (hufPos->child1 = l1Pos)->weight = 0;
311 (hufPos->child2 = l2Pos)->weight = 0;
312 }
313 updHufCnt = MAX_HUF_CNT;
314}
315
316} // namespace openmsx
std::span< const uint8_t > mmap()
Map file in memory.
Definition: File.cc:102
This class represents a filename.
Definition: Filename.hh:18
This class manages the lifetime of a block of memory.
Definition: MemBuffer.hh:29
Abstract class for disk images that only represent the logical sector information (so not the raw tra...
void setNbSectors(size_t num)
XSADiskImage(Filename &filename, File &file)
Definition: XSADiskImage.cc:60
XSAExtractor(File &file)
Definition: XSADiskImage.cc:88
std::pair< MemBuffer< SectorBuffer >, unsigned > extractData()
This file implemented 3 utility functions:
Definition: Autofire.cc:9
auto copy(InputRange &&range, OutputIter out)
Definition: ranges.hh:232
constexpr auto xrange(T e)
Definition: xrange.hh:133