Revision 5f4fc6d440d77a2cf74fe4ea56955674ac7e35e7 authored by Linus Torvalds on 19 July 2019, 17:06:06 UTC, committed by Linus Torvalds on 19 July 2019, 17:06:06 UTC
Pull networking fixes from David Miller: 1) Fix AF_XDP cq entry leak, from Ilya Maximets. 2) Fix handling of PHY power-down on RTL8411B, from Heiner Kallweit. 3) Add some new PCI IDs to iwlwifi, from Ihab Zhaika. 4) Fix handling of neigh timers wrt. entries added by userspace, from Lorenzo Bianconi. 5) Various cases of missing of_node_put(), from Nishka Dasgupta. 6) The new NET_ACT_CT needs to depend upon NF_NAT, from Yue Haibing. 7) Various RDS layer fixes, from Gerd Rausch. 8) Fix some more fallout from TCQ_F_CAN_BYPASS generalization, from Cong Wang. 9) Fix FIB source validation checks over loopback, also from Cong Wang. 10) Use promisc for unsupported number of filters, from Justin Chen. 11) Missing sibling route unlink on failure in ipv6, from Ido Schimmel. * git://git.kernel.org/pub/scm/linux/kernel/git/davem/net: (90 commits) tcp: fix tcp_set_congestion_control() use from bpf hook ag71xx: fix return value check in ag71xx_probe() ag71xx: fix error return code in ag71xx_probe() usb: qmi_wwan: add D-Link DWM-222 A2 device ID bnxt_en: Fix VNIC accounting when enabling aRFS on 57500 chips. net: dsa: sja1105: Fix missing unlock on error in sk_buff() gve: replace kfree with kvfree selftests/bpf: fix test_xdp_noinline on s390 selftests/bpf: fix "valid read map access into a read-only array 1" on s390 net/mlx5: Replace kfree with kvfree MAINTAINERS: update netsec driver ipv6: Unlink sibling route in case of failure liquidio: Replace vmalloc + memset with vzalloc udp: Fix typo in net/ipv4/udp.c net: bcmgenet: use promisc for unsupported filters ipv6: rt6_check should return NULL if 'from' is NULL tipc: initialize 'validated' field of received packets selftests: add a test case for rp_filter fib: relax source validation check for loopback packets mlxsw: spectrum: Do not process learned records with a dummy FID ...
fse_compress.c
/*
* FSE : Finite State Entropy encoder
* Copyright (C) 2013-2015, Yann Collet.
*
* BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
* met:
*
* * Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* * Redistributions in binary form must reproduce the above
* copyright notice, this list of conditions and the following disclaimer
* in the documentation and/or other materials provided with the
* distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
* OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*
* This program is free software; you can redistribute it and/or modify it under
* the terms of the GNU General Public License version 2 as published by the
* Free Software Foundation. This program is dual-licensed; you may select
* either version 2 of the GNU General Public License ("GPL") or BSD license
* ("BSD").
*
* You can contact the author at :
* - Source repository : https://github.com/Cyan4973/FiniteStateEntropy
*/
/* **************************************************************
* Compiler specifics
****************************************************************/
#define FORCE_INLINE static __always_inline
/* **************************************************************
* Includes
****************************************************************/
#include "bitstream.h"
#include "fse.h"
#include <linux/compiler.h>
#include <linux/kernel.h>
#include <linux/math64.h>
#include <linux/string.h> /* memcpy, memset */
/* **************************************************************
* Error Management
****************************************************************/
#define FSE_STATIC_ASSERT(c) \
{ \
enum { FSE_static_assert = 1 / (int)(!!(c)) }; \
} /* use only *after* variable declarations */
/* **************************************************************
* Templates
****************************************************************/
/*
designed to be included
for type-specific functions (template emulation in C)
Objective is to write these functions only once, for improved maintenance
*/
/* safety checks */
#ifndef FSE_FUNCTION_EXTENSION
#error "FSE_FUNCTION_EXTENSION must be defined"
#endif
#ifndef FSE_FUNCTION_TYPE
#error "FSE_FUNCTION_TYPE must be defined"
#endif
/* Function names */
#define FSE_CAT(X, Y) X##Y
#define FSE_FUNCTION_NAME(X, Y) FSE_CAT(X, Y)
#define FSE_TYPE_NAME(X, Y) FSE_CAT(X, Y)
/* Function templates */
/* FSE_buildCTable_wksp() :
* Same as FSE_buildCTable(), but using an externally allocated scratch buffer (`workSpace`).
* wkspSize should be sized to handle worst case situation, which is `1<<max_tableLog * sizeof(FSE_FUNCTION_TYPE)`
* workSpace must also be properly aligned with FSE_FUNCTION_TYPE requirements
*/
size_t FSE_buildCTable_wksp(FSE_CTable *ct, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog, void *workspace, size_t workspaceSize)
{
U32 const tableSize = 1 << tableLog;
U32 const tableMask = tableSize - 1;
void *const ptr = ct;
U16 *const tableU16 = ((U16 *)ptr) + 2;
void *const FSCT = ((U32 *)ptr) + 1 /* header */ + (tableLog ? tableSize >> 1 : 1);
FSE_symbolCompressionTransform *const symbolTT = (FSE_symbolCompressionTransform *)(FSCT);
U32 const step = FSE_TABLESTEP(tableSize);
U32 highThreshold = tableSize - 1;
U32 *cumul;
FSE_FUNCTION_TYPE *tableSymbol;
size_t spaceUsed32 = 0;
cumul = (U32 *)workspace + spaceUsed32;
spaceUsed32 += FSE_MAX_SYMBOL_VALUE + 2;
tableSymbol = (FSE_FUNCTION_TYPE *)((U32 *)workspace + spaceUsed32);
spaceUsed32 += ALIGN(sizeof(FSE_FUNCTION_TYPE) * ((size_t)1 << tableLog), sizeof(U32)) >> 2;
if ((spaceUsed32 << 2) > workspaceSize)
return ERROR(tableLog_tooLarge);
workspace = (U32 *)workspace + spaceUsed32;
workspaceSize -= (spaceUsed32 << 2);
/* CTable header */
tableU16[-2] = (U16)tableLog;
tableU16[-1] = (U16)maxSymbolValue;
/* For explanations on how to distribute symbol values over the table :
* http://fastcompression.blogspot.fr/2014/02/fse-distributing-symbol-values.html */
/* symbol start positions */
{
U32 u;
cumul[0] = 0;
for (u = 1; u <= maxSymbolValue + 1; u++) {
if (normalizedCounter[u - 1] == -1) { /* Low proba symbol */
cumul[u] = cumul[u - 1] + 1;
tableSymbol[highThreshold--] = (FSE_FUNCTION_TYPE)(u - 1);
} else {
cumul[u] = cumul[u - 1] + normalizedCounter[u - 1];
}
}
cumul[maxSymbolValue + 1] = tableSize + 1;
}
/* Spread symbols */
{
U32 position = 0;
U32 symbol;
for (symbol = 0; symbol <= maxSymbolValue; symbol++) {
int nbOccurences;
for (nbOccurences = 0; nbOccurences < normalizedCounter[symbol]; nbOccurences++) {
tableSymbol[position] = (FSE_FUNCTION_TYPE)symbol;
position = (position + step) & tableMask;
while (position > highThreshold)
position = (position + step) & tableMask; /* Low proba area */
}
}
if (position != 0)
return ERROR(GENERIC); /* Must have gone through all positions */
}
/* Build table */
{
U32 u;
for (u = 0; u < tableSize; u++) {
FSE_FUNCTION_TYPE s = tableSymbol[u]; /* note : static analyzer may not understand tableSymbol is properly initialized */
tableU16[cumul[s]++] = (U16)(tableSize + u); /* TableU16 : sorted by symbol order; gives next state value */
}
}
/* Build Symbol Transformation Table */
{
unsigned total = 0;
unsigned s;
for (s = 0; s <= maxSymbolValue; s++) {
switch (normalizedCounter[s]) {
case 0: break;
case -1:
case 1:
symbolTT[s].deltaNbBits = (tableLog << 16) - (1 << tableLog);
symbolTT[s].deltaFindState = total - 1;
total++;
break;
default: {
U32 const maxBitsOut = tableLog - BIT_highbit32(normalizedCounter[s] - 1);
U32 const minStatePlus = normalizedCounter[s] << maxBitsOut;
symbolTT[s].deltaNbBits = (maxBitsOut << 16) - minStatePlus;
symbolTT[s].deltaFindState = total - normalizedCounter[s];
total += normalizedCounter[s];
}
}
}
}
return 0;
}
/*-**************************************************************
* FSE NCount encoding-decoding
****************************************************************/
size_t FSE_NCountWriteBound(unsigned maxSymbolValue, unsigned tableLog)
{
size_t const maxHeaderSize = (((maxSymbolValue + 1) * tableLog) >> 3) + 3;
return maxSymbolValue ? maxHeaderSize : FSE_NCOUNTBOUND; /* maxSymbolValue==0 ? use default */
}
static size_t FSE_writeNCount_generic(void *header, size_t headerBufferSize, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog,
unsigned writeIsSafe)
{
BYTE *const ostart = (BYTE *)header;
BYTE *out = ostart;
BYTE *const oend = ostart + headerBufferSize;
int nbBits;
const int tableSize = 1 << tableLog;
int remaining;
int threshold;
U32 bitStream;
int bitCount;
unsigned charnum = 0;
int previous0 = 0;
bitStream = 0;
bitCount = 0;
/* Table Size */
bitStream += (tableLog - FSE_MIN_TABLELOG) << bitCount;
bitCount += 4;
/* Init */
remaining = tableSize + 1; /* +1 for extra accuracy */
threshold = tableSize;
nbBits = tableLog + 1;
while (remaining > 1) { /* stops at 1 */
if (previous0) {
unsigned start = charnum;
while (!normalizedCounter[charnum])
charnum++;
while (charnum >= start + 24) {
start += 24;
bitStream += 0xFFFFU << bitCount;
if ((!writeIsSafe) && (out > oend - 2))
return ERROR(dstSize_tooSmall); /* Buffer overflow */
out[0] = (BYTE)bitStream;
out[1] = (BYTE)(bitStream >> 8);
out += 2;
bitStream >>= 16;
}
while (charnum >= start + 3) {
start += 3;
bitStream += 3 << bitCount;
bitCount += 2;
}
bitStream += (charnum - start) << bitCount;
bitCount += 2;
if (bitCount > 16) {
if ((!writeIsSafe) && (out > oend - 2))
return ERROR(dstSize_tooSmall); /* Buffer overflow */
out[0] = (BYTE)bitStream;
out[1] = (BYTE)(bitStream >> 8);
out += 2;
bitStream >>= 16;
bitCount -= 16;
}
}
{
int count = normalizedCounter[charnum++];
int const max = (2 * threshold - 1) - remaining;
remaining -= count < 0 ? -count : count;
count++; /* +1 for extra accuracy */
if (count >= threshold)
count += max; /* [0..max[ [max..threshold[ (...) [threshold+max 2*threshold[ */
bitStream += count << bitCount;
bitCount += nbBits;
bitCount -= (count < max);
previous0 = (count == 1);
if (remaining < 1)
return ERROR(GENERIC);
while (remaining < threshold)
nbBits--, threshold >>= 1;
}
if (bitCount > 16) {
if ((!writeIsSafe) && (out > oend - 2))
return ERROR(dstSize_tooSmall); /* Buffer overflow */
out[0] = (BYTE)bitStream;
out[1] = (BYTE)(bitStream >> 8);
out += 2;
bitStream >>= 16;
bitCount -= 16;
}
}
/* flush remaining bitStream */
if ((!writeIsSafe) && (out > oend - 2))
return ERROR(dstSize_tooSmall); /* Buffer overflow */
out[0] = (BYTE)bitStream;
out[1] = (BYTE)(bitStream >> 8);
out += (bitCount + 7) / 8;
if (charnum > maxSymbolValue + 1)
return ERROR(GENERIC);
return (out - ostart);
}
size_t FSE_writeNCount(void *buffer, size_t bufferSize, const short *normalizedCounter, unsigned maxSymbolValue, unsigned tableLog)
{
if (tableLog > FSE_MAX_TABLELOG)
return ERROR(tableLog_tooLarge); /* Unsupported */
if (tableLog < FSE_MIN_TABLELOG)
return ERROR(GENERIC); /* Unsupported */
if (bufferSize < FSE_NCountWriteBound(maxSymbolValue, tableLog))
return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 0);
return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 1);
}
/*-**************************************************************
* Counting histogram
****************************************************************/
/*! FSE_count_simple
This function counts byte values within `src`, and store the histogram into table `count`.
It doesn't use any additional memory.
But this function is unsafe : it doesn't check that all values within `src` can fit into `count`.
For this reason, prefer using a table `count` with 256 elements.
@return : count of most numerous element
*/
size_t FSE_count_simple(unsigned *count, unsigned *maxSymbolValuePtr, const void *src, size_t srcSize)
{
const BYTE *ip = (const BYTE *)src;
const BYTE *const end = ip + srcSize;
unsigned maxSymbolValue = *maxSymbolValuePtr;
unsigned max = 0;
memset(count, 0, (maxSymbolValue + 1) * sizeof(*count));
if (srcSize == 0) {
*maxSymbolValuePtr = 0;
return 0;
}
while (ip < end)
count[*ip++]++;
while (!count[maxSymbolValue])
maxSymbolValue--;
*maxSymbolValuePtr = maxSymbolValue;
{
U32 s;
for (s = 0; s <= maxSymbolValue; s++)
if (count[s] > max)
max = count[s];
}
return (size_t)max;
}
/* FSE_count_parallel_wksp() :
* Same as FSE_count_parallel(), but using an externally provided scratch buffer.
* `workSpace` size must be a minimum of `1024 * sizeof(unsigned)`` */
static size_t FSE_count_parallel_wksp(unsigned *count, unsigned *maxSymbolValuePtr, const void *source, size_t sourceSize, unsigned checkMax,
unsigned *const workSpace)
{
const BYTE *ip = (const BYTE *)source;
const BYTE *const iend = ip + sourceSize;
unsigned maxSymbolValue = *maxSymbolValuePtr;
unsigned max = 0;
U32 *const Counting1 = workSpace;
U32 *const Counting2 = Counting1 + 256;
U32 *const Counting3 = Counting2 + 256;
U32 *const Counting4 = Counting3 + 256;
memset(Counting1, 0, 4 * 256 * sizeof(unsigned));
/* safety checks */
if (!sourceSize) {
memset(count, 0, maxSymbolValue + 1);
*maxSymbolValuePtr = 0;
return 0;
}
if (!maxSymbolValue)
maxSymbolValue = 255; /* 0 == default */
/* by stripes of 16 bytes */
{
U32 cached = ZSTD_read32(ip);
ip += 4;
while (ip < iend - 15) {
U32 c = cached;
cached = ZSTD_read32(ip);
ip += 4;
Counting1[(BYTE)c]++;
Counting2[(BYTE)(c >> 8)]++;
Counting3[(BYTE)(c >> 16)]++;
Counting4[c >> 24]++;
c = cached;
cached = ZSTD_read32(ip);
ip += 4;
Counting1[(BYTE)c]++;
Counting2[(BYTE)(c >> 8)]++;
Counting3[(BYTE)(c >> 16)]++;
Counting4[c >> 24]++;
c = cached;
cached = ZSTD_read32(ip);
ip += 4;
Counting1[(BYTE)c]++;
Counting2[(BYTE)(c >> 8)]++;
Counting3[(BYTE)(c >> 16)]++;
Counting4[c >> 24]++;
c = cached;
cached = ZSTD_read32(ip);
ip += 4;
Counting1[(BYTE)c]++;
Counting2[(BYTE)(c >> 8)]++;
Counting3[(BYTE)(c >> 16)]++;
Counting4[c >> 24]++;
}
ip -= 4;
}
/* finish last symbols */
while (ip < iend)
Counting1[*ip++]++;
if (checkMax) { /* verify stats will fit into destination table */
U32 s;
for (s = 255; s > maxSymbolValue; s--) {
Counting1[s] += Counting2[s] + Counting3[s] + Counting4[s];
if (Counting1[s])
return ERROR(maxSymbolValue_tooSmall);
}
}
{
U32 s;
for (s = 0; s <= maxSymbolValue; s++) {
count[s] = Counting1[s] + Counting2[s] + Counting3[s] + Counting4[s];
if (count[s] > max)
max = count[s];
}
}
while (!count[maxSymbolValue])
maxSymbolValue--;
*maxSymbolValuePtr = maxSymbolValue;
return (size_t)max;
}
/* FSE_countFast_wksp() :
* Same as FSE_countFast(), but using an externally provided scratch buffer.
* `workSpace` size must be table of >= `1024` unsigned */
size_t FSE_countFast_wksp(unsigned *count, unsigned *maxSymbolValuePtr, const void *source, size_t sourceSize, unsigned *workSpace)
{
if (sourceSize < 1500)
return FSE_count_simple(count, maxSymbolValuePtr, source, sourceSize);
return FSE_count_parallel_wksp(count, maxSymbolValuePtr, source, sourceSize, 0, workSpace);
}
/* FSE_count_wksp() :
* Same as FSE_count(), but using an externally provided scratch buffer.
* `workSpace` size must be table of >= `1024` unsigned */
size_t FSE_count_wksp(unsigned *count, unsigned *maxSymbolValuePtr, const void *source, size_t sourceSize, unsigned *workSpace)
{
if (*maxSymbolValuePtr < 255)
return FSE_count_parallel_wksp(count, maxSymbolValuePtr, source, sourceSize, 1, workSpace);
*maxSymbolValuePtr = 255;
return FSE_countFast_wksp(count, maxSymbolValuePtr, source, sourceSize, workSpace);
}
/*-**************************************************************
* FSE Compression Code
****************************************************************/
/*! FSE_sizeof_CTable() :
FSE_CTable is a variable size structure which contains :
`U16 tableLog;`
`U16 maxSymbolValue;`
`U16 nextStateNumber[1 << tableLog];` // This size is variable
`FSE_symbolCompressionTransform symbolTT[maxSymbolValue+1];` // This size is variable
Allocation is manual (C standard does not support variable-size structures).
*/
size_t FSE_sizeof_CTable(unsigned maxSymbolValue, unsigned tableLog)
{
if (tableLog > FSE_MAX_TABLELOG)
return ERROR(tableLog_tooLarge);
return FSE_CTABLE_SIZE_U32(tableLog, maxSymbolValue) * sizeof(U32);
}
/* provides the minimum logSize to safely represent a distribution */
static unsigned FSE_minTableLog(size_t srcSize, unsigned maxSymbolValue)
{
U32 minBitsSrc = BIT_highbit32((U32)(srcSize - 1)) + 1;
U32 minBitsSymbols = BIT_highbit32(maxSymbolValue) + 2;
U32 minBits = minBitsSrc < minBitsSymbols ? minBitsSrc : minBitsSymbols;
return minBits;
}
unsigned FSE_optimalTableLog_internal(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue, unsigned minus)
{
U32 maxBitsSrc = BIT_highbit32((U32)(srcSize - 1)) - minus;
U32 tableLog = maxTableLog;
U32 minBits = FSE_minTableLog(srcSize, maxSymbolValue);
if (tableLog == 0)
tableLog = FSE_DEFAULT_TABLELOG;
if (maxBitsSrc < tableLog)
tableLog = maxBitsSrc; /* Accuracy can be reduced */
if (minBits > tableLog)
tableLog = minBits; /* Need a minimum to safely represent all symbol values */
if (tableLog < FSE_MIN_TABLELOG)
tableLog = FSE_MIN_TABLELOG;
if (tableLog > FSE_MAX_TABLELOG)
tableLog = FSE_MAX_TABLELOG;
return tableLog;
}
unsigned FSE_optimalTableLog(unsigned maxTableLog, size_t srcSize, unsigned maxSymbolValue)
{
return FSE_optimalTableLog_internal(maxTableLog, srcSize, maxSymbolValue, 2);
}
/* Secondary normalization method.
To be used when primary method fails. */
static size_t FSE_normalizeM2(short *norm, U32 tableLog, const unsigned *count, size_t total, U32 maxSymbolValue)
{
short const NOT_YET_ASSIGNED = -2;
U32 s;
U32 distributed = 0;
U32 ToDistribute;
/* Init */
U32 const lowThreshold = (U32)(total >> tableLog);
U32 lowOne = (U32)((total * 3) >> (tableLog + 1));
for (s = 0; s <= maxSymbolValue; s++) {
if (count[s] == 0) {
norm[s] = 0;
continue;
}
if (count[s] <= lowThreshold) {
norm[s] = -1;
distributed++;
total -= count[s];
continue;
}
if (count[s] <= lowOne) {
norm[s] = 1;
distributed++;
total -= count[s];
continue;
}
norm[s] = NOT_YET_ASSIGNED;
}
ToDistribute = (1 << tableLog) - distributed;
if ((total / ToDistribute) > lowOne) {
/* risk of rounding to zero */
lowOne = (U32)((total * 3) / (ToDistribute * 2));
for (s = 0; s <= maxSymbolValue; s++) {
if ((norm[s] == NOT_YET_ASSIGNED) && (count[s] <= lowOne)) {
norm[s] = 1;
distributed++;
total -= count[s];
continue;
}
}
ToDistribute = (1 << tableLog) - distributed;
}
if (distributed == maxSymbolValue + 1) {
/* all values are pretty poor;
probably incompressible data (should have already been detected);
find max, then give all remaining points to max */
U32 maxV = 0, maxC = 0;
for (s = 0; s <= maxSymbolValue; s++)
if (count[s] > maxC)
maxV = s, maxC = count[s];
norm[maxV] += (short)ToDistribute;
return 0;
}
if (total == 0) {
/* all of the symbols were low enough for the lowOne or lowThreshold */
for (s = 0; ToDistribute > 0; s = (s + 1) % (maxSymbolValue + 1))
if (norm[s] > 0)
ToDistribute--, norm[s]++;
return 0;
}
{
U64 const vStepLog = 62 - tableLog;
U64 const mid = (1ULL << (vStepLog - 1)) - 1;
U64 const rStep = div_u64((((U64)1 << vStepLog) * ToDistribute) + mid, (U32)total); /* scale on remaining */
U64 tmpTotal = mid;
for (s = 0; s <= maxSymbolValue; s++) {
if (norm[s] == NOT_YET_ASSIGNED) {
U64 const end = tmpTotal + (count[s] * rStep);
U32 const sStart = (U32)(tmpTotal >> vStepLog);
U32 const sEnd = (U32)(end >> vStepLog);
U32 const weight = sEnd - sStart;
if (weight < 1)
return ERROR(GENERIC);
norm[s] = (short)weight;
tmpTotal = end;
}
}
}
return 0;
}
size_t FSE_normalizeCount(short *normalizedCounter, unsigned tableLog, const unsigned *count, size_t total, unsigned maxSymbolValue)
{
/* Sanity checks */
if (tableLog == 0)
tableLog = FSE_DEFAULT_TABLELOG;
if (tableLog < FSE_MIN_TABLELOG)
return ERROR(GENERIC); /* Unsupported size */
if (tableLog > FSE_MAX_TABLELOG)
return ERROR(tableLog_tooLarge); /* Unsupported size */
if (tableLog < FSE_minTableLog(total, maxSymbolValue))
return ERROR(GENERIC); /* Too small tableLog, compression potentially impossible */
{
U32 const rtbTable[] = {0, 473195, 504333, 520860, 550000, 700000, 750000, 830000};
U64 const scale = 62 - tableLog;
U64 const step = div_u64((U64)1 << 62, (U32)total); /* <== here, one division ! */
U64 const vStep = 1ULL << (scale - 20);
int stillToDistribute = 1 << tableLog;
unsigned s;
unsigned largest = 0;
short largestP = 0;
U32 lowThreshold = (U32)(total >> tableLog);
for (s = 0; s <= maxSymbolValue; s++) {
if (count[s] == total)
return 0; /* rle special case */
if (count[s] == 0) {
normalizedCounter[s] = 0;
continue;
}
if (count[s] <= lowThreshold) {
normalizedCounter[s] = -1;
stillToDistribute--;
} else {
short proba = (short)((count[s] * step) >> scale);
if (proba < 8) {
U64 restToBeat = vStep * rtbTable[proba];
proba += (count[s] * step) - ((U64)proba << scale) > restToBeat;
}
if (proba > largestP)
largestP = proba, largest = s;
normalizedCounter[s] = proba;
stillToDistribute -= proba;
}
}
if (-stillToDistribute >= (normalizedCounter[largest] >> 1)) {
/* corner case, need another normalization method */
size_t const errorCode = FSE_normalizeM2(normalizedCounter, tableLog, count, total, maxSymbolValue);
if (FSE_isError(errorCode))
return errorCode;
} else
normalizedCounter[largest] += (short)stillToDistribute;
}
return tableLog;
}
/* fake FSE_CTable, for raw (uncompressed) input */
size_t FSE_buildCTable_raw(FSE_CTable *ct, unsigned nbBits)
{
const unsigned tableSize = 1 << nbBits;
const unsigned tableMask = tableSize - 1;
const unsigned maxSymbolValue = tableMask;
void *const ptr = ct;
U16 *const tableU16 = ((U16 *)ptr) + 2;
void *const FSCT = ((U32 *)ptr) + 1 /* header */ + (tableSize >> 1); /* assumption : tableLog >= 1 */
FSE_symbolCompressionTransform *const symbolTT = (FSE_symbolCompressionTransform *)(FSCT);
unsigned s;
/* Sanity checks */
if (nbBits < 1)
return ERROR(GENERIC); /* min size */
/* header */
tableU16[-2] = (U16)nbBits;
tableU16[-1] = (U16)maxSymbolValue;
/* Build table */
for (s = 0; s < tableSize; s++)
tableU16[s] = (U16)(tableSize + s);
/* Build Symbol Transformation Table */
{
const U32 deltaNbBits = (nbBits << 16) - (1 << nbBits);
for (s = 0; s <= maxSymbolValue; s++) {
symbolTT[s].deltaNbBits = deltaNbBits;
symbolTT[s].deltaFindState = s - 1;
}
}
return 0;
}
/* fake FSE_CTable, for rle input (always same symbol) */
size_t FSE_buildCTable_rle(FSE_CTable *ct, BYTE symbolValue)
{
void *ptr = ct;
U16 *tableU16 = ((U16 *)ptr) + 2;
void *FSCTptr = (U32 *)ptr + 2;
FSE_symbolCompressionTransform *symbolTT = (FSE_symbolCompressionTransform *)FSCTptr;
/* header */
tableU16[-2] = (U16)0;
tableU16[-1] = (U16)symbolValue;
/* Build table */
tableU16[0] = 0;
tableU16[1] = 0; /* just in case */
/* Build Symbol Transformation Table */
symbolTT[symbolValue].deltaNbBits = 0;
symbolTT[symbolValue].deltaFindState = 0;
return 0;
}
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)
{
const BYTE *const istart = (const BYTE *)src;
const BYTE *const iend = istart + srcSize;
const BYTE *ip = iend;
BIT_CStream_t bitC;
FSE_CState_t CState1, CState2;
/* init */
if (srcSize <= 2)
return 0;
{
size_t const initError = BIT_initCStream(&bitC, dst, dstSize);
if (FSE_isError(initError))
return 0; /* not enough space available to write a bitstream */
}
#define FSE_FLUSHBITS(s) (fast ? BIT_flushBitsFast(s) : BIT_flushBits(s))
if (srcSize & 1) {
FSE_initCState2(&CState1, ct, *--ip);
FSE_initCState2(&CState2, ct, *--ip);
FSE_encodeSymbol(&bitC, &CState1, *--ip);
FSE_FLUSHBITS(&bitC);
} else {
FSE_initCState2(&CState2, ct, *--ip);
FSE_initCState2(&CState1, ct, *--ip);
}
/* join to mod 4 */
srcSize -= 2;
if ((sizeof(bitC.bitContainer) * 8 > FSE_MAX_TABLELOG * 4 + 7) && (srcSize & 2)) { /* test bit 2 */
FSE_encodeSymbol(&bitC, &CState2, *--ip);
FSE_encodeSymbol(&bitC, &CState1, *--ip);
FSE_FLUSHBITS(&bitC);
}
/* 2 or 4 encoding per loop */
while (ip > istart) {
FSE_encodeSymbol(&bitC, &CState2, *--ip);
if (sizeof(bitC.bitContainer) * 8 < FSE_MAX_TABLELOG * 2 + 7) /* this test must be static */
FSE_FLUSHBITS(&bitC);
FSE_encodeSymbol(&bitC, &CState1, *--ip);
if (sizeof(bitC.bitContainer) * 8 > FSE_MAX_TABLELOG * 4 + 7) { /* this test must be static */
FSE_encodeSymbol(&bitC, &CState2, *--ip);
FSE_encodeSymbol(&bitC, &CState1, *--ip);
}
FSE_FLUSHBITS(&bitC);
}
FSE_flushCState(&bitC, &CState2);
FSE_flushCState(&bitC, &CState1);
return BIT_closeCStream(&bitC);
}
size_t FSE_compress_usingCTable(void *dst, size_t dstSize, const void *src, size_t srcSize, const FSE_CTable *ct)
{
unsigned const fast = (dstSize >= FSE_BLOCKBOUND(srcSize));
if (fast)
return FSE_compress_usingCTable_generic(dst, dstSize, src, srcSize, ct, 1);
else
return FSE_compress_usingCTable_generic(dst, dstSize, src, srcSize, ct, 0);
}
size_t FSE_compressBound(size_t size) { return FSE_COMPRESSBOUND(size); }
![swh spinner](/static/img/swh-spinner.gif)
Computing file changes ...