cde/programs/dtinfo/DtMmdb/compression/lzss.C

   1 /* $XConsortium: lzss.cc /main/5 1996/07/18 16:00:08 drk $ */
   2
   3 #include "compression/lzss.h"
   4
   5 /*
   6
   7 Adapted from LDS (lossless datacompression sources) Version 1.1 by
   8 Nico E. de Vries.
   9
  10 qfc. 12-8-93.
  11
  12 */
  13
  14 /**************************************************************
  15         LZSS.C -- A Data Compression Program
  16         (tab = 4 spaces)
  17 ***************************************************************
  18         4/6/1989 Haruhiko Okumura
  19         Use, distribute, and modify this program freely.
  20         Please send me your improved versions.
  21                 PC-VAN          SCIENCE
  22                 NIFTY-Serve     PAF01022
  23                 CompuServe      74050,1022
  24 **************************************************************/
  25 #include <stdio.h>
  26 #include <stdlib.h>
  27 #include <string.h>
  28 #include <ctype.h>
  29
  30 #define N                4096   /* size of ring buffer */
  31 #define F                  18   /* upper limit for match_length */
  32 #define THRESHOLD           2   /* encode string into position and length
  33                                    if match_length is greater than this */
  34 #define NIL                 N   /* index for root of binary search trees */
  35
  36 unsigned long int
  37                 textsize = 0,   /* text size counter */
  38                 codesize = 0,   /* code size counter */
  39                 printcount = 0; /* counter for reporting progress every 1K bytes */
  40 unsigned char
  41                 text_buf[N + F - 1];    /* ring buffer of size N,
  42                         with extra F-1 bytes to facilitate string comparison */
  43 int             match_position, match_length,  /* of longest match.  These are
  44                         set by the InsertNode() procedure. */
  45                 lson[N + 1], rson[N + 257], dad[N + 1];  /* left & right children &
  46                         parents -- These constitute binary search trees. */
  47 //FILE  *infile, *outfile;  /* input & output files */
  48
  49 void InitTree(void)  /* initialize trees */
  50 {
  51         int  i;
  52
  53         /* For i = 0 to N - 1, rson[i] and lson[i] will be the right and
  54            left children of node i.  These nodes need not be initialized.
  55            Also, dad[i] is the parent of node i.  These are initialized to
  56            NIL (= N), which stands for 'not used.'
  57            For i = 0 to 255, rson[N + i + 1] is the root of the tree
  58            for strings that begin with character i.  These are initialized
  59            to NIL.  Note there are 256 trees. */
  60
  61         for (i = N + 1; i <= N + 256; i++) rson[i] = NIL;
  62         for (i = 0; i < N; i++) dad[i] = NIL;
  63 }
  64
  65 void InsertNode(int r)
  66         /* Inserts string of length F, text_buf[r..r+F-1], into one of the
  67            trees (text_buf[r]'th tree) and returns the longest-match position
  68            and length via the global variables match_position and match_length.
  69            If match_length = F, then removes the old node in favor of the new
  70            one, because the old one will be deleted sooner.
  71            Note r plays double role, as tree node and position in buffer. */
  72 {
  73         int  i, p, cmp;
  74         unsigned char  *key;
  75
  76         cmp = 1;  key = &text_buf[r];  p = N + 1 + key[0];
  77         rson[r] = lson[r] = NIL;  match_length = 0;
  78         for ( ; ; ) {
  79                 if (cmp >= 0) {
  80                         if (rson[p] != NIL) p = rson[p];
  81                         else {  rson[p] = r;  dad[r] = p;  return;  }
  82                 } else {
  83                         if (lson[p] != NIL) p = lson[p];
  84                         else {  lson[p] = r;  dad[r] = p;  return;  }
  85                 }
  86                 for (i = 1; i < F; i++)
  87                         if ((cmp = key[i] - text_buf[p + i]) != 0)  break;
  88                 if (i > match_length) {
  89                         match_position = p;
  90                         if ((match_length = i) >= F)  break;
  91                 }
  92         }
  93         dad[r] = dad[p];  lson[r] = lson[p];  rson[r] = rson[p];
  94         dad[lson[p]] = r;  dad[rson[p]] = r;
  95         if (rson[dad[p]] == p) rson[dad[p]] = r;
  96         else                   lson[dad[p]] = r;
  97         dad[p] = NIL;  /* remove p */
  98 }
  99
 100 void DeleteNode(int p)  /* deletes node p from tree */
 101 {
 102         int  q;
 103
 104         if (dad[p] == NIL) return;  /* not in tree */
 105         if (rson[p] == NIL) q = lson[p];
 106         else if (lson[p] == NIL) q = rson[p];
 107         else {
 108                 q = lson[p];
 109                 if (rson[q] != NIL) {
 110                         do {  q = rson[q];  } while (rson[q] != NIL);
 111                         rson[dad[q]] = lson[q];  dad[lson[q]] = dad[q];
 112                         lson[q] = lson[p];  dad[lson[p]] = q;
 113                 }
 114                 rson[q] = rson[p];  dad[rson[p]] = q;
 115         }
 116         dad[q] = dad[p];
 117         if (rson[dad[p]] == p) rson[dad[p]] = q;  else lson[dad[p]] = q;
 118         dad[p] = NIL;
 119 }
 120
 121 void lzss::compress(const buffer& uncompressed, buffer& compressed)
 122 {
 123    if ( compressed.buf_sz() < uncompressed.buf_sz() )
 124       compressed.expand_chunk(uncompressed.buf_sz());
 125
 126 ////////////////////////////////////////////
 127 ////////////////////////////////////////////
 128    int  i, c, len, r, s, last_match_length, code_buf_ptr;
 129    unsigned char  code_buf[17], mask;
 130
 131    InitTree();  /* initialize trees */
 132    code_buf[0] = 0;  /* code_buf[1..16] saves eight units of code, and
 133         code_buf[0] works as eight flags, "1" representing that the unit
 134         is an unencoded letter (1 byte), "0" a position-and-length pair
 135         (2 bytes).  Thus, eight units require at most 16 bytes of code. */
 136
 137    code_buf_ptr = mask = 1;
 138    s = 0;  r = N - F;
 139    for (i = s; i < r; i++) text_buf[i] = ' ';  /* Clear the buffer with
 140                 any character that will appear often. */
 141
 142    char* unc_str = uncompressed.get_base();
 143    int  unc_str_len = uncompressed.content_sz();
 144    int  unc_str_ptr = 0;
 145
 146    for (len = 0; len < F; len++) {
 147
 148       if ( unc_str_ptr == unc_str_len )
 149          break;
 150
 151       c = unc_str[unc_str_ptr++];
 152 //cerr << char(c);
 153
 154       text_buf[r + len] = c;  /* Read F bytes into the last F bytes of
 155                                  the buffer */
 156    }
 157
 158    if ((textsize = len) == 0) return;  /* text of size zero */
 159
 160    for (i = 1; i <= F; i++) InsertNode(r - i);  /* Insert the F strings,
 161         each of which begins with one or more 'space' characters.  Note
 162         the order in which these strings are inserted.  This way,
 163         degenerate trees will be less likely to occur. */
 164
 165    InsertNode(r);  /* Finally, insert the whole string just read.  The
 166                   global variables match_length and match_position are set. */
 167
 168    do {
 169       if (match_length > len) match_length = len;  /* match_length
 170                 may be spuriously long near the end of text. */
 171
 172
 173          if (match_length <= THRESHOLD) {
 174
 175             match_length = 1;  /* Not long enough match.  Send one byte. */
 176             code_buf[0] |= mask;  /* 'send one byte' flag */
 177             code_buf[code_buf_ptr++] = text_buf[r];  /* Send uncoded. */
 178
 179          } else {
 180
 181             code_buf[code_buf_ptr++] = (unsigned char) match_position;
 182             code_buf[code_buf_ptr++] = (unsigned char)
 183                  (((match_position >> 4) & 0xf0)
 184                   | (match_length - (THRESHOLD + 1)));  /* Send position and
 185
 186
 187                                length pair. Note match_length > THRESHOLD. */
 188          }
 189
 190          if ((mask <<= 1) == 0) {  /* Shift mask left one bit. */
 191
 192
 193 //           for (i = 0; i < code_buf_ptr; i++) {  /* Send at most 8 units of */
 194 //              putc(code_buf[i], outfile);     /* code together */
 195 //           }
 196
 197              compressed.put((char*)code_buf, code_buf_ptr, true);
 198
 199              codesize += code_buf_ptr;
 200              code_buf[0] = 0;  code_buf_ptr = mask = 1;
 201          }
 202
 203          last_match_length = match_length;
 204
 205          for (i = 0; i < last_match_length; i++) {
 206
 207             if ( unc_str_ptr == unc_str_len )
 208                break;
 209
 210             c = unc_str[unc_str_ptr++];
 211
 212             DeleteNode(s);              /* Delete old strings and */
 213             text_buf[s] = c;    /* read new bytes */
 214
 215             if (s < F - 1) text_buf[s + N] = c;  /* If the position is
 216                         near the end of buffer, extend the buffer to make
 217                         string comparison easier. */
 218
 219             //s = (s + 1) & (N - 1);  r = (r + 1) & (N - 1);
 220             s++; s &= (N - 1);  r++; r &= (N - 1);
 221                 /* Since this is a ring buffer, increment the position
 222                                    modulo N. */
 223
 224             InsertNode(r);      /* Register the string in text_buf[r..r+F-1] */
 225         }
 226
 227         //      if ((textsize += i) > printcount) {
 228         //              printf("%12ld\r", textsize);  printcount += 1024;
 229         //              /* Reports progress each time the textsize exceeds
 230         //                         multiples of 1024. */
 231         //      }
 232
 233       while (i++ < last_match_length) {/* After the end of text, */
 234          DeleteNode(s);          /* no need to read, but */
 235
 236          //s = (s + 1) & (N - 1);  r = (r + 1) & (N - 1);
 237          s++; s &= (N - 1);  r++; r &= (N - 1);
 238
 239          if (--len) InsertNode(r);      /* buffer may not be empty. */
 240       }
 241
 242    } while (len > 0);   /* until length of string to be processed is zero */
 243
 244    if (code_buf_ptr > 1) {              /* Send remaining code. */
 245
 246 //              for (i = 0; i < code_buf_ptr; i++) {
 247 //                  //putc(code_buf[i], outfile);
 248 //                  compressed.put(code_buf[i], true);
 249 //                }
 250
 251       compressed.put((char*)code_buf, code_buf_ptr, true);
 252       codesize += code_buf_ptr;
 253    }
 254
 255
 256         //printf("In : %ld bytes\n", textsize); /* Encoding is done. */
 257         //printf("Out: %ld bytes\n", codesize);
 258         //printf("Out/In: %.3f\n", (double)codesize / textsize);
 259 }
 260
 261 void lzss::decompress(buffer& compressed, buffer& uncompressed)
 262 {
 263    int  i, j, k, r, c;
 264    unsigned int flags;
 265
 266    for (i = 0; i < N - F; i++) text_buf[i] = ' ';
 267    r = N - F;  flags = 0;
 268    for (;;) {
 269       if (((flags >>= 1) & 256) == 0) {
 270
 271          // if ((c = getc(infile)) == EOF) break;
 272
 273          if ( compressed.content_sz() == 0 )
 274             break;
 275
 276          compressed.getusc(c);
 277
 278          flags = c | 0xff00;  /* uses higher byte cleverly */
 279       }                      /* to count eight */
 280
 281       if (flags & 1) {
 282         //if ((c = getc(infile)) == EOF) break;
 283         //putc(c, outfile);  text_buf[r++] = c;  r &= (N - 1);
 284
 285         if ( compressed.content_sz() == 0 )
 286            break;
 287
 288         compressed.getusc(c);
 289
 290 //debug(cerr, char(c));
 291         uncompressed.put(char(c), true);  text_buf[r++] = c;  r &= (N - 1);
 292
 293       } else {
 294         //if ((i = getc(infile)) == EOF) break;
 295         //if ((j = getc(infile)) == EOF) break;
 296
 297        if ( compressed.content_sz() == 0 )
 298           break;
 299        else {
 300           compressed.getusc(i);
 301        }
 302
 303        if ( compressed.content_sz() == 0 )
 304           break;
 305        else
 306           compressed.getusc(j);
 307
 308
 309        i |= ((j & 0xf0) << 4);  j = (j & 0x0f) + THRESHOLD;
 310
 311        for (k = 0; k <= j; k++) {
 312           c = text_buf[(i + k) & (N - 1)];
 313
 314            //putc(c, outfile);
 315 //debug(cerr, char(c));
 316           uncompressed.put(char(c), true);
 317
 318           text_buf[r++] = c;  r &= (N - 1);
 319
 320         }
 321
 322       }
 323    }
 324 }
 325
 326
 327 io_status lzss::build_dict(lex_func_t, getchar_func_t)
 328 {
 329    return done;
 330 }
 331
 332 MMDB_BODIES(lzss)
 333