Commit Graph

11 Commits

Author SHA1 Message Date
Damien George 6ba57f760c lib/uzlib: For matches of the same length, take the closest one.
Signed-off-by: Damien George <damien@micropython.org>
2023-11-30 12:13:29 +11:00
Jim Mussared 32db4c58f7 extmod/moddeflate: Change default window size.
The primary purpose of this commit is to make decompress default to
wbits=15 when the format is gzip (or auto format with gzip detected). The
idea is that someone decompressing a gzip stream should be able to use the
default `deflate.DeflateIO(f)` and it will "just work" for any input
stream, even though it uses a lot of memory.

This is done by making uzlib report gzip files as having wbits set to 15
in their header (where it previously only set the wbits out parameter for
zlib files), and then fixing up the logic in `deflateio_init_read`.

Updates the documentation to match.

This work was funded through GitHub Sponsors.

Signed-off-by: Jim Mussared <jim.mussared@gmail.com>
2023-09-01 12:23:37 +10:00
Jim Mussared e6c290c3d1 lib/uzlib: Add a source_read_data var to pass to source_read_cb.
For better abstraction for users of this API.

Signed-off-by: Jim Mussared <jim.mussared@gmail.com>
2023-07-21 19:29:34 +10:00
Jim Mussared 7f16bfca9f lib/uzlib/defl_static: Optimize zlib_start/finish_block.
Collapsing the two adjacent calls to outbits saves 32 bytes.

Bringing defl_static.c into lz77.c allows better inlining, saves 24 bytes.

Merge the Outbuf/uzlib_lz77_state_t structs, a minor simplification that
doesn't change code size.

This work was funded through GitHub Sponsors.

Signed-off-by: Jim Mussared <jim.mussared@gmail.com>
2023-07-21 19:29:34 +10:00
Jim Mussared ef5061fefd lib/uzlib/tinflate: Implement more compact lookup tables.
Saves 68 bytes on PYBV11.

This work was funded through GitHub Sponsors.

Signed-off-by: Jim Mussared <jim.mussared@gmail.com>
2023-07-21 19:29:34 +10:00
Jim Mussared d75a3cd861 lib/uzlib: Combine zlib/gzip header parsing to allow auto-detect.
This supports `wbits` values between +40 to +47.

This work was funded through GitHub Sponsors.

Signed-off-by: Jim Mussared <jim.mussared@gmail.com>
2023-07-21 19:29:34 +10:00
Jim Mussared c2b8e6e5d6 lib/uzlib: Clean up tinf -> uzlib rename.
This library used a mix of "tinf" and "uzlib" to refer to itself.  Remove
all use of "tinf" in the public API.

This work was funded through GitHub Sponsors.

Signed-off-by: Jim Mussared <jim.mussared@gmail.com>
2023-07-21 19:29:24 +10:00
Jim Mussared 0900976384 lib/uzlib/defl_static: Implement some code size improvements.
This commit makes the following changes:
- Replace 256-byte reverse-bits-in-byte lookup table with computation.
- Replace length and distance code lookup tables with computation.
- Remove comp_disabled check (it's unused).
- Make the dest_write_cb take the data pointer directly, rather than the
  Outbuf.

Saves 500 bytes on PYBV11.

Signed-off-by: Jim Mussared <jim.mussared@gmail.com>
2023-07-21 18:58:33 +10:00
Jim Mussared 82db9926ed lib/uzlib/lz77: Always use separate history buffer.
Because we only use the streaming source, this is just extra code size.

Saves 64 bytes on PYBV11.

Signed-off-by: Jim Mussared <jim.mussared@gmail.com>
2023-07-21 18:57:49 +10:00
Damien George c4feb806e0 lib/uzlib: Add memory-efficient, streaming LZ77 compression support.
The compression algorithm implemented in this commit uses much less memory
compared to the standard way of implementing it using a hash table and
large look-back window.  In particular the algorithm here doesn't allocate
hash table to store indices into the history of the previously seen text.
Instead it simply does a brute-force-search of the history text to find a
match for the compressor.  This is slower (linear search vs hash table
lookup) but with a small enough history (eg 512 bytes) it's not that slow.
And a small history does not impact the compression too much.

To give some more concrete numbers comparing memory use between the
approaches:

- Standard approach: inplace compression, all text to compress must be in
  RAM (or at least memory addressable), and then an additional 16k bytes
  RAM of hash table pointers, pointing into the text

- The approach in this commit: streaming compression, only a limited amount
  of previous text must be in RAM (user selectable, defaults to 512 bytes).

To compress, say, 1k of data, the standard approach requires all that data
to be in RAM, plus an additional 16k of RAM for the hash table pointers.
With this commit, you only need the 1k of data in RAM.  Or if it's
streaming from a file (or elsewhere), you could get away with only 256
bytes of RAM for the sliding history and still get very decent compression.

In summary: because compression takes such a large amount of RAM (in the
standard algorithm) and it's not really suitable for microcontrollers, the
approach taken in this commit is to minimise RAM usage as much as possible,
and still have acceptable performance (speed and compression ratio).

Signed-off-by: Damien George <damien@micropython.org>
2023-07-21 18:54:22 +10:00
Damien George d1bfb271d7 lib/uzlib: Move uzlib code from extmod to lib.
It's third-party code, and not necessarily tied to extmod.

Signed-off-by: Damien George <damien@micropython.org>
2021-07-12 16:36:34 +10:00