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