lib/zstd/fse_decompress.c

   1 // SPDX-License-Identifier: (GPL-2.0 or BSD-2-Clause)
   2 /*
   3  * FSE : Finite State Entropy decoder
   4  * Copyright (C) 2013-2015, Yann Collet.
   5  *
   6  * You can contact the author at :
   7  * - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
   8  */
   9
  10 /* **************************************************************
  11 *  Compiler specifics
  12 ****************************************************************/
  13 #define FORCE_INLINE static __always_inline
  14
  15 /* **************************************************************
  16 *  Includes
  17 ****************************************************************/
  18 #include "bitstream.h"
  19 #include "fse.h"
  20 #include <linux/compiler.h>
  21 #include <linux/kernel.h>
  22 #include <linux/string.h> /* memcpy, memset */
  23
  24 /* **************************************************************
  25 *  Error Management
  26 ****************************************************************/
  27 #define FSE_isError ERR_isError
  28 #define FSE_STATIC_ASSERT(c)                                   \
  29         {                                                      \
  30                 enum { FSE_static_assert = 1 / (int)(!!(c)) }; \
  31         } /* use only *after* variable declarations */
  32
  33 /* check and forward error code */
  34 #define CHECK_F(f)                  \
  35         {                           \
  36                 size_t const e = f; \
  37                 if (FSE_isError(e)) \
  38                         return e;   \
  39         }
  40
  41 /* **************************************************************
  42 *  Templates
  43 ****************************************************************/
  44 /*
  45   designed to be included
  46   for type-specific functions (template emulation in C)
  47   Objective is to write these functions only once, for improved maintenance
  48 */
  49
  50 /* safety checks */
  51 #ifndef FSE_FUNCTION_EXTENSION
  52 #error "FSE_FUNCTION_EXTENSION must be defined"
  53 #endif
  54 #ifndef FSE_FUNCTION_TYPE
  55 #error "FSE_FUNCTION_TYPE must be defined"
  56 #endif
  57
  58 /* Function names */
  59 #define FSE_CAT(X, Y) X##Y
  60 #define FSE_FUNCTION_NAME(X, Y) FSE_CAT(X, Y)
  61 #define FSE_TYPE_NAME(X, Y) FSE_CAT(X, Y)
  62
  63 /* Function templates */
  64
  65 size_t FSE_buildDTable_wksp(FSE_DTable *dt, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, void *workspace, size_t workspaceSize)
  66 {
  67         void *const tdPtr = dt + 1; /* because *dt is unsigned, 32-bits aligned on 32-bits */
  68         FSE_DECODE_TYPE *const tableDecode = (FSE_DECODE_TYPE *)(tdPtr);
  69         U16 *symbolNext = (U16 *)workspace;
  70
  71         U32 const maxSV1 = maxSymbolValue + 1;
  72         U32 const tableSize = 1 << tableLog;
  73         U32 highThreshold = tableSize - 1;
  74
  75         /* Sanity Checks */
  76         if (workspaceSize < sizeof(U16) * (FSE_MAX_SYMBOL_VALUE + 1))
  77                 return ERROR(tableLog_tooLarge);
  78         if (maxSymbolValue > FSE_MAX_SYMBOL_VALUE)
  79                 return ERROR(maxSymbolValue_tooLarge);
  80         if (tableLog > FSE_MAX_TABLELOG)
  81                 return ERROR(tableLog_tooLarge);
  82
  83         /* Init, lay down lowprob symbols */
  84         {
  85                 FSE_DTableHeader DTableH;
  86                 DTableH.tableLog = (U16)tableLog;
  87                 DTableH.fastMode = 1;
  88                 {
  89                         S16 const largeLimit = (S16)(1 << (tableLog - 1));
  90                         U32 s;
  91                         for (s = 0; s < maxSV1; s++) {
  92                                 if (normalizedCounter[s] == -1) {
  93                                         tableDecode[highThreshold--].symbol = (FSE_FUNCTION_TYPE)s;
  94                                         symbolNext[s] = 1;
  95                                 } else {
  96                                         if (normalizedCounter[s] >= largeLimit)
  97                                                 DTableH.fastMode = 0;
  98                                         symbolNext[s] = normalizedCounter[s];
  99                                 }
 100                         }
 101                 }
 102                 memcpy(dt, &DTableH, sizeof(DTableH));
 103         }
 104
 105         /* Spread symbols */
 106         {
 107                 U32 const tableMask = tableSize - 1;
 108                 U32 const step = FSE_TABLESTEP(tableSize);
 109                 U32 s, position = 0;
 110                 for (s = 0; s < maxSV1; s++) {
 111                         int i;
 112                         for (i = 0; i < normalizedCounter[s]; i++) {
 113                                 tableDecode[position].symbol = (FSE_FUNCTION_TYPE)s;
 114                                 position = (position + step) & tableMask;
 115                                 while (position > highThreshold)
 116                                         position = (position + step) & tableMask; /* lowprob area */
 117                         }
 118                 }
 119                 if (position != 0)
 120                         return ERROR(GENERIC); /* position must reach all cells once, otherwise normalizedCounter is incorrect */
 121         }
 122
 123         /* Build Decoding table */
 124         {
 125                 U32 u;
 126                 for (u = 0; u < tableSize; u++) {
 127                         FSE_FUNCTION_TYPE const symbol = (FSE_FUNCTION_TYPE)(tableDecode[u].symbol);
 128                         U16 nextState = symbolNext[symbol]++;
 129                         tableDecode[u].nbBits = (BYTE)(tableLog - BIT_highbit32((U32)nextState));
 130                         tableDecode[u].newState = (U16)((nextState << tableDecode[u].nbBits) - tableSize);
 131                 }
 132         }
 133
 134         return 0;
 135 }
 136
 137 /*-*******************************************************
 138 *  Decompression (Byte symbols)
 139 *********************************************************/
 140 size_t FSE_buildDTable_rle(FSE_DTable *dt, BYTE symbolValue)
 141 {
 142         void *ptr = dt;
 143         FSE_DTableHeader *const DTableH = (FSE_DTableHeader *)ptr;
 144         void *dPtr = dt + 1;
 145         FSE_decode_t *const cell = (FSE_decode_t *)dPtr;
 146
 147         DTableH->tableLog = 0;
 148         DTableH->fastMode = 0;
 149
 150         cell->newState = 0;
 151         cell->symbol = symbolValue;
 152         cell->nbBits = 0;
 153
 154         return 0;
 155 }
 156
 157 size_t FSE_buildDTable_raw(FSE_DTable *dt, unsigned nbBits)
 158 {
 159         void *ptr = dt;
 160         FSE_DTableHeader *const DTableH = (FSE_DTableHeader *)ptr;
 161         void *dPtr = dt + 1;
 162         FSE_decode_t *const dinfo = (FSE_decode_t *)dPtr;
 163         const unsigned tableSize = 1 << nbBits;
 164         const unsigned tableMask = tableSize - 1;
 165         const unsigned maxSV1 = tableMask + 1;
 166         unsigned s;
 167
 168         /* Sanity checks */
 169         if (nbBits < 1)
 170                 return ERROR(GENERIC); /* min size */
 171
 172         /* Build Decoding Table */
 173         DTableH->tableLog = (U16)nbBits;
 174         DTableH->fastMode = 1;
 175         for (s = 0; s < maxSV1; s++) {
 176                 dinfo[s].newState = 0;
 177                 dinfo[s].symbol = (BYTE)s;
 178                 dinfo[s].nbBits = (BYTE)nbBits;
 179         }
 180
 181         return 0;
 182 }
 183
 184 FORCE_INLINE size_t FSE_decompress_usingDTable_generic(void *dst, size_t maxDstSize, const void *cSrc, size_t cSrcSize, const FSE_DTable *dt,
 185                                                        const unsigned fast)
 186 {
 187         BYTE *const ostart = (BYTE *)dst;
 188         BYTE *op = ostart;
 189         BYTE *const omax = op + maxDstSize;
 190         BYTE *const olimit = omax - 3;
 191
 192         BIT_DStream_t bitD;
 193         FSE_DState_t state1;
 194         FSE_DState_t state2;
 195
 196         /* Init */
 197         CHECK_F(BIT_initDStream(&bitD, cSrc, cSrcSize));
 198
 199         FSE_initDState(&state1, &bitD, dt);
 200         FSE_initDState(&state2, &bitD, dt);
 201
 202 #define FSE_GETSYMBOL(statePtr) fast ? FSE_decodeSymbolFast(statePtr, &bitD) : FSE_decodeSymbol(statePtr, &bitD)
 203
 204         /* 4 symbols per loop */
 205         for (; (BIT_reloadDStream(&bitD) == BIT_DStream_unfinished) & (op < olimit); op += 4) {
 206                 op[0] = FSE_GETSYMBOL(&state1);
 207
 208                 if (FSE_MAX_TABLELOG * 2 + 7 > sizeof(bitD.bitContainer) * 8) /* This test must be static */
 209                         BIT_reloadDStream(&bitD);
 210
 211                 op[1] = FSE_GETSYMBOL(&state2);
 212
 213                 if (FSE_MAX_TABLELOG * 4 + 7 > sizeof(bitD.bitContainer) * 8) /* This test must be static */
 214                 {
 215                         if (BIT_reloadDStream(&bitD) > BIT_DStream_unfinished) {
 216                                 op += 2;
 217                                 break;
 218                         }
 219                 }
 220
 221                 op[2] = FSE_GETSYMBOL(&state1);
 222
 223                 if (FSE_MAX_TABLELOG * 2 + 7 > sizeof(bitD.bitContainer) * 8) /* This test must be static */
 224                         BIT_reloadDStream(&bitD);
 225
 226                 op[3] = FSE_GETSYMBOL(&state2);
 227         }
 228
 229         /* tail */
 230         /* note : BIT_reloadDStream(&bitD) >= FSE_DStream_partiallyFilled; Ends at exactly BIT_DStream_completed */
 231         while (1) {
 232                 if (op > (omax - 2))
 233                         return ERROR(dstSize_tooSmall);
 234                 *op++ = FSE_GETSYMBOL(&state1);
 235                 if (BIT_reloadDStream(&bitD) == BIT_DStream_overflow) {
 236                         *op++ = FSE_GETSYMBOL(&state2);
 237                         break;
 238                 }
 239
 240                 if (op > (omax - 2))
 241                         return ERROR(dstSize_tooSmall);
 242                 *op++ = FSE_GETSYMBOL(&state2);
 243                 if (BIT_reloadDStream(&bitD) == BIT_DStream_overflow) {
 244                         *op++ = FSE_GETSYMBOL(&state1);
 245                         break;
 246                 }
 247         }
 248
 249         return op - ostart;
 250 }
 251
 252 size_t FSE_decompress_usingDTable(void *dst, size_t originalSize, const void *cSrc, size_t cSrcSize, const FSE_DTable *dt)
 253 {
 254         const void *ptr = dt;
 255         const FSE_DTableHeader *DTableH = (const FSE_DTableHeader *)ptr;
 256         const U32 fastMode = DTableH->fastMode;
 257
 258         /* select fast mode (static) */
 259         if (fastMode)
 260                 return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 1);
 261         return FSE_decompress_usingDTable_generic(dst, originalSize, cSrc, cSrcSize, dt, 0);
 262 }
 263
 264 size_t FSE_decompress_wksp(void *dst, size_t dstCapacity, const void *cSrc, size_t cSrcSize, unsigned maxLog, void *workspace, size_t workspaceSize)
 265 {
 266         const BYTE *const istart = (const BYTE *)cSrc;
 267         const BYTE *ip = istart;
 268         unsigned tableLog;
 269         unsigned maxSymbolValue = FSE_MAX_SYMBOL_VALUE;
 270         size_t NCountLength;
 271
 272         FSE_DTable *dt;
 273         short *counting;
 274         size_t spaceUsed32 = 0;
 275
 276         FSE_STATIC_ASSERT(sizeof(FSE_DTable) == sizeof(U32));
 277
 278         dt = (FSE_DTable *)((U32 *)workspace + spaceUsed32);
 279         spaceUsed32 += FSE_DTABLE_SIZE_U32(maxLog);
 280         counting = (short *)((U32 *)workspace + spaceUsed32);
 281         spaceUsed32 += ALIGN(sizeof(short) * (FSE_MAX_SYMBOL_VALUE + 1), sizeof(U32)) >> 2;
 282
 283         if ((spaceUsed32 << 2) > workspaceSize)
 284                 return ERROR(tableLog_tooLarge);
 285         workspace = (U32 *)workspace + spaceUsed32;
 286         workspaceSize -= (spaceUsed32 << 2);
 287
 288         /* normal FSE decoding mode */
 289         NCountLength = FSE_readNCount(counting, &maxSymbolValue, &tableLog, istart, cSrcSize);
 290         if (FSE_isError(NCountLength))
 291                 return NCountLength;
 292         // if (NCountLength >= cSrcSize) return ERROR(srcSize_wrong);   /* too small input size; supposed to be already checked in NCountLength, only remaining
 293         // case : NCountLength==cSrcSize */
 294         if (tableLog > maxLog)
 295                 return ERROR(tableLog_tooLarge);
 296         ip += NCountLength;
 297         cSrcSize -= NCountLength;
 298
 299         CHECK_F(FSE_buildDTable_wksp(dt, counting, maxSymbolValue, tableLog, workspace, workspaceSize));
 300
 301         return FSE_decompress_usingDTable(dst, dstCapacity, ip, cSrcSize, dt); /* always return, even if it is an error code */
 302 }