LordOS — a free, fast and secure GNU/Linux distribution based on Debian, with its own desktop environment: display server and Wayland compositor in C, a React UI engine on QuickJS, and private native apps.
C cdebiandesktop-environmentebpffirewalllandlocklinuxlinux-distributionopen-sourceprivacyquickjsraspberry-pi-5reactsecuritywaylandwayland-compositor
/* qr.c — our own QR codes: encode and decode (see qr.h). ISO/IEC 18004.
*
* Encode: picks the most compact mode (numeric, alphanumeric or byte) and the smallest version
* that fits with the requested correction level; Reed-Solomon over GF(256) (polynomial 0x11d),
* interleaved blocks, function patterns, format and version information (BCH) and the 8 masks
* with the standard's penalty.
*
* Decode: luminance → binarization (global Otsu and Bradley local threshold, normal and inverted) →
* finder patterns by the 1:1:3:1:1 ratio in rows, confirmed in columns → the three
* best (right triangle) → side from the timing pattern and the version
* information → grid (affine, or perspective with the alignment pattern) → format, mask,
* codewords, Reed-Solomon (Berlekamp-Massey + Chien + Forney) → segments. */
#include "qr.h"
#include <math.h>
#include <stdlib.h>
#include <string.h>
/* ================= tables ================= */
static const int8_t ECC_PER_BLOCK[4][41] = {
{ -1, 7,10,15,20,26,18,20,24,30,18,20,24,26,30,22,24,28,30,28,28,28,28,30,30,26,28,30,30,30,30,30,30,30,30,30,30,30,30,30,30 },
{ -1,10,16,26,18,24,16,18,22,22,26,30,22,22,24,24,28,28,26,26,26,26,28,28,28,28,28,28,28,28,28,28,28,28,28,28,28,28,28,28,28 },
{ -1,13,22,18,26,18,24,18,22,20,24,28,26,24,20,30,24,28,28,26,30,28,30,30,30,30,28,30,30,30,30,30,30,30,30,30,30,30,30,30,30 },
{ -1,17,28,22,16,22,28,26,26,24,28,24,28,22,24,24,30,28,28,26,28,30,24,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30 },
};
static const int8_t NUM_BLOCKS[4][41] = {
{ -1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 4, 4, 4, 4, 4, 6, 6, 6, 6, 7, 8, 8, 9, 9,10,12,12,12,13,14,15,16,17,18,19,19,20,21,22,24,25 },
{ -1, 1, 1, 1, 2, 2, 4, 4, 4, 5, 5, 5, 8, 9, 9,10,10,11,13,14,16,17,17,18,20,21,23,25,26,28,29,31,33,35,37,38,40,43,45,47,49 },
{ -1, 1, 1, 2, 2, 4, 4, 6, 6, 8, 8, 8,10,12,16,12,17,16,18,21,20,23,23,25,27,29,34,34,35,38,40,43,45,48,51,53,56,59,62,65,68 },
{ -1, 1, 1, 2, 4, 4, 4, 5, 6, 8, 8,11,11,16,16,18,16,19,21,25,25,25,34,30,32,35,37,40,42,45,48,51,54,57,60,63,66,70,74,77,81 },
};
static const int FORMAT_ECC_BITS[4] = { 1, 0, 3, 2 }; /* L M Q H in the format information */
static const char ALNUM[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:";
static int raw_modules(int ver) {
int r = (16 * ver + 128) * ver + 64;
if (ver >= 2) {
int na = ver / 7 + 2;
r -= (25 * na - 10) * na - 55;
if (ver >= 7) r -= 36;
}
return r;
}
static int data_codewords(int ver, int ecc) { return raw_modules(ver) / 8 - ECC_PER_BLOCK[ecc][ver] * NUM_BLOCKS[ecc][ver]; }
static int align_pos(int ver, int *pos) {
if (ver == 1) return 0;
int na = ver / 7 + 2, size = ver * 4 + 17;
int step = ver == 32 ? 26 : (ver * 4 + na * 2 + 1) / (na * 2 - 2) * 2;
pos[0] = 6;
for (int i = 0, p = size - 7; i < na - 1; i++, p -= step) pos[na - 1 - i] = p;
return na;
}
static int cc_bits(int mode, int ver) {
int g = ver <= 9 ? 0 : ver <= 26 ? 1 : 2;
static const int t[3][3] = { { 10, 12, 14 }, { 9, 11, 13 }, { 8, 16, 16 } };
return t[mode == 1 ? 0 : mode == 2 ? 1 : 2][g];
}
/* ================= GF(256) and Reed-Solomon ================= */
static uint8_t GEXP[512], GLOG[256];
static int gf_ready;
static void gf_init(void) {
if (gf_ready) return;
int x = 1;
for (int i = 0; i < 255; i++) { GEXP[i] = (uint8_t)x; GLOG[x] = (uint8_t)i; x <<= 1; if (x & 0x100) x ^= 0x11d; }
for (int i = 255; i < 512; i++) GEXP[i] = GEXP[i - 255];
gf_ready = 1;
}
static uint8_t gmul(uint8_t a, uint8_t b) { return a && b ? GEXP[GLOG[a] + GLOG[b]] : 0; }
static uint8_t gdiv(uint8_t a, uint8_t b) { return a ? GEXP[(GLOG[a] + 255 - GLOG[b]) % 255] : 0; }
/* Generator of degree d: (x - a^0)(x - a^1)…; coefficients without the leading one (1). */
static void rs_gen(int d, uint8_t *g) {
memset(g, 0, (size_t)d);
g[d - 1] = 1;
uint8_t root = 1;
for (int i = 0; i < d; i++) {
for (int j = 0; j < d; j++) { g[j] = gmul(g[j], root); if (j + 1 < d) g[j] ^= g[j + 1]; }
root = gmul(root, 2);
}
}
static void rs_rem(const uint8_t *data, int n, const uint8_t *g, int d, uint8_t *out) {
memset(out, 0, (size_t)d);
for (int i = 0; i < n; i++) {
uint8_t f = data[i] ^ out[0];
memmove(out, out + 1, (size_t)d - 1);
out[d - 1] = 0;
for (int j = 0; j < d; j++) out[j] ^= gmul(g[j], f);
}
}
/* Corrects block c of n bytes with ne correction bytes. 0 = ok (or no errors), -1 if it cannot. */
static int rs_correct(uint8_t *c, int n, int ne) {
uint8_t S[64], L[64], B[64], T[64], O[64];
int any = 0;
for (int j = 0; j < ne; j++) {
uint8_t s = 0, a = GEXP[j];
for (int k = 0; k < n; k++) s = gmul(s, a) ^ c[k];
S[j] = s;
any |= s;
}
if (!any) return 0;
/* Berlekamp-Massey */
memset(L, 0, sizeof L); memset(B, 0, sizeof B);
L[0] = B[0] = 1;
int Ld = 0, m = 1;
uint8_t b = 1;
for (int r = 0; r < ne; r++) {
uint8_t d = S[r];
for (int i = 1; i <= Ld; i++) d ^= gmul(L[i], S[r - i]);
if (!d) { m++; continue; }
memcpy(T, L, sizeof T);
uint8_t coef = gdiv(d, b);
for (int i = 0; i + m < 64; i++) L[i + m] ^= gmul(coef, B[i]);
if (2 * Ld <= r) { Ld = r + 1 - Ld; memcpy(B, T, sizeof B); b = d; m = 1; }
else m++;
}
if (Ld > ne / 2) return -1;
/* Omega = S * Lambda mod x^ne */
for (int i = 0; i < ne; i++) { uint8_t v = 0; for (int j = 0; j <= i && j <= Ld; j++) v ^= gmul(L[j], S[i - j]); O[i] = v; }
/* Chien: positions p = 0..n-1 (power), array index k = n-1-p */
int found = 0;
for (int p = 0; p < n; p++) {
uint8_t xinv = GEXP[(255 - p) % 255];
uint8_t v = 0, xp = 1;
for (int i = 0; i <= Ld; i++) { v ^= gmul(L[i], xp); xp = gmul(xp, xinv); }
if (v) continue;
/* Forney (first root 0): e = X * Omega(X^-1) / Lambda'(X^-1) */
uint8_t om = 0, dl = 0; xp = 1;
for (int i = 0; i < ne; i++) { om ^= gmul(O[i], xp); xp = gmul(xp, xinv); }
xp = 1;
for (int i = 1; i <= Ld; i += 2) { dl ^= gmul(L[i], xp); xp = gmul(xp, gmul(xinv, xinv)); }
if (!dl) return -1;
uint8_t e = gmul(GEXP[p % 255], gdiv(om, dl));
c[n - 1 - p] ^= e;
found++;
}
if (found != Ld) return -1;
for (int j = 0; j < ne; j++) {
uint8_t s = 0, a = GEXP[j];
for (int k = 0; k < n; k++) s = gmul(s, a) ^ c[k];
if (s) return -1;
}
return 0;
}
/* ================= building the matrix ================= */
typedef struct { int size; uint8_t *m, *fn; } Grid;
#define AT(g, x, y) (g)->m[(y) * (g)->size + (x)]
#define FN(g, x, y) (g)->fn[(y) * (g)->size + (x)]
static void setf(Grid *g, int x, int y, int dark) { AT(g, x, y) = (uint8_t)(dark != 0); FN(g, x, y) = 1; }
static void draw_finder(Grid *g, int cx, int cy) {
for (int dy = -4; dy <= 4; dy++) for (int dx = -4; dx <= 4; dx++) {
int x = cx + dx, y = cy + dy;
if (x < 0 || y < 0 || x >= g->size || y >= g->size) continue;
int d = abs(dx) > abs(dy) ? abs(dx) : abs(dy);
setf(g, x, y, d != 2 && d != 4);
}
}
static void draw_align(Grid *g, int cx, int cy) {
for (int dy = -2; dy <= 2; dy++) for (int dx = -2; dx <= 2; dx++) {
int d = abs(dx) > abs(dy) ? abs(dx) : abs(dy);
setf(g, cx + dx, cy + dy, d != 1);
}
}
static int format_bits(int ecc, int mask) {
int data = FORMAT_ECC_BITS[ecc] << 3 | mask, rem = data;
for (int i = 0; i < 10; i++) rem = (rem << 1) ^ ((rem >> 9) * 0x537);
return (data << 10 | rem) ^ 0x5412;
}
static int version_bits(int ver) {
int rem = ver;
for (int i = 0; i < 12; i++) rem = (rem << 1) ^ ((rem >> 11) * 0x1f25);
return ver << 12 | rem;
}
static void draw_format(Grid *g, int bits) {
int s = g->size;
for (int i = 0; i <= 5; i++) setf(g, 8, i, bits >> i & 1);
setf(g, 8, 7, bits >> 6 & 1);
setf(g, 8, 8, bits >> 7 & 1);
setf(g, 7, 8, bits >> 8 & 1);
for (int i = 9; i < 15; i++) setf(g, 14 - i, 8, bits >> i & 1);
for (int i = 0; i < 8; i++) setf(g, s - 1 - i, 8, bits >> i & 1);
for (int i = 8; i < 15; i++) setf(g, 8, s - 15 + i, bits >> i & 1);
setf(g, 8, s - 8, 1);
}
static void draw_functions(Grid *g, int ver) {
int s = g->size;
for (int i = 0; i < s; i++) { setf(g, 6, i, i % 2 == 0); setf(g, i, 6, i % 2 == 0); }
draw_finder(g, 3, 3);
draw_finder(g, s - 4, 3);
draw_finder(g, 3, s - 4);
int pos[7], na = align_pos(ver, pos);
for (int i = 0; i < na; i++) for (int j = 0; j < na; j++) {
if ((i == 0 && j == 0) || (i == 0 && j == na - 1) || (i == na - 1 && j == 0)) continue;
draw_align(g, pos[i], pos[j]);
}
draw_format(g, 0); /* reserve; written later */
if (ver >= 7) {
int bits = version_bits(ver);
for (int i = 0; i < 18; i++) {
int bit = bits >> i & 1, a = s - 11 + i % 3, b = i / 3;
setf(g, a, b, bit);
setf(g, b, a, bit);
}
}
}
static int mask_bit(int mask, int x, int 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 (x / 3 + 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;
default: return ((x + y) % 2 + x * y % 3) % 2 == 0;
}
}
static void apply_mask(Grid *g, int mask) {
for (int y = 0; y < g->size; y++) for (int x = 0; x < g->size; x++)
if (!FN(g, x, y) && mask_bit(mask, x, y)) AT(g, x, y) ^= 1;
}
/* Zigzag traversal of the data modules: calls fn for each one, in order. */
typedef void (*ZigFn)(Grid *g, int x, int y, void *ud);
static void zigzag(Grid *g, ZigFn fn, void *ud) {
int s = g->size;
for (int right = s - 1; right >= 1; right -= 2) {
if (right == 6) right = 5;
for (int v = 0; v < s; v++) for (int j = 0; j < 2; j++) {
int x = right - j, up = ((right + 1) & 2) == 0, y = up ? s - 1 - v : v;
if (!FN(g, x, y)) fn(g, x, y, ud);
}
}
}
typedef struct { const uint8_t *d; int nbits, i; uint8_t *out; } ZigCtx;
static void zig_put(Grid *g, int x, int y, void *ud) {
ZigCtx *z = ud;
if (z->i < z->nbits) AT(g, x, y) = z->d[z->i >> 3] >> (7 - (z->i & 7)) & 1;
z->i++;
}
static void zig_get(Grid *g, int x, int y, void *ud) {
ZigCtx *z = ud;
if (z->i < z->nbits && AT(g, x, y)) z->out[z->i >> 3] |= (uint8_t)(0x80 >> (z->i & 7));
z->i++;
}
/* Penalty from the standard (N1=3, N2=3, N3=40, N4=10). */
static long run_finder_count(const int *h) {
int n = h[1];
int core = n > 0 && h[2] == n && h[3] == n * 3 && h[4] == n && h[5] == n;
return (core && h[0] >= n * 4 && h[6] >= n) + (core && h[6] >= n * 4 && h[0] >= n);
}
static void run_push(int *h, int len, int s) {
if (h[0] == 0) len += s; /* blank area on the left */
memmove(h + 1, h, 6 * sizeof(int));
h[0] = len;
}
static long penalty(Grid *g) {
int s = g->size;
long r = 0;
for (int pass = 0; pass < 2; pass++) {
for (int a = 0; a < s; a++) {
int color = 0, run = 0, h[7] = { 0 };
for (int b = 0; b < s; b++) {
int c = pass ? AT(g, a, b) : AT(g, b, a);
if (c == color) { run++; if (run == 5) r += 3; else if (run > 5) r++; }
else {
run_push(h, run, s);
if (!color) r += run_finder_count(h) * 40;
color = c;
run = 1;
}
}
/* end of the line */
if (color) { run_push(h, run, s); run = 0; }
run += s;
run_push(h, run, s);
r += run_finder_count(h) * 40;
}
}
for (int y = 0; y + 1 < s; y++) for (int x = 0; x + 1 < s; x++) {
int c = AT(g, x, y);
if (c == AT(g, x + 1, y) && c == AT(g, x, y + 1) && c == AT(g, x + 1, y + 1)) r += 3;
}
long dark = 0;
for (int i = 0; i < s * s; i++) dark += g->m[i];
long total = (long)s * s;
long k = (labs(dark * 20 - total * 10) + total - 1) / total - 1;
r += k * 10;
return r;
}
/* Data bits: mode + length + content. Returns the length in bits (or -1 if it does not fit). */
typedef struct { uint8_t *b; int n, cap; } Bits;
static void bput(Bits *bb, unsigned v, int nb) {
for (int i = nb - 1; i >= 0; i--) {
if (bb->n < bb->cap * 8) { if (v >> i & 1) bb->b[bb->n >> 3] |= (uint8_t)(0x80 >> (bb->n & 7)); }
bb->n++;
}
}
static int pick_mode(const uint8_t *d, size_t len) {
int num = 1, al = 1;
for (size_t i = 0; i < len; i++) {
if (d[i] < '0' || d[i] > '9') num = 0;
if (!d[i] || !strchr(ALNUM, d[i])) al = 0;
}
return num ? 1 : al ? 2 : 4;
}
static long seg_bits(int mode, size_t len, int ver) {
long b = 4 + cc_bits(mode, ver);
if (mode == 1) b += (long)(len / 3) * 10 + (len % 3 == 2 ? 7 : len % 3 == 1 ? 4 : 0);
else if (mode == 2) b += (long)(len / 2) * 11 + (len % 2) * 6;
else b += (long)len * 8;
if (len >= (size_t)1 << cc_bits(mode, ver)) return 1L << 30;
return b;
}
int qr_encode_ex(const uint8_t *data, size_t len, int ecc, int mask, int minver, uint8_t *modules, int *size, int *mask_out) {
if (ecc < 0 || ecc > 3 || !modules || !size || (len && !data) || mask > 7) return -1;
gf_init();
int mode = pick_mode(data, len), ver;
for (ver = minver < 1 ? 1 : minver; ver <= 40; ver++) if (seg_bits(mode, len, ver) <= data_codewords(ver, ecc) * 8) break;
if (ver > 40) return -1;
int ndc = data_codewords(ver, ecc), cap = ndc * 8;
uint8_t dc[3706];
memset(dc, 0, sizeof dc);
Bits bb = { dc, 0, ndc };
bput(&bb, (unsigned)mode, 4);
bput(&bb, (unsigned)len, cc_bits(mode, ver));
if (mode == 1) {
for (size_t i = 0; i < len;) {
size_t k = len - i >= 3 ? 3 : len - i;
unsigned v = 0;
for (size_t j = 0; j < k; j++) v = v * 10 + (unsigned)(data[i + j] - '0');
bput(&bb, v, k == 3 ? 10 : k == 2 ? 7 : 4);
i += k;
}
} else if (mode == 2) {
for (size_t i = 0; i < len; i += 2) {
unsigned a = (unsigned)(strchr(ALNUM, data[i]) - ALNUM);
if (i + 1 < len) bput(&bb, a * 45 + (unsigned)(strchr(ALNUM, data[i + 1]) - ALNUM), 11);
else bput(&bb, a, 6);
}
} else for (size_t i = 0; i < len; i++) bput(&bb, data[i], 8);
int term = cap - bb.n < 4 ? cap - bb.n : 4;
bput(&bb, 0, term);
bput(&bb, 0, (8 - bb.n % 8) % 8);
for (int pad = 0xec; bb.n < cap; pad ^= 0xec ^ 0x11) bput(&bb, (unsigned)pad, 8);
/* blocks and correction, interleaved */
int nb = NUM_BLOCKS[ecc][ver], ne = ECC_PER_BLOCK[ecc][ver];
int raw = raw_modules(ver) / 8, nshort = nb - raw % nb, shortlen = raw / nb;
uint8_t gen[30], blocks[81][160];
int blen[81];
rs_gen(ne, gen);
for (int i = 0, k = 0; i < nb; i++) {
int dl = shortlen - ne + (i < nshort ? 0 : 1);
memcpy(blocks[i], dc + k, (size_t)dl);
rs_rem(dc + k, dl, gen, ne, blocks[i] + dl);
blen[i] = dl;
k += dl;
}
uint8_t all[3706];
int na = 0;
for (int i = 0; i < shortlen + 1 - ne; i++) for (int b = 0; b < nb; b++) if (i < blen[b]) all[na++] = blocks[b][i];
for (int i = 0; i < ne; i++) for (int b = 0; b < nb; b++) all[na++] = blocks[b][blen[b] + i];
int s = ver * 4 + 17;
Grid g = { s, modules, NULL };
uint8_t *fn = calloc((size_t)s * s, 1);
if (!fn) return -1;
g.fn = fn;
memset(modules, 0, (size_t)s * s);
draw_functions(&g, ver);
ZigCtx z = { all, na * 8, 0, NULL };
zigzag(&g, zig_put, &z);
int best = mask;
if (best < 0) {
long bp = -1;
for (int k = 0; k < 8; k++) {
apply_mask(&g, k);
draw_format(&g, format_bits(ecc, k));
long p = penalty(&g);
if (bp < 0 || p < bp) { bp = p; best = k; }
apply_mask(&g, k);
}
}
apply_mask(&g, best);
draw_format(&g, format_bits(ecc, best));
free(fn);
*size = s;
if (mask_out) *mask_out = best;
return ver;
}
int qr_encode(const uint8_t *data, size_t len, int ecc, uint8_t *modules, int *size) {
return qr_encode_ex(data, len, ecc, -1, 1, modules, size, NULL);
}
/* ================= decoding: from the grid to the bytes ================= */
static int popc(unsigned v) { int n = 0; while (v) { n += v & 1; v >>= 1; } return n; }
/* format: (ecc, mask) with the smallest Hamming distance (≤ 3) */
static int decode_format(int bits, int *ecc, int *mask) {
int best = 99;
for (int e = 0; e < 4; e++) for (int m = 0; m < 8; m++) {
int d = popc((unsigned)(bits ^ format_bits(e, m)));
if (d < best) { best = d; *ecc = e; *mask = m; }
}
return best <= 3 ? best : -1;
}
static int decode_version(int bits) {
int best = 99, v = -1;
for (int k = 7; k <= 40; k++) { int d = popc((unsigned)(bits ^ version_bits(k))); if (d < best) { best = d; v = k; } }
return best <= 3 ? v : -1;
}
/* Reads the format information from the two copies in grid g (already sampled). */
static int read_format(Grid *g, int *ecc, int *mask) {
int s = g->size, a = 0, b = 0;
for (int i = 0; i <= 5; i++) a |= AT(g, 8, i) << i;
a |= AT(g, 8, 7) << 6 | AT(g, 8, 8) << 7 | AT(g, 7, 8) << 8;
for (int i = 9; i < 15; i++) a |= AT(g, 14 - i, 8) << i;
for (int i = 0; i < 8; i++) b |= AT(g, s - 1 - i, 8) << i;
for (int i = 8; i < 15; i++) b |= AT(g, 8, s - 15 + i) << i;
int e1, m1, e2, m2;
int d1 = decode_format(a, &e1, &m1), d2 = decode_format(b, &e2, &m2);
if (d1 < 0 && d2 < 0) return -1;
if (d2 < 0 || (d1 >= 0 && d1 <= d2)) { *ecc = e1; *mask = m1; } else { *ecc = e2; *mask = m2; }
return 0;
}
static int read_version_bits(Grid *g) {
int s = g->size, a = 0, b = 0;
for (int i = 0; i < 18; i++) { int x = s - 11 + i % 3, y = i / 3; a |= AT(g, x, y) << i; b |= AT(g, y, x) << i; }
int va = decode_version(a), vb = decode_version(b);
return va > 0 ? va : vb;
}
typedef struct { const uint8_t *b; int n, p; } BR;
static int brd(BR *r, int k) {
if (r->p + k > r->n) { r->p = r->n + 1; return -1; }
int v = 0;
for (int i = 0; i < k; i++, r->p++) v = v << 1 | (r->b[r->p >> 3] >> (7 - (r->p & 7)) & 1);
return v;
}
/* Segments → bytes. */
static int parse_segments(const uint8_t *d, int nbytes, int ver, uint8_t *out, size_t cap) {
BR r = { d, nbytes * 8, 0 };
size_t o = 0;
#define PUT(c) do { if (o < cap) out[o] = (uint8_t)(c); o++; } while (0)
for (;;) {
if (r.n - r.p < 4) break;
int mode = brd(&r, 4);
if (mode == 0) break;
if (mode == 7) { /* ECI: skipped */
int f = brd(&r, 8);
if (f < 0) return -1;
if ((f & 0xc0) == 0x80) brd(&r, 8);
else if ((f & 0xe0) == 0xc0) brd(&r, 16);
else if (f & 0x80) return -1;
continue;
}
if (mode == 3) { brd(&r, 16); continue; } /* structured append */
if (mode == 5) continue; /* FNC1 first position */
if (mode == 9) { brd(&r, 8); continue; }
int g = ver <= 9 ? 0 : ver <= 26 ? 1 : 2;
if (mode == 1) {
int n = brd(&r, (int[]){ 10, 12, 14 }[g]);
if (n < 0) return -1;
for (; n >= 3; n -= 3) { int v = brd(&r, 10); if (v < 0 || v > 999) return -1; PUT('0' + v / 100); PUT('0' + v / 10 % 10); PUT('0' + v % 10); }
if (n == 2) { int v = brd(&r, 7); if (v < 0 || v > 99) return -1; PUT('0' + v / 10); PUT('0' + v % 10); }
else if (n == 1) { int v = brd(&r, 4); if (v < 0 || v > 9) return -1; PUT('0' + v); }
} else if (mode == 2) {
int n = brd(&r, (int[]){ 9, 11, 13 }[g]);
if (n < 0) return -1;
for (; n >= 2; n -= 2) { int v = brd(&r, 11); if (v < 0 || v >= 45 * 45) return -1; PUT(ALNUM[v / 45]); PUT(ALNUM[v % 45]); }
if (n == 1) { int v = brd(&r, 6); if (v < 0 || v >= 45) return -1; PUT(ALNUM[v]); }
} else if (mode == 4) {
int n = brd(&r, (int[]){ 8, 16, 16 }[g]);
if (n < 0) return -1;
for (int i = 0; i < n; i++) { int v = brd(&r, 8); if (v < 0) return -1; PUT(v); }
} else if (mode == 8) { /* kanji → Shift JIS */
int n = brd(&r, (int[]){ 8, 10, 12 }[g]);
if (n < 0) return -1;
for (int i = 0; i < n; i++) {
int v = brd(&r, 13);
if (v < 0) return -1;
int c = (v / 0xc0) << 8 | (v % 0xc0);
c += c < 0x1f00 ? 0x8140 : 0xc140;
PUT(c >> 8); PUT(c & 255);
}
} else return -1;
if (r.p > r.n) return -1;
}
#undef PUT
if (o >= cap) return -1;
out[o] = 0;
return (int)o;
}
/* Sampled grid (modules of version ver) → bytes. */
static int decode_grid(uint8_t *mods, int ver, uint8_t *out, size_t cap) {
gf_init();
int s = ver * 4 + 17;
Grid g = { s, mods, NULL };
int ecc, mask;
if (read_format(&g, &ecc, &mask)) return -1;
uint8_t *fn = calloc((size_t)s * s, 1), *save = malloc((size_t)s * s);
if (!fn || !save) { free(fn); free(save); return -1; }
memcpy(save, mods, (size_t)s * s);
g.fn = fn;
draw_functions(&g, ver); /* only to mark fn; the modules are restored */
memcpy(mods, save, (size_t)s * s);
free(save);
apply_mask(&g, mask);
int raw = raw_modules(ver) / 8;
uint8_t all[3706];
memset(all, 0, sizeof all);
ZigCtx z = { NULL, raw * 8, 0, all };
zigzag(&g, zig_get, &z);
apply_mask(&g, mask);
free(fn);
int nb = NUM_BLOCKS[ecc][ver], ne = ECC_PER_BLOCK[ecc][ver];
int nshort = nb - raw % nb, shortlen = raw / nb;
uint8_t blocks[81][160];
int blen[81], k = 0;
for (int b = 0; b < nb; b++) blen[b] = shortlen - ne + (b < nshort ? 0 : 1);
for (int i = 0; i < shortlen + 1 - ne; i++) for (int b = 0; b < nb; b++) if (i < blen[b]) blocks[b][i] = all[k++];
for (int i = 0; i < ne; i++) for (int b = 0; b < nb; b++) blocks[b][blen[b] + i] = all[k++];
uint8_t data[3706];
int nd = 0;
for (int b = 0; b < nb; b++) {
if (rs_correct(blocks[b], blen[b] + ne, ne)) return -1;
memcpy(data + nd, blocks[b], (size_t)blen[b]);
nd += blen[b];
}
return parse_segments(data, nd, ver, out, cap);
}
/* ================= decoding: from the image to the grid ================= */
typedef struct { double x, y, ms; int count; } Cand;
typedef struct { const uint8_t *bin; int w, h; Cand c[64]; int nc; } Img;
#define PX(im, x, y) ((im)->bin[(y) * (im)->w + (x)])
static int ratio_ok(const int *st) {
int total = 0;
for (int i = 0; i < 5; i++) { if (!st[i]) return 0; total += st[i]; }
if (total < 7) return 0;
double m = total / 7.0, v = m * 0.5;
return fabs(m - st[0]) < v && fabs(m - st[1]) < v && fabs(3 * m - st[2]) < 3 * v && fabs(m - st[3]) < v && fabs(m - st[4]) < v;
}
/* Counts the runs in one direction from (x, y), which must be dark. */
static int cross(Img *im, double fx, double fy, int dx, int dy, int maxc, double *center, double *ms) {
int x0 = (int)fx, y0 = (int)fy;
if (x0 < 0 || y0 < 0 || x0 >= im->w || y0 >= im->h || !PX(im, x0, y0)) return 0;
int st[5] = { 0 };
int x = x0, y = y0;
/* backwards: center (dark), white, dark */
while (x >= 0 && y >= 0 && x < im->w && y < im->h && PX(im, x, y)) { st[2]++; x -= dx; y -= dy; }
while (x >= 0 && y >= 0 && x < im->w && y < im->h && !PX(im, x, y) && st[1] <= maxc) { st[1]++; x -= dx; y -= dy; }
while (x >= 0 && y >= 0 && x < im->w && y < im->h && PX(im, x, y) && st[0] <= maxc) { st[0]++; x -= dx; y -= dy; }
x = x0 + dx; y = y0 + dy;
while (x >= 0 && y >= 0 && x < im->w && y < im->h && PX(im, x, y)) { st[2]++; x += dx; y += dy; }
int ex;
while (x >= 0 && y >= 0 && x < im->w && y < im->h && !PX(im, x, y) && st[3] <= maxc) { st[3]++; x += dx; y += dy; }
while (x >= 0 && y >= 0 && x < im->w && y < im->h && PX(im, x, y) && st[4] <= maxc) { st[4]++; x += dx; y += dy; }
ex = dx ? x : y; /* end (exclusive) on the coordinate that moves */
if (!ratio_ok(st)) return 0;
*center = ex - st[4] - st[3] - st[2] / 2.0;
*ms = (st[0] + st[1] + st[2] + st[3] + st[4]) / 7.0;
return st[0] + st[1] + st[2] + st[3] + st[4];
}
static void add_cand(Img *im, double x, double y, double ms) {
for (int i = 0; i < im->nc; i++) {
Cand *c = &im->c[i];
if (fabs(c->x - x) <= c->ms * 2 && fabs(c->y - y) <= c->ms * 2 && fabs(c->ms - ms) <= c->ms * 0.5 + 1) {
int n = c->count;
c->x = (c->x * n + x) / (n + 1);
c->y = (c->y * n + y) / (n + 1);
c->ms = (c->ms * n + ms) / (n + 1);
c->count++;
return;
}
}
if (im->nc < 64) im->c[im->nc++] = (Cand){ x, y, ms, 1 };
}
static void found(Img *im, const int *st, int y, int xend) {
double cx = xend - st[4] - st[3] - st[2] / 2.0;
int total = st[0] + st[1] + st[2] + st[3] + st[4];
double cy, msv, cx2, msh;
if (!cross(im, cx, y, 0, 1, st[2], &cy, &msv)) return;
if (!cross(im, cx, cy, 1, 0, st[2], &cx2, &msh)) return;
double ms = (msv + msh) / 2;
if (msv * 7 > total * 2 || msv * 7 * 2 < total) return;
/* diagonal (discards stripes) */
double dc, dms;
if (!cross(im, cx2, cy, 1, 1, st[2] * 2, &dc, &dms)) return;
add_cand(im, cx2, cy, ms);
}
static void find_finders(Img *im) {
im->nc = 0;
for (int y = 0; y < im->h; y++) {
int st[5] = { 0 }, cur = 0;
for (int x = 0; x < im->w; x++) {
if (PX(im, x, y)) {
if (cur & 1) cur++;
st[cur]++;
} else {
if (cur == 0 && st[0] == 0) continue;
if (!(cur & 1)) {
if (cur == 4) {
if (ratio_ok(st)) { found(im, st, y, x); memset(st, 0, sizeof st); cur = 0; continue; }
st[0] = st[2]; st[1] = st[3]; st[2] = st[4]; st[3] = 1; st[4] = 0; cur = 3;
continue;
}
cur++;
st[cur]++;
} else st[cur]++;
}
}
if (cur == 4 && ratio_ok(st)) found(im, st, y, im->w);
}
}
static double dist(const Cand *a, const Cand *b) { return hypot(a->x - b->x, a->y - b->y); }
/* Homography: from (u, v) in modules to (x, y) in the image, from 4 points (8x8 system). */
typedef struct { double a[9]; } Hom;
static int hom_solve(const double *u, const double *v, const double *x, const double *y, Hom *H) {
double M[8][9];
for (int i = 0; i < 4; i++) {
double r1[9] = { u[i], v[i], 1, 0, 0, 0, -u[i] * x[i], -v[i] * x[i], x[i] };
double r2[9] = { 0, 0, 0, u[i], v[i], 1, -u[i] * y[i], -v[i] * y[i], y[i] };
memcpy(M[2 * i], r1, sizeof r1);
memcpy(M[2 * i + 1], r2, sizeof r2);
}
for (int c = 0; c < 8; c++) {
int p = c;
for (int r = c + 1; r < 8; r++) if (fabs(M[r][c]) > fabs(M[p][c])) p = r;
if (fabs(M[p][c]) < 1e-12) return -1;
if (p != c) for (int k = 0; k < 9; k++) { double t = M[c][k]; M[c][k] = M[p][k]; M[p][k] = t; }
for (int r = 0; r < 8; r++) {
if (r == c) continue;
double f = M[r][c] / M[c][c];
for (int k = c; k < 9; k++) M[r][k] -= f * M[c][k];
}
}
for (int i = 0; i < 8; i++) H->a[i] = M[i][8] / M[i][i];
H->a[8] = 1;
return 0;
}
static void hom_map(const Hom *H, double u, double v, double *x, double *y) {
double w = H->a[6] * u + H->a[7] * v + H->a[8];
*x = (H->a[0] * u + H->a[1] * v + H->a[2]) / w;
*y = (H->a[3] * u + H->a[4] * v + H->a[5]) / w;
}
static int sample(Img *im, double x, double y) {
int ix = (int)floor(x), iy = (int)floor(y);
if (ix < 0 || iy < 0 || ix >= im->w || iy >= im->h) return 0;
return PX(im, ix, iy);
}
/* Alignment pattern near (ex, ey): a dark module surrounded by a light ring and a dark one. */
static int find_align(Img *im, double ex, double ey, double ms, double *ax, double *ay) {
int r = (int)(ms * 4 + 2), best = 0;
double bd = 1e18;
for (int y = (int)ey - r; y <= (int)ey + r; y++) {
if (y < 0 || y >= im->h) continue;
for (int x = (int)ex - r; x <= (int)ex + r; x++) {
if (x < 0 || x >= im->w || !PX(im, x, y)) continue;
/* horizontal and vertical runs: dark (~1), light (~1) on each side, dark outside */
int ok = 1;
double c[2];
for (int d = 0; d < 2 && ok; d++) {
int dx = d == 0, dy = d == 1, n0 = 0, l1 = 0, r1 = 0, xx, yy;
int lim = (int)(ms * 2.5) + 1;
for (xx = x, yy = y; xx >= 0 && yy >= 0 && PX(im, xx, yy) && n0 < lim; xx -= dx, yy -= dy) n0++;
int left = d ? yy : xx;
for (; xx >= 0 && yy >= 0 && !PX(im, xx, yy) && l1 < lim; xx -= dx, yy -= dy) l1++;
if (xx < 0 || yy < 0 || !PX(im, xx, yy)) { ok = 0; break; }
for (xx = x + dx, yy = y + dy; xx < im->w && yy < im->h && PX(im, xx, yy) && n0 < lim * 2; xx += dx, yy += dy) n0++;
int right = d ? yy : xx;
for (; xx < im->w && yy < im->h && !PX(im, xx, yy) && r1 < lim; xx += dx, yy += dy) r1++;
if (xx >= im->w || yy >= im->h || !PX(im, xx, yy)) { ok = 0; break; }
if (fabs(n0 - ms) > ms * 0.7 + 1 || fabs(l1 - ms) > ms * 0.7 + 1 || fabs(r1 - ms) > ms * 0.7 + 1) ok = 0;
c[d] = (left + 1 + right) / 2.0;
}
if (!ok) continue;
double dd = (c[0] - ex) * (c[0] - ex) + (c[1] - ey) * (c[1] - ey);
if (dd < bd) { bd = dd; *ax = c[0]; *ay = c[1]; best = 1; }
}
}
return best;
}
/* Counts the runs of the timing pattern between p0 and p1 (in pixels). */
static int timing_runs(Img *im, double x0, double y0, double x1, double y1, double ms) {
double len = hypot(x1 - x0, y1 - y0);
int steps = (int)(len / (ms / 4)) + 1, runs = 0, prev = -1;
for (int i = 0; i <= steps; i++) {
double t = (double)i / steps;
int v = sample(im, x0 + (x1 - x0) * t, y0 + (y1 - y0) * t);
if (v != prev) { runs++; prev = v; }
}
return runs;
}
static int try_grid(Img *im, const Cand *B, const Cand *A, const Cand *C, int ver, int use_align, uint8_t *out, size_t cap) {
int s = ver * 4 + 17;
double ms = (A->ms + B->ms + C->ms) / 3;
double u[4] = { 3.5, s - 3.5, 3.5, 0 }, v[4] = { 3.5, 3.5, s - 3.5, 0 };
double x[4] = { B->x, A->x, C->x, 0 }, y[4] = { B->y, A->y, C->y, 0 };
/* fourth point: affine corner (or the alignment pattern) */
double k = (s - 6.5 - 3.5) / (s - 7.0);
u[3] = s - 6.5; v[3] = s - 6.5;
x[3] = B->x + (A->x - B->x) * k + (C->x - B->x) * k;
y[3] = B->y + (A->y - B->y) * k + (C->y - B->y) * k;
if (ver >= 2 && use_align) {
double ax = 0, ay = 0;
if (!find_align(im, x[3], y[3], ms, &ax, &ay)) return -1;
x[3] = ax; y[3] = ay;
}
Hom H;
if (hom_solve(u, v, x, y, &H)) return -1;
uint8_t *mods = malloc((size_t)s * s);
if (!mods) return -1;
for (int r = 0; r < s; r++) for (int c = 0; c < s; c++) {
double px, py;
hom_map(&H, c + 0.5, r + 0.5, &px, &py);
mods[r * s + c] = (uint8_t)sample(im, px, py);
}
int n = -1;
if (ver >= 7) {
Grid g = { s, mods, NULL };
int vv = read_version_bits(&g);
if (vv > 0 && vv != ver) { free(mods); return -2 - vv; } /* different version: try that one */
}
n = decode_grid(mods, ver, out, cap);
free(mods);
return n;
}
static int try_triplet(Img *im, Cand B, Cand A, Cand C, uint8_t *out, size_t cap) {
double ms = (A.ms + B.ms + C.ms) / 3;
double dab = dist(&B, &A), dbc = dist(&B, &C);
int est = (int)lround((dab + dbc) / 2 / ms) + 7;
/* timing pattern: row 6 (from B to A) and column 6 (from B to C) */
double ux = (C.x - B.x) / dbc, uy = (C.y - B.y) / dbc, vx = (A.x - B.x) / dab, vy = (A.y - B.y) / dab;
int t1 = timing_runs(im, B.x + ux * 3 * ms, B.y + uy * 3 * ms, A.x + ux * 3 * ms, A.y + uy * 3 * ms, ms) + 12;
int t2 = timing_runs(im, B.x + vx * 3 * ms, B.y + vy * 3 * ms, C.x + vx * 3 * ms, C.y + vy * 3 * ms, ms) + 12;
int tried[16], nt = 0;
int cands[8] = { t1, t2, est, est + 1, est - 1, est + 2, est - 2, est + 4 };
for (int i = 0; i < 8; i++) {
int d = cands[i];
if (d % 4 != 1) continue;
int ver = (d - 17) / 4;
if (ver < 1 || ver > 40) continue;
for (int pass = 0; pass < 3; pass++) {
int seen = 0;
for (int j = 0; j < nt; j++) if (tried[j] == ver) seen = 1;
if (seen || nt >= 16) break;
tried[nt++] = ver;
int n = try_grid(im, &B, &A, &C, ver, 1, out, cap);
if (n == -1 && ver >= 2) n = try_grid(im, &B, &A, &C, ver, 0, out, cap);
if (n >= 0) return n;
if (n <= -9) { ver = -2 - n; continue; } /* the version information said otherwise */
break;
}
}
return -1;
}
static int decode_bin(Img *im, uint8_t *out, size_t cap) {
find_finders(im);
if (im->nc < 3) return -1;
/* most confirmed first */
for (int i = 0; i < im->nc; i++) for (int j = i + 1; j < im->nc; j++)
if (im->c[j].count > im->c[i].count) { Cand t = im->c[i]; im->c[i] = im->c[j]; im->c[j] = t; }
int n = im->nc < 12 ? im->nc : 12;
typedef struct { double score; int a, b, c; } Tri;
Tri tri[220];
int nt = 0;
for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) for (int k = j + 1; k < n; k++) {
const Cand *p[3] = { &im->c[i], &im->c[j], &im->c[k] };
double mn = fmin(p[0]->ms, fmin(p[1]->ms, p[2]->ms)), mx = fmax(p[0]->ms, fmax(p[1]->ms, p[2]->ms));
if (mx > mn * 1.5) continue;
double d01 = dist(p[0], p[1]), d02 = dist(p[0], p[2]), d12 = dist(p[1], p[2]);
int b; double hyp, l1, l2;
if (d12 >= d01 && d12 >= d02) { b = 0; hyp = d12; l1 = d01; l2 = d02; }
else if (d02 >= d01) { b = 1; hyp = d02; l1 = d01; l2 = d12; }
else { b = 2; hyp = d01; l1 = d02; l2 = d12; }
double ms = (mn + mx) / 2;
if (l1 < ms * 12 || l2 < ms * 12) continue;
double legs = fabs(l1 - l2) / fmax(l1, l2), right = fabs(hyp * hyp - l1 * l1 - l2 * l2) / (hyp * hyp);
if (legs > 0.25 || right > 0.25) continue;
int idx[3] = { i, j, k };
int a = idx[(b + 1) % 3], c = idx[(b + 2) % 3];
tri[nt++] = (Tri){ legs + right + (mx - mn) / mx, idx[b], a, c };
if (nt == 220) goto enough;
}
enough:
for (int i = 0; i < nt; i++) for (int j = i + 1; j < nt; j++) if (tri[j].score < tri[i].score) { Tri t = tri[i]; tri[i] = tri[j]; tri[j] = t; }
for (int t = 0; t < nt && t < 6; t++) {
Cand B = im->c[tri[t].a], A = im->c[tri[t].b], C = im->c[tri[t].c];
/* orientation: with y pointing down, (A-B) x (C-B) > 0 */
double cr = (A.x - B.x) * (C.y - B.y) - (A.y - B.y) * (C.x - B.x);
if (cr < 0) { Cand x = A; A = C; C = x; }
int r = try_triplet(im, B, A, C, out, cap);
if (r >= 0) return r;
}
return -1;
}
int qr_decode(const uint32_t *argb, int w, int h, uint8_t *out, size_t outcap) {
if (!argb || w < 21 || h < 21 || w > 16384 || h > 16384 || !out || !outcap) return -1;
size_t n = (size_t)w * h;
uint8_t *lum = malloc(n), *bin = malloc(n);
uint32_t *integ = malloc(sizeof(uint32_t) * (size_t)(w + 1) * (h + 1));
if (!lum || !bin || !integ) { free(lum); free(bin); free(integ); return -1; }
long hist[256] = { 0 };
for (size_t i = 0; i < n; i++) {
uint32_t p = argb[i];
unsigned a = p >> 24, r = p >> 16 & 255, g = p >> 8 & 255, b = p & 255;
unsigned l = (r * 77 + g * 150 + b * 29) >> 8;
l = (l * a + 255 * (255 - a)) / 255; /* over a white background */
lum[i] = (uint8_t)l;
hist[l]++;
}
/* Otsu */
double sum = 0, sumb = 0, wb = 0, best = -1;
int th = 128;
for (int i = 0; i < 256; i++) sum += (double)i * hist[i];
for (int i = 0; i < 256; i++) {
wb += hist[i];
if (!wb) continue;
double wf = (double)n - wb;
if (wf <= 0) break;
sumb += (double)i * hist[i];
double mb = sumb / wb, mf = (sum - sumb) / wf, v = wb * wf * (mb - mf) * (mb - mf);
if (v > best) { best = v; th = i; }
}
/* integral image for the local threshold */
for (int x = 0; x <= w; x++) integ[x] = 0;
for (int y = 0; y < h; y++) {
uint32_t row = 0;
integ[(size_t)(y + 1) * (w + 1)] = 0;
for (int x = 0; x < w; x++) { row += lum[(size_t)y * w + x]; integ[(size_t)(y + 1) * (w + 1) + x + 1] = integ[(size_t)y * (w + 1) + x + 1] + row; }
}
int win = (w > h ? w : h) / 8;
if (win < 16) win = 16;
int res = -1;
Img *im = malloc(sizeof *im);
if (!im) goto done;
im->bin = bin; im->w = w; im->h = h;
for (int attempt = 0; attempt < 4 && res < 0; attempt++) {
int invert = attempt & 1, local = attempt >= 2;
for (int y = 0; y < h; y++) {
int y0 = y - win / 2 < 0 ? 0 : y - win / 2, y1 = y + win / 2 >= h ? h - 1 : y + win / 2;
for (int x = 0; x < w; x++) {
size_t i = (size_t)y * w + x;
int l = lum[i], dark;
if (!local) dark = l <= th;
else {
int x0 = x - win / 2 < 0 ? 0 : x - win / 2, x1 = x + win / 2 >= w ? w - 1 : x + win / 2;
uint32_t s = integ[(size_t)(y1 + 1) * (w + 1) + x1 + 1] - integ[(size_t)y0 * (w + 1) + x1 + 1]
- integ[(size_t)(y1 + 1) * (w + 1) + x0] + integ[(size_t)y0 * (w + 1) + x0];
long cnt = (long)(x1 - x0 + 1) * (y1 - y0 + 1);
dark = invert ? (long)l * cnt * 100 > (long)s * 115 : (long)l * cnt * 100 < (long)s * 85;
}
if (!local && invert) dark = !dark;
bin[i] = (uint8_t)dark;
}
}
res = decode_bin(im, out, outcap);
}
done:
free(im);
free(lum);
free(bin);
free(integ);
return res;
}