From f9d42b20477523bf2ab2172d51e78d2a398e117f Mon Sep 17 00:00:00 2001 Message-Id: From: Mark Wooding Date: Sat, 19 Apr 2008 11:43:07 +0100 Subject: [PATCH] Add a new function to compute the leftmost bit of a uint32_t Organization: Straylight/Edgeware From: Richard Kettlewell --- lib/Makefile.am | 3 +- lib/bits.c | 81 +++++++++++++++++++++++++++++++++++++++++++++++++ lib/bits.h | 40 ++++++++++++++++++++++++ lib/t-bits.c | 46 ++++++++++++++++++++++++++++ lib/test.c | 5 +-- lib/test.h | 3 +- 6 files changed, 174 insertions(+), 4 deletions(-) create mode 100644 lib/bits.c create mode 100644 lib/bits.h create mode 100644 lib/t-bits.c diff --git a/lib/Makefile.am b/lib/Makefile.am index a7536d8..7f225bd 100644 --- a/lib/Makefile.am +++ b/lib/Makefile.am @@ -28,6 +28,7 @@ libdisorder_a_SOURCES=charset.c charset.h \ authhash.c authhash.h \ basen.c basen.h \ base64.c base64.h \ + bits.c bits.h \ cache.c cache.h \ client.c client.h \ client-common.c client-common.h \ @@ -112,7 +113,7 @@ test_SOURCES=test.c memgc.c test.h t-addr.c t-basen.c t-cache.c \ t-casefold.c t-cookies.c t-filepart.c t-hash.c t-heap.c \ t-hex.c t-kvp.c t-mime.c t-printf.c t-regsub.c t-selection.c \ t-signame.c t-sink.c t-split.c t-unicode.c t-url.c t-utf8.c \ - t-words.c t-wstat.c + t-words.c t-wstat.c t-bits.c test_LDADD=libdisorder.a $(LIBPCRE) $(LIBICONV) $(LIBGC) test_DEPENDENCIES=libdisorder.a diff --git a/lib/bits.c b/lib/bits.c new file mode 100644 index 0000000..d570e64 --- /dev/null +++ b/lib/bits.c @@ -0,0 +1,81 @@ +/* + * This file is part of DisOrder + * Copyright (C) 2008 Richard Kettlewell + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 + * USA + */ + +/** @file lib/bits.c + * @brief Bit operations + */ + +#include +#include "types.h" + +#include + +#include "bits.h" + +/** @brief Compute index of leftmost 1 bit + * @param n Integer + * @return Index of leftmost 1 bit or -1 + * + * For positive @p n we return the index of the leftmost bit of @p n. For + * instance @c leftmost_bit(1) returns 0, @c leftmost_bit(15) returns 3, etc. + * + * If @p n is zero then -1 is returned. + */ +int leftmost_bit(uint32_t n) { + /* See e.g. Hacker's Delight s5-3 (p81) for where the idea comes from. + * Warren is computing the number of leading zeroes, but that's not quite + * what I wanted. Also this version should be more portable than his, which + * inspects the bytes of the floating point number directly. + */ + int x; + frexp((double)n, &x); + /* This gives: n = m * 2^x, where 0.5 <= m < 1 and x is an integer. + * + * If we take log2 of either side then we have: + * log2(n) = x + log2 m + * + * We know that 0.5 <= m < 1 => -1 <= log2 m < 0. So we floor either side: + * + * floor(log2(n)) = x - 1 + * + * What is floor(log2(n))? Well, consider that: + * + * 2^k <= z < 2^(k+1) => floor(log2(z)) = k. + * + * But 2^k <= z < 2^(k+1) is the same as saying that the leftmost bit of z is + * bit k. + * + * + * Warren adds 0.5 first, to deal with the case when n=0. However frexp() + * guarantees to return x=0 when n=0, so we get the right answer without that + * step. + */ + return x - 1; +} + + +/* +Local Variables: +c-basic-offset:2 +comment-column:40 +fill-column:79 +indent-tabs-mode:nil +End: +*/ diff --git a/lib/bits.h b/lib/bits.h new file mode 100644 index 0000000..856db68 --- /dev/null +++ b/lib/bits.h @@ -0,0 +1,40 @@ +/* + * This file is part of DisOrder + * Copyright (C) 2008 Richard Kettlewell + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 + * USA + */ + +/** @file lib/bits.h + * @brief Bit operations + */ + +#ifndef BITS_H +#define BITS_H + +int leftmost_bit(uint32_t n); + +#endif /* BITS_H */ + + +/* +Local Variables: +c-basic-offset:2 +comment-column:40 +fill-column:79 +indent-tabs-mode:nil +End: +*/ diff --git a/lib/t-bits.c b/lib/t-bits.c new file mode 100644 index 0000000..846abb8 --- /dev/null +++ b/lib/t-bits.c @@ -0,0 +1,46 @@ +/* + * This file is part of DisOrder. + * Copyright (C) 2008 Richard Kettlewell + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 + * USA + */ +#include "test.h" +#include "bits.h" + +void test_bits(void) { + int n; + + printf("test_bits\n"); + check_integer(leftmost_bit(0), -1); + check_integer(leftmost_bit(0x80000000), 31); + check_integer(leftmost_bit(0xffffffff), 31); + for(n = 0; n < 28; ++n) { + const uint32_t b = 1 << n, limit = 2 * b; + uint32_t v; + + for(v = b; v < limit; ++v) + check_integer(leftmost_bit(v), n); + } +} + +/* +Local Variables: +c-basic-offset:2 +comment-column:40 +fill-column:79 +indent-tabs-mode:nil +End: +*/ diff --git a/lib/test.c b/lib/test.c index c205a57..30af3a5 100644 --- a/lib/test.c +++ b/lib/test.c @@ -21,7 +21,7 @@ #include "test.h" -int tests, errors; +long long tests, errors; int fail_first; void count_error(void) { @@ -158,7 +158,8 @@ int main(void) { test_hash(); test_url(); test_regsub(); - fprintf(stderr, "%d errors out of %d tests\n", errors, tests); + test_bits(); + fprintf(stderr, "%lld errors out of %lld tests\n", errors, tests); return !!errors; } diff --git a/lib/test.h b/lib/test.h index 2dac634..32eaa6f 100644 --- a/lib/test.h +++ b/lib/test.h @@ -70,7 +70,7 @@ #include "url.h" #include "regsub.h" -extern int tests, errors; +extern long long tests, errors; extern int fail_first; /** @brief Checks that @p expr is nonzero */ @@ -153,6 +153,7 @@ void test_url(void); void test_utf8(void); void test_words(void); void test_wstat(void); +void test_bits(void); #endif /* TEST_H */ -- [mdw]