Ја имам 15 година и написао сам генератор QR кодова користећи Rust

Здраво, желео бих да вам испричам како сам научио да програмирам на Rust-у од нуле, за ово сам одабрао циљ да направим генератор QR кодова, уз помоћ ментора из слободне школе “Пионир”.

Пионир је слободна, самоуправна и бесплатна школа у којој ми, ученици, учимо и стварамо пројекте који су усмерени ка решавању неких друштвених проблема.

Пре свега, зашто сам изабрао Rust? Желео сам да пробам нешто ново, писао сам на једноставном Python-у, без искуства са нечим тежим и сложенијим, и такође овај језик изгледа обећавајуће и занимљиво.

Одабрао сам QR код енкодер као пројекат због чињенице да овај пројекат није толико компликован и да ћу моћи да се добро упознам са основама Rust-а.

Такође, због чињенице да имамо планове за будућност у вези са 2Д кодовима, желео сам да научим из овог пројекта: како да радим са битовима, са матрицом, рад са Rust-ом и његовим библиотекама, Рид-Соломон алгоритам и алгоритме за исправљање грешака.

Шта је QR код и како га генерисати? QR код (Quick Response code) је дводимензионални баркод који чува неке информације и, због блокова за претрагу, лако се чита помоћу скенера.

QR кодови су добри јер се брзо читају и чувају велику количину информација, такође користећи Рид-Соломон алгоритам, QR кодови могу да исправе грешке до 30%.

Да бисте генерисали QR код, потребно је да прођете кроз ове кораке:

• Кодирање података.
• Додавање сервисних информација и попуњавање.
• Раздвајање информација у блокове.
• Креирање корективних бајтова.
• Комбиновање блокова.
• Енкодирање информација на QR код.

Moja одлука

Имао сам различите идеје о архитектури свог генератора, али сам изабрао ону која је по мом мишљењу најједноставнија и најразумљивија.

Моја идеја је да постоје четири главне структуре:

• QrMatrix ⏤ главна матрица, која ће се састојати од модула и може се мењати помоћу координата.
• DataBitvec ⏤ конвертује стринг у вектор бита користећи кодирање и додаје исправку грешака, која ће затим бити послата на DataEncoder.
• DataEncoder ⏤ Ова структура ће кодирати податке у QrMatrix користећи ZigZagIt итератор.
• QrBuilder ⏤ примање као поље QrMatrix, додаје му све основне елементе, кодира информације и ствара маску.

Ове основне структуре међусобно делују у структури QrBuilder и као резултат, добија се готова матрица QR кода, која ће на крају једноставно приказати QR код.

QrMatrix

На почетку за QrMatrix хтео сам да направим сопствену структуру података, која би се једноставно састојала од једног Vec<Vec<Module>> и могао бих да урадим све промене користећи функцију претраживања модула по координатама, али сам мислио да не вреди да измишљам топлу воду, па сам користио библиотеку generic-matrix.

Уз помоћ size креира се матрица size x size и попуњава се модулима. Модул је enum, који је направљен да одвоји функционалне блокове од обичнe информацијe, тако да је много практичнији и не постоји начин да се функционални блокови мењају.

Reserved у модулу се не користи у мојој структури због чињенице да је потребно да се информациони блокови не попуњавају док се не пронађе најбоља маска за QR код, у мом случају сам ово прескочио и увек користим једну маску.

Да бисте променили модуле у матрици, постоје функције:

А да бих приказао QR код, користио сам терминал:

			1.habrahabr!

Овако изгледа коначни QR код.

FinderBuilder и TimingBuilder

Да генеришем блокове претраге у QR коду, направио сам константу у облику низа:

Пошто увек постоје три обрасца претраге и њихове почетне координате је лако израчунати, мислио сам да нема смисла генерисати директно у QrMatrix, и просто константу `FINDER_BLOCК`` ротирамо и убацујемо на одређеним координатама.

Прављење синхроних трака је много лакше, њихове координате су увек познате и дужина се лако може сазнати:

Пошто трака увек почиње са белим модулом, променом вредности на супротну сваком окрету, можете добити вектор са исправним модулима за синхроне пруге.

DataEncoder

Да бисте нешто кодирали у QR код, прво морате конвертовати дати низ у вектор битова, за то се користе кодне стране која могу прихватити различите знакове:

• Нумеричко кодирање ⏤ кодира само бројеве, користи се 10 бита по 3 знака.
• Алфанумеричко кодирање ⏤ кодира велика латинична слова, цифре, $%*+-./: знакове и размак.
• Кодирање бајтова ⏤ иако има малу густину информација, може да кодира било који знак (на пример, у UTF-8).

Постоји и канџи кодирање за далекоазијска писма и друге знакове, али нисам урадио имплементацију за ову кодну страну зато што ми није била потребна.

За чување битова и за њихову згодну употребу користио сам библиотеку bit-vec. Такође, за згодан рад са информацијама, креирао сам структуру QrCodeBitvec која има три поља: поље за чување сервисних информација (тип кодирања и број знакова), поље за чување података и поље за чување бајтова за исправљање грешака.

Као пример, да бих показао како овај систем функционише, кодирам број 1234 у QR код.

Прво, оно што треба да урадите је да сазнате који тип кодирања да користите и колико знакова по реду. У нашем случају, то је тип нумеричног кодирања и дужина је 4, а ово се конвертује у BitVec:

0001 0000000100

За дужину карактера у нумеричном кодирању користи се 10 битова.

Сада треба да конвертујемо број 1234 у нумерично кодирање. Ово се ради прилично једноставно, подељимо број у групе од 3 броја ⏤ 123 и 4, затим се ови бројеви конвертују у BitVec, 10 бита се користи за бројеве веће од 99, 7 бита се користи за бројеве веће од 9 и 4 бита за мање од 9.

Сада добијамо ово:

0001 0000000100 0001111011 0100

Сада имамо BitVec са дужином од 28 бита, али спецификација QR кодова вас приморава да у потпуности попуните податке, у нашем случају морамо да попунимо овај BitVec до 152 бита. Да бисмо то урадили, морамо да урадимо три ствари:

• Додамо терминатор ⏤ попуњава 4 бита нулама.
• Додамо нуле тако да BitVec може бити дељиви са 8.
• Затим циклично и наизменично додајте 2 бајта ⏤ 11101100 и 00010001.

Ове радње се морају извршити све док количина података не буде једнака 152.

Овако ће подаци изгледати на крају:

0001 0000000100 0001111011 0100 0000<11101100 и 00010001 до краја>

Ови подаци су спремни за слање Рид-Соломон алгоритму.

Рид-Соломон алгоритам за исправљање грешака

За овај алгоритам користио сам библиотеку reed-solomon.

Не знам добро како овај алгоритам функционише са математичке стране, али сам покушао да бар разумем логику овог алгоритма, као и да га исправно користим за овај генератор. Особа која је такође креирала генератор QR кодова написала je своју имплементацију овог алгоритма, али ми се овај код није допао, због лоших назива и чудне структуре кода који су ми отежавали разумевање логике његовог алгоритма, а такође није било много смисла у томе, па сам oдбацио ову идеју и само узео готову библиотеку.

Наше податке, свих 152 бита, шаљемо у Encoder структуру ове библиотеке. Ова структура прихвата једну вредност ⏤ број бајтова корекције, за прву верзију QR кода са нивоом корекције L користи се 7 бајтова корекције:

А затим, претварајући бајтове из BitVec-а у децималне бројеве, шаљемо ове бројеве у структуру кодера:

Добили смо 7 бајтова за исправљање грешака, за прву верзију само убацујемо ове бајтове за исправку на крај BitVec-а:

0001 0000000100 0001111011 0100 0000<11101100 и 00010001 до краја података><7 бајтова корекције>

Ове готове податке кодирамо у QR код.

ZigZagIt и DataEncoder

Да кодирам информације у QR код, направио сам итератор који ће дати координате почевши од доње десне стране. Померањем цик-цак и прескакањем функционалних блокова како их не бисмо мењали, добићемо исправне координате за убацивање информација:

И сада, идемо дуж BitVec-а и убацујемо битове у координате, добијамо QR код са тачним подацима, сада само треба да маскирамо податке и добијамо готов радни QR код.

Овако ће изгледати број 1234 у првој верзији, са нивоом корекције L и са првом маском.

Закључак

Уз помоћ овог пројекта научио сам много корисних ствари, барем сам почео боље да разумем програмирање и научио да пишем на Rust-у, али имам простора да растем и заиста бих волео да се даље развијам у програмирању.

У будућности имамо планове да креирамо друге занимљиве пројекте, на пример, да направимо поларну 2Д матрицу кода која ће изгледати као ShotCode али ће бити ефикаснији.

Ако имате било какве савете или проблеме које треба решити у мом коду, слободно их поделите. Ако желите да видите цео код, ево мог репозиторија на GitHub.

Подржите нас

Наша школа је непрофитна и ученици је сами граде и одржавају, па ако вам се мој пројекат свидео, можете подржати школу како бисмо наставили да радимо и развијамо интересантне пројекте у будућности.

Идите на Пиониров OpenCollective где можете да нас подржите безбедно и транспарентно својом картицом или PayPal-ом, или нам пошаљите XMR на 46WXVvyNhwXAaon7XoAWbJcs1UKDJC7m4c9631N28v6pghJs1zzypsWEH2Wi3LFJkC3o9D4BGZi1v9fBo3XrsujoJ9Psm6j или $ETH на pionir.eth.