Merge some files

26 files changed, 396 insertions, 435 deletions

diff --git a/lpg/libqr/Makefile b/lpg/libqr/Makefile
index 3a6af6f..a82372f 100644
--- a/lpg/libqr/Makefile
+++ b/lpg/libqr/Makefile
@@ -1,4 +1,6 @@
-OBJECTS :=      capacity.o              \
+OBJECTS :=      bitmap.o                \
+                bitstream.o             \
+                constants.o             \
                 code-common.o           \
                 code-create.o           \
                 code-layout.o           \
@@ -6,11 +8,7 @@ OBJECTS :=      capacity.o              \
                 data-common.o           \
                 data-create.o           \
                 data-parse.o            \
-                qr-bitmap.o             \
-                qr-bitmap-render.o      \
-                qr-bitstream.o          \
-                qr-mask.o               \
-                rs-encode.o
+                galois.o
 
 CFLAGS := -std=c89 -pedantic -I. -Wall
 CFLAGS += -g
diff --git a/lpg/libqr/TODO b/lpg/libqr/TODO
index 219ca83..3cd0583 100644
--- a/lpg/libqr/TODO
+++ b/lpg/libqr/TODO
@@ -1,4 +1,3 @@
-* Merge some files
 * Fix XXX, TODO
 * Tidy code
 * RELEASE v0.1
diff --git a/lpg/libqr/qr-bitmap-render.c b/lpg/libqr/bitmap.c
index 197e947..3394784 100644
--- a/lpg/libqr/qr-bitmap-render.c
+++ b/lpg/libqr/bitmap.c
@@ -1,9 +1,93 @@
-#include <string.h>
-#include <limits.h>
 #include <assert.h>
+#include <limits.h>
+#include <stdlib.h>
+#include <string.h>
 
 #include <qr/bitmap.h>
 
+struct qr_bitmap * qr_bitmap_create(int width, int height, int masked)
+{
+        struct qr_bitmap * out;
+        size_t size;
+
+        out = malloc(sizeof(*out));
+        if (!out)
+                goto fail;
+
+        out->width = width;
+        out->height = height;
+        out->stride = (width / CHAR_BIT) + (width % CHAR_BIT ? 1 : 0);
+
+        size = out->stride * height;
+
+        out->mask = 0;
+        out->bits = malloc(size);
+        if (!out->bits)
+                goto fail;
+        memset(out->bits, 0, size);
+
+        if (masked) {
+                out->mask = malloc(out->stride * width);
+                if (!out->mask)
+                        goto fail;
+                memset(out->mask, 0xFF, size);
+        }
+
+        return out;
+
+fail:
+        qr_bitmap_destroy(out);
+        return 0;
+}
+
+void qr_bitmap_destroy(struct qr_bitmap * bmp)
+{
+        if (bmp) {
+                free(bmp->bits);
+                free(bmp->mask);
+                free(bmp);
+        }
+}
+
+struct qr_bitmap * qr_bitmap_clone(const struct qr_bitmap * src)
+{
+        struct qr_bitmap * bmp;
+        size_t size;
+
+        bmp = qr_bitmap_create(src->width, src->height, !!src->mask);
+        if (!bmp)
+                return 0;
+
+        assert(bmp->stride == src->stride);
+
+        size = bmp->width * bmp->stride;
+        memcpy(bmp->bits, src->bits, size);
+        if (bmp->mask)
+                memcpy(bmp->mask, src->mask, size);
+
+        return bmp;
+}
+
+void qr_bitmap_merge(struct qr_bitmap * dest, const struct qr_bitmap * src)
+{
+        unsigned char * d, * s, * m;
+        size_t n;
+
+        assert(dest->stride == src->stride);
+        assert(dest->height == src->height);
+        assert(src->mask);
+
+        n = dest->stride * dest->height;
+        d = dest->bits;
+        s = src->bits;
+        m = src->mask;
+
+        while (n--) {
+                *d   &= ~*m;
+                *d++ |= *s++ & *m++;
+        }
+}
+
 /* CHAR_BIT | mod_bits  (multi-byte) */
 static void render_line_1(unsigned char *       out,
                           const unsigned char * in,
diff --git a/lpg/libqr/qr-bitstream.c b/lpg/libqr/bitstream.c
index c752cde..cf5a9d4 100644
--- a/lpg/libqr/qr-bitstream.c
+++ b/lpg/libqr/bitstream.c
@@ -10,7 +10,7 @@
 #include <limits.h>
 #include <assert.h>
 
-#include "qr-bitstream.h"
+#include <qr/bitstream.h>
 
 #define MAX(a, b) ((a) < (b) ? (b) : (a))
 #define MIN(a, b) ((a) > (b) ? (b) : (a))
diff --git a/lpg/libqr/capacity.c b/lpg/libqr/capacity.c
deleted file mode 100644
index 4b513af..0000000
--- a/lpg/libqr/capacity.c
+++ /dev/null
@@ -1,88 +0,0 @@
-/* FIXME: don't like big tables of data */
-
-const int QR_DATA_WORD_COUNT[40][4] = {
-          19,   16,   13,    9,
-          34,   28,   22,   16,
-          55,   44,   34,   26,
-          80,   64,   48,   36,
-         108,   86,   62,   46,
-         136,  108,   76,   60,
-         156,  124,   88,   66,
-         194,  154,  110,   86,
-         232,  182,  132,  100,
-         274,  216,  154,  122,
-         324,  254,  180,  140,
-         370,  290,  206,  158,
-         428,  334,  244,  180,
-         461,  365,  261,  197,
-         523,  415,  295,  223,
-         589,  453,  325,  253,
-         647,  507,  367,  283,
-         721,  563,  397,  313,
-         795,  627,  445,  341,
-         861,  669,  485,  385,
-         932,  714,  512,  406,
-        1006,  782,  568,  442,
-        1094,  860,  614,  464,
-        1174,  914,  664,  514,
-        1276, 1000,  718,  538,
-        1370, 1062,  754,  596,
-        1468, 1128,  808,  628,
-        1531, 1193,  871,  661,
-        1631, 1267,  911,  701,
-        1735, 1373,  985,  745,
-        1845, 1455, 1033,  793,
-        1955, 1541, 1115,  845,
-        2071, 1631, 1171,  901,
-        2191, 1725, 1231,  961,
-        2306, 1812, 1286,  986,
-        2434, 1914, 1351, 1054,
-        2566, 1992, 1426, 1096,
-        2812, 2216, 1582, 1222,
-        2956, 2334, 1666, 1276
-};
-
-/* I'm sure we can calculate these values */
-const int QR_RS_BLOCK_COUNT[40][4][2] = {
-         1,  0,  1,  0,  1,  0,  1,  0, /*  1 */
-         1,  0,  1,  0,  1,  0,  1,  0, /*  2 */
-         1,  0,  1,  0,  2,  0,  2,  0, /*  3 */
-         1,  0,  2,  0,  2,  0,  4,  0, /*  4 */
-         1,  0,  2,  0,  2,  0,  2,  0,
-         2,  0,  4,  0,  4,  0,  4,  0,
-         2,  0,  4,  0,  2,  4,  4,  1,
-         2,  0,  2,  2,  4,  2,  4,  2, /*  8 */
-         2,  0,  3,  2,  4,  4,  4,  4,
-         2,  2,  4,  1,  6,  2,  6,  2,
-         4,  0,  1,  4,  4,  4,  3,  8,
-         2,  2,  6,  2,  4,  6,  7,  4,
-         4,  0,  8,  1,  8,  4, 12,  4,
-         3,  1,  4,  5, 11,  5, 11,  5, /* 14 */
-         5,  1,  5,  5,  5,  7, 11,  7,
-         5,  1,  7,  3, 15,  2,  3, 13,
-         1,  5, 10,  1,  1, 15,  2, 17,
-         5,  1,  9,  4, 17,  1,  2, 19,
-         3,  4,  3, 11, 17,  4,  9, 16, /* 19 */
-         3,  5,  3, 13, 15,  5, 15, 10,
-         4,  4, 17,  0, 17,  6, 19,  6,
-         2,  7, 17,  0,  7, 16, 34,  0,
-         4,  5,  4, 14, 11, 14, 16, 14,
-         6,  4,  6, 14, 11, 16, 30,  2,
-         8,  4,  8, 13,  7, 22, 22, 13, /* 25 */
-        10,  2, 19,  4, 28,  6, 33,  4,
-         8,  4, 22,  3,  8, 26, 12, 28,
-         3, 10,  3, 23,  4, 31, 11, 31,
-         7,  7, 21,  7,  1, 37, 19, 26,
-         5, 10, 19, 10, 15, 25, 23, 25, /* 30 */
-        13,  3,  2, 29, 42,  1, 23, 28,
-        17,  0, 10, 23, 10, 35, 19, 35,
-        17,  1, 14, 21, 29, 19, 11, 46,
-        13,  6, 14, 23, 44,  7, 59,  1,
-        12,  7, 12, 26, 39, 14, 22, 41, /* 35 */
-         6, 14,  6, 34, 46, 10,  2, 64,
-        17,  4, 29, 14, 49, 10, 24, 46,
-         4, 18, 13, 32, 48, 14, 42, 32,
-        20,  4, 40,  7, 43, 22, 10, 67,
-        19,  6, 18, 31, 34, 34, 20, 61 /* 40 */
-};
-
diff --git a/lpg/libqr/code-common.c b/lpg/libqr/code-common.c
index 7c3c119..bc6621a 100644
--- a/lpg/libqr/code-common.c
+++ b/lpg/libqr/code-common.c
@@ -1,7 +1,10 @@
+#include <assert.h>
+#include <limits.h>
 #include <stdlib.h>
+
 #include <qr/code.h>
 #include <qr/bitmap.h>
-#include "code-common.h"
+#include <qr/bitstream.h>
 
 void qr_code_destroy(struct qr_code * code)
 {
@@ -16,7 +19,7 @@ int qr_code_width(const struct qr_code * code)
         return code->version * 4 + 17;
 }
 
-size_t code_total_capacity(int version)
+size_t qr_code_total_capacity(int version)
 {
 	int side = version * 4 + 17;
 
@@ -38,46 +41,44 @@ size_t code_total_capacity(int version)
 	return side * side - function_bits;
 }
 
-const int QR_ALIGNMENT_LOCATION[40][7] = {
-        {  0,  0,  0,  0,  0,  0,  0 }, /*  1 */
-        {  6, 18,  0,  0,  0,  0,  0 }, /*  2 */
-        {  6, 22,  0,  0,  0,  0,  0 }, /*  3 */
-        {  6, 26,  0,  0,  0,  0,  0 }, /*  4 */
-        {  6, 30,  0,  0,  0,  0,  0 }, /*  5 */
-        {  6, 34,  0,  0,  0,  0,  0 }, /*  6 */
-        {  6, 22, 38,  0,  0,  0,  0 }, /*  7 */
-        {  6, 24, 42,  0,  0,  0,  0 }, /*  8 */
-        {  6, 26, 46,  0,  0,  0,  0 }, /*  9 */
-        {  6, 28, 50,  0,  0,  0,  0 }, /* 10 */
-        {  6, 30, 54,  0,  0,  0,  0 }, /* 11 */
-        {  6, 32, 58,  0,  0,  0,  0 }, /* 12 */
-        {  6, 34, 62,  0,  0,  0,  0 }, /* 13 */
-        {  6, 26, 46, 66,  0,  0,  0 }, /* 14 */
-        {  6, 26, 48, 70,  0,  0,  0 }, /* 15 */
-        {  6, 26, 50, 74,  0,  0,  0 }, /* 16 */
-        {  6, 30, 54, 78,  0,  0,  0 }, /* 17 */
-        {  6, 30, 56, 82,  0,  0,  0 }, /* 18 */
-        {  6, 30, 58, 86,  0,  0,  0 }, /* 19 */
-        {  6, 34, 62, 90,  0,  0,  0 }, /* 20 */
-        {  6, 28, 50, 72, 94,  0,  0 }, /* 21 */
-        {  6, 26, 50, 74, 98,  0,  0 }, /* 22 */
-        {  6, 30, 54, 78,102,  0,  0 }, /* 23 */
-        {  6, 28, 54, 80,106,  0,  0 }, /* 24 */
-        {  6, 32, 58, 84,110,  0,  0 }, /* 25 */
-        {  6, 30, 58, 86,114,  0,  0 }, /* 26 */
-        {  6, 34, 62, 90,118,  0,  0 }, /* 27 */
-        {  6, 26, 50, 74, 98,122,  0 }, /* 28 */
-        {  6, 30, 54, 78,102,126,  0 }, /* 29 */
-        {  6, 26, 52, 78,104,130,  0 }, /* 30 */
-        {  6, 30, 56, 82,108,134,  0 }, /* 31 */
-        {  6, 34, 60, 86,112,138,  0 }, /* 32 */
-        {  6, 30, 58, 86,114,142,  0 }, /* 33 */
-        {  6, 34, 62, 90,118,146,  0 }, /* 34 */
-        {  6, 30, 54, 78,102,126,150 }, /* 35 */
-        {  6, 24, 50, 76,102,128,154 }, /* 36 */
-        {  6, 28, 54, 80,106,132,158 }, /* 37 */
-        {  6, 32, 58, 84,110,136,162 }, /* 38 */
-        {  6, 26, 54, 82,110,138,166 }, /* 39 */
-        {  6, 30, 58, 86,114,142,170 }, /* 40 */
-};
+struct qr_bitmap * qr_mask_apply(const struct qr_bitmap * orig,
+                                 unsigned int mask)
+{
+        struct qr_bitmap * bmp;
+        int i, j;
+
+        if (mask & ~0x7)
+                return 0;
+
+        bmp = qr_bitmap_clone(orig);
+        if (!bmp)
+                return 0;
+
+        /* Slow version for now; we can optimize later */
+
+        for (i = 0; i < bmp->height; ++i) {
+                unsigned char * p = bmp->bits + i * bmp->stride;
+
+                for (j = 0; j < bmp->width; ++j) {
+                        int bit = j % CHAR_BIT;
+                        size_t off = j / CHAR_BIT;
+                        int t;
+
+                        switch (mask) {
+                        case 0: t = (i + j) % 2; break;
+                        case 1: t = i % 2; break;
+                        case 2: t = j % 3; break;
+                        case 3: t = (i + j) % 3; break;
+                        case 4: t = (i/2 + j/3) % 2; break;
+                        case 5: t = ((i*j) % 2) + ((i*j) % 3); break;
+                        case 6: t = (((i*j) % 2) + ((i*j) % 3)) % 2; break;
+                        case 7: t = (((i*j) % 3) + ((i+j) % 2)) % 2; break;
+                        }
+
+                        p[off] ^= (t == 0) << bit;
+                }
+        }
+
+        return bmp;
+}
 
diff --git a/lpg/libqr/code-common.h b/lpg/libqr/code-common.h
deleted file mode 100644
index 9900e4e..0000000
--- a/lpg/libqr/code-common.h
+++ /dev/null
@@ -1,18 +0,0 @@
-#ifndef CODE_COMMON_H
-#define CODE_COMMON_H
-
-#include <qr/code.h>
-#include <qr/bitmap.h>
-#include "qr-bitstream.h"
-
-struct qr_code {
-        int                version;
-        struct qr_bitmap * modules;
-};
-
-size_t code_total_capacity(int version);
-
-extern const int QR_ALIGNMENT_LOCATION[40][7];
-
-#endif
-
diff --git a/lpg/libqr/code-create.c b/lpg/libqr/code-create.c
index f8ef7b9..0882b88 100644
--- a/lpg/libqr/code-create.c
+++ b/lpg/libqr/code-create.c
@@ -1,19 +1,17 @@
 #include <stdlib.h>
 #include <limits.h>
 #include <assert.h>
-#include <qr/code.h>
 
-#include "code-common.h"
-#include "code-layout.h"
-#include "data-common.h"
-#include "qr-mask.h"
-#include "rs.h"
+#include <qr/bitmap.h>
+#include <qr/bitstream.h>
+#include <qr/code.h>
+#include <qr/data.h>
+#include <qr/layout.h>
+#include "constants.h"
+#include "galois.h"
 
 #define MIN(a, b) ((b) < (a) ? (b) : (a))
 
-extern const int QR_DATA_WORD_COUNT[40][4];
-extern const int QR_RS_BLOCK_COUNT[40][4][2];
-
 static int mask_data(struct qr_code * code);
 static int score_mask(const struct qr_bitmap * bmp);
 static int score_runs(const struct qr_bitmap * bmp, int base);
@@ -28,11 +26,6 @@ static int draw_format(struct qr_bitmap * bmp,
                         int mask);
 static int calc_format_bits(enum qr_ec_level ec, int mask);
 static long calc_version_bits(int version);
-static unsigned long gal_residue(unsigned long a, unsigned long m);
-
-/* FIXME: the static functions should be in a better
- * order, with prototypes.
- */
 
 #include <stdio.h>
 static void x_dump(struct qr_bitstream * bits)
@@ -175,7 +168,7 @@ static struct qr_bitstream * make_data(int version,
                                        enum qr_ec_level   ec,
                                        struct qr_bitstream * data)
 {
-        const size_t total_bits = code_total_capacity(version);
+        const size_t total_bits = qr_code_total_capacity(version);
         const size_t total_words = total_bits / 8;
         const size_t total_data = QR_DATA_WORD_COUNT[version - 1][ec ^ 0x1];
         size_t total_blocks, block_count[2], data_words, rs_words;
@@ -575,7 +568,7 @@ static int calc_format_bits(enum qr_ec_level ec, int mask)
          */
 
         bits <<= 15 - 5;
-        bits |= (unsigned int)gal_residue(bits, 0x537);
+        bits |= (unsigned int)gf_residue(bits, 0x537);
 
         /* XOR mask: 101 0100 0001 0010 */
         bits ^= 0x5412;
@@ -593,37 +586,8 @@ static long calc_version_bits(int version)
          *   G(x) = x^12 + x^11 + x^10 + x^9 + x^8 + x^5 + x^2 + 1
          */
         bits <<= 18 - 6;
-        bits |= gal_residue(bits, 0x1F25);
+        bits |= gf_residue(bits, 0x1F25);
 
         return bits;
 }
 
-/* Calculate the residue of a modulo m */
-static unsigned long gal_residue(unsigned long a,
-                                   unsigned long m)
-{
-        unsigned long o = 1;
-        int n = 1;
-
-        /* Find one past the highest bit of the modulus */
-        while (m & ~(o - 1))
-                o <<= 1;
-
-        /* Find the highest n such that O(m * x^n) <= O(a) */
-        while (a & ~(o - 1)) {
-                o <<= 1;
-                ++n;
-        }
-
-        /* For each n, try to reduce a by (m * x^n) */
-        while (n--) {
-                o >>= 1;
-
-                /* o is the highest bit of (m * x^n) */
-                if (a & o)
-                        a ^= m << n;
-        }
-
-        return a;
-}
-
diff --git a/lpg/libqr/code-layout.c b/lpg/libqr/code-layout.c
index 2a90124..68a1a0e 100644
--- a/lpg/libqr/code-layout.c
+++ b/lpg/libqr/code-layout.c
@@ -2,9 +2,11 @@
 #include <limits.h>
 #include <stdlib.h>
 #include <string.h>
+
 #include <qr/bitmap.h>
-#include "code-common.h"
-#include "code-layout.h"
+#include <qr/code.h>
+#include <qr/layout.h>
+#include "constants.h"
 
 struct qr_iterator {
         struct qr_code * code;
diff --git a/lpg/libqr/code-parse.c b/lpg/libqr/code-parse.c
index 0d3a71d..a794cdc 100644
--- a/lpg/libqr/code-parse.c
+++ b/lpg/libqr/code-parse.c
@@ -1,7 +1,5 @@
 #include <qr/code.h>
 
-#include "code-common.h"
-
 struct qr_code * qr_code_parse(const void * buffer,
                                size_t       line_bits,
                                size_t       line_stride,
diff --git a/lpg/libqr/constants.c b/lpg/libqr/constants.c
new file mode 100644
index 0000000..86f08ff
--- /dev/null
+++ b/lpg/libqr/constants.c
@@ -0,0 +1,151 @@
+#include "constants.h"
+
+/* FIXME: don't like big tables of data */
+
+const int QR_ALIGNMENT_LOCATION[40][7] = {
+        {  0,  0,  0,  0,  0,  0,  0 }, /*  1 */
+        {  6, 18,  0,  0,  0,  0,  0 }, /*  2 */
+        {  6, 22,  0,  0,  0,  0,  0 }, /*  3 */
+        {  6, 26,  0,  0,  0,  0,  0 }, /*  4 */
+        {  6, 30,  0,  0,  0,  0,  0 }, /*  5 */
+        {  6, 34,  0,  0,  0,  0,  0 }, /*  6 */
+        {  6, 22, 38,  0,  0,  0,  0 }, /*  7 */
+        {  6, 24, 42,  0,  0,  0,  0 }, /*  8 */
+        {  6, 26, 46,  0,  0,  0,  0 }, /*  9 */
+        {  6, 28, 50,  0,  0,  0,  0 }, /* 10 */
+        {  6, 30, 54,  0,  0,  0,  0 }, /* 11 */
+        {  6, 32, 58,  0,  0,  0,  0 }, /* 12 */
+        {  6, 34, 62,  0,  0,  0,  0 }, /* 13 */
+        {  6, 26, 46, 66,  0,  0,  0 }, /* 14 */
+        {  6, 26, 48, 70,  0,  0,  0 }, /* 15 */
+        {  6, 26, 50, 74,  0,  0,  0 }, /* 16 */
+        {  6, 30, 54, 78,  0,  0,  0 }, /* 17 */
+        {  6, 30, 56, 82,  0,  0,  0 }, /* 18 */
+        {  6, 30, 58, 86,  0,  0,  0 }, /* 19 */
+        {  6, 34, 62, 90,  0,  0,  0 }, /* 20 */
+        {  6, 28, 50, 72, 94,  0,  0 }, /* 21 */
+        {  6, 26, 50, 74, 98,  0,  0 }, /* 22 */
+        {  6, 30, 54, 78,102,  0,  0 }, /* 23 */
+        {  6, 28, 54, 80,106,  0,  0 }, /* 24 */
+        {  6, 32, 58, 84,110,  0,  0 }, /* 25 */
+        {  6, 30, 58, 86,114,  0,  0 }, /* 26 */
+        {  6, 34, 62, 90,118,  0,  0 }, /* 27 */
+        {  6, 26, 50, 74, 98,122,  0 }, /* 28 */
+        {  6, 30, 54, 78,102,126,  0 }, /* 29 */
+        {  6, 26, 52, 78,104,130,  0 }, /* 30 */
+        {  6, 30, 56, 82,108,134,  0 }, /* 31 */
+        {  6, 34, 60, 86,112,138,  0 }, /* 32 */
+        {  6, 30, 58, 86,114,142,  0 }, /* 33 */
+        {  6, 34, 62, 90,118,146,  0 }, /* 34 */
+        {  6, 30, 54, 78,102,126,150 }, /* 35 */
+        {  6, 24, 50, 76,102,128,154 }, /* 36 */
+        {  6, 28, 54, 80,106,132,158 }, /* 37 */
+        {  6, 32, 58, 84,110,136,162 }, /* 38 */
+        {  6, 26, 54, 82,110,138,166 }, /* 39 */
+        {  6, 30, 58, 86,114,142,170 }, /* 40 */
+};
+
+const int QR_DATA_WORD_COUNT[40][4] = {
+        {   19,   16,   13,    9 },
+        {   34,   28,   22,   16 },
+        {   55,   44,   34,   26 },
+        {   80,   64,   48,   36 },
+        {  108,   86,   62,   46 },
+        {  136,  108,   76,   60 },
+        {  156,  124,   88,   66 },
+        {  194,  154,  110,   86 },
+        {  232,  182,  132,  100 },
+        {  274,  216,  154,  122 },
+        {  324,  254,  180,  140 },
+        {  370,  290,  206,  158 },
+        {  428,  334,  244,  180 },
+        {  461,  365,  261,  197 },
+        {  523,  415,  295,  223 },
+        {  589,  453,  325,  253 },
+        {  647,  507,  367,  283 },
+        {  721,  563,  397,  313 },
+        {  795,  627,  445,  341 },
+        {  861,  669,  485,  385 },
+        {  932,  714,  512,  406 },
+        { 1006,  782,  568,  442 },
+        { 1094,  860,  614,  464 },
+        { 1174,  914,  664,  514 },
+        { 1276, 1000,  718,  538 },
+        { 1370, 1062,  754,  596 },
+        { 1468, 1128,  808,  628 },
+        { 1531, 1193,  871,  661 },
+        { 1631, 1267,  911,  701 },
+        { 1735, 1373,  985,  745 },
+        { 1845, 1455, 1033,  793 },
+        { 1955, 1541, 1115,  845 },
+        { 2071, 1631, 1171,  901 },
+        { 2191, 1725, 1231,  961 },
+        { 2306, 1812, 1286,  986 },
+        { 2434, 1914, 1351, 1054 },
+        { 2566, 1992, 1426, 1096 },
+        { 2812, 2216, 1582, 1222 },
+        { 2956, 2334, 1666, 1276 }
+};
+
+const int QR_RS_BLOCK_COUNT[40][4][2] = {
+        {  1,  0,  1,  0,  1,  0,  1,  0 }, /*  1 */
+        {  1,  0,  1,  0,  1,  0,  1,  0 }, /*  2 */
+        {  1,  0,  1,  0,  2,  0,  2,  0 }, /*  3 */
+        {  1,  0,  2,  0,  2,  0,  4,  0 }, /*  4 */
+        {  1,  0,  2,  0,  2,  0,  2,  0 }, /*  5 */
+        {  2,  0,  4,  0,  4,  0,  4,  0 }, /*  6 */
+        {  2,  0,  4,  0,  2,  4,  4,  1 }, /*  7 */
+        {  2,  0,  2,  2,  4,  2,  4,  2 }, /*  8 */
+        {  2,  0,  3,  2,  4,  4,  4,  4 }, /*  9 */
+        {  2,  2,  4,  1,  6,  2,  6,  2 }, /* 10 */
+        {  4,  0,  1,  4,  4,  4,  3,  8 }, /* 11 */
+        {  2,  2,  6,  2,  4,  6,  7,  4 }, /* 12 */
+        {  4,  0,  8,  1,  8,  4, 12,  4 }, /* 13 */
+        {  3,  1,  4,  5, 11,  5, 11,  5 }, /* 14 */
+        {  5,  1,  5,  5,  5,  7, 11,  7 }, /* 15 */
+        {  5,  1,  7,  3, 15,  2,  3, 13 }, /* 16 */
+        {  1,  5, 10,  1,  1, 15,  2, 17 }, /* 17 */
+        {  5,  1,  9,  4, 17,  1,  2, 19 }, /* 18 */
+        {  3,  4,  3, 11, 17,  4,  9, 16 }, /* 19 */
+        {  3,  5,  3, 13, 15,  5, 15, 10 }, /* 20 */
+        {  4,  4, 17,  0, 17,  6, 19,  6 }, /* 21 */
+        {  2,  7, 17,  0,  7, 16, 34,  0 }, /* 22 */
+        {  4,  5,  4, 14, 11, 14, 16, 14 }, /* 23 */
+        {  6,  4,  6, 14, 11, 16, 30,  2 }, /* 24 */
+        {  8,  4,  8, 13,  7, 22, 22, 13 }, /* 25 */
+        { 10,  2, 19,  4, 28,  6, 33,  4 }, /* 26 */
+        {  8,  4, 22,  3,  8, 26, 12, 28 }, /* 27 */
+        {  3, 10,  3, 23,  4, 31, 11, 31 }, /* 28 */
+        {  7,  7, 21,  7,  1, 37, 19, 26 }, /* 29 */
+        {  5, 10, 19, 10, 15, 25, 23, 25 }, /* 30 */
+        { 13,  3,  2, 29, 42,  1, 23, 28 }, /* 31 */
+        { 17,  0, 10, 23, 10, 35, 19, 35 }, /* 32 */
+        { 17,  1, 14, 21, 29, 19, 11, 46 }, /* 33 */
+        { 13,  6, 14, 23, 44,  7, 59,  1 }, /* 34 */
+        { 12,  7, 12, 26, 39, 14, 22, 41 }, /* 35 */
+        {  6, 14,  6, 34, 46, 10,  2, 64 }, /* 36 */
+        { 17,  4, 29, 14, 49, 10, 24, 46 }, /* 37 */
+        {  4, 18, 13, 32, 48, 14, 42, 32 }, /* 38 */
+        { 20,  4, 40,  7, 43, 22, 10, 67 }, /* 39 */
+        { 19,  6, 18, 31, 34, 34, 20, 61 }  /* 40 */
+};
+
+const enum qr_data_type QR_TYPE_CODES[16] = {
+        QR_DATA_INVALID,        /* 0000 */
+        QR_DATA_NUMERIC,        /* 0001 */
+        QR_DATA_ALPHA,          /* 0010 */
+        QR_DATA_MIXED,          /* 0011 */
+        QR_DATA_8BIT,           /* 0100 */
+        QR_DATA_FNC1,           /* 0101 */
+        QR_DATA_INVALID,        /* 0110 */
+        QR_DATA_ECI,            /* 0111 */
+        QR_DATA_KANJI,          /* 1000 */
+        QR_DATA_FNC1,           /* 1001 */
+        QR_DATA_INVALID,        /* 1010 */
+        QR_DATA_INVALID,        /* 1011 */
+        QR_DATA_INVALID,        /* 1100 */
+        QR_DATA_INVALID,        /* 1101 */
+        QR_DATA_INVALID,        /* 1110 */
+        QR_DATA_INVALID,        /* 1111 */
+};
+
diff --git a/lpg/libqr/constants.h b/lpg/libqr/constants.h
new file mode 100644
index 0000000..15aa515
--- /dev/null
+++ b/lpg/libqr/constants.h
@@ -0,0 +1,12 @@
+#ifndef QR_CONSTANTS_H
+#define QR_CONSTANTS_H
+
+#include <qr/data.h>
+
+extern const int QR_ALIGNMENT_LOCATION[40][7];
+extern const int QR_DATA_WORD_COUNT[40][4];
+extern const int QR_RS_BLOCK_COUNT[40][4][2];
+extern const enum qr_data_type QR_TYPE_CODES[16];
+
+#endif
+
diff --git a/lpg/libqr/data-common.c b/lpg/libqr/data-common.c
index ac2f198..8a05f4a 100644
--- a/lpg/libqr/data-common.c
+++ b/lpg/libqr/data-common.c
@@ -1,27 +1,7 @@
 #include <stdlib.h>
-#include <qr/data.h>
-
-#include "qr-bitstream.h"
-#include "data-common.h"
 
-const enum qr_data_type QR_TYPE_CODES[16] = {
-        QR_DATA_INVALID,        /* 0000 */
-        QR_DATA_NUMERIC,        /* 0001 */
-        QR_DATA_ALPHA,          /* 0010 */
-        QR_DATA_MIXED,          /* 0011 */
-        QR_DATA_8BIT,           /* 0100 */
-        QR_DATA_FNC1,           /* 0101 */
-        QR_DATA_INVALID,        /* 0110 */
-        QR_DATA_ECI,            /* 0111 */
-        QR_DATA_KANJI,          /* 1000 */
-        QR_DATA_FNC1,           /* 1001 */
-        QR_DATA_INVALID,        /* 1010 */
-        QR_DATA_INVALID,        /* 1011 */
-        QR_DATA_INVALID,        /* 1100 */
-        QR_DATA_INVALID,        /* 1101 */
-        QR_DATA_INVALID,        /* 1110 */
-        QR_DATA_INVALID,        /* 1111 */
-};
+#include <qr/bitstream.h>
+#include <qr/data.h>
 
 void qr_free_data(struct qr_data * data)
 {
@@ -29,7 +9,7 @@ void qr_free_data(struct qr_data * data)
         free(data);
 }
 
-size_t get_size_field_length(int version, enum qr_data_type type)
+size_t qr_data_size_field_length(int version, enum qr_data_type type)
 {
         static const size_t QR_SIZE_LENGTHS[3][4] = {
                 { 10,  9,  8,  8 },
diff --git a/lpg/libqr/data-common.h b/lpg/libqr/data-common.h
deleted file mode 100644
index 054d349..0000000
--- a/lpg/libqr/data-common.h
+++ /dev/null
@@ -1,22 +0,0 @@
-#ifndef DATA_COMMON_H
-#define DATA_COMMON_H
-
-#include <qr/data.h>
-
-#include "qr-bitstream.h"
-
-struct qr_data {
-        int                version; /* 1 ~ 40 */
-        enum qr_ec_level      ec;
-        struct qr_bitstream * bits;
-        size_t             offset;
-};
-
-extern const enum qr_data_type QR_TYPE_CODES[16];
-
-size_t get_size_field_length(int version, enum qr_data_type);
-
-size_t qr_data_dpart_length(enum qr_data_type type, size_t nchars);
-
-#endif
-
diff --git a/lpg/libqr/data-create.c b/lpg/libqr/data-create.c
index 37556c6..9d6c384 100644
--- a/lpg/libqr/data-create.c
+++ b/lpg/libqr/data-create.c
@@ -2,16 +2,12 @@
  * Not "pure" C - only works with ASCII
  */
 
-/** XXX: check that the data will fit! **/
-
 #include <ctype.h>
 #include <stdlib.h>
-#include <qr/data.h>
 
-#include "qr-bitstream.h"
-#include "data-common.h"
-
-extern const int QR_DATA_WORD_COUNT[40][4];
+#include <qr/bitstream.h>
+#include <qr/data.h>
+#include "constants.h"
 
 static void write_type_and_length(struct qr_data *  data,
                                   enum qr_data_type type,
@@ -19,7 +15,7 @@ static void write_type_and_length(struct qr_data *  data,
 {
         (void)qr_bitstream_write(data->bits, QR_TYPE_CODES[type], 4);
         (void)qr_bitstream_write(data->bits, length,
-                get_size_field_length(data->version, type));
+                qr_data_size_field_length(data->version, type));
 }
 
 static struct qr_data * encode_numeric(struct qr_data * data,
@@ -29,7 +25,7 @@ static struct qr_data * encode_numeric(struct qr_data * data,
         struct qr_bitstream * stream = data->bits;
         size_t bits;
 
-        bits = 4 + get_size_field_length(data->version, QR_DATA_NUMERIC)
+        bits = 4 + qr_data_size_field_length(data->version, QR_DATA_NUMERIC)
                  + qr_data_dpart_length(QR_DATA_NUMERIC, length);
 
         stream = data->bits;
@@ -102,7 +98,7 @@ static struct qr_data * encode_alpha(struct qr_data * data,
         struct qr_bitstream * stream = data->bits;
         size_t bits;
 
-        bits = 4 + get_size_field_length(data->version, QR_DATA_ALPHA)
+        bits = 4 + qr_data_size_field_length(data->version, QR_DATA_ALPHA)
                  + qr_data_dpart_length(QR_DATA_ALPHA, length);
 
         stream = data->bits;
@@ -145,7 +141,7 @@ static struct qr_data * encode_8bit(struct qr_data * data,
         struct qr_bitstream * stream = data->bits;
         size_t bits;
 
-        bits = 4 + get_size_field_length(data->version, QR_DATA_8BIT)
+        bits = 4 + qr_data_size_field_length(data->version, QR_DATA_8BIT)
                  + qr_data_dpart_length(QR_DATA_8BIT, length);
 
         stream = data->bits;
@@ -178,7 +174,7 @@ static int calc_min_version(enum qr_data_type type,
         dbits = qr_data_dpart_length(type, length);
 
         for (version = 1; version <= 40; ++version) {
-                if (4 + dbits + get_size_field_length(version, type)
+                if (4 + dbits + qr_data_size_field_length(version, type)
                     < 8 * QR_DATA_WORD_COUNT[version - 1][ec ^ 0x1])
                         return version;
         }
diff --git a/lpg/libqr/data-parse.c b/lpg/libqr/data-parse.c
index 4868cd2..801aa66 100644
--- a/lpg/libqr/data-parse.c
+++ b/lpg/libqr/data-parse.c
@@ -1,10 +1,10 @@
 #include <assert.h>
 #include <stdio.h>
 #include <stdlib.h>
-#include <qr/data.h>
 
-#include "qr-bitstream.h"
-#include "data-common.h"
+#include <qr/bitstream.h>
+#include <qr/data.h>
+#include "constants.h"
 
 static enum qr_data_type read_data_type(struct qr_bitstream * stream)
 {
@@ -33,7 +33,7 @@ static enum qr_data_type parse_numeric(const struct qr_data * data,
         stream = data->bits;
         buffer = 0;
 
-        field_len = get_size_field_length(data->version, QR_DATA_NUMERIC);
+        field_len = qr_data_size_field_length(data->version, QR_DATA_NUMERIC);
         if (qr_bitstream_remaining(stream) < field_len)
                 goto invalid;
 
@@ -93,7 +93,7 @@ static enum qr_data_type parse_alpha(const struct qr_data * data,
         stream = data->bits;
         buffer = 0;
 
-        field_len = get_size_field_length(data->version, QR_DATA_ALPHA);
+        field_len = qr_data_size_field_length(data->version, QR_DATA_ALPHA);
         if (qr_bitstream_remaining(stream) < field_len)
                 goto invalid;
 
@@ -150,7 +150,7 @@ static enum qr_data_type parse_8bit(const struct qr_data * data,
 
         stream = data->bits;
 
-        field_len = get_size_field_length(data->version, QR_DATA_8BIT);
+        field_len = qr_data_size_field_length(data->version, QR_DATA_8BIT);
         if (qr_bitstream_remaining(stream) < field_len)
                 return QR_DATA_INVALID;
 
@@ -181,7 +181,7 @@ static enum qr_data_type parse_kanji(const struct qr_data * data,
         return QR_DATA_INVALID;
 }
 
-enum qr_data_type qr_get_data_type(const struct qr_data * data)
+enum qr_data_type qr_data_type(const struct qr_data * data)
 {
         qr_bitstream_seek(data->bits, data->offset);
         return read_data_type(data->bits);
@@ -201,7 +201,7 @@ int qr_get_data_length(const struct qr_data * data)
         case QR_DATA_ALPHA:
         case QR_DATA_8BIT:
         case QR_DATA_KANJI:
-                field_len = get_size_field_length(data->version, type);
+                field_len = qr_data_size_field_length(data->version, type);
                 break;
         default:
                 /* unsupported / invalid */
diff --git a/lpg/libqr/rs-encode.c b/lpg/libqr/galois.c
index a8ecc73..e21ce22 100644
--- a/lpg/libqr/rs-encode.c
+++ b/lpg/libqr/galois.c
@@ -1,7 +1,37 @@
 #include <assert.h>
 #include <stdlib.h>
-#include "qr-bitstream.h"
-#include "rs.h"
+
+#include <qr/bitstream.h>
+#include "galois.h"
+
+/* Calculate the residue of a modulo m */
+unsigned long gf_residue(unsigned long a,
+                         unsigned long m)
+{
+        unsigned long o = 1;
+        int n = 1;
+
+        /* Find one past the highest bit of the modulus */
+        while (m & ~(o - 1))
+                o <<= 1;
+
+        /* Find the highest n such that O(m * x^n) <= O(a) */
+        while (a & ~(o - 1)) {
+                o <<= 1;
+                ++n;
+        }
+
+        /* For each n, try to reduce a by (m * x^n) */
+        while (n--) {
+                o >>= 1;
+
+                /* o is the highest bit of (m * x^n) */
+                if (a & o)
+                        a ^= m << n;
+        }
+
+        return a;
+}
 
 static unsigned int gf_mult(unsigned int a, unsigned int b)
 {
diff --git a/lpg/libqr/rs.h b/lpg/libqr/galois.h
index c87d852..1adeb88 100644
--- a/lpg/libqr/rs.h
+++ b/lpg/libqr/galois.h
@@ -1,7 +1,8 @@
-#ifndef RS_H
-#define RS_H
+#ifndef QR_GALOIS_H
+#define QR_GALOIS_H
 
-#include "qr-bitstream.h"
+unsigned long gf_residue(unsigned long a,
+                         unsigned long m);
 
 struct qr_bitstream * rs_generate_words(struct qr_bitstream * data,
                                      size_t data_words,
diff --git a/lpg/libqr/qr-bitmap.c b/lpg/libqr/qr-bitmap.c
deleted file mode 100644
index 7d2d900..0000000
--- a/lpg/libqr/qr-bitmap.c
+++ /dev/null
@@ -1,89 +0,0 @@
-#include <assert.h>
-#include <limits.h>
-#include <stdlib.h>
-#include <string.h>
-#include <qr/bitmap.h>
-
-struct qr_bitmap * qr_bitmap_create(int width, int height, int masked)
-{
-        struct qr_bitmap * out;
-        size_t size;
-
-        out = malloc(sizeof(*out));
-        if (!out)
-                goto fail;
-
-        out->width = width;
-        out->height = height;
-        out->stride = (width / CHAR_BIT) + (width % CHAR_BIT ? 1 : 0);
-
-        size = out->stride * height;
-
-        out->mask = 0;
-        out->bits = malloc(size);
-        if (!out->bits)
-                goto fail;
-        memset(out->bits, 0, size);
-
-        if (masked) {
-                out->mask = malloc(out->stride * width);
-                if (!out->mask)
-                        goto fail;
-                memset(out->mask, 0xFF, size);
-        }
-
-        return out;
-
-fail:
-        qr_bitmap_destroy(out);
-        return 0;
-}
-
-void qr_bitmap_destroy(struct qr_bitmap * bmp)
-{
-        if (bmp) {
-                free(bmp->bits);
-                free(bmp->mask);
-                free(bmp);
-        }
-}
-
-struct qr_bitmap * qr_bitmap_clone(const struct qr_bitmap * src)
-{
-        struct qr_bitmap * bmp;
-        size_t size;
-
-        bmp = qr_bitmap_create(src->width, src->height, !!src->mask);
-        if (!bmp)
-                return 0;
-
-        assert(bmp->stride == src->stride);
-
-        size = bmp->width * bmp->stride;
-        memcpy(bmp->bits, src->bits, size);
-        if (bmp->mask)
-                memcpy(bmp->mask, src->mask, size);
-
-        return bmp;
-}
-
-void qr_bitmap_merge(struct qr_bitmap * dest, const struct qr_bitmap * src)
-{
-        unsigned char * d, * s, * m;
-        size_t n;
-
-        assert(dest->stride == src->stride);
-        assert(dest->height == src->height);
-        assert(src->mask);
-
-        n = dest->stride * dest->height;
-        d = dest->bits;
-        s = src->bits;
-        m = src->mask;
-
-        while (n--) {
-                *d   &= ~*m;
-                *d++ |= *s++ & *m++;
-        }
-}
-
diff --git a/lpg/libqr/qr-mask.c b/lpg/libqr/qr-mask.c
deleted file mode 100644
index 7ff78a4..0000000
--- a/lpg/libqr/qr-mask.c
+++ /dev/null
@@ -1,46 +0,0 @@
-#include <limits.h>
-#include <stdlib.h>
-#include <qr/bitmap.h>
-#include "qr-mask.h"
-
-struct qr_bitmap * qr_mask_apply(const struct qr_bitmap * orig,
-                                 unsigned int mask)
-{
-        struct qr_bitmap * bmp;
-        int i, j;
-
-        if (mask & ~0x7)
-                return 0;
-
-        bmp = qr_bitmap_clone(orig);
-        if (!bmp)
-                return 0;
-
-        /* Slow version for now; we can optimize later */
-
-        for (i = 0; i < bmp->height; ++i) {
-                unsigned char * p = bmp->bits + i * bmp->stride;
-
-                for (j = 0; j < bmp->width; ++j) {
-                        int bit = j % CHAR_BIT;
-                        size_t off = j / CHAR_BIT;
-                        int t;
-
-                        switch (mask) {
-                        case 0: t = (i + j) % 2; break;
-                        case 1: t = i % 2; break;
-                        case 2: t = j % 3; break;
-                        case 3: t = (i + j) % 3; break;
-                        case 4: t = (i/2 + j/3) % 2; break;
-                        case 5: t = ((i*j) % 2) + ((i*j) % 3); break;
-                        case 6: t = (((i*j) % 2) + ((i*j) % 3)) % 2; break;
-                        case 7: t = (((i*j) % 3) + ((i+j) % 2)) % 2; break;
-                        }
-
-                        p[off] ^= (t == 0) << bit;
-                }
-        }
-
-        return bmp;
-}
-
diff --git a/lpg/libqr/qr-mask.h b/lpg/libqr/qr-mask.h
deleted file mode 100644
index eb254af..0000000
--- a/lpg/libqr/qr-mask.h
+++ /dev/null
@@ -1,10 +0,0 @@
-#ifndef QR_MASK_H
-#define QR_MASK_H
-
-#include <qr/bitmap.h>
-
-struct qr_bitmap * qr_mask_apply(const struct qr_bitmap * orig,
-                                 unsigned int mask);
-
-#endif
-
diff --git a/lpg/libqr/qr-bitstream.h b/lpg/libqr/qr/bitstream.h
index cf20694..cf20694 100644
--- a/lpg/libqr/qr-bitstream.h
+++ b/lpg/libqr/qr/bitstream.h
diff --git a/lpg/libqr/qr/code.h b/lpg/libqr/qr/code.h
index 3c14c1f..ac3c363 100644
--- a/lpg/libqr/qr/code.h
+++ b/lpg/libqr/qr/code.h
@@ -4,16 +4,26 @@
 #include <stddef.h>
 #include "types.h"
 
+struct qr_code {
+        int                version;
+        struct qr_bitmap * modules;
+};
+
 struct qr_code * qr_code_create(const struct qr_data * data);
 
 void qr_code_destroy(struct qr_code *);
 
 int qr_code_width(const struct qr_code *);
 
+size_t qr_code_total_capacity(int version);
+
 struct qr_code * qr_code_parse(const void * buffer,
                                size_t       line_bits,
                                size_t       line_stride,
                                size_t       line_count);
 
+struct qr_bitmap * qr_mask_apply(const struct qr_bitmap * orig,
+                                 unsigned int mask);
+
 #endif
 
diff --git a/lpg/libqr/qr/data.h b/lpg/libqr/qr/data.h
index 34b6968..a3bb309 100644
--- a/lpg/libqr/qr/data.h
+++ b/lpg/libqr/qr/data.h
@@ -22,6 +22,13 @@ enum qr_ec_level {
         QR_EC_LEVEL_H = 0x2
 };
 
+struct qr_data {
+        int                   version; /* 1 ~ 40 */
+        enum qr_ec_level      ec;
+        struct qr_bitstream * bits;
+        size_t                offset;
+};
+
 struct qr_data * qr_create_data(int               format, /* 1 ~ 40; 0=auto */
                                 enum qr_ec_level  ec,
                                 enum qr_data_type type,
@@ -30,9 +37,11 @@ struct qr_data * qr_create_data(int               format, /* 1 ~ 40; 0=auto */
 
 void qr_free_data(struct qr_data *);
 
-enum qr_data_type qr_get_data_type(const struct qr_data *);
+enum qr_data_type qr_data_type(const struct qr_data *);
 
-int qr_get_data_length(const struct qr_data *);
+size_t qr_data_length(const struct qr_data *);
+size_t qr_data_size_field_length(int version, enum qr_data_type);
+size_t qr_data_dpart_length(enum qr_data_type type, size_t nchars);
 
 enum qr_data_type qr_parse_data(const struct qr_data * input,
                                 char **                output,
diff --git a/lpg/libqr/code-layout.h b/lpg/libqr/qr/layout.h
index 3390548..49bebf6 100644
--- a/lpg/libqr/code-layout.h
+++ b/lpg/libqr/qr/layout.h
@@ -1,5 +1,5 @@
-#ifndef CODE_LAYOUT_H
-#define CODE_LAYOUT_H
+#ifndef QR_CODE_LAYOUT_H
+#define QR_CODE_LAYOUT_H
 
 struct qr_iterator;
 
diff --git a/lpg/libqr/qrgen.c b/lpg/libqr/qrgen.c
index 1309596..ad53125 100644
--- a/lpg/libqr/qrgen.c
+++ b/lpg/libqr/qrgen.c
@@ -1,17 +1,16 @@
+#include <assert.h>
 #include <ctype.h>
+#include <getopt.h>
+#include <limits.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
-#include <assert.h>
-#include <limits.h>
-#include <getopt.h>
+
 #include <qr/bitmap.h>
+#include <qr/bitstream.h>
 #include <qr/code.h>
 #include <qr/data.h>
 
-#include "qr-bitstream.h"
-#include "code-common.h"
-
 struct config {
         int               version;
         enum qr_ec_level  ec;