Lost opportunity: batching incompressible literal runs with zero-length backrefs

[LordMike]

Summary

While benchmarking heatshrink for small embedded targets, I ran into what looks like a missed opportunity in the bitstream format: incompressible data has to be emitted as individual literals, so it trends toward about 112.5% of the original size.

A possible alternative would be to reuse an otherwise meaningless backref length code. A backref with decoded length 0 is not useful as a copy operation, so that code could instead mean "raw bytes follow". This would allow long literal spans to be batched without paying one tag bit per byte.

This is related to #17, which already discusses that some length-code space is effectively wasted and that improving it would require a breaking format change.

Background

Heatshrink is attractive for small streaming decoders because the decoder is simple, deterministic, and has bounded memory usage.

The awkward case is random, noisy, or already-compressed input. As I understand the current format, each literal is encoded as:

1 tag bit + 8 data bits

So if the encoder cannot find useful backrefs, the stream expands by about one bit per byte:

9 bits emitted per 8 bits input = 112.5%

Possible encoding

One possible format change would be to reserve the otherwise useless zero-length backref as a raw-run escape.

For example:

tag = 0
offset = raw_len - 1
length = 0
raw bytes follow

Interpreted as a normal backref, length = 0 does not make sense: copying zero bytes is a no-op, and spending bits to encode a no-op is not useful. That makes it a natural place to piggyback a control marker.

The offset field could then carry the raw-copy length instead:

raw_len = offset + 1

Conceptually:

current:
literal, literal, literal, literal, ...

possible raw-run form:
raw-run(length), byte, byte, byte, byte, ...

The encoder could still use normal literals for short spans where the raw-run header is not worth it.

What it solves

This mainly improves worst-case behavior.

In an experimental variant, long incompressible spans could be emitted as raw runs. That means noisy/random inputs that previously expanded to around 112% could get much closer to 100%.

It does not make heatshrink compete with zlib/DEFLATE on compression ratio. The benefit is more specific: it removes the constant one-bit-per-byte penalty in cases where the encoder already knows the data is not usefully compressible.

Experiment

We tested this while comparing small-memory compression options here:

https://github.com/LordMike/opendisplay-compression-benchmark

The experimental variant is called heatshrinkraw.

In the benchmark, the raw-run variant improved the bad random/noisy cases substantially. Regular heatshrink could expand incompressible inputs to around 112%, while the raw-run variant brought those cases down to roughly 100%.

The average ratio still remained worse than zlib, but the worst-case expansion became much less awkward.

Compatibility

This would be breaking.

Existing decoders would not treat length = 0 as a raw-run marker. So this would need to be a new stream version, explicit variant, or otherwise negotiated format option.

It also consumes one length code that could otherwise be used for a short backref if the format were changed in the direction discussed in #17. Whether that is worth it depends on the workload, but for the tested data the tradeoff was useful for reducing worst-case expansion.

Why I mention it

Heatshrink is otherwise very attractive for tiny streaming decoders. The literal encoding choice leaves avoidable worst-case expansion on the table, and a raw-run escape seems like it could address that while preserving most of the existing format model.

[silentbicycle]

This definitely seems worth exploring. It complicates the encoder and decoder state machine, but reduces the worst-case overhead enough to justify it. I expected systems using it would know enough about their data to decide whether it was worth using in the first place, but that would make it more general purpose.

Building on that idea, perhaps it could use a raw-run length with a bit count chosen to pad the current bit offset to an even byte boundary. Then it could use memcpy for the raw block, which would be faster than needing to shift every byte in the run and further reduce the worst-case overhead. (Maybe you're already doing that.)

It's been about a decade since I did nontrivial embedded development, and I haven't used heatshrink or been in the codebase for a long time. I may get back to it eventually, at which point I'll keep this in mind, but I can't promise it'll be any time soon. (For what it's worth, I've had a couple people offer to take over maintaining it and then ghost on me.)

[LordMike]

I had an agent describe Heatshrink to me, and as it did that, it realized this bit. I was battling with the horrendous worst case, and was deciding between heatshrink which hit 112% ratios for random data, and others which didn't. A quick fix like the suggested brought that down to 100% as it should be, and kept it in the running.

I finally opted for regular deflate, because of other reasons, but it was interesting nonetheless :)

[silentbicycle]

Sorry the agent wasted your time. Agents don't really understand anything.

If you can use deflate then it probably doesn't make sense to use heatshrink in the first place, it is designed for very low-memory embedded systems and kinds of data handled well by LZSS.

[LordMike]

I was on an embedded system, and deflate worked because of Esp32. But the project wanted to diverge into smaller MCU's where deflate with the default 32 KB window was way too much.. Heatshrink came up in this endeavour.

I ended up with deflate still because the legacy codebase must support it, but then expanded it to support windows down to 512 Bytes instead, although still with a state of about 1200 bytes. It shouuld work on the smallest MCUs when they come around. :)

[silentbicycle]

Gotcha, okay.

I'll keep it in mind when I get around to working on heatshrink again.