X-Git-Url: https://wimlib.net/git/?a=blobdiff_plain;f=include%2Fwimlib%2Fmatchfinder_common.h;h=2372bd66a04216bcf62e8077d793f04614c4304a;hb=eea89b54f1000f00961a7154e526484c53479030;hp=66a966a36655ccc8091c0ed3816246d804f2acf4;hpb=226a6dfe2909e054568298196785c944a1b5c4fa;p=wimlib diff --git a/include/wimlib/matchfinder_common.h b/include/wimlib/matchfinder_common.h index 66a966a3..2372bd66 100644 --- a/include/wimlib/matchfinder_common.h +++ b/include/wimlib/matchfinder_common.h @@ -3,53 +3,56 @@ * * Common code for Lempel-Ziv matchfinding. * - * Copyright (c) 2014 Eric Biggers. All rights reserved. + * Author: Eric Biggers + * Year: 2014, 2015 * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * - * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS "AS IS" AND - * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR - * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE - * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR - * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF - * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR - * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, - * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR - * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF - * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + * The author dedicates this file to the public domain. + * You can do whatever you want with this file. */ #ifndef _MATCHFINDER_COMMON_H #define _MATCHFINDER_COMMON_H -#include "wimlib/types.h" - #include -#ifndef MATCHFINDER_WINDOW_ORDER -# error "MATCHFINDER_WINDOW_ORDER must be defined!" +#include "wimlib/types.h" + +#ifndef MATCHFINDER_MAX_WINDOW_ORDER +# error "MATCHFINDER_MAX_WINDOW_ORDER must be defined!" #endif -#ifndef MATCHFINDER_IS_SLIDING -# error "MATCHFINDER_IS_SLIDING must be defined!" +#if MATCHFINDER_MAX_WINDOW_ORDER <= 16 +typedef u16 pos_t; +#else +typedef u32 pos_t; #endif -#define MATCHFINDER_WINDOW_SIZE ((size_t)1 << MATCHFINDER_WINDOW_ORDER) +#if MATCHFINDER_MAX_WINDOW_ORDER != 16 && MATCHFINDER_MAX_WINDOW_ORDER != 32 + +/* Not all the bits of the position type are needed, so the sign bit can be + * reserved to mean "out of bounds". */ +#define MATCHFINDER_NULL ((pos_t)-1) + +static inline bool +matchfinder_node_valid(pos_t node) +{ + return !(node & ((pos_t)1 << (sizeof(pos_t) * 8 - 1))); +} -#if MATCHFINDER_IS_SLIDING -# include "matchfinder_sliding.h" #else -# include "matchfinder_nonsliding.h" + +/* All bits of the position type are needed, so use 0 to mean "out of bounds". + * This prevents the beginning of the buffer from matching anything; however, + * this doesn't matter much. */ + +#define MATCHFINDER_NULL ((pos_t)0) + +static inline bool +matchfinder_node_valid(pos_t node) +{ + return node != 0; +} + #endif #define MATCHFINDER_ALIGNMENT 8 @@ -86,7 +89,7 @@ static inline bool matchfinder_memset_init_okay(void) { /* All bytes must match in order to use memset. */ - const pos_t v = MATCHFINDER_INITVAL; + const pos_t v = MATCHFINDER_NULL; if (sizeof(pos_t) == 2) return (u8)v == (u8)(v >> 8); if (sizeof(pos_t) == 4) @@ -119,73 +122,12 @@ matchfinder_init(pos_t *data, size_t num_entries) #endif if (matchfinder_memset_init_okay()) { - memset(data, (u8)MATCHFINDER_INITVAL, size); + memset(data, (u8)MATCHFINDER_NULL, size); return; } for (size_t i = 0; i < num_entries; i++) - data[i] = MATCHFINDER_INITVAL; -} - -#if MATCHFINDER_IS_SLIDING -/* - * Slide the matchfinder by WINDOW_SIZE bytes. - * - * This must be called just after each WINDOW_SIZE bytes have been run through - * the matchfinder. - * - * This will subtract WINDOW_SIZE bytes from each entry in the array specified. - * The effect is that all entries are updated to be relative to the current - * position, rather than the position WINDOW_SIZE bytes prior. - * - * Underflow is detected and replaced with signed saturation. This ensures that - * once the sliding window has passed over a position, that position forever - * remains out of bounds. - * - * The array passed in must contain all matchfinder data that is - * position-relative. Concretely, this will include the hash table as well as - * the table of positions that is used to link together the sequences in each - * hash bucket. Note that in the latter table, the links are 1-ary in the case - * of "hash chains", and 2-ary in the case of "binary trees". In either case, - * the links need to be rebased in the same way. - */ -static inline void -matchfinder_rebase(pos_t *data, size_t num_entries) -{ - const size_t size = num_entries * sizeof(data[0]); - -#ifdef __AVX2__ - if (matchfinder_rebase_avx2(data, size)) - return; -#endif - -#ifdef __SSE2__ - if (matchfinder_rebase_sse2(data, size)) - return; -#endif - - if (MATCHFINDER_WINDOW_SIZE == 32768) { - /* Branchless version for 32768 byte windows. If the value was - * already negative, clear all bits except the sign bit; this - * changes the value to -32768. Otherwise, set the sign bit; - * this is equivalent to subtracting 32768. */ - for (size_t i = 0; i < num_entries; i++) { - u16 v = data[i]; - u16 sign_bit = v & 0x8000; - v &= sign_bit - ((sign_bit >> 15) ^ 1); - v |= 0x8000; - data[i] = v; - } - return; - } - - for (size_t i = 0; i < num_entries; i++) { - if (data[i] >= 0) - data[i] -= (pos_t)-MATCHFINDER_WINDOW_SIZE; - else - data[i] = (pos_t)-MATCHFINDER_WINDOW_SIZE; - } + data[i] = MATCHFINDER_NULL; } -#endif /* MATCHFINDER_IS_SLIDING */ #endif /* _MATCHFINDER_COMMON_H */