lib/lizard.c

   1 /*
   2  *      LiZaRd -- Fast compression method based on Lempel-Ziv 77
   3  *
   4  *      (c) 2004, Robert Spalek <robert@ucw.cz>
   5  *
   6  *      This software may be freely distributed and used according to the terms
   7  *      of the GNU Lesser General Public License.
   8  *
   9  *      The file format is based on LZO1X and
  10  *      the compression method is based on zlib.
  11  */
  12
  13 #include "lib/lib.h"
  14 #include "lib/lizard.h"
  15
  16 #include <string.h>
  17
  18 typedef u16 hash_ptr_t;
  19 struct hash_record {
  20   /* the position in the original text is implicit; it is computed by locate_string() */
  21   hash_ptr_t next;                      // 0=end
  22   hash_ptr_t prev;                      // high bit: 0=record in array, 1=head in hash-table (i.e. value of hashf)
  23 };
  24
  25 #define HASH_SIZE       (1<<14)         // size of hash-table
  26 #define HASH_RECORDS    (1<<15)         // maximum number of records in hash-table, 0 is unused ==> subtract 1
  27 #define CHAIN_MAX_TESTS         8       // crop longer collision chains
  28 #define CHAIN_GOOD_MATCH        32      // we already have a good match => end
  29
  30 static inline uns
  31 hashf(byte *string)
  32   /* 0..HASH_SIZE-1 */
  33 {
  34     return string[0] ^ (string[1]<<3) ^ (string[2]<<6);
  35 }
  36
  37 static inline byte *
  38 locate_string(byte *string, uns record_id, uns head)
  39   /* The strings are recorded into the hash-table regularly, hence there is no
  40    * need to store the pointer there.  */
  41 {
  42   string += record_id - head;
  43   if (record_id >= head)
  44     string -= HASH_RECORDS-1;
  45   return string;
  46 }
  47
  48 static inline uns
  49 find_match(uns record_id, struct hash_record *hash_rec, byte *string, byte *string_end, byte **best_ptr, uns head)
  50   /* hash_tab[hash] == record_id points to the head of the double-linked
  51    * link-list of strings with the same hash.  The records are statically
  52    * stored in circular array hash_rec (with the 1st entry unused), and the
  53    * pointers are just 16-bit indices.  The strings in every collision chain
  54    * are ordered by age.  */
  55 {
  56   uns count = CHAIN_MAX_TESTS;
  57   uns best_len = 0;
  58   while (record_id && count-- > 0)
  59   {
  60     byte *record_string = locate_string(string, record_id, head);
  61     byte *cmp = record_string;
  62     if (cmp[0] == string[0] && cmp[2] == string[2])
  63     /* implies cmp[1] == string[1] */
  64     {
  65       if (cmp[3] == string[3])
  66       {
  67         cmp += 4;
  68         if (*cmp++ == string[4] && *cmp++ == string[5]
  69             && *cmp++ == string[6] && *cmp++ == string[7])
  70         {
  71           byte *str = string + 8;
  72           while (str <= string_end && *cmp++ == *str++);
  73         }
  74       }
  75       else
  76         cmp += 4;
  77       uns len = cmp - record_string - 1;        /* cmp points 2 characters after the last match */
  78       if (len > best_len)
  79       {
  80         best_len = len;
  81         *best_ptr = record_string;
  82         if (best_len >= CHAIN_GOOD_MATCH)       /* optimization */
  83           break;
  84       }
  85     }
  86     record_id = hash_rec[record_id].next;
  87   }
  88   return best_len;
  89 }
  90
  91 static uns
  92 hash_string(hash_ptr_t *hash_tab, uns hash, struct hash_record *hash_rec, /*byte *string,*/ uns head, uns *to_delete)
  93   /* We reuse hash-records stored in a circular array.  First, delete the old
  94    * one and then add the new one in front of the link-list.  */
  95 {
  96   struct hash_record *rec = hash_rec + head;
  97   if (*to_delete)                               /* unlink the original record */
  98   {
  99     uns prev_id = rec->prev & ((1<<15)-1);
 100     if (rec->prev & (1<<15))                    /* was a head */
 101       hash_tab[prev_id] = 0;
 102     else                                        /* thanks to the ordering, this was a tail */
 103       hash_rec[prev_id].next = 0;
 104   }
 105   rec->next = hash_tab[hash];
 106   rec->prev = (1<<15) | hash;
 107   hash_rec[rec->next].prev = head;
 108   hash_tab[hash] = head;                        /* add the new record before the link-list */
 109
 110   if (++head >= HASH_RECORDS)                   /* circular buffer, reuse old records, 0 is unused */
 111   {
 112     head = 1;
 113     *to_delete = 1;
 114   }
 115   return head;
 116 }
 117
 118 static inline byte *
 119 dump_unary_value(byte *out, uns l)
 120 {
 121   while (l > 255)
 122   {
 123     l -= 255;
 124     *out++ = 0;
 125   }
 126   *out++ = l;
 127   return out;
 128 }
 129
 130 static byte *
 131 flush_copy_command(uns bof, byte *out, byte *start, uns len)
 132 {
 133   if (bof && len <= 238)
 134     *out++ = len + 17;
 135   else if (len < 4)
 136     /* cannot happen when !!bof */
 137     out[-2] |= len;                             /* invariant: lowest 2 bits 2 bytes back */
 138   else
 139   {
 140     /* leave 2 least significant bits of out[-2] set to 0 */
 141     if (len <= 18)
 142       *out++ = len - 3;
 143     else
 144     {
 145       *out++ = 0;
 146       out = dump_unary_value(out, len - 18);
 147     }
 148   }
 149   while (len-- > 0)
 150     *out++ = *start++;
 151   return out;
 152 }
 153
 154 int
 155 lizard_compress(byte *in, uns in_len, byte *out)
 156   /* Requires out being allocated for at least in_len * LIZARD_MAX_MULTIPLY +
 157    * LIZARD_MAX_ADD.  There must be at least LIZARD_NEEDS_CHARS characters
 158    * allocated after in.  Returns the actual compressed length. */
 159 {
 160   hash_ptr_t hash_tab[HASH_SIZE];
 161   struct hash_record hash_rec[HASH_RECORDS];
 162   byte *in_start = in;
 163   byte *in_end = in + in_len;
 164   byte *out_start = out;
 165   byte *copy_start = in;
 166   uns head = 1;                                 /* 0 in unused */
 167   uns to_delete = 0;
 168   bzero(hash_tab, sizeof(hash_tab));            /* init the hash-table */
 169   while (in < in_end)
 170   {
 171     uns hash = hashf(in);
 172     byte *best;
 173     uns len = find_match(hash_tab[hash], hash_rec, in, in_end, &best, head);
 174     if (len < 3)
 175 #if 0                   // TODO: now, our routine does not detect matches of length 2
 176       if (len == 2 && (in - best->string) < ((1<<10) + 1))
 177       { /* pass-thru */ }
 178       else
 179 #endif
 180       {
 181 literal:
 182         head = hash_string(hash_tab, hash, hash_rec, head, &to_delete);
 183         in++;                                   /* add a literal */
 184         continue;
 185       }
 186
 187     if (in + len > in_end)                      /* crop EOF */
 188     {
 189       len = in_end - in;
 190       if (len < 3)
 191         goto literal;
 192     }
 193     /* Record the match.  */
 194     uns copy_len = in - copy_start;
 195     uns is_in_copy_mode = copy_start==in_start || copy_len >= 4;
 196     uns shift = in - best - 1;
 197     /* Try to use a 2-byte sequence.  */
 198 #if 0
 199     if (len == 2)
 200     {
 201       if (is_in_copy_mode || !copy_len)         /* cannot use with 0 copied characters, because this bit pattern is reserved for copy mode */
 202         goto literal;
 203       else
 204         goto dump_2sequence;
 205     } else
 206 #endif
 207     if (len == 3 && is_in_copy_mode && shift >= (1<<11) && shift < (1<<11) + (1<<10))
 208     {
 209       /* optimisation for length-3 matches after a copy command */
 210       shift -= 1<<11;
 211 dump_2sequence:
 212       if (copy_len > 0)
 213         out = flush_copy_command(copy_start==in_start, out, copy_start, copy_len);
 214       *out++ = (shift>>6) & ~3;                 /* shift fits into 10 bits */
 215       *out++ = shift & 0xff;
 216     }
 217     /* now, len >= 3 */
 218     else if (shift < (1<<11) && len <= 8)
 219     {
 220       shift |= (len-3 + 2)<<11;
 221       goto dump_2sequence;                      /* shift has 11 bits and contains also len */
 222     }
 223     /* We have to use a 3-byte sequence.  */
 224     else if (len == 3 && is_in_copy_mode)
 225       /* avoid 3-sequence compressed to 3 sequence if it can simply be appended */
 226       goto literal;
 227     else
 228     {
 229       if (copy_len > 0)
 230         out = flush_copy_command(copy_start==in_start, out, copy_start, copy_len);
 231       if (shift < (1<<14))
 232       {
 233         if (len <= 33)
 234           *out++ = (1<<5) | (len-2);
 235         else
 236         {
 237           *out++ = 1<<5;
 238           out = dump_unary_value(out, len - 33);
 239         }
 240       }
 241       else /* shift < (1<<15)-1 becase of HASH_RECORDS */
 242       {
 243         shift++;                                /* because shift==0 is reserved for EOF */
 244         byte pos_bit = (shift>>11) & (1<<3);
 245         if (len <= 9)
 246           *out++ = (1<<4) | pos_bit | (len-2);
 247         else
 248         {
 249           *out++ = (1<<4) | pos_bit;
 250           out = dump_unary_value(out, len - 9);
 251         }
 252       }
 253       *out++ = (shift>>6) & ~3;                 /* rest of shift fits into 14 bits */
 254       *out++ = shift & 0xff;
 255     }
 256     /* Update the hash-table.  */
 257     head = hash_string(hash_tab, hash, hash_rec, head, &to_delete);
 258     for (uns i=1; i<len; i++)
 259       head = hash_string(hash_tab, hashf(in+i), hash_rec, head, &to_delete);
 260     in += len;
 261     copy_start = in;
 262   }
 263   if (in > in_end)                              /* crop at BOF */
 264     in = in_end;
 265   uns copy_len = in - copy_start;
 266   if (copy_len > 0)
 267     out = flush_copy_command(copy_start==in_start, out, copy_start, copy_len);
 268   *out++ = 17;                                  /* add EOF */
 269   *out++ = 0;
 270   *out++ = 0;
 271   return out - out_start;
 272 }
 273
 274 static inline byte *
 275 read_unary_value(byte *in, uns *val)
 276 {
 277   uns l = 0;
 278   while (!*in++)
 279     l += 255;
 280   l += in[-1];
 281   *val = l;
 282   return in;
 283 }
 284
 285 int
 286 lizard_decompress(byte *in, byte *out)
 287   /* Requires out being allocated for the decompressed length must be known
 288    * beforehand.  It is desirable to lock the following memory page for
 289    * read-only access to prevent buffer overflow.  Returns the actual
 290    * decompressed length or a negative number when an error has occured.  */
 291 {
 292   byte *out_start = out;
 293   uns expect_copy_command = 1;
 294   uns len;
 295   if (*in > 17)                                 /* short copy command at BOF */
 296   {
 297     len = *in++ - 17;
 298     expect_copy_command = 2;
 299     goto perform_copy_command;
 300   }
 301   while (1)
 302   {
 303     uns c = *in++;
 304     uns pos;
 305     if (c < 0x10)
 306       if (expect_copy_command == 1)
 307       {
 308         if (!c)
 309         {
 310           in = read_unary_value(in, &len);
 311           len += 18;
 312         }
 313         else
 314           len = c + 3;
 315         expect_copy_command = 2;
 316         goto perform_copy_command;
 317       }
 318       else
 319       {
 320         pos = ((c&0xc)<<6) | *in++;
 321         if (expect_copy_command == 2)
 322         {
 323           pos += 1<<11;
 324           len = 3;
 325         }
 326         else
 327           len = 2;
 328         pos++;
 329       }
 330     else if (c < 0x20)
 331     {
 332       pos = (c&0x8)<<11;
 333       len = c&0x7;
 334       if (!len)
 335       {
 336         in = read_unary_value(in, &len);
 337         len += 9;
 338       }
 339       else
 340         len += 2;
 341       pos |= (*in++ & 0xfc)<<6;
 342       pos |= *in++;
 343       if (!pos)                                 /* EOF */
 344         break;
 345       /* do NOT pos++ */
 346     }
 347     else if (c < 0x40)
 348     {
 349       len = c&0x1f;
 350       if (!len)
 351       {
 352         in = read_unary_value(in, &len);
 353         len += 33;
 354       }
 355       else
 356         len += 2;
 357       pos = (*in++ & 0xfc)<<6;
 358       pos |= *in++;
 359       pos++;
 360     }
 361     else /* high bits encode the length */
 362     {
 363       len = ((c&0xe0)>>5) -2 +3;
 364       pos = (c&0x1c)<<6;
 365       pos |= *in++;
 366       pos++;
 367     }
 368     /* take from the sliding window */
 369     if (len <= pos)
 370     {
 371       memcpy(out, out-pos, len);
 372       out += len;
 373     }
 374     else
 375     {                                           /* overlapping */
 376       for (; len-- > 0; out++)
 377         *out = out[-pos];
 378     }
 379     /* extract the copy-bits */
 380     len = in[-2] & 0x3;
 381     if (len)
 382     {
 383       expect_copy_command = 0;
 384       while (len-- > 0)
 385         *out++ = *in++;
 386     }
 387     else
 388       expect_copy_command = 1;
 389     continue;
 390
 391 perform_copy_command:
 392     memcpy(out, in, len);
 393     out += len;
 394     in += len;
 395   }
 396
 397   return out - out_start;
 398 }
 399
 400 /*
 401
 402 Description of the LZO1X format :
 403 =================================
 404
 405 Beginning of file:
 406 ------------------
 407
 408 If the first byte is 00010001, it means probably EOF (empty file), so switch
 409 to the compressed mode.  If it is bigger, subtract 17 and copy this number of
 410 the following characters to the ouput and switch to the compressed mode.  If
 411 it is smaller, go to the copy mode.
 412
 413 Compressed mode :
 414 -----------------
 415
 416 Read the first byte of the sequence and determine the type of bit-encoding by
 417 looking at the most significant bits.  The sequence is always at least 2 bytes
 418 long.  Decode sequences of these types until the EOF or END marker is read.
 419
 420   length L = length of the text taken from the sliding window
 421
 422     If L=0, then count the number Z of the following zero bytes and add Z*255
 423     to the value of the following non-zero byte.  This allows setting L
 424     arbitrarily high.
 425
 426   position p = relative position of the beginning of the text
 427
 428     Exception: 00010001 00000000 00000000 means EOF
 429
 430   copying C = length 1..3 of copied characters or END=0
 431
 432     C following characters will be copied from the compressed text to the
 433     output.  The number CC is always stored in the 2 least significant bits of
 434     the second last byte of the sequence.
 435
 436     If END is read, the algorithm switches to the copy mode.
 437
 438 pattern                                 length          position
 439
 440 0000ppCC                 pppppppp       2               10 bits (*)
 441 0001pLLL L*     ppppppCC pppppppp       3..9 + extend   15 bits + EOF
 442 001LLLLL L*     ppppppCC pppppppp       3..33 + extend  14 bits
 443 01\
 444 10 \
 445 11  \
 446 LLLpppCC                 pppppppp       3..8            11 bits
 447
 448 Copy mode :
 449 -----------
 450
 451 Read the first byte and, if the most significant bits are 0000, perform the
 452 following command, otherwise switch to the compressed mode (and evaluate the
 453 command).
 454
 455 pattern                                 length          position
 456
 457 0000LLLL L*                             4..18 + extend  N/A
 458
 459   Copy L characters from the compressed text to the output.  The overhead for
 460   incompressible strings is only roughly 1/256 + epsilon.
 461
 462 (*) After reading one copy command, switch to the compressed mode with the
 463 following "optimisation": the pattern 0000ppCC expands to length 3 instead of 2
 464 and 2048 is added to the position (now it is slightly more than 11 bits),
 465 because a sequence of length 2 would never be used.
 466
 467 */