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 const 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
error(char * msg)48 static void error(char *msg)
49 {
50 fprintf(stderr, "libayemu: lh5dec.c: %s\n", msg);
51 exit(EXIT_FAILURE);
52 }
53
fillbuf(int n)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
getbits(int n)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
make_table(int nchar,unsigned char bitlen[],int tablebits,unsigned short table[])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
read_pt_len(int nn,int nbit,int i_special)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
read_c_len(void)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
decode_c(void)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
decode_p(void)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
decode(unsigned short count,unsigned char buffer[])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
lh5_decode(const unsigned char * inp,unsigned char * outp,unsigned long original_size,unsigned long packed_size)269 void lh5_decode(const 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 #if 0
280 fprintf(stderr, "DEBUG: compsize = %ld, origsize = %ld, first 8 bytes of packed data:\n", packed_size, original_size);
281 fprintf(stderr, " %02x %02x %02x %02x %02x %02x %02x %02x \n",
282 *(inp), *(inp+1),*(inp+2),*(inp+3),
283 *(inp+4),*(inp+5),*(inp+6),*(inp+7));
284 #endif
285
286 buffer = (unsigned char *) malloc(DICSIZ);
287 if (!buffer) error ("Out of memory");
288
289 bitbuf = 0; subbitbuf = 0; bitcount = 0;
290 fillbuf(BITBUFSIZ);
291 blocksize = 0;
292 j = 0;
293
294 while (origsize != 0) {
295 n = (origsize > DICSIZ) ? DICSIZ : (unsigned short)origsize;
296 decode(n, buffer);
297 memmove(out_buf, buffer, n);
298 out_buf += n;
299 origsize -= n;
300 }
301
302 if (buffer) free (buffer);
303 buffer = NULL;
304 }
305