This document describes the encoding algorithms referenced by the BGFA format. It covers integer encoding, string encoding, and specialized encodings used in block payloads.
Normative keywords. MUST, MUST NOT, SHOULD and MAY are to be interpreted as in RFC 2119.
Every statement about what a writer or a reader does is normative; prose that is only explanatory is
marked as such. "Fatal error" always means the same thing: the reader MUST reject the whole file and MUST
NOT continue, as detailed in Reader Requirements. Wherever this
document says that a reader rejects a field, it rejects the whole file.
- String Encoding Overview
- Integer Encoding Algorithms
- String Encoding Algorithms
- CIGAR 4-byte Strategy Code Details
A set of strings is embedded within a single "superstring" constructed by a heuristic that tries to minimize the overall length (e.g., by overlapping common suffixes/prefixes). The metadata stores the start and end position of each string within the superstring.
End positions are excluded. Positions are 0-based, start[i] is the first byte of string i and
end[i] is the position just after its last byte, exactly like a Python slice: string i is
superstring[start[i]:end[i]], and its length is end[i] - start[i]. An empty string has
start[i] == end[i]. See Conventions.
Example. With the superstring ACGTTA, the strings ACG, GTT and TA are stored as
start = [0, 2, 4] and end = [3, 5, 6]: superstring[0:3] is ACG, superstring[2:5] is GTT (it
overlaps the first string), and superstring[4:6] is TA. The last end equals the superstring length.
Note: In the superstring layout, strings are never concatenated directly; every strings field is encoded
via this superstring approach, except a field using the Dictionary method,
which replaces the superstring layout.
The superstring is then encoded using the string encoding strategy.
When encoding a list of strings (the strings type), the encoding strategy is specified by a 2-byte code (see Strategy Code Format Summary in the main spec):
- First byte: integer encoding strategy for the position metadata
- Second byte: string encoding strategy for the superstring blob
Decoding a set of strings does not need to know the heuristic used to compute the superstring.
The payload of the encoded strings consists of:
-
Metadata: the start positions and the end positions of the strings, encoded according to the first-byte strategy (varint, fixed16, etc). The number of strings
nis the number implied by the containing block header, which isrecord_numfor everystringsfield in BGFA.Start and end positions are encoded as two separate integer lists, each an independent unit in the sense of Conventions: first the
nstart positions, then thenend positions. Both lists use the same integer encoding strategy. Because the first start position is usually 0, a writer MUST NOT choose Elias gamma (0x04) or omega (0x05) when either list holds a 0. -
Blob: The superstring is encoded according to the second-byte strategy.
Layout:
[start_0][start_1]...[start_n-1][end_0][end_1]...[end_n-1][blob length][blob]
All start positions are encoded first (as a contiguous list), followed by all end positions (as a contiguous list). Both lists use the same integer encoding strategy specified in the first byte of the compression code.
The compressed_*_len fields in block headers represent the total number of bytes for the encoded payload of that field, including both the integer metadata list and the compressed blob.
The uncompressed_len field is the sum of the lengths of the original strings (before any encoding). Note
that it is not the length of the superstring, which may be shorter because of overlaps.
Every strings field ends with a blob, which holds the compressed form of the superstring. A decoder cannot
use the block's compressed_*_len field to find the end of the blob, because the superstring positions are
decoded before the blob and some methods (Huffman, 2-bit DNA) cannot be decoded "until the bytes run out".
The leading blob length makes every blob self-delimiting (rule 4 of the size rules in
Payload Byte Layouts); the two rules below define it.
Rule 1 — the outer blob length is a byte count. The first thing in a blob is a varint holding the
number of bytes of method-specific data that follow it.
The blob length is always expressed as a number of bytes, for every method, without exception.
It is not a decoded length, not a symbol count, and not a nucleotide count. After reading it, a decoder consumes exactly that many bytes of method-specific data, whatever the method.
[start_0] ... [start_n-1] [end_0] ... [end_n-1] [blob length: varint] [method data]
The blob length bytes themselves are not counted in the blob length.
Rule 2 — method data stays within the blob length. Method-specific data starts at its first byte and
MUST end exactly where the blob length says. For none (0x00) the blob length is the only thing that
gives the extent of the method data. Every other method also has its own framing that takes a decoder
exactly to the last byte of its method data, because that data is sometimes decoded where no blob length is
available: the Huffman data of each block inside BWT + Huffman, and the packed
operations of a CIGAR numOperations decomposition (see
CIGAR 4-byte Strategy Code Details). Methods whose decoded size
cannot be recovered from their own framing (Huffman, 2-bit DNA) therefore carry an explicit decoded item
count inside their method data, defined in their own section. That count is an internal property of those
two methods; it is not the outer blob length, and the two MUST NOT be confused.
Validation. A reader MUST reject a field as a fatal error if the blob length is larger than the number
of bytes remaining in the owning compressed_*_len field, or if decoding the method data does not consume
exactly blob length bytes. For a strings field, the blob is the last part of the field, so the blob
MUST also end exactly at the end of the owning compressed_*_len field (rule 7 of the size rules in
Payload Byte Layouts).
Note on redundancy. For the container methods (zstd, gzip, lzma, bzip2) the blob length is redundant,
because the compressed stream has its own end marker. It is nonetheless mandatory, so that there is exactly
one framing rule for every method and one place where a decoder bounds its reads. For none it is not
redundant, as stated in rule 2. The blob length costs at least 1 byte per strings field (1 byte for a
method data shorter than 128 bytes, more for longer ones, as for every varint).
Exception — Dictionary. The Dictionary method (0x0A) replaces this layout entirely: a strings
field with LL = 0x0A has no start/end positions and no outer blob length. See
Dictionary Encoding. This exception applies only to strings fields: a CIGAR
string decomposition (DD = 0x02) always has its outer blob length, even when SS = 0x0A (rule 5 of the
size rules in Payload Byte Layouts).
A list of signed integers is encoded by two parts:
- the signs of all integers
- the absolute values of all integers (unsigned ints). The encoding strategy applies to this part only.
The signs are considered a sequence of bits, where + is encoded as 0 and - is encoded with 1.
The i-th bit in the sign bits field corresponds to the sign of the i-th integer in the list.
A value whose absolute value is 0 may be stored with either sign bit: a writer MAY write 0 or 1, and a
reader MUST accept both and decode the value as 0.
The sign bits form a bits field of exactly as many bits as there are integers in the field, packed per
Packed Bits. Its size is therefore 8 * ceil(n / 64) bytes, where n
is the number of integers implied by the containing block header, and it is placed in the trailing
bits-fields group of its owning compressed_*_len field (rule 3 of the size rules in
Payload Byte Layouts). The absolute values follow as one
integer list encoded with the field's integer strategy.
Layout of a uints-delta field. Conceptually, a uints-delta field is, per field:
[method preamble, if any][absolute value 0] ... [absolute value n-1][sign bits]
In byte order this is not contiguous: the absolute values sit inline at the field's position, while the
sign bits field is deferred to the trailing bits-fields group of the owning compressed_*_len field,
per rule 3. When a region holds several uints-delta fields (the Walks start_positions and
end_positions), the byte order is: each field's preamble and absolute values in block field order, then
the whole trailing bits-fields group in block field order. The "method preamble" is present only for
Rice (0x07), whose one-byte k parameter therefore precedes the first absolute value.
There is no preamble for any other method.
Note that there is one delta stream per field and it is never restarted part-way: see the uints-delta
definition in Type Definitions.
Validation. A reader MUST reject the field as a fatal error if the sign bits field does not decode to
exactly one sign bit per integer, or if the owning region's inline absolute values — the absolute values of
all the owning region's uints-delta fields, decoded together in block field order — do not terminate exactly
at the start of the owning region's trailing bits-fields group, that is, at compressed_*_len minus the total
byte size of all bits fields in that group, each 8 * ceil(n_i / 64) bytes for its own n_i (rule 3
of the size rules in Payload Byte Layouts). A decoder locates
the group from the end of the region and requires the combined inline integer stream to end at the group's
first byte; the group may hold more bits fields after this field's sign bits (for example,
end_positions signs or walks_orientations). In a region with several uints-delta fields, each field's
absolute values end where the next field's absolute values begin, and only the last field's absolute values
are adjacent to the group. Any bytes between the last absolute value and the group are a fatal error, so a
non-canonical encoding that pads the absolute list is rejected. Negative absolute values are impossible by
construction, but a decoder MUST still reject an absolute value of 2^64 or more (see the integer range in
Conventions), rather than silently wrapping it.
Reconstruction. The decoded values are the running sum of the signed deltas. The first value is the
first delta itself; every later value is the previous value plus its delta. A reader MUST reject the
field as a fatal error if the running sum leaves the range 0 .. 2^64 - 1, and MUST NOT wrap. This range
applies to every uints-delta field: walks_segments, start_positions and end_positions all hold
unsigned values.
The encodings of unsigned ints are the following.
Code 0x00 is reserved in an integer position and MUST NOT be used there. It is a valid string
method (see None / Identity (0x00)) and it is the byte a strategy code carries in
the string position of a strings field, but an integer list of a known count has no element width, so
0x00 has no meaning for it.
A writer MUST NOT emit 0x00 in an integer position of a strategy code, and a reader MUST reject it as
an unknown strategy code. The integer codes are therefore exactly:
0x01 0x02 0x04 0x05 0x06 0x07 0x08 0x09 0x0A 0x0B
This is the set that INTEGER_CODES enumerates in
Strategy Code Validation Examples.
Variable-length integer encoding optimized for small values.
Format:
- Each byte: 7 data bits + 1 continuation bit (1 = more bytes follow, 0 = last byte)
- Little-endian ordering (least significant group first)
- Canonical form. A writer MUST use the shortest encoding: the last byte of a multi-byte varint is never
0x00. A reader MUST reject as a fatal error a varint longer than 10 bytes, a varint whose value is2^64or more, and a multi-byte varint whose last byte is0x00.
Example: the value 300 is 0b10_0101100. The least significant group 0101100 is written first, with
the continuation bit set, giving 0xAC; the remaining group 0b10 is written last, giving 0x02. The
value is therefore stored as AC 02. The same value in fixed16 is 2C 01.
These rules apply to every varint in BGFA, including the blob lengths, counts and positions that are always stored as varint regardless of the field's strategy.
Each integer is encoded as a fixed 16-bit little-endian value.
Example: the value 300 is 0x012C, stored least significant byte first as 2C 01.
Elias gamma encodes a number n >= 1 as a unary bit width followed by the bits of n. This is textbook
Elias gamma, so a generic gamma implementation produces compatible codewords.
Format:
- Let
L = floor(log2(n)) + 1, the number of bits in the binary form ofn. - Write L - 1 zero bits.
- Write the L bits of n in binary, most significant bit first. Their leading bit is always 1 and is the terminator the decoder needs, so gamma is self-delimiting.
Example: n = 5
L = 3- Unary:
00+1=001 binary(5) = 101- Complete:
00101(5 bits)
Packed LSB-first (see Conventions), the first bit of the codeword
occupies bit 0 of the first byte, so the 5-bit codeword 00101 is padded with three zero bits to
0b00010100 = 0x14.
Example: n = 1 is the single bit 1, packed as 0b00000001 = 0x01.
Example: the list [1, 5]
n = 1:L = 1, unary1, no low bits →1n = 5:L = 3, unary001, low bits101→00101- Bit stream:
100101=100101(6 bits), padded with two zero bits and packed LSB-first:0b00101001=0x29
Zero cannot be represented. Gamma has no codeword for n = 0, because L would be 0 and the unary
part would be empty. A writer MUST NOT select 0x04 for an integer list that contains a 0 — in particular
segment IDs and their deltas, which can be 0. A reader MUST reject a field as a fatal error if the unary
prefix decodes to L > 64, or if any other part of the value cannot be decoded.
Elias omega encodes a positive integer by recursing on its bit width. The recursion terminates in a
single 0 bit, so an omega codeword is self-delimiting. The bits of a codeword are written most
significant bit first, and the resulting stream is packed LSB-first (see
Conventions).
Encoding. Start with code = "0". While n > 1, prepend the full binary representation of n to
code, then replace n with bit_width(n) - 1, i.e. floor(log2(n)). When n reaches 1 the loop
stops and code is complete.
Equivalently, in the order the groups appear in the stream: the innermost group comes first and n itself
comes last. The groups are the binary forms of the values n, floor(log2(n)),
floor(log2(floor(log2(n)))), ..., computed until the value reaches 1; the final 1 is not written.
They are written from the last computed value back to n, followed by one terminating 0 bit. The
leading 1 of each binary form is written; nothing is stripped. For n = 5 the values are 5, 2, 1,
so the stream is 10 (for 2), then 101 (for 5), then 0.
Decoding. Set current = 1, then repeat:
- Read one bit. If it is
0, stop: the decoded value iscurrent. - Otherwise set
next = 1, read exactlycurrentmore bits and append each tonextmost significant bit first (next = next << 1 | bit), then setcurrent = nextand go back to step 1.
Example: n = 5
binary(5) = 101; the newnisbit_width(5) - 1 = 3 - 1 = 2binary(2) = 10; the newnisbit_width(2) - 1 = 2 - 1 = 1, which stops the loop- the loop produced
10then101; the terminating0is appended - complete:
101010(6 bits)
Packed LSB-first and padded with two zero bits, the codeword is 0b00010101 = 0x15.
Example: n = 1 emits the single bit 0. A decoder must therefore be able to recognise a lone 0 as a
complete value.
Zero cannot be represented. As with gamma, n = 0 has no codeword. A writer MUST NOT select 0x05
for an integer list that contains a 0, and a reader can never legitimately decode a 0 with this method.
A reader MUST reject as a fatal error a codeword whose recursion would produce a value of 2^64 or more,
i.e. a step 2 entered with current >= 64, which would build a value of more than 64 bits.
Golomb encoding uses a parameter b, which is fixed at 128 for the whole format: every list encoded
with 0x06 uses b = 128, and b is not transmitted.
Format:
- For value n:
- quotient q = n // b, remainder r = n % b
- Write q in unary (q ones, then zero)
- Write r in binary using
ceil(log2(b))= 7 bits
The unary prefix and the 7-bit remainder are written most significant bit first within the codeword, and the resulting stream is packed LSB-first (see Conventions).
Because b = 128 = 2^7, Golomb as defined here is bit-identical to Rice with k = 7.
The two codes differ only in that Rice stores k and Golomb does not.
Rice coding is Golomb with b as a power of 2: b = 2^k.
Format:
- The parameter
kis per integer list (see Conventions) and MUST be stored explicitly as a single raw byte (not a varint), before the first encoded value of that list. It is not part of the strategy code.kMUST satisfy1 <= k <= 31; an out-of-rangekMUST be treated as a fatal error. - In a
uints-deltafield this byte precedes the first absolute value: see the layout in Signed Integers. - For value n:
- quotient q = n >> k
- remainder r = n & (2^k - 1)
- Write q in unary (q ones, then zero)
- Write r in binary using k bits
The unary prefix and the k-bit remainder are written most significant bit first within the codeword, and the resulting stream is packed LSB-first.
Example: For k=3 and sequence [5, 12, 7]:
- Parameter byte:
0x03 - 5:
q = 0,r = 5→0101 - 12:
q = 1,r = 4→10100 - 7:
q = 0,r = 7→0111 - Bit stream:
0101 10100 0111(13 bits), packed LSB-first and padded with three zero bits:01011010 00011100 - Complete list:
03 5A 1C(3 bytes)
StreamVByte encodes integers in groups of four, with one control byte per group. A reader decodes exactly the number of integers the containing block header implies and MUST stop there.
This is not the layout of the reference StreamVByte library. That library stores all control bytes first and all data bytes after them, and supports a 3-byte width. BGFA interleaves each control byte with its group's data and uses the widths 1, 2 and 4 only, as defined below.
Format:
-
The integers are encoded in groups of 4; only the final group may hold fewer. Every group is preceded by exactly one control byte, immediately followed by the data bytes of that group's integers, in order.
-
Control byte bits
2*iand2*i + 1select the width of thei-th integer of the group:bit 2*ibit 2*i + 1width of integer i0 0 1 byte 1 0 2 bytes 0 1 4 bytes 1 1 invalid A writer MUST NOT emit the combination
1 1, and a reader MUST treat it as a fatal error. -
Each integer is stored little-endian in its width.
-
A writer MUST use the smallest width that can represent the value: below 256 always 1 byte, below 65536 always 2 bytes, otherwise 4 bytes. A reader MUST reject as a fatal error a value stored in a width larger than the smallest one that can represent it.
-
Values of
2^32or more cannot be represented. A writer MUST NOT select0x08for an integer list that contains such a value. -
If the final group holds
m < 4integers, the control bits2*m..7describe integers that are not present. A writer MUST set them to 0; a reader MUST ignore them.
Example: with compression = 0x08, the integers [1, 300, 2, 3] form one complete group:
- Control byte: integer 0 (value 1) needs 1 byte, so bits 0-1 are
00; integer 1 (value 300) needs 2 bytes, so bit 2 is 1 and bit 3 is 0; integers 2 and 3 need 1 byte each, so bits 4-7 are0000. The control byte is0b00000100=0x04. - Data:
01(1),2C 01(300, little-endian),02(2),03(3) = 6 bytes. - Total: 1 control byte + 6 data bytes = 7 bytes.
Variable Byte encoding uses 7 bits per byte for data, with the high bit as the continuation flag.
Format:
- Each byte: 7 data bits + 1 continuation bit (1 = more bytes follow, 0 = last byte)
- Little-endian ordering (least significant group first), identical to Varint.
VByteandvarintare the same encoding on the wire; they exist as separate codes so that a field can declare which one it uses. - Canonical form. The canonical-form rules of Varint apply to VByte unchanged: a writer
MUST use the shortest encoding, and a reader MUST reject as a fatal error a VByte value longer than 10
bytes, a value of
2^64or more, and a multi-byte value whose last byte is0x00.
Each integer is encoded as a fixed 32-bit little-endian value.
Example: the value 300 is 0x0000012C, stored least significant byte first as 2C 01 00 00.
Each integer is encoded as a fixed 64-bit little-endian value.
Example: the value 300 is 0x000000000000012C, stored least significant byte first as
2C 01 00 00 00 00 00 00.
These rules apply to every uints and uints-delta field, in addition to the per-method requirements of each
integer method. They exist because the counts and lengths that bound a field come from the block header and
are therefore attacker-controlled.
- A reader MUST decode exactly the number of integers implied by the containing block header, and MUST stop at
that count rather than at the end of the owning
compressed_*_lenfield. - A reader MUST reject the field as a fatal error if decoding that many integers would read past the end of the
owning
compressed_*_lenfield, or past the end of the file. - For
fixed16,fixed32andfixed64, a writer MUST NOT select a width that cannot hold every value of the list; it MUST NOT silently truncate a value to the low bits. - A reader MUST NOT allocate a buffer whose size is derived from an unvalidated header or payload field. Every derived size MUST be validated first, as described in Limits and Validation.
- Arithmetic on sizes derived from the header (products, sums,
ceil(n / 4),8 * ceil(n / 64),16 * ceil(n / 64), dictionaryN + 1) MUST be performed with overflow checking, and a reader MUST reject the field rather than wrap around. - For a
walks-type field, the decodedwalks_lengthslist MUST contain exactlyrecord_numintegers, each L(i) MUST be at least 1, and the sum of all L(i) MUST equaluncompressed_walk_lenin a Walks block anduncompressed_paths_lenin a Paths block. A reader MUST reject the block as a fatal error on any violation: these counts come from the header and are attacker-controlled, and a mismatch would silently mis-assign segment occurrences to walks. Theat least 1bound is a source-format constraint, not an encoding artifact: the GFA 1.2 W-line grammar defines a walk as one or more oriented segments ((<orientation> <segId>)+), so an empty walk cannot be represented, anduncompressed_walk_lenis therefore always at leastrecord_num.
The following algorithms encode a byte buffer: the superstring of a strings field, or the buffer of a
CIGAR decomposition (see CIGAR 4-byte Strategy Code Details). In this
section "the superstring" means whichever buffer is being encoded. Every method applies to an arbitrary
byte buffer; the methods that are tuned for DNA (2-bit, RLE, BWT+Huffman) remain lossless on any input.
The method data is the superstring itself, stored as raw bytes with no transformation. Its length is exactly the blob length of Blob Framing. The string metadata (start/end positions from the integer encoding) defines how to slice individual strings from the superstring.
The method data is exactly one Zstandard frame (RFC 8878) holding the
superstring, whose byte length is exactly the blob length of Blob Framing. The frame MUST
NOT require an external dictionary (its Dictionary_ID is absent or 0). Skippable frames are not allowed.
The method data is exactly one gzip member (RFC 1952, compression method 8, deflate) holding the superstring, whose byte length is exactly the blob length of Blob Framing. A raw deflate stream or a zlib (RFC 1950) stream is not valid here.
The method data is exactly one .xz stream (LZMA2 filter)
holding the superstring, whose byte length is exactly the blob length of Blob Framing. This
is the default output of the xz tool and of Python's lzma.compress. The legacy .lzma (LZMA_Alone)
format and raw LZMA streams are not valid here.
Decompressed size. For every container method (0x01, 0x02, 0x03, 0x07) the decompressed size is
not known before decompression. A reader MUST bound it by the decoded-size cap of
Limits and Validation and stop as soon as the cap is exceeded.
The two Huffman codes share one wire format and differ only in alphabet size:
| Code | Alphabet | Codebook size | Payload unit |
|---|---|---|---|
0x04 |
16 nibbles 0x0-0xF | 32 bytes (16 × uint16) |
one nibble |
0xF4 |
256 bytes 0x00-0xFF | 512 bytes (256 × uint16) |
one byte |
The Huffman encoding of a string consists of:
| Name | Description | Type |
|---|---|---|
codebook_len |
Length of the encoded codebook in bytes | uint16 |
codebook |
Bit-lengths, one little-endian uint16 per alphabet symbol |
bytes |
symbol_count |
Number of symbols to decode (see below) | varint |
huffman_bitstream |
The encoded symbols, packed LSB-first, padded with zeros to a byte boundary | bytes |
Framing. The blob is:
[blob length: varint][codebook_len: uint16][codebook][symbol_count: varint][huffman_bitstream]
The codebook MUST be stored at the beginning of the blob, before any encoded data, so that a decoder has the full code table before it reads a single symbol. The encoder MUST choose the codebook from the data being encoded and MUST store it; a reader MUST NOT assume a fixed codebook.
symbol_count is the decoded item count, and is the reason this method needs an internal count: the
outer blob length of Blob Framing is a byte count, so it cannot tell a decoder how many
symbols to produce.
symbol_count is twice the length L of the byte buffer being encoded for 0x04 (one nibble per
half-byte, so 2 * L nibbles) and exactly L for 0xF4 (one symbol per byte). "The byte buffer" is
whatever this method was asked to encode:
- for a
stringsfield, it is the superstring, soLis the superstring length in bytes; - for a CIGAR
numOperationsdecomposition, it is the packed operations buffer described in Packed Operations String, soLis that buffer's length in bytes; - for a CIGAR
stringdecomposition, it is the newline-terminated CIGAR buffer.
In every case 0x04 splits each byte of the buffer into a high and a low nibble in that order, per
Nibble-Level Processing; the CIGAR buffer is nibble-packed data, but it is
still a byte buffer for the purposes of this method. For 0x04 a reader MUST treat an odd symbol_count as
a fatal error.
Deriving the bitstream length. Let B be the number of bits consumed by decoding the symbol_count
symbols. The bitstream is exactly ceil(B / 8) bytes long; the last 8 * ceil(B / 8) - B bits are padding.
When this method data is the whole method data of a field (a strings blob or a CIGAR buffer), the bitstream
also occupies all the rest of it, i.e. M - 2 - codebook_len - (bytes of the symbol_count varint) bytes,
where M is the method-data byte count (the blob length of Blob Framing, or the rest of the
field for the packed operations of a CIGAR numOperations decomposition). Inside
BWT + Huffman the Huffman data of a block is followed by the next block, and only the
ceil(B / 8) rule applies. A reader MUST reject the field as a fatal error if the available bytes run out
before symbol_count symbols have been decoded, or if, in the first case, any byte is left after the
ceil(B / 8) bytes of the bitstream.
Codebook format:
The codebook is exactly 32 bytes for 0x04 (16 little-endian uint16 values, one bit-length per nibble
0x0 through 0xF) and exactly 512 bytes for 0xF4 (256 little-endian uint16 values, one bit-length per byte
0x00 through 0xFF). codebook_len MUST equal 32 for 0x04 and 512 for 0xF4; any other value is a fatal
error. A bit-length of 0 means the symbol is absent from the alphabet and MUST NOT appear in the encoded data;
such an entry is stored as 0.
codebook = struct.unpack('<16H', codebook_bytes) # 0x04
# codebook[0] = bit-length for nibble 0x0
# codebook[1] = bit-length for nibble 0x1
# ...
# codebook[15] = bit-length for nibble 0xFValidation. A codebook is valid if and only if both of the following hold:
- Every non-zero bit-length is in
1..16. - Kraft's equality holds, which MUST be checked with exact integer arithmetic, not floating point:
sum(2^(16 - len) for len in codebook if len > 0) == 65536. The equivalent floating-point formsum(2**-len ...) == 1is not exact and MUST NOT be used to decide.
A reader MUST reject a codebook that fails either check as a fatal error.
The 16-bit code-length limit is a real constraint, not a formality. A uint16 entry can hold any
length up to 65535, but this specification caps codes at 16 bits, so a codebook that needs longer codes is
not representable. This is not a theoretical concern for 0xF4, whose 256-symbol alphabet can easily
produce codes longer than 16 bits on skewed data. A writer MUST compute its codebook first and, if any code
would exceed 16 bits, MUST NOT use 0x04 or 0xF4 for that buffer — it MUST pick another method.
At least two distinct symbols are needed. A codebook with a single non-zero length, or with none, can
never satisfy Kraft's equality. A writer MUST therefore NOT use 0x04 or 0xF4 for a buffer that holds
fewer than two distinct symbols (for 0x04, distinct nibbles), which includes the empty buffer; it MUST
pick another method.
Reconstruction: The decoder MUST reconstruct the Huffman codes from the bit-lengths using canonical Huffman code assignment:
-
Collect all (symbol, bit-length) pairs where bit-length > 0
-
Sort primarily by bit-length (ascending) and secondarily by symbol value (ascending)
-
Assign codes sequentially using the following algorithm:
code = 0 prev_len = 0 huffman_codes = {} for symbol, bit_len in sorted_pairs: code = (code + 1) << (bit_len - prev_len) if prev_len > 0 else 0 huffman_codes[symbol] = (code, bit_len) prev_len = bit_len
-
Zero bit-length symbols are not in the alphabet and will not appear in the encoded data
Example: Given bit-lengths: {0x41: 1, 0x42: 2, 0x43: 2} (symbols 'A', 'B', 'C'; a 0xF4
codebook, since the symbols exceed the 0x04 nibble range):
- Sorted by (bit-length, symbol):
[(0x41, 1), (0x42, 2), (0x43, 2)] - Code assignment:
- 'A' (0x41): bit-length=1, code=0b0 (first, shortest)
- 'B' (0x42): bit-length=2, code=(0b0+1)<<1 = 0b10
- 'C' (0x43): bit-length=2, code=(0b10+1)<<0 = 0b11
- Kraft's equality holds:
2^15 + 2^14 + 2^14 = 65536, so a conforming reader accepts this codebook.
Encoding process:
- Turn the input into symbols: for
0x04each byte becomes two nibbles (high nibble, low nibble); for0xF4each byte is one symbol - Look up each symbol's code in the reconstructed codebook
- Concatenate all codes, each written most significant bit first, into a bitstream
- Pack the bitstream LSB-first and pad it to a byte boundary with zeros
Decoding: the decoder reads symbol_count and then decodes exactly that many symbols — 2 * L nibbles
for 0x04, L bytes for 0xF4. The unused high bits of the last byte of the bitstream are padding and
MUST be ignored. Because symbol_count is stored explicitly, a decoder never has to infer the decoded
length from the string metadata, and the decoded superstring length is independent of how many overlaps the
superstring heuristic found.
Bit order: the Huffman bit stream is packed LSB-first, like every other bit stream in BGFA (see Conventions). The codes themselves are unchanged: only the order in which their bits are laid into bytes follows the general rule.
-
Symbol Extraction: Each byte of the target string (the superstring) is treated as two 4-bit symbols:
- Symbol A: High nibble (bits 4-7)
- Symbol B: Low nibble (bits 0-3)
-
Encoding Order: For every byte, Symbol A is encoded first, followed immediately by Symbol B.
-
Alphabet Size: The codebook always contains 16 entries (representing nibbles 0x0 through 0xF). A bit-length of 0 indicates the nibble is not present.
2-bit DNA encoding provides optimal compression for DNA sequences by encoding each nucleotide in 2 bits instead of 8 bits (75% size reduction). This is the most impactful encoding for pangenome data where sequences typically comprise 70-80% of file content.
Nucleotide Mapping:
- A = 00
- C = 01
- G = 10
- T = 11
Only the four uppercase bytes A, C, G and T are stored in packed_bases. Every other byte —
lowercase letters, ambiguity codes, or anything else — MUST be stored in the exception table, so the
method is lossless on any byte buffer.
Bit packing: Nucleotides are packed LSB-first, like every other bit stream in BGFA (see
Conventions). Each 2-bit code is a 2-bit codeword written high bit
first into the stream, exactly as Huffman codes are: nucleotide j occupies stream bits 2j (its high
bit) and 2j + 1 (its low bit). The first nucleotide therefore occupies bits 0-1 of the first byte, with
its high bit in bit 0, the second bits 2-3, the third bits 4-5, the fourth bits 6-7. Subsequent nucleotides
continue in subsequent bytes. Note that this is not the common layout that stores the numeric value of
the code in bits 2j+1..2j, which would give 0xE4 for ACGT instead of 0xD8.
Example: Sequence "ACGT" (4 nucleotides):
- A=00, C=01, G=10, T=11
- Packed:
0b11011000= 0xD8 (1 byte)
Example: Sequence "ACGTA" (5 nucleotides):
- A=00, C=01, G=10, T=11, A=00
- Packed:
0b110110000b00000000= 0xD8 0x00 (2 bytes, the 6 high bits of the second byte are padding)
Note: Unused bits in the final byte MUST be set to 0 when writing and MUST be ignored when reading.
Format — the method data is:
varint:nucleotide_count, the number of nucleotides in the decoded sequence, which is the length of the superstring being encoded, not the sum of the lengths of the individual segment sequences. This is an internal decoded item count, not the outer blob length: the blob length of Blob Framing is a byte count and MUST NOT be used here.- 1 byte: flags
- bit 0:
has_exceptions(1 if exception table present, 0 otherwise) - bits 1-7: reserved (MUST be 0 when writing; a reader MUST reject a non-zero value as a fatal error)
- bit 0:
packed_bases: exactlynucleotide_countnucleotides, 4 per byte (2 bits each), occupying exactlyceil(nucleotide_count / 4)bytes, with the unused bits of the final byte set to 0. Every position of the decoded sequence gets a nucleotide frompacked_bases, including the exception positions: a writer MUST write a placeholder (any of the four codes, conventionallyA) in the packed slot of every position that also appears in the exception table, and MUST then overwrite it via the table. A writer MUST NOT skip the packed slot of an exception position, because the decoder mapspacked_basespositionally onto the decoded sequence and would shift every later nucleotide.- If the
has_exceptionsflag is set:varint: exception countEvarintlist: exactlyEpositions, as 0-based indices into the decoded nucleotide sequence, in strictly increasing orderbytes: exactlyEexception characters (one byte per exception, in ASCII)
Validation. A reader MUST reject the field as a fatal error unless all of the following hold:
ceil(nucleotide_count / 4) bytes of packed_bases are present in the remaining method data; every exception
position is strictly less than nucleotide_count; the positions are strictly increasing; and E positions
followed by E characters are present in the remaining bytes. These checks MUST be performed before
allocating the decoded sequence, because nucleotide_count is attacker-controlled.
nucleotide_count and the decoded length are the same number. nucleotide_count is both the number of
nucleotides in the decoded sequence and the number packed into packed_bases; exceptions overwrite
positions of that same sequence rather than adding to it. So the decoder always ends up with exactly
nucleotide_count characters, whether there are exceptions or not.
Exception Handling:
Every byte of the superstring other than A, C, G and T is stored in the exception table with its
original value, which makes reconstruction exact. A writer MUST NOT store A, C, G or T as an
exception character, and a reader MUST treat one as a fatal error.
An exception position unambiguously identifies a character of the decoded sequence, not a byte or a
nibble of the packed stream, so no additional high/low-nibble selector is needed: the decoder expands
packed_bases into the nucleotide sequence and then overwrites position p of that sequence with the
corresponding exception character.
Case is preserved. Lowercase acgt are exceptions like any other byte, so acgt decodes
to acgt. This keeps soft-masked sequences intact, at the cost of compression on them; a writer that
expects many such bytes SHOULD pick another method.
Empty sequences: a nucleotide sequence of length 0 is encoded as nucleotide_count = 0, a flags byte
of 0x00, no packed_bases bytes, and no exception table, i.e. 2 bytes of method data.
Expected Compression (informative): 75% reduction on pure DNA sequences, slightly less with ambiguity codes.
Primary Use Case: Segment sequences, which are typically the largest data component in BGFA files.
Code 0x06 is reserved and MUST NOT be used in BGFA version 1. An earlier draft assigned it to a
byte-oriented arithmetic coder, but the required byte-exact details (register initialisation, the
renormalisation trigger, carry propagation into the pending count, and the final flush) were never pinned
down, and arithmetic coders are bit-incompatible at that level. Two conforming implementations would have
produced different files.
A reader MUST treat 0x06 as an unknown strategy code and report a fatal error. It may be assigned in a
future version, at which point this section must be replaced by a full specification.
The method data is exactly one bzip2 stream holding the superstring, whose byte length is exactly the blob length of Blob Framing.
Run-Length Encoding efficiently compresses sequences with repeated characters (homopolymers in DNA, repeated operations in other contexts). The method data is a sequence of chunks, each stored either raw or run-length encoded.
Format — the method data is:
varint: chunk countR- For each of the
Rchunks:- 1 byte: mode (
0x00= raw,0x01= RLE); any other value is a fatal error varint: chunk data length, in bytes- chunk data, of exactly that many bytes:
- raw mode: the bytes themselves, copied to the output
- RLE mode: a sequence of
[char: 1 byte][repeat: varint]pairs; each pair outputscharrepeatedrepeattimes
- 1 byte: mode (
The decoded superstring is the concatenation of the outputs of all chunks, in order.
Framing. RLE is self-delimiting through the leading chunk count. The outer blob length of Blob Framing is a byte count covering the whole of the method data described above, and is what a decoder uses to bound its reads; the chunk count is what tells it when to stop.
Validation. A reader MUST reject the field as a fatal error if a chunk data length exceeds the
remaining method data, and MUST bound R and every chunk data length by the method data length
before allocating. R = 0 is valid and encodes the empty superstring, and a chunk data length of 0 is
valid and outputs nothing. In RLE mode a chunk's pairs MUST consume the chunk data exactly: a reader
MUST reject a field as a fatal error if the pairs do not end precisely on the chunk data boundary. A
repeat of 0 is invalid and MUST be rejected, since it would encode no characters. The char of an RLE
pair is one raw byte and is not subject to any alphabet restriction. The decoded size is bounded by the
decoded-size cap of Limits and Validation, which a reader
MUST check before expanding a pair.
Writer guidance (informative). Any chunking that decodes to the superstring is valid, and a reader MUST accept it. The reference writer puts runs of 3 or more identical consecutive bytes in RLE chunks and everything else in raw chunks, which avoids expansion on non-repetitive data.
Expected Compression (informative): 30-50% reduction on sequences with homopolymers or repetitive patterns.
Primary Use Cases:
- DNA sequences with homopolymer runs (AAAAAAA, GGGGGG, TTTTTT)
- General string data with repeated characters
Burrows-Wheeler Transform + Huffman coding is intended for repetitive sequences like DNA, but it is lossless on any byte buffer. The superstring is cut into consecutive blocks of 65536 bytes (64KB); only the last block may be shorter. Each block is encoded independently by this pipeline:
- BWT. Consider the
ncyclic rotations of the block, where rotationjstarts at bytej. Sort them lexicographically, comparing bytes as unsigned values. The BWT output is the last column of the sorted rotation matrix:nbytes, ther-th being the last byte of ther-th sorted rotation. The primary index is the 0-based row of the sorted matrix that holds rotation 0 (the block itself). When the block is periodic, several rows hold rotation-equal strings; any of those rows is a valid primary index, since they all invert to the same block. - MTF. Apply the Move-to-Front transform to the BWT output. The MTF list is initialised to the 256 byte
values in increasing order (
0x00, 0x01, ..., 0xFF) at the start of every block. For each input bytec, output the current index ofcin the list, then movecto the front of the list. - Huffman. Encode the MTF output, a buffer of exactly
nbytes, with nibble-level Huffman: the result is exactly the method data of Huffman Coding with code0x04, i.e.[codebook_len][codebook][symbol_count][huffman_bitstream], withsymbol_count = 2 * n.
Format — the method data is:
uint32: number of BWT blocks, little-endian- For each block, in order:
uint32: primary index, little-endianuint32: block sizenin bytes (1..65536), little-endian- the
0x04Huffman method data of the MTF output, as in step 3. Its bitstream ends at the first byte boundary after thesymbol_count-th symbol, and the next block starts at that byte.
Example: a method data holding one block of 65536 bytes with primary index 0 begins 01 00 00 00
(block count 1), 00 00 00 00 (primary index 0), 00 00 01 00 (block size 65536). The block size is the
clearest case: 65536 = 0x00010000, so the least significant byte comes first, and a reader that assumed
big-endian would read 0x00000100 = 256.
Framing. The outer blob length varint of Blob Framing applies here as it does to
every method: it is a byte count of the whole method data, and the decoder bounds its reads with it. Each
block is self-delimiting through its own symbol_count.
Decoding. For each block, decode the Huffman data into n MTF bytes, invert MTF starting from the
initial list above, then invert the BWT using the primary index. Blocks are concatenated in order and the
result is the superstring.
Validation. A reader MUST reject the field as a fatal error if the block count is 0, if a block size is 0
or above 65536, if a block other than the last has a size other than 65536, if a primary index is not below
that block's size, if symbol_count is not 2 * n, if the Huffman data fails any check of
Huffman Coding, if a block overruns the method data, or if the block count is
so large that the per-block minimum of 44 bytes (4 + 4 + 2 + 32 + 1 + 1: primary index, block size,
codebook_len, codebook, a 1-byte symbol_count and at least 1 byte of bitstream) would overrun the method
data.
All of these checks MUST be performed before allocating, because the block count is attacker-controlled.
Empty and uniform buffers. A block always holds at least one byte, so the empty buffer cannot be encoded
with 0x09. The Huffman stage needs at least two distinct nibbles in each block's MTF output. A writer MUST
NOT use 0x09 for a buffer that violates either condition; it MUST pick another method.
Dictionary encoding is optimized for repetitive string data by replacing repeated strings with short references to a dictionary.
Dictionary encoding replaces the superstring layout of the strings type: when the second byte of the
compression code is 0x0A, the payload of a strings field is the dictionary layout below, and no
superstring, and no start/end positions, are written. The first byte of the compression code selects the
integer encoding used for the integer lists of this layout.
Format (Concatenation mode):
uint16: dictionary sizeN(number of unique strings), little-endianuintslist: dictionary entry offsets (N + 1values)- Offsets are cumulative from the start of the dictionary blob, and each end is excluded: entry
iisblob[offsets[i]:offsets[i+1]], of lengthoffsets[i+1] - offsets[i] offsets[N]equals the total length of the dictionary blob- Offsets are encoded using the integer encoding strategy given by the first byte of the 2-byte compression
code
0xHH0A
- Offsets are cumulative from the start of the dictionary blob, and each end is excluded: entry
varint: dictionary blob length — the number of bytes of the concatenated dictionary blob. As everywhere else in BGFA, this is a byte count. It is stored after the offsets, because the offsets are variable length, so it is the only way for a decoder to find where the entries beginbytes: concatenated dictionary entries, stored raw (uncompressed) with no terminators, of exactly that many bytes. A writer MUST NOT store the same string as two entriesuintslist: one dictionary index per string, in the original order of the strings, encoded using the same integer strategy as the offsets. The number of indices equals the number of strings in the field
Example: a dictionary of 3 entries starts with 03 00: N = 3 is a uint16 stored least significant
byte first, so a reader that assumed big-endian would read 0x0300 = 768.
Validation. A reader MUST reject the field as a fatal error if N is 0, if offsets[0] is not 0, if any
offset is greater than the next, if the last offset does not equal the dictionary blob length, if the
dictionary blob length exceeds the remaining bytes, if a dictionary index is not below N, or if the index
list does not end exactly at the end of the field. A reader is not required to check that the entries are
distinct. All of these checks MUST be performed before
allocating the dictionary or the index array, because N and the offsets are attacker-controlled.
Empty strings: a string that is empty is a valid dictionary entry with offsets[i] == offsets[i+1], so
empty segment sequences (GFA *) are representable. Because offsets[0] is 0 and indices start at 0, Elias
gamma (0x04) and omega (0x05) can never encode the offsets list, and a writer MUST NOT select them here.
Outside a strings field. When Dictionary is used as the SS method of a CIGAR code, the buffer is
treated as a list of exactly one string: N = 1, offsets [0, L] where L is the buffer length, and a
single index 0. The integer lists are encoded with varint (0x01), since a CIGAR code has no integer
byte for them.
Maximum dictionary size: 65535 entries (N is a uint16)
Expected Compression (informative): 60-90% reduction on highly repetitive data (e.g., sample IDs repeated across thousands of walks).
Primary Use Cases:
- Sample identifiers in walk blocks
- Segment names with common prefixes
- Path names with structural patterns
- Any string list with high repetition
For CIGAR strings, 4-byte strategy codes are used. The format and decomposition strategies are defined in the Strategy Code Format Summary.
The following decomposition strategies are available:
| Format | Bytes | Strategy |
|---|---|---|
0x00000000 |
[00, 00, 00, 00] |
none (identity); RR, II and SS reserved |
0x01?????? |
[01, RR, II, SS] |
numOperations + lengths + operations |
0x020000?? |
[02, 00, 00, SS] |
string (treat as plain string) |
A cigar strings field always contains exactly record_num entries, one per record of the containing block.
Entries are the GFA CIGAR strings; a path may carry several CIGARs separated by , within a single entry. A
GFA * is stored as the empty entry (see
CIGAR Decomposition Strategies), so an entry is never
*. The uncompressed_*_cigars_len field of the block is the sum of the byte lengths of the entries, without
any terminator, whatever the decomposition.
SS is any string method of String Encoding Algorithms, validated against
STRING_CODES (see
Strategy Code Validation Examples). The buffer it
encodes — the packed operations for 0x01, the newline-terminated entries for 0x02 — is treated like a
superstring, and the method data is exactly as defined for that method.
Bytes: [00, 00, 00, 00]
The record_num CIGAR entries are written as raw ASCII, each followed by a line feed (0x0A). The payload is
therefore record_num terminated entries; a decoder MUST split on 0x0A and drop the final terminator, which
yields exactly record_num entries. Because the terminator guarantees the last entry is present, an entry may
be the empty string, which is how a missing CIGAR (GFA *) is represented. The entry text is not compressed;
SS is reserved and MUST be 0x00; a reader MUST reject any other value as an invalid strategy code.
An entry MUST NOT contain a 0x0A byte, since 0x0A is the entry separator. A reader MUST treat an entry
count other than record_num after splitting, or a payload whose last byte is not 0x0A, as a fatal error.
Format: 0x01RRIISS
Bytes: [01, RR, II, SS]
Applicability. This decomposition can only represent entries that are empty or that are a single CIGAR
string matching ([1-9][0-9]*[MIDNSHP=X])+. If any entry of the field is something else — in particular an
entry holding several ,-separated CIGARs, an operation length of 0, or a length with leading zeros — the
CIGARs MUST be treated as strings: a writer MUST NOT use DD = 0x01 for that field and MUST use DD = 0x00
or DD = 0x02 instead.
Four components are encoded, in this order:
varint: the number of CIGAR entries, which MUST equalrecord_num; any other value is a fatal error- The list of the number of operations in each CIGAR entry (
uints,record_numvalues), encoded withII. An empty entry has 0 operations - The list of lengths of all operations of all entries, concatenated in entry order (
uints), encoded withRR. The total number of lengths is the sum of the operation counts in component 2, and every length MUST be at least 1 - The operations as a single packed buffer, encoded with
SS. See Packed Operations String
Component 1 tells a decoder how many operation counts follow, and the decoded counts tell it how many
lengths follow. The field as a whole is not self-delimiting: component 4 has no blob length, and its
method data occupies the rest of the owning compressed_*_cigars_len field, exactly. With SS = 0x00 its
length MUST be ceil(T / 2) bytes, where T is the total number of operations.
A decoder rebuilds each entry by writing, for each of its operations, the length in decimal (no leading zeros) followed by the operation letter.
Byte assignments:
- First byte (
0x01): Decomposition strategy (numOperations + lengths + operations) - Second byte (
RR): Integer encoding strategy for the operation lengths, e.g.0x01varint,0x02fixed16 - Third byte (
II): Integer encoding strategy for the operation counts, e.g.0x01varint,0x02fixed16 - Fourth byte (
SS): String encoding strategy for the packed operations, e.g.0x00none,0x04Huffman
Example: Strategy code 0x01010204 = Bytes [0x01, 0x01, 0x02, 0x04] means:
- First byte (
0x01): use the numOperations + lengths + operations decomposition - Second byte (
0x01): encode the operation lengths with varint - Third byte (
0x02): encode the operation counts with fixed16 - Fourth byte (
0x04): encode the packed operations with Huffman
Bytes: [02, 00, 00, SS]
The record_num CIGAR entries are written as raw ASCII, each followed by \n (0x0A), exactly as in the
none decomposition, and the resulting buffer is compressed as a single block with the string method SS.
After decoding, the buffer is split exactly as in the none decomposition, with the same checks.
Byte assignments:
- First byte (
0x02): Decomposition strategy (string) - Second byte (
RR): Reserved (MUST be0x00) - Third byte (
II): Reserved (MUST be0x00) - Fourth byte (
SS): String encoding strategy for the whole buffer
The payload is [blob length: varint][method data], framed as in Blob Framing: the blob
length is a byte count of the method data, and the method data MUST end exactly at the end of the owning
compressed_*_cigars_len field.
Example: Strategy code 0x02000003 = Bytes [0x02, 0x00, 0x00, 0x03] means:
- First byte (
0x02): use the string decomposition - Second byte (
0x00): reserved - Third byte (
0x00): reserved - Fourth byte (
0x03): compress the newline-terminated CIGAR buffer with LZMA
The SS component of the numOperations decomposition stores operation codes as nibbles. CIGAR operations
are mapped as follows:
M = 0x0 (match/mismatch)
I = 0x1 (insertion)
D = 0x2 (deletion)
N = 0x3 (skipped region)
S = 0x4 (soft clipping)
H = 0x5 (hard clipping)
P = 0x6 (padding)
= = 0x7 (sequence match)
X = 0x8 (sequence mismatch)
Codes 0x9 to 0xE are unassigned, and 0xF is the padding marker.
Layout: the operations of all entries are concatenated in entry order, two codes per byte:
- High nibble: the first operation of the pair
- Low nibble: the second operation of the pair
- If the total number of operations
Tis odd, the low nibble of the last byte is0xF
The decoded buffer MUST be exactly ceil(T / 2) bytes long. A reader MUST reject as a fatal error a buffer
of any other length, a code in 0x9..0xE, a 0xF anywhere except the low nibble of the last byte when T
is odd, and a low nibble of the last byte other than 0xF when T is odd. When T = 0 the buffer is empty.
Nibble order, not bit order. The operations buffer is packed at nibble granularity, high nibble first,
so the LSB-first bit-packing rule of Conventions does not apply to it:
once built, the buffer is an ordinary byte buffer and is handed to SS unchanged.
The buffer is then encoded with the string method SS, like any other byte buffer.
Example: the entry 10M2I5D has 3 operations M, I, D, i.e. codes 0x0, 0x1, 0x2:
- packed operations: high nibble
0x0and low nibble0x1gives0x01; the next byte has high nibble0x2and low nibble0xF(padding) giving0x2F - with
RR = II = 0x01(varint) andSS = 0x00(none), and assuming a single entry in the block, the whole payload is:01(one CIGAR entry)03(3 operations in this entry)0A 02 05(lengths 10, 2, 5)01 2F(packed operations, with no blob length: they run to the end of the field)