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