From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.2.5 (2008-06-10) on sa.int.altlinux.org X-Spam-Level: X-Spam-Status: No, score=-1.5 required=5.0 tests=BAYES_00,DNS_FROM_OPENWHOIS autolearn=no version=3.2.5 From: "Kirill A. Shutsemov" To: "Dmitry V. Levin" , Alexey Tourbin Date: Fri, 26 Nov 2010 00:04:24 +0200 Message-Id: <1290722666-24606-2-git-send-email-kirill@shutemov.name> X-Mailer: git-send-email 1.7.2.3 In-Reply-To: <1290722666-24606-1-git-send-email-kirill@shutemov.name> References: <1290722666-24606-1-git-send-email-kirill@shutemov.name> Cc: "Alexey I. Froloff" , devel@lists.altlinux.org, Alexey Gladkov , "Kirill A. Shutemov" Subject: [devel] [PATCH 1/3] set.c: use packed bitmap for bit vector X-BeenThere: devel@lists.altlinux.org X-Mailman-Version: 2.1.12 Precedence: list Reply-To: ALT Linux Team development discussions List-Id: ALT Linux Team development discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 25 Nov 2010 22:04:40 -0000 Archived-At: List-Archive: List-Post: From: Kirill A. Shutemov Currently, set.c uses array of chars to store bit vector. Each char stores one bit: 0 or 1. Let's use packed bitmap instead. It creates room for optimizations. Signed-off-by: Kirill A. Shutemov --- lib/set.c | 152 ++++++++++++++++++++++++++++++++++++++----------------------- 1 files changed, 95 insertions(+), 57 deletions(-) diff --git a/lib/set.c b/lib/set.c index 68bcc8c..4b91dab 100644 --- a/lib/set.c +++ b/lib/set.c @@ -16,6 +16,24 @@ #include #include +#define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d)) +#define BITS_PER_BYTE 8 +#define BITS_PER_LONG (sizeof(long) * BITS_PER_BYTE) +#define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_LONG) +#define BIT(nr) (1UL << (nr)) + +static inline +int get_bit(const unsigned long *bitmap, int offset) +{ + return !!(bitmap[offset / BITS_PER_LONG] & BIT(offset % BITS_PER_LONG)); +} + +static inline +void set_bit(unsigned long *bitmap, int offset) +{ + bitmap[offset / BITS_PER_LONG] |= BIT(offset % BITS_PER_LONG); +} + /* * Base62 routines - encode bits with alnum characters. * @@ -55,19 +73,20 @@ void put_digit(char **base62, int c) (*base62)++; } -/* Main base62 encoding routine: pack bitv into base62 string. */ +/* Main base62 encoding routine: pack bitmap into base62 string. */ static -int encode_base62(int bitc, const char *bitv, char *base62) +int encode_base62(char *base62, const unsigned long *bitmap, size_t nbits) { char *base62_start = base62; int bits2 = 0; /* number of high bits set */ int bits6 = 0; /* number of regular bits set */ int num6b = 0; /* pending 6-bit number */ + unsigned int i; - while (bitc-- > 0) { + for(i = 0; i < nbits; i++) { assert(bits6 + bits2 < 6); - num6b |= (*bitv++ << bits6++); + num6b |= (get_bit(bitmap, i) << bits6++); if (bits6 + bits2 != 6) continue; @@ -138,21 +157,20 @@ int char_to_num(int c) } static inline -void putbits(char **bitv, int n, int c) +void putbits(unsigned long *bitmap, int *offset, int c, int nbits) { int i; - for(i = 0; i < n; i++) { - **bitv = (c >> i) & 1; - (*bitv)++; - } + for (i = 0; i < nbits; i++, (*offset)++) + if (c & BIT(i)) + set_bit(bitmap, *offset); } -/* Main base62 decoding routine: unpack base62 string into bitv. */ +/* Main base62 decoding routine: unpack base62 string into bitmap. */ static -int decode_base62(const char *base62, char *bitv) +int decode_base62(unsigned long *bitmap, const char *base62) { - char *bitv_start = bitv; + int offset = 0; int c; while ((c = *base62++)) { @@ -162,7 +180,7 @@ int decode_base62(const char *base62, char *bitv) return -1; if (num6b != 61) { - putbits(&bitv, 6, num6b); + putbits(bitmap, &offset, num6b, 6); continue; } @@ -177,27 +195,37 @@ int decode_base62(const char *base62, char *bitv) switch (num6b & (16 + 32)) { case 0: - putbits(&bitv, 6, 61); + putbits(bitmap, &offset, 61, 6); break; case 16: - putbits(&bitv, 6, 62); + putbits(bitmap, &offset, 62, 6); break; case 32: - putbits(&bitv, 6, 63); + putbits(bitmap, &offset, 63, 6); break; default: return -4; break; } - putbits(&bitv, 4, num6b); + putbits(bitmap, &offset, num6b, 4); } - return bitv - bitv_start; + return offset; } #ifdef SELF_TEST static +void bitv_to_bitmap(unsigned long *bitmap, const char *bitv, size_t n) +{ + unsigned int i; + + for (i = 0; i < n; i++) + if (bitv[i]) + set_bit(bitmap, i); +} + +static void test_base62(void) { const char rnd_bitv[] = { @@ -208,15 +236,20 @@ void test_base62(void) /* trigger some 'Z' */ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, }; - const int rnd_bitc = sizeof(rnd_bitv); - char *base62, *bitv; - int i, len, bitc; + const unsigned int rnd_bitc = sizeof(rnd_bitv); + unsigned long bitmap[BITS_TO_LONGS(rnd_bitc)]; + unsigned long *new_bitmap; + char *base62; + unsigned int i, len, bitc; + + memset(&bitmap, 0, sizeof(bitmap)); + bitv_to_bitmap(bitmap, rnd_bitv, rnd_bitc); /* encode */ base62 = alloca(encode_base62_size(rnd_bitc)); - len = encode_base62(rnd_bitc, rnd_bitv, base62); + len = encode_base62(base62, bitmap, rnd_bitc); assert(len > 0); - assert(len == (int) strlen(base62)); + assert(len == strlen(base62)); fprintf(stderr, "len=%d base62=%s\n", len, base62); /* The length cannot be shorter than 6 bits per symbol. */ @@ -226,17 +259,17 @@ void test_base62(void) assert(len <= rnd_bitc / 2 / 4 + rnd_bitc / 2 / 6 + 1); /* decode */ - bitv = alloca(decode_base62_size(base62)); - bitc = decode_base62(base62, bitv); + bitc = decode_base62_size(base62); + new_bitmap = alloca(BITS_TO_LONGS(bitc) * sizeof(long)); + memset(new_bitmap, 0, BITS_TO_LONGS(bitc) * sizeof(long)); + bitc = decode_base62(new_bitmap, base62); fprintf(stderr, "rnd_bitc=%d bitc=%d\n", rnd_bitc, bitc); assert(bitc >= rnd_bitc); /* Decoded bits must match. */ - for (i = 0; i < rnd_bitc; i++) - assert(rnd_bitv[i] == bitv[i]); - /* The remaining bits must be zero bits. */ - for (i = rnd_bitc; i < bitc; i++) - assert(bitv[i] == 0); + for (i = 0; i < sizeof(bitmap) / sizeof(*bitmap); i++) + assert(bitmap[i] == new_bitmap[i]); + fprintf(stderr, "%s: base62 test OK\n", __FILE__); } #endif @@ -306,32 +339,32 @@ int encode_golomb_size(int c, int Mshift) return (Mshift << 1) * c + 16; } -/* Main golomb encoding routine: package integers into bits. */ +/* Main golomb encoding routine: package integers into bitmap. */ static -int encode_golomb(int c, const unsigned *v, int Mshift, char *bitv) +int encode_golomb(int c, const unsigned *v, int Mshift, unsigned long *bitmap) { - char *bitv_start = bitv; + int offset = 0; const unsigned mask = (1 << Mshift) - 1; while (c-- > 0) { - unsigned v0, q, r; + unsigned v0, r; int i; v0 = *v++; /* first part: variable-length sequence */ - q = v0 >> Mshift; - for (i = 0; i < (int) q; i++) - *bitv++ = 0; - *bitv++ = 1; + offset += v0 >> Mshift; + set_bit(bitmap, offset++); /* second part: lower Mshift bits */ r = v0 & mask; - for (i = 0; i < Mshift; i++) - *bitv++ = (r >> i) & 1; + for (i = 0; i < Mshift; i++, offset++) { + if (r & BIT(i)) + set_bit(bitmap, offset); + } } - return bitv - bitv_start; + return offset; } /* Estimate how many values will emerge. */ @@ -345,11 +378,12 @@ int decode_golomb_size(int bitc, int Mshift) return bitc / (Mshift + 1); } -/* Main golomb decoding routine: unpackage bits into values. */ +/* Main golomb decoding routine: unpackage bitmap into values. */ static -int decode_golomb(int bitc, const char *bitv, int Mshift, unsigned *v) +int decode_golomb(int bitc, const unsigned long *bitmap, int Mshift, unsigned *v) { unsigned *v_start = v; + int offset = 0; /* next value */ while (bitc > 0) { @@ -362,7 +396,7 @@ int decode_golomb(int bitc, const char *bitv, int Mshift, unsigned *v) bit = 0; while (bitc > 0) { bitc--; - bit = *bitv++; + bit = get_bit(bitmap, offset++); if (bit == 0) q++; else @@ -381,8 +415,8 @@ int decode_golomb(int bitc, const char *bitv, int Mshift, unsigned *v) r = 0; for (i = 0; i < Mshift; i++) { bitc--; - if (*bitv++) - r |= (1 << i); + if (get_bit(bitmap, offset++)) + r |= BIT(i); } /* the value */ @@ -401,7 +435,7 @@ void test_golomb(void) 7, 6, 5, 4, 3, 2, 1, }; const int rnd_c = sizeof(rnd_v) / sizeof(*rnd_v); - char *bitv; + unsigned long *bitmap; unsigned *v; int bpp, Mshift; int alloc_bitc, bitc; @@ -417,8 +451,9 @@ void test_golomb(void) /* encode */ alloc_bitc = encode_golomb_size(rnd_c, Mshift); assert(alloc_bitc > rnd_c); - bitv = alloca(alloc_bitc); - bitc = encode_golomb(rnd_c, rnd_v, Mshift, bitv); + bitmap = alloca(BITS_TO_LONGS(alloc_bitc) * sizeof(long)); + memset(bitmap, 0, BITS_TO_LONGS(alloc_bitc) * sizeof(long)); + bitc = encode_golomb(rnd_c, rnd_v, Mshift, bitmap); fprintf(stderr, "alloc_bitc=%d bitc=%d\n", alloc_bitc, bitc); assert(bitc > rnd_c); assert(bitc <= alloc_bitc); @@ -427,7 +462,7 @@ void test_golomb(void) alloc_c = decode_golomb_size(bitc, Mshift); assert(alloc_c >= rnd_c); v = alloca(sizeof(*v) * alloc_c); - c = decode_golomb(bitc, bitv, Mshift, v); + c = decode_golomb(bitc, bitmap, Mshift, v); fprintf(stderr, "rnd_c=%d alloc_c=%d c=%d\n", rnd_c, alloc_c, c); assert(alloc_c >= c); @@ -597,8 +632,9 @@ int encode_set(int c, unsigned *v, int bpp, char *base62) int Mshift = encode_golomb_Mshift(c, bpp); int bitc = encode_golomb_size(c, Mshift); int len; - char bitv[bitc]; + unsigned long bitmap[BITS_TO_LONGS(bitc)]; + memset(bitmap, 0, sizeof(bitmap)); /* bpp */ if (bpp < 10 || bpp > 32) return -1; @@ -613,7 +649,7 @@ int encode_set(int c, unsigned *v, int bpp, char *base62) encode_delta(c, v); /* golomb */ - bitc = encode_golomb(c, v, Mshift, bitv); + bitc = encode_golomb(c, v, Mshift, bitmap); #ifdef SELF_TEST decode_delta(c, v); @@ -623,7 +659,7 @@ int encode_set(int c, unsigned *v, int bpp, char *base62) return -3; /* base62 */ - len = encode_base62(bitc, bitv, base62); + len = encode_base62(base62, bitmap, bitc); if (len < 0) return -4; @@ -671,21 +707,23 @@ int decode_set_size(const char *str, int Mshift) static int decode_set(const char *str, int Mshift, unsigned *v) { - char *bitv; + unsigned long *bitmap; int bitc; int c; str += 2; /* base62 */ - bitv = alloca(decode_base62_size(str)); - bitc = decode_base62(str, bitv); + bitc = decode_base62_size(str); + bitmap = alloca(BITS_TO_LONGS(bitc) * sizeof(long)); + memset(bitmap, 0, BITS_TO_LONGS(bitc) * sizeof(long)); + bitc = decode_base62(bitmap, str); if (bitc < 0) return -1; /* golomb */ - c = decode_golomb(bitc, bitv, Mshift, v); + c = decode_golomb(bitc, bitmap, Mshift, v); if (c < 0) return -2; -- 1.7.3.2