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