1 /* ------------------------------------------------------------------------ */
3 /* slice.c -- sliding dictionary with percolating update */
5 /* Modified Nobutaka Watazaki */
7 /* Ver. 1.14d Exchanging a search algorithm 1997.01.11 T.Okamoto */
8 /* ------------------------------------------------------------------------ */
19 static int noslide = 1;
22 /* ------------------------------------------------------------------------ */
24 static unsigned long encoded_origsize;
26 /* ------------------------------------------------------------------------ */
28 static unsigned int *hash;
29 static unsigned int *prev;
31 /* static unsigned char *text; */
32 unsigned char *too_flag;
35 static struct encode_option encode_define[2] = {
36 #if defined(__STDC__) || defined(AIX)
38 {(void (*) ()) output_dyn,
39 (void (*) ()) encode_start_fix,
40 (void (*) ()) encode_end_dyn},
42 {(void (*) ()) output_st1,
43 (void (*) ()) encode_start_st1,
44 (void (*) ()) encode_end_st1}
47 {(int (*) ()) output_dyn,
48 (int (*) ()) encode_start_fix,
49 (int (*) ()) encode_end_dyn},
51 {(int (*) ()) output_st1,
52 (int (*) ()) encode_start_st1,
53 (int (*) ()) encode_end_st1}
57 static struct decode_option decode_define[] = {
59 {decode_c_dyn, decode_p_st0, decode_start_fix},
61 {decode_c_dyn, decode_p_dyn, decode_start_dyn},
63 {decode_c_st0, decode_p_st0, decode_start_st0},
65 {decode_c_st1, decode_p_st1, decode_start_st1},
67 {decode_c_st1, decode_p_st1, decode_start_st1},
69 {decode_c_st1, decode_p_st1, decode_start_st1},
71 {decode_c_st1, decode_p_st1, decode_start_st1},
73 {decode_c_lzs, decode_p_lzs, decode_start_lzs},
75 {decode_c_lz5, decode_p_lz5, decode_start_lz5}
78 static struct encode_option encode_set;
79 static struct decode_option decode_set;
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;
91 #define DICSIZ (1L << 16)
92 #define TXTSIZ (DICSIZ * 2L + MAXMATCH)
94 #define DICSIZ (((unsigned long)1) << 15)
95 #define TXTSIZ (DICSIZ * 2 + MAXMATCH)
98 #define HSHSIZ (((unsigned long)1) <<15)
100 #define LIMIT 0x100 /* chain ŤΠlimit */
102 static unsigned int txtsiz;
104 static unsigned long dicsiz;
106 static unsigned int hval;
108 static unsigned int matchpos;
109 static unsigned int pos;
110 static unsigned int remainder;
113 /* ------------------------------------------------------------------------ */
118 if (method == LZHUFF1_METHOD_NUM) { /* Changed N.Watazaki */
119 encode_set = encode_define[0];
121 dicbit = 12; /* 12 Changed N.Watazaki */
122 } else { /* method LH4(12),LH5(13),LH6(15) */
123 encode_set = encode_define[1];
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 */
133 dicsiz = (((unsigned long)1) << dicbit);
134 txtsiz = dicsiz*2+maxmatch;
136 if (hash) return method;
138 if (alloc_buf() == NULL) exit(207); /* I don't know this 207. */
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);
145 if (hash == NULL || prev == NULL || text == NULL || too_flag == NULL)
151 /* ------------------------------------------------------------------------ */
152 /* ¥Ý¥¤¥ó¥¿¤Î½é´ü²½ */
154 static void init_slide()
158 for (i = 0; i < HSHSIZ; i++) {
163 for (i = 0; i < DICSIZ; i++) {
169 /* ¼½ñ¤ò DICSIZ ʬ Á°¤Ë¤º¤é¤¹ */
178 memmove(&text[0], &text[dicsiz], (unsigned)(txtsiz - dicsiz));
182 i = 0; j = dicsiz; m = txtsiz-dicsiz;
184 text[i++] = text[j++];
188 n = fread_crc(&text[(unsigned)(txtsiz - dicsiz)],
189 (unsigned)dicsiz, infile);
192 encoded_origsize += n;
195 for (i = 0; i < HSHSIZ; i++) {
197 hash[i] = (j > dicsiz) ? j - dicsiz : NIL;
200 for (i = 0; i < dicsiz; i++) {
202 prev[i] = (j > dicsiz) ? j - dicsiz : NIL;
207 /* ¸½ºß¤Îʸ»úÎó¤ò¥Á¥§¡¼¥ó¤ËÄɲ乤ë */
211 prev[pos & (dicsiz - 1)] = hash[hval];
216 /* ¸½ºß¤Îʸ»úÎó¤ÈºÇĹ°ìÃפ¹¤ëʸ»úÎó¤ò¸¡º÷¤·¡¢¥Á¥§¡¼¥ó¤ËÄɲ乤ë */
218 static void match_insert()
220 unsigned int scan_pos, scan_end, len;
221 unsigned char *a, *b;
222 unsigned int chain, off, h, max;
224 max = maxmatch; /* MAXMATCH; */
225 if (matchlen < THRESHOLD - 1) matchlen = THRESHOLD - 1;
229 for (h = hval; too_flag[h] && off < maxmatch - THRESHOLD; ) {
230 h = ((h << 5) ^ text[pos + (++off) + 2]) & (unsigned)(HSHSIZ - 1);
232 if (off == maxmatch - THRESHOLD) off = 0;
236 scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
237 while (scan_pos > scan_end) {
240 if (text[scan_pos + matchlen - off] == text[pos + matchlen]) {
242 a = text + scan_pos - off; b = text + pos;
243 for (len = 0; len < max && *a++ == *b++; len++);
246 if (len > matchlen) {
247 matchpos = scan_pos - off;
248 if ((matchlen = len) == max) {
253 if (matchpos < dicsiz) {
254 printf("matchpos=%u scan_pos=%u dicsiz=%u\n"
255 ,matchpos, scan_pos, dicsiz);
261 scan_pos = prev[scan_pos & (dicsiz - 1)];
267 if (matchlen > off + 2 || off == 0)
273 prev[pos & (dicsiz - 1)] = hash[hval];
278 /* ¥Ý¥¤¥ó¥¿¤ò¿Ê¤á¡¢¼½ñ¤ò¹¹¿·¤·¡¢¥Ï¥Ã¥·¥åÃͤò¹¹¿·¤¹¤ë */
280 static void get_next()
283 if (++pos >= txtsiz - maxmatch) {
289 hval = ((hval << 5) ^ text[pos + 2]) & (unsigned)(HSHSIZ - 1);
292 void encode(interface)
293 struct interfacing *interface;
296 unsigned int lastmatchoffset;
303 fout = fopen("en", "wt");
304 if (fout == NULL) exit(1);
306 infile = interface->infile;
307 outfile = interface->outfile;
308 origsize = interface->original;
309 compsize = count = 0L;
310 crc = unpackable = 0;
312 /* encode_alloc(); */ /* allocate_memory(); */
315 encode_set.encode_start();
316 memset(&text[0], ' ', (long)TXTSIZ);
318 remainder = fread_crc(&text[dicsiz], txtsiz-dicsiz, infile);
319 encoded_origsize = remainder;
320 matchlen = THRESHOLD - 1;
324 if (matchlen > remainder) matchlen = remainder;
325 hval = ((((text[dicsiz] << 5) ^ text[dicsiz + 1]) << 5)
326 ^ text[dicsiz + 2]) & (unsigned)(HSHSIZ - 1);
329 while (remainder > 0 && ! unpackable) {
330 lastmatchlen = matchlen; lastmatchoffset = pos - matchpos - 1;
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);
337 fprintf(fout, "%u C %02X\n", addr, text[pos-1]);
342 encode_set.output(lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD),
343 (lastmatchoffset) & (dicsiz-1) );
347 fprintf(fout, "%u M %u %u ", addr,
348 lastmatchoffset & (dicsiz-1), lastmatchlen+1);
349 addr += lastmatchlen +1 ;
353 for (t=0; t<lastmatchlen+1; t++) {
354 cc = text[(pos-(lastmatchoffset)) & (dicsiz-1)];
355 fprintf(fout, "%02X ", cc);
360 while (--lastmatchlen > 0) {
361 get_next(); insert();
365 matchlen = THRESHOLD - 1;
367 if (matchlen > remainder) matchlen = remainder;
370 encode_set.encode_end();
372 interface->packed = compsize;
373 interface->original = encoded_origsize;
376 /* ------------------------------------------------------------------------ */
379 struct interfacing *interface;
381 unsigned int i, j, k, c;
382 unsigned int dicsiz1, offset;
383 unsigned char *dtext;
387 fout = fopen("de", "wt");
388 if (fout == NULL) exit(1);
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];
400 dicsiz = 1L << dicbit;
401 dtext = (unsigned char *) malloc(dicsiz);
403 /* error(MEMOVRERR, NULL); */
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;
411 while (count < origsize) {
412 c = decode_set.decode_c();
413 if (c <= UCHAR_MAX) {
415 fprintf(fout, "%u C %02X\n", count, c);
419 fwrite_crc(dtext, dicsiz, outfile);
426 i = (loc - decode_set.decode_p() - 1) & dicsiz1;
428 fprintf(fout, "%u M %u %u ", count, (loc-1-i) & dicsiz1, j);
431 for (k = 0; k < j; k++) {
432 c = dtext[(i + k) & dicsiz1];
435 fprintf(fout, "%02X ", c & 0xff);
439 fwrite_crc(dtext, dicsiz, outfile);
449 fwrite_crc(dtext, loc, outfile);
455 /* Local Variables: */