1/*
2 LZ4 - Fast LZ compression algorithm
3 Copyright (C) 2011-2017, Yann Collet.
4
5 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
6
7 Redistribution and use in source and binary forms, with or without
8 modification, are permitted provided that the following conditions are
9 met:
10
11 * Redistributions of source code must retain the above copyright
12 notice, this list of conditions and the following disclaimer.
13 * Redistributions in binary form must reproduce the above
14 copyright notice, this list of conditions and the following disclaimer
15 in the documentation and/or other materials provided with the
16 distribution.
17
18 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29
30 You can contact the author at :
31 - LZ4 homepage : http://www.lz4.org
32 - LZ4 source repository : https://github.com/lz4/lz4
33*/
34
35
36/*-************************************
37* Tuning parameters
38**************************************/
39/*
40 * LZ4_HEAPMODE :
41 * Select how default compression functions will allocate memory for their hash table,
42 * in memory stack (0:default, fastest), or in memory heap (1:requires malloc()).
43 */
44#ifndef LZ4_HEAPMODE
45# define LZ4_HEAPMODE 0
46#endif
47
48/*
49 * ACCELERATION_DEFAULT :
50 * Select "acceleration" for LZ4_compress_fast() when parameter value <= 0
51 */
52#define ACCELERATION_DEFAULT 1
53
54
55/*-************************************
56* CPU Feature Detection
57**************************************/
58/* LZ4_FORCE_MEMORY_ACCESS
59 * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable.
60 * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal.
61 * The below switch allow to select different access method for improved performance.
62 * Method 0 (default) : use `memcpy()`. Safe and portable.
63 * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable).
64 * This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`.
65 * Method 2 : direct access. This method is portable but violate C standard.
66 * It can generate buggy code on targets which assembly generation depends on alignment.
67 * But in some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6)
68 * See https://fastcompression.blogspot.fr/2015/08/accessing-unaligned-memory.html for details.
69 * Prefer these methods in priority order (0 > 1 > 2)
70 */
71#ifndef LZ4_FORCE_MEMORY_ACCESS /* can be defined externally */
72# if defined(__GNUC__) && ( defined(__ARM_ARCH_6__) || defined(__ARM_ARCH_6J__) || defined(__ARM_ARCH_6K__) || defined(__ARM_ARCH_6Z__) || defined(__ARM_ARCH_6ZK__) || defined(__ARM_ARCH_6T2__) )
73# define LZ4_FORCE_MEMORY_ACCESS 2
74# elif defined(__INTEL_COMPILER) || defined(__GNUC__)
75# define LZ4_FORCE_MEMORY_ACCESS 1
76# endif
77#endif
78
79/*
80 * LZ4_FORCE_SW_BITCOUNT
81 * Define this parameter if your target system or compiler does not support hardware bit count
82 */
83#if defined(_MSC_VER) && defined(_WIN32_WCE) /* Visual Studio for Windows CE does not support Hardware bit count */
84# define LZ4_FORCE_SW_BITCOUNT
85#endif
86
87
88
89/*-************************************
90* Dependency
91**************************************/
92#include "lz4.h"
93/* see also "memory routines" below */
94
95
96/*-************************************
97* Compiler Options
98**************************************/
99#ifdef _MSC_VER /* Visual Studio */
100# include <intrin.h>
101# pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
102# pragma warning(disable : 4293) /* disable: C4293: too large shift (32-bits) */
103#endif /* _MSC_VER */
104
105#ifndef LZ4_FORCE_INLINE
106# ifdef _MSC_VER /* Visual Studio */
107# define LZ4_FORCE_INLINE static __forceinline
108# else
109# if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
110# ifdef __GNUC__
111# define LZ4_FORCE_INLINE static inline __attribute__((always_inline))
112# else
113# define LZ4_FORCE_INLINE static inline
114# endif
115# else
116# define LZ4_FORCE_INLINE static
117# endif /* __STDC_VERSION__ */
118# endif /* _MSC_VER */
119#endif /* LZ4_FORCE_INLINE */
120
121/* LZ4_FORCE_O2_GCC_PPC64LE and LZ4_FORCE_O2_INLINE_GCC_PPC64LE
122 * Gcc on ppc64le generates an unrolled SIMDized loop for LZ4_wildCopy,
123 * together with a simple 8-byte copy loop as a fall-back path.
124 * However, this optimization hurts the decompression speed by >30%,
125 * because the execution does not go to the optimized loop
126 * for typical compressible data, and all of the preamble checks
127 * before going to the fall-back path become useless overhead.
128 * This optimization happens only with the -O3 flag, and -O2 generates
129 * a simple 8-byte copy loop.
130 * With gcc on ppc64le, all of the LZ4_decompress_* and LZ4_wildCopy
131 * functions are annotated with __attribute__((optimize("O2"))),
132 * and also LZ4_wildCopy is forcibly inlined, so that the O2 attribute
133 * of LZ4_wildCopy does not affect the compression speed.
134 */
135#if defined(__PPC64__) && defined(__LITTLE_ENDIAN__) && defined(__GNUC__)
136# define LZ4_FORCE_O2_GCC_PPC64LE __attribute__((optimize("O2")))
137# define LZ4_FORCE_O2_INLINE_GCC_PPC64LE __attribute__((optimize("O2"))) LZ4_FORCE_INLINE
138#else
139# define LZ4_FORCE_O2_GCC_PPC64LE
140# define LZ4_FORCE_O2_INLINE_GCC_PPC64LE static
141#endif
142
143#if (defined(__GNUC__) && (__GNUC__ >= 3)) || (defined(__INTEL_COMPILER) && (__INTEL_COMPILER >= 800)) || defined(__clang__)
144# define expect(expr,value) (__builtin_expect ((expr),(value)) )
145#else
146# define expect(expr,value) (expr)
147#endif
148
149#define likely(expr) expect((expr) != 0, 1)
150#define unlikely(expr) expect((expr) != 0, 0)
151
152
153/*-************************************
154* Memory routines
155**************************************/
156#include <stdlib.h> /* malloc, calloc, free */
157#define ALLOCATOR(n,s) calloc(n,s)
158#define FREEMEM free
159#include <string.h> /* memset, memcpy */
160#define MEM_INIT memset
161
162
163/*-************************************
164* Basic Types
165**************************************/
166#if defined(__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
167# include <stdint.h>
168 typedef uint8_t BYTE;
169 typedef uint16_t U16;
170 typedef uint32_t U32;
171 typedef int32_t S32;
172 typedef uint64_t U64;
173 typedef uintptr_t uptrval;
174#else
175 typedef unsigned char BYTE;
176 typedef unsigned short U16;
177 typedef unsigned int U32;
178 typedef signed int S32;
179 typedef unsigned long long U64;
180 typedef size_t uptrval; /* generally true, except OpenVMS-64 */
181#endif
182
183#if defined(__x86_64__)
184 typedef U64 reg_t; /* 64-bits in x32 mode */
185#else
186 typedef size_t reg_t; /* 32-bits in x32 mode */
187#endif
188
189/*-************************************
190* Reading and writing into memory
191**************************************/
192static unsigned LZ4_isLittleEndian(void)
193{
194 const union { U32 u; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */
195 return one.c[0];
196}
197
198
199#if defined(LZ4_FORCE_MEMORY_ACCESS) && (LZ4_FORCE_MEMORY_ACCESS==2)
200/* lie to the compiler about data alignment; use with caution */
201
202static U16 LZ4_read16(const void* memPtr) { return *(const U16*) memPtr; }
203static U32 LZ4_read32(const void* memPtr) { return *(const U32*) memPtr; }
204static reg_t LZ4_read_ARCH(const void* memPtr) { return *(const reg_t*) memPtr; }
205
206static void LZ4_write16(void* memPtr, U16 value) { *(U16*)memPtr = value; }
207static void LZ4_write32(void* memPtr, U32 value) { *(U32*)memPtr = value; }
208
209#elif defined(LZ4_FORCE_MEMORY_ACCESS) && (LZ4_FORCE_MEMORY_ACCESS==1)
210
211/* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */
212/* currently only defined for gcc and icc */
213typedef union { U16 u16; U32 u32; reg_t uArch; } __attribute__((packed)) unalign;
214
215static U16 LZ4_read16(const void* ptr) { return ((const unalign*)ptr)->u16; }
216static U32 LZ4_read32(const void* ptr) { return ((const unalign*)ptr)->u32; }
217static reg_t LZ4_read_ARCH(const void* ptr) { return ((const unalign*)ptr)->uArch; }
218
219static void LZ4_write16(void* memPtr, U16 value) { ((unalign*)memPtr)->u16 = value; }
220static void LZ4_write32(void* memPtr, U32 value) { ((unalign*)memPtr)->u32 = value; }
221
222#else /* safe and portable access through memcpy() */
223
224static U16 LZ4_read16(const void* memPtr)
225{
226 U16 val; memcpy(&val, memPtr, sizeof(val)); return val;
227}
228
229static U32 LZ4_read32(const void* memPtr)
230{
231 U32 val; memcpy(&val, memPtr, sizeof(val)); return val;
232}
233
234static reg_t LZ4_read_ARCH(const void* memPtr)
235{
236 reg_t val; memcpy(&val, memPtr, sizeof(val)); return val;
237}
238
239static void LZ4_write16(void* memPtr, U16 value)
240{
241 memcpy(memPtr, &value, sizeof(value));
242}
243
244static void LZ4_write32(void* memPtr, U32 value)
245{
246 memcpy(memPtr, &value, sizeof(value));
247}
248
249#endif /* LZ4_FORCE_MEMORY_ACCESS */
250
251
252static U16 LZ4_readLE16(const void* memPtr)
253{
254 if (LZ4_isLittleEndian()) {
255 return LZ4_read16(memPtr);
256 } else {
257 const BYTE* p = (const BYTE*)memPtr;
258 return (U16)((U16)p[0] + (p[1]<<8));
259 }
260}
261
262static void LZ4_writeLE16(void* memPtr, U16 value)
263{
264 if (LZ4_isLittleEndian()) {
265 LZ4_write16(memPtr, value);
266 } else {
267 BYTE* p = (BYTE*)memPtr;
268 p[0] = (BYTE) value;
269 p[1] = (BYTE)(value>>8);
270 }
271}
272
273static void LZ4_copy8(void* dst, const void* src)
274{
275 memcpy(dst,src,8);
276}
277
278/* customized variant of memcpy, which can overwrite up to 8 bytes beyond dstEnd */
279LZ4_FORCE_O2_INLINE_GCC_PPC64LE
280void LZ4_wildCopy(void* dstPtr, const void* srcPtr, void* dstEnd)
281{
282 BYTE* d = (BYTE*)dstPtr;
283 const BYTE* s = (const BYTE*)srcPtr;
284 BYTE* const e = (BYTE*)dstEnd;
285
286 do { LZ4_copy8(d,s); d+=8; s+=8; } while (d<e);
287}
288
289
290/*-************************************
291* Common Constants
292**************************************/
293#define MINMATCH 4
294
295#define WILDCOPYLENGTH 8
296#define LASTLITERALS 5
297#define MFLIMIT (WILDCOPYLENGTH+MINMATCH)
298static const int LZ4_minLength = (MFLIMIT+1);
299
300#define KB *(1 <<10)
301#define MB *(1 <<20)
302#define GB *(1U<<30)
303
304#define MAXD_LOG 16
305#define MAX_DISTANCE ((1 << MAXD_LOG) - 1)
306
307#define ML_BITS 4
308#define ML_MASK ((1U<<ML_BITS)-1)
309#define RUN_BITS (8-ML_BITS)
310#define RUN_MASK ((1U<<RUN_BITS)-1)
311
312
313/*-************************************
314* Error detection
315**************************************/
316#if defined(LZ4_DEBUG) && (LZ4_DEBUG>=1)
317# include <assert.h>
318#else
319# ifndef assert
320# define assert(condition) ((void)0)
321# endif
322#endif
323
324#define LZ4_STATIC_ASSERT(c) { enum { LZ4_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
325
326#if defined(LZ4_DEBUG) && (LZ4_DEBUG>=2)
327# include <stdio.h>
328static int g_debuglog_enable = 1;
329# define DEBUGLOG(l, ...) { \
330 if ((g_debuglog_enable) && (l<=LZ4_DEBUG)) { \
331 fprintf(stderr, __FILE__ ": "); \
332 fprintf(stderr, __VA_ARGS__); \
333 fprintf(stderr, " \n"); \
334 } }
335#else
336# define DEBUGLOG(l, ...) {} /* disabled */
337#endif
338
339
340/*-************************************
341* Common functions
342**************************************/
343static unsigned LZ4_NbCommonBytes (reg_t val)
344{
345 if (LZ4_isLittleEndian()) {
346 if (sizeof(val)==8) {
347# if defined(_MSC_VER) && defined(_WIN64) && !defined(LZ4_FORCE_SW_BITCOUNT)
348 unsigned long r = 0;
349 _BitScanForward64( &r, (U64)val );
350 return (int)(r>>3);
351# elif (defined(__clang__) || (defined(__GNUC__) && (__GNUC__>=3))) && !defined(LZ4_FORCE_SW_BITCOUNT)
352 return (__builtin_ctzll((U64)val) >> 3);
353# else
354 static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2,
355 0, 3, 1, 3, 1, 4, 2, 7,
356 0, 2, 3, 6, 1, 5, 3, 5,
357 1, 3, 4, 4, 2, 5, 6, 7,
358 7, 0, 1, 2, 3, 3, 4, 6,
359 2, 6, 5, 5, 3, 4, 5, 6,
360 7, 1, 2, 4, 6, 4, 4, 5,
361 7, 2, 6, 5, 7, 6, 7, 7 };
362 return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58];
363# endif
364 } else /* 32 bits */ {
365# if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
366 unsigned long r;
367 _BitScanForward( &r, (U32)val );
368 return (int)(r>>3);
369# elif (defined(__clang__) || (defined(__GNUC__) && (__GNUC__>=3))) && !defined(LZ4_FORCE_SW_BITCOUNT)
370 return (__builtin_ctz((U32)val) >> 3);
371# else
372 static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0,
373 3, 2, 2, 1, 3, 2, 0, 1,
374 3, 3, 1, 2, 2, 2, 2, 0,
375 3, 1, 2, 0, 1, 0, 1, 1 };
376 return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];
377# endif
378 }
379 } else /* Big Endian CPU */ {
380 if (sizeof(val)==8) { /* 64-bits */
381# if defined(_MSC_VER) && defined(_WIN64) && !defined(LZ4_FORCE_SW_BITCOUNT)
382 unsigned long r = 0;
383 _BitScanReverse64( &r, val );
384 return (unsigned)(r>>3);
385# elif (defined(__clang__) || (defined(__GNUC__) && (__GNUC__>=3))) && !defined(LZ4_FORCE_SW_BITCOUNT)
386 return (__builtin_clzll((U64)val) >> 3);
387# else
388 static const U32 by32 = sizeof(val)*4; /* 32 on 64 bits (goal), 16 on 32 bits.
389 Just to avoid some static analyzer complaining about shift by 32 on 32-bits target.
390 Note that this code path is never triggered in 32-bits mode. */
391 unsigned r;
392 if (!(val>>by32)) { r=4; } else { r=0; val>>=by32; }
393 if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }
394 r += (!val);
395 return r;
396# endif
397 } else /* 32 bits */ {
398# if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
399 unsigned long r = 0;
400 _BitScanReverse( &r, (unsigned long)val );
401 return (unsigned)(r>>3);
402# elif (defined(__clang__) || (defined(__GNUC__) && (__GNUC__>=3))) && !defined(LZ4_FORCE_SW_BITCOUNT)
403 return (__builtin_clz((U32)val) >> 3);
404# else
405 unsigned r;
406 if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }
407 r += (!val);
408 return r;
409# endif
410 }
411 }
412}
413
414#define STEPSIZE sizeof(reg_t)
415LZ4_FORCE_INLINE
416unsigned LZ4_count(const BYTE* pIn, const BYTE* pMatch, const BYTE* pInLimit)
417{
418 const BYTE* const pStart = pIn;
419
420 if (likely(pIn < pInLimit-(STEPSIZE-1))) {
421 reg_t const diff = LZ4_read_ARCH(pMatch) ^ LZ4_read_ARCH(pIn);
422 if (!diff) {
423 pIn+=STEPSIZE; pMatch+=STEPSIZE;
424 } else {
425 return LZ4_NbCommonBytes(diff);
426 } }
427
428 while (likely(pIn < pInLimit-(STEPSIZE-1))) {
429 reg_t const diff = LZ4_read_ARCH(pMatch) ^ LZ4_read_ARCH(pIn);
430 if (!diff) { pIn+=STEPSIZE; pMatch+=STEPSIZE; continue; }
431 pIn += LZ4_NbCommonBytes(diff);
432 return (unsigned)(pIn - pStart);
433 }
434
435 if ((STEPSIZE==8) && (pIn<(pInLimit-3)) && (LZ4_read32(pMatch) == LZ4_read32(pIn))) { pIn+=4; pMatch+=4; }
436 if ((pIn<(pInLimit-1)) && (LZ4_read16(pMatch) == LZ4_read16(pIn))) { pIn+=2; pMatch+=2; }
437 if ((pIn<pInLimit) && (*pMatch == *pIn)) pIn++;
438 return (unsigned)(pIn - pStart);
439}
440
441
442#ifndef LZ4_COMMONDEFS_ONLY
443/*-************************************
444* Local Constants
445**************************************/
446static const int LZ4_64Klimit = ((64 KB) + (MFLIMIT-1));
447static const U32 LZ4_skipTrigger = 6; /* Increase this value ==> compression run slower on incompressible data */
448
449
450/*-************************************
451* Local Structures and types
452**************************************/
453typedef enum { notLimited = 0, limitedOutput = 1 } limitedOutput_directive;
454typedef enum { byPtr, byU32, byU16 } tableType_t;
455
456typedef enum { noDict = 0, withPrefix64k, usingExtDict } dict_directive;
457typedef enum { noDictIssue = 0, dictSmall } dictIssue_directive;
458
459typedef enum { endOnOutputSize = 0, endOnInputSize = 1 } endCondition_directive;
460typedef enum { full = 0, partial = 1 } earlyEnd_directive;
461
462
463/*-************************************
464* Local Utils
465**************************************/
466int LZ4_versionNumber (void) { return LZ4_VERSION_NUMBER; }
467const char* LZ4_versionString(void) { return LZ4_VERSION_STRING; }
468int LZ4_compressBound(int isize) { return LZ4_COMPRESSBOUND(isize); }
469int LZ4_sizeofState() { return LZ4_STREAMSIZE; }
470
471
472/*-******************************
473* Compression functions
474********************************/
475static U32 LZ4_hash4(U32 sequence, tableType_t const tableType)
476{
477 if (tableType == byU16)
478 return ((sequence * 2654435761U) >> ((MINMATCH*8)-(LZ4_HASHLOG+1)));
479 else
480 return ((sequence * 2654435761U) >> ((MINMATCH*8)-LZ4_HASHLOG));
481}
482
483static U32 LZ4_hash5(U64 sequence, tableType_t const tableType)
484{
485 static const U64 prime5bytes = 889523592379ULL;
486 static const U64 prime8bytes = 11400714785074694791ULL;
487 const U32 hashLog = (tableType == byU16) ? LZ4_HASHLOG+1 : LZ4_HASHLOG;
488 if (LZ4_isLittleEndian())
489 return (U32)(((sequence << 24) * prime5bytes) >> (64 - hashLog));
490 else
491 return (U32)(((sequence >> 24) * prime8bytes) >> (64 - hashLog));
492}
493
494LZ4_FORCE_INLINE U32 LZ4_hashPosition(const void* const p, tableType_t const tableType)
495{
496 if ((sizeof(reg_t)==8) && (tableType != byU16)) return LZ4_hash5(LZ4_read_ARCH(p), tableType);
497 return LZ4_hash4(LZ4_read32(p), tableType);
498}
499
500static void LZ4_putPositionOnHash(const BYTE* p, U32 h, void* tableBase, tableType_t const tableType, const BYTE* srcBase)
501{
502 switch (tableType)
503 {
504 case byPtr: { const BYTE** hashTable = (const BYTE**)tableBase; hashTable[h] = p; return; }
505 case byU32: { U32* hashTable = (U32*) tableBase; hashTable[h] = (U32)(p-srcBase); return; }
506 case byU16: { U16* hashTable = (U16*) tableBase; hashTable[h] = (U16)(p-srcBase); return; }
507 }
508}
509
510LZ4_FORCE_INLINE void LZ4_putPosition(const BYTE* p, void* tableBase, tableType_t tableType, const BYTE* srcBase)
511{
512 U32 const h = LZ4_hashPosition(p, tableType);
513 LZ4_putPositionOnHash(p, h, tableBase, tableType, srcBase);
514}
515
516static const BYTE* LZ4_getPositionOnHash(U32 h, void* tableBase, tableType_t tableType, const BYTE* srcBase)
517{
518 if (tableType == byPtr) { const BYTE** hashTable = (const BYTE**) tableBase; return hashTable[h]; }
519 if (tableType == byU32) { const U32* const hashTable = (U32*) tableBase; return hashTable[h] + srcBase; }
520 { const U16* const hashTable = (U16*) tableBase; return hashTable[h] + srcBase; } /* default, to ensure a return */
521}
522
523LZ4_FORCE_INLINE const BYTE* LZ4_getPosition(const BYTE* p, void* tableBase, tableType_t tableType, const BYTE* srcBase)
524{
525 U32 const h = LZ4_hashPosition(p, tableType);
526 return LZ4_getPositionOnHash(h, tableBase, tableType, srcBase);
527}
528
529
530/** LZ4_compress_generic() :
531 inlined, to ensure branches are decided at compilation time */
532LZ4_FORCE_INLINE int LZ4_compress_generic(
533 LZ4_stream_t_internal* const cctx,
534 const char* const source,
535 char* const dest,
536 const int inputSize,
537 const int maxOutputSize,
538 const limitedOutput_directive outputLimited,
539 const tableType_t tableType,
540 const dict_directive dict,
541 const dictIssue_directive dictIssue,
542 const U32 acceleration)
543{
544 const BYTE* ip = (const BYTE*) source;
545 const BYTE* base;
546 const BYTE* lowLimit;
547 const BYTE* const lowRefLimit = ip - cctx->dictSize;
548 const BYTE* const dictionary = cctx->dictionary;
549 const BYTE* const dictEnd = dictionary + cctx->dictSize;
550 const ptrdiff_t dictDelta = dictEnd - (const BYTE*)source;
551 const BYTE* anchor = (const BYTE*) source;
552 const BYTE* const iend = ip + inputSize;
553 const BYTE* const mflimit = iend - MFLIMIT;
554 const BYTE* const matchlimit = iend - LASTLITERALS;
555
556 BYTE* op = (BYTE*) dest;
557 BYTE* const olimit = op + maxOutputSize;
558
559 U32 forwardH;
560
561 /* Init conditions */
562 if ((U32)inputSize > (U32)LZ4_MAX_INPUT_SIZE) return 0; /* Unsupported inputSize, too large (or negative) */
563 switch(dict)
564 {
565 case noDict:
566 default:
567 base = (const BYTE*)source;
568 lowLimit = (const BYTE*)source;
569 break;
570 case withPrefix64k:
571 base = (const BYTE*)source - cctx->currentOffset;
572 lowLimit = (const BYTE*)source - cctx->dictSize;
573 break;
574 case usingExtDict:
575 base = (const BYTE*)source - cctx->currentOffset;
576 lowLimit = (const BYTE*)source;
577 break;
578 }
579 if ((tableType == byU16) && (inputSize>=LZ4_64Klimit)) return 0; /* Size too large (not within 64K limit) */
580 if (inputSize<LZ4_minLength) goto _last_literals; /* Input too small, no compression (all literals) */
581
582 /* First Byte */
583 LZ4_putPosition(ip, cctx->hashTable, tableType, base);
584 ip++; forwardH = LZ4_hashPosition(ip, tableType);
585
586 /* Main Loop */
587 for ( ; ; ) {
588 ptrdiff_t refDelta = 0;
589 const BYTE* match;
590 BYTE* token;
591
592 /* Find a match */
593 { const BYTE* forwardIp = ip;
594 unsigned step = 1;
595 unsigned searchMatchNb = acceleration << LZ4_skipTrigger;
596 do {
597 U32 const h = forwardH;
598 ip = forwardIp;
599 forwardIp += step;
600 step = (searchMatchNb++ >> LZ4_skipTrigger);
601
602 if (unlikely(forwardIp > mflimit)) goto _last_literals;
603
604 match = LZ4_getPositionOnHash(h, cctx->hashTable, tableType, base);
605 if (dict==usingExtDict) {
606 if (match < (const BYTE*)source) {
607 refDelta = dictDelta;
608 lowLimit = dictionary;
609 } else {
610 refDelta = 0;
611 lowLimit = (const BYTE*)source;
612 } }
613 forwardH = LZ4_hashPosition(forwardIp, tableType);
614 LZ4_putPositionOnHash(ip, h, cctx->hashTable, tableType, base);
615
616 } while ( ((dictIssue==dictSmall) ? (match < lowRefLimit) : 0)
617 || ((tableType==byU16) ? 0 : (match + MAX_DISTANCE < ip))
618 || (LZ4_read32(match+refDelta) != LZ4_read32(ip)) );
619 }
620
621 /* Catch up */
622 while (((ip>anchor) & (match+refDelta > lowLimit)) && (unlikely(ip[-1]==match[refDelta-1]))) { ip--; match--; }
623
624 /* Encode Literals */
625 { unsigned const litLength = (unsigned)(ip - anchor);
626 token = op++;
627 if ((outputLimited) && /* Check output buffer overflow */
628 (unlikely(op + litLength + (2 + 1 + LASTLITERALS) + (litLength/255) > olimit)))
629 return 0;
630 if (litLength >= RUN_MASK) {
631 int len = (int)litLength-RUN_MASK;
632 *token = (RUN_MASK<<ML_BITS);
633 for(; len >= 255 ; len-=255) *op++ = 255;
634 *op++ = (BYTE)len;
635 }
636 else *token = (BYTE)(litLength<<ML_BITS);
637
638 /* Copy Literals */
639 LZ4_wildCopy(op, anchor, op+litLength);
640 op+=litLength;
641 }
642
643_next_match:
644 /* Encode Offset */
645 LZ4_writeLE16(op, (U16)(ip-match)); op+=2;
646
647 /* Encode MatchLength */
648 { unsigned matchCode;
649
650 if ((dict==usingExtDict) && (lowLimit==dictionary)) {
651 const BYTE* limit;
652 match += refDelta;
653 limit = ip + (dictEnd-match);
654 if (limit > matchlimit) limit = matchlimit;
655 matchCode = LZ4_count(ip+MINMATCH, match+MINMATCH, limit);
656 ip += MINMATCH + matchCode;
657 if (ip==limit) {
658 unsigned const more = LZ4_count(ip, (const BYTE*)source, matchlimit);
659 matchCode += more;
660 ip += more;
661 }
662 } else {
663 matchCode = LZ4_count(ip+MINMATCH, match+MINMATCH, matchlimit);
664 ip += MINMATCH + matchCode;
665 }
666
667 if ( outputLimited && /* Check output buffer overflow */
668 (unlikely(op + (1 + LASTLITERALS) + (matchCode>>8) > olimit)) )
669 return 0;
670 if (matchCode >= ML_MASK) {
671 *token += ML_MASK;
672 matchCode -= ML_MASK;
673 LZ4_write32(op, 0xFFFFFFFF);
674 while (matchCode >= 4*255) {
675 op+=4;
676 LZ4_write32(op, 0xFFFFFFFF);
677 matchCode -= 4*255;
678 }
679 op += matchCode / 255;
680 *op++ = (BYTE)(matchCode % 255);
681 } else
682 *token += (BYTE)(matchCode);
683 }
684
685 anchor = ip;
686
687 /* Test end of chunk */
688 if (ip > mflimit) break;
689
690 /* Fill table */
691 LZ4_putPosition(ip-2, cctx->hashTable, tableType, base);
692
693 /* Test next position */
694 match = LZ4_getPosition(ip, cctx->hashTable, tableType, base);
695 if (dict==usingExtDict) {
696 if (match < (const BYTE*)source) {
697 refDelta = dictDelta;
698 lowLimit = dictionary;
699 } else {
700 refDelta = 0;
701 lowLimit = (const BYTE*)source;
702 } }
703 LZ4_putPosition(ip, cctx->hashTable, tableType, base);
704 if ( ((dictIssue==dictSmall) ? (match>=lowRefLimit) : 1)
705 && (match+MAX_DISTANCE>=ip)
706 && (LZ4_read32(match+refDelta)==LZ4_read32(ip)) )
707 { token=op++; *token=0; goto _next_match; }
708
709 /* Prepare next loop */
710 forwardH = LZ4_hashPosition(++ip, tableType);
711 }
712
713_last_literals:
714 /* Encode Last Literals */
715 { size_t const lastRun = (size_t)(iend - anchor);
716 if ( (outputLimited) && /* Check output buffer overflow */
717 ((op - (BYTE*)dest) + lastRun + 1 + ((lastRun+255-RUN_MASK)/255) > (U32)maxOutputSize) )
718 return 0;
719 if (lastRun >= RUN_MASK) {
720 size_t accumulator = lastRun - RUN_MASK;
721 *op++ = RUN_MASK << ML_BITS;
722 for(; accumulator >= 255 ; accumulator-=255) *op++ = 255;
723 *op++ = (BYTE) accumulator;
724 } else {
725 *op++ = (BYTE)(lastRun<<ML_BITS);
726 }
727 memcpy(op, anchor, lastRun);
728 op += lastRun;
729 }
730
731 /* End */
732 return (int) (((char*)op)-dest);
733}
734
735
736int LZ4_compress_fast_extState(void* state, const char* source, char* dest, int inputSize, int maxOutputSize, int acceleration)
737{
738 LZ4_stream_t_internal* ctx = &((LZ4_stream_t*)state)->internal_donotuse;
739 LZ4_resetStream((LZ4_stream_t*)state);
740 if (acceleration < 1) acceleration = ACCELERATION_DEFAULT;
741
742 if (maxOutputSize >= LZ4_compressBound(inputSize)) {
743 if (inputSize < LZ4_64Klimit)
744 return LZ4_compress_generic(ctx, source, dest, inputSize, 0, notLimited, byU16, noDict, noDictIssue, acceleration);
745 else
746 return LZ4_compress_generic(ctx, source, dest, inputSize, 0, notLimited, (sizeof(void*)==8) ? byU32 : byPtr, noDict, noDictIssue, acceleration);
747 } else {
748 if (inputSize < LZ4_64Klimit)
749 return LZ4_compress_generic(ctx, source, dest, inputSize, maxOutputSize, limitedOutput, byU16, noDict, noDictIssue, acceleration);
750 else
751 return LZ4_compress_generic(ctx, source, dest, inputSize, maxOutputSize, limitedOutput, (sizeof(void*)==8) ? byU32 : byPtr, noDict, noDictIssue, acceleration);
752 }
753}
754
755
756int LZ4_compress_fast(const char* source, char* dest, int inputSize, int maxOutputSize, int acceleration)
757{
758#if (LZ4_HEAPMODE)
759 void* ctxPtr = ALLOCATOR(1, sizeof(LZ4_stream_t)); /* malloc-calloc always properly aligned */
760#else
761 LZ4_stream_t ctx;
762 void* const ctxPtr = &ctx;
763#endif
764
765 int const result = LZ4_compress_fast_extState(ctxPtr, source, dest, inputSize, maxOutputSize, acceleration);
766
767#if (LZ4_HEAPMODE)
768 FREEMEM(ctxPtr);
769#endif
770 return result;
771}
772
773
774int LZ4_compress_default(const char* source, char* dest, int inputSize, int maxOutputSize)
775{
776 return LZ4_compress_fast(source, dest, inputSize, maxOutputSize, 1);
777}
778
779
780/* hidden debug function */
781/* strangely enough, gcc generates faster code when this function is uncommented, even if unused */
782int LZ4_compress_fast_force(const char* source, char* dest, int inputSize, int maxOutputSize, int acceleration)
783{
784 LZ4_stream_t ctx;
785 LZ4_resetStream(&ctx);
786
787 if (inputSize < LZ4_64Klimit)
788 return LZ4_compress_generic(&ctx.internal_donotuse, source, dest, inputSize, maxOutputSize, limitedOutput, byU16, noDict, noDictIssue, acceleration);
789 else
790 return LZ4_compress_generic(&ctx.internal_donotuse, source, dest, inputSize, maxOutputSize, limitedOutput, sizeof(void*)==8 ? byU32 : byPtr, noDict, noDictIssue, acceleration);
791}
792
793
794/*-******************************
795* *_destSize() variant
796********************************/
797
798static int LZ4_compress_destSize_generic(
799 LZ4_stream_t_internal* const ctx,
800 const char* const src,
801 char* const dst,
802 int* const srcSizePtr,
803 const int targetDstSize,
804 const tableType_t tableType)
805{
806 const BYTE* ip = (const BYTE*) src;
807 const BYTE* base = (const BYTE*) src;
808 const BYTE* lowLimit = (const BYTE*) src;
809 const BYTE* anchor = ip;
810 const BYTE* const iend = ip + *srcSizePtr;
811 const BYTE* const mflimit = iend - MFLIMIT;
812 const BYTE* const matchlimit = iend - LASTLITERALS;
813
814 BYTE* op = (BYTE*) dst;
815 BYTE* const oend = op + targetDstSize;
816 BYTE* const oMaxLit = op + targetDstSize - 2 /* offset */ - 8 /* because 8+MINMATCH==MFLIMIT */ - 1 /* token */;
817 BYTE* const oMaxMatch = op + targetDstSize - (LASTLITERALS + 1 /* token */);
818 BYTE* const oMaxSeq = oMaxLit - 1 /* token */;
819
820 U32 forwardH;
821
822
823 /* Init conditions */
824 if (targetDstSize < 1) return 0; /* Impossible to store anything */
825 if ((U32)*srcSizePtr > (U32)LZ4_MAX_INPUT_SIZE) return 0; /* Unsupported input size, too large (or negative) */
826 if ((tableType == byU16) && (*srcSizePtr>=LZ4_64Klimit)) return 0; /* Size too large (not within 64K limit) */
827 if (*srcSizePtr<LZ4_minLength) goto _last_literals; /* Input too small, no compression (all literals) */
828
829 /* First Byte */
830 *srcSizePtr = 0;
831 LZ4_putPosition(ip, ctx->hashTable, tableType, base);
832 ip++; forwardH = LZ4_hashPosition(ip, tableType);
833
834 /* Main Loop */
835 for ( ; ; ) {
836 const BYTE* match;
837 BYTE* token;
838
839 /* Find a match */
840 { const BYTE* forwardIp = ip;
841 unsigned step = 1;
842 unsigned searchMatchNb = 1 << LZ4_skipTrigger;
843
844 do {
845 U32 h = forwardH;
846 ip = forwardIp;
847 forwardIp += step;
848 step = (searchMatchNb++ >> LZ4_skipTrigger);
849
850 if (unlikely(forwardIp > mflimit)) goto _last_literals;
851
852 match = LZ4_getPositionOnHash(h, ctx->hashTable, tableType, base);
853 forwardH = LZ4_hashPosition(forwardIp, tableType);
854 LZ4_putPositionOnHash(ip, h, ctx->hashTable, tableType, base);
855
856 } while ( ((tableType==byU16) ? 0 : (match + MAX_DISTANCE < ip))
857 || (LZ4_read32(match) != LZ4_read32(ip)) );
858 }
859
860 /* Catch up */
861 while ((ip>anchor) && (match > lowLimit) && (unlikely(ip[-1]==match[-1]))) { ip--; match--; }
862
863 /* Encode Literal length */
864 { unsigned litLength = (unsigned)(ip - anchor);
865 token = op++;
866 if (op + ((litLength+240)/255) + litLength > oMaxLit) {
867 /* Not enough space for a last match */
868 op--;
869 goto _last_literals;
870 }
871 if (litLength>=RUN_MASK) {
872 unsigned len = litLength - RUN_MASK;
873 *token=(RUN_MASK<<ML_BITS);
874 for(; len >= 255 ; len-=255) *op++ = 255;
875 *op++ = (BYTE)len;
876 }
877 else *token = (BYTE)(litLength<<ML_BITS);
878
879 /* Copy Literals */
880 LZ4_wildCopy(op, anchor, op+litLength);
881 op += litLength;
882 }
883
884_next_match:
885 /* Encode Offset */
886 LZ4_writeLE16(op, (U16)(ip-match)); op+=2;
887
888 /* Encode MatchLength */
889 { size_t matchLength = LZ4_count(ip+MINMATCH, match+MINMATCH, matchlimit);
890
891 if (op + ((matchLength+240)/255) > oMaxMatch) {
892 /* Match description too long : reduce it */
893 matchLength = (15-1) + (oMaxMatch-op) * 255;
894 }
895 ip += MINMATCH + matchLength;
896
897 if (matchLength>=ML_MASK) {
898 *token += ML_MASK;
899 matchLength -= ML_MASK;
900 while (matchLength >= 255) { matchLength-=255; *op++ = 255; }
901 *op++ = (BYTE)matchLength;
902 }
903 else *token += (BYTE)(matchLength);
904 }
905
906 anchor = ip;
907
908 /* Test end of block */
909 if (ip > mflimit) break;
910 if (op > oMaxSeq) break;
911
912 /* Fill table */
913 LZ4_putPosition(ip-2, ctx->hashTable, tableType, base);
914
915 /* Test next position */
916 match = LZ4_getPosition(ip, ctx->hashTable, tableType, base);
917 LZ4_putPosition(ip, ctx->hashTable, tableType, base);
918 if ( (match+MAX_DISTANCE>=ip)
919 && (LZ4_read32(match)==LZ4_read32(ip)) )
920 { token=op++; *token=0; goto _next_match; }
921
922 /* Prepare next loop */
923 forwardH = LZ4_hashPosition(++ip, tableType);
924 }
925
926_last_literals:
927 /* Encode Last Literals */
928 { size_t lastRunSize = (size_t)(iend - anchor);
929 if (op + 1 /* token */ + ((lastRunSize+240)/255) /* litLength */ + lastRunSize /* literals */ > oend) {
930 /* adapt lastRunSize to fill 'dst' */
931 lastRunSize = (oend-op) - 1;
932 lastRunSize -= (lastRunSize+240)/255;
933 }
934 ip = anchor + lastRunSize;
935
936 if (lastRunSize >= RUN_MASK) {
937 size_t accumulator = lastRunSize - RUN_MASK;
938 *op++ = RUN_MASK << ML_BITS;
939 for(; accumulator >= 255 ; accumulator-=255) *op++ = 255;
940 *op++ = (BYTE) accumulator;
941 } else {
942 *op++ = (BYTE)(lastRunSize<<ML_BITS);
943 }
944 memcpy(op, anchor, lastRunSize);
945 op += lastRunSize;
946 }
947
948 /* End */
949 *srcSizePtr = (int) (((const char*)ip)-src);
950 return (int) (((char*)op)-dst);
951}
952
953
954static int LZ4_compress_destSize_extState (LZ4_stream_t* state, const char* src, char* dst, int* srcSizePtr, int targetDstSize)
955{
956 LZ4_resetStream(state);
957
958 if (targetDstSize >= LZ4_compressBound(*srcSizePtr)) { /* compression success is guaranteed */
959 return LZ4_compress_fast_extState(state, src, dst, *srcSizePtr, targetDstSize, 1);
960 } else {
961 if (*srcSizePtr < LZ4_64Klimit)
962 return LZ4_compress_destSize_generic(&state->internal_donotuse, src, dst, srcSizePtr, targetDstSize, byU16);
963 else
964 return LZ4_compress_destSize_generic(&state->internal_donotuse, src, dst, srcSizePtr, targetDstSize, sizeof(void*)==8 ? byU32 : byPtr);
965 }
966}
967
968
969int LZ4_compress_destSize(const char* src, char* dst, int* srcSizePtr, int targetDstSize)
970{
971#if (LZ4_HEAPMODE)
972 LZ4_stream_t* ctx = (LZ4_stream_t*)ALLOCATOR(1, sizeof(LZ4_stream_t)); /* malloc-calloc always properly aligned */
973#else
974 LZ4_stream_t ctxBody;
975 LZ4_stream_t* ctx = &ctxBody;
976#endif
977
978 int result = LZ4_compress_destSize_extState(ctx, src, dst, srcSizePtr, targetDstSize);
979
980#if (LZ4_HEAPMODE)
981 FREEMEM(ctx);
982#endif
983 return result;
984}
985
986
987
988/*-******************************
989* Streaming functions
990********************************/
991
992LZ4_stream_t* LZ4_createStream(void)
993{
994 LZ4_stream_t* lz4s = (LZ4_stream_t*)ALLOCATOR(8, LZ4_STREAMSIZE_U64);
995 LZ4_STATIC_ASSERT(LZ4_STREAMSIZE >= sizeof(LZ4_stream_t_internal)); /* A compilation error here means LZ4_STREAMSIZE is not large enough */
996 LZ4_resetStream(lz4s);
997 return lz4s;
998}
999
1000void LZ4_resetStream (LZ4_stream_t* LZ4_stream)
1001{
1002 DEBUGLOG(4, "LZ4_resetStream");
1003 MEM_INIT(LZ4_stream, 0, sizeof(LZ4_stream_t));
1004}
1005
1006int LZ4_freeStream (LZ4_stream_t* LZ4_stream)
1007{
1008 if (!LZ4_stream) return 0; /* support free on NULL */
1009 FREEMEM(LZ4_stream);
1010 return (0);
1011}
1012
1013
1014#define HASH_UNIT sizeof(reg_t)
1015int LZ4_loadDict (LZ4_stream_t* LZ4_dict, const char* dictionary, int dictSize)
1016{
1017 LZ4_stream_t_internal* dict = &LZ4_dict->internal_donotuse;
1018 const BYTE* p = (const BYTE*)dictionary;
1019 const BYTE* const dictEnd = p + dictSize;
1020 const BYTE* base;
1021
1022 if ((dict->initCheck) || (dict->currentOffset > 1 GB)) /* Uninitialized structure, or reuse overflow */
1023 LZ4_resetStream(LZ4_dict);
1024
1025 if (dictSize < (int)HASH_UNIT) {
1026 dict->dictionary = NULL;
1027 dict->dictSize = 0;
1028 return 0;
1029 }
1030
1031 if ((dictEnd - p) > 64 KB) p = dictEnd - 64 KB;
1032 dict->currentOffset += 64 KB;
1033 base = p - dict->currentOffset;
1034 dict->dictionary = p;
1035 dict->dictSize = (U32)(dictEnd - p);
1036 dict->currentOffset += dict->dictSize;
1037
1038 while (p <= dictEnd-HASH_UNIT) {
1039 LZ4_putPosition(p, dict->hashTable, byU32, base);
1040 p+=3;
1041 }
1042
1043 return dict->dictSize;
1044}
1045
1046
1047static void LZ4_renormDictT(LZ4_stream_t_internal* LZ4_dict, const BYTE* src)
1048{
1049 if ((LZ4_dict->currentOffset > 0x80000000) ||
1050 ((uptrval)LZ4_dict->currentOffset > (uptrval)src)) { /* address space overflow */
1051 /* rescale hash table */
1052 U32 const delta = LZ4_dict->currentOffset - 64 KB;
1053 const BYTE* dictEnd = LZ4_dict->dictionary + LZ4_dict->dictSize;
1054 int i;
1055 for (i=0; i<LZ4_HASH_SIZE_U32; i++) {
1056 if (LZ4_dict->hashTable[i] < delta) LZ4_dict->hashTable[i]=0;
1057 else LZ4_dict->hashTable[i] -= delta;
1058 }
1059 LZ4_dict->currentOffset = 64 KB;
1060 if (LZ4_dict->dictSize > 64 KB) LZ4_dict->dictSize = 64 KB;
1061 LZ4_dict->dictionary = dictEnd - LZ4_dict->dictSize;
1062 }
1063}
1064
1065
1066int LZ4_compress_fast_continue (LZ4_stream_t* LZ4_stream, const char* source, char* dest, int inputSize, int maxOutputSize, int acceleration)
1067{
1068 LZ4_stream_t_internal* streamPtr = &LZ4_stream->internal_donotuse;
1069 const BYTE* const dictEnd = streamPtr->dictionary + streamPtr->dictSize;
1070
1071 const BYTE* smallest = (const BYTE*) source;
1072 if (streamPtr->initCheck) return 0; /* Uninitialized structure detected */
1073 if ((streamPtr->dictSize>0) && (smallest>dictEnd)) smallest = dictEnd;
1074 LZ4_renormDictT(streamPtr, smallest);
1075 if (acceleration < 1) acceleration = ACCELERATION_DEFAULT;
1076
1077 /* Check overlapping input/dictionary space */
1078 { const BYTE* sourceEnd = (const BYTE*) source + inputSize;
1079 if ((sourceEnd > streamPtr->dictionary) && (sourceEnd < dictEnd)) {
1080 streamPtr->dictSize = (U32)(dictEnd - sourceEnd);
1081 if (streamPtr->dictSize > 64 KB) streamPtr->dictSize = 64 KB;
1082 if (streamPtr->dictSize < 4) streamPtr->dictSize = 0;
1083 streamPtr->dictionary = dictEnd - streamPtr->dictSize;
1084 }
1085 }
1086
1087 /* prefix mode : source data follows dictionary */
1088 if (dictEnd == (const BYTE*)source) {
1089 int result;
1090 if ((streamPtr->dictSize < 64 KB) && (streamPtr->dictSize < streamPtr->currentOffset))
1091 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, withPrefix64k, dictSmall, acceleration);
1092 else
1093 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, withPrefix64k, noDictIssue, acceleration);
1094 streamPtr->dictSize += (U32)inputSize;
1095 streamPtr->currentOffset += (U32)inputSize;
1096 return result;
1097 }
1098
1099 /* external dictionary mode */
1100 { int result;
1101 if ((streamPtr->dictSize < 64 KB) && (streamPtr->dictSize < streamPtr->currentOffset))
1102 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, usingExtDict, dictSmall, acceleration);
1103 else
1104 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, maxOutputSize, limitedOutput, byU32, usingExtDict, noDictIssue, acceleration);
1105 streamPtr->dictionary = (const BYTE*)source;
1106 streamPtr->dictSize = (U32)inputSize;
1107 streamPtr->currentOffset += (U32)inputSize;
1108 return result;
1109 }
1110}
1111
1112
1113/* Hidden debug function, to force external dictionary mode */
1114int LZ4_compress_forceExtDict (LZ4_stream_t* LZ4_dict, const char* source, char* dest, int inputSize)
1115{
1116 LZ4_stream_t_internal* streamPtr = &LZ4_dict->internal_donotuse;
1117 int result;
1118 const BYTE* const dictEnd = streamPtr->dictionary + streamPtr->dictSize;
1119
1120 const BYTE* smallest = dictEnd;
1121 if (smallest > (const BYTE*) source) smallest = (const BYTE*) source;
1122 LZ4_renormDictT(streamPtr, smallest);
1123
1124 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, 0, notLimited, byU32, usingExtDict, noDictIssue, 1);
1125
1126 streamPtr->dictionary = (const BYTE*)source;
1127 streamPtr->dictSize = (U32)inputSize;
1128 streamPtr->currentOffset += (U32)inputSize;
1129
1130 return result;
1131}
1132
1133
1134/*! LZ4_saveDict() :
1135 * If previously compressed data block is not guaranteed to remain available at its memory location,
1136 * save it into a safer place (char* safeBuffer).
1137 * Note : you don't need to call LZ4_loadDict() afterwards,
1138 * dictionary is immediately usable, you can therefore call LZ4_compress_fast_continue().
1139 * Return : saved dictionary size in bytes (necessarily <= dictSize), or 0 if error.
1140 */
1141int LZ4_saveDict (LZ4_stream_t* LZ4_dict, char* safeBuffer, int dictSize)
1142{
1143 LZ4_stream_t_internal* const dict = &LZ4_dict->internal_donotuse;
1144 const BYTE* const previousDictEnd = dict->dictionary + dict->dictSize;
1145
1146 if ((U32)dictSize > 64 KB) dictSize = 64 KB; /* useless to define a dictionary > 64 KB */
1147 if ((U32)dictSize > dict->dictSize) dictSize = dict->dictSize;
1148
1149 memmove(safeBuffer, previousDictEnd - dictSize, dictSize);
1150
1151 dict->dictionary = (const BYTE*)safeBuffer;
1152 dict->dictSize = (U32)dictSize;
1153
1154 return dictSize;
1155}
1156
1157
1158
1159/*-*****************************
1160* Decompression functions
1161*******************************/
1162/*! LZ4_decompress_generic() :
1163 * This generic decompression function covers all use cases.
1164 * It shall be instantiated several times, using different sets of directives.
1165 * Note that it is important for performance that this function really get inlined,
1166 * in order to remove useless branches during compilation optimization.
1167 */
1168LZ4_FORCE_O2_GCC_PPC64LE
1169LZ4_FORCE_INLINE int LZ4_decompress_generic(
1170 const char* const src,
1171 char* const dst,
1172 int srcSize,
1173 int outputSize, /* If endOnInput==endOnInputSize, this value is `dstCapacity` */
1174
1175 int endOnInput, /* endOnOutputSize, endOnInputSize */
1176 int partialDecoding, /* full, partial */
1177 int targetOutputSize, /* only used if partialDecoding==partial */
1178 int dict, /* noDict, withPrefix64k, usingExtDict */
1179 const BYTE* const lowPrefix, /* always <= dst, == dst when no prefix */
1180 const BYTE* const dictStart, /* only if dict==usingExtDict */
1181 const size_t dictSize /* note : = 0 if noDict */
1182 )
1183{
1184 const BYTE* ip = (const BYTE*) src;
1185 const BYTE* const iend = ip + srcSize;
1186
1187 BYTE* op = (BYTE*) dst;
1188 BYTE* const oend = op + outputSize;
1189 BYTE* cpy;
1190 BYTE* oexit = op + targetOutputSize;
1191
1192 const BYTE* const dictEnd = (const BYTE*)dictStart + dictSize;
1193 const unsigned inc32table[8] = {0, 1, 2, 1, 0, 4, 4, 4};
1194 const int dec64table[8] = {0, 0, 0, -1, -4, 1, 2, 3};
1195
1196 const int safeDecode = (endOnInput==endOnInputSize);
1197 const int checkOffset = ((safeDecode) && (dictSize < (int)(64 KB)));
1198
1199
1200 /* Special cases */
1201 if ((partialDecoding) && (oexit > oend-MFLIMIT)) oexit = oend-MFLIMIT; /* targetOutputSize too high => just decode everything */
1202 if ((endOnInput) && (unlikely(outputSize==0))) return ((srcSize==1) && (*ip==0)) ? 0 : -1; /* Empty output buffer */
1203 if ((!endOnInput) && (unlikely(outputSize==0))) return (*ip==0?1:-1);
1204
1205 /* Main Loop : decode sequences */
1206 while (1) {
1207 size_t length;
1208 const BYTE* match;
1209 size_t offset;
1210
1211 unsigned const token = *ip++;
1212
1213 /* shortcut for common case :
1214 * in most circumstances, we expect to decode small matches (<= 18 bytes) separated by few literals (<= 14 bytes).
1215 * this shortcut was tested on x86 and x64, where it improves decoding speed.
1216 * it has not yet been benchmarked on ARM, Power, mips, etc. */
1217 if (((ip + 14 /*maxLL*/ + 2 /*offset*/ <= iend)
1218 & (op + 14 /*maxLL*/ + 18 /*maxML*/ <= oend))
1219 & ((token < (15<<ML_BITS)) & ((token & ML_MASK) != 15)) ) {
1220 size_t const ll = token >> ML_BITS;
1221 size_t const off = LZ4_readLE16(ip+ll);
1222 const BYTE* const matchPtr = op + ll - off; /* pointer underflow risk ? */
1223 if ((off >= 18) /* do not deal with overlapping matches */ & (matchPtr >= lowPrefix)) {
1224 size_t const ml = (token & ML_MASK) + MINMATCH;
1225 memcpy(op, ip, 16); op += ll; ip += ll + 2 /*offset*/;
1226 memcpy(op, matchPtr, 18); op += ml;
1227 continue;
1228 }
1229 }
1230
1231 /* decode literal length */
1232 if ((length=(token>>ML_BITS)) == RUN_MASK) {
1233 unsigned s;
1234 do {
1235 s = *ip++;
1236 length += s;
1237 } while ( likely(endOnInput ? ip<iend-RUN_MASK : 1) & (s==255) );
1238 if ((safeDecode) && unlikely((uptrval)(op)+length<(uptrval)(op))) goto _output_error; /* overflow detection */
1239 if ((safeDecode) && unlikely((uptrval)(ip)+length<(uptrval)(ip))) goto _output_error; /* overflow detection */
1240 }
1241
1242 /* copy literals */
1243 cpy = op+length;
1244 if ( ((endOnInput) && ((cpy>(partialDecoding?oexit:oend-MFLIMIT)) || (ip+length>iend-(2+1+LASTLITERALS))) )
1245 || ((!endOnInput) && (cpy>oend-WILDCOPYLENGTH)) )
1246 {
1247 if (partialDecoding) {
1248 if (cpy > oend) goto _output_error; /* Error : write attempt beyond end of output buffer */
1249 if ((endOnInput) && (ip+length > iend)) goto _output_error; /* Error : read attempt beyond end of input buffer */
1250 } else {
1251 if ((!endOnInput) && (cpy != oend)) goto _output_error; /* Error : block decoding must stop exactly there */
1252 if ((endOnInput) && ((ip+length != iend) || (cpy > oend))) goto _output_error; /* Error : input must be consumed */
1253 }
1254 memcpy(op, ip, length);
1255 ip += length;
1256 op += length;
1257 break; /* Necessarily EOF, due to parsing restrictions */
1258 }
1259 LZ4_wildCopy(op, ip, cpy);
1260 ip += length; op = cpy;
1261
1262 /* get offset */
1263 offset = LZ4_readLE16(ip); ip+=2;
1264 match = op - offset;
1265 if ((checkOffset) && (unlikely(match + dictSize < lowPrefix))) goto _output_error; /* Error : offset outside buffers */
1266 LZ4_write32(op, (U32)offset); /* costs ~1%; silence an msan warning when offset==0 */
1267
1268 /* get matchlength */
1269 length = token & ML_MASK;
1270 if (length == ML_MASK) {
1271 unsigned s;
1272 do {
1273 s = *ip++;
1274 if ((endOnInput) && (ip > iend-LASTLITERALS)) goto _output_error;
1275 length += s;
1276 } while (s==255);
1277 if ((safeDecode) && unlikely((uptrval)(op)+length<(uptrval)op)) goto _output_error; /* overflow detection */
1278 }
1279 length += MINMATCH;
1280
1281 /* check external dictionary */
1282 if ((dict==usingExtDict) && (match < lowPrefix)) {
1283 if (unlikely(op+length > oend-LASTLITERALS)) goto _output_error; /* doesn't respect parsing restriction */
1284
1285 if (length <= (size_t)(lowPrefix-match)) {
1286 /* match can be copied as a single segment from external dictionary */
1287 memmove(op, dictEnd - (lowPrefix-match), length);
1288 op += length;
1289 } else {
1290 /* match encompass external dictionary and current block */
1291 size_t const copySize = (size_t)(lowPrefix-match);
1292 size_t const restSize = length - copySize;
1293 memcpy(op, dictEnd - copySize, copySize);
1294 op += copySize;
1295 if (restSize > (size_t)(op-lowPrefix)) { /* overlap copy */
1296 BYTE* const endOfMatch = op + restSize;
1297 const BYTE* copyFrom = lowPrefix;
1298 while (op < endOfMatch) *op++ = *copyFrom++;
1299 } else {
1300 memcpy(op, lowPrefix, restSize);
1301 op += restSize;
1302 } }
1303 continue;
1304 }
1305
1306 /* copy match within block */
1307 cpy = op + length;
1308 if (unlikely(offset<8)) {
1309 op[0] = match[0];
1310 op[1] = match[1];
1311 op[2] = match[2];
1312 op[3] = match[3];
1313 match += inc32table[offset];
1314 memcpy(op+4, match, 4);
1315 match -= dec64table[offset];
1316 } else { LZ4_copy8(op, match); match+=8; }
1317 op += 8;
1318
1319 if (unlikely(cpy>oend-12)) {
1320 BYTE* const oCopyLimit = oend-(WILDCOPYLENGTH-1);
1321 if (cpy > oend-LASTLITERALS) goto _output_error; /* Error : last LASTLITERALS bytes must be literals (uncompressed) */
1322 if (op < oCopyLimit) {
1323 LZ4_wildCopy(op, match, oCopyLimit);
1324 match += oCopyLimit - op;
1325 op = oCopyLimit;
1326 }
1327 while (op<cpy) *op++ = *match++;
1328 } else {
1329 LZ4_copy8(op, match);
1330 if (length>16) LZ4_wildCopy(op+8, match+8, cpy);
1331 }
1332 op = cpy; /* correction */
1333 }
1334
1335 /* end of decoding */
1336 if (endOnInput)
1337 return (int) (((char*)op)-dst); /* Nb of output bytes decoded */
1338 else
1339 return (int) (((const char*)ip)-src); /* Nb of input bytes read */
1340
1341 /* Overflow error detected */
1342_output_error:
1343 return (int) (-(((const char*)ip)-src))-1;
1344}
1345
1346
1347LZ4_FORCE_O2_GCC_PPC64LE
1348int LZ4_decompress_safe(const char* source, char* dest, int compressedSize, int maxDecompressedSize)
1349{
1350 return LZ4_decompress_generic(source, dest, compressedSize, maxDecompressedSize, endOnInputSize, full, 0, noDict, (BYTE*)dest, NULL, 0);
1351}
1352
1353LZ4_FORCE_O2_GCC_PPC64LE
1354int LZ4_decompress_safe_partial(const char* source, char* dest, int compressedSize, int targetOutputSize, int maxDecompressedSize)
1355{
1356 return LZ4_decompress_generic(source, dest, compressedSize, maxDecompressedSize, endOnInputSize, partial, targetOutputSize, noDict, (BYTE*)dest, NULL, 0);
1357}
1358
1359LZ4_FORCE_O2_GCC_PPC64LE
1360int LZ4_decompress_fast(const char* source, char* dest, int originalSize)
1361{
1362 return LZ4_decompress_generic(source, dest, 0, originalSize, endOnOutputSize, full, 0, withPrefix64k, (BYTE*)(dest - 64 KB), NULL, 64 KB);
1363}
1364
1365
1366/*===== streaming decompression functions =====*/
1367
1368LZ4_streamDecode_t* LZ4_createStreamDecode(void)
1369{
1370 LZ4_streamDecode_t* lz4s = (LZ4_streamDecode_t*) ALLOCATOR(1, sizeof(LZ4_streamDecode_t));
1371 return lz4s;
1372}
1373
1374int LZ4_freeStreamDecode (LZ4_streamDecode_t* LZ4_stream)
1375{
1376 if (!LZ4_stream) return 0; /* support free on NULL */
1377 FREEMEM(LZ4_stream);
1378 return 0;
1379}
1380
1381/*!
1382 * LZ4_setStreamDecode() :
1383 * Use this function to instruct where to find the dictionary.
1384 * This function is not necessary if previous data is still available where it was decoded.
1385 * Loading a size of 0 is allowed (same effect as no dictionary).
1386 * Return : 1 if OK, 0 if error
1387 */
1388int LZ4_setStreamDecode (LZ4_streamDecode_t* LZ4_streamDecode, const char* dictionary, int dictSize)
1389{
1390 LZ4_streamDecode_t_internal* lz4sd = &LZ4_streamDecode->internal_donotuse;
1391 lz4sd->prefixSize = (size_t) dictSize;
1392 lz4sd->prefixEnd = (const BYTE*) dictionary + dictSize;
1393 lz4sd->externalDict = NULL;
1394 lz4sd->extDictSize = 0;
1395 return 1;
1396}
1397
1398/*
1399*_continue() :
1400 These decoding functions allow decompression of multiple blocks in "streaming" mode.
1401 Previously decoded blocks must still be available at the memory position where they were decoded.
1402 If it's not possible, save the relevant part of decoded data into a safe buffer,
1403 and indicate where it stands using LZ4_setStreamDecode()
1404*/
1405LZ4_FORCE_O2_GCC_PPC64LE
1406int LZ4_decompress_safe_continue (LZ4_streamDecode_t* LZ4_streamDecode, const char* source, char* dest, int compressedSize, int maxOutputSize)
1407{
1408 LZ4_streamDecode_t_internal* lz4sd = &LZ4_streamDecode->internal_donotuse;
1409 int result;
1410
1411 if (lz4sd->prefixEnd == (BYTE*)dest) {
1412 result = LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize,
1413 endOnInputSize, full, 0,
1414 usingExtDict, lz4sd->prefixEnd - lz4sd->prefixSize, lz4sd->externalDict, lz4sd->extDictSize);
1415 if (result <= 0) return result;
1416 lz4sd->prefixSize += result;
1417 lz4sd->prefixEnd += result;
1418 } else {
1419 lz4sd->extDictSize = lz4sd->prefixSize;
1420 lz4sd->externalDict = lz4sd->prefixEnd - lz4sd->extDictSize;
1421 result = LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize,
1422 endOnInputSize, full, 0,
1423 usingExtDict, (BYTE*)dest, lz4sd->externalDict, lz4sd->extDictSize);
1424 if (result <= 0) return result;
1425 lz4sd->prefixSize = result;
1426 lz4sd->prefixEnd = (BYTE*)dest + result;
1427 }
1428
1429 return result;
1430}
1431
1432LZ4_FORCE_O2_GCC_PPC64LE
1433int LZ4_decompress_fast_continue (LZ4_streamDecode_t* LZ4_streamDecode, const char* source, char* dest, int originalSize)
1434{
1435 LZ4_streamDecode_t_internal* lz4sd = &LZ4_streamDecode->internal_donotuse;
1436 int result;
1437
1438 if (lz4sd->prefixEnd == (BYTE*)dest) {
1439 result = LZ4_decompress_generic(source, dest, 0, originalSize,
1440 endOnOutputSize, full, 0,
1441 usingExtDict, lz4sd->prefixEnd - lz4sd->prefixSize, lz4sd->externalDict, lz4sd->extDictSize);
1442 if (result <= 0) return result;
1443 lz4sd->prefixSize += originalSize;
1444 lz4sd->prefixEnd += originalSize;
1445 } else {
1446 lz4sd->extDictSize = lz4sd->prefixSize;
1447 lz4sd->externalDict = lz4sd->prefixEnd - lz4sd->extDictSize;
1448 result = LZ4_decompress_generic(source, dest, 0, originalSize,
1449 endOnOutputSize, full, 0,
1450 usingExtDict, (BYTE*)dest, lz4sd->externalDict, lz4sd->extDictSize);
1451 if (result <= 0) return result;
1452 lz4sd->prefixSize = originalSize;
1453 lz4sd->prefixEnd = (BYTE*)dest + originalSize;
1454 }
1455
1456 return result;
1457}
1458
1459
1460/*
1461Advanced decoding functions :
1462*_usingDict() :
1463 These decoding functions work the same as "_continue" ones,
1464 the dictionary must be explicitly provided within parameters
1465*/
1466
1467LZ4_FORCE_O2_GCC_PPC64LE
1468LZ4_FORCE_INLINE int LZ4_decompress_usingDict_generic(const char* source, char* dest, int compressedSize, int maxOutputSize, int safe, const char* dictStart, int dictSize)
1469{
1470 if (dictSize==0)
1471 return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, safe, full, 0, noDict, (BYTE*)dest, NULL, 0);
1472 if (dictStart+dictSize == dest) {
1473 if (dictSize >= (int)(64 KB - 1))
1474 return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, safe, full, 0, withPrefix64k, (BYTE*)dest-64 KB, NULL, 0);
1475 return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, safe, full, 0, noDict, (BYTE*)dest-dictSize, NULL, 0);
1476 }
1477 return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, safe, full, 0, usingExtDict, (BYTE*)dest, (const BYTE*)dictStart, dictSize);
1478}
1479
1480LZ4_FORCE_O2_GCC_PPC64LE
1481int LZ4_decompress_safe_usingDict(const char* source, char* dest, int compressedSize, int maxOutputSize, const char* dictStart, int dictSize)
1482{
1483 return LZ4_decompress_usingDict_generic(source, dest, compressedSize, maxOutputSize, 1, dictStart, dictSize);
1484}
1485
1486LZ4_FORCE_O2_GCC_PPC64LE
1487int LZ4_decompress_fast_usingDict(const char* source, char* dest, int originalSize, const char* dictStart, int dictSize)
1488{
1489 return LZ4_decompress_usingDict_generic(source, dest, 0, originalSize, 0, dictStart, dictSize);
1490}
1491
1492/* debug function */
1493LZ4_FORCE_O2_GCC_PPC64LE
1494int LZ4_decompress_safe_forceExtDict(const char* source, char* dest, int compressedSize, int maxOutputSize, const char* dictStart, int dictSize)
1495{
1496 return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, endOnInputSize, full, 0, usingExtDict, (BYTE*)dest, (const BYTE*)dictStart, dictSize);
1497}
1498
1499
1500/*=*************************************************
1501* Obsolete Functions
1502***************************************************/
1503/* obsolete compression functions */
1504int LZ4_compress_limitedOutput(const char* source, char* dest, int inputSize, int maxOutputSize) { return LZ4_compress_default(source, dest, inputSize, maxOutputSize); }
1505int LZ4_compress(const char* source, char* dest, int inputSize) { return LZ4_compress_default(source, dest, inputSize, LZ4_compressBound(inputSize)); }
1506int LZ4_compress_limitedOutput_withState (void* state, const char* src, char* dst, int srcSize, int dstSize) { return LZ4_compress_fast_extState(state, src, dst, srcSize, dstSize, 1); }
1507int LZ4_compress_withState (void* state, const char* src, char* dst, int srcSize) { return LZ4_compress_fast_extState(state, src, dst, srcSize, LZ4_compressBound(srcSize), 1); }
1508int LZ4_compress_limitedOutput_continue (LZ4_stream_t* LZ4_stream, const char* src, char* dst, int srcSize, int maxDstSize) { return LZ4_compress_fast_continue(LZ4_stream, src, dst, srcSize, maxDstSize, 1); }
1509int LZ4_compress_continue (LZ4_stream_t* LZ4_stream, const char* source, char* dest, int inputSize) { return LZ4_compress_fast_continue(LZ4_stream, source, dest, inputSize, LZ4_compressBound(inputSize), 1); }
1510
1511/*
1512These function names are deprecated and should no longer be used.
1513They are only provided here for compatibility with older user programs.
1514- LZ4_uncompress is totally equivalent to LZ4_decompress_fast
1515- LZ4_uncompress_unknownOutputSize is totally equivalent to LZ4_decompress_safe
1516*/
1517int LZ4_uncompress (const char* source, char* dest, int outputSize) { return LZ4_decompress_fast(source, dest, outputSize); }
1518int LZ4_uncompress_unknownOutputSize (const char* source, char* dest, int isize, int maxOutputSize) { return LZ4_decompress_safe(source, dest, isize, maxOutputSize); }
1519
1520
1521/* Obsolete Streaming functions */
1522
1523int LZ4_sizeofStreamState() { return LZ4_STREAMSIZE; }
1524
1525static void LZ4_init(LZ4_stream_t* lz4ds, BYTE* base)
1526{
1527 MEM_INIT(lz4ds, 0, sizeof(LZ4_stream_t));
1528 lz4ds->internal_donotuse.bufferStart = base;
1529}
1530
1531int LZ4_resetStreamState(void* state, char* inputBuffer)
1532{
1533 if ((((uptrval)state) & 3) != 0) return 1; /* Error : pointer is not aligned on 4-bytes boundary */
1534 LZ4_init((LZ4_stream_t*)state, (BYTE*)inputBuffer);
1535 return 0;
1536}
1537
1538void* LZ4_create (char* inputBuffer)
1539{
1540 LZ4_stream_t* lz4ds = (LZ4_stream_t*)ALLOCATOR(8, sizeof(LZ4_stream_t));
1541 LZ4_init (lz4ds, (BYTE*)inputBuffer);
1542 return lz4ds;
1543}
1544
1545char* LZ4_slideInputBuffer (void* LZ4_Data)
1546{
1547 LZ4_stream_t_internal* ctx = &((LZ4_stream_t*)LZ4_Data)->internal_donotuse;
1548 int dictSize = LZ4_saveDict((LZ4_stream_t*)LZ4_Data, (char*)ctx->bufferStart, 64 KB);
1549 return (char*)(ctx->bufferStart + dictSize);
1550}
1551
1552/* Obsolete streaming decompression functions */
1553
1554int LZ4_decompress_safe_withPrefix64k(const char* source, char* dest, int compressedSize, int maxOutputSize)
1555{
1556 return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, endOnInputSize, full, 0, withPrefix64k, (BYTE*)dest - 64 KB, NULL, 64 KB);
1557}
1558
1559int LZ4_decompress_fast_withPrefix64k(const char* source, char* dest, int originalSize)
1560{
1561 return LZ4_decompress_generic(source, dest, 0, originalSize, endOnOutputSize, full, 0, withPrefix64k, (BYTE*)dest - 64 KB, NULL, 64 KB);
1562}
1563
1564#endif /* LZ4_COMMONDEFS_ONLY */
1565