Author Topic: 3D Lemmings file formats  (Read 6827 times)

0 Members and 1 Guest are viewing this topic.

Offline ccexplore

  • Administrator
  • Posts: 4882
    • View Profile
Re: 3D Lemmings file formats
« Reply #45 on: June 24, 2019, 09:58:24 pm »
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]
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]
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.

Offline namida

  • Administrator
  • Posts: 8892
    • View Profile
    • NeoLemmix Website
Re: 3D Lemmings file formats
« Reply #46 on: June 24, 2019, 10:00:34 pm »
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.
My released level packs:
Lemmings Plus Series | Doomsday Lemmings

Offline ccexplore

  • Administrator
  • Posts: 4882
    • View Profile
Re: 3D Lemmings file formats
« Reply #47 on: June 24, 2019, 10:19:21 pm »
Yeah, ROR is bitwise rotate right.  Anyway, here's pseudocode for above:

Code: [Select]
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]
« Last Edit: June 24, 2019, 11:22:42 pm by ccexplore »

Offline namida

  • Administrator
  • Posts: 8892
    • View Profile
    • NeoLemmix Website
Re: 3D Lemmings file formats
« Reply #48 on: June 24, 2019, 10:21:49 pm »
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]
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);
« Last Edit: June 24, 2019, 10:37:09 pm by namida »
My released level packs:
Lemmings Plus Series | Doomsday Lemmings

Offline ccexplore

  • Administrator
  • Posts: 4882
    • View Profile
Re: 3D Lemmings file formats
« Reply #49 on: June 24, 2019, 11:21:37 pm »
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.

Offline namida

  • Administrator
  • Posts: 8892
    • View Profile
    • NeoLemmix Website
Re: 3D Lemmings file formats
« Reply #50 on: July 09, 2019, 07:35:58 am »
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.
My released level packs:
Lemmings Plus Series | Doomsday Lemmings

Offline namida

  • Administrator
  • Posts: 8892
    • View Profile
    • NeoLemmix Website
Re: 3D Lemmings file formats
« Reply #51 on: July 10, 2019, 01:05:12 am »
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.
My released level packs:
Lemmings Plus Series | Doomsday Lemmings

Offline namida

  • Administrator
  • Posts: 8892
    • View Profile
    • NeoLemmix Website
Re: 3D Lemmings file formats
« Reply #52 on: July 11, 2019, 12:09:30 am »
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.)
« Last Edit: July 11, 2019, 02:44:55 am by namida »
My released level packs:
Lemmings Plus Series | Doomsday Lemmings