^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) * Common functions of New Generation Entropy library
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) * Copyright (C) 2016, Yann Collet.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) * Redistribution and use in source and binary forms, with or without
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) * modification, are permitted provided that the following conditions are
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) * met:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) * * Redistributions of source code must retain the above copyright
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) * notice, this list of conditions and the following disclaimer.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) * * Redistributions in binary form must reproduce the above
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) * copyright notice, this list of conditions and the following disclaimer
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) * in the documentation and/or other materials provided with the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) * distribution.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28) * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) * This program is free software; you can redistribute it and/or modify it under
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) * the terms of the GNU General Public License version 2 as published by the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) * Free Software Foundation. This program is dual-licensed; you may select
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) * either version 2 of the GNU General Public License ("GPL") or BSD license
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) * ("BSD").
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) * You can contact the author at :
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) * - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) /* *************************************
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) * Dependencies
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) ***************************************/
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) #include "error_private.h" /* ERR_*, ERROR */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) #include "fse.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) #include "huf.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) #include "mem.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) /*=== Version ===*/
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) unsigned FSE_versionNumber(void) { return FSE_VERSION_NUMBER; }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) /*=== Error Management ===*/
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) unsigned FSE_isError(size_t code) { return ERR_isError(code); }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) unsigned HUF_isError(size_t code) { return ERR_isError(code); }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) /*-**************************************************************
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) * FSE NCount encoding-decoding
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) ****************************************************************/
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) size_t FSE_readNCount(short *normalizedCounter, unsigned *maxSVPtr, unsigned *tableLogPtr, const void *headerBuffer, size_t hbSize)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) const BYTE *const istart = (const BYTE *)headerBuffer;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) const BYTE *const iend = istart + hbSize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) const BYTE *ip = istart;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) int nbBits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) int remaining;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) int threshold;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) U32 bitStream;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) int bitCount;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) unsigned charnum = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) int previous0 = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) if (hbSize < 4)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) return ERROR(srcSize_wrong);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) bitStream = ZSTD_readLE32(ip);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) nbBits = (bitStream & 0xF) + FSE_MIN_TABLELOG; /* extract tableLog */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) if (nbBits > FSE_TABLELOG_ABSOLUTE_MAX)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) return ERROR(tableLog_tooLarge);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) bitStream >>= 4;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) bitCount = 4;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) *tableLogPtr = nbBits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) remaining = (1 << nbBits) + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) threshold = 1 << nbBits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) nbBits++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) while ((remaining > 1) & (charnum <= *maxSVPtr)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) if (previous0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) unsigned n0 = charnum;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) while ((bitStream & 0xFFFF) == 0xFFFF) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) n0 += 24;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) if (ip < iend - 5) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) ip += 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) bitStream = ZSTD_readLE32(ip) >> bitCount;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) bitStream >>= 16;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) bitCount += 16;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) while ((bitStream & 3) == 3) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) n0 += 3;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) bitStream >>= 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) bitCount += 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) n0 += bitStream & 3;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) bitCount += 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) if (n0 > *maxSVPtr)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) return ERROR(maxSymbolValue_tooSmall);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) while (charnum < n0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) normalizedCounter[charnum++] = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) if ((ip <= iend - 7) || (ip + (bitCount >> 3) <= iend - 4)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) ip += bitCount >> 3;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) bitCount &= 7;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) bitStream = ZSTD_readLE32(ip) >> bitCount;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) bitStream >>= 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) int const max = (2 * threshold - 1) - remaining;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) int count;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) if ((bitStream & (threshold - 1)) < (U32)max) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) count = bitStream & (threshold - 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) bitCount += nbBits - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) count = bitStream & (2 * threshold - 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) if (count >= threshold)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) count -= max;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) bitCount += nbBits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) count--; /* extra accuracy */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) remaining -= count < 0 ? -count : count; /* -1 means +1 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133) normalizedCounter[charnum++] = (short)count;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) previous0 = !count;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) while (remaining < threshold) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136) nbBits--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) threshold >>= 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) if ((ip <= iend - 7) || (ip + (bitCount >> 3) <= iend - 4)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) ip += bitCount >> 3;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) bitCount &= 7;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) bitCount -= (int)(8 * (iend - 4 - ip));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) ip = iend - 4;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147) bitStream = ZSTD_readLE32(ip) >> (bitCount & 31);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) } /* while ((remaining>1) & (charnum<=*maxSVPtr)) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) if (remaining != 1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151) return ERROR(corruption_detected);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152) if (bitCount > 32)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153) return ERROR(corruption_detected);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154) *maxSVPtr = charnum - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156) ip += (bitCount + 7) >> 3;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157) return ip - istart;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160) /*! HUF_readStats() :
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161) Read compact Huffman tree, saved by HUF_writeCTable().
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162) `huffWeight` is destination buffer.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163) `rankStats` is assumed to be a table of at least HUF_TABLELOG_MAX U32.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164) @return : size read from `src` , or an error Code .
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165) Note : Needed by HUF_readCTable() and HUF_readDTableX?() .
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167) 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)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169) U32 weightTotal;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170) const BYTE *ip = (const BYTE *)src;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171) size_t iSize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172) size_t oSize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174) if (!srcSize)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175) return ERROR(srcSize_wrong);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176) iSize = ip[0];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177) /* memset(huffWeight, 0, hwSize); */ /* is not necessary, even though some analyzer complain ... */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179) if (iSize >= 128) { /* special header */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180) oSize = iSize - 127;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181) iSize = ((oSize + 1) / 2);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182) if (iSize + 1 > srcSize)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183) return ERROR(srcSize_wrong);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184) if (oSize >= hwSize)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185) return ERROR(corruption_detected);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186) ip += 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188) U32 n;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189) for (n = 0; n < oSize; n += 2) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190) huffWeight[n] = ip[n / 2] >> 4;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 191) huffWeight[n + 1] = ip[n / 2] & 15;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 192) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 193) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 194) } else { /* header compressed with FSE (normal case) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 195) if (iSize + 1 > srcSize)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 196) return ERROR(srcSize_wrong);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 197) oSize = FSE_decompress_wksp(huffWeight, hwSize - 1, ip + 1, iSize, 6, workspace, workspaceSize); /* max (hwSize-1) values decoded, as last one is implied */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 198) if (FSE_isError(oSize))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 199) return oSize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 200) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 201)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 202) /* collect weight stats */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 203) memset(rankStats, 0, (HUF_TABLELOG_MAX + 1) * sizeof(U32));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 204) weightTotal = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 205) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 206) U32 n;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 207) for (n = 0; n < oSize; n++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 208) if (huffWeight[n] >= HUF_TABLELOG_MAX)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 209) return ERROR(corruption_detected);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 210) rankStats[huffWeight[n]]++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 211) weightTotal += (1 << huffWeight[n]) >> 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 212) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 213) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 214) if (weightTotal == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 215) return ERROR(corruption_detected);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 216)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 217) /* get last non-null symbol weight (implied, total must be 2^n) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 218) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 219) U32 const tableLog = BIT_highbit32(weightTotal) + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 220) if (tableLog > HUF_TABLELOG_MAX)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 221) return ERROR(corruption_detected);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 222) *tableLogPtr = tableLog;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 223) /* determine last weight */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 224) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 225) U32 const total = 1 << tableLog;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 226) U32 const rest = total - weightTotal;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 227) U32 const verif = 1 << BIT_highbit32(rest);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 228) U32 const lastWeight = BIT_highbit32(rest) + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 229) if (verif != rest)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 230) return ERROR(corruption_detected); /* last value must be a clean power of 2 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 231) huffWeight[oSize] = (BYTE)lastWeight;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 232) rankStats[lastWeight]++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 233) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 234) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 235)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 236) /* check tree construction validity */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 237) if ((rankStats[1] < 2) || (rankStats[1] & 1))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 238) return ERROR(corruption_detected); /* by construction : at least 2 elts of rank 1, must be even */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 239)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 240) /* results */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 241) *nbSymbolsPtr = (U32)(oSize + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 242) return iSize + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 243) }
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags