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