Fast QR Code generator library

Introduction

This is an alternate, speed-optimized implementation of my QR library in Java. It contrasts with my standard/reference/slow library which optimizes for clarity and conciseness. The functionality of this fast library and its API are nearly identical to the other one, but it runs anywhere from 1.5× to 10× as fast. However, even the slow library takes less than 10 ms in the worst case, so the benefit of increasing speed is dubious at best.

The slow library is available in Java plus 5 other programming languages, but the fast one is only available in Java. To achieve speed-ups, I rewrote parts of the logic to implement caching and optimize low-level arithmetic, at the cost of making the architecture more complicated and the code longer. The fast library can be useful for applications that need to generate large batches of QR Code symbols. Two demo applications are provided to illustrate the usage.

Source code

Browse the project’s source code at GitHub: https://github.com/nayuki/QR-Code-generator/tree/master/java-fast

import java.awt.image.BufferedImage;
import java.io.File;
import java.util.List;
import javax.imageio.ImageIO;
import io.nayuki.fastqrcodegen.*;

// Simple operation
QrCode qr0 = QrCode.encodeText("Hello, world!", QrCode.Ecc.MEDIUM);
BufferedImage img = toImage(qr0, 4, 10);  // See QrCodeGeneratorDemo
ImageIO.write(img, "png", new File("qr-code.png"));

// Manual operation
List<QrSegment> segs = QrSegment.makeSegments("3141592653589793238462643383");
QrCode qr1 = QrCode.encodeSegments(segs, QrCode.Ecc.HIGH, 5, 5, 2, false);
for (int y = 0; y < qr1.size; y++) {
    for (int x = 0; x < qr1.size; x++) {
        (... paint qr1.getModule(x, y) ...)
    }
}

Design notes

Here is a high-level explanation of how I took my reference/slow library and changed the architecture and calculations to optimize for speed.

BitBuffer class

• The slow bit buffer class is based on java.util.BitSet. The fast bit buffer is based on low-level manipulation of an array of 32-bit int values.

• The slow buffer only reads or writes one bit at a time, whereas the fast buffer works with many consecutive bits that don’t cross a word boundary.

• The speed of the bit buffer impacts the creation and concatenation of QR segments.

QrSegment class

• The slow makeNumeric() uses Integer.parseInt(), but the fast version calculates directly on the character codes.

• The slow makeAlphanumeric() uses String.indexOf(), whereas the fast version queries a look-up table once per character.

• The slow isNumeric() and isAlphanumeric() use regular expressions to test the incoming string before starting to encode. The fast variants of the functions perform the character set checking while encoding output bits; if the string is invalid then the partially encoded result is discarded and an exception is thrown.

• The constructor (which generally shouldn’t be used because it’s quite low-level) takes a raw array and length instead of a BitBuffer object, in order to reduce a layer of pointer indirection.

• Overall, the speed improvement within this class shouldn’t be great. The main speed-up comes from QrSegment utilizing the new BitBuffer class.

ReedSolomonGenerator class

• The QR Code standard uses between 7 to 30 error correction bytes per block. We can create Reed–Solomon encoders for given ECC sizes, and cache them for later reuse. These cached encoders include pre-computed multiplication tables.

• Note that QR Code symbols of many versions and error correction levels may share the same RS ECC generator, due to having the same number of error correction bytes per block.

QrTemplate class

• Some aspects of a QR Code symbol only depend on the version (size) and not on the user data being conveyed. These pieces of information can be pre-computed and cached, if you generate many QR Codes that have the same version number.

• Most of the function patterns stay the same: finders, alignment, timing, version info block, and a single dark module. The format info (mask and error correction level) does vary. Hence, the invariant parts of a QR Code of a particular version are rendered onto an initially blank template.

• There is also a temporary template that marks whether each module is for a function pattern versus a bit from a user data/ECC codeword.

• The template computes and saves the zigzag scan. Hence the template knows, for each user data/ECC codeword bit, what location the bit is rendered at in the final QR Code symbol.

• The template also saves all 8 mask patterns, with respect to the version number and avoidance of function pattern modules.

Memoizer class

• This is a thread-safe function execution cache that is used for ReedSolomonGenerator and QrTemplate.

• When a worker is given f and x and wants to compute f(x), it first checks if the dictionary (cache) already contains the answer. If the key-value mapping exists and the soft reference’s target is not null, then it immediately returns that value. Note that the soft reference could be cleared by the garbage collector at any time to reclaim memory. Otherwise, the worker checks if another worker is already trying to compute the same value; if so then it waits for the other worker to finish and then it rechecks the dictionary; otherwise it marks the entry as pending, runs the function, stores the result in the dictionary, notifies all waiting workers, and returns the answer.

QrCode class

• The early parts of the QR Code encoding process are the same in the slow and fast versions: making segments, finding a version number and error correction level, and concatenating segments.

• The computation of error correction bytes is performed using the fast, cacheable Reed–Solomon generator.

• With the version number known and all the data plus ECC bytes, an appropriate QR Code template is cloned as the basis of this barcode.

• The format info is computed and drawn. Then the codewords are drawn using the pre-computed zigzag scan.

• If automatic masking is requested, then each of the 8 masks is applied, the penalty score is computed, and the mask is removed.

• The getPenaltyScore() method fuses all the horizontal-scanning loops into one, and likewise for the vertical-scanning loops. This reduces the amount of overhead spent on extracting bits from specific locations in the QR Code symbol.

Automatic mask selection is an expensive feature that seems to resist effective optimization. Surprisingly in the fast library, the evaluation of one penalty score takes more time than all the other steps needed to render a QR Code symbol. When comparing the fast and slow libraries with the same input data and options, the speed-up is greater if manual masking is used, and less if automatic masking is used.

Benchmark timings

I measured the time to generate a single QR barcode, for all versions from 1 to 40, for all 4 error correction levels, for both the slow and fast Java libraries. The data for each case is a random lowercase string (which must be encoded in byte mode), such that the length is the longest supported by the particular version and error correction level. The platform is OpenJDK Java 12.0.1 (64-bit), Intel Core i5-4690 (Haswell) 3.50 GHz, Windows 8.1 Pro (64-bit).

Manual mask selection

The computations performed are rendering the main QR Code content, applying one mask, and not calculating the penalty score. All times are in microseconds (μs). The speed-up factor is the slow time divided by the corresponding fast time.

Automatic mask selection

The computations performed are rendering the main QR Code content, iterating 8 times of {apply mask, calculate penalty score, remove mask}, and applying one final mask. All times are in microseconds (μs). The speed-up factor is the slow time divided by the corresponding fast time.

Observations

• For manual masking, the fast library is about 8× the speed of the slow library. It represents a good payoff for the amount of new code written.

• For automatic masking, the speed-up is only about 1.7×. This figure does not adequately justify the effort and complexity of the new code.

• For the fast library, manual masking is about 40 times faster than automatic masking. Using manual masking is a good choice if the input already has good randomness properties, such as the output of a hash function.

• For a given version, using less error correction (and storing more useful data) takes somewhat more computation time. This is entirely due to how much work the Reed–Solomon encoding performs; it is unaffected by the templates and rendering logic.