lib/zstd/entropy_common.c

   1 // SPDX-License-Identifier: (GPL-2.0 or BSD-2-Clause)
   2 /*
   3  * Common functions of New Generation Entropy library
   4  * Copyright (C) 2016, Yann Collet.
   5  *
   6  * You can contact the author at :
   7  * - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
   8  */
   9
  10 /* *************************************
  11 *  Dependencies
  12 ***************************************/
  13 #include "error_private.h" /* ERR_*, ERROR */
  14 #include "fse.h"
  15 #include "huf.h"
  16 #include "mem.h"
  17
  18 /*===   Version   ===*/
  19 unsigned FSE_versionNumber(void) { return FSE_VERSION_NUMBER; }
  20
  21 /*===   Error Management   ===*/
  22 unsigned FSE_isError(size_t code) { return ERR_isError(code); }
  23
  24 unsigned HUF_isError(size_t code) { return ERR_isError(code); }
  25
  26 /*-**************************************************************
  27 *  FSE NCount encoding-decoding
  28 ****************************************************************/
  29 size_t FSE_readNCount(short *normalizedCounter, unsigned *maxSVPtr, unsigned *tableLogPtr, const void *headerBuffer, size_t hbSize)
  30 {
  31         const BYTE *const istart = (const BYTE *)headerBuffer;
  32         const BYTE *const iend = istart + hbSize;
  33         const BYTE *ip = istart;
  34         int nbBits;
  35         int remaining;
  36         int threshold;
  37         U32 bitStream;
  38         int bitCount;
  39         unsigned charnum = 0;
  40         int previous0 = 0;
  41
  42         if (hbSize < 4)
  43                 return ERROR(srcSize_wrong);
  44         bitStream = ZSTD_readLE32(ip);
  45         nbBits = (bitStream & 0xF) + FSE_MIN_TABLELOG; /* extract tableLog */
  46         if (nbBits > FSE_TABLELOG_ABSOLUTE_MAX)
  47                 return ERROR(tableLog_tooLarge);
  48         bitStream >>= 4;
  49         bitCount = 4;
  50         *tableLogPtr = nbBits;
  51         remaining = (1 << nbBits) + 1;
  52         threshold = 1 << nbBits;
  53         nbBits++;
  54
  55         while ((remaining > 1) & (charnum <= *maxSVPtr)) {
  56                 if (previous0) {
  57                         unsigned n0 = charnum;
  58                         while ((bitStream & 0xFFFF) == 0xFFFF) {
  59                                 n0 += 24;
  60                                 if (ip < iend - 5) {
  61                                         ip += 2;
  62                                         bitStream = ZSTD_readLE32(ip) >> bitCount;
  63                                 } else {
  64                                         bitStream >>= 16;
  65                                         bitCount += 16;
  66                                 }
  67                         }
  68                         while ((bitStream & 3) == 3) {
  69                                 n0 += 3;
  70                                 bitStream >>= 2;
  71                                 bitCount += 2;
  72                         }
  73                         n0 += bitStream & 3;
  74                         bitCount += 2;
  75                         if (n0 > *maxSVPtr)
  76                                 return ERROR(maxSymbolValue_tooSmall);
  77                         while (charnum < n0)
  78                                 normalizedCounter[charnum++] = 0;
  79                         if ((ip <= iend - 7) || (ip + (bitCount >> 3) <= iend - 4)) {
  80                                 ip += bitCount >> 3;
  81                                 bitCount &= 7;
  82                                 bitStream = ZSTD_readLE32(ip) >> bitCount;
  83                         } else {
  84                                 bitStream >>= 2;
  85                         }
  86                 }
  87                 {
  88                         int const max = (2 * threshold - 1) - remaining;
  89                         int count;
  90
  91                         if ((bitStream & (threshold - 1)) < (U32)max) {
  92                                 count = bitStream & (threshold - 1);
  93                                 bitCount += nbBits - 1;
  94                         } else {
  95                                 count = bitStream & (2 * threshold - 1);
  96                                 if (count >= threshold)
  97                                         count -= max;
  98                                 bitCount += nbBits;
  99                         }
 100
 101                         count--;                                 /* extra accuracy */
 102                         remaining -= count < 0 ? -count : count; /* -1 means +1 */
 103                         normalizedCounter[charnum++] = (short)count;
 104                         previous0 = !count;
 105                         while (remaining < threshold) {
 106                                 nbBits--;
 107                                 threshold >>= 1;
 108                         }
 109
 110                         if ((ip <= iend - 7) || (ip + (bitCount >> 3) <= iend - 4)) {
 111                                 ip += bitCount >> 3;
 112                                 bitCount &= 7;
 113                         } else {
 114                                 bitCount -= (int)(8 * (iend - 4 - ip));
 115                                 ip = iend - 4;
 116                         }
 117                         bitStream = ZSTD_readLE32(ip) >> (bitCount & 31);
 118                 }
 119         } /* while ((remaining>1) & (charnum<=*maxSVPtr)) */
 120         if (remaining != 1)
 121                 return ERROR(corruption_detected);
 122         if (bitCount > 32)
 123                 return ERROR(corruption_detected);
 124         *maxSVPtr = charnum - 1;
 125
 126         ip += (bitCount + 7) >> 3;
 127         return ip - istart;
 128 }
 129
 130 /*! HUF_readStats() :
 131         Read compact Huffman tree, saved by HUF_writeCTable().
 132         `huffWeight` is destination buffer.
 133         `rankStats` is assumed to be a table of at least HUF_TABLELOG_MAX U32.
 134         @return : size read from `src` , or an error Code .
 135         Note : Needed by HUF_readCTable() and HUF_readDTableX?() .
 136 */
 137 size_t HUF_readStats_wksp(BYTE *huffWeight, size_t hwSize, U32 *rankStats, U32 *nbSymbolsPtr, U32 *tableLogPtr, const void *src, size_t srcSize, void *workspace, size_t workspaceSize)
 138 {
 139         U32 weightTotal;
 140         const BYTE *ip = (const BYTE *)src;
 141         size_t iSize;
 142         size_t oSize;
 143
 144         if (!srcSize)
 145                 return ERROR(srcSize_wrong);
 146         iSize = ip[0];
 147         /* memset(huffWeight, 0, hwSize);   */ /* is not necessary, even though some analyzer complain ... */
 148
 149         if (iSize >= 128) { /* special header */
 150                 oSize = iSize - 127;
 151                 iSize = ((oSize + 1) / 2);
 152                 if (iSize + 1 > srcSize)
 153                         return ERROR(srcSize_wrong);
 154                 if (oSize >= hwSize)
 155                         return ERROR(corruption_detected);
 156                 ip += 1;
 157                 {
 158                         U32 n;
 159                         for (n = 0; n < oSize; n += 2) {
 160                                 huffWeight[n] = ip[n / 2] >> 4;
 161                                 huffWeight[n + 1] = ip[n / 2] & 15;
 162                         }
 163                 }
 164         } else {                                                 /* header compressed with FSE (normal case) */
 165                 if (iSize + 1 > srcSize)
 166                         return ERROR(srcSize_wrong);
 167                 oSize = FSE_decompress_wksp(huffWeight, hwSize - 1, ip + 1, iSize, 6, workspace, workspaceSize); /* max (hwSize-1) values decoded, as last one is implied */
 168                 if (FSE_isError(oSize))
 169                         return oSize;
 170         }
 171
 172         /* collect weight stats */
 173         memset(rankStats, 0, (HUF_TABLELOG_MAX + 1) * sizeof(U32));
 174         weightTotal = 0;
 175         {
 176                 U32 n;
 177                 for (n = 0; n < oSize; n++) {
 178                         if (huffWeight[n] >= HUF_TABLELOG_MAX)
 179                                 return ERROR(corruption_detected);
 180                         rankStats[huffWeight[n]]++;
 181                         weightTotal += (1 << huffWeight[n]) >> 1;
 182                 }
 183         }
 184         if (weightTotal == 0)
 185                 return ERROR(corruption_detected);
 186
 187         /* get last non-null symbol weight (implied, total must be 2^n) */
 188         {
 189                 U32 const tableLog = BIT_highbit32(weightTotal) + 1;
 190                 if (tableLog > HUF_TABLELOG_MAX)
 191                         return ERROR(corruption_detected);
 192                 *tableLogPtr = tableLog;
 193                 /* determine last weight */
 194                 {
 195                         U32 const total = 1 << tableLog;
 196                         U32 const rest = total - weightTotal;
 197                         U32 const verif = 1 << BIT_highbit32(rest);
 198                         U32 const lastWeight = BIT_highbit32(rest) + 1;
 199                         if (verif != rest)
 200                                 return ERROR(corruption_detected); /* last value must be a clean power of 2 */
 201                         huffWeight[oSize] = (BYTE)lastWeight;
 202                         rankStats[lastWeight]++;
 203                 }
 204         }
 205
 206         /* check tree construction validity */
 207         if ((rankStats[1] < 2) || (rankStats[1] & 1))
 208                 return ERROR(corruption_detected); /* by construction : at least 2 elts of rank 1, must be even */
 209
 210         /* results */
 211         *nbSymbolsPtr = (U32)(oSize + 1);
 212         return iSize + 1;
 213 }