From 7b61f48876af1c0a91c32355862e8bcb2e6d126c Mon Sep 17 00:00:00 2001 From: Leo Howell Date: Tue, 29 Sep 2009 17:16:07 +0900 Subject: add TODO --- lpg/libqr/TODO | 25 +++++++++++++++++++++++++ 1 file changed, 25 insertions(+) create mode 100644 lpg/libqr/TODO (limited to 'lpg/libqr/TODO') diff --git a/lpg/libqr/TODO b/lpg/libqr/TODO new file mode 100644 index 0000000..6efa259 --- /dev/null +++ b/lpg/libqr/TODO @@ -0,0 +1,25 @@ +* Get sample generated OK +* Fix generation for all sizes (alignment pattern) +* Auto-sizing for data +* Sample app +* Merge some files +* Fix XXX, TODO +* Tidy code +* RELEASE v0.1 + +* Parsing +* RELEASE v0.2 + +* Detection +* RELEASE v0.3 + +* Test suite +* No-malloc +* Optimize +* Documentation +* RELEASE v0.4 (BETA) + +* RELEASE v1.0 + +* Other data types + -- cgit v1.2.3-70-g09d2 From 688c1b52ed356d024ba2e72ba52f7da64b7d74ed Mon Sep 17 00:00:00 2001 From: Leo Howell Date: Tue, 3 Nov 2009 00:12:30 +0900 Subject: generate alignment pattern --- lpg/libqr/TODO | 2 -- lpg/libqr/code-common.c | 43 +++++++++++++++++++++++++++++++++++++++++++ lpg/libqr/code-common.h | 2 ++ lpg/libqr/code-create.c | 23 ++++++++++++++++++++++- lpg/libqr/code-layout.c | 27 +++++++++++++++++++++++++-- 5 files changed, 92 insertions(+), 5 deletions(-) (limited to 'lpg/libqr/TODO') diff --git a/lpg/libqr/TODO b/lpg/libqr/TODO index 6efa259..eb35da8 100644 --- a/lpg/libqr/TODO +++ b/lpg/libqr/TODO @@ -1,5 +1,3 @@ -* Get sample generated OK -* Fix generation for all sizes (alignment pattern) * Auto-sizing for data * Sample app * Merge some files diff --git a/lpg/libqr/code-common.c b/lpg/libqr/code-common.c index 150dfc5..7c3c119 100644 --- a/lpg/libqr/code-common.c +++ b/lpg/libqr/code-common.c @@ -38,3 +38,46 @@ 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 */ +}; + diff --git a/lpg/libqr/code-common.h b/lpg/libqr/code-common.h index 0459708..9900e4e 100644 --- a/lpg/libqr/code-common.h +++ b/lpg/libqr/code-common.h @@ -12,5 +12,7 @@ struct qr_code { 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 36ebb24..ae23acc 100644 --- a/lpg/libqr/code-create.c +++ b/lpg/libqr/code-create.c @@ -79,6 +79,8 @@ static int draw_functional(struct qr_code * code, struct qr_bitmap * bmp; int dim = qr_code_width(code); int i; + int x, y; + int am_side; bmp = qr_bitmap_create(dim, dim, 0); if (!bmp) @@ -95,7 +97,26 @@ static int draw_functional(struct qr_code * code, setpx(bmp, 6, i); } - /* XXX: alignment pattern */ + /* Alignment pattern */ + am_side = code->version > 1 ? (code->version / 7) + 2 : 0; + for (y = 0; y < am_side; ++y) { + const int * am_pos = QR_ALIGNMENT_LOCATION[code->version - 1]; + + for (x = 0; x < am_side; ++x) { + if ((x == 0 && y == 0) || + (x == 0 && y == am_side - 1) || + (x == am_side - 1 && y == 0)) + continue; + + for (i = -2; i < 2; ++i) { + setpx(bmp, am_pos[x] + i, am_pos[y] - 2); + setpx(bmp, am_pos[x] + 2, am_pos[y] + i); + setpx(bmp, am_pos[x] - i, am_pos[y] + 2); + setpx(bmp, am_pos[x] - 2, am_pos[y] - i); + } + setpx(bmp, am_pos[x], am_pos[y]); + } + } /* Format info */ setpx(bmp, 8, dim - 8); diff --git a/lpg/libqr/code-layout.c b/lpg/libqr/code-layout.c index 54947d1..2a90124 100644 --- a/lpg/libqr/code-layout.c +++ b/lpg/libqr/code-layout.c @@ -21,6 +21,8 @@ void qr_layout_init_mask(struct qr_code * code) int x, y; int dim = qr_code_width(code); struct qr_bitmap * bmp = code->modules; + const int * am_pos = QR_ALIGNMENT_LOCATION[code->version - 1]; + int am_side; assert(bmp->mask); @@ -53,11 +55,32 @@ void qr_layout_init_mask(struct qr_code * code) continue; } - /* XXX: alignment pattern */ - row[off] |= bit; } } + + /* Alignment pattern */ + am_side = code->version > 1 ? (code->version / 7) + 2 : 0; + for (y = 0; y < am_side; ++y) { + for (x = 0; x < am_side; ++x) { + int i, j; + + if ((x == 0 && y == 0) || + (x == 0 && y == am_side - 1) || + (x == am_side - 1 && y == 0)) + continue; + + for (j = -2; j <= 2; ++j) { + unsigned char * row = bmp->mask + (am_pos[y]+j) * bmp->stride; + for (i = -2; i <= 2; ++i) { + unsigned char bit = 1 << ((am_pos[x]+i) % CHAR_BIT); + int off = (am_pos[x]+i) / CHAR_BIT; + + row[off] &= ~bit; + } + } + } + } } static int is_data_bit(const struct qr_iterator * i) -- cgit v1.2.3-70-g09d2 From c157f944cd6db591f5da47475200e5e16b0c2cac Mon Sep 17 00:00:00 2001 From: Leo Howell Date: Sat, 14 Nov 2009 18:43:26 +0900 Subject: Auto-size --- lpg/libqr/TODO | 1 - lpg/libqr/data-common.h | 2 ++ lpg/libqr/data-create.c | 69 ++++++++++++++++++++++++++++++++++++++++++------- lpg/libqr/qr/data.h | 2 +- lpg/libqr/qrgen.c | 2 +- 5 files changed, 63 insertions(+), 13 deletions(-) (limited to 'lpg/libqr/TODO') diff --git a/lpg/libqr/TODO b/lpg/libqr/TODO index eb35da8..0511b22 100644 --- a/lpg/libqr/TODO +++ b/lpg/libqr/TODO @@ -1,4 +1,3 @@ -* Auto-sizing for data * Sample app * Merge some files * Fix XXX, TODO diff --git a/lpg/libqr/data-common.h b/lpg/libqr/data-common.h index 420b3b2..054d349 100644 --- a/lpg/libqr/data-common.h +++ b/lpg/libqr/data-common.h @@ -16,5 +16,7 @@ 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 27c6d4b..37556c6 100644 --- a/lpg/libqr/data-create.c +++ b/lpg/libqr/data-create.c @@ -11,6 +11,8 @@ #include "qr-bitstream.h" #include "data-common.h" +extern const int QR_DATA_WORD_COUNT[40][4]; + static void write_type_and_length(struct qr_data * data, enum qr_data_type type, size_t length) @@ -28,12 +30,7 @@ static struct qr_data * encode_numeric(struct qr_data * data, size_t bits; bits = 4 + get_size_field_length(data->version, QR_DATA_NUMERIC) - + 10 * (length / 3); - - if (length % 3 == 1) - bits += 4; - else if (length % 3 == 2) - bits += 7; + + qr_data_dpart_length(QR_DATA_NUMERIC, length); stream = data->bits; if (qr_bitstream_resize(stream, @@ -106,8 +103,7 @@ static struct qr_data * encode_alpha(struct qr_data * data, size_t bits; bits = 4 + get_size_field_length(data->version, QR_DATA_ALPHA) - + 11 * (length / 2) - + 6 * (length % 2); + + qr_data_dpart_length(QR_DATA_ALPHA, length); stream = data->bits; if (qr_bitstream_resize(stream, @@ -150,7 +146,7 @@ static struct qr_data * encode_8bit(struct qr_data * data, size_t bits; bits = 4 + get_size_field_length(data->version, QR_DATA_8BIT) - + 8 * length; + + qr_data_dpart_length(QR_DATA_8BIT, length); stream = data->bits; if (qr_bitstream_resize(stream, @@ -172,6 +168,24 @@ static struct qr_data * encode_kanji(struct qr_data * data, return 0; } +static int calc_min_version(enum qr_data_type type, + enum qr_ec_level ec, + size_t length) +{ + size_t dbits; + int version; + + dbits = qr_data_dpart_length(type, length); + + for (version = 1; version <= 40; ++version) { + if (4 + dbits + get_size_field_length(version, type) + < 8 * QR_DATA_WORD_COUNT[version - 1][ec ^ 0x1]) + return version; + } + + return -1; +} + struct qr_data * qr_create_data(int version, enum qr_ec_level ec, enum qr_data_type type, @@ -179,8 +193,14 @@ struct qr_data * qr_create_data(int version, size_t length) { struct qr_data * data; + int minver; - if (version < 1 || version > 40) + minver = calc_min_version(type, ec, length); + + if (version == 0) + version = minver; + + if (minver < 0 || version < minver) return 0; data = malloc(sizeof(*data)); @@ -222,3 +242,32 @@ struct qr_data * qr_create_data(int version, } } +size_t qr_data_dpart_length(enum qr_data_type type, size_t length) +{ + size_t bits; + + switch (type) { + case QR_DATA_NUMERIC: + bits = 10 * (length / 3); + if (length % 3 == 1) + bits += 4; + else if (length % 3 == 2) + bits += 7; + break; + case QR_DATA_ALPHA: + bits = 11 * (length / 2) + + 6 * (length % 2); + break; + case QR_DATA_8BIT: + bits = 8 * length; + break; + case QR_DATA_KANJI: + /* unsupported */ + default: + /* unsupported; will be ignored */ + bits = 0; + } + + return bits; +} + diff --git a/lpg/libqr/qr/data.h b/lpg/libqr/qr/data.h index 39494f4..34b6968 100644 --- a/lpg/libqr/qr/data.h +++ b/lpg/libqr/qr/data.h @@ -22,7 +22,7 @@ enum qr_ec_level { QR_EC_LEVEL_H = 0x2 }; -struct qr_data * qr_create_data(int format, /* 1 ~ 40 */ +struct qr_data * qr_create_data(int format, /* 1 ~ 40; 0=auto */ enum qr_ec_level ec, enum qr_data_type type, const char * input, diff --git a/lpg/libqr/qrgen.c b/lpg/libqr/qrgen.c index d1aae68..cb6d33c 100644 --- a/lpg/libqr/qrgen.c +++ b/lpg/libqr/qrgen.c @@ -133,7 +133,7 @@ void show_help() { void set_default_config(struct config * conf) { - conf->version = 1; + conf->version = 0; conf->ec = QR_EC_LEVEL_M; conf->dtype = QR_DATA_NUMERIC; conf->ansi = 1; -- cgit v1.2.3-70-g09d2 From 2a5548351d9814a8a23eff1e43e14008ea4ae1d0 Mon Sep 17 00:00:00 2001 From: Leo Howell Date: Sat, 14 Nov 2009 18:46:29 +0900 Subject: Default to 8-bit data --- lpg/libqr/TODO | 1 - lpg/libqr/qrgen.c | 2 +- 2 files changed, 1 insertion(+), 2 deletions(-) (limited to 'lpg/libqr/TODO') diff --git a/lpg/libqr/TODO b/lpg/libqr/TODO index 0511b22..219ca83 100644 --- a/lpg/libqr/TODO +++ b/lpg/libqr/TODO @@ -1,4 +1,3 @@ -* Sample app * Merge some files * Fix XXX, TODO * Tidy code diff --git a/lpg/libqr/qrgen.c b/lpg/libqr/qrgen.c index cb6d33c..1309596 100644 --- a/lpg/libqr/qrgen.c +++ b/lpg/libqr/qrgen.c @@ -135,7 +135,7 @@ void set_default_config(struct config * conf) { conf->version = 0; conf->ec = QR_EC_LEVEL_M; - conf->dtype = QR_DATA_NUMERIC; + conf->dtype = QR_DATA_8BIT; conf->ansi = 1; conf->input = NULL; } -- cgit v1.2.3-70-g09d2 From c2e4639d2ebefbeb7f8b7e1826ae2391c6876a5a Mon Sep 17 00:00:00 2001 From: Leo Howell Date: Sat, 14 Nov 2009 20:24:57 +0900 Subject: Merge some files --- lpg/libqr/Makefile | 10 +- lpg/libqr/TODO | 1 - lpg/libqr/bitmap.c | 202 +++++++++++++++++++++++++++++++++++ lpg/libqr/bitstream.c | 243 +++++++++++++++++++++++++++++++++++++++++++ lpg/libqr/capacity.c | 88 ---------------- lpg/libqr/code-common.c | 89 ++++++++-------- lpg/libqr/code-common.h | 18 ---- lpg/libqr/code-create.c | 56 ++-------- lpg/libqr/code-layout.c | 6 +- lpg/libqr/code-layout.h | 14 --- lpg/libqr/code-parse.c | 2 - lpg/libqr/constants.c | 151 +++++++++++++++++++++++++++ lpg/libqr/constants.h | 12 +++ lpg/libqr/data-common.c | 26 +---- lpg/libqr/data-common.h | 22 ---- lpg/libqr/data-create.c | 20 ++-- lpg/libqr/data-parse.c | 16 +-- lpg/libqr/galois.c | 126 ++++++++++++++++++++++ lpg/libqr/galois.h | 12 +++ lpg/libqr/qr-bitmap-render.c | 118 --------------------- lpg/libqr/qr-bitmap.c | 89 ---------------- lpg/libqr/qr-bitstream.c | 243 ------------------------------------------- lpg/libqr/qr-bitstream.h | 48 --------- lpg/libqr/qr-mask.c | 46 -------- lpg/libqr/qr-mask.h | 10 -- lpg/libqr/qr/bitstream.h | 48 +++++++++ lpg/libqr/qr/code.h | 10 ++ lpg/libqr/qr/data.h | 13 ++- lpg/libqr/qr/layout.h | 14 +++ lpg/libqr/qrgen.c | 11 +- lpg/libqr/rs-encode.c | 96 ----------------- lpg/libqr/rs.h | 11 -- 32 files changed, 916 insertions(+), 955 deletions(-) create mode 100644 lpg/libqr/bitmap.c create mode 100644 lpg/libqr/bitstream.c delete mode 100644 lpg/libqr/capacity.c delete mode 100644 lpg/libqr/code-common.h delete mode 100644 lpg/libqr/code-layout.h create mode 100644 lpg/libqr/constants.c create mode 100644 lpg/libqr/constants.h delete mode 100644 lpg/libqr/data-common.h create mode 100644 lpg/libqr/galois.c create mode 100644 lpg/libqr/galois.h delete mode 100644 lpg/libqr/qr-bitmap-render.c delete mode 100644 lpg/libqr/qr-bitmap.c delete mode 100644 lpg/libqr/qr-bitstream.c delete mode 100644 lpg/libqr/qr-bitstream.h delete mode 100644 lpg/libqr/qr-mask.c delete mode 100644 lpg/libqr/qr-mask.h create mode 100644 lpg/libqr/qr/bitstream.h create mode 100644 lpg/libqr/qr/layout.h delete mode 100644 lpg/libqr/rs-encode.c delete mode 100644 lpg/libqr/rs.h (limited to 'lpg/libqr/TODO') 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/bitmap.c b/lpg/libqr/bitmap.c new file mode 100644 index 0000000..3394784 --- /dev/null +++ b/lpg/libqr/bitmap.c @@ -0,0 +1,202 @@ +#include +#include +#include +#include + +#include + +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, + 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_bitmap_render(const struct qr_bitmap * bmp, + 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 = bmp->bits; + out = buffer; + dim = bmp->width; + + 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 += bmp->stride; + out = next; + } +} + diff --git a/lpg/libqr/bitstream.c b/lpg/libqr/bitstream.c new file mode 100644 index 0000000..cf5a9d4 --- /dev/null +++ b/lpg/libqr/bitstream.c @@ -0,0 +1,243 @@ +/** + * 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 +#include +#include +#include + +#include + +#define MAX(a, b) ((a) < (b) ? (b) : (a)) +#define MIN(a, b) ((a) > (b) ? (b) : (a)) + +struct qr_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 qr_bitstream * stream, size_t bits) +{ + size_t need_bits = stream->pos + bits; + size_t newsize; + + if (stream->bufsiz * CHAR_BIT >= need_bits) + return 0; + + newsize = MAX(stream->bufsiz, 100) * CHAR_BIT; + while (newsize < need_bits) + newsize *= 2; + + return qr_bitstream_resize(stream, newsize); +} + +struct qr_bitstream * qr_bitstream_create(void) +{ + struct qr_bitstream * obj; + + obj = malloc(sizeof(*obj)); + + if (obj) { + obj->pos = 0; + obj->count = 0; + obj->bufsiz = 0; + obj->buffer = 0; + } + + return obj; +} + +int qr_bitstream_resize(struct qr_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 qr_bitstream_destroy(struct qr_bitstream * stream) +{ + free(stream->buffer); + free(stream); +} + +struct qr_bitstream * qr_bitstream_dup(const struct qr_bitstream * src) +{ + struct qr_bitstream * ret; + + ret = qr_bitstream_create(); + if (!ret) + return 0; + + if (qr_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 qr_bitstream_seek(struct qr_bitstream * stream, size_t pos) +{ + assert(pos <= stream->count); + stream->pos = pos; +} + +size_t qr_bitstream_tell(const struct qr_bitstream * stream) +{ + return stream->pos; +} + +size_t qr_bitstream_remaining(const struct qr_bitstream * stream) +{ + return stream->count - stream->pos; +} + +size_t qr_bitstream_size(const struct qr_bitstream * stream) +{ + return stream->count; +} + +unsigned int qr_bitstream_read(struct qr_bitstream * stream, size_t bits) +{ + unsigned int result = 0; + unsigned char * byte; + size_t bitnum; + + assert(qr_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 qr_bitstream_unpack(struct qr_bitstream * stream, + unsigned int * result, + size_t count, + size_t bitsize) +{ + assert(qr_bitstream_remaining(stream) >= (count * bitsize)); + + while (count--) + *(result++) = qr_bitstream_read(stream, bitsize); +} + +int qr_bitstream_write(struct qr_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 qr_bitstream_pack(struct qr_bitstream * stream, + const unsigned int * values, + size_t count, + size_t bitsize) +{ + if (ensure_available(stream, count * bitsize) != 0) + return -1; + + while (count--) + qr_bitstream_write(stream, *(values++), bitsize); + + return 0; +} + +int qr_bitstream_cat(struct qr_bitstream * dest, const struct qr_bitstream * src) +{ + size_t count = qr_bitstream_size(src); + size_t srcpos; + + if (ensure_available(dest, count) != 0) + return -1; + + 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) + qr_bitstream_write( + dest, + qr_bitstream_read((struct qr_bitstream *)src, 16), + 16); + + if (count > 0) + qr_bitstream_write( + dest, + qr_bitstream_read((struct qr_bitstream *)src, count), + count); + + return 0; +} + 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 +#include #include + #include #include -#include "code-common.h" +#include 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 -#include -#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 #include #include -#include -#include "code-common.h" -#include "code-layout.h" -#include "data-common.h" -#include "qr-mask.h" -#include "rs.h" +#include +#include +#include +#include +#include +#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 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 #include #include + #include -#include "code-common.h" -#include "code-layout.h" +#include +#include +#include "constants.h" struct qr_iterator { struct qr_code * code; diff --git a/lpg/libqr/code-layout.h b/lpg/libqr/code-layout.h deleted file mode 100644 index 3390548..0000000 --- a/lpg/libqr/code-layout.h +++ /dev/null @@ -1,14 +0,0 @@ -#ifndef CODE_LAYOUT_H -#define CODE_LAYOUT_H - -struct qr_iterator; - -void qr_layout_init_mask(struct qr_code *); - -struct qr_iterator * qr_layout_begin(struct qr_code * code); -unsigned int qr_layout_read(struct qr_iterator *); -void qr_layout_write(struct qr_iterator *, unsigned int); -void qr_layout_end(struct qr_iterator *); - -#endif - 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 -#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 + +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 -#include - -#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 +#include 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 - -#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 #include -#include -#include "qr-bitstream.h" -#include "data-common.h" - -extern const int QR_DATA_WORD_COUNT[40][4]; +#include +#include +#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 #include #include -#include -#include "qr-bitstream.h" -#include "data-common.h" +#include +#include +#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/galois.c b/lpg/libqr/galois.c new file mode 100644 index 0000000..e21ce22 --- /dev/null +++ b/lpg/libqr/galois.c @@ -0,0 +1,126 @@ +#include +#include + +#include +#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) +{ + /* Reduce modulo x^8 + x^4 + x^3 + x^2 + 1 + * using the peasant's algorithm + */ + const unsigned int m = 0x11D; + unsigned int x = 0; + int i; + + for (i = 0; i < 8; ++i) { + x ^= (b & 0x1) ? a : 0; + a = (a << 1) ^ ((a & 0x80) ? m : 0); + b >>= 1; + } + + return x & 0xFF; +} + +static unsigned int * make_generator(int k) +{ + unsigned int * g; + unsigned int a; + int i, j; + + g = calloc(k, sizeof(*g)); + if (!g) + return 0; + + g[0] = 1; /* Start with g(x) = 1 */ + a = 1; /* 2^0 = 1 */ + + for (i = 0; i < k; ++i) { + /* Multiply our poly g(x) by (x + 2^i) */ + for (j = k - 1; j > 0; --j) + g[j] = gf_mult(g[j], a) ^ g[j-1]; + g[0] = gf_mult(g[0], a); + + a = gf_mult(a, 2); + } + + return g; +} + +struct qr_bitstream * rs_generate_words(struct qr_bitstream * data, + size_t data_words, + size_t rs_words) +{ + struct qr_bitstream * ec = 0; + unsigned int * b = 0; + unsigned int * g; + size_t n = rs_words; + int i, r; + + assert(qr_bitstream_remaining(data) >= data_words * 8); + + ec = qr_bitstream_create(); + if (!ec) + return 0; + + if (qr_bitstream_resize(ec, n * 8) != 0) + goto fail; + + b = calloc(n, sizeof(*b)); + if (!b) + goto fail; + + g = make_generator(n); + if (!g) + goto fail; + + /* First, prepare the registers (b) with data bits */ + for (i = 0; i < data_words; ++i) { + unsigned int x = b[n-1] ^ qr_bitstream_read(data, 8); + for (r = n-1; r > 0; --r) + b[r] = b[r-1] ^ gf_mult(g[r], x); + b[0] = gf_mult(g[0], x); + } + + /* Read off the registers */ + for (r = 0; r < n; ++r) + qr_bitstream_write(ec, b[(n-1)-r], 8); + + free(g); + free(b); + return ec; +fail: + free(b); + qr_bitstream_destroy(ec); + return 0; +} + diff --git a/lpg/libqr/galois.h b/lpg/libqr/galois.h new file mode 100644 index 0000000..1adeb88 --- /dev/null +++ b/lpg/libqr/galois.h @@ -0,0 +1,12 @@ +#ifndef QR_GALOIS_H +#define QR_GALOIS_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, + size_t rs_words); + +#endif + diff --git a/lpg/libqr/qr-bitmap-render.c b/lpg/libqr/qr-bitmap-render.c deleted file mode 100644 index 197e947..0000000 --- a/lpg/libqr/qr-bitmap-render.c +++ /dev/null @@ -1,118 +0,0 @@ -#include -#include -#include - -#include - -/* 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_bitmap_render(const struct qr_bitmap * bmp, - 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 = bmp->bits; - out = buffer; - dim = bmp->width; - - 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 += bmp->stride; - out = next; - } -} - 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 -#include -#include -#include -#include - -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-bitstream.c b/lpg/libqr/qr-bitstream.c deleted file mode 100644 index c752cde..0000000 --- a/lpg/libqr/qr-bitstream.c +++ /dev/null @@ -1,243 +0,0 @@ -/** - * 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 -#include -#include -#include - -#include "qr-bitstream.h" - -#define MAX(a, b) ((a) < (b) ? (b) : (a)) -#define MIN(a, b) ((a) > (b) ? (b) : (a)) - -struct qr_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 qr_bitstream * stream, size_t bits) -{ - size_t need_bits = stream->pos + bits; - size_t newsize; - - if (stream->bufsiz * CHAR_BIT >= need_bits) - return 0; - - newsize = MAX(stream->bufsiz, 100) * CHAR_BIT; - while (newsize < need_bits) - newsize *= 2; - - return qr_bitstream_resize(stream, newsize); -} - -struct qr_bitstream * qr_bitstream_create(void) -{ - struct qr_bitstream * obj; - - obj = malloc(sizeof(*obj)); - - if (obj) { - obj->pos = 0; - obj->count = 0; - obj->bufsiz = 0; - obj->buffer = 0; - } - - return obj; -} - -int qr_bitstream_resize(struct qr_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 qr_bitstream_destroy(struct qr_bitstream * stream) -{ - free(stream->buffer); - free(stream); -} - -struct qr_bitstream * qr_bitstream_dup(const struct qr_bitstream * src) -{ - struct qr_bitstream * ret; - - ret = qr_bitstream_create(); - if (!ret) - return 0; - - if (qr_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 qr_bitstream_seek(struct qr_bitstream * stream, size_t pos) -{ - assert(pos <= stream->count); - stream->pos = pos; -} - -size_t qr_bitstream_tell(const struct qr_bitstream * stream) -{ - return stream->pos; -} - -size_t qr_bitstream_remaining(const struct qr_bitstream * stream) -{ - return stream->count - stream->pos; -} - -size_t qr_bitstream_size(const struct qr_bitstream * stream) -{ - return stream->count; -} - -unsigned int qr_bitstream_read(struct qr_bitstream * stream, size_t bits) -{ - unsigned int result = 0; - unsigned char * byte; - size_t bitnum; - - assert(qr_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 qr_bitstream_unpack(struct qr_bitstream * stream, - unsigned int * result, - size_t count, - size_t bitsize) -{ - assert(qr_bitstream_remaining(stream) >= (count * bitsize)); - - while (count--) - *(result++) = qr_bitstream_read(stream, bitsize); -} - -int qr_bitstream_write(struct qr_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 qr_bitstream_pack(struct qr_bitstream * stream, - const unsigned int * values, - size_t count, - size_t bitsize) -{ - if (ensure_available(stream, count * bitsize) != 0) - return -1; - - while (count--) - qr_bitstream_write(stream, *(values++), bitsize); - - return 0; -} - -int qr_bitstream_cat(struct qr_bitstream * dest, const struct qr_bitstream * src) -{ - size_t count = qr_bitstream_size(src); - size_t srcpos; - - if (ensure_available(dest, count) != 0) - return -1; - - 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) - qr_bitstream_write( - dest, - qr_bitstream_read((struct qr_bitstream *)src, 16), - 16); - - if (count > 0) - qr_bitstream_write( - dest, - qr_bitstream_read((struct qr_bitstream *)src, count), - count); - - return 0; -} - diff --git a/lpg/libqr/qr-bitstream.h b/lpg/libqr/qr-bitstream.h deleted file mode 100644 index cf20694..0000000 --- a/lpg/libqr/qr-bitstream.h +++ /dev/null @@ -1,48 +0,0 @@ -#ifndef QR_BITSTREAM_H -#define QR_BITSTREAM_H - -#include - -/** - * 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 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_dup(const struct qr_bitstream *); - -void qr_bitstream_seek(struct qr_bitstream *, size_t pos); -size_t qr_bitstream_tell(const struct qr_bitstream *); -size_t qr_bitstream_remaining(const struct qr_bitstream *); -size_t qr_bitstream_size(const struct qr_bitstream *); - -unsigned int qr_bitstream_read(struct qr_bitstream *, size_t bits); - -void qr_bitstream_unpack(struct qr_bitstream *, - unsigned int * result, - size_t count, - size_t bitsize); - -int qr_bitstream_write(struct qr_bitstream *, - unsigned int value, - size_t bits); - -int qr_bitstream_pack(struct qr_bitstream *, - const unsigned int * values, - size_t count, - size_t bitsize); - -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 - 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 -#include -#include -#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 - -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 new file mode 100644 index 0000000..cf20694 --- /dev/null +++ b/lpg/libqr/qr/bitstream.h @@ -0,0 +1,48 @@ +#ifndef QR_BITSTREAM_H +#define QR_BITSTREAM_H + +#include + +/** + * 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 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_dup(const struct qr_bitstream *); + +void qr_bitstream_seek(struct qr_bitstream *, size_t pos); +size_t qr_bitstream_tell(const struct qr_bitstream *); +size_t qr_bitstream_remaining(const struct qr_bitstream *); +size_t qr_bitstream_size(const struct qr_bitstream *); + +unsigned int qr_bitstream_read(struct qr_bitstream *, size_t bits); + +void qr_bitstream_unpack(struct qr_bitstream *, + unsigned int * result, + size_t count, + size_t bitsize); + +int qr_bitstream_write(struct qr_bitstream *, + unsigned int value, + size_t bits); + +int qr_bitstream_pack(struct qr_bitstream *, + const unsigned int * values, + size_t count, + size_t bitsize); + +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 + 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 #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/qr/layout.h b/lpg/libqr/qr/layout.h new file mode 100644 index 0000000..49bebf6 --- /dev/null +++ b/lpg/libqr/qr/layout.h @@ -0,0 +1,14 @@ +#ifndef QR_CODE_LAYOUT_H +#define QR_CODE_LAYOUT_H + +struct qr_iterator; + +void qr_layout_init_mask(struct qr_code *); + +struct qr_iterator * qr_layout_begin(struct qr_code * code); +unsigned int qr_layout_read(struct qr_iterator *); +void qr_layout_write(struct qr_iterator *, unsigned int); +void qr_layout_end(struct qr_iterator *); + +#endif + 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 #include +#include +#include #include #include #include -#include -#include -#include + #include +#include #include #include -#include "qr-bitstream.h" -#include "code-common.h" - struct config { int version; enum qr_ec_level ec; diff --git a/lpg/libqr/rs-encode.c b/lpg/libqr/rs-encode.c deleted file mode 100644 index a8ecc73..0000000 --- a/lpg/libqr/rs-encode.c +++ /dev/null @@ -1,96 +0,0 @@ -#include -#include -#include "qr-bitstream.h" -#include "rs.h" - -static unsigned int gf_mult(unsigned int a, unsigned int b) -{ - /* Reduce modulo x^8 + x^4 + x^3 + x^2 + 1 - * using the peasant's algorithm - */ - const unsigned int m = 0x11D; - unsigned int x = 0; - int i; - - for (i = 0; i < 8; ++i) { - x ^= (b & 0x1) ? a : 0; - a = (a << 1) ^ ((a & 0x80) ? m : 0); - b >>= 1; - } - - return x & 0xFF; -} - -static unsigned int * make_generator(int k) -{ - unsigned int * g; - unsigned int a; - int i, j; - - g = calloc(k, sizeof(*g)); - if (!g) - return 0; - - g[0] = 1; /* Start with g(x) = 1 */ - a = 1; /* 2^0 = 1 */ - - for (i = 0; i < k; ++i) { - /* Multiply our poly g(x) by (x + 2^i) */ - for (j = k - 1; j > 0; --j) - g[j] = gf_mult(g[j], a) ^ g[j-1]; - g[0] = gf_mult(g[0], a); - - a = gf_mult(a, 2); - } - - return g; -} - -struct qr_bitstream * rs_generate_words(struct qr_bitstream * data, - size_t data_words, - size_t rs_words) -{ - struct qr_bitstream * ec = 0; - unsigned int * b = 0; - unsigned int * g; - size_t n = rs_words; - int i, r; - - assert(qr_bitstream_remaining(data) >= data_words * 8); - - ec = qr_bitstream_create(); - if (!ec) - return 0; - - if (qr_bitstream_resize(ec, n * 8) != 0) - goto fail; - - b = calloc(n, sizeof(*b)); - if (!b) - goto fail; - - g = make_generator(n); - if (!g) - goto fail; - - /* First, prepare the registers (b) with data bits */ - for (i = 0; i < data_words; ++i) { - unsigned int x = b[n-1] ^ qr_bitstream_read(data, 8); - for (r = n-1; r > 0; --r) - b[r] = b[r-1] ^ gf_mult(g[r], x); - b[0] = gf_mult(g[0], x); - } - - /* Read off the registers */ - for (r = 0; r < n; ++r) - qr_bitstream_write(ec, b[(n-1)-r], 8); - - free(g); - free(b); - return ec; -fail: - free(b); - qr_bitstream_destroy(ec); - return 0; -} - diff --git a/lpg/libqr/rs.h b/lpg/libqr/rs.h deleted file mode 100644 index c87d852..0000000 --- a/lpg/libqr/rs.h +++ /dev/null @@ -1,11 +0,0 @@ -#ifndef RS_H -#define RS_H - -#include "qr-bitstream.h" - -struct qr_bitstream * rs_generate_words(struct qr_bitstream * data, - size_t data_words, - size_t rs_words); - -#endif - -- cgit v1.2.3-70-g09d2 From 5d91255e986b6f1fb6205cc759ff5d43ccb3c96f Mon Sep 17 00:00:00 2001 From: Leo Howell Date: Sat, 14 Nov 2009 20:31:08 +0900 Subject: Final tidy for 0.1 --- lpg/libqr/COPYING | 16 +++++++--------- lpg/libqr/TODO | 9 --------- lpg/libqr/code-common.c | 2 +- lpg/libqr/galois.c | 7 +++---- lpg/libqr/galois.h | 7 +++---- lpg/libqr/qr/bitstream.h | 23 ++++++++++++----------- 6 files changed, 26 insertions(+), 38 deletions(-) (limited to 'lpg/libqr/TODO') diff --git a/lpg/libqr/COPYING b/lpg/libqr/COPYING index 10a9711..ff2f585 100644 --- a/lpg/libqr/COPYING +++ b/lpg/libqr/COPYING @@ -1,16 +1,14 @@ -I, the author, hereby release this work into the public -domain. +I, the author, hereby release this work into the public domain. -Where the above is not possible, I release this work as -"Copyright-Free", or (at your option) under the terms of -the Creative Commons CC0 license: +Where the above is not possible, I release this work as "Copyright +Free", or (at your option) under the terms of the Creative Commons CC0 +license: http://creativecommons.org/publicdomain/zero/1.0/ -The author waives all rights concerning the modification, -reproduction and/or distribution of this work, or -derivatives thereof, in whole or part, and in any form. -Attribution is not required. +The author waives all rights concerning the modification, reproduction +and/or distribution of this work, or derivatives thereof, in whole or +in part, and in any form. Attribution is not required. Leo Howell, September 2009 diff --git a/lpg/libqr/TODO b/lpg/libqr/TODO index 3cd0583..1b9671b 100644 --- a/lpg/libqr/TODO +++ b/lpg/libqr/TODO @@ -1,20 +1,11 @@ -* Fix XXX, TODO -* Tidy code -* RELEASE v0.1 - * Parsing -* RELEASE v0.2 * Detection -* RELEASE v0.3 * Test suite * No-malloc * Optimize * Documentation -* RELEASE v0.4 (BETA) - -* RELEASE v1.0 * Other data types diff --git a/lpg/libqr/code-common.c b/lpg/libqr/code-common.c index bc6621a..a0b8fcc 100644 --- a/lpg/libqr/code-common.c +++ b/lpg/libqr/code-common.c @@ -47,7 +47,7 @@ struct qr_bitmap * qr_mask_apply(const struct qr_bitmap * orig, struct qr_bitmap * bmp; int i, j; - if (mask & ~0x7) + if (mask > 7) return 0; bmp = qr_bitmap_clone(orig); diff --git a/lpg/libqr/galois.c b/lpg/libqr/galois.c index e21ce22..f0aadfd 100644 --- a/lpg/libqr/galois.c +++ b/lpg/libqr/galois.c @@ -5,8 +5,7 @@ #include "galois.h" /* Calculate the residue of a modulo m */ -unsigned long gf_residue(unsigned long a, - unsigned long m) +unsigned long gf_residue(unsigned long a, unsigned long m) { unsigned long o = 1; int n = 1; @@ -77,8 +76,8 @@ static unsigned int * make_generator(int k) } struct qr_bitstream * rs_generate_words(struct qr_bitstream * data, - size_t data_words, - size_t rs_words) + size_t data_words, + size_t rs_words) { struct qr_bitstream * ec = 0; unsigned int * b = 0; diff --git a/lpg/libqr/galois.h b/lpg/libqr/galois.h index 1adeb88..4ca0c93 100644 --- a/lpg/libqr/galois.h +++ b/lpg/libqr/galois.h @@ -1,12 +1,11 @@ #ifndef QR_GALOIS_H #define QR_GALOIS_H -unsigned long gf_residue(unsigned long a, - unsigned long m); +unsigned long gf_residue(unsigned long a, unsigned long m); struct qr_bitstream * rs_generate_words(struct qr_bitstream * data, - size_t data_words, - size_t rs_words); + size_t data_words, + size_t rs_words); #endif diff --git a/lpg/libqr/qr/bitstream.h b/lpg/libqr/qr/bitstream.h index cf20694..5ca6b41 100644 --- a/lpg/libqr/qr/bitstream.h +++ b/lpg/libqr/qr/bitstream.h @@ -13,8 +13,8 @@ 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 *); +int qr_bitstream_resize(struct qr_bitstream *, size_t bits); +void qr_bitstream_destroy(struct qr_bitstream *); struct qr_bitstream * qr_bitstream_dup(const struct qr_bitstream *); void qr_bitstream_seek(struct qr_bitstream *, size_t pos); @@ -25,20 +25,21 @@ size_t qr_bitstream_size(const struct qr_bitstream *); unsigned int qr_bitstream_read(struct qr_bitstream *, size_t bits); void qr_bitstream_unpack(struct qr_bitstream *, - unsigned int * result, - size_t count, - size_t bitsize); + unsigned int * result, + size_t count, + size_t bitsize); int qr_bitstream_write(struct qr_bitstream *, - unsigned int value, - size_t bits); + unsigned int value, + size_t bits); int qr_bitstream_pack(struct qr_bitstream *, - const unsigned int * values, - size_t count, - size_t bitsize); + const unsigned int * values, + size_t count, + size_t bitsize); -int qr_bitstream_cat(struct qr_bitstream *, const struct qr_bitstream * src); +int qr_bitstream_cat(struct qr_bitstream *, + const struct qr_bitstream * src); int qr_bitstream_copy(struct qr_bitstream * dest, struct qr_bitstream * src, -- cgit v1.2.3-70-g09d2