Panda Binary File Format

This document describes Panda binary file format with the following goals in mind:

• Compactness.
• Support for fast access to information.
• Support for low memory footprint.
• Extensibility and compatibility.

Compactness

Many mobile applications use a lot of types, methods and fields. Their number is so large that it doesn't fit in 16-bit unsigned integer. It leads to application developer have to create several files and as a result not all data can be deduplicated.

Current binary file format should extend these limits to conform to the modern requirements.

To achieve this, all references in the binary file are 4 bytes long. It allows to have 4Gb for addressing fields, methods, classes, etc.

The format uses TaggedValue which allows to store only information we have and avoid 0 offsets to absent information.

But to achieve more compactness 16-bit indexes are used to refer classes, methods and fields in the bytecode and some metadata. File can contain multiple indexes each one covers part of the file and described by RegionHeader.

Fast information access

Binary file format should support fast access to information. It means that redundant references should be avoided. Also, if it possible, binary file format should avoid data indexes (like sorted list of strings). However, the described binary format supports one index: a sorted list of offsets to classes. This index is compact and allows to find a type definition quickly, which runtime requires a lot during application launch time.

All classes, fields and methods are separated into 2 groups: foreign and local. Foreign classes, fields and methods are declared in other files, with references from the current binary file. Local classes, fields and methods are declared in the current file. Local entities has the same header as the corresponding foreign. So having an offset to an entity it doesn't matter whether the entity is local or foreign.

Runtime can easily check type of an offset by checking it is in the foreign region ([foreign_off; foreign_off + foreign_size)). Depending on the result runtime can search the entity in other files (for foreign entities) or create a runtime object from the definition by the offset (for local entities).

To improve data access speed most data structures have 4 bytes alignment. Since most target architectures are little endian all multibyte values are little endian.

Offsets

Unless otherwise specified, all offsets are calculated from the beginning of the file. An offset cannot contain values in the range [0; 32), except for specially mentioned cases.

Support for low memory footprint

As practice shows, most of file data is not used by the application. It means memory footprint of a file may be significantly reduced by grouping frequently used data. To support this feature, the described binary file format uses offsets and doesn't specify how structures should be located relatively to each other.

Extensibility and compatibility

The binary file format supports future changes via version number. The version field in the header is 4 bytes long and is encoded as byte array to avoid misinterpretation on platforms with different endianness.

Any tool which supports format version N must support format version N - 1 too.

Data types

MUTF-8 Encoding

Binary file format uses MUTF-8 (Modified UTF-8) encoding for strings.

String

Alignment: none

Format:

TaggedValue

Alignment: none

Format:

String syntax

TypeDescriptor

TypeDescriptor -> PrimitiveType | ArrayType | RefType
PrimitiveType  -> 'Z' | 'B' | 'H' | 'S' | 'C' | 'I' | 'U' | 'J' | 'Q' | 'F' | 'D' | 'A'
ArrayType      -> '[' TypeDescriptor
RefType        -> 'L' ClassName ';'

PrimitiveType is a one letter encoding for primitive type

ClassName is a qualified name of a class with . replaced with /.

Access flags

Field access flags

Method access flags

Class access flags

Source language

A file can be emitted from sources that are written in following languages:

Source language can be specified for classes and methods. For classes Panda Assembly language is assumed by default. Default language for methods is the class's one.

Data layout

A file begins with the header which is located at offset 0. All other data can be reached from the header.

Header

Alignment: 4 bytes

Format:

Constraint: size of header must be > 16 bytes. FieldType uses this fact.

RegionHeader

To address file structures using 16-bit indexes file is split into regions. Each region has class, method, field and proto indexes and described by RegionHeader structure.

Alignment: 4 bytes

Format:

Constraint: regions must not overlap each other.

RegionIndex

RegionIndex structure is aimed to allow runtime to find index structure that covers specified offset in the file. It is organized as an array of RegionHeader structures. All regions are sorted by the start offset of the region. Number of elements in the index is num_index_regions from Header.

Alignment: 4 bytes

ForeignField

Alignment: none

Format:

Note: Proper region index to resolve class_idx and type_idx can be found by foreign field's offset.

Field

Alignment: none

Format:

Note: Proper region index to resolve class_idx and type_idx can be found by field's offset.

FieldTag

Note: Only INT_VALUE or VALUE tags must be present.

FieldType

Since the first bytes of the file contain the header and size of the header > 16 bytes, any offset in the range [0; sizeof(Header)) is invalid. FieldType encoding uses this fact to encode primitive types of the field in the low 4 bits. For non-primitive type the value is an offset to Class or to ForeignClass. In both cases FieldType is uint32_t.

Primitive types are encoded as follows:

ForeignMethod

Alignment: none

Format:

Note: Proper region index to resolve class_idx and proto_idx can be found by foreign method's offset.

Method

Alignment: none

Format:

Note: Proper region index to resolve class_idx and proto_idx can be found by method's offset.

MethodTag

ForeignClass

Alignment: none

Format:

Class

Alignment: none

Format:

ClassTag

Note: Proper region index to resolve interfaces indexes can be found by class's offset.

LiteralArray

Alignment: none

Proto

Alignment: 2 bytes

Format:

Note: Proper region index to resolve reference types indexes can be found by proto's offset.

Shorty

Shorty is a short description of method's signature without detailed information about reference types. A shorty begins with a return type followed by method arguments and ends with 0x0.

Shorty syntax:

Shorty -> ReturnType ParamTypeList End
ReturnType -> Type
ParamTypeList -> '' | Type ParamTypeList
Type -> <encoded type>
End -> 0x0

<encoded type> must be one of:

All shorty elements are divided into groups of 4 elements starting from the beginning. Each group is encoded in uint16_t. Each element is encoded in 4 bits. A group with 4 elements v1, v2, ..., v4 is encoded in uint16_t as follow:

| bits   | 0 - 3 | 4 - 7 | 8 - 11 | 12 - 15 |
| ------ | ----- | ----- | ------ | ------- |
| values | v1    | v2    | v3     | v4      |

If the group contains less then 4 elements the rest bits are filled with 0x0.

Code

Alignment: none

Format:

TryBlock

Alignment: none

Format:

CatchBlock

Alignment: none

Format:

Note: Proper region index to resolve type_idx can be found by corresponding method's offset.

Annotation

Alignment: none

Format:

Note: Proper region index to resolve class_idx can be found by annotation's offset.

Tags description

The correct value for element with nullptr string tag is 0 (\x00\x00\x00\x00)

AnnotationElement

Alignment: none

Format:

ParamAnnotations

Alignment: none

Format:

AnnotationArray

Alignment: none

Format:

Value

There are different value encodings depending on the value's type.

ByteValue

Alignment: None

Format:

ShortValue

Alignment: 2 bytes

Format:

IntegerValue

Alignment: 4 bytes

Format:

LongValue

Alignment: 8 bytes

Format:

FloatValue

Alignment: 4 bytes

Format:

DoubleValue

Alignment: 8 bytes

Format:

StringValue

Alignment: 4 bytes

Format:

EnumValue

Alignment: 4 bytes

Format:

ClassValue

Alignment: 4 bytes

Format:

AnnotationValue

Alignment: 4 bytes

Format:

MethodValue

Alignment: 4 bytes

Format:

MethodHandleValue

Alignment: 4 bytes

Format:

MethodTypeValue

Alignment: 4 bytes

Format:

ArrayValue

Alignment: None

Format:

Literal

There are different literal encodings depending on the num of value's bytes.

ByteOne

Alignment: None

Format:

ByteTwo

Alignment: 2 bytes

Format:

ByteFour

Alignment: 4 bytes

Format:

ByteEight

Alignment: 8 bytes

Format:

ClassIndex

ClassIndex structure is aimed to allow runtime to find a type definition by name quickly. The structure is organized as an array of offsets from the beginning of the file to the Class or ForeignClass structures. All the offsets are sorted by corresponding class names. Number of elements in the index is num_classes from Header.

Alignment: 4 bytes

Format:

LineNumberProgramIndex

LineNumberProgramIndex structure is aimed to allow use more compact references to Line Number Program. The structure is organized as an array of offsets from the beginning of the file to the Line Number Program structures. Number of elements in the index is num_lnps from Header.

Alignment: 4 bytes

Format:

ClassRegionIndex

ClassRegionIndex structure is aimed to allow runtime to find a type definition by index. The structure is organized as an array of FieldType. Number of elements in the index is class_idx_size from RegionHeader.

Alignment: 4 bytes

Format:

MethodRegionIndex

MethodRegionIndex structure is aimed to allow runtime to find a method definition by index. The structure is organized as an array of offsets from the beginning og the file to the Method or the ForeignMethod structure. Number of elements in the index is method_idx_size from RegionHeader.

Alignment: 4 bytes

Format:

FieldRegionIndex

FieldRegionIndex structure is aimed to allow runtime to find a field definition by index. The structure is organized as an array of offsets from the beginning og the file to the Field or the ForeignField structure. Number of elements in the index is field_idx_size from RegionHeader.

Alignment: 4 bytes

Format:

ProtoRegionIndex

ProtoRegionIndex structure is aimed to allow runtime to find a proto definition by index. The structure is organized as an array of offsets from the beginning og the file to the Proto structure. Number of elements in the index is proto_idx_size from RegionHeader.

Alignment: 4 bytes

Format:

LiteralArrayIndex

LiteralArrayIndex structure is aimed to allow runtime to find a LiteralArray definition by index. The structure is organized as an array of offsets from the beginning of the file to the LiteralArray structures. Number of elements in the index is num_literalarrays from Header.

Alignment: 4 bytes

Format:

DebugInfo

Debug information contains mapping between program counter of a method and line numbers in source code and information about local variables. The format is derived from DWARF Debugging Information Format, Version 3 (see item 6.2). The mapping and local variable information are encoded in line number program which is interpreted by the state machine. To deduplicate the same line number programs of different methods all constants the program refers to are moved into the constant pool.

Alignment: none

Format:

Constant pool

Many methods has similar line number program. The difference is only in variable names, variable types and file names. To deduplicate such programs all constants the program refers to are stored in the constant pool. During interpretation of the program the state machine tracks a pointer to the constant pool. When the state machine interprets an instruction which requires a constant argument the machine reads the value from memory constant pool pointer points to and then increments the pointer. Thus programs has no explicit references to constants and could be deduplicated.

State Machine

The aim of the state machine is to generate a mapping between program counter and line numbers and local variable information. The machine has the following registers:

Line Number Program

A line number program consists of instructions. Each instruction has one byte opcode and optional arguments. Depending on opcode argument's value may be encoded into the instruction or the instruction requires reading the value from constant pool.

Special opcodes:

The state machine interprets each special opcode as follow (see DWARF Debugging Information Format item 6.2.5.1 Special Opcodes):

1. Calculate the adjusted opcode: adjusted_opcode = opcode - OPCODE_BASE.
2. Increment address register: address += adjusted_opcode / LINE_RANGE.
3. Increment line register: line += LINE_BASE + (adjusted_opcode % LINE_RANGE).
4. Emit line number.
5. Set prologue_end register to false.
6. Set epilogue_begin register to false.

Where:

• OPCODE_BASE = 0x0c: the first special opcode.
• LINE_BASE = -4: the smallest line number increment.
• LINE_RANGE = 15: the number of line increments presented.

MethodHandle

Alignment: none

Format:

Types of MethodHandle

The available types of a method handle are:

Argument Types

A bootstrap method can accept static arguments of the following types: