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 | |
25 | static int valid_bits; |
26 | static uint16 in_stream; |
27 | static uint8 *in_buf; |
28 | static uint8 bit_ctr[8]; |
29 | static uint8 context_states[32]; |
30 | static int context_MPS[32]; |
31 | static int bitplane_type; |
32 | static int high_context_bits; |
33 | static int low_context_bits; |
34 | static int prev_bits[8]; |
35 | |
36 | static 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 | |
76 | static 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 | |
88 | static 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 | |
109 | static 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 | |
119 | static 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 | |
138 | static 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 | |
150 | void 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 |
238 | static uint8 cur_plane; |
239 | static uint8 num_bits; |
240 | static uint8 next_byte; |
241 | |
242 | void 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 | |
276 | uint8 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 | |