chiark / gitweb /
Add a new function to compute the leftmost bit of a uint32_t
authorRichard Kettlewell <rjk@greenend.org.uk>
Sat, 19 Apr 2008 10:43:07 +0000 (11:43 +0100)
committerRichard Kettlewell <rjk@greenend.org.uk>
Sat, 19 Apr 2008 10:43:07 +0000 (11:43 +0100)
lib/Makefile.am
lib/bits.c [new file with mode: 0644]
lib/bits.h [new file with mode: 0644]
lib/t-bits.c [new file with mode: 0644]
lib/test.c
lib/test.h

index a7536d8..7f225bd 100644 (file)
@@ -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 (file)
index 0000000..d570e64
--- /dev/null
@@ -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 <config.h>
+#include "types.h"
+
+#include <math.h>
+
+#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 (file)
index 0000000..856db68
--- /dev/null
@@ -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 (file)
index 0000000..846abb8
--- /dev/null
@@ -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:
+*/
index c205a57..30af3a5 100644 (file)
@@ -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;
 }
   
index 2dac634..32eaa6f 100644 (file)
@@ -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 */