aboutsummaryrefslogtreecommitdiff
path: root/lpg/libqr/code-create.c
diff options
context:
space:
mode:
Diffstat (limited to 'lpg/libqr/code-create.c')
-rw-r--r--lpg/libqr/code-create.c565
1 files changed, 565 insertions, 0 deletions
diff --git a/lpg/libqr/code-create.c b/lpg/libqr/code-create.c
new file mode 100644
index 0000000..f64e42d
--- /dev/null
+++ b/lpg/libqr/code-create.c
@@ -0,0 +1,565 @@
+#include <stdlib.h>
+#include <limits.h>
+#include <assert.h>
+
+#include <qr/bitmap.h>
+#include <qr/bitstream.h>
+#include <qr/code.h>
+#include <qr/common.h>
+#include <qr/data.h>
+#include <qr/layout.h>
+#include "constants.h"
+#include "galois.h"
+
+#define MIN(a, b) ((b) < (a) ? (b) : (a))
+
+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);
+static int count_2blocks(const struct qr_bitmap * bmp);
+static int count_locators(const struct qr_bitmap * bmp);
+static int calc_bw_balance(const struct qr_bitmap * bmp);
+static int get_px(const struct qr_bitmap * bmp, int x, int y);
+static int get_mask(const struct qr_bitmap * bmp, int x, int y);
+static int draw_format(struct qr_bitmap * bmp,
+ struct qr_code * code,
+ enum qr_ec_level ec,
+ int mask);
+static unsigned int calc_format_bits(enum qr_ec_level ec, int mask);
+static unsigned long calc_version_bits(int version);
+
+static void setpx(struct qr_bitmap * bmp, int x, int y)
+{
+ size_t off = y * bmp->stride + x / CHAR_BIT;
+ unsigned char bit = 1 << (x % CHAR_BIT);
+
+ bmp->bits[off] |= bit;
+}
+
+static void draw_locator(struct qr_bitmap * bmp, int x, int y)
+{
+ int i;
+ for (i = 0; i < 6; ++i) {
+ setpx(bmp, x + i, y + 0);
+ setpx(bmp, x + 6, y + i);
+ setpx(bmp, x + i + 1, y + 6);
+ setpx(bmp, x, y + i + 1);
+ }
+ for (i = 0; i < 9; ++i)
+ setpx(bmp, x + 2 + i % 3, y + 2 + i / 3);
+}
+
+static int draw_functional(struct qr_code * code,
+ enum qr_ec_level ec,
+ unsigned int mask)
+{
+ 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)
+ return -1;
+
+ /* Locator pattern */
+ draw_locator(bmp, 0, 0);
+ draw_locator(bmp, 0, dim - 7);
+ draw_locator(bmp, dim - 7, 0);
+
+ /* Timing pattern */
+ for (i = 8; i < dim - 8; i += 2) {
+ setpx(bmp, i, 6);
+ setpx(bmp, 6, i);
+ }
+
+ /* 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);
+ if (draw_format(bmp, code, ec, mask) != 0)
+ return -1;
+
+ /* Merge data */
+ qr_bitmap_merge(bmp, code->modules);
+ qr_bitmap_destroy(code->modules);
+ code->modules = bmp;
+
+ return 0;
+}
+
+static int pad_data(struct qr_bitstream * bits, size_t limit)
+{
+ /* This function is not very nice. Sorry. */
+
+ size_t count, n;
+
+ assert(qr_bitstream_size(bits) <= limit);
+
+ if (qr_bitstream_resize(bits, limit) != 0)
+ return -1;
+
+ n = qr_bitstream_size(bits);
+ qr_bitstream_seek(bits, n);
+ count = limit - n;
+
+ /* First append the terminator (0000) if possible,
+ * and pad with zeros up to an 8-bit boundary
+ */
+ n = (n + 4) % 8;
+ if (n != 0)
+ n = 8 - n;
+ n = MIN(count, n + 4);
+ qr_bitstream_write(bits, 0, n);
+ count -= n;
+
+ assert(count % 8 == 0); /* since data codewords are 8 bits */
+
+ /* Finally pad with the repeating sequence 11101100 00010001 */
+ while (count >= 16) {
+ qr_bitstream_write(bits, 0xEC11, 16);
+ count -= 16;
+ }
+ if (count > 0) {
+ assert(count == 8);
+ qr_bitstream_write(bits, 0xEC, 8);
+ }
+
+ return 0;
+}
+
+static struct qr_bitstream * make_data(int version,
+ enum qr_ec_level ec,
+ struct qr_bitstream * data)
+{
+ const size_t total_bits = qr_code_total_capacity(version);
+ const size_t total_data = QR_DATA_WORD_COUNT[version - 1][ec ^ 0x1];
+ int block_count[2], data_length[2], ec_length[2];
+ int total_blocks;
+ int i, w;
+ struct qr_bitstream * dcopy = 0;
+ struct qr_bitstream * out = 0;
+ struct qr_bitstream ** blocks = 0;
+
+ /* Set up the output stream */
+ out = qr_bitstream_create();
+ if (!out)
+ return 0;
+
+ if (qr_bitstream_resize(out, total_bits) != 0)
+ goto fail;
+
+ qr_get_rs_block_sizes(version, ec, block_count, data_length, ec_length);
+ total_blocks = block_count[0] + block_count[1];
+
+ /* Make a copy of the data and pad it */
+ dcopy = qr_bitstream_dup(data);
+ if (!dcopy)
+ goto fail;
+
+ if (pad_data(dcopy, total_data * QR_WORD_BITS) != 0)
+ goto fail;
+
+ /* Make space for the RS blocks */
+ blocks = malloc(total_blocks * sizeof(*blocks));
+ if (!blocks)
+ goto fail;
+ for (i = 0; i < total_blocks; ++i)
+ blocks[i] = NULL;
+
+ /* Generate RS codewords */
+ qr_bitstream_seek(dcopy, 0);
+ for (i = 0; i < total_blocks; ++i) {
+ int type = (i >= block_count[0]);
+ blocks[i] = rs_generate_words(dcopy,
+ data_length[type],
+ ec_length[type]);
+ if (!blocks[i]) {
+ while (i--)
+ qr_bitstream_destroy(blocks[i]);
+ free(blocks);
+ blocks = 0;
+ goto fail;
+ }
+ }
+
+ /* Finally, write everything out in the correct order */
+ assert(block_count[1] == 0 || data_length[1] >= data_length[0]);
+ for (w = 0; w < data_length[block_count[1] ? 1 : 0]; ++w) {
+ for (i = (w >= data_length[0] ? block_count[0] : 0); i < total_blocks; ++i) {
+ long di = w + i * data_length[0]
+ + (i > block_count[0] ?
+ (i - block_count[0]) * (data_length[1] - data_length[0])
+ : 0);
+
+ qr_bitstream_seek(dcopy, di * QR_WORD_BITS);
+ qr_bitstream_copy(out, dcopy, QR_WORD_BITS);
+ }
+ }
+ for (i = 0; i < total_blocks; ++i)
+ qr_bitstream_seek(blocks[i], 0);
+ assert(block_count[1] == 0 || ec_length[1] == ec_length[0]);
+ for (w = 0; w < ec_length[0]; ++w)
+ for (i = 0; i < total_blocks; ++i)
+ qr_bitstream_copy(out, blocks[i], QR_WORD_BITS);
+
+ qr_bitstream_write(out, 0, total_bits % QR_WORD_BITS);
+
+exit:
+ if (blocks) {
+ while (total_blocks--)
+ qr_bitstream_destroy(blocks[total_blocks]);
+ free(blocks);
+ }
+ if (dcopy)
+ qr_bitstream_destroy(dcopy);
+
+ return out;
+
+fail:
+ qr_bitstream_destroy(out);
+ out = 0;
+ goto exit;
+}
+
+struct qr_code * qr_code_create(const struct qr_data * data)
+{
+ struct qr_code * code;
+ struct qr_bitstream * bits = 0;
+ struct qr_iterator * layout;
+ int mask;
+ size_t dim;
+
+ code = malloc(sizeof(*code));
+ if (!code)
+ return 0;
+
+ code->version = data->version;
+ dim = qr_code_width(code);
+ code->modules = qr_bitmap_create(dim, dim, 1);
+
+ if (!code->modules)
+ goto fail;
+
+ bits = make_data(data->version, data->ec, data->bits);
+ if (!bits)
+ goto fail;
+
+ qr_layout_init_mask(code);
+
+ layout = qr_layout_begin(code);
+ if (!layout)
+ goto fail;
+
+ qr_bitstream_seek(bits, 0);
+ while (qr_bitstream_remaining(bits) >= (size_t) QR_WORD_BITS)
+ qr_layout_write(layout, qr_bitstream_read(bits, QR_WORD_BITS));
+ qr_layout_end(layout);
+
+ mask = mask_data(code);
+ if (mask < 0)
+ goto fail;
+
+ if (draw_functional(code, data->ec, mask) != 0)
+ goto fail;
+
+exit:
+ if (bits)
+ qr_bitstream_destroy(bits);
+
+ return code;
+
+fail:
+ qr_code_destroy(code);
+ code = 0;
+ goto exit;
+}
+
+static int mask_data(struct qr_code * code)
+{
+ struct qr_bitmap * mask, * test;
+ int selected, score;
+ int i, best;
+
+ mask = 0;
+
+ /* Generate bitmap for each mask and evaluate */
+ for (i = 0; i < 8; ++i) {
+ test = qr_bitmap_clone(code->modules);
+ if (!test) {
+ qr_bitmap_destroy(mask);
+ return -1;
+ }
+ qr_mask_apply(test, i);
+ score = score_mask(test);
+ if (!mask || score < best) {
+ best = score;
+ selected = i;
+ qr_bitmap_destroy(mask);
+ mask = test;
+ } else {
+ qr_bitmap_destroy(test);
+ }
+ }
+
+ qr_bitmap_destroy(code->modules);
+ code->modules = mask;
+
+ return selected;
+}
+
+static int score_mask(const struct qr_bitmap * bmp)
+{
+ const int N[4] = { 3, 3, 40, 10 };
+ int score = 0;
+
+ score += score_runs(bmp, N[0]);
+ score += N[1] * count_2blocks(bmp);
+ score += N[2] * count_locators(bmp);
+ score += N[3] * ((abs(calc_bw_balance(bmp) - 50) + 4) / 5);
+
+ return score;
+}
+
+static int score_runs(const struct qr_bitmap * bmp, int base)
+{
+ /* Runs of 5+n bits -> N[0] + i */
+ size_t x, y;
+ int flip;
+ int score = 0;
+ int count, last;
+
+ for (flip = 0; flip <= 1; ++flip) {
+ for (y = 0; y < bmp->height; ++y) {
+ count = 0;
+ for (x = 0; x < bmp->width; ++x) {
+ int mask, bit;
+ if (flip) {
+ mask = get_mask(bmp, y, x);
+ bit = get_mask(bmp, y, x);
+ } else {
+ mask = get_mask(bmp, x, y);
+ bit = get_px(bmp, x, y);
+ }
+
+ if (mask &&
+ (count == 0 || !!bit == !!last)) {
+ ++count;
+ last = bit;
+ } else {
+ if (count >= 5)
+ score += base + count - 5;
+ count = 0;
+ }
+ }
+ }
+ }
+
+ return score;
+}
+
+static int count_2blocks(const struct qr_bitmap * bmp)
+{
+ /* Count the number of 2x2 blocks (on or off) */
+ size_t x, y;
+ int count = 0;
+
+ /* Slow and stupid */
+ for (y = 0; y < bmp->height - 1; ++y) {
+ for (x = 0; x < bmp->width - 1; ++x) {
+ if (get_mask(bmp, x, y) &&
+ get_mask(bmp, x+1, y) &&
+ get_mask(bmp, x, y+1) &&
+ get_mask(bmp, x+1, y+1)) {
+ int v[4];
+ v[0] = get_px(bmp, x, y);
+ v[1] = get_px(bmp, x+1, y);
+ v[2] = get_px(bmp, x, y+1);
+ v[3] = get_px(bmp, x+1, y+1);
+ if (!(v[0] || v[1] || v[2] || v[3]) ||
+ (v[0] && v[1] && v[2] && v[3])) {
+ ++count;
+ }
+ }
+ }
+ }
+
+ return count;
+}
+
+static int count_locators(const struct qr_bitmap * bmp)
+{
+ /* 1:1:3:1:1 patterns -> N[2] */
+ size_t x, y;
+ int flip;
+ int count = 0;
+
+ for (flip = 0; flip <= 1; ++flip) {
+ for (y = 0; y < bmp->height - 7; ++y) {
+ for (x = 0; x < bmp->width - 7; ++x) {
+ int bits[7];
+ int i;
+
+ for (i = 0; i < 7; ++i)
+ if (!(flip ? get_mask(bmp, y, x+i) : get_mask(bmp, x+i, y)))
+ continue;
+
+ for (i = 0; i < 7; ++i)
+ bits[i] = flip ? get_px(bmp, y, x+i) : get_px(bmp, x+i, y);
+
+ if (!bits[0])
+ for (i = 0; i < 7; ++i)
+ bits[i] = !bits[i];
+
+ if ( bits[0] && !bits[1] && bits[2] &&
+ bits[3] && bits[4] && !bits[5] &&
+ bits[6])
+ ++count;
+ }
+ }
+ }
+
+ return count;
+}
+
+static int calc_bw_balance(const struct qr_bitmap * bmp)
+{
+ /* Calculate the proportion (in percent) of "on" bits */
+ size_t x, y;
+ unsigned char bit;
+ long on, total;
+
+ assert(bmp->mask); /* we only need this case */
+
+ on = total = 0;
+ for (y = 0; y < bmp->height; ++y) {
+ size_t off = y * bmp->stride;
+ unsigned char * bits = bmp->bits + off;
+ unsigned char * mask = bmp->mask + off;
+
+ for (x = 0; x < bmp->width / CHAR_BIT; ++x, ++bits, ++mask) {
+ for (bit = 1; bit; bit <<= 1) {
+ int m = *mask & bit;
+
+ total += !!m;
+ on += !!(*bits & m);
+ }
+ }
+ }
+
+ return (on * 100) / total;
+}
+
+static int get_px(const struct qr_bitmap * bmp, int x, int y)
+{
+ size_t off = y * bmp->stride + x / CHAR_BIT;
+ unsigned char bit = 1 << (x % CHAR_BIT);
+
+ return bmp->bits[off] & bit;
+}
+
+static int get_mask(const struct qr_bitmap * bmp, int x, int y)
+{
+ size_t off = y * bmp->stride + x / CHAR_BIT;
+ unsigned char bit = 1 << (x % CHAR_BIT);
+
+ return bmp->mask[off] & bit;
+}
+
+static int draw_format(struct qr_bitmap * bmp,
+ struct qr_code * code,
+ enum qr_ec_level ec,
+ int mask)
+{
+ int i;
+ size_t dim;
+ long bits;
+
+ dim = bmp->width;
+
+ bits = calc_format_bits(ec, mask);
+ if (bits < 0)
+ return -1;
+
+ for (i = 0; i < 8; ++i) {
+ if (bits & 0x1) {
+ setpx(bmp, 8, i + (i > 5));
+ setpx(bmp, dim - 1 - i, 8);
+ }
+ bits >>= 1;
+ }
+
+ for (i = 0; i < 7; ++i) {
+ if (bits & 0x1) {
+ setpx(bmp, 8, dim - 7 + i);
+ setpx(bmp, 6 - i + (i == 0), 8);
+ }
+ bits >>= 1;
+ }
+
+ if (code->version >= 7) {
+ bits = calc_version_bits(code->version);
+
+ for (i = 0; i < 18; ++i) {
+ if (bits & 0x1) {
+ int a = i % 3, b = i / 3;
+ setpx(bmp, dim - 11 + a, b);
+ setpx(bmp, b, dim - 11 + a);
+ }
+ bits >>= 1;
+ }
+ }
+
+ return 0;
+}
+
+static unsigned int calc_format_bits(enum qr_ec_level ec, int mask)
+{
+ unsigned int bits;
+
+ bits = (ec & 0x3) << 3 | (mask & 0x7);
+
+ /* Compute (15, 5) BCH code */
+
+ bits <<= 15 - 5;
+ bits |= (unsigned int)gf_residue(bits, QR_FORMAT_POLY);
+
+ bits ^= QR_FORMAT_MASK;
+
+ return bits;
+}
+
+static unsigned long calc_version_bits(int version)
+{
+ unsigned long bits;
+
+ bits = version & 0x3F;
+
+ /* (18, 6) BCH code */
+
+ bits <<= 18 - 6;
+ bits |= gf_residue(bits, QR_VERSION_POLY);
+
+ return bits;
+}
+
generated by cgit v1.2.3-70-g09d2 (git 2.47.1) at 2025-01-31 10:02:05 +0000