QR Codes... and all that Jazz!

This is going to be relatively challenging code-golf challenge.

Input: Any URL, must have the protocol attached, e.g. http://codegolf.stackexchange.com (which will be our test case)

Output: A generated QR Code that represents this URL, which, when scanned by a smart device will take you to that URL on the smart device's browser.

Rules for this Code-Golf

1. As usual, smallest code wins.
2. No external web resources, libraries or plugins to generate the code for you. Your code must calculate the QR code image.
3. Output can be presented by an image, generated by HTML5/CSS3, or even using appropriate Unicode blocks, or if your platform's ASCII has it available, through ASCII characters that can form the QR code (this last one is directed at Commodore 64 Basic, Amiga QBasic, Amstrad Basic, etc users), but it must generate a QR code output such that I can scan the code.
4. Entries of the code must be followed with the generated output, either by a screen shot of the output after executing your code, or with a link showing the output (whichever suits the situation best)
5. You are to test your code with the URL "http://codegolf.stackexchange.com", and report the output in accordance to Rules 3 to 4.
6. You are to also test your code with a URL of your choice, and report the output in accordance to Rules 3 to 4.

References:

5) http://www.qrstuff.com/ for inspiration... ;)

• Infinite recursion at rule 5. Feb 4 '14 at 0:50
• @ace Well spotted... this has been fixed Feb 4 '14 at 5:17
• After reading some documentation, I think "relatively challenging" is an understatement. Feb 4 '14 at 17:24
• Can we get a clarification as to what "your code must calculate the QR code image" means? I'm taking it to mean that we must do the two major points in the submitted code: 1) RS encoding, and 2) module layout. Feb 4 '14 at 20:58
• rule 3: so is ascii art printed from a terminal fine, or does it have to go into an actual image file?
– user16402
May 26 '14 at 16:52

Python 3: 974 chars [nb]

Further beat with the ugly stick, see notebook on GH-Gist. Python 3 has built-in ASCII-85 encoding, which helps with the zipped saus. 3's more advanced built-in compression algorithms (LZMA) don't seem to work well with such small things.

Zipping is very fickle about changing characters around, was almost tempted to write something that would randomly try different 1-letter names for variables to minimize the zipped size.

Python 2: 1420 1356 1085 1077 characters

I read the first argument passed when called, which can be a string up to 106-ish characters long. The output is always a version 5-L QR code and mask 4 which means it's 37x37 modules large and can only handle ~5% damage.

The program's only dependencies are numpy (array manipulations) and matplotlib (display only); all Reed-Solomon encoding, data packing, and module layout is handled within the provided code. For RS, I basically robbed the Wikiversity functions...it's still kind of a black-box for me. Learned a ton about QR in any event.

Here's the code before I beat it with the ugly stick:

import sys
import numpy as np
import matplotlib.pyplot as plt
# version 5-L ! = 108 data code words (bytes), 106 after metadata/packing

### RS code stolen from https://en.wikiversity.org/wiki/Reed%E2%80%93Solomon_codes_for_coders#RS_generator_polynomial
gf_exp = [1] + [0] * 511
gf_log = [0] * 256
x = 1
for i in range(1,255):
x <<= 1
if x & 0x100:
x ^= 0x11d
gf_exp[i] = x
gf_log[x] = i
for i in range(255,512):
gf_exp[i] = gf_exp[i-255]

def gf_mul(x,y):
if x==0 or y==0:
return 0
return gf_exp[gf_log[x] + gf_log[y]]

def main():
s = sys.argv[1]

version = 5
mode = 4 # byte mode
dim = 17 + 4 * version
datamatrix = 0.5 * np.ones((dim, dim))
nsym = 26

# PACK
msg = [mode * 16, len(s) * 16] + [ord(c) << 4 for c in s]
for i in range(1, len(msg)):
msg[i-1] += msg[i] // 256
msg[i] = msg[i] % 256

msg = (msg + pad * 54)[:108]

# MAGIC (encoding)
gen = [1]
for i in range(0, nsym):
q = [1, gf_exp[i]]
r = [0] * (len(gen)+len(q)-1)
for j in range(0, len(q)):
for i in range(0, len(gen)):
r[i+j] ^= gf_mul(gen[i], q[j])
gen = r
msg_enc = [0] * (len(msg) + nsym)
for i in range(0, len(msg)):
msg_enc[i] = msg[i]
for i in range(0, len(msg)):
coef = msg_enc[i]
if coef != 0:
for j in range(0, len(gen)):
msg_enc[i+j] ^= gf_mul(gen[j], coef)
for i in range(0, len(msg)):
msg_enc[i] = msg[i]

# PATTERN
# position marks
for _ in range(3):
datamatrix = np.rot90(datamatrix)
for i in range(4):
datamatrix[max(0, i-1):8-i, max(0, i-1):8-i] = i%2
datamatrix = np.rot90(datamatrix.T)

# alignment
for i in range(3):
datamatrix[28+i:33-i, 28+i:33-i] = (i+1)%2

# timing
for i in range(7, dim-7):
datamatrix[i, 6] = datamatrix[6, i] = (i+1)%2

# the "dark module"
datamatrix[dim-8, 8] = 1

# FORMAT INFO
ptr_ul = np.array([8, -1])
steps_ul = [0, 1] * 8 + [-1, 0] * 7
steps_ul[13] = 2 # hop over vertical timing
steps_ul[18] = -2 # then horizontal

ptr_x = np.array([dim, 8])
steps_x = [-1, 0] * 7 + [15-dim, dim-16] + [0, 1] * 7

for bit, step_ul, step_x in zip(L4, np.array(steps_ul).reshape(-1,2), np.array(steps_x).reshape(-1,2)):
ptr_ul += step_ul
ptr_x += step_x
datamatrix[tuple(ptr_ul)] = int(bit)
datamatrix[tuple(ptr_x)] = int(bit)

# FILL

cols = (dim-1)/2
cursor = np.array([dim-1, dim]) # starting off the matrix
up_col = [-1, 1, 0, -1] * dim
down_col = [1, 1, 0, -1] * dim
steps = ([0, -1] + up_col[2:] + [0, -1] + down_col[2:]) * (cols/2)
steps = np.array(steps).reshape(-1, 2)
steps = iter(steps)

# bit-ify everything
msg_enc = ''.join('{:08b}'.format(x) for x in msg_enc) + '0' * 7 # 7 0's are for padding
for bit in msg_enc:
collision = 'maybe'
while collision:
cursor += steps.next()
# skip vertical timing
if cursor[1] == 6:
cursor[1] = 5
datamatrix[tuple(cursor)] = int(bit)

# COOK
mask4 = lambda i, j: (i//2 + j//3)%2 == 0
for i in range(dim):
for j in range(dim):
datamatrix[i, j] = int(datamatrix[i, j]) ^ (1 if mask4(i, j) else 0)

# THE PRESTIGE
plt.figure(facecolor='white')
plt.imshow(datamatrix, cmap=plt.cm.gray_r, interpolation='nearest')
plt.axis('off')
plt.show()

if __name__ == '__main__':
main()


After:

import sys
from pylab import*
n=range
l=len
E=[1]+[0]*511
L=[0]*256
x=1
for i in n(1,255):
x<<=1
if x&256:x^=285
E[i]=x;L[x]=i
for i in n(255,512):E[i]=E[i-255]
def f(x,y):
if x*y==0:return 0
return E[L[x]+L[y]]
m=sys.argv[1]
m=[ord(c)*16 for c in'\4'+chr(l(m))+m]
for i in n(1,l(m)):m[i-1]+=m[i]/256;m[i]=m[i]%256
m=(m+[236,17]*54)[:108]
g=[1]
for i in n(26):
q=[1,E[i]]
r=[0]*(l(g)+l(q)-1)
for j in n(l(q)):
for i in n(l(g)):r[i+j]^=f(g[i],q[j])
g=r
e=[0]*134
for i in n(108):
e[i]=m[i]
for i in n(108):
c=e[i]
if c:
for j in n(l(g)):e[i+j]^=f(g[j],c)
for i in n(108):e[i]=m[i]
m=.1*ones((37,)*2)
for _ in n(3):
m=rot90(m)
for i in n(4):m[max(0,i-1):8-i,max(0,i-1):8-i]=i%2
m=rot90(m.T)
for i in n(3):m[28+i:33-i,28+i:33-i]=(i+1)%2
for i in n(7,30):m[i,6]=m[6,i]=(i+1)%2
m[29,8]=1
a=array
t=tuple
g=int
r=lambda x:iter(a(x).reshape(-1,2))
p=a([8,-1])
s=[0,1]*8+[-1,0]*7
s[13]=2
s[18]=-2
P=a([37,8])
S=[-1,0]*7+[-22,21]+[0,1]*7
for b,q,Q in zip(bin(32170)[2:],r(s),r(S)):p+=q;P+=Q;m[t(p)]=g(b);m[t(P)]=g(b)
D=m==0.1
c=a([36,37])
s=r(([0,-1]+([-1,1,0,-1]*37)[2:]+[0,-1]+([1,1,0,-1]*37)[2:])*9)
for b in ''.join('{:08b}'.format(x) for x in e):
k=3
while k:
c+=s.next()
if c[1]==6:c[1]=5
k=not D[t(c)]
m[t(c)]=g(b)
a=n(37)
for i in a:
for j in a:
if D[i,j]:m[i,j]=g(m[i,j])^(j%3==0)
imshow(m,cmap=cm.gray_r);show()


(relying on a tab to count as 4/8/whatever number of spaces >= 2., not sure how well it will copy)

Because it's so long, we can zip it (saw someone do this somewhere else, forgot who though :( ) to save some more characters, bringing the total down to 1085 1077 because pylab is filthy:

import zlib,base64
exec zlib.decompress(base64.b64decode('eJxtU0tzmzAQvvSkX6FLaglkyiM2hHRvyS2HZNobo3QwwY6IBVjQFrfT/96V3KR4Wg5I+/6+3ZXSfWdGOhwHsjWdpv1xX26oclqPtGDKdleTPezrltxCEUm/CKW3iiJyB/YWr9ZkgohsO0MVVS1tWSTi1YrnhE4fP6KFqi2d3qNfPj1CnK0IvS2UhOn6rpgkqHkkxolVFPPceeBviRpJnuot3bJJHG1Sm807AoS5qcevpqUhoX9ut4VN6d8VRymJBuQUlGb3DUGjVHTmiVXci9bUVqyw4uLdwq+eDdszzbmv5TkJp801gkDSgKf8gCSu7cVJF5a6Bqb9Ik7WIkqxLZe8yKMwk2RnW3VGbW3BH1AtLDmJoF3/sPiO+3t24MuIEwetOUVYnY3Bb5bHuvPcFMpv5CNs2Q6TiUPRSAzegSG1yxoll2dkwsxmql+h/8dWgbW69lY5favazKvWs6qNFBX/J8/fChqCyOvaemAsSQX34pPzl5NzYktqMN14FWKbyZzhpW26LicWCmw9z7OlEucibs1FTN7Cg89nQBIbH2e+ypMEQ99uEpjyI46RM+dUJKEbslhb4Gsxc8MsVyKTuMIllMaURzLC+LXf1zhd1Y7EwL7Um6eSTrkaa8NKNvHA1MNz2ddsia+Ac9JDyYpM4ApxMuBoRCS9zC/QilNKyVBEiYTYnlhoGZN7648Ny9D/E7z6YUAci9g9PpshdRQ24iAeLI0fqmcbhczjKA15EedSGDZw/H3CqfU+HK7vfXjA1R1ZzyXs2IY74f6PQG5A44sKIlK5+muRpA6wYQwr2gfALBZEYwUvSV0V/832j4l7V6ehbCzAxSJoOgS4+JmH2ebXIkCLLkfslxv8ZH1quxIvkBD6/Vnta/pyWv3KhyFo62lk3Ml2P/FpAaxzd66c9gXabqQ3SKniuMT6dDlxKwE7k85WpMxn76zMX9Pe4BI00u1CY0NPF/7ImosEm8OJ0sNz951pUemyh0oHO9yJL4ZfOzX/DQ2mdSs='))


If you replace the last line with the following (it adds 62 chars), you get nearly-perfect output, but the other still scans, so whatever.

figure(facecolor='white');imshow(m,cmap=cm.gray_r,interpolation='nearest');axis('off');show()


• Great job! It's a pity that Python isn't the best in golfing solutions, but this is remarkable coding, @NickT! Feb 5 '14 at 21:57
• I could probably save some more if I lose the struct call and some unnecessary bit pushing by just truncating my 'master string'... Feb 13 '14 at 3:50
• FYI the second indentation level can be just two spaces. I've noticed that you use four/tab. Oct 21 '14 at 6:45
• @BetaDecay it's supposed to just be 1 tab (1 tab > 1 space as far as indenting is concerned...I think SE breaks tabs?) Oct 21 '14 at 7:13
• @NickT yeah, it does. Mar 30 '16 at 22:35