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