Skip to content

Instantly share code, notes, and snippets.

@kig

kig/jsdecode.html

Created November 6, 2015 04:34
Show Gist options
  • Save kig/0f620414b614afd2e3a5 to your computer and use it in GitHub Desktop.
Save kig/0f620414b614afd2e3a5 to your computer and use it in GitHub Desktop.
Download ZIP
Buggy feature-free JavaScript QR decoder
Raw
jsdecode.html
<html>
<body>
<script>
var QRDecoder = function(imageData) {
this.imageData = imageData;
this.imageBits = new Int8Array(QRDecoder.MAX_SIZE * QRDecoder.MAX_SIZE);
this.decodedBits = new Uint8Array( (QRDecoder.MAX_SIZE * QRDecoder.MAX_SIZE) >> 3 );
this.size = -1;
this.ecc = -1;
this.mask = -1;
};
QRDecoder.MIN_SIZE = 21;
QRDecoder.MAX_SIZE = 177;
QRDecoder.prototype.setSize = function(size) {
this.size = size;
this.alignmentCoords = [];
if (size > QRDecoder.MIN_SIZE) {
var version = (size - QRDecoder.MIN_SIZE) / 4 + 1;
this.version = version;
var divs = 2 + (version / 7) | 0;
var total_dist = size - 7 - 6;
var divisor = 2 * (divs - 1);
var step = ((((total_dist + (divisor / 2) | 0) + 1) / divisor) | 0) * 2;
this.alignmentCoords.push(6);
for (var i=divs-2; i >= 0; i--) {
this.alignmentCoords.push(size - 7 - i * step)
}
}
};
QRDecoder.prototype.maskAlignmentPatterns = function() {
var size = this.size;
for (var i=0; i<this.alignmentCoords.length; i++) {
for (var j=0; j<this.alignmentCoords.length; j++) {
var x = this.alignmentCoords[i];
var y = this.alignmentCoords[j];
if (
(x < 9 && y < 9) || // Skip top-left marker
(x < 9 && y > this.size-9) || // Skip bottom-left marker
(x > this.size-8 && y < 9) // Skip top-right marker
) {
// skip
} else {
for (var py=-2; py<3; py++) {
for (var px=-2; px<3; px++) {
this.negateBit(x+px, y+py);
}
}
}
}
}
for (var y=0; y<9; y++) {
for (var x=0; x<9; x++) {
this.negateBit(x, y);
}
}
for (var y=0; y<9; y++) {
for (var x=size-8; x<size; x++) {
this.negateBit(x, y);
}
}
for (var y=size-8; y<size; y++) {
for (var x=0; x<9; x++) {
this.negateBit(x, y);
}
}
for (var x=0; x<size; x++) {
this.negateBit(x, 6);
}
for (var y=0; y<size; y++) {
this.negateBit(6, y);
}
if (this.version >= 7) {
for (var y=0; y<3; y++) {
for (var x=0; x<7; x++) {
this.negateBit(x, y+size-11);
}
}
for (var y=0; y<7; y++) {
for (var x=0; x<3; x++) {
this.negateBit(x+size-11, y);
}
}
}
};
QRDecoder.prototype.negateBit = function(x,y) {
if (this.imageBits[y*this.size + x] < 0) return;
this.imageBits[y*this.size + x] *= -1;
this.imageBits[y*this.size + x] += -1;
};
QRDecoder.prototype.getBit = function(x,y){
return this.imageBits[y*this.size + x];
};
QRDecoder.prototype.setBit = function(x,y,v){
this.imageBits[y*this.size + x] = v;
};
QRDecoder.prototype.getMaskBit = function(x,y) {
switch (this.mask) {
case 0: return ((x+y)%2)^1;
case 1: return (y%2)^1;
case 2: return (x%3) === 0 ? 1 : 0;
case 3: return ((x+y)%3 === 0) ? 1 : 0;
case 4: return (((y/2 | 0) + (x/3 | 0)) % 2)^1;
case 5: return ((y*x)%2 + (y*x)%3) === 0 ? 1 : 0;
case 6: return (((y*x)%2 + (y*x)%3) % 2) ^ 1;
case 7: return (((y+x)%2 + (y*x)%3) % 2) ^ 1;
default:
return 0;
}
};
QRDecoder.prototype.getMaskedBit = function(x,y) {
var mb = this.getMaskBit(x,y);
var bb = this.imageBits[y*this.size + x];
var b = bb^mb;
// if (this.ctx) {
// if (mb) {
// this.ctx.fillStyle = 'rgba('+ (this.readIdx%256) +',0,'+ (255-this.readIdx%256) + ',1)';
// } else {
// this.ctx.fillStyle = 'rgba('+ (this.readIdx%256) +','+ (255-this.readIdx%256) + ', 255,1)';
// }
// this.readIdx++;
// this.ctx.fillRect(x*4, y*4, 4, 4);
// }
return b;
};
QRDecoder.prototype.getFormat = function() {
var ecc = ((this.getBit(0, 8)^1) << 1) + this.getBit(1, 8);
var mask =
((this.getBit(2, 8)^1) << 2) +
(this.getBit(3, 8) << 1) +
(this.getBit(4, 8)^1);
this.ecc = ecc;
this.mask = mask;
};
QRDecoder.prototype.notOnAlignmentMarker = function(x, y) {
return this.getBit(x,y) !== -1;
}
QRDecoder.prototype.readDecodedBits = function() {
this.readIdx = 0;
var readBits = this.decodedBits;
for (var i=0; i<readBits.length; i++) {
readBits[i] = 0;
}
var x = this.size - 1;
var y = this.size - 1;
var dir = -1;
var off = 0;
var boff = 0;
var bit = -1;
this.firstEncoding = (
(this.getMaskedBit(x,y) << 3) +
(this.getMaskedBit(x-1,y) << 2) +
(this.getMaskedBit(x,y-1) << 1) +
(this.getMaskedBit(x-1,y-1))
);
y -= 2;
while (x > 0) {
if (y === 6) { // Skip horizontal timing sequence
y += dir;
}
bit = this.getMaskedBit(x, y);
if (bit >= 0) {
boff = off >> 3;
readBits[boff] += bit << (7 - (off-boff*8));
off++;
}
bit = this.getMaskedBit(x-1, y);
if (bit >= 0) {
boff = off >> 3;
readBits[boff] += bit << (7 - (off-boff*8));
off++;
}
y += dir;
if (y < 0 || y >= this.size) { // Reverse reading direction at top and bottom of marker
dir *= -1;
y += dir;
x -= 2;
if (x === 6) { // Skip vertical timing sequence
x--;
}
}
}
this.bitLength = off;
this.bitOffset = 0;
};
QRDecoder.prototype.readBits = function(n) {
if (n === 8 && (this.bitOffset & 7) === 0) {
var b = this.decodedBits[this.bitOffset >> 3];
this.bitOffset += 8;
return b;
}
var b = 0;
var boff = 0;
for (var i=0; i<n; i++) {
b <<= 1;
boff = this.bitOffset >> 3;
b += (this.decodedBits[boff] >> (7-(this.bitOffset-boff*8))) & 1;
this.bitOffset++;
}
return b;
};
QRDecoder.prototype.decodeNumeric = function() {
var lengthBits = 10;
if (this.version >= 27) {
lengthBits = 14;
} else if (this.version >= 10) {
lengthBits = 12;
}
var length = this.readBits(lengthBits);
var message = '';
for (var i=0; i<length/3; i++) {
var num = this.readBits(10);
if (num < 10) {
message += '00'+num.toString();
} else if (num < 100) {
message += '0'+num.toString();
} else {
message += num.toString();
}
}
return {
encoding: 1,
length: length,
message: message
};
};
QRDecoder.ALPHANUMERIC_TABLE = [
'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F',
'G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V',
'W','X','Y','Z',' ','$','%','*','+','-','.','/',':'
];
QRDecoder.prototype.decodeAlphanumeric = function() {
var lengthBits = 9;
if (this.version >= 27) {
lengthBits = 13;
} else if (this.version >= 10) {
lengthBits = 11;
}
var length = this.readBits(lengthBits);
var message = '';
for (var i=0; i<length; i+=2) {
if (i === length-1) {
var c1 = this.readBits(6);
message += QRDecoder.ALPHANUMERIC_TABLE[c1];
} else {
var chars = this.readBits(11);
var c1 = (chars / 45) | 0;
message += QRDecoder.ALPHANUMERIC_TABLE[c1];
var c2 = chars % 45;
message += QRDecoder.ALPHANUMERIC_TABLE[c2];
}
}
return {
encoding: 2,
length: length,
message: message
};
};
QRDecoder.prototype.decodeKanji = function() {
var lengthBits = 8;
if (this.version >= 27) {
lengthBits = 12;
} else if (this.version >= 10) {
lengthBits = 10;
}
var length = this.readBits(lengthBits);
return null;
};
QRDecoder.prototype.decodeByte = function() {
var lengthBits = 8;
if (this.version >= 27) {
lengthBits = 16;
} else if (this.version >= 10) {
lengthBits = 16;
}
var length = this.readBits(lengthBits);
var message = '';
for (var i=0; i<length; i++) {
message += String.fromCharCode(this.readBits(8));
}
return {
encoding: 4,
length: length,
message: message
};
};
QRDecoder.prototype.parseBits = function(bits) {
var packets = [];
var encoding = this.firstEncoding;
while (this.bitOffset < this.bitLength) {
// var raw = [];
// for (var i=0; i<26; i++) {
// var s = this.decodedBits[i].toString(16);
// if (s.length < 2) s = '0' + s;
// raw.push(s);
// }
// console.log(raw.join(" "));
if (this.bitOffset > 0) {
encoding = this.readBits(4);
}
if (encoding !== 0) {
var packet;
switch (encoding) {
case 1: // Numeric
packet = this.decodeNumeric();
break;
case 2: // Alphanumeric
packet = this.decodeAlphanumeric();
break;
case 4: // Byte
packet = this.decodeByte();
break;
case 8: // Kanji
packet = this.decodeKanji();
break;
case 7: // ECI
break;
}
if (packet) {
packets.push(packet);
return packets;
}
}
}
return packets;
};
QRDecoder.prototype.decode = function() {
if (this.extractQRBits(this.imageData, this)) {
this.getFormat();
this.maskAlignmentPatterns();
this.readDecodedBits();
return this.parseBits();
}
return null;
};
QRDecoder.prototype.extractQRBits = function(imageData, bits) {
var width = imageData.width;
var height = imageData.height;
var data = imageData.data;
var bitMatrix = [];
for (var y=0; y<height; y++) {
var bit = 0;
var rowBits = [];
bitMatrix.push(rowBits);
for (var x=0; x<width; x++) {
var b = data[(y*width + x)*4] < 127 ? 1 : 0;
if (b !== bit) {
bit = b;
rowBits.push(x, b&1);
}
}
}
while (bitMatrix.length && bitMatrix[0].length === 0) {
bitMatrix.shift();
}
while (bitMatrix.length && bitMatrix[bitMatrix.length-1].length === 0) {
bitMatrix.pop();
}
var rowMatch = function(a, b) {
if (a === null || a.length !== b.length) {
return false;
}
for (var i=0; i<a.length; i+=2) {
if (Math.abs( a[i] - b[i] ) > 2) {
return false;
}
if (a[i+1] !== b[i+1]) {
return false;
}
}
return true;
};
var bitRows = [];
var lastBitRow = null;
var lastRow = null;
for (var i=0; i<bitMatrix.length; i++) {
if (!rowMatch(lastRow, bitMatrix[i])) {
var row = {length: 0, row: bitMatrix[i]};
bitRows.push(row);
lastBitRow = row;
}
lastBitRow.length++;
lastRow = bitMatrix[i];
}
var bitRowLengths = [];
for (var i=0; i<bitRows.length; i++) {
var l = bitRows[i].length;
bitRowLengths[l] = (bitRowLengths[l] || 0) + 1;
}
var maxCount = 0;
var maxCountLength = 0;
for (var i=2; i<bitRowLengths.length; i++) {
if (bitRowLengths[i] && bitRowLengths[i] > maxCount) {
maxCountLength = i;
maxCount = bitRowLengths[i];
}
}
bitRows = bitRows.filter(function(br) {
return br.length > 1 && Math.abs(br.length - maxCountLength) <= 2;
});
var r = bitRows[0].row;
var w = r[r.length-2] - r[0];
var stride = w / bitRows.length;
var off = r[0] + stride/2;
var sz = bitRows.length;
if (sz < QRDecoder.MIN_SIZE || sz > QRDecoder.MAX_SIZE || (sz - QRDecoder.MIN_SIZE) % 4 !== 0) {
return false;
}
bits.setSize(sz);
for (var y=0; y<bitRows.length; y++) {
var r = bitRows[y].row;
for (var x=0; x<bitRows.length; x++) {
var xc = x * stride + off;
var bit = 0;
for (var j=r.length-2; j>=0; j-=2) {
if (r[j] < xc) {
bit = r[j+1];
break;
}
}
bits.setBit(x, y, bit);
}
}
return bits;
};
</script>
<script>
var img = new Image;
img.src = 'qr.png';
img.onload = function() {
var width = Math.floor(this.width),
height = Math.floor(this.height);
var canvas = document.createElement('canvas');
canvas.width = width*3;
canvas.height = height*2;
var ctx = canvas.getContext('2d');
ctx.drawImage(this, 0, 0, width, height);
var imageData = ctx.getImageData(0, 0, width, height);
document.body.appendChild(canvas);
var decoder = new QRDecoder(imageData);
var tick = function() {
console.time('qr processing x100');
var msg = decoder.decode();
for (var i=0; i<99; i++) {
decoder.imageData = imageData;
if (msg[0].message !== decoder.decode()[0].message) {
throw "Non-stable decoding";
}
}
console.timeEnd('qr processing x100');
requestAnimationFrame(tick);
};
decoder.extractQRBits(imageData, decoder);
decoder.getFormat();
console.log("ecc: %d, mask: %d\n", decoder.ecc, decoder.mask);
decoder.maskAlignmentPatterns();
ctx.save();
ctx.translate(width,26);
for (var y=0; y<decoder.size; y++) {
for (var x=0; x<decoder.size; x++) {
var b = decoder.getBit(x,y);
if (b) {
ctx.fillStyle = b < 0 ? (b < -1 ? '#ff0000' : '#00ff00') : '#000000';
ctx.fillRect( x*5 , y*5, 5, 5);
}
}
}
for (var i=0; i<10; i++) {
decoder.decode();
}
// decoder.ctx = ctx;
//ctx.restore();
console.time('decode');
var res = decoder.decode();
console.timeEnd('decode');
console.log(res);
ctx.font = '18px sans-serif';
ctx.fillText(res[0].message, 0, decoder.size * 5 + 20);
// tick();
};
</script>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment