git.sur5r.net Git - glabels/blob - qrencode-3.1.0/mask.c

   1 /*
   2  * qrencode - QR Code encoder
   3  *
   4  * Masking.
   5  * Copyright (C) 2006, 2007, 2008, 2009 Kentaro Fukuchi <fukuchi@megaui.net>
   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 #include <stdlib.h>
  23 #include <string.h>
  24 #include <limits.h>
  25 #include "config.h"
  26 #include "qrencode.h"
  27 #include "qrspec.h"
  28 #include "mask.h"
  29
  30 __STATIC int Mask_writeFormatInformation(int width, unsigned char *frame, int mask, QRecLevel level)
  31 {
  32         unsigned int format;
  33         unsigned char v;
  34         int i;
  35         int blacks = 0;
  36
  37         format =  QRspec_getFormatInfo(mask, level);
  38
  39         for(i=0; i<8; i++) {
  40                 if(format & 1) {
  41                         blacks += 2;
  42                         v = 0x85;
  43                 } else {
  44                         v = 0x84;
  45                 }
  46                 frame[width * 8 + width - 1 - i] = v;
  47                 if(i < 6) {
  48                         frame[width * i + 8] = v;
  49                 } else {
  50                         frame[width * (i + 1) + 8] = v;
  51                 }
  52                 format= format >> 1;
  53         }
  54         for(i=0; i<7; i++) {
  55                 if(format & 1) {
  56                         blacks += 2;
  57                         v = 0x85;
  58                 } else {
  59                         v = 0x84;
  60                 }
  61                 frame[width * (width - 7 + i) + 8] = v;
  62                 if(i == 0) {
  63                         frame[width * 8 + 7] = v;
  64                 } else {
  65                         frame[width * 8 + 6 - i] = v;
  66                 }
  67                 format= format >> 1;
  68         }
  69
  70         return blacks;
  71 }
  72
  73 /**
  74  * Demerit coefficients.
  75  * See Section 8.8.2, pp.45, JIS X0510:2004.
  76  */
  77 #define N1 (3)
  78 #define N2 (3)
  79 #define N3 (40)
  80 #define N4 (10)
  81
  82 #define MASKMAKER(__exp__) \
  83         int x, y;\
  84         int b = 0;\
  85 \
  86         for(y=0; y<width; y++) {\
  87                 for(x=0; x<width; x++) {\
  88                         if(*s & 0x80) {\
  89                                 *d = *s;\
  90                         } else {\
  91                                 *d = *s ^ ((__exp__) == 0);\
  92                         }\
  93                         b += (int)(*d & 1);\
  94                         s++; d++;\
  95                 }\
  96         }\
  97         return b;
  98
  99 static int Mask_mask0(int width, const unsigned char *s, unsigned char *d)
 100 {
 101         MASKMAKER((x+y)&1)
 102 }
 103
 104 static int Mask_mask1(int width, const unsigned char *s, unsigned char *d)
 105 {
 106         MASKMAKER(y&1)
 107 }
 108
 109 static int Mask_mask2(int width, const unsigned char *s, unsigned char *d)
 110 {
 111         MASKMAKER(x%3)
 112 }
 113
 114 static int Mask_mask3(int width, const unsigned char *s, unsigned char *d)
 115 {
 116         MASKMAKER((x+y)%3)
 117 }
 118
 119 static int Mask_mask4(int width, const unsigned char *s, unsigned char *d)
 120 {
 121         MASKMAKER(((y/2)+(x/3))&1)
 122 }
 123
 124 static int Mask_mask5(int width, const unsigned char *s, unsigned char *d)
 125 {
 126         MASKMAKER(((x*y)&1)+(x*y)%3)
 127 }
 128
 129 static int Mask_mask6(int width, const unsigned char *s, unsigned char *d)
 130 {
 131         MASKMAKER((((x*y)&1)+(x*y)%3)&1)
 132 }
 133
 134 static int Mask_mask7(int width, const unsigned char *s, unsigned char *d)
 135 {
 136         MASKMAKER((((x*y)%3)+((x+y)&1))&1)
 137 }
 138
 139 typedef int MaskMaker(int, const unsigned char *, unsigned char *);
 140 static MaskMaker *maskMakers[] = {
 141         Mask_mask0, Mask_mask1, Mask_mask2, Mask_mask3,
 142         Mask_mask4, Mask_mask5, Mask_mask6, Mask_mask7
 143 };
 144
 145 unsigned char *Mask_makeMask(int width, unsigned char *frame, int mask, QRecLevel level)
 146 {
 147         unsigned char *masked;
 148
 149         masked = (unsigned char *)malloc(width * width);
 150         if(masked == NULL) return NULL;
 151
 152         maskMakers[mask](width, frame, masked);
 153         Mask_writeFormatInformation(width, masked, mask, level);
 154
 155         return masked;
 156 }
 157
 158 static int runLength[QRSPEC_WIDTH_MAX + 1];
 159
 160 //static int n1;
 161 //static int n2;
 162 //static int n3;
 163 //static int n4;
 164
 165 static int Mask_calcN1N3(int length, int *runLength)
 166 {
 167         int i;
 168         int demerit = 0;
 169         int fact;
 170
 171         for(i=0; i<length; i++) {
 172                 if(runLength[i] >= 5) {
 173                         demerit += N1 + (runLength[i] - 5);
 174                         //n1 += N1 + (runLength[i] - 5);
 175                 }
 176                 if((i & 1)) {
 177                         if(i >= 3 && i < length-2 && (runLength[i] % 3) == 0) {
 178                                 fact = runLength[i] / 3;
 179                                 if(runLength[i-2] == fact &&
 180                                    runLength[i-1] == fact &&
 181                                    runLength[i+1] == fact &&
 182                                    runLength[i+2] == fact) {
 183                                         if(runLength[i-3] < 0 || runLength[i-3] >= 4 * fact) {
 184                                                 demerit += N3;
 185                                                 //n3 += N3;
 186                                         } else if(i+3 >= length || runLength[i+3] >= 4 * fact) {
 187                                                 demerit += N3;
 188                                                 //n3 += N3;
 189                                         }
 190                                 }
 191                         }
 192                 }
 193         }
 194
 195         return demerit;
 196 }
 197
 198 __STATIC int Mask_evaluateSymbol(int width, unsigned char *frame)
 199 {
 200         int x, y;
 201         unsigned char *p;
 202         unsigned char b22, w22;
 203         int head;
 204         int demerit = 0;
 205
 206         p = frame;
 207         for(y=0; y<width; y++) {
 208                 head = 0;
 209                 runLength[0] = 1;
 210                 for(x=0; x<width; x++) {
 211                         if(x > 0 && y > 0) {
 212                                 b22 = p[0] & p[-1] & p[-width] & p [-width-1];
 213                                 w22 = p[0] | p[-1] | p[-width] | p [-width-1];
 214                                 if((b22 | (w22 ^ 1))&1) {
 215                                         demerit += N2;
 216                                 }
 217                         }
 218                         if(x == 0 && (p[0] & 1)) {
 219                                 runLength[0] = -1;
 220                                 head = 1;
 221                                 runLength[head] = 1;
 222                         } else if(x > 0) {
 223                                 if((p[0] ^ p[-1]) & 1) {
 224                                         head++;
 225                                         runLength[head] = 1;
 226                                 } else {
 227                                         runLength[head]++;
 228                                 }
 229                         }
 230                         p++;
 231                 }
 232                 demerit += Mask_calcN1N3(head+1, runLength);
 233         }
 234
 235         for(x=0; x<width; x++) {
 236                 head = 0;
 237                 runLength[0] = 1;
 238                 p = frame + x;
 239                 for(y=0; y<width; y++) {
 240                         if(y == 0 && (p[0] & 1)) {
 241                                 runLength[0] = -1;
 242                                 head = 1;
 243                                 runLength[head] = 1;
 244                         } else if(y > 0) {
 245                                 if((p[0] ^ p[-width]) & 1) {
 246                                         head++;
 247                                         runLength[head] = 1;
 248                                 } else {
 249                                         runLength[head]++;
 250                                 }
 251                         }
 252                         p+=width;
 253                 }
 254                 demerit += Mask_calcN1N3(head+1, runLength);
 255         }
 256
 257         return demerit;
 258 }
 259
 260 unsigned char *Mask_mask(int width, unsigned char *frame, QRecLevel level)
 261 {
 262         int i;
 263         unsigned char *mask, *bestMask;
 264         int minDemerit = INT_MAX;
 265         int bestMaskNum = 0;
 266         int blacks;
 267         int demerit;
 268
 269         mask = (unsigned char *)malloc(width * width);
 270         if(mask == NULL) return NULL;
 271         bestMask = NULL;
 272
 273         for(i=0; i<8; i++) {
 274 //              n1 = n2 = n3 = n4 = 0;
 275                 demerit = 0;
 276                 blacks = maskMakers[i](width, frame, mask);
 277                 blacks += Mask_writeFormatInformation(width, mask, i, level);
 278                 blacks = 100 * blacks / (width * width);
 279                 demerit = (abs(blacks - 50) / 5) * N4;
 280 //              n4 = demerit;
 281                 demerit += Mask_evaluateSymbol(width, mask);
 282 //              printf("(%d,%d,%d,%d)=%d\n", n1, n2, n3 ,n4, demerit);
 283                 if(demerit < minDemerit) {
 284                         minDemerit = demerit;
 285                         bestMaskNum = i;
 286                         if(bestMask != NULL) {
 287                                 free(bestMask);
 288                         }
 289                         bestMask = (unsigned char *)malloc(width * width);
 290                         if(bestMask == NULL) break;
 291                         memcpy(bestMask, mask, width * width);
 292                 }
 293         }
 294         free(mask);
 295         return bestMask;
 296 }