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
39typedef struct
40{
41    int off;
42    int len;
43} LZ4HC_match_t;
44
45typedef struct
46{
47    int price;
48    int off;
49    int mlen;
50    int litlen;
51} LZ4HC_optimal_t;
52
53
54/* price in bits */
55FORCE_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 */
64FORCE_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***************************************/
80FORCE_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
170FORCE_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 */
181FORCE_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
205static 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
327encode: /* 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