Live data from Hacker News

10 > 64, in QR Codes

huonw.github.io

71–80 of 83 posts

Re: 10 > 64, in QR Codes

#71
post #46

Earlier quoted context omitted.

Speaking of visualization...that last figure in this post is super interesting in part because you can actually see some of the redundancy in the base64 encoding on the left, in the patterns of vertical lines. In general, better compression means output that looks more like "randomness"—any redundancy implies there was room for more compression—and that figure makes this quite clear visually!

That’s undoubtedly some redundancy in the underlying data, not in the encoding itself.

Yes, the data is the bytes 00, 01, …, FF repeating, and that pattern is highly visible with a power-of-2 encodings, but not visible with other bases (for similar reasons that 0.1 as a (binary) float doesn’t behave as people expect).

Re: 10 > 64, in QR Codes

#72
post #69
post #48

Earlier quoted context omitted.

Yeah, I had had the same question! One of my earlier articles experiments with this: https://huonw.github.io/blog/2021/09/qr-error-correction/ Figure 8 and its surrounding section are the undamaged case.

That was a nice read. > I also tested only one background image, so the behaviour may differ greatly with QR codes contained in different surrounds. This likely does not matter much. It could theoretically affect binarization near the edges of the code (near module boundaries, depending on how you did the resizing), but in practice as long as the code itself is high-contrast, this is unlikely. The more usual issue is…

Thanks for the kind words and the insight!

Re: 10 > 64, in QR Codes

#73
post #62
post #24

Earlier quoted context omitted.

Fixed, thanks! Yes, longevity is an issue with anything online. On the other hand, in this case recovery is not a huge issue for anybody technical enough.

I was thinking at first it would be better if it takes the entire webpage as a datauri instead of the raw html like this basic business card template: data:text/html;base64,PCFET0NUWVBFIGh0bWw+DQo8aHRtbCBsYW5nPSJlbiI+DQogIDxoZWFkPg0KICAgIDxtZXRhIGNoYXJzZXQ9IlVURi04IiAvPg0KICAgIDxtZXRhIG5hbWU9InZpZXdwb3J0IiBjb250ZW50PSJ3aWR0aD1kZXZpY2Utd2lkdGgsIGluaXRpYWwtc2NhbGU9MS4wIiAvPg0KICAgIDx0aXRsZT5GbGV4IENhcmQ8L3RpdGxlPg0KICA…

There's no need to base64 encode HTML, since it's already plaintext. You can just omit the encoding declaration in the data URL and include the raw HTML, e.g. 'data:text/html,Hello, world!'. That should save a bit of overhead.

Re: 10 > 64, in QR Codes

#74
post #72
post #69

Earlier quoted context omitted.

That was a nice read. > I also tested only one background image, so the behaviour may differ greatly with QR codes contained in different surrounds. This likely does not matter much. It could theoretically affect binarization near the edges of the code (near module boundaries, depending on how you did the resizing), but in practice as long as the code itself is high-contrast, this is unlikely. The more usual issue is…

Thanks for the kind words and the insight!

A slightly more common way to express "field of view" is "module pitch", measured in pixels between adjacent module centers. I went back and tried to express the numbers from Figured 6 as a module pitch, and I think it works out to around 1.6 pixels / module. IIRC, the QR code standard recommends a module pitch of at least 4 pixels. So it is nice that ZBar is able to do around 2.5x better before running into issues (a margin that is a lot bigger than the gains from higher EC levels).

In theory there could still be room for improvement. Right now ZBar estimates finder and alignment pattern locations to quarter-pel precision, but rounds each module location to the nearest pixel so it can sample a binarized version of the image to decide the value of that module. At the extreme limits of small module pitch this effectively turns the resampling filter in whatever you are using to resize your QR code image into a nearest neighbor filter. You can see why that would start to cause issues. Imagine a version 7 code (45x45 modules) sized to be 80x80 pixels. Most of your columns will be 2 pixels wide, but with binarization, somewhere in there you have to have 10 columns that are only 1 pixel wide. Good luck lining up your grid to hit all of them perfectly (without looking at the timing pattern, which would likely only help in the perfectly axis-aligned case). Some kind of sub-pixel integration of the original image before thresholding to decide each module value could probably do better. That would make decoding a lot more computationally expensive, though.

Re: 10 > 64, in QR Codes

#75
I built an open source tool to specifically work on this problem: https://convert.zamicol.com

We know only two open source JS projects that even support alphanumeric, Nayuki and Paul’s. https://github.com/Cyphrme/QRGenJS. We have it hosted here: https://cyphr.me/qrgen

I’ve also done a lot of work on this problem: https://image-ppubs.uspto.gov/dirsearch-public/print/downloa...

Also, regarding alphanumeric, RFC 3986 states that:

> An implementation should accept uppercase letters as equivalent to lowercase in scheme names (e.g., allow “HTTP” as well as “http”)

Re: 10 > 64, in QR Codes

#76

I need to re-run the math based on this info, but a while back, I wanted to figure out the maximum density of QR codes that could be reliably printed on a sheet of plain paper with a laser printer, then optically scanned and re-digitized. I recall the answer was about the same as a double-density 5.25" floppy disk, which is 320kb.

https://i.imgur.com/cAVbqka.png

Of course, pure binary (byte) encoding is best, but many systems have the constraint of text characters or non-control characters. With that constraint, alphanumeric encoding is best.

https://zamicol.com/assets/11580064.pdf

Re: 10 > 64, in QR Codes

#77
post #54
post #49

Earlier quoted context omitted.

Ah, it is a good point that it might be worth comparing to, but it is far worse. Abstractly, it requires approximately log(45)/log(16) output bits per input bit, an overhead of 37%. Making this more concrete: each input byte is encoded as two hex digits, and two hex digits have to be encoded as two Alphanumeric characters. It thus takes 11 bits in the QR code bit stream to store 8 bits of input.

(I've added an analysis of this and other bases to the article: https://huonw.github.io/blog/2024/03/qr-base10-base64/#fn:ot... )

RFC 3986 says that * is a sub-delim. It cannot be assumed to be URI safe.

A base 38 alphabet is the maximal possible URI unreserved alphabet.

Re: 10 > 64, in QR Codes

#78
post #13

I'm not that familiar with QR codes. Anyone know how base16/hexadecimal encoding with 0-9A-F fares in comparison? It seems like an obvious encoding to test, especially for simplicity of implementation compared to base64 and base10, and an odd one to miss for comparison?

Hex is worse, see here [1] for UUIDs [1] https://news.ycombinator.com/item?id=39094251

I'm not confident of the math there.

https://i.imgur.com/cAVbqka.png

Because of quirks, in edge cases decimal is more efficient, but overall alphanumeric is better in QR code.

Re: 10 > 64, in QR Codes

#79

We have a similar problem at work right now, but due to different constraints we've settled on Base85. Slightly denser than Base64, but still just plain old printable ASCII characters and the following characters are still "free" so one can use them as field delimiters in a CSV-style format: "',/[]\ Incidentally, this also makes them JSON-Safe. Base94 uses all printable characters, and Base122 uses both printable cha…

I'm not following as Base85 isn't JSON safe. For example, { and } carry meaning in JSON.

Re: 10 > 64, in QR Codes

#80

Or... Don't encode data in the URL at all. If your data isn't secret or per-user, have it go to https://yoursite.com/gh . If it is security sensitive, go to https://yoursite.com/Qhm4Qr55mS 2 alphanumerics (=4000 links) is plenty to encode a link to all the major pages of your website/service you may want to advertise. 10 alphanumerics (=10^18) is plenty that even if every person in the world had a QR code, nobody cou…

Or just go directly to 2^256 and have enough links for every atom in the observable universe.

More importantly, it's enough links that at the Landauer limit a collision can't happen without consuming ~300,000 solar systems of energy, vastly beyond human technological ability. With this property, each link can also be considered private.

Post reply on HN