lz4hc.cxx
Go to the documentation of this file.
1 /*
2  LZ4 HC - High Compression Mode of LZ4
3  Copyright (C) 2011-2016, Yann Collet.
4 
5  BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
6 
7  Redistribution and use in source and binary forms, with or without
8  modification, are permitted provided that the following conditions are
9  met:
10 
11  * Redistributions of source code must retain the above copyright
12  notice, this list of conditions and the following disclaimer.
13  * Redistributions in binary form must reproduce the above
14  copyright notice, this list of conditions and the following disclaimer
15  in the documentation and/or other materials provided with the
16  distribution.
17 
18  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21  A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22  OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24  LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 
30  You can contact the author at :
31  - LZ4 source repository : https://github.com/lz4/lz4
32  - LZ4 public forum : https://groups.google.com/forum/#!forum/lz4c
33 */
34 /* note : lz4hc is not an independent module, it requires lz4.h/lz4.c for proper compilation */
35 
36 
37 /* *************************************
38 * Tuning Parameter
39 ***************************************/
40 
41 /*!
42  * HEAPMODE :
43  * Select how default compression function will allocate workplace memory,
44  * in stack (0:fastest), or in heap (1:requires malloc()).
45  * Since workplace is rather large, heap mode is recommended.
46  */
47 #ifndef LZ4HC_HEAPMODE
48 # define LZ4HC_HEAPMODE 1
49 #endif
50 
51 
52 /* *************************************
53 * Dependency
54 ***************************************/
55 #include "lz4hc.h"
56 
57 
58 /* *************************************
59 * Local Compiler Options
60 ***************************************/
61 #if defined(__GNUC__)
62 # pragma GCC diagnostic ignored "-Wunused-function"
63 #endif
64 
65 #if defined (__clang__)
66 # pragma clang diagnostic ignored "-Wunused-function"
67 #endif
68 
69 
70 /* *************************************
71 * Common LZ4 definition
72 ***************************************/
73 #define LZ4_COMMONDEFS_ONLY
74 #include "lz4.cxx"
75 
76 
77 /* *************************************
78 * Local Constants
79 ***************************************/
80 #define OPTIMAL_ML (int)((ML_MASK-1)+MINMATCH)
81 
82 
83 /**************************************
84 * Local Macros
85 **************************************/
86 #define HASH_FUNCTION(i) (((i) * 2654435761U) >> ((MINMATCH*8)-LZ4HC_HASH_LOG))
87 #define DELTANEXTMAXD(p) chainTable[(p) & LZ4HC_MAXD_MASK] /* flexible, LZ4HC_MAXD dependent */
88 #define DELTANEXTU16(p) chainTable[(U16)(p)] /* faster */
89 
90 static U32 LZ4HC_hashPtr(const void* ptr) { return HASH_FUNCTION(LZ4_read32(ptr)); }
91 
92 
93 
94 /**************************************
95 * HC Compression
96 **************************************/
97 static void LZ4HC_init (LZ4HC_CCtx_internal* hc4, const BYTE* start)
98 {
99  MEM_INIT((void*)hc4->hashTable, 0, sizeof(hc4->hashTable));
100  MEM_INIT(hc4->chainTable, 0xFF, sizeof(hc4->chainTable));
101  hc4->nextToUpdate = 64 KB;
102  hc4->base = start - 64 KB;
103  hc4->end = start;
104  hc4->dictBase = start - 64 KB;
105  hc4->dictLimit = 64 KB;
106  hc4->lowLimit = 64 KB;
107 }
108 
109 
110 /* Update chains up to ip (excluded) */
112 {
113  U16* const chainTable = hc4->chainTable;
114  U32* const hashTable = hc4->hashTable;
115  const BYTE* const base = hc4->base;
116  U32 const target = (U32)(ip - base);
117  U32 idx = hc4->nextToUpdate;
118 
119  while (idx < target) {
120  U32 const h = LZ4HC_hashPtr(base+idx);
121  size_t delta = idx - hashTable[h];
122  if (delta>MAX_DISTANCE) delta = MAX_DISTANCE;
123  DELTANEXTU16(idx) = (U16)delta;
124  hashTable[h] = idx;
125  idx++;
126  }
127 
128  hc4->nextToUpdate = target;
129 }
130 
131 
132 FORCE_INLINE int LZ4HC_InsertAndFindBestMatch (LZ4HC_CCtx_internal* hc4, /* Index table will be updated */
133  const BYTE* ip, const BYTE* const iLimit,
134  const BYTE** matchpos,
135  const int maxNbAttempts)
136 {
137  U16* const chainTable = hc4->chainTable;
138  U32* const HashTable = hc4->hashTable;
139  const BYTE* const base = hc4->base;
140  const BYTE* const dictBase = hc4->dictBase;
141  const U32 dictLimit = hc4->dictLimit;
142  const U32 lowLimit = (hc4->lowLimit + 64 KB > (U32)(ip-base)) ? hc4->lowLimit : (U32)(ip - base) - (64 KB - 1);
143  U32 matchIndex;
144  int nbAttempts=maxNbAttempts;
145  size_t ml=0;
146 
147  /* HC4 match finder */
148  LZ4HC_Insert(hc4, ip);
149  matchIndex = HashTable[LZ4HC_hashPtr(ip)];
150 
151  while ((matchIndex>=lowLimit) && (nbAttempts)) {
152  nbAttempts--;
153  if (matchIndex >= dictLimit) {
154  const BYTE* const match = base + matchIndex;
155  if (*(match+ml) == *(ip+ml)
156  && (LZ4_read32(match) == LZ4_read32(ip)))
157  {
158  size_t const mlt = LZ4_count(ip+MINMATCH, match+MINMATCH, iLimit) + MINMATCH;
159  if (mlt > ml) { ml = mlt; *matchpos = match; }
160  }
161  } else {
162  const BYTE* const match = dictBase + matchIndex;
163  if (LZ4_read32(match) == LZ4_read32(ip)) {
164  size_t mlt;
165  const BYTE* vLimit = ip + (dictLimit - matchIndex);
166  if (vLimit > iLimit) vLimit = iLimit;
167  mlt = LZ4_count(ip+MINMATCH, match+MINMATCH, vLimit) + MINMATCH;
168  if ((ip+mlt == vLimit) && (vLimit < iLimit))
169  mlt += LZ4_count(ip+mlt, base+dictLimit, iLimit);
170  if (mlt > ml) { ml = mlt; *matchpos = base + matchIndex; } /* virtual matchpos */
171  }
172  }
173  matchIndex -= DELTANEXTU16(matchIndex);
174  }
175 
176  return (int)ml;
177 }
178 
179 
181  LZ4HC_CCtx_internal* hc4,
182  const BYTE* const ip,
183  const BYTE* const iLowLimit,
184  const BYTE* const iHighLimit,
185  int longest,
186  const BYTE** matchpos,
187  const BYTE** startpos,
188  const int maxNbAttempts)
189 {
190  U16* const chainTable = hc4->chainTable;
191  U32* const HashTable = hc4->hashTable;
192  const BYTE* const base = hc4->base;
193  const U32 dictLimit = hc4->dictLimit;
194  const BYTE* const lowPrefixPtr = base + dictLimit;
195  const U32 lowLimit = (hc4->lowLimit + 64 KB > (U32)(ip-base)) ? hc4->lowLimit : (U32)(ip - base) - (64 KB - 1);
196  const BYTE* const dictBase = hc4->dictBase;
197  U32 matchIndex;
198  int nbAttempts = maxNbAttempts;
199  int delta = (int)(ip-iLowLimit);
200 
201 
202  /* First Match */
203  LZ4HC_Insert(hc4, ip);
204  matchIndex = HashTable[LZ4HC_hashPtr(ip)];
205 
206  while ((matchIndex>=lowLimit) && (nbAttempts)) {
207  nbAttempts--;
208  if (matchIndex >= dictLimit) {
209  const BYTE* matchPtr = base + matchIndex;
210  if (*(iLowLimit + longest) == *(matchPtr - delta + longest)) {
211  if (LZ4_read32(matchPtr) == LZ4_read32(ip)) {
212  int mlt = MINMATCH + LZ4_count(ip+MINMATCH, matchPtr+MINMATCH, iHighLimit);
213  int back = 0;
214 
215  while ((ip+back > iLowLimit)
216  && (matchPtr+back > lowPrefixPtr)
217  && (ip[back-1] == matchPtr[back-1]))
218  back--;
219 
220  mlt -= back;
221 
222  if (mlt > longest) {
223  longest = (int)mlt;
224  *matchpos = matchPtr+back;
225  *startpos = ip+back;
226  }
227  }
228  }
229  } else {
230  const BYTE* const matchPtr = dictBase + matchIndex;
231  if (LZ4_read32(matchPtr) == LZ4_read32(ip)) {
232  size_t mlt;
233  int back=0;
234  const BYTE* vLimit = ip + (dictLimit - matchIndex);
235  if (vLimit > iHighLimit) vLimit = iHighLimit;
236  mlt = LZ4_count(ip+MINMATCH, matchPtr+MINMATCH, vLimit) + MINMATCH;
237  if ((ip+mlt == vLimit) && (vLimit < iHighLimit))
238  mlt += LZ4_count(ip+mlt, base+dictLimit, iHighLimit);
239  while ((ip+back > iLowLimit) && (matchIndex+back > lowLimit) && (ip[back-1] == matchPtr[back-1])) back--;
240  mlt -= back;
241  if ((int)mlt > longest) { longest = (int)mlt; *matchpos = base + matchIndex + back; *startpos = ip+back; }
242  }
243  }
244  matchIndex -= DELTANEXTU16(matchIndex);
245  }
246 
247  return longest;
248 }
249 
250 
252 
253 #define LZ4HC_DEBUG 0
254 #if LZ4HC_DEBUG
255 static unsigned debug = 0;
256 #endif
257 
259  const BYTE** ip,
260  BYTE** op,
261  const BYTE** anchor,
262  int matchLength,
263  const BYTE* const match,
264  limitedOutput_directive limitedOutputBuffer,
265  BYTE* oend)
266 {
267  int length;
268  BYTE* token;
269 
270 #if LZ4HC_DEBUG
271  if (debug) printf("literal : %u -- match : %u -- offset : %u\n", (U32)(*ip - *anchor), (U32)matchLength, (U32)(*ip-match));
272 #endif
273 
274  /* Encode Literal length */
275  length = (int)(*ip - *anchor);
276  token = (*op)++;
277  if ((limitedOutputBuffer) && ((*op + (length>>8) + length + (2 + 1 + LASTLITERALS)) > oend)) return 1; /* Check output limit */
278  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; }
279  else *token = (BYTE)(length<<ML_BITS);
280 
281  /* Copy Literals */
282  LZ4_wildCopy(*op, *anchor, (*op) + length);
283  *op += length;
284 
285  /* Encode Offset */
286  LZ4_writeLE16(*op, (U16)(*ip-match)); *op += 2;
287 
288  /* Encode MatchLength */
289  length = (int)(matchLength-MINMATCH);
290  if ((limitedOutputBuffer) && (*op + (length>>8) + (1 + LASTLITERALS) > oend)) return 1; /* Check output limit */
291  if (length>=(int)ML_MASK) {
292  *token += ML_MASK;
293  length -= ML_MASK;
294  for(; length > 509 ; length-=510) { *(*op)++ = 255; *(*op)++ = 255; }
295  if (length > 254) { length-=255; *(*op)++ = 255; }
296  *(*op)++ = (BYTE)length;
297  } else {
298  *token += (BYTE)(length);
299  }
300 
301  /* Prepare next loop */
302  *ip += matchLength;
303  *anchor = *ip;
304 
305  return 0;
306 }
307 
308 #include "lz4opt.h"
309 
311  LZ4HC_CCtx_internal* const ctx,
312  const char* const source,
313  char* const dest,
314  int const inputSize,
315  int const maxOutputSize,
316  unsigned maxNbAttempts,
318  )
319 {
320  const BYTE* ip = (const BYTE*) source;
321  const BYTE* anchor = ip;
322  const BYTE* const iend = ip + inputSize;
323  const BYTE* const mflimit = iend - MFLIMIT;
324  const BYTE* const matchlimit = (iend - LASTLITERALS);
325 
326  BYTE* op = (BYTE*) dest;
327  BYTE* const oend = op + maxOutputSize;
328 
329  int ml, ml2, ml3, ml0;
330  const BYTE* ref = NULL;
331  const BYTE* start2 = NULL;
332  const BYTE* ref2 = NULL;
333  const BYTE* start3 = NULL;
334  const BYTE* ref3 = NULL;
335  const BYTE* start0;
336  const BYTE* ref0;
337 
338  /* init */
339  ctx->end += inputSize;
340 
341  ip++;
342 
343  /* Main Loop */
344  while (ip < mflimit) {
345  ml = LZ4HC_InsertAndFindBestMatch (ctx, ip, matchlimit, (&ref), maxNbAttempts);
346  if (!ml) { ip++; continue; }
347 
348  /* saved, in case we would skip too much */
349  start0 = ip;
350  ref0 = ref;
351  ml0 = ml;
352 
353 _Search2:
354  if (ip+ml < mflimit)
355  ml2 = LZ4HC_InsertAndGetWiderMatch(ctx, ip + ml - 2, ip + 0, matchlimit, ml, &ref2, &start2, maxNbAttempts);
356  else ml2 = ml;
357 
358  if (ml2 == ml) { /* No better match */
359  if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml, ref, limit, oend)) return 0;
360  continue;
361  }
362 
363  if (start0 < ip) {
364  if (start2 < ip + ml0) { /* empirical */
365  ip = start0;
366  ref = ref0;
367  ml = ml0;
368  }
369  }
370 
371  /* Here, start0==ip */
372  if ((start2 - ip) < 3) { /* First Match too small : removed */
373  ml = ml2;
374  ip = start2;
375  ref =ref2;
376  goto _Search2;
377  }
378 
379 _Search3:
380  /*
381  * Currently we have :
382  * ml2 > ml1, and
383  * ip1+3 <= ip2 (usually < ip1+ml1)
384  */
385  if ((start2 - ip) < OPTIMAL_ML) {
386  int correction;
387  int new_ml = ml;
388  if (new_ml > OPTIMAL_ML) new_ml = OPTIMAL_ML;
389  if (ip+new_ml > start2 + ml2 - MINMATCH) new_ml = (int)(start2 - ip) + ml2 - MINMATCH;
390  correction = new_ml - (int)(start2 - ip);
391  if (correction > 0) {
392  start2 += correction;
393  ref2 += correction;
394  ml2 -= correction;
395  }
396  }
397  /* Now, we have start2 = ip+new_ml, with new_ml = min(ml, OPTIMAL_ML=18) */
398 
399  if (start2 + ml2 < mflimit)
400  ml3 = LZ4HC_InsertAndGetWiderMatch(ctx, start2 + ml2 - 3, start2, matchlimit, ml2, &ref3, &start3, maxNbAttempts);
401  else ml3 = ml2;
402 
403  if (ml3 == ml2) { /* No better match : 2 sequences to encode */
404  /* ip & ref are known; Now for ml */
405  if (start2 < ip+ml) ml = (int)(start2 - ip);
406  /* Now, encode 2 sequences */
407  if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml, ref, limit, oend)) return 0;
408  ip = start2;
409  if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml2, ref2, limit, oend)) return 0;
410  continue;
411  }
412 
413  if (start3 < ip+ml+3) { /* Not enough space for match 2 : remove it */
414  if (start3 >= (ip+ml)) { /* can write Seq1 immediately ==> Seq2 is removed, so Seq3 becomes Seq1 */
415  if (start2 < ip+ml) {
416  int correction = (int)(ip+ml - start2);
417  start2 += correction;
418  ref2 += correction;
419  ml2 -= correction;
420  if (ml2 < MINMATCH) {
421  start2 = start3;
422  ref2 = ref3;
423  ml2 = ml3;
424  }
425  }
426 
427  if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml, ref, limit, oend)) return 0;
428  ip = start3;
429  ref = ref3;
430  ml = ml3;
431 
432  start0 = start2;
433  ref0 = ref2;
434  ml0 = ml2;
435  goto _Search2;
436  }
437 
438  start2 = start3;
439  ref2 = ref3;
440  ml2 = ml3;
441  goto _Search3;
442  }
443 
444  /*
445  * OK, now we have 3 ascending matches; let's write at least the first one
446  * ip & ref are known; Now for ml
447  */
448  if (start2 < ip+ml) {
449  if ((start2 - ip) < (int)ML_MASK) {
450  int correction;
451  if (ml > OPTIMAL_ML) ml = OPTIMAL_ML;
452  if (ip + ml > start2 + ml2 - MINMATCH) ml = (int)(start2 - ip) + ml2 - MINMATCH;
453  correction = ml - (int)(start2 - ip);
454  if (correction > 0) {
455  start2 += correction;
456  ref2 += correction;
457  ml2 -= correction;
458  }
459  } else {
460  ml = (int)(start2 - ip);
461  }
462  }
463  if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml, ref, limit, oend)) return 0;
464 
465  ip = start2;
466  ref = ref2;
467  ml = ml2;
468 
469  start2 = start3;
470  ref2 = ref3;
471  ml2 = ml3;
472 
473  goto _Search3;
474  }
475 
476  /* Encode Last Literals */
477  { int lastRun = (int)(iend - anchor);
478  if ((limit) && (((char*)op - dest) + lastRun + 1 + ((lastRun+255-RUN_MASK)/255) > (U32)maxOutputSize)) return 0; /* Check output limit */
479  if (lastRun>=(int)RUN_MASK) { *op++=(RUN_MASK<<ML_BITS); lastRun-=RUN_MASK; for(; lastRun > 254 ; lastRun-=255) *op++ = 255; *op++ = (BYTE) lastRun; }
480  else *op++ = (BYTE)(lastRun<<ML_BITS);
481  memcpy(op, anchor, iend - anchor);
482  op += iend-anchor;
483  }
484 
485  /* End */
486  return (int) (((char*)op)-dest);
487 }
488 
490 {
491  switch (compressionLevel) {
492  default: return 0; /* unused */
493  case 11: return 128;
494  case 12: return 1<<10;
495  }
496 }
497 
499  LZ4HC_CCtx_internal* const ctx,
500  const char* const source,
501  char* const dest,
502  int const inputSize,
503  int const maxOutputSize,
504  int compressionLevel,
506  )
507 {
508  if (compressionLevel < 1) compressionLevel = LZ4HC_CLEVEL_DEFAULT;
509  if (compressionLevel > 9) {
510  switch (compressionLevel) {
511  case 10: return LZ4HC_compress_hashChain(ctx, source, dest, inputSize, maxOutputSize, 1 << (16-1), limit);
512  case 11: ctx->searchNum = LZ4HC_getSearchNum(compressionLevel); return LZ4HC_compress_optimal(ctx, source, dest, inputSize, maxOutputSize, limit, 128, 0);
513  default:
514  case 12: ctx->searchNum = LZ4HC_getSearchNum(compressionLevel); return LZ4HC_compress_optimal(ctx, source, dest, inputSize, maxOutputSize, limit, LZ4_OPT_NUM, 1);
515  }
516  }
517  return LZ4HC_compress_hashChain(ctx, source, dest, inputSize, maxOutputSize, 1 << (compressionLevel-1), limit);
518 }
519 
520 
521 int LZ4_sizeofStateHC(void) { return sizeof(LZ4_streamHC_t); }
522 
523 int LZ4_compress_HC_extStateHC (void* state, const char* src, char* dst, int srcSize, int maxDstSize, int compressionLevel)
524 {
525  LZ4HC_CCtx_internal* ctx = &((LZ4_streamHC_t*)state)->internal_donotuse;
526  if (((size_t)(state)&(sizeof(void*)-1)) != 0) return 0; /* Error : state is not aligned for pointers (32 or 64 bits) */
527  LZ4HC_init (ctx, (const BYTE*)src);
528  if (maxDstSize < LZ4_compressBound(srcSize))
529  return LZ4HC_compress_generic (ctx, src, dst, srcSize, maxDstSize, compressionLevel, limitedOutput);
530  else
531  return LZ4HC_compress_generic (ctx, src, dst, srcSize, maxDstSize, compressionLevel, noLimit);
532 }
533 
534 int LZ4_compress_HC(const char* src, char* dst, int srcSize, int maxDstSize, int compressionLevel)
535 {
536 #if defined(LZ4HC_HEAPMODE) && LZ4HC_HEAPMODE==1
537  LZ4_streamHC_t* const statePtr = (LZ4_streamHC_t*)malloc(sizeof(LZ4_streamHC_t));
538 #else
540  LZ4_streamHC_t* const statePtr = &state;
541 #endif
542  int const cSize = LZ4_compress_HC_extStateHC(statePtr, src, dst, srcSize, maxDstSize, compressionLevel);
543 #if defined(LZ4HC_HEAPMODE) && LZ4HC_HEAPMODE==1
544  free(statePtr);
545 #endif
546  return cSize;
547 }
548 
549 
550 
551 /**************************************
552 * Streaming Functions
553 **************************************/
554 /* allocation */
556 int LZ4_freeStreamHC (LZ4_streamHC_t* LZ4_streamHCPtr) { free(LZ4_streamHCPtr); return 0; }
557 
558 
559 /* initialization */
561 {
562  LZ4_STATIC_ASSERT(sizeof(LZ4HC_CCtx_internal) <= sizeof(size_t) * LZ4_STREAMHCSIZE_SIZET); /* if compilation fails here, LZ4_STREAMHCSIZE must be increased */
563  LZ4_streamHCPtr->internal_donotuse.base = NULL;
564  LZ4_streamHCPtr->internal_donotuse.compressionLevel = (unsigned)compressionLevel;
565  LZ4_streamHCPtr->internal_donotuse.searchNum = LZ4HC_getSearchNum(compressionLevel);
566 }
567 
568 int LZ4_loadDictHC (LZ4_streamHC_t* LZ4_streamHCPtr, const char* dictionary, int dictSize)
569 {
570  LZ4HC_CCtx_internal* ctxPtr = &LZ4_streamHCPtr->internal_donotuse;
571  if (dictSize > 64 KB) {
572  dictionary += dictSize - 64 KB;
573  dictSize = 64 KB;
574  }
575  LZ4HC_init (ctxPtr, (const BYTE*)dictionary);
576  ctxPtr->end = (const BYTE*)dictionary + dictSize;
577  if (ctxPtr->compressionLevel >= LZ4HC_CLEVEL_OPT_MIN)
578  LZ4HC_updateBinTree(ctxPtr, ctxPtr->end - MFLIMIT, ctxPtr->end - LASTLITERALS);
579  else
580  if (dictSize >= 4) LZ4HC_Insert (ctxPtr, ctxPtr->end-3);
581  return dictSize;
582 }
583 
584 
585 /* compression */
586 
587 static void LZ4HC_setExternalDict(LZ4HC_CCtx_internal* ctxPtr, const BYTE* newBlock)
588 {
589  if (ctxPtr->compressionLevel >= LZ4HC_CLEVEL_OPT_MIN)
590  LZ4HC_updateBinTree(ctxPtr, ctxPtr->end - MFLIMIT, ctxPtr->end - LASTLITERALS);
591  else
592  if (ctxPtr->end >= ctxPtr->base + 4) LZ4HC_Insert (ctxPtr, ctxPtr->end-3); /* Referencing remaining dictionary content */
593 
594  /* Only one memory segment for extDict, so any previous extDict is lost at this stage */
595  ctxPtr->lowLimit = ctxPtr->dictLimit;
596  ctxPtr->dictLimit = (U32)(ctxPtr->end - ctxPtr->base);
597  ctxPtr->dictBase = ctxPtr->base;
598  ctxPtr->base = newBlock - ctxPtr->dictLimit;
599  ctxPtr->end = newBlock;
600  ctxPtr->nextToUpdate = ctxPtr->dictLimit; /* match referencing will resume from there */
601 }
602 
603 static int LZ4_compressHC_continue_generic (LZ4_streamHC_t* LZ4_streamHCPtr,
604  const char* source, char* dest,
606 {
607  LZ4HC_CCtx_internal* ctxPtr = &LZ4_streamHCPtr->internal_donotuse;
608  /* auto-init if forgotten */
609  if (ctxPtr->base == NULL) LZ4HC_init (ctxPtr, (const BYTE*) source);
610 
611  /* Check overflow */
612  if ((size_t)(ctxPtr->end - ctxPtr->base) > 2 GB) {
613  size_t dictSize = (size_t)(ctxPtr->end - ctxPtr->base) - ctxPtr->dictLimit;
614  if (dictSize > 64 KB) dictSize = 64 KB;
615  LZ4_loadDictHC(LZ4_streamHCPtr, (const char*)(ctxPtr->end) - dictSize, (int)dictSize);
616  }
617 
618  /* Check if blocks follow each other */
619  if ((const BYTE*)source != ctxPtr->end) LZ4HC_setExternalDict(ctxPtr, (const BYTE*)source);
620 
621  /* Check overlapping input/dictionary space */
622  { const BYTE* sourceEnd = (const BYTE*) source + inputSize;
623  const BYTE* const dictBegin = ctxPtr->dictBase + ctxPtr->lowLimit;
624  const BYTE* const dictEnd = ctxPtr->dictBase + ctxPtr->dictLimit;
625  if ((sourceEnd > dictBegin) && ((const BYTE*)source < dictEnd)) {
626  if (sourceEnd > dictEnd) sourceEnd = dictEnd;
627  ctxPtr->lowLimit = (U32)(sourceEnd - ctxPtr->dictBase);
628  if (ctxPtr->dictLimit - ctxPtr->lowLimit < 4) ctxPtr->lowLimit = ctxPtr->dictLimit;
629  }
630  }
631 
632  return LZ4HC_compress_generic (ctxPtr, source, dest, inputSize, maxOutputSize, ctxPtr->compressionLevel, limit);
633 }
634 
635 int LZ4_compress_HC_continue (LZ4_streamHC_t* LZ4_streamHCPtr, const char* source, char* dest, int inputSize, int maxOutputSize)
636 {
637  if (maxOutputSize < LZ4_compressBound(inputSize))
638  return LZ4_compressHC_continue_generic (LZ4_streamHCPtr, source, dest, inputSize, maxOutputSize, limitedOutput);
639  else
640  return LZ4_compressHC_continue_generic (LZ4_streamHCPtr, source, dest, inputSize, maxOutputSize, noLimit);
641 }
642 
643 
644 /* dictionary saving */
645 
646 int LZ4_saveDictHC (LZ4_streamHC_t* LZ4_streamHCPtr, char* safeBuffer, int dictSize)
647 {
648  LZ4HC_CCtx_internal* const streamPtr = &LZ4_streamHCPtr->internal_donotuse;
649  int const prefixSize = (int)(streamPtr->end - (streamPtr->base + streamPtr->dictLimit));
650  if (dictSize > 64 KB) dictSize = 64 KB;
651  if (dictSize < 4) dictSize = 0;
652  if (dictSize > prefixSize) dictSize = prefixSize;
653  memmove(safeBuffer, streamPtr->end - dictSize, dictSize);
654  { U32 const endIndex = (U32)(streamPtr->end - streamPtr->base);
655  streamPtr->end = (const BYTE*)safeBuffer + dictSize;
656  streamPtr->base = streamPtr->end - endIndex;
657  streamPtr->dictLimit = endIndex - dictSize;
658  streamPtr->lowLimit = endIndex - dictSize;
659  if (streamPtr->nextToUpdate < streamPtr->dictLimit) streamPtr->nextToUpdate = streamPtr->dictLimit;
660  }
661  return dictSize;
662 }
663 
664 
665 /***********************************
666 * Deprecated Functions
667 ***********************************/
668 /* These functions currently generate deprecation warnings */
669 /* Deprecated compression functions */
670 int LZ4_compressHC(const char* src, char* dst, int srcSize) { return LZ4_compress_HC (src, dst, srcSize, LZ4_compressBound(srcSize), 0); }
671 int LZ4_compressHC_limitedOutput(const char* src, char* dst, int srcSize, int maxDstSize) { return LZ4_compress_HC(src, dst, srcSize, maxDstSize, 0); }
672 int LZ4_compressHC2(const char* src, char* dst, int srcSize, int cLevel) { return LZ4_compress_HC (src, dst, srcSize, LZ4_compressBound(srcSize), cLevel); }
673 int LZ4_compressHC2_limitedOutput(const char* src, char* dst, int srcSize, int maxDstSize, int cLevel) { return LZ4_compress_HC(src, dst, srcSize, maxDstSize, cLevel); }
674 int LZ4_compressHC_withStateHC (void* state, const char* src, char* dst, int srcSize) { return LZ4_compress_HC_extStateHC (state, src, dst, srcSize, LZ4_compressBound(srcSize), 0); }
675 int LZ4_compressHC_limitedOutput_withStateHC (void* state, const char* src, char* dst, int srcSize, int maxDstSize) { return LZ4_compress_HC_extStateHC (state, src, dst, srcSize, maxDstSize, 0); }
676 int LZ4_compressHC2_withStateHC (void* state, const char* src, char* dst, int srcSize, int cLevel) { return LZ4_compress_HC_extStateHC(state, src, dst, srcSize, LZ4_compressBound(srcSize), cLevel); }
677 int LZ4_compressHC2_limitedOutput_withStateHC (void* state, const char* src, char* dst, int srcSize, int maxDstSize, int cLevel) { return LZ4_compress_HC_extStateHC(state, src, dst, srcSize, maxDstSize, cLevel); }
678 int LZ4_compressHC_continue (LZ4_streamHC_t* ctx, const char* src, char* dst, int srcSize) { return LZ4_compress_HC_continue (ctx, src, dst, srcSize, LZ4_compressBound(srcSize)); }
679 int LZ4_compressHC_limitedOutput_continue (LZ4_streamHC_t* ctx, const char* src, char* dst, int srcSize, int maxDstSize) { return LZ4_compress_HC_continue (ctx, src, dst, srcSize, maxDstSize); }
680 
681 
682 /* Deprecated streaming functions */
684 
686 {
687  LZ4HC_CCtx_internal *ctx = &((LZ4_streamHC_t*)state)->internal_donotuse;
688  if ((((size_t)state) & (sizeof(void*)-1)) != 0) return 1; /* Error : pointer is not aligned for pointer (32 or 64 bits) */
689  LZ4HC_init(ctx, (const BYTE*)inputBuffer);
690  ctx->inputBuffer = (BYTE*)inputBuffer;
691  return 0;
692 }
693 
695 {
697  if (hc4 == NULL) return NULL; /* not enough memory */
698  LZ4HC_init (&hc4->internal_donotuse, (const BYTE*)inputBuffer);
699  hc4->internal_donotuse.inputBuffer = (BYTE*)inputBuffer;
700  return hc4;
701 }
702 
703 int LZ4_freeHC (void* LZ4HC_Data) { FREEMEM(LZ4HC_Data); return 0; }
704 
705 int LZ4_compressHC2_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize, int compressionLevel)
706 {
707  return LZ4HC_compress_generic (&((LZ4_streamHC_t*)LZ4HC_Data)->internal_donotuse, source, dest, inputSize, 0, compressionLevel, noLimit);
708 }
709 
710 int LZ4_compressHC2_limitedOutput_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize, int maxOutputSize, int compressionLevel)
711 {
712  return LZ4HC_compress_generic (&((LZ4_streamHC_t*)LZ4HC_Data)->internal_donotuse, source, dest, inputSize, maxOutputSize, compressionLevel, limitedOutput);
713 }
714 
715 char* LZ4_slideInputBufferHC(void* LZ4HC_Data)
716 {
717  LZ4HC_CCtx_internal* const hc4 = &((LZ4_streamHC_t*)LZ4HC_Data)->internal_donotuse;
718  int const dictSize = LZ4_saveDictHC((LZ4_streamHC_t*)LZ4HC_Data, (char*)(hc4->inputBuffer), 64 KB);
719  return (char*)(hc4->inputBuffer + dictSize);
720 }
int LZ4_compressHC(const char *src, char *dst, int srcSize)
Definition: lz4hc.cxx:670
const XML_Char int len
Definition: expat.h:262
unsigned char * inputBuffer
Definition: lz4hc.h:170
char int int maxOutputSize
Definition: lz4.h:435
#define MEM_INIT
Definition: lz4.cxx:131
int LZ4_sizeofStreamStateHC(void)
Definition: lz4hc.cxx:683
static void LZ4HC_init(LZ4HC_CCtx_internal *hc4, const BYTE *start)
Definition: lz4hc.cxx:97
#define ML_BITS
Definition: lz4.cxx:277
#define LZ4HC_CLEVEL_DEFAULT
Definition: lz4hc.h:48
const XML_Char * target
Definition: expat.h:268
#define MINMATCH
Definition: lz4.cxx:263
int LZ4_compressHC2(const char *src, char *dst, int srcSize, int cLevel)
Definition: lz4hc.cxx:672
unsigned int dictLimit
Definition: lz4hc.h:171
limitedOutput_directive
Definition: lz4hc.cxx:251
double delta
Definition: runWimpSim.h:98
int LZ4_sizeofStateHC(void)
Definition: lz4hc.cxx:521
unsigned int U32
Definition: lz4.cxx:148
LZ4_streamHC_t * LZ4_createStreamHC(void)
Definition: lz4hc.cxx:555
#define LZ4HC_CLEVEL_OPT_MIN
Definition: lz4hc.h:49
static void LZ4_writeLE16(void *memPtr, U16 value)
Definition: lz4.cxx:233
limitedOutput_directive
Definition: lz4.cxx:380
#define FREEMEM
Definition: lz4.cxx:129
#define ALLOCATOR(n, s)
Definition: lz4.cxx:128
static unsigned LZ4_count(const BYTE *pIn, const BYTE *pMatch, const BYTE *pInLimit)
Definition: lz4.cxx:351
static int LZ4HC_compress_optimal(LZ4HC_CCtx_internal *ctx, const char *const source, char *dest, int inputSize, int maxOutputSize, limitedOutput_directive limit, const size_t sufficient_len, const int fullUpdate)
Definition: lz4opt.h:205
char * dst
Definition: lz4.h:458
LZ4HC_CCtx_internal internal_donotuse
Definition: lz4hc.h:184
int LZ4_compressHC2_withStateHC(void *state, const char *src, char *dst, int srcSize, int cLevel)
Definition: lz4hc.cxx:676
#define LZ4_OPT_NUM
Definition: lz4opt.h:36
static U32 LZ4_read32(const void *memPtr)
Definition: lz4.cxx:200
union LZ4_streamHC_u LZ4_streamHC_t
Definition: lz4hc.h:87
TString ip
Definition: loadincs.C:5
int LZ4_compress_HC_continue(LZ4_streamHC_t *LZ4_streamHCPtr, const char *source, char *dest, int inputSize, int maxOutputSize)
Definition: lz4hc.cxx:635
int LZ4_compressHC_continue(LZ4_streamHC_t *ctx, const char *src, char *dst, int srcSize)
Definition: lz4hc.cxx:678
#define LASTLITERALS
Definition: lz4.cxx:266
int LZ4_resetStreamStateHC(void *state, char *inputBuffer)
Definition: lz4hc.cxx:685
char int int maxDstSize
Definition: lz4.h:458
static int LZ4HC_compress_generic(LZ4HC_CCtx_internal *const ctx, const char *const source, char *const dest, int const inputSize, int const maxOutputSize, int compressionLevel, limitedOutput_directive limit)
Definition: lz4hc.cxx:498
const unsigned char * dictBase
Definition: lz4hc.h:169
int LZ4_compressHC_limitedOutput_withStateHC(void *state, const char *src, char *dst, int srcSize, int maxDstSize)
Definition: lz4hc.cxx:675
int LZ4_compressHC2_continue(void *LZ4HC_Data, const char *source, char *dest, int inputSize, int compressionLevel)
Definition: lz4hc.cxx:705
const XML_Char int const XML_Char int const XML_Char * base
Definition: expat.h:331
#define MAX_DISTANCE
Definition: lz4.cxx:275
FORCE_INLINE int LZ4HC_InsertAndFindBestMatch(LZ4HC_CCtx_internal *hc4, const BYTE *ip, const BYTE *const iLimit, const BYTE **matchpos, const int maxNbAttempts)
Definition: lz4hc.cxx:132
static U32 LZ4HC_hashPtr(const void *ptr)
Definition: lz4hc.cxx:90
static int LZ4HC_compress_hashChain(LZ4HC_CCtx_internal *const ctx, const char *const source, char *const dest, int const inputSize, int const maxOutputSize, unsigned maxNbAttempts, limitedOutput_directive limit)
Definition: lz4hc.cxx:310
static int LZ4_compressHC_continue_generic(LZ4_streamHC_t *LZ4_streamHCPtr, const char *source, char *dest, int inputSize, int maxOutputSize, limitedOutput_directive limit)
Definition: lz4hc.cxx:603
unsigned int hashTable[LZ4HC_HASHTABLESIZE]
Definition: lz4hc.h:165
#define OPTIMAL_ML
Definition: lz4hc.cxx:80
char int int compressionLevel
Definition: lz4hc.h:205
char * inputBuffer
Definition: lz4.h:454
unsigned int lowLimit
Definition: lz4hc.h:172
char * LZ4_slideInputBufferHC(void *LZ4HC_Data)
Definition: lz4hc.cxx:715
#define DELTANEXTU16(p)
Definition: lz4hc.cxx:88
FORCE_INLINE void LZ4HC_updateBinTree(LZ4HC_CCtx_internal *ctx, const BYTE *const ip, const BYTE *const iHighLimit)
Definition: lz4opt.h:170
int LZ4_freeStreamHC(LZ4_streamHC_t *LZ4_streamHCPtr)
Definition: lz4hc.cxx:556
length
Definition: demo0.py:21
#define HASH_FUNCTION(i)
Definition: lz4hc.cxx:86
#define RUN_MASK
Definition: lz4.cxx:280
unsigned int compressionLevel
Definition: lz4hc.h:175
FORCE_INLINE int LZ4HC_encodeSequence(const BYTE **ip, BYTE **op, const BYTE **anchor, int matchLength, const BYTE *const match, limitedOutput_directive limitedOutputBuffer, BYTE *oend)
Definition: lz4hc.cxx:258
unsigned int nextToUpdate
Definition: lz4hc.h:173
printf("%d Experimental points found\n", nlines)
unsigned char BYTE
Definition: lz4.cxx:146
static void LZ4_wildCopy(void *dstPtr, const void *srcPtr, void *dstEnd)
Definition: lz4.cxx:250
#define FORCE_INLINE
Definition: lz4.cxx:110
int LZ4_compress_HC_extStateHC(void *state, const char *src, char *dst, int srcSize, int maxDstSize, int compressionLevel)
Definition: lz4hc.cxx:523
void * LZ4_createHC(char *inputBuffer)
Definition: lz4hc.cxx:694
void LZ4_resetStreamHC(LZ4_streamHC_t *LZ4_streamHCPtr, int compressionLevel)
Definition: lz4hc.cxx:560
#define ML_MASK
Definition: lz4.cxx:278
int LZ4_loadDictHC(LZ4_streamHC_t *LZ4_streamHCPtr, const char *dictionary, int dictSize)
Definition: lz4hc.cxx:568
int LZ4_compressHC_withStateHC(void *state, const char *src, char *dst, int srcSize)
Definition: lz4hc.cxx:674
const char * source
Definition: lz4.h:436
unsigned short U16
Definition: lz4.cxx:147
unsigned int searchNum
Definition: lz4hc.h:174
static void LZ4HC_setExternalDict(LZ4HC_CCtx_internal *ctxPtr, const BYTE *newBlock)
Definition: lz4hc.cxx:587
static int LZ4HC_getSearchNum(int compressionLevel)
Definition: lz4hc.cxx:489
const unsigned char * base
Definition: lz4hc.h:168
int LZ4_compress_HC(const char *src, char *dst, int srcSize, int maxDstSize, int compressionLevel)
Definition: lz4hc.cxx:534
FORCE_INLINE void LZ4HC_Insert(LZ4HC_CCtx_internal *hc4, const BYTE *ip)
Definition: lz4hc.cxx:111
#define GB
Definition: lz4.cxx:272
#define LZ4_STATIC_ASSERT(c)
Definition: lz4.cxx:286
const char char int inputSize
Definition: lz4.h:436
#define MFLIMIT
Definition: lz4.cxx:267
int LZ4_compressHC2_limitedOutput(const char *src, char *dst, int srcSize, int maxDstSize, int cLevel)
Definition: lz4hc.cxx:673
int LZ4_compressBound(int isize)
Definition: lz4.cxx:395
FORCE_INLINE int LZ4HC_InsertAndGetWiderMatch(LZ4HC_CCtx_internal *hc4, const BYTE *const ip, const BYTE *const iLowLimit, const BYTE *const iHighLimit, int longest, const BYTE **matchpos, const BYTE **startpos, const int maxNbAttempts)
Definition: lz4hc.cxx:180
#define LZ4_STREAMHCSIZE_SIZET
Definition: lz4hc.h:181
int LZ4_compressHC_limitedOutput(const char *src, char *dst, int srcSize, int maxDstSize)
Definition: lz4hc.cxx:671
#define LZ4_STREAMHCSIZE
Definition: lz4hc.h:180
int LZ4_saveDictHC(LZ4_streamHC_t *LZ4_streamHCPtr, char *safeBuffer, int dictSize)
Definition: lz4hc.cxx:646
#define KB
Definition: lz4.cxx:270
int LZ4_compressHC_limitedOutput_continue(LZ4_streamHC_t *ctx, const char *src, char *dst, int srcSize, int maxDstSize)
Definition: lz4hc.cxx:679
::xsd::cxx::tree::token< char, normalized_string > token
Definition: Database.h:156
unsigned short chainTable[LZ4HC_MAXD]
Definition: lz4hc.h:166
int LZ4_freeHC(void *LZ4HC_Data)
Definition: lz4hc.cxx:703
int LZ4_compressHC2_limitedOutput_withStateHC(void *state, const char *src, char *dst, int srcSize, int maxDstSize, int cLevel)
Definition: lz4hc.cxx:677
int LZ4_compressHC2_limitedOutput_continue(void *LZ4HC_Data, const char *source, char *dest, int inputSize, int maxOutputSize, int compressionLevel)
Definition: lz4hc.cxx:710
const unsigned char * end
Definition: lz4hc.h:167