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<uint8_t, 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(DiskName(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 (auto nrBits = narrow_cast<uint8_t>(cpdExt[cpdIndex] - 8);
217 nrBits--;
218 strPosMsb |= uint8_t(bitIn() ? 1 : 0)) {
219 strPosMsb <<= 1;
220 }
221 return strPosLsb + 256 * strPosMsb;
222 } else {
223 int pos = 0;
224 for (uint8_t nrBits = cpdExt[cpdIndex]; nrBits--;
225 pos |= (bitIn() ? 1 : 0)) {
226 pos <<= 1;
227 }
228 return pos;
229 }
230 }();
231 if ((updHufCnt--) == 0) {
232 mkHufTbl(); // make the huffman table
233 }
234 return strPos + cpDist[cpdIndex];
235}
236
237// read a bit from the input file
238bool XSAExtractor::bitIn()
239{
240 if (bitCnt == 0) {
241 bitFlg = charIn(); // read bitFlg
242 bitCnt = 8; // 8 bits left
243 }
244 bool temp = bitFlg & 1;
245 --bitCnt; // 1 bit less
246 bitFlg >>= 1;
247
248 return temp;
249}
250
251// initialize the huffman info tables
252void XSAExtractor::initHufInfo()
253{
254 int offs = 1;
255 for (auto i : xrange(TBL_SIZE)) {
256 cpDist[i] = offs;
257 cpdBmask[i] = 1 << cpdExt[i];
258 offs += cpdBmask[i];
259 }
260 cpDist[TBL_SIZE] = offs;
261
262 for (auto i : xrange(TBL_SIZE)) {
263 tblSizes[i] = 0; // reset the table counters
264 hufTbl[i].child1 = nullptr; // mark the leave nodes
265 }
266 mkHufTbl(); // make the huffman table
267}
268
269// Make huffman coding info
270void XSAExtractor::mkHufTbl()
271{
272 // Initialize the huffman tree
273 HufNode* hufPos = &hufTbl[0];
274 for (auto i : xrange(TBL_SIZE)) {
275 (hufPos++)->weight = 1 + (tblSizes[i] >>= 1);
276 }
277 for (int i = TBL_SIZE; i != 2 * TBL_SIZE - 1; ++i) {
278 (hufPos++)->weight = -1;
279 }
280 // Place the nodes in the correct manner in the tree
281 while (hufTbl[2 * TBL_SIZE - 2].weight == -1) {
282 for (hufPos = &hufTbl[0]; !(hufPos->weight); ++hufPos) {
283 // nothing
284 }
285 HufNode* l1Pos = hufPos++;
286 while (!(hufPos->weight)) {
287 ++hufPos;
288 }
289 HufNode* l2Pos = [&] {
290 if (hufPos->weight < l1Pos->weight) {
291 auto* tmp = l1Pos;
292 l1Pos = hufPos++;
293 return tmp;
294 } else {
295 return hufPos++;
296 }
297 }();
298 int tempW;
299 while ((tempW = hufPos->weight) != -1) {
300 if (tempW) {
301 if (tempW < l1Pos->weight) {
302 l2Pos = l1Pos;
303 l1Pos = hufPos;
304 } else if (tempW < l2Pos->weight) {
305 l2Pos = hufPos;
306 }
307 }
308 ++hufPos;
309 }
310 hufPos->weight = l1Pos->weight + l2Pos->weight;
311 (hufPos->child1 = l1Pos)->weight = 0;
312 (hufPos->child2 = l2Pos)->weight = 0;
313 }
314 updHufCnt = MAX_HUF_CNT;
315}
316
317} // namespace openmsx
std::span< const uint8_t > mmap()
Map file in memory.
Definition File.cc:102
This class represents a filename.
Definition Filename.hh:20
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)
std::pair< MemBuffer< SectorBuffer >, unsigned > extractData()
This file implemented 3 utility functions:
Definition Autofire.cc:11
auto copy(InputRange &&range, OutputIter out)
Definition ranges.hh:250
constexpr auto xrange(T e)
Definition xrange.hh:132