Bug Summary

File:root/firefox-clang/mozglue/static/lz4/lz4.c
Warning:line 2199, column 9
Subtraction of a null pointer (from variable 'dictEnd') and a probably nonzero integer value (from variable 'copySize') may result in undefined behavior

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -O2 -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name lz4.c -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -fhalf-no-semantic-interposition -mframe-pointer=all -relaxed-aliasing -ffp-contract=off -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fdebug-compilation-dir=/root/firefox-clang/obj-x86_64-pc-linux-gnu/mozglue/static -fcoverage-compilation-dir=/root/firefox-clang/obj-x86_64-pc-linux-gnu/mozglue/static -resource-dir /usr/lib/llvm-23/lib/clang/23 -include /root/firefox-clang/config/gcc_hidden.h -include /root/firefox-clang/obj-x86_64-pc-linux-gnu/mozilla-config.h -I /root/firefox-clang/obj-x86_64-pc-linux-gnu/dist/system_wrappers -U _FORTIFY_SOURCE -D _FORTIFY_SOURCE=2 -D DEBUG=1 -D LZ4LIB_VISIBILITY= -D LZ4FLIB_VISIBILITY= -D EXPORT_JS_API -D MOZ_HAS_MOZGLUE -D MOZ_SUPPORT_LEAKCHECKING -I /root/firefox-clang/mozglue/static -I /root/firefox-clang/obj-x86_64-pc-linux-gnu/mozglue/static -I /root/firefox-clang/mozglue/static/xxhash -I /root/firefox-clang/obj-x86_64-pc-linux-gnu/dist/include -I /root/firefox-clang/obj-x86_64-pc-linux-gnu/dist/include/nspr -I /root/firefox-clang/obj-x86_64-pc-linux-gnu/dist/include/nss -D MOZILLA_CLIENT -internal-isystem /usr/lib/llvm-23/lib/clang/23/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/16/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -Wno-error=tautological-type-limit-compare -Wno-range-loop-analysis -Wno-error=deprecated-declarations -Wno-error=array-bounds -Wno-error=free-nonheap-object -Wno-error=atomic-alignment -Wno-error=deprecated-builtins -Wno-psabi -Wno-error=builtin-macro-redefined -Wno-unknown-warning-option -Wno-character-conversion -ferror-limit 19 -fstrict-flex-arrays=1 -stack-protector 2 -fstack-clash-protection -ftrivial-auto-var-init=pattern -fgnuc-version=4.2.1 -fskip-odr-check-in-gmf -fdiagnostics-absolute-paths -vectorize-loops -vectorize-slp -analyzer-checker optin.performance.Padding -analyzer-output=html -analyzer-config stable-report-filename=true -mllvm -dwarf-linkage-names=Abstract -faddrsig -fdwarf2-cfi-asm -o /tmp/scan-build-2026-11-12-001017-1011516-1 -x c /root/firefox-clang/mozglue/static/lz4/lz4.c
1/*
2 LZ4 - Fast LZ compression algorithm
3 Copyright (c) Yann Collet. All rights reserved.
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* Tuning parameters
37**************************************/
38/*
39 * LZ4_HEAPMODE :
40 * Select how stateless compression functions like `LZ4_compress_default()`
41 * allocate memory for their hash table,
42 * in memory stack (0:default, fastest), or in memory heap (1:requires malloc()).
43 */
44#ifndef LZ4_HEAPMODE0
45# define LZ4_HEAPMODE0 0
46#endif
47
48
49/*-************************************
50* CPU Feature Detection
51**************************************/
52/* LZ4_FORCE_MEMORY_ACCESS
53 * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable.
54 * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal.
55 * The below switch allow to select different access method for improved performance.
56 * Method 0 (default) : use `memcpy()`. Safe and portable.
57 * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable).
58 * This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`.
59 * Method 2 : direct access. This method is portable but violate C standard.
60 * It can generate buggy code on targets which assembly generation depends on alignment.
61 * But in some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6)
62 * See https://fastcompression.blogspot.fr/2015/08/accessing-unaligned-memory.html for details.
63 * Prefer these methods in priority order (0 > 1 > 2)
64 */
65#ifndef LZ4_FORCE_MEMORY_ACCESS1 /* can be defined externally */
66# if defined(__GNUC__4) && \
67 ( defined(__ARM_ARCH_6__) || defined(__ARM_ARCH_6J__) || defined(__ARM_ARCH_6K__) \
68 || defined(__ARM_ARCH_6Z__) || defined(__ARM_ARCH_6ZK__) || defined(__ARM_ARCH_6T2__) \
69 || (defined(__riscv) && defined(__riscv_zicclsm)) )
70# define LZ4_FORCE_MEMORY_ACCESS1 2
71# elif (defined(__INTEL_COMPILER) && !defined(_WIN32)) || defined(__GNUC__4) || defined(_MSC_VER)
72# define LZ4_FORCE_MEMORY_ACCESS1 1
73# endif
74#endif
75
76/*
77 * LZ4_FORCE_SW_BITCOUNT
78 * Define this parameter if your target system or compiler does not support hardware bit count
79 */
80#if defined(_MSC_VER) && defined(_WIN32_WCE) /* Visual Studio for WinCE doesn't support Hardware bit count */
81# undef LZ4_FORCE_SW_BITCOUNT /* avoid double def */
82# define LZ4_FORCE_SW_BITCOUNT
83#endif
84
85
86
87/*-************************************
88* Dependency
89**************************************/
90/*
91 * LZ4_SRC_INCLUDED:
92 * Amalgamation flag, whether lz4.c is included
93 */
94#ifndef LZ4_SRC_INCLUDED1
95# define LZ4_SRC_INCLUDED1 1
96#endif
97
98#ifndef LZ4_DISABLE_DEPRECATE_WARNINGS
99# define LZ4_DISABLE_DEPRECATE_WARNINGS /* due to LZ4_decompress_safe_withPrefix64k */
100#endif
101
102#ifndef LZ4_STATIC_LINKING_ONLY
103# define LZ4_STATIC_LINKING_ONLY
104#endif
105#include "lz4.h"
106/* see also "memory routines" below */
107
108
109/*-************************************
110* Compiler Options
111**************************************/
112#if defined(_MSC_VER) && (_MSC_VER >= 1400) /* Visual Studio 2005+ */
113# include <intrin.h> /* only present in VS2005+ */
114# pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
115# pragma warning(disable : 6237) /* disable: C6237: conditional expression is always 0 */
116# pragma warning(disable : 6239) /* disable: C6239: (<non-zero constant> && <expression>) always evaluates to the result of <expression> */
117# pragma warning(disable : 6240) /* disable: C6240: (<expression> && <non-zero constant>) always evaluates to the result of <expression> */
118# pragma warning(disable : 6326) /* disable: C6326: Potential comparison of a constant with another constant */
119#endif /* _MSC_VER */
120
121#ifndef LZ4_FORCE_INLINEstatic inline __attribute__((always_inline))
122# if defined (_MSC_VER) && !defined (__clang__1) /* MSVC */
123# define LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) static __forceinline
124# else
125# if defined (__cplusplus) || defined (__STDC_VERSION__201710L) && __STDC_VERSION__201710L >= 199901L /* C99 */
126# if defined (__GNUC__4) || defined (__clang__1)
127# define LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) static inline __attribute__((always_inline))
128# else
129# define LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) static inline
130# endif
131# else
132# define LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) static
133# endif /* __STDC_VERSION__ */
134# endif /* _MSC_VER */
135#endif /* LZ4_FORCE_INLINE */
136
137/* LZ4_FORCE_NOINLINE : keeps a rarely used function out of its callers' hot loops */
138#ifndef LZ4_FORCE_NOINLINEstatic __attribute__((noinline))
139# if defined(_MSC_VER)
140# define LZ4_FORCE_NOINLINEstatic __attribute__((noinline)) static __declspec(noinline)
141# elif defined(__GNUC__4) || defined(__clang__1)
142# define LZ4_FORCE_NOINLINEstatic __attribute__((noinline)) static __attribute__((noinline))
143# else
144# define LZ4_FORCE_NOINLINEstatic __attribute__((noinline)) static
145# endif
146#endif
147
148/* LZ4_FORCE_O2 and LZ4_FORCE_INLINE
149 * gcc on ppc64le generates an unrolled SIMDized loop for LZ4_wildCopy8,
150 * together with a simple 8-byte copy loop as a fall-back path.
151 * However, this optimization hurts the decompression speed by >30%,
152 * because the execution does not go to the optimized loop
153 * for typical compressible data, and all of the preamble checks
154 * before going to the fall-back path become useless overhead.
155 * This optimization happens only with the -O3 flag, and -O2 generates
156 * a simple 8-byte copy loop.
157 * With gcc on ppc64le, all of the LZ4_decompress_* and LZ4_wildCopy8
158 * functions are annotated with __attribute__((optimize("O2"))),
159 * and also LZ4_wildCopy8 is forcibly inlined, so that the O2 attribute
160 * of LZ4_wildCopy8 does not affect the compression speed.
161 */
162#if defined(__PPC64__) && defined(__LITTLE_ENDIAN__1) && defined(__GNUC__4) && !defined(__clang__1)
163# define LZ4_FORCE_O2 __attribute__((optimize("O2")))
164# undef LZ4_FORCE_INLINEstatic inline __attribute__((always_inline))
165# define LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) static __inline __attribute__((optimize("O2"),always_inline))
166#else
167# define LZ4_FORCE_O2
168#endif
169
170#if (defined(__GNUC__4) && (__GNUC__4 >= 3)) || (defined(__INTEL_COMPILER) && (__INTEL_COMPILER >= 800)) || defined(__clang__1)
171# define expect(expr,value)(__builtin_expect ((expr),(value)) ) (__builtin_expect ((expr),(value)) )
172#else
173# define expect(expr,value)(__builtin_expect ((expr),(value)) ) (expr)
174#endif
175
176#ifndef likely
177#define likely(expr)(__builtin_expect (((expr) != 0),(1)) ) expect((expr) != 0, 1)(__builtin_expect (((expr) != 0),(1)) )
178#endif
179#ifndef unlikely
180#define unlikely(expr)(__builtin_expect (((expr) != 0),(0)) ) expect((expr) != 0, 0)(__builtin_expect (((expr) != 0),(0)) )
181#endif
182
183/* Should the alignment test prove unreliable, for some reason,
184 * it can be disabled by setting LZ4_ALIGN_TEST to 0 */
185#ifndef LZ4_ALIGN_TEST1 /* can be externally provided */
186# define LZ4_ALIGN_TEST1 1
187#endif
188
189
190/*-************************************
191* Memory routines
192**************************************/
193
194/*! LZ4_STATIC_LINKING_ONLY_DISABLE_MEMORY_ALLOCATION :
195 * Disable relatively high-level LZ4/HC functions that use dynamic memory
196 * allocation functions (malloc(), calloc(), free()).
197 *
198 * Note that this is a compile-time switch. And since it disables
199 * public/stable LZ4 v1 API functions, we don't recommend using this
200 * symbol to generate a library for distribution.
201 *
202 * The following public functions are removed when this symbol is defined.
203 * - lz4 : LZ4_createStream, LZ4_freeStream,
204 * LZ4_createStreamDecode, LZ4_freeStreamDecode, LZ4_create (deprecated)
205 * - lz4hc : LZ4_createStreamHC, LZ4_freeStreamHC,
206 * LZ4_createHC (deprecated), LZ4_freeHC (deprecated)
207 * - lz4frame, lz4file : All LZ4F_* functions
208 */
209#if defined(LZ4_STATIC_LINKING_ONLY_DISABLE_MEMORY_ALLOCATION)
210# define ALLOC(s)malloc(s) lz4_error_memory_allocation_is_disabled
211# define ALLOC_AND_ZERO(s)calloc(1,s) lz4_error_memory_allocation_is_disabled
212# define FREEMEM(p)free(p) lz4_error_memory_allocation_is_disabled
213#elif defined(LZ4_USER_MEMORY_FUNCTIONS)
214/* memory management functions can be customized by user project.
215 * Below functions must exist somewhere in the Project
216 * and be available at link time. */
217void* LZ4_malloc(size_t s);
218void* LZ4_calloc(size_t n, size_t s);
219void LZ4_free(void* p);
220# define ALLOC(s)malloc(s) LZ4_malloc(s)
221# define ALLOC_AND_ZERO(s)calloc(1,s) LZ4_calloc(1,s)
222# define FREEMEM(p)free(p) LZ4_free(p)
223#else
224# include <stdlib.h> /* malloc, calloc, free */
225# define ALLOC(s)malloc(s) malloc(s)
226# define ALLOC_AND_ZERO(s)calloc(1,s) calloc(1,s)
227# define FREEMEM(p)free(p) free(p)
228#endif
229
230#if ! LZ4_FREESTANDING0
231# include <string.h> /* memset, memcpy */
232#endif
233#if !defined(LZ4_memset)
234# define LZ4_memset(p,v,s)memset((p),(v),(s)) memset((p),(v),(s))
235#endif
236#define MEM_INIT(p,v,s)memset(((p)),((v)),((s))) LZ4_memset((p),(v),(s))memset(((p)),((v)),((s)))
237
238
239/*-************************************
240* Common Constants
241**************************************/
242#define MINMATCH4 4
243
244#define WILDCOPYLENGTH8 8
245#define LASTLITERALS5 5 /* see ../doc/lz4_Block_format.md#parsing-restrictions */
246#define MFLIMIT12 12 /* see ../doc/lz4_Block_format.md#parsing-restrictions */
247#define MATCH_SAFEGUARD_DISTANCE((2*8) - 4) ((2*WILDCOPYLENGTH8) - MINMATCH4) /* ensure it's possible to write 2 x wildcopyLength without overflowing output buffer */
248#define FASTLOOP_SAFE_DISTANCE64 64
249static const int LZ4_minLength = (MFLIMIT12+1);
250
251#define KB*(1 <<10) *(1 <<10)
252#define MB*(1 <<20) *(1 <<20)
253#define GB*(1U<<30) *(1U<<30)
254
255#define LZ4_DISTANCE_ABSOLUTE_MAX65535 65535
256#if (LZ4_DISTANCE_MAX65535 > LZ4_DISTANCE_ABSOLUTE_MAX65535) /* max supported by LZ4 format */
257# error "LZ4_DISTANCE_MAX is too big : must be <= 65535"
258#endif
259
260#define ML_BITS4 4
261#define ML_MASK((1U<<4)-1) ((1U<<ML_BITS4)-1)
262#define RUN_BITS(8-4) (8-ML_BITS4)
263#define RUN_MASK((1U<<(8-4))-1) ((1U<<RUN_BITS(8-4))-1)
264
265
266/*-************************************
267* Error detection
268**************************************/
269#if defined(LZ4_DEBUG) && (LZ4_DEBUG>=1)
270# include <assert.h>
271#else
272# ifndef assert
273# define assert(condition)((void)0) ((void)0)
274# endif
275#endif
276
277#define LZ4_STATIC_ASSERT(c){ enum { LZ4_static_assert = 1/(int)(!!(c)) }; } { enum { LZ4_static_assert = 1/(int)(!!(c)) }; } /* use after variable declarations */
278
279#if defined(LZ4_DEBUG) && (LZ4_DEBUG>=2)
280# include <stdio.h>
281 static int g_debuglog_enable = 1;
282# define DEBUGLOG(l, ...){} { \
283 if ((g_debuglog_enable) && (l<=LZ4_DEBUG)) { \
284 fprintf(stderr, __FILE__"/root/firefox-clang/mozglue/static/lz4/lz4.c" " %i: ", __LINE__284); \
285 fprintf(stderr, __VA_ARGS__); \
286 fprintf(stderr, " \n"); \
287 } }
288#else
289# define DEBUGLOG(l, ...){} {} /* disabled */
290#endif
291
292static int LZ4_isAligned(const void* ptr, size_t alignment)
293{
294 return ((size_t)ptr & (alignment -1)) == 0;
295}
296
297
298/*-************************************
299* Types
300**************************************/
301#include <limits.h>
302#if defined(__cplusplus) || (defined (__STDC_VERSION__201710L) && (__STDC_VERSION__201710L >= 199901L) /* C99 */)
303# include <stdint.h>
304 typedef unsigned char BYTE; /*uint8_t not necessarily blessed to alias arbitrary type*/
305 typedef uint16_t U16;
306 typedef uint32_t U32;
307 typedef int32_t S32;
308 typedef uint64_t U64;
309 typedef uintptr_t uptrval;
310#else
311# if UINT_MAX(2147483647 *2U +1U) != 4294967295UL
312# error "LZ4 code (when not C++ or C99) assumes that sizeof(int) == 4"
313# endif
314 typedef unsigned char BYTE;
315 typedef unsigned short U16;
316 typedef unsigned int U32;
317 typedef signed int S32;
318 typedef unsigned long long U64;
319 typedef size_t uptrval; /* generally true, except OpenVMS-64 */
320#endif
321
322#if defined(__x86_64__1)
323 typedef U64 reg_t; /* 64-bits in x32 mode */
324#else
325 typedef size_t reg_t; /* 32-bits in x32 mode */
326#endif
327
328typedef enum {
329 notLimited = 0,
330 limitedOutput = 1,
331 fillOutput = 2
332} limitedOutput_directive;
333
334
335/*-************************************
336* Reading and writing into memory
337**************************************/
338
339/**
340 * LZ4 relies on memcpy with a constant size being inlined. In freestanding
341 * environments, the compiler can't assume the implementation of memcpy() is
342 * standard compliant, so it can't apply its specialized memcpy() inlining
343 * logic. When possible, use __builtin_memcpy() to tell the compiler to analyze
344 * memcpy() as if it were standard compliant, so it can inline it in freestanding
345 * environments. This is needed when decompressing the Linux Kernel, for example.
346 */
347#if !defined(LZ4_memcpy)
348# if defined(__GNUC__4) && (__GNUC__4 >= 4)
349# define LZ4_memcpy(dst, src, size)__builtin_memcpy(dst, src, size) __builtin_memcpy(dst, src, size)
350# else
351# define LZ4_memcpy(dst, src, size)__builtin_memcpy(dst, src, size) memcpy(dst, src, size)
352# endif
353#endif
354
355#if !defined(LZ4_memmove__builtin_memmove)
356# if defined(__GNUC__4) && (__GNUC__4 >= 4)
357# define LZ4_memmove__builtin_memmove __builtin_memmove
358# else
359# define LZ4_memmove__builtin_memmove memmove
360# endif
361#endif
362
363static unsigned LZ4_isLittleEndian(void)
364{
365 const union { U32 u; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */
366 return one.c[0];
367}
368
369#if defined(__GNUC__4) || defined(__INTEL_COMPILER)
370#define LZ4_PACK( __Declaration__ )__Declaration__ __attribute__((__packed__)) __Declaration__ __attribute__((__packed__))
371#elif defined(_MSC_VER)
372#define LZ4_PACK( __Declaration__ )__Declaration__ __attribute__((__packed__)) __pragma( pack(push, 1) ) __Declaration__ __pragma( pack(pop))
373#endif
374
375#if defined(LZ4_FORCE_MEMORY_ACCESS1) && (LZ4_FORCE_MEMORY_ACCESS1==2)
376/* lie to the compiler about data alignment; use with caution */
377
378static U16 LZ4_read16(const void* memPtr) { return *(const U16*) memPtr; }
379static U32 LZ4_read32(const void* memPtr) { return *(const U32*) memPtr; }
380static reg_t LZ4_read_ARCH(const void* memPtr) { return *(const reg_t*) memPtr; }
381
382static void LZ4_write16(void* memPtr, U16 value) { *(U16*)memPtr = value; }
383static void LZ4_write32(void* memPtr, U32 value) { *(U32*)memPtr = value; }
384
385#elif defined(LZ4_FORCE_MEMORY_ACCESS1) && (LZ4_FORCE_MEMORY_ACCESS1==1)
386
387/* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */
388/* currently only defined for gcc and icc */
389LZ4_PACK(typedef struct { U16 u16; })typedef struct { U16 u16; } __attribute__((__packed__)) LZ4_unalign16;
390LZ4_PACK(typedef struct { U32 u32; })typedef struct { U32 u32; } __attribute__((__packed__)) LZ4_unalign32;
391LZ4_PACK(typedef struct { reg_t uArch; })typedef struct { reg_t uArch; } __attribute__((__packed__)) LZ4_unalignST;
392
393static U16 LZ4_read16(const void* ptr) { return ((const LZ4_unalign16*)ptr)->u16; }
394static U32 LZ4_read32(const void* ptr) { return ((const LZ4_unalign32*)ptr)->u32; }
395static reg_t LZ4_read_ARCH(const void* ptr) { return ((const LZ4_unalignST*)ptr)->uArch; }
396
397static void LZ4_write16(void* memPtr, U16 value) { ((LZ4_unalign16*)memPtr)->u16 = value; }
398static void LZ4_write32(void* memPtr, U32 value) { ((LZ4_unalign32*)memPtr)->u32 = value; }
399
400#else /* safe and portable access using memcpy() */
401
402static U16 LZ4_read16(const void* memPtr)
403{
404 U16 val; LZ4_memcpy(&val, memPtr, sizeof(val))__builtin_memcpy(&val, memPtr, sizeof(val)); return val;
405}
406
407static U32 LZ4_read32(const void* memPtr)
408{
409 U32 val; LZ4_memcpy(&val, memPtr, sizeof(val))__builtin_memcpy(&val, memPtr, sizeof(val)); return val;
410}
411
412static reg_t LZ4_read_ARCH(const void* memPtr)
413{
414 reg_t val; LZ4_memcpy(&val, memPtr, sizeof(val))__builtin_memcpy(&val, memPtr, sizeof(val)); return val;
415}
416
417static void LZ4_write16(void* memPtr, U16 value)
418{
419 LZ4_memcpy(memPtr, &value, sizeof(value))__builtin_memcpy(memPtr, &value, sizeof(value));
420}
421
422static void LZ4_write32(void* memPtr, U32 value)
423{
424 LZ4_memcpy(memPtr, &value, sizeof(value))__builtin_memcpy(memPtr, &value, sizeof(value));
425}
426
427#endif /* LZ4_FORCE_MEMORY_ACCESS */
428
429
430static U16 LZ4_readLE16(const void* memPtr)
431{
432 if (LZ4_isLittleEndian()) {
433 return LZ4_read16(memPtr);
434 } else {
435 const BYTE* p = (const BYTE*)memPtr;
436 return (U16)((U16)p[0] | (p[1]<<8));
437 }
438}
439
440#ifdef LZ4_STATIC_LINKING_ONLY_ENDIANNESS_INDEPENDENT_OUTPUT
441static U32 LZ4_readLE32(const void* memPtr)
442{
443 if (LZ4_isLittleEndian()) {
444 return LZ4_read32(memPtr);
445 } else {
446 const BYTE* p = (const BYTE*)memPtr;
447 return (U32)p[0] | (p[1]<<8) | (p[2]<<16) | (p[3]<<24);
448 }
449}
450#endif
451
452static void LZ4_writeLE16(void* memPtr, U16 value)
453{
454 if (LZ4_isLittleEndian()) {
455 LZ4_write16(memPtr, value);
456 } else {
457 BYTE* p = (BYTE*)memPtr;
458 p[0] = (BYTE) value;
459 p[1] = (BYTE)(value>>8);
460 }
461}
462
463/* customized variant of memcpy, which can overwrite up to 8 bytes beyond dstEnd */
464LZ4_FORCE_INLINEstatic inline __attribute__((always_inline))
465void LZ4_wildCopy8(void* dstPtr, const void* srcPtr, void* dstEnd)
466{
467 BYTE* d = (BYTE*)dstPtr;
468 const BYTE* s = (const BYTE*)srcPtr;
469 BYTE* const e = (BYTE*)dstEnd;
470
471 do { LZ4_memcpy(d,s,8)__builtin_memcpy(d, s, 8); d+=8; s+=8; } while (d<e);
472}
473
474static const unsigned inc32table[8] = {0, 1, 2, 1, 0, 4, 4, 4};
475static const int dec64table[8] = {0, 0, 0, -1, -4, 1, 2, 3};
476
477
478#ifndef LZ4_FAST_DEC_LOOP1
479# if defined __i386__ || defined _M_IX86 || defined __x86_64__1 || defined _M_X64
480# define LZ4_FAST_DEC_LOOP1 1
481# elif defined(__aarch64__)
482# define LZ4_FAST_DEC_LOOP1 1
483# elif defined(__riscv) && (__riscv_xlen == 64) && defined(__riscv_misaligned_fast)
484# define LZ4_FAST_DEC_LOOP1 1 /* otherwise, unaligned memcpy() become byte copies, defeating the fast loop */
485# else
486# define LZ4_FAST_DEC_LOOP1 0
487# endif
488#endif
489
490/* LZ4_memcpy_using_offset_base() :
491 * copy a match of length >= MINMATCH (srcPtr + offset == dstPtr, overlap allowed),
492 * can overwrite up to 12 bytes beyond dstEnd */
493LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) void
494LZ4_memcpy_using_offset_base(BYTE* dstPtr, const BYTE* srcPtr, BYTE* dstEnd, const size_t offset)
495{
496 assert(srcPtr + offset == dstPtr)((void)0);
497 if (unlikely(offset < 8)(__builtin_expect (((offset < 8) != 0),(0)) )) {
498 LZ4_write32(dstPtr, 0); /* silence an msan warning when offset==0 */
499 dstPtr[0] = srcPtr[0];
500 dstPtr[1] = srcPtr[1];
501 dstPtr[2] = srcPtr[2];
502 dstPtr[3] = srcPtr[3];
503 srcPtr += inc32table[offset];
504 LZ4_memcpy(dstPtr+4, srcPtr, 4)__builtin_memcpy(dstPtr+4, srcPtr, 4);
505 srcPtr -= dec64table[offset];
506 } else {
507 LZ4_memcpy(dstPtr, srcPtr, 8)__builtin_memcpy(dstPtr, srcPtr, 8);
508 srcPtr += 8;
509 }
510 dstPtr += 8;
511
512 /* srcPtr is now at least 8 bytes behind dstPtr */
513 LZ4_memcpy(dstPtr, srcPtr, 8)__builtin_memcpy(dstPtr, srcPtr, 8);
514 if (dstEnd > dstPtr + 8) { LZ4_wildCopy8(dstPtr + 8, srcPtr + 8, dstEnd); }
515}
516
517
518#if LZ4_FAST_DEC_LOOP1
519
520/* LZ4_wildCopy64 is faster on aarch64 and x86-64, but not on 32-bit x86.
521 * On wasm, it depends on the host cpu (faster on Apple silicon, slower on x86-64) :
522 * it's not enabled by default, but can be, with LZ4_FAST_DEC_LOOP, from the build command */
523#ifndef LZ4_WILDCOPY641
524# if defined(__aarch64__) || defined(__x86_64__1) || defined(_M_X64)
525# define LZ4_WILDCOPY641 1
526# else
527# define LZ4_WILDCOPY641 0
528# endif
529#endif
530
531#if LZ4_WILDCOPY641
532/* customized variant of memcpy, which can overwrite up to 64 bytes beyond dstEnd */
533LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) void
534LZ4_wildCopy64(void* dstPtr, const void* srcPtr, void* dstEnd)
535{
536 BYTE* d = (BYTE*)dstPtr;
537 const BYTE* s = (const BYTE*)srcPtr;
538 BYTE* const e = (BYTE*)dstEnd;
539
540 do { LZ4_memcpy(d,s,64)__builtin_memcpy(d, s, 64); d+=64; s+=64; } while (d<e);
541}
542#endif
543
544/* customized variant of memcpy, which can overwrite up to 32 bytes beyond dstEnd
545 * this version copies two times 16 bytes (instead of one time 32 bytes)
546 * because it must be compatible with offsets >= 16. */
547LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) void
548LZ4_wildCopy32(void* dstPtr, const void* srcPtr, void* dstEnd)
549{
550 BYTE* d = (BYTE*)dstPtr;
551 const BYTE* s = (const BYTE*)srcPtr;
552 BYTE* const e = (BYTE*)dstEnd;
553
554 do { LZ4_memcpy(d,s,16)__builtin_memcpy(d, s, 16); LZ4_memcpy(d+16,s+16,16)__builtin_memcpy(d+16, s+16, 16); d+=32; s+=32; } while (d<e);
555}
556
557/* LZ4_memcpy_using_offset() presumes :
558 * - dstEnd >= dstPtr + MINMATCH
559 * - there is at least 12 bytes available to write after dstEnd */
560LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) void
561LZ4_memcpy_using_offset(BYTE* dstPtr, const BYTE* srcPtr, BYTE* dstEnd, const size_t offset)
562{
563 BYTE v[8];
564
565 assert(dstEnd >= dstPtr + MINMATCH)((void)0);
566
567 switch(offset) {
568 case 1:
569 MEM_INIT(v, *srcPtr, 8)memset(((v)),((*srcPtr)),((8)));
570 break;
571 case 2:
572 LZ4_memcpy(v, srcPtr, 2)__builtin_memcpy(v, srcPtr, 2);
573 LZ4_memcpy(&v[2], srcPtr, 2)__builtin_memcpy(&v[2], srcPtr, 2);
574#if defined(_MSC_VER) && (_MSC_VER <= 1937) /* MSVC 2022 ver 17.7 or earlier */
575# pragma warning(push)
576# pragma warning(disable : 6385) /* warning C6385: Reading invalid data from 'v'. */
577#endif
578 LZ4_memcpy(&v[4], v, 4)__builtin_memcpy(&v[4], v, 4);
579#if defined(_MSC_VER) && (_MSC_VER <= 1937) /* MSVC 2022 ver 17.7 or earlier */
580# pragma warning(pop)
581#endif
582 break;
583 case 4:
584 LZ4_memcpy(v, srcPtr, 4)__builtin_memcpy(v, srcPtr, 4);
585 LZ4_memcpy(&v[4], srcPtr, 4)__builtin_memcpy(&v[4], srcPtr, 4);
586 break;
587 default:
588 LZ4_memcpy_using_offset_base(dstPtr, srcPtr, dstEnd, offset);
589 return;
590 }
591
592 LZ4_memcpy(dstPtr, v, 8)__builtin_memcpy(dstPtr, v, 8);
593 dstPtr += 8;
594 while (dstPtr < dstEnd) {
595 LZ4_memcpy(dstPtr, v, 8)__builtin_memcpy(dstPtr, v, 8);
596 dstPtr += 8;
597 }
598}
599#endif
600
601
602/*-************************************
603* Common functions
604**************************************/
605static unsigned LZ4_NbCommonBytes (reg_t val)
606{
607 assert(val != 0)((void)0);
608 if (LZ4_isLittleEndian()) {
609 if (sizeof(val) == 8) {
610# if defined(_MSC_VER) && (_MSC_VER >= 1800) && (defined(_M_AMD64) && !defined(_M_ARM64EC)) && !defined(LZ4_FORCE_SW_BITCOUNT)
611/*-*************************************************************************************************
612* ARM64EC is a Microsoft-designed ARM64 ABI compatible with AMD64 applications on ARM64 Windows 11.
613* The ARM64EC ABI does not support AVX/AVX2/AVX512 instructions, nor their relevant intrinsics
614* including _tzcnt_u64. Therefore, we need to neuter the _tzcnt_u64 code path for ARM64EC.
615****************************************************************************************************/
616# if defined(__clang__1) && (__clang_major__23 < 10)
617 /* Avoid undefined clang-cl intrinsics issue.
618 * See https://github.com/lz4/lz4/pull/1017 for details. */
619 return (unsigned)__builtin_ia32_tzcnt_u64(val) >> 3;
620# else
621 /* x64 CPUS without BMI support interpret `TZCNT` as `REP BSF` */
622 return (unsigned)_tzcnt_u64(val) >> 3;
623# endif
624# elif defined(_MSC_VER) && defined(_WIN64) && !defined(LZ4_FORCE_SW_BITCOUNT)
625 unsigned long r = 0;
626 _BitScanForward64(&r, (U64)val);
627 return (unsigned)r >> 3;
628# elif (defined(__clang__1) || (defined(__GNUC__4) && ((__GNUC__4 > 3) || \
629 ((__GNUC__4 == 3) && (__GNUC_MINOR__2 >= 4))))) && \
630 !defined(LZ4_FORCE_SW_BITCOUNT)
631 return (unsigned)__builtin_ctzll((U64)val) >> 3;
632# else
633 const U64 m = 0x0101010101010101ULL;
634 val ^= val - 1;
635 return (unsigned)(((U64)((val & (m - 1)) * m)) >> 56);
636# endif
637 } else /* 32 bits */ {
638# if defined(_MSC_VER) && (_MSC_VER >= 1400) && !defined(LZ4_FORCE_SW_BITCOUNT)
639 unsigned long r;
640 _BitScanForward(&r, (U32)val);
641 return (unsigned)r >> 3;
642# elif (defined(__clang__1) || (defined(__GNUC__4) && ((__GNUC__4 > 3) || \
643 ((__GNUC__4 == 3) && (__GNUC_MINOR__2 >= 4))))) && \
644 !defined(__TINYC__) && !defined(LZ4_FORCE_SW_BITCOUNT)
645 return (unsigned)__builtin_ctz((U32)val) >> 3;
646# else
647 const U32 m = 0x01010101;
648 return (unsigned)((((val - 1) ^ val) & (m - 1)) * m) >> 24;
649# endif
650 }
651 } else /* Big Endian CPU */ {
652 if (sizeof(val)==8) {
653# if (defined(__clang__1) || (defined(__GNUC__4) && ((__GNUC__4 > 3) || \
654 ((__GNUC__4 == 3) && (__GNUC_MINOR__2 >= 4))))) && \
655 !defined(__TINYC__) && !defined(LZ4_FORCE_SW_BITCOUNT)
656 return (unsigned)__builtin_clzll((U64)val) >> 3;
657# else
658#if 1
659 /* this method is probably faster,
660 * but adds a 128 bytes lookup table */
661 static const unsigned char ctz7_tab[128] = {
662 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
663 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
664 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
665 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
666 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
667 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
668 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
669 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
670 };
671 U64 const mask = 0x0101010101010101ULL;
672 U64 const t = (((val >> 8) - mask) | val) & mask;
673 return ctz7_tab[(t * 0x0080402010080402ULL) >> 57];
674#else
675 /* this method doesn't consume memory space like the previous one,
676 * but it contains several branches,
677 * that may end up slowing execution */
678 static const U32 by32 = sizeof(val)*4; /* 32 on 64 bits (goal), 16 on 32 bits.
679 Just to avoid some static analyzer complaining about shift by 32 on 32-bits target.
680 Note that this code path is never triggered in 32-bits mode. */
681 unsigned r;
682 if (!(val>>by32)) { r=4; } else { r=0; val>>=by32; }
683 if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; }
684 r += (!val);
685 return r;
686#endif
687# endif
688 } else /* 32 bits */ {
689# if (defined(__clang__1) || (defined(__GNUC__4) && ((__GNUC__4 > 3) || \
690 ((__GNUC__4 == 3) && (__GNUC_MINOR__2 >= 4))))) && \
691 !defined(LZ4_FORCE_SW_BITCOUNT)
692 return (unsigned)__builtin_clz((U32)val) >> 3;
693# else
694 val >>= 8;
695 val = ((((val + 0x00FFFF00) | 0x00FFFFFF) + val) |
696 (val + 0x00FF0000)) >> 24;
697 return (unsigned)val ^ 3;
698# endif
699 }
700 }
701}
702
703
704#define STEPSIZEsizeof(reg_t) sizeof(reg_t)
705LZ4_FORCE_INLINEstatic inline __attribute__((always_inline))
706unsigned LZ4_count(const BYTE* pIn, const BYTE* pMatch, const BYTE* pInLimit)
707{
708 const BYTE* const pStart = pIn;
709
710 if (likely(pIn < pInLimit-(STEPSIZE-1))(__builtin_expect (((pIn < pInLimit-(sizeof(reg_t)-1)) != 0
),(1)) )) {
711 reg_t const diff = LZ4_read_ARCH(pMatch) ^ LZ4_read_ARCH(pIn);
712 if (!diff) {
713 pIn+=STEPSIZEsizeof(reg_t); pMatch+=STEPSIZEsizeof(reg_t);
714 } else {
715 return LZ4_NbCommonBytes(diff);
716 } }
717
718 while (likely(pIn < pInLimit-(STEPSIZE-1))(__builtin_expect (((pIn < pInLimit-(sizeof(reg_t)-1)) != 0
),(1)) )) {
719 reg_t const diff = LZ4_read_ARCH(pMatch) ^ LZ4_read_ARCH(pIn);
720 if (!diff) { pIn+=STEPSIZEsizeof(reg_t); pMatch+=STEPSIZEsizeof(reg_t); continue; }
721 pIn += LZ4_NbCommonBytes(diff);
722 return (unsigned)(pIn - pStart);
723 }
724
725 if ((STEPSIZEsizeof(reg_t)==8) && (pIn<(pInLimit-3)) && (LZ4_read32(pMatch) == LZ4_read32(pIn))) { pIn+=4; pMatch+=4; }
726 if ((pIn<(pInLimit-1)) && (LZ4_read16(pMatch) == LZ4_read16(pIn))) { pIn+=2; pMatch+=2; }
727 if ((pIn<pInLimit) && (*pMatch == *pIn)) pIn++;
728 return (unsigned)(pIn - pStart);
729}
730
731
732#ifndef LZ4_COMMONDEFS_ONLY
733/*-************************************
734* Local Constants
735**************************************/
736static const int LZ4_64Klimit = ((64 KB*(1 <<10)) + (MFLIMIT12-1));
737static const U32 LZ4_skipTrigger = 6; /* Increase this value ==> compression run slower on incompressible data */
738
739
740/*-************************************
741* Local Structures and types
742**************************************/
743typedef enum { clearedTable = 0, byPtr, byU32, byU16 } tableType_t;
744
745/**
746 * This enum distinguishes several different modes of accessing previous
747 * content in the stream.
748 *
749 * - noDict : There is no preceding content.
750 * - withPrefix64k : Table entries up to ctx->dictSize before the current blob
751 * blob being compressed are valid and refer to the preceding
752 * content (of length ctx->dictSize), which is available
753 * contiguously preceding in memory the content currently
754 * being compressed.
755 * - usingExtDict : Like withPrefix64k, but the preceding content is somewhere
756 * else in memory, starting at ctx->dictionary with length
757 * ctx->dictSize.
758 * - usingDictCtx : Everything concerning the preceding content is
759 * in a separate context, pointed to by ctx->dictCtx.
760 * ctx->dictionary, ctx->dictSize, and table entries
761 * in the current context that refer to positions
762 * preceding the beginning of the current compression are
763 * ignored. Instead, ctx->dictCtx->dictionary and ctx->dictCtx
764 * ->dictSize describe the location and size of the preceding
765 * content, and matches are found by looking in the ctx
766 * ->dictCtx->hashTable.
767 */
768typedef enum { noDict = 0, withPrefix64k, usingExtDict, usingDictCtx } dict_directive;
769typedef enum { noDictIssue = 0, dictSmall } dictIssue_directive;
770
771
772/*-************************************
773* Local Utils
774**************************************/
775int LZ4_versionNumber (void) { return LZ4_VERSION_NUMBER(1 *100*100 + 11 *100 + 0); }
776const char* LZ4_versionString(void) { return LZ4_VERSION_STRING"1.11.0"; }
777int LZ4_compressBound(int isize) { return LZ4_COMPRESSBOUND(isize)((unsigned)(isize) > (unsigned)0x7E000000 ? 0 : (isize) + (
(isize)/255) + 16); }
778int LZ4_sizeofState(void) { return sizeof(LZ4_stream_t); }
779
780
781/*-****************************************
782* Internal Definitions, used only in Tests
783*******************************************/
784#if defined (__cplusplus)
785extern "C" {
786#endif
787
788int LZ4_compress_forceExtDict (LZ4_stream_t* LZ4_dict, const char* source, char* dest, int srcSize);
789
790int LZ4_decompress_safe_forceExtDict(const char* source, char* dest,
791 int compressedSize, int maxOutputSize,
792 const void* dictStart, size_t dictSize);
793int LZ4_decompress_safe_partial_forceExtDict(const char* source, char* dest,
794 int compressedSize, int targetOutputSize, int dstCapacity,
795 const void* dictStart, size_t dictSize);
796#if defined (__cplusplus)
797}
798#endif
799
800
801/*-****************************************
802* Obsolete functions, removed from lz4.h (v1.11.0)
803* still exported, for programs linked to previous versions
804*******************************************/
805#if defined (__cplusplus)
806extern "C" {
807#endif
808
809LZ4LIB_API int LZ4_compress (const char* src, char* dest, int srcSize);
810LZ4LIB_API int LZ4_compress_limitedOutput (const char* src, char* dest, int srcSize, int maxOutputSize);
811LZ4LIB_API int LZ4_compress_withState (void* state, const char* source, char* dest, int inputSize);
812LZ4LIB_API int LZ4_compress_limitedOutput_withState (void* state, const char* source, char* dest, int inputSize, int maxOutputSize);
813LZ4LIB_API int LZ4_compress_continue (LZ4_stream_t* LZ4_streamPtr, const char* source, char* dest, int inputSize);
814LZ4LIB_API int LZ4_compress_limitedOutput_continue (LZ4_stream_t* LZ4_streamPtr, const char* source, char* dest, int inputSize, int maxOutputSize);
815LZ4LIB_API int LZ4_uncompress (const char* source, char* dest, int outputSize);
816LZ4LIB_API int LZ4_uncompress_unknownOutputSize (const char* source, char* dest, int isize, int maxOutputSize);
817LZ4LIB_API void* LZ4_create (char* inputBuffer);
818LZ4LIB_API int LZ4_sizeofStreamState(void);
819LZ4LIB_API int LZ4_resetStreamState(void* state, char* inputBuffer);
820LZ4LIB_API char* LZ4_slideInputBuffer (void* state);
821LZ4LIB_API int LZ4_decompress_safe_withPrefix64k (const char* src, char* dst, int compressedSize, int maxDstSize);
822LZ4LIB_API int LZ4_decompress_fast_withPrefix64k (const char* src, char* dst, int originalSize);
823
824#if defined (__cplusplus)
825}
826#endif
827
828/*-******************************
829* Compression functions
830********************************/
831LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) U32 LZ4_hash4(U32 sequence, tableType_t const tableType)
832{
833 const U32 hashLog = (tableType == byU16) ? LZ4_HASHLOG(14 -2)+1 : LZ4_HASHLOG(14 -2);
834 return ((sequence * 2654435761U) >> ((MINMATCH4*8)-hashLog));
835}
836
837LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) U32 LZ4_hash5(U64 sequence, tableType_t const tableType)
838{
839 const U32 hashLog = (tableType == byU16) ? LZ4_HASHLOG(14 -2)+1 : LZ4_HASHLOG(14 -2);
840 if (LZ4_isLittleEndian()) {
841 const U64 prime5bytes = 889523592379ULL;
842 return (U32)(((sequence << 24) * prime5bytes) >> (64 - hashLog));
843 } else {
844 const U64 prime8bytes = 11400714785074694791ULL;
845 return (U32)(((sequence >> 24) * prime8bytes) >> (64 - hashLog));
846 }
847}
848
849LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) U32 LZ4_hashPosition(const void* const p, tableType_t const tableType)
850{
851 if ((sizeof(reg_t)==8) && (tableType != byU16)) return LZ4_hash5(LZ4_read_ARCH(p), tableType);
852
853#ifdef LZ4_STATIC_LINKING_ONLY_ENDIANNESS_INDEPENDENT_OUTPUT
854 return LZ4_hash4(LZ4_readLE32(p), tableType);
855#else
856 return LZ4_hash4(LZ4_read32(p), tableType);
857#endif
858}
859
860LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) void LZ4_clearHash(U32 h, void* tableBase, tableType_t const tableType)
861{
862 switch (tableType)
863 {
864 default: /* fallthrough */
865 case clearedTable: { /* illegal! */ assert(0)((void)0); return; }
866 case byPtr: { const BYTE** hashTable = (const BYTE**)tableBase; hashTable[h] = NULL((void*)0); return; }
867 case byU32: { U32* hashTable = (U32*) tableBase; hashTable[h] = 0; return; }
868 case byU16: { U16* hashTable = (U16*) tableBase; hashTable[h] = 0; return; }
869 }
870}
871
872LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) void LZ4_putIndexOnHash(U32 idx, U32 h, void* tableBase, tableType_t const tableType)
873{
874 switch (tableType)
875 {
876 default: /* fallthrough */
877 case clearedTable: /* fallthrough */
878 case byPtr: { /* illegal! */ assert(0)((void)0); return; }
879 case byU32: { U32* hashTable = (U32*) tableBase; hashTable[h] = idx; return; }
880 case byU16: { U16* hashTable = (U16*) tableBase; assert(idx < 65536)((void)0); hashTable[h] = (U16)idx; return; }
881 }
882}
883
884/* LZ4_putPositionOnHash() : only used in byPtr mode */
885LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) void LZ4_putPositionOnHash(const BYTE* p, U32 h,
886 void* tableBase, tableType_t const tableType)
887{
888 const BYTE** const hashTable = (const BYTE**)tableBase;
889 assert(tableType == byPtr)((void)0); (void)tableType;
890 hashTable[h] = p;
891}
892
893/* LZ4_putPosition() :
894 * register position p : by pointer (byPtr), or by index relative to base (byU32, byU16) */
895LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) void LZ4_putPosition(const BYTE* p, void* tableBase, tableType_t tableType, const BYTE* base)
896{
897 U32 const h = LZ4_hashPosition(p, tableType);
898 if (tableType == byPtr) {
899 LZ4_putPositionOnHash(p, h, tableBase, byPtr);
900 } else {
901 LZ4_putIndexOnHash((U32)(p - base), h, tableBase, tableType);
902 }
903}
904
905/* LZ4_getIndexOnHash() :
906 * Index of match position registered in hash table.
907 * hash position must be calculated by using base+index, or dictBase+index.
908 * Assumption 1 : only valid if tableType == byU32 or byU16.
909 * Assumption 2 : h is presumed valid (within limits of hash table)
910 */
911LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) U32 LZ4_getIndexOnHash(U32 h, const void* tableBase, tableType_t tableType)
912{
913 LZ4_STATIC_ASSERT(LZ4_MEMORY_USAGE > 2){ enum { LZ4_static_assert = 1/(int)(!!(14 > 2)) }; };
914 if (tableType == byU32) {
915 const U32* const hashTable = (const U32*) tableBase;
916 assert(h < (1U << (LZ4_MEMORY_USAGE-2)))((void)0);
917 return hashTable[h];
918 }
919 if (tableType == byU16) {
920 const U16* const hashTable = (const U16*) tableBase;
921 assert(h < (1U << (LZ4_MEMORY_USAGE-1)))((void)0);
922 return hashTable[h];
923 }
924 assert(0)((void)0); return 0; /* forbidden case */
925}
926
927static const BYTE* LZ4_getPositionOnHash(U32 h, const void* tableBase, tableType_t tableType)
928{
929 assert(tableType == byPtr)((void)0); (void)tableType;
930 { const BYTE* const* hashTable = (const BYTE* const*) tableBase; return hashTable[h]; }
931}
932
933/* beyond this input size (1 KB by default),
934 * clearing the table is faster than rejecting its stale entries */
935#define LZ4_CLEAR_TABLE_THRESHOLD((1 << 14) / 16) (LZ4_HASHTABLESIZE(1 << 14) / 16)
936
937LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) void
938LZ4_prepareTable(LZ4_stream_t_internal* const cctx,
939 const int inputSize,
940 const tableType_t tableType) {
941 /* If the table hasn't been used, it's guaranteed to be zeroed out, and is
942 * therefore safe to use no matter what mode we're in. Otherwise, we figure
943 * out if it's safe to leave as is or whether it needs to be reset.
944 */
945 if ((tableType_t)cctx->tableType != clearedTable) {
946 assert(inputSize >= 0)((void)0);
947 if ((tableType_t)cctx->tableType != tableType
948 || ((tableType == byU16) && cctx->currentOffset + (unsigned)inputSize >= 0xFFFFU)
949 || ((tableType == byU32) && cctx->currentOffset > 1 GB*(1U<<30))
950 || tableType == byPtr
951 || inputSize >= LZ4_CLEAR_TABLE_THRESHOLD((1 << 14) / 16))
952 {
953 DEBUGLOG(4, "LZ4_prepareTable: Resetting table in %p", (void*)cctx){};
954 MEM_INIT(cctx->hashTable, 0, LZ4_HASHTABLESIZE)memset(((cctx->hashTable)),((0)),(((1 << 14))));
955 cctx->currentOffset = 0;
956 cctx->tableType = (U32)clearedTable;
957 } else {
958 DEBUGLOG(4, "LZ4_prepareTable: Re-use hash table (no reset)"){};
959 }
960 }
961
962 /* Adding a gap, so all previous entries are > LZ4_DISTANCE_MAX back,
963 * is faster than compressing without a gap.
964 * However, compressing with currentOffset == 0 is faster still,
965 * so we preserve that case.
966 */
967 if (cctx->currentOffset != 0 && tableType == byU32) {
968 DEBUGLOG(5, "LZ4_prepareTable: adding 64KB to currentOffset"){};
969 cctx->currentOffset += 64 KB*(1 <<10);
970 }
971
972 /* Finally, clear history */
973 cctx->dictCtx = NULL((void*)0);
974 cctx->dictionary = NULL((void*)0);
975 cctx->dictSize = 0;
976}
977
978/* LZ4_match8() : the 8 bytes at p and q are equal */
979LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) int LZ4_match8(const void* p, const void* q)
980{
981 if (sizeof(reg_t) == 8) return LZ4_read_ARCH(p) == LZ4_read_ARCH(q);
982 return (LZ4_read32(p) == LZ4_read32(q))
983 && (LZ4_read32((const BYTE*)p + 4) == LZ4_read32((const BYTE*)q + 4));
984}
985
986/* state of an extDict compression which resumes in prefix mode (see LZ4_compress_generic()) */
987typedef struct {
988 const BYTE* ip; /* end of a match : resumes at the test of the next position */
989 BYTE* op;
990 U32 startIndex;
991} LZ4_resume_t;
992
993/** LZ4_compress_generic_validated() :
994 * inlined, to ensure branches are decided at compilation time.
995 * The following conditions are presumed already validated:
996 * - source != NULL
997 * - inputSize > 0
998 */
999LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) int LZ4_compress_generic_validated(
1000 LZ4_stream_t_internal* const cctx,
1001 const char* const source,
1002 char* const dest,
1003 const int inputSize,
1004 int* inputConsumed, /* only written when outputDirective == fillOutput */
1005 const int maxOutputSize,
1006 const limitedOutput_directive outputDirective,
1007 const tableType_t tableType,
1008 const dict_directive dictDirective,
1009 const dictIssue_directive dictIssue,
1010 const int acceleration,
1011 LZ4_resume_t* const suspend, /* usingExtDict : stops when the dictionary is out of reach, saving its state */
1012 const LZ4_resume_t* const resume) /* withPrefix64k : resumes such a compression */
1013{
1014 int result;
1015 const BYTE* ip = resume ? resume->ip : (const BYTE*)source;
1016
1017 U32 const startIndex = resume ? resume->startIndex : cctx->currentOffset;
1018 const BYTE* base = (const BYTE*)source - startIndex;
1019 const BYTE* lowLimit;
1020
1021 const LZ4_stream_t_internal* dictCtx = (const LZ4_stream_t_internal*) cctx->dictCtx;
1022 const BYTE* const dictionary =
1023 dictDirective == usingDictCtx ? dictCtx->dictionary : cctx->dictionary;
1024 const U32 dictSize =
1025 dictDirective == usingDictCtx ? dictCtx->dictSize : cctx->dictSize;
1026 const U32 dictDelta =
1027 (dictDirective == usingDictCtx) ? startIndex - dictCtx->currentOffset : 0; /* make indexes in dictCtx comparable with indexes in current context */
1028
1029 int const maybe_extMem = (dictDirective == usingExtDict) || (dictDirective == usingDictCtx);
1030 U32 const prefixIdxLimit = startIndex - dictSize; /* used when dictDirective == dictSmall */
1031 const BYTE* const dictEnd = dictionary ? dictionary + dictSize : dictionary;
1032 const BYTE* anchor = resume ? resume->ip : (const BYTE*)source;
1033 const BYTE* const iend = (const BYTE*)source + inputSize;
1034 const BYTE* mflimitPlusOne; /* set after the size check : would precede a small input */
1035 const BYTE* matchlimit;
1036 const BYTE* seqLimit; /* suspend : mflimitPlusOne, or earlier, where the dictionary gets out of reach */
1037
1038 /* the dictCtx currentOffset is indexed on the start of the dictionary,
1039 * while a dictionary in the current context precedes the currentOffset */
1040 const BYTE* dictBase = (dictionary == NULL((void*)0)) ? NULL((void*)0) :
1041 (dictDirective == usingDictCtx) ?
1042 dictionary + dictSize - dictCtx->currentOffset :
1043 dictionary + dictSize - startIndex;
1044
1045 BYTE* op = resume ? resume->op : (BYTE*)dest;
1046 BYTE* const olimit = (BYTE*)dest + maxOutputSize;
1047
1048 U32 offset = 0;
1049 U32 forwardH;
1050 const BYTE* filledIp = NULL((void*)0); /* fillOutput only ; set by catch up (resume : never with fillOutput) */
1051
1052 DEBUGLOG(5, "LZ4_compress_generic_validated: srcSize=%i, tableType=%u", inputSize, tableType){};
1053 assert(ip != NULL)((void)0);
1054 if (tableType == byU16) assert(inputSize<LZ4_64Klimit)((void)0); /* Size too large (not within 64K limit) */
1055 if (tableType == byPtr) assert(dictDirective==noDict)((void)0); /* only supported use case with byPtr */
1056 /* If init conditions are not met, we don't have to mark stream
1057 * as having dirty context, since no action was taken yet */
1058 if (outputDirective == fillOutput && maxOutputSize < 1) { return 0; } /* Impossible to store anything */
1059 assert(acceleration >= 1)((void)0);
1060
1061 /* resume : candidates are within source (see LZ4_compress_generic()) */
1062 lowLimit = (const BYTE*)source - ((dictDirective == withPrefix64k) && !resume ? dictSize : 0);
1063
1064 if (!resume) { /* resume : context state already updated */
1065 /* Update context state */
1066 if (dictDirective == usingDictCtx) {
1067 /* Subsequent linked blocks can't use the dictionary. */
1068 /* Instead, they use the block we just compressed. */
1069 cctx->dictCtx = NULL((void*)0);
1070 cctx->dictSize = (U32)inputSize;
1071 } else {
1072 cctx->dictSize += (U32)inputSize;
1073 }
1074 cctx->currentOffset += (U32)inputSize;
1075 cctx->tableType = (U32)tableType;
1076
1077 if (inputSize<LZ4_minLength) goto _last_literals; /* Input too small, no compression (all literals) */
1078 }
1079 mflimitPlusOne = iend - MFLIMIT12 + 1;
1080 matchlimit = iend - LASTLITERALS5;
1081 seqLimit = mflimitPlusOne;
1082 if ((suspend != NULL((void*)0)) && (inputSize > LZ4_DISTANCE_MAX65535 + MFLIMIT12 - 1)) /* source + LZ4_DISTANCE_MAX < mflimitPlusOne */
1083 seqLimit = (const BYTE*)source + LZ4_DISTANCE_MAX65535;
1084
1085 if (resume) goto _resume;
1086
1087 /* First Byte */
1088 LZ4_putPosition(ip, cctx->hashTable, tableType, base);
1089 ip++; forwardH = LZ4_hashPosition(ip, tableType);
1090
1091 /* Main Loop */
1092 for ( ; ; ) {
1093 const BYTE* match;
1094 BYTE* token;
1095
1096 /* Find a match */
1097 if (tableType == byPtr) {
1098 const BYTE* forwardIp = ip;
1099 int step = 1;
1100 int searchMatchNb = acceleration << LZ4_skipTrigger;
1101 do {
1102 U32 const h = forwardH;
1103 ip = forwardIp;
1104 forwardIp += step;
1105 step = (searchMatchNb++ >> LZ4_skipTrigger);
1106
1107 if (unlikely(forwardIp > mflimitPlusOne)(__builtin_expect (((forwardIp > mflimitPlusOne) != 0),(0)
) )) goto _last_literals;
1108 assert(ip < mflimitPlusOne)((void)0);
1109
1110 match = LZ4_getPositionOnHash(h, cctx->hashTable, tableType);
1111 forwardH = LZ4_hashPosition(forwardIp, tableType);
1112 LZ4_putPositionOnHash(ip, h, cctx->hashTable, tableType);
1113
1114 } while ( (match+LZ4_DISTANCE_MAX65535 < ip)
1115 || (LZ4_read32(match) != LZ4_read32(ip)) );
1116
1117 } else { /* byU32, byU16 */
1118
1119 const BYTE* forwardIp = ip;
1120 int step = 1;
1121 int searchMatchNb = acceleration << LZ4_skipTrigger;
1122 do {
1123 U32 const h = forwardH;
1124 U32 const current = (U32)(forwardIp - base);
1125 U32 matchIndex = LZ4_getIndexOnHash(h, cctx->hashTable, tableType);
1126 assert(matchIndex <= current)((void)0);
1127 assert(forwardIp - base < (ptrdiff_t)(2 GB - 1))((void)0);
1128 ip = forwardIp;
1129 forwardIp += step;
1130 step = (searchMatchNb++ >> LZ4_skipTrigger);
1131
1132 if (unlikely(forwardIp > mflimitPlusOne)(__builtin_expect (((forwardIp > mflimitPlusOne) != 0),(0)
) )) goto _last_literals;
1133 assert(ip < mflimitPlusOne)((void)0);
1134
1135 if (dictDirective == usingDictCtx) {
1136 if (matchIndex < startIndex) {
1137 /* there was no match, try the dictionary */
1138 assert(tableType == byU32)((void)0);
1139 matchIndex = LZ4_getIndexOnHash(h, dictCtx->hashTable, byU32);
1140 match = dictBase + matchIndex;
1141 matchIndex += dictDelta; /* make dictCtx index comparable with current context */
1142 lowLimit = dictionary;
1143 } else {
1144 match = base + matchIndex;
1145 lowLimit = (const BYTE*)source;
1146 }
1147 } else if (dictDirective == usingExtDict) {
1148 /* select without branch : dictionary and prefix candidates alternate unpredictably.
1149 * relative to dictEnd or source, within their buffers (base can be NULL) */
1150 ptrdiff_t const relIdx = (ptrdiff_t)matchIndex - (ptrdiff_t)startIndex; /* < 0 : within dictionary */
1151 match = ((relIdx < 0) ? dictEnd : (const BYTE*)source) + relIdx;
1152 } else { /* single continuous memory segment */
1153 match = base + matchIndex;
1154 }
1155 forwardH = LZ4_hashPosition(forwardIp, tableType);
1156 LZ4_putIndexOnHash(current, h, cctx->hashTable, tableType);
1157
1158 DEBUGLOG(7, "candidate at pos=%u (offset=%u \n", matchIndex, current - matchIndex){};
1159 if ((dictIssue == dictSmall) && (matchIndex < prefixIdxLimit)) { continue; } /* match outside of valid area */
1160 assert(matchIndex < current)((void)0);
1161 /* noDict : the candidate is within input, so it is compared before checking its distance :
1162 * this order is faster (better branch prediction) */
1163 assert((dictDirective != noDict) || (match >= (const BYTE*)source))((void)0);
1164 if ( (dictDirective != noDict)
1165 && ((tableType != byU16) || (LZ4_DISTANCE_MAX65535 < LZ4_DISTANCE_ABSOLUTE_MAX65535))
1166 && (matchIndex+LZ4_DISTANCE_MAX65535 < current)) {
1167 continue;
1168 } /* too far */
1169
1170 if (LZ4_read32(match) == LZ4_read32(ip)) {
1171 if ( (dictDirective == noDict)
1172 && ((tableType != byU16) || (LZ4_DISTANCE_MAX65535 < LZ4_DISTANCE_ABSOLUTE_MAX65535))
1173 && (matchIndex+LZ4_DISTANCE_MAX65535 < current)) {
1174 continue;
1175 } /* too far */
1176 assert((current - matchIndex) <= LZ4_DISTANCE_MAX)((void)0); /* match now expected within distance */
1177 if (maybe_extMem) offset = current - matchIndex;
1178 if (dictDirective == usingExtDict) /* lowLimit : only needed once a match is found */
1179 lowLimit = (matchIndex < startIndex) ? dictionary : (const BYTE*)source;
1180 break; /* match found */
1181 }
1182
1183 } while(1);
1184 }
1185
1186 /* Catch up */
1187 filledIp = ip;
1188 assert(ip > anchor)((void)0); /* this is always true as ip has been advanced before entering the main loop */
1189 if ((match > lowLimit) && unlikely(ip[-1] == match[-1])(__builtin_expect (((ip[-1] == match[-1]) != 0),(0)) )) {
1190 do { ip--; match--; } while (((ip > anchor) & (match > lowLimit)) && (unlikely(ip[-1] == match[-1])(__builtin_expect (((ip[-1] == match[-1]) != 0),(0)) )));
1191 }
1192
1193 /* Encode Literals */
1194 { unsigned const litLength = (unsigned)(ip - anchor);
1195 token = op++;
1196 if ((outputDirective == limitedOutput) && /* Check output buffer overflow */
1197 (unlikely(op + litLength + (2 + 1 + LASTLITERALS) + (litLength/255) > olimit)(__builtin_expect (((op + litLength + (2 + 1 + 5) + (litLength
/255) > olimit) != 0),(0)) )) ) {
1198 return 0; /* cannot compress within `dst` budget. Stored indexes in hash table are nonetheless fine */
1199 }
1200 if ((outputDirective == fillOutput) &&
1201 (unlikely(op + (litLength+240)/255 /* litlen */ + litLength /* literals */ + 2 /* offset */ + 1 /* token */ + MFLIMIT - MINMATCH /* min last literals so last match is <= end - MFLIMIT */ > olimit)(__builtin_expect (((op + (litLength+240)/255 + litLength + 2
+ 1 + 12 - 4 > olimit) != 0),(0)) ))) {
1202 op--;
1203 goto _last_literals;
1204 }
1205 if (litLength >= RUN_MASK((1U<<(8-4))-1)) {
1206 unsigned len = litLength - RUN_MASK((1U<<(8-4))-1);
1207 *token = (RUN_MASK((1U<<(8-4))-1)<<ML_BITS4);
1208 for(; len >= 255 ; len-=255) *op++ = 255;
1209 *op++ = (BYTE)len;
1210 }
1211 else *token = (BYTE)(litLength<<ML_BITS4);
1212
1213 /* Copy Literals */
1214 LZ4_wildCopy8(op, anchor, op+litLength);
1215 op+=litLength;
1216 DEBUGLOG(6, "seq.start:%i, literals=%u, match.start:%i",{}
1217 (int)(anchor-(const BYTE*)source), litLength, (int)(ip-(const BYTE*)source)){};
1218 }
1219
1220_next_match:
1221 /* at this stage, the following variables must be correctly set :
1222 * - ip : at start of LZ operation
1223 * - match : at start of previous pattern occurrence; can be within current prefix, or within extDict
1224 * - offset : if maybe_ext_memSegment==1 (constant)
1225 * - lowLimit : must be == dictionary to mean "match is within extDict"; must be == source otherwise
1226 * - token and *token : position to write 4-bits for match length; higher 4-bits for literal length supposed already written
1227 */
1228
1229 if ((outputDirective == fillOutput) &&
1230 (op + 2 /* offset */ + 1 /* token */ + MFLIMIT12 - MINMATCH4 /* min last literals so last match is <= end - MFLIMIT */ > olimit)) {
1231 /* the match was too close to the end, rewind and go to last literals */
1232 op = token;
1233 goto _last_literals;
1234 }
1235
1236 /* Encode Offset */
1237 if (maybe_extMem) { /* static test */
1238 DEBUGLOG(6, " with offset=%u (ext if > %i)", offset, (int)(ip - (const BYTE*)source)){};
1239 assert(offset <= LZ4_DISTANCE_MAX && offset > 0)((void)0);
1240 LZ4_writeLE16(op, (U16)offset); op+=2;
1241 } else {
1242 DEBUGLOG(6, " with offset=%u (same segment)", (U32)(ip - match)){};
1243 assert(ip-match <= LZ4_DISTANCE_MAX)((void)0);
1244 LZ4_writeLE16(op, (U16)(ip - match)); op+=2;
1245 }
1246
1247 /* Encode MatchLength */
1248 { unsigned matchCode;
1249
1250 if ( (dictDirective==usingExtDict || dictDirective==usingDictCtx)
1251 && (lowLimit==dictionary) /* match within extDict */ ) {
1252 const BYTE* limit = ip + (dictEnd-match);
1253 assert(dictEnd > match)((void)0);
1254 if (limit > matchlimit) limit = matchlimit;
1255 matchCode = LZ4_count(ip+MINMATCH4, match+MINMATCH4, limit);
1256 ip += (size_t)matchCode + MINMATCH4;
1257 if (ip==limit) {
1258 unsigned const more = LZ4_count(limit, (const BYTE*)source, matchlimit);
1259 matchCode += more;
1260 ip += more;
1261 }
1262 DEBUGLOG(6, " with matchLength=%u starting in extDict", matchCode+MINMATCH){};
1263 } else {
1264 matchCode = LZ4_count(ip+MINMATCH4, match+MINMATCH4, matchlimit);
1265 ip += (size_t)matchCode + MINMATCH4;
1266 DEBUGLOG(6, " with matchLength=%u", matchCode+MINMATCH){};
1267 }
1268
1269 if ((outputDirective) && /* Check output buffer overflow */
1270 (unlikely(op + (1 + LASTLITERALS) + (matchCode+240)/255 > olimit)(__builtin_expect (((op + (1 + 5) + (matchCode+240)/255 > olimit
) != 0),(0)) )) ) {
1271 if (outputDirective == fillOutput) {
1272 /* Match description too long : reduce it */
1273 U32 newMatchCode = 15 /* in token */ - 1 /* to avoid needing a zero byte */ + ((U32)(olimit - op) - 1 - LASTLITERALS5) * 255;
1274 ip -= matchCode - newMatchCode;
1275 assert(newMatchCode < matchCode)((void)0);
1276 matchCode = newMatchCode;
1277 if (unlikely(ip <= filledIp)(__builtin_expect (((ip <= filledIp) != 0),(0)) )) {
1278 /* We have already filled up to filledIp so if ip ends up less than filledIp
1279 * we have positions in the hash table beyond the current position. This is
1280 * a problem if we reuse the hash table. So we have to remove these positions
1281 * from the hash table.
1282 */
1283 const BYTE* ptr;
1284 DEBUGLOG(5, "Clearing %u positions", (U32)(filledIp - ip)){};
1285 for (ptr = ip; ptr <= filledIp; ++ptr) {
1286 U32 const h = LZ4_hashPosition(ptr, tableType);
1287 LZ4_clearHash(h, cctx->hashTable, tableType);
1288 }
1289 }
1290 } else {
1291 assert(outputDirective == limitedOutput)((void)0);
1292 return 0; /* cannot compress within `dst` budget. Stored indexes in hash table are nonetheless fine */
1293 }
1294 }
1295 if (matchCode >= ML_MASK((1U<<4)-1)) {
1296 *token += ML_MASK((1U<<4)-1);
1297 matchCode -= ML_MASK((1U<<4)-1);
1298 LZ4_write32(op, 0xFFFFFFFF);
1299 while (matchCode >= 4*255) {
1300 op+=4;
1301 LZ4_write32(op, 0xFFFFFFFF);
1302 matchCode -= 4*255;
1303 }
1304 op += matchCode / 255;
1305 *op++ = (BYTE)(matchCode % 255);
1306 } else
1307 *token += (BYTE)(matchCode);
1308 }
1309 /* Ensure we have enough space for the last literals. */
1310 assert(!(outputDirective == fillOutput && op + 1 + LASTLITERALS > olimit))((void)0);
1311
1312 anchor = ip;
1313
1314 /* Test end of chunk */
1315 if (ip >= seqLimit) {
1316 if ((suspend == NULL((void*)0)) || (ip >= mflimitPlusOne)) break;
1317 /* extDict : from ip, all candidates (and catch up) are beyond reach of the dictionary :
1318 * stop, to resume in prefix mode, which is faster */
1319 suspend->ip = ip;
1320 suspend->op = op;
1321 suspend->startIndex = startIndex;
1322 return 0;
1323 }
1324
1325_resume:
1326 /* Fill table, and test next position.
1327 * First, the position after the previous occurrence of ip-1, if it matches 8+ bytes :
1328 * it breaks chains of short matches, which the table alone can produce on periodic data. */
1329 if (tableType == byPtr) {
1330
1331 U32 const hPrev = LZ4_hashPosition(ip-1, tableType);
1332 const BYTE* const prev = LZ4_getPositionOnHash(hPrev, cctx->hashTable, tableType);
1333 U32 const h = LZ4_hashPosition(ip, tableType);
1334 LZ4_putPositionOnHash(ip-1, hPrev, cctx->hashTable, tableType);
1335 match = LZ4_getPositionOnHash(h, cctx->hashTable, tableType);
1336 if ((prev+1+LZ4_DISTANCE_MAX65535 >= ip) && LZ4_match8(prev+1, ip)) match = prev+1;
1337 LZ4_putPositionOnHash(ip, h, cctx->hashTable, tableType);
1338 if ( (match+LZ4_DISTANCE_MAX65535 >= ip)
1339 && (LZ4_read32(match) == LZ4_read32(ip)) )
1340 { token=op++; *token=0; goto _next_match; }
1341
1342 } else { /* byU32, byU16 */
1343
1344 U32 const h = LZ4_hashPosition(ip, tableType);
1345 U32 const current = (U32)(ip-base);
1346 U32 const hPrev = LZ4_hashPosition(ip-1, tableType);
1347 U32 prevIndex = LZ4_getIndexOnHash(hPrev, cctx->hashTable, tableType);
1348 U32 matchIndex;
1349 LZ4_putIndexOnHash(current-1, hPrev, cctx->hashTable, tableType);
1350 if ((dictDirective == usingDictCtx) && (prevIndex < startIndex)) {
1351 /* no occurrence in the current context : try the dictionary */
1352 prevIndex = LZ4_getIndexOnHash(hPrev, dictCtx->hashTable, byU32) + dictDelta;
1353 }
1354 { /* used table (small block, see LZ4_prepareTable()) : a stale entry yields the candidate of an empty slot
1355 * of a cleared table (0), the position after the first one : the output doesn't depend on the table's history */
1356 int const usedTable = (dictDirective == noDict) && (dictIssue == dictSmall);
1357 U32 const ctxIndex = ((usedTable && (prevIndex < startIndex)) ? startIndex : prevIndex) + 1;
1358 int const inDict = (dictDirective == usingExtDict || dictDirective == usingDictCtx) && (ctxIndex < startIndex);
1359 if ( ((dictIssue==dictSmall) ? (ctxIndex >= prefixIdxLimit) : 1)
1360 && (((tableType==byU16) && (LZ4_DISTANCE_MAX65535 == LZ4_DISTANCE_ABSOLUTE_MAX65535)) ? 1 : (ctxIndex+LZ4_DISTANCE_MAX65535 >= current))
1361 && (!inDict || (ctxIndex + 8 <= startIndex)) /* the 8 compared bytes are within the dictionary */
1362 && LZ4_match8(inDict ? dictBase + (ctxIndex - dictDelta) : base + ctxIndex, ip) ) {
1363 matchIndex = ctxIndex;
1364 } else {
1365 matchIndex = LZ4_getIndexOnHash(h, cctx->hashTable, tableType);
1366 if ((dictDirective == usingDictCtx) && (matchIndex < startIndex))
1367 matchIndex = LZ4_getIndexOnHash(h, dictCtx->hashTable, byU32) + dictDelta;
1368 }
1369 }
1370 assert(matchIndex < current)((void)0);
1371 if (dictDirective == usingExtDict) { /* select without branch */
1372 ptrdiff_t const relIdx = (ptrdiff_t)matchIndex - (ptrdiff_t)startIndex; /* < 0 : within dictionary */
1373 match = ((relIdx < 0) ? dictEnd : (const BYTE*)source) + relIdx;
1374 } else if ((dictDirective == usingDictCtx) && (matchIndex < startIndex)) {
1375 match = dictBase + (matchIndex - dictDelta);
1376 lowLimit = dictionary; /* required for match length counter */
1377 } else {
1378 match = base + matchIndex;
1379 if (dictDirective == usingDictCtx)
1380 lowLimit = (const BYTE*)source; /* required for match length counter */
1381 }
1382 LZ4_putIndexOnHash(current, h, cctx->hashTable, tableType);
1383 assert(matchIndex < current)((void)0);
1384 if ( ((dictIssue==dictSmall) ? (matchIndex >= prefixIdxLimit) : 1)
1385 && (((tableType==byU16) && (LZ4_DISTANCE_MAX65535 == LZ4_DISTANCE_ABSOLUTE_MAX65535)) ? 1 : (matchIndex+LZ4_DISTANCE_MAX65535 >= current))
1386 && (LZ4_read32(match) == LZ4_read32(ip)) ) {
1387 token=op++;
1388 *token=0;
1389 if (maybe_extMem) offset = current - matchIndex;
1390 if (dictDirective == usingExtDict)
1391 lowLimit = (matchIndex < startIndex) ? dictionary : (const BYTE*)source; /* required for match length counter */
1392 DEBUGLOG(6, "seq.start:%i, literals=%u, match.start:%i",{}
1393 (int)(anchor-(const BYTE*)source), 0, (int)(ip-(const BYTE*)source)){};
1394 goto _next_match;
1395 }
1396 }
1397
1398 /* Prepare next loop */
1399 forwardH = LZ4_hashPosition(++ip, tableType);
1400
1401 }
1402
1403_last_literals:
1404 /* Encode Last Literals */
1405 { size_t lastRun = (size_t)(iend - anchor);
1406 if ( (outputDirective) && /* Check output buffer overflow */
1407 (op + lastRun + 1 + ((lastRun+255-RUN_MASK((1U<<(8-4))-1))/255) > olimit)) {
1408 if (outputDirective == fillOutput) {
1409 /* adapt lastRun to fill 'dst' */
1410 assert(olimit >= op)((void)0);
1411 lastRun = (size_t)(olimit-op) - 1/*token*/;
1412 lastRun -= (lastRun + 256 - RUN_MASK((1U<<(8-4))-1)) / 256; /*additional length tokens*/
1413 } else {
1414 assert(outputDirective == limitedOutput)((void)0);
1415 return 0; /* cannot compress within `dst` budget. Stored indexes in hash table are nonetheless fine */
1416 }
1417 }
1418 DEBUGLOG(6, "Final literal run : %i literals", (int)lastRun){};
1419 if (lastRun >= RUN_MASK((1U<<(8-4))-1)) {
1420 size_t accumulator = lastRun - RUN_MASK((1U<<(8-4))-1);
1421 *op++ = RUN_MASK((1U<<(8-4))-1) << ML_BITS4;
1422 for(; accumulator >= 255 ; accumulator-=255) *op++ = 255;
1423 *op++ = (BYTE) accumulator;
1424 } else {
1425 *op++ = (BYTE)(lastRun<<ML_BITS4);
1426 }
1427 LZ4_memcpy(op, anchor, lastRun)__builtin_memcpy(op, anchor, lastRun);
1428 ip = anchor + lastRun;
1429 op += lastRun;
1430 }
1431
1432 if (outputDirective == fillOutput) {
1433 *inputConsumed = (int) (((const char*)ip)-source);
1434 }
1435 result = (int)(((char*)op) - dest);
1436 assert(result > 0)((void)0);
1437 DEBUGLOG(5, "LZ4_compress_generic: compressed %i bytes into %i bytes", inputSize, result){};
1438 return result;
1439}
1440
1441/* second part of an extDict compression, in prefix mode (see LZ4_compress_generic()).
1442 * not inlined : a single instance serves all invocations */
1443LZ4_FORCE_NOINLINEstatic __attribute__((noinline)) int LZ4_compress_resumeWithPrefix(LZ4_stream_t_internal* cctx,
1444 const char* src, char* dst, int srcSize, int dstCapacity, int acceleration,
1445 const LZ4_resume_t* state)
1446{
1447 return LZ4_compress_generic_validated(cctx, src, dst, srcSize, NULL((void*)0), dstCapacity, limitedOutput,
1448 byU32, withPrefix64k, noDictIssue, acceleration, NULL((void*)0), state);
1449}
1450
1451/** LZ4_compress_generic() :
1452 * inlined, to ensure branches are decided at compilation time;
1453 * takes care of src == (NULL, 0)
1454 * and forward the rest to LZ4_compress_generic_validated */
1455LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) int LZ4_compress_generic(
1456 LZ4_stream_t_internal* const cctx,
1457 const char* const src,
1458 char* const dst,
1459 const int srcSize,
1460 int *inputConsumed, /* only written when outputDirective == fillOutput */
1461 const int dstCapacity,
1462 const limitedOutput_directive outputDirective,
1463 const tableType_t tableType,
1464 const dict_directive dictDirective,
1465 const dictIssue_directive dictIssue,
1466 const int acceleration)
1467{
1468 DEBUGLOG(5, "LZ4_compress_generic: srcSize=%i, dstCapacity=%i",{}
1469 srcSize, dstCapacity){};
1470
1471 if ((U32)srcSize > (U32)LZ4_MAX_INPUT_SIZE0x7E000000) { return 0; } /* Unsupported srcSize, too large (or negative) */
1472 if (srcSize == 0) { /* src == NULL supported if srcSize == 0 */
1473 if (outputDirective != notLimited && dstCapacity <= 0) return 0; /* no output, can't write anything */
1474 DEBUGLOG(5, "Generating an empty block"){};
1475 assert(outputDirective == notLimited || dstCapacity >= 1)((void)0);
1476 assert(dst != NULL)((void)0);
1477 dst[0] = 0;
1478 if (outputDirective == fillOutput) {
1479 assert (inputConsumed != NULL)((void)0);
1480 *inputConsumed = 0;
1481 }
1482 return 1;
1483 }
1484 assert(src != NULL)((void)0);
1485
1486 if ((dictDirective == usingExtDict) && (dictIssue == noDictIssue)) {
1487 /* beyond LZ4_DISTANCE_MAX, the dictionary is out of reach : the rest of the input is compressed in prefix mode */
1488 LZ4_resume_t state;
1489 int result;
1490 assert(tableType == byU32)((void)0);
1491 assert(outputDirective != fillOutput)((void)0);
1492 state.ip = NULL((void*)0);
1493 result = LZ4_compress_generic_validated(cctx, src, dst, srcSize, inputConsumed, dstCapacity, outputDirective,
1494 tableType, usingExtDict, noDictIssue, acceleration, &state, NULL((void*)0));
1495 if (state.ip == NULL((void*)0)) return result; /* completed (or failed) in extDict mode */
1496 /* notLimited : dst is presumed large enough for LZ4_compressBound() */
1497 return LZ4_compress_resumeWithPrefix(cctx, src, dst, srcSize,
1498 (outputDirective == notLimited) ? LZ4_COMPRESSBOUND(srcSize)((unsigned)(srcSize) > (unsigned)0x7E000000 ? 0 : (srcSize
) + ((srcSize)/255) + 16) : dstCapacity,
1499 acceleration, &state);
1500 }
1501
1502 return LZ4_compress_generic_validated(cctx, src, dst, srcSize,
1503 inputConsumed, /* only written into if outputDirective == fillOutput */
1504 dstCapacity, outputDirective,
1505 tableType, dictDirective, dictIssue, acceleration, NULL((void*)0), NULL((void*)0));
1506}
1507
1508
1509/* values < 1 select the default, values > LZ4_ACCELERATION_MAX are capped */
1510static int LZ4_clampAcceleration(int acceleration)
1511{
1512 if (acceleration < 1) return LZ4_ACCELERATION_DEFAULT1;
1513 if (acceleration > LZ4_ACCELERATION_MAX65537) return LZ4_ACCELERATION_MAX65537;
1514 return acceleration;
1515}
1516
1517/* table type for inputs too large for byU16.
1518 * byPtr (32-bit only) requires src > LZ4_DISTANCE_MAX,
1519 * so that empty (NULL) entries are always beyond the maximum distance */
1520static tableType_t LZ4_largeInputTableType(const char* src)
1521{
1522 (void)src; /* unused on 64-bit systems */
1523 return ((sizeof(void*)==4) && ((uptrval)src > LZ4_DISTANCE_MAX65535)) ? byPtr : byU32;
1524}
1525
1526/* outputDirective must be a compile-time constant */
1527LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) int LZ4_compress_fastReset_generic(
1528 LZ4_stream_t_internal* const ctx,
1529 const char* const src,
1530 char* const dst,
1531 const int srcSize,
1532 const int dstCapacity,
1533 const limitedOutput_directive outputDirective,
1534 const int acceleration)
1535{
1536 if (srcSize < LZ4_64Klimit) {
1537 LZ4_prepareTable(ctx, srcSize, byU16);
1538 if (ctx->currentOffset) { /* table re-used : stale entries must be rejected */
1539 return LZ4_compress_generic(ctx, src, dst, srcSize, NULL((void*)0), dstCapacity, outputDirective, byU16, noDict, dictSmall, acceleration);
1540 } else {
1541 return LZ4_compress_generic(ctx, src, dst, srcSize, NULL((void*)0), dstCapacity, outputDirective, byU16, noDict, noDictIssue, acceleration);
1542 }
1543 } else {
1544 const tableType_t tableType = LZ4_largeInputTableType(src);
1545 LZ4_prepareTable(ctx, srcSize, tableType);
1546 return LZ4_compress_generic(ctx, src, dst, srcSize, NULL((void*)0), dstCapacity, outputDirective, tableType, noDict, noDictIssue, acceleration);
1547 }
1548}
1549
1550int LZ4_compress_fast_extState(void* state, const char* source, char* dest, int inputSize, int maxOutputSize, int acceleration)
1551{
1552 /* a freshly initialized state is valid for _fastReset() */
1553 LZ4_stream_t* const s = LZ4_initStream(state, sizeof(LZ4_stream_t));
1554 assert(s != NULL)((void)0);
1555 return LZ4_compress_fast_extState_fastReset(s, source, dest, inputSize, maxOutputSize, acceleration);
1556}
1557
1558/**
1559 * LZ4_compress_fast_extState_fastReset() :
1560 * A variant of LZ4_compress_fast_extState().
1561 *
1562 * Using this variant avoids an expensive initialization step. It is only safe
1563 * to call if the state buffer is known to be correctly initialized already
1564 * (see comment in lz4.h on LZ4_resetStream_fast() for a definition of
1565 * "correctly initialized").
1566 */
1567int LZ4_compress_fast_extState_fastReset(void* state, const char* src, char* dst, int srcSize, int dstCapacity, int acceleration)
1568{
1569 LZ4_stream_t_internal* const ctx = &((LZ4_stream_t*)state)->internal_donotuse;
1570 acceleration = LZ4_clampAcceleration(acceleration);
1571 assert(ctx != NULL)((void)0);
1572
1573 if (dstCapacity >= LZ4_compressBound(srcSize)) {
1574 return LZ4_compress_fastReset_generic(ctx, src, dst, srcSize, 0, notLimited, acceleration);
1575 } else {
1576 return LZ4_compress_fastReset_generic(ctx, src, dst, srcSize, dstCapacity, limitedOutput, acceleration);
1577 }
1578}
1579
1580
1581int LZ4_compress_fast(const char* src, char* dest, int srcSize, int dstCapacity, int acceleration)
1582{
1583 int result;
1584#if (LZ4_HEAPMODE0)
1585 LZ4_stream_t* const ctxPtr = (LZ4_stream_t*)ALLOC(sizeof(LZ4_stream_t))malloc(sizeof(LZ4_stream_t)); /* malloc-calloc always properly aligned */
1586 if (ctxPtr == NULL((void*)0)) return 0;
1587#else
1588 LZ4_stream_t ctx;
1589 LZ4_stream_t* const ctxPtr = &ctx;
1590#endif
1591 result = LZ4_compress_fast_extState(ctxPtr, src, dest, srcSize, dstCapacity, acceleration);
1592
1593#if (LZ4_HEAPMODE0)
1594 FREEMEM(ctxPtr)free(ctxPtr);
1595#endif
1596 return result;
1597}
1598
1599
1600int LZ4_compress_default(const char* src, char* dst, int srcSize, int dstCapacity)
1601{
1602 return LZ4_compress_fast(src, dst, srcSize, dstCapacity, 1);
1603}
1604
1605
1606/* Note!: This function leaves the stream in an unclean/broken state!
1607 * It is not safe to subsequently use the same state with a _fastReset() or
1608 * _continue() call without resetting it. */
1609static int LZ4_compress_destSize_extState_internal(LZ4_stream_t* state, const char* src, char* dst, int* srcSizePtr, int targetDstSize, int acceleration)
1610{
1611 void* const s = LZ4_initStream(state, sizeof (*state));
1612 assert(s != NULL)((void)0); (void)s;
1613 acceleration = LZ4_clampAcceleration(acceleration);
1614
1615 if (targetDstSize >= LZ4_compressBound(*srcSizePtr)) { /* compression success is guaranteed */
1616 return LZ4_compress_fast_extState_fastReset(state, src, dst, *srcSizePtr, targetDstSize, acceleration);
1617 } else {
1618 if (*srcSizePtr < LZ4_64Klimit) {
1619 return LZ4_compress_generic(&state->internal_donotuse, src, dst, *srcSizePtr, srcSizePtr, targetDstSize, fillOutput, byU16, noDict, noDictIssue, acceleration);
1620 } else {
1621 return LZ4_compress_generic(&state->internal_donotuse, src, dst, *srcSizePtr, srcSizePtr, targetDstSize, fillOutput, LZ4_largeInputTableType(src), noDict, noDictIssue, acceleration);
1622 } }
1623}
1624
1625int LZ4_compress_destSize_extState(void* state, const char* src, char* dst, int* srcSizePtr, int targetDstSize, int acceleration)
1626{
1627 int const r = LZ4_compress_destSize_extState_internal((LZ4_stream_t*)state, src, dst, srcSizePtr, targetDstSize, acceleration);
1628 /* clean the state on exit */
1629 LZ4_initStream(state, sizeof (LZ4_stream_t));
1630 return r;
1631}
1632
1633
1634int LZ4_compress_destSize(const char* src, char* dst, int* srcSizePtr, int targetDstSize)
1635{
1636 int result;
1637#if (LZ4_HEAPMODE0)
1638 LZ4_stream_t* const ctx = (LZ4_stream_t*)ALLOC(sizeof(LZ4_stream_t))malloc(sizeof(LZ4_stream_t)); /* malloc-calloc always properly aligned */
1639 if (ctx == NULL((void*)0)) return 0;
1640#else
1641 LZ4_stream_t ctxBody;
1642 LZ4_stream_t* const ctx = &ctxBody;
1643#endif
1644 result = LZ4_compress_destSize_extState_internal(ctx, src, dst, srcSizePtr, targetDstSize, 1);
1645
1646#if (LZ4_HEAPMODE0)
1647 FREEMEM(ctx)free(ctx);
1648#endif
1649 return result;
1650}
1651
1652
1653
1654/*-******************************
1655* Streaming functions
1656********************************/
1657
1658#if !defined(LZ4_STATIC_LINKING_ONLY_DISABLE_MEMORY_ALLOCATION)
1659LZ4_stream_t* LZ4_createStream(void)
1660{
1661 LZ4_stream_t* const lz4s = (LZ4_stream_t*)ALLOC(sizeof(LZ4_stream_t))malloc(sizeof(LZ4_stream_t));
1662 LZ4_STATIC_ASSERT(sizeof(LZ4_stream_t) >= sizeof(LZ4_stream_t_internal)){ enum { LZ4_static_assert = 1/(int)(!!(sizeof(LZ4_stream_t) >=
sizeof(LZ4_stream_t_internal))) }; };
1663 DEBUGLOG(4, "LZ4_createStream %p", (void*)lz4s){};
1664 if (lz4s == NULL((void*)0)) return NULL((void*)0);
1665 LZ4_initStream(lz4s, sizeof(*lz4s));
1666 return lz4s;
1667}
1668#endif
1669
1670static size_t LZ4_stream_t_alignment(void)
1671{
1672#if LZ4_ALIGN_TEST1
1673 typedef struct { char c; LZ4_stream_t t; } t_a;
1674 return sizeof(t_a) - sizeof(LZ4_stream_t);
1675#else
1676 return 1; /* effectively disabled */
1677#endif
1678}
1679
1680LZ4_stream_t* LZ4_initStream (void* buffer, size_t size)
1681{
1682 DEBUGLOG(5, "LZ4_initStream"){};
1683 if (buffer == NULL((void*)0)) { return NULL((void*)0); }
1684 if (size < sizeof(LZ4_stream_t)) { return NULL((void*)0); }
1685 if (!LZ4_isAligned(buffer, LZ4_stream_t_alignment())) return NULL((void*)0);
1686 MEM_INIT(buffer, 0, sizeof(LZ4_stream_t_internal))memset(((buffer)),((0)),((sizeof(LZ4_stream_t_internal))));
1687 return (LZ4_stream_t*)buffer;
1688}
1689
1690/* resetStream is now deprecated,
1691 * prefer initStream() which is more general */
1692void LZ4_resetStream (LZ4_stream_t* LZ4_stream)
1693{
1694 DEBUGLOG(5, "LZ4_resetStream (ctx:%p)", (void*)LZ4_stream){};
1695 MEM_INIT(LZ4_stream, 0, sizeof(LZ4_stream_t_internal))memset(((LZ4_stream)),((0)),((sizeof(LZ4_stream_t_internal)))
);
1696}
1697
1698void LZ4_resetStream_fast(LZ4_stream_t* ctx) {
1699 LZ4_prepareTable(&(ctx->internal_donotuse), 0, byU32);
1700}
1701
1702#if !defined(LZ4_STATIC_LINKING_ONLY_DISABLE_MEMORY_ALLOCATION)
1703int LZ4_freeStream (LZ4_stream_t* LZ4_stream)
1704{
1705 if (!LZ4_stream) return 0; /* support free on NULL */
1706 DEBUGLOG(5, "LZ4_freeStream %p", (void*)LZ4_stream){};
1707 FREEMEM(LZ4_stream)free(LZ4_stream);
1708 return (0);
1709}
1710#endif
1711
1712
1713typedef enum { _ld_fast, _ld_slow } LoadDict_mode_e;
1714#define HASH_UNITsizeof(reg_t) sizeof(reg_t)
1715static int LZ4_loadDict_internal(LZ4_stream_t* LZ4_dict,
1716 const char* dictionary, int dictSize,
1717 LoadDict_mode_e _ld)
1718{
1719 LZ4_stream_t_internal* const dict = &LZ4_dict->internal_donotuse;
1720 const tableType_t tableType = byU32;
1721 const BYTE* p = (const BYTE*)dictionary;
1722 const BYTE* const dictEnd = p + dictSize;
1723 U32 idx32;
1724
1725 DEBUGLOG(4, "LZ4_loadDict (%i bytes from %p into %p)", dictSize, (void*)dictionary, (void*)LZ4_dict){};
1726
1727 /* It's necessary to reset the context,
1728 * and not just continue it with prepareTable()
1729 * to avoid any risk of generating overflowing matchIndex
1730 * when compressing using this dictionary */
1731 LZ4_resetStream(LZ4_dict);
1732
1733 /* We always increment the offset by 64 KB, since, if the dict is longer,
1734 * we truncate it to the last 64k, and if it's shorter, we still want to
1735 * advance by a whole window length so we can provide the guarantee that
1736 * there are only valid offsets in the window, which allows an optimization
1737 * in LZ4_compress_fast_continue() where it uses noDictIssue even when the
1738 * dictionary isn't a full 64k. */
1739 dict->currentOffset += 64 KB*(1 <<10);
1740 /* no longer a cleared table : LZ4_prepareTable() must check it,
1741 * even when the dictionary is too small to be used */
1742 dict->tableType = (U32)tableType;
1743
1744 if (dictSize < (int)HASH_UNITsizeof(reg_t)) {
1745 return 0;
1746 }
1747
1748 if ((dictEnd - p) > 64 KB*(1 <<10)) p = dictEnd - 64 KB*(1 <<10);
1749 dict->dictionary = p;
1750 dict->dictSize = (U32)(dictEnd - p);
1751 idx32 = dict->currentOffset - dict->dictSize;
1752
1753 while (p <= dictEnd-HASH_UNITsizeof(reg_t)) {
1754 U32 const h = LZ4_hashPosition(p, tableType);
1755 /* Note: overwriting => favors positions end of dictionary */
1756 LZ4_putIndexOnHash(idx32, h, dict->hashTable, tableType);
1757 p+=3; idx32+=3;
1758 }
1759
1760 if (_ld == _ld_slow) {
1761 /* Fill hash table with additional references, to improve compression capability */
1762 p = dict->dictionary;
1763 idx32 = dict->currentOffset - dict->dictSize;
1764 while (p <= dictEnd-HASH_UNITsizeof(reg_t)) {
1765 U32 const h = LZ4_hashPosition(p, tableType);
1766 U32 const limit = dict->currentOffset - 64 KB*(1 <<10);
1767 if (LZ4_getIndexOnHash(h, dict->hashTable, tableType) <= limit) {
1768 /* Note: not overwriting => favors positions beginning of dictionary */
1769 LZ4_putIndexOnHash(idx32, h, dict->hashTable, tableType);
1770 }
1771 p++; idx32++;
1772 }
1773 }
1774
1775 return (int)dict->dictSize;
1776}
1777
1778int LZ4_loadDict(LZ4_stream_t* LZ4_dict, const char* dictionary, int dictSize)
1779{
1780 return LZ4_loadDict_internal(LZ4_dict, dictionary, dictSize, _ld_fast);
1781}
1782
1783int LZ4_loadDictSlow(LZ4_stream_t* LZ4_dict, const char* dictionary, int dictSize)
1784{
1785 return LZ4_loadDict_internal(LZ4_dict, dictionary, dictSize, _ld_slow);
1786}
1787
1788void LZ4_attach_dictionary(LZ4_stream_t* workingStream, const LZ4_stream_t* dictionaryStream)
1789{
1790 const LZ4_stream_t_internal* dictCtx = (dictionaryStream == NULL((void*)0)) ? NULL((void*)0) :
1791 &(dictionaryStream->internal_donotuse);
1792
1793 DEBUGLOG(4, "LZ4_attach_dictionary (%p, %p, size %u)",{}
1794 (void*)workingStream, (void*)dictionaryStream,{}
1795 dictCtx != NULL ? dictCtx->dictSize : 0){};
1796
1797 if (dictCtx != NULL((void*)0)) {
1798 /* If the current offset is zero, we will never look in the
1799 * external dictionary context, since there is no value a table
1800 * entry can take that indicate a miss. In that case, we need
1801 * to bump the offset to something non-zero.
1802 */
1803 if (workingStream->internal_donotuse.currentOffset == 0) {
1804 workingStream->internal_donotuse.currentOffset = 64 KB*(1 <<10);
1805 /* no longer a cleared table : LZ4_prepareTable() must check it */
1806 workingStream->internal_donotuse.tableType = (U32)byU32;
1807 }
1808
1809 /* Don't actually attach an empty dictionary.
1810 */
1811 if (dictCtx->dictSize == 0) {
1812 dictCtx = NULL((void*)0);
1813 }
1814 }
1815 workingStream->internal_donotuse.dictCtx = dictCtx;
1816}
1817
1818
1819static void LZ4_renormDictT(LZ4_stream_t_internal* LZ4_dict, int nextSize)
1820{
1821 assert(nextSize >= 0)((void)0);
1822 if (LZ4_dict->currentOffset + (unsigned)nextSize > 0x80000000) { /* potential ptrdiff_t overflow (32-bits mode) */
1823 /* rescale hash table */
1824 U32 const delta = LZ4_dict->currentOffset - 64 KB*(1 <<10);
1825 const BYTE* dictEnd = LZ4_dict->dictionary + LZ4_dict->dictSize;
1826 int i;
1827 DEBUGLOG(4, "LZ4_renormDictT"){};
1828 for (i=0; i<LZ4_HASH_SIZE_U32(1 << (14 -2)); i++) {
1829 if (LZ4_dict->hashTable[i] < delta) LZ4_dict->hashTable[i]=0;
1830 else LZ4_dict->hashTable[i] -= delta;
1831 }
1832 LZ4_dict->currentOffset = 64 KB*(1 <<10);
1833 if (LZ4_dict->dictSize > 64 KB*(1 <<10)) LZ4_dict->dictSize = 64 KB*(1 <<10);
1834 LZ4_dict->dictionary = dictEnd - LZ4_dict->dictSize;
1835 }
1836}
1837
1838
1839/* The history covers neither the full window (64 KB) nor all positions since the start of indexes :
1840 * the table may contain stale entries, from before the history, which must be rejected (dictSmall). */
1841static int LZ4_isDictSmall(const LZ4_stream_t_internal* streamPtr)
1842{
1843 return (streamPtr->dictSize < 64 KB*(1 <<10)) && (streamPtr->dictSize < streamPtr->currentOffset);
1844}
1845
1846/* from this input size (2 KB by default, at most 4 KB),
1847 * copying the tables of an attached dictionary is faster than looking into both tables.
1848 * The copy cost follows the table size. */
1849#define LZ4_DICTCTX_COPY_THRESHOLD(((1 << 14) / 8 < 4 *(1 <<10)) ? ((1 << 14
) / 8) : 4 *(1 <<10)) ((LZ4_HASHTABLESIZE(1 << 14) / 8 < 4 KB*(1 <<10)) ? (LZ4_HASHTABLESIZE(1 << 14) / 8) : 4 KB*(1 <<10))
1850
1851
1852int LZ4_compress_fast_continue (LZ4_stream_t* LZ4_stream,
1853 const char* source, char* dest,
1854 int inputSize, int maxOutputSize,
1855 int acceleration)
1856{
1857 const tableType_t tableType = byU32;
1858 LZ4_stream_t_internal* const streamPtr = &LZ4_stream->internal_donotuse;
1859 const char* dictEnd = streamPtr->dictSize ? (const char*)streamPtr->dictionary + streamPtr->dictSize : NULL((void*)0);
1860
1861 DEBUGLOG(5, "LZ4_compress_fast_continue (inputSize=%i, dictSize=%u)", inputSize, streamPtr->dictSize){};
1862
1863 /* new stream (no history) : clear the table beyond LZ4_CLEAR_TABLE_THRESHOLD */
1864 if ((streamPtr->dictSize == 0) && (streamPtr->dictCtx == NULL((void*)0)) && (inputSize >= LZ4_CLEAR_TABLE_THRESHOLD((1 << 14) / 16)))
1865 LZ4_prepareTable(streamPtr, inputSize, byU32);
1866
1867 LZ4_renormDictT(streamPtr, inputSize); /* fix index overflow */
1868 acceleration = LZ4_clampAcceleration(acceleration);
1869
1870 /* invalidate tiny dictionaries */
1871 if ( (streamPtr->dictSize < 4) /* tiny dictionary : not enough for a hash */
1872 && (dictEnd != source) /* prefix mode */
1873 && (inputSize > 0) /* tolerance : don't lose history, in case next invocation would use prefix mode */
1874 && (streamPtr->dictCtx == NULL((void*)0)) /* usingDictCtx */
1875 ) {
1876 DEBUGLOG(5, "LZ4_compress_fast_continue: dictSize(%u) at addr:%p is too small", streamPtr->dictSize, (void*)streamPtr->dictionary){};
1877 /* remove dictionary existence from history, to employ faster prefix mode */
1878 streamPtr->dictSize = 0;
1879 streamPtr->dictionary = (const BYTE*)source;
1880 dictEnd = source;
1881 }
1882
1883 /* Check overlapping input/dictionary space */
1884 { const char* const sourceEnd = source + inputSize;
1885 if ((sourceEnd > (const char*)streamPtr->dictionary) && (source < dictEnd)) {
1886 /* only the part of the dictionary beyond input remains */
1887 streamPtr->dictSize = (sourceEnd < dictEnd) ? (U32)(dictEnd - sourceEnd) : 0;
1888 if (streamPtr->dictSize > 64 KB*(1 <<10)) streamPtr->dictSize = 64 KB*(1 <<10);
1889 if (streamPtr->dictSize < 4) streamPtr->dictSize = 0;
1890 streamPtr->dictionary = (const BYTE*)dictEnd - streamPtr->dictSize;
1891 }
1892 }
1893
1894 /* prefix mode : source data follows dictionary */
1895 if (dictEnd == source) {
1896 if (LZ4_isDictSmall(streamPtr))
1897 return LZ4_compress_generic(streamPtr, source, dest, inputSize, NULL((void*)0), maxOutputSize, limitedOutput, tableType, withPrefix64k, dictSmall, acceleration);
1898 else
1899 return LZ4_compress_generic(streamPtr, source, dest, inputSize, NULL((void*)0), maxOutputSize, limitedOutput, tableType, withPrefix64k, noDictIssue, acceleration);
1900 }
1901
1902 /* external dictionary mode */
1903 { int result;
1904 if (streamPtr->dictCtx) {
1905 /* We depend here on the fact that dictCtx'es (produced by
1906 * LZ4_loadDict) guarantee that their tables contain no references
1907 * to offsets between dictCtx->currentOffset - 64 KB and
1908 * dictCtx->currentOffset - dictCtx->dictSize. This makes it safe
1909 * to use noDictIssue even when the dict isn't a full 64 KB.
1910 */
1911 if (inputSize >= LZ4_DICTCTX_COPY_THRESHOLD(((1 << 14) / 8 < 4 *(1 <<10)) ? ((1 << 14
) / 8) : 4 *(1 <<10))) {
1912 /* For compressing large blobs, it is faster to pay the setup
1913 * cost to copy the dictionary's tables into the active context,
1914 * so that the compression loop is only looking into one table.
1915 */
1916 LZ4_memcpy(streamPtr, streamPtr->dictCtx, sizeof(*streamPtr))__builtin_memcpy(streamPtr, streamPtr->dictCtx, sizeof(*streamPtr
));
1917 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, NULL((void*)0), maxOutputSize, limitedOutput, tableType, usingExtDict, noDictIssue, acceleration);
1918 } else {
1919 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, NULL((void*)0), maxOutputSize, limitedOutput, tableType, usingDictCtx, noDictIssue, acceleration);
1920 }
1921 } else { /* external dictionary in the current context */
1922 if (LZ4_isDictSmall(streamPtr)) {
1923 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, NULL((void*)0), maxOutputSize, limitedOutput, tableType, usingExtDict, dictSmall, acceleration);
1924 } else {
1925 result = LZ4_compress_generic(streamPtr, source, dest, inputSize, NULL((void*)0), maxOutputSize, limitedOutput, tableType, usingExtDict, noDictIssue, acceleration);
1926 }
1927 }
1928 streamPtr->dictionary = (const BYTE*)source;
1929 streamPtr->dictSize = (U32)inputSize;
1930 return result;
1931 }
1932}
1933
1934
1935/* Hidden debug function, to force-test external dictionary mode */
1936int LZ4_compress_forceExtDict (LZ4_stream_t* LZ4_dict, const char* source, char* dest, int srcSize)
1937{
1938 LZ4_stream_t_internal* const streamPtr = &LZ4_dict->internal_donotuse;
1939 int result;
1940
1941 LZ4_renormDictT(streamPtr, srcSize);
1942
1943 if (LZ4_isDictSmall(streamPtr)) {
1944 result = LZ4_compress_generic(streamPtr, source, dest, srcSize, NULL((void*)0), 0, notLimited, byU32, usingExtDict, dictSmall, 1);
1945 } else {
1946 result = LZ4_compress_generic(streamPtr, source, dest, srcSize, NULL((void*)0), 0, notLimited, byU32, usingExtDict, noDictIssue, 1);
1947 }
1948
1949 streamPtr->dictionary = (const BYTE*)source;
1950 streamPtr->dictSize = (U32)srcSize;
1951
1952 return result;
1953}
1954
1955
1956/*! LZ4_saveDict() :
1957 * If previously compressed data block is not guaranteed to remain available at its memory location,
1958 * save it into a safer place (char* safeBuffer).
1959 * Note : no need to call LZ4_loadDict() afterwards, dictionary is immediately usable,
1960 * one can therefore call LZ4_compress_fast_continue() right after.
1961 * @return : saved dictionary size in bytes (necessarily <= dictSize), or 0 if error.
1962 */
1963int LZ4_saveDict (LZ4_stream_t* LZ4_dict, char* safeBuffer, int dictSize)
1964{
1965 LZ4_stream_t_internal* const dict = &LZ4_dict->internal_donotuse;
1966
1967 DEBUGLOG(5, "LZ4_saveDict : dictSize=%i, safeBuffer=%p", dictSize, (void*)safeBuffer){};
1968
1969 if (dictSize < 0) dictSize = 0; /* invalid : save nothing, like LZ4_saveDictHC() */
1970 if ((U32)dictSize > 64 KB*(1 <<10)) { dictSize = 64 KB*(1 <<10); } /* useless to define a dictionary > 64 KB */
1971 if ((U32)dictSize > dict->dictSize) { dictSize = (int)dict->dictSize; }
1972
1973 if (safeBuffer == NULL((void*)0)) assert(dictSize == 0)((void)0);
1974 if (dictSize > 0) {
1975 const BYTE* const previousDictEnd = dict->dictionary + dict->dictSize;
1976 assert(dict->dictionary)((void)0);
1977 LZ4_memmove__builtin_memmove(safeBuffer, previousDictEnd - dictSize, (size_t)dictSize);
1978 }
1979
1980 dict->dictionary = (const BYTE*)safeBuffer;
1981 dict->dictSize = (U32)dictSize;
1982
1983 return dictSize;
1984}
1985
1986
1987
1988/*-*******************************
1989 * Decompression functions
1990 ********************************/
1991
1992typedef enum { decode_full_block = 0, partial_decode = 1 } earlyEnd_directive;
1993
1994#undef MIN
1995#define MIN(a,b)( (a) < (b) ? (a) : (b) ) ( (a) < (b) ? (a) : (b) )
1996
1997
1998/* variant for decompress_unsafe()
1999 * does not know end of input
2000 * presumes input is well formed
2001 * note : will consume at least one byte */
2002static size_t read_long_length_no_check(const BYTE** pp)
2003{
2004 size_t b, l = 0;
2005 do { b = **pp; (*pp)++; l += b; } while (b==255);
2006 DEBUGLOG(6, "read_long_length_no_check: +length=%zu using %zu input bytes", l, l/255 + 1){}
2007 return l;
2008}
2009
2010/* core decoder variant for LZ4_decompress_fast*()
2011 * for legacy support only : these entry points are deprecated.
2012 * - Presumes input is correctly formed (no defense vs malformed inputs)
2013 * - Does not know input size (presume input buffer is "large enough")
2014 * - Decompress a full block (only)
2015 * @return : nb of bytes read from input.
2016 * Note : this variant is not optimized for speed, just for maintenance.
2017 * the goal is to remove support of decompress_fast*() variants by v2.0
2018**/
2019LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) int
2020LZ4_decompress_unsafe_generic(
2021 const BYTE* const istart,
2022 BYTE* const ostart,
2023 int decompressedSize,
2024
2025 size_t prefixSize,
2026 const BYTE* const dictStart, /* only if dict==usingExtDict */
2027 const size_t dictSize /* note: =0 if dictStart==NULL */
2028 )
2029{
2030 const BYTE* ip = istart;
2031 BYTE* op = (BYTE*)ostart;
2032 BYTE* oend;
2033 const BYTE* const prefixStart = ostart - prefixSize;
2034
2035 DEBUGLOG(5, "LZ4_decompress_unsafe_generic"){};
2036 if (dictStart == NULL((void*)0)) assert(dictSize == 0)((void)0);
2037 if (decompressedSize < 0) return -1;
2038 oend = ostart + decompressedSize;
2039
2040 while (1) {
2041 /* start new sequence */
2042 unsigned token = *ip++;
2043
2044 /* literals */
2045 { size_t ll = token >> ML_BITS4;
2046 if (ll==15) {
2047 /* long literal length */
2048 ll += read_long_length_no_check(&ip);
2049 }
2050 if ((size_t)(oend-op) < ll) return -1; /* output buffer overflow */
2051 LZ4_memmove__builtin_memmove(op, ip, ll); /* support in-place decompression */
2052 op += ll;
2053 ip += ll;
2054 if ((size_t)(oend-op) < MFLIMIT12) {
2055 if (op==oend) break; /* end of block */
2056 DEBUGLOG(5, "invalid: literals end at distance %zi from end of block", oend-op){};
2057 /* incorrect end of block :
2058 * last match must start at least MFLIMIT==12 bytes before end of output block */
2059 return -1;
2060 } }
2061
2062 /* match */
2063 { size_t ml = token & 15;
2064 size_t const offset = LZ4_readLE16(ip);
2065 ip+=2;
2066
2067 if (ml==15) {
2068 /* long literal length */
2069 ml += read_long_length_no_check(&ip);
2070 }
2071 ml += MINMATCH4;
2072
2073 if ((size_t)(oend-op) < ml) return -1; /* output buffer overflow */
2074
2075 { const BYTE* match = op - offset;
2076
2077 /* out of range */
2078 if (offset > (size_t)(op - prefixStart) + dictSize) {
2079 DEBUGLOG(6, "offset out of range"){};
2080 return -1;
2081 }
2082
2083 /* check special case : extDict */
2084 if (offset > (size_t)(op - prefixStart)) {
2085 /* extDict scenario */
2086 const BYTE* const dictEnd = dictStart + dictSize;
2087 const BYTE* extMatch = dictEnd - (offset - (size_t)(op-prefixStart));
2088 size_t const extml = (size_t)(dictEnd - extMatch);
2089 if (extml > ml) {
2090 /* match entirely within extDict */
2091 LZ4_memmove__builtin_memmove(op, extMatch, ml);
2092 op += ml;
2093 ml = 0;
2094 } else {
2095 /* match split between extDict & prefix */
2096 LZ4_memmove__builtin_memmove(op, extMatch, extml);
2097 op += extml;
2098 ml -= extml;
2099 }
2100 match = prefixStart;
2101 }
2102
2103 /* match copy - slow variant, supporting overlap copy */
2104 { size_t u;
2105 for (u=0; u<ml; u++) {
2106 op[u] = match[u];
2107 } } }
2108 op += ml;
2109 if ((size_t)(oend-op) < LASTLITERALS5) {
2110 DEBUGLOG(5, "invalid: match ends at distance %zi from end of block", oend-op){};
2111 /* incorrect end of block :
2112 * last match must stop at least LASTLITERALS==5 bytes before end of output block */
2113 return -1;
2114 }
2115 } /* match */
2116 } /* main loop */
2117 return (int)(ip - istart);
2118}
2119
2120
2121/* Read the variable-length literal or match length.
2122 *
2123 * @ipPtr : pointer to input pointer, will be advanced
2124 * @ilimit : read is forbidden beyond this position (must be within input buffer)
2125**/
2126typedef size_t Rvl_t;
2127static const Rvl_t rvl_error = (Rvl_t)(-1);
2128LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) Rvl_t
2129read_variable_length(const BYTE** ipPtr, const BYTE* ilimit)
2130{
2131 Rvl_t s, length = 0;
2132 assert(ipPtr != NULL)((void)0);
2133 assert(*ipPtr != NULL)((void)0);
2134 assert(ilimit != NULL)((void)0);
2135 if (unlikely((*ipPtr) >= ilimit)(__builtin_expect ((((*ipPtr) >= ilimit) != 0),(0)) )) { /* read limit reached */
2136 return rvl_error;
2137 }
2138 s = **ipPtr;
2139 (*ipPtr)++;
2140 length += s;
2141 if (likely(s != 255)(__builtin_expect (((s != 255) != 0),(1)) )) return length;
2142 do {
2143 if (unlikely((*ipPtr) >= ilimit)(__builtin_expect ((((*ipPtr) >= ilimit) != 0),(0)) )) { /* read limit reached */
2144 return rvl_error;
2145 }
2146 s = **ipPtr;
2147 (*ipPtr)++;
2148 length += s;
2149 /* accumulator overflow detection (32-bit mode only) */
2150 if ((sizeof(length) < 8) && unlikely(length > ((Rvl_t)(-1)/2))(__builtin_expect (((length > ((Rvl_t)(-1)/2)) != 0),(0)) ) ) {
2151 return rvl_error;
2152 }
2153 } while (s == 255);
2154
2155 return length;
2156}
2157
2158/* LZ4_copyMatchExact() :
2159 * copy a match of length bytes from match to op (match < op, overlap allowed),
2160 * writing nothing beyond op+length. Invalid offset 0 (match == op) produces 0 bytes.
2161 * Not inlined : rarely used, its memcpy() calls would burden the decoder's hot loops.
2162 * @return : output position after the match */
2163LZ4_FORCE_NOINLINEstatic __attribute__((noinline)) BYTE*
2164LZ4_copyMatchExact(BYTE* op, const BYTE* match, size_t length)
2165{
2166 if (unlikely(match == op)(__builtin_expect (((match == op) != 0),(0)) )) { /* invalid offset 0 : clear the match segment, see doc/lz4_Block_format.md */
2167 MEM_INIT(op, 0, length)memset(((op)),((0)),((length)));
2168 return op + length;
2169 }
2170 /* bytes from match to op repeat with period (op-match) :
2171 * copy all of them, so the distance doubles at each round.
2172 * Beyond 2 KB, keep the distance : larger copies of just written data are slower */
2173 while (length > (size_t)(op - match)) {
2174 size_t const available = (size_t)(op - match);
2175 LZ4_memcpy(op, match, available)__builtin_memcpy(op, match, available);
2176 op += available;
2177 length -= available;
2178 if (available >= 2048) match += available;
2179 }
2180 LZ4_memcpy(op, match, length)__builtin_memcpy(op, match, length);
2181 return op + length;
2182}
2183
2184/* LZ4_copyExtDictMatch() :
2185 * copy a match starting within the external dictionary (match < lowPrefix),
2186 * possibly stretching into the current block.
2187 * @return : output position after the match */
2188LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) BYTE*
2189LZ4_copyExtDictMatch(BYTE* op, const BYTE* match, size_t length,
2190 const BYTE* lowPrefix, const BYTE* dictEnd)
2191{
2192 if (length <= (size_t)(lowPrefix-match)) {
30
←
Assuming the condition is false
→
31
←
Taking false branch
→
2193 /* match fits entirely within external dictionary : just copy */
2194 LZ4_memmove__builtin_memmove(op, dictEnd - (lowPrefix-match), length);
2195 return op + length;
2196 } else {
2197 /* match stretches into both external dictionary and current block */
2198 size_t const copySize = (size_t)(lowPrefix - match);
2199 LZ4_memcpy(op, dictEnd - copySize, copySize)__builtin_memcpy(op, dictEnd - copySize, copySize);
32
←
Subtraction of a null pointer (from variable 'dictEnd') and a probably nonzero integer value (from variable 'copySize') may result in undefined behavior
2200 return LZ4_copyMatchExact(op + copySize, lowPrefix, length - copySize);
2201 }
2202}
2203
2204/*! LZ4_decompress_generic() :
2205 * This generic decompression function covers all use cases.
2206 * It shall be instantiated several times, using different sets of directives.
2207 * Note that it is important for performance that this function really get inlined,
2208 * in order to remove useless branches during compilation optimization.
2209 */
2210LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) int
2211LZ4_decompress_generic(
2212 const char* const src,
2213 char* const dst,
2214 int srcSize,
2215 int outputSize, /* dstCapacity, or MIN(targetOutputSize, dstCapacity) when partialDecoding */
2216
2217 earlyEnd_directive partialDecoding, /* full, partial */
2218 dict_directive dict, /* noDict, withPrefix64k, usingExtDict */
2219 const BYTE* const lowPrefix, /* always <= dst, == dst when no prefix */
2220 const BYTE* const dictStart, /* only if dict==usingExtDict */
2221 const size_t dictSize /* note : = 0 if noDict */
2222 )
2223{
2224 if ((src == NULL((void*)0)) || (outputSize < 0)) { return -1; }
1
Assuming 'src' is not equal to NULL
→
2
←
Assuming 'outputSize' is >= 0
→
3
←
Taking false branch
→
2225
2226 { const BYTE* ip = (const BYTE*) src;
2227 const BYTE* const iend = ip + srcSize;
2228
2229 BYTE* op = (BYTE*) dst;
2230 BYTE* const oend = op + outputSize;
2231
2232 const BYTE* const dictEnd = (dictStart == NULL((void*)0)) ? NULL((void*)0) : dictStart + dictSize;
4
←
Assuming 'dictStart' is equal to NULL
→
5
←
'?' condition is true
→
6
←
'dictEnd' initialized to a null pointer value
→
2233
2234 /* withPrefix64k : offset <= 65535 can't reach beyond the 64 KB prefix */
2235 const int checkOffset = (dict != withPrefix64k) && (dictSize < (int)(64 KB*(1 <<10)));
7
←
Assuming 'dict' is not equal to withPrefix64k
→
8
←
Assuming the condition is false
→
2236
2237
2238 /* Set up the "end" pointers for the shortcut. */
2239 const BYTE* const shortiend = iend - 14 /*maxLL*/ - 2 /*offset*/;
2240 const BYTE* const shortoend = oend - 14 /*maxLL*/ - 18 /*maxML*/;
2241
2242 /* shared by both loops : the fast loop can hand over a decoded match (safe_match_copy) */
2243 const BYTE* match;
2244 size_t offset;
2245 size_t ml; /* match length */
2246
2247
2248 DEBUGLOG(5, "LZ4_decompress_generic (srcSize:%i, dstSize:%i)", srcSize, outputSize){};
2249
2250 /* Special cases */
2251 assert(lowPrefix <= op)((void)0);
2252 if (unlikely(outputSize==0)(__builtin_expect (((outputSize==0) != 0),(0)) )) {
9
←
Assuming 'outputSize' is not equal to 0
→
10
←
Taking false branch
→
2253 /* Empty output buffer */
2254 if (partialDecoding) return 0;
2255 if ((srcSize==1) && (*ip==0)) return 0; /* empty block */
2256 return (srcSize > 1) ? -2 : -1; /* -2 : output buffer too small */
2257 }
2258 if (unlikely(srcSize<=0)(__builtin_expect (((srcSize<=0) != 0),(0)) )) { return -1; }
11
←
Assuming 'srcSize' is > 0
→
12
←
Taking false branch
→
2259
2260 /* LZ4_FAST_DEC_LOOP:
2261 * designed for modern OoO performance cpus,
2262 * where copying reliably 32-bytes is preferable to an unpredictable branch.
2263 * note : fast loop may show a regression for some client arm chips. */
2264#if LZ4_FAST_DEC_LOOP1
2265 if ((oend - op) < FASTLOOP_SAFE_DISTANCE64) {
13
←
Assuming the condition is false
→
2266 DEBUGLOG(6, "move to safe decode loop"){};
2267 goto safe_decode;
2268 }
2269 /* Ring buffer restarting at its beginning : the oldest referenced history (max distance behind op)
2270 * lies in the external dictionary, ahead of op, always at the same distance.
2271 * Rings sized with the former LZ4_DECODER_RING_BUFFER_SIZE() (margin 14, up to v1.10.0)
2272 * still work, but leave as little as 16 bytes :
2273 * the fast loop's wide copies could overwrite it, the safe loop's can't. */
2274 if ( (dict==usingExtDict)
14
←
Assuming 'dict' is equal to usingExtDict
→
16
←
Taking false branch
→
2275 && ((uptrval)dictEnd - (uptrval)lowPrefix - LZ4_DISTANCE_ABSOLUTE_MAX65535 < FASTLOOP_SAFE_DISTANCE64) ) {
15
←
Assuming the condition is false
→
2276 DEBUGLOG(6, "history just ahead : move to safe decode loop"){};
2277 goto safe_decode;
2278 }
2279
2280 /* Fast loop : decode sequences as long as output < oend-FASTLOOP_SAFE_DISTANCE,
2281 * and input is not too close to iend.
2282 * It hands over to the safe loop either at a sequence start (break),
2283 * or once a match is fully decoded (goto safe_match_copy). */
2284 DEBUGLOG(6, "using fast decode loop"){};
2285 while (1) {
17
←
Loop condition is true. Entering loop body
→
2286 unsigned token;
2287 size_t ll; /* literal length */
2288 BYTE* cpy;
2289 /* Main fastloop assertion: We can always wildcopy FASTLOOP_SAFE_DISTANCE */
2290 assert(oend - op >= FASTLOOP_SAFE_DISTANCE)((void)0);
2291 assert(ip < iend)((void)0);
2292 token = *ip++;
2293 ll = token >> ML_BITS4;
2294 DEBUGLOG(7, "blockPos%6u: litLength token = %u", (unsigned)(op-(BYTE*)dst), (unsigned)ll){};
2295
2296 /* too close to input end : the safe loop restarts this sequence */
2297 if (ip > iend-(16 + 1/*max lit + offset + nextToken*/)) { ip--; break; }
18
←
Assuming the condition is false
→
19
←
Taking false branch
→
2298
2299 /* decode literal length */
2300 if (ll == RUN_MASK((1U<<(8-4))-1)) {
20
←
Assuming the condition is false
→
21
←
Taking false branch
→
2301 /* literal length >= RUN_MASK means >= RUN_MASK literal bytes follow the extension bytes,
2302 * so extension bytes cannot reach the last RUN_MASK bytes of input */
2303 const BYTE* const tokenPos = ip-1;
2304 size_t const addl = read_variable_length(&ip, iend - RUN_MASK((1U<<(8-4))-1));
2305 if (addl == rvl_error) {
2306 DEBUGLOG(6, "error reading long literal length"){};
2307 goto _output_error;
2308 }
2309 ll += addl;
2310 if (unlikely((uptrval)(op)+ll<(uptrval)(op))(__builtin_expect ((((uptrval)(op)+ll<(uptrval)(op)) != 0)
,(0)) )) { goto _output_error; } /* overflow detection */
2311 if (unlikely((uptrval)(ip)+ll<(uptrval)(ip))(__builtin_expect ((((uptrval)(ip)+ll<(uptrval)(ip)) != 0)
,(0)) )) { goto _output_error; } /* overflow detection */
2312
2313 /* copy literals, unless too close to the end for a wild copy :
2314 * nothing is written yet, so the safe loop can restart this sequence */
2315 cpy = op+ll;
2316 LZ4_STATIC_ASSERT(MFLIMIT >= WILDCOPYLENGTH){ enum { LZ4_static_assert = 1/(int)(!!(12 >= 8)) }; };
2317 #if LZ4_WILDCOPY641
2318 if ((cpy>oend-64) || (ip+ll>iend-64)) { ip = tokenPos; break; }
2319 LZ4_wildCopy64(op, ip, cpy);
2320 #else
2321 if ((cpy>oend-32) || (ip+ll>iend-32)) { ip = tokenPos; break; }
2322 LZ4_wildCopy32(op, ip, cpy);
2323 #endif
2324 ip += ll; op = cpy;
2325 } else {
2326 DEBUGLOG(7, "copy %u bytes in a 16-bytes stripe", (unsigned)ll){};
2327 /* Literals can only be <= 14, but hope compilers optimize better when copy by a register size */
2328 LZ4_memcpy(op, ip, 16)__builtin_memcpy(op, ip, 16);
2329 ip += ll; op += ll;
2330 }
2331
2332 /* get offset */
2333 offset = LZ4_readLE16(ip); ip+=2;
2334 DEBUGLOG(6, "blockPos%6u: offset = %u", (unsigned)(op-(BYTE*)dst), (unsigned)offset){};
2335 match = op - offset;
2336 assert(match <= op)((void)0); /* overflow check */
2337
2338 /* get matchlength */
2339 ml = token & ML_MASK((1U<<4)-1);
2340 DEBUGLOG(7, " match length token = %u (len==%u)", (unsigned)ml, (unsigned)ml+MINMATCH){};
2341
2342 if (ml == ML_MASK((1U<<4)-1)) {
22
←
Assuming the condition is false
→
23
←
Taking false branch
→
2343 /* after match length extension bytes, at least 1 token + LASTLITERALS literals must remain */
2344 size_t const addl = read_variable_length(&ip, iend - (1 + LASTLITERALS5));
2345 if (addl == rvl_error) {
2346 DEBUGLOG(5, "error reading long match length"){};
2347 goto _output_error;
2348 }
2349 ml += addl;
2350 DEBUGLOG(7, " long match length == %u", (unsigned)ml + MINMATCH){};
2351 if (unlikely((uptrval)(op)+ml<(uptrval)op)(__builtin_expect ((((uptrval)(op)+ml<(uptrval)op) != 0),(
0)) )) { goto _output_error; } /* overflow detection */
2352 }
2353 ml += MINMATCH4;
2354
2355 if (op + ml >= oend - FASTLOOP_SAFE_DISTANCE64) {
24
←
Assuming the condition is false
→
2356 DEBUGLOG(7, "moving to safe_match_copy (ml==%u)", (unsigned)ml){};
2357 goto safe_match_copy;
2358 }
2359
2360 /* match length from token only (<= 18), no overlap, within prefix : copy 18 bytes */
2361 if ( ((token & ML_MASK((1U<<4)-1)) != ML_MASK((1U<<4)-1)) && (offset >= 8)
25
←
Assuming 'offset' is < 8
→
2362 && ((dict == withPrefix64k) || (match >= lowPrefix)) ) {
2363 assert(match >= lowPrefix)((void)0);
2364 assert(match <= op)((void)0);
2365 assert(op + 18 <= oend)((void)0);
2366 LZ4_memcpy(op, match, 8)__builtin_memcpy(op, match, 8);
2367 LZ4_memcpy(op+8, match+8, 8)__builtin_memcpy(op+8, match+8, 8);
2368 LZ4_memcpy(op+16, match+16, 2)__builtin_memcpy(op+16, match+16, 2);
2369 op += ml;
2370 continue;
2371 }
2372
2373 /* match ends far from oend : no end-of-block condition to check */
2374 assert(op + ml < oend - FASTLOOP_SAFE_DISTANCE)((void)0);
2375
2376 if ( checkOffset
25.1
'checkOffset' is 0
 && (unlikely(match + dictSize < lowPrefix)(__builtin_expect (((match + dictSize < lowPrefix) != 0),(
0)) )) ) {
2377 DEBUGLOG(5, "Error : pos=%zi, offset=%zi => outside buffers", op-lowPrefix, op-match){};
2378 goto _offset_error;
2379 }
2380 /* match starting within external dictionary */
2381 if ((dict
25.2
'dict' is equal to usingExtDict
==usingExtDict) && (match < lowPrefix)) {
26
←
Assuming 'match' is < 'lowPrefix'
→
27
←
Taking true branch
→
2382 assert(dictEnd != NULL)((void)0);
2383 op = LZ4_copyExtDictMatch(op, match, ml, lowPrefix, dictEnd);
28
←
Passing null pointer value via 5th parameter 'dictEnd'
→
29
←
Calling 'LZ4_copyExtDictMatch'
→
2384 continue;
2385 }
2386
2387 /* copy match within block */
2388 cpy = op + ml;
2389
2390 assert((op <= oend) && (oend-op >= 64))((void)0);
2391 if (unlikely(offset<16)(__builtin_expect (((offset<16) != 0),(0)) )) {
2392 LZ4_memcpy_using_offset(op, match, cpy, offset);
2393 #if LZ4_WILDCOPY641
2394 } else if (offset >= 64) {
2395 LZ4_wildCopy64(op, match, cpy);
2396 #endif
2397 } else {
2398 LZ4_wildCopy32(op, match, cpy);
2399 }
2400
2401 op = cpy; /* wildcopy correction */
2402 }
2403 safe_decode:
2404#endif
2405
2406 /* Safe loop : decode remaining sequences, without writing beyond oend nor reading beyond iend.
2407 * With LZ4_FAST_DEC_LOOP, that's the end of the block (or a block too small for the fast loop),
2408 * entered at a sequence start, or at safe_match_copy with a decoded match.
2409 * Without it, that's the whole block. */
2410 DEBUGLOG(6, "using safe decode loop"){};
2411 while (1) {
2412 unsigned token;
2413 size_t ll; /* literal length */
2414 BYTE* cpy;
2415 assert(ip < iend)((void)0);
2416 token = *ip++;
2417 ll = token >> ML_BITS4;
2418 DEBUGLOG(7, "blockPos%6u: litLength token = %u", (unsigned)(op-(BYTE*)dst), (unsigned)ll){};
2419
2420 /* A two-stage shortcut for the most common case:
2421 * 1) If the literal length is 0..14, and there is enough space,
2422 * enter the shortcut and copy 16 bytes on behalf of the literals.
2423 * 2) Further if the match length is 4..18, copy 18 bytes in a similar
2424 * manner; but we ensure that there's enough space in the output for
2425 * those 18 bytes earlier, upon entering the shortcut (in other words,
2426 * there is a combined check for both stages).
2427 */
2428 if ( (ll != RUN_MASK((1U<<(8-4))-1))
2429 /* strictly "less than" on input, to re-enter the loop with at least one byte */
2430 && likely((ip < shortiend) & (op <= shortoend))(__builtin_expect ((((ip < shortiend) & (op <= shortoend
)) != 0),(1)) ) ) {
2431 /* Copy the literals */
2432 LZ4_memcpy(op, ip, 16)__builtin_memcpy(op, ip, 16);
2433 op += ll; ip += ll;
2434
2435 /* The second stage: prepare for match copying, decode full info.
2436 * If it doesn't work out, the info won't be wasted. */
2437 offset = LZ4_readLE16(ip); ip += 2;
2438 match = op - offset;
2439 assert(match <= op)((void)0); /* check overflow */
2440 ml = token & ML_MASK((1U<<4)-1);
2441 DEBUGLOG(7, "blockPos%6u: matchLength token = %u (len=%u)", (unsigned)(op-(BYTE*)dst), (unsigned)ml, (unsigned)ml + 4){};
2442
2443 /* Do not deal with overlapping matches. */
2444 if ( (ml != ML_MASK((1U<<4)-1))
2445 && (offset >= 8)
2446 && (dict==withPrefix64k || match >= lowPrefix) ) {
2447 /* Copy the match. */
2448 LZ4_memcpy(op + 0, match + 0, 8)__builtin_memcpy(op + 0, match + 0, 8);
2449 LZ4_memcpy(op + 8, match + 8, 8)__builtin_memcpy(op + 8, match + 8, 8);
2450 LZ4_memcpy(op +16, match +16, 2)__builtin_memcpy(op +16, match +16, 2);
2451 op += ml + MINMATCH4;
2452 /* Both stages worked, load the next token. */
2453 continue;
2454 }
2455 /* The second stage didn't work out, but the info is ready for the match copy below. */
2456 } else {
2457 /* decode literal length */
2458 if (ll == RUN_MASK((1U<<(8-4))-1)) {
2459 /* literal length >= RUN_MASK means >= RUN_MASK literal bytes follow the extension bytes,
2460 * so extension bytes cannot reach the last RUN_MASK bytes of input */
2461 size_t const addl = read_variable_length(&ip, iend-RUN_MASK((1U<<(8-4))-1));
2462 if (addl == rvl_error) { goto _output_error; }
2463 ll += addl;
2464 if (unlikely((uptrval)(op)+ll<(uptrval)(op))(__builtin_expect ((((uptrval)(op)+ll<(uptrval)(op)) != 0)
,(0)) )) { goto _output_error; } /* overflow detection */
2465 if (unlikely((uptrval)(ip)+ll<(uptrval)(ip))(__builtin_expect ((((uptrval)(ip)+ll<(uptrval)(ip)) != 0)
,(0)) )) { goto _output_error; } /* overflow detection */
2466 }
2467
2468 /* copy literals */
2469 cpy = op+ll;
2470 LZ4_STATIC_ASSERT(MFLIMIT >= WILDCOPYLENGTH){ enum { LZ4_static_assert = 1/(int)(!!(12 >= 8)) }; };
2471 if ((cpy>oend-MFLIMIT12) || (ip+ll>iend-(2+1+LASTLITERALS5))) {
2472 /* close to input or output end : these must be the last literals of the block,
2473 * except with partialDecoding, which can also stop within them */
2474 if (partialDecoding) {
2475 /* stop at input end, or when output is full */
2476 ll = MIN(ll, (size_t)(iend-ip))( (ll) < ((size_t)(iend-ip)) ? (ll) : ((size_t)(iend-ip)) );
2477 ll = MIN(ll, (size_t)(oend-op))( (ll) < ((size_t)(oend-op)) ? (ll) : ((size_t)(oend-op)) );
2478 } else if ((ip+ll != iend) || (cpy > oend)) {
2479 /* last literals must end exactly at input end, within output */
2480 DEBUGLOG(5, "invalid last literals : they end at iend%+zi and oend%+zi", (ip+ll)-iend, cpy-oend){};
2481 if ((ip+ll <= iend) && (cpy > oend-MFLIMIT12)) goto _dst_too_small; /* output full, input left */
2482 goto _output_error;
2483 }
2484 LZ4_memmove__builtin_memmove(op, ip, ll); /* supports overlapping memory regions, for in-place decompression scenarios */
2485 ip += ll;
2486 op += ll;
2487 /* end of block, unless partialDecoding can go on : output not full, input left for a match */
2488 if (!partialDecoding || (op == oend) || (ip >= (iend-2))) {
2489 break;
2490 }
2491 } else {
2492 LZ4_wildCopy8(op, ip, cpy); /* can overwrite up to 8 bytes beyond cpy */
2493 ip += ll; op = cpy;
2494 }
2495
2496 /* get offset */
2497 offset = LZ4_readLE16(ip); ip+=2;
2498 match = op - offset;
2499
2500 /* get matchlength */
2501 ml = token & ML_MASK((1U<<4)-1);
2502 DEBUGLOG(7, "blockPos%6u: matchLength token = %u", (unsigned)(op-(BYTE*)dst), (unsigned)ml){};
2503 }
2504
2505 /* literals copied, offset decoded, ml == match length token */
2506 if (ml == ML_MASK((1U<<4)-1)) {
2507 /* after match length extension bytes, at least 1 token + LASTLITERALS literals must remain */
2508 size_t const addl = read_variable_length(&ip, iend - (1 + LASTLITERALS5));
2509 if (addl == rvl_error) { goto _output_error; }
2510 ml += addl;
2511 if (unlikely((uptrval)(op)+ml<(uptrval)op)(__builtin_expect ((((uptrval)(op)+ml<(uptrval)op) != 0),(
0)) )) goto _output_error; /* overflow detection */
2512 }
2513 ml += MINMATCH4;
2514
2515#if LZ4_FAST_DEC_LOOP1
2516 safe_match_copy:
2517#endif
2518 /* literals copied, match fully decoded (ml includes MINMATCH), offset not validated yet */
2519 if ((checkOffset) && (unlikely(match + dictSize < lowPrefix)(__builtin_expect (((match + dictSize < lowPrefix) != 0),(
0)) ))) goto _offset_error; /* Error : offset outside buffers */
2520
2521 /* end of block : the last LASTLITERALS bytes must be literals */
2522 assert(op <= oend)((void)0);
2523 if (unlikely(op+ml > oend-LASTLITERALS)(__builtin_expect (((op+ml > oend-5) != 0),(0)) )) {
2524 if (partialDecoding) ml = MIN(ml, (size_t)(oend-op))( (ml) < ((size_t)(oend-op)) ? (ml) : ((size_t)(oend-op)) ); /* partialDecoding : may end anywhere */
2525 else goto _dst_too_small;
2526 }
2527
2528 /* match starting within external dictionary */
2529 if ((dict==usingExtDict) && (match < lowPrefix)) {
2530 assert(dictEnd != NULL)((void)0);
2531 op = LZ4_copyExtDictMatch(op, match, ml, lowPrefix, dictEnd);
2532 continue;
2533 }
2534 assert(match >= lowPrefix)((void)0);
2535
2536 /* close to block end : no wild copy */
2537 if (unlikely(op+ml > oend-MATCH_SAFEGUARD_DISTANCE)(__builtin_expect (((op+ml > oend-((2*8) - 4)) != 0),(0)) )) {
2538 op = LZ4_copyMatchExact(op, match, ml);
2539 if (op == oend) { break; } /* partialDecoding : output buffer full */
2540 continue;
2541 }
2542
2543 /* copy match within block */
2544 cpy = op + ml;
2545 LZ4_memcpy_using_offset_base(op, match, cpy, offset);
2546 op = cpy; /* wildcopy correction */
2547 }
2548
2549 /* end of decoding */
2550 DEBUGLOG(5, "decoded %i bytes", (int) (((char*)op)-dst)){};
2551 return (int) (((char*)op)-dst); /* Nb of output bytes decoded */
2552
2553 /* errors : see LZ4_decompress_safe() in lz4.h */
2554 _output_error:
2555 return -1;
2556 _dst_too_small:
2557 return -2;
2558 _offset_error:
2559 return -3;
2560 }
2561}
2562
2563
2564/*===== Instantiate the API decoding functions. =====*/
2565
2566LZ4_FORCE_O2
2567int LZ4_decompress_safe(const char* source, char* dest, int compressedSize, int maxDecompressedSize)
2568{
2569 return LZ4_decompress_generic(source, dest, compressedSize, maxDecompressedSize,
2570 decode_full_block, noDict,
2571 (BYTE*)dest, NULL((void*)0), 0);
2572}
2573
2574LZ4_FORCE_O2
2575int LZ4_decompress_safe_partial(const char* src, char* dst, int compressedSize, int targetOutputSize, int dstCapacity)
2576{
2577 dstCapacity = MIN(targetOutputSize, dstCapacity)( (targetOutputSize) < (dstCapacity) ? (targetOutputSize) :
(dstCapacity) );
2578 return LZ4_decompress_generic(src, dst, compressedSize, dstCapacity,
2579 partial_decode,
2580 noDict, (BYTE*)dst, NULL((void*)0), 0);
2581}
2582
2583LZ4_FORCE_O2
2584int LZ4_decompress_fast(const char* source, char* dest, int originalSize)
2585{
2586 DEBUGLOG(5, "LZ4_decompress_fast"){};
2587 return LZ4_decompress_unsafe_generic(
2588 (const BYTE*)source, (BYTE*)dest, originalSize,
2589 0, NULL((void*)0), 0);
2590}
2591
2592/*===== Instantiate a few more decoding cases, used more than once. =====*/
2593
2594LZ4_FORCE_O2 /* Exported, an obsolete API function. */
2595int LZ4_decompress_safe_withPrefix64k(const char* source, char* dest, int compressedSize, int maxOutputSize)
2596{
2597 return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize,
2598 decode_full_block, withPrefix64k,
2599 (BYTE*)dest - 64 KB*(1 <<10), NULL((void*)0), 0);
2600}
2601
2602LZ4_FORCE_O2
2603static int LZ4_decompress_safe_partial_withPrefix64k(const char* source, char* dest, int compressedSize, int targetOutputSize, int dstCapacity)
2604{
2605 dstCapacity = MIN(targetOutputSize, dstCapacity)( (targetOutputSize) < (dstCapacity) ? (targetOutputSize) :
(dstCapacity) );
2606 return LZ4_decompress_generic(source, dest, compressedSize, dstCapacity,
2607 partial_decode, withPrefix64k,
2608 (BYTE*)dest - 64 KB*(1 <<10), NULL((void*)0), 0);
2609}
2610
2611/* Another obsolete API function, paired with the previous one. */
2612int LZ4_decompress_fast_withPrefix64k(const char* source, char* dest, int originalSize)
2613{
2614 return LZ4_decompress_unsafe_generic(
2615 (const BYTE*)source, (BYTE*)dest, originalSize,
2616 64 KB*(1 <<10), NULL((void*)0), 0);
2617}
2618
2619LZ4_FORCE_O2
2620static int LZ4_decompress_safe_withSmallPrefix(const char* source, char* dest, int compressedSize, int maxOutputSize,
2621 size_t prefixSize)
2622{
2623 return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize,
2624 decode_full_block, noDict,
2625 (BYTE*)dest-prefixSize, NULL((void*)0), 0);
2626}
2627
2628LZ4_FORCE_O2
2629static int LZ4_decompress_safe_partial_withSmallPrefix(const char* source, char* dest, int compressedSize, int targetOutputSize, int dstCapacity,
2630 size_t prefixSize)
2631{
2632 dstCapacity = MIN(targetOutputSize, dstCapacity)( (targetOutputSize) < (dstCapacity) ? (targetOutputSize) :
(dstCapacity) );
2633 return LZ4_decompress_generic(source, dest, compressedSize, dstCapacity,
2634 partial_decode, noDict,
2635 (BYTE*)dest-prefixSize, NULL((void*)0), 0);
2636}
2637
2638LZ4_FORCE_O2
2639int LZ4_decompress_safe_forceExtDict(const char* source, char* dest,
2640 int compressedSize, int maxOutputSize,
2641 const void* dictStart, size_t dictSize)
2642{
2643 DEBUGLOG(5, "LZ4_decompress_safe_forceExtDict"){};
2644 return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize,
2645 decode_full_block, usingExtDict,
2646 (BYTE*)dest, (const BYTE*)dictStart, dictSize);
2647}
2648
2649LZ4_FORCE_O2
2650int LZ4_decompress_safe_partial_forceExtDict(const char* source, char* dest,
2651 int compressedSize, int targetOutputSize, int dstCapacity,
2652 const void* dictStart, size_t dictSize)
2653{
2654 dstCapacity = MIN(targetOutputSize, dstCapacity)( (targetOutputSize) < (dstCapacity) ? (targetOutputSize) :
(dstCapacity) );
2655 return LZ4_decompress_generic(source, dest, compressedSize, dstCapacity,
2656 partial_decode, usingExtDict,
2657 (BYTE*)dest, (const BYTE*)dictStart, dictSize);
2658}
2659
2660LZ4_FORCE_O2
2661static int LZ4_decompress_fast_extDict(const char* source, char* dest, int originalSize,
2662 const void* dictStart, size_t dictSize)
2663{
2664 return LZ4_decompress_unsafe_generic(
2665 (const BYTE*)source, (BYTE*)dest, originalSize,
2666 0, (const BYTE*)dictStart, dictSize);
2667}
2668
2669/* The "double dictionary" mode, for use with e.g. ring buffers: the first part
2670 * of the dictionary is passed as prefix, and the second via dictStart + dictSize.
2671 * These routines are used only once, in LZ4_decompress_*_continue().
2672 */
2673LZ4_FORCE_INLINEstatic inline __attribute__((always_inline))
2674int LZ4_decompress_safe_doubleDict(const char* source, char* dest, int compressedSize, int maxOutputSize,
2675 size_t prefixSize, const void* dictStart, size_t dictSize)
2676{
2677 return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize,
2678 decode_full_block, usingExtDict,
2679 (BYTE*)dest-prefixSize, (const BYTE*)dictStart, dictSize);
2680}
2681
2682/*===== streaming decompression functions =====*/
2683
2684#if !defined(LZ4_STATIC_LINKING_ONLY_DISABLE_MEMORY_ALLOCATION)
2685LZ4_streamDecode_t* LZ4_createStreamDecode(void)
2686{
2687 LZ4_STATIC_ASSERT(sizeof(LZ4_streamDecode_t) >= sizeof(LZ4_streamDecode_t_internal)){ enum { LZ4_static_assert = 1/(int)(!!(sizeof(LZ4_streamDecode_t
) >= sizeof(LZ4_streamDecode_t_internal))) }; };
2688 return (LZ4_streamDecode_t*) ALLOC_AND_ZERO(sizeof(LZ4_streamDecode_t))calloc(1,sizeof(LZ4_streamDecode_t));
2689}
2690
2691int LZ4_freeStreamDecode (LZ4_streamDecode_t* LZ4_stream)
2692{
2693 if (LZ4_stream == NULL((void*)0)) { return 0; } /* support free on NULL */
2694 FREEMEM(LZ4_stream)free(LZ4_stream);
2695 return 0;
2696}
2697#endif
2698
2699/*! LZ4_setStreamDecode() :
2700 * Use this function to instruct where to find the dictionary.
2701 * This function is not necessary if previous data is still available where it was decoded.
2702 * Loading a size of 0 is allowed (same effect as no dictionary).
2703 * @return : 1 if OK, 0 if error
2704 */
2705int LZ4_setStreamDecode (LZ4_streamDecode_t* LZ4_streamDecode, const char* dictionary, int dictSize)
2706{
2707 LZ4_streamDecode_t_internal* lz4sd = &LZ4_streamDecode->internal_donotuse;
2708 if (dictSize < 0) return 0;
2709 lz4sd->prefixSize = (size_t)dictSize;
2710 if (dictSize) {
2711 assert(dictionary != NULL)((void)0);
2712 lz4sd->prefixEnd = (const BYTE*) dictionary + dictSize;
2713 } else {
2714 lz4sd->prefixEnd = (const BYTE*) dictionary;
2715 }
2716 lz4sd->externalDict = NULL((void*)0);
2717 lz4sd->extDictSize = 0;
2718 return 1;
2719}
2720
2721/*! LZ4_decoderRingBufferSize() :
2722 * when setting a ring buffer for streaming decompression (optional scenario),
2723 * provides the minimum size of this ring buffer
2724 * to be compatible with any source respecting maxBlockSize condition.
2725 * Note : in a ring buffer scenario,
2726 * blocks are presumed decompressed next to each other.
2727 * When not enough space remains for next block (remainingSize < maxBlockSize),
2728 * decoding resumes from beginning of ring buffer.
2729 * @return : minimum ring buffer size,
2730 * or 0 if there is an error (invalid maxBlockSize).
2731 */
2732int LZ4_decoderRingBufferSize(int maxBlockSize)
2733{
2734 /* the margin must cover the widest write beyond a copy of the safe loop (16 bytes), minus 2 :
2735 * LZ4_decompress_generic() avoids the fast loop when history is closer than FASTLOOP_SAFE_DISTANCE,
2736 * which the current margin (64) never is. The former margin (14) remains valid. */
2737 LZ4_STATIC_ASSERT(LZ4_DECODER_RING_BUFFER_SIZE(0) - 65536 >= 16 - 2){ enum { LZ4_static_assert = 1/(int)(!!((65536 + 64 + (0)) - 65536
>= 16 - 2)) }; };
2738 if (maxBlockSize < 0) return 0;
2739 if (maxBlockSize > LZ4_MAX_INPUT_SIZE0x7E000000) return 0;
2740 if (maxBlockSize < 16) maxBlockSize = 16;
2741 return LZ4_DECODER_RING_BUFFER_SIZE(maxBlockSize)(65536 + 64 + (maxBlockSize));
2742}
2743
2744/*
2745*_continue() :
2746 These decoding functions allow decompression of multiple blocks in "streaming" mode.
2747 Previously decoded blocks must still be available at the memory position where they were decoded.
2748 If it's not possible, save the relevant part of decoded data into a safe buffer,
2749 and indicate where it stands using LZ4_setStreamDecode()
2750*/
2751LZ4_FORCE_O2
2752int LZ4_decompress_safe_continue (LZ4_streamDecode_t* LZ4_streamDecode, const char* source, char* dest, int compressedSize, int maxOutputSize)
2753{
2754 LZ4_streamDecode_t_internal* lz4sd = &LZ4_streamDecode->internal_donotuse;
2755 int result;
2756
2757 if (lz4sd->prefixSize == 0) {
2758 /* The first call, no dictionary yet. */
2759 assert(lz4sd->extDictSize == 0)((void)0);
2760 result = LZ4_decompress_safe(source, dest, compressedSize, maxOutputSize);
2761 if (result <= 0) return result;
2762 lz4sd->prefixSize = (size_t)result;
2763 lz4sd->prefixEnd = (BYTE*)dest + result;
2764 } else if (lz4sd->prefixEnd == (BYTE*)dest) {
2765 /* They're rolling the current segment. */
2766 if (lz4sd->prefixSize >= 64 KB*(1 <<10) - 1)
2767 result = LZ4_decompress_safe_withPrefix64k(source, dest, compressedSize, maxOutputSize);
2768 else if (lz4sd->extDictSize == 0)
2769 result = LZ4_decompress_safe_withSmallPrefix(source, dest, compressedSize, maxOutputSize,
2770 lz4sd->prefixSize);
2771 else
2772 result = LZ4_decompress_safe_doubleDict(source, dest, compressedSize, maxOutputSize,
2773 lz4sd->prefixSize, lz4sd->externalDict, lz4sd->extDictSize);
2774 if (result <= 0) return result;
2775 lz4sd->prefixSize += (size_t)result;
2776 lz4sd->prefixEnd += result;
2777 } else {
2778 /* The buffer wraps around, or they're switching to another buffer. */
2779 lz4sd->extDictSize = lz4sd->prefixSize;
2780 lz4sd->externalDict = lz4sd->prefixEnd - lz4sd->extDictSize;
2781 result = LZ4_decompress_safe_forceExtDict(source, dest, compressedSize, maxOutputSize,
2782 lz4sd->externalDict, lz4sd->extDictSize);
2783 if (result <= 0) return result;
2784 lz4sd->prefixSize = (size_t)result;
2785 lz4sd->prefixEnd = (BYTE*)dest + result;
2786 }
2787
2788 return result;
2789}
2790
2791LZ4_FORCE_O2 int
2792LZ4_decompress_fast_continue (LZ4_streamDecode_t* LZ4_streamDecode,
2793 const char* source, char* dest, int originalSize)
2794{
2795 LZ4_streamDecode_t_internal* const lz4sd =
2796 (assert(LZ4_streamDecode!=NULL)((void)0), &LZ4_streamDecode->internal_donotuse);
2797 int result;
2798
2799 DEBUGLOG(5, "LZ4_decompress_fast_continue (toDecodeSize=%i)", originalSize){};
2800 assert(originalSize >= 0)((void)0);
2801
2802 if (lz4sd->prefixSize == 0) {
2803 DEBUGLOG(5, "first invocation : no prefix nor extDict"){};
2804 assert(lz4sd->extDictSize == 0)((void)0);
2805 result = LZ4_decompress_fast(source, dest, originalSize);
2806 if (result <= 0) return result;
2807 lz4sd->prefixSize = (size_t)originalSize;
2808 lz4sd->prefixEnd = (BYTE*)dest + originalSize;
2809 } else if (lz4sd->prefixEnd == (BYTE*)dest) {
2810 DEBUGLOG(5, "continue using existing prefix"){};
2811 result = LZ4_decompress_unsafe_generic(
2812 (const BYTE*)source, (BYTE*)dest, originalSize,
2813 lz4sd->prefixSize,
2814 lz4sd->externalDict, lz4sd->extDictSize);
2815 if (result <= 0) return result;
2816 lz4sd->prefixSize += (size_t)originalSize;
2817 lz4sd->prefixEnd += originalSize;
2818 } else {
2819 DEBUGLOG(5, "prefix becomes extDict"){};
2820 lz4sd->extDictSize = lz4sd->prefixSize;
2821 lz4sd->externalDict = lz4sd->prefixEnd - lz4sd->extDictSize;
2822 result = LZ4_decompress_fast_extDict(source, dest, originalSize,
2823 lz4sd->externalDict, lz4sd->extDictSize);
2824 if (result <= 0) return result;
2825 lz4sd->prefixSize = (size_t)originalSize;
2826 lz4sd->prefixEnd = (BYTE*)dest + originalSize;
2827 }
2828
2829 return result;
2830}
2831
2832
2833/*
2834Advanced decoding functions :
2835*_usingDict() :
2836 These decoding functions work the same as "_continue" ones,
2837 the dictionary must be explicitly provided within parameters
2838*/
2839
2840int LZ4_decompress_safe_usingDict(const char* source, char* dest, int compressedSize, int maxOutputSize, const char* dictStart, int dictSize)
2841{
2842 if (dictSize < 0) return -1;
2843 if (dictSize==0)
2844 return LZ4_decompress_safe(source, dest, compressedSize, maxOutputSize);
2845 if (dictStart+dictSize == dest) {
2846 if (dictSize >= 64 KB*(1 <<10) - 1) {
2847 return LZ4_decompress_safe_withPrefix64k(source, dest, compressedSize, maxOutputSize);
2848 }
2849 assert(dictSize >= 0)((void)0);
2850 return LZ4_decompress_safe_withSmallPrefix(source, dest, compressedSize, maxOutputSize, (size_t)dictSize);
2851 }
2852 assert(dictSize >= 0)((void)0);
2853 return LZ4_decompress_safe_forceExtDict(source, dest, compressedSize, maxOutputSize, dictStart, (size_t)dictSize);
2854}
2855
2856int LZ4_decompress_safe_partial_usingDict(const char* source, char* dest, int compressedSize, int targetOutputSize, int dstCapacity, const char* dictStart, int dictSize)
2857{
2858 if (dictSize < 0) return -1;
2859 if (dictSize==0)
2860 return LZ4_decompress_safe_partial(source, dest, compressedSize, targetOutputSize, dstCapacity);
2861 if (dictStart+dictSize == dest) {
2862 if (dictSize >= 64 KB*(1 <<10) - 1) {
2863 return LZ4_decompress_safe_partial_withPrefix64k(source, dest, compressedSize, targetOutputSize, dstCapacity);
2864 }
2865 assert(dictSize >= 0)((void)0);
2866 return LZ4_decompress_safe_partial_withSmallPrefix(source, dest, compressedSize, targetOutputSize, dstCapacity, (size_t)dictSize);
2867 }
2868 assert(dictSize >= 0)((void)0);
2869 return LZ4_decompress_safe_partial_forceExtDict(source, dest, compressedSize, targetOutputSize, dstCapacity, dictStart, (size_t)dictSize);
2870}
2871
2872int LZ4_decompress_fast_usingDict(const char* source, char* dest, int originalSize, const char* dictStart, int dictSize)
2873{
2874 if (dictSize < 0) return -1;
2875 if (dictSize==0 || dictStart+dictSize == dest)
2876 return LZ4_decompress_unsafe_generic(
2877 (const BYTE*)source, (BYTE*)dest, originalSize,
2878 (size_t)dictSize, NULL((void*)0), 0);
2879 assert(dictSize >= 0)((void)0);
2880 return LZ4_decompress_fast_extDict(source, dest, originalSize, dictStart, (size_t)dictSize);
2881}
2882
2883
2884/*=*************************************************
2885* Obsolete Functions
2886***************************************************/
2887/* obsolete compression functions */
2888int LZ4_compress_limitedOutput(const char* source, char* dest, int inputSize, int maxOutputSize)
2889{
2890 return LZ4_compress_default(source, dest, inputSize, maxOutputSize);
2891}
2892int LZ4_compress(const char* src, char* dest, int srcSize)
2893{
2894 return LZ4_compress_default(src, dest, srcSize, LZ4_compressBound(srcSize));
2895}
2896int LZ4_compress_limitedOutput_withState (void* state, const char* src, char* dst, int srcSize, int dstSize)
2897{
2898 return LZ4_compress_fast_extState(state, src, dst, srcSize, dstSize, 1);
2899}
2900int LZ4_compress_withState (void* state, const char* src, char* dst, int srcSize)
2901{
2902 return LZ4_compress_fast_extState(state, src, dst, srcSize, LZ4_compressBound(srcSize), 1);
2903}
2904int LZ4_compress_limitedOutput_continue (LZ4_stream_t* LZ4_stream, const char* src, char* dst, int srcSize, int dstCapacity)
2905{
2906 return LZ4_compress_fast_continue(LZ4_stream, src, dst, srcSize, dstCapacity, 1);
2907}
2908int LZ4_compress_continue (LZ4_stream_t* LZ4_stream, const char* source, char* dest, int inputSize)
2909{
2910 return LZ4_compress_fast_continue(LZ4_stream, source, dest, inputSize, LZ4_compressBound(inputSize), 1);
2911}
2912
2913/*
2914These decompression functions are deprecated and should no longer be used.
2915They are only provided here for compatibility with older user programs.
2916- LZ4_uncompress is totally equivalent to LZ4_decompress_fast
2917- LZ4_uncompress_unknownOutputSize is totally equivalent to LZ4_decompress_safe
2918*/
2919int LZ4_uncompress (const char* source, char* dest, int outputSize)
2920{
2921 return LZ4_decompress_fast(source, dest, outputSize);
2922}
2923int LZ4_uncompress_unknownOutputSize (const char* source, char* dest, int isize, int maxOutputSize)
2924{
2925 return LZ4_decompress_safe(source, dest, isize, maxOutputSize);
2926}
2927
2928/* Obsolete Streaming functions */
2929
2930int LZ4_sizeofStreamState(void) { return sizeof(LZ4_stream_t); }
2931
2932int LZ4_resetStreamState(void* state, char* inputBuffer)
2933{
2934 (void)inputBuffer;
2935 LZ4_resetStream((LZ4_stream_t*)state);
2936 return 0;
2937}
2938
2939#if !defined(LZ4_STATIC_LINKING_ONLY_DISABLE_MEMORY_ALLOCATION)
2940void* LZ4_create (char* inputBuffer)
2941{
2942 (void)inputBuffer;
2943 return LZ4_createStream();
2944}
2945#endif
2946
2947char* LZ4_slideInputBuffer (void* state)
2948{
2949 /* avoid const char * -> char * conversion warning */
2950 return (char *)(uptrval)((LZ4_stream_t*)state)->internal_donotuse.dictionary;
2951}
2952
2953#endif /* LZ4_COMMONDEFS_ONLY */