OSDN -- Develop and Download Open Source Software
  • R/O
  • SSH
  • HTTPS

reedsolomon: Commit


Commit MetaInfo

Revision33 (tree)
Time2009-08-03 23:13:12
Authorm-miyzaki

Log Message

Add Encoder/Decoder for Data Matrix Barcode.

QR-CODE

POLYNOMIAL: x8 + x4 + x3 + x2 + 1
G(x) = (x+a0)(x+a1)...

Data Matrix Barcode

POLYNOMIAL: x8 + x5 + x3 + x2 + 1
G(x) = (x+a1)(x+a2)...

Change Summary

Incremental Difference

--- src/jp/sourceforge/reedsolomon/GaloisDM.java (nonexistent)
+++ src/jp/sourceforge/reedsolomon/GaloisDM.java (revision 33)
@@ -0,0 +1,21 @@
1+package jp.sourceforge.reedsolomon;
2+
3+/**
4+ * Galois Field GF(2^8) for Data Matrix Barcode
5+ *
6+ * @author Masayuki Miyazaki
7+ * http://sourceforge.jp/projects/reedsolomon/
8+ */
9+public final class GaloisDM
10+ extends Galois {
11+ public static final int POLYNOMIAL = 0x2d; // x^8 + x^5 + x^3 + x^2 + 1
12+ private static final Galois instance = new GaloisDM();
13+
14+ private GaloisDM() {
15+ super(POLYNOMIAL, 1);
16+ }
17+
18+ public static Galois getInstance() {
19+ return instance;
20+ }
21+}
Added: svn:executable
## -0,0 +1 ##
+*
\ No newline at end of property
--- src/jp/sourceforge/reedsolomon/GaloisQR.java (nonexistent)
+++ src/jp/sourceforge/reedsolomon/GaloisQR.java (revision 33)
@@ -0,0 +1,21 @@
1+package jp.sourceforge.reedsolomon;
2+
3+/**
4+ * Galois Field GF(2^8) for QR-CODE
5+ *
6+ * @author Masayuki Miyazaki
7+ * http://sourceforge.jp/projects/reedsolomon/
8+ */
9+public final class GaloisQR
10+ extends Galois {
11+ public static final int POLYNOMIAL = 0x1d; // x^8 + x^4 + x^3 + x^2 + 1
12+ private static final Galois instance = new GaloisQR();
13+
14+ private GaloisQR() {
15+ super(POLYNOMIAL, 0);
16+ }
17+
18+ public static Galois getInstance() {
19+ return instance;
20+ }
21+}
Added: svn:executable
## -0,0 +1 ##
+*
\ No newline at end of property
--- src/jp/sourceforge/reedsolomon/RsEncode.java (revision 32)
+++ src/jp/sourceforge/reedsolomon/RsEncode.java (revision 33)
@@ -7,28 +7,26 @@
77 * http://sourceforge.jp/projects/reedsolomon/
88 */
99 public class RsEncode {
10- private static final Galois galois = Galois.getInstance();
10+ private final Galois galois;
1111 private int npar;
1212 private int[] encodeGx;
1313
14- public RsEncode(int npar) {
14+ public RsEncode(Galois galois, int npar) {
15+ this.galois = galois;
16+ this.npar = npar;
1517 if(npar <= 0 || npar >= 128) {
1618 throw new IllegalArgumentException("bad npar");
1719 }
18- this.npar = npar;
19- makeEncodeGx();
20+ encodeGx = galois.makeEncodeGx(npar);
2021 }
2122
22- private void makeEncodeGx() {
23- encodeGx = new int[npar];
24- encodeGx[npar - 1] = 1;
25- for(int kou = 0; kou < npar; kou++) {
26- int ex = galois.toExp(kou);
27- for(int i = 0; i < npar - 1; i++) {
28- encodeGx[i] = galois.mul(encodeGx[i], ex) ^ encodeGx[i + 1];
29- }
30- encodeGx[npar - 1] = galois.mul(encodeGx[npar - 1], ex);
23+ public RsEncode(int npar) {
24+ this.galois = GaloisQR.getInstance();
25+ this.npar = npar;
26+ if(npar <= 0 || npar >= 128) {
27+ throw new IllegalArgumentException("bad npar");
3128 }
29+ encodeGx = galois.makeEncodeGx(npar);
3230 }
3331
3432 public int encode(int[] data, int length, int[] parity, int parityStartPos) {
--- src/jp/sourceforge/reedsolomon/RsDecode.java (revision 32)
+++ src/jp/sourceforge/reedsolomon/RsDecode.java (revision 33)
@@ -8,14 +8,23 @@
88 */
99 public class RsDecode {
1010 public static final int RS_CORRECT_ERROR = -2;
11- private static final Galois galois = Galois.getInstance();
11+ private Galois galois = GaloisQR.getInstance();
1212 private int npar;
1313
14+ public RsDecode(Galois galois, int npar) {
15+ this.galois = galois;
16+ this.npar = npar;
17+ if(npar <= 0 || npar >= 128) {
18+ throw new IllegalArgumentException("bad npar");
19+ }
20+ }
21+
1422 public RsDecode(int npar) {
23+ this.galois = GaloisQR.getInstance();
24+ this.npar = npar;
1525 if(npar <= 0 || npar >= 128) {
1626 throw new IllegalArgumentException("bad npar");
1727 }
18- this.npar = npar;
1928 }
2029
2130 /**
@@ -99,8 +108,7 @@
99108 return pos;
100109 }
101110 int posIdx = jisu - 1;
102- for(int i = 0; i < length; i++) {
103- final int z = 255 - i;
111+ for(int i = 0, z = 255; i < length; i++, z--) {
104112 int wz = z;
105113 int wk = 1;
106114 for(int j = 1; j <= jisu; j++) {
@@ -137,24 +145,10 @@
137145 * @param omega int[]
138146 */
139147 private void doForney(int[] data, int length, int[] pos, int[] sigma, int[] omega) {
140- final int jisu = sigma.length - 1;
141148 for(int ps: pos) {
142149 final int zlog = 255 - galois.toLog(ps);
143- int wz = zlog;
144- int ov = omega[0];
145- for(int i = 1; i < jisu; i++) {
146- ov ^= galois.mulExp(omega[i], wz);
147- wz = (wz + zlog) % 255;
148- }
149-
150- final int zlog2 = (zlog * 2) % 255;
151- wz = zlog2;
152- int dv = sigma[1];
153- for(int i = 3; i <= jisu; i += 2) {
154- dv ^= galois.mulExp(sigma[i], wz);
155- wz = (wz + zlog2) % 255;
156- }
157-
150+ int ov = galois.calcOmegaValue(omega, zlog);
151+ int dv = galois.calcSigmaDashValue(sigma, zlog);
158152 data[galois.toPos(length, ps)] ^= galois.mul(ps, galois.div(ov, dv));
159153 }
160154 }
@@ -214,20 +208,43 @@
214208
215209 /*
216210 public static void main(String[] args) {
217- int[] data = new int[] {
218- 32, 65, 205, 69, 41, 220, 46, 128, 236,
219- 42, 159, 74, 221, 244, 169, 239, 150, 138, 70, 237, 85, 224, 96, 74, 219, 61
220- };
211+ final int[] ref = new int[] {32, 65, 205, 69, 41, 220, 46, 128, 236};
212+
213+ // Encoding QR-CODE
214+ int[] qrData = new int[ref.length + 17];
215+ System.arraycopy(ref, 0, qrData, 0, ref.length);
216+ RsEncode enc = new RsEncode(17);
217+ enc.encode(qrData);
218+ System.out.println("qrData=" + java.util.Arrays.toString(qrData));
219+ // parity = 42, 159, 74, 221, 244, 169, 239, 150, 138, 70, 237, 85, 224, 96, 74, 219, 61
220+
221+ // force add errors
222+ qrData[0] ^= 0x55;
223+ qrData[1] ^= 0xaa;
224+
225+ // Decoding QR-CODE
221226 RsDecode dec = new RsDecode(17);
222- int r = dec.decode(data);
227+ int r = dec.decode(qrData);
223228 System.out.println("r=" + r);
224- for(int i = 0; i < 8; i++) {
225- data[i] ^= (int) (Math.random() * 256);
226- }
227- System.out.println(java.util.Arrays.toString(data));
228- r = dec.decode(data);
229+ System.out.println("qrData=" + java.util.Arrays.toString(qrData));
230+
231+ // Encoding Data Matrix Barcode
232+ int[] dmData = new int[ref.length + 17];
233+ System.arraycopy(ref, 0, dmData, 0, ref.length);
234+ RsEncode encDM = new RsEncode(GaloisDM.getInstance(), 17);
235+ encDM.encode(dmData);
236+ System.out.println("dmData=" + java.util.Arrays.toString(dmData));
237+ // parity = 41, 41, 15, 250, 121, 58, 190, 205, 164, 103, 63, 149, 42, 247, 1, 214, 148
238+
239+ // force add errors
240+ dmData[0] ^= 0x55;
241+ dmData[1] ^= 0xaa;
242+
243+ // Decoding Data Matrix Barcode
244+ RsDecode decDM = new RsDecode(GaloisDM.getInstance(), 17);
245+ r = decDM.decode(dmData);
229246 System.out.println("r=" + r);
230- System.out.println(java.util.Arrays.toString(data));
247+ System.out.println("dmData=" + java.util.Arrays.toString(dmData));
231248 }
232249 */
233250 }
--- src/jp/sourceforge/reedsolomon/Galois.java (revision 32)
+++ src/jp/sourceforge/reedsolomon/Galois.java (revision 33)
@@ -6,20 +6,18 @@
66 * @author Masayuki Miyazaki
77 * http://sourceforge.jp/projects/reedsolomon/
88 */
9-public final class Galois {
10- public static final int POLYNOMIAL = 0x1d;
11- private static final Galois instance = new Galois();
9+public class Galois {
10+ private final int polynomial;
11+ private final int symStart;
1212 private int[] expTbl = new int[255 * 2];
1313 private int[] logTbl = new int[255 + 1];
1414
15- private Galois() {
15+ protected Galois(int polynomial, int symStart) {
16+ this.polynomial = polynomial;
17+ this.symStart = symStart;
1618 initGaloisTable();
1719 }
1820
19- public static Galois getInstance() {
20- return instance;
21- }
22-
2321 private void initGaloisTable() {
2422 int d = 1;
2523 for(int i = 0; i < 255; i++) {
@@ -27,7 +25,7 @@
2725 logTbl[d] = i;
2826 d <<= 1;
2927 if((d & 0x100) != 0) {
30- d = (d ^ POLYNOMIAL) & 0xff;
28+ d = (d ^ polynomial) & 0xff;
3129 }
3230 }
3331 }
@@ -83,11 +81,11 @@
8381
8482 public boolean calcSyndrome(int[] data, int length, int[] syn) {
8583 int hasErr = 0;
86- for(int i = 0; i < syn.length; i++) {
84+ for(int i = 0, s = symStart; i < syn.length; i++, s++) {
8785 int wk = 0;
8886 for(int idx = 0; idx < length; idx++) {
8987 if(wk != 0) {
90- wk = expTbl[logTbl[wk] + i];
88+ wk = expTbl[logTbl[wk] + s];
9189 }
9290 wk ^= data[idx];
9391 }
@@ -96,4 +94,42 @@
9694 }
9795 return hasErr == 0;
9896 }
97+
98+ public int[] makeEncodeGx(int npar) {
99+ int[] encodeGx = new int[npar];
100+ encodeGx[npar - 1] = 1;
101+ for(int i = 0, kou = symStart; i < npar; i++, kou++) {
102+ int ex = toExp(kou);
103+ for(int j = 0; j < npar - 1; j++) {
104+ encodeGx[j] = mul(encodeGx[j], ex) ^ encodeGx[j + 1];
105+ }
106+ encodeGx[npar - 1] = mul(encodeGx[npar - 1], ex);
107+ }
108+ return encodeGx;
109+ }
110+
111+ public int calcOmegaValue(int[] omega, int zlog) {
112+ int wz = zlog;
113+ int ov = omega[0];
114+ for(int i = 1; i < omega.length; i++) {
115+ ov ^= mulExp(omega[i], wz);
116+ wz = (wz + zlog) % 255;
117+ }
118+ if(symStart != 0) {
119+ ov = mulExp(ov, (zlog * symStart) % 255);
120+ }
121+ return ov;
122+ }
123+
124+ public int calcSigmaDashValue(int[] sigma, int zlog) {
125+ final int jisu = sigma.length - 1;
126+ final int zlog2 = (zlog * 2) % 255;
127+ int wz = zlog2;
128+ int dv = sigma[1];
129+ for(int i = 3; i <= jisu; i += 2) {
130+ dv ^= mulExp(sigma[i], wz);
131+ wz = (wz + zlog2) % 255;
132+ }
133+ return dv;
134+ }
99135 }
Show on old repository browser