QR Code Generator

by Daniel Ghindea

The QR Code is generated as a .ppm/.png/.jpg image and its properties (version, color, error_correction and more) are all customizable. Currently the program has been tested on Linux.

CONTENTS:

• How it works
• Configuration parametes
• Contributors
• Bibliography
• Licence

HOW IT WORKS:

The process of generating a QR code consists of 5 steps:

Step 1: apply function patterns

• Finder Patterns are unique blocks of 7x7 modules used to orient the QR code in the correct position for decoding.
• Separators are used to distinguish the finder patterns from the rest of the QR code.
• Timing Patterns are used to accurately determine the size of the data grid.
• Alignment Patterns are used to straighten out QR Codes drawn on a curved surface. Depending of the selected QR version more or less alignment patterns can be placed.
• Dark Module is a single module that is always set on 1

QR code version 2

Step 2: encode data & place modules in matrix

PART I

For the beginning the input string has to be processed into a data string. The first 4 bits of the data string represent the Mode Indicator

Mode name	Mode Indicator
Numeric mode	0001
Alphanumeric mode	0010
Byte mode	0100
Kanji mode	1000

Next, the Character Count Indicator needs to be added in a group of x bits, where x depends on QR code version (check len_bit_no()). After that, based on the selected mode, the encoded input string needs to be added. In the end, the obtained string has to be broken up into 8-bit Codewords and padded with 0s if necessary (if its length isn't a multiple of 8 more 0s are required and, if it's still too short, it will be filled with 236 and 17 until maximum capacity is reached).

---

PART II

To ensure that the data is read correctly by the scanner it's required to generate error correction codewords for comparison. This process uses Reed-Solomon method for error correction. In a nutshell, it performs a polynomial division between the polynomial with coefficients made of data string elements and the generator polynomial (check Reed-Solomon documentation). The key of this process is finite field arithmetic ( GF(256) ).

Codewords obtained for "Hello world!" input in a version 1 QR code.

To arrange the codewords correctly into the matrix it's necessary to break the data string into groups and groups into blocks in a suitable manner for the given version of QR code. Then, an error correction array of codewords will be generated for every block. For more information see ¹.

---

PART III

Once the data has been encoded and error correction was generated it's time to place the codewords into the matrix. For this part it's required to interleave the blocks.

Final Message Codewords obtained for "Hello world!" input in a version 5-Q QR code.

Placing final message codewords in a version 1 QR code.

Step 3: mask the data section

To avoid the appearance of patterns that may disturb the scanning process is necessary to apply a mask. A mask pattern changes which modules are 1 and which are 0. To automaticaly determine which is the best mask a penalty score is calculated for each variant and the pattern with the lowest score is chosen.

> source

Step 4: apply format patterns

The format pattern is used to encode which mask pattern and which error correction level are in use. The first 2 bits in the format string represent the error correction and the next 3 the mask applied.

EC level	Bits	Integer Equivalent
L	01	1
M	00	0
Q	11	3
H	10	2

After that, the format string is processed similary to the data string, which results in a string with 15 bits that is placed like this:

For versions >= 7 a special pattern is required to identify version information.

Step 5: generate image based on matrix

Currently 3 image formats can be generated, the simplest one being .pmm. It is structured as it follows:

  P6              # magic number 
  115 115         # image width & height
  255             # maximum color value (ranges between 0-255)
  0 0 0     0  0  0     0 1 0  ...        # (width * height) groups of binary data
  5 1 8     11 3 12     4 6 11 ...        # that represent the RGB color values 
  ...       ...         ...               # of each corresponding pixel 

Since a QR code only has values of 0s and 1s, the .ppm file will contain only white pixels (255 255 255) and a specific color (0 0 0 - black by default). Because the dimensions of the data matrix depends on the selected version a scale variable was implemented to make images of the same size.

.png and .jpg image formats are more complex and in this program they're implemented using stb_image_write.h library.

For detailed explanations on this topic check bibliography.

MAKEFILE:

    make build      # compile
    make clean      # cleanup

SYNOPSIS:

    ./qr [OPTION]

DESCRIPTION:

    --config
            opens header file "config.h" to edit program parameters.

CONFIGURATION PARAMETERS:

Currently all versions are implemented. For more information about character capacities see ²

1. version: there are fixed configurations of QR code sizes that range from 1 to 40:

        1: 21 x 21; can encode up to 17 ASCII characters
        2: 25 x 25; can encode up to 32 ASCII characters
        3: 29 x 29; can encode up to 53 ASCII characters
        ...
        40: 177 x 177; can encode up to 2953 ASCII characters

2. error_correction_level: there are 4 levels of error correction that helps QR code to stay readable even if some pixels can't be recognised by the scanner:

        0: level M - up to 15%
        1: level L - up to 7%
        2: level H - up to 30%
        3: level Q - up to 25% 

3. data_type: QR code can hold 4 different types of data:

        1: numeric              /* not implemented */
        2: alphanumeric         /* not implemented */
        3: bytes
        4: kanji                /* not implemented */

4. mask_type: certain patterns in the QR code matrix can make it difficult for QR code scanners to correctly read the code. to counteract this, the QR code specification defines 8 mask patterns:

        0: (i + j) % 2 == 0
        1: i % 2 == 0
        2: j % 3 == 0
        3: (i + j) % 3 == 0
        4: (i/2 + j/3) % 2 == 0
        5: (i*j) % 2 + (i*j) % 3 == 0
        6: [(i*j) % 3 + i*j ] % 2 == 0
        7: [(i*j) % 3 + i + j] % 2 == 0

5. RGB color of the QR code is determined by the given amount of red, green and blue color. their values range between 0 and 255.

6. file: string that defines output file's name and format.

        name.ppm  #.ppm file
        name.png  #.png file
        name.jpg  #.jpg file

7. scale: factor used to determine the final size of the generated image

Example of configuration

config.h:
    // QR properties
    #define version 7
    #define error_correction_level 1
    #define data_type 3
    #define mask_type 3
    // color parameters
    #define red 0
    #define green 0
    #define blue 0
    // file name
    #define file "QR.png"
    #define scale 10

QR code version 7, ec level L, byte format, mask no. 3, color black, generated as .png file

CONTRIBUTORS:

Thanks to radubig for fixing memory leaks and overview.

BIBLIOGRAPHY:

• Thonky QR code tutorial
• Reed-Solomon CFC
• Reed-Solomon EC
• Polynomials
• stb library for image formats

LICENSE:

Content is published under MIT Licence. For more information check LICENSE.md

---

Footnotes

1. error correction table ↩

2. character capacities by version ↩