3 ms·

And that's why you should probably use base45 for binary data in QR codes: https://www.rfc-editor.org/rfc/rfc9285.html https://www.rfc-editor.org/rfc/rfc9285.ht

And that's why you should probably use base45 for binary data in QR codes: https://www.rfc-editor.org/rfc/rfc9285.html https://www.rfc-editor.org/rfc/rfc9285.html

dgl 2y ago
Some discussion happened here about that when it was in draft: https://news.ycombinator.com/item?id=27628178 https://news.ycombinator.com/item?id=27628178 tl;dr: It is sadly not the most efficient encoding (and they missed an opportunity to make it actually base41, which could have been URL safe) -- as defined it only needs 41 characters (as 41^3 > 2^16). The RFC is also not standards track, it's just "Category: Informational". I think a better approach is to understand there are many circumstances where different sets of characters make sense for encoding data. There's no need to write an RFC, instead define a custom alphabet for them, using something like base-x[1]. [1]: https://github.com/cryptocoinjs/base-x https://github.com/cryptocoinjs/base-x
Dylan16807 2y ago
Or just use numbers. Simpler, no weird symbols, more efficient.
- lifthrasiir 2y ago
  If your original data is not a byte sequence then it would indeed work. Otherwise you have to convert it back to bytes yourself, but no small x exists such that 10^x is just barely smaller than 256^y and bignum would be necessary for efficient encoding. Base45 doesn't need bignum and only incurs ~3.2% overhead [1] compared to the pure octet mode (which might be unsuitable for decoder compatibility and other purposes though). [1] 32 original bits = 4 original bytes = 6 base45-encoded letters = 33 bits in the alphanumeric mode, so the overhead is 1 - 33/32 = 0.03125 for 4n bytes of data.
  - josh11b 2y ago
    10^12 < 256^5 ≈ 1.1e+12, which isn't too bad. You could also use 10^118 < 256^49, which wastes less but is in bignum land. But don't you want 10^x to be slightly bigger than 256^y, so you could represent all length-y byte sequences in x-digit number? In this direction, there's 10^53 > 256^22, but that is still in bignum land.
  - Dylan16807 2y ago
    Yeah, use a bignum. QR codes are not very big. And while 3% overhead is fine, encoding decimal digits in groups of 3 is only 0.3% plus a couple bits to round up to the nearest digit.
- Zamicol 2y ago
  The problem with using base10 is that it cannot encode a URL. Alphanumeric is the simplest QR code encoding mode that can encode a URL. Also, when I do the math alphanumeric is the most efficient QR mode, although just barely.
  - Dylan16807 2y ago
    You can switch modes. (Yes that costs a dozen bits if you were otherwise able to stay in the same mode the entire time. Oh well, but I'd say it's worth it to avoid base45.) And base45 is less efficient than looking at the efficiency of raw alphanumeric.
    - Zamicol 2y ago
      > base45 is less efficient Not according to my math: Numeric: 1000/1024 = 98% Alphanum: 2025/2048 = 99% Byte: 191/256 = 75% Kanji: 13/16 = 81%* Alphanumeric is the most efficient QR code encoding mode. (Just to further make this clear, for QR Byte encoding uses ISO/IEC 8859-1, where 65 characters are undefined, so 191/256, which is ~75%. If character encoding isn't an issue, than byte encoding is the most efficient, 256/256, 100%, but that's a very rare edge case. Also, last time I did the math on Kanji it was about 81% efficient. *I have not dug too deep into Kanji and there may be a way to make it more efficient than I'm aware of. I've never considered it useful for my applications so I have not looked.)
      - Dylan16807 2y ago
        > Alphanum: 2025/2048 = 99% That is a semi-correct calculation of the wrong number. Base45 does not use all 45 characters in every slot. It goes 16 bits at a time, so the character storing the upper bits only has 2^16/45^2 = 33 possible values. The most straightforward way to measure efficiency is to see that base45 takes 32 source bits, and encodes them into 33 bits. The way you're calculating, that's only 50% But the better way to calculate efficiency is to take the log of everything (in other words, count how many bits are needed). Numeric is log(1000)/log(1024) which is 99.7%. Alphanum is 99.9%. Base45 is 97%. And I don't know where that kanji number came from. It stores 13 bits at a time, mapping to 8192 shift-JIS code points, and the vast majority of them are valid. It's pretty efficient.

And that's why you should probably use base45 for binary data in QR codes: https://www.rfc-editor.org/rfc/rfc9285.html https://www.rfc-editor.org/rfc/rfc9285.html

dgl 2y ago

Some discussion happened here about that when it was in draft: https://news.ycombinator.com/item?id=27628178 https://news.ycombinator.com/item?id=27628178 tl;dr: It is sadly not the most efficient encoding (and they missed an opportunity to make it actually base41, which could have been URL safe) -- as defined it only needs 41 characters (as 41^3 > 2^16). The RFC is also not standards track, it's just "Category: Informational". I think a better approach is to understand there are many circumstances where different sets of characters make sense for encoding data. There's no need to write an RFC, instead define a custom alphabet for them, using something like base-x[1]. [1]: https://github.com/cryptocoinjs/base-x https://github.com/cryptocoinjs/base-x

Dylan16807 2y ago

Or just use numbers. Simpler, no weird symbols, more efficient.

lifthrasiir 2y ago
If your original data is not a byte sequence then it would indeed work. Otherwise you have to convert it back to bytes yourself, but no small x exists such that 10^x is just barely smaller than 256^y and bignum would be necessary for efficient encoding. Base45 doesn't need bignum and only incurs ~3.2% overhead [1] compared to the pure octet mode (which might be unsuitable for decoder compatibility and other purposes though). [1] 32 original bits = 4 original bytes = 6 base45-encoded letters = 33 bits in the alphanumeric mode, so the overhead is 1 - 33/32 = 0.03125 for 4n bytes of data.
- josh11b 2y ago
  10^12 < 256^5 ≈ 1.1e+12, which isn't too bad. You could also use 10^118 < 256^49, which wastes less but is in bignum land. But don't you want 10^x to be slightly bigger than 256^y, so you could represent all length-y byte sequences in x-digit number? In this direction, there's 10^53 > 256^22, but that is still in bignum land.
- Dylan16807 2y ago
  Yeah, use a bignum. QR codes are not very big. And while 3% overhead is fine, encoding decimal digits in groups of 3 is only 0.3% plus a couple bits to round up to the nearest digit.
Zamicol 2y ago
The problem with using base10 is that it cannot encode a URL. Alphanumeric is the simplest QR code encoding mode that can encode a URL. Also, when I do the math alphanumeric is the most efficient QR mode, although just barely.
- Dylan16807 2y ago
  You can switch modes. (Yes that costs a dozen bits if you were otherwise able to stay in the same mode the entire time. Oh well, but I'd say it's worth it to avoid base45.) And base45 is less efficient than looking at the efficiency of raw alphanumeric.
  - Zamicol 2y ago
    > base45 is less efficient Not according to my math: Numeric: 1000/1024 = 98% Alphanum: 2025/2048 = 99% Byte: 191/256 = 75% Kanji: 13/16 = 81%* Alphanumeric is the most efficient QR code encoding mode. (Just to further make this clear, for QR Byte encoding uses ISO/IEC 8859-1, where 65 characters are undefined, so 191/256, which is ~75%. If character encoding isn't an issue, than byte encoding is the most efficient, 256/256, 100%, but that's a very rare edge case. Also, last time I did the math on Kanji it was about 81% efficient. *I have not dug too deep into Kanji and there may be a way to make it more efficient than I'm aware of. I've never considered it useful for my applications so I have not looked.)
    - Dylan16807 2y ago
      > Alphanum: 2025/2048 = 99% That is a semi-correct calculation of the wrong number. Base45 does not use all 45 characters in every slot. It goes 16 bits at a time, so the character storing the upper bits only has 2^16/45^2 = 33 possible values. The most straightforward way to measure efficiency is to see that base45 takes 32 source bits, and encodes them into 33 bits. The way you're calculating, that's only 50% But the better way to calculate efficiency is to take the log of everything (in other words, count how many bits are needed). Numeric is log(1000)/log(1024) which is 99.7%. Alphanum is 99.9%. Base45 is 97%. And I don't know where that kanji number came from. It stores 13 bits at a time, mapping to 8192 shift-JIS code points, and the vast majority of them are valid. It's pretty efficient.