1 /* gridmtx.c - Grid Matrix
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 /* This file implements Grid Matrix as specified in
34 AIM Global Document Number AIMD014 Rev. 1.63 Revised 9 Dec 2008 */
35
36 #include <stdio.h>
37 #ifdef _MSC_VER
38 #include <malloc.h>
39 #endif
40 #include "common.h"
41 #include "reedsol.h"
42 #include "gridmtx.h"
43 #include "gb2312.h"
44 #include "eci.h"
45
46 /* define_mode() stuff */
47
48 /* Bits multiplied by this for costs, so as to be whole integer divisible by 2 and 3 */
49 #define GM_MULT 6
50
51 static const char numeral_nondigits[] = " +-.,"; /* Non-digit numeral set, excluding EOL (carriage return/linefeed) */
52
53 /* Whether in numeral or not. If in numeral, *p_numeral_end is set to position after numeral,
54 * and *p_numeral_cost is set to per-numeral cost */
in_numeral(const unsigned int gbdata[],const int length,const int in_posn,unsigned int * p_numeral_end,unsigned int * p_numeral_cost)55 static int in_numeral(const unsigned int gbdata[], const int length, const int in_posn,
56 unsigned int *p_numeral_end, unsigned int *p_numeral_cost) {
57 int i, digit_cnt, nondigit, nondigit_posn;
58
59 if (in_posn < (int) *p_numeral_end) {
60 return 1;
61 }
62
63 /* Attempt to calculate the average 'cost' of using numeric mode in number of bits (times GM_MULT) */
64 /* Also ensures that numeric mode is not selected when it cannot be used: for example in
65 a string which has "2.2.0" (cannot have more than one non-numeric character for each
66 block of three numeric characters) */
67 for (i = in_posn, digit_cnt = 0, nondigit = 0, nondigit_posn = 0; i < length && i < in_posn + 4 && digit_cnt < 3;
68 i++) {
69 if (gbdata[i] >= '0' && gbdata[i] <= '9') {
70 digit_cnt++;
71 } else if (strchr(numeral_nondigits, gbdata[i])) {
72 if (nondigit) {
73 break;
74 }
75 nondigit = 1;
76 nondigit_posn = i;
77 } else if (i < length - 1 && gbdata[i] == 13 && gbdata[i + 1] == 10) {
78 if (nondigit) {
79 break;
80 }
81 i++;
82 nondigit = 2;
83 nondigit_posn = i;
84 } else {
85 break;
86 }
87 }
88 if (digit_cnt == 0) { /* Must have at least one digit */
89 *p_numeral_end = 0;
90 return 0;
91 }
92 if (nondigit && nondigit_posn == i - 1) { /* Non-digit can't be at end */
93 nondigit = 0;
94 }
95 *p_numeral_end = in_posn + digit_cnt + nondigit;
96 /* Calculate per-numeral cost where 120 == (10 + 10) * GM_MULT, 60 == 10 * GM_MULT */
97 if (digit_cnt == 3) {
98 *p_numeral_cost = nondigit == 2 ? 24 /* (120 / 5) */ : nondigit == 1 ? 30 /* (120 / 4) */ : 20 /* (60 / 3) */;
99 } else if (digit_cnt == 2) {
100 *p_numeral_cost = nondigit == 2 ? 30 /* (120 / 4) */ : nondigit == 1 ? 40 /* (120 / 3) */ : 30 /* (60 / 2) */;
101 } else {
102 *p_numeral_cost = nondigit == 2 ? 40 /* (120 / 3) */ : nondigit == 1 ? 60 /* (120 / 2) */ : 60 /* (60 / 1) */;
103 }
104 return 1;
105 }
106
107 /* Encoding modes */
108 #define GM_CHINESE 'H'
109 #define GM_NUMBER 'N'
110 #define GM_LOWER 'L'
111 #define GM_UPPER 'U'
112 #define GM_MIXED 'M'
113 #define GM_BYTE 'B'
114 /* Note Control is a submode of Lower, Upper and Mixed modes */
115
116 /* Indexes into mode_types array */
117 #define GM_H 0 /* Chinese (Hanzi) */
118 #define GM_N 1 /* Numeral */
119 #define GM_L 2 /* Lower case */
120 #define GM_U 3 /* Upper case */
121 #define GM_M 4 /* Mixed */
122 #define GM_B 5 /* Byte */
123
124 #define GM_NUM_MODES 6
125
126 /* Calculate optimized encoding modes. Adapted from Project Nayuki */
127 /* Copyright (c) Project Nayuki. (MIT License) See qr.c for detailed notice */
define_mode(char * mode,const unsigned int gbdata[],const int length,const int debug)128 static void define_mode(char *mode, const unsigned int gbdata[], const int length, const int debug) {
129 /* Must be in same order as GM_H etc */
130 static const char mode_types[] = { GM_CHINESE, GM_NUMBER, GM_LOWER, GM_UPPER, GM_MIXED, GM_BYTE, '\0' };
131
132 /* Initial mode costs */
133 static unsigned int head_costs[GM_NUM_MODES] = {
134 /* H N (+pad prefix) L U M B (+byte count) */
135 4 * GM_MULT, (4 + 2) * GM_MULT, 4 * GM_MULT, 4 * GM_MULT, 4 * GM_MULT, (4 + 9) * GM_MULT
136 };
137
138 /* Cost of switching modes from k to j - see AIMD014 Rev. 1.63 Table 9 – Type conversion codes */
139 static const unsigned int switch_costs[GM_NUM_MODES][GM_NUM_MODES] = {
140 /* H N L U M B */
141 /*H*/ { 0, (13 + 2) * GM_MULT, 13 * GM_MULT, 13 * GM_MULT, 13 * GM_MULT, (13 + 9) * GM_MULT },
142 /*N*/ { 10 * GM_MULT, 0, 10 * GM_MULT, 10 * GM_MULT, 10 * GM_MULT, (10 + 9) * GM_MULT },
143 /*L*/ { 5 * GM_MULT, (5 + 2) * GM_MULT, 0, 5 * GM_MULT, 7 * GM_MULT, (7 + 9) * GM_MULT },
144 /*U*/ { 5 * GM_MULT, (5 + 2) * GM_MULT, 5 * GM_MULT, 0, 7 * GM_MULT, (7 + 9) * GM_MULT },
145 /*M*/ { 10 * GM_MULT, (10 + 2) * GM_MULT, 10 * GM_MULT, 10 * GM_MULT, 0, (10 + 9) * GM_MULT },
146 /*B*/ { 4 * GM_MULT, (4 + 2) * GM_MULT, 4 * GM_MULT, 4 * GM_MULT, 4 * GM_MULT, 0 },
147 };
148
149 /* Final end-of-data cost - see AIMD014 Rev. 1.63 Table 9 – Type conversion codes */
150 static const unsigned int eod_costs[GM_NUM_MODES] = {
151 /* H N L U M B */
152 13 * GM_MULT, 10 * GM_MULT, 5 * GM_MULT, 5 * GM_MULT, 10 * GM_MULT, 4 * GM_MULT
153 };
154
155 unsigned int numeral_end = 0, numeral_cost = 0, byte_count = 0; /* State */
156 int double_byte, space, numeric, lower, upper, control, double_digit, eol;
157
158 int i, j, k, cm_i;
159 unsigned int min_cost;
160 char cur_mode;
161 unsigned int prev_costs[GM_NUM_MODES];
162 unsigned int cur_costs[GM_NUM_MODES];
163 #ifndef _MSC_VER
164 char char_modes[length * GM_NUM_MODES];
165 #else
166 char *char_modes = (char *) _alloca(length * GM_NUM_MODES);
167 #endif
168
169 /* char_modes[i * GM_NUM_MODES + j] represents the mode to encode the code point at index i such that the final
170 * segment ends in mode_types[j] and the total number of bits is minimized over all possible choices */
171 memset(char_modes, 0, length * GM_NUM_MODES);
172
173 /* At the beginning of each iteration of the loop below, prev_costs[j] is the minimum number of 1/6 (1/XX_MULT)
174 * bits needed to encode the entire string prefix of length i, and end in mode_types[j] */
175 memcpy(prev_costs, head_costs, GM_NUM_MODES * sizeof(unsigned int));
176
177 /* Calculate costs using dynamic programming */
178 for (i = 0, cm_i = 0; i < length; i++, cm_i += GM_NUM_MODES) {
179 memset(cur_costs, 0, GM_NUM_MODES * sizeof(unsigned int));
180
181 space = numeric = lower = upper = control = double_digit = eol = 0;
182
183 double_byte = gbdata[i] > 0xFF;
184 if (!double_byte) {
185 space = gbdata[i] == ' ';
186 if (!space) {
187 numeric = gbdata[i] >= '0' && gbdata[i] <= '9';
188 if (!numeric) {
189 lower = gbdata[i] >= 'a' && gbdata[i] <= 'z';
190 if (!lower) {
191 upper = gbdata[i] >= 'A' && gbdata[i] <= 'Z';
192 if (!upper) {
193 control = gbdata[i] < 0x7F; /* Exclude DEL */
194 if (control && i + 1 < length) {
195 eol = gbdata[i] == 13 && gbdata[i + 1] == 10;
196 }
197 }
198 }
199 } else if (i + 1 < length) {
200 double_digit = gbdata[i + 1] >= '0' && gbdata[i + 1] <= '9';
201 }
202 }
203 }
204
205 /* Hanzi mode can encode anything */
206 cur_costs[GM_H] = prev_costs[GM_H] + (double_digit || eol ? 39 : 78); /* (6.5 : 13) * GM_MULT */
207 char_modes[cm_i + GM_H] = GM_CHINESE;
208
209 /* Byte mode can encode anything */
210 if (byte_count == 512 || (double_byte && byte_count == 511)) {
211 cur_costs[GM_B] = head_costs[GM_B];
212 if (double_byte && byte_count == 511) {
213 cur_costs[GM_B] += 48; /* 8 * GM_MULT */
214 double_byte = 0; /* Splitting double-byte so mark as single */
215 }
216 byte_count = 0;
217 }
218 cur_costs[GM_B] += prev_costs[GM_B] + (double_byte ? 96 : 48); /* (16 : 8) * GM_MULT */
219 char_modes[cm_i + GM_B] = GM_BYTE;
220 byte_count += double_byte ? 2 : 1;
221
222 if (in_numeral(gbdata, length, i, &numeral_end, &numeral_cost)) {
223 cur_costs[GM_N] = prev_costs[GM_N] + numeral_cost;
224 char_modes[cm_i + GM_N] = GM_NUMBER;
225 }
226
227 if (control) {
228 cur_costs[GM_L] = prev_costs[GM_L] + 78; /* (7 + 6) * GM_MULT */
229 char_modes[cm_i + GM_L] = GM_LOWER;
230 cur_costs[GM_U] = prev_costs[GM_U] + 78; /* (7 + 6) * GM_MULT */
231 char_modes[cm_i + GM_U] = GM_UPPER;
232 cur_costs[GM_M] = prev_costs[GM_M] + 96; /* (10 + 6) * GM_MULT */
233 char_modes[cm_i + GM_M] = GM_MIXED;
234 } else {
235 if (lower || space) {
236 cur_costs[GM_L] = prev_costs[GM_L] + 30; /* 5 * GM_MULT */
237 char_modes[cm_i + GM_L] = GM_LOWER;
238 }
239 if (upper || space) {
240 cur_costs[GM_U] = prev_costs[GM_U] + 30; /* 5 * GM_MULT */
241 char_modes[cm_i + GM_U] = GM_UPPER;
242 }
243 if (numeric || lower || upper || space) {
244 cur_costs[GM_M] = prev_costs[GM_M] + 36; /* 6 * GM_MULT */
245 char_modes[cm_i + GM_M] = GM_MIXED;
246 }
247 }
248
249 if (i == length - 1) { /* Add end of data costs if last character */
250 for (j = 0; j < GM_NUM_MODES; j++) {
251 if (char_modes[cm_i + j]) {
252 cur_costs[j] += eod_costs[j];
253 }
254 }
255 }
256
257 /* Start new segment at the end to switch modes */
258 for (j = 0; j < GM_NUM_MODES; j++) { /* To mode */
259 for (k = 0; k < GM_NUM_MODES; k++) { /* From mode */
260 if (j != k && char_modes[cm_i + k]) {
261 unsigned int new_cost = cur_costs[k] + switch_costs[k][j];
262 if (!char_modes[cm_i + j] || new_cost < cur_costs[j]) {
263 cur_costs[j] = new_cost;
264 char_modes[cm_i + j] = mode_types[k];
265 }
266 }
267 }
268 }
269
270 memcpy(prev_costs, cur_costs, GM_NUM_MODES * sizeof(unsigned int));
271 }
272
273 /* Find optimal ending mode */
274 min_cost = prev_costs[0];
275 cur_mode = mode_types[0];
276 for (i = 1; i < GM_NUM_MODES; i++) {
277 if (prev_costs[i] < min_cost) {
278 min_cost = prev_costs[i];
279 cur_mode = mode_types[i];
280 }
281 }
282
283 /* Get optimal mode for each code point by tracing backwards */
284 for (i = length - 1, cm_i = i * GM_NUM_MODES; i >= 0; i--, cm_i -= GM_NUM_MODES) {
285 j = strchr(mode_types, cur_mode) - mode_types;
286 cur_mode = char_modes[cm_i + j];
287 mode[i] = cur_mode;
288 }
289
290 if (debug & ZINT_DEBUG_PRINT) {
291 printf(" Mode: %.*s\n", length, mode);
292 }
293 }
294
295 /* Add the length indicator for byte encoded blocks */
add_byte_count(char binary[],const int byte_count_posn,const int byte_count)296 static void add_byte_count(char binary[], const int byte_count_posn, const int byte_count) {
297 /* AIMD014 6.3.7: "Let L be the number of bytes of input data to be encoded in the 8-bit binary data set.
298 * First output (L-1) as a 9-bit binary prefix to record the number of bytes..." */
299 bin_append_posn(byte_count - 1, 9, binary, byte_count_posn);
300 }
301
302 /* Add a control character to the data stream */
add_shift_char(char binary[],int bp,int shifty,int debug)303 static int add_shift_char(char binary[], int bp, int shifty, int debug) {
304 int i;
305 int glyph = 0;
306
307 if (shifty < 32) {
308 glyph = shifty;
309 } else {
310 for (i = 32; i < 64; i++) {
311 if (shift_set[i] == shifty) {
312 glyph = i;
313 break;
314 }
315 }
316 }
317
318 if (debug & ZINT_DEBUG_PRINT) {
319 printf("SHIFT [%d] ", glyph);
320 }
321
322 bp = bin_append_posn(glyph, 6, binary, bp);
323
324 return bp;
325 }
326
gm_encode(unsigned int gbdata[],const int length,char binary[],const int reader,const int eci,int * bin_len,int debug)327 static int gm_encode(unsigned int gbdata[], const int length, char binary[], const int reader, const int eci,
328 int *bin_len, int debug) {
329 /* Create a binary stream representation of the input data.
330 7 sets are defined - Chinese characters, Numerals, Lower case letters, Upper case letters,
331 Mixed numerals and latters, Control characters and 8-bit binary data */
332 int sp;
333 int current_mode, last_mode;
334 unsigned int glyph = 0;
335 int c1, c2, done;
336 int p = 0, ppos;
337 int numbuf[3], punt = 0;
338 int number_pad_posn, byte_count_posn = 0;
339 int byte_count = 0;
340 int shift;
341 int bp;
342 #ifndef _MSC_VER
343 char mode[length];
344 #else
345 char *mode = (char *) _alloca(length);
346 #endif
347
348 *binary = '\0';
349 bp = 0;
350
351 sp = 0;
352 current_mode = 0;
353 number_pad_posn = 0;
354
355 if (reader) {
356 bp = bin_append_posn(10, 4, binary, bp); /* FNC3 - Reader Initialisation */
357 }
358
359 if (eci != 0) {
360 /* ECI assignment according to Table 8 */
361 bp = bin_append_posn(12, 4, binary, bp); /* ECI */
362 if (eci <= 1023) {
363 bp = bin_append_posn(eci, 11, binary, bp);
364 } else if (eci <= 32767) {
365 bp = bin_append_posn(2, 2, binary, bp);
366 bp = bin_append_posn(eci, 15, binary, bp);
367 } else {
368 bp = bin_append_posn(3, 2, binary, bp);
369 bp = bin_append_posn(eci, 20, binary, bp);
370 }
371 }
372
373 define_mode(mode, gbdata, length, debug);
374
375 do {
376 int next_mode = mode[sp];
377
378 if (next_mode != current_mode) {
379 switch (current_mode) {
380 case 0:
381 switch (next_mode) {
382 case GM_CHINESE: bp = bin_append_posn(1, 4, binary, bp);
383 break;
384 case GM_NUMBER: bp = bin_append_posn(2, 4, binary, bp);
385 break;
386 case GM_LOWER: bp = bin_append_posn(3, 4, binary, bp);
387 break;
388 case GM_UPPER: bp = bin_append_posn(4, 4, binary, bp);
389 break;
390 case GM_MIXED: bp = bin_append_posn(5, 4, binary, bp);
391 break;
392 case GM_BYTE: bp = bin_append_posn(6, 4, binary, bp);
393 break;
394 }
395 break;
396 case GM_CHINESE:
397 switch (next_mode) {
398 case GM_NUMBER: bp = bin_append_posn(8161, 13, binary, bp);
399 break;
400 case GM_LOWER: bp = bin_append_posn(8162, 13, binary, bp);
401 break;
402 case GM_UPPER: bp = bin_append_posn(8163, 13, binary, bp);
403 break;
404 case GM_MIXED: bp = bin_append_posn(8164, 13, binary, bp);
405 break;
406 case GM_BYTE: bp = bin_append_posn(8165, 13, binary, bp);
407 break;
408 }
409 break;
410 case GM_NUMBER:
411 /* add numeric block padding value */
412 switch (p) {
413 case 1: binary[number_pad_posn] = '1';
414 binary[number_pad_posn + 1] = '0';
415 break; // 2 pad digits
416 case 2: binary[number_pad_posn] = '0';
417 binary[number_pad_posn + 1] = '1';
418 break; // 1 pad digits
419 case 3: binary[number_pad_posn] = '0';
420 binary[number_pad_posn + 1] = '0';
421 break; // 0 pad digits
422 }
423 switch (next_mode) {
424 case GM_CHINESE: bp = bin_append_posn(1019, 10, binary, bp);
425 break;
426 case GM_LOWER: bp = bin_append_posn(1020, 10, binary, bp);
427 break;
428 case GM_UPPER: bp = bin_append_posn(1021, 10, binary, bp);
429 break;
430 case GM_MIXED: bp = bin_append_posn(1022, 10, binary, bp);
431 break;
432 case GM_BYTE: bp = bin_append_posn(1023, 10, binary, bp);
433 break;
434 }
435 break;
436 case GM_LOWER:
437 case GM_UPPER:
438 switch (next_mode) {
439 case GM_CHINESE: bp = bin_append_posn(28, 5, binary, bp);
440 break;
441 case GM_NUMBER: bp = bin_append_posn(29, 5, binary, bp);
442 break;
443 case GM_LOWER:
444 case GM_UPPER: bp = bin_append_posn(30, 5, binary, bp);
445 break;
446 case GM_MIXED: bp = bin_append_posn(124, 7, binary, bp);
447 break;
448 case GM_BYTE: bp = bin_append_posn(126, 7, binary, bp);
449 break;
450 }
451 break;
452 case GM_MIXED:
453 switch (next_mode) {
454 case GM_CHINESE: bp = bin_append_posn(1009, 10, binary, bp);
455 break;
456 case GM_NUMBER: bp = bin_append_posn(1010, 10, binary, bp);
457 break;
458 case GM_LOWER: bp = bin_append_posn(1011, 10, binary, bp);
459 break;
460 case GM_UPPER: bp = bin_append_posn(1012, 10, binary, bp);
461 break;
462 case GM_BYTE: bp = bin_append_posn(1015, 10, binary, bp);
463 break;
464 }
465 break;
466 case GM_BYTE:
467 /* add byte block length indicator */
468 add_byte_count(binary, byte_count_posn, byte_count);
469 byte_count = 0;
470 switch (next_mode) {
471 case GM_CHINESE: bp = bin_append_posn(1, 4, binary, bp);
472 break;
473 case GM_NUMBER: bp = bin_append_posn(2, 4, binary, bp);
474 break;
475 case GM_LOWER: bp = bin_append_posn(3, 4, binary, bp);
476 break;
477 case GM_UPPER: bp = bin_append_posn(4, 4, binary, bp);
478 break;
479 case GM_MIXED: bp = bin_append_posn(5, 4, binary, bp);
480 break;
481 }
482 break;
483 }
484 if (debug & ZINT_DEBUG_PRINT) {
485 switch (next_mode) {
486 case GM_CHINESE: printf("CHIN ");
487 break;
488 case GM_NUMBER: printf("NUMB ");
489 break;
490 case GM_LOWER: printf("LOWR ");
491 break;
492 case GM_UPPER: printf("UPPR ");
493 break;
494 case GM_MIXED: printf("MIXD ");
495 break;
496 case GM_BYTE: printf("BYTE ");
497 break;
498 }
499 }
500 }
501 last_mode = current_mode;
502 current_mode = next_mode;
503
504 switch (current_mode) {
505 case GM_CHINESE:
506 done = 0;
507 if (gbdata[sp] > 0xff) {
508 /* GB2312 character */
509 c1 = (gbdata[sp] & 0xff00) >> 8;
510 c2 = gbdata[sp] & 0xff;
511
512 if ((c1 >= 0xa1) && (c1 <= 0xa9)) {
513 glyph = (0x60 * (c1 - 0xa1)) + (c2 - 0xa0);
514 } else if ((c1 >= 0xb0) && (c1 <= 0xf7)) {
515 glyph = (0x60 * (c1 - 0xb0 + 9)) + (c2 - 0xa0);
516 }
517 done = 1; /* GB 2312 always within above ranges */
518 }
519 if (!(done)) {
520 if (sp != (length - 1)) {
521 if ((gbdata[sp] == 13) && (gbdata[sp + 1] == 10)) {
522 /* End of Line */
523 glyph = 7776;
524 sp++;
525 done = 1;
526 }
527 }
528 }
529 if (!(done)) {
530 if (sp != (length - 1)) {
531 if (((gbdata[sp] >= '0') && (gbdata[sp] <= '9')) &&
532 ((gbdata[sp + 1] >= '0') && (gbdata[sp + 1] <= '9'))) {
533 /* Two digits */
534 glyph = 8033 + (10 * (gbdata[sp] - '0')) + (gbdata[sp + 1] - '0');
535 sp++;
536 done = 1;
537 }
538 }
539 }
540 if (!(done)) {
541 /* Byte value */
542 glyph = 7777 + gbdata[sp];
543 }
544
545 if (debug & ZINT_DEBUG_PRINT) {
546 printf("[%d] ", (int) glyph);
547 }
548
549 bp = bin_append_posn(glyph, 13, binary, bp);
550 sp++;
551 break;
552
553 case GM_NUMBER:
554 if (last_mode != current_mode) {
555 /* Reserve a space for numeric digit padding value (2 bits) */
556 number_pad_posn = bp;
557 bp = bin_append_posn(0, 2, binary, bp);
558 }
559 p = 0;
560 ppos = -1;
561
562 /* Numeric compression can also include certain combinations of
563 non-numeric character */
564
565 numbuf[0] = '0';
566 numbuf[1] = '0';
567 numbuf[2] = '0';
568 do {
569 if ((gbdata[sp] >= '0') && (gbdata[sp] <= '9')) {
570 numbuf[p] = gbdata[sp];
571 p++;
572 } else if (strchr(numeral_nondigits, gbdata[sp])) {
573 if (ppos != -1) {
574 break;
575 }
576 punt = gbdata[sp];
577 ppos = p;
578 } else if (sp < (length - 1) && (gbdata[sp] == 13) && (gbdata[sp + 1] == 10)) {
579 /* <end of line> */
580 if (ppos != -1) {
581 break;
582 }
583 punt = gbdata[sp];
584 sp++;
585 ppos = p;
586 } else {
587 break;
588 }
589 sp++;
590 } while ((p < 3) && (sp < length) && mode[sp] == GM_NUMBER);
591
592 if (ppos != -1) {
593 switch (punt) {
594 case ' ': glyph = 0;
595 break;
596 case '+': glyph = 3;
597 break;
598 case '-': glyph = 6;
599 break;
600 case '.': glyph = 9;
601 break;
602 case ',': glyph = 12;
603 break;
604 case 13: glyph = 15;
605 break;
606 }
607 glyph += ppos;
608 glyph += 1000;
609
610 if (debug & ZINT_DEBUG_PRINT) {
611 printf("[%d] ", (int) glyph);
612 }
613
614 bp = bin_append_posn(glyph, 10, binary, bp);
615 }
616
617 glyph = (100 * (numbuf[0] - '0')) + (10 * (numbuf[1] - '0')) + (numbuf[2] - '0');
618 if (debug & ZINT_DEBUG_PRINT) {
619 printf("[%d] ", (int) glyph);
620 }
621
622 bp = bin_append_posn(glyph, 10, binary, bp);
623 break;
624
625 case GM_BYTE:
626 if (last_mode != current_mode) {
627 /* Reserve space for byte block length indicator (9 bits) */
628 byte_count_posn = bp;
629 bp = bin_append_posn(0, 9, binary, bp);
630 }
631 glyph = gbdata[sp];
632 if (byte_count == 512 || (glyph > 0xFF && byte_count == 511)) {
633 /* Maximum byte block size is 512 bytes. If longer is needed then start a new block */
634 if (glyph > 0xFF && byte_count == 511) { /* Split double-byte */
635 bp = bin_append_posn(glyph >> 8, 8, binary, bp);
636 glyph &= 0xFF;
637 byte_count++;
638 }
639 add_byte_count(binary, byte_count_posn, byte_count);
640 bp = bin_append_posn(7, 4, binary, bp);
641 byte_count_posn = bp;
642 bp = bin_append_posn(0, 9, binary, bp);
643 byte_count = 0;
644 }
645
646 if (debug & ZINT_DEBUG_PRINT) {
647 printf("[%d] ", (int) glyph);
648 }
649 bp = bin_append_posn(glyph, glyph > 0xFF ? 16 : 8, binary, bp);
650 sp++;
651 byte_count++;
652 if (glyph > 0xFF) {
653 byte_count++;
654 }
655 break;
656
657 case GM_MIXED:
658 shift = 1;
659 if ((gbdata[sp] >= '0') && (gbdata[sp] <= '9')) {
660 shift = 0;
661 } else if ((gbdata[sp] >= 'A') && (gbdata[sp] <= 'Z')) {
662 shift = 0;
663 } else if ((gbdata[sp] >= 'a') && (gbdata[sp] <= 'z')) {
664 shift = 0;
665 } else if (gbdata[sp] == ' ') {
666 shift = 0;
667 }
668
669 if (shift == 0) {
670 /* Mixed Mode character */
671 glyph = posn(EUROPIUM, (const char) gbdata[sp]);
672 if (debug & ZINT_DEBUG_PRINT) {
673 printf("[%d] ", (int) glyph);
674 }
675
676 bp = bin_append_posn(glyph, 6, binary, bp);
677 } else {
678 /* Shift Mode character */
679 bp = bin_append_posn(1014, 10, binary, bp); /* shift indicator */
680 bp = add_shift_char(binary, bp, gbdata[sp], debug);
681 }
682
683 sp++;
684 break;
685
686 case GM_UPPER:
687 shift = 1;
688 if ((gbdata[sp] >= 'A') && (gbdata[sp] <= 'Z')) {
689 shift = 0;
690 } else if (gbdata[sp] == ' ') {
691 shift = 0;
692 }
693
694 if (shift == 0) {
695 /* Upper Case character */
696 glyph = posn("ABCDEFGHIJKLMNOPQRSTUVWXYZ ", (const char) gbdata[sp]);
697 if (debug & ZINT_DEBUG_PRINT) {
698 printf("[%d] ", (int) glyph);
699 }
700
701 bp = bin_append_posn(glyph, 5, binary, bp);
702 } else {
703 /* Shift Mode character */
704 bp = bin_append_posn(125, 7, binary, bp); /* shift indicator */
705 bp = add_shift_char(binary, bp, gbdata[sp], debug);
706 }
707
708 sp++;
709 break;
710
711 case GM_LOWER:
712 shift = 1;
713 if ((gbdata[sp] >= 'a') && (gbdata[sp] <= 'z')) {
714 shift = 0;
715 } else if (gbdata[sp] == ' ') {
716 shift = 0;
717 }
718
719 if (shift == 0) {
720 /* Lower Case character */
721 glyph = posn("abcdefghijklmnopqrstuvwxyz ", (const char) gbdata[sp]);
722 if (debug & ZINT_DEBUG_PRINT) {
723 printf("[%d] ", (int) glyph);
724 }
725
726 bp = bin_append_posn(glyph, 5, binary, bp);
727 } else {
728 /* Shift Mode character */
729 bp = bin_append_posn(125, 7, binary, bp); /* shift indicator */
730 bp = add_shift_char(binary, bp, gbdata[sp], debug);
731 }
732
733 sp++;
734 break;
735 }
736 if (bp > 9191) {
737 return ZINT_ERROR_TOO_LONG;
738 }
739
740 } while (sp < length);
741
742 if (current_mode == GM_NUMBER) {
743 /* add numeric block padding value */
744 switch (p) {
745 case 1: binary[number_pad_posn] = '1';
746 binary[number_pad_posn + 1] = '0';
747 break; // 2 pad digits
748 case 2: binary[number_pad_posn] = '0';
749 binary[number_pad_posn + 1] = '1';
750 break; // 1 pad digit
751 case 3: binary[number_pad_posn] = '0';
752 binary[number_pad_posn + 1] = '0';
753 break; // 0 pad digits
754 }
755 }
756
757 if (current_mode == GM_BYTE) {
758 /* Add byte block length indicator */
759 add_byte_count(binary, byte_count_posn, byte_count);
760 }
761
762 /* Add "end of data" character */
763 switch (current_mode) {
764 case GM_CHINESE: bp = bin_append_posn(8160, 13, binary, bp);
765 break;
766 case GM_NUMBER: bp = bin_append_posn(1018, 10, binary, bp);
767 break;
768 case GM_LOWER:
769 case GM_UPPER: bp = bin_append_posn(27, 5, binary, bp);
770 break;
771 case GM_MIXED: bp = bin_append_posn(1008, 10, binary, bp);
772 break;
773 case GM_BYTE: bp = bin_append_posn(0, 4, binary, bp);
774 break;
775 }
776
777 /* Add padding bits if required */
778 p = 7 - (bp % 7);
779 if (p % 7) {
780 bp = bin_append_posn(0, p, binary, bp);
781 }
782
783 if (bp > 9191) {
784 return ZINT_ERROR_TOO_LONG;
785 }
786 binary[bp] = '\0';
787 *bin_len = bp;
788
789 if (debug & ZINT_DEBUG_PRINT) {
790 printf("\nBinary (%d): %s\n", bp, binary);
791 }
792
793 return 0;
794 }
795
gm_add_ecc(const char binary[],const int data_posn,const int layers,const int ecc_level,unsigned char word[])796 static void gm_add_ecc(const char binary[], const int data_posn, const int layers, const int ecc_level,
797 unsigned char word[]) {
798 int data_cw, i, j, wp, p;
799 int n1, b1, n2, b2, e1, b3, e2;
800 int block_size, ecc_size;
801 unsigned char data[1320], block[130];
802 unsigned char data_block[115], ecc_block[70];
803 rs_t rs;
804
805 data_cw = gm_data_codewords[((layers - 1) * 5) + (ecc_level - 1)];
806
807 for (i = 0; i < 1320; i++) {
808 data[i] = 0;
809 }
810
811 /* Convert from binary stream to 7-bit codewords */
812 for (i = 0; i < data_posn; i++) {
813 for (p = 0; p < 7; p++) {
814 if (binary[i * 7 + p] == '1') {
815 data[i] += (0x40 >> p);
816 }
817 }
818 }
819
820 /* Add padding codewords */
821 data[data_posn] = 0x00;
822 for (i = (data_posn + 1); i < data_cw; i++) {
823 if (i & 1) {
824 data[i] = 0x7e;
825 } else {
826 data[i] = 0x00;
827 }
828 }
829
830 /* Get block sizes */
831 n1 = gm_n1[(layers - 1)];
832 b1 = gm_b1[(layers - 1)];
833 n2 = n1 - 1;
834 b2 = gm_b2[(layers - 1)];
835 e1 = gm_ebeb[((layers - 1) * 20) + ((ecc_level - 1) * 4)];
836 b3 = gm_ebeb[((layers - 1) * 20) + ((ecc_level - 1) * 4) + 1];
837 e2 = gm_ebeb[((layers - 1) * 20) + ((ecc_level - 1) * 4) + 2];
838
839 rs_init_gf(&rs, 0x89);
840
841 /* Split the data into blocks */
842 wp = 0;
843 for (i = 0; i < (b1 + b2); i++) {
844 int data_size;
845 if (i < b1) {
846 block_size = n1;
847 } else {
848 block_size = n2;
849 }
850 if (i < b3) {
851 ecc_size = e1;
852 } else {
853 ecc_size = e2;
854 }
855 data_size = block_size - ecc_size;
856
857 /* printf("block %d/%d: data %d / ecc %d\n", i + 1, (b1 + b2), data_size, ecc_size);*/
858
859 for (j = 0; j < data_size; j++) {
860 data_block[j] = data[wp];
861 wp++;
862 }
863
864 /* Calculate ECC data for this block */
865 rs_init_code(&rs, ecc_size, 1);
866 rs_encode(&rs, data_size, data_block, ecc_block);
867
868 /* Correct error correction data but in reverse order */
869 for (j = 0; j < data_size; j++) {
870 block[j] = data_block[j];
871 }
872 for (j = 0; j < ecc_size; j++) {
873 block[(j + data_size)] = ecc_block[ecc_size - j - 1];
874 }
875
876 for (j = 0; j < n2; j++) {
877 word[((b1 + b2) * j) + i] = block[j];
878 }
879 if (block_size == n1) {
880 word[((b1 + b2) * (n1 - 1)) + i] = block[(n1 - 1)];
881 }
882 }
883 }
884
place_macromodule(char grid[],int x,int y,int word1,int word2,int size)885 static void place_macromodule(char grid[], int x, int y, int word1, int word2, int size) {
886 int i, j;
887
888 i = (x * 6) + 1;
889 j = (y * 6) + 1;
890
891 if (word2 & 0x40) {
892 grid[(j * size) + i + 2] = '1';
893 }
894 if (word2 & 0x20) {
895 grid[(j * size) + i + 3] = '1';
896 }
897 if (word2 & 0x10) {
898 grid[((j + 1) * size) + i] = '1';
899 }
900 if (word2 & 0x08) {
901 grid[((j + 1) * size) + i + 1] = '1';
902 }
903 if (word2 & 0x04) {
904 grid[((j + 1) * size) + i + 2] = '1';
905 }
906 if (word2 & 0x02) {
907 grid[((j + 1) * size) + i + 3] = '1';
908 }
909 if (word2 & 0x01) {
910 grid[((j + 2) * size) + i] = '1';
911 }
912 if (word1 & 0x40) {
913 grid[((j + 2) * size) + i + 1] = '1';
914 }
915 if (word1 & 0x20) {
916 grid[((j + 2) * size) + i + 2] = '1';
917 }
918 if (word1 & 0x10) {
919 grid[((j + 2) * size) + i + 3] = '1';
920 }
921 if (word1 & 0x08) {
922 grid[((j + 3) * size) + i] = '1';
923 }
924 if (word1 & 0x04) {
925 grid[((j + 3) * size) + i + 1] = '1';
926 }
927 if (word1 & 0x02) {
928 grid[((j + 3) * size) + i + 2] = '1';
929 }
930 if (word1 & 0x01) {
931 grid[((j + 3) * size) + i + 3] = '1';
932 }
933 }
934
place_data_in_grid(unsigned char word[],char grid[],int modules,int size)935 static void place_data_in_grid(unsigned char word[], char grid[], int modules, int size) {
936 int x, y, macromodule, offset;
937
938 offset = 13 - ((modules - 1) / 2);
939 for (y = 0; y < modules; y++) {
940 for (x = 0; x < modules; x++) {
941 macromodule = gm_macro_matrix[((y + offset) * 27) + (x + offset)];
942 place_macromodule(grid, x, y, word[macromodule * 2], word[(macromodule * 2) + 1], size);
943 }
944 }
945 }
946
947 /* Place the layer ID into each macromodule */
place_layer_id(char * grid,int size,int layers,int modules,int ecc_level)948 static void place_layer_id(char *grid, int size, int layers, int modules, int ecc_level) {
949 int i, j, layer, start, stop;
950
951 #ifndef _MSC_VER
952 int layerid[layers + 1];
953 int id[modules * modules];
954 #else
955 int *layerid = (int *) _alloca((layers + 1) * sizeof(int));
956 int *id = (int *) _alloca((modules * modules) * sizeof(int));
957 #endif
958
959 /* Calculate Layer IDs */
960 for (i = 0; i <= layers; i++) {
961 if (ecc_level == 1) {
962 layerid[i] = 3 - (i % 4);
963 } else {
964 layerid[i] = (i + 5 - ecc_level) % 4;
965 }
966 }
967
968 for (i = 0; i < modules; i++) {
969 for (j = 0; j < modules; j++) {
970 id[(i * modules) + j] = 0;
971 }
972 }
973
974 /* Calculate which value goes in each macromodule */
975 start = modules / 2;
976 stop = modules / 2;
977 for (layer = 0; layer <= layers; layer++) {
978 for (i = start; i <= stop; i++) {
979 id[(start * modules) + i] = layerid[layer];
980 id[(i * modules) + start] = layerid[layer];
981 id[((modules - start - 1) * modules) + i] = layerid[layer];
982 id[(i * modules) + (modules - start - 1)] = layerid[layer];
983 }
984 start--;
985 stop++;
986 }
987
988 /* Place the data in the grid */
989 for (i = 0; i < modules; i++) {
990 for (j = 0; j < modules; j++) {
991 if (id[(i * modules) + j] & 0x02) {
992 grid[(((i * 6) + 1) * size) + (j * 6) + 1] = '1';
993 }
994 if (id[(i * modules) + j] & 0x01) {
995 grid[(((i * 6) + 1) * size) + (j * 6) + 2] = '1';
996 }
997 }
998 }
999 }
1000
grid_matrix(struct zint_symbol * symbol,unsigned char source[],int length)1001 INTERNAL int grid_matrix(struct zint_symbol *symbol, unsigned char source[], int length) {
1002 int size, modules, error_number;
1003 int auto_layers, min_layers, layers, auto_ecc_level, min_ecc_level, ecc_level;
1004 int x, y, i;
1005 int full_multibyte;
1006 char binary[9300];
1007 int data_cw, input_latch = 0;
1008 unsigned char word[1460] = {0};
1009 int data_max, reader = 0;
1010 int size_squared;
1011 int bin_len;
1012 int eci_length = get_eci_length(symbol->eci, source, length);
1013
1014 #ifndef _MSC_VER
1015 unsigned int gbdata[eci_length + 1];
1016 #else
1017 char *grid;
1018 unsigned int *gbdata = (unsigned int *) _alloca((eci_length + 1) * sizeof(unsigned int));
1019 #endif
1020
1021 /* If ZINT_FULL_MULTIBYTE set use Hanzi mode in DATA_MODE or for non-GB 2312 in UNICODE_MODE */
1022 full_multibyte = (symbol->option_3 & 0xFF) == ZINT_FULL_MULTIBYTE;
1023
1024 if ((symbol->input_mode & 0x07) == DATA_MODE) {
1025 gb2312_cpy(source, &length, gbdata, full_multibyte);
1026 } else {
1027 int done = 0;
1028 if (symbol->eci != 29) { /* Unless ECI 29 (GB) */
1029 /* Try other conversions (ECI 0 defaults to ISO/IEC 8859-1) */
1030 error_number = gb2312_utf8_to_eci(symbol->eci, source, &length, gbdata, full_multibyte);
1031 if (error_number == 0) {
1032 done = 1;
1033 } else if (symbol->eci) {
1034 sprintf(symbol->errtxt, "535: Invalid character in input data for ECI %d", symbol->eci);
1035 return error_number;
1036 }
1037 }
1038 if (!done) {
1039 /* Try GB 2312 (EUC-CN) */
1040 error_number = gb2312_utf8(symbol, source, &length, gbdata);
1041 if (error_number != 0) {
1042 return error_number;
1043 }
1044 }
1045 }
1046
1047 if (symbol->output_options & READER_INIT) reader = 1;
1048
1049 if (symbol->eci > 811799) {
1050 strcpy(symbol->errtxt, "533: Invalid ECI");
1051 return ZINT_ERROR_INVALID_OPTION;
1052 }
1053
1054 error_number = gm_encode(gbdata, length, binary, reader, symbol->eci, &bin_len, symbol->debug);
1055 if (error_number != 0) {
1056 strcpy(symbol->errtxt, "531: Input data too long");
1057 return error_number;
1058 }
1059
1060 /* Determine the size of the symbol */
1061 data_cw = bin_len / 7; /* Binary length always a multiple of 7 */
1062
1063 auto_layers = 13;
1064 for (i = 12; i > 0; i--) {
1065 if (gm_recommend_cw[(i - 1)] >= data_cw) {
1066 auto_layers = i;
1067 }
1068 }
1069 min_layers = 13;
1070 for (i = 12; i > 0; i--) {
1071 if (gm_max_cw[(i - 1)] >= data_cw) {
1072 min_layers = i;
1073 }
1074 }
1075 layers = auto_layers;
1076
1077 if ((symbol->option_2 >= 1) && (symbol->option_2 <= 13)) {
1078 input_latch = 1;
1079 if (symbol->option_2 >= min_layers) {
1080 layers = symbol->option_2;
1081 } else {
1082 strcpy(symbol->errtxt, "534: Input data too long for selected symbol size");
1083 return ZINT_ERROR_TOO_LONG;
1084 }
1085 }
1086
1087 auto_ecc_level = 3;
1088 if (layers == 1) {
1089 auto_ecc_level = 5;
1090 } else if ((layers == 2) || (layers == 3)) {
1091 auto_ecc_level = 4;
1092 }
1093 ecc_level = auto_ecc_level;
1094
1095 min_ecc_level = 1;
1096 if (layers == 1) {
1097 min_ecc_level = 4;
1098 } else if (layers == 2) {
1099 min_ecc_level = 2;
1100 }
1101
1102 if ((symbol->option_1 >= 1) && (symbol->option_1 <= 5)) {
1103 if (symbol->option_1 >= min_ecc_level) {
1104 ecc_level = symbol->option_1;
1105 } else {
1106 ecc_level = min_ecc_level;
1107 }
1108 }
1109 if (data_cw > gm_data_codewords[(5 * (layers - 1)) + (ecc_level - 1)]) {
1110 /* If layers user-specified (option_2), try reducing ECC level first */
1111 if (input_latch && ecc_level > min_ecc_level) {
1112 do {
1113 ecc_level--;
1114 } while ((data_cw > gm_data_codewords[(5 * (layers - 1)) + (ecc_level - 1)])
1115 && (ecc_level > min_ecc_level));
1116 }
1117 while (data_cw > gm_data_codewords[(5 * (layers - 1)) + (ecc_level - 1)] && (layers < 13)) {
1118 layers++;
1119 }
1120 /* ECC min level 1 for layers > 2 */
1121 while (data_cw > gm_data_codewords[(5 * (layers - 1)) + (ecc_level - 1)] && ecc_level > 1) {
1122 ecc_level--;
1123 }
1124 }
1125
1126 data_max = 1313;
1127 switch (ecc_level) {
1128 case 2: data_max = 1167;
1129 break;
1130 case 3: data_max = 1021;
1131 break;
1132 case 4: data_max = 875;
1133 break;
1134 case 5: data_max = 729;
1135 break;
1136 }
1137
1138 if (data_cw > data_max) {
1139 strcpy(symbol->errtxt, "532: Input data too long");
1140 return ZINT_ERROR_TOO_LONG;
1141 }
1142
1143 gm_add_ecc(binary, data_cw, layers, ecc_level, word);
1144 #ifdef ZINT_TEST
1145 if (symbol->debug & ZINT_DEBUG_TEST) debug_test_codeword_dump(symbol, word, data_cw);
1146 #endif
1147 size = 6 + (layers * 12);
1148 modules = 1 + (layers * 2);
1149 size_squared = size * size;
1150
1151 #ifndef _MSC_VER
1152 char grid[size_squared];
1153 #else
1154 grid = (char *) _alloca(size_squared);
1155 #endif
1156
1157 memset(grid, '0', size_squared);
1158
1159 place_data_in_grid(word, grid, modules, size);
1160 place_layer_id(grid, size, layers, modules, ecc_level);
1161
1162 /* Add macromodule frames */
1163 for (x = 0; x < modules; x++) {
1164 int dark = 1 - (x & 1);
1165 for (y = 0; y < modules; y++) {
1166 if (dark == 1) {
1167 for (i = 0; i < 5; i++) {
1168 grid[((y * 6) * size) + (x * 6) + i] = '1';
1169 grid[(((y * 6) + 5) * size) + (x * 6) + i] = '1';
1170 grid[(((y * 6) + i) * size) + (x * 6)] = '1';
1171 grid[(((y * 6) + i) * size) + (x * 6) + 5] = '1';
1172 }
1173 grid[(((y * 6) + 5) * size) + (x * 6) + 5] = '1';
1174 dark = 0;
1175 } else {
1176 dark = 1;
1177 }
1178 }
1179 }
1180
1181 /* Copy values to symbol */
1182 symbol->width = size;
1183 symbol->rows = size;
1184
1185 for (x = 0; x < size; x++) {
1186 for (y = 0; y < size; y++) {
1187 if (grid[(y * size) + x] == '1') {
1188 set_module(symbol, y, x);
1189 }
1190 }
1191 symbol->row_height[x] = 1;
1192 }
1193 symbol->height = size;
1194
1195 return 0;
1196 }
1197