entropy_common.c:ZSTD_countTrailingZeros32: 29| 1.31k|{ 30| 1.31k| assert(val != 0); ------------------ | Branch (30:5): [True: 0, False: 1.31k] | Branch (30:5): [True: 1.31k, 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.31k| 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.31k|} entropy_common.c:ZSTD_highbit32: 175| 745|{ 176| 745| assert(val != 0); ------------------ | Branch (176:5): [True: 0, False: 745] | Branch (176:5): [True: 745, False: 0] ------------------ 177| 745| return 31 - ZSTD_countLeadingZeros32(val); 178| 745|} entropy_common.c:ZSTD_countLeadingZeros32: 70| 745|{ 71| 745| assert(val != 0); ------------------ | Branch (71:5): [True: 0, False: 745] | Branch (71:5): [True: 745, 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| 745| 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| 745|} FSE_isError: 32| 43|unsigned FSE_isError(size_t code) { return ERR_isError(code); } FSE_readNCount_bmi2: 212| 272|{ 213| 272| if (ZSTD_USE_BMI2(bmi2)) { ------------------ | | 36| 272|# define ZSTD_USE_BMI2(bmi2) (bmi2) | | ------------------ | | | Branch (36:31): [True: 0, False: 272] | | ------------------ ------------------ 214| 0| return FSE_readNCount_body_bmi2(normalizedCounter, maxSVPtr, tableLogPtr, headerBuffer, hbSize); 215| 0| } 216| 272| (void)bmi2; 217| 272| return FSE_readNCount_body_default(normalizedCounter, maxSVPtr, tableLogPtr, headerBuffer, hbSize); 218| 272|} FSE_readNCount: 223| 272|{ 224| 272| return FSE_readNCount_bmi2(normalizedCounter, maxSVPtr, tableLogPtr, headerBuffer, hbSize, /* bmi2 */ 0); 225| 272|} entropy_common.c:FSE_readNCount_body: 45| 272|{ 46| 272| const BYTE* const istart = (const BYTE*) headerBuffer; 47| 272| const BYTE* const iend = istart + hbSize; 48| 272| const BYTE* ip = istart; 49| 272| int nbBits; 50| 272| int remaining; 51| 272| int threshold; 52| 272| U32 bitStream; 53| 272| int bitCount; 54| 272| unsigned charnum = 0; 55| 272| unsigned const maxSV1 = *maxSVPtr + 1; 56| 272| int previous0 = 0; 57| | 58| 272| if (hbSize < 8) { ------------------ | Branch (58:9): [True: 43, False: 229] ------------------ 59| | /* This function only works when hbSize >= 8 */ 60| 43| char buffer[8] = {0}; 61| 43| ZSTD_memcpy(buffer, headerBuffer, hbSize); ------------------ | | 44| 43|# define ZSTD_memcpy(d,s,l) __builtin_memcpy((d),(s),(l)) ------------------ 62| 43| { size_t const countSize = FSE_readNCount(normalizedCounter, maxSVPtr, tableLogPtr, 63| 43| buffer, sizeof(buffer)); 64| 43| if (FSE_isError(countSize)) return countSize; ------------------ | Branch (64:17): [True: 0, False: 43] ------------------ 65| 43| 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 (65:17): [True: 0, False: 43] ------------------ 66| 43| return countSize; 67| 43| } } 68| 272| assert(hbSize >= 8); ------------------ | Branch (68:5): [True: 0, False: 229] | Branch (68:5): [True: 229, False: 0] ------------------ 69| | 70| | /* init */ 71| 229| ZSTD_memset(normalizedCounter, 0, (*maxSVPtr+1) * sizeof(normalizedCounter[0])); /* all symbols not present in NCount have a frequency of 0 */ ------------------ | | 46| 229|# define ZSTD_memset(p,v,l) __builtin_memset((p),(v),(l)) ------------------ 72| 229| bitStream = MEM_readLE32(ip); 73| 229| nbBits = (bitStream & 0xF) + FSE_MIN_TABLELOG; /* extract tableLog */ ------------------ | | 616| 229|#define FSE_MIN_TABLELOG 5 ------------------ 74| 229| if (nbBits > FSE_TABLELOG_ABSOLUTE_MAX) return ERROR(tableLog_tooLarge); ------------------ | | 618| 229|#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 (74:9): [True: 0, False: 229] ------------------ 75| 229| bitStream >>= 4; 76| 229| bitCount = 4; 77| 229| *tableLogPtr = nbBits; 78| 229| remaining = (1<> 1; 90| 1.31k| while (repeats >= 12) { ------------------ | Branch (90:20): [True: 276, False: 1.03k] ------------------ 91| 276| charnum += 3 * 12; 92| 276| if (LIKELY(ip <= iend-7)) { ------------------ | | 187| 276|#define LIKELY(x) (__builtin_expect((x), 1)) | | ------------------ | | | Branch (187:19): [True: 216, False: 60] | | ------------------ ------------------ 93| 216| ip += 3; 94| 216| } else { 95| 60| bitCount -= (int)(8 * (iend - 7 - ip)); 96| 60| bitCount &= 31; 97| 60| ip = iend - 4; 98| 60| } 99| 276| bitStream = MEM_readLE32(ip) >> bitCount; 100| 276| repeats = ZSTD_countTrailingZeros32(~bitStream | 0x80000000) >> 1; 101| 276| } 102| 1.03k| charnum += 3 * repeats; 103| 1.03k| bitStream >>= 2 * repeats; 104| 1.03k| bitCount += 2 * repeats; 105| | 106| | /* Add the final repeat which isn't 0b11. */ 107| 1.03k| assert((bitStream & 3) < 3); ------------------ | Branch (107:13): [True: 0, False: 1.03k] | Branch (107:13): [True: 1.03k, False: 0] ------------------ 108| 1.03k| charnum += bitStream & 3; 109| 1.03k| bitCount += 2; 110| | 111| | /* This is an error, but break and return an error 112| | * at the end, because returning out of a loop makes 113| | * it harder for the compiler to optimize. 114| | */ 115| 1.03k| if (charnum >= maxSV1) break; ------------------ | Branch (115:17): [True: 0, False: 1.03k] ------------------ 116| | 117| | /* We don't need to set the normalized count to 0 118| | * because we already memset the whole buffer to 0. 119| | */ 120| | 121| 1.03k| if (LIKELY(ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) { ------------------ | | 187| 2.06k|#define LIKELY(x) (__builtin_expect((x), 1)) | | ------------------ | | | Branch (187:19): [True: 874, False: 160] | | ------------------ ------------------ | Branch (121:41): [True: 39, False: 121] ------------------ 122| 913| assert((bitCount >> 3) <= 3); /* For first condition to work */ ------------------ | Branch (122:17): [True: 0, False: 913] | Branch (122:17): [True: 913, False: 0] ------------------ 123| 913| ip += bitCount>>3; 124| 913| bitCount &= 7; 125| 913| } else { 126| 121| bitCount -= (int)(8 * (iend - 4 - ip)); 127| 121| bitCount &= 31; 128| 121| ip = iend - 4; 129| 121| } 130| 1.03k| bitStream = MEM_readLE32(ip) >> bitCount; 131| 1.03k| } 132| 12.9k| { 133| 12.9k| int const max = (2*threshold-1) - remaining; 134| 12.9k| int count; 135| | 136| 12.9k| if ((bitStream & (threshold-1)) < (U32)max) { ------------------ | Branch (136:17): [True: 11.7k, False: 1.19k] ------------------ 137| 11.7k| count = bitStream & (threshold-1); 138| 11.7k| bitCount += nbBits-1; 139| 11.7k| } else { 140| 1.19k| count = bitStream & (2*threshold-1); 141| 1.19k| if (count >= threshold) count -= max; ------------------ | Branch (141:21): [True: 277, False: 919] ------------------ 142| 1.19k| bitCount += nbBits; 143| 1.19k| } 144| | 145| 12.9k| count--; /* extra accuracy */ 146| | /* When it matters (small blocks), this is a 147| | * predictable branch, because we don't use -1. 148| | */ 149| 12.9k| if (count >= 0) { ------------------ | Branch (149:17): [True: 2.39k, False: 10.5k] ------------------ 150| 2.39k| remaining -= count; 151| 10.5k| } else { 152| 10.5k| assert(count == -1); ------------------ | Branch (152:17): [True: 0, False: 10.5k] | Branch (152:17): [True: 10.5k, False: 0] ------------------ 153| 10.5k| remaining += count; 154| 10.5k| } 155| 12.9k| normalizedCounter[charnum++] = (short)count; 156| 12.9k| previous0 = !count; 157| | 158| 12.9k| assert(threshold > 1); ------------------ | Branch (158:13): [True: 0, False: 12.9k] | Branch (158:13): [True: 12.9k, False: 0] ------------------ 159| 12.9k| if (remaining < threshold) { ------------------ | Branch (159:17): [True: 974, False: 11.9k] ------------------ 160| | /* This branch can be folded into the 161| | * threshold update condition because we 162| | * know that threshold > 1. 163| | */ 164| 974| if (remaining <= 1) break; ------------------ | Branch (164:21): [True: 229, False: 745] ------------------ 165| 745| nbBits = ZSTD_highbit32(remaining) + 1; 166| 745| threshold = 1 << (nbBits - 1); 167| 745| } 168| 12.7k| if (charnum >= maxSV1) break; ------------------ | Branch (168:17): [True: 0, False: 12.7k] ------------------ 169| | 170| 12.7k| if (LIKELY(ip <= iend-7) || (ip + (bitCount>>3) <= iend-4)) { ------------------ | | 187| 25.4k|#define LIKELY(x) (__builtin_expect((x), 1)) | | ------------------ | | | Branch (187:19): [True: 12.0k, False: 649] | | ------------------ ------------------ | Branch (170:41): [True: 404, False: 245] ------------------ 171| 12.4k| ip += bitCount>>3; 172| 12.4k| bitCount &= 7; 173| 12.4k| } else { 174| 245| bitCount -= (int)(8 * (iend - 4 - ip)); 175| 245| bitCount &= 31; 176| 245| ip = iend - 4; 177| 245| } 178| 12.7k| bitStream = MEM_readLE32(ip) >> bitCount; 179| 12.7k| } } 180| 229| 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 (180:9): [True: 0, False: 229] ------------------ 181| | /* Only possible when there are too many zeros. */ 182| 229| 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 (182:9): [True: 0, False: 229] ------------------ 183| 229| 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 (183:9): [True: 0, False: 229] ------------------ 184| 229| *maxSVPtr = charnum-1; 185| | 186| 229| ip += (bitCount+7)>>3; 187| 229| return ip-istart; 188| 229|} entropy_common.c:FSE_readNCount_body_default: 194| 272|{ 195| 272| return FSE_readNCount_body(normalizedCounter, maxSVPtr, tableLogPtr, headerBuffer, hbSize); 196| 272|} entropy_common.c:ERR_isError: 52| 43|ERR_STATIC unsigned ERR_isError(size_t code) { return (code > ERROR(maxCode)); } ------------------ | | 49| 43|#define ERROR(name) ZSTD_ERROR(name) | | ------------------ | | | | 50| 43|#define ZSTD_ERROR(name) ((size_t)-PREFIX(name)) | | | | ------------------ | | | | | | 42| 43|#define PREFIX(name) ZSTD_error_##name | | | | ------------------ | | ------------------ ------------------ zstd_common.c:ERR_isError: 52| 458|ERR_STATIC unsigned ERR_isError(size_t code) { return (code > ERROR(maxCode)); } ------------------ | | 49| 458|#define ERROR(name) ZSTD_ERROR(name) | | ------------------ | | | | 50| 458|#define ZSTD_ERROR(name) ((size_t)-PREFIX(name)) | | | | ------------------ | | | | | | 42| 458|#define PREFIX(name) ZSTD_error_##name | | | | ------------------ | | ------------------ ------------------ entropy_common.c:MEM_readLE32: 322| 14.2k|{ 323| 14.2k| if (MEM_isLittleEndian()) ------------------ | Branch (323:9): [True: 14.2k, False: 0] ------------------ 324| 14.2k| return MEM_read32(memPtr); 325| 0| else 326| 0| return MEM_swap32(MEM_read32(memPtr)); 327| 14.2k|} entropy_common.c:MEM_isLittleEndian: 141| 14.2k|{ 142| 14.2k|#if defined(__BYTE_ORDER__) && defined(__ORDER_LITTLE_ENDIAN__) && (__BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__) 143| 14.2k| 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.2k|} entropy_common.c:MEM_read32: 202| 14.2k|{ 203| 14.2k| U32 val; ZSTD_memcpy(&val, memPtr, sizeof(val)); return val; ------------------ | | 44| 14.2k|# define ZSTD_memcpy(d,s,l) __builtin_memcpy((d),(s),(l)) ------------------ 204| 14.2k|} ZSTD_isError: 36| 458|unsigned ZSTD_isError(size_t code) { return ERR_isError(code); } FSE_NCountWriteBound: 224| 458|{ 225| 458| size_t const maxHeaderSize = (((maxSymbolValue+1) * tableLog 226| 458| + 4 /* bitCount initialized at 4 */ 227| 458| + 2 /* first two symbols may use one additional bit each */) / 8) 228| 458| + 1 /* round up to whole nb bytes */ 229| 458| + 2 /* additional two bytes for bitstream flush */; 230| 458| return maxSymbolValue ? maxHeaderSize : FSE_NCOUNTBOUND; /* maxSymbolValue==0 ? use default */ ------------------ | | 235| 78|#define FSE_NCOUNTBOUND 512 ------------------ | Branch (230:12): [True: 380, False: 78] ------------------ 231| 458|} FSE_writeNCount: 332| 229|{ 333| 229| if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge); /* Unsupported */ ------------------ | | 612| 229|#define FSE_MAX_TABLELOG (FSE_MAX_MEMORY_USAGE-2) | | ------------------ | | | | 582| 229|# 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: 229] ------------------ 334| 229| if (tableLog < FSE_MIN_TABLELOG) return ERROR(GENERIC); /* Unsupported */ ------------------ | | 616| 229|#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: 229] ------------------ 335| | 336| 229| if (bufferSize < FSE_NCountWriteBound(maxSymbolValue, tableLog)) ------------------ | Branch (336:9): [True: 0, False: 229] ------------------ 337| 0| return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 0); 338| | 339| 229| return FSE_writeNCount_generic(buffer, bufferSize, normalizedCounter, maxSymbolValue, tableLog, 1 /* write in buffer is safe */); 340| 229|} fse_compress.c:FSE_writeNCount_generic: 237| 229|{ 238| 229| BYTE* const ostart = (BYTE*) header; 239| 229| BYTE* out = ostart; 240| 229| BYTE* const oend = ostart + headerBufferSize; 241| 229| int nbBits; 242| 229| const int tableSize = 1 << tableLog; 243| 229| int remaining; 244| 229| int threshold; 245| 229| U32 bitStream = 0; 246| 229| int bitCount = 0; 247| 229| unsigned symbol = 0; 248| 229| unsigned const alphabetSize = maxSymbolValue + 1; 249| 229| int previousIs0 = 0; 250| | 251| | /* Table Size */ 252| 229| bitStream += (tableLog-FSE_MIN_TABLELOG) << bitCount; ------------------ | | 616| 229|#define FSE_MIN_TABLELOG 5 ------------------ 253| 229| bitCount += 4; 254| | 255| | /* Init */ 256| 229| remaining = tableSize+1; /* +1 for extra accuracy */ 257| 229| threshold = tableSize; 258| 229| nbBits = (int)tableLog+1; 259| | 260| 13.1k| while ((symbol < alphabetSize) && (remaining>1)) { /* stops at 1 */ ------------------ | Branch (260:12): [True: 12.9k, False: 229] | Branch (260:39): [True: 12.9k, False: 0] ------------------ 261| 12.9k| if (previousIs0) { ------------------ | Branch (261:13): [True: 1.03k, False: 11.9k] ------------------ 262| 1.03k| unsigned start = symbol; 263| 14.1k| while ((symbol < alphabetSize) && !normalizedCounter[symbol]) symbol++; ------------------ | Branch (263:20): [True: 14.1k, False: 0] | Branch (263:47): [True: 13.1k, False: 1.03k] ------------------ 264| 1.03k| if (symbol == alphabetSize) break; /* incorrect distribution */ ------------------ | Branch (264:17): [True: 0, False: 1.03k] ------------------ 265| 1.49k| while (symbol >= start+24) { ------------------ | Branch (265:20): [True: 460, False: 1.03k] ------------------ 266| 460| start+=24; 267| 460| bitStream += 0xFFFFU << bitCount; 268| 460| if ((!writeIsSafe) && (out > oend-2)) ------------------ | Branch (268:21): [True: 0, False: 460] | 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| 460| out[0] = (BYTE) bitStream; 271| 460| out[1] = (BYTE)(bitStream>>8); 272| 460| out+=2; 273| 460| bitStream>>=16; 274| 460| } 275| 1.69k| while (symbol >= start+3) { ------------------ | Branch (275:20): [True: 660, False: 1.03k] ------------------ 276| 660| start+=3; 277| 660| bitStream += 3U << bitCount; 278| 660| bitCount += 2; 279| 660| } 280| 1.03k| bitStream += (symbol-start) << bitCount; 281| 1.03k| bitCount += 2; 282| 1.03k| if (bitCount>16) { ------------------ | Branch (282:17): [True: 246, False: 788] ------------------ 283| 246| if ((!writeIsSafe) && (out > oend - 2)) ------------------ | Branch (283:21): [True: 0, False: 246] | 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| 246| out[0] = (BYTE)bitStream; 286| 246| out[1] = (BYTE)(bitStream>>8); 287| 246| out += 2; 288| 246| bitStream >>= 16; 289| 246| bitCount -= 16; 290| 246| } } 291| 12.9k| { int count = normalizedCounter[symbol++]; 292| 12.9k| int const max = (2*threshold-1) - remaining; 293| 12.9k| remaining -= count < 0 ? -count : count; ------------------ | Branch (293:26): [True: 10.5k, False: 2.39k] ------------------ 294| 12.9k| count++; /* +1 for extra accuracy */ 295| 12.9k| if (count>=threshold) ------------------ | Branch (295:17): [True: 277, False: 12.6k] ------------------ 296| 277| count += max; /* [0..max[ [max..threshold[ (...) [threshold+max 2*threshold[ */ 297| 12.9k| bitStream += (U32)count << bitCount; 298| 12.9k| bitCount += nbBits; 299| 12.9k| bitCount -= (count>=1; } ------------------ | Branch (302:20): [True: 1.82k, False: 12.9k] ------------------ 303| 12.9k| } 304| 12.9k| if (bitCount>16) { ------------------ | Branch (304:13): [True: 5.16k, False: 7.78k] ------------------ 305| 5.16k| if ((!writeIsSafe) && (out > oend - 2)) ------------------ | Branch (305:17): [True: 0, False: 5.16k] | 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.16k| out[0] = (BYTE)bitStream; 308| 5.16k| out[1] = (BYTE)(bitStream>>8); 309| 5.16k| out += 2; 310| 5.16k| bitStream >>= 16; 311| 5.16k| bitCount -= 16; 312| 5.16k| } } 313| | 314| 229| if (remaining != 1) ------------------ | Branch (314:9): [True: 0, False: 229] ------------------ 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| 229| assert(symbol <= alphabetSize); ------------------ | Branch (316:5): [True: 0, False: 229] | Branch (316:5): [True: 229, False: 0] ------------------ 317| | 318| | /* flush remaining bitStream */ 319| 229| if ((!writeIsSafe) && (out > oend - 2)) ------------------ | Branch (319:9): [True: 0, False: 229] | 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| 229| out[0] = (BYTE)bitStream; 322| 229| out[1] = (BYTE)(bitStream>>8); 323| 229| out+= (bitCount+7) /8; 324| | 325| 229| assert(out >= ostart); ------------------ | Branch (325:5): [True: 0, False: 229] | Branch (325:5): [True: 229, False: 0] ------------------ 326| 229| return (size_t)(out-ostart); 327| 229|} LLVMFuzzerTestOneInput: 29| 229|{ 30| 229| FUZZ_dataProducer_t *producer = FUZZ_dataProducer_create(src, size); 31| | 32| | /* Pick a random tableLog and maxSymbolValue */ 33| 229| unsigned const tableLog = FUZZ_dataProducer_uint32Range(producer, FSE_MIN_TABLELOG, FSE_MAX_TABLELOG); ------------------ | | 616| 229|#define FSE_MIN_TABLELOG 5 ------------------ unsigned const tableLog = FUZZ_dataProducer_uint32Range(producer, FSE_MIN_TABLELOG, FSE_MAX_TABLELOG); ------------------ | | 612| 229|#define FSE_MAX_TABLELOG (FSE_MAX_MEMORY_USAGE-2) | | ------------------ | | | | 582| 229|# define FSE_MAX_MEMORY_USAGE 14 | | ------------------ ------------------ 34| 229| unsigned const maxSymbolValue = FUZZ_dataProducer_uint32Range(producer, 0, 255); 35| | 36| 229| unsigned remainingWeight = (1u << tableLog) - 1; 37| 229| size_t dataSize; 38| 229| BYTE data[512]; 39| 229| short ncount[256]; 40| | 41| | /* Randomly fill the normalized count */ 42| 229| memset(ncount, 0, sizeof(ncount)); 43| 229| { 44| 229| unsigned s; 45| 14.4k| for (s = 0; s < maxSymbolValue && remainingWeight > 0; ++s) { ------------------ | Branch (45:21): [True: 14.3k, False: 94] | Branch (45:43): [True: 14.1k, False: 135] ------------------ 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.64k] ------------------ 49| 10.5k| remainingWeight -= 1; 50| 10.5k| } else { 51| 3.64k| assert((unsigned)n <= remainingWeight); ------------------ | Branch (51:17): [True: 0, False: 3.64k] | Branch (51:17): [True: 3.64k, False: 0] ------------------ 52| 3.64k| remainingWeight -= n; 53| 3.64k| } 54| 14.1k| } 55| | /* Ensure ncount[maxSymbolValue] != 0 and the sum is (1<= FSE_NCountWriteBound(maxSymbolValue, tableLog)); ------------------ | | 45| 229|#define FUZZ_ASSERT(cond) FUZZ_ASSERT_MSG((cond), ""); | | ------------------ | | | | 41| 229| ((cond) ? (void)0 \ | | | | ------------------ | | | | | Branch (41:4): [True: 229, False: 0] | | | | ------------------ | | | | 42| 229| : (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| 229| dataSize = FSE_writeNCount(data, sizeof(data), ncount, maxSymbolValue, tableLog); 65| 229| FUZZ_ZASSERT(dataSize); ------------------ | | 47| 229| FUZZ_ASSERT_MSG(!ZSTD_isError(code), ZSTD_getErrorName(code)) | | ------------------ | | | | 41| 229| ((cond) ? (void)0 \ | | | | ------------------ | | | | | Branch (41:4): [True: 229, False: 0] | | | | ------------------ | | | | 42| 229| : (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| 229| } 67| | /* Read & validate the normalized count */ 68| 229| { 69| 229| short rtNcount[256]; 70| 229| unsigned rtMaxSymbolValue = 255; 71| 229| unsigned rtTableLog; 72| | /* Copy into a buffer with a random amount of random data at the end */ 73| 229| size_t const buffSize = (size_t)FUZZ_dataProducer_uint32Range(producer, dataSize, sizeof(data)); 74| 229| BYTE* const buff = FUZZ_malloc(buffSize); 75| 229| size_t rtDataSize; 76| 229| memcpy(buff, data, dataSize); 77| 229| { 78| 229| size_t b; 79| 11.6k| for (b = dataSize; b < buffSize; ++b) { ------------------ | Branch (79:32): [True: 11.4k, False: 229] ------------------ 80| 11.4k| buff[b] = (BYTE)FUZZ_dataProducer_uint32Range(producer, 0, 255); 81| 11.4k| } 82| 229| } 83| | 84| 229| rtDataSize = FSE_readNCount(rtNcount, &rtMaxSymbolValue, &rtTableLog, buff, buffSize); 85| 229| FUZZ_ZASSERT(rtDataSize); ------------------ | | 47| 229| FUZZ_ASSERT_MSG(!ZSTD_isError(code), ZSTD_getErrorName(code)) | | ------------------ | | | | 41| 229| ((cond) ? (void)0 \ | | | | ------------------ | | | | | Branch (41:4): [True: 229, False: 0] | | | | ------------------ | | | | 42| 229| : (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| 229| FUZZ_ASSERT(rtDataSize == dataSize); ------------------ | | 45| 229|#define FUZZ_ASSERT(cond) FUZZ_ASSERT_MSG((cond), ""); | | ------------------ | | | | 41| 229| ((cond) ? (void)0 \ | | | | ------------------ | | | | | Branch (41:4): [True: 229, False: 0] | | | | ------------------ | | | | 42| 229| : (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| 229| FUZZ_ASSERT(rtMaxSymbolValue == maxSymbolValue); ------------------ | | 45| 229|#define FUZZ_ASSERT(cond) FUZZ_ASSERT_MSG((cond), ""); | | ------------------ | | | | 41| 229| ((cond) ? (void)0 \ | | | | ------------------ | | | | | Branch (41:4): [True: 229, False: 0] | | | | ------------------ | | | | 42| 229| : (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| 229| FUZZ_ASSERT(rtTableLog == tableLog); ------------------ | | 45| 229|#define FUZZ_ASSERT(cond) FUZZ_ASSERT_MSG((cond), ""); | | ------------------ | | | | 41| 229| ((cond) ? (void)0 \ | | | | ------------------ | | | | | Branch (41:4): [True: 229, False: 0] | | | | ------------------ | | | | 42| 229| : (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| 229| { 90| 229| unsigned s; 91| 26.3k| for (s = 0; s <= maxSymbolValue; ++s) { ------------------ | Branch (91:25): [True: 26.0k, False: 229] ------------------ 92| 26.0k| FUZZ_ASSERT(ncount[s] == rtNcount[s]); ------------------ | | 45| 26.0k|#define FUZZ_ASSERT(cond) FUZZ_ASSERT_MSG((cond), ""); | | ------------------ | | | | 41| 26.0k| ((cond) ? (void)0 \ | | | | ------------------ | | | | | Branch (41:4): [True: 26.0k, False: 0] | | | | ------------------ | | | | 42| 26.0k| : (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| 26.0k| } 94| 229| } 95| 229| free(buff); 96| 229| } 97| | 98| 0| FUZZ_dataProducer_free(producer); 99| 229| return 0; 100| 229|} FUZZ_dataProducer_create: 19| 229|FUZZ_dataProducer_t *FUZZ_dataProducer_create(const uint8_t *data, size_t size) { 20| 229| FUZZ_dataProducer_t *producer = FUZZ_malloc(sizeof(FUZZ_dataProducer_t)); 21| | 22| 229| producer->data = data; 23| 229| producer->size = size; 24| 229| return producer; 25| 229|} FUZZ_dataProducer_free: 27| 229|void FUZZ_dataProducer_free(FUZZ_dataProducer_t *producer) { free(producer); } FUZZ_dataProducer_uint32Range: 30| 26.4k| uint32_t max) { 31| 26.4k| uint32_t range = max - min; 32| 26.4k| uint32_t rolling = range; 33| 26.4k| uint32_t result = 0; 34| | 35| 26.4k| FUZZ_ASSERT(min <= max); ------------------ | | 45| 26.4k|#define FUZZ_ASSERT(cond) FUZZ_ASSERT_MSG((cond), ""); | | ------------------ | | | | 41| 26.4k| ((cond) ? (void)0 \ | | | | ------------------ | | | | | Branch (41:4): [True: 26.4k, False: 0] | | | | ------------------ | | | | 42| 26.4k| : (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| 38.1k| while (rolling > 0 && producer->size > 0) { ------------------ | Branch (37:12): [True: 27.1k, False: 10.9k] | Branch (37:27): [True: 11.6k, False: 15.4k] ------------------ 38| 11.6k| uint8_t next = *(producer->data + producer->size - 1); 39| 11.6k| producer->size -= 1; 40| 11.6k| result = (result << 8) | next; 41| 11.6k| rolling >>= 8; 42| 11.6k| } 43| | 44| 26.4k| if (range == 0xffffffff) { ------------------ | Branch (44:9): [True: 0, False: 26.4k] ------------------ 45| 0| return result; 46| 0| } 47| | 48| 26.4k| return min + result % (range + 1); 49| 26.4k|} 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| 458|{ 18| 458| if (size > 0) { ------------------ | Branch (18:9): [True: 458, False: 0] ------------------ 19| 458| void* const mem = malloc(size); 20| 458| FUZZ_ASSERT(mem); ------------------ | | 45| 458|#define FUZZ_ASSERT(cond) FUZZ_ASSERT_MSG((cond), ""); | | ------------------ | | | | 41| 458| ((cond) ? (void)0 \ | | | | ------------------ | | | | | Branch (41:4): [True: 458, False: 0] | | | | ------------------ | | | | 42| 458| : (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| 458| return mem; 22| 458| } 23| 0| return NULL; 24| 458|}