# ReDMCSB Readme

## What is ReDMCSB?

ReDMCSB means 'Reverse engineered Dungeon Master and Chaos Strikes Back'. It contains the source code of all versions of both games except the Super NES console versions: Atari ST, Amiga, Apple IIGS, FM-Towns, X68000, PC-98 and PC. This is not the original source code as written by the FTL Games developers but the result of reverse engineering directly from the executables found on the original floppy disks and compact discs. However this source code is extremely accurate because the resulting executables are either identical to the originals or very similar with minor differences explained in the Accuracy section.
ReDMCSB contains 6 toolchains to build all executables, consisting of emulators, compilers, linkers, some other tools and scripts to provide a fully automated build process. The build process is designed to run on Windows (only tested on Windows 10 64 bits).

ReDMCSB can build 146 executables for all programs in the 36 different versions of Dungeon Master or Chaos Strikes Back listed below (including the programs on the Chaos Strikes Back Utility Disk). See ReDMCSB.xlsx for the full list of executables and game versions:

- Dungeon Master for Atari ST 1.0a English (no version visible in dialog boxes)
- Dungeon Master for Atari ST 1.0b English (version '1.0' visible in dialog boxes)
- Dungeon Master for Atari ST 1.1 English
- Dungeon Master for Atari ST 1.2 English
- Dungeon Master for Atari ST 1.2 German
- Dungeon Master for Atari ST 1.3a French (version 1.3 visible in dialog boxes)
- Dungeon Master for Atari ST 1.3b French (variant, version 1.3 also visible in dialog boxes, the only difference is one bug fix for BUG0_56, see Bugs And Changes)
- Chaos Strikes Back for Atari ST 2.0 English
- Chaos Strikes Back for Atari ST 2.1 English
- Dungeon Master Demo for Apple IIGS 1.4 English
- Dungeon Master for Apple IIGS 2.0 English
- Dungeon Master for Apple IIGS 2.1 English
- Dungeon Master Demo for Amiga 2.0 English
- Dungeon Master for Amiga 2.0 English
- Dungeon Master for Amiga 2.0 French
- Dungeon Master for Amiga 2.0 German
- Dungeon Master for Amiga 2.1 English
- Dungeon Master for Amiga 2.2 English
- Dungeon Master for Amiga 2.2 German
- Chaos Strikes Back for Amiga 3.1 English
- Chaos Strikes Back for Amiga 3.1 English, French, German
- Chaos Strikes Back for Amiga 3.3 English, French, German
- Chaos Strikes Back for Amiga 3.5 English
- Chaos Strikes Back for Amiga 3.5 English, French, German
- Dungeon Master for Amiga 3.6 English, French, German
- Dungeon Master for FM-Towns 2.0 English
- Dungeon Master for FM-Towns 2.0 Japanese
- Chaos Strikes Back for FM-Towns 3.1 English
- Chaos Strikes Back for FM-Towns 3.1 Japanese
- Dungeon Master for PC-98 2.0a Japanese (version 2.0 visible in dialog boxes, contains DMSTART3.EXE)
- Dungeon Master for PC-98 2.0b Japanese (variant, version 2.0 also visible in dialog boxes, contains DMSTART4.EXE)
- Chaos Strikes Back for PC-98 3.1 Japanese
- Dungeon Master for X68000 3.0 Japanese
- Chaos Strikes Back for X68000 3.1 Japanese
- Dungeon Master for PC 3.4 English
- Dungeon Master for PC 3.4 English, French, German

## Package contents

This package contains the following files and folders:

Documentation
  Documentation. This readme and also:
  - Bugs And Changes: List of known bugs and changes between versions (only for Atari ST versions).
  - Copy Protection: Detailed description of the copy protection (only for Atari ST versions).
  - Engine: Explanations of some aspects of the game engine.
  - Megamax C: Information about Megamax C version 1.1 gathered during the reverse engineering.
  - ReDMCSB.xlsx: Contains the list of media and their naming convention (each media is a floppy disk or compact disc), the list of all files on each media, the list of executables and instructions to build them from source code files: which source code files are required for each executable, their segmentation and order of compilation and linking).
  - Toolchains: Describes the ReDMCSB toolchains and their preparation.
Reference
  Reference executables for comparison after building with ReDMCSB. Executables built with ReDMCSB are either perfectly identical to the originals or they are different because some tools used in ReDMCSB are not the same versions as those that were used for the originals, and they produce slightly different results. The 'Original' subfolder contains all the original executables. The 'ReDMCSB' subfolder contains only the executables that ReDMCSB cannot build perfectly. Each time ReDMCSB builds an executable file, it is compared to the reference executable file (the 'ReDMCSB' one if present else the 'Original' one) to make sure any change made in the source code or build scripts did not change the resulting executable file.
Toolchains
  Contains one subfolder for each toolchain to build executables. There are six toolchains, each containing an emulator and all the required tools to build executables on one platform: 'Apple Macintosh', 'Atari ST', 'Commodore Amiga', 'Fujitsu FM-Towns', 'IBM PC', 'Sharp X68000'. There is another special toolchain called 'Common' that contains items shared with all other toolchains. In each toolchain folder, there is a 'Base' subfolder containing the actual tools, and a 'Source' subfolder containing the scripts to build executables and may also contain some assembly source code for that specific platform (`*.H`, `*.ASM`), linker files (*.LNK) and scripts (`*.BAT`). The 'Source' folder in the 'Common' toolchain contains most of the ReDMCSB source code (only `*.C`, `*.H` files).
Output
  This folder is created at runtime to store all files generated by ReDMCSB: temporary folders to prepare and run each toolchain, 'Object' folder to store compiled object files, 'Build' folder to store executables, 'Analysis' folder where executable fles are disassembled for text comparisons.

This package does not include:

- The full distribution of compilers/linkers: only the necessary files are included in the ReDMCSB distribution to minimize the size of the package.

The source code includes:

- Mostly C language with some parts written in assembly language (Motorola 68000, Intel 8086 16 bits and 32 bits, MOS Technology 65C816). All the parts in assembly language were written as-is by the original developers, mostly for performance reasons (like the low level graphic and sound routines). The C compilers cannot generate these parts from C language but support inline assembly code in the source code.
- Meaningful and consistent names for all functions and their parameters, global and local variables, constants and macros. [Completed only for Atari ST versions]
- Comments.
- Conditional compilation directives allowing compilation of each version from the same source code. They also provide easy identification of the differences between versions.
- Conditional compilation directives allowing compilation without the copy protection. They also provide easy identification of all code related to the copy protection. [Tested for Atari ST and Amiga versions only]

## How to build executables

This archive does not contain the compiled object files. Executables are available in the Reference folder: All 146 original files are in the 'Original' folder; Executables built with ReDMCSB that are not fully identical to the original files are stored in the 'ReDMCSB' folder. The build process is fully automated with a combination of PowerShell scripts and other scripts running inside emulators. Run the `Build.cmd` file and choose an option to select which executables to build. You can choose to build executables for each of the six toolchains, build all executables at once, or pick which executables to build from a GUI table. Warning: emulators are configured to run with maximum performance and building all executables will start all emulators in parallel which may slow down you computer during the build process. Building all executables can take a long time (up to an hour in my experience, the Apple Macintosh toolchain is the longest because of the high number of executables to build).

## Accuracy

In ReDMCSB.xlsx, go to the 'Executables' tab and check the 'Reference folder' column. The value is 'Original' for executables built with ReDMCSB that are identical to the original executables, otherwise the value is ReDMCSB. Column 'Anomalies causing differences between original and ReDMCSB executables' briefly describes the differences.

### Atari ST

The Reference\Original folder contains the compressed `START.PAK` files from the original floppy disks. When the game starts, `START.PRG` decompresses and then runs the engine executable file. You can use the `Expand-AtariSTPAK.ps1` script in the Toolchains\Base folder to decompress `START.PAK` files.

The executables built from this source code with Megamax C version 1.1 (available in the Reference\ReDMCSB\Sxxx folders) are not identical to the executables built by FTL (available in the Reference\Original folder), but they are as close as possible. This section explains the differences between the two versions. Because of these differences, the executables in the Reference\ReDMCSB\Sxxx folder will fail some copy protection checks because of incorrect checksum values.

The differences are not caused by the source code being 'wrong' but rather because FTL used another version of the Megamax C compiler and linker (probably version 1.2) that includes further optimizations. This version is not available anywhere on the Internet, I could only find and use version 1.1. If you disassemble and compare the executables (between Reference\Original and Reference\ReDMCSB folders) you will find many differences but in fact all of them are caused by 4 compiler optimizations not included in Megamax 1.1 and one difference in linker behavior.

Here are technical details about the differences in compiler behavior:

- When casting an `unsigned char` into an `unsigned int`, version 1.1 generates `move.b` and `and.w #255` instead of `clr.w` and `move.b` in the original.
- Inside a `switch` statement, if the last statement right before a `case` or right at the end of a `default` (but not before a `default`, and not at the end of the last `case` in the switch) is a `break`, a `return`, a `continue` or a `goto`, it will generate a `bra` instruction. Version 1.1 adds a second `bra` instruction to branch to the statement following the next `case` instead of omitting the second `bra` in the original. This optimization avoids inserting `bra` instructions that would never be executed.
- When pushing two consecutive non zero, word sized immediate values as parameters of a function call version 1.1 generates two `move.w` instead of a single combined `move.l` in the original. This optimization is also performed while initializing a global variable with two consecutive `int`.
- When comparing a value with 0 using one operator among `> < >= <=` version 1.1 generates `cmpi` or `cmp` instead of `tst` in the original.

With the version 1.1 linker, eleven entries are missing from the jump table compared to the original games. Their inclusion in the jump table looks like a bug because because none of these entries are used in the program. Some point to data (and not executable code) and none of them are referenced in another segment than the one they are declared in so there is no reason for the linker to include them in the jumptable in the first place. Here are the symbols for these entries:

- V0061000_RemainingSoundSampleCount
- E0061_SOUND_Exception77Handler_TimerA_SoundPlayer
- V0061003_CurrentChannelsAmplitudeTable
- F0063_SOUND_KeyClickOff
- V0061001_SoundSampleRepeatCount
- S0076_MOUSE_OnMouseButtonsStatusChange
- S0075_MOUSE_Exception70Handler_IKBD_MIDI_MouseStatus
- V0061005_ChannelsAmplitudeTableSoft
- V0061002_NextSoundSample
- R0138_CPSEF_HiddenCodeLauncher
- F0497_LZW_Decompress

### Commodore Amiga

The executables built from this source code with Aztec C version 3.6a are identical to the executables built by FTL.

### Other platforms

TO BE COMPLETED

## Terminology

The terminology I have used in the source code is inspired from the following sources:

- The executable file of Dungeon Master for FM-Towns 2.0 English which is the only version that was compiled with symbols included (visible at the end of the file EDM.EXP).
- The executable file of Dungeon Master for Apple IIGS 2.0 English where segment names are visible.
- Documents such as the game manuals, hint books and some press articles.

There are many differences with the terminology in common usage since CSBwin, here are some examples:

CSBwin | ReDMCSB
--- | ---
Monster | Creature
Monster group | Group
Actuator | Sensor
Missile | Projectile
Cloud | Explosion
Timer | Event
Timer queue | Timeline
Cell | Square
Button | Mouse input
Mouse event | Command
Decoration | Ornament
ITEM16 | Active Group
CHARDESC | Champion
RN | Thing
Footprint | Scent

## Naming conventions

The Megamax C compiler allows arbitrarily long identifiers (for the name of variables, functions, parameters, #define) but only uses the first 10 characters. This means that the first 10 characters of each identifier must be unique. In order to avoid any risk of having two identical identifiers (from the compiler point of view), most identifiers are numbered. They start with a letter prefix because identifiers cannot start with a number. The letter prefix defines the type of identifier:

- `G`: Global variables
- `L`: Local variables
- `AL`: Alias for a local variable (used when a single variable is used for multiple purposes)
- `P`: Function parameters
- `AP`: Alias for a function parameter (used when a single parameter is used for multiple purposes)
- `F`: Regular C functions
- `E`: Exceptions declared in `asm{}` blocks (return with `rte` instruction)
- `R`: Routines declared in `asm{}` blocks (return with `jmp` instruction)
- `S`: Subroutines declared in `asm{}` blocks (return with `rts` instruction)
- `T`: Labels
- `V`: Variables declared in `asm{}` blocks
- `C`: Constant values declared with `#define`
- `M`: Macros declared with `#define`
- `MASK`: Constant values used as masks for binary operations declared with `#define`

Note: some constants declared with `#define` and all struct and union members are not numbered and still use unique names.

Identifiers for global variables, local variables and parameters contain a short string identifying their type:

- `i`: int
- `ui`: unsigned int
- `c`: char
- `uc`: unsigned char
- `l`: long
- `ul`: unsigned long
- `s`: struct
- `a<x>`: array of elements of type x (x can be any type, including another a for multi-dimension arrays)
- `p<x>`: pointer to x (x can be any type)
- `f<x>`: function returning type x (x can be any type)

These custom types defined with `typedef` also have an abbreviation because they are used very frequently:

- `V`: VOID
- `B`: BOOLEAN
- `T`: THING

Examples:

- `pui`: pointer to unsigned int
- `aul`: array of unsigned long
- `aaui`: array of array of unsigned int
- `pT`: pointer to a THING
- `pfV`: pointer to a function returning VOID
- `s`: struct

For global variables whose value is defined in one of graphics #558 to #562 in `GRAPHICS.DAT`, a prefix `Graphic558` to `Graphic562` is added to the variable identifier.

Examples of identifiers:

- `G0242_ai_Graphic559_FoodAmounts`: Global variable of type 'array of int' that is part of graphic #559
- `G0269_ps_CurrentMap`: Global variable of type 'pointer to struct'
- `P0234_T_Thing`: Function parameter of type 'THING'
- `L0236_puc_Multiple`: Local variable of type 'pointer to unsigned char'. Multiple means the variable is used for several purposes (One alias is defined for each).
- `AL0236_puc_Group`: Alias to local variable L0236_ of type 'pointer to unsigned char'.
- `C05_THING_TYPE_WEAPON`: Constant of value '5'
- `M12_TYPE`: Macro #12 (the number has no meaning)
- `MASK0x0004_TELEPORTER_VISIBLE`: Binary mask of hexadecimal value 0x0004

With some compilers, the ordering of variables and/or functions in the output executable depends on the actual identifiers of the variables and functions. This requires changing some names using #define directives to fake names used to reproduce the same ordering as in the original:

- For Atari ST, function names contain an additional prefix consisting of 4 seemingly random letters or digits. These characters are used to make sure that the functions appear in the correct order in the jump table at the beginning of the executable file. The linker defines the order of functions based on hashes of their names (the first 10 characters). These characters were carefully selected for each function so that the hashes are ordered in the same order as in the original FTL source code.
- TO BE COMPLETED for other platforms. This problem is not solved for ordering of functions in jumptables generated by the Think C compiler

## Size optimizations

This section applies to Atari ST versions only.

FTL designed Dungeon Master to run on the first Atari 520ST computers. The requirements were:

- The game must fit on a single sided floppy disk because the floppy disk drives in the first Atari 520ST computers were only single sided and FTL did not want to include multiple floppy disks to minimize production costs.
- The game must run in the 512 KB of RAM available in the Atari 520ST.

As shown below, FTL went to great lengths to save disk space and minimize memory footprint. In Dungeon Master, there is no free space available on the original floppy disk which means that all of these optimizations were necessary to put as much content as possible in the game. In Chaos Strikes Back, there is free space available on the floppy disk because the dungeon file (the Prison) is much smaller (the actual dungeon is on the Utility Disk).

### Memory usage

Having the Atari ST boot from the game floppy disk allows reclaiming a memory area that is normally used by the Atari ST OS and is required to load all the game data. This is one of the reasons why the game could not be installed on a hard disk, the other being the copy protection.

### Non standard floppy disk format

The standard floppy disk format for Atari ST use 9 sectors per track, providing 360KB of storage on a single side (80 tracks per side, 512 bytes per sector).
FTL used a non standard format with 10 sectors per track to increase the capacity to 400KB. This custom format can be read without issues. Writing to such disks is less reliable (because the gaps between sectors are smaller) but this is not an issue as it is not needed to write anything on the game disk.

### Custom initialization routine

When the Megamax C linker builds an executable file, it automatically links `init.o` (stored in SYSLIB) which contains the very first routine executed when the program runs. The source code of this module is supplied with Megamax C in the file `init.c`. FTL customized this code and replaced the original `init.o` module in SYSLIB. Here is what was changed from the original:

- The stack size is set to 2000 bytes instead of 8192 bytes to save some memory.
- The instruction `and.l #-2,D0` used to ensure an even byte boundary for the stack address is replaced by `andi.w #-2,D0`.
- Variables `_argc` and `_argv` are removed as well as the call to `_initargcv()` to initialize them from the command line (the game does not access the command line with the standard C parameters for `main()`). Without this call, the linker does not link `_initargcv.o` anymore to the executable.
- The call to `exit()` when `main()` returns is removed (the game never returns, you must restart the computer). Without this call, the linker does not link `exit.o` anymore to the executable as well as these other dependant modules: `close.o`, `exit.o`, `fclose.o`, `fillbuf.o`, `lseek.o`, `misc.o`, `open.o`, `osbind.o` and `write.o`.

These changes save disk space (smaller `.PRG` file with fewer linked modules) and some memory (smaller stack and smaller program code).

### Bulk initialization of global variables

In a `.PRG` file, the BSS segment is only defined by its size in the header. The purpose of this segment is to store global and static variables without an initial value in the source code. It is filled with $00 bytes by the initialization routine before `main()` is executed. The DATA segment is stored near the end of the file after the CODE segment and before the relocation data.
The Megamax C compiler stores only strings in the DATA segment. Other global and static variables that have an initial value are allocated in the BSS segment. Because of this, the compiler generates code to initialize these variables in a code segment named `init!`. This code is also called by the initialization routine before `main()` is executed. The size of the code in `init!` is much larger than the variables it initializes. Because the game contains many global and static variables that should have initial values, FTL decided to minimize the size of the `init!` segment by declaring many variables without their initial values in the source code and rather store the actual data in 5 graphics #558 to #562 in `GRAPHICS.DAT` (their total size is around 12KB). Early when the game starts, each of these graphic is loaded in memory as a block which immediately initializes lots of variables at once while using very few code. This helps to minimize the size of the `.PRG` executable file and its memory footprint.
The Atari ST versions are the only ones to use such a trick. In all other versions, there are no global and static variable values in `GRAPHICS.DAT` (Note that in Dungeon Master for Amiga 2.0 English the graphics #558 to #562 are also present in `GRAPHICS.DAT` but they are not used and the actual data is in the executable file itself).

### Executable file compression

In order to save disk space, the `.PRG` executable file is compressed on the floppy disk in a file named `START.PAK` (33% smaller than the original executable file). When `START.PRG` is executed, it loads `START.PAK`, decompresses it in memory and then runs it.

### Graphics compression and caching

In order to save both disk space and memory, most of the content in `GRAPHICS.DAT` is compressed using two algorithms:

- All the bitmaps are encoded in a way that is fast to decompress. The main purpose of this compression is to save memory as most bitmaps are stored in this compressed form in memory.
- Many graphics (bitmaps, sounds, font, text) are compressed with the LZW algorithm. The purpose of this compression is only to minimize the file size on the floppy disk because when the game loads an LZW compressed graphic it is immediately decompressed in memory. The LZW decompression is quite slow and is responsible for the long loading time of the game.

In order to avoid decompressing the same bitmap multiple times while drawing the dungeon view, the game manages a dynamic cache where it stores the most used bitmaps in decompressed form. Each time a bitmap is required, the game checks if it is already available in the cache. If not then it is decompressed and added to the cache for later use. The cache size is only limited by the available memory after all graphics (bitmaps and sounds) have been loaded.
Storing bitmaps in compressed form in memory and using this cache provides a good compromise between memory footprint and performance.

## Reverse engineering process overview

This section applies to Atari ST versions only.

This section briefly describes the overall process I have used to 'decompile' the original executables back to source code.

For each of the 9 versions:

1. Decompress the executable file from `START.PAK`.
2. Disassemble with TTDigger (running in an Atari ST emulator).
3. Load the disassembly in an Excel spreadsheet. For each line of assembly code, I have the original bytes and the offset.
4. Study of the assembly code.
   - Cleanup of some useless `EQU` instructions that TTDigger adds sometimes without any valid reason.
   - Find and comment all system calls that use `TRAP` instructions.
   - Analysis of the initialization routine (automatically added by the linker).
   - Find all sections in the code: delimit each function and routine, correctly identify code and data (some data in the code segment was disassembled by TTDigger as regular instructions).
   - Find all global variables (offsets to A4 register), local variables and parameters (offsets to A6 register) and all function calls. Inter-segment function calls are performed via the jump table using offsets to A5.
   - Give names to each function, parameter and variable. Establish offset correspondances between game versions.
5. Study of Megamax C compiler 1.1 with simple test programs (FTL mentioned that they used the Megamax C compiler in an interview). Compare the source code statements with the generated machine code to learn what code corresponds to each statement.
6. For each function in the game, write C source code, compile and disassemble the compiled code (with Megamax in Atari ST emulator) then compare (manually and visually) with the original disassembly. Repeat until the C source produces machine code identical to the original (or nearly identical, see Accuracy).

## History

### Release 1 (2014-01-18)

First release

### Release 2 (2014-08-05)

BugsAndChanges.htm: Updated descriptions for BUG0_22 and CHANGE7_19, 14 additional bugs described in BUG0_63 to BUG0_76
Engine.htm: Added a 'Balance issues' section, Updated the 'Limits' section
Readme.htm: Added 'History' section, added Steem SSE as supported emulator for compilation of ReDMCSB
DEFS.H: Updated the CHAMPION structure with information from other platforms
*.C: A few more comments here and there in the source code

### Release 3 (2021-XX-XX)

BugsAndChanges.htm: Added BUG0_77 and others...

Source code for additional versions of the games: Apple IIGS, Commodore Amiga, Fujitsu FM-Towns, Sharp X68000, Nec PC-98 and IBM PC

Lots of changes to source code for consistency with Amiga source code (the binary code generated on Atari ST does not change). Examples: a signed int replaced by an unsigned int, replace a loop type by another (for, while, do / while), curly brackets removed when there is a single statement in an if statement, if / return replaced by if / else, return or continue replaced by goto, if then else replace by ? :
Source core refactoring: merged PROJEXPL.C and GROUP2.C, merged MOVE.C and SENS.C to MOVESENS.C, renamed ...
Array variables G079, G080 and G088 replaced by multiple variables
Fixed a bug in DUNVIEW.C for versions compiled with NOCOPYPROTECTION where things were not drawn on D3C teleporter tiles.
References to G0374_l_WatchdogTime_CPSE and F0256_TIMELINE_ProcessEvent53_Watchdog_CPSE have been included in NOCOPYPROTECTION block because they are part of CPSE (confirmed in the DM Demo on Amiga which is not copy protected).
Added ATARIST.H to include all Atari ST specific definitions and to rename functions that are in the jump table. Function names in the source code are nicer.
Added source code of DMPACK.TOS
TO BE COMPLETED (so many changes and additions)

## Credits

Thanks to the following people who helped me with ReDMCSB:

Paul R. Stevens
  The CSBwin source code helped me to find my way in the machine code at the beginning of the project.
Meynaf
  Meynaf discovered many of the bugs listed in Bugs And Changes, including all those added in release 2.