9 ms·

Why are QR Codes with capital letters smaller than QR codes with lower case?

319 points by todsacerdoti 2y ago

parsimo2010 2y ago
tl;dr: Upper case letters can be represented in "alphanumeric" mode, which uses 11 bits per two characters (5.5 bits per character, but padded if the length is uneven). Lower case letters are not included in alphanumeric mode, so the QR code has to be represented in byte mode, which uses 8 bits per character.
thequux 2y ago
One of the things that Data Matrix got right was being able to shift between encoding regimes mid-stream. Many character sets can be represented in radix-40 (so three characters per two bytes), and the occasional capital character can be handled by a shift byte. If you have a long string of digits, they can be encoded in 4 bits/char. You can even put raw binary in there if need be
- nayuki 2y ago
  A QR Code consists of a sequence of segments. Each segment has a mode - numeric, alphanumeric, kanji, or byte. It is possible to shift between encoding regimes by ending a segment and beginning a new segment with a different mode. https://www.nayuki.io/page/optimal-text-segmentation-for-qr-codes https://www.nayuki.io/page/optimal-text-segmentation-for-qr-... Some 1D barcodes have inline shift symbols like you said for Data Matrix, though. e.g. https://en.wikipedia.org/wiki/Code_128 https://en.wikipedia.org/wiki/Code_128
  - Zamicol 2y ago
    I was going to reply to point that out. I'm not surprised you're the one to point it out first!
- silotis 2y ago
  I seems to me best approach would be to compress the contents with a Huffman code or some other entropy encoding. All this business of restricted character sets is just an ad-hoc way of reducing the size of each symbol and we've got much more mature solutions for that.
  - account42 2y ago
    For entropy codes to be effective for such short strings you need a shared initial probability table. And if you have that you are effectively back at special encoding modes for each character set.
lifthrasiir 2y ago
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.
cypherpunks01 2y ago
My favorite QR code visual explainer: https://qr.blinry.org/ https://qr.blinry.org/
- SirFatty 2y ago
  Thank you for that! A lot is over my head, but very interesting none-the-less.
- tantalor 2y ago
  Not very useful, as it doesn't support alphanumeric mode. > For our code, encoding mode is Alphanumeric (2), but we haven't implemented how to read that yet. Sorry! Try another QR code!
smashed 2y ago
> Byte mode uses (you guessed it!) 8 bits per single character. 8 bits is enough to represent the entire ascii char table, there must be some other limitation going on. QR code control chars maybe? The linked "byte mode" table only has 45 individual chars. This could be represented with 6 bits with room to spare..
- wvbdmp 2y ago
  Apparently you can specify the text encoding in a thing called “ECI”, but support varies and most readers just guess the encoding by the bytes. I imagine these days most are UTF8 https://stackoverflow.com/questions/9699657/is-utf-8-the-encoding-of-choice-for-qr-codes-with-non-ascii-chars-by-now https://stackoverflow.com/questions/9699657/is-utf-8-the-enc...
- duskwuff 2y ago
  > 8 bits is enough to represent the entire ascii char table, there must be some other limitation going on. QR code control chars maybe? The specified capacity of "25 characters" for QR code size is 25 characters in alphanumeric mode, not in byte mode. > The linked "byte mode" table only has 45 individual chars. This could be represented with 6 bits with room to spare.. Even better than that - it's 5.5 bits per character! Each pair of characters is represented as a single 11-bit code unit. (This works because 45 x 45 = 2025, which is just barely under 2^11 = 2048.) There's apparently some support in the QR standard for mixed-encoding codes, but few encoders seem to use that.
- gpvos 2y ago
  > The linked "byte mode" table only has 45 individual chars. No, that link is for alphanumeric mode, which uses 5.5 bits per character (45 * 45 = 2025 <= 2048, so it fits in 11 bits).
recursive 2y ago
All this bitwise optimization, but most of the QR codes I see in the wild have >100 bytes of useless cruft like https://engagement.bigcompany.com/campaigns/1485-0123/landing-page?region=northwest&start-date=1999-12-31&end-date=9999-99-99&correspondence-id=887766&funnel-selector=foobar https://engagement.bigcompany.com/campaigns/1485-0123/landin...
- nomel 2y ago
  It's not useless, it just makes the tracking data (which it almost always is) easier to implement.
  - recursive 2y ago
    Also makes it harder to actually use because the requirements for camera focus get cranked way up.
  - fragmede 2y ago
    thanks for wasting my time! :) (nomel's profile)
    - giancarlostoro 2y ago
      Would be neat to have that as a game, and you get a timer that tells you how long you took.
- emmelaich 2y ago
  Another example, Victoria Australia COVID tracking QR code. https://nick.zoic.org/art/qr-codes-advice/#no-funny-business https://nick.zoic.org/art/qr-codes-advice/#no-funny-business
  - thih9 2y ago
    It works though. Perhaps it would have been easier to use when optimized, but it’s a nontrivial effort - especially if the original requirements were bloated. To me it’s no different than misusing heavy JS frameworks or an electron app.
tantalor 2y ago
This site is the best visual explainer for QR code generation. https://www.nayuki.io/page/creating-a-qr-code-step-by-step https://www.nayuki.io/page/creating-a-qr-code-step-by-step It reproduces what the article is saying, with more detail.
- rkagerer 2y ago
  Thanks, this looks like an awesome tool. I wish more web explainers took this "explain your work" approach. It's great that it uses the content you put in to illustrate the step-by-step breakdown.
jwr 2y ago
Is it safe to uppercase the protocol part of the URL? I decided to use segments and stick to lowercase "https", because I didn't trust various implementations out there to handle "HTTPS" correctly. Should I?
- lifthrasiir 2y ago
  In which case, you can still uppercase the domain to get a partial size reduction as QR code does allow for switching to other encoding modes in stream.
  - toast0 2y ago
    If you control the destination server, you can also upper case the path. In the old days, Yahoo's build of Apache (yApache) included an option to automatically lower case urls before matching them. Super handy because lots of urls were coming in from print publications and you could never get publications to show urls properly, nor get users to type them in properly.
- tln 2y ago
  How many implementations do you care about? All major phones do very well at QR scanning these days including uppercase URLs. Leaving a naked domain name like "www.example.com/1234" was not quite as good, but at least iPhones, Pixels and Samsungs worked well IIRC. I used this trick to allow printing of QR codes at smaller resolutions for 4+ years, and phones have gotten noticeably better in that span at handling QR codes printed at smaller sizes, with uppercase, nonstandard shapes, borders, you name it. If you make https: lowercase and the rest uppercase, with QR encoding that does smart segmentation, I'm pretty sure you can still get most of the benefit... but, exercise for the reader. The smallest v1 QR code is 21 modules. That can fit 20 uppercase letters. The 25 module size, is not that much bigger and can get 38 uppercase or 26 lowercase letters.
  - dgl 2y ago
    Strangely not including the scheme doesn't seem to consistently work on an iPhone when in uppercase, a string like "FOO.COM/BAR" does open as a URL, but a string like "FOO.UK/BAR" does a search. I think it's best to include the full HTTPS:// prefix (and I don't think it being uppercase really matters, I'd be surprised if that breaks anything).
waltbosz 2y ago
This reminds me of a silly nerd lie I like to tell non-technical people: "Did you know that capital letters take up 4 more bits of storage than lowercase letters?"
em3rgent0rdr 2y ago
When QR codes first came out I thought it was really cool. But then re-entering meatspace after the pandemic I was honestly saddened to see so many in-person venues start using QR codes. QR codes are machine-readable, but they sure aren't human-readable, but why can't we have both? For instance, plain text using a low-pixel font with a dotted line underneath for error-correction and alignment.
- bitwize 2y ago
  Or maybe OCR-A? https://en.m.wikipedia.org/wiki/OCR-A https://en.m.wikipedia.org/wiki/OCR-A
- lynnharry 2y ago
  That's basically converting a QR scanner into a text detector. It might work but why do they need to be human-readable? Most part of the encoded string would be UUID that's useless for human eyes anyway. After scanning, the important info will also usually show on the phone screen.
  - em3rgent0rdr 2y ago
    I want it human readable so I'm not presented with QR codes when I'm in meatspace. I'd rather see a pixel-font that say MENU://JOES-CHICKEN when I want to look up the menu at my local chicken restaurant than look at a QR.
    - em3rgent0rdr 2y ago
      If part of the data is just a random number like a UUID that is meaningless to a human, well that number could simply be placed after the pixel-font text or as a rectangle outline...if using a 3x5 pixel font then that gives 4x5=20 bits per character cell, so a 128-bit UUID with 12 bits of overhead could fit within the space of 7 characters...fine...but at least put the parts of the info that the human can relate to (like that this a MENU for RESTAURANT) as pixel text so both the human and machine are happy.
- nayuki 2y ago
kentbrew 2y ago
Here's a guy making a QR code by hand on a Go board, just the way the inventors did: https://www.youtube.com/watch?v=w5ebcowAJD8 https://www.youtube.com/watch?v=w5ebcowAJD8
- BrandoElFollito 2y ago
  A good channel overall. Some things are better, some other worse but for instance, his explanation of the Bayes theorem is on par with the one from 3blue1brown
- speps 2y ago
  “a guy” aka Veritasium, the channel with 17M subs
  - sejje 2y ago
    What are you saying? He's so popular he cannot be referenced with a simple pronoun?
  - kentbrew 2y ago
    Sorry, meant no disrespect. I am assuming he's a guy; apologies if I'm wrong. :)
- indrora 2y ago
  I'm reminded of part of (my family) history where I discovered that my grandfather had worked on the UPC system. The original "test blanks" for UPCs were steel plates with machined cuts in them, photoreduced down to small sizes for testing.
franciscop 2y ago
Another level of "Why": QR codes were invented in 1994 in Japan for automated scanning. As you all probably know, Japanese uses Kanji, and hiragana+katakana; it does not rely on the Latin alphabet. However, Japanese speakers are familiar with it and occasionally use it for specific purposes. While katakana is commonly used for transliterating foreign words, sometimes the exact original spelling is preserved for stylistic reasons, especially in acronyms or single-word cases. However, in such cases, they usually use only capital letters. In Japanese, there's no distinction between lowercase and uppercase letters. So for them this distinction is, if you allow some leeway, similar to the differences between normal, italic, or bold letters in English. So it makes sense with this context, if you are making a "group of letters and numbers", to default to uppercase + numbers as the normal/shorter version.

319 points by todsacerdoti 2y ago

parsimo2010 2y ago

tl;dr: Upper case letters can be represented in "alphanumeric" mode, which uses 11 bits per two characters (5.5 bits per character, but padded if the length is uneven). Lower case letters are not included in alphanumeric mode, so the QR code has to be represented in byte mode, which uses 8 bits per character.

thequux 2y ago

One of the things that Data Matrix got right was being able to shift between encoding regimes mid-stream. Many character sets can be represented in radix-40 (so three characters per two bytes), and the occasional capital character can be handled by a shift byte. If you have a long string of digits, they can be encoded in 4 bits/char. You can even put raw binary in there if need be

nayuki 2y ago
A QR Code consists of a sequence of segments. Each segment has a mode - numeric, alphanumeric, kanji, or byte. It is possible to shift between encoding regimes by ending a segment and beginning a new segment with a different mode. https://www.nayuki.io/page/optimal-text-segmentation-for-qr-codes https://www.nayuki.io/page/optimal-text-segmentation-for-qr-... Some 1D barcodes have inline shift symbols like you said for Data Matrix, though. e.g. https://en.wikipedia.org/wiki/Code_128 https://en.wikipedia.org/wiki/Code_128
- Zamicol 2y ago
  I was going to reply to point that out. I'm not surprised you're the one to point it out first!
silotis 2y ago
I seems to me best approach would be to compress the contents with a Huffman code or some other entropy encoding. All this business of restricted character sets is just an ad-hoc way of reducing the size of each symbol and we've got much more mature solutions for that.
- account42 2y ago
  For entropy codes to be effective for such short strings you need a shared initial probability table. And if you have that you are effectively back at special encoding modes for each character set.

lifthrasiir 2y ago

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.

cypherpunks01 2y ago

My favorite QR code visual explainer: https://qr.blinry.org/ https://qr.blinry.org/

SirFatty 2y ago
Thank you for that! A lot is over my head, but very interesting none-the-less.
tantalor 2y ago
Not very useful, as it doesn't support alphanumeric mode. > For our code, encoding mode is Alphanumeric (2), but we haven't implemented how to read that yet. Sorry! Try another QR code!

smashed 2y ago

> Byte mode uses (you guessed it!) 8 bits per single character. 8 bits is enough to represent the entire ascii char table, there must be some other limitation going on. QR code control chars maybe? The linked "byte mode" table only has 45 individual chars. This could be represented with 6 bits with room to spare..

wvbdmp 2y ago
Apparently you can specify the text encoding in a thing called “ECI”, but support varies and most readers just guess the encoding by the bytes. I imagine these days most are UTF8 https://stackoverflow.com/questions/9699657/is-utf-8-the-encoding-of-choice-for-qr-codes-with-non-ascii-chars-by-now https://stackoverflow.com/questions/9699657/is-utf-8-the-enc...
duskwuff 2y ago
> 8 bits is enough to represent the entire ascii char table, there must be some other limitation going on. QR code control chars maybe? The specified capacity of "25 characters" for QR code size is 25 characters in alphanumeric mode, not in byte mode. > The linked "byte mode" table only has 45 individual chars. This could be represented with 6 bits with room to spare.. Even better than that - it's 5.5 bits per character! Each pair of characters is represented as a single 11-bit code unit. (This works because 45 x 45 = 2025, which is just barely under 2^11 = 2048.) There's apparently some support in the QR standard for mixed-encoding codes, but few encoders seem to use that.
gpvos 2y ago
> The linked "byte mode" table only has 45 individual chars. No, that link is for alphanumeric mode, which uses 5.5 bits per character (45 * 45 = 2025 <= 2048, so it fits in 11 bits).

recursive 2y ago

All this bitwise optimization, but most of the QR codes I see in the wild have >100 bytes of useless cruft like https://engagement.bigcompany.com/campaigns/1485-0123/landing-page?region=northwest&start-date=1999-12-31&end-date=9999-99-99&correspondence-id=887766&funnel-selector=foobar https://engagement.bigcompany.com/campaigns/1485-0123/landin...

nomel 2y ago
It's not useless, it just makes the tracking data (which it almost always is) easier to implement.
- recursive 2y ago
  Also makes it harder to actually use because the requirements for camera focus get cranked way up.
- fragmede 2y ago
  thanks for wasting my time! :) (nomel's profile)
  - giancarlostoro 2y ago
    Would be neat to have that as a game, and you get a timer that tells you how long you took.
emmelaich 2y ago
Another example, Victoria Australia COVID tracking QR code. https://nick.zoic.org/art/qr-codes-advice/#no-funny-business https://nick.zoic.org/art/qr-codes-advice/#no-funny-business
- thih9 2y ago
  It works though. Perhaps it would have been easier to use when optimized, but it’s a nontrivial effort - especially if the original requirements were bloated. To me it’s no different than misusing heavy JS frameworks or an electron app.

tantalor 2y ago

This site is the best visual explainer for QR code generation. https://www.nayuki.io/page/creating-a-qr-code-step-by-step https://www.nayuki.io/page/creating-a-qr-code-step-by-step It reproduces what the article is saying, with more detail.

rkagerer 2y ago
Thanks, this looks like an awesome tool. I wish more web explainers took this "explain your work" approach. It's great that it uses the content you put in to illustrate the step-by-step breakdown.

jwr 2y ago

Is it safe to uppercase the protocol part of the URL? I decided to use segments and stick to lowercase "https", because I didn't trust various implementations out there to handle "HTTPS" correctly. Should I?

lifthrasiir 2y ago
In which case, you can still uppercase the domain to get a partial size reduction as QR code does allow for switching to other encoding modes in stream.
- toast0 2y ago
  If you control the destination server, you can also upper case the path. In the old days, Yahoo's build of Apache (yApache) included an option to automatically lower case urls before matching them. Super handy because lots of urls were coming in from print publications and you could never get publications to show urls properly, nor get users to type them in properly.
tln 2y ago
How many implementations do you care about? All major phones do very well at QR scanning these days including uppercase URLs. Leaving a naked domain name like "www.example.com/1234" was not quite as good, but at least iPhones, Pixels and Samsungs worked well IIRC. I used this trick to allow printing of QR codes at smaller resolutions for 4+ years, and phones have gotten noticeably better in that span at handling QR codes printed at smaller sizes, with uppercase, nonstandard shapes, borders, you name it. If you make https: lowercase and the rest uppercase, with QR encoding that does smart segmentation, I'm pretty sure you can still get most of the benefit... but, exercise for the reader. The smallest v1 QR code is 21 modules. That can fit 20 uppercase letters. The 25 module size, is not that much bigger and can get 38 uppercase or 26 lowercase letters.
- dgl 2y ago
  Strangely not including the scheme doesn't seem to consistently work on an iPhone when in uppercase, a string like "FOO.COM/BAR" does open as a URL, but a string like "FOO.UK/BAR" does a search. I think it's best to include the full HTTPS:// prefix (and I don't think it being uppercase really matters, I'd be surprised if that breaks anything).

waltbosz 2y ago

This reminds me of a silly nerd lie I like to tell non-technical people: "Did you know that capital letters take up 4 more bits of storage than lowercase letters?"

em3rgent0rdr 2y ago

When QR codes first came out I thought it was really cool. But then re-entering meatspace after the pandemic I was honestly saddened to see so many in-person venues start using QR codes. QR codes are machine-readable, but they sure aren't human-readable, but why can't we have both? For instance, plain text using a low-pixel font with a dotted line underneath for error-correction and alignment.

bitwize 2y ago
Or maybe OCR-A? https://en.m.wikipedia.org/wiki/OCR-A https://en.m.wikipedia.org/wiki/OCR-A
lynnharry 2y ago
That's basically converting a QR scanner into a text detector. It might work but why do they need to be human-readable? Most part of the encoded string would be UUID that's useless for human eyes anyway. After scanning, the important info will also usually show on the phone screen.
- em3rgent0rdr 2y ago
  I want it human readable so I'm not presented with QR codes when I'm in meatspace. I'd rather see a pixel-font that say MENU://JOES-CHICKEN when I want to look up the menu at my local chicken restaurant than look at a QR.
  - em3rgent0rdr 2y ago
    If part of the data is just a random number like a UUID that is meaningless to a human, well that number could simply be placed after the pixel-font text or as a rectangle outline...if using a 3x5 pixel font then that gives 4x5=20 bits per character cell, so a 128-bit UUID with 12 bits of overhead could fit within the space of 7 characters...fine...but at least put the parts of the info that the human can relate to (like that this a MENU for RESTAURANT) as pixel text so both the human and machine are happy.
nayuki 2y ago

kentbrew 2y ago

Here's a guy making a QR code by hand on a Go board, just the way the inventors did: https://www.youtube.com/watch?v=w5ebcowAJD8 https://www.youtube.com/watch?v=w5ebcowAJD8

BrandoElFollito 2y ago
A good channel overall. Some things are better, some other worse but for instance, his explanation of the Bayes theorem is on par with the one from 3blue1brown
speps 2y ago
“a guy” aka Veritasium, the channel with 17M subs
- sejje 2y ago
  What are you saying? He's so popular he cannot be referenced with a simple pronoun?
- kentbrew 2y ago
  Sorry, meant no disrespect. I am assuming he's a guy; apologies if I'm wrong. :)
indrora 2y ago
I'm reminded of part of (my family) history where I discovered that my grandfather had worked on the UPC system. The original "test blanks" for UPCs were steel plates with machined cuts in them, photoreduced down to small sizes for testing.

franciscop 2y ago

Another level of "Why": QR codes were invented in 1994 in Japan for automated scanning. As you all probably know, Japanese uses Kanji, and hiragana+katakana; it does not rely on the Latin alphabet. However, Japanese speakers are familiar with it and occasionally use it for specific purposes. While katakana is commonly used for transliterating foreign words, sometimes the exact original spelling is preserved for stylistic reasons, especially in acronyms or single-word cases. However, in such cases, they usually use only capital letters. In Japanese, there's no distinction between lowercase and uppercase letters. So for them this distinction is, if you allow some leeway, similar to the differences between normal, italic, or bold letters in English. So it makes sense with this context, if you are making a "group of letters and numbers", to default to uppercase + numbers as the normal/shorter version.