type QrVersion = {
  version: number
  size: number
  dataCodewords: number
  errorCodewords: number
  alignment: number[]
}

const lowVersions: QrVersion[] = [
  { version: 1, size: 21, dataCodewords: 19, errorCodewords: 7, alignment: [] },
  { version: 2, size: 25, dataCodewords: 34, errorCodewords: 10, alignment: [6, 18] },
  { version: 3, size: 29, dataCodewords: 55, errorCodewords: 15, alignment: [6, 22] },
  { version: 4, size: 33, dataCodewords: 80, errorCodewords: 20, alignment: [6, 26] },
]

function gfTables() {
  const exp = new Array<number>(512).fill(0)
  const log = new Array<number>(256).fill(0)
  let value = 1
  for (let index = 0; index < 255; index += 1) {
    exp[index] = value
    log[value] = index
    value <<= 1
    if (value & 0x100) value ^= 0x11d
  }
  for (let index = 255; index < 512; index += 1) exp[index] = exp[index - 255]
  return { exp, log }
}

const gf = gfTables()

function gfMul(left: number, right: number) {
  if (left === 0 || right === 0) return 0
  return gf.exp[gf.log[left] + gf.log[right]]
}

function reedSolomonDivisor(degree: number) {
  const result = new Array<number>(degree).fill(0)
  result[degree - 1] = 1
  let root = 1
  for (let index = 0; index < degree; index += 1) {
    for (let item = 0; item < result.length; item += 1) {
      result[item] = gfMul(result[item], root)
      if (item + 1 < result.length) result[item] ^= result[item + 1]
    }
    root = gfMul(root, 2)
  }
  return result
}

function reedSolomonRemainder(data: number[], degree: number) {
  const divisor = reedSolomonDivisor(degree)
  const result = new Array<number>(degree).fill(0)
  data.forEach((codeword) => {
    const factor = codeword ^ result.shift()!
    result.push(0)
    divisor.forEach((coefficient, index) => {
      result[index] ^= gfMul(coefficient, factor)
    })
  })
  return result
}

function pushBits(target: number[], value: number, length: number) {
  for (let index = length - 1; index >= 0; index -= 1) {
    target.push((value >>> index) & 1)
  }
}

function bytesFor(value: string) {
  const encoder = new TextEncoder()
  return Array.from(encoder.encode(value))
}

function pickVersion(byteLength: number) {
  const selected = lowVersions.find((item) => 4 + 8 + byteLength * 8 <= item.dataCodewords * 8)
  if (!selected) {
    throw new Error('QR value is too long for the built-in renderer')
  }
  return selected
}

function encodeData(value: string, config: QrVersion) {
  const bytes = bytesFor(value)
  const bits: number[] = []
  pushBits(bits, 0b0100, 4)
  pushBits(bits, bytes.length, 8)
  bytes.forEach((byte) => pushBits(bits, byte, 8))
  const terminator = Math.min(4, config.dataCodewords * 8 - bits.length)
  for (let index = 0; index < terminator; index += 1) bits.push(0)
  while (bits.length % 8 !== 0) bits.push(0)

  const codewords: number[] = []
  for (let index = 0; index < bits.length; index += 8) {
    codewords.push(bits.slice(index, index + 8).reduce((sum, bit) => (sum << 1) | bit, 0))
  }
  const pads = [0xec, 0x11]
  while (codewords.length < config.dataCodewords) {
    codewords.push(pads[codewords.length % 2])
  }
  return codewords
}

function formatBits() {
  const data = 0b01000
  let bits = data << 10
  const divisor = 0x537
  for (let index = 14; index >= 10; index -= 1) {
    if (((bits >>> index) & 1) !== 0) bits ^= divisor << (index - 10)
  }
  return ((data << 10) | bits) ^ 0x5412
}

function bit(value: number, index: number) {
  return ((value >>> index) & 1) !== 0
}

export function createQrMatrix(value: string) {
  const config = pickVersion(bytesFor(value).length)
  const { size } = config
  const matrix = Array.from({ length: size }, () => new Array<boolean>(size).fill(false))
  const reserved = Array.from({ length: size }, () => new Array<boolean>(size).fill(false))

  function setModule(x: number, y: number, dark: boolean, reserve = true) {
    if (x < 0 || y < 0 || x >= size || y >= size) return
    matrix[y][x] = dark
    if (reserve) reserved[y][x] = true
  }

  function finder(originX: number, originY: number) {
    for (let y = -1; y <= 7; y += 1) {
      for (let x = -1; x <= 7; x += 1) {
        const xx = originX + x
        const yy = originY + y
        if (xx < 0 || yy < 0 || xx >= size || yy >= size) continue
        const inPattern = x >= 0 && x <= 6 && y >= 0 && y <= 6
        const dark = inPattern && (x === 0 || x === 6 || y === 0 || y === 6 || (x >= 2 && x <= 4 && y >= 2 && y <= 4))
        setModule(xx, yy, dark)
      }
    }
  }

  function alignment(centerX: number, centerY: number) {
    for (let y = -2; y <= 2; y += 1) {
      for (let x = -2; x <= 2; x += 1) {
        const distance = Math.max(Math.abs(x), Math.abs(y))
        setModule(centerX + x, centerY + y, distance === 2 || distance === 0)
      }
    }
  }

  finder(0, 0)
  finder(size - 7, 0)
  finder(0, size - 7)

  config.alignment.forEach((x) => {
    config.alignment.forEach((y) => {
      const nearTop = y < 9
      const nearLeft = x < 9
      const nearRight = x > size - 10
      if ((nearTop && nearLeft) || (nearTop && nearRight) || (!nearTop && nearLeft)) return
      alignment(x, y)
    })
  })

  for (let index = 8; index <= size - 9; index += 1) {
    setModule(index, 6, index % 2 === 0)
    setModule(6, index, index % 2 === 0)
  }
  setModule(8, size - 8, true)

  for (let index = 0; index <= 8; index += 1) {
    if (index !== 6) {
      setModule(8, index, false)
      setModule(index, 8, false)
    }
  }
  for (let index = 0; index < 8; index += 1) setModule(size - 1 - index, 8, false)
  for (let index = 8; index < 15; index += 1) setModule(8, size - 15 + index, false)

  const data = encodeData(value, config)
  const allCodewords = [...data, ...reedSolomonRemainder(data, config.errorCodewords)]
  const bits = allCodewords.flatMap((codeword) => Array.from({ length: 8 }, (_, index) => (codeword >>> (7 - index)) & 1))
  let bitIndex = 0
  let upward = true
  for (let right = size - 1; right >= 1; right -= 2) {
    if (right === 6) right -= 1
    for (let row = 0; row < size; row += 1) {
      const y = upward ? size - 1 - row : row
      for (let column = 0; column < 2; column += 1) {
        const x = right - column
        if (reserved[y][x]) continue
        const raw = bitIndex < bits.length ? bits[bitIndex] === 1 : false
        const masked = raw !== ((x + y) % 2 === 0)
        setModule(x, y, masked, false)
        bitIndex += 1
      }
    }
    upward = !upward
  }

  const format = formatBits()
  for (let index = 0; index <= 5; index += 1) setModule(8, index, bit(format, index))
  setModule(8, 7, bit(format, 6))
  setModule(8, 8, bit(format, 7))
  setModule(7, 8, bit(format, 8))
  for (let index = 9; index < 15; index += 1) setModule(14 - index, 8, bit(format, index))
  for (let index = 0; index < 8; index += 1) setModule(size - 1 - index, 8, bit(format, index))
  for (let index = 8; index < 15; index += 1) setModule(8, size - 15 + index, bit(format, index))
  setModule(8, size - 8, true)

  return matrix
}
