Figure out how to encode RS

3 files changed, 66 insertions, 16 deletions

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