Base84 for Zig

An implementation of the Base84 encoding scheme written in Zig.

It converts binary data to a Base84-encoded string and back.

Every character of the output is valid in a file name on macOS, Linux and Windows.

The output is about 25% larger than the input, against 33% for Base64.

Alphabet

File names have different rules on every operating system.

Windows rejects the characters < > : " / \ | ? *.

It also rejects names that end with a period or a space.

Linux and macOS are less strict, but a name that works on Windows works there too.

The standard alphabet starts from the 94 printable ASCII characters other than space.

It removes the period and the nine characters that Windows rejects:

ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!#$%&'()+,-;=@[]^_`{}~

Base64 in its URL-safe form is also safe for file names, but it only uses 64 characters.

Base91 packs more bits per character, but its alphabet contains most of the characters that Windows rejects.

Base84 sits in between: it uses every character that is safe, and nothing else.

The Base84 function accepts any alphabet of 84 distinct ASCII characters other than NUL.

The standard codec uses the alphabet above.

Encoding

The encoder works like Base91, with groups of five characters instead of fixed blocks.

A group of five characters has 84^5 = 4182119424 values, which is more than the 2147483648 values of 31 bits.

When the next 31 bits of input form a value below 2034635776, the group also holds a 32nd bit. Otherwise, the group only holds these 31 bits.

The first byte of the input goes into the low bits, like in Base91.

The last bits of the input, up to 31 of them, form a tail of one to five characters. The tail has the fewest characters that can hold its bits. A tail of up to seven bits becomes a single character when its value is at most 83.

Base85 encodes four bytes into five characters. Base84 does the same for 95% of the groups, because 84^5 is only 2.6% below 2^32.

On random data such as hashes, keys and identifiers, a character carries 6.389 bits on average. The limit for an alphabet of 84 characters is 6.392 bits.

Base64 carries 6 bits per character. The gain is about 6.5%.

In the worst case, every group only holds 31 bits, and a character carries 6.2 bits.

+-------------+--------------------+----------------+----------------+
| Input bytes | Base64, no padding | Base84 average | Base84 maximum |
+-------------+--------------------+----------------+----------------+
| 16          | 22                 | 20             | 21             |
| 32          | 43                 | 40             | 42             |
| 64          | 86                 | 81             | 83             |
| 128         | 171                | 161            | 166            |
+-------------+--------------------+----------------+----------------+

The average column is the mean output length for random input, rounded to the nearest character.

The calcSizeUpperBound function gives the maximum for a source length.

Usage

const std = @import("std");
const base84 = @import("base84");

pub fn main() !void {
    const codec = base84.standard;
    const message = "Hello, World!";

    var encoded_buf: [codec.calcSizeUpperBound(message.len)]u8 = undefined;
    const encoded = try codec.encode(&encoded_buf, message);
    std.debug.print("{s}\n", .{encoded});

    var decoded_buf: [codec.calcDecodedSizeUpperBound(encoded_buf.len)]u8 = undefined;
    const decoded = try codec.decode(&decoded_buf, encoded);
    std.debug.assert(std.mem.eql(u8, message, decoded));
}

This prints s@Etk'#Qedrxz+hhA.

File name considerations

The alphabet is safe for the filesystems, but a few traps remain.

• macOS and Windows compare file names without regard to case by default. Two different encoded strings can then be the same file name.
• Windows reserves the device names CON, PRN, AUX, NUL, COM1 to COM9 and LPT1 to LPT9, in any case. The standard alphabet never produces them. An output of three characters ends with a letter from A to J, and an output of four characters ends with a capital letter or with a, b or c.
• Many characters of the alphabet have a meaning in shells, and a name can start with -. Quote the names in scripts, and put -- before them on command lines.
• Most filesystems limit a file name to 255 bytes. That is enough for 197 bytes of input.