Bug Summary

File:root/firefox-clang/mozglue/static/lz4/lz4hc.c
Warning:line 1864, column 9
Null pointer passed as 1st argument to memory copy function

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 lz4hc.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/lz4hc.c
1/*
2 LZ4 HC - High Compression Mode of LZ4
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 source repository : https://github.com/lz4/lz4
32 - LZ4 public forum : https://groups.google.com/forum/#!forum/lz4c
33*/
34/* note : lz4hc is not an independent module, it requires lz4.h/lz4.c for proper compilation */
35
36
37/* *************************************
38* Tuning Parameter
39***************************************/
40
41/*! HEAPMODE :
42 * Select how stateless HC compression functions like `LZ4_compress_HC()`
43 * allocate memory for their workspace:
44 * in stack (0:fastest), or in heap (1:default, requires malloc()).
45 * Since workspace is rather large, heap mode is recommended.
46**/
47#ifndef LZ4HC_HEAPMODE1
48# define LZ4HC_HEAPMODE1 1
49#endif
50
51
52/*=== Dependency ===*/
53#define LZ4_HC_STATIC_LINKING_ONLY
54#include "lz4hc.h"
55#include <limits.h>
56
57
58/*=== Shared lz4.c code ===*/
59#ifndef LZ4_SRC_INCLUDED1
60# if defined(__GNUC__4)
61# pragma GCC diagnostic ignored "-Wunused-function"
62# endif
63# if defined (__clang__1)
64# pragma clang diagnostic ignored "-Wunused-function"
65# endif
66# define LZ4_COMMONDEFS_ONLY
67# include "lz4.c" /* LZ4_count, constants, mem */
68#endif
69
70
71/*=== Enums ===*/
72typedef enum { noDictCtx, usingDictCtxHc } dictCtx_directive;
73
74
75/*=== Constants ===*/
76#define OPTIMAL_ML(int)((((1U<<4)-1)-1)+4) (int)((ML_MASK((1U<<4)-1)-1)+MINMATCH4)
77#define LZ4_OPT_NUM(1<<12) (1<<12)
78
79
80/*=== Macros ===*/
81#undef MIN
82#define MIN(a,b)( (a) < (b) ? (a) : (b) ) ( (a) < (b) ? (a) : (b) )
83#undef MAX
84#define MAX(a,b)( (a) > (b) ? (a) : (b) ) ( (a) > (b) ? (a) : (b) )
85
86
87/*=== Levels definition ===*/
88typedef enum { lz4mid, lz4hc, lz4opt } lz4hc_strat_e;
89typedef struct {
90 lz4hc_strat_e strat;
91 int nbSearches;
92 U32 targetLength;
93 int nbSearchesSeq; /* lz4opt with favorDecSpeed only : budget at positions only worth searching to save a sequence */
94 int dictCopyMin; /* attached dictionary : from this input size, its tables (256 KB) are copied rather than referenced (dictCtx),
95 * which compresses as well or better, and pays off sooner at levels which search more */
96} cParams_t;
97static const cParams_t k_clTable[LZ4HC_CLEVEL_MAX12+1] = {
98 { lz4mid, 2, 16, 0, 4 KB*(1 <<10) }, /* 0, unused */
99 { lz4mid, 2, 16, 0, 4 KB*(1 <<10) }, /* 1, unused */
100 { lz4mid, 2, 16, 0, 4 KB*(1 <<10) }, /* 2 */
101 { lz4hc, 4, 16, 0, 4 KB*(1 <<10) }, /* 3 */
102 { lz4hc, 8, 16, 0, 4 KB*(1 <<10) }, /* 4 */
103 { lz4hc, 16, 16, 0, 4 KB*(1 <<10) }, /* 5 */
104 { lz4hc, 32, 16, 0, 4 KB*(1 <<10) }, /* 6 */
105 { lz4hc, 64, 16, 0, 4 KB*(1 <<10) }, /* 7 */
106 { lz4hc, 128, 16, 0, 4 KB*(1 <<10) }, /* 8 */
107 { lz4hc, 256, 16, 0, 4 KB*(1 <<10) }, /* 9 */
108 { lz4opt, 96, 64, 1, 4 KB*(1 <<10) }, /*10==LZ4HC_CLEVEL_OPT_MIN*/
109 { lz4opt, 512,128, 2, 2 KB*(1 <<10) }, /*11 */
110 { lz4opt,16384,LZ4_OPT_NUM(1<<12), 64, 1 KB*(1 <<10) }, /* 12==LZ4HC_CLEVEL_MAX */
111};
112
113static cParams_t LZ4HC_getCLevelParams(int cLevel)
114{
115 /* note : clevel convention is a bit different from lz4frame,
116 * possibly something worth revisiting for consistency */
117 if (cLevel < 1)
118 cLevel = LZ4HC_CLEVEL_DEFAULT9;
119 cLevel = MIN(LZ4HC_CLEVEL_MAX, cLevel)( (12) < (cLevel) ? (12) : (cLevel) );
120 return k_clTable[cLevel];
121}
122
123
124/*=== Hashing ===*/
125#define LZ4HC_HASHSIZE4 4
126#define HASH_FUNCTION(i)(((i) * 2654435761U) >> ((4*8)-15)) (((i) * 2654435761U) >> ((MINMATCH4*8)-LZ4HC_HASH_LOG15))
127static U32 LZ4HC_hashPtr(const void* ptr) { return HASH_FUNCTION(LZ4_read32(ptr))(((LZ4_read32(ptr)) * 2654435761U) >> ((4*8)-15)); }
128
129#if defined(LZ4_FORCE_MEMORY_ACCESS1) && (LZ4_FORCE_MEMORY_ACCESS1==2)
130/* lie to the compiler about data alignment; use with caution */
131static U64 LZ4_read64(const void* memPtr) { return *(const U64*) memPtr; }
132
133#elif defined(LZ4_FORCE_MEMORY_ACCESS1) && (LZ4_FORCE_MEMORY_ACCESS1==1)
134/* __pack instructions are safer, but compiler specific */
135LZ4_PACK(typedef struct { U64 u64; })typedef struct { U64 u64; } __attribute__((__packed__)) LZ4_unalign64;
136static U64 LZ4_read64(const void* ptr) { return ((const LZ4_unalign64*)ptr)->u64; }
137
138#else /* safe and portable access using memcpy() */
139static U64 LZ4_read64(const void* memPtr)
140{
141 U64 val; LZ4_memcpy(&val, memPtr, sizeof(val))__builtin_memcpy(&val, memPtr, sizeof(val)); return val;
142}
143
144#endif /* LZ4_FORCE_MEMORY_ACCESS */
145
146#define LZ4MID_HASHSIZE8 8
147#define LZ4MID_HASHLOG(15 -1) (LZ4HC_HASH_LOG15-1)
148#define LZ4MID_HASHTABLESIZE(1 << (15 -1)) (1 << LZ4MID_HASHLOG(15 -1))
149
150static U32 LZ4MID_hash4(U32 v) { return (v * 2654435761U) >> (32-LZ4MID_HASHLOG(15 -1)); }
151static U32 LZ4MID_hash4Ptr(const void* ptr) { return LZ4MID_hash4(LZ4_read32(ptr)); }
152/* note: hash7 hashes the lower 56-bits.
153 * It presumes input was read using little endian.*/
154static U32 LZ4MID_hash7(U64 v) { return (U32)(((v << (64-56)) * 58295818150454627ULL) >> (64-LZ4MID_HASHLOG(15 -1))) ; }
155static U64 LZ4_readLE64(const void* memPtr);
156static U32 LZ4MID_hash8Ptr(const void* ptr) { return LZ4MID_hash7(LZ4_readLE64(ptr)); }
157
158static U64 LZ4_readLE64(const void* memPtr)
159{
160 if (LZ4_isLittleEndian()) {
161 return LZ4_read64(memPtr);
162 } else {
163 const BYTE* p = (const BYTE*)memPtr;
164 /* note: relies on the compiler to simplify this expression */
165 return (U64)p[0] | ((U64)p[1]<<8) | ((U64)p[2]<<16) | ((U64)p[3]<<24)
166 | ((U64)p[4]<<32) | ((U64)p[5]<<40) | ((U64)p[6]<<48) | ((U64)p[7]<<56);
167 }
168}
169
170
171/*=== Count match length ===*/
172LZ4_FORCE_INLINEstatic inline __attribute__((always_inline))
173unsigned LZ4HC_NbCommonBytes32(U32 val)
174{
175 assert(val != 0)((void)0);
176 if (LZ4_isLittleEndian()) {
177# if defined(_MSC_VER) && (_MSC_VER >= 1400) && !defined(LZ4_FORCE_SW_BITCOUNT)
178 unsigned long r;
179 _BitScanReverse(&r, val);
180 return (unsigned)((31 - r) >> 3);
181# elif (defined(__clang__1) || (defined(__GNUC__4) && ((__GNUC__4 > 3) || \
182 ((__GNUC__4 == 3) && (__GNUC_MINOR__2 >= 4))))) && \
183 !defined(LZ4_FORCE_SW_BITCOUNT)
184 return (unsigned)__builtin_clz(val) >> 3;
185# else
186 val >>= 8;
187 val = ((((val + 0x00FFFF00) | 0x00FFFFFF) + val) |
188 (val + 0x00FF0000)) >> 24;
189 return (unsigned)val ^ 3;
190# endif
191 } else {
192# if defined(_MSC_VER) && (_MSC_VER >= 1400) && !defined(LZ4_FORCE_SW_BITCOUNT)
193 unsigned long r;
194 _BitScanForward(&r, val);
195 return (unsigned)(r >> 3);
196# elif (defined(__clang__1) || (defined(__GNUC__4) && ((__GNUC__4 > 3) || \
197 ((__GNUC__4 == 3) && (__GNUC_MINOR__2 >= 4))))) && \
198 !defined(LZ4_FORCE_SW_BITCOUNT)
199 return (unsigned)__builtin_ctz(val) >> 3;
200# else
201 const U32 m = 0x01010101;
202 return (unsigned)((((val - 1) ^ val) & (m - 1)) * m) >> 24;
203# endif
204 }
205}
206
207/** LZ4HC_countBack() :
208 * @return : negative value, nb of common bytes before ip/match */
209LZ4_FORCE_INLINEstatic inline __attribute__((always_inline))
210int LZ4HC_countBack(const BYTE* const ip, const BYTE* const match,
211 const BYTE* const iMin, const BYTE* const mMin)
212{
213 int back = 0;
214 int const min = (int)MAX(iMin - ip, mMin - match)( (iMin - ip) > (mMin - match) ? (iMin - ip) : (mMin - match
) );
215 assert(min <= 0)((void)0);
216 assert(ip >= iMin)((void)0); assert((size_t)(ip-iMin) < (1U<<31))((void)0);
217 assert(match >= mMin)((void)0); assert((size_t)(match - mMin) < (1U<<31))((void)0);
218
219 while ((back - min) > 3) {
220 U32 const v = LZ4_read32(ip + back - 4) ^ LZ4_read32(match + back - 4);
221 if (v) {
222 return (back - (int)LZ4HC_NbCommonBytes32(v));
223 } else back -= 4; /* 4-byte step */
224 }
225 /* check remainder if any */
226 while ( (back > min)
227 && (ip[back-1] == match[back-1]) )
228 back--;
229 return back;
230}
231
232/*=== Chain table updates ===*/
233#define DELTANEXTU16(table, pos)table[(U16)(pos)] table[(U16)(pos)] /* faster */
234/* Make fields passed to, and updated by LZ4HC_encodeSequence explicit */
235#define UPDATABLE(ip, op, anchor)&ip, &op, &anchor &ip, &op, &anchor
236
237
238/**************************************
239* Init
240**************************************/
241static void LZ4HC_clearTables (LZ4HC_CCtx_internal* hc4)
242{
243 MEM_INIT(hc4->hashTable, 0, sizeof(hc4->hashTable))memset(((hc4->hashTable)),((0)),((sizeof(hc4->hashTable
))));
244 MEM_INIT(hc4->chainTable, 0xFF, sizeof(hc4->chainTable))memset(((hc4->chainTable)),((0xFF)),((sizeof(hc4->chainTable
))));
245}
246
247static void LZ4HC_init_internal (LZ4HC_CCtx_internal* hc4, const BYTE* start)
248{
249 size_t const bufferSize = (size_t)(hc4->end - hc4->prefixStart);
250 size_t newStartingOffset = bufferSize + hc4->dictLimit;
251 DEBUGLOG(5, "LZ4HC_init_internal"){};
252 assert(newStartingOffset >= bufferSize)((void)0); /* check overflow */
253 if (newStartingOffset > 1 GB*(1U<<30)) {
254 LZ4HC_clearTables(hc4);
255 newStartingOffset = 0;
256 }
257 newStartingOffset += 64 KB*(1 <<10);
258 hc4->nextToUpdate = (U32)newStartingOffset;
259 hc4->prefixStart = start;
260 hc4->end = start;
261 hc4->dictStart = start;
262 hc4->dictLimit = (U32)newStartingOffset;
263 hc4->lowLimit = (U32)newStartingOffset;
264}
265
266
267/**************************************
268* Encode
269**************************************/
270#if defined(LZ4_DEBUG) && (LZ4_DEBUG >= 2)
271# define RAWLOG(...) fprintf(stderr, __VA_ARGS__)
272void LZ4HC_hexOut(const void* src, size_t len)
273{
274 const BYTE* p = (const BYTE*)src;
275 size_t n;
276 for (n=0; n<len; n++) {
277 RAWLOG("%02X ", p[n]);
278 }
279 RAWLOG(" \n");
280}
281
282# define HEX_CMP(_lev, _ptr, _ref, _len) \
283 if (LZ4_DEBUG >= _lev) { \
284 RAWLOG("match bytes: "); \
285 LZ4HC_hexOut(_ptr, _len); \
286 RAWLOG("ref bytes: "); \
287 LZ4HC_hexOut(_ref, _len); \
288 }
289
290#else
291# define HEX_CMP(l,p,r,_l)
292#endif
293
294/* LZ4HC_encodeSequence() :
295 * @return : 0 if ok,
296 * 1 if buffer issue detected : @ip, @op and @anchor are then unchanged */
297LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) int LZ4HC_encodeSequence (
298 const BYTE** _ip,
299 BYTE** _op,
300 const BYTE** _anchor,
301 int matchLength,
302 int offset,
303 limitedOutput_directive limit,
304 BYTE* oend)
305{
306#define ip (*_ip)
307#define op (*_op)
308#define anchor (*_anchor)
309
310 BYTE* const token = op++;
311
312#if defined(LZ4_DEBUG) && (LZ4_DEBUG >= 6)
313 static const BYTE* start = NULL((void*)0);
314 static U32 totalCost = 0;
315 U32 const pos = (start==NULL((void*)0)) ? 0 : (U32)(anchor - start); /* only works for single segment */
316 U32 const ll = (U32)(ip - anchor);
317 U32 const llAdd = (ll>=15) ? ((ll-15) / 255) + 1 : 0;
318 U32 const mlAdd = (matchLength>=19) ? ((matchLength-19) / 255) + 1 : 0;
319 U32 const cost = 1 + llAdd + ll + 2 + mlAdd;
320 if (start==NULL((void*)0)) start = anchor; /* only works for single segment */
321 DEBUGLOG(6, "pos:%7u -- literals:%4u, match:%4i, offset:%5i, cost:%4u + %5u",{}
322 pos,{}
323 (U32)(ip - anchor), matchLength, offset,{}
324 cost, totalCost){};
325# if 1 /* only works on single segment data */
326 HEX_CMP(7, ip, ip-offset, matchLength);
327# endif
328 totalCost += cost;
329#endif
330
331 /* Encode Literal length */
332 { size_t litLen = (size_t)(ip - anchor);
333 LZ4_STATIC_ASSERT(notLimited == 0){ enum { LZ4_static_assert = 1/(int)(!!(notLimited == 0)) }; };
334 /* Check output limit */
335 if (limit && ((op + (litLen / 255) + litLen + (2 + 1 + LASTLITERALS5)) > oend)) {
336 DEBUGLOG(6, "Not enough room to write %i literals (%i bytes remaining)",{}
337 (int)litLen, (int)(oend - op)){};
338 op = token;
339 return 1;
340 }
341 if (litLen >= RUN_MASK((1U<<(8-4))-1)) {
342 size_t len = litLen - RUN_MASK((1U<<(8-4))-1);
343 *token = (RUN_MASK((1U<<(8-4))-1) << ML_BITS4);
344 for(; len >= 255 ; len -= 255) *op++ = 255;
345 *op++ = (BYTE)len;
346 } else {
347 *token = (BYTE)(litLen << ML_BITS4);
348 }
349
350 /* Copy Literals */
351 LZ4_wildCopy8(op, anchor, op + litLen);
352 op += litLen;
353 }
354
355 /* Encode Offset */
356 assert(offset <= LZ4_DISTANCE_MAX )((void)0);
357 assert(offset > 0)((void)0);
358 LZ4_writeLE16(op, (U16)(offset)); op += 2;
359
360 /* Encode MatchLength */
361 assert(matchLength >= MINMATCH)((void)0);
362 { size_t mlCode = (size_t)matchLength - MINMATCH4;
363 if (limit && (op + (mlCode / 255) + (1 + LASTLITERALS5) > oend)) {
364 DEBUGLOG(6, "Not enough room to write match length"){};
365 op = token;
366 return 1;
367 }
368 if (mlCode >= ML_MASK((1U<<4)-1)) {
369 *token += ML_MASK((1U<<4)-1);
370 mlCode -= ML_MASK((1U<<4)-1);
371 for(; mlCode >= 510 ; mlCode -= 510) { *op++ = 255; *op++ = 255; }
372 if (mlCode >= 255) { mlCode -= 255; *op++ = 255; }
373 *op++ = (BYTE)mlCode;
374 } else {
375 *token += (BYTE)(mlCode);
376 } }
377
378 /* Prepare next loop */
379 ip += matchLength;
380 anchor = ip;
381
382 return 0;
383
384#undef ip
385#undef op
386#undef anchor
387}
388
389/* LZ4HC_encodeLastLiterals() :
390 * Encode the final run of literals, from @anchor to @iend.
391 * In fillOutput mode, the run may be truncated, to fit into dst.
392 * @oend : same as LZ4HC_encodeSequence() : end of dst, minus LASTLITERALS in fillOutput mode
393 * @return : 0 if ok,
394 * 1 if dst is too small (limitedOutput) */
395static int LZ4HC_encodeLastLiterals (
396 const BYTE** _ip,
397 BYTE** _op,
398 const BYTE** _anchor,
399 const BYTE* iend,
400 limitedOutput_directive limit,
401 BYTE* oend)
402{
403#define ip (*_ip)
404#define op (*_op)
405#define anchor (*_anchor)
406
407 BYTE* const dstEnd = (limit == fillOutput) ? oend + LASTLITERALS5 : oend;
408 size_t lastRunSize = (size_t)(iend - anchor); /* literals */
409 size_t llAdd = (lastRunSize + 255 - RUN_MASK((1U<<(8-4))-1)) / 255;
410 size_t const totalSize = 1 + llAdd + lastRunSize;
411 if (limit && (op + totalSize > dstEnd)) {
412 if (limit == limitedOutput) return 1; /* not enough space in dst */
413 /* adapt lastRunSize to fill dst */
414 lastRunSize = (size_t)(dstEnd - op) - 1 /*token*/;
415 llAdd = (lastRunSize + 256 - RUN_MASK((1U<<(8-4))-1)) / 256;
416 lastRunSize -= llAdd;
417 }
418 DEBUGLOG(6, "Final literal run : %i literals", (int)lastRunSize){};
419 ip = anchor + lastRunSize; /* can be != iend if limit==fillOutput */
420
421 if (lastRunSize >= RUN_MASK((1U<<(8-4))-1)) {
422 size_t accumulator = lastRunSize - RUN_MASK((1U<<(8-4))-1);
423 *op++ = (RUN_MASK((1U<<(8-4))-1) << ML_BITS4);
424 for(; accumulator >= 255 ; accumulator -= 255) *op++ = 255;
425 *op++ = (BYTE) accumulator;
426 } else {
427 *op++ = (BYTE)(lastRunSize << ML_BITS4);
428 }
429 assert(lastRunSize <= (size_t)(dstEnd - op))((void)0);
430 LZ4_memcpy(op, anchor, lastRunSize)__builtin_memcpy(op, anchor, lastRunSize);
431 op += lastRunSize;
432 return 0;
433
434#undef ip
435#undef op
436#undef anchor
437}
438
439/* LZ4HC_encodeLastSequence_fillOutput() :
440 * fillOutput mode only : current sequence doesn't fit into dst.
441 * Encode it anyway if all its literals fit, shortening its match if need be,
442 * but only if it leaves enough room for the final run of literals (MFLIMIT).
443 * @op : start of this sequence (before the failed LZ4HC_encodeSequence())
444 * @oend : same as LZ4HC_encodeSequence() : end of dst minus LASTLITERALS */
445static void LZ4HC_encodeLastSequence_fillOutput (
446 const BYTE** _ip,
447 BYTE** _op,
448 const BYTE** _anchor,
449 int matchLength,
450 int offset,
451 BYTE* oend)
452{
453#define ip (*_ip)
454#define op (*_op)
455#define anchor (*_anchor)
456
457 BYTE* const dstEnd = oend + LASTLITERALS5;
458 size_t const ll = (size_t)(ip - anchor);
459 size_t const ll_addbytes = (ll + 240) / 255;
460 size_t const ll_totalCost = 1 + ll_addbytes + ll;
461 BYTE* const maxLitPos = oend - 3; /* 2 for offset, 1 for token */
462 DEBUGLOG(6, "Last sequence is overflowing : %u literals, %u remaining space",{}
463 (unsigned)ll, (unsigned)(oend - op)){};
464 if (op + ll_totalCost <= maxLitPos) {
465 /* ll validated; now adjust match length */
466 size_t const bytesLeftForMl = (size_t)(maxLitPos - (op+ll_totalCost));
467 size_t const maxMlSize = MINMATCH4 + (ML_MASK((1U<<4)-1)-1) + (bytesLeftForMl * 255);
468 assert(maxMlSize < INT_MAX)((void)0); assert(matchLength >= 0)((void)0);
469 if ((size_t)matchLength > maxMlSize) matchLength = (int)maxMlSize;
470 if (dstEnd - (op + ll_totalCost + 2) - 1 + matchLength >= MFLIMIT12) {
471 DEBUGLOG(6, "Let's encode a last sequence (ll=%u, ml=%i)", (unsigned)ll, matchLength){};
472 LZ4HC_encodeSequence(UPDATABLE(ip, op, anchor)&ip, &op, &anchor, matchLength, offset, notLimited, oend);
473 } }
474
475#undef ip
476#undef op
477#undef anchor
478}
479
480
481typedef struct {
482 int off;
483 int len;
484 int back; /* negative value */
485} LZ4HC_match_t;
486
487static LZ4HC_match_t LZ4HC_searchExtDict(const BYTE* ip, U32 ipIndex,
488 const BYTE* const iLowLimit, const BYTE* const iHighLimit,
489 const LZ4HC_CCtx_internal* dictCtx, U32 gDictEndIndex,
490 int currentBestML, int nbAttempts)
491{
492 size_t const lDictEndIndex = (size_t)(dictCtx->end - dictCtx->prefixStart) + dictCtx->dictLimit;
493 U32 lDictMatchIndex = dictCtx->hashTable[LZ4HC_hashPtr(ip)];
494 U32 matchIndex = lDictMatchIndex + gDictEndIndex - (U32)lDictEndIndex;
495 int offset = 0, sBack = 0;
496 assert(lDictEndIndex <= 1 GB)((void)0);
497 if (lDictMatchIndex>0)
498 DEBUGLOG(7, "lDictEndIndex = %zu, lDictMatchIndex = %u", lDictEndIndex, lDictMatchIndex){};
499 while (ipIndex - matchIndex <= LZ4_DISTANCE_MAX65535 && nbAttempts--) {
500 const BYTE* const matchPtr = dictCtx->prefixStart - dictCtx->dictLimit + lDictMatchIndex;
501
502 if (LZ4_read32(matchPtr) == LZ4_read32(ip)) {
503 int mlt;
504 int back = 0;
505 const BYTE* vLimit = ip + (lDictEndIndex - lDictMatchIndex);
506 if (vLimit > iHighLimit) vLimit = iHighLimit;
507 mlt = (int)LZ4_count(ip+MINMATCH4, matchPtr+MINMATCH4, vLimit) + MINMATCH4;
508 back = (ip > iLowLimit) ? LZ4HC_countBack(ip, matchPtr, iLowLimit, dictCtx->prefixStart) : 0;
509 mlt -= back;
510 if (mlt > currentBestML) {
511 currentBestML = mlt;
512 offset = (int)(ipIndex - matchIndex);
513 sBack = back;
514 DEBUGLOG(7, "found match of length %i within extDictCtx", currentBestML){};
515 } }
516
517 { U32 const nextOffset = DELTANEXTU16(dictCtx->chainTable, lDictMatchIndex)dictCtx->chainTable[(U16)(lDictMatchIndex)];
518 lDictMatchIndex -= nextOffset;
519 matchIndex -= nextOffset;
520 } }
521
522 { LZ4HC_match_t md;
523 md.len = currentBestML;
524 md.off = offset;
525 md.back = sBack;
526 return md;
527 }
528}
529
530typedef LZ4HC_match_t (*LZ4MID_searchIntoDict_f)(const BYTE* ip, U32 ipIndex,
531 const BYTE* const iHighLimit,
532 const LZ4HC_CCtx_internal* dictCtx, U32 gDictEndIndex);
533
534static LZ4HC_match_t LZ4MID_searchHCDict(const BYTE* ip, U32 ipIndex,
535 const BYTE* const iHighLimit,
536 const LZ4HC_CCtx_internal* dictCtx, U32 gDictEndIndex)
537{
538 return LZ4HC_searchExtDict(ip,ipIndex,
539 ip, iHighLimit,
540 dictCtx, gDictEndIndex,
541 MINMATCH4-1, 2);
542}
543
544static LZ4HC_match_t LZ4MID_searchExtDict(const BYTE* ip, U32 ipIndex,
545 const BYTE* const iHighLimit,
546 const LZ4HC_CCtx_internal* dictCtx, U32 gDictEndIndex)
547{
548 size_t const lDictEndIndex = (size_t)(dictCtx->end - dictCtx->prefixStart) + dictCtx->dictLimit;
549 const U32* const hash4Table = dictCtx->hashTable;
550 const U32* const hash8Table = hash4Table + LZ4MID_HASHTABLESIZE(1 << (15 -1));
551 DEBUGLOG(7, "LZ4MID_searchExtDict (ipIdx=%u)", ipIndex){};
552
553 /* search long match first */
554 { U32 l8DictMatchIndex = hash8Table[LZ4MID_hash8Ptr(ip)];
555 U32 m8Index = l8DictMatchIndex + gDictEndIndex - (U32)lDictEndIndex;
556 assert(lDictEndIndex <= 1 GB)((void)0);
557 if (ipIndex - m8Index <= LZ4_DISTANCE_MAX65535) {
558 const BYTE* const matchPtr = dictCtx->prefixStart - dictCtx->dictLimit + l8DictMatchIndex;
559 const size_t safeLen = MIN(lDictEndIndex - l8DictMatchIndex, (size_t)(iHighLimit - ip))( (lDictEndIndex - l8DictMatchIndex) < ((size_t)(iHighLimit
- ip)) ? (lDictEndIndex - l8DictMatchIndex) : ((size_t)(iHighLimit
- ip)) );
560 int mlt = (int)LZ4_count(ip, matchPtr, ip + safeLen);
561 if (mlt >= MINMATCH4) {
562 LZ4HC_match_t md;
563 DEBUGLOG(7, "Found long ExtDict match of len=%u", mlt){};
564 md.len = mlt;
565 md.off = (int)(ipIndex - m8Index);
566 md.back = 0;
567 return md;
568 }
569 }
570 }
571
572 /* search for short match second */
573 { U32 l4DictMatchIndex = hash4Table[LZ4MID_hash4Ptr(ip)];
574 U32 m4Index = l4DictMatchIndex + gDictEndIndex - (U32)lDictEndIndex;
575 if (ipIndex - m4Index <= LZ4_DISTANCE_MAX65535) {
576 const BYTE* const matchPtr = dictCtx->prefixStart - dictCtx->dictLimit + l4DictMatchIndex;
577 const size_t safeLen = MIN(lDictEndIndex - l4DictMatchIndex, (size_t)(iHighLimit - ip))( (lDictEndIndex - l4DictMatchIndex) < ((size_t)(iHighLimit
- ip)) ? (lDictEndIndex - l4DictMatchIndex) : ((size_t)(iHighLimit
- ip)) );
578 int mlt = (int)LZ4_count(ip, matchPtr, ip + safeLen);
579 if (mlt >= MINMATCH4) {
580 LZ4HC_match_t md;
581 DEBUGLOG(7, "Found short ExtDict match of len=%u", mlt){};
582 md.len = mlt;
583 md.off = (int)(ipIndex - m4Index);
584 md.back = 0;
585 return md;
586 }
587 }
588 }
589
590 /* nothing found */
591 { LZ4HC_match_t const md = {0, 0, 0 };
592 return md;
593 }
594}
595
596/* LZ4HC_dropPositions() :
597 * In fillOutput mode, compression can stop at @start, before positions the parser has already referenced.
598 * The next block compresses them : it must not find them as matches.
599 * Remove their references from the hash table, up to @end (excluded).
600 * Costs one pass on these positions, or on the hash table, whichever is shorter. */
601static void
602LZ4HC_dropPositions(LZ4HC_CCtx_internal* ctx, const BYTE* start, const BYTE* end, lz4hc_strat_e strat)
603{
604 U32* const hashTable = ctx->hashTable;
605 U32 const startIdx = ctx->dictLimit + (U32)(start - ctx->prefixStart);
606 if (end - start > LZ4HC_HASHTABLESIZE(1 << 15)) {
607 int i;
608 for (i = 0; i < LZ4HC_HASHTABLESIZE(1 << 15); i++) {
609 /* branchless, so that it can be vectorized */
610 hashTable[i] = (hashTable[i] >= startIdx) ? 0 : hashTable[i];
611 }
612 } else {
613 U32 idx = startIdx;
614 const BYTE* p;
615 for (p = start; p < end; p++, idx++) {
616 if (strat == lz4mid) {
617 U32 const h4 = LZ4MID_hash4Ptr(p);
618 U32 const h8 = LZ4MID_HASHTABLESIZE(1 << (15 -1)) + LZ4MID_hash8Ptr(p);
619 if (hashTable[h4] == idx) hashTable[h4] = 0;
620 if (hashTable[h8] == idx) hashTable[h8] = 0;
621 } else {
622 U32 const h = LZ4HC_hashPtr(p);
623 if (hashTable[h] == idx) hashTable[h] = 0;
624 } } }
625}
626
627/**************************************
628* Mid Compression (level 2)
629**************************************/
630
631LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) void
632LZ4MID_addPosition(U32* hTable, U32 hValue, U32 index)
633{
634 hTable[hValue] = index;
635}
636
637#define ADDPOS8(_p, _idx)LZ4MID_addPosition(hash8Table, LZ4MID_hash8Ptr(_p), _idx) LZ4MID_addPosition(hash8Table, LZ4MID_hash8Ptr(_p), _idx)
638#define ADDPOS4(_p, _idx)LZ4MID_addPosition(hash4Table, LZ4MID_hash4Ptr(_p), _idx) LZ4MID_addPosition(hash4Table, LZ4MID_hash4Ptr(_p), _idx)
639
640/* Fill hash tables with references into dictionary.
641 * The resulting table is only exploitable by LZ4MID (level 2) */
642static void
643LZ4MID_fillHTable (LZ4HC_CCtx_internal* cctx, const void* dict, size_t size)
644{
645 U32* const hash4Table = cctx->hashTable;
646 U32* const hash8Table = hash4Table + LZ4MID_HASHTABLESIZE(1 << (15 -1));
647 const BYTE* const prefixPtr = (const BYTE*)dict;
648 U32 const prefixIdx = cctx->dictLimit;
649 U32 const target = prefixIdx + (U32)size - LZ4MID_HASHSIZE8;
650 U32 idx = cctx->nextToUpdate;
651 assert(dict == cctx->prefixStart)((void)0);
652 DEBUGLOG(4, "LZ4MID_fillHTable (size:%zu)", size){};
653 if (size <= LZ4MID_HASHSIZE8)
654 return;
655
656 for (; idx < target; idx += 3) {
657 ADDPOS4(prefixPtr+idx-prefixIdx, idx)LZ4MID_addPosition(hash4Table, LZ4MID_hash4Ptr(prefixPtr+idx-
prefixIdx), idx);
658 ADDPOS8(prefixPtr+idx+1-prefixIdx, idx+1)LZ4MID_addPosition(hash8Table, LZ4MID_hash8Ptr(prefixPtr+idx+
1-prefixIdx), idx+1);
659 }
660
661 idx = (size > 32 KB*(1 <<10) + LZ4MID_HASHSIZE8) ? target - 32 KB*(1 <<10) : cctx->nextToUpdate;
662 for (; idx < target; idx += 1) {
663 ADDPOS8(prefixPtr+idx-prefixIdx, idx)LZ4MID_addPosition(hash8Table, LZ4MID_hash8Ptr(prefixPtr+idx-
prefixIdx), idx);
664 }
665
666 cctx->nextToUpdate = target;
667}
668
669static LZ4MID_searchIntoDict_f select_searchDict_function(const LZ4HC_CCtx_internal* dictCtx)
670{
671 if (dictCtx == NULL((void*)0)) return NULL((void*)0);
672 if (LZ4HC_getCLevelParams(dictCtx->compressionLevel).strat == lz4mid)
673 return LZ4MID_searchExtDict;
674 return LZ4MID_searchHCDict;
675}
676
677/* Length of the match between @ip and the candidate at index @pos (in prefix or extDict),
678 * or 0 if the candidate is out of reach */
679LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) unsigned
680LZ4MID_countMatch(const BYTE* ip, U32 ipIndex, U32 pos, const BYTE* matchlimit,
681 const BYTE* prefixPtr, U32 prefixIdx,
682 const BYTE* dictStart, U32 dictIdx)
683{
684 if (ipIndex - pos > LZ4_DISTANCE_MAX65535) return 0;
685 if (pos >= prefixIdx) {
686 const BYTE* const matchPtr = prefixPtr + (pos - prefixIdx);
687 assert(matchPtr < ip)((void)0);
688 return LZ4_count(ip, matchPtr, matchlimit);
689 }
690 if (pos >= dictIdx) {
691 /* extDict : the match stops at the end of the dictionary */
692 const BYTE* const matchPtr = dictStart + (pos - dictIdx);
693 size_t const safeLen = MIN(prefixIdx - pos, (size_t)(matchlimit - ip))( (prefixIdx - pos) < ((size_t)(matchlimit - ip)) ? (prefixIdx
- pos) : ((size_t)(matchlimit - ip)) );
694 return LZ4_count(ip, matchPtr, ip + safeLen);
695 }
696 return 0;
697}
698
699/* preconditions:
700 * - *srcSizePtr within [1, LZ4_MAX_INPUT_SIZE]
701 * - src is valid
702 * - maxOutputSize >= 1
703 * - dst is valid
704 */
705static int LZ4MID_compress (
706 LZ4HC_CCtx_internal* const ctx,
707 const char* const src,
708 char* const dst,
709 int* srcSizePtr,
710 int const maxOutputSize,
711 const limitedOutput_directive limit,
712 const dictCtx_directive dict
713 )
714{
715 U32* const hash4Table = ctx->hashTable;
716 U32* const hash8Table = hash4Table + LZ4MID_HASHTABLESIZE(1 << (15 -1));
717 const BYTE* ip = (const BYTE*)src;
718 const BYTE* anchor = ip;
719 const BYTE* const iend = ip + *srcSizePtr;
720 const BYTE* mflimit; /* set after the size check : would precede a small input */
721 const BYTE* matchlimit;
722 const BYTE* ilimit;
723 BYTE* op = (BYTE*)dst;
724 /* fillOutput : keep room for the final run of literals (LZ4 format restriction) */
725 BYTE* const oend = op + maxOutputSize - ((limit == fillOutput) ? LASTLITERALS5 : 0);
726
727 const BYTE* const prefixPtr = ctx->prefixStart;
728 const U32 prefixIdx = ctx->dictLimit;
729 U32 ilimitIdx;
730 const BYTE* const dictStart = ctx->dictStart;
731 const U32 dictIdx = ctx->lowLimit;
732 const U32 gDictEndIndex = ctx->lowLimit;
733 const LZ4MID_searchIntoDict_f searchIntoDict = (dict == usingDictCtxHc) ? select_searchDict_function(ctx->dictCtx) : NULL((void*)0);
734 const BYTE* refEnd = ip; /* fillOutput : the hash tables reference positions before MAX(refEnd, ip) */
735
736 DEBUGLOG(5, "LZ4MID_compress (%i bytes)", *srcSizePtr){};
737
738 /* preconditions verifications */
739 if (dict == usingDictCtxHc) DEBUGLOG(5, "usingDictCtxHc"){};
740 assert(*srcSizePtr > 0)((void)0);
741 assert(*srcSizePtr <= LZ4_MAX_INPUT_SIZE)((void)0);
742 assert(src != NULL)((void)0);
743 assert(maxOutputSize >= 1)((void)0);
744 assert(dst != NULL)((void)0);
745
746 if (*srcSizePtr < LZ4_minLength)
747 goto _lz4mid_last_literals; /* Input too small, no compression (all literals) */
748 mflimit = iend - MFLIMIT12;
749 matchlimit = (iend - LASTLITERALS5);
750 ilimit = (iend - LZ4MID_HASHSIZE8);
751 ilimitIdx = (U32)(ilimit - prefixPtr) + prefixIdx;
752
753 /* main loop */
754 while (ip <= mflimit) {
755 const U32 ipIndex = (U32)(ip - prefixPtr) + prefixIdx;
756 unsigned matchLength;
757 unsigned matchDistance;
758 /* search long match */
759 { U32 const h8 = LZ4MID_hash8Ptr(ip);
760 U32 const pos8 = hash8Table[h8];
761 assert(h8 < LZ4MID_HASHTABLESIZE)((void)0);
762 assert(pos8 < ipIndex)((void)0);
763 LZ4MID_addPosition(hash8Table, h8, ipIndex);
764 matchLength = LZ4MID_countMatch(ip, ipIndex, pos8, matchlimit, prefixPtr, prefixIdx, dictStart, dictIdx);
765 matchDistance = ipIndex - pos8;
766 }
767 /* search short match */
768 if (matchLength < MINMATCH4) {
769 U32 const h4 = LZ4MID_hash4Ptr(ip);
770 U32 const pos4 = hash4Table[h4];
771 assert(h4 < LZ4MID_HASHTABLESIZE)((void)0);
772 assert(pos4 < ipIndex)((void)0);
773 LZ4MID_addPosition(hash4Table, h4, ipIndex);
774 matchLength = LZ4MID_countMatch(ip, ipIndex, pos4, matchlimit, prefixPtr, prefixIdx, dictStart, dictIdx);
775 matchDistance = ipIndex - pos4;
776 }
777 if (matchLength >= MINMATCH4) {
778 if ((matchLength < 8) && likely(ip < mflimit)(__builtin_expect (((ip < mflimit) != 0),(1)) )) {
779 /* short match : check ip+1 for longer, except ip itself */
780 U32 const h8 = LZ4MID_hash8Ptr(ip+1);
781 U32 const pos8 = hash8Table[h8];
782 unsigned const ml2 = LZ4MID_countMatch(ip+1, ipIndex+1, pos8, matchlimit, prefixPtr, prefixIdx, dictStart, dictIdx);
783 if ((ml2 > matchLength) && (pos8 != ipIndex)) {
784 LZ4MID_addPosition(hash8Table, h8, ipIndex+1);
785 ip++;
786 matchLength = ml2;
787 matchDistance = ipIndex + 1 - pos8;
788 } }
789 goto _lz4mid_encode_sequence;
790 }
791 /* no match found in prefix nor extDict : search into the attached dictionary */
792 if ( (dict == usingDictCtxHc)
793 && (ipIndex - gDictEndIndex < LZ4_DISTANCE_MAX65535 - 8) ) {
794 LZ4HC_match_t const dMatch = searchIntoDict(ip, ipIndex,
795 matchlimit,
796 ctx->dictCtx, gDictEndIndex);
797 assert(dMatch.back == 0)((void)0);
798 matchLength = (unsigned)dMatch.len;
799 matchDistance = (unsigned)dMatch.off;
800 if (matchLength >= MINMATCH4) goto _lz4mid_encode_sequence;
801 }
802 /* no match found */
803 ip += 1 + ((ip-anchor) >> 9); /* skip faster over incompressible data */
804 continue;
805
806_lz4mid_encode_sequence:
807 /* match found at ip : matchLength, matchDistance */
808 DEBUGLOG(7, "found match at pos %u (len=%u, distance=%u)",{}
809 (U32)(ip - prefixPtr) + prefixIdx, matchLength, matchDistance){};
810
811 /* catch back */
812 while (((ip > anchor) & ((U32)(ip-prefixPtr) > matchDistance)) && (unlikely(ip[-1] == ip[-(int)matchDistance-1])(__builtin_expect (((ip[-1] == ip[-(int)matchDistance-1]) != 0
),(0)) ))) {
813 ip--; matchLength++;
814 };
815
816 /* fill table with beginning of match
817 * note : ip may have moved since ipIndex (longer match at ip+1, catch back) */
818 { U32 const startMatchIdx = (U32)(ip-prefixPtr) + prefixIdx;
819 ADDPOS8(ip+1, startMatchIdx+1)LZ4MID_addPosition(hash8Table, LZ4MID_hash8Ptr(ip+1), startMatchIdx
+1);
820 ADDPOS8(ip+2, startMatchIdx+2)LZ4MID_addPosition(hash8Table, LZ4MID_hash8Ptr(ip+2), startMatchIdx
+2);
821 ADDPOS4(ip+1, startMatchIdx+1)LZ4MID_addPosition(hash4Table, LZ4MID_hash4Ptr(ip+1), startMatchIdx
+1);
822 }
823
824 /* encode */
825 if (LZ4HC_encodeSequence(UPDATABLE(ip, op, anchor)&ip, &op, &anchor,
826 (int)matchLength, (int)matchDistance,
827 limit, oend) ) {
828 if (limit != fillOutput) return 0; /* compression failed */
829 refEnd = ip + matchLength;
830 LZ4HC_encodeLastSequence_fillOutput(UPDATABLE(ip, op, anchor)&ip, &op, &anchor,
831 (int)matchLength, (int)matchDistance, oend);
832 break;
833 }
834
835 /* fill table with end of match */
836 { U32 endMatchIdx = (U32)(ip-prefixPtr) + prefixIdx;
837 U32 pos_m2 = endMatchIdx - 2;
838 if (pos_m2 < ilimitIdx) {
839 if (likely(ip - prefixPtr > 5)(__builtin_expect (((ip - prefixPtr > 5) != 0),(1)) )) {
840 ADDPOS8(ip-5, endMatchIdx - 5)LZ4MID_addPosition(hash8Table, LZ4MID_hash8Ptr(ip-5), endMatchIdx
- 5);
841 }
842 ADDPOS8(ip-3, endMatchIdx - 3)LZ4MID_addPosition(hash8Table, LZ4MID_hash8Ptr(ip-3), endMatchIdx
- 3);
843 ADDPOS8(ip-2, endMatchIdx - 2)LZ4MID_addPosition(hash8Table, LZ4MID_hash8Ptr(ip-2), endMatchIdx
- 2);
844 ADDPOS4(ip-2, endMatchIdx - 2)LZ4MID_addPosition(hash4Table, LZ4MID_hash4Ptr(ip-2), endMatchIdx
- 2);
845 ADDPOS4(ip-1, endMatchIdx - 1)LZ4MID_addPosition(hash4Table, LZ4MID_hash4Ptr(ip-1), endMatchIdx
- 1);
846 }
847 }
848 }
849
850_lz4mid_last_literals:
851 if (refEnd < ip) refEnd = ip;
852 if (LZ4HC_encodeLastLiterals(UPDATABLE(ip, op, anchor)&ip, &op, &anchor, iend, limit, oend))
853 return 0; /* not enough space in @dst */
854 if (ip < refEnd) /* fillOutput : the rest of input is left to the next block (input >= LZ4_minLength) */
855 LZ4HC_dropPositions(ctx, ip, MIN(refEnd, iend - LZ4MID_HASHSIZE)( (refEnd) < (iend - 8) ? (refEnd) : (iend - 8) ), lz4mid);
856
857 /* End */
858 DEBUGLOG(5, "compressed %i bytes into %i bytes", *srcSizePtr, (int)((char*)op - dst)){};
859 assert(ip >= (const BYTE*)src)((void)0);
860 assert(ip <= iend)((void)0);
861 *srcSizePtr = (int)(ip - (const BYTE*)src);
862 assert((char*)op >= dst)((void)0);
863 assert((char*)op - dst <= maxOutputSize)((void)0);
864 assert((char*)op - dst < INT_MAX)((void)0);
865 return (int)((char*)op - dst);
866}
867
868
869/**************************************
870* HC Compression - Search
871**************************************/
872
873/* Update chains up to ip (excluded) */
874LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) void LZ4HC_Insert (LZ4HC_CCtx_internal* hc4, const BYTE* ip)
875{
876 U16* const chainTable = hc4->chainTable;
877 U32* const hashTable = hc4->hashTable;
878 const BYTE* const prefixPtr = hc4->prefixStart;
879 U32 const prefixIdx = hc4->dictLimit;
880 U32 const target = (U32)(ip - prefixPtr) + prefixIdx;
881 U32 idx = hc4->nextToUpdate;
882 assert(ip >= prefixPtr)((void)0);
883 assert(target >= prefixIdx)((void)0);
884
885 while (idx < target) {
886 U32 const h = LZ4HC_hashPtr(prefixPtr+idx-prefixIdx);
887 size_t delta = idx - hashTable[h];
888 if (delta>LZ4_DISTANCE_MAX65535) delta = LZ4_DISTANCE_MAX65535;
889 DELTANEXTU16(chainTable, idx)chainTable[(U16)(idx)] = (U16)delta;
890 hashTable[h] = idx;
891 idx++;
892 }
893
894 hc4->nextToUpdate = target;
895}
896
897#if defined(_MSC_VER)
898# define LZ4HC_rotl32(x,r)((x << r) | (x >> (32 - r))) _rotl(x,r)
899#else
900# define LZ4HC_rotl32(x,r)((x << r) | (x >> (32 - r))) ((x << r) | (x >> (32 - r)))
901#endif
902
903
904static U32 LZ4HC_rotatePattern(size_t const rotate, U32 const pattern)
905{
906 size_t const bitsToRotate = (rotate & (sizeof(pattern) - 1)) << 3;
907 if (bitsToRotate == 0) return pattern;
908 return LZ4HC_rotl32(pattern, (int)bitsToRotate)((pattern << (int)bitsToRotate) | (pattern >> (32
- (int)bitsToRotate)));
909}
910
911/* LZ4HC_countPattern() :
912 * pattern32 must be a sample of repetitive pattern of length 1, 2 or 4 (but not 3!) */
913static unsigned
914LZ4HC_countPattern(const BYTE* ip, const BYTE* const iEnd, U32 const pattern32)
915{
916 const BYTE* const iStart = ip;
917 reg_t const pattern = (sizeof(pattern)==8) ?
918 (reg_t)pattern32 + (((reg_t)pattern32) << (sizeof(pattern)*4)) : pattern32;
919
920 while (likely(ip < iEnd-(sizeof(pattern)-1))(__builtin_expect (((ip < iEnd-(sizeof(pattern)-1)) != 0),
(1)) )) {
921 reg_t const diff = LZ4_read_ARCH(ip) ^ pattern;
922 if (!diff) { ip+=sizeof(pattern); continue; }
923 ip += LZ4_NbCommonBytes(diff);
924 return (unsigned)(ip - iStart);
925 }
926
927 if (LZ4_isLittleEndian()) {
928 reg_t patternByte = pattern;
929 while ((ip<iEnd) && (*ip == (BYTE)patternByte)) {
930 ip++; patternByte >>= 8;
931 }
932 } else { /* big endian */
933 U32 bitOffset = (sizeof(pattern)*8) - 8;
934 while (ip < iEnd) {
935 BYTE const byte = (BYTE)(pattern >> bitOffset);
936 if (*ip != byte) break;
937 ip ++; bitOffset -= 8;
938 } }
939
940 return (unsigned)(ip - iStart);
941}
942
943/* LZ4HC_reverseCountPattern() :
944 * pattern must be a sample of repetitive pattern of length 1, 2 or 4 (but not 3!)
945 * read using natural platform endianness */
946static unsigned
947LZ4HC_reverseCountPattern(const BYTE* ip, const BYTE* const iLow, U32 pattern)
948{
949 const BYTE* const iStart = ip;
950
951 while (likely(ip >= iLow+4)(__builtin_expect (((ip >= iLow+4) != 0),(1)) )) {
952 if (LZ4_read32(ip-4) != pattern) break;
953 ip -= 4;
954 }
955 { const BYTE* bytePtr = (const BYTE*)(&pattern) + 3; /* works for any endianness */
956 while (likely(ip>iLow)(__builtin_expect (((ip>iLow) != 0),(1)) )) {
957 if (ip[-1] != *bytePtr) break;
958 ip--; bytePtr--;
959 } }
960 return (unsigned)(iStart - ip);
961}
962
963/* LZ4HC_protectDictEnd() :
964 * Checks if the match is in the last 3 bytes of the dictionary, so reading the
965 * 4 byte MINMATCH would overflow.
966 * @returns true if the match index is okay.
967 */
968static int LZ4HC_protectDictEnd(U32 const dictLimit, U32 const matchIndex)
969{
970 return ((U32)((dictLimit - 1) - matchIndex) >= 3);
971}
972
973typedef enum { rep_untested, rep_not, rep_confirmed } repeat_state_e;
974
975/* LZ4HC_sparsestChain() :
976 * A longer match must also match at every position of the current one (at @matchIndex, @longest bytes).
977 * Finds, among these positions, the chain jumping farthest back (sampled, with acceleration).
978 * @return : distance to the next candidate of that chain (1 if none is better),
979 * *matchChainPosPtr is set to its position within the match, if better */
980LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) U32
981LZ4HC_sparsestChain(const U16* chainTable, U32 matchIndex, int longest, U32* matchChainPosPtr)
982{
983 int const kTrigger = 4;
984 U32 distanceToNextMatch = 1;
985 int const end = longest - MINMATCH4 + 1;
986 int step = 1;
987 int accel = 1 << kTrigger;
988 int pos;
989 for (pos = 0; pos < end; pos += step) {
990 U32 const candidateDist = DELTANEXTU16(chainTable, matchIndex + (U32)pos)chainTable[(U16)(matchIndex + (U32)pos)];
991 step = (accel++ >> kTrigger);
992 if (candidateDist > distanceToNextMatch) {
993 distanceToNextMatch = candidateDist;
994 *matchChainPosPtr = (U32)pos;
995 accel = 1 << kTrigger;
996 } }
997 return distanceToNextMatch;
998}
999
1000/* LZ4HC_patternSegment() :
1001 * Measures the run of @pattern (a repeated byte, or 2 alternating bytes) around @candidateIdx,
1002 * across the external dictionary / prefix boundary, without going below @lowestMatchIndex.
1003 * @return : 0 if @pattern isn't present at @candidateIdx,
1004 * 1 otherwise, with *forwardPtr bytes from @candidateIdx (included) and *backPtr bytes before it */
1005LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) int
1006LZ4HC_patternSegment(const LZ4HC_CCtx_internal* hc4, U32 candidateIdx, U32 pattern,
1007 const BYTE* iHighLimit, U32 lowestMatchIndex,
1008 size_t* forwardPtr, size_t* backPtr)
1009{
1010 const BYTE* const prefixPtr = hc4->prefixStart;
1011 U32 const prefixIdx = hc4->dictLimit;
1012 const BYTE* const dictStart = hc4->dictStart;
1013 U32 const dictIdx = hc4->lowLimit;
1014 const BYTE* const dictEnd = dictStart + prefixIdx - dictIdx;
1015 int const extDict = candidateIdx < prefixIdx;
1016 const BYTE* const matchPtr = extDict ? dictStart + (candidateIdx - dictIdx) : prefixPtr + (candidateIdx - prefixIdx);
1017 size_t forward, back;
1018 if (LZ4_read32(matchPtr) != pattern) return 0;
1019
1020 { const BYTE* const iLimit = extDict ? dictEnd : iHighLimit;
1021 forward = LZ4HC_countPattern(matchPtr+sizeof(pattern), iLimit, pattern) + sizeof(pattern);
1022 if (extDict && matchPtr + forward == iLimit) { /* continues into the prefix */
1023 U32 const rotatedPattern = LZ4HC_rotatePattern(forward, pattern);
1024 forward += LZ4HC_countPattern(prefixPtr, iHighLimit, rotatedPattern);
1025 } }
1026
1027 back = LZ4HC_reverseCountPattern(matchPtr, extDict ? dictStart : prefixPtr, pattern);
1028 if (!extDict && matchPtr - back == prefixPtr && dictIdx < prefixIdx) { /* continues into the external dictionary */
1029 U32 const rotatedPattern = LZ4HC_rotatePattern((U32)(-(int)back), pattern);
1030 back += LZ4HC_reverseCountPattern(dictEnd, dictStart, rotatedPattern);
1031 }
1032 /* don't go below lowestMatchIndex */
1033 back = candidateIdx - MAX(candidateIdx - (U32)back, lowestMatchIndex)( (candidateIdx - (U32)back) > (lowestMatchIndex) ? (candidateIdx
- (U32)back) : (lowestMatchIndex) );
1034 assert(candidateIdx - back >= lowestMatchIndex)((void)0);
1035
1036 *forwardPtr = forward;
1037 *backPtr = back;
1038 return 1;
1039}
1040typedef enum { favorCompressionRatio=0, favorDecompressionSpeed } HCfavor_e;
1041
1042
1043LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) LZ4HC_match_t
1044LZ4HC_InsertAndGetWiderMatch (
1045 LZ4HC_CCtx_internal* const hc4,
1046 const BYTE* const ip,
1047 const BYTE* const iLowLimit, const BYTE* const iHighLimit,
1048 int longest,
1049 const int maxNbAttempts,
1050 const int patternAnalysis, const int chainSwap,
1051 const dictCtx_directive dict,
1052 const HCfavor_e favorDecSpeed)
1053{
1054 U16* const chainTable = hc4->chainTable;
1055 U32* const hashTable = hc4->hashTable;
1056 const LZ4HC_CCtx_internal* const dictCtx = hc4->dictCtx;
1057 const BYTE* const prefixPtr = hc4->prefixStart;
1058 const U32 prefixIdx = hc4->dictLimit;
1059 const U32 ipIndex = (U32)(ip - prefixPtr) + prefixIdx;
1060 const int withinStartDistance = (hc4->lowLimit + (LZ4_DISTANCE_MAX65535 + 1) > ipIndex);
1061 const U32 lowestMatchIndex = (withinStartDistance) ? hc4->lowLimit : ipIndex - LZ4_DISTANCE_MAX65535;
1062 const BYTE* const dictStart = hc4->dictStart;
1063 const U32 dictIdx = hc4->lowLimit;
1064 int const lookBackLength = (int)(ip-iLowLimit);
1065 int const maxLength = (int)(iHighLimit-iLowLimit); /* no match can be longer */
1066 int nbAttempts = maxNbAttempts;
1067 U32 matchChainPos = 0;
1068 U32 const pattern = LZ4_read32(ip);
1069 U32 matchIndex;
1070 repeat_state_e repeat = rep_untested;
1071 size_t srcPatternLength = 0;
1072 int offset = 0, sBack = 0;
1073
1074 DEBUGLOG(7, "LZ4HC_InsertAndGetWiderMatch"){};
1075 /* First Match */
1076 LZ4HC_Insert(hc4, ip); /* insert all prior positions up to ip (excluded) */
1077 matchIndex = hashTable[LZ4HC_hashPtr(ip)];
1078 DEBUGLOG(7, "First candidate match for pos %u found at index %u / %u (lowestMatchIndex)",{}
1079 ipIndex, matchIndex, lowestMatchIndex){};
1080
1081 /* Candidates only replace the current match if strictly longer,
1082 * so stopping once @longest reaches @maxLength doesn't change the result. */
1083 while ((matchIndex>=lowestMatchIndex) && (nbAttempts>0) && (longest<maxLength)) {
1084 int matchLength=0;
1085 nbAttempts--;
1086 assert(matchIndex < ipIndex)((void)0);
1087 if (favorDecSpeed && (ipIndex - matchIndex < 8)) {
1088 /* do nothing:
1089 * favorDecSpeed intentionally skips matches with offset < 8 */
1090 } else if (matchIndex >= prefixIdx) { /* within current Prefix */
1091 const BYTE* const matchPtr = prefixPtr + (matchIndex - prefixIdx);
1092 assert(matchPtr < ip)((void)0);
1093 assert(longest >= 1)((void)0);
1094 if (LZ4_read16(iLowLimit + longest - 1) == LZ4_read16(matchPtr - lookBackLength + longest - 1)) {
1095 if (LZ4_read32(matchPtr) == pattern) {
1096 int const back = lookBackLength ? LZ4HC_countBack(ip, matchPtr, iLowLimit, prefixPtr) : 0;
1097 matchLength = MINMATCH4 + (int)LZ4_count(ip+MINMATCH4, matchPtr+MINMATCH4, iHighLimit);
1098 matchLength -= back;
1099 if (matchLength > longest) {
1100 longest = matchLength;
1101 offset = (int)(ipIndex - matchIndex);
1102 sBack = back;
1103 DEBUGLOG(7, "Found match of len=%i within prefix, offset=%i, back=%i", longest, offset, -back){};
1104 HEX_CMP(7, ip + back, ip + back - offset, (size_t)matchLength);
1105 } } }
1106 } else { /* lowestMatchIndex <= matchIndex < dictLimit : within Ext Dict */
1107 const BYTE* const matchPtr = dictStart + (matchIndex - dictIdx);
1108 assert(matchIndex >= dictIdx)((void)0);
1109 if ( likely(matchIndex <= prefixIdx - 4)(__builtin_expect (((matchIndex <= prefixIdx - 4) != 0),(1
)) )
1110 && (LZ4_read32(matchPtr) == pattern) ) {
1111 int back = 0;
1112 const BYTE* vLimit = ip + (prefixIdx - matchIndex);
1113 if (vLimit > iHighLimit) vLimit = iHighLimit;
1114 matchLength = (int)LZ4_count(ip+MINMATCH4, matchPtr+MINMATCH4, vLimit) + MINMATCH4;
1115 if ((ip+matchLength == vLimit) && (vLimit < iHighLimit))
1116 matchLength += LZ4_count(ip+matchLength, prefixPtr, iHighLimit);
1117 back = lookBackLength ? LZ4HC_countBack(ip, matchPtr, iLowLimit, dictStart) : 0;
1118 matchLength -= back;
1119 if (matchLength > longest) {
1120 longest = matchLength;
1121 offset = (int)(ipIndex - matchIndex);
1122 sBack = back;
1123 DEBUGLOG(7, "Found match of len=%i within dict, offset=%i, back=%i", longest, offset, -back){};
1124 HEX_CMP(7, ip + back, matchPtr + back, (size_t)matchLength);
1125 } } }
1126
1127 if (chainSwap && matchLength==longest && matchIndex + (U32)longest <= ipIndex) { /* better match => select a better chain */
1128 U32 const distanceToNextMatch = LZ4HC_sparsestChain(chainTable, matchIndex, longest, &matchChainPos);
1129 assert(lookBackLength==0)((void)0); /* search forward only */
1130 if (distanceToNextMatch > 1) {
1131 if (distanceToNextMatch > matchIndex) break; /* avoid overflow */
1132 matchIndex -= distanceToNextMatch;
1133 continue;
1134 } }
1135
1136 { U32 const distNextMatch = DELTANEXTU16(chainTable, matchIndex)chainTable[(U16)(matchIndex)];
1137 if (patternAnalysis && distNextMatch==1 && matchChainPos==0) {
1138 U32 const matchCandidateIdx = matchIndex-1;
1139 size_t forwardPatternLength, backLength;
1140 /* may be a repeated pattern */
1141 if (repeat == rep_untested) {
1142 if ( ((pattern & 0xFFFF) == (pattern >> 16))
1143 & ((pattern & 0xFF) == (pattern >> 24)) ) {
1144 DEBUGLOG(7, "Repeat pattern detected, char %02X", pattern >> 24){};
1145 repeat = rep_confirmed;
1146 srcPatternLength = LZ4HC_countPattern(ip+sizeof(pattern), iHighLimit, pattern) + sizeof(pattern);
1147 } else {
1148 repeat = rep_not;
1149 } }
1150 if ( (repeat == rep_confirmed) && (matchCandidateIdx >= lowestMatchIndex)
1151 && LZ4HC_protectDictEnd(prefixIdx, matchCandidateIdx)
1152 && LZ4HC_patternSegment(hc4, matchCandidateIdx, pattern, iHighLimit, lowestMatchIndex,
1153 &forwardPatternLength, &backLength) ) {
1154 size_t const currentSegmentLength = backLength + forwardPatternLength;
1155 /* if the full source pattern fits (and hasn't been reached yet), jump to its best position :
1156 * at the end of the segment, it might be followed by more match.
1157 * Otherwise, jump to the farthest position in the segment : the longest match, plus maybe some back */
1158 int const fullPatternFits = (currentSegmentLength >= srcPatternLength)
1159 && (forwardPatternLength <= srcPatternLength);
1160 U32 const newMatchIndex = fullPatternFits ?
1161 matchCandidateIdx + (U32)forwardPatternLength - (U32)srcPatternLength :
1162 matchCandidateIdx - (U32)backLength;
1163 if (!LZ4HC_protectDictEnd(prefixIdx, newMatchIndex)) {
1164 /* Can only happen if started in the prefix */
1165 assert(newMatchIndex >= prefixIdx - 3 && newMatchIndex < prefixIdx && matchCandidateIdx >= prefixIdx)((void)0);
1166 matchIndex = prefixIdx;
1167 continue;
1168 }
1169 matchIndex = newMatchIndex;
1170 if (!fullPatternFits && lookBackLength==0) { /* no back possible : the match length is known */
1171 size_t const maxML = MIN(currentSegmentLength, srcPatternLength)( (currentSegmentLength) < (srcPatternLength) ? (currentSegmentLength
) : (srcPatternLength) );
1172 if ((size_t)longest < maxML) {
1173 assert(prefixPtr - prefixIdx + matchIndex != ip)((void)0);
1174 if ((size_t)(ip - prefixPtr) + prefixIdx - matchIndex > LZ4_DISTANCE_MAX65535) break;
1175 assert(maxML < 2 GB)((void)0);
1176 longest = (int)maxML;
1177 offset = (int)(ipIndex - matchIndex);
1178 assert(sBack == 0)((void)0);
1179 DEBUGLOG(7, "Found repeat pattern match of len=%i, offset=%i", longest, offset){};
1180 }
1181 { U32 const distToNextPattern = DELTANEXTU16(chainTable, matchIndex)chainTable[(U16)(matchIndex)];
1182 if (distToNextPattern > matchIndex) break; /* avoid overflow */
1183 matchIndex -= distToNextPattern;
1184 } }
1185 continue;
1186 }
1187 } } /* PA optimization */
1188
1189 /* follow current chain */
1190 matchIndex -= DELTANEXTU16(chainTable, matchIndex + matchChainPos)chainTable[(U16)(matchIndex + matchChainPos)];
1191
1192 } /* while ((matchIndex>=lowestMatchIndex) && (nbAttempts)) */
1193
1194 if ( dict == usingDictCtxHc
1195 && nbAttempts > 0
1196 && longest < maxLength
1197 && withinStartDistance) {
1198 size_t const dictEndOffset = (size_t)(dictCtx->end - dictCtx->prefixStart) + dictCtx->dictLimit;
1199 U32 dictMatchIndex = dictCtx->hashTable[LZ4HC_hashPtr(ip)];
1200 assert(dictEndOffset <= 1 GB)((void)0);
1201 matchIndex = dictMatchIndex + lowestMatchIndex - (U32)dictEndOffset;
1202 if (dictMatchIndex>0) DEBUGLOG(7, "dictEndOffset = %zu, dictMatchIndex = %u => relative matchIndex = %i", dictEndOffset, dictMatchIndex, (int)dictMatchIndex - (int)dictEndOffset){};
1203 while (ipIndex - matchIndex <= LZ4_DISTANCE_MAX65535 && longest < maxLength && nbAttempts--) {
1204 const BYTE* const matchPtr = dictCtx->prefixStart - dictCtx->dictLimit + dictMatchIndex;
1205
1206 if (LZ4_read32(matchPtr) == pattern) {
1207 int mlt;
1208 int back = 0;
1209 const BYTE* vLimit = ip + (dictEndOffset - dictMatchIndex);
1210 if (vLimit > iHighLimit) vLimit = iHighLimit;
1211 mlt = (int)LZ4_count(ip+MINMATCH4, matchPtr+MINMATCH4, vLimit) + MINMATCH4;
1212 back = lookBackLength ? LZ4HC_countBack(ip, matchPtr, iLowLimit, dictCtx->prefixStart) : 0;
1213 mlt -= back;
1214 if (mlt > longest) {
1215 longest = mlt;
1216 offset = (int)(ipIndex - matchIndex);
1217 sBack = back;
1218 DEBUGLOG(7, "found match of length %i within extDictCtx", longest){};
1219 } }
1220
1221 { U32 const nextOffset = DELTANEXTU16(dictCtx->chainTable, dictMatchIndex)dictCtx->chainTable[(U16)(dictMatchIndex)];
1222 dictMatchIndex -= nextOffset;
1223 matchIndex -= nextOffset;
1224 } } }
1225
1226 { LZ4HC_match_t md;
1227 assert(longest >= 0)((void)0);
1228 md.len = longest;
1229 md.off = offset;
1230 md.back = sBack;
1231 return md;
1232 }
1233}
1234
1235LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) LZ4HC_match_t
1236LZ4HC_InsertAndFindBestMatch(LZ4HC_CCtx_internal* const hc4, /* Index table will be updated */
1237 const BYTE* const ip, const BYTE* const iLimit,
1238 const int maxNbAttempts,
1239 const int patternAnalysis,
1240 const dictCtx_directive dict)
1241{
1242 DEBUGLOG(7, "LZ4HC_InsertAndFindBestMatch"){};
1243 /* note : LZ4HC_InsertAndGetWiderMatch() is able to modify the starting position of a match (*startpos),
1244 * but this won't be the case here, as we define iLowLimit==ip,
1245 * so LZ4HC_InsertAndGetWiderMatch() won't be allowed to search past ip */
1246 return LZ4HC_InsertAndGetWiderMatch(hc4, ip, ip, iLimit, MINMATCH4-1, maxNbAttempts, patternAnalysis, 0 /*chainSwap*/, dict, favorCompressionRatio);
1247}
1248
1249
1250/* preconditions:
1251 * - *srcSizePtr within [1, LZ4_MAX_INPUT_SIZE]
1252 * - src is valid
1253 * - maxOutputSize >= 1
1254 * - dst is valid
1255 */
1256LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) int LZ4HC_compress_hashChain (
1257 LZ4HC_CCtx_internal* const ctx,
1258 const char* const src,
1259 char* const dst,
1260 int* srcSizePtr,
1261 int const maxOutputSize,
1262 int maxNbAttempts,
1263 const limitedOutput_directive limit,
1264 const dictCtx_directive dict
1265 )
1266{
1267 const int inputSize = *srcSizePtr;
1268 const int patternAnalysis = (maxNbAttempts > 128); /* levels 9+ */
1269
1270 const BYTE* ip = (const BYTE*)src;
1271 const BYTE* anchor = ip;
1272 const BYTE* const iend = ip + inputSize;
1273 const BYTE* mflimit; /* set after the size check : would precede a small input */
1274 const BYTE* matchlimit;
1275
1276 BYTE* op = (BYTE*) dst;
1277 /* fillOutput : keep room for the final run of literals (LZ4 format restriction) */
1278 BYTE* const oend = op + maxOutputSize - ((limit == fillOutput) ? LASTLITERALS5 : 0);
1279
1280 const BYTE* start0;
1281 const BYTE* start2 = NULL((void*)0);
1282 const BYTE* start3 = NULL((void*)0);
1283 LZ4HC_match_t m0, m1, m2, m3;
1284 const LZ4HC_match_t nomatch = {0, 0, 0};
1285
1286 /* init */
1287 DEBUGLOG(5, "LZ4HC_compress_hashChain (dict?=>%i)", dict){};
1288
1289 /* preconditions verifications */
1290 assert(*srcSizePtr >= 1)((void)0);
1291 assert(src != NULL)((void)0);
1292 assert(maxOutputSize >= 1)((void)0);
1293 assert(dst != NULL)((void)0);
1294
1295 *srcSizePtr = 0;
1296 if (inputSize < LZ4_minLength) goto _last_literals; /* Input too small, no compression (all literals) */
1297 mflimit = iend - MFLIMIT12;
1298 matchlimit = (iend - LASTLITERALS5);
1299
1300 /* Main Loop */
1301 while (ip <= mflimit) {
1302 m1 = LZ4HC_InsertAndFindBestMatch(ctx, ip, matchlimit, maxNbAttempts, patternAnalysis, dict);
1303 if (m1.len<MINMATCH4) { ip++; continue; }
1304
1305 /* saved, in case we would skip too much */
1306 start0 = ip; m0 = m1;
1307
1308_Search2:
1309 /* m1 (at ip) is the next match to encode, m0 (at start0 <= ip) its fallback.
1310 * Search a longer match m2, starting before the end of m1. */
1311 DEBUGLOG(7, "_Search2 (currently found match of size %i)", m1.len){};
1312 if (ip+m1.len <= mflimit) {
1313 start2 = ip + m1.len - 2;
1314 m2 = LZ4HC_InsertAndGetWiderMatch(ctx,
1315 start2, ip + 0, matchlimit, m1.len,
1316 maxNbAttempts, patternAnalysis, 0, dict, favorCompressionRatio);
1317 start2 += m2.back;
1318 } else {
1319 m2 = nomatch; /* do not search further */
1320 }
1321
1322 if (m2.len <= m1.len) { /* No better match => encode m1 immediately */
1323 if (LZ4HC_encodeSequence(UPDATABLE(ip, op, anchor)&ip, &op, &anchor,
1324 m1.len, m1.off,
1325 limit, oend) )
1326 goto _dest_overflow;
1327 continue;
1328 }
1329
1330 if ((start0 < ip) && (start2 < ip + m0.len)) {
1331 /* m1 was skipped at least once, and m2 starts early enough : restore m0 */
1332 ip = start0; m1 = m0;
1333 }
1334
1335 if ((start2 - ip) < 3) { /* m1 too short before m2 : removed */
1336 ip = start2;
1337 m1 = m2;
1338 goto _Search2;
1339 }
1340
1341 /* m2 (at start2) is the candidate after m1.
1342 * Search a longer match m3, starting before the end of m2. */
1343 while (1) {
1344 /* m1 will be cut where m2 starts, but keeps up to OPTIMAL_ML bytes (no extra length byte) :
1345 * m2 is shifted after them, as long as it keeps at least MINMATCH bytes. */
1346 if ((start2 - ip) < OPTIMAL_ML(int)((((1U<<4)-1)-1)+4)) {
1347 int const gap = (int)(start2 - ip);
1348 int newML = MIN(m1.len, OPTIMAL_ML)( (m1.len) < ((int)((((1U<<4)-1)-1)+4)) ? (m1.len) :
((int)((((1U<<4)-1)-1)+4)) );
1349 if (newML > gap + m2.len - MINMATCH4)
1350 newML = gap + m2.len - MINMATCH4;
1351 if (newML > gap) { /* shift m2 */
1352 start2 += newML - gap;
1353 m2.len -= newML - gap;
1354 }
1355 }
1356
1357 if (start2 + m2.len <= mflimit) {
1358 start3 = start2 + m2.len - 3;
1359 m3 = LZ4HC_InsertAndGetWiderMatch(ctx,
1360 start3, start2, matchlimit, m2.len,
1361 maxNbAttempts, patternAnalysis, 0, dict, favorCompressionRatio);
1362 start3 += m3.back;
1363 } else {
1364 m3 = nomatch; /* do not search further */
1365 }
1366
1367 if ((m3.len > m2.len) && (start3 < ip+m1.len+3)) { /* not enough room for m2 between m1 and m3 */
1368 if (start3 >= (ip+m1.len)) {
1369 /* m3 starts after m1 : encode m1, then m3 becomes m1,
1370 * and m2, moved after m1 if needed (replaced by m3 if too short), becomes the fallback m0 */
1371 if (start2 < ip+m1.len) {
1372 int correction = (int)(ip+m1.len - start2);
1373 start2 += correction;
1374 m2.len -= correction;
1375 if (m2.len < MINMATCH4) {
1376 start2 = start3;
1377 m2 = m3;
1378 }
1379 }
1380
1381 if (LZ4HC_encodeSequence(UPDATABLE(ip, op, anchor)&ip, &op, &anchor,
1382 m1.len, m1.off,
1383 limit, oend) )
1384 goto _dest_overflow;
1385 ip = start3;
1386 m1 = m3;
1387
1388 start0 = start2;
1389 m0 = m2;
1390 goto _Search2;
1391 }
1392
1393 /* m3 starts within m1 : m3 replaces m2 */
1394 start2 = start3;
1395 m2 = m3;
1396 continue;
1397 }
1398
1399 /* encode m1, cut where m2 starts */
1400 if (start2 < ip+m1.len) m1.len = (int)(start2 - ip);
1401 if (LZ4HC_encodeSequence(UPDATABLE(ip, op, anchor)&ip, &op, &anchor,
1402 m1.len, m1.off,
1403 limit, oend) )
1404 goto _dest_overflow;
1405
1406 /* m2 becomes m1 */
1407 ip = start2; m1 = m2;
1408
1409 if (m3.len <= m1.len) { /* No better match => encode m1 (former m2) */
1410 if (LZ4HC_encodeSequence(UPDATABLE(ip, op, anchor)&ip, &op, &anchor,
1411 m1.len, m1.off,
1412 limit, oend) )
1413 goto _dest_overflow;
1414 break;
1415 }
1416
1417 /* m3 becomes m2 */
1418 start2 = start3; m2 = m3;
1419 }
1420 }
1421
1422_last_literals:
1423 if (LZ4HC_encodeLastLiterals(UPDATABLE(ip, op, anchor)&ip, &op, &anchor, iend, limit, oend))
1424 return 0; /* not enough space in @dst */
1425
1426 /* End */
1427 *srcSizePtr = (int) (((const char*)ip) - src);
1428 return (int) (((char*)op)-dst);
1429
1430_dest_overflow:
1431 if (limit != fillOutput) return 0; /* compression failed */
1432 LZ4HC_encodeLastSequence_fillOutput(UPDATABLE(ip, op, anchor)&ip, &op, &anchor, m1.len, m1.off, oend);
1433 goto _last_literals;
1434}
1435
1436
1437static int LZ4HC_compress_optimal( LZ4HC_CCtx_internal* ctx,
1438 const char* const source, char* dst,
1439 int* srcSizePtr, int dstCapacity,
1440 int const nbSearches, int const nbSearchesSeq, int const targetLength,
1441 const limitedOutput_directive limit,
1442 const dictCtx_directive dict,
1443 const HCfavor_e favorDecSpeed);
1444
1445static int
1446LZ4HC_compress_generic_internal (
1447 LZ4HC_CCtx_internal* const ctx,
1448 const char* const src,
1449 char* const dst,
1450 int* const srcSizePtr,
1451 int const dstCapacity,
1452 int cLevel,
1453 const limitedOutput_directive limit,
1454 const dictCtx_directive dict
1455 )
1456{
1457 DEBUGLOG(5, "LZ4HC_compress_generic_internal(src=%p, srcSize=%d, dstCapacity=%d)",{}
1458 src, *srcSizePtr, dstCapacity){};
1459
1460 /* input sanitization */
1461 if ((U32)*srcSizePtr > (U32)LZ4_MAX_INPUT_SIZE0x7E000000) return 0; /* Unsupported input size (too large or negative) */
1462 if (dstCapacity < 1) return 0; /* Invalid: impossible to store anything */
1463 assert(dst)((void)0); /* since dstCapacity >= 1, dst must be valid */
1464 if (*srcSizePtr == 0) { *dst = 0; return 1; }
1465 assert(src != NULL)((void)0); /* since *srcSizePtr >= 1, src must be valid */
1466
1467 ctx->end += *srcSizePtr;
1468 { cParams_t const cParam = LZ4HC_getCLevelParams(cLevel);
1469 HCfavor_e const favor = ctx->favorDecSpeed ? favorDecompressionSpeed : favorCompressionRatio;
1470 int const srcSize = *srcSizePtr;
1471 int result;
1472
1473 if (cParam.strat == lz4mid) {
1474 result = LZ4MID_compress(ctx,
1475 src, dst, srcSizePtr, dstCapacity,
1476 limit, dict);
1477 } else if (cParam.strat == lz4hc) {
1478 result = LZ4HC_compress_hashChain(ctx,
1479 src, dst, srcSizePtr, dstCapacity,
1480 cParam.nbSearches, limit, dict);
1481 } else {
1482 assert(cParam.strat == lz4opt)((void)0);
1483 result = LZ4HC_compress_optimal(ctx,
1484 src, dst, srcSizePtr, dstCapacity,
1485 cParam.nbSearches, cParam.nbSearchesSeq, (int)cParam.targetLength, limit,
1486 dict, favor);
1487 }
1488 if ((limit == fillOutput) && (result > 0) && (*srcSizePtr < srcSize)) {
1489 /* fillOutput : compression stopped before the end of input.
1490 * The rest of input is left to the next block : it isn't history yet,
1491 * and the positions already inserted into it are dropped (lz4mid drops its own).
1492 * Note : a failed compression is different : lz4frame stores its block uncompressed,
1493 * and the next block still references it. */
1494 const BYTE* const consumedEnd = (const BYTE*)src + *srcSizePtr;
1495 U32 const consumedIdx = ctx->dictLimit + (U32)(consumedEnd - ctx->prefixStart);
1496 if ((cParam.strat != lz4mid) && (ctx->nextToUpdate > consumedIdx)) {
1497 LZ4HC_dropPositions(ctx, consumedEnd, consumedEnd + (ctx->nextToUpdate - consumedIdx), cParam.strat);
1498 ctx->nextToUpdate = consumedIdx;
1499 }
1500 ctx->end = consumedEnd;
1501 }
1502 return result;
1503 }
1504}
1505
1506static void LZ4HC_setExternalDict(LZ4HC_CCtx_internal* ctxPtr, const BYTE* newBlock);
1507
1508static int
1509LZ4HC_compress_generic_noDictCtx (
1510 LZ4HC_CCtx_internal* const ctx,
1511 const char* const src,
1512 char* const dst,
1513 int* const srcSizePtr,
1514 int const dstCapacity,
1515 int cLevel,
1516 limitedOutput_directive limit
1517 )
1518{
1519 assert(ctx->dictCtx == NULL)((void)0);
1520 return LZ4HC_compress_generic_internal(ctx, src, dst, srcSizePtr, dstCapacity, cLevel, limit, noDictCtx);
1521}
1522
1523static int isStateCompatible(const LZ4HC_CCtx_internal* ctx1, const LZ4HC_CCtx_internal* ctx2)
1524{
1525 int const isMid1 = LZ4HC_getCLevelParams(ctx1->compressionLevel).strat == lz4mid;
1526 int const isMid2 = LZ4HC_getCLevelParams(ctx2->compressionLevel).strat == lz4mid;
1527 return !(isMid1 ^ isMid2);
1528}
1529
1530static int
1531LZ4HC_compress_generic_dictCtx (
1532 LZ4HC_CCtx_internal* const ctx,
1533 const char* const src,
1534 char* const dst,
1535 int* const srcSizePtr,
1536 int const dstCapacity,
1537 int cLevel,
1538 limitedOutput_directive limit
1539 )
1540{
1541 const size_t position = (size_t)(ctx->end - ctx->prefixStart) + (ctx->dictLimit - ctx->lowLimit);
1542 assert(ctx->dictCtx != NULL)((void)0);
1543 if (position >= 64 KB*(1 <<10)) {
1544 ctx->dictCtx = NULL((void*)0);
1545 return LZ4HC_compress_generic_noDictCtx(ctx, src, dst, srcSizePtr, dstCapacity, cLevel, limit);
1546 } else if (position == 0 && *srcSizePtr >= LZ4HC_getCLevelParams(cLevel).dictCopyMin && isStateCompatible(ctx, ctx->dictCtx)) {
1547 /* parameters and extension belong to the working context, not to the dictionary */
1548 LZ4_i8 const favorDecSpeed = ctx->favorDecSpeed;
1549 LZ4_i8 const hasWorkspace = ctx->hasWorkspace;
1550 LZ4_memcpy(ctx, ctx->dictCtx, sizeof(LZ4HC_CCtx_internal))__builtin_memcpy(ctx, ctx->dictCtx, sizeof(LZ4HC_CCtx_internal
));
1551 LZ4HC_setExternalDict(ctx, (const BYTE *)src);
1552 ctx->compressionLevel = (short)cLevel;
1553 ctx->favorDecSpeed = favorDecSpeed;
1554 ctx->hasWorkspace = hasWorkspace;
1555 return LZ4HC_compress_generic_noDictCtx(ctx, src, dst, srcSizePtr, dstCapacity, cLevel, limit);
1556 } else {
1557 return LZ4HC_compress_generic_internal(ctx, src, dst, srcSizePtr, dstCapacity, cLevel, limit, usingDictCtxHc);
1558 }
1559}
1560
1561static int
1562LZ4HC_compress_generic (
1563 LZ4HC_CCtx_internal* const ctx,
1564 const char* const src,
1565 char* const dst,
1566 int* const srcSizePtr,
1567 int const dstCapacity,
1568 int cLevel,
1569 limitedOutput_directive limit
1570 )
1571{
1572 if (ctx->dictCtx == NULL((void*)0)) {
1573 return LZ4HC_compress_generic_noDictCtx(ctx, src, dst, srcSizePtr, dstCapacity, cLevel, limit);
1574 } else {
1575 return LZ4HC_compress_generic_dictCtx(ctx, src, dst, srcSizePtr, dstCapacity, cLevel, limit);
1576 }
1577}
1578
1579
1580int LZ4_sizeofStateHC(void) { return (int)sizeof(LZ4_streamHC_t); }
1581
1582static size_t LZ4_streamHC_t_alignment(void)
1583{
1584#if LZ4_ALIGN_TEST1
1585 typedef struct { char c; LZ4_streamHC_t t; } t_a;
1586 return sizeof(t_a) - sizeof(LZ4_streamHC_t);
1587#else
1588 return 1; /* effectively disabled */
1589#endif
1590}
1591
1592/* state is presumed correctly initialized,
1593 * in which case its size and alignment have already been validate */
1594int LZ4_compress_HC_extStateHC_fastReset (void* state, const char* src, char* dst, int srcSize, int dstCapacity, int compressionLevel)
1595{
1596 LZ4HC_CCtx_internal* const ctx = &((LZ4_streamHC_t*)state)->internal_donotuse;
1597 if (!LZ4_isAligned(state, LZ4_streamHC_t_alignment())) return 0;
1598 LZ4_resetStreamHC_fast((LZ4_streamHC_t*)state, compressionLevel);
1599 LZ4HC_init_internal (ctx, (const BYTE*)src);
1600 if (dstCapacity < LZ4_compressBound(srcSize))
1601 return LZ4HC_compress_generic (ctx, src, dst, &srcSize, dstCapacity, compressionLevel, limitedOutput);
1602 else
1603 return LZ4HC_compress_generic (ctx, src, dst, &srcSize, dstCapacity, compressionLevel, notLimited);
1604}
1605
1606int LZ4_compress_HC_extStateHC (void* state, const char* src, char* dst, int srcSize, int dstCapacity, int compressionLevel)
1607{
1608 LZ4_streamHC_t* const ctx = LZ4_initStreamHC(state, sizeof(*ctx));
1609 if (ctx==NULL((void*)0)) return 0; /* init failure */
1610 return LZ4_compress_HC_extStateHC_fastReset(state, src, dst, srcSize, dstCapacity, compressionLevel);
1611}
1612
1613int LZ4_compress_HC(const char* src, char* dst, int srcSize, int dstCapacity, int compressionLevel)
1614{
1615 int cSize;
1616 DEBUGLOG(5, "LZ4_compress_HC"){}
1617#if defined(LZ4HC_HEAPMODE1) && LZ4HC_HEAPMODE1==1
1618 { /* extended state : a single allocation, including the temporary buffer of levels >= 10 */
1619 LZ4_streamHC_t* const statePtr = LZ4_initStreamHC(ALLOC(LZ4_STREAMHC_EXTSIZE)malloc((262200 + 65584)), LZ4_STREAMHC_EXTSIZE(262200 + 65584));
1620 if (statePtr==NULL((void*)0)) return 0;
1621 cSize = LZ4_compress_HC_extStateHC_fastReset(statePtr, src, dst, srcSize, dstCapacity, compressionLevel);
1622 FREEMEM(statePtr)free(statePtr);
1623 }
1624#else
1625 { LZ4_streamHC_t state;
1626 cSize = LZ4_compress_HC_extStateHC(&state, src, dst, srcSize, dstCapacity, compressionLevel);
1627 }
1628#endif
1629 return cSize;
1630}
1631
1632/* state is presumed sized correctly (>= sizeof(LZ4_streamHC_t)) */
1633int LZ4_compress_HC_destSize(void* state, const char* source, char* dest, int* sourceSizePtr, int targetDestSize, int cLevel)
1634{
1635 LZ4_streamHC_t* const ctx = LZ4_initStreamHC(state, sizeof(*ctx));
1636 if (ctx==NULL((void*)0)) return 0; /* init failure */
1637 LZ4HC_init_internal(&ctx->internal_donotuse, (const BYTE*) source);
1638 LZ4_setCompressionLevel(ctx, cLevel);
1639 return LZ4HC_compress_generic(&ctx->internal_donotuse, source, dest, sourceSizePtr, targetDestSize, cLevel, fillOutput);
1640}
1641
1642
1643
1644/**************************************
1645* Streaming Functions
1646**************************************/
1647/* allocation */
1648#if !defined(LZ4_STATIC_LINKING_ONLY_DISABLE_MEMORY_ALLOCATION)
1649LZ4_streamHC_t* LZ4_createStreamHC(void)
1650{
1651 LZ4_streamHC_t* const state =
1652 (LZ4_streamHC_t*)ALLOC_AND_ZERO(LZ4_STREAMHC_EXTSIZE)calloc(1,(262200 + 65584)); /* zeroed : initialized */
1653 if (state == NULL((void*)0)) return NULL((void*)0);
1654 state->internal_donotuse.hasWorkspace = 1;
1655 LZ4_setCompressionLevel(state, LZ4HC_CLEVEL_DEFAULT9);
1656 return state;
1657}
1658
1659int LZ4_freeStreamHC (LZ4_streamHC_t* LZ4_streamHCPtr)
1660{
1661 DEBUGLOG(4, "LZ4_freeStreamHC(%p)", LZ4_streamHCPtr){};
1662 if (!LZ4_streamHCPtr) return 0; /* support free on NULL */
1663 FREEMEM(LZ4_streamHCPtr)free(LZ4_streamHCPtr);
1664 return 0;
1665}
1666#endif
1667
1668
1669LZ4_streamHC_t* LZ4_initStreamHC (void* buffer, size_t size)
1670{
1671 LZ4_streamHC_t* const LZ4_streamHCPtr = (LZ4_streamHC_t*)buffer;
1672 DEBUGLOG(4, "LZ4_initStreamHC(%p, %u)", buffer, (unsigned)size){};
1673 /* check conditions */
1674 if (buffer == NULL((void*)0)) return NULL((void*)0);
1675 if (size < sizeof(LZ4_streamHC_t)) return NULL((void*)0);
1676 if (!LZ4_isAligned(buffer, LZ4_streamHC_t_alignment())) return NULL((void*)0);
1677 /* init */
1678 { LZ4HC_CCtx_internal* const hcstate = &(LZ4_streamHCPtr->internal_donotuse);
1679 MEM_INIT(hcstate, 0, sizeof(*hcstate))memset(((hcstate)),((0)),((sizeof(*hcstate))));
1680 hcstate->hasWorkspace = (size >= LZ4_STREAMHC_EXTSIZE(262200 + 65584)); }
1681 LZ4_setCompressionLevel(LZ4_streamHCPtr, LZ4HC_CLEVEL_DEFAULT9);
1682 return LZ4_streamHCPtr;
1683}
1684
1685/* size of an initialized state, to initialize it again : extended states are followed by their buffer */
1686static size_t LZ4HC_sizeofState(const LZ4_streamHC_t* s)
1687{
1688 return s->internal_donotuse.hasWorkspace ? LZ4_STREAMHC_EXTSIZE(262200 + 65584) : sizeof(*s);
1689}
1690
1691/* just a stub */
1692void LZ4_resetStreamHC (LZ4_streamHC_t* LZ4_streamHCPtr, int compressionLevel)
1693{
1694 LZ4_initStreamHC(LZ4_streamHCPtr, LZ4HC_sizeofState(LZ4_streamHCPtr));
1695 LZ4_setCompressionLevel(LZ4_streamHCPtr, compressionLevel);
1696}
1697
1698void LZ4_resetStreamHC_fast (LZ4_streamHC_t* LZ4_streamHCPtr, int compressionLevel)
1699{
1700 LZ4HC_CCtx_internal* const s = &LZ4_streamHCPtr->internal_donotuse;
1701 DEBUGLOG(5, "LZ4_resetStreamHC_fast(%p, %d)", LZ4_streamHCPtr, compressionLevel){};
1702 /* also after a failed compression : its positions are below @end, hence out of reach of the next stream */
1703 assert(s->end >= s->prefixStart)((void)0);
1704 s->dictLimit += (U32)(s->end - s->prefixStart);
1705 s->prefixStart = NULL((void*)0);
1706 s->end = NULL((void*)0);
1707 s->dictCtx = NULL((void*)0);
1708 LZ4_setCompressionLevel(LZ4_streamHCPtr, compressionLevel);
1709}
1710
1711void LZ4_setCompressionLevel(LZ4_streamHC_t* LZ4_streamHCPtr, int compressionLevel)
1712{
1713 DEBUGLOG(5, "LZ4_setCompressionLevel(%p, %d)", LZ4_streamHCPtr, compressionLevel){};
1714 if (compressionLevel < 1) compressionLevel = LZ4HC_CLEVEL_DEFAULT9;
1715 if (compressionLevel > LZ4HC_CLEVEL_MAX12) compressionLevel = LZ4HC_CLEVEL_MAX12;
1716 LZ4_streamHCPtr->internal_donotuse.compressionLevel = (short)compressionLevel;
1717}
1718
1719void LZ4_favorDecompressionSpeed(LZ4_streamHC_t* LZ4_streamHCPtr, int favor)
1720{
1721 LZ4_streamHCPtr->internal_donotuse.favorDecSpeed = (favor!=0);
1722}
1723
1724/* LZ4_loadDictHC() :
1725 * LZ4_streamHCPtr is presumed properly initialized */
1726int LZ4_loadDictHC (LZ4_streamHC_t* LZ4_streamHCPtr,
1727 const char* dictionary, int dictSize)
1728{
1729 LZ4HC_CCtx_internal* const ctxPtr = &LZ4_streamHCPtr->internal_donotuse;
1730 cParams_t cp;
1731 DEBUGLOG(4, "LZ4_loadDictHC(ctx:%p, dict:%p, dictSize:%d, clevel=%d)", LZ4_streamHCPtr, dictionary, dictSize, ctxPtr->compressionLevel){};
1732 assert(LZ4_streamHCPtr != NULL)((void)0);
1733 if (dictSize < 0) dictSize = 0; /* invalid size : no dictionary */
1734 if (dictSize > 64 KB*(1 <<10)) {
1735 dictionary += (size_t)dictSize - 64 KB*(1 <<10);
1736 dictSize = 64 KB*(1 <<10);
1737 }
1738 /* need a full initialization, there are bad side-effects when using resetFast(),
1739 * but preserve parameters */
1740 { int const cLevel = ctxPtr->compressionLevel;
1741 LZ4_i8 const favorDecSpeed = ctxPtr->favorDecSpeed;
1742 LZ4_initStreamHC(LZ4_streamHCPtr, LZ4HC_sizeofState(LZ4_streamHCPtr));
1743 LZ4_setCompressionLevel(LZ4_streamHCPtr, cLevel);
1744 ctxPtr->favorDecSpeed = favorDecSpeed;
1745 cp = LZ4HC_getCLevelParams(cLevel);
1746 }
1747 LZ4HC_init_internal (ctxPtr, (const BYTE*)dictionary);
1748 ctxPtr->end = (const BYTE*)dictionary + dictSize;
1749 if (cp.strat == lz4mid) {
1750 LZ4MID_fillHTable (ctxPtr, dictionary, (size_t)dictSize);
1751 } else {
1752 if (dictSize >= LZ4HC_HASHSIZE4) LZ4HC_Insert (ctxPtr, ctxPtr->end-3);
1753 }
1754 return dictSize;
1755}
1756
1757void LZ4_attach_HC_dictionary(LZ4_streamHC_t *working_stream, const LZ4_streamHC_t *dictionary_stream) {
1758 working_stream->internal_donotuse.dictCtx = dictionary_stream != NULL((void*)0) ? &(dictionary_stream->internal_donotuse) : NULL((void*)0);
1759}
1760
1761/* compression */
1762
1763static void LZ4HC_setExternalDict(LZ4HC_CCtx_internal* ctxPtr, const BYTE* newBlock)
1764{
1765 DEBUGLOG(4, "LZ4HC_setExternalDict(%p, %p)", ctxPtr, newBlock){};
1766 if (LZ4HC_getCLevelParams(ctxPtr->compressionLevel).strat != lz4mid) {
1767 U32 const endIdx = ctxPtr->dictLimit + (U32)(ctxPtr->end - ctxPtr->prefixStart);
1768 U32 idx;
1769 if (ctxPtr->end >= ctxPtr->prefixStart + 4)
1770 LZ4HC_Insert (ctxPtr, ctxPtr->end-3); /* Referencing remaining dictionary content */
1771 /* last positions can't be inserted : don't leave stale chains from previous history */
1772 for (idx = ctxPtr->nextToUpdate; idx < endIdx; idx++)
1773 DELTANEXTU16(ctxPtr->chainTable, idx)ctxPtr->chainTable[(U16)(idx)] = 0;
1774 }
1775
1776 /* Only one memory segment for extDict, so any previous extDict is lost at this stage */
1777 ctxPtr->lowLimit = ctxPtr->dictLimit;
1778 ctxPtr->dictStart = ctxPtr->prefixStart;
1779 ctxPtr->dictLimit += (U32)(ctxPtr->end - ctxPtr->prefixStart);
1780 ctxPtr->prefixStart = newBlock;
1781 ctxPtr->end = newBlock;
1782 ctxPtr->nextToUpdate = ctxPtr->dictLimit; /* match referencing will resume from there */
1783
1784 /* cannot reference an extDict and a dictCtx at the same time */
1785 ctxPtr->dictCtx = NULL((void*)0);
1786}
1787
1788static int
1789LZ4_compressHC_continue_generic (LZ4_streamHC_t* LZ4_streamHCPtr,
1790 const char* src, char* dst,
1791 int* srcSizePtr, int dstCapacity,
1792 limitedOutput_directive limit)
1793{
1794 LZ4HC_CCtx_internal* const ctxPtr = &LZ4_streamHCPtr->internal_donotuse;
1795 DEBUGLOG(5, "LZ4_compressHC_continue_generic(ctx=%p, src=%p, srcSize=%d, limit=%d)",{}
1796 LZ4_streamHCPtr, src, *srcSizePtr, limit){};
1797 assert(ctxPtr != NULL)((void)0);
1798 /* auto-init if forgotten */
1799 if (ctxPtr->prefixStart == NULL((void*)0))
1800 LZ4HC_init_internal (ctxPtr, (const BYTE*) src);
1801
1802 /* Check overflow */
1803 if ((size_t)(ctxPtr->end - ctxPtr->prefixStart) + ctxPtr->dictLimit > 2 GB*(1U<<30)) {
1804 size_t dictSize = (size_t)(ctxPtr->end - ctxPtr->prefixStart);
1805 if (dictSize > 64 KB*(1 <<10)) dictSize = 64 KB*(1 <<10);
1806 LZ4_loadDictHC(LZ4_streamHCPtr, (const char*)(ctxPtr->end) - dictSize, (int)dictSize);
1807 }
1808
1809 /* Check if blocks follow each other */
1810 if ((const BYTE*)src != ctxPtr->end)
1811 LZ4HC_setExternalDict(ctxPtr, (const BYTE*)src);
1812
1813 /* Check overlapping input/dictionary space */
1814 { const BYTE* sourceEnd = (const BYTE*) src + *srcSizePtr;
1815 const BYTE* const dictBegin = ctxPtr->dictStart;
1816 const BYTE* const dictEnd = ctxPtr->dictStart + (ctxPtr->dictLimit - ctxPtr->lowLimit);
1817 if ((sourceEnd > dictBegin) && ((const BYTE*)src < dictEnd)) {
1818 if (sourceEnd > dictEnd) sourceEnd = dictEnd;
1819 ctxPtr->lowLimit += (U32)(sourceEnd - ctxPtr->dictStart);
1820 ctxPtr->dictStart += (U32)(sourceEnd - ctxPtr->dictStart);
1821 /* invalidate dictionary is it's too small */
1822 if (ctxPtr->dictLimit - ctxPtr->lowLimit < LZ4HC_HASHSIZE4) {
1823 ctxPtr->lowLimit = ctxPtr->dictLimit;
1824 ctxPtr->dictStart = ctxPtr->prefixStart;
1825 } } }
1826
1827 return LZ4HC_compress_generic (ctxPtr, src, dst, srcSizePtr, dstCapacity, ctxPtr->compressionLevel, limit);
1828}
1829
1830int LZ4_compress_HC_continue (LZ4_streamHC_t* LZ4_streamHCPtr, const char* src, char* dst, int srcSize, int dstCapacity)
1831{
1832 DEBUGLOG(5, "LZ4_compress_HC_continue"){};
1833 if (dstCapacity < LZ4_compressBound(srcSize))
1834 return LZ4_compressHC_continue_generic (LZ4_streamHCPtr, src, dst, &srcSize, dstCapacity, limitedOutput);
1835 else
1836 return LZ4_compressHC_continue_generic (LZ4_streamHCPtr, src, dst, &srcSize, dstCapacity, notLimited);
1837}
1838
1839int LZ4_compress_HC_continue_destSize (LZ4_streamHC_t* LZ4_streamHCPtr, const char* src, char* dst, int* srcSizePtr, int targetDestSize)
1840{
1841 return LZ4_compressHC_continue_generic(LZ4_streamHCPtr, src, dst, srcSizePtr, targetDestSize, fillOutput);
1842}
1843
1844
1845/* LZ4_saveDictHC :
1846 * save history content
1847 * into a user-provided buffer
1848 * which is then used to continue compression
1849 */
1850int LZ4_saveDictHC (LZ4_streamHC_t* LZ4_streamHCPtr, char* safeBuffer, int dictSize)
1851{
1852 LZ4HC_CCtx_internal* const streamPtr = &LZ4_streamHCPtr->internal_donotuse;
1853 int const prefixSize = (int)(streamPtr->end - streamPtr->prefixStart);
1854 DEBUGLOG(5, "LZ4_saveDictHC(%p, %p, %d)", LZ4_streamHCPtr, safeBuffer, dictSize){};
1855 /* nothing compressed yet (new or reset stream) : nothing to save,
1856 * the stream remains to be initialized by next compression (attached dictionary included) */
1857 if (streamPtr->prefixStart == NULL((void*)0)) return 0;
1
Assuming field 'prefixStart' is not equal to NULL
→
2
←
Taking false branch
→
1858 assert(prefixSize >= 0)((void)0);
1859 if (dictSize > 64 KB*(1 <<10)) dictSize = 64 KB*(1 <<10);
3
←
Assuming the condition is false
→
4
←
Taking false branch
→
1860 if (dictSize < 4) dictSize = 0;
5
←
Assuming 'dictSize' is >= 4
→
6
←
Taking false branch
→
1861 if (dictSize > prefixSize) dictSize = prefixSize;
7
←
Assuming 'dictSize' is <= 'prefixSize'
→
8
←
Taking false branch
→
1862 if (safeBuffer == NULL((void*)0)) assert(dictSize == 0)((void)0); /* a NULL buffer with !0 size is invalid */
9
←
Assuming 'safeBuffer' is equal to NULL
→
10
←
Taking true branch
→
1863 if (dictSize
10.1
'dictSize' is > 0
 > 0)
11
←
Taking true branch
→
1864 LZ4_memmove__builtin_memmove(safeBuffer, streamPtr->end - dictSize, (size_t)dictSize);
12
←
Null pointer passed as 1st argument to memory copy function
1865 { U32 const endIndex = (U32)(streamPtr->end - streamPtr->prefixStart) + streamPtr->dictLimit;
1866 streamPtr->end = (safeBuffer == NULL((void*)0)) ? NULL((void*)0) : (const BYTE*)safeBuffer + dictSize;
1867 streamPtr->prefixStart = (const BYTE*)safeBuffer;
1868 streamPtr->dictLimit = endIndex - (U32)dictSize;
1869 streamPtr->lowLimit = endIndex - (U32)dictSize;
1870 streamPtr->dictStart = streamPtr->prefixStart;
1871 if (streamPtr->nextToUpdate < streamPtr->dictLimit)
1872 streamPtr->nextToUpdate = streamPtr->dictLimit;
1873 }
1874 return dictSize;
1875}
1876
1877
1878/* ================================================
1879 * LZ4 Optimal parser (levels [LZ4HC_CLEVEL_OPT_MIN - LZ4HC_CLEVEL_MAX])
1880 * ===============================================*/
1881typedef struct {
1882 int price;
1883 int off;
1884 int mlen; /* 1 means literal */
1885 int litlen;
1886} LZ4HC_optimal_t;
1887
1888#define TRAILING_LITERALS3 3
1889
1890/* Prices are in 1/LZ4HC_PRICE_SCALE byte,
1891 * leaving room for a price per sequence, lower than a byte. */
1892#define LZ4HC_PRICE_SCALE4 4
1893
1894/* favorDecSpeed : each sequence costs decoding time, so it also costs LZ4HC_SEQ_PRICE_FDS.
1895 * Removing a sequence almost always costs at least one byte,
1896 * so this price, lower than a byte, mostly acts as a tie-breaker :
1897 * among solutions of the same size, the one with fewer sequences is preferred.
1898 * They are found at positions only worth searching to save a sequence,
1899 * which are searched if at most LZ4HC_SEQ_SEARCH_DIST before the end of the furthest match. */
1900#define LZ4HC_SEQ_PRICE_FDS1 1
1901#define LZ4HC_SEQ_SEARCH_DIST4 4
1902
1903LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) int LZ4HC_literalsPrice(int const litlen)
1904{
1905 int price = litlen;
1906 assert(litlen >= 0)((void)0);
1907 if (litlen >= (int)RUN_MASK((1U<<(8-4))-1))
1908 price += 1 + ((litlen-(int)RUN_MASK((1U<<(8-4))-1)) / 255);
1909 return price * LZ4HC_PRICE_SCALE4;
1910}
1911
1912/* requires mlen >= MINMATCH */
1913LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) int LZ4HC_sequencePrice(int litlen, int mlen)
1914{
1915 int price = 1 + 2 ; /* token + 16-bit offset */
1916 assert(litlen >= 0)((void)0);
1917 assert(mlen >= MINMATCH)((void)0);
1918
1919 if (mlen >= (int)(ML_MASK((1U<<4)-1)+MINMATCH4))
1920 price += 1 + ((mlen-(int)(ML_MASK((1U<<4)-1)+MINMATCH4)) / 255);
1921
1922 return price * LZ4HC_PRICE_SCALE4 + LZ4HC_literalsPrice(litlen);
1923}
1924
1925/* LZ4HC_pricedLitlen() :
1926 * All solutions of a window start with the same run of @llen literals,
1927 * so only price differences matter, and they depend on @llen
1928 * only through its position relative to the 255-steps of the literal length field.
1929 * Reduce it accordingly : scaled prices of long runs would overflow. */
1930LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) int LZ4HC_pricedLitlen(int const llen)
1931{
1932 int const reduceFrom = (int)RUN_MASK((1U<<(8-4))-1) + 255;
1933 assert(llen >= 0)((void)0);
1934 if (llen < reduceFrom) return llen;
1935 return reduceFrom + ((llen - (int)RUN_MASK((1U<<(8-4))-1)) % 255);
1936}
1937
1938LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) LZ4HC_match_t
1939LZ4HC_FindLongestMatch(LZ4HC_CCtx_internal* const ctx,
1940 const BYTE* ip, const BYTE* const iHighLimit,
1941 int nbSearches,
1942 const dictCtx_directive dict,
1943 const HCfavor_e favorDecSpeed)
1944{
1945 LZ4HC_match_t const match0 = { 0 , 0, 0 };
1946 /* note : LZ4HC_InsertAndGetWiderMatch() can extend a match backward (md.back < 0),
1947 * but not here, since iLowLimit == ip */
1948 LZ4HC_match_t md = LZ4HC_InsertAndGetWiderMatch(ctx, ip, ip, iHighLimit, MINMATCH4-1, nbSearches, 1 /*patternAnalysis*/, 1 /*chainSwap*/, dict, favorDecSpeed);
1949 assert(md.back == 0)((void)0);
1950 if (md.len < MINMATCH4) return match0;
1951 if (favorDecSpeed) {
1952 if ((md.len>18) & (md.len<=36)) md.len=18; /* favor dec.speed (shortcut) */
1953 }
1954 return md;
1955}
1956
1957LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) void
1958LZ4HC_setLiteral(LZ4HC_optimal_t* opt, int pos, int litlen, int price)
1959{
1960 opt[pos].mlen = 1;
1961 opt[pos].off = 0;
1962 opt[pos].litlen = litlen;
1963 opt[pos].price = price;
1964 DEBUGLOG(7, "rPos:%3i => price:%3i (litlen=%i)", pos, price, litlen){};
1965}
1966
1967LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) void
1968LZ4HC_setMatch(LZ4HC_optimal_t* opt, int pos, int mlen, int off, int price)
1969{
1970 opt[pos].mlen = mlen;
1971 opt[pos].off = off;
1972 opt[pos].litlen = 0;
1973 opt[pos].price = price;
1974 DEBUGLOG(7, "rPos:%3i => price:%3i (matchlen=%i)", pos, price, mlen){};
1975}
1976
1977/* price at the start of the literal run ending at @pos
1978 * (0 if this run started before position 0, i.e. it includes literals since anchor) */
1979LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) int LZ4HC_runStartPrice(const LZ4HC_optimal_t* opt, int pos)
1980{
1981 int const ll = opt[pos].litlen;
1982 return (ll <= pos) ? opt[pos - ll].price : 0;
1983}
1984
1985/* LZ4HC_addMatch() :
1986 * Update prices of positions reachable from @cur using @match.
1987 * Positions beyond @lastPos + TRAILING_LITERALS are not reached yet.
1988 * @return : updated @lastPos (end of the furthest match) */
1989LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) int
1990LZ4HC_addMatch(LZ4HC_optimal_t* opt, int cur, LZ4HC_match_t match,
1991 int lastPos, const HCfavor_e favorDecSpeed)
1992{
1993 int const ll = opt[cur].litlen;
1994 int const basePrice = LZ4HC_runStartPrice(opt, cur) + (favorDecSpeed ? LZ4HC_SEQ_PRICE_FDS1 : 0);
1995 int ml;
1996 assert(cur + match.len < LZ4_OPT_NUM)((void)0);
1997 assert((U32)favorDecSpeed <= 1)((void)0);
1998 for (ml = MINMATCH4; ml <= match.len; ml++) {
1999 int const pos = cur + ml;
2000 int const price = basePrice + LZ4HC_sequencePrice(ll, ml);
2001 /* on equal price, favorDecSpeed keeps the existing solution */
2002 if ( pos > lastPos + TRAILING_LITERALS3
2003 || price <= opt[pos].price - (int)favorDecSpeed) {
2004 LZ4HC_setMatch(opt, pos, ml, match.off, price);
2005 if ((ml == match.len) && (lastPos < pos)) lastPos = pos;
2006 } }
2007
2008 /* complete following positions with literals */
2009 { int addLit;
2010 assert(opt[lastPos].mlen >= MINMATCH)((void)0);
2011 for (addLit = 1; addLit <= TRAILING_LITERALS3; addLit++)
2012 LZ4HC_setLiteral(opt, lastPos + addLit, addLit,
2013 opt[lastPos].price + LZ4HC_literalsPrice(addLit));
2014 }
2015 return lastPos;
2016}
2017
2018
2019/* preconditions:
2020 * - *srcSizePtr within [1, LZ4_MAX_INPUT_SIZE]
2021 * - src is valid
2022 * - maxOutputSize >= 1
2023 * - dst is valid
2024 * - @opt : table of LZ4_OPT_NUM + TRAILING_LITERALS cells
2025 */
2026LZ4_FORCE_INLINEstatic inline __attribute__((always_inline)) int
2027LZ4HC_compress_optimal_internal(LZ4HC_CCtx_internal* ctx,
2028 const char* const source,
2029 char* dst,
2030 int* srcSizePtr,
2031 int dstCapacity,
2032 int const nbSearches,
2033 int const nbSearchesSeq,
2034 int const targetLength,
2035 const limitedOutput_directive limit,
2036 const dictCtx_directive dict,
2037 const HCfavor_e favorDecSpeed,
2038 LZ4HC_optimal_t* const opt)
2039{
2040 const BYTE* ip = (const BYTE*) source;
2041 const BYTE* anchor = ip;
2042 const int inputSize = *srcSizePtr;
2043 const BYTE* const iend = ip + inputSize;
2044 const BYTE* mflimit; /* set after the size check : would precede a small input */
2045 const BYTE* matchlimit;
2046 BYTE* op = (BYTE*) dst;
2047 /* fillOutput : keep room for the final run of literals (LZ4 format restriction) */
2048 BYTE* const oend = op + dstCapacity - ((limit == fillOutput) ? LASTLITERALS5 : 0);
2049 int const sufficientLen = MIN(targetLength, LZ4_OPT_NUM-1)( (targetLength) < ((1<<12)-1) ? (targetLength) : ((
1<<12)-1) );
2050
2051 DEBUGLOG(5, "LZ4HC_compress_optimal(dst=%p, dstCapa=%u)", dst, (unsigned)dstCapacity){};
2052
2053 /* preconditions verifications */
2054 assert(dstCapacity > 0)((void)0);
2055 assert(dst != NULL)((void)0);
2056 assert(*srcSizePtr > 0)((void)0);
2057 assert(source != NULL)((void)0);
2058 assert(opt != NULL)((void)0);
2059 assert(nbSearchesSeq >= 1)((void)0);
2060
2061 *srcSizePtr = 0;
2062 if (inputSize < LZ4_minLength) goto _last_literals;
2063 mflimit = iend - MFLIMIT12;
2064 matchlimit = iend - LASTLITERALS5;
2065
2066 /* Main Loop */
2067 while (ip <= mflimit) {
2068 int const llen = LZ4HC_pricedLitlen((int)(ip - anchor));
2069 int cur, lastPos;
2070 int lastSeqPos; /* position of the last sequence to encode */
2071 LZ4HC_match_t lastSeq;
2072
2073 LZ4HC_match_t const firstMatch = LZ4HC_FindLongestMatch(ctx, ip, matchlimit, nbSearches, dict, favorDecSpeed);
2074 if (firstMatch.len==0) { ip++; continue; }
2075
2076 if (firstMatch.len > sufficientLen) {
2077 /* good enough solution : immediate encoding */
2078 lastSeqPos = 0;
2079 lastSeq = firstMatch;
2080 goto encode;
2081 }
2082
2083 /* set prices for first positions (literals) */
2084 { int rPos;
2085 for (rPos = 0 ; rPos < MINMATCH4 ; rPos++)
2086 LZ4HC_setLiteral(opt, rPos, llen + rPos, LZ4HC_literalsPrice(llen + rPos));
2087 }
2088 lastPos = LZ4HC_addMatch(opt, 0, firstMatch, 0, favorDecSpeed);
2089
2090 /* check further positions */
2091 for (cur = 1; cur < lastPos; cur++) {
2092 const BYTE* const curPtr = ip + cur;
2093 LZ4HC_match_t newMatch;
2094 int nbS = nbSearches;
2095
2096 if (curPtr > mflimit) break;
2097 DEBUGLOG(7, "rPos:%u[%u] vs [%u]%u",{}
2098 cur, opt[cur].price, opt[cur+1].price, cur+1){};
2099 /* not useful to search here if next position has same (or lower) cost */
2100 if (opt[cur+1].price <= opt[cur].price) continue;
2101 /* favorDecSpeed : next position costs less than one more byte, the difference comes from sequences.
2102 * A match starting here might save some : worth a cheaper search, if close to lastPos */
2103 if (favorDecSpeed && (opt[cur+1].price < opt[cur].price + LZ4HC_PRICE_SCALE4)) {
2104 if (lastPos - cur > LZ4HC_SEQ_SEARCH_DIST4) continue;
2105 nbS = nbSearchesSeq;
2106 }
2107
2108 newMatch = LZ4HC_FindLongestMatch(ctx, curPtr, matchlimit, nbS, dict, favorDecSpeed);
2109 if (!newMatch.len) continue;
2110
2111 if ( (newMatch.len > sufficientLen)
2112 || (newMatch.len + cur >= LZ4_OPT_NUM(1<<12)) ) {
2113 /* immediate encoding */
2114 lastSeqPos = cur;
2115 lastSeq = newMatch;
2116 goto encode;
2117 }
2118
2119 lastPos = LZ4HC_addMatch(opt, cur, newMatch, lastPos, favorDecSpeed);
2120 } /* for (cur = 1; cur < lastPos; cur++) */
2121
2122 assert(lastPos < LZ4_OPT_NUM + TRAILING_LITERALS)((void)0);
2123 lastSeq.len = opt[lastPos].mlen;
2124 lastSeq.off = opt[lastPos].off;
2125 lastSeqPos = lastPos - lastSeq.len;
2126
2127encode: /* lastSeqPos and lastSeq must be set */
2128 assert(0 <= lastSeqPos && lastSeqPos < LZ4_OPT_NUM)((void)0);
2129 DEBUGLOG(6, "reverse traversal, looking for shortest path (lastSeqPos=%i)", lastSeqPos){};
2130 /* opt[pos] describes the step ending at pos.
2131 * Walk the path backward, moving each step to its starting position instead */
2132 { int pos = lastSeqPos;
2133 int mlen = lastSeq.len;
2134 int off = lastSeq.off;
2135 while (pos > 0) {
2136 int const prevMlen = opt[pos].mlen;
2137 int const prevOff = opt[pos].off;
2138 opt[pos].mlen = mlen;
2139 opt[pos].off = off;
2140 mlen = prevMlen;
2141 off = prevOff;
2142 assert(0 < mlen && mlen <= pos)((void)0);
2143 pos -= mlen;
2144 }
2145 /* first step of the path; note : opt[0] isn't necessarily initialized */
2146 opt[0].mlen = mlen;
2147 opt[0].off = off;
2148 }
2149
2150 /* encode all recorded sequences in order */
2151 { int rPos = 0; /* relative position (to ip) */
2152 while (rPos <= lastSeqPos) {
2153 int const ml = opt[rPos].mlen;
2154 int const offset = opt[rPos].off;
2155 if (ml == 1) { ip++; rPos++; continue; } /* literal */
2156 rPos += ml;
2157 assert(ml >= MINMATCH)((void)0);
2158 assert((offset >= 1) && (offset <= LZ4_DISTANCE_MAX))((void)0);
2159 if ( LZ4HC_encodeSequence(UPDATABLE(ip, op, anchor)&ip, &op, &anchor, ml, offset, limit, oend) ) { /* updates ip, op and anchor */
2160 if (limit != fillOutput) return 0; /* compression failed */
2161 LZ4HC_encodeLastSequence_fillOutput(UPDATABLE(ip, op, anchor)&ip, &op, &anchor, ml, offset, oend);
2162 goto _last_literals;
2163 } } }
2164 } /* while (ip <= mflimit) */
2165
2166_last_literals:
2167 if (LZ4HC_encodeLastLiterals(UPDATABLE(ip, op, anchor)&ip, &op, &anchor, iend, limit, oend))
2168 return 0; /* not enough space in @dst */
2169
2170 /* End */
2171 *srcSizePtr = (int) (((const char*)ip) - source);
2172 return (int) ((char*)op-dst);
2173}
2174
2175static int LZ4HC_compress_optimal ( LZ4HC_CCtx_internal* ctx,
2176 const char* const source,
2177 char* dst,
2178 int* srcSizePtr,
2179 int dstCapacity,
2180 int const nbSearches,
2181 int const nbSearchesSeq,
2182 int const targetLength,
2183 const limitedOutput_directive limit,
2184 const dictCtx_directive dict,
2185 const HCfavor_e favorDecSpeed)
2186{
2187 LZ4_STATIC_ASSERT(LZ4_STREAMHC_EXTSIZE == sizeof(LZ4_streamHC_t) + sizeof(LZ4HC_optimal_t) * (LZ4_OPT_NUM + TRAILING_LITERALS)){ enum { LZ4_static_assert = 1/(int)(!!((262200 + 65584) == sizeof
(LZ4_streamHC_t) + sizeof(LZ4HC_optimal_t) * ((1<<12) +
3))) }; };
2188 if (ctx->hasWorkspace) { /* extended state : the buffer follows it */
2189 LZ4HC_optimal_t* const opt = (LZ4HC_optimal_t*)(void*)((BYTE*)ctx + sizeof(LZ4_streamHC_t));
2190 return LZ4HC_compress_optimal_internal(ctx, source, dst, srcSizePtr, dstCapacity,
2191 nbSearches, nbSearchesSeq, targetLength, limit, dict, favorDecSpeed, opt);
2192 }
2193 { /* plain state */
2194#if defined(LZ4HC_HEAPMODE1) && LZ4HC_HEAPMODE1==1
2195 LZ4HC_optimal_t* const opt = (LZ4HC_optimal_t*)ALLOC(sizeof(LZ4HC_optimal_t) * (LZ4_OPT_NUM + TRAILING_LITERALS))malloc(sizeof(LZ4HC_optimal_t) * ((1<<12) + 3));
2196 int result;
2197 if (opt == NULL((void*)0)) return 0;
2198 result = LZ4HC_compress_optimal_internal(ctx, source, dst, srcSizePtr, dstCapacity,
2199 nbSearches, nbSearchesSeq, targetLength, limit, dict, favorDecSpeed, opt);
2200 FREEMEM(opt)free(opt);
2201 return result;
2202#else
2203 LZ4HC_optimal_t opt[LZ4_OPT_NUM(1<<12) + TRAILING_LITERALS3]; /* ~64 KB, which can be a bit large for some stacks... */
2204 return LZ4HC_compress_optimal_internal(ctx, source, dst, srcSizePtr, dstCapacity,
2205 nbSearches, nbSearchesSeq, targetLength, limit, dict, favorDecSpeed, opt);
2206#endif
2207 }
2208}
2209
2210
2211/***************************************************
2212* Obsolete functions, removed from lz4hc.h (v1.11.0)
2213* still exported, for programs linked to previous versions
2214***************************************************/
2215#if defined (__cplusplus)
2216extern "C" {
2217#endif
2218
2219LZ4LIB_API int LZ4_compressHC (const char* source, char* dest, int inputSize);
2220LZ4LIB_API int LZ4_compressHC_limitedOutput (const char* source, char* dest, int inputSize, int maxOutputSize);
2221LZ4LIB_API int LZ4_compressHC2 (const char* source, char* dest, int inputSize, int compressionLevel);
2222LZ4LIB_API int LZ4_compressHC2_limitedOutput (const char* source, char* dest, int inputSize, int maxOutputSize, int compressionLevel);
2223LZ4LIB_API int LZ4_compressHC_withStateHC (void* state, const char* source, char* dest, int inputSize);
2224LZ4LIB_API int LZ4_compressHC_limitedOutput_withStateHC (void* state, const char* source, char* dest, int inputSize, int maxOutputSize);
2225LZ4LIB_API int LZ4_compressHC2_withStateHC (void* state, const char* source, char* dest, int inputSize, int compressionLevel);
2226LZ4LIB_API int LZ4_compressHC2_limitedOutput_withStateHC (void* state, const char* source, char* dest, int inputSize, int maxOutputSize, int compressionLevel);
2227LZ4LIB_API int LZ4_compressHC_continue (LZ4_streamHC_t* LZ4_streamHCPtr, const char* source, char* dest, int inputSize);
2228LZ4LIB_API int LZ4_compressHC_limitedOutput_continue (LZ4_streamHC_t* LZ4_streamHCPtr, const char* source, char* dest, int inputSize, int maxOutputSize);
2229LZ4LIB_API void* LZ4_createHC (const char* inputBuffer);
2230LZ4LIB_API int LZ4_freeHC (void* LZ4HC_Data);
2231LZ4LIB_API char* LZ4_slideInputBufferHC (void* LZ4HC_Data);
2232LZ4LIB_API int LZ4_compressHC2_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize, int compressionLevel);
2233LZ4LIB_API int LZ4_compressHC2_limitedOutput_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize, int maxOutputSize, int compressionLevel);
2234LZ4LIB_API int LZ4_sizeofStreamStateHC(void);
2235LZ4LIB_API int LZ4_resetStreamStateHC(void* state, char* inputBuffer);
2236
2237#if defined (__cplusplus)
2238}
2239#endif
2240
2241/* Wrappers for deprecated compression functions */
2242int LZ4_compressHC(const char* src, char* dst, int srcSize) { return LZ4_compress_HC (src, dst, srcSize, LZ4_compressBound(srcSize), 0); }
2243int LZ4_compressHC_limitedOutput(const char* src, char* dst, int srcSize, int maxDstSize) { return LZ4_compress_HC(src, dst, srcSize, maxDstSize, 0); }
2244int LZ4_compressHC2(const char* src, char* dst, int srcSize, int cLevel) { return LZ4_compress_HC (src, dst, srcSize, LZ4_compressBound(srcSize), cLevel); }
2245int LZ4_compressHC2_limitedOutput(const char* src, char* dst, int srcSize, int maxDstSize, int cLevel) { return LZ4_compress_HC(src, dst, srcSize, maxDstSize, cLevel); }
2246int LZ4_compressHC_withStateHC (void* state, const char* src, char* dst, int srcSize) { return LZ4_compress_HC_extStateHC (state, src, dst, srcSize, LZ4_compressBound(srcSize), 0); }
2247int LZ4_compressHC_limitedOutput_withStateHC (void* state, const char* src, char* dst, int srcSize, int maxDstSize) { return LZ4_compress_HC_extStateHC (state, src, dst, srcSize, maxDstSize, 0); }
2248int LZ4_compressHC2_withStateHC (void* state, const char* src, char* dst, int srcSize, int cLevel) { return LZ4_compress_HC_extStateHC(state, src, dst, srcSize, LZ4_compressBound(srcSize), cLevel); }
2249int LZ4_compressHC2_limitedOutput_withStateHC (void* state, const char* src, char* dst, int srcSize, int maxDstSize, int cLevel) { return LZ4_compress_HC_extStateHC(state, src, dst, srcSize, maxDstSize, cLevel); }
2250int LZ4_compressHC_continue (LZ4_streamHC_t* ctx, const char* src, char* dst, int srcSize) { return LZ4_compress_HC_continue (ctx, src, dst, srcSize, LZ4_compressBound(srcSize)); }
2251int LZ4_compressHC_limitedOutput_continue (LZ4_streamHC_t* ctx, const char* src, char* dst, int srcSize, int maxDstSize) { return LZ4_compress_HC_continue (ctx, src, dst, srcSize, maxDstSize); }
2252
2253
2254/* Deprecated streaming functions */
2255int LZ4_sizeofStreamStateHC(void) { return sizeof(LZ4_streamHC_t); }
2256
2257/* state is presumed correctly sized, aka >= sizeof(LZ4_streamHC_t)
2258 * @return : 0 on success, !=0 if error */
2259int LZ4_resetStreamStateHC(void* state, char* inputBuffer)
2260{
2261 LZ4_streamHC_t* const hc4 = LZ4_initStreamHC(state, sizeof(*hc4));
2262 if (hc4 == NULL((void*)0)) return 1; /* init failed */
2263 LZ4HC_init_internal (&hc4->internal_donotuse, (const BYTE*)inputBuffer);
2264 return 0;
2265}
2266
2267#if !defined(LZ4_STATIC_LINKING_ONLY_DISABLE_MEMORY_ALLOCATION)
2268void* LZ4_createHC (const char* inputBuffer)
2269{
2270 LZ4_streamHC_t* const hc4 = LZ4_createStreamHC();
2271 if (hc4 == NULL((void*)0)) return NULL((void*)0); /* not enough memory */
2272 LZ4HC_init_internal (&hc4->internal_donotuse, (const BYTE*)inputBuffer);
2273 return hc4;
2274}
2275
2276int LZ4_freeHC (void* LZ4HC_Data)
2277{
2278 if (!LZ4HC_Data) return 0; /* support free on NULL */
2279 FREEMEM(LZ4HC_Data)free(LZ4HC_Data);
2280 return 0;
2281}
2282#endif
2283
2284/* LZ4_compress_HC_continue() at level @cLevel : notably, restarts the stream after LZ4_slideInputBufferHC() */
2285int LZ4_compressHC2_continue (void* LZ4HC_Data, const char* src, char* dst, int srcSize, int cLevel)
2286{
2287 LZ4_setCompressionLevel((LZ4_streamHC_t*)LZ4HC_Data, cLevel);
2288 return LZ4_compress_HC_continue((LZ4_streamHC_t*)LZ4HC_Data, src, dst, srcSize, LZ4_compressBound(srcSize));
2289}
2290
2291int LZ4_compressHC2_limitedOutput_continue (void* LZ4HC_Data, const char* src, char* dst, int srcSize, int dstCapacity, int cLevel)
2292{
2293 LZ4_setCompressionLevel((LZ4_streamHC_t*)LZ4HC_Data, cLevel);
2294 return LZ4_compress_HC_continue((LZ4_streamHC_t*)LZ4HC_Data, src, dst, srcSize, dstCapacity);
2295}
2296
2297char* LZ4_slideInputBufferHC(void* LZ4HC_Data)
2298{
2299 LZ4HC_CCtx_internal* const s = &((LZ4_streamHC_t*)LZ4HC_Data)->internal_donotuse;
2300 const BYTE* const bufferStart = s->prefixStart - s->dictLimit + s->lowLimit;
2301 LZ4_resetStreamHC_fast((LZ4_streamHC_t*)LZ4HC_Data, s->compressionLevel);
2302 /* ugly conversion trick, required to evade (const char*) -> (char*) cast-qual warning :( */
2303 return (char*)(uptrval)bufferStart;
2304}