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


            
            /*

            
             * LZ4 - Fast LZ compression algorithm

            
             * Copyright (C) 2011-2012, 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://fastcompression.blogspot.com/p/lz4.html

            
             * - LZ4 source repository : http://code.google.com/p/lz4/

            
             *

            
             *  Changed for kernel use by:

            
             *  Chanho Min <[email protected]>

            
             */


            #include <linux/module.h>

            
            #include <linux/kernel.h>

            
            #include <linux/lz4.h>

            
            #include <asm/unaligned.h>

            
            #include "lz4defs.h"


            /*

            
             * LZ4_compressCtx :

            
             * -----------------

            
             * Compress 'isize' bytes from 'source' into an output buffer 'dest' of

            
             * maximum size 'maxOutputSize'.  * If it cannot achieve it, compression

            
             * will stop, and result of the function will be zero.

            
             * return : the number of bytes written in buffer 'dest', or 0 if the

            
             * compression fails

            
             */

            
            static inline int lz4_compressctx(void *ctx,

            
            		const char *source,

            
            		char *dest,

            
            		int isize,

            
            		int maxoutputsize)

            
            {

            
            	HTYPE *hashtable = (HTYPE *)ctx;

            
            	const u8 *ip = (u8 *)source;

            
            #if LZ4_ARCH64

            
            	const BYTE * const base = ip;

            
            #else

            
            	const int base = 0;

            
            #endif

            
            	const u8 *anchor = ip;

            
            	const u8 *const iend = ip + isize;

            
            	const u8 *const mflimit = iend - MFLIMIT;

            
            	#define MATCHLIMIT (iend - LASTLITERALS)


            	u8 *op = (u8 *) dest;

            
            	u8 *const oend = op + maxoutputsize;

            
            	int length;

            
            	const int skipstrength = SKIPSTRENGTH;

            
            	u32 forwardh;

            
            	int lastrun;


            	/* Init */

            
            	if (isize < MINLENGTH)

            
            		goto _last_literals;


            	memset((void *)hashtable, 0, LZ4_MEM_COMPRESS);


            	/* First Byte */

            
            	hashtable[LZ4_HASH_VALUE(ip)] = ip - base;

            
            	ip++;

            
            	forwardh = LZ4_HASH_VALUE(ip);


            	/* Main Loop */

            
            	for (;;) {

            
            		int findmatchattempts = (1U << skipstrength) + 3;

            
            		const u8 *forwardip = ip;

            
            		const u8 *ref;

            
            		u8 *token;


            		/* Find a match */

            
            		do {

            
            			u32 h = forwardh;

            
            			int step = findmatchattempts++ >> skipstrength;

            
            			ip = forwardip;

            
            			forwardip = ip + step;


            			if (unlikely(forwardip > mflimit))

            
            				goto _last_literals;


            			forwardh = LZ4_HASH_VALUE(forwardip);

            
            			ref = base + hashtable[h];

            
            			hashtable[h] = ip - base;

            
            		} while ((ref < ip - MAX_DISTANCE) || (A32(ref) != A32(ip)));


            		/* Catch up */

            
            		while ((ip > anchor) && (ref > (u8 *)source) &&

            
            			unlikely(ip[-1] == ref[-1])) {

            
            			ip--;

            
            			ref--;

            
            		}


            		/* Encode Literal length */

            
            		length = (int)(ip - anchor);

            
            		token = op++;

            
            		/* check output limit */

            
            		if (unlikely(op + length + (2 + 1 + LASTLITERALS) +

            
            			(length >> 8) > oend))

            
            			return 0;


            		if (length >= (int)RUN_MASK) {

            
            			int len;

            
            			*token = (RUN_MASK << ML_BITS);

            
            			len = length - RUN_MASK;

            
            			for (; len > 254 ; len -= 255)

            
            				*op++ = 255;

            
            			*op++ = (u8)len;

            
            		} else

            
            			*token = (length << ML_BITS);


            		/* Copy Literals */

            
            		LZ4_BLINDCOPY(anchor, op, length);

            
            _next_match:

            
            		/* Encode Offset */

            
            		LZ4_WRITE_LITTLEENDIAN_16(op, (u16)(ip - ref));


            		/* Start Counting */

            
            		ip += MINMATCH;

            
            		/* MinMatch verified */

            
            		ref += MINMATCH;

            
            		anchor = ip;

            
            		while (likely(ip < MATCHLIMIT - (STEPSIZE - 1))) {

            
            			#if LZ4_ARCH64

            
            			u64 diff = A64(ref) ^ A64(ip);

            
            			#else

            
            			u32 diff = A32(ref) ^ A32(ip);

            
            			#endif

            
            			if (!diff) {

            
            				ip += STEPSIZE;

            
            				ref += STEPSIZE;

            
            				continue;

            
            			}

            
            			ip += LZ4_NBCOMMONBYTES(diff);

            
            			goto _endcount;

            
            		}

            
            		#if LZ4_ARCH64

            
            		if ((ip < (MATCHLIMIT - 3)) && (A32(ref) == A32(ip))) {

            
            			ip += 4;

            
            			ref += 4;

            
            		}

            
            		#endif

            
            		if ((ip < (MATCHLIMIT - 1)) && (A16(ref) == A16(ip))) {

            
            			ip += 2;

            
            			ref += 2;

            
            		}

            
            		if ((ip < MATCHLIMIT) && (*ref == *ip))

            
            			ip++;

            
            _endcount:

            
            		/* Encode MatchLength */

            
            		length = (int)(ip - anchor);

            
            		/* Check output limit */

            
            		if (unlikely(op + (1 + LASTLITERALS) + (length >> 8) > oend))

            
            			return 0;

            
            		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++ = (u8)length;

            
            		} else

            
            			*token += length;


            		/* Test end of chunk */

            
            		if (ip > mflimit) {

            
            			anchor = ip;

            
            			break;

            
            		}


            		/* Fill table */

            
            		hashtable[LZ4_HASH_VALUE(ip-2)] = ip - 2 - base;


            		/* Test next position */

            
            		ref = base + hashtable[LZ4_HASH_VALUE(ip)];

            
            		hashtable[LZ4_HASH_VALUE(ip)] = ip - base;

            
            		if ((ref > ip - (MAX_DISTANCE + 1)) && (A32(ref) == A32(ip))) {

            
            			token = op++;

            
            			*token = 0;

            
            			goto _next_match;

            
            		}


            		/* Prepare next loop */

            
            		anchor = ip++;

            
            		forwardh = LZ4_HASH_VALUE(ip);

            
            	}


            _last_literals:

            
            	/* Encode Last Literals */

            
            	lastrun = (int)(iend - anchor);

            
            	if (((char *)op - dest) + lastrun + 1

            
            		+ ((lastrun + 255 - RUN_MASK) / 255) > (u32)maxoutputsize)

            
            		return 0;


            	if (lastrun >= (int)RUN_MASK) {

            
            		*op++ = (RUN_MASK << ML_BITS);

            
            		lastrun -= RUN_MASK;

            
            		for (; lastrun > 254 ; lastrun -= 255)

            
            			*op++ = 255;

            
            		*op++ = (u8)lastrun;

            
            	} else

            
            		*op++ = (lastrun << ML_BITS);

            
            	memcpy(op, anchor, iend - anchor);

            
            	op += iend - anchor;


            	/* End */

            
            	return (int)(((char *)op) - dest);

            
            }


            static inline int lz4_compress64kctx(void *ctx,

            
            		const char *source,

            
            		char *dest,

            
            		int isize,

            
            		int maxoutputsize)

            
            {

            
            	u16 *hashtable = (u16 *)ctx;

            
            	const u8 *ip = (u8 *) source;

            
            	const u8 *anchor = ip;

            
            	const u8 *const base = ip;

            
            	const u8 *const iend = ip + isize;

            
            	const u8 *const mflimit = iend - MFLIMIT;

            
            	#define MATCHLIMIT (iend - LASTLITERALS)


            	u8 *op = (u8 *) dest;

            
            	u8 *const oend = op + maxoutputsize;

            
            	int len, length;

            
            	const int skipstrength = SKIPSTRENGTH;

            
            	u32 forwardh;

            
            	int lastrun;


            	/* Init */

            
            	if (isize < MINLENGTH)

            
            		goto _last_literals;


            	memset((void *)hashtable, 0, LZ4_MEM_COMPRESS);


            	/* First Byte */

            
            	ip++;

            
            	forwardh = LZ4_HASH64K_VALUE(ip);


            	/* Main Loop */

            
            	for (;;) {

            
            		int findmatchattempts = (1U << skipstrength) + 3;

            
            		const u8 *forwardip = ip;

            
            		const u8 *ref;

            
            		u8 *token;


            		/* Find a match */

            
            		do {

            
            			u32 h = forwardh;

            
            			int step = findmatchattempts++ >> skipstrength;

            
            			ip = forwardip;

            
            			forwardip = ip + step;


            			if (forwardip > mflimit)

            
            				goto _last_literals;


            			forwardh = LZ4_HASH64K_VALUE(forwardip);

            
            			ref = base + hashtable[h];

            
            			hashtable[h] = (u16)(ip - base);

            
            		} while (A32(ref) != A32(ip));


            		/* Catch up */

            
            		while ((ip > anchor) && (ref > (u8 *)source)

            
            			&& (ip[-1] == ref[-1])) {

            
            			ip--;

            
            			ref--;

            
            		}


            		/* Encode Literal length */

            
            		length = (int)(ip - anchor);

            
            		token = op++;

            
            		/* Check output limit */

            
            		if (unlikely(op + length + (2 + 1 + LASTLITERALS)

            
            			+ (length >> 8) > oend))

            
            			return 0;

            
            		if (length >= (int)RUN_MASK) {

            
            			*token = (RUN_MASK << ML_BITS);

            
            			len = length - RUN_MASK;

            
            			for (; len > 254 ; len -= 255)

            
            				*op++ = 255;

            
            			*op++ = (u8)len;

            
            		} else

            
            			*token = (length << ML_BITS);


            		/* Copy Literals */

            
            		LZ4_BLINDCOPY(anchor, op, length);


            _next_match:

            
            		/* Encode Offset */

            
            		LZ4_WRITE_LITTLEENDIAN_16(op, (u16)(ip - ref));


            		/* Start Counting */

            
            		ip += MINMATCH;

            
            		/* MinMatch verified */

            
            		ref += MINMATCH;

            
            		anchor = ip;


            		while (ip < MATCHLIMIT - (STEPSIZE - 1)) {

            
            			#if LZ4_ARCH64

            
            			u64 diff = A64(ref) ^ A64(ip);

            
            			#else

            
            			u32 diff = A32(ref) ^ A32(ip);

            
            			#endif


            			if (!diff) {

            
            				ip += STEPSIZE;

            
            				ref += STEPSIZE;

            
            				continue;

            
            			}

            
            			ip += LZ4_NBCOMMONBYTES(diff);

            
            			goto _endcount;

            
            		}

            
            		#if LZ4_ARCH64

            
            		if ((ip < (MATCHLIMIT - 3)) && (A32(ref) == A32(ip))) {

            
            			ip += 4;

            
            			ref += 4;

            
            		}

            
            		#endif

            
            		if ((ip < (MATCHLIMIT - 1)) && (A16(ref) == A16(ip))) {

            
            			ip += 2;

            
            			ref += 2;

            
            		}

            
            		if ((ip < MATCHLIMIT) && (*ref == *ip))

            
            			ip++;

            
            _endcount:


            		/* Encode MatchLength */

            
            		len = (int)(ip - anchor);

            
            		/* Check output limit */

            
            		if (unlikely(op + (1 + LASTLITERALS) + (len >> 8) > oend))

            
            			return 0;

            
            		if (len >= (int)ML_MASK) {

            
            			*token += ML_MASK;

            
            			len -= ML_MASK;

            
            			for (; len > 509 ; len -= 510) {

            
            				*op++ = 255;

            
            				*op++ = 255;

            
            			}

            
            			if (len > 254) {

            
            				len -= 255;

            
            				*op++ = 255;

            
            			}

            
            			*op++ = (u8)len;

            
            		} else

            
            			*token += len;


            		/* Test end of chunk */

            
            		if (ip > mflimit) {

            
            			anchor = ip;

            
            			break;

            
            		}


            		/* Fill table */

            
            		hashtable[LZ4_HASH64K_VALUE(ip-2)] = (u16)(ip - 2 - base);


            		/* Test next position */

            
            		ref = base + hashtable[LZ4_HASH64K_VALUE(ip)];

            
            		hashtable[LZ4_HASH64K_VALUE(ip)] = (u16)(ip - base);

            
            		if (A32(ref) == A32(ip)) {

            
            			token = op++;

            
            			*token = 0;

            
            			goto _next_match;

            
            		}


            		/* Prepare next loop */

            
            		anchor = ip++;

            
            		forwardh = LZ4_HASH64K_VALUE(ip);

            
            	}


            _last_literals:

            
            	/* Encode Last Literals */

            
            	lastrun = (int)(iend - anchor);

            
            	if (op + lastrun + 1 + (lastrun - RUN_MASK + 255) / 255 > oend)

            
            		return 0;

            
            	if (lastrun >= (int)RUN_MASK) {

            
            		*op++ = (RUN_MASK << ML_BITS);

            
            		lastrun -= RUN_MASK;

            
            		for (; lastrun > 254 ; lastrun -= 255)

            
            			*op++ = 255;

            
            		*op++ = (u8)lastrun;

            
            	} else

            
            		*op++ = (lastrun << ML_BITS);

            
            	memcpy(op, anchor, iend - anchor);

            
            	op += iend - anchor;

            
            	/* End */

            
            	return (int)(((char *)op) - dest);

            
            }


            int lz4_compress(const unsigned char *src, size_t src_len,

            
            			unsigned char *dst, size_t *dst_len, void *wrkmem)

            
            {

            
            	int ret = -1;

            
            	int out_len = 0;


            	if (src_len < LZ4_64KLIMIT)

            
            		out_len = lz4_compress64kctx(wrkmem, src, dst, src_len,

            
            				lz4_compressbound(src_len));

            
            	else

            
            		out_len = lz4_compressctx(wrkmem, src, dst, src_len,

            
            				lz4_compressbound(src_len));


            	if (out_len < 0)

            
            		goto exit;


            	*dst_len = out_len;


            	return 0;

            
            exit:

            
            	return ret;

            
            }

            
            EXPORT_SYMBOL(lz4_compress);


            MODULE_LICENSE("Dual BSD/GPL");

            
            MODULE_DESCRIPTION("LZ4 compressor");
	/*
	* LZ4 - Fast LZ compression algorithm
	* Copyright (C) 2011-2012, 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://fastcompression.blogspot.com/p/lz4.html
	* - LZ4 source repository : http://code.google.com/p/lz4/
	*
	* Changed for kernel use by:
	* Chanho Min <[email protected]>
	*/

	#include <linux/module.h>
	#include <linux/kernel.h>
	#include <linux/lz4.h>
	#include <asm/unaligned.h>
	#include "lz4defs.h"

	/*
	* LZ4_compressCtx :
	* -----------------
	* Compress 'isize' bytes from 'source' into an output buffer 'dest' of
	* maximum size 'maxOutputSize'. * If it cannot achieve it, compression
	* will stop, and result of the function will be zero.
	* return : the number of bytes written in buffer 'dest', or 0 if the
	* compression fails
	*/
	static inline int lz4_compressctx(void *ctx,
	const char *source,
	char *dest,
	int isize,
	int maxoutputsize)
	{
	HTYPE hashtable = (HTYPE )ctx;
	const u8 ip = (u8 )source;
	#if LZ4_ARCH64
	const BYTE * const base = ip;
	#else
	const int base = 0;
	#endif
	const u8 *anchor = ip;
	const u8 *const iend = ip + isize;
	const u8 *const mflimit = iend - MFLIMIT;
	#define MATCHLIMIT (iend - LASTLITERALS)

	u8 op = (u8 ) dest;
	u8 *const oend = op + maxoutputsize;
	int length;
	const int skipstrength = SKIPSTRENGTH;
	u32 forwardh;
	int lastrun;

	/* Init */
	if (isize < MINLENGTH)
	goto _last_literals;

	memset((void *)hashtable, 0, LZ4_MEM_COMPRESS);

	/* First Byte */
	hashtable[LZ4_HASH_VALUE(ip)] = ip - base;
	ip++;
	forwardh = LZ4_HASH_VALUE(ip);

	/* Main Loop */
	for (;;) {
	int findmatchattempts = (1U << skipstrength) + 3;
	const u8 *forwardip = ip;
	const u8 *ref;
	u8 *token;

	/* Find a match */
	do {
	u32 h = forwardh;
	int step = findmatchattempts++ >> skipstrength;
	ip = forwardip;
	forwardip = ip + step;

	if (unlikely(forwardip > mflimit))
	goto _last_literals;

	forwardh = LZ4_HASH_VALUE(forwardip);
	ref = base + hashtable[h];
	hashtable[h] = ip - base;
	} while ((ref < ip - MAX_DISTANCE) \|\| (A32(ref) != A32(ip)));

	/* Catch up */
	while ((ip > anchor) && (ref > (u8 *)source) &&
	unlikely(ip[-1] == ref[-1])) {
	ip--;
	ref--;
	}

	/* Encode Literal length */
	length = (int)(ip - anchor);
	token = op++;
	/* check output limit */
	if (unlikely(op + length + (2 + 1 + LASTLITERALS) +
	(length >> 8) > oend))
	return 0;

	if (length >= (int)RUN_MASK) {
	int len;
	*token = (RUN_MASK << ML_BITS);
	len = length - RUN_MASK;
	for (; len > 254 ; len -= 255)
	*op++ = 255;
	*op++ = (u8)len;
	} else
	*token = (length << ML_BITS);

	/* Copy Literals */
	LZ4_BLINDCOPY(anchor, op, length);
	_next_match:
	/* Encode Offset */
	LZ4_WRITE_LITTLEENDIAN_16(op, (u16)(ip - ref));

	/* Start Counting */
	ip += MINMATCH;
	/* MinMatch verified */
	ref += MINMATCH;
	anchor = ip;
	while (likely(ip < MATCHLIMIT - (STEPSIZE - 1))) {
	#if LZ4_ARCH64
	u64 diff = A64(ref) ^ A64(ip);
	#else
	u32 diff = A32(ref) ^ A32(ip);
	#endif
	if (!diff) {
	ip += STEPSIZE;
	ref += STEPSIZE;
	continue;
	}
	ip += LZ4_NBCOMMONBYTES(diff);
	goto _endcount;
	}
	#if LZ4_ARCH64
	if ((ip < (MATCHLIMIT - 3)) && (A32(ref) == A32(ip))) {
	ip += 4;
	ref += 4;
	}
	#endif
	if ((ip < (MATCHLIMIT - 1)) && (A16(ref) == A16(ip))) {
	ip += 2;
	ref += 2;
	}
	if ((ip < MATCHLIMIT) && (ref == ip))
	ip++;
	_endcount:
	/* Encode MatchLength */
	length = (int)(ip - anchor);
	/* Check output limit */
	if (unlikely(op + (1 + LASTLITERALS) + (length >> 8) > oend))
	return 0;
	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++ = (u8)length;
	} else
	*token += length;

	/* Test end of chunk */
	if (ip > mflimit) {
	anchor = ip;
	break;
	}

	/* Fill table */
	hashtable[LZ4_HASH_VALUE(ip-2)] = ip - 2 - base;

	/* Test next position */
	ref = base + hashtable[LZ4_HASH_VALUE(ip)];
	hashtable[LZ4_HASH_VALUE(ip)] = ip - base;
	if ((ref > ip - (MAX_DISTANCE + 1)) && (A32(ref) == A32(ip))) {
	token = op++;
	*token = 0;
	goto _next_match;
	}

	/* Prepare next loop */
	anchor = ip++;
	forwardh = LZ4_HASH_VALUE(ip);
	}

	_last_literals:
	/* Encode Last Literals */
	lastrun = (int)(iend - anchor);
	if (((char *)op - dest) + lastrun + 1
	+ ((lastrun + 255 - RUN_MASK) / 255) > (u32)maxoutputsize)
	return 0;

	if (lastrun >= (int)RUN_MASK) {
	*op++ = (RUN_MASK << ML_BITS);
	lastrun -= RUN_MASK;
	for (; lastrun > 254 ; lastrun -= 255)
	*op++ = 255;
	*op++ = (u8)lastrun;
	} else
	*op++ = (lastrun << ML_BITS);
	memcpy(op, anchor, iend - anchor);
	op += iend - anchor;

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

	static inline int lz4_compress64kctx(void *ctx,
	const char *source,
	char *dest,
	int isize,
	int maxoutputsize)
	{
	u16 hashtable = (u16 )ctx;
	const u8 ip = (u8 ) source;
	const u8 *anchor = ip;
	const u8 *const base = ip;
	const u8 *const iend = ip + isize;
	const u8 *const mflimit = iend - MFLIMIT;
	#define MATCHLIMIT (iend - LASTLITERALS)

	u8 op = (u8 ) dest;
	u8 *const oend = op + maxoutputsize;
	int len, length;
	const int skipstrength = SKIPSTRENGTH;
	u32 forwardh;
	int lastrun;

	/* Init */
	if (isize < MINLENGTH)
	goto _last_literals;

	memset((void *)hashtable, 0, LZ4_MEM_COMPRESS);

	/* First Byte */
	ip++;
	forwardh = LZ4_HASH64K_VALUE(ip);

	/* Main Loop */
	for (;;) {
	int findmatchattempts = (1U << skipstrength) + 3;
	const u8 *forwardip = ip;
	const u8 *ref;
	u8 *token;

	/* Find a match */
	do {
	u32 h = forwardh;
	int step = findmatchattempts++ >> skipstrength;
	ip = forwardip;
	forwardip = ip + step;

	if (forwardip > mflimit)
	goto _last_literals;

	forwardh = LZ4_HASH64K_VALUE(forwardip);
	ref = base + hashtable[h];
	hashtable[h] = (u16)(ip - base);
	} while (A32(ref) != A32(ip));

	/* Catch up */
	while ((ip > anchor) && (ref > (u8 *)source)
	&& (ip[-1] == ref[-1])) {
	ip--;
	ref--;
	}

	/* Encode Literal length */
	length = (int)(ip - anchor);
	token = op++;
	/* Check output limit */
	if (unlikely(op + length + (2 + 1 + LASTLITERALS)
	+ (length >> 8) > oend))
	return 0;
	if (length >= (int)RUN_MASK) {
	*token = (RUN_MASK << ML_BITS);
	len = length - RUN_MASK;
	for (; len > 254 ; len -= 255)
	*op++ = 255;
	*op++ = (u8)len;
	} else
	*token = (length << ML_BITS);

	/* Copy Literals */
	LZ4_BLINDCOPY(anchor, op, length);

	_next_match:
	/* Encode Offset */
	LZ4_WRITE_LITTLEENDIAN_16(op, (u16)(ip - ref));

	/* Start Counting */
	ip += MINMATCH;
	/* MinMatch verified */
	ref += MINMATCH;
	anchor = ip;

	while (ip < MATCHLIMIT - (STEPSIZE - 1)) {
	#if LZ4_ARCH64
	u64 diff = A64(ref) ^ A64(ip);
	#else
	u32 diff = A32(ref) ^ A32(ip);
	#endif

	if (!diff) {
	ip += STEPSIZE;
	ref += STEPSIZE;
	continue;
	}
	ip += LZ4_NBCOMMONBYTES(diff);
	goto _endcount;
	}
	#if LZ4_ARCH64
	if ((ip < (MATCHLIMIT - 3)) && (A32(ref) == A32(ip))) {
	ip += 4;
	ref += 4;
	}
	#endif
	if ((ip < (MATCHLIMIT - 1)) && (A16(ref) == A16(ip))) {
	ip += 2;
	ref += 2;
	}
	if ((ip < MATCHLIMIT) && (ref == ip))
	ip++;
	_endcount:

	/* Encode MatchLength */
	len = (int)(ip - anchor);
	/* Check output limit */
	if (unlikely(op + (1 + LASTLITERALS) + (len >> 8) > oend))
	return 0;
	if (len >= (int)ML_MASK) {
	*token += ML_MASK;
	len -= ML_MASK;
	for (; len > 509 ; len -= 510) {
	*op++ = 255;
	*op++ = 255;
	}
	if (len > 254) {
	len -= 255;
	*op++ = 255;
	}
	*op++ = (u8)len;
	} else
	*token += len;

	/* Test end of chunk */
	if (ip > mflimit) {
	anchor = ip;
	break;
	}

	/* Fill table */
	hashtable[LZ4_HASH64K_VALUE(ip-2)] = (u16)(ip - 2 - base);

	/* Test next position */
	ref = base + hashtable[LZ4_HASH64K_VALUE(ip)];
	hashtable[LZ4_HASH64K_VALUE(ip)] = (u16)(ip - base);
	if (A32(ref) == A32(ip)) {
	token = op++;
	*token = 0;
	goto _next_match;
	}

	/* Prepare next loop */
	anchor = ip++;
	forwardh = LZ4_HASH64K_VALUE(ip);
	}

	_last_literals:
	/* Encode Last Literals */
	lastrun = (int)(iend - anchor);
	if (op + lastrun + 1 + (lastrun - RUN_MASK + 255) / 255 > oend)
	return 0;
	if (lastrun >= (int)RUN_MASK) {
	*op++ = (RUN_MASK << ML_BITS);
	lastrun -= RUN_MASK;
	for (; lastrun > 254 ; lastrun -= 255)
	*op++ = 255;
	*op++ = (u8)lastrun;
	} else
	*op++ = (lastrun << ML_BITS);
	memcpy(op, anchor, iend - anchor);
	op += iend - anchor;
	/* End */
	return (int)(((char *)op) - dest);
	}

	int lz4_compress(const unsigned char *src, size_t src_len,
	unsigned char dst, size_t dst_len, void *wrkmem)
	{
	int ret = -1;
	int out_len = 0;

	if (src_len < LZ4_64KLIMIT)
	out_len = lz4_compress64kctx(wrkmem, src, dst, src_len,
	lz4_compressbound(src_len));
	else
	out_len = lz4_compressctx(wrkmem, src, dst, src_len,
	lz4_compressbound(src_len));

	if (out_len < 0)
	goto exit;

	*dst_len = out_len;

	return 0;
	exit:
	return ret;
	}
	EXPORT_SYMBOL(lz4_compress);

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