Calculating Ethernet Multicast filter HASH value (?)

[hpipon957]

Posted on May 23, 2014 at 03:03

Hi All

It is strange but I can't find any code example of how to set up the Ethernet HASH filter for multicast reception. There was a question in 2011 in this forum as to the same but it was not answered - so I will try again. At the moment I am working with the ALL MULTICAST bit set so that all multicast frames are received - the reason being that the HASH calculation is presently making no sense. An example - I join a multicast group 224.0.0.33 and would like to set a multicast filter on the corresponding MAC address 01 00 5e 00 00 21 The CRC-32 calculation of this is 0xe2dae536 - taking the 6 MS bits it gives the hash 0x38 so the 24th bit in the high hash register is set. The result is however no reception on the address. Playing around with the bits in the HASH registers it is found, by trial-and-error, that reception works when the 5th bit in that register is set instead (hash value 0x24) OK - I thought - there must be a mis-understanding in the calculation so I studied the user's manual again and looked at two examples that are given there: - 1f52 419c b6af   should give 0x2c (bit 12 to be set in the high register) - a00a 9800 0045 should give 0x07 (7th bit in the low register) When I put these through a CRC-32 IEEE calculation with CRC primed with 0xffffffff I get 0xdd39bb32 and 0x63d32b47 respectively, meaning that they would give HASH values of 0x37 and 0x18 respectively, not as the user's manual suggests and presumably also giving incorrect filtering results. The CRC32 IEEE calculation I use is used in other projects and also matches with a HW CRC-32 IEEE result, confirmed by calculating Ethernet frame content too. It also works as expected when used to calculate HASH values for other Ethernet multicasting applications with other devices using the same technique, and having essentially identical instructions in their user manuals. So the questions are: - What is the calculation to be used to get the HASH setting correct? - Is there any code that uses this? (I find plenty of multi-casting code in examples but with nothing more than a note to say  that the filter could be set up if required - is this because no code has successfully been able to do it??) Regards Mark #ethernet-stm32-multicast-hash

[Tesla DeLorean]

Posted on May 23, 2014 at 07:28

DD39BB32 ~22C644CD 2C

63D32B47 ~9C2CD4B8 07 E2DAE536 ~1D251AC9 24 Low Order 6-bits, Invert, Reverse 0x36 -> 0xC9 -> 11 001001 -> 100100 -> 0x24 Or Hash = (Rev32(~Crc) >> 26);

uint32_t Rev32(uint32_t x)
{
uint32_t y;
int i;
y = 0;
for(i=0; i<
32
; i++)
if (x & (1 << i))
y |= 1 << (31 - i);
return(y);
}
uint32_t MacHash(uint8_t *Mac) // sourcer32@gmail.com
{
int i, j;
uint32_t Crc;
Crc
= 
0xFFFFFFFF
;
for(
j
=
0
; j<6; j++)
{
Crc
= Crc ^ (uint32_t)Mac[j];
for(
i
=
0
; i<8; i++)
if (Crc & 1)
Crc = (Crc >> 1) ^ 0xEDB88320; // Reversed 0x04C11DB7
else
Crc = (Crc >> 1);
}
return(Rev32(~Crc) >> 26); // Get High order 6-bit in reversed/inverted CRC
}
static const uint8_t Test1[] = { 0x1F, 0x52, 0x41, 0x9C, 0xB6, 0xAF }; // 0x2C
static const uint8_t Test2[] = { 0xA0, 0x0A, 0x98, 0x00, 0x00, 0x45 }; // 0x07
static const uint8_t Test3[] = { 0x01, 0x00, 0x5e, 0x00, 0x00, 0x21 }; // 0x24
printf(''MacHash %02
X'', MacHash(Test1));
printf(''MacHash %02
X'', MacHash(Test2));
printf(''MacHash %02
X'', MacHash(Test3));

[Tesla DeLorean]

Posted on May 23, 2014 at 08:06

And a faster implementation...

uint32_t MacHashFast(const uint8_t *Mac) // sourcer32@gmail.com
{
static const uint32_t Rev6Tbl[] = {
0x00,0x20,0x10,0x30,0x08,0x28,0x18,0x38,0x04,0x24,0x14,0x34,0x0C,0x2C,0x1C,0x3C,
0x02,0x22,0x12,0x32,0x0A,0x2A,0x1A,0x3A,0x06,0x26,0x16,0x36,0x0E,0x2E,0x1E,0x3E,
0x01,0x21,0x11,0x31,0x09,0x29,0x19,0x39,0x05,0x25,0x15,0x35,0x0D,0x2D,0x1D,0x3D,
0x03,0x23,0x13,0x33,0x0B,0x2B,0x1B,0x3B,0x07,0x27,0x17,0x37,0x0F,0x2F,0x1F,0x3F };
static const uint32_t Crc32Tbl[] = {
0x4DBDF21C, 0x500AE278, 0x76D3D2D4, 0x6B64C2B0,
0x3B61B38C, 0x26D6A3E8, 0x000F9344, 0x1DB88320,
0xA005713C, 0xBDB26158, 0x9B6B51F4, 0x86DC4190,
0xD6D930AC, 0xCB6E20C8, 0xEDB71064, 0xF0000000 };
int i;
uint32_t Crc;
Crc = 0;
for(i=0; i<
6
; i++)
{
Crc
= Crc ^ (uint32_t)Mac[i];
Crc = (Crc >> 4) ^ Crc32Tbl[Crc & 0x0F]; /* lower nibble */
Crc = (Crc >> 4) ^ Crc32Tbl[Crc & 0x0F]; /* upper nibble */
}
return(Rev6Tbl[Crc & 0x3F]);
}

[hpipon957]

Posted on May 23, 2014 at 15:06

Hi Clive

Many thanks for the information; I had tried various swaps and shifts in the hope of finding something that matched but was concentrating on the MSB. I did take a quick look at the LSB but didn't recognise the manipulation needed at a quick glance. However in the user's manual it is stated: ''For hash filtering, the MAC uses the 6 upper CRC bits of the received multicast address to index the content of the Hash table'' which doesn't give one much change of getting it right without a tip from an insider. Maybe it should read ''For hash filtering, the MAC uses the 6

lower

CRC bits of the received multicast address to index the content of the Hash table

, after inverting and reversing the bit order

'' But I am good now - just lost a few hours sleep last night trying to work it out before temporarily giving up. Regards Mark

[Tesla DeLorean]

Posted on May 23, 2014 at 15:50

The problem here really is an endian/shift direction one. In terms of what the polynomial is doing, it is the high order 6-bits.

The 8-bit data is LSB first right shifting, and the CRC is 32-bit left shifting 0x04C11DB7. In order to be computationally efficient it makes more sense to stand the CRC on it's head so the data and the CRC shift in the same direction, and a single XOR is required to merge the two bit streams. One could do it in the normal sense of the CRC, but this would require a bit reversal of each data byte. As a bonus, we have the seeding of CRC-32, and the bit-inversion at the end, basically making sure 0x00 bytes generate a check sum

[Tesla DeLorean]

Posted on May 23, 2014 at 16:13

0x04C11DB7 LEFT 0xEDB88320 RIGHT

[hpipon957]

Posted on May 24, 2014 at 00:53

Hi Clive

I am not a good enough mathematician to see all details without a lot of study but the HASH in the Freescale devices (Coldfire and Kinetis - using both big and little endian) is calculated using the same CRC code with the polynomial direction reversed (for efficiency as in yours): see http://git.ti.com/keystone-linux/linux/blobs/8d82f219c2d476811cd3157a39c7b5c1f045ebc3/drivers/net/ethernet/freescale/fec.c Here they also specify that the HASH is the ''6 MSbits of the CRC'' and to get the 6 bit HASH value they shift 26 bits to the right. I don't see the difference with your CRC32 calculation - they give the same 32 bit values - but in the ST case the 6 LSBs are used after negating and bit inversing and in the Freescael case the 6 at the other end are used. This tells me that there is a difference in the implemention (as to which CRC bits are fed to the HASH logic) rather than in the terminology. But as I said, I'm good with it. I'm no mathematician - just a coding monkey and now what comes out is correct so whatever I am putting in must now be good... Regards Mark

[Tesla DeLorean]

Wow the forum transition butchered the posts

uint32_t MacHashFast(const uint8_t *Mac) // sourcer32@gmail.com
{
  static const uint32_t Rev6Tbl[] = {
    0x00,0x20,0x10,0x30,0x08,0x28,0x18,0x38,
    0x04,0x24,0x14,0x34,0x0C,0x2C,0x1C,0x3C,
    0x02,0x22,0x12,0x32,0x0A,0x2A,0x1A,0x3A,
    0x06,0x26,0x16,0x36,0x0E,0x2E,0x1E,0x3E,
    0x01,0x21,0x11,0x31,0x09,0x29,0x19,0x39,
    0x05,0x25,0x15,0x35,0x0D,0x2D,0x1D,0x3D,
    0x03,0x23,0x13,0x33,0x0B,0x2B,0x1B,0x3B,
    0x07,0x27,0x17,0x37,0x0F,0x2F,0x1F,0x3F };
 
  static const uint32_t Crc32Tbl[] = {
    0x4DBDF21C, 0x500AE278, 0x76D3D2D4, 0x6B64C2B0,
    0x3B61B38C, 0x26D6A3E8, 0x000F9344, 0x1DB88320,
    0xA005713C, 0xBDB26158, 0x9B6B51F4, 0x86DC4190,
    0xD6D930AC, 0xCB6E20C8, 0xEDB71064, 0xF0000000 };
 
  int i;
  uint32_t Crc;
 
  Crc = 0;
 
  for(i=0; i<6; i++)
  {
    Crc = Crc ^ (uint32_t)Mac[i];
 
    Crc = (Crc >> 4) ^ Crc32Tbl[Crc & 0x0F];  /* lower nibble */
    Crc = (Crc >> 4) ^ Crc32Tbl[Crc & 0x0F];  /* upper nibble */
  }
 
  return(Rev6Tbl[Crc & 0x3F]);
}

[Tesla DeLorean]

Test fixture of slow and fast methods

// STM32 MACHASH - Copyright (C) 2014-2018 Clive Turvey (sourcer32@gmail.com)
//  All Rights Reserved
 
#include <windows.h>
 
#include <stdio.h>
#include <stdlib.h>
 
typedef unsigned char uint8_t;
typedef unsigned long uint32_t;
 
uint32_t Rev32(uint32_t x)
{
  uint32_t y;
  int i;
 
  y = 0;
 
  for(i=0; i<32; i++)
    if (x & (1 << i))
      y |= 1 << (31 - i);
 
  return(y);
}
 
uint32_t MacHash(const uint8_t *Mac) // sourcer32@gmail.com
{
  int i, j;
  uint32_t Crc;
 
  Crc = 0xFFFFFFFF;
 
  for(j=0; j<6; j++)
  {
    Crc = Crc ^ (uint32_t)Mac[j];
 
    for(i=0; i<8; i++)
      if (Crc & 1)
        Crc = (Crc >> 1) ^ 0xEDB88320; // Reversed 0x04C11DB7
      else
        Crc = (Crc >> 1);
  }
 
  return(Rev32(~Crc) >> 26); // Get High order 6-bit in reversed/inverted CRC
}
 
uint32_t MacHashFast(const uint8_t *Mac) // sourcer32@gmail.com
{
  static const uint32_t Rev6Tbl[] = {
    0x00,0x20,0x10,0x30,0x08,0x28,0x18,0x38,
    0x04,0x24,0x14,0x34,0x0C,0x2C,0x1C,0x3C,
    0x02,0x22,0x12,0x32,0x0A,0x2A,0x1A,0x3A,
    0x06,0x26,0x16,0x36,0x0E,0x2E,0x1E,0x3E,
    0x01,0x21,0x11,0x31,0x09,0x29,0x19,0x39,
    0x05,0x25,0x15,0x35,0x0D,0x2D,0x1D,0x3D,
    0x03,0x23,0x13,0x33,0x0B,0x2B,0x1B,0x3B,
    0x07,0x27,0x17,0x37,0x0F,0x2F,0x1F,0x3F };
 
  static const uint32_t Crc32Tbl[] = {
    0x4DBDF21C, 0x500AE278, 0x76D3D2D4, 0x6B64C2B0,
    0x3B61B38C, 0x26D6A3E8, 0x000F9344, 0x1DB88320,
    0xA005713C, 0xBDB26158, 0x9B6B51F4, 0x86DC4190,
    0xD6D930AC, 0xCB6E20C8, 0xEDB71064, 0xF0000000 };
 
  int i;
  uint32_t Crc;
 
  Crc = 0;
 
  for(i=0; i<6; i++)
  {
    Crc = Crc ^ (uint32_t)Mac[i];
 
    Crc = (Crc >> 4) ^ Crc32Tbl[Crc & 0x0F];  /* lower nibble */
    Crc = (Crc >> 4) ^ Crc32Tbl[Crc & 0x0F];  /* upper nibble */
  }
 
  return(Rev6Tbl[Crc & 0x3F]);
}
 
int main(int argc, char **argv)
{
  static const uint8_t Test1[] = { 0x1F, 0x52, 0x41, 0x9C, 0xB6, 0xAF }; // 0x2C
  static const uint8_t Test2[] = { 0xA0, 0x0A, 0x98, 0x00, 0x00, 0x45 }; // 0x07
  static const uint8_t Test3[] = { 0x01, 0x00, 0x5e, 0x00, 0x00, 0x21 }; // 0x24
 
  printf("MacHash %02X\n", MacHash(Test1));
  printf("MacHash %02X\n", MacHash(Test2));
  printf("MacHash %02X\n", MacHash(Test3));
 
  printf("MacHashFast %02X\n", MacHashFast(Test1));
  printf("MacHashFast %02X\n", MacHashFast(Test2));
  printf("MacHashFast %02X\n", MacHashFast(Test3));
 
  return(1);
}