Back to home page

OSCL-LXR
 
 

     

0001 /*
0002  * LZ4 - Fast LZ compression algorithm
0003  * Copyright (C) 2011 - 2016, Yann Collet.
0004  * BSD 2 - Clause License (http://www.opensource.org/licenses/bsd - license.php)
0005  * Redistribution and use in source and binary forms, with or without
0006  * modification, are permitted provided that the following conditions are
0007  * met:
0008  *  * Redistributions of source code must retain the above copyright
0009  *    notice, this list of conditions and the following disclaimer.
0010  *  * Redistributions in binary form must reproduce the above
0011  * copyright notice, this list of conditions and the following disclaimer
0012  * in the documentation and/or other materials provided with the
0013  * distribution.
0014  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
0015  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
0016  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
0017  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
0018  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
0019  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
0020  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
0021  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
0022  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
0023  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
0024  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
0025  * You can contact the author at :
0026  *  - LZ4 homepage : http://www.lz4.org
0027  *  - LZ4 source repository : https://github.com/lz4/lz4
0028  *
0029  *  Changed for kernel usage by:
0030  *  Sven Schmidt <4sschmid@informatik.uni-hamburg.de>
0031  */
0032 
0033 /*-************************************
0034  *  Dependencies
0035  **************************************/
0036 #include <linux/lz4.h>
0037 #include "lz4defs.h"
0038 #include <linux/module.h>
0039 #include <linux/kernel.h>
0040 #include <asm/unaligned.h>
0041 
0042 static const int LZ4_minLength = (MFLIMIT + 1);
0043 static const int LZ4_64Klimit = ((64 * KB) + (MFLIMIT - 1));
0044 
0045 /*-******************************
0046  *  Compression functions
0047  ********************************/
0048 static FORCE_INLINE U32 LZ4_hash4(
0049     U32 sequence,
0050     tableType_t const tableType)
0051 {
0052     if (tableType == byU16)
0053         return ((sequence * 2654435761U)
0054             >> ((MINMATCH * 8) - (LZ4_HASHLOG + 1)));
0055     else
0056         return ((sequence * 2654435761U)
0057             >> ((MINMATCH * 8) - LZ4_HASHLOG));
0058 }
0059 
0060 static FORCE_INLINE U32 LZ4_hash5(
0061     U64 sequence,
0062     tableType_t const tableType)
0063 {
0064     const U32 hashLog = (tableType == byU16)
0065         ? LZ4_HASHLOG + 1
0066         : LZ4_HASHLOG;
0067 
0068 #if LZ4_LITTLE_ENDIAN
0069     static const U64 prime5bytes = 889523592379ULL;
0070 
0071     return (U32)(((sequence << 24) * prime5bytes) >> (64 - hashLog));
0072 #else
0073     static const U64 prime8bytes = 11400714785074694791ULL;
0074 
0075     return (U32)(((sequence >> 24) * prime8bytes) >> (64 - hashLog));
0076 #endif
0077 }
0078 
0079 static FORCE_INLINE U32 LZ4_hashPosition(
0080     const void *p,
0081     tableType_t const tableType)
0082 {
0083 #if LZ4_ARCH64
0084     if (tableType == byU32)
0085         return LZ4_hash5(LZ4_read_ARCH(p), tableType);
0086 #endif
0087 
0088     return LZ4_hash4(LZ4_read32(p), tableType);
0089 }
0090 
0091 static void LZ4_putPositionOnHash(
0092     const BYTE *p,
0093     U32 h,
0094     void *tableBase,
0095     tableType_t const tableType,
0096     const BYTE *srcBase)
0097 {
0098     switch (tableType) {
0099     case byPtr:
0100     {
0101         const BYTE **hashTable = (const BYTE **)tableBase;
0102 
0103         hashTable[h] = p;
0104         return;
0105     }
0106     case byU32:
0107     {
0108         U32 *hashTable = (U32 *) tableBase;
0109 
0110         hashTable[h] = (U32)(p - srcBase);
0111         return;
0112     }
0113     case byU16:
0114     {
0115         U16 *hashTable = (U16 *) tableBase;
0116 
0117         hashTable[h] = (U16)(p - srcBase);
0118         return;
0119     }
0120     }
0121 }
0122 
0123 static FORCE_INLINE void LZ4_putPosition(
0124     const BYTE *p,
0125     void *tableBase,
0126     tableType_t tableType,
0127     const BYTE *srcBase)
0128 {
0129     U32 const h = LZ4_hashPosition(p, tableType);
0130 
0131     LZ4_putPositionOnHash(p, h, tableBase, tableType, srcBase);
0132 }
0133 
0134 static const BYTE *LZ4_getPositionOnHash(
0135     U32 h,
0136     void *tableBase,
0137     tableType_t tableType,
0138     const BYTE *srcBase)
0139 {
0140     if (tableType == byPtr) {
0141         const BYTE **hashTable = (const BYTE **) tableBase;
0142 
0143         return hashTable[h];
0144     }
0145 
0146     if (tableType == byU32) {
0147         const U32 * const hashTable = (U32 *) tableBase;
0148 
0149         return hashTable[h] + srcBase;
0150     }
0151 
0152     {
0153         /* default, to ensure a return */
0154         const U16 * const hashTable = (U16 *) tableBase;
0155 
0156         return hashTable[h] + srcBase;
0157     }
0158 }
0159 
0160 static FORCE_INLINE const BYTE *LZ4_getPosition(
0161     const BYTE *p,
0162     void *tableBase,
0163     tableType_t tableType,
0164     const BYTE *srcBase)
0165 {
0166     U32 const h = LZ4_hashPosition(p, tableType);
0167 
0168     return LZ4_getPositionOnHash(h, tableBase, tableType, srcBase);
0169 }
0170 
0171 
0172 /*
0173  * LZ4_compress_generic() :
0174  * inlined, to ensure branches are decided at compilation time
0175  */
0176 static FORCE_INLINE int LZ4_compress_generic(
0177     LZ4_stream_t_internal * const dictPtr,
0178     const char * const source,
0179     char * const dest,
0180     const int inputSize,
0181     const int maxOutputSize,
0182     const limitedOutput_directive outputLimited,
0183     const tableType_t tableType,
0184     const dict_directive dict,
0185     const dictIssue_directive dictIssue,
0186     const U32 acceleration)
0187 {
0188     const BYTE *ip = (const BYTE *) source;
0189     const BYTE *base;
0190     const BYTE *lowLimit;
0191     const BYTE * const lowRefLimit = ip - dictPtr->dictSize;
0192     const BYTE * const dictionary = dictPtr->dictionary;
0193     const BYTE * const dictEnd = dictionary + dictPtr->dictSize;
0194     const size_t dictDelta = dictEnd - (const BYTE *)source;
0195     const BYTE *anchor = (const BYTE *) source;
0196     const BYTE * const iend = ip + inputSize;
0197     const BYTE * const mflimit = iend - MFLIMIT;
0198     const BYTE * const matchlimit = iend - LASTLITERALS;
0199 
0200     BYTE *op = (BYTE *) dest;
0201     BYTE * const olimit = op + maxOutputSize;
0202 
0203     U32 forwardH;
0204     size_t refDelta = 0;
0205 
0206     /* Init conditions */
0207     if ((U32)inputSize > (U32)LZ4_MAX_INPUT_SIZE) {
0208         /* Unsupported inputSize, too large (or negative) */
0209         return 0;
0210     }
0211 
0212     switch (dict) {
0213     case noDict:
0214     default:
0215         base = (const BYTE *)source;
0216         lowLimit = (const BYTE *)source;
0217         break;
0218     case withPrefix64k:
0219         base = (const BYTE *)source - dictPtr->currentOffset;
0220         lowLimit = (const BYTE *)source - dictPtr->dictSize;
0221         break;
0222     case usingExtDict:
0223         base = (const BYTE *)source - dictPtr->currentOffset;
0224         lowLimit = (const BYTE *)source;
0225         break;
0226     }
0227 
0228     if ((tableType == byU16)
0229         && (inputSize >= LZ4_64Klimit)) {
0230         /* Size too large (not within 64K limit) */
0231         return 0;
0232     }
0233 
0234     if (inputSize < LZ4_minLength) {
0235         /* Input too small, no compression (all literals) */
0236         goto _last_literals;
0237     }
0238 
0239     /* First Byte */
0240     LZ4_putPosition(ip, dictPtr->hashTable, tableType, base);
0241     ip++;
0242     forwardH = LZ4_hashPosition(ip, tableType);
0243 
0244     /* Main Loop */
0245     for ( ; ; ) {
0246         const BYTE *match;
0247         BYTE *token;
0248 
0249         /* Find a match */
0250         {
0251             const BYTE *forwardIp = ip;
0252             unsigned int step = 1;
0253             unsigned int searchMatchNb = acceleration << LZ4_SKIPTRIGGER;
0254 
0255             do {
0256                 U32 const h = forwardH;
0257 
0258                 ip = forwardIp;
0259                 forwardIp += step;
0260                 step = (searchMatchNb++ >> LZ4_SKIPTRIGGER);
0261 
0262                 if (unlikely(forwardIp > mflimit))
0263                     goto _last_literals;
0264 
0265                 match = LZ4_getPositionOnHash(h,
0266                     dictPtr->hashTable,
0267                     tableType, base);
0268 
0269                 if (dict == usingExtDict) {
0270                     if (match < (const BYTE *)source) {
0271                         refDelta = dictDelta;
0272                         lowLimit = dictionary;
0273                     } else {
0274                         refDelta = 0;
0275                         lowLimit = (const BYTE *)source;
0276                 }    }
0277 
0278                 forwardH = LZ4_hashPosition(forwardIp,
0279                     tableType);
0280 
0281                 LZ4_putPositionOnHash(ip, h, dictPtr->hashTable,
0282                     tableType, base);
0283             } while (((dictIssue == dictSmall)
0284                     ? (match < lowRefLimit)
0285                     : 0)
0286                 || ((tableType == byU16)
0287                     ? 0
0288                     : (match + MAX_DISTANCE < ip))
0289                 || (LZ4_read32(match + refDelta)
0290                     != LZ4_read32(ip)));
0291         }
0292 
0293         /* Catch up */
0294         while (((ip > anchor) & (match + refDelta > lowLimit))
0295                 && (unlikely(ip[-1] == match[refDelta - 1]))) {
0296             ip--;
0297             match--;
0298         }
0299 
0300         /* Encode Literals */
0301         {
0302             unsigned const int litLength = (unsigned int)(ip - anchor);
0303 
0304             token = op++;
0305 
0306             if ((outputLimited) &&
0307                 /* Check output buffer overflow */
0308                 (unlikely(op + litLength +
0309                     (2 + 1 + LASTLITERALS) +
0310                     (litLength / 255) > olimit)))
0311                 return 0;
0312 
0313             if (litLength >= RUN_MASK) {
0314                 int len = (int)litLength - RUN_MASK;
0315 
0316                 *token = (RUN_MASK << ML_BITS);
0317 
0318                 for (; len >= 255; len -= 255)
0319                     *op++ = 255;
0320                 *op++ = (BYTE)len;
0321             } else
0322                 *token = (BYTE)(litLength << ML_BITS);
0323 
0324             /* Copy Literals */
0325             LZ4_wildCopy(op, anchor, op + litLength);
0326             op += litLength;
0327         }
0328 
0329 _next_match:
0330         /* Encode Offset */
0331         LZ4_writeLE16(op, (U16)(ip - match));
0332         op += 2;
0333 
0334         /* Encode MatchLength */
0335         {
0336             unsigned int matchCode;
0337 
0338             if ((dict == usingExtDict)
0339                 && (lowLimit == dictionary)) {
0340                 const BYTE *limit;
0341 
0342                 match += refDelta;
0343                 limit = ip + (dictEnd - match);
0344 
0345                 if (limit > matchlimit)
0346                     limit = matchlimit;
0347 
0348                 matchCode = LZ4_count(ip + MINMATCH,
0349                     match + MINMATCH, limit);
0350 
0351                 ip += MINMATCH + matchCode;
0352 
0353                 if (ip == limit) {
0354                     unsigned const int more = LZ4_count(ip,
0355                         (const BYTE *)source,
0356                         matchlimit);
0357 
0358                     matchCode += more;
0359                     ip += more;
0360                 }
0361             } else {
0362                 matchCode = LZ4_count(ip + MINMATCH,
0363                     match + MINMATCH, matchlimit);
0364                 ip += MINMATCH + matchCode;
0365             }
0366 
0367             if (outputLimited &&
0368                 /* Check output buffer overflow */
0369                 (unlikely(op +
0370                     (1 + LASTLITERALS) +
0371                     (matchCode >> 8) > olimit)))
0372                 return 0;
0373 
0374             if (matchCode >= ML_MASK) {
0375                 *token += ML_MASK;
0376                 matchCode -= ML_MASK;
0377                 LZ4_write32(op, 0xFFFFFFFF);
0378 
0379                 while (matchCode >= 4 * 255) {
0380                     op += 4;
0381                     LZ4_write32(op, 0xFFFFFFFF);
0382                     matchCode -= 4 * 255;
0383                 }
0384 
0385                 op += matchCode / 255;
0386                 *op++ = (BYTE)(matchCode % 255);
0387             } else
0388                 *token += (BYTE)(matchCode);
0389         }
0390 
0391         anchor = ip;
0392 
0393         /* Test end of chunk */
0394         if (ip > mflimit)
0395             break;
0396 
0397         /* Fill table */
0398         LZ4_putPosition(ip - 2, dictPtr->hashTable, tableType, base);
0399 
0400         /* Test next position */
0401         match = LZ4_getPosition(ip, dictPtr->hashTable,
0402             tableType, base);
0403 
0404         if (dict == usingExtDict) {
0405             if (match < (const BYTE *)source) {
0406                 refDelta = dictDelta;
0407                 lowLimit = dictionary;
0408             } else {
0409                 refDelta = 0;
0410                 lowLimit = (const BYTE *)source;
0411             }
0412         }
0413 
0414         LZ4_putPosition(ip, dictPtr->hashTable, tableType, base);
0415 
0416         if (((dictIssue == dictSmall) ? (match >= lowRefLimit) : 1)
0417             && (match + MAX_DISTANCE >= ip)
0418             && (LZ4_read32(match + refDelta) == LZ4_read32(ip))) {
0419             token = op++;
0420             *token = 0;
0421             goto _next_match;
0422         }
0423 
0424         /* Prepare next loop */
0425         forwardH = LZ4_hashPosition(++ip, tableType);
0426     }
0427 
0428 _last_literals:
0429     /* Encode Last Literals */
0430     {
0431         size_t const lastRun = (size_t)(iend - anchor);
0432 
0433         if ((outputLimited) &&
0434             /* Check output buffer overflow */
0435             ((op - (BYTE *)dest) + lastRun + 1 +
0436             ((lastRun + 255 - RUN_MASK) / 255) > (U32)maxOutputSize))
0437             return 0;
0438 
0439         if (lastRun >= RUN_MASK) {
0440             size_t accumulator = lastRun - RUN_MASK;
0441             *op++ = RUN_MASK << ML_BITS;
0442             for (; accumulator >= 255; accumulator -= 255)
0443                 *op++ = 255;
0444             *op++ = (BYTE) accumulator;
0445         } else {
0446             *op++ = (BYTE)(lastRun << ML_BITS);
0447         }
0448 
0449         LZ4_memcpy(op, anchor, lastRun);
0450 
0451         op += lastRun;
0452     }
0453 
0454     /* End */
0455     return (int) (((char *)op) - dest);
0456 }
0457 
0458 static int LZ4_compress_fast_extState(
0459     void *state,
0460     const char *source,
0461     char *dest,
0462     int inputSize,
0463     int maxOutputSize,
0464     int acceleration)
0465 {
0466     LZ4_stream_t_internal *ctx = &((LZ4_stream_t *)state)->internal_donotuse;
0467 #if LZ4_ARCH64
0468     const tableType_t tableType = byU32;
0469 #else
0470     const tableType_t tableType = byPtr;
0471 #endif
0472 
0473     LZ4_resetStream((LZ4_stream_t *)state);
0474 
0475     if (acceleration < 1)
0476         acceleration = LZ4_ACCELERATION_DEFAULT;
0477 
0478     if (maxOutputSize >= LZ4_COMPRESSBOUND(inputSize)) {
0479         if (inputSize < LZ4_64Klimit)
0480             return LZ4_compress_generic(ctx, source,
0481                 dest, inputSize, 0,
0482                 noLimit, byU16, noDict,
0483                 noDictIssue, acceleration);
0484         else
0485             return LZ4_compress_generic(ctx, source,
0486                 dest, inputSize, 0,
0487                 noLimit, tableType, noDict,
0488                 noDictIssue, acceleration);
0489     } else {
0490         if (inputSize < LZ4_64Klimit)
0491             return LZ4_compress_generic(ctx, source,
0492                 dest, inputSize,
0493                 maxOutputSize, limitedOutput, byU16, noDict,
0494                 noDictIssue, acceleration);
0495         else
0496             return LZ4_compress_generic(ctx, source,
0497                 dest, inputSize,
0498                 maxOutputSize, limitedOutput, tableType, noDict,
0499                 noDictIssue, acceleration);
0500     }
0501 }
0502 
0503 int LZ4_compress_fast(const char *source, char *dest, int inputSize,
0504     int maxOutputSize, int acceleration, void *wrkmem)
0505 {
0506     return LZ4_compress_fast_extState(wrkmem, source, dest, inputSize,
0507         maxOutputSize, acceleration);
0508 }
0509 EXPORT_SYMBOL(LZ4_compress_fast);
0510 
0511 int LZ4_compress_default(const char *source, char *dest, int inputSize,
0512     int maxOutputSize, void *wrkmem)
0513 {
0514     return LZ4_compress_fast(source, dest, inputSize,
0515         maxOutputSize, LZ4_ACCELERATION_DEFAULT, wrkmem);
0516 }
0517 EXPORT_SYMBOL(LZ4_compress_default);
0518 
0519 /*-******************************
0520  *  *_destSize() variant
0521  ********************************/
0522 static int LZ4_compress_destSize_generic(
0523     LZ4_stream_t_internal * const ctx,
0524     const char * const src,
0525     char * const dst,
0526     int * const srcSizePtr,
0527     const int targetDstSize,
0528     const tableType_t tableType)
0529 {
0530     const BYTE *ip = (const BYTE *) src;
0531     const BYTE *base = (const BYTE *) src;
0532     const BYTE *lowLimit = (const BYTE *) src;
0533     const BYTE *anchor = ip;
0534     const BYTE * const iend = ip + *srcSizePtr;
0535     const BYTE * const mflimit = iend - MFLIMIT;
0536     const BYTE * const matchlimit = iend - LASTLITERALS;
0537 
0538     BYTE *op = (BYTE *) dst;
0539     BYTE * const oend = op + targetDstSize;
0540     BYTE * const oMaxLit = op + targetDstSize - 2 /* offset */
0541         - 8 /* because 8 + MINMATCH == MFLIMIT */ - 1 /* token */;
0542     BYTE * const oMaxMatch = op + targetDstSize
0543         - (LASTLITERALS + 1 /* token */);
0544     BYTE * const oMaxSeq = oMaxLit - 1 /* token */;
0545 
0546     U32 forwardH;
0547 
0548     /* Init conditions */
0549     /* Impossible to store anything */
0550     if (targetDstSize < 1)
0551         return 0;
0552     /* Unsupported input size, too large (or negative) */
0553     if ((U32)*srcSizePtr > (U32)LZ4_MAX_INPUT_SIZE)
0554         return 0;
0555     /* Size too large (not within 64K limit) */
0556     if ((tableType == byU16) && (*srcSizePtr >= LZ4_64Klimit))
0557         return 0;
0558     /* Input too small, no compression (all literals) */
0559     if (*srcSizePtr < LZ4_minLength)
0560         goto _last_literals;
0561 
0562     /* First Byte */
0563     *srcSizePtr = 0;
0564     LZ4_putPosition(ip, ctx->hashTable, tableType, base);
0565     ip++; forwardH = LZ4_hashPosition(ip, tableType);
0566 
0567     /* Main Loop */
0568     for ( ; ; ) {
0569         const BYTE *match;
0570         BYTE *token;
0571 
0572         /* Find a match */
0573         {
0574             const BYTE *forwardIp = ip;
0575             unsigned int step = 1;
0576             unsigned int searchMatchNb = 1 << LZ4_SKIPTRIGGER;
0577 
0578             do {
0579                 U32 h = forwardH;
0580 
0581                 ip = forwardIp;
0582                 forwardIp += step;
0583                 step = (searchMatchNb++ >> LZ4_SKIPTRIGGER);
0584 
0585                 if (unlikely(forwardIp > mflimit))
0586                     goto _last_literals;
0587 
0588                 match = LZ4_getPositionOnHash(h, ctx->hashTable,
0589                     tableType, base);
0590                 forwardH = LZ4_hashPosition(forwardIp,
0591                     tableType);
0592                 LZ4_putPositionOnHash(ip, h,
0593                     ctx->hashTable, tableType,
0594                     base);
0595 
0596             } while (((tableType == byU16)
0597                 ? 0
0598                 : (match + MAX_DISTANCE < ip))
0599                 || (LZ4_read32(match) != LZ4_read32(ip)));
0600         }
0601 
0602         /* Catch up */
0603         while ((ip > anchor)
0604             && (match > lowLimit)
0605             && (unlikely(ip[-1] == match[-1]))) {
0606             ip--;
0607             match--;
0608         }
0609 
0610         /* Encode Literal length */
0611         {
0612             unsigned int litLength = (unsigned int)(ip - anchor);
0613 
0614             token = op++;
0615             if (op + ((litLength + 240) / 255)
0616                 + litLength > oMaxLit) {
0617                 /* Not enough space for a last match */
0618                 op--;
0619                 goto _last_literals;
0620             }
0621             if (litLength >= RUN_MASK) {
0622                 unsigned int len = litLength - RUN_MASK;
0623                 *token = (RUN_MASK<<ML_BITS);
0624                 for (; len >= 255; len -= 255)
0625                     *op++ = 255;
0626                 *op++ = (BYTE)len;
0627             } else
0628                 *token = (BYTE)(litLength << ML_BITS);
0629 
0630             /* Copy Literals */
0631             LZ4_wildCopy(op, anchor, op + litLength);
0632             op += litLength;
0633         }
0634 
0635 _next_match:
0636         /* Encode Offset */
0637         LZ4_writeLE16(op, (U16)(ip - match)); op += 2;
0638 
0639         /* Encode MatchLength */
0640         {
0641             size_t matchLength = LZ4_count(ip + MINMATCH,
0642             match + MINMATCH, matchlimit);
0643 
0644             if (op + ((matchLength + 240)/255) > oMaxMatch) {
0645                 /* Match description too long : reduce it */
0646                 matchLength = (15 - 1) + (oMaxMatch - op) * 255;
0647             }
0648             ip += MINMATCH + matchLength;
0649 
0650             if (matchLength >= ML_MASK) {
0651                 *token += ML_MASK;
0652                 matchLength -= ML_MASK;
0653                 while (matchLength >= 255) {
0654                     matchLength -= 255;
0655                     *op++ = 255;
0656                 }
0657                 *op++ = (BYTE)matchLength;
0658             } else
0659                 *token += (BYTE)(matchLength);
0660         }
0661 
0662         anchor = ip;
0663 
0664         /* Test end of block */
0665         if (ip > mflimit)
0666             break;
0667         if (op > oMaxSeq)
0668             break;
0669 
0670         /* Fill table */
0671         LZ4_putPosition(ip - 2, ctx->hashTable, tableType, base);
0672 
0673         /* Test next position */
0674         match = LZ4_getPosition(ip, ctx->hashTable, tableType, base);
0675         LZ4_putPosition(ip, ctx->hashTable, tableType, base);
0676 
0677         if ((match + MAX_DISTANCE >= ip)
0678             && (LZ4_read32(match) == LZ4_read32(ip))) {
0679             token = op++; *token = 0;
0680             goto _next_match;
0681         }
0682 
0683         /* Prepare next loop */
0684         forwardH = LZ4_hashPosition(++ip, tableType);
0685     }
0686 
0687 _last_literals:
0688     /* Encode Last Literals */
0689     {
0690         size_t lastRunSize = (size_t)(iend - anchor);
0691 
0692         if (op + 1 /* token */
0693             + ((lastRunSize + 240) / 255) /* litLength */
0694             + lastRunSize /* literals */ > oend) {
0695             /* adapt lastRunSize to fill 'dst' */
0696             lastRunSize = (oend - op) - 1;
0697             lastRunSize -= (lastRunSize + 240) / 255;
0698         }
0699         ip = anchor + lastRunSize;
0700 
0701         if (lastRunSize >= RUN_MASK) {
0702             size_t accumulator = lastRunSize - RUN_MASK;
0703 
0704             *op++ = RUN_MASK << ML_BITS;
0705             for (; accumulator >= 255; accumulator -= 255)
0706                 *op++ = 255;
0707             *op++ = (BYTE) accumulator;
0708         } else {
0709             *op++ = (BYTE)(lastRunSize<<ML_BITS);
0710         }
0711         LZ4_memcpy(op, anchor, lastRunSize);
0712         op += lastRunSize;
0713     }
0714 
0715     /* End */
0716     *srcSizePtr = (int) (((const char *)ip) - src);
0717     return (int) (((char *)op) - dst);
0718 }
0719 
0720 static int LZ4_compress_destSize_extState(
0721     LZ4_stream_t *state,
0722     const char *src,
0723     char *dst,
0724     int *srcSizePtr,
0725     int targetDstSize)
0726 {
0727 #if LZ4_ARCH64
0728     const tableType_t tableType = byU32;
0729 #else
0730     const tableType_t tableType = byPtr;
0731 #endif
0732 
0733     LZ4_resetStream(state);
0734 
0735     if (targetDstSize >= LZ4_COMPRESSBOUND(*srcSizePtr)) {
0736         /* compression success is guaranteed */
0737         return LZ4_compress_fast_extState(
0738             state, src, dst, *srcSizePtr,
0739             targetDstSize, 1);
0740     } else {
0741         if (*srcSizePtr < LZ4_64Klimit)
0742             return LZ4_compress_destSize_generic(
0743                 &state->internal_donotuse,
0744                 src, dst, srcSizePtr,
0745                 targetDstSize, byU16);
0746         else
0747             return LZ4_compress_destSize_generic(
0748                 &state->internal_donotuse,
0749                 src, dst, srcSizePtr,
0750                 targetDstSize, tableType);
0751     }
0752 }
0753 
0754 
0755 int LZ4_compress_destSize(
0756     const char *src,
0757     char *dst,
0758     int *srcSizePtr,
0759     int targetDstSize,
0760     void *wrkmem)
0761 {
0762     return LZ4_compress_destSize_extState(wrkmem, src, dst, srcSizePtr,
0763         targetDstSize);
0764 }
0765 EXPORT_SYMBOL(LZ4_compress_destSize);
0766 
0767 /*-******************************
0768  *  Streaming functions
0769  ********************************/
0770 void LZ4_resetStream(LZ4_stream_t *LZ4_stream)
0771 {
0772     memset(LZ4_stream, 0, sizeof(LZ4_stream_t));
0773 }
0774 
0775 int LZ4_loadDict(LZ4_stream_t *LZ4_dict,
0776     const char *dictionary, int dictSize)
0777 {
0778     LZ4_stream_t_internal *dict = &LZ4_dict->internal_donotuse;
0779     const BYTE *p = (const BYTE *)dictionary;
0780     const BYTE * const dictEnd = p + dictSize;
0781     const BYTE *base;
0782 
0783     if ((dict->initCheck)
0784         || (dict->currentOffset > 1 * GB)) {
0785         /* Uninitialized structure, or reuse overflow */
0786         LZ4_resetStream(LZ4_dict);
0787     }
0788 
0789     if (dictSize < (int)HASH_UNIT) {
0790         dict->dictionary = NULL;
0791         dict->dictSize = 0;
0792         return 0;
0793     }
0794 
0795     if ((dictEnd - p) > 64 * KB)
0796         p = dictEnd - 64 * KB;
0797     dict->currentOffset += 64 * KB;
0798     base = p - dict->currentOffset;
0799     dict->dictionary = p;
0800     dict->dictSize = (U32)(dictEnd - p);
0801     dict->currentOffset += dict->dictSize;
0802 
0803     while (p <= dictEnd - HASH_UNIT) {
0804         LZ4_putPosition(p, dict->hashTable, byU32, base);
0805         p += 3;
0806     }
0807 
0808     return dict->dictSize;
0809 }
0810 EXPORT_SYMBOL(LZ4_loadDict);
0811 
0812 static void LZ4_renormDictT(LZ4_stream_t_internal *LZ4_dict,
0813     const BYTE *src)
0814 {
0815     if ((LZ4_dict->currentOffset > 0x80000000) ||
0816         ((uptrval)LZ4_dict->currentOffset > (uptrval)src)) {
0817         /* address space overflow */
0818         /* rescale hash table */
0819         U32 const delta = LZ4_dict->currentOffset - 64 * KB;
0820         const BYTE *dictEnd = LZ4_dict->dictionary + LZ4_dict->dictSize;
0821         int i;
0822 
0823         for (i = 0; i < LZ4_HASH_SIZE_U32; i++) {
0824             if (LZ4_dict->hashTable[i] < delta)
0825                 LZ4_dict->hashTable[i] = 0;
0826             else
0827                 LZ4_dict->hashTable[i] -= delta;
0828         }
0829         LZ4_dict->currentOffset = 64 * KB;
0830         if (LZ4_dict->dictSize > 64 * KB)
0831             LZ4_dict->dictSize = 64 * KB;
0832         LZ4_dict->dictionary = dictEnd - LZ4_dict->dictSize;
0833     }
0834 }
0835 
0836 int LZ4_saveDict(LZ4_stream_t *LZ4_dict, char *safeBuffer, int dictSize)
0837 {
0838     LZ4_stream_t_internal * const dict = &LZ4_dict->internal_donotuse;
0839     const BYTE * const previousDictEnd = dict->dictionary + dict->dictSize;
0840 
0841     if ((U32)dictSize > 64 * KB) {
0842         /* useless to define a dictionary > 64 * KB */
0843         dictSize = 64 * KB;
0844     }
0845     if ((U32)dictSize > dict->dictSize)
0846         dictSize = dict->dictSize;
0847 
0848     memmove(safeBuffer, previousDictEnd - dictSize, dictSize);
0849 
0850     dict->dictionary = (const BYTE *)safeBuffer;
0851     dict->dictSize = (U32)dictSize;
0852 
0853     return dictSize;
0854 }
0855 EXPORT_SYMBOL(LZ4_saveDict);
0856 
0857 int LZ4_compress_fast_continue(LZ4_stream_t *LZ4_stream, const char *source,
0858     char *dest, int inputSize, int maxOutputSize, int acceleration)
0859 {
0860     LZ4_stream_t_internal *streamPtr = &LZ4_stream->internal_donotuse;
0861     const BYTE * const dictEnd = streamPtr->dictionary
0862         + streamPtr->dictSize;
0863 
0864     const BYTE *smallest = (const BYTE *) source;
0865 
0866     if (streamPtr->initCheck) {
0867         /* Uninitialized structure detected */
0868         return 0;
0869     }
0870 
0871     if ((streamPtr->dictSize > 0) && (smallest > dictEnd))
0872         smallest = dictEnd;
0873 
0874     LZ4_renormDictT(streamPtr, smallest);
0875 
0876     if (acceleration < 1)
0877         acceleration = LZ4_ACCELERATION_DEFAULT;
0878 
0879     /* Check overlapping input/dictionary space */
0880     {
0881         const BYTE *sourceEnd = (const BYTE *) source + inputSize;
0882 
0883         if ((sourceEnd > streamPtr->dictionary)
0884             && (sourceEnd < dictEnd)) {
0885             streamPtr->dictSize = (U32)(dictEnd - sourceEnd);
0886             if (streamPtr->dictSize > 64 * KB)
0887                 streamPtr->dictSize = 64 * KB;
0888             if (streamPtr->dictSize < 4)
0889                 streamPtr->dictSize = 0;
0890             streamPtr->dictionary = dictEnd - streamPtr->dictSize;
0891         }
0892     }
0893 
0894     /* prefix mode : source data follows dictionary */
0895     if (dictEnd == (const BYTE *)source) {
0896         int result;
0897 
0898         if ((streamPtr->dictSize < 64 * KB) &&
0899             (streamPtr->dictSize < streamPtr->currentOffset)) {
0900             result = LZ4_compress_generic(
0901                 streamPtr, source, dest, inputSize,
0902                 maxOutputSize, limitedOutput, byU32,
0903                 withPrefix64k, dictSmall, acceleration);
0904         } else {
0905             result = LZ4_compress_generic(
0906                 streamPtr, source, dest, inputSize,
0907                 maxOutputSize, limitedOutput, byU32,
0908                 withPrefix64k, noDictIssue, acceleration);
0909         }
0910         streamPtr->dictSize += (U32)inputSize;
0911         streamPtr->currentOffset += (U32)inputSize;
0912         return result;
0913     }
0914 
0915     /* external dictionary mode */
0916     {
0917         int result;
0918 
0919         if ((streamPtr->dictSize < 64 * KB) &&
0920             (streamPtr->dictSize < streamPtr->currentOffset)) {
0921             result = LZ4_compress_generic(
0922                 streamPtr, source, dest, inputSize,
0923                 maxOutputSize, limitedOutput, byU32,
0924                 usingExtDict, dictSmall, acceleration);
0925         } else {
0926             result = LZ4_compress_generic(
0927                 streamPtr, source, dest, inputSize,
0928                 maxOutputSize, limitedOutput, byU32,
0929                 usingExtDict, noDictIssue, acceleration);
0930         }
0931         streamPtr->dictionary = (const BYTE *)source;
0932         streamPtr->dictSize = (U32)inputSize;
0933         streamPtr->currentOffset += (U32)inputSize;
0934         return result;
0935     }
0936 }
0937 EXPORT_SYMBOL(LZ4_compress_fast_continue);
0938 
0939 MODULE_LICENSE("Dual BSD/GPL");
0940 MODULE_DESCRIPTION("LZ4 compressor");
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.1.0 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!