xref: /openbmc/linux/lib/lz4/lz4_compress.c (revision b1a3e75e)
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 
42 static const int LZ4_minLength = (MFLIMIT + 1);
43 static const int LZ4_64Klimit = ((64 * KB) + (MFLIMIT - 1));
44 
45 /*-******************************
46  *	Compression functions
47  ********************************/
LZ4_hash4(U32 sequence,tableType_t const tableType)48 static 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 
LZ4_hash5(U64 sequence,tableType_t const tableType)60 static 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 
LZ4_hashPosition(const void * p,tableType_t const tableType)79 static 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 
LZ4_putPositionOnHash(const BYTE * p,U32 h,void * tableBase,tableType_t const tableType,const BYTE * srcBase)91 static 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 
LZ4_putPosition(const BYTE * p,void * tableBase,tableType_t tableType,const BYTE * srcBase)123 static 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 
LZ4_getPositionOnHash(U32 h,void * tableBase,tableType_t tableType,const BYTE * srcBase)134 static 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 
LZ4_getPosition(const BYTE * p,void * tableBase,tableType_t tableType,const BYTE * srcBase)160 static 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  */
LZ4_compress_generic(LZ4_stream_t_internal * const dictPtr,const char * const source,char * const dest,const int inputSize,const int maxOutputSize,const limitedOutput_directive outputLimited,const tableType_t tableType,const dict_directive dict,const dictIssue_directive dictIssue,const U32 acceleration)176 static 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 
LZ4_compress_fast_extState(void * state,const char * source,char * dest,int inputSize,int maxOutputSize,int acceleration)458 static 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 
LZ4_compress_fast(const char * source,char * dest,int inputSize,int maxOutputSize,int acceleration,void * wrkmem)503 int 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 }
509 EXPORT_SYMBOL(LZ4_compress_fast);
510 
LZ4_compress_default(const char * source,char * dest,int inputSize,int maxOutputSize,void * wrkmem)511 int 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 }
517 EXPORT_SYMBOL(LZ4_compress_default);
518 
519 /*-******************************
520  *	*_destSize() variant
521  ********************************/
LZ4_compress_destSize_generic(LZ4_stream_t_internal * const ctx,const char * const src,char * const dst,int * const srcSizePtr,const int targetDstSize,const tableType_t tableType)522 static 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 
LZ4_compress_destSize_extState(LZ4_stream_t * state,const char * src,char * dst,int * srcSizePtr,int targetDstSize)720 static 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 
LZ4_compress_destSize(const char * src,char * dst,int * srcSizePtr,int targetDstSize,void * wrkmem)755 int 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 }
765 EXPORT_SYMBOL(LZ4_compress_destSize);
766 
767 /*-******************************
768  *	Streaming functions
769  ********************************/
LZ4_resetStream(LZ4_stream_t * LZ4_stream)770 void LZ4_resetStream(LZ4_stream_t *LZ4_stream)
771 {
772 	memset(LZ4_stream, 0, sizeof(LZ4_stream_t));
773 }
774 
LZ4_loadDict(LZ4_stream_t * LZ4_dict,const char * dictionary,int dictSize)775 int 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 }
810 EXPORT_SYMBOL(LZ4_loadDict);
811 
LZ4_renormDictT(LZ4_stream_t_internal * LZ4_dict,const BYTE * src)812 static 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 
LZ4_saveDict(LZ4_stream_t * LZ4_dict,char * safeBuffer,int dictSize)836 int 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 }
855 EXPORT_SYMBOL(LZ4_saveDict);
856 
LZ4_compress_fast_continue(LZ4_stream_t * LZ4_stream,const char * source,char * dest,int inputSize,int maxOutputSize,int acceleration)857 int 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 }
937 EXPORT_SYMBOL(LZ4_compress_fast_continue);
938 
939 MODULE_LICENSE("Dual BSD/GPL");
940 MODULE_DESCRIPTION("LZ4 compressor");
941