1 /*
2 Lizard - Fast LZ compression algorithm
3 Copyright (C) 2011-2015, Yann Collet
4 Copyright (C) 2016-2017, Przemyslaw Skibinski <inikep@gmail.com>
5
6 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
7
8 Redistribution and use in source and binary forms, with or without
9 modification, are permitted provided that the following conditions are
10 met:
11
12 * Redistributions of source code must retain the above copyright
13 notice, this list of conditions and the following disclaimer.
14 * Redistributions in binary form must reproduce the above
15 copyright notice, this list of conditions and the following disclaimer
16 in the documentation and/or other materials provided with the
17 distribution.
18
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30
31 You can contact the author at :
32 - Lizard source repository : https://github.com/inikep/lizard
33 */
34
35 #ifndef LIZARD_COMMON_H_2983
36 #define LIZARD_COMMON_H_2983
37
38 #if defined (__cplusplus)
39 extern "C" {
40 #endif
41
42
43 /*-************************************
44 * Memory routines
45 **************************************/
46 #include <stdlib.h> /* malloc, calloc, free */
47 #include <string.h> /* memset, memcpy */
48 #include <stdint.h> /* intptr_t */
49 #include "entropy/mem.h"
50 #include "lizard_compress.h" /* LIZARD_GCC_VERSION */
51
52 //#define LIZARD_USE_LOGS
53 #define LIZARD_LOG_COMPRESS(...) //printf(__VA_ARGS__)
54 #define LIZARD_LOG_DECOMPRESS(...) //printf(__VA_ARGS__)
55
56 #define LIZARD_LOG_COMPRESS_LZ4(...) //printf(__VA_ARGS__)
57 #define COMPLOG_CODEWORDS_LZ4(...) //printf(__VA_ARGS__)
58 #define LIZARD_LOG_DECOMPRESS_LZ4(...) //printf(__VA_ARGS__)
59 #define DECOMPLOG_CODEWORDS_LZ4(...) //printf(__VA_ARGS__)
60
61 #define LIZARD_LOG_COMPRESS_LIZv1(...) //printf(__VA_ARGS__)
62 #define COMPLOG_CODEWORDS_LIZv1(...) //printf(__VA_ARGS__)
63 #define LIZARD_LOG_DECOMPRESS_LIZv1(...) //printf(__VA_ARGS__)
64 #define DECOMPLOG_CODEWORDS_LIZv1(...) //printf(__VA_ARGS__)
65
66
67
68
69 /*-************************************
70 * Common Constants
71 **************************************/
72 #define MINMATCH 4
73 //#define USE_LZ4_ONLY
74 //#define LIZARD_USE_TEST
75
76 #define LIZARD_DICT_SIZE (1<<24)
77 #define WILDCOPYLENGTH 16
78 #define LASTLITERALS WILDCOPYLENGTH
79 #define MFLIMIT (WILDCOPYLENGTH+MINMATCH)
80
81 #define LIZARD_MAX_PRICE (1<<28)
82 #define LIZARD_INIT_LAST_OFFSET 0
83 #define LIZARD_MAX_16BIT_OFFSET (1<<16)
84 #define MM_LONGOFF 16
85 #define LIZARD_BLOCK_SIZE_PAD (LIZARD_BLOCK_SIZE+32)
86 #define LIZARD_COMPRESS_ADD_BUF (5*LIZARD_BLOCK_SIZE_PAD)
87 #ifndef LIZARD_NO_HUFFMAN
88 #define LIZARD_COMPRESS_ADD_HUF HUF_compressBound(LIZARD_BLOCK_SIZE_PAD)
89 #define LIZARD_HUF_BLOCK_SIZE LIZARD_BLOCK_SIZE
90 #else
91 #define LIZARD_COMPRESS_ADD_HUF 0
92 #define LIZARD_HUF_BLOCK_SIZE 1
93 #endif
94
95 /* LZ4 codewords */
96 #define ML_BITS_LZ4 4
97 #define ML_MASK_LZ4 ((1U<<ML_BITS_LZ4)-1)
98 #define RUN_BITS_LZ4 (8-ML_BITS_LZ4)
99 #define RUN_MASK_LZ4 ((1U<<RUN_BITS_LZ4)-1)
100
101 /* LIZv1 codewords */
102 #define ML_BITS_LIZv1 4
103 #define RUN_BITS_LIZv1 3
104 #define ML_RUN_BITS (ML_BITS_LIZv1 + RUN_BITS_LIZv1)
105 #define MAX_SHORT_LITLEN 7
106 #define MAX_SHORT_MATCHLEN 15
107 #define LIZARD_LAST_LONG_OFF 31
108
109 /* header byte */
110 #define LIZARD_FLAG_LITERALS 1
111 #define LIZARD_FLAG_FLAGS 2
112 #define LIZARD_FLAG_OFFSET16 4
113 #define LIZARD_FLAG_OFFSET24 8
114 #define LIZARD_FLAG_LEN 16
115 #define LIZARD_FLAG_UNCOMPRESSED 128
116
117 /* stream numbers */
118 #define LIZARD_STREAM_LITERALS 0
119 #define LIZARD_STREAM_FLAGS 1
120 #define LIZARD_STREAM_OFFSET16 2
121 #define LIZARD_STREAM_OFFSET24 3
122 #define LIZARD_STREAM_LEN 4
123 #define LIZARD_STREAM_UNCOMPRESSED 5
124
125
126
127
128 typedef enum { Lizard_parser_fastSmall, Lizard_parser_fast, Lizard_parser_fastBig, Lizard_parser_noChain, Lizard_parser_hashChain, Lizard_parser_priceFast, Lizard_parser_lowestPrice, Lizard_parser_optimalPrice, Lizard_parser_optimalPriceBT } Lizard_parser_type; /* from faster to stronger */
129 typedef enum { Lizard_coderwords_LZ4, Lizard_coderwords_LIZv1 } Lizard_decompress_type;
130 typedef struct
131 {
132 U32 windowLog; /* largest match distance : impact decompression buffer size */
133 U32 contentLog; /* full search segment : larger == more compression, slower, more memory (useless for fast) */
134 U32 hashLog; /* dispatch table : larger == more memory, faster*/
135 U32 hashLog3; /* dispatch table : larger == more memory, faster*/
136 U32 searchNum; /* nb of searches : larger == more compression, slower*/
137 U32 searchLength; /* size of matches : larger == faster decompression */
138 U32 minMatchLongOff; /* min match size with offsets >= 1<<16 */
139 U32 sufficientLength; /* used only by optimal parser: size of matches which is acceptable: larger == more compression, slower */
140 U32 fullSearch; /* used only by optimal parser: perform full search of matches: 1 == more compression, slower */
141 Lizard_parser_type parserType;
142 Lizard_decompress_type decompressType;
143 } Lizard_parameters;
144
145
146 struct Lizard_stream_s
147 {
148 const BYTE* end; /* next block here to continue on current prefix */
149 const BYTE* base; /* All index relative to this position */
150 const BYTE* dictBase; /* alternate base for extDict */
151 U32 dictLimit; /* below that point, need extDict */
152 U32 lowLimit; /* below that point, no more dict */
153 U32 nextToUpdate; /* index from which to continue dictionary update */
154 U32 allocatedMemory;
155 int compressionLevel;
156 Lizard_parameters params;
157 U32 hashTableSize;
158 U32 chainTableSize;
159 U32* chainTable;
160 U32* hashTable;
161 int last_off;
162 const BYTE* off24pos;
163 U32 huffType;
164 U32 comprStreamLen;
165
166 BYTE* huffBase;
167 BYTE* huffEnd;
168 BYTE* offset16Base;
169 BYTE* offset24Base;
170 BYTE* lenBase;
171 BYTE* literalsBase;
172 BYTE* flagsBase;
173 BYTE* offset16Ptr;
174 BYTE* offset24Ptr;
175 BYTE* lenPtr;
176 BYTE* literalsPtr;
177 BYTE* flagsPtr;
178 BYTE* offset16End;
179 BYTE* offset24End;
180 BYTE* lenEnd;
181 BYTE* literalsEnd;
182 BYTE* flagsEnd;
183 U32 flagFreq[256];
184 U32 litFreq[256];
185 U32 litSum, flagSum;
186 U32 litPriceSum, log2LitSum, log2FlagSum;
187 U32 cachedPrice;
188 U32 cachedLitLength;
189 const BYTE* cachedLiterals;
190 const BYTE* diffBase;
191 const BYTE* srcBase;
192 const BYTE* destBase;
193 };
194
195 struct Lizard_dstream_s
196 {
197 const BYTE* offset16Ptr;
198 const BYTE* offset24Ptr;
199 const BYTE* lenPtr;
200 const BYTE* literalsPtr;
201 const BYTE* flagsPtr;
202 const BYTE* offset16End;
203 const BYTE* offset24End;
204 const BYTE* lenEnd;
205 const BYTE* literalsEnd;
206 const BYTE* flagsEnd;
207 const BYTE* diffBase;
208 intptr_t last_off;
209 };
210
211 typedef struct Lizard_dstream_s Lizard_dstream_t;
212
213 /* *************************************
214 * HC Pre-defined compression levels
215 ***************************************/
216 #define LIZARD_WINDOWLOG_LZ4 16
217 #define LIZARD_CHAINLOG_LZ4 LIZARD_WINDOWLOG_LZ4
218 #define LIZARD_HASHLOG_LZ4 18
219 #define LIZARD_HASHLOG_LZ4SM 12
220
221 #define LIZARD_WINDOWLOG_LIZv1 22
222 #define LIZARD_CHAINLOG_LIZv1 LIZARD_WINDOWLOG_LIZv1
223 #define LIZARD_HASHLOG_LIZv1 18
224
225
226
227 static const Lizard_parameters Lizard_defaultParameters[LIZARD_MAX_CLEVEL+1-LIZARD_MIN_CLEVEL] =
228 {
229 /* windLog, contentLog, HashLog, H3, Snum, SL, MMLongOff, SuffL, FS, Parser function, Decompressor type */
230 { LIZARD_WINDOWLOG_LZ4, 0, LIZARD_HASHLOG_LZ4SM, 0, 0, 0, 0, 0, 0, Lizard_parser_fastSmall, Lizard_coderwords_LZ4 }, // level 10
231 { LIZARD_WINDOWLOG_LZ4, 0, LIZARD_HASHLOG_LZ4, 0, 0, 0, 0, 0, 0, Lizard_parser_fast, Lizard_coderwords_LZ4 }, // level 11
232 { LIZARD_WINDOWLOG_LZ4, 0, LIZARD_HASHLOG_LZ4, 0, 0, 0, 0, 0, 0, Lizard_parser_noChain, Lizard_coderwords_LZ4 }, // level 12
233 { LIZARD_WINDOWLOG_LZ4, LIZARD_CHAINLOG_LZ4, LIZARD_HASHLOG_LZ4, 0, 2, 5, 0, 0, 0, Lizard_parser_hashChain, Lizard_coderwords_LZ4 }, // level 13
234 { LIZARD_WINDOWLOG_LZ4, LIZARD_CHAINLOG_LZ4, LIZARD_HASHLOG_LZ4, 0, 4, 5, 0, 0, 0, Lizard_parser_hashChain, Lizard_coderwords_LZ4 }, // level 14
235 { LIZARD_WINDOWLOG_LZ4, LIZARD_CHAINLOG_LZ4, LIZARD_HASHLOG_LZ4, 0, 8, 5, 0, 0, 0, Lizard_parser_hashChain, Lizard_coderwords_LZ4 }, // level 15
236 { LIZARD_WINDOWLOG_LZ4, LIZARD_CHAINLOG_LZ4, LIZARD_HASHLOG_LZ4, 0, 16, 4, 0, 0, 0, Lizard_parser_hashChain, Lizard_coderwords_LZ4 }, // level 16
237 { LIZARD_WINDOWLOG_LZ4, LIZARD_CHAINLOG_LZ4, LIZARD_HASHLOG_LZ4, 0, 256, 4, 0, 0, 0, Lizard_parser_hashChain, Lizard_coderwords_LZ4 }, // level 17
238 { LIZARD_WINDOWLOG_LZ4, LIZARD_WINDOWLOG_LZ4+1, LIZARD_HASHLOG_LZ4, 16, 16, 4, 0, 1<<10, 1, Lizard_parser_optimalPriceBT, Lizard_coderwords_LZ4 }, // level 18
239 { LIZARD_WINDOWLOG_LZ4, LIZARD_WINDOWLOG_LZ4+1, 23, 16, 256, 4, 0, 1<<10, 1, Lizard_parser_optimalPriceBT, Lizard_coderwords_LZ4 }, // level 19
240 /* windLog, contentLog, HashLog, H3, Snum, SL, MMLongOff, SuffL, FS, Parser function, Decompressor type */
241 { LIZARD_WINDOWLOG_LIZv1, 0, 14, 0, 1, 5, MM_LONGOFF, 0, 0, Lizard_parser_fastBig, Lizard_coderwords_LIZv1 }, // level 20
242 { LIZARD_WINDOWLOG_LIZv1, LIZARD_CHAINLOG_LIZv1, 14, 13, 1, 5, MM_LONGOFF, 0, 0, Lizard_parser_priceFast, Lizard_coderwords_LIZv1 }, // level 21
243 { LIZARD_WINDOWLOG_LIZv1, LIZARD_CHAINLOG_LIZv1, LIZARD_HASHLOG_LIZv1, 13, 1, 5, MM_LONGOFF, 0, 0, Lizard_parser_priceFast, Lizard_coderwords_LIZv1 }, // level 22
244 { LIZARD_WINDOWLOG_LIZv1, LIZARD_CHAINLOG_LIZv1, LIZARD_HASHLOG_LIZv1, 13, 1, 5, MM_LONGOFF, 64, 0, Lizard_parser_lowestPrice, Lizard_coderwords_LIZv1 }, // level 23
245 { LIZARD_WINDOWLOG_LIZv1, LIZARD_CHAINLOG_LIZv1, 23, 16, 2, 5, MM_LONGOFF, 64, 0, Lizard_parser_lowestPrice, Lizard_coderwords_LIZv1 }, // level 24
246 { LIZARD_WINDOWLOG_LIZv1, LIZARD_CHAINLOG_LIZv1, 23, 16, 8, 4, MM_LONGOFF, 64, 0, Lizard_parser_lowestPrice, Lizard_coderwords_LIZv1 }, // level 25
247 { LIZARD_WINDOWLOG_LIZv1, LIZARD_CHAINLOG_LIZv1+1, 23, 16, 8, 4, MM_LONGOFF, 64, 1, Lizard_parser_optimalPriceBT, Lizard_coderwords_LIZv1 }, // level 26
248 { LIZARD_WINDOWLOG_LIZv1, LIZARD_CHAINLOG_LIZv1+1, 23, 16, 128, 4, MM_LONGOFF, 64, 1, Lizard_parser_optimalPriceBT, Lizard_coderwords_LIZv1 }, // level 27
249 { LIZARD_WINDOWLOG_LIZv1, LIZARD_CHAINLOG_LIZv1+1, 23, 24, 1<<10, 4, MM_LONGOFF, 1<<10, 1, Lizard_parser_optimalPriceBT, Lizard_coderwords_LIZv1 }, // level 28
250 { 24, 25, 23, 24, 1<<10, 4, MM_LONGOFF, 1<<10, 1, Lizard_parser_optimalPriceBT, Lizard_coderwords_LIZv1 }, // level 29
251 #ifndef LIZARD_NO_HUFFMAN
252 /* windLog, contentLog, HashLog, H3, Snum, SL, MMLongOff, SuffL, FS, Parser function, Decompressor type */
253 { LIZARD_WINDOWLOG_LZ4, 0, LIZARD_HASHLOG_LZ4SM, 0, 0, 0, 0, 0, 0, Lizard_parser_fastSmall, Lizard_coderwords_LZ4 }, // level 30
254 { LIZARD_WINDOWLOG_LZ4, 0, LIZARD_HASHLOG_LZ4, 0, 0, 0, 0, 0, 0, Lizard_parser_fast, Lizard_coderwords_LZ4 }, // level 31
255 { LIZARD_WINDOWLOG_LZ4, 0, 14, 0, 0, 0, 0, 0, 0, Lizard_parser_noChain, Lizard_coderwords_LZ4 }, // level 32
256 { LIZARD_WINDOWLOG_LZ4, 0, LIZARD_HASHLOG_LZ4, 0, 0, 0, 0, 0, 0, Lizard_parser_noChain, Lizard_coderwords_LZ4 }, // level 33
257 { LIZARD_WINDOWLOG_LZ4, LIZARD_CHAINLOG_LZ4, LIZARD_HASHLOG_LZ4, 0, 2, 5, 0, 0, 0, Lizard_parser_hashChain, Lizard_coderwords_LZ4 }, // level 34
258 { LIZARD_WINDOWLOG_LZ4, LIZARD_CHAINLOG_LZ4, LIZARD_HASHLOG_LZ4, 0, 4, 5, 0, 0, 0, Lizard_parser_hashChain, Lizard_coderwords_LZ4 }, // level 35
259 { LIZARD_WINDOWLOG_LZ4, LIZARD_CHAINLOG_LZ4, LIZARD_HASHLOG_LZ4, 0, 8, 5, 0, 0, 0, Lizard_parser_hashChain, Lizard_coderwords_LZ4 }, // level 36
260 { LIZARD_WINDOWLOG_LZ4, LIZARD_CHAINLOG_LZ4, LIZARD_HASHLOG_LZ4, 0, 16, 4, 0, 0, 0, Lizard_parser_hashChain, Lizard_coderwords_LZ4 }, // level 37
261 { LIZARD_WINDOWLOG_LZ4, LIZARD_CHAINLOG_LZ4, LIZARD_HASHLOG_LZ4, 0, 256, 4, 0, 0, 0, Lizard_parser_hashChain, Lizard_coderwords_LZ4 }, // level 38
262 { LIZARD_WINDOWLOG_LZ4, LIZARD_WINDOWLOG_LZ4+1, 23, 16, 256, 4, 0, 1<<10, 1, Lizard_parser_optimalPriceBT, Lizard_coderwords_LZ4 }, // level 39
263 /* windLog, contentLog, HashLog, H3, Snum, SL, MMLongOff, SuffL, FS, Parser function, Decompressor type */
264 { LIZARD_WINDOWLOG_LIZv1, 0, 14, 0, 1, 5, MM_LONGOFF, 0, 0, Lizard_parser_fastBig, Lizard_coderwords_LIZv1 }, // level 40
265 { LIZARD_WINDOWLOG_LIZv1, LIZARD_CHAINLOG_LIZv1, 14, 13, 1, 5, MM_LONGOFF, 0, 0, Lizard_parser_priceFast, Lizard_coderwords_LIZv1 }, // level 41
266 { LIZARD_WINDOWLOG_LIZv1, LIZARD_CHAINLOG_LIZv1, LIZARD_HASHLOG_LIZv1, 13, 1, 5, MM_LONGOFF, 0, 0, Lizard_parser_priceFast, Lizard_coderwords_LIZv1 }, // level 42
267 { LIZARD_WINDOWLOG_LIZv1, LIZARD_CHAINLOG_LIZv1, LIZARD_HASHLOG_LIZv1, 13, 1, 5, MM_LONGOFF, 64, 0, Lizard_parser_lowestPrice, Lizard_coderwords_LIZv1 }, // level 43
268 { LIZARD_WINDOWLOG_LIZv1, LIZARD_CHAINLOG_LIZv1, 23, 16, 2, 5, MM_LONGOFF, 64, 0, Lizard_parser_lowestPrice, Lizard_coderwords_LIZv1 }, // level 44
269 { LIZARD_WINDOWLOG_LIZv1, LIZARD_CHAINLOG_LIZv1, 23, 16, 8, 4, MM_LONGOFF, 64, 0, Lizard_parser_lowestPrice, Lizard_coderwords_LIZv1 }, // level 45
270 { LIZARD_WINDOWLOG_LIZv1, LIZARD_CHAINLOG_LIZv1, 23, 16, 8, 4, MM_LONGOFF, 64, 0, Lizard_parser_optimalPrice, Lizard_coderwords_LIZv1 }, // level 46
271 { LIZARD_WINDOWLOG_LIZv1, LIZARD_CHAINLOG_LIZv1+1, 23, 16, 8, 4, MM_LONGOFF, 64, 1, Lizard_parser_optimalPriceBT, Lizard_coderwords_LIZv1 }, // level 47
272 { LIZARD_WINDOWLOG_LIZv1, LIZARD_CHAINLOG_LIZv1+1, 23, 16, 128, 4, MM_LONGOFF, 64, 1, Lizard_parser_optimalPriceBT, Lizard_coderwords_LIZv1 }, // level 48
273 { 24, 25, 23, 24, 1<<10, 4, MM_LONGOFF, 1<<10, 1, Lizard_parser_optimalPriceBT, Lizard_coderwords_LIZv1 }, // level 49
274 #endif
275 // { 10, 10, 10, 0, 0, 4, 0, 0, 0, Lizard_fast }, // min values
276 // { 24, 24, 28, 24, 1<<24, 7, 0, 1<<24, 2, Lizard_optimal_price }, // max values
277 };
278
279
280
281 /*-************************************
282 * Compiler Options
283 **************************************/
284 #ifdef _MSC_VER /* Visual Studio */
285 # define FORCE_INLINE static __forceinline
286 # include <intrin.h>
287 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
288 # pragma warning(disable : 4293) /* disable: C4293: too large shift (32-bits) */
289 #else
290 # if defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */
291 # if defined(__GNUC__) || defined(__clang__)
292 # define FORCE_INLINE static inline __attribute__((always_inline))
293 # else
294 # define FORCE_INLINE static inline
295 # endif
296 # else
297 # define FORCE_INLINE static
298 # endif /* __STDC_VERSION__ */
299 #endif /* _MSC_VER */
300
301 #define LIZARD_GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
302 #if (LIZARD_GCC_VERSION >= 302) || (__INTEL_COMPILER >= 800) || defined(__clang__)
303 # define expect(expr,value) (__builtin_expect ((expr),(value)) )
304 #else
305 # define expect(expr,value) (expr)
306 #endif
307
308 #define likely(expr) expect((expr) != 0, 1)
309 #define unlikely(expr) expect((expr) != 0, 0)
310
311 #define KB *(1 <<10)
312 #define MB *(1 <<20)
313 #define GB *(1U<<30)
314
315 #define ALLOCATOR(n,s) calloc(n,s)
316 #define FREEMEM free
317 #define MEM_INIT memset
318 #ifndef MAX
319 #define MAX(a,b) ((a)>(b))?(a):(b)
320 #endif
321 #ifndef MIN
322 #define MIN(a,b) ((a)<(b)?(a):(b))
323 #endif
324
325 #if MINMATCH == 3
326 #define MEM_readMINMATCH(ptr) (U32)(MEM_read32(ptr)<<8)
327 #else
328 #define MEM_readMINMATCH(ptr) (U32)(MEM_read32(ptr))
329 #endif
330
331
332
333
334 /*-************************************
335 * Reading and writing into memory
336 **************************************/
337 #define STEPSIZE sizeof(size_t)
338
339
Lizard_copy8(void * dst,const void * src)340 MEM_STATIC void Lizard_copy8(void* dst, const void* src)
341 {
342 memcpy(dst,src,8);
343 }
344
345 /* customized variant of memcpy, which can overwrite up to 7 bytes beyond dstEnd */
Lizard_wildCopy(void * dstPtr,const void * srcPtr,void * dstEnd)346 MEM_STATIC void Lizard_wildCopy(void* dstPtr, const void* srcPtr, void* dstEnd)
347 {
348 BYTE* d = (BYTE*)dstPtr;
349 const BYTE* s = (const BYTE*)srcPtr;
350 BYTE* const e = (BYTE*)dstEnd;
351
352 #if 0
353 const size_t l2 = 8 - (((size_t)d) & (sizeof(void*)-1));
354 Lizard_copy8(d,s); if (d>e-9) return;
355 d+=l2; s+=l2;
356 #endif /* join to align */
357
358 do { Lizard_copy8(d,s); d+=8; s+=8; } while (d<e);
359 }
360
Lizard_wildCopy16(BYTE * dstPtr,const BYTE * srcPtr,BYTE * dstEnd)361 MEM_STATIC void Lizard_wildCopy16(BYTE* dstPtr, const BYTE* srcPtr, BYTE* dstEnd)
362 {
363 do {
364 Lizard_copy8(dstPtr, srcPtr);
365 Lizard_copy8(dstPtr+8, srcPtr+8);
366 dstPtr += 16;
367 srcPtr += 16;
368 }
369 while (dstPtr < dstEnd);
370 }
371
372 /*
373 * LIZARD_FORCE_SW_BITCOUNT
374 * Define this parameter if your target system or compiler does not support hardware bit count
375 */
376 #if defined(_MSC_VER) && defined(_WIN32_WCE) /* Visual Studio for Windows CE does not support Hardware bit count */
377 # define LIZARD_FORCE_SW_BITCOUNT
378 #endif
379
380
381 /* **************************************
382 * Function body to include for inlining
383 ****************************************/
Lizard_highbit32(U32 val)384 MEM_STATIC U32 Lizard_highbit32(U32 val)
385 {
386 # if defined(_MSC_VER) /* Visual */
387 unsigned long r=0;
388 _BitScanReverse(&r, val);
389 return (unsigned)r;
390 # elif defined(__GNUC__) && (__GNUC__ >= 3) /* GCC Intrinsic */
391 return 31 - __builtin_clz(val);
392 # else /* Software version */
393 static const int DeBruijnClz[32] = { 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 };
394 U32 v = val;
395 int r;
396 v |= v >> 1;
397 v |= v >> 2;
398 v |= v >> 4;
399 v |= v >> 8;
400 v |= v >> 16;
401 r = DeBruijnClz[(U32)(v * 0x07C4ACDDU) >> 27];
402 return r;
403 # endif
404 }
405
406
407 /*-************************************
408 * Common functions
409 **************************************/
Lizard_NbCommonBytes(register size_t val)410 MEM_STATIC unsigned Lizard_NbCommonBytes (register size_t val)
411 {
412 if (MEM_isLittleEndian()) {
413 if (MEM_64bits()) {
414 # if defined(_MSC_VER) && defined(_WIN64) && !defined(LIZARD_FORCE_SW_BITCOUNT)
415 unsigned long r = 0;
416 _BitScanForward64( &r, (U64)val );
417 return (int)(r>>3);
418 # elif (defined(__clang__) || (LIZARD_GCC_VERSION >= 304)) && !defined(LIZARD_FORCE_SW_BITCOUNT)
419 return (__builtin_ctzll((U64)val) >> 3);
420 # else
421 static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2, 0, 3, 1, 3, 1, 4, 2, 7, 0, 2, 3, 6, 1, 5, 3, 5, 1, 3, 4, 4, 2, 5, 6, 7, 7, 0, 1, 2, 3, 3, 4, 6, 2, 6, 5, 5, 3, 4, 5, 6, 7, 1, 2, 4, 6, 4, 4, 5, 7, 2, 6, 5, 7, 6, 7, 7 };
422 return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58];
423 # endif
424 } else /* 32 bits */ {
425 # if defined(_MSC_VER) && !defined(LIZARD_FORCE_SW_BITCOUNT)
426 unsigned long r;
427 _BitScanForward( &r, (U32)val );
428 return (int)(r>>3);
429 # elif (defined(__clang__) || (LIZARD_GCC_VERSION >= 304)) && !defined(LIZARD_FORCE_SW_BITCOUNT)
430 return (__builtin_ctz((U32)val) >> 3);
431 # else
432 static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0, 3, 2, 2, 1, 3, 2, 0, 1, 3, 3, 1, 2, 2, 2, 2, 0, 3, 1, 2, 0, 1, 0, 1, 1 };
433 return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];
434 # endif
435 }
436 } else /* Big Endian CPU */ {
437 if (MEM_64bits()) {
438 # if defined(_MSC_VER) && defined(_WIN64) && !defined(LIZARD_FORCE_SW_BITCOUNT)
439 unsigned long r = 0;
440 _BitScanReverse64( &r, val );
441 return (unsigned)(r>>3);
442 # elif (defined(__clang__) || (LIZARD_GCC_VERSION >= 304)) && !defined(LIZARD_FORCE_SW_BITCOUNT)
443 return (__builtin_clzll((U64)val) >> 3);
444 # else
445 unsigned r;
446 if (!(val>>32)) { r=4; } else { r=0; val>>=32; }
447 if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }
448 r += (!val);
449 return r;
450 # endif
451 } else /* 32 bits */ {
452 # if defined(_MSC_VER) && !defined(LIZARD_FORCE_SW_BITCOUNT)
453 unsigned long r = 0;
454 _BitScanReverse( &r, (unsigned long)val );
455 return (unsigned)(r>>3);
456 # elif (defined(__clang__) || (LIZARD_GCC_VERSION >= 304)) && !defined(LIZARD_FORCE_SW_BITCOUNT)
457 return (__builtin_clz((U32)val) >> 3);
458 # else
459 unsigned r;
460 if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }
461 r += (!val);
462 return r;
463 # endif
464 }
465 }
466 }
467
Lizard_count(const BYTE * pIn,const BYTE * pMatch,const BYTE * pInLimit)468 MEM_STATIC unsigned Lizard_count(const BYTE* pIn, const BYTE* pMatch, const BYTE* pInLimit)
469 {
470 const BYTE* const pStart = pIn;
471
472 while (likely(pIn<pInLimit-(STEPSIZE-1))) {
473 size_t diff = MEM_readST(pMatch) ^ MEM_readST(pIn);
474 if (!diff) { pIn+=STEPSIZE; pMatch+=STEPSIZE; continue; }
475 pIn += Lizard_NbCommonBytes(diff);
476 return (unsigned)(pIn - pStart);
477 }
478
479 if (MEM_64bits()) if ((pIn<(pInLimit-3)) && (MEM_read32(pMatch) == MEM_read32(pIn))) { pIn+=4; pMatch+=4; }
480 if ((pIn<(pInLimit-1)) && (MEM_read16(pMatch) == MEM_read16(pIn))) { pIn+=2; pMatch+=2; }
481 if ((pIn<pInLimit) && (*pMatch == *pIn)) pIn++;
482 return (unsigned)(pIn - pStart);
483 }
484
485 /* alias to functions with compressionLevel=1 */
486 int Lizard_sizeofState_MinLevel(void);
487 int Lizard_compress_MinLevel(const char* source, char* dest, int sourceSize, int maxDestSize);
488 int Lizard_compress_extState_MinLevel (void* state, const char* source, char* dest, int inputSize, int maxDestSize);
489 Lizard_stream_t* Lizard_resetStream_MinLevel (Lizard_stream_t* streamPtr);
490 Lizard_stream_t* Lizard_createStream_MinLevel(void);
491
492
493 #if defined (__cplusplus)
494 }
495 #endif
496
497 #endif /* LIZARD_COMMON_H_2983827168210 */
498