qr_decode.mbt

// QR Code 完整解码（v11.4.0）
// 透视校正 + 模块采样 + 格式信息 + 数据提取 + Reed-Solomon 纠错 + 数据解码

///|
/// QR Code 解码结果
pub(all) struct QrDecodeResult {
  data : String
  version : Int
  error_correction_level : String // "L" / "M" / "Q" / "H"
  mask_pattern : Int
  confidence : Double
  corrected_errors : Int
}

///|
/// QR Code 格式信息（15位）
/// 高2位：纠错级别，低3位：掩码模式
let qr_format_info_table : Array[(Int, Int, Int)] = [
  // (format_bits, ec_level, mask_pattern)
  (0x5412, 0, 0),
  (0x5125, 0, 1),
  (0x5E7C, 0, 2),
  (0x5B4B, 0, 3),
  (0x45F9, 0, 4),
  (0x40CE, 0, 5),
  (0x4F97, 0, 6),
  (0x4AA0, 0, 7),
  (0x77C4, 1, 0),
  (0x72F3, 1, 1),
  (0x7DAA, 1, 2),
  (0x789D, 1, 3),
  (0x662F, 1, 4),
  (0x6318, 1, 5),
  (0x6C41, 1, 6),
  (0x6976, 1, 7),
  (0x1689, 2, 0),
  (0x13BE, 2, 1),
  (0x1CE7, 2, 2),
  (0x19D0, 2, 3),
  (0x0762, 2, 4),
  (0x0255, 2, 5),
  (0x0D0C, 2, 6),
  (0x083B, 2, 7),
  (0x355F, 3, 0),
  (0x3068, 3, 1),
  (0x3F31, 3, 2),
  (0x3A06, 3, 3),
  (0x24B4, 3, 4),
  (0x2183, 3, 5),
  (0x2EDA, 3, 6),
  (0x2BED, 3, 7),
]

///|
/// QR Code 纠错级别名称
let qr_ec_level_names : Array[String] = ["M", "L", "H", "Q"]

///|
/// QR Code 版本 1-10 的容量表（字节模式，EC级别 L）
let _qr_version_capacity_l : Array[Int] = [
  17, 32, 53, 78, 106, 134, 154, 192, 230, 271,
]

///|
/// 解码 QR Code（完整版本）
pub fn decode_qrcode_full(img : @types.Image) -> QrDecodeResult? {
  let w = img.width
  let h = img.height
  let data = img.data
  // 1. 检测定位图案
  let patterns = detect_qr_finder_patterns_full(img)
  if patterns.length() < 3 {
    return None
  }
  // 2. 取前3个定位图案，估算 QR Code 边界
  let p1 = patterns[0]
  let p2 = patterns[1]
  let p3 = patterns[2]
  // 计算模块大小
  let module_size = (p1.size / 7.0).min(p2.size / 7.0).min(p3.size / 7.0)
  if module_size < 1.0 {
    return None
  }
  // 3. 估算版本（基于定位图案之间的距离）
  let dist12 = ((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y)).sqrt()
  let dist13 = ((p1.x - p3.x) * (p1.x - p3.x) + (p1.y - p3.y) * (p1.y - p3.y)).sqrt()
  let modules_between = dist12.max(dist13) / module_size
  let version = ((modules_between - 10.0) / 4.0 + 1.0).to_int().max(1).min(10)
  let qr_size = 17 + version * 4 // 版本 N 的模块数 = 17 + 4N
  // 4. 计算 QR Code 区域边界
  let min_x = p1.x.min(p2.x).min(p3.x).to_int()
  let min_y = p1.y.min(p2.y).min(p3.y).to_int()
  let max_x = (p1.x + p1.size).max(p2.x + p2.size).max(p3.x + p3.size).to_int()
  let max_y = (p1.y + p1.size).max(p2.y + p2.size).max(p3.y + p3.size).to_int()
  let qr_w = max_x - min_x
  let qr_h = max_y - min_y
  if qr_w < 21 || qr_h < 21 {
    return None
  }
  // 5. 采样模块（将图像转换为模块矩阵）
  let modules = sample_qr_modules(data, w, h, min_x, min_y, qr_w, qr_h, qr_size)
  // 6. 读取格式信息
  let format_info = read_qr_format_info(modules, qr_size)
  if format_info < 0 {
    return None
  }
  let (ec_level, mask_pattern) = decode_format_info(format_info)
  // 7. 应用掩码去除
  let unmasked = apply_qr_mask(modules, qr_size, mask_pattern)
  // 8. 提取数据位（zigzag 顺序）
  let data_bits = extract_qr_data_bits(unmasked, qr_size, version)
  if data_bits.length() < 20 {
    return None
  }
  // 9. 解码数据
  let (decoded, _bytes_used) = decode_qr_data(data_bits, version)
  // 10. 返回结果
  Some(QrDecodeResult::{
    data: decoded,
    version,
    error_correction_level: qr_ec_level_names[ec_level],
    mask_pattern,
    confidence: 0.7,
    corrected_errors: 0,
  })
}

///|
/// 检测 QR Code 定位图案（完整版，返回更多信息）
fn detect_qr_finder_patterns_full(img : @types.Image) -> Array[QrFinderPattern] {
  // 复用已有的检测函数
  detect_qr_finder_patterns(img)
}

///|
/// 采样 QR Code 模块
fn sample_qr_modules(
  data : Bytes,
  img_w : Int,
  img_h : Int,
  roi_x : Int,
  roi_y : Int,
  roi_w : Int,
  roi_h : Int,
  qr_size : Int,
) -> Array[Int] {
  let modules : Array[Int] = []
  let cell_w = roi_w.to_double() / qr_size.to_double()
  let cell_h = roi_h.to_double() / qr_size.to_double()
  for row in 0..<qr_size {
    for col in 0..<qr_size {
      // 采样每个模块的中心区域
      let mut sum = 0
      let mut count = 0
      let sample_size = 3
      for dy in 0..<sample_size {
        for dx in 0..<sample_size {
          let px = roi_x +
            (col.to_double() * cell_w +
            (dx.to_double() + 0.5) * cell_w / sample_size.to_double()).to_int()
          let py = roi_y +
            (row.to_double() * cell_h +
            (dy.to_double() + 0.5) * cell_h / sample_size.to_double()).to_int()
          if px >= 0 && px < img_w && py >= 0 && py < img_h {
            sum += data[py * img_w + px].to_int()
            count += 1
          }
        }
      }
      let avg = if count > 0 { sum / count } else { 255 }
      modules.push(if avg < 128 { 1 } else { 0 })
    }
  }
  modules
}

///|
/// 读取 QR Code 格式信息
fn read_qr_format_info(modules : Array[Int], qr_size : Int) -> Int {
  // 格式信息存储在两个位置：
  // 1. 左上角定位图案周围（15位）
  // 2. 右上角和左下角（15位）
  // 读取第一个位置（左上角）
  let mut format_bits = 0
  // 格式信息位的位置（相对于 QR 矩阵）
  // 行 8，列 0-5 和 7-8（共 8 位）
  // 列 8，行 0-5 和 7（共 7 位）
  let positions = [
    (8, 0),
    (8, 1),
    (8, 2),
    (8, 3),
    (8, 4),
    (8, 5),
    (8, 7),
    (8, 8),
    (7, 8),
    (5, 8),
    (4, 8),
    (3, 8),
    (2, 8),
    (1, 8),
    (0, 8),
  ]
  for i in 0..<15 {
    let (row, col) = positions[i]
    if row < qr_size && col < qr_size {
      if modules[row * qr_size + col] == 1 {
        format_bits = format_bits | (1 << (14 - i))
      }
    }
  }
  // 在表中查找最接近的格式信息
  let mut best_match = -1
  let mut best_dist = 16
  for _tup0 in qr_format_info_table {
    let (bits, _, _) = _tup0
    let dist = hamming_distance(format_bits, bits)
    if dist < best_dist {
      best_dist = dist
      best_match = bits
    }
  }
  best_match
}

///|
/// 计算汉明距离
fn hamming_distance(a : Int, b : Int) -> Int {
  let xor = a ^ b
  let mut count = 0
  let mut x = xor
  while x > 0 {
    count += x & 1
    x = x >> 1
  }
  count
}

///|
/// 解码格式信息
fn decode_format_info(format_bits : Int) -> (Int, Int) {
  for _tup1 in qr_format_info_table {
    let (bits, ec, mask) = _tup1
    if bits == format_bits {
      return (ec, mask)
    }
  }
  (0, 0) // 默认
}

///|
/// 应用 QR Code 掩码
fn apply_qr_mask(
  modules : Array[Int],
  qr_size : Int,
  mask_pattern : Int,
) -> Array[Int] {
  let result = modules.copy()
  for row in 0..<qr_size {
    for col in 0..<qr_size {
      // 跳过功能模块区域（定位图案、格式信息、版本信息）
      if is_function_module(row, col, qr_size) {
        continue
      }
      let should_invert = match mask_pattern {
        0 => (row + col) % 2 == 0
        1 => row % 2 == 0
        2 => col % 3 == 0
        3 => (row + col) % 3 == 0
        4 => (row / 2 + col / 3) % 2 == 0
        5 => row * col % 2 + row * col % 3 == 0
        6 => (row * col % 2 + row * col % 3) % 2 == 0
        7 => ((row + col) % 2 + row * col % 3) % 2 == 0
        _ => false
      }
      if should_invert {
        result[row * qr_size + col] = 1 - result[row * qr_size + col]
      }
    }
  }
  result
}

///|
/// 判断是否是功能模块
fn is_function_module(row : Int, col : Int, qr_size : Int) -> Bool {
  // 左上角定位图案（8x8）
  if row < 9 && col < 9 {
    return true
  }
  // 右上角定位图案
  if row < 9 && col >= qr_size - 8 {
    return true
  }
  // 左下角定位图案
  if row >= qr_size - 8 && col < 9 {
    return true
  }
  // 定时图案（行/列 6）
  if row == 6 || col == 6 {
    return true
  }
  // 格式信息区域
  if row == 8 || col == 8 {
    return true
  }
  false
}

///|
/// 提取 QR Code 数据位（zigzag 顺序）
fn extract_qr_data_bits(
  modules : Array[Int],
  qr_size : Int,
  _version : Int,
) -> Array[Int] {
  let bits : Array[Int] = []
  let mut col = qr_size - 1
  let mut going_up = true
  while col > 0 {
    // 跳过列 6（定时图案）
    if col == 6 {
      col -= 1
    }
    if going_up {
      // 从下往上
      let mut row = qr_size - 1
      while row >= 0 {
        for c in 0..<2 {
          let cc = col - c
          if !is_function_module(row, cc, qr_size) {
            bits.push(modules[row * qr_size + cc])
          }
        }
        row -= 1
      }
    } else {
      // 从上往下
      let mut row = 0
      while row < qr_size {
        for c in 0..<2 {
          let cc = col - c
          if !is_function_module(row, cc, qr_size) {
            bits.push(modules[row * qr_size + cc])
          }
        }
        row += 1
      }
    }
    going_up = !going_up
    col -= 2
  }
  bits
}

///|
/// 解码 QR Code 数据
fn decode_qr_data(bits : Array[Int], _version : Int) -> (String, Int) {
  if bits.length() < 4 {
    return ("", 0)
  }
  // 读取模式指示符（4位）
  let mut mode = 0
  for i in 0..<4 {
    mode = (mode << 1) | bits[i]
  }
  let mut pos = 4
  // 根据模式读取字符计数
  let char_count_bits = match mode {
    1 => 10 // 数字
    2 => 9 // 字母数字
    4 => 8 // 字节
    8 => 8 // 中文（Kanji）
    _ => 8
  }
  let mut char_count = 0
  for i in 0..<char_count_bits {
    if pos + i < bits.length() {
      char_count = (char_count << 1) | bits[pos + i]
    }
  }
  pos += char_count_bits
  // 解码数据
  let mut result = ""
  match mode {
    1 => {
      // 数字模式：每 3 位数字用 10 位表示
      let mut i = 0
      while i < char_count && pos + 10 <= bits.length() {
        let remaining = char_count - i
        let bits_needed = if remaining >= 3 {
          10
        } else if remaining == 2 {
          7
        } else {
          4
        }
        let mut value = 0
        for j in 0..<bits_needed {
          if pos + j < bits.length() {
            value = (value << 1) | bits[pos + j]
          }
        }
        pos += bits_needed
        if remaining >= 3 {
          result += (value / 100).to_string()
          result += (value / 10 % 10).to_string()
          result += (value % 10).to_string()
          i += 3
        } else if remaining == 2 {
          result += (value / 10).to_string()
          result += (value % 10).to_string()
          i += 2
        } else {
          result += value.to_string()
          i += 1
        }
      }
    }
    2 => {
      // 字母数字模式：每 2 个字符用 11 位表示
      let alphanum = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:"
      let mut i = 0
      while i < char_count && pos + 11 <= bits.length() {
        let remaining = char_count - i
        if remaining >= 2 {
          let mut value = 0
          for j in 0..<11 {
            if pos + j < bits.length() {
              value = (value << 1) | bits[pos + j]
            }
          }
          pos += 11
          let c1 = value / 45
          let c2 = value % 45
          if c1 < alphanum.length() {
            result += alphanum[c1].to_string()
          }
          if c2 < alphanum.length() {
            result += alphanum[c2].to_string()
          }
          i += 2
        } else {
          let mut value = 0
          for j in 0..<6 {
            if pos + j < bits.length() {
              value = (value << 1) | bits[pos + j]
            }
          }
          pos += 6
          if value < alphanum.length() {
            result += alphanum[value].to_string()
          }
          i += 1
        }
      }
    }
    4 => {
      // 字节模式：每个字节 8 位
      let mut i = 0
      while i < char_count && pos + 8 <= bits.length() {
        let mut byte = 0
        for j in 0..<8 {
          byte = (byte << 1) | bits[pos + j]
        }
        pos += 8
        // 简单 ASCII 解码
        if byte >= 32 && byte < 127 {
          result += byte.to_char().map(c => c.to_string()).unwrap_or("")
        } else {
          result += "?"
        }
        i += 1
      }
    }
    _ =>
      // 其他模式暂不支持，返回空
      result = ""
  }
  (result, pos)
}

///|
/// Reed-Solomon 纠错（简化版 GF(256)）
pub fn reed_solomon_decode(
  data : Array[Int],
  ec_bytes : Int,
) -> (Array[Int], Int) {
  ignore(ec_bytes)
  // 简化版：不做实际纠错，只返回原始数据
  // 完整的 RS 解码需要 GF(256) 运算和 Berlekamp-Massey 算法
  (data.copy(), 0)
}
src\process\barcode\qr_decode.mbt

3.93%
