# TDF Specification, Issue 4.0

### January 1998     8.1 - The Basic Encoding
8.2 - Fundamental encodings
8.2.1 - TDFINT
8.2.2 - TDFBOOL
8.2.3 - TDFSTRING
8.2.4 - TDFIDENT
8.3 - BITSTREAM
8.3.1 - BYTESTREAM
8.3.2 - BYTE_ALIGN
8.3.3 - Extendable integer encoding
8.4 - The TDF encoding
8.5 - File Formats

# 8. The bit encoding of TDF

This is a description of the encoding used for TDF.

Section 8.1 defines the basic level of encoding, in which integers consisting of a specified number of bits are appended to the sequence of bytes. Section 8.2 defines the second level of encoding, in which fundamental kinds of value are encoded in terms of integers of specified numbers of bits. Section 8.4 defines the third level, in which TDF is encoded using the previously defined concepts.

## 8.1. The Basic Encoding

TDF consists of a sequence of 8-bit bytes used to encode integers of a varying number of bits, from 1 to 32. These integers will be called basic integers.

TDF is encoded into bytes in increasing byte index, and within the byte the most significant end is filled before the least significant. Let the bits within a byte be numbered from 0 to 7, 0 denoting the least significant bit and 7 the most significant. Suppose that the bytes up to n-1 have been filled and that the next free bit in byte n is bit k. Then bits k+1 to 7 are full and bits 0 to k remain to be used. Now an integer of d bits is to be appended.

If d is less than or equal to k, the d bits will occupy bits k-d+1 to k of byte n, and the next free bit will be at bit k-d. Bit 0 of the integer will be at bit k-d+1 of the byte, and bit d-1 of the integer will be at bit k.

If d is equal to k+1, the d bits will occupy bits 0 to k of byte n and the next free bit will be bit 7 of byte n+1. Bit d-1 of the integer will be at bit k of the byte.

If d is greater than k+1, the most significant k+1 bits of the integer will be in byte n, with bit d-1 at bit k of the byte. The remaining d-k-1 least significant bits are then encoded into the bytes, starting at byte n+1, bit 7, using the same algorithm (i.e. recursively).

## 8.2. Fundamental encodings

This section describes the encoding of `TDFINT`, `TDFBOOL`, `TDFSTRING`, `TDFIDENT`, `BITSTREAM`, `BYTESTREAM`, `BYTE_ALIGN` and extendable integers.

### 8.2.1. TDFINT

`TDFINT` encodes non-negative integers of unbounded size. The encoding uses octal digits encoded in 4-bit basic integers. The most significant octal digit is encoded first, the least significant last. For all digits except the last the 4-bit integer is the value of the octal digit. For the last digit the 4-bit integer is the value of the octal digit plus 8.

### 8.2.2. TDFBOOL

`TDFBOOL` encodes a boolean, true or false. The encoding uses a 1-bit basic integer, with 1 encoding true and 0 encoding false.

### 8.2.3. TDFSTRING

`TDFSTRING` encodes a sequence containing n non-negative integers, each of k bits. The encoding consists of, first a `TDFINT` giving the number of bits, second a `TDFINT` giving the number of integers, which may be zero. Thirdly it contains n k-bit basic integers, giving the sequence of integers required, the first integer being first in this sequence.

### 8.2.4. TDFIDENT

`TDFIDENT` also encodes a sequence containing n non-negative integers. These integers will all consist of the same number of bits, which will be a multiple of 8. It is a property of the encoding of the other constructions that TDFIDENTS will start on either bit 7 or bit 3 of a byte and end on bit 7 or bit 3 of a byte. It thus has some alignment properties which are useful to permit fast copying of sections of TDF.

The encoding consists of, first a `TDFINT` giving the number of bits, second a `TDFINT` giving the number of integers, which may be zero. If the next free bit is not bit 7 of some byte, it is moved on to bit 7 of the next byte.

Thirdly it contains n k-bit integers.

If the next free bit is not bit 7 of some byte, it is moved on to bit 7 of the next byte.

## 8.3. BITSTREAM

It can be useful to be able to skip a TDF construction without reading through it. `BITSTREAM` provides a means of doing this.

A `BITSTREAM` encoding of X consists of a `TDFINT` giving the number of bits of encoding which are occupied by the X. Hence to skip over a `BITSTREAM` while decoding, one should read the `TDFINT` and then advance the bit index by that number of bits. To read the contents of a `BITSTREAM` encoding of X, one should read and ignore a `TDFINT` and then decode an X. There will be no spare bits at the end of the X, so reading can continue directly.

### 8.3.1. BYTESTREAM

It can be useful to be able to skip a TDF construction without reading through it. `BYTESTREAM` provides a means of doing this while remaining byte aligned, so facilitating copying the TDF. A `BYTESTREAM` will always start when the bit position is 3 or 7.

A `BYTESTREAM` encoding of X starts with a `TDFINT` giving a number, n. After this, if the current bit position is not bit 7 of some byte, it is moved to bit 7 of the next byte. The next n bytes are an encoding of X. There may be some spare bits left over at the end of X.

Hence to skip over a `BYTESTREAM` while decoding one should read a `TDFINT`, n, move to the next byte alignment (if the bit position is not 7) and advance the bit index over n bytes. To read a `BYTESTREAM` encoding of X one should read a `TDFINT`, n, and move to the next byte, b (if the bit position is not 7), and then decode an X. Finally the bit position should be moved to n bytes after b.

### 8.3.2. BYTE_ALIGN

`BYTE_ALIGN` leaves the bit position alone if it is 7, and otherwise moves to bit 7 of the next byte.

### 8.3.3. Extendable integer encoding

A d-bit extendable integer encoding enables an integer greater than zero to be encoded given d, a number of bits.

If the integer is between 1 and 2d - 1 inclusive, a d-bit basic integer is encoded.

If the integer, i, is greater than or equal to 2d, a d-bit basic integer encoding of zero is inserted and then i - 2d + 1 is encoded as a d-bit extendable encodin, and so on, recursively.

## 8.4. The TDF encoding

The descriptions of SORTS and constructors contain encoding information which is interpreted as follows to define the TDF encoding.

## 8.5. File Formats

There may be various kinds of files which contain TDF bitstream information. Each will start with a 4-byte "magic-number" identifying the kind of file followed by two `TDFINT`s giving the major and minor version numbers of the TDF involved.

A CAPSULE file will have a magic-number "TDFC". The encoding of the CAPSULE will be byte-aligned following the version numbers.

A TDF library file will have a magic-number "TDFL". These files are constructed by the TDF linker.

A TDF archive file will have a magic-number "TDFA".

Other file formats introduced should follow a similar pattern.

The TDF linker will refuse to link TDF files with different major version numbers. The resulting minor version number is the maximum of component minor version numbers.

Part of the TenDRA Web.