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__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	int blacks = 0;
40
41	format = QRspec_getFormatInfo(mask, level);
42
43	for(i=0; i<8; i++) {
44		if(format & 1) {
45			blacks += 2;
46			v = 0x85;
47		} else {
48			v = 0x84;
49		}
50		frame[width * 8 + width - 1 - i] = v;
51		if(i < 6) {
52			frame[width * i + 8] = v;
53		} else {
54			frame[width * (i + 1) + 8] = v;
55		}
56		format= format >> 1;
57	}
58	for(i=0; i<7; i++) {
59		if(format & 1) {
60			blacks += 2;
61			v = 0x85;
62		} else {
63			v = 0x84;
64		}
65		frame[width * (width - 7 + i) + 8] = v;
66		if(i == 0) {
67			frame[width * 8 + 7] = v;
68		} else {
69			frame[width * 8 + 6 - i] = v;
70		}
71		format= format >> 1;
72	}
73
74	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
103static int Mask_mask0(int width, const unsigned char *s, unsigned char *d)
104{
105	MASKMAKER((x+y)&1)
106}
107
108static int Mask_mask1(int width, const unsigned char *s, unsigned char *d)
109{
110	MASKMAKER(y&1)
111}
112
113static int Mask_mask2(int width, const unsigned char *s, unsigned char *d)
114{
115	MASKMAKER(x%3)
116}
117
118static int Mask_mask3(int width, const unsigned char *s, unsigned char *d)
119{
120	MASKMAKER((x+y)%3)
121}
122
123static int Mask_mask4(int width, const unsigned char *s, unsigned char *d)
124{
125	MASKMAKER(((y/2)+(x/3))&1)
126}
127
128static int Mask_mask5(int width, const unsigned char *s, unsigned char *d)
129{
130	MASKMAKER(((x*y)&1)+(x*y)%3)
131}
132
133static int Mask_mask6(int width, const unsigned char *s, unsigned char *d)
134{
135	MASKMAKER((((x*y)&1)+(x*y)%3)&1)
136}
137
138static int Mask_mask7(int width, const unsigned char *s, unsigned char *d)
139{
140	MASKMAKER((((x*y)%3)+((x+y)&1))&1)
141}
142
143#define maskNum (8)
144typedef int MaskMaker(int, const unsigned char *, unsigned char *);
145static 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
151unsigned 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
164unsigned char *Mask_makeMask(int width, unsigned char *frame, int mask, QRecLevel level)
165{
166	unsigned char *masked;
167
168	if(mask < 0 || mask >= maskNum) {
169		errno = EINVAL;
170		return NULL;
171	}
172
173	masked = (unsigned char *)malloc(width * width);
174	if(masked == NULL) return NULL;
175
176	maskMakers[mask](width, frame, masked);
177	Mask_writeFormatInformation(width, masked, mask, level);
178
179	return masked;
180}
181
182
183//static int n1;
184//static int n2;
185//static int n3;
186//static int n4;
187
188__STATIC int Mask_calcN1N3(int length, int *runLength)
189{
190	int i;
191	int demerit = 0;
192	int fact;
193
194	for(i=0; i<length; i++) {
195		if(runLength[i] >= 5) {
196			demerit += N1 + (runLength[i] - 5);
197			//n1 += N1 + (runLength[i] - 5);
198		}
199		if((i & 1)) {
200			if(i >= 3 && i < length-2 && (runLength[i] % 3) == 0) {
201				fact = runLength[i] / 3;
202				if(runLength[i-2] == fact &&
203				   runLength[i-1] == fact &&
204				   runLength[i+1] == fact &&
205				   runLength[i+2] == fact) {
206					if(i == 3 || runLength[i-3] >= 4 * fact) {
207						demerit += N3;
208						//n3 += N3;
209					} else if(i+4 >= length || runLength[i+3] >= 4 * fact) {
210						demerit += N3;
211						//n3 += N3;
212					}
213				}
214			}
215		}
216	}
217
218	return demerit;
219}
220
221__STATIC int Mask_calcN2(int width, unsigned char *frame)
222{
223	int x, y;
224	unsigned char *p;
225	unsigned char b22, w22;
226	int demerit = 0;
227
228	p = frame + width + 1;
229	for(y=1; y<width; y++) {
230		for(x=1; x<width; x++) {
231			b22 = p[0] & p[-1] & p[-width] & p [-width-1];
232			w22 = p[0] | p[-1] | p[-width] | p [-width-1];
233			if((b22 | (w22 ^ 1))&1) {
234				demerit += N2;
235			}
236			p++;
237		}
238		p++;
239	}
240
241	return demerit;
242}
243
244__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	pitch = (dir==0)?1:width;
252	if(frame[0] & 1) {
253		runLength[0] = -1;
254		head = 1;
255	} else {
256		head = 0;
257	}
258	runLength[head] = 1;
259	p = frame + pitch;
260
261	for(i=1; i<width; i++) {
262		if((p[0] ^ p[-pitch]) & 1) {
263			head++;
264			runLength[head] = 1;
265		} else {
266			runLength[head]++;
267		}
268		p += pitch;
269	}
270
271	return head + 1;
272}
273
274__STATIC int Mask_evaluateSymbol(int width, unsigned char *frame)
275{
276	int x, y;
277	int demerit = 0;
278	int runLength[QRSPEC_WIDTH_MAX + 1];
279	int length;
280
281	demerit += Mask_calcN2(width, frame);
282
283	for(y=0; y<width; y++) {
284		length = Mask_calcRunLength(width, frame + y * width, 0, runLength);
285		demerit += Mask_calcN1N3(length, runLength);
286	}
287
288	for(x=0; x<width; x++) {
289		length = Mask_calcRunLength(width, frame + x, 1, runLength);
290		demerit += Mask_calcN1N3(length, runLength);
291	}
292
293	return demerit;
294}
295
296unsigned char *Mask_mask(int width, unsigned char *frame, QRecLevel level)
297{
298	int i;
299	unsigned char *mask, *bestMask;
300	int minDemerit = INT_MAX;
301	int blacks;
302	int bratio;
303	int demerit;
304	int w2 = width * width;
305
306	mask = (unsigned char *)malloc(w2);
307	if(mask == NULL) return NULL;
308	bestMask = NULL;
309
310	for(i=0; i<maskNum; i++) {
311//		n1 = n2 = n3 = n4 = 0;
312		demerit = 0;
313		blacks = maskMakers[i](width, frame, mask);
314		blacks += Mask_writeFormatInformation(width, mask, i, level);
315		bratio = (200 * blacks + w2) / w2 / 2; /* (int)(100*blacks/w2+0.5) */
316		demerit = (abs(bratio - 50) / 5) * N4;
317//		n4 = demerit;
318		demerit += Mask_evaluateSymbol(width, mask);
319//		printf("(%d,%d,%d,%d)=%d\n", n1, n2, n3 ,n4, demerit);
320		if(demerit < minDemerit) {
321			minDemerit = demerit;
322			free(bestMask);
323			bestMask = mask;
324			mask = (unsigned char *)malloc(w2);
325			if(mask == NULL) break;
326		}
327	}
328	free(mask);
329	return bestMask;
330}
331