We have all used QR codes at some point of our life. UPI payments in stores, scanning QRs on posters to register for an event, sometimes even restaurants where the entire menu is stored on a QR code. But have you ever wondered how it works? If your answer is no, don't worry. I was the same lol. But I suddenly felt like going into this rabbithole, and it was a crazy experience to say the least.
Let's start from the beginning. QR stands for Quick Response. It was first created back in 1994 at a Japanese automobile company to track the types and numbers of different parts. But with the advent of the 2000s and the Internet, people soon found the potential of QR codes left untouched, and now its become a common part in many systems.
A QR code can seem random at first, but every black and white pixel carries a meaning. It contains some static patterns, like the three 7x7 squares at the top-left, top-right, and bottom-left corners, which are used by a scanner to determine the extent of the code to be scanned. There are predefined rules to placing information on the grid, and we will discuss them as we progress further in this blog.
Phase 1: Encoding text into bytes
A QR code is a bunch of black and white pixels. Every dark pixel is 1 and every light pixel is 0. So, the input text must be encoded into binary bytes so that it can be engraved into the grid.
There are a few different modes of encoding, but the ones we will talk about are the following three:
Numeric mode: It is the most efficient mode to encode text containing only numeric values. It uses 10 bits to store 3 digits (2^10 = 1024 > 999), 7 bits to store 2 digits (2^7 = 128 > 99), and 4 bits to store 1 digit (2^4 = 16 > 9).
Alphanumeric mode: This mode has a character set of 45 elements, including uppercase characters A-Z, digits 0-9, space, $, %, *, +, -, ., /, :. It uses 11 bits to store 2 characters ((45 x first_char) + second_char), and 6 bits to store 1 character (2^6 = 64 > 45).
Byte mode: This mode stores every character as a single byte, according to ISO 8859-1 character set, or if supported, UTF-8. Here, every character is stored with 8 bits (1 byte).
We would write the code in a way so that it can automatically determine the best encoding mode to use, as per the characters present in the input text.
It is time to construct the message data bytes. The first four bits represent the encoding mode, as follows:
1. Numeric mode: 0001
2. Alphanumeric mode: 0010
3. Byte mode: 0100
Next would be to encode the number of characters in the input (i.e. character count of input text). Different versions of QR code specify the number of bits the character count must be represented it. I highly recommend readers to go through Thonky's QR Code Tutorial for detailed information.
After the character count, its time to finally push the encoded bytes of input text. At the end of these bytes, terminator bits are added, which are 4 0s. If however, there isn't enough space left for 4 0s, the spec says to add only the number of 0s that are available.
After adding the terminator bits, if the number of filled bits is not a multiple of 8, add more 0s to pad it up to the next nearest multiple. Following that, we add bytes 236 and 11 alternatively until the full allocated message data bytes are full.
Phase 2: The Math (and correcting errors)
This is where the math starts. We start with Galois Field. A Galois Field GF(p) is just a set of numbers that follow all general properties (closure, associative, etc) of all operations like addition, subtraction, multiplication, division. In a field GF(p), every operation is mod p.
For example, let's take GF(5). The set of numbers would be {0, 1, 2, 3, 4}. Addition: a + b (mod 5). For instance, adding 1 and 3 would be 1 + 3 = 4 mod 5 = 4. For numbers greater than 4: 2 + 7 = 9 mod 5 = 4. This follows for all operations, wrapping every operation result into the set of numbers provided.
In our case, we use GF(2^8) since we are working with bytes, so the possible values are 0 to 255, decimal values possible in 8 bits (1 byte).
Multiplication in GF(2^8)
In regular arithmetic, multiplying two 8-bit numbers can go up to 65025. To fit all results within 0 to 255, numbers in GF(2^8) are treated as polynomials where (n+1)th bit is the coefficient of x^n (e.g. 8th bit - x^7, 3rd bit - x^2, 1st bit - x^0 (constant term)). For example, 13 in binary is 00001101, represented as a polynomial as follows:
1.x^3 + 1.x^2 + 0.x + 1 = x^3 + x^2 + 1
To keep multiplication bounded within 0-255 (8 bits), we multiply these polynomials using standard algebra and take the remainder after dividing by a primitive polynomial (an irreducible polynomial that acts as the prime number for field restriction).
For QR codes, the standard primitive polynomial specified by ISO/IEC 18004 is x^8 + x^4 + x^3 + x^2 + 1 (represented as hex 0x11D or decimal 285).
NOTE: Addition and subtraction in GF(2^8) are both equivalent to XORing the two numbers.
Fast way: Log and Antilog Tables
Doing full polynomial long divison for every single multiplication during Reed-Solomon generation would destroy performance. Instead we use a property: a primitive element g (generator) can generate every non-zero element in the field through exponentiation. For QR codes, we use g = 2.
By pre-computing two 256-element lookup tables (an exponential (antilog) table and a log table), we can convert heavy polynomial multiplication into simple integer addition:
a x b = exp((log(a) + log(b)) mod 255)
Error Correction Levels
Before moving on to actually error correction, we need to discuss the different error correction levels. QR codes have four different levels, each having a different number of error correction bytes to be added depending on the version of QR code. The four levels are:
L (Low): 7% error correction
M (Medium): 15% error correction
Q (Quartile): 25% error correction
H (High): 30% error correction
Generating Error Correction Bytes (Reed Solomon Codes)
This is the error correction method we will be using for QR codes. Reed Solomon error correction works by taking your message bytes, treating them as coefficients of a high-degree message polynomial M(x), and finding the remainder when divided by generator polynomial G(x). The remainder R(x) contains the actual error correction bytes to be appended to the original message bytes.
1. Generator Polynomial G(x)
A generator polynomial for k error correction codewords is created by expanding the factors (x-2^0)(x-2^1)...(x-2^(k-1)) using GF(2^8) arithmetic. For example, for k=7 error correction bytes:
G(x) = (x-2^0)(x-2^1)...(x-2^6)
Expanding this gives a polynomial with 8 terms whose coefficients are elements in GF(2^8).
2. Polynomial Synthetic Division
To compute the remainder, we perform synthetic division of M(x).x^k by G(x) inside our field:
Shift the message polynomial left by k positions (multiplying by x^k) to leave k zero bytes at the end for error correction bytes.
-
Step through each byte of the message:
- Take the first byte of the current remainder buffer as a multiplier scale factor S.
- If S != 0, multiply each coefficient of G(x) by S using our log/exp lookup tables.
- XOR the scaled generator polynomial into the remainder buffer.
- Shift the remainder buffer left by 1 position.
Once all message bytes are processed, values remaining in the remainder buffer are the exact Reed Solomon Error Correction Bytes.
And we are done! We now have the error correction bytes, and we append it to the end of the message bytes we had previously.
For implementation details, you can refer to my QR code generator in Rust, linked in a later section.
Phase 3: Masks and Format String
We are almost at the end. The last phase is to choose a mask and create the format string. A mask is essentially a formula which decides which pixels on the grid should be XORed. The main reason of using a mask is to reduce unnecessary concentration of same-color pixels and other factors that can affect the ability of scanners to properly scan a QR code.
There are 8 different masks, ranging from 0 to 7 (000 to 111). I will not be going through all the formulae here, but again, I recommend you to go through Thonky's guide for details on this.
Choosing a mask: Penalty Rules
All the 8 masks are applied on to the grid, each is checked against four penalty rules, and the mask with the least penalty score is finalized. The beauty of masks is that they are their own negatives, i.e. XORing a mask onto a grid masks it, XORing it again gives us back the original data grid.
The four penalty rules are as follows:
Continuous runs of same-color modules of length 5 or more, in a row or a column.
Score: 3 + (n - 5) per run of length n >= 5.2x2 blocks of same-color modules.
Score: 3 points per 2x2 block.Patterns matching 1011101 surrounded by 4 light modules (finder-like false positives).
Score: 40 points per occurrence.Proportion of dark vs light modules deviating from 50%.
Score: 10 x floor(abs(dark_percent - 50) / 5).
Format String
Once a mask is selected, we need to encode metadata directly into the QR code so that a scanner knows which error correction level and mask was used.
The format string is 15-bits long, with 5 data bits and 10 error correction bits. Out of the 5 data bits, 2 bits represent error correction level, and 3 bits represent the mask used (000-111). For error correction level:
L -> 01
M -> 00
Q -> 11
H -> 10
The 10 error correction bits are generated with the help of BCH codes.
BCH Error Correction
Because the format string is critical for decoding the entire QR code, it gets its own error correction using a BCH (Bose-Chaudhuri-Hocquenghem) (15, 5) code. To generate the 10 error correction bits:
Shift the 5-bit value left by 10 bits.
Perform polynomial division modulo 2 using generator polynomial
G(x) = x^10 + x^8 + x^5 + x^4 + x^2 + x + 1(which is 0x537 or 10100110111).The 10-bit remainder is appended to the original 5 bits to form a 15-bit codeword.
Masking the format string
To ensure that format strings don't accidentally contain long runs of all zeros or all ones which could confuse scanners, the final 15-bit string is XORed with a fixed mask: 101010000010010 or 0x5412.
The 15-bit format string is written into two redundant locations on the QR code to survive physical damage or corruption:
Around the top-left finder pattern
Divided between top-right and bottom-left finder patterns
NOTE: Remember to skip the dark module at coordinate (4 * version + 9, 8) which always remains dark (as per QR code specification).
Implementing Everything: The Battle Wounds I Have
Writing qred, my own implementation of a QR code generator, wasn't a smooth ride in the slightest. I faced quite a few brain-frying bugs:
Bit placement order: The issue wasn't in error correction math or matrix generation. Everything was working perfectly, but turns out I was writing the bits of the format string in reverse order. Bit 14 in the place of bit 0, bit 13 at bit 1, and so on. That alone took one day for me to find, and I couldn't even find it alone (massive Claude W).
The Math: I'm surprised I even managed to finish this project. Given my background of not liking math (or so I thought), I expected face much more trouble. Thankfully, after the first weird bug found at the remainder generation of Reed Solomon, I started writing unit tests for every file, ensuring the code of the current phase is fully functional before moving on to the next phase with a broken foundation.
I implemented it in Rust BTW (I use Arch BTW)
Benchmarks
I didn't leave it after just writing everything. I wanted to see the fruits of my labor. So for the first time in any of my Rust projects (don't bully me, I'm pretty new to this field), I downloaded criterion, set up benchmark functions, and started measuring performance. Here's the results, analyze them and judge whether they're good or bad, because I'm leaving absolutely no comments here:
| Operation | Output | Execution Time |
|---|---|---|
| Matrix Generation Only | Pure Bit Matrix | 179.92 µs |
| Default Image Save | Standard PNG Export | 237.19 µs |
| Single Custom Color | Custom Foreground | 274.65 µs |
| Dual Custom Colors | Custom Fore & Background | 281.26 µs |
What I Left Out
Of course, I didn't touch every little detail in this small blog. I have left out some parts, like:
Static patterns like finder patterns, timing patterns, alignment patterns, etc.
Exact locations of format strings, message and error correction bytes.
The order of reading the data bytes.
Next Steps
To dive deeper into this rabbit hole, I recommend these sources as I used them myself:
The full PDF of ISO/IEC 18004
Like me?
Well then, you're not alone (I like myself too)! Check out more about me:
GitHub: https://github.com/aether-flux
qredCrates.io: https://crates.io/crates/qred
A bonus flex: Wanna see my implementation in practice? Scan this QR generated by qred to get to my portfolio:
Top comments (0)