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 #include <assert.h>
  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 #define TXTSIZ (MAX_DICSIZ * 2L + MAXMATCH)
  82 #define HSHSIZ (((unsigned long)1) <<15)
  83 #define NIL 0
  84 #define LIMIT 0x100 /* chain Ä¹¤Î limit */
  85
  86 static unsigned int txtsiz;
  87
  88 static unsigned long dicsiz;
  89
  90 static unsigned int hval;
  91 static int matchlen;
  92 static unsigned int matchpos;
  93 static unsigned int pos;
  94 static unsigned int remainder;
  95
  96
  97 /* ------------------------------------------------------------------------ */
  98 int
  99 encode_alloc(method)
 100     int             method;
 101 {
 102     switch (method) {
 103     case LZHUFF1_METHOD_NUM:
 104         encode_set = encode_define[0];
 105         maxmatch = 60;
 106         dicbit = LZHUFF1_DICBIT;    /* 12 bits  Changed N.Watazaki */
 107         break;
 108     case LZHUFF5_METHOD_NUM:
 109         encode_set = encode_define[1];
 110         maxmatch = MAXMATCH;
 111         dicbit = LZHUFF5_DICBIT;    /* 13 bits */
 112         break;
 113     case LZHUFF6_METHOD_NUM:
 114         encode_set = encode_define[1];
 115         maxmatch = MAXMATCH;
 116         dicbit = LZHUFF6_DICBIT;    /* 15 bits */
 117         break;
 118     case LZHUFF7_METHOD_NUM:
 119         encode_set = encode_define[1];
 120         maxmatch = MAXMATCH;
 121         dicbit = LZHUFF7_DICBIT;    /* 16 bits */
 122         break;
 123     default:
 124         assert(0);
 125     }
 126
 127     dicsiz = (((unsigned long)1) << dicbit);
 128     txtsiz = dicsiz*2+maxmatch;
 129
 130     if (hash) return method;
 131
 132     alloc_buf();
 133
 134     hash = (unsigned int*)xmalloc(HSHSIZ * sizeof(unsigned int));
 135     prev = (unsigned int*)xmalloc(MAX_DICSIZ * sizeof(unsigned int));
 136     text = (unsigned char*)xmalloc(TXTSIZ);
 137     too_flag = (unsigned char*)xmalloc(HSHSIZ);
 138
 139     return method;
 140 }
 141
 142 /* ------------------------------------------------------------------------ */
 143 /* ¥Ý¥¤¥ó¥¿¤Î½é´ü²½ */
 144
 145 static void init_slide()
 146 {
 147     unsigned int i;
 148
 149     for (i = 0; i < HSHSIZ; i++) {
 150         hash[i] = NIL;
 151         too_flag[i] = 0;
 152     }
 153     /*
 154     for (i = 0; i < DICSIZ; i++) {
 155         prev[i] = NIL;
 156     }
 157     */
 158 }
 159
 160 /* ¼½ñ¤ò DICSIZ Ê¬ Á°¤Ë¤º¤é¤¹ */
 161
 162 static unsigned int
 163 update(crc)
 164     unsigned int crc;
 165 {
 166     unsigned int i, j;
 167     long n;
 168
 169     assert(dicsiz > 0);
 170     assert(txtsiz - dicsiz > 0);
 171     memmove(&text[0], &text[dicsiz], txtsiz - dicsiz);
 172
 173     n = fread_crc(&crc, &text[txtsiz - dicsiz], dicsiz, infile);
 174
 175     remainder += n;
 176     encoded_origsize += n;      /* total size of read bytes */
 177
 178     pos -= dicsiz;
 179     for (i = 0; i < HSHSIZ; i++) {
 180         j = hash[i];
 181         hash[i] = (j > dicsiz) ? j - dicsiz : NIL;
 182         too_flag[i] = 0;
 183     }
 184     for (i = 0; i < dicsiz; i++) {
 185         j = prev[i];
 186         prev[i] = (j > dicsiz) ? j - dicsiz : NIL;
 187     }
 188
 189     return crc;
 190 }
 191
 192
 193 /* ¸½ºß¤ÎÊ¸»úÎó¤ò¥Á¥§¡¼¥ó¤ËÄÉ²Ã¤¹¤ë */
 194
 195 static void insert()
 196 {
 197     prev[pos & (dicsiz - 1)] = hash[hval];
 198     hash[hval] = pos;
 199 }
 200
 201
 202 /* ¸½ºß¤ÎÊ¸»úÎó¤ÈºÇÄ¹°ìÃ×¤¹¤ëÊ¸»úÎó¤ò¸¡º÷¤·¡¢¥Á¥§¡¼¥ó¤ËÄÉ²Ã¤¹¤ë */
 203
 204 static void match_insert()
 205 {
 206     unsigned int scan_pos, scan_end, len;
 207     unsigned char *a, *b;
 208     unsigned int chain, off, h, max;
 209
 210     max = maxmatch; /* MAXMATCH; */
 211     if (matchlen < THRESHOLD - 1) matchlen = THRESHOLD - 1;
 212     matchpos = pos;
 213
 214     off = 0;
 215     for (h = hval; too_flag[h] && off < maxmatch - THRESHOLD; ) {
 216         h = ((h << 5) ^ text[pos + (++off) + 2]) & (unsigned)(HSHSIZ - 1);
 217     }
 218     if (off == maxmatch - THRESHOLD) off = 0;
 219     for (;;) {
 220         chain = 0;
 221         scan_pos = hash[h];
 222         scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
 223         while (scan_pos > scan_end) {
 224             chain++;
 225
 226             if (text[scan_pos + matchlen - off] == text[pos + matchlen]) {
 227                 {
 228                     a = text + scan_pos - off;  b = text + pos;
 229                     for (len = 0; len < max && *a++ == *b++; len++);
 230                 }
 231
 232                 if (len > matchlen) {
 233                     matchpos = scan_pos - off;
 234                     if ((matchlen = len) == max) {
 235                         break;
 236                     }
 237 #ifdef DEBUG
 238                     if (noslide) {
 239                       if (matchpos < dicsiz) {
 240                         printf("matchpos=%u scan_pos=%u dicsiz=%u\n"
 241                                ,matchpos, scan_pos, dicsiz);
 242                       }
 243                     }
 244 #endif
 245                 }
 246             }
 247             scan_pos = prev[scan_pos & (dicsiz - 1)];
 248         }
 249
 250         if (chain >= LIMIT)
 251             too_flag[h] = 1;
 252
 253         if (matchlen > off + 2 || off == 0)
 254             break;
 255         max = off + 2;
 256         off = 0;
 257         h = hval;
 258     }
 259     prev[pos & (dicsiz - 1)] = hash[hval];
 260     hash[hval] = pos;
 261 }
 262
 263
 264 /* ¥Ý¥¤¥ó¥¿¤ò¿Ê¤á¡¢¼½ñ¤ò¹¹¿·¤·¡¢¥Ï¥Ã¥·¥åÃÍ¤ò¹¹¿·¤¹¤ë */
 265
 266 static unsigned int
 267 get_next(crc)
 268     unsigned int crc;
 269 {
 270     remainder--;
 271     if (++pos >= txtsiz - maxmatch) {
 272         crc = update(crc);
 273 #ifdef DEBUG
 274         noslide = 0;
 275 #endif
 276     }
 277     hval = ((hval << 5) ^ text[pos + 2]) & (unsigned)(HSHSIZ - 1);
 278
 279     return crc;
 280 }
 281
 282 unsigned int
 283 encode(interface)
 284     struct interfacing *interface;
 285 {
 286     int lastmatchlen;
 287     unsigned int lastmatchoffset;
 288     unsigned int crc;
 289
 290 #ifdef DEBUG
 291     unsigned int addr;
 292
 293     addr = 0;
 294
 295     fout = fopen("en", "wt");
 296     if (fout == NULL) exit(1);
 297 #endif
 298     infile = interface->infile;
 299     outfile = interface->outfile;
 300     origsize = interface->original;
 301     compsize = count = 0L;
 302     unpackable = 0;
 303
 304     INITIALIZE_CRC(crc);
 305
 306     /* encode_alloc(); */ /* allocate_memory(); */
 307     init_slide();
 308
 309     encode_set.encode_start();
 310     memset(&text[0], ' ', TXTSIZ);
 311
 312     remainder = fread_crc(&crc, &text[dicsiz], txtsiz-dicsiz, infile);
 313     encoded_origsize = remainder;
 314     matchlen = THRESHOLD - 1;
 315
 316     pos = dicsiz;
 317
 318     if (matchlen > remainder) matchlen = remainder;
 319     hval = ((((text[dicsiz] << 5) ^ text[dicsiz + 1]) << 5)
 320             ^ text[dicsiz + 2]) & (unsigned)(HSHSIZ - 1);
 321
 322     insert();
 323     while (remainder > 0 && ! unpackable) {
 324         lastmatchlen = matchlen;  lastmatchoffset = pos - matchpos - 1;
 325         --matchlen;
 326         crc = get_next(crc);  match_insert();
 327         if (matchlen > remainder) matchlen = remainder;
 328         if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) {
 329             encode_set.output(text[pos - 1], 0);
 330 #ifdef DEBUG
 331             fprintf(fout, "%u C %02X\n", addr, text[pos-1]);
 332             addr++;
 333 #endif
 334             count++;
 335         } else {
 336             encode_set.output(lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD),
 337                (lastmatchoffset) & (dicsiz-1) );
 338             --lastmatchlen;
 339
 340 #ifdef DEBUG
 341             fprintf(fout, "%u M %u %u ", addr,
 342                     lastmatchoffset & (dicsiz-1), lastmatchlen+1);
 343             addr += lastmatchlen +1 ;
 344
 345             {
 346                 int t,cc;
 347                 for (t=0; t<lastmatchlen+1; t++) {
 348                     cc = text[pos - lastmatchoffset - 2 + t];
 349                     fprintf(fout, "%02X ", cc);
 350                 }
 351                 fprintf(fout, "\n");
 352             }
 353 #endif
 354             while (--lastmatchlen > 0) {
 355                 crc = get_next(crc);  insert();
 356                 count++;
 357             }
 358             crc = get_next(crc);
 359             matchlen = THRESHOLD - 1;
 360             match_insert();
 361             if (matchlen > remainder) matchlen = remainder;
 362         }
 363     }
 364     encode_set.encode_end();
 365
 366     interface->packed = compsize;
 367     interface->original = encoded_origsize;
 368
 369     return crc;
 370 }
 371
 372 /* ------------------------------------------------------------------------ */
 373 unsigned int
 374 decode(interface)
 375     struct interfacing *interface;
 376 {
 377     unsigned int i, j, k, c;
 378     unsigned int dicsiz1, offset;
 379     unsigned char *dtext;
 380     unsigned int crc;
 381
 382 #ifdef DEBUG
 383     fout = fopen("de", "wt");
 384     if (fout == NULL) exit(1);
 385 #endif
 386
 387     infile = interface->infile;
 388     outfile = interface->outfile;
 389     dicbit = interface->dicbit;
 390     origsize = interface->original;
 391     compsize = interface->packed;
 392     decode_set = decode_define[interface->method - 1];
 393
 394     INITIALIZE_CRC(crc);
 395     prev_char = -1;
 396     dicsiz = 1L << dicbit;
 397     dtext = (unsigned char *)xmalloc(dicsiz);
 398     for (i=0; i<dicsiz; i++) dtext[i] = 0x20;
 399     decode_set.decode_start();
 400     dicsiz1 = dicsiz - 1;
 401     offset = (interface->method == LARC_METHOD_NUM) ? 0x100 - 2 : 0x100 - 3;
 402     count = 0;
 403     loc = 0;
 404     while (count < origsize) {
 405         c = decode_set.decode_c();
 406         if (c <= UCHAR_MAX) {
 407 #ifdef DEBUG
 408           fprintf(fout, "%u C %02X\n", count, c);
 409 #endif
 410             dtext[loc++] = c;
 411             if (loc == dicsiz) {
 412                 fwrite_crc(&crc, dtext, dicsiz, outfile);
 413                 loc = 0;
 414             }
 415             count++;
 416         }
 417         else {
 418             j = c - offset;
 419             i = (loc - decode_set.decode_p() - 1) & dicsiz1;
 420 #ifdef DEBUG
 421             fprintf(fout, "%u M %u %u ", count, (loc-1-i) & dicsiz1, j);
 422 #endif
 423             count += j;
 424             for (k = 0; k < j; k++) {
 425                 c = dtext[(i + k) & dicsiz1];
 426
 427 #ifdef DEBUG
 428                 fprintf(fout, "%02X ", c & 0xff);
 429 #endif
 430                 dtext[loc++] = c;
 431                 if (loc == dicsiz) {
 432                     fwrite_crc(&crc, dtext, dicsiz, outfile);
 433                     loc = 0;
 434                 }
 435             }
 436 #ifdef DEBUG
 437             fprintf(fout, "\n");
 438 #endif
 439         }
 440     }
 441     if (loc != 0) {
 442         fwrite_crc(&crc, dtext, loc, outfile);
 443     }
 444
 445     free(dtext);
 446     return crc;
 447 }