Writing a BrainF*** to  Malbolge compiler

Malbolge, for those not familiar with it, is a language designed to be difficult (or perhaps impossible - it's not been proved to be Turing complete) to program in. See the link above for the gory details.

Here is an outline of how to build a compiler that takes BF as input, and generates a Malbolge program to do the same thing.  Here we assume we have a loader that lets us put arbitrary instructions and data in arbirtary locations.

We also assume we can work around this problems of self-modifying instructions, using some of the techniques from the original Malboge analysis.

Data representation:

Our compiler will correspond to a model with 243 memory cells, each containing a value 0..242.  We'll use a load /store architecture with an address and an accumulator.  You can increment and decrement the address, and load or store the location at the address into/from and accumulator.  You can increment and decrement the accumulator, and branch differently depending on whether it is 0.

It is easy to convert BF to this model. basically there are ADDRESS instructions '>' and '<', and DATA instructions (all the rest).  When you switch from an address instruction to a data instruction, you need to do a 'load', when you switch back you do a 'store'.  Otherwise all operations work on the accumulator.

Increment/decrement

Arithmetic is not easy given the very limited Malbolge operations.  So we do this by table lookup.  First start with a memory address containing TTTTT11111, where T is a 1 or a 2 (this limits us to 32 tables, but that's more than enough).  Then you OP in the data to be incremented or decremented (either the address counter or the accumulator), which is in the form of 00000XXXXX.  This will generate data contents of the form TTTTTYYYYY, where YYYYY is corresponds 1-to-1 with XXXXX, though not in order (this operation swaps all the 0s and 1s in the number).  This is OK since we are going to use table lookup, so we can scramble the table to compensate for this.

Now, at location TTTTT00000, we start a table of 243 (immutable) NOPs, followed by a LOAD instruction, then 243 more NOPS (actually we want a few more NOPs to get the LOAD on a good cycle location, but the principle is the same.).  Then we do this:

Program counter
 D location
 YYYYY=0
 YYYYY=1
 ...
 YYYYY=242
ROTATE
 2222222222



BRANCH
 TTTTTYYYYY




ANSWER 242
 NOP
 NOP
OP

ANSWER 241
 NOP
 NOP
NOP

.....


NOP

ANSWER 2
 NOP
 NOP
NOP

ANSWER 1
 NOP
 OP
NOP

ANSWER 0
 OP
 NOP
NOP
After the rotate, the A register will contain 2222222222.   Then we will branch to somewhere in the NOP table.  We will do some number of NOPS (242-YYYYY) of them, while the D register advances through all the answers.  At the appropriate point we will do an OP.  Since the A register contains 2222222222, we can get any result we want since an OP with 2 as the A value just results in  the existing memory value with 1 and 2 reversed. 

Unfortunately, this scrambles the value in the lookup table as well.  However, if do the same lookup again, it will scramble it back.  By pre-loading the table correctly, we can make either the first or the second lookup come out right (but not both).

Performance:  take a time proportional to the number of possible cell values.  So it won't be efficient, but that's not our goal here.

Conditional branch

We can do this just like the above.  By replacing the OP with a LOAD, we can do a 243 way computed branch.  For the purposes of our compiler, 242 of the branch addresses will be the same, and 1 (corresponding to 0) will be different.  Thus we can branch to a different address if the data is 0, which is what we need.

Load/Store

Here, how can we load or store a value into the memory array?  We do a very similar trick to the table lookup above.  This lets up apply an OP to a location selected by the ADDR counter.
For a load, we set A to 2222222222. when we do the OP, this sets both A and the location to original value at the location, but with 1 and 2 swapped.  Then exactly the same thing again.  This restores the location to the original value, and sets the A register to the desired result.

A store is more complex.  First, we need to save the A value we want to store (OP it into a location with all 1s - this will swaps the 0s and 1s).  Then we need to prepare the value at the destination address.
Performance:  This takes a number of instructions proportional to the number of words in memory.

Output

This is the simplest operation. Just load the value into A, then do the output instruction

Input

Here the only problem is coping with the EOF, or End Of File.