Project Nayuki


Fast QR Code generator library

Introduction

My (slow) QR Code generator library is available in 6 programming languages, and its code is optimized for readability. Here, I rewrote the Java version of the library for speed, at the cost of making the code longer and implementing a harder-to-understand architecture.

This library runs about 1.5 to 6 times as fast as the slow reference library, which can be useful for applications that need to generate large batches of QR Code symbols.

The public API is exactly the same as the reference library, which makes it easy to switch between the two implementations. Two demo applications are provided to illustrate the usage.

Source code

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

Or download a ZIP of all the files: https://github.com/nayuki/Fast-QR-Code-generator/archive/master.zip

Design notes

The following is an overview of how the slow QR Code library’s logic was changed 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 parses numbers manually.

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

  • The slow makeNumeric() and makeAlphanumeric() 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.

  • 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
  • Instead of multiplying finite field elements via the basic algorithm, we pre-compute a 256×256 look-up table, which covers all possible inputs.

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

  • A thread-safe cache is implemented: When a worker needs an RS generator, it examines the cache table and follows the soft reference. (The soft reference could be cleared by the garbage collector at any time to reclaim memory.) If the reference or referent is missing, then the worker either creates the object or waits for another thread to finish creating it. If the cache entry is marked as pending, then this worker waits for a notification, then rechecks. Otherwise, the worker creates the RS generator object, saves it in the cache, and notifies any waiters.

  • 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 depends 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 black 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.

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-correcting 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 speedup 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 Oracle Java 1.8.0 Update 152 (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.

Version Slow L Slow M Slow Q Slow H Fast L Fast M Fast Q Fast H Speedup L Speedup M Speedup Q Speedup H
11110101032224.094.734.924.90
21516171833325.555.395.877.74
32327191944335.336.675.576.46
43428302065545.906.116.525.24
55041292887556.396.235.575.58
65041403987765.955.795.996.00
761494041108776.126.125.715.71
8806553491311996.356.205.815.67
9107765954161211106.536.165.605.44
1096967369161513126.106.195.705.61
111171199172191916136.236.295.855.32
121441159886231917166.276.035.705.40
1317213010986272220176.406.015.585.09
1420014810898312520196.456.055.405.21
15192167146109312825216.246.055.765.13
16223195143135363226256.256.105.505.35
17264217171143423530276.356.125.665.27
18303231185157483833306.366.045.575.25
19320254197164514236326.336.055.545.14
20345271230189554541366.296.005.615.20
21374290235206594842396.346.035.545.27
22402327267202635448406.336.055.615.04
23452358287235715951456.346.035.615.19
24484380309257766355496.346.015.595.21
25485413332270776960536.316.025.575.15
26540439338295867362576.295.995.475.16
27600465373311957868616.335.955.525.14
28626492400328998272646.315.975.565.14
296655214193471068876686.295.955.515.11
307075624503681129482726.315.965.525.09
3174959447339011910086776.295.965.485.09
3279462850641312610692826.295.945.495.07
3384066453143813411297866.275.945.475.07
34887700558465141118102926.285.935.455.07
35933735583480148123107956.315.955.475.07
369837756135101561301121006.315.965.475.08
3710348076455321641361181056.315.945.475.05
3810888516785551721431241106.315.935.465.03
3911328957125891801511311176.305.935.455.05
4011889417486141881591371226.315.945.455.04
Version Slow L Slow M Slow Q Slow H Fast L Fast M Fast Q Fast H Speedup L Speedup M Speedup Q Speedup H

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.

Version Slow L Slow M Slow Q Slow H Fast L Fast M Fast Q Fast H Speedup L Speedup M Speedup Q Speedup H
193888787615553531.541.601.641.63
2133130130132858079781.561.631.651.68
31831811741741151091081081.591.661.611.61
42432322332221481421411411.641.641.651.58
53102982832811871791791791.661.671.591.57
63673553553552272202202201.621.621.621.61
74464314224212732652642641.631.631.601.60
85355175044973233153143141.661.641.611.58
96365995875843773713663681.691.621.601.59
107067056846754314274254281.641.651.611.58
118128187907724904904884881.661.671.621.58
129319058928835565525555541.681.641.611.59
131056101710039806256216236231.691.641.611.57
1411941144111111027056976996971.691.641.591.58
1512931273125812247777757807731.671.641.611.58
1614441423137613688618608618631.681.651.601.59
1716061565152814999489479479471.691.651.611.58
18177317031670164210381033103710371.711.651.611.58
19192118591816178811291129113411351.701.651.601.58
20208320151983194812301228123312331.691.641.611.58
21223421722129211113161323132813351.701.641.601.58
22239423542310225614191429143714391.691.651.611.57
23260525302482245015271535154615541.711.651.611.58
24279127202670263216411652166316711.701.651.611.58
25295729212854281917501766178317921.691.651.601.57
26317831123039301018731888190019111.701.651.601.58
27340733153254321019952014202820361.711.651.601.58
28366335593486342321522164216921731.701.641.611.57
29389237763692363322892297230223081.701.641.601.57
30412140093926384924252431244624441.701.651.601.58
31436142514156408025642577258725901.701.651.611.58
32461944964400431827122724273827381.701.651.611.58
33485847364630455628572869288028921.701.651.611.58
34513649954880480330143023303730441.701.651.611.58
35540352425138504931563170319332001.711.651.611.58
36567855115393530833163333335733641.711.651.611.58
37595957905667557134833497351935271.711.661.611.58
38624460605948583936503661369336991.711.661.611.58
39653863526224612338223834386538711.711.661.611.58
40686066636537642639934006404140501.721.661.621.59
Version Slow L Slow M Slow Q Slow H Fast L Fast M Fast Q Fast H Speedup L Speedup M Speedup Q Speedup H

Observations