Mercurial > audlegacy-plugins
comparison src/vtx/lh5dec.c @ 749:26ff35aa9b2b trunk
[svn] - vtx input plugin based on a submission from Pavel Vymetalek.
author | nenolod |
---|---|
date | Wed, 28 Feb 2007 04:38:53 -0800 |
parents | |
children | 33ffac81f4c7 |
comparison
equal
deleted
inserted
replaced
748:559c68ce2e3d | 749:26ff35aa9b2b |
---|---|
1 /* extractiong lh5 module | |
2 (c) Haruhiko Okumura | |
3 (m) Roman Scherbakov | |
4 */ | |
5 #include <stdlib.h> | |
6 #include <stdio.h> | |
7 #include <string.h> /* memmove */ | |
8 #include <limits.h> | |
9 | |
10 static unsigned short bitbuf; | |
11 | |
12 #define BITBUFSIZ (CHAR_BIT * sizeof bitbuf) | |
13 | |
14 #define DICBIT 13 /* 12(-lh4-) or 13(-lh5-) */ | |
15 #define DICSIZ (1L << DICBIT) | |
16 #define MATCHBIT 8 /* bits for MAXMATCH - THRESHOLD */ | |
17 #define MAXMATCH 256 /* formerly F (not more than unsigned char_MAX + 1) */ | |
18 #define THRESHOLD 3 /* choose optimal value */ | |
19 #define NC (UCHAR_MAX + MAXMATCH + 2 - THRESHOLD) | |
20 #define CBIT 9 /* $\lfloor \log_2 NC \rfloor + 1$ */ | |
21 #define CODE_BIT 16 /* codeword length */ | |
22 #define NP (DICBIT + 1) | |
23 #define NT (CODE_BIT + 3) | |
24 #define PBIT 4 /* smallest integer such that (1U << PBIT) > NP */ | |
25 #define TBIT 5 /* smallest integer such that (1U << TBIT) > NT */ | |
26 #if NT > NP | |
27 #define NPT NT | |
28 #else | |
29 #define NPT NP | |
30 #endif | |
31 | |
32 static unsigned long origsize, compsize; | |
33 static unsigned char *in_buf; | |
34 static unsigned char *out_buf; | |
35 | |
36 static unsigned short subbitbuf; | |
37 static int bitcount; | |
38 | |
39 static unsigned short left[2 * NC - 1], right[2 * NC - 1]; | |
40 static unsigned char c_len[NC], pt_len[NPT]; | |
41 static unsigned short blocksize; | |
42 | |
43 static unsigned short c_table[4096], pt_table[256]; | |
44 | |
45 static int j; /* remaining bytes to copy */ | |
46 | |
47 | |
48 static void error(char *msg) | |
49 { | |
50 fprintf(stderr, "libayemu: lh5dec.c: %s\n", msg); | |
51 exit(EXIT_FAILURE); | |
52 } | |
53 | |
54 static void fillbuf(int n) /* Shift bitbuf n bits left, read n bits */ | |
55 { | |
56 bitbuf <<= n; | |
57 while (n > bitcount) { | |
58 bitbuf |= subbitbuf << (n -= bitcount); | |
59 if (compsize != 0) { | |
60 compsize--; subbitbuf = *in_buf++; | |
61 } else subbitbuf = 0; | |
62 bitcount = CHAR_BIT; | |
63 } | |
64 bitbuf |= subbitbuf >> (bitcount -= n); | |
65 } | |
66 | |
67 static unsigned short getbits(int n) | |
68 { | |
69 unsigned short x; | |
70 | |
71 x = bitbuf >> (BITBUFSIZ - n); fillbuf(n); | |
72 return x; | |
73 } | |
74 | |
75 // make table for decoding | |
76 | |
77 static void make_table(int nchar, unsigned char bitlen[], int tablebits, unsigned short table[]) | |
78 { | |
79 unsigned short count[17], weight[17], start[18], *p; | |
80 unsigned short i, k, len, ch, jutbits, avail, nextcode, mask; | |
81 | |
82 for (i = 1; i <= 16; i++) count[i] = 0; | |
83 for (i = 0; i < nchar; i++) count[bitlen[i]]++; | |
84 | |
85 start[1] = 0; | |
86 for (i = 1; i <= 16; i++) | |
87 start[i + 1] = start[i] + (count[i] << (16 - i)); | |
88 if (start[17] != (unsigned short)(1U << 16)) error("Bad table"); | |
89 | |
90 jutbits = 16 - tablebits; | |
91 for (i = 1; i <= tablebits; i++) { | |
92 start[i] >>= jutbits; | |
93 weight[i] = 1U << (tablebits - i); | |
94 } | |
95 while (i <= 16) weight[i++] = 1U << (16 - i); | |
96 | |
97 i = start[tablebits + 1] >> jutbits; | |
98 if (i != (unsigned short)(1U << 16)) { | |
99 k = 1U << tablebits; | |
100 while (i != k) table[i++] = 0; | |
101 } | |
102 | |
103 avail = nchar; | |
104 mask = 1U << (15 - tablebits); | |
105 for (ch = 0; ch < nchar; ch++) { | |
106 if ((len = bitlen[ch]) == 0) continue; | |
107 nextcode = start[len] + weight[len]; | |
108 if (len <= tablebits) { | |
109 for (i = start[len]; i < nextcode; i++) table[i] = ch; | |
110 } else { | |
111 k = start[len]; | |
112 p = &table[k >> jutbits]; | |
113 i = len - tablebits; | |
114 while (i != 0) { | |
115 if (*p == 0) { | |
116 right[avail] = left[avail] = 0; | |
117 *p = avail++; | |
118 } | |
119 if (k & mask) p = &right[*p]; | |
120 else p = &left[*p]; | |
121 k <<= 1; i--; | |
122 } | |
123 *p = ch; | |
124 } | |
125 start[len] = nextcode; | |
126 } | |
127 } | |
128 | |
129 // static Huffman | |
130 | |
131 static void read_pt_len(int nn, int nbit, int i_special) | |
132 { | |
133 int i, c, n; | |
134 unsigned short mask; | |
135 | |
136 n = getbits(nbit); | |
137 if (n == 0) { | |
138 c = getbits(nbit); | |
139 for (i = 0; i < nn; i++) pt_len[i] = 0; | |
140 for (i = 0; i < 256; i++) pt_table[i] = c; | |
141 } else { | |
142 i = 0; | |
143 while (i < n) { | |
144 c = bitbuf >> (BITBUFSIZ - 3); | |
145 if (c == 7) { | |
146 mask = 1U << (BITBUFSIZ - 1 - 3); | |
147 while (mask & bitbuf) { mask >>= 1; c++; } | |
148 } | |
149 fillbuf((c < 7) ? 3 : c - 3); | |
150 pt_len[i++] = c; | |
151 if (i == i_special) { | |
152 c = getbits(2); | |
153 while (--c >= 0) pt_len[i++] = 0; | |
154 } | |
155 } | |
156 while (i < nn) pt_len[i++] = 0; | |
157 make_table(nn, pt_len, 8, pt_table); | |
158 } | |
159 } | |
160 | |
161 static void read_c_len(void) | |
162 { | |
163 int i, c, n; | |
164 unsigned short mask; | |
165 | |
166 n = getbits(CBIT); | |
167 if (n == 0) { | |
168 c = getbits(CBIT); | |
169 for (i = 0; i < NC; i++) c_len[i] = 0; | |
170 for (i = 0; i < 4096; i++) c_table[i] = c; | |
171 } else { | |
172 i = 0; | |
173 while (i < n) { | |
174 c = pt_table[bitbuf >> (BITBUFSIZ - 8)]; | |
175 if (c >= NT) { | |
176 mask = 1U << (BITBUFSIZ - 1 - 8); | |
177 do { | |
178 if (bitbuf & mask) c = right[c]; | |
179 else c = left [c]; | |
180 mask >>= 1; | |
181 } while (c >= NT); | |
182 } | |
183 fillbuf(pt_len[c]); | |
184 if (c <= 2) { | |
185 if (c == 0) c = 1; | |
186 else if (c == 1) c = getbits(4) + 3; | |
187 else c = getbits(CBIT) + 20; | |
188 while (--c >= 0) c_len[i++] = 0; | |
189 } else c_len[i++] = c - 2; | |
190 } | |
191 while (i < NC) c_len[i++] = 0; | |
192 make_table(NC, c_len, 12, c_table); | |
193 } | |
194 } | |
195 | |
196 | |
197 static unsigned short decode_c(void) | |
198 { | |
199 unsigned short j, mask; | |
200 | |
201 if (blocksize == 0) { | |
202 blocksize = getbits(16); | |
203 read_pt_len(NT, TBIT, 3); | |
204 read_c_len(); | |
205 read_pt_len(NP, PBIT, -1); | |
206 } | |
207 blocksize--; | |
208 j = c_table[bitbuf >> (BITBUFSIZ - 12)]; | |
209 if (j >= NC) { | |
210 mask = 1U << (BITBUFSIZ - 1 - 12); | |
211 do { | |
212 if (bitbuf & mask) j = right[j]; | |
213 else j = left [j]; | |
214 mask >>= 1; | |
215 } while (j >= NC); | |
216 } | |
217 fillbuf(c_len[j]); | |
218 return j; | |
219 } | |
220 | |
221 | |
222 static unsigned short decode_p(void) | |
223 { | |
224 unsigned short j, mask; | |
225 | |
226 j = pt_table[bitbuf >> (BITBUFSIZ - 8)]; | |
227 if (j >= NP) { | |
228 mask = 1U << (BITBUFSIZ - 1 - 8); | |
229 do { | |
230 if (bitbuf & mask) j = right[j]; | |
231 else j = left [j]; | |
232 mask >>= 1; | |
233 } while (j >= NP); | |
234 } | |
235 fillbuf(pt_len[j]); | |
236 if (j != 0) j = (1U << (j - 1)) + getbits(j - 1); | |
237 return j; | |
238 } | |
239 | |
240 | |
241 static void decode(unsigned short count, unsigned char buffer[]) | |
242 { | |
243 static unsigned short i; | |
244 unsigned short r, c; | |
245 | |
246 r = 0; | |
247 while (--j >= 0) { | |
248 buffer[r] = buffer[i]; | |
249 i = (i + 1) & (DICSIZ - 1); | |
250 if (++r == count) return; | |
251 } | |
252 for ( ; ; ) { | |
253 c = decode_c(); | |
254 if (c <= UCHAR_MAX) { | |
255 buffer[r] = c & UCHAR_MAX; | |
256 if (++r == count) return; | |
257 } else { | |
258 j = c - (UCHAR_MAX + 1 - THRESHOLD); | |
259 i = (r - decode_p() - 1) & (DICSIZ - 1); | |
260 while (--j >= 0) { | |
261 buffer[r] = buffer[i]; | |
262 i = (i + 1) & (DICSIZ - 1); | |
263 if (++r == count) return; | |
264 } | |
265 } | |
266 } | |
267 } | |
268 | |
269 void lh5_decode(unsigned char *inp, unsigned char *outp, unsigned long original_size, unsigned long packed_size) | |
270 { | |
271 unsigned short n; | |
272 unsigned char *buffer; | |
273 | |
274 compsize = packed_size; | |
275 origsize = original_size; | |
276 in_buf = inp; | |
277 out_buf = outp; | |
278 | |
279 buffer = (unsigned char *) malloc(DICSIZ); | |
280 if (!buffer) error ("Out of memory"); | |
281 | |
282 bitbuf = 0; subbitbuf = 0; bitcount = 0; | |
283 fillbuf(BITBUFSIZ); | |
284 blocksize = 0; | |
285 j = 0; | |
286 | |
287 while (origsize != 0) { | |
288 n = (origsize > DICSIZ) ? DICSIZ : (unsigned short)origsize; | |
289 decode(n, buffer); | |
290 memmove(out_buf, buffer, n); | |
291 out_buf += n; | |
292 origsize -= n; | |
293 } | |
294 | |
295 if (buffer) free (buffer); | |
296 buffer = NULL; | |
297 } |