I'm working on unpacking a camera firmware file which consists of various sections that I am able to correctly split and validate. One section within this file is additionally compressed with a form of LZSS as described here, of which I cannot determine the correct format of the lookup bytes.
The data starts with 2 uncompressed data blocks of 4096 bytes each (or a single 8192 byte block, however you want to see it), then follows the compressed data.
The compressed data starts with a flag byte, whose bits (starting at the LSB) tell which of the following bytes are to be copied (bit set), and which ones are lookup information (bit unset). Lookup information is made up of 2 bytes / 16 bits, and I am looking for help to decode their exact format.
I already know:
- the MSBs contain the
indexinto the lookup buffer
- the LSBs contain the
lengthof the lookup, i.e. the number of bytes to be copied from the lookup buffer at the given index
lengthis at least 3 bits
- the actual lookup length is
length + 3(because 3 is the minimum length for which a lookup makes sense, e.g. a bit-indicated length of 2 equals an actual lookup length of 5 bytes)
- The lookup length is either 3 or 4 bits (inside the data that I could manually decode, I did not find an occurrence of a length that requires 4 bits though)
- Since the lookup is either 3 or 4 bits, the index should be 13 or 12 bits. 12 bits make a lookup buffer size of 4096 byte, 13 bits a size of 8192, which corresponds to the uncompressed data block at the top and could be the init data of the buffer
Let's decompress an excerpt, starting at
00675CC0 65 0D 0A 0D FD 0A 33 C0 3C 68 74 6D 6C 3E FF 3C e...ý.3À<html>ÿ< 00675CD0 68 65 61 64 3E 3C 74 BF 69 74 6C 65 3E 34 40 C0 head><t¿itle>4@À 00675CE0 42 FF 61 64 20 52 65 71 75 65 6F 73 74 3C 2F 5F Bÿad Requeost</_ 00675CF0 C3 3C 2F 59 C3 6F 62 6F 64 79 57 C0 31 3E 69 CA Ã</YÃobodyWÀ1>iÊ 00675D00 FE 8A C0 3C 70 3E 59 6F 75 72 FF 20 62 72 6F 77 þŠÀ<p>Yourÿ brow
The decoding sequence:
00675CCE FF: read 8 bytes ("<head><t") 00675CD7 BF: read 6 bytes ("itle>4") lookup 40C0 -> read 3 bytes @ ? index ("00 ") read 1 byte ("B") 00675CE0 FF: read 8 bytes ("ad Reque") 00675CEA 6F: read 4 bytes ("st</") lookup 5FC3 -> read 6 bytes @ ? index ("title>") read 2 bytes ("</") lookup 59C3 -> read 6 bytes @ ? index ("head><") 00675CF5 6F: read 4 bytes ("body") ...
The decoded result:
00000000 3C 68 65 61 64 3E 3C 74 69 74 6C 65 3E 34 30 30 <head><title>400 00000010 20 42 61 64 20 52 65 71 75 65 73 74 3C 2F 74 69 Bad Request</ti 00000020 74 6C 65 3E 3C 2F 68 65 61 64 3E 3C 62 6F 64 79 tle></head><body
Now let's look at the last two lookups and their potential decodings:
0x5FC3 = 0101111111000011b 0101111111000 011 -> index 3064, length 6 (3 + 3 per above rule) 010111111100 0011 -> index 1532, length 6 0x59C3 = 0101100111000011b 0101100111000 011 -> index 2872, length 6 010110011100 0011 -> index 1436, length 6
I specifically chose this example because both lookups are only a few bytes back. In the decoded output/lookup-buffer,
0x5FC3 looks back 23 bytes and
0x59C3 looks back 38 bytes. The length is definitely correct, but the index numbers don't make sense to me. No matter which buffer size I assume, or if the index starts from the front or back of the buffer, or even differentiating endianness, the numbers don't fit. I'd assume that the lookup indices, due to only looking back a few bytes, should be on the lower or upper edge of the buffer. Also due to their vicinity in both compressed data and lookup data, their indices should be very close together.
So the question is either how can the lookup indices be correctly interpreted, or, assuming they are correct, how does the lookup buffer work because it can't be a standard circular buffer in such case. Any help would be greatly appreciated!
ps: In case anyone is interested, the firmware format in question is used by the YI M1 and Fujifilm X-A10 cameras. The current state of the firmware unpacker is available on GitHub.
Update: Further investigation has led me to this related RE question and the LZRW compression family where the lookup indices may also refer to some kind of lookup table instead of directly into the data.
Update 2: Found evidence that the lookup length takes at least 4 bits. Also figured out that the lookup bytes are stored in big endian order (seems like I made a mistake last time when I tried it).
0x5FC3 = 0101111111000011b 110001011111 0011 -> index 3167, length 6 (big endian) 0x59C3 = 0101100111000011b 110001011001 0011 -> index 3161, length 6 (big endian)
In the test cases I set up in the linked code repository, I noticed that many lookups are off by 709 byte, so I added an initial lookup buffer write offset of 709 and I'm now able to correctly decode large parts of the data, including the example above. Other parts seem to require another offset though, so this is still open to be figured out.
Update 3: By analyzing where the lookup offset changes, I noticed longer 0x00 byte sequences that obviously would not be there if that data would be compressed. Taking a closer look at them, it turned out they are paddings for a 2048 byte alignment, and that the compressed data section is again made up of several subsections. Once I split them up and decompressed them separately, the problem with the changing buffer lookup offset was solved. So in the end it seems that the LZSS algorithm works exactly as in the link that I already posted above. The mystery was not the compression itself but the file structure. There are still a few questions open regarding to that, and once I'm done I will post a more detailed answer.