X-Git-Url: https://git.tcpdump.org/libpcap/blobdiff_plain/c700a2f42df3d1076cc007676e139a35f4c6fdf8..c909e8a31ffcbb7f1a41bb801392e14f5d20e1fc:/optimize.c diff --git a/optimize.c b/optimize.c index 19980dc8..d72cf7a4 100644 --- a/optimize.c +++ b/optimize.c @@ -18,26 +18,14 @@ * 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 #endif -#ifdef _WIN32 -#include -#else /* _WIN32 */ -#if HAVE_INTTYPES_H -#include -#elif HAVE_STDINT_H -#include -#endif -#ifdef HAVE_SYS_BITYPES_H -#include -#endif -#include -#endif /* _WIN32 */ +#include #include #include @@ -58,30 +46,87 @@ 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 +#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 , 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 and declares ffs() there, + * or some other platform (UN*X conforming to a sufficient recent version + * of the Single UNIX Specification). + */ + #include + #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 @@ -127,7 +172,7 @@ struct vmapinfo { 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 @@ -210,7 +255,7 @@ struct _opt_state { struct vmapinfo *vmap; struct valnode *vnode_base; struct valnode *next_vnode; -}; +} opt_state_t; typedef struct { /* @@ -590,7 +635,7 @@ F(opt_state_t *opt_state, int code, int v0, int v1) 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; @@ -1254,8 +1299,9 @@ opt_blk(compiler_state_t *cstate, struct icode *ic, opt_state_t *opt_state, * 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; @@ -1380,7 +1426,7 @@ opt_j(opt_state_t *opt_state, struct edge *ep) 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; @@ -2258,8 +2304,8 @@ install_bpf_program(pcap_t *p, struct bpf_program *fp) 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); @@ -2287,7 +2333,7 @@ dot_dump_node(struct icode *ic, struct block *block, struct bpf_program *prog, } 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]); @@ -2346,10 +2392,8 @@ dot_dump(compiler_state_t *cstate, struct icode *ic) 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");