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