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