
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:
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.
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 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.
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.)
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
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 }
qrc
be improved?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.)You must be a registered user to add a comment. If you've already registered, sign in. Otherwise, register and sign in.
EMEA
Tel: +44 (0)28 3025 2242
AMERICAS
Tel: +1 (212) 447 6700
APAC
Tel: +61 (0)2 9236 5700
KX. All Rights Reserved.
KX and kdb+ are registered trademarks of KX Systems, Inc., a subsidiary of FD Technologies plc.