Hi

I am certain this has been done before, but as a thought experiment I wanted to explore it. It became apparent that my thought may have lead to an efficient way to compress code, or maybe it would only bloat it.

Anyway, to give you an idea, I though that I could simulate a One-opcode CPU using 6502 assembly. The program would simply take the one-opcode code and read it with 6502 assembly and do its instruction(s).

My one-opcode instruction set is very simple as it only contains one opcode. In fact you don't need to store the opcode since its always the same. I called it "MAB" as a shortening of Move Add Branch:

MAB $XX $YY

The full instruction would be 2 bytes with first byte being $XX and second being $YY. The $XX (and $YY) points to a register which for the 6502 could be the Zeropage. The instruction moves data from the memory location in register $XX to the memory location in register $YY.

To do something else we have some special cases. Register $00 is not used and in the case the $XX=$00, the instruction will move data into register $YY. This data is contained in the two next bytes so that the opcode looks like:

MAB $00 $YY $DATA

Were $DATA is a 16-bit value contained in two bytes.

We can continue this with another special case $YY=$00 in which we do an ADC and/or SBC:

MAB $XX $00 $ADD $SUB

Were $XX points to the memory location $DATA so that $DATA= $DATA + $ADD - $SUB

For branches one could have a special case were $XX=$YY=$00... and so on.

You get the idea.

It looks like this could be a compact way of running a program, but it could also be a way to bloat the code. I have no idea. Does anyone knows of similar ways to code data that has been done in the past? Like in the 60ies or something. I would love to read about it.

Edit: I corrected a few things with respect to the registers being pointers to memory locations..

So an ADC becomes 4 bytes, your address space becomes only 8 bits, and the variety of operations you can carry out is severely restricted. That doesn't sound like good compression to me.

You should definitely look into AcheronVM to see how the professionals do this sort of thing.

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

hmmm, if its thought exercise and ive understood this correctly - then we kinda doing this today when we use Macros.

Again if ive understood you could have mab$ $xx label flags as a branch instruction.
$xx is the value to compare, label the location if the flag is set. One line code vs cmp #xx & bmi label. Maybe 3 bytes vs 4 if it ever became microcode.

But there's times when you need to just compare the flags and not a register say after an addition.
So it becomes mab$ label flags (like bmi label) now hows the system going to know that its a branch and not say a move without adding another byte..

_________________
_________________________________________________________________________
Checkout my 2pass assembler/monitor https://github.com/jdimeglio/6502-Monitor

There is a lot already on this - it's somewhat esoteric/exciting/boring/weird, depending on your point of view..

e.g. https://en.wikipedia.org/wiki/One-instr ... t_computer

There is even a target of LLVM to generate MOV instructions on the x86 - I think this video has it, but I can't find the original I'm thinking of: https://www.youtube.com/watch?v=R7EEoWg6Ekk

It's certinaly NOT compressed code - if you want that, then look at a bytecode VM - e.g. the BCPL Cintcode system - which on my '816 system produces an object file of about 5KB long for my editor where the same editor coded in C (using cc65) compiles to just under 16KB.

I'm not sure if there is one 'true' 6502 opcode that we could use here, however who knows...

I put it in the exciting, but weird category myself!

-Gordon

_________________
--
Gordon Henderson.
See my Ruby 6502 and 65816 SBC projects here: https://projects.drogon.net/ruby/

Hi kakamoms
an interesting idea, I think. Not everyone will get it, but we must expect that.

if it were a single-instruction CPU that you were conjuring into life, that's possible, but is unlikely to be compact. It's of some theoretical interest that a single instruction is enough. But I think it's not practical.

once you introduce your three or four variant forms, you are in the territory of making a small instruction set. Sweet16 is the famous example in the land of 6502. The floating point code in Sinclair's Basic is another example: a small RPN-style calculation language. I think in both those cases it isn't, and doesn't aim to be, a full instruction set.

it may be that a small (interpreted) instruction set would be a handy thing: I suspect that if you restrict to byte-sized encodings and operands, you won't get the density you're looking for. Unfortunately, once you descend to bit-level encodings, you'll lose a lot of performance. It's a tradeoff! But I think it's interesting to explore.

(Maybe I should add: any interpreter is doing this kind of thing, and Forth is the classic example of how to make such an interpreter in an efficient and extensible way. Basic is more familiar. The JVM, and .NET, are perhaps also examples, of a sort.)

A given set of information, like f.ex. a program, has a given entrophy. It's as impossible as a warp drive to represent it with less. Take a good look on what is written about information theory already during the 1950:th. Even if it takes one word to command the execution of a complicated task, the task itself still has to have been explained somewhere. Another invention by Mr Gearlose...

https://en.wikipedia.org/wiki/Huffman_coding

Oh, another good example of a virtual machine, this time for portability not for extensibility: Infocom's z-machine, for interactive fiction.

(If you allow yourself two bytes for an operation, you could push those to the stack and RTS, so you have an indirect threaded interpreter. You have the option of having the routine take further input bytes from the 'instruction' stream - there's bound to be a zero page pointer to act as the virtual PC. If on the other hand you allow yourself only one byte for an operation, you could lookup into a table of 128 addresses of the routines to handle even values, or you could lookup into two tables allowing 256 operations:
and now you've got a bytecode. You could handle subtleties of instruction encoding within the bytecode by having the handlers be duplicated and inspecting the X value, or you could handle variations directly in each of the routines.

Woha! Lots of responses here.. wonderful!

My explanation was probably poor. The registers point to a memory location with the register content being the address. So the basic "instruction" of

MAB $AA, $BB

would be (with X=0):

LDA ($AA,X)
STA ($BB,X)

which is two bytes shorter than 6502 code. And in the basic 6502 you have an address range of 16 bits. With the 6509 that would be 20 bits, or with some other clever banking you can have as many bits as you like...

MAB $AA $00 $ADD $SUB in 6502 terms would be (with X=0):

LDA ($AA,X)
ADC ($ADD,X)
SBC ($SUB,X)
STA ($AA,X)

which is 4 bytes shorter than 6502 code..

An interpreter may look something like (for a short program):



I think the point of this was to see if one could make code that would be more condensed than basic 6502 assembly, in 6502 assembly. It is certainly not easy and neither obvious how to do it. It may also be hard with respect to what rules to use and were to apply them. The interpreter would bloat it if it is too complicated, and a small program would neither help.

The Huffman coding and URISC was interesting read.... it will certainly keep me exited and thinking through the holidays.

Thanks!

Edit: I just saw BigEd's response. The Z-machine (or other high-level languages) reuse more complicated code in order to condense that is being done. I was thinking more towards basic assembly rather than complicated instructions, but I do see the parallel there.

Using a bytecode VM then it's very easy to get very compact code - much tighter than native 6502.

The downside is of-course the size of the VM/interpreter and everything need to support it... In my BCPL (a product of the 60's) system, this is now approaching 16KB of '816 code (it's a 32-bit VM) then there is the run-time library (written in BCPL) which is a modest 10KB of compiled code, but that's shared between all programs/threads. Under that is about 10KB of native OS and behind that is about 48KB of compiled C code running on the AVR host processor to handle IO and the filing system...

The 16-bit version that ran on the BBC Micro was also a 16KB ROM (plus 12KB of native OS plus separate filing system ROMs), but that ROM also contained some of the the run-time library, CLI and some utilities.

It's great that my nice little editor compiles to 5KB of code but knowing that it needs all the above makes it somewhat perplexing at times.

So at what expense... Everything is a trade-off.

-Gordon

_________________
--
Gordon Henderson.
See my Ruby 6502 and 65816 SBC projects here: https://projects.drogon.net/ruby/

Oh, another technical term worth knowing in this context, is Transport-Triggered Architecture. That's where memory operations cause side-effects, typically causing some arithmetic to be done. It allows a store and a load to work as an addition, for example.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

It was full of bugs. That is what I get for just writing something without testing...

Anyway I fixed it a little and added (a few) comments. I also added the special case were one tries to add and subtract the same value (which stores that value instead).

Thank you for that link! That was very interesting reading. I didn't know there was such a thing as a successful commercial product that used this priciple.

You're welcome. Just one thing... I didn't give a link! Do please share what you found...