1 /* ScummVM - Graphic Adventure Engine
2 *
3 * ScummVM is the legal property of its developers, whose names
4 * are too numerous to list here. Please refer to the COPYRIGHT
5 * file distributed with this source distribution.
6 *
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License
9 * as published by the Free Software Foundation; either version 2
10 * of the License, or (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
20 *
21 */
22
23
24 #include "common/endian.h"
25 #include "sky/rnc_deco.h"
26
27 namespace Sky {
28
29 //return codes
30 #define NOT_PACKED 0
31 #define PACKED_CRC -1
32 #define UNPACKED_CRC -2
33
34 //other defines
35 #define TABLE_SIZE (16 * 8)
36 #define MIN_LENGTH 2
37 #define HEADER_LEN 18
38
RncDecoder()39 RncDecoder::RncDecoder() {
40 initCrc();
41 }
42
~RncDecoder()43 RncDecoder::~RncDecoder() { }
44
initCrc()45 void RncDecoder::initCrc() {
46 uint16 cnt = 0;
47 uint16 tmp1 = 0;
48 uint16 tmp2 = 0;
49
50 for (tmp2 = 0; tmp2 < 0x100; tmp2++) {
51 tmp1 = tmp2;
52 for (cnt = 8; cnt > 0; cnt--) {
53 if (tmp1 % 2) {
54 tmp1 >>= 1;
55 tmp1 ^= 0x0a001;
56 } else
57 tmp1 >>= 1;
58 }
59 _crcTable[tmp2] = tmp1;
60 }
61 }
62
63 //calculate 16 bit crc of a block of memory
crcBlock(const uint8 * block,uint32 size)64 uint16 RncDecoder::crcBlock(const uint8 *block, uint32 size) {
65 uint16 crc = 0;
66 uint8 *crcTable8 = (uint8 *)_crcTable; //make a uint8* to crc_table
67 uint8 tmp;
68 uint32 i;
69
70 for (i = 0; i < size; i++) {
71 tmp = *block++;
72 crc ^= tmp;
73 tmp = (uint8)((crc >> 8) & 0x00FF);
74 crc &= 0x00FF;
75 crc = *(uint16 *)&crcTable8[crc << 1];
76 crc ^= tmp;
77 }
78
79 return crc;
80 }
81
inputBits(uint8 amount)82 uint16 RncDecoder::inputBits(uint8 amount) {
83 uint16 newBitBuffh = _bitBuffh;
84 uint16 newBitBuffl = _bitBuffl;
85 int16 newBitCount = _bitCount;
86 uint16 remBits, returnVal;
87
88 returnVal = ((1 << amount) - 1) & newBitBuffl;
89 newBitCount -= amount;
90
91 if (newBitCount < 0) {
92 newBitCount += amount;
93 remBits = (newBitBuffh << (16 - newBitCount));
94 newBitBuffh >>= newBitCount;
95 newBitBuffl >>= newBitCount;
96 newBitBuffl |= remBits;
97 _srcPtr += 2;
98 newBitBuffh = READ_LE_UINT16(_srcPtr);
99 amount -= newBitCount;
100 newBitCount = 16 - amount;
101 }
102 remBits = (newBitBuffh << (16 - amount));
103 _bitBuffh = newBitBuffh >> amount;
104 _bitBuffl = (newBitBuffl >> amount) | remBits;
105 _bitCount = (uint8)newBitCount;
106
107 return returnVal;
108 }
109
makeHufftable(uint16 * table)110 void RncDecoder::makeHufftable(uint16 *table) {
111 uint16 bitLength, i, j;
112 uint16 numCodes = inputBits(5);
113
114 if (!numCodes)
115 return;
116
117 uint8 huffLength[16];
118 for (i = 0; i < numCodes; i++)
119 huffLength[i] = (uint8)(inputBits(4) & 0x00FF);
120
121 uint16 huffCode = 0;
122
123 for (bitLength = 1; bitLength < 17; bitLength++) {
124 for (i = 0; i < numCodes; i++) {
125 if (huffLength[i] == bitLength) {
126 *table++ = (1 << bitLength) - 1;
127
128 uint16 b = huffCode >> (16 - bitLength);
129 uint16 a = 0;
130
131 for (j = 0; j < bitLength; j++)
132 a |= ((b >> j) & 1) << (bitLength - j - 1);
133 *table++ = a;
134
135 *(table + 0x1e) = (huffLength[i] << 8) | (i & 0x00FF);
136 huffCode += 1 << (16 - bitLength);
137 }
138 }
139 }
140 }
141
inputValue(uint16 * table)142 uint16 RncDecoder::inputValue(uint16 *table) {
143 uint16 valOne, valTwo, value = _bitBuffl;
144
145 do {
146 valTwo = (*table++) & value;
147 valOne = *table++;
148
149 } while (valOne != valTwo);
150
151 value = *(table + 0x1e);
152 inputBits((uint8)((value>>8) & 0x00FF));
153 value &= 0x00FF;
154
155 if (value >= 2) {
156 value--;
157 valOne = inputBits((uint8)value & 0x00FF);
158 valOne |= (1 << value);
159 value = valOne;
160 }
161
162 return value;
163 }
164
unpackM1(const void * input,void * output,uint16 key)165 int32 RncDecoder::unpackM1(const void *input, void *output, uint16 key) {
166 uint8 *outputLow, *outputHigh;
167 const uint8 *inputHigh, *inputptr = (const uint8 *)input;
168
169 uint32 unpackLen = 0;
170 uint32 packLen = 0;
171 uint16 counts = 0;
172 uint16 crcUnpacked = 0;
173 uint16 crcPacked = 0;
174
175
176 _bitBuffl = 0;
177 _bitBuffh = 0;
178 _bitCount = 0;
179
180 //Check for "RNC "
181 if (READ_BE_UINT32(inputptr) != RNC_SIGNATURE)
182 return NOT_PACKED;
183
184 inputptr += 4;
185
186 // read unpacked/packed file length
187 unpackLen = READ_BE_UINT32(inputptr); inputptr += 4;
188 packLen = READ_BE_UINT32(inputptr); inputptr += 4;
189
190 uint8 blocks = *(inputptr + 5);
191
192 //read CRC's
193 crcUnpacked = READ_BE_UINT16(inputptr); inputptr += 2;
194 crcPacked = READ_BE_UINT16(inputptr); inputptr += 2;
195 inputptr = (inputptr + HEADER_LEN - 16);
196
197 if (crcBlock(inputptr, packLen) != crcPacked)
198 return PACKED_CRC;
199
200 inputptr = (((const uint8 *)input) + HEADER_LEN);
201 _srcPtr = inputptr;
202
203 inputHigh = ((const uint8 *)input) + packLen + HEADER_LEN;
204 outputLow = (uint8 *)output;
205 outputHigh = *(((const uint8 *)input) + 16) + unpackLen + outputLow;
206
207 if (! ((inputHigh <= outputLow) || (outputHigh <= inputHigh)) ) {
208 _srcPtr = inputHigh;
209 _dstPtr = outputHigh;
210 memcpy((_dstPtr-packLen), (_srcPtr-packLen), packLen);
211 _srcPtr = (_dstPtr-packLen);
212 }
213
214 _dstPtr = (uint8 *)output;
215 _bitCount = 0;
216
217 _bitBuffl = READ_LE_UINT16(_srcPtr);
218 inputBits(2);
219
220 do {
221 makeHufftable(_rawTable);
222 makeHufftable(_posTable);
223 makeHufftable(_lenTable);
224
225 counts = inputBits(16);
226
227 do {
228 uint32 inputLength = inputValue(_rawTable);
229 uint32 inputOffset;
230
231 if (inputLength) {
232 memcpy(_dstPtr, _srcPtr, inputLength); //memcpy is allowed here
233 _dstPtr += inputLength;
234 _srcPtr += inputLength;
235 uint16 a = READ_LE_UINT16(_srcPtr);
236 uint16 b = READ_LE_UINT16(_srcPtr + 2);
237
238 _bitBuffl &= ((1 << _bitCount) - 1);
239 _bitBuffl |= (a << _bitCount);
240 _bitBuffh = (a >> (16 - _bitCount)) | (b << _bitCount);
241 }
242
243 if (counts > 1) {
244 inputOffset = inputValue(_posTable) + 1;
245 inputLength = inputValue(_lenTable) + MIN_LENGTH;
246
247 // Don't use memcpy here! because input and output overlap.
248 uint8 *tmpPtr = (_dstPtr-inputOffset);
249 while (inputLength--)
250 *_dstPtr++ = *tmpPtr++;
251 }
252 } while (--counts);
253 } while (--blocks);
254
255 if (crcBlock((uint8 *)output, unpackLen) != crcUnpacked)
256 return UNPACKED_CRC;
257
258 // all is done..return the amount of unpacked bytes
259 return unpackLen;
260 }
261
262 } // End of namespace Sky
263