sater@cs.vu.nl (Hans van Staveren) (04/07/89)
The AMD Lance Ethernet chip(and others) perform a hashing function on incoming multicast packets that hash the 48 bit multicast address to a 6 bit(0-63) value. Does anyone have the algorithm used? (preferrably ofcourse as debugged C) Thanks in advance, Hans van Staveren Vrije Universiteit Amsterdam, Holland
rpw3@amdcad.AMD.COM (Rob Warnock) (04/08/89)
In article <2262@sater.cs.vu.nl> sater@cs.vu.nl (Hans van Staveren) writes: +--------------- | The AMD Lance Ethernet chip(and others) perform a hashing function on incoming | multicast packets that hash the 48 bit multicast address to a 6 bit(0-63) | value. Does anyone have the algorithm used? (preferrably as debugged C) +--------------- I don't have it as C, but if you go get a LANCE data sheet, it contains listings for both 8086 assembler and BASIC code for computing the bit masks for multicast. The data sheet also describes in words what's going on, and gives a table of some sample addresses that would cause which bits to be needed in the hash register. (That's four *different* ways it's described!) The basic idea is this: The incoming packet is being fed into the CRC-32 register anyway, so just after the last bit of the source address has been shifted into the CRC register, the high-order 6 bits of the CRC are used to select one of the 64 bits in the hash filter register. If the address was multicast, and the selected bit of the hash filter register is set, the LANCE receives the packet. Possible things to watch out for: - Note that Ethernet addresses are sent least significant bit first *within* a byte (just like RS-232), and most significant byte first. Thus, the multi- cast address 0F-A0-13-00-00-00 appears on the wire as four 1's, nine 0's, a 1, a 0, three 1's, two 0's, a 1, and twenty-seven 0's (if I counted right), or, left-to-right, 111100000000010111001000000000000000000000000000. - The "high-order 6 CRC bits" are the ones "farthest" from the serial input, the ones that are last to get shifted into. See the D/I/X Ethernet spec for a diagram of the (reference) CRC register. - I don't know which order to read those 6 bits, but from the BASIC listing in the LANCE manual, I think the *highest* order CRC bit is read as the *low*-order bit of the 6-bit number. (The LANCE data sheet numbers the bits of the hash filter register from 63:0, so at least that mapping is easy.) - The CRC-32 is defined to start out with all 1's in the CRC register (preset). Shifting these 48 times does make *some* deterministic thing in the high 6 CRC bits, but I haven't bothered to compute it. In any case, the 6 bits for a simple multicast address like 0F-00-00-00-00-00 would not be itself a simple pattern, since those high order bits will cause several copies of the feedback terms to get XOR'd into the CRC reg. (In other words, boy & girls, if you try this with pencil & paper, you're just asking for a mistake... ;-} ) - For each multicast address you want to recognize, you run the algorithm and find which bit of 64 is set. The hash filter reg is set to the inclusive-OR of the bits from all the desired addresses. Note that if you are taking an address *out* of the hash filter, it's not correct to simply turn the corresponding bit off in the hash reg, as you might also be turning off other addresses which hashes to the same address. You need to completely reload the hash reg. (If you are going to be adding/deleting addresses a lot, cache the 6-bit bit number for each multicast address, so you can rebuild the mask quickly, or even keep a list thread sorted by hash bit number, so you can tell if any other addresses uses the same bit.) Good luck. Rob Warnock Systems Architecture Consultant UUCP: {amdcad,fortune,sun}!redwood!rpw3 DDD: (415)572-2607 USPS: 627 26th Ave, San Mateo, CA 94403