Hacking Lemmings Revolution

[mobius]

  I actually looked enough into it that I have identified the section of code that does the decompression, and can easily hook up debugger commands associated with a breakpoint to dump decompressed data to a file each time the program decompresses a file from BOX.  This is how I got the LR font BMP to http://www.lemmingsforums.com/index.php?topic=50.15" class="bbc_link" target="_blank">post here, except the forum seems to be acting odd when I made replies to that super-old thread, so I don't know if the attachment made it there.

Geoo said he couldn't see it either. logged in I can't read it, the page takes really long to load and cuts off at minimac's post but not logged in I can see it (of course the picture isn't there)

[ccexplore]

Actually I just remember that the font BMP's data mostly comes from the uncompressed ^font.alf file, so that is a poor example of decompression.  But pick any file you want decompressed and I can do it through the debugger, at least from my copy of lemmings.box/patch.box.  So for example I can definitely hook it up again to get Textures\Cylinder\e14_kf_1\OUT_e14_kf_1_7_0Hi.bmp extracted, although it sounds like we think the compressed data itself may be bad to begin with for that file?  Today's Friday though so I still have work to do in real-life (ie. job).

BTW, one quick way you can see what a bitmap looks like (w/o bothering about the actual data, compressed or otherwise), is to make a copy of the EXE, hex-edit to find and replace the string texture\main_logo.bmp with path to the bitmap you want to see, and then run the modified EXE and see what the start-screen logo is replaced with.

The bitmap files contain a 5-byte header:

Code: [Select]

Byte    Version number maybe? Currently set to 0x01
Int16   Packed size, which is the total file size - 5
Int16   Unpacked size

The first byte actually is number of sections.  As you noted, packed and unpacked sizes are limited to Int16 (actually UInt16 I think, IIRC), so to support larger file sizes (like texture\main_logo.bmp which is a full 640x480x24bpp BMP), contents are split into multiple sections whose size fit within UInt16, and compressed separately (I think, not sure if no state data gets carried over from section to section).  That is:

number of sections (packed size of section, unpacked size of section, compressed data), (packed size of section, unpacked size of section, compressed data), ...

[ccexplore]

  I actually looked enough into it that I have identified the section of code that does the decompression, and can easily hook up debugger commands associated with a breakpoint to dump decompressed data to a file each time the program decompresses a file from BOX.  This is how I got the LR font BMP to http://www.lemmingsforums.com/index.php?topic=50.15" class="bbc_link" target="_blank">post here, except the forum seems to be acting odd when I made replies to that super-old thread, so I don't know if the attachment made it there.

Geoo said he couldn't see it either. logged in I can't read it, the page takes really long to load and cuts off at minimac's post but not logged in I can see it (of course the picture isn't there)

Yeah, I think my act of posting on that old thread has somehow corrupted the data on it. http://www.lemmingsforums.com/Smileys/lemmings/undecided.gif" alt=":-\" title="Undecided" class="smiley" /> http://www.lemmingsforums.com/Smileys/lemmings/shocked.gif" alt=":o" title="Shocked" class="smiley" />  The really funny thing is that I can still read the post as guest, so I'm thoroughly confused as to what's going on.  And since it refuses to display my posts when I logged in, I can't delete the post either (although maybe with the damage already done, further modifications might just make things worse).

Let me repost later on a new thread instead.

[ccexplore]

Or maybe I can just post here.  The attached is what I got out of the debugger for all BMPs loaded from BOX from launching the game to reaching the start screen.  Numbers are auto-generated (the debugger I used don't have powerful enough scripting support to do anything fancy with the filename of the dump command).  font.png is actually not from any compressed BMPs, it so happens that for the font, the main BMP is just a 256x240 white rectangle, and there is an associated separate .alf file that contains raw bitmap bits for the alpha-channel part of the bitmap.  font.png is derived from the ^font.alf file.  Other "all white" rectangles are probably similarly formatted.

[GuyPerfect]

So for example I can definitely hook it up again to get Textures\Cylinder\e14_kf_1\OUT_e14_kf_1_7_0Hi.bmp extracted, although it sounds like we think the compressed data itself may be bad to begin with for that file?

Unfortunately, no. There's nothing wrong with the file. I snagged this as it passed through my texture loader:

http://i7.photobucket.com/albums/y255/bgng/OUT_E14_KF_1_7_0HI.png" alt="" class="bbc_img" />

I mean, it's fortunate that there's nothing wrong with the file, but unfortunate that the game is crashing for an unrelated reason. Who knows how many hours it took finding that out.

Let me see if I can just tell the game to ignore the error.

[GuyPerfect]

Well, I told the game to just ignore the error and it crashed for reals.

Code: [Select]

00450379 | 83F9 03       | CMP     ECX, 3                   |
0045037C | 75 1F         | JNZ     0045039D                 | Initial error is detected here
0045037E | 8B95 B0FEFFFF | MOV     EDX, DWORD PTR [EBP-150] |
00450384 | 83EA 05       | SUB     EDX, 5                   |
00450387 | 52            | PUSH    EDX                      |
00450388 | 8B45 F0       | MOV     EAX, DWORD PTR [EBP-10]  |
0045038B | 50            | PUSH    EAX                      |
0045038C | 8B8D B8FEFFFF | MOV     ECX, DWORD PTR [EBP-148] |
00450392 | 51            | PUSH    ECX                      |
00450393 | E8 48CC0400   | CALL    0049CFE0                 |
00450398 | 83C4 0C       | ADD     ESP, C                   |
0045039B | EB 6A         | JMP     00450407                 |

0045039D | 8B55 F0       | MOV     EDX, DWORD PTR [EBP-10]  |
004503A0 | 33C0          | XOR     EAX, EAX                 |
004503A2 | 8A42 FF       | MOV     AL, BYTE PTR [EDX-1]     |
004503A5 | 83F8 04       | CMP     EAX, 4                   | If this passes, the game will not crash
004503A8 | EB 1A         | JMP     004503C4                 |

004503AA | 8B4D 08       | MOV     ECX, DWORD PTR [EBP+8]   |
004503AD | 51            | PUSH    ECX                      |
004503AE | 6A 3F         | PUSH    3F                       |
004503B0 | 68 78034C00   | PUSH    4C0378                   |
004503B5 | E8 68240300   | CALL    00482822                 | This calls the routine to display the message box
004503BA | 83C4 0C       | ADD     ESP, C                   |
004503BD | 6A 00         | PUSH    0                        |
004503BF | E8 8FCF0400   | CALL    0049D353                 | This presumably has an exit() somewhere.

004503C4 | 8B95 A8FEFFFF | MOV     EDX, DWORD PTR [EBP-158] |
I'm still experimenting seeing if I can get it to pass anyway, since as far as I can tell, the texture is valid by the time it gets here.

[GuyPerfect]

Ohohoooooo, they thought they were clever.

I believe I know the source of the problem, and it's an anti-piracy countermeasure. Let me run a couple tests to make sure.


EDIT:
Bahaha! Man, was that ever dumb. To think I wasted a whole day on this.

No, it's not an anti-piracy countermeasure; it's just a big wad of derp. The only users affected are those who chose a Typical install from the original CD. Users with a Compact installation will not crash when loading the level.

The installer writes a different lemmings.box file than is on the CD. I don't know exactly what changed or how, but copying the file from the CD into the installation directory after running a Typical install will fix the level and make it playable.

What a load of crap.

[GuyPerfect]

Attached to this post is Full Color v1.0 (Beta 4). This is a release candidate.

The updated Readme is as follows:

Code: [Select]

Lemmings Full Color Revolution!             Windows Vista/7 Compatibility Patch
Written and maintained by Lemmings Forums        http://www.lemmingsforums.com/
  Version 1.0 (Beta 4) - April 27, 2012


About this program:

As you've probably noticed, Lemmings Revolution has been falling apart over the
years as Windows went through its many updates. It started out innocently
enough on Windows XP: a few of the icons had wonky colors, but it was otherwise
okay. But then, when windows Vista and 7 came about, those icky colors just
turned full-on black. And the main menu became a virtually unusable cluster of
black rectangles. Oh, and the sound stopped working! It's a real mess.

Well, this handy little gadget fixes all of those problems. While the technical
details are beyond the scope of this readme file, the tl;dr version is that the
game program does not conform 100% to the DirectX specification. It was just
fine back on Windows 98 where it worked anyway, but as time marches on, we see
that the game was released with what we have since learned to be show-stopping
bugs!


Things that this gizmo will fix:
 * Restores audio on Windows Vista and 7. It was completely AWOL before.
 * Provides a new texture loading routine. This corrects the messed-up colors.
 * Tweaks the main menu graphics. Solid black rectangles are hard to read.


Things you can fix yourself:
 * Level 9-6, The High Dive, has practically never worked for users who
   selected the "Typical" installation option. This can be corrected by copying
   "lemmings.box" from the CD and into the Lemmings Revolution installation
   directory. For real. The installer doesn't copy it right for some reason.


How to use this bad boy:

 * This patch is only designed to work with the original Lemmings Revolution
   EXE files (the game has seen various releases), so if you have one with any
   modifications, don't expect it to work. When in doubt, just re-install it
   from the CD. Don't worry: you won't lose your save data.

 * Locate the Lemmings Revolution installation directory on your computer. By
   default, this is "C:\Program Files (x86)\Take 2\Lemmings Revolution\" for
   the North America releases. Believe in yourself. I'm sure you can find it.

 * Make sure "Lemmings Revolution.exe" is not read-only. You can check this by
   right-clicking the file, selecting Properties, then making sure the box next
   to "Attributes" is un-checked.

 * Copy the Full Color EXE file into the Lemmings Revolution installation
   directory and run it. If UAC is enabled, you will have to run it as
   administrator. To do so, right-click the Full Color file and select
   "Run as administrator"

 * The program will do its darnedest to fix up the Lemmings Revolution EXE so
   that it works correctly again. Be sure to read the contents of the window
   that appears for information on what it was able to accomplish. If there was
   a problem, it will let you know what went wrong.


Additional information:

As noted above, there's a few different versions of Lemmings Revolution out
there. In fact, no one's really sure just how many there are. It's not feasible
to track them all down to make a comprehensive list, so this patch is instead
designed to be flexible and figure out exactly what needs to be done by
analyzing the Lemmings Revolution EXE file that it's intended to patch.

Some of the code updates were too large or otherwise too complex to be fitted
into the original EXE file, so they were moved into a DLL file instead. The
Full Color program will produce one such DLL file when it patches Lemmings
Revolution, adding it to the installation directory. The file's name is
"patch.dll" and it is required for the game to run, so don't delete it.

In addition to patching the Lemmings Revolution EXE file, that DLL file itself
is configured to work specifically with the version of Lemmings Revolution
being patched. If you copy a patch DLL from a different installation of
Lemmings Revolution, it will not work. In order to ensure correct
functionality, always run the Full Color program on an un-modified Lemmings
Revolution EXE.


Change log:

 * April 27, 2012 - Original release
   - Introducing audio fix
   - Introducing texture fix
   - Introducing main menu fix


Credits:
 * Lemmings Revolution is ©2000 Psygnosis/Talonsoft and Take-Two Interactive
 * Lemmings Forums staff (http://www.lemmingsforums.com/)
   - ccexplore, for technical research, ideas and testing support
   - Guy Perfect, for reverse engineering and patch development
   - thick molasses, for bug investigation and testing support



[GuyPerfect]

Hey ccexplore, since you've already located it, would you be so kind as to post the EXE you're using and the address of the bitmap decompression routine? I'd like to disassemble it to see what it's doing.

[GuyPerfect]

Nevermind, I found it.

In the EXE from Download.com linked earlier:

Code: [Select]

00467C28 | 55          | PUSH    EBP                     |
00467C29 | 8BEC        | MOV     EBP, ESP                |
00467C2B | 53          | PUSH    EBX                     |
00467C2C | 51          | PUSH    ECX                     |
00467C2D | 52          | PUSH    EDX                     |
00467C2E | 56          | PUSH    ESI                     |
00467C2F | 57          | PUSH    EDI                     |
00467C30 | 8B75 08     | MOV     ESI, DWORD PTR [EBP+8]  | ;Pointer to seventh byte of the bitmap file
00467C33 | 8B7D 0C     | MOV     EDI, DWORD PTR [EBP+C]  | ;Pointer to the first byte of the output buffer
00467C36 | 8B4D 14     | MOV     ECX, DWORD PTR [EBP+14] | ;Unpacked size of this chunk
00467C39 | 55          | PUSH    EBP                     |
00467C3A | E8 14000000 | CALL    00467C53                |
00467C3F | 5D          | POP     EBP                     |
00467C40 | B8 00000000 | MOV     EAX, 0                  |
00467C45 | 72 05       | JB      00467C4C                |
00467C47 | 8BC7        | MOV     EAX, EDI                |
00467C49 | 2B45 0C     | SUB     EAX, DWORD PTR [EBP+C]  |
00467C4C | 5F          | POP     EDI                     |
00467C4D | 5E          | POP     ESI                     |
00467C4E | 5A          | POP     EDX                     |
00467C4F | 59          | POP     ECX                     |
00467C50 | 5B          | POP     EBX                     |
00467C51 | C9          | LEAVE                           |
00467C52 | C3          | RETN                            |
This function is called to decompress individual chunks in the file, which for small bitmaps is the entire file.

I'm just now diving into 00467C53, which does the heavy lifting. Most of the functions in the program are _cdecl or __stdcall, but this one's loading values into registers without pushing to the stack. It's probably a compiler-defined fastcall.


EDIT:
The cursory examination has failed. Now I get the honor of pulling apart 16-bit code one line at a time. (-:

[GuyPerfect]

I've isolated all of the code responsible for decompressing the chunks in the bitmap file. I'll be looking through it later--not right now. All of the magic happens in the code I've pasted into this post.

The functions seem to be largely 16-bit centric, and do not follow typical calling conventions. My guess is that it was an optimized 16-bit program, possibly written in assembly (as evidenced by its lack of wastefulness), and only linked into Lemmings Revolution. Whatever it is, it wasn't made by the same compiler that made the rest of the program.

Some addresses (004C0F2C and 004C1228 among others) appear to be global variables and are located in static memory. Since Decomp1 reads from these addresses prior to writing to them, it seems like it might be a persistent decoder state across data chunks. Regardless, for the first chunk of each file, these have to be initialized; there's no two ways about that.

Decomp2 does not end with a RETN instruction. The disassembly as I've provided it is correct. This particular function will be the hardest to figure out, but it's the key to the whole deal.

When Decomp1 is called the first time:

• ESI = Address of seventh byte of BMP file
• EDI = Address of first byte of output buffer
• ECX = Unpacked size of the output buffer
• Memory at 004C0F2C = Zeroes all the way down
• Memory at 004C1228 = Zeroes all the way down

When Decomp1 returns, the fully decompressed BMP file will be located at [EDI]

Decomp1

Code: [Select]

00467C53 | 51            | PUSH    ECX                     |
00467C54 | 57            | PUSH    EDI                     |
00467C55 | 8D3D 28124C00 | LEA     EDI, DWORD PTR [4C1228] |
00467C5B | 893D 2C0F4C00 | MOV     DWORD PTR [4C0F2C], EDI |
00467C61 | 83C7 11       | ADD     EDI, 11                 |
00467C64 | 893D 300F4C00 | MOV     DWORD PTR [4C0F30], EDI |
00467C6A | 83C7 03       | ADD     EDI, 3                  |
00467C6D | 33DB          | XOR     EBX, EBX                |
00467C6F | E8 83000000   | CALL    00467CF7                | ;Decomp2
00467C74 | 72 16         | JB      00467C8C                |
00467C76 | BB 01000000   | MOV     EBX, 1                  |
00467C7B | E8 77000000   | CALL    00467CF7                | ;Decomp2
00467C80 | 72 0A         | JB      00467C8C                |
00467C82 | BB 02000000   | MOV     EBX, 2                  |
00467C87 | E8 6B000000   | CALL    00467CF7                | ;Decomp2
00467C8C | 5F            | POP     EDI                     |
00467C8D | 59            | POP     ECX                     |
00467C8E | 73 02         | JNB     00467C92                |
00467C90 | F9            | STC                             |
00467C91 | C3            | RETN                            |
00467C92 | 49            | DEC     ECX                     |
00467C93 | B2 80         | MOV     DL, 80                  |
00467C95 | FC            | CLD                             |
00467C96 | 51            | PUSH    ECX                     |
00467C97 | 33DB          | XOR     EBX, EBX                |
00467C99 | E8 8F010000   | CALL    00467E2D                | ;Decomp3
00467C9E | 85C0          | TEST    EAX, EAX                |
00467CA0 | 74 21         | JE      00467CC3                |
00467CA2 | 8BC8          | MOV     ECX, EAX                |
00467CA4 | 8BD8          | MOV     EBX, EAX                |
00467CA6 | B0 01         | MOV     AL, 1                   |
00467CA8 | 8A26          | MOV     AH, BYTE PTR [ESI]      |
00467CAA | 22E2          | AND     AH, DL                  |
00467CAC | D0CA          | ROR     DL, 1                   |
00467CAE | 83D6 00       | ADC     ESI, 0                  |
00467CB1 | 80C4 FF       | ADD     AH, FF                  |
00467CB4 | D0D0          | RCL     AL, 1                   |
00467CB6 | 73 F0         | JNB     00467CA8                |
00467CB8 | AA            | STOSB                           |
00467CB9 | E2 EB         | LOOPD   00467CA6                |
00467CBB | 8BC3          | MOV     EAX, EBX                |
00467CBD | 59            | POP     ECX                     |
00467CBE | 2BC8          | SUB     ECX, EAX                |
00467CC0 | 72 2E         | JB      00467CF0                |
00467CC2 | 51            | PUSH    ECX                     |
00467CC3 | BB 01000000   | MOV     EBX, 1                  |
00467CC8 | E8 60010000   | CALL    00467E2D                | ;Decomp3
00467CCD | 50            | PUSH    EAX                     |
00467CCE | BB 02000000   | MOV     EBX, 2                  |
00467CD3 | E8 55010000   | CALL    00467E2D                | ;Decomp3
00467CD8 | 8BDE          | MOV     EBX, ESI                |
00467CDA | 8BF7          | MOV     ESI, EDI                |
00467CDC | F9            | STC                             |
00467CDD | 1BF0          | SBB     ESI, EAX                |
00467CDF | 59            | POP     ECX                     |
00467CE0 | 83C1 02       | ADD     ECX, 2                  |
00467CE3 | 8BC1          | MOV     EAX, ECX                |
00467CE5 | F3:A4         | REP MOVSB                       |
00467CE7 | 8BF3          | MOV     ESI, EBX                |
00467CE9 | 59            | POP     ECX                     |
00467CEA | 2BC8          | SUB     ECX, EAX                |
00467CEC | 72 02         | JB      00467CF0                |
00467CEE | EB A6         | JMP     00467C96                |
00467CF0 | D0C2          | ROL     DL, 1                   |
00467CF2 | F5            | CMC                             |
00467CF3 | 83D6 00       | ADC     ESI, 0                  |
00467CF6 | C3            | RETN                            |
Decomp2

Code: [Select]

00467CF7 | 8A06          | MOV     AL, BYTE PTR [ESI]          |
00467CF9 | 46            | INC     ESI                         |
00467CFA | A8 0F         | TEST    AL, F                       |
00467CFC | 75 0A         | JNZ     00467D08                    |
00467CFE | 8883 3A0F4C00 | MOV     BYTE PTR [EBX+4C0F3A], AL   |
00467D04 | 3C 01         | CMP     AL, 1                       |
00467D06 | F5            | CMC                                 |
00467D07 | C3            | RETN                                |
00467D08 | 53            | PUSH    EBX                         |
00467D09 | 57            | PUSH    EDI                         |
00467D0A | 8B3D 2C0F4C00 | MOV     EDI, DWORD PTR [4C0F2C]     |
00467D10 | 8AF8          | MOV     BH, AL                      |
00467D12 | 66:83E0 0F    | AND     AX, F                       |
00467D16 | 04 02         | ADD     AL, 2                       |
00467D18 | 8AE8          | MOV     CH, AL                      |
00467D1A | B1 04         | MOV     CL, 4                       |
00467D1C | D2EF          | SHR     BH, CL                      |
00467D1E | 38FC          | CMP     AH, BH                      |
00467D20 | 73 02         | JNB     00467D24                    |
00467D22 | 8AE7          | MOV     AH, BH                      |
00467D24 | 883F          | MOV     BYTE PTR [EDI], BH          |
00467D26 | 47            | INC     EDI                         |
00467D27 | FECD          | DEC     CH                          |
00467D29 | 74 15         | JE      00467D40                    |
00467D2B | 8A1E          | MOV     BL, BYTE PTR [ESI]          |
00467D2D | 46            | INC     ESI                         |
00467D2E | 8AFB          | MOV     BH, BL                      |
00467D30 | 80E3 0F       | AND     BL, F                       |
00467D33 | 38DC          | CMP     AH, BL                      |
00467D35 | 73 02         | JNB     00467D39                    |
00467D37 | 8AE3          | MOV     AH, BL                      |
00467D39 | 881F          | MOV     BYTE PTR [EDI], BL          |
00467D3B | 47            | INC     EDI                         |
00467D3C | FECD          | DEC     CH                          |
00467D3E | 75 DC         | JNZ     00467D1C                    |
00467D40 | A2 340F4C00   | MOV     BYTE PTR [4C0F34], AL       |
00467D45 | 8825 350F4C00 | MOV     BYTE PTR [4C0F35], AH       |
00467D4B | 5F            | POP     EDI                         |
00467D4C | 5B            | POP     EBX                         |
00467D4D | 56            | PUSH    ESI                         |
00467D4E | 8BF3          | MOV     ESI, EBX                    |
00467D50 | 8886 3A0F4C00 | MOV     BYTE PTR [ESI+4C0F3A], AL   |
00467D56 | C1E6 02       | SHL     ESI, 2                      |
00467D59 | 89BE 3E0F4C00 | MOV     DWORD PTR [ESI+4C0F3E], EDI |
00467D5F | 893D 360F4C00 | MOV     DWORD PTR [4C0F36], EDI     |
00467D65 | C607 00       | MOV     BYTE PTR [EDI], 0           |
00467D68 | 47            | INC     EDI                         |
00467D69 | 8B35 300F4C00 | MOV     ESI, DWORD PTR [4C0F30]     |
00467D6F | C606 00       | MOV     BYTE PTR [ESI], 0           |
00467D72 | B6 80         | MOV     DH, 80                      |
00467D74 | B5 01         | MOV     CH, 1                       |
00467D76 | 8B1D 2C0F4C00 | MOV     EBX, DWORD PTR [4C0F2C]     |
00467D7C | 8A0D 340F4C00 | MOV     CL, BYTE PTR [4C0F34]       |
00467D82 | 382B          | CMP     BYTE PTR [EBX], CH          |
00467D84 | 74 1F         | JE      00467DA5                    |
00467D86 | 43            | INC     EBX                         |
00467D87 | FEC9          | DEC     CL                          |
00467D89 | 75 F7         | JNZ     00467D82                    |
00467D8B | 880F          | MOV     BYTE PTR [EDI], CL          |
00467D8D | 47            | INC     EDI                         |
00467D8E | D0CE          | ROR     DH, 1                       |
00467D90 | 83D6 00       | ADC     ESI, 0                      |
00467D93 | 8AC6          | MOV     AL, DH                      |
00467D95 | F6D0          | NOT     AL                          |
00467D97 | 2006          | AND     BYTE PTR [ESI], AL          |
00467D99 | FEC5          | INC     CH                          |
00467D9B | 382D 350F4C00 | CMP     BYTE PTR [4C0F35], CH       |
00467DA1 | 73 D3         | JNB     00467D76                    |
00467DA3 | EB 20         | JMP     00467DC5                    |
00467DA5 | 8A25 340F4C00 | MOV     AH, BYTE PTR [4C0F34]       |
00467DAB | 2AE1          | SUB     AH, CL                      |
00467DAD | B0 00         | MOV     AL, 0                       |
00467DAF | 66:8907       | MOV     WORD PTR [EDI], AX          |
00467DB2 | 47            | INC     EDI                         |
00467DB3 | 47            | INC     EDI                         |
00467DB4 | 8AD5          | MOV     DL, CH                      |
00467DB6 | 8AC5          | MOV     AL, CH                      |
00467DB8 | 8436          | TEST    BYTE PTR [ESI], DH          |
00467DBA | 74 0C         | JE      00467DC8                    |
00467DBC | D0C6          | ROL     DH, 1                       |
00467DBE | 83DE 00       | SBB     ESI, 0                      |
00467DC1 | FEC8          | DEC     AL                          |
00467DC3 | 75 F3         | JNZ     00467DB8                    |
00467DC5 | 5E            | POP     ESI                         |
00467DC6 | F8            | CLC                                 |
00467DC7 | C3            | RETN                                |
00467DC8 | 0836          | OR      BYTE PTR [ESI], DH          |
00467DCA | 53            | PUSH    EBX                         |
00467DCB | B6 80         | MOV     DH, 80                      |
00467DCD | 8B35 300F4C00 | MOV     ESI, DWORD PTR [4C0F30]     |
00467DD3 | 8B1D 360F4C00 | MOV     EBX, DWORD PTR [4C0F36]     |
00467DD9 | 8436          | TEST    BYTE PTR [ESI], DH          |
00467DDB | 75 03         | JNZ     00467DE0                    |
00467DDD | 43            | INC     EBX                         |
00467DDE | EB 2C         | JMP     00467E0C                    |
00467DE0 | 8A03          | MOV     AL, BYTE PTR [EBX]          |
00467DE2 | 66:25 FF00    | AND     AX, FF                      |
00467DE6 | 75 22         | JNZ     00467E0A                    |
00467DE8 | 8BC7          | MOV     EAX, EDI                    |
00467DEA | 2BC3          | SUB     EAX, EBX                    |
00467DEC | 3D 00010000   | CMP     EAX, 100                    |
00467DF1 | 73 22         | JNB     00467E15                    |
00467DF3 | 8803          | MOV     BYTE PTR [EBX], AL          |
00467DF5 | FECA          | DEC     DL                          |
00467DF7 | 74 20         | JE      00467E19                    |
00467DF9 | C607 00       | MOV     BYTE PTR [EDI], 0           |
00467DFC | 47            | INC     EDI                         |
00467DFD | D0CE          | ROR     DH, 1                       |
00467DFF | 83D6 00       | ADC     ESI, 0                      |
00467E02 | 8AC6          | MOV     AL, DH                      |
00467E04 | F6D0          | NOT     AL                          |
00467E06 | 2006          | AND     BYTE PTR [ESI], AL          |
00467E08 | EB EB         | JMP     00467DF5                    |
00467E0A | 03D8          | ADD     EBX, EAX                    |
00467E0C | D0CE          | ROR     DH, 1                       |
00467E0E | 83D6 00       | ADC     ESI, 0                      |
00467E11 | FECA          | DEC     DL                          |
00467E13 | 75 C4         | JNZ     00467DD9                    |
00467E15 | 5B            | POP     EBX                         |
00467E16 | 5E            | POP     ESI                         |
00467E17 | F9            | STC                                 |
00467E18 | C3            | RETN                                |
00467E19 | 5B            | POP     EBX                         |
00467E1A | 43            | INC     EBX                         |
00467E1B | FEC9          | DEC     CL                          |
00467E1D | 75 05         | JNZ     00467E24                    |
00467E1F | E9 67FFFFFF   | JMP     00467D8B                    |
00467E24 | 382B          | CMP     BYTE PTR [EBX], CH          |
00467E26 | 75 F2         | JNZ     00467E1A                    |
00467E28 | E9 78FFFFFF   | JMP     00467DA5                    |
Decomp3

Code: [Select]

00467E2D | 8BCB            | MOV     ECX, EBX                    |
00467E2F | 0FB683 3A0F4C00 | MOVZX   EAX, BYTE PTR [EBX+4C0F3A]  |
00467E36 | 84C0            | TEST    AL, AL                      |
00467E38 | 75 33           | JNZ     00467E6D                    |
00467E3A | B9 00000000     | MOV     ECX, 0                      |
00467E3F | 8416            | TEST    BYTE PTR [ESI], DL          |
00467E41 | 74 09           | JE      00467E4C                    |
00467E43 | FEC1            | INC     CL                          |
00467E45 | D0CA            | ROR     DL, 1                       |
00467E47 | 83D6 00         | ADC     ESI, 0                      |
00467E4A | EB F3           | JMP     00467E3F                    |
00467E4C | D0CA            | ROR     DL, 1                       |
00467E4E | 83D6 00         | ADC     ESI, 0                      |
00467E51 | 33C0            | XOR     EAX, EAX                    |
00467E53 | 84C9            | TEST    CL, CL                      |
00467E55 | 74 15           | JE      00467E6C                    |
00467E57 | 40              | INC     EAX                         |
00467E58 | 8A2E            | MOV     CH, BYTE PTR [ESI]          |
00467E5A | 22EA            | AND     CH, DL                      |
00467E5C | 80C5 FF         | ADD     CH, FF                      |
00467E5F | 66:D1D0         | RCL     AX, 1                       |
00467E62 | D0CA            | ROR     DL, 1                       |
00467E64 | 83D6 00         | ADC     ESI, 0                      |
00467E67 | FEC9            | DEC     CL                          |
00467E69 | 75 ED           | JNZ     00467E58                    |
00467E6B | 48              | DEC     EAX                         |
00467E6C | C3              | RETN                                |
00467E6D | 03D9            | ADD     EBX, ECX                    |
00467E6F | D1E3            | SHL     EBX, 1                      |
00467E71 | 8B9B 3E0F4C00   | MOV     EBX, DWORD PTR [EBX+4C0F3E] |
00467E77 | 8416            | TEST    BYTE PTR [ESI], DL          |
00467E79 | 75 03           | JNZ     00467E7E                    |
00467E7B | 43              | INC     EBX                         |
00467E7C | EB 05           | JMP     00467E83                    |
00467E7E | 0FB603          | MOVZX   EAX, BYTE PTR [EBX]         |
00467E81 | 03D8            | ADD     EBX, EAX                    |
00467E83 | D0CA            | ROR     DL, 1                       |
00467E85 | 83D6 00         | ADC     ESI, 0                      |
00467E88 | 803B 00         | CMP     BYTE PTR [EBX], 0           |
00467E8B | 75 EA           | JNZ     00467E77                    |
00467E8D | 43              | INC     EBX                         |
00467E8E | 8A0B            | MOV     CL, BYTE PTR [EBX]          |
00467E90 | 80F9 02         | CMP     CL, 2                       |
00467E93 | 72 1B           | JB      00467EB0                    |
00467E95 | FEC9            | DEC     CL                          |
00467E97 | B8 01000000     | MOV     EAX, 1                      |
00467E9C | 8A2E            | MOV     CH, BYTE PTR [ESI]          |
00467E9E | 22EA            | AND     CH, DL                      |
00467EA0 | 80C5 FF         | ADD     CH, FF                      |
00467EA3 | 66:D1D0         | RCL     AX, 1                       |
00467EA6 | D0CA            | ROR     DL, 1                       |
00467EA8 | 83D6 00         | ADC     ESI, 0                      |
00467EAB | FEC9            | DEC     CL                          |
00467EAD | 75 ED           | JNZ     00467E9C                    |
00467EAF | C3              | RETN                                |
00467EB0 | 0FB6C1          | MOVZX   EAX, CL                     |
00467EB3 | C3              | RETN                                |

[GuyPerfect]

Ah, the things I do for lem.

The assembly here was definitely done by hand, and it's heavily spaghettified. I think the most reliable and portable way to implement it is to make a sort of miniature x86 emulator to process the bytecode. This makes it so we won't have to pull out our hair just to get the decompression working, and the code can still be moved to other languages and architectures.

[ccexplore]

Hey ccexplore, since you've already located it, would you be so kind as to post the EXE you're using and the address of the bitmap decompression routine? I'd like to disassemble it to see what it's doing.

You caught me at a bad time, I was work-swamped for Friday and away for all of Saturday.  But looks like you managed just fine anyway. http://www.lemmingsforums.com/Smileys/lemmings/winktounge.gif" alt=";P" title="Wink-Tongue" class="smiley" />

I think the most reliable and portable way to implement it is to make a sort of miniature x86 emulator to process the bytecode.

I guess that would be a more portable approach, albeit seems like just as much work as deciphering the decompression?

My plan was to take a version of the game EXE (the demo version might be best as it doesn't require CD-ROM drive, assuming there aren't any changes to decompression between demo and non-demo), and just hack it so that instead of running the game, we short-circuit it into just decompressing some data we set up in memory.  An approach like this:

1) somewhere near the start of the game (preferably before the DirectX video mode switch, and not too early as to avoid skipping any potential necessary initialization of C runtime etc.), have it call our own DLL function.

2) The DLL function handles user input, and loads the user-specified data to be decompressed into some memory buffer.  It then jumps back into the point in the game EXE's code where, normally, it's just after the game loads something from BOX to be decompressed.  Except we've set things up for the code to process our data instead.

3) At the point further down in the game EXE's code, where it finishes decompression and is prepping to return the data, we call our own DLL function again, passing in things such as size of decompressed data and pointer to it.  The DLL function handles user input and saves the decompressed data to wherever the user wants, then calls ExitProcess() to shut everything down.

=============

Below's what I had jotted/copied down earlier in the week to help with above approach (based on my own copy of game EXE, non-demo):

Code: [Select]

0045015a 55              push    ebp
0045015b 8bec            mov     ebp,esp
0045015d 6aff            push    0FFFFFFFFh
0045015f 687ccb4a00      push    offset Lemmings_Revolution+0xacb7c (004acb7c)
00450164 64a100000000    mov     eax,dword ptr fs:[00000000h]
0045016a 50              push    eax
0045016b 64892500000000  mov     dword ptr fs:[0],esp
00450172 81ec5c010000    sub     esp,15Ch
<snip>
004501ea 8985a4feffff    mov     dword ptr [ebp-15Ch],eax
004501f0 8b9598feffff    mov     edx,dword ptr [ebp-168h]
004501f6 8b85a4feffff    mov     eax,dword ptr [ebp-15Ch]
004501fc 894204          mov     dword ptr [edx+4],eax
004501ff 8b8d98feffff    mov     ecx,dword ptr [ebp-168h]
00450205 8b11            mov     edx,dword ptr [ecx]
00450207 52              push    edx
00450208 8b8598feffff    mov     eax,dword ptr [ebp-168h]
0045020e 8b4804          mov     ecx,dword ptr [eax+4]
00450211 51              push    ecx
00450212 8d8dbcfeffff    lea     ecx,[ebp-144h]
00450218 e893b3feff      call    Lemmings_Revolution+0x3b5b0 (0043b5b0)
0045021d 8d8dbcfeffff    lea     ecx,[ebp-144h]
00450223 e80ae60200      call    Lemmings_Revolution+0x7e832 (0047e832) // load from BOX file?

// at this point, [ebp-168h] = address to an 8-byte struct {UInt32 numBytes; Byte *ptrData};
// [[ebp-168h]+4] = address to compressed data

00450228 8b9598feffff    mov     edx,dword ptr [ebp-168h]
0045022e 8b4204          mov     eax,dword ptr [edx+4]
00450231 33c9            xor     ecx,ecx
00450233 8a08            mov     cl,byte ptr [eax]
00450235 83f942          cmp     ecx,42h  // 'B'
00450238 752a            jne     Lemmings_Revolution+0x50264 (00450264)
0045023a 8b9598feffff    mov     edx,dword ptr [ebp-168h]
00450240 8b4204          mov     eax,dword ptr [edx+4]
00450243 33c9            xor     ecx,ecx
00450245 8a4801          mov     cl,byte ptr [eax+1]
00450248 83f94d          cmp     ecx,4Dh  // 'M'
0045024b 7517            jne     Lemmings_Revolution+0x50264 (00450264)
0045024d c745fcffffffff  mov     dword ptr [ebp-4],0FFFFFFFFh
00450254 8d8dbcfeffff    lea     ecx,[ebp-144h]
0045025a e8b9d90200      call    Lemmings_Revolution+0x7dc18 (0047dc18)
0045025f e933020000      jmp     Lemmings_Revolution+0x50497 (00450497)
00450264 8b9598feffff    mov     edx,dword ptr [ebp-168h]
<snip>
00450427 8b8db0feffff    mov     ecx,dword ptr [ebp-150h]
0045042d 8b55f0          mov     edx,dword ptr [ebp-10h]
00450430 8d440afb        lea     eax,[edx+ecx-5]
00450434 8945f0          mov     dword ptr [ebp-10h],eax
00450437 8b8db8feffff    mov     ecx,dword ptr [ebp-148h]
0045043d 038da8feffff    add     ecx,dword ptr [ebp-158h]
00450443 898db8feffff    mov     dword ptr [ebp-148h],ecx
00450449 e9edfeffff      jmp     Lemmings_Revolution+0x5033b (0045033b)

// when we reach 45044e, [ebp-14c] = address to decompressed data,
// [[ebp-168h]] = size of decompressed data

0045044e 8b9598feffff    mov     edx,dword ptr [ebp-168h]

[GuyPerfect]

That looks like the code I was picking through yesterday. By the time that function returns, [EBP-14C] contains the address of the decompressed bitmap, copied from [[EBP-168]+4].

I just woke up to a decompressed bitmap in Skype, so I'll have to wait for my associate to show up so he can tell me how he did it. O-:


EDIT:
For what it's worth, I don't like the idea of hijacking the Lemmings EXE to make it do decompression for us. I like to keep my utilities cross-platform when possible, and I prefer to make general things like archive managers in Java to make sure nigh-on everybody can use it. Restricting support to 32-bit x86 code isn't really the best way to achieve that goal.


EDIT2:
Looks like all he did was execute the code I posted. At least now we know for sure it works. (-:

[GuyPerfect]

Well, the other guy was able to point out that the code reads the input data one bit at a time, and that the uncompressed "BM" file identifier is visible in the data if you shift it a few times. Looking at the data myself, I was able to see that all the literal byte values for the file we're working with (^OUT.BMP) are in fact in the data, just not always on a byte boundary. Strings of repeated bytes are encoded differently, which reeks of LZ77 or one of its variants.

I'm still investigating, but starting at offset 00000006 in the file, the following bit strings are known:

Code: [Select]

No output:
0010011000110011001100110100001100000100000000000110101101010000011001010110011100110010001000110111001110001
First byte of output:
01000010 01001101 11110110 00001001 00000000    42 4D F6 09 00
11000111100010                                  (Encoded) 00 00 00 00 00 - Distance 1 Length 5
00110110                                        36
100111                                          (Encoded) 00 00 00 - Distance 4 or 7, Length 3
00101000                                        28
101000100111001010                              (Encoded) 00 00 00 - Distance 6 or 11, Length 3
00011010                                        1A
100111001010001000001001110010111               (Encoded) 00 00 00 - Distance 6 or 14, Length 3
00000001 00000000 00011000                      01 00 18
11001111111010000011111000001111100111010110    (Encoded) 00 * 40d - Distance... uh... Probably at least two distance/length pairs here.
00100100 00101100 00111000                      24 2C 38...