^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) * FSE : Finite State Entropy encoder
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) * Copyright (C) 2013-2015, 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) * Compiler specifics
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) ****************************************************************/
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) #define FORCE_INLINE static __always_inline
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) /* **************************************************************
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) * Includes
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) ****************************************************************/
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) #include "bitstream.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) #include "fse.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) #include <linux/compiler.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) #include <linux/kernel.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) #include <linux/math64.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) #include <linux/string.h> /* memcpy, memset */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) /* **************************************************************
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) * Error Management
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) ****************************************************************/
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) #define FSE_STATIC_ASSERT(c) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) enum { FSE_static_assert = 1 / (int)(!!(c)) }; \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) } /* use only *after* variable declarations */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) /* **************************************************************
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) * Templates
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) ****************************************************************/
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) designed to be included
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) for type-specific functions (template emulation in C)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) Objective is to write these functions only once, for improved maintenance
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) /* safety checks */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) #ifndef FSE_FUNCTION_EXTENSION
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) #error "FSE_FUNCTION_EXTENSION must be defined"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) #ifndef FSE_FUNCTION_TYPE
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) #error "FSE_FUNCTION_TYPE must be defined"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) #endif
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) /* Function names */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) #define FSE_CAT(X, Y) X##Y
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) #define FSE_FUNCTION_NAME(X, Y) FSE_CAT(X, Y)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) #define FSE_TYPE_NAME(X, Y) FSE_CAT(X, Y)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) /* Function templates */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) /* FSE_buildCTable_wksp() :
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) * Same as FSE_buildCTable(), but using an externally allocated scratch buffer (`workSpace`).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) * wkspSize should be sized to handle worst case situation, which is `1<<max_tableLog * sizeof(FSE_FUNCTION_TYPE)`
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) * workSpace must also be properly aligned with FSE_FUNCTION_TYPE requirements
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) size_t FSE_buildCTable_wksp(FSE_CTable *ct, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, void *workspace, size_t workspaceSize)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) U32 const tableSize = 1 << tableLog;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) U32 const tableMask = tableSize - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) void *const ptr = ct;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) U16 *const tableU16 = ((U16 *)ptr) + 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) void *const FSCT = ((U32 *)ptr) + 1 /* header */ + (tableLog ? tableSize >> 1 : 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) FSE_symbolCompressionTransform *const symbolTT = (FSE_symbolCompressionTransform *)(FSCT);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) U32 const step = FSE_TABLESTEP(tableSize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) U32 highThreshold = tableSize - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) U32 *cumul;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) FSE_FUNCTION_TYPE *tableSymbol;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) size_t spaceUsed32 = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) cumul = (U32 *)workspace + spaceUsed32;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) spaceUsed32 += FSE_MAX_SYMBOL_VALUE + 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) tableSymbol = (FSE_FUNCTION_TYPE *)((U32 *)workspace + spaceUsed32);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) spaceUsed32 += ALIGN(sizeof(FSE_FUNCTION_TYPE) * ((size_t)1 << tableLog), sizeof(U32)) >> 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) if ((spaceUsed32 << 2) > workspaceSize)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) return ERROR(tableLog_tooLarge);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) workspace = (U32 *)workspace + spaceUsed32;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) workspaceSize -= (spaceUsed32 << 2);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) /* CTable header */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) tableU16[-2] = (U16)tableLog;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) tableU16[-1] = (U16)maxSymbolValue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) /* For explanations on how to distribute symbol values over the table :
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) * http://fastcompression.blogspot.fr/2014/02/fse-distributing-symbol-values.html */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) /* symbol start positions */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) U32 u;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) cumul[0] = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) for (u = 1; u <= maxSymbolValue + 1; u++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) if (normalizedCounter[u - 1] == -1) { /* Low proba symbol */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) cumul[u] = cumul[u - 1] + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) tableSymbol[highThreshold--] = (FSE_FUNCTION_TYPE)(u - 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133) cumul[u] = cumul[u - 1] + normalizedCounter[u - 1];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136) cumul[maxSymbolValue + 1] = tableSize + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) /* Spread symbols */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) U32 position = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) U32 symbol;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143) for (symbol = 0; symbol <= maxSymbolValue; symbol++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) int nbOccurences;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) for (nbOccurences = 0; nbOccurences < normalizedCounter[symbol]; nbOccurences++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146) tableSymbol[position] = (FSE_FUNCTION_TYPE)symbol;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147) position = (position + step) & tableMask;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148) while (position > highThreshold)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) position = (position + step) & tableMask; /* Low proba area */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153) if (position != 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154) return ERROR(GENERIC); /* Must have gone through all positions */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157) /* Build table */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159) U32 u;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160) for (u = 0; u < tableSize; u++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161) FSE_FUNCTION_TYPE s = tableSymbol[u]; /* note : static analyzer may not understand tableSymbol is properly initialized */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162) tableU16[cumul[s]++] = (U16)(tableSize + u); /* TableU16 : sorted by symbol order; gives next state value */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166) /* Build Symbol Transformation Table */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168) unsigned total = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169) unsigned s;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170) for (s = 0; s <= maxSymbolValue; s++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171) switch (normalizedCounter[s]) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172) case 0: break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174) case -1:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175) case 1:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176) symbolTT[s].deltaNbBits = (tableLog << 16) - (1 << tableLog);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177) symbolTT[s].deltaFindState = total - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178) total++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180) default: {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181) U32 const maxBitsOut = tableLog - BIT_highbit32(normalizedCounter[s] - 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182) U32 const minStatePlus = normalizedCounter[s] << maxBitsOut;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183) symbolTT[s].deltaNbBits = (maxBitsOut << 16) - minStatePlus;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184) symbolTT[s].deltaFindState = total - normalizedCounter[s];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185) total += normalizedCounter[s];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 191) return 0;
^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) /*-**************************************************************
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 195) * FSE NCount encoding-decoding
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 196) ****************************************************************/
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 197) size_t FSE_NCountWriteBound(unsigned maxSymbolValue, unsigned tableLog)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 198) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 199) size_t const maxHeaderSize = (((maxSymbolValue + 1) * tableLog) >> 3) + 3;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 200) return maxSymbolValue ? maxHeaderSize : FSE_NCOUNTBOUND; /* maxSymbolValue==0 ? use default */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 201) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 202)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 203) static size_t FSE_writeNCount_generic(void *header, size_t headerBufferSize, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 204) unsigned writeIsSafe)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 205) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 206) BYTE *const ostart = (BYTE *)header;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 207) BYTE *out = ostart;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 208) BYTE *const oend = ostart + headerBufferSize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 209) int nbBits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 210) const int tableSize = 1 << tableLog;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 211) int remaining;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 212) int threshold;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 213) U32 bitStream;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 214) int bitCount;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 215) unsigned charnum = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 216) int previous0 = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 217)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 218) bitStream = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 219) bitCount = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 220) /* Table Size */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 221) bitStream += (tableLog - FSE_MIN_TABLELOG) << bitCount;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 222) bitCount += 4;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 223)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 224) /* Init */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 225) remaining = tableSize + 1; /* +1 for extra accuracy */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 226) threshold = tableSize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 227) nbBits = tableLog + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 228)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 229) while (remaining > 1) { /* stops at 1 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 230) if (previous0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 231) unsigned start = charnum;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 232) while (!normalizedCounter[charnum])
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 233) charnum++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 234) while (charnum >= start + 24) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 235) start += 24;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 236) bitStream += 0xFFFFU << bitCount;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 237) if ((!writeIsSafe) && (out > oend - 2))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 238) return ERROR(dstSize_tooSmall); /* Buffer overflow */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 239) out[0] = (BYTE)bitStream;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 240) out[1] = (BYTE)(bitStream >> 8);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 241) out += 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 242) bitStream >>= 16;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 243) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 244) while (charnum >= start + 3) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 245) start += 3;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 246) bitStream += 3 << bitCount;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 247) bitCount += 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 248) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 249) bitStream += (charnum - start) << bitCount;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 250) bitCount += 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 251) if (bitCount > 16) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 252) if ((!writeIsSafe) && (out > oend - 2))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 253) return ERROR(dstSize_tooSmall); /* Buffer overflow */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 254) out[0] = (BYTE)bitStream;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 255) out[1] = (BYTE)(bitStream >> 8);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 256) out += 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 257) bitStream >>= 16;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 258) bitCount -= 16;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 259) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 260) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 261) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 262) int count = normalizedCounter[charnum++];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 263) int const max = (2 * threshold - 1) - remaining;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 264) remaining -= count < 0 ? -count : count;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 265) count++; /* +1 for extra accuracy */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 266) if (count >= threshold)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 267) count += max; /* [0..max[ [max..threshold[ (...) [threshold+max 2*threshold[ */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 268) bitStream += count << bitCount;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 269) bitCount += nbBits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 270) bitCount -= (count < max);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 271) previous0 = (count == 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 272) if (remaining < 1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 273) return ERROR(GENERIC);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 274) while (remaining < threshold)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 275) nbBits--, threshold >>= 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 276) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 277) if (bitCount > 16) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 278) if ((!writeIsSafe) && (out > oend - 2))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 279) return ERROR(dstSize_tooSmall); /* Buffer overflow */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 280) out[0] = (BYTE)bitStream;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 281) out[1] = (BYTE)(bitStream >> 8);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 282) out += 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 283) bitStream >>= 16;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 284) bitCount -= 16;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 285) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 286) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 287)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 288) /* flush remaining bitStream */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 289) if ((!writeIsSafe) && (out > oend - 2))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 290) return ERROR(dstSize_tooSmall); /* Buffer overflow */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 291) out[0] = (BYTE)bitStream;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 292) out[1] = (BYTE)(bitStream >> 8);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 293) out += (bitCount + 7) / 8;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 294)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 295) if (charnum > maxSymbolValue + 1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 296) return ERROR(GENERIC);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 297)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 298) return (out - ostart);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 299) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 300)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 301) size_t FSE_writeNCount(void *buffer, size_t bufferSize, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 302) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 303) if (tableLog > FSE_MAX_TABLELOG)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 304) return ERROR(tableLog_tooLarge); /* Unsupported */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 305) if (tableLog < FSE_MIN_TABLELOG)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 306) return ERROR(GENERIC); /* Unsupported */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 307)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 308) if (bufferSize < FSE_NCountWriteBound(maxSymbolValue, tableLog))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 309) return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 310)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 311) return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 312) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 313)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 314) /*-**************************************************************
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 315) * Counting histogram
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 316) ****************************************************************/
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 317) /*! FSE_count_simple
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 318) This function counts byte values within `src`, and store the histogram into table `count`.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 319) It doesn't use any additional memory.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 320) But this function is unsafe : it doesn't check that all values within `src` can fit into `count`.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 321) For this reason, prefer using a table `count` with 256 elements.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 322) @return : count of most numerous element
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 323) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 324) size_t FSE_count_simple(unsigned *count, unsigned *maxSymbolValuePtr, const void *src, size_t srcSize)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 325) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 326) const BYTE *ip = (const BYTE *)src;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 327) const BYTE *const end = ip + srcSize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 328) unsigned maxSymbolValue = *maxSymbolValuePtr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 329) unsigned max = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 330)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 331) memset(count, 0, (maxSymbolValue + 1) * sizeof(*count));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 332) if (srcSize == 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 333) *maxSymbolValuePtr = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 334) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 335) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 336)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 337) while (ip < end)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 338) count[*ip++]++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 339)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 340) while (!count[maxSymbolValue])
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 341) maxSymbolValue--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 342) *maxSymbolValuePtr = maxSymbolValue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 343)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 344) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 345) U32 s;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 346) for (s = 0; s <= maxSymbolValue; s++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 347) if (count[s] > max)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 348) max = count[s];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 349) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 350)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 351) return (size_t)max;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 352) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 353)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 354) /* FSE_count_parallel_wksp() :
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 355) * Same as FSE_count_parallel(), but using an externally provided scratch buffer.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 356) * `workSpace` size must be a minimum of `1024 * sizeof(unsigned)`` */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 357) static size_t FSE_count_parallel_wksp(unsigned *count, unsigned *maxSymbolValuePtr, const void *source, size_t sourceSize, unsigned checkMax,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 358) unsigned *const workSpace)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 359) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 360) const BYTE *ip = (const BYTE *)source;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 361) const BYTE *const iend = ip + sourceSize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 362) unsigned maxSymbolValue = *maxSymbolValuePtr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 363) unsigned max = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 364) U32 *const Counting1 = workSpace;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 365) U32 *const Counting2 = Counting1 + 256;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 366) U32 *const Counting3 = Counting2 + 256;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 367) U32 *const Counting4 = Counting3 + 256;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 368)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 369) memset(Counting1, 0, 4 * 256 * sizeof(unsigned));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 370)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 371) /* safety checks */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 372) if (!sourceSize) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 373) memset(count, 0, maxSymbolValue + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 374) *maxSymbolValuePtr = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 375) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 376) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 377) if (!maxSymbolValue)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 378) maxSymbolValue = 255; /* 0 == default */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 379)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 380) /* by stripes of 16 bytes */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 381) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 382) U32 cached = ZSTD_read32(ip);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 383) ip += 4;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 384) while (ip < iend - 15) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 385) U32 c = cached;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 386) cached = ZSTD_read32(ip);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 387) ip += 4;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 388) Counting1[(BYTE)c]++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 389) Counting2[(BYTE)(c >> 8)]++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 390) Counting3[(BYTE)(c >> 16)]++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 391) Counting4[c >> 24]++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 392) c = cached;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 393) cached = ZSTD_read32(ip);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 394) ip += 4;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 395) Counting1[(BYTE)c]++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 396) Counting2[(BYTE)(c >> 8)]++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 397) Counting3[(BYTE)(c >> 16)]++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 398) Counting4[c >> 24]++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 399) c = cached;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 400) cached = ZSTD_read32(ip);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 401) ip += 4;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 402) Counting1[(BYTE)c]++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 403) Counting2[(BYTE)(c >> 8)]++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 404) Counting3[(BYTE)(c >> 16)]++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 405) Counting4[c >> 24]++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 406) c = cached;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 407) cached = ZSTD_read32(ip);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 408) ip += 4;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 409) Counting1[(BYTE)c]++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 410) Counting2[(BYTE)(c >> 8)]++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 411) Counting3[(BYTE)(c >> 16)]++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 412) Counting4[c >> 24]++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 413) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 414) ip -= 4;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 415) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 416)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 417) /* finish last symbols */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 418) while (ip < iend)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 419) Counting1[*ip++]++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 420)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 421) if (checkMax) { /* verify stats will fit into destination table */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 422) U32 s;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 423) for (s = 255; s > maxSymbolValue; s--) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 424) Counting1[s] += Counting2[s] + Counting3[s] + Counting4[s];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 425) if (Counting1[s])
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 426) return ERROR(maxSymbolValue_tooSmall);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 427) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 428) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 429)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 430) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 431) U32 s;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 432) for (s = 0; s <= maxSymbolValue; s++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 433) count[s] = Counting1[s] + Counting2[s] + Counting3[s] + Counting4[s];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 434) if (count[s] > max)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 435) max = count[s];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 436) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 437) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 438)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 439) while (!count[maxSymbolValue])
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 440) maxSymbolValue--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 441) *maxSymbolValuePtr = maxSymbolValue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 442) return (size_t)max;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 443) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 444)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 445) /* FSE_countFast_wksp() :
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 446) * Same as FSE_countFast(), but using an externally provided scratch buffer.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 447) * `workSpace` size must be table of >= `1024` unsigned */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 448) size_t FSE_countFast_wksp(unsigned *count, unsigned *maxSymbolValuePtr, const void *source, size_t sourceSize, unsigned *workSpace)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 449) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 450) if (sourceSize < 1500)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 451) return FSE_count_simple(count, maxSymbolValuePtr, source, sourceSize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 452) return FSE_count_parallel_wksp(count, maxSymbolValuePtr, source, sourceSize, 0, workSpace);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 453) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 454)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 455) /* FSE_count_wksp() :
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 456) * Same as FSE_count(), but using an externally provided scratch buffer.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 457) * `workSpace` size must be table of >= `1024` unsigned */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 458) size_t FSE_count_wksp(unsigned *count, unsigned *maxSymbolValuePtr, const void *source, size_t sourceSize, unsigned *workSpace)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 459) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 460) if (*maxSymbolValuePtr < 255)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 461) return FSE_count_parallel_wksp(count, maxSymbolValuePtr, source, sourceSize, 1, workSpace);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 462) *maxSymbolValuePtr = 255;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 463) return FSE_countFast_wksp(count, maxSymbolValuePtr, source, sourceSize, workSpace);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 464) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 465)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 466) /*-**************************************************************
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 467) * FSE Compression Code
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 468) ****************************************************************/
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 469) /*! FSE_sizeof_CTable() :
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 470) FSE_CTable is a variable size structure which contains :
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 471) `U16 tableLog;`
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 472) `U16 maxSymbolValue;`
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 473) `U16 nextStateNumber[1 << tableLog];` // This size is variable
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 474) `FSE_symbolCompressionTransform symbolTT[maxSymbolValue+1];` // This size is variable
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 475) Allocation is manual (C standard does not support variable-size structures).
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 476) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 477) size_t FSE_sizeof_CTable(unsigned maxSymbolValue, unsigned tableLog)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 478) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 479) if (tableLog > FSE_MAX_TABLELOG)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 480) return ERROR(tableLog_tooLarge);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 481) return FSE_CTABLE_SIZE_U32(tableLog, maxSymbolValue) * sizeof(U32);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 482) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 483)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 484) /* provides the minimum logSize to safely represent a distribution */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 485) static unsigned FSE_minTableLog(size_t srcSize, unsigned maxSymbolValue)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 486) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 487) U32 minBitsSrc = BIT_highbit32((U32)(srcSize - 1)) + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 488) U32 minBitsSymbols = BIT_highbit32(maxSymbolValue) + 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 489) U32 minBits = minBitsSrc < minBitsSymbols ? minBitsSrc : minBitsSymbols;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 490) return minBits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 491) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 492)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 493) unsigned FSE_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 494) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 495) U32 maxBitsSrc = BIT_highbit32((U32)(srcSize - 1)) - minus;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 496) U32 tableLog = maxTableLog;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 497) U32 minBits = FSE_minTableLog(srcSize, maxSymbolValue);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 498) if (tableLog == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 499) tableLog = FSE_DEFAULT_TABLELOG;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 500) if (maxBitsSrc < tableLog)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 501) tableLog = maxBitsSrc; /* Accuracy can be reduced */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 502) if (minBits > tableLog)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 503) tableLog = minBits; /* Need a minimum to safely represent all symbol values */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 504) if (tableLog < FSE_MIN_TABLELOG)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 505) tableLog = FSE_MIN_TABLELOG;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 506) if (tableLog > FSE_MAX_TABLELOG)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 507) tableLog = FSE_MAX_TABLELOG;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 508) return tableLog;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 509) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 510)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 511) unsigned FSE_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 512) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 513) return FSE_optimalTableLog_internal(maxTableLog, srcSize, maxSymbolValue, 2);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 514) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 515)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 516) /* Secondary normalization method.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 517) To be used when primary method fails. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 518)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 519) static size_t FSE_normalizeM2(short *norm, U32 tableLog, const unsigned *count, size_t total, U32 maxSymbolValue)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 520) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 521) short const NOT_YET_ASSIGNED = -2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 522) U32 s;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 523) U32 distributed = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 524) U32 ToDistribute;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 525)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 526) /* Init */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 527) U32 const lowThreshold = (U32)(total >> tableLog);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 528) U32 lowOne = (U32)((total * 3) >> (tableLog + 1));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 529)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 530) for (s = 0; s <= maxSymbolValue; s++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 531) if (count[s] == 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 532) norm[s] = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 533) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 534) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 535) if (count[s] <= lowThreshold) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 536) norm[s] = -1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 537) distributed++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 538) total -= count[s];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 539) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 540) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 541) if (count[s] <= lowOne) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 542) norm[s] = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 543) distributed++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 544) total -= count[s];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 545) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 546) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 547)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 548) norm[s] = NOT_YET_ASSIGNED;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 549) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 550) ToDistribute = (1 << tableLog) - distributed;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 551)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 552) if ((total / ToDistribute) > lowOne) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 553) /* risk of rounding to zero */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 554) lowOne = (U32)((total * 3) / (ToDistribute * 2));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 555) for (s = 0; s <= maxSymbolValue; s++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 556) if ((norm[s] == NOT_YET_ASSIGNED) && (count[s] <= lowOne)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 557) norm[s] = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 558) distributed++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 559) total -= count[s];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 560) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 561) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 562) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 563) ToDistribute = (1 << tableLog) - distributed;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 564) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 565)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 566) if (distributed == maxSymbolValue + 1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 567) /* all values are pretty poor;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 568) probably incompressible data (should have already been detected);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 569) find max, then give all remaining points to max */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 570) U32 maxV = 0, maxC = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 571) for (s = 0; s <= maxSymbolValue; s++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 572) if (count[s] > maxC)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 573) maxV = s, maxC = count[s];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 574) norm[maxV] += (short)ToDistribute;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 575) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 576) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 577)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 578) if (total == 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 579) /* all of the symbols were low enough for the lowOne or lowThreshold */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 580) for (s = 0; ToDistribute > 0; s = (s + 1) % (maxSymbolValue + 1))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 581) if (norm[s] > 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 582) ToDistribute--, norm[s]++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 583) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 584) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 585)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 586) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 587) U64 const vStepLog = 62 - tableLog;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 588) U64 const mid = (1ULL << (vStepLog - 1)) - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 589) U64 const rStep = div_u64((((U64)1 << vStepLog) * ToDistribute) + mid, (U32)total); /* scale on remaining */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 590) U64 tmpTotal = mid;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 591) for (s = 0; s <= maxSymbolValue; s++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 592) if (norm[s] == NOT_YET_ASSIGNED) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 593) U64 const end = tmpTotal + (count[s] * rStep);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 594) U32 const sStart = (U32)(tmpTotal >> vStepLog);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 595) U32 const sEnd = (U32)(end >> vStepLog);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 596) U32 const weight = sEnd - sStart;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 597) if (weight < 1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 598) return ERROR(GENERIC);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 599) norm[s] = (short)weight;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 600) tmpTotal = end;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 601) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 602) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 603) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 604)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 605) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 606) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 607)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 608) size_t FSE_normalizeCount(short *normalizedCounter, unsigned tableLog, const unsigned *count, size_t total, unsigned maxSymbolValue)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 609) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 610) /* Sanity checks */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 611) if (tableLog == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 612) tableLog = FSE_DEFAULT_TABLELOG;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 613) if (tableLog < FSE_MIN_TABLELOG)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 614) return ERROR(GENERIC); /* Unsupported size */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 615) if (tableLog > FSE_MAX_TABLELOG)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 616) return ERROR(tableLog_tooLarge); /* Unsupported size */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 617) if (tableLog < FSE_minTableLog(total, maxSymbolValue))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 618) return ERROR(GENERIC); /* Too small tableLog, compression potentially impossible */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 619)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 620) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 621) U32 const rtbTable[] = {0, 473195, 504333, 520860, 550000, 700000, 750000, 830000};
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 622) U64 const scale = 62 - tableLog;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 623) U64 const step = div_u64((U64)1 << 62, (U32)total); /* <== here, one division ! */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 624) U64 const vStep = 1ULL << (scale - 20);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 625) int stillToDistribute = 1 << tableLog;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 626) unsigned s;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 627) unsigned largest = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 628) short largestP = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 629) U32 lowThreshold = (U32)(total >> tableLog);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 630)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 631) for (s = 0; s <= maxSymbolValue; s++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 632) if (count[s] == total)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 633) return 0; /* rle special case */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 634) if (count[s] == 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 635) normalizedCounter[s] = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 636) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 637) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 638) if (count[s] <= lowThreshold) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 639) normalizedCounter[s] = -1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 640) stillToDistribute--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 641) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 642) short proba = (short)((count[s] * step) >> scale);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 643) if (proba < 8) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 644) U64 restToBeat = vStep * rtbTable[proba];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 645) proba += (count[s] * step) - ((U64)proba << scale) > restToBeat;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 646) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 647) if (proba > largestP)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 648) largestP = proba, largest = s;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 649) normalizedCounter[s] = proba;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 650) stillToDistribute -= proba;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 651) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 652) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 653) if (-stillToDistribute >= (normalizedCounter[largest] >> 1)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 654) /* corner case, need another normalization method */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 655) size_t const errorCode = FSE_normalizeM2(normalizedCounter, tableLog, count, total, maxSymbolValue);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 656) if (FSE_isError(errorCode))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 657) return errorCode;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 658) } else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 659) normalizedCounter[largest] += (short)stillToDistribute;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 660) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 661)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 662) return tableLog;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 663) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 664)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 665) /* fake FSE_CTable, for raw (uncompressed) input */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 666) size_t FSE_buildCTable_raw(FSE_CTable *ct, unsigned nbBits)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 667) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 668) const unsigned tableSize = 1 << nbBits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 669) const unsigned tableMask = tableSize - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 670) const unsigned maxSymbolValue = tableMask;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 671) void *const ptr = ct;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 672) U16 *const tableU16 = ((U16 *)ptr) + 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 673) void *const FSCT = ((U32 *)ptr) + 1 /* header */ + (tableSize >> 1); /* assumption : tableLog >= 1 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 674) FSE_symbolCompressionTransform *const symbolTT = (FSE_symbolCompressionTransform *)(FSCT);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 675) unsigned s;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 676)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 677) /* Sanity checks */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 678) if (nbBits < 1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 679) return ERROR(GENERIC); /* min size */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 680)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 681) /* header */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 682) tableU16[-2] = (U16)nbBits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 683) tableU16[-1] = (U16)maxSymbolValue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 684)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 685) /* Build table */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 686) for (s = 0; s < tableSize; s++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 687) tableU16[s] = (U16)(tableSize + s);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 688)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 689) /* Build Symbol Transformation Table */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 690) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 691) const U32 deltaNbBits = (nbBits << 16) - (1 << nbBits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 692) for (s = 0; s <= maxSymbolValue; s++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 693) symbolTT[s].deltaNbBits = deltaNbBits;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 694) symbolTT[s].deltaFindState = s - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 695) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 696) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 697)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 698) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 699) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 700)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 701) /* fake FSE_CTable, for rle input (always same symbol) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 702) size_t FSE_buildCTable_rle(FSE_CTable *ct, BYTE symbolValue)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 703) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 704) void *ptr = ct;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 705) U16 *tableU16 = ((U16 *)ptr) + 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 706) void *FSCTptr = (U32 *)ptr + 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 707) FSE_symbolCompressionTransform *symbolTT = (FSE_symbolCompressionTransform *)FSCTptr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 708)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 709) /* header */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 710) tableU16[-2] = (U16)0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 711) tableU16[-1] = (U16)symbolValue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 712)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 713) /* Build table */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 714) tableU16[0] = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 715) tableU16[1] = 0; /* just in case */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 716)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 717) /* Build Symbol Transformation Table */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 718) symbolTT[symbolValue].deltaNbBits = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 719) symbolTT[symbolValue].deltaFindState = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 720)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 721) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 722) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 723)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 724) static size_t FSE_compress_usingCTable_generic(void *dst, size_t dstSize, const void *src, size_t srcSize, const FSE_CTable *ct, const unsigned fast)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 725) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 726) const BYTE *const istart = (const BYTE *)src;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 727) const BYTE *const iend = istart + srcSize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 728) const BYTE *ip = iend;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 729)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 730) BIT_CStream_t bitC;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 731) FSE_CState_t CState1, CState2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 732)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 733) /* init */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 734) if (srcSize <= 2)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 735) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 736) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 737) size_t const initError = BIT_initCStream(&bitC, dst, dstSize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 738) if (FSE_isError(initError))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 739) return 0; /* not enough space available to write a bitstream */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 740) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 741)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 742) #define FSE_FLUSHBITS(s) (fast ? BIT_flushBitsFast(s) : BIT_flushBits(s))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 743)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 744) if (srcSize & 1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 745) FSE_initCState2(&CState1, ct, *--ip);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 746) FSE_initCState2(&CState2, ct, *--ip);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 747) FSE_encodeSymbol(&bitC, &CState1, *--ip);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 748) FSE_FLUSHBITS(&bitC);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 749) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 750) FSE_initCState2(&CState2, ct, *--ip);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 751) FSE_initCState2(&CState1, ct, *--ip);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 752) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 753)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 754) /* join to mod 4 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 755) srcSize -= 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 756) if ((sizeof(bitC.bitContainer) * 8 > FSE_MAX_TABLELOG * 4 + 7) && (srcSize & 2)) { /* test bit 2 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 757) FSE_encodeSymbol(&bitC, &CState2, *--ip);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 758) FSE_encodeSymbol(&bitC, &CState1, *--ip);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 759) FSE_FLUSHBITS(&bitC);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 760) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 761)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 762) /* 2 or 4 encoding per loop */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 763) while (ip > istart) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 764)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 765) FSE_encodeSymbol(&bitC, &CState2, *--ip);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 766)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 767) if (sizeof(bitC.bitContainer) * 8 < FSE_MAX_TABLELOG * 2 + 7) /* this test must be static */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 768) FSE_FLUSHBITS(&bitC);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 769)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 770) FSE_encodeSymbol(&bitC, &CState1, *--ip);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 771)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 772) if (sizeof(bitC.bitContainer) * 8 > FSE_MAX_TABLELOG * 4 + 7) { /* this test must be static */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 773) FSE_encodeSymbol(&bitC, &CState2, *--ip);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 774) FSE_encodeSymbol(&bitC, &CState1, *--ip);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 775) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 776)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 777) FSE_FLUSHBITS(&bitC);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 778) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 779)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 780) FSE_flushCState(&bitC, &CState2);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 781) FSE_flushCState(&bitC, &CState1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 782) return BIT_closeCStream(&bitC);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 783) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 784)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 785) size_t FSE_compress_usingCTable(void *dst, size_t dstSize, const void *src, size_t srcSize, const FSE_CTable *ct)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 786) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 787) unsigned const fast = (dstSize >= FSE_BLOCKBOUND(srcSize));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 788)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 789) if (fast)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 790) return FSE_compress_usingCTable_generic(dst, dstSize, src, srcSize, ct, 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 791) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 792) return FSE_compress_usingCTable_generic(dst, dstSize, src, srcSize, ct, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 793) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 794)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 795) size_t FSE_compressBound(size_t size) { return FSE_COMPRESSBOUND(size); }
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags