From 388507a61df32c0bddf7e61c5da013c3f29d32d4 Mon Sep 17 00:00:00 2001 From: Leo Howell Date: Sun, 27 Sep 2009 16:53:16 +0900 Subject: bitstream -> qr_bitstream --- lpg/libqr/Makefile | 4 +- lpg/libqr/bitstream.c | 232 ----------------------------------------------- lpg/libqr/bitstream.h | 44 --------- lpg/libqr/code-common.h | 2 +- lpg/libqr/code-create.c | 66 +++++++------- lpg/libqr/data-common.c | 4 +- lpg/libqr/data-common.h | 4 +- lpg/libqr/data-create.c | 38 ++++---- lpg/libqr/data-parse.c | 52 +++++------ lpg/libqr/qr-bitstream.c | 232 +++++++++++++++++++++++++++++++++++++++++++++++ lpg/libqr/qr-bitstream.h | 44 +++++++++ lpg/libqr/rs-encode.c | 20 ++-- lpg/libqr/rs.h | 4 +- lpg/libqr/test.c | 2 +- 14 files changed, 374 insertions(+), 374 deletions(-) delete mode 100644 lpg/libqr/bitstream.c delete mode 100644 lpg/libqr/bitstream.h create mode 100644 lpg/libqr/qr-bitstream.c create mode 100644 lpg/libqr/qr-bitstream.h (limited to 'lpg/libqr') diff --git a/lpg/libqr/Makefile b/lpg/libqr/Makefile index 1571de4..49f89d4 100644 --- a/lpg/libqr/Makefile +++ b/lpg/libqr/Makefile @@ -1,5 +1,4 @@ -OBJECTS := bitstream.o \ - code-common.o \ +OBJECTS := code-common.o \ code-create.o \ code-layout.o \ code-parse.o \ @@ -9,6 +8,7 @@ OBJECTS := bitstream.o \ qr-bitmap.o \ qr-bitmap-pbm.o \ qr-bitmap-render.o \ + qr-bitstream.o \ rs-encode.o CFLAGS := -std=c89 -pedantic -I. -Wall diff --git a/lpg/libqr/bitstream.c b/lpg/libqr/bitstream.c deleted file mode 100644 index fd58ea3..0000000 --- a/lpg/libqr/bitstream.c +++ /dev/null @@ -1,232 +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 "bitstream.h" - -#define MAX(a, b) ((a) < (b) ? (b) : (a)) -#define MIN(a, b) ((a) > (b) ? (b) : (a)) - -struct bitstream { - size_t pos; /* bits */ - size_t count; /* bits */ - size_t bufsiz; /* bytes */ - unsigned char * buffer; -}; - -static size_t bits_to_bytes(size_t bits) -{ - return (bits / CHAR_BIT) + (bits % CHAR_BIT != 0); -} - -static int ensure_available(struct bitstream * stream, size_t bits) -{ - size_t need_bits = stream->pos + bits; - size_t need_bytes = need_bits / CHAR_BIT + ((need_bits % CHAR_BIT) ? 0 : 1); - size_t newsize; - - if (stream->bufsiz >= need_bytes) - return 0; - - newsize = MAX(stream->bufsiz, 100); - while (newsize < need_bytes) - newsize *= 2; - - return bitstream_resize(stream, newsize); -} - -struct bitstream * bitstream_create(void) -{ - struct bitstream * obj; - - obj = malloc(sizeof(*obj)); - - if (obj) { - obj->pos = 0; - obj->count = 0; - obj->bufsiz = 0; - obj->buffer = 0; - } - - return obj; -} - -int bitstream_resize(struct bitstream * stream, size_t bits) -{ - size_t newsize; - void * newbuf; - - newsize = bits_to_bytes(bits); - newbuf = realloc(stream->buffer, newsize); - - if (newbuf) { - stream->bufsiz = newsize; - stream->buffer = newbuf; - } - - return newbuf ? 0 : -1; -} - -void bitstream_destroy(struct bitstream * stream) -{ - free(stream->buffer); - free(stream); -} - -struct bitstream * bitstream_copy(const struct bitstream * src) -{ - struct bitstream * ret; - - ret = bitstream_create(); - if (!ret) - return 0; - - if (bitstream_resize(ret, src->count) != 0) { - free(ret); - return 0; - } - - ret->pos = src->pos; - ret->count = src->count; - memcpy(ret->buffer, src->buffer, src->bufsiz); - - return ret; -} - -void bitstream_seek(struct bitstream * stream, size_t pos) -{ - assert(pos <= stream->count); - stream->pos = pos; -} - -size_t bitstream_tell(const struct bitstream * stream) -{ - return stream->pos; -} - -size_t bitstream_remaining(const struct bitstream * stream) -{ - return stream->count - stream->pos; -} - -size_t bitstream_size(const struct bitstream * stream) -{ - return stream->count; -} - -unsigned int bitstream_read(struct bitstream * stream, size_t bits) -{ - unsigned int result = 0; - unsigned char * byte; - size_t bitnum; - - assert(bitstream_remaining(stream) >= bits); - - byte = stream->buffer + (stream->pos / CHAR_BIT); - bitnum = stream->pos % CHAR_BIT; - - stream->pos += bits; - - while (bits-- > 0) { - int bit = (*byte >> bitnum++) & 0x1; - result = (result << 1) | bit; - if (bitnum == CHAR_BIT) { - bitnum = 0; - ++byte; - } - } - - return result; -} - -void bitstream_unpack(struct bitstream * stream, - unsigned int * result, - size_t count, - size_t bitsize) -{ - assert(bitstream_remaining(stream) >= (count * bitsize)); - - while (count--) - *(result++) = bitstream_read(stream, bitsize); -} - -int bitstream_write(struct bitstream * stream, - unsigned int value, - size_t bits) -{ - unsigned char * byte; - size_t bitnum; - - if (ensure_available(stream, bits) != 0) - return -1; - - byte = stream->buffer + (stream->pos / CHAR_BIT); - bitnum = stream->pos % CHAR_BIT; - - stream->pos += bits; - stream->count = stream->pos; /* truncate */ - - while (bits-- > 0) { - int bit = (value >> bits) & 0x1; - unsigned char mask = 1 << bitnum++; - *byte = (*byte & ~mask) | (bit ? mask : 0); - if (bitnum == CHAR_BIT) { - bitnum = 0; - ++byte; - } - } - - return 0; -} - -int bitstream_pack(struct bitstream * stream, - const unsigned int * values, - size_t count, - size_t bitsize) -{ - if (ensure_available(stream, count * bitsize) != 0) - return -1; - - while (count--) - bitstream_write(stream, *(values++), bitsize); - - return 0; -} - -int bitstream_cat(struct bitstream * dest, const struct bitstream * src) -{ - size_t count = bitstream_size(src); - size_t srcpos; - - if (ensure_available(dest, count) != 0) - return -1; - - srcpos = bitstream_tell(src); - bitstream_seek((struct bitstream *)src, 0); - - /* uint must be at least 16 bits */ - for (; count >= 16; count -= 16) - bitstream_write( - dest, - bitstream_read((struct bitstream *)src, 16), - 16); - - if (count > 0) - bitstream_write( - dest, - bitstream_read((struct bitstream *)src, count), - count); - - bitstream_seek((struct bitstream *)src, srcpos); - - return 0; -} - diff --git a/lpg/libqr/bitstream.h b/lpg/libqr/bitstream.h deleted file mode 100644 index 12412bc..0000000 --- a/lpg/libqr/bitstream.h +++ /dev/null @@ -1,44 +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 bitstream; - -struct bitstream * bitstream_create(void); -int bitstream_resize(struct bitstream *, size_t bits); -void bitstream_destroy(struct bitstream *); -struct bitstream * bitstream_copy(const struct bitstream *); - -void bitstream_seek(struct bitstream *, size_t pos); -size_t bitstream_tell(const struct bitstream *); -size_t bitstream_remaining(const struct bitstream *); -size_t bitstream_size(const struct bitstream *); - -unsigned int bitstream_read(struct bitstream *, size_t bits); - -void bitstream_unpack(struct bitstream *, - unsigned int * result, - size_t count, - size_t bitsize); - -int bitstream_write(struct bitstream *, - unsigned int value, - size_t bits); - -int bitstream_pack(struct bitstream *, - const unsigned int * values, - size_t count, - size_t bitsize); - -int bitstream_cat(struct bitstream *, const struct bitstream * src); - -#endif - diff --git a/lpg/libqr/code-common.h b/lpg/libqr/code-common.h index fce8dce..cf96217 100644 --- a/lpg/libqr/code-common.h +++ b/lpg/libqr/code-common.h @@ -2,7 +2,7 @@ #define CODE_COMMON_H #include -#include "bitstream.h" +#include "qr-bitstream.h" #include "qr-bitmap.h" struct qr_code { diff --git a/lpg/libqr/code-create.c b/lpg/libqr/code-create.c index 5c0f2b7..c6451ac 100644 --- a/lpg/libqr/code-create.c +++ b/lpg/libqr/code-create.c @@ -11,14 +11,14 @@ #define MIN(a, b) ((b) < (a) ? (b) : (a)) #include -static void x_dump(struct bitstream * bits) +static void x_dump(struct qr_bitstream * bits) { size_t i, n; - bitstream_seek(bits, 0); - n = bitstream_size(bits); + qr_bitstream_seek(bits, 0); + n = qr_bitstream_size(bits); for (i = 0; i < n; ++i) { - printf("%d", bitstream_read(bits, 1)); + printf("%d", qr_bitstream_read(bits, 1)); if (i % 8 == 7) printf(" "); if ((i+1) % (7 * 8) == 0) @@ -67,19 +67,19 @@ static void draw_fixed_bits(struct qr_code * code) /* XXX: alignment pattern */ } -static int pad_data(struct bitstream * bits, size_t limit) +static int pad_data(struct qr_bitstream * bits, size_t limit) { /* This function is not very nice. Sorry. */ size_t count, n; - assert(bitstream_size(bits) <= limit); + assert(qr_bitstream_size(bits) <= limit); - if (bitstream_resize(bits, limit) != 0) + if (qr_bitstream_resize(bits, limit) != 0) return -1; - n = bitstream_size(bits); - bitstream_seek(bits, n); + n = qr_bitstream_size(bits); + qr_bitstream_seek(bits, n); count = limit - n; /* First append the terminator (0000) if possible, @@ -89,42 +89,42 @@ static int pad_data(struct bitstream * bits, size_t limit) if (n != 0) n = 8 - n; n = MIN(count, n + 4); - bitstream_write(bits, 0, n); + 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) { - bitstream_write(bits, 0xEC11, 16); + qr_bitstream_write(bits, 0xEC11, 16); count -= 16; } if (count > 0) { assert(count == 8); - bitstream_write(bits, 0xEC, 8); + qr_bitstream_write(bits, 0xEC, 8); } return 0; } -static struct bitstream * make_data(int format, +static struct qr_bitstream * make_data(int format, enum qr_ec_level ec, - struct bitstream * data) + struct qr_bitstream * data) { const size_t total_bits = code_total_capacity(format); const size_t total_words = total_bits / 8; size_t block_count, data_words, rs_words; size_t i; - struct bitstream * dcopy = 0; - struct bitstream * out = 0; - struct bitstream ** blocks = 0; + struct qr_bitstream * dcopy = 0; + struct qr_bitstream * out = 0; + struct qr_bitstream ** blocks = 0; /* Set up the output stream */ - out = bitstream_create(); + out = qr_bitstream_create(); if (!out) return 0; - if (bitstream_resize(out, total_bits) != 0) + if (qr_bitstream_resize(out, total_bits) != 0) goto fail; /** @@ -138,7 +138,7 @@ static struct bitstream * make_data(int format, assert(data_words + rs_words == total_words); /* Make a copy of the data and pad it */ - dcopy = bitstream_copy(data); + dcopy = qr_bitstream_copy(data); if (!dcopy) goto fail; @@ -154,14 +154,14 @@ static struct bitstream * make_data(int format, goto fail; /* Generate RS codewords */ - bitstream_seek(dcopy, 0); + qr_bitstream_seek(dcopy, 0); puts("Generate RS blocks:"); for (i = 0; i < block_count; ++i) { /* XXX: some blocks may be longer */ blocks[i] = rs_generate_words(dcopy, data_words, rs_words); if (!blocks[i]) { while (i--) - bitstream_destroy(blocks[i]); + qr_bitstream_destroy(blocks[i]); free(blocks); blocks = 0; goto fail; @@ -171,25 +171,25 @@ static struct bitstream * make_data(int format, /* Finally, write everything out in the correct order */ /* XXX: need to handle multiple blocks */ - bitstream_cat(out, dcopy); - bitstream_cat(out, blocks[0]); - bitstream_write(out, 0, total_bits - total_words * 8); + qr_bitstream_cat(out, dcopy); + qr_bitstream_cat(out, blocks[0]); + qr_bitstream_write(out, 0, total_bits - total_words * 8); puts("Final bitstream:"); x_dump(out); exit: if (blocks) { while (block_count--) - bitstream_destroy(blocks[block_count]); + qr_bitstream_destroy(blocks[block_count]); free(blocks); } if (dcopy) - bitstream_destroy(dcopy); + qr_bitstream_destroy(dcopy); return out; fail: - bitstream_destroy(out); + qr_bitstream_destroy(out); out = 0; goto exit; } @@ -198,7 +198,7 @@ struct qr_code * qr_code_create(enum qr_ec_level ec, const struct qr_data * data) { struct qr_code * code; - struct bitstream * bits = 0; + struct qr_bitstream * bits = 0; struct qr_iterator * layout; size_t dim; @@ -224,14 +224,14 @@ struct qr_code * qr_code_create(enum qr_ec_level ec, if (!layout) goto fail; - bitstream_seek(bits, 0); - while (bitstream_remaining(bits) >= 8) - qr_layout_write(layout, bitstream_read(bits, 8)); + qr_bitstream_seek(bits, 0); + while (qr_bitstream_remaining(bits) >= 8) + qr_layout_write(layout, qr_bitstream_read(bits, 8)); qr_layout_end(layout); exit: if (bits) - bitstream_destroy(bits); + qr_bitstream_destroy(bits); return code; diff --git a/lpg/libqr/data-common.c b/lpg/libqr/data-common.c index 123e5c4..c64527a 100644 --- a/lpg/libqr/data-common.c +++ b/lpg/libqr/data-common.c @@ -1,7 +1,7 @@ #include #include -#include "bitstream.h" +#include "qr-bitstream.h" #include "data-common.h" const enum qr_data_type QR_TYPE_CODES[16] = { @@ -25,7 +25,7 @@ const enum qr_data_type QR_TYPE_CODES[16] = { void qr_free_data(struct qr_data * data) { - bitstream_destroy(data->bits); + qr_bitstream_destroy(data->bits); free(data); } diff --git a/lpg/libqr/data-common.h b/lpg/libqr/data-common.h index d5f6e45..1522b09 100644 --- a/lpg/libqr/data-common.h +++ b/lpg/libqr/data-common.h @@ -3,11 +3,11 @@ #include -#include "bitstream.h" +#include "qr-bitstream.h" struct qr_data { int format; /* 1 ~ 40 */ - struct bitstream * bits; + struct qr_bitstream * bits; size_t offset; }; diff --git a/lpg/libqr/data-create.c b/lpg/libqr/data-create.c index 2910997..a918413 100644 --- a/lpg/libqr/data-create.c +++ b/lpg/libqr/data-create.c @@ -9,15 +9,15 @@ #include #include -#include "bitstream.h" +#include "qr-bitstream.h" #include "data-common.h" static void write_type_and_length(struct qr_data * data, enum qr_data_type type, size_t length) { - (void)bitstream_write(data->bits, QR_TYPE_CODES[type], 4); - (void)bitstream_write(data->bits, length, + (void)qr_bitstream_write(data->bits, QR_TYPE_CODES[type], 4); + (void)qr_bitstream_write(data->bits, length, get_size_field_length(data->format, type)); } @@ -25,7 +25,7 @@ static struct qr_data * encode_numeric(struct qr_data * data, const char * input, size_t length) { - struct bitstream * stream = data->bits; + struct qr_bitstream * stream = data->bits; size_t bits; bits = 4 + get_size_field_length(data->format, QR_DATA_NUMERIC) @@ -37,8 +37,8 @@ static struct qr_data * encode_numeric(struct qr_data * data, bits += 7; stream = data->bits; - if (bitstream_resize(stream, - bitstream_size(stream) + bits) != 0) + if (qr_bitstream_resize(stream, + qr_bitstream_size(stream) + bits) != 0) return 0; write_type_and_length(data, QR_DATA_NUMERIC, length); @@ -54,7 +54,7 @@ static struct qr_data * encode_numeric(struct qr_data * data, x = (input[0] - '0') * 100 + (input[1] - '0') * 10 + (input[2] - '0'); - bitstream_write(stream, x, 10); + qr_bitstream_write(stream, x, 10); input += 3; } @@ -72,7 +72,7 @@ static struct qr_data * encode_numeric(struct qr_data * data, x = x * 10 + (*input - '0'); } - bitstream_write(stream, x, length == 2 ? 7 : 4); + qr_bitstream_write(stream, x, length == 2 ? 7 : 4); } return data; @@ -103,7 +103,7 @@ static struct qr_data * encode_alpha(struct qr_data * data, const char * input, size_t length) { - struct bitstream * stream = data->bits; + struct qr_bitstream * stream = data->bits; size_t bits; bits = 4 + get_size_field_length(data->format, QR_DATA_ALPHA) @@ -111,8 +111,8 @@ static struct qr_data * encode_alpha(struct qr_data * data, + 6 * (length % 2); stream = data->bits; - if (bitstream_resize(stream, - bitstream_size(stream) + bits) != 0) + if (qr_bitstream_resize(stream, + qr_bitstream_size(stream) + bits) != 0) return 0; write_type_and_length(data, QR_DATA_ALPHA, length); @@ -128,7 +128,7 @@ static struct qr_data * encode_alpha(struct qr_data * data, return 0; x = c1 * 45 + c2; - bitstream_write(stream, x, 11); + qr_bitstream_write(stream, x, 11); } if (length > 0) { @@ -137,7 +137,7 @@ static struct qr_data * encode_alpha(struct qr_data * data, if (c < 0) return 0; - bitstream_write(stream, c, 6); + qr_bitstream_write(stream, c, 6); } return data; @@ -147,21 +147,21 @@ static struct qr_data * encode_8bit(struct qr_data * data, const char * input, size_t length) { - struct bitstream * stream = data->bits; + struct qr_bitstream * stream = data->bits; size_t bits; bits = 4 + get_size_field_length(data->format, QR_DATA_8BIT) + 8 * length; stream = data->bits; - if (bitstream_resize(stream, - bitstream_size(stream) + bits) != 0) + if (qr_bitstream_resize(stream, + qr_bitstream_size(stream) + bits) != 0) return 0; write_type_and_length(data, QR_DATA_8BIT, length); while (length--) - bitstream_write(stream, *input++, 8); + qr_bitstream_write(stream, *input++, 8); return data; } @@ -188,7 +188,7 @@ struct qr_data * qr_create_data(int format, return 0; data->format = format; - data->bits = bitstream_create(); + data->bits = qr_bitstream_create(); data->offset = 0; if (data->bits) { @@ -210,7 +210,7 @@ struct qr_data * qr_create_data(int format, } if (!ret) { - bitstream_destroy(data->bits); + qr_bitstream_destroy(data->bits); free(data); } diff --git a/lpg/libqr/data-parse.c b/lpg/libqr/data-parse.c index 9129ed7..d497bdf 100644 --- a/lpg/libqr/data-parse.c +++ b/lpg/libqr/data-parse.c @@ -3,18 +3,18 @@ #include #include -#include "bitstream.h" +#include "qr-bitstream.h" #include "data-common.h" -static enum qr_data_type read_data_type(struct bitstream * stream) +static enum qr_data_type read_data_type(struct qr_bitstream * stream) { const size_t length = 4; unsigned int type; - if (bitstream_remaining(stream) < length) + if (qr_bitstream_remaining(stream) < length) return QR_DATA_INVALID; - type = bitstream_read(stream, length); + type = qr_bitstream_read(stream, length); assert(type < 16); return QR_TYPE_CODES[type]; @@ -24,7 +24,7 @@ static enum qr_data_type parse_numeric(const struct qr_data * data, char ** output, size_t * length) { - struct bitstream * stream; + struct qr_bitstream * stream; size_t field_len, bits; unsigned int digits; unsigned int chunk; @@ -34,10 +34,10 @@ static enum qr_data_type parse_numeric(const struct qr_data * data, buffer = 0; field_len = get_size_field_length(data->format, QR_DATA_NUMERIC); - if (bitstream_remaining(stream) < field_len) + if (qr_bitstream_remaining(stream) < field_len) goto invalid; - digits = bitstream_read(stream, field_len); + digits = qr_bitstream_read(stream, field_len); bits = (digits / 3) * 10; if (digits % 3 == 1) @@ -45,7 +45,7 @@ static enum qr_data_type parse_numeric(const struct qr_data * data, else if (digits % 3 == 2) bits += 7; - if (bitstream_remaining(stream) < bits) + if (qr_bitstream_remaining(stream) < bits) goto invalid; buffer = malloc(digits + 1); @@ -55,7 +55,7 @@ static enum qr_data_type parse_numeric(const struct qr_data * data, p = buffer; for (; bits >= 10; bits -= 10) { - chunk = bitstream_read(stream, 10); + chunk = qr_bitstream_read(stream, 10); if (chunk >= 1000) goto invalid; sprintf(p, "%03u", chunk); @@ -63,7 +63,7 @@ static enum qr_data_type parse_numeric(const struct qr_data * data, } if (bits > 0) { - chunk = bitstream_read(stream, bits); + chunk = qr_bitstream_read(stream, bits); if (chunk >= (bits >= 7 ? 100 : 10)) goto invalid; sprintf(p, "%0*u", bits >= 7 ? 2 : 1, chunk); @@ -84,7 +84,7 @@ static enum qr_data_type parse_alpha(const struct qr_data * data, { static const char charset[45] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:"; - struct bitstream * stream; + struct qr_bitstream * stream; size_t field_len, bits; unsigned int chars; unsigned int chunk; @@ -94,16 +94,16 @@ static enum qr_data_type parse_alpha(const struct qr_data * data, buffer = 0; field_len = get_size_field_length(data->format, QR_DATA_ALPHA); - if (bitstream_remaining(stream) < field_len) + if (qr_bitstream_remaining(stream) < field_len) goto invalid; - chars = bitstream_read(stream, field_len); + chars = qr_bitstream_read(stream, field_len); bits = (chars / 2) * 11; if (chars % 2 == 1) bits += 6; - if (bitstream_remaining(stream) < bits) + if (qr_bitstream_remaining(stream) < bits) goto invalid; buffer = malloc(chars + 1); @@ -114,7 +114,7 @@ static enum qr_data_type parse_alpha(const struct qr_data * data, for (; bits >= 11; bits -= 11) { unsigned int c1, c2; - chunk = bitstream_read(stream, 11); + chunk = qr_bitstream_read(stream, 11); c1 = chunk / 45; c2 = chunk % 45; if (c1 >= 45) @@ -124,7 +124,7 @@ static enum qr_data_type parse_alpha(const struct qr_data * data, } if (bits > 0) { - chunk = bitstream_read(stream, bits); + chunk = qr_bitstream_read(stream, bits); if (chunk >= 45) goto invalid; *p = charset[chunk]; @@ -143,7 +143,7 @@ static enum qr_data_type parse_8bit(const struct qr_data * data, char ** output, size_t * length) { - struct bitstream * stream; + struct qr_bitstream * stream; size_t field_len; unsigned int bytes; char * p; @@ -151,12 +151,12 @@ static enum qr_data_type parse_8bit(const struct qr_data * data, stream = data->bits; field_len = get_size_field_length(data->format, QR_DATA_8BIT); - if (bitstream_remaining(stream) < field_len) + if (qr_bitstream_remaining(stream) < field_len) return QR_DATA_INVALID; - bytes = bitstream_read(stream, field_len); + bytes = qr_bitstream_read(stream, field_len); - if (bitstream_remaining(stream) < bytes * 8) + if (qr_bitstream_remaining(stream) < bytes * 8) return QR_DATA_INVALID; *output = malloc(bytes + 1); @@ -167,7 +167,7 @@ static enum qr_data_type parse_8bit(const struct qr_data * data, *length = bytes; while (bytes-- > 0) - *p++ = bitstream_read(stream, 8); + *p++ = qr_bitstream_read(stream, 8); *p = '\0'; @@ -183,7 +183,7 @@ static enum qr_data_type parse_kanji(const struct qr_data * data, enum qr_data_type qr_get_data_type(const struct qr_data * data) { - bitstream_seek(data->bits, data->offset); + qr_bitstream_seek(data->bits, data->offset); return read_data_type(data->bits); } @@ -192,7 +192,7 @@ int qr_get_data_length(const struct qr_data * data) size_t field_len; enum qr_data_type type; - bitstream_seek(data->bits, data->offset); + qr_bitstream_seek(data->bits, data->offset); type = read_data_type(data->bits); @@ -208,17 +208,17 @@ int qr_get_data_length(const struct qr_data * data) return -1; } - if (bitstream_remaining(data->bits) < field_len) + if (qr_bitstream_remaining(data->bits) < field_len) return -1; - return (int) bitstream_read(data->bits, field_len); + return (int) qr_bitstream_read(data->bits, field_len); } enum qr_data_type qr_parse_data(const struct qr_data * input, char ** output, size_t * length) { - bitstream_seek(input->bits, input->offset); + qr_bitstream_seek(input->bits, input->offset); switch (read_data_type(input->bits)) { case QR_DATA_NUMERIC: diff --git a/lpg/libqr/qr-bitstream.c b/lpg/libqr/qr-bitstream.c new file mode 100644 index 0000000..3df2549 --- /dev/null +++ b/lpg/libqr/qr-bitstream.c @@ -0,0 +1,232 @@ +/** + * 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 need_bytes = need_bits / CHAR_BIT + ((need_bits % CHAR_BIT) ? 0 : 1); + size_t newsize; + + if (stream->bufsiz >= need_bytes) + return 0; + + newsize = MAX(stream->bufsiz, 100); + while (newsize < need_bytes) + newsize *= 2; + + return 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_copy(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); + + /* 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); + + qr_bitstream_seek((struct qr_bitstream *)src, srcpos); + + return 0; +} + diff --git a/lpg/libqr/qr-bitstream.h b/lpg/libqr/qr-bitstream.h new file mode 100644 index 0000000..298e53b --- /dev/null +++ b/lpg/libqr/qr-bitstream.h @@ -0,0 +1,44 @@ +#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_copy(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); + +#endif + diff --git a/lpg/libqr/rs-encode.c b/lpg/libqr/rs-encode.c index 1e6c6bf..42b404f 100644 --- a/lpg/libqr/rs-encode.c +++ b/lpg/libqr/rs-encode.c @@ -1,6 +1,6 @@ #include #include -#include "bitstream.h" +#include "qr-bitstream.h" #include "rs.h" static unsigned int gf_mult(unsigned int a, unsigned int b) @@ -46,23 +46,23 @@ static unsigned int * make_generator(int k) return g; } -struct bitstream * rs_generate_words(struct bitstream * data, +struct qr_bitstream * rs_generate_words(struct qr_bitstream * data, size_t data_words, size_t rs_words) { - struct bitstream * ec = 0; + struct qr_bitstream * ec = 0; unsigned int * b = 0; unsigned int * g; size_t n = rs_words; int i, r; - assert(bitstream_remaining(data) >= data_words * 8); + assert(qr_bitstream_remaining(data) >= data_words * 8); - ec = bitstream_create(); + ec = qr_bitstream_create(); if (!ec) return 0; - if (bitstream_resize(ec, n * 8) != 0) + if (qr_bitstream_resize(ec, n * 8) != 0) goto fail; b = calloc(n, sizeof(*b)); @@ -74,9 +74,9 @@ struct bitstream * rs_generate_words(struct bitstream * data, goto fail; /* First, prepare the registers (b) with data bits */ - bitstream_seek(data, 0); + qr_bitstream_seek(data, 0); for (i = 0; i < data_words; ++i) { - unsigned int x = b[n-1] ^ bitstream_read(data, 8); + 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); @@ -84,14 +84,14 @@ struct bitstream * rs_generate_words(struct bitstream * data, /* Read off the registers */ for (r = 0; r < n; ++r) - bitstream_write(ec, b[(n-1)-r], 8); + qr_bitstream_write(ec, b[(n-1)-r], 8); free(g); free(b); return ec; fail: free(b); - bitstream_destroy(ec); + qr_bitstream_destroy(ec); return 0; } diff --git a/lpg/libqr/rs.h b/lpg/libqr/rs.h index e640044..c87d852 100644 --- a/lpg/libqr/rs.h +++ b/lpg/libqr/rs.h @@ -1,9 +1,9 @@ #ifndef RS_H #define RS_H -#include "bitstream.h" +#include "qr-bitstream.h" -struct bitstream * rs_generate_words(struct bitstream * data, +struct qr_bitstream * rs_generate_words(struct qr_bitstream * data, size_t data_words, size_t rs_words); diff --git a/lpg/libqr/test.c b/lpg/libqr/test.c index 035908b..4e288af 100644 --- a/lpg/libqr/test.c +++ b/lpg/libqr/test.c @@ -4,7 +4,7 @@ #include #include -#include "bitstream.h" +#include "qr-bitstream.h" #include "code-common.h" int main() { -- cgit v1.2.3-70-g09d2