Base84 deserves a place in file names

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

Yeah I definitely don't want any of those last ~22 characters in file names if I need to do anything with them from a shell

Base62 (or 64, with -_) is totally sufficient.

> That leaves enough room for a group to hold 32 bits about 95% of the time on uniformly random input, and 31 bits otherwise.

> The encoder looks at the next 31 bits. If their value is below 84⁵ - 2³¹, there’s room for a 32nd bit. Otherwise, it consumes just those 31 bits. Either way, the value fits in five base-84 digits.

Seems pretty awkward.

I understand for the authors particular application the probability of collision is small, but this makes this encoding completely impractical for filenames generally.

Most projects or directories probably don't contain filenames that are sensitive. If you do have sensitive filenames, storing the true filenames in an encrypted manifest will work fine if you don't have a huge number of files.

For the use case where you have a lot of data, the data needs to be encrypted, and the filenames are sensitive you'd surely be better off using something like dm-crypt (if you can use a block device) or a FUSE solution like gocryptfs.

Base16 is verbose, but each symbol in the alphabet carries exactly 4 bits (hence why a single byte in hex is two symbols). This is nice for encoding bytes. Base64 requires two non-alphanumeric symbols such as + and / or - and _ because A-Za-z0-9 only provides 62 characters. Each output symbol encodes exactly 6 bits of the original input. But when we're encoding whole bytes we sometimes need to use padding (when the input is not a multiple of 3 bytes and that ambiguity is harmful in the context that decoding occurs in). Then there's Base32, which is what currently seems like a sweet spot to me and is what I'm considering using for identifiers in my own systems. It only requires 32 characters, so can easily take a range of A-Z0-9 or a-z0-9 excluding visually-similar characters. Like Base64 it can also require padding in some settings.

I quite like the general scheme used in the Bech32 and Bech32m framing idea, which allows for a human-readable prefix before a `1` and then the base32 data follows. This can be done because `1` is excluded from the Bech32 alphabet. This prefix can be used to differentiate between kinds of identifier, for example:

https://github.com/bitcoin/bips/blob/master/bip-0350.mediawi...

But to address the article directly, I'm not sure the complexity is worth the gains in the table in https://github.com/jedisct1/zig-base84#encoding, which states that we save ~6.5% of characters, and for 128 input bytes, the resulting Base64 string is 171 characters, while the Base84 string is 161-166 characters.

I also dislike that the chosen alphabet breaks text selection; GitHub very carefully picked their current token formats so that the whole token is selected with a double-click:

> One other neat thing about _ is it will reliably select the whole token when you double click on it. Other characters we considered are sometimes included in application word separators and thus will stop highlighting at that character. Try out double clicking this-random-text versus this_random_text!

https://github.blog/engineering/platform-security/behind-git...

For example, compare double-clicking on the article's Base84 alphabet:

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

with the Bech32 Base32 alphabet:

> qpzry9x8gf2tvdw0s3jn54khce6mua7l

Regardless though we still have the fundamental issue that bytes encoded as Base16, Base32, Base64, or even Base91/Base84 will be _longer_ when encoded. Base32 can encode up to 159 bytes before hitting a filename limit of 255 bytes. I can't remember whether filenames are 16-bit on Windows (UCS-2? UTF-16?), but I speculate on average that maybe you could save a lot of bytes by first ensuring that filenames are UTF-8 before encrypting them, since filenames on a lot of computeres, especially ones running in the west, likely contain a lot of latin characters. You could even switch between encodings to get the best bit-packing in filenames.

At the moment it looks like turbocrypt forbids encrypted filenames that are too long: https://github.com/jedisct1/turbocrypt/blob/4905241d271e84a0...

I think turbocrypt could switch to using a surrogate file when an encrypted filename exceeds 255 bytes to allow for encrypting any filename permitted by the filesystem, while still preserving the property that the same filename in a different directory has the same encrypted filename. If an encrypted filename is too long to fit on the filesystem, maybe its hash could be stored as the filename instead (which is extremely unlikely to collide). Then we could store the full encrypted filename in a `.name` file in the same directory. We could do similar for directory names that are too long. We could then use a less dense but bit-aligned encoding scheme like Base32 with an all-lowercase alphabet without any punctuation to make filename text selection straightfoward. We would avoid all case sensitivity traps that can occur with things like Base64 and Base84. Let's pick two filename prefixes, say "tcf1" for "turbocrypt filename" and "tch1" for "turbocrypt filename hash". Then we could have a directory layout like this:

  tch1q9x8gf2tvdw0 # a file whose encrypted filename exceeds 255 bytes; this filename is a hash of the encrypted filename, e.g. SHA-256.
  tch1q9x8gf2tvdw0.name # a file whose contents are the full encrypted filename of tch1q9x8gf2tvdw0.
  tcf1tvdhc6mua7l9x8s3qprz # a file whose encrypted filename does not exceed 255 bytes.

Once a system to support long filenames is implemented, the size of the alphabet used for encoding the filenames (like Base84) becomes less important; Base16, Base32, Base64, or another bit-aligned encoding scheme could be used.

As a very small added bonus, you could even implement a bit-aligned codec such as base16 or base64 using SIMD via a bunch of swizzling, shifting, bitmasking, and AND/XORing, making it very fast should the need arise.