Привет, я бы хотел вам рассказать о том, как я учился программировать на языке Rust с нуля, для этого я выбрал цель — сделать QR-код-энкодер с помощью ментора из свободной школы «Пионир».
Пионир — это свободная, самоуправляемая и бесплатная школа в которой мы, ученики, изучаем и создаём проекты, которые решают какие-то социальные проблемы.
Для начала, почему я выбрал Rust? Во-первых, я хотел попробовать что-то новое, раньше я писал на простом Python, не имея опыта с чем-то более низкоуровневым и сложным, и во-вторых, этот язык выглядит перспективным и интересным.
QR-код-энкодер я выбрал из-за того, что этот проект не настолько сложный, и я смогу хорошо ознакомиться с основами Rust-а.
Также из-за того, что у нас есть планы на будущее, связанные с 2D-кодами, я хотел из этого проекта научиться, как работать с битами, с матрицей, с Rust-ом и его библиотеками, алгоритмом Рида-Соломона и с алгоритмами для исправления ошибок.
Что же такое QR-код, и как его генерировать? QR-код(Quick Response code) — это двухмерный штрихкод, который хранит в себе какую-то информацию и с помощью поисковых узоров легко считывается сканерами.
QR-коды хороши тем, что они быстро считываются и сохраняют большое количество информации, также с помощью алгоритма Рида-Соломона QR-коды могут скорректировать ошибки до 30%.
Для генерации QR кода нужно пройти вот эти этапы:
Кодирование данных.
Добавление служебной информации и заполнения.
Разделение информации на блоки.
Создание байтов коррекции.
Объединение блоков.
Размещение информации на QR-коде.
Моё решение
У меня были разные идеи по поводу архитектуры моего генератора, но я выбрал ту, которая, по моему мнению, самая простая и понятная.
Моя идея заключается в том, что существует четыре основные структуры:
QrMatrix ⏤ основная матрица, которая будет состоять из модулей, и её можно изменять с помощью координат.
DataBitvec ⏤ конвертирует строку в битовый вектор с помощью кодировки и добавляет коррекцию ошибок, которая дальше будет посылаться в DataEncoder.
DataEncoder ⏤ эта структура будет энкодировать данные в QrMatrix c помощью итератора ZigZagIt.
QrBuilder ⏤ получая как поле QrMatrix, он добавляет в него все базовые элементы, энкодирует информацию и создаёт маску.
Эти основные структуры взаимодействуют друг с другом в структуре QrBuilder, и в итоге получается готовая QR-код-матрица, которая в конце просто изобразит QR-код.
QrMatrix
В начале для QrMatrix я хотел создать свою структуру данных, которая бы просто состояла из Vec<Vec<Module>> ,и я мог делать все изменения с помощью функции поиска модулей по координатам, но я подумал, что не стоит изобретать велосипед, поэтому использовал библиотеку generic-matrix.
#[derive(Debug)] pub struct QrMatrix { size: usize, modules: Matrix<Module>, } impl QrMatrix { pub fn new(size: usize) -> Self { let to_matrix_vec: Vec<Module> = vec![Module::Unknown; size * size]; let modules: Matrix<Module> = Matrix::from_vec(size, size, to_matrix_vec); QrMatrix { size, modules } }
С помощью size создаётся матрица размером size x size и заполняется модулями. Модуль — это enum, который сделан, чтобы отделить функциональные блоки от обычной информации, так гораздо удобнее и нет возможности изменить функциональные блоки.
#[derive(Clone, Copy, PartialEq, Debug)] pub enum Module { Unknown, //Reserved, Data(bool), Function(bool), } impl Module { pub fn set_module(&mut self, new_module: Module) { *self = new_module; } pub fn is_fun(&self) -> bool { match self { Module::Function(_) => return true, _ => return false, } } pub fn flip_module(&mut self) { match self { Self::Data(true) => *self = Self::Data(false), Self::Data(false) => *self = Self::Data(true), _ => (), } } }
Reserved в модуле не используется в моей структуре: он нужен, для того чтобы информационные блоки были не заполнены до тех пор, пока не найдена лучшая маска для QR-кода, в моём случае я пропустил это, и всегда использую одну маску.
Для изменения модулей в матрице есть функции:
pub fn set_square(&mut self, size: usize, cordinate: (usize, usize), matrix_module: &mut Matrix<Module>) { let start_width: usize = cordinate.1; let start_height: usize = cordinate.0; for i in 0..size { for j in 0..size { let new_module = matrix_module.index_mut((i, j)); self.set_module((i + start_height, j + start_width), *new_module); } } } pub fn set_module(&mut self, cordinate: (usize, usize), new_module: Module) { let mut _module: &mut Module = self.get_mut_module(cordinate); _module.set_module(new_module); }
А для отображения QR-кода я использовал терминал:
FinderBuilder and TimingBuilder
Для генерации поисковых узоров в QR коде я создал константу в виде массива:
pub const FINDER_BLOCK: [[i32; FINDER_SIZE]; FINDER_SIZE] = [[1, 1, 1, 1, 1, 1, 1, 0], [1, 0, 0, 0, 0, 0, 1, 0], [1, 0, 1, 1, 1, 0, 1, 0], [1, 0, 1, 1, 1, 0, 1, 0], [1, 0, 1, 1, 1, 0, 1, 0], [1, 0, 0, 0, 0, 0, 1, 0], [1, 1, 1, 1, 1, 1, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0]];
Так как поисковых ��зоров всегда три, и их начальные координаты легко вычислить, я подумал, что нет смысла генерировать напрямую в QrMatrix, и просто константу FINDER_BLOCК ротировал и вставлял целиком в определённые координаты.
Создание синхронных полос же намного легче, их координаты всегда известны, и длину можно легко узнать:
fn get_size_timing(&self) -> usize { return self.matrix.get_size() - 2 * FINDER_SIZE; }
Так как полоса всегда начинается с белого модуля, каждый ход меняя значение на противоположное, можно получить вектор с правильными модулями для синхронных полос.
DataEncoder
Для того чтобы что-то энкодировать в QR-код, нужно сперва конвертировать заданную строку в битовый вектор, для этого используются кодировки, которые могут принять в себя разные символы:
Цифровое кодирование ⏤ кодирует только цифры, используется 10 битов на 3 символа.
Буквенно-цифровое кодирование ⏤ кодирует прописные буквы латинского алфавита, цифры символы $%*+-./: и пробел.
Побайтовое кодирование ⏤ хоть и имеет маленькую плотность информации, может кодировать любой символ(например, в UTF-8).
Существует еще кодирование кандзи для иероглифов и других символов, но его я пропустил.
Для хранения битов и для их удобного использования я использовал библиотеку bit_vec. Также для удобной работы с информацией я создал структуру QrCodeBitvec , которая имеет три поля: для хранения служебной информации (тип кодировки и количество символов), для хранения данных и для хранения байтов коррекции ошибок.
Для примера, чтобы показать, как работает эта система, я энкодирую число 1234 в QR-код.
Сперва, то что нужно сделать, — это узнать, какой тип кодировки стоит использовать и какое количество символов в строке. В нашем случае это цифровой тип кодировки и длина символов 4, и это преобразуется в BitVec:0001 0000000100
Для длины символов в цифровом кодировании используется 10 битов.
Теперь надо конвертировать число 1234 в цифровую кодировку. Это делается довольно просто: делится на группы по 3 числа ⏤ 123 и 4 — потом эти числа конвертируются в BitVec, для чисел больше 99 используется 10 битов, для чисел больше 9 — 7 битов и 4 битов для меньших, чем 9.
Теперь мы получаем вот это:
0001 0000000100 0001111011 0100
fn generate_bitvec(integer: u32) -> BitVec { let bit_len = |num: u32| { if num > 99 { return 10; } else if num > 9 { return 7; } else { return 4; } }; let mut bitvector: BitVec = BitVec::new(); bitvector.reserve(bit_len(integer)); append_to_bitvec(&mut bitvector, &integer, bit_len(integer)); return bitvector; }
Вот сейчас мы получили BitVec длиной 28 битов, но спецификация QR-кодов заставляет заполнять данные полностью, в нашем случае нужно заполнить этотBitVec до 152 битов. Чтобы это сделать, нам нужны три действия:
Добавить терминатор ⏤ заполняет 4 бита нулями.
Заполнить данные нулями, чтобы они могли делиться на 8.
Дальше циклично и поочерёдно добавлять 2 байта ⏤ 11101100 и 00010001.
Эти действия нужно выполнять, пока количество данных не будет равно 152.
Вот так будут выглядеть данные в конце:
0001 0000000100 0001111011 0100 0000<11101100 и 00010001 до конца>
Эти данные готовы для отправления в алгоритм Рида-Соломона.
Алгоритм Рида-Соломона
Для этого алгоритма я использовал библиотеку reed-solomon.
Я не особо хорошо знаю, как этот алгоритм работает с математической стороны, но я пытался хотя бы понять его логику, а также её правильно использовать для этого генератора. Человек, который также создавал генератор QR-кода написал свою имплементацию этого алгоритма, но этот код мне не понравился, плохие наименования и странная структура мешали понимать логику его алгоритма, а также в этом не было много смысла, поэтому я отбросил эту идею и просто взял готовую библиотеку.
Наши данные, все 152 бита, мы отправляем в Encoder-структуру этой библиотеки. Эта структура принимает в себя одно значение ⏤ количество байтов коррекции, для первой версии QR-кода с уровнем коррекции L используется 7 байтов коррекции:
fn create_reed_solomon_encoder(num_error_correction_blocks: usize) -> Encoder { let reed_encoder: Encoder = Encoder::new(num_error_correction_blocks); return reed_encoder; }
И потом, конвертируя байты из BitVec в десятичные числа, мы шлём эти кодовые слова в структуру Encoder:
pub fn create_error_corrections_blocks(data: Vec<u8>, num_error_correction_blocks: usize) -> Vec<u8> { let reed_encoder: Encoder = Self::create_reed_solomon_encoder(num_error_correction_blocks); let data_copy = reed_encoder.encode(&data).to_vec(); return data_copy; }
Вставляем эти байты коррекции в конецBitVec-а:
0001 0000000100 0001111011 0100 0000<11101100 и 00010001 до конца данных><7 байтов коррекции>
Эти готовые данные мы энкодируем в QR-код.
ZigZagIt и DataEncoder
Для энкодирования информации в QR код я создал итератор, который будет давать координаты, начиная с нижней правой стороны. Двигаясь зигзагообразно и пропуская функциональные блоки, чтобы их не изменить, мы получим правильные координаты для вставки информации:
impl Iterator for ZigZagIt { type Item = (usize, usize); fn next(&mut self) -> Option<Self::Item> { if !self.valid { return None; } let cordinates: (usize, usize) = (self.row_cordinate, self.column_cordinate); self.move_cordinate(); return Some(cordinates); } }
fn move_horizontaly(&mut self) { match self.column_cordinate { 0 => self.valid = false, 6 => self.column_cordinate -= 2, _ => self.column_cordinate -= 1, } self.horizontaly_next = false; } fn move_vertical(&mut self) { if (self.upward && self.row_cordinate == 0) || (!self.upward && self.row_cordinate == self.matrix_size - 1) { self.upward = !self.upward; self.move_horizontaly(); } else { if self.upward { self.row_cordinate -= 1 } else if !self.upward { self.row_cordinate += 1 } self.column_cordinate += 1; } self.horizontaly_next = true; }
И теперь, идя по BitVec-у и вставляя в координаты биты, мы получаем QR-код с правильными данными, теперь мы должны просто маскировать их, и получаем готовый, рабочий QR-код.
Вот так будет выглядеть число 1234 в первой версии, с уровнем коррекции L и с первой маской.
Заключение
С помощью этого проекта я выучил много полезного, как минимум, я начал лучше понимать программирование и научился писать на Rust, но мне есть, куда расти, и я бы очень хотел дальше развиваться в программировании.
В дальнейшем у нас есть планы создавать и другие интересные проекты, например — полярную 2D-код-матрицу, которая будет похожа на ShotCode, но более эффективную.
Если у вас есть советы или проблемы, которые стоит решить в моём коде, свободно рассказывайте о них. Если захотите увидеть целый код, вот мой репозиторий на GitHub.
