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 \
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
--- /dev/null
+/*
+ * 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:
+*/
--- /dev/null
+/*
+ * 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:
+*/
--- /dev/null
+/*
+ * 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:
+*/
#include "test.h"
-int tests, errors;
+long long tests, errors;
int fail_first;
void count_error(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;
}
#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 */
void test_utf8(void);
void test_words(void);
void test_wstat(void);
+void test_bits(void);
#endif /* TEST_H */
~mdw / disorder / commitdiff