Base67

English | 简体中文

A zero-escape, padding-free, lexicographically order-preserving, u128-quantum binary-to-text encoding with native $\mathrm{GF}(67)$ prime-field error detection and Reed–Solomon self-healing.

Alphabet (67 chars, strict ASCII byte order 0x21..=0x7E):
!-.0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz~

Written in 100% safe Rust with zero third-party dependencies (~1.8 GiB/s encode, ~2.0 GiB/s strict canonical decode), accompanied by the b67 CLI tool, formal specification (SPEC.md), and zero-dependency linear-time reference implementations in Python 3 and JavaScript ES Modules.

---

Why 67? (Triple Mathematical Convergence)

Every classical binary-to-text scheme—Base16, Base32, Base58, Base62, Base64, Base85, Base91—uses a composite radix and trades off escape-safety, sort order, speed, or native algebraic integrity. 67 is the unique point where ASCII syntax constraints, Diophantine bit-packing, and finite-field algebra converge simultaneously:

1. Syntax Uniqueness (The Exact 67 Zero-Escape ASCII Characters)

Out of all 94 printable non-space ASCII characters (0x21..=0x7E), requiring a character to survive unchanged and unescaped across all 7 universal transport contexts leaves strictly 67 characters (RFC 3986's 66 unreserved characters plus ! 0x21):

1. Cross-OS filenames — valid on Linux (ext4/xfs), macOS (APFS), and Windows (NTFS) (excludes < > : " / \ | ? *);
2. String & template literals — zero escaping in JSON, C, Rust, Go, Python, SQL, and JS '...', "...", `...${}` (excludes \ " ' $`);
3. HTML / XML / SVG — zero entity escaping in text nodes or attributes (excludes & < > " ');
4. Raw URL query & fragment — safe in ?k=<v>&k2=v2#hash without key splitting or + -> space corruption (excludes & = + # % / ?);
5. Tabular & HTTP header lists — never splits CSV columns or ;-delimited headers/cookies (excludes , ;);
6. ECMAScript encodeURIComponent fixed point — encodeURIComponent(s) === s (excludes @ ^ [ ] { } |);
7. Markdown & parenthesized auto-linkers — never breaks [label](https://.../token) (excludes ( ) [ ] { }).

Ordering these 67 symbols by strictly ascending ASCII byte value preserves binary sort order (memcmp(encode(a), encode(b)) == memcmp(a, b)) for all equal-length keys (UUIDv7, ULID, big-endian timestamps, SHA-256 digests).

2. Hardware Register Resonance ($67^{16} \approx 2^{97}$) & Closed-Form Lengths

Because the continued fraction of $\log_2(67) \approx 6.066089$ is $[6;, 15, 7, 1, \dots]$, any fixed block smaller than 16 characters (such as naive 3 bytes -> 4 chars) yields zero density improvement over Base64 ($6.0\text{ bits/char}$). Resonance occurs at 97 bits $\leftrightarrow$ 16 characters:

• 99.941% Shannon Efficiency — packs $6.0625\text{ bits/char}$, cutting expansion from Base64's $+33.333%$ down to $+31.959%$ (saving 14,416 chars per MiB) with zero = padding characters.
• u128 $\leftrightarrow$ 128-bit SIMD Alignment — 97 bits fit natively inside a single CPU u128 register; 16 output ASCII bytes fill one 128-bit SIMD register; radix splitting cascades cleanly via $67^8 < 2^{49}$ (u64) $\to 67^4 < 2^{25}$ (u32) $\to 67^2 = 4489$ (8.77 KB L1d-resident pair table).
• 97-Byte $\leftrightarrow$ 128-Char Superblocks — 8 quanta equal 97 bytes $\leftrightarrow$ 128 chars (two 64B cache lines). Since $97 = 12 \times 8 + 1$, quantum $k$ starts at 12k bytes + k bits, extracting via a single unaligned u128 load.
• Division-Free Exact Length Identities — for every $N, M \ge 0$: $$M = \left\lceil \frac{128 N}{97} \right\rceil, \qquad N = \left\lfloor \frac{97 M}{128} \right\rfloor = (97 M) \gg 7, \qquad \text{Valid}(M) \iff ((97 M) \mathbin{&} 127) < 97$$
• Strict Canonical Bijection — full quanta enforce $v < 2^{97}$ and $r$-bit tails enforce $v_{\text{tail}} < 2^r$, eliminating Base64/Base58-style non-canonical malleability.

3. Native $\mathrm{GF}(67)$ Check Digits & Self-Healing ECC

67 is the smallest prime $> 64$ (and the 8th Heegner number), with $g = 2$ as its smallest primitive root. Base67 provides two optional algebraic integrity modes in the exact same alphabet without cryptographic hash overhead:

• Base67c (+1 char, MOD 67-2) — the prime-field successor to ISO/IEC 7064 MOD 11-2 and MOD 37-2. Detects 100% of single-character typos, 100% of adjacent and jump transpositions (distance $< 66$), and leading '!' insertions/deletions.
• Base67rs (+2 chars, $\mathrm{GF}(67)$ Reed–Solomon $\mathrm{RS}(n, n-2)$) — for payloads $\le 47$ bytes (UUIDs, ULIDs, SHA-256, Ed25519 public keys, API tokens), automatically locates and repairs any single-character typo (including out-of-alphabet erasures), or rejects 100% of 1- and 2-character corruptions in strict mode.

---

Comparison

Property	Base64 (RFC 4648)	Base64url	Base58 / Base62	Base85 (Ascii85)	Base67
Radix algebra	$64 = 2^6$ (composite)	$64 = 2^6$	$58 / 62$ (composite)	$85 = 5 \cdot 17$	$67$ (Prime field $\mathbb{F}_{67}$)
Bits / char	$6.0000$	$6.0000$	$5.858 / 5.954$	$6.4000$	$6.0625$ (99.941% Shannon)
Size overhead	$+33.33%$ (+ =)	$+33.33%$	$+36.57% / +34.36%$	$+25.00%$	$+31.96%$ (no padding)
Complexity	$O(N)$	$O(N)$	$O(N^2)$ BigInt	$O(N)$	$O(N)$ streaming (~2 GiB/s)
encodeURIComponent safe	No (+ / =)	Yes (unpadded)	Yes	No	Yes (100% invariant)
JSON / HTML / FS safe	No (/)	Yes	Yes	No (" ' \ < > & * :)	Yes (all 7 syntax axioms)
memcmp sort-preserving	No	No	No / Yes	Yes	Yes (strict ASCII order)
Native same-alphabet ECC	None	None	Double SHA-256 (+4B)	None	Base67c (+1c) & Base67rs (+2c)

---

Quickstart & CLI (b67)

cargo build --release

# 1. Standard Base67 encode / decode
./target/release/b67 -s "Hello, Base67!"
# -> FAwuTq5etxpQ2-hT06d

./target/release/b67 -d -s "FAwuTq5etxpQ2-hT06d"
# -> Hello, Base67!

# 2. Base67c (+1 char GF(67) MOD 67-2 check digit)
./target/release/b67 -c -s "Hello, Base67!"
# -> FAwuTq5etxpQ2-hT06d8

# 3. Base67rs (+2 chars GF(67) Reed-Solomon self-healing)
./target/release/b67 -e -s "Hello, Base67!"
# -> FAwuTq5etxpQ2-hT06d35

# Deliberately corrupt 'F' -> 'Z' at index 0; b67 heals it automatically:
./target/release/b67 -d -e -s "ZAwuTq5etxpQ2-hT06d35"
# stderr: b67: self-healed single-char typo at index 0: 'Z' -> 'F'
# stdout: Hello, Base67!

# 4. Run throughput benchmark & spec card
./target/release/b67 --info
./target/release/b67 --bench

---

Rust Library Usage

use base67::{
    encode, decode,
    encode_check, decode_check,
    encode_ecc, decode_ecc_heal,
    StreamEncoder, StreamDecoder,
};

// Standard canonical Base67
let s = encode(b"Hello, Base67!");
assert_eq!(s, "FAwuTq5etxpQ2-hT06d");
assert_eq!(decode(&s).unwrap(), b"Hello, Base67!");

// Base67c: +1 char MOD 67-2 check digit
let checked = encode_check(b"api_key_payload");
assert_eq!(decode_check(&checked).unwrap(), b"api_key_payload");

// Base67rs: +2 chars GF(67) Reed-Solomon single-typo self-healing (<= 47 bytes)
let token = encode_ecc(&[0xAB; 32]).unwrap();
let mut corrupted = token.into_bytes();
corrupted[10] = b'?'; // even out-of-alphabet erasures are healed
let (recovered, report) = decode_ecc_heal(&corrupted).unwrap();
assert_eq!(recovered, vec![0xAB; 32]);
assert!(report.is_some());

// Constant-memory O(1) streaming
let mut se = StreamEncoder::new();
let mut streamed = String::new();
se.update(b"Hello, ", &mut streamed);
se.update(b"Base67!", &mut streamed);
se.finish(&mut streamed);
assert_eq!(streamed, s);

---

Benchmark

Measured on 1 MiB pseudo-random buffers (cargo run --release -- --bench, safe Rust, zero unsafe, single thread):

Payload size   :    1048576 bytes
Base64 size    :    1398104 chars (+33.334% overhead)
Base67 size    :    1383688 chars (+31.959% overhead, saves 14416 chars / MiB)
Base67 encode  :     1791.8 MiB/s
Base67 decode  :     2028.5 MiB/s (with strict canonicality & length verification)

Uses an exact 128-bit Barrett reciprocal (ceil(2^145 / 67^8), proven exact across all $2^{97}$ quantum states) to eliminate software __udivti3 calls, paired with an L1-cached 4489-entry two-character lookup table and branchless 128-char superblock validation.

---

Repository Layout & Cross-Language Verification

.
├── SPEC.md                    # Formal Base67 v1.0 specification & mathematical proofs
├── Cargo.toml                 # Zero-dependency Rust crate & CLI manifest
├── src/
│   ├── lib.rs                 # Core library (Base67 / Stream / Base67c / Base67rs)
│   └── main.rs                # `b67` CLI utility & benchmark runner
├── tests/
│   └── vectors_and_props.rs   # Exhaustive roundtrip, streaming, canonicality, order & ECC tests
├── ref/
│   ├── base67.py              # Zero-dependency O(N) Python 3 reference implementation
│   └── base67.mjs             # Zero-dependency O(N) JavaScript ES Module reference implementation
└── test-vectors.json          # Cross-language canonical & non-canonical rejection test vectors

Verify all three implementations against test-vectors.json:

cargo test
python3 ref/base67.py
node ref/base67.mjs

---

License

MIT