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:
- Generate a hash of the argument string as ASCII codes
- Represent each character as a 3×3 boolean matrix
- Represent the Position Identification Square (PIS) as four numbers
- Arrange the ASCII and PIS numbers as a 2-D QR code
- 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 dont 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:bodytopleft!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)#partsbody q)top:(shp[top]#partstop),'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. Heres 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:bodytopleft!raze each (0,4 5+gl)_(4+gl)cut hsh; PIS:(485 461;359 335); / Position Identification Square body:(2#4+gl)#partsbody; shp:topleft!1 reverse\2,2+gl; top:(shp[top]#partstop),'PIS; left:PIS,(shp[left]#partsleft),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
- How can
qrcbe improved? - Write
crqto take a 18×18 or 36×36 bitmap as above and return a string. (Extra credit for discovering and ignoring a white border.)