1// go-qrcode 2// Copyright 2014 Tom Harwood 3 4package qrcode 5 6// symbol is a 2D array of bits representing a QR Code symbol. 7// 8// A symbol consists of size*size modules, with each module normally drawn as a 9// black or white square. The symbol also has a border of quietZoneSize modules. 10// 11// A (fictional) size=2, quietZoneSize=1 QR Code looks like: 12// 13// +----+ 14// | | 15// | ab | 16// | cd | 17// | | 18// +----+ 19// 20// For ease of implementation, the functions to set/get bits ignore the border, 21// so (0,0)=a, (0,1)=b, (1,0)=c, and (1,1)=d. The entire symbol (including the 22// border) is returned by bitmap(). 23// 24type symbol struct { 25 // Value of module at [y][x]. True is set. 26 module [][]bool 27 28 // True if the module at [y][x] is used (to either true or false). 29 // Used to identify unused modules. 30 isUsed [][]bool 31 32 // Combined width/height of the symbol and quiet zones. 33 // 34 // size = symbolSize + 2*quietZoneSize. 35 size int 36 37 // Width/height of the symbol only. 38 symbolSize int 39 40 // Width/height of a single quiet zone. 41 quietZoneSize int 42} 43 44// newSymbol constructs a symbol of size size*size, with a border of 45// quietZoneSize. 46func newSymbol(size int, quietZoneSize int) *symbol { 47 var m symbol 48 49 m.module = make([][]bool, size+2*quietZoneSize) 50 m.isUsed = make([][]bool, size+2*quietZoneSize) 51 52 for i := range m.module { 53 m.module[i] = make([]bool, size+2*quietZoneSize) 54 m.isUsed[i] = make([]bool, size+2*quietZoneSize) 55 } 56 57 m.size = size + 2*quietZoneSize 58 m.symbolSize = size 59 m.quietZoneSize = quietZoneSize 60 61 return &m 62} 63 64// get returns the module value at (x, y). 65func (m *symbol) get(x int, y int) (v bool) { 66 v = m.module[y+m.quietZoneSize][x+m.quietZoneSize] 67 return 68} 69 70// empty returns true if the module at (x, y) has not been set (to either true 71// or false). 72func (m *symbol) empty(x int, y int) bool { 73 return !m.isUsed[y+m.quietZoneSize][x+m.quietZoneSize] 74} 75 76// numEmptyModules returns the number of empty modules. 77// 78// Initially numEmptyModules is symbolSize * symbolSize. After every module has 79// been set (to either true or false), the number of empty modules is zero. 80func (m *symbol) numEmptyModules() int { 81 var count int 82 for y := 0; y < m.symbolSize; y++ { 83 for x := 0; x < m.symbolSize; x++ { 84 if !m.isUsed[y+m.quietZoneSize][x+m.quietZoneSize] { 85 count++ 86 } 87 } 88 } 89 90 return count 91} 92 93// set sets the module at (x, y) to v. 94func (m *symbol) set(x int, y int, v bool) { 95 m.module[y+m.quietZoneSize][x+m.quietZoneSize] = v 96 m.isUsed[y+m.quietZoneSize][x+m.quietZoneSize] = true 97} 98 99// set2dPattern sets a 2D array of modules, starting at (x, y). 100func (m *symbol) set2dPattern(x int, y int, v [][]bool) { 101 for j, row := range v { 102 for i, value := range row { 103 m.set(x+i, y+j, value) 104 } 105 } 106} 107 108// bitmap returns the entire symbol, including the quiet zone. 109func (m *symbol) bitmap() [][]bool { 110 module := make([][]bool, len(m.module)) 111 112 for i := range m.module { 113 module[i] = m.module[i][:] 114 } 115 116 return module 117} 118 119// string returns a pictorial representation of the symbol, suitable for 120// printing in a TTY. 121func (m *symbol) string() string { 122 var result string 123 124 for _, row := range m.module { 125 for _, value := range row { 126 switch value { 127 case true: 128 result += " " 129 case false: 130 // Unicode 'FULL BLOCK' (U+2588). 131 result += "██" 132 } 133 } 134 result += "\n" 135 } 136 137 return result 138} 139 140// Constants used to weight penalty calculations. Specified by ISO/IEC 141// 18004:2006. 142const ( 143 penaltyWeight1 = 3 144 penaltyWeight2 = 3 145 penaltyWeight3 = 40 146 penaltyWeight4 = 10 147) 148 149// penaltyScore returns the penalty score of the symbol. The penalty score 150// consists of the sum of the four individual penalty types. 151func (m *symbol) penaltyScore() int { 152 return m.penalty1() + m.penalty2() + m.penalty3() + m.penalty4() 153} 154 155// penalty1 returns the penalty score for "adjacent modules in row/column with 156// same colour". 157// 158// The numbers of adjacent matching modules and scores are: 159// 0-5: score = 0 160// 6+ : score = penaltyWeight1 + (numAdjacentModules - 5) 161func (m *symbol) penalty1() int { 162 penalty := 0 163 164 for x := 0; x < m.symbolSize; x++ { 165 lastValue := m.get(x, 0) 166 count := 1 167 168 for y := 1; y < m.symbolSize; y++ { 169 v := m.get(x, y) 170 171 if v != lastValue { 172 count = 1 173 lastValue = v 174 } else { 175 count++ 176 if count == 6 { 177 penalty += penaltyWeight1 + 1 178 } else if count > 6 { 179 penalty++ 180 } 181 } 182 } 183 } 184 185 for y := 0; y < m.symbolSize; y++ { 186 lastValue := m.get(0, y) 187 count := 1 188 189 for x := 1; x < m.symbolSize; x++ { 190 v := m.get(x, y) 191 192 if v != lastValue { 193 count = 1 194 lastValue = v 195 } else { 196 count++ 197 if count == 6 { 198 penalty += penaltyWeight1 + 1 199 } else if count > 6 { 200 penalty++ 201 } 202 } 203 } 204 } 205 206 return penalty 207} 208 209// penalty2 returns the penalty score for "block of modules in the same colour". 210// 211// m*n: score = penaltyWeight2 * (m-1) * (n-1). 212func (m *symbol) penalty2() int { 213 penalty := 0 214 215 for y := 1; y < m.symbolSize; y++ { 216 for x := 1; x < m.symbolSize; x++ { 217 topLeft := m.get(x-1, y-1) 218 above := m.get(x, y-1) 219 left := m.get(x-1, y) 220 current := m.get(x, y) 221 222 if current == left && current == above && current == topLeft { 223 penalty++ 224 } 225 } 226 } 227 228 return penalty * penaltyWeight2 229} 230 231// penalty3 returns the penalty score for "1:1:3:1:1 ratio 232// (dark:light:dark:light:dark) pattern in row/column, preceded or followed by 233// light area 4 modules wide". 234// 235// Existence of the pattern scores penaltyWeight3. 236func (m *symbol) penalty3() int { 237 penalty := 0 238 239 for y := 0; y < m.symbolSize; y++ { 240 var bitBuffer int16 = 0x00 241 242 for x := 0; x < m.symbolSize; x++ { 243 bitBuffer <<= 1 244 if v := m.get(x, y); v { 245 bitBuffer |= 1 246 } 247 248 switch bitBuffer & 0x7ff { 249 // 0b000 0101 1101 or 0b10111010000 250 // 0x05d or 0x5d0 251 case 0x05d, 0x5d0: 252 penalty += penaltyWeight3 253 bitBuffer = 0xFF 254 default: 255 if x == m.symbolSize-1 && (bitBuffer&0x7f) == 0x5d { 256 penalty += penaltyWeight3 257 bitBuffer = 0xFF 258 } 259 } 260 } 261 } 262 263 for x := 0; x < m.symbolSize; x++ { 264 var bitBuffer int16 = 0x00 265 266 for y := 0; y < m.symbolSize; y++ { 267 bitBuffer <<= 1 268 if v := m.get(x, y); v { 269 bitBuffer |= 1 270 } 271 272 switch bitBuffer & 0x7ff { 273 // 0b000 0101 1101 or 0b10111010000 274 // 0x05d or 0x5d0 275 case 0x05d, 0x5d0: 276 penalty += penaltyWeight3 277 bitBuffer = 0xFF 278 default: 279 if y == m.symbolSize-1 && (bitBuffer&0x7f) == 0x5d { 280 penalty += penaltyWeight3 281 bitBuffer = 0xFF 282 } 283 } 284 } 285 } 286 287 return penalty 288} 289 290// penalty4 returns the penalty score... 291func (m *symbol) penalty4() int { 292 numModules := m.symbolSize * m.symbolSize 293 numDarkModules := 0 294 295 for x := 0; x < m.symbolSize; x++ { 296 for y := 0; y < m.symbolSize; y++ { 297 if v := m.get(x, y); v { 298 numDarkModules++ 299 } 300 } 301 } 302 303 numDarkModuleDeviation := numModules/2 - numDarkModules 304 if numDarkModuleDeviation < 0 { 305 numDarkModuleDeviation *= -1 306 } 307 308 return penaltyWeight4 * (numDarkModuleDeviation / (numModules / 20)) 309} 310