Hello, I would like to tell you about how I learned to program in Rust from scratch, for this I chose the goal of making a QR code encoder, with the help of a mentor from Pionir Free School.
Pionir Free School is a self-managed free school in which we, students, study and create projects with a principal emphasis on solving communal and social problems.
First of all, why did I choose Rust? Firstly, I wanted to try something new, I used to write in simple Python, having no experience with something more low-level and complex, and secondly, this language looks promising and interesting.
I chose QR code encoder as a project due to the fact that this project is not so complicated, and I will be able to get familiar with the basics of Rust.
Also, due to the fact that we have plans for the future related to 2D codes, I wanted to learn from this project: how to work with bits, with matrices, work with Rust and its libraries, the Reed-Solomon error correction algorithm and algorithms for error correction in general.
What is a QR code and how to generate it? QR code (Quick Response code) is a two-dimensional barcode that stores some information and, with the help of search patterns, is easily read using scanners.
QR codes are good because they are quickly read and store a large amount of information, also using the Reed-Solomon algorithm, QR codes can correct errors up to 30%.
To generate a QR code, you need to go through these steps:
- Data encoding.
- Adding service information and filling.
- Separation of information into blocks.
- Creation of correction bytes.
- Combining blocks.
- Placement of information on the QR code.
My decision regarding architecture
I had different ideas about the architecture of my generator, but I chose the one that in my opinion is the simplest and most understandable.
My idea is that there are four main structures:
- QrMatrix ⏤ the main matrix, which will consist of modules and can be changed using coordinates.
- DataBitvec ⏤ converts the string to a bit vector using an encoding and adds error correction, which will then be sent toDataEncoder.
- DataEncoder ⏤ this structure will encode the data inQrMatrix using the ZigZagIt iterator.
- QrBuilder ⏤ receiving as fieldQrMatrix, it adds all the basic elements to it, encodes the information and creates a mask
These basic structures interact with each other in the structure QrBuilder and as a result, a ready-made QR code matrix is obtained, which at the end will simply display a QR code.
QrMatrix
At the beginning for QrMatrix I wanted to create my own data structure, which would simply consist of one Vec<Vec
With the help of size, a matrix of size size x size is created and filled with modules. A module is an enum, which is made to separate function blocks from ordinary information, so it is much more convenient and there is no way to change function blocks.
Reserved in the module is not used in my structure due to the fact that it is needed so that the information blocks are not filled until the best mask for the QR code is found, in my case I skipped this, and always use one mask.
To change the modules in the matrix, there are functions:
And to display the QR code, I used the terminal:
1. habrahabr!
This is how the final QR code looks like.
FinderBuilder and TimingBuilder
To generate search patterns in a QR code, I created a constant in the form of an array:
Since there are always three search patterns and their initial coordinates are easy to calculate, I thought that it makes no sense to generate directly in QrMatrix, and simply the constant FINDER_BLOCK rotated and inserted entirely at certain coordinates.
Creating synchronous lanes is much easier, their coordinates are always known and the length can be easily found out:
Since the stripe always starts with a white module, by changing the value to the opposite each turn, you can get a vector with the correct modules for synchronous stripes.
DataEncoder
In order to encode something into a QR code, you must first convert the given string into a bit vector, for this, encodings are used that can accept different characters:
- Numeric Encoding ⏤ encodes only numbers, 10 bits per 3 characters is used.
- Alphanumeric encoding ⏤ encodes uppercase Latin letters, digits, $%*+-./: characters, and space.
- Byte encoding ⏤ although it has a low information density, it can encode any character (for example, in UTF-8).
There is also a kanji encoding for CJK and other characters, but I missed this encoding.
For storing bits and for their convenient use, I used the library bit_thing. Also, for convenient work with information, I created a QrCodeBitvec structure that has three fields: a field for storing service information (encoding type and number of characters), a field for storing data, and a field for storing error correction bytes.
As an example, to show how this system works, I encode the number 1234 into a QR code.
First, what you need to do is find out what type of encoding to use and how many characters per line. In our case, it is a digital encoding type and character length 4, and this is converted to BitVec:
0001 0000000100
For the length of characters in digital encoding, 10 bits are used.
Now, we need to convert the number 1234 into digital encoding. This is done quite simply, divided into groups of 3 numbers ⏤ 123 and 4, then these numbers are converted to BitVec, 10 bits are used for numbers greater than 99, 7 bits are used for numbers greater than 9 and 4 bits for less than 9.
Now we get this:
0001 0000000100 0001111011 0100
Now we have BitVec with a length of 28 bits, but the specification QR codes forces you to fill in the data completely, in our case we need to fill this BitVec to 152 bits. To do this, we need to do three things:
- Add terminator ⏤ fills 4 bits with zeros.
- Pad the data with zeros so it can be divisible by 8.
- Then cyclically and alternately add 2 bytes ⏤ 11101100 and 00010001.
These actions must be done until the amount of data is equal to 152.
This is what the data will look like at the end:
0001 0000000100 0001111011 0100 0000<11101100 and 00010001 to end>
This data is ready to be sent to the Reed-Solomon algorithm.
Reed-Solomon algorithm
For this algorithm I used the library reed-solomon.
I do not know very well how this algorithm works from the mathematical side, but I tried to at least understand the logic of this algorithm, as well as use it correctly for this generator. The person who also created the QR code generator wrote his implementation of this algorithm, but I didn’t like this code, because naming was bads and a strange code structure made it difficult to understand the logic of its algorithm, and there was also not much sense in it, so I discarded this idea and just took a ready-made library.
Our data, all 152 bits, we send the structure of this library to the Encoder. This structure accepts one value ⏤ the number of correction bytes, for the first version of the QR code with correction level L, 7 correction bytes are used:
And then, converting bytes from BitVec to decimal numbers, we send these code words to the Encoder structure:
We got 7 error correction bytes, for the first version we just insert these correction bytes at the end of BitVec:
0001 0000000100 0001111011 0100 0000<11101100 and 00010001 to end of data><7 correction bytes>
We encode this ready-made data with a QR code.
ZIG_ZAG_IT и DATA_ENCODER
To encode information into a QR code, I created an iterator that will give coordinates starting from the bottom right side. By moving in a zigzag way and skipping the function blocks so as not to change them, we will get the correct coordinates for inserting information:
And now, going along BitVec and inserting bits into the coordinates, we get a QR code with the correct data, now we just have to mask the data and we get a ready-made working QR code.
This is how the number 1234 will look like in the first version, with the correction level L and with the first mask.
Conclusion
With the help of this project, I learned a lot of useful things, at least I began to understand programming better and learned to write in Rust, but I have room to grow and I would really like to develop further in programming.
In the future, we have plans to create other interesting projects, for example, to create a polar 2D code matrix that will look like ShotCode but will be more efficient.
If you have any tips or problems to solve in my code, feel free to share them. If you want to see the whole code, here is my repository at GitHub.
Donate and support
Our school is non-profit and we, the students, are maintaining and building it, so if you like my project, you can donate to us and support our work and future projects.
Go to OpenCollective Pionir where you can safely and transparently donate via card or PayPal, or send us some $XMR to 46WXVvyNhwXAaon7XoAWbJcs1UKDJC7m4c9631N28v6pghJs1zzypsWEH2Wi3LFJkC3o9D4BGZi1v9fBo3XrsujoJ9Psm6j or $ETH to pionir.eth.