[linux kernel patch] fixed possible 'rtbTable' underflow in FSE_normalizeCount()

[kdave]

There's a patch set to linux kernel for a possible underflow, there was no reaction so I'm posting it here for awareness. https://lore.kernel.org/all/20251211171950.852001-1-devsec@tpz.ru/

As we may need to sync the code it would be better to have it upstream first and then forward it to linux kernel. I can send a separate pull request with just this fix (to linux kernel) assuming that it will be also in the zstd upstream.

[terrelln]

Thanks for posting @kdave! We will take a look today

[felixhandte]

I've taken a first pass look and don't immediately see a path by which proba could end up negative. I can take another pass and try to prove that, but in parallel, it would be helpful if there were any context available for this patch. I.e., is there evidence that this has underflowed or can underflow? Is there a reproduction case?

I'll ask on the list I suppose.

[terrelln]

proba cannot be negative:

FSE_MAX_TABLELOG is 12

Based on line 473 we know that unsigned tableLog <= 12:

if (tableLog > FSE_MAX_TABLELOG) return ERROR(tableLog_tooLarge);   /* Unsupported size */

Based on line 478 we know that scale >= 50:

U64 const scale = 62 - tableLog;

Finally in line 474 we can determine the top >= 50 bits of proba are 0 before being converted to a short. So only the bottom 12 bits can be non-zero. Therefore proba is guaranteed to be non-negative:

                short proba = (short)((count[s]*step) >> scale);

So we can add an assert(proba >= 0); and add a comment explaining that. I will also respond on the mailing list.

[felixhandte]

We can also just make proba an unsigned short.