Rustlings / code generation algorithm for Lemmings 1 / DOS

[DirtyHairy]

Howdy!

I few years ago I wrote a lemmings 1 data decoder and viewer ("rustlings") in an effort to get to know rust. At this point, it is capable to decode the original data files, extract level and graphics data and display sprites and levels. You can find the source here: https://github.com/DirtyHairy/rustlings

A few days ago I started working on it again, with the intend of expanding it into a full game engine. Since then I have spent a bit of time poking the original .exe with Ghidra to reverse a few bits and pieces that I am missing (or do not just want to read off from existing reimplementations), and on the way I also reversed the code generation algorithm. As I couldn't find much about this online, here's a JavaScript version that can generate the codes for all original levels, in case anyone else comes looking for the same thing:

Code Select Expand

// rating and level both zero based
function codeFor(rating, level) {
  const secret = "AJHLDHBBCJ".split("").map((x) => x.charCodeAt(0));
  const percentage = 100;

  const levelIndex = 30 * rating + level;
  const code = new Array(10).fill(" ".charCodeAt(0));

  code[0] = ((levelIndex & 0x01) << 3) | secret[0] | ((percentage & 0x01) << 2);
  code[1] = ((levelIndex & 0x02) << 1) | secret[1] | ((percentage & 0x02) >> 1);
  code[2] = (levelIndex & 0x04) | secret[2] | ((percentage & 0x04) >> 1);
  code[3] = ((levelIndex & 0x08) >> 3) | secret[3] | ((percentage & 0x08) >> 2);
  code[4] = ((levelIndex & 0x10) >> 3) | secret[4] | ((percentage & 0x10) >> 1);
  code[5] = ((levelIndex & 0x20) >> 5) | secret[5] | ((percentage & 0x20) >> 3);
  code[6] = ((levelIndex & 0xc0) >> 4) | secret[6] | ((percentage & 0x40) >> 6);
  code[7] = (levelIndex & 0xf) + secret[7];
  code[8] = (levelIndex >> 4) + secret[8];
  code[9] =
    ((code[0] + code[1] + code[2] + code[3] + code[4] + code[5] + code[6] + code[7] + code[8]) & 0xf) + secret[9];

  for (let i = 7 - (levelIndex & 0x07); i > -1; i--) {
    const tmp = code[6];
    code[6] = code[5];
    code[5] = code[4];
    code[4] = code[3];
    code[3] = code[2];
    code[2] = code[1];
    code[1] = code[0];
    code[0] = tmp;
  }

  return code.map((x) => String.fromCharCode(x)).join("");
}


[DirtyHairy]

Actually, turns reality is slightly more complicated On my actual copy of lemmings, the code for the next level depends on the percentage of lemmings rescued when completing the current one, and all different codes generated this way work. In addition, there is a variable (that I called "salt" in the listing below), the lowest 4 bit of which are encoded in the code. All different salts generate valid codes, and restoring a code also restores the salt, so subsequent codes will encode the same value. Or, in other words, if you enter a code for a different percentage you'll get the same codes for the next levels, but if you enter a code with a different salt you'll get a different set of codes.

Code Select Expand

// rating:        0 .. 4
// level:         0 .. 29
// percentage:    0 .. 100
// salt:          0 .. 0x0f
function codeFor(rating, level, percentage = 100, salt = 0x00) {
  const secret = "AJHLDHBBCJ".split("").map((x) => x.charCodeAt(0));

  const levelIndex = 30 * rating + level;
  const code = new Array(10).fill(" ".charCodeAt(0));

  code[0] = ((levelIndex & 0x01) << 3) | secret[0] | ((salt & 0x01) << 1) | ((percentage & 0x01) << 2);
  code[1] = ((levelIndex & 0x02) << 1) | secret[1] | ((percentage & 0x02) >> 1);
  code[2] = (levelIndex & 0x04) | secret[2] | ((percentage & 0x04) >> 1) | ((salt & 0x02) >> 1);
  code[3] = ((levelIndex & 0x08) >> 3) | secret[3] | ((percentage & 0x08) >> 2);
  code[4] = ((levelIndex & 0x10) >> 3) | secret[4] | ((percentage & 0x10) >> 1) | ((salt & 0x04) >> 2);

  code[5] = ((levelIndex & 0x20) >> 5) | secret[5] | ((percentage & 0x20) >> 3) | ((salt & 0x08) >> 2);
  code[6] = ((levelIndex & 0xc0) >> 4) | secret[6] | ((percentage & 0x40) >> 6);
  code[7] = (levelIndex & 0xf) + secret[7];
  code[8] = (levelIndex >> 4) + secret[8];

  code[9] =
    ((code[0] + code[1] + code[2] + code[3] + code[4] + code[5] + code[6] + code[7] + code[8]) & 0xf) + secret[9];

  for (let i = 7 - (levelIndex & 0x07); i > -1; i--) {
    const tmp = code[6];
    code[6] = code[5];
    code[5] = code[4];
    code[4] = code[3];
    code[3] = code[2];
    code[2] = code[1];
    code[1] = code[0];
    code[0] = tmp;
  }

  return code.map((x) => String.fromCharCode(x)).join("");
}