"SfR Fresh" - the SfR Freeware/Shareware Archive 
Member "lha-114i/src/slide.c" of archive lha-114i.tar.gz:
As a special service "SfR Fresh" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting with prefixed line numbers.
Alternatively you can here view or download the uninterpreted source code file.
That can be also achieved for any archive member file by clicking within an archive contents listing on the first character of the file(path) respectively on the according byte size field.
1 /* ------------------------------------------------------------------------ */
2 /* LHa for UNIX */
3 /* slice.c -- sliding dictionary with percolating update */
4 /* */
5 /* Modified Nobutaka Watazaki */
6 /* */
7 /* Ver. 1.14d Exchanging a search algorithm 1997.01.11 T.Okamoto */
8 /* ------------------------------------------------------------------------ */
9
10 #if 0
11 #define DEBUG 1
12 #endif
13
14 #include "lha.h"
15
16
17 #ifdef DEBUG
18 FILE *fout = NULL;
19 static int noslide = 1;
20 #endif
21
22 /* ------------------------------------------------------------------------ */
23
24 static unsigned long encoded_origsize;
25
26 /* ------------------------------------------------------------------------ */
27
28 static unsigned int *hash;
29 static unsigned int *prev;
30
31 /* static unsigned char *text; */
32 unsigned char *too_flag;
33
34
35 static struct encode_option encode_define[2] = {
36 #if defined(__STDC__) || defined(AIX)
37 /* lh1 */
38 {(void (*) ()) output_dyn,
39 (void (*) ()) encode_start_fix,
40 (void (*) ()) encode_end_dyn},
41 /* lh4, 5,6 */
42 {(void (*) ()) output_st1,
43 (void (*) ()) encode_start_st1,
44 (void (*) ()) encode_end_st1}
45 #else
46 /* lh1 */
47 {(int (*) ()) output_dyn,
48 (int (*) ()) encode_start_fix,
49 (int (*) ()) encode_end_dyn},
50 /* lh4, 5,6 */
51 {(int (*) ()) output_st1,
52 (int (*) ()) encode_start_st1,
53 (int (*) ()) encode_end_st1}
54 #endif
55 };
56
57 static struct decode_option decode_define[] = {
58 /* lh1 */
59 {decode_c_dyn, decode_p_st0, decode_start_fix},
60 /* lh2 */
61 {decode_c_dyn, decode_p_dyn, decode_start_dyn},
62 /* lh3 */
63 {decode_c_st0, decode_p_st0, decode_start_st0},
64 /* lh4 */
65 {decode_c_st1, decode_p_st1, decode_start_st1},
66 /* lh5 */
67 {decode_c_st1, decode_p_st1, decode_start_st1},
68 /* lh6 */
69 {decode_c_st1, decode_p_st1, decode_start_st1},
70 /* lh7 */
71 {decode_c_st1, decode_p_st1, decode_start_st1},
72 /* lzs */
73 {decode_c_lzs, decode_p_lzs, decode_start_lzs},
74 /* lz5 */
75 {decode_c_lz5, decode_p_lz5, decode_start_lz5}
76 };
77
78 static struct encode_option encode_set;
79 static struct decode_option decode_set;
80
81 #if 0
82 static node pos, matchpos, avail, *position, *parent, *prev;
83 static int remainder, matchlen;
84 static unsigned char *level, *childcount;
85 static unsigned long dicsiz; /* t.okamoto */
86 static unsigned short max_hash_val;
87 static unsigned short hash1, hash2;
88 #endif
89
90 #ifdef SUPPORT_LH7
91 #define DICSIZ (1L << 16)
92 #define TXTSIZ (DICSIZ * 2L + MAXMATCH)
93 #else
94 #define DICSIZ (((unsigned long)1) << 15)
95 #define TXTSIZ (DICSIZ * 2 + MAXMATCH)
96 #endif
97
98 #define HSHSIZ (((unsigned long)1) <<15)
99 #define NIL 0
100 #define LIMIT 0x100 /* chain 長の limit */
101
102 static unsigned int txtsiz;
103
104 static unsigned long dicsiz;
105
106 static unsigned int hval;
107 static int matchlen;
108 static unsigned int matchpos;
109 static unsigned int pos;
110 static unsigned int remainder;
111
112
113 /* ------------------------------------------------------------------------ */
114 int
115 encode_alloc(method)
116 int method;
117 {
118 if (method == LZHUFF1_METHOD_NUM) { /* Changed N.Watazaki */
119 encode_set = encode_define[0];
120 maxmatch = 60;
121 dicbit = 12; /* 12 Changed N.Watazaki */
122 } else { /* method LH4(12),LH5(13),LH6(15) */
123 encode_set = encode_define[1];
124 maxmatch = MAXMATCH;
125 if (method == LZHUFF7_METHOD_NUM)
126 dicbit = MAX_DICBIT; /* 16 bits */
127 else if (method == LZHUFF6_METHOD_NUM)
128 dicbit = MAX_DICBIT-1; /* 15 bits */
129 else /* LH5 LH4 is not used */
130 dicbit = MAX_DICBIT - 3; /* 13 bits */
131 }
132
133 dicsiz = (((unsigned long)1) << dicbit);
134 txtsiz = dicsiz*2+maxmatch;
135
136 if (hash) return method;
137
138 if (alloc_buf() == NULL) exit(207); /* I don't know this 207. */
139
140 hash = (unsigned int*)malloc(HSHSIZ * sizeof(unsigned int));
141 prev = (unsigned int*)malloc(DICSIZ * sizeof(unsigned int));
142 text = (unsigned char*)malloc(TXTSIZ);
143 too_flag = (unsigned char*)malloc(HSHSIZ);
144
145 if (hash == NULL || prev == NULL || text == NULL || too_flag == NULL)
146 exit(207);
147
148 return method;
149 }
150
151 /* ------------------------------------------------------------------------ */
152 /* ポインタの初期化 */
153
154 static void init_slide()
155 {
156 unsigned int i;
157
158 for (i = 0; i < HSHSIZ; i++) {
159 hash[i] = NIL;
160 too_flag[i] = 0;
161 }
162 /*
163 for (i = 0; i < DICSIZ; i++) {
164 prev[i] = NIL;
165 }
166 */
167 }
168
169 /* 辞書を DICSIZ 分 前にずらす */
170
171 static void update()
172 {
173 unsigned int i, j;
174 unsigned int k;
175 long n;
176
177 #if 0
178 memmove(&text[0], &text[dicsiz], (unsigned)(txtsiz - dicsiz));
179 #else
180 {
181 int m;
182 i = 0; j = dicsiz; m = txtsiz-dicsiz;
183 while (m-- > 0) {
184 text[i++] = text[j++];
185 }
186 }
187 #endif
188 n = fread_crc(&text[(unsigned)(txtsiz - dicsiz)],
189 (unsigned)dicsiz, infile);
190
191 remainder += n;
192 encoded_origsize += n;
193
194 pos -= dicsiz;
195 for (i = 0; i < HSHSIZ; i++) {
196 j = hash[i];
197 hash[i] = (j > dicsiz) ? j - dicsiz : NIL;
198 too_flag[i] = 0;
199 }
200 for (i = 0; i < dicsiz; i++) {
201 j = prev[i];
202 prev[i] = (j > dicsiz) ? j - dicsiz : NIL;
203 }
204 }
205
206
207 /* 現在の文字列をチェーンに追加する */
208
209 static void insert()
210 {
211 prev[pos & (dicsiz - 1)] = hash[hval];
212 hash[hval] = pos;
213 }
214
215
216 /* 現在の文字列と最長一致する文字列を検索し、チェーンに追加する */
217
218 static void match_insert()
219 {
220 unsigned int scan_pos, scan_end, len;
221 unsigned char *a, *b;
222 unsigned int chain, off, h, max;
223
224 max = maxmatch; /* MAXMATCH; */
225 if (matchlen < THRESHOLD - 1) matchlen = THRESHOLD - 1;
226 matchpos = pos;
227
228 off = 0;
229 for (h = hval; too_flag[h] && off < maxmatch - THRESHOLD; ) {
230 h = ((h << 5) ^ text[pos + (++off) + 2]) & (unsigned)(HSHSIZ - 1);
231 }
232 if (off == maxmatch - THRESHOLD) off = 0;
233 for (;;) {
234 chain = 0;
235 scan_pos = hash[h];
236 scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
237 while (scan_pos > scan_end) {
238 chain++;
239
240 if (text[scan_pos + matchlen - off] == text[pos + matchlen]) {
241 {
242 a = text + scan_pos - off; b = text + pos;
243 for (len = 0; len < max && *a++ == *b++; len++);
244 }
245
246 if (len > matchlen) {
247 matchpos = scan_pos - off;
248 if ((matchlen = len) == max) {
249 break;
250 }
251 #ifdef DEBUG
252 if (noslide) {
253 if (matchpos < dicsiz) {
254 printf("matchpos=%u scan_pos=%u dicsiz=%u\n"
255 ,matchpos, scan_pos, dicsiz);
256 }
257 }
258 #endif
259 }
260 }
261 scan_pos = prev[scan_pos & (dicsiz - 1)];
262 }
263
264 if (chain >= LIMIT)
265 too_flag[h] = 1;
266
267 if (matchlen > off + 2 || off == 0)
268 break;
269 max = off + 2;
270 off = 0;
271 h = hval;
272 }
273 prev[pos & (dicsiz - 1)] = hash[hval];
274 hash[hval] = pos;
275 }
276
277
278 /* ポインタを進め、辞書を更新し、ハッシュ値を更新する */
279
280 static void get_next()
281 {
282 remainder--;
283 if (++pos >= txtsiz - maxmatch) {
284 update();
285 #ifdef DEBUG
286 noslide = 0;
287 #endif
288 }
289 hval = ((hval << 5) ^ text[pos + 2]) & (unsigned)(HSHSIZ - 1);
290 }
291
292 void encode(interface)
293 struct interfacing *interface;
294 {
295 int lastmatchlen;
296 unsigned int lastmatchoffset;
297
298 #ifdef DEBUG
299 unsigned int addr;
300
301 addr = 0;
302
303 fout = fopen("en", "wt");
304 if (fout == NULL) exit(1);
305 #endif
306 infile = interface->infile;
307 outfile = interface->outfile;
308 origsize = interface->original;
309 compsize = count = 0L;
310 crc = unpackable = 0;
311
312 /* encode_alloc(); */ /* allocate_memory(); */
313 init_slide();
314
315 encode_set.encode_start();
316 memset(&text[0], ' ', (long)TXTSIZ);
317
318 remainder = fread_crc(&text[dicsiz], txtsiz-dicsiz, infile);
319 encoded_origsize = remainder;
320 matchlen = THRESHOLD - 1;
321
322 pos = dicsiz;
323
324 if (matchlen > remainder) matchlen = remainder;
325 hval = ((((text[dicsiz] << 5) ^ text[dicsiz + 1]) << 5)
326 ^ text[dicsiz + 2]) & (unsigned)(HSHSIZ - 1);
327
328 insert();
329 while (remainder > 0 && ! unpackable) {
330 lastmatchlen = matchlen; lastmatchoffset = pos - matchpos - 1;
331 --matchlen;
332 get_next(); match_insert();
333 if (matchlen > remainder) matchlen = remainder;
334 if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) {
335 encode_set.output(text[pos - 1], 0);
336 #ifdef DEBUG
337 fprintf(fout, "%u C %02X\n", addr, text[pos-1]);
338 addr++;
339 #endif
340 count++;
341 } else {
342 encode_set.output(lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD),
343 (lastmatchoffset) & (dicsiz-1) );
344 --lastmatchlen;
345
346 #ifdef DEBUG
347 fprintf(fout, "%u M %u %u ", addr,
348 lastmatchoffset & (dicsiz-1), lastmatchlen+1);
349 addr += lastmatchlen +1 ;
350
351 {
352 int t,cc;
353 for (t=0; t<lastmatchlen+1; t++) {
354 cc = text[(pos-(lastmatchoffset)) & (dicsiz-1)];
355 fprintf(fout, "%02X ", cc);
356 }
357 fprintf(fout, "\n");
358 }
359 #endif
360 while (--lastmatchlen > 0) {
361 get_next(); insert();
362 count++;
363 }
364 get_next();
365 matchlen = THRESHOLD - 1;
366 match_insert();
367 if (matchlen > remainder) matchlen = remainder;
368 }
369 }
370 encode_set.encode_end();
371
372 interface->packed = compsize;
373 interface->original = encoded_origsize;
374 }
375
376 /* ------------------------------------------------------------------------ */
377 void
378 decode(interface)
379 struct interfacing *interface;
380 {
381 unsigned int i, j, k, c;
382 unsigned int dicsiz1, offset;
383 unsigned char *dtext;
384
385
386 #ifdef DEBUG
387 fout = fopen("de", "wt");
388 if (fout == NULL) exit(1);
389 #endif
390
391 infile = interface->infile;
392 outfile = interface->outfile;
393 dicbit = interface->dicbit;
394 origsize = interface->original;
395 compsize = interface->packed;
396 decode_set = decode_define[interface->method - 1];
397
398 crc = 0;
399 prev_char = -1;
400 dicsiz = 1L << dicbit;
401 dtext = (unsigned char *) malloc(dicsiz);
402 if (dtext == NULL)
403 /* error(MEMOVRERR, NULL); */
404 exit(errno);
405 for (i=0; i<dicsiz; i++) dtext[i] = 0x20;
406 decode_set.decode_start();
407 dicsiz1 = dicsiz - 1;
408 offset = (interface->method == LARC_METHOD_NUM) ? 0x100 - 2 : 0x100 - 3;
409 count = 0;
410 loc = 0;
411 while (count < origsize) {
412 c = decode_set.decode_c();
413 if (c <= UCHAR_MAX) {
414 #ifdef DEBUG
415 fprintf(fout, "%u C %02X\n", count, c);
416 #endif
417 dtext[loc++] = c;
418 if (loc == dicsiz) {
419 fwrite_crc(dtext, dicsiz, outfile);
420 loc = 0;
421 }
422 count++;
423 }
424 else {
425 j = c - offset;
426 i = (loc - decode_set.decode_p() - 1) & dicsiz1;
427 #ifdef DEBUG
428 fprintf(fout, "%u M %u %u ", count, (loc-1-i) & dicsiz1, j);
429 #endif
430 count += j;
431 for (k = 0; k < j; k++) {
432 c = dtext[(i + k) & dicsiz1];
433
434 #ifdef DEBUG
435 fprintf(fout, "%02X ", c & 0xff);
436 #endif
437 dtext[loc++] = c;
438 if (loc == dicsiz) {
439 fwrite_crc(dtext, dicsiz, outfile);
440 loc = 0;
441 }
442 }
443 #ifdef DEBUG
444 fprintf(fout, "\n");
445 #endif
446 }
447 }
448 if (loc != 0) {
449 fwrite_crc(dtext, loc, outfile);
450 }
451
452 free(dtext);
453 }
454
455 /* Local Variables: */
456 /* mode:c */
457 /* tab-width:4 */
458 /* End: */