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