1 Introduction

The Box format is an open archive format designed for storing files with support for compression, checksums, extended attributes, and memory-mapped access. It provides platform-independent path encoding and efficient metadata storage through string interning.

1.1 Design Goals

• Platform Independence: Paths are encoded in a platform-neutral format that can be safely represented on all major operating systems.
• Compression: Multiple compression algorithms are supported, selectable per-file.
• Integrity: Optional Blake3 checksums for content verification.
• Efficiency: String interning for attribute keys reduces metadata size. Memory mapping enables zero-copy file access for uncompressed files. Block-level compression enables efficient random access for large compressed files.
• Extensibility: The attribute system allows arbitrary metadata without format changes.

1.2 File Extension

Box archives SHOULD use the .box file extension.

2 Terminology

The key words “MUST”, “MUST NOT”, “REQUIRED”, “SHALL”, “SHALL NOT”, “SHOULD”, “SHOULD NOT”, “RECOMMENDED”, “MAY”, and “OPTIONAL” in this document are to be interpreted as described in RFC 2119.

Archive: A Box format file containing zero or more entries.

Entry: A file, directory, or symbolic link stored in the archive.

Record: The metadata structure describing an entry.

Trailer: The metadata section at the end of the archive containing all records and attributes.

Chunked File: A file stored with block-level compression, enabling random access without decompressing the entire file.

3 File Structure Overview

A Box archive consists of five sections laid out sequentially:

The Header is always 32 bytes and located at offset 0. The Header contains a pointer to the Trailer, which stores record metadata. File content data is stored between the Header and Trailer. The Path FST follows the Trailer and provides path-to-record mapping (see Section 14). The Block FST, if present, follows the Path FST and provides logical-to-physical offset mapping for chunked files (see Section 15). Both FSTs are prefixed with a u64 length (little-endian), enabling efficient seeking past the Path FST to detect the Block FST’s presence.

All multi-byte integers in the Box format are stored in little-endian byte order unless otherwise specified.

4 Data Types

4.1 Fixed-Size Integers

4.2 Vu64 Encoding (FastVint)

Variable-size unsigned 64-bit integers (Vu64) are encoded using FastVint, a prefix-based variable-length encoding where the number of leading zeros in the first byte determines the total byte count.

Length Determination:

The number of leading zero bits in the first byte, plus one, gives the total byte count:

1xxx_xxxx  →  1 byte   (7 data bits)
01xx_xxxx  →  2 bytes  (14 data bits: 6 + 8)
001x_xxxx  →  3 bytes  (21 data bits: 5 + 16)
0001_xxxx  →  4 bytes  (28 data bits: 4 + 24)
0000_1xxx  →  5 bytes  (35 data bits: 3 + 32)
0000_01xx  →  6 bytes  (42 data bits: 2 + 40)
0000_001x  →  7 bytes  (49 data bits: 1 + 48)
0000_0001  →  8 bytes  (56 data bits: 0 + 56)
0000_0000  →  9 bytes  (64 data bits: 0 + 64)

Offset-Based Encoding:

FastVint uses offset-based encoding for denser packing. Each length tier has a base offset:

Data Byte Order:

After the prefix byte, remaining data bytes are stored in big-endian order.

Key Properties:

• Length is known from the first byte alone (no continuation scanning required)
• Maximum 9 bytes for u64 values
• This encoding does NOT enforce minimal representations; the same value MAY have multiple valid encodings
• Decoders MUST accept all valid encodings of a value, including non-minimal representations

4.3 String

Strings are encoded as:

[Vu64: byte length]
[UTF-8 bytes]

All strings MUST be valid UTF-8. Implementations MUST reject invalid UTF-8 sequences.

4.4 Vec<T>

Vectors (arrays) are encoded as:

[Vu64: element count]
[T encoding] * count

The following vector types are used in the format:

4.5 Vec<u8> (Byte Array)

Byte arrays are encoded identically to strings:

[Vu64: byte length]
[raw bytes]

4.6 RecordIndex

A RecordIndex is a 1-based index into the records array, encoded as Vu64:

[Vu64: index value]

Index values MUST be non-zero. An index value of n refers to records[n-1].

4.7 AttrMap

Attribute maps are encoded as:

[u64: byte count of remaining section (not including this field)]
[Vu64: entry count]
For each entry:
    [Vu64: key index into attr_keys]
    [Vec<u8>: value]

The leading byte count allows implementations to skip the entire attribute map without parsing individual entries.

5 Header

The Header is located at byte offset 0 and is exactly 32 bytes.

5.1 Header Structure

Total Size: 32 bytes

5.2 Magic Bytes

The magic bytes MUST be exactly 0xFF 0x42 0x4F 0x58 (the byte 0xFF followed by ASCII BOX).

The leading 0xFF byte is invalid UTF-8, causing any attempt to parse the file as a text string to fail immediately at byte 0.

5.3 Version

The current format version is 0x01 (1). Implementations SHOULD reject archives with unknown major versions.

5.4 Flags

The flags byte is a bitfield:

5.5 Alignment

The alignment field specifies the byte boundary to which file data is aligned. Valid values are powers of 2 from 1 to 65536. A value of 0 indicates no alignment (equivalent to 1).

When alignment is specified, padding bytes (value 0x00) are inserted before file data to ensure each file’s data starts at an offset that is a multiple of the alignment value.

Common alignment values:

• 0 or 1: No alignment (most compact)
• 4096: Page alignment (optimal for memory mapping)
• 512: Sector alignment

5.6 Reserved Fields

All reserved fields (reserved1, reserved2, reserved3) MUST be set to zero when writing and MUST be ignored when reading to allow for future format extensions.

5.7 Binary Layout

Legend: FF 42 4F 58 = magic, VV = version, XX = flags, RR = reserved, AA = alignment, TT = trailer offset

6 Data Section

The Data Section immediately follows the Header and contains the actual file content.

6.1 Layout

File data is stored contiguously, with optional padding between files when alignment is enabled. The Data Section starts immediately after the Header. When alignment is disabled, this is offset 0x20 (32 bytes). When alignment is enabled, padding bytes (0x00) are inserted so that the first file’s data begins at an aligned offset. The Data Section extends to the trailer offset.

6.2 Alignment Padding

When header.alignment > 1, padding bytes (0x00) are inserted before file data such that:

file_data_offset % alignment == 0

The amount of padding before each file is:

padding = (alignment - (current_offset % alignment)) % alignment

7 Trailer (Metadata)

The Trailer contains all archive metadata encoded as BoxMetadata.

7.1 BoxMetadata Structure

[Vec<AttrKey>: attr_keys]
[AttrMap: attrs]
[Vu64: dictionary_length]
[bytes: dictionary]
[Vec<Record>: records]

Fields are encoded in the order shown, using the data type encodings from Section 4. The dictionary field is encoded as a Vu64 length followed by raw bytes; length=0 means no dictionary is present.

7.2 Attribute Key Table (attr_keys)

The attribute key table provides string interning for attribute keys. Each entry consists of:

[u8: type tag]
[String: key name]

The type tag indicates the expected value type for this attribute key. See Section 7.3 for type tag values.

Keys are referenced by their 0-based index in this table.

7.3 Attribute Value Types

Type Tag Values:

When serializing: keys are written in symbol order (0, 1, 2, …).

When deserializing: strings are assigned symbols in the order read. The type tag determines how the attribute value is interpreted.

7.4 Archive Attributes (attrs)

The attrs field stores archive-level attributes as an AttrMap. Common archive attributes include creation tools, comments, or custom metadata.

7.5 Dictionary

The dictionary field contains a Zstd dictionary used for compression. When present (non-empty), all records compressed with Zstd MUST use this dictionary for both compression and decompression. The dictionary is ignored for other compression methods (Stored, XZ).

Dictionary training is typically performed at archive creation time using ZDICT_trainFromBuffer() or equivalent. A recommended dictionary size is 32KB-128KB, trained on representative samples from the archive contents totaling approximately 100× the dictionary size.

When dictionary is empty, Zstd compression operates without a dictionary.

The dictionary provides two benefits:

1. Improved compression ratio, especially for small files with shared patterns
2. More predictable compression ratios, which aids in estimating compressed block sizes for chunked files

8 Record Types

Records describe entries in the archive. Each record begins with a 1-byte type/compression identifier.

8.1 Type/Compression Byte

The first byte of each record encodes both the record type and compression method:

[type_compression: u8]

Layout:

Bits 0-3: Record type
Bits 4-7: Compression method

Record Type Values:

Compression Values:

Combined Examples:

8.2 Directory Record (Type 0x01)

Directories have no associated data in the Data Section.

Structure:

[type_compression: u8]  // Always 0x01
[String: name]
[AttrMap: attrs]

Binary Layout:

8.3 File Record (Type 0x02)

Files store their content in the Data Section.

Structure:

[type_compression: u8]
[length: u64]              // Compressed length in data section
[decompressed_length: u64] // Original file size
[data: u64]                // Byte offset in archive
[String: name]
[AttrMap: attrs]

Binary Layout:

When compression == Stored, length == decompressed_length.

8.4 Symlink Record (Type 0x03)

Symbolic links point to other entries within the archive.

Structure:

[type_compression: u8]  // Always 0x03
[String: name]
[Vu64: target (RecordIndex)]
[AttrMap: attrs]

Constraints:

• Target MUST be a valid RecordIndex pointing to an existing record
• Circular symlinks are not permitted
• The target record MUST NOT be another symlink

Binary Layout:

8.5 External Symlink Record (Type 0x0B)

External symlinks point to paths outside the archive. This record type is only valid when the EXTERNAL_SYMLINKS flag is set in the header.

Structure:

[type_compression: u8]  // Always 0x0B
[String: name]
[String: target]
[AttrMap: attrs]

Target Path Format:

The target path uses BoxPath encoding (see Section 9) with one relaxation: .. components are permitted to allow the symlink to escape the archive root. The path is stored with \x1F (Unit Separator) as the component separator.

Constraints:

• The header MUST have the EXTERNAL_SYMLINKS flag (bit 0) set
• Target is a relative path from the symlink’s location
• Implementations MUST validate .. does not escape the extraction directory without explicit user consent

Binary Layout:

Extraction Behavior:

When extracting an external symlink record, implementations:

1. Convert the stored target path from BoxPath format (\x1F separators) to platform path format
2. Create a symbolic link at the record’s location using the converted relative target path

Security Considerations:

External symlinks can point to arbitrary locations outside the extraction directory. This presents security risks:

• Implementations MUST require explicit user consent before extracting archives containing external symlinks.
• This feature is opt-in at both archive creation time (setting the header flag) and extraction time.
• Extraction tools SHOULD warn users when processing archives with external symlinks.

8.6 Chunked File Record (Type 0x0A)

Chunked files store content in fixed-size blocks, each independently compressed. This enables random access to large compressed files without decompressing the entire file.

Structure:

[type_compression: u8]     // 0x0A | compression_method
[block_size: u32]          // Size of each block before compression
[length: u64]              // Total compressed length
[decompressed_length: u64] // Total original file size
[data: u64]                // Byte offset to first block
[String: name]
[AttrMap: attrs]

Binary Layout:

Decompression:

To read bytes at logical offset O within a chunked file, use the Block FST lookup procedure described in Section 15.5.

Recommended Block Size:

A block size of 2MB (2,097,152 bytes) is RECOMMENDED. This aligns with common hugepage sizes and provides a good balance between compression ratio and random access granularity.

9 Path Encoding

Paths in Box archives use a platform-independent encoding called BoxPath.

9.1 BoxPath Format

BoxPath paths are sequences of components separated by U+001F UNIT SEPARATOR (hex \x1F).

Properties:

• Paths are always relative (no leading separator)
• No trailing separator
• Empty components are not permitted
• Components . and .. are not permitted
• Components cannot contain platform path separators (/ or \)
• Components cannot contain null bytes

9.2 Separator Choice

The U+001F separator was chosen because:

1. It forces explicit handling - developers cannot be lazy and treat paths as platform-native strings
2. It avoids confusion with URL scheme prefixes (file://, http://) that would occur with /
3. It is truly platform-agnostic - neither Unix nor Windows “owns” this separator
4. It is illegal in filenames on all major platforms, preventing ambiguity

9.3 Platform Conversion

When extracting archives, implementations MUST convert BoxPath paths to platform-native paths:

Example:

BoxPath:  foo\x1Fbar\x1Fbaz.txt
Unix:     foo/bar/baz.txt
Windows:  foo\bar\baz.txt

9.4 Unicode Normalization

All paths MUST be stored in NFC (Canonical Decomposition, followed by Canonical Composition) normalized form. Implementations MUST normalize paths before storage and comparison.

10 Compression

Box supports multiple compression methods, selectable per-file.

10.1 Supported Methods

10.2 Zstd Configuration

When using Zstd:

• Compression level: Implementations SHOULD allow user-configurable levels (1-22)
• Default level: 3 (good balance of speed and ratio)
• Dictionary: If BoxMetadata.dictionary is non-empty, it MUST be used

10.3 XZ Configuration

When using XZ:

• Preset: Implementations SHOULD use preset 6 by default
• Integrity check: CRC64 is RECOMMENDED

10.4 Stored (Uncompressed)

When compression is Stored (0x00):

• length equals decompressed_length
• Data is stored verbatim
• Useful for already-compressed files (images, videos) or when memory mapping is desired

10.5 Dictionary Usage

When a dictionary is present in BoxMetadata.dictionary (Section 7.5), it MUST be used for all Zstd-compressed content in the archive, including:

• Whole-file compressed files
• Individual blocks in chunked files

The dictionary is loaded once when opening the archive and reused for all Zstd decompression operations. The dictionary has no effect on Stored or XZ-compressed content.

11 Checksums

Box archives support content checksums for integrity verification.

11.1 Supported Algorithms

11.2 Checksum Storage

Checksums are stored as record attributes:

attrs["blake3"] = <32-byte hash>

The checksum is computed over the decompressed content.

11.3 Verification

Implementations SHOULD verify checksums when:

1. Extracting files (if checksums are present)
2. Explicitly requested by the user

Verification failures MUST be reported to the user. Implementations MAY offer options to proceed despite failures.

12 Standard Attributes

This section defines standard attribute keys that implementations SHOULD recognize.

12.1 Timestamps

Box Epoch: 2026-01-01 00:00:00 UTC

Timestamps are OPTIONAL and stored as signed variable-length integers (Vi64, zigzag encoded) representing minutes since the Box epoch. The signed format supports dates before 2026. Minute precision is sufficient for typical archive use cases.

12.2 Sub-Minute Precision

For applications requiring higher precision:

Seconds and nanoseconds attributes are OPTIONAL. If present, they provide additional precision beyond the minute-level timestamp. If nanoseconds is present, these take precedence over the seconds attribute.

12.3 Unix Permissions

unix.mode Storage:

The mode value includes the file type bits in the standard Unix format:

• Regular file: 0o100000 + permissions
• Directory: 0o040000 + permissions
• Symlink: 0o120000 + permissions

Extraction Behavior:

If unix.mode is not present:

• Files: 0o100644 (rw-r–r–)
• Directories: 0o040755 (rwxr-xr-x)
• Symlinks: 0o120777 (rwxrwxrwx)

If unix.uid/unix.gid are not present, implementations SHOULD:

1. Check archive-level unix.uid/unix.gid attributes
2. Fall back to current user’s UID/GID

12.4 Attribute Encoding

Attribute values are stored as raw bytes (Vec<u8>). The type tag stored with the attribute key (see Section 7.2) determines how to interpret the value.

Standard Attribute Types:

Applications MAY define custom attributes with any type tag.

13 Implementation Guidance

This section provides non-normative guidance for implementers.

13.1 Memory Mapping

Box archives are designed to support memory-mapped access:

1. Use appropriate alignment (e.g., 4096 for page alignment)
2. Store files with compression = Stored for direct access
3. The FST structure enables O(m) path lookups where m is path length

13.2 Streaming Creation

Archives can be created in a streaming fashion:

1. Write header with placeholder trailer offset
2. Write file data sequentially, recording offsets
3. Write trailer with all records
4. Build and write Path FST (and Block FST if needed)
5. Seek back and update header with trailer offset

13.3 Large File Handling

For files larger than available memory:

1. Use chunked file records for random access
2. Stream decompression for sequential access
3. Consider block size trade-offs (smaller = more overhead, larger = more memory)

13.4 Error Recovery

The trailer-at-end design means truncated archives lose metadata. Implementations MAY:

1. Store periodic checkpoints during creation
2. Implement recovery tools that scan for record boundaries
3. Use file system features (copy-on-write, journaling) for durability

14 Path FST

The Path FST (Finite State Transducer) provides efficient path-to-record mapping.

14.1 Overview

The FST maps BoxPath strings to RecordIndex values. It supports:

• O(m) exact lookups where m is path length
• Prefix queries (enumerate all paths under a directory)
• Memory-efficient storage through prefix sharing

14.2 FST Layout

The Path FST is located immediately after the Trailer:

The length prefix encodes the total size of the FST data (Header through Cold Section, not including the length prefix itself).

The Block FST (if present) uses the same structure (length prefix followed by FST data) and follows immediately after the Path FST.

14.3 FST Header

The FST Header is 24 bytes and located at the start of the FST section.

The Hot Section starts at offset 24 + node_count × 8 (immediately after the Node Index). The root node is always node 0.

Implementations MUST reject FST data where magic bytes do not match or version is unsupported.

14.4 Node Index

The Node Index is an array of node_count entries, with each entry being 8 bytes.

Entry Format:

Offsets are relative to the start of their respective sections. Node IDs are indices into this array (node 0 = first entry, node 1 = second entry, etc.).

14.5 Hot Section

The Hot Section contains compact node headers optimized for cache efficiency. Each node’s hot data has the following structure:

Flags Byte:

Lookup Data:

The lookup data format depends on the INDEXED flag:

• If INDEXED (>16 edges): 256-byte lookup table where table[byte] returns the edge index for that byte value, or 0xFF if no edge exists for that byte.

• If not INDEXED (<=16 edges): Array of edge_count bytes containing the first byte of each edge label, sorted in ascending order. Used for binary search or SIMD-accelerated lookups.

Offsets Array:

Array of edge_count entries, each a u16. Each offset points to the corresponding edge’s data within this node’s cold section data block.

14.6 Cold Section

The Cold Section contains edge data and final output values. Each node’s cold data has the following structure:

Edge Fields:

Final Output:

If the IS_FINAL flag is set, the final output value is stored at the end of the node’s cold data block. This value is added to the accumulated output when the traversal terminates at this node.

14.7 Path Encoding in FST

Paths stored in the FST use the same encoding as BoxPath (Section 9):

• Components are separated by U+001F UNIT SEPARATOR (\x1F)
• Paths are stored without leading separators
• Example: foo/bar/baz.txt → foo\x1Fbar\x1Fbaz.txt

Build Requirements:

• Keys MUST be inserted in strict lexicographic byte order
• Duplicate keys are not permitted
• Values are non-zero u64 record indices

14.8 Output Value Accumulation

The FST stores output values along edges and at final nodes. The final lookup value is computed by:

1. Starting with accumulated value = 0
2. For each edge traversed: accumulated = accumulated.wrapping_add(edge.output)
3. If the final node has IS_FINAL set: accumulated = accumulated.wrapping_add(final_output)

For the Path FST, the result is a RecordIndex value. For the Block FST, the result is a physical byte offset.

14.9 FST Implementation Notes

Adaptive Node Format:

The FST uses an adaptive node format inspired by Adaptive Radix Trees (ART):

• Nodes with more than 16 edges use indexed format (256-byte lookup table)
• Nodes with 16 or fewer edges use compact format (sorted first-bytes array)

The threshold of >16 balances memory usage against lookup performance.

Hot/Cold Separation:

Data is separated into “hot” (frequently accessed during traversal) and “cold” (accessed only when needed) sections. This improves cache utilization during lookups.

SIMD Optimization:

Implementations MAY use SIMD instructions for compact node lookups:

• x86_64: SSE2 _mm_cmpeq_epi8 for 16-byte parallel comparison
• aarch64: NEON vceqq_u8 for similar parallel comparison

14.10 FST Constants

These constants apply to both Path FST and Block FST:

15 Block FST

The Block FST provides logical-to-physical offset mapping for chunked files. It is located immediately after the Path FST.

Presence Detection:

Read the Path FST length prefix, then compute path_fst_end = trailer_end + sizeof(length_prefix) + path_fst_length. If path_fst_end < EOF, the Block FST begins at that position (starting with its own length prefix). If path_fst_end = EOF, no Block FST is present.

15.1 Block FST Overview

The Block FST maps (record_index, logical_offset) pairs to physical offsets within the archive’s data section. Block lookups use predecessor queries to find the block containing any arbitrary byte offset.

15.2 Block FST Format

The Block FST uses the same structure as the Path FST: a Vu64 length prefix followed by the FST data (Section 14.3 – Section 14.6, Section 14.8 – Section 14.10). Section 14.7 (Path Encoding) does not apply; Block FST uses fixed-width keys as described below.

15.3 Block FST Key Format

Keys are 16-byte fixed-width values:

• record_index: 1-based index of the chunked file record
• logical_offset: Logical byte offset of the block start (always a multiple of block_size)

Big-endian encoding ensures lexicographic byte order matches numeric order.

Example keys for record 5 with 2MB blocks:

15.4 Block FST Value Format

Values are physical byte offsets (u64) pointing to the start of the compressed block data within the archive.

15.5 Block Lookup

To find the compressed data for a logical offset O in a chunked file with record index R:

1. Construct key: [R as u64, big-endian][O as u64, big-endian]
2. Query Block FST for predecessor (largest key ≤ query key)
3. Verify the result key has matching record index R
4. Result value is the physical offset of the compressed block
5. Read and decompress the frame (compression frames are self-delimiting)
6. The offset within the decompressed block is O - block_logical_offset where block_logical_offset is from the result key

Example: Record 5 with 2MB (2,097,152 byte) block size. Block FST contains:

Query: 17KB (17,408 bytes)

1. Construct key: [5][17408]
2. Predecessor result: [5][0] (since 0 ≤ 17408 < 2097152)
3. Read from physical_offset_a, decompress
4. Offset within block: 17408 - 0 = 17408

Query: 2MB exactly (2,097,152 bytes)

1. Construct key: [5][2097152]
2. Predecessor result: [5][2097152] (exact match)
3. Read from physical_offset_b, decompress
4. Offset within block: 2097152 - 2097152 = 0

Query: 2MB + 17KB (2,114,560 bytes)

1. Construct key: [5][2114560]
2. Predecessor result: [5][2097152] (since 2097152 ≤ 2114560 < 4194304)
3. Read from physical_offset_b, decompress
4. Offset within block: 2114560 - 2097152 = 17408

15.6 Block FST Build Requirements

• Keys MUST be inserted in strict lexicographic byte order
• For a single chunked file, this means blocks are inserted in logical offset order
• Across multiple files, files are ordered by record index

15.7 Streaming Decompression

Compression frames are self-delimiting, so implementations can decompress blocks without knowing their compressed size in advance. The Block FST provides the starting offset; the decompressor determines where the frame ends.

15.8 Block FST Constants

In addition to the shared constants in Section 14.10: