src/slide.c

   1 /* ------------------------------------------------------------------------ */
   2 /* LHa for UNIX                                                             */
   3 /*              slide.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 #ifdef DEBUG
  17 FILE *fout = NULL;
  18 static int noslide = 1;
  19 #endif
  20
  21 /* variables for hash */
  22 struct hash {
  23     unsigned int pos;
  24     int too_flag;               /* if 1, matching candidate is too many */
  25 } *hash;
  26 static unsigned int *prev;      /* previous posiion associated with hash */
  27
  28 /* hash function: it represents 3 letters from `pos' on `text' */
  29 #define INIT_HASH(pos) \
  30         ((( (text[(pos)] << 5) \
  31            ^ text[(pos) + 1]  ) << 5) \
  32            ^ text[(pos) + 2]         ) & (unsigned)(HSHSIZ - 1);
  33 #define NEXT_HASH(hash,pos) \
  34         (((hash) << 5) \
  35            ^ text[(pos) + 2]         ) & (unsigned)(HSHSIZ - 1);
  36
  37 static struct encode_option encode_define[2] = {
  38 #if defined(__STDC__) || defined(AIX)
  39     /* lh1 */
  40     {(void (*) ()) output_dyn,
  41      (void (*) ()) encode_start_fix,
  42      (void (*) ()) encode_end_dyn},
  43     /* lh4, 5, 6, 7 */
  44     {(void (*) ()) output_st1,
  45      (void (*) ()) encode_start_st1,
  46      (void (*) ()) encode_end_st1}
  47 #else
  48     /* lh1 */
  49     {(int (*) ()) output_dyn,
  50      (int (*) ()) encode_start_fix,
  51      (int (*) ()) encode_end_dyn},
  52     /* lh4, 5, 6, 7 */
  53     {(int (*) ()) output_st1,
  54      (int (*) ()) encode_start_st1,
  55      (int (*) ()) encode_end_st1}
  56 #endif
  57 };
  58
  59 static struct decode_option decode_define[] = {
  60     /* lh1 */
  61     {decode_c_dyn, decode_p_st0, decode_start_fix},
  62     /* lh2 */
  63     {decode_c_dyn, decode_p_dyn, decode_start_dyn},
  64     /* lh3 */
  65     {decode_c_st0, decode_p_st0, decode_start_st0},
  66     /* lh4 */
  67     {decode_c_st1, decode_p_st1, decode_start_st1},
  68     /* lh5 */
  69     {decode_c_st1, decode_p_st1, decode_start_st1},
  70     /* lh6 */
  71     {decode_c_st1, decode_p_st1, decode_start_st1},
  72     /* lh7 */
  73     {decode_c_st1, decode_p_st1, decode_start_st1},
  74     /* lzs */
  75     {decode_c_lzs, decode_p_lzs, decode_start_lzs},
  76     /* lz5 */
  77     {decode_c_lz5, decode_p_lz5, decode_start_lz5},
  78     /* lz4 */
  79     {NULL        , NULL        , NULL            },
  80     /* lhd */
  81     {NULL        , NULL        , NULL            },
  82     /* pm0 */
  83     {NULL        , NULL        , NULL            },
  84     /* pm2 */
  85     {decode_c_pm2, decode_p_pm2, decode_start_pm2}
  86 };
  87
  88 static struct encode_option encode_set;
  89 static struct decode_option decode_set;
  90
  91 #define TXTSIZ (MAX_DICSIZ * 2L + MAXMATCH)
  92 #define HSHSIZ (((unsigned long)1) <<15)
  93 #define NIL 0
  94 #define LIMIT 0x100             /* limit of hash chain */
  95
  96 static unsigned int txtsiz;
  97 static unsigned long dicsiz;
  98 static unsigned int remainder;
  99
 100 struct matchdata {
 101     int len;
 102     unsigned int off;
 103 };
 104
 105 int
 106 encode_alloc(method)
 107     int method;
 108 {
 109     switch (method) {
 110     case LZHUFF1_METHOD_NUM:
 111         encode_set = encode_define[0];
 112         maxmatch = 60;
 113         dicbit = LZHUFF1_DICBIT;    /* 12 bits  Changed N.Watazaki */
 114         break;
 115     case LZHUFF5_METHOD_NUM:
 116         encode_set = encode_define[1];
 117         maxmatch = MAXMATCH;
 118         dicbit = LZHUFF5_DICBIT;    /* 13 bits */
 119         break;
 120     case LZHUFF6_METHOD_NUM:
 121         encode_set = encode_define[1];
 122         maxmatch = MAXMATCH;
 123         dicbit = LZHUFF6_DICBIT;    /* 15 bits */
 124         break;
 125     case LZHUFF7_METHOD_NUM:
 126         encode_set = encode_define[1];
 127         maxmatch = MAXMATCH;
 128         dicbit = LZHUFF7_DICBIT;    /* 16 bits */
 129         break;
 130     default:
 131         error("unknown method %d", method);
 132         exit(1);
 133     }
 134
 135     dicsiz = (((unsigned long)1) << dicbit);
 136     txtsiz = dicsiz*2+maxmatch;
 137
 138     if (hash) return method;
 139
 140     alloc_buf();
 141
 142     hash = (struct hash*)xmalloc(HSHSIZ * sizeof(struct hash));
 143     prev = (unsigned int*)xmalloc(MAX_DICSIZ * sizeof(unsigned int));
 144     text = (unsigned char*)xmalloc(TXTSIZ);
 145
 146     return method;
 147 }
 148
 149 static void
 150 init_slide()
 151 {
 152     unsigned int i;
 153
 154     for (i = 0; i < HSHSIZ; i++) {
 155         hash[i].pos = NIL;
 156         hash[i].too_flag = 0;
 157     }
 158 }
 159
 160 /* update dictionary */
 161 static void
 162 update_dict(pos, crc)
 163     unsigned int *pos;
 164     unsigned int *crc;
 165 {
 166     unsigned int i, j;
 167     long n;
 168
 169     memmove(&text[0], &text[dicsiz], txtsiz - dicsiz);
 170
 171     n = fread_crc(crc, &text[txtsiz - dicsiz], dicsiz, infile);
 172
 173     remainder += n;
 174
 175     *pos -= dicsiz;
 176     for (i = 0; i < HSHSIZ; i++) {
 177         j = hash[i].pos;
 178         hash[i].pos = (j > dicsiz) ? j - dicsiz : NIL;
 179         hash[i].too_flag = 0;
 180     }
 181     for (i = 0; i < dicsiz; i++) {
 182         j = prev[i];
 183         prev[i] = (j > dicsiz) ? j - dicsiz : NIL;
 184     }
 185 }
 186
 187 /* associate position with token */
 188 static void
 189 insert_hash(token, pos)
 190     unsigned int token;
 191     unsigned int pos;
 192 {
 193     prev[pos & (dicsiz - 1)] = hash[token].pos; /* chain the previous pos. */
 194     hash[token].pos = pos;
 195 }
 196
 197 static void
 198 search_dict_1(token, pos, off, max, m)
 199     unsigned int token;
 200     unsigned int pos;
 201     unsigned int off;
 202     unsigned int max;           /* max. length of matching string */
 203     struct matchdata *m;
 204 {
 205     unsigned int chain = 0;
 206     unsigned int scan_pos = hash[token].pos;
 207     int scan_beg = scan_pos - off;
 208     int scan_end = pos - dicsiz;
 209     unsigned int len;
 210
 211     while (scan_beg > scan_end) {
 212         chain++;
 213
 214         if (text[scan_beg + m->len] == text[pos + m->len]) {
 215             {
 216                 /* collate token */
 217                 unsigned char *a = &text[scan_beg];
 218                 unsigned char *b = &text[pos];
 219
 220                 for (len = 0; len < max && *a++ == *b++; len++);
 221             }
 222
 223             if (len > m->len) {
 224                 m->off = pos - scan_beg;
 225                 m->len = len;
 226                 if (m->len == max)
 227                     break;
 228
 229 #ifdef DEBUG
 230                 if (noslide) {
 231                     if (pos - m->off < dicsiz) {
 232                         printf("matchpos=%u scan_pos=%u dicsiz=%u\n",
 233                                pos - m->off, scan_pos, dicsiz);
 234                     }
 235                 }
 236 #endif
 237             }
 238         }
 239         scan_pos = prev[scan_pos & (dicsiz - 1)];
 240         scan_beg = scan_pos - off;
 241     }
 242
 243     if (chain >= LIMIT)
 244         hash[token].too_flag = 1;
 245 }
 246
 247 /* search the longest token matching to current token */
 248 static void
 249 search_dict(token, pos, min, m)
 250     unsigned int token;         /* search token */
 251     unsigned int pos;           /* position of token */
 252     int min;                    /* min. length of matching string */
 253     struct matchdata *m;
 254 {
 255     unsigned int off, tok, max;
 256
 257     if (min < THRESHOLD - 1) min = THRESHOLD - 1;
 258
 259     max = maxmatch;
 260     m->off = 0;
 261     m->len = min;
 262
 263     off = 0;
 264     for (tok = token; hash[tok].too_flag && off < maxmatch - THRESHOLD; ) {
 265         /* If matching position is too many, The search key is
 266            changed into following token from `off' (for speed). */
 267         ++off;
 268         tok = NEXT_HASH(tok, pos+off);
 269     }
 270     if (off == maxmatch - THRESHOLD) {
 271         off = 0;
 272         tok = token;
 273     }
 274
 275     search_dict_1(tok, pos, off, max, m);
 276
 277     if (off > 0 && m->len < off + 3)
 278         /* re-search */
 279         search_dict_1(token, pos, 0, off+2, m);
 280
 281     if (m->len > remainder) m->len = remainder;
 282 }
 283
 284 /* slide dictionary */
 285 static void
 286 next_token(token, pos, crc)
 287     unsigned int *token;
 288     unsigned int *pos;
 289     unsigned int *crc;
 290 {
 291     remainder--;
 292     if (++*pos >= txtsiz - maxmatch) {
 293         update_dict(pos, crc);
 294 #ifdef DEBUG
 295         noslide = 0;
 296 #endif
 297     }
 298     *token = NEXT_HASH(*token, *pos);
 299 }
 300
 301 unsigned int
 302 encode(interface)
 303     struct interfacing *interface;
 304 {
 305     unsigned int token, pos, crc;
 306     off_t count;
 307     struct matchdata match, last;
 308
 309 #ifdef DEBUG
 310     if (!fout)
 311         fout = xfopen("en", "wt");
 312     fprintf(fout, "[filename: %s]\n", reading_filename);
 313 #endif
 314     infile = interface->infile;
 315     outfile = interface->outfile;
 316     origsize = interface->original;
 317     compsize = count = 0L;
 318     unpackable = 0;
 319
 320     INITIALIZE_CRC(crc);
 321
 322     init_slide();
 323
 324     encode_set.encode_start();
 325     memset(text, ' ', TXTSIZ);
 326
 327     remainder = fread_crc(&crc, &text[dicsiz], txtsiz-dicsiz, infile);
 328
 329     match.len = THRESHOLD - 1;
 330     match.off = 0;
 331     if (match.len > remainder) match.len = remainder;
 332
 333     pos = dicsiz;
 334     token = INIT_HASH(pos);
 335     insert_hash(token, pos);     /* associate token and pos */
 336
 337     while (remainder > 0 && ! unpackable) {
 338         last = match;
 339
 340         next_token(&token, &pos, &crc);
 341         search_dict(token, pos, last.len-1, &match);
 342         insert_hash(token, pos);
 343
 344         if (match.len > last.len || last.len < THRESHOLD) {
 345             /* output a letter */
 346             encode_set.output(text[pos - 1], 0);
 347 #ifdef DEBUG
 348             fprintf(fout, "%u C %02X\n", count, text[pos-1]);
 349 #endif
 350             count++;
 351         } else {
 352             /* output length and offset */
 353             encode_set.output(last.len + (256 - THRESHOLD),
 354                               (last.off-1) & (dicsiz-1) );
 355
 356 #ifdef DEBUG
 357             {
 358                 int i;
 359                 unsigned char *ptr;
 360                 unsigned int offset = (last.off & (dicsiz-1));
 361
 362                 fprintf(fout, "%u M <%u %u> ",
 363                         count, last.len, count - offset);
 364
 365                 ptr = &text[pos-1 - offset];
 366                 for (i=0; i < last.len; i++)
 367                     fprintf(fout, "%02X ", ptr[i]);
 368                 fprintf(fout, "\n");
 369             }
 370 #endif
 371             count += last.len;
 372
 373             --last.len;
 374             while (--last.len > 0) {
 375                 next_token(&token, &pos, &crc);
 376                 insert_hash(token, pos);
 377             }
 378             next_token(&token, &pos, &crc);
 379             search_dict(token, pos, THRESHOLD - 1, &match);
 380             insert_hash(token, pos);
 381         }
 382     }
 383     encode_set.encode_end();
 384
 385     interface->packed = compsize;
 386     interface->original = count;
 387
 388     return crc;
 389 }
 390
 391 unsigned int
 392 decode(interface)
 393     struct interfacing *interface;
 394 {
 395     unsigned int i, c;
 396     unsigned int dicsiz1, adjust;
 397     unsigned int crc;
 398
 399 #ifdef DEBUG
 400     if (!fout)
 401         fout = xfopen("de", "wt");
 402     fprintf(fout, "[filename: %s]\n", writing_filename);
 403 #endif
 404
 405     infile = interface->infile;
 406     outfile = interface->outfile;
 407     dicbit = interface->dicbit;
 408     origsize = interface->original;
 409     compsize = interface->packed;
 410     decode_set = decode_define[interface->method - 1];
 411
 412     INITIALIZE_CRC(crc);
 413     dicsiz = 1L << dicbit;
 414     dtext = (unsigned char *)xmalloc(dicsiz);
 415
 416     if (extract_broken_archive)
 417
 418         /* LHa for UNIX (autoconf) had a fatal bug since version
 419            1.14i-ac20030713 (slide.c revision 1.20).
 420
 421            This bug is possible to make a broken archive, proper LHA
 422            cannot extract it (probably it report CRC error).
 423
 424            If the option "--extract-broken-archive" specified, extract
 425            the broken archive made by old LHa for UNIX. */
 426         memset(dtext, 0, dicsiz);
 427     else
 428         memset(dtext, ' ', dicsiz);
 429     decode_set.decode_start();
 430     dicsiz1 = dicsiz - 1;
 431     adjust = 256 - THRESHOLD;
 432     if ((interface->method == LARC_METHOD_NUM) || (interface->method == PMARC2_METHOD_NUM))
 433         adjust = 256 - 2;
 434
 435     decode_count = 0;
 436     loc = 0;
 437     while (decode_count < origsize) {
 438         c = decode_set.decode_c();
 439         if (c < 256) {
 440             if (dump_lzss) {
 441 #if SIZEOF_OFF_T == 8
 442                 printf("%04llu %02x(%c)\n",
 443                        decode_count, c, isprint(c) ? c : '?');
 444 #else
 445                 printf("%04lu %02x(%c)\n",
 446                        decode_count, c, isprint(c) ? c : '?');
 447 #endif
 448             }
 449             dtext[loc++] = c;
 450             if (loc == dicsiz) {
 451                 fwrite_crc(&crc, dtext, dicsiz, outfile);
 452                 loc = 0;
 453             }
 454             decode_count++;
 455         }
 456         else {
 457             struct matchdata match;
 458             unsigned int matchpos;
 459
 460             match.len = c - adjust;
 461             match.off = decode_set.decode_p() + 1;
 462             matchpos = (loc - match.off) & dicsiz1;
 463             if (dump_lzss) {
 464 #if SIZEOF_OFF_T == 8
 465                 printf("%04llu <%u %llu>\n",
 466                        decode_count, match.len, decode_count-match.off);
 467 #else
 468                 printf("%04lu <%u %lu>\n",
 469                        decode_count, match.len, decode_count-match.off);
 470 #endif
 471             }
 472
 473             decode_count += match.len;
 474             for (i = 0; i < match.len; i++) {
 475                 c = dtext[(matchpos + i) & dicsiz1];
 476                 /*
 477                 if (dump_lzss) {
 478                     printf(" %02x", c & 0xff);
 479                 }
 480                 */
 481                 dtext[loc++] = c;
 482                 if (loc == dicsiz) {
 483                     fwrite_crc(&crc, dtext, dicsiz, outfile);
 484                     loc = 0;
 485                 }
 486             }
 487             /*
 488             if (dump_lzss) {
 489                 printf("\n");
 490             }
 491             */
 492         }
 493     }
 494     if (loc != 0) {
 495         fwrite_crc(&crc, dtext, loc, outfile);
 496     }
 497
 498     free(dtext);
 499
 500     /* usually read size is interface->packed */
 501     interface->read_size = interface->packed - compsize;
 502
 503     return crc;
 504 }