src/slide.c

   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: */