4

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 index into the lookup buffer
  • the LSBs contain the length of the lookup, i.e. the number of bytes to be copied from the lookup buffer at the given index
  • the length is 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)

I suspect:

  • 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 00675CCE:

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.

  • 1
    It might be easier to just check what the decompression code is doing. Did you find it? – Igor Skochinsky Nov 2 '17 at 8:46
  • I assumed that code is also part of the compressed data since the other firmware sections only contain resources, the booloader and a partition table. It could be inside the first 8192 uncompressed bytes though, so thanks for the hint! I have not yet identified the architecture either... have you ever heard about "EV9x" ("/XC_ODM/sdk/SDK_selfcheck/src/EV9x_DevEnv")? – Mario Gu Nov 2 '17 at 15:46
  • Firmware contains "ARM926" strings, pointing at armv5te architecture. Could a relatively new camera that processes 4K H.264 videos be based on a 10 years old processor? – Mario Gu Nov 2 '17 at 16:14
  • 1
    ARM926 actually has special instructions for accelerating DSP-like code (that's the e in armv5te) but it's likely that most of the processing is done in dedicated hardware blocks and the CPU only handles the UI and task management. – Igor Skochinsky Nov 2 '17 at 17:07
1

As already described in the updates to my question, it turned out that the compression algorithm is the standard LZSS algorithm with a 12 bit lookup index and 4 bit lookup length. They were just stored in an unexpected way (flipped bytes).

Taking the example from the question:

0x5FC3 = 0 1 0 1 1 1 1 1 1 1 0 0 0 0 1 1 b
         <-------------> <-----> <----->
         7             0 11    8 3     0 (bit indices)
             index        index  length

Ordering the bits correctly yields the following:

lookup index  110001011111b = 3167
lookup length 0011b         = 3 (+ 3 [lookup threshold length] = 6) 

So the lookup is 6 bytes at buffer position 3167. The buffer position is absolute and always starts at the "physical" buffer index 0, it's not an offset to the circular buffer position.

The reason why I had observed weird and changing lookup index offsets was

  • the data contained multiple independent compressed sections, which once split, gave a constant buffer offset
  • I still have to apply a buffer offset to decompress correctly, that is probably because of some data header or init data that I have not determined yet, but that is out of scope of this question

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.