(de)Compressing Altera FPGA streams

[tv84]

Hi,

During the development of my parsing utility (posted in another post) I found out that there was very little information about the compression used in the Altera stream files. And, from time to time, someone interested shows up asking for any details.

So I decided to give it a try and, after some research, concluded that the compression method was based on "presence bits" algorithm as described in this Altera patent:

https://patentimages.storage.googleapis.com/e7/9f/62/c8f4d9e27c3fa0/US6525678.pdf

After much mental bit-banging  (it seemed within my reach but it eluded me for 2 weeks) I was sucessfull in understading how the compression works:

How decompression works (can be done in many ways but I find this the easier):

1 - Swap the nibbles in each byte (after this swap it becomes clear how to apply the patent method). Very important!!
2 - Swap the bit pairs in each "presence bits" nibble.
3 - Apply the method described in the patent (zones 5-6). It's very easy, I leave you that as homework. No RLE-compression involved!!!
4 - Do some nibble swapping in the substitution nibbles that follow the "presence bits" nibble, as needed.

And, that's it!

PS: Attached is a graphical image of the nibble grouping that has to be done in order to decompress (left - decompressed , right compressed). The correspondence is done with the colors. The file used was a random .RBF generated with and without compression.

With this example, anyone interested will be able to implement the method.

PS2: I inserted the "for dummies" table that resumes all of the above.

[marshallh]

Very neat info, seems cheap to implement in hardware

[tmbinc]

Hi,

thanks for the description! I was trying to decompress an EP3C25 bitstream. I found the description with "swapping nibbles" slightly confusing as in the end it's really just if it's "most significant nibble" or "least significant nibble" first (it's LSN). Also, depending on how the compressed bitstream is stored, it may be bit-reversed. (An .RBF file that I created compressed isn't reversed, but one that I dumped from flash apparently is).

Also there's a header block (that probably isn't fixed-size, but I was too lazy to figure out the details) that goes through uncompressed.

So, here's my implementation - i partially verified the result by producing a compressed and uncompressed image with quartus, and then checking that the images are identical (other than some bits in the header that likely indicate whether the bitstream is compressed; they would have to be reset).

Replace the usage of "nibbler" with "nibbler_bitrev" if your input file is bit-reversed. A good indication is the data at 0x20: It's either 56 EF (then it's reversed), or 6A F7 (then it's unreversed), but then again I don't know what the header means...

Next step (for me): extracting M9K contents.

Code: [Select]

import sys

data = open(sys.argv[1], "rb")

bitrev = [0b0000, 0b1000, 0b0100, 0b1100, 0b0010, 0b1010, 0b0110, 0b1110, 0b0001, 0b1001, 0b0101, 0b1101, 0b0011, 0b1011, 0b0111, 0b1111]
for i in range(16):
assert bitrev[bitrev[i]] == i

def nibbler_bitrev(data):
for i in range(len(data)):
yield bitrev[(data[i] >> 4) & 0xF]
yield bitrev[data[i] & 0xF]

def nibbler(data):
for i in range(len(data)):
yield data[i] & 0xF
yield (data[i] >> 4) & 0xF

n = nibbler(data)

def decompress(n):
while True:
presence = next(n)
for i in range(4):
if presence & 1:
yield next(n)
else:
yield 0
presence >>= 1

def denibble(n):
while True:
a = next(n)
a |= next(n) << 4
yield a

with open(sys.argv[2], "wb") as fo:
be = 0x1d3a # pass through header
fo.write(data[:be])
fo.write(bytes(denibble(decompress(nibbler(data[be:])))))


[AndyC_772]

(An .RBF file that I created compressed isn't reversed, but one that I dumped from flash apparently is).

I recall hearing from somewhere that's down to the Altera configuration flash chip (EPCS), which is very like a standard serial flash but uses different bit ordering.

[tv84]

(An .RBF file that I created compressed isn't reversed, but one that I dumped from flash apparently is).

I recall hearing from somewhere that's down to the Altera configuration flash chip (EPCS), which is very like a standard serial flash but uses different bit ordering.

Yes, I think when you have a EPCS the bitstream will be "produced" reversed to facilitate the programming, since it's done in a reverse way.

In the Siglent ADS thread I have some examples of (almost) full decoding of Altera's headers:

https://www.eevblog.com/forum/testgear/siglent-ads-firmware-file-format/msg1313901/#msg1313901

And in the parsing file of Siglent firmwares:

https://www.eevblog.com/forum/testgear/siglent-ads-firmware-file-format/msg1335892/#msg1335892

But decoding Altera's headers is far from being a finished quest.