pxa: hash heap corruption

[anas-purpurata]

trafficstars

Hello Dan, i'm not sure if it makes sense to file an issue here because it's only example code, but I think I found a bug in the pxa compression routine:

When one of the lists in hash_list grows to more than 32768 entries, the code in https://github.com/dansanderson/lexaloffle/blob/main/pxa_compress_snippets.c#L406 tries to reallocate it with a size of 32768 * 2 == 65536, which doesn't fit into the uint16 used to store the allocation size. So the list is effectively reallocated with a size of zero; i.e. the heap_pos is increased by only 2 for the list header.

If any other lists are later reallocated, they will overwrite the affected list.

Here is a cartridge where this happens: https://www.lexaloffle.com/bbs/get_cart.php?cat=7&play_src=2&lid=nerfcooking_in_vegas-2

At input position 63072, the list for hash 3088 grows to more than 32768 entries. It is the reallocated to offset 157716 in the heap. The heap_pos is increased to 157718. Later, at input position 63433, the list for hash 3032 is reallocated to 157718, overwriting the start of the list for 3088.

I guess this doesn't affect the correctness of the compression, since pxa_find_repeatable_block will never choose one of the corrupted blocks. But it does affect the efficiency: an implementation without this problem compresses the code in above cartridge to 7971b instead of 14348b.

This issue also seems to be present in PICO-8 0.2.5c.

Have a nice day!

[dansanderson]

Thanks @anas-purpurata ! I'll forward this to zep. This is the actual C code from PICO-8, so it makes sense that the bug would be present in PICO-8 directly.

[lexaloffle]

Excellent find, @anas-purpurata -- I'll get this fixed for 0.2.5d and update the version here.