## DEV Community is a community of 787,625 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

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:

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!).

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:

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!

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;
});
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[3] = (maskIndex >> 1) & 1;
``````

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

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]);
(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]);
const formatPoly = new Uint8Array(15);
const errorLevelIndex = EDC_ORDER.indexOf(errorLevel);
formatPoly[0] = errorLevelIndex >> 1;
formatPoly[1] = errorLevelIndex & 1;
formatPoly[3] = (maskIndex >> 1) & 1;
const rest = polyRest(formatPoly, FORMAT_DIVISOR);
formatPoly.set(rest, 5);
(bit, index) => bit ^ FORMAT_MASK[index]
);
}
``````

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);
(cell, index) => (matrix[matrix.length - index - 1][8] = cell)
);
(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!
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) {