wonderful-mobile/exynos-linux-stable
2
0
Fork 0
Code Issues Pull requests Projects Releases Packages Wiki Activity Actions
exynos-linux-stable/lib/lz4/lz4_compress.c
Andrzej Perczak 3d0695d4f3
lz4: Update to version 1.9.4 
Signed-off-by: Andrzej Perczak <linux@andrzejperczak.com>
2023-02-21 00:24:44 +03:00

1226 lines
37 KiB
C
Raw Permalink Blame History

/*
* LZ4 - Fast LZ compression algorithm
* Copyright (C) 2011 - 2016, Yann Collet.
* BSD 2 - Clause License (http://www.opensource.org/licenses/bsd - license.php)
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
* met:
* * Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* * Redistributions in binary form must reproduce the above
* copyright notice, this list of conditions and the following disclaimer
* in the documentation and/or other materials provided with the
* distribution.
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
* OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
* You can contact the author at :
* - LZ4 homepage : http://www.lz4.org
* - LZ4 source repository : https://github.com/lz4/lz4
*
* Changed for kernel usage by:
* Sven Schmidt <4sschmid@informatik.uni-hamburg.de>
*/
/*-************************************
* Dependencies
**************************************/
#include <linux/lz4.h>
#include "lz4defs.h"
#include <linux/module.h>
#include <linux/kernel.h>
#include <asm/unaligned.h>
static const int LZ4_minLength = (MFLIMIT + 1);
static const int LZ4_64Klimit = ((64 * KB) + (MFLIMIT - 1));
/* Increase this value ==> compression run slower on incompressible data */
static const U32 LZ4_skipTrigger = 6;
LZ4_stream_t *LZ4_initStream(void *buffer, size_t size);
/*-******************************
* Compression functions
********************************/
static FORCE_INLINE U32 LZ4_hash4(U32 sequence, tableType_t const tableType)
{
if (tableType == byU16)
return ((sequence * 2654435761U) >>
((MINMATCH * 8) - (LZ4_HASHLOG + 1)));
else
return ((sequence * 2654435761U) >>
((MINMATCH * 8) - LZ4_HASHLOG));
}
static FORCE_INLINE U32 LZ4_hash5(U64 sequence, tableType_t const tableType)
{
const U32 hashLog = (tableType == byU16) ? LZ4_HASHLOG + 1 :
LZ4_HASHLOG;
#if LZ4_LITTLE_ENDIAN
static const U64 prime5bytes = 889523592379ULL;
return (U32)(((sequence << 24) * prime5bytes) >> (64 - hashLog));
#else
static const U64 prime8bytes = 11400714785074694791ULL;
return (U32)(((sequence >> 24) * prime8bytes) >> (64 - hashLog));
#endif
}
static FORCE_INLINE U32 LZ4_hashPosition(const void *p,
tableType_t const tableType)
{
#if LZ4_ARCH64
if (tableType != byU16)
return LZ4_hash5(LZ4_read_ARCH(p), tableType);
#endif
return LZ4_hash4(LZ4_read32(p), tableType);
}
static FORCE_INLINE void LZ4_clearHash(U32 h, void *tableBase,
tableType_t const tableType)
{
switch (tableType) {
default: /* fallthrough */
case clearedTable: { /* illegal! */
assert(0);
return;
}
case byPtr: {
const BYTE **hashTable = (const BYTE **)tableBase;
hashTable[h] = NULL;
return;
}
case byU32: {
U32 *hashTable = (U32 *)tableBase;
hashTable[h] = 0;
return;
}
case byU16: {
U16 *hashTable = (U16 *)tableBase;
hashTable[h] = 0;
return;
}
}
}
static FORCE_INLINE void LZ4_putIndexOnHash(U32 idx, U32 h, void *tableBase,
tableType_t const tableType)
{
switch (tableType) {
default: /* fallthrough */
case clearedTable: /* fallthrough */
case byPtr: { /* illegal! */
assert(0);
return;
}
case byU32: {
U32 *hashTable = (U32 *)tableBase;
hashTable[h] = idx;
return;
}
case byU16: {
U16 *hashTable = (U16 *)tableBase;
assert(idx < 65536);
hashTable[h] = (U16)idx;
return;
}
}
}
static void LZ4_putPositionOnHash(const BYTE *p, U32 h, void *tableBase,
tableType_t const tableType,
const BYTE *srcBase)
{
switch (tableType) {
case byPtr: {
const BYTE **hashTable = (const BYTE **)tableBase;
hashTable[h] = p;
return;
}
case byU32: {
U32 *hashTable = (U32 *)tableBase;
hashTable[h] = (U32)(p - srcBase);
return;
}
case byU16: {
U16 *hashTable = (U16 *)tableBase;
hashTable[h] = (U16)(p - srcBase);
return;
}
case clearedTable: { /* fallthrough */
}
}
}
static FORCE_INLINE void LZ4_putPosition(const BYTE *p, void *tableBase,
tableType_t tableType,
const BYTE *srcBase)
{
U32 const h = LZ4_hashPosition(p, tableType);
LZ4_putPositionOnHash(p, h, tableBase, tableType, srcBase);
}
/* LZ4_getIndexOnHash() :
* Index of match position registered in hash table.
* hash position must be calculated by using base+index, or dictBase+index.
* Assumption 1 : only valid if tableType == byU32 or byU16.
* Assumption 2 : h is presumed valid (within limits of hash table)
*/
static FORCE_INLINE U32 LZ4_getIndexOnHash(U32 h, const void *tableBase,
tableType_t tableType)
{
LZ4_STATIC_ASSERT(LZ4_MEMORY_USAGE > 2);
if (tableType == byU32) {
const U32 *const hashTable = (const U32 *)tableBase;
assert(h < (1U << (LZ4_MEMORY_USAGE - 2)));
return hashTable[h];
}
if (tableType == byU16) {
const U16 *const hashTable = (const U16 *)tableBase;
assert(h < (1U << (LZ4_MEMORY_USAGE - 1)));
return hashTable[h];
}
assert(0);
return 0; /* forbidden case */
}
static const BYTE *LZ4_getPositionOnHash(U32 h, void *tableBase,
tableType_t tableType,
const BYTE *srcBase)
{
if (tableType == byPtr) {
const BYTE **hashTable = (const BYTE **)tableBase;
return hashTable[h];
}
if (tableType == byU32) {
const U32 *const hashTable = (U32 *)tableBase;
return hashTable[h] + srcBase;
}
{
/* default, to ensure a return */
const U16 *const hashTable = (U16 *)tableBase;
return hashTable[h] + srcBase;
}
}
static FORCE_INLINE const BYTE *LZ4_getPosition(const BYTE *p, void *tableBase,
tableType_t tableType,
const BYTE *srcBase)
{
U32 const h = LZ4_hashPosition(p, tableType);
return LZ4_getPositionOnHash(h, tableBase, tableType, srcBase);
}
static FORCE_INLINE void LZ4_prepareTable(LZ4_stream_t_internal *const cctx,
const int inputSize,
const tableType_t tableType)
{
/* If the table hasn't been used, it's guaranteed to be zeroed out, and is
* therefore safe to use no matter what mode we're in. Otherwise, we figure
* out if it's safe to leave as is or whether it needs to be reset.
*/
if ((tableType_t)cctx->tableType != clearedTable) {
assert(inputSize >= 0);
if ((tableType_t)cctx->tableType != tableType ||
((tableType == byU16) &&
cctx->currentOffset + (unsigned)inputSize >= 0xFFFFU) ||
((tableType == byU32) && cctx->currentOffset > 1 * GB) ||
tableType == byPtr || inputSize >= 4 * KB) {
DEBUGLOG(4, "LZ4_prepareTable: Resetting table in %p",
cctx);
memset(cctx->hashTable, 0, LZ4_HASHTABLESIZE);
cctx->currentOffset = 0;
cctx->tableType = (U32)clearedTable;
} else {
DEBUGLOG(
4,
"LZ4_prepareTable: Re-use hash table (no reset)");
}
}
/* Adding a gap, so all previous entries are > LZ4_DISTANCE_MAX back,
* is faster than compressing without a gap.
* However, compressing with currentOffset == 0 is faster still,
* so we preserve that case.
*/
if (cctx->currentOffset != 0 && tableType == byU32) {
DEBUGLOG(5, "LZ4_prepareTable: adding 64KB to currentOffset");
cctx->currentOffset += 64 * KB;
}
/* Finally, clear history */
cctx->dictCtx = NULL;
cctx->dictionary = NULL;
cctx->dictSize = 0;
}
/** LZ4_compress_generic() :
* inlined, to ensure branches are decided at compilation time.
* Presumed already validated at this stage:
* - source != NULL
* - inputSize > 0
*/
static FORCE_INLINE int LZ4_compress_generic_validated(
LZ4_stream_t_internal *const cctx, const char *const source,
char *const dest, const int inputSize,
int *inputConsumed, /* only written when outputDirective == fillOutput */
const int maxOutputSize, const limitedOutput_directive outputDirective,
const tableType_t tableType, const dict_directive dictDirective,
const dictIssue_directive dictIssue, const int acceleration)
{
int result;
const BYTE *ip = (const BYTE *)source;
U32 const startIndex = cctx->currentOffset;
const BYTE *base = (const BYTE *)source - startIndex;
const BYTE *lowLimit;
const LZ4_stream_t_internal *dictCtx =
(const LZ4_stream_t_internal *)cctx->dictCtx;
const BYTE *const dictionary = dictDirective == usingDictCtx ?
dictCtx->dictionary :
cctx->dictionary;
const U32 dictSize = dictDirective == usingDictCtx ? dictCtx->dictSize :
cctx->dictSize;
const U32 dictDelta =
(dictDirective == usingDictCtx) ?
startIndex - dictCtx->currentOffset :
0; /* make indexes in dictCtx comparable with index in current context */
int const maybe_extMem = (dictDirective == usingExtDict) ||
(dictDirective == usingDictCtx);
U32 const prefixIdxLimit =
startIndex -
dictSize; /* used when dictDirective == dictSmall */
const BYTE *const dictEnd = dictionary ? dictionary + dictSize :
dictionary;
const BYTE *anchor = (const BYTE *)source;
const BYTE *const iend = ip + inputSize;
const BYTE *const mflimitPlusOne = iend - MFLIMIT + 1;
const BYTE *const matchlimit = iend - LASTLITERALS;
/* the dictCtx currentOffset is indexed on the start of the dictionary,
* while a dictionary in the current context precedes the currentOffset */
const BYTE *dictBase =
(dictionary == NULL) ?
NULL :
(dictDirective == usingDictCtx) ?
dictionary + dictSize - dictCtx->currentOffset :
dictionary + dictSize - startIndex;
BYTE *op = (BYTE *)dest;
BYTE *const olimit = op + maxOutputSize;
U32 offset = 0;
U32 forwardH;
DEBUGLOG(5, "LZ4_compress_generic_validated: srcSize=%i, tableType=%u",
inputSize, tableType);
assert(ip != NULL);
/* If init conditions are not met, we don't have to mark stream
* as having dirty context, since no action was taken yet */
if (outputDirective == fillOutput && maxOutputSize < 1) {
return 0;
} /* Impossible to store anything */
if ((tableType == byU16) && (inputSize >= LZ4_64Klimit)) {
return 0;
} /* Size too large (not within 64K limit) */
if (tableType == byPtr)
assert(dictDirective ==
noDict); /* only supported use case with byPtr */
assert(acceleration >= 1);
lowLimit = (const BYTE *)source -
(dictDirective == withPrefix64k ? dictSize : 0);
/* Update context state */
if (dictDirective == usingDictCtx) {
/* Subsequent linked blocks can't use the dictionary. */
/* Instead, they use the block we just compressed. */
cctx->dictCtx = NULL;
cctx->dictSize = (U32)inputSize;
} else {
cctx->dictSize += (U32)inputSize;
}
cctx->currentOffset += (U32)inputSize;
cctx->tableType = (U32)tableType;
if (inputSize < LZ4_minLength)
goto _last_literals; /* Input too small, no compression (all literals) */
/* First Byte */
LZ4_putPosition(ip, cctx->hashTable, tableType, base);
ip++;
forwardH = LZ4_hashPosition(ip, tableType);
/* Main Loop */
for (;;) {
const BYTE *match;
BYTE *token;
const BYTE *filledIp;
/* Find a match */
if (tableType == byPtr) {
const BYTE *forwardIp = ip;
int step = 1;
int searchMatchNb = acceleration << LZ4_skipTrigger;
do {
U32 const h = forwardH;
ip = forwardIp;
forwardIp += step;
step = (searchMatchNb++ >> LZ4_skipTrigger);
if (unlikely(forwardIp > mflimitPlusOne))
goto _last_literals;
assert(ip < mflimitPlusOne);
match = LZ4_getPositionOnHash(
h, cctx->hashTable, tableType, base);
forwardH =
LZ4_hashPosition(forwardIp, tableType);
LZ4_putPositionOnHash(ip, h, cctx->hashTable,
tableType, base);
} while ((match + LZ4_DISTANCE_MAX < ip) ||
(LZ4_read32(match) != LZ4_read32(ip)));
} else { /* byU32, byU16 */
const BYTE *forwardIp = ip;
int step = 1;
int searchMatchNb = acceleration << LZ4_skipTrigger;
do {
U32 const h = forwardH;
U32 const cur = (U32)(forwardIp - base);
U32 matchIndex = LZ4_getIndexOnHash(
h, cctx->hashTable, tableType);
assert(matchIndex <= cur);
assert(forwardIp - base <
(ptrdiff_t)(2 * GB - 1));
ip = forwardIp;
forwardIp += step;
step = (searchMatchNb++ >> LZ4_skipTrigger);
if (unlikely(forwardIp > mflimitPlusOne))
goto _last_literals;
assert(ip < mflimitPlusOne);
if (dictDirective == usingDictCtx) {
if (matchIndex < startIndex) {
/* there was no match, try the dictionary */
assert(tableType == byU32);
matchIndex = LZ4_getIndexOnHash(
h, dictCtx->hashTable,
byU32);
match = dictBase + matchIndex;
matchIndex +=
dictDelta; /* make dictCtx index comparable with current context */
lowLimit = dictionary;
} else {
match = base + matchIndex;
lowLimit = (const BYTE *)source;
}
} else if (dictDirective == usingExtDict) {
if (matchIndex < startIndex) {
DEBUGLOG(
7,
"extDict candidate: matchIndex=%5u < startIndex=%5u",
matchIndex, startIndex);
assert(startIndex -
matchIndex >=
MINMATCH);
assert(dictBase);
match = dictBase + matchIndex;
lowLimit = dictionary;
} else {
match = base + matchIndex;
lowLimit = (const BYTE *)source;
}
} else { /* single continuous memory segment */
match = base + matchIndex;
}
forwardH =
LZ4_hashPosition(forwardIp, tableType);
LZ4_putIndexOnHash(cur, h, cctx->hashTable,
tableType);
DEBUGLOG(7,
"candidate at pos=%u (offset=%u \n",
matchIndex, cur - matchIndex);
if ((dictIssue == dictSmall) &&
(matchIndex < prefixIdxLimit)) {
continue;
} /* match outside of valid area */
assert(matchIndex < cur);
if (((tableType != byU16) ||
(LZ4_DISTANCE_MAX <
LZ4_DISTANCE_ABSOLUTE_MAX)) &&
(matchIndex + LZ4_DISTANCE_MAX < cur)) {
continue;
} /* too far */
assert((cur - matchIndex) <=
LZ4_DISTANCE_MAX); /* match now expected within distance */
if (LZ4_read32(match) == LZ4_read32(ip)) {
if (maybe_extMem)
offset = cur - matchIndex;
break; /* match found */
}
} while (1);
}
/* Catch up */
filledIp = ip;
while (((ip > anchor) & (match > lowLimit)) &&
(unlikely(ip[-1] == match[-1]))) {
ip--;
match--;
}
/* Encode Literals */
{
unsigned const litLength = (unsigned)(ip - anchor);
token = op++;
if ((outputDirective ==
limitedOutput) && /* Check output buffer overflow */
(unlikely(op + litLength + (2 + 1 + LASTLITERALS) +
(litLength / 255) >
olimit))) {
return 0; /* cannot compress within `dst` budget. Stored indexes in hash table are nonetheless fine */
}
if ((outputDirective == fillOutput) &&
(unlikely(
op + (litLength + 240) / 255 /* litlen */ +
litLength /* literals */ +
2 /* offset */ + 1 /* token */ +
MFLIMIT -
MINMATCH /* min last literals so last match is <= end - MFLIMIT */
> olimit))) {
op--;
goto _last_literals;
}
if (litLength >= RUN_MASK) {
int len = (int)(litLength - RUN_MASK);
*token = (RUN_MASK << ML_BITS);
for (; len >= 255; len -= 255)
*op++ = 255;
*op++ = (BYTE)len;
} else
*token = (BYTE)(litLength << ML_BITS);
/* Copy Literals */
LZ4_wildCopy8(op, anchor, op + litLength);
op += litLength;
DEBUGLOG(6, "seq.start:%i, literals=%u, match.start:%i",
(int)(anchor - (const BYTE *)source),
litLength, (int)(ip - (const BYTE *)source));
}
_next_match:
/* at this stage, the following variables must be correctly set :
* - ip : at start of LZ operation
* - match : at start of previous pattern occurrence; can be within current prefix, or within extDict
* - offset : if maybe_ext_memSegment==1 (constant)
* - lowLimit : must be == dictionary to mean "match is within extDict"; must be == source otherwise
* - token and *token : position to write 4-bits for match length; higher 4-bits for literal length supposed already written
*/
if ((outputDirective == fillOutput) &&
(op + 2 /* offset */ + 1 /* token */ + MFLIMIT -
MINMATCH /* min last literals so last match is <= end - MFLIMIT */
> olimit)) {
/* the match was too close to the end, rewind and go to last literals */
op = token;
goto _last_literals;
}
/* Encode Offset */
if (maybe_extMem) { /* static test */
DEBUGLOG(6,
" with offset=%u (ext if > %i)",
offset, (int)(ip - (const BYTE *)source));
assert(offset <= LZ4_DISTANCE_MAX && offset > 0);
LZ4_writeLE16(op, (U16)offset);
op += 2;
} else {
DEBUGLOG(6,
" with offset=%u (same segment)",
(U32)(ip - match));
assert(ip - match <= LZ4_DISTANCE_MAX);
LZ4_writeLE16(op, (U16)(ip - match));
op += 2;
}
/* Encode MatchLength */
{
unsigned matchCode;
if ((dictDirective == usingExtDict ||
dictDirective == usingDictCtx) &&
(lowLimit ==
dictionary) /* match within extDict */) {
const BYTE *limit = ip + (dictEnd - match);
assert(dictEnd > match);
if (limit > matchlimit)
limit = matchlimit;
matchCode = LZ4_count(ip + MINMATCH,
match + MINMATCH, limit);
ip += (size_t)matchCode + MINMATCH;
if (ip == limit) {
unsigned const more = LZ4_count(
limit, (const BYTE *)source,
matchlimit);
matchCode += more;
ip += more;
}
DEBUGLOG(
6,
" with matchLength=%u starting in extDict",
matchCode + MINMATCH);
} else {
matchCode = LZ4_count(ip + MINMATCH,
match + MINMATCH,
matchlimit);
ip += (size_t)matchCode + MINMATCH;
DEBUGLOG(6, " with matchLength=%u",
matchCode + MINMATCH);
}
if ((outputDirective) && /* Check output buffer overflow */
(unlikely(op + (1 + LASTLITERALS) +
(matchCode + 240) / 255 >
olimit))) {
if (outputDirective == fillOutput) {
/* Match description too long : reduce it */
U32 newMatchCode =
15 /* in token */ -
1 /* to avoid needing a zero byte */ +
((U32)(olimit - op) - 1 -
LASTLITERALS) *
255;
ip -= matchCode - newMatchCode;
assert(newMatchCode < matchCode);
matchCode = newMatchCode;
if (unlikely(ip <= filledIp)) {
/* We have already filled up to filledIp so if ip ends up less than filledIp
* we have positions in the hash table beyond the current position. This is
* a problem if we reuse the hash table. So we have to remove these positions
* from the hash table.
*/
const BYTE *ptr;
DEBUGLOG(
5,
"Clearing %u positions",
(U32)(filledIp - ip));
for (ptr = ip; ptr <= filledIp;
++ptr) {
U32 const h =
LZ4_hashPosition(
ptr,
tableType);
LZ4_clearHash(
h,
cctx->hashTable,
tableType);
}
}
} else {
assert(outputDirective ==
limitedOutput);
return 0; /* cannot compress within `dst` budget. Stored indexes in hash table are nonetheless fine */
}
}
if (matchCode >= ML_MASK) {
*token += ML_MASK;
matchCode -= ML_MASK;
LZ4_write32(op, 0xFFFFFFFF);
while (matchCode >= 4 * 255) {
op += 4;
LZ4_write32(op, 0xFFFFFFFF);
matchCode -= 4 * 255;
}
op += matchCode / 255;
*op++ = (BYTE)(matchCode % 255);
} else
*token += (BYTE)(matchCode);
}
/* Ensure we have enough space for the last literals. */
assert(!(outputDirective == fillOutput &&
op + 1 + LASTLITERALS > olimit));
anchor = ip;
/* Test end of chunk */
if (ip >= mflimitPlusOne)
break;
/* Fill table */
LZ4_putPosition(ip - 2, cctx->hashTable, tableType, base);
/* Test next position */
if (tableType == byPtr) {
match = LZ4_getPosition(ip, cctx->hashTable, tableType,
base);
LZ4_putPosition(ip, cctx->hashTable, tableType, base);
if ((match + LZ4_DISTANCE_MAX >= ip) &&
(LZ4_read32(match) == LZ4_read32(ip))) {
token = op++;
*token = 0;
goto _next_match;
}
} else { /* byU32, byU16 */
U32 const h = LZ4_hashPosition(ip, tableType);
U32 const cur = (U32)(ip - base);
U32 matchIndex = LZ4_getIndexOnHash(h, cctx->hashTable,
tableType);
assert(matchIndex < cur);
if (dictDirective == usingDictCtx) {
if (matchIndex < startIndex) {
/* there was no match, try the dictionary */
matchIndex = LZ4_getIndexOnHash(
h, dictCtx->hashTable, byU32);
match = dictBase + matchIndex;
lowLimit =
dictionary; /* required for match length counter */
matchIndex += dictDelta;
} else {
match = base + matchIndex;
lowLimit = (const BYTE *)
source; /* required for match length counter */
}
} else if (dictDirective == usingExtDict) {
if (matchIndex < startIndex) {
assert(dictBase);
match = dictBase + matchIndex;
lowLimit =
dictionary; /* required for match length counter */
} else {
match = base + matchIndex;
lowLimit = (const BYTE *)
source; /* required for match length counter */
}
} else { /* single memory segment */
match = base + matchIndex;
}
LZ4_putIndexOnHash(cur, h, cctx->hashTable, tableType);
assert(matchIndex < cur);
if (((dictIssue == dictSmall) ?
(matchIndex >= prefixIdxLimit) :
1) &&
(((tableType == byU16) &&
(LZ4_DISTANCE_MAX == LZ4_DISTANCE_ABSOLUTE_MAX)) ?
1 :
(matchIndex + LZ4_DISTANCE_MAX >= cur)) &&
(LZ4_read32(match) == LZ4_read32(ip))) {
token = op++;
*token = 0;
if (maybe_extMem)
offset = cur - matchIndex;
DEBUGLOG(
6,
"seq.start:%i, literals=%u, match.start:%i",
(int)(anchor - (const BYTE *)source), 0,
(int)(ip - (const BYTE *)source));
goto _next_match;
}
}
/* Prepare next loop */
forwardH = LZ4_hashPosition(++ip, tableType);
}
_last_literals:
/* Encode Last Literals */
{
size_t lastRun = (size_t)(iend - anchor);
if ((outputDirective) && /* Check output buffer overflow */
(op + lastRun + 1 + ((lastRun + 255 - RUN_MASK) / 255) >
olimit)) {
if (outputDirective == fillOutput) {
/* adapt lastRun to fill 'dst' */
assert(olimit >= op);
lastRun = (size_t)(olimit - op) - 1 /*token*/;
lastRun -= (lastRun + 256 - RUN_MASK) /
256; /*additional length tokens*/
} else {
assert(outputDirective == limitedOutput);
return 0; /* cannot compress within `dst` budget. Stored indexes in hash table are nonetheless fine */
}
}
DEBUGLOG(6, "Final literal run : %i literals", (int)lastRun);
if (lastRun >= RUN_MASK) {
size_t accumulator = lastRun - RUN_MASK;
*op++ = RUN_MASK << ML_BITS;
for (; accumulator >= 255; accumulator -= 255)
*op++ = 255;
*op++ = (BYTE)accumulator;
} else {
*op++ = (BYTE)(lastRun << ML_BITS);
}
LZ4_memcpy(op, anchor, lastRun);
ip = anchor + lastRun;
op += lastRun;
}
if (outputDirective == fillOutput) {
*inputConsumed = (int)(((const char *)ip) - source);
}
result = (int)(((char *)op) - dest);
assert(result > 0);
DEBUGLOG(5, "LZ4_compress_generic: compressed %i bytes into %i bytes",
inputSize, result);
return result;
}
/** LZ4_compress_generic() :
* inlined, to ensure branches are decided at compilation time;
* takes care of src == (NULL, 0)
* and forward the rest to LZ4_compress_generic_validated */
static FORCE_INLINE int LZ4_compress_generic(
LZ4_stream_t_internal *const cctx, const char *const src,
char *const dst, const int srcSize,
int *inputConsumed, /* only written when outputDirective == fillOutput */
const int dstCapacity, const limitedOutput_directive outputDirective,
const tableType_t tableType, const dict_directive dictDirective,
const dictIssue_directive dictIssue, const int acceleration)
{
DEBUGLOG(5, "LZ4_compress_generic: srcSize=%i, dstCapacity=%i", srcSize,
dstCapacity);
if ((U32)srcSize > (U32)LZ4_MAX_INPUT_SIZE) {
return 0;
} /* Unsupported srcSize, too large (or negative) */
if (srcSize == 0) { /* src == NULL supported if srcSize == 0 */
if (outputDirective != notLimited && dstCapacity <= 0)
return 0; /* no output, can't write anything */
DEBUGLOG(5, "Generating an empty block");
assert(outputDirective == notLimited || dstCapacity >= 1);
assert(dst != NULL);
dst[0] = 0;
if (outputDirective == fillOutput) {
assert(inputConsumed != NULL);
*inputConsumed = 0;
}
return 1;
}
assert(src != NULL);
return LZ4_compress_generic_validated(
cctx, src, dst, srcSize,
inputConsumed, /* only written into if outputDirective == fillOutput */
dstCapacity, outputDirective, tableType, dictDirective,
dictIssue, acceleration);
}
int LZ4_compress_fast_extState(void *state, const char *source, char *dest,
int inputSize, int maxOutputSize,
int acceleration)
{
LZ4_stream_t_internal *const ctx =
&LZ4_initStream(state, sizeof(LZ4_stream_t))->internal_donotuse;
assert(ctx != NULL);
if (acceleration < 1)
acceleration = LZ4_ACCELERATION_DEFAULT;
if (acceleration > LZ4_ACCELERATION_MAX)
acceleration = LZ4_ACCELERATION_MAX;
if (maxOutputSize >= LZ4_compressBound(inputSize)) {
if (inputSize < LZ4_64Klimit) {
return LZ4_compress_generic(ctx, source, dest,
inputSize, NULL, 0,
notLimited, byU16, noDict,
noDictIssue, acceleration);
} else {
const tableType_t tableType =
((sizeof(void *) == 4) &&
((uptrval)source > LZ4_DISTANCE_MAX)) ?
byPtr :
byU32;
return LZ4_compress_generic(ctx, source, dest,
inputSize, NULL, 0,
notLimited, tableType,
noDict, noDictIssue,
acceleration);
}
} else {
if (inputSize < LZ4_64Klimit) {
return LZ4_compress_generic(
ctx, source, dest, inputSize, NULL,
maxOutputSize, limitedOutput, byU16, noDict,
noDictIssue, acceleration);
} else {
const tableType_t tableType =
((sizeof(void *) == 4) &&
((uptrval)source > LZ4_DISTANCE_MAX)) ?
byPtr :
byU32;
return LZ4_compress_generic(
ctx, source, dest, inputSize, NULL,
maxOutputSize, limitedOutput, tableType, noDict,
noDictIssue, acceleration);
}
}
}
int LZ4_compress_fast(const char *source, char *dest, int inputSize,
int maxOutputSize, int acceleration, void *wrkmem)
{
return LZ4_compress_fast_extState(wrkmem, source, dest, inputSize,
maxOutputSize, acceleration);
}
EXPORT_SYMBOL(LZ4_compress_fast);
int LZ4_compress_default(const char *source, char *dest, int inputSize,
int maxOutputSize, void *wrkmem)
{
return LZ4_compress_fast(source, dest, inputSize, maxOutputSize,
LZ4_ACCELERATION_DEFAULT, wrkmem);
}
EXPORT_SYMBOL(LZ4_compress_default);
static int LZ4_compress_destSize_extState(LZ4_stream_t *state, const char *src,
char *dst, int *srcSizePtr,
int targetDstSize)
{
void *const s = LZ4_initStream(state, sizeof(*state));
assert(s != NULL);
(void)s;
if (targetDstSize >=
LZ4_compressBound(
*srcSizePtr)) { /* compression success is guaranteed */
return LZ4_compress_fast_extState(state, src, dst, *srcSizePtr,
targetDstSize, 1);
} else {
if (*srcSizePtr < LZ4_64Klimit) {
return LZ4_compress_generic(&state->internal_donotuse,
src, dst, *srcSizePtr,
srcSizePtr, targetDstSize,
fillOutput, byU16, noDict,
noDictIssue, 1);
} else {
tableType_t const addrMode =
((sizeof(void *) == 4) &&
((uptrval)src > LZ4_DISTANCE_MAX)) ?
byPtr :
byU32;
return LZ4_compress_generic(&state->internal_donotuse,
src, dst, *srcSizePtr,
srcSizePtr, targetDstSize,
fillOutput, addrMode,
noDict, noDictIssue, 1);
}
}
}
int LZ4_compress_destSize(const char *src, char *dst, int *srcSizePtr,
int targetDstSize, void *wrkmem)
{
return LZ4_compress_destSize_extState(wrkmem, src, dst, srcSizePtr,
targetDstSize);
}
EXPORT_SYMBOL(LZ4_compress_destSize);
/*-******************************
* Streaming functions
********************************/
static size_t LZ4_stream_t_alignment(void)
{
typedef struct {
char c;
LZ4_stream_t t;
} t_a;
return sizeof(t_a) - sizeof(LZ4_stream_t);
}
static int LZ4_isAligned(const void *ptr, size_t alignment)
{
return ((size_t)ptr & (alignment - 1)) == 0;
}
LZ4_stream_t *LZ4_initStream(void *buffer, size_t size)
{
DEBUGLOG(5, "LZ4_initStream");
if (buffer == NULL) {
return NULL;
}
if (size < sizeof(LZ4_stream_t)) {
return NULL;
}
if (!LZ4_isAligned(buffer, LZ4_stream_t_alignment()))
return NULL;
memset(buffer, 0, sizeof(LZ4_stream_t_internal));
return (LZ4_stream_t *)buffer;
}
void LZ4_resetStream(LZ4_stream_t *LZ4_stream)
{
memset(LZ4_stream, 0, sizeof(LZ4_stream_t_internal));
}
int LZ4_loadDict(LZ4_stream_t *LZ4_dict, const char *dictionary, int dictSize)
{
LZ4_stream_t_internal *dict = &LZ4_dict->internal_donotuse;
const tableType_t tableType = byU32;
const BYTE *p = (const BYTE *)dictionary;
const BYTE *const dictEnd = p + dictSize;
const BYTE *base;
DEBUGLOG(4, "LZ4_loadDict (%i bytes from %p into %p)", dictSize,
dictionary, LZ4_dict);
/* It's necessary to reset the context,
* and not just continue it with prepareTable()
* to avoid any risk of generating overflowing matchIndex
* when compressing using this dictionary */
LZ4_resetStream(LZ4_dict);
/* We always increment the offset by 64 KB, since, if the dict is longer,
* we truncate it to the last 64k, and if it's shorter, we still want to
* advance by a whole window length so we can provide the guarantee that
* there are only valid offsets in the window, which allows an optimization
* in LZ4_compress_fast_continue() where it uses noDictIssue even when the
* dictionary isn't a full 64k. */
dict->currentOffset += 64 * KB;
if (dictSize < (int)HASH_UNIT) {
return 0;
}
if ((dictEnd - p) > 64 * KB)
p = dictEnd - 64 * KB;
base = dictEnd - dict->currentOffset;
dict->dictionary = p;
dict->dictSize = (U32)(dictEnd - p);
dict->tableType = (U32)tableType;
while (p <= dictEnd - HASH_UNIT) {
LZ4_putPosition(p, dict->hashTable, tableType, base);
p += 3;
}
return (int)dict->dictSize;
}
EXPORT_SYMBOL(LZ4_loadDict);
static void LZ4_renormDictT(LZ4_stream_t_internal *LZ4_dict, int nextSize)
{
assert(nextSize >= 0);
if (LZ4_dict->currentOffset + (unsigned)nextSize >
0x80000000) { /* potential ptrdiff_t overflow (32-bits mode) */
/* rescale hash table */
U32 const delta = LZ4_dict->currentOffset - 64 * KB;
const BYTE *dictEnd = LZ4_dict->dictionary + LZ4_dict->dictSize;
int i;
DEBUGLOG(4, "LZ4_renormDictT");
for (i = 0; i < LZ4_HASH_SIZE_U32; i++) {
if (LZ4_dict->hashTable[i] < delta)
LZ4_dict->hashTable[i] = 0;
else
LZ4_dict->hashTable[i] -= delta;
}
LZ4_dict->currentOffset = 64 * KB;
if (LZ4_dict->dictSize > 64 * KB)
LZ4_dict->dictSize = 64 * KB;
LZ4_dict->dictionary = dictEnd - LZ4_dict->dictSize;
}
}
int LZ4_saveDict(LZ4_stream_t *LZ4_dict, char *safeBuffer, int dictSize)
{
LZ4_stream_t_internal *const dict = &LZ4_dict->internal_donotuse;
DEBUGLOG(5, "LZ4_saveDict : dictSize=%i, safeBuffer=%p", dictSize,
safeBuffer);
if ((U32)dictSize > 64 * KB) {
dictSize = 64 * KB;
} /* useless to define a dictionary > 64 KB */
if ((U32)dictSize > dict->dictSize) {
dictSize = (int)dict->dictSize;
}
if (safeBuffer == NULL)
assert(dictSize == 0);
if (dictSize > 0) {
const BYTE *const previousDictEnd =
dict->dictionary + dict->dictSize;
assert(dict->dictionary);
LZ4_memmove(safeBuffer, previousDictEnd - dictSize,
(size_t)dictSize);
}
dict->dictionary = (const BYTE *)safeBuffer;
dict->dictSize = (U32)dictSize;
return dictSize;
}
EXPORT_SYMBOL(LZ4_saveDict);
int LZ4_compress_fast_continue(LZ4_stream_t *LZ4_stream, const char *source,
char *dest, int inputSize, int maxOutputSize,
int acceleration)
{
const tableType_t tableType = byU32;
LZ4_stream_t_internal *const streamPtr = &LZ4_stream->internal_donotuse;
const char *dictEnd = streamPtr->dictSize ?
(const char *)streamPtr->dictionary +
streamPtr->dictSize :
NULL;
DEBUGLOG(5, "LZ4_compress_fast_continue (inputSize=%i, dictSize=%u)",
inputSize, streamPtr->dictSize);
LZ4_renormDictT(streamPtr, inputSize); /* fix index overflow */
if (acceleration < 1)
acceleration = LZ4_ACCELERATION_DEFAULT;
if (acceleration > LZ4_ACCELERATION_MAX)
acceleration = LZ4_ACCELERATION_MAX;
/* invalidate tiny dictionaries */
if ((streamPtr->dictSize <
4) /* tiny dictionary : not enough for a hash */
&& (dictEnd != source) /* prefix mode */
&&
(inputSize >
0) /* tolerance : don't lose history, in case next invocation would use prefix mode */
&& (streamPtr->dictCtx == NULL) /* usingDictCtx */
) {
DEBUGLOG(
5,
"LZ4_compress_fast_continue: dictSize(%u) at addr:%p is too small",
streamPtr->dictSize, streamPtr->dictionary);
/* remove dictionary existence from history, to employ faster prefix mode */
streamPtr->dictSize = 0;
streamPtr->dictionary = (const BYTE *)source;
dictEnd = source;
}
/* Check overlapping input/dictionary space */
{
const char *const sourceEnd = source + inputSize;
if ((sourceEnd > (const char *)streamPtr->dictionary) &&
(sourceEnd < dictEnd)) {
streamPtr->dictSize = (U32)(dictEnd - sourceEnd);
if (streamPtr->dictSize > 64 * KB)
streamPtr->dictSize = 64 * KB;
if (streamPtr->dictSize < 4)
streamPtr->dictSize = 0;
streamPtr->dictionary =
(const BYTE *)dictEnd - streamPtr->dictSize;
}
}
/* prefix mode : source data follows dictionary */
if (dictEnd == source) {
if ((streamPtr->dictSize < 64 * KB) &&
(streamPtr->dictSize < streamPtr->currentOffset))
return LZ4_compress_generic(
streamPtr, source, dest, inputSize, NULL,
maxOutputSize, limitedOutput, tableType,
withPrefix64k, dictSmall, acceleration);
else
return LZ4_compress_generic(
streamPtr, source, dest, inputSize, NULL,
maxOutputSize, limitedOutput, tableType,
withPrefix64k, noDictIssue, acceleration);
}
/* external dictionary mode */
{
int result;
if (streamPtr->dictCtx) {
/* We depend here on the fact that dictCtx'es (produced by
* LZ4_loadDict) guarantee that their tables contain no references
* to offsets between dictCtx->currentOffset - 64 KB and
* dictCtx->currentOffset - dictCtx->dictSize. This makes it safe
* to use noDictIssue even when the dict isn't a full 64 KB.
*/
if (inputSize > 4 * KB) {
/* For compressing large blobs, it is faster to pay the setup
* cost to copy the dictionary's tables into the active context,
* so that the compression loop is only looking into one table.
*/
LZ4_memcpy(streamPtr, streamPtr->dictCtx,
sizeof(*streamPtr));
result = LZ4_compress_generic(
streamPtr, source, dest, inputSize,
NULL, maxOutputSize, limitedOutput,
tableType, usingExtDict, noDictIssue,
acceleration);
} else {
result = LZ4_compress_generic(
streamPtr, source, dest, inputSize,
NULL, maxOutputSize, limitedOutput,
tableType, usingDictCtx, noDictIssue,
acceleration);
}
} else { /* small data <= 4 KB */
if ((streamPtr->dictSize < 64 * KB) &&
(streamPtr->dictSize < streamPtr->currentOffset)) {
result = LZ4_compress_generic(
streamPtr, source, dest, inputSize,
NULL, maxOutputSize, limitedOutput,
tableType, usingExtDict, dictSmall,
acceleration);
} else {
result = LZ4_compress_generic(
streamPtr, source, dest, inputSize,
NULL, maxOutputSize, limitedOutput,
tableType, usingExtDict, noDictIssue,
acceleration);
}
}
streamPtr->dictionary = (const BYTE *)source;
streamPtr->dictSize = (U32)inputSize;
return result;
}
}
EXPORT_SYMBOL(LZ4_compress_fast_continue);
/*-******************************
* For backwards compatibility
********************************/
int lz4_compress(const unsigned char *src, size_t src_len, unsigned char *dst,
size_t *dst_len, void *wrkmem) {
*dst_len = LZ4_compress_default(src, dst, src_len,
LZ4_COMPRESSBOUND(src_len), wrkmem);
/*
* Prior lz4_compress will return -1 in case of error
* and 0 on success
* while new LZ4_compress_fast/default
* returns 0 in case of error
* and the output length on success
*/
if (!*dst_len)
return -1;
else
return 0;
}
EXPORT_SYMBOL(lz4_compress);
MODULE_LICENSE("Dual BSD/GPL");
MODULE_DESCRIPTION("LZ4 compressor");
Reference in a new issue View git blame Copy permalink