lib/lz4/lz4hc_compress.c - kernel/common - Git at Google

 /*
  * LZ4 HC - High Compression Mode of LZ4
  * Copyright (C) 2011-2015, Yann Collet.
  *
  * BSD 2 - Clause License (http://www.opensource.org/licenses/bsd - license.php)
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions are
  * met:
  *	* Redistributions of source code must retain the above copyright
  *	  notice, this list of conditions and the following disclaimer.
  *	* Redistributions in binary form must reproduce the above
  * copyright notice, this list of conditions and the following disclaimer
  * in the documentation and/or other materials provided with the
  * distribution.
  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  * You can contact the author at :
  *	- LZ4 homepage : http://www.lz4.org
  *	- LZ4 source repository : https://github.com/lz4/lz4
  *
  *	Changed for kernel usage by:
  *	Sven Schmidt <[email protected]>
  */

 /*-************************************
  *	Dependencies
  **************************************/
 #include <linux/lz4.h>
 #include "lz4defs.h"
 #include <linux/module.h>
 #include <linux/kernel.h>
 #include <linux/string.h> /* memset */

 /* *************************************
  *	Local Constants and types
  ***************************************/

 #define OPTIMAL_ML (int)((ML_MASK - 1) + MINMATCH)

 #define HASH_FUNCTION(i)	(((i) * 2654435761U) \
 	>> ((MINMATCH*8) - LZ4HC_HASH_LOG))
 #define DELTANEXTU16(p)	chainTable[(U16)(p)] /* faster */

 static U32 LZ4HC_hashPtr(const void *ptr)
 {
 	return HASH_FUNCTION(LZ4_read32(ptr));
 }

 /**************************************
  *	HC Compression
  **************************************/
 static void LZ4HC_init(LZ4HC_CCtx_internal *hc4, const BYTE *start)
 {
 	memset((void *)hc4->hashTable, 0, sizeof(hc4->hashTable));
 	memset(hc4->chainTable, 0xFF, sizeof(hc4->chainTable));
 	hc4->nextToUpdate = 64 * KB;
 	hc4->base = start - 64 * KB;
 	hc4->end = start;
 	hc4->dictBase = start - 64 * KB;
 	hc4->dictLimit = 64 * KB;
 	hc4->lowLimit = 64 * KB;
 }

 /* Update chains up to ip (excluded) */
 static FORCE_INLINE void LZ4HC_Insert(LZ4HC_CCtx_internal *hc4,
 	const BYTE *ip)
 {
 	U16 * const chainTable = hc4->chainTable;
 	U32 * const hashTable	= hc4->hashTable;
 	const BYTE * const base = hc4->base;
 	U32 const target = (U32)(ip - base);
 	U32 idx = hc4->nextToUpdate;

 	while (idx < target) {
 		U32 const h = LZ4HC_hashPtr(base + idx);
 		size_t delta = idx - hashTable[h];

 		if (delta > MAX_DISTANCE)
 			delta = MAX_DISTANCE;

 		DELTANEXTU16(idx) = (U16)delta;

 		hashTable[h] = idx;
 		idx++;
 	}

 	hc4->nextToUpdate = target;
 }

 static FORCE_INLINE int LZ4HC_InsertAndFindBestMatch(
 	LZ4HC_CCtx_internal *hc4, /* Index table will be updated */
 	const BYTE *ip,
 	const BYTE * const iLimit,
 	const BYTE **matchpos,
 	const int maxNbAttempts)
 {
 	U16 * const chainTable = hc4->chainTable;
 	U32 * const HashTable = hc4->hashTable;
 	const BYTE * const base = hc4->base;
 	const BYTE * const dictBase = hc4->dictBase;
 	const U32 dictLimit = hc4->dictLimit;
 	const U32 lowLimit = (hc4->lowLimit + 64 * KB > (U32)(ip - base))
 		? hc4->lowLimit
 		: (U32)(ip - base) - (64 * KB - 1);
 	U32 matchIndex;
 	int nbAttempts = maxNbAttempts;
 	size_t ml = 0;

 	/* HC4 match finder */
 	LZ4HC_Insert(hc4, ip);
 	matchIndex = HashTable[LZ4HC_hashPtr(ip)];

 	while ((matchIndex >= lowLimit)
 		&& (nbAttempts)) {
 		nbAttempts--;
 		if (matchIndex >= dictLimit) {
 			const BYTE * const match = base + matchIndex;

 			if (*(match + ml) == *(ip + ml)
 				&& (LZ4_read32(match) == LZ4_read32(ip))) {
 				size_t const mlt = LZ4_count(ip + MINMATCH,
 					match + MINMATCH, iLimit) + MINMATCH;

 				if (mlt > ml) {
 					ml = mlt;
 					*matchpos = match;
 				}
 			}
 		} else {
 			const BYTE * const match = dictBase + matchIndex;

 			if (LZ4_read32(match) == LZ4_read32(ip)) {
 				size_t mlt;
 				const BYTE *vLimit = ip
 					+ (dictLimit - matchIndex);

 				if (vLimit > iLimit)
 					vLimit = iLimit;
 				mlt = LZ4_count(ip + MINMATCH,
 					match + MINMATCH, vLimit) + MINMATCH;
 				if ((ip + mlt == vLimit)
 					&& (vLimit < iLimit))
 					mlt += LZ4_count(ip + mlt,
 						base + dictLimit,
 						iLimit);
 				if (mlt > ml) {
 					/* virtual matchpos */
 					ml = mlt;
 					*matchpos = base + matchIndex;
 				}
 			}
 		}
 		matchIndex -= DELTANEXTU16(matchIndex);
 	}

 	return (int)ml;
 }

 static FORCE_INLINE int LZ4HC_InsertAndGetWiderMatch(
 	LZ4HC_CCtx_internal *hc4,
 	const BYTE * const ip,
 	const BYTE * const iLowLimit,
 	const BYTE * const iHighLimit,
 	int longest,
 	const BYTE **matchpos,
 	const BYTE **startpos,
 	const int maxNbAttempts)
 {
 	U16 * const chainTable = hc4->chainTable;
 	U32 * const HashTable = hc4->hashTable;
 	const BYTE * const base = hc4->base;
 	const U32 dictLimit = hc4->dictLimit;
 	const BYTE * const lowPrefixPtr = base + dictLimit;
 	const U32 lowLimit = (hc4->lowLimit + 64 * KB > (U32)(ip - base))
 		? hc4->lowLimit
 		: (U32)(ip - base) - (64 * KB - 1);
 	const BYTE * const dictBase = hc4->dictBase;
 	U32 matchIndex;
 	int nbAttempts = maxNbAttempts;
 	int delta = (int)(ip - iLowLimit);

 	/* First Match */
 	LZ4HC_Insert(hc4, ip);
 	matchIndex = HashTable[LZ4HC_hashPtr(ip)];

 	while ((matchIndex >= lowLimit)
 		&& (nbAttempts)) {
 		nbAttempts--;
 		if (matchIndex >= dictLimit) {
 			const BYTE *matchPtr = base + matchIndex;

 			if (*(iLowLimit + longest)
 				== *(matchPtr - delta + longest)) {
 				if (LZ4_read32(matchPtr) == LZ4_read32(ip)) {
 					int mlt = MINMATCH + LZ4_count(
 						ip + MINMATCH,
 						matchPtr + MINMATCH,
 						iHighLimit);
 					int back = 0;

 					while ((ip + back > iLowLimit)
 						&& (matchPtr + back > lowPrefixPtr)
 						&& (ip[back - 1] == matchPtr[back - 1]))
 						back--;

 					mlt -= back;

 					if (mlt > longest) {
 						longest = (int)mlt;
 						*matchpos = matchPtr + back;
 						*startpos = ip + back;
 					}
 				}
 			}
 		} else {
 			const BYTE * const matchPtr = dictBase + matchIndex;

 			if (LZ4_read32(matchPtr) == LZ4_read32(ip)) {
 				size_t mlt;
 				int back = 0;
 				const BYTE *vLimit = ip + (dictLimit - matchIndex);

 				if (vLimit > iHighLimit)
 					vLimit = iHighLimit;

 				mlt = LZ4_count(ip + MINMATCH,
 					matchPtr + MINMATCH, vLimit) + MINMATCH;

 				if ((ip + mlt == vLimit) && (vLimit < iHighLimit))
 					mlt += LZ4_count(ip + mlt, base + dictLimit,
 						iHighLimit);
 				while ((ip + back > iLowLimit)
 					&& (matchIndex + back > lowLimit)
 					&& (ip[back - 1] == matchPtr[back - 1]))
 					back--;

 				mlt -= back;

 				if ((int)mlt > longest) {
 					longest = (int)mlt;
 					*matchpos = base + matchIndex + back;
 					*startpos = ip + back;
 				}
 			}
 		}

 		matchIndex -= DELTANEXTU16(matchIndex);
 	}

 	return longest;
 }

 static FORCE_INLINE int LZ4HC_encodeSequence(
 	const BYTE **ip,
 	BYTE **op,
 	const BYTE **anchor,
 	int matchLength,
 	const BYTE * const match,
 	limitedOutput_directive limitedOutputBuffer,
 	BYTE *oend)
 {
 	int length;
 	BYTE *token;

 	/* Encode Literal length */
 	length = (int)(*ip - *anchor);
 	token = (*op)++;

 	if ((limitedOutputBuffer)
 		&& ((*op + (length>>8)
 			+ length + (2 + 1 + LASTLITERALS)) > oend)) {
 		/* Check output limit */
 		return 1;
 	}
 	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;
 	} else
 		*token = (BYTE)(length<<ML_BITS);

 	/* Copy Literals */
 	LZ4_wildCopy(*op, *anchor, (*op) + length);
 	*op += length;

 	/* Encode Offset */
 	LZ4_writeLE16(*op, (U16)(*ip - match));
 	*op += 2;

 	/* Encode MatchLength */
 	length = (int)(matchLength - MINMATCH);

 	if ((limitedOutputBuffer)
 		&& (*op + (length>>8)
 			+ (1 + LASTLITERALS) > oend)) {
 		/* Check output limit */
 		return 1;
 	}

 	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;
 	} else
 		*token += (BYTE)(length);

 	/* Prepare next loop */
 	*ip += matchLength;
 	*anchor = *ip;

 	return 0;
 }

 static int LZ4HC_compress_generic(
 	LZ4HC_CCtx_internal *const ctx,
 	const char * const source,
 	char * const dest,
 	int const inputSize,
 	int const maxOutputSize,
 	int compressionLevel,
 	limitedOutput_directive limit
 	)
 {
 	const BYTE *ip = (const BYTE *) source;
 	const BYTE *anchor = ip;
 	const BYTE * const iend = ip + inputSize;
 	const BYTE * const mflimit = iend - MFLIMIT;
 	const BYTE * const matchlimit = (iend - LASTLITERALS);

 	BYTE *op = (BYTE *) dest;
 	BYTE * const oend = op + maxOutputSize;

 	unsigned int maxNbAttempts;
 	int ml, ml2, ml3, ml0;
 	const BYTE *ref = NULL;
 	const BYTE *start2 = NULL;
 	const BYTE *ref2 = NULL;
 	const BYTE *start3 = NULL;
 	const BYTE *ref3 = NULL;
 	const BYTE *start0;
 	const BYTE *ref0;

 	/* init */
 	if (compressionLevel > LZ4HC_MAX_CLEVEL)
 		compressionLevel = LZ4HC_MAX_CLEVEL;
 	if (compressionLevel < 1)
 		compressionLevel = LZ4HC_DEFAULT_CLEVEL;
 	maxNbAttempts = 1 << (compressionLevel - 1);
 	ctx->end += inputSize;

 	ip++;

 	/* Main Loop */
 	while (ip < mflimit) {
 		ml = LZ4HC_InsertAndFindBestMatch(ctx, ip,
 			matchlimit, (&ref), maxNbAttempts);
 		if (!ml) {
 			ip++;
 			continue;
 		}

 		/* saved, in case we would skip too much */
 		start0 = ip;
 		ref0 = ref;
 		ml0 = ml;

 _Search2:
 		if (ip + ml < mflimit)
 			ml2 = LZ4HC_InsertAndGetWiderMatch(ctx,
 				ip + ml - 2, ip + 0,
 				matchlimit, ml, &ref2,
 				&start2, maxNbAttempts);
 		else
 			ml2 = ml;

 		if (ml2 == ml) {
 			/* No better match */
 			if (LZ4HC_encodeSequence(&ip, &op,
 				&anchor, ml, ref, limit, oend))
 				return 0;
 			continue;
 		}

 		if (start0 < ip) {
 			if (start2 < ip + ml0) {
 				/* empirical */
 				ip = start0;
 				ref = ref0;
 				ml = ml0;
 			}
 		}

 		/* Here, start0 == ip */
 		if ((start2 - ip) < 3) {
 			/* First Match too small : removed */
 			ml = ml2;
 			ip = start2;
 			ref = ref2;
 			goto _Search2;
 		}

 _Search3:
 		/*
 		* Currently we have :
 		* ml2 > ml1, and
 		* ip1 + 3 <= ip2 (usually < ip1 + ml1)
 		*/
 		if ((start2 - ip) < OPTIMAL_ML) {
 			int correction;
 			int new_ml = ml;

 			if (new_ml > OPTIMAL_ML)
 				new_ml = OPTIMAL_ML;
 			if (ip + new_ml > start2 + ml2 - MINMATCH)
 				new_ml = (int)(start2 - ip) + ml2 - MINMATCH;

 			correction = new_ml - (int)(start2 - ip);

 			if (correction > 0) {
 				start2 += correction;
 				ref2 += correction;
 				ml2 -= correction;
 			}
 		}
 		/*
 		 * Now, we have start2 = ip + new_ml,
 		 * with new_ml = min(ml, OPTIMAL_ML = 18)
 		 */

 		if (start2 + ml2 < mflimit)
 			ml3 = LZ4HC_InsertAndGetWiderMatch(ctx,
 				start2 + ml2 - 3, start2,
 				matchlimit, ml2, &ref3, &start3,
 				maxNbAttempts);
 		else
 			ml3 = ml2;

 		if (ml3 == ml2) {
 			/* No better match : 2 sequences to encode */
 			/* ip & ref are known; Now for ml */
 			if (start2 < ip + ml)
 				ml = (int)(start2 - ip);
 			/* Now, encode 2 sequences */
 			if (LZ4HC_encodeSequence(&ip, &op, &anchor,
 				ml, ref, limit, oend))
 				return 0;
 			ip = start2;
 			if (LZ4HC_encodeSequence(&ip, &op, &anchor,
 				ml2, ref2, limit, oend))
 				return 0;
 			continue;
 		}

 		if (start3 < ip + ml + 3) {
 			/* Not enough space for match 2 : remove it */
 			if (start3 >= (ip + ml)) {
 				/* can write Seq1 immediately
 				 * ==> Seq2 is removed,
 				 * so Seq3 becomes Seq1
 				 */
 				if (start2 < ip + ml) {
 					int correction = (int)(ip + ml - start2);

 					start2 += correction;
 					ref2 += correction;
 					ml2 -= correction;
 					if (ml2 < MINMATCH) {
 						start2 = start3;
 						ref2 = ref3;
 						ml2 = ml3;
 					}
 				}

 				if (LZ4HC_encodeSequence(&ip, &op, &anchor,
 					ml, ref, limit, oend))
 					return 0;
 				ip = start3;
 				ref = ref3;
 				ml = ml3;

 				start0 = start2;
 				ref0 = ref2;
 				ml0 = ml2;
 				goto _Search2;
 			}

 			start2 = start3;
 			ref2 = ref3;
 			ml2 = ml3;
 			goto _Search3;
 		}

 		/*
 		* OK, now we have 3 ascending matches;
 		* let's write at least the first one
 		* ip & ref are known; Now for ml
 		*/
 		if (start2 < ip + ml) {
 			if ((start2 - ip) < (int)ML_MASK) {
 				int correction;

 				if (ml > OPTIMAL_ML)
 					ml = OPTIMAL_ML;
 				if (ip + ml > start2 + ml2 - MINMATCH)
 					ml = (int)(start2 - ip) + ml2 - MINMATCH;
 				correction = ml - (int)(start2 - ip);
 				if (correction > 0) {
 					start2 += correction;
 					ref2 += correction;
 					ml2 -= correction;
 				}
 			} else
 				ml = (int)(start2 - ip);
 		}
 		if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml,
 			ref, limit, oend))
 			return 0;

 		ip = start2;
 		ref = ref2;
 		ml = ml2;

 		start2 = start3;
 		ref2 = ref3;
 		ml2 = ml3;

 		goto _Search3;
 	}

 	/* Encode Last Literals */
 	{
 		int lastRun = (int)(iend - anchor);

 		if ((limit)
 			&& (((char *)op - dest) + lastRun + 1
 				+ ((lastRun + 255 - RUN_MASK)/255)
 					> (U32)maxOutputSize)) {
 			/* Check output limit */
 			return 0;
 		}
 		if (lastRun >= (int)RUN_MASK) {
 			*op++ = (RUN_MASK<<ML_BITS);
 			lastRun -= RUN_MASK;
 			for (; lastRun > 254 ; lastRun -= 255)
 				*op++ = 255;
 			*op++ = (BYTE) lastRun;
 		} else
 			*op++ = (BYTE)(lastRun<<ML_BITS);
 		memcpy(op, anchor, iend - anchor);
 		op += iend - anchor;
 	}

 	/* End */
 	return (int) (((char *)op) - dest);
 }

 static int LZ4_compress_HC_extStateHC(
 	void *state,
 	const char *src,
 	char *dst,
 	int srcSize,
 	int maxDstSize,
 	int compressionLevel)
 {
 	LZ4HC_CCtx_internal *ctx = &((LZ4_streamHC_t *)state)->internal_donotuse;

 	if (((size_t)(state)&(sizeof(void *) - 1)) != 0) {
 		/* Error : state is not aligned
 		 * for pointers (32 or 64 bits)
 		 */
 		return 0;
 	}

 	LZ4HC_init(ctx, (const BYTE *)src);

 	if (maxDstSize < LZ4_compressBound(srcSize))
 		return LZ4HC_compress_generic(ctx, src, dst,
 			srcSize, maxDstSize, compressionLevel, limitedOutput);
 	else
 		return LZ4HC_compress_generic(ctx, src, dst,
 			srcSize, maxDstSize, compressionLevel, noLimit);
 }

 int LZ4_compress_HC(const char *src, char *dst, int srcSize,
 	int maxDstSize, int compressionLevel, void *wrkmem)
 {
 	return LZ4_compress_HC_extStateHC(wrkmem, src, dst,
 		srcSize, maxDstSize, compressionLevel);
 }
 EXPORT_SYMBOL(LZ4_compress_HC);

 /**************************************
  *	Streaming Functions
  **************************************/
 void LZ4_resetStreamHC(LZ4_streamHC_t *LZ4_streamHCPtr, int compressionLevel)
 {
 	LZ4_streamHCPtr->internal_donotuse.base = NULL;
 	LZ4_streamHCPtr->internal_donotuse.compressionLevel = (unsigned int)compressionLevel;
 }

 int LZ4_loadDictHC(LZ4_streamHC_t *LZ4_streamHCPtr,
 	const char *dictionary,
 	int dictSize)
 {
 	LZ4HC_CCtx_internal *ctxPtr = &LZ4_streamHCPtr->internal_donotuse;

 	if (dictSize > 64 * KB) {
 		dictionary += dictSize - 64 * KB;
 		dictSize = 64 * KB;
 	}
 	LZ4HC_init(ctxPtr, (const BYTE *)dictionary);
 	if (dictSize >= 4)
 		LZ4HC_Insert(ctxPtr, (const BYTE *)dictionary + (dictSize - 3));
 	ctxPtr->end = (const BYTE *)dictionary + dictSize;
 	return dictSize;
 }
 EXPORT_SYMBOL(LZ4_loadDictHC);

 /* compression */

 static void LZ4HC_setExternalDict(
 	LZ4HC_CCtx_internal *ctxPtr,
 	const BYTE *newBlock)
 {
 	if (ctxPtr->end >= ctxPtr->base + 4) {
 		/* Referencing remaining dictionary content */
 		LZ4HC_Insert(ctxPtr, ctxPtr->end - 3);
 	}

 	/*
 	 * Only one memory segment for extDict,
 	 * so any previous extDict is lost at this stage
 	 */
 	ctxPtr->lowLimit	= ctxPtr->dictLimit;
 	ctxPtr->dictLimit = (U32)(ctxPtr->end - ctxPtr->base);
 	ctxPtr->dictBase	= ctxPtr->base;
 	ctxPtr->base = newBlock - ctxPtr->dictLimit;
 	ctxPtr->end	= newBlock;
 	/* match referencing will resume from there */
 	ctxPtr->nextToUpdate = ctxPtr->dictLimit;
 }
 EXPORT_SYMBOL(LZ4HC_setExternalDict);

 static int LZ4_compressHC_continue_generic(
 	LZ4_streamHC_t *LZ4_streamHCPtr,
 	const char *source,
 	char *dest,
 	int inputSize,
 	int maxOutputSize,
 	limitedOutput_directive limit)
 {
 	LZ4HC_CCtx_internal *ctxPtr = &LZ4_streamHCPtr->internal_donotuse;

 	/* auto - init if forgotten */
 	if (ctxPtr->base == NULL)
 		LZ4HC_init(ctxPtr, (const BYTE *) source);

 	/* Check overflow */
 	if ((size_t)(ctxPtr->end - ctxPtr->base) > 2 * GB) {
 		size_t dictSize = (size_t)(ctxPtr->end - ctxPtr->base)
 			- ctxPtr->dictLimit;
 		if (dictSize > 64 * KB)
 			dictSize = 64 * KB;
 		LZ4_loadDictHC(LZ4_streamHCPtr,
 			(const char *)(ctxPtr->end) - dictSize, (int)dictSize);
 	}

 	/* Check if blocks follow each other */
 	if ((const BYTE *)source != ctxPtr->end)
 		LZ4HC_setExternalDict(ctxPtr, (const BYTE *)source);

 	/* Check overlapping input/dictionary space */
 	{
 		const BYTE *sourceEnd = (const BYTE *) source + inputSize;
 		const BYTE * const dictBegin = ctxPtr->dictBase + ctxPtr->lowLimit;
 		const BYTE * const dictEnd = ctxPtr->dictBase + ctxPtr->dictLimit;

 		if ((sourceEnd > dictBegin)
 			&& ((const BYTE *)source < dictEnd)) {
 			if (sourceEnd > dictEnd)
 				sourceEnd = dictEnd;
 			ctxPtr->lowLimit = (U32)(sourceEnd - ctxPtr->dictBase);

 			if (ctxPtr->dictLimit - ctxPtr->lowLimit < 4)
 				ctxPtr->lowLimit = ctxPtr->dictLimit;
 		}
 	}

 	return LZ4HC_compress_generic(ctxPtr, source, dest,
 		inputSize, maxOutputSize, ctxPtr->compressionLevel, limit);
 }

 int LZ4_compress_HC_continue(
 	LZ4_streamHC_t *LZ4_streamHCPtr,
 	const char *source,
 	char *dest,
 	int inputSize,
 	int maxOutputSize)
 {
 	if (maxOutputSize < LZ4_compressBound(inputSize))
 		return LZ4_compressHC_continue_generic(LZ4_streamHCPtr,
 			source, dest, inputSize, maxOutputSize, limitedOutput);
 	else
 		return LZ4_compressHC_continue_generic(LZ4_streamHCPtr,
 			source, dest, inputSize, maxOutputSize, noLimit);
 }
 EXPORT_SYMBOL(LZ4_compress_HC_continue);

 /* dictionary saving */

 int LZ4_saveDictHC(
 	LZ4_streamHC_t *LZ4_streamHCPtr,
 	char *safeBuffer,
 	int dictSize)
 {
 	LZ4HC_CCtx_internal *const streamPtr = &LZ4_streamHCPtr->internal_donotuse;
 	int const prefixSize = (int)(streamPtr->end
 		- (streamPtr->base + streamPtr->dictLimit));

 	if (dictSize > 64 * KB)
 		dictSize = 64 * KB;
 	if (dictSize < 4)
 		dictSize = 0;
 	if (dictSize > prefixSize)
 		dictSize = prefixSize;

 	memmove(safeBuffer, streamPtr->end - dictSize, dictSize);

 	{
 		U32 const endIndex = (U32)(streamPtr->end - streamPtr->base);

 		streamPtr->end = (const BYTE *)safeBuffer + dictSize;
 		streamPtr->base = streamPtr->end - endIndex;
 		streamPtr->dictLimit = endIndex - dictSize;
 		streamPtr->lowLimit = endIndex - dictSize;

 		if (streamPtr->nextToUpdate < streamPtr->dictLimit)
 			streamPtr->nextToUpdate = streamPtr->dictLimit;
 	}
 	return dictSize;
 }
 EXPORT_SYMBOL(LZ4_saveDictHC);

 MODULE_LICENSE("Dual BSD/GPL");
 MODULE_DESCRIPTION("LZ4 HC compressor");
	/*
	* LZ4 HC - High Compression Mode of LZ4
	* Copyright (C) 2011-2015, Yann Collet.
	*
	* BSD 2 - Clause License (http://www.opensource.org/licenses/bsd - license.php)
	* Redistribution and use in source and binary forms, with or without
	* modification, are permitted provided that the following conditions are
	* met:
	* * Redistributions of source code must retain the above copyright
	* notice, this list of conditions and the following disclaimer.
	* * Redistributions in binary form must reproduce the above
	* copyright notice, this list of conditions and the following disclaimer
	* in the documentation and/or other materials provided with the
	* distribution.
	* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
	* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
	* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
	* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
	* OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
	* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
	* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
	* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
	* You can contact the author at :
	* - LZ4 homepage : http://www.lz4.org
	* - LZ4 source repository : https://github.com/lz4/lz4
	*
	* Changed for kernel usage by:
	* Sven Schmidt <[email protected]>
	*/

	/-***********************************
	* Dependencies
	**************************************/
	#include <linux/lz4.h>
	#include "lz4defs.h"
	#include <linux/module.h>
	#include <linux/kernel.h>
	#include <linux/string.h> /* memset */

	/* *************************************
	* Local Constants and types
	***************************************/

	#define OPTIMAL_ML (int)((ML_MASK - 1) + MINMATCH)

	#define HASH_FUNCTION(i) (((i) * 2654435761U) \
	>> ((MINMATCH*8) - LZ4HC_HASH_LOG))
	#define DELTANEXTU16(p) chainTable[(U16)(p)] /* faster */

	static U32 LZ4HC_hashPtr(const void *ptr)
	{
	return HASH_FUNCTION(LZ4_read32(ptr));
	}

	/**************************************
	* HC Compression
	**************************************/
	static void LZ4HC_init(LZ4HC_CCtx_internal hc4, const BYTE start)
	{
	memset((void *)hc4->hashTable, 0, sizeof(hc4->hashTable));
	memset(hc4->chainTable, 0xFF, sizeof(hc4->chainTable));
	hc4->nextToUpdate = 64 * KB;
	hc4->base = start - 64 * KB;
	hc4->end = start;
	hc4->dictBase = start - 64 * KB;
	hc4->dictLimit = 64 * KB;
	hc4->lowLimit = 64 * KB;
	}

	/* Update chains up to ip (excluded) */
	static FORCE_INLINE void LZ4HC_Insert(LZ4HC_CCtx_internal *hc4,
	const BYTE *ip)
	{
	U16 * const chainTable = hc4->chainTable;
	U32 * const hashTable = hc4->hashTable;
	const BYTE * const base = hc4->base;
	U32 const target = (U32)(ip - base);
	U32 idx = hc4->nextToUpdate;

	while (idx < target) {
	U32 const h = LZ4HC_hashPtr(base + idx);
	size_t delta = idx - hashTable[h];

	if (delta > MAX_DISTANCE)
	delta = MAX_DISTANCE;

	DELTANEXTU16(idx) = (U16)delta;

	hashTable[h] = idx;
	idx++;
	}

	hc4->nextToUpdate = target;
	}

	static FORCE_INLINE int LZ4HC_InsertAndFindBestMatch(
	LZ4HC_CCtx_internal hc4, / Index table will be updated */
	const BYTE *ip,
	const BYTE * const iLimit,
	const BYTE **matchpos,
	const int maxNbAttempts)
	{
	U16 * const chainTable = hc4->chainTable;
	U32 * const HashTable = hc4->hashTable;
	const BYTE * const base = hc4->base;
	const BYTE * const dictBase = hc4->dictBase;
	const U32 dictLimit = hc4->dictLimit;
	const U32 lowLimit = (hc4->lowLimit + 64 * KB > (U32)(ip - base))
	? hc4->lowLimit
	: (U32)(ip - base) - (64 * KB - 1);
	U32 matchIndex;
	int nbAttempts = maxNbAttempts;
	size_t ml = 0;

	/* HC4 match finder */
	LZ4HC_Insert(hc4, ip);
	matchIndex = HashTable[LZ4HC_hashPtr(ip)];

	while ((matchIndex >= lowLimit)
	&& (nbAttempts)) {
	nbAttempts--;
	if (matchIndex >= dictLimit) {
	const BYTE * const match = base + matchIndex;

	if ((match + ml) == (ip + ml)
	&& (LZ4_read32(match) == LZ4_read32(ip))) {
	size_t const mlt = LZ4_count(ip + MINMATCH,
	match + MINMATCH, iLimit) + MINMATCH;

	if (mlt > ml) {
	ml = mlt;
	*matchpos = match;
	}
	}
	} else {
	const BYTE * const match = dictBase + matchIndex;

	if (LZ4_read32(match) == LZ4_read32(ip)) {
	size_t mlt;
	const BYTE *vLimit = ip
	+ (dictLimit - matchIndex);

	if (vLimit > iLimit)
	vLimit = iLimit;
	mlt = LZ4_count(ip + MINMATCH,
	match + MINMATCH, vLimit) + MINMATCH;
	if ((ip + mlt == vLimit)
	&& (vLimit < iLimit))
	mlt += LZ4_count(ip + mlt,
	base + dictLimit,
	iLimit);
	if (mlt > ml) {
	/* virtual matchpos */
	ml = mlt;
	*matchpos = base + matchIndex;
	}
	}
	}
	matchIndex -= DELTANEXTU16(matchIndex);
	}

	return (int)ml;
	}

	static FORCE_INLINE int LZ4HC_InsertAndGetWiderMatch(
	LZ4HC_CCtx_internal *hc4,
	const BYTE * const ip,
	const BYTE * const iLowLimit,
	const BYTE * const iHighLimit,
	int longest,
	const BYTE **matchpos,
	const BYTE **startpos,
	const int maxNbAttempts)
	{
	U16 * const chainTable = hc4->chainTable;
	U32 * const HashTable = hc4->hashTable;
	const BYTE * const base = hc4->base;
	const U32 dictLimit = hc4->dictLimit;
	const BYTE * const lowPrefixPtr = base + dictLimit;
	const U32 lowLimit = (hc4->lowLimit + 64 * KB > (U32)(ip - base))
	? hc4->lowLimit
	: (U32)(ip - base) - (64 * KB - 1);
	const BYTE * const dictBase = hc4->dictBase;
	U32 matchIndex;
	int nbAttempts = maxNbAttempts;
	int delta = (int)(ip - iLowLimit);

	/* First Match */
	LZ4HC_Insert(hc4, ip);
	matchIndex = HashTable[LZ4HC_hashPtr(ip)];

	while ((matchIndex >= lowLimit)
	&& (nbAttempts)) {
	nbAttempts--;
	if (matchIndex >= dictLimit) {
	const BYTE *matchPtr = base + matchIndex;

	if (*(iLowLimit + longest)
	== *(matchPtr - delta + longest)) {
	if (LZ4_read32(matchPtr) == LZ4_read32(ip)) {
	int mlt = MINMATCH + LZ4_count(
	ip + MINMATCH,
	matchPtr + MINMATCH,
	iHighLimit);
	int back = 0;

	while ((ip + back > iLowLimit)
	&& (matchPtr + back > lowPrefixPtr)
	&& (ip[back - 1] == matchPtr[back - 1]))
	back--;

	mlt -= back;

	if (mlt > longest) {
	longest = (int)mlt;
	*matchpos = matchPtr + back;
	*startpos = ip + back;
	}
	}
	}
	} else {
	const BYTE * const matchPtr = dictBase + matchIndex;

	if (LZ4_read32(matchPtr) == LZ4_read32(ip)) {
	size_t mlt;
	int back = 0;
	const BYTE *vLimit = ip + (dictLimit - matchIndex);

	if (vLimit > iHighLimit)
	vLimit = iHighLimit;

	mlt = LZ4_count(ip + MINMATCH,
	matchPtr + MINMATCH, vLimit) + MINMATCH;

	if ((ip + mlt == vLimit) && (vLimit < iHighLimit))
	mlt += LZ4_count(ip + mlt, base + dictLimit,
	iHighLimit);
	while ((ip + back > iLowLimit)
	&& (matchIndex + back > lowLimit)
	&& (ip[back - 1] == matchPtr[back - 1]))
	back--;

	mlt -= back;

	if ((int)mlt > longest) {
	longest = (int)mlt;
	*matchpos = base + matchIndex + back;
	*startpos = ip + back;
	}
	}
	}

	matchIndex -= DELTANEXTU16(matchIndex);
	}

	return longest;
	}

	static FORCE_INLINE int LZ4HC_encodeSequence(
	const BYTE **ip,
	BYTE **op,
	const BYTE **anchor,
	int matchLength,
	const BYTE * const match,
	limitedOutput_directive limitedOutputBuffer,
	BYTE *oend)
	{
	int length;
	BYTE *token;

	/* Encode Literal length */
	length = (int)(ip - anchor);
	token = (*op)++;

	if ((limitedOutputBuffer)
	&& ((*op + (length>>8)
	+ length + (2 + 1 + LASTLITERALS)) > oend)) {
	/* Check output limit */
	return 1;
	}
	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;
	} else
	*token = (BYTE)(length<<ML_BITS);

	/* Copy Literals */
	LZ4_wildCopy(op, anchor, (*op) + length);
	*op += length;

	/* Encode Offset */
	LZ4_writeLE16(op, (U16)(ip - match));
	*op += 2;

	/* Encode MatchLength */
	length = (int)(matchLength - MINMATCH);

	if ((limitedOutputBuffer)
	&& (*op + (length>>8)
	+ (1 + LASTLITERALS) > oend)) {
	/* Check output limit */
	return 1;
	}

	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;
	} else
	*token += (BYTE)(length);

	/* Prepare next loop */
	*ip += matchLength;
	anchor = ip;

	return 0;
	}

	static int LZ4HC_compress_generic(
	LZ4HC_CCtx_internal *const ctx,
	const char * const source,
	char * const dest,
	int const inputSize,
	int const maxOutputSize,
	int compressionLevel,
	limitedOutput_directive limit
	)
	{
	const BYTE ip = (const BYTE ) source;
	const BYTE *anchor = ip;
	const BYTE * const iend = ip + inputSize;
	const BYTE * const mflimit = iend - MFLIMIT;
	const BYTE * const matchlimit = (iend - LASTLITERALS);

	BYTE op = (BYTE ) dest;
	BYTE * const oend = op + maxOutputSize;

	unsigned int maxNbAttempts;
	int ml, ml2, ml3, ml0;
	const BYTE *ref = NULL;
	const BYTE *start2 = NULL;
	const BYTE *ref2 = NULL;
	const BYTE *start3 = NULL;
	const BYTE *ref3 = NULL;
	const BYTE *start0;
	const BYTE *ref0;

	/* init */
	if (compressionLevel > LZ4HC_MAX_CLEVEL)
	compressionLevel = LZ4HC_MAX_CLEVEL;
	if (compressionLevel < 1)
	compressionLevel = LZ4HC_DEFAULT_CLEVEL;
	maxNbAttempts = 1 << (compressionLevel - 1);
	ctx->end += inputSize;

	ip++;

	/* Main Loop */
	while (ip < mflimit) {
	ml = LZ4HC_InsertAndFindBestMatch(ctx, ip,
	matchlimit, (&ref), maxNbAttempts);
	if (!ml) {
	ip++;
	continue;
	}

	/* saved, in case we would skip too much */
	start0 = ip;
	ref0 = ref;
	ml0 = ml;

	_Search2:
	if (ip + ml < mflimit)
	ml2 = LZ4HC_InsertAndGetWiderMatch(ctx,
	ip + ml - 2, ip + 0,
	matchlimit, ml, &ref2,
	&start2, maxNbAttempts);
	else
	ml2 = ml;

	if (ml2 == ml) {
	/* No better match */
	if (LZ4HC_encodeSequence(&ip, &op,
	&anchor, ml, ref, limit, oend))
	return 0;
	continue;
	}

	if (start0 < ip) {
	if (start2 < ip + ml0) {
	/* empirical */
	ip = start0;
	ref = ref0;
	ml = ml0;
	}
	}

	/* Here, start0 == ip */
	if ((start2 - ip) < 3) {
	/* First Match too small : removed */
	ml = ml2;
	ip = start2;
	ref = ref2;
	goto _Search2;
	}

	_Search3:
	/*
	* Currently we have :
	* ml2 > ml1, and
	* ip1 + 3 <= ip2 (usually < ip1 + ml1)
	*/
	if ((start2 - ip) < OPTIMAL_ML) {
	int correction;
	int new_ml = ml;

	if (new_ml > OPTIMAL_ML)
	new_ml = OPTIMAL_ML;
	if (ip + new_ml > start2 + ml2 - MINMATCH)
	new_ml = (int)(start2 - ip) + ml2 - MINMATCH;

	correction = new_ml - (int)(start2 - ip);

	if (correction > 0) {
	start2 += correction;
	ref2 += correction;
	ml2 -= correction;
	}
	}
	/*
	* Now, we have start2 = ip + new_ml,
	* with new_ml = min(ml, OPTIMAL_ML = 18)
	*/

	if (start2 + ml2 < mflimit)
	ml3 = LZ4HC_InsertAndGetWiderMatch(ctx,
	start2 + ml2 - 3, start2,
	matchlimit, ml2, &ref3, &start3,
	maxNbAttempts);
	else
	ml3 = ml2;

	if (ml3 == ml2) {
	/* No better match : 2 sequences to encode */
	/* ip & ref are known; Now for ml */
	if (start2 < ip + ml)
	ml = (int)(start2 - ip);
	/* Now, encode 2 sequences */
	if (LZ4HC_encodeSequence(&ip, &op, &anchor,
	ml, ref, limit, oend))
	return 0;
	ip = start2;
	if (LZ4HC_encodeSequence(&ip, &op, &anchor,
	ml2, ref2, limit, oend))
	return 0;
	continue;
	}

	if (start3 < ip + ml + 3) {
	/* Not enough space for match 2 : remove it */
	if (start3 >= (ip + ml)) {
	/* can write Seq1 immediately
	* ==> Seq2 is removed,
	* so Seq3 becomes Seq1
	*/
	if (start2 < ip + ml) {
	int correction = (int)(ip + ml - start2);

	start2 += correction;
	ref2 += correction;
	ml2 -= correction;
	if (ml2 < MINMATCH) {
	start2 = start3;
	ref2 = ref3;
	ml2 = ml3;
	}
	}

	if (LZ4HC_encodeSequence(&ip, &op, &anchor,
	ml, ref, limit, oend))
	return 0;
	ip = start3;
	ref = ref3;
	ml = ml3;

	start0 = start2;
	ref0 = ref2;
	ml0 = ml2;
	goto _Search2;
	}

	start2 = start3;
	ref2 = ref3;
	ml2 = ml3;
	goto _Search3;
	}

	/*
	* OK, now we have 3 ascending matches;
	* let's write at least the first one
	* ip & ref are known; Now for ml
	*/
	if (start2 < ip + ml) {
	if ((start2 - ip) < (int)ML_MASK) {
	int correction;

	if (ml > OPTIMAL_ML)
	ml = OPTIMAL_ML;
	if (ip + ml > start2 + ml2 - MINMATCH)
	ml = (int)(start2 - ip) + ml2 - MINMATCH;
	correction = ml - (int)(start2 - ip);
	if (correction > 0) {
	start2 += correction;
	ref2 += correction;
	ml2 -= correction;
	}
	} else
	ml = (int)(start2 - ip);
	}
	if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml,
	ref, limit, oend))
	return 0;

	ip = start2;
	ref = ref2;
	ml = ml2;

	start2 = start3;
	ref2 = ref3;
	ml2 = ml3;

	goto _Search3;
	}

	/* Encode Last Literals */
	{
	int lastRun = (int)(iend - anchor);

	if ((limit)
	&& (((char *)op - dest) + lastRun + 1
	+ ((lastRun + 255 - RUN_MASK)/255)
	> (U32)maxOutputSize)) {
	/* Check output limit */
	return 0;
	}
	if (lastRun >= (int)RUN_MASK) {
	*op++ = (RUN_MASK<<ML_BITS);
	lastRun -= RUN_MASK;
	for (; lastRun > 254 ; lastRun -= 255)
	*op++ = 255;
	*op++ = (BYTE) lastRun;
	} else
	*op++ = (BYTE)(lastRun<<ML_BITS);
	memcpy(op, anchor, iend - anchor);
	op += iend - anchor;
	}

	/* End */
	return (int) (((char *)op) - dest);
	}

	static int LZ4_compress_HC_extStateHC(
	void *state,
	const char *src,
	char *dst,
	int srcSize,
	int maxDstSize,
	int compressionLevel)
	{
	LZ4HC_CCtx_internal ctx = &((LZ4_streamHC_t )state)->internal_donotuse;

	if (((size_t)(state)&(sizeof(void *) - 1)) != 0) {
	/* Error : state is not aligned
	* for pointers (32 or 64 bits)
	*/
	return 0;
	}

	LZ4HC_init(ctx, (const BYTE *)src);

	if (maxDstSize < LZ4_compressBound(srcSize))
	return LZ4HC_compress_generic(ctx, src, dst,
	srcSize, maxDstSize, compressionLevel, limitedOutput);
	else
	return LZ4HC_compress_generic(ctx, src, dst,
	srcSize, maxDstSize, compressionLevel, noLimit);
	}

	int LZ4_compress_HC(const char src, char dst, int srcSize,
	int maxDstSize, int compressionLevel, void *wrkmem)
	{
	return LZ4_compress_HC_extStateHC(wrkmem, src, dst,
	srcSize, maxDstSize, compressionLevel);
	}
	EXPORT_SYMBOL(LZ4_compress_HC);

	/**************************************
	* Streaming Functions
	**************************************/
	void LZ4_resetStreamHC(LZ4_streamHC_t *LZ4_streamHCPtr, int compressionLevel)
	{
	LZ4_streamHCPtr->internal_donotuse.base = NULL;
	LZ4_streamHCPtr->internal_donotuse.compressionLevel = (unsigned int)compressionLevel;
	}

	int LZ4_loadDictHC(LZ4_streamHC_t *LZ4_streamHCPtr,
	const char *dictionary,
	int dictSize)
	{
	LZ4HC_CCtx_internal *ctxPtr = &LZ4_streamHCPtr->internal_donotuse;

	if (dictSize > 64 * KB) {
	dictionary += dictSize - 64 * KB;
	dictSize = 64 * KB;
	}
	LZ4HC_init(ctxPtr, (const BYTE *)dictionary);
	if (dictSize >= 4)
	LZ4HC_Insert(ctxPtr, (const BYTE *)dictionary + (dictSize - 3));
	ctxPtr->end = (const BYTE *)dictionary + dictSize;
	return dictSize;
	}
	EXPORT_SYMBOL(LZ4_loadDictHC);

	/* compression */

	static void LZ4HC_setExternalDict(
	LZ4HC_CCtx_internal *ctxPtr,
	const BYTE *newBlock)
	{
	if (ctxPtr->end >= ctxPtr->base + 4) {
	/* Referencing remaining dictionary content */
	LZ4HC_Insert(ctxPtr, ctxPtr->end - 3);
	}

	/*
	* Only one memory segment for extDict,
	* so any previous extDict is lost at this stage
	*/
	ctxPtr->lowLimit = ctxPtr->dictLimit;
	ctxPtr->dictLimit = (U32)(ctxPtr->end - ctxPtr->base);
	ctxPtr->dictBase = ctxPtr->base;
	ctxPtr->base = newBlock - ctxPtr->dictLimit;
	ctxPtr->end = newBlock;
	/* match referencing will resume from there */
	ctxPtr->nextToUpdate = ctxPtr->dictLimit;
	}
	EXPORT_SYMBOL(LZ4HC_setExternalDict);

	static int LZ4_compressHC_continue_generic(
	LZ4_streamHC_t *LZ4_streamHCPtr,
	const char *source,
	char *dest,
	int inputSize,
	int maxOutputSize,
	limitedOutput_directive limit)
	{
	LZ4HC_CCtx_internal *ctxPtr = &LZ4_streamHCPtr->internal_donotuse;

	/* auto - init if forgotten */
	if (ctxPtr->base == NULL)
	LZ4HC_init(ctxPtr, (const BYTE *) source);

	/* Check overflow */
	if ((size_t)(ctxPtr->end - ctxPtr->base) > 2 * GB) {
	size_t dictSize = (size_t)(ctxPtr->end - ctxPtr->base)
	- ctxPtr->dictLimit;
	if (dictSize > 64 * KB)
	dictSize = 64 * KB;
	LZ4_loadDictHC(LZ4_streamHCPtr,
	(const char *)(ctxPtr->end) - dictSize, (int)dictSize);
	}

	/* Check if blocks follow each other */
	if ((const BYTE *)source != ctxPtr->end)
	LZ4HC_setExternalDict(ctxPtr, (const BYTE *)source);

	/* Check overlapping input/dictionary space */
	{
	const BYTE sourceEnd = (const BYTE ) source + inputSize;
	const BYTE * const dictBegin = ctxPtr->dictBase + ctxPtr->lowLimit;
	const BYTE * const dictEnd = ctxPtr->dictBase + ctxPtr->dictLimit;

	if ((sourceEnd > dictBegin)
	&& ((const BYTE *)source < dictEnd)) {
	if (sourceEnd > dictEnd)
	sourceEnd = dictEnd;
	ctxPtr->lowLimit = (U32)(sourceEnd - ctxPtr->dictBase);

	if (ctxPtr->dictLimit - ctxPtr->lowLimit < 4)
	ctxPtr->lowLimit = ctxPtr->dictLimit;
	}
	}

	return LZ4HC_compress_generic(ctxPtr, source, dest,
	inputSize, maxOutputSize, ctxPtr->compressionLevel, limit);
	}

	int LZ4_compress_HC_continue(
	LZ4_streamHC_t *LZ4_streamHCPtr,
	const char *source,
	char *dest,
	int inputSize,
	int maxOutputSize)
	{
	if (maxOutputSize < LZ4_compressBound(inputSize))
	return LZ4_compressHC_continue_generic(LZ4_streamHCPtr,
	source, dest, inputSize, maxOutputSize, limitedOutput);
	else
	return LZ4_compressHC_continue_generic(LZ4_streamHCPtr,
	source, dest, inputSize, maxOutputSize, noLimit);
	}
	EXPORT_SYMBOL(LZ4_compress_HC_continue);

	/* dictionary saving */

	int LZ4_saveDictHC(
	LZ4_streamHC_t *LZ4_streamHCPtr,
	char *safeBuffer,
	int dictSize)
	{
	LZ4HC_CCtx_internal *const streamPtr = &LZ4_streamHCPtr->internal_donotuse;
	int const prefixSize = (int)(streamPtr->end
	- (streamPtr->base + streamPtr->dictLimit));

	if (dictSize > 64 * KB)
	dictSize = 64 * KB;
	if (dictSize < 4)
	dictSize = 0;
	if (dictSize > prefixSize)
	dictSize = prefixSize;

	memmove(safeBuffer, streamPtr->end - dictSize, dictSize);

	{
	U32 const endIndex = (U32)(streamPtr->end - streamPtr->base);

	streamPtr->end = (const BYTE *)safeBuffer + dictSize;
	streamPtr->base = streamPtr->end - endIndex;
	streamPtr->dictLimit = endIndex - dictSize;
	streamPtr->lowLimit = endIndex - dictSize;

	if (streamPtr->nextToUpdate < streamPtr->dictLimit)
	streamPtr->nextToUpdate = streamPtr->dictLimit;
	}
	return dictSize;
	}
	EXPORT_SYMBOL(LZ4_saveDictHC);

	MODULE_LICENSE("Dual BSD/GPL");
	MODULE_DESCRIPTION("LZ4 HC compressor");