The story so far

17 files changed, 1235 insertions, 0 deletions

diff --git a/lpg/libqr/.gitignore b/lpg/libqr/.gitignore
new file mode 100644
index 0000000..dbfb6fb
--- /dev/null
+++ b/lpg/libqr/.gitignore
@@ -0,0 +1,5 @@
+*~
+*.o
+*.a
+*.so
+test
diff --git a/lpg/libqr/Makefile b/lpg/libqr/Makefile
new file mode 100644
index 0000000..e36b09f
--- /dev/null
+++ b/lpg/libqr/Makefile
@@ -0,0 +1,25 @@
+OBJECTS :=      bitstream.o     \
+                code-common.o   \
+                code-create.o   \
+                code-parse.o    \
+                code-render.o   \
+                data-common.o   \
+                data-create.o   \
+                data-parse.o
+
+CFLAGS := -std=c89 -pedantic -I. -Wall
+CFLAGS += -g
+#CFLAGS += -O3 -DNDEBUG
+
+all : libqr test
+
+$(OBJECTS) : $(wildcard *.h qr/*.h)
+
+libqr : libqr.a($(OBJECTS))
+
+test : libqr.a test.c
+
+.PHONY : clean
+clean:
+	$(RM) qr/*~ *~ *.o *.a *.so test
+
diff --git a/lpg/libqr/bitstream.c b/lpg/libqr/bitstream.c
new file mode 100644
index 0000000..a2b2b58
--- /dev/null
+++ b/lpg/libqr/bitstream.c
@@ -0,0 +1,203 @@
+/**
+ * It would perhaps be more sensible just to store the bits
+ * as an array of char or similar, but this way is more fun.
+ * This is a pretty inefficient implementation, althought I
+ * suspect that won't be a problem.
+ */
+
+#include <stdlib.h>
+#include <string.h>
+#include <limits.h>
+#include <assert.h>
+
+#include "bitstream.h"
+
+#define MAX(a, b) ((a) < (b) ? (b) : (a))
+#define MIN(a, b) ((a) > (b) ? (b) : (a))
+
+struct bitstream {
+        size_t pos;    /* bits */
+        size_t count;  /* bits */
+        size_t bufsiz; /* bytes */
+        unsigned char * buffer;
+};
+
+static size_t bits_to_bytes(size_t bits)
+{
+        return (bits / CHAR_BIT) + (bits % CHAR_BIT != 0);
+}
+
+static int ensure_available(struct bitstream * stream, size_t bits)
+{
+        size_t need_bits = stream->pos + bits;
+        size_t need_bytes = need_bits / CHAR_BIT + ((need_bits % CHAR_BIT) ? 0 : 1);
+        size_t newsize;
+
+        if (stream->bufsiz >= need_bytes)
+                return 0;
+
+        newsize = MAX(stream->bufsiz, 100);
+        while (newsize < need_bytes)
+                newsize *= 2;
+
+        return bitstream_resize(stream, newsize);
+}
+
+struct bitstream * bitstream_create(void)
+{
+        struct bitstream * obj;
+
+        obj = malloc(sizeof(*obj));
+
+        if (obj) {
+                obj->pos    = 0;
+                obj->count  = 0;
+                obj->bufsiz = 0;
+                obj->buffer = 0;
+        }
+
+        return obj;
+}
+
+int bitstream_resize(struct bitstream * stream, size_t bits)
+{
+        size_t newsize;
+        void * newbuf;
+
+        newsize = bits_to_bytes(bits);
+        newbuf = realloc(stream->buffer, newsize);
+
+        if (newbuf) {
+                stream->bufsiz = newsize;
+                stream->buffer = newbuf;
+        }
+
+        return newbuf ? 0 : -1;
+}
+
+void bitstream_destroy(struct bitstream * stream)
+{
+        free(stream->buffer);
+        free(stream);
+}
+
+struct bitstream * bitstream_copy(const struct bitstream * src)
+{
+        struct bitstream * ret;
+
+        ret = bitstream_create();
+        if (!ret)
+                return 0;
+
+        if (bitstream_resize(ret, src->count) != 0) {
+                free(ret);
+                return 0;
+        }
+
+        ret->pos   = src->pos;
+        ret->count = src->count;
+        memcpy(ret->buffer, src->buffer, src->bufsiz);
+
+        return ret;
+}
+
+void bitstream_seek(struct bitstream * stream, size_t pos)
+{
+        assert(pos <= stream->count);
+        stream->pos = pos;
+}
+
+size_t bitstream_tell(const struct bitstream * stream)
+{
+        return stream->pos;
+}
+
+size_t bitstream_remaining(const struct bitstream * stream)
+{
+        return stream->count - stream->pos;
+}
+
+size_t bitstream_size(const struct bitstream * stream)
+{
+        return stream->count;
+}
+
+unsigned int bitstream_read(struct bitstream * stream, size_t bits)
+{
+        unsigned int result = 0;
+        unsigned char * byte;
+        size_t bitnum;
+
+        assert(bitstream_remaining(stream) >= bits);
+
+        byte = stream->buffer + (stream->pos / CHAR_BIT);
+        bitnum = stream->pos % CHAR_BIT;
+
+        stream->pos += bits;
+
+        while (bits-- > 0) {
+                int bit = (*byte >> bitnum++) & 0x1;
+                result = (result << 1) | bit;
+                if (bitnum == CHAR_BIT) {
+                        bitnum = 0;
+                        ++byte;
+                }                
+        }
+
+        return result;
+}
+
+void bitstream_unpack(struct bitstream * stream,
+                      unsigned int *     result,
+                      size_t             count,
+                      size_t             bitsize)
+{
+        assert(bitstream_remaining(stream) >= (count * bitsize));
+
+        while (count--)
+                *(result++) = bitstream_read(stream, bitsize);
+}
+
+int bitstream_write(struct bitstream * stream,
+                    unsigned int       value,
+                    size_t             bits)
+{
+        unsigned char * byte;
+        size_t bitnum;
+
+        if (ensure_available(stream, bits) != 0)
+                return -1;
+
+        byte = stream->buffer + (stream->pos / CHAR_BIT);
+        bitnum = stream->pos % CHAR_BIT;
+
+        stream->pos += bits;
+        stream->count = stream->pos; /* truncate */
+
+        while (bits-- > 0) {
+                int bit = (value >> bits) & 0x1;
+                unsigned char mask = 1 << bitnum++;
+                *byte = (*byte & ~mask) | (bit ? mask : 0);
+                if (bitnum == CHAR_BIT) {
+                        bitnum = 0;
+                        ++byte;
+                }
+        }
+
+        return 0;
+}
+
+int bitstream_pack(struct bitstream *   stream,
+                   const unsigned int * values,
+                   size_t               count,
+                   size_t               bitsize)
+{
+        if (ensure_available(stream, count * bitsize) != 0)
+                return -1;
+
+        while (count--)
+                bitstream_write(stream, *(values++), bitsize);
+
+        return 0;
+}
+
diff --git a/lpg/libqr/bitstream.h b/lpg/libqr/bitstream.h
new file mode 100644
index 0000000..12412bc
--- /dev/null
+++ b/lpg/libqr/bitstream.h
@@ -0,0 +1,44 @@
+#ifndef QR_BITSTREAM_H
+#define QR_BITSTREAM_H
+
+#include <stddef.h>
+
+/**
+ * Note: when writing / reading multiple bits, the
+ * _most_ significant bits come first in the stream.
+ * (That is, the order you would naturally write the
+ * number in binary)
+ */
+
+struct bitstream;
+
+struct bitstream * bitstream_create(void);
+int                bitstream_resize(struct bitstream *, size_t bits);
+void               bitstream_destroy(struct bitstream *);
+struct bitstream * bitstream_copy(const struct bitstream *);
+
+void bitstream_seek(struct bitstream *, size_t pos);
+size_t bitstream_tell(const struct bitstream *);
+size_t bitstream_remaining(const struct bitstream *);
+size_t bitstream_size(const struct bitstream *);
+
+unsigned int bitstream_read(struct bitstream *, size_t bits);
+
+void bitstream_unpack(struct bitstream *,
+                      unsigned int * result,
+                      size_t         count,
+                      size_t         bitsize);
+
+int bitstream_write(struct bitstream *,
+                    unsigned int value,
+                    size_t       bits);
+
+int bitstream_pack(struct bitstream *,
+                   const unsigned int * values,
+                   size_t               count,
+                   size_t               bitsize);
+
+int bitstream_cat(struct bitstream *, const struct bitstream * src);
+
+#endif
+
diff --git a/lpg/libqr/code-common.c b/lpg/libqr/code-common.c
new file mode 100644
index 0000000..08b16df
--- /dev/null
+++ b/lpg/libqr/code-common.c
@@ -0,0 +1,36 @@
+#include <stdlib.h>
+#include <qr/code.h>
+
+#include "code-common.h"
+
+void qr_code_destroy(struct qr_code * code)
+{
+        free(code->modules);
+        free(code);
+}
+
+int qr_code_width(const struct qr_code * code)
+{
+        return code_side_length(code->format);
+}
+
+int code_side_length(int format)
+{
+        return format * 4 + 17;
+}
+
+int code_finder_count(int format)
+{
+        int x = format / 7;
+        return format > 1 ? x*x + 4*x + 1 : 0;        
+}
+
+size_t code_total_capacity(int format)
+{
+        /* XXX: figure out the "correct" formula */
+        return 160
+             +  25 * code_finder_count(format)
+             -  10 * (format / 7)
+             +   2 * code_side_length(format);
+}
+
diff --git a/lpg/libqr/code-common.h b/lpg/libqr/code-common.h
new file mode 100644
index 0000000..52666e6
--- /dev/null
+++ b/lpg/libqr/code-common.h
@@ -0,0 +1,19 @@
+#ifndef CODE_COMMON_H
+#define CODE_COMMON_H
+
+#include <qr/code.h>
+#include "bitstream.h"
+
+struct qr_code {
+        int              format;
+        unsigned char *  modules;
+        size_t           line_stride;
+};
+
+int code_side_length(int format);
+int code_finder_count(int format);
+
+size_t code_total_capacity(int format);
+
+#endif
+
diff --git a/lpg/libqr/code-create.c b/lpg/libqr/code-create.c
new file mode 100644
index 0000000..d09c2fe
--- /dev/null
+++ b/lpg/libqr/code-create.c
@@ -0,0 +1,121 @@
+#include <stdlib.h>
+#include <limits.h>
+#include <assert.h>
+#include <qr/code.h>
+
+#include "code-common.h"
+#include "data-common.h"
+
+#define MIN(a, b) ((b) < (a) ? (b) : (a))
+
+#include <stdio.h>
+static void x_dump(struct bitstream * bits)
+{
+        size_t i, n;
+
+        bitstream_seek(bits, 0);
+        n = bitstream_size(bits);
+        for (i = 0; i < n; ++i) {
+                printf("%d", bitstream_read(bits, 1));
+                if (i % 8 == 7)
+                        printf(" ");
+                if ((i+1) % (7 * 8) == 0)
+                        printf("\n");
+        }
+        printf("\n");
+}
+
+static int add_ecc(struct bitstream * bits, int format, enum qr_ec_level ec)
+{
+        puts("Before ecc:");
+        x_dump(bits);
+
+        return -1;
+}
+
+static int pad_data(struct bitstream * bits, size_t limit)
+{
+        /* This function is not very nice. Sorry. */
+
+        size_t count, n;
+
+        assert(bitstream_size(bits) <= limit);
+
+        if (bitstream_resize(bits, limit) != 0)
+                return -1;
+
+        n = bitstream_size(bits);
+        bitstream_seek(bits, n);
+        count = limit - n;
+
+        /* First append the terminator (0000) if possible,
+         * and pad with zeros up to an 8-bit boundary
+         */
+        n = (n + 4) % 8;
+        if (n != 0)
+                n = 8 - n;
+        n = MIN(count, n + 4);
+        bitstream_write(bits, 0, n);
+        count -= n;
+
+        assert(count % 8 == 0); /* since data codewords are 8 bits */
+
+        /* Finally pad with the repeating sequence 11101100 00010001 */
+        while (count >= 16) {
+                bitstream_write(bits, 0xEC11, 16);
+                count -= 16;
+        }
+        if (count > 0) {
+                assert(count == 8);
+                bitstream_write(bits, 0xEC, 8);
+        }
+
+        return 0;
+}
+
+static struct bitstream * make_data(int                format,
+                                    enum qr_ec_level   ec,
+                                    struct bitstream * data)
+{
+        size_t data_bits = 16 * 8 /*XXX*/;
+        struct bitstream * out;
+
+        out = bitstream_copy(data);
+        if (!out)
+                return 0;
+
+        if (pad_data(out, data_bits) != 0)
+                goto fail;
+
+        if (add_ecc(out, format, ec) != 0)
+                goto fail;
+
+        return out;
+fail:
+        bitstream_destroy(out);
+        return 0;
+}
+
+struct qr_code * qr_code_create(enum qr_ec_level       ec,
+                                const struct qr_data * data)
+{
+        struct qr_code * code;
+        struct bitstream * ecdata;
+
+        code = malloc(sizeof(*code));
+        if (!code)
+                return 0;
+
+        code->format = data->format;
+        ecdata = make_data(data->format, ec, data->bits);
+
+        if (!ecdata) {
+                free(code);
+                return 0;
+        }
+
+        /* TODO: allocate bitmap; layout */
+
+        return 0;
+}
+
diff --git a/lpg/libqr/code-parse.c b/lpg/libqr/code-parse.c
new file mode 100644
index 0000000..0d3a71d
--- /dev/null
+++ b/lpg/libqr/code-parse.c
@@ -0,0 +1,12 @@
+#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,
+                               size_t       line_count)
+{
+        return 0;
+}
+
diff --git a/lpg/libqr/code-render.c b/lpg/libqr/code-render.c
new file mode 100644
index 0000000..cdffe24
--- /dev/null
+++ b/lpg/libqr/code-render.c
@@ -0,0 +1,119 @@
+#include <string.h>
+#include <limits.h>
+#include <assert.h>
+#include <qr/code.h>
+
+#include "code-common.h"
+
+/* CHAR_BIT | mod_bits  (multi-byte) */
+static void render_line_1(unsigned char *       out,
+                          const unsigned char * in,
+                          size_t                mod_bits,
+                          size_t                dim,
+                          unsigned long         mark,
+                          unsigned long         space)
+{
+        unsigned char in_mask;
+        size_t n, b;
+
+        in_mask = 1;
+        n = dim;
+
+        while (n-- > 0) {
+                unsigned long v = (*in & in_mask) ? mark : space;
+
+                if ((in_mask <<= 1) == 0) {
+                        in_mask = 1;
+                        ++in;
+                }
+
+                b = mod_bits / CHAR_BIT;
+                while (b-- > 0) {
+                        *out++ = (unsigned char) v;
+                        v >>= CHAR_BIT;
+                }
+        }
+}
+
+/* mod_bits | CHAR_BIT  (packed) */
+static void render_line_2(unsigned char *       out,
+                          const unsigned char * in,
+                          size_t                mod_bits,
+                          size_t                dim,
+                          unsigned long         mark,
+                          unsigned long         space)
+{
+        unsigned char in_mask;
+        size_t n, b, step, shift;
+
+        in_mask = 1;
+        step = CHAR_BIT / mod_bits;
+        shift = CHAR_BIT - mod_bits;
+        n = dim;
+
+        while (n > 0) {
+                unsigned char tmp = 0;
+
+                b = step;
+                while (b-- > 0) {
+                        unsigned long v = (*in & in_mask) ? mark : space;
+
+                        if ((in_mask <<= 1) == 0) {
+                                in_mask = 1;
+                                ++in;
+                        }
+
+                        tmp = (tmp >> mod_bits) | (v << shift);
+                        if (--n == 0) {
+                                tmp >>= b * mod_bits;
+                                break;
+                        }
+                };
+
+                *out++ = tmp;
+        }
+}
+
+void qr_code_render(const struct qr_code * code,
+                    void *                 buffer,
+                    size_t                 mod_bits,
+                    size_t                 line_stride,
+                    size_t                 line_repeat,
+                    unsigned long          mark,
+                    unsigned long          space)
+{
+        unsigned char * out;
+        const unsigned char * in;
+        size_t n, dim;
+        int pack;
+
+        pack = (mod_bits < CHAR_BIT);
+        assert(!pack || (CHAR_BIT % mod_bits == 0));
+        assert( pack || (mod_bits % CHAR_BIT == 0));
+
+        in = code->modules;
+        out = buffer;
+        dim = qr_code_width(code);
+
+        n = dim;
+        while (n-- > 0) {
+                size_t rpt;
+                unsigned char * next;
+
+                if (pack)
+                        render_line_2(out, in, mod_bits, dim, mark, space);
+                else
+                        render_line_1(out, in, mod_bits, dim, mark, space);
+
+                rpt = line_repeat;
+                next = out + line_stride;
+                while (rpt-- > 0) {
+                        memcpy(next, out, line_stride);
+                        next += line_stride;
+                }
+
+                in += code->line_stride;
+                out = next;
+        }
+}
+
diff --git a/lpg/libqr/data-common.c b/lpg/libqr/data-common.c
new file mode 100644
index 0000000..123e5c4
--- /dev/null
+++ b/lpg/libqr/data-common.c
@@ -0,0 +1,58 @@
+#include <stdlib.h>
+#include <qr/data.h>
+
+#include "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 */
+};
+
+void qr_free_data(struct qr_data * data)
+{
+        bitstream_destroy(data->bits);
+        free(data);
+}
+
+size_t get_size_field_length(int format, enum qr_data_type type)
+{
+        static const size_t QR_SIZE_LENGTHS[3][4] = {
+                { 10,  9,  8,  8 },
+                { 12, 11, 16, 10 },
+                { 14, 13, 16, 12 }
+        };
+        int row, col;
+
+        switch (type) {
+        case QR_DATA_NUMERIC:   col = 0; break;
+        case QR_DATA_ALPHA:     col = 1; break;
+        case QR_DATA_8BIT:      col = 2; break;
+        case QR_DATA_KANJI:     col = 3; break;
+        default:                return 0;
+        }
+
+        if (format < 10)
+                row = 0;
+        else if (format < 27)
+                row = 1;
+        else
+                row = 2;
+
+        return QR_SIZE_LENGTHS[row][col];
+}
+
diff --git a/lpg/libqr/data-common.h b/lpg/libqr/data-common.h
new file mode 100644
index 0000000..d5f6e45
--- /dev/null
+++ b/lpg/libqr/data-common.h
@@ -0,0 +1,19 @@
+#ifndef DATA_COMMON_H
+#define DATA_COMMON_H
+
+#include <qr/data.h>
+
+#include "bitstream.h"
+
+struct qr_data {
+        int                format; /* 1 ~ 40 */
+        struct bitstream * bits;
+        size_t             offset;
+};
+
+extern const enum qr_data_type QR_TYPE_CODES[16];
+
+size_t get_size_field_length(int format, enum qr_data_type);
+
+#endif
+
diff --git a/lpg/libqr/data-create.c b/lpg/libqr/data-create.c
new file mode 100644
index 0000000..2910997
--- /dev/null
+++ b/lpg/libqr/data-create.c
@@ -0,0 +1,223 @@
+/**
+ * Not "pure" C - only works with ASCII
+ */
+
+/** XXX: check that the data will fit! **/
+/** NOTE: should store ec type in qr_data **/
+
+#include <ctype.h>
+#include <stdlib.h>
+#include <qr/data.h>
+
+#include "bitstream.h"
+#include "data-common.h"
+
+static void write_type_and_length(struct qr_data *  data,
+                                  enum qr_data_type type,
+                                  size_t            length)
+{
+        (void)bitstream_write(data->bits, QR_TYPE_CODES[type], 4);
+        (void)bitstream_write(data->bits, length,
+                get_size_field_length(data->format, type));
+}
+
+static struct qr_data * encode_numeric(struct qr_data * data,
+                                       const char *     input,
+                                       size_t           length)
+{
+        struct bitstream * stream = data->bits;
+        size_t bits;
+
+        bits = 4 + get_size_field_length(data->format, QR_DATA_NUMERIC)
+                 + 10 * (length / 3);
+
+        if (length % 3 == 1)
+                bits += 4;
+        else if (length % 3 == 2)
+                bits += 7;
+
+        stream = data->bits;
+        if (bitstream_resize(stream,
+                        bitstream_size(stream) + bits) != 0)
+                return 0;
+
+        write_type_and_length(data, QR_DATA_NUMERIC, length);
+
+        for (; length >= 3; length -= 3) {
+                unsigned int x;
+
+                if (!isdigit(input[0]) ||
+                    !isdigit(input[1]) ||
+                    !isdigit(input[2]))
+                        return 0;
+
+                x = (input[0] - '0') * 100
+                  + (input[1] - '0') * 10
+                  + (input[2] - '0');
+                bitstream_write(stream, x, 10);
+                input += 3;
+        }
+
+        if (length > 0) {
+                unsigned int x;
+
+                if (!isdigit(*input))
+                        return 0;
+
+                x = *input++ - '0';
+
+                if (length == 2) {
+                        if (!isdigit(*input))
+                                return 0;
+                        x = x * 10 + (*input - '0');
+                }
+
+                bitstream_write(stream, x, length == 2 ? 7 : 4);
+        }
+
+        return data;
+}
+
+static int get_alpha_code(char c)
+{
+        if (isdigit(c))
+                return c - '0';
+        else if (isalpha(c))
+                return toupper(c) - 'A' + 10;
+
+        switch (c) {
+        case ' ': return 36;
+        case '$': return 37;
+        case '%': return 38;
+        case '*': return 39;
+        case '+': return 40;
+        case '-': return 41;
+        case '.': return 42;
+        case '/': return 43;
+        case ':': return 44;
+        default:  return -1;
+        }
+}
+
+static struct qr_data * encode_alpha(struct qr_data * data,
+                                     const char *     input,
+                                     size_t           length)
+{
+        struct bitstream * stream = data->bits;
+        size_t bits;
+
+        bits = 4 + get_size_field_length(data->format, QR_DATA_ALPHA)
+                 + 11 * (length / 2)
+                 + 6 * (length % 2);
+
+        stream = data->bits;
+        if (bitstream_resize(stream,
+                        bitstream_size(stream) + bits) != 0)
+                return 0;
+
+        write_type_and_length(data, QR_DATA_ALPHA, length);
+
+        for (; length >= 2; length -= 2) {
+                unsigned int x;
+                int c1, c2;
+
+                c1 = get_alpha_code(*input++);
+                c2 = get_alpha_code(*input++);
+
+                if (c1 < 0 || c2 < 0)
+                        return 0;
+
+                x = c1 * 45 + c2;
+                bitstream_write(stream, x, 11);
+        }
+
+        if (length > 0) {
+                int c = get_alpha_code(*input);
+
+                if (c < 0)
+                        return 0;
+
+                bitstream_write(stream, c, 6);
+        }
+
+        return data;
+}
+
+static struct qr_data * encode_8bit(struct qr_data * data,
+                                    const char *     input,
+                                    size_t           length)
+{
+        struct bitstream * stream = data->bits;
+        size_t bits;
+
+        bits = 4 + get_size_field_length(data->format, QR_DATA_8BIT)
+                 + 8 * length;
+
+        stream = data->bits;
+        if (bitstream_resize(stream,
+                        bitstream_size(stream) + bits) != 0)
+                return 0;
+
+        write_type_and_length(data, QR_DATA_8BIT, length);
+
+        while (length--)
+                bitstream_write(stream, *input++, 8);
+
+        return data;
+}
+
+static struct qr_data * encode_kanji(struct qr_data * data,
+                                     const char *     input,
+                                     size_t           length)
+{
+        return 0;
+}
+
+struct qr_data * qr_create_data(int               format,
+                                enum qr_data_type type,
+                                const char *      input,
+                                size_t            length)
+{
+        struct qr_data * data;
+
+        if (format < 1 || format > 40)
+                return 0;
+
+        data = malloc(sizeof(*data));
+        if (!data)
+                return 0;
+
+        data->format = format;
+        data->bits   = bitstream_create();
+        data->offset = 0;
+
+        if (data->bits) {
+                struct qr_data * ret;
+
+                switch (type) {
+                case QR_DATA_NUMERIC:
+                        ret = encode_numeric(data, input, length); break;
+                case QR_DATA_ALPHA:
+                        ret = encode_alpha(data, input, length); break;
+                case QR_DATA_8BIT:
+                        ret = encode_8bit(data, input, length); break;
+                case QR_DATA_KANJI:
+                        ret = encode_kanji(data, input, length); break;
+                default:
+                        /* unsupported / invalid */
+                        ret = 0;
+                        break;
+                }
+
+                if (!ret) {
+                        bitstream_destroy(data->bits);
+                        free(data);
+                }
+
+                return ret;
+        } else {
+                free(data);
+                return 0;
+        }
+}
+
diff --git a/lpg/libqr/data-parse.c b/lpg/libqr/data-parse.c
new file mode 100644
index 0000000..9129ed7
--- /dev/null
+++ b/lpg/libqr/data-parse.c
@@ -0,0 +1,237 @@
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <qr/data.h>
+
+#include "bitstream.h"
+#include "data-common.h"
+
+static enum qr_data_type read_data_type(struct bitstream * stream)
+{
+        const size_t length = 4;
+        unsigned int type;
+
+        if (bitstream_remaining(stream) < length)
+                return QR_DATA_INVALID;
+
+        type = bitstream_read(stream, length);
+        assert(type < 16);
+
+        return QR_TYPE_CODES[type];
+}
+
+static enum qr_data_type parse_numeric(const struct qr_data * data,
+                                       char **                output,
+                                       size_t *               length)
+{
+        struct bitstream * stream;
+        size_t field_len, bits;
+	unsigned int digits;
+	unsigned int chunk;
+	char * p, * buffer;
+
+        stream = data->bits;
+        buffer = 0;
+
+        field_len = get_size_field_length(data->format, QR_DATA_NUMERIC);
+        if (bitstream_remaining(stream) < field_len)
+                goto invalid;
+
+	digits = bitstream_read(stream, field_len);
+
+	bits = (digits / 3) * 10;
+	if (digits % 3 == 1)
+		bits += 4;
+	else if (digits % 3 == 2)
+		bits += 7;
+
+	if (bitstream_remaining(stream) < bits)
+		goto invalid;
+
+	buffer = malloc(digits + 1);
+	if (!buffer)
+		goto invalid;
+
+	p = buffer;
+
+	for (; bits >= 10; bits -= 10) {
+		chunk = bitstream_read(stream, 10);
+                if (chunk >= 1000)
+                        goto invalid;
+		sprintf(p, "%03u", chunk);
+                p += 3;
+	}
+
+        if (bits > 0) {
+                chunk = bitstream_read(stream, bits);
+                if (chunk >= (bits >= 7 ? 100 : 10))
+                        goto invalid;
+                sprintf(p, "%0*u", bits >= 7 ? 2 : 1, chunk);
+        }
+
+        *output = buffer;
+        *length = digits;
+
+        return QR_DATA_NUMERIC;
+invalid:
+        free(buffer);
+        return QR_DATA_INVALID;
+}
+
+static enum qr_data_type parse_alpha(const struct qr_data * data,
+                                     char **                output,
+                                     size_t *               length)
+{
+        static const char charset[45] =
+                "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:";
+        struct bitstream * stream;
+        size_t field_len, bits;
+	unsigned int chars;
+	unsigned int chunk;
+	char * p, * buffer;
+
+        stream = data->bits;
+        buffer = 0;
+
+        field_len = get_size_field_length(data->format, QR_DATA_ALPHA);
+        if (bitstream_remaining(stream) < field_len)
+                goto invalid;
+
+	chars = bitstream_read(stream, field_len);
+
+	bits = (chars / 2) * 11;
+	if (chars % 2 == 1)
+		bits += 6;
+
+	if (bitstream_remaining(stream) < bits)
+		goto invalid;
+
+	buffer = malloc(chars + 1);
+	if (!buffer)
+		goto invalid;
+
+	p = buffer;
+
+	for (; bits >= 11; bits -= 11) {
+                unsigned int c1, c2;
+		chunk = bitstream_read(stream, 11);
+                c1 = chunk / 45;
+                c2 = chunk % 45;
+                if (c1 >= 45)
+                        goto invalid;
+                *p++ = charset[c1];
+                *p++ = charset[c2];
+	}
+
+        if (bits > 0) {
+                chunk = bitstream_read(stream, bits);
+                if (chunk >= 45)
+                        goto invalid;
+                *p = charset[chunk];
+        }
+
+        *output = buffer;
+        *length = chars;
+
+        return QR_DATA_ALPHA;
+invalid:
+        free(buffer);
+        return QR_DATA_INVALID;
+}
+
+static enum qr_data_type parse_8bit(const struct qr_data * data,
+                                    char **                output,
+                                    size_t *               length)
+{
+        struct bitstream * stream;
+        size_t field_len;
+	unsigned int bytes;
+	char * p;
+
+        stream = data->bits;
+
+        field_len = get_size_field_length(data->format, QR_DATA_8BIT);
+        if (bitstream_remaining(stream) < field_len)
+                return QR_DATA_INVALID;
+
+	bytes = bitstream_read(stream, field_len);
+
+	if (bitstream_remaining(stream) < bytes * 8)
+		return QR_DATA_INVALID;
+
+	*output = malloc(bytes + 1);
+	if (!*output)
+		return QR_DATA_INVALID;
+
+        p = *output;
+        *length = bytes;
+
+        while (bytes-- > 0)
+                *p++ = bitstream_read(stream, 8);
+
+        *p = '\0';
+
+        return QR_DATA_8BIT;
+}
+
+static enum qr_data_type parse_kanji(const struct qr_data * data,
+                                     char **                output,
+                                     size_t *               length)
+{
+        return QR_DATA_INVALID;
+}
+
+enum qr_data_type qr_get_data_type(const struct qr_data * data)
+{
+        bitstream_seek(data->bits, data->offset);
+        return read_data_type(data->bits);
+}
+
+int qr_get_data_length(const struct qr_data * data) 
+{
+        size_t field_len;
+        enum qr_data_type type;
+
+        bitstream_seek(data->bits, data->offset);
+
+        type = read_data_type(data->bits);
+
+        switch (type) {
+        case QR_DATA_NUMERIC:
+        case QR_DATA_ALPHA:
+        case QR_DATA_8BIT:
+        case QR_DATA_KANJI:
+                field_len = get_size_field_length(data->format, type);
+                break;
+        default:
+                /* unsupported / invalid */
+                return -1;
+        }
+
+        if (bitstream_remaining(data->bits) < field_len)
+                return -1;
+
+        return (int) bitstream_read(data->bits, field_len);
+}
+
+enum qr_data_type qr_parse_data(const struct qr_data * input,
+                                char **                output,
+                                size_t *               length)
+{
+        bitstream_seek(input->bits, input->offset);
+
+        switch (read_data_type(input->bits)) {
+        case QR_DATA_NUMERIC:
+                return parse_numeric(input, output, length);
+        case QR_DATA_ALPHA:
+                return parse_alpha(input, output, length);
+        case QR_DATA_8BIT:
+                return parse_8bit(input, output, length);
+        case QR_DATA_KANJI:
+                return parse_kanji(input, output, length);
+        default:
+                /* unsupported / invalid */
+                return QR_DATA_INVALID;
+        }
+}
+
diff --git a/lpg/libqr/qr/code.h b/lpg/libqr/qr/code.h
new file mode 100644
index 0000000..6ae1aa9
--- /dev/null
+++ b/lpg/libqr/qr/code.h
@@ -0,0 +1,35 @@
+#ifndef QR_CODE_H
+#define QR_CODE_H
+
+#include <stddef.h>
+#include "types.h"
+
+enum qr_ec_level {
+        QR_EC_LEVEL_L,
+        QR_EC_LEVEL_M,
+        QR_EC_LEVEL_Q,
+        QR_EC_LEVEL_H
+};
+
+struct qr_code * qr_code_create(enum qr_ec_level       ec,
+                                const struct qr_data * data);
+
+void qr_code_destroy(struct qr_code *);
+
+int qr_code_width(const struct qr_code *);
+
+struct qr_code * qr_code_parse(const void * buffer,
+                               size_t       line_bits,
+                               size_t       line_stride,
+                               size_t       line_count);
+
+void qr_code_render(const struct qr_code * code,
+                    void *                 buffer,
+                    size_t                 mod_bits,
+                    size_t                 line_stride,
+                    size_t                 line_repeat,
+                    unsigned long          mark,
+                    unsigned long          space);
+
+#endif
+
diff --git a/lpg/libqr/qr/data.h b/lpg/libqr/qr/data.h
new file mode 100644
index 0000000..5fbdded
--- /dev/null
+++ b/lpg/libqr/qr/data.h
@@ -0,0 +1,34 @@
+#ifndef QR_DATA_H
+#define QR_DATA_H
+
+#include <stddef.h>
+#include "types.h"
+
+enum qr_data_type {
+        QR_DATA_INVALID = -1,
+        QR_DATA_ECI     =  7,
+        QR_DATA_NUMERIC =  1,
+        QR_DATA_ALPHA   =  2,
+        QR_DATA_8BIT    =  4,
+        QR_DATA_KANJI   =  8, /* JIS X 0208 */
+        QR_DATA_MIXED   =  3,
+        QR_DATA_FNC1    =  9
+};
+
+struct qr_data * qr_create_data(int               format, /* 1 ~ 40 */
+                                enum qr_data_type type,
+                                const char *      input,
+                                size_t            length);
+
+void qr_free_data(struct qr_data *);
+
+enum qr_data_type qr_get_data_type(const struct qr_data *);
+
+int qr_get_data_length(const struct qr_data *);
+
+enum qr_data_type qr_parse_data(const struct qr_data * input,
+                                char **                output,
+                                size_t *               length);
+
+#endif
+
diff --git a/lpg/libqr/qr/types.h b/lpg/libqr/qr/types.h
new file mode 100644
index 0000000..bb44cde
--- /dev/null
+++ b/lpg/libqr/qr/types.h
@@ -0,0 +1,8 @@
+#ifndef QR_TYPES_H
+#define QR_TYPES_H
+
+struct qr_data;
+struct qr_code;
+
+#endif
+
diff --git a/lpg/libqr/test.c b/lpg/libqr/test.c
new file mode 100644
index 0000000..76d0b97
--- /dev/null
+++ b/lpg/libqr/test.c
@@ -0,0 +1,37 @@
+#include <stdio.h>
+#include <string.h>
+#include <assert.h>
+#include <qr/code.h>
+#include <qr/data.h>
+
+#include "bitstream.h"
+
+int main() {
+
+        struct qr_code * code;
+        struct qr_data * data;
+        enum qr_data_type type;
+        char *str;
+        size_t len;
+
+        type = QR_DATA_NUMERIC;
+        str = "01234567";
+        len = strlen(str);
+
+        data = qr_create_data(1, type, str, len);
+        assert(data);
+        assert(qr_get_data_type(data) == type);
+        assert(qr_get_data_length(data) == len);
+
+        type = qr_parse_data(data, &str, &len);
+        printf("[%d] %d\n", type, (int)len);
+        printf("\"%s\"\n", str);
+
+        code = qr_code_create(QR_EC_LEVEL_M, data);
+        assert(code);
+
+        printf("Code width %d\n", qr_code_width(code));
+
+	return 0;
+}
+