1/*****************************************************************************\
2 Snes9x - Portable Super Nintendo Entertainment System (TM) emulator.
3 This file is licensed under the Snes9x License.
4 For further information, consult the LICENSE file in the root directory.
5\*****************************************************************************/
6
7/* S-DD1 decompressor
8 *
9 * Based on code and documentation by Andreas Naive, who deserves a great deal
10 * of thanks and credit for figuring this out.
11 *
12 * Andreas says:
13 * The author is greatly indebted with The Dumper, without whose help and
14 * patience providing him with real S-DD1 data the research had never been
15 * possible. He also wish to note that in the very beggining of his research,
16 * Neviksti had done some steps in the right direction. By last, the author is
17 * indirectly indebted to all the people that worked and contributed in the
18 * S-DD1 issue in the past.
19 */
20
21
22#include "port.h"
23#include "sdd1emu.h"
24
25static int valid_bits;
26static uint16 in_stream;
27static uint8 *in_buf;
28static uint8 bit_ctr[8];
29static uint8 context_states[32];
30static int context_MPS[32];
31static int bitplane_type;
32static int high_context_bits;
33static int low_context_bits;
34static int prev_bits[8];
35
36static struct {
37 uint8 code_size;
38 uint8 MPS_next;
39 uint8 LPS_next;
40} evolution_table[] = {
41 /* 0 */ { 0,25,25},
42 /* 1 */ { 0, 2, 1},
43 /* 2 */ { 0, 3, 1},
44 /* 3 */ { 0, 4, 2},
45 /* 4 */ { 0, 5, 3},
46 /* 5 */ { 1, 6, 4},
47 /* 6 */ { 1, 7, 5},
48 /* 7 */ { 1, 8, 6},
49 /* 8 */ { 1, 9, 7},
50 /* 9 */ { 2,10, 8},
51 /* 10 */ { 2,11, 9},
52 /* 11 */ { 2,12,10},
53 /* 12 */ { 2,13,11},
54 /* 13 */ { 3,14,12},
55 /* 14 */ { 3,15,13},
56 /* 15 */ { 3,16,14},
57 /* 16 */ { 3,17,15},
58 /* 17 */ { 4,18,16},
59 /* 18 */ { 4,19,17},
60 /* 19 */ { 5,20,18},
61 /* 20 */ { 5,21,19},
62 /* 21 */ { 6,22,20},
63 /* 22 */ { 6,23,21},
64 /* 23 */ { 7,24,22},
65 /* 24 */ { 7,24,23},
66 /* 25 */ { 0,26, 1},
67 /* 26 */ { 1,27, 2},
68 /* 27 */ { 2,28, 4},
69 /* 28 */ { 3,29, 8},
70 /* 29 */ { 4,30,12},
71 /* 30 */ { 5,31,16},
72 /* 31 */ { 6,32,18},
73 /* 32 */ { 7,24,22}
74};
75
76static uint8 run_table[128] = {
77 128, 64, 96, 32, 112, 48, 80, 16, 120, 56, 88, 24, 104, 40, 72,
78 8, 124, 60, 92, 28, 108, 44, 76, 12, 116, 52, 84, 20, 100, 36,
79 68, 4, 126, 62, 94, 30, 110, 46, 78, 14, 118, 54, 86, 22, 102,
80 38, 70, 6, 122, 58, 90, 26, 106, 42, 74, 10, 114, 50, 82, 18,
81 98, 34, 66, 2, 127, 63, 95, 31, 111, 47, 79, 15, 119, 55, 87,
82 23, 103, 39, 71, 7, 123, 59, 91, 27, 107, 43, 75, 11, 115, 51,
83 83, 19, 99, 35, 67, 3, 125, 61, 93, 29, 109, 45, 77, 13, 117,
84 53, 85, 21, 101, 37, 69, 5, 121, 57, 89, 25, 105, 41, 73, 9,
85 113, 49, 81, 17, 97, 33, 65, 1
86};
87
88static inline uint8 GetCodeword(int bits){
89 uint8 tmp;
90
91 if(!valid_bits){
92 in_stream|=*(in_buf++);
93 valid_bits=8;
94 }
95 in_stream<<=1;
96 valid_bits--;
97 in_stream^=0x8000;
98 if(in_stream&0x8000) return 0x80+(1<<bits);
99 tmp=(in_stream>>8) | (0x7f>>bits);
100 in_stream<<=bits;
101 valid_bits-=bits;
102 if(valid_bits<0){
103 in_stream |= (*(in_buf++))<<(-valid_bits);
104 valid_bits+=8;
105 }
106 return run_table[tmp];
107}
108
109static inline uint8 GolombGetBit(int code_size){
110 if(!bit_ctr[code_size]) bit_ctr[code_size]=GetCodeword(code_size);
111 bit_ctr[code_size]--;
112 if(bit_ctr[code_size]==0x80){
113 bit_ctr[code_size]=0;
114 return 2; /* secret code for 'last zero'. ones are always last. */
115 }
116 return (bit_ctr[code_size]==0)?1:0;
117}
118
119static inline uint8 ProbGetBit(uint8 context){
120 uint8 state=context_states[context];
121 uint8 bit=GolombGetBit(evolution_table[state].code_size);
122
123 if(bit&1){
124 context_states[context]=evolution_table[state].LPS_next;
125 if(state<2){
126 context_MPS[context]^=1;
127 return context_MPS[context]; /* just inverted, so just return it */
128 } else{
129 return context_MPS[context]^1; /* we know bit is 1, so use a constant */
130 }
131 } else if(bit){
132 context_states[context]=evolution_table[state].MPS_next;
133 /* zero here, zero there, no difference so drop through. */
134 }
135 return context_MPS[context]; /* we know bit is 0, so don't bother xoring */
136}
137
138static inline uint8 GetBit(uint8 cur_bitplane){
139 uint8 bit;
140
141 bit=ProbGetBit(((cur_bitplane&1)<<4)
142 | ((prev_bits[cur_bitplane]&high_context_bits)>>5)
143 | (prev_bits[cur_bitplane]&low_context_bits));
144
145 prev_bits[cur_bitplane] <<= 1;
146 prev_bits[cur_bitplane] |= bit;
147 return bit;
148}
149
150void SDD1_decompress(uint8 *out, uint8 *in, int len){
151 uint8 bit, i, plane;
152 uint8 byte1, byte2;
153
154 if(len==0) len=0x10000;
155
156 bitplane_type=in[0]>>6;
157
158 switch(in[0]&0x30){
159 case 0x00:
160 high_context_bits=0x01c0;
161 low_context_bits =0x0001;
162 break;
163 case 0x10:
164 high_context_bits=0x0180;
165 low_context_bits =0x0001;
166 break;
167 case 0x20:
168 high_context_bits=0x00c0;
169 low_context_bits =0x0001;
170 break;
171 case 0x30:
172 high_context_bits=0x0180;
173 low_context_bits =0x0003;
174 break;
175 }
176
177 in_stream=(in[0]<<11) | (in[1]<<3);
178 valid_bits=5;
179 in_buf=in+2;
180 memset(bit_ctr, 0, sizeof(bit_ctr));
181 memset(context_states, 0, sizeof(context_states));
182 memset(context_MPS, 0, sizeof(context_MPS));
183 memset(prev_bits, 0, sizeof(prev_bits));
184
185 switch(bitplane_type){
186 case 0:
187 while(1) {
188 for(byte1=byte2=0, bit=0x80; bit; bit>>=1){
189 if(GetBit(0)) byte1 |= bit;
190 if(GetBit(1)) byte2 |= bit;
191 }
192 *(out++)=byte1;
193 if(!--len) return;
194 *(out++)=byte2;
195 if(!--len) return;
196 }
197 break;
198 case 1:
199 i=plane=0;
200 while(1) {
201 for(byte1=byte2=0, bit=0x80; bit; bit>>=1){
202 if(GetBit(plane)) byte1 |= bit;
203 if(GetBit(plane+1)) byte2 |= bit;
204 }
205 *(out++)=byte1;
206 if(!--len) return;
207 *(out++)=byte2;
208 if(!--len) return;
209 if(!(i+=32)) plane = (plane+2)&7;
210 }
211 break;
212 case 2:
213 i=plane=0;
214 while(1) {
215 for(byte1=byte2=0, bit=0x80; bit; bit>>=1){
216 if(GetBit(plane)) byte1 |= bit;
217 if(GetBit(plane+1)) byte2 |= bit;
218 }
219 *(out++)=byte1;
220 if(!--len) return;
221 *(out++)=byte2;
222 if(!--len) return;
223 if(!(i+=32)) plane ^= 2;
224 }
225 break;
226 case 3:
227 do {
228 for(byte1=plane=0, bit=1; bit; bit<<=1, plane++){
229 if(GetBit(plane)) byte1 |= bit;
230 }
231 *(out++)=byte1;
232 } while(--len);
233 break;
234 }
235}
236
237#if 0
238static uint8 cur_plane;
239static uint8 num_bits;
240static uint8 next_byte;
241
242void SDD1_init(uint8 *in){
243 bitplane_type=in[0]>>6;
244
245 switch(in[0]&0x30){
246 case 0x00:
247 high_context_bits=0x01c0;
248 low_context_bits =0x0001;
249 break;
250 case 0x10:
251 high_context_bits=0x0180;
252 low_context_bits =0x0001;
253 break;
254 case 0x20:
255 high_context_bits=0x00c0;
256 low_context_bits =0x0001;
257 break;
258 case 0x30:
259 high_context_bits=0x0180;
260 low_context_bits =0x0003;
261 break;
262 }
263
264 in_stream=(in[0]<<11) | (in[1]<<3);
265 valid_bits=5;
266 in_buf=in+2;
267 memset(bit_ctr, 0, sizeof(bit_ctr));
268 memset(context_states, 0, sizeof(context_states));
269 memset(context_MPS, 0, sizeof(context_MPS));
270 memset(prev_bits, 0, sizeof(prev_bits));
271
272 cur_plane=0;
273 num_bits=0;
274}
275
276uint8 SDD1_get_byte(void){
277 uint8 bit;
278 uint8 byte=0;
279
280 switch(bitplane_type){
281 case 0:
282 num_bits+=16;
283 if(num_bits&16){
284 next_byte=0;
285 for(bit=0x80; bit; bit>>=1){
286 if(GetBit(0)) byte |= bit;
287 if(GetBit(1)) next_byte |= bit;
288 }
289 return byte;
290 } else {
291 return next_byte;
292 }
293
294 case 1:
295 num_bits+=16;
296 if(num_bits&16){
297 next_byte=0;
298 for(bit=0x80; bit; bit>>=1){
299 if(GetBit(cur_plane)) byte |= bit;
300 if(GetBit(cur_plane+1)) next_byte |= bit;
301 }
302 return byte;
303 } else {
304 if(!num_bits) cur_plane = (cur_plane+2)&7;
305 return next_byte;
306 }
307
308 case 2:
309 num_bits+=16;
310 if(num_bits&16){
311 next_byte=0;
312 for(bit=0x80; bit; bit>>=1){
313 if(GetBit(cur_plane)) byte |= bit;
314 if(GetBit(cur_plane+1)) next_byte |= bit;
315 }
316 return byte;
317 } else {
318 if(!num_bits) cur_plane ^= 2;
319 return next_byte;
320 }
321
322 case 3:
323 for(cur_plane=0, bit=1; bit; bit<<=1, cur_plane++){
324 if(GetBit(cur_plane)) byte |= bit;
325 }
326 return byte;
327
328 default:
329 /* should never happen */
330 return 0;
331 }
332}
333#endif
334