# An artisanal QR code

Article published in PagedOut! issue #2.

## Data to encode

Encoding of "PagedOut!" results in 16 bytes of data:

```binary:
mode|length   |P        |a        |g        |e        |d        |O        |u        |t        |!        |padding
0100 0000 1001 0101 0000 0110 0001 0110 0111 0110 0101 0110 0100 0100 1111 0111 0101 0111 0100 0010 0001 0000 1110 1100 0001 0001 1110 1100 0001 0001 1110 1100

hex:
0x40      0x95      0x6       0x16      0x76      0x56      0x44      0xf7      0x57      0x42      0x10      0xec      0x11      0xec      0x11      0xec

dec:
64,149,6,22,118,86,68,247,87,66,16,236,17,236,17,236
```

## Reed-Solomon Error Correcting Code (ECC)

The article contains a JavaScript snippet to compute the Reed-Solomon ECC. Here, we can see the same calculation being performed using middle school style long division. We use xor instead of substraction. It is feasible to perform these calculations using just pen and paper.

We are going to divide by [1,216,194,159,111,199,94,95,113,157,193] (the divisor can be computed or we can look up appendix A in the standard and use a log table).

note: the powers of x have been omitted — the notation 1, 2, 3, ... is actually 1*x^25 + 2*x^24 + 3*x^23...

```
---------------------------------------------------------------------------------------------------------
1,216,194,159,111,199,94,95,113,157,193 |   64,149,  6, 22,118, 86, 68,247, 87, 66, 16,236, 17,236, 17,236,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0
^  64,  4,202, 20,194,151, 30, 94, 17,148, 10     <= if computing by hand, the multiplication of the divisor
-------------------------------------------        is easiest to compute with log/antilog tables.
145,204,  2,180,193, 90,169, 70,214, 26,236
^ 145,209,247,178, 72, 24,235,122, 16,141, 89
-------------------------------------------
29,245,  6,137, 66, 66, 60,198,151,181, 17
^  29, 16, 15, 80, 47,102,120,101, 68,106, 40
-------------------------------------------
229,  9,217,109, 36, 68,163,211,223, 57,236
^ 229,145,203,239,244,157, 22,243, 29, 56,249
-------------------------------------------
152, 18,130,208,217,181, 32,194,  1, 21, 17
^ 152,135,107,161,120,169,127,231,206,140,222
-------------------------------------------
149,233,113,161, 28, 95, 37,207,153,207,236
^ 149,150,216,244,233, 35,142, 27,201,195,122
-------------------------------------------
127,169, 85,245,124,171,212, 80, 12,150,  0
^ 127,187, 57,109, 82,167,213,170, 49,147,184
-------------------------------------------
18,108,152, 46, 12,  1,250, 61,  5,184,  0
^  18,172, 37, 38, 96,127, 53, 39,161,  2, 19
-------------------------------------------
192,189,  8,108,126,207, 26,164,186, 19,  0
^ 192, 12, 67, 60, 91,164, 34,226, 51,161, 30
-------------------------------------------
177, 75, 80, 37,107, 56, 70,137,178, 30,  0
^ 177,211,146,184, 41,221,228, 85,150,199, 92
-------------------------------------------
152,194,157, 66,229,162,220, 36,217, 92,  0
^ 152,135,107,161,120,169,127,231,206,140,222
-------------------------------------------
69,246,227,157, 11,163,195, 23,208,222,  0
^  69,155, 39,205, 12,107, 37, 96,185, 71,232
-------------------------------------------
109,196, 80,  7,200,230,119,105,153,232,  0
^ 109, 23, 28, 75, 50,216,224,141,144,145,171
-------------------------------------------
211, 76, 76,250, 62,151,228,  9,121,171,  0
^ 211,120,164,133, 84, 28, 73,154,227, 62,204
-------------------------------------------
52,232,127,106,139,173,147,154,149,204,  0
^  52, 68,246, 73,126, 18,227,215, 28, 33,170
-------------------------------------------
172,137, 35,245,191,112, 77,137,237,170,  0
^ 172,195,157,232,  6,187,156, 48,210,173,116
-------------------------------------------
74,190, 29,185,203,209,185, 63,  7,116 <= our error correcting code
```

Note: these multiplications and divisions using xor are basic Galois Field operations. If you understand these, you can perform AES encryption or decryption by hand — AES requires similar operations in addition to swapping bytes around using predefined tables.

## BCH Correcting Code

Similarly to above, we can use long division with xor to calculate the BCH correcting code.

```data = 00101
divisor = 10100110111

-----------------
10100110111 | 001010000000000
^ 10100110111
-----------
0000011011100  <= remainder

data + remainder = 001010011011100