* 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
-#include "config.h"
+#include <config.h>
#endif
-#ifdef _WIN32
-#include <pcap-stdinc.h>
-#else /* _WIN32 */
-#if HAVE_INTTYPES_H
-#include <inttypes.h>
-#elif HAVE_STDINT_H
-#include <stdint.h>
-#endif
-#ifdef HAVE_SYS_BITYPES_H
-#include <sys/bitypes.h>
-#endif
-#include <sys/types.h>
-#endif /* _WIN32 */
+#include <pcap-types.h>
#include <stdio.h>
#include <stdlib.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
bpf_int32 const_val;
};
-struct _opt_state {
+typedef struct {
/*
* A flag to indicate that further optimization is needed.
* Iterative passes are continued until a given pass yields no
struct vmapinfo *vmap;
struct valnode *vnode_base;
struct valnode *next_vnode;
-};
+} opt_state_t;
typedef struct {
/*
static inline void
vstore(struct stmt *s, int *valp, int newval, int alter)
{
- if (alter && *valp == newval)
+ if (alter && newval != VAL_UNKNOWN && *valp == newval)
s->code = NOP;
else
*valp = newval;
* block, can we eliminate it?
*/
if (do_stmts &&
- ((b->out_use == 0 && aval != 0 && b->val[A_ATOM] == aval &&
- xval != 0 && b->val[X_ATOM] == xval) ||
+ ((b->out_use == 0 &&
+ aval != VAL_UNKNOWN && b->val[A_ATOM] == aval &&
+ xval != VAL_UNKNOWN && b->val[X_ATOM] == xval) ||
BPF_CLASS(b->s.code) == BPF_RET)) {
if (b->stmts != 0) {
b->stmts = 0;
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);
}
fprintf(out, "\" tooltip=\"");
for (i = 0; i < BPF_MEMWORDS; i++)
- if (block->val[i] != 0)
+ if (block->val[i] != VAL_UNKNOWN)
fprintf(out, "val[%d]=%d ", i, block->val[i]);
fprintf(out, "val[A]=%d ", block->val[A_ATOM]);
fprintf(out, "val[X]=%d", block->val[X_ATOM]);
f.bf_insns = icode_to_fcode(cstate, ic, ic->root, &f.bf_len);
fprintf(out, "digraph BPF {\n");
- ic->cur_mark = 0;
unMarkAll(ic);
dot_dump_node(ic, ic->root, &f, out);
- ic->cur_mark = 0;
unMarkAll(ic);
dot_dump_edge(ic, ic->root, out);
fprintf(out, "}\n");
projects / libpcap / blobdiff