941 lines · c
1/*2 * LZ4 - Fast LZ compression algorithm3 * 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 without6 * modification, are permitted provided that the following conditions are7 * met:8 * * Redistributions of source code must retain the above copyright9 * notice, this list of conditions and the following disclaimer.10 * * Redistributions in binary form must reproduce the above11 * copyright notice, this list of conditions and the following disclaimer12 * in the documentation and/or other materials provided with the13 * distribution.14 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS15 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT16 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR17 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT18 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,19 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT20 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE24 * 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.org27 * - LZ4 source repository : https://github.com/lz4/lz428 *29 * Changed for kernel usage by:30 * Sven Schmidt <4sschmid@informatik.uni-hamburg.de>31 */32 33/*-************************************34 * Dependencies35 **************************************/36#include <linux/lz4.h>37#include "lz4defs.h"38#include <linux/module.h>39#include <linux/kernel.h>40#include <linux/unaligned.h>41 42static const int LZ4_minLength = (MFLIMIT + 1);43static const int LZ4_64Klimit = ((64 * KB) + (MFLIMIT - 1));44 45/*-******************************46 * Compression functions47 ********************************/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 else56 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 + 166 : LZ4_HASHLOG;67 68#if LZ4_LITTLE_ENDIAN69 static const U64 prime5bytes = 889523592379ULL;70 71 return (U32)(((sequence << 24) * prime5bytes) >> (64 - hashLog));72#else73 static const U64 prime8bytes = 11400714785074694791ULL;74 75 return (U32)(((sequence >> 24) * prime8bytes) >> (64 - hashLog));76#endif77}78 79static FORCE_INLINE U32 LZ4_hashPosition(80 const void *p,81 tableType_t const tableType)82{83#if LZ4_ARCH6484 if (tableType == byU32)85 return LZ4_hash5(LZ4_read_ARCH(p), tableType);86#endif87 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 time175 */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 ? 0288 : (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 } else322 *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 } else388 *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_ARCH64468 const tableType_t tableType = byU32;469#else470 const tableType_t tableType = byPtr;471#endif472 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 else485 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 else496 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() variant521 ********************************/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 + targetDstSize543 - (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 ? 0598 : (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 } else628 *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 } else659 *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_ARCH64728 const tableType_t tableType = byU32;729#else730 const tableType_t tableType = byPtr;731#endif732 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 else747 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 functions769 ********************************/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 else827 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->dictionary862 + 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