support for multiple ec blocks

5 files changed, 138 insertions, 26 deletions

diff --git a/lpg/libqr/Makefile b/lpg/libqr/Makefile
index 19e8791..3a6af6f 100644
--- a/lpg/libqr/Makefile
+++ b/lpg/libqr/Makefile
@@ -1,4 +1,5 @@
-OBJECTS :=      code-common.o           \
+OBJECTS :=      capacity.o              \
+                code-common.o           \
                 code-create.o           \
                 code-layout.o           \
                 code-parse.o            \
diff --git a/lpg/libqr/capacity.c b/lpg/libqr/capacity.c
new file mode 100644
index 0000000..4b513af
--- /dev/null
+++ b/lpg/libqr/capacity.c
@@ -0,0 +1,88 @@
+/* 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-create.c b/lpg/libqr/code-create.c
index 2e0a0b2..36ebb24 100644
--- a/lpg/libqr/code-create.c
+++ b/lpg/libqr/code-create.c
@@ -11,6 +11,9 @@
 
 #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);
@@ -153,7 +156,8 @@ static struct qr_bitstream * make_data(int version,
 {
         const size_t total_bits = code_total_capacity(version);
         const size_t total_words = total_bits / 8;
-        size_t block_count, data_words, rs_words;
+        const size_t total_data = QR_DATA_WORD_COUNT[version - 1][ec ^ 0x1];
+        size_t total_blocks, block_count[2], data_words, rs_words;
         size_t i;
         struct qr_bitstream * dcopy = 0;
         struct qr_bitstream * out = 0;
@@ -167,38 +171,38 @@ static struct qr_bitstream * make_data(int version,
         if (qr_bitstream_resize(out, total_bits) != 0)
                 goto fail;
 
-        /**
-         * XXX: For our test case (1-M) there is only one RS block.
-         * This is not the case for most other formats, so we'll
-         * have to deal with this eventually.
-         */
-        block_count = 1;
-        data_words = 16;
-        rs_words = 10;
-        assert(data_words + rs_words == total_words);
+        /* XXX: 14-M will be incorrect */
+        block_count[0] = QR_RS_BLOCK_COUNT[version - 1][ec ^ 0x1][0];
+        block_count[1] = QR_RS_BLOCK_COUNT[version - 1][ec ^ 0x1][1];
+        total_blocks = block_count[0] + block_count[1];
+        data_words = total_data / total_blocks;
+        rs_words = total_words / total_blocks - data_words;
+        assert((data_words + rs_words) * block_count[0] +
+               (data_words + rs_words + 1) * block_count[1] == total_words);
 
         /* Make a copy of the data and pad it */
-        dcopy = qr_bitstream_copy(data);
+        dcopy = qr_bitstream_dup(data);
         if (!dcopy)
                 goto fail;
 
-        if (pad_data(dcopy, data_words * 8) != 0)
+        if (pad_data(dcopy, total_data * 8) != 0)
                 goto fail;
 
         fputs("Pad data:\n", stderr);
         x_dump(dcopy);
 
         /* Make space for the RS blocks */
-        blocks = calloc(block_count, sizeof(*blocks));
+        blocks = calloc(total_blocks, sizeof(*blocks));
         if (!blocks)
                 goto fail;
 
         /* Generate RS codewords */
         qr_bitstream_seek(dcopy, 0);
         fputs("Generate RS blocks:\n", stderr);
-        for (i = 0; i < block_count; ++i) {
-                /* XXX: some blocks may be longer */
-                blocks[i] = rs_generate_words(dcopy, data_words, rs_words);
+        for (i = 0; i < total_blocks; ++i) {
+                size_t dw = data_words + (i >= block_count[0]);
+
+                blocks[i] = rs_generate_words(dcopy, dw, rs_words);
                 if (!blocks[i]) {
                         while (i--)
                                 qr_bitstream_destroy(blocks[i]);
@@ -210,17 +214,20 @@ static struct qr_bitstream * make_data(int version,
         }
 
         /* Finally, write everything out in the correct order */
-        /* XXX: need to handle multiple blocks */
-        qr_bitstream_cat(out, dcopy);
-        qr_bitstream_cat(out, blocks[0]);
+        qr_bitstream_seek(dcopy, 0);
+        for (i = 0; i < total_blocks; ++i) {
+                size_t dw = data_words + (i >= block_count[0]);
+                qr_bitstream_copy(out, dcopy, dw * 8);
+                qr_bitstream_cat(out, blocks[i]);
+        }
         qr_bitstream_write(out, 0, total_bits - total_words * 8);
 
         fputs("Final bitstream:\n", stderr);
         x_dump(out);
 exit:
         if (blocks) {
-                while (block_count--)
-                       qr_bitstream_destroy(blocks[block_count]);
+                while (total_blocks--)
+                       qr_bitstream_destroy(blocks[total_blocks]);
                 free(blocks);
         }
         if (dcopy)
diff --git a/lpg/libqr/qr-bitstream.c b/lpg/libqr/qr-bitstream.c
index b223f4c..c752cde 100644
--- a/lpg/libqr/qr-bitstream.c
+++ b/lpg/libqr/qr-bitstream.c
@@ -80,7 +80,7 @@ void qr_bitstream_destroy(struct qr_bitstream * stream)
         free(stream);
 }
 
-struct qr_bitstream * qr_bitstream_copy(const struct qr_bitstream * src)
+struct qr_bitstream * qr_bitstream_dup(const struct qr_bitstream * src)
 {
         struct qr_bitstream * ret;
 
@@ -210,6 +210,20 @@ int qr_bitstream_cat(struct qr_bitstream * dest, const struct qr_bitstream * src
 
         srcpos = qr_bitstream_tell(src);
         qr_bitstream_seek((struct qr_bitstream *)src, 0);
+        qr_bitstream_copy(dest, (struct qr_bitstream *)src, count);
+        qr_bitstream_seek((struct qr_bitstream *)src, srcpos);
+
+        return 0;
+}
+
+int qr_bitstream_copy(struct qr_bitstream * dest,
+                      struct qr_bitstream * src,
+                      size_t count)
+{
+        if (qr_bitstream_remaining(src) < count)
+                return -1;
+        if (ensure_available(dest, count) != 0)
+                return -1;
 
         /* uint must be at least 16 bits */
         for (; count >= 16; count -= 16)
@@ -224,8 +238,6 @@ int qr_bitstream_cat(struct qr_bitstream * dest, const struct qr_bitstream * src
                         qr_bitstream_read((struct qr_bitstream *)src, count),
                         count);
 
-        qr_bitstream_seek((struct qr_bitstream *)src, srcpos);
-
         return 0;
 }
 
diff --git a/lpg/libqr/qr-bitstream.h b/lpg/libqr/qr-bitstream.h
index 298e53b..cf20694 100644
--- a/lpg/libqr/qr-bitstream.h
+++ b/lpg/libqr/qr-bitstream.h
@@ -15,7 +15,7 @@ struct qr_bitstream;
 struct qr_bitstream * qr_bitstream_create(void);
 int                qr_bitstream_resize(struct qr_bitstream *, size_t bits);
 void               qr_bitstream_destroy(struct qr_bitstream *);
-struct qr_bitstream * qr_bitstream_copy(const struct qr_bitstream *);
+struct qr_bitstream * qr_bitstream_dup(const struct qr_bitstream *);
 
 void qr_bitstream_seek(struct qr_bitstream *, size_t pos);
 size_t qr_bitstream_tell(const struct qr_bitstream *);
@@ -40,5 +40,9 @@ int qr_bitstream_pack(struct qr_bitstream *,
 
 int qr_bitstream_cat(struct qr_bitstream *, const struct qr_bitstream * src);
 
+int qr_bitstream_copy(struct qr_bitstream * dest,
+                      struct qr_bitstream * src,
+                      size_t count);
+
 #endif