## DEV Community Massimo Artizzu

Posted on • Updated on

# Let's develop a QR Code Generator, part VI: mask optimization

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

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

``````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×n gets a penalty of 3×(m - 1)×(n - 1).

… 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×2 square of dark/light modules, including overlapping ones. There are 60 of such 2×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:

``````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. Anyway, here are said patterns highlighted in our QR Code: Three patterns, for a penalty of 120.

#### In code

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

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

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

``````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.

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

Finally, let's compute the penalty score:

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

Since basically `Math.trunc = x => x > 0 ? Math.floor(x) : Math.ceil(x)` (MDN, we can come up with a more compact formula like this:

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

``````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;

}
``````

### Total penalty score

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

``````function getOptimalMask(version, codewords, errorLevel) {
let bestMatrix;
let bestScore = Infinity;
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;
}
}
}
``````

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: 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. 