DOS Lemmings (OhNo, Holiday, etc) password algorithm

[namida]

Subject came up in Discord, realised I couldn't easily find any documentation of the algorithm on Google despite being sure I'd seen it before, managed to track it down. Posted here for reference.

Source: The source code to "LemGen", linked under "Other game tools" on the Lemmings Universe downloads page. This is from comments in LCP100S0.BAS (which is the only source code file).

'-----------------------------------------------------------------------------
'
' HOW THE LEMMINGS CODES ARE PUT TOGETHER:
' =======================================
'
' Let us number the characters in the codes as follows: 0123456789
'
' This example of the first 20 level numbers are taken from my 100% codes
' from the original Lemmings version:
'
'    Level   Real order          Real order            Logical order
'   number
'           0123456 78 9   vertically aligned 78 9      0123456 78 9
'
'       1:  CAJJLDL BC S       CAJJLDL        BC S      AJJLDLC BC S
'       2:  IJJLDLC CC L        IJJLDLC       CC L      IJJLDLC CC L
'       3:  NJLDLCA DC Y         NJLDLCA      DC Y      ANJLDLC DC Y
'       4:  JLDLCIN EC R          JLDLCIN     EC R      INJLDLC EC R
'       5:  LDLCAJN FC K           LDLCAJN    FC K      AJNLDLC FC K
'       6:  DLCIJNL GC T            DLCIJNL   GC T      IJNLDLC GC T
'       7:  LCANNLD HC Q             LCANNLD  HC Q      ANNLDLC HC Q
'       8:  CINNLDL IC J              CINNLDL IC J      INNLDLC IC J
'       9:  CAJJMDL JC L       CAJJMDL        JC L      AJJMDLC JC L
'      10:  IJJMDLC KC U        IJJMDLC       KC U      IJJMDLC KC U
'      11:  NJMDLCA LC R         NJMDLCA      LC R      ANJMDLC LC R
'      12:  JMDLCIN MC K          JMDLCIN     MC K      INJMDLC MC K
'      13:  MDLCAJN NC T           MDLCAJN    NC T      AJNMDLC NC T
'      14:  DLCIJNM OC M            DLCIJNM   OC M      IJNMDLC OC M
'      15:  LCANNMD PC J             LCANNMD  PC J      ANNMDLC PC J
'      16:  CINNMDL QC S              CINNMDL QC S      INNMDLC QC S
'      17:  CAJJLFL BD V       CAJJLFL        BD V      AJJLFLC BD V
'      18:  IJJLFLC CD O        IJJLFLC       CD O      IJJLFLC CD O
'      19:  NJLFLCA DD L         NJLFLCA      DD L      ANJLFLC DD L
'      20:  JLFLCIN ED U          JLFLCIN     ED U      INJLFLC ED U
'
' We can observe block-wise rotating of the first 7 characters:
' Each block of 8 levels rotate 7 times.  Note that the codes for levels
' 8,9 and 16,17 etc. all are rotated equally:  No change between 8 and 9 etc.
'
' We can also see, that character 7 and 8 must contain level-number
' information, because of the way those values change.
'
' Character 9 could be a checksum, which is an obvious idea to be checked.
'
' Coming back to the first 7 characters:
' It is not hard to decide where to start the first logical character. In the
' "verticalli aligned" column, we see a column with AIAIAIAI etc., and the
' column to the right of that one, we see JJNNJJNN etc.  It looks as if the
' level number is hidden in there too in a binary way:  The least significant
' bit on the left.  So let's rotate these seven characters until this supposed
' least significant bit is placed first, and we have our logical order.
' The code looks much more structured now!
'
' Looking at codes with percent information for a certain level (which you
' can try yourself and which I don't show here), we see that this extra
' information is also changing those seven characters in a similar way as
' the level-number information does.  There are some exceptions here with
' these percentages, which are due to what I call "spurious bits".
'
'- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
'
' Some conclusions and other observations:
'
' characters 0..6 : bit-coded rotating level + percentage info,
' characters 7    : hex Level low  4 bits
' characters 8    : hex Level high 4 bits (the highest bit will always be 0)
' characters 9    : hex checksum of chars[1..9]
'
' More results:
'
' Different Lemmings games use different letter ranges for each character:
' The different characters, counted the logical way as in the last column in
' in the table above, start at different  characters for different games.
' Let us call these starting values "base characters".  It is not hard to
' guess what those might be, if you look at the character ranges of each
' column in the "logical order" codes separately.  I found these "bases":
'
'                                   Logical order 0123456789
'                                                 ----------
' Lemmings, Xmas91, Xmas92, COVOX, Prima Bonus:   AJHLDHBBCJ
' Oh No!, Oh No! demo:                            AHPTDHBBAD
' Holiday 1993, Holiday 1993 demo:                AJHLDHBBAD
' Holiday 1994, Holiday 1994 demo:                AJPLDHBBCD
' Lemmings demo, old version. (Not found by me):  EHPVLXDHIJ <- see below
'
' If we forget the old demo of the original Lemmings version with its
' incomplete implementation of the coding scheme, we can see that only
' characters 1, 2, 3, 8 AND 9 use different bases.
'
' These base characters are updated to a code by adding a nibble to each
' character, which carry several different bit-wise informations.
' (A nibble is a 4 bit unit, a hecadecimal digit, a number between 0 and 15.)
' The first 7 updated characters are then rotated somehow for each level.
' Expect only illegal codes with base character (3), especially with Oh No!
' (The old original Lemmings demo would create a lot more illegal codes then.)
'
' In 1999 I found exactly the above strings (AJHLDHBBCJ etc.) in the expanded
' exe-files of each game.  These strings were exactly the same as what I
' constructed in 1994 and 1999, except for old Lemmings demo:
'
'- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
'
' Before I knew about the incompleteness of the old Lemmings demo, which does
' not use the percentages of rescued lemmings, I used the same scheme as with
' the other games, and got for 100% rescued lemmings following base characters
' Lemmings demo, old version, my first guess:     GHNVMTCHIJ <- not used here
'
' Because percentage is not used there, and because I found the string
' EHPVLXDHIJ in the expanded exe file, where all other games have strings,
' matching my already found base characters, I used that info instead.
' This meant, that I needed to make my spurous bits fixed to 33, (= hex 21).
'
'- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
'
' Checksum calculation is very eazy:
' The low nibble of the sum of the ASCII values of the first 9 characters
' is to be added to the base character for the checksum.  That is it.
'
'-----------------------------------------------------------------------------
'
' The description of each bit in the nibbles of the 7 "rotating" characters:
'
' The table below shows following:
'
' Line 1:  Nibble numbers, which are the same as the logical order numbers.
' ------
' Line 2:  Bit numbers of the 4 bits in each nibble, as usual.
' Line 3:  Bit values  of the 4 bits in each nibble, as usual: = 2^bit_number
'
' Line 4:  The bit descriptions of each bit in each nibble, where:
'     0  = fixed bitvalue: must be zero, otherwise the code is not accepted!
'     Ln = level bits: L6 is most significant, L0 is least significant
'     %n = previous percentage bits: %6 is most-, %0 is least significant
'     Sn = spurious bits: S6 is used here as most, S0 as least significant
'
' nibble 0 | nibble 1 | nibble 2 | nibble 3  | nibble 4 | nibble 5 | nibble 6
'----------|----------|----------|-----------|----------|----------|---------
' 3  2  1 0| 3  2 1  0|3  2  1  0| 3  2  1  0| 3 2  1  0|3  2  1  0|3  2 1  0
' 8  4  2 1| 8  4 2  1|8  4  2  1| 8  4  2  1| 8 4  2  1|8  4  2  1|8  4 2  1
'          |          |          |           |          |          |
'L0 %0 S0 0|S1 L1 0 %1|0 L2 %2 S2|S4 S3 %3 L3|%4 0 L4 S5|0 %5 S6 L5|0 L6 0 %6
'       |    |                     |  |                |
'       |    +---------------------+--+----------------|---> never seen as 1
'       +----------------------------------------------+---> old Demo: make 1
'
'-----------------------------------------------------------------------------