1 /*
2 lz4opt.h - Optimal Mode of LZ4
3 Copyright (C) 2015-2016, 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 {
41 int off;
42 int len;
43 } LZ4HC_match_t;
44
45 typedef struct
46 {
47 int price;
48 int off;
49 int mlen;
50 int litlen;
51 } LZ4HC_optimal_t;
52
53
54 /* price in bits */
LZ4HC_literalsPrice(size_t litlen)55 FORCE_INLINE size_t LZ4HC_literalsPrice(size_t litlen)
56 {
57 size_t price = 8*litlen;
58 if (litlen >= (size_t)RUN_MASK) price+=8*(1+(litlen-RUN_MASK)/255);
59 return price;
60 }
61
62
63 /* requires mlen >= MINMATCH */
LZ4HC_sequencePrice(size_t litlen,size_t mlen)64 FORCE_INLINE size_t LZ4HC_sequencePrice(size_t litlen, size_t mlen)
65 {
66 size_t price = 16 + 8; /* 16-bit offset + token */
67
68 price += LZ4HC_literalsPrice(litlen);
69
70 mlen -= MINMATCH;
71 if (mlen >= (size_t)ML_MASK) price+=8*(1+(mlen-ML_MASK)/255);
72
73 return price;
74 }
75
76
77 /*-*************************************
78 * Binary Tree search
79 ***************************************/
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)80 FORCE_INLINE int LZ4HC_BinTree_InsertAndGetAllMatches (
81 LZ4HC_CCtx_internal* ctx,
82 const BYTE* const ip,
83 const BYTE* const iHighLimit,
84 size_t best_mlen,
85 LZ4HC_match_t* matches,
86 int* matchNum)
87 {
88 U16* const chainTable = ctx->chainTable;
89 U32* const HashTable = ctx->hashTable;
90 const BYTE* const base = ctx->base;
91 const U32 dictLimit = ctx->dictLimit;
92 const U32 current = (U32)(ip - base);
93 const U32 lowLimit = (ctx->lowLimit + MAX_DISTANCE > current) ? ctx->lowLimit : current - (MAX_DISTANCE - 1);
94 const BYTE* const dictBase = ctx->dictBase;
95 const BYTE* match;
96 int nbAttempts = ctx->searchNum;
97 int mnum = 0;
98 U16 *ptr0, *ptr1, delta0, delta1;
99 U32 matchIndex;
100 size_t matchLength = 0;
101 U32* HashPos;
102
103 if (ip + MINMATCH > iHighLimit) return 1;
104
105 /* HC4 match finder */
106 HashPos = &HashTable[LZ4HC_hashPtr(ip)];
107 matchIndex = *HashPos;
108 *HashPos = current;
109
110 ptr0 = &DELTANEXTMAXD(current*2+1);
111 ptr1 = &DELTANEXTMAXD(current*2);
112 delta0 = delta1 = (U16)(current - matchIndex);
113
114 while ((matchIndex < current) && (matchIndex>=lowLimit) && (nbAttempts)) {
115 nbAttempts--;
116 if (matchIndex >= dictLimit) {
117 match = base + matchIndex;
118 matchLength = LZ4_count(ip, match, iHighLimit);
119 } else {
120 const BYTE* vLimit = ip + (dictLimit - matchIndex);
121 match = dictBase + matchIndex;
122 if (vLimit > iHighLimit) vLimit = iHighLimit;
123 matchLength = LZ4_count(ip, match, vLimit);
124 if ((ip+matchLength == vLimit) && (vLimit < iHighLimit))
125 matchLength += LZ4_count(ip+matchLength, base+dictLimit, iHighLimit);
126 }
127
128 if (matchLength > best_mlen) {
129 best_mlen = matchLength;
130 if (matches) {
131 if (matchIndex >= dictLimit)
132 matches[mnum].off = (int)(ip - match);
133 else
134 matches[mnum].off = (int)(ip - (base + matchIndex)); /* virtual matchpos */
135 matches[mnum].len = (int)matchLength;
136 mnum++;
137 }
138 if (best_mlen > LZ4_OPT_NUM) break;
139 }
140
141 if (ip+matchLength >= iHighLimit) /* equal : no way to know if inf or sup */
142 break; /* drop , to guarantee consistency ; miss a bit of compression, but other solutions can corrupt the tree */
143
144 if (*(ip+matchLength) < *(match+matchLength)) {
145 *ptr0 = delta0;
146 ptr0 = &DELTANEXTMAXD(matchIndex*2);
147 if (*ptr0 == (U16)-1) break;
148 delta0 = *ptr0;
149 delta1 += delta0;
150 matchIndex -= delta0;
151 } else {
152 *ptr1 = delta1;
153 ptr1 = &DELTANEXTMAXD(matchIndex*2+1);
154 if (*ptr1 == (U16)-1) break;
155 delta1 = *ptr1;
156 delta0 += delta1;
157 matchIndex -= delta1;
158 }
159 }
160
161 *ptr0 = (U16)-1;
162 *ptr1 = (U16)-1;
163 if (matchNum) *matchNum = mnum;
164 /* if (best_mlen > 8) return best_mlen-8; */
165 if (!matchNum) return 1;
166 return 1;
167 }
168
169
LZ4HC_updateBinTree(LZ4HC_CCtx_internal * ctx,const BYTE * const ip,const BYTE * const iHighLimit)170 FORCE_INLINE void LZ4HC_updateBinTree(LZ4HC_CCtx_internal* ctx, const BYTE* const ip, const BYTE* const iHighLimit)
171 {
172 const BYTE* const base = ctx->base;
173 const U32 target = (U32)(ip - base);
174 U32 idx = ctx->nextToUpdate;
175 while(idx < target)
176 idx += LZ4HC_BinTree_InsertAndGetAllMatches(ctx, base+idx, iHighLimit, 8, NULL, NULL);
177 }
178
179
180 /** Tree updater, providing best match */
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)181 FORCE_INLINE int LZ4HC_BinTree_GetAllMatches (
182 LZ4HC_CCtx_internal* ctx,
183 const BYTE* const ip, const BYTE* const iHighLimit,
184 size_t best_mlen, LZ4HC_match_t* matches, const int fullUpdate)
185 {
186 int mnum = 0;
187 if (ip < ctx->base + ctx->nextToUpdate) return 0; /* skipped area */
188 if (fullUpdate) LZ4HC_updateBinTree(ctx, ip, iHighLimit);
189 best_mlen = LZ4HC_BinTree_InsertAndGetAllMatches(ctx, ip, iHighLimit, best_mlen, matches, &mnum);
190 ctx->nextToUpdate = (U32)(ip - ctx->base + best_mlen);
191 return mnum;
192 }
193
194
195 #define SET_PRICE(pos, mlen, offset, litlen, price) \
196 { \
197 while (last_pos < pos) { opt[last_pos+1].price = 1<<30; last_pos++; } \
198 opt[pos].mlen = (int)mlen; \
199 opt[pos].off = (int)offset; \
200 opt[pos].litlen = (int)litlen; \
201 opt[pos].price = (int)price; \
202 }
203
204
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)205 static int LZ4HC_compress_optimal (
206 LZ4HC_CCtx_internal* ctx,
207 const char* const source,
208 char* dest,
209 int inputSize,
210 int maxOutputSize,
211 limitedOutput_directive limit,
212 const size_t sufficient_len,
213 const int fullUpdate
214 )
215 {
216 LZ4HC_optimal_t opt[LZ4_OPT_NUM + 1];
217 LZ4HC_match_t matches[LZ4_OPT_NUM + 1];
218 const BYTE *inr = NULL;
219 size_t res, cur, cur2;
220 size_t i, llen, litlen, mlen, best_mlen, price, offset, best_off, match_num, last_pos;
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 ctx->end += inputSize;
232 ip++;
233
234 /* Main Loop */
235 while (ip < mflimit) {
236 memset(opt, 0, sizeof(LZ4HC_optimal_t));
237 last_pos = 0;
238 llen = ip - anchor;
239 match_num = LZ4HC_BinTree_GetAllMatches(ctx, ip, matchlimit, MINMATCH-1, matches, fullUpdate);
240 if (!match_num) { ip++; continue; }
241
242 if ((size_t)matches[match_num-1].len > sufficient_len) {
243 best_mlen = matches[match_num-1].len;
244 best_off = matches[match_num-1].off;
245 cur = 0;
246 last_pos = 1;
247 goto encode;
248 }
249
250 /* set prices using matches at position = 0 */
251 for (i = 0; i < match_num; i++) {
252 mlen = (i>0) ? (size_t)matches[i-1].len+1 : MINMATCH;
253 best_mlen = (matches[i].len < LZ4_OPT_NUM) ? matches[i].len : LZ4_OPT_NUM;
254 while (mlen <= best_mlen) {
255 litlen = 0;
256 price = LZ4HC_sequencePrice(llen + litlen, mlen) - LZ4HC_literalsPrice(llen);
257 SET_PRICE(mlen, mlen, matches[i].off, litlen, price);
258 mlen++;
259 }
260 }
261
262 if (last_pos < MINMATCH) { ip++; continue; }
263
264 /* check further positions */
265 opt[0].mlen = opt[1].mlen = 1;
266 for (cur = 1; cur <= last_pos; cur++) {
267 inr = ip + cur;
268
269 if (opt[cur-1].mlen == 1) {
270 litlen = opt[cur-1].litlen + 1;
271 if (cur != litlen) {
272 price = opt[cur - litlen].price + LZ4HC_literalsPrice(litlen);
273 } else {
274 price = LZ4HC_literalsPrice(llen + litlen) - LZ4HC_literalsPrice(llen);
275 }
276 } else {
277 litlen = 1;
278 price = opt[cur - 1].price + LZ4HC_literalsPrice(litlen);
279 }
280
281 mlen = 1;
282 best_mlen = 0;
283 if (cur > last_pos || price < (size_t)opt[cur].price)
284 SET_PRICE(cur, mlen, best_mlen, litlen, price);
285
286 if (cur == last_pos || inr >= mflimit) break;
287
288 match_num = LZ4HC_BinTree_GetAllMatches(ctx, inr, matchlimit, MINMATCH-1, matches, fullUpdate);
289 if (match_num > 0 && (size_t)matches[match_num-1].len > sufficient_len) {
290 best_mlen = matches[match_num-1].len;
291 best_off = matches[match_num-1].off;
292 last_pos = cur + 1;
293 goto encode;
294 }
295
296 /* set prices using matches at position = cur */
297 for (i = 0; i < match_num; i++) {
298 mlen = (i>0) ? (size_t)matches[i-1].len+1 : MINMATCH;
299 cur2 = cur;
300 best_mlen = (cur2 + matches[i].len < LZ4_OPT_NUM) ? (size_t)matches[i].len : LZ4_OPT_NUM - cur2;
301
302 while (mlen <= best_mlen) {
303 if (opt[cur2].mlen == 1) {
304 litlen = opt[cur2].litlen;
305
306 if (cur2 != litlen)
307 price = opt[cur2 - litlen].price + LZ4HC_sequencePrice(litlen, mlen);
308 else
309 price = LZ4HC_sequencePrice(llen + litlen, mlen) - LZ4HC_literalsPrice(llen);
310 } else {
311 litlen = 0;
312 price = opt[cur2].price + LZ4HC_sequencePrice(litlen, mlen);
313 }
314
315 if (cur2 + mlen > last_pos || price < (size_t)opt[cur2 + mlen].price) { // || (((int)price == opt[cur2 + mlen].price) && (opt[cur2 + mlen-1].mlen == 1))) {
316 SET_PRICE(cur2 + mlen, mlen, matches[i].off, litlen, price);
317 }
318 mlen++;
319 }
320 }
321 } /* for (cur = 1; cur <= last_pos; cur++) */
322
323 best_mlen = opt[last_pos].mlen;
324 best_off = opt[last_pos].off;
325 cur = last_pos - best_mlen;
326
327 encode: /* cur, last_pos, best_mlen, best_off have to be set */
328 opt[0].mlen = 1;
329 while (1) {
330 mlen = opt[cur].mlen;
331 offset = opt[cur].off;
332 opt[cur].mlen = (int)best_mlen;
333 opt[cur].off = (int)best_off;
334 best_mlen = mlen;
335 best_off = offset;
336 if (mlen > cur) break;
337 cur -= mlen;
338 }
339
340 cur = 0;
341 while (cur < last_pos) {
342 mlen = opt[cur].mlen;
343 if (mlen == 1) { ip++; cur++; continue; }
344 offset = opt[cur].off;
345 cur += mlen;
346
347 res = LZ4HC_encodeSequence(&ip, &op, &anchor, (int)mlen, ip - offset, limit, oend);
348 if (res) return 0;
349 }
350 }
351
352 /* Encode Last Literals */
353 { int lastRun = (int)(iend - anchor);
354 if ((limit) && (((char*)op - dest) + lastRun + 1 + ((lastRun+255-RUN_MASK)/255) > (U32)maxOutputSize)) return 0; /* Check output limit */
355 if (lastRun>=(int)RUN_MASK) { *op++=(RUN_MASK<<ML_BITS); lastRun-=RUN_MASK; for(; lastRun > 254 ; lastRun-=255) *op++ = 255; *op++ = (BYTE) lastRun; }
356 else *op++ = (BYTE)(lastRun<<ML_BITS);
357 memcpy(op, anchor, iend - anchor);
358 op += iend-anchor;
359 }
360
361 /* End */
362 return (int) ((char*)op-dest);
363 }
364