3D Lemmings file formats

[ccexplore]

Ok, I started off at the end of the log since presumably the log ends at the point where the checksum value is written to memory.  Based on that, tell me if what I said below tracks with the savegame data being processed at the time:

Code Select Expand

1E58:0000745F  push fs                                                EAX:00000000 EBX:00001600 ECX:00000000 EDX:00000007 ESI:00000020 EDI:000003EE EBP:08100014 ESP:000007EE DS:1088 ES:1088 FS:6546 GS:2658 SS:25D7 CF:0 ZF:0 SF:0 OF:0 AF:0 PF:1 IF:1
1E58:00007461  mov  fs,[3D00]                  ds:[3D00]=6546         EAX:00000000 EBX:00001600 ECX:00000000 EDX:00000007 ESI:00000020 EDI:000003EE EBP:08100014 ESP:000007EC DS:1088 ES:1088 FS:6546 GS:2658 SS:25D7 CF:0 ZF:0 SF:0 OF:0 AF:0 PF:1 IF:1
1E58:00007465  mov  di,0002                                           EAX:00000000 EBX:00001600 ECX:00000000 EDX:00000007 ESI:00000020 EDI:000003EE EBP:08100014 ESP:000007EC DS:1088 ES:1088 FS:6546 GS:2658 SS:25D7 CF:0 ZF:0 SF:0 OF:0 AF:0 PF:1 IF:1
1E58:00007468  mov  cx,0742                                           EAX:00000000 EBX:00001600 ECX:00000000 EDX:00000007 ESI:00000020 EDI:00000002 EBP:08100014 ESP:000007EC DS:1088 ES:1088 FS:6546 GS:2658 SS:25D7 CF:0 ZF:0 SF:0 OF:0 AF:0 PF:1 IF:1
1E58:0000746B  xor  ax,ax                                             EAX:00000000 EBX:00001600 ECX:00000742 EDX:00000007 ESI:00000020 EDI:00000002 EBP:08100014 ESP:000007EC DS:1088 ES:1088 FS:6546 GS:2658 SS:25D7 CF:0 ZF:0 SF:0 OF:0 AF:0 PF:1 IF:1

1E58:0000746D  add  ax,fs:[di]                 fs:[0002]=5551         EAX:00000000 EBX:00001600 ECX:00000742 EDX:00000007 ESI:00000020 EDI:00000002 EBP:08100014 ESP:000007EC DS:1088 ES:1088 FS:6546 GS:2658 SS:25D7 CF:0 ZF:1 SF:0 OF:0 AF:0 PF:1 IF:1
1E58:00007470  ror  ax,03                                             EAX:00005551 EBX:00001600 ECX:00000742 EDX:00000007 ESI:00000020 EDI:00000002 EBP:08100014 ESP:000007EC DS:1088 ES:1088 FS:6546 GS:2658 SS:25D7 CF:0 ZF:0 SF:0 OF:0 AF:0 PF:0 IF:1
1E58:00007473  xor  ax,cx                                             EAX:00002AAA EBX:00001600 ECX:00000742 EDX:00000007 ESI:00000020 EDI:00000002 EBP:08100014 ESP:000007EC DS:1088 ES:1088 FS:6546 GS:2658 SS:25D7 CF:0 ZF:0 SF:0 OF:0 AF:0 PF:0 IF:1
1E58:00007475  add  di,0002                                           EAX:00002DE8 EBX:00001600 ECX:00000742 EDX:00000007 ESI:00000020 EDI:00000002 EBP:08100014 ESP:000007EC DS:1088 ES:1088 FS:6546 GS:2658 SS:25D7 CF:0 ZF:0 SF:0 OF:0 AF:0 PF:1 IF:1
1E58:00007478  loop 0000746D                                          EAX:00002DE8 EBX:00001600 ECX:00000742 EDX:00000007 ESI:00000020 EDI:00000004 EBP:08100014 ESP:000007EC DS:1088 ES:1088 FS:6546 GS:2658 SS:25D7 CF:0 ZF:0 SF:0 OF:0 AF:0 PF:0 IF:1

1E58:0000747A  mov  fs:[0000],ax               fs:[0000]=6313         EAX:00006DF2 EBX:00001600 ECX:00000000 EDX:00000007 ESI:00000020 EDI:00000E86 EBP:08100014 ESP:000007EC DS:1088 ES:1088 FS:6546 GS:2658 SS:25D7 CF:0 ZF:0 SF:0 OF:0 AF:0 PF:0 IF:1

1) So the checksum in hexadecimal is 6313, ie. first byte (hex) is 13 and second byte is 63?
2) In the loop, according to the logs the following values were the first few processed into the checksum calculation:

Code Select Expand

fs:[0002]=5551
fs:[0004]=4441
fs:[0006]=4F43
fs:[0008]=4552
fs:[000A]=0000

Translating to individual bytes, they would be (in hex):

51 55 41 44 43 4F 52 45 00 00

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

If above tracks with the savegame data, the next step is simply to translate the above calculation (from 1E58:00007465 to 1E58:00007478) from assembly to some pseudolanguage which you can understand well enough to implement yourself.

[namida]

Those are indeed the first 10 bytes (excluding the checksum) of the save file data. Excluding the 2-byte checksum, the entire size of the save file is 0x0E85 (3717) bytes - as far as I can tell, this never varies, although I don't know for sure that every byte is used.

Regarding pseudocode: I understand the basic bitwise operations (eg. AND, OR, XOR, NOT, bitshifts), but not the more advanced stuff like... I think "bit rotate" was one I heard of? If the pseudocode resembles any of BASIC, Pascal or C#, I should be able to understand it. Even if not, it's all pretty similar really, so I should still be able to make sense of it.

[ccexplore]

Yeah, ROR is bitwise rotate right.  Anyway, here's pseudocode for above:

Code Select Expand

count = 1858
checksum = 0

do
   checksum = checksum + <next 2 bytes read as a 16-bit little-endian word>
   (equivalently:  checksum = checksum + <next byte> + <next next byte> * 256)
   checksum = checksum AND 65535   (ie. keep only lower 16 bits)
     
   checksum_last3bits = checksum AND 7
   checksum_shifted3bitsright = checksum div 8  (integer division dropping remainder, so 7 div 8 = 0, 8 div 8 = 1, 9 div 8 = 1)
   checksum_rotatelast3bitsintofirst3bits = checksum_last3bits * 8192
   checksum = checksum_shifted3bitsright OR checksum_rotatelast3bitsintofirst3bits

   checksum = checksum XOR count
   count = count - 1
while (count > 0)

The business in the middle is implementing the bitwise rotate with more commonly supported bitwise operators in high-level languages.  In case bitwise shifts are not available, I did those above using integer division and multiplication instead, you're welcome to just use shifts if they are available in your language (right shift by 3, and left shift by 13).

Based on the code, it expects 3716 bytes after the 2-byte checksum.  Maybe it's an off-by-1 error that the file size (excluding checksum) is 3717 rather than 3716?  The checksum algorithm is hardcoded to process exactly 3716 bytes.

[edit: fix missing the discarding all but lowest 16 bits after the add]

[namida]

Ah, so rotate is essentially just a bitwise shift that wraps around? That's simple enough then. I don't know if FreePascal supports it, but that's very easily replicated anyway.

EDIT: To clarify, when doing this step: "checksum = checksum + <next 2 bytes read as a 16-bit little-endian word>" - I assume we're immediately discarding anything above the 16th bit?

EDIT: Answer to the above question is "yes", and it works - I've successfully written code that repairs the checksum on a save file with an incorrect one. Next step, of course, is to actually generate the all-levels save file.

Here's the relevant Pascal code, in case that's more readable to anyone else reading this topic in the future. I've stripped out the parts that just relate to selecting the save file via an Open File dialog and actually opening / closing the file stream, I assume anyone who's familiar with Pascal will have little difficulty doing this.

Code Select Expand

var
  F: TFileStream;
  Buffer: array[0..3718] of Byte;

  Checksum: Word;
  RemainingCount: Word;
  WordPtr: ^Word;
[...]
        F.Read(Buffer[0], 3719);
        WordPtr := @Buffer[2];
        RemainingCount := 1858;
        Checksum := 0;

        while (RemainingCount > 0) do
        begin
          Checksum := (Checksum + WordPtr^) and $FFFF;
          Checksum := ((Checksum and $FFF8) shr 3) or ((Checksum and $0007) shl 13);
          Checksum := Checksum xor RemainingCount;
          Dec(RemainingCount);
          Inc(WordPtr);
        end;

        F.Position := 0;
        F.Write(Checksum, 2);

[ccexplore]

EDIT: To clarify, when doing this step: "checksum = checksum + <next 2 bytes read as a 16-bit little-endian word>" - I assume we're immediately discarding anything above the 16th bit?

Ah yes, sorry, I forgot about that part with the add, that the mathematical sum can have more bits than the operands.  The CPU is running in 16-bit mode so AX is only 16 bits, thus you only keep lower 16 bits of the sum.  Will edit my post above for clarity.

[namida]

With the one exception of BGRD.000, all files with a number as the extension in Lemmings 3D Winterland's GFX folder, are either unique to Lemmings 3D Winterland, or are identical to the same-name file in the full verison of Lemmings 3D.

This means that if you want to use the Lemmings 3D Winterland graphics in custom levels, you can safely just copy all the numbered files (except BGRD.000) into regular Lemmings 3D - and yes, they work! (I'll add the relevant presets in the next L3DEdit update, for now, you'd have to enter the numbers manually.)

No numbers in the 60s, 70s or 80s are used for graphic files by either regular or Winterland L3D.

[namida]

Here's a minorly interesting discovery: The 4th level in Lemmings 3D Winterland, instead of having the author's name in the comment field, has the text "EARLY TRICKY". I don't recall this level's solution, so I'm not sure off-hand how accurate that is, but it's what's there.

[namida]

And now an actual feature: The byte at 0x0157, known for the 0x01 flag marking the bottom of the level as slippery (if combined with the "bottom of level is solid" flag), also has an effect on the 0x02 flag - this makes land areas slippery. This single flag affects all land areas, I don't believe there's a way to set it on a per-land basis, though I'm going to investigate a bit more. (EDIT: If this is configurable per-land, it's not as part of the known land data, nor part of different flags in the 0x0157 byte.)

This is particularly interesting, as this is a feature that isn't used in any official levels, not even in Winterland. The levels that have ice at the bottom of them (Alpine Assault Course, Slippery Maze, Ski Jump, Snowy Islands and Arctic Obstical Course) all have a sea graphic that resembles ice, and use the 0x01 flag alongside "bottom of level is solid" - and don't contain any land areas full stop. (In fact - if you place land areas in a level with that combination of flags, but not the 0x02 "land is slippery" flag, the land areas are exempt from the slipperyness. Since none of the above levels have that flag set, land will be non-slippery on them.)

[namida]

It seems all but certain that the byte at 0x0140, known to have an effect on the amount of faces that can be rendered, is actually part of a two-byte value (0x013F-0x0140). It in turn seems that the range of accepted values here are 0x000F to 0x044C. All values outside this range are identical, but I'm not sure exactly how it's calculated - I thought it was "always 0x0300, or something close to it", but that might just be the cap rather than an exact value, due to what I've observed re: replay breakage (see below).

EDIT: Values above 0x0439 reduce the maximum number of lemmings you can have in the level (actually, even 0x0439 and a bit below probably does, but since you shouldn't have more than 80, and 80 lemmings works with a value of 0x0439...). At 0x044C, the limit is 65 lemmings.

It also seems at a glance - though I didn't check this too in-depth - that the rule "0x013E = 0x0140" in official levels, extends to this as a two-byte value, ie: in official levels, the two bytes 0x013D-0x013E, always have the same value as the two bytes 0x013F-0x0140. I still have not found any effect of changing 0x013D and/or 0x013E in a level, though.

I've also discovered, that replays working seems to depend on whether the value is above or below 0x02AC. Take this with a grain of salt, as this is based on testing a single level with a single replay. If a replay is recorded on a level where the value is 0x02AC or above, then the level is modified to make this value below 0x02AC (or vice versa), the replay breaks. This explains the replay breakage I saw with L3DEdit - all were in cases where I modified a level created with an old version of L3DEdit, using a newer version. Older versions left 0x0000 in these bytes, while newer ones write 0x0400 (which will be changed to 0x044C 0x0439 in the future, if I don't find any replay breakage or other negative side effects of such a change). EDIT: Based on further testing, there seems to be nothing special about 0x02AC outside of the context of that particular level. I've seen breakage on a different level when changing from 0x0400 to 0x0439. Assume any change to this value can break replays.

[namida]

On further investigation, it appears any change whatsoever to 0x013E can break replays (I had one break when changing a level from 0x0400 to 0x0439) - so I'll have to consider what's more important, pushing the limit very slightly further (and this is on the order of maybe 10 or so extra blocks, I believe), or not breaking replays (which to be fair, there aren't all that many of yet).

Of course, Option C is "preserve existing value for existing levels unless the user specifically asks to change it, use 0x0439 for any new levels"... I might go with that one.

[namida]

It appears the interaction between the face render limit and the lemming count is not as straightforward as I thought. I've had a level where, with a face render limit of 0x0439, only 78 lemmings were allowed to spawn. Additionally, decreasing this to 0x0437 - which I would've expected to allow 80 lemmings again - only allowed 79. This is on a level that previously worked fine with 80 lemmings @ 0x0439, and has less blocks now - but a couple more objects, and lots of small lands instead of one large one.

Given this, I'll likely leave L3DEdit's default at 0x0400 (1024), which I have never seen cause problems, but with that being said the next update allows editing this value anyway.

[namida]

I've started a TCRF page for Lemmings 3D PC version, and put up some of the most interesting finds there. Would be great if others could help complete it.

[ccexplore]

Hmm, really, no TCRF page for DOS Lemmings 1? I'm not sure but I feel like I remember seeing some hidden text in the game's EXE as well as in adlib.dat.  Maybe I'll start the page if I can confirm.  If nothing else, there is at least that one unused trap in the blue Crystal style that we all know about.  Oh, and all those flag objects across all 5 styles that are unused due to no 2-player mode on DOS.

[ccexplore]

Hmm, really, no TCRF page for DOS Lemmings 1?

Alright, I went ahead and created that page now.  I didn't realize how much of a pain it is to register and then create the page from scratch, maybe that's why no one bothered.  I hope to find more to add there soon.

[namida]

TITLE.MHC's format isn't documented anywhere.

Code Select Expand

No header. File immediately begins with first cell.

CELL STRUCTURE:
0x00 ~ 0x01 -- Size of cell data (including these bytes)
0x02 ~      -- Image data

Image data is usual format, except any instance of 00 is repeated a number of times indicated by the following byte. If the quantity is 00, the number of times is "until the end of the current line".

First attachment is L3D's TITLE.MHC file, second attachment is Winterland's.