Let's develop a QR Code Generator, part V: masking
Tags: javascript, tutorial, qrcode
Published: 2021-08-14 21:40:41

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

If you remember the final result from [the previous part](https://dev.to/maxart2501/let-s-develop-a-qr-code-generator-part-iv-placing-bits-3mn1), 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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/zitonx2dc4d6acq4ylnm.png)

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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1fuaiompxtuqnlx4yr9q.png) | 4 | ![QR Code mask pattern 4](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/utattadjqt95j23k41w2.png)
1 | ![QR Code mask pattern 1](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/q9hyorq85q30vw91zxne.png) | 5 | ![QR Code mask pattern 5](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/f1940tsgt97vax23ll2o.png)
2 | ![QR Code mask pattern 2](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jlv17xxy4nbzn4pdmt6c.png) | 6 | ![QR Code mask pattern 6](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/chq45hl6xyxm2jhu6xdv.png)
3 | ![QR Code mask pattern 3](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/68ly8pla4exfjala1lox.png) | 7 | ![QR Code mask pattern 7](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/n8jadzsiu9m7ac2xc7un.png)

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&times;25 grid with the reserved areas of a version-2 QR code darkened](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/l8dp1p0njtava3aie56c.png)

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:

```js
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](https://dev.to/maxart2501/let-s-develop-a-qr-code-generator-part-iv-placing-bits-3mn1#the-code), 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):

```js
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:

```js
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):

```js
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*<sup>10</sup> + *x*<sup>8</sup> + *x*<sup>5</sup> + *x*<sup>4</sup> + *x*<sup>2</sup> + *x* + 1

Why this exact polynomial? Because it's irreducible blah blah&hellip; the usual shenanigans we've seen in [part 3](https://dev.to/maxart2501/let-s-develop-a-qr-code-generator-part-iii-error-correction-1kbm) 😅

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

```js
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 🤷‍♂️):

```js
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:

```js
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):

![QR Code matrix with the format bits marked with numbers](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/pl5z9fc39q40zh1dmdhp.png)

And the following code should do it:

```js
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](https://dev.to/maxart2501/let-s-develop-a-qr-code-generator-part-iv-placing-bits-3mn1#the-code) to have a function that just fills the fixed areas:

```js
// 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:

```js
// 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:

```js
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! 👋