4

Note: This question is somewhat related to How exactly is bytecode "parsed"?, but it is not a duplicate of it. In this question, I'm asking about a specific part of how bytecode is generated, not how bytecode is "parsed".


As stated in the title, how are literals(such as strings, integers, etc...), encoded into bytecode files? My confusion comes from the fact that the byte representation of any given literal is of variable length. Which means that a virtual machine would have no idea how many bytes it needs to gather in order to read the entire literal. If my question is still not clear, I believe a visual example will help illustrate my confusion.

Consider this example. A parser has just constructed an abstract syntax tree. It converted the expression 3 + 2 into:

   +
  / \
 3   2

Your compiler/interprter now begins to walk the tree. It generates the following bytecode:

 PUSH          3            PUSH        2         ADD
  |            |             |          |          |    
|-----| |--------------|  |-----|  |----------| |-----|
b'\x00' b'\x00\x00\x00\'  b'\x00'  b'\x00\x00\' b'\x05'

Your virtual machine then begins reading in the bytecode file. It reads the first byte, and sees that it is the opcode PUSH. It now needs to read the argument to the opcode PUSH.

But here is the problem. The virtual machine has no way of knowing how many bytes it needs to read to get the entire argument to PUSH. the arguments to PUSH are a variable number of bytes, so the virtual machine does not know how many bytes it needs to read for each argument. As seen in the pseudo bytecode above, The number of bytes used to represent different values can vary, and are not consistent.

And while the above example only uses integers, this can also apply to other things. Such as strings, or string representations of identifier names.


I tried searching on various blogs and even the official documentation of some languages bytecode, but I still have not found a explanation for how literals are encoded.

The closet information I have came across, was a sentence from this answer given by Ratchet Freak to the question I linked to in the header. It reads:

To give an example that makes the bytes-per-operation very explicit there is SPIR-V. The first 4-byte word of each instruction is constructed as 2-byte length + 2-byte opcode.

It seems that what he is saying is that SPIR-V forces all opcodes an their arguments to be compressed or expand to fill two bytes. While I suppose on could do this, I'm fairly sure this is not what he meant.

What is the common practice when encoding literal values, whose byte representations are of variable length, into bytecode files? Of course, I assume that their is a common practice, but perhaps each language does it differently?

  • 1
    Bytecode per se is not bound to a specific language. I guess you are talking about Java bytecode particularly? – qwerty_so Dec 22 '16 at 19:56
  • 1
    I recognize the username and the question writing style. This question is one of a series, the OP is not implementing an existing VM/bytecode spec, he is designing and implementing his own. – Jörg W Mittag Dec 22 '16 at 20:09
  • 2
    You may also want to look at serialization formats, which have to solve some of the same problems. E.g. ASN.1, which has the property of being completely self-describing (i.e. you can fully decode any stream without knowing anything about its contents / structure / schema), Google protobuf, Apache Thrift, Python's pickle, Ruby's Marshal, Java serialization, but also textual serialization such as JSON, YAML, OGDL, XML. – Jörg W Mittag Dec 22 '16 at 20:13
  • One method that some implementations use is to encode the length of an object before the object data itself. For example, a string might have a 32-bit integer specifying its length in bytes, perhaps another integer representing the encoding (ASCII, UTF-8/16/32, et al), then (length) bytes containing the string data itself. This is the idea behind Pascal-style strings. – user22815 Dec 22 '16 at 20:14
  • @Snowman But what if the length of the string is bigger than what a 32-bit integer can hold? – Christian Dean Dec 23 '16 at 0:28
6

Your question applies more broadly than byte code systems, to general instruction set architecture, hardware or byte code.

What is the common practice when encoding literal values, whose byte representations are of variable length?

There are about half a dozen reasonable techniques.

  • The opcode tells you the number of bytes of the literal that is following the opcode. This means there are usually several of otherwise identical opcodes. Note that the opcode must (somehow) encode the size or type of the operand manipulation (e.g. push 32-bit int), which can be done together or separately from encoding the size/count of the literal data bytes (often called an immediate) following the opcode. In case these differ (often the immediate literal described by the instruction is shorter than the type for the operand), then, the byte(s) following the opcode are expanded as per the definition of the opcode (e.g. using sign extension), from the size of the immediate literal provided to the size of the operand type.

  • There are other bits after the opcode, yet are considered separate from the opcode, that tell the size of the literal (and/or format of (all) operands). When an instruction set has sub-opcodes grouped together sometimes bits beyond the major opcode indicate things about the various operands.

  • A variant of the last is that each operand has its own separate descriptor (possibly grouped together before the literal). These are typical in CISC-style register machines (like the VAX) having multiple operand instructions, such as addl3 (three operand add long).

  • There are bits in the literal itself that tell whether more data of the literal follows; for example, one bit of each byte can be dedicated to indicating more bytes, meaning each literal byte yields 7 bits, and tells if the next byte is a literal or the literal is completed. This is somewhat hostile to (software) interpretation performance, but hardware can decode this better than the naive approach would seem to indicate. If you are doing a JIT instead of interpreter, this may work alright.

  • An indirection of some sort is used, and the literal is stored elsewhere. This the case, for example, with strings in Java/C# byte code. In Java the push string opcode uses an index into the constant table. Application binary interfaces often specify one machine register or an accessible global location for larger constants like strings, or other 32-bit, 64-bit or larger blob constants.

  • Sometimes literals can be large enough or complex enough bit pattern that multiple instructions are used to assemble the literal. Some architectures provide a load immediate that takes its literal operand and puts it into the high bytes of the register (or stack). Then a regular add immediate is used to bring in the low bits of the literal. This is sometimes found in architectures that uses fixed size instructions.

  • 2
    I couldn't let you sit there at 9,990 rep :-) – user22815 Dec 22 '16 at 20:27
  • @Snowman, sweet, thx :) – Erik Eidt Dec 22 '16 at 20:34
4

the arguments to PUSH are a variable number of bytes, so the virtual machine does not know how many bytes it needs to read for each argument.

Usually, the architecture dictates that all arguments are a fixed number of bytes.

Note that there may be multiple variants of PUSH, each of which takes a different number of bytes. So you may have a PUSHWORD, a PUSHBYTE, a PUSHSHORT and each one will have a unique opcode. They may possibly all be called just PUSH in assembly, but then there needs to be enough context in the arguments (e.g. specifying a 16-bit register instead of a 32-bit register) to determine which unique opcode opcode the PUSH actually is.

Your generated instructions would look a bit more like this:

 PUSH3         3           PUSH2        2         ADD
  |            |             |          |          |    
|-----| |--------------|  |-----|  |----------| |-----|
b'\x03' b'\x00\x00\x00\'  b'\x02'  b'\x00\x00\' b'\x05'

Note that the push instructions are different and have different opcodes. That's not limited to PUSH either, you may have multiple opcodes for each arithmetic and logical operation, so you can specify whether you're ADDing bytes or words, or XORing just a byte, or an entire word.

Strings (or any non-atomic data structure such as arrays, structs, or lists) are usually not provided as immediates (i.e. part of the instruction). Instead they are stored in a separate location in memory and pointed to via a memory address (which would be of a fixed size and thus could be provided as part of the instruction).

Therefore (assuming you happen to have a string printing instruction in your bytecode) `PRNT "Hello World" would not look like this:

PRNT               "Hello World"
 |                      |
|--| |------------------------------------------|
\x45 \x48\x65\x6c\x6c\x6f\x20\x57\x6f\x72\x6c\x64

It would instead look like this:

// data section
// This example assumes the string is loaded at address /xcafebeef.
// HWString is a label referring to that. The label is useful in
// assembly, but probably not needed in the actual bytecode.

HWString:     "Hello World"
                   |
|----------------------------------------------|
\x48\x65\x6c\x6c\x6f\x20\x57\x6f\x72\x6c\x64\x00  // null terminator, if you're a fan of C-style strings.

// later in the file

// text section
PRNT  HWString
 |        |
|--| |--------|
\x45 \xcafebeef

You may want to take a look at the MIPS (32 bit) architecture, in which all instructions are exactly 32 bits, and all instructions fit into one of three formats.

Java is another example. In particular, it has bipush (byte immediate push) and sipush (short immediate push). The former takes a single one-byte operand, the latter takes a single two-byte operand, always.

  • I'm sorry, I'm still not following you. Your saying that the arguments to PUSH will not be a variable number of bytes. How so? Are not the number of bytes used to represent different values of different data types going to vary? Even if I had a specific opcode for pushing say, strings, each argument to the opcode is going to be different. "Hello World" and "Hello" do not use the same number of bytes to represent themselves, even if they are the same data type. – Christian Dean Dec 22 '16 at 19:18
  • @Engineer See my edit. – 8bittree Dec 22 '16 at 19:20
  • So your saying the other data types such as integers and characters are going to be a fixed number of bytes? But are not the individual values of each data type going to be a different number of bytes? Isn't 3 going to use a different number of bytes than say, 150 or 1500? Perhaps I'm thinking of this in the wrong context. I'm using Python to prototype my language, and whenever I convert an integer to bytes, the number of bytes used for each value if different. – Christian Dean Dec 22 '16 at 19:42
  • @Engineer: You demand that the arguments always be a fixed number of bytes. If you can accept 1500, which would require 2 bytes, then when you pass 3, you'll still pass 2 bytes, one of them being all zeros. Or, like the answerer said, you have different opcodes that provide the info on how many bytes the arguments are. – whatsisname Dec 22 '16 at 19:58
  • "Usually, the architecture dictates that all arguments are a fixed number of bytes." - But what should be done when the argument cannot fit in a fixed number of bytes? What if the byte representation of the literal is bigger than the set number of bytes? – Christian Dean Dec 24 '16 at 3:08
0

Literal objects are stored in an array outside of the bytecode. And then the put bytecode just indexes into that array.

A Ruby example,

$ ruby --dump insns -e '[nil,0,1,2,"str",/regexp/]'
== disasm: <RubyVM::InstructionSequence:<main>@-e>======================
0000 trace            1                                               (   1)
0002 putnil           
0003 putobject_OP_INT2FIX_O_0_C_ 
0004 putobject_OP_INT2FIX_O_1_C_ 
0005 putobject        2
0007 putstring        "str"
0009 putobject        /regexp/
0011 newarray         6
0013 leave            

As you can see there are different put bytecodes.

  • Some are 1 bytes longe and specialized for nil and common numbers like 0 and 1
  • Others are 2 bytes long and include an index into the array of literal object

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.