Slightly off topic: One day in the late 90s or early 2000s, I wanted to transfer the contents of my Atari 8-bit disks to my PC. I did know about SIO2PC, a cable that converts between Atari's SIO port and the PC's serial port and a piece of software to go with it. But I didn't have the electronics skills to build one (even though it is actually very easy).
So I ended up writing a Basic program on the Atari to read data from the disk sector by sector and paint it on the screen (with the large 4-color pixels of graphics mode 3). The Atari was connected to the TV card of my PC and a Delphi program I wrote was running on the PC that kept taking screen shots and trying to decode the data from there. I quickly learned that empty sectors threw off my pixel position calibration so I added a mask pattern and a checksum. The sector address was also included. With that, I was able to transfer all my disk contents to my PC. To this day I consider it my greatest engineering achievement :)
Some ten years later, I went on to build an SIO2PC program called AspeQt. A more up-to-date community fork called RespeQt is still the most popular tool in that category used by the community. It even has its own subforum on AtariAge[1].
Reminds me of how the first generation iPod firmware and keys were reverse engineered. They blinked out bit patterns on the LCD backlight and used a camera to read the data in! https://mastodon.social/@bagder/111538350617290554
Citation needed, but I think I read that hackers dumped the firmware of Canon cameras by blinking the single red LED on the camera (and foregoing the main graphical LCD). See the CHDK and Magic Lantern projects.
> So is the rest all content? Not quite! There is also error correction, which is used to make sure that the QR code can still be read even if some parts are damaged, blurry, or missing. The error correction is generated by some fancy math, and we don't care about it here for the purpose of reading it by hand.
This should be explained better... I mean sure, the math can be hard.. but is the error correction appended at the end? After every byte? In the middle? Can we still read a qr code by hand if it has error correction (assuming it's not damaged, and we can skip the math part?)?
Barcodes use the last digit as a checksum. The checksum is some adding up the numbers and multiplying or something, then % 10 (only 0-9 possible values). As you can see with this math, the error checking has a 1/10 of a chance of coincidentally showing a correct checksum in cases where the data is incorrect. Either way, that last digit on barcodes is insignificant to the actual product's unique barcode ID.
Fun story: The barcode was ripped and the checksum # was frayed off of an item I was returning to Home Depot. I frantically tried to do the math quicker that the checker could manually look it up. But they won and I'll never forget it.
A few common barcodes including UPC work this way but mostly this is the exception. The 2D ones being discussed here like QR and Aztec use actual error correcting codes, so none of them. In the linear space Codabar (libraries) is a widely used example that doesn’t. GS-128 doesn’t, etc.
When I worked at a grocery store in the 2000s, you didn't need the checksum digit when keying in a barcode by hand. In fact, manually entering the checksum digit would result in a "product not found" error.
So I wonder if the checker had to manually look anything up, assuming it was only the checksum digit that was frayed off.
Perhaps some POS systems do require the checksum digit for manually-entered barcodes, though.
Barcodes are entered as text. Older barcode scanners used to plug into either the serial port or the PS2 keyboard port; often they had an inline adapter so you could plug it in between your computer and keyboard.
As a checksum, the last digit of the barcode is not part of the data (product number), it's metadata; when the barcode reader beeps, that means it has computed the check digit and it matches the digit on the barcode. The barcode data is sent to the computer, but the check digit is not. The check digit is not in the database. The computer using the UPC leaves it to the barcode reader or human to ensure the input is correct.
You'll might also notice that similar barcodes exist in multiple places as well--unopened cases of products might have an identifier that includes the UPC, and so does the price sticker on the shelf. Both of these include more data than just the UPC.
It is possible that a check digit could happen to be incorrect from the beginning. This (and more rarely, an accidental code reuse) does happen fairly commonly with ISBN, so I would expect the same for general UPC/EAN.
As a grocery checker, I also remember not typing the checksum. It isn't part of the product's ID, but manually typing in probably has a higher chance of error than scanning so what the heck??
Another fun fact: in the intro to The Simpsons, Maggie gets scanned by the clerk as a valid item with a price shown on the register.
the data in the code is encoded as a bitstream using possibly different alphabets, byte is just one of them.
Then, depending on the size and error correction level (not covered in the article where this is decoded from) the bitstream is split up into blocks, ecc data is calculated for both, and then the blocks are interleaved.
So this method will fail for any qr version above 5 for any level of ecc, and 3-5 with high levels of ecc.
An Artisanal QR Code [1] shows how to compute the checksum by hand using arithmetic similar to a long division. There are actually two slightly different codes (Reed-Solomon and BCH) for different pieces of information.
Great explanation of how to read QR codes, thanks for the write up! Here's a nice one about 1D codes and how to decode your average UPC codes you find on products in (American) supermarkets:
I tried reading them manually about ten years ago, but gave up because of the mask. The mask pattern needs to be applied (xor) before you can even tell as much as the data type...
Does anyone know how much it actually helps QR code readers to have this mask pattern applied?
Last month, I tried to find out what the optimal error correction setting is (answer: none, if the matrix isn't damaged, like in my use-case where it's shown on a screen), which wasn't easy to find. I didn't find anyone who actually went out into the real world and tried out different settings and different scanning implementations to see what the effect is of choosing a good mask or choosing a good error correction value. In the end, a theoretical answer was enough for my application because I can assume the QRs to be pristine, but in a perfect world we also wouldn't need a mask setting. I then tried to do some research of my own by reading a small QR off my screen with different error correction levels and an intentionally shaking camera to simulate read issues when someone points a smartphone, but found no significant difference between any of the settings. With there being at least four alignment markers, a huge quiet area, and a "timing pattern", does it really matter if there are white blobs due to not having a mask?
(The secondary reason why I gave up trying to read QRs visually is because I noticed they always have the URL written below as fallback anyway. Since then, I did see a few times where there was no fallback, but it's very rare)
The error correction is funny. If you don't use it, your message takes up less space, and the QR is smaller. If you have a fixed space to fit it in (e.g. printing to a sticker), that means your pixels can be physically bigger. For reliable reading, I found that physically bigger pixels helped more than the error correction itself.
Depending on the length of your message, sometimes you can turn up the error correction level without impacting the final QR dimensions, and in those cases it's a win/win.
The 'proper' fix is to either engineer cameras that can focus closer, or to engineer barcode scanning apps to be able to see a code which is small somewhere in the frame.
It doesn't matter how objectively good your camera/decoder is, in absolute terms. There will always be some minimum size or maximum distance, where the detail can no longer be resolved (or errors no longer corrected)
If we're talking theory, the pixel size doesn't matter - it's the amount of information encoded in the QR code that matters (ie. excluding ECC bits!). In turn, that means it is theoretically possible to decode a QR code where each 'pixel' of the code is smaller than the pixel of the camera sensor observing the code.
While it is theoretically possible, nobody has yet done so...
Physically bigger pixels help a lot indeed. The encoding mode also helps make pixels bigger.
This is very convenient when you control the QR reader and need to represent long numeric identifiers like UUIDs.
For example:
9728983f-7d7d-4189-b624-f92781e36650 (lowercase UUID):
=> length=36, 15 pixels between markers
JWM9GFVXFN0RKDH4Z4KR3RV6A0 (base32 UUID):
=> length=26, 11 pixels between markers
9728983F-7D7D-4189-B624-F92781E36650 (uppercase UUID):
=> length=36, 11 pixels between markers
200924207194334734815443970355691218512 (decimal UUID):
=> length=39, 7 pixels between markers
The uppercase UUID has bigger pixels because it used a different encoding, and gets the same results as the shorter base32 uuid.
The decimal UUID is a longer string, but results in much bigger pixels because it can use numeric encoding.
I have a QR code base attendance tracker [1], where attendees show the code [2] on their phones (glares, etc.), in bad lighting conditions, etc. Bigger pixels means scanning stays quick. Same with parcel tracking [3] where field agents might need to scan QR codes in barely-lit hallways, etc.
-4J5BJ+%F$C881NIMV-IG2.C (base45, 132 bits in QR)
JWM9GFVXFN0RKDH4Z4KR3RV6A0 (base32, 143 bits in QR)
200924207194334734815443970355691218512 (decimal, 130 bits in QR)
It will make use of all allowed characters in the alphanumeric mode, while being significantly shorter than base32 and as dense as decimal. And decimal encoding in general needs bignum, because there is no suitable 10^k which is only slightly larger than powers of two so no convenient binary-to-decimal encoding exists (conversely, QR code itself does make use of the fact 2^10 is only slightly larger than 10^3 for this mode). Base45 always works on three-byte groups and maintains the similar efficiency in comparison.
The error correction isn't meant for folks like us who think about things like "how can I make this message smaller to increase the readability of the QR code", it's for the people that take their entire tracking parameter-infected URL and dump it into a version 25 (117x117) code and plaster it onto a huge sign out front where a bird promptly shits on it and a teenager slaps a sticker on it and somehow the data remains.
I also have the impression that a common use of error correction is the "QR Code with a logo in the middle" style. With an appropriate level of error correction, you can carve an empty patch in the middle of the logo and slap a logo/icon there, and the QR code remains readable.
At least this is the way I did it years ago when I thought it would be fancy to have my contact data as a QR Code on my visit card.
Last year I did some experimentation along these lines and I also found that no error correction was best, at least when 3d printing QR codes. I was trying to find how small I could print it and still have it be detectable. Like the sibling comment, I suspect it is because of individually larger pixels.
The problem with that, as I understand it, is that your 3d print (or any print or screen) cannot get damaged at all. The pixels being bigger makes it easier to scan ...when it's fully in view and fully intact. Any pixel fails, and you can never recover the original data (besides some guesses, e.g. if the protocol identifier gets damaged a la htwps://)
Error correction doesn't seem to be for easier scanning, but for errors that might occur
(... and stupid logo overlays)
but this information is annoyingly hard to find. Hence my question about the mask xor overlay: does that actually help? Did anyone try it, or did it just sound like a good idea?
the idea that a single pixel of the design would get damaged absent the rest seems unlikely. What seems to be more common is that a direction of light/some flaw in the printing process causes many/all pixels to be flawed in the same way past some threshold.
Error correction is a fascinating topic. Shannon discovered in the mid-20th century what the theoretical limit was, yet nobody knew how to achieve it. When we suddenly got close in the 1990s with the patent of turbocodes the community reacted with disbelief!
Of course, that's what's enabled things like fast and reliable mobile networks.
Semi-related, there was a recent puzzle (part of an offshoot of the 2023 Mystery Hunt), which required you to decipher a really broken QR code by hand (too far for error correction to work). We ended up looking at all the guides listed in this comment section, and while they were useful, none were super great. It's always nice to have more detailed articles like this, and this one definitely seems very polished!
It’s of course possible, but the spec is trying to avoid this. There are multiple “masking patterns”, and the algorithm should choose one that gives fewest “penalty points”. Large single color areas are a lot of penalty points, so QR algorithm is trying to avoid them.
Yeah, it's not mandatory. The specification itself recommends a very concrete algorithm though, and one of its criteria is literally the average density [1].
My friends often joke that a person who is checking our tickets is able to do precisely this mentally in their head – when that person is satisfied by seeing a QR code rather than scanning it.
It became very popular over here with the Green Passes (EU Digital Covid Vaccination Certificates). Waiters, etc. were supposed to check whether the guests are vaccinated, but 99% of them just demanded any random QR code to be shown to them, took a look at it and considered it done.
Unless we are a country of hidden math geniuses :)
It would probably only take a week of training/practice for someone to get good enough to read them manually. Particularity if the vaccination codes have a common pattern - the same mask, format information and the like. I would expect you can look at a few areas to see if the person is vaccinated (though this wouldn't pick up on someone else's vaccinated status)
We don't need to verify everything though, just extract the vaccinated/not field which is probably in the same location on every QR code (or at least it should be possible to make it in the same area), and maybe the name of the person the QR code is for.
The signature is the whole point of the QR code though, otherwise someone could just trivially create a QR code that has their name and "vaccinated = yes".
How could two-dimensional codes have been designed to be human-readable?
I was hoping to learn from the article how to manually read QR codes, but that format, at least, is much too complex to do with any efficiency.
At the end of the day, it's bits. Simplist case: 7-bit ASCII; eliminate masks (is that really so difficult for modern software to read sans the masks?); put error correction, length etc. in some corner where humans can ignore them ...
This would have been useful a few weeks back, especially the error correction part!
I was visiting an unmanned business (no-one around) and my phone was dead. I wanted to connect to the wireless but the WiFi sign had only a QR code and no plain text password.
I didn't have a QR code scanner on my computer. One of my services uses a QR scanner on the web but I didn't have that project cloned on my MacBook.
Regardless I scanned dependencies of dependencies hoping that some useless NPM dependency or some python package would have a QR code scanner but to no avail.
In my search at least I found (several) parsers which knew how to scan the QR code (exactly what the article is describing) from a picture but no code to go from an image to the binary data. I didn't have OpenCV or any other library I'm familiar with to process images and I deemed it hard to do something without documentation - so I took a photo with PhotoBooth and started converting the picture manually square by square into 0 or 1.
A few minutes later (and plenty of double checking) I had the data and I piped it into one of the parsers et voilà, I had internet.
My son, a freshman in high school, had an Apple Watch as his first and only device for a while. One big annoyance for him was not being able to scan QR codes that are common in high school where we live. It is an affluent area and the assumption by many, including teachers, is that all of the kids have phones. Not required and they have computers, just comes up regularly.
I was considering doing a project with low quality camera to scan QR codes. We got him a phone before I started down that path.
I would love a game where you learn to actually read QR codes by eyesight - and quickly. Would be quite fun to have an impressive and not very useful skill
Not sure if it's possible to be honest, it might be if you can sit down with a pen a paper. But again we've seen human perform seemingly impossible tasks before, so who knows.
I've always wanted to see someone encode/decode Base64 in their head.
At best, I've learned to recognize a base64 string that begins with "eyJ" is likely JSON.
Also, if you asked me what the base64 encoding of "password" is, but if you showed me "cGFzc3dvcmQ=" and asked me what the decoded value is, I'd recognize it as "password". Though you could probably change a few digits and fool me.
Wonderful write up, thank you! One question I’ve been trying to answer: I’ve been seeing more QR codes in the wild using dots instead of squares, and rounded edges instead of hard corners.
All my research suggests these are reader implementation specific and not guaranteed to work per the official spec.
But I find it hard to believe these codes are becoming more prevalent if they aren’t guaranteed to read.
You'd be surprised how incompetent most adults are at what they do. I'm sure some less technical person assumed QR reading works the same way everywhere, tested it with their device and went "Yess it works! Ship it!"
I also sometimes see QR codes that are inverted. Not all readers detect them but many enough do that they end up in print.
That being said, the QR code readers most people have in their pockets already have to be able to deal with all sorts of problems (blurry pictures, dust on lens, and many more scenarios) that rounded corners are unlikely to have an affect on any of them.
Rounded corners is handled similarly to blurry images, one of the main ideas is readers to be forgiving in what they accept, and rely on the error detection bits to tell if it is way off.
With error correction you can tolerate stylistic mangling.
The qr code scanning algorithm works based on contrast and is designed to work with poor cameras under poor light conditions. Whatever shapes, colors and shades are used are interpreted as either black or white squares.
The process starts by scanning for the 3 markers on the corners. That give you the square containing the qr content and it's orientation. The next jobs are figuring out the resolution of the square and the version of the qr code used. Eventually you end up knowing the grid dimensions. And then you simply scan the grid as the article outlines by simply averaging the pixels in each grid square to be "white" or "black". As long as you have enough contrast, most grid squares will scan correctly.
You can abuse this quite a bit before it starts breaking. There are some interesting QR codes out there that are barely recognizable as QR codes for people. But if you open them in an image editor and play with the levels and contrast a bit, they are obviously qr codes. And there's error correction too so it's OK if some of the qr code is scanned incorrectly.
How do you distinguish different encoding modes (numeric, alphanumeric, byte, etc.) within the data region, especially when dealing with a QR code that uses multiple encoding modes?
Not sure. But I'm guessing that the finder patters represent a pattern that is not possible in the data encoding. That is, according the the encoding scheme you couldn't have data that, just by chance looked like a finder pattern.
So I ended up writing a Basic program on the Atari to read data from the disk sector by sector and paint it on the screen (with the large 4-color pixels of graphics mode 3). The Atari was connected to the TV card of my PC and a Delphi program I wrote was running on the PC that kept taking screen shots and trying to decode the data from there. I quickly learned that empty sectors threw off my pixel position calibration so I added a mask pattern and a checksum. The sector address was also included. With that, I was able to transfer all my disk contents to my PC. To this day I consider it my greatest engineering achievement :)
Some ten years later, I went on to build an SIO2PC program called AspeQt. A more up-to-date community fork called RespeQt is still the most popular tool in that category used by the community. It even has its own subforum on AtariAge[1].
[1] https://forums.atariage.com/forum/184-respeqt-sio2pc-softwar...