/*!
 * qr.js - compact QR Code encoder (byte mode, error correction level M, versions 1-10)
 * Dependency-free. Works offline. Exposes window.QR
 *
 * Usage:
 *   QR.encode(text)                  -> { size, version, mask, modules }
 *   QR.toCanvas(canvas, text, opts)  -> encodes and paints the canvas
 */
(function (root, factory) {
  if (typeof module === 'object' && module.exports) module.exports = factory();
  else root.QR = factory();
})(typeof self !== 'undefined' ? self : this, function () {
  'use strict';

  /* Version -> EC codewords per block + data codeword lengths per block.
     Level M only. Totals: 26, 44, 70, 100, 134, 172, 196, 242, 292, 346. */
  var SPECS = [null,
    { ec: 10, blocks: [16] },
    { ec: 16, blocks: [28] },
    { ec: 26, blocks: [44] },
    { ec: 18, blocks: [32, 32] },
    { ec: 24, blocks: [43, 43] },
    { ec: 16, blocks: [27, 27, 27, 27] },
    { ec: 18, blocks: [31, 31, 31, 31] },
    { ec: 22, blocks: [38, 38, 39, 39] },
    { ec: 22, blocks: [36, 36, 36, 37, 37] },
    { ec: 26, blocks: [43, 43, 43, 43, 44] }
  ];

  var ALIGN = [null, [], [6, 18], [6, 22], [6, 26], [6, 30], [6, 34],
    [6, 22, 38], [6, 24, 42], [6, 26, 46], [6, 28, 50]];

  /* ---------- GF(256) arithmetic, primitive polynomial 0x11D ---------- */
  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 mul(a, b) {
    return (a === 0 || b === 0) ? 0 : EXP[LOG[a] + LOG[b]];
  }

  function generator(degree) {
    var g = [1];
    for (var i = 0; i < degree; i++) {
      var next = new Array(g.length + 1).fill(0);
      for (var j = 0; j < g.length; j++) {
        next[j] ^= g[j];
        next[j + 1] ^= mul(g[j], EXP[i]);
      }
      g = next;
    }
    return g;
  }

  function ecBytes(data, degree) {
    var gen = generator(degree);
    var res = new Array(degree).fill(0);
    for (var i = 0; i < data.length; i++) {
      var factor = data[i] ^ res[0];
      res.shift();
      res.push(0);
      if (factor !== 0) {
        for (var j = 0; j < degree; j++) res[j] ^= mul(gen[j + 1], factor);
      }
    }
    return res;
  }

  /* ---------- helpers ---------- */
  function utf8(text) {
    if (typeof TextEncoder !== 'undefined') return Array.prototype.slice.call(new TextEncoder().encode(text));
    var out = [];
    for (var i = 0; i < text.length; i++) {
      var c = text.charCodeAt(i);
      if (c < 0x80) out.push(c);
      else if (c < 0x800) out.push(0xc0 | (c >> 6), 0x80 | (c & 0x3f));
      else out.push(0xe0 | (c >> 12), 0x80 | ((c >> 6) & 0x3f), 0x80 | (c & 0x3f));
    }
    return out;
  }

  var MAX_BYTES = 213; // version 10, level M

  /* ---------- format / version information ---------- */
  function formatBits(mask) {
    var data = (0 << 3) | mask; // level M = 00
    var rem = data;
    for (var i = 0; i < 10; i++) rem = (rem << 1) ^ ((rem >>> 9) * 0x537);
    return ((data << 10) | rem) ^ 0x5412;
  }

  function versionBits(version) {
    var rem = version;
    for (var i = 0; i < 12; i++) rem = (rem << 1) ^ ((rem >>> 11) * 0x1f25);
    return (version << 12) | rem;
  }

  function writeFormat(m, size, mask) {
    var bits = formatBits(mask);
    function bit(i) { return ((bits >>> i) & 1) === 1; }
    var i;
    for (i = 0; i <= 5; i++) m[i][8] = bit(i);
    m[7][8] = bit(6);
    m[8][8] = bit(7);
    m[8][7] = bit(8);
    for (i = 9; i < 15; i++) m[8][14 - i] = bit(i);
    for (i = 0; i < 8; i++) m[8][size - 1 - i] = bit(i);
    for (i = 8; i < 15; i++) m[size - 15 + i][8] = bit(i);
    m[size - 8][8] = true; // fixed dark module
  }

  function writeVersion(m, size, version) {
    if (version < 7) return;
    var bits = versionBits(version);
    for (var i = 0; i < 18; i++) {
      var bit = ((bits >>> i) & 1) === 1;
      var a = size - 11 + (i % 3);
      var b = Math.floor(i / 3);
      m[b][a] = bit;
      m[a][b] = bit;
    }
  }

  /* ---------- penalty scoring (choose the cleanest mask) ---------- */
  function penalty(m, size) {
    var score = 0;
    var x, y, run, c;

    for (y = 0; y < size; y++) {
      run = 1;
      for (x = 1; x < size; x++) {
        if (m[y][x] === m[y][x - 1]) {
          run++;
          if (run === 5) score += 3;
          else if (run > 5) score += 1;
        } else run = 1;
      }
    }
    for (x = 0; x < size; x++) {
      run = 1;
      for (y = 1; y < size; y++) {
        if (m[y][x] === m[y - 1][x]) {
          run++;
          if (run === 5) score += 3;
          else if (run > 5) score += 1;
        } else run = 1;
      }
    }

    for (y = 0; y < size - 1; y++) {
      for (x = 0; x < size - 1; x++) {
        c = m[y][x];
        if (c === m[y][x + 1] && c === m[y + 1][x] && c === m[y + 1][x + 1]) score += 3;
      }
    }

    var p1 = '10111010000';
    var p2 = '00001011101';
    for (y = 0; y < size; y++) {
      var row = '';
      var col = '';
      for (x = 0; x < size; x++) {
        row += m[y][x] ? '1' : '0';
        col += m[x][y] ? '1' : '0';
      }
      score += countPattern(row, p1) * 40 + countPattern(row, p2) * 40;
      score += countPattern(col, p1) * 40 + countPattern(col, p2) * 40;
    }

    var dark = 0;
    for (y = 0; y < size; y++) for (x = 0; x < size; x++) if (m[y][x]) dark++;
    var total = size * size;
    score += (Math.ceil(Math.abs(dark * 20 - total * 10) / total) - 1) * 10;

    return score;
  }

  function countPattern(haystack, needle) {
    var n = 0, at = 0;
    while ((at = haystack.indexOf(needle, at)) !== -1) { n++; at++; }
    return n;
  }

  /* ---------- mask patterns ---------- */
  function maskAt(mask, x, y) {
    switch (mask) {
      case 0: return (x + y) % 2 === 0;
      case 1: return y % 2 === 0;
      case 2: return x % 3 === 0;
      case 3: return (x + y) % 3 === 0;
      case 4: return (Math.floor(x / 3) + Math.floor(y / 2)) % 2 === 0;
      case 5: return ((x * y) % 2) + ((x * y) % 3) === 0;
      case 6: return (((x * y) % 2) + ((x * y) % 3)) % 2 === 0;
      case 7: return (((x + y) % 2) + ((x * y) % 3)) % 2 === 0;
    }
    return false;
  }

  /* ---------- encoder ---------- */
  function encode(text) {
    var bytes = utf8(String(text));
    if (bytes.length > MAX_BYTES) {
      throw new Error('Too long for this QR generator: ' + bytes.length + ' bytes (max ' + MAX_BYTES + '). Use a shorter link.');
    }

    var version = 0, spec = null, dataCap = 0, i, j;
    for (var v = 1; v <= 10; v++) {
      var candidate = SPECS[v];
      var cap = 0;
      for (i = 0; i < candidate.blocks.length; i++) cap += candidate.blocks[i];
      var countBits = v <= 9 ? 8 : 16;
      if (4 + countBits + bytes.length * 8 <= cap * 8) {
        version = v; spec = candidate; dataCap = cap;
        break;
      }
    }
    if (!version) throw new Error('Too long for this QR generator.');

    /* bit stream: mode 0100, length, payload, terminator, padding */
    var bits = [];
    function push(val, len) {
      for (var b = len - 1; b >= 0; b--) bits.push((val >>> b) & 1);
    }
    push(4, 4);
    push(bytes.length, version <= 9 ? 8 : 16);
    for (i = 0; i < bytes.length; i++) push(bytes[i], 8);

    var maxBits = dataCap * 8;
    push(0, Math.min(4, maxBits - bits.length));
    while (bits.length % 8 !== 0) bits.push(0);

    var data = [];
    for (i = 0; i < bits.length; i += 8) {
      var byte = 0;
      for (j = 0; j < 8; j++) byte = (byte << 1) | bits[i + j];
      data.push(byte);
    }
    var padCycle = [0xec, 0x11];
    for (i = 0; data.length < dataCap; i++) data.push(padCycle[i % 2]);

    /* split into blocks, add Reed-Solomon bytes, interleave */
    var blocks = [], offset = 0;
    for (i = 0; i < spec.blocks.length; i++) {
      var len = spec.blocks[i];
      var chunk = data.slice(offset, offset + len);
      offset += len;
      blocks.push({ data: chunk, ec: ecBytes(chunk, spec.ec) });
    }

    var totalData = 0;
    for (i = 0; i < blocks.length; i++) totalData = Math.max(totalData, blocks[i].data.length);

    var codewords = [];
    for (i = 0; i < totalData; i++) {
      for (j = 0; j < blocks.length; j++) if (i < blocks[j].data.length) codewords.push(blocks[j].data[i]);
    }
    for (i = 0; i < spec.ec; i++) {
      for (j = 0; j < blocks.length; j++) codewords.push(blocks[j].ec[i]);
    }

    /* ---------- matrix ---------- */
    var size = version * 4 + 17;
    var modules = [], isFn = [];
    for (i = 0; i < size; i++) {
      modules.push(new Array(size).fill(false));
      isFn.push(new Array(size).fill(false));
    }

    function set(x, y, dark) {
      modules[y][x] = !!dark;
      isFn[y][x] = true;
    }

    function finder(cx, cy) {
      for (var dy = -4; dy <= 4; dy++) {
        for (var dx = -4; dx <= 4; dx++) {
          var x = cx + dx, y = cy + dy;
          if (x < 0 || y < 0 || x >= size || y >= size) continue;
          var d = Math.max(Math.abs(dx), Math.abs(dy));
          set(x, y, d !== 2 && d !== 4);
        }
      }
    }
    finder(3, 3);
    finder(size - 4, 3);
    finder(3, size - 4);

    for (i = 8; i < size - 8; i++) {
      set(i, 6, i % 2 === 0);
      set(6, i, i % 2 === 0);
    }

    var align = ALIGN[version];
    for (i = 0; i < align.length; i++) {
      for (j = 0; j < align.length; j++) {
        var ax = align[i], ay = align[j];
        if ((ax === 6 && ay === 6) || (ax === 6 && ay === size - 7) || (ax === size - 7 && ay === 6)) continue;
        for (var dy2 = -2; dy2 <= 2; dy2++) {
          for (var dx2 = -2; dx2 <= 2; dx2++) {
            set(ax + dx2, ay + dy2, Math.max(Math.abs(dx2), Math.abs(dy2)) !== 1);
          }
        }
      }
    }

    /* reserve format + version areas before writing data */
    for (i = 0; i <= 8; i++) {
      if (i !== 6) {
        isFn[i][8] = true;
        isFn[8][i] = true;
      }
    }
    for (i = 0; i < 8; i++) isFn[8][size - 1 - i] = true;
    for (i = 8; i < 15; i++) isFn[size - 15 + i][8] = true;
    isFn[size - 8][8] = true;

    writeVersion(modules, size, version);
    if (version >= 7) {
      for (i = 0; i < 18; i++) {
        var a = size - 11 + (i % 3);
        var b = Math.floor(i / 3);
        isFn[b][a] = true;
        isFn[a][b] = true;
      }
    }

    /* place data in the two-module-wide zigzag */
    var bitIndex = 0, totalBits = codewords.length * 8;
    for (var right = size - 1; right >= 1; right -= 2) {
      if (right === 6) right = 5;
      for (var vert = 0; vert < size; vert++) {
        for (var k = 0; k < 2; k++) {
          var x2 = right - k;
          var upward = ((right + 1) & 2) === 0;
          var y2 = upward ? size - 1 - vert : vert;
          if (!isFn[y2][x2] && bitIndex < totalBits) {
            modules[y2][x2] = ((codewords[bitIndex >> 3] >>> (7 - (bitIndex & 7))) & 1) === 1;
            bitIndex++;
          }
        }
      }
    }

    /* pick the lowest-penalty mask, then stamp the real format bits */
    var best = null, bestScore = Infinity, bestMask = 0;
    for (var mask = 0; mask < 8; mask++) {
      var candidateMatrix = [];
      for (i = 0; i < size; i++) candidateMatrix.push(modules[i].slice());
      for (var y3 = 0; y3 < size; y3++) {
        for (var x3 = 0; x3 < size; x3++) {
          if (!isFn[y3][x3] && maskAt(mask, x3, y3)) candidateMatrix[y3][x3] = !candidateMatrix[y3][x3];
        }
      }
      writeFormat(candidateMatrix, size, mask);
      var score = penalty(candidateMatrix, size);
      if (score < bestScore) {
        bestScore = score;
        best = candidateMatrix;
        bestMask = mask;
      }
    }

    return { size: size, version: version, mask: bestMask, modules: best, bytes: bytes.length };
  }

  /* ---------- rendering ---------- */
  function toCanvas(canvas, text, opts) {
    opts = opts || {};
    var qr = encode(text);
    var margin = opts.margin == null ? 4 : opts.margin;
    var target = opts.size || 720;
    var dark = opts.dark || '#ffffff';
    var light = opts.light || '#000000';
    var count = qr.size + margin * 2;
    var scale = Math.max(1, Math.floor(target / count));
    var dim = scale * count;

    canvas.width = dim;
    canvas.height = dim;
    var ctx = canvas.getContext('2d');
    ctx.fillStyle = light;
    ctx.fillRect(0, 0, dim, dim);
    ctx.fillStyle = dark;
    for (var y = 0; y < qr.size; y++) {
      for (var x = 0; x < qr.size; x++) {
        if (qr.modules[y][x]) ctx.fillRect((x + margin) * scale, (y + margin) * scale, scale, scale);
      }
    }
    return qr;
  }

  return {
    encode: encode,
    toCanvas: toCanvas,
    maxBytes: MAX_BYTES
  };
});