/*
- * 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
*
- * Before including this header, you must define 'pos_t' to an integer type that
- * can represent all possible positions. This can be a 16-bit or 32-bit
+ * 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 'pos_t' definitions; however, you must define a
- * different MF_SUFFIX each time to generate different names for the matchfinder
- * structure and functions.
+ * 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().
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
+static forceinline size_t
TEMPLATED(hc_matchfinder_size)(size_t max_bufsize)
{
return sizeof(struct TEMPLATED(hc_matchfinder)) +
- (max_bufsize * sizeof(pos_t));
+ (max_bufsize * sizeof(mf_pos_t));
}
/* Prepare the matchfinder for a new input buffer. */
-static inline void
+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
+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,
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 *
+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,