ofproto: Move 'max_ports' from ofproto-dpif.c to ofproto.c.

This allows port numbers in actions and elsewhere in OpenFlow messages to
be checked at a higher level.

Signed-off-by: Ben Pfaff <blp@nicira.com>
ofproto: Move ofpacts_check() calls from ofproto-dpif to ofproto.

Signed-off-by: Ben Pfaff <blp@nicira.com>
flow: Fully separate FWW_* from OFPFW10_*.

It might have been a useful optimization at one point to have FWW_*
correspond in OFPFW10_* where possible, but it doesn't seem worthwhile for
only 3 corresponding values.  It also makes the code somewhat more
confusing.

Signed-off-by: Ben Pfaff <blp@nicira.com>
flow: Use bit-mask for DSCP and ECN bits, instead of FWW_* flags.

Signed-off-by: Ben Pfaff <blp@nicira.com>
flow: Use bit-mask for TTL match, instead of FWW_* flag.

Signed-off-by: Ben Pfaff <blp@nicira.com>
flow: Use bit-mask for IP protocol match, instead of FWW_* flag.

Signed-off-by: Ben Pfaff <blp@nicira.com>
flow: Use bit-mask for Ethernet type match, instead of FWW_* flag.

Signed-off-by: Ben Pfaff <blp@nicira.com>
flow: Use bit-mask for in_port match, instead of FWW_* flag.

Signed-off-by: Ben Pfaff <blp@nicira.com>
flow: Ensure that padding is always zeroed.

Signed-off-by: Ben Pfaff <blp@nicira.com>
flow: Take advantage of zero-padding in struct flow and flow_wildcards.

Since we know these bytes are always 0 in both structures, we can use
faster functions that only work with full words.

Signed-off-by: Ben Pfaff <blp@nicira.com>
flow: Replace flow_wildcards members by a single "struct flow".

Signed-off-by: Ben Pfaff <blp@nicira.com>
flow: Remove flow_wildcards_is_exact().

It's only used in a not-very-useful assertion in some test code.  In
general, exact-match flows make very little sense anymore, and they're
basically on their way out.

Signed-off-by: Ben Pfaff <blp@nicira.com>
flow: Simplify many functions for working with flows and wildcards.

Now that "struct flow" and "struct flow_wildcards" have the same simple
and uniform structure, it's easy to handle common operations by just
iterating over the bits inside them.

Signed-off-by: Ben Pfaff <blp@nicira.com>
util: New function zero_rightmost_1bit().

It's probably easier to understand
	x = zero_rightmost_1bit(x);
than
	x &= x - 1;

Signed-off-by: Ben Pfaff <blp@nicira.com>
util: New function popcount().

This is the fastest portable implementation among the ones below, as
measured with GCC 4.4 on a Xeon X3430.  The measeured times were, in
seconds:

popcount1    25.6
popcount2     6.9 (but is not portable)
popcount3    31.4
popcount4    25.6
popcount5    61.6 (and is buggy)
popcount6    64.6
popcount7    32.3
popcount8    11.2

int
popcount1(unsigned int x)
{
    return __builtin_popcount(x);
}

int
popcount2(unsigned int x)
{
    unsigned int y;
    asm("popcnt %1, %0" : "=r" (y) : "g" (x));
    return y;
}

int
popcount3(unsigned int x)
{
    unsigned int n;

    n = (x >> 1) & 033333333333;
    x -= n;
    n = (n >> 1) & 033333333333;
    x -= n;
    x = (x + (x >> 3)) & 030707070707;
    return x % 63;
}

int
popcount4(unsigned int x)
{
    x -= (x >> 1) & 0x55555555;
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0f0f0f0f;
    x += x >> 8;
    x += x >> 16;
    return x & 0x3f;
}

int
popcount5(unsigned int x)
{
    int n;

    n = 0;
    while (x) {
        if (x & 0xf) {
            n += ((0xe9949440 >> (x & 0xf)) & 3) + 1;
        }
        x >>= 4;
    }
    return n;
}

int
popcount6(unsigned int x)
{
    int n;

    n = 0;
    while (x) {
        n += (0xe994 >> (x & 7)) & 3;
        x >>= 3;
    }
    return n;
}

int
popcount7(unsigned int x)
{
    static const int table[16] = {
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4
    };

    return (table[x & 0xf]
            + table[(x >> 4) & 0xf]
            + table[(x >> 8) & 0xf]
            + table[(x >> 12) & 0xf]
            + table[(x >> 16) & 0xf]
            + table[(x >> 20) & 0xf]
            + table[(x >> 24) & 0xf]
            + table[x >> 28]);
}

static int
popcount8(unsigned int x)
{
    ((((X) & (1 << 0)) != 0) +                  \
     (((X) & (1 << 1)) != 0) +                  \
     (((X) & (1 << 2)) != 0) +                  \
     (((X) & (1 << 3)) != 0) +                  \
     (((X) & (1 << 4)) != 0) +                  \
     (((X) & (1 << 5)) != 0) +                  \
     (((X) & (1 << 6)) != 0) +                  \
     (((X) & (1 << 7)) != 0))

    static const uint8_t popcount8[256] = {
        INIT64(0), INIT64(64), INIT64(128), INIT64(192)
    };

    return (popcount8[x & 0xff] +
            popcount8[(x >> 8) & 0xff] +
            popcount8[(x >> 16) & 0xff] +
            popcount8[x >> 24]);
}

int
main(void)
{
    unsigned long long int x;
    int n;

    n = 0;
    for (x = 0; x <= UINT32_MAX; x++) {
        n += popcount8(x);
    }
    printf("%d\n", n);

    return 0;
}

Signed-off-by: Ben Pfaff <blp@nicira.com>
classifier: Fix typo in comment.

Signed-off-by: Ben Pfaff <blp@nicira.com>
classifier: Break cls_rule 'flow' and 'wc' members into new "struct match".

Signed-off-by: Ben Pfaff <blp@nicira.com>
classifier: Prepare for "struct cls_rule" needing to be destroyed.

Until now, "struct cls_rule" didn't own any data outside its own memory
block.  An upcoming commit will make "struct cls_rule" sometimes own blocks
of memory, so it needs "destroy" and to a lesser extent "clone" functions.
This commit adds these in advance, even though they are mostly no-ops, to
make it possible to separately review the memory management.

Signed-off-by: Ben Pfaff <blp@nicira.com>
classifier: Optimize iteration with a catch-all target rule.

When cls_cursor_init() is given a NULL target, it can skip an expensive
step comparing the rule against the target for every table and every rule
in the classifier.  collect_rule_loose() and other callers could take
advantage of this optimization, except that they actually pass in a rule
that matches everything instead of a NULL rule (e.g. for "ovs-ofctl
dump-flows <bridge>" without specifying a matching rule).

This optimizes that case.

Signed-off-by: Ben Pfaff <blp@nicira.com>
util: New function raw_ctz().

This will acquire a user in an upcoming commit.

Signed-off-by: Ben Pfaff <blp@nicira.com>