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