diff options
Diffstat (limited to 'Godeps/_workspace/src/github.com/mattermost/rsc/qr/coding')
4 files changed, 1104 insertions, 0 deletions
diff --git a/Godeps/_workspace/src/github.com/mattermost/rsc/qr/coding/Makefile b/Godeps/_workspace/src/github.com/mattermost/rsc/qr/coding/Makefile new file mode 100644 index 000000000..5d1c4d307 --- /dev/null +++ b/Godeps/_workspace/src/github.com/mattermost/rsc/qr/coding/Makefile @@ -0,0 +1,7 @@ +include $(GOROOT)/src/Make.inc + +TARG=rsc.googlecode.com/hg/qr/coding +GOFILES=\ + qr.go\ + +include $(GOROOT)/src/Make.pkg diff --git a/Godeps/_workspace/src/github.com/mattermost/rsc/qr/coding/gen.go b/Godeps/_workspace/src/github.com/mattermost/rsc/qr/coding/gen.go new file mode 100644 index 000000000..a3857f277 --- /dev/null +++ b/Godeps/_workspace/src/github.com/mattermost/rsc/qr/coding/gen.go @@ -0,0 +1,149 @@ +// +build ignore + +package main + +import "fmt" + +// tables from qrencode-3.1.1/qrspec.c + +var capacity = [41]struct { + width int + words int + remainder int + ec [4]int +}{ + {0, 0, 0, [4]int{0, 0, 0, 0}}, + {21, 26, 0, [4]int{7, 10, 13, 17}}, // 1 + {25, 44, 7, [4]int{10, 16, 22, 28}}, + {29, 70, 7, [4]int{15, 26, 36, 44}}, + {33, 100, 7, [4]int{20, 36, 52, 64}}, + {37, 134, 7, [4]int{26, 48, 72, 88}}, // 5 + {41, 172, 7, [4]int{36, 64, 96, 112}}, + {45, 196, 0, [4]int{40, 72, 108, 130}}, + {49, 242, 0, [4]int{48, 88, 132, 156}}, + {53, 292, 0, [4]int{60, 110, 160, 192}}, + {57, 346, 0, [4]int{72, 130, 192, 224}}, //10 + {61, 404, 0, [4]int{80, 150, 224, 264}}, + {65, 466, 0, [4]int{96, 176, 260, 308}}, + {69, 532, 0, [4]int{104, 198, 288, 352}}, + {73, 581, 3, [4]int{120, 216, 320, 384}}, + {77, 655, 3, [4]int{132, 240, 360, 432}}, //15 + {81, 733, 3, [4]int{144, 280, 408, 480}}, + {85, 815, 3, [4]int{168, 308, 448, 532}}, + {89, 901, 3, [4]int{180, 338, 504, 588}}, + {93, 991, 3, [4]int{196, 364, 546, 650}}, + {97, 1085, 3, [4]int{224, 416, 600, 700}}, //20 + {101, 1156, 4, [4]int{224, 442, 644, 750}}, + {105, 1258, 4, [4]int{252, 476, 690, 816}}, + {109, 1364, 4, [4]int{270, 504, 750, 900}}, + {113, 1474, 4, [4]int{300, 560, 810, 960}}, + {117, 1588, 4, [4]int{312, 588, 870, 1050}}, //25 + {121, 1706, 4, [4]int{336, 644, 952, 1110}}, + {125, 1828, 4, [4]int{360, 700, 1020, 1200}}, + {129, 1921, 3, [4]int{390, 728, 1050, 1260}}, + {133, 2051, 3, [4]int{420, 784, 1140, 1350}}, + {137, 2185, 3, [4]int{450, 812, 1200, 1440}}, //30 + {141, 2323, 3, [4]int{480, 868, 1290, 1530}}, + {145, 2465, 3, [4]int{510, 924, 1350, 1620}}, + {149, 2611, 3, [4]int{540, 980, 1440, 1710}}, + {153, 2761, 3, [4]int{570, 1036, 1530, 1800}}, + {157, 2876, 0, [4]int{570, 1064, 1590, 1890}}, //35 + {161, 3034, 0, [4]int{600, 1120, 1680, 1980}}, + {165, 3196, 0, [4]int{630, 1204, 1770, 2100}}, + {169, 3362, 0, [4]int{660, 1260, 1860, 2220}}, + {173, 3532, 0, [4]int{720, 1316, 1950, 2310}}, + {177, 3706, 0, [4]int{750, 1372, 2040, 2430}}, //40 +} + +var eccTable = [41][4][2]int{ + {{0, 0}, {0, 0}, {0, 0}, {0, 0}}, + {{1, 0}, {1, 0}, {1, 0}, {1, 0}}, // 1 + {{1, 0}, {1, 0}, {1, 0}, {1, 0}}, + {{1, 0}, {1, 0}, {2, 0}, {2, 0}}, + {{1, 0}, {2, 0}, {2, 0}, {4, 0}}, + {{1, 0}, {2, 0}, {2, 2}, {2, 2}}, // 5 + {{2, 0}, {4, 0}, {4, 0}, {4, 0}}, + {{2, 0}, {4, 0}, {2, 4}, {4, 1}}, + {{2, 0}, {2, 2}, {4, 2}, {4, 2}}, + {{2, 0}, {3, 2}, {4, 4}, {4, 4}}, + {{2, 2}, {4, 1}, {6, 2}, {6, 2}}, //10 + {{4, 0}, {1, 4}, {4, 4}, {3, 8}}, + {{2, 2}, {6, 2}, {4, 6}, {7, 4}}, + {{4, 0}, {8, 1}, {8, 4}, {12, 4}}, + {{3, 1}, {4, 5}, {11, 5}, {11, 5}}, + {{5, 1}, {5, 5}, {5, 7}, {11, 7}}, //15 + {{5, 1}, {7, 3}, {15, 2}, {3, 13}}, + {{1, 5}, {10, 1}, {1, 15}, {2, 17}}, + {{5, 1}, {9, 4}, {17, 1}, {2, 19}}, + {{3, 4}, {3, 11}, {17, 4}, {9, 16}}, + {{3, 5}, {3, 13}, {15, 5}, {15, 10}}, //20 + {{4, 4}, {17, 0}, {17, 6}, {19, 6}}, + {{2, 7}, {17, 0}, {7, 16}, {34, 0}}, + {{4, 5}, {4, 14}, {11, 14}, {16, 14}}, + {{6, 4}, {6, 14}, {11, 16}, {30, 2}}, + {{8, 4}, {8, 13}, {7, 22}, {22, 13}}, //25 + {{10, 2}, {19, 4}, {28, 6}, {33, 4}}, + {{8, 4}, {22, 3}, {8, 26}, {12, 28}}, + {{3, 10}, {3, 23}, {4, 31}, {11, 31}}, + {{7, 7}, {21, 7}, {1, 37}, {19, 26}}, + {{5, 10}, {19, 10}, {15, 25}, {23, 25}}, //30 + {{13, 3}, {2, 29}, {42, 1}, {23, 28}}, + {{17, 0}, {10, 23}, {10, 35}, {19, 35}}, + {{17, 1}, {14, 21}, {29, 19}, {11, 46}}, + {{13, 6}, {14, 23}, {44, 7}, {59, 1}}, + {{12, 7}, {12, 26}, {39, 14}, {22, 41}}, //35 + {{6, 14}, {6, 34}, {46, 10}, {2, 64}}, + {{17, 4}, {29, 14}, {49, 10}, {24, 46}}, + {{4, 18}, {13, 32}, {48, 14}, {42, 32}}, + {{20, 4}, {40, 7}, {43, 22}, {10, 67}}, + {{19, 6}, {18, 31}, {34, 34}, {20, 61}}, //40 +} + +var align = [41][2]int{ + {0, 0}, + {0, 0}, {18, 0}, {22, 0}, {26, 0}, {30, 0}, // 1- 5 + {34, 0}, {22, 38}, {24, 42}, {26, 46}, {28, 50}, // 6-10 + {30, 54}, {32, 58}, {34, 62}, {26, 46}, {26, 48}, //11-15 + {26, 50}, {30, 54}, {30, 56}, {30, 58}, {34, 62}, //16-20 + {28, 50}, {26, 50}, {30, 54}, {28, 54}, {32, 58}, //21-25 + {30, 58}, {34, 62}, {26, 50}, {30, 54}, {26, 52}, //26-30 + {30, 56}, {34, 60}, {30, 58}, {34, 62}, {30, 54}, //31-35 + {24, 50}, {28, 54}, {32, 58}, {26, 54}, {30, 58}, //35-40 +} + +var versionPattern = [41]int{ + 0, + 0, 0, 0, 0, 0, 0, + 0x07c94, 0x085bc, 0x09a99, 0x0a4d3, 0x0bbf6, 0x0c762, 0x0d847, 0x0e60d, + 0x0f928, 0x10b78, 0x1145d, 0x12a17, 0x13532, 0x149a6, 0x15683, 0x168c9, + 0x177ec, 0x18ec4, 0x191e1, 0x1afab, 0x1b08e, 0x1cc1a, 0x1d33f, 0x1ed75, + 0x1f250, 0x209d5, 0x216f0, 0x228ba, 0x2379f, 0x24b0b, 0x2542e, 0x26a64, + 0x27541, 0x28c69, +} + +func main() { + fmt.Printf("\t{},\n") + for i := 1; i <= 40; i++ { + apos := align[i][0] - 2 + if apos < 0 { + apos = 100 + } + astride := align[i][1] - align[i][0] + if astride < 1 { + astride = 100 + } + fmt.Printf("\t{%v, %v, %v, %#x, [4]level{{%v, %v}, {%v, %v}, {%v, %v}, {%v, %v}}}, // %v\n", + apos, astride, capacity[i].words, + versionPattern[i], + eccTable[i][0][0]+eccTable[i][0][1], + float64(capacity[i].ec[0])/float64(eccTable[i][0][0]+eccTable[i][0][1]), + eccTable[i][1][0]+eccTable[i][1][1], + float64(capacity[i].ec[1])/float64(eccTable[i][1][0]+eccTable[i][1][1]), + eccTable[i][2][0]+eccTable[i][2][1], + float64(capacity[i].ec[2])/float64(eccTable[i][2][0]+eccTable[i][2][1]), + eccTable[i][3][0]+eccTable[i][3][1], + float64(capacity[i].ec[3])/float64(eccTable[i][3][0]+eccTable[i][3][1]), + i, + ) + } +} diff --git a/Godeps/_workspace/src/github.com/mattermost/rsc/qr/coding/qr.go b/Godeps/_workspace/src/github.com/mattermost/rsc/qr/coding/qr.go new file mode 100644 index 000000000..35711a4eb --- /dev/null +++ b/Godeps/_workspace/src/github.com/mattermost/rsc/qr/coding/qr.go @@ -0,0 +1,815 @@ +// Copyright 2011 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// Package coding implements low-level QR coding details. +package coding + +import ( + "fmt" + "strconv" + "strings" + + "github.com/mattermost/rsc/gf256" +) + +// Field is the field for QR error correction. +var Field = gf256.NewField(0x11d, 2) + +// A Version represents a QR version. +// The version specifies the size of the QR code: +// a QR code with version v has 4v+17 pixels on a side. +// Versions number from 1 to 40: the larger the version, +// the more information the code can store. +type Version int + +const MinVersion = 1 +const MaxVersion = 40 + +func (v Version) String() string { + return strconv.Itoa(int(v)) +} + +func (v Version) sizeClass() int { + if v <= 9 { + return 0 + } + if v <= 26 { + return 1 + } + return 2 +} + +// DataBytes returns the number of data bytes that can be +// stored in a QR code with the given version and level. +func (v Version) DataBytes(l Level) int { + vt := &vtab[v] + lev := &vt.level[l] + return vt.bytes - lev.nblock*lev.check +} + +// Encoding implements a QR data encoding scheme. +// The implementations--Numeric, Alphanumeric, and String--specify +// the character set and the mapping from UTF-8 to code bits. +// The more restrictive the mode, the fewer code bits are needed. +type Encoding interface { + Check() error + Bits(v Version) int + Encode(b *Bits, v Version) +} + +type Bits struct { + b []byte + nbit int +} + +func (b *Bits) Reset() { + b.b = b.b[:0] + b.nbit = 0 +} + +func (b *Bits) Bits() int { + return b.nbit +} + +func (b *Bits) Bytes() []byte { + if b.nbit%8 != 0 { + panic("fractional byte") + } + return b.b +} + +func (b *Bits) Append(p []byte) { + if b.nbit%8 != 0 { + panic("fractional byte") + } + b.b = append(b.b, p...) + b.nbit += 8 * len(p) +} + +func (b *Bits) Write(v uint, nbit int) { + for nbit > 0 { + n := nbit + if n > 8 { + n = 8 + } + if b.nbit%8 == 0 { + b.b = append(b.b, 0) + } else { + m := -b.nbit & 7 + if n > m { + n = m + } + } + b.nbit += n + sh := uint(nbit - n) + b.b[len(b.b)-1] |= uint8(v >> sh << uint(-b.nbit&7)) + v -= v >> sh << sh + nbit -= n + } +} + +// Num is the encoding for numeric data. +// The only valid characters are the decimal digits 0 through 9. +type Num string + +func (s Num) String() string { + return fmt.Sprintf("Num(%#q)", string(s)) +} + +func (s Num) Check() error { + for _, c := range s { + if c < '0' || '9' < c { + return fmt.Errorf("non-numeric string %#q", string(s)) + } + } + return nil +} + +var numLen = [3]int{10, 12, 14} + +func (s Num) Bits(v Version) int { + return 4 + numLen[v.sizeClass()] + (10*len(s)+2)/3 +} + +func (s Num) Encode(b *Bits, v Version) { + b.Write(1, 4) + b.Write(uint(len(s)), numLen[v.sizeClass()]) + var i int + for i = 0; i+3 <= len(s); i += 3 { + w := uint(s[i]-'0')*100 + uint(s[i+1]-'0')*10 + uint(s[i+2]-'0') + b.Write(w, 10) + } + switch len(s) - i { + case 1: + w := uint(s[i] - '0') + b.Write(w, 4) + case 2: + w := uint(s[i]-'0')*10 + uint(s[i+1]-'0') + b.Write(w, 7) + } +} + +// Alpha is the encoding for alphanumeric data. +// The valid characters are 0-9A-Z$%*+-./: and space. +type Alpha string + +const alphabet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:" + +func (s Alpha) String() string { + return fmt.Sprintf("Alpha(%#q)", string(s)) +} + +func (s Alpha) Check() error { + for _, c := range s { + if strings.IndexRune(alphabet, c) < 0 { + return fmt.Errorf("non-alphanumeric string %#q", string(s)) + } + } + return nil +} + +var alphaLen = [3]int{9, 11, 13} + +func (s Alpha) Bits(v Version) int { + return 4 + alphaLen[v.sizeClass()] + (11*len(s)+1)/2 +} + +func (s Alpha) Encode(b *Bits, v Version) { + b.Write(2, 4) + b.Write(uint(len(s)), alphaLen[v.sizeClass()]) + var i int + for i = 0; i+2 <= len(s); i += 2 { + w := uint(strings.IndexRune(alphabet, rune(s[i])))*45 + + uint(strings.IndexRune(alphabet, rune(s[i+1]))) + b.Write(w, 11) + } + + if i < len(s) { + w := uint(strings.IndexRune(alphabet, rune(s[i]))) + b.Write(w, 6) + } +} + +// String is the encoding for 8-bit data. All bytes are valid. +type String string + +func (s String) String() string { + return fmt.Sprintf("String(%#q)", string(s)) +} + +func (s String) Check() error { + return nil +} + +var stringLen = [3]int{8, 16, 16} + +func (s String) Bits(v Version) int { + return 4 + stringLen[v.sizeClass()] + 8*len(s) +} + +func (s String) Encode(b *Bits, v Version) { + b.Write(4, 4) + b.Write(uint(len(s)), stringLen[v.sizeClass()]) + for i := 0; i < len(s); i++ { + b.Write(uint(s[i]), 8) + } +} + +// A Pixel describes a single pixel in a QR code. +type Pixel uint32 + +const ( + Black Pixel = 1 << iota + Invert +) + +func (p Pixel) Offset() uint { + return uint(p >> 6) +} + +func OffsetPixel(o uint) Pixel { + return Pixel(o << 6) +} + +func (r PixelRole) Pixel() Pixel { + return Pixel(r << 2) +} + +func (p Pixel) Role() PixelRole { + return PixelRole(p>>2) & 15 +} + +func (p Pixel) String() string { + s := p.Role().String() + if p&Black != 0 { + s += "+black" + } + if p&Invert != 0 { + s += "+invert" + } + s += "+" + strconv.FormatUint(uint64(p.Offset()), 10) + return s +} + +// A PixelRole describes the role of a QR pixel. +type PixelRole uint32 + +const ( + _ PixelRole = iota + Position // position squares (large) + Alignment // alignment squares (small) + Timing // timing strip between position squares + Format // format metadata + PVersion // version pattern + Unused // unused pixel + Data // data bit + Check // error correction check bit + Extra +) + +var roles = []string{ + "", + "position", + "alignment", + "timing", + "format", + "pversion", + "unused", + "data", + "check", + "extra", +} + +func (r PixelRole) String() string { + if Position <= r && r <= Check { + return roles[r] + } + return strconv.Itoa(int(r)) +} + +// A Level represents a QR error correction level. +// From least to most tolerant of errors, they are L, M, Q, H. +type Level int + +const ( + L Level = iota + M + Q + H +) + +func (l Level) String() string { + if L <= l && l <= H { + return "LMQH"[l : l+1] + } + return strconv.Itoa(int(l)) +} + +// A Code is a square pixel grid. +type Code struct { + Bitmap []byte // 1 is black, 0 is white + Size int // number of pixels on a side + Stride int // number of bytes per row +} + +func (c *Code) Black(x, y int) bool { + return 0 <= x && x < c.Size && 0 <= y && y < c.Size && + c.Bitmap[y*c.Stride+x/8]&(1<<uint(7-x&7)) != 0 +} + +// A Mask describes a mask that is applied to the QR +// code to avoid QR artifacts being interpreted as +// alignment and timing patterns (such as the squares +// in the corners). Valid masks are integers from 0 to 7. +type Mask int + +// http://www.swetake.com/qr/qr5_en.html +var mfunc = []func(int, int) bool{ + func(i, j int) bool { return (i+j)%2 == 0 }, + func(i, j int) bool { return i%2 == 0 }, + func(i, j int) bool { return j%3 == 0 }, + func(i, j int) bool { return (i+j)%3 == 0 }, + func(i, j int) bool { return (i/2+j/3)%2 == 0 }, + func(i, j int) bool { return i*j%2+i*j%3 == 0 }, + func(i, j int) bool { return (i*j%2+i*j%3)%2 == 0 }, + func(i, j int) bool { return (i*j%3+(i+j)%2)%2 == 0 }, +} + +func (m Mask) Invert(y, x int) bool { + if m < 0 { + return false + } + return mfunc[m](y, x) +} + +// A Plan describes how to construct a QR code +// with a specific version, level, and mask. +type Plan struct { + Version Version + Level Level + Mask Mask + + DataBytes int // number of data bytes + CheckBytes int // number of error correcting (checksum) bytes + Blocks int // number of data blocks + + Pixel [][]Pixel // pixel map +} + +// NewPlan returns a Plan for a QR code with the given +// version, level, and mask. +func NewPlan(version Version, level Level, mask Mask) (*Plan, error) { + p, err := vplan(version) + if err != nil { + return nil, err + } + if err := fplan(level, mask, p); err != nil { + return nil, err + } + if err := lplan(version, level, p); err != nil { + return nil, err + } + if err := mplan(mask, p); err != nil { + return nil, err + } + return p, nil +} + +func (b *Bits) Pad(n int) { + if n < 0 { + panic("qr: invalid pad size") + } + if n <= 4 { + b.Write(0, n) + } else { + b.Write(0, 4) + n -= 4 + n -= -b.Bits() & 7 + b.Write(0, -b.Bits()&7) + pad := n / 8 + for i := 0; i < pad; i += 2 { + b.Write(0xec, 8) + if i+1 >= pad { + break + } + b.Write(0x11, 8) + } + } +} + +func (b *Bits) AddCheckBytes(v Version, l Level) { + nd := v.DataBytes(l) + if b.nbit < nd*8 { + b.Pad(nd*8 - b.nbit) + } + if b.nbit != nd*8 { + panic("qr: too much data") + } + + dat := b.Bytes() + vt := &vtab[v] + lev := &vt.level[l] + db := nd / lev.nblock + extra := nd % lev.nblock + chk := make([]byte, lev.check) + rs := gf256.NewRSEncoder(Field, lev.check) + for i := 0; i < lev.nblock; i++ { + if i == lev.nblock-extra { + db++ + } + rs.ECC(dat[:db], chk) + b.Append(chk) + dat = dat[db:] + } + + if len(b.Bytes()) != vt.bytes { + panic("qr: internal error") + } +} + +func (p *Plan) Encode(text ...Encoding) (*Code, error) { + var b Bits + for _, t := range text { + if err := t.Check(); err != nil { + return nil, err + } + t.Encode(&b, p.Version) + } + if b.Bits() > p.DataBytes*8 { + return nil, fmt.Errorf("cannot encode %d bits into %d-bit code", b.Bits(), p.DataBytes*8) + } + b.AddCheckBytes(p.Version, p.Level) + bytes := b.Bytes() + + // Now we have the checksum bytes and the data bytes. + // Construct the actual code. + c := &Code{Size: len(p.Pixel), Stride: (len(p.Pixel) + 7) &^ 7} + c.Bitmap = make([]byte, c.Stride*c.Size) + crow := c.Bitmap + for _, row := range p.Pixel { + for x, pix := range row { + switch pix.Role() { + case Data, Check: + o := pix.Offset() + if bytes[o/8]&(1<<uint(7-o&7)) != 0 { + pix ^= Black + } + } + if pix&Black != 0 { + crow[x/8] |= 1 << uint(7-x&7) + } + } + crow = crow[c.Stride:] + } + return c, nil +} + +// A version describes metadata associated with a version. +type version struct { + apos int + astride int + bytes int + pattern int + level [4]level +} + +type level struct { + nblock int + check int +} + +var vtab = []version{ + {}, + {100, 100, 26, 0x0, [4]level{{1, 7}, {1, 10}, {1, 13}, {1, 17}}}, // 1 + {16, 100, 44, 0x0, [4]level{{1, 10}, {1, 16}, {1, 22}, {1, 28}}}, // 2 + {20, 100, 70, 0x0, [4]level{{1, 15}, {1, 26}, {2, 18}, {2, 22}}}, // 3 + {24, 100, 100, 0x0, [4]level{{1, 20}, {2, 18}, {2, 26}, {4, 16}}}, // 4 + {28, 100, 134, 0x0, [4]level{{1, 26}, {2, 24}, {4, 18}, {4, 22}}}, // 5 + {32, 100, 172, 0x0, [4]level{{2, 18}, {4, 16}, {4, 24}, {4, 28}}}, // 6 + {20, 16, 196, 0x7c94, [4]level{{2, 20}, {4, 18}, {6, 18}, {5, 26}}}, // 7 + {22, 18, 242, 0x85bc, [4]level{{2, 24}, {4, 22}, {6, 22}, {6, 26}}}, // 8 + {24, 20, 292, 0x9a99, [4]level{{2, 30}, {5, 22}, {8, 20}, {8, 24}}}, // 9 + {26, 22, 346, 0xa4d3, [4]level{{4, 18}, {5, 26}, {8, 24}, {8, 28}}}, // 10 + {28, 24, 404, 0xbbf6, [4]level{{4, 20}, {5, 30}, {8, 28}, {11, 24}}}, // 11 + {30, 26, 466, 0xc762, [4]level{{4, 24}, {8, 22}, {10, 26}, {11, 28}}}, // 12 + {32, 28, 532, 0xd847, [4]level{{4, 26}, {9, 22}, {12, 24}, {16, 22}}}, // 13 + {24, 20, 581, 0xe60d, [4]level{{4, 30}, {9, 24}, {16, 20}, {16, 24}}}, // 14 + {24, 22, 655, 0xf928, [4]level{{6, 22}, {10, 24}, {12, 30}, {18, 24}}}, // 15 + {24, 24, 733, 0x10b78, [4]level{{6, 24}, {10, 28}, {17, 24}, {16, 30}}}, // 16 + {28, 24, 815, 0x1145d, [4]level{{6, 28}, {11, 28}, {16, 28}, {19, 28}}}, // 17 + {28, 26, 901, 0x12a17, [4]level{{6, 30}, {13, 26}, {18, 28}, {21, 28}}}, // 18 + {28, 28, 991, 0x13532, [4]level{{7, 28}, {14, 26}, {21, 26}, {25, 26}}}, // 19 + {32, 28, 1085, 0x149a6, [4]level{{8, 28}, {16, 26}, {20, 30}, {25, 28}}}, // 20 + {26, 22, 1156, 0x15683, [4]level{{8, 28}, {17, 26}, {23, 28}, {25, 30}}}, // 21 + {24, 24, 1258, 0x168c9, [4]level{{9, 28}, {17, 28}, {23, 30}, {34, 24}}}, // 22 + {28, 24, 1364, 0x177ec, [4]level{{9, 30}, {18, 28}, {25, 30}, {30, 30}}}, // 23 + {26, 26, 1474, 0x18ec4, [4]level{{10, 30}, {20, 28}, {27, 30}, {32, 30}}}, // 24 + {30, 26, 1588, 0x191e1, [4]level{{12, 26}, {21, 28}, {29, 30}, {35, 30}}}, // 25 + {28, 28, 1706, 0x1afab, [4]level{{12, 28}, {23, 28}, {34, 28}, {37, 30}}}, // 26 + {32, 28, 1828, 0x1b08e, [4]level{{12, 30}, {25, 28}, {34, 30}, {40, 30}}}, // 27 + {24, 24, 1921, 0x1cc1a, [4]level{{13, 30}, {26, 28}, {35, 30}, {42, 30}}}, // 28 + {28, 24, 2051, 0x1d33f, [4]level{{14, 30}, {28, 28}, {38, 30}, {45, 30}}}, // 29 + {24, 26, 2185, 0x1ed75, [4]level{{15, 30}, {29, 28}, {40, 30}, {48, 30}}}, // 30 + {28, 26, 2323, 0x1f250, [4]level{{16, 30}, {31, 28}, {43, 30}, {51, 30}}}, // 31 + {32, 26, 2465, 0x209d5, [4]level{{17, 30}, {33, 28}, {45, 30}, {54, 30}}}, // 32 + {28, 28, 2611, 0x216f0, [4]level{{18, 30}, {35, 28}, {48, 30}, {57, 30}}}, // 33 + {32, 28, 2761, 0x228ba, [4]level{{19, 30}, {37, 28}, {51, 30}, {60, 30}}}, // 34 + {28, 24, 2876, 0x2379f, [4]level{{19, 30}, {38, 28}, {53, 30}, {63, 30}}}, // 35 + {22, 26, 3034, 0x24b0b, [4]level{{20, 30}, {40, 28}, {56, 30}, {66, 30}}}, // 36 + {26, 26, 3196, 0x2542e, [4]level{{21, 30}, {43, 28}, {59, 30}, {70, 30}}}, // 37 + {30, 26, 3362, 0x26a64, [4]level{{22, 30}, {45, 28}, {62, 30}, {74, 30}}}, // 38 + {24, 28, 3532, 0x27541, [4]level{{24, 30}, {47, 28}, {65, 30}, {77, 30}}}, // 39 + {28, 28, 3706, 0x28c69, [4]level{{25, 30}, {49, 28}, {68, 30}, {81, 30}}}, // 40 +} + +func grid(siz int) [][]Pixel { + m := make([][]Pixel, siz) + pix := make([]Pixel, siz*siz) + for i := range m { + m[i], pix = pix[:siz], pix[siz:] + } + return m +} + +// vplan creates a Plan for the given version. +func vplan(v Version) (*Plan, error) { + p := &Plan{Version: v} + if v < 1 || v > 40 { + return nil, fmt.Errorf("invalid QR version %d", int(v)) + } + siz := 17 + int(v)*4 + m := grid(siz) + p.Pixel = m + + // Timing markers (overwritten by boxes). + const ti = 6 // timing is in row/column 6 (counting from 0) + for i := range m { + p := Timing.Pixel() + if i&1 == 0 { + p |= Black + } + m[i][ti] = p + m[ti][i] = p + } + + // Position boxes. + posBox(m, 0, 0) + posBox(m, siz-7, 0) + posBox(m, 0, siz-7) + + // Alignment boxes. + info := &vtab[v] + for x := 4; x+5 < siz; { + for y := 4; y+5 < siz; { + // don't overwrite timing markers + if (x < 7 && y < 7) || (x < 7 && y+5 >= siz-7) || (x+5 >= siz-7 && y < 7) { + } else { + alignBox(m, x, y) + } + if y == 4 { + y = info.apos + } else { + y += info.astride + } + } + if x == 4 { + x = info.apos + } else { + x += info.astride + } + } + + // Version pattern. + pat := vtab[v].pattern + if pat != 0 { + v := pat + for x := 0; x < 6; x++ { + for y := 0; y < 3; y++ { + p := PVersion.Pixel() + if v&1 != 0 { + p |= Black + } + m[siz-11+y][x] = p + m[x][siz-11+y] = p + v >>= 1 + } + } + } + + // One lonely black pixel + m[siz-8][8] = Unused.Pixel() | Black + + return p, nil +} + +// fplan adds the format pixels +func fplan(l Level, m Mask, p *Plan) error { + // Format pixels. + fb := uint32(l^1) << 13 // level: L=01, M=00, Q=11, H=10 + fb |= uint32(m) << 10 // mask + const formatPoly = 0x537 + rem := fb + for i := 14; i >= 10; i-- { + if rem&(1<<uint(i)) != 0 { + rem ^= formatPoly << uint(i-10) + } + } + fb |= rem + invert := uint32(0x5412) + siz := len(p.Pixel) + for i := uint(0); i < 15; i++ { + pix := Format.Pixel() + OffsetPixel(i) + if (fb>>i)&1 == 1 { + pix |= Black + } + if (invert>>i)&1 == 1 { + pix ^= Invert | Black + } + // top left + switch { + case i < 6: + p.Pixel[i][8] = pix + case i < 8: + p.Pixel[i+1][8] = pix + case i < 9: + p.Pixel[8][7] = pix + default: + p.Pixel[8][14-i] = pix + } + // bottom right + switch { + case i < 8: + p.Pixel[8][siz-1-int(i)] = pix + default: + p.Pixel[siz-1-int(14-i)][8] = pix + } + } + return nil +} + +// lplan edits a version-only Plan to add information +// about the error correction levels. +func lplan(v Version, l Level, p *Plan) error { + p.Level = l + + nblock := vtab[v].level[l].nblock + ne := vtab[v].level[l].check + nde := (vtab[v].bytes - ne*nblock) / nblock + extra := (vtab[v].bytes - ne*nblock) % nblock + dataBits := (nde*nblock + extra) * 8 + checkBits := ne * nblock * 8 + + p.DataBytes = vtab[v].bytes - ne*nblock + p.CheckBytes = ne * nblock + p.Blocks = nblock + + // Make data + checksum pixels. + data := make([]Pixel, dataBits) + for i := range data { + data[i] = Data.Pixel() | OffsetPixel(uint(i)) + } + check := make([]Pixel, checkBits) + for i := range check { + check[i] = Check.Pixel() | OffsetPixel(uint(i+dataBits)) + } + + // Split into blocks. + dataList := make([][]Pixel, nblock) + checkList := make([][]Pixel, nblock) + for i := 0; i < nblock; i++ { + // The last few blocks have an extra data byte (8 pixels). + nd := nde + if i >= nblock-extra { + nd++ + } + dataList[i], data = data[0:nd*8], data[nd*8:] + checkList[i], check = check[0:ne*8], check[ne*8:] + } + if len(data) != 0 || len(check) != 0 { + panic("data/check math") + } + + // Build up bit sequence, taking first byte of each block, + // then second byte, and so on. Then checksums. + bits := make([]Pixel, dataBits+checkBits) + dst := bits + for i := 0; i < nde+1; i++ { + for _, b := range dataList { + if i*8 < len(b) { + copy(dst, b[i*8:(i+1)*8]) + dst = dst[8:] + } + } + } + for i := 0; i < ne; i++ { + for _, b := range checkList { + if i*8 < len(b) { + copy(dst, b[i*8:(i+1)*8]) + dst = dst[8:] + } + } + } + if len(dst) != 0 { + panic("dst math") + } + + // Sweep up pair of columns, + // then down, assigning to right then left pixel. + // Repeat. + // See Figure 2 of http://www.pclviewer.com/rs2/qrtopology.htm + siz := len(p.Pixel) + rem := make([]Pixel, 7) + for i := range rem { + rem[i] = Extra.Pixel() + } + src := append(bits, rem...) + for x := siz; x > 0; { + for y := siz - 1; y >= 0; y-- { + if p.Pixel[y][x-1].Role() == 0 { + p.Pixel[y][x-1], src = src[0], src[1:] + } + if p.Pixel[y][x-2].Role() == 0 { + p.Pixel[y][x-2], src = src[0], src[1:] + } + } + x -= 2 + if x == 7 { // vertical timing strip + x-- + } + for y := 0; y < siz; y++ { + if p.Pixel[y][x-1].Role() == 0 { + p.Pixel[y][x-1], src = src[0], src[1:] + } + if p.Pixel[y][x-2].Role() == 0 { + p.Pixel[y][x-2], src = src[0], src[1:] + } + } + x -= 2 + } + return nil +} + +// mplan edits a version+level-only Plan to add the mask. +func mplan(m Mask, p *Plan) error { + p.Mask = m + for y, row := range p.Pixel { + for x, pix := range row { + if r := pix.Role(); (r == Data || r == Check || r == Extra) && p.Mask.Invert(y, x) { + row[x] ^= Black | Invert + } + } + } + return nil +} + +// posBox draws a position (large) box at upper left x, y. +func posBox(m [][]Pixel, x, y int) { + pos := Position.Pixel() + // box + for dy := 0; dy < 7; dy++ { + for dx := 0; dx < 7; dx++ { + p := pos + if dx == 0 || dx == 6 || dy == 0 || dy == 6 || 2 <= dx && dx <= 4 && 2 <= dy && dy <= 4 { + p |= Black + } + m[y+dy][x+dx] = p + } + } + // white border + for dy := -1; dy < 8; dy++ { + if 0 <= y+dy && y+dy < len(m) { + if x > 0 { + m[y+dy][x-1] = pos + } + if x+7 < len(m) { + m[y+dy][x+7] = pos + } + } + } + for dx := -1; dx < 8; dx++ { + if 0 <= x+dx && x+dx < len(m) { + if y > 0 { + m[y-1][x+dx] = pos + } + if y+7 < len(m) { + m[y+7][x+dx] = pos + } + } + } +} + +// alignBox draw an alignment (small) box at upper left x, y. +func alignBox(m [][]Pixel, x, y int) { + // box + align := Alignment.Pixel() + for dy := 0; dy < 5; dy++ { + for dx := 0; dx < 5; dx++ { + p := align + if dx == 0 || dx == 4 || dy == 0 || dy == 4 || dx == 2 && dy == 2 { + p |= Black + } + m[y+dy][x+dx] = p + } + } +} diff --git a/Godeps/_workspace/src/github.com/mattermost/rsc/qr/coding/qr_test.go b/Godeps/_workspace/src/github.com/mattermost/rsc/qr/coding/qr_test.go new file mode 100644 index 000000000..b8199bb51 --- /dev/null +++ b/Godeps/_workspace/src/github.com/mattermost/rsc/qr/coding/qr_test.go @@ -0,0 +1,133 @@ +// Copyright 2011 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package coding + +import ( + "bytes" + "testing" + + "github.com/mattermost/rsc/gf256" + "github.com/mattermost/rsc/qr/libqrencode" +) + +func test(t *testing.T, v Version, l Level, text ...Encoding) bool { + s := "" + ty := libqrencode.EightBit + switch x := text[0].(type) { + case String: + s = string(x) + case Alpha: + s = string(x) + ty = libqrencode.Alphanumeric + case Num: + s = string(x) + ty = libqrencode.Numeric + } + key, err := libqrencode.Encode(libqrencode.Version(v), libqrencode.Level(l), ty, s) + if err != nil { + t.Errorf("libqrencode.Encode(%v, %v, %d, %#q): %v", v, l, ty, s, err) + return false + } + mask := (^key.Pixel[8][2]&1)<<2 | (key.Pixel[8][3]&1)<<1 | (^key.Pixel[8][4] & 1) + p, err := NewPlan(v, l, Mask(mask)) + if err != nil { + t.Errorf("NewPlan(%v, L, %d): %v", v, err, mask) + return false + } + if len(p.Pixel) != len(key.Pixel) { + t.Errorf("%v: NewPlan uses %dx%d, libqrencode uses %dx%d", v, len(p.Pixel), len(p.Pixel), len(key.Pixel), len(key.Pixel)) + return false + } + c, err := p.Encode(text...) + if err != nil { + t.Errorf("Encode: %v", err) + return false + } + badpix := 0 +Pixel: + for y, prow := range p.Pixel { + for x, pix := range prow { + pix &^= Black + if c.Black(x, y) { + pix |= Black + } + + keypix := key.Pixel[y][x] + want := Pixel(0) + switch { + case keypix&libqrencode.Finder != 0: + want = Position.Pixel() + case keypix&libqrencode.Alignment != 0: + want = Alignment.Pixel() + case keypix&libqrencode.Timing != 0: + want = Timing.Pixel() + case keypix&libqrencode.Format != 0: + want = Format.Pixel() + want |= OffsetPixel(pix.Offset()) // sic + want |= pix & Invert + case keypix&libqrencode.PVersion != 0: + want = PVersion.Pixel() + case keypix&libqrencode.DataECC != 0: + if pix.Role() == Check || pix.Role() == Extra { + want = pix.Role().Pixel() + } else { + want = Data.Pixel() + } + want |= OffsetPixel(pix.Offset()) + want |= pix & Invert + default: + want = Unused.Pixel() + } + if keypix&libqrencode.Black != 0 { + want |= Black + } + if pix != want { + t.Errorf("%v/%v: Pixel[%d][%d] = %v, want %v %#x", v, mask, y, x, pix, want, keypix) + if badpix++; badpix >= 100 { + t.Errorf("stopping after %d bad pixels", badpix) + break Pixel + } + } + } + } + return badpix == 0 +} + +var input = []Encoding{ + String("hello"), + Num("1"), + Num("12"), + Num("123"), + Alpha("AB"), + Alpha("ABC"), +} + +func TestVersion(t *testing.T) { + badvers := 0 +Version: + for v := Version(1); v <= 40; v++ { + for l := L; l <= H; l++ { + for _, in := range input { + if !test(t, v, l, in) { + if badvers++; badvers >= 10 { + t.Errorf("stopping after %d bad versions", badvers) + break Version + } + } + } + } + } +} + +func TestEncode(t *testing.T) { + data := []byte{0x10, 0x20, 0x0c, 0x56, 0x61, 0x80, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11, 0xec, 0x11} + check := []byte{0xa5, 0x24, 0xd4, 0xc1, 0xed, 0x36, 0xc7, 0x87, 0x2c, 0x55} + rs := gf256.NewRSEncoder(Field, len(check)) + out := make([]byte, len(check)) + rs.ECC(data, out) + if !bytes.Equal(out, check) { + t.Errorf("have %x want %x", out, check) + } +} |