Codebase list golang-rsc-qr / upstream/0.0_git20161121.48b2ede
Import Upstream version 0.0~git20161121.48b2ede Michael Meskes 6 years ago
12 changed file(s) with 2385 addition(s) and 0 deletion(s). Raw diff Collapse all Expand all
+27
-0
LICENSE less more
0 Copyright (c) 2009 The Go Authors. All rights reserved.
1
2 Redistribution and use in source and binary forms, with or without
3 modification, are permitted provided that the following conditions are
4 met:
5
6 * Redistributions of source code must retain the above copyright
7 notice, this list of conditions and the following disclaimer.
8 * Redistributions in binary form must reproduce the above
9 copyright notice, this list of conditions and the following disclaimer
10 in the documentation and/or other materials provided with the
11 distribution.
12 * Neither the name of Google Inc. nor the names of its
13 contributors may be used to endorse or promote products derived from
14 this software without specific prior written permission.
15
16 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+3
-0
README.md less more
0 Basic QR encoder.
1
2 go get [-u] rsc.io/qr
+149
-0
coding/gen.go less more
0 // +build ignore
1
2 package main
3
4 import "fmt"
5
6 // tables from qrencode-3.1.1/qrspec.c
7
8 var capacity = [41]struct {
9 width int
10 words int
11 remainder int
12 ec [4]int
13 }{
14 {0, 0, 0, [4]int{0, 0, 0, 0}},
15 {21, 26, 0, [4]int{7, 10, 13, 17}}, // 1
16 {25, 44, 7, [4]int{10, 16, 22, 28}},
17 {29, 70, 7, [4]int{15, 26, 36, 44}},
18 {33, 100, 7, [4]int{20, 36, 52, 64}},
19 {37, 134, 7, [4]int{26, 48, 72, 88}}, // 5
20 {41, 172, 7, [4]int{36, 64, 96, 112}},
21 {45, 196, 0, [4]int{40, 72, 108, 130}},
22 {49, 242, 0, [4]int{48, 88, 132, 156}},
23 {53, 292, 0, [4]int{60, 110, 160, 192}},
24 {57, 346, 0, [4]int{72, 130, 192, 224}}, //10
25 {61, 404, 0, [4]int{80, 150, 224, 264}},
26 {65, 466, 0, [4]int{96, 176, 260, 308}},
27 {69, 532, 0, [4]int{104, 198, 288, 352}},
28 {73, 581, 3, [4]int{120, 216, 320, 384}},
29 {77, 655, 3, [4]int{132, 240, 360, 432}}, //15
30 {81, 733, 3, [4]int{144, 280, 408, 480}},
31 {85, 815, 3, [4]int{168, 308, 448, 532}},
32 {89, 901, 3, [4]int{180, 338, 504, 588}},
33 {93, 991, 3, [4]int{196, 364, 546, 650}},
34 {97, 1085, 3, [4]int{224, 416, 600, 700}}, //20
35 {101, 1156, 4, [4]int{224, 442, 644, 750}},
36 {105, 1258, 4, [4]int{252, 476, 690, 816}},
37 {109, 1364, 4, [4]int{270, 504, 750, 900}},
38 {113, 1474, 4, [4]int{300, 560, 810, 960}},
39 {117, 1588, 4, [4]int{312, 588, 870, 1050}}, //25
40 {121, 1706, 4, [4]int{336, 644, 952, 1110}},
41 {125, 1828, 4, [4]int{360, 700, 1020, 1200}},
42 {129, 1921, 3, [4]int{390, 728, 1050, 1260}},
43 {133, 2051, 3, [4]int{420, 784, 1140, 1350}},
44 {137, 2185, 3, [4]int{450, 812, 1200, 1440}}, //30
45 {141, 2323, 3, [4]int{480, 868, 1290, 1530}},
46 {145, 2465, 3, [4]int{510, 924, 1350, 1620}},
47 {149, 2611, 3, [4]int{540, 980, 1440, 1710}},
48 {153, 2761, 3, [4]int{570, 1036, 1530, 1800}},
49 {157, 2876, 0, [4]int{570, 1064, 1590, 1890}}, //35
50 {161, 3034, 0, [4]int{600, 1120, 1680, 1980}},
51 {165, 3196, 0, [4]int{630, 1204, 1770, 2100}},
52 {169, 3362, 0, [4]int{660, 1260, 1860, 2220}},
53 {173, 3532, 0, [4]int{720, 1316, 1950, 2310}},
54 {177, 3706, 0, [4]int{750, 1372, 2040, 2430}}, //40
55 }
56
57 var eccTable = [41][4][2]int{
58 {{0, 0}, {0, 0}, {0, 0}, {0, 0}},
59 {{1, 0}, {1, 0}, {1, 0}, {1, 0}}, // 1
60 {{1, 0}, {1, 0}, {1, 0}, {1, 0}},
61 {{1, 0}, {1, 0}, {2, 0}, {2, 0}},
62 {{1, 0}, {2, 0}, {2, 0}, {4, 0}},
63 {{1, 0}, {2, 0}, {2, 2}, {2, 2}}, // 5
64 {{2, 0}, {4, 0}, {4, 0}, {4, 0}},
65 {{2, 0}, {4, 0}, {2, 4}, {4, 1}},
66 {{2, 0}, {2, 2}, {4, 2}, {4, 2}},
67 {{2, 0}, {3, 2}, {4, 4}, {4, 4}},
68 {{2, 2}, {4, 1}, {6, 2}, {6, 2}}, //10
69 {{4, 0}, {1, 4}, {4, 4}, {3, 8}},
70 {{2, 2}, {6, 2}, {4, 6}, {7, 4}},
71 {{4, 0}, {8, 1}, {8, 4}, {12, 4}},
72 {{3, 1}, {4, 5}, {11, 5}, {11, 5}},
73 {{5, 1}, {5, 5}, {5, 7}, {11, 7}}, //15
74 {{5, 1}, {7, 3}, {15, 2}, {3, 13}},
75 {{1, 5}, {10, 1}, {1, 15}, {2, 17}},
76 {{5, 1}, {9, 4}, {17, 1}, {2, 19}},
77 {{3, 4}, {3, 11}, {17, 4}, {9, 16}},
78 {{3, 5}, {3, 13}, {15, 5}, {15, 10}}, //20
79 {{4, 4}, {17, 0}, {17, 6}, {19, 6}},
80 {{2, 7}, {17, 0}, {7, 16}, {34, 0}},
81 {{4, 5}, {4, 14}, {11, 14}, {16, 14}},
82 {{6, 4}, {6, 14}, {11, 16}, {30, 2}},
83 {{8, 4}, {8, 13}, {7, 22}, {22, 13}}, //25
84 {{10, 2}, {19, 4}, {28, 6}, {33, 4}},
85 {{8, 4}, {22, 3}, {8, 26}, {12, 28}},
86 {{3, 10}, {3, 23}, {4, 31}, {11, 31}},
87 {{7, 7}, {21, 7}, {1, 37}, {19, 26}},
88 {{5, 10}, {19, 10}, {15, 25}, {23, 25}}, //30
89 {{13, 3}, {2, 29}, {42, 1}, {23, 28}},
90 {{17, 0}, {10, 23}, {10, 35}, {19, 35}},
91 {{17, 1}, {14, 21}, {29, 19}, {11, 46}},
92 {{13, 6}, {14, 23}, {44, 7}, {59, 1}},
93 {{12, 7}, {12, 26}, {39, 14}, {22, 41}}, //35
94 {{6, 14}, {6, 34}, {46, 10}, {2, 64}},
95 {{17, 4}, {29, 14}, {49, 10}, {24, 46}},
96 {{4, 18}, {13, 32}, {48, 14}, {42, 32}},
97 {{20, 4}, {40, 7}, {43, 22}, {10, 67}},
98 {{19, 6}, {18, 31}, {34, 34}, {20, 61}}, //40
99 }
100
101 var align = [41][2]int{
102 {0, 0},
103 {0, 0}, {18, 0}, {22, 0}, {26, 0}, {30, 0}, // 1- 5
104 {34, 0}, {22, 38}, {24, 42}, {26, 46}, {28, 50}, // 6-10
105 {30, 54}, {32, 58}, {34, 62}, {26, 46}, {26, 48}, //11-15
106 {26, 50}, {30, 54}, {30, 56}, {30, 58}, {34, 62}, //16-20
107 {28, 50}, {26, 50}, {30, 54}, {28, 54}, {32, 58}, //21-25
108 {30, 58}, {34, 62}, {26, 50}, {30, 54}, {26, 52}, //26-30
109 {30, 56}, {34, 60}, {30, 58}, {34, 62}, {30, 54}, //31-35
110 {24, 50}, {28, 54}, {32, 58}, {26, 54}, {30, 58}, //35-40
111 }
112
113 var versionPattern = [41]int{
114 0,
115 0, 0, 0, 0, 0, 0,
116 0x07c94, 0x085bc, 0x09a99, 0x0a4d3, 0x0bbf6, 0x0c762, 0x0d847, 0x0e60d,
117 0x0f928, 0x10b78, 0x1145d, 0x12a17, 0x13532, 0x149a6, 0x15683, 0x168c9,
118 0x177ec, 0x18ec4, 0x191e1, 0x1afab, 0x1b08e, 0x1cc1a, 0x1d33f, 0x1ed75,
119 0x1f250, 0x209d5, 0x216f0, 0x228ba, 0x2379f, 0x24b0b, 0x2542e, 0x26a64,
120 0x27541, 0x28c69,
121 }
122
123 func main() {
124 fmt.Printf("\t{},\n")
125 for i := 1; i <= 40; i++ {
126 apos := align[i][0] - 2
127 if apos < 0 {
128 apos = 100
129 }
130 astride := align[i][1] - align[i][0]
131 if astride < 1 {
132 astride = 100
133 }
134 fmt.Printf("\t{%v, %v, %v, %#x, [4]level{{%v, %v}, {%v, %v}, {%v, %v}, {%v, %v}}}, // %v\n",
135 apos, astride, capacity[i].words,
136 versionPattern[i],
137 eccTable[i][0][0]+eccTable[i][0][1],
138 float64(capacity[i].ec[0])/float64(eccTable[i][0][0]+eccTable[i][0][1]),
139 eccTable[i][1][0]+eccTable[i][1][1],
140 float64(capacity[i].ec[1])/float64(eccTable[i][1][0]+eccTable[i][1][1]),
141 eccTable[i][2][0]+eccTable[i][2][1],
142 float64(capacity[i].ec[2])/float64(eccTable[i][2][0]+eccTable[i][2][1]),
143 eccTable[i][3][0]+eccTable[i][3][1],
144 float64(capacity[i].ec[3])/float64(eccTable[i][3][0]+eccTable[i][3][1]),
145 i,
146 )
147 }
148 }
+815
-0
coding/qr.go less more
0 // Copyright 2011 The Go Authors. All rights reserved.
1 // Use of this source code is governed by a BSD-style
2 // license that can be found in the LICENSE file.
3
4 // Package coding implements low-level QR coding details.
5 package coding
6
7 import (
8 "fmt"
9 "strconv"
10 "strings"
11
12 "rsc.io/qr/gf256"
13 )
14
15 // Field is the field for QR error correction.
16 var Field = gf256.NewField(0x11d, 2)
17
18 // A Version represents a QR version.
19 // The version specifies the size of the QR code:
20 // a QR code with version v has 4v+17 pixels on a side.
21 // Versions number from 1 to 40: the larger the version,
22 // the more information the code can store.
23 type Version int
24
25 const MinVersion = 1
26 const MaxVersion = 40
27
28 func (v Version) String() string {
29 return strconv.Itoa(int(v))
30 }
31
32 func (v Version) sizeClass() int {
33 if v <= 9 {
34 return 0
35 }
36 if v <= 26 {
37 return 1
38 }
39 return 2
40 }
41
42 // DataBytes returns the number of data bytes that can be
43 // stored in a QR code with the given version and level.
44 func (v Version) DataBytes(l Level) int {
45 vt := &vtab[v]
46 lev := &vt.level[l]
47 return vt.bytes - lev.nblock*lev.check
48 }
49
50 // Encoding implements a QR data encoding scheme.
51 // The implementations--Numeric, Alphanumeric, and String--specify
52 // the character set and the mapping from UTF-8 to code bits.
53 // The more restrictive the mode, the fewer code bits are needed.
54 type Encoding interface {
55 Check() error
56 Bits(v Version) int
57 Encode(b *Bits, v Version)
58 }
59
60 type Bits struct {
61 b []byte
62 nbit int
63 }
64
65 func (b *Bits) Reset() {
66 b.b = b.b[:0]
67 b.nbit = 0
68 }
69
70 func (b *Bits) Bits() int {
71 return b.nbit
72 }
73
74 func (b *Bits) Bytes() []byte {
75 if b.nbit%8 != 0 {
76 panic("fractional byte")
77 }
78 return b.b
79 }
80
81 func (b *Bits) Append(p []byte) {
82 if b.nbit%8 != 0 {
83 panic("fractional byte")
84 }
85 b.b = append(b.b, p...)
86 b.nbit += 8 * len(p)
87 }
88
89 func (b *Bits) Write(v uint, nbit int) {
90 for nbit > 0 {
91 n := nbit
92 if n > 8 {
93 n = 8
94 }
95 if b.nbit%8 == 0 {
96 b.b = append(b.b, 0)
97 } else {
98 m := -b.nbit & 7
99 if n > m {
100 n = m
101 }
102 }
103 b.nbit += n
104 sh := uint(nbit - n)
105 b.b[len(b.b)-1] |= uint8(v >> sh << uint(-b.nbit&7))
106 v -= v >> sh << sh
107 nbit -= n
108 }
109 }
110
111 // Num is the encoding for numeric data.
112 // The only valid characters are the decimal digits 0 through 9.
113 type Num string
114
115 func (s Num) String() string {
116 return fmt.Sprintf("Num(%#q)", string(s))
117 }
118
119 func (s Num) Check() error {
120 for _, c := range s {
121 if c < '0' || '9' < c {
122 return fmt.Errorf("non-numeric string %#q", string(s))
123 }
124 }
125 return nil
126 }
127
128 var numLen = [3]int{10, 12, 14}
129
130 func (s Num) Bits(v Version) int {
131 return 4 + numLen[v.sizeClass()] + (10*len(s)+2)/3
132 }
133
134 func (s Num) Encode(b *Bits, v Version) {
135 b.Write(1, 4)
136 b.Write(uint(len(s)), numLen[v.sizeClass()])
137 var i int
138 for i = 0; i+3 <= len(s); i += 3 {
139 w := uint(s[i]-'0')*100 + uint(s[i+1]-'0')*10 + uint(s[i+2]-'0')
140 b.Write(w, 10)
141 }
142 switch len(s) - i {
143 case 1:
144 w := uint(s[i] - '0')
145 b.Write(w, 4)
146 case 2:
147 w := uint(s[i]-'0')*10 + uint(s[i+1]-'0')
148 b.Write(w, 7)
149 }
150 }
151
152 // Alpha is the encoding for alphanumeric data.
153 // The valid characters are 0-9A-Z$%*+-./: and space.
154 type Alpha string
155
156 const alphabet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:"
157
158 func (s Alpha) String() string {
159 return fmt.Sprintf("Alpha(%#q)", string(s))
160 }
161
162 func (s Alpha) Check() error {
163 for _, c := range s {
164 if strings.IndexRune(alphabet, c) < 0 {
165 return fmt.Errorf("non-alphanumeric string %#q", string(s))
166 }
167 }
168 return nil
169 }
170
171 var alphaLen = [3]int{9, 11, 13}
172
173 func (s Alpha) Bits(v Version) int {
174 return 4 + alphaLen[v.sizeClass()] + (11*len(s)+1)/2
175 }
176
177 func (s Alpha) Encode(b *Bits, v Version) {
178 b.Write(2, 4)
179 b.Write(uint(len(s)), alphaLen[v.sizeClass()])
180 var i int
181 for i = 0; i+2 <= len(s); i += 2 {
182 w := uint(strings.IndexRune(alphabet, rune(s[i])))*45 +
183 uint(strings.IndexRune(alphabet, rune(s[i+1])))
184 b.Write(w, 11)
185 }
186
187 if i < len(s) {
188 w := uint(strings.IndexRune(alphabet, rune(s[i])))
189 b.Write(w, 6)
190 }
191 }
192
193 // String is the encoding for 8-bit data. All bytes are valid.
194 type String string
195
196 func (s String) String() string {
197 return fmt.Sprintf("String(%#q)", string(s))
198 }
199
200 func (s String) Check() error {
201 return nil
202 }
203
204 var stringLen = [3]int{8, 16, 16}
205
206 func (s String) Bits(v Version) int {
207 return 4 + stringLen[v.sizeClass()] + 8*len(s)
208 }
209
210 func (s String) Encode(b *Bits, v Version) {
211 b.Write(4, 4)
212 b.Write(uint(len(s)), stringLen[v.sizeClass()])
213 for i := 0; i < len(s); i++ {
214 b.Write(uint(s[i]), 8)
215 }
216 }
217
218 // A Pixel describes a single pixel in a QR code.
219 type Pixel uint32
220
221 const (
222 Black Pixel = 1 << iota
223 Invert
224 )
225
226 func (p Pixel) Offset() uint {
227 return uint(p >> 6)
228 }
229
230 func OffsetPixel(o uint) Pixel {
231 return Pixel(o << 6)
232 }
233
234 func (r PixelRole) Pixel() Pixel {
235 return Pixel(r << 2)
236 }
237
238 func (p Pixel) Role() PixelRole {
239 return PixelRole(p>>2) & 15
240 }
241
242 func (p Pixel) String() string {
243 s := p.Role().String()
244 if p&Black != 0 {
245 s += "+black"
246 }
247 if p&Invert != 0 {
248 s += "+invert"
249 }
250 s += "+" + strconv.FormatUint(uint64(p.Offset()), 10)
251 return s
252 }
253
254 // A PixelRole describes the role of a QR pixel.
255 type PixelRole uint32
256
257 const (
258 _ PixelRole = iota
259 Position // position squares (large)
260 Alignment // alignment squares (small)
261 Timing // timing strip between position squares
262 Format // format metadata
263 PVersion // version pattern
264 Unused // unused pixel
265 Data // data bit
266 Check // error correction check bit
267 Extra
268 )
269
270 var roles = []string{
271 "",
272 "position",
273 "alignment",
274 "timing",
275 "format",
276 "pversion",
277 "unused",
278 "data",
279 "check",
280 "extra",
281 }
282
283 func (r PixelRole) String() string {
284 if Position <= r && r <= Check {
285 return roles[r]
286 }
287 return strconv.Itoa(int(r))
288 }
289
290 // A Level represents a QR error correction level.
291 // From least to most tolerant of errors, they are L, M, Q, H.
292 type Level int
293
294 const (
295 L Level = iota
296 M
297 Q
298 H
299 )
300
301 func (l Level) String() string {
302 if L <= l && l <= H {
303 return "LMQH"[l : l+1]
304 }
305 return strconv.Itoa(int(l))
306 }
307
308 // A Code is a square pixel grid.
309 type Code struct {
310 Bitmap []byte // 1 is black, 0 is white
311 Size int // number of pixels on a side
312 Stride int // number of bytes per row
313 }
314
315 func (c *Code) Black(x, y int) bool {
316 return 0 <= x && x < c.Size && 0 <= y && y < c.Size &&
317 c.Bitmap[y*c.Stride+x/8]&(1<<uint(7-x&7)) != 0
318 }
319
320 // A Mask describes a mask that is applied to the QR
321 // code to avoid QR artifacts being interpreted as
322 // alignment and timing patterns (such as the squares
323 // in the corners). Valid masks are integers from 0 to 7.
324 type Mask int
325
326 // http://www.swetake.com/qr/qr5_en.html
327 var mfunc = []func(int, int) bool{
328 func(i, j int) bool { return (i+j)%2 == 0 },
329 func(i, j int) bool { return i%2 == 0 },
330 func(i, j int) bool { return j%3 == 0 },
331 func(i, j int) bool { return (i+j)%3 == 0 },
332 func(i, j int) bool { return (i/2+j/3)%2 == 0 },
333 func(i, j int) bool { return i*j%2+i*j%3 == 0 },
334 func(i, j int) bool { return (i*j%2+i*j%3)%2 == 0 },
335 func(i, j int) bool { return (i*j%3+(i+j)%2)%2 == 0 },
336 }
337
338 func (m Mask) Invert(y, x int) bool {
339 if m < 0 {
340 return false
341 }
342 return mfunc[m](y, x)
343 }
344
345 // A Plan describes how to construct a QR code
346 // with a specific version, level, and mask.
347 type Plan struct {
348 Version Version
349 Level Level
350 Mask Mask
351
352 DataBytes int // number of data bytes
353 CheckBytes int // number of error correcting (checksum) bytes
354 Blocks int // number of data blocks
355
356 Pixel [][]Pixel // pixel map
357 }
358
359 // NewPlan returns a Plan for a QR code with the given
360 // version, level, and mask.
361 func NewPlan(version Version, level Level, mask Mask) (*Plan, error) {
362 p, err := vplan(version)
363 if err != nil {
364 return nil, err
365 }
366 if err := fplan(level, mask, p); err != nil {
367 return nil, err
368 }
369 if err := lplan(version, level, p); err != nil {
370 return nil, err
371 }
372 if err := mplan(mask, p); err != nil {
373 return nil, err
374 }
375 return p, nil
376 }
377
378 func (b *Bits) Pad(n int) {
379 if n < 0 {
380 panic("qr: invalid pad size")
381 }
382 if n <= 4 {
383 b.Write(0, n)
384 } else {
385 b.Write(0, 4)
386 n -= 4
387 n -= -b.Bits() & 7
388 b.Write(0, -b.Bits()&7)
389 pad := n / 8
390 for i := 0; i < pad; i += 2 {
391 b.Write(0xec, 8)
392 if i+1 >= pad {
393 break
394 }
395 b.Write(0x11, 8)
396 }
397 }
398 }
399
400 func (b *Bits) AddCheckBytes(v Version, l Level) {
401 nd := v.DataBytes(l)
402 if b.nbit < nd*8 {
403 b.Pad(nd*8 - b.nbit)
404 }
405 if b.nbit != nd*8 {
406 panic("qr: too much data")
407 }
408
409 dat := b.Bytes()
410 vt := &vtab[v]
411 lev := &vt.level[l]
412 db := nd / lev.nblock
413 extra := nd % lev.nblock
414 chk := make([]byte, lev.check)
415 rs := gf256.NewRSEncoder(Field, lev.check)
416 for i := 0; i < lev.nblock; i++ {
417 if i == lev.nblock-extra {
418 db++
419 }
420 rs.ECC(dat[:db], chk)
421 b.Append(chk)
422 dat = dat[db:]
423 }
424
425 if len(b.Bytes()) != vt.bytes {
426 panic("qr: internal error")
427 }
428 }
429
430 func (p *Plan) Encode(text ...Encoding) (*Code, error) {
431 var b Bits
432 for _, t := range text {
433 if err := t.Check(); err != nil {
434 return nil, err
435 }
436 t.Encode(&b, p.Version)
437 }
438 if b.Bits() > p.DataBytes*8 {
439 return nil, fmt.Errorf("cannot encode %d bits into %d-bit code", b.Bits(), p.DataBytes*8)
440 }
441 b.AddCheckBytes(p.Version, p.Level)
442 bytes := b.Bytes()
443
444 // Now we have the checksum bytes and the data bytes.
445 // Construct the actual code.
446 c := &Code{Size: len(p.Pixel), Stride: (len(p.Pixel) + 7) &^ 7}
447 c.Bitmap = make([]byte, c.Stride*c.Size)
448 crow := c.Bitmap
449 for _, row := range p.Pixel {
450 for x, pix := range row {
451 switch pix.Role() {
452 case Data, Check:
453 o := pix.Offset()
454 if bytes[o/8]&(1<<uint(7-o&7)) != 0 {
455 pix ^= Black
456 }
457 }
458 if pix&Black != 0 {
459 crow[x/8] |= 1 << uint(7-x&7)
460 }
461 }
462 crow = crow[c.Stride:]
463 }
464 return c, nil
465 }
466
467 // A version describes metadata associated with a version.
468 type version struct {
469 apos int
470 astride int
471 bytes int
472 pattern int
473 level [4]level
474 }
475
476 type level struct {
477 nblock int
478 check int
479 }
480
481 var vtab = []version{
482 {},
483 {100, 100, 26, 0x0, [4]level{{1, 7}, {1, 10}, {1, 13}, {1, 17}}}, // 1
484 {16, 100, 44, 0x0, [4]level{{1, 10}, {1, 16}, {1, 22}, {1, 28}}}, // 2
485 {20, 100, 70, 0x0, [4]level{{1, 15}, {1, 26}, {2, 18}, {2, 22}}}, // 3
486 {24, 100, 100, 0x0, [4]level{{1, 20}, {2, 18}, {2, 26}, {4, 16}}}, // 4
487 {28, 100, 134, 0x0, [4]level{{1, 26}, {2, 24}, {4, 18}, {4, 22}}}, // 5
488 {32, 100, 172, 0x0, [4]level{{2, 18}, {4, 16}, {4, 24}, {4, 28}}}, // 6
489 {20, 16, 196, 0x7c94, [4]level{{2, 20}, {4, 18}, {6, 18}, {5, 26}}}, // 7
490 {22, 18, 242, 0x85bc, [4]level{{2, 24}, {4, 22}, {6, 22}, {6, 26}}}, // 8
491 {24, 20, 292, 0x9a99, [4]level{{2, 30}, {5, 22}, {8, 20}, {8, 24}}}, // 9
492 {26, 22, 346, 0xa4d3, [4]level{{4, 18}, {5, 26}, {8, 24}, {8, 28}}}, // 10
493 {28, 24, 404, 0xbbf6, [4]level{{4, 20}, {5, 30}, {8, 28}, {11, 24}}}, // 11
494 {30, 26, 466, 0xc762, [4]level{{4, 24}, {8, 22}, {10, 26}, {11, 28}}}, // 12
495 {32, 28, 532, 0xd847, [4]level{{4, 26}, {9, 22}, {12, 24}, {16, 22}}}, // 13
496 {24, 20, 581, 0xe60d, [4]level{{4, 30}, {9, 24}, {16, 20}, {16, 24}}}, // 14
497 {24, 22, 655, 0xf928, [4]level{{6, 22}, {10, 24}, {12, 30}, {18, 24}}}, // 15
498 {24, 24, 733, 0x10b78, [4]level{{6, 24}, {10, 28}, {17, 24}, {16, 30}}}, // 16
499 {28, 24, 815, 0x1145d, [4]level{{6, 28}, {11, 28}, {16, 28}, {19, 28}}}, // 17
500 {28, 26, 901, 0x12a17, [4]level{{6, 30}, {13, 26}, {18, 28}, {21, 28}}}, // 18
501 {28, 28, 991, 0x13532, [4]level{{7, 28}, {14, 26}, {21, 26}, {25, 26}}}, // 19
502 {32, 28, 1085, 0x149a6, [4]level{{8, 28}, {16, 26}, {20, 30}, {25, 28}}}, // 20
503 {26, 22, 1156, 0x15683, [4]level{{8, 28}, {17, 26}, {23, 28}, {25, 30}}}, // 21
504 {24, 24, 1258, 0x168c9, [4]level{{9, 28}, {17, 28}, {23, 30}, {34, 24}}}, // 22
505 {28, 24, 1364, 0x177ec, [4]level{{9, 30}, {18, 28}, {25, 30}, {30, 30}}}, // 23
506 {26, 26, 1474, 0x18ec4, [4]level{{10, 30}, {20, 28}, {27, 30}, {32, 30}}}, // 24
507 {30, 26, 1588, 0x191e1, [4]level{{12, 26}, {21, 28}, {29, 30}, {35, 30}}}, // 25
508 {28, 28, 1706, 0x1afab, [4]level{{12, 28}, {23, 28}, {34, 28}, {37, 30}}}, // 26
509 {32, 28, 1828, 0x1b08e, [4]level{{12, 30}, {25, 28}, {34, 30}, {40, 30}}}, // 27
510 {24, 24, 1921, 0x1cc1a, [4]level{{13, 30}, {26, 28}, {35, 30}, {42, 30}}}, // 28
511 {28, 24, 2051, 0x1d33f, [4]level{{14, 30}, {28, 28}, {38, 30}, {45, 30}}}, // 29
512 {24, 26, 2185, 0x1ed75, [4]level{{15, 30}, {29, 28}, {40, 30}, {48, 30}}}, // 30
513 {28, 26, 2323, 0x1f250, [4]level{{16, 30}, {31, 28}, {43, 30}, {51, 30}}}, // 31
514 {32, 26, 2465, 0x209d5, [4]level{{17, 30}, {33, 28}, {45, 30}, {54, 30}}}, // 32
515 {28, 28, 2611, 0x216f0, [4]level{{18, 30}, {35, 28}, {48, 30}, {57, 30}}}, // 33
516 {32, 28, 2761, 0x228ba, [4]level{{19, 30}, {37, 28}, {51, 30}, {60, 30}}}, // 34
517 {28, 24, 2876, 0x2379f, [4]level{{19, 30}, {38, 28}, {53, 30}, {63, 30}}}, // 35
518 {22, 26, 3034, 0x24b0b, [4]level{{20, 30}, {40, 28}, {56, 30}, {66, 30}}}, // 36
519 {26, 26, 3196, 0x2542e, [4]level{{21, 30}, {43, 28}, {59, 30}, {70, 30}}}, // 37
520 {30, 26, 3362, 0x26a64, [4]level{{22, 30}, {45, 28}, {62, 30}, {74, 30}}}, // 38
521 {24, 28, 3532, 0x27541, [4]level{{24, 30}, {47, 28}, {65, 30}, {77, 30}}}, // 39
522 {28, 28, 3706, 0x28c69, [4]level{{25, 30}, {49, 28}, {68, 30}, {81, 30}}}, // 40
523 }
524
525 func grid(siz int) [][]Pixel {
526 m := make([][]Pixel, siz)
527 pix := make([]Pixel, siz*siz)
528 for i := range m {
529 m[i], pix = pix[:siz], pix[siz:]
530 }
531 return m
532 }
533
534 // vplan creates a Plan for the given version.
535 func vplan(v Version) (*Plan, error) {
536 p := &Plan{Version: v}
537 if v < 1 || v > 40 {
538 return nil, fmt.Errorf("invalid QR version %d", int(v))
539 }
540 siz := 17 + int(v)*4
541 m := grid(siz)
542 p.Pixel = m
543
544 // Timing markers (overwritten by boxes).
545 const ti = 6 // timing is in row/column 6 (counting from 0)
546 for i := range m {
547 p := Timing.Pixel()
548 if i&1 == 0 {
549 p |= Black
550 }
551 m[i][ti] = p
552 m[ti][i] = p
553 }
554
555 // Position boxes.
556 posBox(m, 0, 0)
557 posBox(m, siz-7, 0)
558 posBox(m, 0, siz-7)
559
560 // Alignment boxes.
561 info := &vtab[v]
562 for x := 4; x+5 < siz; {
563 for y := 4; y+5 < siz; {
564 // don't overwrite timing markers
565 if (x < 7 && y < 7) || (x < 7 && y+5 >= siz-7) || (x+5 >= siz-7 && y < 7) {
566 } else {
567 alignBox(m, x, y)
568 }
569 if y == 4 {
570 y = info.apos
571 } else {
572 y += info.astride
573 }
574 }
575 if x == 4 {
576 x = info.apos
577 } else {
578 x += info.astride
579 }
580 }
581
582 // Version pattern.
583 pat := vtab[v].pattern
584 if pat != 0 {
585 v := pat
586 for x := 0; x < 6; x++ {
587 for y := 0; y < 3; y++ {
588 p := PVersion.Pixel()
589 if v&1 != 0 {
590 p |= Black
591 }
592 m[siz-11+y][x] = p
593 m[x][siz-11+y] = p
594 v >>= 1
595 }
596 }
597 }
598
599 // One lonely black pixel
600 m[siz-8][8] = Unused.Pixel() | Black
601
602 return p, nil
603 }
604
605 // fplan adds the format pixels
606 func fplan(l Level, m Mask, p *Plan) error {
607 // Format pixels.
608 fb := uint32(l^1) << 13 // level: L=01, M=00, Q=11, H=10
609 fb |= uint32(m) << 10 // mask
610 const formatPoly = 0x537
611 rem := fb
612 for i := 14; i >= 10; i-- {
613 if rem&(1<<uint(i)) != 0 {
614 rem ^= formatPoly << uint(i-10)
615 }
616 }
617 fb |= rem
618 invert := uint32(0x5412)
619 siz := len(p.Pixel)
620 for i := uint(0); i < 15; i++ {
621 pix := Format.Pixel() + OffsetPixel(i)
622 if (fb>>i)&1 == 1 {
623 pix |= Black
624 }
625 if (invert>>i)&1 == 1 {
626 pix ^= Invert | Black
627 }
628 // top left
629 switch {
630 case i < 6:
631 p.Pixel[i][8] = pix
632 case i < 8:
633 p.Pixel[i+1][8] = pix
634 case i < 9:
635 p.Pixel[8][7] = pix
636 default:
637 p.Pixel[8][14-i] = pix
638 }
639 // bottom right
640 switch {
641 case i < 8:
642 p.Pixel[8][siz-1-int(i)] = pix
643 default:
644 p.Pixel[siz-1-int(14-i)][8] = pix
645 }
646 }
647 return nil
648 }
649
650 // lplan edits a version-only Plan to add information
651 // about the error correction levels.
652 func lplan(v Version, l Level, p *Plan) error {
653 p.Level = l
654
655 nblock := vtab[v].level[l].nblock
656 ne := vtab[v].level[l].check
657 nde := (vtab[v].bytes - ne*nblock) / nblock
658 extra := (vtab[v].bytes - ne*nblock) % nblock
659 dataBits := (nde*nblock + extra) * 8
660 checkBits := ne * nblock * 8
661
662 p.DataBytes = vtab[v].bytes - ne*nblock
663 p.CheckBytes = ne * nblock
664 p.Blocks = nblock
665
666 // Make data + checksum pixels.
667 data := make([]Pixel, dataBits)
668 for i := range data {
669 data[i] = Data.Pixel() | OffsetPixel(uint(i))
670 }
671 check := make([]Pixel, checkBits)
672 for i := range check {
673 check[i] = Check.Pixel() | OffsetPixel(uint(i+dataBits))
674 }
675
676 // Split into blocks.
677 dataList := make([][]Pixel, nblock)
678 checkList := make([][]Pixel, nblock)
679 for i := 0; i < nblock; i++ {
680 // The last few blocks have an extra data byte (8 pixels).
681 nd := nde
682 if i >= nblock-extra {
683 nd++
684 }
685 dataList[i], data = data[0:nd*8], data[nd*8:]
686 checkList[i], check = check[0:ne*8], check[ne*8:]
687 }
688 if len(data) != 0 || len(check) != 0 {
689 panic("data/check math")
690 }
691
692 // Build up bit sequence, taking first byte of each block,
693 // then second byte, and so on. Then checksums.
694 bits := make([]Pixel, dataBits+checkBits)
695 dst := bits
696 for i := 0; i < nde+1; i++ {
697 for _, b := range dataList {
698 if i*8 < len(b) {
699 copy(dst, b[i*8:(i+1)*8])
700 dst = dst[8:]
701 }
702 }
703 }
704 for i := 0; i < ne; i++ {
705 for _, b := range checkList {
706 if i*8 < len(b) {
707 copy(dst, b[i*8:(i+1)*8])
708 dst = dst[8:]
709 }
710 }
711 }
712 if len(dst) != 0 {
713 panic("dst math")
714 }
715
716 // Sweep up pair of columns,
717 // then down, assigning to right then left pixel.
718 // Repeat.
719 // See Figure 2 of http://www.pclviewer.com/rs2/qrtopology.htm
720 siz := len(p.Pixel)
721 rem := make([]Pixel, 7)
722 for i := range rem {
723 rem[i] = Extra.Pixel()
724 }
725 src := append(bits, rem...)
726 for x := siz; x > 0; {
727 for y := siz - 1; y >= 0; y-- {
728 if p.Pixel[y][x-1].Role() == 0 {
729 p.Pixel[y][x-1], src = src[0], src[1:]
730 }
731 if p.Pixel[y][x-2].Role() == 0 {
732 p.Pixel[y][x-2], src = src[0], src[1:]
733 }
734 }
735 x -= 2
736 if x == 7 { // vertical timing strip
737 x--
738 }
739 for y := 0; y < siz; y++ {
740 if p.Pixel[y][x-1].Role() == 0 {
741 p.Pixel[y][x-1], src = src[0], src[1:]
742 }
743 if p.Pixel[y][x-2].Role() == 0 {
744 p.Pixel[y][x-2], src = src[0], src[1:]
745 }
746 }
747 x -= 2
748 }
749 return nil
750 }
751
752 // mplan edits a version+level-only Plan to add the mask.
753 func mplan(m Mask, p *Plan) error {
754 p.Mask = m
755 for y, row := range p.Pixel {
756 for x, pix := range row {
757 if r := pix.Role(); (r == Data || r == Check || r == Extra) && p.Mask.Invert(y, x) {
758 row[x] ^= Black | Invert
759 }
760 }
761 }
762 return nil
763 }
764
765 // posBox draws a position (large) box at upper left x, y.
766 func posBox(m [][]Pixel, x, y int) {
767 pos := Position.Pixel()
768 // box
769 for dy := 0; dy < 7; dy++ {
770 for dx := 0; dx < 7; dx++ {
771 p := pos
772 if dx == 0 || dx == 6 || dy == 0 || dy == 6 || 2 <= dx && dx <= 4 && 2 <= dy && dy <= 4 {
773 p |= Black
774 }
775 m[y+dy][x+dx] = p
776 }
777 }
778 // white border
779 for dy := -1; dy < 8; dy++ {
780 if 0 <= y+dy && y+dy < len(m) {
781 if x > 0 {
782 m[y+dy][x-1] = pos
783 }
784 if x+7 < len(m) {
785 m[y+dy][x+7] = pos
786 }
787 }
788 }
789 for dx := -1; dx < 8; dx++ {
790 if 0 <= x+dx && x+dx < len(m) {
791 if y > 0 {
792 m[y-1][x+dx] = pos
793 }
794 if y+7 < len(m) {
795 m[y+7][x+dx] = pos
796 }
797 }
798 }
799 }
800
801 // alignBox draw an alignment (small) box at upper left x, y.
802 func alignBox(m [][]Pixel, x, y int) {
803 // box
804 align := Alignment.Pixel()
805 for dy := 0; dy < 5; dy++ {
806 for dx := 0; dx < 5; dx++ {
807 p := align
808 if dx == 0 || dx == 4 || dy == 0 || dy == 4 || dx == 2 && dy == 2 {
809 p |= Black
810 }
811 m[y+dy][x+dx] = p
812 }
813 }
814 }
+133
-0
coding/qr_test.go less more
0 // Copyright 2011 The Go Authors. All rights reserved.
1 // Use of this source code is governed by a BSD-style
2 // license that can be found in the LICENSE file.
3
4 package coding
5
6 import (
7 "bytes"
8 "testing"
9
10 "rsc.io/qr/gf256"
11 "rsc.io/qr/libqrencode"
12 )
13
14 func test(t *testing.T, v Version, l Level, text ...Encoding) bool {
15 s := ""
16 ty := libqrencode.EightBit
17 switch x := text[0].(type) {
18 case String:
19 s = string(x)
20 case Alpha:
21 s = string(x)
22 ty = libqrencode.Alphanumeric
23 case Num:
24 s = string(x)
25 ty = libqrencode.Numeric
26 }
27 key, err := libqrencode.Encode(libqrencode.Version(v), libqrencode.Level(l), ty, s)
28 if err != nil {
29 t.Errorf("libqrencode.Encode(%v, %v, %d, %#q): %v", v, l, ty, s, err)
30 return false
31 }
32 mask := (^key.Pixel[8][2]&1)<<2 | (key.Pixel[8][3]&1)<<1 | (^key.Pixel[8][4] & 1)
33 p, err := NewPlan(v, l, Mask(mask))
34 if err != nil {
35 t.Errorf("NewPlan(%v, L, %d): %v", v, err, mask)
36 return false
37 }
38 if len(p.Pixel) != len(key.Pixel) {
39 t.Errorf("%v: NewPlan uses %dx%d, libqrencode uses %dx%d", v, len(p.Pixel), len(p.Pixel), len(key.Pixel), len(key.Pixel))
40 return false
41 }
42 c, err := p.Encode(text...)
43 if err != nil {
44 t.Errorf("Encode: %v", err)
45 return false
46 }
47 badpix := 0
48 Pixel:
49 for y, prow := range p.Pixel {
50 for x, pix := range prow {
51 pix &^= Black
52 if c.Black(x, y) {
53 pix |= Black
54 }
55
56 keypix := key.Pixel[y][x]
57 want := Pixel(0)
58 switch {
59 case keypix&libqrencode.Finder != 0:
60 want = Position.Pixel()
61 case keypix&libqrencode.Alignment != 0:
62 want = Alignment.Pixel()
63 case keypix&libqrencode.Timing != 0:
64 want = Timing.Pixel()
65 case keypix&libqrencode.Format != 0:
66 want = Format.Pixel()
67 want |= OffsetPixel(pix.Offset()) // sic
68 want |= pix & Invert
69 case keypix&libqrencode.PVersion != 0:
70 want = PVersion.Pixel()
71 case keypix&libqrencode.DataECC != 0:
72 if pix.Role() == Check || pix.Role() == Extra {
73 want = pix.Role().Pixel()
74 } else {
75 want = Data.Pixel()
76 }
77 want |= OffsetPixel(pix.Offset())
78 want |= pix & Invert
79 default:
80 want = Unused.Pixel()
81 }
82 if keypix&libqrencode.Black != 0 {
83 want |= Black
84 }
85 if pix != want {
86 t.Errorf("%v/%v: Pixel[%d][%d] = %v, want %v %#x", v, mask, y, x, pix, want, keypix)
87 if badpix++; badpix >= 100 {
88 t.Errorf("stopping after %d bad pixels", badpix)
89 break Pixel
90 }
91 }
92 }
93 }
94 return badpix == 0
95 }
96
97 var input = []Encoding{
98 String("hello"),
99 Num("1"),
100 Num("12"),
101 Num("123"),
102 Alpha("AB"),
103 Alpha("ABC"),
104 }
105
106 func TestVersion(t *testing.T) {
107 badvers := 0
108 Version:
109 for v := Version(1); v <= 40; v++ {
110 for l := L; l <= H; l++ {
111 for _, in := range input {
112 if !test(t, v, l, in) {
113 if badvers++; badvers >= 10 {
114 t.Errorf("stopping after %d bad versions", badvers)
115 break Version
116 }
117 }
118 }
119 }
120 }
121 }
122
123 func TestEncode(t *testing.T) {
124 data := []byte{0x10, 0x20, 0x0c, 0x56, 0x61, 0x80, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11}
125 check := []byte{0xa5, 0x24, 0xd4, 0xc1, 0xed, 0x36, 0xc7, 0x87, 0x2c, 0x55}
126 rs := gf256.NewRSEncoder(Field, len(check))
127 out := make([]byte, len(check))
128 rs.ECC(data, out)
129 if !bytes.Equal(out, check) {
130 t.Errorf("have %x want %x", out, check)
131 }
132 }
+85
-0
gf256/blog_test.go less more
0 // Copyright 2012 The Go Authors. All rights reserved.
1 // Use of this source code is governed by a BSD-style
2 // license that can be found in the LICENSE file.
3
4 // This file contains a straightforward implementation of
5 // Reed-Solomon encoding, along with a benchmark.
6 // It goes with http://research.swtch.com/field.
7 //
8 // For an optimized implementation, see gf256.go.
9
10 package gf256
11
12 import (
13 "bytes"
14 "fmt"
15 "testing"
16 )
17
18 // BlogECC writes to check the error correcting code bytes
19 // for data using the given Reed-Solomon parameters.
20 func BlogECC(rs *RSEncoder, m []byte, check []byte) {
21 if len(check) < rs.c {
22 panic("gf256: invalid check byte length")
23 }
24 if rs.c == 0 {
25 return
26 }
27
28 // The check bytes are the remainder after dividing
29 // data padded with c zeros by the generator polynomial.
30
31 // p = data padded with c zeros.
32 var p []byte
33 n := len(m) + rs.c
34 if len(rs.p) >= n {
35 p = rs.p
36 } else {
37 p = make([]byte, n)
38 }
39 copy(p, m)
40 for i := len(m); i < len(p); i++ {
41 p[i] = 0
42 }
43
44 gen := rs.gen
45
46 // Divide p by gen, leaving the remainder in p[len(data):].
47 // p[0] is the most significant term in p, and
48 // gen[0] is the most significant term in the generator.
49 for i := 0; i < len(m); i++ {
50 k := f.Mul(p[i], f.Inv(gen[0])) // k = pi / g0
51 // p -= k·g
52 for j, g := range gen {
53 p[i+j] = f.Add(p[i+j], f.Mul(k, g))
54 }
55 }
56
57 copy(check, p[len(m):])
58 rs.p = p
59 }
60
61 func BenchmarkBlogECC(b *testing.B) {
62 data := []byte{0x10, 0x20, 0x0c, 0x56, 0x61, 0x80, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11, 0x10, 0x20, 0x0c, 0x56, 0x61, 0x80, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11}
63 check := []byte{0x29, 0x41, 0xb3, 0x93, 0x8, 0xe8, 0xa3, 0xe7, 0x63, 0x8f}
64 out := make([]byte, len(check))
65 rs := NewRSEncoder(f, len(check))
66 for i := 0; i < b.N; i++ {
67 BlogECC(rs, data, out)
68 }
69 b.SetBytes(int64(len(data)))
70 if !bytes.Equal(out, check) {
71 fmt.Printf("have %#v want %#v\n", out, check)
72 }
73 }
74
75 func TestBlogECC(t *testing.T) {
76 data := []byte{0x10, 0x20, 0x0c, 0x56, 0x61, 0x80, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11}
77 check := []byte{0xa5, 0x24, 0xd4, 0xc1, 0xed, 0x36, 0xc7, 0x87, 0x2c, 0x55}
78 out := make([]byte, len(check))
79 rs := NewRSEncoder(f, len(check))
80 BlogECC(rs, data, out)
81 if !bytes.Equal(out, check) {
82 t.Errorf("have %x want %x", out, check)
83 }
84 }
+241
-0
gf256/gf256.go less more
0 // Copyright 2010 The Go Authors. All rights reserved.
1 // Use of this source code is governed by a BSD-style
2 // license that can be found in the LICENSE file.
3
4 // Package gf256 implements arithmetic over the Galois Field GF(256).
5 package gf256
6
7 import "strconv"
8
9 // A Field represents an instance of GF(256) defined by a specific polynomial.
10 type Field struct {
11 log [256]byte // log[0] is unused
12 exp [510]byte
13 }
14
15 // NewField returns a new field corresponding to the polynomial poly
16 // and generator α. The Reed-Solomon encoding in QR codes uses
17 // polynomial 0x11d with generator 2.
18 //
19 // The choice of generator α only affects the Exp and Log operations.
20 func NewField(poly, α int) *Field {
21 if poly < 0x100 || poly >= 0x200 || reducible(poly) {
22 panic("gf256: invalid polynomial: " + strconv.Itoa(poly))
23 }
24
25 var f Field
26 x := 1
27 for i := 0; i < 255; i++ {
28 if x == 1 && i != 0 {
29 panic("gf256: invalid generator " + strconv.Itoa(α) +
30 " for polynomial " + strconv.Itoa(poly))
31 }
32 f.exp[i] = byte(x)
33 f.exp[i+255] = byte(x)
34 f.log[x] = byte(i)
35 x = mul(x, α, poly)
36 }
37 f.log[0] = 255
38 for i := 0; i < 255; i++ {
39 if f.log[f.exp[i]] != byte(i) {
40 panic("bad log")
41 }
42 if f.log[f.exp[i+255]] != byte(i) {
43 panic("bad log")
44 }
45 }
46 for i := 1; i < 256; i++ {
47 if f.exp[f.log[i]] != byte(i) {
48 panic("bad log")
49 }
50 }
51
52 return &f
53 }
54
55 // nbit returns the number of significant in p.
56 func nbit(p int) uint {
57 n := uint(0)
58 for ; p > 0; p >>= 1 {
59 n++
60 }
61 return n
62 }
63
64 // polyDiv divides the polynomial p by q and returns the remainder.
65 func polyDiv(p, q int) int {
66 np := nbit(p)
67 nq := nbit(q)
68 for ; np >= nq; np-- {
69 if p&(1<<(np-1)) != 0 {
70 p ^= q << (np - nq)
71 }
72 }
73 return p
74 }
75
76 // mul returns the product x*y mod poly, a GF(256) multiplication.
77 func mul(x, y, poly int) int {
78 z := 0
79 for x > 0 {
80 if x&1 != 0 {
81 z ^= y
82 }
83 x >>= 1
84 y <<= 1
85 if y&0x100 != 0 {
86 y ^= poly
87 }
88 }
89 return z
90 }
91
92 // reducible reports whether p is reducible.
93 func reducible(p int) bool {
94 // Multiplying n-bit * n-bit produces (2n-1)-bit,
95 // so if p is reducible, one of its factors must be
96 // of np/2+1 bits or fewer.
97 np := nbit(p)
98 for q := 2; q < 1<<(np/2+1); q++ {
99 if polyDiv(p, q) == 0 {
100 return true
101 }
102 }
103 return false
104 }
105
106 // Add returns the sum of x and y in the field.
107 func (f *Field) Add(x, y byte) byte {
108 return x ^ y
109 }
110
111 // Exp returns the base-α exponential of e in the field.
112 // If e < 0, Exp returns 0.
113 func (f *Field) Exp(e int) byte {
114 if e < 0 {
115 return 0
116 }
117 return f.exp[e%255]
118 }
119
120 // Log returns the base-α logarithm of x in the field.
121 // If x == 0, Log returns -1.
122 func (f *Field) Log(x byte) int {
123 if x == 0 {
124 return -1
125 }
126 return int(f.log[x])
127 }
128
129 // Inv returns the multiplicative inverse of x in the field.
130 // If x == 0, Inv returns 0.
131 func (f *Field) Inv(x byte) byte {
132 if x == 0 {
133 return 0
134 }
135 return f.exp[255-f.log[x]]
136 }
137
138 // Mul returns the product of x and y in the field.
139 func (f *Field) Mul(x, y byte) byte {
140 if x == 0 || y == 0 {
141 return 0
142 }
143 return f.exp[int(f.log[x])+int(f.log[y])]
144 }
145
146 // An RSEncoder implements Reed-Solomon encoding
147 // over a given field using a given number of error correction bytes.
148 type RSEncoder struct {
149 f *Field
150 c int
151 gen []byte
152 lgen []byte
153 p []byte
154 }
155
156 func (f *Field) gen(e int) (gen, lgen []byte) {
157 // p = 1
158 p := make([]byte, e+1)
159 p[e] = 1
160
161 for i := 0; i < e; i++ {
162 // p *= (x + Exp(i))
163 // p[j] = p[j]*Exp(i) + p[j+1].
164 c := f.Exp(i)
165 for j := 0; j < e; j++ {
166 p[j] = f.Mul(p[j], c) ^ p[j+1]
167 }
168 p[e] = f.Mul(p[e], c)
169 }
170
171 // lp = log p.
172 lp := make([]byte, e+1)
173 for i, c := range p {
174 if c == 0 {
175 lp[i] = 255
176 } else {
177 lp[i] = byte(f.Log(c))
178 }
179 }
180
181 return p, lp
182 }
183
184 // NewRSEncoder returns a new Reed-Solomon encoder
185 // over the given field and number of error correction bytes.
186 func NewRSEncoder(f *Field, c int) *RSEncoder {
187 gen, lgen := f.gen(c)
188 return &RSEncoder{f: f, c: c, gen: gen, lgen: lgen}
189 }
190
191 // ECC writes to check the error correcting code bytes
192 // for data using the given Reed-Solomon parameters.
193 func (rs *RSEncoder) ECC(data []byte, check []byte) {
194 if len(check) < rs.c {
195 panic("gf256: invalid check byte length")
196 }
197 if rs.c == 0 {
198 return
199 }
200
201 // The check bytes are the remainder after dividing
202 // data padded with c zeros by the generator polynomial.
203
204 // p = data padded with c zeros.
205 var p []byte
206 n := len(data) + rs.c
207 if len(rs.p) >= n {
208 p = rs.p
209 } else {
210 p = make([]byte, n)
211 }
212 copy(p, data)
213 for i := len(data); i < len(p); i++ {
214 p[i] = 0
215 }
216
217 // Divide p by gen, leaving the remainder in p[len(data):].
218 // p[0] is the most significant term in p, and
219 // gen[0] is the most significant term in the generator,
220 // which is always 1.
221 // To avoid repeated work, we store various values as
222 // lv, not v, where lv = log[v].
223 f := rs.f
224 lgen := rs.lgen[1:]
225 for i := 0; i < len(data); i++ {
226 c := p[i]
227 if c == 0 {
228 continue
229 }
230 q := p[i+1:]
231 exp := f.exp[f.log[c]:]
232 for j, lg := range lgen {
233 if lg != 255 { // lgen uses 255 for log 0
234 q[j] ^= exp[lg]
235 }
236 }
237 }
238 copy(check, p[len(data):])
239 rs.p = p
240 }
+194
-0
gf256/gf256_test.go less more
0 // Copyright 2010 The Go Authors. All rights reserved.
1 // Use of this source code is governed by a BSD-style
2 // license that can be found in the LICENSE file.
3
4 package gf256
5
6 import (
7 "bytes"
8 "fmt"
9 "testing"
10 )
11
12 var f = NewField(0x11d, 2) // x^8 + x^4 + x^3 + x^2 + 1
13
14 func TestBasic(t *testing.T) {
15 if f.Exp(0) != 1 || f.Exp(1) != 2 || f.Exp(255) != 1 {
16 panic("bad Exp")
17 }
18 }
19
20 func TestECC(t *testing.T) {
21 data := []byte{0x10, 0x20, 0x0c, 0x56, 0x61, 0x80, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11}
22 check := []byte{0xa5, 0x24, 0xd4, 0xc1, 0xed, 0x36, 0xc7, 0x87, 0x2c, 0x55}
23 out := make([]byte, len(check))
24 rs := NewRSEncoder(f, len(check))
25 rs.ECC(data, out)
26 if !bytes.Equal(out, check) {
27 t.Errorf("have %x want %x", out, check)
28 }
29 }
30
31 func TestLinear(t *testing.T) {
32 d1 := []byte{0x00, 0x00}
33 c1 := []byte{0x00, 0x00}
34 out := make([]byte, len(c1))
35 rs := NewRSEncoder(f, len(c1))
36 if rs.ECC(d1, out); !bytes.Equal(out, c1) {
37 t.Errorf("ECBytes(%x, %d) = %x, want 0", d1, len(c1), out)
38 }
39 d2 := []byte{0x00, 0x01}
40 c2 := make([]byte, 2)
41 rs.ECC(d2, c2)
42 d3 := []byte{0x00, 0x02}
43 c3 := make([]byte, 2)
44 rs.ECC(d3, c3)
45 cx := make([]byte, 2)
46 for i := range cx {
47 cx[i] = c2[i] ^ c3[i]
48 }
49 d4 := []byte{0x00, 0x03}
50 c4 := make([]byte, 2)
51 rs.ECC(d4, c4)
52 if !bytes.Equal(cx, c4) {
53 t.Errorf("ECBytes(%x, 2) = %x\nECBytes(%x, 2) = %x\nxor = %x\nECBytes(%x, 2) = %x",
54 d2, c2, d3, c3, cx, d4, c4)
55 }
56 }
57
58 func TestGaussJordan(t *testing.T) {
59 rs := NewRSEncoder(f, 2)
60 m := make([][]byte, 16)
61 for i := range m {
62 m[i] = make([]byte, 4)
63 m[i][i/8] = 1 << uint(i%8)
64 rs.ECC(m[i][:2], m[i][2:])
65 }
66 if false {
67 fmt.Printf("---\n")
68 for _, row := range m {
69 fmt.Printf("%x\n", row)
70 }
71 }
72 b := []uint{0, 1, 2, 3, 12, 13, 14, 15, 20, 21, 22, 23, 24, 25, 26, 27}
73 for i := 0; i < 16; i++ {
74 bi := b[i]
75 if m[i][bi/8]&(1<<(7-bi%8)) == 0 {
76 for j := i + 1; ; j++ {
77 if j >= len(m) {
78 t.Errorf("lost track for %d", bi)
79 break
80 }
81 if m[j][bi/8]&(1<<(7-bi%8)) != 0 {
82 m[i], m[j] = m[j], m[i]
83 break
84 }
85 }
86 }
87 for j := i + 1; j < len(m); j++ {
88 if m[j][bi/8]&(1<<(7-bi%8)) != 0 {
89 for k := range m[j] {
90 m[j][k] ^= m[i][k]
91 }
92 }
93 }
94 }
95 if false {
96 fmt.Printf("---\n")
97 for _, row := range m {
98 fmt.Printf("%x\n", row)
99 }
100 }
101 for i := 15; i >= 0; i-- {
102 bi := b[i]
103 for j := i - 1; j >= 0; j-- {
104 if m[j][bi/8]&(1<<(7-bi%8)) != 0 {
105 for k := range m[j] {
106 m[j][k] ^= m[i][k]
107 }
108 }
109 }
110 }
111 if false {
112 fmt.Printf("---\n")
113 for _, row := range m {
114 fmt.Printf("%x", row)
115 out := make([]byte, 2)
116 if rs.ECC(row[:2], out); !bytes.Equal(out, row[2:]) {
117 fmt.Printf(" - want %x", out)
118 }
119 fmt.Printf("\n")
120 }
121 }
122 }
123
124 func BenchmarkECC(b *testing.B) {
125 data := []byte{0x10, 0x20, 0x0c, 0x56, 0x61, 0x80, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11, 0x10, 0x20, 0x0c, 0x56, 0x61, 0x80, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11}
126 check := []byte{0x29, 0x41, 0xb3, 0x93, 0x8, 0xe8, 0xa3, 0xe7, 0x63, 0x8f}
127 out := make([]byte, len(check))
128 rs := NewRSEncoder(f, len(check))
129 for i := 0; i < b.N; i++ {
130 rs.ECC(data, out)
131 }
132 b.SetBytes(int64(len(data)))
133 if !bytes.Equal(out, check) {
134 fmt.Printf("have %#v want %#v\n", out, check)
135 }
136 }
137
138 func TestGen(t *testing.T) {
139 for i := 0; i < 256; i++ {
140 _, lg := f.gen(i)
141 if lg[0] != 0 {
142 t.Errorf("#%d: %x", i, lg)
143 }
144 }
145 }
146
147 func TestReducible(t *testing.T) {
148 var count = []int{1, 2, 3, 6, 9, 18, 30, 56, 99, 186} // oeis.org/A1037
149 for i, want := range count {
150 n := 0
151 for p := 1 << uint(i+2); p < 1<<uint(i+3); p++ {
152 if !reducible(p) {
153 n++
154 }
155 }
156 if n != want {
157 t.Errorf("#reducible(%d-bit) = %d, want %d", i+2, n, want)
158 }
159 }
160 }
161
162 func TestExhaustive(t *testing.T) {
163 for poly := 0x100; poly < 0x200; poly++ {
164 if reducible(poly) {
165 continue
166 }
167 α := 2
168 for !generates(α, poly) {
169 α++
170 }
171 f := NewField(poly, α)
172 for p := 0; p < 256; p++ {
173 for q := 0; q < 256; q++ {
174 fm := int(f.Mul(byte(p), byte(q)))
175 pm := mul(p, q, poly)
176 if fm != pm {
177 t.Errorf("NewField(%#x).Mul(%#x, %#x) = %#x, want %#x", poly, p, q, fm, pm)
178 }
179 }
180 }
181 }
182 }
183
184 func generates(α, poly int) bool {
185 x := α
186 for i := 0; i < 254; i++ {
187 if x == 1 {
188 return false
189 }
190 x = mul(x, α, poly)
191 }
192 return true
193 }
+149
-0
libqrencode/qrencode.go less more
0 // Copyright 2011 The Go Authors. All rights reserved.
1 // Use of this source code is governed by a BSD-style
2 // license that can be found in the LICENSE file.
3
4 // Package libqrencode wraps the C libqrencode library.
5 // The qr package (in this package's parent directory)
6 // does not use any C wrapping. This code is here only
7 // for use during that package's tests.
8 package libqrencode
9
10 /*
11 #cgo LDFLAGS: -lqrencode
12 #include <qrencode.h>
13 */
14 import "C"
15
16 import (
17 "fmt"
18 "image"
19 "image/color"
20 "unsafe"
21 )
22
23 type Version int
24
25 type Mode int
26
27 const (
28 Numeric Mode = C.QR_MODE_NUM
29 Alphanumeric Mode = C.QR_MODE_AN
30 EightBit Mode = C.QR_MODE_8
31 )
32
33 type Level int
34
35 const (
36 L Level = C.QR_ECLEVEL_L
37 M Level = C.QR_ECLEVEL_M
38 Q Level = C.QR_ECLEVEL_Q
39 H Level = C.QR_ECLEVEL_H
40 )
41
42 type Pixel int
43
44 const (
45 Black Pixel = 1 << iota
46 DataECC
47 Format
48 PVersion
49 Timing
50 Alignment
51 Finder
52 NonData
53 )
54
55 type Code struct {
56 Version int
57 Width int
58 Pixel [][]Pixel
59 Scale int
60 }
61
62 func (*Code) ColorModel() color.Model {
63 return color.RGBAModel
64 }
65
66 func (c *Code) Bounds() image.Rectangle {
67 d := (c.Width + 8) * c.Scale
68 return image.Rect(0, 0, d, d)
69 }
70
71 var (
72 white color.Color = color.RGBA{0xFF, 0xFF, 0xFF, 0xFF}
73 black color.Color = color.RGBA{0x00, 0x00, 0x00, 0xFF}
74 blue color.Color = color.RGBA{0x00, 0x00, 0x80, 0xFF}
75 red color.Color = color.RGBA{0xFF, 0x40, 0x40, 0xFF}
76 yellow color.Color = color.RGBA{0xFF, 0xFF, 0x00, 0xFF}
77 gray color.Color = color.RGBA{0x80, 0x80, 0x80, 0xFF}
78 green color.Color = color.RGBA{0x22, 0x8B, 0x22, 0xFF}
79 )
80
81 func (c *Code) At(x, y int) color.Color {
82 x = x/c.Scale - 4
83 y = y/c.Scale - 4
84 if 0 <= x && x < c.Width && 0 <= y && y < c.Width {
85 switch p := c.Pixel[y][x]; {
86 case p&Black == 0:
87 // nothing
88 case p&DataECC != 0:
89 return black
90 case p&Format != 0:
91 return blue
92 case p&PVersion != 0:
93 return red
94 case p&Timing != 0:
95 return yellow
96 case p&Alignment != 0:
97 return gray
98 case p&Finder != 0:
99 return green
100 }
101 }
102 return white
103 }
104
105 type Chunk struct {
106 Mode Mode
107 Text string
108 }
109
110 func Encode(version Version, level Level, mode Mode, text string) (*Code, error) {
111 return EncodeChunk(version, level, Chunk{mode, text})
112 }
113
114 func EncodeChunk(version Version, level Level, chunk ...Chunk) (*Code, error) {
115 qi, err := C.QRinput_new2(C.int(version), C.QRecLevel(level))
116 if qi == nil {
117 return nil, fmt.Errorf("QRinput_new2: %v", err)
118 }
119 defer C.QRinput_free(qi)
120 for _, ch := range chunk {
121 data := []byte(ch.Text)
122 n, err := C.QRinput_append(qi, C.QRencodeMode(ch.Mode), C.int(len(data)), (*C.uchar)(&data[0]))
123 if n < 0 {
124 return nil, fmt.Errorf("QRinput_append %q: %v", data, err)
125 }
126 }
127
128 qc, err := C.QRcode_encodeInput(qi)
129 if qc == nil {
130 return nil, fmt.Errorf("QRinput_encodeInput: %v", err)
131 }
132
133 c := &Code{
134 Version: int(qc.version),
135 Width: int(qc.width),
136 Scale: 16,
137 }
138 pix := make([]Pixel, c.Width*c.Width)
139 cdat := (*[1000 * 1000]byte)(unsafe.Pointer(qc.data))[:len(pix)]
140 for i := range pix {
141 pix[i] = Pixel(cdat[i])
142 }
143 c.Pixel = make([][]Pixel, c.Width)
144 for i := range c.Pixel {
145 c.Pixel[i] = pix[i*c.Width : (i+1)*c.Width]
146 }
147 return c, nil
148 }
+400
-0
png.go less more
0 // Copyright 2011 The Go Authors. All rights reserved.
1 // Use of this source code is governed by a BSD-style
2 // license that can be found in the LICENSE file.
3
4 package qr
5
6 // PNG writer for QR codes.
7
8 import (
9 "bytes"
10 "encoding/binary"
11 "hash"
12 "hash/crc32"
13 )
14
15 // PNG returns a PNG image displaying the code.
16 //
17 // PNG uses a custom encoder tailored to QR codes.
18 // Its compressed size is about 2x away from optimal,
19 // but it runs about 20x faster than calling png.Encode
20 // on c.Image().
21 func (c *Code) PNG() []byte {
22 var p pngWriter
23 return p.encode(c)
24 }
25
26 type pngWriter struct {
27 tmp [16]byte
28 wctmp [4]byte
29 buf bytes.Buffer
30 zlib bitWriter
31 crc hash.Hash32
32 }
33
34 var pngHeader = []byte("\x89PNG\r\n\x1a\n")
35
36 func (w *pngWriter) encode(c *Code) []byte {
37 scale := c.Scale
38 siz := c.Size
39
40 w.buf.Reset()
41
42 // Header
43 w.buf.Write(pngHeader)
44
45 // Header block
46 binary.BigEndian.PutUint32(w.tmp[0:4], uint32((siz+8)*scale))
47 binary.BigEndian.PutUint32(w.tmp[4:8], uint32((siz+8)*scale))
48 w.tmp[8] = 1 // 1-bit
49 w.tmp[9] = 0 // gray
50 w.tmp[10] = 0
51 w.tmp[11] = 0
52 w.tmp[12] = 0
53 w.writeChunk("IHDR", w.tmp[:13])
54
55 // Comment
56 w.writeChunk("tEXt", comment)
57
58 // Data
59 w.zlib.writeCode(c)
60 w.writeChunk("IDAT", w.zlib.bytes.Bytes())
61
62 // End
63 w.writeChunk("IEND", nil)
64
65 return w.buf.Bytes()
66 }
67
68 var comment = []byte("Software\x00QR-PNG http://qr.swtch.com/")
69
70 func (w *pngWriter) writeChunk(name string, data []byte) {
71 if w.crc == nil {
72 w.crc = crc32.NewIEEE()
73 }
74 binary.BigEndian.PutUint32(w.wctmp[0:4], uint32(len(data)))
75 w.buf.Write(w.wctmp[0:4])
76 w.crc.Reset()
77 copy(w.wctmp[0:4], name)
78 w.buf.Write(w.wctmp[0:4])
79 w.crc.Write(w.wctmp[0:4])
80 w.buf.Write(data)
81 w.crc.Write(data)
82 crc := w.crc.Sum32()
83 binary.BigEndian.PutUint32(w.wctmp[0:4], crc)
84 w.buf.Write(w.wctmp[0:4])
85 }
86
87 func (b *bitWriter) writeCode(c *Code) {
88 const ftNone = 0
89
90 b.adler32.Reset()
91 b.bytes.Reset()
92 b.nbit = 0
93
94 scale := c.Scale
95 siz := c.Size
96
97 // zlib header
98 b.tmp[0] = 0x78
99 b.tmp[1] = 0
100 b.tmp[1] += uint8(31 - (uint16(b.tmp[0])<<8+uint16(b.tmp[1]))%31)
101 b.bytes.Write(b.tmp[0:2])
102
103 // Start flate block.
104 b.writeBits(1, 1, false) // final block
105 b.writeBits(1, 2, false) // compressed, fixed Huffman tables
106
107 // White border.
108 // First row.
109 b.byte(ftNone)
110 n := (scale*(siz+8) + 7) / 8
111 b.byte(255)
112 b.repeat(n-1, 1)
113 // 4*scale rows total.
114 b.repeat((4*scale-1)*(1+n), 1+n)
115
116 for i := 0; i < 4*scale; i++ {
117 b.adler32.WriteNByte(ftNone, 1)
118 b.adler32.WriteNByte(255, n)
119 }
120
121 row := make([]byte, 1+n)
122 for y := 0; y < siz; y++ {
123 row[0] = ftNone
124 j := 1
125 var z uint8
126 nz := 0
127 for x := -4; x < siz+4; x++ {
128 // Raw data.
129 for i := 0; i < scale; i++ {
130 z <<= 1
131 if !c.Black(x, y) {
132 z |= 1
133 }
134 if nz++; nz == 8 {
135 row[j] = z
136 j++
137 nz = 0
138 }
139 }
140 }
141 if j < len(row) {
142 row[j] = z
143 }
144 for _, z := range row {
145 b.byte(z)
146 }
147
148 // Scale-1 copies.
149 b.repeat((scale-1)*(1+n), 1+n)
150
151 b.adler32.WriteN(row, scale)
152 }
153
154 // White border.
155 // First row.
156 b.byte(ftNone)
157 b.byte(255)
158 b.repeat(n-1, 1)
159 // 4*scale rows total.
160 b.repeat((4*scale-1)*(1+n), 1+n)
161
162 for i := 0; i < 4*scale; i++ {
163 b.adler32.WriteNByte(ftNone, 1)
164 b.adler32.WriteNByte(255, n)
165 }
166
167 // End of block.
168 b.hcode(256)
169 b.flushBits()
170
171 // adler32
172 binary.BigEndian.PutUint32(b.tmp[0:], b.adler32.Sum32())
173 b.bytes.Write(b.tmp[0:4])
174 }
175
176 // A bitWriter is a write buffer for bit-oriented data like deflate.
177 type bitWriter struct {
178 bytes bytes.Buffer
179 bit uint32
180 nbit uint
181
182 tmp [4]byte
183 adler32 adigest
184 }
185
186 func (b *bitWriter) writeBits(bit uint32, nbit uint, rev bool) {
187 // reverse, for huffman codes
188 if rev {
189 br := uint32(0)
190 for i := uint(0); i < nbit; i++ {
191 br |= ((bit >> i) & 1) << (nbit - 1 - i)
192 }
193 bit = br
194 }
195 b.bit |= bit << b.nbit
196 b.nbit += nbit
197 for b.nbit >= 8 {
198 b.bytes.WriteByte(byte(b.bit))
199 b.bit >>= 8
200 b.nbit -= 8
201 }
202 }
203
204 func (b *bitWriter) flushBits() {
205 if b.nbit > 0 {
206 b.bytes.WriteByte(byte(b.bit))
207 b.nbit = 0
208 b.bit = 0
209 }
210 }
211
212 func (b *bitWriter) hcode(v int) {
213 /*
214 Lit Value Bits Codes
215 --------- ---- -----
216 0 - 143 8 00110000 through
217 10111111
218 144 - 255 9 110010000 through
219 111111111
220 256 - 279 7 0000000 through
221 0010111
222 280 - 287 8 11000000 through
223 11000111
224 */
225 switch {
226 case v <= 143:
227 b.writeBits(uint32(v)+0x30, 8, true)
228 case v <= 255:
229 b.writeBits(uint32(v-144)+0x190, 9, true)
230 case v <= 279:
231 b.writeBits(uint32(v-256)+0, 7, true)
232 case v <= 287:
233 b.writeBits(uint32(v-280)+0xc0, 8, true)
234 default:
235 panic("invalid hcode")
236 }
237 }
238
239 func (b *bitWriter) byte(x byte) {
240 b.hcode(int(x))
241 }
242
243 func (b *bitWriter) codex(c int, val int, nx uint) {
244 b.hcode(c + val>>nx)
245 b.writeBits(uint32(val)&(1<<nx-1), nx, false)
246 }
247
248 func (b *bitWriter) repeat(n, d int) {
249 for ; n >= 258+3; n -= 258 {
250 b.repeat1(258, d)
251 }
252 if n > 258 {
253 // 258 < n < 258+3
254 b.repeat1(10, d)
255 b.repeat1(n-10, d)
256 return
257 }
258 if n < 3 {
259 panic("invalid flate repeat")
260 }
261 b.repeat1(n, d)
262 }
263
264 func (b *bitWriter) repeat1(n, d int) {
265 /*
266 Extra Extra Extra
267 Code Bits Length(s) Code Bits Lengths Code Bits Length(s)
268 ---- ---- ------ ---- ---- ------- ---- ---- -------
269 257 0 3 267 1 15,16 277 4 67-82
270 258 0 4 268 1 17,18 278 4 83-98
271 259 0 5 269 2 19-22 279 4 99-114
272 260 0 6 270 2 23-26 280 4 115-130
273 261 0 7 271 2 27-30 281 5 131-162
274 262 0 8 272 2 31-34 282 5 163-194
275 263 0 9 273 3 35-42 283 5 195-226
276 264 0 10 274 3 43-50 284 5 227-257
277 265 1 11,12 275 3 51-58 285 0 258
278 266 1 13,14 276 3 59-66
279 */
280 switch {
281 case n <= 10:
282 b.codex(257, n-3, 0)
283 case n <= 18:
284 b.codex(265, n-11, 1)
285 case n <= 34:
286 b.codex(269, n-19, 2)
287 case n <= 66:
288 b.codex(273, n-35, 3)
289 case n <= 130:
290 b.codex(277, n-67, 4)
291 case n <= 257:
292 b.codex(281, n-131, 5)
293 case n == 258:
294 b.hcode(285)
295 default:
296 panic("invalid repeat length")
297 }
298
299 /*
300 Extra Extra Extra
301 Code Bits Dist Code Bits Dist Code Bits Distance
302 ---- ---- ---- ---- ---- ------ ---- ---- --------
303 0 0 1 10 4 33-48 20 9 1025-1536
304 1 0 2 11 4 49-64 21 9 1537-2048
305 2 0 3 12 5 65-96 22 10 2049-3072
306 3 0 4 13 5 97-128 23 10 3073-4096
307 4 1 5,6 14 6 129-192 24 11 4097-6144
308 5 1 7,8 15 6 193-256 25 11 6145-8192
309 6 2 9-12 16 7 257-384 26 12 8193-12288
310 7 2 13-16 17 7 385-512 27 12 12289-16384
311 8 3 17-24 18 8 513-768 28 13 16385-24576
312 9 3 25-32 19 8 769-1024 29 13 24577-32768
313 */
314 if d <= 4 {
315 b.writeBits(uint32(d-1), 5, true)
316 } else if d <= 32768 {
317 nbit := uint(16)
318 for d <= 1<<(nbit-1) {
319 nbit--
320 }
321 v := uint32(d - 1)
322 v &^= 1 << (nbit - 1) // top bit is implicit
323 code := uint32(2*nbit - 2) // second bit is low bit of code
324 code |= v >> (nbit - 2)
325 v &^= 1 << (nbit - 2)
326 b.writeBits(code, 5, true)
327 // rest of bits follow
328 b.writeBits(uint32(v), nbit-2, false)
329 } else {
330 panic("invalid repeat distance")
331 }
332 }
333
334 func (b *bitWriter) run(v byte, n int) {
335 if n == 0 {
336 return
337 }
338 b.byte(v)
339 if n-1 < 3 {
340 for i := 0; i < n-1; i++ {
341 b.byte(v)
342 }
343 } else {
344 b.repeat(n-1, 1)
345 }
346 }
347
348 type adigest struct {
349 a, b uint32
350 }
351
352 func (d *adigest) Reset() { d.a, d.b = 1, 0 }
353
354 const amod = 65521
355
356 func aupdate(a, b uint32, pi byte, n int) (aa, bb uint32) {
357 // TODO(rsc): 6g doesn't do magic multiplies for b %= amod,
358 // only for b = b%amod.
359
360 // invariant: a, b < amod
361 if pi == 0 {
362 b += uint32(n%amod) * a
363 b = b % amod
364 return a, b
365 }
366
367 // n times:
368 // a += pi
369 // b += a
370 // is same as
371 // b += n*a + n*(n+1)/2*pi
372 // a += n*pi
373 m := uint32(n)
374 b += (m % amod) * a
375 b = b % amod
376 b += (m * (m + 1) / 2) % amod * uint32(pi)
377 b = b % amod
378 a += (m % amod) * uint32(pi)
379 a = a % amod
380 return a, b
381 }
382
383 func afinish(a, b uint32) uint32 {
384 return b<<16 | a
385 }
386
387 func (d *adigest) WriteN(p []byte, n int) {
388 for i := 0; i < n; i++ {
389 for _, pi := range p {
390 d.a, d.b = aupdate(d.a, d.b, pi, 1)
391 }
392 }
393 }
394
395 func (d *adigest) WriteNByte(pi byte, n int) {
396 d.a, d.b = aupdate(d.a, d.b, pi, n)
397 }
398
399 func (d *adigest) Sum32() uint32 { return afinish(d.a, d.b) }
+73
-0
png_test.go less more
0 // Copyright 2011 The Go Authors. All rights reserved.
1 // Use of this source code is governed by a BSD-style
2 // license that can be found in the LICENSE file.
3
4 package qr
5
6 import (
7 "bytes"
8 "image"
9 "image/color"
10 "image/png"
11 "io/ioutil"
12 "testing"
13 )
14
15 func TestPNG(t *testing.T) {
16 c, err := Encode("hello, world", L)
17 if err != nil {
18 t.Fatal(err)
19 }
20 pngdat := c.PNG()
21 if true {
22 ioutil.WriteFile("x.png", pngdat, 0666)
23 }
24 m, err := png.Decode(bytes.NewBuffer(pngdat))
25 if err != nil {
26 t.Fatal(err)
27 }
28 gm := m.(*image.Gray)
29
30 scale := c.Scale
31 siz := c.Size
32 nbad := 0
33 for y := 0; y < scale*(8+siz); y++ {
34 for x := 0; x < scale*(8+siz); x++ {
35 v := byte(255)
36 if c.Black(x/scale-4, y/scale-4) {
37 v = 0
38 }
39 if gv := gm.At(x, y).(color.Gray).Y; gv != v {
40 t.Errorf("%d,%d = %d, want %d", x, y, gv, v)
41 if nbad++; nbad >= 20 {
42 t.Fatalf("too many bad pixels")
43 }
44 }
45 }
46 }
47 }
48
49 func BenchmarkPNG(b *testing.B) {
50 c, err := Encode("0123456789012345678901234567890123456789", L)
51 if err != nil {
52 panic(err)
53 }
54 var bytes []byte
55 for i := 0; i < b.N; i++ {
56 bytes = c.PNG()
57 }
58 b.SetBytes(int64(len(bytes)))
59 }
60
61 func BenchmarkImagePNG(b *testing.B) {
62 c, err := Encode("0123456789012345678901234567890123456789", L)
63 if err != nil {
64 panic(err)
65 }
66 var buf bytes.Buffer
67 for i := 0; i < b.N; i++ {
68 buf.Reset()
69 png.Encode(&buf, c.Image())
70 }
71 b.SetBytes(int64(buf.Len()))
72 }
+116
-0
qr.go less more
0 // Copyright 2011 The Go Authors. All rights reserved.
1 // Use of this source code is governed by a BSD-style
2 // license that can be found in the LICENSE file.
3
4 /*
5 Package qr encodes QR codes.
6 */
7 package qr
8
9 import (
10 "errors"
11 "image"
12 "image/color"
13
14 "rsc.io/qr/coding"
15 )
16
17 // A Level denotes a QR error correction level.
18 // From least to most tolerant of errors, they are L, M, Q, H.
19 type Level int
20
21 const (
22 L Level = iota // 20% redundant
23 M // 38% redundant
24 Q // 55% redundant
25 H // 65% redundant
26 )
27
28 // Encode returns an encoding of text at the given error correction level.
29 func Encode(text string, level Level) (*Code, error) {
30 // Pick data encoding, smallest first.
31 // We could split the string and use different encodings
32 // but that seems like overkill for now.
33 var enc coding.Encoding
34 switch {
35 case coding.Num(text).Check() == nil:
36 enc = coding.Num(text)
37 case coding.Alpha(text).Check() == nil:
38 enc = coding.Alpha(text)
39 default:
40 enc = coding.String(text)
41 }
42
43 // Pick size.
44 l := coding.Level(level)
45 var v coding.Version
46 for v = coding.MinVersion; ; v++ {
47 if v > coding.MaxVersion {
48 return nil, errors.New("text too long to encode as QR")
49 }
50 if enc.Bits(v) <= v.DataBytes(l)*8 {
51 break
52 }
53 }
54
55 // Build and execute plan.
56 p, err := coding.NewPlan(v, l, 0)
57 if err != nil {
58 return nil, err
59 }
60 cc, err := p.Encode(enc)
61 if err != nil {
62 return nil, err
63 }
64
65 // TODO: Pick appropriate mask.
66
67 return &Code{cc.Bitmap, cc.Size, cc.Stride, 8}, nil
68 }
69
70 // A Code is a square pixel grid.
71 // It implements image.Image and direct PNG encoding.
72 type Code struct {
73 Bitmap []byte // 1 is black, 0 is white
74 Size int // number of pixels on a side
75 Stride int // number of bytes per row
76 Scale int // number of image pixels per QR pixel
77 }
78
79 // Black returns true if the pixel at (x,y) is black.
80 func (c *Code) Black(x, y int) bool {
81 return 0 <= x && x < c.Size && 0 <= y && y < c.Size &&
82 c.Bitmap[y*c.Stride+x/8]&(1<<uint(7-x&7)) != 0
83 }
84
85 // Image returns an Image displaying the code.
86 func (c *Code) Image() image.Image {
87 return &codeImage{c}
88
89 }
90
91 // codeImage implements image.Image
92 type codeImage struct {
93 *Code
94 }
95
96 var (
97 whiteColor color.Color = color.Gray{0xFF}
98 blackColor color.Color = color.Gray{0x00}
99 )
100
101 func (c *codeImage) Bounds() image.Rectangle {
102 d := (c.Size + 8) * c.Scale
103 return image.Rect(0, 0, d, d)
104 }
105
106 func (c *codeImage) At(x, y int) color.Color {
107 if c.Black(x, y) {
108 return blackColor
109 }
110 return whiteColor
111 }
112
113 func (c *codeImage) ColorModel() color.Model {
114 return color.GrayModel
115 }