entropy_common.c:ZSTD_countTrailingZeros32: 29| 1.43k|{ 30| 1.43k| assert(val != 0); ------------------ | Branch (30:5): [True: 0, False: 1.43k] | Branch (30:5): [True: 1.43k, False: 0] ------------------ 31| |#if defined(_MSC_VER) 32| |# if STATIC_BMI2 33| | return (unsigned)_tzcnt_u32(val); 34| |# else 35| | if (val != 0) { 36| | unsigned long r; 37| | _BitScanForward(&r, val); 38| | return (unsigned)r; 39| | } else { 40| | __assume(0); /* Should not reach this code path */ 41| | } 42| |# endif 43| |#elif defined(__GNUC__) && (__GNUC__ >= 4) 44| 1.43k| return (unsigned)__builtin_ctz(val); 45| |#elif defined(__ICCARM__) 46| | return (unsigned)__builtin_ctz(val); 47| |#else 48| | return ZSTD_countTrailingZeros32_fallback(val); 49| |#endif 50| 1.43k|} entropy_common.c:ZSTD_highbit32: 175| 780|{ 176| 780| assert(val != 0); ------------------ | Branch (176:5): [True: 0, False: 780] | Branch (176:5): [True: 780, False: 0] ------------------ 177| 780| return 31 - ZSTD_countLeadingZeros32(val); 178| 780|} entropy_common.c:ZSTD_countLeadingZeros32: 70| 780|{ 71| 780| assert(val != 0); ------------------ | Branch (71:5): [True: 0, False: 780] | Branch (71:5): [True: 780, False: 0] ------------------ 72| |#if defined(_MSC_VER) 73| |# if STATIC_BMI2 74| | return (unsigned)_lzcnt_u32(val); 75| |# else 76| | if (val != 0) { 77| | unsigned long r; 78| | _BitScanReverse(&r, val); 79| | return (unsigned)(31 - r); 80| | } else { 81| | __assume(0); /* Should not reach this code path */ 82| | } 83| |# endif 84| |#elif defined(__GNUC__) && (__GNUC__ >= 4) 85| 780| return (unsigned)__builtin_clz(val); 86| |#elif defined(__ICCARM__) 87| | return (unsigned)__builtin_clz(val); 88| |#else 89| | return ZSTD_countLeadingZeros32_fallback(val); 90| |#endif 91| 780|} FSE_isError: 31| 49|unsigned FSE_isError(size_t code) { return ERR_isError(code); } FSE_readNCount_bmi2: 209| 299|{ 210| 299|#if DYNAMIC_BMI2 211| 299| if (bmi2) { ------------------ | Branch (211:9): [True: 0, False: 299] ------------------ 212| 0| return FSE_readNCount_body_bmi2(normalizedCounter, maxSVPtr, tableLogPtr, headerBuffer, hbSize); 213| 0| } 214| 299|#endif 215| 299| (void)bmi2; 216| 299| return FSE_readNCount_body_default(normalizedCounter, maxSVPtr, tableLogPtr, headerBuffer, hbSize); 217| 299|} FSE_readNCount: 222| 299|{ 223| 299| return FSE_readNCount_bmi2(normalizedCounter, maxSVPtr, tableLogPtr, headerBuffer, hbSize, /* bmi2 */ 0); 224| 299|} entropy_common.c:FSE_readNCount_body: 44| 299|{ 45| 299| const BYTE* const istart = (const BYTE*) headerBuffer; 46| 299| const BYTE* const iend = istart + hbSize; 47| 299| const BYTE* ip = istart; 48| 299| int nbBits; 49| 299| int remaining; 50| 299| int threshold; 51| 299| U32 bitStream; 52| 299| int bitCount; 53| 299| unsigned charnum = 0; 54| 299| unsigned const maxSV1 = *maxSVPtr + 1; 55| 299| int previous0 = 0; 56| | 57| 299| if (hbSize < 8) { ------------------ | Branch (57:9): [True: 49, False: 250] ------------------ 58| | /* This function only works when hbSize >= 8 */ 59| 49| char buffer[8] = {0}; 60| 49| ZSTD_memcpy(buffer, headerBuffer, hbSize); ------------------ | | 44| 49|# define ZSTD_memcpy(d,s,l) __builtin_memcpy((d),(s),(l)) ------------------ 61| 49| { size_t const countSize = FSE_readNCount(normalizedCounter, maxSVPtr, tableLogPtr, 62| 49| buffer, sizeof(buffer)); 63| 49| if (FSE_isError(countSize)) return countSize; ------------------ | Branch (63:17): [True: 0, False: 49] ------------------ 64| 49| if (countSize > hbSize) return ERROR(corruption_detected); ------------------ | | 49| 0|#define ERROR(name) ZSTD_ERROR(name) | | ------------------ | | | | 50| 0|#define ZSTD_ERROR(name) ((size_t)-PREFIX(name)) | | | | ------------------ | | | | | | 42| 0|#define PREFIX(name) ZSTD_error_##name | | | | ------------------ | | ------------------ ------------------ | Branch (64:17): [True: 0, False: 49] ------------------ 65| 49| return countSize; 66| 49| } } 67| 299| assert(hbSize >= 8); ------------------ | Branch (67:5): [True: 0, False: 250] | Branch (67:5): [True: 250, False: 0] ------------------ 68| | 69| | /* init */ 70| 250| ZSTD_memset(normalizedCounter, 0, (*maxSVPtr+1) * sizeof(normalizedCounter[0])); /* all symbols not present in NCount have a frequency of 0 */ ------------------ | | 46| 250|# define ZSTD_memset(p,v,l) __builtin_memset((p),(v),(l)) ------------------ 71| 250| bitStream = MEM_readLE32(ip); 72| 250| nbBits = (bitStream & 0xF) + FSE_MIN_TABLELOG; /* extract tableLog */ ------------------ | | 616| 250|#define FSE_MIN_TABLELOG 5 ------------------ 73| 250| if (nbBits > FSE_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge); ------------------ | | 618| 250|#define FSE_TABLELOG_ABSOLUTE_MAX 15 ------------------ if (nbBits > FSE_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge); ------------------ | | 49| 0|#define ERROR(name) ZSTD_ERROR(name) | | ------------------ | | | | 50| 0|#define ZSTD_ERROR(name) ((size_t)-PREFIX(name)) | | | | ------------------ | | | | | | 42| 0|#define PREFIX(name) ZSTD_error_##name | | | | ------------------ | | ------------------ ------------------ | Branch (73:9): [True: 0, False: 250] ------------------ 74| 250| bitStream >>= 4; 75| 250| bitCount = 4; 76| 250| *tableLogPtr = nbBits; 77| 250| remaining = (1<> 1; 89| 1.43k| while (repeats >= 12) { ------------------ | Branch (89:20): [True: 309, False: 1.12k] ------------------ 90| 309| charnum += 3 * 12; 91| 309| if (LIKELY(ip <= iend-7)) { ------------------ | | 187| 309|#define LIKELY(x) (__builtin_expect((x), 1)) | | ------------------ | | | Branch (187:19): [True: 249, False: 60] | | ------------------ ------------------ 92| 249| ip += 3; 93| 249| } else { 94| 60| bitCount -= (int)(8 * (iend - 7 - ip)); 95| 60| bitCount &= 31; 96| 60| ip = iend - 4; 97| 60| } 98| 309| bitStream = MEM_readLE32(ip) >> bitCount; 99| 309| repeats = ZSTD_countTrailingZeros32(~bitStream | 0x80000000) >> 1; 100| 309| } 101| 1.12k| charnum += 3 * repeats; 102| 1.12k| bitStream >>= 2 * repeats; 103| 1.12k| bitCount += 2 * repeats; 104| | 105| | /* Add the final repeat which isn't 0b11. */ 106| 1.12k| assert((bitStream & 3) < 3); ------------------ | Branch (106:13): [True: 0, False: 1.12k] | Branch (106:13): [True: 1.12k, False: 0] ------------------ 107| 1.12k| charnum += bitStream & 3; 108| 1.12k| 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| 1.12k| if (charnum >= maxSV1) break; ------------------ | Branch (114:17): [True: 0, False: 1.12k] ------------------ 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| 1.12k| if (LIKELY(ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) { ------------------ | | 187| 2.24k|#define LIKELY(x) (__builtin_expect((x), 1)) | | ------------------ | | | Branch (187:19): [True: 950, False: 172] | | ------------------ ------------------ | Branch (120:41): [True: 43, False: 129] ------------------ 121| 993| assert((bitCount >> 3) <= 3); /* For first condition to work */ ------------------ | Branch (121:17): [True: 0, False: 993] | Branch (121:17): [True: 993, False: 0] ------------------ 122| 993| ip += bitCount>>3; 123| 993| bitCount &= 7; 124| 993| } else { 125| 129| bitCount -= (int)(8 * (iend - 4 - ip)); 126| 129| bitCount &= 31; 127| 129| ip = iend - 4; 128| 129| } 129| 1.12k| bitStream = MEM_readLE32(ip) >> bitCount; 130| 1.12k| } 131| 13.2k| { 132| 13.2k| int const max = (2*threshold-1) - remaining; 133| 13.2k| int count; 134| | 135| 13.2k| if ((bitStream & (threshold-1)) < (U32)max) { ------------------ | Branch (135:17): [True: 11.8k, False: 1.31k] ------------------ 136| 11.8k| count = bitStream & (threshold-1); 137| 11.8k| bitCount += nbBits-1; 138| 11.8k| } else { 139| 1.31k| count = bitStream & (2*threshold-1); 140| 1.31k| if (count >= threshold) count -= max; ------------------ | Branch (140:21): [True: 303, False: 1.01k] ------------------ 141| 1.31k| bitCount += nbBits; 142| 1.31k| } 143| | 144| 13.2k| count--; /* extra accuracy */ 145| | /* When it matters (small blocks), this is a 146| | * predictable branch, because we don't use -1. 147| | */ 148| 13.2k| if (count >= 0) { ------------------ | Branch (148:17): [True: 2.60k, False: 10.6k] ------------------ 149| 2.60k| remaining -= count; 150| 10.6k| } else { 151| 10.6k| assert(count == -1); ------------------ | Branch (151:17): [True: 0, False: 10.6k] | Branch (151:17): [True: 10.6k, False: 0] ------------------ 152| 10.6k| remaining += count; 153| 10.6k| } 154| 13.2k| normalizedCounter[charnum++] = (short)count; 155| 13.2k| previous0 = !count; 156| | 157| 13.2k| assert(threshold > 1); ------------------ | Branch (157:13): [True: 0, False: 13.2k] | Branch (157:13): [True: 13.2k, False: 0] ------------------ 158| 13.2k| if (remaining < threshold) { ------------------ | Branch (158:17): [True: 1.03k, False: 12.1k] ------------------ 159| | /* This branch can be folded into the 160| | * threshold update condition because we 161| | * know that threshold > 1. 162| | */ 163| 1.03k| if (remaining <= 1) break; ------------------ | Branch (163:21): [True: 250, False: 780] ------------------ 164| 780| nbBits = ZSTD_highbit32(remaining) + 1; 165| 780| threshold = 1 << (nbBits - 1); 166| 780| } 167| 12.9k| if (charnum >= maxSV1) break; ------------------ | Branch (167:17): [True: 0, False: 12.9k] ------------------ 168| | 169| 12.9k| if (LIKELY(ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) { ------------------ | | 187| 25.9k|#define LIKELY(x) (__builtin_expect((x), 1)) | | ------------------ | | | Branch (187:19): [True: 12.2k, False: 717] | | ------------------ ------------------ | Branch (169:41): [True: 448, False: 269] ------------------ 170| 12.6k| ip += bitCount>>3; 171| 12.6k| bitCount &= 7; 172| 12.6k| } else { 173| 269| bitCount -= (int)(8 * (iend - 4 - ip)); 174| 269| bitCount &= 31; 175| 269| ip = iend - 4; 176| 269| } 177| 12.9k| bitStream = MEM_readLE32(ip) >> bitCount; 178| 12.9k| } } 179| 250| if (remaining != 1) return ERROR(corruption_detected); ------------------ | | 49| 0|#define ERROR(name) ZSTD_ERROR(name) | | ------------------ | | | | 50| 0|#define ZSTD_ERROR(name) ((size_t)-PREFIX(name)) | | | | ------------------ | | | | | | 42| 0|#define PREFIX(name) ZSTD_error_##name | | | | ------------------ | | ------------------ ------------------ | Branch (179:9): [True: 0, False: 250] ------------------ 180| | /* Only possible when there are too many zeros. */ 181| 250| if (charnum > maxSV1) return ERROR(maxSymbolValue_tooSmall); ------------------ | | 49| 0|#define ERROR(name) ZSTD_ERROR(name) | | ------------------ | | | | 50| 0|#define ZSTD_ERROR(name) ((size_t)-PREFIX(name)) | | | | ------------------ | | | | | | 42| 0|#define PREFIX(name) ZSTD_error_##name | | | | ------------------ | | ------------------ ------------------ | Branch (181:9): [True: 0, False: 250] ------------------ 182| 250| if (bitCount > 32) return ERROR(corruption_detected); ------------------ | | 49| 0|#define ERROR(name) ZSTD_ERROR(name) | | ------------------ | | | | 50| 0|#define ZSTD_ERROR(name) ((size_t)-PREFIX(name)) | | | | ------------------ | | | | | | 42| 0|#define PREFIX(name) ZSTD_error_##name | | | | ------------------ | | ------------------ ------------------ | Branch (182:9): [True: 0, False: 250] ------------------ 183| 250| *maxSVPtr = charnum-1; 184| | 185| 250| ip += (bitCount+7)>>3; 186| 250| return ip-istart; 187| 250|} entropy_common.c:FSE_readNCount_body_default: 193| 299|{ 194| 299| return FSE_readNCount_body(normalizedCounter, maxSVPtr, tableLogPtr, headerBuffer, hbSize); 195| 299|} entropy_common.c:ERR_isError: 52| 49|ERR_STATIC unsigned ERR_isError(size_t code) { return (code > ERROR(maxCode)); } ------------------ | | 49| 49|#define ERROR(name) ZSTD_ERROR(name) | | ------------------ | | | | 50| 49|#define ZSTD_ERROR(name) ((size_t)-PREFIX(name)) | | | | ------------------ | | | | | | 42| 49|#define PREFIX(name) ZSTD_error_##name | | | | ------------------ | | ------------------ ------------------ zstd_common.c:ERR_isError: 52| 500|ERR_STATIC unsigned ERR_isError(size_t code) { return (code > ERROR(maxCode)); } ------------------ | | 49| 500|#define ERROR(name) ZSTD_ERROR(name) | | ------------------ | | | | 50| 500|#define ZSTD_ERROR(name) ((size_t)-PREFIX(name)) | | | | ------------------ | | | | | | 42| 500|#define PREFIX(name) ZSTD_error_##name | | | | ------------------ | | ------------------ ------------------ entropy_common.c:MEM_readLE32: 322| 14.6k|{ 323| 14.6k| if (MEM_isLittleEndian()) ------------------ | Branch (323:9): [True: 14.6k, False: 0] ------------------ 324| 14.6k| return MEM_read32(memPtr); 325| 0| else 326| 0| return MEM_swap32(MEM_read32(memPtr)); 327| 14.6k|} entropy_common.c:MEM_isLittleEndian: 141| 14.6k|{ 142| 14.6k|#if defined(__BYTE_ORDER__) && defined(__ORDER_LITTLE_ENDIAN__) && (__BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__) 143| 14.6k| return 1; 144| |#elif defined(__BYTE_ORDER__) && defined(__ORDER_BIG_ENDIAN__) && (__BYTE_ORDER__ == __ORDER_BIG_ENDIAN__) 145| | return 0; 146| |#elif defined(__clang__) && __LITTLE_ENDIAN__ 147| | return 1; 148| |#elif defined(__clang__) && __BIG_ENDIAN__ 149| | return 0; 150| |#elif defined(_MSC_VER) && (_M_X64 || _M_IX86) 151| | return 1; 152| |#elif defined(__DMC__) && defined(_M_IX86) 153| | return 1; 154| |#elif defined(__IAR_SYSTEMS_ICC__) && __LITTLE_ENDIAN__ 155| | return 1; 156| |#else 157| | const union { U32 u; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */ 158| | return one.c[0]; 159| |#endif 160| 14.6k|} entropy_common.c:MEM_read32: 202| 14.6k|{ 203| 14.6k| U32 val; ZSTD_memcpy(&val, memPtr, sizeof(val)); return val; ------------------ | | 44| 14.6k|# define ZSTD_memcpy(d,s,l) __builtin_memcpy((d),(s),(l)) ------------------ 204| 14.6k|} ZSTD_isError: 36| 500|unsigned ZSTD_isError(size_t code) { return ERR_isError(code); } FSE_NCountWriteBound: 224| 500|{ 225| 500| size_t const maxHeaderSize = (((maxSymbolValue+1) * tableLog 226| 500| + 4 /* bitCount initialized at 4 */ 227| 500| + 2 /* first two symbols may use one additional bit each */) / 8) 228| 500| + 1 /* round up to whole nb bytes */ 229| 500| + 2 /* additional two bytes for bitstream flush */; 230| 500| return maxSymbolValue ? maxHeaderSize : FSE_NCOUNTBOUND; /* maxSymbolValue==0 ? use default */ ------------------ | | 235| 74|#define FSE_NCOUNTBOUND 512 ------------------ | Branch (230:12): [True: 426, False: 74] ------------------ 231| 500|} FSE_writeNCount: 332| 250|{ 333| 250| if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge); /* Unsupported */ ------------------ | | 612| 250|#define FSE_MAX_TABLELOG (FSE_MAX_MEMORY_USAGE-2) | | ------------------ | | | | 582| 250|# define FSE_MAX_MEMORY_USAGE 14 | | ------------------ ------------------ if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge); /* Unsupported */ ------------------ | | 49| 0|#define ERROR(name) ZSTD_ERROR(name) | | ------------------ | | | | 50| 0|#define ZSTD_ERROR(name) ((size_t)-PREFIX(name)) | | | | ------------------ | | | | | | 42| 0|#define PREFIX(name) ZSTD_error_##name | | | | ------------------ | | ------------------ ------------------ | Branch (333:9): [True: 0, False: 250] ------------------ 334| 250| if (tableLog < FSE_MIN_TABLELOG) return ERROR(GENERIC); /* Unsupported */ ------------------ | | 616| 250|#define FSE_MIN_TABLELOG 5 ------------------ if (tableLog < FSE_MIN_TABLELOG) return ERROR(GENERIC); /* Unsupported */ ------------------ | | 49| 0|#define ERROR(name) ZSTD_ERROR(name) | | ------------------ | | | | 50| 0|#define ZSTD_ERROR(name) ((size_t)-PREFIX(name)) | | | | ------------------ | | | | | | 42| 0|#define PREFIX(name) ZSTD_error_##name | | | | ------------------ | | ------------------ ------------------ | Branch (334:9): [True: 0, False: 250] ------------------ 335| | 336| 250| if (bufferSize < FSE_NCountWriteBound(maxSymbolValue, tableLog)) ------------------ | Branch (336:9): [True: 0, False: 250] ------------------ 337| 0| return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 0); 338| | 339| 250| return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 1 /* write in buffer is safe */); 340| 250|} fse_compress.c:FSE_writeNCount_generic: 237| 250|{ 238| 250| BYTE* const ostart = (BYTE*) header; 239| 250| BYTE* out = ostart; 240| 250| BYTE* const oend = ostart + headerBufferSize; 241| 250| int nbBits; 242| 250| const int tableSize = 1 << tableLog; 243| 250| int remaining; 244| 250| int threshold; 245| 250| U32 bitStream = 0; 246| 250| int bitCount = 0; 247| 250| unsigned symbol = 0; 248| 250| unsigned const alphabetSize = maxSymbolValue + 1; 249| 250| int previousIs0 = 0; 250| | 251| | /* Table Size */ 252| 250| bitStream += (tableLog-FSE_MIN_TABLELOG) << bitCount; ------------------ | | 616| 250|#define FSE_MIN_TABLELOG 5 ------------------ 253| 250| bitCount += 4; 254| | 255| | /* Init */ 256| 250| remaining = tableSize+1; /* +1 for extra accuracy */ 257| 250| threshold = tableSize; 258| 250| nbBits = (int)tableLog+1; 259| | 260| 13.4k| while ((symbol < alphabetSize) && (remaining>1)) { /* stops at 1 */ ------------------ | Branch (260:12): [True: 13.2k, False: 250] | Branch (260:39): [True: 13.2k, False: 0] ------------------ 261| 13.2k| if (previousIs0) { ------------------ | Branch (261:13): [True: 1.12k, False: 12.0k] ------------------ 262| 1.12k| unsigned start = symbol; 263| 15.4k| while ((symbol < alphabetSize) && !normalizedCounter[symbol]) symbol++; ------------------ | Branch (263:20): [True: 15.4k, False: 0] | Branch (263:47): [True: 14.3k, False: 1.12k] ------------------ 264| 1.12k| if (symbol == alphabetSize) break; /* incorrect distribution */ ------------------ | Branch (264:17): [True: 0, False: 1.12k] ------------------ 265| 1.62k| while (symbol >= start+24) { ------------------ | Branch (265:20): [True: 507, False: 1.12k] ------------------ 266| 507| start+=24; 267| 507| bitStream += 0xFFFFU << bitCount; 268| 507| if ((!writeIsSafe) && (out > oend-2)) ------------------ | Branch (268:21): [True: 0, False: 507] | Branch (268:39): [True: 0, False: 0] ------------------ 269| 0| return ERROR(dstSize_tooSmall); /* Buffer overflow */ ------------------ | | 49| 0|#define ERROR(name) ZSTD_ERROR(name) | | ------------------ | | | | 50| 0|#define ZSTD_ERROR(name) ((size_t)-PREFIX(name)) | | | | ------------------ | | | | | | 42| 0|#define PREFIX(name) ZSTD_error_##name | | | | ------------------ | | ------------------ ------------------ 270| 507| out[0] = (BYTE) bitStream; 271| 507| out[1] = (BYTE)(bitStream>>8); 272| 507| out+=2; 273| 507| bitStream>>=16; 274| 507| } 275| 1.79k| while (symbol >= start+3) { ------------------ | Branch (275:20): [True: 675, False: 1.12k] ------------------ 276| 675| start+=3; 277| 675| bitStream += 3U << bitCount; 278| 675| bitCount += 2; 279| 675| } 280| 1.12k| bitStream += (symbol-start) << bitCount; 281| 1.12k| bitCount += 2; 282| 1.12k| if (bitCount>16) { ------------------ | Branch (282:17): [True: 263, False: 859] ------------------ 283| 263| if ((!writeIsSafe) && (out > oend - 2)) ------------------ | Branch (283:21): [True: 0, False: 263] | Branch (283:39): [True: 0, False: 0] ------------------ 284| 0| return ERROR(dstSize_tooSmall); /* Buffer overflow */ ------------------ | | 49| 0|#define ERROR(name) ZSTD_ERROR(name) | | ------------------ | | | | 50| 0|#define ZSTD_ERROR(name) ((size_t)-PREFIX(name)) | | | | ------------------ | | | | | | 42| 0|#define PREFIX(name) ZSTD_error_##name | | | | ------------------ | | ------------------ ------------------ 285| 263| out[0] = (BYTE)bitStream; 286| 263| out[1] = (BYTE)(bitStream>>8); 287| 263| out += 2; 288| 263| bitStream >>= 16; 289| 263| bitCount -= 16; 290| 263| } } 291| 13.2k| { int count = normalizedCounter[symbol++]; 292| 13.2k| int const max = (2*threshold-1) - remaining; 293| 13.2k| remaining -= count < 0 ? -count : count; ------------------ | Branch (293:26): [True: 10.6k, False: 2.60k] ------------------ 294| 13.2k| count++; /* +1 for extra accuracy */ 295| 13.2k| if (count>=threshold) ------------------ | Branch (295:17): [True: 303, False: 12.8k] ------------------ 296| 303| count += max; /* [0..max[ [max..threshold[ (...) [threshold+max 2*threshold[ */ 297| 13.2k| bitStream += (U32)count << bitCount; 298| 13.2k| bitCount += nbBits; 299| 13.2k| bitCount -= (count>=1; } ------------------ | Branch (302:20): [True: 1.93k, False: 13.2k] ------------------ 303| 13.2k| } 304| 13.2k| if (bitCount>16) { ------------------ | Branch (304:13): [True: 5.13k, False: 8.06k] ------------------ 305| 5.13k| if ((!writeIsSafe) && (out > oend - 2)) ------------------ | Branch (305:17): [True: 0, False: 5.13k] | Branch (305:35): [True: 0, False: 0] ------------------ 306| 0| return ERROR(dstSize_tooSmall); /* Buffer overflow */ ------------------ | | 49| 0|#define ERROR(name) ZSTD_ERROR(name) | | ------------------ | | | | 50| 0|#define ZSTD_ERROR(name) ((size_t)-PREFIX(name)) | | | | ------------------ | | | | | | 42| 0|#define PREFIX(name) ZSTD_error_##name | | | | ------------------ | | ------------------ ------------------ 307| 5.13k| out[0] = (BYTE)bitStream; 308| 5.13k| out[1] = (BYTE)(bitStream>>8); 309| 5.13k| out += 2; 310| 5.13k| bitStream >>= 16; 311| 5.13k| bitCount -= 16; 312| 5.13k| } } 313| | 314| 250| if (remaining != 1) ------------------ | Branch (314:9): [True: 0, False: 250] ------------------ 315| 0| return ERROR(GENERIC); /* incorrect normalized distribution */ ------------------ | | 49| 0|#define ERROR(name) ZSTD_ERROR(name) | | ------------------ | | | | 50| 0|#define ZSTD_ERROR(name) ((size_t)-PREFIX(name)) | | | | ------------------ | | | | | | 42| 0|#define PREFIX(name) ZSTD_error_##name | | | | ------------------ | | ------------------ ------------------ 316| 250| assert(symbol <= alphabetSize); ------------------ | Branch (316:5): [True: 0, False: 250] | Branch (316:5): [True: 250, False: 0] ------------------ 317| | 318| | /* flush remaining bitStream */ 319| 250| if ((!writeIsSafe) && (out > oend - 2)) ------------------ | Branch (319:9): [True: 0, False: 250] | Branch (319:27): [True: 0, False: 0] ------------------ 320| 0| return ERROR(dstSize_tooSmall); /* Buffer overflow */ ------------------ | | 49| 0|#define ERROR(name) ZSTD_ERROR(name) | | ------------------ | | | | 50| 0|#define ZSTD_ERROR(name) ((size_t)-PREFIX(name)) | | | | ------------------ | | | | | | 42| 0|#define PREFIX(name) ZSTD_error_##name | | | | ------------------ | | ------------------ ------------------ 321| 250| out[0] = (BYTE)bitStream; 322| 250| out[1] = (BYTE)(bitStream>>8); 323| 250| out+= (bitCount+7) /8; 324| | 325| 250| assert(out >= ostart); ------------------ | Branch (325:5): [True: 0, False: 250] | Branch (325:5): [True: 250, False: 0] ------------------ 326| 250| return (size_t)(out-ostart); 327| 250|} LLVMFuzzerTestOneInput: 29| 250|{ 30| 250| FUZZ_dataProducer_t *producer = FUZZ_dataProducer_create(src, size); 31| | 32| | /* Pick a random tableLog and maxSymbolValue */ 33| 250| unsigned const tableLog = FUZZ_dataProducer_uint32Range(producer, FSE_MIN_TABLELOG, FSE_MAX_TABLELOG); ------------------ | | 616| 250|#define FSE_MIN_TABLELOG 5 ------------------ unsigned const tableLog = FUZZ_dataProducer_uint32Range(producer, FSE_MIN_TABLELOG, FSE_MAX_TABLELOG); ------------------ | | 612| 250|#define FSE_MAX_TABLELOG (FSE_MAX_MEMORY_USAGE-2) | | ------------------ | | | | 582| 250|# define FSE_MAX_MEMORY_USAGE 14 | | ------------------ ------------------ 34| 250| unsigned const maxSymbolValue = FUZZ_dataProducer_uint32Range(producer, 0, 255); 35| | 36| 250| unsigned remainingWeight = (1u << tableLog) - 1; 37| 250| size_t dataSize; 38| 250| BYTE data[512]; 39| 250| short ncount[256]; 40| | 41| | /* Randomly fill the normalized count */ 42| 250| memset(ncount, 0, sizeof(ncount)); 43| 250| { 44| 250| unsigned s; 45| 14.3k| for (s = 0; s < maxSymbolValue && remainingWeight > 0; ++s) { ------------------ | Branch (45:21): [True: 14.2k, False: 103] | Branch (45:43): [True: 14.1k, False: 147] ------------------ 46| 14.1k| short n = (short)FUZZ_dataProducer_int32Range(producer, -1, remainingWeight); 47| 14.1k| ncount[s] = n; 48| 14.1k| if (n < 0) { ------------------ | Branch (48:17): [True: 10.5k, False: 3.53k] ------------------ 49| 10.5k| remainingWeight -= 1; 50| 10.5k| } else { 51| 3.53k| assert((unsigned)n <= remainingWeight); ------------------ | Branch (51:17): [True: 0, False: 3.53k] | Branch (51:17): [True: 3.53k, False: 0] ------------------ 52| 3.53k| remainingWeight -= n; 53| 3.53k| } 54| 14.1k| } 55| | /* Ensure ncount[maxSymbolValue] != 0 and the sum is (1<= FSE_NCountWriteBound(maxSymbolValue, tableLog)); ------------------ | | 45| 250|#define FUZZ_ASSERT(cond) FUZZ_ASSERT_MSG((cond), ""); | | ------------------ | | | | 41| 250| ((cond) ? (void)0 \ | | | | ------------------ | | | | | Branch (41:4): [True: 250, False: 0] | | | | ------------------ | | | | 42| 250| : (fprintf(stderr, "%s: %u: Assertion: `%s' failed. %s\n", __FILE__, \ | | | | 43| 0| __LINE__, FUZZ_QUOTE(cond), (msg)), \ | | | | ------------------ | | | | | | 35| 0|#define FUZZ_QUOTE(str) FUZZ_QUOTE_IMPL(str) | | | | | | ------------------ | | | | | | | | 34| 0|#define FUZZ_QUOTE_IMPL(str) #str | | | | | | ------------------ | | | | ------------------ | | | | 44| 0| abort())) | | ------------------ ------------------ 64| 250| dataSize = FSE_writeNCount(data, sizeof(data), ncount, maxSymbolValue, tableLog); 65| 250| FUZZ_ZASSERT(dataSize); ------------------ | | 47| 250| FUZZ_ASSERT_MSG(!ZSTD_isError(code), ZSTD_getErrorName(code)) | | ------------------ | | | | 41| 250| ((cond) ? (void)0 \ | | | | ------------------ | | | | | Branch (41:4): [True: 250, False: 0] | | | | ------------------ | | | | 42| 250| : (fprintf(stderr, "%s: %u: Assertion: `%s' failed. %s\n", __FILE__, \ | | | | 43| 0| __LINE__, FUZZ_QUOTE(cond), (msg)), \ | | | | ------------------ | | | | | | 35| 0|#define FUZZ_QUOTE(str) FUZZ_QUOTE_IMPL(str) | | | | | | ------------------ | | | | | | | | 34| 0|#define FUZZ_QUOTE_IMPL(str) #str | | | | | | ------------------ | | | | ------------------ | | | | 44| 0| abort())) | | ------------------ ------------------ 66| 250| } 67| | /* Read & validate the normalized count */ 68| 250| { 69| 250| short rtNcount[256]; 70| 250| unsigned rtMaxSymbolValue = 255; 71| 250| unsigned rtTableLog; 72| | /* Copy into a buffer with a random amount of random data at the end */ 73| 250| size_t const buffSize = (size_t)FUZZ_dataProducer_uint32Range(producer, dataSize, sizeof(data)); 74| 250| BYTE* const buff = FUZZ_malloc(buffSize); 75| 250| size_t rtDataSize; 76| 250| memcpy(buff, data, dataSize); 77| 250| { 78| 250| size_t b; 79| 10.6k| for (b = dataSize; b < buffSize; ++b) { ------------------ | Branch (79:32): [True: 10.3k, False: 250] ------------------ 80| 10.3k| buff[b] = (BYTE)FUZZ_dataProducer_uint32Range(producer, 0, 255); 81| 10.3k| } 82| 250| } 83| | 84| 250| rtDataSize = FSE_readNCount(rtNcount, &rtMaxSymbolValue, &rtTableLog, buff, buffSize); 85| 250| FUZZ_ZASSERT(rtDataSize); ------------------ | | 47| 250| FUZZ_ASSERT_MSG(!ZSTD_isError(code), ZSTD_getErrorName(code)) | | ------------------ | | | | 41| 250| ((cond) ? (void)0 \ | | | | ------------------ | | | | | Branch (41:4): [True: 250, False: 0] | | | | ------------------ | | | | 42| 250| : (fprintf(stderr, "%s: %u: Assertion: `%s' failed. %s\n", __FILE__, \ | | | | 43| 0| __LINE__, FUZZ_QUOTE(cond), (msg)), \ | | | | ------------------ | | | | | | 35| 0|#define FUZZ_QUOTE(str) FUZZ_QUOTE_IMPL(str) | | | | | | ------------------ | | | | | | | | 34| 0|#define FUZZ_QUOTE_IMPL(str) #str | | | | | | ------------------ | | | | ------------------ | | | | 44| 0| abort())) | | ------------------ ------------------ 86| 250| FUZZ_ASSERT(rtDataSize == dataSize); ------------------ | | 45| 250|#define FUZZ_ASSERT(cond) FUZZ_ASSERT_MSG((cond), ""); | | ------------------ | | | | 41| 250| ((cond) ? (void)0 \ | | | | ------------------ | | | | | Branch (41:4): [True: 250, False: 0] | | | | ------------------ | | | | 42| 250| : (fprintf(stderr, "%s: %u: Assertion: `%s' failed. %s\n", __FILE__, \ | | | | 43| 0| __LINE__, FUZZ_QUOTE(cond), (msg)), \ | | | | ------------------ | | | | | | 35| 0|#define FUZZ_QUOTE(str) FUZZ_QUOTE_IMPL(str) | | | | | | ------------------ | | | | | | | | 34| 0|#define FUZZ_QUOTE_IMPL(str) #str | | | | | | ------------------ | | | | ------------------ | | | | 44| 0| abort())) | | ------------------ ------------------ 87| 250| FUZZ_ASSERT(rtMaxSymbolValue == maxSymbolValue); ------------------ | | 45| 250|#define FUZZ_ASSERT(cond) FUZZ_ASSERT_MSG((cond), ""); | | ------------------ | | | | 41| 250| ((cond) ? (void)0 \ | | | | ------------------ | | | | | Branch (41:4): [True: 250, False: 0] | | | | ------------------ | | | | 42| 250| : (fprintf(stderr, "%s: %u: Assertion: `%s' failed. %s\n", __FILE__, \ | | | | 43| 0| __LINE__, FUZZ_QUOTE(cond), (msg)), \ | | | | ------------------ | | | | | | 35| 0|#define FUZZ_QUOTE(str) FUZZ_QUOTE_IMPL(str) | | | | | | ------------------ | | | | | | | | 34| 0|#define FUZZ_QUOTE_IMPL(str) #str | | | | | | ------------------ | | | | ------------------ | | | | 44| 0| abort())) | | ------------------ ------------------ 88| 250| FUZZ_ASSERT(rtTableLog == tableLog); ------------------ | | 45| 250|#define FUZZ_ASSERT(cond) FUZZ_ASSERT_MSG((cond), ""); | | ------------------ | | | | 41| 250| ((cond) ? (void)0 \ | | | | ------------------ | | | | | Branch (41:4): [True: 250, False: 0] | | | | ------------------ | | | | 42| 250| : (fprintf(stderr, "%s: %u: Assertion: `%s' failed. %s\n", __FILE__, \ | | | | 43| 0| __LINE__, FUZZ_QUOTE(cond), (msg)), \ | | | | ------------------ | | | | | | 35| 0|#define FUZZ_QUOTE(str) FUZZ_QUOTE_IMPL(str) | | | | | | ------------------ | | | | | | | | 34| 0|#define FUZZ_QUOTE_IMPL(str) #str | | | | | | ------------------ | | | | ------------------ | | | | 44| 0| abort())) | | ------------------ ------------------ 89| 250| { 90| 250| unsigned s; 91| 27.8k| for (s = 0; s <= maxSymbolValue; ++s) { ------------------ | Branch (91:25): [True: 27.5k, False: 250] ------------------ 92| 27.5k| FUZZ_ASSERT(ncount[s] == rtNcount[s]); ------------------ | | 45| 27.5k|#define FUZZ_ASSERT(cond) FUZZ_ASSERT_MSG((cond), ""); | | ------------------ | | | | 41| 27.5k| ((cond) ? (void)0 \ | | | | ------------------ | | | | | Branch (41:4): [True: 27.5k, False: 0] | | | | ------------------ | | | | 42| 27.5k| : (fprintf(stderr, "%s: %u: Assertion: `%s' failed. %s\n", __FILE__, \ | | | | 43| 0| __LINE__, FUZZ_QUOTE(cond), (msg)), \ | | | | ------------------ | | | | | | 35| 0|#define FUZZ_QUOTE(str) FUZZ_QUOTE_IMPL(str) | | | | | | ------------------ | | | | | | | | 34| 0|#define FUZZ_QUOTE_IMPL(str) #str | | | | | | ------------------ | | | | ------------------ | | | | 44| 0| abort())) | | ------------------ ------------------ 93| 27.5k| } 94| 250| } 95| 250| free(buff); 96| 250| } 97| | 98| 0| FUZZ_dataProducer_free(producer); 99| 250| return 0; 100| 250|} FUZZ_dataProducer_create: 19| 250|FUZZ_dataProducer_t *FUZZ_dataProducer_create(const uint8_t *data, size_t size) { 20| 250| FUZZ_dataProducer_t *producer = FUZZ_malloc(sizeof(FUZZ_dataProducer_t)); 21| | 22| 250| producer->data = data; 23| 250| producer->size = size; 24| 250| return producer; 25| 250|} FUZZ_dataProducer_free: 27| 250|void FUZZ_dataProducer_free(FUZZ_dataProducer_t *producer) { free(producer); } FUZZ_dataProducer_uint32Range: 30| 25.3k| uint32_t max) { 31| 25.3k| uint32_t range = max - min; 32| 25.3k| uint32_t rolling = range; 33| 25.3k| uint32_t result = 0; 34| | 35| 25.3k| FUZZ_ASSERT(min <= max); ------------------ | | 45| 25.3k|#define FUZZ_ASSERT(cond) FUZZ_ASSERT_MSG((cond), ""); | | ------------------ | | | | 41| 25.3k| ((cond) ? (void)0 \ | | | | ------------------ | | | | | Branch (41:4): [True: 25.3k, False: 0] | | | | ------------------ | | | | 42| 25.3k| : (fprintf(stderr, "%s: %u: Assertion: `%s' failed. %s\n", __FILE__, \ | | | | 43| 0| __LINE__, FUZZ_QUOTE(cond), (msg)), \ | | | | ------------------ | | | | | | 35| 0|#define FUZZ_QUOTE(str) FUZZ_QUOTE_IMPL(str) | | | | | | ------------------ | | | | | | | | 34| 0|#define FUZZ_QUOTE_IMPL(str) #str | | | | | | ------------------ | | | | ------------------ | | | | 44| 0| abort())) | | ------------------ ------------------ 36| | 37| 35.8k| while (rolling > 0 && producer->size > 0) { ------------------ | Branch (37:12): [True: 25.7k, False: 10.0k] | Branch (37:27): [True: 10.4k, False: 15.2k] ------------------ 38| 10.4k| uint8_t next = *(producer->data + producer->size - 1); 39| 10.4k| producer->size -= 1; 40| 10.4k| result = (result << 8) | next; 41| 10.4k| rolling >>= 8; 42| 10.4k| } 43| | 44| 25.3k| if (range == 0xffffffff) { ------------------ | Branch (44:9): [True: 0, False: 25.3k] ------------------ 45| 0| return result; 46| 0| } 47| | 48| 25.3k| return min + result % (range + 1); 49| 25.3k|} FUZZ_dataProducer_int32Range: 57| 14.1k|{ 58| 14.1k| FUZZ_ASSERT(min <= max); ------------------ | | 45| 14.1k|#define FUZZ_ASSERT(cond) FUZZ_ASSERT_MSG((cond), ""); | | ------------------ | | | | 41| 14.1k| ((cond) ? (void)0 \ | | | | ------------------ | | | | | Branch (41:4): [True: 14.1k, False: 0] | | | | ------------------ | | | | 42| 14.1k| : (fprintf(stderr, "%s: %u: Assertion: `%s' failed. %s\n", __FILE__, \ | | | | 43| 0| __LINE__, FUZZ_QUOTE(cond), (msg)), \ | | | | ------------------ | | | | | | 35| 0|#define FUZZ_QUOTE(str) FUZZ_QUOTE_IMPL(str) | | | | | | ------------------ | | | | | | | | 34| 0|#define FUZZ_QUOTE_IMPL(str) #str | | | | | | ------------------ | | | | ------------------ | | | | 44| 0| abort())) | | ------------------ ------------------ 59| | 60| 14.1k| if (min < 0) ------------------ | Branch (60:9): [True: 14.1k, False: 0] ------------------ 61| 14.1k| return (int)FUZZ_dataProducer_uint32Range(producer, 0, max - min) + min; 62| | 63| 0| return FUZZ_dataProducer_uint32Range(producer, min, max); 64| 14.1k|} FUZZ_malloc: 17| 500|{ 18| 500| if (size > 0) { ------------------ | Branch (18:9): [True: 500, False: 0] ------------------ 19| 500| void* const mem = malloc(size); 20| 500| FUZZ_ASSERT(mem); ------------------ | | 45| 500|#define FUZZ_ASSERT(cond) FUZZ_ASSERT_MSG((cond), ""); | | ------------------ | | | | 41| 500| ((cond) ? (void)0 \ | | | | ------------------ | | | | | Branch (41:4): [True: 500, False: 0] | | | | ------------------ | | | | 42| 500| : (fprintf(stderr, "%s: %u: Assertion: `%s' failed. %s\n", __FILE__, \ | | | | 43| 0| __LINE__, FUZZ_QUOTE(cond), (msg)), \ | | | | ------------------ | | | | | | 35| 0|#define FUZZ_QUOTE(str) FUZZ_QUOTE_IMPL(str) | | | | | | ------------------ | | | | | | | | 34| 0|#define FUZZ_QUOTE_IMPL(str) #str | | | | | | ------------------ | | | | ------------------ | | | | 44| 0| abort())) | | ------------------ ------------------ 21| 500| return mem; 22| 500| } 23| 0| return NULL; 24| 500|}