lz4opt.h
Go to the documentation of this file.
1 /*
2  lz4opt.h - Optimal Mode of LZ4
3  Copyright (C) 2015-2017, Przemyslaw Skibinski <inikep@gmail.com>
4  Note : this file is intended to be included within lz4hc.c
5 
6  BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
7 
8  Redistribution and use in source and binary forms, with or without
9  modification, are permitted provided that the following conditions are
10  met:
11 
12  * Redistributions of source code must retain the above copyright
13  notice, this list of conditions and the following disclaimer.
14  * Redistributions in binary form must reproduce the above
15  copyright notice, this list of conditions and the following disclaimer
16  in the documentation and/or other materials provided with the
17  distribution.
18 
19  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22  A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23  OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25  LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 
31  You can contact the author at :
32  - LZ4 source repository : https://github.com/lz4/lz4
33  - LZ4 public forum : https://groups.google.com/forum/#!forum/lz4c
34 */
35 
36 #define LZ4_OPT_NUM (1<<12)
37 
38 
39 typedef struct {
40  int off;
41  int len;
43 
44 typedef struct {
45  int price;
46  int off;
47  int mlen;
48  int litlen;
50 
51 
52 /* price in bytes */
53 FORCE_INLINE size_t LZ4HC_literalsPrice(size_t litlen)
54 {
55  size_t price = litlen;
56  if (litlen >= (size_t)RUN_MASK)
57  price += 1 + (litlen-RUN_MASK)/255;
58  return price;
59 }
60 
61 
62 /* requires mlen >= MINMATCH */
63 FORCE_INLINE size_t LZ4HC_sequencePrice(size_t litlen, size_t mlen)
64 {
65  size_t price = 2 + 1; /* 16-bit offset + token */
66 
67  price += LZ4HC_literalsPrice(litlen);
68 
69  if (mlen >= (size_t)(ML_MASK+MINMATCH))
70  price+= 1 + (mlen-(ML_MASK+MINMATCH))/255;
71 
72  return price;
73 }
74 
75 
76 /*-*************************************
77 * Binary Tree search
78 ***************************************/
81  const BYTE* const ip,
82  const BYTE* const iHighLimit,
83  size_t best_mlen,
85  int* matchNum)
86 {
87  U16* const chainTable = ctx->chainTable;
88  U32* const HashTable = ctx->hashTable;
89  const BYTE* const base = ctx->base;
90  const U32 dictLimit = ctx->dictLimit;
91  const U32 current = (U32)(ip - base);
92  const U32 lowLimit = (ctx->lowLimit + MAX_DISTANCE > current) ? ctx->lowLimit : current - (MAX_DISTANCE - 1);
93  const BYTE* const dictBase = ctx->dictBase;
94  const BYTE* match;
95  int nbAttempts = ctx->searchNum;
96  int mnum = 0;
97  U16 *ptr0, *ptr1, delta0, delta1;
98  U32 matchIndex;
99  size_t matchLength = 0;
100  U32* HashPos;
101 
102  if (ip + MINMATCH > iHighLimit) return 1;
103 
104  /* HC4 match finder */
105  HashPos = &HashTable[LZ4HC_hashPtr(ip)];
106  matchIndex = *HashPos;
107  *HashPos = current;
108 
109  ptr0 = &DELTANEXTMAXD(current*2+1);
110  ptr1 = &DELTANEXTMAXD(current*2);
111  delta0 = delta1 = (U16)(current - matchIndex);
112 
113  while ((matchIndex < current) && (matchIndex>=lowLimit) && (nbAttempts)) {
114  nbAttempts--;
115  if (matchIndex >= dictLimit) {
116  match = base + matchIndex;
117  matchLength = LZ4_count(ip, match, iHighLimit);
118  } else {
119  const BYTE* vLimit = ip + (dictLimit - matchIndex);
120  match = dictBase + matchIndex;
121  if (vLimit > iHighLimit) vLimit = iHighLimit;
122  matchLength = LZ4_count(ip, match, vLimit);
123  if ((ip+matchLength == vLimit) && (vLimit < iHighLimit))
124  matchLength += LZ4_count(ip+matchLength, base+dictLimit, iHighLimit);
125  if (matchIndex+matchLength >= dictLimit)
126  match = base + matchIndex; /* to prepare for next usage of match[matchLength] */
127  }
128 
129  if (matchLength > best_mlen) {
130  best_mlen = matchLength;
131  if (matches) {
132  if (matchIndex >= dictLimit)
133  matches[mnum].off = (int)(ip - match);
134  else
135  matches[mnum].off = (int)(ip - (base + matchIndex)); /* virtual matchpos */
136  matches[mnum].len = (int)matchLength;
137  mnum++;
138  }
139  if (best_mlen > LZ4_OPT_NUM) break;
140  }
141 
142  if (ip+matchLength >= iHighLimit) /* equal : no way to know if inf or sup */
143  break; /* drop , to guarantee consistency ; miss a bit of compression, but other solutions can corrupt the tree */
144 
145  DEBUGLOG(6, "ip :%016llX", (U64)ip);
146  DEBUGLOG(6, "match:%016llX", (U64)match);
147  if (*(ip+matchLength) < *(match+matchLength)) {
148  *ptr0 = delta0;
149  ptr0 = &DELTANEXTMAXD(matchIndex*2);
150  if (*ptr0 == (U16)-1) break;
151  delta0 = *ptr0;
152  delta1 += delta0;
153  matchIndex -= delta0;
154  } else {
155  *ptr1 = delta1;
156  ptr1 = &DELTANEXTMAXD(matchIndex*2+1);
157  if (*ptr1 == (U16)-1) break;
158  delta1 = *ptr1;
159  delta0 += delta1;
160  matchIndex -= delta1;
161  }
162  }
163 
164  *ptr0 = (U16)-1;
165  *ptr1 = (U16)-1;
166  if (matchNum) *matchNum = mnum;
167  /* if (best_mlen > 8) return best_mlen-8; */
168  if (!matchNum) return 1;
169  return 1;
170 }
171 
172 
173 FORCE_INLINE void LZ4HC_updateBinTree(LZ4HC_CCtx_internal* ctx, const BYTE* const ip, const BYTE* const iHighLimit)
174 {
175  const BYTE* const base = ctx->base;
176  const U32 target = (U32)(ip - base);
177  U32 idx = ctx->nextToUpdate;
178  while(idx < target)
179  idx += LZ4HC_BinTree_InsertAndGetAllMatches(ctx, base+idx, iHighLimit, 8, NULL, NULL);
180 }
181 
182 
186  const BYTE* const ip, const BYTE* const iHighLimit,
187  size_t best_mlen, LZ4HC_match_t* matches, const int fullUpdate)
188 {
189  int mnum = 0;
190  if (ip < ctx->base + ctx->nextToUpdate) return 0; /* skipped area */
191  if (fullUpdate) LZ4HC_updateBinTree(ctx, ip, iHighLimit);
192  best_mlen = LZ4HC_BinTree_InsertAndGetAllMatches(ctx, ip, iHighLimit, best_mlen, matches, &mnum);
193  ctx->nextToUpdate = (U32)(ip - ctx->base + best_mlen);
194  return mnum;
195 }
196 
197 
198 #define SET_PRICE(pos, ml, offset, ll, cost) \
199 { \
200  while (last_pos < pos) { opt[last_pos+1].price = 1<<30; last_pos++; } \
201  opt[pos].mlen = (int)ml; \
202  opt[pos].off = (int)offset; \
203  opt[pos].litlen = (int)ll; \
204  opt[pos].price = (int)cost; \
205 }
206 
207 
210  const char* const source,
211  char* dest,
212  int inputSize,
213  int maxOutputSize,
215  size_t sufficient_len,
216  const int fullUpdate
217  )
218 {
219  LZ4HC_optimal_t opt[LZ4_OPT_NUM + 1]; /* this uses a bit too much stack memory to my taste ... */
221 
222  const BYTE* ip = (const BYTE*) source;
223  const BYTE* anchor = ip;
224  const BYTE* const iend = ip + inputSize;
225  const BYTE* const mflimit = iend - MFLIMIT;
226  const BYTE* const matchlimit = (iend - LASTLITERALS);
227  BYTE* op = (BYTE*) dest;
228  BYTE* const oend = op + maxOutputSize;
229 
230  /* init */
231  DEBUGLOG(5, "LZ4HC_compress_optimal");
232  if (sufficient_len >= LZ4_OPT_NUM) sufficient_len = LZ4_OPT_NUM-1;
233  ctx->end += inputSize;
234  ip++;
235 
236  /* Main Loop */
237  while (ip < mflimit) {
238  size_t const llen = ip - anchor;
239  size_t last_pos = 0;
240  size_t match_num, cur, best_mlen, best_off;
241  memset(opt, 0, sizeof(LZ4HC_optimal_t)); /* memset only the first one */
242 
243  match_num = LZ4HC_BinTree_GetAllMatches(ctx, ip, matchlimit, MINMATCH-1, matches, fullUpdate);
244  if (!match_num) { ip++; continue; }
245 
246  if ((size_t)matches[match_num-1].len > sufficient_len) {
247  /* good enough solution : immediate encoding */
248  best_mlen = matches[match_num-1].len;
249  best_off = matches[match_num-1].off;
250  cur = 0;
251  last_pos = 1;
252  goto encode;
253  }
254 
255  /* set prices using matches at position = 0 */
256  { size_t matchNb;
257  for (matchNb = 0; matchNb < match_num; matchNb++) {
258  size_t mlen = (matchNb>0) ? (size_t)matches[matchNb-1].len+1 : MINMATCH;
259  best_mlen = matches[matchNb].len; /* necessarily < sufficient_len < LZ4_OPT_NUM */
260  for ( ; mlen <= best_mlen ; mlen++) {
261  size_t const cost = LZ4HC_sequencePrice(llen, mlen) - LZ4HC_literalsPrice(llen);
262  SET_PRICE(mlen, mlen, matches[matchNb].off, 0, cost); /* updates last_pos and opt[pos] */
263  } } }
264 
265  if (last_pos < MINMATCH) { ip++; continue; } /* note : on clang at least, this test improves performance */
266 
267  /* check further positions */
268  opt[0].mlen = opt[1].mlen = 1;
269  for (cur = 1; cur <= last_pos; cur++) {
270  const BYTE* const curPtr = ip + cur;
271 
272  /* establish baseline price if cur is literal */
273  { size_t price, litlen;
274  if (opt[cur-1].mlen == 1) {
275  /* no match at previous position */
276  litlen = opt[cur-1].litlen + 1;
277  if (cur > litlen) {
278  price = opt[cur - litlen].price + LZ4HC_literalsPrice(litlen);
279  } else {
280  price = LZ4HC_literalsPrice(llen + litlen) - LZ4HC_literalsPrice(llen);
281  }
282  } else {
283  litlen = 1;
284  price = opt[cur - 1].price + LZ4HC_literalsPrice(1);
285  }
286 
287  if (price < (size_t)opt[cur].price)
288  SET_PRICE(cur, 1 /*mlen*/, 0 /*off*/, litlen, price); /* note : increases last_pos */
289  }
290 
291  if (cur == last_pos || curPtr >= mflimit) break;
292 
293  match_num = LZ4HC_BinTree_GetAllMatches(ctx, curPtr, matchlimit, MINMATCH-1, matches, fullUpdate);
294  if ((match_num > 0) && (size_t)matches[match_num-1].len > sufficient_len) {
295  /* immediate encoding */
296  best_mlen = matches[match_num-1].len;
297  best_off = matches[match_num-1].off;
298  last_pos = cur + 1;
299  goto encode;
300  }
301 
302  /* set prices using matches at position = cur */
303  { size_t matchNb;
304  for (matchNb = 0; matchNb < match_num; matchNb++) {
305  size_t ml = (matchNb>0) ? (size_t)matches[matchNb-1].len+1 : MINMATCH;
306  best_mlen = (cur + matches[matchNb].len < LZ4_OPT_NUM) ?
307  (size_t)matches[matchNb].len : LZ4_OPT_NUM - cur;
308 
309  for ( ; ml <= best_mlen ; ml++) {
310  size_t ll, price;
311  if (opt[cur].mlen == 1) {
312  ll = opt[cur].litlen;
313  if (cur > ll)
314  price = opt[cur - ll].price + LZ4HC_sequencePrice(ll, ml);
315  else
316  price = LZ4HC_sequencePrice(llen + ll, ml) - LZ4HC_literalsPrice(llen);
317  } else {
318  ll = 0;
319  price = opt[cur].price + LZ4HC_sequencePrice(0, ml);
320  }
321 
322  if (cur + ml > last_pos || price < (size_t)opt[cur + ml].price) {
323  SET_PRICE(cur + ml, ml, matches[matchNb].off, ll, price);
324  } } } }
325  } /* for (cur = 1; cur <= last_pos; cur++) */
326 
327  best_mlen = opt[last_pos].mlen;
328  best_off = opt[last_pos].off;
329  cur = last_pos - best_mlen;
330 
331 encode: /* cur, last_pos, best_mlen, best_off must be set */
332  opt[0].mlen = 1;
333  while (1) { /* from end to beginning */
334  size_t const ml = opt[cur].mlen;
335  int const offset = opt[cur].off;
336  opt[cur].mlen = (int)best_mlen;
337  opt[cur].off = (int)best_off;
338  best_mlen = ml;
339  best_off = offset;
340  if (ml > cur) break; /* can this happen ? */
341  cur -= ml;
342  }
343 
344  /* encode all recorded sequences */
345  cur = 0;
346  while (cur < last_pos) {
347  int const ml = opt[cur].mlen;
348  int const offset = opt[cur].off;
349  if (ml == 1) { ip++; cur++; continue; }
350  cur += ml;
351  if ( LZ4HC_encodeSequence(&ip, &op, &anchor, ml, ip - offset, limit, oend) ) return 0;
352  }
353  } /* while (ip < mflimit) */
354 
355  /* Encode Last Literals */
356  { int lastRun = (int)(iend - anchor);
357  if ((limit) && (((char*)op - dest) + lastRun + 1 + ((lastRun+255-RUN_MASK)/255) > (U32)maxOutputSize)) return 0; /* Check output limit */
358  if (lastRun>=(int)RUN_MASK) { *op++=(RUN_MASK<<ML_BITS); lastRun-=RUN_MASK; for(; lastRun > 254 ; lastRun-=255) *op++ = 255; *op++ = (BYTE) lastRun; }
359  else *op++ = (BYTE)(lastRun<<ML_BITS);
360  memcpy(op, anchor, iend - anchor);
361  op += iend-anchor;
362  }
363 
364  /* End */
365  return (int) ((char*)op-dest);
366 }
static int LZ4HC_compress_optimal(LZ4HC_CCtx_internal *ctx, const char *const source, char *dest, int inputSize, int maxOutputSize, limitedOutput_directive limit, size_t sufficient_len, const int fullUpdate)
Definition: lz4opt.h:208
#define MINMATCH
Definition: lz4.c:262
unsigned int U32
Definition: lz4.c:147
static U32 LZ4HC_hashPtr(const void *ptr)
Definition: lz4hc.c:76
unsigned int dictLimit
Definition: lz4hc.h:169
#define LASTLITERALS
Definition: lz4.c:265
FORCE_INLINE size_t LZ4HC_literalsPrice(size_t litlen)
Definition: lz4opt.h:53
matches
Definition: test-fg.py:19
#define LZ4_OPT_NUM
Definition: lz4opt.h:36
FORCE_INLINE int LZ4HC_encodeSequence(const BYTE **ip, BYTE **op, const BYTE **anchor, int matchLength, const BYTE *const match, limitedOutput_directive limit, BYTE *oend)
Definition: lz4hc.c:249
#define SET_PRICE(pos, ml, offset, ll, cost)
Definition: lz4opt.h:198
#define MAX_DISTANCE
Definition: lz4.c:274
unsigned long long U64
Definition: lz4.c:149
GLint limit
Definition: glext.h:9964
const unsigned char * dictBase
Definition: lz4hc.h:167
#define DEBUGLOG(l,...)
Definition: lz4.c:296
unsigned int hashTable[LZ4HC_HASHTABLESIZE]
Definition: lz4hc.h:163
GLenum GLsizei len
Definition: glext.h:3285
#define FORCE_INLINE
Definition: lz4.c:109
unsigned short U16
Definition: lz4.c:146
unsigned char BYTE
Definition: lz4.c:145
unsigned int lowLimit
Definition: lz4hc.h:170
#define ML_BITS
Definition: lz4.c:276
FORCE_INLINE void LZ4HC_updateBinTree(LZ4HC_CCtx_internal *ctx, const BYTE *const ip, const BYTE *const iHighLimit)
Definition: lz4opt.h:173
FORCE_INLINE size_t LZ4HC_sequencePrice(size_t litlen, size_t mlen)
Definition: lz4opt.h:63
unsigned int nextToUpdate
Definition: lz4hc.h:171
GLenum target
Definition: glext.h:1565
unsigned int searchNum
Definition: lz4hc.h:172
LZ4LIB_API const char char int inputSize
Definition: lz4.h:440
const unsigned char * base
Definition: lz4hc.h:166
#define ML_MASK
Definition: lz4.c:277
LZ4LIB_API char int int maxOutputSize
Definition: lz4.h:439
GLsizei GLsizei GLchar * source
#define RUN_MASK
Definition: lz4.c:279
LZ4LIB_API char * dest
Definition: lz4.h:438
#define NULL
Definition: tinycthread.c:47
FORCE_INLINE int LZ4HC_BinTree_GetAllMatches(LZ4HC_CCtx_internal *ctx, const BYTE *const ip, const BYTE *const iHighLimit, size_t best_mlen, LZ4HC_match_t *matches, const int fullUpdate)
Definition: lz4opt.h:184
limitedOutput_directive
Definition: lz4.c:391
unsigned short chainTable[LZ4HC_MAXD]
Definition: lz4hc.h:164
FORCE_INLINE int LZ4HC_BinTree_InsertAndGetAllMatches(LZ4HC_CCtx_internal *ctx, const BYTE *const ip, const BYTE *const iHighLimit, size_t best_mlen, LZ4HC_match_t *matches, int *matchNum)
Definition: lz4opt.h:79
#define MFLIMIT
Definition: lz4.c:266
GLintptr offset
const unsigned char * end
Definition: lz4hc.h:165
static unsigned LZ4_count(const BYTE *pIn, const BYTE *pMatch, const BYTE *pInLimit)
Definition: lz4.c:362
#define DELTANEXTMAXD(p)
Definition: lz4hc.c:73


librealsense2
Author(s): Sergey Dorodnicov , Doron Hirshberg , Mark Horn , Reagan Lopez , Itay Carpis
autogenerated on Mon May 3 2021 02:47:21