lz4hc.c
Go to the documentation of this file.
1 /*
2  LZ4 HC - High Compression Mode of LZ4
3  Copyright (C) 2011-2015, 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/Cyan4973/lz4
32  - LZ4 public forum : https://groups.google.com/forum/#!forum/lz4c
33 */
34 
35 
36 
37 /**************************************
38 * Tuning Parameter
39 **************************************/
40 static const int LZ4HC_compressionLevel_default = 9;
41 
42 
43 /**************************************
44 * Includes
45 **************************************/
46 #include "lz4hc.h"
47 
48 
49 /**************************************
50 * Local Compiler Options
51 **************************************/
52 #if defined(__GNUC__)
53 # pragma GCC diagnostic ignored "-Wunused-function"
54 #endif
55 
56 #if defined (__clang__)
57 # pragma clang diagnostic ignored "-Wunused-function"
58 #endif
59 
60 
61 /**************************************
62 * Common LZ4 definition
63 **************************************/
64 #define LZ4_COMMONDEFS_ONLY
65 #include "lz4.c"
66 
67 
68 /**************************************
69 * Local Constants
70 **************************************/
71 #define DICTIONARY_LOGSIZE 16
72 #define MAXD (1<<DICTIONARY_LOGSIZE)
73 #define MAXD_MASK (MAXD - 1)
74 
75 #define HASH_LOG (DICTIONARY_LOGSIZE-1)
76 #define HASHTABLESIZE (1 << HASH_LOG)
77 #define HASH_MASK (HASHTABLESIZE - 1)
78 
79 #define OPTIMAL_ML (int)((ML_MASK-1)+MINMATCH)
80 
81 static const int g_maxCompressionLevel = 16;
82 
83 
84 /**************************************
85 * Local Types
86 **************************************/
87 typedef struct
88 {
89  U32 hashTable[HASHTABLESIZE];
90  U16 chainTable[MAXD];
91  const BYTE* end; /* next block here to continue on current prefix */
92  const BYTE* base; /* All index relative to this position */
93  const BYTE* dictBase; /* alternate base for extDict */
94  BYTE* inputBuffer; /* deprecated */
95  U32 dictLimit; /* below that point, need extDict */
96  U32 lowLimit; /* below that point, no more dict */
97  U32 nextToUpdate; /* index from which to continue dictionary update */
100 
101 
102 /**************************************
103 * Local Macros
104 **************************************/
105 #define HASH_FUNCTION(i) (((i) * 2654435761U) >> ((MINMATCH*8)-HASH_LOG))
106 //#define DELTANEXTU16(p) chainTable[(p) & MAXD_MASK] /* flexible, MAXD dependent */
107 #define DELTANEXTU16(p) chainTable[(U16)(p)] /* faster */
108 
109 static U32 LZ4HC_hashPtr(const void* ptr) { return HASH_FUNCTION(LZ4_read32(ptr)); }
110 
111 
112 
113 /**************************************
114 * HC Compression
115 **************************************/
116 static void LZ4HC_init (LZ4HC_Data_Structure* hc4, const BYTE* start)
117 {
118  MEM_INIT((void*)hc4->hashTable, 0, sizeof(hc4->hashTable));
119  MEM_INIT(hc4->chainTable, 0xFF, sizeof(hc4->chainTable));
120  hc4->nextToUpdate = 64 KB;
121  hc4->base = start - 64 KB;
122  hc4->end = start;
123  hc4->dictBase = start - 64 KB;
124  hc4->dictLimit = 64 KB;
125  hc4->lowLimit = 64 KB;
126 }
127 
128 
129 /* Update chains up to ip (excluded) */
131 {
132  U16* chainTable = hc4->chainTable;
133  U32* HashTable = hc4->hashTable;
134  const BYTE* const base = hc4->base;
135  const U32 target = (U32)(ip - base);
136  U32 idx = hc4->nextToUpdate;
137 
138  while(idx < target)
139  {
140  U32 h = LZ4HC_hashPtr(base+idx);
141  size_t delta = idx - HashTable[h];
142  if (delta>MAX_DISTANCE) delta = MAX_DISTANCE;
143  DELTANEXTU16(idx) = (U16)delta;
144  HashTable[h] = idx;
145  idx++;
146  }
147 
148  hc4->nextToUpdate = target;
149 }
150 
151 
152 FORCE_INLINE int LZ4HC_InsertAndFindBestMatch (LZ4HC_Data_Structure* hc4, /* Index table will be updated */
153  const BYTE* ip, const BYTE* const iLimit,
154  const BYTE** matchpos,
155  const int maxNbAttempts)
156 {
157  U16* const chainTable = hc4->chainTable;
158  U32* const HashTable = hc4->hashTable;
159  const BYTE* const base = hc4->base;
160  const BYTE* const dictBase = hc4->dictBase;
161  const U32 dictLimit = hc4->dictLimit;
162  const U32 lowLimit = (hc4->lowLimit + 64 KB > (U32)(ip-base)) ? hc4->lowLimit : (U32)(ip - base) - (64 KB - 1);
163  U32 matchIndex;
164  const BYTE* match;
165  int nbAttempts=maxNbAttempts;
166  size_t ml=0;
167 
168  /* HC4 match finder */
169  LZ4HC_Insert(hc4, ip);
170  matchIndex = HashTable[LZ4HC_hashPtr(ip)];
171 
172  while ((matchIndex>=lowLimit) && (nbAttempts))
173  {
174  nbAttempts--;
175  if (matchIndex >= dictLimit)
176  {
177  match = base + matchIndex;
178  if (*(match+ml) == *(ip+ml)
179  && (LZ4_read32(match) == LZ4_read32(ip)))
180  {
181  size_t mlt = LZ4_count(ip+MINMATCH, match+MINMATCH, iLimit) + MINMATCH;
182  if (mlt > ml) { ml = mlt; *matchpos = match; }
183  }
184  }
185  else
186  {
187  match = dictBase + matchIndex;
188  if (LZ4_read32(match) == LZ4_read32(ip))
189  {
190  size_t mlt;
191  const BYTE* vLimit = ip + (dictLimit - matchIndex);
192  if (vLimit > iLimit) vLimit = iLimit;
193  mlt = LZ4_count(ip+MINMATCH, match+MINMATCH, vLimit) + MINMATCH;
194  if ((ip+mlt == vLimit) && (vLimit < iLimit))
195  mlt += LZ4_count(ip+mlt, base+dictLimit, iLimit);
196  if (mlt > ml) { ml = mlt; *matchpos = base + matchIndex; } /* virtual matchpos */
197  }
198  }
199  matchIndex -= DELTANEXTU16(matchIndex);
200  }
201 
202  return (int)ml;
203 }
204 
205 
208  const BYTE* const ip,
209  const BYTE* const iLowLimit,
210  const BYTE* const iHighLimit,
211  int longest,
212  const BYTE** matchpos,
213  const BYTE** startpos,
214  const int maxNbAttempts)
215 {
216  U16* const chainTable = hc4->chainTable;
217  U32* const HashTable = hc4->hashTable;
218  const BYTE* const base = hc4->base;
219  const U32 dictLimit = hc4->dictLimit;
220  const BYTE* const lowPrefixPtr = base + dictLimit;
221  const U32 lowLimit = (hc4->lowLimit + 64 KB > (U32)(ip-base)) ? hc4->lowLimit : (U32)(ip - base) - (64 KB - 1);
222  const BYTE* const dictBase = hc4->dictBase;
223  U32 matchIndex;
224  int nbAttempts = maxNbAttempts;
225  int delta = (int)(ip-iLowLimit);
226 
227 
228  /* First Match */
229  LZ4HC_Insert(hc4, ip);
230  matchIndex = HashTable[LZ4HC_hashPtr(ip)];
231 
232  while ((matchIndex>=lowLimit) && (nbAttempts))
233  {
234  nbAttempts--;
235  if (matchIndex >= dictLimit)
236  {
237  const BYTE* matchPtr = base + matchIndex;
238  if (*(iLowLimit + longest) == *(matchPtr - delta + longest))
239  if (LZ4_read32(matchPtr) == LZ4_read32(ip))
240  {
241  int mlt = MINMATCH + LZ4_count(ip+MINMATCH, matchPtr+MINMATCH, iHighLimit);
242  int back = 0;
243 
244  while ((ip+back>iLowLimit)
245  && (matchPtr+back > lowPrefixPtr)
246  && (ip[back-1] == matchPtr[back-1]))
247  back--;
248 
249  mlt -= back;
250 
251  if (mlt > longest)
252  {
253  longest = (int)mlt;
254  *matchpos = matchPtr+back;
255  *startpos = ip+back;
256  }
257  }
258  }
259  else
260  {
261  const BYTE* matchPtr = dictBase + matchIndex;
262  if (LZ4_read32(matchPtr) == LZ4_read32(ip))
263  {
264  size_t mlt;
265  int back=0;
266  const BYTE* vLimit = ip + (dictLimit - matchIndex);
267  if (vLimit > iHighLimit) vLimit = iHighLimit;
268  mlt = LZ4_count(ip+MINMATCH, matchPtr+MINMATCH, vLimit) + MINMATCH;
269  if ((ip+mlt == vLimit) && (vLimit < iHighLimit))
270  mlt += LZ4_count(ip+mlt, base+dictLimit, iHighLimit);
271  while ((ip+back > iLowLimit) && (matchIndex+back > lowLimit) && (ip[back-1] == matchPtr[back-1])) back--;
272  mlt -= back;
273  if ((int)mlt > longest) { longest = (int)mlt; *matchpos = base + matchIndex + back; *startpos = ip+back; }
274  }
275  }
276  matchIndex -= DELTANEXTU16(matchIndex);
277  }
278 
279  return longest;
280 }
281 
282 
284 
285 #define LZ4HC_DEBUG 0
286 #if LZ4HC_DEBUG
287 static unsigned debug = 0;
288 #endif
289 
291  const BYTE** ip,
292  BYTE** op,
293  const BYTE** anchor,
294  int matchLength,
295  const BYTE* const match,
296  limitedOutput_directive limitedOutputBuffer,
297  BYTE* oend)
298 {
299  int length;
300  BYTE* token;
301 
302 #if LZ4HC_DEBUG
303  if (debug) printf("literal : %u -- match : %u -- offset : %u\n", (U32)(*ip - *anchor), (U32)matchLength, (U32)(*ip-match));
304 #endif
305 
306  /* Encode Literal length */
307  length = (int)(*ip - *anchor);
308  token = (*op)++;
309  if ((limitedOutputBuffer) && ((*op + (length>>8) + length + (2 + 1 + LASTLITERALS)) > oend)) return 1; /* Check output limit */
310  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; }
311  else *token = (BYTE)(length<<ML_BITS);
312 
313  /* Copy Literals */
314  LZ4_wildCopy(*op, *anchor, (*op) + length);
315  *op += length;
316 
317  /* Encode Offset */
318  LZ4_writeLE16(*op, (U16)(*ip-match)); *op += 2;
319 
320  /* Encode MatchLength */
321  length = (int)(matchLength-MINMATCH);
322  if ((limitedOutputBuffer) && (*op + (length>>8) + (1 + LASTLITERALS) > oend)) return 1; /* Check output limit */
323  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; }
324  else *token += (BYTE)(length);
325 
326  /* Prepare next loop */
327  *ip += matchLength;
328  *anchor = *ip;
329 
330  return 0;
331 }
332 
333 
335  void* ctxvoid,
336  const char* source,
337  char* dest,
338  int inputSize,
339  int maxOutputSize,
340  int compressionLevel,
342  )
343 {
344  LZ4HC_Data_Structure* ctx = (LZ4HC_Data_Structure*) ctxvoid;
345  const BYTE* ip = (const BYTE*) source;
346  const BYTE* anchor = ip;
347  const BYTE* const iend = ip + inputSize;
348  const BYTE* const mflimit = iend - MFLIMIT;
349  const BYTE* const matchlimit = (iend - LASTLITERALS);
350 
351  BYTE* op = (BYTE*) dest;
352  BYTE* const oend = op + maxOutputSize;
353 
354  unsigned maxNbAttempts;
355  int ml, ml2, ml3, ml0;
356  const BYTE* ref=NULL;
357  const BYTE* start2=NULL;
358  const BYTE* ref2=NULL;
359  const BYTE* start3=NULL;
360  const BYTE* ref3=NULL;
361  const BYTE* start0;
362  const BYTE* ref0;
363 
364 
365  /* init */
366  if (compressionLevel > g_maxCompressionLevel) compressionLevel = g_maxCompressionLevel;
367  if (compressionLevel < 1) compressionLevel = LZ4HC_compressionLevel_default;
368  maxNbAttempts = 1 << (compressionLevel-1);
369  ctx->end += inputSize;
370 
371  ip++;
372 
373  /* Main Loop */
374  while (ip < mflimit)
375  {
376  ml = LZ4HC_InsertAndFindBestMatch (ctx, ip, matchlimit, (&ref), maxNbAttempts);
377  if (!ml) { ip++; continue; }
378 
379  /* saved, in case we would skip too much */
380  start0 = ip;
381  ref0 = ref;
382  ml0 = ml;
383 
384 _Search2:
385  if (ip+ml < mflimit)
386  ml2 = LZ4HC_InsertAndGetWiderMatch(ctx, ip + ml - 2, ip + 1, matchlimit, ml, &ref2, &start2, maxNbAttempts);
387  else ml2 = ml;
388 
389  if (ml2 == ml) /* No better match */
390  {
391  if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml, ref, limit, oend)) return 0;
392  continue;
393  }
394 
395  if (start0 < ip)
396  {
397  if (start2 < ip + ml0) /* empirical */
398  {
399  ip = start0;
400  ref = ref0;
401  ml = ml0;
402  }
403  }
404 
405  /* Here, start0==ip */
406  if ((start2 - ip) < 3) /* First Match too small : removed */
407  {
408  ml = ml2;
409  ip = start2;
410  ref =ref2;
411  goto _Search2;
412  }
413 
414 _Search3:
415  /*
416  * Currently we have :
417  * ml2 > ml1, and
418  * ip1+3 <= ip2 (usually < ip1+ml1)
419  */
420  if ((start2 - ip) < OPTIMAL_ML)
421  {
422  int correction;
423  int new_ml = ml;
424  if (new_ml > OPTIMAL_ML) new_ml = OPTIMAL_ML;
425  if (ip+new_ml > start2 + ml2 - MINMATCH) new_ml = (int)(start2 - ip) + ml2 - MINMATCH;
426  correction = new_ml - (int)(start2 - ip);
427  if (correction > 0)
428  {
429  start2 += correction;
430  ref2 += correction;
431  ml2 -= correction;
432  }
433  }
434  /* Now, we have start2 = ip+new_ml, with new_ml = min(ml, OPTIMAL_ML=18) */
435 
436  if (start2 + ml2 < mflimit)
437  ml3 = LZ4HC_InsertAndGetWiderMatch(ctx, start2 + ml2 - 3, start2, matchlimit, ml2, &ref3, &start3, maxNbAttempts);
438  else ml3 = ml2;
439 
440  if (ml3 == ml2) /* No better match : 2 sequences to encode */
441  {
442  /* ip & ref are known; Now for ml */
443  if (start2 < ip+ml) ml = (int)(start2 - ip);
444  /* Now, encode 2 sequences */
445  if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml, ref, limit, oend)) return 0;
446  ip = start2;
447  if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml2, ref2, limit, oend)) return 0;
448  continue;
449  }
450 
451  if (start3 < ip+ml+3) /* Not enough space for match 2 : remove it */
452  {
453  if (start3 >= (ip+ml)) /* can write Seq1 immediately ==> Seq2 is removed, so Seq3 becomes Seq1 */
454  {
455  if (start2 < ip+ml)
456  {
457  int correction = (int)(ip+ml - start2);
458  start2 += correction;
459  ref2 += correction;
460  ml2 -= correction;
461  if (ml2 < MINMATCH)
462  {
463  start2 = start3;
464  ref2 = ref3;
465  ml2 = ml3;
466  }
467  }
468 
469  if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml, ref, limit, oend)) return 0;
470  ip = start3;
471  ref = ref3;
472  ml = ml3;
473 
474  start0 = start2;
475  ref0 = ref2;
476  ml0 = ml2;
477  goto _Search2;
478  }
479 
480  start2 = start3;
481  ref2 = ref3;
482  ml2 = ml3;
483  goto _Search3;
484  }
485 
486  /*
487  * OK, now we have 3 ascending matches; let's write at least the first one
488  * ip & ref are known; Now for ml
489  */
490  if (start2 < ip+ml)
491  {
492  if ((start2 - ip) < (int)ML_MASK)
493  {
494  int correction;
495  if (ml > OPTIMAL_ML) ml = OPTIMAL_ML;
496  if (ip + ml > start2 + ml2 - MINMATCH) ml = (int)(start2 - ip) + ml2 - MINMATCH;
497  correction = ml - (int)(start2 - ip);
498  if (correction > 0)
499  {
500  start2 += correction;
501  ref2 += correction;
502  ml2 -= correction;
503  }
504  }
505  else
506  {
507  ml = (int)(start2 - ip);
508  }
509  }
510  if (LZ4HC_encodeSequence(&ip, &op, &anchor, ml, ref, limit, oend)) return 0;
511 
512  ip = start2;
513  ref = ref2;
514  ml = ml2;
515 
516  start2 = start3;
517  ref2 = ref3;
518  ml2 = ml3;
519 
520  goto _Search3;
521  }
522 
523  /* Encode Last Literals */
524  {
525  int lastRun = (int)(iend - anchor);
526  if ((limit) && (((char*)op - dest) + lastRun + 1 + ((lastRun+255-RUN_MASK)/255) > (U32)maxOutputSize)) return 0; /* Check output limit */
527  if (lastRun>=(int)RUN_MASK) { *op++=(RUN_MASK<<ML_BITS); lastRun-=RUN_MASK; for(; lastRun > 254 ; lastRun-=255) *op++ = 255; *op++ = (BYTE) lastRun; }
528  else *op++ = (BYTE)(lastRun<<ML_BITS);
529  memcpy(op, anchor, iend - anchor);
530  op += iend-anchor;
531  }
532 
533  /* End */
534  return (int) (((char*)op)-dest);
535 }
536 
537 
538 int LZ4_sizeofStateHC(void) { return sizeof(LZ4HC_Data_Structure); }
539 
540 int LZ4_compress_HC_extStateHC (void* state, const char* src, char* dst, int srcSize, int maxDstSize, int compressionLevel)
541 {
542  if (((size_t)(state)&(sizeof(void*)-1)) != 0) return 0; /* Error : state is not aligned for pointers (32 or 64 bits) */
543  LZ4HC_init ((LZ4HC_Data_Structure*)state, (const BYTE*)src);
544  if (maxDstSize < LZ4_compressBound(srcSize))
545  return LZ4HC_compress_generic (state, src, dst, srcSize, maxDstSize, compressionLevel, limitedOutput);
546  else
547  return LZ4HC_compress_generic (state, src, dst, srcSize, maxDstSize, compressionLevel, noLimit);
548 }
549 
550 int LZ4_compress_HC(const char* src, char* dst, int srcSize, int maxDstSize, int compressionLevel)
551 {
553  return LZ4_compress_HC_extStateHC(&state, src, dst, srcSize, maxDstSize, compressionLevel);
554 }
555 
556 
557 
558 /**************************************
559 * Streaming Functions
560 **************************************/
561 /* allocation */
563 int LZ4_freeStreamHC (LZ4_streamHC_t* LZ4_streamHCPtr) { free(LZ4_streamHCPtr); return 0; }
564 
565 
566 /* initialization */
568 {
569  LZ4_STATIC_ASSERT(sizeof(LZ4HC_Data_Structure) <= sizeof(LZ4_streamHC_t)); /* if compilation fails here, LZ4_STREAMHCSIZE must be increased */
570  ((LZ4HC_Data_Structure*)LZ4_streamHCPtr)->base = NULL;
571  ((LZ4HC_Data_Structure*)LZ4_streamHCPtr)->compressionLevel = (unsigned)compressionLevel;
572 }
573 
574 int LZ4_loadDictHC (LZ4_streamHC_t* LZ4_streamHCPtr, const char* dictionary, int dictSize)
575 {
576  LZ4HC_Data_Structure* ctxPtr = (LZ4HC_Data_Structure*) LZ4_streamHCPtr;
577  if (dictSize > 64 KB)
578  {
579  dictionary += dictSize - 64 KB;
580  dictSize = 64 KB;
581  }
582  LZ4HC_init (ctxPtr, (const BYTE*)dictionary);
583  if (dictSize >= 4) LZ4HC_Insert (ctxPtr, (const BYTE*)dictionary +(dictSize-3));
584  ctxPtr->end = (const BYTE*)dictionary + dictSize;
585  return dictSize;
586 }
587 
588 
589 /* compression */
590 
591 static void LZ4HC_setExternalDict(LZ4HC_Data_Structure* ctxPtr, const BYTE* newBlock)
592 {
593  if (ctxPtr->end >= ctxPtr->base + 4)
594  LZ4HC_Insert (ctxPtr, ctxPtr->end-3); /* Referencing remaining dictionary content */
595  /* Only one memory segment for extDict, so any previous extDict is lost at this stage */
596  ctxPtr->lowLimit = ctxPtr->dictLimit;
597  ctxPtr->dictLimit = (U32)(ctxPtr->end - ctxPtr->base);
598  ctxPtr->dictBase = ctxPtr->base;
599  ctxPtr->base = newBlock - ctxPtr->dictLimit;
600  ctxPtr->end = newBlock;
601  ctxPtr->nextToUpdate = ctxPtr->dictLimit; /* match referencing will resume from there */
602 }
603 
605  const char* source, char* dest,
607 {
608  /* auto-init if forgotten */
609  if (ctxPtr->base == NULL)
610  LZ4HC_init (ctxPtr, (const BYTE*) source);
611 
612  /* Check overflow */
613  if ((size_t)(ctxPtr->end - ctxPtr->base) > 2 GB)
614  {
615  size_t dictSize = (size_t)(ctxPtr->end - ctxPtr->base) - ctxPtr->dictLimit;
616  if (dictSize > 64 KB) dictSize = 64 KB;
617 
618  LZ4_loadDictHC((LZ4_streamHC_t*)ctxPtr, (const char*)(ctxPtr->end) - dictSize, (int)dictSize);
619  }
620 
621  /* Check if blocks follow each other */
622  if ((const BYTE*)source != ctxPtr->end)
623  LZ4HC_setExternalDict(ctxPtr, (const BYTE*)source);
624 
625  /* Check overlapping input/dictionary space */
626  {
627  const BYTE* sourceEnd = (const BYTE*) source + inputSize;
628  const BYTE* dictBegin = ctxPtr->dictBase + ctxPtr->lowLimit;
629  const BYTE* dictEnd = ctxPtr->dictBase + ctxPtr->dictLimit;
630  if ((sourceEnd > dictBegin) && ((const BYTE*)source < dictEnd))
631  {
632  if (sourceEnd > dictEnd) sourceEnd = dictEnd;
633  ctxPtr->lowLimit = (U32)(sourceEnd - ctxPtr->dictBase);
634  if (ctxPtr->dictLimit - ctxPtr->lowLimit < 4) ctxPtr->lowLimit = ctxPtr->dictLimit;
635  }
636  }
637 
638  return LZ4HC_compress_generic (ctxPtr, source, dest, inputSize, maxOutputSize, ctxPtr->compressionLevel, limit);
639 }
640 
641 int LZ4_compress_HC_continue (LZ4_streamHC_t* LZ4_streamHCPtr, const char* source, char* dest, int inputSize, int maxOutputSize)
642 {
643  if (maxOutputSize < LZ4_compressBound(inputSize))
644  return LZ4_compressHC_continue_generic ((LZ4HC_Data_Structure*)LZ4_streamHCPtr, source, dest, inputSize, maxOutputSize, limitedOutput);
645  else
646  return LZ4_compressHC_continue_generic ((LZ4HC_Data_Structure*)LZ4_streamHCPtr, source, dest, inputSize, maxOutputSize, noLimit);
647 }
648 
649 
650 /* dictionary saving */
651 
652 int LZ4_saveDictHC (LZ4_streamHC_t* LZ4_streamHCPtr, char* safeBuffer, int dictSize)
653 {
654  LZ4HC_Data_Structure* streamPtr = (LZ4HC_Data_Structure*)LZ4_streamHCPtr;
655  int prefixSize = (int)(streamPtr->end - (streamPtr->base + streamPtr->dictLimit));
656  if (dictSize > 64 KB) dictSize = 64 KB;
657  if (dictSize < 4) dictSize = 0;
658  if (dictSize > prefixSize) dictSize = prefixSize;
659  memmove(safeBuffer, streamPtr->end - dictSize, dictSize);
660  {
661  U32 endIndex = (U32)(streamPtr->end - streamPtr->base);
662  streamPtr->end = (const BYTE*)safeBuffer + dictSize;
663  streamPtr->base = streamPtr->end - endIndex;
664  streamPtr->dictLimit = endIndex - dictSize;
665  streamPtr->lowLimit = endIndex - dictSize;
666  if (streamPtr->nextToUpdate < streamPtr->dictLimit) streamPtr->nextToUpdate = streamPtr->dictLimit;
667  }
668  return dictSize;
669 }
670 
671 
672 /***********************************
673 * Deprecated Functions
674 ***********************************/
675 /* Deprecated compression functions */
676 /* These functions are planned to start generate warnings by r131 approximately */
677 int LZ4_compressHC(const char* src, char* dst, int srcSize) { return LZ4_compress_HC (src, dst, srcSize, LZ4_compressBound(srcSize), 0); }
678 int LZ4_compressHC_limitedOutput(const char* src, char* dst, int srcSize, int maxDstSize) { return LZ4_compress_HC(src, dst, srcSize, maxDstSize, 0); }
679 int LZ4_compressHC2(const char* src, char* dst, int srcSize, int cLevel) { return LZ4_compress_HC (src, dst, srcSize, LZ4_compressBound(srcSize), cLevel); }
680 int LZ4_compressHC2_limitedOutput(const char* src, char* dst, int srcSize, int maxDstSize, int cLevel) { return LZ4_compress_HC(src, dst, srcSize, maxDstSize, cLevel); }
681 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); }
682 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); }
683 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); }
684 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); }
685 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)); }
686 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); }
687 
688 
689 /* Deprecated streaming functions */
690 /* These functions currently generate deprecation warnings */
692 
694 {
695  if ((((size_t)state) & (sizeof(void*)-1)) != 0) return 1; /* Error : pointer is not aligned for pointer (32 or 64 bits) */
696  LZ4HC_init((LZ4HC_Data_Structure*)state, (const BYTE*)inputBuffer);
697  ((LZ4HC_Data_Structure*)state)->inputBuffer = (BYTE*)inputBuffer;
698  return 0;
699 }
700 
702 {
703  void* hc4 = ALLOCATOR(1, sizeof(LZ4HC_Data_Structure));
704  if (hc4 == NULL) return NULL; /* not enough memory */
705  LZ4HC_init ((LZ4HC_Data_Structure*)hc4, (const BYTE*)inputBuffer);
706  ((LZ4HC_Data_Structure*)hc4)->inputBuffer = (BYTE*)inputBuffer;
707  return hc4;
708 }
709 
710 int LZ4_freeHC (void* LZ4HC_Data)
711 {
712  FREEMEM(LZ4HC_Data);
713  return (0);
714 }
715 
716 int LZ4_compressHC2_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize, int compressionLevel)
717 {
718  return LZ4HC_compress_generic (LZ4HC_Data, source, dest, inputSize, 0, compressionLevel, noLimit);
719 }
720 
721 int LZ4_compressHC2_limitedOutput_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize, int maxOutputSize, int compressionLevel)
722 {
723  return LZ4HC_compress_generic (LZ4HC_Data, source, dest, inputSize, maxOutputSize, compressionLevel, limitedOutput);
724 }
725 
726 char* LZ4_slideInputBufferHC(void* LZ4HC_Data)
727 {
728  LZ4HC_Data_Structure* hc4 = (LZ4HC_Data_Structure*)LZ4HC_Data;
729  int dictSize = LZ4_saveDictHC((LZ4_streamHC_t*)LZ4HC_Data, (char*)(hc4->inputBuffer), 64 KB);
730  return (char*)(hc4->inputBuffer + dictSize);
731 }
#define MAXD
Definition: lz4hc.c:72
#define NULL
int LZ4_freeHC(void *LZ4HC_Data)
Definition: lz4hc.c:710
static int LZ4_compressHC_continue_generic(LZ4HC_Data_Structure *ctxPtr, const char *source, char *dest, int inputSize, int maxOutputSize, limitedOutput_directive limit)
Definition: lz4hc.c:604
U32 compressionLevel
Definition: lz4hc.c:98
#define MINMATCH
Definition: lz4.c:219
int LZ4_loadDictHC(LZ4_streamHC_t *LZ4_streamHCPtr, const char *dictionary, int dictSize)
Definition: lz4hc.c:574
unsigned int U32
Definition: lz4.c:125
#define HASH_FUNCTION(i)
Definition: lz4hc.c:105
int LZ4_compressHC2_withStateHC(void *state, const char *src, char *dst, int srcSize, int cLevel)
Definition: lz4hc.c:683
int LZ4_compressHC(const char *src, char *dst, int srcSize)
Definition: lz4hc.c:677
static U32 LZ4HC_hashPtr(const void *ptr)
Definition: lz4hc.c:109
const BYTE * base
Definition: lz4hc.c:92
int LZ4_compressHC_withStateHC(void *state, const char *src, char *dst, int srcSize)
Definition: lz4hc.c:681
#define LASTLITERALS
Definition: lz4.c:222
int LZ4_freeStreamHC(LZ4_streamHC_t *LZ4_streamHCPtr)
Definition: lz4hc.c:563
FORCE_INLINE void LZ4HC_Insert(LZ4HC_Data_Structure *hc4, const BYTE *ip)
Definition: lz4hc.c:130
#define FREEMEM
Definition: lz4.c:107
def match(kptsFrom, kptsTo, scoresFrom, scoresTo, descriptorsFrom, descriptorsTo, imageWidth, imageHeight)
void LZ4_resetStreamHC(LZ4_streamHC_t *LZ4_streamHCPtr, int compressionLevel)
Definition: lz4hc.c:567
char * dst
Definition: lz4.h:354
#define MAX_DISTANCE
Definition: lz4.c:231
const BYTE * end
Definition: lz4hc.c:91
#define DELTANEXTU16(p)
Definition: lz4hc.c:107
int LZ4_compressHC2_limitedOutput_continue(void *LZ4HC_Data, const char *source, char *dest, int inputSize, int maxOutputSize, int compressionLevel)
Definition: lz4hc.c:721
char int int maxDstSize
Definition: lz4.h:354
LZ4_streamHC_t * LZ4_createStreamHC(void)
Definition: lz4hc.c:562
int LZ4_compressHC_limitedOutput_continue(LZ4_streamHC_t *ctx, const char *src, char *dst, int srcSize, int maxDstSize)
Definition: lz4hc.c:686
#define FORCE_INLINE
Definition: lz4.c:87
const char char int int compressionLevel
Definition: lz4hc.h:181
int LZ4_compressHC_limitedOutput(const char *src, char *dst, int srcSize, int maxDstSize)
Definition: lz4hc.c:678
char * inputBuffer
Definition: lz4.h:350
unsigned short U16
Definition: lz4.c:124
limitedOutput_directive
Definition: lz4hc.c:283
unsigned char BYTE
Definition: lz4.c:123
int LZ4_compress_HC(const char *src, char *dst, int srcSize, int maxDstSize, int compressionLevel)
Definition: lz4hc.c:550
static int LZ4HC_compress_generic(void *ctxvoid, const char *source, char *dest, int inputSize, int maxOutputSize, int compressionLevel, limitedOutput_directive limit)
Definition: lz4hc.c:334
#define ML_BITS
Definition: lz4.c:233
#define HASHTABLESIZE
Definition: lz4hc.c:76
int LZ4_compressHC2_limitedOutput_withStateHC(void *state, const char *src, char *dst, int srcSize, int maxDstSize, int cLevel)
Definition: lz4hc.c:684
int LZ4_resetStreamStateHC(void *state, char *inputBuffer)
Definition: lz4hc.c:693
U16 chainTable[MAXD]
Definition: lz4hc.c:90
#define KB
Definition: lz4.c:226
static void LZ4HC_init(LZ4HC_Data_Structure *hc4, const BYTE *start)
Definition: lz4hc.c:116
const char * source
Definition: lz4hc.h:181
Definition: lz4hc.c:283
static void LZ4HC_setExternalDict(LZ4HC_Data_Structure *ctxPtr, const BYTE *newBlock)
Definition: lz4hc.c:591
#define MEM_INIT
Definition: lz4.c:109
int LZ4_sizeofStateHC(void)
Definition: lz4hc.c:538
void * LZ4_createHC(char *inputBuffer)
Definition: lz4hc.c:701
#define ALLOCATOR(n, s)
Definition: lz4.c:106
static void LZ4_writeLE16(void *memPtr, U16 value)
Definition: lz4.c:165
int LZ4_compressHC_continue(LZ4_streamHC_t *ctx, const char *src, char *dst, int srcSize)
Definition: lz4hc.c:685
static void LZ4_wildCopy(void *dstPtr, const void *srcPtr, void *dstEnd)
Definition: lz4.c:207
static U32 LZ4_read32(const void *memPtr)
Definition: lz4.c:179
#define LZ4_STATIC_ASSERT(c)
Definition: lz4.c:242
RecoveryProgressState state
#define ML_MASK
Definition: lz4.c:234
int LZ4_compress_HC_extStateHC(void *state, const char *src, char *dst, int srcSize, int maxDstSize, int compressionLevel)
Definition: lz4hc.c:540
const char char int int maxOutputSize
Definition: lz4hc.h:182
int LZ4_compressHC2_limitedOutput(const char *src, char *dst, int srcSize, int maxDstSize, int cLevel)
Definition: lz4hc.c:680
int LZ4_compressHC2(const char *src, char *dst, int srcSize, int cLevel)
Definition: lz4hc.c:679
int LZ4_compress_HC_continue(LZ4_streamHC_t *LZ4_streamHCPtr, const char *source, char *dest, int inputSize, int maxOutputSize)
Definition: lz4hc.c:641
#define RUN_MASK
Definition: lz4.c:236
int LZ4_sizeofStreamStateHC(void)
Definition: lz4hc.c:691
int LZ4_compressBound(int isize)
Definition: lz4.c:372
const char char * dest
Definition: lz4hc.h:181
#define GB
Definition: lz4.c:228
limitedOutput_directive
Definition: lz4.c:358
int LZ4_compressHC2_continue(void *LZ4HC_Data, const char *source, char *dest, int inputSize, int compressionLevel)
Definition: lz4hc.c:716
BYTE * inputBuffer
Definition: lz4hc.c:94
#define LZ4_STREAMHCSIZE
Definition: lz4hc.h:89
U32 hashTable[HASHTABLESIZE]
Definition: lz4hc.c:89
GLM_FUNC_DECL genType::value_type length(genType const &x)
const char char int inputSize
Definition: lz4hc.h:181
char * LZ4_slideInputBufferHC(void *LZ4HC_Data)
Definition: lz4hc.c:726
FORCE_INLINE int LZ4HC_InsertAndGetWiderMatch(LZ4HC_Data_Structure *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.c:206
FORCE_INLINE int LZ4HC_InsertAndFindBestMatch(LZ4HC_Data_Structure *hc4, const BYTE *ip, const BYTE *const iLimit, const BYTE **matchpos, const int maxNbAttempts)
Definition: lz4hc.c:152
static const int g_maxCompressionLevel
Definition: lz4hc.c:81
int LZ4_compressHC_limitedOutput_withStateHC(void *state, const char *src, char *dst, int srcSize, int maxDstSize)
Definition: lz4hc.c:682
static const int LZ4HC_compressionLevel_default
Definition: lz4hc.c:40
#define OPTIMAL_ML
Definition: lz4hc.c:79
#define MFLIMIT
Definition: lz4.c:223
const BYTE * dictBase
Definition: lz4hc.c:93
static unsigned LZ4_count(const BYTE *pIn, const BYTE *pMatch, const BYTE *pInLimit)
Definition: lz4.c:315
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.c:290
int LZ4_saveDictHC(LZ4_streamHC_t *LZ4_streamHCPtr, char *safeBuffer, int dictSize)
Definition: lz4hc.c:652


rtabmap
Author(s): Mathieu Labbe
autogenerated on Mon Dec 14 2020 03:34:59