Page 1 of 2 12 LastLast
Results 1 to 30 of 41

Thread: LZ98

  1. #1
    Member
    Join Date
    Jul 2019
    Location
    USA
    Posts
    23
    Thanks
    8
    Thanked 1 Time in 1 Post

    LZ98

    Hi, I'm a new member and am trying to find some information about the LZ98 compression algorithm. I've had not a lot of luck searching google for it, I did find one spanish presentation that mentioned it.

    Wondering if any of the forum members have heard of this and looking for anything related to it.

    thanks!
    ~telengard

  2. #2
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,982
    Thanks
    298
    Thanked 1,309 Times in 745 Posts
    In that spanish presentation its probably a mistype of LZ78.
    More context information, please.

    "I found it being used in some firmware I'm reversing for a Roland sampler."?

  3. #3
    Member
    Join Date
    Jul 2019
    Location
    USA
    Posts
    23
    Thanks
    8
    Thanked 1 Time in 1 Post
    Quote Originally Posted by Shelwien View Post
    In that spanish presentation its probably a mistype of LZ78.
    More context information, please.

    "I found it being used in some firmware I'm reversing for a Roland sampler."?
    Thanks for responding!

    That makes sense that it is a typo, and that link is me.

    I'm reverse engineering an old, no longer made sampler. I've made great progress reversing the bootloader, etc but the main program is compressed and the string I see at the beginning of what seems to be the compressed binary starts w/ LZ98 which made me think of the other LZ algorithms.

    Here's a few screenshots for some context:

    This is the top portion of that binary as part of a larger binary blob which is stored in flash


    Click image for larger version. 

Name:	1.png 
Views:	119 
Size:	260.6 KB 
ID:	6681

    This is the routine which looks for that string before decompressing into RAM (a different routine, a bit longer)

    Click image for larger version. 

Name:	2.png 
Views:	98 
Size:	140.7 KB 
ID:	6682

  4. #4
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,982
    Thanks
    298
    Thanked 1,309 Times in 745 Posts
    https://static.roland.com/assets/med...V8800_V101.zip
    It seems to be a type of LZSS - flag bytes and no entropy coding.
    Flag bytes seem to work bit0 to bit7, 1=literal (uncompressed data byte), 0=match.
    Code:
    ROM:80021043                 .data.b h'FF
    ROM:80021044 aProgress:      .sdata "Progress"
    ROM:8002104C                 .data.b h'FF
    ROM:8002104D aCountsub:      .sdata "CountSub"
    ROM:80021055                 .data.b h'FF
    ROM:80021056 a118chmiw:      .data.b 0
    ROM:80021056                 .sdata "18CHMIW"
    ROM:8002105E                 .data.b h'FF
    ROM:8002105F aIntitlea:      .sdata "inTitleA"
    ROM:80021067                 .data.b h'9F            ; 10011111
    ROM:80021068 aPpend:         .sdata "ppend"
    ROM:8002106D                 .data.b h'20, h'A1
    ROM:8002106F aV:             .data.b h'56, h'AB
    ROM:80021071 aH:             .sdata "H"
    ROM:80021072                 .data.b h'5F ; _        ; 01011111
    ROM:80021073 aOlder:         .sdata "older"
    ROM:80021078 aJ_0:           .data.b h'6A, h'A2
    ROM:8002107A a4:             .sdata "4"
    ROM:8002107B aX_0:           .data.b h'58, h'A1
    ROM:8002107D                 .data.b h'FF
    ROM:8002107E aMarkedpa:      .sdata "MarkedPa"
    ROM:80021086                 .data.b h'EB            ; 11101011
    ROM:80021087 aNej:           .sdata "ne"
    ROM:80021089 aJ:             .data.b h'6A, h'A2      ; match
    ROM:8002108B a3:             .sdata "3"
    ROM:8002108C aX:             .data.b h'58, h'A1      ; match
    ROM:8002108E aAva:           .sdata "Ava"
    ROM:80021091                 .data.b h'FF
    ROM:80021092 aIlinfo:        .sdata "ilInfo"
    ROM:80021092                 .data.b 0, h'8D
    ROM:8002109A                 .data.b h'F7            ; 11110111
    ROM:8002109B                 .data.b h'B3, h'E5, h'20
    ROM:8002109E                 .data.b h'20, h'A0
    ROM:800210A0                 .data.b 1, h'8D, h'B4, 4
    Also it looks like there's a decoding routine called after the reference to "Extracting program..."

  5. Thanks:

    telengard (4th July 2019)

  6. #5
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,982
    Thanks
    298
    Thanked 1,309 Times in 745 Posts
    In other news, in may be possible to decompile code for this cpu, with ghidra.
    https://nuget.pkg.github.com/VGKints...turn-Processor
    My attempt wasn't very successful, but maybe there're better resources somewhere?
    Attached Thumbnails Attached Thumbnails Click image for larger version. 

Name:	roland1.png 
Views:	83 
Size:	178.2 KB 
ID:	6683  

  7. Thanks:

    telengard (4th July 2019)

  8. #6
    Member
    Join Date
    Jul 2019
    Location
    USA
    Posts
    23
    Thanks
    8
    Thanked 1 Time in 1 Post
    Quote Originally Posted by Shelwien View Post
    In other news, in may be possible to decompile code for this cpu, with ghidra.
    https://nuget.pkg.github.com/VGKints...turn-Processor
    My attempt wasn't very successful, but maybe there're better resources somewhere?
    Wow, this is great stuff, thank you for the info!

    I hadn't thought of trying out Ghidra, I am used to IDA and it supported a variant of the super-h (sh3) this sampler uses. It seemed to be the best I could find, but it seems Ghidra can do it to.
    Decompilation would make things WAY easier for me, I've been disassembling it and not being too familiar with the instruction set it has been painful... the delay execute is a real brain burner.

    My weak spot as far as dev is algorithms so I'll have to dig deeper, but knowing it is related to LZSS should help me further along. My goal is just to be able to unpack this program, fix some bugs, and re-compress. I have purchased a hardware debugger for handling the (hopefully unlikely) case where I brick the machine.

    Click image for larger version. 

Name:	3.png 
Views:	78 
Size:	360.2 KB 
ID:	6684

    If you happen to know of any pointers for material that would help me learn what I need to to understand LZSS (I will google), that would be super.

    thanks again

  9. #7
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,982
    Thanks
    298
    Thanked 1,309 Times in 745 Posts
    Here's my attempt at decoding it.
    It seems to use consistently 2 bytes per match, but I wasn't able to guess the layout.
    Decoding starts from offset of "LZ98L016"+32 (FF byte first).
    It would help if you could provide a dump of unpacked data (along with corresponding compressed data).
    Attached Files Attached Files

  10. Thanks:

    telengard (4th July 2019)

  11. #8
    Member
    Join Date
    Jul 2019
    Location
    USA
    Posts
    23
    Thanks
    8
    Thanked 1 Time in 1 Post
    Quote Originally Posted by Shelwien View Post
    Here's my attempt at decoding it.
    It seems to use consistently 2 bytes per match, but I wasn't able to guess the layout.
    Decoding starts from offset of "LZ98L016"+32 (FF byte first).
    It would help if you could provide a dump of unpacked data (along with corresponding compressed data).
    Awesome, thanks!

    I will work on getting that, I have a dev kit for the SH7216 (which isn't the same, but is similar) which also came with a serial debugger and I need to hook that up and dump some values from flash RAM. I know the offset in flash that the binary is placed so it should be straightforward to map things up. The issue is, this is a non documented board and I have to figure out the wiring for the header, but I need to do this at some point to continue, so I will work on it.

    In the meantime, is there anything I can disassemble to give more insight? I will take what you have and try to map it to the decompress_into_ram routine. What should I be looking for when you say "layout"?

  12. #9
    Member
    Join Date
    Jul 2019
    Location
    USA
    Posts
    23
    Thanks
    8
    Thanked 1 Time in 1 Post
    These are screengrabs of the validation and decompression subroutines. I've been annotating them as I go, but I'm not 100% done yet. Just putting them here in the event you wanted to take a peek.

    Validation 1

    Click image for larger version. 

Name:	validate_1.png 
Views:	67 
Size:	360.2 KB 
ID:	6691

    Validation 2

    Click image for larger version. 

Name:	validate_2.png 
Views:	48 
Size:	125.4 KB 
ID:	6692

    Decompress 1, stuff related to decompression seems to start around 0x800029C4

    Click image for larger version. 

Name:	decomp_1.png 
Views:	56 
Size:	346.5 KB 
ID:	6693

    Decompress 2

    Click image for larger version. 

Name:	decomp_2.png 
Views:	47 
Size:	291.1 KB 
ID:	6694

    Decompress 3

    Click image for larger version. 

Name:	decomp_3.png 
Views:	46 
Size:	315.7 KB 
ID:	6695

    And I'm curious to know if you got as far as I did with your program, the FF I too have marked as the start at offset 0x20044.

    phantasie[~/mus/hardware/recording/roland_mv8800/firmware/my_mods/extractions]% ./unlz98 main_compressed_offset_20044.bin decompressed.bin
    error: pos=30 dist=32; c=0106

  13. #10
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,982
    Thanks
    298
    Thanked 1,309 Times in 745 Posts
    > In the meantime, is there anything I can disassemble to give more insight?

    There should be a match copy loop somewhere (like memcpy).
    Finding that could help with understanding how it calculates match length and distance.

    > What should I be looking for when you say "layout"?

    Code:
    ROM:80020044 FF                                   .data.b h'FF
    ROM:80020045 D0 0B 40 0E D0 0D D1+                .data.b h'D0, h'B,h'40, h'E,h'D0, h'D,h'D1, h'E
    ROM:8002004D FF                                   .data.b h'FF
    ROM:8002004E E2 00 30 12 89 03 20+                .data.b h'E2,   0,h'30,h'12,h'89,   3,h'20,h'22
    ROM:80020056 FF                                   .data.b h'FF
    ROM:80020057 70 04 AF FA 00 09 D0+                .data.b h'70,   4,h'AF,h'FA,   0,   9,h'D0,   7
    ROM:8002005F BF                                   .data.b h'BF            ; 10111111
    ROM:80020060 40 0B 20 0B D0 06                    .data.b h'40, h'B,h'20, h'B,h'D0,   6
    ROM:80020066 06 01                                .data.w b'0000011000000001   ; match
    ROM:80020068 00                                   .data.b 0
    ROM:80020069 FD                                   .data.b h'FD            ; 11111101
    ROM:8002006A 09                                   .data.b 9
    ROM:8002006B 10 09                                .data.w b'0001000000001001
    ROM:8002006D 60 00 00 F0 8C 01                    .data.b h'60
    ROM:8002006D                                      .datab.b 2,    0
    ROM:8002006D                                      .data.b h'F0,h'8C,   1
    ROM:80020073 FF                                   .data.b h'FF
    ROM:80020074 01 D0 8C 6E 11 30 8C+                .data.b    1,h'D0,h'8C,h'6E,h'11,h'30,h'8C,h'6E
    Presuming its a typical LZSS, there should be length and distance fields encoded
    for each match.
    From what I could manually parse, here it seems to be 2 bytes per match always.
    Code:
    06 01  00000110 00000001
    10 09  00010000 00001001
    But even if it uses simple fixed-size bitfields for length and distance,
    there's still a choice of LE/BE order for that 16-bit value,
    how to split it to length and distance (bitfield sizes),
    and base len/dist values.

  14. Thanks:

    telengard (5th July 2019)

  15. #11
    Member
    Join Date
    Jul 2019
    Location
    USA
    Posts
    23
    Thanks
    8
    Thanked 1 Time in 1 Post
    Here's the de-compiled version of the decompress_into_ram routine via Ghidra.
    Attached Files Attached Files

  16. #12
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,982
    Thanks
    298
    Thanked 1,309 Times in 745 Posts
    Seems to work like this: http://nishi.dreamhosters.com/u/unLZ98_v0.zip

    Both match layout and overall algorithm are pretty strange, I'd never guess without that pseudocode.
    Instead of the normal match distance it encodes absolute window position.

      for( i=0; i<winsize; i++ ) win[i]=0;

    for( pos=0xFEE;; ) {
    c = getc(f); if( c==-1 ) break;
    flag = c;

    for( i=0; i<8; i++ ) {

    c = getc(f);

    if( (flag>>i)&1 ) {
    // literal
    win[ (pos++)&winmask ] = c; putc( c, g );

    } else {
    // match

    d = getc(f);

    l = (d & 15) + 3;
    d = c + (d>>4)*256;

    for( j=0; j<l; j++ ) {
    c = win[ (d+j)&winmask ];
    win[ (pos++)&winmask ] = c; putc( c, g );
    }

    }

    }
    }

  17. #13
    Member
    Join Date
    Jul 2019
    Location
    USA
    Posts
    23
    Thanks
    8
    Thanked 1 Time in 1 Post
    AMAZING!!! The output disassembles perfectly (although IDA doesn't do a very good job, I spend a lot of time marking regions as code/functions as I spot them), and I see you picked up on the 0xFFs at the end being non-relevant (it's for being resident in flash).

    There's a lot to explore now, but I'm wondering, does this just get "played back" in reverse to compress again? Once I make changes, I'll need to do that to re-flash the device with changes. I have checksums to handle, but that is easy enough.

    There were some bytes repeated twice just prior to the compressed portion which I thought might be the size of the uncompressed code (0x6393D4 == 6,525,908 bytes), but it seems to have ended up a little bigger (7,181,268). I'll have to dig into that. From what I could tell, that number itself, and divided by 64, was utilized during the decompression into RAM.

    Thanks so much for what you've done, it would have taken me a very, very long time to get to this point (if at all).

  18. #14
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,982
    Thanks
    298
    Thanked 1,309 Times in 745 Posts
    > There's a lot to explore now, but I'm wondering,
    > does this just get "played back" in reverse to compress again?

    Its not, but I can make a simple encoder if you're sure that its decoded correctly.
    Keep in mind that encoding likely would be different even without any changes -
    it would take too much work to reverse-engineer the precise encoding algorithm.
    But in theory it shouldn't matter if it decodes?

    > There were some bytes repeated twice just prior to the compressed portion
    > which I thought might be the size of the uncompressed code (0x6393D4 == 6,525,908 bytes),

    00 6D 93 D4
    Its actually precisely the decoded size (big-endian)

    > Thanks so much for what you've done, it would have taken me a very,
    > very long time to get to this point (if at all).

    Tell that twitter guy about it too :)

  19. Thanks:

    telengard (5th July 2019)

  20. #15
    Member
    Join Date
    Jul 2019
    Location
    USA
    Posts
    23
    Thanks
    8
    Thanked 1 Time in 1 Post

    Smile

    Quote Originally Posted by Shelwien View Post
    > There's a lot to explore now, but I'm wondering,
    > does this just get "played back" in reverse to compress again?

    Its not, but I can make a simple encoder if you're sure that its decoded correctly.
    Keep in mind that encoding likely would be different even without any changes -
    it would take too much work to reverse-engineer the precise encoding algorithm.
    But in theory it shouldn't matter if it decodes?
    Makes sense if the end result is the same. And yes, it definitely is decoded OK. I am able to construct functions and strings from the decompressed binary in IDA. Including at the top, in the middle, and towards the end.

    Quote Originally Posted by Shelwien View Post
    > There were some bytes repeated twice just prior to the compressed portion
    > which I thought might be the size of the uncompressed code (0x6393D4 == 6,525,908 bytes),

    00 6D 93 D4
    Its actually precisely the decoded size (big-endian)
    Yeah, that makes sense and fits what I see happening in the code, and I feel this is another data point proving that it decompressed OK. If the algorithm wasn't correct, I have to imagine the size wouldn't line up. Although you would know much better than I if that is something that would happen.

    Quote Originally Posted by Shelwien View Post
    > Thanks so much for what you've done, it would have taken me a very,
    > very long time to get to this point (if at all).

    Tell that twitter guy about it too
    I did! We have communicated over email. He had yanked firmware off an old digital piano and wanted to make new presets for it, this will allow him to I believe. This will let some old music hardware live just a little longer.

    thanks again!

  21. #16
    Member
    Join Date
    Jul 2019
    Location
    USA
    Posts
    23
    Thanks
    8
    Thanked 1 Time in 1 Post
    I've spent a few more days with this and I think I can safely say the decoding is being done correctly. All the strings I see referenced in the code are intact and there has been (so far) no code blocks that have had issues being disassembled. It's going to take quite a while to go through the 7+ megs of code (I have to manually mark regions as code/data/strings), but once that is done I will attempt to make some changes.

    If there is anything I can do to assist with any effort to handle the compression side, please let me know. And I think I get what you mean now, that the compressed code would be different than the original but would decompress to the same thing. This should work assuming that the code embedded in the firmware can handle the compressed code.

  22. #17
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,982
    Thanks
    298
    Thanked 1,309 Times in 745 Posts
    Here's a dumb encoder: http://nishi.dreamhosters.com/u/unLZ98_v1.zip
    Somehow still compresses a bit better than original size: 3,281,098 vs 3,282,595

    Keep in mind that there's an uncertain thing at the end of compressed data - LZ tokens are packed in sets of 8, so what happens if there's less at the end?
    I had to also patch the decoder a little, since it assumed a complete token set at the end.

  23. Thanks:

    telengard (9th July 2019)

  24. #18
    Member
    Join Date
    Jul 2019
    Location
    USA
    Posts
    23
    Thanks
    8
    Thanked 1 Time in 1 Post
    Great, thank you Shelwien!

    I will test this out tomorrow. As for the tokens, if I just align/pad the program to a certain size, would that work? I can always add 0xFF to the end of the program to byte align.

    As for the de-coder, should I re-run it on the binary? If it just affects the end, that shouldn't be an issue, but before I get too heavy into the disassembling, if it makes a big difference I will. I'm pretty sure Ghidra imports the binary that is being disassembled, not sure if I can "update" it, so if I need to replace it I'd rather do it now when I only have a few hours into disassembling/marking up the binary. I'm doing about 10k an hour, so.... the 7+ megs will take a bit.

  25. #19
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,982
    Thanks
    298
    Thanked 1,309 Times in 745 Posts
    > As for the tokens, if I just align/pad the program to a certain size, would that work?

    Yes. But for now just keep in mind that in theory decoder could add several bytes of garbage at the end.
    I just don't know what original decoder does in this case, there's probably no problem at all.

    > As for the de-coder, should I re-run it on the binary?

    No, the output is the same for the original binary.
    Previous version of decoder just adds garbage at the end of files unpacked from output of my encoder.

    > Ghidra imports the binary

    Btw, ghidra has import/export plugins for Ida, so you can use both for analysis.

  26. #20
    Member
    Join Date
    Jul 2019
    Location
    USA
    Posts
    23
    Thanks
    8
    Thanked 1 Time in 1 Post
    Quote Originally Posted by Shelwien View Post
    > As for the tokens, if I just align/pad the program to a certain size, would that work?

    Yes. But for now just keep in mind that in theory decoder could add several bytes of garbage at the end.
    I just don't know what original decoder does in this case, there's probably no problem at all.

    > As for the de-coder, should I re-run it on the binary?

    No, the output is the same for the original binary.
    Previous version of decoder just adds garbage at the end of files unpacked from output of my encoder.

    > Ghidra imports the binary

    Btw, ghidra has import/export plugins for Ida, so you can use both for analysis.
    Thanks for the tip on Ghidra. It does a good job, I just need to manually mark most things, but once I do that, barring a few instructions, it disassembles (and decompiles!) quite well.

    I compiled both of your programs on my Linux box and they work well, thank you!

    I ran dhex on the original compressed and on a version that was decompressed and then re-compressed. They seem to diverge quite quickly. I don't know any theory going on here, but can the following work?

    I take the original code and decompress, make some changes, re-compress and then the original boot code loads it and decompresses it.

    I will be able to try this for real hopefully within the next couple weeks. I have a 2nd machine coming and I just need to solder on a debug header, map the pins, and get the software going. I want to have that working before I attempt trying any new changes. I'll start with something easy like changing a string. I just don't want to brick an $800 machine and not be able to recover.

  27. #21
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,982
    Thanks
    298
    Thanked 1,309 Times in 745 Posts
    > I ran dhex on the original compressed and on a version that was decompressed and then re-compressed.
    > They seem to diverge quite quickly.

    LZ compression works by replacing repeated strings with references
    ({12-bit position;4-bit length} in LZ98 case).
    Problem is, there're multiple equally correct representations for the same data -
    for example, we can choose to not use string references ("matches") at all,
    or we can use any of multiple previous instances of the same string
    as reference (only match position would be different).

    Also, LZ matchfinding is usually implemented with some type of hashtable,
    so precisely reproducing the same compression can be hard.

    > I take the original code and decompress, make some changes,
    > re-compress and then the original boot code loads it and decompresses it.

    That's the only thing we can do really - test and change something if it doesn't work.
    Well, unless the encoder function is also there somewhere.
    For example, in the LZ98 header, there's a suspicious binary field "00 01 00 00".
    Could anything special happen after decoding 64k of data?

    > I'll start with something easy like changing a string.

    Good luck! :)

  28. #22
    Member
    Join Date
    Jul 2019
    Location
    USA
    Posts
    23
    Thanks
    8
    Thanked 1 Time in 1 Post
    Quote Originally Posted by Shelwien View Post
    > I ran dhex on the original compressed and on a version that was decompressed and then re-compressed.
    > They seem to diverge quite quickly.

    LZ compression works by replacing repeated strings with references
    ({12-bit position;4-bit length} in LZ98 case).
    Problem is, there're multiple equally correct representations for the same data -
    for example, we can choose to not use string references ("matches") at all,
    or we can use any of multiple previous instances of the same string
    as reference (only match position would be different).

    Also, LZ matchfinding is usually implemented with some type of hashtable,
    so precisely reproducing the same compression can be hard.
    That makes total sense to me.

    Quote Originally Posted by Shelwien View Post
    > I take the original code and decompress, make some changes,
    > re-compress and then the original boot code loads it and decompresses it.

    That's the only thing we can do really - test and change something if it doesn't work.
    Well, unless the encoder function is also there somewhere.
    For example, in the LZ98 header, there's a suspicious binary field "00 01 00 00".
    Could anything special happen after decoding 64k of data?
    Good points. I'm wondering what I could do to add some clarity once I can test the newly compressed binary. If it fails, would having a memory dump of the unpacked blob help?

    One thing I hadn't mentioned, and this may be an option. I can possibly just change the boot program to not bother with compression or use something else (simpler). I really didn't want to modify the boot program (and I'm not really sure I can yet). But this may be an option if for some reason a compressor that works can't be created due to the lack of info.

    Quote Originally Posted by Shelwien View Post
    > I'll start with something easy like changing a string.

    Good luck!
    thanks! I'll report back once I have more to share. Thanks again for all of your help, very appreciated!

  29. #23
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,982
    Thanks
    298
    Thanked 1,309 Times in 745 Posts
    > If it fails, would having a memory dump of the unpacked blob help?

    Yes, we'd see if something decoded incorrectly.

    > I can possibly just change the boot program to not bother with compression or use something else (simpler).

    I had the same idea, but it won't fit without compression.
    Well, lzma can compress it 3x better, so we can use it when you'd want to install linux there or something :)

  30. #24
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,982
    Thanks
    298
    Thanked 1,309 Times in 745 Posts
    Huh, turns out, it was the standard Okumura LZSS, supported by quickbms.
    http://nishi.dreamhosters.com/u/unLZ98_v2.zip

    But I was right that I'd not be able to reverse-engineer the encoder from data :)
    (Replaced the encoder with quickbms version, now matches original compressed data after recompression).

  31. Thanks:

    Mike (11th July 2019)

  32. #25
    Member
    Join Date
    Jul 2019
    Location
    USA
    Posts
    23
    Thanks
    8
    Thanked 1 Time in 1 Post
    Quote Originally Posted by Shelwien View Post
    Huh, turns out, it was the standard Okumura LZSS, supported by quickbms.
    http://nishi.dreamhosters.com/u/unLZ98_v2.zip

    But I was right that I'd not be able to reverse-engineer the encoder from data
    (Replaced the encoder with quickbms version, now matches original compressed data after recompression).
    Whoa, somehow I missed this post. So you are saying it is actually not all that obscure, just given an oddball name (LZ9?
    It also sounds like there is an encoder I can use so I don't have to come up with something different! That's awesome!

    I've made a LOT of progress over the past couple of months reversing, and getting to the point where I can attempt to read flash (lots of LONG boring HW related stories, one issue after another).

    One thing I was hitting, and I thought it might be due to the decoding, was 99% of the disassembly looks very normal, but I see a few cases where there are JMPs happening to the middle of ASCII string data. I've spent a lot of time laying out the memory map of the 3 programs (loader, boot program, and uncompressed main program) taking into account what I've reversed for small code caves and offsets, so it's possible I have missed something there, but these are in the middle of large swaths of 100% legit SH3 assembly. Here's a screenshot example of what I'm talking about:

    And thanks for finding more info about the LZ algorithm, that's going to allow me to get even further now (if I could only write to flash!)

    Click image for larger version. 

Name:	string.png 
Views:	74 
Size:	8.9 KB 
ID:	6915Click image for larger version. 

Name:	jmp_to_string.png 
Views:	55 
Size:	9.0 KB 
ID:	6914
    Last edited by telengard; 6th October 2019 at 21:50.

  33. #26
    Member
    Join Date
    Jul 2019
    Location
    USA
    Posts
    23
    Thanks
    8
    Thanked 1 Time in 1 Post
    Quote Originally Posted by telengard View Post
    Whoa, somehow I missed this post. So you are saying it is actually not all that obscure, just given an oddball name?
    It also sounds like there is an encoder I can use so I don't have to come up with something different! That's awesome!

    I've made a LOT of progress over the past couple of months reversing, and getting to the point where I can attempt to read flash (lots of LONG boring HW related stories, one issue after another).

    One thing I was hitting, and I thought it might be due to the decoding, was 99% of the disassembly looks very normal, but I see a few cases where there are JMPs happening to the middle of ASCII string data. I've spent a lot of time laying out the memory map of the 3 programs (loader, boot program, and uncompressed main program) taking into account what I've reversed for small code caves and offsets, so it's possible I have missed something there, but these are in the middle of large swaths of 100% legit SH3 assembly. Here's a screenshot example of what I'm talking about:

    And thanks for finding more info about the LZ algorithm, that's going to allow me to get even further now (if I could only write to flash!)

    Click image for larger version. 

Name:	string.png 
Views:	74 
Size:	8.9 KB 
ID:	6915Click image for larger version. 

Name:	jmp_to_string.png 
Views:	55 
Size:	9.0 KB 
ID:	6914
    I found another example where things don't seem to make sense... a function stuffs a few registers with values and then calls in the middle of a different function (and the function seems non-related as well)

    In screenshot one you can see the jsr to 0x8c010d20 (the 400b does correctly assembly to jsr r0). 2nd screenshot shows what's at 0x8c010d20.

    There is very similar code which works on the same addrs and it calls what I've determined to be memcpy() (see screenshot 3). I was expecting the example that doesn't map out right to also be doing something similar to a memcpy as it is specifing the base location of flash and a location in ram.

    I've been reversing this for a few months now, and just about everything seems to check out OK except for these very few stragglers.... odd
    Attached Thumbnails Attached Thumbnails Click image for larger version. 

Name:	Screenshot_1.png 
Views:	36 
Size:	15.3 KB 
ID:	6967   Click image for larger version. 

Name:	Screenshot_2.png 
Views:	41 
Size:	33.5 KB 
ID:	6968   Click image for larger version. 

Name:	Screenshot_3.png 
Views:	31 
Size:	14.5 KB 
ID:	6969  

  34. #27
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,982
    Thanks
    298
    Thanked 1,309 Times in 745 Posts
    Well, v2 encoder produces _exactly_ the same compressed data, so I think that unpacked data must be correct there.
    I guess you can compare unpacked file there with the one you're disassembling?

    Another idea is that there could be some bugs (or unsupported instructions) in that processor module.
    Maybe compare with ida output?

    Unfortunately I don't think I can help you with actual code analysis there :)

  35. #28
    Member
    Join Date
    Jul 2019
    Location
    USA
    Posts
    23
    Thanks
    8
    Thanked 1 Time in 1 Post
    Quote Originally Posted by Shelwien View Post
    Well, v2 encoder produces _exactly_ the same compressed data, so I think that unpacked data must be correct there.
    I guess you can compare unpacked file there with the one you're disassembling?

    Another idea is that there could be some bugs (or unsupported instructions) in that processor module.
    Maybe compare with ida output?

    Unfortunately I don't think I can help you with actual code analysis there
    Totally understand, just bouncing stuff around to see if anything makes sense or is possibly at issue.

    Yeah, I was planning to check out how IDA views it. Surrounding blocks of code look legit so there is something odd, and the instructions all check out to what Ghidra things when I look at the SH3 Hardware manual. Knowing that you were able to go back and forth and have it be exact gives me a lot of confidence that it is something else. There is a LOT of code and as I mentioned it all looks good except for the these couple of spots.

    What did you mean by compare the unpacked file w/ the one I'm disassembling? I had unpacked using your unLZ98 and then imported it into Ghirda, so it should be the same, right? Should I also try decompressing with quickbms to match the encoder? Is that what you mean?

  36. #29
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,982
    Thanks
    298
    Thanked 1,309 Times in 745 Posts
    > What did you mean by compare the unpacked file w/ the one I'm disassembling?

    I mean, there were multiple decoder versions, or maybe the file got corrupted for some reason?
    My idea was to unpack/pack the data with v2, make sure that the output is identical,
    then compare the code bytes for incorrectly disassembled data in ghidra with corresponding
    offset in unpacked file.

    > I had unpacked using your unLZ98 and then imported it into Ghirda, so it should be the same, right?

    Yes, but stuff happens.

    > Should I also try decompressing with quickbms to match the encoder? Is that what you mean?

    No, quickbms is not really automatic, you'd have to write a script for it to make it work.

  37. #30
    Member
    Join Date
    Jul 2019
    Location
    USA
    Posts
    23
    Thanks
    8
    Thanked 1 Time in 1 Post
    Quote Originally Posted by Shelwien View Post
    > What did you mean by compare the unpacked file w/ the one I'm disassembling?

    I mean, there were multiple decoder versions, or maybe the file got corrupted for some reason?
    My idea was to unpack/pack the data with v2, make sure that the output is identical,
    then compare the code bytes for incorrectly disassembled data in ghidra with corresponding
    offset in unpacked file.
    I did that and it all checks out, also verified I see the exact same thing in IDA.

    Quote Originally Posted by Shelwien View Post
    > I had unpacked using your unLZ98 and then imported it into Ghirda, so it should be the same, right?

    Yes, but stuff happens.

    > Should I also try decompressing with quickbms to match the encoder? Is that what you mean?

    No, quickbms is not really automatic, you'd have to write a script for it to make it work.
    Ok, I'll have to figure out how to do that. Before coming to this forum, I was fiddling with it and had this:


    endian big
    comtype lzss0
    get ZSIZE long
    get SIZE long
    savepos OFFSET
    get NAME filename
    string NAME + ".unpacked"
    clog NAME OFFSET ZSIZE SIZE


    If you feel it is not worth comparing with your v2 code, I won't spend more time on it. There's so much that looks correct I have a hard time believing the if the v2 decompression program was off it would only be off in very few select places in almost 8M of assembly. I'd expect a lot of differences. But I'm not very knowledgeable about compression, etc so that may be the case.

Page 1 of 2 12 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •