/*
- * hc_matchfinder.h
+ * hc_matchfinder.h - Lempel-Ziv matchfinding with a hash table of linked lists
*
- * Author: Eric Biggers
- * Year: 2014, 2015
+ * The following copying information applies to this specific source code file:
*
- * The author dedicates this file to the public domain.
- * You can do whatever you want with this file.
+ * Written in 2014-2015 by Eric Biggers <ebiggers3@gmail.com>
+ *
+ * To the extent possible under law, the author(s) have dedicated all copyright
+ * and related and neighboring rights to this software to the public domain
+ * worldwide via the Creative Commons Zero 1.0 Universal Public Domain
+ * Dedication (the "CC0").
+ *
+ * This software is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the CC0 for more details.
+ *
+ * You should have received a copy of the CC0 along with this software; if not
+ * see <http://creativecommons.org/publicdomain/zero/1.0/>.
*
* ---------------------------------------------------------------------------
*
*
* Notes on usage
*
- * You must define MATCHFINDER_MAX_WINDOW_ORDER before including this header
- * because that determines which integer type to use for positions. Since
- * 16-bit integers are faster than 32-bit integers due to reduced memory usage
- * (and therefore reduced cache pressure), the code only uses 32-bit integers if
- * they are needed to represent all possible positions.
+ * Before including this header, you must define 'mf_pos_t' to an integer type
+ * that can represent all possible positions. This can be a 16-bit or 32-bit
+ * unsigned integer. When possible, the former should be used due to the
+ * reduced cache pressure. This header can be included multiple times in a
+ * single .c file with different 'mf_pos_t' definitions; however, you must
+ * define a different MF_SUFFIX each time to generate different names for the
+ * matchfinder structure and functions.
*
* The number of bytes that must be allocated for a given 'struct
* hc_matchfinder' must be gotten by calling hc_matchfinder_size().
* ----------------------------------------------------------------------------
*/
-#ifndef _HC_MATCHFINDER_H
-#define _HC_MATCHFINDER_H
-
-#ifndef MATCHFINDER_MAX_WINDOW_ORDER
-# error "MATCHFINDER_MAX_WINDOW_ORDER must be defined!"
-#endif
-
#include <string.h>
#include "wimlib/lz_extend.h"
#include "wimlib/lz_hash.h"
#include "wimlib/unaligned.h"
-#if MATCHFINDER_MAX_WINDOW_ORDER <= 16
-typedef u16 pos_t;
-#else
-typedef u32 pos_t;
-#endif
-
#define HC_MATCHFINDER_HASH3_ORDER 14
#define HC_MATCHFINDER_HASH4_ORDER 15
-struct hc_matchfinder {
+/* TEMPLATED functions and structures have MF_SUFFIX appended to their name. */
+#undef TEMPLATED
+#define TEMPLATED(name) CONCAT(name, MF_SUFFIX)
+
+struct TEMPLATED(hc_matchfinder) {
/* The hash table for finding length 3 matches */
- pos_t hash3_tab[1UL << HC_MATCHFINDER_HASH3_ORDER];
+ mf_pos_t hash3_tab[1UL << HC_MATCHFINDER_HASH3_ORDER];
/* The hash table which contains the first nodes of the linked lists for
* finding length 4+ matches */
- pos_t hash4_tab[1UL << HC_MATCHFINDER_HASH4_ORDER];
+ mf_pos_t hash4_tab[1UL << HC_MATCHFINDER_HASH4_ORDER];
/* The "next node" references for the linked lists. The "next node" of
* the node for the sequence with position 'pos' is 'next_tab[pos]'. */
- pos_t next_tab[];
+ mf_pos_t next_tab[];
};
/* Return the number of bytes that must be allocated for a 'hc_matchfinder' that
* can work with buffers up to the specified size. */
-static inline size_t
-hc_matchfinder_size(size_t max_bufsize)
+static forceinline size_t
+TEMPLATED(hc_matchfinder_size)(size_t max_bufsize)
{
- return sizeof(struct hc_matchfinder) + (max_bufsize * sizeof(pos_t));
+ return sizeof(struct TEMPLATED(hc_matchfinder)) +
+ (max_bufsize * sizeof(mf_pos_t));
}
/* Prepare the matchfinder for a new input buffer. */
-static inline void
-hc_matchfinder_init(struct hc_matchfinder *mf)
+static forceinline void
+TEMPLATED(hc_matchfinder_init)(struct TEMPLATED(hc_matchfinder) *mf)
{
memset(mf, 0, sizeof(*mf));
}
* Return the length of the match found, or 'best_len' if no match longer than
* 'best_len' was found.
*/
-static inline u32
-hc_matchfinder_longest_match(struct hc_matchfinder * const restrict mf,
- const u8 * const restrict in_begin,
- const ptrdiff_t cur_pos,
- u32 best_len,
- const u32 max_len,
- const u32 nice_len,
- const u32 max_search_depth,
- u32 next_hashes[const restrict static 2],
- u32 * const restrict offset_ret)
+static forceinline u32
+TEMPLATED(hc_matchfinder_longest_match)(struct TEMPLATED(hc_matchfinder) * const restrict mf,
+ const u8 * const restrict in_begin,
+ const ptrdiff_t cur_pos,
+ u32 best_len,
+ const u32 max_len,
+ const u32 nice_len,
+ const u32 max_search_depth,
+ u32 next_hashes[const restrict static 2],
+ u32 * const restrict offset_ret)
{
const u8 *in_next = in_begin + cur_pos;
u32 depth_remaining = max_search_depth;
const u8 *best_matchptr = best_matchptr; /* uninitialized */
- pos_t cur_node3, cur_node4;
+ mf_pos_t cur_node3, cur_node4;
u32 hash3, hash4;
u32 next_seq3, next_seq4;
u32 seq4;
*
* Returns @in_next + @count.
*/
-static inline const u8 *
-hc_matchfinder_skip_positions(struct hc_matchfinder * const restrict mf,
- const u8 * const restrict in_begin,
- const ptrdiff_t cur_pos,
- const ptrdiff_t end_pos,
- const u32 count,
- u32 next_hashes[const restrict static 2])
+static forceinline const u8 *
+TEMPLATED(hc_matchfinder_skip_positions)(struct TEMPLATED(hc_matchfinder) * const restrict mf,
+ const u8 * const restrict in_begin,
+ const ptrdiff_t cur_pos,
+ const ptrdiff_t end_pos,
+ const u32 count,
+ u32 next_hashes[const restrict static 2])
{
const u8 *in_next = in_begin + cur_pos;
const u8 * const stop_ptr = in_next + count;
return stop_ptr;
}
-
-#endif /* _HC_MATCHFINDER_H */
git://wimlib.net / wimlib / blobdiff