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                 u32 len;
 184
 185                 if (matchptr[best_len] != strptr[best_len] ||
 186                     matchptr[best_len - 1] != strptr[best_len - 1] ||
 187                     matchptr[0] != strptr[0])
 188                         goto next_match;
 189
 190                 for (len = 1; len < best_len - 1; len++)
 191                         if (matchptr[len] != strptr[len])
 192                                 goto next_match;
 193
 194                 len = best_len;
 195
 196                 while (++len != max_len)
 197                         if (matchptr[len] != strptr[len])
 198                                 break;
 199
 200                 matches[num_matches++] = (struct lz_match) {
 201                         .len = len,
 202                         .offset = strptr - matchptr,
 203                 };
 204                 best_len = len;
 205                 if (best_len == max_len)
 206                         break;
 207         next_match:
 208                 ;
 209         }
 210         return num_matches;
 211 }
 212
 213 static u32
 214 lz_hc_get_matches(struct lz_mf *_mf, struct lz_match matches[])
 215 {
 216         struct lz_hc *mf = (struct lz_hc *)_mf;
 217         const u32 bytes_remaining = lz_mf_get_bytes_remaining(&mf->base);
 218         u32 hash;
 219         u32 cur_match;
 220         u32 num_matches = 0;
 221
 222         if (bytes_remaining <= LZ_HC_HASH_BYTES)
 223                 goto out;
 224
 225         hash = mf->next_hash;
 226         mf->next_hash = lz_hc_hash(lz_mf_get_window_ptr(&mf->base) + 1);
 227         prefetch(&mf->hash_tab[mf->next_hash]);
 228         cur_match = mf->hash_tab[hash];
 229         mf->hash_tab[hash] = mf->base.cur_window_pos;
 230         mf->prev_tab[mf->base.cur_window_pos] = cur_match;
 231
 232         num_matches = do_search(mf->base.cur_window,
 233                                 mf->base.cur_window_pos,
 234                                 mf->prev_tab,
 235                                 cur_match,
 236                                 mf->base.params.min_match_len,
 237                                 min(bytes_remaining, mf->base.params.nice_match_len),
 238                                 mf->base.params.max_search_depth,
 239                                 matches);
 240
 241         /* If the longest match is @nice_match_len in length, it may have been
 242          * truncated.  Try extending it up to the maximum match length.  */
 243         if (num_matches != 0 &&
 244             matches[num_matches - 1].len == mf->base.params.nice_match_len)
 245         {
 246                 const u8 * const strptr = lz_mf_get_window_ptr(&mf->base);
 247                 const u8 * const matchptr = strptr - matches[num_matches - 1].offset;
 248                 const u32 len_limit = min(bytes_remaining, mf->base.params.max_match_len);
 249                 u32 len;
 250
 251                 len = matches[num_matches - 1].len;
 252                 while (len < len_limit && strptr[len] == matchptr[len])
 253                         len++;
 254                 matches[num_matches - 1].len = len;
 255         }
 256
 257 out:
 258         mf->base.cur_window_pos++;
 259         return num_matches;
 260 }
 261
 262 static void
 263 lz_hc_skip_position(struct lz_hc *mf)
 264 {
 265         const u32 bytes_remaining = lz_mf_get_bytes_remaining(&mf->base);
 266         u32 hash;
 267
 268         if (bytes_remaining <= LZ_HC_HASH_BYTES)
 269                 goto out;
 270
 271         hash = mf->next_hash;
 272         mf->next_hash = lz_hc_hash(lz_mf_get_window_ptr(&mf->base) + 1);
 273         prefetch(&mf->hash_tab[mf->next_hash]);
 274         mf->prev_tab[mf->base.cur_window_pos] = mf->hash_tab[hash];
 275         mf->hash_tab[hash] = mf->base.cur_window_pos;
 276
 277 out:
 278         mf->base.cur_window_pos++;
 279 }
 280
 281 static void
 282 lz_hc_skip_positions(struct lz_mf *_mf, u32 n)
 283 {
 284         struct lz_hc *mf = (struct lz_hc *)_mf;
 285
 286         do {
 287                 lz_hc_skip_position(mf);
 288         } while (--n);
 289 }
 290
 291 static void
 292 lz_hc_destroy(struct lz_mf *_mf)
 293 {
 294         struct lz_hc *mf = (struct lz_hc *)_mf;
 295
 296         FREE(mf->hash_tab);
 297 }
 298
 299 const struct lz_mf_ops lz_hash_chains_ops = {
 300         .params_valid      = lz_hc_params_valid,
 301         .get_needed_memory = lz_hc_get_needed_memory,
 302         .init              = lz_hc_init,
 303         .load_window       = lz_hc_load_window,
 304         .get_matches       = lz_hc_get_matches,
 305         .skip_positions    = lz_hc_skip_positions,
 306         .destroy           = lz_hc_destroy,
 307         .struct_size       = sizeof(struct lz_hc),
 308 };