diff options
| -rw-r--r-- | lpg/libqr/code-create.c | 4 | ||||
| -rw-r--r-- | lpg/libqr/rs-encode.c | 76 | ||||
| -rw-r--r-- | lpg/libqr/rs.h | 2 |
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 |