From 69b03a15eb048c05b31a5cc6128c27acc77c1dd5 Mon Sep 17 00:00:00 2001
From: Leo Howell <leo@lwh.jp>
Date: Tue, 15 Sep 2009 19:03:26 +0900
Subject: Figure out how to encode RS
---
lpg/libqr/code-create.c | 4 +--
lpg/libqr/rs-encode.c | 76 ++++++++++++++++++++++++++++++++++++++++---------
lpg/libqr/rs.h | 2 +-
3 files changed, 66 insertions(+), 16 deletions(-)
(limited to 'lpg/libqr')
diff --git a/lpg/libqr/code-create.c b/lpg/libqr/code-create.c
index 484dbe3..389dcd5 100644
--- a/lpg/libqr/code-create.c
+++ b/lpg/libqr/code-create.c
@@ -31,13 +31,13 @@ static int add_ecc(struct bitstream * bits, int format, enum qr_ec_level ec)
puts("Before ecc:");
x_dump(bits);
{
- const int g[10] = { 251, 67, 61, 118, 70, 64, 94, 32, 45 };
int rs_words = 10; /* 1-M */
struct bitstream * rs;
- rs = rs_generate_words(rs_words, g, bits);
+ rs = rs_generate_words(rs_words, bits);
puts("ecc part:");
x_dump(rs);
+ bitstream_destroy(rs);
}
return -1;
}
diff --git a/lpg/libqr/rs-encode.c b/lpg/libqr/rs-encode.c
index ec99c6b..ea54d77 100644
--- a/lpg/libqr/rs-encode.c
+++ b/lpg/libqr/rs-encode.c
@@ -3,11 +3,56 @@
#include "bitstream.h"
#include "rs.h"
-struct bitstream * rs_generate_words(int k, const int * coeff, struct bitstream * data)
+static unsigned int gf_mult(unsigned int a, unsigned int b)
+{
+ /* Reduce modulo x^8 + x^4 + x^3 + x^2 + 1
+ * using the peasant's algorithm
+ */
+ const unsigned int m = 0x11D;
+ unsigned int x = 0;
+ int i;
+
+ for (i = 0; i < 8; ++i) {
+ x ^= (b & 0x1) ? a : 0;
+ a = (a << 1) ^ ((a & 0x80) ? m : 0);
+ b >>= 1;
+ }
+
+ return x & 0xFF;
+}
+
+static unsigned int * make_generator(int k)
+{
+ unsigned int * g;
+ unsigned int a;
+ int i, j;
+
+ g = calloc(k, sizeof(*g));
+ if (!g)
+ return 0;
+
+ g[0] = 1; /* Start with g(x) = 1 */
+ a = 1; /* 2^0 = 1 */
+
+ for (i = 0; i < k; ++i) {
+ /* Multiply our poly g(x) by (x + 2^i) */
+ for (j = k - 1; j > 0; --j)
+ g[j] = gf_mult(g[j], a) ^ g[j-1];
+ g[0] = gf_mult(g[0], a);
+
+ a = gf_mult(a, 2);
+ }
+
+ return g;
+}
+
+struct bitstream * rs_generate_words(int n, struct bitstream * data)
{
struct bitstream * ec = 0;
unsigned int * b = 0;
- size_t n, i, dlen;
+ unsigned int * g;
+ size_t dlen;
+ int i, r;
dlen = bitstream_size(data);
assert(dlen % 8 == 0);
@@ -17,30 +62,35 @@ struct bitstream * rs_generate_words(int k, const int * coeff, struct bitstream
if (!ec)
return 0;
- if (bitstream_resize(ec, k * 8) != 0)
+ if (bitstream_resize(ec, n * 8) != 0)
goto fail;
- b = calloc(k, sizeof(*b));
+ b = calloc(n, sizeof(*b));
if (!b)
goto fail;
- /* First, prepare the registers (b) with data bits. Note that
- * the registers are in reverse of the normal order
- */
+ g = make_generator(n);
+ if (!g)
+ goto fail;
+
+ /* First, prepare the registers (b) with data bits */
bitstream_seek(data, 0);
- for (n = 0; n < dlen; ++n) {
- unsigned int x = b[0] + bitstream_read(data, 8);
- for (i = 0; i < k-1; ++i)
- b[i] = b[i+1] + coeff[(k-1) - i] * x;
- b[k-1] = coeff[0] * x;
+ for (i = 0; i < dlen; ++i) {
+ unsigned int x = b[n-1] ^ bitstream_read(data, 8);
+ for (r = n-1; r > 0; --r)
+ b[r] = b[r-1] ^ gf_mult(g[r], x);
+ b[0] = gf_mult(g[0], x);
}
/* Read off the registers */
- bitstream_pack(ec, b, k, 8);
+ for (r = 0; r < n; ++r)
+ bitstream_write(ec, b[(n-1)-r], 8);
+ free(g);
free(b);
return ec;
fail:
+ free(b);
bitstream_destroy(ec);
return 0;
}
diff --git a/lpg/libqr/rs.h b/lpg/libqr/rs.h
index 98e3aa0..48b1f01 100644
--- a/lpg/libqr/rs.h
+++ b/lpg/libqr/rs.h
@@ -3,7 +3,7 @@
#include "bitstream.h"
-struct bitstream * rs_generate_words(int k, const int * coeff, struct bitstream * data);
+struct bitstream * rs_generate_words(int n, struct bitstream * data);
#endif
--
cgit v1.2.3-70-g09d2