Re: A tiny almost sorta kinda nearly minimal perfect hash for a mac classifier?

[Sean Conner <sean@conman.org>]

It was thus said that the Great Dave Taht once stated:
> On Mon, Nov 14, 2011 at 3:41 AM, Fred Baker <fred@cisco.com> wrote:
> >
> > On Nov 14, 2011, at 10:22 AM, Sean Conner wrote:
> >
> >> �Why not just use the lower N bits as the hash function?
> >
> > or
> >
> > unsigned macHash (unsigned long long �macAddressClone) {
> > � � return 0xFFF & (macAddressClone ^ (macAddressClone >> 12));
> > }
> >
> > That allows you to keep different OUIs separated somewhat.
> 
> I should probably not have used 'arp' as an example, but suggested tcpdump.
> 
> Multicast and broadcast on 802.11 are 'special'. They are always
> transmitted at the lowest rate possible (and eat up correspondingly
> far more airtime), and in the case of power save mode, can be deferred
> up to 200 ms, to wait for stations to be awake enough to 'hear' them.
> So anything with the multicast mac bit set should end up dumped in a
> special queue to manage that better.
> 
> Virtual interfaces on a given radio twiddle on the local mac bit and
> then do arbitrary transforms elsewhere on the mac

  The format for a MAC address is:

+--------+--------+--------+--------+--------+--------+
|      lg|        |        |        |        |        |
+--------+--------+--------+--------+--------+--------+
\______||____OUI___________/
       ||
       |+-- group/individual bit (1 = multicast/broadcast)
       +--- global/local assigned address (1 = local)

Given that, I would then write the hash code as:

typdef union macaddr
{
  uint8_t  bit8[6];
  uint16_t bit16[3];
} macaddr__t;

typedef enum macqueue
{
  MACQ_NORMAL,
  MACQ_SPECIAL
} macqueue__t;

macqueue__t mac_hash(unsigned int *phash,macaddr__t addr)
{
  *phash = addr.bit16[2] & 0x0FFF;
  if (addr.bit8[0] & 0x01)
    return MACQ_SPECIAL;
  else
    return MACQ_NORMAL;
  /*------------
  ; if I was very concerned with speed, I would do:
  ;     return addr.bit8[0] & 0x01;
  ; but I opted for clarity here, not speed
  ;---------------*/
}

The broadcast MAC address is FF:FF:FF:FF:FF:FF while a multicast MAC address
is based off the IP multicast address, but the global bit is set, for
example: 01:00:5E:7F:00:01.  This way, if you want to set
broadcasts/multicasts on their own special queue, you can (heck, you can
even have a separate hash table for them given this).  I don't see how
locally defined addresses will mess this up, unless I see actual, real world
evidence.  

  -spc (Measure twice, cut once and all that ... )