Muxcomp

From Esolang
Jump to: navigation, search

Muxcomp uses an idea from FPGA logic block design: an N:1 multiplexer can be used to implement an arbitrary Boolean function of log_2(N) inputs. For example, to implement any Boolean function of 5 bits, you can use 32 bits of memory and a 32:1 mux with 5 select lines. The result of this would always be a single bit.

Most machines (and, therefore, languages) operate on 32 or 64 bits at a time. The muxcomp32 and muxcomp64 languages are two specific implementations of the muxcomp idea, simply replicating a muxcomp bit-slice 32 or 64 times respectively.

The muxcompN language uses a random-access memory model with N address bits. In other words, muxcomp32 addresses 32 bits of memory and muxcomp64 addresses 64 bits of memory, and so on.

The muxcomp32 instruction format is as follows:

DD sel0
DD sel1
DD sel2
DD sel3
DD sel4
DD op
DD res

Each word is actually a 32-bit pointer, not an immediate value. This permits separation of code and data, if desired. The sel0-sel4 words encode the bit-slices of the select lines. The op word is the encoding of the Boolean function which this instruction implements.

The muxcomp64 instruction format is almost identical, it simply includes one more select word (and words are 64 bits, not 32):

DQ sel0
DQ sel1
DQ sel2
DQ sel3
DQ sel4
DQ sel5
DQ op
DQ res

Here are some example muxcomp64 instructions:

AND:
sel0
sel1
sel2
sel3
sel4
sel5
8000000000000000 #op
res

(numeric values in hexadecimal)

This performs a bitwise-AND of sel0-sel5. Let's assign a value to sel0 and sel1 and set all other fields to ff's:

0123456789abcdef # sel0
123456789abcdef0 # sel1
ffffffffffffffff # ...
ffffffffffffffff
ffffffffffffffff
ffffffffffffffff
8000000000000000 #op 

The result of executing this is:

0020446088a8cce0

Here's another example Boolean function:

XOR:
0123456789abcdef # sel0
123456789abcdef0 # sel1
0000000000000000 # ...
0000000000000000
0000000000000000
0000000000000000
6996966996696996 #op

The result of executing this is:

1317131f1317131f

AND and XOR are common, simple Boolean functions but you can implement more complex functions (any Boolean function of 6 inputs), such as F=(XY + Z). Combining multiple Boolean operations into a single instruction can be used to save computation steps in muxcomp.

You can also rotate the op (instruction shown with a sample value in op):

ROL4:
aaaaaaaaaaaaaaaa #sel0
cccccccccccccccc #sel1
0f0f0f0f0f0f0f0f #sel2
f00ff00ff00ff00f #sel3
fff0000ffff0000f #sel4
fffffff00000000f #sel5
0123456789abcdef #op

The result of executing this is:

123456789abcdef0

One memory location is defined as the Program Counter (PC). Writing to this memory location has the effect of altering the flow of evaluation of instructions. The muxcomp32 language auto-increments the PC by 7 (muxcomp64 increments by 8) before each instruction is executed. If the instruction writes to the PC, the next instruction will be evaluated at the new location pointed to by the PC.

A simulator has been written in Perl with a small library of Boolean functions and some shifts. An assembler is under construction and a planned implementation of a Kogge-Stone adder will illustrate how this minimal language can be used to perform complex operations.

The planned assembler will implement two important macros, called SLICE and BOOL.

SLICE (for muxcompN) accepts a list N values, between 0 and N-1. These are encoded as slices in the select lines. For example, to implement the ROL4 instruction above:

ROL4: SLICE[4..63,0..3]

The BOOL macro accepts any N-bit value, which is applied to the select lines. For example, to implement the XOR function above:

XOR: BOOL[6996966996696996]

ClaytonB 00:25, 15 October 2010 (UTC)