reed_solomon.go (2331B)
1 // go-qrcode 2 // Copyright 2014 Tom Harwood 3 4 // Package reedsolomon provides error correction encoding for QR Code 2005. 5 // 6 // QR Code 2005 uses a Reed-Solomon error correcting code to detect and correct 7 // errors encountered during decoding. 8 // 9 // The generated RS codes are systematic, and consist of the input data with 10 // error correction bytes appended. 11 package reedsolomon 12 13 import ( 14 "log" 15 16 bitset "github.com/skip2/go-qrcode/bitset" 17 ) 18 19 // Encode data for QR Code 2005 using the appropriate Reed-Solomon code. 20 // 21 // numECBytes is the number of error correction bytes to append, and is 22 // determined by the target QR Code's version and error correction level. 23 // 24 // ISO/IEC 18004 table 9 specifies the numECBytes required. e.g. a 1-L code has 25 // numECBytes=7. 26 func Encode(data *bitset.Bitset, numECBytes int) *bitset.Bitset { 27 // Create a polynomial representing |data|. 28 // 29 // The bytes are interpreted as the sequence of coefficients of a polynomial. 30 // The last byte's value becomes the x^0 coefficient, the second to last 31 // becomes the x^1 coefficient and so on. 32 ecpoly := newGFPolyFromData(data) 33 ecpoly = gfPolyMultiply(ecpoly, newGFPolyMonomial(gfOne, numECBytes)) 34 35 // Pick the generator polynomial. 36 generator := rsGeneratorPoly(numECBytes) 37 38 // Generate the error correction bytes. 39 remainder := gfPolyRemainder(ecpoly, generator) 40 41 // Combine the data & error correcting bytes. 42 // The mathematically correct answer is: 43 // 44 // result := gfPolyAdd(ecpoly, remainder). 45 // 46 // The encoding used by QR Code 2005 is slightly different this result: To 47 // preserve the original |data| bit sequence exactly, the data and remainder 48 // are combined manually below. This ensures any most significant zero bits 49 // are preserved (and not optimised away). 50 result := bitset.Clone(data) 51 result.AppendBytes(remainder.data(numECBytes)) 52 53 return result 54 } 55 56 // rsGeneratorPoly returns the Reed-Solomon generator polynomial with |degree|. 57 // 58 // The generator polynomial is calculated as: 59 // (x + a^0)(x + a^1)...(x + a^degree-1) 60 func rsGeneratorPoly(degree int) gfPoly { 61 if degree < 2 { 62 log.Panic("degree < 2") 63 } 64 65 generator := gfPoly{term: []gfElement{1}} 66 67 for i := 0; i < degree; i++ { 68 nextPoly := gfPoly{term: []gfElement{gfExpTable[i], 1}} 69 generator = gfPolyMultiply(generator, nextPoly) 70 } 71 72 return generator 73 }