2 * LiZaRd -- Fast compression method based on Lempel-Ziv 77
4 * (c) 2004, Robert Spalek <robert@ucw.cz>
6 * This software may be freely distributed and used according to the terms
7 * of the GNU Lesser General Public License.
9 * The file format is based on LZO1X and
10 * the compression method is based on zlib.
14 #include "lib/lizard.h"
18 typedef u16 hash_ptr_t;
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)
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
34 return string[0] ^ (string[1]<<3) ^ (string[2]<<6);
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. */
42 string += record_id - head;
43 if (record_id >= head)
44 string -= HASH_RECORDS-1;
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. */
56 uns count = CHAIN_MAX_TESTS;
58 while (record_id && count-- > 0)
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] */
65 if (cmp[3] == string[3])
68 if (*cmp++ == string[4] && *cmp++ == string[5]
69 && *cmp++ == string[6] && *cmp++ == string[7])
71 byte *str = string + 8;
72 while (str <= string_end && *cmp++ == *str++);
77 uns len = cmp - record_string - 1; /* cmp points 2 characters after the last match */
81 *best_ptr = record_string;
82 if (best_len >= CHAIN_GOOD_MATCH) /* optimization */
86 record_id = hash_rec[record_id].next;
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. */
96 struct hash_record *rec = hash_rec + head;
97 if (*to_delete) /* unlink the original record */
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;
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 */
110 if (++head >= HASH_RECORDS) /* circular buffer, reuse old records, 0 is unused */
119 dump_unary_value(byte *out, uns l)
131 flush_copy_command(uns bof, byte *out, byte *start, uns len)
133 if (bof && len <= 238)
136 /* cannot happen when !!bof */
137 out[-2] |= len; /* invariant: lowest 2 bits 2 bytes back */
140 /* leave 2 least significant bits of out[-2] set to 0 */
146 out = dump_unary_value(out, len - 18);
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. */
160 hash_ptr_t hash_tab[HASH_SIZE];
161 struct hash_record hash_rec[HASH_RECORDS];
163 byte *in_end = in + in_len;
164 byte *out_start = out;
165 byte *copy_start = in;
166 uns head = 1; /* 0 in unused */
168 bzero(hash_tab, sizeof(hash_tab)); /* init the hash-table */
171 uns hash = hashf(in);
173 uns len = find_match(hash_tab[hash], hash_rec, in, in_end, &best, head);
175 #if 0 // TODO: now, our routine does not detect matches of length 2
176 if (len == 2 && (in - best->string) < ((1<<10) + 1))
182 head = hash_string(hash_tab, hash, hash_rec, head, &to_delete);
183 in++; /* add a literal */
187 if (in + len > in_end) /* crop EOF */
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. */
201 if (is_in_copy_mode || !copy_len) /* cannot use with 0 copied characters, because this bit pattern is reserved for copy mode */
207 if (len == 3 && is_in_copy_mode && shift >= (1<<11) && shift < (1<<11) + (1<<10))
209 /* optimisation for length-3 matches after a copy command */
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;
218 else if (shift < (1<<11) && len <= 8)
220 shift |= (len-3 + 2)<<11;
221 goto dump_2sequence; /* shift has 11 bits and contains also len */
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 */
230 out = flush_copy_command(copy_start==in_start, out, copy_start, copy_len);
234 *out++ = (1<<5) | (len-2);
238 out = dump_unary_value(out, len - 33);
241 else /* shift < (1<<15)-1 becase of HASH_RECORDS */
243 shift++; /* because shift==0 is reserved for EOF */
244 byte pos_bit = (shift>>11) & (1<<3);
246 *out++ = (1<<4) | pos_bit | (len-2);
249 *out++ = (1<<4) | pos_bit;
250 out = dump_unary_value(out, len - 9);
253 *out++ = (shift>>6) & ~3; /* rest of shift fits into 14 bits */
254 *out++ = shift & 0xff;
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);
263 if (in > in_end) /* crop at BOF */
265 uns copy_len = in - copy_start;
267 out = flush_copy_command(copy_start==in_start, out, copy_start, copy_len);
268 *out++ = 17; /* add EOF */
271 return out - out_start;
275 read_unary_value(byte *in, uns *val)
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. */
292 byte *out_start = out;
293 uns expect_copy_command = 1;
295 if (*in > 17) /* short copy command at BOF */
298 expect_copy_command = 2;
299 goto perform_copy_command;
306 if (expect_copy_command == 1)
310 in = read_unary_value(in, &len);
315 expect_copy_command = 2;
316 goto perform_copy_command;
320 pos = ((c&0xc)<<6) | *in++;
321 if (expect_copy_command == 2)
336 in = read_unary_value(in, &len);
341 pos |= (*in++ & 0xfc)<<6;
352 in = read_unary_value(in, &len);
357 pos = (*in++ & 0xfc)<<6;
361 else /* high bits encode the length */
363 len = ((c&0xe0)>>5) -2 +3;
368 /* take from the sliding window */
371 memcpy(out, out-pos, len);
376 for (; len-- > 0; out++)
379 /* extract the copy-bits */
383 expect_copy_command = 0;
388 expect_copy_command = 1;
391 perform_copy_command:
392 memcpy(out, in, len);
397 return out - out_start;
402 Description of the LZO1X format :
403 =================================
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.
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.
420 length L = length of the text taken from the sliding window
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
426 position p = relative position of the beginning of the text
428 Exception: 00010001 00000000 00000000 means EOF
430 copying C = length 1..3 of copied characters or END=0
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.
436 If END is read, the algorithm switches to the copy mode.
438 pattern length position
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
446 LLLpppCC pppppppp 3..8 11 bits
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
455 pattern length position
457 0000LLLL L* 4..18 + extend N/A
459 Copy L characters from the compressed text to the output. The overhead for
460 incompressible strings is only roughly 1/256 + epsilon.
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.