DEV Community

Cover image for Let's develop a QR Code Generator, part V: masking
Massimo Artizzu
Massimo Artizzu

Posted on

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:

A proto-QR code with large drak/light areas highlighted in red scribbles

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 QR Code mask pattern 0 4 QR Code mask pattern 4
1 QR Code mask pattern 1 5 QR Code mask pattern 5
2 QR Code mask pattern 2 6 QR Code mask pattern 6
3 QR Code mask pattern 3 7 QR Code mask pattern 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:

A 25×25 grid with the reserved areas of a version-2 QR code darkened

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,
];
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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);
Enter fullscreen mode Exit fullscreen mode

(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;
Enter fullscreen mode Exit fullscreen mode

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

x10 + x8 + x5 + x4 + x2 + 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);
Enter fullscreen mode Exit fullscreen mode

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]
);
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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

QR Code matrix with the format bits marked with numbers

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)
);
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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)
  );
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

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! πŸ‘‹

Discussion (0)