0

I'm looking into suggestions on how to convert a 64-bit die revision field into a 32-bit MAC address I can use a for a wireless application to avoid collisions.

The die information is

struct {
   uint32_t lot;
   uint16_t X_coordinate;
   uint16_t Y_coordinate;
}

I don't know the range of coordinates, but based on a few samples, I think the coordinates are limited to < 256. That effectly reduces the space by 2 bytes. But the lot number is fully populated.

I'm going to try this (pseudocode to make it readable, I'm leaving the casts out)

MAC =  X_coordinate | Y_coordinate << 8 | lot << 16;

and throw away the top 16 bits of the lot and the top 8 bits of the coordinates. I feel though that maybe I should XOR in the top 16 bits of the lot somewhere, but I have no experience with this in the real world.

Here is a sample of die revision information: little endian byte dump

lot/wafer ID    X coordinate    Y coordinate
C3 1B B0 46     20 00           22 00
CB 8B 94 46     14 00           32 00
CB 8B 94 46     27 00           1E 00
B9 F7 80 6F     20 00           08 00
Mark Lakata
  • 19,989
  • 5
  • 106
  • 123
  • It looks like no matter how you slice it you're going to have collisions. You can't fit 46 bits (or did I misunderstand?) of data into 32 bits without collisions. Unless you can narrow down your range of data, you might just want to go with a hashing algorithm written by a person much smarter than either of us (number theorist). – Floegipoky Nov 19 '13 at 23:50
  • I want to make collisions as unlikely as possible. If it is done right, the probability of collisions is 1:4 billion. That's acceptable. If it is done wrong, it could be worse. I am hoping someone smart (or wiser) than me has done this before and has an answer. I'm pretty sure that answer depends on knowing the distribution of "lot" numbers. I don't know that. – Mark Lakata Nov 20 '13 at 01:46
  • (ps. it's 48 bits = 32+8+8) – Mark Lakata Nov 20 '13 at 01:47
  • Assuming a uniform, pseudorandom hash distribution (which would be the actual probability's lower bound), the [birthday problem](http://en.wikipedia.org/wiki/Birthday_attack) applies. If you have 50k hashes, there is a 25% chance that there will be a collision. With 77k it bumps to 50%. Like I said, this is the lowest possible chance. If the hashing algorithm is unbalanced the probability increases. I don't know how many hashes you're going to be using at once, but you may end up needing to expect collisions – Floegipoky Nov 20 '13 at 17:12
  • This is a local 900 MHz wireless network, probably with less than 100 nodes. – Mark Lakata Nov 20 '13 at 17:31
  • I guess my question is, is there any advantage to XOR'ing the upper bits (>32) back into the lower bits (<32), or should I just truncate the upper bits at 32? – Mark Lakata Nov 20 '13 at 17:32
  • I'd just pick one of [these](http://www.partow.net/programming/hashfunctions/#Download) and not worry about it :) – Floegipoky Nov 20 '13 at 17:45
  • @MarkLakata did you sort this problem out? I have the exact same question regarding 4 byte ID for 900MHz network using MSP430. Did you end up using the hash function? – Tibbe Oct 11 '18 at 12:48
  • @Tibbe - no, I never got a "real" answer. I think I just did what I proposed in the question. The company that I was contracted for doesn't exist anymore, so it was never a problem :) – Mark Lakata Oct 12 '18 at 19:25
  • @Tibbe You might consider [Dynamic perfect hashing](https://en.wikipedia.org/wiki/Dynamic_perfect_hashing). It takes a bit more memory, but it guarantees no collisions. If your table is updated very infrequently, look at [Perfect hash function](https://en.wikipedia.org/wiki/Perfect_hash_function). – Jim Mischel Oct 13 '18 at 06:10

0 Answers0