hexatess-code

Hexatess Code Specification — Version 0.3

Status: Stable draft (reference implementation available) Date: 2026-09-01 License: CC-BY-4.0 (this document); reference code under MIT

Hexatess Code is an experimental two-dimensional barcode built on a hexagonal module grid with a hexagonal bullseye finder pattern, spiral serialization from the centre outwards, a Reed-Solomon protected header and a continuously selectable error-correction budget of 5–90 % (Aztec-style).

This document contains everything needed to implement an independent encoder or decoder in any language. The key words MUST, MUST NOT, SHOULD and MAY are to be interpreted as described in RFC 2119.

What changed in v0.3. One formerly reserved header bit is now the payload compression flag (§4.3): when set, the payload is a zlib stream (RFC 1950) of the UTF-8 text. Symbols produced under the v0.2 rules remain valid v0.3 symbols (flag = 0), so the change is strictly additive.

Design heritage. The architecture deliberately follows proven ideas: the bullseye + spiral layout follows Aztec Code (ISO/IEC 24778), independent RS blocks with ≤ 50 data bytes follow Data Matrix / Aztec practice, and the GF(256) field with primitive polynomial 0x11D follows QR Code and Aztec. The hexagonal grid follows MaxiCode (ISO/IEC 16023) — extended, unlike MaxiCode, to variable-size, high-capacity symbols.

1. Conventions and terminology

Module — one hexagonal cell of the grid; its value is a bit: 1 = dark (printed), 0 = light (background).
Axial coordinates (q, r) — integer coordinates of a module. The six neighbour directions in fixed traversal order are:
```
DIRS = [(+1, 0), (+1, -1), (0, -1), (-1, 0), (-1, +1), (0, +1)]
```
Ring k — the set of modules at hex distance k from the origin, where hex distance is max(|q|, |r|, |q + r|). Ring 0 is the single origin module (0, 0).

Canonical ring order — ring k ≥ 1 starts at module (-k, +k) and then takes k steps in each direction of DIRS in order, appending every visited module. Ring k therefore contains 6k modules. Pseudocode:

function hex_ring(k):
    if k = 0: return [(0, 0)]
    cells ← []
    (q, r) ← (-k, +k)
    for d in 0 .. 5:
        repeat k times:
            append (q, r) to cells
            (q, r) ← (q, r) + DIRS[d]
    return cells

Radius of a symbol — the largest ring index present, rmax.
The number of modules within radius n is the centered hexagonal number 3n(n+1) + 1.

2. Symbol structure

A Hexatess Code symbol consists of:

Region	Rings	Content
Bullseye	0 … 4	finder pattern, `bit = 1 − (k mod 2)`
Key ring	5	orientation key (see §2.2)
Data region	6 … rmax	header + masked payload, spiral order (§3, §4)

rmax MUST be between 7 and 31. The data region of radius rmax contains 3·rmax·(rmax+1) + 1 − 91 modules.

2.1 Bullseye finder

For every module of ring k, 0 ≤ k ≤ 4, set bit = 1 − (k mod 2). Consequence (v0.2): the centre module is DARK (ring 0 → 1), ring 1 is light, ring 2 dark, ring 3 light, ring 4 dark. Note: v0.1 used the opposite polarity (light centre, bit = k mod 2). The dark centre improves finder detectability — it gives the bullseye a solid high-contrast core that survives blur and low-resolution imaging, matching the finder conventions of Aztec Code and MaxiCode. The change is format-breaking; conformance vectors for v0.1 are superseded.

2.2 Orientation key (ring 5)

All 30 modules of ring 5 are LIGHT (0), except the first two modules in canonical ring order — (−5, +5) and (−4, +5) — which are DARK (1). The pair breaks the 60-fold rotational symmetry of the hexagonal lattice and defines the spiral start direction for camera decoders: the vector from the symbol centre to the key pair points “backwards along the spiral start”.

3. Data region and spiral serialization

Payload bits are placed in spiral order: all modules of ring 6 in canonical order, then ring 7, and so on up to ring rmax. The data region therefore contains, in order:

data_cells = concat(hex_ring(k) for k = 6 .. rmax)

Bit i of the full bitstream (§4) is written to data_cells[i]. If the bitstream is shorter than the data region, the remaining modules MUST be set to the alternating padding pattern 0, 1, 0, 1, … (indexed from 0 at the first empty module).

4. Bitstream structure

+--------------------+-----------------------------------+
| mode message       | payload                           |
| 80 bits (10 bytes) | (data + ECC + padding)            |
| never masked       | masked (§6)                       |
+--------------------+-----------------------------------+

4.1 Mode message (header)

5 data bytes, each protected by a separate Reed-Solomon code (§5), giving 10 bytes = 80 bits. Bit layout, MSB first:

Byte	Bits	Field	Range
0	5	`rmax` (symbol radius)	7 … 31
0	3	`mask_id`	0 … 7
1	5	`ec_pct / 5`	1 … 18
1	3	`block_count >> 5` (high)	0 … 7
2	5	`block_count & 0x1F` (low)	—
2	3	`data_len >> 9` (high)	0 … 7
3	8	`data_len >> 1` (middle)	—
4	1	`data_len & 1` (low, leftmost)	—
4	1	`compressed` (v0.3, §4.3)	0 … 1
4	6	padding (zero)	0

ec_pct MUST be a multiple of 5 between 5 and 90 (only ec_pct/5 is stored).
data_len is the stored payload byte length (§4.3), up to 4095.
The mode message is never masked — it contains the mask id.
In v0.2 bit 6 of byte 4 was padding (zero); v0.3 defines it as the compression flag. Decoders SHOULD treat unknown flag values as a corrupt symbol.

Pseudocode (packing):

b0 = (rmax << 3) | mask_id
b1 = (ecq << 3) | (block_count >> 5)          # ecq = ec_pct / 5
b2 = ((block_count & 0x1F) << 3) | (data_len >> 9)
b3 = (data_len >> 1) & 0xFF
b4 = ((data_len & 1) << 7) | (compressed << 6)
mode_data = [b0, b1, b2, b3, b4]
mode = RS_encode(mode_data, ecc=5)            # 10 bytes total

4.2 Payload layering

Let data be the UTF-8 payload (data_len bytes) and blocks the block plan (§5.2). The unmasked payload bitstream is:

Data part: the bytes of all blocks in block order (block 0 data, block 1 data, …),
ECC part: the Reed-Solomon ECC symbols of all blocks in block order (block 0 ECC, block 1 ECC, …),
Padding: alternating 0, 1, 0, 1, … until the data region is exactly filled.

Note the interleaving level: all data of all blocks first, then all ECC of all blocks — each group internally in block order.

4.3 Payload compression (v0.3)

Bit 6 of header byte 4 selects the payload byte stream:

compressed = 0 — the payload bytes are the raw UTF-8 text (the v0.2 layout). data_len is the text length in bytes.
compressed = 1 — the payload bytes are a zlib stream (RFC 1950, DEFLATE) of the UTF-8 text. data_len is the length of the stored stream; the encoder SHOULD use the highest practical compression level (the reference uses zlib level 9). After Reed-Solomon recovery the decoder MUST inflate the stream and then interpret the result as UTF-8.

Encoders SHOULD set the flag only when it strictly reduces the stored length (short payloads grow from the stream overhead); the reference compress="auto" rule is compress iff len(zlib(text)) < len(text). Decoders MUST support both modes. A zlib stream that fails to inflate MUST be rejected as a corrupt symbol.

5. Error correction

5.1 Reed-Solomon over GF(256)

Field: GF(2^8) with primitive polynomial x^8 + x^4 + x^3 + x^2 + 1 = 0x11D, generator α = 2 (identical to QR Code and Aztec Code).
Code: systematic RS, generator polynomial g(x) = ∏_{i=0}^{nsym−1} (x − α^i).
Encoding: polynomial long division of (m(x) · x^nsym) by g(x); the codeword is data || remainder (nsym trailing ECC symbols).
Decoding: syndromes → Berlekamp–Massey locator → Chien search → Forney magnitudes. A block MUST be rejected if the number of found errors exceeds ⌊nsym/2⌋ or if the corrected word fails syndrome verification.

5.2 Block plan

The payload is split into independent RS blocks, each carrying at most 50 data bytes:

function plan_blocks(data_len, ec_pct):
    if data_len = 0: return [(0, 2)]
    bc ← ceil(data_len / 50)
    (base, extra) ← divmod(data_len, bc)      # balanced block sizes
    blocks ← []
    for i in 0 .. bc-1:
        size ← base + (1 if i < extra else 0)
        ecc  ← max(2, ceil(size · ec_pct / 100))
        ecc  ← min(ecc, 255 − size)           # hard RS limit
        append (size, ecc) to blocks
    return blocks

block_count (the number of blocks) MUST be ≤ 255; combined with the 12-bit data_len field and the 31-ring radius limit this yields the practical capacity of §8.

The mode message itself is a single RS block with 5 data bytes and 5 ECC symbols (corrects up to 2 byte errors).

6. Masking

The payload bitstream (§4.2, data + ECC + padding, before header placement) is XORed bit-by-bit with a deterministic pseudo-random stream selected from 8 candidates:

function mask_bit(index, mask_id):            # index = position in payload
    x = (index · 1103515245 + 12345 + mask_id · 2654435761) & 0x7FFFFFFF
    x = x XOR (x >> 13)
    return (x >> 19) & 1

Mask selection SHOULD evaluate all 8 masks and minimise the penalty

score(mask) = |2·dark − total|               # balance term
            + count(adjacent equal pairs)    # repetition term

with ties resolving to the lowest mask id. Encoders MAY force a specific mask; decoders MUST honour the mask id in the header.

7. Encoding procedure

Validate ec_pct (multiple of 5, 5…90); encode the text to UTF-8.
Optionally compress (§4.3): when compression is enabled and strictly reduces the length, replace the byte string with its zlib stream and set compressed = 1; in both cases data_len ≤ 4095 counts the stored bytes.
Compute blocks = plan_blocks(data_len, ec_pct).
Compute the required bit count need = 80 + 8 · (data_len + Σ ecc) and the smallest rmax ∈ 7…31 with modules(6..rmax) ≥ need (or honour a caller minimum radius).
Build the unmasked payload stream (§4.2).
Select and apply a mask (§6).
Build and place the mode message with the final mask id.
Place header + masked payload in spiral order (§3); pad the tail.
Stamp bullseye (§2.1) and key ring (§2.2).

8. Capacity

Data-region modules and maximum payload byte counts (rounded down by the exact block rule of §5.2):

rings (rmax)	modules	EC 5	EC 30	EC 55	EC 90
8	126	3	3	3	2
10	240	18	15	12	10
12	378	35	28	23	19
14	540	53	43	36	30
17	828	87	71	59	48
20	1170	127	103	87	71
24	1710	191	155	130	106
28	2346	265	216	181	148
31	2886	329	266	225	183

The 12-bit length field allows up to 4095 bytes, but the radius limit (31 rings) caps capacity at 329 bytes (EC 5). Larger radii are a candidate extension.

With the v0.3 compression flag the effective text capacity is considerably higher for compressible content: e.g. an 849-byte Slovene paragraph stores in 203 bytes and fits at rmax 28 (raw it exceeds the radius limit), and a 250-byte repetitive payload stores in 12 bytes. Incompressible data (random bytes, already-compressed text) is unaffected.

9. Rendering recommendations

Modules are pointy-top hexagons. With module radius s, the centre of module (q, r) maps to x = s·√3·(q + r/2), y = s·1.5·r.
Corners of a module lie at angles 60°·i − 30°, i = 0…5.
Hexagons SHOULD be drawn at ≥ 99 % of nominal size to avoid hairline gaps between adjacent dark modules; the reference draws at 99.5 % with 3× supersampling.
Quiet zone MUST be ≥ 1 module on all sides; the reference default is 1.5 modules.
Dark/light contrast SHOULD be ≥ 40 % (the reference uses near-black rgb(24, 22, 18) on white).

10. Decoding procedure (reference)

Detect the hexagonal bullseye (concentric alternating rings) and the key pair on ring 5; establish centre, scale and rotation.
Sample every data-region module; build the bitstream in spiral order (§3).
Read the 80-bit mode message; RS-correct it (capacity: 2 byte errors); unpack parameters (§4.1). Reject the symbol if correction fails.
Unmask the payload with mask_id (§6).
Rebuild the block plan (§5.2) from data_len and ec_pct; RS-correct each block independently; reject on failure.
If the compression flag (§4.3) is 1, inflate the payload with zlib (RFC 1950); reject the symbol if inflation fails.
Decode the payload bytes as UTF-8.

11. Design notes and future candidates

Centre polarity (resolved in v0.2). The bullseye centre is DARK (bit = 1 − (k mod 2)), chosen for stronger detectability; the opposite light-centre polarity of v0.1 is deprecated.
Erasure decoding. Modules occluded by a detected blob can be declared erasures, doubling correctable symbol counts (RS corrects nsym erasures vs nsym/2 errors). Not part of v0.3.
Camera decoding (shipped in lib v0.3.0). The symbol format is unchanged; the reference repository now ships an optional photo decoder (hexatess.camera, the [camera] extra). It locates the bullseye under merged-blob and illumination hazards, fits a homography on the 91 known finder cells, disambiguates the canonical frame with the RS-protected header across all six 60-degree model rotations, refits a polynomial correction field on the 171 known cells (finder + verified header), and samples with a local adaptive threshold. Note for implementers: the two-cell key alone is too weak to pin the canonical frame — a conformant photo decoder should validate the frame via the header, exactly like the reference does. Ideal-grid decoding (§8) is unaffected.
Larger radii. Extending rmax beyond 31 requires only widening the header’s radius field (a breaking change).
Other compressors. zlib (RFC 1950) was chosen for v0.3 because every ecosystem has a mature inflate implementation; the flag field leaves room for future mode bits (e.g. bzip or a text model) but modes MUST be introduced one bit at a time so old decoders fail cleanly instead of mis-decoding.
Mask quality. The LCG mask is fast and deterministic but not optimized against any adversarial pattern class; penalty terms may be extended in a future minor revision without breaking decoders (selection is an encoder-side choice).

12. Conformance

An implementation is conformant with this specification if, for every vector in test_vectors/vectors_v0.3.json:

its encoder produces the recorded symbol parameters, mode message bytes and canonical grid serialization for the given input; and
its decoder returns the recorded text for the recorded grids, including the deterministically damaged ones (ECC correction) and the recorded decode failure.

Canonical grid serialization: bits ordered by ring 0…rmax, within each ring in canonical order (§1); packed MSB-first into bytes, right-padded with zero bits to a byte boundary; written as lowercase hexadecimal.

Appendix A — Constants

Constant	Value	Meaning
`GF_PRIM_POLY`	0x11D	GF(256) primitive polynomial
`BULLSEYE_RINGS`	4	finder rings (0…4)
`KEY_RING`	5	orientation key ring
`DATA_RING0`	6	first payload ring
`MAX_RINGS`	31	radius limit (v0.2)
`BLOCK_DATA_MAX`	50	data bytes per RS block
`MODE_BYTES`	5	header data bytes
`MODE_ECC`	5	header ECC symbols
`MODE_BITS`	80	header bit length
`MIN/MAX_EC_PCT`	5 / 90	EC budget bounds (step 5)
`MAX_DATA_BYTES`	4095	length-field limit
masks	8	mask ids 0…7

This site is open source. Improve this page.