Subversion Repositories hdl-deflate

# HDL-deflate
FPGA implementation of deflate (de)compress RFC 1950/1951

This design is implemented in MyHDL (www.myhdl.org) and can be translated to Verilog or VHDL.

It has been verified in Icarus, Xilinx Vivado and on a physical Xilinx device (Digilent Arty).

Usage should be clear from the test bench in `test_deflate.py`.

# Tunable parameters

    OBSIZE = 8192   # Size of output buffer (BRAM)
                    # You need 32768 to compress ALL valid deflate streams!

    IBSIZE = 2048   # Size of input buffer (LUT-RAM)

    CWINDOW = 32    # Search window for compression

## Compression efficiency

One can use a sliding window to reduce the size of the input buffer and the LUT-usage.

The minimal value is 2 * CWINDOW (64 bytes), the UnitTest in `test_deflate.py`
uses this strategy.

By default the compressor will reduce repeated 3/4/5 byte sequences in the search window to 15 bit.
This will result in a decent compression ratio for many real life input data patterns.

At the expense of additional LUTs one can improve this by enlarging the `CWINDOW` or expanding
the matching code to include 6/7/8/9/10 byte matches. Set `MATCH10` to `True` in the top of `deflate.py`
to activate this option.

Another strategy for data sets with just a small set of used byte values would be
to use a dedicated pre-computed Huffman tree. I could add this if there is interest, but it is probably
better to use a more dense coding in your FPGA application data in the first place.

## Compression speed

To reduce LUT usage the original implementation matched each slot in the search window in a dedicated clock cycle.
By setting `FAST` to `True` it will generate the logic to match the whole window in a single cycle.
The effective speed will be around 1 input byte every two cycles.

## Disabling functionality to save LUTs

The compress mode can be disabled by setting `COMPRESS` to `False`.

The decompress mode can be disabled by setting `DECOMPRESS` to `False`.

As an option you can disable dynamic tree decompression by setting `DYNAMIC` to `False`. 
This will save a lot of LUT-ram and HDL-Deflate compressed output is always using a static tree,
but zlib will normally generate dynamic trees. Set zlib option `Z_FIXED` to generate streams with
a static tree.

In general the size of `leaves` and `d_leaves` can be reduced a lot when the maximal length of the input stream
is less than 32768. One can replace `test_data()` in `test_deflate.py` with a specific version which generates
typical test data for the intended FPGA application, and repeatedly halve the sizes of the `leaves` arrays
until the test fails.

FAST MATCH10 compress only has quite good resource usage.

## Practical considerations

In general HDL-Deflate is interesting when speed is important. When speed is not a real issue using a (soft)
CPU with zlib is probably the better approach. Especially decompression is also quite fast with a CPU and HDL-Deflate
needs a lot of LUTs when configured to decompress ANY deflate input stream. Compression is another story because it
is a LOT faster in hardware with the `FAST` option and uses a reasonable amount of LUTs.

# FPGA validation

## Minimal with smaller leaves arrays

Resource|Estimation
--------|----------
LUT     |7116
LUTRAM  |800
FF      |2265
BRAM    |4

## Compress False and smaller leaves arrays

Resource|Estimation
--------|----------
LUT     |5769
LUTRAM  |512
FF      |2169
BRAM    |4

## Decompress False and FAST and MATCH10

Resource|Estimation
--------|----------
LUT     |5118
LUTRAM  |84
FF      |1577
BRAM    |2

## FAST

Resource|Estimation
--------|----------
LUT     |8246
LUTRAM  |704
FF      |2520
BRAM    |4

## FAST and MATCH10

Resource|Estimation
--------|----------
LUT     |11888
LUTRAM  |536
FF      |3308
BRAM    |4

## Speed

The Vivado timing report fails at 100Mhz, but the test bench runs fine on my Arty at 100Mhz.

# Future Improvements (when there is interest)

* ~~Reduce LUT usage~~
* ~~Improve speed from current 80Mhz to 100Mhz~~
* ~~Improve compression performance~~