1/*
2 * LZ4 - Fast LZ compression algorithm
3 * Copyright (C) 2011 - 2016, Yann Collet.
4 * BSD 2 - Clause License (http://www.opensource.org/licenses/bsd - license.php)
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are
7 * met:
8 *	* Redistributions of source code must retain the above copyright
9 *	  notice, this list of conditions and the following disclaimer.
10 *	* Redistributions in binary form must reproduce the above
11 * copyright notice, this list of conditions and the following disclaimer
12 * in the documentation and/or other materials provided with the
13 * distribution.
14 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
15 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
16 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
17 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
18 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
19 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
20 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 * You can contact the author at :
26 *	- LZ4 homepage : http://www.lz4.org
27 *	- LZ4 source repository : https://github.com/lz4/lz4
28 *
29 *	Changed for kernel usage by:
30 *	Sven Schmidt <4sschmid@informatik.uni-hamburg.de>
31 */
32
33/*-************************************
34 *	Dependencies
35 **************************************/
36#include <linux/lz4.h>
37#include "lz4defs.h"
38#include <linux/module.h>
39#include <linux/kernel.h>
40#include <asm/unaligned.h>
41
42static const int LZ4_minLength = (MFLIMIT + 1);
43static const int LZ4_64Klimit = ((64 * KB) + (MFLIMIT - 1));
44
45/*-******************************
46 *	Compression functions
47 ********************************/
48static FORCE_INLINE U32 LZ4_hash4(
49	U32 sequence,
50	tableType_t const tableType)
51{
52	if (tableType == byU16)
53		return ((sequence * 2654435761U)
54			>> ((MINMATCH * 8) - (LZ4_HASHLOG + 1)));
55	else
56		return ((sequence * 2654435761U)
57			>> ((MINMATCH * 8) - LZ4_HASHLOG));
58}
59
60static FORCE_INLINE U32 LZ4_hash5(
61	U64 sequence,
62	tableType_t const tableType)
63{
64	const U32 hashLog = (tableType == byU16)
65		? LZ4_HASHLOG + 1
66		: LZ4_HASHLOG;
67
68#if LZ4_LITTLE_ENDIAN
69	static const U64 prime5bytes = 889523592379ULL;
70
71	return (U32)(((sequence << 24) * prime5bytes) >> (64 - hashLog));
72#else
73	static const U64 prime8bytes = 11400714785074694791ULL;
74
75	return (U32)(((sequence >> 24) * prime8bytes) >> (64 - hashLog));
76#endif
77}
78
79static FORCE_INLINE U32 LZ4_hashPosition(
80	const void *p,
81	tableType_t const tableType)
82{
83#if LZ4_ARCH64
84	if (tableType == byU32)
85		return LZ4_hash5(LZ4_read_ARCH(p), tableType);
86#endif
87
88	return LZ4_hash4(LZ4_read32(p), tableType);
89}
90
91static void LZ4_putPositionOnHash(
92	const BYTE *p,
93	U32 h,
94	void *tableBase,
95	tableType_t const tableType,
96	const BYTE *srcBase)
97{
98	switch (tableType) {
99	case byPtr:
100	{
101		const BYTE **hashTable = (const BYTE **)tableBase;
102
103		hashTable[h] = p;
104		return;
105	}
106	case byU32:
107	{
108		U32 *hashTable = (U32 *) tableBase;
109
110		hashTable[h] = (U32)(p - srcBase);
111		return;
112	}
113	case byU16:
114	{
115		U16 *hashTable = (U16 *) tableBase;
116
117		hashTable[h] = (U16)(p - srcBase);
118		return;
119	}
120	}
121}
122
123static FORCE_INLINE void LZ4_putPosition(
124	const BYTE *p,
125	void *tableBase,
126	tableType_t tableType,
127	const BYTE *srcBase)
128{
129	U32 const h = LZ4_hashPosition(p, tableType);
130
131	LZ4_putPositionOnHash(p, h, tableBase, tableType, srcBase);
132}
133
134static const BYTE *LZ4_getPositionOnHash(
135	U32 h,
136	void *tableBase,
137	tableType_t tableType,
138	const BYTE *srcBase)
139{
140	if (tableType == byPtr) {
141		const BYTE **hashTable = (const BYTE **) tableBase;
142
143		return hashTable[h];
144	}
145
146	if (tableType == byU32) {
147		const U32 * const hashTable = (U32 *) tableBase;
148
149		return hashTable[h] + srcBase;
150	}
151
152	{
153		/* default, to ensure a return */
154		const U16 * const hashTable = (U16 *) tableBase;
155
156		return hashTable[h] + srcBase;
157	}
158}
159
160static FORCE_INLINE const BYTE *LZ4_getPosition(
161	const BYTE *p,
162	void *tableBase,
163	tableType_t tableType,
164	const BYTE *srcBase)
165{
166	U32 const h = LZ4_hashPosition(p, tableType);
167
168	return LZ4_getPositionOnHash(h, tableBase, tableType, srcBase);
169}
170
171
172/*
173 * LZ4_compress_generic() :
174 * inlined, to ensure branches are decided at compilation time
175 */
176static FORCE_INLINE int LZ4_compress_generic(
177	LZ4_stream_t_internal * const dictPtr,
178	const char * const source,
179	char * const dest,
180	const int inputSize,
181	const int maxOutputSize,
182	const limitedOutput_directive outputLimited,
183	const tableType_t tableType,
184	const dict_directive dict,
185	const dictIssue_directive dictIssue,
186	const U32 acceleration)
187{
188	const BYTE *ip = (const BYTE *) source;
189	const BYTE *base;
190	const BYTE *lowLimit;
191	const BYTE * const lowRefLimit = ip - dictPtr->dictSize;
192	const BYTE * const dictionary = dictPtr->dictionary;
193	const BYTE * const dictEnd = dictionary + dictPtr->dictSize;
194	const size_t dictDelta = dictEnd - (const BYTE *)source;
195	const BYTE *anchor = (const BYTE *) source;
196	const BYTE * const iend = ip + inputSize;
197	const BYTE * const mflimit = iend - MFLIMIT;
198	const BYTE * const matchlimit = iend - LASTLITERALS;
199
200	BYTE *op = (BYTE *) dest;
201	BYTE * const olimit = op + maxOutputSize;
202
203	U32 forwardH;
204	size_t refDelta = 0;
205
206	/* Init conditions */
207	if ((U32)inputSize > (U32)LZ4_MAX_INPUT_SIZE) {
208		/* Unsupported inputSize, too large (or negative) */
209		return 0;
210	}
211
212	switch (dict) {
213	case noDict:
214	default:
215		base = (const BYTE *)source;
216		lowLimit = (const BYTE *)source;
217		break;
218	case withPrefix64k:
219		base = (const BYTE *)source - dictPtr->currentOffset;
220		lowLimit = (const BYTE *)source - dictPtr->dictSize;
221		break;
222	case usingExtDict:
223		base = (const BYTE *)source - dictPtr->currentOffset;
224		lowLimit = (const BYTE *)source;
225		break;
226	}
227
228	if ((tableType == byU16)
229		&& (inputSize >= LZ4_64Klimit)) {
230		/* Size too large (not within 64K limit) */
231		return 0;
232	}
233
234	if (inputSize < LZ4_minLength) {
235		/* Input too small, no compression (all literals) */
236		goto _last_literals;
237	}
238
239	/* First Byte */
240	LZ4_putPosition(ip, dictPtr->hashTable, tableType, base);
241	ip++;
242	forwardH = LZ4_hashPosition(ip, tableType);
243
244	/* Main Loop */
245	for ( ; ; ) {
246		const BYTE *match;
247		BYTE *token;
248
249		/* Find a match */
250		{
251			const BYTE *forwardIp = ip;
252			unsigned int step = 1;
253			unsigned int searchMatchNb = acceleration << LZ4_SKIPTRIGGER;
254
255			do {
256				U32 const h = forwardH;
257
258				ip = forwardIp;
259				forwardIp += step;
260				step = (searchMatchNb++ >> LZ4_SKIPTRIGGER);
261
262				if (unlikely(forwardIp > mflimit))
263					goto _last_literals;
264
265				match = LZ4_getPositionOnHash(h,
266					dictPtr->hashTable,
267					tableType, base);
268
269				if (dict == usingExtDict) {
270					if (match < (const BYTE *)source) {
271						refDelta = dictDelta;
272						lowLimit = dictionary;
273					} else {
274						refDelta = 0;
275						lowLimit = (const BYTE *)source;
276				}	 }
277
278				forwardH = LZ4_hashPosition(forwardIp,
279					tableType);
280
281				LZ4_putPositionOnHash(ip, h, dictPtr->hashTable,
282					tableType, base);
283			} while (((dictIssue == dictSmall)
284					? (match < lowRefLimit)
285					: 0)
286				|| ((tableType == byU16)
287					? 0
288					: (match + MAX_DISTANCE < ip))
289				|| (LZ4_read32(match + refDelta)
290					!= LZ4_read32(ip)));
291		}
292
293		/* Catch up */
294		while (((ip > anchor) & (match + refDelta > lowLimit))
295				&& (unlikely(ip[-1] == match[refDelta - 1]))) {
296			ip--;
297			match--;
298		}
299
300		/* Encode Literals */
301		{
302			unsigned const int litLength = (unsigned int)(ip - anchor);
303
304			token = op++;
305
306			if ((outputLimited) &&
307				/* Check output buffer overflow */
308				(unlikely(op + litLength +
309					(2 + 1 + LASTLITERALS) +
310					(litLength / 255) > olimit)))
311				return 0;
312
313			if (litLength >= RUN_MASK) {
314				int len = (int)litLength - RUN_MASK;
315
316				*token = (RUN_MASK << ML_BITS);
317
318				for (; len >= 255; len -= 255)
319					*op++ = 255;
320				*op++ = (BYTE)len;
321			} else
322				*token = (BYTE)(litLength << ML_BITS);
323
324			/* Copy Literals */
325			LZ4_wildCopy(op, anchor, op + litLength);
326			op += litLength;
327		}
328
329_next_match:
330		/* Encode Offset */
331		LZ4_writeLE16(op, (U16)(ip - match));
332		op += 2;
333
334		/* Encode MatchLength */
335		{
336			unsigned int matchCode;
337
338			if ((dict == usingExtDict)
339				&& (lowLimit == dictionary)) {
340				const BYTE *limit;
341
342				match += refDelta;
343				limit = ip + (dictEnd - match);
344
345				if (limit > matchlimit)
346					limit = matchlimit;
347
348				matchCode = LZ4_count(ip + MINMATCH,
349					match + MINMATCH, limit);
350
351				ip += MINMATCH + matchCode;
352
353				if (ip == limit) {
354					unsigned const int more = LZ4_count(ip,
355						(const BYTE *)source,
356						matchlimit);
357
358					matchCode += more;
359					ip += more;
360				}
361			} else {
362				matchCode = LZ4_count(ip + MINMATCH,
363					match + MINMATCH, matchlimit);
364				ip += MINMATCH + matchCode;
365			}
366
367			if (outputLimited &&
368				/* Check output buffer overflow */
369				(unlikely(op +
370					(1 + LASTLITERALS) +
371					(matchCode >> 8) > olimit)))
372				return 0;
373
374			if (matchCode >= ML_MASK) {
375				*token += ML_MASK;
376				matchCode -= ML_MASK;
377				LZ4_write32(op, 0xFFFFFFFF);
378
379				while (matchCode >= 4 * 255) {
380					op += 4;
381					LZ4_write32(op, 0xFFFFFFFF);
382					matchCode -= 4 * 255;
383				}
384
385				op += matchCode / 255;
386				*op++ = (BYTE)(matchCode % 255);
387			} else
388				*token += (BYTE)(matchCode);
389		}
390
391		anchor = ip;
392
393		/* Test end of chunk */
394		if (ip > mflimit)
395			break;
396
397		/* Fill table */
398		LZ4_putPosition(ip - 2, dictPtr->hashTable, tableType, base);
399
400		/* Test next position */
401		match = LZ4_getPosition(ip, dictPtr->hashTable,
402			tableType, base);
403
404		if (dict == usingExtDict) {
405			if (match < (const BYTE *)source) {
406				refDelta = dictDelta;
407				lowLimit = dictionary;
408			} else {
409				refDelta = 0;
410				lowLimit = (const BYTE *)source;
411			}
412		}
413
414		LZ4_putPosition(ip, dictPtr->hashTable, tableType, base);
415
416		if (((dictIssue == dictSmall) ? (match >= lowRefLimit) : 1)
417			&& (match + MAX_DISTANCE >= ip)
418			&& (LZ4_read32(match + refDelta) == LZ4_read32(ip))) {
419			token = op++;
420			*token = 0;
421			goto _next_match;
422		}
423
424		/* Prepare next loop */
425		forwardH = LZ4_hashPosition(++ip, tableType);
426	}
427
428_last_literals:
429	/* Encode Last Literals */
430	{
431		size_t const lastRun = (size_t)(iend - anchor);
432
433		if ((outputLimited) &&
434			/* Check output buffer overflow */
435			((op - (BYTE *)dest) + lastRun + 1 +
436			((lastRun + 255 - RUN_MASK) / 255) > (U32)maxOutputSize))
437			return 0;
438
439		if (lastRun >= RUN_MASK) {
440			size_t accumulator = lastRun - RUN_MASK;
441			*op++ = RUN_MASK << ML_BITS;
442			for (; accumulator >= 255; accumulator -= 255)
443				*op++ = 255;
444			*op++ = (BYTE) accumulator;
445		} else {
446			*op++ = (BYTE)(lastRun << ML_BITS);
447		}
448
449		LZ4_memcpy(op, anchor, lastRun);
450
451		op += lastRun;
452	}
453
454	/* End */
455	return (int) (((char *)op) - dest);
456}
457
458static int LZ4_compress_fast_extState(
459	void *state,
460	const char *source,
461	char *dest,
462	int inputSize,
463	int maxOutputSize,
464	int acceleration)
465{
466	LZ4_stream_t_internal *ctx = &((LZ4_stream_t *)state)->internal_donotuse;
467#if LZ4_ARCH64
468	const tableType_t tableType = byU32;
469#else
470	const tableType_t tableType = byPtr;
471#endif
472
473	LZ4_resetStream((LZ4_stream_t *)state);
474
475	if (acceleration < 1)
476		acceleration = LZ4_ACCELERATION_DEFAULT;
477
478	if (maxOutputSize >= LZ4_COMPRESSBOUND(inputSize)) {
479		if (inputSize < LZ4_64Klimit)
480			return LZ4_compress_generic(ctx, source,
481				dest, inputSize, 0,
482				noLimit, byU16, noDict,
483				noDictIssue, acceleration);
484		else
485			return LZ4_compress_generic(ctx, source,
486				dest, inputSize, 0,
487				noLimit, tableType, noDict,
488				noDictIssue, acceleration);
489	} else {
490		if (inputSize < LZ4_64Klimit)
491			return LZ4_compress_generic(ctx, source,
492				dest, inputSize,
493				maxOutputSize, limitedOutput, byU16, noDict,
494				noDictIssue, acceleration);
495		else
496			return LZ4_compress_generic(ctx, source,
497				dest, inputSize,
498				maxOutputSize, limitedOutput, tableType, noDict,
499				noDictIssue, acceleration);
500	}
501}
502
503int LZ4_compress_fast(const char *source, char *dest, int inputSize,
504	int maxOutputSize, int acceleration, void *wrkmem)
505{
506	return LZ4_compress_fast_extState(wrkmem, source, dest, inputSize,
507		maxOutputSize, acceleration);
508}
509EXPORT_SYMBOL(LZ4_compress_fast);
510
511int LZ4_compress_default(const char *source, char *dest, int inputSize,
512	int maxOutputSize, void *wrkmem)
513{
514	return LZ4_compress_fast(source, dest, inputSize,
515		maxOutputSize, LZ4_ACCELERATION_DEFAULT, wrkmem);
516}
517EXPORT_SYMBOL(LZ4_compress_default);
518
519/*-******************************
520 *	*_destSize() variant
521 ********************************/
522static int LZ4_compress_destSize_generic(
523	LZ4_stream_t_internal * const ctx,
524	const char * const src,
525	char * const dst,
526	int * const srcSizePtr,
527	const int targetDstSize,
528	const tableType_t tableType)
529{
530	const BYTE *ip = (const BYTE *) src;
531	const BYTE *base = (const BYTE *) src;
532	const BYTE *lowLimit = (const BYTE *) src;
533	const BYTE *anchor = ip;
534	const BYTE * const iend = ip + *srcSizePtr;
535	const BYTE * const mflimit = iend - MFLIMIT;
536	const BYTE * const matchlimit = iend - LASTLITERALS;
537
538	BYTE *op = (BYTE *) dst;
539	BYTE * const oend = op + targetDstSize;
540	BYTE * const oMaxLit = op + targetDstSize - 2 /* offset */
541		- 8 /* because 8 + MINMATCH == MFLIMIT */ - 1 /* token */;
542	BYTE * const oMaxMatch = op + targetDstSize
543		- (LASTLITERALS + 1 /* token */);
544	BYTE * const oMaxSeq = oMaxLit - 1 /* token */;
545
546	U32 forwardH;
547
548	/* Init conditions */
549	/* Impossible to store anything */
550	if (targetDstSize < 1)
551		return 0;
552	/* Unsupported input size, too large (or negative) */
553	if ((U32)*srcSizePtr > (U32)LZ4_MAX_INPUT_SIZE)
554		return 0;
555	/* Size too large (not within 64K limit) */
556	if ((tableType == byU16) && (*srcSizePtr >= LZ4_64Klimit))
557		return 0;
558	/* Input too small, no compression (all literals) */
559	if (*srcSizePtr < LZ4_minLength)
560		goto _last_literals;
561
562	/* First Byte */
563	*srcSizePtr = 0;
564	LZ4_putPosition(ip, ctx->hashTable, tableType, base);
565	ip++; forwardH = LZ4_hashPosition(ip, tableType);
566
567	/* Main Loop */
568	for ( ; ; ) {
569		const BYTE *match;
570		BYTE *token;
571
572		/* Find a match */
573		{
574			const BYTE *forwardIp = ip;
575			unsigned int step = 1;
576			unsigned int searchMatchNb = 1 << LZ4_SKIPTRIGGER;
577
578			do {
579				U32 h = forwardH;
580
581				ip = forwardIp;
582				forwardIp += step;
583				step = (searchMatchNb++ >> LZ4_SKIPTRIGGER);
584
585				if (unlikely(forwardIp > mflimit))
586					goto _last_literals;
587
588				match = LZ4_getPositionOnHash(h, ctx->hashTable,
589					tableType, base);
590				forwardH = LZ4_hashPosition(forwardIp,
591					tableType);
592				LZ4_putPositionOnHash(ip, h,
593					ctx->hashTable, tableType,
594					base);
595
596			} while (((tableType == byU16)
597				? 0
598				: (match + MAX_DISTANCE < ip))
599				|| (LZ4_read32(match) != LZ4_read32(ip)));
600		}
601
602		/* Catch up */
603		while ((ip > anchor)
604			&& (match > lowLimit)
605			&& (unlikely(ip[-1] == match[-1]))) {
606			ip--;
607			match--;
608		}
609
610		/* Encode Literal length */
611		{
612			unsigned int litLength = (unsigned int)(ip - anchor);
613
614			token = op++;
615			if (op + ((litLength + 240) / 255)
616				+ litLength > oMaxLit) {
617				/* Not enough space for a last match */
618				op--;
619				goto _last_literals;
620			}
621			if (litLength >= RUN_MASK) {
622				unsigned int len = litLength - RUN_MASK;
623				*token = (RUN_MASK<<ML_BITS);
624				for (; len >= 255; len -= 255)
625					*op++ = 255;
626				*op++ = (BYTE)len;
627			} else
628				*token = (BYTE)(litLength << ML_BITS);
629
630			/* Copy Literals */
631			LZ4_wildCopy(op, anchor, op + litLength);
632			op += litLength;
633		}
634
635_next_match:
636		/* Encode Offset */
637		LZ4_writeLE16(op, (U16)(ip - match)); op += 2;
638
639		/* Encode MatchLength */
640		{
641			size_t matchLength = LZ4_count(ip + MINMATCH,
642			match + MINMATCH, matchlimit);
643
644			if (op + ((matchLength + 240)/255) > oMaxMatch) {
645				/* Match description too long : reduce it */
646				matchLength = (15 - 1) + (oMaxMatch - op) * 255;
647			}
648			ip += MINMATCH + matchLength;
649
650			if (matchLength >= ML_MASK) {
651				*token += ML_MASK;
652				matchLength -= ML_MASK;
653				while (matchLength >= 255) {
654					matchLength -= 255;
655					*op++ = 255;
656				}
657				*op++ = (BYTE)matchLength;
658			} else
659				*token += (BYTE)(matchLength);
660		}
661
662		anchor = ip;
663
664		/* Test end of block */
665		if (ip > mflimit)
666			break;
667		if (op > oMaxSeq)
668			break;
669
670		/* Fill table */
671		LZ4_putPosition(ip - 2, ctx->hashTable, tableType, base);
672
673		/* Test next position */
674		match = LZ4_getPosition(ip, ctx->hashTable, tableType, base);
675		LZ4_putPosition(ip, ctx->hashTable, tableType, base);
676
677		if ((match + MAX_DISTANCE >= ip)
678			&& (LZ4_read32(match) == LZ4_read32(ip))) {
679			token = op++; *token = 0;
680			goto _next_match;
681		}
682
683		/* Prepare next loop */
684		forwardH = LZ4_hashPosition(++ip, tableType);
685	}
686
687_last_literals:
688	/* Encode Last Literals */
689	{
690		size_t lastRunSize = (size_t)(iend - anchor);
691
692		if (op + 1 /* token */
693			+ ((lastRunSize + 240) / 255) /* litLength */
694			+ lastRunSize /* literals */ > oend) {
695			/* adapt lastRunSize to fill 'dst' */
696			lastRunSize	= (oend - op) - 1;
697			lastRunSize -= (lastRunSize + 240) / 255;
698		}
699		ip = anchor + lastRunSize;
700
701		if (lastRunSize >= RUN_MASK) {
702			size_t accumulator = lastRunSize - RUN_MASK;
703
704			*op++ = RUN_MASK << ML_BITS;
705			for (; accumulator >= 255; accumulator -= 255)
706				*op++ = 255;
707			*op++ = (BYTE) accumulator;
708		} else {
709			*op++ = (BYTE)(lastRunSize<<ML_BITS);
710		}
711		LZ4_memcpy(op, anchor, lastRunSize);
712		op += lastRunSize;
713	}
714
715	/* End */
716	*srcSizePtr = (int) (((const char *)ip) - src);
717	return (int) (((char *)op) - dst);
718}
719
720static int LZ4_compress_destSize_extState(
721	LZ4_stream_t *state,
722	const char *src,
723	char *dst,
724	int *srcSizePtr,
725	int targetDstSize)
726{
727#if LZ4_ARCH64
728	const tableType_t tableType = byU32;
729#else
730	const tableType_t tableType = byPtr;
731#endif
732
733	LZ4_resetStream(state);
734
735	if (targetDstSize >= LZ4_COMPRESSBOUND(*srcSizePtr)) {
736		/* compression success is guaranteed */
737		return LZ4_compress_fast_extState(
738			state, src, dst, *srcSizePtr,
739			targetDstSize, 1);
740	} else {
741		if (*srcSizePtr < LZ4_64Klimit)
742			return LZ4_compress_destSize_generic(
743				&state->internal_donotuse,
744				src, dst, srcSizePtr,
745				targetDstSize, byU16);
746		else
747			return LZ4_compress_destSize_generic(
748				&state->internal_donotuse,
749				src, dst, srcSizePtr,
750				targetDstSize, tableType);
751	}
752}
753
754
755int LZ4_compress_destSize(
756	const char *src,
757	char *dst,
758	int *srcSizePtr,
759	int targetDstSize,
760	void *wrkmem)
761{
762	return LZ4_compress_destSize_extState(wrkmem, src, dst, srcSizePtr,
763		targetDstSize);
764}
765EXPORT_SYMBOL(LZ4_compress_destSize);
766
767/*-******************************
768 *	Streaming functions
769 ********************************/
770void LZ4_resetStream(LZ4_stream_t *LZ4_stream)
771{
772	memset(LZ4_stream, 0, sizeof(LZ4_stream_t));
773}
774
775int LZ4_loadDict(LZ4_stream_t *LZ4_dict,
776	const char *dictionary, int dictSize)
777{
778	LZ4_stream_t_internal *dict = &LZ4_dict->internal_donotuse;
779	const BYTE *p = (const BYTE *)dictionary;
780	const BYTE * const dictEnd = p + dictSize;
781	const BYTE *base;
782
783	if ((dict->initCheck)
784		|| (dict->currentOffset > 1 * GB)) {
785		/* Uninitialized structure, or reuse overflow */
786		LZ4_resetStream(LZ4_dict);
787	}
788
789	if (dictSize < (int)HASH_UNIT) {
790		dict->dictionary = NULL;
791		dict->dictSize = 0;
792		return 0;
793	}
794
795	if ((dictEnd - p) > 64 * KB)
796		p = dictEnd - 64 * KB;
797	dict->currentOffset += 64 * KB;
798	base = p - dict->currentOffset;
799	dict->dictionary = p;
800	dict->dictSize = (U32)(dictEnd - p);
801	dict->currentOffset += dict->dictSize;
802
803	while (p <= dictEnd - HASH_UNIT) {
804		LZ4_putPosition(p, dict->hashTable, byU32, base);
805		p += 3;
806	}
807
808	return dict->dictSize;
809}
810EXPORT_SYMBOL(LZ4_loadDict);
811
812static void LZ4_renormDictT(LZ4_stream_t_internal *LZ4_dict,
813	const BYTE *src)
814{
815	if ((LZ4_dict->currentOffset > 0x80000000) ||
816		((uptrval)LZ4_dict->currentOffset > (uptrval)src)) {
817		/* address space overflow */
818		/* rescale hash table */
819		U32 const delta = LZ4_dict->currentOffset - 64 * KB;
820		const BYTE *dictEnd = LZ4_dict->dictionary + LZ4_dict->dictSize;
821		int i;
822
823		for (i = 0; i < LZ4_HASH_SIZE_U32; i++) {
824			if (LZ4_dict->hashTable[i] < delta)
825				LZ4_dict->hashTable[i] = 0;
826			else
827				LZ4_dict->hashTable[i] -= delta;
828		}
829		LZ4_dict->currentOffset = 64 * KB;
830		if (LZ4_dict->dictSize > 64 * KB)
831			LZ4_dict->dictSize = 64 * KB;
832		LZ4_dict->dictionary = dictEnd - LZ4_dict->dictSize;
833	}
834}
835
836int LZ4_saveDict(LZ4_stream_t *LZ4_dict, char *safeBuffer, int dictSize)
837{
838	LZ4_stream_t_internal * const dict = &LZ4_dict->internal_donotuse;
839	const BYTE * const previousDictEnd = dict->dictionary + dict->dictSize;
840
841	if ((U32)dictSize > 64 * KB) {
842		/* useless to define a dictionary > 64 * KB */
843		dictSize = 64 * KB;
844	}
845	if ((U32)dictSize > dict->dictSize)
846		dictSize = dict->dictSize;
847
848	memmove(safeBuffer, previousDictEnd - dictSize, dictSize);
849
850	dict->dictionary = (const BYTE *)safeBuffer;
851	dict->dictSize = (U32)dictSize;
852
853	return dictSize;
854}
855EXPORT_SYMBOL(LZ4_saveDict);
856
857int LZ4_compress_fast_continue(LZ4_stream_t *LZ4_stream, const char *source,
858	char *dest, int inputSize, int maxOutputSize, int acceleration)
859{
860	LZ4_stream_t_internal *streamPtr = &LZ4_stream->internal_donotuse;
861	const BYTE * const dictEnd = streamPtr->dictionary
862		+ streamPtr->dictSize;
863
864	const BYTE *smallest = (const BYTE *) source;
865
866	if (streamPtr->initCheck) {
867		/* Uninitialized structure detected */
868		return 0;
869	}
870
871	if ((streamPtr->dictSize > 0) && (smallest > dictEnd))
872		smallest = dictEnd;
873
874	LZ4_renormDictT(streamPtr, smallest);
875
876	if (acceleration < 1)
877		acceleration = LZ4_ACCELERATION_DEFAULT;
878
879	/* Check overlapping input/dictionary space */
880	{
881		const BYTE *sourceEnd = (const BYTE *) source + inputSize;
882
883		if ((sourceEnd > streamPtr->dictionary)
884			&& (sourceEnd < dictEnd)) {
885			streamPtr->dictSize = (U32)(dictEnd - sourceEnd);
886			if (streamPtr->dictSize > 64 * KB)
887				streamPtr->dictSize = 64 * KB;
888			if (streamPtr->dictSize < 4)
889				streamPtr->dictSize = 0;
890			streamPtr->dictionary = dictEnd - streamPtr->dictSize;
891		}
892	}
893
894	/* prefix mode : source data follows dictionary */
895	if (dictEnd == (const BYTE *)source) {
896		int result;
897
898		if ((streamPtr->dictSize < 64 * KB) &&
899			(streamPtr->dictSize < streamPtr->currentOffset)) {
900			result = LZ4_compress_generic(
901				streamPtr, source, dest, inputSize,
902				maxOutputSize, limitedOutput, byU32,
903				withPrefix64k, dictSmall, acceleration);
904		} else {
905			result = LZ4_compress_generic(
906				streamPtr, source, dest, inputSize,
907				maxOutputSize, limitedOutput, byU32,
908				withPrefix64k, noDictIssue, acceleration);
909		}
910		streamPtr->dictSize += (U32)inputSize;
911		streamPtr->currentOffset += (U32)inputSize;
912		return result;
913	}
914
915	/* external dictionary mode */
916	{
917		int result;
918
919		if ((streamPtr->dictSize < 64 * KB) &&
920			(streamPtr->dictSize < streamPtr->currentOffset)) {
921			result = LZ4_compress_generic(
922				streamPtr, source, dest, inputSize,
923				maxOutputSize, limitedOutput, byU32,
924				usingExtDict, dictSmall, acceleration);
925		} else {
926			result = LZ4_compress_generic(
927				streamPtr, source, dest, inputSize,
928				maxOutputSize, limitedOutput, byU32,
929				usingExtDict, noDictIssue, acceleration);
930		}
931		streamPtr->dictionary = (const BYTE *)source;
932		streamPtr->dictSize = (U32)inputSize;
933		streamPtr->currentOffset += (U32)inputSize;
934		return result;
935	}
936}
937EXPORT_SYMBOL(LZ4_compress_fast_continue);
938
939MODULE_LICENSE("Dual BSD/GPL");
940MODULE_DESCRIPTION("LZ4 compressor");
941