Data compression for FPGA bitstream

0
votes

I'm looking for a good compression algorithm to use for decompressing data from a flash chip to load to an FPGA (a Xilinx Spartan6-LX9, on the Mojo development board). It must be fast to decompress and not require a lot of working memory to do so, as the CPU (an ATmega16U4) is clocked at 8 MHz and has only 2 KiB of RAM and 16 KiB of program flash, some of which is already in use. Compression speed is not particularly important, as compression will only be run once on a computer, and the compression algorithm need not work on arbitrary inputs.

Here is an example bitstream. The format is documented in the Spartan-6 FPGA Configuration manual (starting on page 92).

Generally, the patterns present in the data fall into a few categories, and I'm not sure which of these will be easiest to exploit given the constraints I'm working with:

  • The data is organized overall into a set of packets of a known format. Certain parts of the bitstream are somewhat "stereotyped" (e.g, it will always begin and end by writing to certain registers), and other commands will appear in predictable sequences.

  • Some bytes are much more common than others. 00 and FF are by far the most frequent, but other bytes with few bits set (e.g, 80, 44, 02) are also quite common.

  • Runs of 00 and FF bytes are very frequent. Other patterns will sometimes appear on a local scale (e.g, a 16-byte sequence will be repeated a few times), but not globally.

What would be an appropriate compression algorithm (not a library, unless you're sure it'll fit!) for this task, given the constraints?

3
embeddedcompressionfpgalossless-compression
do you need to code a compression algorithm, or a decompression algorithm, on your target system ? (or both ?) - Cyan
Decompression only on the target. Compression can be handled on the computer that's generating the bitstream. - user149341
OK, in this case, initial recommendation by Mark seems applicable, since the LZ4 decoding algorithm requires almost no RAM (only a few variables). And its coding size is typically ~150 bytes or less. The compression part will have to produce small blocks, small enough to stay within the limit of your target system. - Cyan
@Cyan: LZ4 decompression appears to require that you be able to look behind up to 64KB in the decompressed data. That's a lot of memory that I don't have to work with! - user149341
no, it doesn't require it. It just "can" do it, but it doesn't need to. If your data is cut into small independent blocks, it will just use that. - Cyan

3 Answers

2
votes

You should consider using LZO compression library. It has probably one of the fastest decompressors in existence, and decompression requires no memory. Compression, however, needs 64KB of memory (or 8KB for one of compression levels). If you only need to decompress, it might just work for you.

LZO project even provides special cut-down version of this library called miniLZO. According to the author, miniLZO compiles to less than 5KB binary on i386. Since you have 16KB flash, it might just fit into your constraints.

LZO compressor is currently used by UPX (ultimate packer for executables).

2
votes

From your description, I would recommend run-length encoding followed by Huffman coding the bytes and runs. You would need very little memory over the data itself, mainly for accumulating frequencies and building a Huffman tree in place. Less than 1K.

You should make a histogram of the lengths of the runs to help determine how many bits to allocate to the run lengths.

2
votes

Have you tried the built-in bitstream compression? That can work really well on non-full devices. It's a bitgen option, and the FPGA supports it out of the box, so it has no resource impact on your micro.

The way the compression is achieved is described here:

http://www.xilinx.com/support/answers/16996.html

Other possibilities have been discussed on comp.arch.fpga:

https://groups.google.com/forum/?fromgroups#!topic/comp.arch.fpga/7UWTrS307wc

It appears that one poster implemented LZMA successfully on a relatively constrained embedded system. You could use 7zip to check what sort of compression ratio you might expect and see if it's good enough before committing to implementation of the embedded part.