* WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
* MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
*
- * Optimization module for tcpdump intermediate representation.
+ * Optimization module for BPF code intermediate representation.
*/
#ifdef HAVE_CONFIG_H
int pcap_optimizer_debug;
#endif
-#if defined(MSDOS) && !defined(__DJGPP__)
-extern int _w32_ffs (int mask);
-#define ffs _w32_ffs
-#endif
-
/*
- * So is the check for _MSC_VER done because MinGW has this?
+ * lowest_set_bit().
+ *
+ * Takes a 32-bit integer as an argument.
+ *
+ * If handed a non-zero value, returns the index of the lowest set bit,
+ * counting upwards fro zero.
+ *
+ * If handed zero, the results are platform- and compiler-dependent.
+ * Keep it out of the light, don't give it any water, don't feed it
+ * after midnight, and don't pass zero to it.
+ *
+ * This is the same as the count of trailing zeroes in the word.
*/
-#if defined(_WIN32) && defined (_MSC_VER)
+#if PCAP_IS_AT_LEAST_GNUC_VERSION(3,4)
+ /*
+ * GCC 3.4 and later; we have __builtin_ctz().
+ */
+ #define lowest_set_bit(mask) __builtin_ctz(mask)
+#elif defined(_MSC_VER)
+ /*
+ * Visual Studio; we support only 2005 and later, so use
+ * _BitScanForward().
+ */
+#include <intrin.h>
+#pragma intrinsic(_BitScanForward)
+
+static __forceinline int
+lowest_set_bit(int mask)
+{
+ unsigned long bit;
+
+ /*
+ * Don't sign-extend mask if long is longer than int.
+ * (It's currently not, in MSVC, even on 64-bit platforms, but....)
+ */
+ if (_BitScanForward(&bit, (unsigned int)mask) == 0)
+ return -1; /* mask is zero */
+ return (int)bit;
+}
+#elif defined(MSDOS) && defined(__DJGPP__)
+ /*
+ * MS-DOS with DJGPP, which declares ffs() in <string.h>, which
+ * we've already included.
+ */
+ #define lowest_set_bit(mask) (ffs((mask)) - 1)
+#elif (defined(MSDOS) && defined(__WATCOMC__)) || defined(STRINGS_H_DECLARES_FFS)
+ /*
+ * MS-DOS with Watcom C, which has <strings.h> and declares ffs() there,
+ * or some other platform (UN*X conforming to a sufficient recent version
+ * of the Single UNIX Specification).
+ */
+ #include <strings.h>
+ #define lowest_set_bit(mask) (ffs((mask)) - 1)
+#else
/*
- * ffs -- vax ffs instruction
- *
- * XXX - with versions of VS that have it, use _BitScanForward()?
+ * None of the above.
+ * Use a perfect-hash-function-based function.
*/
static int
-ffs(int mask)
+lowest_set_bit(int mask)
{
- int bit;
+ unsigned int v = (unsigned int)mask;
+
+ static const int MultiplyDeBruijnBitPosition[32] = {
+ 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
+ 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
+ };
- if (mask == 0)
- return(0);
- for (bit = 1; !(mask & 1); bit++)
- mask >>= 1;
- return(bit);
+ /*
+ * We strip off all but the lowermost set bit (v & ~v),
+ * and perform a minimal perfect hash on it to look up the
+ * number of low-order zero bits in a table.
+ *
+ * See:
+ *
+ * http://7ooo.mooo.com/text/ComputingTrailingZerosHOWTO.pdf
+ *
+ * http://supertech.csail.mit.edu/papers/debruijn.pdf
+ */
+ return (MultiplyDeBruijnBitPosition[((v & -v) * 0x077CB531U) >> 27]);
}
#endif
register bpf_u_int32 x = ep->edom[i];
while (x != 0) {
- k = ffs(x) - 1;
+ k = lowest_set_bit(x);
x &=~ (1 << k);
k += i * BITS_PER_WORD;
p->fcode.bf_len = fp->bf_len;
p->fcode.bf_insns = (struct bpf_insn *)malloc(prog_size);
if (p->fcode.bf_insns == NULL) {
- pcap_snprintf(p->errbuf, sizeof(p->errbuf),
- "malloc: %s", pcap_strerror(errno));
+ pcap_fmt_errmsg_for_errno(p->errbuf, sizeof(p->errbuf),
+ errno, "malloc");
return (-1);
}
memcpy(p->fcode.bf_insns, fp->bf_insns, prog_size);