September 1996 Programmer's Challenge

ByteCode Interpreter

Mail solutions to: progchallenge@mactech.com

Due Date: 1 September 1996

(See addendum as well)

September is assembly language month at the Programmer's Challenge, and this year we will be accepting solutions in PowerPC assembly for the first time. This month's Challenge, suggested by Xan Gregg, is to write an interpreter for a subset of the byte code language used by the Java Virtual Machine.

The prototype for the code you should write is:

void JavaMiniVM(
  void *constant_pool,   /* pointer to cp_info array */
  void *fields,          /* pointer to field_info array */
  void *methods,         /* pointer to method_info array */
  void *classFile,       /* pointer to class file */
  long methodToExecute,  /* index of method to start executing */
  void *heapSpace,       /* preallocated storage for your use */
  void *returnStack      /* stack where return values are stored */
);
  

Your Challenge is to write an efficient interpreter for a subset of the Java byte code instruction set. A Java instruction consists of a single-byte opcode specifying the operation to be performed, followed by zero or more operand bytes. So, for example, in the byte sequence 0x10 0xFF, the opcode 0x10 (bipush) indicates that the operand byte 0xFF is to be pushed onto the operand stack. The instruction 0x60 (iadd) indicates that two integers are to be popped off the operand stack, added, and the result pushed back onto the stack. The virtual machine operates by repeatedly fetching an opcode and performing the indicated action on the operands.

To participate in this Challenge, you don't need to know anything about Java itself, but you do need to understand the Java Virtual Machine. A Java Virtual Machine executes a .class file, the format of which is too complicated to provide here, but is described in the Java Virtual Machine Specification (release 1.0 Beta) available at .

The first three parameters passed to your JavaMiniVM routine are pointers to the constants, fields, and methods contained in the .class file that your interpreter is to execute. These parameters are taken directly from the classFile described in section 2 of the VM specification. A pointer to the ClassFile is provided as the fourth parameter for those who feel they need direct access to the .class file. The parameter methodToExecute indicates which of the methods that your VM is to start executing.

Stack space and execution frames should be established by your virtual machine in the memory provided in heapSpace. Adequate heap space will be allocated by the caller. Your code may include static data that might be needed for lookup tables, etc., to efficiently implement the virtual machine. The parameter returnStack is provided as the stack for the execution environment of the calling routine. It is to be used when executing the various return byte codes to provide the caller access to your results.

To simplify the Challenge, your code need not implement the long, float, and double data types supported by the Java Virtual Machine. You also do not need to process exceptions, breakpoints, monitored code regions, or the wide modifier for load and store instructions. Your interpreter should be robust enough to determine the operand size of these unimplemented instructions in order to skip any that are encountered. All methods invoked will be in the single class file provided to your routine.

Sample test class files will be provided via the Programmer's Challenge mailing list, and are also available by writing me at . If there are any questions about what needs to be implemented, please send me a note at the same email address. [Test code will be available on or before 5 August 1996.]

Your code may be written in PowerPC assembly, 68K asssembly, C, or C++. Testing will be performed on an 8500 using the latest CodeWarrior environment. Because this is a more difficult Challenge than usual, it has been sent to the mailing list earlier than normal to provide additional solution time. For those of you who haven't had a chance to investigate Java in detail, it is a good opportunity to find out what all the excitement (hype?) is about. I hope you find this Challenge enjoyable and educational.