From: "Kirill A. Shutsemov" <kirill@shutemov.name> To: "Dmitry V. Levin" <ldv@altlinux.org>, Alexey Tourbin <at@altlinux.ru> Cc: "Alexey I. Froloff" <raorn@altlinux.org>, devel@lists.altlinux.org, Alexey Gladkov <legion@altlinux.ru>, "Kirill A. Shutemov" <kirill@shutemov.name> Subject: [devel] [PATCH 1/3] set.c: use packed bitmap for bit vector Date: Fri, 26 Nov 2010 00:04:24 +0200 Message-ID: <1290722666-24606-2-git-send-email-kirill@shutemov.name> (raw) In-Reply-To: <1290722666-24606-1-git-send-email-kirill@shutemov.name> From: Kirill A. Shutemov <kirill@shutemov.name> 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 <kirill@shutemov.name> --- 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 <stdlib.h> #include <assert.h> +#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
next prev parent reply other threads:[~2010-11-25 22:04 UTC|newest] Thread overview: 29+ messages / expand[flat|nested] mbox.gz Atom feed top 2010-11-25 22:04 [devel] [PATCH 0/3] optimize rpmsetcmp() Kirill A. Shutsemov 2010-11-25 22:04 ` Kirill A. Shutsemov [this message] 2010-11-25 22:04 ` [devel] [PATCH 2/3] set.c: optimize putbits() Kirill A. Shutsemov 2010-11-25 22:04 ` [devel] [PATCH 3/3] set.c: optimize decode_golomb() Kirill A. Shutsemov 2010-11-26 8:35 ` [devel] [PATCH 0/3] optimize rpmsetcmp() Kirill A. Shutemov 2010-11-30 0:35 ` Dmitry V. Levin 2010-12-02 21:48 ` Dmitry V. Levin 2010-12-04 13:02 ` Alexey Tourbin 2010-12-04 16:30 ` Dmitry V. Levin 2010-12-04 16:55 ` Alexey Tourbin 2010-12-04 15:06 ` Alexey Tourbin 2010-12-04 16:29 ` Dmitry V. Levin 2010-12-04 16:42 ` Alexey Tourbin 2010-12-04 16:52 ` Dmitry V. Levin 2010-12-04 17:05 ` Alexey Tourbin 2010-12-04 17:52 ` Dmitry V. Levin 2010-12-04 21:28 ` Alexey Tourbin 2010-12-04 23:26 ` Dmitry V. Levin 2010-12-04 23:41 ` Alexey Tourbin 2010-12-05 0:03 ` Dmitry V. Levin 2010-12-05 0:21 ` Alexey Tourbin 2010-12-05 12:49 ` Michael Shigorin 2010-12-07 17:50 ` Dmitry V. Levin 2010-12-05 1:24 ` Alexey Tourbin 2010-12-05 11:18 ` Dmitry V. Levin 2010-12-05 12:39 ` Alexey Tourbin 2010-12-05 12:39 ` Michael Shigorin 2010-12-05 12:58 ` Alexey Tourbin 2010-12-05 15:27 ` Dmitry V. Levin
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=1290722666-24606-2-git-send-email-kirill@shutemov.name \ --to=kirill@shutemov.name \ --cc=at@altlinux.ru \ --cc=devel@lists.altlinux.org \ --cc=ldv@altlinux.org \ --cc=legion@altlinux.ru \ --cc=raorn@altlinux.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: link
ALT Linux Team development discussions This inbox may be cloned and mirrored by anyone: git clone --mirror http://lore.altlinux.org/devel/0 devel/git/0.git # If you have public-inbox 1.1+ installed, you may # initialize and index your mirror using the following commands: public-inbox-init -V2 devel devel/ http://lore.altlinux.org/devel \ devel@altlinux.org devel@altlinux.ru devel@lists.altlinux.org devel@lists.altlinux.ru devel@linux.iplabs.ru mandrake-russian@linuxteam.iplabs.ru sisyphus@linuxteam.iplabs.ru public-inbox-index devel Example config snippet for mirrors. Newsgroup available over NNTP: nntp://lore.altlinux.org/org.altlinux.lists.devel AGPL code for this site: git clone https://public-inbox.org/public-inbox.git