2 * LiZzaRd -- Fast compression method based on Lempel-Ziv 77
4 * (c) 2004, Robert Spalek <robert@ucw.cz>
6 * The file format is based on LZO1X and
7 * the compression method is based on zlib.
11 #include "lib/lizzard.h"
15 typedef u16 hash_ptr_t;
17 /* the position in the original text is implicit; it is computed by locate_string() */
18 hash_ptr_t next; // 0=end
19 hash_ptr_t prev; // high bit: 0=record in array, 1=head in hash-table (i.e. value of hashf)
22 #define HASH_SIZE (1<<14) // size of hash-table
23 #define HASH_RECORDS (1<<15) // maximum number of records in hash-table, 0 is unused ==> subtract 1
24 #define CHAIN_MAX_TESTS 8 // crop longer collision chains
25 #define CHAIN_GOOD_MATCH 32 // we already have a good match => end
31 return string[0] ^ (string[1]<<3) ^ (string[2]<<6);
35 locate_string(byte *string, uns record_id, uns head)
36 /* The strings are recorded into the hash-table regularly, hence there is no
37 * need to store the pointer there. */
39 string += record_id - head;
40 if (record_id >= head)
41 string -= HASH_RECORDS-1;
46 find_match(uns record_id, struct hash_record *hash_rec, byte *string, byte *string_end, byte **best_ptr, uns head)
47 /* hash_tab[hash] == record_id points to the head of the double-linked
48 * link-list of strings with the same hash. The records are statically
49 * stored in circular array hash_rec (with the 1st entry unused), and the
50 * pointers are just 16-bit indices. The strings in every collision chain
51 * are ordered by age. */
53 uns count = CHAIN_MAX_TESTS;
55 while (record_id && count-- > 0)
57 byte *record_string = locate_string(string, record_id, head);
58 byte *cmp = record_string;
59 if (cmp[0] == string[0] && cmp[2] == string[2])
60 /* implies cmp[1] == string[1] */
62 if (cmp[3] == string[3])
65 if (*cmp++ == string[4] && *cmp++ == string[5]
66 && *cmp++ == string[6] && *cmp++ == string[7])
68 byte *str = string + 8;
69 while (str <= string_end && *cmp++ == *str++);
74 uns len = cmp - record_string - 1; /* cmp points 2 characters after the last match */
78 *best_ptr = record_string;
79 if (best_len >= CHAIN_GOOD_MATCH) /* optimization */
83 record_id = hash_rec[record_id].next;
89 hash_string(hash_ptr_t *hash_tab, uns hash, struct hash_record *hash_rec, /*byte *string,*/ uns head, uns *to_delete)
90 /* We reuse hash-records stored in a circular array. First, delete the old
91 * one and then add the new one in front of the link-list. */
93 struct hash_record *rec = hash_rec + head;
94 if (*to_delete) /* unlink the original record */
96 uns prev_id = rec->prev & ((1<<15)-1);
97 if (rec->prev & (1<<15)) /* was a head */
98 hash_tab[prev_id] = 0;
99 else /* thanks to the ordering, this was a tail */
100 hash_rec[prev_id].next = 0;
102 rec->next = hash_tab[hash];
103 rec->prev = (1<<15) | hash;
104 hash_rec[rec->next].prev = head;
105 hash_tab[hash] = head; /* add the new record before the link-list */
107 if (++head >= HASH_RECORDS) /* circular buffer, reuse old records, 0 is unused */
116 dump_unary_value(byte *out, uns l)
128 flush_copy_command(uns bof, byte *out, byte *start, uns len)
130 if (bof && len <= 238)
133 /* cannot happen when !!bof */
134 out[-2] |= len; /* invariant: lowest 2 bits 2 bytes back */
137 /* leave 2 least significant bits of out[-2] set to 0 */
143 out = dump_unary_value(out, len - 18);
152 lizzard_compress(byte *in, uns in_len, byte *out)
153 /* Requires out being allocated for at least in_len * LIZZARD_MAX_MULTIPLY +
154 * LIZZARD_MAX_ADD. There must be at least LIZZARD_NEEDS_CHARS characters
155 * allocated after in. Returns the actual compressed length. */
157 hash_ptr_t hash_tab[HASH_SIZE];
158 struct hash_record hash_rec[HASH_RECORDS];
160 byte *in_end = in + in_len;
161 byte *out_start = out;
162 byte *copy_start = in;
163 uns head = 1; /* 0 in unused */
165 bzero(hash_tab, sizeof(hash_tab)); /* init the hash-table */
168 uns hash = hashf(in);
170 uns len = find_match(hash_tab[hash], hash_rec, in, in_end, &best, head);
172 #if 0 // TODO: now, our routine does not detect matches of length 2
173 if (len == 2 && (in - best->string) < ((1<<10) + 1))
179 head = hash_string(hash_tab, hash, hash_rec, head, &to_delete);
180 in++; /* add a literal */
184 if (in + len > in_end) /* crop EOF */
190 /* Record the match. */
191 uns copy_len = in - copy_start;
192 uns is_in_copy_mode = copy_start==in_start || copy_len >= 4;
193 uns shift = in - best - 1;
194 /* Try to use a 2-byte sequence. */
198 if (is_in_copy_mode || !copy_len) /* cannot use with 0 copied characters, because this bit pattern is reserved for copy mode */
204 if (len == 3 && is_in_copy_mode && shift >= (1<<11) && shift < (1<<11) + (1<<10))
206 /* optimisation for length-3 matches after a copy command */
210 out = flush_copy_command(copy_start==in_start, out, copy_start, copy_len);
211 *out++ = (shift>>6) & ~3; /* shift fits into 10 bits */
212 *out++ = shift & 0xff;
215 else if (shift < (1<<11) && len <= 8)
217 shift |= (len-3 + 2)<<11;
218 goto dump_2sequence; /* shift has 11 bits and contains also len */
220 /* We have to use a 3-byte sequence. */
221 else if (len == 3 && is_in_copy_mode)
222 /* avoid 3-sequence compressed to 3 sequence if it can simply be appended */
227 out = flush_copy_command(copy_start==in_start, out, copy_start, copy_len);
231 *out++ = (1<<5) | (len-2);
235 out = dump_unary_value(out, len - 33);
238 else /* shift < (1<<15)-1 becase of HASH_RECORDS */
240 shift++; /* because shift==0 is reserved for EOF */
241 byte pos_bit = (shift>>11) & (1<<3);
243 *out++ = (1<<4) | pos_bit | (len-2);
246 *out++ = (1<<4) | pos_bit;
247 out = dump_unary_value(out, len - 9);
250 *out++ = (shift>>6) & ~3; /* rest of shift fits into 14 bits */
251 *out++ = shift & 0xff;
253 /* Update the hash-table. */
254 head = hash_string(hash_tab, hash, hash_rec, head, &to_delete);
255 for (uns i=1; i<len; i++)
256 head = hash_string(hash_tab, hashf(in+i), hash_rec, head, &to_delete);
260 if (in > in_end) /* crop at BOF */
262 uns copy_len = in - copy_start;
264 out = flush_copy_command(copy_start==in_start, out, copy_start, copy_len);
265 *out++ = 17; /* add EOF */
268 return out - out_start;
272 read_unary_value(byte *in, uns *val)
283 lizzard_decompress(byte *in, byte *out)
284 /* Requires out being allocated for the decompressed length must be known
285 * beforehand. It is desirable to lock the following memory page for
286 * read-only access to prevent buffer overflow. Returns the actual
287 * decompressed length or a negative number when an error has occured. */
289 byte *out_start = out;
290 uns expect_copy_command = 1;
292 if (*in > 17) /* short copy command at BOF */
295 expect_copy_command = 2;
296 goto perform_copy_command;
303 if (expect_copy_command == 1)
307 in = read_unary_value(in, &len);
312 expect_copy_command = 2;
313 goto perform_copy_command;
317 pos = ((c&0xc)<<6) | *in++;
318 if (expect_copy_command == 2)
333 in = read_unary_value(in, &len);
338 pos |= (*in++ & 0xfc)<<6;
349 in = read_unary_value(in, &len);
354 pos = (*in++ & 0xfc)<<6;
358 else /* high bits encode the length */
360 len = ((c&0xe0)>>5) -2 +3;
365 /* take from the sliding window */
368 memcpy(out, out-pos, len);
373 for (; len-- > 0; out++)
376 /* extract the copy-bits */
380 expect_copy_command = 0;
385 expect_copy_command = 1;
388 perform_copy_command:
389 memcpy(out, in, len);
394 return out - out_start;
399 Description of the LZO1X format :
400 =================================
405 If the first byte is 00010001, it means probably EOF (empty file), so switch
406 to the compressed mode. If it is bigger, subtract 17 and copy this number of
407 the following characters to the ouput and switch to the compressed mode. If
408 it is smaller, go to the copy mode.
413 Read the first byte of the sequence and determine the type of bit-encoding by
414 looking at the most significant bits. The sequence is always at least 2 bytes
415 long. Decode sequences of these types until the EOF or END marker is read.
417 length L = length of the text taken from the sliding window
419 If L=0, then count the number Z of the following zero bytes and add Z*255
420 to the value of the following non-zero byte. This allows setting L
423 position p = relative position of the beginning of the text
425 Exception: 00010001 00000000 00000000 means EOF
427 copying C = length 1..3 of copied characters or END=0
429 C following characters will be copied from the compressed text to the
430 output. The number CC is always stored in the 2 least significant bits of
431 the second last byte of the sequence.
433 If END is read, the algorithm switches to the copy mode.
435 pattern length position
437 0000ppCC pppppppp 2 10 bits (*)
438 0001pLLL L* ppppppCC pppppppp 3..9 + extend 15 bits + EOF
439 001LLLLL L* ppppppCC pppppppp 3..33 + extend 14 bits
443 LLLpppCC pppppppp 3..8 11 bits
448 Read the first byte and, if the most significant bits are 0000, perform the
449 following command, otherwise switch to the compressed mode (and evaluate the
452 pattern length position
454 0000LLLL L* 4..18 + extend N/A
456 Copy L characters from the compressed text to the output. The overhead for
457 incompressible strings is only roughly 1/256 + epsilon.
459 (*) After reading one copy command, switch to the compressed mode with the
460 following "optimisation": the pattern 0000ppCC expands to length 3 instead of 2
461 and 2048 is added to the position (now it is slightly more than 11 bits),
462 because a sequence of length 2 would never be used.