sys/contrib/zstd/lib/compress/zstd_compress_sequences.c

   1 /*
   2  * Copyright (c) 2016-present, 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 the cost in bytes of encoding the normalized count header.
  55  * Returns an error if any of the helper functions return an error.
  56  */
  57 static size_t ZSTD_NCountCost(unsigned const* count, unsigned const max,
  58                               size_t const nbSeq, unsigned const FSELog)
  59 {
  60     BYTE wksp[FSE_NCOUNTBOUND];
  61     S16 norm[MaxSeq + 1];
  62     const U32 tableLog = FSE_optimalTableLog(FSELog, nbSeq, max);
  63     FORWARD_IF_ERROR(FSE_normalizeCount(norm, tableLog, count, nbSeq, max));
  64     return FSE_writeNCount(wksp, sizeof(wksp), norm, max, tableLog);
  65 }
  66
  67 /**
  68  * Returns the cost in bits of encoding the distribution described by count
  69  * using the entropy bound.
  70  */
  71 static size_t ZSTD_entropyCost(unsigned const* count, unsigned const max, size_t const total)
  72 {
  73     unsigned cost = 0;
  74     unsigned s;
  75     for (s = 0; s <= max; ++s) {
  76         unsigned norm = (unsigned)((256 * count[s]) / total);
  77         if (count[s] != 0 && norm == 0)
  78             norm = 1;
  79         assert(count[s] < total);
  80         cost += count[s] * kInverseProbabilityLog256[norm];
  81     }
  82     return cost >> 8;
  83 }
  84
  85 /**
  86  * Returns the cost in bits of encoding the distribution in count using ctable.
  87  * Returns an error if ctable cannot represent all the symbols in count.
  88  */
  89 static size_t ZSTD_fseBitCost(
  90     FSE_CTable const* ctable,
  91     unsigned const* count,
  92     unsigned const max)
  93 {
  94     unsigned const kAccuracyLog = 8;
  95     size_t cost = 0;
  96     unsigned s;
  97     FSE_CState_t cstate;
  98     FSE_initCState(&cstate, ctable);
  99     RETURN_ERROR_IF(ZSTD_getFSEMaxSymbolValue(ctable) < max, GENERIC,
 100                     "Repeat FSE_CTable has maxSymbolValue %u < %u",
 101                     ZSTD_getFSEMaxSymbolValue(ctable), max);
 102     for (s = 0; s <= max; ++s) {
 103         unsigned const tableLog = cstate.stateLog;
 104         unsigned const badCost = (tableLog + 1) << kAccuracyLog;
 105         unsigned const bitCost = FSE_bitCost(cstate.symbolTT, tableLog, s, kAccuracyLog);
 106         if (count[s] == 0)
 107             continue;
 108         RETURN_ERROR_IF(bitCost >= badCost, GENERIC,
 109                         "Repeat FSE_CTable has Prob[%u] == 0", s);
 110         cost += count[s] * bitCost;
 111     }
 112     return cost >> kAccuracyLog;
 113 }
 114
 115 /**
 116  * Returns the cost in bits of encoding the distribution in count using the
 117  * table described by norm. The max symbol support by norm is assumed >= max.
 118  * norm must be valid for every symbol with non-zero probability in count.
 119  */
 120 static size_t ZSTD_crossEntropyCost(short const* norm, unsigned accuracyLog,
 121                                     unsigned const* count, unsigned const max)
 122 {
 123     unsigned const shift = 8 - accuracyLog;
 124     size_t cost = 0;
 125     unsigned s;
 126     assert(accuracyLog <= 8);
 127     for (s = 0; s <= max; ++s) {
 128         unsigned const normAcc = norm[s] != -1 ? norm[s] : 1;
 129         unsigned const norm256 = normAcc << shift;
 130         assert(norm256 > 0);
 131         assert(norm256 < 256);
 132         cost += count[s] * kInverseProbabilityLog256[norm256];
 133     }
 134     return cost >> 8;
 135 }
 136
 137 symbolEncodingType_e
 138 ZSTD_selectEncodingType(
 139         FSE_repeat* repeatMode, unsigned const* count, unsigned const max,
 140         size_t const mostFrequent, size_t nbSeq, unsigned const FSELog,
 141         FSE_CTable const* prevCTable,
 142         short const* defaultNorm, U32 defaultNormLog,
 143         ZSTD_defaultPolicy_e const isDefaultAllowed,
 144         ZSTD_strategy const strategy)
 145 {
 146     ZSTD_STATIC_ASSERT(ZSTD_defaultDisallowed == 0 && ZSTD_defaultAllowed != 0);
 147     if (mostFrequent == nbSeq) {
 148         *repeatMode = FSE_repeat_none;
 149         if (isDefaultAllowed && nbSeq <= 2) {
 150             /* Prefer set_basic over set_rle when there are 2 or less symbols,
 151              * since RLE uses 1 byte, but set_basic uses 5-6 bits per symbol.
 152              * If basic encoding isn't possible, always choose RLE.
 153              */
 154             DEBUGLOG(5, "Selected set_basic");
 155             return set_basic;
 156         }
 157         DEBUGLOG(5, "Selected set_rle");
 158         return set_rle;
 159     }
 160     if (strategy < ZSTD_lazy) {
 161         if (isDefaultAllowed) {
 162             size_t const staticFse_nbSeq_max = 1000;
 163             size_t const mult = 10 - strategy;
 164             size_t const baseLog = 3;
 165             size_t const dynamicFse_nbSeq_min = (((size_t)1 << defaultNormLog) * mult) >> baseLog;  /* 28-36 for offset, 56-72 for lengths */
 166             assert(defaultNormLog >= 5 && defaultNormLog <= 6);  /* xx_DEFAULTNORMLOG */
 167             assert(mult <= 9 && mult >= 7);
 168             if ( (*repeatMode == FSE_repeat_valid)
 169               && (nbSeq < staticFse_nbSeq_max) ) {
 170                 DEBUGLOG(5, "Selected set_repeat");
 171                 return set_repeat;
 172             }
 173             if ( (nbSeq < dynamicFse_nbSeq_min)
 174               || (mostFrequent < (nbSeq >> (defaultNormLog-1))) ) {
 175                 DEBUGLOG(5, "Selected set_basic");
 176                 /* The format allows default tables to be repeated, but it isn't useful.
 177                  * When using simple heuristics to select encoding type, we don't want
 178                  * to confuse these tables with dictionaries. When running more careful
 179                  * analysis, we don't need to waste time checking both repeating tables
 180                  * and default tables.
 181                  */
 182                 *repeatMode = FSE_repeat_none;
 183                 return set_basic;
 184             }
 185         }
 186     } else {
 187         size_t const basicCost = isDefaultAllowed ? ZSTD_crossEntropyCost(defaultNorm, defaultNormLog, count, max) : ERROR(GENERIC);
 188         size_t const repeatCost = *repeatMode != FSE_repeat_none ? ZSTD_fseBitCost(prevCTable, count, max) : ERROR(GENERIC);
 189         size_t const NCountCost = ZSTD_NCountCost(count, max, nbSeq, FSELog);
 190         size_t const compressedCost = (NCountCost << 3) + ZSTD_entropyCost(count, max, nbSeq);
 191
 192         if (isDefaultAllowed) {
 193             assert(!ZSTD_isError(basicCost));
 194             assert(!(*repeatMode == FSE_repeat_valid && ZSTD_isError(repeatCost)));
 195         }
 196         assert(!ZSTD_isError(NCountCost));
 197         assert(compressedCost < ERROR(maxCode));
 198         DEBUGLOG(5, "Estimated bit costs: basic=%u\trepeat=%u\tcompressed=%u",
 199                     (unsigned)basicCost, (unsigned)repeatCost, (unsigned)compressedCost);
 200         if (basicCost <= repeatCost && basicCost <= compressedCost) {
 201             DEBUGLOG(5, "Selected set_basic");
 202             assert(isDefaultAllowed);
 203             *repeatMode = FSE_repeat_none;
 204             return set_basic;
 205         }
 206         if (repeatCost <= compressedCost) {
 207             DEBUGLOG(5, "Selected set_repeat");
 208             assert(!ZSTD_isError(repeatCost));
 209             return set_repeat;
 210         }
 211         assert(compressedCost < basicCost && compressedCost < repeatCost);
 212     }
 213     DEBUGLOG(5, "Selected set_compressed");
 214     *repeatMode = FSE_repeat_check;
 215     return set_compressed;
 216 }
 217
 218 size_t
 219 ZSTD_buildCTable(void* dst, size_t dstCapacity,
 220                 FSE_CTable* nextCTable, U32 FSELog, symbolEncodingType_e type,
 221                 unsigned* count, U32 max,
 222                 const BYTE* codeTable, size_t nbSeq,
 223                 const S16* defaultNorm, U32 defaultNormLog, U32 defaultMax,
 224                 const FSE_CTable* prevCTable, size_t prevCTableSize,
 225                 void* entropyWorkspace, size_t entropyWorkspaceSize)
 226 {
 227     BYTE* op = (BYTE*)dst;
 228     const BYTE* const oend = op + dstCapacity;
 229     DEBUGLOG(6, "ZSTD_buildCTable (dstCapacity=%u)", (unsigned)dstCapacity);
 230
 231     switch (type) {
 232     case set_rle:
 233         FORWARD_IF_ERROR(FSE_buildCTable_rle(nextCTable, (BYTE)max));
 234         RETURN_ERROR_IF(dstCapacity==0, dstSize_tooSmall);
 235         *op = codeTable[0];
 236         return 1;
 237     case set_repeat:
 238         memcpy(nextCTable, prevCTable, prevCTableSize);
 239         return 0;
 240     case set_basic:
 241         FORWARD_IF_ERROR(FSE_buildCTable_wksp(nextCTable, defaultNorm, defaultMax, defaultNormLog, entropyWorkspace, entropyWorkspaceSize));  /* note : could be pre-calculated */
 242         return 0;
 243     case set_compressed: {
 244         S16 norm[MaxSeq + 1];
 245         size_t nbSeq_1 = nbSeq;
 246         const U32 tableLog = FSE_optimalTableLog(FSELog, nbSeq, max);
 247         if (count[codeTable[nbSeq-1]] > 1) {
 248             count[codeTable[nbSeq-1]]--;
 249             nbSeq_1--;
 250         }
 251         assert(nbSeq_1 > 1);
 252         FORWARD_IF_ERROR(FSE_normalizeCount(norm, tableLog, count, nbSeq_1, max));
 253         {   size_t const NCountSize = FSE_writeNCount(op, oend - op, norm, max, tableLog);   /* overflow protected */
 254             FORWARD_IF_ERROR(NCountSize);
 255             FORWARD_IF_ERROR(FSE_buildCTable_wksp(nextCTable, norm, max, tableLog, entropyWorkspace, entropyWorkspaceSize));
 256             return NCountSize;
 257         }
 258     }
 259     default: assert(0); RETURN_ERROR(GENERIC);
 260     }
 261 }
 262
 263 FORCE_INLINE_TEMPLATE size_t
 264 ZSTD_encodeSequences_body(
 265             void* dst, size_t dstCapacity,
 266             FSE_CTable const* CTable_MatchLength, BYTE const* mlCodeTable,
 267             FSE_CTable const* CTable_OffsetBits, BYTE const* ofCodeTable,
 268             FSE_CTable const* CTable_LitLength, BYTE const* llCodeTable,
 269             seqDef const* sequences, size_t nbSeq, int longOffsets)
 270 {
 271     BIT_CStream_t blockStream;
 272     FSE_CState_t  stateMatchLength;
 273     FSE_CState_t  stateOffsetBits;
 274     FSE_CState_t  stateLitLength;
 275
 276     RETURN_ERROR_IF(
 277         ERR_isError(BIT_initCStream(&blockStream, dst, dstCapacity)),
 278         dstSize_tooSmall, "not enough space remaining");
 279     DEBUGLOG(6, "available space for bitstream : %i  (dstCapacity=%u)",
 280                 (int)(blockStream.endPtr - blockStream.startPtr),
 281                 (unsigned)dstCapacity);
 282
 283     /* first symbols */
 284     FSE_initCState2(&stateMatchLength, CTable_MatchLength, mlCodeTable[nbSeq-1]);
 285     FSE_initCState2(&stateOffsetBits,  CTable_OffsetBits,  ofCodeTable[nbSeq-1]);
 286     FSE_initCState2(&stateLitLength,   CTable_LitLength,   llCodeTable[nbSeq-1]);
 287     BIT_addBits(&blockStream, sequences[nbSeq-1].litLength, LL_bits[llCodeTable[nbSeq-1]]);
 288     if (MEM_32bits()) BIT_flushBits(&blockStream);
 289     BIT_addBits(&blockStream, sequences[nbSeq-1].matchLength, ML_bits[mlCodeTable[nbSeq-1]]);
 290     if (MEM_32bits()) BIT_flushBits(&blockStream);
 291     if (longOffsets) {
 292         U32 const ofBits = ofCodeTable[nbSeq-1];
 293         int const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN-1);
 294         if (extraBits) {
 295             BIT_addBits(&blockStream, sequences[nbSeq-1].offset, extraBits);
 296             BIT_flushBits(&blockStream);
 297         }
 298         BIT_addBits(&blockStream, sequences[nbSeq-1].offset >> extraBits,
 299                     ofBits - extraBits);
 300     } else {
 301         BIT_addBits(&blockStream, sequences[nbSeq-1].offset, ofCodeTable[nbSeq-1]);
 302     }
 303     BIT_flushBits(&blockStream);
 304
 305     {   size_t n;
 306         for (n=nbSeq-2 ; n<nbSeq ; n--) {      /* intentional underflow */
 307             BYTE const llCode = llCodeTable[n];
 308             BYTE const ofCode = ofCodeTable[n];
 309             BYTE const mlCode = mlCodeTable[n];
 310             U32  const llBits = LL_bits[llCode];
 311             U32  const ofBits = ofCode;
 312             U32  const mlBits = ML_bits[mlCode];
 313             DEBUGLOG(6, "encoding: litlen:%2u - matchlen:%2u - offCode:%7u",
 314                         (unsigned)sequences[n].litLength,
 315                         (unsigned)sequences[n].matchLength + MINMATCH,
 316                         (unsigned)sequences[n].offset);
 317                                                                             /* 32b*/  /* 64b*/
 318                                                                             /* (7)*/  /* (7)*/
 319             FSE_encodeSymbol(&blockStream, &stateOffsetBits, ofCode);       /* 15 */  /* 15 */
 320             FSE_encodeSymbol(&blockStream, &stateMatchLength, mlCode);      /* 24 */  /* 24 */
 321             if (MEM_32bits()) BIT_flushBits(&blockStream);                  /* (7)*/
 322             FSE_encodeSymbol(&blockStream, &stateLitLength, llCode);        /* 16 */  /* 33 */
 323             if (MEM_32bits() || (ofBits+mlBits+llBits >= 64-7-(LLFSELog+MLFSELog+OffFSELog)))
 324                 BIT_flushBits(&blockStream);                                /* (7)*/
 325             BIT_addBits(&blockStream, sequences[n].litLength, llBits);
 326             if (MEM_32bits() && ((llBits+mlBits)>24)) BIT_flushBits(&blockStream);
 327             BIT_addBits(&blockStream, sequences[n].matchLength, mlBits);
 328             if (MEM_32bits() || (ofBits+mlBits+llBits > 56)) BIT_flushBits(&blockStream);
 329             if (longOffsets) {
 330                 int const extraBits = ofBits - MIN(ofBits, STREAM_ACCUMULATOR_MIN-1);
 331                 if (extraBits) {
 332                     BIT_addBits(&blockStream, sequences[n].offset, extraBits);
 333                     BIT_flushBits(&blockStream);                            /* (7)*/
 334                 }
 335                 BIT_addBits(&blockStream, sequences[n].offset >> extraBits,
 336                             ofBits - extraBits);                            /* 31 */
 337             } else {
 338                 BIT_addBits(&blockStream, sequences[n].offset, ofBits);     /* 31 */
 339             }
 340             BIT_flushBits(&blockStream);                                    /* (7)*/
 341             DEBUGLOG(7, "remaining space : %i", (int)(blockStream.endPtr - blockStream.ptr));
 342     }   }
 343
 344     DEBUGLOG(6, "ZSTD_encodeSequences: flushing ML state with %u bits", stateMatchLength.stateLog);
 345     FSE_flushCState(&blockStream, &stateMatchLength);
 346     DEBUGLOG(6, "ZSTD_encodeSequences: flushing Off state with %u bits", stateOffsetBits.stateLog);
 347     FSE_flushCState(&blockStream, &stateOffsetBits);
 348     DEBUGLOG(6, "ZSTD_encodeSequences: flushing LL state with %u bits", stateLitLength.stateLog);
 349     FSE_flushCState(&blockStream, &stateLitLength);
 350
 351     {   size_t const streamSize = BIT_closeCStream(&blockStream);
 352         RETURN_ERROR_IF(streamSize==0, dstSize_tooSmall, "not enough space");
 353         return streamSize;
 354     }
 355 }
 356
 357 static size_t
 358 ZSTD_encodeSequences_default(
 359             void* dst, size_t dstCapacity,
 360             FSE_CTable const* CTable_MatchLength, BYTE const* mlCodeTable,
 361             FSE_CTable const* CTable_OffsetBits, BYTE const* ofCodeTable,
 362             FSE_CTable const* CTable_LitLength, BYTE const* llCodeTable,
 363             seqDef const* sequences, size_t nbSeq, int longOffsets)
 364 {
 365     return ZSTD_encodeSequences_body(dst, dstCapacity,
 366                                     CTable_MatchLength, mlCodeTable,
 367                                     CTable_OffsetBits, ofCodeTable,
 368                                     CTable_LitLength, llCodeTable,
 369                                     sequences, nbSeq, longOffsets);
 370 }
 371
 372
 373 #if DYNAMIC_BMI2
 374
 375 static TARGET_ATTRIBUTE("bmi2") size_t
 376 ZSTD_encodeSequences_bmi2(
 377             void* dst, size_t dstCapacity,
 378             FSE_CTable const* CTable_MatchLength, BYTE const* mlCodeTable,
 379             FSE_CTable const* CTable_OffsetBits, BYTE const* ofCodeTable,
 380             FSE_CTable const* CTable_LitLength, BYTE const* llCodeTable,
 381             seqDef const* sequences, size_t nbSeq, int longOffsets)
 382 {
 383     return ZSTD_encodeSequences_body(dst, dstCapacity,
 384                                     CTable_MatchLength, mlCodeTable,
 385                                     CTable_OffsetBits, ofCodeTable,
 386                                     CTable_LitLength, llCodeTable,
 387                                     sequences, nbSeq, longOffsets);
 388 }
 389
 390 #endif
 391
 392 size_t ZSTD_encodeSequences(
 393             void* dst, size_t dstCapacity,
 394             FSE_CTable const* CTable_MatchLength, BYTE const* mlCodeTable,
 395             FSE_CTable const* CTable_OffsetBits, BYTE const* ofCodeTable,
 396             FSE_CTable const* CTable_LitLength, BYTE const* llCodeTable,
 397             seqDef const* sequences, size_t nbSeq, int longOffsets, int bmi2)
 398 {
 399     DEBUGLOG(5, "ZSTD_encodeSequences: dstCapacity = %u", (unsigned)dstCapacity);
 400 #if DYNAMIC_BMI2
 401     if (bmi2) {
 402         return ZSTD_encodeSequences_bmi2(dst, dstCapacity,
 403                                          CTable_MatchLength, mlCodeTable,
 404                                          CTable_OffsetBits, ofCodeTable,
 405                                          CTable_LitLength, llCodeTable,
 406                                          sequences, nbSeq, longOffsets);
 407     }
 408 #endif
 409     (void)bmi2;
 410     return ZSTD_encodeSequences_default(dst, dstCapacity,
 411                                         CTable_MatchLength, mlCodeTable,
 412                                         CTable_OffsetBits, ofCodeTable,
 413                                         CTable_LitLength, llCodeTable,
 414                                         sequences, nbSeq, longOffsets);
 415 }