Coverage Report

Created: 2026-11-13 07:26

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