Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | Download | RSS feed

  1. /* quirc -- QR-code recognition library
  2.  * Copyright (C) 2010-2012 Daniel Beer <dlbeer@gmail.com>
  3.  *
  4.  * Permission to use, copy, modify, and/or distribute this software for any
  5.  * purpose with or without fee is hereby granted, provided that the above
  6.  * copyright notice and this permission notice appear in all copies.
  7.  *
  8.  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  9.  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  10.  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  11.  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  12.  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  13.  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  14.  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  15.  */
  16.  
  17. #include "quirc_internal.h"
  18.  
  19. #include <string.h>
  20. #include <stdlib.h>
  21.  
  22. #define MAX_POLY       64
  23.  
  24. /************************************************************************
  25.  * Galois fields
  26.  */
  27.  
  28. struct galois_field {
  29.         int p;
  30.         const uint8_t *log;
  31.         const uint8_t *exp;
  32. };
  33.  
  34. static const uint8_t gf16_exp[16] = {
  35.         0x01, 0x02, 0x04, 0x08, 0x03, 0x06, 0x0c, 0x0b,
  36.         0x05, 0x0a, 0x07, 0x0e, 0x0f, 0x0d, 0x09, 0x01
  37. };
  38.  
  39. static const uint8_t gf16_log[16] = {
  40.         0x00, 0x0f, 0x01, 0x04, 0x02, 0x08, 0x05, 0x0a,
  41.         0x03, 0x0e, 0x09, 0x07, 0x06, 0x0d, 0x0b, 0x0c
  42. };
  43.  
  44. static const struct galois_field gf16 = {
  45.         .p = 15,
  46.         .log = gf16_log,
  47.         .exp = gf16_exp
  48. };
  49.  
  50. static const uint8_t gf256_exp[256] = {
  51.         0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80,
  52.         0x1d, 0x3a, 0x74, 0xe8, 0xcd, 0x87, 0x13, 0x26,
  53.         0x4c, 0x98, 0x2d, 0x5a, 0xb4, 0x75, 0xea, 0xc9,
  54.         0x8f, 0x03, 0x06, 0x0c, 0x18, 0x30, 0x60, 0xc0,
  55.         0x9d, 0x27, 0x4e, 0x9c, 0x25, 0x4a, 0x94, 0x35,
  56.         0x6a, 0xd4, 0xb5, 0x77, 0xee, 0xc1, 0x9f, 0x23,
  57.         0x46, 0x8c, 0x05, 0x0a, 0x14, 0x28, 0x50, 0xa0,
  58.         0x5d, 0xba, 0x69, 0xd2, 0xb9, 0x6f, 0xde, 0xa1,
  59.         0x5f, 0xbe, 0x61, 0xc2, 0x99, 0x2f, 0x5e, 0xbc,
  60.         0x65, 0xca, 0x89, 0x0f, 0x1e, 0x3c, 0x78, 0xf0,
  61.         0xfd, 0xe7, 0xd3, 0xbb, 0x6b, 0xd6, 0xb1, 0x7f,
  62.         0xfe, 0xe1, 0xdf, 0xa3, 0x5b, 0xb6, 0x71, 0xe2,
  63.         0xd9, 0xaf, 0x43, 0x86, 0x11, 0x22, 0x44, 0x88,
  64.         0x0d, 0x1a, 0x34, 0x68, 0xd0, 0xbd, 0x67, 0xce,
  65.         0x81, 0x1f, 0x3e, 0x7c, 0xf8, 0xed, 0xc7, 0x93,
  66.         0x3b, 0x76, 0xec, 0xc5, 0x97, 0x33, 0x66, 0xcc,
  67.         0x85, 0x17, 0x2e, 0x5c, 0xb8, 0x6d, 0xda, 0xa9,
  68.         0x4f, 0x9e, 0x21, 0x42, 0x84, 0x15, 0x2a, 0x54,
  69.         0xa8, 0x4d, 0x9a, 0x29, 0x52, 0xa4, 0x55, 0xaa,
  70.         0x49, 0x92, 0x39, 0x72, 0xe4, 0xd5, 0xb7, 0x73,
  71.         0xe6, 0xd1, 0xbf, 0x63, 0xc6, 0x91, 0x3f, 0x7e,
  72.         0xfc, 0xe5, 0xd7, 0xb3, 0x7b, 0xf6, 0xf1, 0xff,
  73.         0xe3, 0xdb, 0xab, 0x4b, 0x96, 0x31, 0x62, 0xc4,
  74.         0x95, 0x37, 0x6e, 0xdc, 0xa5, 0x57, 0xae, 0x41,
  75.         0x82, 0x19, 0x32, 0x64, 0xc8, 0x8d, 0x07, 0x0e,
  76.         0x1c, 0x38, 0x70, 0xe0, 0xdd, 0xa7, 0x53, 0xa6,
  77.         0x51, 0xa2, 0x59, 0xb2, 0x79, 0xf2, 0xf9, 0xef,
  78.         0xc3, 0x9b, 0x2b, 0x56, 0xac, 0x45, 0x8a, 0x09,
  79.         0x12, 0x24, 0x48, 0x90, 0x3d, 0x7a, 0xf4, 0xf5,
  80.         0xf7, 0xf3, 0xfb, 0xeb, 0xcb, 0x8b, 0x0b, 0x16,
  81.         0x2c, 0x58, 0xb0, 0x7d, 0xfa, 0xe9, 0xcf, 0x83,
  82.         0x1b, 0x36, 0x6c, 0xd8, 0xad, 0x47, 0x8e, 0x01
  83. };
  84.  
  85. static const uint8_t gf256_log[256] = {
  86.         0x00, 0xff, 0x01, 0x19, 0x02, 0x32, 0x1a, 0xc6,
  87.         0x03, 0xdf, 0x33, 0xee, 0x1b, 0x68, 0xc7, 0x4b,
  88.         0x04, 0x64, 0xe0, 0x0e, 0x34, 0x8d, 0xef, 0x81,
  89.         0x1c, 0xc1, 0x69, 0xf8, 0xc8, 0x08, 0x4c, 0x71,
  90.         0x05, 0x8a, 0x65, 0x2f, 0xe1, 0x24, 0x0f, 0x21,
  91.         0x35, 0x93, 0x8e, 0xda, 0xf0, 0x12, 0x82, 0x45,
  92.         0x1d, 0xb5, 0xc2, 0x7d, 0x6a, 0x27, 0xf9, 0xb9,
  93.         0xc9, 0x9a, 0x09, 0x78, 0x4d, 0xe4, 0x72, 0xa6,
  94.         0x06, 0xbf, 0x8b, 0x62, 0x66, 0xdd, 0x30, 0xfd,
  95.         0xe2, 0x98, 0x25, 0xb3, 0x10, 0x91, 0x22, 0x88,
  96.         0x36, 0xd0, 0x94, 0xce, 0x8f, 0x96, 0xdb, 0xbd,
  97.         0xf1, 0xd2, 0x13, 0x5c, 0x83, 0x38, 0x46, 0x40,
  98.         0x1e, 0x42, 0xb6, 0xa3, 0xc3, 0x48, 0x7e, 0x6e,
  99.         0x6b, 0x3a, 0x28, 0x54, 0xfa, 0x85, 0xba, 0x3d,
  100.         0xca, 0x5e, 0x9b, 0x9f, 0x0a, 0x15, 0x79, 0x2b,
  101.         0x4e, 0xd4, 0xe5, 0xac, 0x73, 0xf3, 0xa7, 0x57,
  102.         0x07, 0x70, 0xc0, 0xf7, 0x8c, 0x80, 0x63, 0x0d,
  103.         0x67, 0x4a, 0xde, 0xed, 0x31, 0xc5, 0xfe, 0x18,
  104.         0xe3, 0xa5, 0x99, 0x77, 0x26, 0xb8, 0xb4, 0x7c,
  105.         0x11, 0x44, 0x92, 0xd9, 0x23, 0x20, 0x89, 0x2e,
  106.         0x37, 0x3f, 0xd1, 0x5b, 0x95, 0xbc, 0xcf, 0xcd,
  107.         0x90, 0x87, 0x97, 0xb2, 0xdc, 0xfc, 0xbe, 0x61,
  108.         0xf2, 0x56, 0xd3, 0xab, 0x14, 0x2a, 0x5d, 0x9e,
  109.         0x84, 0x3c, 0x39, 0x53, 0x47, 0x6d, 0x41, 0xa2,
  110.         0x1f, 0x2d, 0x43, 0xd8, 0xb7, 0x7b, 0xa4, 0x76,
  111.         0xc4, 0x17, 0x49, 0xec, 0x7f, 0x0c, 0x6f, 0xf6,
  112.         0x6c, 0xa1, 0x3b, 0x52, 0x29, 0x9d, 0x55, 0xaa,
  113.         0xfb, 0x60, 0x86, 0xb1, 0xbb, 0xcc, 0x3e, 0x5a,
  114.         0xcb, 0x59, 0x5f, 0xb0, 0x9c, 0xa9, 0xa0, 0x51,
  115.         0x0b, 0xf5, 0x16, 0xeb, 0x7a, 0x75, 0x2c, 0xd7,
  116.         0x4f, 0xae, 0xd5, 0xe9, 0xe6, 0xe7, 0xad, 0xe8,
  117.         0x74, 0xd6, 0xf4, 0xea, 0xa8, 0x50, 0x58, 0xaf
  118. };
  119.  
  120. static const struct galois_field gf256 = {
  121.         .p = 255,
  122.         .log = gf256_log,
  123.         .exp = gf256_exp
  124. };
  125.  
  126. /************************************************************************
  127.  * Polynomial operations
  128.  */
  129.  
  130. static void poly_add(uint8_t *dst, const uint8_t *src, uint8_t c,
  131.                      int shift, const struct galois_field *gf)
  132. {
  133.         int i;
  134.         int log_c = gf->log[c];
  135.  
  136.         if (!c)
  137.                 return;
  138.  
  139.         for (i = 0; i < MAX_POLY; i++) {
  140.                 int p = i + shift;
  141.                 uint8_t v = src[i];
  142.  
  143.                 if (p < 0 || p >= MAX_POLY)
  144.                         continue;
  145.                 if (!v)
  146.                         continue;
  147.  
  148.                 dst[p] ^= gf->exp[(gf->log[v] + log_c) % gf->p];
  149.         }
  150. }
  151.  
  152. static uint8_t poly_eval(const uint8_t *s, uint8_t x,
  153.                          const struct galois_field *gf)
  154. {
  155.         int i;
  156.         uint8_t sum = 0;
  157.         uint8_t log_x = gf->log[x];
  158.  
  159.         if (!x)
  160.                 return s[0];
  161.  
  162.         for (i = 0; i < MAX_POLY; i++) {
  163.                 uint8_t c = s[i];
  164.  
  165.                 if (!c)
  166.                         continue;
  167.  
  168.                 sum ^= gf->exp[(gf->log[c] + log_x * i) % gf->p];
  169.         }
  170.  
  171.         return sum;
  172. }
  173.  
  174. /************************************************************************
  175.  * Berlekamp-Massey algorithm for finding error locator polynomials.
  176.  */
  177.  
  178. static void berlekamp_massey(const uint8_t *s, int N,
  179.                              const struct galois_field *gf,
  180.                              uint8_t *sigma)
  181. {
  182.         uint8_t C[MAX_POLY];
  183.         uint8_t B[MAX_POLY];
  184.         int L = 0;
  185.         int m = 1;
  186.         uint8_t b = 1;
  187.         int n;
  188.  
  189.         memset(B, 0, sizeof(B));
  190.         memset(C, 0, sizeof(C));
  191.         B[0] = 1;
  192.         C[0] = 1;
  193.  
  194.         for (n = 0; n < N; n++) {
  195.                 uint8_t d = s[n];
  196.                 uint8_t mult;
  197.                 int i;
  198.  
  199.                 for (i = 1; i <= L; i++) {
  200.                         if (!(C[i] && s[n - i]))
  201.                                 continue;
  202.  
  203.                         d ^= gf->exp[(gf->log[C[i]] +
  204.                                       gf->log[s[n - i]]) %
  205.                                      gf->p];
  206.                 }
  207.  
  208.                 mult = gf->exp[(gf->p - gf->log[b] + gf->log[d]) % gf->p];
  209.  
  210.                 if (!d) {
  211.                         m++;
  212.                 } else if (L * 2 <= n) {
  213.                         uint8_t T[MAX_POLY];
  214.  
  215.                         memcpy(T, C, sizeof(T));
  216.                         poly_add(C, B, mult, m, gf);
  217.                         memcpy(B, T, sizeof(B));
  218.                         L = n + 1 - L;
  219.                         b = d;
  220.                         m = 1;
  221.                 } else {
  222.                         poly_add(C, B, mult, m, gf);
  223.                         m++;
  224.                 }
  225.         }
  226.  
  227.         memcpy(sigma, C, MAX_POLY);
  228. }
  229.  
  230. /************************************************************************
  231.  * Code stream error correction
  232.  *
  233.  * Generator polynomial for GF(2^8) is x^8 + x^4 + x^3 + x^2 + 1
  234.  */
  235.  
  236. static int block_syndromes(const uint8_t *data, int bs, int npar, uint8_t *s)
  237. {
  238.         int nonzero = 0;
  239.         int i;
  240.  
  241.         memset(s, 0, MAX_POLY);
  242.  
  243.         for (i = 0; i < npar; i++) {
  244.                 int j;
  245.  
  246.                 for (j = 0; j < bs; j++) {
  247.                         uint8_t c = data[bs - j - 1];
  248.  
  249.                         if (!c)
  250.                                 continue;
  251.  
  252.                         s[i] ^= gf256_exp[((int)gf256_log[c] +
  253.                                     i * j) % 255];
  254.                 }
  255.  
  256.                 if (s[i])
  257.                         nonzero = 1;
  258.         }
  259.  
  260.         return nonzero;
  261. }
  262.  
  263. static void eloc_poly(uint8_t *omega,
  264.                       const uint8_t *s, const uint8_t *sigma,
  265.                       int npar)
  266. {
  267.         int i;
  268.  
  269.         memset(omega, 0, MAX_POLY);
  270.  
  271.         for (i = 0; i < npar; i++) {
  272.                 const uint8_t a = sigma[i];
  273.                 const uint8_t log_a = gf256_log[a];
  274.                 int j;
  275.  
  276.                 if (!a)
  277.                         continue;
  278.  
  279.                 for (j = 0; j + 1 < MAX_POLY; j++) {
  280.                         const uint8_t b = s[j + 1];
  281.  
  282.                         if (i + j >= npar)
  283.                                 break;
  284.  
  285.                         if (!b)
  286.                                 continue;
  287.  
  288.                         omega[i + j] ^=
  289.                             gf256_exp[(log_a + gf256_log[b]) % 255];
  290.                 }
  291.         }
  292. }
  293.  
  294. static quirc_decode_error_t correct_block(uint8_t *data,
  295.                                           const struct quirc_rs_params *ecc)
  296. {
  297.         int npar = ecc->bs - ecc->dw;
  298.         uint8_t s[MAX_POLY];
  299.         uint8_t sigma[MAX_POLY];
  300.         uint8_t sigma_deriv[MAX_POLY];
  301.         uint8_t omega[MAX_POLY];
  302.         int i;
  303.  
  304.         /* Compute syndrome vector */
  305.         if (!block_syndromes(data, ecc->bs, npar, s))
  306.                 return QUIRC_SUCCESS;
  307.  
  308.         berlekamp_massey(s, npar, &gf256, sigma);
  309.  
  310.         /* Compute derivative of sigma */
  311.         memset(sigma_deriv, 0, MAX_POLY);
  312.         for (i = 0; i + 1 < MAX_POLY; i += 2)
  313.                 sigma_deriv[i] = sigma[i + 1];
  314.  
  315.         /* Compute error evaluator polynomial */
  316.         eloc_poly(omega, s, sigma, npar - 1);
  317.  
  318.         /* Find error locations and magnitudes */
  319.         for (i = 0; i < ecc->bs; i++) {
  320.                 uint8_t xinv = gf256_exp[255 - i];
  321.  
  322.                 if (!poly_eval(sigma, xinv, &gf256)) {
  323.                         uint8_t sd_x = poly_eval(sigma_deriv, xinv, &gf256);
  324.                         uint8_t omega_x = poly_eval(omega, xinv, &gf256);
  325.                         uint8_t error = gf256_exp[(255 - gf256_log[sd_x] +
  326.                                                    gf256_log[omega_x]) % 255];
  327.  
  328.                         data[ecc->bs - i - 1] ^= error;
  329.                 }
  330.         }
  331.  
  332.         if (block_syndromes(data, ecc->bs, npar, s))
  333.                 return QUIRC_ERROR_DATA_ECC;
  334.  
  335.         return QUIRC_SUCCESS;
  336. }
  337.  
  338. /************************************************************************
  339.  * Format value error correction
  340.  *
  341.  * Generator polynomial for GF(2^4) is x^4 + x + 1
  342.  */
  343.  
  344. #define FORMAT_MAX_ERROR        3
  345. #define FORMAT_SYNDROMES        (FORMAT_MAX_ERROR * 2)
  346. #define FORMAT_BITS             15
  347.  
  348. static int format_syndromes(uint16_t u, uint8_t *s)
  349. {
  350.         int i;
  351.         int nonzero = 0;
  352.  
  353.         memset(s, 0, MAX_POLY);
  354.  
  355.         for (i = 0; i < FORMAT_SYNDROMES; i++) {
  356.                 int j;
  357.  
  358.                 s[i] = 0;
  359.                 for (j = 0; j < FORMAT_BITS; j++)
  360.                         if (u & (1 << j))
  361.                                 s[i] ^= gf16_exp[((i + 1) * j) % 15];
  362.  
  363.                 if (s[i])
  364.                         nonzero = 1;
  365.         }
  366.  
  367.         return nonzero;
  368. }
  369.  
  370. static quirc_decode_error_t correct_format(uint16_t *f_ret)
  371. {
  372.         uint16_t u = *f_ret;
  373.         int i;
  374.         uint8_t s[MAX_POLY];
  375.         uint8_t sigma[MAX_POLY];
  376.  
  377.         /* Evaluate U (received codeword) at each of alpha_1 .. alpha_6
  378.          * to get S_1 .. S_6 (but we index them from 0).
  379.          */
  380.         if (!format_syndromes(u, s))
  381.                 return QUIRC_SUCCESS;
  382.  
  383.         berlekamp_massey(s, FORMAT_SYNDROMES, &gf16, sigma);
  384.  
  385.         /* Now, find the roots of the polynomial */
  386.         for (i = 0; i < 15; i++)
  387.                 if (!poly_eval(sigma, gf16_exp[15 - i], &gf16))
  388.                         u ^= (1 << i);
  389.  
  390.         if (format_syndromes(u, s))
  391.                 return QUIRC_ERROR_FORMAT_ECC;
  392.  
  393.         *f_ret = u;
  394.         return QUIRC_SUCCESS;
  395. }
  396.  
  397. /************************************************************************
  398.  * Decoder algorithm
  399.  */
  400.  
  401. struct datastream {
  402.         uint8_t         raw[QUIRC_MAX_PAYLOAD];
  403.         int             data_bits;
  404.         int             ptr;
  405.  
  406.         uint8_t         data[QUIRC_MAX_PAYLOAD];
  407. };
  408.  
  409. static inline int grid_bit(const struct quirc_code *code, int x, int y)
  410. {
  411.         int p = y * code->size + x;
  412.         return (code->cell_bitmap[p >> 3] >> (p & 7)) & 1;
  413. }
  414.  
  415. static quirc_decode_error_t read_format(const struct quirc_code *code,
  416.                                         struct quirc_data *data, int which)
  417. {
  418.         int i;
  419.         uint16_t format = 0;
  420.         uint16_t fdata;
  421.         quirc_decode_error_t err;
  422.  
  423.         if (which) {
  424.                 for (i = 0; i < 7; i++)
  425.                         format = (format << 1) |
  426.                                 grid_bit(code, 8, code->size - 1 - i);
  427.                 for (i = 0; i < 8; i++)
  428.                         format = (format << 1) |
  429.                                 grid_bit(code, code->size - 8 + i, 8);
  430.         } else {
  431.                 static const int xs[15] = {
  432.                         8, 8, 8, 8, 8, 8, 8, 8, 7, 5, 4, 3, 2, 1, 0
  433.                 };
  434.                 static const int ys[15] = {
  435.                         0, 1, 2, 3, 4, 5, 7, 8, 8, 8, 8, 8, 8, 8, 8
  436.                 };
  437.  
  438.                 for (i = 14; i >= 0; i--)
  439.                         format = (format << 1) | grid_bit(code, xs[i], ys[i]);
  440.         }
  441.  
  442.         format ^= 0x5412;
  443.  
  444.         err = correct_format(&format);
  445.         if (err)
  446.                 return err;
  447.  
  448.         fdata = format >> 10;
  449.         data->ecc_level = fdata >> 3;
  450.         data->mask = fdata & 7;
  451.  
  452.         return QUIRC_SUCCESS;
  453. }
  454.  
  455. static int mask_bit(int mask, int i, int j)
  456. {
  457.         switch (mask) {
  458.         case 0: return !((i + j) % 2);
  459.         case 1: return !(i % 2);
  460.         case 2: return !(j % 3);
  461.         case 3: return !((i + j) % 3);
  462.         case 4: return !(((i / 2) + (j / 3)) % 2);
  463.         case 5: return !((i * j) % 2 + (i * j) % 3);
  464.         case 6: return !(((i * j) % 2 + (i * j) % 3) % 2);
  465.         case 7: return !(((i * j) % 3 + (i + j) % 2) % 2);
  466.         }
  467.  
  468.         return 0;
  469. }
  470.  
  471. static int reserved_cell(int version, int i, int j)
  472. {
  473.         const struct quirc_version_info *ver = &quirc_version_db[version];
  474.         int size = version * 4 + 17;
  475.         int ai = -1, aj = -1, a;
  476.  
  477.         /* Finder + format: top left */
  478.         if (i < 9 && j < 9)
  479.                 return 1;
  480.  
  481.         /* Finder + format: bottom left */
  482.         if (i + 8 >= size && j < 9)
  483.                 return 1;
  484.  
  485.         /* Finder + format: top right */
  486.         if (i < 9 && j + 8 >= size)
  487.                 return 1;
  488.  
  489.         /* Exclude timing patterns */
  490.         if (i == 6 || j == 6)
  491.                 return 1;
  492.  
  493.         /* Exclude version info, if it exists. Version info sits adjacent to
  494.          * the top-right and bottom-left finders in three rows, bounded by
  495.          * the timing pattern.
  496.          */
  497.         if (version >= 7) {
  498.                 if (i < 6 && j + 11 >= size)
  499.                         return 1;
  500.                 if (i + 11 >= size && j < 6)
  501.                         return 1;
  502.         }
  503.  
  504.         /* Exclude alignment patterns */
  505.         for (a = 0; a < QUIRC_MAX_ALIGNMENT && ver->apat[a]; a++) {
  506.                 int p = ver->apat[a];
  507.  
  508.                 if (abs(p - i) < 3)
  509.                         ai = a;
  510.                 if (abs(p - j) < 3)
  511.                         aj = a;
  512.         }
  513.  
  514.         if (ai >= 0 && aj >= 0) {
  515.                 a--;
  516.                 if (ai > 0 && ai < a)
  517.                         return 1;
  518.                 if (aj > 0 && aj < a)
  519.                         return 1;
  520.                 if (aj == a && ai == a)
  521.                         return 1;
  522.         }
  523.  
  524.         return 0;
  525. }
  526.  
  527. static void read_bit(const struct quirc_code *code,
  528.                      struct quirc_data *data,
  529.                      struct datastream *ds, int i, int j)
  530. {
  531.         int bitpos = ds->data_bits & 7;
  532.         int bytepos = ds->data_bits >> 3;
  533.         int v = grid_bit(code, j, i);
  534.  
  535.         if (mask_bit(data->mask, i, j))
  536.                 v ^= 1;
  537.  
  538.         if (v)
  539.                 ds->raw[bytepos] |= (0x80 >> bitpos);
  540.  
  541.         ds->data_bits++;
  542. }
  543.  
  544. static void read_data(const struct quirc_code *code,
  545.                       struct quirc_data *data,
  546.                       struct datastream *ds)
  547. {
  548.         int y = code->size - 1;
  549.         int x = code->size - 1;
  550.         int dir = -1;
  551.  
  552.         while (x > 0) {
  553.                 if (x == 6)
  554.                         x--;
  555.  
  556.                 if (!reserved_cell(data->version, y, x))
  557.                         read_bit(code, data, ds, y, x);
  558.  
  559.                 if (!reserved_cell(data->version, y, x - 1))
  560.                         read_bit(code, data, ds, y, x - 1);
  561.  
  562.                 y += dir;
  563.                 if (y < 0 || y >= code->size) {
  564.                         dir = -dir;
  565.                         x -= 2;
  566.                         y += dir;
  567.                 }
  568.         }
  569. }
  570.  
  571. static quirc_decode_error_t codestream_ecc(struct quirc_data *data,
  572.                                            struct datastream *ds)
  573. {
  574.         const struct quirc_version_info *ver =
  575.                 &quirc_version_db[data->version];
  576.         const struct quirc_rs_params *sb_ecc = &ver->ecc[data->ecc_level];
  577.         struct quirc_rs_params lb_ecc;
  578.         const int lb_count =
  579.             (ver->data_bytes - sb_ecc->bs * sb_ecc->ns) / (sb_ecc->bs + 1);
  580.         const int bc = lb_count + sb_ecc->ns;
  581.         const int ecc_offset = sb_ecc->dw * bc + lb_count;
  582.         int dst_offset = 0;
  583.         int i;
  584.  
  585.         memcpy(&lb_ecc, sb_ecc, sizeof(lb_ecc));
  586.         lb_ecc.dw++;
  587.         lb_ecc.bs++;
  588.  
  589.         for (i = 0; i < bc; i++) {
  590.                 uint8_t *dst = ds->data + dst_offset;
  591.                 const struct quirc_rs_params *ecc =
  592.                     (i < sb_ecc->ns) ? sb_ecc : &lb_ecc;
  593.                 const int num_ec = ecc->bs - ecc->dw;
  594.                 quirc_decode_error_t err;
  595.                 int j;
  596.  
  597.                 for (j = 0; j < ecc->dw; j++)
  598.                         dst[j] = ds->raw[j * bc + i];
  599.                 for (j = 0; j < num_ec; j++)
  600.                         dst[ecc->dw + j] = ds->raw[ecc_offset + j * bc + i];
  601.  
  602.                 err = correct_block(dst, ecc);
  603.                 if (err)
  604.                         return err;
  605.  
  606.                 dst_offset += ecc->dw;
  607.         }
  608.  
  609.         ds->data_bits = dst_offset * 8;
  610.  
  611.         return QUIRC_SUCCESS;
  612. }
  613.  
  614. static inline int bits_remaining(const struct datastream *ds)
  615. {
  616.         return ds->data_bits - ds->ptr;
  617. }
  618.  
  619. static int take_bits(struct datastream *ds, int len)
  620. {
  621.         int ret = 0;
  622.  
  623.         while (len && (ds->ptr < ds->data_bits)) {
  624.                 uint8_t b = ds->data[ds->ptr >> 3];
  625.                 int bitpos = ds->ptr & 7;
  626.  
  627.                 ret <<= 1;
  628.                 if ((b << bitpos) & 0x80)
  629.                         ret |= 1;
  630.  
  631.                 ds->ptr++;
  632.                 len--;
  633.         }
  634.  
  635.         return ret;
  636. }
  637.  
  638. static int numeric_tuple(struct quirc_data *data,
  639.                          struct datastream *ds,
  640.                          int bits, int digits)
  641. {
  642.         int tuple;
  643.         int i;
  644.  
  645.         if (bits_remaining(ds) < bits)
  646.                 return -1;
  647.  
  648.         tuple = take_bits(ds, bits);
  649.  
  650.         for (i = digits - 1; i >= 0; i--) {
  651.                 data->payload[data->payload_len + i] = tuple % 10 + '0';
  652.                 tuple /= 10;
  653.         }
  654.  
  655.         data->payload_len += digits;
  656.         return 0;
  657. }
  658.  
  659. static quirc_decode_error_t decode_numeric(struct quirc_data *data,
  660.                                            struct datastream *ds)
  661. {
  662.         int bits = 14;
  663.         int count;
  664.  
  665.         if (data->version < 10)
  666.                 bits = 10;
  667.         else if (data->version < 27)
  668.                 bits = 12;
  669.  
  670.         count = take_bits(ds, bits);
  671.         if (data->payload_len + count + 1 > QUIRC_MAX_PAYLOAD)
  672.                 return QUIRC_ERROR_DATA_OVERFLOW;
  673.  
  674.         while (count >= 3) {
  675.                 if (numeric_tuple(data, ds, 10, 3) < 0)
  676.                         return QUIRC_ERROR_DATA_UNDERFLOW;
  677.                 count -= 3;
  678.         }
  679.  
  680.         if (count >= 2) {
  681.                 if (numeric_tuple(data, ds, 7, 2) < 0)
  682.                         return QUIRC_ERROR_DATA_UNDERFLOW;
  683.                 count -= 2;
  684.         }
  685.  
  686.         if (count) {
  687.                 if (numeric_tuple(data, ds, 4, 1) < 0)
  688.                         return QUIRC_ERROR_DATA_UNDERFLOW;
  689.                 count--;
  690.         }
  691.  
  692.         return QUIRC_SUCCESS;
  693. }
  694.  
  695. static int alpha_tuple(struct quirc_data *data,
  696.                        struct datastream *ds,
  697.                        int bits, int digits)
  698. {
  699.         int tuple;
  700.         int i;
  701.  
  702.         if (bits_remaining(ds) < bits)
  703.                 return -1;
  704.  
  705.         tuple = take_bits(ds, bits);
  706.  
  707.         for (i = 0; i < digits; i++) {
  708.                 static const char *alpha_map =
  709.                         "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:";
  710.  
  711.                 data->payload[data->payload_len + digits - i - 1] =
  712.                         alpha_map[tuple % 45];
  713.                 tuple /= 45;
  714.         }
  715.  
  716.         data->payload_len += digits;
  717.         return 0;
  718. }
  719.  
  720. static quirc_decode_error_t decode_alpha(struct quirc_data *data,
  721.                                          struct datastream *ds)
  722. {
  723.         int bits = 13;
  724.         int count;
  725.  
  726.         if (data->version < 10)
  727.                 bits = 9;
  728.         else if (data->version < 27)
  729.                 bits = 11;
  730.  
  731.         count = take_bits(ds, bits);
  732.         if (data->payload_len + count + 1 > QUIRC_MAX_PAYLOAD)
  733.                 return QUIRC_ERROR_DATA_OVERFLOW;
  734.  
  735.         while (count >= 2) {
  736.                 if (alpha_tuple(data, ds, 11, 2) < 0)
  737.                         return QUIRC_ERROR_DATA_UNDERFLOW;
  738.                 count -= 2;
  739.         }
  740.  
  741.         if (count) {
  742.                 if (alpha_tuple(data, ds, 6, 1) < 0)
  743.                         return QUIRC_ERROR_DATA_UNDERFLOW;
  744.                 count--;
  745.         }
  746.  
  747.         return QUIRC_SUCCESS;
  748. }
  749.  
  750. static quirc_decode_error_t decode_byte(struct quirc_data *data,
  751.                                         struct datastream *ds)
  752. {
  753.         int bits = 16;
  754.         int count;
  755.         int i;
  756.  
  757.         if (data->version < 10)
  758.                 bits = 8;
  759.  
  760.         count = take_bits(ds, bits);
  761.         if (data->payload_len + count + 1 > QUIRC_MAX_PAYLOAD)
  762.                 return QUIRC_ERROR_DATA_OVERFLOW;
  763.         if (bits_remaining(ds) < count * 8)
  764.                 return QUIRC_ERROR_DATA_UNDERFLOW;
  765.  
  766.         for (i = 0; i < count; i++)
  767.                 data->payload[data->payload_len++] = take_bits(ds, 8);
  768.  
  769.         return QUIRC_SUCCESS;
  770. }
  771.  
  772. static quirc_decode_error_t decode_kanji(struct quirc_data *data,
  773.                                          struct datastream *ds)
  774. {
  775.         int bits = 12;
  776.         int count;
  777.         int i;
  778.  
  779.         if (data->version < 10)
  780.                 bits = 8;
  781.         else if (data->version < 27)
  782.                 bits = 10;
  783.  
  784.         count = take_bits(ds, bits);
  785.         if (data->payload_len + count * 2 + 1 > QUIRC_MAX_PAYLOAD)
  786.                 return QUIRC_ERROR_DATA_OVERFLOW;
  787.         if (bits_remaining(ds) < count * 13)
  788.                 return QUIRC_ERROR_DATA_UNDERFLOW;
  789.  
  790.         for (i = 0; i < count; i++) {
  791.                 int d = take_bits(ds, 13);
  792.                 int msB = d / 0xc0;
  793.                 int lsB = d % 0xc0;
  794.                 int intermediate = (msB << 8) | lsB;
  795.                 uint16_t sjw;
  796.  
  797.                 if (intermediate + 0x8140 <= 0x9ffc) {
  798.                         /* bytes are in the range 0x8140 to 0x9FFC */
  799.                         sjw = intermediate + 0x8140;
  800.                 } else {
  801.                         /* bytes are in the range 0xE040 to 0xEBBF */
  802.                         sjw = intermediate + 0xc140;
  803.                 }
  804.  
  805.                 data->payload[data->payload_len++] = sjw >> 8;
  806.                 data->payload[data->payload_len++] = sjw & 0xff;
  807.         }
  808.  
  809.         return QUIRC_SUCCESS;
  810. }
  811.  
  812. static quirc_decode_error_t decode_eci(struct quirc_data *data,
  813.                                        struct datastream *ds)
  814. {
  815.         if (bits_remaining(ds) < 8)
  816.                 return QUIRC_ERROR_DATA_UNDERFLOW;
  817.  
  818.         data->eci = take_bits(ds, 8);
  819.  
  820.         if ((data->eci & 0xc0) == 0x80) {
  821.                 if (bits_remaining(ds) < 8)
  822.                         return QUIRC_ERROR_DATA_UNDERFLOW;
  823.  
  824.                 data->eci = (data->eci << 8) | take_bits(ds, 8);
  825.         } else if ((data->eci & 0xe0) == 0xc0) {
  826.                 if (bits_remaining(ds) < 16)
  827.                         return QUIRC_ERROR_DATA_UNDERFLOW;
  828.  
  829.                 data->eci = (data->eci << 16) | take_bits(ds, 16);
  830.         }
  831.  
  832.         return QUIRC_SUCCESS;
  833. }
  834.  
  835. static quirc_decode_error_t decode_payload(struct quirc_data *data,
  836.                                            struct datastream *ds)
  837. {
  838.         while (bits_remaining(ds) >= 4) {
  839.                 quirc_decode_error_t err = QUIRC_SUCCESS;
  840.                 int type = take_bits(ds, 4);
  841.  
  842.                 switch (type) {
  843.                 case QUIRC_DATA_TYPE_NUMERIC:
  844.                         err = decode_numeric(data, ds);
  845.                         break;
  846.  
  847.                 case QUIRC_DATA_TYPE_ALPHA:
  848.                         err = decode_alpha(data, ds);
  849.                         break;
  850.  
  851.                 case QUIRC_DATA_TYPE_BYTE:
  852.                         err = decode_byte(data, ds);
  853.                         break;
  854.  
  855.                 case QUIRC_DATA_TYPE_KANJI:
  856.                         err = decode_kanji(data, ds);
  857.                         break;
  858.  
  859.                 case 7:
  860.                         err = decode_eci(data, ds);
  861.                         break;
  862.  
  863.                 default:
  864.                         goto done;
  865.                 }
  866.  
  867.                 if (err)
  868.                         return err;
  869.  
  870.                 if (!(type & (type - 1)) && (type > data->data_type))
  871.                         data->data_type = type;
  872.         }
  873. done:
  874.  
  875.         /* Add nul terminator to all payloads */
  876.         if (data->payload_len >= (int) sizeof(data->payload))
  877.                 data->payload_len--;
  878.         data->payload[data->payload_len] = 0;
  879.  
  880.         return QUIRC_SUCCESS;
  881. }
  882.  
  883. quirc_decode_error_t quirc_decode(const struct quirc_code *code,
  884.                                   struct quirc_data *data)
  885. {
  886.         quirc_decode_error_t err;
  887.         struct datastream ds;
  888.  
  889.         if ((code->size - 17) % 4)
  890.                 return QUIRC_ERROR_INVALID_GRID_SIZE;
  891.  
  892.         memset(data, 0, sizeof(*data));
  893.         memset(&ds, 0, sizeof(ds));
  894.  
  895.         data->version = (code->size - 17) / 4;
  896.  
  897.         if (data->version < 1 ||
  898.             data->version > QUIRC_MAX_VERSION)
  899.                 return QUIRC_ERROR_INVALID_VERSION;
  900.  
  901.         /* Read format information -- try both locations */
  902.         err = read_format(code, data, 0);
  903.         if (err)
  904.                 err = read_format(code, data, 1);
  905.         if (err)
  906.                 return err;
  907.  
  908.         read_data(code, data, &ds);
  909.         err = codestream_ecc(data, &ds);
  910.         if (err)
  911.                 return err;
  912.  
  913.         err = decode_payload(data, &ds);
  914.         if (err)
  915.                 return err;
  916.  
  917.         return QUIRC_SUCCESS;
  918. }
  919.  
  920. void quirc_flip(struct quirc_code *code)
  921. {
  922.         struct quirc_code flipped = {0};
  923.         unsigned int offset = 0;
  924.         for (int y = 0; y < code->size; y++) {
  925.                 for (int x = 0; x < code->size; x++) {
  926.                         if (grid_bit(code, y, x)) {
  927.                                 flipped.cell_bitmap[offset >> 3u] |= (1u << (offset & 7u));
  928.                         }
  929.                         offset++;
  930.                 }
  931.         }
  932.         memcpy(&code->cell_bitmap, &flipped.cell_bitmap, sizeof(flipped.cell_bitmap));
  933. }
  934.