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 NOTLizard_hash4Ptr
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
36 /* *************************************
37 * Includes
38 ***************************************/
39 #include "lizard_compress.h"
40 #include "lizard_common.h"
41 #include <stdio.h>
42 #include <stdint.h> // intptr_t
43 #ifndef USE_LZ4_ONLY
44 #ifdef LIZARD_USE_TEST
45 #include "test/lizard_common_test.h"
46 #include "test/lizard_compress_test.h"
47 #else
48 #include "lizard_compress_liz.h"
49 #endif
50 #endif
51 #include "lizard_compress_lz4.h"
52 #include "entropy/huf.h"
53
54
55 /* *************************************
56 * Local Macros
57 ***************************************/
58 #define DELTANEXT(p) chainTable[(p) & contentMask]
59 #define LIZARD_MINIMAL_HUFF_GAIN(comprSize) (comprSize + (comprSize/8) + 512)
60 #define LIZARD_MINIMAL_BLOCK_GAIN(comprSize) (comprSize + (comprSize/32) + 512)
61
62
63 /*-************************************
64 * Local Utils
65 **************************************/
Lizard_versionNumber(void)66 int Lizard_versionNumber (void) { return LIZARD_VERSION_NUMBER; }
Lizard_compressBound(int isize)67 int Lizard_compressBound(int isize) { return LIZARD_COMPRESSBOUND(isize); }
Lizard_sizeofState_MinLevel()68 int Lizard_sizeofState_MinLevel() { return Lizard_sizeofState(LIZARD_MIN_CLEVEL); }
69
70
71
72 /* *************************************
73 * Hash functions
74 ***************************************/
75 #define HASH_UPDATE_LIMIT 8 /* equal to MEM_read64 */
76 static const U32 prime4bytes = 2654435761U;
77 static const U64 prime5bytes = 889523592379ULL;
78 static const U64 prime6bytes = 227718039650203ULL;
79 static const U64 prime7bytes = 58295818150454627ULL;
80
81 #if MINMATCH == 3
82 static const U32 prime3bytes = 506832829U;
Lizard_hash3(U32 u,U32 h)83 static U32 Lizard_hash3(U32 u, U32 h) { return (u * prime3bytes) << (32-24) >> (32-h) ; }
Lizard_hash3Ptr(const void * ptr,U32 h)84 static size_t Lizard_hash3Ptr(const void* ptr, U32 h) { return Lizard_hash3(MEM_read32(ptr), h); }
85 #endif
86
Lizard_hash4(U32 u,U32 h)87 static U32 Lizard_hash4(U32 u, U32 h) { return (u * prime4bytes) >> (32-h) ; }
Lizard_hash4Ptr(const void * ptr,U32 h)88 static size_t Lizard_hash4Ptr(const void* ptr, U32 h) { return Lizard_hash4(MEM_read32(ptr), h); }
89
Lizard_hash5(U64 u,U32 h)90 static size_t Lizard_hash5(U64 u, U32 h) { return (size_t)((u * prime5bytes) << (64-40) >> (64-h)) ; }
Lizard_hash5Ptr(const void * p,U32 h)91 static size_t Lizard_hash5Ptr(const void* p, U32 h) { return Lizard_hash5(MEM_read64(p), h); }
92
Lizard_hash6(U64 u,U32 h)93 static size_t Lizard_hash6(U64 u, U32 h) { return (size_t)((u * prime6bytes) << (64-48) >> (64-h)) ; }
Lizard_hash6Ptr(const void * p,U32 h)94 static size_t Lizard_hash6Ptr(const void* p, U32 h) { return Lizard_hash6(MEM_read64(p), h); }
95
Lizard_hash7(U64 u,U32 h)96 static size_t Lizard_hash7(U64 u, U32 h) { return (size_t)((u * prime7bytes) << (64-56) >> (64-h)) ; }
Lizard_hash7Ptr(const void * p,U32 h)97 static size_t Lizard_hash7Ptr(const void* p, U32 h) { return Lizard_hash7(MEM_read64(p), h); }
98
Lizard_hashPtr(const void * p,U32 hBits,U32 mls)99 static size_t Lizard_hashPtr(const void* p, U32 hBits, U32 mls)
100 {
101 switch(mls)
102 {
103 default:
104 case 4: return Lizard_hash4Ptr(p, hBits);
105 case 5: return Lizard_hash5Ptr(p, hBits);
106 case 6: return Lizard_hash6Ptr(p, hBits);
107 case 7: return Lizard_hash7Ptr(p, hBits);
108 }
109 }
110
111
112
113
114 /**************************************
115 * Internal functions
116 **************************************/
117 /** Lizard_count_2segments() :
118 * can count match length with `ip` & `match` in 2 different segments.
119 * convention : on reaching mEnd, match count continue starting from iStart
120 */
Lizard_count_2segments(const BYTE * ip,const BYTE * match,const BYTE * iEnd,const BYTE * mEnd,const BYTE * iStart)121 static size_t Lizard_count_2segments(const BYTE* ip, const BYTE* match, const BYTE* iEnd, const BYTE* mEnd, const BYTE* iStart)
122 {
123 const BYTE* const vEnd = MIN( ip + (mEnd - match), iEnd);
124 size_t const matchLength = Lizard_count(ip, match, vEnd);
125 if (match + matchLength != mEnd) return matchLength;
126 return matchLength + Lizard_count(ip+matchLength, iStart, iEnd);
127 }
128
129
Lizard_initBlock(Lizard_stream_t * ctx)130 void Lizard_initBlock(Lizard_stream_t* ctx)
131 {
132 ctx->offset16Ptr = ctx->offset16Base;
133 ctx->offset24Ptr = ctx->offset24Base;
134 ctx->lenPtr = ctx->lenBase;
135 ctx->literalsPtr = ctx->literalsBase;
136 ctx->flagsPtr = ctx->flagsBase;
137 ctx->last_off = LIZARD_INIT_LAST_OFFSET; /* reset last offset */
138 }
139
140
Lizard_writeStream(int useHuff,Lizard_stream_t * ctx,BYTE * streamPtr,uint32_t streamLen,BYTE ** op,BYTE * oend)141 FORCE_INLINE int Lizard_writeStream(int useHuff, Lizard_stream_t* ctx, BYTE* streamPtr, uint32_t streamLen, BYTE** op, BYTE* oend)
142 {
143 if (useHuff && streamLen > 1024) {
144 #ifndef LIZARD_NO_HUFFMAN
145 int useHuffBuf;
146 if (*op + 6 > oend) { LIZARD_LOG_COMPRESS("*op[%p] + 6 > oend[%p]\n", *op, oend); return -1; }
147
148 useHuffBuf = ((size_t)(oend - (*op + 6)) < HUF_compressBound(streamLen));
149 if (useHuffBuf) {
150 if (streamLen > LIZARD_BLOCK_SIZE) { LIZARD_LOG_COMPRESS("streamLen[%d] > LIZARD_BLOCK_SIZE\n", streamLen); return -1; }
151 ctx->comprStreamLen = (U32)HUF_compress(ctx->huffBase, ctx->huffEnd - ctx->huffBase, streamPtr, streamLen);
152 } else {
153 ctx->comprStreamLen = (U32)HUF_compress(*op + 6, oend - (*op + 6), streamPtr, streamLen);
154 }
155
156 if (!HUF_isError(ctx->comprStreamLen)) {
157 if (ctx->comprStreamLen > 0 && (LIZARD_MINIMAL_HUFF_GAIN(ctx->comprStreamLen) < streamLen)) { /* compressible */
158 MEM_writeLE24(*op, streamLen);
159 MEM_writeLE24(*op+3, ctx->comprStreamLen);
160 if (useHuffBuf) {
161 if ((size_t)(oend - (*op + 6)) < ctx->comprStreamLen) { LIZARD_LOG_COMPRESS("*op[%p] oend[%p] comprStreamLen[%d]\n", *op, oend, (int)ctx->comprStreamLen); return -1; }
162 memcpy(*op + 6, ctx->huffBase, ctx->comprStreamLen);
163 }
164 *op += ctx->comprStreamLen + 6;
165 LIZARD_LOG_COMPRESS("HUF_compress streamLen=%d comprStreamLen=%d\n", (int)streamLen, (int)ctx->comprStreamLen);
166 return 1;
167 } else { LIZARD_LOG_COMPRESS("HUF_compress ERROR comprStreamLen=%d streamLen=%d\n", (int)ctx->comprStreamLen, (int)streamLen); }
168 } else { LIZARD_LOG_COMPRESS("HUF_compress ERROR %d: %s\n", (int)ctx->comprStreamLen, HUF_getErrorName(ctx->comprStreamLen)); }
169 #else
170 LIZARD_LOG_COMPRESS("compiled with LIZARD_NO_HUFFMAN\n");
171 (void)ctx;
172 return -1;
173 #endif
174 } else ctx->comprStreamLen = 0;
175
176 if (*op + 3 + streamLen > oend) { LIZARD_LOG_COMPRESS("*op[%p] + 3 + streamLen[%d] > oend[%p]\n", *op, streamLen, oend); return -1; }
177 MEM_writeLE24(*op, streamLen);
178 *op += 3;
179 memcpy(*op, streamPtr, streamLen);
180 *op += streamLen;
181 LIZARD_LOG_COMPRESS("Uncompressed streamLen=%d\n", (int)streamLen);
182 return 0;
183 }
184
185
Lizard_writeBlock(Lizard_stream_t * ctx,const BYTE * ip,uint32_t inputSize,BYTE ** op,BYTE * oend)186 int Lizard_writeBlock(Lizard_stream_t* ctx, const BYTE* ip, uint32_t inputSize, BYTE** op, BYTE* oend)
187 {
188 int res;
189 uint32_t flagsLen = (uint32_t)(ctx->flagsPtr - ctx->flagsBase);
190 uint32_t literalsLen = (uint32_t)(ctx->literalsPtr - ctx->literalsBase);
191 uint32_t lenLen = (uint32_t)(ctx->lenPtr - ctx->lenBase);
192 uint32_t offset16Len = (uint32_t)(ctx->offset16Ptr - ctx->offset16Base);
193 uint32_t offset24Len = (uint32_t)(ctx->offset24Ptr - ctx->offset24Base);
194 uint32_t sum = flagsLen + literalsLen + lenLen + offset16Len + offset24Len;
195 #ifdef LIZARD_USE_LOGS
196 uint32_t comprFlagsLen, comprLiteralsLen;
197 #endif
198
199 BYTE* start = *op;
200
201 if ((literalsLen < WILDCOPYLENGTH) || (sum+5*3+1 > inputSize)) goto _write_uncompressed;
202
203 *start = 0;
204 *op += 1;
205
206 res = Lizard_writeStream(0, ctx, ctx->lenBase, lenLen, op, oend);
207 if (res < 0) goto _output_error; else *start += (BYTE)(res*LIZARD_FLAG_LEN);
208
209 res = Lizard_writeStream(ctx->huffType&LIZARD_FLAG_OFFSET16, ctx, ctx->offset16Base, offset16Len, op, oend);
210 if (res < 0) goto _output_error; else *start += (BYTE)(res*LIZARD_FLAG_OFFSET16);
211
212 res = Lizard_writeStream(ctx->huffType&LIZARD_FLAG_OFFSET24, ctx, ctx->offset24Base, offset24Len, op, oend);
213 if (res < 0) goto _output_error; else *start += (BYTE)(res*LIZARD_FLAG_OFFSET24);
214
215 res = Lizard_writeStream(ctx->huffType&LIZARD_FLAG_FLAGS, ctx, ctx->flagsBase, flagsLen, op, oend);
216 if (res < 0) goto _output_error; else *start += (BYTE)(res*LIZARD_FLAG_FLAGS);
217 #ifdef LIZARD_USE_LOGS
218 comprFlagsLen = ctx->comprStreamLen;
219 #endif
220
221 res = Lizard_writeStream(ctx->huffType&LIZARD_FLAG_LITERALS, ctx, ctx->literalsBase, literalsLen, op, oend);
222 if (res < 0) goto _output_error; else *start += (BYTE)(res*LIZARD_FLAG_LITERALS);
223 #ifdef LIZARD_USE_LOGS
224 comprLiteralsLen = ctx->comprStreamLen;
225 sum = (int)(*op-start);
226 #endif
227
228 if (LIZARD_MINIMAL_BLOCK_GAIN((uint32_t)(*op-start)) > inputSize) goto _write_uncompressed;
229
230 LIZARD_LOG_COMPRESS("%d: total=%d block=%d flagsLen[%.2f%%]=%d comprFlagsLen[%.2f%%]=%d literalsLen[%.2f%%]=%d comprLiteralsLen[%.2f%%]=%d lenLen=%d offset16Len[%.2f%%]=%d offset24Len[%.2f%%]=%d\n", (int)(ip - ctx->srcBase),
231 (int)(*op - ctx->destBase), sum, (flagsLen*100.0)/sum, flagsLen, (comprFlagsLen*100.0)/sum, comprFlagsLen, (literalsLen*100.0)/sum, literalsLen, (comprLiteralsLen*100.0)/sum, comprLiteralsLen,
232 lenLen, (offset16Len*100.0)/sum, offset16Len, (offset24Len*100.0)/sum, offset24Len);
233 return 0;
234
235 _write_uncompressed:
236 LIZARD_LOG_COMPRESS("%d: total=%d block=%d UNCOMPRESSED inputSize=%u outSize=%d\n", (int)(ip - ctx->srcBase),
237 (int)(*op - ctx->destBase), (int)(*op-start), inputSize, (int)(oend-start));
238 if ((uint32_t)(oend - start) < inputSize + 4) goto _output_error;
239 *start = LIZARD_FLAG_UNCOMPRESSED;
240 *op = start + 1;
241 MEM_writeLE24(*op, inputSize);
242 *op += 3;
243 memcpy(*op, ip, inputSize);
244 *op += inputSize;
245 return 0;
246
247 _output_error:
248 LIZARD_LOG_COMPRESS("Lizard_writeBlock ERROR size=%d/%d flagsLen=%d literalsLen=%d lenLen=%d offset16Len=%d offset24Len=%d\n", (int)(*op-start), (int)(oend-start), flagsLen, literalsLen, lenLen, offset16Len, offset24Len);
249 return 1;
250 }
251
252
Lizard_encodeSequence(Lizard_stream_t * ctx,const BYTE ** ip,const BYTE ** anchor,size_t matchLength,const BYTE * const match)253 FORCE_INLINE int Lizard_encodeSequence (
254 Lizard_stream_t* ctx,
255 const BYTE** ip,
256 const BYTE** anchor,
257 size_t matchLength,
258 const BYTE* const match)
259 {
260 #ifdef USE_LZ4_ONLY
261 return Lizard_encodeSequence_LZ4(ctx, ip, anchor, matchLength, match);
262 #else
263 if (ctx->params.decompressType == Lizard_coderwords_LZ4)
264 return Lizard_encodeSequence_LZ4(ctx, ip, anchor, matchLength, match);
265
266 return Lizard_encodeSequence_LIZv1(ctx, ip, anchor, matchLength, match);
267 #endif
268 }
269
270
Lizard_encodeLastLiterals(Lizard_stream_t * ctx,const BYTE ** ip,const BYTE ** anchor)271 FORCE_INLINE int Lizard_encodeLastLiterals (
272 Lizard_stream_t* ctx,
273 const BYTE** ip,
274 const BYTE** anchor)
275 {
276 LIZARD_LOG_COMPRESS("Lizard_encodeLastLiterals Lizard_coderwords_LZ4=%d\n", ctx->params.decompressType == Lizard_coderwords_LZ4);
277 #ifdef USE_LZ4_ONLY
278 return Lizard_encodeLastLiterals_LZ4(ctx, ip, anchor);
279 #else
280 if (ctx->params.decompressType == Lizard_coderwords_LZ4)
281 return Lizard_encodeLastLiterals_LZ4(ctx, ip, anchor);
282
283 return Lizard_encodeLastLiterals_LIZv1(ctx, ip, anchor);
284 #endif
285 }
286
287
288 /**************************************
289 * Include parsers
290 **************************************/
291 #include "lizard_parser_hashchain.h"
292 #include "lizard_parser_nochain.h"
293 #include "lizard_parser_fast.h"
294 #include "lizard_parser_fastsmall.h"
295 #include "lizard_parser_fastbig.h"
296 #ifndef USE_LZ4_ONLY
297 #include "lizard_parser_optimal.h"
298 #include "lizard_parser_lowestprice.h"
299 #include "lizard_parser_pricefast.h"
300 #endif
301
302
Lizard_verifyCompressionLevel(int compressionLevel)303 int Lizard_verifyCompressionLevel(int compressionLevel)
304 {
305 if (compressionLevel > LIZARD_MAX_CLEVEL) compressionLevel = LIZARD_MAX_CLEVEL;
306 if (compressionLevel < LIZARD_MIN_CLEVEL) compressionLevel = LIZARD_DEFAULT_CLEVEL;
307 return compressionLevel;
308 }
309
310
Lizard_sizeofState(int compressionLevel)311 int Lizard_sizeofState(int compressionLevel)
312 {
313 Lizard_parameters params;
314 U32 hashTableSize, chainTableSize;
315
316 compressionLevel = Lizard_verifyCompressionLevel(compressionLevel);
317 params = Lizard_defaultParameters[compressionLevel - LIZARD_MIN_CLEVEL];
318 // hashTableSize = (U32)(sizeof(U32)*(((size_t)1 << params.hashLog3)+((size_t)1 << params.hashLog)));
319 hashTableSize = (U32)(sizeof(U32)*(((size_t)1 << params.hashLog)));
320 chainTableSize = (U32)(sizeof(U32)*((size_t)1 << params.contentLog));
321
322 return sizeof(Lizard_stream_t) + hashTableSize + chainTableSize + LIZARD_COMPRESS_ADD_BUF + (int)LIZARD_COMPRESS_ADD_HUF;
323 }
324
325
Lizard_init(Lizard_stream_t * ctx,const BYTE * start)326 static void Lizard_init(Lizard_stream_t* ctx, const BYTE* start)
327 {
328 // No need to use memset() on tables as values are always bound checked
329 #ifdef LIZARD_RESET_MEM
330 MEM_INIT((void*)ctx->hashTable, 0, ctx->hashTableSize);
331 MEM_INIT(ctx->chainTable, 0x01, ctx->chainTableSize);
332 #endif
333 // printf("memset hashTable=%p hashEnd=%p chainTable=%p chainEnd=%p\n", ctx->hashTable, ((BYTE*)ctx->hashTable) + ctx->hashTableSize, ctx->chainTable, ((BYTE*)ctx->chainTable)+ctx->chainTableSize);
334 ctx->nextToUpdate = LIZARD_DICT_SIZE;
335 ctx->base = start - LIZARD_DICT_SIZE;
336 ctx->end = start;
337 ctx->dictBase = start - LIZARD_DICT_SIZE;
338 ctx->dictLimit = LIZARD_DICT_SIZE;
339 ctx->lowLimit = LIZARD_DICT_SIZE;
340 ctx->last_off = LIZARD_INIT_LAST_OFFSET;
341 ctx->litSum = 0;
342 }
343
344
345 /* if ctx==NULL memory is allocated and returned as value */
Lizard_initStream(Lizard_stream_t * ctx,int compressionLevel)346 Lizard_stream_t* Lizard_initStream(Lizard_stream_t* ctx, int compressionLevel)
347 {
348 Lizard_parameters params;
349 U32 hashTableSize, chainTableSize;
350 void *tempPtr;
351
352 compressionLevel = Lizard_verifyCompressionLevel(compressionLevel);
353 params = Lizard_defaultParameters[compressionLevel - LIZARD_MIN_CLEVEL];
354 // hashTableSize = (U32)(sizeof(U32)*(((size_t)1 << params.hashLog3)+((size_t)1 << params.hashLog)));
355 hashTableSize = (U32)(sizeof(U32)*(((size_t)1 << params.hashLog)));
356 chainTableSize = (U32)(sizeof(U32)*((size_t)1 << params.contentLog));
357
358 if (!ctx)
359 {
360 ctx = (Lizard_stream_t*)malloc(sizeof(Lizard_stream_t) + hashTableSize + chainTableSize + LIZARD_COMPRESS_ADD_BUF + LIZARD_COMPRESS_ADD_HUF);
361 if (!ctx) { printf("ERROR: Cannot allocate %d MB (compressionLevel=%d)\n", (int)(sizeof(Lizard_stream_t) + hashTableSize + chainTableSize)>>20, compressionLevel); return 0; }
362 LIZARD_LOG_COMPRESS("Allocated %d MB (compressionLevel=%d)\n", (int)(sizeof(Lizard_stream_t) + hashTableSize + chainTableSize)>>20, compressionLevel);
363 ctx->allocatedMemory = sizeof(Lizard_stream_t) + hashTableSize + chainTableSize + LIZARD_COMPRESS_ADD_BUF + (U32)LIZARD_COMPRESS_ADD_HUF;
364 // printf("malloc from=%p to=%p hashTable=%p hashEnd=%p chainTable=%p chainEnd=%p\n", ctx, ((BYTE*)ctx)+sizeof(Lizard_stream_t) + hashTableSize + chainTableSize, ctx->hashTable, ((BYTE*)ctx->hashTable) + hashTableSize, ctx->chainTable, ((BYTE*)ctx->chainTable)+chainTableSize);
365 }
366
367 tempPtr = ctx;
368 ctx->hashTable = (U32*)(tempPtr) + sizeof(Lizard_stream_t)/4;
369 ctx->hashTableSize = hashTableSize;
370 ctx->chainTable = ctx->hashTable + hashTableSize/4;
371 ctx->chainTableSize = chainTableSize;
372 ctx->params = params;
373 ctx->compressionLevel = (unsigned)compressionLevel;
374 if (compressionLevel < 30)
375 ctx->huffType = 0;
376 else
377 ctx->huffType = LIZARD_FLAG_LITERALS + LIZARD_FLAG_FLAGS; // + LIZARD_FLAG_OFFSET16 + LIZARD_FLAG_OFFSET24;
378
379 ctx->literalsBase = (BYTE*)ctx->hashTable + ctx->hashTableSize + ctx->chainTableSize;
380 ctx->flagsBase = ctx->literalsEnd = ctx->literalsBase + LIZARD_BLOCK_SIZE_PAD;
381 ctx->lenBase = ctx->flagsEnd = ctx->flagsBase + LIZARD_BLOCK_SIZE_PAD;
382 ctx->offset16Base = ctx->lenEnd = ctx->lenBase + LIZARD_BLOCK_SIZE_PAD;
383 ctx->offset24Base = ctx->offset16End = ctx->offset16Base + LIZARD_BLOCK_SIZE_PAD;
384 ctx->huffBase = ctx->offset24End = ctx->offset24Base + LIZARD_BLOCK_SIZE_PAD;
385 ctx->huffEnd = ctx->huffBase + LIZARD_COMPRESS_ADD_HUF;
386
387 return ctx;
388 }
389
390
391
Lizard_createStream(int compressionLevel)392 Lizard_stream_t* Lizard_createStream(int compressionLevel)
393 {
394 Lizard_stream_t* ctx = Lizard_initStream(NULL, compressionLevel);
395 return ctx;
396 }
397
398
399 /* initialization */
Lizard_resetStream(Lizard_stream_t * ctx,int compressionLevel)400 Lizard_stream_t* Lizard_resetStream(Lizard_stream_t* ctx, int compressionLevel)
401 {
402 size_t wanted = Lizard_sizeofState(compressionLevel);
403
404 if (ctx->allocatedMemory < wanted) {
405 Lizard_freeStream(ctx);
406 ctx = Lizard_createStream(compressionLevel);
407 } else {
408 Lizard_initStream(ctx, compressionLevel);
409 }
410
411 if (ctx) ctx->base = NULL;
412 return ctx;
413 }
414
415
Lizard_freeStream(Lizard_stream_t * ctx)416 int Lizard_freeStream(Lizard_stream_t* ctx)
417 {
418 if (ctx) {
419 free(ctx);
420 }
421 return 0;
422 }
423
424
Lizard_loadDict(Lizard_stream_t * Lizard_streamPtr,const char * dictionary,int dictSize)425 int Lizard_loadDict(Lizard_stream_t* Lizard_streamPtr, const char* dictionary, int dictSize)
426 {
427 Lizard_stream_t* ctxPtr = (Lizard_stream_t*) Lizard_streamPtr;
428 if (dictSize > LIZARD_DICT_SIZE) {
429 dictionary += dictSize - LIZARD_DICT_SIZE;
430 dictSize = LIZARD_DICT_SIZE;
431 }
432 Lizard_init (ctxPtr, (const BYTE*)dictionary);
433 if (dictSize >= HASH_UPDATE_LIMIT) Lizard_Insert (ctxPtr, (const BYTE*)dictionary + (dictSize - (HASH_UPDATE_LIMIT-1)));
434 ctxPtr->end = (const BYTE*)dictionary + dictSize;
435 return dictSize;
436 }
437
438
Lizard_setExternalDict(Lizard_stream_t * ctxPtr,const BYTE * newBlock)439 static void Lizard_setExternalDict(Lizard_stream_t* ctxPtr, const BYTE* newBlock)
440 {
441 if (ctxPtr->end >= ctxPtr->base + HASH_UPDATE_LIMIT) Lizard_Insert (ctxPtr, ctxPtr->end - (HASH_UPDATE_LIMIT-1)); /* Referencing remaining dictionary content */
442 /* Only one memory segment for extDict, so any previous extDict is lost at this stage */
443 ctxPtr->lowLimit = ctxPtr->dictLimit;
444 ctxPtr->dictLimit = (U32)(ctxPtr->end - ctxPtr->base);
445 ctxPtr->dictBase = ctxPtr->base;
446 ctxPtr->base = newBlock - ctxPtr->dictLimit;
447 ctxPtr->end = newBlock;
448 ctxPtr->nextToUpdate = ctxPtr->dictLimit; /* match referencing will resume from there */
449 }
450
451
452 /* dictionary saving */
Lizard_saveDict(Lizard_stream_t * Lizard_streamPtr,char * safeBuffer,int dictSize)453 int Lizard_saveDict (Lizard_stream_t* Lizard_streamPtr, char* safeBuffer, int dictSize)
454 {
455 Lizard_stream_t* const ctx = (Lizard_stream_t*)Lizard_streamPtr;
456 int const prefixSize = (int)(ctx->end - (ctx->base + ctx->dictLimit));
457 if (dictSize > LIZARD_DICT_SIZE) dictSize = LIZARD_DICT_SIZE;
458 if (dictSize < 4) dictSize = 0;
459 if (dictSize > prefixSize) dictSize = prefixSize;
460 memmove(safeBuffer, ctx->end - dictSize, dictSize);
461 { U32 const endIndex = (U32)(ctx->end - ctx->base);
462 ctx->end = (const BYTE*)safeBuffer + dictSize;
463 ctx->base = ctx->end - endIndex;
464 ctx->dictLimit = endIndex - dictSize;
465 ctx->lowLimit = endIndex - dictSize;
466 if (ctx->nextToUpdate < ctx->dictLimit) ctx->nextToUpdate = ctx->dictLimit;
467 }
468 return dictSize;
469 }
470
Lizard_compress_generic(void * ctxvoid,const char * source,char * dest,int inputSize,int maxOutputSize)471 FORCE_INLINE int Lizard_compress_generic (
472 void* ctxvoid,
473 const char* source,
474 char* dest,
475 int inputSize,
476 int maxOutputSize)
477 {
478 Lizard_stream_t* ctx = (Lizard_stream_t*) ctxvoid;
479 size_t dictSize = (size_t)(ctx->end - ctx->base) - ctx->dictLimit;
480 const BYTE* ip = (const BYTE*) source;
481 BYTE* op = (BYTE*) dest;
482 BYTE* const oend = op + maxOutputSize;
483 int res;
484
485 (void)dictSize;
486 LIZARD_LOG_COMPRESS("Lizard_compress_generic source=%p inputSize=%d dest=%p maxOutputSize=%d cLevel=%d dictBase=%p dictSize=%d\n", source, inputSize, dest, maxOutputSize, ctx->compressionLevel, ctx->dictBase, (int)dictSize);
487 *op++ = (BYTE)ctx->compressionLevel;
488 maxOutputSize--; // can be lower than 0
489 ctx->end += inputSize;
490 ctx->srcBase = ctx->off24pos = ip;
491 ctx->destBase = (BYTE*)dest;
492
493 while (inputSize > 0)
494 {
495 int inputPart = MIN(LIZARD_BLOCK_SIZE, inputSize);
496
497 if (ctx->huffType) Lizard_rescaleFreqs(ctx);
498 Lizard_initBlock(ctx);
499 ctx->diffBase = ip;
500
501 switch(ctx->params.parserType)
502 {
503 default:
504 case Lizard_parser_fastSmall:
505 res = Lizard_compress_fastSmall(ctx, ip, ip+inputPart); break;
506 case Lizard_parser_fast:
507 res = Lizard_compress_fast(ctx, ip, ip+inputPart); break;
508 case Lizard_parser_noChain:
509 res = Lizard_compress_noChain(ctx, ip, ip+inputPart); break;
510 case Lizard_parser_hashChain:
511 res = Lizard_compress_hashChain(ctx, ip, ip+inputPart); break;
512 #ifndef USE_LZ4_ONLY
513 case Lizard_parser_fastBig:
514 res = Lizard_compress_fastBig(ctx, ip, ip+inputPart); break;
515 case Lizard_parser_priceFast:
516 res = Lizard_compress_priceFast(ctx, ip, ip+inputPart); break;
517 case Lizard_parser_lowestPrice:
518 res = Lizard_compress_lowestPrice(ctx, ip, ip+inputPart); break;
519 case Lizard_parser_optimalPrice:
520 case Lizard_parser_optimalPriceBT:
521 res = Lizard_compress_optimalPrice(ctx, ip, ip+inputPart); break;
522 #else
523 case Lizard_parser_priceFast:
524 case Lizard_parser_lowestPrice:
525 case Lizard_parser_optimalPrice:
526 case Lizard_parser_optimalPriceBT:
527 res = 0;
528 #endif
529 }
530
531 LIZARD_LOG_COMPRESS("Lizard_compress_generic res=%d inputPart=%d \n", res, inputPart);
532 if (res <= 0) return res;
533
534 if (Lizard_writeBlock(ctx, ip, inputPart, &op, oend)) goto _output_error;
535
536 ip += inputPart;
537 inputSize -= inputPart;
538 LIZARD_LOG_COMPRESS("Lizard_compress_generic in=%d out=%d\n", (int)(ip-(const BYTE*)source), (int)(op-(BYTE*)dest));
539 }
540
541 LIZARD_LOG_COMPRESS("Lizard_compress_generic total=%d\n", (int)(op-(BYTE*)dest));
542 return (int)(op-(BYTE*)dest);
543 _output_error:
544 LIZARD_LOG_COMPRESS("Lizard_compress_generic ERROR\n");
545 return 0;
546 }
547
548
Lizard_compress_continue(Lizard_stream_t * ctxPtr,const char * source,char * dest,int inputSize,int maxOutputSize)549 int Lizard_compress_continue (Lizard_stream_t* ctxPtr,
550 const char* source, char* dest,
551 int inputSize, int maxOutputSize)
552 {
553 /* auto-init if forgotten */
554 if (ctxPtr->base == NULL) Lizard_init (ctxPtr, (const BYTE*) source);
555
556 /* Check overflow */
557 if ((size_t)(ctxPtr->end - ctxPtr->base) > 2 GB) {
558 size_t dictSize = (size_t)(ctxPtr->end - ctxPtr->base) - ctxPtr->dictLimit;
559 if (dictSize > LIZARD_DICT_SIZE) dictSize = LIZARD_DICT_SIZE;
560 Lizard_loadDict((Lizard_stream_t*)ctxPtr, (const char*)(ctxPtr->end) - dictSize, (int)dictSize);
561 }
562
563 /* Check if blocks follow each other */
564 if ((const BYTE*)source != ctxPtr->end)
565 Lizard_setExternalDict(ctxPtr, (const BYTE*)source);
566
567 /* Check overlapping input/dictionary space */
568 { const BYTE* sourceEnd = (const BYTE*) source + inputSize;
569 const BYTE* const dictBegin = ctxPtr->dictBase + ctxPtr->lowLimit;
570 const BYTE* const dictEnd = ctxPtr->dictBase + ctxPtr->dictLimit;
571 if ((sourceEnd > dictBegin) && ((const BYTE*)source < dictEnd)) {
572 if (sourceEnd > dictEnd) sourceEnd = dictEnd;
573 ctxPtr->lowLimit = (U32)(sourceEnd - ctxPtr->dictBase);
574 if (ctxPtr->dictLimit - ctxPtr->lowLimit < 4) ctxPtr->lowLimit = ctxPtr->dictLimit;
575 }
576 }
577
578 return Lizard_compress_generic (ctxPtr, source, dest, inputSize, maxOutputSize);
579 }
580
581
Lizard_compress_extState(void * state,const char * src,char * dst,int srcSize,int maxDstSize,int compressionLevel)582 int Lizard_compress_extState (void* state, const char* src, char* dst, int srcSize, int maxDstSize, int compressionLevel)
583 {
584 Lizard_stream_t* ctx = (Lizard_stream_t*) state;
585 if (((size_t)(state)&(sizeof(void*)-1)) != 0) return 0; /* Error : state is not aligned for pointers (32 or 64 bits) */
586
587 /* initialize stream */
588 Lizard_initStream(ctx, compressionLevel);
589 Lizard_init ((Lizard_stream_t*)state, (const BYTE*)src);
590
591 return Lizard_compress_generic (state, src, dst, srcSize, maxDstSize);
592 }
593
594
Lizard_compress(const char * src,char * dst,int srcSize,int maxDstSize,int compressionLevel)595 int Lizard_compress(const char* src, char* dst, int srcSize, int maxDstSize, int compressionLevel)
596 {
597 int cSize;
598 Lizard_stream_t* statePtr = Lizard_createStream(compressionLevel);
599
600 if (!statePtr) return 0;
601 cSize = Lizard_compress_extState(statePtr, src, dst, srcSize, maxDstSize, compressionLevel);
602
603 Lizard_freeStream(statePtr);
604 return cSize;
605 }
606
607
608 /**************************************
609 * Level1 functions
610 **************************************/
Lizard_compress_extState_MinLevel(void * state,const char * source,char * dest,int inputSize,int maxOutputSize)611 int Lizard_compress_extState_MinLevel(void* state, const char* source, char* dest, int inputSize, int maxOutputSize)
612 {
613 return Lizard_compress_extState(state, source, dest, inputSize, maxOutputSize, LIZARD_MIN_CLEVEL);
614 }
615
Lizard_compress_MinLevel(const char * source,char * dest,int inputSize,int maxOutputSize)616 int Lizard_compress_MinLevel(const char* source, char* dest, int inputSize, int maxOutputSize)
617 {
618 return Lizard_compress(source, dest, inputSize, maxOutputSize, LIZARD_MIN_CLEVEL);
619 }
620
Lizard_createStream_MinLevel(void)621 Lizard_stream_t* Lizard_createStream_MinLevel(void)
622 {
623 return Lizard_createStream(LIZARD_MIN_CLEVEL);
624 }
625
Lizard_resetStream_MinLevel(Lizard_stream_t * Lizard_stream)626 Lizard_stream_t* Lizard_resetStream_MinLevel(Lizard_stream_t* Lizard_stream)
627 {
628 return Lizard_resetStream (Lizard_stream, LIZARD_MIN_CLEVEL);
629 }
630