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