LXR uboot/lib/zstd/entropy

   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   ===*/
  19unsigned FSE_versionNumber(void) { return FSE_VERSION_NUMBER; }
  20
  21/*===   Error Management   ===*/
  22unsigned FSE_isError(size_t code) { return ERR_isError(code); }
  23
  24unsigned HUF_isError(size_t code) { return ERR_isError(code); }
  25
  26/*-**************************************************************
  27*  FSE NCount encoding-decoding
  28****************************************************************/
  29size_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*/
 137size_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}
 214