Let's develop a QR Code Generator, part V: masking

It's time for the final step to get our first working QR code!

If you remember the final result from the previous part, we ended up with something that had some relatively large areas in dark or light, and that might be troublesome for QR code readers:

So this final step is all about making it easier for readers to actually tell the modules apart in order to compose the square matrix. It goes something like this:

1. for each of the 8 estabilished masks, apply it to the matrix we got at the end of the last part;
2. compute the penalty score of the resulting output;
3. your final QR code is the one with the mask with the lowest penalty score (duh!).

The masks

Masks are, again, matrixes of dots of the same size of the QR code. Each dot has to be XOR'ed with the proto-QR code we got so far.

Fortunately we don't have to acutally memorize these matrixes, as we have their corresponding generation formulas to create them - and all they need is the row and column of each dot. These are the formulas:

Formula #	Dark module test
0	(row + column) % 2 === 0
1	row % 2 === 0
2	column % 3 === 0
3	(row + column) % 3 === 0
4	(floor(row / 2) + floor(column / 3)) % 2 === 0
5	row * column % 2 + row * column % 3 === 0
6	((row * column) % 2 + row * column % 3) % 2 === 0
7	((row + column) % 2 + row * column % 3) % 2 === 0

(No, formulas 6 and 7 aren't the same - look closely!)

These generate the following repeated patterns:

Mask #	Pattern	Mask #	Pattern
0		4
1		5
2		6
3		7

These patterns have to be applied to the data modules only, meaning that all the reserved areas must be left as is. Which means, only to the empty modules in the figure below:

But how do we choose the right mask to apply? Actually, any of the above mask would produce a valid QR Code! It might just be harder to read for code readers. So, Denso Wave devised an algorithm to determine that.

In the final step, we're going to write the information about the error code and the selected mask in the reserved areas of our code, and we'll be done!

Applying the mask

As we said, we need to apply the mask only to the data modules only, leaving the reserved areas alone. First of all, let's translate the mask functions to their JavaScript equivalent:

const MASK_FNS = [
  (row, column) => ((row + column) & 1) === 0,
  (row, column) => (row & 1) === 0,
  (row, column) => column % 3 === 0,
  (row, column) => (row + column) % 3 === 0,
  (row, column) => (((row >> 1) + Math.floor(column / 3)) & 1) === 0,
  (row, column) => ((row * column) & 1) + ((row * column) % 3) === 0,
  (row, column) => ((((row * column) & 1) + ((row * column) % 3)) & 1) === 0,
  (row, column) => ((((row + column) & 1) + ((row * column) % 3)) & 1) === 0,
];

In part 4, we already devised a getModuleSequence function that returns the sequence of coordinates of modules in the filling order. We're going to use that to apply our mask, starting with the code version, the array of codewords and mask index (codewords is the array of both data and error correction codewords):

function getMaskedMatrix(version, codewords, maskIndex) {
  const sequence = getModuleSequence(version);
  const matrix = getNewMatrix(version);
  sequence.forEach(([ row, column ], index) => {
    // Each codeword contains 8 modules, so shifting the index to the
    // right by 3 gives the codeword's index
    const codeword = codewords[index >> 3];
    const bitShift = 7 - (index & 7);
    const moduleBit = (codeword >> bitShift) & 1;
    matrix[row][column] = moduleBit ^ MASK_FNS[maskIndex](row, column);
  });
  return matrix;
}

Encoding error level and mask information

As we've seen, we have some reserved areas in our QR Codes. It's now time to fill them.

At this point, we've already chosen an error correction level. But now that we're in the mask phase part, we have all the information we need to fill the reserved modules. Which are 15, so we're going to start with this:

const formatPoly = new Uint8Array(15);

(Yes, we're going to work with polynomials again, so that explains the suffix Poly.)

Next, each error level is matched with an index:

Level	Index
L	1
M	0
Q	3
H	2

(Yes, they're not in order of correction strenght. Don't ask we why!)

We then can proceed to fill our format polynomial (given the error correction level and mask index):

const EDC_ORDER = 'MLHQ';
const errorLevelIndex = EDC_ORDER.indexOf(level);
formatPoly[0] = errorLevelIndex >> 1;
formatPoly[1] = errorLevelIndex & 1;
formatPoly[2] = maskIndex >> 2;
formatPoly[3] = (maskIndex >> 1) & 1;
formatPoly[4] = maskIndex & 1;

So we've occupied the first 5 "bits" of our format polynomial. The next step is dividing this polynomial by

x¹⁰ + x⁸ + x⁵ + x⁴ + x² + x + 1

Why this exact polynomial? Because it's irreducible blah blah… the usual shenanigans we've seen in part 3 😅

Again, we take the rest of this division and attach it to our format polynomial:

const FORMAT_DIVISOR = new Uint8Array([1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1]);
const rest = polyRest(formatPoly, FORMAT_DIVISOR);
formatPoly.set(rest, 5);

Finally, mask the bits with a specific mask that should grant the best readability (maybe? I don't actually know how it's been chosen 🤷‍♂️):

const FORMAT_MASK = new Uint8Array([1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0]);
const maskedFormatPoly = formatPoly.map(
  (bit, index) => bit ^ FORMAT_MASK[index]
);

Let's wrap it all in a single function:

const EDC_ORDER = 'MLHQ';
const FORMAT_DIVISOR = new Uint8Array([1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1]);
const FORMAT_MASK = new Uint8Array([1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0]);
function getFormatModules(errorLevel, maskIndex) {
  const formatPoly = new Uint8Array(15);
  const errorLevelIndex = EDC_ORDER.indexOf(errorLevel);
  formatPoly[0] = errorLevelIndex >> 1;
  formatPoly[1] = errorLevelIndex & 1;
  formatPoly[2] = maskIndex >> 2;
  formatPoly[3] = (maskIndex >> 1) & 1;
  formatPoly[4] = maskIndex & 1;
  const rest = polyRest(formatPoly, FORMAT_DIVISOR);
  formatPoly.set(rest, 5);
  const maskedFormatPoly = formatPoly.map(
    (bit, index) => bit ^ FORMAT_MASK[index]
  );
  return maskedFormatPoly;
}

And this is how we place our bits (yes, each bit is placed twice, for redundancy):

And the following code should do it:

matrix[8].set(maskedFormatPoly.subarray(0, 6), 0);
matrix[8].set(maskedFormatPoly.subarray(6, 8), 7);
matrix[8].set(maskedFormatPoly.subarray(7), matrix.length - 8);
matrix[7][8] = maskedFormatPoly[8];
maskedFormatPoly.subarray(0, 7).forEach(
  (cell, index) => (matrix[matrix.length - index - 1][8] = cell)
);
maskedFormatPoly.subarray(9).forEach(
  (cell, index) => (matrix[5 - index][8] = cell)
);

Wrapping up

Now let's put it all together. First, let's split up the getRawQRCode function we temporarily created in part 4 to have a function that just fills the fixed areas:

// WARNING: this function *mutates* the given matrix!
function placeFixedPatterns(matrix) {
  const size = matrix.length;
  // Finder patterns
  [[0, 0], [size - 7, 0], [0, size - 7]].forEach(([row, col]) => {
    fillArea(matrix, row, col, 7, 7);
    fillArea(matrix, row + 1, col + 1, 5, 5, 0);
    fillArea(matrix, row + 2, col + 2, 3, 3);
  });
  // Separators
  fillArea(matrix, 7, 0, 8, 1, 0);
  fillArea(matrix, 0, 7, 1, 7, 0);
  fillArea(matrix, size - 8, 0, 8, 1, 0);
  fillArea(matrix, 0, size - 8, 1, 7, 0);
  fillArea(matrix, 7, size - 8, 8, 1, 0);
  fillArea(matrix, size - 7, 7, 1, 7, 0);
  // Alignment pattern
  fillArea(matrix, size - 9, size - 9, 5, 5);
  fillArea(matrix, size - 8, size - 8, 3, 3, 0);
  matrix[size - 7][size - 7] = 1;
  // Timing patterns
  for (let pos = 8; pos < size - 9; pos += 2) {
    matrix[6][pos] = 1;
    matrix[6][pos + 1] = 0;
    matrix[pos][6] = 1;
    matrix[pos + 1][6] = 0;
  }
  matrix[6][size - 7] = 1;
  matrix[size - 7][6] = 1;
  // Dark module
  matrix[size - 8][8] = 1;
}

Then, a similar function to place the format data:

// WARNING: this function *mutates* the given matrix!
function placeFormatModules(matrix, errorLevel, maskIndex) {
  const formatModules = getFormatModules(errorLevel, maskIndex);
  matrix[8].set(formatModules.subarray(0, 6), 0);
  matrix[8].set(formatModules.subarray(6, 8), 7);
  matrix[8].set(formatModules.subarray(7), matrix.length - 8);
  matrix[7][8] = formatModules[8];
  formatModules.subarray(0, 7).forEach(
    (cell, index) => (matrix[matrix.length - index - 1][8] = cell)
  );
  formatModules.subarray(9).forEach(
    (cell, index) => (matrix[5 - index][8] = cell)
  );
}

Finally we can wrap everything up in a single function. Remember, codewords is the Uint8Array equals to the data codewords concatenated with the error correction data, as shown in the getRawQRCode function from part 4:

function getMaskedQRCode(version, codewords, errorLevel, maskIndex) {
  const matrix = getMaskedMatrix(version, codewords, maskIndex);
  placeFormatModules(matrix, errorLevel, maskIndex);
  placeFixedPatterns(matrix);
  return matrix;
}

And we're done! 🙌

And if you're wondering, yes, the above function returns a working QR Code! (At least for our case.)

Whoa, this part has been long! It didn't expect it. So I'll leave the mask optimization steps to the next part. See ya! 👋

Comments

[龔宏裕]

Great tutorial! I have a little question. The Timing Pattern in function placeFixedPatterns, and in function getRawQRCode in pervious part IV.

// Part V function placeFixedPatterns
for (let pos = 8; pos < size - 9; pos += 2) {
    matrix[6][pos] = 1;
    matrix[6][pos + 1] = 0;
    matrix[pos][6] = 1;
    matrix[pos + 1][6] = 0;
}
matrix[6][size - 7] = 1;
matrix[size - 7][6] = 1;

// Part IV function getRawQRCode
for (let pos = 8; pos < VERSION * 4 + 8; pos += 2) {
    qrCode[6][pos] = 1;
    qrCode[6][pos + 1] = 0;
    qrCode[pos][6] = 1;
    qrCode[pos + 1][6] = 0;
}
qrCode[6][size - 7] = 1;
qrCode[size - 7][6] = 1;

The upperboud of pos is something wrong. By example version = 2 or size = 25, pos loops from 8 to 14. The last matrix[6][16] will miss. And I don't understand the purpose of later 2 lines of code: matrix[6][size - 7] = 1; and matrix[size - 7][6] = 1;. The two modules are part of Finder Pattern, and are already 1. Maybe I can change the upperboud for pos and delete the two lines after for loop?

for (let pos = 8; pos <= size - 9; pos += 2) {
    matrix[6][pos] = 1;
    matrix[6][pos + 1] = 0;
    matrix[pos][6] = 1;
    matrix[pos + 1][6] = 0;
}
//matrix[6][size - 7] = 1;
//matrix[size - 7][6] = 1;

[Massimo Artizzu]

Thank you for your comment!

And I must say... I can't really remember 😅
I can only imagine that would take care of some extra-module that's been set to 0 in the for loop before, but needs to be set to 1 (because part of the alignment patterns), so it's the simplest way I could conceive to ensure they're set to 1. This could happen with different QR code levels.

I agree that for loop could be refactored so it doesn't need this kind of patching, e.g.:

for (let pos = 8; pos <= size - 9; pos += 1) {
    const state = (pos + 1) % 2;
    matrix[6][pos] = state;
    matrix[pos][6] = state;
}

but maybe it's not much clearer. What do you think? (Warning: I haven't actually tested this code!)

[Chris DeHaan]

The line of alternating timing pattern dots starts and ends with a 1, so this loop does most of the pixels in pairs then adds one more at the end. Your new code that uses <= size - 9 would make a line that's one pixel too long. < size - 9 makes a line that's one pixel too short, so the final 2 lines add one extra "1" pixel.

If you'd like to wrap up the code a little, it could be this:
for (let pos = 8; pos <= size - 9; pos ++) {
matrix[6][pos] = (pos+1)%2; // If pos is even, set to 1
matrix[pos][6] = (pos+1)%2;
}

[Chris DeHaan]

Sorry, I just saw the author's comment doing something similar. Both loops are logically similar.