Malbolge programming

The Malbolge language has eluded many attempts to use it for some years. That was before Lou Scheffer published his cryptanalysis of the encryption algorithm it uses. This article walks the way he opened, explaining many of his findings in detail and other caveats that must be taken into account not mentioned by him.

Weaknesses

Malbolge's probably biggest piece of evilness comes from the encryption of instructions as they are executed. That encryption, fortunately, has a few weaknesses that make writing Malbolge programs feasible.

Jumps are not encrypted

First of all let's examine the order in which instruction fetching and execution is performed:

1. Fetch the instruction from [C] and decrypt it.
2. Execute the instruction.
3. Encrypt the byte at [C].
4. Increment C.

In the case of the jump instruction, whose execution has the effect of changing the value of the code pointer C in step 2 above, the memory position that gets encrypted via step 3 is the final value of the code pointer, i.e. the address previous to the target of the jump, instead of the jump instruction itself which remains unencrypted. That's a great advantage as we will see later.

Cycles of length 2

Another weakness that can be exploited is the existence of length-2 cycles in the encryption step. Every possible instruction can be written as a 2-cycle in which the other instruction in the cycle is a NOP, that is, when an instruction is executed it turns into a NOP and when that NOP is executed it turns into the original instruction.

Here's a table of these memory addresses modulo 94 allowing period-2 instructions where the second is a NOP, together with the instruction itself (there are exactly two possible addresses for each of these instructions, so both are listed):

Address (mod 94)	Alternative address (mod 94)	Instruction
25	29	<
43	47	/
59	63	*
60	64	j
82	86	p

The remaining three instructions are irrelevant here: v is executed at most once per program, i is not encrypted as explained above, and o is part of the immutable NOPs mentioned below and the cycle length is not important.

Immutable NOPs

The last weakness that makes it practical to write Malbolge programs is the existence of at least one immutable NOP for every possible memory address. An immutable NOP is an instruction that always behaves as a NOP no matter the number of times it is executed. However very few addresses allow to directly enter immutable NOPs into the code because the range of allowed values in the source code is very limited. (Lou Scheffer notes that such values can always be entered by using a bug in the reference interpreter which allows values greater than 126 to be entered, then rotating with the * instruction, but other authors consider that making use of that bug is cheating.)

Note the distinction between the o instruction and any of the other NOPs: the former may be entered directly into the code while the latter can only be obtained by indirect means. Both can be immutable NOPs, though, depending on the address. The following addresses modulo 94 allow to directly enter an immutable NOP into the code by using the o instruction:

6, 8, 10, 17, 26, 27, 37, 42, 48, 51, 82, 86, 88, 92

In memory addresses other than these the o (NOP) instructions will mutate into a non-NOP instruction after a variable number of executions. For example, an o executed at position 0 modulo 94 will become a j after 29 executions.

The values 70 and 74 form the 2-cycle: an instruction with value 70 becomes 74 when executed and 74 becomes 70 and this is independent of the memory address (what is dependent is the meaning of that value). They are immutable NOPs for most addresses modulo 94. The following table lists all the addresses that are an exception to this rule, together with sample values which are immutable NOPs for them:

Address (mod 94)	Value
7	60
11	58
24	60
25	60
28	60
29	60
43	60
47	58
59	60
60	58
63	60
64	60
82	62, 80
86	60, 76

The importance of immutable NOPs can easily be seen by realizing that the data pointer D is incremented with every instruction executed, just as the code pointer, so in order to position the data pointer as required it's sometimes necessary to advance it by inserting NOP instructions in the code.

Putting all together

We'll see now how to take advantage of these weaknesses to write actual programs.

Program flux

Let's assume we want to execute the following code (as in the cat program):

1. Input a character.
2. Output the character.
3. Jump to step 1.

Easy as it looks, it's not so easy to write in Malbolge. To start with, this must be translated to the following:

1. Input a character (at address 43 mod 94)
2. Jump to address 25 mod 94.
3. Output a character (at address 25 mod 94)
4. Jump to address 60 mod 94.
5. Reload the data pointer to start again.
6. Jump to address 43 mod 94.

Since the instructions are at addresses which form a 2-cycle, in the first execution all instructions will perform their function while in the second they will act as NOPs, then the cycle will start again.

Now it starts to look more promising, doesn't it? Unfortunately that's not the whole story.

Store operation

Crazy as it is, the crazy operator can be very useful. At a minimum it provides a mechanism for storing values into memory, which is necessary for almost any operation except the most basic ones as the above. For example, checking for EOF before printing the character is not possible without using at least a partial version of the store operation, because there's no way to examine the contents of the accumulator without altering it.

It has to be made in several steps. Prior to the store itself the memory address <addr> in which it is performed must be initialized to 1111111111 ternary (29524 decimal). This can be done in this way:

1. Set A to 1111111111t (29524 decimal).
2. Op into <addr>.
3. Op into <addr>.

After step 3, the memory word at <addr> will contain 1111111111t no matter the initial value it contained. Now <addr> is ready for a value to be stored in it.

The store of the accumulator A into memory now consists of two steps: first OP the value into a location already containing 1111111111t; (this will swap the 0's and 1's in A); then OP the resulting value into <addr> (this will unswap the 0's and 1's, leaving the original value stored in both A and <addr>). Note that this method makes it necessary to perform the above 3 steps into just another memory address. That's part of the fun of writing Malbolge programs.

Load operation

There are two simple(ish) ways of loading a value from memory into A; a straightforward one is to perform ten rotates, but this is very costly. There's another one using the crazy operator: load A with 2222222222t (this requires just one rotation), then OP into the address with the value to load, then load A again with 2222222222t, then OP again into that address. After these operations the accumulator will hold the value originally present in that address.

Not so easy as it looks

Now that we've reached the point where Scheffer stops let's continue from there, pointing out the problems that are encountered on the way. For now we'll assume that the memory can be preloaded at will, even if that's not the case.

Data pointer load operations need fixup

Let's remember the algorithm for writing a cat program which does not stop on EOF:

1. Input a character (at address 43 mod 94)
2. Jump to address 25 mod 94.
3. Output a character (at address 25 mod 94)
4. Jump to address 60 mod 94.
5. Reload the data pointer to start again.
6. Jump to address 43 mod 94.

The first point to note is that step 5 can't be performed every two cycles: it must take effect immediately or otherwise the jump addresses have to be repeated again, meaning an avoidable waste of preinitialized data space. The solution to this problem is to revert the j instruction at step 5 just after it's executed. The way of doing this is to re-execute or "pseudo-execute" it (a pseudo-execution means to jump to the instruction immediately following it, so that the encryption step is performed on it anyway). We add a step 5b executed after step 5:

5b. Encrypt the j instruction of step 5.

This will complete the simplified version of the cat program. The design involves working with both the data and the code section at the same time, keeping track especially of the value of the D register, as follows (the choice of 97 as the start of the data area is arbitrary):

Data:

Address	Content
97	60
98	42
99	(unused)
100	24
101	(unused)
102	59
103	96

Code:

Step	C register	D register	Content of [D]	Ins.	C after	D after
1	43	99	-	/	-	-
2	44	100	24	i	24	-
3	25	101	-	<	-	-
4	26	102	59	i	59	-
5	60	103	96	j	-	96
5b	61	97	60	i	60	-
6	61	98	42	i	42	-

(Remember that both C and D are incremented between steps, and that the final value of C prior to the increment is the position that gets encrypted.)

This will loop forever; every two iterations it will input a byte and output it, and execute two NOPs at the next iteration. It does not stop on EOF; instead it outputs 2222222222t mod 256 = 168 repeatedly.

Now it should be apparent that it's possible to achieve execution of arbitrary code by means of jumping to the places where the instructions are to be executed, but there are still a few problems that need to be addressed: the overhead due to data manipulation and the initialization of memory with the desired values.

Initialization of memory

We've assumed that the memory can be preloaded at will, even if that's not the case. Why? Because it's possible (in principle) to create an initialization routine that is executed only once, with no loops or repetitions, so that there's no need to care about self-encryption. That routine's mission is to set up the memory just as needed. The problem is that the routine can be very expensive in terms of number of instructions used: many instructions may be needed for one single memory word to reach the desired value. Fortunately it's much easier in Malbolge to write execute-once code than reusable code.

Overhead due to data manipulation

With the programming method exposed above, when a memory word at address <addr> needs to be manipulated (e.g. for a store operation), for each instruction that acts on it there's a need of:

• A data pointer that positions the data register before it via a j instruction (it can be before or after <addr>).
• A program pointer to fix up that j instruction.
• A program pointer that jumps to the instruction that manipulates <addr>.
• A program pointer that jumps to the next instruction, which is probably a j if more operations on <addr> are needed.
• A certain number of immutable NOPs around the instruction that make the data register skip other words used to manipulate the value at <addr> (if it's the only instruction manipulating <addr>, then these are not necessary).

As we've explained things, it's not possible to reuse an instruction which already has the desired number of immutable NOPs around it in the same turn of the main loop, because the second time it's executed it acts as a NOP. This means that either of these two approaches has to be taken: either the instructions have to be allocated (in different addresses which have the same value mod 94) or they have to be fixed up on the fly in the same manner as the j instruction was. The second approach is by far the most desirable one because it means just one extra program pointer per instruction, while the first one implies initialization of lots of immutable NOPs and allocation of many extra instructions. So we add one extra word of overhead to the ones already stated:

• A program pointer to fix up the data manipulation instruction for reuse.

Now it may be more apparent why the approach of making ten rotate operations for one load was not the preferred one, as that would mean ten times the overhead explained above plus the initialization of it all.

Example: How to store the accumulator into memory (long)

Here's an example of a subprogram that stores the accumulator into a memory position, for the purpose of illustrating how the influence of the overhead mentioned above applies to Malbolge programs. Please note that the code is untested and there might be bugs; it's more an example than anything else. It's possible to reduce the total size, but not much. The code pointers use labels while the data addresses are expressed numerically. Address 200 is chosen as the target of the store/load operation and address 300 is chosen as the ancillary address that has to be filled with 1111111111t as part of the store operation. All instructions except i are assumed to be length-2 cycles. The labels for code pointers represent the address of the memory word prior to the address where the label points to. The labels starting with "R_" are the restoring addresses of the corresponding instructions. Thus, code pointers with this prefix directly point to the command's address instead of the memory word before the command. In general, special care must be taken to ensure that the address prior to the target of a jump always contains a character in the printable ASCII range (33-126) or the reference interpreter may crash. Execution starts with data register pointing to address 400.

Code:

Label	Command
OPR	p
	i

Label	Command
ROT	*
	i

Label	Command
MOVD	j
	i

Label	Command
LOOP	j
	i

Label	Command
RETURN_FLAG_1	j
	i

Label	Command
RETURN_FLAG_2	j
	i

Data starting at address 199 (target variable):

Address	Content	Comment
199	OPR	Access target variable
200	(initial value is irrelevant)	Target varible
201	R_OPR	Restore OPR
202	R_MOVD	Restore MOVD that has been used to jump to address 199
203	RETURN_FLAG_1	Test first return flag (the j command is intact iff the flag is set)
204	412	Return to address 412 if return flag 1 was set
205	R_RETURN_FLAG_1	Destroy return flag 1
206	RETURN_FLAG_2	Test second return flag
207	505	Return to address 505 if return flag 1 was set
208	R_RETURN_FLAG_2	Destroy return flag 2 (only necessary if further return flags follow)

Data starting at address 299 (temporary variable):

Address	Content
299	OPR
300	(initial value is irrelevant)
301	R_OPR
302	R_MOVD
303	RETURN_FLAG_1
304	407
305	R_RETURN_FLAG_1
306	RETURN_FLAG_2
307	502
308	R_RETURN_FLAG_2

Data starting at address 400 (initialization):

Address	Content	Comment
400	R_RETURN_FLAG_1	Unset flags (destroy j command)
401	R_RETURN_FLAG_2
402	ROT	Load 1111111111t
403	1111111111t
404	R_ROT
405	R_RETURN_FLAG_1	Store D register by setting return flag 1
406	MOVD
407	298	Write A register into tmp
408	LOOP	Write A register into tmp again
409	404
410	R_RETURN_FLAG_1	Store D register by setting return flag 1
411	MOVD
412	198	Write A register into val
413	LOOP	Write A register into tmp again
414	409
415	(fetch value that should be stored)

Data starting at address 500 (storing the value):

Address	Content	Comment
500	R_RETURN_FLAG_2	Store D register by setting return flag 2
501	MOVD
502	298	Write A register into tmp
503	R_RETURN_FLAG_2	Store D register by setting return flag 2
504	MOVD
505	198	Write A register into val
506	(continuation of program)

Trace:

Label	D register	Content of [D]	Ins.	Comment
...	400	R_RETURN_FLAG_1	i	Entry
R_RETURN_FLAG_1	401	R_RETURN_FLAG_2	i	Initialize return flags
R_RETURN_FLAG_2	402	ROT	i
ROT	403	1111111111t	*	Load A with all 1's
R_ROT	404	R_ROT	i
R_ROT	405	R_RETURN_FLAG1	i
R_RETURN_FLAG1	406	MOVD	i	Save D register
MOVD	407	298	j
R_MOVD	299	OPR	i
OPR	300	??????????t	p	Opr all 1's into [300]
R_OPR	301	R_OPR	i
R_OPR	302	R_MOVD	i
R_MOVD	303	RETURN_FLAG_1	i
RETURN_FLAG_1	304	407	j	Restore D register
R_RETURN_FLAG_1	408	LOOP	i
LOOP	409	404	j	Test loop condition -> opr A into [300] again
R_LOOP	405	R_RETURN_FLAG1	i
R_RETURN_FLAG1	406	MOVD	i	Save D register
MOVD	407	298	j
R_MOVD	299	OPR	i
OPR	300	??????????t	p	Opr into [300], resulting in [300] containing all 1's
R_OPR	301	R_OPR	i
R_OPR	302	R_MOVD	i
R_MOVD	303	RETURN_FLAG_1	i
RETURN_FLAG_1	304	407	j	Restore D register
R_RETURN_FLAG_1	408	LOOP	i
LOOP	409	404	o	Test loop condition -> exit loop
R_LOOP	410	R_RETURN_FLAG_1	i
R_RETURN_FLAG1	411	MOVD	i
MOVD	412	198	j
R_MOVD	199	OPR	i
OPR	200	??????????t	p	Opr all 1's into [200]
R_OPR	201	R_OPR	i
R_OPR	202	R_MOVD	i
R_MOVD	203	RETURN_FLAG_1	i
RETURN_FLAG_1	204	412	j	Restore D register
R_RETURN_FLAG_1	413	LOOP	i
LOOP	414	409	j	Test loop condition -> opr A into [200] again
R_LOOP	410	R_RETURN_FLAG1	i
R_RETURN_FLAG1	411	MOVD	i	Save D register
MOVD	412	198	j
R_MOVD	199	OPR	i
OPR	200	??????????t	p	Opr into [200], resulting in [200] containing all 1's
R_OPR	201	R_OPR	i
R_OPR	202	R_MOVD	i
R_MOVD	203	RETURN_FLAG_1	i
RETURN_FLAG_1	204	412	j	Restore D register
R_RETURN_FLAG_1	413	LOOP	i
LOOP	414	409	o	Test loop condition -> exit loop
R_LOOP	415	...	i	Do something that loads the accumulator with the value to store.
...	500	R_RETURN_FLAG_2	i
R_RETURN_FLAG_2	501	MOVD	i	Save D register
MOVD	502	298	j
R_MOVD	299	OPR	i
OPR	300	1111111111t	p	Opr A into [300]
R_OPR	301	R_OPR	i
R_OPR	302	R_MOVD	i
R_MOVD	303	RETURN_FLAG_1	i
RETURN_FLAG_1	304	407	o	Return flag 1 was not set
R_RETURN_FLAG_1	305	R_RETURN_FLAG_1	i
R_RETURN_FLAG_1	306	RETURN_FLAG_2	i	Unset return flag 1 again
RETURN_FLAG_2	307	502	j	Restore D register
R_RETURN_FLAG_2	503	R_RETURN_FLAG_2	i
R_RETURN_FLAG_2	504	MOVD	i	Save D register
MOVD	505	198	j
R_MOVD	199	OPR	i
OPR	200	1111111111t	p	Opr A into [200]
R_OPR	201	R_OPR	i
R_OPR	202	R_MOVD	i
R_MOVD	203	RETURN_FLAG_1	i
RETURN_FLAG_1	204	412	o	Return flag 1 was not set
R_RETURN_FLAG_1	205	R_RETURN_FLAG_1	i
R_RETURN_FLAG_1	206	RETURN_FLAG_2	i	Unset return flag 1 again
RETURN_FLAG_2	207	505	j	Restore D register
R_RETURN_FLAG_2	506	...	i	Go on with program logic

Reducing the number of immutable NOPs

Instead of controlling the program flow with the code register, which means that all commands are written in their correct order filled with immutable NOPs, it is possible to control the program flow using the data register. This technique has been developed by Hisashi Iizawa et al. and has been used in their 99 bottles of beer program.

Using this technique every instruction in Malbolge (except Jmp) will only occur once in the whole program at a position where the encryption function has a 2-cycle, followed by a Jmp instruction (there may be some exceptions, but this is the basic idea). Thus we know that after the execution of every instruction a Jmp instruction will follow.

Example: Loading 0t1111111111 into the A register

Code pointer to rotate instruction.

0t1111111111

Code pointer to rotate instruction + 1 (restore)

The next data word will be a pointer to another Malbolge command, e.g. the crazy instruction, followed by the cell used by it.

When we control the program flow with the D register, branches can be executed by MoveD. If we use a MoveD instruction with a 2-cycle of the encryption function without a restore operation, we can build a loop that will be executed two times.

Using this technique it's possible to save many immutable NOPs, so the number of cells that have to be initialized decreases dramatically. Simple programs in Malbolge still need many memory cells. However, with this technique programs like a cat that halts on EOF are possible.

Programming with memory addresses is very confusing, and it may be time-consuming to manually write code in Malbolge to initialize the memory cells that are needed. To avoid this one can use a Malbolge assembler. Such an assembler can be found in the external resources: LMAO (Low-level Malbolge Assembler, Ooh!). LMAO comes with some examples written in the Malbolge assembler language HeLL (Hellish Low-level Language), so the user can understand the way HeLL works. One of the examples is a cat program that halts on EOF.

Introducing assembly language for Malbolge

Let's consider the example above and introduce labels for data pointers.

Variable val (offset 199):

Label	Value
opr_val	OPR
val	(initial value is irrelevant)
	R_OPR
	R_MOVD
	FLAG1
	val_back1
	R_RETURN_FLAG_1
	FLAG2
	val_back2
	R_RETURN_FLAG_2

Variable tmp (offset 299):

Label	Value
opr_tmp	OPR
tmp	(initial value is irrelevant)
	R_OPR
	R_MOVD
	FLAG1
	tmp_back1
	R_RETURN_FLAG_1
	FLAG2
	tmp_back2
	R_RETURN_FLAG_2

Initialization (offset 400):

Label	Value
ENTRY	ROT
	1111111111t
	R_ROT
clear_tmp	R_RETURN_FLAG_1
	MOVD
	opr_tmp
tmp_back1	LOOP
	clear_tmp
clear_val	R_RETURN_FLAG_1
	MOVD
	opr_val
val_back1	LOOP
	clear_val
	(fetch value that should be stored)

Write value (offset 500):

Label	Value
write	R_RETURN_FLAG_2
	MOVD
	opr_tmp
tmp_back2	R_RETURN_FLAG_2
	MOVD
	opr_val
val_back2	(continuation of program)

We just introduced a Malbolge assembly language and got rid of absolute positions for code or data sections. Thus, the code above can be extended easily. A Malbolge program can be created from the assembly program above as follows. We must choose positions of code and data sections, replace labels by the address of the memory word prior to the address where the label points to, and write use-once Malbolge code to initialize everything. However, one may use a Malbolge assembler in order to automatize this process.

External resources

• Lou Scheffer's discussion about Malbolge programming
• Matthias Ernst's Malbolge assembler LMAO
• Online Malbolge assembler
• Normalized Malbolge to Malbolge compiler.