Likely bug in get_bits at end of stream when count > 8

timburke commented 6 years ago

Introduction

I'm in the process of porting heatshrink to typescript for use with a mobile app that deals with heatshrink data from an embedded device. As I was porting and testing the get_bits function I noticed what appears to be an edge case bug.

The comment in get_bits indicates that if there are not enough bits in the input buffer to satisfy count it should suspend immediately and not consume any bits, however the check for this condition linked below appears to miss a case when count > 8 since it only performs the check if there are no more whole bytes left.

Example situation

input_buffer: [1, 2]
input_index: 1
input_size: 2
bit_index: 1
current_byte: 1
count: 10

In this situation the user is asking for 10 bits but there are only 9 bits remaining in the input buffer (8 from the last byte and one remaining in the current byte. As I understand the code it will consume current byte before suspending, which I suspect is incorrect.

Could you please clarify if this was the intended behavior or a latent bug? It appears it could only affect situations with a window size > 8 bits based on a preliminary reading of the usage of get_bits.

Link to Relevant Code

https://github.com/atomicobject/heatshrink/blob/master/heatshrink_decoder.c#L298

trollcop commented 6 years ago

Hey,

I think I'm hitting a similar issue - my consume buffer size is 0x100, compressed data size is 0x101, and in the loop after consuming 0x100 bytes the decoder just keeps spinning and decoding garbage - which I think is related to this "suspend without consuming" issue you talk about.

Did you ever figure out how to fix it?

timburke commented 6 years ago

@trollcop I never did resolve the code issue but I believe the bug only applies when you have a window size > 8 bits, which we needed to stay below anyway to minimize RAM usage so it didn't end up affecting us.

silentbicycle commented 6 years ago

I haven't had much spare time for heatshrink for a while, but I'm planning on cutting a release in the next week or two with several fixes integrated.

timburke commented 6 years ago

In case it's helpful, I fixed the get_bits implementation logic for count > 8 window size in our typescript port and the port was just a direct function by function translation, so the fix should map well back to C. The relevant code is here:

https://github.com/iotile/heatshrink-ts/blob/master/src/heatshrink-utils.ts#L39

silentbicycle commented 6 years ago

I've been investigating your issue today, but haven't been able to reproduce the failure yet. Thanks for the detailed bug report, and comparing against the typescript is helpful. I think I see the edge case you're talking about -- I just haven't been able to trigger it in a test yet.

@trollcop, when you say "my consume buffer size is 0x100, compressed data size is 0x101, and in the loop after consuming 0x100 bytes the decoder just keeps spinning and decoding garbage", what is the return value from heatshrink_decoder_poll?

trollcop commented 5 years ago

@silentbicycle

@trollcop, when you say "my consume buffer size is 0x100, compressed data size is 0x101, and in the loop after consuming 0x100 bytes the decoder just keeps spinning and decoding garbage", what is the return value from heatshrink_decoder_poll?

Hey, no, I figured it out and it was my issue, not heatshrink. I've added heatshrink_decoder_sink_const() to be able to decode from flash buffer directly (embedded code, no need to copy into ram buffers), but the problem was as I was pushing HEATSHRINK_STATIC_INPUT_BUFFER_SIZE blocks into decoder, and compressed data wasn't aligned at 256 bytes, the final block would be longer and result in garbage decoding. Once I modified the input loop to end at compressed_data_size bytes to push, garbage decoding doesn't happen anymore. Sorry for a false alarm.

silentbicycle commented 5 years ago

Thanks for letting me know.

atomicobject / heatshrink