proj-oot-ootCoreThoughts

name change to 'oot'

---

now, to specify a bit field width which is a power of 2 between 0 and 7, we need to choose between 8 values, which takes 3 bits.

so we can pack together a bunch of bit field width specifications into a few bytes, with 3 bits for each spec. or maybe we should make it 4 bits to be even.

what are some things we may need to specify?

• bit width for opcode
• bit width for pointers
• bit width for registers (if we have registers)
• bit width for max number of local variables (or mb all accessible variables, including non-locals and constants and subprocedure names)
• bit width for max stack depth
• bit width for network addresses and IPC addressses
• bit width for integers
• bit width for floating point
• bit width for characters

that's 9 items, so let's limit ourselves to 8 because it's a power of 2.

--

so i am suggesting that there is a 'self-describing' format for bytecode which specifies these bit widths in the first few bytes. This allows this format to be suitable for embedded as well as desktop encodings. i am not suggesting that most Oot Core bytecode interpreters should actually have the flexibility to accept files with arbitrary values for these bitwidths, just that conceptually it's a good way to specify things.

for example, low-end PIC MCUs had "12-bit instructions" made of "5 address bits to specify the memory operand, and 9-bit branch destinations", e.g. a bit width of 5 for the opcode and 9 for pointers. If we demand Oot bit widths to themselves be powers of 2, that rounds up to 8 bits for instructions and 16 for pointers. Which is not actually very satisfactory.

note that now low-end PICs have about 35 instructions (http://en.wikipedia.org/wiki/PIC_microcontroller#Instruction_set), so they need 6 bits for the opcode. Lua bytecode has 38 opcodes, also using 6 bits ( http://luaforge.net/docman/83/98/ANoFrillsIntroToLua51VMInstructions.pdf ).

which suggests a two-step system:

• use 3-bits to specify the bit width of the specification of the bit-width of the things
• then specify the bit widths of the things

because on embedded systems we wouldn't want each program to waste like 8 bytes specifying these bit widths, even in the fully-describing format.

but this is too much; because 3 bits can specify a 128-bit width specification which can specify bit widths up to 2^(2^7), whereas we only want to specify bit widths up to 2^7. if we had 2 bits, then that's 2^3 instead of 2^7, which is 8, which is right.

so e.g. if the two bits were both 1, that means that the bit width spec for something is one byte. but wait, we never use zero, so if the two bits are both zero, that means the bit width spec is one bit (1 bits or two). if the two bits are 01, that means the spec is two bits (bit widths up to 4), if the two bits are 10, we have a four bit bit width spec (bit widths up to 16), and if the two bits are 11, we have an eight bit bit width spec (bit widths up to 256).

now we'll never really use those first few choices, because even old PICs and Lua need bit widths of 5 or more (we aren't trying to support esoteric computing here, with small bit widths just for the heck of it). So we would always see either 10 or 11. So we really only need 1 bit:

0: 4 bit bitwidth spec 1: 8 bit bitwidth spec

so in the self-describing format, the first byte could contain some bits that choose between 4-bit and 8-bit bitwidth specs.

Alternately, we could assume that tight embedded systems won't use more than a bit width of 16 for anything, and that systems which do have any bit width above 16 won't might a few extra bytes at the beginning of each Oot program, and have just one bit, which selects whether all subsequent bit width specs are 4 bits or 8 bits.

note also that in the case that the bit width specifications only need to go up to 16, we also know that no bit width will be below 4, so maybe we can save a couple more bits with some clever encoding, although that's probably more trouble than it's worth.

so if we have 8 things that need to be specified, we have a leading byte with that bit and maybe some other spec junk, then we waste either 4 or 8 bytes on the bit width specifications. What if we are so embedded that we don't want to waste 5 bytes? Maybe add another bit that allows us to turn off specification and accept the minimal values (probably 6 or 7 bit opcodes, 8 bit integers, 8 or 9 bit pointers, etc).

Note that PICS originally had 12-bit instructions, AVR has 16-bit instructions, MCP430 has 16-bit instructions, ARM Thumb originally had 16-bit instructions and now has 32, Lua bytecode has 32-bit instructions; so at a minimum the total number of bits per instruction (including opcode and operands) will be >=8, and >=16 most likely. EmbedVM?, which take only 3 KiB? on an AVR, has 8-bit instructions with some instructions taking 8- or 16-bit extensions. PyMite? has 8-bit opcodes and some instructions take 16-bit arguments (all bytecodes after 90 (0x5A)). eLua seems to follow Lua: https://github.com/elua/elua/blob/master/src/lua/lopcodes.h . What does Java Card do? I know Java Card opcodes are 8-bits, but how long are potential arguments?

So let's say that the Oot word size is 16 bits at a minimum, and that Oot opcodes are 6 bits at a minimum. So an instruction has at least 10 bits besides the opcode for operands, etc. If we tried to fit all instructions into 16 bits, with no extended instructions for e.g. memory addressing, and if the pointer size was at least 8 bits, then we'd only have 2 bits for another operand, so a LOAD or STORE opcode could only have 4 registers. Or, like PIC, we could replace LOAD and STORE with instructions that implicitly choose a register. One choice (not PIC's) would be to have LOAD and STORE but only to an implicit register, and then we have to follow or precede them with a general MOV. A MOV has 10 bits for all operands so it could have 5 bits per reg, so at most 32 regs. PIC's style is rather to have a MOV with one implicit register, in which case we'd have 10 bits to choose the other one (1024 registers, which i guess only makes sense if you memory-map them like PIC).

That all seems pretty tight, and i think i would rather have some more bits for modes to make the instructions more orthogonal. It seems like the most embedded systems have either 16-bit instruction sizes, or 8-bit instruction sizes with some instructions taking up to 16-bit extensions. Lua's choice of a uniform 32-bit instruction also seems reasonable.

I guess 32 bits is more uniform but the tighter thing to do would be to have extensions; so some instructions-with-arguments are 8 bits, some are 16, some 24, some 32. Is there any advantage to having 8/16/32 and disallowing the 24? The only thing i can think of is that that way all instructions align on 32-bit boundaries; which might be worth it already. Is there a reason that ARM Thumb and Thumb2 didn't offer any 8-bit instructions, only 16? Maybe because if you don't have enough commonly used 8-bit instructions, you might waste some opcode space on the 8-bit opcodes, depending on how instructions are formatted? Maybe because the CPU can decode easier if everything is on 16-bit boundaries? Maybe because there just weren't enough instructions without big operands to make it worth the extra complexity? Also, i notice that e.g. PyMite?