openMSX
XSADiskImage.cc
Go to the documentation of this file.
1 #include "XSADiskImage.hh"
2 #include "DiskExceptions.hh"
3 #include "File.hh"
4 #include <cstring>
5 #include <utility>
6 
7 using std::string;
8 
9 namespace openmsx {
10 
12 {
13 public:
14  explicit XSAExtractor(File& file);
15  std::pair<MemBuffer<SectorBuffer>, unsigned> extractData();
16 
17 private:
18  static constexpr int MAXSTRLEN = 254;
19  static constexpr int TBLSIZE = 16;
20  static constexpr int MAXHUFCNT = 127;
21 
22  [[nodiscard]] inline byte 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 
37 private:
38  MemBuffer<SectorBuffer> outBuf; // the output buffer
39  const byte* inBufPos; // pos in input buffer
40  const byte* inBufEnd;
41  unsigned sectors;
42 
43  int updHufCnt;
44  int cpDist[TBLSIZE + 1];
45  int cpdBmask[TBLSIZE];
46  int tblSizes[TBLSIZE];
47  HufNode hufTbl[2 * TBLSIZE - 1];
48 
49  byte bitFlg; // flag with the bits
50  byte bitCnt; // nb bits left
51 
52  static constexpr int cpdExt[TBLSIZE] = { // 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 
62 {
63  XSAExtractor extractor(file);
64  auto [d, sectors] = extractor.extractData();
65  data = std::move(d);
66  setNbSectors(sectors);
67 }
68 
69 void XSADiskImage::readSectorImpl(size_t sector, SectorBuffer& buf)
70 {
71  memcpy(&buf, &data[sector], sizeof(buf));
72 }
73 
74 void XSADiskImage::writeSectorImpl(size_t /*sector*/, const SectorBuffer& /*buf*/)
75 {
76  throw WriteProtectedException("Write protected");
77 }
78 
79 bool 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 
103 std::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
110 byte 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
119 void XSAExtractor::chkHeader()
120 {
121  // read original length (little endian)
122  unsigned outBufLen = 0;
123  for (int i = 0; i < 4; ++i) {
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
137 void XSAExtractor::unLz77()
138 {
139  bitCnt = 0; // no bits read yet
140 
141  size_t remaining = sectors * sizeof(SectorBuffer);
142  byte* 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 == (MAXSTRLEN + 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
178 unsigned XSAExtractor::rdStrLen()
179 {
180  if (!bitIn()) return 2;
181  if (!bitIn()) return 3;
182  if (!bitIn()) return 4;
183 
184  byte 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
197 int XSAExtractor::rdStrPos()
198 {
199  HufNode* hufPos = &hufTbl[2 * TBLSIZE - 2];
200 
201  while (hufPos->child1) {
202  if (bitIn()) {
203  hufPos = hufPos->child2;
204  } else {
205  hufPos = hufPos->child1;
206  }
207  }
208  byte cpdIndex = byte(hufPos - hufTbl);
209  ++tblSizes[cpdIndex];
210 
211  int strPos = [&] {
212  if (cpdBmask[cpdIndex] >= 256) {
213  byte strPosLsb = charIn();
214  byte strPosMsb = 0;
215  for (byte nrBits = cpdExt[cpdIndex] - 8; nrBits--;
216  strPosMsb |= (bitIn() ? 1 : 0)) {
217  strPosMsb <<= 1;
218  }
219  return strPosLsb + 256 * strPosMsb;
220  } else {
221  int pos = 0;
222  for (byte nrBits = cpdExt[cpdIndex]; nrBits--;
223  pos |= (bitIn() ? 1 : 0)) {
224  pos <<= 1;
225  }
226  return pos;
227  }
228  }();
229  if ((updHufCnt--) == 0) {
230  mkHufTbl(); // make the huffman table
231  }
232  return strPos + cpDist[cpdIndex];
233 }
234 
235 // read a bit from the input file
236 bool XSAExtractor::bitIn()
237 {
238  if (bitCnt == 0) {
239  bitFlg = charIn(); // read bitFlg
240  bitCnt = 8; // 8 bits left
241  }
242  bool temp = bitFlg & 1;
243  --bitCnt; // 1 bit less
244  bitFlg >>= 1;
245 
246  return temp;
247 }
248 
249 // initialize the huffman info tables
250 void XSAExtractor::initHufInfo()
251 {
252  int offs = 1;
253  for (int i = 0; i != TBLSIZE; ++i) {
254  cpDist[i] = offs;
255  cpdBmask[i] = 1 << cpdExt[i];
256  offs += cpdBmask[i];
257  }
258  cpDist[TBLSIZE] = offs;
259 
260  for (int i = 0; i != TBLSIZE; ++i) {
261  tblSizes[i] = 0; // reset the table counters
262  hufTbl[i].child1 = nullptr; // mark the leave nodes
263  }
264  mkHufTbl(); // make the huffman table
265 }
266 
267 // Make huffman coding info
268 void XSAExtractor::mkHufTbl()
269 {
270  // Initialize the huffman tree
271  HufNode* hufPos = hufTbl;
272  for (int i = 0; i != TBLSIZE; ++i) {
273  (hufPos++)->weight = 1 + (tblSizes[i] >>= 1);
274  }
275  for (int i = TBLSIZE; i != 2 * TBLSIZE - 1; ++i) {
276  (hufPos++)->weight = -1;
277  }
278  // Place the nodes in the correct manner in the tree
279  while (hufTbl[2 * TBLSIZE - 2].weight == -1) {
280  for (hufPos = hufTbl; !(hufPos->weight); ++hufPos) {
281  // nothing
282  }
283  HufNode* l1Pos = hufPos++;
284  while (!(hufPos->weight)) {
285  ++hufPos;
286  }
287  HufNode* l2Pos = [&] {
288  if (hufPos->weight < l1Pos->weight) {
289  auto* tmp = l1Pos;
290  l1Pos = hufPos++;
291  return tmp;
292  } else {
293  return hufPos++;
294  }
295  }();
296  int tempW;
297  while ((tempW = hufPos->weight) != -1) {
298  if (tempW) {
299  if (tempW < l1Pos->weight) {
300  l2Pos = l1Pos;
301  l1Pos = hufPos;
302  } else if (tempW < l2Pos->weight) {
303  l2Pos = hufPos;
304  }
305  }
306  ++hufPos;
307  }
308  hufPos->weight = l1Pos->weight + l2Pos->weight;
309  (hufPos->child1 = l1Pos)->weight = 0;
310  (hufPos->child2 = l2Pos)->weight = 0;
311  }
312  updHufCnt = MAXHUFCNT;
313 }
314 
315 } // namespace openmsx
openmsx::File::mmap
span< uint8_t > mmap()
Map file in memory.
Definition: File.cc:93
openmsx::SectorBuffer
Definition: DiskImageUtils.hh:90
DiskExceptions.hh
openmsx::XSADiskImage::XSADiskImage
XSADiskImage(Filename &filename, File &file)
Definition: XSADiskImage.cc:60
openmsx::byte
uint8_t byte
8 bit unsigned integer
Definition: openmsx.hh:26
openmsx::MSXException
Definition: MSXException.hh:10
File.hh
openmsx::MemBuffer
This class manages the lifetime of a block of memory.
Definition: MemBuffer.hh:29
openmsx::filename
constexpr const char *const filename
Definition: FirmwareSwitch.cc:10
openmsx::SectorBasedDisk::setNbSectors
void setNbSectors(size_t num)
Definition: SectorBasedDisk.cc:147
openmsx::XSAExtractor::extractData
std::pair< MemBuffer< SectorBuffer >, unsigned > extractData()
Definition: XSADiskImage.cc:103
XSADiskImage.hh
openmsx::XSAExtractor
Definition: XSADiskImage.cc:12
openmsx::File
Definition: File.hh:16
openmsx::SectorBasedDisk
Abstract class for disk images that only represent the logical sector information (so not the raw tra...
Definition: SectorBasedDisk.hh:14
openmsx::XSAExtractor::XSAExtractor
XSAExtractor(File &file)
Definition: XSADiskImage.cc:87
openmsx::Filename
This class represents a filename.
Definition: Filename.hh:18
openmsx
This file implemented 3 utility functions:
Definition: Autofire.cc:5