# Optimize [QR code generation](https://www.nayuki.io/page/creating-a-qr-code-step-by-step) programs (tweaked for srv32, RV32IM) contributed by < [`eeeXun`](https://github.com/eeeXun) > ## GF multiplication > Reference from [Galois Field Youtube](https://www.youtube.com/watch?v=x1v2tX4_dkQ) and [Stack Exchange](https://math.stackexchange.com/a/89904) The elements in Galois Field are $GF(2^m)=\{0,1,2,\ldots,2^m-1\}$ Suppose we want to mutiply two polynomials $a(x)$ and $b(x)$, where $a(x)=\sum_{i=0}^7a_ix^i$ and $b(x)=\sum_{i=0}^7b_ix^i$ in $GF(2^8)$. And primitive polynomial is $p(x)=x^8+x^4+x^3+x^2+1$. Then we have the following multiplication result. $$ \begin{align*} c(x)&=a(x)b(x)\bmod p(x) \\ &=(\sum_{i=0}^7a_ix^i)b(x)\bmod p(x) \\ &= [a_0x^0b(x)+a_1x^1b(x)+\ldots+a_6x^6b(x)+a_7x^7b(x)]\bmod p(x) \\ &=a_0b(x)+a_1[xb(x)\bmod p(x)]+\ldots \\ &\quad\ldots+a_6[x(x^5b(x)\bmod p(x))\bmod p(x)]+a_7[x(x^6b(x)\bmod p(x))\bmod p(x)] \\ \end{align*} $$ From above equation, we can have Galois Field multiplication in C code > Reference from [jevillegasd/GF2-8](https://github.com/jevillegasd/GF2-8/blob/master/gf28.cpp#L16-L25) ```c= uint8_t gf_mul(uint8_t x, uint8_t y) { uint8_t z = 0; for (int i = 0; i < 8; i++) { if (x & 1) z ^= y; if (y & 0x80) y = (y << 1) ^ 0x1D; else y <<= 1; x >>= 1; } return z; } ``` Line 6 to line 9 corresponds to $x(x^ib(x))$ in above equation. We want to multiply $x^ib(x)$ with $x$, but we also need to check if the result is out of field. If it is out of field, then we have to take the remainder modulo primitive polynomial. At this point, I still couldn't get the principle of the multiplication in [qrcode](https://github.com/sysprog21/rv32emu/blob/master/tests/qrcode.c#L262-L272) ```c= static inline uint _rs_mul(uint x, uint y) { uint z = 0; /* This is called (133, 340, 825) times in V(1, 2, 3) ECC calculation. */ for (int i = 7; i >= 0; i--) { /* And this body is run 1064, 2720, 6600 times. */ z = (z << 1) ^ ((z >> 7) * 0x11D); z ^= ((y >> i) & 1) * x; } return z; } ``` ## GF multiplication LUT > Reference from [Youtube](https://www.youtube.com/watch?v=TK_GjqFbpNo) and [Wikipedia](https://en.wikipedia.org/wiki/Primitive_polynomial_(field_theory)#Field_element_representation) If $\alpha$ is root of primitive polynomial, we can represent $GF(2^m)$ with $$ GF(2^m)=\{0,1=\alpha^0,\alpha,\alpha^2,\ldots,\alpha^m-2\} $$ In our case, we use $GF(2^8)$. We can represent it as $\{0,1,\alpha,\alpha^2,\ldots,\alpha^{254}\}$. And primitive polynomial is $p(x)=x^8+x^4+x^3+x^2+1$, so $$ \begin{align*} p(\alpha)=0&=\alpha^8+\alpha^4+\alpha^3+\alpha^2+1 \\ \alpha^8&=\alpha^4+\alpha^3+\alpha^2+1=\textbf{29} \end{align*} $$ For the power greater than 8, we can apply the above result $$ \begin{align*} \alpha^9&=\alpha\times \alpha^8=\alpha^5+\alpha^4+\alpha^3+\alpha=\textbf{58} \\ \alpha^{10}&=\alpha\times \alpha^9=\alpha^6+\alpha^5+\alpha^4+\alpha^2=\textbf{116} \\ \alpha^{11}&=\alpha\times \alpha^{10}=\alpha^7+\alpha^6+\alpha^5+\alpha^3=\textbf{232} \\ \alpha^{12}&=\alpha\times \alpha^{11}=\alpha^8+\alpha^7+\alpha^6+\alpha^4 \\ &=(\alpha^4+\alpha^3+\alpha^2+1)+\alpha^7+\alpha^6+\alpha^4 \\ &=\alpha^7+\alpha^6+\alpha^3+\alpha^2+1=\textbf{205} \\ \alpha^{13}&=\ldots \\ \vdots \\ \alpha^{254}&=\ldots \\ &=\alpha^7+\alpha^3+\alpha^2+\alpha=\textbf{142} \\ \alpha^{255}&=\alpha\times \alpha^{254}=\alpha^8+\alpha^4+\alpha^3+\alpha^2 \\ &=(\alpha^4+\alpha^3+\alpha^2+1)+\alpha^4+\alpha^3+\alpha^2 \\ &=\textbf{1} \end{align*} $$ So if we want to multiply two number $a$ and $b$, we need to find out the corresponding $a'$ and $b'$ that $\alpha^{a'}=a$ and $\alpha^{b'}=b$ in Galois Field. Then multiply it $$ a\times b=\alpha^{a'}\times \alpha^{b'}=\alpha^{a'+b'} $$ If $a'+b'$ is greater than 255, we have to minus 255(or modulo 255). Because it is in Galois Field. Finally, the value of $GF(\alpha^{(a'+b')\mod 255})$ is what we want. You could find the table at this [blog](https://www.thonky.com/qr-code-tutorial/log-antilog-table). ## QRCode Structure > Reference from [Youtube](https://www.youtube.com/watch?v=142TGhaTMtI) and this [blog](https://www.thonky.com/qr-code-tutorial/) ### finder patterns It is used to detect position and rotation of QR Code ![image](https://hackmd.io/_uploads/HJIKamdu6.png) ### timing patterns It alternates between two colors at the size of 1 pixel. It allows the reader to confirm the QR code [version](https://en.wikipedia.org/wiki/QR_code#Information_capacity) ![image](https://hackmd.io/_uploads/ByyERQu_a.png) ### format bits #### ECC level There are 4 levels of [Error Correction](https://en.wikipedia.org/wiki/QR_code#Error_correction) - L(Low): 7% data restoration, represented by `01` - M(Medium): 15% data restoration, represented by `00` - Q(Quartile): 25% data restoration, represented by `11` - H(High): 30% data restoration, represented by `11` ![image](https://hackmd.io/_uploads/rk1xlVO_T.png) #### mask pattern There 8 types of mask pattern. The mask are used to mask(XOR) the data. > Reference from this [blog](https://www.thonky.com/qr-code-tutorial/mask-patterns) - pattern `(row + column) mod 2 == 0` - `000` - pattern `(row) mod 2 == 0` - `001` - pattern `(column) mod 3 == 0` - `010` - pattern `(row + column) mod 3 == 0` - `011` - pattern `(floor(row / 2) + floor(column / 3)) mod 2 == 0` - `100` - pattern `((row * column) mod 2) + ((row * column) mod 3) == 0` - `101` - pattern `(((row * column) mod 2) + ((row * column) mod 3) ) mod 2 == 0` - `110` - pattern `(((row + column) mod 2) + ((row * column) mod 3) ) mod 2 == 0` - `111` ![image](https://hackmd.io/_uploads/BJnlUV__6.png) :::info We can't directly take ECC level and mask pattern mentioned above as final output. There is something to do with error correction and XOR. ::: #### format error correction This is error correction for 5 bits of ECC level and mask pattern ![image](https://hackmd.io/_uploads/ByOQbNF_T.png) #### Example > Reference this [blog](https://www.thonky.com/qr-code-tutorial/format-version-information#generate-error-correction-bits-for-format-string) and [Youtube CRC](https://www.youtube.com/watch?v=A9g6rTMblz4) Suppose we use low level of error correction and mask pattern `000`. Then we have five bits `01000` format string. The generator polynomial of QR code specification is $x^{10}+x^8+x^5+x^4+x^2+x+1$. We can represent it as `10100110111` 1. Given the generator polynomial is `10100110111` and data `01000`, find out the CRC - `01000` is $0x^4+x^3+0x^2+0x+0$ - multiply `01000` with $x^{10}$, the result is $x^{13}$, `010000000000000` - Take the result from previous step to modulo generator polynomial. Get $x^9+x^8+x^7+x^6+x^4+x^2+x$ (`1111010110`) 2. Combine 5 bits of error correction and mask with 10 bits of CRC. Get `010001111010110` 3. XOR 15 bits from step 2 with `101010000010010`. Then the final output is `111011111000100` Place final 15 bits from step 3 with following order ![image](https://hackmd.io/_uploads/S18m8hid6.png) #### single bit This bit is always 1 ![image](https://hackmd.io/_uploads/HJSsMNtdp.png) ### data Data is palced in zigzag pattern ![image](https://hackmd.io/_uploads/rJonuwFdT.png) #### encoding mode These 4 bits indicate the encoding mode for message. Enconding mode includes Numeric, Alphanumeric, Byte, Kanji, etc. ![image](https://hackmd.io/_uploads/rkVWFvtdT.png) #### message length This byte indicates the length of message ![image](https://hackmd.io/_uploads/HydDeuK_p.png) #### message We place data in zigzag pattern as mentioned above ![image](https://hackmd.io/_uploads/ryK3qDYOa.png) #### end of message The end of data is represented wiht 4 bits of 0 ![image](https://hackmd.io/_uploads/SJD7hwK_a.png) #### paddings The number of codewords is fixed in QR code. You could check out [here](https://www.thonky.com/qr-code-tutorial/error-correction-table). Let's take QR code version 1 with low level of error correction for example. The number of codewords is 19 bytes, including encoding mode, message length, message and end of message. If the message length is less than 19 bytes, you have to add padding with `0xEC` and `0x11` alternately until it reaches 19 bytes. #### ECC The remaining bytes are used for error correction. QR code uses [Reed-Solomon error correction](https://en.wikipedia.org/wiki/QR_code#Error_correction) ![image](https://hackmd.io/_uploads/S1Im1dY_a.png) Finally, we have to mask the data according the mask pattern #### Example > Reference from this [blog](https://www.thonky.com/qr-code-tutorial/error-correction-coding#step-7-understanding-the-generator-polynomial) Given the QR code version 1 with mideum level of error correction. The generator polynomial is $$ g(x)=x^{10}+\alpha^{251}x^9+\alpha^{67}x^8+\alpha^{46}x^7+\alpha^{61}x^6+\alpha^{118}x^5+\alpha^{70}x^4+\alpha^{64}x^3+\alpha^{94}x^2+\alpha^{32}x+\alpha^{45} $$ You could find the generator polynomial [here](https://www.thonky.com/qr-code-tutorial/generator-polynomial-tool). We encode message `hello world` with byte mode. We have the following data | encode mode | message length | message | end of message | paddings | | :---------: | :------------: | :------------------------------------------------------------------------------------------------------------------------------: | :------------: | :------------------------------: | | 0100 | 00001011 | 01101000<br>01100101<br>01101100<br>01101100<br>01101111<br>00100000<br>01110111<br>01101111<br>01110010<br>01101100<br>01100100 | 0000 | 11101100<br>00010001<br>11101100 | Then values presented in 16 bytes | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | | 64 | 182 | 134 | 86 | 198 | 198 | 242 | 7 | | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | | 118 | 247 | 38 | 198 | 64 | 236 | 17 | 236 | So the message polynomial is $$ \begin{align*} m(x)&=64x^{15}+182x^{14}+134x^{13}+86x^{12}+198x^{11}+198x^{10}+242x^9+7x^8 \\ &+118x^7+247x^6+38x^5+198x^4+64x^3+236x^2+17x+236 \end{align*} $$ First multiply message polynomial with $x^n$, where $n$ is is highest exponent of $g(x)$. In our case, we have to multiply $x^{10}$. So we get $$ \begin{align*} m(x)=x^{10}m(x)&=64x^{25}+182x^{24}+134x^{23}+86x^{22}+198x^{21}+198x^{20}+242x^{19}+7x^{18} \\ &+118x^{17}+247x^{16}+38x^{15}+198x^{14}+64x^{13}+236x^{12}+17x^{11}+236x^{10} \end{align*} $$ Then, we want to get remainder of $m(x)$ divide by $g(x)$ 1. Step1 a. Multiply Generator Polynomial with $x^{15}$ so it has the same exponent as Message Polynomial b. Multiply the Generator Polynomial by the Lead Term of the Message Polynomial. The leader term is $64x^{25}$. And $64=\alpha^6$. So multiply generator polynomial with $\alpha^6$ $$ \begin{align*} &\alpha^{6}x^{25}+\alpha^{257\mod 255}x^{24}+\alpha^{73}x^{23}+\alpha^{52}x^{22}+\alpha^{67}x^{21}+\alpha^{124}x^{20}+\alpha^{76}x^{19}+\alpha^{70}x^{18}+\alpha^{100}x^{17}+\alpha^{38}x^{16}+\alpha^5x^{15} \\ =&\alpha^{6}x^{25}+\alpha^2x^{24}+\alpha^{73}x^{23}+\alpha^{52}x^{22}+\alpha^{67}x^{21}+\alpha^{124}x^{20}+\alpha^{76}x^{19}+\alpha^{70}x^{18}+\alpha^{100}x^{17}+\alpha^{38}x^{16}+\alpha^5x^{15} \end{align*} $$ Convert it into integer notation $$ 64x^{25}+4x^{24}+202x^{23}+20x^{22}+194x^{21}+151x^{20}+30x^{19}+94x^{18}+17x^{17}+148x^{16}+32x^{15} $$ c. XOR the result with the message polynomial $$ \begin{align*} &(64\oplus 64)x^{25}+(4\oplus 182)x^{24}+(202\oplus 134)x^{23}+(20\oplus 86)x^{22}+(194\oplus 198)x^{21} \\ &+(151\oplus 198)x^{20}+(30\oplus 242)x^{19}+(94\oplus 7)x^{18}+(17\oplus 118)x^{17}+(148\oplus 247)x^{16} \\ &+(32\oplus 38)x^{15}+(0\oplus 198)x^{14}+(0\oplus 64)x^{13}+(0\oplus 236)x^{12}+(0\oplus 17)x^{11}+(0\oplus 236)x^{10} \\ m(x)=&178x^{24}+76x^{23}+66x^{22}+4x^{21}+81x^{20}+236x^{19}+89x^{18}+103x^{17} \\ &+99x^{16}+6x^{15}+198x^{14}+64x^{13}+236x^{12}+17x^{11}+236x^{10} \end{align*} $$ 2. Step 2 a. Multiply Generator Polynomial with $x^{14}$ so it has the same exponent as Message Polynomial b. Multiply the Generator Polynomial by the Lead Term of the Message Polynomial. The leader term is $178x^{24}$. And $178=\alpha^{211}$. So multiply generator polynomial with $\alpha^{211}$ $$ \ldots $$ c. XOR the result with the message polynomial $$ \ldots $$ 3. $\ldots$ $\vdots$ Finally, we will get the remainder $$ 57x^9+58x^8+220x^7+32x^6+213x^5+8x^4+197x^3+250x^2+63x+193 $$ And `57 58 220 32 213 8 197 250 63 193` are our error correction codewords. ## srv32 ### Build Install RISCV toolchains from [Github](https://github.com/xpack-dev-tools/riscv-none-elf-gcc-xpack/releases) Build rvsim ```sh git clone https://github.com/kuopinghsu/srv32.git cd srv32 export CROSS_COMPILE=riscv-none-elf- export EXTRA_CFLAGS="-misa-spec=2.2 -march=rv32im" make build ``` The simulator is located at `tool/rvsim` ### Run QR code Create folder `qrcode` under `srv32/sw`. Put `qrcode.c` under `srv32/sw/qrcode` and create `Makefile`. ```makefile! include ../common/Makefile.common EXE = .elf SRC = qrcode.c CFLAGS += -L../common LDFLAGS += -T ../common/default.ld TARGET = qrcode OUTPUT = $(TARGET)$(EXE) .PHONY: all clean all: $(TARGET) $(TARGET): $(SRC) $(CC) $(CFLAGS) -o $(OUTPUT) $(SRC) $(LDFLAGS) $(OBJDUMP) -d $(OUTPUT) > $(TARGET).dis $(READELF) -a $(OUTPUT) > $(TARGET).symbol clean: $(RM) *.o $(OUTPUT) $(TARGET).dis $(TARGET).symbol ``` Run simulator ```sh tools/rvsim sw/qrcode/qrcode.elf ``` :::warning Lack of improvements. e.g., pipeline-specific tweaks. :::