| 1 |
/* |
| 2 |
LZ4 - Fast LZ compression algorithm |
| 3 |
Copyright (C) 2011-2014, Yann Collet. |
| 4 |
BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) |
| 5 |
|
| 6 |
Redistribution and use in source and binary forms, with or without |
| 7 |
modification, are permitted provided that the following conditions are |
| 8 |
met: |
| 9 |
|
| 10 |
* Redistributions of source code must retain the above copyright |
| 11 |
notice, this list of conditions and the following disclaimer. |
| 12 |
* Redistributions in binary form must reproduce the above |
| 13 |
copyright notice, this list of conditions and the following disclaimer |
| 14 |
in the documentation and/or other materials provided with the |
| 15 |
distribution. |
| 16 |
|
| 17 |
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 18 |
"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 19 |
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| 20 |
A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| 21 |
OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| 22 |
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| 23 |
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| 24 |
DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| 25 |
THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| 26 |
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| 27 |
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 28 |
|
| 29 |
You can contact the author at : |
| 30 |
- LZ4 source repository : http://code.google.com/p/lz4/ |
| 31 |
- LZ4 public forum : https://groups.google.com/forum/#!forum/lz4c |
| 32 |
*/ |
| 33 |
|
| 34 |
/************************************** |
| 35 |
Tuning parameters |
| 36 |
**************************************/ |
| 37 |
/* |
| 38 |
* HEAPMODE : |
| 39 |
* Select how default compression functions will allocate memory for their hash table, |
| 40 |
* in memory stack (0:default, fastest), or in memory heap (1:requires memory allocation (malloc)). |
| 41 |
*/ |
| 42 |
#define HEAPMODE 0 |
| 43 |
|
| 44 |
|
| 45 |
/************************************** |
| 46 |
CPU Feature Detection |
| 47 |
**************************************/ |
| 48 |
/* 32 or 64 bits ? */ |
| 49 |
#if (defined(__x86_64__) || defined(_M_X64) || defined(_WIN64) \ |
| 50 |
|| defined(__powerpc64__) || defined(__powerpc64le__) \ |
| 51 |
|| defined(__ppc64__) || defined(__ppc64le__) \ |
| 52 |
|| defined(__PPC64__) || defined(__PPC64LE__) \ |
| 53 |
|| defined(__ia64) || defined(__itanium__) || defined(_M_IA64) ) /* Detects 64 bits mode */ |
| 54 |
# define LZ4_ARCH64 1 |
| 55 |
#else |
| 56 |
# define LZ4_ARCH64 0 |
| 57 |
#endif |
| 58 |
|
| 59 |
/* |
| 60 |
* Little Endian or Big Endian ? |
| 61 |
* Overwrite the #define below if you know your architecture endianess |
| 62 |
*/ |
| 63 |
#include <stdlib.h> /* Apparently required to detect endianess */ |
| 64 |
#if defined (__GLIBC__) |
| 65 |
# include <endian.h> |
| 66 |
# if (__BYTE_ORDER == __BIG_ENDIAN) |
| 67 |
# define LZ4_BIG_ENDIAN 1 |
| 68 |
# endif |
| 69 |
#elif (defined(__BIG_ENDIAN__) || defined(__BIG_ENDIAN) || defined(_BIG_ENDIAN)) && !(defined(__LITTLE_ENDIAN__) || defined(__LITTLE_ENDIAN) || defined(_LITTLE_ENDIAN)) |
| 70 |
# define LZ4_BIG_ENDIAN 1 |
| 71 |
#elif defined(__sparc) || defined(__sparc__) \ |
| 72 |
|| defined(__powerpc__) || defined(__ppc__) || defined(__PPC__) \ |
| 73 |
|| defined(__hpux) || defined(__hppa) \ |
| 74 |
|| defined(_MIPSEB) || defined(__s390__) |
| 75 |
# define LZ4_BIG_ENDIAN 1 |
| 76 |
#else |
| 77 |
/* Little Endian assumed. PDP Endian and other very rare endian format are unsupported. */ |
| 78 |
#endif |
| 79 |
|
| 80 |
/* |
| 81 |
* Unaligned memory access is automatically enabled for "common" CPU, such as x86. |
| 82 |
* For others CPU, such as ARM, the compiler may be more cautious, inserting unnecessary extra code to ensure aligned access property |
| 83 |
* If you know your target CPU supports unaligned memory access, you want to force this option manually to improve performance |
| 84 |
*/ |
| 85 |
#if defined(__ARM_FEATURE_UNALIGNED) |
| 86 |
# define LZ4_FORCE_UNALIGNED_ACCESS 1 |
| 87 |
#endif |
| 88 |
|
| 89 |
/* Define this parameter if your target system or compiler does not support hardware bit count */ |
| 90 |
#if defined(_MSC_VER) && defined(_WIN32_WCE) /* Visual Studio for Windows CE does not support Hardware bit count */ |
| 91 |
# define LZ4_FORCE_SW_BITCOUNT |
| 92 |
#endif |
| 93 |
|
| 94 |
/* |
| 95 |
* BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE : |
| 96 |
* This option may provide a small boost to performance for some big endian cpu, although probably modest. |
| 97 |
* You may set this option to 1 if data will remain within closed environment. |
| 98 |
* This option is useless on Little_Endian CPU (such as x86) |
| 99 |
*/ |
| 100 |
|
| 101 |
/* #define BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE 1 */ |
| 102 |
|
| 103 |
|
| 104 |
/************************************** |
| 105 |
Compiler Options |
| 106 |
**************************************/ |
| 107 |
#if defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */ |
| 108 |
/* "restrict" is a known keyword */ |
| 109 |
#else |
| 110 |
# define restrict /* Disable restrict */ |
| 111 |
#endif |
| 112 |
|
| 113 |
#ifdef _MSC_VER /* Visual Studio */ |
| 114 |
# define FORCE_INLINE static __forceinline |
| 115 |
# include <intrin.h> /* For Visual 2005 */ |
| 116 |
# if LZ4_ARCH64 /* 64-bits */ |
| 117 |
# pragma intrinsic(_BitScanForward64) /* For Visual 2005 */ |
| 118 |
# pragma intrinsic(_BitScanReverse64) /* For Visual 2005 */ |
| 119 |
# else /* 32-bits */ |
| 120 |
# pragma intrinsic(_BitScanForward) /* For Visual 2005 */ |
| 121 |
# pragma intrinsic(_BitScanReverse) /* For Visual 2005 */ |
| 122 |
# endif |
| 123 |
# pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ |
| 124 |
#else |
| 125 |
# ifdef __GNUC__ |
| 126 |
# define FORCE_INLINE static inline __attribute__((always_inline)) |
| 127 |
# else |
| 128 |
# define FORCE_INLINE static inline |
| 129 |
# endif |
| 130 |
#endif |
| 131 |
|
| 132 |
#ifdef _MSC_VER /* Visual Studio */ |
| 133 |
# define lz4_bswap16(x) _byteswap_ushort(x) |
| 134 |
#else |
| 135 |
# define lz4_bswap16(x) ((unsigned short int) ((((x) >> 8) & 0xffu) | (((x) & 0xffu) << 8))) |
| 136 |
#endif |
| 137 |
|
| 138 |
#define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__) |
| 139 |
|
| 140 |
#if (GCC_VERSION >= 302) || (__INTEL_COMPILER >= 800) || defined(__clang__) |
| 141 |
# define expect(expr,value) (__builtin_expect ((expr),(value)) ) |
| 142 |
#else |
| 143 |
# define expect(expr,value) (expr) |
| 144 |
#endif |
| 145 |
|
| 146 |
#define likely(expr) expect((expr) != 0, 1) |
| 147 |
#define unlikely(expr) expect((expr) != 0, 0) |
| 148 |
|
| 149 |
|
| 150 |
/************************************** |
| 151 |
Memory routines |
| 152 |
**************************************/ |
| 153 |
#include <stdlib.h> /* malloc, calloc, free */ |
| 154 |
#define ALLOCATOR(n,s) calloc(n,s) |
| 155 |
#define FREEMEM free |
| 156 |
#include <string.h> /* memset, memcpy */ |
| 157 |
#define MEM_INIT memset |
| 158 |
|
| 159 |
|
| 160 |
/************************************** |
| 161 |
Includes |
| 162 |
**************************************/ |
| 163 |
#include "lz4.h" |
| 164 |
|
| 165 |
|
| 166 |
/************************************** |
| 167 |
Basic Types |
| 168 |
**************************************/ |
| 169 |
#if defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */ |
| 170 |
# include <stdint.h> |
| 171 |
typedef uint8_t BYTE; |
| 172 |
typedef uint16_t U16; |
| 173 |
typedef uint32_t U32; |
| 174 |
typedef int32_t S32; |
| 175 |
typedef uint64_t U64; |
| 176 |
#else |
| 177 |
typedef unsigned char BYTE; |
| 178 |
typedef unsigned short U16; |
| 179 |
typedef unsigned int U32; |
| 180 |
typedef signed int S32; |
| 181 |
typedef unsigned long long U64; |
| 182 |
#endif |
| 183 |
|
| 184 |
#if defined(__GNUC__) && !defined(LZ4_FORCE_UNALIGNED_ACCESS) |
| 185 |
# define _PACKED __attribute__ ((packed)) |
| 186 |
#else |
| 187 |
# define _PACKED |
| 188 |
#endif |
| 189 |
|
| 190 |
#if !defined(LZ4_FORCE_UNALIGNED_ACCESS) && !defined(__GNUC__) |
| 191 |
# if defined(__IBMC__) || defined(__SUNPRO_C) || defined(__SUNPRO_CC) |
| 192 |
# pragma pack(1) |
| 193 |
# else |
| 194 |
# pragma pack(push, 1) |
| 195 |
# endif |
| 196 |
#endif |
| 197 |
|
| 198 |
typedef struct { U16 v; } _PACKED U16_S; |
| 199 |
typedef struct { U32 v; } _PACKED U32_S; |
| 200 |
typedef struct { U64 v; } _PACKED U64_S; |
| 201 |
typedef struct {size_t v;} _PACKED size_t_S; |
| 202 |
|
| 203 |
#if !defined(LZ4_FORCE_UNALIGNED_ACCESS) && !defined(__GNUC__) |
| 204 |
# if defined(__SUNPRO_C) || defined(__SUNPRO_CC) |
| 205 |
# pragma pack(0) |
| 206 |
# else |
| 207 |
# pragma pack(pop) |
| 208 |
# endif |
| 209 |
#endif |
| 210 |
|
| 211 |
#define A16(x) (((U16_S *)(x))->v) |
| 212 |
#define A32(x) (((U32_S *)(x))->v) |
| 213 |
#define A64(x) (((U64_S *)(x))->v) |
| 214 |
#define AARCH(x) (((size_t_S *)(x))->v) |
| 215 |
|
| 216 |
|
| 217 |
/************************************** |
| 218 |
Constants |
| 219 |
**************************************/ |
| 220 |
#define LZ4_HASHLOG (LZ4_MEMORY_USAGE-2) |
| 221 |
#define HASHTABLESIZE (1 << LZ4_MEMORY_USAGE) |
| 222 |
#define HASH_SIZE_U32 (1 << LZ4_HASHLOG) |
| 223 |
|
| 224 |
#define MINMATCH 4 |
| 225 |
|
| 226 |
#define COPYLENGTH 8 |
| 227 |
#define LASTLITERALS 5 |
| 228 |
#define MFLIMIT (COPYLENGTH+MINMATCH) |
| 229 |
static const int LZ4_minLength = (MFLIMIT+1); |
| 230 |
|
| 231 |
#define KB *(1U<<10) |
| 232 |
#define MB *(1U<<20) |
| 233 |
#define GB *(1U<<30) |
| 234 |
|
| 235 |
#define LZ4_64KLIMIT ((64 KB) + (MFLIMIT-1)) |
| 236 |
#define SKIPSTRENGTH 6 /* Increasing this value will make the compression run slower on incompressible data */ |
| 237 |
|
| 238 |
#define MAXD_LOG 16 |
| 239 |
#define MAX_DISTANCE ((1 << MAXD_LOG) - 1) |
| 240 |
|
| 241 |
#define ML_BITS 4 |
| 242 |
#define ML_MASK ((1U<<ML_BITS)-1) |
| 243 |
#define RUN_BITS (8-ML_BITS) |
| 244 |
#define RUN_MASK ((1U<<RUN_BITS)-1) |
| 245 |
|
| 246 |
|
| 247 |
/************************************** |
| 248 |
Structures and local types |
| 249 |
**************************************/ |
| 250 |
typedef struct { |
| 251 |
U32 hashTable[HASH_SIZE_U32]; |
| 252 |
U32 currentOffset; |
| 253 |
U32 initCheck; |
| 254 |
const BYTE* dictionary; |
| 255 |
const BYTE* bufferStart; |
| 256 |
U32 dictSize; |
| 257 |
} LZ4_stream_t_internal; |
| 258 |
|
| 259 |
typedef enum { notLimited = 0, limitedOutput = 1 } limitedOutput_directive; |
| 260 |
typedef enum { byPtr, byU32, byU16 } tableType_t; |
| 261 |
|
| 262 |
typedef enum { noDict = 0, withPrefix64k, usingExtDict } dict_directive; |
| 263 |
typedef enum { noDictIssue = 0, dictSmall } dictIssue_directive; |
| 264 |
|
| 265 |
typedef enum { endOnOutputSize = 0, endOnInputSize = 1 } endCondition_directive; |
| 266 |
typedef enum { full = 0, partial = 1 } earlyEnd_directive; |
| 267 |
|
| 268 |
|
| 269 |
/************************************** |
| 270 |
Architecture-specific macros |
| 271 |
**************************************/ |
| 272 |
#define STEPSIZE sizeof(size_t) |
| 273 |
#define LZ4_COPYSTEP(d,s) { AARCH(d) = AARCH(s); d+=STEPSIZE; s+=STEPSIZE; } |
| 274 |
#define LZ4_COPY8(d,s) { LZ4_COPYSTEP(d,s); if (STEPSIZE<8) LZ4_COPYSTEP(d,s); } |
| 275 |
|
| 276 |
#if (defined(LZ4_BIG_ENDIAN) && !defined(BIG_ENDIAN_NATIVE_BUT_INCOMPATIBLE)) |
| 277 |
# define LZ4_READ_LITTLEENDIAN_16(d,s,p) { U16 v = A16(p); v = lz4_bswap16(v); d = (s) - v; } |
| 278 |
# define LZ4_WRITE_LITTLEENDIAN_16(p,i) { U16 v = (U16)(i); v = lz4_bswap16(v); A16(p) = v; p+=2; } |
| 279 |
#else /* Little Endian */ |
| 280 |
# define LZ4_READ_LITTLEENDIAN_16(d,s,p) { d = (s) - A16(p); } |
| 281 |
# define LZ4_WRITE_LITTLEENDIAN_16(p,v) { A16(p) = v; p+=2; } |
| 282 |
#endif |
| 283 |
|
| 284 |
|
| 285 |
/************************************** |
| 286 |
Macros |
| 287 |
**************************************/ |
| 288 |
#define LZ4_STATIC_ASSERT(c) { enum { LZ4_static_assert = 1/(!!(c)) }; } /* use only *after* variable declarations */ |
| 289 |
#if LZ4_ARCH64 || !defined(__GNUC__) |
| 290 |
# define LZ4_WILDCOPY(d,s,e) { do { LZ4_COPY8(d,s) } while (d<e); } /* at the end, d>=e; */ |
| 291 |
#else |
| 292 |
# define LZ4_WILDCOPY(d,s,e) { if (likely(e-d <= 8)) LZ4_COPY8(d,s) else do { LZ4_COPY8(d,s) } while (d<e); } |
| 293 |
#endif |
| 294 |
|
| 295 |
|
| 296 |
/**************************** |
| 297 |
Private local functions |
| 298 |
****************************/ |
| 299 |
#if LZ4_ARCH64 |
| 300 |
|
| 301 |
int LZ4_NbCommonBytes (register U64 val) |
| 302 |
{ |
| 303 |
# if defined(LZ4_BIG_ENDIAN) |
| 304 |
# if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT) |
| 305 |
unsigned long r = 0; |
| 306 |
_BitScanReverse64( &r, val ); |
| 307 |
return (int)(r>>3); |
| 308 |
# elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT) |
| 309 |
return (__builtin_clzll(val) >> 3); |
| 310 |
# else |
| 311 |
int r; |
| 312 |
if (!(val>>32)) { r=4; } else { r=0; val>>=32; } |
| 313 |
if (!(val>>16)) { r+=2; val>>=8; } else { val>>=24; } |
| 314 |
r += (!val); |
| 315 |
return r; |
| 316 |
# endif |
| 317 |
# else |
| 318 |
# if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT) |
| 319 |
unsigned long r = 0; |
| 320 |
_BitScanForward64( &r, val ); |
| 321 |
return (int)(r>>3); |
| 322 |
# elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT) |
| 323 |
return (__builtin_ctzll(val) >> 3); |
| 324 |
# else |
| 325 |
static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2, 0, 3, 1, 3, 1, 4, 2, 7, 0, 2, 3, 6, 1, 5, 3, 5, 1, 3, 4, 4, 2, 5, 6, 7, 7, 0, 1, 2, 3, 3, 4, 6, 2, 6, 5, 5, 3, 4, 5, 6, 7, 1, 2, 4, 6, 4, 4, 5, 7, 2, 6, 5, 7, 6, 7, 7 }; |
| 326 |
return DeBruijnBytePos[((U64)((val & -(long long)val) * 0x0218A392CDABBD3FULL)) >> 58]; |
| 327 |
# endif |
| 328 |
# endif |
| 329 |
} |
| 330 |
|
| 331 |
#else |
| 332 |
|
| 333 |
int LZ4_NbCommonBytes (register U32 val) |
| 334 |
{ |
| 335 |
# if defined(LZ4_BIG_ENDIAN) |
| 336 |
# if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT) |
| 337 |
unsigned long r = 0; |
| 338 |
_BitScanReverse( &r, val ); |
| 339 |
return (int)(r>>3); |
| 340 |
# elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT) |
| 341 |
return (__builtin_clz(val) >> 3); |
| 342 |
# else |
| 343 |
int r; |
| 344 |
if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; } |
| 345 |
r += (!val); |
| 346 |
return r; |
| 347 |
# endif |
| 348 |
# else |
| 349 |
# if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT) |
| 350 |
unsigned long r; |
| 351 |
_BitScanForward( &r, val ); |
| 352 |
return (int)(r>>3); |
| 353 |
# elif defined(__GNUC__) && (GCC_VERSION >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT) |
| 354 |
return (__builtin_ctz(val) >> 3); |
| 355 |
# else |
| 356 |
static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0, 3, 2, 2, 1, 3, 2, 0, 1, 3, 3, 1, 2, 2, 2, 2, 0, 3, 1, 2, 0, 1, 0, 1, 1 }; |
| 357 |
return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27]; |
| 358 |
# endif |
| 359 |
# endif |
| 360 |
} |
| 361 |
|
| 362 |
#endif |
| 363 |
|
| 364 |
|
| 365 |
/******************************** |
| 366 |
Compression functions |
| 367 |
********************************/ |
| 368 |
int LZ4_compressBound(int isize) { return LZ4_COMPRESSBOUND(isize); } |
| 369 |
|
| 370 |
static int LZ4_hashSequence(U32 sequence, tableType_t tableType) |
| 371 |
{ |
| 372 |
if (tableType == byU16) |
| 373 |
return (((sequence) * 2654435761U) >> ((MINMATCH*8)-(LZ4_HASHLOG+1))); |
| 374 |
else |
| 375 |
return (((sequence) * 2654435761U) >> ((MINMATCH*8)-LZ4_HASHLOG)); |
| 376 |
} |
| 377 |
|
| 378 |
static int LZ4_hashPosition(const BYTE* p, tableType_t tableType) { return LZ4_hashSequence(A32(p), tableType); } |
| 379 |
|
| 380 |
static void LZ4_putPositionOnHash(const BYTE* p, U32 h, void* tableBase, tableType_t tableType, const BYTE* srcBase) |
| 381 |
{ |
| 382 |
switch (tableType) |
| 383 |
{ |
| 384 |
case byPtr: { const BYTE** hashTable = (const BYTE**) tableBase; hashTable[h] = p; break; } |
| 385 |
case byU32: { U32* hashTable = (U32*) tableBase; hashTable[h] = (U32)(p-srcBase); break; } |
| 386 |
case byU16: { U16* hashTable = (U16*) tableBase; hashTable[h] = (U16)(p-srcBase); break; } |
| 387 |
} |
| 388 |
} |
| 389 |
|
| 390 |
static void LZ4_putPosition(const BYTE* p, void* tableBase, tableType_t tableType, const BYTE* srcBase) |
| 391 |
{ |
| 392 |
U32 h = LZ4_hashPosition(p, tableType); |
| 393 |
LZ4_putPositionOnHash(p, h, tableBase, tableType, srcBase); |
| 394 |
} |
| 395 |
|
| 396 |
static const BYTE* LZ4_getPositionOnHash(U32 h, void* tableBase, tableType_t tableType, const BYTE* srcBase) |
| 397 |
{ |
| 398 |
if (tableType == byPtr) { const BYTE** hashTable = (const BYTE**) tableBase; return hashTable[h]; } |
| 399 |
if (tableType == byU32) { U32* hashTable = (U32*) tableBase; return hashTable[h] + srcBase; } |
| 400 |
{ U16* hashTable = (U16*) tableBase; return hashTable[h] + srcBase; } /* default, to ensure a return */ |
| 401 |
} |
| 402 |
|
| 403 |
static const BYTE* LZ4_getPosition(const BYTE* p, void* tableBase, tableType_t tableType, const BYTE* srcBase) |
| 404 |
{ |
| 405 |
U32 h = LZ4_hashPosition(p, tableType); |
| 406 |
return LZ4_getPositionOnHash(h, tableBase, tableType, srcBase); |
| 407 |
} |
| 408 |
|
| 409 |
static unsigned LZ4_count(const BYTE* pIn, const BYTE* pRef, const BYTE* pInLimit) |
| 410 |
{ |
| 411 |
const BYTE* const pStart = pIn; |
| 412 |
|
| 413 |
while (likely(pIn<pInLimit-(STEPSIZE-1))) |
| 414 |
{ |
| 415 |
size_t diff = AARCH(pRef) ^ AARCH(pIn); |
| 416 |
if (!diff) { pIn+=STEPSIZE; pRef+=STEPSIZE; continue; } |
| 417 |
pIn += LZ4_NbCommonBytes(diff); |
| 418 |
return (unsigned)(pIn - pStart); |
| 419 |
} |
| 420 |
if (sizeof(void*)==8) if ((pIn<(pInLimit-3)) && (A32(pRef) == A32(pIn))) { pIn+=4; pRef+=4; } |
| 421 |
if ((pIn<(pInLimit-1)) && (A16(pRef) == A16(pIn))) { pIn+=2; pRef+=2; } |
| 422 |
if ((pIn<pInLimit) && (*pRef == *pIn)) pIn++; |
| 423 |
|
| 424 |
return (unsigned)(pIn - pStart); |
| 425 |
} |
| 426 |
|
| 427 |
|
| 428 |
static int LZ4_compress_generic( |
| 429 |
void* ctx, |
| 430 |
const char* source, |
| 431 |
char* dest, |
| 432 |
int inputSize, |
| 433 |
int maxOutputSize, |
| 434 |
|
| 435 |
limitedOutput_directive outputLimited, |
| 436 |
tableType_t tableType, |
| 437 |
dict_directive dict, |
| 438 |
dictIssue_directive dictIssue) |
| 439 |
{ |
| 440 |
LZ4_stream_t_internal* const dictPtr = (LZ4_stream_t_internal*)ctx; |
| 441 |
|
| 442 |
const BYTE* ip = (const BYTE*) source; |
| 443 |
const BYTE* base; |
| 444 |
const BYTE* lowLimit; |
| 445 |
const BYTE* const lowRefLimit = ip - dictPtr->dictSize; |
| 446 |
const BYTE* const dictionary = dictPtr->dictionary; |
| 447 |
const BYTE* const dictEnd = dictionary + dictPtr->dictSize; |
| 448 |
const size_t dictDelta = dictEnd - (const BYTE*)source; |
| 449 |
const BYTE* anchor = (const BYTE*) source; |
| 450 |
const BYTE* const iend = ip + inputSize; |
| 451 |
const BYTE* const mflimit = iend - MFLIMIT; |
| 452 |
const BYTE* const matchlimit = iend - LASTLITERALS; |
| 453 |
|
| 454 |
BYTE* op = (BYTE*) dest; |
| 455 |
BYTE* const olimit = op + maxOutputSize; |
| 456 |
|
| 457 |
const int skipStrength = SKIPSTRENGTH; |
| 458 |
U32 forwardH; |
| 459 |
size_t refDelta=0; |
| 460 |
|
| 461 |
/* Init conditions */ |
| 462 |
if ((U32)inputSize > (U32)LZ4_MAX_INPUT_SIZE) return 0; /* Unsupported input size, too large (or negative) */ |
| 463 |
switch(dict) |
| 464 |
{ |
| 465 |
case noDict: |
| 466 |
default: |
| 467 |
base = (const BYTE*)source; |
| 468 |
lowLimit = (const BYTE*)source; |
| 469 |
break; |
| 470 |
case withPrefix64k: |
| 471 |
base = (const BYTE*)source - dictPtr->currentOffset; |
| 472 |
lowLimit = (const BYTE*)source - dictPtr->dictSize; |
| 473 |
break; |
| 474 |
case usingExtDict: |
| 475 |
base = (const BYTE*)source - dictPtr->currentOffset; |
| 476 |
lowLimit = (const BYTE*)source; |
| 477 |
break; |
| 478 |
} |
| 479 |
if ((tableType == byU16) && (inputSize>=(int)LZ4_64KLIMIT)) return 0; /* Size too large (not within 64K limit) */ |
| 480 |
if (inputSize<LZ4_minLength) goto _last_literals; /* Input too small, no compression (all literals) */ |
| 481 |
|
| 482 |
/* First Byte */ |
| 483 |
LZ4_putPosition(ip, ctx, tableType, base); |
| 484 |
ip++; forwardH = LZ4_hashPosition(ip, tableType); |
| 485 |
|
| 486 |
/* Main Loop */ |
| 487 |
for ( ; ; ) |
| 488 |
{ |
| 489 |
const BYTE* ref; |
| 490 |
BYTE* token; |
| 491 |
{ |
| 492 |
const BYTE* forwardIp = ip; |
| 493 |
unsigned step=1; |
| 494 |
unsigned searchMatchNb = (1U << skipStrength); |
| 495 |
|
| 496 |
/* Find a match */ |
| 497 |
do { |
| 498 |
U32 h = forwardH; |
| 499 |
ip = forwardIp; |
| 500 |
forwardIp += step; |
| 501 |
step = searchMatchNb++ >> skipStrength; |
| 502 |
//if (step>8) step=8; // required for valid forwardIp ; slows down uncompressible data a bit |
| 503 |
|
| 504 |
if (unlikely(forwardIp > mflimit)) goto _last_literals; |
| 505 |
|
| 506 |
ref = LZ4_getPositionOnHash(h, ctx, tableType, base); |
| 507 |
if (dict==usingExtDict) |
| 508 |
{ |
| 509 |
if (ref<(const BYTE*)source) |
| 510 |
{ |
| 511 |
refDelta = dictDelta; |
| 512 |
lowLimit = dictionary; |
| 513 |
} |
| 514 |
else |
| 515 |
{ |
| 516 |
refDelta = 0; |
| 517 |
lowLimit = (const BYTE*)source; |
| 518 |
} |
| 519 |
} |
| 520 |
forwardH = LZ4_hashPosition(forwardIp, tableType); |
| 521 |
LZ4_putPositionOnHash(ip, h, ctx, tableType, base); |
| 522 |
|
| 523 |
} while ( ((dictIssue==dictSmall) ? (ref < lowRefLimit) : 0) |
| 524 |
|| ((tableType==byU16) ? 0 : (ref + MAX_DISTANCE < ip)) |
| 525 |
|| (A32(ref+refDelta) != A32(ip)) ); |
| 526 |
} |
| 527 |
|
| 528 |
/* Catch up */ |
| 529 |
while ((ip>anchor) && (ref+refDelta > lowLimit) && (unlikely(ip[-1]==ref[refDelta-1]))) { ip--; ref--; } |
| 530 |
|
| 531 |
{ |
| 532 |
/* Encode Literal length */ |
| 533 |
unsigned litLength = (unsigned)(ip - anchor); |
| 534 |
token = op++; |
| 535 |
if ((outputLimited) && (unlikely(op + litLength + (2 + 1 + LASTLITERALS) + (litLength/255) > olimit))) |
| 536 |
return 0; /* Check output limit */ |
| 537 |
if (litLength>=RUN_MASK) |
| 538 |
{ |
| 539 |
int len = (int)litLength-RUN_MASK; |
| 540 |
*token=(RUN_MASK<<ML_BITS); |
| 541 |
for(; len >= 255 ; len-=255) *op++ = 255; |
| 542 |
*op++ = (BYTE)len; |
| 543 |
} |
| 544 |
else *token = (BYTE)(litLength<<ML_BITS); |
| 545 |
|
| 546 |
/* Copy Literals */ |
| 547 |
{ BYTE* end = op+litLength; LZ4_WILDCOPY(op,anchor,end); op=end; } |
| 548 |
} |
| 549 |
|
| 550 |
_next_match: |
| 551 |
/* Encode Offset */ |
| 552 |
LZ4_WRITE_LITTLEENDIAN_16(op, (U16)(ip-ref)); |
| 553 |
|
| 554 |
/* Encode MatchLength */ |
| 555 |
{ |
| 556 |
unsigned matchLength; |
| 557 |
|
| 558 |
if ((dict==usingExtDict) && (lowLimit==dictionary)) |
| 559 |
{ |
| 560 |
const BYTE* limit; |
| 561 |
ref += refDelta; |
| 562 |
limit = ip + (dictEnd-ref); |
| 563 |
if (limit > matchlimit) limit = matchlimit; |
| 564 |
matchLength = LZ4_count(ip+MINMATCH, ref+MINMATCH, limit); |
| 565 |
ip += MINMATCH + matchLength; |
| 566 |
if (ip==limit) |
| 567 |
{ |
| 568 |
unsigned more = LZ4_count(ip, (const BYTE*)source, matchlimit); |
| 569 |
matchLength += more; |
| 570 |
ip += more; |
| 571 |
} |
| 572 |
} |
| 573 |
else |
| 574 |
{ |
| 575 |
matchLength = LZ4_count(ip+MINMATCH, ref+MINMATCH, matchlimit); |
| 576 |
ip += MINMATCH + matchLength; |
| 577 |
} |
| 578 |
|
| 579 |
if (matchLength>=ML_MASK) |
| 580 |
{ |
| 581 |
if ((outputLimited) && (unlikely(op + (1 + LASTLITERALS) + (matchLength>>8) > olimit))) |
| 582 |
return 0; /* Check output limit */ |
| 583 |
*token += ML_MASK; |
| 584 |
matchLength -= ML_MASK; |
| 585 |
for (; matchLength >= 510 ; matchLength-=510) { *op++ = 255; *op++ = 255; } |
| 586 |
if (matchLength >= 255) { matchLength-=255; *op++ = 255; } |
| 587 |
*op++ = (BYTE)matchLength; |
| 588 |
} |
| 589 |
else *token += (BYTE)(matchLength); |
| 590 |
} |
| 591 |
|
| 592 |
anchor = ip; |
| 593 |
|
| 594 |
/* Test end of chunk */ |
| 595 |
if (ip > mflimit) break; |
| 596 |
|
| 597 |
/* Fill table */ |
| 598 |
LZ4_putPosition(ip-2, ctx, tableType, base); |
| 599 |
|
| 600 |
/* Test next position */ |
| 601 |
ref = LZ4_getPosition(ip, ctx, tableType, base); |
| 602 |
if (dict==usingExtDict) |
| 603 |
{ |
| 604 |
if (ref<(const BYTE*)source) |
| 605 |
{ |
| 606 |
refDelta = dictDelta; |
| 607 |
lowLimit = dictionary; |
| 608 |
} |
| 609 |
else |
| 610 |
{ |
| 611 |
refDelta = 0; |
| 612 |
lowLimit = (const BYTE*)source; |
| 613 |
} |
| 614 |
} |
| 615 |
LZ4_putPosition(ip, ctx, tableType, base); |
| 616 |
if ( ((dictIssue==dictSmall) ? (ref>=lowRefLimit) : 1) |
| 617 |
&& (ref+MAX_DISTANCE>=ip) |
| 618 |
&& (A32(ref+refDelta)==A32(ip)) ) |
| 619 |
{ token=op++; *token=0; goto _next_match; } |
| 620 |
|
| 621 |
/* Prepare next loop */ |
| 622 |
forwardH = LZ4_hashPosition(++ip, tableType); |
| 623 |
} |
| 624 |
|
| 625 |
_last_literals: |
| 626 |
/* Encode Last Literals */ |
| 627 |
{ |
| 628 |
int lastRun = (int)(iend - anchor); |
| 629 |
if ((outputLimited) && (((char*)op - dest) + lastRun + 1 + ((lastRun+255-RUN_MASK)/255) > (U32)maxOutputSize)) |
| 630 |
return 0; /* Check output limit */ |
| 631 |
if (lastRun>=(int)RUN_MASK) { *op++=(RUN_MASK<<ML_BITS); lastRun-=RUN_MASK; for(; lastRun >= 255 ; lastRun-=255) *op++ = 255; *op++ = (BYTE) lastRun; } |
| 632 |
else *op++ = (BYTE)(lastRun<<ML_BITS); |
| 633 |
memcpy(op, anchor, iend - anchor); |
| 634 |
op += iend-anchor; |
| 635 |
} |
| 636 |
|
| 637 |
/* End */ |
| 638 |
return (int) (((char*)op)-dest); |
| 639 |
} |
| 640 |
|
| 641 |
|
| 642 |
int LZ4_compress(const char* source, char* dest, int inputSize) |
| 643 |
{ |
| 644 |
#if (HEAPMODE) |
| 645 |
void* ctx = ALLOCATOR(LZ4_STREAMSIZE_U32, 4); /* Aligned on 4-bytes boundaries */ |
| 646 |
#else |
| 647 |
U32 ctx[LZ4_STREAMSIZE_U32] = {0}; /* Ensure data is aligned on 4-bytes boundaries */ |
| 648 |
#endif |
| 649 |
int result; |
| 650 |
|
| 651 |
if (inputSize < (int)LZ4_64KLIMIT) |
| 652 |
result = LZ4_compress_generic((void*)ctx, source, dest, inputSize, 0, notLimited, byU16, noDict, noDictIssue); |
| 653 |
else |
| 654 |
result = LZ4_compress_generic((void*)ctx, source, dest, inputSize, 0, notLimited, (sizeof(void*)==8) ? byU32 : byPtr, noDict, noDictIssue); |
| 655 |
|
| 656 |
#if (HEAPMODE) |
| 657 |
FREEMEM(ctx); |
| 658 |
#endif |
| 659 |
return result; |
| 660 |
} |
| 661 |
|
| 662 |
int LZ4_compress_limitedOutput(const char* source, char* dest, int inputSize, int maxOutputSize) |
| 663 |
{ |
| 664 |
#if (HEAPMODE) |
| 665 |
void* ctx = ALLOCATOR(LZ4_STREAMSIZE_U32, 4); /* Aligned on 4-bytes boundaries */ |
| 666 |
#else |
| 667 |
U32 ctx[LZ4_STREAMSIZE_U32] = {0}; /* Ensure data is aligned on 4-bytes boundaries */ |
| 668 |
#endif |
| 669 |
int result; |
| 670 |
|
| 671 |
if (inputSize < (int)LZ4_64KLIMIT) |
| 672 |
result = LZ4_compress_generic((void*)ctx, source, dest, inputSize, maxOutputSize, limitedOutput, byU16, noDict, noDictIssue); |
| 673 |
else |
| 674 |
result = LZ4_compress_generic((void*)ctx, source, dest, inputSize, maxOutputSize, limitedOutput, (sizeof(void*)==8) ? byU32 : byPtr, noDict, noDictIssue); |
| 675 |
|
| 676 |
#if (HEAPMODE) |
| 677 |
FREEMEM(ctx); |
| 678 |
#endif |
| 679 |
return result; |
| 680 |
} |
| 681 |
|
| 682 |
|
| 683 |
/***************************************** |
| 684 |
Experimental : Streaming functions |
| 685 |
*****************************************/ |
| 686 |
|
| 687 |
void* LZ4_createStream() |
| 688 |
{ |
| 689 |
void* lz4s = ALLOCATOR(4, LZ4_STREAMSIZE_U32); |
| 690 |
MEM_INIT(lz4s, 0, LZ4_STREAMSIZE); |
| 691 |
return lz4s; |
| 692 |
} |
| 693 |
|
| 694 |
int LZ4_free (void* LZ4_stream) |
| 695 |
{ |
| 696 |
FREEMEM(LZ4_stream); |
| 697 |
return (0); |
| 698 |
} |
| 699 |
|
| 700 |
|
| 701 |
int LZ4_loadDict (void* LZ4_dict, const char* dictionary, int dictSize) |
| 702 |
{ |
| 703 |
LZ4_stream_t_internal* dict = (LZ4_stream_t_internal*) LZ4_dict; |
| 704 |
const BYTE* p = (const BYTE*)dictionary; |
| 705 |
const BYTE* const dictEnd = p + dictSize; |
| 706 |
const BYTE* base; |
| 707 |
|
| 708 |
LZ4_STATIC_ASSERT(LZ4_STREAMSIZE >= sizeof(LZ4_stream_t_internal)); /* A compilation error here means LZ4_STREAMSIZE is not large enough */ |
| 709 |
if (dict->initCheck) MEM_INIT(dict, 0, sizeof(LZ4_stream_t_internal)); /* Uninitialized structure detected */ |
| 710 |
|
| 711 |
if (dictSize < MINMATCH) |
| 712 |
{ |
| 713 |
dict->dictionary = NULL; |
| 714 |
dict->dictSize = 0; |
| 715 |
return 1; |
| 716 |
} |
| 717 |
|
| 718 |
if (p <= dictEnd - 64 KB) p = dictEnd - 64 KB; |
| 719 |
base = p - dict->currentOffset; |
| 720 |
dict->dictionary = p; |
| 721 |
dict->dictSize = (U32)(dictEnd - p); |
| 722 |
dict->currentOffset += dict->dictSize; |
| 723 |
|
| 724 |
while (p <= dictEnd-MINMATCH) |
| 725 |
{ |
| 726 |
LZ4_putPosition(p, dict, byU32, base); |
| 727 |
p+=3; |
| 728 |
} |
| 729 |
|
| 730 |
return 1; |
| 731 |
} |
| 732 |
|
| 733 |
|
| 734 |
void LZ4_renormDictT(LZ4_stream_t_internal* LZ4_dict, const BYTE* src) |
| 735 |
{ |
| 736 |
if ((LZ4_dict->currentOffset > 0x80000000) || |
| 737 |
((size_t)LZ4_dict->currentOffset > (size_t)src)) /* address space overflow */ |
| 738 |
{ |
| 739 |
/* rescale hash table */ |
| 740 |
U32 delta = LZ4_dict->currentOffset - 64 KB; |
| 741 |
const BYTE* dictEnd = LZ4_dict->dictionary + LZ4_dict->dictSize; |
| 742 |
int i; |
| 743 |
for (i=0; i<HASH_SIZE_U32; i++) |
| 744 |
{ |
| 745 |
if (LZ4_dict->hashTable[i] < delta) LZ4_dict->hashTable[i]=0; |
| 746 |
else LZ4_dict->hashTable[i] -= delta; |
| 747 |
} |
| 748 |
LZ4_dict->currentOffset = 64 KB; |
| 749 |
if (LZ4_dict->dictSize > 64 KB) LZ4_dict->dictSize = 64 KB; |
| 750 |
LZ4_dict->dictionary = dictEnd - LZ4_dict->dictSize; |
| 751 |
} |
| 752 |
} |
| 753 |
|
| 754 |
|
| 755 |
FORCE_INLINE int LZ4_compress_continue_generic (void* LZ4_stream, const char* source, char* dest, int inputSize, |
| 756 |
int maxOutputSize, limitedOutput_directive limit) |
| 757 |
{ |
| 758 |
LZ4_stream_t_internal* streamPtr = (LZ4_stream_t_internal*)LZ4_stream; |
| 759 |
const BYTE* const dictEnd = streamPtr->dictionary + streamPtr->dictSize; |
| 760 |
|
| 761 |
const BYTE* smallest = (const BYTE*) source; |
| 762 |
if (streamPtr->initCheck) return 0; /* Uninitialized structure detected */ |
| 763 |
if ((streamPtr->dictSize>0) && (smallest>dictEnd)) smallest = dictEnd; |
| 764 |
LZ4_renormDictT(streamPtr, smallest); |
| 765 |
|
| 766 |
/* Check overlapping input/dictionary space */ |
| 767 |
{ |
| 768 |
const BYTE* sourceEnd = (const BYTE*) source + inputSize; |
| 769 |
if ((sourceEnd > streamPtr->dictionary) && (sourceEnd < dictEnd)) |
| 770 |
{ |
| 771 |
streamPtr->dictSize = (U32)(dictEnd - sourceEnd); |
| 772 |
if (streamPtr->dictSize > 64 KB) streamPtr->dictSize = 64 KB; |
| 773 |
if (streamPtr->dictSize < 4) streamPtr->dictSize = 0; |
| 774 |
streamPtr->dictionary = dictEnd - streamPtr->dictSize; |
| 775 |
} |
| 776 |
} |
| 777 |
|
| 778 |
/* prefix mode : source data follows dictionary */ |
| 779 |
if (dictEnd == (const BYTE*)source) |
| 780 |
{ |
| 781 |
int result; |
| 782 |
if ((streamPtr->dictSize < 64 KB) && (streamPtr->dictSize < streamPtr->currentOffset)) |
| 783 |
result = LZ4_compress_generic(LZ4_stream, source, dest, inputSize, maxOutputSize, limit, byU32, withPrefix64k, dictSmall); |
| 784 |
else |
| 785 |
result = LZ4_compress_generic(LZ4_stream, source, dest, inputSize, maxOutputSize, limit, byU32, withPrefix64k, noDictIssue); |
| 786 |
streamPtr->dictSize += (U32)inputSize; |
| 787 |
streamPtr->currentOffset += (U32)inputSize; |
| 788 |
return result; |
| 789 |
} |
| 790 |
|
| 791 |
/* external dictionary mode */ |
| 792 |
{ |
| 793 |
int result; |
| 794 |
if ((streamPtr->dictSize < 64 KB) && (streamPtr->dictSize < streamPtr->currentOffset)) |
| 795 |
result = LZ4_compress_generic(LZ4_stream, source, dest, inputSize, maxOutputSize, limit, byU32, usingExtDict, dictSmall); |
| 796 |
else |
| 797 |
result = LZ4_compress_generic(LZ4_stream, source, dest, inputSize, maxOutputSize, limit, byU32, usingExtDict, noDictIssue); |
| 798 |
streamPtr->dictionary = (const BYTE*)source; |
| 799 |
streamPtr->dictSize = (U32)inputSize; |
| 800 |
streamPtr->currentOffset += (U32)inputSize; |
| 801 |
return result; |
| 802 |
} |
| 803 |
} |
| 804 |
|
| 805 |
|
| 806 |
int LZ4_compress_continue (void* LZ4_stream, const char* source, char* dest, int inputSize) |
| 807 |
{ |
| 808 |
return LZ4_compress_continue_generic(LZ4_stream, source, dest, inputSize, 0, notLimited); |
| 809 |
} |
| 810 |
|
| 811 |
int LZ4_compress_limitedOutput_continue (void* LZ4_stream, const char* source, char* dest, int inputSize, int maxOutputSize) |
| 812 |
{ |
| 813 |
return LZ4_compress_continue_generic(LZ4_stream, source, dest, inputSize, maxOutputSize, limitedOutput); |
| 814 |
} |
| 815 |
|
| 816 |
|
| 817 |
// Hidden debug function, to force separate dictionary mode |
| 818 |
int LZ4_compress_forceExtDict (LZ4_stream_t* LZ4_dict, const char* source, char* dest, int inputSize) |
| 819 |
{ |
| 820 |
LZ4_stream_t_internal* streamPtr = (LZ4_stream_t_internal*)LZ4_dict; |
| 821 |
int result; |
| 822 |
const BYTE* const dictEnd = streamPtr->dictionary + streamPtr->dictSize; |
| 823 |
|
| 824 |
const BYTE* smallest = dictEnd; |
| 825 |
if (smallest > (const BYTE*) source) smallest = (const BYTE*) source; |
| 826 |
LZ4_renormDictT((LZ4_stream_t_internal*)LZ4_dict, smallest); |
| 827 |
|
| 828 |
result = LZ4_compress_generic(LZ4_dict, source, dest, inputSize, 0, notLimited, byU32, usingExtDict, noDictIssue); |
| 829 |
|
| 830 |
streamPtr->dictionary = (const BYTE*)source; |
| 831 |
streamPtr->dictSize = (U32)inputSize; |
| 832 |
streamPtr->currentOffset += (U32)inputSize; |
| 833 |
|
| 834 |
return result; |
| 835 |
} |
| 836 |
|
| 837 |
|
| 838 |
int LZ4_saveDict (void* LZ4_dict, char* safeBuffer, int dictSize) |
| 839 |
{ |
| 840 |
LZ4_stream_t_internal* dict = (LZ4_stream_t_internal*) LZ4_dict; |
| 841 |
const BYTE* previousDictEnd = dict->dictionary + dict->dictSize; |
| 842 |
|
| 843 |
if ((U32)dictSize > 64 KB) dictSize = 64 KB; /* useless to define a dictionary > 64 KB */ |
| 844 |
if ((U32)dictSize > dict->dictSize) dictSize = dict->dictSize; |
| 845 |
|
| 846 |
memcpy(safeBuffer, previousDictEnd - dictSize, dictSize); |
| 847 |
|
| 848 |
dict->dictionary = (const BYTE*)safeBuffer; |
| 849 |
dict->dictSize = (U32)dictSize; |
| 850 |
|
| 851 |
return 1; |
| 852 |
} |
| 853 |
|
| 854 |
|
| 855 |
|
| 856 |
/**************************** |
| 857 |
Decompression functions |
| 858 |
****************************/ |
| 859 |
/* |
| 860 |
* This generic decompression function cover all use cases. |
| 861 |
* It shall be instanciated several times, using different sets of directives |
| 862 |
* Note that it is essential this generic function is really inlined, |
| 863 |
* in order to remove useless branches during compilation optimisation. |
| 864 |
*/ |
| 865 |
FORCE_INLINE int LZ4_decompress_generic( |
| 866 |
const char* source, |
| 867 |
char* dest, |
| 868 |
int inputSize, |
| 869 |
int outputSize, /* If endOnInput==endOnInputSize, this value is the max size of Output Buffer. */ |
| 870 |
|
| 871 |
int endOnInput, /* endOnOutputSize, endOnInputSize */ |
| 872 |
int partialDecoding, /* full, partial */ |
| 873 |
int targetOutputSize, /* only used if partialDecoding==partial */ |
| 874 |
int dict, /* noDict, withPrefix64k, usingExtDict */ |
| 875 |
const char* dictStart, /* only if dict==usingExtDict */ |
| 876 |
int dictSize /* note : = 0 if noDict */ |
| 877 |
) |
| 878 |
{ |
| 879 |
/* Local Variables */ |
| 880 |
const BYTE* restrict ip = (const BYTE*) source; |
| 881 |
const BYTE* ref; |
| 882 |
const BYTE* const iend = ip + inputSize; |
| 883 |
|
| 884 |
BYTE* op = (BYTE*) dest; |
| 885 |
BYTE* const oend = op + outputSize; |
| 886 |
BYTE* cpy; |
| 887 |
BYTE* oexit = op + targetOutputSize; |
| 888 |
const BYTE* const lowLimit = (const BYTE*)dest - dictSize; |
| 889 |
|
| 890 |
const BYTE* const dictEnd = (const BYTE*)dictStart + dictSize; |
| 891 |
//#define OLD |
| 892 |
#ifdef OLD |
| 893 |
const size_t dec32table[] = {0, 3, 2, 3, 0, 0, 0, 0}; /* static reduces speed for LZ4_decompress_safe() on GCC64 */ |
| 894 |
#else |
| 895 |
const size_t dec32table[] = {4-0, 4-3, 4-2, 4-3, 4-0, 4-0, 4-0, 4-0}; /* static reduces speed for LZ4_decompress_safe() on GCC64 */ |
| 896 |
#endif |
| 897 |
static const size_t dec64table[] = {0, 0, 0, (size_t)-1, 0, 1, 2, 3}; |
| 898 |
|
| 899 |
const int checkOffset = (endOnInput) && (dictSize < (int)(64 KB)); |
| 900 |
|
| 901 |
|
| 902 |
/* Special cases */ |
| 903 |
if ((partialDecoding) && (oexit> oend-MFLIMIT)) oexit = oend-MFLIMIT; /* targetOutputSize too high => decode everything */ |
| 904 |
if ((endOnInput) && (unlikely(outputSize==0))) return ((inputSize==1) && (*ip==0)) ? 0 : -1; /* Empty output buffer */ |
| 905 |
if ((!endOnInput) && (unlikely(outputSize==0))) return (*ip==0?1:-1); |
| 906 |
|
| 907 |
|
| 908 |
/* Main Loop */ |
| 909 |
while (1) |
| 910 |
{ |
| 911 |
unsigned token; |
| 912 |
size_t length; |
| 913 |
|
| 914 |
/* get runlength */ |
| 915 |
token = *ip++; |
| 916 |
if ((length=(token>>ML_BITS)) == RUN_MASK) |
| 917 |
{ |
| 918 |
unsigned s; |
| 919 |
do |
| 920 |
{ |
| 921 |
s = *ip++; |
| 922 |
length += s; |
| 923 |
} |
| 924 |
while (likely((endOnInput)?ip<iend-RUN_MASK:1) && (s==255)); |
| 925 |
//if ((sizeof(void*)==4) && unlikely(length>LZ4_MAX_INPUT_SIZE)) goto _output_error; /* overflow detection */ |
| 926 |
if ((sizeof(void*)==4) && unlikely((size_t)(op+length)<(size_t)(op))) goto _output_error; /* quickfix issue 134 */ |
| 927 |
if ((endOnInput) && (sizeof(void*)==4) && unlikely((size_t)(ip+length)<(size_t)(ip))) goto _output_error; /* quickfix issue 134 */ |
| 928 |
} |
| 929 |
|
| 930 |
/* copy literals */ |
| 931 |
cpy = op+length; |
| 932 |
if (((endOnInput) && ((cpy>(partialDecoding?oexit:oend-MFLIMIT)) || (ip+length>iend-(2+1+LASTLITERALS))) ) |
| 933 |
|| ((!endOnInput) && (cpy>oend-COPYLENGTH))) |
| 934 |
{ |
| 935 |
if (partialDecoding) |
| 936 |
{ |
| 937 |
if (cpy > oend) goto _output_error; /* Error : write attempt beyond end of output buffer */ |
| 938 |
if ((endOnInput) && (ip+length > iend)) goto _output_error; /* Error : read attempt beyond end of input buffer */ |
| 939 |
} |
| 940 |
else |
| 941 |
{ |
| 942 |
if ((!endOnInput) && (cpy != oend)) goto _output_error; /* Error : block decoding must stop exactly there */ |
| 943 |
if ((endOnInput) && ((ip+length != iend) || (cpy > oend))) goto _output_error; /* Error : input must be consumed */ |
| 944 |
} |
| 945 |
memcpy(op, ip, length); |
| 946 |
ip += length; |
| 947 |
op += length; |
| 948 |
break; /* Necessarily EOF, due to parsing restrictions */ |
| 949 |
} |
| 950 |
LZ4_WILDCOPY(op, ip, cpy); ip -= (op-cpy); op = cpy; |
| 951 |
|
| 952 |
/* get offset */ |
| 953 |
LZ4_READ_LITTLEENDIAN_16(ref,cpy,ip); ip+=2; |
| 954 |
if ((checkOffset) && (unlikely(ref < lowLimit))) goto _output_error; /* Error : offset outside destination buffer */ |
| 955 |
|
| 956 |
/* get matchlength */ |
| 957 |
if ((length=(token&ML_MASK)) == ML_MASK) |
| 958 |
{ |
| 959 |
unsigned s; |
| 960 |
do |
| 961 |
{ |
| 962 |
if ((endOnInput) && (ip > iend-LASTLITERALS)) goto _output_error; |
| 963 |
s = *ip++; |
| 964 |
length += s; |
| 965 |
} while (s==255); |
| 966 |
//if ((sizeof(void*)==4) && unlikely(length>LZ4_MAX_INPUT_SIZE)) goto _output_error; /* overflow detection */ |
| 967 |
if ((sizeof(void*)==4) && unlikely((size_t)(op+length)<(size_t)op)) goto _output_error; /* quickfix issue 134 */ |
| 968 |
} |
| 969 |
|
| 970 |
/* check external dictionary */ |
| 971 |
if ((dict==usingExtDict) && (ref < (BYTE* const)dest)) |
| 972 |
{ |
| 973 |
if (unlikely(op+length+MINMATCH > oend-LASTLITERALS)) goto _output_error; |
| 974 |
|
| 975 |
if (length+MINMATCH <= (size_t)(dest-(char*)ref)) |
| 976 |
{ |
| 977 |
ref = dictEnd - (dest-(char*)ref); |
| 978 |
memcpy(op, ref, length+MINMATCH); |
| 979 |
op += length+MINMATCH; |
| 980 |
} |
| 981 |
else |
| 982 |
{ |
| 983 |
size_t copySize = (size_t)(dest-(char*)ref); |
| 984 |
memcpy(op, dictEnd - copySize, copySize); |
| 985 |
op += copySize; |
| 986 |
copySize = length+MINMATCH - copySize; |
| 987 |
if (copySize > (size_t)((char*)op-dest)) /* overlap */ |
| 988 |
{ |
| 989 |
BYTE* const cpy = op + copySize; |
| 990 |
const BYTE* ref = (BYTE*)dest; |
| 991 |
while (op < cpy) *op++ = *ref++; |
| 992 |
} |
| 993 |
else |
| 994 |
{ |
| 995 |
memcpy(op, dest, copySize); |
| 996 |
op += copySize; |
| 997 |
} |
| 998 |
} |
| 999 |
continue; |
| 1000 |
} |
| 1001 |
|
| 1002 |
/* copy repeated sequence */ |
| 1003 |
if (unlikely((op-ref)<(int)STEPSIZE)) |
| 1004 |
{ |
| 1005 |
const size_t dec64 = dec64table[(sizeof(void*)==4) ? 0 : op-ref]; |
| 1006 |
op[0] = ref[0]; |
| 1007 |
op[1] = ref[1]; |
| 1008 |
op[2] = ref[2]; |
| 1009 |
op[3] = ref[3]; |
| 1010 |
#ifdef OLD |
| 1011 |
op += 4, ref += 4; ref -= dec32table[op-ref]; |
| 1012 |
A32(op) = A32(ref); |
| 1013 |
op += STEPSIZE-4; ref -= dec64; |
| 1014 |
#else |
| 1015 |
ref += dec32table[op-ref]; |
| 1016 |
A32(op+4) = A32(ref); |
| 1017 |
op += STEPSIZE; ref -= dec64; |
| 1018 |
#endif |
| 1019 |
} else { LZ4_COPYSTEP(op,ref); } |
| 1020 |
cpy = op + length - (STEPSIZE-4); |
| 1021 |
|
| 1022 |
if (unlikely(cpy>oend-COPYLENGTH-(STEPSIZE-4))) |
| 1023 |
{ |
| 1024 |
if (cpy > oend-LASTLITERALS) goto _output_error; /* Error : last 5 bytes must be literals */ |
| 1025 |
if (op<oend-COPYLENGTH) LZ4_WILDCOPY(op, ref, (oend-COPYLENGTH)); |
| 1026 |
while(op<cpy) *op++=*ref++; |
| 1027 |
op=cpy; |
| 1028 |
continue; |
| 1029 |
} |
| 1030 |
LZ4_WILDCOPY(op, ref, cpy); |
| 1031 |
op=cpy; /* correction */ |
| 1032 |
} |
| 1033 |
|
| 1034 |
/* end of decoding */ |
| 1035 |
if (endOnInput) |
| 1036 |
return (int) (((char*)op)-dest); /* Nb of output bytes decoded */ |
| 1037 |
else |
| 1038 |
return (int) (((char*)ip)-source); /* Nb of input bytes read */ |
| 1039 |
|
| 1040 |
/* Overflow error detected */ |
| 1041 |
_output_error: |
| 1042 |
return (int) (-(((char*)ip)-source))-1; |
| 1043 |
} |
| 1044 |
|
| 1045 |
|
| 1046 |
int LZ4_decompress_safe(const char* source, char* dest, int compressedSize, int maxOutputSize) |
| 1047 |
{ |
| 1048 |
return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, endOnInputSize, full, 0, noDict, NULL, 0); |
| 1049 |
} |
| 1050 |
|
| 1051 |
int LZ4_decompress_safe_partial(const char* source, char* dest, int compressedSize, int targetOutputSize, int maxOutputSize) |
| 1052 |
{ |
| 1053 |
return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, endOnInputSize, partial, targetOutputSize, noDict, NULL, 0); |
| 1054 |
} |
| 1055 |
|
| 1056 |
int LZ4_decompress_fast(const char* source, char* dest, int originalSize) |
| 1057 |
{ |
| 1058 |
return LZ4_decompress_generic(source, dest, 0, originalSize, endOnOutputSize, full, 0, withPrefix64k, NULL, 0); |
| 1059 |
} |
| 1060 |
|
| 1061 |
/* streaming decompression functions */ |
| 1062 |
|
| 1063 |
//#define LZ4_STREAMDECODESIZE_U32 4 |
| 1064 |
//#define LZ4_STREAMDECODESIZE (LZ4_STREAMDECODESIZE_U32 * sizeof(unsigned int)) |
| 1065 |
//typedef struct { unsigned int table[LZ4_STREAMDECODESIZE_U32]; } LZ4_streamDecode_t; |
| 1066 |
typedef struct |
| 1067 |
{ |
| 1068 |
const char* dictionary; |
| 1069 |
int dictSize; |
| 1070 |
} LZ4_streamDecode_t_internal; |
| 1071 |
|
| 1072 |
/* |
| 1073 |
* If you prefer dynamic allocation methods, |
| 1074 |
* LZ4_createStreamDecode() |
| 1075 |
* provides a pointer (void*) towards an initialized LZ4_streamDecode_t structure. |
| 1076 |
*/ |
| 1077 |
void* LZ4_createStreamDecode() |
| 1078 |
{ |
| 1079 |
void* lz4s = ALLOCATOR(sizeof(U32), LZ4_STREAMDECODESIZE_U32); |
| 1080 |
MEM_INIT(lz4s, 0, LZ4_STREAMDECODESIZE); |
| 1081 |
return lz4s; |
| 1082 |
} |
| 1083 |
|
| 1084 |
/* |
| 1085 |
* LZ4_setDictDecode |
| 1086 |
* Use this function to instruct where to find the dictionary |
| 1087 |
* This function is not necessary if previous data is still available where it was decoded. |
| 1088 |
* Loading a size of 0 is allowed (same effect as no dictionary). |
| 1089 |
* Return : 1 if OK, 0 if error |
| 1090 |
*/ |
| 1091 |
int LZ4_setDictDecode (void* LZ4_streamDecode, const char* dictionary, int dictSize) |
| 1092 |
{ |
| 1093 |
LZ4_streamDecode_t_internal* lz4sd = (LZ4_streamDecode_t_internal*) LZ4_streamDecode; |
| 1094 |
lz4sd->dictionary = dictionary; |
| 1095 |
lz4sd->dictSize = dictSize; |
| 1096 |
return 1; |
| 1097 |
} |
| 1098 |
|
| 1099 |
/* |
| 1100 |
*_continue() : |
| 1101 |
These decoding functions allow decompression of multiple blocks in "streaming" mode. |
| 1102 |
Previously decoded blocks must still be available at the memory position where they were decoded. |
| 1103 |
If it's not possible, save the relevant part of decoded data into a safe buffer, |
| 1104 |
and indicate where it stands using LZ4_setDictDecode() |
| 1105 |
*/ |
| 1106 |
int LZ4_decompress_safe_continue (void* LZ4_streamDecode, const char* source, char* dest, int compressedSize, int maxOutputSize) |
| 1107 |
{ |
| 1108 |
LZ4_streamDecode_t_internal* lz4sd = (LZ4_streamDecode_t_internal*) LZ4_streamDecode; |
| 1109 |
int result; |
| 1110 |
|
| 1111 |
result = LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, endOnInputSize, full, 0, usingExtDict, lz4sd->dictionary, lz4sd->dictSize); |
| 1112 |
if (result <= 0) return result; |
| 1113 |
if (lz4sd->dictionary + lz4sd->dictSize == dest) |
| 1114 |
{ |
| 1115 |
lz4sd->dictSize += result; |
| 1116 |
} |
| 1117 |
else |
| 1118 |
{ |
| 1119 |
lz4sd->dictionary = dest; |
| 1120 |
lz4sd->dictSize = result; |
| 1121 |
} |
| 1122 |
|
| 1123 |
return result; |
| 1124 |
} |
| 1125 |
|
| 1126 |
int LZ4_decompress_fast_continue (void* LZ4_streamDecode, const char* source, char* dest, int originalSize) |
| 1127 |
{ |
| 1128 |
LZ4_streamDecode_t_internal* lz4sd = (LZ4_streamDecode_t_internal*) LZ4_streamDecode; |
| 1129 |
int result; |
| 1130 |
|
| 1131 |
result = LZ4_decompress_generic(source, dest, 0, originalSize, endOnOutputSize, full, 0, usingExtDict, lz4sd->dictionary, lz4sd->dictSize); |
| 1132 |
if (result <= 0) return result; |
| 1133 |
if (lz4sd->dictionary + lz4sd->dictSize == dest) |
| 1134 |
{ |
| 1135 |
lz4sd->dictSize += result; |
| 1136 |
} |
| 1137 |
else |
| 1138 |
{ |
| 1139 |
lz4sd->dictionary = dest; |
| 1140 |
lz4sd->dictSize = result; |
| 1141 |
} |
| 1142 |
|
| 1143 |
return result; |
| 1144 |
} |
| 1145 |
|
| 1146 |
|
| 1147 |
/* |
| 1148 |
Advanced decoding functions : |
| 1149 |
*_usingDict() : |
| 1150 |
These decoding functions work the same as "_continue" ones, |
| 1151 |
the dictionary must be explicitly provided within parameters |
| 1152 |
*/ |
| 1153 |
|
| 1154 |
int LZ4_decompress_safe_usingDict(const char* source, char* dest, int compressedSize, int maxOutputSize, const char* dictStart, int dictSize) |
| 1155 |
{ |
| 1156 |
return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, endOnInputSize, full, 0, usingExtDict, dictStart, dictSize); |
| 1157 |
} |
| 1158 |
|
| 1159 |
int LZ4_decompress_fast_usingDict(const char* source, char* dest, int originalSize, const char* dictStart, int dictSize) |
| 1160 |
{ |
| 1161 |
return LZ4_decompress_generic(source, dest, 0, originalSize, endOnOutputSize, full, 0, usingExtDict, dictStart, dictSize); |
| 1162 |
} |
| 1163 |
|
| 1164 |
|
| 1165 |
/*************************************************** |
| 1166 |
Obsolete Functions |
| 1167 |
***************************************************/ |
| 1168 |
/* |
| 1169 |
These function names are deprecated and should no longer be used. |
| 1170 |
They are only provided here for compatibility with older user programs. |
| 1171 |
- LZ4_uncompress is totally equivalent to LZ4_decompress_fast |
| 1172 |
- LZ4_uncompress_unknownOutputSize is totally equivalent to LZ4_decompress_safe |
| 1173 |
*/ |
| 1174 |
int LZ4_uncompress (const char* source, char* dest, int outputSize) { return LZ4_decompress_fast(source, dest, outputSize); } |
| 1175 |
int LZ4_uncompress_unknownOutputSize (const char* source, char* dest, int isize, int maxOutputSize) { return LZ4_decompress_safe(source, dest, isize, maxOutputSize); } |
| 1176 |
|
| 1177 |
|
| 1178 |
/* Obsolete Streaming functions */ |
| 1179 |
|
| 1180 |
int LZ4_sizeofStreamState() { return LZ4_STREAMSIZE; } |
| 1181 |
|
| 1182 |
void LZ4_init(LZ4_stream_t_internal* lz4ds, const BYTE* base) |
| 1183 |
{ |
| 1184 |
MEM_INIT(lz4ds, 0, LZ4_STREAMSIZE); |
| 1185 |
lz4ds->bufferStart = base; |
| 1186 |
} |
| 1187 |
|
| 1188 |
int LZ4_resetStreamState(void* state, const char* inputBuffer) |
| 1189 |
{ |
| 1190 |
if ((((size_t)state) & 3) != 0) return 1; /* Error : pointer is not aligned on 4-bytes boundary */ |
| 1191 |
LZ4_init((LZ4_stream_t_internal*)state, (const BYTE*)inputBuffer); |
| 1192 |
return 0; |
| 1193 |
} |
| 1194 |
|
| 1195 |
void* LZ4_create (const char* inputBuffer) |
| 1196 |
{ |
| 1197 |
void* lz4ds = ALLOCATOR(4, LZ4_STREAMSIZE_U32); |
| 1198 |
LZ4_init ((LZ4_stream_t_internal*)lz4ds, (const BYTE*)inputBuffer); |
| 1199 |
return lz4ds; |
| 1200 |
} |
| 1201 |
|
| 1202 |
char* LZ4_slideInputBuffer (void* LZ4_Data) |
| 1203 |
{ |
| 1204 |
LZ4_stream_t_internal* lz4ds = (LZ4_stream_t_internal*)LZ4_Data; |
| 1205 |
|
| 1206 |
LZ4_saveDict((LZ4_stream_t*)LZ4_Data, (char*)lz4ds->bufferStart, 64 KB); |
| 1207 |
|
| 1208 |
return (char*)(lz4ds->bufferStart + 64 KB); |
| 1209 |
} |
| 1210 |
|
| 1211 |
/* Obsolete compresson functions using User-allocated state */ |
| 1212 |
|
| 1213 |
int LZ4_sizeofState() { return LZ4_STREAMSIZE; } |
| 1214 |
|
| 1215 |
int LZ4_compress_withState (void* state, const char* source, char* dest, int inputSize) |
| 1216 |
{ |
| 1217 |
if (((size_t)(state)&3) != 0) return 0; /* Error : state is not aligned on 4-bytes boundary */ |
| 1218 |
MEM_INIT(state, 0, LZ4_STREAMSIZE); |
| 1219 |
|
| 1220 |
if (inputSize < (int)LZ4_64KLIMIT) |
| 1221 |
return LZ4_compress_generic(state, source, dest, inputSize, 0, notLimited, byU16, noDict, noDictIssue); |
| 1222 |
else |
| 1223 |
return LZ4_compress_generic(state, source, dest, inputSize, 0, notLimited, (sizeof(void*)==8) ? byU32 : byPtr, noDict, noDictIssue); |
| 1224 |
} |
| 1225 |
|
| 1226 |
int LZ4_compress_limitedOutput_withState (void* state, const char* source, char* dest, int inputSize, int maxOutputSize) |
| 1227 |
{ |
| 1228 |
if (((size_t)(state)&3) != 0) return 0; /* Error : state is not aligned on 4-bytes boundary */ |
| 1229 |
MEM_INIT(state, 0, LZ4_STREAMSIZE); |
| 1230 |
|
| 1231 |
if (inputSize < (int)LZ4_64KLIMIT) |
| 1232 |
return LZ4_compress_generic(state, source, dest, inputSize, maxOutputSize, limitedOutput, byU16, noDict, noDictIssue); |
| 1233 |
else |
| 1234 |
return LZ4_compress_generic(state, source, dest, inputSize, maxOutputSize, limitedOutput, (sizeof(void*)==8) ? byU32 : byPtr, noDict, noDictIssue); |
| 1235 |
} |
| 1236 |
|
| 1237 |
/* Obsolete streaming decompression functions */ |
| 1238 |
|
| 1239 |
int LZ4_decompress_safe_withPrefix64k(const char* source, char* dest, int compressedSize, int maxOutputSize) |
| 1240 |
{ |
| 1241 |
return LZ4_decompress_generic(source, dest, compressedSize, maxOutputSize, endOnInputSize, full, 0, withPrefix64k, NULL, 64 KB); |
| 1242 |
} |
| 1243 |
|
| 1244 |
int LZ4_decompress_fast_withPrefix64k(const char* source, char* dest, int originalSize) |
| 1245 |
{ |
| 1246 |
return LZ4_decompress_generic(source, dest, 0, originalSize, endOnOutputSize, full, 0, withPrefix64k, NULL, 64 KB); |
| 1247 |
} |