atomicobject / heatshrink

data compression library for embedded/real-time systems
ISC License
1.31k stars 176 forks source link

Usage simplified if heatshrink_encoder_poll() returns HSER_POLL_MORE when finish flag is set and output buffer is full #71

Open James-NZ opened 2 years ago

James-NZ commented 2 years ago

heatshrink_encoder_poll() is returning 'HSER_POLL_EMPTY' rather than 'HSER_POLL_MORE' when finishing and the output buffer is full. Is a break missing from the 'HSES_FLUSH_BITS' case? As implemented, it is dropping through to the 'HSES_DONE' case and returning 'HSER_POLL_EMPTY' rather than running through the 'HSER_POLL_MORE' check?

    case HSES_FLUSH_BITS:
        hse->state = st_flush_bit_buffer(hse, &oi);
    case HSES_DONE:
        return HSER_POLL_EMPTY;
    default:
        LOG("-- bad state %s\n", state_names[hse->state]);
        return HSER_POLL_ERROR_MISUSE;
    }

    if (hse->state == in_state) {
        /* Check if output buffer is exhausted. */
        if (*output_size == out_buf_size) return HSER_POLL_MORE;
    }

Logging without break:

heatshrink_encoder_poll()
(12:59:37.602) (>>) -- polling, state 1 (filled), flags 0x01<LF>
...
(13:00:37.174) (>>) -- polling, state 2 (search), flags 0x01<LF>
(13:00:37.174) (>>) ## step_search, scan @ +963 (1927/2048), input size 964<LF>
(13:00:37.199) (>>) -- scanning for match of buf[1987:1988] between buf[963:1987] (max 1 bytes)<LF>
(13:00:37.199) (>>) -- none found<LF>
(13:00:37.230) (>>) ss Match not found<LF>
(13:00:37.230) (>>) -- polling, state 3 (yield_tag_bit), flags 0x01<LF>
(13:00:37.230) (>>) -- adding tag bit: 1<LF>
(13:00:37.230) (>>) ++ push_bits: 1 bits, input of 0x01<LF>
(13:00:37.293) (>>) -- polling, state 4 (yield_literal), flags 0x01<LF>
(13:00:37.293) (>>) -- yielded literal byte 0x44 ('D') from +1987<LF>
(13:00:37.293) (>>) ++ push_bits: 8 bits, input of 0x44<LF>
(13:00:37.293) (>>)  > pushing byte 0x75<LF>
(13:00:37.293) (>>) -- polling, state 2 (search), flags 0x01<LF>
(13:00:37.293) (>>) ## step_search, scan @ +964 (1928/2048), input size 964<LF>
(13:00:37.323) (>>) -- end of search @ 964<LF>
(13:00:37.323) (>>) -- polling, state 8 (flush_bits), flags 0x01<LF>
returns HSER_POLL_EMPTY

I observe the desired behaviour with:

    case HSES_FLUSH_BITS:
        hse->state = st_flush_bit_buffer(hse, &oi);
        break;

Logging with break:

heatshrink_encoder_poll()
(13:15:58.567) (>>) -- polling, state 1 (filled), flags 0x01<LF>
...
(13:17:46.218) (>>) -- polling, state 2 (search), flags 0x01<LF>
(13:17:46.218) (>>) ## step_search, scan @ +963 (1927/2048), input size 964<LF>
(13:17:46.218) (>>) -- scanning for match of buf[1987:1988] between buf[963:1987] (max 1 bytes)<LF>
(13:17:46.227) (>>) -- none found<LF>
(13:17:46.227) (>>) ss Match not found<LF>
(13:17:46.227) (>>) -- polling, state 3 (yield_tag_bit), flags 0x01<LF>
(13:17:46.227) (>>) -- adding tag bit: 1<LF>
(13:17:46.258) (>>) ++ push_bits: 1 bits, input of 0x01<LF>
(13:17:46.258) (>>) -- polling, state 4 (yield_literal), flags 0x01<LF>
(13:17:46.258) (>>) -- yielded literal byte 0x44 ('D') from +1987<LF>
(13:17:46.289) (>>) ++ push_bits: 8 bits, input of 0x44<LF>
(13:17:46.289) (>>)  > pushing byte 0x75<LF>
(13:17:46.289) (>>) -- polling, state 2 (search), flags 0x01<LF>
(13:17:46.289) (>>) ## step_search, scan @ +964 (1928/2048), input size 964<LF>
(13:17:46.362) (>>) -- end of search @ 964<LF>
(13:17:46.362) (>>) -- polling, state 8 (flush_bits), flags 0x01<LF>
returns HSDR_POLL_MORE

heatshrink_encoder_poll()
(13:17:46.362) (>>) -- polling, state 8 (flush_bits), flags 0x01<LF>
(13:17:46.362) (>>) -- flushing remaining byte (bit_index == 0x02)<LF>
(13:17:46.382) (>>) -- done!<LF>
(13:17:46.382) (>>) -- polling, state 9 (done), flags 0x01<LF>
returns HSER_POLL_EMPTY

This behaviour is not seen in the example usage, since heatshrink_decoder_poll is also called until 'poll_sz == 0', rather than just until pres != HSDR_POLL_MORE.

If heatshrink_encoder_poll() is returns 'HSER_POLL_MORE' when finishing and the output buffer is full, the usage can be simplified by only needing to call heatshrink_decoder_finish() once to set the finish flag. If it returns 'HSDR_FINISH_MORE', keep calling heatshrink_encoder_poll() until it returns 'HSER_POLL_EMPTY' i.e. same as when sinking.

Pseudo code without error handling:

do
{
    if (input remaining)
    {
        heatshrink_encoder_sink()
        update input remaining
    }

    if (no input remaining)
    {
        fres = heatshrink_encoder_finish()
        if (fres == HSER_FINISH_DONE)
        {
            return
        }
    }

    do 
    {
        pres = heatshrink_encoder_poll()
        write output
    } while (pres == HSER_POLL_MORE);
} while (input remaining)

I believe the encoder example in the following pull request has an issue without changing the fall-through to a break in the 'HSES_FLUSH_BITS' case, as this is what I based my implementation on i.e. a single call to heatshrink_encoder_finish(): https://github.com/atomicobject/heatshrink/pull/54/commits

unixdj commented 2 years ago

In the develop branch there's no fallthrough but an explicit return HSER_POLL_EMPTY;, so the functionality is essentially the same.

It seems that you're right and HSER_POLL_MORE should be returned in this case.

Do you have the input and parameters (window size, backref length) with which you observe the bug?