FeLZ32

FeLz32 is a format intended to be relatively simple and to support high-speed encoding and decoding.

Table of Contents Speed Examples Format Header Payload

Speed Examples

Codec Speed Examples (4GHz AMD-FX 8350):

• Quake1 "id/pak0.pak" (~18 MB);
  • "FeLZ32 -1", encode= 390MB/s, decode= 2970MB/s (82% size)
  • "LZ4 -1" encode= 338MB/s, decode= 1312MB/s (67% size).
  • "FeLZ32 -3", encode= 146MB/s, decode= 2748MB/s (78% size)
  • "LZ4 -3" encode= 338MB/s, decode= 1312MB/s (67% size; no change).
  • MemCpy: 3034 MB/s
• Quake1 "quake_sh4.elf" (541kB);
  • "FeLZ32 -1", encode= 375MB/s, decode= 3419MB/s (74% size)
  • "LZ4 -1" encode= 318MB/s, decode= 1540MB/s (60% size).
  • "FeLZ32 -3", encode= 146MB/s, decode= 3110MB/s (70% size)
  • "LZ4 -3" encode= 320MB/s, decode= 1541MB/s (60% size; no change).
  • "FeLZ32 -9", encode= 34MB/s, decode= 2306MB/s (67% size)
  • "LZ4 -9" encode= 30MB/s, decode= 1679MB/s (54% size).
  • MemCpy: 9070 MB/s
• Tarball of random stuff (250MB)
  • "FeLZ32 -1", encode= 422MB/s, decode= 2626MB/s (63% size)
  • "LZ4 -1", encode= 453MB/s, decode= 1608MB/s (48% size)
  • "FeLZ32 -3", encode= 178MB/s, decode= 2472MB/s (59% size)
  • "LZ4 -3", encode= 457MB/s, decode= 1613MB/s (48% size)
  • "FeLZ32 -9", encode= 76MB/s, decode= 2415MB/s (54% size)
  • "LZ4 -9", encode= 26MB/s, decode= 1928MB/s (41% size)
  • MemCpy: 3400 MB/s

Format

A standalone FeLz32 file consists of a file header followed by a compressed payload.

Tool

• https://github.com/cr88192/bgbtech_misc/blob/master/mini/tst_felz0.c

Usage:

• tst_felz0 [options*] infile outfile
• -1 .. -9, Compression Level
• -d, Decode
  • Default is to encode.
• -t, Test compress input and run speed tests.

Header

Standalone File Header:

 	FOURCC magic0;	//'FeLZ'
 	TWOCC magic1;	//'32'
 	BYTE ver;		//1, format version
 	BYTE resv;		//0, reserved
 	DWORD csize;	//compressed size (includes header)
 	DWORD dsize;	//decompressed size

Payload

FELZ32: LZ in terms of 32-bit DWORDs

Structure consists of Tag DWORDs followed by runs of zero or more raw/literal DWORDs.

• During decoding:
  • Firstly, we read/decode the Tag DWORD.
  • Then the raw DWORDs are copied to output
  • Then the matched DWORDs are copied in from the sliding window.
  • Repeat until the end of the compressed data.
• A tag word of 0x00000000 indicates the end of the compressed data.
• The DWORDs for this compression format are stored in little-endian ordering.

Tag DWORD:

• Bits 0..15: md, Match Distance (1..65535 DWORDs)
• Bits 16..22: ml, Match Length (1..127 DWORDs)
• Bits 23..29: rl, Raw Length (0..127 DWORDs)
• Bits 30..31: al, Type or Align (0..3 BYTEs)

Cases:

• ml!=0:
  • md=distance
  • ml=length
  • mr=raw length
  • al=align (0=DWORD aligned, others: byte offset)
• ml==0, rl==0, al==0:
  • md==0: EOB
  • md!=0: Long run of raw DWORDs, md gives the raw length.
• Otherwise: Reserved

Distance is in terms of how many DWORDs back the match is relative to the current output position. The distance for a match may not be 0.

If al=0, we are simply copying DWORDs and need not bother with unaligned reads. An encoder may be told to only use aligned reads so as to avoid the overhead of dealing with non-aligned words on some targets.

Align is relative to this position, and indicates how many bytes forward the match is.

• Distance=1 byte : md=1, al=3
• Distance=2 bytes: md=1, al=2
• Distance=3 bytes: md=1, al=1
• Distance=4 bytes: md=1, al=0 (1 DWORD)
• Distance=5 bytes: md=2, al=3
• Distance=6 bytes: md=2, al=2
• Distance=7 bytes: md=2, al=1
• Distance=8 bytes: md=2, al=0 (2 DWORDs)