1 /*
2 Copyright (c) 1997 Simon Tatham
3
4 Permission is hereby granted, free of charge, to any person obtaining a copy of
5 this software and associated documentation files (the "Software"), to deal in
6 the Software without restriction, including without limitation the rights to
7 use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
8 of the Software, and to permit persons to whom the Software is furnished to do
9 so, subject to the following conditions:
10
11 The above copyright notice and this permission notice shall be included in all
12 copies or substantial portions of the Software.
13
14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
20 SOFTWARE.
21
22 Original code was from http://www.yoda.arachsys.com/dk/utils.html. While
23 that site and the original code do not state copyright or license, email
24 communication releaved the original author, and they agreed to releasing it
25 under the MIT license (above).
26
27 Modifications made to the original code include:
28 * Const correctness
29 * Prebuilt CRC table
30 * Lua interface
31 * Indentation and code style
32 * Bit stream pointers to data
33 * Fix bit operations near end of stream
34 * Style changes to conform to CorsixTH
35 */
36
37 #include "rnc.h"
38
39 #include <cstddef>
40 #include <cstdint>
41 #include <vector>
42
43 static const std::uint32_t rnc_signature = 0x524E4301; /*!< "RNC\001" */
44
45 // clang-format off
46 static const std::uint16_t rnc_crc_table[256] = {
47 0x0000, 0xC0C1, 0xC181, 0x0140, 0xC301, 0x03C0, 0x0280, 0xC241,
48 0xC601, 0x06C0, 0x0780, 0xC741, 0x0500, 0xC5C1, 0xC481, 0x0440,
49 0xCC01, 0x0CC0, 0x0D80, 0xCD41, 0x0F00, 0xCFC1, 0xCE81, 0x0E40,
50 0x0A00, 0xCAC1, 0xCB81, 0x0B40, 0xC901, 0x09C0, 0x0880, 0xC841,
51 0xD801, 0x18C0, 0x1980, 0xD941, 0x1B00, 0xDBC1, 0xDA81, 0x1A40,
52 0x1E00, 0xDEC1, 0xDF81, 0x1F40, 0xDD01, 0x1DC0, 0x1C80, 0xDC41,
53 0x1400, 0xD4C1, 0xD581, 0x1540, 0xD701, 0x17C0, 0x1680, 0xD641,
54 0xD201, 0x12C0, 0x1380, 0xD341, 0x1100, 0xD1C1, 0xD081, 0x1040,
55 0xF001, 0x30C0, 0x3180, 0xF141, 0x3300, 0xF3C1, 0xF281, 0x3240,
56 0x3600, 0xF6C1, 0xF781, 0x3740, 0xF501, 0x35C0, 0x3480, 0xF441,
57 0x3C00, 0xFCC1, 0xFD81, 0x3D40, 0xFF01, 0x3FC0, 0x3E80, 0xFE41,
58 0xFA01, 0x3AC0, 0x3B80, 0xFB41, 0x3900, 0xF9C1, 0xF881, 0x3840,
59 0x2800, 0xE8C1, 0xE981, 0x2940, 0xEB01, 0x2BC0, 0x2A80, 0xEA41,
60 0xEE01, 0x2EC0, 0x2F80, 0xEF41, 0x2D00, 0xEDC1, 0xEC81, 0x2C40,
61 0xE401, 0x24C0, 0x2580, 0xE541, 0x2700, 0xE7C1, 0xE681, 0x2640,
62 0x2200, 0xE2C1, 0xE381, 0x2340, 0xE101, 0x21C0, 0x2080, 0xE041,
63 0xA001, 0x60C0, 0x6180, 0xA141, 0x6300, 0xA3C1, 0xA281, 0x6240,
64 0x6600, 0xA6C1, 0xA781, 0x6740, 0xA501, 0x65C0, 0x6480, 0xA441,
65 0x6C00, 0xACC1, 0xAD81, 0x6D40, 0xAF01, 0x6FC0, 0x6E80, 0xAE41,
66 0xAA01, 0x6AC0, 0x6B80, 0xAB41, 0x6900, 0xA9C1, 0xA881, 0x6840,
67 0x7800, 0xB8C1, 0xB981, 0x7940, 0xBB01, 0x7BC0, 0x7A80, 0xBA41,
68 0xBE01, 0x7EC0, 0x7F80, 0xBF41, 0x7D00, 0xBDC1, 0xBC81, 0x7C40,
69 0xB401, 0x74C0, 0x7580, 0xB541, 0x7700, 0xB7C1, 0xB681, 0x7640,
70 0x7200, 0xB2C1, 0xB381, 0x7340, 0xB101, 0x71C0, 0x7080, 0xB041,
71 0x5000, 0x90C1, 0x9181, 0x5140, 0x9301, 0x53C0, 0x5280, 0x9241,
72 0x9601, 0x56C0, 0x5780, 0x9741, 0x5500, 0x95C1, 0x9481, 0x5440,
73 0x9C01, 0x5CC0, 0x5D80, 0x9D41, 0x5F00, 0x9FC1, 0x9E81, 0x5E40,
74 0x5A00, 0x9AC1, 0x9B81, 0x5B40, 0x9901, 0x59C0, 0x5880, 0x9841,
75 0x8801, 0x48C0, 0x4980, 0x8941, 0x4B00, 0x8BC1, 0x8A81, 0x4A40,
76 0x4E00, 0x8EC1, 0x8F81, 0x4F40, 0x8D01, 0x4DC0, 0x4C80, 0x8C41,
77 0x4400, 0x84C1, 0x8581, 0x4540, 0x8701, 0x47C0, 0x4680, 0x8641,
78 0x8201, 0x42C0, 0x4380, 0x8341, 0x4100, 0x81C1, 0x8081, 0x4040,
79 };
80 // clang-format on
81
82 struct bit_stream {
83 std::uint32_t bitbuf; ///< holds between 16 and 32 bits.
84 int bitcount; ///< how many bits does bitbuf hold?
85 const std::uint8_t* endpos; ///< pointer past the readable data
86 const std::uint8_t* p; ///< pointer in data that stream is reading.
87 };
88
89 struct huf_table {
90 int num; ///< number of nodes in the tree.
91 struct {
92 std::uint32_t code;
93 int codelen;
94 int value;
95 } table[32];
96 };
97
98 //! Calculate a CRC, the RNC way.
99 /*!
100 @param data data for which to calculate the CRC
101 @param len length of the data in bytes
102 */
rnc_crc(const std::uint8_t * data,std::size_t len)103 static std::uint16_t rnc_crc(const std::uint8_t* data, std::size_t len) {
104 std::uint16_t val = 0;
105
106 while (len--) {
107 val = static_cast<std::uint16_t>(val ^ *data++);
108 val = static_cast<std::uint16_t>((val >> 8) ^ rnc_crc_table[val & 0xFF]);
109 }
110
111 return val;
112 }
113
114 //! Return the big-endian 32 bit word at p.
115 /*!
116 @param p Pointer to data containing the word
117 */
blong(const std::uint8_t * p)118 static std::uint32_t blong(const std::uint8_t* p) {
119 std::uint32_t n;
120 n = p[0];
121 n = (n << 8) + p[1];
122 n = (n << 8) + p[2];
123 n = (n << 8) + p[3];
124 return n;
125 }
126
127 //! Return the big-endian 16 bit word at p.
128 /*!
129 @param p Pointer to data containing the word
130 */
bword(const std::uint8_t * p)131 static std::uint32_t bword(const std::uint8_t* p) {
132 std::uint32_t n;
133 n = p[0];
134 n = (n << 8) + p[1];
135 return n;
136 }
137
138 //! Return the little-endian 16 bit word at p.
139 /*!
140 @param p Pointer to data containing the word
141 */
lword(const std::uint8_t * p)142 static std::uint32_t lword(const std::uint8_t* p) {
143 std::uint32_t n;
144 n = p[1];
145 n = (n << 8) + p[0];
146 return n;
147 }
148
149 //! Mirror the bottom n bits of x.
150 /*!
151 @param x
152 @param n
153 */
mirror(std::uint32_t x,int n)154 static std::uint32_t mirror(std::uint32_t x, int n) {
155 std::uint32_t top = 1 << (n - 1), bottom = 1;
156 while (top > bottom) {
157 std::uint32_t mask = top | bottom;
158 std::uint32_t masked = x & mask;
159 if (masked != 0 && masked != mask) {
160 x ^= mask;
161 }
162 top >>= 1;
163 bottom <<= 1;
164 }
165 return x;
166 }
167
168 //! Initialises a bit stream with the first two bytes of the packed
169 //! data.
170 /*!
171 @param bs Bit stream to be initialized
172 @param p Pointer to start of memory block the bitstream is to
173 traverse
174 @param endpos Pointer to byte after the last memory block the bitstream is
175 to traverse
176 */
bitread_init(bit_stream * bs,const std::uint8_t * p,const std::uint8_t * endpos)177 static void bitread_init(bit_stream* bs, const std::uint8_t* p,
178 const std::uint8_t* endpos) {
179 bs->bitbuf = lword(p);
180 bs->bitcount = 16;
181 bs->p = p;
182 bs->endpos = endpos;
183 }
184
185 //! Fixes up a bit stream after literals have been read out of the
186 //! data stream and the pointer has been moved.
187 /*!
188 @param bs Bit stream to correct
189 */
bitread_fix(bit_stream * bs)190 static void bitread_fix(bit_stream* bs) {
191 // Remove the top 16 bits
192 bs->bitcount -= 16;
193 bs->bitbuf &= (1 << bs->bitcount) - 1;
194
195 // Replace with what is in the new current location
196 // in the bit stream
197 if (bs->p < bs->endpos - 1) {
198 bs->bitbuf |= (lword(bs->p) << bs->bitcount);
199 bs->bitcount += 16;
200 } else if (bs->p == bs->endpos - 1) {
201 bs->bitbuf |= (*(bs->p) << bs->bitcount);
202 bs->bitcount += 16;
203 }
204 }
205
206 //! Return a word consisting of the specified bits without advancing
207 //! the bit stream.
208 /*!
209 @param bs Bit stream from which to peek
210 @param mask A 32 bit bit mask specifying which bits to peek
211 */
bit_peek(bit_stream * bs,const std::uint32_t mask)212 static std::uint32_t bit_peek(bit_stream* bs, const std::uint32_t mask) {
213 return bs->bitbuf & mask;
214 }
215
216 //! Advances the bit stream.
217 /*!
218 @param bs Bit stream to advance
219 @param n Number of bits to advance the stream. Must be
220 between 0 and 16
221 */
bit_advance(bit_stream * bs,int n)222 static void bit_advance(bit_stream* bs, int n) {
223 bs->bitbuf >>= n;
224 bs->bitcount -= n;
225
226 if (bs->bitcount < 16) {
227 // At this point it is possible for bs->p to advance past
228 // the end of the data. In that case we simply do not read
229 // anything more into the buffer. If we are on the last
230 // byte the lword matches what is in that byte.
231 bs->p += 2;
232
233 if (bs->p < (bs->endpos - 1)) {
234 bs->bitbuf |= (lword(bs->p) << bs->bitcount);
235 bs->bitcount += 16;
236 } else if (bs->p < bs->endpos) {
237 bs->bitbuf |= (*(bs->p) << bs->bitcount);
238 bs->bitcount += 16;
239 }
240 }
241 }
242
243 //! Returns bits from the bit stream matching the mask and advances it
244 //! n places.
245 /*!
246 @param bs Bit stream to read
247 @param mask A 32 bit bit mask specifying which bits to read
248 @param n Number of bits to advance the stream. Must be
249 between 0 and 16
250 */
bit_read(bit_stream * bs,std::uint32_t mask,int n)251 static std::uint32_t bit_read(bit_stream* bs, std::uint32_t mask, int n) {
252 std::uint32_t result = bit_peek(bs, mask);
253 bit_advance(bs, n);
254 return result;
255 }
256
257 //! Read a Huffman table out of the bit stream given.
258 /*!
259 @param h huf_table structure to populate
260 @param bs Bit stream pointing to the start of the Huffman table
261 description
262 */
read_huftable(huf_table * h,bit_stream * bs)263 static void read_huftable(huf_table* h, bit_stream* bs) {
264 int i, j, k, num;
265 int leaflen[32];
266 int leafmax;
267 std::uint32_t codeb; /* big-endian form of code. */
268
269 num = bit_read(bs, 0x1F, 5);
270
271 if (num == 0) {
272 return;
273 }
274
275 leafmax = 1;
276 for (i = 0; i < num; i++) {
277 leaflen[i] = bit_read(bs, 0x0F, 4);
278 if (leafmax < leaflen[i]) {
279 leafmax = leaflen[i];
280 }
281 }
282
283 codeb = 0L;
284 k = 0;
285 for (i = 1; i <= leafmax; i++) {
286 for (j = 0; j < num; j++) {
287 if (leaflen[j] == i) {
288 h->table[k].code = mirror(codeb, i);
289 h->table[k].codelen = i;
290 h->table[k].value = j;
291 codeb++;
292 k++;
293 }
294 }
295 codeb <<= 1;
296 }
297 h->num = k;
298 }
299
300 //! Read a value out of the bit stream using the given Huffman table.
301 /*!
302 @param h Huffman table to transcribe from
303 @param bs bit stream
304 @param p input data
305 @return The value from the table with the matching bits, or -1 if none
306 found.
307 */
huf_read(huf_table * h,bit_stream * bs,const std::uint8_t ** p)308 static std::uint32_t huf_read(huf_table* h, bit_stream* bs,
309 const std::uint8_t** p) {
310 int i;
311 std::uint32_t val;
312 std::uint32_t mask;
313
314 // Find the current bits in the table
315 for (i = 0; i < h->num; i++) {
316 mask = (1 << h->table[i].codelen) - 1;
317 if (bit_peek(bs, mask) == h->table[i].code) {
318 break;
319 }
320 }
321
322 // No match found in table (error)
323 if (i == h->num) {
324 return -1;
325 }
326
327 bit_advance(bs, h->table[i].codelen);
328
329 val = h->table[i].value;
330 if (val >= 2) {
331 val = 1 << (val - 1);
332 val |= bit_read(bs, val - 1, h->table[i].value - 1);
333 }
334 return val;
335 }
336
rnc_output_size(const std::uint8_t * input)337 std::size_t rnc_output_size(const std::uint8_t* input) {
338 return static_cast<std::size_t>(blong(input + 4));
339 }
340
rnc_input_size(const std::uint8_t * input)341 std::size_t rnc_input_size(const std::uint8_t* input) {
342 return static_cast<std::size_t>(blong(input + 8) + rnc_header_size);
343 }
344
345 //! Decompresses RNC data
346 /*!
347 @param input Pointer to compressed RNC data
348 @param output Pointer to allocated memory region to hold uncompressed
349 data. The size of output must match the value specified in the
350 4 byte segment of the input header starting at the 4th byte
351 in Big-endian.
352 */
rnc_unpack(const std::uint8_t * input,std::uint8_t * output)353 rnc_status rnc_unpack(const std::uint8_t* input, std::uint8_t* output) {
354 const std::uint8_t* inputend;
355 std::uint8_t* outputend;
356 bit_stream input_bs;
357 huf_table raw = {0}, dist = {0}, len = {0};
358 std::uint32_t ch_count;
359 std::uint32_t ret_len;
360 std::uint32_t out_crc;
361 if (blong(input) != rnc_signature) {
362 return rnc_status::file_is_not_rnc;
363 }
364 ret_len = blong(input + 4);
365 outputend = output + ret_len;
366 inputend = input + 18 + blong(input + 8);
367
368 // skip header
369 input += 18;
370
371 // Check the packed-data CRC. Also save the unpacked-data CRC
372 // for later.
373 if (rnc_crc(input, inputend - input) != bword(input - 4)) {
374 return rnc_status::packed_crc_error;
375 }
376 out_crc = bword(input - 6);
377
378 // initialize the bitstream to the input and advance past the
379 // first two bits as they don't have any understood use.
380 bitread_init(&input_bs, input, inputend);
381 bit_advance(&input_bs, 2);
382
383 // process chunks
384 while (output < outputend) {
385 read_huftable(&raw, &input_bs); // raw byte length table
386 read_huftable(&dist, &input_bs); // distance prior to copy table
387 read_huftable(&len, &input_bs); // length bytes to copy table
388 ch_count = bit_read(&input_bs, 0xFFFF, 16);
389
390 while (true) {
391 long length, posn;
392
393 // Copy bit pattern to output based on lookup
394 // of bytes from input.
395 length = huf_read(&raw, &input_bs, &input);
396 if (length == -1) {
397 return rnc_status::huf_decode_error;
398 }
399 if (length) {
400 while (length--) {
401 *output++ = *(input_bs.p++);
402 }
403 bitread_fix(&input_bs);
404 }
405 if (--ch_count <= 0) {
406 break;
407 }
408
409 // Read position to copy output to
410 posn = huf_read(&dist, &input_bs, &input);
411 if (posn == -1) {
412 return rnc_status::huf_decode_error;
413 }
414 posn += 1;
415
416 // Read length of output to copy back
417 length = huf_read(&len, &input_bs, &input);
418 if (length == -1) {
419 return rnc_status::huf_decode_error;
420 }
421 length += 2;
422
423 // Copy length bytes from output back posn
424 while (length > 0) {
425 length--;
426 *output = output[-posn];
427 output++;
428 }
429 }
430 }
431
432 if (outputend != output) {
433 return rnc_status::file_size_mismatch;
434 }
435
436 // Check the unpacked-data CRC.
437 if (rnc_crc(outputend - ret_len, ret_len) != out_crc) {
438 return rnc_status::unpacked_crc_error;
439 }
440
441 return rnc_status::ok;
442 }
443