src/mask.c

filter: Statementstmt 92.7% 115 / 124 Branchbran 93.3% 112 / 120 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 93.0% 227 / 244 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« src/qrspec.c ↑ Summary
1 /*
2 * qrencode - QR Code encoder
3 *
4 * Masking.
5 * Copyright (C) 2006-2011 Kentaro Fukuchi <kentaro@fukuchi.org>
6 *
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation; either
10 * version 2.1 of the License, or any later version.
11 *
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
16 *
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with this library; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20 */
21  
22 #if HAVE_CONFIG_H
23 # include "config.h"
24 #endif
25 #include <stdlib.h>
26 #include <string.h>
27 #include <limits.h>
28 #include <errno.h>
29  
30 #include "qrencode.h"
31 #include "qrspec.h"
32 #include "mask.h"
33  
34 48 __STATIC int Mask_writeFormatInformation(int width, unsigned char *frame, int mask, QRecLevel level)
35 {
36 unsigned int format;
37 unsigned char v;
38 int i;
39 48 int blacks = 0;
40  
41 48 format = QRspec_getFormatInfo(mask, level);
42  
43 432 ▶ for(i=0; i<8; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for(i=0; i<8; i++) { 384 48 432
44 384 ▶ if(format & 1) {
Branch: 1 branch
BranchTrueFalseTotal
if(format & 1) { 192 192 384
45 192 blacks += 2;
46 192 v = 0x85;
47 } else {
48 192 v = 0x84;
49 }
50 384 frame[width * 8 + width - 1 - i] = v;
51 384 ▶ if(i < 6) {
Branch: 1 branch
BranchTrueFalseTotal
if(i < 6) { 288 96 384
52 288 frame[width * i + 8] = v;
53 } else {
54 96 frame[width * (i + 1) + 8] = v;
55 }
56 384 format= format >> 1;
57 }
58 384 ▶ for(i=0; i<7; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for(i=0; i<7; i++) { 336 48 384
59 336 ▶ if(format & 1) {
Branch: 1 branch
BranchTrueFalseTotal
if(format & 1) { 184 152 336
60 184 blacks += 2;
61 184 v = 0x85;
62 } else {
63 152 v = 0x84;
64 }
65 336 frame[width * (width - 7 + i) + 8] = v;
66 336 ▶ if(i == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if(i == 0) { 48 288 336
67 48 frame[width * 8 + 7] = v;
68 } else {
69 288 frame[width * 8 + 6 - i] = v;
70 }
71 336 format= format >> 1;
72 }
73  
74 48 return blacks;
75 }
76  
77 /**
78 * Demerit coefficients.
79 * See Section 8.8.2, pp.45, JIS X0510:2004.
80 */
81 #define N1 (3)
82 #define N2 (3)
83 #define N3 (40)
84 #define N4 (10)
85  
86 #define MASKMAKER(__exp__) \
87 int x, y;\
88 int b = 0;\
89 \
90 for(y=0; y<width; y++) {\
91 for(x=0; x<width; x++) {\
92 if(*s & 0x80) {\
93 *d = *s;\
94 } else {\
95 *d = *s ^ ((__exp__) == 0);\
96 }\
97 b += (int)(*d & 1);\
98 s++; d++;\
99 }\
100 }\
101 return b;
102  
103 6 static int Mask_mask0(int width, const unsigned char *s, unsigned char *d)
104 {
105 8362 ▶ MASKMAKER((x+y)&1)
Branch: 3 branches
BranchTrueFalseTotal
MASKMAKER((x+y)&1) 2086 6064 8150
MASKMAKER((x+y)&1) 8150 206 8356
MASKMAKER((x+y)&1) 206 6 212
106 }
107  
108 6 static int Mask_mask1(int width, const unsigned char *s, unsigned char *d)
109 {
110 8362 ▶ MASKMAKER(y&1)
Branch: 3 branches
BranchTrueFalseTotal
MASKMAKER(y&1) 2086 6064 8150
MASKMAKER(y&1) 8150 206 8356
MASKMAKER(y&1) 206 6 212
111 }
112  
113 6 static int Mask_mask2(int width, const unsigned char *s, unsigned char *d)
114 {
115 8362 ▶ MASKMAKER(x%3)
Branch: 3 branches
BranchTrueFalseTotal
MASKMAKER(x%3) 2086 6064 8150
MASKMAKER(x%3) 8150 206 8356
MASKMAKER(x%3) 206 6 212
116 }
117  
118 6 static int Mask_mask3(int width, const unsigned char *s, unsigned char *d)
119 {
120 8362 ▶ MASKMAKER((x+y)%3)
Branch: 3 branches
BranchTrueFalseTotal
MASKMAKER((x+y)%3) 2086 6064 8150
MASKMAKER((x+y)%3) 8150 206 8356
MASKMAKER((x+y)%3) 206 6 212
121 }
122  
123 6 static int Mask_mask4(int width, const unsigned char *s, unsigned char *d)
124 {
125 8362 ▶ MASKMAKER(((y/2)+(x/3))&1)
Branch: 3 branches
BranchTrueFalseTotal
MASKMAKER(((y/2)+(x/3))&1) 2086 6064 8150
MASKMAKER(((y/2)+(x/3))&1) 8150 206 8356
MASKMAKER(((y/2)+(x/3))&1) 206 6 212
126 }
127  
128 6 static int Mask_mask5(int width, const unsigned char *s, unsigned char *d)
129 {
130 8362 ▶ MASKMAKER(((x*y)&1)+(x*y)%3)
Branch: 3 branches
BranchTrueFalseTotal
MASKMAKER(((x*y)&1)+(x*y)%3) 2086 6064 8150
MASKMAKER(((x*y)&1)+(x*y)%3) 8150 206 8356
MASKMAKER(((x*y)&1)+(x*y)%3) 206 6 212
131 }
132  
133 6 static int Mask_mask6(int width, const unsigned char *s, unsigned char *d)
134 {
135 8362 ▶ MASKMAKER((((x*y)&1)+(x*y)%3)&1)
Branch: 3 branches
BranchTrueFalseTotal
MASKMAKER((((x*y)&1)+(x*y)%3)&1) 2086 6064 8150
MASKMAKER((((x*y)&1)+(x*y)%3)&1) 8150 206 8356
MASKMAKER((((x*y)&1)+(x*y)%3)&1) 206 6 212
136 }
137  
138 6 static int Mask_mask7(int width, const unsigned char *s, unsigned char *d)
139 {
140 8362 ▶ MASKMAKER((((x*y)%3)+((x+y)&1))&1)
Branch: 3 branches
BranchTrueFalseTotal
MASKMAKER((((x*y)%3)+((x+y)&1))&1) 2086 6064 8150
MASKMAKER((((x*y)%3)+((x+y)&1))&1) 8150 206 8356
MASKMAKER((((x*y)%3)+((x+y)&1))&1) 206 6 212
141 }
142  
143 #define maskNum (8)
144 typedef int MaskMaker(int, const unsigned char *, unsigned char *);
145 static MaskMaker *maskMakers[maskNum] = {
146 Mask_mask0, Mask_mask1, Mask_mask2, Mask_mask3,
147 Mask_mask4, Mask_mask5, Mask_mask6, Mask_mask7
148 };
149  
150 #ifdef WITH_TESTS
151 unsigned char *Mask_makeMaskedFrame(int width, unsigned char *frame, int mask)
152 {
153 unsigned char *masked;
154  
155 masked = (unsigned char *)malloc(width * width);
156 if(masked == NULL) return NULL;
157  
158 maskMakers[mask](width, frame, masked);
159  
160 return masked;
161 }
162 #endif
163  
164 0 unsigned char *Mask_makeMask(int width, unsigned char *frame, int mask, QRecLevel level)
165 {
166 unsigned char *masked;
167  
168 0 ▶ if(mask < 0 || mask >= maskNum) {
Branch: 2 branches
BranchTrueFalseTotal
if(mask < 0 || mask >= maskNum) { 0 0 0
if(mask < 0 || mask >= maskNum) { 0 0 0
169 0 errno = EINVAL;
170 0 return NULL;
171 }
172  
173 0 masked = (unsigned char *)malloc(width * width);
174 0 ▶ if(masked == NULL) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if(masked == NULL) return NULL; 0 0 0
175  
176 0 maskMakers[mask](width, frame, masked);
177 0 Mask_writeFormatInformation(width, masked, mask, level);
178  
179 0 return masked;
180 }
181  
182  
183 //static int n1;
184 //static int n2;
185 //static int n3;
186 //static int n4;
187  
188 3296 __STATIC int Mask_calcN1N3(int length, int *runLength)
189 {
190 int i;
191 3296 int demerit = 0;
192 int fact;
193  
194 70882 ▶ for(i=0; i<length; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for(i=0; i<length; i++) { 67586 3296 70882
195 67586 ▶ if(runLength[i] >= 5) {
Branch: 1 branch
BranchTrueFalseTotal
if(runLength[i] >= 5) { 4987 62599 67586
196 4987 demerit += N1 + (runLength[i] - 5);
197 //n1 += N1 + (runLength[i] - 5);
198 }
199 67586 ▶ if((i & 1)) {
Branch: 1 branch
BranchTrueFalseTotal
if((i & 1)) { 33185 34401 67586
200 33185 ▶ if(i >= 3 && i < length-2 && (runLength[i] % 3) == 0) {
Branch: 3 branches
BranchTrueFalseTotal
if(i >= 3 && i < length-2 && (runLength[i] % 3) == 0) { 29890 3295 33185
if(i >= 3 && i < length-2 && (runLength[i] % 3) == 0) { 26623 3267 29890
if(i >= 3 && i < length-2 && (runLength[i] % 3) == 0) { 3963 22660 26623
201 3963 fact = runLength[i] / 3;
202 3963 ▶ if(runLength[i-2] == fact &&
Branch: 1 branch
BranchTrueFalseTotal
if(runLength[i-2] == fact && 2337 1626 3963
203 2337 ▶ runLength[i-1] == fact &&
Branch: 1 branch
BranchTrueFalseTotal
runLength[i-1] == fact && 1619 718 2337
204 1619 ▶ runLength[i+1] == fact &&
Branch: 1 branch
BranchTrueFalseTotal
runLength[i+1] == fact && 1264 355 1619
205 1264 ▶ runLength[i+2] == fact) {
Branch: 1 branch
BranchTrueFalseTotal
runLength[i+2] == fact) { 1077 187 1264
206 1077 ▶ if(i == 3 || runLength[i-3] >= 4 * fact) {
Branch: 2 branches
BranchTrueFalseTotal
if(i == 3 || runLength[i-3] >= 4 * fact) { 486 591 1077
if(i == 3 || runLength[i-3] >= 4 * fact) { 63 423 486
207 654 demerit += N3;
208 //n3 += N3;
209 423 ▶ } else if(i+4 >= length || runLength[i+3] >= 4 * fact) {
Branch: 2 branches
BranchTrueFalseTotal
} else if(i+4 >= length || runLength[i+3] >= 4 * fact) { 165 258 423
} else if(i+4 >= length || runLength[i+3] >= 4 * fact) { 36 129 165
210 294 demerit += N3;
211 //n3 += N3;
212 }
213 }
214 }
215 }
216 }
217  
218 3296 return demerit;
219 }
220  
221 48 __STATIC int Mask_calcN2(int width, unsigned char *frame)
222 {
223 int x, y;
224 unsigned char *p;
225 unsigned char b22, w22;
226 48 int demerit = 0;
227  
228 48 p = frame + width + 1;
229 1648 ▶ for(y=1; y<width; y++) {
Branch: 1 branch
BranchTrueFalseTotal
for(y=1; y<width; y++) { 1600 48 1648
230 63552 ▶ for(x=1; x<width; x++) {
Branch: 1 branch
BranchTrueFalseTotal
for(x=1; x<width; x++) { 61952 1600 63552
231 61952 b22 = p[0] & p[-1] & p[-width] & p [-width-1];
232 61952 w22 = p[0] | p[-1] | p[-width] | p [-width-1];
233 61952 ▶ if((b22 | (w22 ^ 1))&1) {
Branch: 1 branch
BranchTrueFalseTotal
if((b22 | (w22 ^ 1))&1) { 7083 54869 61952
234 7083 demerit += N2;
235 }
236 61952 p++;
237 }
238 1600 p++;
239 }
240  
241 48 return demerit;
242 }
243  
244 3296 __STATIC int Mask_calcRunLength(int width, unsigned char *frame, int dir, int *runLength)
245 {
246 int head;
247 int i;
248 unsigned char *p;
249 int pitch;
250  
251 3296 ▶ pitch = (dir==0)?1:width;
Branch: 1 branch
BranchTrueFalseTotal
pitch = (dir==0)?1:width; 1648 1648 3296
252 3296 ▶ if(frame[0] & 1) {
Branch: 1 branch
BranchTrueFalseTotal
if(frame[0] & 1) { 2207 1089 3296
253 2207 runLength[0] = -1;
254 2207 head = 1;
255 } else {
256 1089 head = 0;
257 }
258 3296 runLength[head] = 1;
259 3296 p = frame + pitch;
260  
261 130400 ▶ for(i=1; i<width; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for(i=1; i<width; i++) { 127104 3296 130400
262 127104 ▶ if((p[0] ^ p[-pitch]) & 1) {
Branch: 1 branch
BranchTrueFalseTotal
if((p[0] ^ p[-pitch]) & 1) { 62083 65021 127104
263 62083 head++;
264 62083 runLength[head] = 1;
265 } else {
266 65021 runLength[head]++;
267 }
268 127104 p += pitch;
269 }
270  
271 3296 return head + 1;
272 }
273  
274 48 __STATIC int Mask_evaluateSymbol(int width, unsigned char *frame)
275 {
276 int x, y;
277 48 int demerit = 0;
278 int runLength[QRSPEC_WIDTH_MAX + 1];
279 int length;
280  
281 48 demerit += Mask_calcN2(width, frame);
282  
283 1696 ▶ for(y=0; y<width; y++) {
Branch: 1 branch
BranchTrueFalseTotal
for(y=0; y<width; y++) { 1648 48 1696
284 1648 length = Mask_calcRunLength(width, frame + y * width, 0, runLength);
285 1648 demerit += Mask_calcN1N3(length, runLength);
286 }
287  
288 1696 ▶ for(x=0; x<width; x++) {
Branch: 1 branch
BranchTrueFalseTotal
for(x=0; x<width; x++) { 1648 48 1696
289 1648 length = Mask_calcRunLength(width, frame + x, 1, runLength);
290 1648 demerit += Mask_calcN1N3(length, runLength);
291 }
292  
293 48 return demerit;
294 }
295  
296 6 unsigned char *Mask_mask(int width, unsigned char *frame, QRecLevel level)
297 {
298 int i;
299 unsigned char *mask, *bestMask;
300 6 int minDemerit = INT_MAX;
301 int blacks;
302 int bratio;
303 int demerit;
304 6 int w2 = width * width;
305  
306 6 mask = (unsigned char *)malloc(w2);
307 6 ▶ if(mask == NULL) return NULL;
Branch: 1 branch
BranchTrueFalseTotal
if(mask == NULL) return NULL; 0 6 6
308 6 bestMask = NULL;
309  
310 54 ▶ for(i=0; i<maskNum; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for(i=0; i<maskNum; i++) { 48 6 54
311 // n1 = n2 = n3 = n4 = 0;
312 48 demerit = 0;
313 48 blacks = maskMakers[i](width, frame, mask);
314 48 blacks += Mask_writeFormatInformation(width, mask, i, level);
315 48 bratio = (200 * blacks + w2) / w2 / 2; /* (int)(100*blacks/w2+0.5) */
316 48 demerit = (abs(bratio - 50) / 5) * N4;
317 // n4 = demerit;
318 48 demerit += Mask_evaluateSymbol(width, mask);
319 // printf("(%d,%d,%d,%d)=%d\n", n1, n2, n3 ,n4, demerit);
320 48 ▶ if(demerit < minDemerit) {
Branch: 1 branch
BranchTrueFalseTotal
if(demerit < minDemerit) { 12 36 48
321 12 minDemerit = demerit;
322 12 free(bestMask);
323 12 bestMask = mask;
324 12 mask = (unsigned char *)malloc(w2);
325 12 ▶ if(mask == NULL) break;
Branch: 1 branch
BranchTrueFalseTotal
if(mask == NULL) break; 0 12 12
326 }
327 }
328 6 free(mask);
329 6 return bestMask;
330 }
« src/qrspec.c ↑ Summary