Hacker News Reader

Comment by Confiks | Hacker News Reader

Note that this encoding isn't of the same efficiency as QR binary mode, as it converts 3 bytes into 2 base45 characters. So it's more like 'base41 using the base45' charset.

I'm still a bit sad that with this standard and the packages available now, the namespace of 'base45' is clobbered with this suboptimal implementation. It can best just be renamed to 'base41'. It's a good tradeoff for the DCC, but not for the rest of possible implementations.

For the Dutch variant of the green pass using unlinkable signatures [1], we need all the space we can get, so we use a base45 encoding that uses the exact same method as base58 [2][3], and which has the exact same efficiency as QR binary mode.

[1] https://github.com/minvws/nl-covid19-coronacheck-app-coordin...

[2] https://gist.github.com/confiks/8fcb480d87a50cf1bb5e40e2f093...

[3] https://github.com/confiks/base45-go/tree/main/base45

View on HN

32 bits raw <==> 33 bits (3 pairs of 11 bits) QR alphanum.

In blocks of 4 bytes this encodes as 6 'base45' (QR alphanum) characters, and uses the same lookup table.

https://en.wikipedia.org/wiki/QR_code#Encoding

The "Alphanumeric character codes" table, at least at a visual glance, is identical to the RFC's lookup table.

The GP is saying that the equal efficiency is possible with using only 41 out of 45 characters, so reducing the symbol set would make base45 (now base41) more useful as a general encoding, not just an encoding for QR codes.

That's a fair point that wasn't made clearly enough. I have two questions though:

1) Is it worth no longer sharing the same lookup table? My supposition is that this wouldn't practically matter in the modern bloated environment anyway, but it's still annoying and might be a source of additional bugs.

2) Which 4 characters would be skipped for what reason?

I'd initially propose not including: non-printing character space (b45[36]), possible variable wildcard dollar-sign (also a currency symbol that might get translated) (b45[37]), html escape and database wildcard percent (b45[38]), then typical wildcard asterisk (star) (b45[39]). Thus the sequence string would be.

b41 = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ+-./:";

One could take 10 digits, 26 letters and 5 operands (+ - * / %) for Base41 encoding. 41 * 41 * 41 = 68921 is enough for 2 bytes (65536 combinatons).

/ and % don't play well with URLs. I would take + - * . $ instead.

'+' doesn't play well with URLs

Less so than %, for example. It is classified as a sub-delim subset of reserved characters [1], meaning that they won't conflict with the generic URI components syntax and thus are reasonably safe. (* and $ are also included in this set.) You might be worrying that it gets "converted" into %2B but this conversion is not required and fully reversible.

[1] https://datatracker.ietf.org/doc/html/rfc3986#section-2.2

Reply on news.ycombinator.com