diff options
Diffstat (limited to 'linux')
| -rw-r--r-- | linux/blkdev.c | 2 | ||||
| -rw-r--r-- | linux/crypto/api.c | 33 | ||||
| -rw-r--r-- | linux/crypto/chacha20_generic.c | 45 | ||||
| -rw-r--r-- | linux/lz4_compress.c | 1006 | ||||
| -rw-r--r-- | linux/lz4_decompress.c | 656 | ||||
| -rw-r--r-- | linux/lz4defs.h | 347 |
6 files changed, 1526 insertions, 563 deletions
diff --git a/linux/blkdev.c b/linux/blkdev.c index 7fe638f6..70995c8b 100644 --- a/linux/blkdev.c +++ b/linux/blkdev.c @@ -194,6 +194,8 @@ struct block_device *blkdev_get_by_path(const char *path, fmode_t mode, bdev->bd_sync_fd = sync_fd; bdev->bd_holder = holder; bdev->bd_disk = &bdev->__bd_disk; + bdev->bd_bdi = &bdev->__bd_bdi; + bdev->queue.backing_dev_info = bdev->bd_bdi; return bdev; } diff --git a/linux/crypto/api.c b/linux/crypto/api.c index 2d24630e..63efee30 100644 --- a/linux/crypto/api.c +++ b/linux/crypto/api.c @@ -201,3 +201,36 @@ int crypto_register_alg(struct crypto_alg *alg) return 0; } + +/* skcipher: */ + +static int crypto_skcipher_init_tfm(struct crypto_tfm *tfm) +{ + struct crypto_skcipher *skcipher = __crypto_skcipher_cast(tfm); + struct skcipher_alg *alg = crypto_skcipher_alg(skcipher); + + skcipher->setkey = alg->setkey; + skcipher->encrypt = alg->encrypt; + skcipher->decrypt = alg->decrypt; + skcipher->ivsize = alg->ivsize; + skcipher->keysize = alg->max_keysize; + + if (alg->init) + return alg->init(skcipher); + + return 0; +} + +static const struct crypto_type crypto_skcipher_type2 = { + .extsize = crypto_alg_extsize, + .init_tfm = crypto_skcipher_init_tfm, + .maskclear = ~CRYPTO_ALG_TYPE_MASK, + .maskset = CRYPTO_ALG_TYPE_BLKCIPHER_MASK, + .tfmsize = offsetof(struct crypto_skcipher, base), +}; + +struct crypto_skcipher *crypto_alloc_skcipher(const char *alg_name, + u32 type, u32 mask) +{ + return crypto_alloc_tfm(alg_name, &crypto_skcipher_type2, type, mask); +} diff --git a/linux/crypto/chacha20_generic.c b/linux/crypto/chacha20_generic.c index 7ac68321..df4c0e04 100644 --- a/linux/crypto/chacha20_generic.c +++ b/linux/crypto/chacha20_generic.c @@ -18,6 +18,7 @@ #include <linux/crypto.h> #include <crypto/algapi.h> #include <crypto/chacha20.h> +#include <crypto/skcipher.h> #include <sodium/crypto_stream_chacha20.h> @@ -25,10 +26,10 @@ struct chacha20_ctx { u32 key[8]; }; -static int crypto_chacha20_setkey(struct crypto_tfm *tfm, const u8 *key, +static int crypto_chacha20_setkey(struct crypto_skcipher *tfm, const u8 *key, unsigned int keysize) { - struct chacha20_ctx *ctx = crypto_tfm_ctx(tfm); + struct chacha20_ctx *ctx = crypto_skcipher_ctx(tfm); int i; if (keysize != CHACHA20_KEY_SIZE) @@ -40,19 +41,18 @@ static int crypto_chacha20_setkey(struct crypto_tfm *tfm, const u8 *key, return 0; } -static int crypto_chacha20_crypt(struct blkcipher_desc *desc, - struct scatterlist *dst, - struct scatterlist *src, - unsigned nbytes) +static int crypto_chacha20_crypt(struct skcipher_request *req) { - struct chacha20_ctx *ctx = crypto_blkcipher_ctx(desc->tfm); - struct scatterlist *sg = src; + struct crypto_skcipher *tfm = crypto_skcipher_reqtfm(req); + struct chacha20_ctx *ctx = crypto_skcipher_ctx(tfm); + struct scatterlist *sg = req->src; + unsigned nbytes = req->cryptlen; u32 iv[4]; int ret; - BUG_ON(src != dst); + BUG_ON(req->src != req->dst); - memcpy(iv, desc->info, sizeof(iv)); + memcpy(iv, req->iv, sizeof(iv)); while (1) { ret = crypto_stream_chacha20_xor_ic(sg_virt(sg), @@ -78,22 +78,21 @@ static int crypto_chacha20_crypt(struct blkcipher_desc *desc, return 0; } -static struct crypto_alg alg = { - .cra_name = "chacha20", - .cra_flags = CRYPTO_ALG_TYPE_BLKCIPHER, - .cra_type = &crypto_blkcipher_type, - .cra_ctxsize = sizeof(struct chacha20_ctx), - .cra_u = { - .blkcipher = { - .setkey = crypto_chacha20_setkey, - .encrypt = crypto_chacha20_crypt, - .decrypt = crypto_chacha20_crypt, - }, - }, +static struct skcipher_alg alg = { + .base.cra_name = "chacha20", + .base.cra_ctxsize = sizeof(struct chacha20_ctx), + + .min_keysize = CHACHA20_KEY_SIZE, + .max_keysize = CHACHA20_KEY_SIZE, + .ivsize = CHACHA20_IV_SIZE, + .chunksize = CHACHA20_BLOCK_SIZE, + .setkey = crypto_chacha20_setkey, + .encrypt = crypto_chacha20_crypt, + .decrypt = crypto_chacha20_crypt, }; __attribute__((constructor(110))) static int chacha20_generic_mod_init(void) { - return crypto_register_alg(&alg); + return crypto_register_alg(&alg.base); } diff --git a/linux/lz4_compress.c b/linux/lz4_compress.c index 808fe93e..091b57bb 100644 --- a/linux/lz4_compress.c +++ b/linux/lz4_compress.c @@ -1,19 +1,16 @@ /* * LZ4 - Fast LZ compression algorithm - * Copyright (C) 2011-2012, Yann Collet. - * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) - + * 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 + * * 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 @@ -25,200 +22,909 @@ * 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://fastcompression.blogspot.com/p/lz4.html - * - LZ4 source repository : http://code.google.com/p/lz4/ + * - LZ4 homepage : http://www.lz4.org + * - LZ4 source repository : https://github.com/lz4/lz4 * - * Changed for kernel use by: - * Chanho Min <chanho.min@lge.com> + * Changed for kernel usage by: + * Sven Schmidt <4sschmid@informatik.uni-hamburg.de> */ -#include <linux/log2.h> -#include <linux/kernel.h> +/*-************************************ + * Dependencies + **************************************/ #include <linux/lz4.h> -#include <asm/unaligned.h> #include "lz4defs.h" +#include <linux/kernel.h> +#include <asm/unaligned.h> -#define LZ4_HASH_VALUE(p, _table) \ - __HASH_VALUE(p, MEMORY_USAGE - ilog2(sizeof(_table[0]))) +static const int LZ4_minLength = (MFLIMIT + 1); +static const int LZ4_64Klimit = ((64 * KB) + (MFLIMIT - 1)); -struct lz4_hash_table { - const u8 *(*add)(const struct lz4_hash_table, const u8 *); - void *ctx; - const u8 *base; -}; +/*-****************************** + * 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)); +} -#if __SIZEOF_POINTER__ == 4 -static inline const u8 *hash_table_add32(const struct lz4_hash_table hash, - const u8 *ip) +static FORCE_INLINE U32 LZ4_hash5( + U64 sequence, + tableType_t const tableType) { - const u8 **table = hash.ctx; + const U32 hashLog = (tableType == byU16) + ? LZ4_HASHLOG + 1 + : LZ4_HASHLOG; - swap(table[LZ4_HASH_VALUE(ip, table)], ip); - return ip; -} +#if LZ4_LITTLE_ENDIAN + static const U64 prime5bytes = 889523592379ULL; + + return (U32)(((sequence << 24) * prime5bytes) >> (64 - hashLog)); #else -static inline const u8 *hash_table_add32(const struct lz4_hash_table hash, - const u8 *ip) -{ - u32 *table = hash.ctx; - size_t offset = ip - hash.base; + static const U64 prime8bytes = 11400714785074694791ULL; - swap(table[LZ4_HASH_VALUE(ip, table)], offset); - return hash.base + offset; + 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 == byU32) + return LZ4_hash5(LZ4_read_ARCH(p), tableType); #endif -static inline const u8 *hash_table_add16(const struct lz4_hash_table hash, - const u8 *ip) + return LZ4_hash4(LZ4_read32(p), tableType); +} + +static void LZ4_putPositionOnHash( + const BYTE *p, + U32 h, + void *tableBase, + tableType_t const tableType, + const BYTE *srcBase) { - u16 *table = hash.ctx; - size_t offset = ip - hash.base; + 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; - swap(table[LZ4_HASH_VALUE(ip, table)], offset); - return hash.base + offset; + hashTable[h] = (U16)(p - srcBase); + return; + } + } } -static inline const u8 *find_match(const struct lz4_hash_table hash, - const u8 **ip, const u8 *anchor, - const u8 *start, const u8 *mflimit) +static FORCE_INLINE void LZ4_putPosition( + const BYTE *p, + void *tableBase, + tableType_t tableType, + const BYTE *srcBase) { - int findmatchattempts = (1U << SKIPSTRENGTH) + 3; + U32 const h = LZ4_hashPosition(p, tableType); - while (*ip <= mflimit) { - const u8 *ref = hash.add(hash, *ip); + LZ4_putPositionOnHash(p, h, tableBase, tableType, srcBase); +} - if (ref >= *ip - MAX_DISTANCE && A32(ref) == A32(*ip)) { - /* found match: */ - while (*ip > anchor && - ref > start && - unlikely((*ip)[-1] == ref[-1])) { - (*ip)--; - ref--; - } +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 ref; - } + return hashTable[h]; + } + + if (tableType == byU32) { + const U32 * const hashTable = (U32 *) tableBase; - *ip += findmatchattempts++ >> SKIPSTRENGTH; + return hashTable[h] + srcBase; } - return NULL; + { + /* default, to ensure a return */ + const U16 * const hashTable = (U16 *) tableBase; + + return hashTable[h] + srcBase; + } } -static inline int length_len(unsigned length) +static FORCE_INLINE const BYTE *LZ4_getPosition( + const BYTE *p, + void *tableBase, + tableType_t tableType, + const BYTE *srcBase) { - return length / 255 + 1; + U32 const h = LZ4_hashPosition(p, tableType); + + return LZ4_getPositionOnHash(h, tableBase, tableType, srcBase); } + /* - * LZ4_compressCtx : - * ----------------- - * Compress 'isize' bytes from 'source' into an output buffer 'dest' of - * maximum size 'maxOutputSize'. * If it cannot achieve it, compression - * will stop, and result of the function will be zero. - * return : the number of bytes written in buffer 'dest', or 0 if the - * compression fails + * LZ4_compress_generic() : + * inlined, to ensure branches are decided at compilation time */ -static inline int lz4_compressctx(const struct lz4_hash_table hash, - const u8 *src, size_t src_len, - u8 *dst, size_t *dst_len) -{ - const u8 *ip = src, *anchor = ip, *ref; - const u8 *const iend = ip + src_len; - const u8 *const mflimit = iend - MFLIMIT; - const u8 *const matchlimit = iend - LASTLITERALS; - u8 *op = dst, *token; - u8 *const oend = op + *dst_len; - size_t literal_len, match_len, match_offset; - - /* Init */ - memset(hash.ctx, 0, LZ4_MEM_COMPRESS); - hash.add(hash, ip); - - /* Always start with a literal: */ +static FORCE_INLINE int LZ4_compress_generic( + LZ4_stream_t_internal * const dictPtr, + const char * const source, + char * const dest, + const int inputSize, + const int maxOutputSize, + const limitedOutput_directive outputLimited, + const tableType_t tableType, + const dict_directive dict, + const dictIssue_directive dictIssue, + const U32 acceleration) +{ + const BYTE *ip = (const BYTE *) source; + const BYTE *base; + const BYTE *lowLimit; + const BYTE * const lowRefLimit = ip - dictPtr->dictSize; + const BYTE * const dictionary = dictPtr->dictionary; + const BYTE * const dictEnd = dictionary + dictPtr->dictSize; + const size_t dictDelta = dictEnd - (const BYTE *)source; + const BYTE *anchor = (const BYTE *) source; + const BYTE * const iend = ip + inputSize; + const BYTE * const mflimit = iend - MFLIMIT; + const BYTE * const matchlimit = iend - LASTLITERALS; + + BYTE *op = (BYTE *) dest; + BYTE * const olimit = op + maxOutputSize; + + U32 forwardH; + size_t refDelta = 0; + + /* Init conditions */ + if ((U32)inputSize > (U32)LZ4_MAX_INPUT_SIZE) { + /* Unsupported inputSize, too large (or negative) */ + return 0; + } + + switch (dict) { + case noDict: + default: + base = (const BYTE *)source; + lowLimit = (const BYTE *)source; + break; + case withPrefix64k: + base = (const BYTE *)source - dictPtr->currentOffset; + lowLimit = (const BYTE *)source - dictPtr->dictSize; + break; + case usingExtDict: + base = (const BYTE *)source - dictPtr->currentOffset; + lowLimit = (const BYTE *)source; + break; + } + + if ((tableType == byU16) + && (inputSize >= LZ4_64Klimit)) { + /* Size too large (not within 64K limit) */ + return 0; + } + + if (inputSize < LZ4_minLength) { + /* Input too small, no compression (all literals) */ + goto _last_literals; + } + + /* First Byte */ + LZ4_putPosition(ip, dictPtr->hashTable, tableType, base); ip++; + forwardH = LZ4_hashPosition(ip, tableType); + + /* Main Loop */ + for ( ; ; ) { + const BYTE *match; + BYTE *token; + + /* Find a match */ + { + const BYTE *forwardIp = ip; + unsigned int step = 1; + unsigned int searchMatchNb = acceleration << LZ4_SKIPTRIGGER; + + do { + U32 const h = forwardH; + + ip = forwardIp; + forwardIp += step; + step = (searchMatchNb++ >> LZ4_SKIPTRIGGER); + + if (unlikely(forwardIp > mflimit)) + goto _last_literals; + + match = LZ4_getPositionOnHash(h, + dictPtr->hashTable, + tableType, base); + + if (dict == usingExtDict) { + if (match < (const BYTE *)source) { + refDelta = dictDelta; + lowLimit = dictionary; + } else { + refDelta = 0; + lowLimit = (const BYTE *)source; + } } + + forwardH = LZ4_hashPosition(forwardIp, + tableType); + + LZ4_putPositionOnHash(ip, h, dictPtr->hashTable, + tableType, base); + } while (((dictIssue == dictSmall) + ? (match < lowRefLimit) + : 0) + || ((tableType == byU16) + ? 0 + : (match + MAX_DISTANCE < ip)) + || (LZ4_read32(match + refDelta) + != LZ4_read32(ip))); + } - while ((ref = find_match(hash, &ip, anchor, src, mflimit))) { - /* - * We found a match; @ip now points to the match and @ref points - * to the prior part of the input we matched with. Everything up - * to @anchor has been encoded; the range from @anchor to @ip - * didn't match and now has to be encoded as a literal: - */ - literal_len = ip - anchor; - match_offset = ip - ref; - - /* MINMATCH bytes already matched from find_match(): */ - ip += MINMATCH; - ref += MINMATCH; - match_len = common_length(ip, ref, matchlimit); - ip += match_len; - - /* check output limit */ - if (unlikely(op + - 1 + /* token */ - 2 + /* match ofset */ - literal_len + - length_len(literal_len) + - length_len(match_len) + - LASTLITERALS > oend)) - break; + /* Catch up */ + while (((ip > anchor) & (match + refDelta > lowLimit)) + && (unlikely(ip[-1] == match[refDelta - 1]))) { + ip--; + match--; + } + + /* Encode Literals */ + { + unsigned const int litLength = (unsigned int)(ip - anchor); + + token = op++; + + if ((outputLimited) && + /* Check output buffer overflow */ + (unlikely(op + litLength + + (2 + 1 + LASTLITERALS) + + (litLength / 255) > olimit))) + return 0; + + 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_wildCopy(op, anchor, op + litLength); + op += litLength; + } + +_next_match: + /* Encode Offset */ + LZ4_writeLE16(op, (U16)(ip - match)); + op += 2; - token = op++; - *token = encode_length(&op, literal_len) << ML_BITS; - MEMCPY_ADVANCE_CHUNKED(op, anchor, literal_len); - PUT_LE16_ADVANCE(op, match_offset); - *token += encode_length(&op, match_len); + /* Encode MatchLength */ + { + unsigned int matchCode; + + if ((dict == usingExtDict) + && (lowLimit == dictionary)) { + const BYTE *limit; + + match += refDelta; + limit = ip + (dictEnd - match); + + if (limit > matchlimit) + limit = matchlimit; + + matchCode = LZ4_count(ip + MINMATCH, + match + MINMATCH, limit); + + ip += MINMATCH + matchCode; + + if (ip == limit) { + unsigned const int more = LZ4_count(ip, + (const BYTE *)source, + matchlimit); + + matchCode += more; + ip += more; + } + } else { + matchCode = LZ4_count(ip + MINMATCH, + match + MINMATCH, matchlimit); + ip += MINMATCH + matchCode; + } + + if (outputLimited && + /* Check output buffer overflow */ + (unlikely(op + + (1 + LASTLITERALS) + + (matchCode >> 8) > olimit))) + return 0; + + 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); + } anchor = ip; + + /* Test end of chunk */ + if (ip > mflimit) + break; + + /* Fill table */ + LZ4_putPosition(ip - 2, dictPtr->hashTable, tableType, base); + + /* Test next position */ + match = LZ4_getPosition(ip, dictPtr->hashTable, + tableType, base); + + if (dict == usingExtDict) { + if (match < (const BYTE *)source) { + refDelta = dictDelta; + lowLimit = dictionary; + } else { + refDelta = 0; + lowLimit = (const BYTE *)source; + } + } + + LZ4_putPosition(ip, dictPtr->hashTable, tableType, base); + + if (((dictIssue == dictSmall) ? (match >= lowRefLimit) : 1) + && (match + MAX_DISTANCE >= ip) + && (LZ4_read32(match + refDelta) == LZ4_read32(ip))) { + token = op++; + *token = 0; + goto _next_match; + } + + /* Prepare next loop */ + forwardH = LZ4_hashPosition(++ip, tableType); + } + +_last_literals: + /* Encode Last Literals */ + { + size_t const lastRun = (size_t)(iend - anchor); + + if ((outputLimited) && + /* Check output buffer overflow */ + ((op - (BYTE *)dest) + lastRun + 1 + + ((lastRun + 255 - RUN_MASK) / 255) > (U32)maxOutputSize)) + return 0; + + 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); + } + + memcpy(op, anchor, lastRun); + + op += lastRun; + } + + /* End */ + return (int) (((char *)op) - dest); +} + +static int LZ4_compress_fast_extState( + void *state, + const char *source, + char *dest, + int inputSize, + int maxOutputSize, + int acceleration) +{ + LZ4_stream_t_internal *ctx = &((LZ4_stream_t *)state)->internal_donotuse; +#if LZ4_ARCH64 + const tableType_t tableType = byU32; +#else + const tableType_t tableType = byPtr; +#endif + + LZ4_resetStream((LZ4_stream_t *)state); + + if (acceleration < 1) + acceleration = LZ4_ACCELERATION_DEFAULT; + + if (maxOutputSize >= LZ4_COMPRESSBOUND(inputSize)) { + if (inputSize < LZ4_64Klimit) + return LZ4_compress_generic(ctx, source, + dest, inputSize, 0, + noLimit, byU16, noDict, + noDictIssue, acceleration); + else + return LZ4_compress_generic(ctx, source, + dest, inputSize, 0, + noLimit, tableType, noDict, + noDictIssue, acceleration); + } else { + if (inputSize < LZ4_64Klimit) + return LZ4_compress_generic(ctx, source, + dest, inputSize, + maxOutputSize, limitedOutput, byU16, noDict, + noDictIssue, acceleration); + else + return LZ4_compress_generic(ctx, source, + dest, inputSize, + 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); +} + +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); +} + +/*-****************************** + * *_destSize() variant + ********************************/ +static int LZ4_compress_destSize_generic( + LZ4_stream_t_internal * const ctx, + const char * const src, + char * const dst, + int * const srcSizePtr, + const int targetDstSize, + const tableType_t tableType) +{ + const BYTE *ip = (const BYTE *) src; + const BYTE *base = (const BYTE *) src; + const BYTE *lowLimit = (const BYTE *) src; + const BYTE *anchor = ip; + const BYTE * const iend = ip + *srcSizePtr; + const BYTE * const mflimit = iend - MFLIMIT; + const BYTE * const matchlimit = iend - LASTLITERALS; + + BYTE *op = (BYTE *) dst; + BYTE * const oend = op + targetDstSize; + BYTE * const oMaxLit = op + targetDstSize - 2 /* offset */ + - 8 /* because 8 + MINMATCH == MFLIMIT */ - 1 /* token */; + BYTE * const oMaxMatch = op + targetDstSize + - (LASTLITERALS + 1 /* token */); + BYTE * const oMaxSeq = oMaxLit - 1 /* token */; + + U32 forwardH; + + /* Init conditions */ + /* Impossible to store anything */ + if (targetDstSize < 1) + return 0; + /* Unsupported input size, too large (or negative) */ + if ((U32)*srcSizePtr > (U32)LZ4_MAX_INPUT_SIZE) + return 0; + /* Size too large (not within 64K limit) */ + if ((tableType == byU16) && (*srcSizePtr >= LZ4_64Klimit)) + return 0; + /* Input too small, no compression (all literals) */ + if (*srcSizePtr < LZ4_minLength) + goto _last_literals; + + /* First Byte */ + *srcSizePtr = 0; + LZ4_putPosition(ip, ctx->hashTable, tableType, base); + ip++; forwardH = LZ4_hashPosition(ip, tableType); + + /* Main Loop */ + for ( ; ; ) { + const BYTE *match; + BYTE *token; + + /* Find a match */ + { + const BYTE *forwardIp = ip; + unsigned int step = 1; + unsigned int searchMatchNb = 1 << LZ4_SKIPTRIGGER; + + do { + U32 h = forwardH; + + ip = forwardIp; + forwardIp += step; + step = (searchMatchNb++ >> LZ4_SKIPTRIGGER); + + if (unlikely(forwardIp > mflimit)) + goto _last_literals; + + match = LZ4_getPositionOnHash(h, ctx->hashTable, + tableType, base); + forwardH = LZ4_hashPosition(forwardIp, + tableType); + LZ4_putPositionOnHash(ip, h, + ctx->hashTable, tableType, + base); + + } while (((tableType == byU16) + ? 0 + : (match + MAX_DISTANCE < ip)) + || (LZ4_read32(match) != LZ4_read32(ip))); + } + + /* Catch up */ + while ((ip > anchor) + && (match > lowLimit) + && (unlikely(ip[-1] == match[-1]))) { + ip--; + match--; + } + + /* Encode Literal length */ + { + unsigned int litLength = (unsigned int)(ip - anchor); + + token = op++; + if (op + ((litLength + 240) / 255) + + litLength > oMaxLit) { + /* Not enough space for a last match */ + op--; + goto _last_literals; + } + if (litLength >= RUN_MASK) { + unsigned int len = 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_wildCopy(op, anchor, op + litLength); + op += litLength; + } + +_next_match: + /* Encode Offset */ + LZ4_writeLE16(op, (U16)(ip - match)); op += 2; + + /* Encode MatchLength */ + { + size_t matchLength = LZ4_count(ip + MINMATCH, + match + MINMATCH, matchlimit); - /* Encode remaining input as literal: */ - literal_len = iend - anchor; - if (unlikely(op + - 1 + - literal_len + - length_len(literal_len) > oend)) { - /* Return how much would be able to fit: */ - ssize_t remaining = oend - op; - ssize_t encoded = anchor - src; + if (op + ((matchLength + 240)/255) > oMaxMatch) { + /* Match description too long : reduce it */ + matchLength = (15 - 1) + (oMaxMatch - op) * 255; + } + ip += MINMATCH + matchLength; + + if (matchLength >= ML_MASK) { + *token += ML_MASK; + matchLength -= ML_MASK; + while (matchLength >= 255) { + matchLength -= 255; + *op++ = 255; + } + *op++ = (BYTE)matchLength; + } else + *token += (BYTE)(matchLength); + } + + anchor = ip; - remaining -= length_len(remaining) + 1; + /* Test end of block */ + if (ip > mflimit) + break; + if (op > oMaxSeq) + break; - return -max(encoded + remaining, 1L); + /* Fill table */ + LZ4_putPosition(ip - 2, ctx->hashTable, tableType, base); + + /* Test next position */ + match = LZ4_getPosition(ip, ctx->hashTable, tableType, base); + LZ4_putPosition(ip, ctx->hashTable, tableType, base); + + if ((match + MAX_DISTANCE >= ip) + && (LZ4_read32(match) == LZ4_read32(ip))) { + token = op++; *token = 0; + goto _next_match; + } + + /* Prepare next loop */ + forwardH = LZ4_hashPosition(++ip, tableType); } - token = op++; - *token = encode_length(&op, literal_len) << ML_BITS; - MEMCPY_ADVANCE(op, anchor, literal_len); +_last_literals: + /* Encode Last Literals */ + { + size_t lastRunSize = (size_t)(iend - anchor); + + if (op + 1 /* token */ + + ((lastRunSize + 240) / 255) /* litLength */ + + lastRunSize /* literals */ > oend) { + /* adapt lastRunSize to fill 'dst' */ + lastRunSize = (oend - op) - 1; + lastRunSize -= (lastRunSize + 240) / 255; + } + ip = anchor + lastRunSize; + + if (lastRunSize >= RUN_MASK) { + size_t accumulator = lastRunSize - RUN_MASK; + + *op++ = RUN_MASK << ML_BITS; + for (; accumulator >= 255; accumulator -= 255) + *op++ = 255; + *op++ = (BYTE) accumulator; + } else { + *op++ = (BYTE)(lastRunSize<<ML_BITS); + } + memcpy(op, anchor, lastRunSize); + op += lastRunSize; + } /* End */ - BUG_ON(op > oend); - *dst_len = op - dst; - return 0; + *srcSizePtr = (int) (((const char *)ip) - src); + return (int) (((char *)op) - dst); } -__attribute__((flatten)) -int lz4_compress(const unsigned char *src, size_t src_len, - unsigned char *dst, size_t *dst_len, void *wrkmem) +static int LZ4_compress_destSize_extState( + LZ4_stream_t *state, + const char *src, + char *dst, + int *srcSizePtr, + int targetDstSize) { - if (src_len < LZ4_64KLIMIT) { - const struct lz4_hash_table hash = { - .add = hash_table_add16, - .ctx = wrkmem, - .base = src, - }; +#if LZ4_ARCH64 + const tableType_t tableType = byU32; +#else + const tableType_t tableType = byPtr; +#endif - return lz4_compressctx(hash, src, src_len, dst, dst_len); + LZ4_resetStream(state); + + if (targetDstSize >= LZ4_COMPRESSBOUND(*srcSizePtr)) { + /* compression success is guaranteed */ + return LZ4_compress_fast_extState( + state, src, dst, *srcSizePtr, + targetDstSize, 1); } else { - const struct lz4_hash_table hash = { - .add = hash_table_add32, - .ctx = wrkmem, - .base = src, - }; + if (*srcSizePtr < LZ4_64Klimit) + return LZ4_compress_destSize_generic( + &state->internal_donotuse, + src, dst, srcSizePtr, + targetDstSize, byU16); + else + return LZ4_compress_destSize_generic( + &state->internal_donotuse, + src, dst, srcSizePtr, + targetDstSize, tableType); + } +} - return lz4_compressctx(hash, src, src_len, dst, dst_len); + +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); +} + +/*-****************************** + * Streaming functions + ********************************/ +void LZ4_resetStream(LZ4_stream_t *LZ4_stream) +{ + memset(LZ4_stream, 0, sizeof(LZ4_stream_t)); +} + +int LZ4_loadDict(LZ4_stream_t *LZ4_dict, + const char *dictionary, int dictSize) +{ + LZ4_stream_t_internal *dict = &LZ4_dict->internal_donotuse; + const BYTE *p = (const BYTE *)dictionary; + const BYTE * const dictEnd = p + dictSize; + const BYTE *base; + + if ((dict->initCheck) + || (dict->currentOffset > 1 * GB)) { + /* Uninitialized structure, or reuse overflow */ + LZ4_resetStream(LZ4_dict); + } + + if (dictSize < (int)HASH_UNIT) { + dict->dictionary = NULL; + dict->dictSize = 0; + return 0; + } + + if ((dictEnd - p) > 64 * KB) + p = dictEnd - 64 * KB; + dict->currentOffset += 64 * KB; + base = p - dict->currentOffset; + dict->dictionary = p; + dict->dictSize = (U32)(dictEnd - p); + dict->currentOffset += dict->dictSize; + + while (p <= dictEnd - HASH_UNIT) { + LZ4_putPosition(p, dict->hashTable, byU32, base); + p += 3; + } + + return dict->dictSize; +} + +static void LZ4_renormDictT(LZ4_stream_t_internal *LZ4_dict, + const BYTE *src) +{ + if ((LZ4_dict->currentOffset > 0x80000000) || + ((uptrval)LZ4_dict->currentOffset > (uptrval)src)) { + /* address space overflow */ + /* rescale hash table */ + U32 const delta = LZ4_dict->currentOffset - 64 * KB; + const BYTE *dictEnd = LZ4_dict->dictionary + LZ4_dict->dictSize; + int i; + + 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; + const BYTE * const previousDictEnd = dict->dictionary + dict->dictSize; + + if ((U32)dictSize > 64 * KB) { + /* useless to define a dictionary > 64 * KB */ + dictSize = 64 * KB; + } + if ((U32)dictSize > dict->dictSize) + dictSize = dict->dictSize; + + memmove(safeBuffer, previousDictEnd - dictSize, dictSize); + + dict->dictionary = (const BYTE *)safeBuffer; + dict->dictSize = (U32)dictSize; + + return dictSize; +} + +int LZ4_compress_fast_continue(LZ4_stream_t *LZ4_stream, const char *source, + char *dest, int inputSize, int maxOutputSize, int acceleration) +{ + LZ4_stream_t_internal *streamPtr = &LZ4_stream->internal_donotuse; + const BYTE * const dictEnd = streamPtr->dictionary + + streamPtr->dictSize; + + const BYTE *smallest = (const BYTE *) source; + + if (streamPtr->initCheck) { + /* Uninitialized structure detected */ + return 0; + } + + if ((streamPtr->dictSize > 0) && (smallest > dictEnd)) + smallest = dictEnd; + + LZ4_renormDictT(streamPtr, smallest); + + if (acceleration < 1) + acceleration = LZ4_ACCELERATION_DEFAULT; + + /* Check overlapping input/dictionary space */ + { + const BYTE *sourceEnd = (const BYTE *) source + inputSize; + + if ((sourceEnd > 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 = dictEnd - streamPtr->dictSize; + } + } + + /* prefix mode : source data follows dictionary */ + if (dictEnd == (const BYTE *)source) { + int result; + + if ((streamPtr->dictSize < 64 * KB) && + (streamPtr->dictSize < streamPtr->currentOffset)) { + result = LZ4_compress_generic( + streamPtr, source, dest, inputSize, + maxOutputSize, limitedOutput, byU32, + withPrefix64k, dictSmall, acceleration); + } else { + result = LZ4_compress_generic( + streamPtr, source, dest, inputSize, + maxOutputSize, limitedOutput, byU32, + withPrefix64k, noDictIssue, acceleration); + } + streamPtr->dictSize += (U32)inputSize; + streamPtr->currentOffset += (U32)inputSize; + return result; + } + + /* external dictionary mode */ + { + int result; + + if ((streamPtr->dictSize < 64 * KB) && + (streamPtr->dictSize < streamPtr->currentOffset)) { + result = LZ4_compress_generic( + streamPtr, source, dest, inputSize, + maxOutputSize, limitedOutput, byU32, + usingExtDict, dictSmall, acceleration); + } else { + result = LZ4_compress_generic( + streamPtr, source, dest, inputSize, + maxOutputSize, limitedOutput, byU32, + usingExtDict, noDictIssue, acceleration); + } + streamPtr->dictionary = (const BYTE *)source; + streamPtr->dictSize = (U32)inputSize; + streamPtr->currentOffset += (U32)inputSize; + return result; } } diff --git a/linux/lz4_decompress.c b/linux/lz4_decompress.c index 0f3e42dd..5cf910d7 100644 --- a/linux/lz4_decompress.c +++ b/linux/lz4_decompress.c @@ -1,25 +1,16 @@ /* - * LZ4 Decompressor for Linux kernel - * - * Copyright (C) 2013, LG Electronics, Kyungsik Lee <kyungsik.lee@lge.com> - * - * Based on LZ4 implementation by Yann Collet. - * * LZ4 - Fast LZ compression algorithm - * Copyright (C) 2011-2012, Yann Collet. - * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) - * + * 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 + * * 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 @@ -31,286 +22,471 @@ * 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 * - * You can contact the author at : - * - LZ4 homepage : http://fastcompression.blogspot.com/p/lz4.html - * - LZ4 source repository : http://code.google.com/p/lz4/ + * Changed for kernel usage by: + * Sven Schmidt <4sschmid@informatik.uni-hamburg.de> */ -#ifndef STATIC -#include <linux/module.h> -#include <linux/kernel.h> -#endif +/*-************************************ + * Dependencies + **************************************/ #include <linux/lz4.h> - #include "lz4defs.h" - -static const int dec32table[8] = {0, 3, 2, 3, 0, 0, 0, 0}; -#if LZ4_ARCH64 -static const int dec64table[8] = {0, 0, 0, -1, 0, 1, 2, 3}; -#else -static const int dec64table[8] = {0, 0, 0, 0, 0, 0, 0, 0}; -#endif - -static inline size_t get_length(const u8 **ip, size_t length) +#include <linux/kernel.h> +#include <asm/unaligned.h> + +/*-***************************** + * Decompression functions + *******************************/ +/* LZ4_decompress_generic() : + * This generic decompression function cover all use cases. + * It shall be instantiated several times, using different sets of directives + * Note that it is important this generic function is really inlined, + * in order to remove useless branches during compilation optimization. + */ +static FORCE_INLINE int LZ4_decompress_generic( + const char * const source, + char * const dest, + int inputSize, + /* + * If endOnInput == endOnInputSize, + * this value is the max size of Output Buffer. + */ + int outputSize, + /* endOnOutputSize, endOnInputSize */ + int endOnInput, + /* full, partial */ + int partialDecoding, + /* only used if partialDecoding == partial */ + int targetOutputSize, + /* noDict, withPrefix64k, usingExtDict */ + int dict, + /* == dest when no prefix */ + const BYTE * const lowPrefix, + /* only if dict == usingExtDict */ + const BYTE * const dictStart, + /* note : = 0 if noDict */ + const size_t dictSize + ) { - if (length == LENGTH_LONG) { - size_t len; + /* Local Variables */ + const BYTE *ip = (const BYTE *) source; + const BYTE * const iend = ip + inputSize; - do { - length += (len = *(*ip)++); - } while (len == 255); - } + BYTE *op = (BYTE *) dest; + BYTE * const oend = op + outputSize; + BYTE *cpy; + BYTE *oexit = op + targetOutputSize; + const BYTE * const lowLimit = lowPrefix - dictSize; - return length; -} + const BYTE * const dictEnd = (const BYTE *)dictStart + dictSize; + const unsigned int dec32table[] = { 0, 1, 2, 1, 4, 4, 4, 4 }; + const int dec64table[] = { 0, 0, 0, -1, 0, 1, 2, 3 }; -static int lz4_uncompress(const u8 *source, u8 *dest, int osize) -{ - const u8 *ip = source; - const u8 *ref; - u8 *op = dest; - u8 * const oend = op + osize; - u8 *cpy; - unsigned token, offset; - ssize_t length; + const int safeDecode = (endOnInput == endOnInputSize); + const int checkOffset = ((safeDecode) && (dictSize < (int)(64 * KB))); - while (1) { - /* get runlength */ - token = *ip++; - length = get_length(&ip, token >> ML_BITS); + /* Special cases */ + /* targetOutputSize too high => decode everything */ + if ((partialDecoding) && (oexit > oend - MFLIMIT)) + oexit = oend - MFLIMIT; - /* copy literals */ - if (unlikely(op + length > oend - COPYLENGTH)) { - /* - * Error: not enough place for another match - * (min 4) + 5 literals - */ - if (op + length != oend) - goto _output_error; + /* Empty output buffer */ + if ((endOnInput) && (unlikely(outputSize == 0))) + return ((inputSize == 1) && (*ip == 0)) ? 0 : -1; - MEMCPY_ADVANCE(op, ip, length); - break; /* EOF */ - } - MEMCPY_ADVANCE_CHUNKED(op, ip, length); + if ((!endOnInput) && (unlikely(outputSize == 0))) + return (*ip == 0 ? 1 : -1); - /* get match offset */ - offset = GET_LE16_ADVANCE(ip); - ref = op - offset; + /* Main Loop : decode sequences */ + while (1) { + size_t length; + const BYTE *match; + size_t offset; - /* Error: offset create reference outside destination buffer */ - if (unlikely(ref < (u8 *const) dest)) - goto _output_error; + /* get literal length */ + unsigned int const token = *ip++; - /* get match length */ - length = get_length(&ip, token & ML_MASK); - length += MINMATCH; + length = token>>ML_BITS; - /* copy first STEPSIZE bytes of match: */ - if (unlikely(offset < STEPSIZE)) { - MEMCPY_ADVANCE_BYTES(op, ref, 4); - ref -= dec32table[offset]; + if (length == RUN_MASK) { + unsigned int s; - memcpy(op, ref, 4); - op += STEPSIZE - 4; - ref -= dec64table[offset]; - } else { - MEMCPY_ADVANCE(op, ref, STEPSIZE); - } - length -= STEPSIZE; - /* - * Note - length could have been < STEPSIZE; that's ok, length - * will now be negative and we'll just end up rewinding op: - */ + do { + s = *ip++; + length += s; + } while (likely(endOnInput + ? ip < iend - RUN_MASK + : 1) & (s == 255)); - /* copy rest of match: */ - cpy = op + length; - if (cpy > oend - COPYLENGTH) { - /* Error: request to write beyond destination buffer */ - if (cpy > oend || - ref + COPYLENGTH > oend) - goto _output_error; -#if !LZ4_ARCH64 - if (op + COPYLENGTH > oend) + if ((safeDecode) + && unlikely( + (size_t)(op + length) < (size_t)(op))) { + /* overflow detection */ goto _output_error; -#endif - MEMCPY_ADVANCE_CHUNKED_NOFIXUP(op, ref, oend - COPYLENGTH); - /* op could be > cpy here */ - while (op < cpy) - *op++ = *ref++; - op = cpy; - /* - * Check EOF (should never happen, since last 5 bytes - * are supposed to be literals) - */ - if (op == oend) + } + if ((safeDecode) + && unlikely( + (size_t)(ip + length) < (size_t)(ip))) { + /* overflow detection */ goto _output_error; - } else { - MEMCPY_ADVANCE_CHUNKED(op, ref, length); + } } - } - /* end of decoding */ - return ip - source; - /* write overflow error detected */ -_output_error: - return -1; -} + /* copy literals */ + cpy = op + length; + if (((endOnInput) && ((cpy > (partialDecoding ? oexit : oend - MFLIMIT)) + || (ip + length > iend - (2 + 1 + LASTLITERALS)))) + || ((!endOnInput) && (cpy > oend - WILDCOPYLENGTH))) { + if (partialDecoding) { + if (cpy > oend) { + /* + * Error : + * write attempt beyond end of output buffer + */ + goto _output_error; + } + if ((endOnInput) + && (ip + length > iend)) { + /* + * Error : + * read attempt beyond + * end of input buffer + */ + goto _output_error; + } + } else { + if ((!endOnInput) + && (cpy != oend)) { + /* + * Error : + * block decoding must + * stop exactly there + */ + goto _output_error; + } + if ((endOnInput) + && ((ip + length != iend) + || (cpy > oend))) { + /* + * Error : + * input must be consumed + */ + goto _output_error; + } + } + + memcpy(op, ip, length); + ip += length; + op += length; + /* Necessarily EOF, due to parsing restrictions */ + break; + } -static inline ssize_t get_length_safe(const u8 **ip, ssize_t length) -{ - if (length == 15) { - size_t len; + LZ4_wildCopy(op, ip, cpy); + ip += length; + op = cpy; - do { - length += (len = *(*ip)++); - if (unlikely((ssize_t) length < 0)) - return -1; + /* get offset */ + offset = LZ4_readLE16(ip); + ip += 2; + match = op - offset; - length += len; - } while (len == 255); - } + if ((checkOffset) && (unlikely(match < lowLimit))) { + /* Error : offset outside buffers */ + goto _output_error; + } - return length; -} + /* costs ~1%; silence an msan warning when offset == 0 */ + LZ4_write32(op, (U32)offset); -static int lz4_uncompress_unknownoutputsize(const u8 *source, u8 *dest, - int isize, size_t maxoutputsize) -{ - const u8 *ip = source; - const u8 *const iend = ip + isize; - const u8 *ref; - u8 *op = dest; - u8 * const oend = op + maxoutputsize; - u8 *cpy; - unsigned token, offset; - size_t length; - - /* Main Loop */ - while (ip < iend) { - /* get runlength */ - token = *ip++; - length = get_length_safe(&ip, token >> ML_BITS); - if (unlikely((ssize_t) length < 0)) - goto _output_error; + /* get matchlength */ + length = token & ML_MASK; + if (length == ML_MASK) { + unsigned int s; - /* copy literals */ - if ((op + length > oend - COPYLENGTH) || - (ip + length > iend - COPYLENGTH)) { - - if (op + length > oend) - goto _output_error;/* writes beyond buffer */ - - if (ip + length != iend) - goto _output_error;/* - * Error: LZ4 format requires - * to consume all input - * at this stage - */ - MEMCPY_ADVANCE(op, ip, length); - break;/* Necessarily EOF, due to parsing restrictions */ - } - MEMCPY_ADVANCE_CHUNKED(op, ip, length); + do { + s = *ip++; - /* get match offset */ - offset = GET_LE16_ADVANCE(ip); - ref = op - offset; + if ((endOnInput) && (ip > iend - LASTLITERALS)) + goto _output_error; - /* Error: offset create reference outside destination buffer */ - if (ref < (u8 * const) dest) - goto _output_error; + length += s; + } while (s == 255); - /* get match length */ - length = get_length_safe(&ip, token & ML_MASK); - if (unlikely((ssize_t) length < 0)) - goto _output_error; + if ((safeDecode) + && unlikely( + (size_t)(op + length) < (size_t)op)) { + /* overflow detection */ + goto _output_error; + } + } length += MINMATCH; - /* copy first STEPSIZE bytes of match: */ - if (unlikely(offset < STEPSIZE)) { - MEMCPY_ADVANCE_BYTES(op, ref, 4); - ref -= dec32table[offset]; + /* check external dictionary */ + if ((dict == usingExtDict) && (match < lowPrefix)) { + if (unlikely(op + length > oend - LASTLITERALS)) { + /* doesn't respect parsing restriction */ + goto _output_error; + } + + if (length <= (size_t)(lowPrefix - match)) { + /* + * match can be copied as a single segment + * from external dictionary + */ + memmove(op, dictEnd - (lowPrefix - match), + length); + op += length; + } else { + /* + * match encompass external + * dictionary and current block + */ + size_t const copySize = (size_t)(lowPrefix - match); + size_t const restSize = length - copySize; + + memcpy(op, dictEnd - copySize, copySize); + op += copySize; + + if (restSize > (size_t)(op - lowPrefix)) { + /* overlap copy */ + BYTE * const endOfMatch = op + restSize; + const BYTE *copyFrom = lowPrefix; + + while (op < endOfMatch) + *op++ = *copyFrom++; + } else { + memcpy(op, lowPrefix, restSize); + op += restSize; + } + } + + continue; + } + + /* copy match within block */ + cpy = op + length; + + if (unlikely(offset < 8)) { + const int dec64 = dec64table[offset]; - memcpy(op, ref, 4); - op += STEPSIZE - 4; - ref -= dec64table[offset]; + op[0] = match[0]; + op[1] = match[1]; + op[2] = match[2]; + op[3] = match[3]; + match += dec32table[offset]; + memcpy(op + 4, match, 4); + match -= dec64; } else { - MEMCPY_ADVANCE(op, ref, STEPSIZE); + LZ4_copy8(op, match); + match += 8; } - length -= STEPSIZE; - /* copy rest of match: */ - cpy = op + length; - if (cpy > oend - COPYLENGTH) { - /* Error: request to write beyond destination buffer */ - if (cpy > oend || - ref + COPYLENGTH > oend) - goto _output_error; -#if !LZ4_ARCH64 - if (op + COPYLENGTH > oend) + op += 8; + + if (unlikely(cpy > oend - 12)) { + BYTE * const oCopyLimit = oend - (WILDCOPYLENGTH - 1); + + if (cpy > oend - LASTLITERALS) { + /* + * Error : last LASTLITERALS bytes + * must be literals (uncompressed) + */ goto _output_error; -#endif - MEMCPY_ADVANCE_CHUNKED_NOFIXUP(op, ref, oend - COPYLENGTH); + } + + if (op < oCopyLimit) { + LZ4_wildCopy(op, match, oCopyLimit); + match += oCopyLimit - op; + op = oCopyLimit; + } + while (op < cpy) - *op++ = *ref++; - op = cpy; - /* - * Check EOF (should never happen, since last 5 bytes - * are supposed to be literals) - */ - if (op == oend) - goto _output_error; + *op++ = *match++; } else { - MEMCPY_ADVANCE_CHUNKED(op, ref, length); + LZ4_copy8(op, match); + + if (length > 16) + LZ4_wildCopy(op + 8, match + 8, cpy); } + + op = cpy; /* correction */ } + /* end of decoding */ - return op - dest; + if (endOnInput) { + /* Nb of output bytes decoded */ + return (int) (((char *)op) - dest); + } else { + /* Nb of input bytes read */ + return (int) (((const char *)ip) - source); + } - /* write overflow error detected */ + /* Overflow error detected */ _output_error: return -1; } -int lz4_decompress(const unsigned char *src, size_t *src_len, - unsigned char *dest, size_t actual_dest_len) +int LZ4_decompress_safe(const char *source, char *dest, + int compressedSize, int maxDecompressedSize) +{ + return LZ4_decompress_generic(source, dest, compressedSize, + maxDecompressedSize, endOnInputSize, full, 0, + noDict, (BYTE *)dest, NULL, 0); +} + +int LZ4_decompress_safe_partial(const char *source, char *dest, + int compressedSize, int targetOutputSize, int maxDecompressedSize) +{ + return LZ4_decompress_generic(source, dest, compressedSize, + maxDecompressedSize, endOnInputSize, partial, + targetOutputSize, noDict, (BYTE *)dest, NULL, 0); +} + +int LZ4_decompress_fast(const char *source, char *dest, int originalSize) +{ + return LZ4_decompress_generic(source, dest, 0, originalSize, + endOnOutputSize, full, 0, withPrefix64k, + (BYTE *)(dest - 64 * KB), NULL, 64 * KB); +} + +int LZ4_setStreamDecode(LZ4_streamDecode_t *LZ4_streamDecode, + const char *dictionary, int dictSize) +{ + LZ4_streamDecode_t_internal *lz4sd = (LZ4_streamDecode_t_internal *) LZ4_streamDecode; + + lz4sd->prefixSize = (size_t) dictSize; + lz4sd->prefixEnd = (const BYTE *) dictionary + dictSize; + lz4sd->externalDict = NULL; + lz4sd->extDictSize = 0; + return 1; +} + +/* + * *_continue() : + * These decoding functions allow decompression of multiple blocks + * in "streaming" mode. + * Previously decoded blocks must still be available at the memory + * position where they were decoded. + * If it's not possible, save the relevant part of + * decoded data into a safe buffer, + * and indicate where it stands using LZ4_setStreamDecode() + */ +int LZ4_decompress_safe_continue(LZ4_streamDecode_t *LZ4_streamDecode, + const char *source, char *dest, int compressedSize, int maxOutputSize) +{ + LZ4_streamDecode_t_internal *lz4sd = &LZ4_streamDecode->internal_donotuse; + int result; + + if (lz4sd->prefixEnd == (BYTE *)dest) { + result = LZ4_decompress_generic(source, dest, + compressedSize, + maxOutputSize, + endOnInputSize, full, 0, + usingExtDict, lz4sd->prefixEnd - lz4sd->prefixSize, + lz4sd->externalDict, + lz4sd->extDictSize); + + if (result <= 0) + return result; + + lz4sd->prefixSize += result; + lz4sd->prefixEnd += result; + } else { + lz4sd->extDictSize = lz4sd->prefixSize; + lz4sd->externalDict = lz4sd->prefixEnd - lz4sd->extDictSize; + result = LZ4_decompress_generic(source, dest, + compressedSize, maxOutputSize, + endOnInputSize, full, 0, + usingExtDict, (BYTE *)dest, + lz4sd->externalDict, lz4sd->extDictSize); + if (result <= 0) + return result; + lz4sd->prefixSize = result; + lz4sd->prefixEnd = (BYTE *)dest + result; + } + + return result; +} + +int LZ4_decompress_fast_continue(LZ4_streamDecode_t *LZ4_streamDecode, + const char *source, char *dest, int originalSize) { - int ret = -1; - int input_len = 0; + LZ4_streamDecode_t_internal *lz4sd = &LZ4_streamDecode->internal_donotuse; + int result; + + if (lz4sd->prefixEnd == (BYTE *)dest) { + result = LZ4_decompress_generic(source, dest, 0, originalSize, + endOnOutputSize, full, 0, + usingExtDict, + lz4sd->prefixEnd - lz4sd->prefixSize, + lz4sd->externalDict, lz4sd->extDictSize); + + if (result <= 0) + return result; + + lz4sd->prefixSize += originalSize; + lz4sd->prefixEnd += originalSize; + } else { + lz4sd->extDictSize = lz4sd->prefixSize; + lz4sd->externalDict = lz4sd->prefixEnd - lz4sd->extDictSize; + result = LZ4_decompress_generic(source, dest, 0, originalSize, + endOnOutputSize, full, 0, + usingExtDict, (BYTE *)dest, + lz4sd->externalDict, lz4sd->extDictSize); + if (result <= 0) + return result; + lz4sd->prefixSize = originalSize; + lz4sd->prefixEnd = (BYTE *)dest + originalSize; + } - input_len = lz4_uncompress(src, dest, actual_dest_len); - if (input_len < 0) - goto exit_0; - *src_len = input_len; + return result; +} - return 0; -exit_0: - return ret; +/* + * Advanced decoding functions : + * *_usingDict() : + * These decoding functions work the same as "_continue" ones, + * the dictionary must be explicitly provided within parameters + */ +static FORCE_INLINE int LZ4_decompress_usingDict_generic(const char *source, + char *dest, int compressedSize, int maxOutputSize, int safe, + const char *dictStart, int dictSize) +{ + if (dictSize == 0) + return LZ4_decompress_generic(source, dest, + compressedSize, maxOutputSize, safe, full, 0, + noDict, (BYTE *)dest, NULL, 0); + if (dictStart + dictSize == dest) { + if (dictSize >= (int)(64 * KB - 1)) + return LZ4_decompress_generic(source, dest, + compressedSize, maxOutputSize, safe, full, 0, + withPrefix64k, (BYTE *)dest - 64 * KB, NULL, 0); + return LZ4_decompress_generic(source, dest, compressedSize, + maxOutputSize, safe, full, 0, noDict, + (BYTE *)dest - dictSize, NULL, 0); + } + return LZ4_decompress_generic(source, dest, compressedSize, + maxOutputSize, safe, full, 0, usingExtDict, + (BYTE *)dest, (const BYTE *)dictStart, dictSize); } -#ifndef STATIC -EXPORT_SYMBOL(lz4_decompress); -#endif -int lz4_decompress_unknownoutputsize(const unsigned char *src, size_t src_len, - unsigned char *dest, size_t *dest_len) +int LZ4_decompress_safe_usingDict(const char *source, char *dest, + int compressedSize, int maxOutputSize, + const char *dictStart, int dictSize) { - int ret = -1; - int out_len = 0; - - out_len = lz4_uncompress_unknownoutputsize(src, dest, src_len, - *dest_len); - if (out_len < 0) - goto exit_0; - *dest_len = out_len; - - return 0; -exit_0: - return ret; + return LZ4_decompress_usingDict_generic(source, dest, + compressedSize, maxOutputSize, 1, dictStart, dictSize); } -#ifndef STATIC -EXPORT_SYMBOL(lz4_decompress_unknownoutputsize); -MODULE_LICENSE("Dual BSD/GPL"); -MODULE_DESCRIPTION("LZ4 Decompressor"); -#endif +int LZ4_decompress_fast_usingDict(const char *source, char *dest, + int originalSize, const char *dictStart, int dictSize) +{ + return LZ4_decompress_usingDict_generic(source, dest, 0, + originalSize, 0, dictStart, dictSize); +} diff --git a/linux/lz4defs.h b/linux/lz4defs.h index 586b217f..42045272 100644 --- a/linux/lz4defs.h +++ b/linux/lz4defs.h @@ -1,181 +1,228 @@ +#ifndef __LZ4DEFS_H__ +#define __LZ4DEFS_H__ + /* - * lz4defs.h -- architecture specific defines - * - * Copyright (C) 2013, LG Electronics, Kyungsik Lee <kyungsik.lee@lge.com> + * lz4defs.h -- common and architecture specific defines for the kernel usage + + * 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 * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License version 2 as - * published by the Free Software Foundation. + * Changed for kernel usage by: + * Sven Schmidt <4sschmid@informatik.uni-hamburg.de> */ -/* - * Detects 64 bits mode - */ -#if __SIZEOF_POINTER__ == 8 +#include <asm/unaligned.h> +#include <linux/bitops.h> +#include <linux/string.h> /* memset, memcpy */ + +#define FORCE_INLINE __always_inline + +/*-************************************ + * Basic Types + **************************************/ +#include <linux/types.h> + +typedef uint8_t BYTE; +typedef uint16_t U16; +typedef uint32_t U32; +typedef int32_t S32; +typedef uint64_t U64; +typedef uintptr_t uptrval; + +/*-************************************ + * Architecture specifics + **************************************/ +#if defined(CONFIG_64BIT) #define LZ4_ARCH64 1 #else #define LZ4_ARCH64 0 #endif -#include <linux/string.h> -#include <asm/unaligned.h> +#if defined(__LITTLE_ENDIAN) +#define LZ4_LITTLE_ENDIAN 1 +#else +#define LZ4_LITTLE_ENDIAN 0 +#endif -#define A32(_p) get_unaligned((u32 *) (_p)) -#define A16(_p) get_unaligned((u16 *) (_p)) - -#define GET_LE16_ADVANCE(_src) \ -({ \ - u16 _r = get_unaligned_le16(_src); \ - (_src) += 2; \ - _r; \ -}) - -#define PUT_LE16_ADVANCE(_dst, _v) \ -do { \ - put_unaligned_le16((_v), (_dst)); \ - (_dst) += 2; \ -} while (0) - -#define LENGTH_LONG 15 -#define COPYLENGTH 8 -#define ML_BITS 4 -#define ML_MASK ((1U << ML_BITS) - 1) -#define RUN_BITS (8 - ML_BITS) -#define RUN_MASK ((1U << RUN_BITS) - 1) -#define MEMORY_USAGE 14 -#define MINMATCH 4 -#define SKIPSTRENGTH 6 -#define LASTLITERALS 5 -#define MFLIMIT (COPYLENGTH + MINMATCH) -#define MINLENGTH (MFLIMIT + 1) -#define MAXD_LOG 16 -#define MAXD (1 << MAXD_LOG) -#define MAXD_MASK (u32)(MAXD - 1) -#define MAX_DISTANCE (MAXD - 1) -#define HASH_LOG (MAXD_LOG - 1) -#define HASHTABLESIZE (1 << HASH_LOG) -#define MAX_NB_ATTEMPTS 256 -#define OPTIMAL_ML (int)((ML_MASK-1)+MINMATCH) -#define LZ4_64KLIMIT ((1<<16) + (MFLIMIT - 1)) - -#define __HASH_VALUE(p, bits) \ - (((A32(p)) * 2654435761U) >> (32 - (bits))) - -#define HASH_VALUE(p) __HASH_VALUE(p, HASH_LOG) - -#define MEMCPY_ADVANCE(_dst, _src, length) \ -do { \ - typeof(length) _length = (length); \ - memcpy(_dst, _src, _length); \ - _src += _length; \ - _dst += _length; \ -} while (0) - -#define MEMCPY_ADVANCE_BYTES(_dst, _src, _length) \ -do { \ - const u8 *_end = (_src) + (_length); \ - while ((_src) < _end) \ - *_dst++ = *_src++; \ -} while (0) - -#define STEPSIZE __SIZEOF_LONG__ - -#define LZ4_COPYPACKET(_src, _dst) \ -do { \ - MEMCPY_ADVANCE(_dst, _src, STEPSIZE); \ - MEMCPY_ADVANCE(_dst, _src, COPYLENGTH - STEPSIZE);\ -} while (0) +/*-************************************ + * Constants + **************************************/ +#define MINMATCH 4 -/* - * Equivalent to MEMCPY_ADVANCE - except may overrun @_dst and @_src by - * COPYLENGTH: - * - * Note: src and dst may overlap (with src < dst) - we must do the copy in - * STEPSIZE chunks for correctness - * - * Note also: length may be negative - we must not call memcpy if length is - * negative, but still adjust dst and src by length - */ -#define MEMCPY_ADVANCE_CHUNKED(_dst, _src, _length) \ -do { \ - u8 *_end = (_dst) + (_length); \ - while ((_dst) < _end) \ - LZ4_COPYPACKET(_src, _dst); \ - _src -= (_dst) - _end; \ - _dst = _end; \ -} while (0) - -#define MEMCPY_ADVANCE_CHUNKED_NOFIXUP(_dst, _src, _end)\ -do { \ - while ((_dst) < (_end)) \ - LZ4_COPYPACKET((_src), (_dst)); \ -} while (0) - -struct lz4_hashtable { +#define WILDCOPYLENGTH 8 +#define LASTLITERALS 5 +#define MFLIMIT (WILDCOPYLENGTH + MINMATCH) + +/* Increase this value ==> compression run slower on incompressible data */ +#define LZ4_SKIPTRIGGER 6 + +#define HASH_UNIT sizeof(size_t) + +#define KB (1 << 10) +#define MB (1 << 20) +#define GB (1U << 30) + +#define MAXD_LOG 16 +#define MAX_DISTANCE ((1 << MAXD_LOG) - 1) +#define STEPSIZE sizeof(size_t) + +#define ML_BITS 4 +#define ML_MASK ((1U << ML_BITS) - 1) +#define RUN_BITS (8 - ML_BITS) +#define RUN_MASK ((1U << RUN_BITS) - 1) + +/*-************************************ + * Reading and writing into memory + **************************************/ +static FORCE_INLINE U16 LZ4_read16(const void *ptr) +{ + return get_unaligned((const U16 *)ptr); +} + +static FORCE_INLINE U32 LZ4_read32(const void *ptr) +{ + return get_unaligned((const U32 *)ptr); +} + +static FORCE_INLINE size_t LZ4_read_ARCH(const void *ptr) +{ + return get_unaligned((const size_t *)ptr); +} + +static FORCE_INLINE void LZ4_write16(void *memPtr, U16 value) +{ + put_unaligned(value, (U16 *)memPtr); +} + +static FORCE_INLINE void LZ4_write32(void *memPtr, U32 value) +{ + put_unaligned(value, (U32 *)memPtr); +} + +static FORCE_INLINE U16 LZ4_readLE16(const void *memPtr) +{ + return get_unaligned_le16(memPtr); +} + +static FORCE_INLINE void LZ4_writeLE16(void *memPtr, U16 value) +{ + return put_unaligned_le16(value, memPtr); +} + +static FORCE_INLINE void LZ4_copy8(void *dst, const void *src) +{ #if LZ4_ARCH64 - const u8 * const base; - u32 *table; + U64 a = get_unaligned((const U64 *)src); + + put_unaligned(a, (U64 *)dst); #else - const int base; - const u8 *table; -#endif -}; + U32 a = get_unaligned((const U32 *)src); + U32 b = get_unaligned((const U32 *)src + 1); -#if LZ4_ARCH64 -#define HTYPE u32 -#else /* 32-bit */ -#define HTYPE const u8* + put_unaligned(a, (U32 *)dst); + put_unaligned(b, (U32 *)dst + 1); #endif +} -#ifdef __BIG_ENDIAN -#define LZ4_NBCOMMONBYTES(val) (__builtin_clzl(val) >> 3) +/* + * customized variant of memcpy, + * which can overwrite up to 7 bytes beyond dstEnd + */ +static FORCE_INLINE void LZ4_wildCopy(void *dstPtr, + const void *srcPtr, void *dstEnd) +{ + BYTE *d = (BYTE *)dstPtr; + const BYTE *s = (const BYTE *)srcPtr; + BYTE *const e = (BYTE *)dstEnd; + + do { + LZ4_copy8(d, s); + d += 8; + s += 8; + } while (d < e); +} + +static FORCE_INLINE unsigned int LZ4_NbCommonBytes(register size_t val) +{ +#if LZ4_LITTLE_ENDIAN + return __ffs(val) >> 3; #else -#define LZ4_NBCOMMONBYTES(val) (__builtin_ctzl(val) >> 3) + return (BITS_PER_LONG - 1 - __fls(val)) >> 3; #endif +} -static inline unsigned common_length(const u8 *l, const u8 *r, - const u8 *const l_end) +static FORCE_INLINE unsigned int LZ4_count( + const BYTE *pIn, + const BYTE *pMatch, + const BYTE *pInLimit) { - const u8 *l_start = l; + const BYTE *const pStart = pIn; - while (likely(l <= l_end - sizeof(long))) { - unsigned long diff = - get_unaligned((unsigned long *) l) ^ - get_unaligned((unsigned long *) r); + while (likely(pIn < pInLimit - (STEPSIZE - 1))) { + size_t const diff = LZ4_read_ARCH(pMatch) ^ LZ4_read_ARCH(pIn); - if (diff) - return l + LZ4_NBCOMMONBYTES(diff) - l_start; + if (!diff) { + pIn += STEPSIZE; + pMatch += STEPSIZE; + continue; + } - l += sizeof(long); - r += sizeof(long); + pIn += LZ4_NbCommonBytes(diff); + + return (unsigned int)(pIn - pStart); } + #if LZ4_ARCH64 - if (l <= l_end - 4 && A32(r) == A32(l)) { - l += 4; - r += 4; + if ((pIn < (pInLimit - 3)) + && (LZ4_read32(pMatch) == LZ4_read32(pIn))) { + pIn += 4; + pMatch += 4; } #endif - if (l <= l_end - 2 && A16(r) == A16(l)) { - l += 2; - r += 2; - } - if (l <= l_end - 1 && *r == *l) { - l++; - r++; + + if ((pIn < (pInLimit - 1)) + && (LZ4_read16(pMatch) == LZ4_read16(pIn))) { + pIn += 2; + pMatch += 2; } - return l - l_start; -} + if ((pIn < pInLimit) && (*pMatch == *pIn)) + pIn++; -static inline unsigned encode_length(u8 **op, unsigned length) -{ - if (length >= LENGTH_LONG) { - length -= LENGTH_LONG; - - for (; length > 254 ; length -= 255) - *(*op)++ = 255; - *(*op)++ = length; - return LENGTH_LONG; - } else - return length; + return (unsigned int)(pIn - pStart); } + +typedef enum { noLimit = 0, limitedOutput = 1 } limitedOutput_directive; +typedef enum { byPtr, byU32, byU16 } tableType_t; + +typedef enum { noDict = 0, withPrefix64k, usingExtDict } dict_directive; +typedef enum { noDictIssue = 0, dictSmall } dictIssue_directive; + +typedef enum { endOnOutputSize = 0, endOnInputSize = 1 } endCondition_directive; +typedef enum { full = 0, partial = 1 } earlyEnd_directive; + +#endif |