Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/zint/backend/qr.c @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
1 /* qr.c Handles QR Code, Micro QR Code, UPNQR and rMQR */
2 /*
3 libzint - the open source barcode library
4 Copyright (C) 2009-2024 Robin Stuart <rstuart114@gmail.com>
5
6 Redistribution and use in source and binary forms, with or without
7 modification, are permitted provided that the following conditions
8 are met:
9
10 1. Redistributions of source code must retain the above copyright
11 notice, this list of conditions and the following disclaimer.
12 2. Redistributions in binary form must reproduce the above copyright
13 notice, this list of conditions and the following disclaimer in the
14 documentation and/or other materials provided with the distribution.
15 3. Neither the name of the project nor the names of its contributors
16 may be used to endorse or promote products derived from this software
17 without specific prior written permission.
18
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
20 ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25 OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26 HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 SUCH DAMAGE.
30 */
31 /* SPDX-License-Identifier: BSD-3-Clause */
32
33 #include <assert.h>
34 #include <math.h>
35 #include <stdio.h>
36 #include "common.h"
37 #include "eci.h"
38 #include "qr.h"
39 #include "reedsol.h"
40
41 #define QR_ALPHA (IS_NUM_F | IS_UPR_F | IS_SPC_F | IS_AST_F | IS_PLS_F | IS_MNS_F | IS_SIL_F | IS_CLI_F)
42
43 #define QR_LEVEL_L 0
44 #define QR_LEVEL_M 1
45 #define QR_LEVEL_Q 2
46 #define QR_LEVEL_H 3
47
48 static const char qr_ecc_level_names[] = { 'L', 'M', 'Q', 'H' };
49
50 #define QR_PERCENT 38 /* Alphanumeric mode % */
51
52 #define RMQR_VERSION 41
53 #define MICROQR_VERSION 73
54
55 /* Returns true if input glyph is in the Alphanumeric set or is GS1 FNC1 */
56 static int qr_is_alpha(const unsigned int glyph, const int gs1) {
57 if (is_chr(QR_ALPHA, glyph)) {
58 return 1;
59 }
60 if (gs1 && glyph == '\x1D') {
61 return 1;
62 }
63 return 0;
64 }
65
66 /* Bits multiplied by this for costs, so as to be whole integer divisible by 2 and 3 */
67 #define QR_MULT 6
68
69 /* Whether in numeric or not. If in numeric, *p_end is set to position after numeric, and *p_cost is set to
70 * per-numeric cost */
71 static int qr_in_numeric(const unsigned int ddata[], const int length, const int in_posn,
72 unsigned int *p_end, unsigned int *p_cost) {
73 int i, digit_cnt;
74
75 if (in_posn < (int) *p_end) {
76 return 1;
77 }
78
79 /* Attempt to calculate the average 'cost' of using numeric mode in number of bits (times QR_MULT) */
80 for (i = in_posn; i < length && i < in_posn + 3 && z_isdigit(ddata[i]); i++);
81
82 digit_cnt = i - in_posn;
83
84 if (digit_cnt == 0) {
85 *p_end = 0;
86 return 0;
87 }
88 *p_end = i;
89 *p_cost = digit_cnt == 1
90 ? 24 /* 4 * QR_MULT */ : digit_cnt == 2 ? 21 /* (7 / 2) * QR_MULT */ : 20 /* (10 / 3) * QR_MULT) */;
91 return 1;
92 }
93
94 /* Whether in alpha or not. If in alpha, *p_end is set to position after alpha, and *p_cost is set to per-alpha cost.
95 * For GS1, *p_pcent set if 2nd char percent */
96 static int qr_in_alpha(const unsigned int ddata[], const int length, const int in_posn,
97 unsigned int *p_end, unsigned int *p_cost, unsigned int *p_pcent, unsigned int *p_pccnt,
98 unsigned int gs1) {
99 const int last = in_posn + 1 == length;
100 int two_alphas;
101
102 /* Attempt to calculate the average 'cost' of using alphanumeric mode in number of bits (times QR_MULT) */
103 if (in_posn < (int) *p_end) {
104 if (gs1) {
105 if (*p_pcent) {
106 /* Previous 2nd char was a percent, so allow for second half of doubled-up percent here */
107 two_alphas = !last && qr_is_alpha(ddata[in_posn + 1], gs1);
108 /* Uneven percents means this will fit evenly in alpha pair */
109 *p_cost = two_alphas || !(*p_pccnt & 1) ? 66 /* 11 * QR_MULT */ : 69 /* (11 / 2 + 6) * QR_MULT */;
110 *p_pcent = 0;
111 } else {
112 /* As above, uneven percents means will fit in alpha pair */
113 *p_cost = !last || !(*p_pccnt & 1) ? 33 /* (11 / 2) * QR_MULT */ : 36 /* 6 * QR_MULT */;
114 }
115 } else {
116 *p_cost = !last ? 33 /* (11 / 2) * QR_MULT */ : 36 /* 6 * QR_MULT */;
117 }
118 return 1;
119 }
120
121 if (!qr_is_alpha(ddata[in_posn], gs1)) {
122 *p_end = 0;
123 *p_pcent = 0;
124 *p_pccnt = 0;
125 return 0;
126 }
127
128 two_alphas = !last && qr_is_alpha(ddata[in_posn + 1], gs1);
129
130 if (gs1 && ddata[in_posn] == '%') { /* Must double-up so counts as 2 chars */
131 *p_end = in_posn + 1;
132 *p_pcent = 0;
133 (*p_pccnt)++;
134 /* Uneven percents means will fit in alpha pair */
135 *p_cost = two_alphas || !(*p_pccnt & 1) ? 66 /* 11 * QR_MULT */ : 69 /* (11 / 2 + 6) * QR_MULT */;
136 return 1;
137 }
138
139 *p_end = two_alphas ? in_posn + 2 : in_posn + 1;
140 if (gs1) {
141 *p_pcent = two_alphas && ddata[in_posn + 1] == '%'; /* 2nd char is percent */
142 *p_pccnt += *p_pcent;
143 /* Uneven percents means will fit in alpha pair */
144 *p_cost = two_alphas || !(*p_pccnt & 1) ? 33 /* (11 / 2) * QR_MULT */ : 36 /* 6 * QR_MULT */;
145 } else {
146 *p_cost = two_alphas ? 33 /* (11 / 2) * QR_MULT */ : 36 /* 6 * QR_MULT */;
147 }
148 return 1;
149 }
150
151 #if 0
152 #define QR_DEBUG_DEFINE_MODE /* For debugging costings */
153 #endif
154
155 /* Indexes into qr_mode_types array (and state array) */
156 #define QR_N 0 /* Numeric */
157 #define QR_A 1 /* Alphanumeric */
158 #define QR_B 2 /* Byte */
159 #define QR_K 3 /* Kanji */
160
161 static const char qr_mode_types[] = { 'N', 'A', 'B', 'K', '\0' }; /* Must be in same order as QR_N etc */
162
163 #define QR_NUM_MODES 4
164
165 /* Indexes into state array (0..3 head costs) */
166 #define QR_VER 4 /* Version */
167 #define QR_N_END 5 /* Numeric end index */
168 #define QR_N_COST 6 /* Numeric cost */
169 #define QR_A_END 7 /* Alpha end index */
170 #define QR_A_COST 8 /* Alpha cost */
171 #define QR_A_PCENT 9 /* Alpha 2nd char percent (GS1-specific) */
172 #define QR_A_PCCNT 10 /* Alpha total percent count (GS1-specific) */
173
174 /* Costs set to this for invalid MICROQR modes for versions M1 and M2.
175 * 128 is the max number of data bits for M4-L (ISO/IEC 18004:2015 Table 7) */
176 #define QR_MICROQR_MAX 774 /* (128 + 1) * QR_MULT */
177
178 /* Initial mode costs */
179 static unsigned int *qr_head_costs(unsigned int state[11]) {
180 static const unsigned int head_costs[7][QR_NUM_MODES] = {
181 /* N A B K */
182 { (10 + 4) * QR_MULT, (9 + 4) * QR_MULT, (8 + 4) * QR_MULT, (8 + 4) * QR_MULT, }, /* QR */
183 { (12 + 4) * QR_MULT, (11 + 4) * QR_MULT, (16 + 4) * QR_MULT, (10 + 4) * QR_MULT, },
184 { (14 + 4) * QR_MULT, (13 + 4) * QR_MULT, (16 + 4) * QR_MULT, (12 + 4) * QR_MULT, },
185 { 3 * QR_MULT, QR_MICROQR_MAX, QR_MICROQR_MAX, QR_MICROQR_MAX, }, /* MICROQR */
186 { (4 + 1) * QR_MULT, (3 + 1) * QR_MULT, QR_MICROQR_MAX, QR_MICROQR_MAX, },
187 { (5 + 2) * QR_MULT, (4 + 2) * QR_MULT, (4 + 2) * QR_MULT, (3 + 2) * QR_MULT, },
188 { (6 + 3) * QR_MULT, (5 + 3) * QR_MULT, (5 + 3) * QR_MULT, (4 + 3) * QR_MULT, }
189 };
190 int version;
191
192 /* Head costs kept in states 0..3 */
193
194 version = state[QR_VER];
195
196 if (version < RMQR_VERSION) { /* QRCODE */
197 if (version < 10) {
198 memcpy(state, head_costs[0], QR_NUM_MODES * sizeof(unsigned int));
199 } else if (version < 27) {
200 memcpy(state, head_costs[1], QR_NUM_MODES * sizeof(unsigned int));
201 } else {
202 memcpy(state, head_costs[2], QR_NUM_MODES * sizeof(unsigned int));
203 }
204 } else if (version < MICROQR_VERSION) { /* RMQR */
205 version -= RMQR_VERSION;
206 state[QR_N] = (rmqr_numeric_cci[version] + 3) * QR_MULT;
207 state[QR_A] = (rmqr_alphanum_cci[version] + 3) * QR_MULT;
208 state[QR_B] = (rmqr_byte_cci[version] + 3) * QR_MULT;
209 state[QR_K] = (rmqr_kanji_cci[version] + 3) * QR_MULT;
210 } else { /* MICROQR */
211 memcpy(state, head_costs[3 + (version - MICROQR_VERSION)], QR_NUM_MODES * sizeof(unsigned int));
212 }
213
214 return state;
215 }
216
217 /* Calculate optimized encoding modes. Adapted from Project Nayuki */
218 static void qr_define_mode(char mode[], const unsigned int ddata[], const int length, const int gs1,
219 const int version, const int debug_print) {
220 /*
221 * Copyright (c) Project Nayuki. (MIT License)
222 * https://www.nayuki.io/page/qr-code-generator-library
223 *
224 * Permission is hereby granted, free of charge, to any person obtaining a copy of
225 * this software and associated documentation files (the "Software"), to deal in
226 * the Software without restriction, including without limitation the rights to
227 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
228 * the Software, and to permit persons to whom the Software is furnished to do so,
229 * subject to the following conditions:
230 * - The above copyright notice and this permission notice shall be included in
231 * all copies or substantial portions of the Software.
232 */
233 unsigned int state[11] = {
234 0 /*N*/, 0 /*A*/, 0 /*B*/, 0 /*K*/, /* Head/switch costs */
235 0 /*version*/,
236 0 /*numeric_end*/, 0 /*numeric_cost*/, 0 /*alpha_end*/, 0 /*alpha_cost*/, 0 /*alpha_pcent*/, 0 /*alpha_pccnt*/
237 };
238 int m1, m2;
239
240 int i, j, k;
241 unsigned int min_cost;
242 char cur_mode;
243 unsigned int prev_costs[QR_NUM_MODES];
244 unsigned int cur_costs[QR_NUM_MODES];
245 char (*char_modes)[QR_NUM_MODES] = (char (*)[QR_NUM_MODES]) z_alloca(QR_NUM_MODES * length);
246
247 state[QR_VER] = (unsigned int) version;
248
249 /* char_modes[i][j] represents the mode to encode the code point at index i such that the final segment
250 ends in qr_mode_types[j] and the total number of bits is minimized over all possible choices */
251 memset(char_modes, 0, QR_NUM_MODES * length);
252
253 /* At the beginning of each iteration of the loop below, prev_costs[j] is the minimum number of 1/6 (1/QR_MULT)
254 * bits needed to encode the entire string prefix of length i, and end in qr_mode_types[j] */
255 memcpy(prev_costs, qr_head_costs(state), QR_NUM_MODES * sizeof(unsigned int));
256
257 #ifdef QR_DEBUG_DEFINE_MODE
258 printf(" head");
259 for (j = 0; j < QR_NUM_MODES; j++) {
260 printf(" %c(%c)=%d", qr_mode_types[j], char_modes[0][j], prev_costs[j]);
261 }
262 printf("\n");
263 #endif
264
265 /* Calculate costs using dynamic programming */
266 for (i = 0; i < length; i++) {
267 memset(cur_costs, 0, QR_NUM_MODES * sizeof(unsigned int));
268
269 m1 = version == MICROQR_VERSION;
270 m2 = version == MICROQR_VERSION + 1;
271
272 if (ddata[i] > 0xFF) {
273 cur_costs[QR_B] = prev_costs[QR_B] + ((m1 || m2) ? QR_MICROQR_MAX : 96); /* 16 * QR_MULT */
274 char_modes[i][QR_B] = 'B';
275 cur_costs[QR_K] = prev_costs[QR_K] + ((m1 || m2) ? QR_MICROQR_MAX : 78); /* 13 * QR_MULT */
276 char_modes[i][QR_K] = 'K';
277 } else {
278 if (qr_in_numeric(ddata, length, i, &state[QR_N_END], &state[QR_N_COST])) {
279 cur_costs[QR_N] = prev_costs[QR_N] + state[QR_N_COST];
280 char_modes[i][QR_N] = 'N';
281 }
282 if (qr_in_alpha(ddata, length, i, &state[QR_A_END], &state[QR_A_COST], &state[QR_A_PCENT],
283 &state[QR_A_PCCNT], gs1)) {
284 cur_costs[QR_A] = prev_costs[QR_A] + (m1 ? QR_MICROQR_MAX : state[QR_A_COST]);
285 char_modes[i][QR_A] = 'A';
286 }
287 cur_costs[QR_B] = prev_costs[QR_B] + ((m1 || m2) ? QR_MICROQR_MAX : 48); /* 8 * QR_MULT */
288 char_modes[i][QR_B] = 'B';
289 }
290
291 /* Start new segment at the end to switch modes */
292 for (j = 0; j < QR_NUM_MODES; j++) { /* To mode */
293 for (k = 0; k < QR_NUM_MODES; k++) { /* From mode */
294 if (j != k && char_modes[i][k]) {
295 const unsigned int new_cost = cur_costs[k] + state[j]; /* Switch costs same as head costs */
296 if (!char_modes[i][j] || new_cost < cur_costs[j]) {
297 cur_costs[j] = new_cost;
298 char_modes[i][j] = qr_mode_types[k];
299 }
300 }
301 }
302 }
303
304 #ifdef QR_DEBUG_DEFINE_MODE
305 {
306 int min_j = 0;
307 printf(" % 4d: curr", i);
308 for (j = 0; j < QR_NUM_MODES; j++) {
309 printf(" %c(%c)=%d", qr_mode_types[j], char_modes[i][j], cur_costs[j]);
310 if (cur_costs[j] < cur_costs[min_j]) min_j = j;
311 }
312 printf(" min %c(%c)=%d\n", qr_mode_types[min_j], char_modes[i][min_j], cur_costs[min_j]);
313 }
314 #endif
315 memcpy(prev_costs, cur_costs, QR_NUM_MODES * sizeof(unsigned int));
316 }
317
318 /* Find optimal ending mode */
319 min_cost = prev_costs[0];
320 cur_mode = qr_mode_types[0];
321 for (i = 1; i < QR_NUM_MODES; i++) {
322 if (prev_costs[i] < min_cost) {
323 min_cost = prev_costs[i];
324 cur_mode = qr_mode_types[i];
325 }
326 }
327
328 /* Get optimal mode for each code point by tracing backwards */
329 for (i = length - 1; i >= 0; i--) {
330 j = posn(qr_mode_types, cur_mode);
331 cur_mode = char_modes[i][j];
332 mode[i] = cur_mode;
333 }
334
335 if (debug_print) {
336 printf(" Mode: %.*s\n", length, mode);
337 }
338 }
339
340 /* Returns mode indicator based on version and mode */
341 static int qr_mode_indicator(const int version, const int mode) {
342 static const char mode_indicators[6][QR_NUM_MODES] = {
343 /*N A B K */
344 { 1, 2, 4, 8, }, /* QRCODE */
345 { 1, 2, 3, 4, }, /* RMQR */
346 { 0, 0, 0, 0, }, /* MICROQR */
347 { 0, 1, 0, 0, },
348 { 0, 1, 2, 3, },
349 { 0, 1, 2, 3, },
350 };
351
352 int mode_index = posn(qr_mode_types, (const char) mode);
353
354 if (version < RMQR_VERSION) {
355 return mode_indicators[0][mode_index]; /* QRCODE */
356 }
357 if (version < MICROQR_VERSION) {
358 return mode_indicators[1][mode_index] /* RMQR */;
359 }
360 return mode_indicators[2 + version - MICROQR_VERSION][mode_index]; /* MICROQR */
361 }
362
363 /* Return mode indicator bits based on version */
364 static int qr_mode_bits(const int version) {
365 if (version < RMQR_VERSION) {
366 return 4; /* QRCODE */
367 }
368 if (version < MICROQR_VERSION) {
369 return 3; /* RMQR */
370 }
371 return version - MICROQR_VERSION; /* MICROQR */
372 }
373
374 /* Return character count indicator bits based on version and mode */
375 static int qr_cci_bits(const int version, const int mode) {
376 static const char cci_bits[7][QR_NUM_MODES] = {
377 /* N A B K */
378 { 10, 9, 8, 8, }, /* QRCODE */
379 { 12, 11, 16, 10, },
380 { 14, 13, 16, 12, },
381 { 3, 0, 0, 0, }, /* MICROQR */
382 { 4, 3, 0, 0, },
383 { 5, 4, 4, 3, },
384 { 6, 5, 5, 4, }
385 };
386 static const unsigned char *const rmqr_ccis[QR_NUM_MODES] = {
387 rmqr_numeric_cci, rmqr_alphanum_cci, rmqr_byte_cci, rmqr_kanji_cci,
388 };
389 int mode_index = posn(qr_mode_types, (const char) mode);
390
391 if (version < RMQR_VERSION) { /* QRCODE */
392 if (version < 10) {
393 return cci_bits[0][mode_index];
394 }
395 if (version < 27) {
396 return cci_bits[1][mode_index];
397 }
398 return cci_bits[2][mode_index];
399 }
400 if (version < MICROQR_VERSION) { /* RMQR */
401 return rmqr_ccis[mode_index][version - RMQR_VERSION];
402 }
403 return cci_bits[3 + (version - MICROQR_VERSION)][mode_index]; /* MICROQR */
404 }
405
406 /* Returns terminator bits based on version */
407 static int qr_terminator_bits(const int version) {
408 if (version < RMQR_VERSION) {
409 return 4; /* QRCODE */
410 }
411 if (version < MICROQR_VERSION) {
412 return 3; /* RMQR */
413 }
414 return 3 + (version - MICROQR_VERSION) * 2; /* MICROQR */
415 }
416
417 /* Convert input data to a binary stream and add padding */
418 static int qr_binary(char binary[], int bp, const int version, const char mode[],
419 const unsigned int ddata[], const int length, const int gs1,
420 const int eci, const int debug_print) {
421 int position = 0;
422 int i;
423 int modebits;
424 int percent = 0;
425 int percent_count;
426
427 if (eci != 0) { /* Not applicable to MICROQR */
428 bp = bin_append_posn(7, version < RMQR_VERSION ? 4 : 3, binary, bp); /* ECI (Table 4) */
429 if (eci <= 127) {
430 bp = bin_append_posn(eci, 8, binary, bp); /* 000000 to 000127 */
431 } else if (eci <= 16383) {
432 bp = bin_append_posn(0x8000 + eci, 16, binary, bp); /* 000128 to 016383 */
433 } else {
434 bp = bin_append_posn(0xC00000 + eci, 24, binary, bp); /* 016384 to 999999 */
435 }
436 }
437
438 modebits = qr_mode_bits(version);
439
440 do {
441 char data_block = mode[position];
442 int short_data_block_length = 0;
443 int double_byte = 0;
444 do {
445 if (data_block == 'B' && ddata[position + short_data_block_length] > 0xFF) {
446 double_byte++;
447 }
448 short_data_block_length++;
449 } while (((short_data_block_length + position) < length)
450 && (mode[position + short_data_block_length] == data_block));
451
452 /* Mode indicator */
453 if (modebits) {
454 bp = bin_append_posn(qr_mode_indicator(version, data_block), modebits, binary, bp);
455 }
456
457 switch (data_block) {
458 case 'K':
459 /* Kanji mode */
460
461 /* Character count indicator */
462 bp = bin_append_posn(short_data_block_length, qr_cci_bits(version, data_block), binary, bp);
463
464 if (debug_print) {
465 printf("Kanji block (length %d)\n\t", short_data_block_length);
466 }
467
468 /* Character representation */
469 for (i = 0; i < short_data_block_length; i++) {
470 unsigned int jis = ddata[position + i];
471 int prod;
472
473 if (jis >= 0x8140 && jis <= 0x9ffc)
474 jis -= 0x8140;
475
476 else if (jis >= 0xe040 && jis <= 0xebbf)
477 jis -= 0xc140;
478
479 prod = ((jis >> 8) * 0xc0) + (jis & 0xff);
480
481 bp = bin_append_posn(prod, 13, binary, bp);
482
483 if (debug_print) {
484 printf("0x%04X ", prod);
485 }
486 }
487
488 if (debug_print) {
489 fputc('\n', stdout);
490 }
491
492 break;
493 case 'B':
494 /* Byte mode */
495
496 /* Character count indicator */
497 bp = bin_append_posn(short_data_block_length + double_byte, qr_cci_bits(version, data_block), binary,
498 bp);
499
500 if (debug_print) {
501 printf("Byte block (length %d)\n\t", short_data_block_length + double_byte);
502 }
503
504 /* Character representation */
505 for (i = 0; i < short_data_block_length; i++) {
506 unsigned int byte = ddata[position + i];
507
508 bp = bin_append_posn(byte, byte > 0xFF ? 16 : 8, binary, bp);
509
510 if (debug_print) {
511 printf("0x%02X(%d) ", byte, (int) byte);
512 }
513 }
514
515 if (debug_print) {
516 fputc('\n', stdout);
517 }
518
519 break;
520 case 'A':
521 /* Alphanumeric mode */
522
523 percent_count = 0;
524 if (gs1) {
525 for (i = 0; i < short_data_block_length; i++) {
526 if (ddata[position + i] == '%') {
527 percent_count++;
528 }
529 }
530 }
531
532 /* Character count indicator */
533 bp = bin_append_posn(short_data_block_length + percent_count, qr_cci_bits(version, data_block),
534 binary, bp);
535
536 if (debug_print) {
537 printf("Alpha block (length %d)\n\t", short_data_block_length + percent_count);
538 }
539
540 /* Character representation */
541 i = 0;
542 while (i < short_data_block_length) {
543 int count;
544 int first = 0, second = 0, prod;
545
546 if (percent == 0) {
547 if (gs1 && (ddata[position + i] == '%')) {
548 first = QR_PERCENT;
549 second = QR_PERCENT;
550 count = 2;
551 prod = (first * 45) + second;
552 i++;
553 } else {
554 if (gs1 && ddata[position + i] == '\x1D') {
555 first = QR_PERCENT; /* FNC1 */
556 } else {
557 first = qr_alphanumeric[ddata[position + i] - 32];
558 }
559 count = 1;
560 i++;
561 prod = first;
562
563 if (i < short_data_block_length && mode[position + i] == 'A') {
564 if (gs1 && (ddata[position + i] == '%')) {
565 second = QR_PERCENT;
566 count = 2;
567 prod = (first * 45) + second;
568 percent = 1;
569 } else {
570 if (gs1 && ddata[position + i] == '\x1D') {
571 second = QR_PERCENT; /* FNC1 */
572 } else {
573 second = qr_alphanumeric[ddata[position + i] - 32];
574 }
575 count = 2;
576 i++;
577 prod = (first * 45) + second;
578 }
579 }
580 }
581 } else {
582 first = QR_PERCENT;
583 count = 1;
584 i++;
585 prod = first;
586 percent = 0;
587
588 if (i < short_data_block_length && mode[position + i] == 'A') {
589 if (gs1 && (ddata[position + i] == '%')) {
590 second = QR_PERCENT;
591 count = 2;
592 prod = (first * 45) + second;
593 percent = 1;
594 } else {
595 if (gs1 && ddata[position + i] == '\x1D') {
596 second = QR_PERCENT; /* FNC1 */
597 } else {
598 second = qr_alphanumeric[ddata[position + i] - 32];
599 }
600 count = 2;
601 i++;
602 prod = (first * 45) + second;
603 }
604 }
605 }
606
607 bp = bin_append_posn(prod, 1 + (5 * count), binary, bp);
608
609 if (debug_print) {
610 printf("0x%X ", prod);
611 }
612 }
613
614 if (debug_print) {
615 fputc('\n', stdout);
616 }
617
618 break;
619 case 'N':
620 /* Numeric mode */
621
622 /* Character count indicator */
623 bp = bin_append_posn(short_data_block_length, qr_cci_bits(version, data_block), binary, bp);
624
625 if (debug_print) {
626 printf("Number block (length %d)\n\t", short_data_block_length);
627 }
628
629 /* Character representation */
630 i = 0;
631 while (i < short_data_block_length) {
632 int count;
633 int first = 0, prod;
634
635 first = ctoi((const char) ddata[position + i]);
636 count = 1;
637 prod = first;
638
639 if (i + 1 < short_data_block_length && mode[position + i + 1] == 'N') {
640 int second = ctoi((const char) ddata[position + i + 1]);
641 count = 2;
642 prod = (prod * 10) + second;
643
644 if (i + 2 < short_data_block_length && mode[position + i + 2] == 'N') {
645 int third = ctoi((const char) ddata[position + i + 2]);
646 count = 3;
647 prod = (prod * 10) + third;
648 }
649 }
650
651 bp = bin_append_posn(prod, 1 + (3 * count), binary, bp);
652
653 if (debug_print) {
654 printf("0x%X(%d) ", prod, prod);
655 }
656
657 i += count;
658 };
659
660 if (debug_print) {
661 fputc('\n', stdout);
662 }
663
664 break;
665 }
666
667 position += short_data_block_length;
668 } while (position < length);
669
670 return bp;
671 }
672
673 /* Call `qr_binary()` for each segment, dealing with Structured Append and GS1 beforehand and padding afterwards */
674 static int qr_binary_segs(unsigned char datastream[], const int version, const int target_codewords,
675 const char mode[], const unsigned int ddata[], const struct zint_seg segs[], const int seg_count,
676 const struct zint_structapp *p_structapp, const int gs1, const int est_binlen, const int debug_print) {
677 int i, j;
678 const unsigned int *dd = ddata;
679 const char *m = mode;
680 int bp = 0;
681 int termbits, padbits;
682 int current_bytes;
683 int toggle;
684 char *binary = (char *) z_alloca(est_binlen + 12);
685
686 *binary = '\0';
687
688 if (p_structapp) {
689 bp = bin_append_posn(3, 4, binary, bp); /* Structured Append indicator */
690 bp = bin_append_posn(p_structapp->index - 1, 4, binary, bp);
691 bp = bin_append_posn(p_structapp->count - 1, 4, binary, bp);
692 bp = bin_append_posn(to_int((const unsigned char *) p_structapp->id, (int) strlen(p_structapp->id)), 8,
693 binary, bp); /* Parity */
694 }
695
696 if (gs1) { /* Not applicable to MICROQR */
697 if (version < RMQR_VERSION) {
698 bp = bin_append_posn(5, 4, binary, bp); /* FNC1 */
699 } else {
700 bp = bin_append_posn(5, 3, binary, bp);
701 }
702 }
703
704 for (i = 0; i < seg_count; i++) {
705 bp = qr_binary(binary, bp, version, m, dd, segs[i].length, gs1, segs[i].eci, debug_print);
706 m += segs[i].length;
707 dd += segs[i].length;
708 }
709
710 if (version >= MICROQR_VERSION && version < MICROQR_VERSION + 4) {
711 /* MICROQR does its own terminating/padding */
712 memcpy(datastream, binary, bp);
713 return bp;
714 }
715
716 /* Terminator */
717 termbits = 8 - bp % 8;
718 if (termbits == 8) {
719 termbits = 0;
720 }
721 current_bytes = (bp + termbits) / 8;
722 if (termbits || current_bytes < target_codewords) {
723 int max_termbits = qr_terminator_bits(version);
724 termbits = termbits < max_termbits && current_bytes == target_codewords ? termbits : max_termbits;
725 bp = bin_append_posn(0, termbits, binary, bp);
726 }
727
728 /* Padding bits */
729 padbits = 8 - bp % 8;
730 if (padbits == 8) {
731 padbits = 0;
732 }
733 if (padbits) {
734 current_bytes = (bp + padbits) / 8;
735 (void) bin_append_posn(0, padbits, binary, bp); /* Last use so not setting bp */
736 }
737
738 if (debug_print) printf("Terminated binary (%d): %.*s (padbits %d)\n", bp, bp, binary, padbits);
739
740 /* Put data into 8-bit codewords */
741 for (i = 0; i < current_bytes; i++) {
742 int p;
743 j = i * 8;
744 datastream[i] = 0x00;
745 for (p = 0; p < 8; p++) {
746 if (binary[j + p] == '1') {
747 datastream[i] |= (0x80 >> p);
748 }
749 }
750 }
751
752 /* Add pad codewords */
753 toggle = 0;
754 for (i = current_bytes; i < target_codewords; i++) {
755 if (toggle == 0) {
756 datastream[i] = 0xec;
757 toggle = 1;
758 } else {
759 datastream[i] = 0x11;
760 toggle = 0;
761 }
762 }
763
764 if (debug_print) {
765 printf("Resulting codewords (%d):\n\t", target_codewords);
766 for (i = 0; i < target_codewords; i++) {
767 printf("0x%02X ", datastream[i]);
768 }
769 fputc('\n', stdout);
770 }
771
772 return 0; /* Not used */
773 }
774
775 /* Split data into blocks, add error correction and then interleave the blocks and error correction data */
776 static void qr_add_ecc(unsigned char fullstream[], const unsigned char datastream[], const int version,
777 const int data_cw, const int blocks, const int debug_print) {
778 int ecc_cw;
779 int short_data_block_length;
780 int qty_long_blocks;
781 int qty_short_blocks;
782 int ecc_block_length;
783 int i, j, length_this_block, in_posn;
784 rs_t rs;
785 unsigned char *data_block;
786 unsigned char *ecc_block;
787 unsigned char *interleaved_data;
788 unsigned char *interleaved_ecc;
789
790 if (version < RMQR_VERSION) {
791 ecc_cw = qr_total_codewords[version - 1] - data_cw;
792 } else {
793 ecc_cw = rmqr_total_codewords[version - RMQR_VERSION] - data_cw;
794 }
795
796 /* Suppress some clang-tidy clang-analyzer-core.UndefinedBinaryOperatorResult/uninitialized.Assign warnings */
797 assert(blocks > 0);
798
799 short_data_block_length = data_cw / blocks;
800 qty_long_blocks = data_cw % blocks;
801 qty_short_blocks = blocks - qty_long_blocks;
802 ecc_block_length = ecc_cw / blocks;
803
804 /* Suppress some clang-tidy clang-analyzer-core.UndefinedBinaryOperatorResult/uninitialized.Assign warnings */
805 assert(short_data_block_length > 0);
806 assert(qty_long_blocks || qty_short_blocks);
807
808 data_block = (unsigned char *) z_alloca(short_data_block_length + 1);
809 ecc_block = (unsigned char *) z_alloca(ecc_block_length);
810 interleaved_data = (unsigned char *) z_alloca(data_cw);
811 interleaved_ecc = (unsigned char *) z_alloca(ecc_cw);
812
813 rs_init_gf(&rs, 0x11d);
814 rs_init_code(&rs, ecc_block_length, 0);
815
816 in_posn = 0;
817
818 for (i = 0; i < blocks; i++) {
819 if (i < qty_short_blocks) {
820 length_this_block = short_data_block_length;
821 } else {
822 length_this_block = short_data_block_length + 1;
823 }
824
825 for (j = 0; j < length_this_block; j++) {
826 /* This false-positive popped up with clang-tidy 14.0.1 */
827 data_block[j] = datastream[in_posn + j]; /* NOLINT(clang-analyzer-core.uninitialized.Assign) */
828 }
829
830 rs_encode(&rs, length_this_block, data_block, ecc_block);
831
832 if (debug_print) {
833 printf("Block %d: ", i + 1);
834 for (j = 0; j < length_this_block; j++) {
835 printf("%2X ", data_block[j]);
836 }
837 if (i < qty_short_blocks) {
838 fputs(" ", stdout);
839 }
840 fputs(" // ", stdout);
841 for (j = 0; j < ecc_block_length; j++) {
842 printf("%2X ", ecc_block[j]);
843 }
844 fputc('\n', stdout);
845 }
846
847 for (j = 0; j < short_data_block_length; j++) {
848 /* And another with clang-tidy 14.0.6 */
849 interleaved_data[(j * blocks) + i] = data_block[j]; /* NOLINT(clang-analyzer-core.uninitialized.Assign) */
850 }
851
852 if (i >= qty_short_blocks) {
853 interleaved_data[(short_data_block_length * blocks) + (i - qty_short_blocks)]
854 = data_block[short_data_block_length];
855 }
856
857 for (j = 0; j < ecc_block_length; j++) {
858 interleaved_ecc[(j * blocks) + i] = ecc_block[j];
859 }
860
861 in_posn += length_this_block;
862 }
863
864 for (j = 0; j < data_cw; j++) {
865 fullstream[j] = interleaved_data[j];
866 }
867 for (j = 0; j < ecc_cw; j++) {
868 fullstream[j + data_cw] = interleaved_ecc[j];
869 }
870
871 if (debug_print) {
872 printf("\nData Stream (%d): \n", data_cw + ecc_cw);
873 for (j = 0; j < (data_cw + ecc_cw); j++) {
874 printf("%2X ", fullstream[j]);
875 }
876 fputc('\n', stdout);
877 }
878 }
879
880 static void qr_place_finder(unsigned char grid[], const int size, const int x, const int y) {
881 int xp, yp;
882 char finder[] = {0x7F, 0x41, 0x5D, 0x5D, 0x5D, 0x41, 0x7F};
883
884 for (xp = 0; xp < 7; xp++) {
885 for (yp = 0; yp < 7; yp++) {
886 if (finder[yp] & 0x40 >> xp) {
887 grid[((yp + y) * size) + (xp + x)] = 0x11;
888 } else {
889 grid[((yp + y) * size) + (xp + x)] = 0x10;
890 }
891 }
892 }
893 }
894
895 static void qr_place_align(unsigned char grid[], const int size, int x, int y) {
896 int xp, yp;
897 char alignment[] = {0x1F, 0x11, 0x15, 0x11, 0x1F};
898
899 x -= 2;
900 y -= 2; /* Input values represent centre of pattern */
901
902 for (xp = 0; xp < 5; xp++) {
903 for (yp = 0; yp < 5; yp++) {
904 if (alignment[yp] & 0x10 >> xp) {
905 grid[((yp + y) * size) + (xp + x)] = 0x11;
906 } else {
907 grid[((yp + y) * size) + (xp + x)] = 0x10;
908 }
909 }
910 }
911 }
912
913 static void qr_setup_grid(unsigned char *grid, const int size, const int version) {
914 int i, toggle = 1;
915
916 /* Suppress false positive gcc >= 13 warning (when optimizing only) "writing 1 byte into a region of size 0" */
917 #if defined(__GNUC__) && !defined(__clang__) && __GNUC__ >= 13
918 #pragma GCC diagnostic push
919 #pragma GCC diagnostic ignored "-Wstringop-overflow"
920 #endif
921
922 /* Add timing patterns */
923 for (i = 0; i < size; i++) {
924 if (toggle == 1) {
925 grid[(6 * size) + i] = 0x21;
926 grid[(i * size) + 6] = 0x21;
927 toggle = 0;
928 } else {
929 grid[(6 * size) + i] = 0x20;
930 grid[(i * size) + 6] = 0x20;
931 toggle = 1;
932 }
933 }
934
935 /* Add finder patterns */
936 qr_place_finder(grid, size, 0, 0);
937 qr_place_finder(grid, size, 0, size - 7);
938 qr_place_finder(grid, size, size - 7, 0);
939
940 /* Add separators */
941 for (i = 0; i < 7; i++) {
942 grid[(7 * size) + i] = 0x10;
943 grid[(i * size) + 7] = 0x10;
944 grid[(7 * size) + (size - 1 - i)] = 0x10;
945 grid[(i * size) + (size - 8)] = 0x10;
946 grid[((size - 8) * size) + i] = 0x10;
947 grid[((size - 1 - i) * size) + 7] = 0x10;
948 }
949 grid[(7 * size) + 7] = 0x10;
950 grid[(7 * size) + (size - 8)] = 0x10;
951 grid[((size - 8) * size) + 7] = 0x10;
952
953 #if defined(__GNUC__) && !defined(__clang__) && __GNUC__ >= 13
954 #pragma GCC diagnostic pop
955 #endif
956
957 /* Add alignment patterns */
958 if (version != 1) {
959 /* Version 1 does not have alignment patterns */
960
961 int loopsize = qr_align_loopsize[version - 1];
962 int x, y;
963 for (x = 0; x < loopsize; x++) {
964 for (y = 0; y < loopsize; y++) {
965 int xcoord = qr_table_e1[((version - 2) * 7) + x];
966 int ycoord = qr_table_e1[((version - 2) * 7) + y];
967
968 if (!(grid[(ycoord * size) + xcoord] & 0x10)) {
969 qr_place_align(grid, size, xcoord, ycoord);
970 }
971 }
972 }
973 }
974
975 /* Reserve space for format information */
976 for (i = 0; i < 8; i++) {
977 grid[(8 * size) + i] |= 0x20;
978 grid[(i * size) + 8] |= 0x20;
979 grid[(8 * size) + (size - 1 - i)] = 0x20;
980 grid[((size - 1 - i) * size) + 8] = 0x20;
981 }
982 grid[(8 * size) + 8] |= 0x20;
983 grid[((size - 1 - 7) * size) + 8] = 0x21; /* Dark Module from Figure 25 */
984
985 /* Reserve space for version information */
986 if (version >= 7) {
987 for (i = 0; i < 6; i++) {
988 grid[((size - 9) * size) + i] = 0x20;
989 grid[((size - 10) * size) + i] = 0x20;
990 grid[((size - 11) * size) + i] = 0x20;
991 grid[(i * size) + (size - 9)] = 0x20;
992 grid[(i * size) + (size - 10)] = 0x20;
993 grid[(i * size) + (size - 11)] = 0x20;
994 }
995 }
996 }
997
998 static int qr_cwbit(const unsigned char *fullstream, const int i) {
999
1000 if (fullstream[(i >> 3)] & (0x80 >> (i & 0x07))) {
1001 return 1;
1002 }
1003
1004 return 0;
1005 }
1006
1007 static void qr_populate_grid(unsigned char *grid, const int h_size, const int v_size, const unsigned char *fullstream,
1008 const int cw) {
1009 const int not_rmqr = v_size == h_size;
1010 const int x_start = h_size - (not_rmqr ? 2 : 3); /* For rMQR allow for righthand vertical timing pattern */
1011 int direction = 1; /* up */
1012 int row = 0; /* right hand side */
1013
1014 int i, n, y;
1015
1016 n = cw * 8;
1017 y = v_size - 1;
1018 i = 0;
1019 while (i < n) {
1020 int x = x_start - (row * 2);
1021 int r = y * h_size;
1022
1023 if ((x < 6) && (not_rmqr))
1024 x--; /* skip over vertical timing pattern */
1025
1026 if (!(grid[r + (x + 1)] & 0xf0)) {
1027 grid[r + (x + 1)] = qr_cwbit(fullstream, i);
1028 i++;
1029 }
1030
1031 if (i < n) {
1032 if (!(grid[r + x] & 0xf0)) {
1033 grid[r + x] = qr_cwbit(fullstream, i);
1034 i++;
1035 }
1036 }
1037
1038 if (direction) {
1039 y--;
1040 if (y == -1) {
1041 /* reached the top */
1042 row++;
1043 y = 0;
1044 direction = 0;
1045 }
1046 } else {
1047 y++;
1048 if (y == v_size) {
1049 /* reached the bottom */
1050 row++;
1051 y = v_size - 1;
1052 direction = 1;
1053 }
1054 }
1055 }
1056 }
1057
1058 #ifdef ZINTLOG
1059 static void append_log(const unsigned char log) {
1060 FILE *file;
1061
1062 if ((file = fopen("zintlog.txt", "a+"))) {
1063 fprintf(file, "%02X", log);
1064 (void) fclose(file);
1065 }
1066 }
1067
1068 static void write_log(const char log[]) {
1069 FILE *file;
1070
1071 if ((file = fopen("zintlog.txt", "a+"))) {
1072 fprintf(file, "%s\n", log); /*writes*/
1073 (void) fclose(file);
1074 }
1075 }
1076 #endif
1077
1078 static int qr_evaluate(unsigned char *local, const int size) {
1079 static const unsigned char h1011101[7] = { 1, 0, 1, 1, 1, 0, 1 };
1080
1081 int x, y, r, k, block;
1082 int result = 0;
1083 char state;
1084 int dark_mods;
1085 double percentage;
1086 int a, b, afterCount, beforeCount;
1087 #ifdef ZINTLOG
1088 int result_b = 0;
1089 char str[15];
1090 #endif
1091
1092 /* Suppresses clang-tidy clang-analyzer-core.UndefinedBinaryOperatorResult warnings */
1093 assert(size > 0);
1094
1095 #ifdef ZINTLOG
1096 /* bitmask output */
1097 for (y = 0; y < size; y++) {
1098 for (x = 0; x < size; x++) {
1099 append_log(local[(y * size) + x]);
1100 }
1101 write_log("");
1102 }
1103 #endif
1104
1105 /* Test 1: Adjacent modules in row/column in same colour */
1106 /* Vertical */
1107 for (x = 0; x < size; x++) {
1108 block = 0;
1109 state = 0;
1110 for (y = 0; y < size; y++) {
1111 if (local[(y * size) + x] == state) {
1112 block++;
1113 } else {
1114 if (block >= 5) {
1115 result += block - 2;
1116 }
1117 block = 1;
1118 state = local[(y * size) + x];
1119 }
1120 }
1121 if (block >= 5) {
1122 result += block - 2;
1123 }
1124 }
1125
1126 /* Horizontal */
1127 dark_mods = 0; /* Count dark mods simultaneously (see Test 4 below) */
1128 for (y = 0; y < size; y++) {
1129 r = y * size;
1130 block = 0;
1131 state = 0;
1132 for (x = 0; x < size; x++) {
1133 if (local[r + x] == state) {
1134 block++;
1135 } else {
1136 if (block >= 5) {
1137 result += block - 2;
1138 }
1139 block = 1;
1140 state = local[r + x];
1141 }
1142 if (state) {
1143 dark_mods++;
1144 }
1145 }
1146 if (block >= 5) {
1147 result += block - 2;
1148 }
1149 }
1150
1151 #ifdef ZINTLOG
1152 /* output Test 1 */
1153 sprintf(str, "%d", result);
1154 result_b = result;
1155 write_log(str);
1156 #endif
1157
1158 /* Test 2: Block of modules in same color */
1159 for (x = 0; x < size - 1; x++) {
1160 for (y = 0; y < size - 1; y++) {
1161 k = local[(y * size) + x];
1162 if (((k == local[((y + 1) * size) + x]) &&
1163 (k == local[(y * size) + (x + 1)])) &&
1164 (k == local[((y + 1) * size) + (x + 1)])) {
1165 result += 3;
1166 }
1167 }
1168 }
1169
1170 #ifdef ZINTLOG
1171 /* output Test 2 */
1172 sprintf(str, "%d", result - result_b);
1173 result_b = result;
1174 write_log(str);
1175 #endif
1176
1177 /* Test 3: 1:1:3:1:1 ratio pattern in row/column */
1178 /* Vertical */
1179 for (x = 0; x < size; x++) {
1180 for (y = 0; y <= (size - 7); y++) {
1181 if (local[y * size + x] && !local[(y + 1) * size + x] && local[(y + 2) * size + x] &&
1182 local[(y + 3) * size + x] && local[(y + 4) * size + x] &&
1183 !local[(y + 5) * size + x] && local[(y + 6) * size + x]) {
1184 /* Pattern found, check before and after */
1185 beforeCount = 0;
1186 for (b = (y - 1); b >= (y - 4); b--) {
1187 if (b < 0) { /* Count < edge as whitespace */
1188 beforeCount = 4;
1189 break;
1190 }
1191 if (local[(b * size) + x]) {
1192 break;
1193 }
1194 beforeCount++;
1195 }
1196 if (beforeCount == 4) {
1197 /* Pattern is preceded by light area 4 modules wide */
1198 result += 40;
1199 } else {
1200 afterCount = 0;
1201 for (a = (y + 7); a <= (y + 10); a++) {
1202 if (a >= size) { /* Count > edge as whitespace */
1203 afterCount = 4;
1204 break;
1205 }
1206 if (local[(a * size) + x]) {
1207 break;
1208 }
1209 afterCount++;
1210 }
1211 if (afterCount == 4) {
1212 /* Pattern is followed by light area 4 modules wide */
1213 result += 40;
1214 }
1215 }
1216 y += 3; /* Skip to next possible match */
1217 }
1218 }
1219 }
1220
1221 /* Horizontal */
1222 for (y = 0; y < size; y++) {
1223 r = y * size;
1224 for (x = 0; x <= (size - 7); x++) {
1225 if (memcmp(local + r + x, h1011101, 7) == 0) {
1226 /* Pattern found, check before and after */
1227 beforeCount = 0;
1228 for (b = (x - 1); b >= (x - 4); b--) {
1229 if (b < 0) { /* Count < edge as whitespace */
1230 beforeCount = 4;
1231 break;
1232 }
1233 if (local[r + b]) {
1234 break;
1235 }
1236 beforeCount++;
1237 }
1238
1239 if (beforeCount == 4) {
1240 /* Pattern is preceded by light area 4 modules wide */
1241 result += 40;
1242 } else {
1243 afterCount = 0;
1244 for (a = (x + 7); a <= (x + 10); a++) {
1245 if (a >= size) { /* Count > edge as whitespace */
1246 afterCount = 4;
1247 break;
1248 }
1249 if (local[r + a]) {
1250 break;
1251 }
1252 afterCount++;
1253 }
1254 if (afterCount == 4) {
1255 /* Pattern is followed by light area 4 modules wide */
1256 result += 40;
1257 }
1258 }
1259 x += 3; /* Skip to next possible match */
1260 }
1261 }
1262 }
1263
1264 #ifdef ZINTLOG
1265 /* output Test 3 */
1266 sprintf(str, "%d", result - result_b);
1267 result_b = result;
1268 write_log(str);
1269 #endif
1270
1271 /* Test 4: Proportion of dark modules in entire symbol */
1272 percentage = (100.0 * dark_mods) / (size * size);
1273 k = (int) (fabs(percentage - 50.0) / 5.0);
1274
1275 result += 10 * k;
1276
1277 #ifdef ZINTLOG
1278 /* output Test 4+summary */
1279 sprintf(str, "%d", result - result_b);
1280 write_log(str);
1281 write_log("==========");
1282 sprintf(str, "%d", result);
1283 write_log(str);
1284 #endif
1285
1286 return result;
1287 }
1288
1289 /* Add format information to grid */
1290 static void qr_add_format_info(unsigned char *grid, const int size, const int ecc_level, const int pattern) {
1291 int format = pattern;
1292 unsigned int seq;
1293 int i;
1294
1295 switch (ecc_level) {
1296 case QR_LEVEL_L: format |= 0x08;
1297 break;
1298 case QR_LEVEL_Q: format |= 0x18;
1299 break;
1300 case QR_LEVEL_H: format |= 0x10;
1301 break;
1302 }
1303
1304 seq = qr_annex_c[format];
1305
1306 for (i = 0; i < 6; i++) {
1307 grid[(i * size) + 8] |= (seq >> i) & 0x01;
1308 }
1309
1310 for (i = 0; i < 8; i++) {
1311 grid[(8 * size) + (size - i - 1)] |= (seq >> i) & 0x01;
1312 }
1313
1314 for (i = 0; i < 6; i++) {
1315 grid[(8 * size) + (5 - i)] |= (seq >> (i + 9)) & 0x01;
1316 }
1317
1318 for (i = 0; i < 7; i++) {
1319 grid[(((size - 7) + i) * size) + 8] |= (seq >> (i + 8)) & 0x01;
1320 }
1321
1322 grid[(7 * size) + 8] |= (seq >> 6) & 0x01;
1323 grid[(8 * size) + 8] |= (seq >> 7) & 0x01;
1324 grid[(8 * size) + 7] |= (seq >> 8) & 0x01;
1325 }
1326
1327 static int qr_apply_bitmask(unsigned char *grid, const int size, const int ecc_level, const int user_mask,
1328 const int fast_encode, const int debug_print) {
1329 int x, y;
1330 int r, k;
1331 int bit;
1332 int pattern, penalty[8];
1333 int best_pattern;
1334 int size_squared = size * size;
1335 unsigned char *mask = (unsigned char *) z_alloca(size_squared);
1336 unsigned char *local = (unsigned char *) z_alloca(size_squared);
1337 #ifdef ZINTLOG
1338 char str[15];
1339 #endif
1340
1341 /* Perform data masking */
1342 memset(mask, 0, size_squared);
1343 for (y = 0; y < size; y++) {
1344 r = y * size;
1345 for (x = 0; x < size; x++) {
1346
1347 /* all eight bitmask variants are encoded in the 8 bits of the bytes that make up the mask array. */
1348 if (!(grid[r + x] & 0xf0)) { /* exclude areas not to be masked. */
1349 if (((y + x) & 1) == 0) {
1350 mask[r + x] |= 0x01;
1351 }
1352 if (!fast_encode) {
1353 if ((y & 1) == 0) {
1354 mask[r + x] |= 0x02;
1355 }
1356 }
1357 if ((x % 3) == 0) {
1358 mask[r + x] |= 0x04;
1359 }
1360 if (!fast_encode) {
1361 if (((y + x) % 3) == 0) {
1362 mask[r + x] |= 0x08;
1363 }
1364 }
1365 if ((((y / 2) + (x / 3)) & 1) == 0) {
1366 mask[r + x] |= 0x10;
1367 }
1368 if (!fast_encode) {
1369 if ((y * x) % 6 == 0) { /* Equivalent to (y * x) % 2 + (y * x) % 3 == 0 */
1370 mask[r + x] |= 0x20;
1371 }
1372 if (((((y * x) & 1) + ((y * x) % 3)) & 1) == 0) {
1373 mask[r + x] |= 0x40;
1374 }
1375 }
1376 if (((((y + x) & 1) + ((y * x) % 3)) & 1) == 0) {
1377 mask[r + x] |= 0x80;
1378 }
1379 }
1380 }
1381 }
1382
1383 if (user_mask) {
1384 best_pattern = user_mask - 1;
1385 } else {
1386 /* all eight bitmask variants have been encoded in the 8 bits of the bytes
1387 * that make up the mask array. select them for evaluation according to the
1388 * desired pattern.*/
1389 best_pattern = 0;
1390 for (pattern = 0; pattern < 8; pattern++) {
1391 if (fast_encode && pattern != 0 && pattern != 2 && pattern != 4 && pattern != 7) {
1392 continue;
1393 }
1394 bit = 1 << pattern;
1395 for (k = 0; k < size_squared; k++) {
1396 if (mask[k] & bit) {
1397 local[k] = grid[k] ^ 0x01;
1398 } else {
1399 local[k] = grid[k] & 0x0f;
1400 }
1401 }
1402 qr_add_format_info(local, size, ecc_level, pattern);
1403
1404 penalty[pattern] = qr_evaluate(local, size);
1405
1406 if (penalty[pattern] < penalty[best_pattern]) {
1407 best_pattern = pattern;
1408 }
1409 }
1410 }
1411
1412 if (debug_print) {
1413 printf("Mask: %d (%s)", best_pattern, user_mask ? "specified" : fast_encode ? "fast automatic": "automatic");
1414 if (!user_mask) {
1415 if (fast_encode) {
1416 printf(" 0:%d 2:%d 4:%d 7:%d", penalty[0], penalty[2], penalty[4], penalty[7]);
1417 } else {
1418 for (pattern = 0; pattern < 8; pattern++) printf(" %d:%d", pattern, penalty[pattern]);
1419 }
1420 }
1421 fputc('\n', stdout);
1422 }
1423
1424 #ifdef ZINTLOG
1425 sprintf(str, "%d", best_pattern);
1426 write_log("chose pattern:");
1427 write_log(str);
1428 #endif
1429
1430 /* Apply mask */
1431 if (!user_mask && best_pattern == 7) { /* Reuse last */
1432 memcpy(grid, local, size_squared);
1433 } else {
1434 bit = 1 << best_pattern;
1435 for (y = 0; y < size_squared; y++) {
1436 if (mask[y] & bit) {
1437 grid[y] ^= 0x01;
1438 }
1439 }
1440 }
1441
1442 return best_pattern;
1443 }
1444
1445 /* Add version information */
1446 static void qr_add_version_info(unsigned char *grid, const int size, const int version) {
1447 int i;
1448
1449 unsigned int version_data = qr_annex_d[version - 7];
1450 for (i = 0; i < 6; i++) {
1451 grid[((size - 11) * size) + i] |= (version_data >> (i * 3)) & 1;
1452 grid[((size - 10) * size) + i] |= (version_data >> ((i * 3) + 1)) & 1;
1453 grid[((size - 9) * size) + i] |= (version_data >> ((i * 3) + 2)) & 1;
1454 grid[(i * size) + (size - 11)] |= (version_data >> (i * 3)) & 1;
1455 grid[(i * size) + (size - 10)] |= (version_data >> ((i * 3) + 1)) & 1;
1456 grid[(i * size) + (size - 9)] |= (version_data >> ((i * 3) + 2)) & 1;
1457 }
1458 }
1459
1460 /* Find the length of the block starting from 'start' */
1461 static int qr_blockLength(const int start, const char mode[], const int length) {
1462 int i;
1463 int count = 0;
1464 char start_mode = mode[start];
1465
1466 i = start;
1467
1468 do {
1469 count++;
1470 } while (((i + count) < length) && (mode[i + count] == start_mode));
1471
1472 return count;
1473 }
1474
1475 /* Calculate the actual bitlength of the proposed binary string */
1476 static int qr_calc_binlen(const int version, char mode[], const unsigned int ddata[], const int length,
1477 const int mode_preset, const int gs1, const int eci, const int debug_print) {
1478 int i, j;
1479 char currentMode;
1480 int count = 0;
1481 int alphalength;
1482 int blocklength;
1483
1484 if (!mode_preset) {
1485 qr_define_mode(mode, ddata, length, gs1, version, debug_print);
1486 }
1487
1488 currentMode = ' '; /* Null */
1489
1490 if (eci != 0) { /* Not applicable to MICROQR */
1491 count += 4;
1492 if (eci <= 127) {
1493 count += 8;
1494 } else if (eci <= 16383) {
1495 count += 16;
1496 } else {
1497 count += 24;
1498 }
1499 }
1500
1501 for (i = 0; i < length; i++) {
1502 if (mode[i] != currentMode) {
1503 count += qr_mode_bits(version) + qr_cci_bits(version, mode[i]);
1504 blocklength = qr_blockLength(i, mode, length);
1505 switch (mode[i]) {
1506 case 'K':
1507 count += (blocklength * 13);
1508 break;
1509 case 'B':
1510 for (j = i; j < (i + blocklength); j++) {
1511 if (ddata[j] > 0xff) {
1512 count += 16;
1513 } else {
1514 count += 8;
1515 }
1516 }
1517 break;
1518 case 'A':
1519 alphalength = blocklength;
1520 if (gs1) {
1521 /* In alphanumeric mode % becomes %% */
1522 for (j = i; j < (i + blocklength); j++) {
1523 if (ddata[j] == '%') {
1524 alphalength++;
1525 }
1526 }
1527 }
1528 switch (alphalength % 2) {
1529 case 0:
1530 count += (alphalength / 2) * 11;
1531 break;
1532 case 1:
1533 count += ((alphalength - 1) / 2) * 11;
1534 count += 6;
1535 break;
1536 }
1537 break;
1538 case 'N':
1539 switch (blocklength % 3) {
1540 case 0:
1541 count += (blocklength / 3) * 10;
1542 break;
1543 case 1:
1544 count += ((blocklength - 1) / 3) * 10;
1545 count += 4;
1546 break;
1547 case 2:
1548 count += ((blocklength - 2) / 3) * 10;
1549 count += 7;
1550 break;
1551 }
1552 break;
1553 }
1554 currentMode = mode[i];
1555 }
1556 }
1557
1558 return count;
1559 }
1560
1561 /* Call `qr_calc_binlen()` on each segment */
1562 static int qr_calc_binlen_segs(const int version, char mode[], const unsigned int ddata[],
1563 const struct zint_seg segs[], const int seg_count, const struct zint_structapp *p_structapp,
1564 const int mode_preset, const int gs1, const int debug_print) {
1565 int i;
1566 int count = 0;
1567 const unsigned int *dd = ddata;
1568 char *m = mode;
1569
1570 if (p_structapp) {
1571 count += 4 + 8 + 8;
1572 }
1573
1574 if (gs1) { /* Not applicable to MICROQR */
1575 if (version < RMQR_VERSION) {
1576 count += 4;
1577 } else {
1578 count += 3;
1579 }
1580 }
1581
1582 for (i = 0; i < seg_count; i++) {
1583 count += qr_calc_binlen(version, m, dd, segs[i].length, mode_preset, gs1, segs[i].eci, debug_print);
1584 m += segs[i].length;
1585 dd += segs[i].length;
1586 }
1587
1588 if (debug_print) {
1589 printf("Estimated Binary Length: %d (version %d, gs1 %d)\n", count, version, gs1);
1590 }
1591
1592 return count;
1593 }
1594
1595 /* Helper to process source data into `ddata` array */
1596 static int qr_prep_data(struct zint_symbol *symbol, struct zint_seg segs[], const int seg_count,
1597 unsigned int ddata[]) {
1598 int warn_number = 0;
1599 int i;
1600 /* If ZINT_FULL_MULTIBYTE use Kanji mode in DATA_MODE or for non-Shift JIS in UNICODE_MODE */
1601 const int full_multibyte = (symbol->option_3 & 0xFF) == ZINT_FULL_MULTIBYTE;
1602
1603 if ((symbol->input_mode & 0x07) == DATA_MODE) {
1604 sjis_cpy_segs(segs, seg_count, ddata, full_multibyte);
1605 } else {
1606 unsigned int *dd = ddata;
1607 for (i = 0; i < seg_count; i++) {
1608 int done = 0;
1609 if (segs[i].eci != 20 || seg_count > 1) { /* Unless ECI 20 (Shift JIS) or have multiple segments */
1610 /* Try other encodings (ECI 0 defaults to ISO/IEC 8859-1) */
1611 int error_number = sjis_utf8_to_eci(segs[i].eci, segs[i].source, &segs[i].length, dd, full_multibyte);
1612 if (error_number == 0) {
1613 done = 1;
1614 } else if (segs[i].eci || seg_count > 1) {
1615 return errtxtf(error_number, symbol, 575, "Invalid character in input for ECI '%d'", segs[i].eci);
1616 }
1617 }
1618 if (!done) {
1619 /* Try Shift-JIS */
1620 int error_number = sjis_utf8(symbol, segs[i].source, &segs[i].length, dd);
1621 if (error_number != 0) {
1622 return error_number;
1623 }
1624 if (segs[i].eci != 20) {
1625 warn_number = errtxt(ZINT_WARN_NONCOMPLIANT, symbol, 760,
1626 "Converted to Shift JIS but no ECI specified");
1627 }
1628 }
1629 dd += segs[i].length;
1630 }
1631 }
1632
1633 return warn_number;
1634 }
1635
1636 INTERNAL int qrcode(struct zint_symbol *symbol, struct zint_seg segs[], const int seg_count) {
1637 int warn_number;
1638 int i, j, est_binlen, prev_est_binlen;
1639 int ecc_level, autosize, version, max_cw, target_codewords, blocks, size;
1640 int bitmask;
1641 int user_mask;
1642 int canShrink;
1643 int size_squared;
1644 const struct zint_structapp *p_structapp = NULL;
1645 const int gs1 = ((symbol->input_mode & 0x07) == GS1_MODE);
1646 const int fast_encode = symbol->input_mode & FAST_MODE;
1647 const int debug_print = symbol->debug & ZINT_DEBUG_PRINT;
1648 const int eci_length_segs = get_eci_length_segs(segs, seg_count);
1649 struct zint_seg *local_segs = (struct zint_seg *) z_alloca(sizeof(struct zint_seg) * seg_count);
1650 unsigned int *ddata = (unsigned int *) z_alloca(sizeof(unsigned int) * eci_length_segs);
1651 char *mode = (char *) z_alloca(eci_length_segs);
1652 char *prev_mode = (char *) z_alloca(eci_length_segs);
1653 unsigned char *datastream;
1654 unsigned char *fullstream;
1655 unsigned char *grid;
1656
1657 user_mask = (symbol->option_3 >> 8) & 0x0F; /* User mask is pattern + 1, so >= 1 and <= 8 */
1658 if (user_mask > 8) {
1659 user_mask = 0; /* Ignore */
1660 }
1661
1662 segs_cpy(symbol, segs, seg_count, local_segs); /* Shallow copy (needed to set default ECIs & protect lengths) */
1663
1664 warn_number = qr_prep_data(symbol, local_segs, seg_count, ddata);
1665 if (warn_number >= ZINT_ERROR) {
1666 return warn_number;
1667 }
1668
1669 if (symbol->structapp.count) {
1670 if (symbol->structapp.count < 2 || symbol->structapp.count > 16) {
1671 return errtxtf(ZINT_ERROR_INVALID_OPTION, symbol, 750,
1672 "Structured Append count '%d' out of range (2 to 16)", symbol->structapp.count);
1673 }
1674 if (symbol->structapp.index < 1 || symbol->structapp.index > symbol->structapp.count) {
1675 return errtxtf(ZINT_ERROR_INVALID_OPTION, symbol, 751,
1676 "Structured Append index '%1$d' out of range (1 to count %2$d)",
1677 symbol->structapp.index, symbol->structapp.count);
1678 }
1679 if (symbol->structapp.id[0]) {
1680 int id, id_len;
1681
1682 for (id_len = 1; id_len < 4 && symbol->structapp.id[id_len]; id_len++);
1683
1684 if (id_len > 3) { /* Max value 255 */
1685 return errtxtf(ZINT_ERROR_INVALID_OPTION, symbol, 752,
1686 "Structured Append ID length %d too long (3 digit maximum)", id_len);
1687 }
1688
1689 id = to_int((const unsigned char *) symbol->structapp.id, id_len);
1690 if (id == -1) {
1691 return errtxt(ZINT_ERROR_INVALID_OPTION, symbol, 753, "Invalid Structured Append ID (digits only)");
1692 }
1693 if (id > 255) {
1694 return errtxtf(ZINT_ERROR_INVALID_OPTION, symbol, 754,
1695 "Structured Append ID value '%d' out of range (0 to 255)", id);
1696 }
1697 }
1698 p_structapp = &symbol->structapp;
1699 }
1700
1701 /* GS1 General Specifications 22.0 section 5.7.3 says Structured Append and ECIs not supported
1702 for GS1 QR Code so check and return ZINT_WARN_NONCOMPLIANT if either true */
1703 if (gs1 && warn_number == 0) {
1704 for (i = 0; i < seg_count; i++) {
1705 if (local_segs[i].eci) {
1706 warn_number = errtxt(ZINT_WARN_NONCOMPLIANT, symbol, 755,
1707 "Using ECI in GS1 mode not supported by GS1 standards");
1708 break;
1709 }
1710 }
1711 if (warn_number == 0 && p_structapp) {
1712 warn_number = errtxt(ZINT_WARN_NONCOMPLIANT, symbol, 756,
1713 "Using Structured Append in GS1 mode not supported by GS1 standards");
1714 }
1715 }
1716
1717 est_binlen = qr_calc_binlen_segs(40, mode, ddata, local_segs, seg_count, p_structapp, 0 /*mode_preset*/, gs1,
1718 debug_print);
1719
1720 if ((symbol->option_1 >= 1) && (symbol->option_1 <= 4)) {
1721 ecc_level = symbol->option_1 - 1;
1722 } else {
1723 ecc_level = QR_LEVEL_L;
1724 }
1725 max_cw = qr_data_codewords[ecc_level][39];
1726
1727 if (est_binlen > (8 * max_cw)) {
1728 if (ecc_level == QR_LEVEL_L) {
1729 return errtxtf(ZINT_ERROR_TOO_LONG, symbol, 567, "Input too long, requires %1$d codewords (maximum %2$d)",
1730 (est_binlen + 7) / 8, max_cw);
1731 }
1732 return errtxtf(ZINT_ERROR_TOO_LONG, symbol, 561,
1733 "Input too long for ECC level %1$c, requires %2$d codewords (maximum %3$d)",
1734 qr_ecc_level_names[ecc_level], (est_binlen + 7) / 8, max_cw);
1735 }
1736
1737 autosize = 40;
1738 for (i = 39; i >= 0; i--) {
1739 if ((8 * qr_data_codewords[ecc_level][i]) >= est_binlen) {
1740 autosize = i + 1;
1741 }
1742 }
1743 if (autosize != 40) {
1744 /* Save version 40 estimate in case incorrect costings in `qr_define_mode()` lead to its `mode` being better
1745 than current lower version one */
1746 prev_est_binlen = est_binlen;
1747 est_binlen = qr_calc_binlen_segs(autosize, mode, ddata, local_segs, seg_count, p_structapp, 0 /*mode_preset*/,
1748 gs1, debug_print);
1749 if (prev_est_binlen < est_binlen) { /* Shouldn't happen */
1750 assert(0); /* Not reached (hopefully) */
1751 /* Defensively use version 40 `mode` to avoid crashes (ticket #300) */
1752 est_binlen = qr_calc_binlen_segs(40, mode, ddata, local_segs, seg_count, p_structapp, 0 /*mode_preset*/,
1753 gs1, debug_print);
1754 assert(est_binlen == prev_est_binlen);
1755 }
1756 }
1757
1758 /* Now see if the optimised binary will fit in a smaller symbol. */
1759 canShrink = 1;
1760
1761 do {
1762 if (autosize == 1) {
1763 canShrink = 0;
1764 } else {
1765 prev_est_binlen = est_binlen;
1766 memcpy(prev_mode, mode, eci_length_segs);
1767 est_binlen = qr_calc_binlen_segs(autosize - 1, mode, ddata, local_segs, seg_count, p_structapp,
1768 0 /*mode_preset*/, gs1, debug_print);
1769
1770 if ((8 * qr_data_codewords[ecc_level][autosize - 2]) < est_binlen) {
1771 canShrink = 0;
1772 }
1773
1774 if (canShrink == 1) {
1775 /* Optimisation worked - data will fit in a smaller symbol */
1776 autosize--;
1777 } else {
1778 /* Data did not fit in the smaller symbol, revert to original size */
1779 est_binlen = prev_est_binlen;
1780 memcpy(mode, prev_mode, eci_length_segs);
1781 }
1782 }
1783 } while (canShrink == 1);
1784
1785 version = autosize;
1786
1787 if ((symbol->option_2 >= 1) && (symbol->option_2 <= 40)) {
1788 /* If the user has selected a larger symbol than the smallest available,
1789 then use the size the user has selected, and re-optimise for this
1790 symbol size.
1791 */
1792 if (symbol->option_2 > version) {
1793 version = symbol->option_2;
1794 est_binlen = qr_calc_binlen_segs(symbol->option_2, mode, ddata, local_segs, seg_count, p_structapp,
1795 0 /*mode_preset*/, gs1, debug_print);
1796 }
1797
1798 if (symbol->option_2 < version) {
1799 return errtxtf(ZINT_ERROR_TOO_LONG, symbol, 569,
1800 "Input too long for Version %1$d-%2$c, requires %3$d codewords (maximum %4$d)",
1801 symbol->option_2, qr_ecc_level_names[ecc_level], (est_binlen + 7) / 8,
1802 qr_data_codewords[ecc_level][symbol->option_2 - 1]);
1803 }
1804 }
1805
1806 /* Ensure maxium error correction capacity unless user-specified */
1807 if (symbol->option_1 == -1 || symbol->option_1 - 1 != ecc_level) {
1808 if (est_binlen <= qr_data_codewords[QR_LEVEL_H][version - 1] * 8) {
1809 ecc_level = QR_LEVEL_H;
1810 } else if (est_binlen <= qr_data_codewords[QR_LEVEL_Q][version - 1] * 8) {
1811 ecc_level = QR_LEVEL_Q;
1812 } else if (est_binlen <= qr_data_codewords[QR_LEVEL_M][version - 1] * 8) {
1813 ecc_level = QR_LEVEL_M;
1814 }
1815 }
1816
1817 target_codewords = qr_data_codewords[ecc_level][version - 1];
1818 blocks = qr_blocks[ecc_level][version - 1];
1819
1820 if (debug_print) {
1821 printf("Minimum codewords: %d\n", (est_binlen + 7) / 8);
1822 printf("Selected version: %d-%c (%dx%d)\n",
1823 version, qr_ecc_level_names[ecc_level], qr_sizes[version - 1], qr_sizes[version - 1]);
1824 printf("Number of data codewords in symbol: %d\n", target_codewords);
1825 printf("Number of ECC blocks: %d\n", blocks);
1826 }
1827
1828 datastream = (unsigned char *) z_alloca(target_codewords + 1);
1829 fullstream = (unsigned char *) z_alloca(qr_total_codewords[version - 1] + 1);
1830
1831 (void) qr_binary_segs(datastream, version, target_codewords, mode, ddata, local_segs, seg_count, p_structapp, gs1,
1832 est_binlen, debug_print);
1833 #ifdef ZINT_TEST
1834 if (symbol->debug & ZINT_DEBUG_TEST) debug_test_codeword_dump(symbol, datastream, target_codewords);
1835 #endif
1836 qr_add_ecc(fullstream, datastream, version, target_codewords, blocks, debug_print);
1837
1838 size = qr_sizes[version - 1];
1839 size_squared = size * size;
1840
1841 grid = (unsigned char *) z_alloca(size_squared);
1842 memset(grid, 0, size_squared);
1843
1844 qr_setup_grid(grid, size, version);
1845 qr_populate_grid(grid, size, size, fullstream, qr_total_codewords[version - 1]);
1846
1847 if (version >= 7) {
1848 qr_add_version_info(grid, size, version);
1849 }
1850
1851 bitmask = qr_apply_bitmask(grid, size, ecc_level, user_mask, fast_encode, debug_print);
1852
1853 qr_add_format_info(grid, size, ecc_level, bitmask);
1854
1855 symbol->width = size;
1856 symbol->rows = size;
1857
1858 for (i = 0; i < size; i++) {
1859 int r = i * size;
1860 for (j = 0; j < size; j++) {
1861 if (grid[r + j] & 0x01) {
1862 set_module(symbol, i, j);
1863 }
1864 }
1865 symbol->row_height[i] = 1;
1866 }
1867 symbol->height = size;
1868
1869 return warn_number;
1870 }
1871
1872 /* Write terminator, padding & ECC */
1873 static int microqr_end(struct zint_symbol *symbol, char binary_data[], int bp, const int ecc_level,
1874 const int version) {
1875 int i, j;
1876 int bits_left;
1877 unsigned char data_blocks[17];
1878 unsigned char ecc_blocks[15];
1879 rs_t rs;
1880
1881 const int terminator_bits = qr_terminator_bits(MICROQR_VERSION + version);
1882 const int bits_total = microqr_data[ecc_level][version][0];
1883 const int data_codewords = microqr_data[ecc_level][version][1];
1884 const int ecc_codewords = microqr_data[ecc_level][version][2];
1885 const int bits_end = version == 0 || version == 2 ? 4 : 8;
1886
1887 /* Add terminator */
1888 bits_left = bits_total - bp;
1889 if (bits_left <= terminator_bits) {
1890 if (bits_left) {
1891 bp = bin_append_posn(0, bits_left, binary_data, bp);
1892 bits_left = 0;
1893 }
1894 } else {
1895 bp = bin_append_posn(0, terminator_bits, binary_data, bp);
1896 bits_left -= terminator_bits;
1897 }
1898
1899 if (symbol->debug & ZINT_DEBUG_PRINT) {
1900 printf("M%d Terminated binary (%d): %.*s (bits_left %d)\n", version + 1, bp, bp, binary_data, bits_left);
1901 }
1902
1903 /* Manage last (4-bit) block */
1904 if (bits_end == 4 && bits_left && bits_left <= 4) {
1905 bp = bin_append_posn(0, bits_left, binary_data, bp);
1906 bits_left = 0;
1907 }
1908
1909 if (bits_left) {
1910 /* Complete current byte */
1911 int remainder = 8 - (bp % 8);
1912 if (remainder != 8) {
1913 bp = bin_append_posn(0, remainder, binary_data, bp);
1914 bits_left -= remainder;
1915 }
1916
1917 /* Add padding */
1918 if (bits_end == 4 && bits_left > 4) {
1919 bits_left -= 4;
1920 }
1921 remainder = bits_left / 8;
1922 for (i = 0; i < remainder; i++) {
1923 bp = bin_append_posn(i & 1 ? 0x11 : 0xEC, 8, binary_data, bp);
1924 }
1925 if (bits_end == 4) {
1926 bp = bin_append_posn(0, 4, binary_data, bp);
1927 }
1928 }
1929 assert((bp & 0x07) == 8 - bits_end);
1930
1931 /* Copy data into codewords */
1932 for (i = 0; i < data_codewords; i++) {
1933 const int bits = i + 1 == data_codewords ? bits_end : 8;
1934 data_blocks[i] = 0;
1935
1936 for (j = 0; j < bits; j++) {
1937 if (binary_data[(i * 8) + j] == '1') {
1938 data_blocks[i] |= 0x80 >> j;
1939 }
1940 }
1941 }
1942 #ifdef ZINT_TEST
1943 if (symbol->debug & ZINT_DEBUG_TEST) {
1944 char bp_buf[10];
1945 debug_test_codeword_dump(symbol, data_blocks, data_codewords);
1946 sprintf(bp_buf, "%d", bp); /* Append `bp` to detect padding errors */
1947 errtxt_adj(0, symbol, "%s (%s)", bp_buf);
1948 }
1949 #endif
1950
1951 /* Calculate Reed-Solomon error codewords */
1952 rs_init_gf(&rs, 0x11d);
1953 rs_init_code(&rs, ecc_codewords, 0);
1954 rs_encode(&rs, data_codewords, data_blocks, ecc_blocks);
1955
1956 /* Add Reed-Solomon codewords to binary data */
1957 for (i = 0; i < ecc_codewords; i++) {
1958 bp = bin_append_posn(ecc_blocks[i], 8, binary_data, bp);
1959 }
1960
1961 return bp;
1962 }
1963
1964 static void microqr_setup_grid(unsigned char *grid, const int size) {
1965 int i, toggle = 1;
1966
1967 /* Add timing patterns */
1968 for (i = 0; i < size; i++) {
1969 if (toggle == 1) {
1970 grid[i] = 0x21;
1971 grid[(i * size)] = 0x21;
1972 toggle = 0;
1973 } else {
1974 grid[i] = 0x20;
1975 grid[(i * size)] = 0x20;
1976 toggle = 1;
1977 }
1978 }
1979
1980 /* Add finder patterns */
1981 qr_place_finder(grid, size, 0, 0);
1982
1983 /* Add separators */
1984 for (i = 0; i < 7; i++) {
1985 grid[(7 * size) + i] = 0x10;
1986 grid[(i * size) + 7] = 0x10;
1987 }
1988 grid[(7 * size) + 7] = 0x10;
1989
1990
1991 /* Reserve space for format information */
1992 for (i = 0; i < 8; i++) {
1993 grid[(8 * size) + i] |= 0x20;
1994 grid[(i * size) + 8] |= 0x20;
1995 }
1996 grid[(8 * size) + 8] |= 20;
1997 }
1998
1999 static void microqr_populate_grid(unsigned char *grid, const int size, const char full_stream[], int bp) {
2000 int direction = 1; /* up */
2001 int row = 0; /* right hand side */
2002 int i;
2003 int y;
2004
2005 y = size - 1;
2006 i = 0;
2007 do {
2008 int x = (size - 2) - (row * 2);
2009
2010 if (!(grid[(y * size) + (x + 1)] & 0xf0)) {
2011 if (full_stream[i] == '1') {
2012 grid[(y * size) + (x + 1)] = 0x01;
2013 } else {
2014 grid[(y * size) + (x + 1)] = 0x00;
2015 }
2016 i++;
2017 }
2018
2019 if (i < bp) {
2020 if (!(grid[(y * size) + x] & 0xf0)) {
2021 if (full_stream[i] == '1') {
2022 grid[(y * size) + x] = 0x01;
2023 } else {
2024 grid[(y * size) + x] = 0x00;
2025 }
2026 i++;
2027 }
2028 }
2029
2030 if (direction) {
2031 y--;
2032 } else {
2033 y++;
2034 }
2035 if (y == 0) {
2036 /* reached the top */
2037 row++;
2038 y = 1;
2039 direction = 0;
2040 }
2041 if (y == size) {
2042 /* reached the bottom */
2043 row++;
2044 y = size - 1;
2045 direction = 1;
2046 }
2047 } while (i < bp);
2048 }
2049
2050 static int microqr_evaluate(const unsigned char *grid, const int size, const int pattern) {
2051 int sum1, sum2, i, filter = 0, retval;
2052
2053 switch (pattern) {
2054 case 0: filter = 0x01;
2055 break;
2056 case 1: filter = 0x02;
2057 break;
2058 case 2: filter = 0x04;
2059 break;
2060 case 3: filter = 0x08;
2061 break;
2062 }
2063
2064 sum1 = 0;
2065 sum2 = 0;
2066 for (i = 1; i < size; i++) {
2067 if (grid[(i * size) + size - 1] & filter) {
2068 sum1++;
2069 }
2070 if (grid[((size - 1) * size) + i] & filter) {
2071 sum2++;
2072 }
2073 }
2074
2075 if (sum1 <= sum2) {
2076 retval = (sum1 * 16) + sum2;
2077 } else {
2078 retval = (sum2 * 16) + sum1;
2079 }
2080
2081 return retval;
2082 }
2083
2084 static int microqr_apply_bitmask(unsigned char *grid, const int size, const int user_mask, const int debug_print) {
2085 int x, y;
2086 int r, k;
2087 int bit;
2088 int pattern, value[4];
2089 int best_pattern;
2090 int size_squared = size * size;
2091 unsigned char *mask = (unsigned char *) z_alloca(size_squared);
2092 unsigned char *eval = (unsigned char *) z_alloca(size_squared);
2093
2094 /* Perform data masking */
2095 memset(mask, 0, size_squared);
2096 for (y = 0; y < size; y++) {
2097 r = y * size;
2098 for (x = 0; x < size; x++) {
2099
2100 if (!(grid[r + x] & 0xf0)) {
2101 if ((y & 1) == 0) {
2102 mask[r + x] |= 0x01;
2103 }
2104
2105 if ((((y / 2) + (x / 3)) & 1) == 0) {
2106 mask[r + x] |= 0x02;
2107 }
2108
2109 if (((((y * x) & 1) + ((y * x) % 3)) & 1) == 0) {
2110 mask[r + x] |= 0x04;
2111 }
2112
2113 if (((((y + x) & 1) + ((y * x) % 3)) & 1) == 0) {
2114 mask[r + x] |= 0x08;
2115 }
2116 }
2117 }
2118 }
2119
2120 if (user_mask) {
2121 best_pattern = user_mask - 1;
2122 } else {
2123 for (k = 0; k < size_squared; k++) {
2124 if (grid[k] & 0x01) {
2125 eval[k] = mask[k] ^ 0xff;
2126 } else {
2127 eval[k] = mask[k];
2128 }
2129 }
2130
2131
2132 /* Evaluate result */
2133 best_pattern = 0;
2134 for (pattern = 0; pattern < 4; pattern++) {
2135 value[pattern] = microqr_evaluate(eval, size, pattern);
2136 if (value[pattern] > value[best_pattern]) {
2137 best_pattern = pattern;
2138 }
2139 }
2140 }
2141
2142 if (debug_print) {
2143 printf("Mask: %d (%s)", best_pattern, user_mask ? "specified" : "automatic");
2144 if (!user_mask) {
2145 for (pattern = 0; pattern < 4; pattern++) printf(" %d:%d", pattern, value[pattern]);
2146 }
2147 fputc('\n', stdout);
2148 }
2149
2150 /* Apply mask */
2151 bit = 1 << best_pattern;
2152 for (k = 0; k < size_squared; k++) {
2153 if (mask[k] & bit) {
2154 grid[k] ^= 0x01;
2155 }
2156 }
2157
2158 return best_pattern;
2159 }
2160
2161 INTERNAL int microqr(struct zint_symbol *symbol, unsigned char source[], int length) {
2162 int i, size, j;
2163 char full_stream[200];
2164 int bp;
2165 int full_multibyte;
2166 int user_mask;
2167
2168 unsigned int ddata[40];
2169 char mode[40];
2170 int alpha_used = 0, byte_or_kanji_used = 0;
2171 int version_valid[4];
2172 int binary_count[4];
2173 int ecc_level, version;
2174 int bitmask, format, format_full;
2175 int size_squared;
2176 struct zint_seg segs[1];
2177 const int seg_count = 1;
2178 const int debug_print = symbol->debug & ZINT_DEBUG_PRINT;
2179 unsigned char *grid;
2180
2181 if (length > 35) {
2182 return errtxtf(ZINT_ERROR_TOO_LONG, symbol, 562, "Input length %d too long (maximum 35)", length);
2183 }
2184
2185 /* Check option 1 in combination with option 2 */
2186 ecc_level = QR_LEVEL_L;
2187 if (symbol->option_1 >= 1 && symbol->option_1 <= 4) {
2188 if (symbol->option_1 == 4) {
2189 return errtxt(ZINT_ERROR_INVALID_OPTION, symbol, 566, "Error correction level H not available");
2190 }
2191 if (symbol->option_2 >= 1 && symbol->option_2 <= 4) {
2192 if (symbol->option_2 == 1 && symbol->option_1 != 1) {
2193 return errtxt(ZINT_ERROR_INVALID_OPTION, symbol, 574,
2194 "Version M1 supports error correction level L only");
2195 }
2196 if (symbol->option_2 != 4 && symbol->option_1 == 3) {
2197 return errtxt(ZINT_ERROR_INVALID_OPTION, symbol, 563, "Error correction level Q requires Version M4");
2198 }
2199 }
2200 ecc_level = symbol->option_1 - 1;
2201 }
2202
2203 /* If ZINT_FULL_MULTIBYTE use Kanji mode in DATA_MODE or for non-Shift JIS in UNICODE_MODE */
2204 full_multibyte = (symbol->option_3 & 0xFF) == ZINT_FULL_MULTIBYTE;
2205 user_mask = (symbol->option_3 >> 8) & 0x0F; /* User mask is pattern + 1, so >= 1 and <= 4 */
2206 if (user_mask > 4) {
2207 user_mask = 0; /* Ignore */
2208 }
2209
2210 if ((symbol->input_mode & 0x07) == DATA_MODE) {
2211 sjis_cpy(source, &length, ddata, full_multibyte);
2212 } else {
2213 /* Try ISO 8859-1 conversion first */
2214 int error_number = sjis_utf8_to_eci(3, source, &length, ddata, full_multibyte);
2215 if (error_number != 0) {
2216 /* Try Shift-JIS */
2217 error_number = sjis_utf8(symbol, source, &length, ddata);
2218 if (error_number != 0) {
2219 return error_number;
2220 }
2221 }
2222 }
2223
2224 /* Determine if alpha (excluding numerics), byte or kanji used */
2225 for (i = 0; i < length && (alpha_used == 0 || byte_or_kanji_used == 0); i++) {
2226 if (!z_isdigit(ddata[i])) {
2227 if (qr_is_alpha(ddata[i], 0 /*gs1*/)) {
2228 alpha_used = 1;
2229 } else {
2230 byte_or_kanji_used = 1;
2231 }
2232 }
2233 }
2234
2235 for (i = 0; i < 4; i++) {
2236 version_valid[i] = 1;
2237 }
2238
2239 /* Eliminate possible versions depending on type of content */
2240 if (byte_or_kanji_used) {
2241 version_valid[0] = 0;
2242 version_valid[1] = 0;
2243 } else if (alpha_used) {
2244 version_valid[0] = 0;
2245 }
2246
2247 /* Eliminate possible versions depending on error correction level specified */
2248 if (ecc_level == QR_LEVEL_Q) {
2249 version_valid[0] = 0;
2250 version_valid[1] = 0;
2251 version_valid[2] = 0;
2252 } else if (ecc_level == QR_LEVEL_M) {
2253 version_valid[0] = 0;
2254 }
2255
2256 segs[0].source = source;
2257 segs[0].length = length;
2258 segs[0].eci = 0;
2259
2260 /* Determine length of binary data */
2261 for (i = 0; i < 4; i++) {
2262 if (version_valid[i]) {
2263 binary_count[i] = qr_calc_binlen_segs(MICROQR_VERSION + i, mode, ddata, segs, seg_count,
2264 NULL /*p_structapp*/, 0 /*mode_preset*/, 0 /*gs1*/, debug_print);
2265 } else {
2266 binary_count[i] = 128 + 1;
2267 }
2268 }
2269
2270 /* Eliminate possible versions depending on binary length and error correction level specified */
2271 if (binary_count[3] > microqr_data[ecc_level][3][0]) {
2272 return errtxtf(ZINT_ERROR_TOO_LONG, symbol, 565,
2273 "Input too long for Version M4-%1$c, requires %2$d codewords (maximum %3$d)",
2274 qr_ecc_level_names[ecc_level], (binary_count[3] + 7) / 8, microqr_data[ecc_level][3][1]);
2275 }
2276 for (i = 0; i < 3; i++) {
2277 if (binary_count[i] > microqr_data[ecc_level][i][0]) {
2278 version_valid[i] = 0;
2279 }
2280 }
2281
2282 /* Auto-select lowest valid size */
2283 version = 3;
2284 if (version_valid[2]) {
2285 version = 2;
2286 }
2287 if (version_valid[1]) {
2288 version = 1;
2289 }
2290 if (version_valid[0]) {
2291 version = 0;
2292 }
2293
2294 /* Get version from user */
2295 if ((symbol->option_2 >= 1) && (symbol->option_2 <= 4)) {
2296 if (symbol->option_2 == 1 && (i = not_sane(NEON_F, source, length))) {
2297 return errtxtf(ZINT_ERROR_INVALID_DATA, symbol, 758,
2298 "Invalid character at position %d in input for Version M1 (digits only)", i);
2299 } else if (symbol->option_2 == 2 && not_sane(QR_ALPHA, source, length)) {
2300 return errtxt(ZINT_ERROR_INVALID_DATA, symbol, 759,
2301 "Invalid character in input for Version M2 (digits, A-Z, space and \"$%*+-./:\" only)");
2302 }
2303 if (symbol->option_2 - 1 >= version) {
2304 version = symbol->option_2 - 1;
2305 } else {
2306 return errtxtf(ZINT_ERROR_TOO_LONG, symbol, 570,
2307 "Input too long for Version M%1$d-%2$c, requires %3$d codewords (maximum %4$d)",
2308 symbol->option_2, qr_ecc_level_names[ecc_level], (binary_count[version] + 7) / 8,
2309 microqr_data[ecc_level][symbol->option_2 - 1][1]);
2310 }
2311 }
2312
2313 /* If there is enough unused space then increase the error correction level, unless user-specified */
2314 if (version && (symbol->option_1 == -1 || symbol->option_1 - 1 != ecc_level)) {
2315 if (binary_count[version] <= microqr_data[QR_LEVEL_Q][version][0]) {
2316 ecc_level = QR_LEVEL_Q;
2317 } else if (binary_count[version] <= microqr_data[QR_LEVEL_M][version][0]) {
2318 ecc_level = QR_LEVEL_M;
2319 }
2320 }
2321
2322 qr_define_mode(mode, ddata, length, 0 /*gs1*/, MICROQR_VERSION + version, debug_print);
2323
2324 bp = qr_binary_segs((unsigned char *) full_stream, MICROQR_VERSION + version, 0 /*target_codewords*/, mode, ddata,
2325 segs, seg_count, NULL /*p_structapp*/, 0 /*gs1*/, binary_count[version], debug_print);
2326
2327 if (debug_print) printf("Binary (%d): %.*s\n", bp, bp, full_stream);
2328
2329 bp = microqr_end(symbol, full_stream, bp, ecc_level, version);
2330
2331 size = microqr_sizes[version];
2332 size_squared = size * size;
2333
2334 grid = (unsigned char *) z_alloca(size_squared);
2335 memset(grid, 0, size_squared);
2336
2337 microqr_setup_grid(grid, size);
2338 microqr_populate_grid(grid, size, full_stream, bp);
2339 bitmask = microqr_apply_bitmask(grid, size, user_mask, debug_print);
2340
2341 /* Add format data */
2342 format = version ? (version - 1) * 2 + ecc_level + 1 : 0;
2343
2344 if (debug_print) {
2345 printf("Version: M%d-%c, Size: %dx%d, Format: %d\n",
2346 version + 1, qr_ecc_level_names[ecc_level], size, size, format);
2347 }
2348
2349 format_full = qr_annex_c1[(format << 2) + bitmask];
2350
2351 for (i = 1; i <= 8; i++) {
2352 grid[(8 * size) + i] |= (format_full >> (15 - i)) & 0x01;
2353 }
2354 for (i = 7; i >= 1; i--) {
2355 grid[(i * size) + 8] |= (format_full >> (i - 1)) & 0x01;
2356 }
2357
2358 symbol->width = size;
2359 symbol->rows = size;
2360
2361 for (i = 0; i < size; i++) {
2362 for (j = 0; j < size; j++) {
2363 if (grid[(i * size) + j] & 0x01) {
2364 set_module(symbol, i, j);
2365 }
2366 }
2367 symbol->row_height[i] = 1;
2368 }
2369 symbol->height = size;
2370
2371 return 0;
2372 }
2373
2374 /* For UPNQR the symbol size and error correction capacity is fixed */
2375 INTERNAL int upnqr(struct zint_symbol *symbol, unsigned char source[], int length) {
2376 int i, j, r, est_binlen;
2377 int ecc_level, version, target_codewords, blocks, size;
2378 int bitmask, error_number;
2379 int user_mask;
2380 int size_squared;
2381 struct zint_seg segs[1];
2382 const int seg_count = 1;
2383 const int fast_encode = symbol->input_mode & FAST_MODE;
2384 const int debug_print = symbol->debug & ZINT_DEBUG_PRINT;
2385 unsigned char *datastream;
2386 unsigned char *fullstream;
2387 unsigned char *grid;
2388 unsigned int *ddata = (unsigned int *) z_alloca(sizeof(unsigned int) * length);
2389 char *mode = (char *) z_alloca(length + 1);
2390 unsigned char *preprocessed = (unsigned char *) z_alloca(length + 1);
2391
2392 symbol->eci = 4; /* Set before any processing */
2393
2394 user_mask = (symbol->option_3 >> 8) & 0x0F; /* User mask is pattern + 1, so >= 1 and <= 8 */
2395 if (user_mask > 8) {
2396 user_mask = 0; /* Ignore */
2397 }
2398
2399 switch (symbol->input_mode & 0x07) {
2400 case DATA_MODE:
2401 /* Input is already in ISO-8859-2 format */
2402 for (i = 0; i < length; i++) {
2403 ddata[i] = source[i];
2404 mode[i] = 'B';
2405 }
2406 break;
2407 case GS1_MODE: /* Should never happen as checked before being called */
2408 return errtxt(ZINT_ERROR_INVALID_OPTION, symbol, 571,
2409 "UPNQR does not support GS1 data"); /* Not reached */
2410 break;
2411 case UNICODE_MODE:
2412 error_number = utf8_to_eci(4, source, preprocessed, &length);
2413 if (error_number != 0) {
2414 return errtxt(error_number, symbol, 572, "Invalid character in input for ECI '4'");
2415 }
2416 for (i = 0; i < length; i++) {
2417 ddata[i] = preprocessed[i];
2418 mode[i] = 'B';
2419 }
2420 break;
2421 }
2422
2423 segs[0].source = source;
2424 segs[0].length = length;
2425 segs[0].eci = 4;
2426
2427 est_binlen = qr_calc_binlen_segs(15, mode, ddata, segs, seg_count, NULL /*p_structapp*/, 1 /*mode_preset*/,
2428 0 /*gs1*/, debug_print);
2429
2430 ecc_level = QR_LEVEL_M;
2431
2432 if (est_binlen > 3320) {
2433 return errtxtf(ZINT_ERROR_TOO_LONG, symbol, 573, "Input too long, requires %d codewords (maximum 415)",
2434 (est_binlen + 7) / 8);
2435 }
2436
2437 version = 15; /* 77 x 77 */
2438
2439 target_codewords = qr_data_codewords[ecc_level][version - 1];
2440 blocks = qr_blocks[ecc_level][version - 1];
2441
2442 datastream = (unsigned char *) z_alloca(target_codewords + 1);
2443 fullstream = (unsigned char *) z_alloca(qr_total_codewords[version - 1] + 1);
2444
2445 (void) qr_binary_segs(datastream, version, target_codewords, mode, ddata, segs, seg_count, NULL /*p_structapp*/,
2446 0 /*gs1*/, est_binlen, debug_print);
2447 #ifdef ZINT_TEST
2448 if (symbol->debug & ZINT_DEBUG_TEST) debug_test_codeword_dump(symbol, datastream, target_codewords);
2449 #endif
2450 qr_add_ecc(fullstream, datastream, version, target_codewords, blocks, debug_print);
2451
2452 size = qr_sizes[version - 1];
2453 size_squared = size * size;
2454
2455 grid = (unsigned char *) z_alloca(size_squared);
2456 memset(grid, 0, size_squared);
2457
2458 qr_setup_grid(grid, size, version);
2459 qr_populate_grid(grid, size, size, fullstream, qr_total_codewords[version - 1]);
2460
2461 qr_add_version_info(grid, size, version);
2462
2463 bitmask = qr_apply_bitmask(grid, size, ecc_level, user_mask, fast_encode, debug_print);
2464
2465 qr_add_format_info(grid, size, ecc_level, bitmask);
2466
2467 symbol->width = size;
2468 symbol->rows = size;
2469
2470 for (i = 0; i < size; i++) {
2471 r = i * size;
2472 for (j = 0; j < size; j++) {
2473 if (grid[r + j] & 0x01) {
2474 set_module(symbol, i, j);
2475 }
2476 }
2477 symbol->row_height[i] = 1;
2478 }
2479 symbol->height = size;
2480
2481 return 0;
2482 }
2483
2484 static const char rmqr_version_names[38][8] = {
2485 "R7x43", "R7x59", "R7x77", "R7x99", "R7x139", "R9x43", "R9x59", "R9x77",
2486 "R9x99", "R9x139", "R11x27", "R11x43", "R11x59", "R11x77", "R11x99", "R11x139",
2487 "R13x27", "R13x43", "R13x59", "R13x77", "R13x99", "R13x139", "R15x43", "R15x59",
2488 "R15x77", "R15x99", "R15x139", "R17x43", "R17x59", "R17x77", "R17x99", "R17x139",
2489 "R7xW", "R9xW", "R11xW", "R13xW", "R15xW", "R17xW",
2490 };
2491
2492 static void rmqr_setup_grid(unsigned char *grid, const int h_size, const int v_size) {
2493 int i, j;
2494 char alignment[] = {0x1F, 0x11, 0x15, 0x11, 0x1F};
2495 int h_version, finder_position;
2496
2497 /* Add timing patterns - top and bottom */
2498 for (i = 0; i < h_size; i++) {
2499 if (i % 2) {
2500 grid[i] = 0x20;
2501 grid[((v_size - 1) * h_size) + i] = 0x20;
2502 } else {
2503 grid[i] = 0x21;
2504 grid[((v_size - 1) * h_size) + i] = 0x21;
2505 }
2506 }
2507
2508 /* Add timing patterns - left and right */
2509 for (i = 0; i < v_size; i++) {
2510 if (i % 2) {
2511 grid[i * h_size] = 0x20;
2512 grid[(i * h_size) + (h_size - 1)] = 0x20;
2513 } else {
2514 grid[i * h_size] = 0x21;
2515 grid[(i * h_size) + (h_size - 1)] = 0x21;
2516 }
2517 }
2518
2519 /* Add finder pattern */
2520 qr_place_finder(grid, h_size, 0, 0); /* This works because finder is always top left */
2521
2522 /* Add finder sub-pattern to bottom right */
2523 for (i = 0; i < 5; i++) {
2524 for (j = 0; j < 5; j++) {
2525 if (alignment[j] & 0x10 >> i) {
2526 grid[((v_size - 5) * h_size) + (h_size * i) + (h_size - 5) + j] = 0x11;
2527 } else {
2528 grid[((v_size - 5) * h_size) + (h_size * i) + (h_size - 5) + j] = 0x10;
2529 }
2530 }
2531 }
2532
2533 /* Add corner finder pattern - bottom left */
2534 grid[(v_size - 2) * h_size] = 0x11;
2535 grid[((v_size - 2) * h_size) + 1] = 0x10;
2536 grid[((v_size - 1) * h_size) + 1] = 0x11;
2537
2538 /* Add corner finder pattern - top right */
2539 grid[h_size - 2] = 0x11;
2540 grid[(h_size * 2) - 2] = 0x10;
2541 grid[(h_size * 2) - 1] = 0x11;
2542
2543 /* Add seperator */
2544 for (i = 0; i < 7; i++) {
2545 grid[(i * h_size) + 7] = 0x20;
2546 }
2547 if (v_size > 7) {
2548 /* Note for v_size = 9 this overrides the bottom right corner finder pattern */
2549 for (i = 0; i < 8; i++) {
2550 grid[(7 * h_size) + i] = 0x20;
2551 }
2552 }
2553
2554 /* Add alignment patterns */
2555 if (h_size > 27) {
2556 h_version = 0; /* Suppress compiler warning [-Wmaybe-uninitialized] */
2557 for (i = 0; i < 5; i++) {
2558 if (h_size == rmqr_width[i]) {
2559 h_version = i;
2560 break;
2561 }
2562 }
2563
2564 for (i = 0; i < 4; i++) {
2565 finder_position = rmqr_table_d1[(h_version * 4) + i];
2566
2567 if (finder_position != 0) {
2568 for (j = 0; j < v_size; j++) {
2569 if (j % 2) {
2570 grid[(j * h_size) + finder_position] = 0x10;
2571 } else {
2572 grid[(j * h_size) + finder_position] = 0x11;
2573 }
2574 }
2575
2576 /* Top square */
2577 grid[h_size + finder_position - 1] = 0x11;
2578 grid[(h_size * 2) + finder_position - 1] = 0x11;
2579 grid[h_size + finder_position + 1] = 0x11;
2580 grid[(h_size * 2) + finder_position + 1] = 0x11;
2581
2582 /* Bottom square */
2583 grid[(h_size * (v_size - 3)) + finder_position - 1] = 0x11;
2584 grid[(h_size * (v_size - 2)) + finder_position - 1] = 0x11;
2585 grid[(h_size * (v_size - 3)) + finder_position + 1] = 0x11;
2586 grid[(h_size * (v_size - 2)) + finder_position + 1] = 0x11;
2587 }
2588 }
2589 }
2590
2591 /* Reserve space for format information */
2592 for (i = 0; i < 5; i++) {
2593 for (j = 0; j < 3; j++) {
2594 grid[(h_size * (i + 1)) + j + 8] = 0x20;
2595 grid[(h_size * (v_size - 6)) + (h_size * i) + j + (h_size - 8)] = 0x20;
2596 }
2597 }
2598 grid[(h_size * 1) + 11] = 0x20;
2599 grid[(h_size * 2) + 11] = 0x20;
2600 grid[(h_size * 3) + 11] = 0x20;
2601 grid[(h_size * (v_size - 6)) + (h_size - 5)] = 0x20;
2602 grid[(h_size * (v_size - 6)) + (h_size - 4)] = 0x20;
2603 grid[(h_size * (v_size - 6)) + (h_size - 3)] = 0x20;
2604 }
2605
2606 /* rMQR according to 2018 draft standard */
2607 INTERNAL int rmqr(struct zint_symbol *symbol, struct zint_seg segs[], const int seg_count) {
2608 int warn_number;
2609 int i, j, est_binlen;
2610 int ecc_level, autosize, version, max_cw, target_codewords, blocks, h_size, v_size;
2611 int footprint, best_footprint, format_data;
2612 unsigned int left_format_info, right_format_info;
2613 const int gs1 = ((symbol->input_mode & 0x07) == GS1_MODE);
2614 const int debug_print = symbol->debug & ZINT_DEBUG_PRINT;
2615 const int eci_length_segs = get_eci_length_segs(segs, seg_count);
2616 struct zint_seg *local_segs = (struct zint_seg *) z_alloca(sizeof(struct zint_seg) * seg_count);
2617 unsigned int *ddata = (unsigned int *) z_alloca(sizeof(unsigned int) * eci_length_segs);
2618 char *mode = (char *) z_alloca(eci_length_segs);
2619 unsigned char *datastream;
2620 unsigned char *fullstream;
2621 unsigned char *grid;
2622
2623 if (symbol->option_1 == 1) {
2624 return errtxt(ZINT_ERROR_INVALID_OPTION, symbol, 576, "Error correction level L not available in rMQR");
2625 }
2626 if (symbol->option_1 == 3) {
2627 return errtxt(ZINT_ERROR_INVALID_OPTION, symbol, 577, "Error correction level Q not available in rMQR");
2628 }
2629
2630 if ((symbol->option_2 < 0) || (symbol->option_2 > 38)) {
2631 return errtxtf(ZINT_ERROR_INVALID_OPTION, symbol, 579, "Version '%d' out of range (1 to 38)",
2632 symbol->option_2);
2633 }
2634
2635 segs_cpy(symbol, segs, seg_count, local_segs);
2636
2637 warn_number = qr_prep_data(symbol, local_segs, seg_count, ddata);
2638 if (warn_number >= ZINT_ERROR) {
2639 return warn_number;
2640 }
2641
2642 /* GS1 General Specifications 22.0 section 5.7.3 says ECIs not supported
2643 for GS1 QR Code so check and return ZINT_WARN_NONCOMPLIANT if true */
2644 if (gs1 && warn_number == 0) {
2645 for (i = 0; i < seg_count; i++) {
2646 if (local_segs[i].eci) {
2647 warn_number = errtxt(ZINT_WARN_NONCOMPLIANT, symbol, 757,
2648 "Using ECI in GS1 mode not supported by GS1 standards");
2649 break;
2650 }
2651 }
2652 }
2653
2654 est_binlen = qr_calc_binlen_segs(RMQR_VERSION + 31, mode, ddata, local_segs, seg_count, NULL /*p_structapp*/,
2655 0 /*mode_preset*/, gs1, debug_print);
2656
2657 ecc_level = symbol->option_1 == 4 ? QR_LEVEL_H : QR_LEVEL_M;
2658 max_cw = rmqr_data_codewords[ecc_level >> 1][31];
2659
2660 if (est_binlen > (8 * max_cw)) {
2661 return errtxtf(ZINT_ERROR_TOO_LONG, symbol, 578,
2662 "Input too long for ECC level %1$c, requires %2$d codewords (maximum %3$d)",
2663 qr_ecc_level_names[ecc_level], (est_binlen + 7) / 8, max_cw);
2664 }
2665
2666 version = 31; /* Set default to keep compiler happy */
2667
2668 if (symbol->option_2 == 0) {
2669 /* Automatic symbol size */
2670 autosize = 31;
2671 best_footprint = rmqr_height[31] * rmqr_width[31];
2672 for (version = 30; version >= 0; version--) {
2673 est_binlen = qr_calc_binlen_segs(RMQR_VERSION + version, mode, ddata, local_segs, seg_count,
2674 NULL /*p_structapp*/, 0 /*mode_preset*/, gs1, debug_print);
2675 footprint = rmqr_height[version] * rmqr_width[version];
2676 if (8 * rmqr_data_codewords[ecc_level >> 1][version] >= est_binlen) {
2677 if (footprint < best_footprint) {
2678 autosize = version;
2679 best_footprint = footprint;
2680 }
2681 }
2682 }
2683 version = autosize;
2684 est_binlen = qr_calc_binlen_segs(RMQR_VERSION + version, mode, ddata, local_segs, seg_count,
2685 NULL /*p_structapp*/, 0 /*mode_preset*/, gs1, debug_print);
2686 }
2687
2688 if ((symbol->option_2 >= 1) && (symbol->option_2 <= 32)) {
2689 /* User specified symbol size */
2690 version = symbol->option_2 - 1;
2691 est_binlen = qr_calc_binlen_segs(RMQR_VERSION + version, mode, ddata, local_segs, seg_count,
2692 NULL /*p_structapp*/, 0 /*mode_preset*/, gs1, debug_print);
2693 }
2694
2695 if (symbol->option_2 >= 33) {
2696 /* User has specified symbol height only */
2697 version = rmqr_fixed_height_upper_bound[symbol->option_2 - 32];
2698 for (i = version - 1; i > rmqr_fixed_height_upper_bound[symbol->option_2 - 33]; i--) {
2699 est_binlen = qr_calc_binlen_segs(RMQR_VERSION + i, mode, ddata, local_segs, seg_count,
2700 NULL /*p_structapp*/, 0 /*mode_preset*/, gs1, debug_print);
2701 if (8 * rmqr_data_codewords[ecc_level >> 1][i] >= est_binlen) {
2702 version = i;
2703 }
2704 }
2705 est_binlen = qr_calc_binlen_segs(RMQR_VERSION + version, mode, ddata, local_segs, seg_count,
2706 NULL /*p_structapp*/, 0 /*mode_preset*/, gs1, debug_print);
2707 }
2708
2709 if (symbol->option_1 == -1) {
2710 /* Detect if there is enough free space to increase ECC level */
2711 if (est_binlen < rmqr_data_codewords[QR_LEVEL_H >> 1][version] * 8) {
2712 ecc_level = QR_LEVEL_H;
2713 }
2714 }
2715
2716 target_codewords = rmqr_data_codewords[ecc_level >> 1][version];
2717 blocks = rmqr_blocks[ecc_level >> 1][version];
2718
2719 if (est_binlen > (target_codewords * 8)) {
2720 /* User has selected a symbol too small for the data */
2721 assert(symbol->option_2 > 0);
2722 return errtxtf(ZINT_ERROR_TOO_LONG, symbol, 560,
2723 "Input too long for Version %1$d %2$s-%3$c, requires %4$d codewords (maximum %5$d)",
2724 symbol->option_2, rmqr_version_names[symbol->option_2 - 1], qr_ecc_level_names[ecc_level],
2725 (est_binlen + 7) / 8, target_codewords);
2726 }
2727
2728 if (debug_print) {
2729 printf("Minimum codewords: %d\n", (est_binlen + 7) / 8);
2730 printf("Selected version: %d = R%dx%d-%c\n",
2731 (version + 1), rmqr_height[version], rmqr_width[version], qr_ecc_level_names[ecc_level]);
2732 printf("Number of data codewords in symbol: %d\n", target_codewords);
2733 printf("Number of ECC blocks: %d\n", blocks);
2734 }
2735
2736 datastream = (unsigned char *) z_alloca(target_codewords + 1);
2737 fullstream = (unsigned char *) z_alloca(rmqr_total_codewords[version] + 1);
2738
2739 (void) qr_binary_segs(datastream, RMQR_VERSION + version, target_codewords, mode, ddata, local_segs, seg_count,
2740 NULL /*p_structapp*/, gs1, est_binlen, debug_print);
2741 #ifdef ZINT_TEST
2742 if (symbol->debug & ZINT_DEBUG_TEST) debug_test_codeword_dump(symbol, datastream, target_codewords);
2743 #endif
2744 qr_add_ecc(fullstream, datastream, RMQR_VERSION + version, target_codewords, blocks, debug_print);
2745
2746 h_size = rmqr_width[version];
2747 v_size = rmqr_height[version];
2748
2749 grid = (unsigned char *) z_alloca(h_size * v_size);
2750 memset(grid, 0, h_size * v_size);
2751
2752 rmqr_setup_grid(grid, h_size, v_size);
2753 qr_populate_grid(grid, h_size, v_size, fullstream, rmqr_total_codewords[version]);
2754
2755 /* apply bitmask */
2756 for (i = 0; i < v_size; i++) {
2757 int r = i * h_size;
2758 for (j = 0; j < h_size; j++) {
2759 if ((grid[r + j] & 0xf0) == 0) {
2760 /* This is a data module */
2761 if (((i / 2) + (j / 3)) % 2 == 0) { /* < This is the data mask from section 7.8.2 */
2762 /* This module needs to be changed */
2763 grid[r + j] ^= 0x01;
2764 }
2765 }
2766 }
2767 }
2768
2769 /* add format information */
2770 format_data = version;
2771 if (ecc_level == QR_LEVEL_H) {
2772 format_data += 32;
2773 }
2774 left_format_info = rmqr_format_info_left[format_data];
2775 right_format_info = rmqr_format_info_right[format_data];
2776
2777 for (i = 0; i < 5; i++) {
2778 for (j = 0; j < 3; j++) {
2779 grid[(h_size * (i + 1)) + j + 8] = (left_format_info >> ((j * 5) + i)) & 0x01;
2780 grid[(h_size * (v_size - 6)) + (h_size * i) + j + (h_size - 8)]
2781 = (right_format_info >> ((j * 5) + i)) & 0x01;
2782 }
2783 }
2784 grid[(h_size * 1) + 11] = (left_format_info >> 15) & 0x01;
2785 grid[(h_size * 2) + 11] = (left_format_info >> 16) & 0x01;
2786 grid[(h_size * 3) + 11] = (left_format_info >> 17) & 0x01;
2787 grid[(h_size * (v_size - 6)) + (h_size - 5)] = (right_format_info >> 15) & 0x01;
2788 grid[(h_size * (v_size - 6)) + (h_size - 4)] = (right_format_info >> 16) & 0x01;
2789 grid[(h_size * (v_size - 6)) + (h_size - 3)] = (right_format_info >> 17) & 0x01;
2790
2791 symbol->width = h_size;
2792 symbol->rows = v_size;
2793
2794 for (i = 0; i < v_size; i++) {
2795 int r = i * h_size;
2796 for (j = 0; j < h_size; j++) {
2797 if (grid[r + j] & 0x01) {
2798 set_module(symbol, i, j);
2799 }
2800 }
2801 symbol->row_height[i] = 1;
2802 }
2803 symbol->height = v_size;
2804
2805 return warn_number;
2806 }
2807
2808 /* vim: set ts=4 sw=4 et : */