1 /*
2  * Copyright (c) Yann Collet, Facebook, Inc.
3  * All rights reserved.
4  *
5  * This source code is licensed under both the BSD-style license (found in the
6  * LICENSE file in the root directory of this source tree) and the GPLv2 (found
7  * in the COPYING file in the root directory of this source tree).
8  * You may select, at your option, one of the above-listed licenses.
9  */
10 
11  /*-*************************************
12  *  Dependencies
13  ***************************************/
14 #include "zstd_compress_sequences.h"
15 
16 /*
17  * -log2(x / 256) lookup table for x in [0, 256).
18  * If x == 0: Return 0
19  * Else: Return floor(-log2(x / 256) * 256)
20  */
21 static unsigned const kInverseProbabilityLog256[256] = {
22     0,    2048, 1792, 1642, 1536, 1453, 1386, 1329, 1280, 1236, 1197, 1162,
23     1130, 1100, 1073, 1047, 1024, 1001, 980,  960,  941,  923,  906,  889,
24     874,  859,  844,  830,  817,  804,  791,  779,  768,  756,  745,  734,
25     724,  714,  704,  694,  685,  676,  667,  658,  650,  642,  633,  626,
26     618,  610,  603,  595,  588,  581,  574,  567,  561,  554,  548,  542,
27     535,  529,  523,  517,  512,  506,  500,  495,  489,  484,  478,  473,
28     468,  463,  458,  453,  448,  443,  438,  434,  429,  424,  420,  415,
29     411,  407,  402,  398,  394,  390,  386,  382,  377,  373,  370,  366,
30     362,  358,  354,  350,  347,  343,  339,  336,  332,  329,  325,  322,
31     318,  315,  311,  308,  305,  302,  298,  295,  292,  289,  286,  282,
32     279,  276,  273,  270,  267,  264,  261,  258,  256,  253,  250,  247,
33     244,  241,  239,  236,  233,  230,  228,  225,  222,  220,  217,  215,
34     212,  209,  207,  204,  202,  199,  197,  194,  192,  190,  187,  185,
35     182,  180,  178,  175,  173,  171,  168,  166,  164,  162,  159,  157,
36     155,  153,  151,  149,  146,  144,  142,  140,  138,  136,  134,  132,
37     130,  128,  126,  123,  121,  119,  117,  115,  114,  112,  110,  108,
38     106,  104,  102,  100,  98,   96,   94,   93,   91,   89,   87,   85,
39     83,   82,   80,   78,   76,   74,   73,   71,   69,   67,   66,   64,
40     62,   61,   59,   57,   55,   54,   52,   50,   49,   47,   46,   44,
41     42,   41,   39,   37,   36,   34,   33,   31,   30,   28,   26,   25,
42     23,   22,   20,   19,   17,   16,   14,   13,   11,   10,   8,    7,
43     5,    4,    2,    1,
44 };
45 
46 static unsigned ZSTD_getFSEMaxSymbolValue(FSE_CTable const* ctable) {
47   void const* ptr = ctable;
48   U16 const* u16ptr = (U16 const*)ptr;
49   U32 const maxSymbolValue = MEM_read16(u16ptr + 1);
50   return maxSymbolValue;
51 }
52 
53 /*
54  * Returns true if we should use ncount=-1 else we should
55  * use ncount=1 for low probability symbols instead.
56  */
57 static unsigned ZSTD_useLowProbCount(size_t const nbSeq)
58 {
59     /* Heuristic: This should cover most blocks <= 16K and
60      * start to fade out after 16K to about 32K depending on
61      * comprssibility.
62      */
63     return nbSeq >= 2048;
64 }
65 
66 /*
67  * Returns the cost in bytes of encoding the normalized count header.
68  * Returns an error if any of the helper functions return an error.
69  */
70 static size_t ZSTD_NCountCost(unsigned const* count, unsigned const max,
71                               size_t const nbSeq, unsigned const FSELog)
72 {
73     BYTE wksp[FSE_NCOUNTBOUND];
74     S16 norm[MaxSeq + 1];
75     const U32 tableLog = FSE_optimalTableLog(FSELog, nbSeq, max);
76     FORWARD_IF_ERROR(FSE_normalizeCount(norm, tableLog, count, nbSeq, max, ZSTD_useLowProbCount(nbSeq)), "");
77     return FSE_writeNCount(wksp, sizeof(wksp), norm, max, tableLog);
78 }
79 
80 /*
81  * Returns the cost in bits of encoding the distribution described by count
82  * using the entropy bound.
83  */
84 static size_t ZSTD_entropyCost(unsigned const* count, unsigned const max, size_t const total)
85 {
86     unsigned cost = 0;
87     unsigned s;
88     for (s = 0; s <= max; ++s) {
89         unsigned norm = (unsigned)((256 * count[s]) / total);
90         if (count[s] != 0 && norm == 0)
91             norm = 1;
92         assert(count[s] < total);
93         cost += count[s] * kInverseProbabilityLog256[norm];
94     }
95     return cost >> 8;
96 }
97 
98 /*
99  * Returns the cost in bits of encoding the distribution in count using ctable.
100  * Returns an error if ctable cannot represent all the symbols in count.
101  */
102 size_t ZSTD_fseBitCost(
103     FSE_CTable const* ctable,
104     unsigned const* count,
105     unsigned const max)
106 {
107     unsigned const kAccuracyLog = 8;
108     size_t cost = 0;
109     unsigned s;
110     FSE_CState_t cstate;
111     FSE_initCState(&cstate, ctable);
112     if (ZSTD_getFSEMaxSymbolValue(ctable) < max) {
113         DEBUGLOG(5, "Repeat FSE_CTable has maxSymbolValue %u < %u",
114                     ZSTD_getFSEMaxSymbolValue(ctable), max);
115         return ERROR(GENERIC);
116     }
117     for (s = 0; s <= max; ++s) {
118         unsigned const tableLog = cstate.stateLog;
119         unsigned const badCost = (tableLog + 1) << kAccuracyLog;
120         unsigned const bitCost = FSE_bitCost(cstate.symbolTT, tableLog, s, kAccuracyLog);
121         if (count[s] == 0)
122             continue;
123         if (bitCost >= badCost) {
124             DEBUGLOG(5, "Repeat FSE_CTable has Prob[%u] == 0", s);
125             return ERROR(GENERIC);
126         }
127         cost += (size_t)count[s] * bitCost;
128     }
129     return cost >> kAccuracyLog;
130 }
131 
132 /*
133  * Returns the cost in bits of encoding the distribution in count using the
134  * table described by norm. The max symbol support by norm is assumed >= max.
135  * norm must be valid for every symbol with non-zero probability in count.
136  */
137 size_t ZSTD_crossEntropyCost(short const* norm, unsigned accuracyLog,
138                              unsigned const* count, unsigned const max)
139 {
140     unsigned const shift = 8 - accuracyLog;
141     size_t cost = 0;
142     unsigned s;
143     assert(accuracyLog <= 8);
144     for (s = 0; s <= max; ++s) {
145         unsigned const normAcc = (norm[s] != -1) ? (unsigned)norm[s] : 1;
146         unsigned const norm256 = normAcc << shift;
147         assert(norm256 > 0);
148         assert(norm256 < 256);
149         cost += count[s] * kInverseProbabilityLog256[norm256];
150     }
151     return cost >> 8;
152 }
153 
154 symbolEncodingType_e
155 ZSTD_selectEncodingType(
156         FSE_repeat* repeatMode, unsigned const* count, unsigned const max,
157         size_t const mostFrequent, size_t nbSeq, unsigned const FSELog,
158         FSE_CTable const* prevCTable,
159         short const* defaultNorm, U32 defaultNormLog,
160         ZSTD_defaultPolicy_e const isDefaultAllowed,
161         ZSTD_strategy const strategy)
162 {
163     ZSTD_STATIC_ASSERT(ZSTD_defaultDisallowed == 0 && ZSTD_defaultAllowed != 0);
164     if (mostFrequent == nbSeq) {
165         *repeatMode = FSE_repeat_none;
166         if (isDefaultAllowed && nbSeq <= 2) {
167             /* Prefer set_basic over set_rle when there are 2 or less symbols,
168              * since RLE uses 1 byte, but set_basic uses 5-6 bits per symbol.
169              * If basic encoding isn't possible, always choose RLE.
170              */
171             DEBUGLOG(5, "Selected set_basic");
172             return set_basic;
173         }
174         DEBUGLOG(5, "Selected set_rle");
175         return set_rle;
176     }
177     if (strategy < ZSTD_lazy) {
178         if (isDefaultAllowed) {
179             size_t const staticFse_nbSeq_max = 1000;
180             size_t const mult = 10 - strategy;
181             size_t const baseLog = 3;
182             size_t const dynamicFse_nbSeq_min = (((size_t)1 << defaultNormLog) * mult) >> baseLog;  /* 28-36 for offset, 56-72 for lengths */
183             assert(defaultNormLog >= 5 && defaultNormLog <= 6);  /* xx_DEFAULTNORMLOG */
184             assert(mult <= 9 && mult >= 7);
185             if ( (*repeatMode == FSE_repeat_valid)
186               && (nbSeq < staticFse_nbSeq_max) ) {
187                 DEBUGLOG(5, "Selected set_repeat");
188                 return set_repeat;
189             }
190             if ( (nbSeq < dynamicFse_nbSeq_min)
191               || (mostFrequent < (nbSeq >> (defaultNormLog-1))) ) {
192                 DEBUGLOG(5, "Selected set_basic");
193                 /* The format allows default tables to be repeated, but it isn't useful.
194                  * When using simple heuristics to select encoding type, we don't want
195                  * to confuse these tables with dictionaries. When running more careful
196                  * analysis, we don't need to waste time checking both repeating tables
197                  * and default tables.
198                  */
199                 *repeatMode = FSE_repeat_none;
200                 return set_basic;
201             }
202         }
203     } else {
204         size_t const basicCost = isDefaultAllowed ? ZSTD_crossEntropyCost(defaultNorm, defaultNormLog, count, max) : ERROR(GENERIC);
205         size_t const repeatCost = *repeatMode != FSE_repeat_none ? ZSTD_fseBitCost(prevCTable, count, max) : ERROR(GENERIC);
206         size_t const NCountCost = ZSTD_NCountCost(count, max, nbSeq, FSELog);
207         size_t const compressedCost = (NCountCost << 3) + ZSTD_entropyCost(count, max, nbSeq);
208 
209         if (isDefaultAllowed) {
210             assert(!ZSTD_isError(basicCost));
211             assert(!(*repeatMode == FSE_repeat_valid && ZSTD_isError(repeatCost)));
212         }
213         assert(!ZSTD_isError(NCountCost));
214         assert(compressedCost < ERROR(maxCode));
215         DEBUGLOG(5, "Estimated bit costs: basic=%u\trepeat=%u\tcompressed=%u",
216                     (unsigned)basicCost, (unsigned)repeatCost, (unsigned)compressedCost);
217         if (basicCost <= repeatCost && basicCost <= compressedCost) {
218             DEBUGLOG(5, "Selected set_basic");
219             assert(isDefaultAllowed);
220             *repeatMode = FSE_repeat_none;
221             return set_basic;
222         }
223         if (repeatCost <= compressedCost) {
224             DEBUGLOG(5, "Selected set_repeat");
225             assert(!ZSTD_isError(repeatCost));
226             return set_repeat;
227         }
228         assert(compressedCost < basicCost && compressedCost < repeatCost);
229     }
230     DEBUGLOG(5, "Selected set_compressed");
231     *repeatMode = FSE_repeat_check;
232     return set_compressed;
233 }
234 
235 typedef struct {
236     S16 norm[MaxSeq + 1];
237     U32 wksp[FSE_BUILD_CTABLE_WORKSPACE_SIZE_U32(MaxSeq, MaxFSELog)];
238 } ZSTD_BuildCTableWksp;
239 
240 size_t
241 ZSTD_buildCTable(void* dst, size_t dstCapacity,
242                 FSE_CTable* nextCTable, U32 FSELog, symbolEncodingType_e type,
243                 unsigned* count, U32 max,
244                 const BYTE* codeTable, size_t nbSeq,
245                 const S16* defaultNorm, U32 defaultNormLog, U32 defaultMax,
246                 const FSE_CTable* prevCTable, size_t prevCTableSize,
247                 void* entropyWorkspace, size_t entropyWorkspaceSize)
248 {
249     BYTE* op = (BYTE*)dst;
250     const BYTE* const oend = op + dstCapacity;
251     DEBUGLOG(6, "ZSTD_buildCTable (dstCapacity=%u)", (unsigned)dstCapacity);
252 
253     switch (type) {
254     case set_rle:
255         FORWARD_IF_ERROR(FSE_buildCTable_rle(nextCTable, (BYTE)max), "");
256         RETURN_ERROR_IF(dstCapacity==0, dstSize_tooSmall, "not enough space");
257         *op = codeTable[0];
258         return 1;
259     case set_repeat:
260         ZSTD_memcpy(nextCTable, prevCTable, prevCTableSize);
261         return 0;
262     case set_basic:
263         FORWARD_IF_ERROR(FSE_buildCTable_wksp(nextCTable, defaultNorm, defaultMax, defaultNormLog, entropyWorkspace, entropyWorkspaceSize), "");  /* note : could be pre-calculated */
264         return 0;
265     case set_compressed: {
266         ZSTD_BuildCTableWksp* wksp = (ZSTD_BuildCTableWksp*)entropyWorkspace;
267         size_t nbSeq_1 = nbSeq;
268         const U32 tableLog = FSE_optimalTableLog(FSELog, nbSeq, max);
269         if (count[codeTable[nbSeq-1]] > 1) {
270             count[codeTable[nbSeq-1]]--;
271             nbSeq_1--;
272         }
273         assert(nbSeq_1 > 1);
274         assert(entropyWorkspaceSize >= sizeof(ZSTD_BuildCTableWksp));
275         (void)entropyWorkspaceSize;
276         FORWARD_IF_ERROR(FSE_normalizeCount(wksp->norm, tableLog, count, nbSeq_1, max, ZSTD_useLowProbCount(nbSeq_1)), "");
277         {   size_t const NCountSize = FSE_writeNCount(op, oend - op, wksp->norm, max, tableLog);   /* overflow protected */
278             FORWARD_IF_ERROR(NCountSize, "FSE_writeNCount failed");
279             FORWARD_IF_ERROR(FSE_buildCTable_wksp(nextCTable, wksp->norm, max, tableLog, wksp->wksp, sizeof(wksp->wksp)), "");
280             return NCountSize;
281         }
282     }
283     default: assert(0); RETURN_ERROR(GENERIC, "impossible to reach");
284     }
285 }
286 
287 FORCE_INLINE_TEMPLATE size_t
288 ZSTD_encodeSequences_body(
289             void* dst, size_t dstCapacity,
290             FSE_CTable const* CTable_MatchLength, BYTE const* mlCodeTable,
291             FSE_CTable const* CTable_OffsetBits, BYTE const* ofCodeTable,
292             FSE_CTable const* CTable_LitLength, BYTE const* llCodeTable,
293             seqDef const* sequences, size_t nbSeq, int longOffsets)
294 {
295     BIT_CStream_t blockStream;
296     FSE_CState_t  stateMatchLength;
297     FSE_CState_t  stateOffsetBits;
298     FSE_CState_t  stateLitLength;
299 
300     RETURN_ERROR_IF(
301         ERR_isError(BIT_initCStream(&blockStream, dst, dstCapacity)),
302         dstSize_tooSmall, "not enough space remaining");
303     DEBUGLOG(6, "available space for bitstream : %i  (dstCapacity=%u)",
304                 (int)(blockStream.endPtr - blockStream.startPtr),
305                 (unsigned)dstCapacity);
306 
307     /* first symbols */
308     FSE_initCState2(&stateMatchLength, CTable_MatchLength, mlCodeTable[nbSeq-1]);
309     FSE_initCState2(&stateOffsetBits,  CTable_OffsetBits,  ofCodeTable[nbSeq-1]);
310     FSE_initCState2(&stateLitLength,   CTable_LitLength,   llCodeTable[nbSeq-1]);
311     BIT_addBits(&blockStream, sequences[nbSeq-1].litLength, LL_bits[llCodeTable[nbSeq-1]]);
312     if (MEM_32bits()) BIT_flushBits(&blockStream);
313     BIT_addBits(&blockStream, sequences[nbSeq-1].matchLength, ML_bits[mlCodeTable[nbSeq-1]]);
314     if (MEM_32bits()) BIT_flushBits(&blockStream);
315     if (longOffsets) {
316         U32 const ofBits = ofCodeTable[nbSeq-1];
317         unsigned const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN-1);
318         if (extraBits) {
319             BIT_addBits(&blockStream, sequences[nbSeq-1].offset, extraBits);
320             BIT_flushBits(&blockStream);
321         }
322         BIT_addBits(&blockStream, sequences[nbSeq-1].offset >> extraBits,
323                     ofBits - extraBits);
324     } else {
325         BIT_addBits(&blockStream, sequences[nbSeq-1].offset, ofCodeTable[nbSeq-1]);
326     }
327     BIT_flushBits(&blockStream);
328 
329     {   size_t n;
330         for (n=nbSeq-2 ; n<nbSeq ; n--) {      /* intentional underflow */
331             BYTE const llCode = llCodeTable[n];
332             BYTE const ofCode = ofCodeTable[n];
333             BYTE const mlCode = mlCodeTable[n];
334             U32  const llBits = LL_bits[llCode];
335             U32  const ofBits = ofCode;
336             U32  const mlBits = ML_bits[mlCode];
337             DEBUGLOG(6, "encoding: litlen:%2u - matchlen:%2u - offCode:%7u",
338                         (unsigned)sequences[n].litLength,
339                         (unsigned)sequences[n].matchLength + MINMATCH,
340                         (unsigned)sequences[n].offset);
341                                                                             /* 32b*/  /* 64b*/
342                                                                             /* (7)*/  /* (7)*/
343             FSE_encodeSymbol(&blockStream, &stateOffsetBits, ofCode);       /* 15 */  /* 15 */
344             FSE_encodeSymbol(&blockStream, &stateMatchLength, mlCode);      /* 24 */  /* 24 */
345             if (MEM_32bits()) BIT_flushBits(&blockStream);                  /* (7)*/
346             FSE_encodeSymbol(&blockStream, &stateLitLength, llCode);        /* 16 */  /* 33 */
347             if (MEM_32bits() || (ofBits+mlBits+llBits >= 64-7-(LLFSELog+MLFSELog+OffFSELog)))
348                 BIT_flushBits(&blockStream);                                /* (7)*/
349             BIT_addBits(&blockStream, sequences[n].litLength, llBits);
350             if (MEM_32bits() && ((llBits+mlBits)>24)) BIT_flushBits(&blockStream);
351             BIT_addBits(&blockStream, sequences[n].matchLength, mlBits);
352             if (MEM_32bits() || (ofBits+mlBits+llBits > 56)) BIT_flushBits(&blockStream);
353             if (longOffsets) {
354                 unsigned const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN-1);
355                 if (extraBits) {
356                     BIT_addBits(&blockStream, sequences[n].offset, extraBits);
357                     BIT_flushBits(&blockStream);                            /* (7)*/
358                 }
359                 BIT_addBits(&blockStream, sequences[n].offset >> extraBits,
360                             ofBits - extraBits);                            /* 31 */
361             } else {
362                 BIT_addBits(&blockStream, sequences[n].offset, ofBits);     /* 31 */
363             }
364             BIT_flushBits(&blockStream);                                    /* (7)*/
365             DEBUGLOG(7, "remaining space : %i", (int)(blockStream.endPtr - blockStream.ptr));
366     }   }
367 
368     DEBUGLOG(6, "ZSTD_encodeSequences: flushing ML state with %u bits", stateMatchLength.stateLog);
369     FSE_flushCState(&blockStream, &stateMatchLength);
370     DEBUGLOG(6, "ZSTD_encodeSequences: flushing Off state with %u bits", stateOffsetBits.stateLog);
371     FSE_flushCState(&blockStream, &stateOffsetBits);
372     DEBUGLOG(6, "ZSTD_encodeSequences: flushing LL state with %u bits", stateLitLength.stateLog);
373     FSE_flushCState(&blockStream, &stateLitLength);
374 
375     {   size_t const streamSize = BIT_closeCStream(&blockStream);
376         RETURN_ERROR_IF(streamSize==0, dstSize_tooSmall, "not enough space");
377         return streamSize;
378     }
379 }
380 
381 static size_t
382 ZSTD_encodeSequences_default(
383             void* dst, size_t dstCapacity,
384             FSE_CTable const* CTable_MatchLength, BYTE const* mlCodeTable,
385             FSE_CTable const* CTable_OffsetBits, BYTE const* ofCodeTable,
386             FSE_CTable const* CTable_LitLength, BYTE const* llCodeTable,
387             seqDef const* sequences, size_t nbSeq, int longOffsets)
388 {
389     return ZSTD_encodeSequences_body(dst, dstCapacity,
390                                     CTable_MatchLength, mlCodeTable,
391                                     CTable_OffsetBits, ofCodeTable,
392                                     CTable_LitLength, llCodeTable,
393                                     sequences, nbSeq, longOffsets);
394 }
395 
396 
397 #if DYNAMIC_BMI2
398 
399 static TARGET_ATTRIBUTE("bmi2") size_t
400 ZSTD_encodeSequences_bmi2(
401             void* dst, size_t dstCapacity,
402             FSE_CTable const* CTable_MatchLength, BYTE const* mlCodeTable,
403             FSE_CTable const* CTable_OffsetBits, BYTE const* ofCodeTable,
404             FSE_CTable const* CTable_LitLength, BYTE const* llCodeTable,
405             seqDef const* sequences, size_t nbSeq, int longOffsets)
406 {
407     return ZSTD_encodeSequences_body(dst, dstCapacity,
408                                     CTable_MatchLength, mlCodeTable,
409                                     CTable_OffsetBits, ofCodeTable,
410                                     CTable_LitLength, llCodeTable,
411                                     sequences, nbSeq, longOffsets);
412 }
413 
414 #endif
415 
416 size_t ZSTD_encodeSequences(
417             void* dst, size_t dstCapacity,
418             FSE_CTable const* CTable_MatchLength, BYTE const* mlCodeTable,
419             FSE_CTable const* CTable_OffsetBits, BYTE const* ofCodeTable,
420             FSE_CTable const* CTable_LitLength, BYTE const* llCodeTable,
421             seqDef const* sequences, size_t nbSeq, int longOffsets, int bmi2)
422 {
423     DEBUGLOG(5, "ZSTD_encodeSequences: dstCapacity = %u", (unsigned)dstCapacity);
424 #if DYNAMIC_BMI2
425     if (bmi2) {
426         return ZSTD_encodeSequences_bmi2(dst, dstCapacity,
427                                          CTable_MatchLength, mlCodeTable,
428                                          CTable_OffsetBits, ofCodeTable,
429                                          CTable_LitLength, llCodeTable,
430                                          sequences, nbSeq, longOffsets);
431     }
432 #endif
433     (void)bmi2;
434     return ZSTD_encodeSequences_default(dst, dstCapacity,
435                                         CTable_MatchLength, mlCodeTable,
436                                         CTable_OffsetBits, ofCodeTable,
437                                         CTable_LitLength, llCodeTable,
438                                         sequences, nbSeq, longOffsets);
439 }
440