Author Topic: Hacking Lemmings Revolution  (Read 47382 times)

0 Members and 1 Guest are viewing this topic.

Offline GuyPerfect

  • Posts: 363
    • View Profile
Re: Hacking Lemmings Revolution
« Reply #60 on: April 30, 2012, 03:06:13 AM »
Still don't know the details of the algorithm in whole, but still looking into it.

We made a C program that can decode single-chunk compressed .bmp files from Lemmings Revolution using the code from its EXE file. It requires an x86 architecture to work, but that's how it goes.

Usage: lrdecomp <inputfile> <outputfile>

A compiled version is attached to this post, while the source code is this:

Code: [Select]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define PRG_SIZE    609
#define PRG_BASE    0x00467C53

// Codewalker's hax
char staticmemory[0x100000];
int len;
char *outbuf;
void *decp1dst = (void*)0x00467c53;
unsigned char *out_bmp;

// The mystery program data
static unsigned char PRG_ROM[PRG_SIZE] = {
0x51,0x57,0x8D,0x3D,0x28,0x12,0x4C,0x00,0x89,0x3D,0x2C,0x0F,0x4C,0x00,0x83,0xC7,
0x11,0x89,0x3D,0x30,0x0F,0x4C,0x00,0x83,0xC7,0x03,0x33,0xDB,0xE8,0x83,0x00,0x00,
0x00,0x72,0x16,0xBB,0x01,0x00,0x00,0x00,0xE8,0x77,0x00,0x00,0x00,0x72,0x0A,0xBB,
0x02,0x00,0x00,0x00,0xE8,0x6B,0x00,0x00,0x00,0x5F,0x59,0x73,0x02,0xF9,0xC3,0x49,
0xB2,0x80,0xFC,0x51,0x33,0xDB,0xE8,0x8F,0x01,0x00,0x00,0x85,0xC0,0x74,0x21,0x8B,
0xC8,0x8B,0xD8,0xB0,0x01,0x8A,0x26,0x22,0xE2,0xD0,0xCA,0x83,0xD6,0x00,0x80,0xC4,
0xFF,0xD0,0xD0,0x73,0xF0,0xAA,0xE2,0xEB,0x8B,0xC3,0x59,0x2B,0xC8,0x72,0x2E,0x51,
0xBB,0x01,0x00,0x00,0x00,0xE8,0x60,0x01,0x00,0x00,0x50,0xBB,0x02,0x00,0x00,0x00,
0xE8,0x55,0x01,0x00,0x00,0x8B,0xDE,0x8B,0xF7,0xF9,0x1B,0xF0,0x59,0x83,0xC1,0x02,
0x8B,0xC1,0xF3,0xA4,0x8B,0xF3,0x59,0x2B,0xC8,0x72,0x02,0xEB,0xA6,0xD0,0xC2,0xF5,
0x83,0xD6,0x00,0xC3,0x8A,0x06,0x46,0xA8,0x0F,0x75,0x0A,0x88,0x83,0x3A,0x0F,0x4C,
0x00,0x3C,0x01,0xF5,0xC3,0x53,0x57,0x8B,0x3D,0x2C,0x0F,0x4C,0x00,0x8A,0xF8,0x66,
0x83,0xE0,0x0F,0x04,0x02,0x8A,0xE8,0xB1,0x04,0xD2,0xEF,0x38,0xFC,0x73,0x02,0x8A,
0xE7,0x88,0x3F,0x47,0xFE,0xCD,0x74,0x15,0x8A,0x1E,0x46,0x8A,0xFB,0x80,0xE3,0x0F,
0x38,0xDC,0x73,0x02,0x8A,0xE3,0x88,0x1F,0x47,0xFE,0xCD,0x75,0xDC,0xA2,0x34,0x0F,
0x4C,0x00,0x88,0x25,0x35,0x0F,0x4C,0x00,0x5F,0x5B,0x56,0x8B,0xF3,0x88,0x86,0x3A,
0x0F,0x4C,0x00,0xC1,0xE6,0x02,0x89,0xBE,0x3E,0x0F,0x4C,0x00,0x89,0x3D,0x36,0x0F,
0x4C,0x00,0xC6,0x07,0x00,0x47,0x8B,0x35,0x30,0x0F,0x4C,0x00,0xC6,0x06,0x00,0xB6,
0x80,0xB5,0x01,0x8B,0x1D,0x2C,0x0F,0x4C,0x00,0x8A,0x0D,0x34,0x0F,0x4C,0x00,0x38,
0x2B,0x74,0x1F,0x43,0xFE,0xC9,0x75,0xF7,0x88,0x0F,0x47,0xD0,0xCE,0x83,0xD6,0x00,
0x8A,0xC6,0xF6,0xD0,0x20,0x06,0xFE,0xC5,0x38,0x2D,0x35,0x0F,0x4C,0x00,0x73,0xD3,
0xEB,0x20,0x8A,0x25,0x34,0x0F,0x4C,0x00,0x2A,0xE1,0xB0,0x00,0x66,0x89,0x07,0x47,
0x47,0x8A,0xD5,0x8A,0xC5,0x84,0x36,0x74,0x0C,0xD0,0xC6,0x83,0xDE,0x00,0xFE,0xC8,
0x75,0xF3,0x5E,0xF8,0xC3,0x08,0x36,0x53,0xB6,0x80,0x8B,0x35,0x30,0x0F,0x4C,0x00,
0x8B,0x1D,0x36,0x0F,0x4C,0x00,0x84,0x36,0x75,0x03,0x43,0xEB,0x2C,0x8A,0x03,0x66,
0x25,0xFF,0x00,0x75,0x22,0x8B,0xC7,0x2B,0xC3,0x3D,0x00,0x01,0x00,0x00,0x73,0x22,
0x88,0x03,0xFE,0xCA,0x74,0x20,0xC6,0x07,0x00,0x47,0xD0,0xCE,0x83,0xD6,0x00,0x8A,
0xC6,0xF6,0xD0,0x20,0x06,0xEB,0xEB,0x03,0xD8,0xD0,0xCE,0x83,0xD6,0x00,0xFE,0xCA,
0x75,0xC4,0x5B,0x5E,0xF9,0xC3,0x5B,0x43,0xFE,0xC9,0x75,0x05,0xE9,0x67,0xFF,0xFF,
0xFF,0x38,0x2B,0x75,0xF2,0xE9,0x78,0xFF,0xFF,0xFF,0x8B,0xCB,0x0F,0xB6,0x83,0x3A,
0x0F,0x4C,0x00,0x84,0xC0,0x75,0x33,0xB9,0x00,0x00,0x00,0x00,0x84,0x16,0x74,0x09,
0xFE,0xC1,0xD0,0xCA,0x83,0xD6,0x00,0xEB,0xF3,0xD0,0xCA,0x83,0xD6,0x00,0x33,0xC0,
0x84,0xC9,0x74,0x15,0x40,0x8A,0x2E,0x22,0xEA,0x80,0xC5,0xFF,0x66,0xD1,0xD0,0xD0,
0xCA,0x83,0xD6,0x00,0xFE,0xC9,0x75,0xED,0x48,0xC3,0x03,0xD9,0xD1,0xE3,0x8B,0x9B,
0x3E,0x0F,0x4C,0x00,0x84,0x16,0x75,0x03,0x43,0xEB,0x05,0x0F,0xB6,0x03,0x03,0xD8,
0xD0,0xCA,0x83,0xD6,0x00,0x80,0x3B,0x00,0x75,0xEA,0x43,0x8A,0x0B,0x80,0xF9,0x02,
0x72,0x1B,0xFE,0xC9,0xB8,0x01,0x00,0x00,0x00,0x8A,0x2E,0x22,0xEA,0x80,0xC5,0xFF,
0x66,0xD1,0xD0,0xD0,0xCA,0x83,0xD6,0x00,0xFE,0xC9,0x75,0xED,0xC3,0x0F,0xB6,0xC1,
0xC3};

// Calculates the total unpacked size of a file and returns the length
int lrdGetSize(unsigned char *data, int size) {
    int chunks, packed, unpacked = 0, x, off = 1;

    // Error checking
    if (data == NULL || size < 6) return 0;

    // Get the number of chunks in the file
    chunks = (int) data[0];
    if (chunks < 1) return 0;

    // Read the unpacked sizes for all chunks
    for (x = 0; x < chunks; x++) {
        if (off + 4 > size) return 0;
        packed    = (int) data[off + 1] << 8 | (int) data[off];
        if (off + packed > size) return 0;
        unpacked += (int) data[off + 3] << 8 | (int) data[off + 2];
        off += packed;
    }

    return unpacked;
}

// Decompresses a Lemmings Revolution bitmap file
int lrdDecompress(unsigned char *src, int srclen,
                  unsigned char *dst, int dstlen) {

    // Error checking
    if (src == NULL || srclen < 6 || dst == NULL || dstlen < 1) return 1;

    //memset(staticmemory, 0, 0x100000);
    memcpy((void *) PRG_BASE, PRG_ROM, PRG_SIZE);

       out_bmp = src;
   outbuf = dst;
   len = (int) dstlen;
   memset(outbuf, 0, len);

   asm("movl _out_bmp, %esi\n"
      "add $6, %esi\n"
      "movl _outbuf, %edi\n"
      "movl _len, %ecx\n"
      "call *_decp1dst");

    return 0;
}

// Program entry point
int main(int argc, char **argv) {
    FILE *fPtr;
    int fLen, uLen;
    unsigned char *fData, *uData;

    if (argc != 3) {
        printf("Usage: %s <inputfile> <outputfile>\n", argv[0]);
        return 0;
    }

    fPtr = fopen(argv[1], "rb");
    if (fPtr == NULL) {
        printf("Could not open %s\n", argv[1]);
        return 1;
    }

    fseek(fPtr, 0, SEEK_END);
    fLen = ftell(fPtr);
    if (fLen < 6) {
        fclose(fPtr);
        printf("Invalid data in %s\n", argv[1]);
        return 1;
    }

    fData = malloc(fLen);
    fseek(fPtr, 0, SEEK_SET);
    uLen = fread(fData, 1, fLen, fPtr);
    fclose(fPtr);
    if (uLen != fLen) {
        printf("Could not read data from %s\n", argv[1]);
        return 1;
    }

    uLen = lrdGetSize(fData, fLen);
    if (!uLen) {
        free(fData);
        printf("Invalid data in %s\n", argv[1]);
        return 1;
    }

    printf("File size: %04X\n", uLen);
    uData = malloc(uLen);
    fLen = lrdDecompress(fData, fLen, uData, uLen);

    fPtr = fopen(argv[2], "wb");
    if (fPtr == NULL) {
        printf("Error writing %s\n", argv[2]);
    } else {
        fwrite(uData, 1, uLen, fPtr);
        fclose(fPtr);
        printf("Wrote %s\n", argv[2]);
    }

    free(fData);
    free(uData);
    return 0;
}

Offline GuyPerfect

  • Posts: 363
    • View Profile
Re: Hacking Lemmings Revolution
« Reply #61 on: April 30, 2012, 08:03:56 AM »
Okay, making some slow but tangible progress.

The first however many bytes of the compressed chunk initialize some state variables in static memory. How this happens and by what logic is unknown, as well as how many of them there are. What is known is that there are at least three in all cases, because Decomp2() is called 3 times to initialize the aforementioned state variables. The variables are located at 4C1228 (in the code that I posted, as well as in the kludgy C program in the previous post), and if the lower 4 bits of a byte are zero when Decomp2() is called, it will immediately return without altering the data in the variables.

The data stream itself is processed one bit at a time, pulling values for decompressing the data. The setup is fully suitable for chunked input, which appears to be the case with larger files anyway. I don't know all the specifics yet, but there's a catch: if the state variables are initialized, the exact size and format of the values becomes unknown. Only in files that don't initialize the state variables do we know the format of the data at this time.

The decoder alternates between states: first is raw data, and the other is distance/length pair. Every time data for one state is processed, the decoder flips to the other state.
  • Raw data reads one number from the data, which represents the number of 8-bit bytes to copy to the output.
  • Distance/length pair reads two numbers from the data: first for length, then for distance.
    • The value read for length gets 2 added implicitly after decoding.
    • The value read for distance gets 1 added implicitly after decoding.
The numbers themselves are stored in a variable-size data format:
  • Read bits for as long as they are 1
  • When a 0 is encountered, count how many 1s there were and read that many additional bits
  • The value of the number is the value of the 1s bits plus the value of the additional bits, both in high-to-low order
For example:
  • Bit sequence 11111010010
  • There are 5 contiguous 1s, which comes out to 31
  • There is a zero separating the two fields
  • The next 5 bits, 10010, comes out to 18
  • The value of the number is 31 + 18 = 49
It is worth noting that if the first bit in a number sequence is a 0, it effectively produces 0 as the result because there are no 1s on the left and no additional bits on the right. 0 + 0 = 0. This value is used in situations where multiple distance/length pairs need to exist back-to-back, because the decoder will flip into the raw data state after each one.
__________

Most of what I've been doing comes from TEXTURES\^WATER_GLOW.BMP from lemmings.box.

This is the compressed file as extracted from the BOX:
Code: [Select]
00000000  01 22 00 F6 00 04 00 00  00 CA 12 6F B0 06 50 DA
00000010  62 14 4C 40 8D 63 00 20  03 1A F5 3C 2C 72 CD A6
00000020  7F 3C A0

And this is the decompressed file:
Code: [Select]
00000000  42 4D F6 00 00 00 00 00  00 00 36 00 00 00 28 00
00000010  00 00 08 00 00 00 08 00  00 00 01 00 18 00 00 00
00000020  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00
00000030  00 00 00 00 00 00 E5 9B  4C E5 9B 4C E5 9B 4C E5
00000040  9B 4C E5 9B 4C E5 9B 4C  E5 9B 4C E5 9B 4C E5 9B
00000050  4C E5 9B 4C E5 9B 4C E5  9B 4C E5 9B 4C E5 9B 4C
00000060  E5 9B 4C E5 9B 4C E5 9B  4C E5 9B 4C E5 9B 4C E5
00000070  9B 4C E5 9B 4C E5 9B 4C  E5 9B 4C E5 9B 4C E5 9B
00000080  4C E5 9B 4C E5 9B 4C E5  9B 4C E5 9B 4C E5 9B 4C
00000090  E5 9B 4C E5 9B 4C E5 9B  4C E5 9B 4C E5 9B 4C E5
000000A0  9B 4C E5 9B 4C E5 9B 4C  E5 9B 4C E5 9B 4C E5 9B
000000B0  4C E5 9B 4C E5 9B 4C E5  9B 4C E5 9B 4C E5 9B 4C
000000C0  E5 9B 4C E5 9B 4C E5 9B  4C E5 9B 4C E5 9B 4C E5
000000D0  9B 4C E5 9B 4C E5 9B 4C  E5 9B 4C E5 9B 4C E5 9B
000000E0  4C E5 9B 4C E5 9B 4C E5  9B 4C E5 9B 4C E5 9B 4C
000000F0  E5 9B 4C E5 9B 4C

This, on the other hand, is the compressed file expressed in binary:
Code: [Select]
00000000  00000001 00100010 00000000 11110110
00000004  00000000 00000100 00000000 00000000
00000008  00000000 11001010 00010010 01101111
0000000C  10110000 00000110 01010000 11011010
00000010  01100010 00010100 01001100 01000000
00000014  10001101 01100011 00000000 00100000
00000018  00000011 00011010 11110101 00111100
0000001C  00101100 01110010 11001101 10100110
00000020  01111111 00111100 10100000

An analysis of the file is as follows:

File Header
  * 00000001                   Chunks      = 1
  * 00100010 00000000  ChunkSize = 0x0022
  * 11110110 00000000  DataSize    = 0x00F6
  * 00000100                   (Unknown) = 4

Stream Chunk Header
  * 00000000  These three bytes are all 0x00. Decomp2() is called once for each
  * 00000000  of them, and promptly returns because their lower 4 bits are all
  * 00000000  0. No data is written to 4C1228 for this file.

Begin output stream

11001 = 4 bytes
  * 01000010 = 42 = 'B'
  * 01001101 = 4D = 'M'
  * 11110110 = F6
  * 00000000 = 00

11001 = Length = 4 + (2) = 6
0 = Distance = 0 + (1) = 1
  * 00 00 00 00 00 00

100 = 1 byte
  * 00110110 = 36

100 = Length = 1 + (2) = 3
11000 = Distance = 3 + (1) = 4
  * 00 00 00

100 = Raw data, 1 byte
  * 00101000 = 28

100 = Length = 1 + (2) = 3
11000 = Distance = 3 + (1) = 4
  * 00 00 00

100 = 1 byte
  * 00001000 = 08

11010 = Length = 5 + (2) = 7
11000 = Distance = 3 + (1) = 4
  * 00 00 00 08 00 00 00

11000 = 3 bytes
  * 00000001 = 01
  * 00000000 = 00
  * 00011000 = 18

11010 = Length = 5 + (2) = 7
111101010 = Distance = 25 + (1) = 26
  * 00 00 00 00 00 00 00

0 = 0 bytes

111100001 = Length = 16 + (2) = 18
0 = Distance = 0 + (1) = 1
  * 00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00
     00 00

11000 = 3 bytes
  * 11100101 = E5
  * 10011011 = 9B
  * 01001100 = 4C

111111100111100 = Length = 187 + (2) = 189
101 = Distance = 2 + (1) = 3
  * E5 9B 4C E5 9B 4C... you get the idea

00000 = Spare bits at the end of the stream, padded onto the last byte

Offline GuyPerfect

  • Posts: 363
    • View Profile
Re: Hacking Lemmings Revolution
« Reply #62 on: April 30, 2012, 10:42:36 PM »
Crawling along, I still don't know exactly how the chunk header bits affect data input, but I at least know what values they represent now.

Indeed, there are at least 3 bytes at the beginning of every chunk. The lower 4 bits of these specifies a number of additional data units to read, where a value of 0 indicates there are no additional values. However, if the value is non-zero, then 2 is added to it to get the total number of units to read. Units are then read 4 bits each, starting with the high nibble of the current byte (the one that contained the count value), then the low nibble of the next byte and so-on until all of the specified units are read. If there is an even number of nibbles to read, the upper 4 bits of the last byte only exist as padding so that the next data begins on a byte boundary.

Decomp2() processes these nibble units, parsing them into bytes of their own and temporarily storing them at 4C1228 for further processing. As per the specification, there can be anywhere from 3 to 17 bytes written starting at that address. However, it's that "further processing" I'm still not clear on.

The first group of units affects how raw data byte count numbers are read from the stream. The second and third affect the distance/length numbers, presumably length for the second and distance for the third. I'll still need to verify that once I get the protocol down, but the magic 8 ball seems to think that's how it will end up.

Example:
  • Byte sequence 12 34 05 70 61 89
  • 12 = *2 = 4 nibbles for raw data: 1, 4, 3, 5, and then the 0 is junk
  • 70 = *0 = no nibbles for length data, so the 7 is junk
  • 61 = *1 = 3 nibbles for distance data: 6, 9, 8

Offline GuyPerfect

  • Posts: 363
    • View Profile
Re: Hacking Lemmings Revolution
« Reply #63 on: May 02, 2012, 12:23:40 AM »
Got it!

The nibbles prior to the encoded data stream are parsed in the method I described in detail in the previous post, so I won't review.

What those nibbles represent are A) values to be added to a binary tree and B) the depth within that tree where each value occurs.
__________

For the uninitiated, a binary tree consists of nodes, where each node is either a value or branches out to 2 more nodes. If a node branches out, it has two paths: 0 and 1. At the top of the tree is a single node, called the root node, which ALWAYS branches. The nodes it branches to are called child nodes and, to those nodes, the node that branched to them is their parent node.

A quick example:

Code: [Select]
Level 0      root
            0/  \1
Level 1     a    b
          0/ \1
Level 2   c   d

In this example, the root node branches into 0=a and 1=b. a in turn branches into 0=c and 1=d. b, c and d, however, do not branch. They are terminal nodes in this particular tree. a is the parent node of c and d, and root is the parent node of a and b.
__________

Imagine the list of nibbles as an array with 0 as the first index. The index of each nibble will find its way into the tree as a terminal node. The value of the nibble represents how many levels down into the tree that the index appears. If the value of a nibble is 0, then its index will not appear in the  tree.

So as an example from a file I was working with last night:

Nibbles:  4
Values:   2, 1, 3, 3
Indexes: 0, 1, 2, 3

As shown, the nibble at (for instance) index 2 is a 3, meaning that a 2 will appear in level 3 of the binary tree.

I tried to express the algorithm, but it was taking too long. So let's just process the example. The tree starts out in the following state:

Code: [Select]
Level 0    root
          0/  \1
Level 1   ?    ?

Nibbles: 2 1 3 3
Indexes: 0 1 2 3

It always starts on the 0 side and tries to fill in the question marks by looking for nibbles that have values equal to the current level of depth. We start at level 1, so it looks for a nibble with value 1. It finds one at index 1, so it writes that into the tree and marks the nibble as used. It now looks like this:

Code: [Select]
Level 0    root
          0/  \1
Level 1  (1)   ?

Nibbles: 2 X 3 3
Indexes: 0 1 2 3

When it tries to find a second nibble for level 1, it fails and turns that node into a branching node instead:

Code: [Select]
Level 0    root
          0/  \1
Level 1  (1)   @
             0/ \1
Level 2      ?   ?

Nibbles: 2 X 3 3
Indexes: 0 1 2 3

It finds a 2 to assign to the 0 side, but there isn't a 2 for the 1 side and it thus makes another branching node:

Code: [Select]
Level 0    root
          0/  \1
Level 1  (1)   @
             0/ \1
Level 2     (0)  @
               0/ \1
Level 3        ?   ?

Nibbles: X X 3 3
Indexes: 0 1 2 3

This time, it does have enough nibbles for the current level of depth, so it writes those both into the tree, which makes all of its nodes terminal:

Code: [Select]
Level 0    root
          0/  \1
Level 1  (1)   @
             0/ \1
Level 2     (0)  @
               0/ \1
Level 3       (2) (3)

Nibbles: X X X X
Indexes: 0 1 2 3
__________

As practice, here's another list of nibbles from another file:

3, 4, 3, 2, 3, 3, 3, 4

The output should look something like this if you did it correctly:

Code: [Select]
Level 0            root
             0/            \1
Level 1      @              @
           0/ \1        0/     \1
Level 2   (3)  @        @       @
             0/ \1    0/ \1   0/ \1
Level 3     (0) (2)  (4) (5) (6)  @
                                0/ \1
Level 4                        (1) (7)

Offline GuyPerfect

  • Posts: 363
    • View Profile
Re: Hacking Lemmings Revolution
« Reply #64 on: May 02, 2012, 12:34:43 AM »
The next part is important, so I didn't want it to get lost in the mess of illustrations up there.

As mentioned before, three binary trees are processed before decoding begins. The first is for raw byte counts, the second is for distance/length lengths and the third is for distance length distances. After those bytes are processed, the encoded input begins. If there are 0 nibbles to process for the current binary tree, then no binary tree is generated and instead, numbers are read directly from the input data using the format I described in an earlier post.

In the event a binary tree is present for the type of number that needs to be read, there's a small algorithm used to produce the final value:
  • Step down the binary tree one input bit at a time to locate a number
  • If the number is 0 or 1, use it
  • If the number is 2 or greater
    • Subtract 1 from the number
    • Read the resulting number additional bits from the input data
    • Process a number using the bits read, along with an additional 1 as the highest bit
For example, let's use that binary tree from the last post:

Code: [Select]
Level 0            root
             0/            \1
Level 1      @              @
           0/ \1        0/     \1
Level 2   (3)  @        @       @
             0/ \1    0/ \1   0/ \1
Level 3     (0) (2)  (4) (5) (6)  @
                                0/ \1
Level 4                        (1) (7)

And let's say our input bits are 1010011.
  • As we step down the binary tree, 1, 0, 1, we wind up at 5
  • 5 is >= 2, so we don't return it as-is
  • We subtract 1 to make 4
  • The next 4 bits in the data are 0011
  • We stick a 1 on the front, making 10011, or 19 in decimal, which is the number to use
Numbers read either from the data or from the binary tree are still subject to modification when processing distance/length pairs: namely, you still add 2 for length or 1 for distance depending on context.

Offline GuyPerfect

  • Posts: 363
    • View Profile
Re: Hacking Lemmings Revolution
« Reply #65 on: May 02, 2012, 01:42:16 AM »
Revisiting ^OUT.BMP from earlier, I can actually decode it now. (-: Sing along at home!


Partial input file (hex):
Code: [Select]
Source (hex)
00000000  01 36 08 36 0A 04 26 33  33 43 04 00 6B 50 65 67
00000010  32 23 73 8A 12 6F B0 48  06 3C 46 D3 94 51 39 43
00000020  53 94 41 39 70 10 01 8C  FE 83 E0 F9 D6 24 2C 38
00000030  97 B6 BA 5F 7D 9D 5B 7F  BB 64 8B CE 54 72 C6 46
00000040  5E A7 50 69 A1 53 67 92  36 47 6F 49 68 9D 5D 85
00000050  C4 53 73 C6 45 5C AC 35  48 81 36 49 85 23 30 56
00000060  05 07 0C E1 F7 9B 37 37  B0 7F 58 44 50 59 CE 2E
00000070  4E AB 3F 63 3F F3 FB 37  F7 F6 B7 6B FA 3A C7 C5
00000080  ...

Partial output file (hex):
Code: [Select]
00000000  42 4D F6 09 00 00 00 00  00 00 36 00 00 00 28 00
00000010  00 00 1A 00 00 00 20 00  00 00 01 00 18 00 00 00
00000020  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00
00000030  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00
00000040  00 00 00 00 00 24 2C 38  97 B6 BA 5F 7D 9D 5B 7F
00000050  BB 64 8B CE 54 72 C6 46  5E A7 50 69 A1 53 67 92
00000060  36 47 6F 49 68 9D 5D 85  C4 53 73 C6 45 5C AC 35
00000070  48 81 36 49 85 23 30 56  05 07 0C 00 00 00 00 00
00000080  ...

Partial input file (binary):
Code: [Select]
00000000 00000001 00110110 00001000 00110110
00000004 00001010 00000100 00100110 00110011
00000008 00110011 01000011 00000100 00000000
0000000C 01101011 01010000 01100101 01100111
00000010 00110010 00100011 01110011 10001010
00000014 00010010 01101111 10110000 01001000
00000018 00000110 00111100 01000110 11010011
0000001C 10010100 01010001 00111001 01000011
00000020 01010011 10010100 01000001 00111001
00000024 01110000 00010000 00000001 10001100
00000028 11111110 10000011 11100000 11111001
0000002C 11010110 00100100 00101100 00111000
00000030 10010111 10110110 10111010 01011111
00000034 01111101 10011101 01011011 01111111
00000038 10111011 01100100 10001011 11001110
0000003C 01010100 01110010 11000110 01000110
00000040 01011110 10100111 01010000 01101001
00000044 10100001 01010011 01100111 10010010
00000048 00110110 01000111 01101111 01001001
0000004C 01101000 10011101 01011101 10000101
00000050 11000100 01010011 01110011 11000110
00000054 01000101 01011100 10101100 00110101
00000058 01001000 10000001 00110110 01001001
0000005C 10000101 00100011 00110000 01010110
00000060 00000101 00000111 00001100 11100001
00000064 11110111 10011011 00110111 00110111
00000068 10110000 01111111 01011000 01000100
0000006C 01010000 01011001 11001110 00101110
00000070 01001110 10101011 00111111 01100011
00000074 00111111 11110011 11111011 00110111
00000078 11110111 11110110 10110111 01101011
0000007C 11111010 00111010 11000111 11000101
00000080 ...


File Header

00000001 = 1 chunk


Chunk Header

00110110 00001000 = Chunk size = 0x0836
00110110 00001010 = Data size  = 0x0A36
00000100                  = 4 (unknown)

Raw Binary Tree Header
0010[0110] = 6 + (2) = 8 nibbles = 2,
0011 0011  = 3, 3
0011 0011  = 3, 3
0100 0011  = 3, 4
0000 0100  = 4 (, padding)

Produces the following tree with nibbles 2 3 3 3 3 3 4 4:
Code: [Select]
Level 0            root
             0/            \1
Level 1      @              @
           0/ \1        0/     \1
Level 2   (0)  @        @       @
             0/ \1    0/ \1   0/ \1
Level 3     (1) (2)  (3) (4) (5)  @
                                0/ \1
Level 4                        (6) (7)

Length Binary Tree Haader
0000[0000] = 0 = No binary tree for Length

Distance Binary Tree Header
0110[1011] = 11 + (2) = 13 nibbles = 6,
0101 0000  = 0, 5
0110 0101  = 5, 6
0110 0111  = 7, 6
0011 0010  = 2, 3
0010 0011  = 3, 2
0111 0011  = 3, 7

Produces the following tree with nibbles 6 0 5 5 6 7 6 2 3 3 2 3 7:
Code: [Select]
Level 0          root
             0/        \1
Level 1      @          @
           0/ \1   0/       \1
Level 2   (7) (A)  @         @
                 0/ \1   0/     \1
Level 3         (8) (9) (B)      @
                            0/       \1
Level 4                     @         @
                          0/ \1   0/     \1
Level 5                  (2) (3)  @       @
                                0/ \1   0/ \1
Level 6                        (0) (4) (6)  @
                                          0/ \1
Level 7                                  (5) (C)


Begin Output Stream

100 (1)01 = 5 bytes
 * 01000010 = 42 = 'B'
 * 01001101 = 4D = 'M'
 * 11110110 = F6
 * 00001001 = 09
 * 00000000 = 00

11000 = Length 3 + (2) = 5
111100 = Distance 0 + (1) = 1
 * 00 00 00 00 00

010 = 1 byte
 * 00110110 = 36

100 = Length 1 + (2) = 3
11100 (1)1 = Distance = 3 + (1) = 4
 * 00 00 00

010 = 1 byte
 * 00101000 = 28

100 = Length 1 + (2) = 3
11100 (1)1 = Distance 3 + (1) = 4
 * 00 00 00

010 = 1 byte
 * 00011010 = 1A

100 = Length 1 + (2) = 3
11100 (1)1 = Distance 3 + (1) = 4
 * 00 00 00

010 = 1 byte
 * 00100000 = 20

100 = Length 1 + (2) = 3
11100 (1)1 = Distance 3 + (1) = 4
 * 00 00 00

011 (1)1 = 3 bytes
 * 00000001 = 01
 * 00000000 = 00
 * 00011000 = 18

11001 = Length 4 + (2) = 6
1111110 (1)1000 = 24 + (1) = 25
 * 00 00 00 00 00 00

00 = 0 bytes

11111000001 = Length 32 + (2) = 34
111100 = Distance 0 + (1) = 1
 * 00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00
   00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00
   00 00

1110 (1)10110 = 54 bytes
 * 00100100 = 24
 * 00101100 = 2C
 * 00111000 = 38
 * 10010111 = 97
 * 10110110 = B6
 * 10111010 = BA
 * 01011111 = 5F
 * ...

...

Offline mobius

  • Posts: 2747
  • relax.
    • View Profile
Re: Hacking Lemmings Revolution
« Reply #66 on: May 02, 2012, 08:55:29 PM »
I didn't want to post this in the glitches thread because it's not exactly a glitch. But maybe you can get something out of it. I found it interesting.

I took a screencap with "Screenhunter6" while playing the game, and this is the picture that came from it (see attachment)

this never happened before (I've taken quite a few pics now).
However, I noticed every time I take a picture, Revolution 'flashes' or blacks out for a split second. (this doesn't normally happen with this program).

-(this is the level 'Lone Ranger') most of the objects are gone, like the teleporters and acid but the "light" from the acid is still there. also the lemmings are gone (they were there in reality. ...that sounds odd :-\)
plus you can see through to the background decoration.

I should mention I also attempted to take a video of the game awhile ago with Camstudio and a somewhat similar anomaly happened. [The video was mostly black and the whole thing appeared to be misplaced up and to the left so all you saw was a small portion of the game happening in the upper corner of the screen.]

At least this let me see the different parts of the graphics and the way they're rendered in a way
everything by me: https://www.lemmingsforums.net/index.php?topic=5982.msg96035#msg96035

"Not knowing how near the truth is, we seek it far away."
-Hakuin Ekaku

"I have seen a heap of trouble in my life, and most of it has never come to pass" - Mark Twain


Offline ccexplore

  • Posts: 5311
    • View Profile
Re: Hacking Lemmings Revolution
« Reply #67 on: May 02, 2012, 09:50:36 PM »
In general, screen capture types of program aren't guaranteed to play well with programs that outputs video through DirectX and similar means.  The price of being able to output video faster is that other programs occasionally can't accurately read back what is currently being displayed.

That said, I think for the CamStudio issue, I suspect you simply failed to correctly set up CamStudio to capture full-screen instead of a specific region of the screen.  Either that or CamStudio is buggy and fails to correctly calculate the screen size.

Offline Leo

  • Posts: 125
    • View Profile
Re: Hacking Lemmings Revolution
« Reply #68 on: May 28, 2012, 02:38:55 AM »
This is not really related to this subject, but it's sort of the game settings and maybe can be the start of some new game settings program. As I can see GuyPerfect is certainly capable to make one.

There are 3 possible ways of pointer behaving at the gameplay, but I don't see it's mention in the manual or selectable in the game itself.

One, of course, is default settings. It's, lets say, 'Manual rotation'. Right mouse button must be hold to rotate cylinder.

Other one is 'Automatic rotation'. Rotation follows any mouse movement, and right mouse button is switch between the play area and 'skill icons'.

Last one is 'Old style' with rotation when pointer touch the playfield edges.

Settings to that three styles are just metter of changing one number in the game registry entries. So, it's all what we have here, three reg files, one for each setting. Just doubleclick on any and try for yourself.

But, I have some other ideas what can be included in some nice settings utility.
Switching On/Off animation, all together, or separate for each one. Start animations are really annoying, who want's to watch that every time before the game? Animation after the end of a level also start to be boring after some time. It's enough to change the names of the animations in the EXE file (change any letter in the names) and animations files will be considered missing and animation will be skipped. It's easy to change that 'manualy' with an hex editor, but that's not something what 'normal' gamer do.
And there is one more thing that be nice to have. At the 'Old style' rotation, pointer can't reach 'skill icons' area normally, so must be switched with right mouse button. It's OK for the 'Automatic rotation' settings, but for the 'Old style' is stupid. Would be nice if that can be 'fixed'.

Offline mobius

  • Posts: 2747
  • relax.
    • View Profile
Re: Hacking Lemmings Revolution
« Reply #69 on: May 28, 2012, 03:57:10 AM »
hey you didn't give up on this did you Guy?

good ideas there Leo.  Guy has already discovered a number of things in the game that were not documented or in the manual.

There are 3 possible ways of pointer behaving at the gameplay, but I don't see it's mention in the manual or selectable in the game itself.

Other one is 'Automatic rotation'. Rotation follows any mouse movement, and right mouse button is switch between the play area and 'skill icons'.

so in other words; the cursor always remains horizontally in the center of the screen and when you move the mouse right the cylinder rotates right? Sounds like it might be a very cool concept, but it would be cool to be able to switch easily. thanx for those  :)

As far as ideas for the game I have a few as well but was holding off on mentioning them, but I might as well while I remember them. It would be nice for blockers to turn builders like in previous lemmings games.
everything by me: https://www.lemmingsforums.net/index.php?topic=5982.msg96035#msg96035

"Not knowing how near the truth is, we seek it far away."
-Hakuin Ekaku

"I have seen a heap of trouble in my life, and most of it has never come to pass" - Mark Twain


Offline Minim

  • Posts: 1724
    • View Profile
Re: Hacking Lemmings Revolution
« Reply #70 on: May 30, 2012, 08:13:24 AM »
good ideas there Leo.  Guy has already discovered a number of things in the game that were not documented or in the manual.

I agree. Both registration entries do work quite well (Although one of them made me dizzy. :sick:). However, I'm getting a slight problem with both of them. I am unable to fast forward. When I try to click on that button the pointer moves back to the middle whether it's a left click or a right click (Unless it's me not knowing which key is to fast forward). I wonder how that can be solved...
Level Solving Contest creator. Anybody bored and looking for a different challenge? Try these levels!

Neolemmix: #1 #4 #5 #6
Lix: #2  #7
Both Engines: #3

Offline GuyPerfect

  • Posts: 363
    • View Profile
Re: Hacking Lemmings Revolution
« Reply #71 on: May 30, 2012, 04:56:01 PM »
I imagine the functionality is leftovers from A) the PlayStation version of the game and B) an early Windows approach to rotation. On PlayStation, I imagine you could use shoulder buttons to rotate, and a couple other buttons to select skills, so all you needed to do was move the cursor to select Lemmings and not use it for rotation. The first Windows build may have used the classic edge-of-screen paradigm used by other Lemmings games, but they settled on the right-hold solution because frankly, it's more intuitive.

Very nice finds, Leo. It's fun to see that this stuff is still in the game without modifying anything.

As for adjusting the program to make it work with whatever enhancements, it's certainly possible. I personally would love to tweak the screen size to get the game to run at a higher resolution, and my poking around in the programming suggests that there are actual variables containing 640 for width and 480 for height that might be able to be simply changed to modify the size the game runs at. Having said that, I wanted to keep such enhancements out of the "fix" patch, since they're not "fix" related.

Offline Leo

  • Posts: 125
    • View Profile
Re: Hacking Lemmings Revolution
« Reply #72 on: May 30, 2012, 11:21:07 PM »
All the keyboard controls I know of (some of them are not documented in the manual).

Esc. . . . . . . . . . . . .options (in game)
                              exit to windows (in menus)
Space, Control . . . zoom in, zoom out
Backspace. . . . . . . rotate 180 degrees
Cursor left. . . . . . . (hold) select only left walking lemmings
Cursor right. . . . . . (hold) select only right walking lemmings
Cursor up, A . . . . . change one skill up
Cursor down, Z . . .change one skill down
P. . . . . . . . . . . . . . .pause
O. . . . . . . . . . . . . . options (in pause)
Num pad left . . . . . move cursor left (rotation left)
Num pad right. . . . .move cursor right (rotation right)

At the default mouse settings Num pad left/right rotate screen only when Right mouse button is hold down. On the other two settings these buttons can rotate screen without a mouse.

There isn't 'fast forward' key on the keyboard, that's strange. And it is annoying that 'fast forward' is not available if mouse is not in the default mode.

Offline lem

  • Posts: 1
    • View Profile
Re: Hacking Lemmings Revolution
« Reply #73 on: July 15, 2012, 08:55:04 PM »
Possible New Idea

I was thinking that this game would be ideal to play on a touchscreen and would likely become one of the best touchscreen games available. The interface is really perfect for it and it doesn't necessarily require any mouse motion like when played on PC as it has a simple point and click input.

However when touchscreen is used, the mouse cursor (ie the in-game green crosshair) mostly circles the outer edge of the gameplay area. It does float quickly over the gameplay area when touching the center of the screen, but is quickly dragged to the outer edge closest to where the screen is touched. Is there a reason why this is happening? Or is there a fix that would allow Lemmings Revolution to work on a touchscreen.

Thanks

Offline jclampy

  • Posts: 23
    • View Profile
Re: Hacking Lemmings Revolution
« Reply #74 on: July 16, 2012, 01:33:25 PM »
Wow guys, just found out about this custom patch today and it is great!  :thumbsup:

Anyhow, I read a couple of people asking if Lemmings Revolution could be played in a window or at different resolutions. I found that we could use DXWind and posted about it here http://www.lemmingsforums.com/index.php?topic=646.0

Unfortunately DXWind doesn't play nicely with your custom patch.

Just wondering, is it possible to make the custom patch play nicely with DXWind.
Or, from trying DXWind can you get any hints for how to make your custom patch work in a window or at different resolutions without using DXWind?

At the very least you might have a good idea of what DXWind settings might work better with Lemmings Revolution.
In particular so that [Alt][Tab] or clicking outside of game window doesn't crash, etc..
To keep this thread clean; if you do find some good settings for DXWind please post in that thread http://www.lemmingsforums.com/index.php?topic=646.0

PS: really impressed with your custom patch and really enjoyed reading through this thread!