QR: Quick Response quite reasonable; quirkily rectangular

[SJT]

Turning a URL into a QR (Quick Response) code is an illuminating exercise. 

Following the description of the algorithm posted by Vidurangi Kalpana, and setting aside the business of representing a boolean matrix in print or on a screen, the steps are:

1. Generate a hash of the argument string as ASCII codes
2. Represent each character as a 3×3 boolean matrix
3. Represent the Position Identification Square (PIS) as four numbers
4. Arrange the ASCII and PIS numbers as a 2-D QR code
5. Map each number to a 3×3 boolean matrix

The result will be an 18×18 boolean matrix for a URL of ≤20 chars; a 36×36 matrix for a URL of 25-132 chars.

Hashing the URL

To encode a string to a QR code, first, you need to hash the string and convert it to a fixed-length string. For the smaller QR version (input string less than or equal to 20) you need to hash the string to 24 characters and for the larger version (input string greater than 20) you need to hash the string to 132 characters. Follow the steps below to get the hashed string.

The ASCII value of the first character of the hashed string = Length of the input string + 50 (which is used for decoding purposes).

Assume the length of the string is L. Then, the next L characters of the hashed string should be the characters of the input string. To fill the remaining characters (this part of string is used for error detection), add 1 to the ASCII values of characters in the input string and append them to the string until you reach the desired length. Do this by incrementing the number you are adding by 1 in each round until all the required number of characters is obtained. Then reverse the error detection part of the hashed string. 

Observe the given example:

Input string: ABCDEFGH

First character = 50 + 8

[…]

58 65 66 67 68 69 70 71 72 73 72 71 70 69 68 67 73 72 71 70 69 68 67 66
:  A  B  C  D  E  F  G  H  I  H  G  F  E  D  C  I  H  G  F  E  D  C  B

None of this seems hard in q. The hash starts:

q){("c"$50+count x),x}"ABCDEFGH"
":ABCDEFGH"

The rump is for error correction and is slightly more interesting.

q)"c"$reverse raze{{x+1+til count x}cx cut(-1+24 132[20<cx]-cx:count x)#x}"j"$"ABCDEFGH"
"IHGFEDCIHGFEDCB"

Tempting to just join the two strings. But we can do better. To start with, we don’t need the chars to proceed: we can do everything we need in ASCII codes. 

q){(cx+50),x,reverse raze{x+1+til count x}cx cut(24 132[20<cx]-1+cx:count x)#x}"j"$"ABCDEFGH"
58 65 66 67 68 69 70 71 72 73 72 71 70 69 68 67 73 72 71 70 69 68 67 66

And that x could just as well be x+0 as long as we make sure not to reverse it.

q)show H:{(L+50),(L#s),reverse L _ s:raze{x+til count x}L cut(24 132[20<L:count x]-1)#x}"j"$"ABCDEFGH"
58 65 66 67 68 69 70 71 72 73 72 71 70 69 68 67 73 72 71 70 69 68 67 66

Mapping chars to bitmaps

Mapping chars to 3×3 bit matrices begins with encoding them to 9-bit vectors.

q)flip(9#2)vs"j"$"ABCD"
0 0 1 0 0 0 0 0 1
0 0 1 0 0 0 0 1 0
0 0 1 0 0 0 0 1 1
0 0 1 0 0 0 1 0 0
q)3 3#first flip(9#2)vs"j"$"ABCD"  / "A"
0 0 1
0 0 0
0 0 1

We can defer reshaping the bit vectors into matrices until the last step.

Position Identification Square

Each QR Code has 3 Position identification squares (6×6 unit squares) in 3 corners. They should be drawn in the pattern given below.

The remaining area is for character encoding, which is divided into small squares. (of size 3×3 unit squares each).

Each small square represents one character of the hashed string.

The PIS occupies the same space as four ASCII characters. It consists of four rotations of the same 3×3 bitmap. (Rotation is flip reverse.)

q)(111b;100b;101b)                    / top left quarter
111b
100b
101b
q)3(flip reverse@)\(111b;100b;101b)  / quarters clockwise
111b 100b 101b
111b 001b 101b
101b 001b 111b
101b 100b 111b

Encoded as decimals:

q)2 sv'raze each 3(flip reverse@)\(111b;100b;101b)
485 461 335 359

That gives the PIS as (485 461;359 335)code>. (In Take, not clockwise order.)

Arrange codes in a QR pattern

There are two QR patterns: for short and long strings:

A brief inspection discovers that in each case this is the bulk of the hash as a square, with the rest arranged with PIS copies at the top and left. 

Partition the hash accordingly.

q)gl:6*20<count "ABCDEFGH"  / go large?
q)show parts:`body`top`left!raze each (0,4 5+gl) _ (4+gl)cut H
body| 58 65 66 67 68 69 70 71 72 73 72 71 70 69 68 67
top | 73 72 71 70
left| 69 68 67 66
q)show shp:`top`left!1 reverse\2,2+lf
top | 2 2
left| 2 2

And assemble from the parts.

q)PIS:(485 461;359 335)  / Position Identification Square
q)body:(2#4+lf)#parts`body
q)top:(shp[`top]#parts`top),'PIS
q)left:PIS,(shp[`left]#parts`left),PIS
q)show mat:left,'top,body
485 461 73 72 485 461
359 335 71 70 359 335
69  68  58 65 66  67
67  66  68 69 70  71
485 461 72 73 72  71
359 335 70 69 68  67

Mapping the numbers to bitmaps

Represent each number as a bit vector.

q)show lbv:flip(9#2)vs raze mat  / list of bit vectors
1 1 1 1 0 0 1 0 1
1 1 1 0 0 1 1 0 1
0 0 1 0 0 1 0 0 1
0 0 1 0 0 1 0 0 0
..

Reshape each bit vector as a 3×3 matrix, then cut the list of them into a 6- or 10-column matrix.

q)(6+lf) cut 3 3#/:lbv
1 1 1 1 0 0 1 0 1 1 1 1 0 0 1 1 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 1 0..
1 0 1 1 0 0 1 1 1 1 0 1 0 0 1 1 1 1 0 0 1 0 0 0 1 1 1 0 0 1 0 0 0 1 1 0 1 0 1 1 0 0 1 1..
0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 1 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1..
0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 1..
1 1 1 1 0 0 1 0 1 1 1 1 0 0 1 1 0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0..
1 0 1 1 0 0 1 1 1 1 0 1 0 0 1 1 1 1 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0..

Each item above represents a row of the 6×6 QR code pattern. Here’s the first row:

q)first (6+lf) cut 3 3#/:lbv
1 1 1 1 0 0 1 0 1
1 1 1 0 0 1 1 0 1
0 0 1 0 0 1 0 0 1
0 0 1 0 0 1 0 0 0
1 1 1 1 0 0 1 0 1
1 1 1 0 0 1 1 0 1

And in its first item we can see the bitmap for the top-left quarter of the PIS.

q)first first (6+lf) cut 3 3#/:lbv
1 1 1
1 0 0
1 0 1

So far, so good. To line everything up, we apply (raze')flip to each row – and raze the result.

q)raze((raze')flip@)each (6+lf) cut 3 3#/:lbv
1 1 1 1 1 1 0 0 1 0 0 1 1 1 1 1 1 1
1 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 1
1 0 1 1 0 1 0 0 1 0 0 0 1 0 1 1 0 1
1 0 1 1 0 1 0 0 1 0 0 1 1 0 1 1 0 1
1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1
0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1
0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0
1 0 1 1 0 0 0 1 0 0 0 1 0 1 0 0 1 1
0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 0 1 0 1 0 0 1 0 1 1 1 0 1 1 1
1 1 1 1 1 1 0 0 1 0 0 1 0 0 1 0 0 1
1 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0
1 0 1 1 0 1 0 0 0 0 0 1 0 0 0 1 1 1
1 0 1 1 0 1 0 0 1 0 0 1 0 0 1 0 0 1
1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 0 1 0 1 1 0 0 0 1 1

Above we can make out the PIS patterns in the first three corners. Easier to see as a char matrix:

q)".#"raze((raze')flip@)each (6+lf) cut 3 3#/:lbv
"######..#..#######"
"#....#..#..##....#"
"#.##.#..#...#.##.#"
"#.##.#..#..##.##.#"
"#....#......#....#"
"###########.######"
"..#..#.....#..#..#"
"......###........."
"#.##...#...#.#..##"
"..#..#..#..#..#..#"
".................."
".##.#.#..#.###.###"
"######..#..#..#..#"
"#....#..#..#..#..."
"#.##.#.....#...###"
"#.##.#..#..#..#..#"
"#....#............"
"########.#.##...##"

Lastly we need a border of blanks, a subject investigated in Flouring the loaf. 

qrc:{ / QR code bits from string x
  gl:6*large:20<L:count x;                                      / go large?
  hsh:(L+50),{(x#y),reverse x _ y}[L] raze
    {x+til count x}L cut(23 131@large)#"i"$x;                   / hash of ASCII codes
  parts:`body`top`left!raze each (0,4 5+gl)_(4+gl)cut hsh;
  PIS:(485 461;359 335);                                        / Position Identification Square                                                    
  body:(2#4+gl)#parts`body;
  shp:`top`left!1 reverse\2,2+gl;
  top:(shp[`top]#parts`top),'PIS;
  left:PIS,(shp[`left]#parts`left),PIS;
  mat:left,'top,body;                                           / numeric matrix
  lbv:flip(9#2)vs raze mat;                                     / list of bit vectors
  / map to 3x3 blocks and border 
  bm:raze((raze')flip@)each (6+gl) cut 3 3#/:lbv;
  4(reverse flip,[;0b]@)/bm }

Challenges

1. How can qrc be improved?
2. Write crq to take a 18×18 or 36×36 bitmap as above and return a string. (Extra credit for discovering and ignoring a white border.)

[LeahS]

Super @SJT 👏

Make sure you haven't missed Flouring-the-loaf 

Best of luck with the challenges!

[rocuinneagain]

You can use ASCII escape code colours to get a more familiar output

qrEcho:{{-1 raze (("\033[47m  ";"\033[40m  ") x),"\033[0m"} each x;}

[SJT]

Blimey. Thanks, Rian. 

But pretty as the pattern is, my phone mutely declines to recognise it as a URL. 

Nor does forcing it into the larger format produce a pattern it recognises. Which leaves me wondering: what is the real algorithm?

This tutorial describes a significantly more complicated procedure. More later.