DEV Community: Massimo Artizzu

Shadow DOM makes perfect sense

Massimo Artizzu — Fri, 18 Apr 2025 16:07:34 +0000

(Cover: illusion installation by Daihei Shibata)

When it comes to Web Components, I think one of the main reasons why there's not more widely adopted is caused by the lack of (good) communication that led the specification editors to develop a standard the way it's been developed, and the userland community. As a result, there are a lot of misconceptions about the reasons, the goals and the use cases that Web Components want to cover.

Even experienced developers and menthors could fall in the same trap, as we'll see later.

One of the most misunderstood pieces is definitely the Shadow DOM. This feature recreates a custom DOM structure entirely contained inside our component, possibly completely different from the one we'd expect from the nodes we inserted as descendants.

What comes with the Shadow DOM

This jarring behavior is also just a part of what Shadow DOM implies: it is, in fact, the heart of the encapsulation capabilities of Web Components. It also means the following:

Stylesheets defined inside the Shadow DOM can only affect elements inside the Shadow DOM; viceversa, stylesheets outside do not have effect on elements inside the Shadow DOM - except for some well-defined ways that allow to fine-tune this kind of style spilling.
Many DOM-selection and traversing API are blocked by shadow roots, e.g. document.querySelector('button') cannot return a button placed inside a Shadow DOM. This includes ARIA cross-root references, which could have an impact on accessibility.
Events can now be composed, which is necessary if you want them to escape the boundaries of the shadow root.
When replacing the descendant nodes with its own DOM structure, it's possible to reassign the custom element's children to a special element called <slot>, either declaratively or imperatively.

Shadow DOMs behave like a miniature DOM nested inside our custom elements and, as such, they pose coding challenges that could reward us with features that could be hardly achievable otherwise.

Shadow DOM is not for everything

So, why should we use a Shadow DOM inside our Web Components? Why should we torture ourselves with those challenges? We want our job as simple as possible, right?

Let's start saying that nobody says we should always use a Shadow DOM. We don't always need this level of encapsulation. But when we do, in my opinion it's a great solution.

For example, if I want to define an UI Kit for my/my company/third party applications, I'd like to have a consistent layout and appearance. I want its colors, its spacings, its decorative features to be fixed. I want their pieces and bits always be present in the places I intended them to be (its internal layout). And when I allow some external customization, I'd like to limit the impacts consumers may have. Otherwise, I'd allow consumers to break the underlying design system.

For example, imagine you want to create a classic "collapsible card" component <my-card>, and suppose you don't want to use the Shadow DOM. Your card is going to have its own internal structure, so the first thing you could do is to manipulate the DOM via JavaScript in order to move around child nodes. When should we perform this operation? When the elements is attached to the page? When it first receives its children? What if the content is modified from external factors after that? How would you reconcile the changes with the component's intended structure?

UI Kits are probably the best example why we'd want some higher level of encapsulations. But that's not the end of it: encapsulation could be used also for some widely used components, like a checkout widget, or a cookie consent banner. I've used it for wrapping branches of legacy applications while migrating to another framework/newer version.

What about the rest? Would I always use a Shadow DOM when developing a full application with Web Components? Probably not. Because I wouldn't need strong encapsulation everywhere: it'd create unnecessary hurdles for little or no result. It's no use to define a shadow DOM for a component that comprise a whole page, for example.

So, what's the fuss about?

Those points are summarily examined in Chris Ferdinandi's article "The Shadow DOM is an antipattern" that was published last June 28th. In the article, Chris minimizes the advantages of Shadow DOMs and reduces the mentioned challenges as "disadvantages", concluding that using Shadow DOM is actually an "antipattern" that creates more problems that it solves.

But, as I said, I think he fell victim of the misconceptions I mentioned before. Let's see what I mean in particular:

[The Shadow DOM] prevents your global CSS from cascading into your Web Component HTML. This makes consistent styling significantly harder and more verbose.

This surprised me right off the bat, because preventing the cascade is exactly the goal of style encapsulation. You may want to encapsulate the styles to your component.

It's also unclear how that'd make "consistent styling significantly harder and more verbose". Let's remember that you absolutely can include more than one stylesheet in the Shadow DOM, so you can define a "global" list of core style rules that you can include in every component with a shadow root. So yeah, you can use your utility class .uppercase inside a Shadow DOM if you want to.

Second: when I said that external stylesheets don't affect the Shadow DOM, it's not completely true. In fact, all inherited CSS properties are passed through the shadow root. It's not like your shadow text will appear in Times New Roman in case of a missing definition inside, because font-family is indeed an inherited CSS property.

Other inherited properties are usually text-related, like font-size and color, but also visibility is inherited. And, above all, custom properties are normally inherited, allowing us to define a list of special properties that represent the set of design properties and values that can be shared among our components and even altered if needed. This is what's called a design token.

It (currently) requires you to generate your HTML with JavaScript. Declarative Shadow DOM is a newer feature that will fix this once better supported.

I have to underline that Declarative Shadow DOM is actually supported by all the major browsers (and can even be polyfilled), but even if we accept that it needs to be "better supported", the former statement is also misleading.

You can, in fact, limit yourself to grab a piece of (light) DOM, copy it (eventually) and attach it to your shadow root. Sure, you need to do that with JavaScript, but it can be as little as a single line. And lo, there's even a specific element for this exact case, which is also as old as the concept of "Web Components": the good ol' <template> element, which is the base for Declarative Shadow DOM and the key for its polyfill, allowing us to just write:

this.shadowRoot.append(
  document.querySelector('#tpl').content.cloneNode(true)
);

You can saying that I'm sort of "playing with words", but since we do have access to the document, saying that we're "required" to use JavaScript to create HTML is flat-out incorrect.

From that point, I won't mention dynamic content, because light and Shadow DOM are clearly on par with this.

The encapsulation it provides also makes extending and customizing the code harder unless you build in lots of developer hooks.

That's probably my limitation, but I see little problem here. I just suppose he's not referring to "extending" in the OOP sense, as in:

const LibButton = customElements.get('lib-button');
class MyButton extends LibButton { ... }
customElements.define('my-button', MyButton);

because you can do that, although it's probably not the best thing to work with. Also because you cannot do that with native elements, e.g. class MyButton extends HTMLButtonElement {...}, unless you want to drop support for Safari. Native elements also are the "most closed" thing you could use to create an extension from.

That being said, why would you want to extend a custom element? If your goal is to be able to completely dismantle its layout and functionality... Well, you're not probably creating a UI Kit or other stuff that needs strong encapsulation anyway. So the point is moot.

Can you actually achieve “good enough” versions of the benefits without the Shadow DOM?

The question is followed by an interesting point:

The custom elements you use to create your Web Component provide a styling hook that can scope your styles to just the Web Component.
accordion-group button {
    /* Button styles just for this component */
}

I think I'm decently versed when it comes to CSS, and I applaud the people who show no fear of the cascade. But beware of the code above: because the accordion-group selector gives us an upper bound for our scope, but not a lower bound. This means that any button inside the accordion-group will be affected by the rule, even those that are not supposed to be part of the intrinsic structure of the element, but rather of its content.

Today, there's actually a far better solution for this, represented by the new @scope rule that, alas, is still not supported by Firefox (should be soon, though). That supports lower bound for our scopes.

Chris also suggests that:

When you need to deviate, add specificity or scope to an element/class/etc.

This is hardly a decent approach. If you feel the need to "add specificity" to your selectors, you're already on a slippery slope guarded by !important modifiers and several head-scratches. Be very careful when adding specificity. Not everything can be dismissed as

sounds like an issue with how the global stylesheet is designed.

In an encapsulated stylesheet? You don't even need to care: the cascade is much shorter and manageable. I don't even usually use classes in a shadow DOM.

And all in all, Chris' opinion sounds to me like it's limited by his own experience. It's not always a thing to have a handle on the global CSS. For example, I've created several UI kits in my career for many clients. That was just the design token and the components, that's it: my task didn't include developing the applications that used the kit. If I didn't use Shadow DOM, were I to dismiss every style problems that would have emerged with "well, that's a you problem #wontfix"?

Nope. You bet I've used the Shadow DOM: it saved me a lot of headaches.

The most misunderstood element

The post concludes with the following:

And while the <slot> element is really cool and I wish you could use it without the Shadow DOM, you absolutely can do the same thing without it.

It does require you to use the querySelector() method to grab elements, but it’s not anymore work than coding all of your HTML in JavaScript was in the first place.

That, in my opinion, is not a "good enough" version of <slot>. It's a very broken version of it.

Specifically, it doesn't react to changes to the set of children elements: it does its job once, and that's it. If you need to update the content of your custom element with new data, you're out of luck.

Sadly, Chris just doesn't explain how to deal with it. My naive assumption is that you either stay stuck with a broken look-alike, or if you try to recreate native slots using e.g. a MutationObserver, in the end, you'd be using more JavaScript. This is pretty surprising coming from someone so hostile to JavaScript.

And an anti-pattern to me.

Why we create "components" in the first place

The main goal to create a component is to have a reusable piece of markup that saves us to do the same things over and over again. But then you see his ideal usage of "Web Components":

<ajax-form>
  <form method="post" action="/subscribe">
    <label for="email">Add your email to join the newsletter</label>
    <input type="email" id="email" name="email">
    <button>Join</button>
  </form>
</ajax-form>

This way, even if JavaScript is disabled, the form still works. Sure. But the cost is I saved almost nothing from my usual code grinding tasks.

The interesting part is that he apparently created this for NASA. I doubt NASA employees would complain if they can't turn JavaScript off, but little I know about the requirements. I can only say that, in my experience, it's only something I could be concerned with when building public web sites and apps.

As I've said in the past, relegating JavaScript to just progressive enhancements is narrow minded to me: there are so many patterns we commonly do with JavaScript, and while some of them could be done without it, others definitely cannot.

Accessibility patterns aside, there are multiple cases where you need to handle stuff with JavaScript on the frontend. It may be because you don't control the backend, so you need to elaborate the data on your own. Or because it makes no sense to do something in the backend (an interactive game for kids, for example; or an audio elaboration tool; or scanning a QR code...). Or because something can be generated on the client rather than doing a network round-trip to the server to create the same thing.

Everybody works with constraints. And not everything is a blog.

Dynamic image creation with service workers

Massimo Artizzu — Mon, 11 Nov 2024 18:57:11 +0000

Service workers are a fantastic technology. You may know them in relation to the term Progressive Web Application (PWA), so that something that's normally visible on the browser could be "installed" in the OS, and could be opened like a native application, and disinstalled like a native application, and looks like a native application all around. But service workers can do much more than that.

For accessibility and explanation, look here.

Service workers are basically shared web workers (which exist as a separate technology, by the way) with the special ability to intercept all http requests made by the browser from URLs in the same scope (origin + path) the worker has been registered with. Then, it could be instructed to either respond with a constructed or a cached response - actually preventing the browser to hit the network with the request - or pass the request to the network as normal or by modifying the request (using fetch).

This said, it's clear why service workers are often associated with the ability to access to a web page when offline: the first time you can download and cache all the static resources (which basically "installs" the page), then the service worker can respond to the same requests with the cached versions, basically serving the "application resources" like it was a native app. dev.to is a great example of that.

This is already a simplification, and talking about cache busting, updates and the rest is out of scope for this article, so I won't indulge in that. What I'll talk about is the ability of service workers to serve constructed responses.

Mocking responses

My team was recently tasked to build a "showcase" application, i.e. a web application that basically does nothing, but serves the purpose to show how to use our Web Component UI Kit, following the design system and the coding guide lines.

The application was intended as a purely frontend application (meaning we weren't supposed to develop a backend too), but should look like one the many B2B applications that our customer maintains, with backend and all. That's were the role of a service worker comes in handy.

Now, responding with a textual response is quite simple. Even a JSON is basically text, so in the end our service worker could be something like this:

self.addEventListener('fetch', event => {
  if (event.request.url.includes('/api/hello')) {
    event.respondWith(new Response(
      JSON.stringify({ message: 'Hello!' }),
      { headers: { 'Content-Type': 'application/json' }}
    );
  } else  {
    event.respondWith(fetch(event.request));
  }
});

I won't bore you about how this snippet could be improved. URL matching could use URLPattern. You can load static data with fetch and store them on IndexedDB. You can go nuts with that.

But what about other kind of dynamic responses? Like images?

Generating images: the "easy" way.

The easiest way to generate a dynamic image is to create an SVG, which is basically an XML document. Meaning, it's text. It's a totally feasible task, and you can use libraries like D3.js to generate the SVG elements and paths for you: factories like line() and others returns functions that return what you need to put into the d attribute of <path> elements:

import { pie, arc } from 'd3-shape';

const pieData = pie().sort(null)(data);
const sectorArc = arc().outerRadius(35).innerRadius(20);

const svg = '<svg viewBox="-40 -40 80 80" xmlns="http://www.w3.org/2000/svg">'
  + pieData.map((pie, index) =>
    `<path d="${sectorArc(pie)}" fill="${colors[index]}"/>`
  ).join('')
  + '</svg>';

event.respondWith(new Response(
  svg, { headers: { 'Content-Type': 'image/svg+xml' }}
));

Dynamically generating SVGs could be great to get the task off the main thread - and the result could even be cached. This is great for charts and infographics, and "easy" enough to accomplish.

Generating other image types

What's more tricky is generating a raster image like a PNG or a JPG. "Generation" means using editing instruments to alter a picture or create it from scratch. What we usually do in these cases is using a <canvas> element, getting its 2d context and start painting on it using its many drawing directives.

Problem is, service workers don't have accesso to DOM element. So, are we out of luck?

Worry not, my friends! Because all workers (including service workers) can create OffscreenCanvas objects. Give a width and a height in pixels to the conscructor and there you go, a perfectly fine (although invisible) canvas in a service worker:

const canvas = new OffscreenCanvas(800, 600);
const context = canvas.getContext('2d');

For those wondering: yes, you can get a different type of context, although not all of them are available in every browser. You can try using a library like three.js to generate 3D scenes in a service worker (I think I'll try that later).

Now we can do... whatever, basically. Draw lines, arcs, paths, etc. Even modifying the geometry of our canvas. That's as simple as drawing on a DOM canvas context, so I won't indulge in this part.

Drawing text

We can indeed write text too. This is important because in other environments - namely, a Paint worklet, we cannot do that:

Note: The PaintRenderingContext2D implements a subset of the CanvasRenderingContext2D API. Specifically it doesn’t implement the CanvasImageData, CanvasUserInterface, CanvasText, or CanvasTextDrawingStyles APIs.

But in a service worker, this is all fine. This means that we have a more powerful (although less performant) environment to generate our background images.

Drawing text is as easy as this:

context.fillStyle = '#222';
context.font = '24px serif';
// (x, y) = (50, 90) will be the *bottom left* corner of the text
context.fillText('Hello, world!', 50, 90);

You can use the font you like here, but I've found that usual standard values like sans-serif, monospace or system-ui don't seem to work, as they all fall back to the default serif font. But you can use font stacks as usual:

context.font = '24px Helvetica, Roboto, Arial, Open Sans';

Moreover, you can use the Font Loading API to load fonts from external resources:

const font = new FontFace('Doto', 'url(./fonts/doto.woff2)');
self.fonts.add(font);

self.fonts.ready.then(() => {
  // ...
  context.font = '24px Doto';
});

Sending back to the application

Sending back the response is, again, as easy as calling the convertToBlob method that returns the promise of - you guessed it - a Blob. And blobs can be easily sent back to sender.

const blob = await canvas.convertToBlob({ type: 'image/jpeg' });
event.respondWith(new Response(blob));

The method creates a PNG image by default, but could be instructed to create a JPG file instead, as seen above. 'image/webp' is another common format, but Safari doesn't support it. To be honest, the choice here is a little underwhelming, as newly available and more capable image format decoders aren't reflected in their corresponding encoders. But that's sufficient for most purposes anyway.

Fun fact: the method convertToBlob is specific to the OffscreenCanvas class. HTMLCanvasElements have toBlob instead, which takes a callback as the first argument, in the common pre-Promise era style of asynchronous task handling.

Using a template image

Now, this all works if we want to create a picture from scratch. But what if we want to start from a blank template?

If we were to work in the main thread, we could slap a picture in the context using the drawImage method of our 2D context, sourcing it e.g. from a readily available <img> element.

Problem is, again, that we can't access the DOM, so we can't reference <img> elements. What we can do, instead, it fetching the picture we need as background, getting its Blob and then convert it to something else that drawImage can digest. Enter createImageBitmap, a global method that's available in service workers too. It returns a promise for an ImageBitmap instance, one of the many less-known classes of frontend web development. It's apparently more widely used in WebGL contexts, but drawImage seems to accept it, so...

const templateBlob = await (await (fetch('./img/template.png')).blob();
const template = await self.createImageBitmap(templateBlob);

const canvas = new OffscreenCanvas(template.width, template.height);
const context = canvas.getContext('2d');
context.drawImage(template, 0, 0);

From this point on, we can proceed drawing our scribbles and texts on it, creating a satisfying synamic image to send back to the user.

Note: this could be more easily solved with an SVG, as you could just use a <image> element to set up a background picture. But that would mean the browser has to load the picture after the generated image has been sent, whereas with this technique this is done before. Something similar applies when picking a font.

Putting all together

In all these examples, I've used module service workers (i.e. I've used import from other ES modules). Alas, module service workers aren't yet supported by Firefox, but hopefully they'll be soon. In the meanwhile, you might need to adjust your code to use the old importScripts instead.

When importing other scripts into a service workers, either via import or importScripts, remember that the browser will not fire an updatefound event when an imported file changes: it's fired only when the service worker entry script changes.

In a case like ours, where the service worker is needed only to mock the presence of a backend, its life cycle could be shortcut by calling self.skipWaiting() right when the install event is fired, and then call self.clients.claim() on the activate event in order to be able to immediately respond to requests (otherwise, it'll start only on the next page refresh).

import { getUser } from './users.js';

self.addEventListener('install', () => self.skipWaiting());

self.addEventListener('activate', event => {
  event.waitUntil(self.clients.claim());
});

const pattern = new URLPattern('/api/docs/mock-:id', location.origin);
self.addEventListener('fetch', event => {
  const match = pattern.exec(event.request.url);
  event.respondWith(match
    ? createDocument(match.pathname.groups.id)
    : fetch(event.request)
  );
});

let templatePromise;
let font;
const createDocument = async userId => {
  const user = await getUser(userId);
  if (!user) return new Response(null, { status: 404 });

  if (!templatePromise) {
    templatePromise = fetch('./img/template.png')
      .then(response => response.blob())
      .then(blob => self.createImageBitmap(blob));
  }
  if (!font) {
    font = new FontFace('Doto', 'url(./fonts/doto.woff2)');
    self.fonts.add(font);
    font.load();
  }

  const [ template ] = await Promise.all([
    templatePromise,
    self.fonts.ready
  ]);

  const canvas = new OffscreenCanvas(template.width, template.height);
  const ctx = canvas.getContext('2d');
  ctx.drawImage(template, 0, 0);

  ctx.font = '24px Doto';
  ctx.fillText(`${user.firstName} ${user.lastName}`, 20, 50);

  const blob = await canvas.convertToBlob({ type: 'image/jpeg' });
  return new Response(blob);
};

And this is basically everythin, so... have fun with service workers, folks!

JavaScript is not the problem

Massimo Artizzu — Thu, 16 May 2024 12:27:47 +0000

The other day I was asked to examine a performance issue on an Angular 11 app. Simply typing in an <input> field was very sluggish, and CPU load skyrocketed at 100% from the moment a key is pressed to ~3 seconds after the last is released.

Angular should be the culprit, right? A silly crafted module that caused a loop that gets broken by a "Maximum call stack size exceeded" error or similar.

But the main thread wasn't occupied by script execution. It was a rendering issue.

It turns out that this CSS rule was the cause instead:



.form-control-extra.is-invalid,
.form-control-extra:invalid::placeholder,
.form-control.is-invalid,
.was-validated .form-control-extra:invalid,
.was-validated .form-control:invalid {
  border-color: rgb(43, 239, 117);
  color: rgb(43, 239, 117);
  padding-right: 4px;
  background-image: none;
  background-repeat: no-repeat;
  background-position: right calc(0.1875rem + 0.375em) center;
  background-size: calc(0.375rem + 0.75em) calc(0.375rem + 0.75em);
}

Simply removing it from its stylesheet would iron things out. And that's not even the plot twist! In fact, that rule wasn't even applied on that page!

...

🦗🦗🦗

...

To this day, I still have no idea about the real cause of the problem. It was tested on Chrome only, as it's an app for internal use, and Chrome is the only supported browser. The problem isn't easily reproducible, but I suspect it's a bug on the Blink engine.

My conclusion was to not ship a 200+ KB blanket CSS file with 2000+ rules when only 2% of them are actually used, and partially.

What's this about?

On May 14th, Chris Ferdinandi published his article The wrong way to do Web Components on his blog. Chris is incredibly knowledgeable about web development, and an excellent teacher that gives a lot of great tips.

But indeed he has peculiar ideas about how the web should be developed.

The article above starts with a clarification:

There’s not really a “wrong” way to build Web Components. But there are some approaches that are, in my opinion, antithetical to the spirit of them, and maybe miss the point of what makes them so great.

From my experience, I've always struggled to precisely outline what's the "spirit" of Web Components. Since their original conception in 2011 by Alex Russell, many things have changed. I've used them for the following goals:

building UI Kits (probably their best use case);
creating easily transportable widgets;
wrapping branches of legacy applications;
developing "framework-less" web applications;
encapsulating micro-frontends.

But if Chris has a clearer idea, it's worth listening to him.

The article continues mentioning Web Awesome, the "next iteration" of Shoelace by the same author @claviska Cory LaViska. Then it highlights:

But here’s the problem: Shoelace is not a progressive enhancement library.

... No, it's not indeed. But what is the problem, exactly?

Far too much of the UI renders nothing at all without JavaScript. Other stuff starts out as useless junk.

That <sl-button>? Without JS, it’s just text. You can focus on it. You can’t interact with it. Why do I need JavaScript to render a button!?!

So the problem is... that it uses JavaScript, then?

Of course, a button is one of the basic tiles of the Web. We don't need JavaScript to have a working button. We can very well choose to use native <button>s.

You need some JavaScript if you want that button to:

have a consistent, encapsulated and controlled style;
have a compact, declarative interface like <sl-button loading> to express complex states;
emit custom meaningful events.

(Worth mentioning: Shoelace's buttons could have been a progressive enhancement over native buttons - in the form of <button is="sl-button"> - if built-in extensions were supported in all browsers instead of facing the obstinate opposition from Safari's team, but that's another story.)

Moreover, there are very common UI patterns that require JavaScript to work correctly, at least if you want to follow to WCAG's directions to create accessible components. You might also notice that all WCAG's examples use vanilla HTML, CSS and JavaScript, no frameworks, no libraries whatsoever.

You want tabs? You need JavaScript. You want a combobox? Only with JavaScript. A menu button? JavaScript.

It's great that Chris' blog can work without JavaScript. But he surely had to avoid those patterns. He probably didn't need them anyway, but not every web page is Chris' blog.

Must all the web work without JavaScript?

If we apply that concept, it's clear that we should make without all those patterns, many of which are pretty common to web users. But that's not just that.

Many UI patterns emerged from decades of web UI evolution. Take accordions, for example. Or modal dialogs. Or tooltips. All of them have been implemented with JavaScript libraries for a long time, and only recently new standard elements have been introduced and supported by browsers to reproduce the most common use cases.

The matter here is that, if the whole world developed their web sites and applications in a manner that they could always work without JavaScript, they could have chosen one of the following:

implement new UI patterns, but always providing alternative fallbacks that could work without JavaScript;
forget about new patterns and use the JavaScript-less alternative right away.

I'm inclined to think that most customers would have chosen the second alternative, as it would have meant paying less. This would have meant that those new patterns would have had a much, much harder time emerging, so maybe today we wouldn't even have <dialog> as we have today. And probably not even XHRHttpRequest, let alone fetch. It would have been a completely different web.

Ok, but now we have all we need, right?

Not really. Several patterns still require JavaScript, as there's no native equivalent yet. Think about carousels, for example. Or, yet again, tabbed content. Or tooltips (we may be close to achieve them, thanks to Popover API and Anchor Positioning API).

So, yeah, we probably still need JavaScript. Once the JavaScript usage has been legitimized, the next step is to use it wisely.

With this outcome, flat-out suggesting that everything we do with JavaScript should be progressive enhancement, relegating the role of Web Components as cute wrappers around native elements, sounds frankly narrow minded to me.

What's the fuss about JavaScript anyway?

The JavaScript part of a web page is a something that often blamed for poor site performances. And with a reason, too!

While discussing with Chris on Mastodon, he linked this scheme by Stuart Langridge. It highlights all the possible problems that originates from having some JavaScript in the page.

Most of those points are valid indeed, but also apply to other content: CSS, fonts, images, even the HTML that you have to load right at the start. Depending on the role, the page could end up broken as much.

Some other points are indeed specific to JavaScript and, most of all, are mostly avoidable. Because, after you optimize and lazy-load them you can't take away much more from images and fonts, but there's a lot to be done for JavaScript. It's not rare to download something like 5-6 MB of script behemoths nowadays.

And I'm not saying that most of the code isn't used (even though it very well could be!), just that loading, parsing and running it can be deferred at a later time, when it's actually necessary.

So, what about Shoelace? Does it load a multi-megabyte script for its components? Does it block the main thread while doing so?

Not at all. Shoelace is comprised by several small chunks, the result of a finely grained code splitting. An autoloader loads them only when necessary (it uses a MutationObserver internally), but you can opt for a full-library loaded or even cherry-pick only the components you need. (The full library is ~300 kB compressed with Brotli, by the way.)

In short, Shoelace would be the least of my concerns when it comes to performance issues.

So what are the real concerns?

The usual answer when it comes to development: it depends.

Optimizing static assets is trivial nowadays and fundamental to modern web development. I don't want to see a 3 MB animated .gif when I could do much better with a 60 kB .webm video, thank you.

JavaScript bundles would probably be my next target. There are so many things to look into. Major performance offenders include: analytics libraries, monolithic bundles, lack of code splitting, minification, compression.

I like JavaScript as a language and an ecosystem, but I try to write as little JavaScript as possible, delegating the work to HTML and CSS (when working on the front-end) when possible.

But I'd never dream to impose to use JavaScript for progressive enhancement only. There are applications that far too complex to rely on what HTML and CSS can offer alone, and you don't always have the luxury to dictate the back-end to do everything that's needed.

Moreover, as we've seen at the beginning of this article, the problems could be caused by something completely different and unrelated. But, as much as CSS Naked Day exists, you won't hear many asking that every website should work without CSS either.

(And yes, that would raise accessibility concerns as well.)

In the end: JavaScript, per se, is not the problem. Its excessive use is.

Addendum: on Shadow DOM

The next day, Chris clarified even further w.r.t. Web Components and the Shadow DOM:

[...] the shadow DOM, in my opinion, is an anti-pattern.

It provides little benefit, with lots of cost. It’s harder to work with. It’s harder to style. It can break accessibility, depending on how it’s implemented. It requires JavaScript to work.

The point on accessibility is, unfortunately, correct. The main problem nowadays is cross-root ARIA element referencing, which is currently discussed but still not possible. So everything should be carefully engineered in order to not break accessibility.

But if Chris cares about accessibility, he should alleviate his resentment against JavaScript as well.

Is Shadow DOM harder to work with? Sure. Just like any new API, it brings several new concepts to the table as well, especially when it comes to encapsulation.

You're not forced to use the Shadow DOM, if you don't feel confident. But it's not like it's been conceived on a whim, without any real reason, like Chris seems to suggest.

I also find much easier to style custom elements with a Shadow DOM. It's basically a miniature DOM where the cascade is much more manageable, and I rarely even use classes there. The real challenge, in my experience, is creating a way to permit style variations from the consumer without allowing to mangle the component's layout and overall meaning, which is usually a thing you want e.g. for a design system.

Chris Ferdinandi's approach to Web Components and web development in general is legitimate and based on concrete motivations, which are weighted by his own preferences. On the other hand, his usage of terms like "wrong way" or "anti-pattern" expresses way more than his personal opinions and leans towards unwarranted absolutism.

In short: always take your context and use cases into consideration before rejecting a pattern, library, framework or any other technology.

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

Massimo Artizzu — Tue, 14 Sep 2021 16:12:03 +0000

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[row][size - 11 + 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! 👋

Let's develop a QR Code Generator, part IX: structuring larger versions

Massimo Artizzu — Fri, 10 Sep 2021 16:07:59 +0000

The cover image will make sense later, I swear! 😅

In the last part, we came to know how to split our data and error correction codewords for QR Codes of larger versions. But how can we choose the right version for our content?

QR Code capacity

The answer lies in that big table we've seen. Thanks to that, we can get to know how many codewords are reserved for data for a given version and error correction level and, given the encoding mode, compute the maximum length of the content we can write.

Let's have a look at the columns of that table:

Number of error correction codewords per block
Number of blocks in Group 1
Number of data codewords in blocks of Group 1
Number of blocks in Group 2
Number of data codewords in blocks of Group 2

Let's recall that the data codewords of a QR Code are split into blocks, and each block belong to group 1 or 2 depending on their size. For each data block there's an error correction block.

We also know that:

the value in (5) is just the value in (3) plus 1;
the value in (3) is actually the number of data codewords divided by (2) + (4) (i.e., the total number of blocks), rounded down to the previous integer;
the number of data codewords is the total number of codewords minus the number of error correction codewords;
the number of error correction codewords is (1) multiplied by the number of blocks;
(4) is actually the number of data codewords modulo the number of blocks.

In order to get the total number of codewords, we can use our function getAvailableModules from part 8 and divide the result by 8 (or shift to the right by 3).

In the end, for every version and error level, we just need two values:

the number of error correction codewords per block;
the number of blocks.

In the end, this should be our table:

const EC_TABLE = [
  { L: [7, 1],   M: [10, 1],  Q: [13, 1],  H: [17, 1] },
  { L: [10, 1],  M: [16, 1],  Q: [22, 1],  H: [28, 1] },
  { L: [15, 1],  M: [26, 1],  Q: [18, 2],  H: [22, 2] },
  { L: [20, 1],  M: [18, 2],  Q: [26, 2],  H: [16, 4] },
  { L: [26, 1],  M: [24, 2],  Q: [18, 4],  H: [22, 4] },
  { L: [18, 2],  M: [16, 4],  Q: [24, 4],  H: [28, 4] },
  { L: [20, 2],  M: [18, 4],  Q: [18, 6],  H: [26, 5] },
  { L: [24, 2],  M: [22, 4],  Q: [22, 6],  H: [26, 6] },
  { L: [30, 2],  M: [22, 5],  Q: [20, 8],  H: [24, 8] },
  { L: [18, 4],  M: [26, 5],  Q: [24, 8],  H: [28, 8] },
  { L: [20, 4],  M: [30, 5],  Q: [28, 8],  H: [24, 11] },
  { L: [24, 4],  M: [22, 8],  Q: [26, 10], H: [28, 11] },
  { L: [26, 4],  M: [22, 9],  Q: [24, 12], H: [22, 16] },
  { L: [30, 4],  M: [24, 9],  Q: [20, 16], H: [24, 16] },
  { L: [22, 6],  M: [24, 10], Q: [30, 12], H: [24, 18] },
  { L: [24, 6],  M: [28, 10], Q: [24, 17], H: [30, 16] },
  { L: [28, 6],  M: [28, 11], Q: [28, 16], H: [28, 19] },
  { L: [30, 6],  M: [26, 13], Q: [28, 18], H: [28, 21] },
  { L: [28, 7],  M: [26, 14], Q: [26, 21], H: [26, 25] },
  { L: [28, 8],  M: [26, 16], Q: [30, 20], H: [28, 25] },
  { L: [28, 8],  M: [26, 17], Q: [28, 23], H: [30, 25] },
  { L: [28, 9],  M: [28, 17], Q: [30, 23], H: [24, 34] },
  { L: [30, 9],  M: [28, 18], Q: [30, 25], H: [30, 30] },
  { L: [30, 10], M: [28, 20], Q: [30, 27], H: [30, 32] },
  { L: [26, 12], M: [28, 21], Q: [30, 29], H: [30, 35] },
  { L: [28, 12], M: [28, 23], Q: [28, 34], H: [30, 37] },
  { L: [30, 12], M: [28, 25], Q: [30, 34], H: [30, 40] },
  { L: [30, 13], M: [28, 26], Q: [30, 35], H: [30, 42] },
  { L: [30, 14], M: [28, 28], Q: [30, 38], H: [30, 45] },
  { L: [30, 15], M: [28, 29], Q: [30, 40], H: [30, 48] },
  { L: [30, 16], M: [28, 31], Q: [30, 43], H: [30, 51] },
  { L: [30, 17], M: [28, 33], Q: [30, 45], H: [30, 54] },
  { L: [30, 18], M: [28, 35], Q: [30, 48], H: [30, 57] },
  { L: [30, 19], M: [28, 37], Q: [30, 51], H: [30, 60] },
  { L: [30, 19], M: [28, 38], Q: [30, 53], H: [30, 63] },
  { L: [30, 20], M: [28, 40], Q: [30, 56], H: [30, 66] },
  { L: [30, 21], M: [28, 43], Q: [30, 59], H: [30, 70] },
  { L: [30, 22], M: [28, 45], Q: [30, 62], H: [30, 74] },
  { L: [30, 24], M: [28, 47], Q: [30, 65], H: [30, 77] },
  { L: [30, 25], M: [28, 49], Q: [30, 68], H: [30, 81] }
];

Using this table, we can compute the amount of codewords reserved for data:

function getDataCodewords(version, errorLevel) {
  const totalCodewords = getAvailableModules(version) >> 3;
  const [blocks, ecBlockSize] = EC_TABLE[version - 1][errorLevel];
  return totalCodewords - blocks * ecBlockSize;
}

This is not enough, though, because part of these data codewords are reserved for:

the encoding mode block;
the content length. While the former always take 4 bits/modules, the latter is variable in bit length, so we'll use the function getLengthBits that we've created back in part 2.

In the end we have a certain amount of available bits, but as we've seen in part 7, each encoding mode uses those bits differently.

Let's imagine we have 4 different functions (one for each encoding mode) that, given a certain amount of bits, returns the length of the content that can be cointained in those bits for a certain encoding mode:

const capacityFnMap = {
  [0b0001]: getNumericCapacity,
  [0b0010]: getAlphanumericCapacity,
  [0b0100]: getByteCapacity,
  [0b1000]: getKanjiCapacity
};

We'll end up with something like this:

function getCapacity(version, errorLevel, encodingMode) {
  const dataCodewords = getDataCodewords(version, errorLevel);
  const lengthBits = getLengthBits(encodingMode, version);
  const availableBits = (dataCodewords << 3) - lengthBits - 4;
  return capacityFnMap[encodingMode](availableBits);
}

Again, this is a pure function that we can memoize, but we can also precompute a table that we can use later.

Numeric mode capacity

As we've seen in part 7, we can store 3 digits in 10 bits, two digits in 7 and one digit in 4. Se we need to compute the bits modulo 10 and add the remainder digits at the end:

function getNumericCapacity(availableBits) {
  const remainderBits = availableBits % 10;
  return Math.floor(availableBits / 10) * 3 +
    (remainderBits > 6 ? 2 : remainderBits > 3 ? 1 : 0);
}

Alphanumeric mode capacity

Similarly to numeric mode, we can store two characters in 11 bits and one in 6:

function getAlphanumericCapacity(availableBits) {
  return Math.floor(availableBits / 11) * 2 +
    (availableBits % 11 > 5 ? 1 : 0);
}

Byte mode capacity

This is easy, as 1 character = 8 bits, flat.

function getByteCapacity(availableBits) {
  return availableBits >> 3;
}

Kanji mode capacity

This is also easy, as each pictogram needs 13 bits:

function getKanjiCapacity(availableBits) {
  return Math.floor(availableBits / 13);
}

The best QR Code

Now we've got everything to know which version we must choose for our content: we aim for the smallest version and highest error correction possible. The only additional complexity may come from the fact that we want a certain minimum error correction level.

For example, if we have a 54-digit long number (like the 10th perfect number), we could use a version 2 QR Code with medium error correction (as getCapacity(2, 'M') === 63), but if we want a high correction we have to use version 3 (since getCapacity(3, 'H') === 58).

So we can use something like this:

function getVersionAndErrorLevel(encodingMode, contentLength, minErrorLevel = 'L') {
  // The error levels we're going to consider
  const errorLevels = 'HQML'.slice(0, 'HQML'.indexOf(minErrorLevel) + 1);
  for (let version = 1; version <= 40; version++) {
    // You can iterate over strings in JavaScript 😁
    for (const errorLevel of errorLevels) {
      const capacity = getCapacity(version, errorLevel, encodingMode);
      if (capacity >= contentLength) {
        return [version, errorLevel];
      }
    }
  }
}

If it doesn't return anything, it means the content is too long.

Shuffling the codewords!

Let's suppose we have to encode… a snippet of JavaScript code, for a change:

['give you up','let you down','run around and desert you'].map(x=>'Never gonna '+x)

It's 83 bytes long, but we want a QR Code with quartile error correction at minimum. We get getVersionAndErrorLevel(0b0100, 83, 'Q') === [7, 'Q'], so we're going to need a version 7 QR Code.

We also know that getDataCodewords(7, 'Q') === 88, and we'll have to split these 88 codewords reserved for data into 2 blocks of 14 codewords (group 1), then other 4 blocks of 15 codewords each (group 2). Using the getData function from the last part, we get:

> getData(snippet, 8, 88)
< Uint8Array(88) [69, 53, 178, 118, 118, 151, 102, 82, 7, 150, 247, 82, 7, 87, 2, 114, 194, 118, 198, 87, 66, 7, 150, 247, 82, 6, 70, 247, 118, 226, 114, 194, 119, 39, 86, 226, 6, 23, 38, 247, 86, 230, 66, 6, 22, 230, 66, 6, 70, 87, 54, 87, 39, 66, 7, 150, 247, 82, 117, 210, 230, 214, 23, 2, 135, 131, 211, 226, 116, 230, 87, 102, 87, 34, 6, 118, 246, 230, 230, 18, 2, 114, 183, 130, 144, 236, 17, 236]

These codewords should be split like this (hex values):

Block	Bytes
G1-B1	`45 35 B2 76 76 97 66 52 07 96 F7 52 07 57`
G1-B2	`02 72 C2 76 C6 57 42 07 96 F7 52 06 46 F7`
G2-B1	`76 E2 72 C2 77 27 56 E2 06 17 26 F7 56 E6 42`
G2-B2	`06 16 E6 42 06 46 57 36 57 27 42 07 96 F7 52`
G2-B3	`75 D2 E6 D6 17 02 87 83 D3 E2 74 E6 57 66 57`
G2-B4	`22 06 76 F6 E6 E6 12 02 72 B7 82 90 EC 11 EC`

Now, instead of placing them one after the other, we take the first codewords from each block (first from group 1, then group 2), then the second codewords, and so on, until the 15th codewords, which are followed by the 16th codewords of the blocks of group 2. In short, we need to interleave the blocks. In the end, we'll end up with this sequence:

45 02 76 06 75 22 35 72 ... 57 EC 57 F7 E6 F7 66 11 42 52 57 EC

In code

We can either modify getData, or keep it as it as but we'll need another helper function to reorder the codewords we got. This function should take:

the codewords returned from getData;
the number of blocks we should use to split the data.

Something like this:

function reorderData(data, blocks) {
  /** Codewords in data blocks (in group 1) */
  const blockSize = Math.floor(data.length / blocks);
  /** Blocks in group 1 */
  const group1 = blocks - data.length % blocks;
  /** Starting index of each block inside `data` */
  const blockStartIndexes = Array.from(
    { length: blocks },
    (_, index) => index < group1
      ? blockSize * index
      : (blockSize + 1) * index - group1
  );
  return Uint8Array.from(data, (_, index) => {
    /** Index of the codeword inside the block */
    const blockOffset = Math.floor(index / blocks);
    /** Index of the block to take the codeword from
      If we're at the end (`blockOffset === blockSize`), then we take
      only from the blocks of group 2 */
    const blockIndex = (index % blocks)
      + (blockOffset === blockSize ? group1 : 0);
    /** Index of the codeword inside `data` */
    const codewordIndex = blockStartIndexes[blockIndex] + blockOffset;
    return data[codewordIndex];
  });
}

This function is supposed to be used like this:

const rawData = getData(snippet, 8, 88);
const orderedData = reorderData(rawData, 6);

Error correction

The error correction part is similar to the data part, in that also error correction codewords are split into blocks. It's just a little easier because all the error correction blocks have the same size.

So, for a 7-Q QR Code, the table above says we have 18 codewords for each error correction block. These blocks are computed using the respective data block. So, the first error correction block is comprised by the error correction codewords for the codewords of the first data block of group 1. Basically, it's this:

const rawData = getData(snippet, 8, 88);
const firstBlock = rawData.subarray(0, 14);
// => 69 53 178 118 118 151 102 82 7 150 247 82 7 87
const firstECBlock = getEDC(firstBlock, 14 + 18);
// => 63 102 26 192 65 106 117 90 107 88 138 42 103 127 227 86 189 1

The final part consists in interleaving the error correction blocks, and we're done.

In code

Given the instruction above, we can come up with the following helper function that wraps and replaces the old getEDC:

function getECData(data, blocks, ecBlockSize) {
  /** Codewords in data blocks (in group 1) */
  const dataBlockSize = Math.floor(data.length / blocks);
  /** Blocks in group 1 */
  const group1 = blocks - data.length % blocks;
  const ecData = new Uint8Array(ecBlockSize * blocks);
  for (let offset = 0; offset < blocks; offset++) {
    const start = offset < group1
      ? dataBlockSize * offset
      : (dataBlockSize + 1) * offset - group1;
    const end = start + dataBlockSize + (offset < group1 ? 0 : 1);
    const dataBlock = data.subarray(start, end);
    const ecCodewords = getEDC(dataBlock, dataBlock.length + ecBlockSize);
    // Interleaving the EC codewords: we place one every `blocks`
    ecCodewords.forEach((codeword, index) => {
      ecData[index * blocks + offset] = codeword;
    });
  }
  return ecData;
}

For our example, we should get the following result:

const rawData = getData(snippet, 8, 88);
const ecData = getECData(rawData, 6, 18);
// => 63 55 231 201 50 250 102 104 ... 7 15 1 181 202 64 199 23

for a total of 6*18 = 108 error correction codewords.

Wrapping everything up

So we have all that we need for data and error correction:

function getCodewords(content, minErrorLevel = 'L') {
  const encodingMode = getEncodingMode(content);
  const [version, errorLevel] = getVersionAndErrorLevel(
    encodingMode,
    content.length,
    minErrorLevel
  );
  const lengthBits = getLengthBits(encodingMode, version);

  const dataCodewords = getDataCodewords(version, errorLevel);
  const [ecBlockSize, blocks] = EC_TABLE[version - 1][errorLevel];

  const rawData = getData(content, lengthBits, dataCodewords);
  const data = reorderData(rawData, blocks);
  const ecData = getECData(rawData, blocks, ecBlockSize);

  const codewords = new Uint8Array(data.length + ecData.length);
  codewords.set(data, 0);
  codewords.set(ecData, data.length);

  return {
    codewords,
    version,
    errorLevel,
    encodingMode
  };
}

The function above should return the codewords - both data and error correction - ready to be placed in our QR Code! 🙌

And we're… not done?

Unfortunately there's still a small step to do, and we're going to see it in the next part. We have to fix the functions that return the sequence of module placements in the matrix and that actually place the modules, then also add the format information areas.

See you then and happy coding! 👋🎉

Let's develop a QR Code Generator, part VIII: different sizes

Massimo Artizzu — Sat, 04 Sep 2021 22:10:55 +0000

At this point in the series, we know how to creare a QR Code with numeric, alphanumeric, ISO-8859-1 or Kanji data. But we've created only version 2 QR Codes, meaning that our content is quite limited in size. So let's see how to overcome this.

As we've said in part 1, the version of the code gives its size, as the code matrix will be a square of 17 + version * 4 modules. Part of this square is occupied by either fixed patterns, or reserved space for format information.

Let's have a look at what we're talking about:

So we have:

three finder patterns (in green), as 8×8 module patterns (including separator lines): these are fixed;
alignment patterns (in blue), 5×5 module patterns that vary in number (they are n² - 3, where n depends on the version);
timing patterns (in red): lines that connect the finder patterns, and as such their length depends on the QR Code version;
a dark module (in olive, fixed);
error level and mask information (in purple): two 15-module sequences (fixed);
version format information (in orange); two 6×3 areas adjacent to the top right and bottom left finder patterns (fixed, but present only from version 7 and above).

The content of last two areas have to be generated, but we don't know how to do it for the second one yet (we'll see that later). The main point of variability is the number of alignment patterns in the matrix.

Placing the alignment patterns

As we said, there are n² - 3 alignment patterns in a QR Code, except for version 1 that has no such patterns. The -3 part is because they'd be placed over the finder patterns, as you can see in the figure above. But how do we know this n?

Basically, if v is the version number, it's n = floor(v / 7) + 2, so versions 2 to 6 have 2² - 3 = 1 alignment patterns, versions 7-13 have 3² - 3 = 6, versions 14-20 have 4² - 3 = 13 and so on.

Now the question is: how do we place them in the QR Code's matrix?

As we can realize from the previous figure, they are placed on the vertexes of a grid, and this grid is symmetrical relatively to its main diagonal. This means we only need to know the position of one set of its tracks (either the rows or the columns).

For example, a version 2 QR Code has its alignment patterns on tracks 6 and 18 (nevermind we can only see one); while a version 7 has them on tracks 6, 22 and 38. These values are 0-based (the first row and column have index 0), and refer to the center of the pattern.

Here's the algorithm:

the first track is always 6;
the last track is always 6 from the end;
for the tracks in the middle, do the following:
- get the difference between the last and the first tracks above, then divide by n - 1;
- take the even number greater or equal to the quotient above;
- place the middle tracks counting from the last one.

We need to take an even number because, as you might see from the figure from before, the alignment patterns must match the timing patterns, i.e. you can't have an alignment pattern placed on an odd row/column.

Example: for version 22, n is Math.floor(22 / 7) + 2, so it's 5. A version 22 QR Code is 17 + 22 * 4 = 105 modules wide, so the fifth and last track is 98. For the other two:

the difference between the last and first track is 92;
92 / 4 = 23, so the next even number is 24;
therefore, the fourth track is 98 - 24 = 74, the third is 74 - 24 = 50 and the second is 50 - 24 = 26.

In code

The following function basically executes the above steps:



function getAlignmentTracks(version) {
  if (version === 1) {
    return [];
  }
  const intervals = Math.floor(version / 7) + 1;
  const distance = 4 * version + 4; // between first and last pattern
  const step = Math.ceil(distance / intervals / 2) * 2;
  return [6].concat(Array.from(
    { length: intervals },
    (_, index) => distance + 6 - (intervals - 1 - index) * step)
  );
}

Note that the pure function above should be used with just 40 different values, so we can safely memoize it, or precompute all the values beforehand and store them in a constant array. Or even copy a table from around the web (e.g. this well known library).

How many codewords?

Once the alignment pattern matter is solved, we can get to know how much actual space there is in a QR Code, i.e. codewords that can be used to store data and error correction information.

As we've said, version 1 has no alignment pattern, so the amount of available modules is:

21² (441, where 21 is the size of the QR Code)
- 3⋅8⋅8 (192, for 3 finder patterns)
- 2⋅5 (10, the timing patterns)
- 1 (the dark module)
- 2⋅15 (30, the error level and mask information)

for a total of 208, i.e. 26 codewords.

For larger versions, we have to compute this (let v the version number and n the number of alignment pattern coordinates):

v² (total modules)
- 3⋅8⋅8 (finder patterns)
- (n² - 3)⋅5 (alignment patterns)
- 2⋅(4‍v + 1) (timing patterns)
+ 2⋅(n - 2)⋅5 (readding the intersection of alignment and timing patterns)
- 1 (dark module)
- 2⋅3⋅6 (format data, only if v > 6)

In code

We just need to do the above:



function getAvailableModules(version) {
  if (version === 1) {
    return 21 * 21 - 3 * 8 * 8 - 2 * 15 - 1 - 2 * 5;
  }
  const alignmentCount = Math.floor(version / 7) + 2;
  return (version * 4 + 17) ** 2
    - 3 * 8 * 8
    - (alignmentCount ** 2 - 3) * 5 * 5
    - 2 * (version * 4 + 1)
    + (alignmentCount - 2) * 5 * 2
    - 2 * 15
    - 1
    - (version > 6 ? 2 * 3 * 6 : 0);
}

You can simplify the above return statement or let the compiler do that for you (I got down to 16 * (version + 4) ** 2 - (5 * alignmentCount - 1) ** 2 - (version > 6 ? 172 : 136)).

Just like getAlignmentTracks, also this function can be memoized/use to precomputation/replaced with a table.

How many data codewords?

The main question is, though, is get to know how many of those codewords are reserved for data - and conversely how many for error correction.

The problem here is that I haven't found, nor derived, any exact formula to determine that. Remember the error correction table we've seen in part 1 and 3?

Level	Letter	Data recovery
Low	L	~7%
Medium	M	~15%
Quartile	Q	~25%
High	H	~30%

But we just can't take those percentages and derive the amount of error correction codewords back. The original specification reports this formula (from the Reed-Solomon error correction algorithm):

e + 2‍t ≤ d - p

where:

e = number of erasures (i.e. single errors at known locations);
t = number of errors (i.e. recoverable codewords);
d = number of error correction codewords;
p = number of misdecode protection codewords (generally 0, except for smaller QR Codes),

meaning that d error correction codewords can correct at most d/2 unreadable codewords.

But other than that, it just reports a table where we can just take the amount of error correction codewords, and that's it (you can get it from here, for example). If you compute the "recovery capacity" for each version and error level, you'll see those percentages being 2-3% off the values from the table.

For example, our case of a version 2 QR Code with quartile error level has 22 error correction codewords, meaning a recovery capacity of 11… which is exactly 25% of all the codewords. But it's a rare case.

If you take a version 6 QR Code, still with quartile error correction level, it can recover at most 4*24/2 = 48 codewords out of 172, which is ~27.9%. If you reserve only 88 codewords for error correction instead of 96, you'd have a recovery capacity of ~25.5% (closer to 25%) and 8 more codewords for data. I don't know why they chose otherwise.

Anyway, let's see how to structure a QR Code for larger versions, because it's not as straightforward as it was for version 2…

Codeword blocks

As version grows, the number of total codewords grows too (more or less quadratically). The spec developers decided it was wiser to split the message into several blocks of varying amounts of codewords. Each block has its own data and error correction codewords.

Moreover, not every block has the same amount of codewords, but they're divided in two groups instead: one with blocks of n codewords, the other with block with n + 1 codewords. But for every block the number of error correction codewords is the same, so it's the number of data codewords that has a difference of 1 between blocks of different groups.

Splitting the total set of codewords into blocks happens as soon as version 3, while you'd get two groups in version 5. The main goal is having the number of error correction codewords in each block to be at most 30, while splitting into groups is just for parity.

But let's cut to the point, and see the actual table:

Version and EC level	EC codewords/block	Group 1 blocks	Data codewords in G1 blocks	Group 2 blocks	Data codewords in G2 blocks
1-L	7	1	19
1-M	10	1	16
1-Q	13	1	13
1-H	17	1	9
2-L	10	1	34
2-M	16	1	28
2-Q	22	1	22
2-H	28	1	16
3-L	15	1	55
3-M	26	1	44
3-Q	18	2	17
3-H	22	2	13
4-L	20	1	80
4-M	18	2	32
4-Q	26	2	24
4-H	16	4	9
5-L	26	1	108
5-M	24	2	43
5-Q	18	2	15	2	16
5-H	22	2	11	2	12
6-L	18	2	68
6-M	16	4	27
6-Q	24	4	19
6-H	28	4	15
7-L	20	2	78
7-M	18	4	31
7-Q	18	2	14	4	15
7-H	26	4	13	1	14
8-L	24	2	97
8-M	22	2	38	2	39
8-Q	22	4	18	2	19
8-H	26	4	14	2	15
9-L	30	2	116
9-M	22	3	36	2	37
9-Q	20	4	16	4	17
9-H	24	4	12	4	13
10-L	18	2	68	2	69
10-M	26	4	43	1	44
10-Q	24	6	19	2	20
10-H	28	6	15	2	16
11-L	20	4	81
11-M	30	1	50	4	51
11-Q	28	4	22	4	23
11-H	24	3	12	8	13
12-L	24	2	92	2	93
12-M	22	6	36	2	37
12-Q	26	4	20	6	21
12-H	28	7	14	4	15
13-L	26	4	107
13-M	22	8	37	1	38
13-Q	24	8	20	4	21
13-H	22	12	11	4	12
14-L	30	3	115	1	116
14-M	24	4	40	5	41
14-Q	20	11	16	5	17
14-H	24	11	12	5	13
15-L	22	5	87	1	88
15-M	24	5	41	5	42
15-Q	30	5	24	7	25
15-H	24	11	12	7	13
16-L	24	5	98	1	99
16-M	28	7	45	3	46
16-Q	24	15	19	2	20
16-H	30	3	15	13	16
17-L	28	1	107	5	108
17-M	28	10	46	1	47
17-Q	28	1	22	15	23
17-H	28	2	14	17	15
18-L	30	5	120	1	121
18-M	26	9	43	4	44
18-Q	28	17	22	1	23
18-H	28	2	14	19	15
19-L	28	3	113	4	114
19-M	26	3	44	11	45
19-Q	26	17	21	4	22
19-H	26	9	13	16	14
20-L	28	3	107	5	108
20-M	26	3	41	13	42
20-Q	30	15	24	5	25
20-H	28	15	15	10	16
21-L	28	4	116	4	117
21-M	26	17	42
21-Q	28	17	22	6	23
21-H	30	19	16	6	17
22-L	28	2	111	7	112
22-M	28	17	46
22-Q	30	7	24	16	25
22-H	24	34	13
23-L	30	4	121	5	122
23-M	28	4	47	14	48
23-Q	30	11	24	14	25
23-H	30	16	15	14	16
24-L	30	6	117	4	118
24-M	28	6	45	14	46
24-Q	30	11	24	16	25
24-H	30	30	16	2	17
25-L	26	8	106	4	107
25-M	28	8	47	13	48
25-Q	30	7	24	22	25
25-H	30	22	15	13	16
26-L	28	10	114	2	115
26-M	28	19	46	4	47
26-Q	28	28	22	6	23
26-H	30	33	16	4	17
27-L	30	8	122	4	123
27-M	28	22	45	3	46
27-Q	30	8	23	26	24
27-H	30	12	15	28	16
28-L	30	3	117	10	118
28-M	28	3	45	23	46
28-Q	30	4	24	31	25
28-H	30	11	15	31	16
29-L	30	7	116	7	117
29-M	28	21	45	7	46
29-Q	30	1	23	37	24
29-H	30	19	15	26	16
30-L	30	5	115	10	116
30-M	28	19	47	10	48
30-Q	30	15	24	25	25
30-H	30	23	15	25	16
31-L	30	13	115	3	116
31-M	28	2	46	29	47
31-Q	30	42	24	1	25
31-H	30	23	15	28	16
32-L	30	17	115
32-M	28	10	46	23	47
32-Q	30	10	24	35	25
32-H	30	19	15	35	16
33-L	30	17	115	1	116
33-M	28	14	46	21	47
33-Q	30	29	24	19	25
33-H	30	11	15	46	16
34-L	30	13	115	6	116
34-M	28	14	46	23	47
34-Q	30	44	24	7	25
34-H	30	59	16	1	17
35-L	30	12	121	7	122
35-M	28	12	47	26	48
35-Q	30	39	24	14	25
35-H	30	22	15	41	16
36-L	30	6	121	14	122
36-M	28	6	47	34	48
36-Q	30	46	24	10	25
36-H	30	2	15	64	16
37-L	30	17	122	4	123
37-M	28	29	46	14	47
37-Q	30	49	24	10	25
37-H	30	24	15	46	16
38-L	30	4	122	18	123
38-M	28	13	46	32	47
38-Q	30	48	24	14	25
38-H	30	42	15	32	16
39-L	30	20	117	4	118
39-M	28	40	47	7	48
39-Q	30	43	24	22	25
39-H	30	10	15	67	16
40-L	30	19	118	6	119
40-M	28	18	47	31	48
40-Q	30	34	24	34	25
40-H	30	20	15	61	16

To read these values: a version 38 QR Code with high error correction level has its data codewords split in two groups. The first group has 42 blocks of 15 codewords each, and the second has 32 blocks of 16 codewords. For each of these blocks, there's a error correction block of 30 codewords.

As a practical example, let's create a QR Code for the string https://en.wikipedia.org/wiki/QR_code#Error_correction (still byte content, for simplicity), adding a quartile error correction level. We need at least a version 5 QR Code for that.

According to the table above, we'll need to split the data codewords into 2 blocks of 15 codewords, then other 2 blocks of 16 codewords each (for 62 codewords in total for data). Using the getData function from the last part, we get:



> getData('https://en.wikipedia.org/wiki/QR_code#Error_correction', 8, 62)
< Uint8Array(62) [67, 102, 135, 71, 71, 7, 51, 162, 242, 246, 86, 226, 231, 118, 150, 182, 151, 6, 86, 70, 150, 18, 230, 247, 38, 114, 247, 118, 150, 182, 146, 245, 21, 37, 246, 54, 246, 70, 82, 52, 87, 39, 38, 247, 37, 246, 54, 247, 39, 38, 86, 55, 70, 150, 246, 224, 236, 17, 236, 17, 236, 17]

These codewords should be split like this:

Block	Data codewords
G1-B1	`67 102 135 71 71 7 51 162 242 246 86 226 231 118 150`
G1-B2	`182 151 6 86 70 150 18 230 247 38 114 247 118 150 182`
G2-B1	`146 245 21 37 246 54 246 70 82 52 87 39 38 247 37 246`
G2-B2	`54 247 39 38 86 55 70 150 246 224 236 17 236 17 236 17`

In the next part, we'll see how to actually place all these information (plus the error correction, and something more) inside the QR Code matrix. See you soon! 👋

Let's develop a QR Code Generator, part VII: other kinds of data

Massimo Artizzu — Sat, 28 Aug 2021 21:26:27 +0000

So now we're able do create QR Codes for certain data. Specifically, short Latin-1 strings (i.e., strings with just 256 possible symbols, defined in the Latin-1 table). But, as we've said since part 1, we can encode also numbers, alphanumeric strings and even Kanji characters, thus wasting less of our available space.

After all, it's a shame if we can use 256 symbols but end up using just a limited set, no? But we're still working with codewords, and a codeword roughly translates into 8-bit bytes. So we need a way to stick more data in those bytes.

In the end, what we'll need is some function that spouts values that we'll need to write in our buffer (that consists of codewords, or better our Uint8Arrays). Keep in mind that those values aren't going to be 8-bit long, but rather they'll have variable bit length, as we'll see.

Preparing the field

Since we're using JavaScript, what better function to emit values than a generator? We'll come out with 4 different generator functions - one for each encoding mode - with the following signature (pardon the TypeScript):



type ContentValuesFn = (content: string) => Generator<{
  value: number;
  bitLength: number;
}, void, unknown>;

Each yielded value will go with its length in bits. Our old function getByteData (see part 2) will be replaced by a generic encoding function with the same arguments, and a fairly simple getByteValues generator function like this:



function* getByteValues(content) {
  for (const char of content) {
    yield {
      value: char.charCodeAt(0),
      bitLength: 8
    };
  }
}

Numbers

If we improperly accepted that a kilobyte is not 1000 bytes (as it should be), but rather 1024, it's because 1024 and 1000 are so close. We can actually take advantage of that!

So, how do we encode numbers? Let's start with a large number, for example the 10th perfect number: it's 191561942608236107294793378084303638130997321548169216, a 54 digits behemot (yes, perfect numbers grow quite fast).

The next step is to split the number in groups of 3 digits:

191 561 942 608 236 107 294 793 378 084 303 638 130 997 321 548 169 216

Each of these group can be stored in 10 bits (as 2¹⁰ = 1024), wasting just above 2% of space. If the last group is just 2 digit long, instead of 10 bits it will take 7 (since 2⁷ = 128 is enough to cover 100 values), and if the last group is just one digit it will take 4.

This will be the final result (version 2 QR Code, medium correction):

In code

We need to come up with a function that does just the above. We'll also use a BIT_WIDTHS constant as something to map the length of the group to its bit length:



const BIT_WIDTHS = [0, 4, 7, 10];
function* getNumericValues(content) {
  for (let index = 0; index < content.length; index += 3) {
    const chunk = content.substr(index, 3);
    const bitLength = BIT_WIDTHS[chunk.length];
    const value = parseInt(chunk, 10);
    yield { value, bitLength };
  }
}

Alphanumeric

Only 45 symbols are supported in alphanumeric mode, and they are:

numeric Arabic digits (codes from 0 to 9);
uppercase Latin letters (codes 10-35);
the following symbols: " " (space, code 36), "$" (37), "%" (38), "*" (39), "+" (40), "-" (41), "." (42), "/" (43), ":" (44).

If you notice, these symbols are enough for most URLs, although in uppercase and without query strings or fragments (as in our example from the previous parts, we'd encode HTTPS://WWW.QRCODE.COM/), but more in general alphanumeric mode should be used for simple messages in Latin letters and Arabic digits, plus some punctuation.

Why 45 symbols? I think it's because 45² = 2025. So, since 2¹¹ = 2048, similarly to numeric mode, we can encode two characters using 11 bits, wasting even less space (~1%).

All we have to do, then, is splitting our string into groups of two characters:



HT TP S: // WW W. QR CO DE .C OM /

Then, for each group, map each character to its alphanumeric code, multiply the first by 45 and add the second (as you'd do in a base-45 arithmetic). For the first group, H is code 17, T is 29, so the value to be written in our buffer is 17 * 45 + 29 = 794.

If the last group consists of only one character (as in our case), we'd need only 6 bits to write its value.

We'll some this result (version 2, quartile quality):

In code

The generator function for alphanumeric mode will be, predictably, very similar to the one for numeric mode. We'll use a constant string as a lookup table for mapping characters to their alphanumeric codes.



const ALPHACHAR_MAP = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:';
function* getAlphanumericValues(content) {
  for (let index = 0; index < content.length; index += 2) {
    const chunk = content.substr(index, 2);
    const bitLength = chunk.length === 1 ? 6 : 11;
    const codes = chunk.split('').map(
      char => ALPHACHAR_MAP.indexOf(char)
    );
    const value = chunk.length === 1
      ? codes[0]
      : codes[0] * ALPHACHAR_MAP.length + codes[1];
    yield { value, bitLength };
  }
}

Kanji mode

Kanji is a very complex alphabet. I don't even know if it can be actually called that, as it's not phoneme-based, but rather a set of logographic characters. But being so complex, it wouldn't expect encoding Kanji characters to be simple, would you?

Encoding Kanji in QR Codes uses the so-called Shift JIS code table, so for each character we'll have to find its equivalent code in Shift JIS. Not only that: QR Codes can accept characters with codes from (in hex) 0x8140 to 0x9FFC, and again from 0xE040 to 0xEBBF, for 6593 characters in total.

I won't go into detail about how to map a character into its Shift JIS code for now, as there are good libraries for the job (iconv-lite comes to mind, and you can even have a look to the actual table if you want to whip up your own solution). It's sufficient to say that we'll need 13 bits (2¹³ = 8192) for each one of them.

But we won't use the Shift JIS code directly, as they're all well above 8192 in values. We'll need to to the following:

get the Shift JIS code;
if the code is between 0x8140 and 0x9FFC, subtract 0x8140; otherwise, subtract 0xC140;
get the most significant byte from difference above (basically, shift the value 8 bits to the right), and multiply it by 0xC0 (192);
add the least significant byte of the difference (i.e., get the rest modulo 256).

For example, the character 荷 is 0x89D7 in Shift JIS, and the operations above will give us 1687; 茗 is 0xE4AA, so we'll get 6826.

In code

Let's suppose we have a magical getShiftJISCode function, so we won't need to write our own:



function* getKanjiValues(content) {
  for (const char of content) {
    const code = getShiftJISCode(char);
    const reduced = code - (code >= 0xe040 ? 0xc140 : 0x8140);
    const value = (reduced >> 8) * 192 + (reduced & 255);
    yield { value, bitLength: 13 };
  }
}

Wrap everything up

In part 2 we had a getByteData function to fill our available codewords, so we'll need something similar.

But first, we need a function to actually write value bits into our buffer. Something like this:



function putBits(buffer, value, bitLength, offset) {
  const byteStart = offset >> 3;
  const byteEnd = (offset + bitLength - 1) >> 3;
  let remainingBits = bitLength;
  for (let index = byteStart; index <= byteEnd; index++) {
    const availableBits = index === byteStart ? 8 - (offset & 7) : 8;
    const bitMask = (1 << availableBits) - 1;
    const rightShift = Math.max(0, remainingBits - availableBits);
    const leftShift = Math.max(0, availableBits - remainingBits);
    // chunk might get over 255, but it won't fit a Uint8 anyway, so no
    // problem here. Watch out using other languages or data structures!
    const chunk = ((value >> rightShift) & bitMask) << leftShift;
    buffer[index] |= chunk;
    remainingBits -= availableBits;
  }
}

It takes four arguments:

buffer is a Uint8Array (where we need to write);
value is the value we need to write;
bitLength is the length in bits of value;
offset is the index of the bit we'll start writing from.

I won't go into details, but basically it takes 8-bit chunks from value and write them into the buffer, preserving the existing data (that's why the OR assignment |=).

Next, we'll need to map the encoding mode values to our generator functions:



const valueGenMap = {
  [0b0001]: getNumericValues,
  [0b0010]: getAlphanumericValues,
  [0b0100]: getByteValues,
  [0b1000]: getKanjiValues
};

Then, we're going to refactor the mentioned function into something similar but functional for every encoding mode:



function getData(content, lengthBits, dataCodewords) {

  const encodingMode = getEncodingMode(content);

  let offset = 4 + lengthBits;

  const data = new Uint8Array(dataCodewords);

  putBits(data, encodingMode, 4, 0);

  putBits(data, content.length, lengthBits, 4);

  const dataGenerator = valueGenMap[encodingMode];

  for (const { value, bitLength } of dataGenerator(content)) {

    putBits(data, value, bitLength, offset);

    offset += bitLength;

  }

  const remainderBits = 8 - (offset & 7);

  const fillerStart = (offset >> 3) + (remainderBits < 4 ? 2 : 1);

  for (let index = 0; index < dataCodewords - fillerStart; index++) {

    const byte = index & 1 ? 17 : 236;

    data[fillerStart + index] = byte;

  }

  return data;

}

Coming soon…

We've come around the first of the main limitations of our QR Code generator so far: the encoding mode. We haven't seen ECI mode yet, but we've covered the basic 4 modes.

In the next parts, we'll create QR Codes of different sizes too, as we've only created version 2 codes. So keep in touch and see you around! 👋

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

Massimo Artizzu — Thu, 19 Aug 2021 15:02:00 +0000

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

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:

Four patterns, for a penalty of 160.

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:

compute the percentage of dark modules;
if the percentage is greater than 50, round down to the nearest multiple of 5; otherwise, round it up;
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;

  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:



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:

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.

Let's develop a QR Code Generator, part V: masking

Massimo Artizzu — Sat, 14 Aug 2021 21:40:41 +0000

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:

for each of the 8 estabilished masks, apply it to the matrix we got at the end of the last part;
compute the penalty score of the resulting output;
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		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!

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:



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



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[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¹⁰ + x⁸ + x⁵ + x⁴ + x² + 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]);
const maskedFormatPoly = formatPoly.map(
  (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]);
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):

And the following code should do it:



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



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

Let's develop a QR Code Generator, part IV: placing bits

Massimo Artizzu — Mon, 19 Jul 2021 14:35:20 +0000

Ok, now we've finally got our error correction data, and it's time to place all those codewords into the matrix!

So, we know there are parts of the QR code that are reserved. This leaves only the light modules below as fillable with our data:

In the figure above (the size of a version 2 QR code, i.e. the one we need for our example), the brown areas are fixed pattern areas, while the dark teal modules are reserved areas for encoding information (see the next part).

Before starting, let's estabilish the way to place our modules.

Not really, dear Padme, not really…

First thing, we start from the bottom right corner. Not actually a problem, here, as QR codes have the finder and alignment patterns exactly for being able to be read even when upside down.

Then we move to the left. And that's ok.

Then up and to the right. Wait, what?!

Then to the left again. And again up and to the right!

Now we've filled the first codeword. Remember that the first module corresponds to the leftmost bit of the first codeword. In our example (the string https://www.qrcode.com/), the first codeword is 65, or 01000001 in binary, so the first module will report 0, not 1, and thus it will be light; the second one will be dark, then 5 more light modules, and finally a dark module.

Then we proceed with thq zig-zag pattern towards the top of the grid. Once we've filled the last two columns, we can expect that we're going to fill the adjacent two columns next, with the same zig-zag movement. And that's correct, but we're starting from the top now:

And if you think we'll start the next two columns from the bottom, you guessed right. The problem here is that the alignment pattern is now in the way. The solution? Just skip it:

Moving on, we will resume the usual zig-zag pattern, until we find more reserved areas, which we're going to skip. And since the 7th column is always entirely reserved, we can pretend it doesn't even exist and we'll skip it altogether.

This is how we're going to fill a version 2 QR code:

I hope the images are pretty clear on how to proceed. But just in case, we can sum everything up with the following steps (remember that every time we end up on a module that doesn't belong to a reserved area, we shall use it for data):

start from the bottom right corner;
move to the left;
if we're not on the first row, move above and to the right, then go to step 2; otherwise proceed to step 4;
if we're on the 8th column, move twice to the left; otherwise move to the left;
move to the left;
if we're not on the last row, move below and to the right, then go to step 5; otherwise proceed to step 7;
if we're not on the first column, move to the left, then go to step 2; otherwise we're done 🙌

Also, notice how the last "codeword" has only 7 bits: we have no use for that, and those 7 bits are just remainder space. Versions from 2 to 6 all have 7 remainder bits, while other versions might have 0, 3 or 4 remainder bits.

It kind of feels like we've solved a maze, doesn't it? But why did we have to torture ourselves with this obscure path?

… I honestly have no idea. Really, if someone has some clues about it, please speak up 😭

Actually setting the modules

At this point, after placing all the modules and the fixed patterns, we should end up with this:

Wow, it definitely looks like a QR code! Alas, if you try to scan it, it doesn't work. Some parts are missing (the ones about error level and masking info, marked in dark teal in the figures above), and also it lacks masking. We'll get a working QR code at the end of the next part though!

The code

I'll be clear: actually showing a QR code is just a visualization problem. We can do it with an SVG, a <canvas>, a bunch of square <span>s, or even these two emojis: ⬜⬛. It's not really important, nor difficult for someone with a minimal expertise in rendering stuff on the web.

What is important is getting the matrix of bits that will allow us to create such figure.

Let's start with actually storing the data. Again, out of convenience we can use just an array of arrays - i.e., a matrix - to record whether a module is light (0) or dark (1). But for the rows we can use Uint8Arrays again, because they're faster than regular arrays and also for the .set() method that comes in handy. We'll start simple:



function getSize(version) {
  return version * 4 + 17;
}
function getNewMatrix(version) {
  const length = getSize(version);
  return Array.from({ length }, () => new Uint8Array(length));
}

The second argument of Array.from is basically a map function that lets us using a new typed array for each row (i.e., new Array(length).fill(new Uint8Array(length)) would use the same array for each row).

Now we need a function that fills a designed area with ones or zeroes, because it'll be useful for fixed patterns:



function fillArea(matrix, row, column, width, height, fill = 1) {
  const fillRow = new Uint8Array(width).fill(fill);
  for (let index = row; index < row + height; index++) {
    // YES, this mutates the matrix. Watch out!
    matrix[index].set(fillRow, column);
  }
}

At this point, we need the sequence of modules that we need to fill with our codewords. Our strategy will be:

start with an empty matrix;
mark with ones the reserved areas;
apply the 7-step iteration above - or a similar one.



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);
  // Alignment pattern - yes, we just place one. For the general
  // implementation, wait for the next parts in the series!
  fillArea(matrix, size - 9, size - 9, 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;

  let rowStep = -1;
  let row = size - 1;
  let column = size - 1;
  const sequence = [];
  let index = 0;
  while (column >= 0) {
    if (matrix[row][column] === 0) {
      sequence.push([row, column]);
    }
    // Checking the parity of the index of the current module
    if (index & 1) {
      row += rowStep;
      if (row === -1 || row === size) {
        rowStep = -rowStep;
        row += rowStep;
        column -= column === 7 ? 2 : 1;
      } else {
        column++;
      }
    } else {
      column--;
    }
    index++;
  }
  return sequence;
}

We did some changes in the function above. First of all, we're using rowStep to track whether we're going upwards or downwards in the matrix. Then we're using index and its parity to determine if we need to go left, or move diagonally.

For our version 2 QR code, we should end up with this:



getModuleSequence(2)
// Uint8Array(359) [[24, 24], [24, 23], [23, 24], ..., [16, 0]]

It's finally time to place our data (both message and error correction modules)!



function getRawQRCode(message) {
  // One day, we'll compute these values. But not today!
  const VERSION = 2;
  const TOTAL_CODEWORDS = 44;
  const LENGTH_BITS = 8;
  const DATA_CODEWORDS = 28;

  const codewords = new Uint8Array(TOTAL_CODEWORDS);
  const byteData = getByteData(message, LENGTH_BITS, DATA_CODEWORDS);
  codewords.set(byteData, 0);
  codewords.set(getEDC(byteData, TOTAL_CODEWORDS), DATA_CODEWORDS);

  const size = getSize(VERSION);
  const qrCode = getNewMatrix(VERSION);
  const moduleSequence = getModuleSequence(VERSION);

  // Placing the fixed patterns
  // Finder patterns
  [[0, 0], [size - 7, 0], [0, size - 7]].forEach(([row, col]) => {
    fillArea(qrCode, row, col, 7, 7);
    fillArea(qrCode, row + 1, col + 1, 5, 5, 0);
    fillArea(qrCode, row + 2, col + 2, 3, 3);
  });
  // Separators
  fillArea(qrCode, 7, 0, 8, 1, 0);
  fillArea(qrCode, 0, 7, 1, 7, 0);
  fillArea(qrCode, size - 8, 0, 8, 1, 0);
  fillArea(qrCode, 0, size - 8, 1, 7, 0);
  fillArea(qrCode, 7, size - 8, 8, 1, 0);
  fillArea(qrCode, size - 7, 7, 1, 7, 0);
  // Alignment pattern
  fillArea(qrCode, size - 9, size - 9, 5, 5);
  fillArea(qrCode, size - 8, size - 8, 3, 3, 0);
  qrCode[size - 7][size - 7] = 1;
  // Timing patterns
  for (let pos = 8; pos < VERSION * 4 + 8; pos += 2) {
    qrCode[6][pos] = 1;
    qrCode[6][pos + 1] = 0;
    qrCode[pos][6] = 1;
    qrCode[pos + 1][6] = 0;
  }
  qrCode[6][size - 7] = 1;
  qrCode[size - 7][6] = 1;
  // Dark module
  qrCode[size - 8][8] = 1;

  // Placing message and error data
  let index = 0;
  for (const codeword of codewords) {
    // Counting down from the leftmost bit
    for (let shift = 7; shift >= 0; shift--;) {
      const bit = (codeword >> shift) & 1;
      const [row, column] = moduleSequence[index];
      index++;
      qrCode[row][column] = bit;
    }
  }
  return qrCode;
}

We'll get a version 2 proto-QR code. With "proto" I mean it hasn't been transformed by the last action: masking. It consists in XOR'ing all the modules with one of 8 predefined patterns. And why should we do that, you might ask?

Well, this time it does make sense. If you have a look at our proto-QR code, there are large areas uniformly filled with dark or light patterns, and scanners generally don't like them as they might mismatch the grid or miscount the rows or columns. So we'll have to apply a mask in order to minimize this problem.

We'll see how to do this in the next part of the series! 👋

Let's develop a QR Code Generator, part III: error correction

Massimo Artizzu — Tue, 13 Jul 2021 17:01:16 +0000

Now comes the hard part.

Most of the Math in QR codes in performed in the Galois Field of order 2⁸ = 256. In this set, denoted as GF(256):

includes the numbers from 0 to 255;
has an "addition" operation, which is actually the binary XOR and not the usual sum (so the "sum" of two elements will still be part of GF(256));
has a "multiplication" operation, which is similar to the usual arithmetic multiplication but with some differences so that multiplying two elements will still give us an element of GF(256) (the neutral element is still 1).

The algorithm chosen for EDC in QR codes is the Reed-Solomon error correction, which is widely used for streaming data (e.g. CDs, wireless communications) because it allows to correct errors found in bursts, rather than single isolated cases. I won't go into details, but we're stuck with this kind of odd arithmetic.

Operations on GF(256)

The "addition" (XOR'ing) is quite simple. The neutral element with relation to XOR is still 0, as a ^ 0 = a. Also every element is the opposite of itself, since a ^ a = 0.

And since "subtraction" is defined as adding the opposite of the second term, this also means that the "subtraction" is equivalent of the "addition"! In fact: a - b = a ^ (-b) = a ^ b.

Now, about the multiplication. A Galois Field is cyclic, meaning that every non-zero element can be expressed as the power of a "primitive element" α. So, in GF(256), if a = αⁿ and b = α^m, then a ⋅ b = αⁿ ⋅ α^m = α^{n + m}.

But, as we said, a Galois Field is cyclic, so α²⁵⁶ = α. This means that we can take the exponent n + m modulo 255, so we can simplify our computations a bit. In the end, a ⋅ b = α^{(n + m) % 255} (if both a and b are non-zero; the result is of course 0 otherwise).

This also means that for every a, a²⁵⁶ = a, and then a²⁵⁵ = 1, therefore a²⁵⁴ = a^-1, i.e. is the inverse of a. So now we have a way to do divisions: a / b = αⁿ / α^m = αⁿ(α^m)²⁵⁴ = α^{(n + m * 254) % 255}.

Operations in code

XOR'ing is no sweat for JavaScript or any other capable language, but multiplication is another story. The easiest thing to do is creating logarithmic and exponential tables, so it'll be easy to convert a number from and to its exponential notation.

But how do we find α? It's not so hard, as there are φ(255) = 192 primitive elements in GF(256), where φ is Euler's totient function. For the sake of simplicity, we can take α = 2.

Since we're dealing with values all below 256, we can use JavaScript's Uint8Arrays, but if you wish you can use just regular arrays:



const LOG = new Uint8Array(256);
const EXP = new Uint8Array(256);
for (let exponent = 1, value = 1; exponent < 256; exponent++) {
  value = value > 127 ? ((value << 1) ^ 285) : value << 1;
  LOG[value] = exponent % 255;
  EXP[exponent % 255] = value;
}

We just start at 1, then double value at each iteration (shifting by 1 to the left). If value goes over 255, we XOR it with 285. Why 285? I won't go into details (if you're curious, you can find them here), as it has something to do with the relation between elements of a Galois field and polynomials, but rest assured that we'll get all 255 non-zero elements like this.

In the end we'll have:



> LOG
< Uint8Array(256) [0, 0, 1, 25, 2, 50, 26, 198, 3, 223, 51, 238, ...]
> EXP
< Uint8Array(256) [1, 2, 4, 8, 16, 32, 64, 128, 29, 58, 116, 232, ...]

Now we can implement the functions for multiplication and division:



function mul(a, b) {
  return a && b ? EXP[(LOG[a] + LOG[b]) % 255] : 0;
}
function div(a, b) {
  return EXP[(LOG[a] + LOG[b] * 254) % 255];
}

But how will that serve us for error correction? Let's see...

Polynomials in GF(256)

Yes, the Reed-Solomon algorithm uses polynomials! You've probably seen them since high school, and have this form:

anxⁿ + an - 1x^{n - 1} + ... + a1x + a0

where a0, ..., an are the coefficients, while x is the variable. You've probably seen (and solved, in the form of equations) them in the field of real numbers, with either real or complex solutions.

But coefficients, exponents and variables could be meant to be in any other field (ring would be enough, actually), even GF(256), inheriting its operations too. So, the "addition" is GF(256)'s addition, i.e. XOR, while multiplication is the one seen above. Exponentiation is just repeated multiplication by itself, as usual.

The good news here is that, as long as our concern is just generation, we do not need to solve any equation!

Polynomial multiplication

Addition is a commutative operation, meaning that a + b = b + a. It is in GF(256) too, because a ^ b = b ^ a. And multiplication is too, but it's also distributive over the addition, meaning that a(b + c) = ab + ac. And this holds in GF(256) too.

This basically means that we can multiply polynomials between them like we used to do with polynomials on real numbers. Suppose we have

p1(x) = anxⁿ + an - 1x^{n - 1} + ... + a1x + a0
p2(x) = bmx^m + bm - 1x^{m - 1} + ... + b1x + b0

Take the first term of p1(x), i.e. anxⁿ, then multiply it with all the terms of p2(x):

anxⁿ⋅p2(x) = anbmx^{n + m} + anbm - 1x^{n + m - 1} + … + anb1x^{n + 1} + anb0xⁿ

Then do the same with the second term of p1(x), then the third, and so on. Finally, sum them all together. If this makes your head spin, let's start with and example: x² + 3‍x + 2 and 2‍x² + x + 7. As we've said above, we have to do the following:

(x² + 3‍x + 2)(2‍x² + x + 7)
= x²(2‍x² + x + 7) + 3‍x(2‍x² + x + 7) + 2(2‍x² + x + 7)
= 2‍x⁴ + x³ + 7‍x² + 6‍x³ + 3‍x² + 21‍x + 4‍x² + 2‍x + 14
= 2‍x⁴ + (6 + 1)x³ + (7 + 3 + 4)x² + (21 + 2)x + 14
= 2‍x⁴ + 7‍x³ + 14‍x² + 23‍x + 14

We end up with a polynomial with 5 terms, which is the sum of the amount of terms of both polynomials, minus 1.

In code

We can represent a polynomial with the array of its coefficients, so that x² + 3‍x + 2 could be translated to [1, 3, 2]. Again, since the coefficients can't go over 255, we can use Uint8Array to optimize performances.

Of course all the operations are meant to be done in GF(256), so we're using XOR for addition and the mul function defined above.

Please read the comments in the code snippet below carefully 😁



function polyMul(poly1, poly2) {
  // This is going to be the product polynomial, that we pre-allocate.
  // We know it's going to be `poly1.length + poly2.length - 1` long.
  const coeffs = new Uint8Array(poly1.length + poly2.length - 1);

  // Instead of executing all the steps in the example, we can jump to
  // computing the coefficients of the result
  for (let index = 0; index < coeffs.length; index++) {
    let coeff = 0;
    for (let p1index = 0; p1index <= index; p1index++) {
      const p2index = index - p1index;
      // We *should* do better here, as `p1index` and `p2index` could
      // be out of range, but `mul` defined above will handle that case.
      // Just beware of that when implementing in other languages.
      coeff ^= mul(poly1[p1index], poly2[p2index]);
    }
    coeffs[index] = coeff;
  }
  return coeffs;
}

Polynomial divisions

Ooooh boy. Remember long divisions in high school? Same thing here. (Except we'll just need the rest of the division, not the quotient, but let's save that for later.)

Let't take a dividend polynomial 4‍x³ + 4‍x² + 7‍x + 5, and a divisor polynomial 2‍x + 1. Basically these are the steps:

divide the first term of the dividend polynomial (4‍x³) with the first term of the divisor (2‍x, and get 2‍x²);
multiply the divisor polynomial by the above quotient (you'll get 4‍x³ + 2‍x²);
get the rest by subtracting the result from the dividend (you'll get 2‍x² + 7‍x + 5);
if the degree of the rest is lower than the degree of the divisor, you're done; otherwise, the rest becomes your new dividend and you go back to step 1.

For the division above (in the field of real numbers), you'll get a polynomial quotient of 2‍x² + x + 3, and a rest of 2. Now let's do this in JavaScript, and in GF(256).

In code

The quotient polynomial will always be long the difference in length of the dividend and the divisor, plus one.

But it turns out that we don't need the quotient for the Reed-Solomon error correction algorithm, just the rest. So we're defining a function that returns only the rest of the division. The size of the quotient is needed just to count the steps to do.

The code below should be self-explanatory given the example above (it really just does the steps above), but if it's not feel free to ask in the comments:



function polyRest(dividend, divisor) {
  const quotientLength = dividend.length - divisor.length + 1;
  // Let's just say that the dividend is the rest right away
  let rest = new Uint8Array(dividend);
  for (let count = 0; count < quotientLength; count++) {
    // If the first term is 0, we can just skip this iteration
    if (rest[0]) {
      const factor = div(rest[0], divisor[0]);
      const subtr = new Uint8Array(rest.length);
      subtr.set(polyMul(divisor, [factor]), 0);
      rest = rest.map((value, index) => value ^ subtr[index]).slice(1);
    } else {
      rest = rest.slice(1);
    }
  }
  return rest;
}

Now what?

Theory says that a Reed-Solomon error correction data sequence spanning n codewords allows to recover up to n/2 unreadable codewords, they being among the data sequence or in error correction sequence itself (!). Kinda cool, is it?

Remember the error correction table from the first part?

Level	Letter	Data recovery
Low	L	~7%
Medium	M	~15%
Quartile	Q	~25%
High	H	~30%

Those percentages are not results, but rather goals: for example, we want the quartile level of correction to be able to recover 25% (a quarter) of the codewords. This means that for this level of correction, there must be as many error correction codewords as data codewords.

For example, a version 2 QR code contains 44 codewords in total. We want to recover up to 11 (25%) of them, which means that we must reserve 22 codewords for EDC. If it looks expensive, it's because it is... but necessary if we want our QR codes to be readable even when damaged.

(The above applies for smaller QR codes. For larger ones, data is often split into two groups, and each group into several blocks - up to 67. Each block has its own error correction sequence, but while data blocks for the second group are always one codeword larger then the blocks from the first group, error correction sequences are all long the same and sized for the larger block, so even for quartile level EDC sequences could be slighly more in total codewords than data. We'll discuss about spliting data into blocks later in the series.)

From this, it's also clear we can't do much better than level H of error correction. If, for example, we wanted 18 codewords to be recoverable out of 44, then we had to use 36 codewords just for error correction, leaving just 8 codewords for data - i.e. less than 18! It's clear it makes little sense, as we'd be better off just repeating the data.

Now let's focus on how to get those error correction codewords out of our data.

Working with (big) polynomials

In the second part, we've sequenced our data (the string https://www.qrcode.com/) into an array of bytes (or codewords, in QR code jargon). Now we've treated polynomials as arrays of values between 0 and 255, so basically using Uint8Arrays for both of them. And that's handy, since for error correction we have to view our data as a polynomial with the codewords as coefficients. Perfect!

Basically, we have our data that becomes this polynomial, called the message polynomial:

65‍x²⁷ + 118‍x²⁶ + 135‍x²⁵ + 71‍x²⁴ + … + 17‍x + 236

But we have 44 total codewords in our version 2 QR code, so we have to multiply this by x to the power of the error correction codewords, i.e. 16. In the end we have:

65‍x⁴³ + 118‍x⁴² + 135‍x⁴¹ + 71‍x⁴⁰ + … + 17‍x¹⁷ + 236‍x¹⁶

Now that we have our big polynomial, we have to divide it by... something, and take the rest of this division: the coefficients of the rest polynomial are going to be our error correction codewords!

But what's this divisor polynomial? Also called…

The generator polynomial

If we have to fill n codewords with error correction data, we need the generator polynomial to be of degree n, so that the rest is of degree n - 1 and so the coefficients are exactly n. What we're going to compute is a polynomial like this:

(x - α⁰)(x - α¹)(x - α²)…(x - α^{n - 2})(x - α^{n - 1})

Now, as we've said, in GF(256) subtraction is the same as addition, and we've also chosen α to be 2. Finally, there are 16 codewords for medium correction in a version 2 QR code, so our generator polynomial is this one:

(x + 1)(x + 2)(x + 4)(x + 8)(x + 16)(x + 32)(x + 64)(x + 128)(x + 29)(x + 58)(x + 116)(x + 232)(x + 205)(x + 135)(x + 19)(x + 38)

The values in the factors are basically the ones from the EXP table computed before. Anyway, let's get our polyMul function rolling!



function getGeneratorPoly(degree) {
  let lastPoly = new Uint8Array([1]);
  for (let index = 0; index < degree; index++) {
    lastPoly = polyMul(lastPoly, new Uint8Array([1, EXP[index]]));
  }
  return lastPoly;
}

Normally, you'd want to pre-compute or cache these polynomials instead of generating them each time. Anyway, our polynomial will be this one:



getGeneratorPoly(16);
// Uint8Array(17) [1, 59, 13, 104, 189, 68, 209, 30, 8, 163, 65, 41, 229, 98, 50, 36, 59]

Finally, we're getting our EDC codewords, by dividing our message polynomial with the generator polynomial:



function getEDC(data, codewords) {
  const degree = codewords - data.length;
  const messagePoly = new Uint8Array(codewords);
  messagePoly.set(data, 0);
  return polyRest(messagePoly, getGeneratorPoly(degree));
}

In the end:



const data = getByteData('https://www.qrcode.com/', 8, 28);
getEDC(data, 44);
// Uint8Array(16) [52, 61, 242, 187, 29, 7, 216, 249, 103, 87, 95, 69, 188, 134, 57, 20]

And we're done! 🙌 It's been a long, but fundamental chapter.

… at least for now. Because much still has to be done in order to create a working QR code.

Stay tuned for the next part, which will be a shorter one. We'll define some details around error correction, and learn how to actually displace all the codewords in the grid. In the following part, we'll talk about masking.

Let's develop a QR Code Generator, part II: sequencing data

Massimo Artizzu — Sat, 10 Jul 2021 16:29:36 +0000

In the first part we've seen the basic concepts of QR codes. Now let's actively do something to generate one. Let's suppose we want to create a QR code for the string https://www.qrcode.com/ (the official QR code site).

Encoding mode

First of all, we need to find the correct encoding mode. Each mode has a corresponding value, according to the following table:

Encoding Mode	Value bits
Numeric	0001 (1)
Alphanumeric	0010 (2)
Byte	0100 (4)
Kanji	1000 (8)
ECI	0111 (7)

Determining the optimal encoding mode is easily done by just checking what characters are included in the string. The only issue is detecting Kanji characters correctly. I'm no expert in Kanji by any means, so I'll just rely on the new ES2018 Unicode support of RegExp in JavaScript:

const KANJI_RE = /^[\p{Script_Extensions=Han}\p{Script_Extensions=Hiragana}\p{Script_Extensions=Katakana}]*$/u;

I don't actually know if it's a perfect fit for Kanji mode, so if anyone knows just hit the comments! (I'll come up with a better solution later in the series, probably.)

In the end, we'll have something like this:

const NUMERIC_RE = /^\d*$/;
const ALPHANUMERIC_RE = /^[\dA-Z $%*+\-./:]*$/;
const LATIN1_RE = /^[\x00-\xff]*$/;
const KANJI_RE = /^[\p{Script_Extensions=Han}\p{Script_Extensions=Hiragana}\p{Script_Extensions=Katakana}]*$/u;
function getEncodingMode(string) {
  if (NUMERIC_RE.test(string)) {
    return 0b0001;
  }
  if (ALPHANUMERIC_RE.test(string)) {
    return 0b0010;
  }
  if (LATIN1_RE.test(string)) {
    return 0b0100;
  }
  if (KANJI_RE.test(string)) {
    return 0b1000;
  }
  return 0b0111;
}

In the end, we have getEncodingMode('https://www.qrcode.com/') === 4.

Version

Let's aim for the smallest version possible: since it's 23 characters long, we can check in various tables around (here, for example) that we're going to need at least a version 2 code. Also, since we're there, we can get the highest possibile correction level - medium, in our case.

Also this other table tells us that a version 2 can contain 28 data codewords for medium correction: those 2 spare codewords are going to be used for data information.

If we wanted a higher error correction level, we should have chosen a larger version.

Data bits

The first 4 bits of our data sequence are 0100, our encoding mode.

Then, we'll tell how long our string is going to be. We need a table again for that, as the amount of bits reserved for this value is variable:

Encoding Mode	Version 1-9	Version 10-26	Version 27-40
Numeric	10	12	14
Alphanumeric	9	11	13
Byte	8	16	16
Kanji	8	10	12

Turning this into a handy function:

const LENGTH_BITS = [
  [10, 12, 14],
  [9, 11, 13],
  [8, 16, 16],
  [8, 10, 12]
];
function getLengthBits(mode, version) {
  // ECI mode folds into byte mode
  // Basically it's `Math.floor(Math.log2(mode))` but much faster
  // See https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/clz32
  const modeIndex = 31 - Math.clz32(mode);
  const bitsIndex = version > 26 ? 2 : version > 9 ? 1 : 0;
  return LENGTH_BITS[modeIndex][bitsIndex];
}

Since getLengthBits(4, 2) === 8 we'll need 8 bits, and 23 (the length of our string) in binary is 10111, our first bits are:

01000001 0111....

Next, the real data. All we have to do is getting the code of the characters of the string in ISO-8859-1:

h   t   t   p   s   :  /  /  w   w   w   .  q   r   c  o   d   e   .  c  o   m   /
104 116 116 112 115 58 47 47 119 119 119 46 113 114 99 111 100 101 46 99 111 109 47

Now convert everything to binary and concatenate it to the previous sequence:

01000001 01110110 10000111 01000111 01000111
00000111 00110011 10100010 11110010 11110111
01110111 01110111 01110010 11100111 00010111
00100110 00110110 11110110 01000110 01010010
11100110 00110110 11110110 11010010 1111....

Now we have to put a termination block, which is exactly 4 zeroes, so the last codewords will be 11110000. We still have 3 of the availabe 28 codewords to be filled.

Remaining space

We have filled all the 8 bits of the last codeword, otherwise we'd have to fill the remaining bits with zeroes (it's always like that in byte mode).

With the remaining codewords we can do two things:

instead of the termination 4-bit block, we can put another encoding mode block (maybe a different one) and start another sequence - but with just 3 codewords we can't do much;
fill the remaining codewords with the sequences 11101100 00010001 (which translates into 236 and 17 in decimal) until the limit is reached.

Why 236 and 17? I have no idea, but my guess is that they (Denso Wave?) made a lot of tries and verified that those two are the sequence that produces the most easily recognizable codes.

In the end we have:

65 118 135 71 71 7 51 162 242 247 119 119 114 231 23 38 54 246 70 82 230 54 246 210 240 236 17 236

Or, in binary:

01000001 01110110 10000111 01000111 01000111
00000111 00110011 10100010 11110010 11110111
01110111 01110111 01110010 11100111 00010111
00100110 00110110 11110110 01000110 01010010
11100110 00110110 11110110 11010010 11110000
11101100 00010001 11101100

Translating into code

Our function getByteData will need three things:

the content to be sequenced into codewords, of course;
how many bits are needed to state the length of the content: as we've seen, this depends on the encoding mode (byte, in this case) and the version (for our case it's 8);
the amount of codewords to be filled: this again depends on the QR code version and the error correction level (for our case it's 28).

For QR codes from version 10 and up we'll need 16 bits to express the length of our content, so the actual data will begin on the third codeword.

function getByteData(content, lengthBits, dataCodewords) {
  const data = new Uint8Array(dataCodewords);
  const rightShift = (4 + lengthBits) & 7;
  const leftShift = 8 - rightShift;
  const andMask = (1 << rightShift) - 1;
  const dataIndexStart = lengthBits > 12 ? 2 : 1;

  data[0] = 64 /* byte mode */ + (content.length >> (lengthBits - 4));
  if (lengthBits > 12) {
    data[1] = (content.length >> rightShift) & 255;
  }
  data[dataIndexStart] = (content.length & andMask) << leftShift;

  for (let index = 0; index < content.length; index++) {
    const byte = content.charCodeAt(index);
    data[index + dataIndexStart] |= byte >> rightShift;
    data[index + dataIndexStart + 1] = (byte & andMask) << leftShift;
  }
  const remaining = dataCodewords - content.length - dataIndexStart - 1;
  for (let index = 0; index < remaining; index++) {
    const byte = index & 1 ? 17 : 236;
    data[index + content.length + 2] = byte;
  }
  return data;
}

At the end of this first step, we should have this result:

getByteData('https://www.qrcode.com/', 8, 28)
// Uint8Array(28) [65, 166, 135, 71, 71, 7, 51, 162, 242, 247, 119, 119, 114, 231, 23, 38, 54, 246, 70, 82, 230, 54, 246, 210, 240, 236, 17, 236]

Remember: the above function will work for byte mode only!

Other encoding modes

We won't go into details for now, but for numeric mode we have to split the number in groups of 3 digits and encode each group with 10 bits (2¹⁰ = 1024, so the space wasted is minimal).

Alphanumeric mode contains 45 symbols instead, so the string must be splitted into groups of 2 characters. Each symbol has a value (first the digits, then the uppercase Latin letters, then the space and the symbols $, %, *, +, \, -, ., /, :), so every pair of characters can be translated into a number ranging from 0 to 2024 (= 45² - 1). Therefore, we need 11 bits for every two alphanumeric characters (2¹¹ = 2048).

For Kanji mode... oh dear. First, we'd have to get the Shift JIS code of the pictogram, and the best way to do it is using a library like iconv-lite or, if you want to to it on your own, use its symbol table. Also, not every symbol can be used, but only those in the ranges 0x8140 to 0x9FFC and 0xE040 to 0xEBBF. In the end, a Kanji character will take 13 bits.

Next steps

Keep in touch, because it's all been quite easy so far. Now we'll have to deal with error data correction (EDC), and Math will be rolling!