Let's develop a QR Code Generator, part VIII: different sizes

At this point in the series, we know how to creare a QR Code with numeric, alphanumeric, ISO-8859-1 or Kanji data. But we've created only version 2 QR Codes, meaning that our content is quite limited in size. So let's see how to overcome this.

As we've said in part 1, the version of the code gives its size, as the code matrix will be a square of 17 + version * 4 modules. Part of this square is occupied by either fixed patterns, or reserved space for format information.

Let's have a look at what we're talking about:

So we have:

• three finder patterns (in green), as 8×8 module patterns (including separator lines): these are fixed;
• alignment patterns (in blue), 5×5 module patterns that vary in number (they are n² - 3, where n depends on the version);
• timing patterns (in red): lines that connect the finder patterns, and as such their length depends on the QR Code version;
• a dark module (in olive, fixed);
• error level and mask information (in purple): two 15-module sequences (fixed);
• version format information (in orange); two 6×3 areas adjacent to the top right and bottom left finder patterns (fixed, but present only from version 7 and above).

The content of last two areas have to be generated, but we don't know how to do it for the second one yet (we'll see that later). The main point of variability is the number of alignment patterns in the matrix.

Placing the alignment patterns

As we said, there are n² - 3 alignment patterns in a QR Code, except for version 1 that has no such patterns. The -3 part is because they'd be placed over the finder patterns, as you can see in the figure above. But how do we know this n?

Basically, if v is the version number, it's n = floor(v / 7) + 2, so versions 2 to 6 have 2² - 3 = 1 alignment patterns, versions 7-13 have 3² - 3 = 6, versions 14-20 have 4² - 3 = 13 and so on.

Now the question is: how do we place them in the QR Code's matrix?

As we can realize from the previous figure, they are placed on the vertexes of a grid, and this grid is symmetrical relatively to its main diagonal. This means we only need to know the position of one set of its tracks (either the rows or the columns).

For example, a version 2 QR Code has its alignment patterns on tracks 6 and 18 (nevermind we can only see one); while a version 7 has them on tracks 6, 22 and 38. These values are 0-based (the first row and column have index 0), and refer to the center of the pattern.

Here's the algorithm:

1. the first track is always 6;
2. the last track is always 6 from the end;
3. for the tracks in the middle, do the following:
   • get the difference between the last and the first tracks above, then divide by n - 1;
   • take the even number greater or equal to the quotient above;
   • place the middle tracks counting from the last one.

We need to take an even number because, as you might see from the figure from before, the alignment patterns must match the timing patterns, i.e. you can't have an alignment pattern placed on an odd row/column.

Example: for version 22, n is Math.floor(22 / 7) + 2, so it's 5. A version 22 QR Code is 17 + 22 * 4 = 105 modules wide, so the fifth and last track is 98. For the other two:

• the difference between the last and first track is 92;
• 92 / 4 = 23, so the next even number is 24;
• therefore, the fourth track is 98 - 24 = 74, the third is 74 - 24 = 50 and the second is 50 - 24 = 26.

In code

The following function basically executes the above steps:

function getAlignmentTracks(version) {
  if (version === 1) {
    return [];
  }
  const intervals = Math.floor(version / 7) + 1;
  const distance = 4 * version + 4; // between first and last pattern
  const step = Math.ceil(distance / intervals / 2) * 2;
  return [6].concat(Array.from(
    { length: intervals },
    (_, index) => distance + 6 - (intervals - 1 - index) * step)
  );
}

Note that the pure function above should be used with just 40 different values, so we can safely memoize it, or precompute all the values beforehand and store them in a constant array. Or even copy a table from around the web (e.g. this well known library).

How many codewords?

Once the alignment pattern matter is solved, we can get to know how much actual space there is in a QR Code, i.e. codewords that can be used to store data and error correction information.

As we've said, version 1 has no alignment pattern, so the amount of available modules is:

21² (441, where 21 is the size of the QR Code)
 - 3⋅8⋅8 (192, for 3 finder patterns)
 - 2⋅5 (10, the timing patterns)
 - 1 (the dark module)
 - 2⋅15 (30, the error level and mask information)

for a total of 208, i.e. 26 codewords.

For larger versions, we have to compute this (let v the version number and n the number of alignment pattern coordinates):

v² (total modules)
 - 3⋅8⋅8 (finder patterns)
 - (n² - 3)⋅5 (alignment patterns)
 - 2⋅(4‍v + 1) (timing patterns)
 + 2⋅(n - 2)⋅5 (readding the intersection of alignment and timing patterns)
 - 1 (dark module)
 - 2⋅3⋅6 (format data, only if v > 6)

In code

We just need to do the above:

function getAvailableModules(version) {
  if (version === 1) {
    return 21 * 21 - 3 * 8 * 8 - 2 * 15 - 1 - 2 * 5;
  }
  const alignmentCount = Math.floor(version / 7) + 2;
  return (version * 4 + 17) ** 2
    - 3 * 8 * 8
    - (alignmentCount ** 2 - 3) * 5 * 5
    - 2 * (version * 4 + 1)
    + (alignmentCount - 2) * 5 * 2
    - 2 * 15
    - 1
    - (version > 6 ? 2 * 3 * 6 : 0);
}

You can simplify the above return statement or let the compiler do that for you (I got down to 16 * (version + 4) ** 2 - (5 * alignmentCount - 1) ** 2 - (version > 6 ? 172 : 136)).

Just like getAlignmentTracks, also this function can be memoized/use to precomputation/replaced with a table.

How many data codewords?

The main question is, though, is get to know how many of those codewords are reserved for data - and conversely how many for error correction.

The problem here is that I haven't found, nor derived, any exact formula to determine that. Remember the error correction table we've seen in part 1 and 3?

But we just can't take those percentages and derive the amount of error correction codewords back. The original specification reports this formula (from the Reed-Solomon error correction algorithm):

e + 2‍t ≤ d - p

where:

• e = number of erasures (i.e. single errors at known locations);
• t = number of errors (i.e. recoverable codewords);
• d = number of error correction codewords;
• p = number of misdecode protection codewords (generally 0, except for smaller QR Codes),

meaning that d error correction codewords can correct at most d/2 unreadable codewords.

But other than that, it just reports a table where we can just take the amount of error correction codewords, and that's it (you can get it from here, for example). If you compute the "recovery capacity" for each version and error level, you'll see those percentages being 2-3% off the values from the table.

For example, our case of a version 2 QR Code with quartile error level has 22 error correction codewords, meaning a recovery capacity of 11… which is exactly 25% of all the codewords. But it's a rare case.

If you take a version 6 QR Code, still with quartile error correction level, it can recover at most 4*24/2 = 48 codewords out of 172, which is ~27.9%. If you reserve only 88 codewords for error correction instead of 96, you'd have a recovery capacity of ~25.5% (closer to 25%) and 8 more codewords for data. I don't know why they chose otherwise.

Anyway, let's see how to structure a QR Code for larger versions, because it's not as straightforward as it was for version 2…

Codeword blocks

As version grows, the number of total codewords grows too (more or less quadratically). The spec developers decided it was wiser to split the message into several blocks of varying amounts of codewords. Each block has its own data and error correction codewords.

Moreover, not every block has the same amount of codewords, but they're divided in two groups instead: one with blocks of n codewords, the other with block with n + 1 codewords. But for every block the number of error correction codewords is the same, so it's the number of data codewords that has a difference of 1 between blocks of different groups.

Splitting the total set of codewords into blocks happens as soon as version 3, while you'd get two groups in version 5. The main goal is having the number of error correction codewords in each block to be at most 30, while splitting into groups is just for parity.

But let's cut to the point, and see the actual table:

To read these values: a version 38 QR Code with high error correction level has its data codewords split in two groups. The first group has 42 blocks of 15 codewords each, and the second has 32 blocks of 16 codewords. For each of these blocks, there's a error correction block of 30 codewords.

As a practical example, let's create a QR Code for the string https://en.wikipedia.org/wiki/QR_code#Error_correction (still byte content, for simplicity), adding a quartile error correction level. We need at least a version 5 QR Code for that.

According to the table above, we'll need to split the data codewords into 2 blocks of 15 codewords, then other 2 blocks of 16 codewords each (for 62 codewords in total for data). Using the getData function from the last part, we get:

> getData('https://en.wikipedia.org/wiki/QR_code#Error_correction', 8, 62)
< Uint8Array(62) [67, 102, 135, 71, 71, 7, 51, 162, 242, 246, 86, 226, 231, 118, 150, 182, 151, 6, 86, 70, 150, 18, 230, 247, 38, 114, 247, 118, 150, 182, 146, 245, 21, 37, 246, 54, 246, 70, 82, 52, 87, 39, 38, 247, 37, 246, 54, 247, 39, 38, 86, 55, 70, 150, 246, 224, 236, 17, 236, 17, 236, 17]

These codewords should be split like this:

In the next part, we'll see how to actually place all these information (plus the error correction, and something more) inside the QR Code matrix. See you soon! 👋