Let's develop a QR Code Generator, part X: creating larger codes

We're so close! We're just about to create a QR of any of the standard sizes, so nothing will stop us anymore!

But before that…

The version information area

From the previous parts, we still don't know how to fill one of the reserved areas: the version information block. It's a 6×3 (or 3×6, depending on how you place it) rectangle of modules that just reports the size of the QR Code. It's present from version 7 and up, and I guess it's because readers may have it simpler to understand how large the code is.

As I said, it's comprised of 18 modules. The first 6 of them are easy to determine: it's just the version number in binary. For example, for version 26 the first 6 modules/bits will be 011010.

The other 12 are the rest of a polynomial division between the one corresponding to the version in binary multiplied by x¹², and exactly this generator polynomial:

x¹² + x¹¹ + x¹⁰ + x⁹ + x⁸ + x⁵ + x² + 1

… but why this one? Again, it's because it's irreducible an so on. About the dividend, for version 26 we'd have x¹²(x⁴ + x³ + x) = x¹⁶ + x¹⁵ + x¹³.

All of this shouldn't be difficult for our polyRest function:

const VERSION_DIVISOR = new Uint8Array([1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1]);
function getVersionInformation(version) {
  // Using `Uint8Array.from` on a string feels kinda cheating... but it works!
  const poly = Uint8Array.from(version.toString(2).padStart(6, '0') + '000000000000');
  poly.set(polyRest(poly, VERSION_DIVISOR), 6);
  return poly;
}

In the end, we'd get this:

getVersionInformation(26)
// => Uint8Array(18) [0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1]

Like any other cases, it's better to memoize this function, or precompute all the needed results right away.

Placing the bits

We now have the bits to place, we have to know how to place them. As we've said, these areas have to be placed near the upper right and lower left finder patterns, like this:

So let's create a function that does just that, taking a bit matrix as input:

// WARNING: this function *mutates* the given matrix!
function placeVersionModules(matrix) {
  const size = matrix.length;
  const version = (size - 17) >> 2;
  if (version < 7) {
    return;
  }
  getVersionInformation(version).forEach((bit, index) => {
    const row = Math.floor(index / 3);
    const col = index % 3;
    matrix[5 - row][size - 9 - col] = bit;
    matrix[size - 11 + col][row] = bit;
  });
}

Adjusting matrix generation to larger versions

If you remember what we did in part 4, we created some functions to fill the dots of the QR Code's matrix. But they were simplified versions, as they don't support:

• zero or more than one alignment pattern;
• version information areas.

We have to fix those. Let's see how we can do it.

Module sequence

The first one is getModuleSequence, a function that return the sequence of coordinates that have to be filled, in the correct order. To do so, it fills The function is mainly unchanged, except for the first part:

function getModuleSequence(version) {
  const matrix = getNewMatrix(version);
  const size = getSize(version);

  // Finder patterns + divisors
  fillArea(matrix, 0, 0, 9, 9);
  fillArea(matrix, 0, size - 8, 8, 9);
  fillArea(matrix, size - 8, 0, 9, 8);
  // CHANGED PART in order to support multiple alignment patterns
  // Alignment patterns
  const alignmentTracks = getAlignmentCoordinates(version);
  const lastTrack = alignmentTracks.length - 1;
  alignmentTracks.forEach((row, rowIndex) => {
    alignmentTracks.forEach((column, columnIndex) => {
      // Skipping the alignment near the finder patterns
      if (rowIndex === 0 &&
        (columnIndex === 0 || columnIndex === lastTrack)
        || columnIndex === 0 && rowIndex === lastTrack) {
        return;
      }
      fillArea(matrix, row - 2, column - 2, 5, 5);
    });
  });
  // Timing patterns
  fillArea(matrix, 6, 9, version * 4, 1);
  fillArea(matrix, 9, 6, 1, version * 4);
  // Dark module
  matrix[size - 8][8] = 1;
  // ADDED PART
  // Version info
  if (version > 6) {
    fillArea(matrix, 0, size - 11, 3, 6);
    fillArea(matrix, size - 11, 0, 6, 3);
  }

  // ... rest of the function
}

Placing fixed patterns

The next one is placeFixedPatterns from part 5. Similarly to getModuleSequence, we need to support zero or more than one alignment pattern.

We'll focus on the interested lines:

function placeFixedPatterns(matrix) {
  // ...
  // Alignment patterns
  const alignmentTracks = getAlignmentCoordinates(version);
  const lastTrack = alignmentTracks.length - 1;
  alignmentTracks.forEach((row, rowIndex) => {
    alignmentTracks.forEach((column, columnIndex) => {
      // Skipping the alignment near the finder patterns
      if (rowIndex === 0 &&
        (columnIndex === 0 || columnIndex === lastTrack )
        || columnIndex === 0 && rowIndex === lastTrack) {
        return;
      }
      fillArea(matrix, row - 2, column - 2, 5, 5);
      fillArea(matrix, row - 1, column - 1, 3, 3, 0);
      matrix[row][column] = 1;
    });
  });
  // ...
}

Placing the version information bits

This is quite easy, since we already created the placeVersionModules function above. We just need to edit the getMaskedQRCode function (still from part 5) and we're done:

function getMaskedQRCode(version, codewords, errorLevel, maskIndex) {
  const matrix = getMaskedMatrix(version, codewords, maskIndex);
  placeFormatModules(matrix, errorLevel, maskIndex);
  placeFixedPatterns(matrix);
  placeVersionModules(matrix); // NEW LINE
  return matrix;
}

Glueing all together

Using the getCodewords function part 9, and getOptimalMask from part 6, we can write a "final" function getQRCode that just returns the QR Code data we need:

function getQRCode(content, minErrorLevel = 'L') {
  const { codewords, version, errorLevel, encodingMode }
    = getCodewords(content, minErrorLevel);
  const [ qrCode, maskIndex ]
    = getOptimalMask(version, codewords, errorLevel);
  return {
    qrCode,
    version,
    errorLevel,
    encodingMode,
    codewords,
    maskIndex
  };
}

Admire our example in all of its nerdy glory:

And we should be done! We can produce whatever QR Code we want! At last this series is finished, right?!

… right?

Well… mostly yes, but actually no. There's quite a bit of things that could be said about QR Codes, namely:

• multiple encoding modes;
• ECI encoding mode;
• encoding kanji characters… for real, this time;
• data optimization;
• micro QR Codes (yes, they exist);
• reading QR Codes on a browser!

So I'm asking you to keep staying tuned for the next parts! 👋

Comments

[Ashif Khan]

I WANT TO WORK ON THIS KINDA PROJECT. JUST WANTED TO KNOW WHATS THE LEVEL OF SHOULD I KNOW BEFORE JUMPING INTO THIS? CAN ANYONE CONFIRM?