Leviathan  0.8.0.0
Leviathan game engine
lz4hc.c File Reference
#include <stdlib.h>
#include <string.h>
#include "lz4hc.h"
#include "lz4.h"

Go to the source code of this file.

Classes

struct  _U16_S
 
struct  _U32_S
 
struct  _U64_S
 
struct  LZ4HC_Data_Structure
 

Macros

#define ALLOCATOR(s)   calloc(1,s)
 
#define FREEMEM   free
 
#define MEM_INIT   memset
 
#define LZ4_ARCH64   0
 
#define restrict
 
#define FORCE_INLINE   static inline
 
#define lz4_bswap16(x)   ((unsigned short int) ((((x) >> 8) & 0xffu) | (((x) & 0xffu) << 8)))
 
#define _PACKED
 
#define A64(x)   (((U64_S *)(x))->v)
 
#define A32(x)   (((U32_S *)(x))->v)
 
#define A16(x)   (((U16_S *)(x))->v)
 
#define MINMATCH   4
 
#define DICTIONARY_LOGSIZE   16
 
#define MAXD   (1<<DICTIONARY_LOGSIZE)
 
#define MAXD_MASK   ((U32)(MAXD - 1))
 
#define MAX_DISTANCE   (MAXD - 1)
 
#define HASH_LOG   (DICTIONARY_LOGSIZE-1)
 
#define HASHTABLESIZE   (1 << HASH_LOG)
 
#define HASH_MASK   (HASHTABLESIZE - 1)
 
#define MAX_NB_ATTEMPTS   256
 
#define ML_BITS   4
 
#define ML_MASK   (size_t)((1U<<ML_BITS)-1)
 
#define RUN_BITS   (8-ML_BITS)
 
#define RUN_MASK   ((1U<<RUN_BITS)-1)
 
#define COPYLENGTH   8
 
#define LASTLITERALS   5
 
#define MFLIMIT   (COPYLENGTH+MINMATCH)
 
#define MINLENGTH   (MFLIMIT+1)
 
#define OPTIMAL_ML   (int)((ML_MASK-1)+MINMATCH)
 
#define KB   *(1U<<10)
 
#define MB   *(1U<<20)
 
#define GB   *(1U<<30)
 
#define STEPSIZE   4
 
#define LZ4_COPYSTEP(s, d)   A32(d) = A32(s); d+=4; s+=4;
 
#define LZ4_COPYPACKET(s, d)   LZ4_COPYSTEP(s,d); LZ4_COPYSTEP(s,d);
 
#define UARCH   U32
 
#define AARCH   A32
 
#define HTYPE   U32
 
#define INITBASE(b, s)   const BYTE* const b = s
 
#define LZ4_READ_LITTLEENDIAN_16(d, s, p)   { d = (s) - A16(p); }
 
#define LZ4_WRITE_LITTLEENDIAN_16(p, v)   { A16(p) = v; p+=2; }
 
#define LZ4_WILDCOPY(s, d, e)   do { LZ4_COPYPACKET(s,d) } while (d<e);
 
#define LZ4_BLINDCOPY(s, d, l)   { BYTE* e=d+l; LZ4_WILDCOPY(s,d,e); d=e; }
 
#define HASH_FUNCTION(i)   (((i) * 2654435761U) >> ((MINMATCH*8)-HASH_LOG))
 
#define HASH_VALUE(p)   HASH_FUNCTION(A32(p))
 
#define HASH_POINTER(p)   (HashTable[HASH_VALUE(p)] + base)
 
#define DELTANEXT(p)   chainTable[(size_t)(p) & MAXD_MASK]
 
#define GETNEXT(p)   ((p) - (size_t)DELTANEXT(p))
 
#define REPEAT_OPTIMIZATION
 

Typedefs

typedef unsigned char BYTE
 
typedef unsigned short U16
 
typedef unsigned int U32
 
typedef signed int S32
 
typedef unsigned long long U64
 
typedef struct _U16_S U16_S
 
typedef struct _U32_S U32_S
 
typedef struct _U64_S U64_S
 

Enumerations

enum  limitedOutput_directive { notLimited = 0, limited = 1, noLimit = 0, limitedOutput = 1 }
 

Functions

FORCE_INLINE int LZ4_NbCommonBytes (register U32 val)
 
int LZ4_sizeofStreamStateHC ()
 
FORCE_INLINE void LZ4_initHC (LZ4HC_Data_Structure *hc4, const BYTE *base)
 
int LZ4_resetStreamStateHC (void *state, const char *inputBuffer)
 
void * LZ4_createHC (const char *inputBuffer)
 
int LZ4_freeHC (void *LZ4HC_Data)
 
FORCE_INLINE void LZ4HC_Insert (LZ4HC_Data_Structure *hc4, const BYTE *ip)
 
char * LZ4_slideInputBufferHC (void *LZ4HC_Data)
 
FORCE_INLINE size_t LZ4HC_CommonLength (const BYTE *p1, const BYTE *p2, const BYTE *const matchlimit)
 
FORCE_INLINE int LZ4HC_InsertAndFindBestMatch (LZ4HC_Data_Structure *hc4, const BYTE *ip, const BYTE *const matchlimit, const BYTE **matchpos)
 
FORCE_INLINE int LZ4HC_InsertAndGetWiderMatch (LZ4HC_Data_Structure *hc4, const BYTE *ip, const BYTE *startLimit, const BYTE *matchlimit, int longest, const BYTE **matchpos, const BYTE **startpos)
 
FORCE_INLINE int LZ4HC_encodeSequence (const BYTE **ip, BYTE **op, const BYTE **anchor, int matchLength, const BYTE *ref, limitedOutput_directive limitedOutputBuffer, BYTE *oend)
 
static int LZ4HC_compress_generic (void *ctxvoid, const char *source, char *dest, int inputSize, int maxOutputSize, limitedOutput_directive limit)
 
int LZ4_compressHC (const char *source, char *dest, int inputSize)
 
int LZ4_compressHC_limitedOutput (const char *source, char *dest, int inputSize, int maxOutputSize)
 
int LZ4_sizeofStateHC ()
 
int LZ4_compressHC_withStateHC (void *state, const char *source, char *dest, int inputSize)
 
int LZ4_compressHC_limitedOutput_withStateHC (void *state, const char *source, char *dest, int inputSize, int maxOutputSize)
 
int LZ4_compressHC_continue (void *LZ4HC_Data, const char *source, char *dest, int inputSize)
 
int LZ4_compressHC_limitedOutput_continue (void *LZ4HC_Data, const char *source, char *dest, int inputSize, int maxOutputSize)
 

Macro Definition Documentation

◆ _PACKED

#define _PACKED

Definition at line 152 of file lz4hc.c.

◆ A16

#define A16 (   x)    (((U16_S *)(x))->v)

Definition at line 173 of file lz4hc.c.

◆ A32

#define A32 (   x)    (((U32_S *)(x))->v)

Definition at line 172 of file lz4hc.c.

◆ A64

#define A64 (   x)    (((U64_S *)(x))->v)

Definition at line 171 of file lz4hc.c.

◆ AARCH

#define AARCH   A32

Definition at line 224 of file lz4hc.c.

◆ ALLOCATOR

#define ALLOCATOR (   s)    calloc(1,s)

Definition at line 38 of file lz4hc.c.

◆ COPYLENGTH

#define COPYLENGTH   8

Definition at line 197 of file lz4hc.c.

◆ DELTANEXT

#define DELTANEXT (   p)    chainTable[(size_t)(p) & MAXD_MASK]

Definition at line 262 of file lz4hc.c.

◆ DICTIONARY_LOGSIZE

#define DICTIONARY_LOGSIZE   16

Definition at line 181 of file lz4hc.c.

◆ FORCE_INLINE

#define FORCE_INLINE   static inline

Definition at line 113 of file lz4hc.c.

◆ FREEMEM

#define FREEMEM   free

Definition at line 39 of file lz4hc.c.

◆ GB

#define GB   *(1U<<30)

Definition at line 205 of file lz4hc.c.

◆ GETNEXT

#define GETNEXT (   p)    ((p) - (size_t)DELTANEXT(p))

Definition at line 263 of file lz4hc.c.

◆ HASH_FUNCTION

#define HASH_FUNCTION (   i)    (((i) * 2654435761U) >> ((MINMATCH*8)-HASH_LOG))

Definition at line 259 of file lz4hc.c.

◆ HASH_LOG

#define HASH_LOG   (DICTIONARY_LOGSIZE-1)

Definition at line 186 of file lz4hc.c.

◆ HASH_MASK

#define HASH_MASK   (HASHTABLESIZE - 1)

Definition at line 188 of file lz4hc.c.

◆ HASH_POINTER

#define HASH_POINTER (   p)    (HashTable[HASH_VALUE(p)] + base)

Definition at line 261 of file lz4hc.c.

◆ HASH_VALUE

#define HASH_VALUE (   p)    HASH_FUNCTION(A32(p))

Definition at line 260 of file lz4hc.c.

◆ HASHTABLESIZE

#define HASHTABLESIZE   (1 << HASH_LOG)

Definition at line 187 of file lz4hc.c.

◆ HTYPE

#define HTYPE   U32

Definition at line 227 of file lz4hc.c.

◆ INITBASE

#define INITBASE (   b,
 
)    const BYTE* const b = s

Definition at line 228 of file lz4hc.c.

◆ KB

#define KB   *(1U<<10)

Definition at line 203 of file lz4hc.c.

◆ LASTLITERALS

#define LASTLITERALS   5

Definition at line 198 of file lz4hc.c.

◆ LZ4_ARCH64

#define LZ4_ARCH64   0

Definition at line 54 of file lz4hc.c.

◆ LZ4_BLINDCOPY

#define LZ4_BLINDCOPY (   s,
  d,
 
)    { BYTE* e=d+l; LZ4_WILDCOPY(s,d,e); d=e; }

Definition at line 258 of file lz4hc.c.

◆ lz4_bswap16

#define lz4_bswap16 (   x)    ((unsigned short int) ((((x) >> 8) & 0xffu) | (((x) & 0xffu) << 8)))

Definition at line 120 of file lz4hc.c.

◆ LZ4_COPYPACKET

#define LZ4_COPYPACKET (   s,
 
)    LZ4_COPYSTEP(s,d); LZ4_COPYSTEP(s,d);

Definition at line 222 of file lz4hc.c.

◆ LZ4_COPYSTEP

#define LZ4_COPYSTEP (   s,
 
)    A32(d) = A32(s); d+=4; s+=4;

Definition at line 221 of file lz4hc.c.

◆ LZ4_READ_LITTLEENDIAN_16

#define LZ4_READ_LITTLEENDIAN_16 (   d,
  s,
 
)    { d = (s) - A16(p); }

Definition at line 235 of file lz4hc.c.

◆ LZ4_WILDCOPY

#define LZ4_WILDCOPY (   s,
  d,
 
)    do { LZ4_COPYPACKET(s,d) } while (d<e);

Definition at line 257 of file lz4hc.c.

◆ LZ4_WRITE_LITTLEENDIAN_16

#define LZ4_WRITE_LITTLEENDIAN_16 (   p,
 
)    { A16(p) = v; p+=2; }

Definition at line 236 of file lz4hc.c.

◆ MAX_DISTANCE

#define MAX_DISTANCE   (MAXD - 1)

Definition at line 184 of file lz4hc.c.

◆ MAX_NB_ATTEMPTS

#define MAX_NB_ATTEMPTS   256

Definition at line 190 of file lz4hc.c.

◆ MAXD

#define MAXD   (1<<DICTIONARY_LOGSIZE)

Definition at line 182 of file lz4hc.c.

◆ MAXD_MASK

#define MAXD_MASK   ((U32)(MAXD - 1))

Definition at line 183 of file lz4hc.c.

◆ MB

#define MB   *(1U<<20)

Definition at line 204 of file lz4hc.c.

◆ MEM_INIT

#define MEM_INIT   memset

Definition at line 41 of file lz4hc.c.

◆ MFLIMIT

#define MFLIMIT   (COPYLENGTH+MINMATCH)

Definition at line 199 of file lz4hc.c.

◆ MINLENGTH

#define MINLENGTH   (MFLIMIT+1)

Definition at line 200 of file lz4hc.c.

◆ MINMATCH

#define MINMATCH   4

Definition at line 179 of file lz4hc.c.

◆ ML_BITS

#define ML_BITS   4

Definition at line 192 of file lz4hc.c.

◆ ML_MASK

#define ML_MASK   (size_t)((1U<<ML_BITS)-1)

Definition at line 193 of file lz4hc.c.

◆ OPTIMAL_ML

#define OPTIMAL_ML   (int)((ML_MASK-1)+MINMATCH)

Definition at line 201 of file lz4hc.c.

◆ REPEAT_OPTIMIZATION

#define REPEAT_OPTIMIZATION

◆ restrict

#define restrict

Definition at line 94 of file lz4hc.c.

◆ RUN_BITS

#define RUN_BITS   (8-ML_BITS)

Definition at line 194 of file lz4hc.c.

◆ RUN_MASK

#define RUN_MASK   ((1U<<RUN_BITS)-1)

Definition at line 195 of file lz4hc.c.

◆ STEPSIZE

#define STEPSIZE   4

Definition at line 220 of file lz4hc.c.

◆ UARCH

#define UARCH   U32

Definition at line 223 of file lz4hc.c.

Typedef Documentation

◆ BYTE

typedef unsigned char BYTE

Definition at line 142 of file lz4hc.c.

◆ S32

typedef signed int S32

Definition at line 145 of file lz4hc.c.

◆ U16

typedef unsigned short U16

Definition at line 143 of file lz4hc.c.

◆ U16_S

typedef struct _U16_S U16_S

◆ U32

typedef unsigned int U32

Definition at line 144 of file lz4hc.c.

◆ U32_S

typedef struct _U32_S U32_S

◆ U64

typedef unsigned long long U64

Definition at line 146 of file lz4hc.c.

◆ U64_S

typedef struct _U64_S U64_S

Enumeration Type Documentation

◆ limitedOutput_directive

Enumerator
notLimited 
limited 
noLimit 
limitedOutput 

Definition at line 557 of file lz4hc.c.

limitedOutput_directive
Definition: lz4hc.c:557
Definition: lz4hc.c:557

Function Documentation

◆ LZ4_compressHC()

int LZ4_compressHC ( const char *  source,
char *  dest,
int  inputSize 
)

Definition at line 795 of file lz4hc.c.

796 {
797  void* ctx = LZ4_createHC(source);
798  int result;
799  if (ctx==NULL) return 0;
800 
801  result = LZ4HC_compress_generic (ctx, source, dest, inputSize, 0, noLimit);
802 
803  LZ4_freeHC(ctx);
804  return result;
805 }
int LZ4_freeHC(void *LZ4HC_Data)
Definition: lz4hc.c:366
void * LZ4_createHC(const char *inputBuffer)
Definition: lz4hc.c:358
static int LZ4HC_compress_generic(void *ctxvoid, const char *source, char *dest, int inputSize, int maxOutputSize, limitedOutput_directive limit)
Definition: lz4hc.c:598
Definition: lz4hc.c:557

◆ LZ4_compressHC_continue()

int LZ4_compressHC_continue ( void *  LZ4HC_Data,
const char *  source,
char *  dest,
int  inputSize 
)

Definition at line 847 of file lz4hc.c.

848 {
849  return LZ4HC_compress_generic (LZ4HC_Data, source, dest, inputSize, 0, noLimit);
850 }
static int LZ4HC_compress_generic(void *ctxvoid, const char *source, char *dest, int inputSize, int maxOutputSize, limitedOutput_directive limit)
Definition: lz4hc.c:598
Definition: lz4hc.c:557

◆ LZ4_compressHC_limitedOutput()

int LZ4_compressHC_limitedOutput ( const char *  source,
char *  dest,
int  inputSize,
int  maxOutputSize 
)

Definition at line 807 of file lz4hc.c.

808 {
809  void* ctx = LZ4_createHC(source);
810  int result;
811  if (ctx==NULL) return 0;
812 
813  result = LZ4HC_compress_generic (ctx, source, dest, inputSize, maxOutputSize, limitedOutput);
814 
815  LZ4_freeHC(ctx);
816  return result;
817 }
int LZ4_freeHC(void *LZ4HC_Data)
Definition: lz4hc.c:366
void * LZ4_createHC(const char *inputBuffer)
Definition: lz4hc.c:358
static int LZ4HC_compress_generic(void *ctxvoid, const char *source, char *dest, int inputSize, int maxOutputSize, limitedOutput_directive limit)
Definition: lz4hc.c:598

◆ LZ4_compressHC_limitedOutput_continue()

int LZ4_compressHC_limitedOutput_continue ( void *  LZ4HC_Data,
const char *  source,
char *  dest,
int  inputSize,
int  maxOutputSize 
)

Definition at line 852 of file lz4hc.c.

853 {
854  return LZ4HC_compress_generic (LZ4HC_Data, source, dest, inputSize, maxOutputSize, limitedOutput);
855 }
static int LZ4HC_compress_generic(void *ctxvoid, const char *source, char *dest, int inputSize, int maxOutputSize, limitedOutput_directive limit)
Definition: lz4hc.c:598

◆ LZ4_compressHC_limitedOutput_withStateHC()

int LZ4_compressHC_limitedOutput_withStateHC ( void *  state,
const char *  source,
char *  dest,
int  inputSize,
int  maxOutputSize 
)

Definition at line 835 of file lz4hc.c.

836 {
837  if (((size_t)(state)&(sizeof(void*)-1)) != 0) return 0; // Error : state is not aligned for pointers (32 or 64 bits)
838  LZ4_initHC ((LZ4HC_Data_Structure*)state, (const BYTE*)source);
839  return LZ4HC_compress_generic (state, source, dest, inputSize, maxOutputSize, limitedOutput);
840 }
unsigned char BYTE
Definition: lz4.c:173
static int LZ4HC_compress_generic(void *ctxvoid, const char *source, char *dest, int inputSize, int maxOutputSize, limitedOutput_directive limit)
Definition: lz4hc.c:598
FORCE_INLINE void LZ4_initHC(LZ4HC_Data_Structure *hc4, const BYTE *base)
Definition: lz4hc.c:340

◆ LZ4_compressHC_withStateHC()

int LZ4_compressHC_withStateHC ( void *  state,
const char *  source,
char *  dest,
int  inputSize 
)

Definition at line 827 of file lz4hc.c.

828 {
829  if (((size_t)(state)&(sizeof(void*)-1)) != 0) return 0; // Error : state is not aligned for pointers (32 or 64 bits)
830  LZ4_initHC ((LZ4HC_Data_Structure*)state, (const BYTE*)source);
831  return LZ4HC_compress_generic (state, source, dest, inputSize, 0, noLimit);
832 }
unsigned char BYTE
Definition: lz4.c:173
static int LZ4HC_compress_generic(void *ctxvoid, const char *source, char *dest, int inputSize, int maxOutputSize, limitedOutput_directive limit)
Definition: lz4hc.c:598
Definition: lz4hc.c:557
FORCE_INLINE void LZ4_initHC(LZ4HC_Data_Structure *hc4, const BYTE *base)
Definition: lz4hc.c:340

◆ LZ4_createHC()

void* LZ4_createHC ( const char *  inputBuffer)

Definition at line 358 of file lz4hc.c.

359 {
360  void* hc4 = ALLOCATOR(sizeof(LZ4HC_Data_Structure));
361  LZ4_initHC ((LZ4HC_Data_Structure*)hc4, (const BYTE*)inputBuffer);
362  return hc4;
363 }
unsigned char BYTE
Definition: lz4.c:173
FORCE_INLINE void LZ4_initHC(LZ4HC_Data_Structure *hc4, const BYTE *base)
Definition: lz4hc.c:340
#define ALLOCATOR(s)
Definition: lz4hc.c:38

◆ LZ4_freeHC()

int LZ4_freeHC ( void *  LZ4HC_Data)

Definition at line 366 of file lz4hc.c.

367 {
368  FREEMEM(LZ4HC_Data);
369  return (0);
370 }
#define FREEMEM
Definition: lz4hc.c:39

◆ LZ4_initHC()

FORCE_INLINE void LZ4_initHC ( LZ4HC_Data_Structure hc4,
const BYTE base 
)

Definition at line 340 of file lz4hc.c.

341 {
342  MEM_INIT((void*)hc4->hashTable, 0, sizeof(hc4->hashTable));
343  MEM_INIT(hc4->chainTable, 0xFF, sizeof(hc4->chainTable));
344  hc4->nextToUpdate = base + 1;
345  hc4->base = base;
346  hc4->inputBuffer = base;
347  hc4->end = base;
348 }
HTYPE hashTable[HASHTABLESIZE]
Definition: lz4hc.c:248
#define MEM_INIT
Definition: lz4hc.c:41
U16 chainTable[MAXD]
Definition: lz4hc.c:249
const BYTE * base
Definition: lz4hc.c:246
const BYTE * inputBuffer
Definition: lz4hc.c:245
const BYTE * end
Definition: lz4hc.c:247
const BYTE * nextToUpdate
Definition: lz4hc.c:250

◆ LZ4_NbCommonBytes()

FORCE_INLINE int LZ4_NbCommonBytes ( register U32  val)

Definition at line 303 of file lz4hc.c.

304 {
305 #if defined(LZ4_BIG_ENDIAN)
306 # if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
307  unsigned long r;
308  _BitScanReverse( &r, val );
309  return (int)(r>>3);
310 # elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)
311  return (__builtin_clz(val) >> 3);
312 # else
313  int r;
314  if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; }
315  r += (!val);
316  return r;
317 # endif
318 #else
319 # if defined(_MSC_VER) && !defined(LZ4_FORCE_SW_BITCOUNT)
320  unsigned long r;
321  _BitScanForward( &r, val );
322  return (int)(r>>3);
323 # elif defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 304) && !defined(LZ4_FORCE_SW_BITCOUNT)
324  return (__builtin_ctz(val) >> 3);
325 # else
326  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 };
327  return DeBruijnBytePos[((U32)((val & -(S32)val) * 0x077CB531U)) >> 27];
328 # endif
329 #endif
330 }
signed int S32
Definition: lz4.c:176
unsigned int U32
Definition: lz4hc.c:144

◆ LZ4_resetStreamStateHC()

int LZ4_resetStreamStateHC ( void *  state,
const char *  inputBuffer 
)

Definition at line 350 of file lz4hc.c.

351 {
352  if ((((size_t)state) & (sizeof(void*)-1)) != 0) return 1; // Error : pointer is not aligned for pointer (32 or 64 bits)
353  LZ4_initHC((LZ4HC_Data_Structure*)state, (const BYTE*)inputBuffer);
354  return 0;
355 }
unsigned char BYTE
Definition: lz4.c:173
FORCE_INLINE void LZ4_initHC(LZ4HC_Data_Structure *hc4, const BYTE *base)
Definition: lz4hc.c:340

◆ LZ4_sizeofStateHC()

int LZ4_sizeofStateHC ( )

Definition at line 824 of file lz4hc.c.

824 { return sizeof(LZ4HC_Data_Structure); }

◆ LZ4_sizeofStreamStateHC()

int LZ4_sizeofStreamStateHC ( )

Definition at line 335 of file lz4hc.c.

336 {
337  return sizeof(LZ4HC_Data_Structure);
338 }

◆ LZ4_slideInputBufferHC()

char* LZ4_slideInputBufferHC ( void *  LZ4HC_Data)

Definition at line 392 of file lz4hc.c.

393 {
394  LZ4HC_Data_Structure* hc4 = (LZ4HC_Data_Structure*)LZ4HC_Data;
395  U32 distance = (U32)(hc4->end - hc4->inputBuffer) - 64 KB;
396  distance = (distance >> 16) << 16; // Must be a multiple of 64 KB
397  LZ4HC_Insert(hc4, hc4->end - MINMATCH);
398  memcpy((void*)(hc4->end - 64 KB - distance), (const void*)(hc4->end - 64 KB), 64 KB);
399  hc4->nextToUpdate -= distance;
400  hc4->base -= distance;
401  if ((U32)(hc4->inputBuffer - hc4->base) > 1 GB + 64 KB) // Avoid overflow
402  {
403  int i;
404  hc4->base += 1 GB;
405  for (i=0; i<HASHTABLESIZE; i++) hc4->hashTable[i] -= 1 GB;
406  }
407  hc4->end -= distance;
408  return (char*)(hc4->end);
409 }
HTYPE hashTable[HASHTABLESIZE]
Definition: lz4hc.c:248
unsigned int U32
Definition: lz4.c:175
#define KB
Definition: lz4hc.c:203
#define MINMATCH
Definition: lz4hc.c:179
FORCE_INLINE void LZ4HC_Insert(LZ4HC_Data_Structure *hc4, const BYTE *ip)
Definition: lz4hc.c:374
#define GB
Definition: lz4hc.c:205
#define HASHTABLESIZE
Definition: lz4hc.c:187
const BYTE * base
Definition: lz4hc.c:246
const BYTE * inputBuffer
Definition: lz4hc.c:245
const BYTE * end
Definition: lz4hc.c:247
const BYTE * nextToUpdate
Definition: lz4hc.c:250
std::iterator_traits< octet_iterator >::difference_type distance(octet_iterator first, octet_iterator last)
Definition: checked.h:198
unsigned int U32
Definition: lz4hc.c:144

◆ LZ4HC_CommonLength()

FORCE_INLINE size_t LZ4HC_CommonLength ( const BYTE p1,
const BYTE p2,
const BYTE *const  matchlimit 
)

Definition at line 412 of file lz4hc.c.

413 {
414  const BYTE* p1t = p1;
415 
416  while (p1t<matchlimit-(STEPSIZE-1))
417  {
418  UARCH diff = AARCH(p2) ^ AARCH(p1t);
419  if (!diff) { p1t+=STEPSIZE; p2+=STEPSIZE; continue; }
420  p1t += LZ4_NbCommonBytes(diff);
421  return (p1t - p1);
422  }
423  if (LZ4_ARCH64) if ((p1t<(matchlimit-3)) && (A32(p2) == A32(p1t))) { p1t+=4; p2+=4; }
424  if ((p1t<(matchlimit-1)) && (A16(p2) == A16(p1t))) { p1t+=2; p2+=2; }
425  if ((p1t<matchlimit) && (*p2 == *p1t)) p1t++;
426  return (p1t - p1);
427 }
#define STEPSIZE
Definition: lz4hc.c:220
#define AARCH
Definition: lz4hc.c:224
#define UARCH
Definition: lz4hc.c:223
#define A16(x)
Definition: lz4hc.c:173
unsigned char BYTE
Definition: lz4.c:173
FORCE_INLINE int LZ4_NbCommonBytes(register U32 val)
Definition: lz4hc.c:303
#define A32(x)
Definition: lz4hc.c:172
#define LZ4_ARCH64
Definition: lz4hc.c:54

◆ LZ4HC_compress_generic()

static int LZ4HC_compress_generic ( void *  ctxvoid,
const char *  source,
char *  dest,
int  inputSize,
int  maxOutputSize,
limitedOutput_directive  limit 
)
static

Definition at line 598 of file lz4hc.c.

606 {
607  LZ4HC_Data_Structure* ctx = (LZ4HC_Data_Structure*) ctxvoid;
608  const BYTE* ip = (const BYTE*) source;
609  const BYTE* anchor = ip;
610  const BYTE* const iend = ip + inputSize;
611  const BYTE* const mflimit = iend - MFLIMIT;
612  const BYTE* const matchlimit = (iend - LASTLITERALS);
613 
614  BYTE* op = (BYTE*) dest;
615  BYTE* const oend = op + maxOutputSize;
616 
617  int ml, ml2, ml3, ml0;
618  const BYTE* ref=NULL;
619  const BYTE* start2=NULL;
620  const BYTE* ref2=NULL;
621  const BYTE* start3=NULL;
622  const BYTE* ref3=NULL;
623  const BYTE* start0;
624  const BYTE* ref0;
625 
626 
627  // Ensure blocks follow each other
628  if (ip != ctx->end) return 0;
629  ctx->end += inputSize;
630 
631  ip++;
632 
633  // Main Loop
634  while (ip < mflimit)
635  {
636  ml = LZ4HC_InsertAndFindBestMatch (ctx, ip, matchlimit, (&ref));
637  if (!ml) { ip++; continue; }
638 
639  // saved, in case we would skip too much
640  start0 = ip;
641  ref0 = ref;
642  ml0 = ml;
643 
644 _Search2:
645  if (ip+ml < mflimit)
646  ml2 = LZ4HC_InsertAndGetWiderMatch(ctx, ip + ml - 2, ip + 1, matchlimit, ml, &ref2, &start2);
647  else ml2 = ml;
648 
649  if (ml2 == ml) // No better match
650  {
651  if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml, ref, limit, oend)) return 0;
652  continue;
653  }
654 
655  if (start0 < ip)
656  {
657  if (start2 < ip + ml0) // empirical
658  {
659  ip = start0;
660  ref = ref0;
661  ml = ml0;
662  }
663  }
664 
665  // Here, start0==ip
666  if ((start2 - ip) < 3) // First Match too small : removed
667  {
668  ml = ml2;
669  ip = start2;
670  ref =ref2;
671  goto _Search2;
672  }
673 
674 _Search3:
675  // Currently we have :
676  // ml2 > ml1, and
677  // ip1+3 <= ip2 (usually < ip1+ml1)
678  if ((start2 - ip) < OPTIMAL_ML)
679  {
680  int correction;
681  int new_ml = ml;
682  if (new_ml > OPTIMAL_ML) new_ml = OPTIMAL_ML;
683  if (ip+new_ml > start2 + ml2 - MINMATCH) new_ml = (int)(start2 - ip) + ml2 - MINMATCH;
684  correction = new_ml - (int)(start2 - ip);
685  if (correction > 0)
686  {
687  start2 += correction;
688  ref2 += correction;
689  ml2 -= correction;
690  }
691  }
692  // Now, we have start2 = ip+new_ml, with new_ml = min(ml, OPTIMAL_ML=18)
693 
694  if (start2 + ml2 < mflimit)
695  ml3 = LZ4HC_InsertAndGetWiderMatch(ctx, start2 + ml2 - 3, start2, matchlimit, ml2, &ref3, &start3);
696  else ml3 = ml2;
697 
698  if (ml3 == ml2) // No better match : 2 sequences to encode
699  {
700  // ip & ref are known; Now for ml
701  if (start2 < ip+ml) ml = (int)(start2 - ip);
702  // Now, encode 2 sequences
703  if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml, ref, limit, oend)) return 0;
704  ip = start2;
705  if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml2, ref2, limit, oend)) return 0;
706  continue;
707  }
708 
709  if (start3 < ip+ml+3) // Not enough space for match 2 : remove it
710  {
711  if (start3 >= (ip+ml)) // can write Seq1 immediately ==> Seq2 is removed, so Seq3 becomes Seq1
712  {
713  if (start2 < ip+ml)
714  {
715  int correction = (int)(ip+ml - start2);
716  start2 += correction;
717  ref2 += correction;
718  ml2 -= correction;
719  if (ml2 < MINMATCH)
720  {
721  start2 = start3;
722  ref2 = ref3;
723  ml2 = ml3;
724  }
725  }
726 
727  if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml, ref, limit, oend)) return 0;
728  ip = start3;
729  ref = ref3;
730  ml = ml3;
731 
732  start0 = start2;
733  ref0 = ref2;
734  ml0 = ml2;
735  goto _Search2;
736  }
737 
738  start2 = start3;
739  ref2 = ref3;
740  ml2 = ml3;
741  goto _Search3;
742  }
743 
744  // OK, now we have 3 ascending matches; let's write at least the first one
745  // ip & ref are known; Now for ml
746  if (start2 < ip+ml)
747  {
748  if ((start2 - ip) < (int)ML_MASK)
749  {
750  int correction;
751  if (ml > OPTIMAL_ML) ml = OPTIMAL_ML;
752  if (ip + ml > start2 + ml2 - MINMATCH) ml = (int)(start2 - ip) + ml2 - MINMATCH;
753  correction = ml - (int)(start2 - ip);
754  if (correction > 0)
755  {
756  start2 += correction;
757  ref2 += correction;
758  ml2 -= correction;
759  }
760  }
761  else
762  {
763  ml = (int)(start2 - ip);
764  }
765  }
766  if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml, ref, limit, oend)) return 0;
767 
768  ip = start2;
769  ref = ref2;
770  ml = ml2;
771 
772  start2 = start3;
773  ref2 = ref3;
774  ml2 = ml3;
775 
776  goto _Search3;
777 
778  }
779 
780  // Encode Last Literals
781  {
782  int lastRun = (int)(iend - anchor);
783  if ((limit) && (((char*)op - dest) + lastRun + 1 + ((lastRun+255-RUN_MASK)/255) > (U32)maxOutputSize)) return 0; // Check output limit
784  if (lastRun>=(int)RUN_MASK) { *op++=(RUN_MASK<<ML_BITS); lastRun-=RUN_MASK; for(; lastRun > 254 ; lastRun-=255) *op++ = 255; *op++ = (BYTE) lastRun; }
785  else *op++ = (BYTE)(lastRun<<ML_BITS);
786  memcpy(op, anchor, iend - anchor);
787  op += iend-anchor;
788  }
789 
790  // End
791  return (int) (((char*)op)-dest);
792 }
#define MFLIMIT
Definition: lz4hc.c:199
#define LASTLITERALS
Definition: lz4hc.c:198
#define MINMATCH
Definition: lz4hc.c:179
#define ML_BITS
Definition: lz4hc.c:192
unsigned char BYTE
Definition: lz4.c:173
FORCE_INLINE int LZ4HC_InsertAndGetWiderMatch(LZ4HC_Data_Structure *hc4, const BYTE *ip, const BYTE *startLimit, const BYTE *matchlimit, int longest, const BYTE **matchpos, const BYTE **startpos)
Definition: lz4hc.c:498
#define ML_MASK
Definition: lz4hc.c:193
const BYTE * end
Definition: lz4hc.c:247
unsigned char BYTE
Definition: lz4hc.c:142
FORCE_INLINE int LZ4HC_InsertAndFindBestMatch(LZ4HC_Data_Structure *hc4, const BYTE *ip, const BYTE *const matchlimit, const BYTE **matchpos)
Definition: lz4hc.c:430
FORCE_INLINE int LZ4HC_encodeSequence(const BYTE **ip, BYTE **op, const BYTE **anchor, int matchLength, const BYTE *ref, limitedOutput_directive limitedOutputBuffer, BYTE *oend)
Definition: lz4hc.c:559
#define RUN_MASK
Definition: lz4hc.c:195
unsigned int U32
Definition: lz4hc.c:144
#define OPTIMAL_ML
Definition: lz4hc.c:201

◆ LZ4HC_encodeSequence()

FORCE_INLINE int LZ4HC_encodeSequence ( const BYTE **  ip,
BYTE **  op,
const BYTE **  anchor,
int  matchLength,
const BYTE ref,
limitedOutput_directive  limitedOutputBuffer,
BYTE oend 
)

Definition at line 559 of file lz4hc.c.

567 {
568  int length;
569  BYTE* token;
570 
571  // Encode Literal length
572  length = (int)(*ip - *anchor);
573  token = (*op)++;
574  if ((limitedOutputBuffer) && ((*op + length + (2 + 1 + LASTLITERALS) + (length>>8)) > oend)) return 1; // Check output limit
575  if (length>=(int)RUN_MASK) { int len; *token=(RUN_MASK<<ML_BITS); len = length-RUN_MASK; for(; len > 254 ; len-=255) *(*op)++ = 255; *(*op)++ = (BYTE)len; }
576  else *token = (BYTE)(length<<ML_BITS);
577 
578  // Copy Literals
579  LZ4_BLINDCOPY(*anchor, *op, length);
580 
581  // Encode Offset
582  LZ4_WRITE_LITTLEENDIAN_16(*op,(U16)(*ip-ref));
583 
584  // Encode MatchLength
585  length = (int)(matchLength-MINMATCH);
586  if ((limitedOutputBuffer) && (*op + (1 + LASTLITERALS) + (length>>8) > oend)) return 1; // Check output limit
587  if (length>=(int)ML_MASK) { *token+=ML_MASK; length-=ML_MASK; for(; length > 509 ; length-=510) { *(*op)++ = 255; *(*op)++ = 255; } if (length > 254) { length-=255; *(*op)++ = 255; } *(*op)++ = (BYTE)length; }
588  else *token += (BYTE)(length);
589 
590  // Prepare next loop
591  *ip += matchLength;
592  *anchor = *ip;
593 
594  return 0;
595 }
#define LASTLITERALS
Definition: lz4hc.c:198
#define MINMATCH
Definition: lz4hc.c:179
unsigned short U16
Definition: lz4.c:174
#define ML_BITS
Definition: lz4hc.c:192
unsigned char BYTE
Definition: lz4.c:173
#define ML_MASK
Definition: lz4hc.c:193
unsigned char BYTE
Definition: lz4hc.c:142
#define LZ4_WRITE_LITTLEENDIAN_16(p, v)
Definition: lz4hc.c:236
#define RUN_MASK
Definition: lz4hc.c:195
#define LZ4_BLINDCOPY(s, d, l)
Definition: lz4hc.c:258

◆ LZ4HC_Insert()

FORCE_INLINE void LZ4HC_Insert ( LZ4HC_Data_Structure hc4,
const BYTE ip 
)

Definition at line 374 of file lz4hc.c.

375 {
376  U16* chainTable = hc4->chainTable;
377  HTYPE* HashTable = hc4->hashTable;
378  INITBASE(base,hc4->base);
379 
380  while(hc4->nextToUpdate < ip)
381  {
382  const BYTE* const p = hc4->nextToUpdate;
383  size_t delta = (p) - HASH_POINTER(p);
384  if (delta>MAX_DISTANCE) delta = MAX_DISTANCE;
385  DELTANEXT(p) = (U16)delta;
386  HashTable[HASH_VALUE(p)] = (HTYPE)((p) - base);
387  hc4->nextToUpdate++;
388  }
389 }
HTYPE hashTable[HASHTABLESIZE]
Definition: lz4hc.c:248
#define MAX_DISTANCE
Definition: lz4hc.c:184
#define DELTANEXT(p)
Definition: lz4hc.c:262
unsigned short U16
Definition: lz4.c:174
unsigned char BYTE
Definition: lz4.c:173
U16 chainTable[MAXD]
Definition: lz4hc.c:249
#define HASH_VALUE(p)
Definition: lz4hc.c:260
const BYTE * base
Definition: lz4hc.c:246
unsigned short U16
Definition: lz4hc.c:143
const BYTE * nextToUpdate
Definition: lz4hc.c:250
#define INITBASE(b, s)
Definition: lz4hc.c:228
#define HTYPE
Definition: lz4hc.c:227
#define HASH_POINTER(p)
Definition: lz4hc.c:261

◆ LZ4HC_InsertAndFindBestMatch()

FORCE_INLINE int LZ4HC_InsertAndFindBestMatch ( LZ4HC_Data_Structure hc4,
const BYTE ip,
const BYTE *const  matchlimit,
const BYTE **  matchpos 
)

Definition at line 430 of file lz4hc.c.

431 {
432  U16* const chainTable = hc4->chainTable;
433  HTYPE* const HashTable = hc4->hashTable;
434  const BYTE* ref;
435  INITBASE(base,hc4->base);
436  int nbAttempts=MAX_NB_ATTEMPTS;
437  size_t repl=0, ml=0;
438  U16 delta=0; // useless assignment, to remove an uninitialization warning
439 
440  // HC4 match finder
441  LZ4HC_Insert(hc4, ip);
442  ref = HASH_POINTER(ip);
443 
444 #define REPEAT_OPTIMIZATION
445 #ifdef REPEAT_OPTIMIZATION
446  // Detect repetitive sequences of length <= 4
447  if ((U32)(ip-ref) <= 4) // potential repetition
448  {
449  if (A32(ref) == A32(ip)) // confirmed
450  {
451  delta = (U16)(ip-ref);
452  repl = ml = LZ4HC_CommonLength(ip+MINMATCH, ref+MINMATCH, matchlimit) + MINMATCH;
453  *matchpos = ref;
454  }
455  ref = GETNEXT(ref);
456  }
457 #endif
458 
459  while (((U32)(ip-ref) <= MAX_DISTANCE) && (nbAttempts))
460  {
461  nbAttempts--;
462  if (*(ref+ml) == *(ip+ml))
463  if (A32(ref) == A32(ip))
464  {
465  size_t mlt = LZ4HC_CommonLength(ip+MINMATCH, ref+MINMATCH, matchlimit) + MINMATCH;
466  if (mlt > ml) { ml = mlt; *matchpos = ref; }
467  }
468  ref = GETNEXT(ref);
469  }
470 
471 #ifdef REPEAT_OPTIMIZATION
472  // Complete table
473  if (repl)
474  {
475  const BYTE* ptr = ip;
476  const BYTE* end;
477 
478  end = ip + repl - (MINMATCH-1);
479  while(ptr < end-delta)
480  {
481  DELTANEXT(ptr) = delta; // Pre-Load
482  ptr++;
483  }
484  do
485  {
486  DELTANEXT(ptr) = delta;
487  HashTable[HASH_VALUE(ptr)] = (HTYPE)((ptr) - base); // Head of chain
488  ptr++;
489  } while(ptr < end);
490  hc4->nextToUpdate = end;
491  }
492 #endif
493 
494  return (int)ml;
495 }
#define GETNEXT(p)
Definition: lz4hc.c:263
HTYPE hashTable[HASHTABLESIZE]
Definition: lz4hc.c:248
unsigned int U32
Definition: lz4.c:175
#define MINMATCH
Definition: lz4hc.c:179
FORCE_INLINE void LZ4HC_Insert(LZ4HC_Data_Structure *hc4, const BYTE *ip)
Definition: lz4hc.c:374
#define MAX_NB_ATTEMPTS
Definition: lz4hc.c:190
#define MAX_DISTANCE
Definition: lz4hc.c:184
#define DELTANEXT(p)
Definition: lz4hc.c:262
unsigned short U16
Definition: lz4.c:174
unsigned char BYTE
Definition: lz4.c:173
FORCE_INLINE size_t LZ4HC_CommonLength(const BYTE *p1, const BYTE *p2, const BYTE *const matchlimit)
Definition: lz4hc.c:412
U16 chainTable[MAXD]
Definition: lz4hc.c:249
#define HASH_VALUE(p)
Definition: lz4hc.c:260
const BYTE * base
Definition: lz4hc.c:246
unsigned short U16
Definition: lz4hc.c:143
const BYTE * nextToUpdate
Definition: lz4hc.c:250
#define A32(x)
Definition: lz4hc.c:172
#define INITBASE(b, s)
Definition: lz4hc.c:228
#define HTYPE
Definition: lz4hc.c:227
#define HASH_POINTER(p)
Definition: lz4hc.c:261

◆ LZ4HC_InsertAndGetWiderMatch()

FORCE_INLINE int LZ4HC_InsertAndGetWiderMatch ( LZ4HC_Data_Structure hc4,
const BYTE ip,
const BYTE startLimit,
const BYTE matchlimit,
int  longest,
const BYTE **  matchpos,
const BYTE **  startpos 
)

Definition at line 498 of file lz4hc.c.

499 {
500  U16* const chainTable = hc4->chainTable;
501  HTYPE* const HashTable = hc4->hashTable;
502  INITBASE(base,hc4->base);
503  const BYTE* ref;
504  int nbAttempts = MAX_NB_ATTEMPTS;
505  int delta = (int)(ip-startLimit);
506 
507  // First Match
508  LZ4HC_Insert(hc4, ip);
509  ref = HASH_POINTER(ip);
510 
511  while (((U32)(ip-ref) <= MAX_DISTANCE) && (nbAttempts))
512  {
513  nbAttempts--;
514  if (*(startLimit + longest) == *(ref - delta + longest))
515  if (A32(ref) == A32(ip))
516  {
517 #if 1
518  const BYTE* reft = ref+MINMATCH;
519  const BYTE* ipt = ip+MINMATCH;
520  const BYTE* startt = ip;
521 
522  while (ipt<matchlimit-(STEPSIZE-1))
523  {
524  UARCH diff = AARCH(reft) ^ AARCH(ipt);
525  if (!diff) { ipt+=STEPSIZE; reft+=STEPSIZE; continue; }
526  ipt += LZ4_NbCommonBytes(diff);
527  goto _endCount;
528  }
529  if (LZ4_ARCH64) if ((ipt<(matchlimit-3)) && (A32(reft) == A32(ipt))) { ipt+=4; reft+=4; }
530  if ((ipt<(matchlimit-1)) && (A16(reft) == A16(ipt))) { ipt+=2; reft+=2; }
531  if ((ipt<matchlimit) && (*reft == *ipt)) ipt++;
532 _endCount:
533  reft = ref;
534 #else
535  // Easier for code maintenance, but unfortunately slower too
536  const BYTE* startt = ip;
537  const BYTE* reft = ref;
538  const BYTE* ipt = ip + MINMATCH + LZ4HC_CommonLength(ip+MINMATCH, ref+MINMATCH, matchlimit);
539 #endif
540 
541  while ((startt>startLimit) && (reft > hc4->inputBuffer) && (startt[-1] == reft[-1])) {startt--; reft--;}
542 
543  if ((ipt-startt) > longest)
544  {
545  longest = (int)(ipt-startt);
546  *matchpos = reft;
547  *startpos = startt;
548  }
549  }
550  ref = GETNEXT(ref);
551  }
552 
553  return longest;
554 }
#define GETNEXT(p)
Definition: lz4hc.c:263
HTYPE hashTable[HASHTABLESIZE]
Definition: lz4hc.c:248
unsigned int U32
Definition: lz4.c:175
#define MINMATCH
Definition: lz4hc.c:179
#define STEPSIZE
Definition: lz4hc.c:220
FORCE_INLINE void LZ4HC_Insert(LZ4HC_Data_Structure *hc4, const BYTE *ip)
Definition: lz4hc.c:374
#define AARCH
Definition: lz4hc.c:224
#define MAX_NB_ATTEMPTS
Definition: lz4hc.c:190
#define UARCH
Definition: lz4hc.c:223
#define MAX_DISTANCE
Definition: lz4hc.c:184
unsigned short U16
Definition: lz4.c:174
#define A16(x)
Definition: lz4hc.c:173
unsigned char BYTE
Definition: lz4.c:173
FORCE_INLINE size_t LZ4HC_CommonLength(const BYTE *p1, const BYTE *p2, const BYTE *const matchlimit)
Definition: lz4hc.c:412
U16 chainTable[MAXD]
Definition: lz4hc.c:249
const BYTE * base
Definition: lz4hc.c:246
FORCE_INLINE int LZ4_NbCommonBytes(register U32 val)
Definition: lz4hc.c:303
const BYTE * inputBuffer
Definition: lz4hc.c:245
#define A32(x)
Definition: lz4hc.c:172
#define LZ4_ARCH64
Definition: lz4hc.c:54
#define INITBASE(b, s)
Definition: lz4hc.c:228
#define HTYPE
Definition: lz4hc.c:227
#define HASH_POINTER(p)
Definition: lz4hc.c:261