## 18.2M message-id dataset supplied by Joe Greco

I would like to thank everyone who offered their history files and/or message-id logs to run this test. I wound up using most of them for smaller runs during my construction of the CRC test program, and used an 18.2 million message-id data set supplied by Joe Greco for the final test runs shown below.

Using the program I posted earlier with one minor bug in the placement of ++total corrected, I ran the 18.2 million message-id data set with CRC's ranging from 16 to 64 bits. The number of collisions are shown below. The program is included at the bottom.

The lower numbered CRC's tended on collision rates nearing 100% after a certain number of samples, which is as expected. Once the test got beyond the noise floor, each additional bit of CRC cut the number of collisions down by approximately half. No collisions occured with the 18.2 million message-id's dataset once we got beyond CRC48, but one can extrapolate a collision rate of one message-id per 2.3 Trillion message-id's with a CRC64 from empirical data. The theoretical collision rate for CRC64 and 18.2 million mesage-id's is one collision every 2 trillion message-id's so we have good correspondance to theory.

I should have used a real CRC long ago rather then try to do something fancy with prime numbers. The 1.14 diablo release is going to use the CRC64 algorithm included at the end (well, actually CRC63 as I want to reserve one bit for future use). Besides, it's a good deal faster then the old prime-mod algorithm anyway as it only requires shift and xor ops to implement.

```			-Matt (dillon@backplane.com)
```

Summary, 18.2 million sample test dataset, number of collisions.

```
output.16 Count 18134464/18200000
output.17 Count 18068928/18200000
output.18 Count 17937856/18200000
output.19 Count 17675712/18200000
output.20 Count 17151424/18200000
output.21 Count 16103198/18200000
output.22 Count 14061250/18200000
output.23 Count 10770169/18200000
output.24 Count 7092360/18200000
output.25 Count 4153742/18200000
output.26 Count 2259269/18200000
output.27 Count 1179721/18200000
output.28 Count 603421/18200000
output.29 Count 305089/18200000
output.30 Count 153722/18200000
output.31 Count 77254/18200000
output.32 Count 38638/18200000
output.33 Count 19232/18200000
output.34 Count 9652/18200000
output.35 Count 4914/18200000
output.36 Count 2343/18200000
output.37 Count 1204/18200000
output.38 Count 637/18200000
output.39 Count 302/18200000
output.40 Count 152/18200000
output.41 Count 75/18200000
output.42 Count 52/18200000
output.43 Count 21/18200000
output.44 Count 13/18200000
output.45 Count 7/18200000
output.46 Count 1/18200000		(below noise floor)
output.47 Count 1/18200000		(below noise floor)
output.48 Count 1/18200000		(below noise floor)
output.49 Count 0/18200000		(below noise floor)
output.50 Count 0/18200000		(... all remaining entries below noise
output.51 Count 0/18200000		floor)
output.52 Count 0/18200000
output.53 Count 0/18200000
output.54 Count 0/18200000
output.55 Count 0/18200000
output.56 Count 0/18200000
output.57 Count 0/18200000
output.58 Count 0/18200000
output.59 Count 0/18200000
output.60 Count 0/18200000
output.61 Count 0/18200000
output.62 Count 0/18200000
output.63 Count 0/18200000
output.64 Count 0/18200000
```

Raw data, collisions for 18.2 million sample data set in increments of 100,000 samples for CRC16 through CRC64. Note that near the end, CRC16 through CRC20 approach a 100% collision rate. No collisions occured with the test dataset beyond CRC-48.

```
SAMPLES     CRC16    CRC17    CRC18    CRC19    CRC20    CRC21    CRC22
0.1M     48694    29762    17032     9070     4519     2274     1212
0.2M    137655    97436    60243    34119    17834     9211     4809
0.3M    235174   182198   121457    71883    39173    20303    10626
0.4M    334630   275232   194897   120208    67433    35624    18672
0.5M    434497   371788   277068   177992   102379    55094    28973
0.6M    534472   470260   364505   242833   143019    78184    41394
0.7M    634464   569530   456066   314036   189198   105006    55646
0.8M    734464   669213   550297   389973   240256   135019    72156
0.9M    834464   769050   646412   470339   295794   168415    91007
1.0M    934464   868987   743717   554420   356011   205050   111280
1.1M   1034464   968955   841834   640870   419364   244383   133311
1.2M   1134464  1068940   940621   729741   486134   286809   157443
...
16.3M  16234464 16168928 16037856 15775712 15251424 14203708 12192725
16.4M  16334464 16268928 16137856 15875712 15351424 14303666 12290669
16.5M  16434464 16368928 16237856 15975712 15451424 14403623 12388681
16.6M  16534464 16468928 16337856 16075712 15551424 14503585 12486733
16.7M  16634464 16568928 16437856 16175712 15651424 14603553 12584808
16.8M  16734464 16668928 16537856 16275712 15751424 14703524 12682912
16.9M  16834464 16768928 16637856 16375712 15851424 14803488 12781127
17.0M  16934464 16868928 16737856 16475712 15951424 14903456 12879337
17.1M  17034464 16968928 16837856 16575712 16051424 15003425 12977634
17.2M  17134464 17068928 16937856 16675712 16151424 15103396 13076030
17.3M  17234464 17168928 17037856 16775712 16251424 15203379 13174358
17.4M  17334464 17268928 17137856 16875712 16351424 15303355 13272762
17.5M  17434464 17368928 17237856 16975712 16451424 15403335 13371202
17.6M  17534464 17468928 17337856 17075712 16551424 15503319 13469702
17.7M  17634464 17568928 17437856 17175712 16651424 15603292 13568257
17.8M  17734464 17668928 17537856 17275712 16751424 15703269 13666849
17.9M  17834464 17768928 17637856 17375712 16851424 15803253 13765429
18.0M  17934464 17868928 17737856 17475712 16951424 15903234 13863977
18.1M  18034464 17968928 17837856 17575712 17051424 16003219 13962602
18.2M  18134464 18068928 17937856 17675712 17151424 16103198 14061250

SAMPLES     CRC23    CRC24    CRC25    CRC26    CRC27    CRC28    CRC29
0.1M       598      306      137       70       33       32        6
0.2M      2335     1234      566      286      148       80       36
0.3M      5306     2735     1297      660      338      185       76
0.4M      9430     4829     2366     1184      593      317      136
0.5M     14681     7449     3695     1874      921      480      212
0.6M     21107    10766     5245     2713     1329      693      298
0.7M     28501    14579     7107     3685     1816      904      418
0.8M     37024    18949     9289     4775     2368     1200      552
0.9M     46627    24062    11747     6030     2999     1535      726
1.0M     57487    29702    14566     7434     3696     1883      900
1.1M     69275    35841    17618     8982     4420     2278     1085
1.2M     82141    42418    20918    10651     5242     2735     1276
...
16.3M   9114163  5872118  3390118  1829751   951696   485017   244776
16.4M   9200121  5934331  3428694  1851395   963180   490947   247822
16.5M   9286007  5996612  3467221  1872875   974620   496944   250882
16.6M   9372012  6059317  3506292  1894849   986234   502734   253973
16.7M   9458202  6122215  3545563  1917044   997824   508770   257098
16.8M   9544827  6185514  3585185  1939007  1009459   514758   260095
16.9M   9631424  6248792  3624656  1961210  1021186   520766   263145
17.0M   9717886  6312228  3664147  1983486  1033057   526828   266255
17.1M   9804653  6376231  3704077  2005842  1045006   533034   269413
17.2M   9891451  6440246  3744092  2028282  1056942   539151   272609
17.3M   9978615  6504484  3784090  2050970  1068949   545393   275829
17.4M  10066095  6568897  3824279  2073908  1080972   551746   279052
17.5M  10153638  6633419  3864988  2096617  1093007   558241   282168
17.6M  10241316  6698409  3905771  2119439  1105345   564643   285307
17.7M  10329060  6763735  3946805  2142721  1117568   571041   288589
17.8M  10416956  6829189  3987814  2165682  1129935   577460   291925
17.9M  10505125  6894783  4028719  2188977  1142181   583945   295143
18.0M  10593200  6960451  4070229  2212196  1154546   590442   298462
18.1M  10681658  7026271  4111702  2235718  1167082   596914   301830
18.2M  10770169  7092360  4153742  2259269  1179721   603421   305089

SAMPLES     CRC30    CRC31    CRC32    CRC33    CRC34    CRC35    CRC36
0.1M         5        1        3        0        0        0        0
0.2M        14       12        5        3        0        1        0
0.3M        40       24        7        8        6        3        1
0.4M        73       37       20       10        9        3        3
0.5M       110       65       29       16       12        4        4
0.6M       161       86       44       22       14        6        5
0.7M       219      121       66       33       14        8        5
0.8M       292      151       84       41       19        9        5
0.9M       370      195      104       53       26       11        5
1.0M       455      238      124       68       29       12        6
1.1M       557      281      149       78       32       15        8
1.2M       669      350      178       88       38       17       12
...
16.3M    123428    61928    31046    15393     7752     3939     1891
16.4M    124961    62691    31444    15576     7839     3991     1920
16.5M    126444    63473    31815    15776     7948     4043     1938
16.6M    127945    64235    32207    16004     8046     4097     1962
16.7M    129517    64984    32588    16230     8148     4144     1984
16.8M    131019    65739    32974    16438     8244     4194     2010
16.9M    132553    66529    33358    16632     8351     4248     2036
17.0M    134113    67326    33756    16835     8444     4290     2060
17.1M    135661    68138    34135    17032     8553     4344     2086
17.2M    137279    68952    34510    17234     8665     4387     2114
17.3M    138840    69781    34891    17448     8765     4436     2136
17.4M    140575    70594    35276    17629     8858     4483     2161
17.5M    142290    71396    35726    17807     8955     4521     2189
17.6M    143864    72236    36174    17994     9072     4561     2214
17.7M    145485    73014    36600    18204     9167     4637     2241
17.8M    147093    73825    36971    18396     9261     4682     2260
17.9M    148720    74638    37388    18586     9357     4735     2289
18.0M    150358    75498    37804    18802     9452     4801     2305
18.1M    152014    76347    38195    19014     9551     4861     2324
18.2M    153722    77254    38638    19232     9652     4914     2343

SAMPLES     CRC37    CRC38    CRC39    CRC40    CRC41    CRC42    CRC43
0.1M         0        0        0        0        0        0        0
0.2M         0        0        0        0        0        0        0
0.3M         1        0        0        0        0        0        0
0.4M         1        0        0        0        0        0        0
0.5M         2        0        0        0        0        0        0
0.6M         2        0        0        0        0        0        0
0.7M         2        0        0        0        0        0        0
0.8M         3        0        1        0        0        0        0
0.9M         4        0        1        0        0        0        0
1.0M         6        0        1        0        0        0        0
1.1M         6        0        1        0        0        0        0
1.2M         6        1        1        0        0        0        0
...
16.3M       975      511      245      118       63       35       16
16.4M       989      515      247      122       65       36       17
16.5M       998      521      248      122       65       37       17
16.6M      1012      531      249      123       65       38       17
16.7M      1020      533      250      123       66       40       17
16.8M      1033      539      253      128       66       40       17
16.9M      1043      546      254      129       67       41       17
17.0M      1054      550      257      129       69       42       17
17.1M      1067      555      260      130       70       42       18
17.2M      1083      561      263      133       70       44       19
17.3M      1090      573      266      135       70       46       20
17.4M      1096      586      271      137       71       46       20
17.5M      1108      594      275      139       72       46       20
17.6M      1120      597      280      140       72       48       21
17.7M      1134      603      287      142       72       48       21
17.8M      1146      608      287      146       73       48       21
17.9M      1162      614      291      147       73       50       21
18.0M      1176      621      293      149       73       50       21
18.1M      1185      626      298      150       75       51       21
18.2M      1204      637      302      152       75       52       21

SAMPLES     CRC44    CRC45    CRC46    CRC47    CRC48    CRC49    CRC50
0.1M         0        0        0        0        0        0        0
0.2M         0        0        0        0        0        0        0
0.3M         0        0        0        0        0        0        0
0.4M         0        0        0        0        0        0        0
0.5M         0        0        0        0        0        0        0
0.6M         0        0        0        0        0        0        0
0.7M         0        0        0        0        0        0        0
0.8M         0        0        0        0        0        0        0
0.9M         0        0        0        0        0        0        0
1.0M         0        0        0        0        0        0        0
1.1M         0        0        0        0        0        0        0
1.2M         0        0        0        0        0        0        0
1.3M         0        0        0        0        0        0        0
1.4M         0        0        0        0        0        0        0
1.5M         0        0        0        0        0        0        0
1.6M         0        0        0        0        0        0        0
1.7M         0        0        0        0        0        0        0
1.8M         0        0        0        0        0        0        0
1.9M         0        0        0        0        0        0        0
2.0M         0        0        0        0        0        0        0
2.1M         0        0        0        0        0        0        0
2.2M         0        0        0        0        0        0        0
2.3M         0        0        0        0        0        0        0
2.4M         0        0        0        0        0        0        0
2.5M         0        0        0        0        0        0        0
2.6M         0        0        0        0        0        0        0
2.7M         0        0        0        0        0        0        0
2.8M         0        0        0        0        0        0        0
2.9M         0        0        0        0        0        0        0
3.0M         1        0        0        0        0        0        0
3.1M         1        0        0        0        0        0        0
3.2M         1        0        0        0        0        0        0
3.3M         1        0        0        0        0        0        0
3.4M         1        0        0        0        0        0        0
3.5M         1        0        0        0        0        0        0
3.6M         2        0        0        0        0        0        0
3.7M         3        0        0        0        0        0        0
3.8M         3        0        0        0        0        0        0
3.9M         3        0        0        0        0        0        0
4.0M         3        0        0        0        0        0        0
4.1M         3        0        0        0        0        0        0
4.2M         3        0        0        0        0        0        0
4.3M         3        0        0        0        0        0        0
4.4M         3        0        0        0        0        0        0
4.5M         3        0        0        0        0        0        0
4.6M         3        0        0        0        0        0        0
4.7M         3        0        0        0        0        0        0
4.8M         3        0        0        0        0        0        0
4.9M         3        0        0        0        0        0        0
5.0M         4        0        0        0        0        0        0
5.1M         4        0        0        0        0        0        0
5.2M         4        0        0        0        0        0        0
5.3M         4        0        0        0        0        0        0
5.4M         4        0        0        0        0        0        0
5.5M         4        0        0        0        0        0        0
5.6M         5        0        0        0        0        0        0
5.7M         5        0        0        0        0        0        0
5.8M         5        0        0        0        0        0        0
5.9M         5        0        0        0        0        0        0
6.0M         5        0        0        0        0        0        0
6.1M         5        0        0        0        0        0        0
6.2M         5        0        0        0        0        0        0
6.3M         5        0        0        0        0        0        0
6.4M         5        0        0        0        0        0        0
6.5M         5        0        0        0        0        0        0
6.6M         5        0        0        0        0        0        0
6.7M         5        0        0        0        0        0        0
6.8M         5        0        0        0        0        0        0
6.9M         5        0        0        0        0        0        0
7.0M         5        0        0        0        0        0        0
7.1M         5        0        0        0        0        0        0
7.2M         5        0        0        0        0        0        0
7.3M         5        0        0        0        0        0        0
7.4M         5        0        0        0        0        0        0
7.5M         5        0        0        0        0        0        0
7.6M         5        0        0        0        0        0        0
7.7M         5        0        0        0        0        0        0
7.8M         5        0        0        0        0        0        0
7.9M         5        1        0        0        0        0        0
8.0M         5        1        0        0        0        0        0
8.1M         5        1        0        0        0        0        0
8.2M         5        1        0        0        0        0        0
8.3M         5        1        0        0        0        0        0
8.4M         5        1        0        0        0        0        0
8.5M         5        1        0        0        0        0        0
8.6M         5        1        0        0        0        0        0
8.7M         5        1        0        0        0        0        0
8.8M         5        1        0        0        0        0        0
8.9M         5        2        0        0        0        0        0
9.0M         5        2        0        0        0        0        0
9.1M         5        2        0        0        0        0        0
9.2M         5        2        0        0        0        0        0
9.3M         5        2        0        0        0        0        0
9.4M         5        2        0        0        0        0        0
9.5M         5        2        1        0        0        0        0
9.6M         5        2        1        0        0        0        0
9.7M         5        2        1        0        0        0        0
9.8M         5        2        1        0        0        0        0
9.9M         5        2        1        0        0        0        0
10.0M         5        2        1        0        0        0        0
10.1M         6        2        1        0        0        0        0
10.2M         6        2        1        0        0        0        0
10.3M         6        2        1        0        0        0        0
10.4M         6        2        1        0        0        0        0
10.5M         6        2        1        0        0        0        0
10.6M         6        2        1        0        0        0        0
10.7M         6        2        1        0        0        0        0
10.8M         6        2        1        0        0        0        0
10.9M         6        2        1        0        0        0        0
11.0M         6        2        1        0        0        0        0
11.1M         6        2        1        0        0        0        0
11.2M         6        2        1        0        0        0        0
11.3M         6        2        1        0        0        0        0
11.4M         6        2        1        0        0        0        0
11.5M         6        2        1        0        0        0        0
11.6M         6        2        1        0        0        0        0
11.7M         6        2        1        0        0        0        0
11.8M         6        2        1        0        0        0        0
11.9M         6        2        1        0        0        0        0
12.0M         6        2        1        0        0        0        0
12.1M         6        2        1        0        0        0        0
12.2M         6        2        1        0        0        0        0
12.3M         6        2        1        0        0        0        0
12.4M         6        3        1        0        0        0        0
12.5M         6        4        1        0        0        0        0
12.6M         7        4        1        0        0        0        0
12.7M         7        4        1        0        0        0        0
12.8M         7        4        1        0        0        0        0
12.9M         7        4        1        0        0        0        0
13.0M         7        4        1        0        0        0        0
13.1M         7        4        1        0        0        0        0
13.2M         7        4        1        0        0        0        0
13.3M         7        4        1        0        0        0        0
13.4M         7        4        1        0        0        0        0
13.5M         7        4        1        0        0        0        0
13.6M         7        4        1        0        0        0        0
13.7M         7        4        1        0        0        0        0
13.8M         7        4        1        0        0        0        0
13.9M         7        4        1        0        0        0        0
14.0M         7        4        1        0        0        0        0
14.1M         7        4        1        0        0        0        0
14.2M         7        4        1        0        0        0        0
14.3M         7        4        1        0        0        0        0
14.4M         7        4        1        0        0        0        0
14.5M         7        4        1        0        0        0        0
14.6M         7        4        1        0        0        0        0
14.7M         7        4        1        0        0        0        0
14.8M         7        4        1        0        0        0        0
14.9M         7        4        1        0        0        0        0
15.0M         7        4        1        0        0        0        0
15.1M         8        4        1        0        0        0        0
15.2M         8        4        1        0        0        0        0
15.3M         8        4        1        0        0        0        0
15.4M         8        4        1        0        0        0        0
15.5M         9        4        1        1        0        0        0
15.6M         9        4        1        1        0        0        0
15.7M        11        4        1        1        0        0        0
15.8M        11        4        1        1        0        0        0
15.9M        11        4        1        1        0        0        0
16.0M        11        4        1        1        0        0        0
16.1M        11        4        1        1        0        0        0
16.2M        12        5        1        1        0        0        0
16.3M        12        5        1        1        0        0        0
16.4M        12        5        1        1        0        0        0
16.5M        12        5        1        1        0        0        0
16.6M        12        5        1        1        0        0        0
16.7M        13        5        1        1        0        0        0
16.8M        13        5        1        1        0        0        0
16.9M        13        5        1        1        0        0        0
17.0M        13        5        1        1        0        0        0
17.1M        13        5        1        1        0        0        0
17.2M        13        5        1        1        0        0        0
17.3M        13        6        1        1        0        0        0
17.4M        13        6        1        1        0        0        0
17.5M        13        6        1        1        0        0        0
17.6M        13        6        1        1        0        0        0
17.7M        13        6        1        1        0        0        0
17.8M        13        6        1        1        0        0        0
17.9M        13        6        1        1        0        0        0
18.0M        13        6        1        1        0        0        0
18.1M        13        6        1        1        0        0        0
18.2M        13        7        1        1        1        0        0

SAMPLES     CRC51    CRC52    CRC53    CRC54    CRC55    CRC56    CRC57
(all zero)

SAMPLES     CRC58    CRC59    CRC60    CRC61    CRC62    CRC63    CRC64
(all zero)
```