First attempt at parsing

12 files changed, 427 insertions, 12 deletions

diff --git a/lpg/libqr/Makefile b/lpg/libqr/Makefile
index a82372f..fa6cf04 100644
--- a/lpg/libqr/Makefile
+++ b/lpg/libqr/Makefile
@@ -14,7 +14,7 @@ CFLAGS := -std=c89 -pedantic -I. -Wall
 CFLAGS += -g
 #CFLAGS += -O3 -DNDEBUG
 
-all : libqr qrgen
+all : libqr qrgen qrparse
 
 $(OBJECTS) : $(wildcard *.h qr/*.h)
 
@@ -23,6 +23,9 @@ libqr : libqr.a($(OBJECTS))
 qrgen : libqr qrgen.c
 	$(CC) $(CFLAGS) -o qrgen qrgen.c libqr.a
 
+qrparse : libqr qrparse.c
+	$(CC) $(CFLAGS) -o qrparse qrparse.c libqr.a
+
 .PHONY : clean
 clean:
 	$(RM) qr/*~ *~ *.o *.a *.so qrgen
diff --git a/lpg/libqr/bitmap.c b/lpg/libqr/bitmap.c
index 3394784..759aeca 100644
--- a/lpg/libqr/bitmap.c
+++ b/lpg/libqr/bitmap.c
@@ -49,6 +49,16 @@ void qr_bitmap_destroy(struct qr_bitmap * bmp)
         }
 }
 
+int qr_bitmap_add_mask(struct qr_bitmap * bmp)
+{
+        size_t size = bmp->stride * bmp->width;
+        bmp->mask = malloc(size);
+        if (!bmp->mask)
+                return -1;
+        memset(bmp->mask, 0xFF, size);
+        return 0;
+}
+
 struct qr_bitmap * qr_bitmap_clone(const struct qr_bitmap * src)
 {
         struct qr_bitmap * bmp;
diff --git a/lpg/libqr/code-create.c b/lpg/libqr/code-create.c
index b0db1c9..155ffa3 100644
--- a/lpg/libqr/code-create.c
+++ b/lpg/libqr/code-create.c
@@ -588,6 +588,7 @@ static long calc_version_bits(int version)
         bits <<= 18 - 6;
         bits |= gf_residue(bits, 0x1F25);
 
+fprintf(stderr, "version bits: %lx\n", bits);
         return bits;
 }
 
diff --git a/lpg/libqr/code-layout.c b/lpg/libqr/code-layout.c
index 68a1a0e..04b6ca6 100644
--- a/lpg/libqr/code-layout.c
+++ b/lpg/libqr/code-layout.c
@@ -26,6 +26,9 @@ void qr_layout_init_mask(struct qr_code * code)
         const int * am_pos = QR_ALIGNMENT_LOCATION[code->version - 1];
         int am_side;
 
+        if (!bmp->mask)
+                qr_bitmap_add_mask(bmp);
+
         assert(bmp->mask);
 
         memset(bmp->mask, 0, bmp->height * bmp->stride);
@@ -164,9 +167,8 @@ unsigned int qr_layout_read(struct qr_iterator * i)
         int b;
 
         for (b = 0; b < 8; ++b) {
-                x |= (*i->p & i->mask) ? 1 : 0;
+                x = (x << 1) | ((*i->p & i->mask) ? 1 : 0);
                 advance(i);
-                x <<= 1;
         }
 
         return x;
diff --git a/lpg/libqr/code-parse.c b/lpg/libqr/code-parse.c
index a794cdc..50d621c 100644
--- a/lpg/libqr/code-parse.c
+++ b/lpg/libqr/code-parse.c
@@ -1,10 +1,314 @@
+#include <assert.h>
+#include <limits.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include <qr/bitmap.h>
+#include <qr/bitstream.h>
 #include <qr/code.h>
+#include <qr/data.h>
+#include <qr/layout.h>
+#include <qr/parse.h>
+
+#include "constants.h"
+#include "galois.h"
+
+/* XXX: duplicated */
+static int get_px(const struct qr_bitmap * bmp, int x, int y)
+{
+        size_t off = y * bmp->stride + x / CHAR_BIT;
+        unsigned char bit = 1 << (x % CHAR_BIT);
+
+        return bmp->bits[off] & bit;
+}
+
+static int unpack_bits(int version,
+                       enum qr_ec_level ec,
+                       struct qr_bitstream * raw_bits,
+                       struct qr_bitstream * bits_out)
+{
+        /* FIXME: less math here (get the values from a common helper fn) */
+        /* FIXME: more comments to explain the algorithm */
+
+        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];
+        int total_blocks, block_count[2], row_length[2], data_words, rs_words;
+        int i, w, block;
+        struct qr_bitstream ** blocks = 0;
+
+        /* copied from make_data */
+        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);
+
+        blocks = calloc(total_blocks, sizeof(*blocks));
+        /* XXX: check return (and below) */
+
+        for (i = 0; i < total_blocks; ++i)
+                blocks[i] = qr_bitstream_create();
+
+        /* Read in the data & EC (see spec table 19) */
+
+        qr_bitstream_seek(raw_bits, 0);
+
+        /* XXX: 14-M will be incorrect */
+        row_length[0] = data_words;
+        row_length[1] = block_count[1] > 0 ? (total_data - row_length[0] * block_count[0]) / block_count[1] : 0;
+
+        fprintf(stderr, "block counts %d and %d\n", block_count[0], block_count[1]);
+        fprintf(stderr, "row lengths %d and %d\n", row_length[0], row_length[1]);
+
+        block = 0;
+        for (w = 0; w < total_words; ++w) {
+                if (block == 0 && w / total_blocks == row_length[0] && block_count[1] != 0) {
+                        /* Skip the short blocks, if there are any */
+                        block += block_count[0];
+                }
+                qr_bitstream_write(blocks[block], qr_bitstream_read(raw_bits, 8), 8);
+                block = (block + 1) % total_blocks;
+        }
+
+        /* XXX: apply ec */
+
+        for (block = 0; block < total_blocks; ++block) {
+                struct qr_bitstream * stream = blocks[block];
+                qr_bitstream_seek(stream, 0);
+                for (w = 0; w < row_length[block >= block_count[0]]; ++w)
+                        qr_bitstream_write(bits_out,
+                                           qr_bitstream_read(stream, 8),
+                                           8);
+                qr_bitstream_destroy(stream);
+        }
+        free(blocks);
+
+        return 0;
+}
 
-struct qr_code * qr_code_parse(const void * buffer,
-                               size_t       line_bits,
-                               size_t       line_stride,
-                               size_t       line_count)
+static int read_bits(const struct qr_code * code,
+                     enum qr_ec_level ec,
+                     struct qr_bitstream * data_bits)
 {
+        const size_t total_bits = qr_code_total_capacity(code->version);
+        const size_t total_words = total_bits / 8;
+        struct qr_bitstream * raw_bits;
+        struct qr_iterator * layout;
+        int w;
+        int ret;
+
+        raw_bits = qr_bitstream_create();
+        layout = qr_layout_begin((struct qr_code *) code); /* dropping const! */
+        for (w = 0; w < total_words; ++w)
+                qr_bitstream_write(raw_bits, qr_layout_read(layout), 8);
+        qr_layout_end(layout);
+
+        ret = unpack_bits(code->version, ec, raw_bits, data_bits);
+        qr_bitstream_destroy(raw_bits);
+
+        return ret;
+}
+
+static int read_format(const struct qr_bitmap * bmp, enum qr_ec_level * ec, int * mask)
+{
+        int dim;
+        int i;
+        unsigned bits1, bits2;
+        enum qr_ec_level ec1, ec2;
+        int mask1, mask2;
+        int err1, err2;
+
+        dim = bmp->width;
+        bits1 = bits2 = 0;
+
+        for (i = 14; i >= 8; --i) {
+                bits1 = (bits1 << 1) | !!get_px(bmp, 14 - i + (i <= 8), 8);
+                bits2 = (bits2 << 1) | !!get_px(bmp, 8, dim - 1 - (14 - i));
+        }
+
+        for (; i >= 0; --i) {
+                bits1 = (bits1 << 1) | !!get_px(bmp, 8, i + (i >= 6));
+                bits2 = (bits2 << 1) | !!get_px(bmp, dim - 1 - i, 8);
+        }
+
+        fprintf(stderr, "read format bits %x / %x\n", bits1, bits2);
+
+        err1 = qr_decode_format(bits1, &ec1, &mask1);
+        err2 = qr_decode_format(bits2, &ec2, &mask2);
+
+        if (err1 < 0 && err2 < 0)
+                return -1;
+
+        if (err1 < err2)
+                *ec = ec1, *mask = mask1;
+        else
+                *ec = ec2, *mask = mask2;
+
         return 0;
 }
 
+static int read_version(const struct qr_bitmap * bmp)
+{
+        int dim;
+        int i;
+        unsigned long bits1, bits2;
+        int ver1, ver2;
+        int err1, err2;
+
+        dim = bmp->width;
+        bits1 = bits2 = 0;
+
+        for (i = 17; i >= 0; --i) {
+                bits1 = (bits1 << 1) | !!get_px(bmp, i / 3, dim - 11 + (i % 3));
+                bits2 = (bits2 << 1) | !!get_px(bmp, dim - 11 + (i % 3), i / 3);
+        }
+
+        fprintf(stderr, "read version bits %lx / %lx\n", bits1, bits2);
+
+        err1 = qr_decode_version(bits1, &ver1);
+        err2 = qr_decode_version(bits2, &ver2);
+
+        fprintf(stderr, "got versions %d[%d] / %d[%d]\n", ver1, err1, ver2, err2);
+
+        if (err1 < 0 && err2 < 0)
+                return -1;
+
+        return err1 < err2 ? ver1 : ver2;
+}
+
+int qr_code_parse(const void *      buffer,
+                  size_t            line_bits,
+                  size_t            line_stride,
+                  size_t            line_count,
+                  struct qr_data ** data)
+{
+        struct qr_bitmap src_bmp;
+        struct qr_code code;
+        enum qr_ec_level ec;
+        int mask;
+        struct qr_bitstream * data_bits;
+
+        fprintf(stderr, "parsing code bitmap %lux%lu\n", line_bits, line_count);
+
+        if (line_bits != line_count
+            || line_bits < 21
+            || (line_bits - 17) % 4 != 0) {
+                /* Invalid size */
+                fprintf(stderr, "Invalid size\n");
+                return -1;
+        }
+
+        code.version = (line_bits - 17) / 4;
+        fprintf(stderr, "assuming version %d\n", code.version);
+
+        src_bmp.bits = (unsigned char *) buffer; /* dropping const! */
+        src_bmp.mask = NULL;
+        src_bmp.stride = line_stride;
+        src_bmp.width = line_bits;
+        src_bmp.height = line_count;
+
+        if (code.version >= 7 && read_version(&src_bmp) != code.version) {
+                fprintf(stderr, "Invalid version info\n");
+                return -1;
+        }
+
+        if (read_format(&src_bmp, &ec, &mask) != 0) {
+                fprintf(stderr, "Failed to read format\n");
+                return -1;
+        }
+
+        fprintf(stderr, "detected ec type %d; mask %d\n", ec, mask);
+
+        code.modules = qr_mask_apply(&src_bmp, mask);
+        if (code.modules == NULL) {
+                fprintf(stderr, "failed to apply mask\n");
+                return -1;
+        }
+
+        qr_layout_init_mask(&code);
+
+        data_bits = qr_bitstream_create();
+        /* XXX: check return */
+
+        read_bits(&code, ec, data_bits);
+        /* XXX: check return */
+
+        /*
+        {
+                fprintf(stderr, "decoding failed\n");
+                qr_bitmap_destroy(code.modules);
+                qr_bitstream_destroy(bits);
+                *data = NULL;
+                return -1;
+        }
+        */
+
+        *data = malloc(sizeof(*data));
+        /* XXX: check return */
+
+        (*data)->version = code.version;
+        (*data)->ec = ec;
+        (*data)->bits = data_bits;
+        (*data)->offset = 0;
+
+        return 0;
+}
+
+int qr_decode_format(unsigned bits, enum qr_ec_level * ec, int * mask)
+{
+        bits ^= 0x5412;
+
+        /* TODO: check and fix errors */
+
+        bits >>= 10;
+        *mask = bits & 7;
+        *ec = bits >> 3;
+
+        return 0;
+}
+
+int qr_decode_version(unsigned long bits, int * version)
+{
+        int v, errors;
+        unsigned long version_bits;
+        int best_err, best_version;
+
+        if (bits != (bits & 0x3FFFF))
+                fprintf(stderr, "WARNING: excess version bits");
+
+        best_err = 18;
+
+        for (v = 7; v <= 40; ++v) {
+                /* FIXME: cache these values */
+                /* see calc_version_bits() */
+                version_bits = v;
+                version_bits <<= 12;
+                version_bits |= gf_residue(version_bits, 0x1F25);
+
+                /* count errors */
+                errors = 0;
+                version_bits ^= bits;
+                while (version_bits != 0) {
+                        if ((version_bits & 1) == 1)
+                                ++errors;
+                        version_bits >>= 1;
+                }
+
+                if (errors < best_err) {
+                        best_version = v;
+                        best_err = errors;
+                }
+
+                if (errors == 0) /* can we do better than this? */
+                        break;
+        }
+
+        *version = best_version;
+
+        return best_err;
+}
+
diff --git a/lpg/libqr/constants.h b/lpg/libqr/constants.h
index 15aa515..2c19e97 100644
--- a/lpg/libqr/constants.h
+++ b/lpg/libqr/constants.h
@@ -5,6 +5,7 @@
 
 extern const int QR_ALIGNMENT_LOCATION[40][7];
 extern const int QR_DATA_WORD_COUNT[40][4];
+/* See spec table 18 (also table 19 for application) */
 extern const int QR_RS_BLOCK_COUNT[40][4][2];
 extern const enum qr_data_type QR_TYPE_CODES[16];
 
diff --git a/lpg/libqr/data-parse.c b/lpg/libqr/data-parse.c
index 801aa66..d641c47 100644
--- a/lpg/libqr/data-parse.c
+++ b/lpg/libqr/data-parse.c
@@ -220,6 +220,9 @@ enum qr_data_type qr_parse_data(const struct qr_data * input,
 {
         qr_bitstream_seek(input->bits, input->offset);
 
+        *output = NULL;
+        *length = 0;
+
         switch (read_data_type(input->bits)) {
         case QR_DATA_NUMERIC:
                 return parse_numeric(input, output, length);
diff --git a/lpg/libqr/qr/bitmap.h b/lpg/libqr/qr/bitmap.h
index 83e82ab..36c56b3 100644
--- a/lpg/libqr/qr/bitmap.h
+++ b/lpg/libqr/qr/bitmap.h
@@ -11,6 +11,8 @@ struct qr_bitmap {
 struct qr_bitmap * qr_bitmap_create(int width, int height, int masked);
 void qr_bitmap_destroy(struct qr_bitmap *);
 
+int qr_bitmap_add_mask(struct qr_bitmap *);
+
 struct qr_bitmap * qr_bitmap_clone(const struct qr_bitmap *);
 
 void qr_bitmap_merge(struct qr_bitmap * dest, const struct qr_bitmap * src);
diff --git a/lpg/libqr/qr/code.h b/lpg/libqr/qr/code.h
index ac3c363..2392467 100644
--- a/lpg/libqr/qr/code.h
+++ b/lpg/libqr/qr/code.h
@@ -17,11 +17,6 @@ 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);
 
diff --git a/lpg/libqr/qr/parse.h b/lpg/libqr/qr/parse.h
new file mode 100644
index 0000000..d7b8c4e
--- /dev/null
+++ b/lpg/libqr/qr/parse.h
@@ -0,0 +1,16 @@
+#ifndef QR_PARSE_H
+#define QR_PARSE_H
+
+#include "data.h"
+
+int qr_code_parse(const void *      buffer,
+                  size_t            line_bits,
+                  size_t            line_stride,
+                  size_t            line_count,
+                  struct qr_data ** data);
+
+int qr_decode_format(unsigned bits, enum qr_ec_level * ec, int * mask);
+int qr_decode_version(unsigned long bits, int * version);
+
+#endif
+
diff --git a/lpg/libqr/qrparse.c b/lpg/libqr/qrparse.c
new file mode 100644
index 0000000..4a9312f
--- /dev/null
+++ b/lpg/libqr/qrparse.c
@@ -0,0 +1,59 @@
+#include <limits.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#include <qr/code.h>
+#include <qr/data.h>
+#include <qr/parse.h>
+
+#include "testqr.xbm"
+
+int main(int argc, char ** argv)
+{
+        struct qr_data * data;
+        int ret;
+
+        ret = qr_code_parse(testqr_bits,
+                            testqr_width,
+                            (testqr_width + CHAR_BIT - 1) / CHAR_BIT,
+                            testqr_height,
+                            &data);
+
+        fprintf(stderr, "qr_code_parse returned %d\n", ret);
+
+        if (ret == 0) {
+                const char * ec_str, * type_str;
+                char * data_str;
+                size_t data_len;
+                enum qr_data_type data_type;
+
+                fprintf(stderr, "version = %d\n", data->version);
+                switch (data->ec) {
+                case QR_EC_LEVEL_L: ec_str = "L"; break;
+                case QR_EC_LEVEL_M: ec_str = "M"; break;
+                case QR_EC_LEVEL_Q: ec_str = "Q"; break;
+                case QR_EC_LEVEL_H: ec_str = "H"; break;
+                default: ec_str = "(unknown)"; break;
+                }
+                fprintf(stderr, "EC level %s\n", ec_str);
+
+                data_type = qr_parse_data(data, &data_str, &data_len);
+                switch (data_type) {
+                case QR_DATA_INVALID: type_str = "(invalid)"; break;
+                case QR_DATA_ECI: type_str = "ECI"; break;
+                case QR_DATA_NUMERIC: type_str = "numeric"; break;
+                case QR_DATA_ALPHA: type_str = "alpha"; break;
+                case QR_DATA_8BIT: type_str = "8-bit"; break;
+                case QR_DATA_KANJI: type_str = "kanji"; break;
+                case QR_DATA_MIXED: type_str = "mixed"; break;
+                case QR_DATA_FNC1: type_str = "FNC1"; break;
+                default: type_str = "(unknown)"; break;
+                }
+                fprintf(stderr, "Data type: %s; %lu bytes\nContent: %s\n", type_str, data_len, data_str);
+                free(data_str);
+                qr_free_data(data);
+        }
+
+        return 0;
+}
+
diff --git a/lpg/libqr/testqr.xbm b/lpg/libqr/testqr.xbm
new file mode 100644
index 0000000..ca2966f
--- /dev/null
+++ b/lpg/libqr/testqr.xbm
@@ -0,0 +1,19 @@
+#define testqr_width 37
+#define testqr_height 37
+static unsigned char testqr_bits[] = {
+  0x7F, 0x63, 0xFB, 0xDA, 0x1F, 0x41, 0xD7, 0xAD, 0x55, 0x10, 0x5D, 0x3D, 
+  0xE9, 0x5E, 0x17, 0x5D, 0xC6, 0xB5, 0x43, 0x17, 0x5D, 0x41, 0x61, 0x52, 
+  0x17, 0x41, 0x76, 0xC9, 0x46, 0x10, 0x7F, 0x55, 0x55, 0xD5, 0x1F, 0x00, 
+  0x98, 0x47, 0x05, 0x00, 0xF9, 0x99, 0xE0, 0x36, 0x1D, 0x24, 0x01, 0x07, 
+  0xC7, 0x0A, 0x60, 0xBC, 0xB9, 0x44, 0x16, 0x81, 0x21, 0x9D, 0x8D, 0x1B, 
+  0xCF, 0x8E, 0x83, 0x51, 0x16, 0xA2, 0x1B, 0xFD, 0x3A, 0x1B, 0xEB, 0x3B, 
+  0x1D, 0x5B, 0x17, 0xA9, 0xF6, 0x70, 0xF8, 0x1F, 0xC1, 0x68, 0x66, 0xFD, 
+  0x1D, 0xB3, 0x07, 0xC2, 0x54, 0x04, 0xD8, 0x0C, 0x4F, 0x4D, 0x15, 0x11, 
+  0xA1, 0x99, 0xA2, 0x11, 0x60, 0x65, 0xCC, 0x49, 0x05, 0x1D, 0x1F, 0xC3, 
+  0x8E, 0x15, 0x64, 0xED, 0xB9, 0x9A, 0x02, 0x90, 0x03, 0x1D, 0xAA, 0x0D, 
+  0x45, 0xD8, 0x72, 0x92, 0x01, 0x83, 0x53, 0x6E, 0x55, 0x06, 0xC7, 0xC4, 
+  0x02, 0xB4, 0x1B, 0x19, 0x24, 0x0F, 0x8D, 0x12, 0xE5, 0xAA, 0xAA, 0xF3, 
+  0x03, 0x00, 0x5F, 0x66, 0x11, 0x11, 0x7F, 0x73, 0x8F, 0x57, 0x1B, 0x41, 
+  0x8D, 0x39, 0x1B, 0x19, 0x5D, 0x3B, 0x3D, 0xFB, 0x13, 0x5D, 0x03, 0x70, 
+  0x62, 0x1C, 0x5D, 0x6A, 0x46, 0x37, 0x19, 0x41, 0xDA, 0x62, 0xF8, 0x1D, 
+  0x7F, 0x7B, 0x3E, 0x58, 0x14, };