Decoding QR Codes for fun and profit

QR code decoders

If you’ve ever wanted to make your own QR Code decoder, you’ve probably come across these tutorials, and while they are fantastic, they are for encoding not decoding. Trying to use them myself I ran into numerous pitfalls, so I’ll save you from bashing your head against your desk for several hours.

Generally speaking, the decoding process goes like this:

• Read the format bits to find the error correction level and mask pattern
• Read and unmask the data codewords
• Deinterleave the data codewords
• Read the encoding and length information
• Decode the data

There’s a lot more involved on the error correction and image processing side, but I won’t be going over those in this guide.

Anatomy of a QR Code

Before we get to decoding, let’s first understand the different parts of a QR code.

1. Modules

   • These are the distinct black and white boxes that make up the QR code
   • They are called modules to separate them from pixels, because in an image a module is usually made up of many pixels
   • A module is considered “on” or 1 when it is black, and “off” or 0 when it is white

2. Version

   • The QR version is what defines the size of the QR code (and vice versa)
   • version = ((size - 21) / 4) + 1 (size being width or height in modules)

Functional modules

Functional modules are used for various metadata or image processing purposes.

1. Finder pattern

   • Three distinct boxes in each corner except for the bottom-left.
   • They are 7x7 module boxes, with a 3x3 module box inside
   • The 3x3 inner box has a 1 module white border around it
   • They always have a 1 module white border around the two sides facing inwards

2. Timing pattern

   • Two 1 module wide lines, alternating on/off
   • Horizontal and vertical
   • Aligned to the bottom-left corner of the top-left finder pattern

3. Alignment pattern

   • These are smaller boxes spread evenly across the QR code
   • 5x5 modules boxes with 1 module in the center
   • Not present on smaller QR codes (version == 1)
   • The positions are dependent on QR version
     • And they are always in sync with the timing pattern

4. Format bits

   • A 15 bit string containing QR code format metadata
   • Always wrapped around the top-left finder pattern
   • Also to the left of the bottom-left finder pattern, and below the top-right finder pattern

5. Dark Module

   • A single module that’s always on (dark)
   • Always in the same place - aligned to the top-left corner of the bottom-left finder pattern

6. Version bits

   • 18 bits defining the QR version
   • Always a 6x3 rectangle, above the bottom-left finder pattern and to the left of the top-left finder pattern
   • Only present on large QR codes (version > 6)
   • 6 bit version number with 12 bits for error correction
   • Mostly useful for error correction; QR version can be computed from the size

Tip: Hover over me, I’m interactive!

(The dark module is a bit hard to see, it’s next to the top-right corner of the bottom-left finder pattern)

Text manipulation

For no particular reason let’s assume you have a QR code in the following format:

const qrText = `
█▀▀▀▀▀█ █▀   ███▀ █▄█▀▀▀▄▄▀ ▄▀█▄ ▄▄▄  ▄▄█ █▀▀▀▀▀█
█ ███ █ ▀█▄▄▄  ▄█ ▄▄██▄█▄▄▀▀▄█  ▄▀▀▄▄▄ █▀ █ ███ █
█ ▀▀▀ █ ▄█▄   ▀█▄█ ▀ ██▀▀▀█▄▀▄ ▀ ▄▄ ▀▀▄   █ ▀▀▀ █
▀▀▀▀▀▀▀ █ █ ▀ ▀▄▀ █▄▀ █ ▀ █▄▀ █ █▄▀ █ █▄▀ ▀▀▀▀▀▀▀
  ▀▀█▄▀▄█▀█   ▄██▄ ▀▄ ▀█▀▀█ ▄█▄█▀▀▀▀  ▀█▀███ ▄▀▀▀
▄▄█ ▄▄▀▀▄▀ ██▄██▄ ▄▀██  ▄▀▀█▀ ▄▄█▀█▀▄ ██▀▀▄▀▄█▀▀▀
█▀▄▄  ▀  ▀▄ ▀█▀ ▄ █ ▀  ▄█▀▄█▄ ▀▀▀▀█▄█▄ █▀▄▄ ▄▄▀▀ 
▀  ██▀▀█ █▀ ▀ █  ▄ ▄█▄▀██▄▀ ▀█ ▀▄█ ▀  ▀██▄ ▄▄▄ █▀
  ▀█ ▀▀ ▀  ▀ ▄ █▀▄ ▀▄▀▀ ▄▄   ▄▄ ▄▄  █▀ ▀▄▄ █ ▄▄ ▀
██ ▀█▄▀█▀█ ▄▄▀▄ ▀█▀▀▀ ▀▀▄█▀▄ ▄█ ▄  ▀ ▀ ▀█▄█▀▄▄▀ ▀
█▀██ ▀▀▄█▄ █▀▀█▄▀▀ ▀▄▄█▄█▄▄ ▀ ▀    █▀▄▀▄▀ ██ ▀█▄▀
█ ▀▀█▀▀▀█▄▀▄▀ ▀█ ▄█▀▀▄█▀▀▀█  ▄ ▀▀▀█  ▀▀▀█▀▀▀██ ██
 ▀█▄█ ▀ █▄██▀▄██▄ ▀   █ ▀ █▀▀▀▀▀█ ▀▀▀ ▀ █ ▀ █▀▀ █
 █ ██▀▀▀█▄▄▀▀▀█▄▄▀▄██▄▀████ █▄ █▀ █▄▀▀▀ ▀▀▀▀█  ▀ 
▄█   █▀█ ▀█ ██▀█ ▀█▀▄▀▄  ▀ ▄▀█▄▄ ▀▀█▀█ ▀ ▄▀▀ ▀█▀ 
██▄ ▀▀▀ █  ▄▀ ▄▀  ▀▄██ ▄█▀▄▀▄  ▄ ███▄ ▀▀█▀▀▀  ▀▄▀
▀  ▄█▀▀██ ▄▀█ ▄███ █▀▄███ ▀▄ ▀▀▄ █ ▄█ ▀▀ ▀▄▄▀▄█  
▄ ██ ▀▀ ██▀█▄█▀ ▄█ ▀ ▀█▄▄▀▀▀ ▄█  ▄▀▄▀ █▀█ ▀ ▀█▀█▀
 █ █▄▄▀▀ ▄▄██▄▄█  ▄ ▀▄█ ██▄█ ▀▄▀█▄ ▀▀▀ ██▄▀▄▀▀██ 
 █▄▄ ▀▀  █ ▄▀ ▀▀▀ ▄ ███▄▄▄▄ ▄▄ ▀█ ▄ ▀▄█▀▀ ▀▄ ▀███
▀▀▀   ▀▀▄▄▄ ▄▀▄▀ ▄█▀█ █▀▀▀█ ▄██▀▄▀█ ▀▄███▀▀▀██ ▀▀
█▀▀▀▀▀█  ▀█▄██▀█ █ ▀▄▄█ ▀ █▄▀█▀█ ▀  ▀ ▄▄█ ▀ █▀▀ ▀
█ ███ █ █▀▀▄ ▄ ▄▀ █ ██████▀ ▀███▄▀ █▀█ ▀▀▀█▀██▀▀▄
█ ▀▀▀ █ ▀██ ▄▄▀▀▄▀█ ▀▄█  ▄▄ ▀▀▀█▄▀▀ ▀ █▀ █▄  ▀▀▀█
▀▀▀▀▀▀▀   ▀▀▀▀▀▀ ▀▀ ▀▀  ▀      ▀ ▀  ▀ ▀▀   ▀  ▀▀▀`;

If you squint your eyes, it somewhat resembles a QR code. Your phone probably can’t read it. Let’s parse that text and turn it into something more useful.

Given a coordinate (x, y), we have to get the right character from the text. While each character in a line represents one x coordinate, each line represents two y coordinates. Therefore, we get the correct character in each line by selecting (x, y/2) of the text characters.

// clean and split up the qr code text into lines for simpler access
const qrLines = qrText.trim().split("\n");

const char = qrLines[Math.floor(y / 2)][x];

Now for a detour about binary math. Stay with me, I promise it will be quick.

The text is made up of block characters, such that two pixels are stacked vertically in one line of characters:

const emptyBlock = " "; // colloquially "space"
const topHalf    = "▀";
const bottomHalf = "▄";
const fullBlock  = "█";

If you rotate them 90 degrees to the right, you can think of them as a two-bit binary number

const blockMap = {
    [emptyBlock]: 0b00, // 0
    [topHalf]:    0b01, // 1
    [bottomHalf]: 0b10, // 2
    [fullBlock]:  0b11  // 3
}

With this map, we can turn each character into a number, and then we “extract” the bits we want by using some bitwise operations.

So, to get the numerical value we look up the character in the map (blockMap[char]).

This still gives us two possible modules. In order to figure out if we want the top or bottom module, we simply do y & 1. This returns 0 for the top, and 1 for the bottom.

Conveniently, we ordered our bits such that the right-most bit corresponds to the top, and the left-most bit is the bottom. We can now bit-shift our numerical representation by the result of y & 1, so that the right-most bit is always the one we need.

blockMap[char] >> (y & 1)

Last, we need to wrap the result of all of that in one final & 1. This is because in the case where y & 1 == 0, we don’t bit shift at all, and so we return the whole blockMap[char], rather than the top bit.

Putting it all together, we can make a function to get whatever bit we want from our QR code text:

const getModule = (x,y) => {
    const char = qrLines[Math.floor(y / 2)][x];

    return (blockMap[char] >> (y & 1)) & 1;
}

Honestly, I’m not sure if these two lines of code are ugly or elegant. Both I guess?

By iterating over each line twice (and with some flexbox magic), we now have a clean QR code.

Now you can scan it with your phone. But you don’t want spoilers, do you?

Decoding Pt.1: Metadata

To begin decoding we have to know the QR code version, which we can calculate from the size.

const size = QRLines[0].length; // easier to get the width than the height

const version = ((size - 21) / 4) + 1;

You can also get it from the version bits on the larger QR codes, if you want to double-check (or perform error correction).

In our case, we have a 49x49 module QR code, which means it’s version 8.

Next we need the format metadata. It’s 15 bits long; The first 5 bits contain format data and the last 10 are for error correction. It’s wrapped around the top-left finder pattern, or next to the bottom-left and top-right patterns. Watch out for the timing pattern and dark module!

As we do not care about error correction we only have to read the first 5 bits, from either one. The format is then masked with these bits: 101010000010010. Unmasking is performed by XORing the masked data with the mask.

const formatBits = [];

for(let x = 0; x < 5; x++) 
    formatBits.push(getModule(x, 8));

const format = parseInt(formatBits.join(""), 2) ^ 0b10101;

The format contains:

• 2 bits for error correction level
• 3 bits for the mask pattern

With some simple bitwise operations, we can get their values

const ecLevel = format >> 3;
const mask = format & 0b111;

There are 4 error correction levels, and 8 mask patterns

Note that the error correction levels are not in order, it should be L -> M -> Q -> H (from lowest to highest)

(NB: ~~ is shorthand for Math.floor())

In our QR code the format starts with 00111. After unmasking, that’s 10010, meaning our error correction is 10 (2 or High) and the mask pattern is 010 (also 2 or x % 3).

The mask pattern is a 2D mask applied to the data and error correction codewords before they get placed in the QR code. Mask patterns are expressed as formulas that take in the position of the module and produce cool patterns to further break up the QR code.

(Yoinked from the QR code wikipedia page)

While I’m not implementing error correction in this guide, the error correction level will be useful later.

Decoding Pt.2: Reading and Unmasking

Now that we have the mask pattern, we can begin reading the data codewords in the QR code.

Encoded data split into 8-bit codewords. The codewords are placed starting from the bottom-right corner tightly packed, snaking up and down, left to right. Immediately following the data codewords are the error correction codewords, similarly masked, interleaved, and snaked left to right.

The individual bits in each codeword is placed in a zig-zag pattern, in either upwards or downwards direction.

If you encounter functional modules, skip over them.

When you reach the top or bottom, flip the vertical reading direction and continue reading two modules to the left.

The logic for reading data bits is quite simple, despite many diagrams on the internet trying to confuse you.

• Start at the bottom-right corner and set your vertical direction to up

While you have data to read:

• Read the module at your current position
• If you are in an odd column, move one module left
• Otherwise, move one module vertically and to the right
• If you are outside the vertical bounds of the QR code:
  • Flip your vertical direction
  • Move one module vertically (so you’re back inside)
  • Move two modules left
• If you are currently on a functional module, repeat the moving logic until you aren’t

There is one notable exception - if you are in the 7th column (the vertical timing pattern), move one additional module to the left. However if you don’t care about error correction it shouldn’t matter as the data codewords don’t reach that far into the QR code.

There’s are many ways that you could implement reading; Personally I came up with the “skip mask” approach.

Create a square 2D array the same size as the QR code filled with 0, and set all the locations with functional modules to 1. This simplifies reading logic as we can easily check if the module we’re on is a functional module to be skipped over.

const skipMask = Array.from({length: size}, () => new Array(size).fill(0));

We have to calculate the locations with functional modules as they are different for each QR version. Luckily, most of the areas we’re interested in are grouped together and always in the same place. We don’t even need all the functional modules, as we’re mainly interested in the second half of the QR code.

// a few convenience functions

// set a rectangular region of the skip mask
const setRectangular = (startX, startY, endX, endY) => {
   for(let y = startY; y < endY; y++)
       for(let x = startX; x < endX; x++)
           skipMask[y][x] = 1;
}

// set a square region of the skip mask
const setSquare = (startX, startY, size) =>
    setRectangular(startX, startY, startX + size, startY + size);

// the coordinate of the last module inside the QR code
const end = size - 1;


// finder pattern + version block
setRectangular(end - 11, 0, size, 7);

// bottom border of qr code and format bits
setRectangular(end - 8, 7, size, 9);

// horizontal timing pattern
setRectangular(9, 6, end - 11, 7);

Alignment patterns get a little tricky, as each QR code version has different positions. I’ve omitted most of them for brevity, you can see the full list here.

The the positions of each alignment patterns are based on a grid in sync with the timing pattern and spread equally throughout the QR code. The coordinates where each line intersects is the center of an alignment pattern, except where they overlap with finder patterns.

// an array of alignment pattern row/column positions, for each QR version
const alignmentPatterns = [
    // 7 elements not shown...
    [6, 24, 42],
    // ...
];

const patternPos = alignmentPatterns[version];

// iterate through all alignment patterns to generate all permutations
for(const x of patternPos)
    for(const y of patternPos) {
        // filter disallowed positions
        if(
            (x == 6 && y == 6) ||
            (x == 6 && y == end - 6) ||
            (x == end - 6 && y == 6)
        )
            continue;
        
        // the coordinates are for the center, but setSquare 
        // starts from the top-left corner 
        setSquare(x - 2, y - 2, 5);
    }

This will give us a rudimentary “skip mask”:

Next, we need to get the mask function using the mask pattern from the format bits earlier in Pt.1: Metadata.

const maskFunctions = [
    // ...
    (x, y) => x % 3 == 0,
    // ...
];

const maskFunction = maskFunctions[mask]

Now we can implement the module reading logic.

// start by going up
let direction = -1;

const readBit = (x, y) => {
    // get current module and XOR with the mask
    const bit = getModule(x, y) ^ maskFormula(x, y);

    // calculate the next module position to read, skipping any functional modules
    do {
        if (x & 1) { // left column
            x++; // move right & vertical
            y += direction;
        } else { // right column
            x--; // move left
        }

        // when we reach the top/bottom edge
        if(y < 0 || y == size) {
            y -= direction; // go back
            direction *= -1; // flip reading direction
            x -= 2; // jump to next column
        }

        // if we go OOB (x == -1), there's no more to read
        if(x < 0)
            break;
        
    } while (skipMask[y][x] == 1)

    return [bit, x, y]; 
}