Code Comments
Programming Forum and web based access to our favorite programming groups.
Reverse-engineering an LZSS compression routine (on a Hitachi H8)[Xposted to comp.arch.embedded - hopefully there are a few H8 asm gurus
there who can help]
Hi,
I'm currently trying to reverse-engineer the LZSS decompression
engine used in the Cybiko PDA to compress firmware updates (and small
ASM and C programs) that are sent over a serial link. I've disassembled
the bootloader and found the decompress() routine (in Hitachi H8
assembler), but I haven't managed to work out what I need to do to write
a C program to decompress the images.
From the disassembly, I guessed that the code used is a variant of
Haruhiko Okumura's LZSS.C. I've also found the value of THRESHOLD, but I
don't know what the values of F and N (related to ring buffer sizing) are.
All I know about the output file is that it should be 1288 bytes in
size. Using { THRESHOLD=2, N=1024, F=18 } produces a file of that size,
but my disassembler reports that the decompressed data is not valid code.
Here's the disassembly:
> ROM:0000388A ; ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦ S U B R O U T I N E ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
> ROM:0000388A
> ROM:0000388A
> ROM:0000388A decompress: ; CODE XREF: sub_ABC+
12Ep
> ROM:0000388A
> ROM:0000388A var_10 = -0x10
> ROM:0000388A var_C = -0xC
> ROM:0000388A inputPointer = -8
> ROM:0000388A outputPointer = -4
> ROM:0000388A
> ROM:0000388A sub.l #0x10, sp ; ER0 = output poi
nter
> ROM:0000388A ; ER1 = input poin
ter
> ROM:0000388A ; ER2 = compressed
size
> ROM:00003890 stm.l er4-er6, @-sp
> ROM:00003894 mov.l er0, @(0x1C+outputPointer:16,sp) ; O
utput pointer -> ER0
> ROM:0000389A mov.l er1, @(0x1C+inputPointer:16,sp) ; In
put pointer -> ER1
> ROM:000038A0 mov.l er2, er4 ; Counter -> ER4
> ROM:000038A2 sub.l er5, er5 ; ER5 = 0
> ROM:000038A4 mov.l er5, @(0x1C+var_10:16,sp) ; var_10
= 0
> ROM:000038AA sub.w r6, r6 ; R6 = 0
> ROM:000038AC mov.l er0, @(0x1C+var_C:16,sp) ; Output p
ointer -> var_C
> ROM:000038B2
> ROM:000038B2 loc_38B2: ; CODE XREF: decom
press+86j
> ROM:000038B2 ; decompress+10Cj
> ROM:000038B2 shlr.w r6 ; Logical Shift Ri
ght on R6
> ROM:000038B4 btst #0, r6h ; Test R6high bit
0
> ROM:000038B6 bne loc_38D2:8 ; if (r6 & 256) th
en branch
> ROM:000038B8 mov.l er4, er2 ; ER2 = ER4 (count
er)
> ROM:000038BA subs #1, er4 ; ER4 = ER4 - 1 (c
ounter)
> ROM:000038BC beq decompress_done:16 ; If it's zero, w
e've decoded everything
> ROM:000038C0 mov.l @(0x1C+inputPointer:16,sp), er5 ; ER
5 = input pointer
> ROM:000038C6 mov.b @er5+, r6l ; R6low = @ER5 (in
c. ER5)
> ROM:000038C8 mov.b #0, r6h ; R6high = 0
> ROM:000038CA mov.l er5, @(0x1C+inputPointer:16,sp) ; Inp
ut pointer = ER5
> ROM:000038D0 or.b #0xFF, r6h ; R6 |= 0xFF00
> ROM:000038D2
> ROM:000038D2 loc_38D2: ; CODE XREF: decompre
ss+2Cj
> ROM:000038D2 mov.l er4, er3 ; ER3 = ER4 (counter)
> ROM:000038D4 subs #1, er3 ; Decrement counter
> ROM:000038D6 btst #0, r6l ; if (flags & 1)
> ROM:000038D8 beq loc_3912:8 ; then branch
> ROM:000038DA mov.l er4, er2
> ROM:000038DC mov.l er3, er4
> ROM:000038DE mov.l er2, er2
> ROM:000038E0 beq decompress_done:16
> ROM:000038E4 mov.l @(0x1C+inputPointer:16,sp), er5
> ROM:000038EA mov.b @er5+, r2l
> ROM:000038EC mov.l er5, @(0x1C+inputPointer:16,sp)
> ROM:000038F2 mov.l @(0x1C+var_C:16,sp), er5
> ROM:000038F8 mov.b r2l, @er5
> ROM:000038FA adds #1, er5
> ROM:000038FC mov.l er5, @(0x1C+var_C:16,sp)
> ROM:00003902 mov.l @(0x1C+var_10:16,sp), er5
> ROM:00003908 adds #1, er5
> ROM:0000390A mov.l er5, @(0x1C+var_10:16,sp)
> ROM:00003910 bra loc_38B2:8
> ROM:00003912 ; -----------------------------------------------------------
----------------
> ROM:00003912
> ROM:00003912 loc_3912: ; CODE XREF: decom
press+4Ej
> ROM:00003912 mov.l er4, er4 ; if (count == 0)
> ROM:00003914 beq decompress_done:16 ; then branch
> ROM:00003918 mov.l @(0x1C+inputPointer:16,sp), er5 ; R2
= next data byte (R2 = i)
> ROM:0000391E mov.b @er5+, r2l
> ROM:00003920 mov.b #0, r2h
> ROM:00003922 mov.l er5, @(0x1C+inputPointer:16,sp) ; Up
date pointer
> ROM:00003928 mov.w r2, r0 ; R0 = R2 = i
> ROM:0000392A extu.l er0 ; er0 &= 0x0000FFF
F
> ROM:0000392C mov.l er3, er4 ; ER4 = ER3
> ROM:0000392E subs #1, er4 ; ER4 = ER4 - 1 [counter]
> ROM:00003930 mov.l er3, er3 ; if (ER3 = 0) the
n decompress done
> ROM:00003932 beq decompress_done:8
> ROM:00003934 mov.b @er5+, r3l ; R3 = next data b
yte
> ROM:00003936 mov.b #0, r3h
> ROM:00003938 mov.l er5, @(0x1C+inputPointer:16,sp) ; Up
date pointer
> ROM:0000393E mov.l er3, er2 ; ER2 = ER3 = j
> ROM:00003940 shll.l #2, er2 ; ER2 = ((ER2 << 4
) & 0xF00)
> ROM:00003942 shll.l #2, er2
> ROM:00003944 and.l #0xF00, er2
> ROM:0000394A or.l er2, er0 ; ER0 |= ER2
> ROM:0000394A ; note: ER0 = i
> ROM:0000394E mov.l @(0x1C+var_10:16,sp), er1
> ROM:00003954 sub.l er0, er1
> ROM:00003956 and.b #0xF, r3l ; j = (j & 0x0F) +
THRESHOLD
> ROM:00003958 and.b #0, r3h
> ROM:0000395A adds #2, er3 ; *** THRESHOLD =
3
> ROM:0000395C adds #1, er3
> ROM:0000395E mov.l @(0x1C+var_10:16,sp), er0
> ROM:00003964 mov.l @(0x1C+outputPointer:16,sp), er5
> ROM:0000396A add.l er5, er0
> ROM:0000396C add.l er5, er1
> ROM:0000396E
> ROM:0000396E loc_396E: ; CODE XREF: decom
press+10Aj
> ROM:0000396E mov.b @er1+, r2l
> ROM:00003970 mov.b r2l, @er0
> ROM:00003972 adds #1, er0
> ROM:00003974 mov.l @(0x1C+var_C:16,sp), er5
> ROM:0000397A adds #1, er5
> ROM:0000397C mov.l er5, @(0x1C+var_C:16,sp)
> ROM:00003982 mov.l @(0x1C+var_10:16,sp), er5
> ROM:00003988 adds #1, er5
> ROM:0000398A mov.l er5, @(0x1C+var_10:16,sp)
> ROM:00003990 subs #1, er3
> ROM:00003992 mov.w r3, r3
> ROM:00003994 bne loc_396E:8
> ROM:00003996 bra loc_38B2:16
> ROM:0000399A ; -----------------------------------------------------------
----------------
> ROM:0000399A
> ROM:0000399A decompress_done: ; CODE XREF: decom
press+32j
> ROM:0000399A ; decompress+56j
..
> ROM:0000399A mov.l @(0x1C+var_10:16,sp), er0
> ROM:000039A0 ldm.l @sp+, er4-er6
> ROM:000039A4 add.l #0x10, sp
> ROM:000039AA rts
> ROM:000039AA ; End of function decompress
> ROM:000039AA
And a hex dump of the input data:
> 000 ff 12 34 ab cd 00 20 00 24 ff 54 2e 30 2e 30 31
> 010 00 4d ff 61 72 20 33 31 20 32 30 ff 30 30 00 31
> 020 35 3a 34 38 bf 3a 32 30 00 7a 00 22 00 4a ff 7a
> 030 03 00 ff f1 00 7a 01 ff 00 20 04 fa 1f 90 47 0a
> 040 ff 6c 0a 68 ba 0b 03 1f 90 f7 46 f6 5a 18 00 54
> 050 70 04 80 fb 7a 06 22 01 fd 00 6c ed fd 55 01 04
> 060 00 02 08 00 04 0c 00 08 10 00 55 10 14 00 20 18
> 070 00 40 1c 00 80 20 00 55 ff 24 00 fe 28 00 fd 2c
> 080 00 fb 30 00 55 f7 34 00 ef 38 00 df 3c 00 bf 40
> 090 00 df 7f 6c ed 6c 6d 78 02 00 0c df d2 68 82 52
> 0a0 12 02 01 68 02 ff 1c d2 58 60 01 c8 0b 70 ff 7a
> 0b0 20 00 28 00 00 46 e4 ff 6a 38 00 ff ff 61 71 30
> 0c0 ff 0c db 11 4b 11 4b eb 0f ff 8b 30 ab 39 4f 02
> 0d0 8b 07 fb 6a 2a 18 00 8c 4c f8 6a ab fa 20 00 8b
> 0e0 26 02 8c 72 70 0c db cc 22 0f 22 0b fb 0a 18 0f
> 0f0 3a 01 7a 26 de fc 01 58 60 ff 6a 72 03 70 30 ef
> 100 fa 20 6a aa 7c 00 8a fc 03 24 34 0f 4c 04 54 18
> 110 0f 64 02 45 18 0f 7c 02 91 53 18 0f 48 0f ac 08
> 120 20 18 0f c4 02 4f c4 18 0f dc 02 4b 18 0f f4 0f
> 130 2e 17 1a 0c c2 f0 00 3a 66 0f 7e 0f 18 0f 18 0f
> 140 7a 04 ff 00 1e 84 80 52 12 1b 74 ff 46 fa 1a 80
> 150 01 00 69 00 ab 59 00 4c 14 20 c6 13 72 54 16 0d
> 160 83 84 0c ce 10 d0 1f d0 1e 22 0f f2 1d cb cc 48
> 170 0f 26 0f 0c cb 22 0f 3a 2b 0d 04 00 92 0f 28 0f
> 180 92 0f 22 0f 92 0f 26 0f 92 0f 22 0f 64 68 1f e4
> 190 24 2b 60 0f 26 0f 0c 2b 22 0f 0c 16 2f 18 0f 72
> 1a0 70 f0 20 90 2f d8 2f d8 2f 90 18 0f 48 0f da 0f
> 1b0 92 09 4e 18 0f aa 02 47 b8 18 0f c2 0f d8 2d 40
> 1c0 fe 00 d6 41 08 0a fc 40 0f 00 50 1b
According to the header, this file should be 0x0508 bytes in size when
expanded.
I can upload a binary image of this data (and a copy of the full
disassembly) if it would help. Unfortunately I don't have any output
data - just the input to the compression algorithm and the length. The
first four bytes of the file should be 0x1234ABCD; I'm not sure about
the rest of the file.
Thanks.
Phil.
philpem@despammed.com (valid address)
http://www.philpem.me.uk/
Post Follow-up to this message
Re: Reverse-engineering an LZSS compression routine (on a Hitachi H8)Philip Pemberton wrote:
>
> I'm currently trying to reverse-engineer the LZSS decompression
> engine used in the Cybiko PDA to compress firmware updates (and
> small ASM and C programs) that are sent over a serial link. I've
> disassembled the bootloader and found the decompress() routine
> (in Hitachi H8 assembler), but I haven't managed to work out what
> I need to do to write a C program to decompress the images.
>
> From the disassembly, I guessed that the code used is a variant
> of Haruhiko Okumura's LZSS.C. I've also found the value of
> THRESHOLD, but I don't know what the values of F and N (related
> to ring buffer sizing) are.
>
> All I know about the output file is that it should be 1288 bytes
> in size. Using { THRESHOLD=2, N=1024, F=18 } produces a file of
> that size, but my disassembler reports that the decompressed
> data is not valid code.
I think you are attacking it in the wrong manner. Decompression
is much easier than compression, you don't have to worry about
forming trees of phrases and revising them, etc. I suggest you
start by getting "The Data Compression Book", by Mark Nelson and
Jean-Loup Gailly, M&T Books, ISBN 1-55851-434-1 (paperback, don't
know about hardback) and read up on the data format. Then the
first few bytes of the compressed code should give you clues about
where to go next. Your disassembly probably doesn't matter, the
data does.
This assumes the compressed data is not deliberately obscured, by
such things as encoding it with a pseudo random generator or
such. If so the disassembly comes back into play.
You are lucky it is not LZ78 or LZW compression, which requires
intimate knowledge of the compressor to decompress.
answered in c.a.e
--
Chuck F (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Post Follow-up to this message
Sponsored Links
Show a Printable Version
Email This Page to Someone!
Receive updates to this thread
Powered by vBulletin
Copyright 2000-2006 Jelsoft Enterprises Limited.
