[edge case] Zstd performs badly on 200-symbol uniform data

[terrelln]

Data generated by this script:

import random
rd = random.Random()
rd.seed(0)
HIGH_ENTROPY = bytes(rd.randint(0, 200) for _ in range(10_000_000)) * 10
with open("med.bin", "wb") as f:
  f.write(HIGH_ENTROPY)

gzip -1: 100000000 -> 96526120
zstd -1: 100000000 -> 100002299

If I remove these heusistics:

zstd/lib/compress/huf_compress.c

Line 1297 in b7b7edb

if (largestTotal <= ((2 * SUSPECT_INCOMPRESSIBLE_SAMPLE_SIZE) >> 7)+4) return 0; /* heuristic : probably not compressible enough */

zstd/lib/compress/huf_compress.c

Line 1303 in b7b7edb

if (largest <= (srcSize >> 7)+4) return 0; /* heuristic : probably not compressible enough */

We get:

zstd -1: 100000000 -> 96449637

Zstd should do a better job with determining compressibility so we don't lose out on this case.

[yoniko]

I think we should be able to remove these heuristic and replace them with an actual Shannon entropy estimation.
As I already have a pretty precise and fast estimator, we can try it here.
I believe runtime shouldn't change much, given that we already calculate the histogram and its in cache.

[thatch]

aside: this is 201-symbol data; randint is inclusive of both params.