Writing an emulator for a slightly unusual abstract FSM

what would be a relatively hassle-free way of writing an elegant, intuitive code that emulates a finite state machine (no jumps or conditionals) with a self-modifying instruction set (or maybe just two instruction sets: one for modifying data, other for modifying the first instruction set)? I don't care about performance right now (I doubt it will get to the stage when I need to care about that but if it does, some fuckery with C function pointers will be inevitable; right now I care about readability and being able to prototype quickly) so functional is OK but I'm thinking of instructions having four-bit length and I'm not sure how good purefuncs are at handling that

verilog or vhdl?

>>2

right now I just need something for a software implementation

You need to define your problem more. There's about 15 different ways I could parse "emulates a finite state machine with a self-modifying instruction set".

>>4
think of it as an emulation of a simple computer (not Turing complete though because no jumps and conditionals) which takes two separate input streams: first contains instructions and left operands (from now on, 'program'), second contains right operands (from now on, 'data'). output is just a stream of results of operations. simple, isn't it?

now, instead of having a usual instruction set, have a built-in list of allowed instructions. mapping those to opcodes should be the first part of the 'program' stream. when you have this, add another instruction set (with mappings also provided with 'program') which transforms the previous instruction set.

I'm thinking of having a constant length for opcode for simplicity. because I don't need many instructions (and I don't want to input hundreds of them with each program), I'm thinking of 4 bits for instruction and a byte for operand. thus, an access to data smaller than single bytes would be nice.

NIBBLE MY ANUS

What the fuck does this have to do with FSMs? You're throwing shit at the wall.

>>7
I'm not good with semantics. it's not a Turing machine, I'm not sure it's really a computer either. what would that be? a pushdown automaton?

If I understand this, you're saying you have >16 instructions that you want to put into a 4 bit opcode. And plan to build an index table to map them. Guess you could reserve one opcode for remapping and have a 15 instruction table. Will your remapping operands be in the data stream?

>>9
not really. a hypothetical opcode 0x012 will result in the execution of:
- instruction 0x0 from the first instruction set with 0x12 as a left operand (e.g. add 0x12 to the current byte of 'data' stream)
- instruction 0x0 from second instruction set (e.g. swap instructions 0x0 and 0xF in the first instruction set)

>>8
So its SIMILAR to a Turing machine but doesn't have conditional branching?

>>11
more or less. it's generally not designed for general-purpose computation or for being programmed by humans

>>8
Finite State Automation is practically equivalent to Turing Machine. The only difference is that Turing Machine has "infinite" tape, which is a property completely useless for real world. BTW, there is _NO halting problem_ for real world computers, because halting problems exists only when memory is inifinite

>>8
It would be called a list of instructions. FSM can have conditionals. A state transition function in a FSM could be:
f(d0, 0) = d1
f(d0, 1) = d2
That's just a piecewise function, dependent on the next input symbol.

>>13
it's nice that you mentioned halting problems because one of the ideas behind this machine is that it will always halt, regardless of program and data. also, every program is a valid program.

anyway, we're arguing about semantics of FSMs, Turing machines and pushdown automata instead of trying to find the answer to the topic's question: what would be the best way of emulating such thing if right now I'm more concerned with the code being easy to read (and understand, obviously) than with performance?

>>15
non-halting programs can still be valid.

>>16
I know, that's why I said 'also'. as in 'every program is valid AND every program is halting'.

finite state machine
no jumps or conditionals

FAIL

great, now this thread is going to be about Cudder and cudderhaters

Yay!

>>17
non-halting program is halted in a cycle.

I prefer polka dot.

>>15
What are you doing? It sounds like you are trying to make a genetic algorithm to search the space of possible codes with these programs, but that's just my guess.

>>15
If the instruction set is closed under operations, then have a fixed length instruction word with a fixed number of argument bits and instruction bits. For 16 instructions, make the first four correspond to the instruction, and the last twelve correspond to an address, for example. Twelve address bits mean you can get 4096 words on the input tape, which should be plenty for whatever you are trying to do, and not have to worry about addressing outside of memory. Store each instruction in a structure containing the 16 bit word and a union with bitfields. Then iterate over the input tape with a big switch statement on the instruction bits of that union field. To plan out the instructions, try writing simple programs to get a feel for what you like. For example, look at the program I made with list operations in https://bbs.progrider.org/prog/read/1444460614. That uses loops, thus conditionals and jumps, but it could be unrolled easily to make fibs.

>>23
not genetic algorithm, although this would be one possible use for such architecture. I can think of only other one and I think you'll figure it out when I add two constraints to the mix:
- every instruction must be a bijection so that given a program and its output, it's trivial to create a program which calculates the initial input
- if this ever reaches production (>imblyign), each instruction should take equal amount of time to execute
>>24
I'm not sure if switch is a way to go here. remember, 0x012 might mean 'add 0x12' in one step of execution and 'xor 0x12' in another.

>>25

every instruction must be a bijection so that given a program and its output, it's trivial to create a program which calculates the initial input

Cannot be done like this. 2+x=4 can be uniquely solved, but y+x=4 cannot be. Even AND, OR, and XOR cannot be uniquely mapped to their original inputs based only on an output. Just thinking about it now, I'm don't see how any binary function can avoid information loss without preserving one of the inputs, but that would defeat the purpose of being reversible.

if this ever reaches production (>imblyign), each instruction should take equal amount of time to execute

That's a waste of time. A naive implementation of multiplication (the one your processor uses, not fancy shit in bignum libraries) is O(n²), while addition is O(n), where n is the number of bits. Addition (or any other simpler instruction, such as logical operations) is going to have to stall 240 operations to have the same operation as multiplication on a 16 bit number.

0x012 might mean 'add 0x12' in one step of execution and 'xor 0x12' in another.

Did you mean "self-modifying instruction set" literally, as in, the instructions that opcodes map to are changed? Why not just change the program itself? Well, if that's what you want, there's this:
int add = 0, sub = 1, ..., swap_op = 15;
eval (int opcode, int param, int param2) {
if(opcode == add) ...;
else if(opcode == sub) ...;
else if(opcode == swap_op) int a = param; param = param2; param2 = a;
}
Such that eval (15, 0, 1) changes the meaning of opcodes.

>>26

Cannot be done like this. 2+x=4 can be uniquely solved, but y+x=4 cannot be. Even AND, OR, and XOR cannot be uniquely mapped to their original inputs based only on an output. Just thinking about it now, I'm don't see how any binary function can avoid information loss without preserving one of the inputs, but that would defeat the purpose of being reversible.

program consists of instructions and left hand operands. input data consists of right operands. output consists of results. when you have left operands, instructions and results and each instruction is a bijection, finding right operands is first-grade math.

think about this - program cosnsits of instructions which translate to things like:
add 0x01 to first byte of input
bitwise rotate right by 0x02 the second byte of input
xor 0x03 to the second byte of input
output results

when you have an output stream and a program, the program to calculate the initial input stream would look like:
substract 0x01 from the first byte of output
bitwise rotate left by 0x02 the second byte of output
xor 0x01 to the first byte of output
output results

That's a waste of time. A naive implementation of multiplication (the one your processor uses, not fancy shit in bignum libraries) is O(n2), while addition is O(n), where n is the number of bits. Addition (or any other simpler instruction, such as logical operations) is going to have to stall 240 operations to have the same operation as multiplication on a 16 bit number.

who said I need multiplication? this is not a general purpose computer and it's not supposed to be programmed by humans. it's designed with a specific goal in mind and this goal doesn't require multiplication.

Did you mean "self-modifying instruction set" literally, as in, the instructions that opcodes map to are changed?

yes, and the initial mappings are a part of each program.

Why not just change the program itself?

imagine you have a 2GB program (which is not that unlikely in this case) and each instruction modifies every instruction that happens after it. is nearly almost quadratic in relation to program size and modifications that happen early in the program take longer to execute than those which happen near the end.

now, imagine you have 16 opcdoes, each mapped to a single instruction. each instruction modifies the opcode array/list/whatever else data structure I pick. complexity is now linear in relation to program size and if the modifications are chosen carefully, each modification can happen in constant time.

xor 0x03 to the second byte of input
xor 0x03 to the second byte of input

should be 'third byte'

>>18
Hello, Cudder! Will your browser get a preview release?

>>29
Preview that: *releases a penis*

>>27
You need to be very particular with your instruction selection to retain reversibility. Things like bit shifting can be irreversible as well.

>>26
Equal execution time is often required of encryption algorithms to avoid timing attacks. However, OP is doing this completely boneheadedly. What should be done is to ensure that the two branches that a decision can make result in the same execution time, with padding on the slower branch, not trying for equal execution time of every single instruction. Plus, since she doesn't have any branches anyway, it's all moot with regards to timing attacks.

>>31

You need to be very particular with your instruction selection to retain reversibility. Things like bit shifting can be irreversible as well.

the only shifting I'm using is rotation which is reversible

Equal execution time is often required of encryption algorithms to avoid timing attacks.

finally, someone with a brain

However, OP is doing this completely boneheadedly. What should be done is to ensure that the two branches that a decision can make result in the same execution time, with padding on the slower branch, not trying for equal execution time of every single instruction.

that's what I'm talking about, 'instruction' in this case refers to the instruction on the abstract machine, not on a CPU on which it's emulated.

Plus, since she doesn't have any branches anyway, it's all moot with regards to timing attacks.

timing is there so you can't identify which instruction is being executed. that's because 'program' stream is key and 'data' stream is plaintext.

>>32

the only shifting I'm using is rotation which is reversible

Then use the reversible version of rotation.

>>33

I'm using reversible function
if you're using a reversible function you should use a reversible function

what a waste of dubs

It looks like you want to create a one time pad. Know that this is completely pointless. Even a mere XOR on all elements from the key to the data is provably perfect and unbreakable. It's a waste of time to do any more.

>>35
I want to create a stream cipher (more precisely: something like a 'mode of operation' for arbitrary stream ciphers). stream ciphers in general are based on one-time pads and while they're not as secure, they'res also less impractical