lz4hc.c revision 52cac9a97342641315c76cfb861206d6acd631a8 
1/*
2    LZ4 HC - High Compression Mode of LZ4
3    Copyright (C) 2011-2016, Yann Collet.
4
5    BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
6
7    Redistribution and use in source and binary forms, with or without
8    modification, are permitted provided that the following conditions are
9    met:
10
11    * Redistributions of source code must retain the above copyright
12    notice, this list of conditions and the following disclaimer.
13    * Redistributions in binary form must reproduce the above
14    copyright notice, this list of conditions and the following disclaimer
15    in the documentation and/or other materials provided with the
16    distribution.
17
18    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24    LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25    DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26    THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27    (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29
30    You can contact the author at :
31       - LZ4 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/*!
42 * HEAPMODE :
43 * Select how default compression function will allocate workplace memory,
44 * in stack (0:fastest), or in heap (1:requires malloc()).
45 * Since workplace is rather large, heap mode is recommended.
46 */
47#ifndef LZ4HC_HEAPMODE
48#  define LZ4HC_HEAPMODE 1
49#endif
50
51
52/* *************************************
53*  Dependency
54***************************************/
55#include "lz4hc.h"
56
57
58/* *************************************
59*  Local Compiler Options
60***************************************/
61#if defined(__GNUC__)
62#  pragma GCC diagnostic ignored "-Wunused-function"
63#endif
64
65#if defined (__clang__)
66#  pragma clang diagnostic ignored "-Wunused-function"
67#endif
68
69
70/* *************************************
71*  Common LZ4 definition
72***************************************/
73#define LZ4_COMMONDEFS_ONLY
74#include "lz4.c"
75
76
77/* *************************************
78*  Local Constants
79***************************************/
80#define OPTIMAL_ML (int)((ML_MASK-1)+MINMATCH)
81
82
83/**************************************
84*  Local Macros
85**************************************/
86#define HASH_FUNCTION(i)       (((i) * 2654435761U) >> ((MINMATCH*8)-LZ4HC_HASH_LOG))
87#define DELTANEXTMAXD(p)       chainTable[(p) & LZ4HC_MAXD_MASK]    /* flexible, LZ4HC_MAXD dependent */
88#define DELTANEXTU16(p)        chainTable[(U16)(p)]   /* faster */
89
90static U32 LZ4HC_hashPtr(const void* ptr) { return HASH_FUNCTION(LZ4_read32(ptr)); }
91
92
93
94/**************************************
95*  HC Compression
96**************************************/
97static void LZ4HC_init (LZ4HC_CCtx_internal* hc4, const BYTE* start)
98{
99    MEM_INIT((void*)hc4->hashTable, 0, sizeof(hc4->hashTable));
100    MEM_INIT(hc4->chainTable, 0xFF, sizeof(hc4->chainTable));
101    hc4->nextToUpdate = hc4->nextToUpdateBT = 64 KB;
102    hc4->base = start - 64 KB;
103    hc4->end = start;
104    hc4->dictBase = start - 64 KB;
105    hc4->dictLimit = 64 KB;
106    hc4->lowLimit = 64 KB;
107}
108
109
110/* Update chains up to ip (excluded) */
111FORCE_INLINE void LZ4HC_Insert (LZ4HC_CCtx_internal* hc4, const BYTE* ip)
112{
113    U16* const chainTable = hc4->chainTable;
114    U32* const hashTable  = hc4->hashTable;
115    const BYTE* const base = hc4->base;
116    U32 const target = (U32)(ip - base);
117    U32 idx = hc4->nextToUpdate;
118
119    while (idx < target) {
120        U32 const h = LZ4HC_hashPtr(base+idx);
121        size_t delta = idx - hashTable[h];
122        if (delta>MAX_DISTANCE) delta = MAX_DISTANCE;
123        DELTANEXTU16(idx) = (U16)delta;
124        hashTable[h] = idx;
125        idx++;
126    }
127
128    hc4->nextToUpdate = target;
129}
130
131
132FORCE_INLINE int LZ4HC_InsertAndFindBestMatch (LZ4HC_CCtx_internal* hc4,   /* Index table will be updated */
133                                               const BYTE* ip, const BYTE* const iLimit,
134                                               const BYTE** matchpos,
135                                               const int maxNbAttempts)
136{
137    U16* const chainTable = hc4->chainTable;
138    U32* const HashTable = hc4->hashTable;
139    const BYTE* const base = hc4->base;
140    const BYTE* const dictBase = hc4->dictBase;
141    const U32 dictLimit = hc4->dictLimit;
142    const U32 lowLimit = (hc4->lowLimit + 64 KB > (U32)(ip-base)) ? hc4->lowLimit : (U32)(ip - base) - (64 KB - 1);
143    U32 matchIndex;
144    int nbAttempts=maxNbAttempts;
145    size_t ml=0;
146
147    /* HC4 match finder */
148    LZ4HC_Insert(hc4, ip);
149    matchIndex = HashTable[LZ4HC_hashPtr(ip)];
150
151    while ((matchIndex>=lowLimit) && (nbAttempts)) {
152        nbAttempts--;
153        if (matchIndex >= dictLimit) {
154            const BYTE* const match = base + matchIndex;
155            if (*(match+ml) == *(ip+ml)
156                && (LZ4_read32(match) == LZ4_read32(ip)))
157            {
158                size_t const mlt = LZ4_count(ip+MINMATCH, match+MINMATCH, iLimit) + MINMATCH;
159                if (mlt > ml) { ml = mlt; *matchpos = match; }
160            }
161        } else {
162            const BYTE* const match = dictBase + matchIndex;
163            if (LZ4_read32(match) == LZ4_read32(ip)) {
164                size_t mlt;
165                const BYTE* vLimit = ip + (dictLimit - matchIndex);
166                if (vLimit > iLimit) vLimit = iLimit;
167                mlt = LZ4_count(ip+MINMATCH, match+MINMATCH, vLimit) + MINMATCH;
168                if ((ip+mlt == vLimit) && (vLimit < iLimit))
169                    mlt += LZ4_count(ip+mlt, base+dictLimit, iLimit);
170                if (mlt > ml) { ml = mlt; *matchpos = base + matchIndex; }   /* virtual matchpos */
171            }
172        }
173        matchIndex -= DELTANEXTU16(matchIndex);
174    }
175
176    return (int)ml;
177}
178
179
180FORCE_INLINE int LZ4HC_InsertAndGetWiderMatch (
181    LZ4HC_CCtx_internal* hc4,
182    const BYTE* const ip,
183    const BYTE* const iLowLimit,
184    const BYTE* const iHighLimit,
185    int longest,
186    const BYTE** matchpos,
187    const BYTE** startpos,
188    const int maxNbAttempts)
189{
190    U16* const chainTable = hc4->chainTable;
191    U32* const HashTable = hc4->hashTable;
192    const BYTE* const base = hc4->base;
193    const U32 dictLimit = hc4->dictLimit;
194    const BYTE* const lowPrefixPtr = base + dictLimit;
195    const U32 lowLimit = (hc4->lowLimit + 64 KB > (U32)(ip-base)) ? hc4->lowLimit : (U32)(ip - base) - (64 KB - 1);
196    const BYTE* const dictBase = hc4->dictBase;
197    U32   matchIndex;
198    int nbAttempts = maxNbAttempts;
199    int delta = (int)(ip-iLowLimit);
200
201
202    /* First Match */
203    LZ4HC_Insert(hc4, ip);
204    matchIndex = HashTable[LZ4HC_hashPtr(ip)];
205
206    while ((matchIndex>=lowLimit) && (nbAttempts)) {
207        nbAttempts--;
208        if (matchIndex >= dictLimit) {
209            const BYTE* matchPtr = base + matchIndex;
210            if (*(iLowLimit + longest) == *(matchPtr - delta + longest)) {
211                if (LZ4_read32(matchPtr) == LZ4_read32(ip)) {
212                    int mlt = MINMATCH + LZ4_count(ip+MINMATCH, matchPtr+MINMATCH, iHighLimit);
213                    int back = 0;
214
215                    while ((ip+back > iLowLimit)
216                           && (matchPtr+back > lowPrefixPtr)
217                           && (ip[back-1] == matchPtr[back-1]))
218                            back--;
219
220                    mlt -= back;
221
222                    if (mlt > longest) {
223                        longest = (int)mlt;
224                        *matchpos = matchPtr+back;
225                        *startpos = ip+back;
226                    }
227                }
228            }
229        } else {
230            const BYTE* const matchPtr = dictBase + matchIndex;
231            if (LZ4_read32(matchPtr) == LZ4_read32(ip)) {
232                size_t mlt;
233                int back=0;
234                const BYTE* vLimit = ip + (dictLimit - matchIndex);
235                if (vLimit > iHighLimit) vLimit = iHighLimit;
236                mlt = LZ4_count(ip+MINMATCH, matchPtr+MINMATCH, vLimit) + MINMATCH;
237                if ((ip+mlt == vLimit) && (vLimit < iHighLimit))
238                    mlt += LZ4_count(ip+mlt, base+dictLimit, iHighLimit);
239                while ((ip+back > iLowLimit) && (matchIndex+back > lowLimit) && (ip[back-1] == matchPtr[back-1])) back--;
240                mlt -= back;
241                if ((int)mlt > longest) { longest = (int)mlt; *matchpos = base + matchIndex + back; *startpos = ip+back; }
242            }
243        }
244        matchIndex -= DELTANEXTU16(matchIndex);
245    }
246
247    return longest;
248}
249
250
251typedef enum { noLimit = 0, limitedOutput = 1 } limitedOutput_directive;
252
253#define LZ4HC_DEBUG 0
254#if LZ4HC_DEBUG
255static unsigned debug = 0;
256#endif
257
258FORCE_INLINE int LZ4HC_encodeSequence (
259    const BYTE** ip,
260    BYTE** op,
261    const BYTE** anchor,
262    int matchLength,
263    const BYTE* const match,
264    limitedOutput_directive limitedOutputBuffer,
265    BYTE* oend)
266{
267    int length;
268    BYTE* token;
269
270#if LZ4HC_DEBUG
271    if (debug) printf("literal : %u  --  match : %u  --  offset : %u\n", (U32)(*ip - *anchor), (U32)matchLength, (U32)(*ip-match));
272#endif
273
274    /* Encode Literal length */
275    length = (int)(*ip - *anchor);
276    token = (*op)++;
277    if ((limitedOutputBuffer) && ((*op + (length>>8) + length + (2 + 1 + LASTLITERALS)) > oend)) return 1;   /* Check output limit */
278    if (length>=(int)RUN_MASK) { int len; *token=(RUN_MASK<<ML_BITS); len = length-RUN_MASK; for(; len > 254 ; len-=255) *(*op)++ = 255;  *(*op)++ = (BYTE)len; }
279    else *token = (BYTE)(length<<ML_BITS);
280
281    /* Copy Literals */
282    LZ4_wildCopy(*op, *anchor, (*op) + length);
283    *op += length;
284
285    /* Encode Offset */
286    LZ4_writeLE16(*op, (U16)(*ip-match)); *op += 2;
287
288    /* Encode MatchLength */
289    length = (int)(matchLength-MINMATCH);
290    if ((limitedOutputBuffer) && (*op + (length>>8) + (1 + LASTLITERALS) > oend)) return 1;   /* Check output limit */
291    if (length>=(int)ML_MASK) {
292        *token += ML_MASK;
293        length -= ML_MASK;
294        for(; length > 509 ; length-=510) { *(*op)++ = 255; *(*op)++ = 255; }
295        if (length > 254) { length-=255; *(*op)++ = 255; }
296        *(*op)++ = (BYTE)length;
297    } else {
298        *token += (BYTE)(length);
299    }
300
301    /* Prepare next loop */
302    *ip += matchLength;
303    *anchor = *ip;
304
305    return 0;
306}
307
308#include "lz4opt.h"
309
310static int LZ4HC_compress_hashChain (
311    LZ4HC_CCtx_internal* const ctx,
312    const char* const source,
313    char* const dest,
314    int const inputSize,
315    int const maxOutputSize,
316    unsigned maxNbAttempts,
317    limitedOutput_directive limit
318    )
319{
320    const BYTE* ip = (const BYTE*) source;
321    const BYTE* anchor = ip;
322    const BYTE* const iend = ip + inputSize;
323    const BYTE* const mflimit = iend - MFLIMIT;
324    const BYTE* const matchlimit = (iend - LASTLITERALS);
325
326    BYTE* op = (BYTE*) dest;
327    BYTE* const oend = op + maxOutputSize;
328
329    int   ml, ml2, ml3, ml0;
330    const BYTE* ref = NULL;
331    const BYTE* start2 = NULL;
332    const BYTE* ref2 = NULL;
333    const BYTE* start3 = NULL;
334    const BYTE* ref3 = NULL;
335    const BYTE* start0;
336    const BYTE* ref0;
337
338    /* init */
339    ctx->end += inputSize;
340
341    ip++;
342
343    /* Main Loop */
344    while (ip < mflimit) {
345        ml = LZ4HC_InsertAndFindBestMatch (ctx, ip, matchlimit, (&ref), maxNbAttempts);
346        if (!ml) { ip++; continue; }
347
348        /* saved, in case we would skip too much */
349        start0 = ip;
350        ref0 = ref;
351        ml0 = ml;
352
353_Search2:
354        if (ip+ml < mflimit)
355            ml2 = LZ4HC_InsertAndGetWiderMatch(ctx, ip + ml - 2, ip + 0, matchlimit, ml, &ref2, &start2, maxNbAttempts);
356        else ml2 = ml;
357
358        if (ml2 == ml) { /* No better match */
359            if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml, ref, limit, oend)) return 0;
360            continue;
361        }
362
363        if (start0 < ip) {
364            if (start2 < ip + ml0) {  /* empirical */
365                ip = start0;
366                ref = ref0;
367                ml = ml0;
368            }
369        }
370
371        /* Here, start0==ip */
372        if ((start2 - ip) < 3) {  /* First Match too small : removed */
373            ml = ml2;
374            ip = start2;
375            ref =ref2;
376            goto _Search2;
377        }
378
379_Search3:
380        /*
381        * Currently we have :
382        * ml2 > ml1, and
383        * ip1+3 <= ip2 (usually < ip1+ml1)
384        */
385        if ((start2 - ip) < OPTIMAL_ML) {
386            int correction;
387            int new_ml = ml;
388            if (new_ml > OPTIMAL_ML) new_ml = OPTIMAL_ML;
389            if (ip+new_ml > start2 + ml2 - MINMATCH) new_ml = (int)(start2 - ip) + ml2 - MINMATCH;
390            correction = new_ml - (int)(start2 - ip);
391            if (correction > 0) {
392                start2 += correction;
393                ref2 += correction;
394                ml2 -= correction;
395            }
396        }
397        /* Now, we have start2 = ip+new_ml, with new_ml = min(ml, OPTIMAL_ML=18) */
398
399        if (start2 + ml2 < mflimit)
400            ml3 = LZ4HC_InsertAndGetWiderMatch(ctx, start2 + ml2 - 3, start2, matchlimit, ml2, &ref3, &start3, maxNbAttempts);
401        else ml3 = ml2;
402
403        if (ml3 == ml2) {  /* No better match : 2 sequences to encode */
404            /* ip & ref are known; Now for ml */
405            if (start2 < ip+ml)  ml = (int)(start2 - ip);
406            /* Now, encode 2 sequences */
407            if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml, ref, limit, oend)) return 0;
408            ip = start2;
409            if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml2, ref2, limit, oend)) return 0;
410            continue;
411        }
412
413        if (start3 < ip+ml+3) {  /* Not enough space for match 2 : remove it */
414            if (start3 >= (ip+ml)) {  /* can write Seq1 immediately ==> Seq2 is removed, so Seq3 becomes Seq1 */
415                if (start2 < ip+ml) {
416                    int correction = (int)(ip+ml - start2);
417                    start2 += correction;
418                    ref2 += correction;
419                    ml2 -= correction;
420                    if (ml2 < MINMATCH) {
421                        start2 = start3;
422                        ref2 = ref3;
423                        ml2 = ml3;
424                    }
425                }
426
427                if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml, ref, limit, oend)) return 0;
428                ip  = start3;
429                ref = ref3;
430                ml  = ml3;
431
432                start0 = start2;
433                ref0 = ref2;
434                ml0 = ml2;
435                goto _Search2;
436            }
437
438            start2 = start3;
439            ref2 = ref3;
440            ml2 = ml3;
441            goto _Search3;
442        }
443
444        /*
445        * OK, now we have 3 ascending matches; let's write at least the first one
446        * ip & ref are known; Now for ml
447        */
448        if (start2 < ip+ml) {
449            if ((start2 - ip) < (int)ML_MASK) {
450                int correction;
451                if (ml > OPTIMAL_ML) ml = OPTIMAL_ML;
452                if (ip + ml > start2 + ml2 - MINMATCH) ml = (int)(start2 - ip) + ml2 - MINMATCH;
453                correction = ml - (int)(start2 - ip);
454                if (correction > 0) {
455                    start2 += correction;
456                    ref2 += correction;
457                    ml2 -= correction;
458                }
459            } else {
460                ml = (int)(start2 - ip);
461            }
462        }
463        if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml, ref, limit, oend)) return 0;
464
465        ip = start2;
466        ref = ref2;
467        ml = ml2;
468
469        start2 = start3;
470        ref2 = ref3;
471        ml2 = ml3;
472
473        goto _Search3;
474    }
475
476    /* Encode Last Literals */
477    {   int lastRun = (int)(iend - anchor);
478        if ((limit) && (((char*)op - dest) + lastRun + 1 + ((lastRun+255-RUN_MASK)/255) > (U32)maxOutputSize)) return 0;  /* Check output limit */
479        if (lastRun>=(int)RUN_MASK) { *op++=(RUN_MASK<<ML_BITS); lastRun-=RUN_MASK; for(; lastRun > 254 ; lastRun-=255) *op++ = 255; *op++ = (BYTE) lastRun; }
480        else *op++ = (BYTE)(lastRun<<ML_BITS);
481        memcpy(op, anchor, iend - anchor);
482        op += iend-anchor;
483    }
484
485    /* End */
486    return (int) (((char*)op)-dest);
487}
488
489
490static int LZ4HC_compress_generic (
491    LZ4HC_CCtx_internal* const ctx,
492    const char* const source,
493    char* const dest,
494    int const inputSize,
495    int const maxOutputSize,
496    int compressionLevel,
497    limitedOutput_directive limit
498    )
499{
500    if (compressionLevel < 1) compressionLevel = LZ4HC_CLEVEL_DEFAULT;
501    if (compressionLevel > 9) {
502        switch (compressionLevel) {
503            case 10: return LZ4HC_compress_hashChain(ctx, source, dest, inputSize, maxOutputSize, 1 << (16-1), limit);
504            case 11: ctx->searchNum = 128;  return LZ4HC_compress_optimal(ctx, source, dest, inputSize, maxOutputSize, limit, 128, 0);
505            default:
506            case 12: ctx->searchNum = 1<<10; return LZ4HC_compress_optimal(ctx, source, dest, inputSize, maxOutputSize, limit, LZ4_OPT_NUM, 1);
507        }
508    }
509    return LZ4HC_compress_hashChain(ctx, source, dest, inputSize, maxOutputSize, 1 << (compressionLevel-1), limit);
510}
511
512
513int LZ4_sizeofStateHC(void) { return sizeof(LZ4_streamHC_t); }
514
515int LZ4_compress_HC_extStateHC (void* state, const char* src, char* dst, int srcSize, int maxDstSize, int compressionLevel)
516{
517    LZ4HC_CCtx_internal* ctx = &((LZ4_streamHC_t*)state)->internal_donotuse;
518    if (((size_t)(state)&(sizeof(void*)-1)) != 0) return 0;   /* Error : state is not aligned for pointers (32 or 64 bits) */
519    LZ4HC_init (ctx, (const BYTE*)src);
520    if (maxDstSize < LZ4_compressBound(srcSize))
521        return LZ4HC_compress_generic (ctx, src, dst, srcSize, maxDstSize, compressionLevel, limitedOutput);
522    else
523        return LZ4HC_compress_generic (ctx, src, dst, srcSize, maxDstSize, compressionLevel, noLimit);
524}
525
526int LZ4_compress_HC(const char* src, char* dst, int srcSize, int maxDstSize, int compressionLevel)
527{
528#if defined(LZ4HC_HEAPMODE) && LZ4HC_HEAPMODE==1
529    LZ4_streamHC_t* const statePtr = (LZ4_streamHC_t*)malloc(sizeof(LZ4_streamHC_t));
530#else
531    LZ4_streamHC_t state;
532    LZ4_streamHC_t* const statePtr = &state;
533#endif
534    int const cSize = LZ4_compress_HC_extStateHC(statePtr, src, dst, srcSize, maxDstSize, compressionLevel);
535#if defined(LZ4HC_HEAPMODE) && LZ4HC_HEAPMODE==1
536    free(statePtr);
537#endif
538    return cSize;
539}
540
541
542
543/**************************************
544*  Streaming Functions
545**************************************/
546/* allocation */
547LZ4_streamHC_t* LZ4_createStreamHC(void) { return (LZ4_streamHC_t*)malloc(sizeof(LZ4_streamHC_t)); }
548int             LZ4_freeStreamHC (LZ4_streamHC_t* LZ4_streamHCPtr) { free(LZ4_streamHCPtr); return 0; }
549
550
551/* initialization */
552void LZ4_resetStreamHC (LZ4_streamHC_t* LZ4_streamHCPtr, int compressionLevel)
553{
554    LZ4_STATIC_ASSERT(sizeof(LZ4HC_CCtx_internal) <= sizeof(size_t) * LZ4_STREAMHCSIZE_SIZET);   /* if compilation fails here, LZ4_STREAMHCSIZE must be increased */
555    LZ4_streamHCPtr->internal_donotuse.base = NULL;
556    LZ4_streamHCPtr->internal_donotuse.compressionLevel = (unsigned)compressionLevel;
557}
558
559int LZ4_loadDictHC (LZ4_streamHC_t* LZ4_streamHCPtr, const char* dictionary, int dictSize)
560{
561    LZ4HC_CCtx_internal* ctxPtr = &LZ4_streamHCPtr->internal_donotuse;
562    if (dictSize > 64 KB) {
563        dictionary += dictSize - 64 KB;
564        dictSize = 64 KB;
565    }
566    LZ4HC_init (ctxPtr, (const BYTE*)dictionary);
567    if (dictSize >= 4) LZ4HC_Insert (ctxPtr, (const BYTE*)dictionary +(dictSize-3));
568    ctxPtr->end = (const BYTE*)dictionary + dictSize;
569    return dictSize;
570}
571
572
573/* compression */
574
575static void LZ4HC_setExternalDict(LZ4HC_CCtx_internal* ctxPtr, const BYTE* newBlock)
576{
577    if (ctxPtr->compressionLevel >= LZ4HC_CLEVEL_OPT_MIN)
578        LZ4HC_updateBinTree(ctxPtr, ctxPtr->end - MFLIMIT, ctxPtr->end - LASTLITERALS);
579    else
580        if (ctxPtr->end >= ctxPtr->base + 4) LZ4HC_Insert (ctxPtr, ctxPtr->end-3);   /* Referencing remaining dictionary content */
581
582    /* Only one memory segment for extDict, so any previous extDict is lost at this stage */
583    ctxPtr->lowLimit  = ctxPtr->dictLimit;
584    ctxPtr->dictLimit = (U32)(ctxPtr->end - ctxPtr->base);
585    ctxPtr->dictBase  = ctxPtr->base;
586    ctxPtr->base = newBlock - ctxPtr->dictLimit;
587    ctxPtr->end  = newBlock;
588    ctxPtr->nextToUpdate = ctxPtr->nextToUpdateBT = ctxPtr->dictLimit;   /* match referencing will resume from there */
589}
590
591static int LZ4_compressHC_continue_generic (LZ4_streamHC_t* LZ4_streamHCPtr,
592                                            const char* source, char* dest,
593                                            int inputSize, int maxOutputSize, limitedOutput_directive limit)
594{
595    LZ4HC_CCtx_internal* ctxPtr = &LZ4_streamHCPtr->internal_donotuse;
596    /* auto-init if forgotten */
597    if (ctxPtr->base == NULL) LZ4HC_init (ctxPtr, (const BYTE*) source);
598
599    /* Check overflow */
600    if ((size_t)(ctxPtr->end - ctxPtr->base) > 2 GB) {
601        size_t dictSize = (size_t)(ctxPtr->end - ctxPtr->base) - ctxPtr->dictLimit;
602        if (dictSize > 64 KB) dictSize = 64 KB;
603        LZ4_loadDictHC(LZ4_streamHCPtr, (const char*)(ctxPtr->end) - dictSize, (int)dictSize);
604    }
605
606    /* Check if blocks follow each other */
607    if ((const BYTE*)source != ctxPtr->end) LZ4HC_setExternalDict(ctxPtr, (const BYTE*)source);
608
609    /* Check overlapping input/dictionary space */
610    {   const BYTE* sourceEnd = (const BYTE*) source + inputSize;
611        const BYTE* const dictBegin = ctxPtr->dictBase + ctxPtr->lowLimit;
612        const BYTE* const dictEnd   = ctxPtr->dictBase + ctxPtr->dictLimit;
613        if ((sourceEnd > dictBegin) && ((const BYTE*)source < dictEnd)) {
614            if (sourceEnd > dictEnd) sourceEnd = dictEnd;
615            ctxPtr->lowLimit = (U32)(sourceEnd - ctxPtr->dictBase);
616            if (ctxPtr->dictLimit - ctxPtr->lowLimit < 4) ctxPtr->lowLimit = ctxPtr->dictLimit;
617        }
618    }
619
620    return LZ4HC_compress_generic (ctxPtr, source, dest, inputSize, maxOutputSize, ctxPtr->compressionLevel, limit);
621}
622
623int LZ4_compress_HC_continue (LZ4_streamHC_t* LZ4_streamHCPtr, const char* source, char* dest, int inputSize, int maxOutputSize)
624{
625    if (maxOutputSize < LZ4_compressBound(inputSize))
626        return LZ4_compressHC_continue_generic (LZ4_streamHCPtr, source, dest, inputSize, maxOutputSize, limitedOutput);
627    else
628        return LZ4_compressHC_continue_generic (LZ4_streamHCPtr, source, dest, inputSize, maxOutputSize, noLimit);
629}
630
631
632/* dictionary saving */
633
634int LZ4_saveDictHC (LZ4_streamHC_t* LZ4_streamHCPtr, char* safeBuffer, int dictSize)
635{
636    LZ4HC_CCtx_internal* const streamPtr = &LZ4_streamHCPtr->internal_donotuse;
637    int const prefixSize = (int)(streamPtr->end - (streamPtr->base + streamPtr->dictLimit));
638    if (dictSize > 64 KB) dictSize = 64 KB;
639    if (dictSize < 4) dictSize = 0;
640    if (dictSize > prefixSize) dictSize = prefixSize;
641    memmove(safeBuffer, streamPtr->end - dictSize, dictSize);
642    {   U32 const endIndex = (U32)(streamPtr->end - streamPtr->base);
643        streamPtr->end = (const BYTE*)safeBuffer + dictSize;
644        streamPtr->base = streamPtr->end - endIndex;
645        streamPtr->dictLimit = endIndex - dictSize;
646        streamPtr->lowLimit = endIndex - dictSize;
647        if (streamPtr->nextToUpdate < streamPtr->dictLimit) streamPtr->nextToUpdate = streamPtr->dictLimit;
648        if (streamPtr->nextToUpdateBT < streamPtr->dictLimit) streamPtr->nextToUpdateBT = streamPtr->dictLimit;
649    }
650    return dictSize;
651}
652
653
654/***********************************
655*  Deprecated Functions
656***********************************/
657/* These functions currently generate deprecation warnings */
658/* Deprecated compression functions */
659int LZ4_compressHC(const char* src, char* dst, int srcSize) { return LZ4_compress_HC (src, dst, srcSize, LZ4_compressBound(srcSize), 0); }
660int LZ4_compressHC_limitedOutput(const char* src, char* dst, int srcSize, int maxDstSize) { return LZ4_compress_HC(src, dst, srcSize, maxDstSize, 0); }
661int LZ4_compressHC2(const char* src, char* dst, int srcSize, int cLevel) { return LZ4_compress_HC (src, dst, srcSize, LZ4_compressBound(srcSize), cLevel); }
662int LZ4_compressHC2_limitedOutput(const char* src, char* dst, int srcSize, int maxDstSize, int cLevel) { return LZ4_compress_HC(src, dst, srcSize, maxDstSize, cLevel); }
663int 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); }
664int 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); }
665int 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); }
666int 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); }
667int 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)); }
668int 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); }
669
670
671/* Deprecated streaming functions */
672int LZ4_sizeofStreamStateHC(void) { return LZ4_STREAMHCSIZE; }
673
674int LZ4_resetStreamStateHC(void* state, char* inputBuffer)
675{
676    LZ4HC_CCtx_internal *ctx = &((LZ4_streamHC_t*)state)->internal_donotuse;
677    if ((((size_t)state) & (sizeof(void*)-1)) != 0) return 1;   /* Error : pointer is not aligned for pointer (32 or 64 bits) */
678    LZ4HC_init(ctx, (const BYTE*)inputBuffer);
679    ctx->inputBuffer = (BYTE*)inputBuffer;
680    return 0;
681}
682
683void* LZ4_createHC (char* inputBuffer)
684{
685    LZ4_streamHC_t* hc4 = (LZ4_streamHC_t*)ALLOCATOR(1, sizeof(LZ4_streamHC_t));
686    if (hc4 == NULL) return NULL;   /* not enough memory */
687    LZ4HC_init (&hc4->internal_donotuse, (const BYTE*)inputBuffer);
688    hc4->internal_donotuse.inputBuffer = (BYTE*)inputBuffer;
689    return hc4;
690}
691
692int LZ4_freeHC (void* LZ4HC_Data) { FREEMEM(LZ4HC_Data); return 0; }
693
694int LZ4_compressHC2_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize, int compressionLevel)
695{
696    return LZ4HC_compress_generic (&((LZ4_streamHC_t*)LZ4HC_Data)->internal_donotuse, source, dest, inputSize, 0, compressionLevel, noLimit);
697}
698
699int LZ4_compressHC2_limitedOutput_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize, int maxOutputSize, int compressionLevel)
700{
701    return LZ4HC_compress_generic (&((LZ4_streamHC_t*)LZ4HC_Data)->internal_donotuse, source, dest, inputSize, maxOutputSize, compressionLevel, limitedOutput);
702}
703
704char* LZ4_slideInputBufferHC(void* LZ4HC_Data)
705{
706    LZ4HC_CCtx_internal* const hc4 = &((LZ4_streamHC_t*)LZ4HC_Data)->internal_donotuse;
707    int const dictSize = LZ4_saveDictHC((LZ4_streamHC_t*)LZ4HC_Data, (char*)(hc4->inputBuffer), 64 KB);
708    return (char*)(hc4->inputBuffer + dictSize);
709}
710