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 (https://www.lemmingsuniverse.net/downloads.html). This is from comments in LCP100S0.BAS (which is the only source code file).
Quote'-----------------------------------------------------------------------------
'
' 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
'
'-----------------------------------------------------------------------------