wimlib.net Git - wimlib/blob - src/lz_hash_chains.c

   1 /*
   2  * lz_hash_chains.c
   3  *
   4  * Hash chain match-finder for Lempel-Ziv compression.
   5  *
   6  * Copyright (c) 2014 Eric Biggers.  All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  *
  12  * 1. Redistributions of source code must retain the above copyright
  13  *    notice, this list of conditions and the following disclaimer.
  14  *
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS "AS IS" AND
  20  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  22  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE
  23  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  24  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  25  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
  26  * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
  27  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
  28  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  29  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  30  */
  31
  32 #ifdef HAVE_CONFIG_H
  33 #  include "config.h"
  34 #endif
  35
  36 #include "wimlib/lz_mf.h"
  37 #include "wimlib/util.h"
  38 #include <pthread.h>
  39 #include <string.h>
  40
  41 /* Number of hash buckets.  This can be changed, but should be a power of 2 so
  42  * that the correct hash bucket can be selected using a fast bitwise AND.  */
  43 #define LZ_HC_HASH_LEN     (1 << 15)
  44
  45 /* Number of bytes from which the hash code is computed at each position.  This
  46  * can be changed, provided that lz_hc_hash() is updated as well.  */
  47 #define LZ_HC_HASH_BYTES   3
  48
  49 struct lz_hc {
  50         struct lz_mf base;
  51         u32 *hash_tab;
  52         u32 *prev_tab;
  53         u32 next_hash;
  54 };
  55
  56 static u32 crc32_table[256];
  57 static pthread_once_t crc32_table_filled = PTHREAD_ONCE_INIT;
  58
  59 static void
  60 crc32_init(void)
  61 {
  62         for (u32 b = 0; b < 256; b++) {
  63                 u32 r = b;
  64                 for (int i = 0; i < 8; i++) {
  65                         if (r & 1)
  66                                 r = (r >> 1) ^ 0xEDB88320;
  67                         else
  68                                 r >>= 1;
  69                 }
  70                 crc32_table[b] = r;
  71         }
  72 }
  73
  74 /* This hash function is taken from the LZMA SDK.  It seems to work well.
  75  *
  76  * TODO: Maybe use the SSE4.2 CRC32 instruction when available?  */
  77 static inline u32
  78 lz_hc_hash(const u8 *p)
  79 {
  80         u32 hash = 0;
  81
  82         hash ^= crc32_table[p[0]];
  83         hash ^= p[1];
  84         hash ^= (u32)p[2] << 8;
  85
  86         return hash % LZ_HC_HASH_LEN;
  87 }
  88
  89 static void
  90 lz_hc_set_default_params(struct lz_mf_params *params)
  91 {
  92         if (params->min_match_len < LZ_HC_HASH_BYTES)
  93                 params->min_match_len = LZ_HC_HASH_BYTES;
  94
  95         if (params->max_match_len == 0)
  96                 params->max_match_len = params->max_window_size;
  97
  98         if (params->max_search_depth == 0)
  99                 params->max_search_depth = 50;
 100
 101         if (params->nice_match_len == 0)
 102                 params->nice_match_len = 24;
 103
 104         if (params->nice_match_len < params->min_match_len)
 105                 params->nice_match_len = params->min_match_len;
 106
 107         if (params->nice_match_len > params->max_match_len)
 108                 params->nice_match_len = params->max_match_len;
 109 }
 110
 111 static bool
 112 lz_hc_params_valid(const struct lz_mf_params *_params)
 113 {
 114         struct lz_mf_params params = *_params;
 115
 116         lz_hc_set_default_params(&params);
 117
 118         /* Avoid edge case where min_match_len = 3, max_match_len = 2 */
 119         return (params.min_match_len <= params.max_match_len);
 120 }
 121
 122 static u64
 123 lz_hc_get_needed_memory(u32 max_window_size)
 124 {
 125         u64 len = 0;
 126
 127         len += LZ_HC_HASH_LEN;
 128         len += max_window_size;
 129
 130         return len * sizeof(u32);
 131 }
 132
 133 static bool
 134 lz_hc_init(struct lz_mf *_mf)
 135 {
 136         struct lz_hc *mf = (struct lz_hc *)_mf;
 137
 138         lz_hc_set_default_params(&mf->base.params);
 139
 140         /* Allocate space for 'hash_tab' and 'prev_tab'.  */
 141
 142         mf->hash_tab = MALLOC(lz_hc_get_needed_memory(mf->base.params.max_window_size));
 143         if (!mf->hash_tab)
 144                 return false;
 145
 146         mf->prev_tab = mf->hash_tab + LZ_HC_HASH_LEN;
 147
 148         /* Fill in the CRC32 table if not done already.  */
 149         pthread_once(&crc32_table_filled, crc32_init);
 150
 151         return true;
 152 }
 153
 154 static void
 155 lz_hc_load_window(struct lz_mf *_mf, const u8 window[], u32 size)
 156 {
 157         struct lz_hc *mf = (struct lz_hc *)_mf;
 158
 159         memset(mf->hash_tab, 0, LZ_HC_HASH_LEN * sizeof(u32));
 160
 161         if (size >= LZ_HC_HASH_BYTES)
 162                 mf->next_hash = lz_hc_hash(window);
 163 }
 164
 165 static inline u32
 166 do_search(const u8 * restrict window,
 167           const u32 cur_window_pos,
 168           u32 prev_tab[restrict],
 169           u32 cur_match,
 170           const u32 min_len,
 171           const u32 max_len,
 172           const u32 max_search_depth,
 173           struct lz_match matches[restrict])
 174 {
 175         const u8 * const strptr = &window[cur_window_pos];
 176         u32 best_len = min_len - 1;
 177         u32 depth_remaining = max_search_depth;
 178         u32 num_matches = 0;
 179
 180         for (; cur_match && depth_remaining--; cur_match = prev_tab[cur_match]) {
 181
 182                 const u8 * const matchptr = &window[cur_match];
 183
 184                 if (matchptr[best_len] == strptr[best_len] &&
 185                     matchptr[best_len - 1] == strptr[best_len - 1] &&
 186                     matchptr[0] == strptr[0])
 187                 {
 188                         u32 len = 0;
 189
 190                         while (++len != max_len)
 191                                 if (matchptr[len] != strptr[len])
 192                                         break;
 193
 194                         if (len > best_len) {
 195                                 matches[num_matches++] = (struct lz_match) {
 196                                         .len = len,
 197                                         .offset = strptr - matchptr,
 198                                 };
 199                                 best_len = len;
 200                                 if (best_len == max_len)
 201                                         break;
 202                         }
 203                 }
 204         }
 205         return num_matches;
 206 }
 207
 208 static u32
 209 lz_hc_get_matches(struct lz_mf *_mf, struct lz_match matches[])
 210 {
 211         struct lz_hc *mf = (struct lz_hc *)_mf;
 212         const u32 bytes_remaining = lz_mf_get_bytes_remaining(&mf->base);
 213         u32 hash;
 214         u32 cur_match;
 215         u32 num_matches = 0;
 216
 217         if (bytes_remaining <= LZ_HC_HASH_BYTES)
 218                 goto out;
 219
 220         hash = mf->next_hash;
 221         mf->next_hash = lz_hc_hash(lz_mf_get_window_ptr(&mf->base) + 1);
 222         prefetch(&mf->hash_tab[mf->next_hash]);
 223         cur_match = mf->hash_tab[hash];
 224         mf->hash_tab[hash] = mf->base.cur_window_pos;
 225         mf->prev_tab[mf->base.cur_window_pos] = cur_match;
 226
 227         num_matches = do_search(mf->base.cur_window,
 228                                 mf->base.cur_window_pos,
 229                                 mf->prev_tab,
 230                                 cur_match,
 231                                 mf->base.params.min_match_len,
 232                                 min(bytes_remaining, mf->base.params.nice_match_len),
 233                                 mf->base.params.max_search_depth,
 234                                 matches);
 235
 236         /* If the longest match is @nice_match_len in length, it may have been
 237          * truncated.  Try extending it up to the maximum match length.  */
 238         if (num_matches != 0 &&
 239             matches[num_matches - 1].len == mf->base.params.nice_match_len)
 240         {
 241                 const u8 * const strptr = lz_mf_get_window_ptr(&mf->base);
 242                 const u8 * const matchptr = strptr - matches[num_matches - 1].offset;
 243                 const u32 len_limit = min(bytes_remaining, mf->base.params.max_match_len);
 244                 u32 len;
 245
 246                 len = matches[num_matches - 1].len;
 247                 while (len < len_limit && strptr[len] == matchptr[len])
 248                         len++;
 249                 matches[num_matches - 1].len = len;
 250         }
 251
 252 out:
 253         mf->base.cur_window_pos++;
 254         return num_matches;
 255 }
 256
 257 static void
 258 lz_hc_skip_position(struct lz_hc *mf)
 259 {
 260         const u32 bytes_remaining = lz_mf_get_bytes_remaining(&mf->base);
 261         u32 hash;
 262
 263         if (bytes_remaining <= LZ_HC_HASH_BYTES)
 264                 goto out;
 265
 266         hash = mf->next_hash;
 267         mf->next_hash = lz_hc_hash(lz_mf_get_window_ptr(&mf->base) + 1);
 268         prefetch(&mf->hash_tab[mf->next_hash]);
 269         mf->prev_tab[mf->base.cur_window_pos] = mf->hash_tab[hash];
 270         mf->hash_tab[hash] = mf->base.cur_window_pos;
 271
 272 out:
 273         mf->base.cur_window_pos++;
 274 }
 275
 276 static void
 277 lz_hc_skip_positions(struct lz_mf *_mf, u32 n)
 278 {
 279         struct lz_hc *mf = (struct lz_hc *)_mf;
 280
 281         do {
 282                 lz_hc_skip_position(mf);
 283         } while (--n);
 284 }
 285
 286 static void
 287 lz_hc_destroy(struct lz_mf *_mf)
 288 {
 289         struct lz_hc *mf = (struct lz_hc *)_mf;
 290
 291         FREE(mf->hash_tab);
 292 }
 293
 294 const struct lz_mf_ops lz_hash_chains_ops = {
 295         .params_valid      = lz_hc_params_valid,
 296         .get_needed_memory = lz_hc_get_needed_memory,
 297         .init              = lz_hc_init,
 298         .load_window       = lz_hc_load_window,
 299         .get_matches       = lz_hc_get_matches,
 300         .skip_positions    = lz_hc_skip_positions,
 301         .destroy           = lz_hc_destroy,
 302         .struct_size       = sizeof(struct lz_hc),
 303 };