Creating a QR Code step by step(nayuki.io)
nayuki.io
Creating a QR Code step by step
https://www.nayuki.io/page/creating-a-qr-code-step-by-step
15 comments
The utility of the masking pattern becomes clear when following the next steps, which calculate "penalty points" for dot patterns in the QR code that might occur naturally, but are known to make it harder to read and more prone to erroneous reads. The masking pattern that, when applied to the "clean" content, generates the least problematic output is chosen.
I found this pretty self-explanatory while just following the individual steps. However, a few sentences detailing the higher-level algorithm and its purpose right before the step which first introduces the masking pattern probably wouldn't be a bad idea either.
I found this pretty self-explanatory while just following the individual steps. However, a few sentences detailing the higher-level algorithm and its purpose right before the step which first introduces the masking pattern probably wouldn't be a bad idea either.
Yeah, I once implemented a very simple AR tag mechanism -- using Binary Golay codes [1] which are super simple to understand.
It turns out that you need a mask, otherwise you can too easily get a tag that is entirely (or close to) white or black. I was fortunate with a small code space (only 12 bit) that I could get away with a single mask, it never occurred to me that I could have used multiple masks (at the cost of a the bits to encode the choice)
I looks like extra complexity, but it solves a very pragmatic problem
[1] https://en.wikipedia.org/wiki/Binary_Golay_code
It turns out that you need a mask, otherwise you can too easily get a tag that is entirely (or close to) white or black. I was fortunate with a small code space (only 12 bit) that I could get away with a single mask, it never occurred to me that I could have used multiple masks (at the cost of a the bits to encode the choice)
I looks like extra complexity, but it solves a very pragmatic problem
[1] https://en.wikipedia.org/wiki/Binary_Golay_code
I agree that the why is important, and it reinforces understanding of the how. I share your frustration when I see technical tutorials that show a bunch of screenshots or make you type a bunch of command line actions without explaining what it does and why you should do it.
In this case though, I chose to omit the why because other written resources on QR Codes have covered the topics extensively. Just to name a few: https://en.wikipedia.org/wiki/QR_code ; http://datagenetics.com/blog/november12013/index.html ; https://en.wikipedia.org/wiki/Error_correction_code#Interlea... ; https://en.wikipedia.org/wiki/Clock_recovery
In this case though, I chose to omit the why because other written resources on QR Codes have covered the topics extensively. Just to name a few: https://en.wikipedia.org/wiki/QR_code ; http://datagenetics.com/blog/november12013/index.html ; https://en.wikipedia.org/wiki/Error_correction_code#Interlea... ; https://en.wikipedia.org/wiki/Clock_recovery
I have written a QR encoder in Lua and documented it a bit. Perhaps this goes into the direction?
http://speedata.github.io/luaqrcode/docs/qrencode.html
http://speedata.github.io/luaqrcode/docs/qrencode.html
During quarantine I designed a paper-based system for making QR codes by hand. Everything is very papery and bureaucratic, but also fun. Tables to look up bytes, long forms for calculating Reed-Solomon, and even transparent sheets of paper for comparing different masking patterns.
My goal is to film a video of generating a QR code without any computers or even calculators. It's possible, just might take two hours or so.
My goal is to film a video of generating a QR code without any computers or even calculators. It's possible, just might take two hours or so.
Please post it to HN when it's ready, and let us know at [email protected].
That's awesome. Reminds me of Ken Shirriff computing sha256 with pencil and paper...
http://www.righto.com/2014/09/mining-bitcoin-with-pencil-and...
http://www.righto.com/2014/09/mining-bitcoin-with-pencil-and...
This was the main inspiration! Also, the fact that I couldn't find anyone going through EVERY step of QR code generation manually (even if CPU-assisted) and in detail.
It's a great way to learn. In my cryptography classes we did all of the algorithms by hand (often shortened, so 16 rounds of something would be dropped to 3 or min bytes dropped) on pen and paper as homework. Hard but it really did make a lot stick in my mind about how things worked.
It's also a great way to debug.
I've written video/image codecs and when things go subtly wrong, decoding the raw bitstream by hand and comparing carefully with the decoder output has been the best way to figure out the problem. It can be quite tedious, but as the phrase goes, definitely "builds character".
Or as someone else put it, "How can you tell the computer what to do, if you can't do it yourself?"
I've written video/image codecs and when things go subtly wrong, decoding the raw bitstream by hand and comparing carefully with the decoder output has been the best way to figure out the problem. It can be quite tedious, but as the phrase goes, definitely "builds character".
Or as someone else put it, "How can you tell the computer what to do, if you can't do it yourself?"
I want some hybrid that uses AR on my phone to help me hand draw and color in QR codes for when I can't print them.
I'd be very interested in seeing this when you are done!
This sounds pretty cool. Hope you share it when it’s finished!
I found this video to be a lot clearer and with the combination of the website makes understanding easier: https://www.youtube.com/watch?v=KA8hDldvfv0
Though QR codes are very interesting technically, they were designed to be used by devices with orders of magnitude less computational power than is currently the norm, and much lower resolution optics as well. This is a good thing from an error-prevention perspective, but I wonder if a more modern QR code could be designed for today's smartphones.
I think an interesting new standard would take advantage of higher resolution cameras and OCR functionality to make data transparent to the consumer. I personally wonder what the hell is going to pop up on my phone every time I use a QR code... Text? URL? Link to an app store? Who knows. A standard which marks text as "data" would let a user know what they're saving, and let them point a camera in the general direction of some text, and all the relevant info be extracted and organized. (Think addresses, receipts, etc.) I already use my phone to remember lots of things - like I take a picture of the back of my DSL router for the access codes printed there, or take a picture of my bike tire to remember the size of the tube I need, etc.
Or if transparency isn't important, given we have 4K cameras now, imagine if there was a popular standard using steganography! I can imagine movie posters having showtimes, director and actor info, URLs for streaming it online, etc. all baked into the image.
I think an interesting new standard would take advantage of higher resolution cameras and OCR functionality to make data transparent to the consumer. I personally wonder what the hell is going to pop up on my phone every time I use a QR code... Text? URL? Link to an app store? Who knows. A standard which marks text as "data" would let a user know what they're saving, and let them point a camera in the general direction of some text, and all the relevant info be extracted and organized. (Think addresses, receipts, etc.) I already use my phone to remember lots of things - like I take a picture of the back of my DSL router for the access codes printed there, or take a picture of my bike tire to remember the size of the tube I need, etc.
Or if transparency isn't important, given we have 4K cameras now, imagine if there was a popular standard using steganography! I can imagine movie posters having showtimes, director and actor info, URLs for streaming it online, etc. all baked into the image.
Most of your critique would be handled by proper input sanitation and allowing the user to review and confirm the best / default action.
For a modern QR code I'd prefer something that allows more data and which also mandates support for some compression algorithms and data filters.
Old QR codes are optimized for shrinking serial numbers, barcodes, and the like to a very small size on a product. That's a good use case and I feel they've sufficiently solved that problem domain.
A modern QR might include more like a very tiny web-page, with a subset of allowed entities for security. An icon, or a link to an icon, image (links, maybe bitstream embed?), and simple links.
I would ideally love to be able to hand out small files as blob patches on a business card, printed on a standard laser printer (300 DPI max resolution, assume 100 to 150ish DPI). Maybe two files on the back half. One a reasonable resume and the other a pack of public key data.
Edit, back of napkin math: In the US that would be about 3.5in by 2in and in the dot density about 1.5 in square for each of two squares. At 300 that'd be 450 by 450 dots, or 150 by 150 in the minimum. 22500 to about 200000 bits, not including ECC. The upper density I'd like only offers about 25K of data. This might be enough for a compressed mostly text document or some well-packed PQC safe keys and en EC crypto key or two for current use.
https://en.wikipedia.org/wiki/Post-quantum_cryptography#Comp...
For a modern QR code I'd prefer something that allows more data and which also mandates support for some compression algorithms and data filters.
Old QR codes are optimized for shrinking serial numbers, barcodes, and the like to a very small size on a product. That's a good use case and I feel they've sufficiently solved that problem domain.
A modern QR might include more like a very tiny web-page, with a subset of allowed entities for security. An icon, or a link to an icon, image (links, maybe bitstream embed?), and simple links.
I would ideally love to be able to hand out small files as blob patches on a business card, printed on a standard laser printer (300 DPI max resolution, assume 100 to 150ish DPI). Maybe two files on the back half. One a reasonable resume and the other a pack of public key data.
Edit, back of napkin math: In the US that would be about 3.5in by 2in and in the dot density about 1.5 in square for each of two squares. At 300 that'd be 450 by 450 dots, or 150 by 150 in the minimum. 22500 to about 200000 bits, not including ECC. The upper density I'd like only offers about 25K of data. This might be enough for a compressed mostly text document or some well-packed PQC safe keys and en EC crypto key or two for current use.
https://en.wikipedia.org/wiki/Post-quantum_cryptography#Comp...
Seven years ago I had the wildest ideas of creating photo realistic QR's. Sadly, I got pulled away to other projects with higher priority. The unanimous advice given to me at that time was to hold publishing so I could exploit it financially. Until today neither of both have changed.
I'm not going to let it catch more dust and decided to open-source it under Affero license.
Creating a photo realistic QR requires two steps. The first is to create a 93x93 dithered monochrome image. The dithering is calculated to preserve the mandatory QR framework/timing bits and generating the CRC.
The second step is adding colour information as a 186x186 dithered layer. The colour palette is created using Spacial Colour Quantification which uses the 93x93 QR image as constraints on the available colour range.
SCQ also stabilises palettes used for animations (a service not made available on the site).
During the years the site has been prone to bitrot. I managed to recover most of the missing parts parts from backups. Most of the functionality has been restored and I'm still working with higher priority projects.
[0] https://www.qrpicture.com [1] https://github.com/xyzzy/qrpicture
I'm not going to let it catch more dust and decided to open-source it under Affero license.
Creating a photo realistic QR requires two steps. The first is to create a 93x93 dithered monochrome image. The dithering is calculated to preserve the mandatory QR framework/timing bits and generating the CRC.
The second step is adding colour information as a 186x186 dithered layer. The colour palette is created using Spacial Colour Quantification which uses the 93x93 QR image as constraints on the available colour range.
SCQ also stabilises palettes used for animations (a service not made available on the site).
During the years the site has been prone to bitrot. I managed to recover most of the missing parts parts from backups. Most of the functionality has been restored and I'm still working with higher priority projects.
[0] https://www.qrpicture.com [1] https://github.com/xyzzy/qrpicture
For those interested in the creation of the QR code.
Japanese TV Station NHK World have a 15 minute documentary charting it's creation -
https://www3.nhk.or.jp/nhkworld/en/ondemand/video/2072031/
It also features interesting details such as how they figured out the ratio of the marker squares should be.
It also features interesting details such as how they figured out the ratio of the marker squares should be.
Make sure to have a QR code reader on hand as you watch this. The video is full of Easter eggs hidden in the dramatizations.
This was a good exploration of your approach. The interactive usage inline with description was very helpful. As some have pointed out, some expansion in certain areas could improve it, but still good.
As a side note, I'm looking into using your libraries. They do seem fairly solid and efficient.
Thanks for putting this out there!
As a side note, I'm looking into using your libraries. They do seem fairly solid and efficient.
Thanks for putting this out there!
Previous discussion: https://news.ycombinator.com/item?id=18360847
An artisanal QR code goes over the error correcting code by manually calculating the long division: https://www.quaxio.com/an_artisanal_qr_code.html
This is a great resource. I used it along with another practical tutorial (https://www.thonky.com/qr-code-tutorial/) to complement the official QR code standard when I wrote my own QR code encoder in Common Lisp: https://github.com/mare5x/LispQR
Along similar lines is there any guides on making more artful QR codes? I've seen ones that aren't square but still scan and found them fascinating.
It basically amounts to cranking up the error correction and seeing how much you can get away with changing before it stops reading correctly.
How small can you make a QR code until it can't be scanned by a phone?
That's dependent on the zoom factor and focus distance of your lens and therefore really hard to say in general.
In theory, you could even make a micrometer-sized QR code and scan it using a phone-microscope-attachment - so if you're really trying to push it, probably smaller than you can reasonably print/manufacture.
For a more practical usage, when we worked with QR-Codes, about 3cm by 3cm (or 1.2 inch) seemed to be the smallest unit not causing trouble; smaller than that and problems with focus started appearing for some clients and scan times increased. Of course, that's only anecdotal evidence.
In theory, you could even make a micrometer-sized QR code and scan it using a phone-microscope-attachment - so if you're really trying to push it, probably smaller than you can reasonably print/manufacture.
For a more practical usage, when we worked with QR-Codes, about 3cm by 3cm (or 1.2 inch) seemed to be the smallest unit not causing trouble; smaller than that and problems with focus started appearing for some clients and scan times increased. Of course, that's only anecdotal evidence.
That's really cool! Thanks for sharing it!
>The math behind computing the Reed-Solomon error correction codes is omitted because it is long, tedious, and not very interesting.
LOL! That's probably the most difficult part of creating a QR code, the rest is just framing/padding the data which is pretty obvious.
LOL! That's probably the most difficult part of creating a QR code, the rest is just framing/padding the data which is pretty obvious.
I'd argue that while Reed-Solomon is used in QR codes, the math behind it is not central to explaining how to create a QR code, and there are plenty of material available on Reed-Solomon.
Specific framing/padding of the data is what makes a QR code. This may be simpler than explaining how Reed-Solomon codes work but it is not obvious.
I think it is good that this article stays on point.
Specific framing/padding of the data is what makes a QR code. This may be simpler than explaining how Reed-Solomon codes work but it is not obvious.
I think it is good that this article stays on point.
Other discussions on Hacker News and Reddit have requested me to show the Reed-Solomon ECC calculations too (see https://news.ycombinator.com/item?id=18370829 ).
mytailorisrich is correct; Reed-Solomon is used by many different standards, so it's not difficult if you learned it elsewhere. Whereas other parts of the QR Code standard are idiosyncratic, i.e. unique to it. If you want to see for yourself, go learn how Data Matrix works (another 2D barcode) and notice how little knowledge you can carry between the two standards.
As for showing the Reed-Solomon calculations, I stand by my statement of them being long and tedious. Moreover, it requires background knowledge of finite field arithmetic (as opposed to ordinary arithmetic), which increases the explanation length and makes the calculations even more difficult to follow by hand.
The actual Reed-Solomon encoding is conceptually simple. First you choose a generator element. Then you create a divisor polynomial by multiplying monomial terms involving powers of the generator. Then you encode the message as a polynomial, and finally divide the message by the divisor to yield the remainder polynomial, which is the final RS ECC data.
If you want to see the cryptic verbosity of tons of numbers, here are examples: https://www.backblaze.com/blog/reed-solomon/ ; https://www.youtube.com/watch?v=H2LlHOw_ANg (AES)
mytailorisrich is correct; Reed-Solomon is used by many different standards, so it's not difficult if you learned it elsewhere. Whereas other parts of the QR Code standard are idiosyncratic, i.e. unique to it. If you want to see for yourself, go learn how Data Matrix works (another 2D barcode) and notice how little knowledge you can carry between the two standards.
As for showing the Reed-Solomon calculations, I stand by my statement of them being long and tedious. Moreover, it requires background knowledge of finite field arithmetic (as opposed to ordinary arithmetic), which increases the explanation length and makes the calculations even more difficult to follow by hand.
The actual Reed-Solomon encoding is conceptually simple. First you choose a generator element. Then you create a divisor polynomial by multiplying monomial terms involving powers of the generator. Then you encode the message as a polynomial, and finally divide the message by the divisor to yield the remainder polynomial, which is the final RS ECC data.
If you want to see the cryptic verbosity of tons of numbers, here are examples: https://www.backblaze.com/blog/reed-solomon/ ; https://www.youtube.com/watch?v=H2LlHOw_ANg (AES)
For those curious, I've always found Computerphile has a reasonable explanation for most things
https://www.youtube.com/watch?v=fBRMaEAFLE0
https://www.youtube.com/watch?v=fBRMaEAFLE0
And perhaps the most interesting part, too.
... or you could just use an "Oh By" code.[1]
No app, no reader, and you can just chalk/write/scratch it anywhere you like.
This message, for instance, is at: 0xH6VYP7 [2]
[1] https://0x.co/
[2] https://0x.co/H6VYP7
No app, no reader, and you can just chalk/write/scratch it anywhere you like.
This message, for instance, is at: 0xH6VYP7 [2]
[1] https://0x.co/
[2] https://0x.co/H6VYP7
What happens when the company goes out of business?
What happens when you try requesting random short URLs to peep on other people's texts?
What happens when you try requesting random short URLs to peep on other people's texts?
"What happens when the company goes out of business?"
That's the most frequently asked question.
rsync.net has been providing service, continuously, for 19 years, so it's not without a good track record that I say I will keep "Oh By" running forever, even if it doesn't make any money.
Interesting trivia: Oh By has actually made money ... as in, people have paid for custom Oh By codes.
That's the most frequently asked question.
rsync.net has been providing service, continuously, for 19 years, so it's not without a good track record that I say I will keep "Oh By" running forever, even if it doesn't make any money.
Interesting trivia: Oh By has actually made money ... as in, people have paid for custom Oh By codes.
"What happens when you try requesting random short URLs to peep on other people's texts?"
I think most use-cases involve a code that you chalk up, or write, or paste publicly ... I am not sure that the codes being secret will be a common use-case.
There's a fair amount of space in a 6-digit alpha-numeric code, though (36^6, roughly) ... that's a lot of brute forcing ...
I think most use-cases involve a code that you chalk up, or write, or paste publicly ... I am not sure that the codes being secret will be a common use-case.
There's a fair amount of space in a 6-digit alpha-numeric code, though (36^6, roughly) ... that's a lot of brute forcing ...
I get an SSL error NET::ERR_CERT_COMMON_NAME_INVALID, with the certificate's subject being dock.shp.mcafee.com
Edit: Never mind, it's my ISP (CenturyLink) being dumb and saying it's malicious. Need to figure out how to disable that.
Edit: Never mind, it's my ISP (CenturyLink) being dumb and saying it's malicious. Need to figure out how to disable that.
Sure, I understand these are just the steps to create a QR code and I could just Google why the QR code needs a masking pattern, but that’s besides the point. A good material would explain why I need it, instead of just saying it should be done. Even one sentence would be sufficient.