I have several devices. Each of them has its unique ID composed of 11 bytes, like: 0x34 0x57 0x36 0x31 0x38 0x39 0x15 0x0e 0x00 0x0f 0x00. I would like to generate unique number (0-32767 or 0-65535) to delay answer when FindDevices command is broadcasted. When devices start to answer at the same moment there is RS485 bus contention problem so I would like to avoid that.
My first attempt was to sum all the 11 bytes of unique ID, call srand(sum) to seed generator and then call rand() to get my value. But it's unfortunately poor solution and in my batch of devices I've got 2 devices with unique ID but the same "(not so)unique" number :(
UID1: 34 57 36 31 38 39 15 0e 00 0f 00 sum: 405 decimal generated number: 23860
UID2: 34 57 33 31 35 39 04 18 00 1c 00 sum: 405 decimal generated number: 23860
Devices don't know what number was generated in other devices or what unique IDs they have so they can't simply compare them.
Any idea how to generate such unique number (0-32767 or 0-65535)?
Edit:
List of unique IDs (as hex) of batch from my bench:
01. 34 57 36 31 38 39 15 0E 00 02 00
02. 34 57 36 31 38 39 15 0E 00 06 00
03. 34 57 36 31 38 39 15 0E 00 0A 00
04. 34 57 36 31 38 39 15 0E 00 0E 00
05. 34 57 36 31 38 39 15 0A 00 14 00
06. 34 57 36 31 38 39 15 0A 00 1C 00
07. 34 57 36 31 38 39 15 09 00 23 00
08. 34 57 36 31 38 39 15 0A 00 24 00
09. 34 57 36 31 38 39 0E 1D 00 1A 00
10. 34 57 36 31 38 39 15 0E 00 09 00
11. 34 57 33 31 35 39 04 10 00 20 00
12. 34 57 33 31 35 39 04 18 00 1C 00
13. 34 57 36 31 38 39 15 0E 00 0F 00
14. 34 57 36 31 38 39 15 0E 00 13 00
15. 34 57 36 31 38 39 15 0E 00 17 00
16. 34 57 36 31 38 39 15 0E 00 1F 00
17. 34 57 36 31 38 39 15 0A 00 25 00
It looks that they are unique but many bytes are repeated/constant. Good solution should generate values placed in whole range even if input values are close to each other :)
Edit2: Here are results for all solutions from your answers:
Test results:
OP: 1977, H1L: 14759, H1H: 13938, H2L: 7189, H2H: 36686, H3L: 14759, H3H: 13938, H4: 2652, PRS: 61086
OP: 3669, H1L: 13735, H1H: 12914, H2L: 8213, H2H: 37710, H3L: 13735, H3H: 12914, H4: 6748, PRS: 25852
OP: 5361, H1L: 16807, H1H: 15986, H2L: 5141, H2H: 34638, H3L: 16807, H3H: 15986, H4: 10844, PRS: 40974
OP: 7053, H1L: 15783, H1H: 14962, H2L: 6165, H2H: 35662, H3L: 15783, H3H: 14962, H4: 14940, PRS: 19836
OP: 7899, H1L: 18507, H1H: 25943, H2L: 3441, H2H: 24681, H3L: 18507, H3H: 25943, H4: 21076, PRS: 4898
OP: 11283, H1L: 20555, H1H: 27991, H2L: 1393, H2H: 22633, H3L: 20555, H3H: 27991, H4: 29268, PRS: 10065
OP: 13821, H1L: 391, H1H: 26260, H2L: 21557, H2H: 24364, H3L: 391, H3H: 26260, H4: 36434, PRS: 63904
OP: 14667, H1L: 30795, H1H: 38231, H2L: 23902, H2H: 12393, H3L: 30795, H3H: 38231, H4: 37460, PRS: 46300
OP: 15513, H1L: 23009, H1H: 40628, H2L: 31688, H2H: 9996, H3L: 23009, H3H: 40628, H4: 27066, PRS: 21678
OP: 21322, H1L: 17063, H1H: 16242, H2L: 4885, H2H: 34382, H3L: 17063, H3H: 16242, H4: 9820, PRS: 60787
OP: 22168, H1L: 31736, H1H: 54522, H2L: 22961, H2H: 61623, H3L: 31736, H3H: 54522, H4: 32801, PRS: 20737
OP: 23860, H1L: 3760, H1H: 10032, H2L: 18188, H2H: 40592, H3L: 3760, H3H: 10032, H4: 28721, PRS: 50696
OP: 23860, H1L: 15527, H1H: 14706, H2L: 6421, H2H: 35918, H3L: 15527, H3H: 14706, H4: 15964, PRS: 28319
OP: 25552, H1L: 10407, H1H: 9586, H2L: 11541, H2H: 41038, H3L: 10407, H3H: 9586, H4: 20060, PRS: 60097
OP: 27244, H1L: 9383, H1H: 8562, H2L: 12565, H2H: 42062, H3L: 9383, H3H: 8562, H4: 24156, PRS: 5512
OP: 30628, H1L: 11431, H1H: 10610, H2L: 10517, H2H: 40014, H3L: 11431, H3H: 10610, H4: 32348, PRS: 55107
OP: 31474, H1L: 30539, H1H: 37975, H2L: 24158, H2H: 12649, H3L: 30539, H3H: 37975, H4: 38484, PRS: 4379
OP: 20035, H1L: 0, H1H: 0, H2L: 21948, H2H: 50624, H3L: 0, H3H: 0, H4: 0, PRS: 26124
OP is my original method which is poor and generates non-unique numbers for UIDs that were listed. H1L and H1H are simplified solutions presented by chux. H2L, H2H, H3L, H3H are my modifications (adding ~ to lower or upper part) to see if it produces better results. H4 is solution presented by alain. PRS is Pearson returning uint16_t suggested by mattinbits.
And the winner is... PRS! :) All your suggestions generate unique numbers from listed UIDs so they are correct but Pearson hashing offers best variance of results (checked in Excel ;) ). Thank you for your help!
What you're trying to do is effectively find a hash for your ids where the hash output is smaller than the input, so there will always be a risk of collisions, ie two device ids producing the same short id. Nevertheless, you'll have better luck using a proper hashing function than your sum approach. Just look for a simple 8 or 16 bit hash function and use that. E.g. https://en.m.wikipedia.org/wiki/Pearson_hashing