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