Algorithm for generating a QR code

A QR code is a monochrome picture in which some devices (for example, a smartphone with a special application) recognize the text. This text can be not only a simple phrase, but, although it is not included in the official specification, a link, a phone number or a business card. Such codes are most often used to encode a link and print it on a poster or business card.

This article is a detailed instruction on creating a QR code with examples at each step, which requires you to have only basic skills in working with binary data and mastering any programming language (if you want to create an automatic QR code generator).
')
The basis of this article is taken by the cycle of articles "QR Code Demystified" by Jason Brown (Jason Brown). There are many nuances in these articles that have caused me some problems. All these nuances are taken into account and mentioned here.



The process of generating a QR code is divided into several clear steps:

1. Encoding data.
2. Add service information and fill.
3. The division of information into blocks.
4. Creating correction bytes.
5. Combining blocks.
6. Placing information on the QR code.

Data coding

The QR code supports several ways of encoding data, depending on which characters are used: digital, alphanumeric, kanji (Chinese-Japanese hieroglyphs) and byte-coding. Digital coding implies using only numbers from 0 to 9, alphanumeric - capital letters of the Latin alphabet, numbers and symbols $% + + -. /: And a space, I will not consider kanji, and encoding bytes are not required at all. First you need to create an empty bit sequence, which will be filled further.

Digital coding

This type of encoding requires 10 bits by 3 characters. The entire sequence of characters is divided into groups of 3 digits, and each group (a three-digit number) is translated into a 10-bit binary number and added to the sequence of bits. If the total number of characters is not a multiple of 3, then if at the end there are 2 characters left, the resulting two-digit number is encoded with 7 bits, and if 1 character, then 4 bits.

For example, there is the string "12345678" that needs to be encoded. We divide it into numbers: 123, 456 and 78, then we translate each of them into binary form: 0001111011, 0111001000 and 1001110, and combine it into one stream: 000111101101110010001001110.

Alphanumeric encoding

In this case, 2 characters require 11 bits of information. The input stream of characters is divided into groups of 2, in the group each character is encoded according to the table below, the value of the first character in the group is multiplied by 45 and added to the value of the second character. The resulting number is converted to an 11-bit binary number and added to the bit sequence. If the last group contains 1 character, then its value is immediately encoded with a 6-bit number and added to the bit sequence.



For example, the string "HELLO" is encoded as follows. We divide into groups: HE, LL, O; we find the corresponding value of the symbols in each group: (17, 14), (21, 21), (24); we find the value for each group: 17 * 45 + 14 = 779, 21 * 45 + 21 = 966, 24 = 24; translate each value into a binary form: 779 = 01100001011, 966 = 01111000110, 24 = 011000; and combine it all into one sequence of bits: 0110000101101111000110011000.

Byte coding

This is a universal encoding method that can encode any characters. The only drawback of the method is the relatively low information density. In this case, the text is encoded in any encoding (recommended in UTF-8) and the resulting sequence of bytes is taken unchanged.

For example, the string "Habr", encoded UTF-8 encoding, a byte consists of the following: 11010000, 10100101, 11010000, 10110000, 11010000, 10110001, 11010001 and 10000000. They just need to be combined into a single bit stream: 1101000010100101110100001011000011010000101100011101000110000000.

Add service information

At this stage, it is necessary to determine the level of correction: the higher this level, the higher the permissible level of damage to the image and the less information with an equal size. There are 4 levels of correction in total: L (maximum 7% damage is acceptable), M (15%), Q (25%) and H (30%). Level M is most often used. If you want to add a picture to a QR code (there are several articles on this topic on Habré), then use level H.

Another property of the QR code is its version (the larger it is, the larger the size). There are 40 versions in total. The version number depends on the amount of information encoded and on the level of correction. Table 2 shows the maximum amount of useful information along with service information (in bits), which can be encoded in the QR code of this version. The version of our QR code is determined from this table.

Adding service fields

At this point, the correction level should be selected and the version determined. Now it is necessary, before the bit sequence obtained in the previous paragraph, to add two fields at the beginning: the encoding method and the amount of data. The encoding method is a 4-bit field, which has the following values: 0001 for digital encoding, 0010 for alphanumeric and 0100 for byte-byte. The amount of data is the number of characters to be encoded, and for byte bytes, the number of bytes (and not the bits in the received sequence), represented as a binary number of a certain length (determined according to Table 3).



For example, given a string of 100 bytes, encoded byte-byte, the correction level is M. The length of the bit sequence of this string is 800 bits. Using the table 2, you can determine that the best will use the 6th version. The length of the field that determines the amount of data in our case is 8 bits (Table 3). The field defining the encoding method is 0100, the data quantity field is 01100100 (100 in binary form). The result is a sequence of bits 010001100100 <original sequence>.

If the length of the received sequence of bits turned out to be more acceptable for the selected version, then the version should be increased by one and the service fields should be added anew.

The specification allows the use of mixed coding. This means that several data groups can be encoded in different ways and combined into one sequence. This is done as follows: <data encoding method 1> <data amount 1> <data 1> <data encoding method 2> <data amount 2> <data 2> and so on.

Filling

At this stage, we have a sequence of data bits, the number of bits in which is probably not a multiple of 8. We must add zeros so that its length becomes a multiple of 8. Now our sequence of bits can be divided into groups of 8 bits and represented as a sequence of bytes ( then we will do so). If the number of bits in the current byte sequence is less than that needed for the selected version, then it must be supplemented with alternating bytes 11101100 and 00010001. Thus, we have a sequence of bytes, the length of which corresponds to the selected version of the QR code.

Example. There is a sequence: <a sequence of bits whose length is a multiple of 8> 10101011101; we fill it with zeros so that its length becomes a multiple of 8: <a sequence of bits whose length is a multiple of 8> 10101011101 00000; Now suppose that its length is 104 bits, and for the selected version you need 128 bits, then you need to add 24 “fill” bits (3 bytes) to fill: <a sequence of bits that is a multiple of 8> 10101011101 00000 11101100 00010001 11101100. Done.

Information division into blocks

The sequence of bytes obtained in the previous step (hereinafter referred to as data) is divided into the number of blocks specified for the version and correction level, which is shown in Table 4. If the number of blocks is one, then this step can be skipped.

Determining the number of bytes in each block

To do this, you need to divide the entire number of bytes (you can determine the number of bytes in the data or divide the number from table 2 by eight) by the number of data blocks. If this number is not an integer, then it is necessary to determine the remainder of the division. This remainder determines how many blocks of all are added (such blocks, the number of bytes in which is one more than in the others). Contrary to expectations, the added blocks should not be the first blocks, but the last ones.

For example, for version 9 and the correction level M data quanta are 182 bytes, the number of blocks is 5. Sharing the number of data bytes by the number of blocks, we get 36 bytes and 2 bytes in the remainder. This means that the data blocks will have the following sizes: 36, 36, 36, 37, 37 (bytes). If there was no residue, all 5 blocks would be 36 bytes in size.

Filling the blocks

The block is filled with bytes from the data completely. When the current block is full, the queue moves to the next. Data bytes should be enough for all blocks, no more and no less.

Creating correction bytes

The following algorithm is applied to each data block (if the data block is one, then just to the data).

This algorithm is based on the Reed – Solomon algorithm . The first thing to do is to determine how many bytes of correction should be created (table 5). By the number of correction bytes, the so-called generating polynomial is determined (Table 6). It is called a polynomial, because the original method uses a polynomial with the same coefficients.





Before executing the loop, it is necessary to prepare an array whose length is equal to the maximum of the number of bytes in the current block and the number of correction bytes, and fill its beginning with bytes from the current block, and the end with zeros.

The cycle described in this list is repeated as many times as the data bytes are contained in the current block.

1. We take the first element of the array, save its value in the variable A and remove it from the array (all the following values ​​are shifted one cell to the left, the last element is filled with zero).
2. If A is zero, then skip the following steps (to the end of the list) and go to the next iteration of the loop.
3. Find the corresponding number A number in table 8, put it in the variable B.
4. Further, for the N first elements, where N is the number of correction bytes, i is the loop counter:
   
   • It is necessary to add the value of B to the i-th value of the generating polynomial and write this sum in variable C (do not change the polynomial itself).
   • If B is greater than 254, it is necessary to use its remainder when divided by 255 (255, not 256).
   • Find the corresponding B value in Table 7 and perform bitwise addition modulo 2 (XOR, operator ^ in many programming languages) with the i-th value of the prepared array and write the obtained value into the i-th cell of the prepared array.

The first N bytes of the prepared array after this cycle are the correction bytes. For each data block, the corresponding byte correction block is obtained.

Nothing is clear? Me too. Look at the example and everything will become clear.





Example. Here I will represent all the bytes in the form of decimal numbers from 0 to 255. The original data block:
64 196 132 84 196 196 242 194 4 132 20 37 34 16 236 17
The 2nd version with the correction level H is used. In this case, you need to create 28 bytes of correction (table 5) and use the generating polynomial (table 6):
168 223 200 104 224 234 108 180 110 190 195 147 205 27 232 201 21 43 245 87 42 195 212 119 242 37 9 123
Create an array (prepared array) for 28 elements and fill it with data bytes:
64 196 132 84 196 196 242 194 4 132 20 37 34 16 236 17 0 0 0 0 0 0 0 0 0 0 0 0
I will paint in detail the first step of the cycle, the rest in the form of a finished array. The first element of the array is 64. We remove it from the prepared array:
196 132 84 196 196 242 194 4 132 20 37 34 16 236 17 0 0 0 0 0 0 0 0 0 0 0 0 0
In table 8, we find a match for it - 6; add 255 this number to each number of the generating polynomial:
174 229 206 110 230 240 114 186 116 196 201 153 211 33 238 207 27 49 251 93 48 201 218 125 248 43 15 129
For each number of the generating polynomial, we find the correspondence in table 7:
241 122 83 103 244 44 62 110 248 200 56 146 178 39 11 166 12 140 216 182 70 56 43 51 27 119 38 23
And we perform the operation of bitwise addition modulo 2 with the prepared array:
53 254 7 163 48 222 252 106 124 220 29 176 162 203 26 166 12 140 216 182 70 56 43 51 27 119 38 23
Repeat these steps 16 times (16 bytes of data). The result will be the following correction bytes:
16 85 12 231 54 54 140 70 118 84 10 174 235 197 99 218 12 254 246 4 190 56 39 217 115 189 193 24

Combining blocks

We have several data blocks and as many blocks of correction bytes, they need to be combined into one stream of bytes. This is done as follows: from each data block, one byte of information is taken in turn, when the queue reaches the last block, a byte is taken from it, and the queue goes to the first block. This continues until bytes in each block run out. If there are no more bytes in the current block, then it is skipped (this happens when the usual blocks are already empty, and in the added blocks there is one byte). Similarly, you need to do with blocks of bytes correction. They are taken in the same order as the corresponding data blocks.

The result should be something like this: <1st byte of 1st data block> <1st byte of 2nd data block> ... <1st byte of nth data block> <2nd byte 1st data block> ... <(m - 1) -th byte of the 1st data block> ... <(m - 1) -th byte of the n-th data block> <m-th byte of k-th data block> ... <m-th byte of n-th data block> <1st byte of 1st correction byte block> <1st byte of 2nd correction byte block> ... <1st byte n th block of correction bytes> <2nd byte of 1st correction byte block> ... <lth byte of 1st correction byte block> ... <lth byte of nth correction byte block>. Here n is the number of data blocks, m is the number of bytes per data block of ordinary blocks, l is the number of correction bytes, k is the number of data blocks minus the number of padded data blocks (those with 1 more byte).

Placing information on the QR code

We have a byte sequence, which is ready to be placed on the canvas. Canvas consists of modules - elementary squares.

Basic elements

The size of the QR code depends only on the version. For the first version, this is 21 modules, and the sizes of the older versions are determined from table 9. In general, it shows the locations of the alignment patterns (more on that later), but the canvas size can be defined as the last number + 7 modules. I want to draw your attention that the indent, a frame of white modules 4 modules wide, is a full-fledged part of a QR code, and it cannot be ignored. Despite this, I indicate the width of the width of the part with black modules and start the report with its upper left corner ((0, 0) - the upper left module of the upper left search pattern).

Search patterns

These are patterns that are a black square measuring 3 by 3 modules, which is surrounded by a frame of white modules, which is surrounded by a frame of black modules, which is surrounded by a frame of white modules only from those sides where there is no indent. Search patterns are located in the upper and left corners (3 total).

Leveling patterns

Used from the 2nd version, they are a black square with a size of 1 to 1 module, which is surrounded by a frame of white modules, which is surrounded by a frame of black modules, as a result, this pattern has a size of 5 by 5. The places where the alignment patterns are located, are shown in table 9. More precisely, there are grid nodes vertically and horizontally, where the central modules of the patterns are located. For example, if the table says 6, 22, 38, this means that the centers of the modules should be located at the following points: (6, 6), (6, 22), (6, 38), (22, 6), (22 , 22), (22, 38), (38, 6), (38, 22), (38, 38). There is one important condition: the leveling patterns should not be layered on the search patterns. That is, when the version is greater than 6, there should be no alignment patterns at the points (first, first), (first, last) and (last, first) alignment patterns. In our example, these are (6, 6), (6, 38) and (38, 6).

Sync bands

Everything is simple here. The stripes start from the lower-right black module of the upper left search pattern and go, alternating black and white modules, down and to the right to opposite search patterns. When layered on the leveling pattern, it should remain unchanged.

Version code

These elements are used starting with the 7th version. The version code is duplicated in 2 places, and it is mirrored, that is, specifying the color of the module in coordinates (x, y), you can safely specify the same color in coordinates (y, x). The modules in these places are arranged in accordance with the figure below and table 10 (1 - black, 0 - white).

Mask code and correction level

This code, as well as the previous one, is duplicated in 2 places: next to the upper left search pattern and next to the lower and right search patterns (the element has a break). In it, the mask code is ciphered in a special way (more on this later) and the code of the correction level. The finished codes are given in Table 11. The mask is determined at the very last step, when all the rest of the free space is filled with data. Due to the fact that the mask is selected on the basis of the best option (for this you need to go through all the masks), you will have to return more than once to adding the mask code and the level of correction. Do not add this item yet. The figure shows exactly where and in which direction the modules of this element are lined up, and also the module, which is always black, is marked in red.

Adding data

All the remaining free space on the canvas is divided into columns: every 2 modules, no matter what is in these modules, except for the vertical sync band, which is simply skipped. Filling starts from the bottom right corner, goes within the bounds from right to left, from bottom to top. If the current module is busy (for example, a sync stripe or an alignment pattern), then it is simply skipped. If the top of the bar is reached, the movement continues from the upper right corner of the bar, which is located to the left, and goes from top to bottom. Reaching the bottom, the movement continues from the lower right corner of the column, which is located to the left, and goes upwards. And so on, until all the free space is filled.



Filling takes place bit by bit from the data bytes, with 1 being the black module and 0 being the white. If there is not enough data, the remaining space is filled with zero modules.

In this case, one of the masks is superimposed on each module. The total number of masks is 8 pieces (from 0 to 7), their list is in table 12. If the expression from the table is zero, the color of the module is inverted, otherwise it remains unchanged. The mask applies only to data modules.



The mask is chosen in different ways: some always use the same, others are random each time, but the specification insists that each mask is evaluated and the most optimal is chosen. The method with the assessment requires more time, but there is nothing terrible if an optimal mask is not chosen, so it is not necessary to use it, but I will still tell about it. The mask code and correction level (see above) depends on the selected mask; now is the time to add this element.

Choosing the best mask

This part is optional, and if you have already decided on the choice of mask and added data to the canvas, your QR code is ready.

The essence of this procedure is to generate a QR code with each of the eight masks, to charge each penalty points according to certain rules and choose a mask with the least amount of points. Remember that together with the data, the element of the mask code and the level of correction is added to the canvas again.

Rule 1

Horizontally and vertically for every 5 or more modules of the same color running in a row, the number of points equal to the length of this section is minus 2. In this and all other rules, the indent is not considered, everything is limited to the main field.

Rule 2

For each square of modules of the same color with a size of 2 by 2, 3 points are awarded.

Rule 3

For each sequence of modules CHBCHCHBCH, with 4 white modules on one side (or from 2 at once), 40 points are added (vertically or horizontally). Simply put, for these elements:



In our example, there are only 3 such elements, for which he gets 120 additional points (these elements need not intersect with the search pattern):

Rule 4

The number of points in this step depends on the ratio of the number of black and white modules. The closer it is to the 50% to 50% ratio, the better. The first thing to do is to divide the number of black modules by the total number of modules (again, the indent is not considered).
203 / 441 = 0.46032
Then multiply the result by 100 and subtract 50.
0.46032 * 100 - 50 = -3.986
Discard the decimal part and take the number modulo.
-3.986 -> 3
Multiply the resulting number by 2.
3 * 2 = 6
Add this number to the total number of penalty points.

Total

In the end, for each mask, you will get your number of penalty points, you will only have to choose the one with less points and your QR code is completely ready. As practice shows, the lower the mask number, the greater the likelihood that it will be the best, so for optimization you can choose the best mask not from all, but, for example, from 4.

Articles taken as a basis

• QR Code Demystified - Part 1
• QR Code Demystified - Part 2
• QR Code Demystified - Part 3
• QR Code Demystified - Part 4
• QR Code Demystified - Part 5
• QR Code Demystified - Part 6