I’m starting a new side project writing a CHIP 8 emulator, and for the CPU I have to process 2 byte long instruction codes and dispatch on them. So far my solution has been to read in the instruction from memory which is a bytes array, and turn it into a (int * int * int * int) tuple so that I can dispatch on those half words. The issue being this wastes a ton of space (28 * 4 bytes per instruction) so I was wondering if there’s a better way to do this? I wanted to represent them as Chars however it seems Char and Int aren’t implicitly castable so I end up with lots of Char.code and Char.char in my code which is annoying.
Just wanted people’s opinion. Here’s a summary of how it’s written right now:
(** Represents a 2 byte opcode in 4 half byte ints *)
type opcode = int * int * int * int
(** Reads a 2 byte opcode from provided memory buffer *)
let read_opcode memory addr : opcode =
let op = Bytes.get_int16_be memory addr in
let i3 = (op land (0b1111 lsl 12)) lsr 12 in
let i2 = (op land (0b1111 lsl 8)) lsr 8 in
let i1 = (op land (0b1111 lsl 4)) lsr 4 in
let i0 = (op land (0b1111 lsl 0)) lsr 0 in
(i3, i2, i1, i0)
And then to dispatch on opcode I have thos
(** Dispatches on the 2 byte opcode *)
let execute context memory (op : opcode) : string =
let open Printf in
match op with
| 0x0, 0x0, 0xE, 0x0 -> "clear"
| 0x0, 0x0, 0xE, 0xE -> "return"
| 0x1, nx, ny, nz -> sprintf "jump %d" @@ make_int12_be nx ny nz
| 0x2, nx, ny, nz -> sprintf "call %d" @@ make_int12_be nx ny nz
...
Where the make_int12_be function is just a helper function
let make_int12_be nx ny nz =
assert (nx <= 0b1111 && ny <= 0b1111 && nz <= 0b1111);
(nx lsl 8) lor (ny lsl 4) lor (nz lsl 0)
Would like to know how people would approach this. Tysm! <3
Personally, I would keep the opcode as a plain int but wrap it in an abstract type that can extract the half words once you actually want to match on them.
module Opcode : sig
type t
val whatever_the_first_half_word_represents : t -> int
...
end = struct
type t = int
let whatever_the_first_half_word_represents = ...
...
end
This way you are still wasting 6 bytes per opcode since the int takes up a full word, but that’s more-or-less optimal for a uniform representation language like OCaml.
ohhh that’s super cool and much better than messing around with what I was doing. I’m fairly new to ocaml so I didn’t make the connection between an abstract type and a module since modules have been a bit confusing but this is really helpful. tysm! <3 I’ll try it and revert back if I encounter something I can’t figure out.
One side question, you mentioned this:
This way you are still wasting 6 bytes per opcode since the int takes up a full word, but that’s more-or-less optimal for a uniform representation language like OCaml.
What does uniform representation language mean here? I haven’t encountered that term yet.
In OCaml (and many other high level languages), every value has the exact same representation at runtime. This is usually a pointer to an object on the garbage collected heap, except for ints and similar small values (like chars), which use the least significant bit as a tag to tell the GC that they aren’t pointers (this works since every heap pointer is at least 8 byte aligned and so always ends in a 0). That’s also the reason why OCaml’s int type is actually 63 bits on a 64 bit platform.
The reason for this representation is that with it, a polymorphic function can just be compiled like any other function.
Languages that don’t use this approach (like Rust or C++) need to compile a separate copy of the function for every type that it is be used with. This increases compile times and binary size and makes some programs that are valid in OCaml impossible to compile (for example ones involving functors that take modules that include polymorphic functions)
But a downside of this approach is that values can never be smaller than a word.
That… I had not thought through, even though if you’d asked me I could have given a half-coherent account of how unboxed ints are stored and know details are in the manual somewhere. Apologies for posting late-night nonsense.
If I remember properly, bitstrings are string slices internally, so if you could have your whole memory in a string that would be quite efficient actually.
That would still be a lot less efficient than just storing an int. bitstring is defined as
type bitstring = bytes * int * int
So if you represent your opcodes as bitstrings, then every opcode is actually an 8 byte pointer to a heap object that takes up at least 24 bytes (8 for the bytes pointer and 8 per int).
If we’re very generous, ignore all overhead from heap metadata and alignment and assume that all opcodes are slices over the same byte array, then this is still at least 32 bytes per opcode (4x as many as an int) and an extra heap allocation per opcode that you construct.
It would be slightly more memory efficient than type opcode = int * int * int * int, but not by much.
What match%bitstring does is to extract the bytes into integers (of the appropriate types) in a more efficient (and elegant) way than doing it by hand with Bytes.get_int16_be etc. In the example I gave above, dest is an int.
Well, dest is an int yes, but the actual opcode type that you’re storing for each instruction is still a bitstring that takes up at least 32 bytes.
I don’t know what exactly match%bitstring expands to, but it’s at least going to need to read from the underlying byte array, which is going to be dramatically slower than two bitshifts and a mask.
I also highly doubt that it’s going to be more efficient than Bytes.get_int16_be (otherwise why would Bytes.get_int16_be not do whatever bitstring does?)
There are also libraries like integers that give you the wrapper types for the different ints plus the appropriate functions. You’re generally still stuck with boxed versions of those, until OCaml has better support for unboxed types like OxCaml (OxCaml | Unboxed types | Intro).
It’s not. But if you read several bytes just to recompose them later (as in in the jump argument) then it may be faster, not having to read bytes and then reassemble them. Depends how often this case arises in practice.
Also, if you do not want to build a bitstring with each opcode, you could bitmatch on the full program at every step (starting the match by skipping as many bytes as the current pointer instruction first). Not sure how efficient the generated code would be, but it’s not impossible that it does a good job at this. Also, it would allow you to pattern match several instructions at once, in case you can optimize sur special sequences.
As for the elegance, this is certainly subjective.