Let's develop a QR Code Generator, part VI: mask optimization
Tags: javascript, tutorial, qrcode
Published: 2021-08-19 15:02:00

In part 5 we've created our first QR Code. Our code is *not* complete, but rather it's specific to our case (version 2, byte mode) and we've applied a fixed mask, violating the specification that tell us to choose *the best* mask among the predefined 8.

Anyway, this is the result:

![Our QR code with mask #0 applied](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1ejrzz968xryxpiyqnpz.png)

In order to choose the best mask, we need to compute the **penalty score** that we get from each one, and select the mask with the lowest score. The penalty score is the sum of the penalties obtained using 4 rules, as follows.

### Rule 1

The first rule says that **each sequence of 5 or more consecutive dark/light modules in a row or column gets a penalty of the length of the sequence minus 2**.

This is the penalties for the QR Code above *just for the horizontal sequences*:

![Counting rule 1 penalties for horizontal sequences](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3btp500gyp21m0658ur8.png)

It sums up to 102. When adding up the penalties for *vertical* sequences, we should get 138 more, for a total score of 240 for rule 1.

#### In code

Let's start with a pretty straightforward helper function to compute the penalty in a certain sequence of modules according to rule 1:

```js
function getLinePenalty(line) {
  let count = 0;
  let counting = 0; // To keep trick of which modules we're counting
  let penalty = 0;
  for (const cell of line) {
    if (cell !== counting) {
      counting = cell;
      count = 1;
    } else {
      count++;
      if (count === 5) {
        penalty += 3;
      } else if (count > 5) {
        penalty++;
      }
    }
  }
  return penalty;
}
```

Now we're going to use it to compute the total penalty score of rows and columns (remember that `matrix` is supposed to be an array of `Uint8Array`s containing either `0` or `1` - our QR Code):

```js
let totalPenalty = 0;

const rowPenalty = matrix.reduce((sum, row) => sum + getLinePenalty(row), 0);
totalPenalty += rowPenalty;

const columnPenalty = matrix.reduce((sum, _, columnIndex) => {
  const column = matrix.map(row => row[columnIndex]);
  return sum + getLinePenalty(column);
}, 0);
totalPenalty += columnPenalty;
```

### Rule 2

The second rule says that **each rectangular region of dark/light modules of size *m*&times;*n* gets a penalty of 3&times;(*m* - 1)&times;(*n* - 1)**.

&hellip; ok. But *how* should we identify such rectangles, if there are several ways to split a certain area?

Fortunately, we have an equivalent strategy: just **add a penalty of 3 for each 2&times;2 square of dark/light modules, *including* overlapping ones**.

![Our QR code with 2x2 solid areas highlighted](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/bp9r41fc07qdf4ky2lkm.png)

There are 60 of such 2&times;2 squares in the picture above, for a total penalty score of 180.

#### In code

This rule is quite simple: all you have to do is checking if three adjacent modules are equal to the current one:

```js
let blocks = 0;
const size = matrix.length
for (let row = 0; row < size - 1; row++) {
  for (let column = 0; column < size - 1; column++) {
    const module = matrix[row][column];
    if (
      matrix[row][column + 1] === module &&
      matrix[row + 1][column] === module &&
      matrix[row + 1][column + 1] === module
    ) {
      blocks++;
    }
  }
}
totalPenalty += blocks * 3;
```

### Rule 3

The third rules says that **each sequence of *dark-light-dark-dark-dark-light-dark-light-light-light-light* modules (⬛⬜⬛⬛⬛⬜⬛⬜⬜⬜⬜) or its reverse (⬜⬜⬜⬜⬛⬜⬛⬛⬛⬜⬛), found on any row or column, adds a penalty of 40**.

![Meme of Ryan Reynolds saying 'But why?'](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/cn9ftngrjmavfzw03nx4.gif)

~~**I have no idea!** Seriously, if someone has any info about this, please speak up!~~ As user @latestversion points out in the comments, the reason can be found in section 7.8.1 of the QR Code ISO 18004 specification:

> The module pattern 1011101 particularly found in the finder pattern should be avoided in other areas of the symbol as much as possible.

Anyway, here are said patterns highlighted in our QR Code:

![Our QR Code with rule 3 patterns highlighted](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/n8fd5jfhjpv4gqqnb6xn.png)

Four patterns, for a penalty of 160.

#### In code

First of all, let's put those sequences in constants:

```js
const RULE_3_PATTERN = new Uint8Array([1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0]);
const RULE_3_REVERSED_PATTERN = RULE_3_PATTERN.slice().reverse();
```

Then, for each row and column, let's check how many times they contain the pattern or its reverse:

```js
let patterns = 0;
for (let index = 0; index < size; index++) {
  // Checking the rows...
  const row = matrix[index];
  for (let columnIndex = 0; columnIndex < size - 11; columnIndex++) {
    if ([RULE_3_PATTERN, RULE_3_REVERSED_PATTERN].some(
      pattern => pattern.every(
        (cell, ptr) => cell === row[columnIndex + ptr]
      )
    )) {
      patterns++;
    }
  }
  // Checking the columns...
  for (let rowIndex = 0; rowIndex < size - 11; rowIndex++) {
    if ([RULE_3_PATTERN, RULE_3_REVERSED_PATTERN].some(
      pattern => pattern.every(
        (cell, ptr) => cell === matrix[rowIndex + ptr][index]
      )
    )) {
      patterns++;
    }
  }
}
totalPenalty += patterns * 40;
```

### Rule 4

Rule 4 is mostly computational. Follow these steps:

1. compute the percentage of dark modules;
2. if the percentage is greater than 50, round down to the nearest multiple of 5; otherwise, round it up;
3. subtract 50 and double the absolute value of the difference: that's our penalty for rule 4.

In our case, 50.4% of the modules (315 out of 625) are dark, so we round down to 50, subtract 50 and double the difference: it's 0.

If we had, for example, a percentage of 42%, we'd have rounded up to 45%, then get a penalty of 10. For 67%, we'd round down to 65% and get a penalty of 30.

Note that you can actually make the computation based on the *light* modules instead of the dark: it's the same thing, if you check the formula.

#### In code

First, let's compute the amount of dark (or light) modules:

```js
const totalModules = size * size;
const darkModules = matrix.reduce(
  (sum, line) => sum + line.reduce(
    (lineSum, cell) => lineSum + cell
  , 0)
, 0);
const percentage = darkModules * 100 / totalModules;
```

In order to round down to the nearest multiple of *n*, we divide by *n*, round down to the nearest integer and multiply back by *n*. It's similar when rounding up.

```js
const roundedPercentage = percentage > 50
  ? Math.floor(percentage / 5) * 5
  : Math.ceil(percentage / 5) * 5;
```

Finally, let's compute the penalty score:

```js
const mixPenalty = Math.abs(roundedPercentage - 50) * 2;
totalPenalty += maxPenalty;
```

Since basically `Math.trunc = x => x > 0 ? Math.floor(x) : Math.ceil(x)` ([MDN](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/trunc), we can come up with a more compact formula like this:

```js
const mixPenalty = Math.abs(Math.trunc(percentage / 5 - 10)) * 10;
```

### The complete penalty score function

Let's gather all the code above in a single function:

```js
const RULE_3_PATTERN = new Uint8Array([1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0]);
const RULE_3_REVERSED_PATTERN = RULE_3_PATTERN.slice().reverse();

function getLinePenalty(line) {
  let count = 0;
  let counting = 0;
  let penalty = 0;
  for (const cell of line) {
    if (cell !== counting) {
      counting = cell;
      count = 1;
    } else {
      count++;
      if (count === 5) {
        penalty += 3;
      } else if (count > 5) {
        penalty++;
      }
    }
  }
  return penalty;
}

function getPenaltyScore(matrix) {
  let totalPenalty = 0;

  // Rule 1
  const rowPenalty = matrix.reduce(
    (sum, row) => sum + getLinePenalty(row)
  , 0);
  totalPenalty += rowPenalty;

  const columnPenalty = matrix.reduce((sum, _, columnIndex) => {
    const column = matrix.map(row => row[columnIndex]);
    return sum + getLinePenalty(column);
  }, 0);
  totalPenalty += columnPenalty;

  // Rule 2
  let blocks = 0;
  const size = matrix.length
  for (let row = 0; row < size - 1; row++) {
    for (let column = 0; column < size - 1; column++) {
      const module = matrix[row][column];
      if (
        matrix[row][column + 1] === module &&
        matrix[row + 1][column] === module &&
        matrix[row + 1][column + 1] === module
      ) {
        blocks++;
      }
    }
  }
  totalPenalty += blocks * 3;

  // Rule 3
  let patterns = 0;
  for (let index = 0; index < size; index++) {
    const row = matrix[index];
    for (let columnIndex = 0; columnIndex < size - 11; columnIndex++) {
      if ([RULE_3_PATTERN, RULE_3_REVERSED_PATTERN].some(
        pattern => pattern.every(
          (cell, ptr) => cell === row[columnIndex + ptr]
        )
      )) {
        patterns++;
      }
    }
    for (let rowIndex = 0; rowIndex < size - 11; rowIndex++) {
      if ([RULE_3_PATTERN, RULE_3_REVERSED_PATTERN].some(
        pattern => pattern.every(
          (cell, ptr) => cell === matrix[rowIndex + ptr][index]
        )
      )) {
        patterns++;
      }
    }
  }
  totalPenalty += patterns * 40;

  // Rule 4
  const totalModules = size * size;
  const darkModules = matrix.reduce(
    (sum, line) => sum + line.reduce(
      (lineSum, cell) => lineSum + cell
    , 0)
  , 0);
  const percentage = darkModules * 100 / totalModules;
  const mixPenalty = Math.abs(Math.trunc(percentage / 5 - 10)) * 10;

  return totalPenalty + mixPenalty;
}
```

### Total penalty score

The total penalty score in our case is therefore 240 + 180 + 160 + 0 = 580. New we need to find which mask yields the lowest penaly, and this function should do the trick:

```js
function getOptimalMask(version, codewords, errorLevel) {
  let bestMatrix;
  let bestScore = Infinity;
  let bestMask = -1;
  for (let index = 0; index < 8; index++) {
    const matrix = getMaskedQRCode(version, codewords, errorLevel, index);
    const penaltyScore = getPenaltyScore(matrix);
    if (penaltyScore < bestScore) {
      bestScore = penaltyScore;
      bestMatrix = matrix;
      bestMask = index;
    }
  }
  return [bestMatrix, bestMask];
}
```

The other masks yield a penalty score of, respectively, 495, 415, 575, 597, 579, 472, 779. So the best mask to apply is #2, with this final result:

![Our final QR Code, with mask #2 applied](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/t3o0ia30gcjr0t6a3sa8.png)

And that's it! We finally have our final QR Code 🎉. But still, we assumed quite some things and cut corners in order to reach a result as soon as possible (and still needed 5-6 parts anyway!):

* the content is a plain Latin-1 encoded string;
* the length of the content fits in a smaller QR Code;
* no need to split the data in multiple code blocks.

In the next parts, we're going to solve these issue, so we can actually develop a fully functional QR Code generator.