93d07f0d386ec2c311393f858aa4b4d37a076d1d
[wimlib] / src / lz.c
1 /*
2  * lz.c
3  *
4  * This file provides the code to analyze a buffer of uncompressed data for
5  * matches, as per the LZ77 algorithm.  It uses a hash table to accelerate the
6  * process.  This is based on code from zlib (v. 1.2.5).
7  */
8
9 /*
10  * Copyright (C) 2012 Eric Biggers
11  * Copyright (C) 1995-2010 Jean-loup Gailly and Mark Adler
12  *
13  * This file is part of wimlib, a library for working with WIM files.
14  *
15  * wimlib is free software; you can redistribute it and/or modify it under the
16  * terms of the GNU General Public License as published by the Free
17  * Software Foundation; either version 3 of the License, or (at your option)
18  * any later version.
19  *
20  * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY
21  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
22  * A PARTICULAR PURPOSE. See the GNU General Public License for more
23  * details.
24  *
25  * You should have received a copy of the GNU General Public License
26  * along with wimlib; if not, see http://www.gnu.org/licenses/.
27  */
28
29 #include "comp.h"
30 #include <string.h>
31
32 #define HASH_BITS       15
33 #define HASH_SIZE       (1 << HASH_BITS)
34 #define HASH_MASK       (HASH_SIZE - 1)
35 #define HASH_SHIFT      ((HASH_BITS + 2) /  3)
36
37 /* Hash function, based on code from zlib.  This function will update and return
38  * the hash value @hash for the string ending on the additional input character
39  * @c.  This function must be called for each consecutive character, because it
40  * uses a running hash value rather than computing it separately for each
41  * 3-character string.
42  *
43  * The AND operation guarantees that only 3 characters will affect the hash
44  * value, so every identical 3-character string will have the same hash value.
45  */
46 static inline uint update_hash(uint hash, u8 c)
47 {
48         return ((hash << HASH_SHIFT) ^ c) & HASH_MASK;
49 }
50
51
52 /* Insert a 3-character string at position @str_pos in @window and with hash
53  * code @hash into the hash table described by @hash_tab and @prev_tab.  Based
54  * on code from zlib.
55  *
56  * The hash table uses chains (linked lists) for the hash buckets, but there are
57  * no real pointers involved.  Indexing `hash_tab' by hash value gives the index
58  * within the window of the last string in the hash bucket.  To find the index
59  * of the previous string in the hash chain, the `prev_tab' array is indexed by
60  * the string index.  `prev_tab' can be indexed repeatedly by the string index
61  * to walk through the hash chain, until the special index `0' is reached,
62  * indicating the end of the hash chain.
63  */
64 static inline uint insert_string(u16 hash_tab[], u16 prev_tab[], 
65                                  const u8 window[], uint str_pos, uint hash)
66 {
67         hash = update_hash(hash, window[str_pos + 2]);
68         prev_tab[str_pos] = hash_tab[hash];
69         hash_tab[hash] = str_pos;
70         return hash;
71 }
72
73
74 /*
75  * Returns the longest match for a given input position.
76  *
77  * @window:             The window of uncompressed data.
78  * @bytes_remaining:    The number of bytes remaining in the window.
79  * @strstart:           The index of the start of the string in the window that
80  *                              we are trying to find a match for.
81  * @prev_tab:           The array of prev pointers for the hash table.
82  * @cur_match:          The index of the head of the hash chain for matches 
83  *                              having the hash value of the string beginning 
84  *                              at index @strstart.
85  * @prev_len:           The length of the match that was found for the string 
86  *                              beginning at (@strstart - 1).
87  * @match_start_ret:    A location into which the index of the start of the
88  *                              match will be returned.
89  * @params:             Parameters that affect how long the search will proceed
90  *                              before going with the best that has been found
91  *                              so far.
92  *
93  * Returns the length of the match that was found.
94  */
95 static uint longest_match(const u8 window[], uint bytes_remaining,
96                           uint strstart, const u16 prev_tab[], 
97                           uint cur_match, uint prev_len, 
98                           uint *match_start_ret, 
99                           const struct lz_params *params)
100 {
101         uint chain_len = params->max_chain_len;
102
103         const u8 *scan = window + strstart;
104         const u8 *match;
105         uint len;
106         uint best_len = prev_len;
107         uint match_start = cur_match;
108
109         uint nice_match = min(params->nice_match, bytes_remaining);
110
111         const u8 *strend = scan + params->max_match;
112
113         u8 scan_end1 = scan[best_len - 1];
114         u8 scan_end = scan[best_len];
115
116
117         /* Do not waste too much time if we already have a good match: */
118         if (best_len >= params->good_match)
119                 chain_len >>= 2;
120
121         do {
122                 match = &window[cur_match];
123
124
125                 /* Skip to next match if the match length cannot increase
126                  * or if the match length is less than 2.  Note that the checks below
127                  * for insufficient lookahead only occur occasionally for performance
128                  * reasons.  Therefore uninitialized memory will be accessed, and
129                  * conditional jumps will be made that depend on those values.
130                  * However the length of the match is limited to the lookahead, so
131                  * the output of deflate is not affected by the uninitialized values.
132                  */
133
134                 if (match[best_len]   != scan_end  ||
135                         match[best_len-1] != scan_end1 ||
136                         *match                  != *scan         ||
137                         *++match                  != scan[1])     continue;
138
139                 /* The check at best_len-1 can be removed because it will be made
140                  * again later. (This heuristic is not always a win.)
141                  * It is not necessary to compare scan[2] and match[2] since they
142                  * are always equal when the other bytes match, given that
143                  * the hash keys are equal and that HASH_BITS >= 8.
144                  */
145                 scan += 2, match++;
146
147                 wimlib_assert(*scan == *match);
148
149                 /* We check for insufficient lookahead only every 8th comparison;
150                  * the 256th check will be made at strstart+258.  */
151                 do {
152                 } while (*++scan == *++match && *++scan == *++match &&
153                                  *++scan == *++match && *++scan == *++match &&
154                                  *++scan == *++match && *++scan == *++match &&
155                                  *++scan == *++match && *++scan == *++match &&
156                                  scan < strend);
157
158                 len = params->max_match - (int)(strend - scan);
159                 scan = strend - params->max_match;
160
161                 if (len > best_len) {
162                         match_start = cur_match;
163                         best_len = len;
164                         if (len >= nice_match) 
165                                 break;
166                         scan_end1  = scan[best_len - 1];
167                         scan_end   = scan[best_len];
168                 }
169                 cur_match = prev_tab[cur_match];
170         } while (--chain_len != 0 && cur_match != 0);
171         *match_start_ret = match_start;
172         return min(min(best_len, bytes_remaining), params->max_match);
173 }
174
175
176
177 /* 
178  * Determines the sequence of matches and literals that a block of data will be
179  * compressed to.
180  *
181  * @uncompressed_data:  The data that is to be compressed.
182  * @uncompressed_len:   The length of @uncompressed_data, in bytes.
183  * @match_tab:          An array for the intermediate representation of matches.
184  * @record_match:       A function that will be called to produce the
185  *                              intermediate representation of a match, given
186  *                              the offset and length.  This function should also
187  *                              update the appropriate symbol frequency counts
188  *                              so that any needed Huffman codes can be made
189  *                              later.
190  * @record_literal:     A function that will be called to produce the
191  *                              intermediate representation of a literal, given
192  *                              the character of the literal.  This function
193  *                              should also update the appropriate symbol 
194  *                              frequency counts so that any needed Huffman 
195  *                              codes can be made later.
196  * @record_match_arg_1:
197  * @record_match_arg_2: Extra arguments to be passed to @record_match.
198  * @record_literal_arg: Extra arguments to be passed to @record_literal.
199  * @params:             Structure that contains parameters that affect how the
200  *                              analysis proceeds (mainly how good the matches
201  *                              have to be).
202  *
203  * Returns the total number of matches and literal bytes that were found; this
204  * is the number of slots in @match_tab that have been filled with the
205  * intermediate representation of a match or literal byte.
206  */
207 uint lz_analyze_block(const u8 uncompressed_data[], uint uncompressed_len,
208                       u32 match_tab[], lz_record_match_t record_match,
209                       lz_record_literal_t record_literal, void *record_match_arg1,
210                       void *record_match_arg2, void *record_literal_arg,
211                       const struct lz_params *params)
212 {
213         uint cur_match_pos = 0;
214         uint cur_input_pos = 0;
215         uint hash          = 0;
216         uint hash_head     = 0;
217         uint prev_len      = params->min_match - 1;
218         uint prev_start;
219         uint match_len     = params->min_match - 1;
220         uint match_start   = 0;
221         bool match_available = false;
222         u16 hash_tab[HASH_SIZE];
223         u32 match;
224         u16 prev_tab[uncompressed_len];
225
226         ZERO_ARRAY(hash_tab);
227         ZERO_ARRAY(prev_tab);
228
229         do {
230                 /* If there are at least 3 characters remaining in the input,
231                  * insert the 3-character string beginning at
232                  * uncompressed_data[cur_input_pos] into the hash table.
233                  *
234                  * hash_head is set to the index of the previous string in the
235                  * hash bucket, or 0 if there is no such string */
236                 if (uncompressed_len - cur_input_pos >= params->min_match) {
237                         hash = insert_string(hash_tab, prev_tab, 
238                                                 uncompressed_data, 
239                                                 cur_input_pos, hash);
240                         hash_head = prev_tab[cur_input_pos];
241                 } else {
242                         hash_head = 0;
243                 }
244
245
246                 /* Find the longest match, discarding those <= prev_len. */
247                 prev_len = match_len;
248                 prev_start = match_start;
249                 match_len = params->min_match - 1;
250
251                 if (hash_head != 0 && prev_len < params->max_lazy_match) {
252                         /* To simplify the code, we prevent matches with the
253                          * string of window index 0 (in particular we have to
254                          * avoid a match of the string with itself at the start
255                          * of the input file).  */
256                         match_len = longest_match(uncompressed_data, 
257                                                 uncompressed_len - cur_input_pos,
258                                                 cur_input_pos, prev_tab, 
259                                                 hash_head, prev_len,
260                                                 &match_start, params);
261
262                         if (match_len == params->min_match && 
263                                 cur_input_pos - match_start > params->too_far) 
264                         {
265                                 match_len = params->min_match - 1;
266                         }
267                 }
268
269                 /* If there was a match at the previous step and the current
270                  * match is not better, output the previous match:
271                  */
272                 if (prev_len >= params->min_match && match_len <= prev_len) {
273
274                         /* Do not insert strings in hash table beyond this. */
275                         uint max_insert = uncompressed_len - params->min_match;
276
277                         /*DEBUG("Recording match (pos = %u, offset = %u, len = %u)\n",*/
278                                         /*cur_input_pos - 1, */
279                                         /*cur_input_pos - 1 - prev_start,*/
280                                         /*prev_len);*/
281
282                         match = (*record_match)(cur_input_pos - 1 - prev_start, 
283                                                         prev_len, 
284                                                         record_match_arg1,
285                                                         record_match_arg2);
286
287                         match_tab[cur_match_pos++] = match;
288
289                         /* Insert in hash table all strings up to the end of the match.
290                          * strstart-1 and strstart are already inserted. If there is not
291                          * enough lookahead, the last two strings are not inserted in
292                          * the hash table.
293                          */
294                         prev_len -= 2;
295
296                         do {
297                                 if (++cur_input_pos <= max_insert) {
298                                         hash = insert_string(hash_tab, prev_tab,
299                                                                 uncompressed_data,
300                                                                 cur_input_pos,
301                                                                 hash);
302                                 }
303                         } while (--prev_len != 0);
304
305                         match_available = false;
306                         match_len = params->min_match - 1;
307                 } else if (match_available) {
308                         /* If there was no match at the previous position, output a
309                          * single literal. If there was a match but the current match
310                          * is longer, truncate the previous match to a single literal.
311                          */
312
313                         /*DEBUG("Recording litrl (pos = %u, value = %u)\n",*/
314                                         /*cur_input_pos - 1, */
315                                         /*uncompressed_data[cur_input_pos - 1]);*/
316
317                         match = (*record_literal)(
318                                         uncompressed_data[cur_input_pos - 1],
319                                                         record_literal_arg);
320                         match_tab[cur_match_pos++] = match;
321                 } else {
322                         /* There is no previous match to compare with, wait for
323                          * the next step to decide.  */
324                         match_available = true;
325                 }
326         } while (++cur_input_pos < uncompressed_len);
327
328         if (match_available) {
329                 match = (*record_literal)(uncompressed_data[cur_input_pos - 1],
330                                                 record_literal_arg);
331                 match_tab[cur_match_pos++] = match;
332         }
333         return cur_match_pos;
334 }