/**
 * BitForgeNet Guest Tickets — dependency-free QR decoder.
 *
 * The browser's native BarcodeDetector is used when it exists, but it is absent on
 * desktop Chrome for Windows, on Firefox, and on Safari before 17 — which is exactly
 * where a door team ends up when the tablet dies and someone opens the laptop. This
 * decoder fills that gap: binarise, find the three finder patterns, correct the
 * perspective, sample the grid, then Reed-Solomon decode.
 *
 * Nothing is loaded from a CDN. A venue's Wi-Fi is not something to bet a door on.
 *
 * Exposes: window.BFNETQR.decode( imageData ) -> string | null
 */
( function ( global ) {
	'use strict';

	/* ------------------------------------------------------------------ */
	/* GF(256)                                                            */
	/* ------------------------------------------------------------------ */

	var EXP = new Uint8Array( 512 );
	var LOG = new Uint8Array( 256 );

	( function () {
		var x = 1;
		for ( var i = 0; i < 255; i++ ) {
			EXP[ i ] = x;
			LOG[ x ] = i;
			x <<= 1;
			if ( x & 0x100 ) {
				x ^= 0x11d;
			}
		}
		for ( var j = 255; j < 512; j++ ) {
			EXP[ j ] = EXP[ j - 255 ];
		}
	} )();

	function gmul( a, b ) {
		if ( a === 0 || b === 0 ) {
			return 0;
		}
		return EXP[ LOG[ a ] + LOG[ b ] ];
	}

	function gdiv( a, b ) {
		if ( b === 0 ) {
			throw new Error( 'div0' );
		}
		if ( a === 0 ) {
			return 0;
		}
		return EXP[ ( LOG[ a ] - LOG[ b ] + 255 ) % 255 ];
	}

	function gpow( a, n ) {
		return EXP[ ( LOG[ a ] * n ) % 255 ];
	}

	function polyMul( p, q ) {
		var r = new Uint8Array( p.length + q.length - 1 );
		for ( var i = 0; i < p.length; i++ ) {
			for ( var j = 0; j < q.length; j++ ) {
				r[ i + j ] ^= gmul( p[ i ], q[ j ] );
			}
		}
		return r;
	}

	function polyEval( p, x ) {
		var y = p[ 0 ];
		for ( var i = 1; i < p.length; i++ ) {
			y = gmul( y, x ) ^ p[ i ];
		}
		return y;
	}

	/**
	 * Reed-Solomon decode in place. Returns false when the block is beyond repair.
	 */
	function rsDecode( msg, ecCount ) {
		var synd = new Uint8Array( ecCount );
		var hasError = false;
		var i;

		for ( i = 0; i < ecCount; i++ ) {
			synd[ i ] = polyEval( msg, EXP[ i ] );
			if ( synd[ i ] !== 0 ) {
				hasError = true;
			}
		}
		if ( ! hasError ) {
			return true;
		}

		// Berlekamp-Massey.
		var errLoc = new Uint8Array( [ 1 ] );
		var oldLoc = new Uint8Array( [ 1 ] );

		for ( i = 0; i < ecCount; i++ ) {
			oldLoc = concat( oldLoc, new Uint8Array( [ 0 ] ) );

			var delta = synd[ i ];
			for ( var j = 1; j < errLoc.length; j++ ) {
				delta ^= gmul( errLoc[ errLoc.length - 1 - j ], synd[ i - j ] );
			}

			if ( delta !== 0 ) {
				if ( oldLoc.length > errLoc.length ) {
					var neo = scalePoly( oldLoc, delta );
					oldLoc = scalePoly( errLoc, gdiv( 1, delta ) );
					errLoc = neo;
				}
				errLoc = addPoly( errLoc, scalePoly( oldLoc, delta ) );
			}
		}

		errLoc = trimLeading( errLoc );
		var errCount = errLoc.length - 1;
		if ( errCount * 2 > ecCount ) {
			return false;
		}

		// Chien search for the error positions.
		var positions = [];
		for ( i = 0; i < msg.length; i++ ) {
			if ( polyEval( errLoc, gpow( 2, msg.length - 1 - i ) ) === 0 ) {
				positions.push( msg.length - 1 - i );
			}
		}
		if ( positions.length !== errCount ) {
			return false;
		}

		// Forney: build the locator from the found positions and correct.
		var coefPos = positions.map( function ( p ) {
			return msg.length - 1 - p;
		} );

		var errLocPoly = new Uint8Array( [ 1 ] );
		for ( i = 0; i < coefPos.length; i++ ) {
			errLocPoly = polyMul( errLocPoly, new Uint8Array( [ gpow( 2, msg.length - 1 - coefPos[ i ] ), 1 ] ) );
		}

		var syndRev = new Uint8Array( synd.length );
		for ( i = 0; i < synd.length; i++ ) {
			syndRev[ i ] = synd[ synd.length - 1 - i ];
		}

		var errEval = polyMul( syndRev, errLocPoly ).slice( -coefPos.length );

		var xs = new Uint8Array( coefPos.length );
		for ( i = 0; i < coefPos.length; i++ ) {
			xs[ i ] = gpow( 2, coefPos[ i ] - msg.length + 256 );
		}

		for ( i = 0; i < xs.length; i++ ) {
			var xinv = gdiv( 1, xs[ i ] );

			var errLocPrime = 1;
			for ( var k = 0; k < xs.length; k++ ) {
				if ( k !== i ) {
					errLocPrime = gmul( errLocPrime, 1 ^ gmul( xinv, xs[ k ] ) );
				}
			}
			if ( errLocPrime === 0 ) {
				return false;
			}

			var y = gmul( xs[ i ], polyEval( errEval, xinv ) );
			msg[ coefPos[ i ] ] ^= gdiv( y, errLocPrime );
		}

		// Verify.
		for ( i = 0; i < ecCount; i++ ) {
			if ( polyEval( msg, EXP[ i ] ) !== 0 ) {
				return false;
			}
		}
		return true;
	}

	function concat( a, b ) {
		var r = new Uint8Array( a.length + b.length );
		r.set( a, 0 );
		r.set( b, a.length );
		return r;
	}

	function scalePoly( p, s ) {
		var r = new Uint8Array( p.length );
		for ( var i = 0; i < p.length; i++ ) {
			r[ i ] = gmul( p[ i ], s );
		}
		return r;
	}

	function addPoly( a, b ) {
		var r = new Uint8Array( Math.max( a.length, b.length ) );
		var i;
		for ( i = 0; i < a.length; i++ ) {
			r[ i + r.length - a.length ] = a[ i ];
		}
		for ( i = 0; i < b.length; i++ ) {
			r[ i + r.length - b.length ] ^= b[ i ];
		}
		return r;
	}

	function trimLeading( p ) {
		var i = 0;
		while ( i < p.length - 1 && p[ i ] === 0 ) {
			i++;
		}
		return p.slice( i );
	}

	/* ------------------------------------------------------------------ */
	/* Symbol tables                                                      */
	/* ------------------------------------------------------------------ */

	// [version][level L,M,Q,H] => [ecPerBlock, blocks1, data1, blocks2, data2]
	var ECC = {
		1: [ [ 7, 1, 19, 0, 0 ], [ 10, 1, 16, 0, 0 ], [ 13, 1, 13, 0, 0 ], [ 17, 1, 9, 0, 0 ] ],
		2: [ [ 10, 1, 34, 0, 0 ], [ 16, 1, 28, 0, 0 ], [ 22, 1, 22, 0, 0 ], [ 28, 1, 16, 0, 0 ] ],
		3: [ [ 15, 1, 55, 0, 0 ], [ 26, 1, 44, 0, 0 ], [ 18, 2, 17, 0, 0 ], [ 22, 2, 13, 0, 0 ] ],
		4: [ [ 20, 1, 80, 0, 0 ], [ 18, 2, 32, 0, 0 ], [ 26, 2, 24, 0, 0 ], [ 16, 4, 9, 0, 0 ] ],
		5: [ [ 26, 1, 108, 0, 0 ], [ 24, 2, 43, 0, 0 ], [ 18, 2, 15, 2, 16 ], [ 22, 2, 11, 2, 12 ] ],
		6: [ [ 18, 2, 68, 0, 0 ], [ 16, 4, 27, 0, 0 ], [ 24, 4, 19, 0, 0 ], [ 28, 4, 15, 0, 0 ] ],
		7: [ [ 20, 2, 78, 0, 0 ], [ 18, 4, 31, 0, 0 ], [ 18, 2, 14, 4, 15 ], [ 26, 4, 13, 1, 14 ] ],
		8: [ [ 24, 2, 97, 0, 0 ], [ 22, 2, 38, 2, 39 ], [ 22, 4, 18, 2, 19 ], [ 26, 4, 14, 2, 15 ] ],
		9: [ [ 30, 2, 116, 0, 0 ], [ 22, 3, 36, 2, 37 ], [ 20, 4, 16, 4, 17 ], [ 24, 4, 12, 4, 13 ] ],
		10: [ [ 18, 2, 68, 2, 69 ], [ 26, 4, 43, 1, 44 ], [ 24, 6, 19, 2, 20 ], [ 28, 6, 15, 2, 16 ] ],
		11: [ [ 20, 4, 81, 0, 0 ], [ 30, 1, 50, 4, 51 ], [ 28, 4, 22, 4, 23 ], [ 24, 3, 12, 8, 13 ] ],
		12: [ [ 24, 2, 92, 2, 93 ], [ 22, 6, 36, 2, 37 ], [ 26, 4, 20, 6, 21 ], [ 28, 7, 14, 4, 15 ] ],
		13: [ [ 26, 4, 107, 0, 0 ], [ 22, 8, 37, 1, 38 ], [ 24, 8, 20, 4, 21 ], [ 22, 12, 11, 4, 12 ] ],
		14: [ [ 30, 3, 115, 1, 116 ], [ 24, 4, 40, 5, 41 ], [ 20, 11, 16, 5, 17 ], [ 24, 11, 12, 5, 13 ] ],
		15: [ [ 22, 5, 87, 1, 88 ], [ 24, 5, 41, 5, 42 ], [ 30, 5, 24, 7, 25 ], [ 24, 11, 12, 7, 13 ] ],
		16: [ [ 24, 5, 98, 1, 99 ], [ 28, 7, 45, 3, 46 ], [ 24, 15, 19, 2, 20 ], [ 30, 3, 15, 13, 16 ] ],
		17: [ [ 28, 1, 107, 5, 108 ], [ 28, 10, 46, 1, 47 ], [ 28, 1, 22, 15, 23 ], [ 28, 2, 14, 17, 15 ] ],
		18: [ [ 30, 5, 120, 1, 121 ], [ 26, 9, 43, 4, 44 ], [ 28, 17, 22, 1, 23 ], [ 28, 2, 14, 19, 15 ] ],
		19: [ [ 28, 3, 113, 4, 114 ], [ 26, 3, 44, 11, 45 ], [ 26, 17, 21, 4, 22 ], [ 26, 9, 13, 16, 14 ] ],
		20: [ [ 28, 3, 107, 5, 108 ], [ 26, 3, 41, 13, 42 ], [ 30, 15, 24, 5, 25 ], [ 28, 15, 15, 10, 16 ] ]
	};

	var ALIGN = {
		1: [], 2: [ 6, 18 ], 3: [ 6, 22 ], 4: [ 6, 26 ], 5: [ 6, 30 ], 6: [ 6, 34 ],
		7: [ 6, 22, 38 ], 8: [ 6, 24, 42 ], 9: [ 6, 26, 46 ], 10: [ 6, 28, 50 ],
		11: [ 6, 30, 54 ], 12: [ 6, 32, 58 ], 13: [ 6, 34, 62 ], 14: [ 6, 26, 46, 66 ],
		15: [ 6, 26, 48, 70 ], 16: [ 6, 26, 50, 74 ], 17: [ 6, 30, 54, 78 ],
		18: [ 6, 30, 56, 82 ], 19: [ 6, 30, 58, 86 ], 20: [ 6, 34, 62, 90 ]
	};

	function remainderBits( v ) {
		if ( v === 1 ) { return 0; }
		if ( v <= 6 ) { return 7; }
		if ( v <= 13 ) { return 0; }
		return 3;
	}

	function maskFn( mask, r, c ) {
		switch ( mask ) {
			case 0: return ( r + c ) % 2 === 0;
			case 1: return r % 2 === 0;
			case 2: return c % 3 === 0;
			case 3: return ( r + c ) % 3 === 0;
			case 4: return ( Math.floor( r / 2 ) + Math.floor( c / 3 ) ) % 2 === 0;
			case 5: return ( ( r * c ) % 2 ) + ( ( r * c ) % 3 ) === 0;
			case 6: return ( ( ( r * c ) % 2 ) + ( ( r * c ) % 3 ) ) % 2 === 0;
			default: return ( ( ( r + c ) % 2 ) + ( ( r * c ) % 3 ) ) % 2 === 0;
		}
	}

	/* ------------------------------------------------------------------ */
	/* Binarisation                                                       */
	/* ------------------------------------------------------------------ */

	/**
	 * Block-adaptive threshold.
	 *
	 * A single global cut-off fails the moment one half of the ticket catches the door
	 * light and the other does not. Luminance is reduced to 8x8 blocks, each block gets
	 * a black point, and the threshold at any pixel is the mean of the 5x5 block
	 * neighbourhood around it.
	 *
	 * Two details matter and are easy to get wrong: a block with almost no contrast is
	 * assumed to be background and takes half its own maximum (or its neighbours' level
	 * if they are darker), and the comparison is <= rather than <, so the interior of a
	 * large solid black area is not read as white.
	 */
	function binarize( data, width, height ) {
		var gray = new Uint8Array( width * height );
		var i, x, y, z;

		for ( i = 0; i < width * height; i++ ) {
			var o = i * 4;
			gray[ i ] = ( data[ o ] * 306 + data[ o + 1 ] * 601 + data[ o + 2 ] * 117 ) >> 10;
		}

		var BS = 8;
		var subW = Math.max( 1, ( width >> 3 ) + ( ( width & 7 ) === 0 ? 0 : 1 ) );
		var subH = Math.max( 1, ( height >> 3 ) + ( ( height & 7 ) === 0 ? 0 : 1 ) );
		var points = new Int32Array( subW * subH );

		for ( y = 0; y < subH; y++ ) {
			var yo = Math.min( y * BS, height - BS );
			if ( yo < 0 ) { yo = 0; }

			for ( x = 0; x < subW; x++ ) {
				var xo = Math.min( x * BS, width - BS );
				if ( xo < 0 ) { xo = 0; }

				var sum = 0, min = 255, max = 0, n = 0;

				for ( var yy = 0; yy < BS && yo + yy < height; yy++ ) {
					var row = ( yo + yy ) * width;
					for ( var xx = 0; xx < BS && xo + xx < width; xx++ ) {
						var g = gray[ row + xo + xx ];
						sum += g; n++;
						if ( g < min ) { min = g; }
						if ( g > max ) { max = g; }
					}
				}

				var average;
				if ( max - min > 24 ) {
					average = ( sum / Math.max( 1, n ) ) | 0;
				} else {
					// Nearly flat: treat it as background unless the neighbours are darker.
					average = ( max / 2 ) | 0;
					if ( y > 0 && x > 0 ) {
						var neigh = ( points[ ( y - 1 ) * subW + x ] + 2 * points[ y * subW + x - 1 ] + points[ ( y - 1 ) * subW + x - 1 ] ) / 4;
						if ( min < neigh ) { average = neigh | 0; }
					}
				}

				points[ y * subW + x ] = average;
			}
		}

		var bits = new Uint8Array( width * height );
		var cap = function ( v, lo, hi ) {
			return v < lo ? lo : ( v > hi ? hi : v );
		};

		for ( y = 0; y < subH; y++ ) {
			var yoff = Math.min( y * BS, height - BS );
			if ( yoff < 0 ) { yoff = 0; }
			var top = cap( y, 2, subH - 3 );

			for ( x = 0; x < subW; x++ ) {
				var xoff = Math.min( x * BS, width - BS );
				if ( xoff < 0 ) { xoff = 0; }
				var left = cap( x, 2, subW - 3 );

				var total = 0;
				for ( z = -2; z <= 2; z++ ) {
					var r = ( top + z ) * subW;
					total += points[ r + left - 2 ] + points[ r + left - 1 ] + points[ r + left ] + points[ r + left + 1 ] + points[ r + left + 2 ];
				}

				var threshold = total / 25;

				for ( var by = 0; by < BS && yoff + by < height; by++ ) {
					var brow = ( yoff + by ) * width;
					for ( var bx = 0; bx < BS && xoff + bx < width; bx++ ) {
						bits[ brow + xoff + bx ] = gray[ brow + xoff + bx ] <= threshold ? 1 : 0;
					}
				}
			}
		}

		return bits;
	}

	/* ------------------------------------------------------------------ */
	/* Finder patterns                                                    */
	/* ------------------------------------------------------------------ */

	function ratioOk( c ) {
		var total = 0;
		for ( var i = 0; i < 5; i++ ) {
			if ( c[ i ] === 0 ) { return false; }
			total += c[ i ];
		}
		if ( total < 7 ) { return false; }

		var mod = total / 7;
		var tol = mod / 2;

		return Math.abs( mod - c[ 0 ] ) < tol &&
			Math.abs( mod - c[ 1 ] ) < tol &&
			Math.abs( 3 * mod - c[ 2 ] ) < 3 * tol &&
			Math.abs( mod - c[ 3 ] ) < tol &&
			Math.abs( mod - c[ 4 ] ) < tol;
	}

	function centreFromEnd( c, end ) {
		return end - c[ 4 ] - c[ 3 ] - c[ 2 ] / 2;
	}

	function crossCheckVertical( bits, w, h, startX, centreY, maxCount, originalTotal ) {
		var c = [ 0, 0, 0, 0, 0 ];
		var y = centreY;

		while ( y >= 0 && bits[ y * w + startX ] ) { c[ 2 ]++; y--; }
		if ( y < 0 ) { return NaN; }
		while ( y >= 0 && ! bits[ y * w + startX ] && c[ 1 ] <= maxCount ) { c[ 1 ]++; y--; }
		if ( y < 0 || c[ 1 ] > maxCount ) { return NaN; }
		while ( y >= 0 && bits[ y * w + startX ] && c[ 0 ] <= maxCount ) { c[ 0 ]++; y--; }
		if ( c[ 0 ] > maxCount ) { return NaN; }

		y = centreY + 1;
		while ( y < h && bits[ y * w + startX ] ) { c[ 2 ]++; y++; }
		if ( y === h ) { return NaN; }
		while ( y < h && ! bits[ y * w + startX ] && c[ 3 ] < maxCount ) { c[ 3 ]++; y++; }
		if ( y === h || c[ 3 ] >= maxCount ) { return NaN; }
		while ( y < h && bits[ y * w + startX ] && c[ 4 ] < maxCount ) { c[ 4 ]++; y++; }
		if ( c[ 4 ] >= maxCount ) { return NaN; }

		var total = c[ 0 ] + c[ 1 ] + c[ 2 ] + c[ 3 ] + c[ 4 ];
		if ( 5 * Math.abs( total - originalTotal ) >= 2 * originalTotal ) { return NaN; }

		return ratioOk( c ) ? centreFromEnd( c, y ) : NaN;
	}

	function crossCheckHorizontal( bits, w, centreX, centreY, maxCount, originalTotal ) {
		var c = [ 0, 0, 0, 0, 0 ];
		var x = centreX;
		var row = centreY * w;

		while ( x >= 0 && bits[ row + x ] ) { c[ 2 ]++; x--; }
		if ( x < 0 ) { return NaN; }
		while ( x >= 0 && ! bits[ row + x ] && c[ 1 ] <= maxCount ) { c[ 1 ]++; x--; }
		if ( x < 0 || c[ 1 ] > maxCount ) { return NaN; }
		while ( x >= 0 && bits[ row + x ] && c[ 0 ] <= maxCount ) { c[ 0 ]++; x--; }
		if ( c[ 0 ] > maxCount ) { return NaN; }

		x = centreX + 1;
		while ( x < w && bits[ row + x ] ) { c[ 2 ]++; x++; }
		if ( x === w ) { return NaN; }
		while ( x < w && ! bits[ row + x ] && c[ 3 ] < maxCount ) { c[ 3 ]++; x++; }
		if ( x === w || c[ 3 ] >= maxCount ) { return NaN; }
		while ( x < w && bits[ row + x ] && c[ 4 ] < maxCount ) { c[ 4 ]++; x++; }
		if ( c[ 4 ] >= maxCount ) { return NaN; }

		var total = c[ 0 ] + c[ 1 ] + c[ 2 ] + c[ 3 ] + c[ 4 ];
		if ( 5 * Math.abs( total - originalTotal ) >= originalTotal ) { return NaN; }

		return ratioOk( c ) ? centreFromEnd( c, x ) : NaN;
	}

	/**
	 * Row-scan for the 1:1:3:1:1 signature.
	 *
	 * Even states count dark runs, odd states count light runs. A candidate completes
	 * when a light pixel arrives while in state 4.
	 */
	function findFinders( bits, w, h ) {
		var found = [];
		var step = Math.max( 1, Math.floor( h / 320 ) );

		for ( var y = 0; y < h; y += step ) {
			var c = [ 0, 0, 0, 0, 0 ];
			var state = 0;
			var row = y * w;

			for ( var x = 0; x < w; x++ ) {
				if ( bits[ row + x ] ) {
					// Dark.
					if ( ( state & 1 ) === 1 ) { state++; }
					c[ state ]++;
				} else {
					// Light.
					if ( ( state & 1 ) === 0 ) {
						if ( state === 4 ) {
							if ( ratioOk( c ) ) {
								tryFinder( bits, w, h, c, x, y, found );
								c = [ 0, 0, 0, 0, 0 ];
								state = 0;
							} else {
								c = [ c[ 2 ], c[ 3 ], c[ 4 ], 1, 0 ];
								state = 3;
							}
						} else {
							state++;
							c[ state ]++;
						}
					} else {
						c[ state ]++;
					}
				}
			}

			if ( state === 4 && ratioOk( c ) ) {
				tryFinder( bits, w, h, c, w, y, found );
			}
		}

		return found;
	}

	function tryFinder( bits, w, h, c, endX, y, found ) {
		var total = c[ 0 ] + c[ 1 ] + c[ 2 ] + c[ 3 ] + c[ 4 ];
		var cx = centreFromEnd( c, endX );
		var maxCount = c[ 2 ];

		var cy = crossCheckVertical( bits, w, h, Math.floor( cx ), y, 2 * maxCount, total );
		if ( isNaN( cy ) ) { return; }

		cx = crossCheckHorizontal( bits, w, Math.floor( cx ), Math.floor( cy ), 2 * maxCount, total );
		if ( isNaN( cx ) ) { return; }

		var size = total / 7;

		for ( var i = 0; i < found.length; i++ ) {
			var f = found[ i ];
			if ( Math.abs( f.x - cx ) <= size && Math.abs( f.y - cy ) <= size ) {
				f.x = ( f.x * f.n + cx ) / ( f.n + 1 );
				f.y = ( f.y * f.n + cy ) / ( f.n + 1 );
				f.size = ( f.size * f.n + size ) / ( f.n + 1 );
				f.n++;
				return;
			}
		}

		found.push( { x: cx, y: cy, size: size, n: 1 } );
	}

	function dist( a, b ) {
		var dx = a.x - b.x, dy = a.y - b.y;
		return Math.sqrt( dx * dx + dy * dy );
	}

	/**
	 * Work out which of the three patterns is the corner, and which way round the
	 * other two go.
	 */
	function orderFinders( f ) {
		var ab = dist( f[ 0 ], f[ 1 ] );
		var bc = dist( f[ 1 ], f[ 2 ] );
		var ac = dist( f[ 0 ], f[ 2 ] );

		var topLeft, p, q;
		if ( bc >= ab && bc >= ac ) {
			topLeft = f[ 0 ]; p = f[ 1 ]; q = f[ 2 ];
		} else if ( ac >= ab && ac >= bc ) {
			topLeft = f[ 1 ]; p = f[ 0 ]; q = f[ 2 ];
		} else {
			topLeft = f[ 2 ]; p = f[ 0 ]; q = f[ 1 ];
		}

		// Cross product decides the handedness.
		var cross = ( q.x - topLeft.x ) * ( p.y - topLeft.y ) - ( q.y - topLeft.y ) * ( p.x - topLeft.x );
		var topRight, bottomLeft;
		if ( cross < 0 ) {
			topRight = p; bottomLeft = q;
		} else {
			topRight = q; bottomLeft = p;
		}

		return { topLeft: topLeft, topRight: topRight, bottomLeft: bottomLeft };
	}

	/* ------------------------------------------------------------------ */
	/* Perspective transform                                              */
	/* ------------------------------------------------------------------ */

	function squareToQuad( x0, y0, x1, y1, x2, y2, x3, y3 ) {
		var dx3 = x0 - x1 + x2 - x3;
		var dy3 = y0 - y1 + y2 - y3;

		if ( dx3 === 0 && dy3 === 0 ) {
			return [ x1 - x0, x2 - x1, x0, y1 - y0, y2 - y1, y0, 0, 0, 1 ];
		}

		var dx1 = x1 - x2, dx2 = x3 - x2;
		var dy1 = y1 - y2, dy2 = y3 - y2;
		var den = dx1 * dy2 - dx2 * dy1;
		var a13 = ( dx3 * dy2 - dx2 * dy3 ) / den;
		var a23 = ( dx1 * dy3 - dx3 * dy1 ) / den;

		return [
			x1 - x0 + a13 * x1, x3 - x0 + a23 * x3, x0,
			y1 - y0 + a13 * y1, y3 - y0 + a23 * y3, y0,
			a13, a23, 1
		];
	}

	/**
	 * Adjugate of a square-to-quad matrix, i.e. quad-to-square.
	 *
	 * Layout throughout is [ a11, a21, a31, a12, a22, a32, a13, a23, a33 ].
	 */
	function quadToSquare( x0, y0, x1, y1, x2, y2, x3, y3 ) {
		var m = squareToQuad( x0, y0, x1, y1, x2, y2, x3, y3 );

		return [
			m[ 4 ] * m[ 8 ] - m[ 7 ] * m[ 5 ],
			m[ 7 ] * m[ 2 ] - m[ 1 ] * m[ 8 ],
			m[ 1 ] * m[ 5 ] - m[ 4 ] * m[ 2 ],
			m[ 6 ] * m[ 5 ] - m[ 3 ] * m[ 8 ],
			m[ 0 ] * m[ 8 ] - m[ 6 ] * m[ 2 ],
			m[ 3 ] * m[ 2 ] - m[ 0 ] * m[ 5 ],
			m[ 3 ] * m[ 7 ] - m[ 6 ] * m[ 4 ],
			m[ 6 ] * m[ 1 ] - m[ 0 ] * m[ 7 ],
			m[ 0 ] * m[ 4 ] - m[ 3 ] * m[ 1 ]
		];
	}

	function matMul( a, b ) {
		return [
			a[ 0 ] * b[ 0 ] + a[ 1 ] * b[ 3 ] + a[ 2 ] * b[ 6 ],
			a[ 0 ] * b[ 1 ] + a[ 1 ] * b[ 4 ] + a[ 2 ] * b[ 7 ],
			a[ 0 ] * b[ 2 ] + a[ 1 ] * b[ 5 ] + a[ 2 ] * b[ 8 ],
			a[ 3 ] * b[ 0 ] + a[ 4 ] * b[ 3 ] + a[ 5 ] * b[ 6 ],
			a[ 3 ] * b[ 1 ] + a[ 4 ] * b[ 4 ] + a[ 5 ] * b[ 7 ],
			a[ 3 ] * b[ 2 ] + a[ 4 ] * b[ 5 ] + a[ 5 ] * b[ 8 ],
			a[ 6 ] * b[ 0 ] + a[ 7 ] * b[ 3 ] + a[ 8 ] * b[ 6 ],
			a[ 6 ] * b[ 1 ] + a[ 7 ] * b[ 4 ] + a[ 8 ] * b[ 7 ],
			a[ 6 ] * b[ 2 ] + a[ 7 ] * b[ 5 ] + a[ 8 ] * b[ 8 ]
		];
	}

	function transformPoint( m, x, y ) {
		var d = m[ 6 ] * x + m[ 7 ] * y + m[ 8 ];
		return {
			x: ( m[ 0 ] * x + m[ 1 ] * y + m[ 2 ] ) / d,
			y: ( m[ 3 ] * x + m[ 4 ] * y + m[ 5 ] ) / d
		};
	}

	function quadToQuad( sx0, sy0, sx1, sy1, sx2, sy2, sx3, sy3, dx0, dy0, dx1, dy1, dx2, dy2, dx3, dy3 ) {
		return matMul( squareToQuad( dx0, dy0, dx1, dy1, dx2, dy2, dx3, dy3 ), quadToSquare( sx0, sy0, sx1, sy1, sx2, sy2, sx3, sy3 ) );
	}

	/* ------------------------------------------------------------------ */
	/* Alignment pattern                                                  */
	/* ------------------------------------------------------------------ */

	function findAlignment( bits, w, h, estX, estY, moduleSize ) {
		var span = Math.ceil( moduleSize * 5 );
		var left = Math.max( 0, Math.floor( estX - span ) );
		var right = Math.min( w - 1, Math.ceil( estX + span ) );
		var top = Math.max( 0, Math.floor( estY - span ) );
		var bottom = Math.min( h - 1, Math.ceil( estY + span ) );

		var best = null;
		var bestScore = Infinity;

		for ( var y = top; y <= bottom; y++ ) {
			var c = [ 0, 0, 0 ];
			var stage = 0;

			for ( var x = left; x <= right; x++ ) {
				var dark = bits[ y * w + x ];

				if ( ( stage & 1 ) === ( dark ? 0 : 1 ) ) {
					c[ stage ]++;
				} else if ( stage === 2 ) {
					if ( alignRatioOk( c, moduleSize ) ) {
						var cx = x - c[ 2 ] - c[ 1 ] / 2;
						var cy = alignVertical( bits, w, h, Math.floor( cx ), y, moduleSize );
						if ( ! isNaN( cy ) ) {
							var score = Math.abs( cx - estX ) + Math.abs( cy - estY );
							if ( score < bestScore ) {
								bestScore = score;
								best = { x: cx, y: cy };
							}
						}
					}
					c[ 0 ] = c[ 2 ]; c[ 1 ] = 1; c[ 2 ] = 0; stage = 1;
				} else {
					stage++;
					c[ stage ] = 1;
				}
			}
		}

		return best;
	}

	function alignRatioOk( c, moduleSize ) {
		var tol = moduleSize / 2;
		return Math.abs( c[ 0 ] - moduleSize ) < tol &&
			Math.abs( c[ 1 ] - moduleSize ) < tol &&
			Math.abs( c[ 2 ] - moduleSize ) < tol;
	}

	function alignVertical( bits, w, h, x, y, moduleSize ) {
		var up = 0, down = 0, mid = 0;
		var yy = y;

		while ( yy >= 0 && bits[ yy * w + x ] && mid < moduleSize * 2 ) { mid++; yy--; }
		if ( yy < 0 ) { return NaN; }
		while ( yy >= 0 && ! bits[ yy * w + x ] && up < moduleSize * 2 ) { up++; yy--; }
		if ( up === 0 ) { return NaN; }

		yy = y + 1;
		while ( yy < h && bits[ yy * w + x ] && mid < moduleSize * 3 ) { mid++; yy++; }
		if ( yy >= h ) { return NaN; }
		while ( yy < h && ! bits[ yy * w + x ] && down < moduleSize * 2 ) { down++; yy++; }
		if ( down === 0 ) { return NaN; }

		if ( Math.abs( mid - moduleSize ) > moduleSize / 1.5 ) { return NaN; }

		return yy - down - mid / 2;
	}

	/* ------------------------------------------------------------------ */
	/* Sampling and decoding                                              */
	/* ------------------------------------------------------------------ */

	function sample( bits, w, h, transform, dimension ) {
		var m = new Uint8Array( dimension * dimension );

		for ( var y = 0; y < dimension; y++ ) {
			for ( var x = 0; x < dimension; x++ ) {
				var p = transformPoint( transform, x + 0.5, y + 0.5 );
				var px = Math.round( p.x );
				var py = Math.round( p.y );
				if ( px < 0 || py < 0 || px >= w || py >= h ) {
					return null;
				}
				m[ y * dimension + x ] = bits[ py * w + px ];
			}
		}

		return m;
	}

	function readFormat( m, size ) {
		var bits1 = 0, i;
		for ( i = 0; i < 15; i++ ) {
			var b;
			if ( i < 6 ) { b = m[ i * size + 8 ]; }
			else if ( i === 6 ) { b = m[ 7 * size + 8 ]; }
			else if ( i === 7 ) { b = m[ 8 * size + 8 ]; }
			else if ( i === 8 ) { b = m[ 8 * size + 7 ]; }
			else { b = m[ 8 * size + ( 14 - i ) ]; }
			bits1 |= b << i;
		}

		var bits2 = 0;
		for ( i = 0; i < 15; i++ ) {
			var b2;
			if ( i < 8 ) { b2 = m[ 8 * size + ( size - 1 - i ) ]; }
			else { b2 = m[ ( size - 15 + i ) * size + 8 ]; }
			bits2 |= b2 << i;
		}

		var best = null, bestDist = 5;

		for ( var data = 0; data < 32; data++ ) {
			var rem = data;
			for ( var k = 0; k < 10; k++ ) {
				rem = ( rem << 1 ) ^ ( ( ( rem >> 9 ) & 1 ) * 0x537 );
			}
			var candidate = ( ( ( data << 10 ) | rem ) ^ 0x5412 ) & 0x7fff;

			var d1 = popcount( candidate ^ bits1 );
			var d2 = popcount( candidate ^ bits2 );
			var d = Math.min( d1, d2 );

			if ( d < bestDist ) {
				bestDist = d;
				best = data;
			}
		}

		if ( best === null ) { return null; }

		var levelBits = ( best >> 3 ) & 3;
		var levelMap = { 1: 0, 0: 1, 3: 2, 2: 3 };

		return { level: levelMap[ levelBits ], mask: best & 7 };
	}

	function popcount( n ) {
		var c = 0;
		while ( n ) { c += n & 1; n >>= 1; }
		return c;
	}

	function functionMap( size, version ) {
		var f = new Uint8Array( size * size );
		var i, j, r, c;

		var corners = [ [ 0, 0 ], [ 0, size - 7 ], [ size - 7, 0 ] ];
		for ( i = 0; i < 3; i++ ) {
			for ( r = -1; r <= 7; r++ ) {
				for ( c = -1; c <= 7; c++ ) {
					var rr = corners[ i ][ 0 ] + r, cc = corners[ i ][ 1 ] + c;
					if ( rr >= 0 && rr < size && cc >= 0 && cc < size ) { f[ rr * size + cc ] = 1; }
				}
			}
		}

		for ( i = 0; i < size; i++ ) { f[ 6 * size + i ] = 1; f[ i * size + 6 ] = 1; }

		var ce = ALIGN[ version ] || [];
		for ( i = 0; i < ce.length; i++ ) {
			for ( j = 0; j < ce.length; j++ ) {
				if ( ( i === 0 && j === 0 ) || ( i === 0 && j === ce.length - 1 ) || ( i === ce.length - 1 && j === 0 ) ) { continue; }
				for ( r = -2; r <= 2; r++ ) {
					for ( c = -2; c <= 2; c++ ) { f[ ( ce[ i ] + r ) * size + ( ce[ j ] + c ) ] = 1; }
				}
			}
		}

		for ( i = 0; i < 9; i++ ) { f[ 8 * size + i ] = 1; f[ i * size + 8 ] = 1; }
		for ( i = 0; i < 8; i++ ) { f[ 8 * size + ( size - 1 - i ) ] = 1; f[ ( size - 1 - i ) * size + 8 ] = 1; }

		if ( version >= 7 ) {
			for ( i = 0; i < 6; i++ ) {
				for ( j = 0; j < 3; j++ ) {
					f[ i * size + ( size - 11 + j ) ] = 1;
					f[ ( size - 11 + j ) * size + i ] = 1;
				}
			}
		}

		return f;
	}

	function readCodewords( m, size, version, mask ) {
		var f = functionMap( size, version );
		var bits = [];
		var col = size - 1;
		var up = true;

		while ( col > 0 ) {
			if ( col === 6 ) { col = 5; }
			for ( var n = 0; n < size; n++ ) {
				var row = up ? ( size - 1 - n ) : n;
				for ( var k = 0; k < 2; k++ ) {
					var c = col - k;
					if ( f[ row * size + c ] ) { continue; }
					var v = m[ row * size + c ];
					if ( maskFn( mask, row, c ) ) { v ^= 1; }
					bits.push( v );
				}
			}
			up = ! up;
			col -= 2;
		}

		var bytes = [];
		for ( var i = 0; i + 8 <= bits.length; i += 8 ) {
			var b = 0;
			for ( var j = 0; j < 8; j++ ) { b = ( b << 1 ) | bits[ i + j ]; }
			bytes.push( b );
		}

		return bytes;
	}

	function deinterleave( cw, version, level ) {
		var spec = ECC[ version ][ level ];
		var ecPer = spec[ 0 ], b1 = spec[ 1 ], d1 = spec[ 2 ], b2 = spec[ 3 ], d2 = spec[ 4 ];
		var nb = b1 + b2;
		var sizes = [];
		var i, b;

		for ( i = 0; i < b1; i++ ) { sizes.push( d1 ); }
		for ( i = 0; i < b2; i++ ) { sizes.push( d2 ); }

		var blocks = [];
		for ( i = 0; i < nb; i++ ) { blocks.push( [] ); }

		var idx = 0;
		var maxData = Math.max( d1, d2 );
		for ( i = 0; i < maxData; i++ ) {
			for ( b = 0; b < nb; b++ ) {
				if ( i < sizes[ b ] ) { blocks[ b ].push( cw[ idx++ ] ); }
			}
		}

		var ecs = [];
		for ( i = 0; i < nb; i++ ) { ecs.push( [] ); }
		for ( i = 0; i < ecPer; i++ ) {
			for ( b = 0; b < nb; b++ ) { ecs[ b ].push( cw[ idx++ ] ); }
		}

		var out = [];
		for ( b = 0; b < nb; b++ ) {
			var full = new Uint8Array( blocks[ b ].concat( ecs[ b ] ) );
			if ( ! rsDecode( full, ecPer ) ) { return null; }
			for ( i = 0; i < sizes[ b ]; i++ ) { out.push( full[ i ] ); }
		}

		return out;
	}

	var ALNUM = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:';

	function parseSegments( data, version ) {
		var bits = [];
		for ( var i = 0; i < data.length; i++ ) {
			for ( var j = 7; j >= 0; j-- ) { bits.push( ( data[ i ] >> j ) & 1 ); }
		}

		var pos = 0;
		var read = function ( n ) {
			var v = 0;
			for ( var k = 0; k < n; k++ ) {
				if ( pos >= bits.length ) { return -1; }
				v = ( v << 1 ) | bits[ pos++ ];
			}
			return v;
		};

		var bytes = [];
		var text = '';
		var guard = 0;

		while ( pos + 4 <= bits.length && guard++ < 64 ) {
			var mode = read( 4 );
			if ( mode <= 0 ) { break; }

			if ( mode === 4 ) {
				var lenBits = version < 10 ? 8 : 16;
				var len = read( lenBits );
				if ( len < 0 ) { break; }
				for ( var b = 0; b < len; b++ ) {
					var byte = read( 8 );
					if ( byte < 0 ) { break; }
					bytes.push( byte );
				}
			} else if ( mode === 1 ) {
				var nlen = read( version < 10 ? 10 : 12 );
				var chunk = '';
				while ( nlen >= 3 ) { chunk += pad( read( 10 ), 3 ); nlen -= 3; }
				if ( nlen === 2 ) { chunk += pad( read( 7 ), 2 ); }
				else if ( nlen === 1 ) { chunk += String( read( 4 ) ); }
				pushString( bytes, chunk );
			} else if ( mode === 2 ) {
				var alen = read( version < 10 ? 9 : 11 );
				var s = '';
				while ( alen >= 2 ) {
					var pair = read( 11 );
					s += ALNUM[ Math.floor( pair / 45 ) ] + ALNUM[ pair % 45 ];
					alen -= 2;
				}
				if ( alen === 1 ) { s += ALNUM[ read( 6 ) ]; }
				pushString( bytes, s );
			} else if ( mode === 7 ) {
				read( 8 ); // ECI assignment: UTF-8 is assumed either way.
			} else {
				break;
			}
		}

		if ( ! bytes.length ) { return null; }

		try {
			text = new TextDecoder( 'utf-8' ).decode( new Uint8Array( bytes ) );
		} catch ( e ) {
			text = String.fromCharCode.apply( null, bytes );
		}

		return text;
	}

	function pad( n, width ) {
		var s = String( n );
		while ( s.length < width ) { s = '0' + s; }
		return s;
	}

	function pushString( bytes, s ) {
		for ( var i = 0; i < s.length; i++ ) { bytes.push( s.charCodeAt( i ) & 0xff ); }
	}

	/* ------------------------------------------------------------------ */
	/* Public entry point                                                 */
	/* ------------------------------------------------------------------ */

	function decodeMatrix( m, size ) {
		var version = ( size - 17 ) / 4;
		if ( version < 1 || version > 20 || version !== Math.floor( version ) ) { return null; }

		var fmt = readFormat( m, size );
		if ( ! fmt ) { return null; }

		var cw = readCodewords( m, size, version, fmt.mask );

		var spec = ECC[ version ][ fmt.level ];
		var expected = ( spec[ 1 ] * ( spec[ 2 ] + spec[ 0 ] ) ) + ( spec[ 3 ] * ( spec[ 4 ] + spec[ 0 ] ) );
		if ( cw.length < expected ) { return null; }

		var data = deinterleave( cw.slice( 0, expected ), version, fmt.level );
		if ( ! data ) { return null; }

		return parseSegments( data, version );
	}

	/**
	 * Decode a QR code from an ImageData frame.
	 *
	 * @param {ImageData} imageData Frame from a canvas.
	 * @return {string|null} Payload, or null when nothing readable was found.
	 */
	function decode( imageData ) {
		var w = imageData.width, h = imageData.height;

		var bits;
		try {
			bits = binarize( imageData.data, w, h );
		} catch ( e ) {
			return null;
		}

		var finders = findFinders( bits, w, h );
		if ( finders.length < 3 ) { return null; }

		// Keep the three most confidently detected patterns.
		finders.sort( function ( a, b ) { return b.n - a.n; } );

		var combos = [];
		var limit = Math.min( finders.length, 5 );
		for ( var a = 0; a < limit; a++ ) {
			for ( var b = a + 1; b < limit; b++ ) {
				for ( var c = b + 1; c < limit; c++ ) {
					combos.push( [ finders[ a ], finders[ b ], finders[ c ] ] );
				}
			}
		}

		for ( var i = 0; i < combos.length && i < 10; i++ ) {
			var result = attempt( bits, w, h, combos[ i ] );
			if ( result ) { return result; }
		}

		return null;
	}

	function attempt( bits, w, h, trio ) {
		var o;
		try {
			o = orderFinders( trio );
		} catch ( e ) {
			return null;
		}

		var tl = o.topLeft, tr = o.topRight, bl = o.bottomLeft;
		var moduleSize = ( tl.size + tr.size + bl.size ) / 3;
		if ( ! isFinite( moduleSize ) || moduleSize < 1 ) { return null; }

		var dimension = Math.round( ( dist( tl, tr ) / moduleSize + dist( tl, bl ) / moduleSize ) / 2 ) + 7;
		switch ( dimension % 4 ) {
			case 0: dimension++; break;
			case 2: dimension--; break;
			case 3: return null;
		}

		if ( dimension < 21 || dimension > 97 ) { return null; }

		var version = ( dimension - 17 ) / 4;
		var dimMinus = dimension - 3.5;

		// The corner implied by the three finders, used when there is no alignment
		// pattern or when the one we found turns out to be a decoy.
		var brX = tr.x - tl.x + bl.x;
		var brY = tr.y - tl.y + bl.y;

		var candidates = [ { srcBR: dimMinus, x: brX, y: brY } ];

		if ( version >= 2 ) {
			var corr = 1 - 3 / ( dimension - 7 );
			var estX = tl.x + corr * ( brX - tl.x );
			var estY = tl.y + corr * ( brY - tl.y );
			var al = findAlignment( bits, w, h, estX, estY, moduleSize );

			// Only trust it if it landed near where geometry says it should be.
			if ( al && Math.abs( al.x - estX ) < moduleSize * 2.5 && Math.abs( al.y - estY ) < moduleSize * 2.5 ) {
				// A real alignment pattern corrects perspective, so try it first.
				candidates.unshift( { srcBR: dimMinus - 3, x: al.x, y: al.y } );
			}
		}

		for ( var i = 0; i < candidates.length; i++ ) {
			var cand = candidates[ i ];

			var transform = quadToQuad(
				3.5, 3.5,
				dimMinus, 3.5,
				cand.srcBR, cand.srcBR,
				3.5, dimMinus,
				tl.x, tl.y,
				tr.x, tr.y,
				cand.x, cand.y,
				bl.x, bl.y
			);

			var m = sample( bits, w, h, transform, dimension );
			if ( ! m ) { continue; }

			try {
				var text = decodeMatrix( m, dimension );
				if ( text ) { return text; }
			} catch ( e ) {
				/* Try the next candidate. */
			}
		}

		return null;
	}

	global.BFNETQR = { decode: decode, decodeMatrix: decodeMatrix };
} )( typeof window !== 'undefined' ? window : this );
