Open CKey Make a CKey
Menu
Viewing is open to everyone. Downloading and starring need a GitHub sign-in. Sign in with GitHub

core_internal.inc

v0.1.0-build.85 Latest Commit ede38f5

Size
89 KB
Lines
1,595
Language
cpp
SHA-256
431dad143d14…
View on GitHub

Sign in with GitHub to download. Each download is recorded with your GitHub username.

1// Shared internal definitions (RS, CRC, layouts, sampling, style checks).
2// Included first by every core translation unit.
3#include "ckey/ckey.h"
4
5#include <algorithm>
6#include <array>
7#include <cmath>
8#include <cstdio>
9#include <cstring>
10#include <functional>
11#include <initializer_list>
12#include <limits>
13#include <memory>
14#include <mutex>
15#include <numeric>
16#include <iomanip>
17#include <sstream>
18#include <string>
19#include <utility>
20#include <vector>
21
22namespace {
23constexpr size_t kDataBytes = 26;
24constexpr size_t kParityBytes = 51;
25constexpr size_t kCodewordBytes = kDataBytes + kParityBytes;
26constexpr size_t kBits = kCodewordBytes * 8;
27constexpr size_t kTextDataBytes = 210;
28constexpr size_t kTextParityBytes = 45;
29constexpr size_t kTextCodewordBytes = kTextDataBytes + kTextParityBytes;
30static_assert(kTextCodewordBytes == CKEY_TEXT_CODEWORD_BYTES);
31constexpr size_t kExtendedBlocks = CKEY_EXTENDED_BLOCK_COUNT;
32constexpr size_t kExtendedDataBytes = CKEY_EXTENDED_DATA_BYTES_PER_BLOCK;
33constexpr size_t kExtendedParityBytes = CKEY_EXTENDED_PARITY_BYTES_PER_BLOCK;
34constexpr size_t kExtendedBlockBytes = CKEY_EXTENDED_CODEWORD_BYTES_PER_BLOCK;
35constexpr size_t kExtendedCodewordBytes = CKEY_EXTENDED_CODEWORD_BYTES;
36constexpr size_t kExtendedBits = kExtendedCodewordBytes * 8;
37constexpr int kExtendedSide = 116;
38constexpr std::array<size_t, CKEY_EXTENDED_TIER_COUNT> kExtendedTierCapacities = {256, 384, 512, 768, 1024, 1536, 2048};
39static_assert(kExtendedBlocks * kExtendedBlockBytes == kExtendedCodewordBytes);
40constexpr int kSide = 29;
41constexpr double kCenter = 14.5;
42constexpr double kTau = 6.283185307179586476925286766559;
43
44struct Gf {
45 std::array<uint8_t, 512> exp{};
46 std::array<uint8_t, 256> log{};
47 Gf() {
48 unsigned x = 1;
49 for (int i = 0; i < 255; ++i) {
50 exp[i] = static_cast<uint8_t>(x); log[x] = static_cast<uint8_t>(i);
51 x <<= 1; if (x & 0x100) x ^= 0x11d;
52 }
53 for (int i = 255; i < 512; ++i) exp[i] = exp[i - 255];
54 }
55 uint8_t mul(uint8_t a, uint8_t b) const { return (!a || !b) ? 0 : exp[log[a] + log[b]]; }
56 uint8_t inv(uint8_t a) const { return a ? exp[255 - log[a]] : 0; }
57};
58const Gf gf{};
59
60std::array<uint8_t, kParityBytes + 1> rs_generator() {
61 std::array<uint8_t, kParityBytes + 1> p{}; p[0] = 1;
62 size_t len = 1;
63 for (size_t i = 0; i < kParityBytes; ++i) {
64 std::array<uint8_t, kParityBytes + 1> q{};
65 const uint8_t root = gf.exp[i];
66 for (size_t j = 0; j < len; ++j) { q[j] ^= p[j]; q[j + 1] ^= gf.mul(p[j], root); }
67 p = q; ++len;
68 }
69 return p;
70}
71
72uint8_t eval_low(const std::array<uint8_t, kParityBytes + 1> &p, size_t degree, uint8_t x) {
73 uint8_t y = p[degree];
74 while (degree) { --degree; y = gf.mul(y, x) ^ p[degree]; }
75 return y;
76}
77
78std::array<uint8_t, kParityBytes> syndromes(const std::array<uint8_t, kCodewordBytes> &cw) {
79 std::array<uint8_t, kParityBytes> s{};
80 for (size_t j = 0; j < kParityBytes; ++j) {
81 const uint8_t x = gf.exp[j];
82 uint8_t y = 0;
83 for (uint8_t b : cw) y = gf.mul(y, x) ^ b;
84 s[j] = y;
85 }
86 return s;
87}
88
89bool rs_correct(std::array<uint8_t, kCodewordBytes> &cw, uint32_t &corrected) {
90 const auto s = syndromes(cw);
91 if (std::all_of(s.begin(), s.end(), [](uint8_t v) { return v == 0; })) { corrected = 0; return true; }
92
93 // Berlekamp–Massey over the 51 syndromes. Locator coefficients are
94 // stored low-degree first: Lambda(z)=prod(1-X_i*z).
95 std::array<uint8_t, kParityBytes + 1> lambda{}, previous{};
96 lambda[0] = previous[0] = 1;
97 size_t degree = 0, shift = 1;
98 uint8_t last_discrepancy = 1;
99 for (size_t n = 0; n < kParityBytes; ++n) {
100 uint8_t discrepancy = s[n];
101 for (size_t i = 1; i <= degree; ++i) discrepancy ^= gf.mul(lambda[i], s[n - i]);
102 if (discrepancy == 0) { ++shift; continue; }
103 const auto saved = lambda;
104 const uint8_t factor = gf.mul(discrepancy, gf.inv(last_discrepancy));
105 for (size_t i = 0; i + shift <= kParityBytes; ++i) lambda[i + shift] ^= gf.mul(factor, previous[i]);
106 if (2 * degree <= n) {
107 degree = n + 1 - degree;
108 previous = saved;
109 last_discrepancy = discrepancy;
110 shift = 1;
111 } else {
112 ++shift;
113 }
114 }
115 if (degree == 0 || degree > kParityBytes / 2) return false;
116
117 std::array<size_t, kParityBytes / 2> positions{};
118 std::array<uint8_t, kParityBytes / 2> locations{};
119 size_t found = 0;
120 for (size_t pos = 0; pos < cw.size(); ++pos) {
121 const size_t exponent = cw.size() - 1 - pos;
122 const uint8_t x = gf.exp[exponent];
123 const uint8_t inverse_x = gf.inv(x);
124 if (eval_low(lambda, degree, inverse_x) == 0) {
125 if (found >= positions.size()) return false;
126 positions[found] = pos; locations[found] = x; ++found;
127 }
128 }
129 if (found != degree) return false;
130
131 // Solve the first degree syndrome equations for error magnitudes using a
132 // small GF(256) Vandermonde system. This avoids a second fragile formula
133 // convention for Forney magnitudes and is small for a 77-byte codeword.
134 uint8_t matrix[kParityBytes / 2][kParityBytes / 2 + 1]{};
135 for (size_t row = 0; row < degree; ++row) {
136 for (size_t col = 0; col < degree; ++col) {
137 uint8_t v = 1;
138 for (size_t p = 0; p < row; ++p) v = gf.mul(v, locations[col]);
139 matrix[row][col] = v;
140 }
141 matrix[row][degree] = s[row];
142 }
143 for (size_t col = 0; col < degree; ++col) {
144 size_t pivot = col;
145 while (pivot < degree && matrix[pivot][col] == 0) ++pivot;
146 if (pivot == degree) return false;
147 if (pivot != col) for (size_t j = col; j <= degree; ++j) std::swap(matrix[pivot][j], matrix[col][j]);
148 const uint8_t inv = gf.inv(matrix[col][col]);
149 for (size_t j = col; j <= degree; ++j) matrix[col][j] = gf.mul(matrix[col][j], inv);
150 for (size_t row = 0; row < degree; ++row) if (row != col) {
151 const uint8_t factor = matrix[row][col];
152 for (size_t j = col; j <= degree; ++j) matrix[row][j] ^= gf.mul(factor, matrix[col][j]);
153 }
154 }
155 for (size_t i = 0; i < degree; ++i) cw[positions[i]] ^= matrix[i][degree];
156 const auto check = syndromes(cw);
157 if (!std::all_of(check.begin(), check.end(), [](uint8_t v) { return v == 0; })) return false;
158 corrected = static_cast<uint32_t>(degree);
159 return true;
160}
161
162std::vector<uint8_t> rs_generator_generic(size_t parity) {
163 std::vector<uint8_t> polynomial(1, 1);
164 for (size_t root = 0; root < parity; ++root) {
165 std::vector<uint8_t> next(polynomial.size() + 1, 0);
166 for (size_t i = 0; i < polynomial.size(); ++i) {
167 next[i] ^= polynomial[i];
168 next[i + 1] ^= gf.mul(polynomial[i], gf.exp[root]);
169 }
170 polynomial = std::move(next);
171 }
172 return polynomial;
173}
174
175void rs_encode_generic(std::vector<uint8_t> &codeword, size_t data_bytes, size_t parity_bytes) {
176 const auto generator = rs_generator_generic(parity_bytes);
177 std::vector<uint8_t> work = codeword;
178 for (size_t i = 0; i < data_bytes; ++i) {
179 const uint8_t feedback = work[i];
180 if (!feedback) continue;
181 for (size_t j = 1; j <= parity_bytes; ++j) work[i + j] ^= gf.mul(generator[j], feedback);
182 }
183 std::copy(work.begin() + static_cast<std::ptrdiff_t>(data_bytes), work.end(),
184 codeword.begin() + static_cast<std::ptrdiff_t>(data_bytes));
185}
186
187bool rs_correct_generic(std::vector<uint8_t> &cw, size_t parity_bytes, uint32_t &corrected) {
188 if (cw.empty() || parity_bytes == 0 || parity_bytes >= cw.size() || parity_bytes > 254) return false;
189 std::vector<uint8_t> syndromes(parity_bytes, 0);
190 for (size_t j = 0; j < parity_bytes; ++j) for (uint8_t b : cw) syndromes[j] = gf.mul(syndromes[j], gf.exp[j]) ^ b;
191 if (std::all_of(syndromes.begin(), syndromes.end(), [](uint8_t v) { return v == 0; })) { corrected = 0; return true; }
192
193 std::vector<uint8_t> lambda(parity_bytes + 1, 0), previous(parity_bytes + 1, 0);
194 lambda[0] = previous[0] = 1;
195 size_t degree = 0, shift = 1;
196 uint8_t last_discrepancy = 1;
197 for (size_t n = 0; n < parity_bytes; ++n) {
198 uint8_t discrepancy = syndromes[n];
199 for (size_t i = 1; i <= degree; ++i) discrepancy ^= gf.mul(lambda[i], syndromes[n - i]);
200 if (!discrepancy) { ++shift; continue; }
201 const auto saved = lambda;
202 const uint8_t factor = gf.mul(discrepancy, gf.inv(last_discrepancy));
203 for (size_t i = 0; i + shift <= parity_bytes; ++i) lambda[i + shift] ^= gf.mul(factor, previous[i]);
204 if (2 * degree <= n) { degree = n + 1 - degree; previous = saved; last_discrepancy = discrepancy; shift = 1; }
205 else ++shift;
206 }
207 if (degree == 0 || degree > parity_bytes / 2) return false;
208 std::vector<size_t> positions; std::vector<uint8_t> locations;
209 for (size_t pos = 0; pos < cw.size(); ++pos) {
210 const uint8_t location = gf.exp[cw.size() - 1 - pos];
211 uint8_t value = lambda[degree];
212 for (size_t i = degree; i-- > 0;) value = gf.mul(value, gf.inv(location)) ^ lambda[i];
213 if (!value) { positions.push_back(pos); locations.push_back(location); }
214 }
215 if (positions.size() != degree) return false;
216 std::vector<uint8_t> matrix(degree * (degree + 1), 0);
217 const auto at = [&](size_t row, size_t col) -> uint8_t & { return matrix[row * (degree + 1) + col]; };
218 for (size_t row = 0; row < degree; ++row) {
219 for (size_t col = 0; col < degree; ++col) {
220 uint8_t value = 1;
221 for (size_t power = 0; power < row; ++power) value = gf.mul(value, locations[col]);
222 at(row, col) = value;
223 }
224 at(row, degree) = syndromes[row];
225 }
226 for (size_t col = 0; col < degree; ++col) {
227 size_t pivot = col; while (pivot < degree && at(pivot, col) == 0) ++pivot;
228 if (pivot == degree) return false;
229 if (pivot != col) for (size_t j = col; j <= degree; ++j) std::swap(at(pivot, j), at(col, j));
230 const uint8_t inverse = gf.inv(at(col, col));
231 for (size_t j = col; j <= degree; ++j) at(col, j) = gf.mul(at(col, j), inverse);
232 for (size_t row = 0; row < degree; ++row) if (row != col) {
233 const uint8_t factor = at(row, col);
234 for (size_t j = col; j <= degree; ++j) at(row, j) ^= gf.mul(factor, at(col, j));
235 }
236 }
237 for (size_t i = 0; i < degree; ++i) cw[positions[i]] ^= at(i, degree);
238 for (size_t j = 0; j < parity_bytes; ++j) {
239 uint8_t syndrome = 0; for (uint8_t b : cw) syndrome = gf.mul(syndrome, gf.exp[j]) ^ b;
240 if (syndrome) return false;
241 }
242 corrected = static_cast<uint32_t>(degree);
243 return true;
244}
245
246uint32_t crc32c(const uint8_t *data, size_t len) {
247 uint32_t crc = 0xffffffffu;
248 for (size_t i = 0; i < len; ++i) {
249 crc ^= data[i];
250 for (int b = 0; b < 8; ++b) crc = (crc >> 1) ^ (0x82f63b78u & (0u - (crc & 1u)));
251 }
252 return ~crc;
253}
254
255// Normative SplitMix32 fill for unused frame bytes. This is visual decorrelation,
256// not encryption or error correction; the complete padded frame remains under RS.
257uint8_t padding_byte(uint32_t &state) {
258 state += 0x9e3779b9u;
259 uint32_t value = state;
260 value = (value ^ (value >> 16)) * 0x85ebca6bu;
261 value = (value ^ (value >> 13)) * 0xc2b2ae35u;
262 value ^= value >> 16;
263 return static_cast<uint8_t>(value);
264}
265
266void fill_padding(uint8_t *frame, size_t begin, size_t end, size_t seed_length) {
267 uint32_t state = crc32c(frame, seed_length);
268 for (size_t i = begin; i < end; ++i) frame[i] = padding_byte(state);
269}
270
271bool padding_matches(const uint8_t *frame, size_t begin, size_t end, size_t seed_length) {
272 uint32_t state = crc32c(frame, seed_length);
273 for (size_t i = begin; i < end; ++i) if (frame[i] != padding_byte(state)) return false;
274 return true;
275}
276
277size_t extended_tier_index(ckey_extended_tier tier, size_t payload_length) {
278 if (tier == CKEY_EXTENDED_TIER_AUTO) {
279 for (size_t i = 0; i < kExtendedTierCapacities.size(); ++i)
280 if (payload_length <= kExtendedTierCapacities[i]) return i;
281 return kExtendedTierCapacities.size();
282 }
283 for (size_t i = 0; i < kExtendedTierCapacities.size(); ++i)
284 if (static_cast<size_t>(tier) == kExtendedTierCapacities[i]) return i;
285 return kExtendedTierCapacities.size();
286}
287
288struct Node { bool polar; bool dial; double x, y; int row, col; int ring, slot; };
289
290bool in_finder(int r, int c) {
291 const bool tl = r < 6 && c < 6, tr = r < 6 && c >= kSide - 6;
292 const bool bl = r >= kSide - 6 && c < 6, br = r >= kSide - 6 && c >= kSide - 6;
293 return tl || tr || bl || br;
294}
295bool grid_key(int r, int c) { return (c == 2 || c == 3) && (r == 11 || r == 12); }
296bool ray_key(int slot) { return slot == 0 || slot == 54 || slot == 55; }
297bool ring_key(int ring, int slot) { return ring == 3 && slot >= 18 && slot <= 25; }
298
299std::vector<Node> build_data_nodes() {
300 std::vector<Node> cart, polar, out;
301 std::array<std::vector<Node>, 72> cart_by_angle;
302 // Fixed Cartesian field is sampled outside the polar aperture. The four
303 // corner finders and the left-side Grid Key never carry payload.
304 for (int r = 1; r < kSide - 1; ++r) for (int c = 1; c < kSide - 1; ++c) {
305 const double x = c + .5, y = r + .5;
306 const double dx = x - kCenter, dy = y - kCenter;
307 if (in_finder(r, c) || grid_key(r, c) || dx * dx + dy * dy <= 10.4 * 10.4) continue;
308 double angle = std::atan2(dx, -dy);
309 if (angle < 0) angle += kTau;
310 const int slot = static_cast<int>(std::lround(angle * 72.0 / kTau)) % 72;
311 cart_by_angle[slot].push_back({false, false, x, y, r, c, -1, -1});
312 }
313 for (auto &bin : cart_by_angle) std::sort(bin.begin(), bin.end(), [=](const Node &a, const Node &b) {
314 const double ax = a.x-kCenter, ay = a.y-kCenter, bx = b.x-kCenter, by = b.y-kCenter;
315 const double ar=ax*ax+ay*ay, br=bx*bx+by*by;
316 if (ar != br) return ar > br;
317 if (a.row != b.row) return a.row < b.row;
318 return a.col < b.col;
319 });
320 for (size_t depth = 0; ; ++depth) {
321 bool any = false;
322 for (int step = 0; step < 72; ++step) {
323 auto &bin = cart_by_angle[(step * 37) % 72];
324 if (depth < bin.size()) { cart.push_back(bin[depth]); any = true; }
325 }
326 if (!any) break;
327 }
328 // Four concentric payload rings occupy the inner field. A fifth layer of
329 // radial data cells is a narrow annular dial band, never spokes to center.
330 std::array<std::vector<Node>, 5> polar_layers;
331 for (int layer = 0; layer < 5; ++layer) for (int step = 0; step < 72; ++step) {
332 const int slot = (step * 37 + layer * 13) % 72;
333 if (ray_key(slot)) continue;
334 if (layer == 0) polar_layers[layer].push_back({true, true, 0, 0, -1, -1, -2, slot});
335 else {
336 const int ring = layer - 1;
337 if (ring_key(ring, slot)) continue;
338 const double radius = 3.6 + 0.8 * ring;
339 const double a = kTau * slot / 72.0;
340 polar_layers[layer].push_back({true, false, kCenter + radius * std::sin(a), kCenter - radius * std::cos(a), -1, -1, ring, slot});
341 }
342 }
343 // Put all dial sites first so every one of the 69 length-coded data rays
344 // is inside the locator codeword, then round-robin the four dot rings.
345 polar = polar_layers[0];
346 for (size_t depth = 0; ; ++depth) {
347 bool any = false;
348 for (size_t layer = 1; layer < polar_layers.size(); ++layer)
349 if (depth < polar_layers[layer].size()) { polar.push_back(polar_layers[layer][depth]); any = true; }
350 if (!any) break;
351 }
352 // Interleave coordinate systems in the placement sequence. Local image
353 // damage is therefore less likely to erase a consecutive run of bytes.
354 size_t ci = 0, pi = 0;
355 while (ci < cart.size() || pi < polar.size()) {
356 if (ci < cart.size()) out.push_back(cart[ci++]);
357 if (pi < polar.size()) out.push_back(polar[pi++]);
358 }
359 return out;
360}
361
362const std::vector<Node> &data_nodes() { static const std::vector<Node> nodes = build_data_nodes(); return nodes; }
363
364bool code_bit(const ckey_symbol *s, size_t i) { return ((s->codeword[i / 8] >> (7 - (i % 8))) & 1u) != 0; }
365
366// ---------------------------------------------------------------------------
367// Dense-profile layout (Profile 2 Format 0.25, Profile 3 Format 0.26).
368//
369// Safe area: a candidate Cartesian module is placed only if its ink (bounded
370// by the module's circumscribed disc) keeps a declared clearance from every
371// structural mark: the frame stroke, each finder arc including its round
372// caps and its concave side, the Grid Key, and the radial alphabet. All
373// tests below use only +, *, sqrt, and comparisons on exactly representable
374// constants, so every conforming implementation derives the same site set.
375//
376// No dead space: every site (Cartesian, ring, dial/ray component) carries a
377// value. Sites are ordered by a keyed bijective hash of their integer
378// identity, so the codeword is spread uniformly over the whole symbol. Sites
379// past the codeword carry fill. All site values are XORed with a fixed
380// SplitMix32 whitening stream; this is optical modulation (it prevents
381// payload-dependent empty or solid regions) and is not error correction.
382// ---------------------------------------------------------------------------
383struct DenseGeometry {
384 double frame_center, frame_half, frame_radius, frame_half_stroke, frame_clear;
385 double finder_inset, finder_radius, finder_half_stroke, finder_clear, side;
386 double grid_x0, grid_y0, grid_x1, grid_y1, grid_clear;
387 double polar_center, ray_ink_outer, polar_clear;
388 double key_ray_r0, key_ray_length, key_ray_half_width;
389 double key_ray_dir[3][2]; // unit (sin, -cos) for each Ray Key slot
390 double key_ray_fraction[3];
391 double module_half; // half side of a square Cartesian module
392};
393
394double rounded_square_sd(double x, double y, double center, double half, double radius) {
395 const double qx = std::abs(x - center) - (half - radius), qy = std::abs(y - center) - (half - radius);
396 const double ox = std::max(qx, 0.0), oy = std::max(qy, 0.0);
397 return std::sqrt(ox * ox + oy * oy) + std::min(std::max(qx, qy), 0.0) - radius;
398}
399
400// Distance to a corner finder centerline: the quarter circle around
401// (cx, cy) lying in the symbol's outer corner quadrant.
402double finder_centerline_distance(double x, double y, double cx, double cy, double r, bool right, bool bottom) {
403 double dx = x - cx, dy = y - cy;
404 if (right) dx = -dx;
405 if (bottom) dy = -dy;
406 if (dx <= 0 && dy <= 0) return std::abs(std::sqrt(dx * dx + dy * dy) - r);
407 const double ex = dx + r, ey = dy + r;
408 return std::min(std::sqrt(ex * ex + dy * dy), std::sqrt(dx * dx + ey * ey));
409}
410
411double segment_distance(double x, double y, double x0, double y0, double x1, double y1) {
412 const double vx = x1 - x0, vy = y1 - y0, wx = x - x0, wy = y - y0;
413 const double t = std::clamp((wx * vx + wy * vy) / (vx * vx + vy * vy), 0.0, 1.0);
414 const double px = x0 + t * vx - x, py = y0 + t * vy - y;
415 return std::sqrt(px * px + py * py);
416}
417
418// Signed safe-area slack for a Cartesian module centered at (x, y): positive
419// means every structural clearance is met. Exposed for layout tests.
420double dense_site_margin(const DenseGeometry &g, double x, double y) {
421 const double e = g.module_half * 1.4142135623730951; // circumscribed disc
422 double m = -rounded_square_sd(x, y, g.frame_center, g.frame_half, g.frame_radius) - g.frame_half_stroke - e - g.frame_clear;
423 const double near = g.finder_inset, far = g.side - g.finder_inset;
424 const double finder_need = g.finder_half_stroke + e + g.finder_clear;
425 m = std::min(m, finder_centerline_distance(x, y, near, near, g.finder_radius, false, false) - finder_need);
426 m = std::min(m, finder_centerline_distance(x, y, far, near, g.finder_radius, true, false) - finder_need);
427 m = std::min(m, finder_centerline_distance(x, y, near, far, g.finder_radius, false, true) - finder_need);
428 m = std::min(m, finder_centerline_distance(x, y, far, far, g.finder_radius, true, true) - finder_need);
429 const double gx = std::max({g.grid_x0 - x, 0.0, x - g.grid_x1}), gy = std::max({g.grid_y0 - y, 0.0, y - g.grid_y1});
430 m = std::min(m, std::sqrt(gx * gx + gy * gy) - e - g.grid_clear);
431 const double dx = x - g.polar_center, dy = y - g.polar_center;
432 m = std::min(m, std::sqrt(dx * dx + dy * dy) - g.ray_ink_outer - e - g.polar_clear);
433 for (int k = 0; k < 3; ++k) {
434 const double r1 = g.key_ray_r0 + g.key_ray_length * g.key_ray_fraction[k];
435 const double ux = g.key_ray_dir[k][0], uy = g.key_ray_dir[k][1];
436 m = std::min(m, segment_distance(x, y, g.polar_center + g.key_ray_r0 * ux, g.polar_center + g.key_ray_r0 * uy,
437 g.polar_center + r1 * ux, g.polar_center + r1 * uy) - g.key_ray_half_width - e - g.polar_clear);
438 }
439 return m;
440}
441
442// Ray Key directions are 0 deg, 270 deg, and 270 + 1/72 turn (P2: slots 0, 108,
443// 110 of 144; P3: slots 0, 432, 440 of 576). The third direction is the only
444// non-axis value; no candidate site is within 1e-6 of any clearance boundary
445// (checked by tests/layout_tests.cpp), so libm rounding cannot change the set.
446DenseGeometry text_geometry() {
447 const double a = kTau * 110.0 / 144.0;
448 return {14.5, 14.0, 3.5, 0.325, 0.5,
449 4.0, 2.3, 0.4, 0.5, 29.0,
450 2.13, 11.13, 3.87, 12.87, 0.5,
451 kCenter, 7.6 + 1.20 + 0.05, 0.5,
452 7.6, 1.9, 0.11,
453 {{0.0, -1.0}, {-1.0, 0.0}, {std::sin(a), -std::cos(a)}},
454 {1.0, 0.5, 0.75},
455 0.17};
456}
457
458DenseGeometry extended_geometry() {
459 const double a = kTau * 440.0 / 576.0;
460 return {58.0, 56.0, 14.0, 1.3, 1.5,
461 16.0, 9.2, 1.6, 1.5, 116.0,
462 8.08, 45.08, 8.92, 45.92, 0.5,
463 58.0, 26.30 + 0.80 + 0.85 * 3 + 0.14, 0.5,
464 26.30, 3.6, 0.14,
465 {{0.0, -1.0}, {-1.0, 0.0}, {std::sin(a), -std::cos(a)}},
466 {1.0, 0.5, 0.75},
467 0.17};
468}
469
470// lowbias32: a bijection on 32-bit words, so distinct site identities never tie.
471uint32_t site_hash(uint32_t x) {
472 x ^= x >> 16; x *= 0x7feb352du; x ^= x >> 15; x *= 0x846ca68bu; x ^= x >> 16;
473 return x;
474}
475constexpr uint32_t kTextPlacementKey = 0x434b5032u; // "CKP2"
476constexpr uint32_t kExtendedPlacementKey = 0x434b5033u; // "CKP3"
477constexpr uint32_t kTextWhiteningSeed = 0x434b5732u; // "CKW2"
478constexpr uint32_t kExtendedWhiteningSeed = 0x434b5733u; // "CKW3"
479
480uint32_t site_identity(uint32_t kind, uint32_t a, uint32_t b) { return (kind << 24) | (a << 12) | b; }
481
482template <class NodeT>
483void order_sites(std::vector<NodeT> &nodes, uint32_t key) {
484 std::sort(nodes.begin(), nodes.end(), [key](const NodeT &l, const NodeT &r) {
485 return site_hash(l.id ^ key) < site_hash(r.id ^ key);
486 });
487}
488
489std::vector<uint8_t> whitening_bits(uint32_t seed, size_t count) {
490 std::vector<uint8_t> bits(count);
491 uint32_t state = seed; uint8_t byte = 0;
492 for (size_t i = 0; i < count; ++i) {
493 if (i % 8 == 0) byte = padding_byte(state);
494 bits[i] = static_cast<uint8_t>((byte >> (7 - i % 8)) & 1u);
495 }
496 return bits;
497}
498
499// Normative site counts (Format 0.25 / 0.26); tests/layout_tests.cpp asserts
500// that the derived layouts match them exactly.
501constexpr size_t kTextSiteCount = 2630, kTextCartesianSites = 1377;
502constexpr size_t kExtendedSiteCount = 42645, kExtendedCartesianSites = 31244;
503
504struct TextNode { bool cart; bool dial; double x, y; int row, col, ring, slot; uint32_t id; };
505
506constexpr int kTextGrid = 58, kTextSlots = 144, kTextRings = 8;
507bool text_reserved_slot(int slot) { return slot == 0 || slot == 108 || slot == 110; }
508
509std::vector<TextNode> build_text_nodes() {
510 constexpr double pitch = 29.0 / kTextGrid;
511 const DenseGeometry g = text_geometry();
512 std::vector<TextNode> nodes;
513 for (int row = 0; row < kTextGrid; ++row) for (int col = 0; col < kTextGrid; ++col) {
514 const double x = (col + .5) * pitch, y = (row + .5) * pitch;
515 if (dense_site_margin(g, x, y) <= 0.0) continue;
516 nodes.push_back({true, false, x, y, row, col, -1, -1,
517 site_identity(0, static_cast<uint32_t>(row), static_cast<uint32_t>(col))});
518 }
519 // Every non-key dial slot carries a short (0) or long (1) ray.
520 for (int slot = 0; slot < kTextSlots; ++slot)
521 if (!text_reserved_slot(slot)) nodes.push_back({false, true, 0, 0, -1, -1, -1, slot, site_identity(1, 0, static_cast<uint32_t>(slot))});
522 for (int ring = 0; ring < kTextRings; ++ring) for (int slot = 0; slot < kTextSlots; ++slot) {
523 if (text_reserved_slot(slot) || (ring == kTextRings - 1 && slot >= 36 && slot <= 51)) continue;
524 const double radius = 3.4 + .43 * ring;
525 const double a = kTau * slot / kTextSlots;
526 nodes.push_back({false, false, kCenter + radius * std::sin(a), kCenter - radius * std::cos(a), -1, -1, ring, slot,
527 site_identity(2, static_cast<uint32_t>(ring), static_cast<uint32_t>(slot))});
528 }
529 order_sites(nodes, kTextPlacementKey);
530 return nodes;
531}
532
533const std::vector<TextNode> &text_nodes() { static const std::vector<TextNode> nodes = build_text_nodes(); return nodes; }
534const std::vector<uint8_t> &text_whitening() { static const auto bits = whitening_bits(kTextWhiteningSeed, text_nodes().size()); return bits; }
535
536bool text_code_bit(const ckey_text_symbol *s, size_t i) { return ((s->codeword[i / 8] >> (7 - (i % 8))) & 1u) != 0; }
537// Printed value of site i: codeword bit (or 0 for fill sites) XOR whitening.
538bool text_site_value(const ckey_text_symbol *s, size_t i) {
539 const bool data = i < kTextCodewordBytes * 8 && text_code_bit(s, i);
540 return data != (text_whitening()[i] != 0);
541}
542
543enum class ExtendedKind : uint8_t { cart, ring, ray };
544struct ExtendedNode { ExtendedKind kind; double x, y; int ring, slot, component; uint32_t id; };
545
546constexpr int kExtendedGrid = 232, kExtendedRingSlots = 288, kExtendedRings = 34, kExtendedRaySlots = 576;
547// Format 0.26 extends the ring field outward (outer ring 23.96 -> 24.62,
548// Ring Key 24.45 -> 25.11) so the Ring Key-to-ray gap is 1.19 units, as in
549// Profile 2, instead of a 1.85-unit dark annulus. Rays stay at r=26.30 because
550// moving them inward would make adjacent wide rays overlap.
551constexpr double kExtendedRingInner = 7.0, kExtendedRingOuter = 24.62;
552constexpr double kExtendedRingKeyRadius = 25.11;
553// Never printed: between the Ring Key and the ray alphabet's inner end.
554constexpr double kExtendedPolarGapRadius = 25.7;
555constexpr double kExtendedRingPitch = (kExtendedRingOuter - kExtendedRingInner) / (kExtendedRings - 1);
556bool extended_reserved_ray(int slot) { return slot == 0 || slot == 432 || slot == 440; }
557
558std::vector<ExtendedNode> build_extended_nodes() {
559 constexpr double pitch = .5, center = 58.0;
560 const DenseGeometry g = extended_geometry();
561 std::vector<ExtendedNode> nodes;
562 for (int row = 0; row < kExtendedGrid; ++row) for (int col = 0; col < kExtendedGrid; ++col) {
563 const double x = (col + .5) * pitch, y = (row + .5) * pitch;
564 if (dense_site_margin(g, x, y) <= 0.0) continue;
565 nodes.push_back({ExtendedKind::cart, x, y, -1, -1, -1,
566 site_identity(0, static_cast<uint32_t>(row), static_cast<uint32_t>(col))});
567 }
568 for (int ring = 0; ring < kExtendedRings; ++ring) for (int slot = 0; slot < kExtendedRingSlots; ++slot) {
569 if (slot == 0 || slot == 216 || slot == 224 || (ring == kExtendedRings - 1 && slot >= 72 && slot <= 79)) continue;
570 const double radius = kExtendedRingInner + kExtendedRingPitch * ring;
571 const double a = kTau * slot / kExtendedRingSlots;
572 nodes.push_back({ExtendedKind::ring, center + radius * std::sin(a), center - radius * std::cos(a), ring, slot, -1,
573 site_identity(2, static_cast<uint32_t>(ring), static_cast<uint32_t>(slot))});
574 }
575 // Every non-key ray is always visible: two Gray-coded length bits plus
576 // one width bit form an eight-state alphabet. Each component is a site.
577 for (int slot = 0; slot < kExtendedRaySlots; ++slot) {
578 if (extended_reserved_ray(slot)) continue;
579 for (int component = 0; component < 3; ++component)
580 nodes.push_back({ExtendedKind::ray, 0, 0, -1, slot, component,
581 site_identity(3, static_cast<uint32_t>(component), static_cast<uint32_t>(slot))});
582 }
583 order_sites(nodes, kExtendedPlacementKey);
584 return nodes;
585}
586
587const std::vector<ExtendedNode> &extended_nodes() { static const std::vector<ExtendedNode> nodes = build_extended_nodes(); return nodes; }
588const std::vector<uint8_t> &extended_whitening() { static const auto bits = whitening_bits(kExtendedWhiteningSeed, extended_nodes().size()); return bits; }
589
590bool extended_code_bit(const ckey_extended_symbol *s, size_t i) {
591 return ((s->codeword[i / 8] >> (7 - (i % 8))) & 1u) != 0;
592}
593bool extended_site_value(const ckey_extended_symbol *s, size_t i) {
594 const bool data = i < kExtendedBits && extended_code_bit(s, i);
595 return data != (extended_whitening()[i] != 0);
596}
597
598void set_status(ckey_diagnostics *d, ckey_status s, const char *m) {
599 if (!d) return;
600 d->abi_version = CKEY_ABI_VERSION; d->status = s;
601 d->corrected_symbols = 0; d->erasures_used = 0;
602 std::snprintf(d->message, sizeof(d->message), "%s", m);
603}
604
605double polar_dot_radius() {
606 // A single physical dot size keeps all four data rings and the Ring Key uniform.
607 return 0.15;
608}
609
610void svg_circle(std::ostringstream &o, double x, double y, double r) {
611 o << "<circle cx=\"" << x << "\" cy=\"" << y << "\" r=\"" << r << "\" stroke=\"none\"/>";
612}
613
614// A run of adjacent ring sites from slot position `from` to `to` (in slot
615// units), drawn as one round-capped arc. Caps add a dot diameter, so the
616// centerline is shortened by one dot radius at each end. Runs spanning more
617// than half a turn must set the SVG large-arc flag, or renderers draw the
618// complementary short arc on the opposite side of the ring.
619void svg_ring_run(std::ostringstream &o, double center, double radius, double from, double to,
620 double slots, double dot_radius, const char *stroke_width) {
621 const double cap = dot_radius / radius;
622 const double a0 = kTau * from / slots + cap, a1 = kTau * to / slots - cap;
623 o << "<path d=\"M " << center + radius * std::sin(a0) << ' ' << center - radius * std::cos(a0)
624 << " A " << radius << ' ' << radius << " 0 " << (a1 - a0 > kTau / 2 ? 1 : 0) << " 1 "
625 << center + radius * std::sin(a1) << ' ' << center - radius * std::cos(a1)
626 << "\" fill=\"none\" stroke-width=\"" << stroke_width << "\" stroke-linecap=\"round\"/>";
627}
628
629// CKey's finder follows the rounded corner itself. It is deliberately a
630// single broad inset arc rather than a nested set of marks that projects into
631// the payload field. Only the top-left arc is interrupted; that clear gap is
632// the structural orientation signature.
633void svg_corner_finders(std::ostringstream &o, double side, double inset,
634 const std::array<double, 3> &radii, double thickness,
635 double visible_split_gap) {
636 for (int corner = 0; corner < 4; ++corner) {
637 const std::string transform =
638 corner == 0 ? "" :
639 corner == 1 ? "translate(" + std::to_string(side) + " 0) scale(-1 1)" :
640 corner == 2 ? "translate(" + std::to_string(side) + " " + std::to_string(side) + ") scale(-1 -1)" :
641 "translate(0 " + std::to_string(side) + ") scale(1 -1)";
642 o << "<g transform=\"" << transform << "\" fill=\"none\" stroke-linecap=\"round\">";
643 for (double radius : radii) {
644 if (radius <= 0.0) continue;
645 if (corner == 0) {
646 // Include cap diameter in the angular calculation: the clear
647 // visual gap is exactly visible_split_gap, not merely the
648 // shorter centerline gap.
649 const double half_gap = (visible_split_gap + thickness) / (2.0 * radius);
650 // The outer (top-left) quadrant uses angles 180°..270°.
651 // Its concave/open side points down-right, toward the polar
652 // field, and the outermost path meets the frame tangents.
653 const double middle = 5.0 * kTau / 8.0;
654 const double a1 = middle - half_gap, a2 = middle + half_gap;
655 o << "<path d=\"M " << inset - radius << ' ' << inset
656 << " A " << radius << ' ' << radius << " 0 0 1 "
657 << inset + radius * std::cos(a1) << ' ' << inset + radius * std::sin(a1)
658 << " M " << inset + radius * std::cos(a2) << ' ' << inset + radius * std::sin(a2)
659 << " A " << radius << ' ' << radius << " 0 0 1 " << inset << ' ' << inset - radius
660 << "\" stroke-width=\"" << thickness << "\"/>";
661 } else {
662 o << "<path d=\"M " << inset - radius << ' ' << inset
663 << " A " << radius << ' ' << radius << " 0 0 1 " << inset << ' ' << inset - radius
664 << "\" stroke-width=\"" << thickness << "\"/>";
665 }
666 }
667 o << "</g>";
668 }
669}
670
671struct ImagePoint { double x, y; };
672
673bool solve_homography(const double src[8], const double dst[8], double h[8]) {
674 double a[8][9]{};
675 for (int i = 0; i < 4; ++i) {
676 const double x = src[2*i], y = src[2*i+1], u = dst[2*i], v = dst[2*i+1];
677 a[2*i][0]=x; a[2*i][1]=y; a[2*i][2]=1; a[2*i][6]=-u*x; a[2*i][7]=-u*y; a[2*i][8]=u;
678 a[2*i+1][3]=x; a[2*i+1][4]=y; a[2*i+1][5]=1; a[2*i+1][6]=-v*x; a[2*i+1][7]=-v*y; a[2*i+1][8]=v;
679 }
680 for (int col=0; col<8; ++col) {
681 int pivot=col;
682 for (int row=col+1; row<8; ++row) if (std::abs(a[row][col])>std::abs(a[pivot][col])) pivot=row;
683 if (std::abs(a[pivot][col])<1e-12) return false;
684 if (pivot!=col) for (int j=col; j<9; ++j) std::swap(a[pivot][j],a[col][j]);
685 const double d=a[col][col]; for (int j=col; j<9; ++j) a[col][j]/=d;
686 for (int row=0; row<8; ++row) if (row!=col) { const double f=a[row][col]; for (int j=col; j<9; ++j) a[row][j]-=f*a[col][j]; }
687 }
688 for (int i=0;i<8;++i) h[i]=a[i][8];
689 return true;
690}
691
692bool map_point(const double h[8], double x, double y, ImagePoint &p) {
693 const double d=h[6]*x+h[7]*y+1.0;
694 if (!std::isfinite(d) || std::abs(d)<1e-12) return false;
695 p={(h[0]*x+h[1]*y+h[2])/d,(h[3]*x+h[4]*y+h[5])/d};
696 return std::isfinite(p.x) && std::isfinite(p.y);
697}
698
699// Profile 1's original 3x3 support, in canonical units. It suits P1's
700// one-unit modules; dense-profile marks are 0.10-0.34 units wide, so their
701// samplers pass a support proportional to the feature they read.
702constexpr double kLocatorSampleSpread = 0.12;
703// P1 keeps its original support for dots and dial rays: narrower supports
704// helped synthetic renders but lost the noise averaging the committed iPhone
705// camera fixtures depend on. Per-class thresholds recover the thin rays.
706constexpr double kLocatorDotSpread = kLocatorSampleSpread;
707constexpr double kLocatorRaySpread = kLocatorSampleSpread;
708// Between P1's outer dot ring (r <= 6.15) and its dial band (r >= 7.6):
709// never printed, unlike the former (1.5, 11.5) reference, which is a
710// Cartesian payload module.
711constexpr double kLocatorApertureRadius = 6.9;
712// A dense decoder samples every site only for orientations whose fixed keys
713// agree: at least this fraction of key samples must match the expected print
714// pattern. Wrong orientations and non-symbols are rejected cheaply.
715constexpr double kDenseKeyGate = 0.8;
716constexpr double kModuleSpread = 0.06; // 0.34-unit dense Cartesian modules
717constexpr double kDotSpread = 0.025; // 0.15-0.20-unit ring dots and arcs
718constexpr double kRaySpread = 0.02; // 0.10-0.16-unit radial strokes
719// A point inside the P3 Grid Key clearance: guaranteed unprinted.
720constexpr double kExtendedGridClearX = 7.75, kExtendedGridClearY = 45.5;
721
722double gray_sample(const uint8_t *gray, size_t width, size_t height, size_t stride,
723 const double h[8], double x, double y, double spread = kLocatorSampleSpread) {
724 // A small center-weighted 3x3 sample tolerates rasterization and mild blur.
725 const double offsets[3]={-spread,0.0,spread};
726 constexpr double weights[3]={1.0,2.0,1.0};
727 double sum=0, weight_sum=0;
728 for (int iy=0;iy<3;++iy) for (int ix=0;ix<3;++ix) {
729 ImagePoint p{}; if (!map_point(h,x+offsets[ix],y+offsets[iy],p)) return -1;
730 if (p.x<0 || p.y<0 || p.x>static_cast<double>(width-1) || p.y>static_cast<double>(height-1)) return -1;
731 const size_t x0=static_cast<size_t>(p.x), y0=static_cast<size_t>(p.y);
732 const size_t x1=std::min(x0+1,width-1), y1=std::min(y0+1,height-1);
733 const double fx=p.x-x0, fy=p.y-y0;
734 const double top=gray[y0*stride+x0]*(1-fx)+gray[y0*stride+x1]*fx;
735 const double bottom=gray[y1*stride+x0]*(1-fx)+gray[y1*stride+x1]*fx;
736 const double w=weights[ix]*weights[iy]; sum+=(top*(1-fy)+bottom*fy)*w; weight_sum+=w;
737 }
738 return sum/weight_sum;
739}
740
741double polar_sample(const uint8_t *gray, size_t width, size_t height, size_t stride,
742 const double h[8], double radius, double slot, double spread = kLocatorSampleSpread) {
743 const double a=kTau*slot/72.0;
744 return gray_sample(gray,width,height,stride,h,kCenter+radius*std::sin(a),kCenter-radius*std::cos(a),spread);
745}
746
747double polar_sample_slots(const uint8_t *gray, size_t width, size_t height, size_t stride,
748 const double h[8], double center, double radius,
749 double slot, double slot_count, double spread = kLocatorSampleSpread) {
750 const double a=kTau*slot/slot_count;
751 return gray_sample(gray,width,height,stride,h,center+radius*std::sin(a),center-radius*std::cos(a),spread);
752}
753
754// Two-cluster (two-means) split of normalized samples (0 = unprinted
755// reference, 1 = printed reference). Whitening makes every feature class
756// roughly half printed, so a class's own samples calibrate its threshold;
757// this absorbs the lower peak contrast of sub-pixel dots and strokes. The
758// cut is bounded to [0.05, 0.95]: P3 width coverage legitimately separates
759// near 0.85, so a tighter bound would misplace it. `separation` reports the
760// distance between the two cluster means.
761double two_means_cut(const std::vector<double> &values, double &separation) {
762 separation = 0;
763 if (values.size() < 16) return 0.5;
764 const auto [min_it, max_it] = std::minmax_element(values.begin(), values.end());
765 double threshold = std::clamp((*min_it + *max_it) * 0.5, 0.05, 0.95);
766 for (int iteration = 0; iteration < 32; ++iteration) {
767 double sum_lo = 0, sum_hi = 0; size_t n_lo = 0, n_hi = 0;
768 for (double v : values) { if (v > threshold) { sum_hi += v; ++n_hi; } else { sum_lo += v; ++n_lo; } }
769 if (!n_lo || !n_hi) { separation = 0; break; }
770 const double lo = sum_lo / n_lo, hi = sum_hi / n_hi;
771 separation = hi - lo;
772 const double next = std::clamp((lo + hi) * 0.5, 0.05, 0.95);
773 if (std::abs(next - threshold) < 1e-6) break;
774 threshold = next;
775 }
776 return threshold;
777}
778
779double class_threshold(const std::vector<double> &values) {
780 double separation = 0;
781 return two_means_cut(values, separation);
782}
783
784// Ring sites join into arcs, so under blur an isolated dot peaks far lower
785// than a dot inside a run, and a gap between two runs rises. Refine each data
786// ring site's decision by its neighbour context (0, 1, or 2 printed ring
787// neighbours), with a separate two-means cut per context. Fill sites'
788// printed values are known exactly (whitening only), which anchors the
789// context. A context keeps the class cut unless its own two clusters are
790// clearly separated, so a one-sided context is never split spuriously.
791// `grid` maps ring * slots + slot to a site index (-1 for reserved slots).
792void refine_ring_context_rings(const std::vector<int> &grid, const std::vector<int> &ring_slots, int stride, size_t data_sites,
793 const std::vector<uint8_t> &white, const std::vector<double> &level,
794 double class_cut, std::vector<uint8_t> &printed);
795
796void refine_ring_context(const std::vector<int> &grid, int rings, int slots, size_t data_sites,
797 const std::vector<uint8_t> &white, const std::vector<double> &level,
798 double class_cut, std::vector<uint8_t> &printed) {
799 refine_ring_context_rings(grid, std::vector<int>(static_cast<size_t>(rings), slots), slots, data_sites, white, level, class_cut, printed);
800}
801
802// grid maps ring * stride + slot -> site index (-1 reserved); ring r has
803// ring_slots[r] slots and wraps at that count.
804void refine_ring_context_rings(const std::vector<int> &grid, const std::vector<int> &ring_slots, int stride, size_t data_sites,
805 const std::vector<uint8_t> &white, const std::vector<double> &level,
806 double class_cut, std::vector<uint8_t> &printed) {
807 const int rings = static_cast<int>(ring_slots.size());
808 constexpr double kMinSeparation = 0.2;
809 const auto value_at = [&](int ring, int slot) -> int {
810 const int slots = ring_slots[static_cast<size_t>(ring)];
811 const int index = grid[static_cast<size_t>(ring) * stride + static_cast<size_t>((slot + slots) % slots)];
812 return index < 0 ? 0 : printed[static_cast<size_t>(index)];
813 };
814 for (int pass = 0; pass < 2; ++pass) {
815 std::array<std::vector<double>, 3> by_context;
816 std::vector<std::pair<size_t, int>> sites;
817 for (int ring = 0; ring < rings; ++ring) for (int slot = 0; slot < ring_slots[static_cast<size_t>(ring)]; ++slot) {
818 const int index = grid[static_cast<size_t>(ring) * stride + slot];
819 if (index < 0 || static_cast<size_t>(index) >= data_sites) continue;
820 const int context = value_at(ring, slot - 1) + value_at(ring, slot + 1);
821 by_context[context].push_back(level[static_cast<size_t>(index)]);
822 sites.push_back({static_cast<size_t>(index), context});
823 }
824 std::array<double, 3> cut{class_cut, class_cut, class_cut};
825 for (int context = 0; context < 3; ++context) {
826 double separation = 0;
827 const double candidate = two_means_cut(by_context[context], separation);
828 if (separation >= kMinSeparation) cut[context] = candidate;
829 }
830 for (const auto &[index, context] : sites) printed[index] = level[index] > cut[context] ? 1 : 0;
831 }
832 (void)white;
833}
834
835bool is_tiered_extended_format(uint8_t format) {
836 return format == 17u || format == 20u || format == 21u || format == 24u || format == CKEY_EXTENDED_FORMAT_VERSION;
837}
838
839bool is_text_format(uint8_t format) {
840 return format == 9u || format == 15u || format == 18u || format == 19u || format == 22u || format == 23u ||
841 format == CKEY_TEXT_FORMAT_VERSION;
842}
843
844bool valid_quad(const double q[8]);
845
846// Shared argument contract for every grayscale entry point.
847bool valid_image_args(const uint8_t *gray, size_t width, size_t height, size_t stride, const double quad[8]) {
848 if (!gray || !quad || width < 2 || height < 2 || stride < width ||
849 height > std::numeric_limits<size_t>::max() / stride) return false;
850 for (int i = 0; i < 8; ++i) if (!std::isfinite(quad[i])) return false;
851 return valid_quad(quad);
852}
853
854bool valid_quad(const double q[8]) {
855 double area=0; int sign=0;
856 for (int i=0;i<4;++i) {
857 const double x1=q[2*i], y1=q[2*i+1], x2=q[2*((i+1)%4)], y2=q[2*((i+1)%4)+1];
858 area+=x1*y2-x2*y1;
859 const double x3=q[2*((i+2)%4)], y3=q[2*((i+2)%4)+1];
860 const double cross=(x2-x1)*(y3-y2)-(y2-y1)*(x3-x2);
861 if (std::abs(cross)<1e-6) return false;
862 const int current=cross>0?1:-1;
863 if (sign && sign!=current) return false;
864 sign=current;
865 }
866 return std::abs(area)>4.0;
867}
868}
869
870namespace {
871// Fixed-key evidence for one candidate homography: contrast between printed
872// and never-printed key samples, and the fraction of key samples that agree
873// with the expected print pattern. Used by the calibration scores and as a
874// cheap per-orientation gate before a dense decoder samples ~2k-21k sites.
875struct KeyFit { bool valid = false; double contrast = 0, evidence = 0; };
876
877KeyFit text_key_fit(const uint8_t *gray, size_t width, size_t height, size_t stride, const double h[8]) {
878 std::vector<double> marks, empty;
879 for (int r : {11,12}) for (int c : {2,3})
880 marks.push_back(gray_sample(gray,width,height,stride,h,c+.5,r+.5));
881 for (int slot : {36,38,42})
882 marks.push_back(polar_sample_slots(gray,width,height,stride,h,kCenter,6.41,slot,144.0,kDotSpread));
883 marks.push_back(polar_sample_slots(gray,width,height,stride,h,kCenter,6.41,47.5,144.0,kDotSpread));
884 marks.push_back(polar_sample_slots(gray,width,height,stride,h,kCenter,8.8,0.0,144.0,kRaySpread));
885 marks.push_back(polar_sample_slots(gray,width,height,stride,h,kCenter,8.4,108.0,144.0,kRaySpread));
886 marks.push_back(polar_sample_slots(gray,width,height,stride,h,kCenter,8.8,110.0,144.0,kRaySpread));
887 constexpr double finder_inset=4.0, finder_radius=2.3;
888 const double diagonal=kTau/8.0;
889 for (const auto &[cx,cy,a] : {std::tuple{25.0,4.0,kTau*315.0/360.0},
890 std::tuple{4.0,25.0,kTau*135.0/360.0},
891 std::tuple{25.0,25.0,kTau*45.0/360.0}})
892 marks.push_back(gray_sample(gray,width,height,stride,h,cx+finder_radius*std::cos(a),cy+finder_radius*std::sin(a)));
893 for (double a : {kTau*198.0/360.0,kTau*252.0/360.0})
894 marks.push_back(gray_sample(gray,width,height,stride,h,finder_inset+finder_radius*std::cos(a),finder_inset+finder_radius*std::sin(a)));
895 // The top-left finder's split gap (225 deg) is never printed. (The 45 deg
896 // point used by Profile 1 is a payload site under Profile 2's safe area.)
897 empty.push_back(gray_sample(gray,width,height,stride,h,finder_inset+finder_radius*std::cos(5.0*diagonal),finder_inset+finder_radius*std::sin(5.0*diagonal)));
898 empty.push_back(gray_sample(gray,width,height,stride,h,1.5,11.5));
899 empty.push_back(polar_sample_slots(gray,width,height,stride,h,kCenter,6.41,40.0,144.0,kDotSpread));
900 empty.push_back(polar_sample_slots(gray,width,height,stride,h,kCenter,8.8,108.0,144.0,kRaySpread));
901 if (std::any_of(marks.begin(),marks.end(),[](double v){return v<0;}) || std::any_of(empty.begin(),empty.end(),[](double v){return v<0;})) return {};
902 const double mark_mean=std::accumulate(marks.begin(),marks.end(),0.0)/marks.size();
903 const double empty_mean=std::accumulate(empty.begin(),empty.end(),0.0)/empty.size();
904 const double contrast=std::abs(mark_mean-empty_mean), threshold=(mark_mean+empty_mean)*.5;
905 const bool dark=mark_mean<empty_mean;
906 const auto marked=[&](double value){return dark ? value<threshold : value>threshold;};
907 const size_t evidence=std::count_if(marks.begin(),marks.end(),marked)+
908 std::count_if(empty.begin(),empty.end(),[&](double value){return !marked(value);});
909 return {true, contrast, static_cast<double>(evidence)/static_cast<double>(marks.size()+empty.size())};
910}
911
912KeyFit extended_key_fit(const uint8_t *gray, size_t width, size_t height, size_t stride, const double h[8]) {
913 std::vector<double> marks, empty;
914 // Grid Key, Ring Key, and Ray Key are all fixed in physical modules.
915 for (int r=0;r<2;++r) for (int c=0;c<2;++c) marks.push_back(gray_sample(gray,width,height,stride,h,8.25+c*.5,45.25+r*.5,kModuleSpread));
916 for (int slot : {72,73,75}) marks.push_back(polar_sample_slots(gray,width,height,stride,h,58.0,kExtendedRingKeyRadius,slot,288.0,kDotSpread));
917 marks.push_back(polar_sample_slots(gray,width,height,stride,h,58.0,kExtendedRingKeyRadius,77.5,288.0,kDotSpread));
918 marks.push_back(polar_sample_slots(gray,width,height,stride,h,58.0,28.0,0.0,576.0,kRaySpread));
919 marks.push_back(polar_sample_slots(gray,width,height,stride,h,58.0,27.9,432.0,576.0,kRaySpread));
920 marks.push_back(polar_sample_slots(gray,width,height,stride,h,58.0,28.4,440.0,576.0,kRaySpread));
921 // Three whole finder arcs plus both halves of the split orientation
922 // arc. These are measured on the actual *outer* corner quadrants: a
923 // finder mouth faces the polar field but its ink follows the frame.
924 constexpr double finder_radius=9.2;
925 for (const auto &[cx,cy,a] : {std::tuple{100.0,16.0,kTau*315.0/360.0},
926 std::tuple{16.0,100.0,kTau*135.0/360.0},
927 std::tuple{100.0,100.0,kTau*45.0/360.0}})
928 marks.push_back(gray_sample(gray,width,height,stride,h,cx+finder_radius*std::cos(a),cy+finder_radius*std::sin(a)));
929 for (double a : {kTau*195.0/360.0,kTau*255.0/360.0})
930 marks.push_back(gray_sample(gray,width,height,stride,h,16.0+finder_radius*std::cos(a),16.0+finder_radius*std::sin(a)));
931 empty.push_back(gray_sample(gray,width,height,stride,h,16.0+finder_radius*std::cos(kTau*225.0/360.0),16.0+finder_radius*std::sin(kTau*225.0/360.0)));
932 empty.push_back(gray_sample(gray,width,height,stride,h,kExtendedGridClearX,kExtendedGridClearY,kModuleSpread));
933 empty.push_back(polar_sample_slots(gray,width,height,stride,h,58.0,kExtendedRingKeyRadius,74.0,288.0,kDotSpread));
934 empty.push_back(polar_sample_slots(gray,width,height,stride,h,58.0,kExtendedPolarGapRadius,216.0,576.0,kRaySpread));
935 if (std::any_of(marks.begin(),marks.end(),[](double v){return v<0;}) || std::any_of(empty.begin(),empty.end(),[](double v){return v<0;})) return {};
936 const double mark_mean=std::accumulate(marks.begin(),marks.end(),0.0)/marks.size();
937 const double empty_mean=std::accumulate(empty.begin(),empty.end(),0.0)/empty.size();
938 const double contrast=std::abs(mark_mean-empty_mean); const bool dark=mark_mean<empty_mean;
939 const double threshold=(mark_mean+empty_mean)*.5;
940 const auto marked=[&](double value){ return dark ? value<threshold : value>threshold; };
941 const size_t evidence=std::count_if(marks.begin(),marks.end(),marked)+
942 std::count_if(empty.begin(),empty.end(),[&](double value){return !marked(value);});
943 return {true, contrast, static_cast<double>(evidence)/static_cast<double>(marks.size()+empty.size())};
944}
945
946}
947
948
949// ---------------------------------------------------------------------------
950// Profile 0 (Format 0.27): the scalable family. All versions share Profile
951// 2's skeleton in the same 29-unit canonical field: frame, finders, a polar
952// centre whose rings start at r = 3.4, and a dial whose rays start at r = 7.6.
953// Version v sets the module pitch p = 29 / G(v); every payload mark, key, and
954// clearance scales with p. The fixed integer tables below are normative.
955// ---------------------------------------------------------------------------
956namespace {
957
958constexpr int kScalableVersions = static_cast<int>(CKEY_SCALABLE_VERSION_COUNT);
959constexpr std::array<int, kScalableVersions> kScalableGrid = {29, 31, 33, 36, 38, 41, 44, 47, 50, 54, 58, 62, 67, 71, 77, 82, 88, 94, 101, 108, 116, 124, 133, 143, 153, 164, 176, 188, 202, 216, 232};
960constexpr std::array<int, kScalableVersions> kScalableSlots = {72, 80, 80, 88, 96, 104, 112, 120, 128, 136, 144, 152, 168, 176, 192, 200, 216, 232, 248, 272, 288, 304, 328, 352, 376, 408, 440, 464, 504, 536, 576};
961constexpr std::array<int, kScalableVersions> kScalableRings = {3, 3, 3, 4, 4, 5, 5, 6, 6, 7, 8, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 22, 23, 25, 27, 29, 32, 34, 37};
962constexpr std::array<int, kScalableVersions> kScalableGridCol = {2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20, 21, 23};
963constexpr std::array<int, kScalableVersions> kScalableGridRow = {10, 12, 13, 14, 15, 16, 17, 18, 20, 21, 23, 25, 27, 28, 31, 33, 35, 38, 41, 44, 47, 50, 54, 58, 62, 67, 72, 77, 83, 88, 95};
964constexpr std::array<int, 4> kScalableParityPercent = {14, 28, 44, 60}; // L, M, Q, H
965constexpr double kScalableRingInner = 3.4, kScalableDialInner = 7.6;
966constexpr size_t kScalableHeaderBytes = 8, kScalableOverheadBytes = 12; // header + CRC-32C
967
968struct ScalableNode { uint8_t kind; double x, y; int ring, slot; uint32_t id; }; // kind: 0 Cartesian, 1 dial, 2 ring
969
970// Layout families. 0 = standard (Format 0.27). 1 = print (Format 0.28): every
971// mark and gap is at least about one module, for small printed sizes.
972constexpr int kScalableFamilies = 2;
973constexpr std::array<int, kScalableVersions> kScalablePrintRings = {2, 3, 3, 3, 4, 4, 4, 5, 5, 6, 7, 7, 8, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 22, 24, 25, 27, 29, 32};
974
975struct ScalableLayout {
976 int version = 0, family = 0, grid = 0, rings = 0, col0 = 0, row0 = 0;
977 int dial_slots = 0; // dial ray slots (Ray Keys use these)
978 int ring_stride = 0; // max ring slots (ring_grid row length)
979 std::vector<int> ring_slots; // slots on each ring
980 double pitch = 0;
981 double ring_pitch = 0, dot = 0, ray_width = 0, long_len = 0, short_len = 0, dial_sample = 0;
982 int ring_key_span = 16;
983 DenseGeometry geom{};
984 std::vector<ScalableNode> nodes;
985 std::vector<uint8_t> white;
986 std::vector<int> ring_grid; // ring * ring_stride + slot -> site index, -1 reserved
987 size_t codeword_bytes = 0;
988 uint8_t format = CKEY_SCALABLE_FORMAT_VERSION;
989 double ring_radius(int k) const { return kScalableRingInner + ring_pitch * k; }
990 int ray_key_half() const { return 3 * dial_slots / 4; } // 9:00, half length
991 int ray_key_three() const { return 3 * dial_slots / 4 - 2; } // two slots before, 3/4 length
992 int ring_key_slot() const { return ring_slots.back() / 4; } // 3:00, on the outermost ring
993 bool reserved_ray(int slot) const { return slot == 0 || slot == ray_key_half() || slot == ray_key_three(); }
994 double long_ray() const { return long_len; }
995 double short_ray() const { return short_len; }
996 double key_ray() const { return 3.4 * pitch; }
997 // Ring Key on the outermost ring, in slots relative to ring_key_slot():
998 // standard 16-slot pattern (dots 0, 2, 6; run 7.5..15.5), print 8-slot
999 // pattern (dots 0, 2; run 3.5..7.5).
1000 std::vector<int> ring_key_dots() const { return family == 0 ? std::vector<int>{0, 2, 6} : std::vector<int>{0, 2}; }
1001 std::pair<double, double> ring_key_run() const { return family == 0 ? std::pair{7.5, 15.5} : std::pair{3.5, 7.5}; }
1002 std::vector<double> ring_key_marks() const { return family == 0 ? std::vector<double>{0, 2, 6, 11.5} : std::vector<double>{0, 2, 5.5}; }
1003 std::vector<double> ring_key_empties() const { return family == 0 ? std::vector<double>{4} : std::vector<double>{1, 3}; }
1004};
1005
1006DenseGeometry scalable_geometry(int col0, int row0, double p, int slots, double ray_ink_outer) {
1007 const double a = kTau * (3.0 * slots / 4.0 - 2.0) / slots;
1008 const double clear = std::max(0.375, p);
1009 return {14.5, 14.0, 3.5, 0.325, clear,
1010 4.0, 2.3, 0.4, clear, 29.0,
1011 col0 * p + 0.16 * p, row0 * p + 0.16 * p, (col0 + 2) * p - 0.16 * p, (row0 + 2) * p - 0.16 * p, p,
1012 kCenter, ray_ink_outer, p,
1013 kScalableDialInner, 3.4 * p, 0.22 * p,
1014 {{0.0, -1.0}, {-1.0, 0.0}, {std::sin(a), -std::cos(a)}},
1015 {1.0, 0.5, 0.75},
1016 0.34 * p};
1017}
1018
1019// Equal-arc slot count: the largest multiple of 8 whose arc spacing at
1020// radius r is at least one module (print family).
1021int equal_arc_slots(double r, double p) { return 8 * static_cast<int>(std::floor(kTau * r / (8.0 * p))); }
1022
1023std::unique_ptr<ScalableLayout> build_scalable_layout(int v, int family) {
1024 auto L = std::make_unique<ScalableLayout>();
1025 const size_t i = static_cast<size_t>(v - 1);
1026 L->version = v; L->family = family; L->grid = kScalableGrid[i];
1027 L->col0 = kScalableGridCol[i]; L->row0 = kScalableGridRow[i]; L->pitch = 29.0 / L->grid;
1028 const double p = L->pitch;
1029 if (family == 0) {
1030 L->rings = kScalableRings[i]; L->dial_slots = kScalableSlots[i];
1031 L->ring_slots.assign(static_cast<size_t>(L->rings), L->dial_slots);
1032 L->ring_pitch = 0.86 * p; L->dot = 0.2 * p; L->ray_width = 0.2 * p; L->long_len = 2.2 * p; L->short_len = 1.0 * p;
1033 L->dial_sample = 1.6 * p; L->ring_key_span = 16; L->format = CKEY_SCALABLE_FORMAT_VERSION;
1034 } else {
1035 L->rings = kScalablePrintRings[i]; L->ring_pitch = 1.0 * p;
1036 L->dial_slots = equal_arc_slots(kScalableDialInner, p);
1037 for (int k = 0; k < L->rings; ++k) L->ring_slots.push_back(equal_arc_slots(L->ring_radius(k), p));
1038 L->dot = 0.3 * p; L->ray_width = 0.35 * p; L->long_len = 2.4 * p; L->short_len = 1.0 * p;
1039 L->dial_sample = 1.7 * p; L->ring_key_span = 8; L->format = CKEY_SCALABLE_PRINT_FORMAT_VERSION;
1040 if (v == 1) L->row0 = 9; // its longer rays need the v1 Grid Key one row higher for a pitch of clearance
1041 }
1042 L->ring_stride = *std::max_element(L->ring_slots.begin(), L->ring_slots.end());
1043 L->geom = scalable_geometry(L->col0, L->row0, p, L->dial_slots, kScalableDialInner + L->long_len + L->ray_width / 2);
1044 for (int row = 0; row < L->grid; ++row) for (int col = 0; col < L->grid; ++col) {
1045 const double x = (col + .5) * p, y = (row + .5) * p;
1046 if (dense_site_margin(L->geom, x, y) <= 0.0) continue;
1047 L->nodes.push_back({0, x, y, -1, -1, site_identity(0, static_cast<uint32_t>(row), static_cast<uint32_t>(col))});
1048 }
1049 for (int slot = 0; slot < L->dial_slots; ++slot)
1050 if (!L->reserved_ray(slot)) L->nodes.push_back({1, 0, 0, -1, slot, site_identity(1, 0, static_cast<uint32_t>(slot))});
1051 const int key = L->ring_key_slot();
1052 for (int ring = 0; ring < L->rings; ++ring) {
1053 const int S = L->ring_slots[static_cast<size_t>(ring)];
1054 for (int slot = 0; slot < S; ++slot) {
1055 // Standard family: ring slots are also cleared on the Ray Key bearings (inherited from Profile 2).
1056 if ((family == 0 && L->reserved_ray(slot)) || (ring == L->rings - 1 && slot >= key && slot < key + L->ring_key_span)) continue;
1057 const double r = L->ring_radius(ring), a = kTau * slot / S;
1058 L->nodes.push_back({2, kCenter + r * std::sin(a), kCenter - r * std::cos(a), ring, slot,
1059 site_identity(2, static_cast<uint32_t>(ring), static_cast<uint32_t>(slot))});
1060 }
1061 }
1062 const uint32_t placement = family == 0 ? 0x434b5030u : 0x434b5031u; // "CKP0" / "CKP1"
1063 const uint32_t whitening = family == 0 ? 0x434b5730u : 0x434b5731u; // "CKW0" / "CKW1"
1064 order_sites(L->nodes, site_hash(placement ^ static_cast<uint32_t>(v)));
1065 L->white = whitening_bits(whitening + static_cast<uint32_t>(v), L->nodes.size());
1066 L->codeword_bytes = L->nodes.size() / 8;
1067 L->ring_grid.assign(static_cast<size_t>(L->rings) * L->ring_stride, -1);
1068 for (size_t n = 0; n < L->nodes.size(); ++n)
1069 if (L->nodes[n].kind == 2) L->ring_grid[static_cast<size_t>(L->nodes[n].ring) * L->ring_stride + L->nodes[n].slot] = static_cast<int>(n);
1070 return L;
1071}
1072
1073const ScalableLayout &scalable_layout(int v, int family = 0) {
1074 static std::array<std::once_flag, kScalableVersions * kScalableFamilies> once;
1075 static std::array<std::unique_ptr<ScalableLayout>, kScalableVersions * kScalableFamilies> cache;
1076 const size_t i = static_cast<size_t>(family * kScalableVersions + v - 1);
1077 std::call_once(once[i], [&] { cache[i] = build_scalable_layout(v, family); });
1078 return *cache[i];
1079}
1080
1081struct RsBlock { size_t n, k; };
1082
1083// The codeword is split into ceil(C/255) near-equal RS blocks (longer ones
1084// first); each keeps 2*round(pct*n/200) parity bytes (integer arithmetic).
1085std::vector<RsBlock> scalable_blocks(size_t codeword_bytes, int level) {
1086 std::vector<RsBlock> blocks;
1087 const size_t count = (codeword_bytes + 254) / 255;
1088 for (size_t b = 0; b < count; ++b) {
1089 const size_t n = codeword_bytes / count + (b < codeword_bytes % count ? 1 : 0);
1090 const size_t parity = std::max<size_t>(2, 2 * ((static_cast<size_t>(kScalableParityPercent[static_cast<size_t>(level)]) * n + 100) / 200));
1091 blocks.push_back({n, n - std::min(parity, n - 1)});
1092 }
1093 return blocks;
1094}
1095
1096size_t scalable_data_bytes(size_t codeword_bytes, int level) {
1097 size_t k = 0; for (const auto &b : scalable_blocks(codeword_bytes, level)) k += b.k; return k;
1098}
1099
1100size_t scalable_capacity(int v, int level, int family = 0) {
1101 if (v < 1 || v > kScalableVersions || level < 0 || level > 3 || family < 0 || family >= kScalableFamilies) return 0;
1102 const size_t k = scalable_data_bytes(scalable_layout(v, family).codeword_bytes, level);
1103 return k > kScalableOverheadBytes ? std::min<size_t>(k - kScalableOverheadBytes, 65535) : 0;
1104}
1105
1106bool scalable_site_value(const ScalableLayout &L, const ckey_scalable_symbol *s, size_t i) {
1107 const bool data = i < L.codeword_bytes * 8 && ((s->codeword[i / 8] >> (7 - i % 8)) & 1u) != 0;
1108 return data != (L.white[i] != 0);
1109}
1110
1111// Contrast/agreement fit of fixed samples (marks expected printed, empties
1112// expected clear); invalid if any sample leaves the image.
1113KeyFit sample_fit(const std::vector<double> &marks, const std::vector<double> &empty) {
1114 if (marks.empty() || empty.empty() || std::any_of(marks.begin(), marks.end(), [](double v) { return v < 0; }) ||
1115 std::any_of(empty.begin(), empty.end(), [](double v) { return v < 0; })) return {};
1116 const double mark_mean = std::accumulate(marks.begin(), marks.end(), 0.0) / marks.size();
1117 const double empty_mean = std::accumulate(empty.begin(), empty.end(), 0.0) / empty.size();
1118 const bool dark = mark_mean < empty_mean; const double threshold = (mark_mean + empty_mean) * .5;
1119 const auto marked = [&](double v) { return dark ? v < threshold : v > threshold; };
1120 const size_t evidence = std::count_if(marks.begin(), marks.end(), marked) +
1121 std::count_if(empty.begin(), empty.end(), [&](double v) { return !marked(v); });
1122 return {true, std::abs(mark_mean - empty_mean), static_cast<double>(evidence) / static_cast<double>(marks.size() + empty.size())};
1123}
1124
1125// Version- and style-independent skeleton: the frame stroke and both arms of
1126// all four finders, sampled near the arm ends (common to every finder style:
1127// arc, pill, squircle, bracket), against the frame moat and the outer quiet
1128// margin. It is symmetric under the 8 orientations on purpose: finder styles
1129// change the top-left split's shape, and a logo may occupy the centre, so
1130// orientation comes from the asymmetric Grid, Ring, and Ray Keys instead.
1131KeyFit scalable_skeleton_fit(const uint8_t *gray, size_t width, size_t height, size_t stride, const double h[8]) {
1132 std::vector<double> marks, empty;
1133 for (const auto &[x, y] : {std::pair{14.5, 0.5}, {28.5, 14.5}, {14.5, 28.5}, {0.5, 14.5}, {8.0, 0.5}, {21.0, 0.5}, {0.5, 21.0}, {28.5, 8.0}})
1134 marks.push_back(gray_sample(gray, width, height, stride, h, x, y));
1135 // Arm points at 198 and 252 degrees of the canonical arc (radius 2.3 about
1136 // the corner inset 4), mirrored into each corner.
1137 const double arm[2][2] = {{2.3 * std::cos(kTau * 198.0 / 360.0), 2.3 * std::sin(kTau * 198.0 / 360.0)},
1138 {2.3 * std::cos(kTau * 252.0 / 360.0), 2.3 * std::sin(kTau * 252.0 / 360.0)}};
1139 for (const auto &[cx, cy, mx, my] : {std::tuple{4.0, 4.0, 1.0, 1.0}, {25.0, 4.0, -1.0, 1.0}, {4.0, 25.0, 1.0, -1.0}, {25.0, 25.0, -1.0, -1.0}})
1140 for (const auto &o : arm) marks.push_back(gray_sample(gray, width, height, stride, h, cx + mx * o[0], cy + my * o[1]));
1141 // Frame moat (payload ink starts at least 0.825 + 0.375 from each edge)
1142 // and the mandatory outer quiet margin (-1..0).
1143 for (const auto &[x, y] : {std::pair{14.5, 1.0}, {28.0, 14.5}, {14.5, 28.0}, {1.0, 14.5},
1144 {14.5, -0.4}, {29.4, 14.5}, {14.5, 29.4}, {-0.4, 14.5}})
1145 empty.push_back(gray_sample(gray, width, height, stride, h, x, y, 0.05));
1146 return sample_fit(marks, empty);
1147}
1148
1149// Version-specific keys at the version's own module and slot pitch: the 2x2
1150// Grid Key on the payload lattice, the Ring Key's dot/gap/run pattern on the
1151// outermost ring, and the three Ray Keys. A wrong version misses them.
1152KeyFit scalable_version_fit(const ScalableLayout &L, const uint8_t *gray, size_t width, size_t height, size_t stride, const double h[8]) {
1153 const double p = L.pitch, rk = L.ring_radius(L.rings - 1), S = L.ring_slots.back(), D = L.dial_slots, ds = 0.25 * L.dot;
1154 std::vector<double> marks, empty;
1155 for (int r = 0; r < 2; ++r) for (int c = 0; c < 2; ++c)
1156 marks.push_back(gray_sample(gray, width, height, stride, h, (L.col0 + c + .5) * p, (L.row0 + r + .5) * p, 0.12 * p));
1157 const int k = L.ring_key_slot();
1158 for (double slot : L.ring_key_marks()) marks.push_back(polar_sample_slots(gray, width, height, stride, h, kCenter, rk, k + slot, S, ds));
1159 marks.push_back(polar_sample_slots(gray, width, height, stride, h, kCenter, kScalableDialInner + 3.0 * p, 0, D, 0.04 * p));
1160 marks.push_back(polar_sample_slots(gray, width, height, stride, h, kCenter, kScalableDialInner + 1.3 * p, L.ray_key_half(), D, 0.04 * p));
1161 marks.push_back(polar_sample_slots(gray, width, height, stride, h, kCenter, kScalableDialInner + 2.3 * p, L.ray_key_three(), D, 0.04 * p));
1162 empty.push_back(gray_sample(gray, width, height, stride, h, (L.col0 - 1 + .5) * p, (L.row0 + .5) * p, 0.12 * p));
1163 for (double slot : L.ring_key_empties()) empty.push_back(polar_sample_slots(gray, width, height, stride, h, kCenter, rk, k + slot, S, ds));
1164 empty.push_back(polar_sample_slots(gray, width, height, stride, h, kCenter, kScalableDialInner + 2.6 * p, L.ray_key_half(), D, 0.04 * p));
1165 return sample_fit(marks, empty);
1166}
1167
1168void orientation_homography(const double quad[8], int reverse, int start, double h[8], bool &ok) {
1169 constexpr double canonical[8] = {0, 0, 29, 0, 29, 29, 0, 29};
1170 double dst[8];
1171 for (int i = 0; i < 4; ++i) { const int q = (start + (reverse ? -i : i) + 8) % 4; dst[2 * i] = quad[2 * q]; dst[2 * i + 1] = quad[2 * q + 1]; }
1172 ok = solve_homography(canonical, dst, h);
1173}
1174
1175// Sub-module alignment from the frame stroke's two edges. For points along
1176// the straight middle of all four sides, compare samples just inside the
1177// stroke with samples just outside it, at both its outer (0.175) and inner
1178// (0.825) edge. The sum peaks sharply when every edge is exactly aligned and,
1179// averaged over 64 points per edge, resolves well below a module even at
1180// Profile 0's finest pitch. The frame is symmetric, so no orientation search.
1181// eps_px is the half-separation of each edge's sample pair, in pixels. The
1182// score is flat within about +/-eps of alignment, so callers shrink eps with
1183// their search step (coarse-to-fine): wide to capture, sub-pixel to finish.
1184double frame_edge_score(const uint8_t *gray, size_t width, size_t height, size_t stride, const double quad[8], double eps_px) {
1185 constexpr double canonical[8] = {0, 0, 29, 0, 29, 29, 0, 29};
1186 double h[8]; if (!solve_homography(canonical, quad, h)) return 0;
1187 const double side_px = (std::hypot(quad[2] - quad[0], quad[3] - quad[1]) + std::hypot(quad[6] - quad[0], quad[7] - quad[1])) / 2;
1188 const double eps = std::clamp(eps_px * 29.0 / std::max(side_px, 1.0), 0.004, 0.3);
1189 double centre = 0, clear = 0, edges = 0; int n = 0;
1190 for (int side = 0; side < 4; ++side) for (int i = 0; i < 16; ++i) {
1191 const double t = 5.0 + 19.0 * i / 15.0;
1192 // Point on the stroke centreline (inset 0.5) and outward normal.
1193 double x, y, nx, ny;
1194 if (side == 0) { x = t; y = 0.5; nx = 0; ny = -1; }
1195 else if (side == 1) { x = 28.5; y = t; nx = 1; ny = 0; }
1196 else if (side == 2) { x = 29 - t; y = 28.5; nx = 0; ny = 1; }
1197 else { x = 0.5; y = 29 - t; nx = -1; ny = 0; }
1198 const auto at = [&](double d) { return gray_sample(gray, width, height, stride, h, x + nx * d, y + ny * d, 0.0); };
1199 const double c = at(0), out_in = at(0.325 - eps), out_out = at(0.325 + eps), in_in = at(-0.325 + eps), in_out = at(-0.325 - eps);
1200 if (c < 0 || out_in < 0 || out_out < 0 || in_in < 0 || in_out < 0) return 0;
1201 centre += c; clear += (out_out + in_out) / 2; edges += (out_in - out_out) + (in_in - in_out); ++n;
1202 }
1203 const double polarity = centre > clear ? 1.0 : -1.0; // light-on-dark or dark-on-light
1204 return std::max(0.0, polarity * edges / n);
1205}
1206
1207double scalable_skeleton_score(const uint8_t *gray, size_t width, size_t height, size_t stride, const double quad[8]) {
1208 double best = 0;
1209 for (int reverse = 0; reverse < 2; ++reverse) for (int start = 0; start < 4; ++start) {
1210 double h[8]; bool ok; orientation_homography(quad, reverse, start, h, ok); if (!ok) continue;
1211 const KeyFit fit = scalable_skeleton_fit(gray, width, height, stride, h);
1212 if (fit.valid) best = std::max(best, fit.contrast * fit.evidence);
1213 }
1214 return best;
1215}
1216
1217// Combined skeleton + version-key score; the version terms dominate once the
1218// skeleton is aligned, which is what pins the module pitch.
1219double scalable_version_score(const ScalableLayout &L, const uint8_t *gray, size_t width, size_t height, size_t stride, const double quad[8]) {
1220 double best = 0;
1221 for (int reverse = 0; reverse < 2; ++reverse) for (int start = 0; start < 4; ++start) {
1222 double h[8]; bool ok; orientation_homography(quad, reverse, start, h, ok); if (!ok) continue;
1223 const KeyFit skeleton = scalable_skeleton_fit(gray, width, height, stride, h);
1224 const KeyFit keys = scalable_version_fit(L, gray, width, height, stride, h);
1225 if (skeleton.valid && keys.valid) best = std::max(best, skeleton.contrast * skeleton.evidence + 2.0 * keys.contrast * keys.evidence * keys.evidence);
1226 }
1227 return best;
1228}
1229
1230int best_scalable_version(const uint8_t *gray, size_t width, size_t height, size_t stride, const double quad[8], double &score, int *family = nullptr) {
1231 int best_v = 0, best_f = 0; score = 0;
1232 for (int f = 0; f < kScalableFamilies; ++f) for (int v = 1; v <= kScalableVersions; ++v) {
1233 const double s = scalable_version_score(scalable_layout(v, f), gray, width, height, stride, quad);
1234 if (s > score) { score = s; best_v = v; best_f = f; }
1235 }
1236 if (family) *family = best_f;
1237 return best_v;
1238}
1239
1240std::string fixed4(double v) { char b[32]; std::snprintf(b, sizeof(b), "%.4f", v); return b; }
1241
1242} // namespace
1243
1244
1245
1246namespace {
1247
1248std::string hex_colour(ckey_rgb c) { char b[8]; std::snprintf(b, sizeof(b), "#%02x%02x%02x", c.r, c.g, c.b); return b; }
1249bool same_colour(ckey_rgb a, ckey_rgb b) { return a.r == b.r && a.g == b.g && a.b == b.b; }
1250
1251// WCAG relative luminance and contrast ratio: the reader decodes luminance,
1252// so every ink colour must stand clear of every background colour.
1253double relative_luminance(ckey_rgb c) {
1254 const auto channel = [](uint8_t v) { const double x = v / 255.0; return x <= 0.04045 ? x / 12.92 : std::pow((x + 0.055) / 1.055, 2.4); };
1255 return 0.2126 * channel(c.r) + 0.7152 * channel(c.g) + 0.0722 * channel(c.b);
1256}
1257double contrast_ratio(ckey_rgb a, ckey_rgb b) {
1258 const double la = relative_luminance(a), lb = relative_luminance(b);
1259 return (std::max(la, lb) + 0.05) / (std::min(la, lb) + 0.05);
1260}
1261
1262std::string xml_escape(const char *text) {
1263 std::string out;
1264 for (const char *c = text; *c; ++c) {
1265 if (*c == '&') out += "&amp;"; else if (*c == '<') out += "&lt;"; else if (*c == '>') out += "&gt;";
1266 else if (*c == '"') out += "&quot;"; else out += *c;
1267 }
1268 return out;
1269}
1270
1271// The empty centre (inside ring 0's ink) holds a logo without hiding marks.
1272double logo_quiet_radius(const ScalableLayout &L) { return kScalableRingInner - L.dot - 0.15; }
1273// Keep the outermost ring (which carries the Ring Key) fully visible.
1274double logo_max_radius(const ScalableLayout &L) { return L.ring_radius(L.rings - 1) - L.dot - 0.25; }
1275
1276double logo_load(const ScalableLayout &L, int level, double radius) {
1277 if (radius <= logo_quiet_radius(L)) return 0.0;
1278 const auto blocks = scalable_blocks(L.codeword_bytes, level);
1279 std::vector<size_t> block_of(L.codeword_bytes); size_t pos = 0;
1280 for (size_t j = 0; j < blocks.front().n; ++j) for (size_t b = 0; b < blocks.size(); ++b) if (j < blocks[b].n) block_of[pos++] = b;
1281 std::vector<uint8_t> hidden(L.codeword_bytes, 0);
1282 for (size_t i = 0; i < L.codeword_bytes * 8; ++i) {
1283 const auto &n = L.nodes[i];
1284 if (n.kind != 2) continue; // only ring marks can lie under an allowed logo
1285 if (std::hypot(n.x - kCenter, n.y - kCenter) - L.dot <= radius + 0.05) hidden[i / 8] = 1;
1286 }
1287 std::vector<size_t> per_block(blocks.size(), 0);
1288 for (size_t byte = 0; byte < hidden.size(); ++byte) per_block[block_of[byte]] += hidden[byte];
1289 double worst = 0;
1290 for (size_t b = 0; b < blocks.size(); ++b) worst = std::max(worst, per_block[b] / std::max(1.0, (blocks[b].n - blocks[b].k) / 2.0));
1291 return worst;
1292}
1293
1294// The default style (spec §4: black on white). Shared so that libraries
1295// other than ckey_render (the .ckey reader in ckey_codec) need not link it.
1296void fill_default_style(ckey_style &st) {
1297 std::memset(&st, 0, sizeof(st));
1298 st.background = st.background_edge = {0xff, 0xff, 0xff};
1299 st.ink = st.ink_shade = {0, 0, 0};
1300 st.modules = CKEY_MODULE_ROUNDED; st.rings = CKEY_RING_JOINED; st.rays = CKEY_RAY_ROUND;
1301 st.policy = CKEY_POLICY_STRICT;
1302}
1303
1304// Values a renderer cannot draw at all, whatever the policy.
1305std::string structural_problem(const ScalableLayout &L, const ckey_style &st) {
1306 const auto finite01 = [](double v) { return std::isfinite(v) && v >= 0 && v <= 1; };
1307 // A caller can store any integer in an enum field. Read the raw bytes so an
1308 // out-of-range value is refused without loading it as the enum type.
1309 const auto raw = [](const auto &field) {
1310 using T = std::remove_cvref_t<decltype(field)>;
1311 if constexpr (std::is_enum_v<T>) {
1312 std::underlying_type_t<T> v;
1313 std::memcpy(&v, &field, sizeof v);
1314 return static_cast<long long>(v);
1315 } else {
1316 return static_cast<long long>(field);
1317 }
1318 };
1319 if (raw(st.policy) < CKEY_POLICY_STRICT || raw(st.policy) > CKEY_POLICY_OVERRIDE) return "unknown style policy";
1320 if (raw(st.modules) < CKEY_MODULE_ROUNDED || raw(st.modules) > CKEY_MODULE_DIAMOND) return "unknown module shape";
1321 if (raw(st.rings) < CKEY_RING_JOINED || raw(st.rings) > CKEY_RING_DOTS) return "unknown ring style";
1322 if (raw(st.rays) < CKEY_RAY_ROUND || raw(st.rays) > CKEY_RAY_FLAT) return "unknown ray cap";
1323 if (st.accent_count > 4 || st.accent_percent > 100) return "accents: at most 4 colours and 100%";
1324 if (!finite01(st.bevel) || !finite01(st.shadow) || !finite01(st.texture)) return "bevel, shadow, and texture must be 0..1";
1325 if (!std::isfinite(st.logo_radius) || st.logo_radius < 0) return "logo radius must be 0 or positive";
1326 if (st.logo_href && *st.logo_href && st.logo_radius > 14.5) return "logo radius must be at most 14.5 units";
1327 (void)L;
1328 return {};
1329}
1330
1331// Scan-safety rules. Only what reliably breaks a code is a hard refusal:
1332// near-invisible marks (any ink or accent below kHardContrast against a
1333// background), mixed polarity, and logos that hide too much. Lower contrast
1334// and strong depth are warnings: the photo sweep in ckey_certify decides
1335// whether such a style scans, and it often does.
1336constexpr double kHardContrast = 1.5;
1337constexpr double kAdviseContrast = 3.0;
1338
1339std::string safety_problem(const ScalableLayout &L, const ckey_scalable_symbol &sym, const ckey_style &st,
1340 const std::vector<ckey_rgb> &extra_backgrounds, double &min_contrast, double &load,
1341 std::string *warnings = nullptr) {
1342 min_contrast = 1e9; load = 0;
1343 std::vector<ckey_rgb> inks = {st.ink, st.ink_shade};
1344 if (st.accent_percent > 0) for (uint32_t i = 0; i < st.accent_count; ++i) inks.push_back(st.accents[i]);
1345 std::vector<ckey_rgb> backgrounds = {st.background, st.background_edge};
1346 backgrounds.insert(backgrounds.end(), extra_backgrounds.begin(), extra_backgrounds.end());
1347 int polarity = 0; std::string problem, advice;
1348 for (const auto &bg : backgrounds) for (const auto &ink : inks) {
1349 const double ratio = contrast_ratio(ink, bg);
1350 min_contrast = std::min(min_contrast, ratio);
1351 char why[112];
1352 if (ratio < kHardContrast && problem.empty()) { std::snprintf(why, sizeof(why), "ink %s on background %s is %.1f:1, too faint to read (minimum %.1f:1)", hex_colour(ink).c_str(), hex_colour(bg).c_str(), ratio, kHardContrast); problem = why; }
1353 else if (ratio < kAdviseContrast && advice.empty()) { std::snprintf(why, sizeof(why), "ink %s on background %s is only %.1f:1", hex_colour(ink).c_str(), hex_colour(bg).c_str(), ratio); advice = why; }
1354 const int side = relative_luminance(ink) > relative_luminance(bg) ? 1 : -1;
1355 if (polarity && side != polarity && problem.empty()) problem = "all inks must be lighter than the background, or all darker";
1356 polarity = side;
1357 }
1358 if (polarity < 0 && st.shadow > 0.4 && advice.empty()) advice = "strong shadow on dark-on-light marks";
1359 if (polarity < 0 && st.bevel > 0.5 && advice.empty()) advice = "strong bevel on dark-on-light marks";
1360 if (warnings) *warnings = advice;
1361 if (!problem.empty()) return problem;
1362 if (st.logo_href && *st.logo_href) {
1363 const double radius = st.logo_radius > 0 ? st.logo_radius : logo_quiet_radius(L);
1364 char why[96];
1365 if (radius > logo_max_radius(L)) { std::snprintf(why, sizeof(why), "logo radius %.2f exceeds %.2f (it would hide the Ring Key)", radius, logo_max_radius(L)); return why; }
1366 if (radius > logo_quiet_radius(L) && !st.logo_plate) return "a logo larger than the empty centre needs a plate";
1367 load = logo_load(L, static_cast<int>(sym.ecc_level), radius);
1368 if (load > 0.5) { std::snprintf(why, sizeof(why), "logo hides %.0f%% of a block's correction (max 50%%); raise the level or shrink it", 100 * load); return why; }
1369 }
1370 return {};
1371}
1372
1373// Policy-aware check. STRICT and ADAPTIVE styles must pass the safety rules
1374// (renderers adapt an ADAPTIVE style first, see effective_style); OVERRIDE
1375// skips them: the caller has explicitly accepted an uncertified symbol.
1376std::string check_style(const ScalableLayout &L, const ckey_scalable_symbol &sym, const ckey_style &st, double &min_contrast, double &load) {
1377 min_contrast = 0; load = 0;
1378 std::string problem = structural_problem(L, st);
1379 if (!problem.empty()) return problem;
1380 problem = safety_problem(L, sym, st, {}, min_contrast, load);
1381 return st.policy == CKEY_POLICY_OVERRIDE ? std::string() : problem;
1382}
1383
1384// ---- Adaptive policy: rule-based repairs, each reported in a bitmask ----
1385
1386ckey_rgb best_ink_for(const std::vector<ckey_rgb> &backgrounds) {
1387 double black = 1e9, white = 1e9;
1388 for (const auto &bg : backgrounds) { black = std::min(black, contrast_ratio({0, 0, 0}, bg)); white = std::min(white, contrast_ratio({255, 255, 255}, bg)); }
1389 return black >= white ? ckey_rgb{0, 0, 0} : ckey_rgb{255, 255, 255};
1390}
1391
1392uint32_t adapt_style(const ScalableLayout &L, const ckey_scalable_symbol &sym, ckey_style &st, const std::vector<ckey_rgb> &extra_backgrounds) {
1393 uint32_t changed = 0;
1394 std::vector<ckey_rgb> backgrounds = {st.background, st.background_edge};
1395 backgrounds.insert(backgrounds.end(), extra_backgrounds.begin(), extra_backgrounds.end());
1396 const auto ink_ok = [&](ckey_rgb ink, int &side) {
1397 for (const auto &bg : backgrounds) {
1398 if (contrast_ratio(ink, bg) < 3.0) return false;
1399 const int s = relative_luminance(ink) > relative_luminance(bg) ? 1 : -1;
1400 if (side && s != side) return false;
1401 side = s;
1402 }
1403 return true;
1404 };
1405 int side = 0;
1406 if (!ink_ok(st.ink, side) || !ink_ok(st.ink_shade, side)) {
1407 st.ink = st.ink_shade = best_ink_for(backgrounds);
1408 changed |= CKEY_ADJUST_INK; side = 0;
1409 if (!ink_ok(st.ink, side)) { // no ink can work on these backgrounds: give the symbol its own ground
1410 st.background = st.background_edge = st.ink.r ? ckey_rgb{0, 0, 0} : ckey_rgb{255, 255, 255};
1411 backgrounds = {st.background};
1412 changed |= CKEY_ADJUST_BACKGROUND; side = 0; ink_ok(st.ink, side);
1413 }
1414 }
1415 if (st.accent_percent > 0 && st.accent_count > 0) {
1416 int s = side; bool ok = true;
1417 for (uint32_t i = 0; i < st.accent_count; ++i) { int t = s; ok = ok && ink_ok(st.accents[i], t); }
1418 if (!ok) { st.accent_percent = 0; st.accent_count = 0; changed |= CKEY_ADJUST_ACCENTS; }
1419 }
1420 if (side < 0 && (st.shadow > 0.4 || st.bevel > 0.5)) { st.shadow = std::min(st.shadow, 0.4); st.bevel = std::min(st.bevel, 0.5); changed |= CKEY_ADJUST_EFFECTS; }
1421 if (st.logo_href && *st.logo_href) {
1422 double radius = st.logo_radius > 0 ? st.logo_radius : logo_quiet_radius(L);
1423 if (radius > logo_quiet_radius(L) && !st.logo_plate) { st.logo_plate = 1; changed |= CKEY_ADJUST_LOGO; }
1424 const double original = radius;
1425 radius = std::min(radius, logo_max_radius(L));
1426 while (radius > logo_quiet_radius(L) && logo_load(L, static_cast<int>(sym.ecc_level), radius) > 0.5) radius -= 0.05;
1427 radius = std::max(radius, logo_quiet_radius(L));
1428 if (radius < original - 1e-9) { st.logo_radius = radius; changed |= CKEY_ADJUST_LOGO; }
1429 }
1430 return changed;
1431}
1432
1433// The style a renderer draws: an ADAPTIVE style after its rule-based repairs.
1434ckey_style effective_style(const ScalableLayout &L, const ckey_scalable_symbol &sym, const ckey_style &st) {
1435 ckey_style out = st;
1436 double contrast = 0, load = 0;
1437 if (st.policy == CKEY_POLICY_ADAPTIVE && structural_problem(L, st).empty() && !safety_problem(L, sym, st, {}, contrast, load).empty())
1438 adapt_style(L, sym, out, {});
1439 return out;
1440}
1441
1442void emit_module(std::ostringstream &o, double cx, double cy, double p, ckey_module_shape shape, const std::string &colour) {
1443 const std::string fill = colour.empty() ? "" : " fill=\"" + colour + "\"";
1444 const double h = 0.34 * p;
1445 switch (shape) {
1446 case CKEY_MODULE_CIRCLE: o << "<circle cx=\"" << cx << "\" cy=\"" << cy << "\" r=\"" << h << "\" stroke=\"none\"" << fill << "/>"; break;
1447 case CKEY_MODULE_DIAMOND: {
1448 const double d = 0.40 * p; // inscribed radius 0.28p covers the sample support
1449 o << "<polygon points=\"" << cx << ',' << cy - d << ' ' << cx + d << ',' << cy << ' ' << cx << ',' << cy + d << ' ' << cx - d << ',' << cy << "\" stroke=\"none\"" << fill << "/>"; break;
1450 }
1451 default:
1452 o << "<rect x=\"" << cx - h << "\" y=\"" << cy - h << "\" width=\"" << 2 * h << "\" height=\"" << 2 * h << "\" rx=\""
1453 << (shape == CKEY_MODULE_SQUARE ? 0.0 : 0.16 * p) << "\" stroke=\"none\"" << fill << "/>";
1454 }
1455}
1456
1457// Deterministic accent choice per site (decorative; luminance is checked).
1458int accent_of(uint32_t id, const ckey_style &st) {
1459 if (!st.accent_count || !st.accent_percent) return -1;
1460 const uint32_t h = site_hash(id ^ 0x41434345u); // "ACCE"
1461 return (h % 100) < st.accent_percent ? static_cast<int>((h / 100) % st.accent_count) : -1;
1462}
1463
1464} // namespace
1465
1466
1467
1468
1469// ---------------------------------------------------------------------------
1470// Full-frame localization (moved from the iPhone reader so it is shared and
1471// testable). Border candidates are connected components of the continuous
1472// frame stroke; each is fitted with a perspective quadrilateral, then refined
1473// against a profile's fixed keys. Neither step can accept a payload.
1474// ---------------------------------------------------------------------------
1475namespace {
1476
1477struct Point2 { double x, y; };
1478
1479uint8_t frame_threshold(const uint8_t *gray, size_t width, size_t height, size_t stride, bool dark_marks) {
1480 std::array<size_t, 256> histogram{}; size_t samples = 0;
1481 for (size_t y = 0; y < height; y += 8) for (size_t x = 0; x < width; x += 8) { ++histogram[gray[y * stride + x]]; ++samples; }
1482 if (!samples) return dark_marks ? 92 : 164;
1483 const auto percentile = [&](double fraction) {
1484 const size_t target = static_cast<size_t>(static_cast<double>(samples - 1) * fraction); size_t total = 0;
1485 for (int v = 0; v < 256; ++v) { total += histogram[v]; if (total > target) return v; }
1486 return 255;
1487 };
1488 const int low = percentile(0.10), high = percentile(0.90);
1489 if (high - low < 32) return dark_marks ? 92 : 164;
1490 const double contrast = high - low;
1491 const double value = dark_marks ? low + contrast * 0.32 : high - contrast * 0.32;
1492 return static_cast<uint8_t>(std::clamp(static_cast<int>(std::lround(value)), 0, 255));
1493}
1494
1495double cross(const Point2 &o, const Point2 &a, const Point2 &b) { return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x); }
1496
1497std::vector<Point2> convex_hull(std::vector<Point2> p) {
1498 std::sort(p.begin(), p.end(), [](const Point2 &a, const Point2 &b) { return a.x < b.x || (a.x == b.x && a.y < b.y); });
1499 p.erase(std::unique(p.begin(), p.end(), [](const Point2 &a, const Point2 &b) { return a.x == b.x && a.y == b.y; }), p.end());
1500 if (p.size() < 3) return p;
1501 std::vector<Point2> h(2 * p.size()); size_t k = 0;
1502 for (size_t i = 0; i < p.size(); ++i) { while (k >= 2 && cross(h[k - 2], h[k - 1], p[i]) <= 0) --k; h[k++] = p[i]; }
1503 for (size_t i = p.size() - 1, t = k + 1; i-- > 0;) { while (k >= t && cross(h[k - 2], h[k - 1], p[i]) <= 0) --k; h[k++] = p[i]; }
1504 h.resize(k - 1);
1505 return h;
1506}
1507
1508// Fits the outer edge of a square border component. Second moments cannot
1509// orient a square (its inertia is isotropic, so the old principal-axis fit
1510// returned an essentially random angle, often 45 degrees off). The minimum-
1511// area enclosing rectangle of the convex hull gives the orientation; each
1512// side is then re-fitted as a line through the stroke's outer edge, so a
1513// tilted (keystoned) display yields a true perspective quadrilateral.
1514bool fit_border_quad(const std::vector<Point2> &points, double step, std::array<double, 8> &quad) {
1515 const auto hull = convex_hull(points);
1516 if (hull.size() < 4) return false;
1517 double best_area = std::numeric_limits<double>::infinity(), ux = 1, uy = 0;
1518 for (size_t i = 0; i < hull.size(); ++i) {
1519 const Point2 &a = hull[i], &b = hull[(i + 1) % hull.size()];
1520 double ex = b.x - a.x, ey = b.y - a.y; const double len = std::hypot(ex, ey);
1521 if (len < 1e-9) continue;
1522 ex /= len; ey /= len;
1523 double min_u = 1e300, max_u = -1e300, min_v = 1e300, max_v = -1e300;
1524 for (const auto &p : hull) {
1525 const double u = p.x * ex + p.y * ey, v = -p.x * ey + p.y * ex;
1526 min_u = std::min(min_u, u); max_u = std::max(max_u, u); min_v = std::min(min_v, v); max_v = std::max(max_v, v);
1527 }
1528 const double area = (max_u - min_u) * (max_v - min_v);
1529 if (area < best_area) { best_area = area; ux = ex; uy = ey; }
1530 }
1531 const double vx = -uy, vy = ux;
1532 double cx = 0, cy = 0; for (const auto &p : points) { cx += p.x; cy += p.y; } cx /= points.size(); cy /= points.size();
1533 double min_u = 1e300, max_u = -1e300, min_v = 1e300, max_v = -1e300;
1534 for (const auto &p : points) {
1535 const double u = (p.x - cx) * ux + (p.y - cy) * uy, v = (p.x - cx) * vx + (p.y - cy) * vy;
1536 min_u = std::min(min_u, u); max_u = std::max(max_u, u); min_v = std::min(min_v, v); max_v = std::max(max_v, v);
1537 }
1538 const double half_u = (max_u - min_u) / 2, half_v = (max_v - min_v) / 2, mid_u = (max_u + min_u) / 2, mid_v = (max_v + min_v) / 2;
1539 // Side lines: normal n (outward), offset d, so that n . p = d on the edge.
1540 struct Line { double nx, ny, d; };
1541 std::array<Line, 4> lines{};
1542 const std::array<std::array<double, 2>, 4> normals = {{{-vx, -vy}, {ux, uy}, {vx, vy}, {-ux, -uy}}}; // top, right, bottom, left
1543 for (int s = 0; s < 4; ++s) {
1544 const double nx = normals[s][0], ny = normals[s][1];
1545 const bool along_u = s == 0 || s == 2;
1546 const double half_along = along_u ? half_u : half_v, half_across = along_u ? half_v : half_u;
1547 const double band = std::max(3.0 * step, 0.10 * half_across);
1548 std::vector<Point2> side;
1549 for (const auto &p : points) {
1550 const double u = (p.x - cx) * ux + (p.y - cy) * uy - mid_u, v = (p.x - cx) * vx + (p.y - cy) * vy - mid_v;
1551 const double across = along_u ? (s == 0 ? -v : v) : (s == 1 ? u : -u);
1552 const double along = along_u ? u : v;
1553 // Skip the rounded corners: only the straight middle of each side.
1554 if (across > half_across - band && std::abs(along) < 0.62 * half_along) side.push_back(p);
1555 }
1556 Line line{nx, ny, 0};
1557 if (side.size() >= 8) {
1558 double mx = 0, my = 0; for (const auto &p : side) { mx += p.x; my += p.y; } mx /= side.size(); my /= side.size();
1559 double sxx = 0, syy = 0, sxy = 0;
1560 for (const auto &p : side) { sxx += (p.x - mx) * (p.x - mx); syy += (p.y - my) * (p.y - my); sxy += (p.x - mx) * (p.y - my); }
1561 const double theta = 0.5 * std::atan2(2 * sxy, sxx - syy); // direction of the side
1562 double lx = -std::sin(theta), ly = std::cos(theta); // its normal
1563 if (lx * nx + ly * ny < 0) { lx = -lx; ly = -ly; }
1564 if (lx * nx + ly * ny > 0.94) { line.nx = lx; line.ny = ly; } // accept tilt up to ~20 degrees
1565 }
1566 // Outer edge: a high percentile of the outward coordinate of the side's
1567 // points (the whole stroke lies in the band), plus half a sample.
1568 std::vector<double> outward;
1569 for (const auto &p : side.size() >= 8 ? side : points) outward.push_back(p.x * line.nx + p.y * line.ny);
1570 std::sort(outward.begin(), outward.end());
1571 line.d = outward[static_cast<size_t>(0.95 * (outward.size() - 1))] + 0.5 * step;
1572 lines[s] = line;
1573 }
1574 for (int c = 0; c < 4; ++c) { // corners: top-left, top-right, bottom-right, bottom-left
1575 const Line &a = lines[c == 0 ? 3 : c - 1], &b = lines[c];
1576 const double det = a.nx * b.ny - a.ny * b.nx;
1577 if (std::abs(det) < 1e-9) return false;
1578 quad[2 * c] = (a.d * b.ny - a.ny * b.d) / det;
1579 quad[2 * c + 1] = (a.nx * b.d - a.d * b.nx) / det;
1580 }
1581 return std::all_of(quad.begin(), quad.end(), [](double v) { return std::isfinite(v); });
1582}
1583
1584// Candidate ordering only (generated by tools/train_locator_ranker.py).
1585double border_rank(double aspect_error, double fill_ratio, double relative_side) {
1586 const double z = 0.81059192 - 10.65985208 * aspect_error + 0.18755525 * fill_ratio - 0.55068352 * std::abs(relative_side - 0.32);
1587 return 1.0 / (1.0 + std::exp(-z));
1588}
1589
1590// The outer ink edge of the frame stroke sits at canonical 0.175..28.825 in
1591// Profiles 1/2 and 0.7..115.3 in Profile 3: both 1.0122x inside the field.
1592constexpr double kBorderToField = 29.0 / 28.65;
1593
1594
1595} // namespace