Orbit Executable Format

Created 2nd July, 2009 09:01 (UTC), last edited 2nd July, 2009 09:03 (UTC)

I expect that there'll be several good puzzles that come out of the ICFP competition last weekend. Here's one to start us off.

The problem statement explains the format of a binary file that contains a data dump for a program to run on a virtual machine. How the machine works isn't important for this question, suffice it to say that it has two memory areas: One is for the program itself which is held as 32 bit integers. The other memory area is data memory which is held as 64 bit double precision floats. From the specification document:

The Orbit executable format stores the values for the instruction memory and the initial contents of the data memory. These values are stored in the exe- cutable format in sequential order, starting with the values for address zero. Instructions are stored as 32-bit words, encoded according to the format de- scribed in sections 2.2 and 2.3. Data memory values are stored as 64-bit double precision floating point values. Both instruction and data values are stored in the binary format in little-endian byte order.

The pairing of a 32-bit instruction and a 64-bit data value constitutes a 96-bit frame in the executable file. The order of the instruction and data values varies, depending on the frame address. For frames corresponding to even addresses, the first eight bytes of the frame contain to the double data value, while the next four bytes constitute the instruction value. Conversely, for frames corresponding to odd addresses, the first four bytes contain the instruction value and then next eight bytes contain the data value.

During the competition we were wondering if the strange format was only to annoy us, but afterwards I realised that there is another more subtle reason. What good explanations for this format can you come up with?


Categories: