Мне 15 лет и я написал QR код генератор на Rust

Привет, я бы хотел вам рассказать о том, как я учился программировать на языке 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.