[linux-block.git] / lib / zstd / common / entropy_common.c

/* ******************************************************************
 * Common functions of New Generation Entropy library
 * Copyright (c) Yann Collet, Facebook, Inc.
 *
 *  You can contact the author at :
 *  - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy
 *  - Public forum : https://groups.google.com/forum/#!forum/lz4c
 *
 * This source code is licensed under both the BSD-style license (found in the
 * LICENSE file in the root directory of this source tree) and the GPLv2 (found
 * in the COPYING file in the root directory of this source tree).
 * You may select, at your option, one of the above-listed licenses.
****************************************************************** */

/* *************************************
*  Dependencies
***************************************/
#include <linux/module.h>
#include "mem.h"
#include "error_private.h"       /* ERR_*, ERROR */
#define FSE_STATIC_LINKING_ONLY  /* FSE_MIN_TABLELOG */
#include "fse.h"
#define HUF_STATIC_LINKING_ONLY  /* HUF_TABLELOG_ABSOLUTEMAX */
#include "huf.h"


/*===   Version   ===*/
unsigned FSE_versionNumber(void) { return FSE_VERSION_NUMBER; }


/*===   Error Management   ===*/
unsigned FSE_isError(size_t code) { return ERR_isError(code); }
const char* FSE_getErrorName(size_t code) { return ERR_getErrorName(code); }

unsigned HUF_isError(size_t code) { return ERR_isError(code); }
const char* HUF_getErrorName(size_t code) { return ERR_getErrorName(code); }


/*-**************************************************************
*  FSE NCount encoding-decoding
****************************************************************/
static U32 FSE_ctz(U32 val)
{
    assert(val != 0);
    {
#   if (__GNUC__ >= 3)   /* GCC Intrinsic */
        return __builtin_ctz(val);
#   else   /* Software version */
        U32 count = 0;
        while ((val & 1) == 0) {
            val >>= 1;
            ++count;
        }
        return count;
#   endif
    }
}

FORCE_INLINE_TEMPLATE
size_t FSE_readNCount_body(short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
                           const void* headerBuffer, size_t hbSize)
{
    const BYTE* const istart = (const BYTE*) headerBuffer;
    const BYTE* const iend = istart + hbSize;
    const BYTE* ip = istart;
    int nbBits;
    int remaining;
    int threshold;
    U32 bitStream;
    int bitCount;
    unsigned charnum = 0;
    unsigned const maxSV1 = *maxSVPtr + 1;
    int previous0 = 0;

    if (hbSize < 8) {
        /* This function only works when hbSize >= 8 */
        char buffer[8] = {0};
        ZSTD_memcpy(buffer, headerBuffer, hbSize);
        {   size_t const countSize = FSE_readNCount(normalizedCounter, maxSVPtr, tableLogPtr,
                                                    buffer, sizeof(buffer));
            if (FSE_isError(countSize)) return countSize;
            if (countSize > hbSize) return ERROR(corruption_detected);
            return countSize;
    }   }
    assert(hbSize >= 8);

    /* init */
    ZSTD_memset(normalizedCounter, 0, (*maxSVPtr+1) * sizeof(normalizedCounter[0]));   /* all symbols not present in NCount have a frequency of 0 */
    bitStream = MEM_readLE32(ip);
    nbBits = (bitStream & 0xF) + FSE_MIN_TABLELOG;   /* extract tableLog */
    if (nbBits > FSE_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge);
    bitStream >>= 4;
    bitCount = 4;
    *tableLogPtr = nbBits;
    remaining = (1<<nbBits)+1;
    threshold = 1<<nbBits;
    nbBits++;

    for (;;) {
        if (previous0) {
            /* Count the number of repeats. Each time the
             * 2-bit repeat code is 0b11 there is another
             * repeat.
             * Avoid UB by setting the high bit to 1.
             */
            int repeats = FSE_ctz(~bitStream | 0x80000000) >> 1;
            while (repeats >= 12) {
                charnum += 3 * 12;
                if (LIKELY(ip <= iend-7)) {
                    ip += 3;
                } else {
                    bitCount -= (int)(8 * (iend - 7 - ip));
                    bitCount &= 31;
                    ip = iend - 4;
                }
                bitStream = MEM_readLE32(ip) >> bitCount;
                repeats = FSE_ctz(~bitStream | 0x80000000) >> 1;
            }
            charnum += 3 * repeats;
            bitStream >>= 2 * repeats;
            bitCount += 2 * repeats;

            /* Add the final repeat which isn't 0b11. */
            assert((bitStream & 3) < 3);
            charnum += bitStream & 3;
            bitCount += 2;

            /* This is an error, but break and return an error
             * at the end, because returning out of a loop makes
             * it harder for the compiler to optimize.
             */
            if (charnum >= maxSV1) break;

            /* We don't need to set the normalized count to 0
             * because we already memset the whole buffer to 0.
             */

            if (LIKELY(ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
                assert((bitCount >> 3) <= 3); /* For first condition to work */
                ip += bitCount>>3;
                bitCount &= 7;
            } else {
                bitCount -= (int)(8 * (iend - 4 - ip));
                bitCount &= 31;
                ip = iend - 4;
            }
            bitStream = MEM_readLE32(ip) >> bitCount;
        }
        {
            int const max = (2*threshold-1) - remaining;
            int count;

            if ((bitStream & (threshold-1)) < (U32)max) {
                count = bitStream & (threshold-1);
                bitCount += nbBits-1;
            } else {
                count = bitStream & (2*threshold-1);
                if (count >= threshold) count -= max;
                bitCount += nbBits;
            }

            count--;   /* extra accuracy */
            /* When it matters (small blocks), this is a
             * predictable branch, because we don't use -1.
             */
            if (count >= 0) {
                remaining -= count;
            } else {
                assert(count == -1);
                remaining += count;
            }
            normalizedCounter[charnum++] = (short)count;
            previous0 = !count;

            assert(threshold > 1);
            if (remaining < threshold) {
                /* This branch can be folded into the
                 * threshold update condition because we
                 * know that threshold > 1.
                 */
                if (remaining <= 1) break;
                nbBits = BIT_highbit32(remaining) + 1;
                threshold = 1 << (nbBits - 1);
            }
            if (charnum >= maxSV1) break;

            if (LIKELY(ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) {
                ip += bitCount>>3;
                bitCount &= 7;
            } else {
                bitCount -= (int)(8 * (iend - 4 - ip));
                bitCount &= 31;
                ip = iend - 4;
            }
            bitStream = MEM_readLE32(ip) >> bitCount;
    }   }
    if (remaining != 1) return ERROR(corruption_detected);
    /* Only possible when there are too many zeros. */
    if (charnum > maxSV1) return ERROR(maxSymbolValue_tooSmall);
    if (bitCount > 32) return ERROR(corruption_detected);
    *maxSVPtr = charnum-1;

    ip += (bitCount+7)>>3;
    return ip-istart;
}

/* Avoids the FORCE_INLINE of the _body() function. */
static size_t FSE_readNCount_body_default(
        short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
        const void* headerBuffer, size_t hbSize)
{
    return FSE_readNCount_body(normalizedCounter, maxSVPtr, tableLogPtr, headerBuffer, hbSize);
}

#if DYNAMIC_BMI2
TARGET_ATTRIBUTE("bmi2") static size_t FSE_readNCount_body_bmi2(
        short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
        const void* headerBuffer, size_t hbSize)
{
    return FSE_readNCount_body(normalizedCounter, maxSVPtr, tableLogPtr, headerBuffer, hbSize);
}
#endif

size_t FSE_readNCount_bmi2(
        short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
        const void* headerBuffer, size_t hbSize, int bmi2)
{
#if DYNAMIC_BMI2
    if (bmi2) {
        return FSE_readNCount_body_bmi2(normalizedCounter, maxSVPtr, tableLogPtr, headerBuffer, hbSize);
    }
#endif
    (void)bmi2;
    return FSE_readNCount_body_default(normalizedCounter, maxSVPtr, tableLogPtr, headerBuffer, hbSize);
}

size_t FSE_readNCount(
        short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
        const void* headerBuffer, size_t hbSize)
{
    return FSE_readNCount_bmi2(normalizedCounter, maxSVPtr, tableLogPtr, headerBuffer, hbSize, /* bmi2 */ 0);
}
EXPORT_SYMBOL_GPL(FSE_readNCount);

/*! HUF_readStats() :
    Read compact Huffman tree, saved by HUF_writeCTable().
    `huffWeight` is destination buffer.
    `rankStats` is assumed to be a table of at least HUF_TABLELOG_MAX U32.
    @return : size read from `src` , or an error Code .
    Note : Needed by HUF_readCTable() and HUF_readDTableX?() .
*/
size_t HUF_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
                     U32* nbSymbolsPtr, U32* tableLogPtr,
                     const void* src, size_t srcSize)
{
    U32 wksp[HUF_READ_STATS_WORKSPACE_SIZE_U32];
    return HUF_readStats_wksp(huffWeight, hwSize, rankStats, nbSymbolsPtr, tableLogPtr, src, srcSize, wksp, sizeof(wksp), /* bmi2 */ 0);
}
EXPORT_SYMBOL_GPL(HUF_readStats);

FORCE_INLINE_TEMPLATE size_t
HUF_readStats_body(BYTE* huffWeight, size_t hwSize, U32* rankStats,
                   U32* nbSymbolsPtr, U32* tableLogPtr,
                   const void* src, size_t srcSize,
                   void* workSpace, size_t wkspSize,
                   int bmi2)
{
    U32 weightTotal;
    const BYTE* ip = (const BYTE*) src;
    size_t iSize;
    size_t oSize;

    if (!srcSize) return ERROR(srcSize_wrong);
    iSize = ip[0];
    /* ZSTD_memset(huffWeight, 0, hwSize);   *//* is not necessary, even though some analyzer complain ... */

    if (iSize >= 128) {  /* special header */
        oSize = iSize - 127;
        iSize = ((oSize+1)/2);
        if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
        if (oSize >= hwSize) return ERROR(corruption_detected);
        ip += 1;
        {   U32 n;
            for (n=0; n<oSize; n+=2) {
                huffWeight[n]   = ip[n/2] >> 4;
                huffWeight[n+1] = ip[n/2] & 15;
    }   }   }
    else  {   /* header compressed with FSE (normal case) */
        if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
        /* max (hwSize-1) values decoded, as last one is implied */
        oSize = FSE_decompress_wksp_bmi2(huffWeight, hwSize-1, ip+1, iSize, 6, workSpace, wkspSize, bmi2);
        if (FSE_isError(oSize)) return oSize;
    }

    /* collect weight stats */
    ZSTD_memset(rankStats, 0, (HUF_TABLELOG_MAX + 1) * sizeof(U32));
    weightTotal = 0;
    {   U32 n; for (n=0; n<oSize; n++) {
            if (huffWeight[n] >= HUF_TABLELOG_MAX) return ERROR(corruption_detected);
            rankStats[huffWeight[n]]++;
            weightTotal += (1 << huffWeight[n]) >> 1;
    }   }
    if (weightTotal == 0) return ERROR(corruption_detected);

    /* get last non-null symbol weight (implied, total must be 2^n) */
    {   U32 const tableLog = BIT_highbit32(weightTotal) + 1;
        if (tableLog > HUF_TABLELOG_MAX) return ERROR(corruption_detected);
        *tableLogPtr = tableLog;
        /* determine last weight */
        {   U32 const total = 1 << tableLog;
            U32 const rest = total - weightTotal;
            U32 const verif = 1 << BIT_highbit32(rest);
            U32 const lastWeight = BIT_highbit32(rest) + 1;
            if (verif != rest) return ERROR(corruption_detected);    /* last value must be a clean power of 2 */
            huffWeight[oSize] = (BYTE)lastWeight;
            rankStats[lastWeight]++;
    }   }

    /* check tree construction validity */
    if ((rankStats[1] < 2) || (rankStats[1] & 1)) return ERROR(corruption_detected);   /* by construction : at least 2 elts of rank 1, must be even */

    /* results */
    *nbSymbolsPtr = (U32)(oSize+1);
    return iSize+1;
}

/* Avoids the FORCE_INLINE of the _body() function. */
static size_t HUF_readStats_body_default(BYTE* huffWeight, size_t hwSize, U32* rankStats,
                     U32* nbSymbolsPtr, U32* tableLogPtr,
                     const void* src, size_t srcSize,
                     void* workSpace, size_t wkspSize)
{
    return HUF_readStats_body(huffWeight, hwSize, rankStats, nbSymbolsPtr, tableLogPtr, src, srcSize, workSpace, wkspSize, 0);
}

#if DYNAMIC_BMI2
static TARGET_ATTRIBUTE("bmi2") size_t HUF_readStats_body_bmi2(BYTE* huffWeight, size_t hwSize, U32* rankStats,
                     U32* nbSymbolsPtr, U32* tableLogPtr,
                     const void* src, size_t srcSize,
                     void* workSpace, size_t wkspSize)
{
    return HUF_readStats_body(huffWeight, hwSize, rankStats, nbSymbolsPtr, tableLogPtr, src, srcSize, workSpace, wkspSize, 1);
}
#endif

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 wkspSize,
                     int bmi2)
{
#if DYNAMIC_BMI2
    if (bmi2) {
        return HUF_readStats_body_bmi2(huffWeight, hwSize, rankStats, nbSymbolsPtr, tableLogPtr, src, srcSize, workSpace, wkspSize);
    }
#endif
    (void)bmi2;
    return HUF_readStats_body_default(huffWeight, hwSize, rankStats, nbSymbolsPtr, tableLogPtr, src, srcSize, workSpace, wkspSize);
}
EXPORT_SYMBOL_GPL(HUF_readStats_wksp);
Commit	Line	Data
e0c1b49f NT	1	/* ******************************************************************
	2	* Common functions of New Generation Entropy library
	3	* Copyright (c) Yann Collet, Facebook, Inc.
	4	*
	5	* You can contact the author at :
	6	* - FSE+HUF source repository : https://github.com/Cyan4973/FiniteStateEntropy
	7	* - Public forum : https://groups.google.com/forum/#!forum/lz4c
	8	*
	9	* This source code is licensed under both the BSD-style license (found in the
	10	* LICENSE file in the root directory of this source tree) and the GPLv2 (found
	11	* in the COPYING file in the root directory of this source tree).
	12	* You may select, at your option, one of the above-listed licenses.
	13	****************************************************************** */
	14
	15	/* *************************************
	16	* Dependencies
	17	***************************************/
637a642f	18	#include <linux/module.h>
e0c1b49f NT	19	#include "mem.h"
	20	#include "error_private.h" /* ERR_, ERROR /
	21	#define FSE_STATIC_LINKING_ONLY /* FSE_MIN_TABLELOG */
	22	#include "fse.h"
	23	#define HUF_STATIC_LINKING_ONLY /* HUF_TABLELOG_ABSOLUTEMAX */
	24	#include "huf.h"
	25
	26
	27	/=== Version ===/
	28	unsigned FSE_versionNumber(void) { return FSE_VERSION_NUMBER; }
	29
	30
	31	/=== Error Management ===/
	32	unsigned FSE_isError(size_t code) { return ERR_isError(code); }
	33	const char* FSE_getErrorName(size_t code) { return ERR_getErrorName(code); }
	34
	35	unsigned HUF_isError(size_t code) { return ERR_isError(code); }
	36	const char* HUF_getErrorName(size_t code) { return ERR_getErrorName(code); }
	37
	38
	39	/-*************************************************************
	40	* FSE NCount encoding-decoding
	41	****************************************************************/
	42	static U32 FSE_ctz(U32 val)
	43	{
	44	assert(val != 0);
	45	{
	46	# if (__GNUC__ >= 3) /* GCC Intrinsic */
	47	return __builtin_ctz(val);
	48	# else /* Software version */
	49	U32 count = 0;
	50	while ((val & 1) == 0) {
	51	val >>= 1;
	52	++count;
	53	}
	54	return count;
	55	# endif
	56	}
	57	}
	58
	59	FORCE_INLINE_TEMPLATE
	60	size_t FSE_readNCount_body(short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
	61	const void* headerBuffer, size_t hbSize)
	62	{
	63	const BYTE* const istart = (const BYTE*) headerBuffer;
	64	const BYTE* const iend = istart + hbSize;
	65	const BYTE* ip = istart;
	66	int nbBits;
	67	int remaining;
	68	int threshold;
	69	U32 bitStream;
	70	int bitCount;
	71	unsigned charnum = 0;
	72	unsigned const maxSV1 = *maxSVPtr + 1;
	73	int previous0 = 0;
	74
	75	if (hbSize < 8) {
	76	/* This function only works when hbSize >= 8 */
	77	char buffer[8] = {0};
	78	ZSTD_memcpy(buffer, headerBuffer, hbSize);
	79	{ size_t const countSize = FSE_readNCount(normalizedCounter, maxSVPtr, tableLogPtr,
	80	buffer, sizeof(buffer));
	81	if (FSE_isError(countSize)) return countSize;
	82	if (countSize > hbSize) return ERROR(corruption_detected);
83	return countSize;
84	} }
85	assert(hbSize >= 8);
86
87	/* init */
88	ZSTD_memset(normalizedCounter, 0, (maxSVPtr+1) sizeof(normalizedCounter[0])); /* all symbols not present in NCount have a frequency of 0 */
89	bitStream = MEM_readLE32(ip);
90	nbBits = (bitStream & 0xF) + FSE_MIN_TABLELOG; /* extract tableLog */
91	if (nbBits > FSE_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge);
92	bitStream >>= 4;
93	bitCount = 4;
94	*tableLogPtr = nbBits;
95	remaining = (1<<nbBits)+1;
96	threshold = 1<<nbBits;
97	nbBits++;
98
99	for (;;) {
100	if (previous0) {
101	/* Count the number of repeats. Each time the
102	* 2-bit repeat code is 0b11 there is another
103	* repeat.
104	* Avoid UB by setting the high bit to 1.
105	*/
106	int repeats = FSE_ctz(~bitStream \| 0x80000000) >> 1;
107	while (repeats >= 12) {
108	charnum += 3 * 12;
109	if (LIKELY(ip <= iend-7)) {
110	ip += 3;
111	} else {
112	bitCount -= (int)(8 * (iend - 7 - ip));
113	bitCount &= 31;
114	ip = iend - 4;
115	}
116	bitStream = MEM_readLE32(ip) >> bitCount;
117	repeats = FSE_ctz(~bitStream \| 0x80000000) >> 1;
118	}
119	charnum += 3 * repeats;
120	bitStream >>= 2 * repeats;
121	bitCount += 2 * repeats;
122
123	/* Add the final repeat which isn't 0b11. */
124	assert((bitStream & 3) < 3);
125	charnum += bitStream & 3;
126	bitCount += 2;
127
128	/* This is an error, but break and return an error
129	* at the end, because returning out of a loop makes
130	* it harder for the compiler to optimize.
131	*/
132	if (charnum >= maxSV1) break;
133
134	/* We don't need to set the normalized count to 0
135	* because we already memset the whole buffer to 0.
136	*/
137
138	if (LIKELY(ip <= iend-7) \|\| (ip + (bitCount>>3) <= iend-4)) {
139	assert((bitCount >> 3) <= 3); /* For first condition to work */
140	ip += bitCount>>3;
141	bitCount &= 7;
142	} else {
143	bitCount -= (int)(8 * (iend - 4 - ip));
144	bitCount &= 31;
145	ip = iend - 4;
146	}
147	bitStream = MEM_readLE32(ip) >> bitCount;
148	}
149	{
150	int const max = (2*threshold-1) - remaining;
151	int count;
152
153	if ((bitStream & (threshold-1)) < (U32)max) {
154	count = bitStream & (threshold-1);
155	bitCount += nbBits-1;
156	} else {
157	count = bitStream & (2*threshold-1);
158	if (count >= threshold) count -= max;
159	bitCount += nbBits;
160	}
161
162	count--; /* extra accuracy */
163	/* When it matters (small blocks), this is a
164	* predictable branch, because we don't use -1.
165	*/
166	if (count >= 0) {
167	remaining -= count;
168	} else {
169	assert(count == -1);
170	remaining += count;
171	}
172	normalizedCounter[charnum++] = (short)count;
173	previous0 = !count;
174
175	assert(threshold > 1);
176	if (remaining < threshold) {
177	/* This branch can be folded into the
178	* threshold update condition because we
179	* know that threshold > 1.
180	*/
181	if (remaining <= 1) break;
182	nbBits = BIT_highbit32(remaining) + 1;
183	threshold = 1 << (nbBits - 1);
184	}
185	if (charnum >= maxSV1) break;
186
187	if (LIKELY(ip <= iend-7) \|\| (ip + (bitCount>>3) <= iend-4)) {
188	ip += bitCount>>3;
189	bitCount &= 7;
190	} else {
191	bitCount -= (int)(8 * (iend - 4 - ip));
192	bitCount &= 31;
193	ip = iend - 4;
194	}
195	bitStream = MEM_readLE32(ip) >> bitCount;
196	} }
197	if (remaining != 1) return ERROR(corruption_detected);
198	/* Only possible when there are too many zeros. */
199	if (charnum > maxSV1) return ERROR(maxSymbolValue_tooSmall);
200	if (bitCount > 32) return ERROR(corruption_detected);
201	*maxSVPtr = charnum-1;
202
203	ip += (bitCount+7)>>3;
204	return ip-istart;
205	}
206
207	/* Avoids the FORCE_INLINE of the _body() function. */
208	static size_t FSE_readNCount_body_default(
209	short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
210	const void* headerBuffer, size_t hbSize)
211	{
212	return FSE_readNCount_body(normalizedCounter, maxSVPtr, tableLogPtr, headerBuffer, hbSize);
213	}
214
215	#if DYNAMIC_BMI2
216	TARGET_ATTRIBUTE("bmi2") static size_t FSE_readNCount_body_bmi2(
217	short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
218	const void* headerBuffer, size_t hbSize)
219	{
220	return FSE_readNCount_body(normalizedCounter, maxSVPtr, tableLogPtr, headerBuffer, hbSize);
221	}
222	#endif
223
224	size_t FSE_readNCount_bmi2(
225	short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
226	const void* headerBuffer, size_t hbSize, int bmi2)
227	{
228	#if DYNAMIC_BMI2
229	if (bmi2) {
230	return FSE_readNCount_body_bmi2(normalizedCounter, maxSVPtr, tableLogPtr, headerBuffer, hbSize);
231	}
232	#endif
233	(void)bmi2;
234	return FSE_readNCount_body_default(normalizedCounter, maxSVPtr, tableLogPtr, headerBuffer, hbSize);
235	}
236
237	size_t FSE_readNCount(
238	short* normalizedCounter, unsigned* maxSVPtr, unsigned* tableLogPtr,
239	const void* headerBuffer, size_t hbSize)
240	{
241	return FSE_readNCount_bmi2(normalizedCounter, maxSVPtr, tableLogPtr, headerBuffer, hbSize, /* bmi2 */ 0);
242	}
637a642f	243	EXPORT_SYMBOL_GPL(FSE_readNCount);
e0c1b49f NT	244
	245	/*! HUF_readStats() :
	246	Read compact Huffman tree, saved by HUF_writeCTable().
	247	`huffWeight` is destination buffer.
	248	`rankStats` is assumed to be a table of at least HUF_TABLELOG_MAX U32.
	249	@return : size read from `src` , or an error Code .
	250	Note : Needed by HUF_readCTable() and HUF_readDTableX?() .
	251	*/
	252	size_t HUF_readStats(BYTE* huffWeight, size_t hwSize, U32* rankStats,
	253	U32* nbSymbolsPtr, U32* tableLogPtr,
	254	const void* src, size_t srcSize)
	255	{
	256	U32 wksp[HUF_READ_STATS_WORKSPACE_SIZE_U32];
	257	return HUF_readStats_wksp(huffWeight, hwSize, rankStats, nbSymbolsPtr, tableLogPtr, src, srcSize, wksp, sizeof(wksp), /* bmi2 */ 0);
	258	}
637a642f	259	EXPORT_SYMBOL_GPL(HUF_readStats);
e0c1b49f NT	260
	261	FORCE_INLINE_TEMPLATE size_t
	262	HUF_readStats_body(BYTE* huffWeight, size_t hwSize, U32* rankStats,
	263	U32* nbSymbolsPtr, U32* tableLogPtr,
	264	const void* src, size_t srcSize,
	265	void* workSpace, size_t wkspSize,
	266	int bmi2)
	267	{
	268	U32 weightTotal;
	269	const BYTE* ip = (const BYTE*) src;
	270	size_t iSize;
	271	size_t oSize;
	272
	273	if (!srcSize) return ERROR(srcSize_wrong);
	274	iSize = ip[0];
	275	/* ZSTD_memset(huffWeight, 0, hwSize); // is not necessary, even though some analyzer complain ... */
	276
	277	if (iSize >= 128) { /* special header */
	278	oSize = iSize - 127;
	279	iSize = ((oSize+1)/2);
	280	if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
	281	if (oSize >= hwSize) return ERROR(corruption_detected);
	282	ip += 1;
	283	{ U32 n;
	284	for (n=0; n<oSize; n+=2) {
	285	huffWeight[n] = ip[n/2] >> 4;
	286	huffWeight[n+1] = ip[n/2] & 15;
	287	} } }
	288	else { /* header compressed with FSE (normal case) */
	289	if (iSize+1 > srcSize) return ERROR(srcSize_wrong);
	290	/* max (hwSize-1) values decoded, as last one is implied */
	291	oSize = FSE_decompress_wksp_bmi2(huffWeight, hwSize-1, ip+1, iSize, 6, workSpace, wkspSize, bmi2);
	292	if (FSE_isError(oSize)) return oSize;
	293	}
	294
	295	/* collect weight stats */
	296	ZSTD_memset(rankStats, 0, (HUF_TABLELOG_MAX + 1) * sizeof(U32));
	297	weightTotal = 0;
	298	{ U32 n; for (n=0; n<oSize; n++) {
	299	if (huffWeight[n] >= HUF_TABLELOG_MAX) return ERROR(corruption_detected);
	300	rankStats[huffWeight[n]]++;
	301	weightTotal += (1 << huffWeight[n]) >> 1;
	302	} }
	303	if (weightTotal == 0) return ERROR(corruption_detected);
	304
	305	/* get last non-null symbol weight (implied, total must be 2^n) */
	306	{ U32 const tableLog = BIT_highbit32(weightTotal) + 1;
	307	if (tableLog > HUF_TABLELOG_MAX) return ERROR(corruption_detected);
	308	*tableLogPtr = tableLog;
	309	/* determine last weight */
	310	{ U32 const total = 1 << tableLog;
	311	U32 const rest = total - weightTotal;
	312	U32 const verif = 1 << BIT_highbit32(rest);
	313	U32 const lastWeight = BIT_highbit32(rest) + 1;
	314	if (verif != rest) return ERROR(corruption_detected); /* last value must be a clean power of 2 */
	315	huffWeight[oSize] = (BYTE)lastWeight;
	316	rankStats[lastWeight]++;
	317	} }
	318
	319	/* check tree construction validity */
	320	if ((rankStats[1] < 2) \|\| (rankStats[1] & 1)) return ERROR(corruption_detected); /* by construction : at least 2 elts of rank 1, must be even */
	321
	322	/* results */
	323	*nbSymbolsPtr = (U32)(oSize+1);
324	return iSize+1;
325	}
326
327	/* Avoids the FORCE_INLINE of the _body() function. */
328	static size_t HUF_readStats_body_default(BYTE* huffWeight, size_t hwSize, U32* rankStats,
329	U32* nbSymbolsPtr, U32* tableLogPtr,
330	const void* src, size_t srcSize,
331	void* workSpace, size_t wkspSize)
332	{
333	return HUF_readStats_body(huffWeight, hwSize, rankStats, nbSymbolsPtr, tableLogPtr, src, srcSize, workSpace, wkspSize, 0);
334	}
335
336	#if DYNAMIC_BMI2
337	static TARGET_ATTRIBUTE("bmi2") size_t HUF_readStats_body_bmi2(BYTE* huffWeight, size_t hwSize, U32* rankStats,
338	U32* nbSymbolsPtr, U32* tableLogPtr,
339	const void* src, size_t srcSize,
340	void* workSpace, size_t wkspSize)
341	{
342	return HUF_readStats_body(huffWeight, hwSize, rankStats, nbSymbolsPtr, tableLogPtr, src, srcSize, workSpace, wkspSize, 1);
343	}
344	#endif
345
346	size_t HUF_readStats_wksp(BYTE* huffWeight, size_t hwSize, U32* rankStats,
347	U32* nbSymbolsPtr, U32* tableLogPtr,
348	const void* src, size_t srcSize,
349	void* workSpace, size_t wkspSize,
350	int bmi2)
351	{
352	#if DYNAMIC_BMI2
353	if (bmi2) {
354	return HUF_readStats_body_bmi2(huffWeight, hwSize, rankStats, nbSymbolsPtr, tableLogPtr, src, srcSize, workSpace, wkspSize);
355	}
356	#endif
357	(void)bmi2;
358	return HUF_readStats_body_default(huffWeight, hwSize, rankStats, nbSymbolsPtr, tableLogPtr, src, srcSize, workSpace, wkspSize);
359	}
637a642f	360	EXPORT_SYMBOL_GPL(HUF_readStats_wksp);