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