GOPHERSPACE.DE - P H O X Y
gophering on blog.qartis.com
---
title: "Decoding small QR codes by hand"
date: 2012-04-21
---

It's not hard to decode QR codes with a pen and paper. For this guide I'm going
to grab a random QR code from google images and show the process of decoding it
by hand. QR codes contain a lot of error correction information and they can
survive a lot of errors, but that's a lot harder to do using just a pen and
paper (and 99% of the QR codes you encounter don't have any missing bits, so
it's rarely necessary). So I'll highlight where the error correction
information is stored, but I won't explain it in this guide.

The picture I found is from


image:qr-1.jpg

Before we begin we should rotate it to the proper orientation. QR codes always
have 3 timing patterns (big black squares) in all the corners except for the
bottom-right. So we need to rotate our picture 90 degrees counterclockwise:

image:qr-2.jpg

The first thing we should learn is what QR code **version** we're looking at.
The version basically just represents the physical size of the QR code. Count
the number of pixels (or *modules*) across the QR code, subtract 17, and divide
by 4. For example, our tattoo QR code is 25 modules wide, and (25-17)/4 = 2,
which means this is a version 2 QR code. Very big QR codes (versions 7-40) have
a few extra features, but most consumer QR codes are fairly small and simple,
so you don't need to worry about that.

Next, we will figure out our QR code's **format** marker. Every QR code stores
two identical copies of the format marker, but we only need one of them. The
format marker is 15 bits long: 5 bits of format information, and 10 bits for
error correction. The first 5 bits of the format marker hold the error
correction level (2 bits) and the data mask (3 bits). These 5 bits are found
here:

image:qr-3.jpg

So in our case the format information is **01100**. However this number has
been XOR'ed with **10101** before being written into the QR code. So we must
flip bits 1, 3 and 5. After flipping the bits, we get a format information
string of 01100^10101 = **11001**. The first two bits of this value are the
error correction level (the amount of error correction data included in the QR
code). Again, we can ignore this. The last 3 bits of the format string are
**001**, and this is the most important piece of information. This means the
body of the QR code has been masked against the mask number **001**. Here is a
table of all the possible mask numbers and their appearance:

image:qr-mask.png

Here's where you need the pen and paper. The reason QR codes are masked in the
first place is that sometimes particular combinations of data bytes produce QR
codes with certain undesirable features (like big empty blocks in the middle).
These undesirable features confuse the QR code reader, so the data is masked
against a value in order to make the code easier to process when it's scanned
by a QR code reader. The computer then unmasks the original data bytes using
the same process, and retrieves the data.

You can imagine the masking process as essentially covering the surface of the
QR code in one of the patterns seen above, starting from the top left corner.
In our case we have a mask reference number 001, which means all of the
odd-numbered rows are black. Once we've tiled the surface of our original QR
code using the mask pattern, then every black pixel in the mask means we need
to invert the corresponding bit in the original QR code. So in our case, we
need to (in our mind, or using the pen and paper) invert all of the bits on
odd-numbered rows. Note that we only mask the data pixels, and not the timing
patterns or the format marker (otherwise we wouldn't know how to unmask it to
get the mask reference number!). The data areas are the yellow areas in this
picture:

image:qr-data.png

I've highlighted the data areas of the tattoo QR code below:

image:qr-5.jpg

Note that there's a little island in the middle of the data area that we must
work around. That's called an alignment pattern, and whenever you see one in
the data just skip past it to read the data bytes.

From now on we need to always remember the mask pattern above, and whenever we
read bits from the data section we need to account for the mask pattern, and
flip any bits that would be masked off by it (in our case, that's every odd
row).

The data section consists of [header][data] chunks. Technically QR codes are
allowed to have several of these chunks, but most QR codes just have one big
chunk that holds all the data, so it won't matter. The header has an **encoding
type** and a **length** (the number of data bytes). The encoding type is always
4 bits, but the length is stored in 8-10 bits depending on the encoding type.
Here's the encoding type of our tattoo:

image:qr-4.jpg

But remember, every odd row needs to have its bits inverted. To help us
remember, I'll use green to highlight every cell that should be inverted when
we read it:

image:qr-6.png

Now, the encoding type is stored as the bottom-right 4 bits, starting from the
bottom right and working left and right in a zig-zag motion.

image:qr-7.png

So in our case, the tattoo itself has the bits **1000**. However
the bottom row is masked, so we invert the first two bits: **0100**. This means
that our QR code's encoding type is **0100**. Here's the table of encoding
types:

- 0001 Numeric
- 0010 Alphanumeric
- 0100 8-bit Byte

The other encoding types are rarely used in consumer QR codes. They're used for
encoding japanese characters, custom charsets and spreading a message across
several QR codes in series. For our purposes these 3 encodings will be enough.

So that means that our QR code uses 8-bit byte encoding. The next piece of
information is the length field, or the number of characters (clusters of bits)
that are in the message. Like I said, the length field changes size depending
on the encoding type. Here's the number of bits in the length field, for each
encoding type:

- Numeric (10 bits)
- Alphanumeric (9 bits)
- 8-bit Byte (8 bits)

Since we're using 8-bit byte mode, our length field is 8 bits long. We read the
next 8 bits in a vertical zig-zag motion, like this:

image:qr-7-length.png

So the tattoo itself contains the bits **11011100**
(reading from bottom to top). However we need to mask two of these rows, so the
actual length field has the value **00010000**.  That's 16 in decimal, which
means this QR code has a message that is sixteen 8-bit bytes long. After the
length field, the bytes themselves are stored, one after another, MSB first. We
continue climbing in a vertical zig-zag motion until we hit the top, and then
we curl over and continue downwards as seen in this picture:

image:qr-placement.png

So the first byte would be 10000110 (masked), which is 01001101 (unmasked).
That corresponds to ASCII character 'M'. The next byte would be 10101101
(masked), which is 01100001 (unmasked). That corresponds to ASCII character
'a'. So far we've decoded "Ma".

Continuing up and around the corner: 10100000 (masked), or 01100011 (unmasked).
That's ASCII 'c'. Then it's 'i'.

By continuing in this way, we can decode the full message: **Maci Clare
Peltz**.