Integer division by zero in FSE_normalizeM2

[sh4k3n]

Hi, I get sometimes integer division by zero error from FSE_normalizeM2, when having large max symbol values. Specifically, I am using following compiler defines to compile FSE:

FSE_DEFAULT_MEMORY_USAGE=14 FSE_MAX_MEMORY_USAGE=16 FSEU16_DEFAULT_MEMORY_USAGE=14 FSEU16_MAX_MEMORY_USAGE=16 FSEU16_MAX_SYMBOL_VALUE=4095

Please find below example code that will reproduce the error.

#include "fse.h"

void test()
{
    uint16_t sourceBuffer[64] =
    {
        4048, 1072, 1532, 1936, 2252, 2460, 2536, 2480, 2292, 1988, 1596, 1140, 668, 200, 
        207, 535, 747, 839, 795, 615, 327, 64, 512, 988, 1456, 1868, 2208, 2432, 2532,
        2500, 2332, 2048, 1672, 1224, 748, 280, 139, 483, 723, 831, 811, 659, 383, 11,
        432, 904, 1376, 1800, 2152, 2404, 2524, 2516, 2372, 2104, 1744, 1304, 832, 364,
        71, 431, 687, 823, 827, 263
    };
    uint16_t destinationBuffer[64];
    static_assert(FSEU16_MAX_SYMBOL_VALUE == 4095, "Custom fseu16 max symbol value");
    FSE_compressU16(destinationBuffer, 64, sourceBuffer, 64, 4048, 13);
    /* -> Integer division by zero at fse_compress.c line 540 (FSE_normalizeM2) */
}

Thanks, Markus

[Cyan4973]

Thanks for the clear reproduction case @makush . I'll look into it.

[kozross]

Is this still an issue?

[Cyan4973]

Yes it's still an issue. Huge alphabet size is a fairly specific use case, I don't have any real-world situation where it applies. But it's nonetheless something to fix.

[kozross]

@Cyan4973 The main reason I ask is because I maintain awesome-c, and I would like to include your work, but this issue has me concerned.

[Cyan4973]

The issue still needs to be fixed. So I need to find some time to do it.

But I wouldn't be that concerned by it. I'm keeping the bug opened to not forget it, but really, you have to go through some uncommon scenario and invoke a rare interface labelled "experimental" which is not even present in fse.h, plus an additional set of conditions on distributions (which basically means FSE is not the right tool for the task) to have a chance to trigger it.

[kozross]

@Cyan4973 First off, thank you for the very prompt responses. Given what you've said, I am happy to include this very cool work in awesome-c, as it really seems that this issue is a corner case that people wouldn't encounter casually.

[JohanKnutzen]

FYI, I believe that this might be fixed in the zstd code with the addition of:

if (ToDistribute == 0) return 0 commit: https://github.com/facebook/zstd/commit/9889bca530a2b52615eb1cd06260e9cd0c29e001#diff-27457e92342bf0494cfc4a4ad6ba6bc9

I was able to repro this with another use case and I've fixed it with the addition of that if statement. Unfortunately I don't have my repro code anymore.

[Uzume]

@yohan1234 That code was pulled in here at ea7b3456bbbcc8533292f944251d284ddf0aabf3

Perhaps this is no longer an issue now.