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