1use core::ops::{AddAssign, BitAnd, BitOrAssign, Shl, SubAssign};
2
3use num_traits::{ops::wrapping::WrappingSub, FromPrimitive, Num};
4
5#[inline]
7pub fn simhash32(data: &[u32]) -> u32 {
8 simhash::<u32, 32>(data)
9}
10
11#[inline]
20pub fn simhash<T, const N: usize>(data: &[T]) -> T
21where
22 T: Num
23 + FromPrimitive
24 + WrappingSub
25 + AddAssign
26 + SubAssign
27 + BitAnd<Output = T>
28 + BitOrAssign
29 + Shl<Output = T>
30 + Copy,
31{
32 assert_eq!(
33 std::mem::size_of::<T>() * 8,
34 N,
35 "size of T must be equal to {} bits",
36 N
37 );
38
39 let mut buf = [0i64; N];
40
41 for i in 0..data.len() {
42 for j in 0..N {
43 let s = T::one() << T::from_usize(j).unwrap();
44 if (data[i] & s) != T::zero() {
45 buf[j] += 1;
46 } else {
47 buf[j] -= 1;
48 }
49 }
50 }
51
52 let mut hash = T::zero();
53 for i in 0..N {
54 if buf[i] > 0 {
55 hash |= T::one() << T::from_usize(i).unwrap();
56 }
57 }
58
59 hash
60}
61
62#[cfg(test)]
63mod test {
64 use super::*;
65
66 #[test]
67 fn test_single() {
68 const DATA: &[u32] = &[3740390231];
69 assert_eq!(simhash32(DATA), 3740390231);
70 }
71
72 #[test]
73 fn test_small() {
74 const DATA: &[u32] = &[
75 3740390231, 3739276119, 3730871573, 3743460629, 3743525173, 3744594229, 3727948087,
76 1584920886, 1593302326, 1593295926, 1584907318,
77 ];
78 assert_eq!(simhash32(DATA), 3732003127);
79 }
80
81 #[test]
82 fn test_normal() {
83 const DATA: &[i32] = &[
84 1518991452,
85 -1511651436,
86 -1511579771,
87 -1528353403,
88 -1528469033,
89 -1528501962,
90 -1511724778,
91 -1511543546,
92 -1477991162,
93 -1478183674,
94 -1502310138,
95 -1506504441,
96 -1506482827,
97 -1489541659,
98 -1489619548,
99 -1485437532,
100 -1510078540,
101 -1511127164,
102 -1528353403,
103 -1527829033,
104 -1528469130,
105 -1511720650,
106 -1511741178,
107 -1478185722,
108 -1477139194,
109 -1502300922,
110 -1506504441,
111 -1506499307,
112 -1489640091,
113 -1489607196,
114 -1485437020,
115 -1518991452,
116 -1511061628,
117 -1527826556,
118 -1527828587,
119 -1526896137,
120 -1527907978,
121 -1511720682,
122 -1511741178,
123 -1478185722,
124 -1478187770,
125 -1502310138,
126 -1506504441,
127 -1506482891,
128 -1489541659,
129 -1489619548,
130 -1485437020,
131 -1510078540,
132 -1511061627,
133 -1528352891,
134 -1531105897,
135 -1531090442,
136 -1532692202,
137 -1511741178,
138 -1511740154,
139 -1478187770,
140 -1485523706,
141 -1506504441,
142 -1506482921,
143 -1489640091,
144 -1489607195,
145 -1485437020,
146 -1518991451,
147 -1511061627,
148 -1527824507,
149 -1527829113,
150 -1526896137,
151 -1527383690,
152 -1511737082,
153 -1511740154,
154 -1478187770,
155 -1493912314,
156 -1506504441,
157 -1506495225,
158 -1506417307,
159 -1489607195,
160 -1489619036,
161 -1518991451,
162 -1511127147,
163 -1527834747,
164 -1527828603,
165 -1532155433,
166 -1532106378,
167 -1515914986,
168 -1515935482,
169 -1478185722,
170 -1478187770,
171 -1502301946,
172 -1506508537,
173 -1506482891,
174 -1489541659,
175 -1489623644,
176 -1518991452,
177 -1518991451,
178 -1528363131,
179 -1528352891,
180 -1527435881,
181 -1527486089,
182 -1511659210,
183 -1511675642,
184 -1478185722,
185 -1477139194,
186 -1502301946,
187 -1506504441,
188 -1506483939,
189 -1489639955,
190 -1489605148,
191 -1518985308,
192 -1518989404,
193 -1510535532,
194 -1527302523,
195 -1527437691,
196 -1527419177,
197 -1510609130,
198 -1510675178,
199 -1510691818,
200 -1481262058,
201 -1477143546,
202 -1502309370,
203 -1508577209,
204 -434870827,
205 -434756188,
206 -415879260,
207 -445247580,
208 -437907532,
209 -454621308,
210 -459200571,
211 -459247673,
212 -459215018,
213 -454956282,
214 -168580858,
215 -135021306,
216 -135166714,
217 -428829674,
218 -432999337,
219 -164600619,
220 -147771996,
221 -183358044,
222 -177070172,
223 -168687968,
224 -168622448,
225 -169789756,
226 -174053819,
227 -241111289,
228 -207574778,
229 -207378170,
230 -136135418,
231 -136149758,
232 -144670458,
233 -147803385,
234 -181341379,
235 -466589844,
236 -466472980,
237 -462280212,
238 -453899804,
239 -441249884,
240 -441448828,
241 -405790003,
242 -405773617,
243 -212797746,
244 -210506258,
245 -504190746,
246 -508315418,
247 -508457770,
248 -235866938,
249 1932534159,
250 1930441613,
251 1930568684,
252 1915889644,
253 1936856420,
254 1944259940,
255 1906313541,
256 1906339141,
257 1906371911,
258 1889648454,
259 1894956870,
260 1911729990,
261 1936891142,
262 1936885046,
263 1935705190,
264 1935696999,
265 1935680743,
266 1902128629,
267 1886531045,
268 1886533092,
269 1894909920,
270 1894777456,
271 1894838788,
272 1910546948,
273 1910552069,
274 1927327253,
275 -220026347,
276 -220026091,
277 -220029161,
278 -160267513,
279 -143604977,
280 -181374401,
281 -198158807,
282 -197973207,
283 -194893779,
284 -185460627,
285 -185579027,
286 -168802355,
287 -179281267,
288 2001760911,
289 1980842638,
290 1930589094,
291 1934812326,
292 1911745702,
293 -172897118,
294 1974498438,
295 1978687623,
296 1399857613,
297 1378957149,
298 1383218988,
299 1382169892,
300 1407388961,
301 1373635889,
302 1352671493,
303 1352725255,
304 1356976982,
305 1424160326,
306 1416802119,
307 1429389059,
308 1395821841,
309 1377864993,
310 1382081892,
311 1390470500,
312 1408268276,
313 1374830549,
314 1355952117,
315 1347567523,
316 1364264418,
317 1364197858,
318 1364222290,
319 1408299330,
320 1390540098,
321 1390586946,
322 1407364163,
323 1398967619,
324 1398966083,
325 1366327891,
326 1362141814,
327 1345385062,
328 1882324582,
329 1886579046,
330 1893886055,
331 -253671323,
332 1911604565,
333 1903223300,
334 1932648964,
335 1932612101,
336 1932752501,
337 1903356389,
338 1911744743,
339 1907574951,
340 1940999303,
341 1945118087,
342 1397760903,
343 1381040783,
344 1381118975,
345 1383212135,
346 1399002147,
347 1373637667,
348 1373662227,
349 1356915719,
350 1352711495,
351 1358085959,
352 1374863175,
353 1397931331,
354 1379044675,
355 1379110177,
356 1382085985,
357 1407247719,
358 1373660535,
359 1358067031,
360 1358069223,
361 1347556833,
362 1347438433,
363 1364214641,
364 1366352385,
365 1399894529,
366 1391504977,
367 1391700545,
368 1391635395,
369 1391640515,
370 1383237443,
371 1467056711,
372 1362162199,
373 -265230801,
374 -265261521,
375 -261986001,
376 -186484691,
377 -186529755,
378 -185545355,
379 -168758715,
380 -212802875,
381 -233745785,
382 -216894826,
383 -212703834,
384 -237868894,
385 -242071390,
386 -256685950,
387 1353786498,
388 1374692806,
389 1399859142,
390 1383282022,
391 -697160666,
392 -966649822,
393 -941619166,
394 -941615086,
395 -975116030,
396 -710824190,
397 -1800225022,
398 -1648969982,
399 -1651067646,
400 -1650555343,
401 -1615296992,
402 -1619484128,
403 -1641487776,
404 -567803168,
405 -567737696,
406 -30797152,
407 -163958620,
408 1999438061,
409 1973814334,
410 1889668106,
411 815933450,
412 279062538,
413 279063562,
414 14740507,
415 299955499,
416 291799915,
417 828670569,
418 828691033,
419 807727737,
420 874897979,
421 879190827,
422 342258986,
423 484924714,
424 484825466,
425 484948298,
426 1567079370,
427 1601018826,
428 2145951706,
429 -5664262,
430 -5663814,
431 -22310216,
432 -559238472,
433 -559177048,
434 -567745876,
435 -566746460,
436 -566684960,
437 -567659676,
438 1982738468,
439 2003238959,
440 1973816334,
441 815933450,
442 279062538,
443 279066634,
444 11537482,
445 15785339,
446 7656939,
447 291816427,
448 291799979,
449 828699579,
450 820376507,
451 350614457,
452 342356923,
453 73848250,
454 207871466,
455 207731578,
456 1298381594,
457 1566817034,
458 1609018122,
459 -558911734,
460 -22044406,
461 -559238630,
462 -559250888,
463 -559185304,
464 -555179288,
465 -566697236,
466 -566742300,
467 -567602464,
468 -567660060,
469 -30469916,
470 2003240173,
471 1973816394,
472 884096010,
473 347219978,
474 351419402,
475 342899738,
476 351282218,
477 351285354,
478 882901098,
479 887357658,
480 887361754,
481 878989787,
482 879063387,
483 342356283,
484 342349178,
485 350723578,
486 367507866,
487 350726538,
488 1978121098,
489 1978505866,
490 1978506906,
491 -139619686,
492 -156265767,
493 -156331400,
494 -156323272,
495 -697376216,
496 -701685140,
497 -700702108,
498 -700636320,
499 -164298524,
500 2004091111,
501 1906508926,
502 1889668110,
503 279066634,
504 279062538,
505 279063562,
506 14738491,
507 283157803,
508 291537259,
509 828408683,
510 828670715,
511 828748409,
512 811704953,
513 811837049,
514 811771385,
515 811834792,
516 887197096,
517 887201688,
518 896646792,
519 829660808,
520 825472648,
521 825484952,
522 829612472,
523 829616552,
524 837996968,
525 838001576,
526 835723949,
527 324018879,
528 307241727,
529 309469543,
530 309470247,
531 316677155,
532 333449251,
533 333473795,
534 295762945,
535 10747713,
536 15924929,
537 24280769,
538 17989440,
539 53628240,
540 52446560,
541 65037665,
542 60845411,
543 329317846,
544 27459014,
545 15924418,
546 1232098,
547 1082723,
548 17860387,
549 288403969,
550 1399895553,
551 1390521873,
552 1390586641,
553 1390587185,
554 1382200625,
555 1383236113,
556 1393672709,
557 1360065031,
558 1880159807,
559 1882319406,
560 1886578734,
561 1962072111,
562 1957742695,
563 1955646935,
564 1976623821,
565 1997566671,
566 1913717391,
567 1930568366,
568 1930570918,
569 1909598374,
570 1907493026,
571 1907559554,
572 1907434630,
573 298852742,
574 324022983,
575 307392885,
576 309486629,
577 333708321,
578 299944993,
579 299957265,
580 278983937,
581 279051847,
582 15924935,
583 24276679,
584 51544003,
585 53611859,
586 321998049,
587 325084385,
588 329278693,
589 329315829,
590 280096197,
591 11726293,
592 5436915,
593 1234787,
594 17875747,
595 288403987,
596 1399886339,
597 1390456595,
598 1390586131,
599 1390585873,
600 1382193233,
601 1383237440,
602 1378910720,
603 1362141717,
604 1882255933,
605 1882258989,
606 1886578991,
607 1894967335,
608 1890699367,
609 1957743719,
610 1959818055,
611 1901093583,
612 1930494670,
613 1930561246,
614 1934764198,
615 1945249958,
616 1941129382,
617 1907427463,
618 1911563655,
619 1934631559,
620 303043214,
621 303178479,
622 309469223,
623 325202979,
624 299895843,
625 283130899,
626 278948867,
627 279051525,
628 10681925,
629 32669377,
630 38960961,
631 101866817,
632 36851057,
633 39900257,
634 312517857,
635 396404198,
636 1957799366,
637 1957868998,
638 1414700390,
639 1410436390,
640 1410369830,
641 -718230778,
642 -147801338,
643 -164562170,
644 -165482730,
645 -151591642,
646 -155258841,
647 -557924320,
648 -558349968,
649 -558341184,
650 -566726080,
651 -700956144,
652 1463423520,
653 1463690016,
654 1429610532,
655 1442267191,
656 347210766,
657 351411470,
658 338824970,
659 338890251,
660 338959737,
661 880026729,
662 900998377,
663 632565993,
664 632565977,
665 614731849,
666 878985545,
667 879149881,
668 887535419,
669 1017556778,
670 497336186,
671 497335130,
672 1608825802,
673 1601018762,
674 1596825482,
675 1584103834,
676 -559246918,
677 -559246934,
678 -693456472,
679 -559176792,
680 -555162968,
681 -567745876,
682 -683904340,
683 -717327652,
684 1966482040,
685 1966224680,
686 1978747945,
687 1978682394,
688 1978923018,
689 1965287434,
690 1965091850,
691 891415627,
692 895730937,
693 636731817,
694 565461481,
695 552874969,
696 540029449,
697 540029465,
698 606216747,
699 1692542763,
700 1956785450,
701 1973442874,
702 1974786314,
703 2012518666,
704 -30110902,
705 -30634022,
706 -26242566,
707 -22376022,
708 -5598293,
709 -22367576,
710 -22306136,
711 -25632084,
712 -1103568156,
713 -1103498528,
714 -163679520,
715 -164728736,
716 -161201952,
717 -140459785,
718 -173882170,
719 1977772230,
720 1948412302,
721 1949514127,
722 1966091695,
723 1970283695,
724 1978663147,
725 1974468859,
726 1973428299,
727 888152075,
728 888152331,
729 888301370,
730 1957854762,
731 1957874218,
732 1420872218,
733 1441839626,
734 -680224246,
735 -165376246,
736 -30570726,
737 -26561734,
738 -22367894,
739 -1096121368,
740 -1096117528,
741 -1095195992,
742 -1082596692,
743 -1086823700,
744 -1086651668,
745 -12700948,
746 -147446548,
747 -176944024,
748 -441447365,
749 1706167306,
750 1978805258,
751 1901210698,
752 1896885466,
753 823141546,
754 837812394,
755 833880234,
756 832843930,
757 820256906,
758 811872714,
759 812057370,
760 811992874,
761 283520298,
762 346433834,
763 1420060954,
764 1420077322,
765 1424263434,
766 1441566282,
767 -38959398,
768 -5668262,
769 -22375877,
770 -22375880,
771 -22367704,
772 -26631576,
773 -30907676,
774 -30928160,
775 -30866784,
776 -163901020,
777 1983709421,
778 2011497582,
779 1906707466,
780 816199690,
781 816195594,
782 279063562,
783 278930442,
784 14738475,
785 283148649,
786 291537897,
787 895779561,
788 879030905,
789 879096379,
790 879190555,
791 342254874,
792 476476458,
793 484924458,
794 216520730,
795 1575467082,
796 1567078730,
797 1609408474,
798 -5728294,
799 -5663846,
800 -22310215,
801 -22310216,
802 -559238488,
803 -554065240,
804 -566730068,
805 -566746464,
806 -566619424,
807 -567660508,
808 1982795813,
809 2011628590,
810 1973554190,
811 279062538,
812 279062538,
813 77732874,
814 82838539,
815 82867563,
816 74498409,
817 358924649,
818 367301097,
819 887403513,
820 887469019,
821 887600091,
822 342276058,
823 476485594,
824 476552698,
825 493336922,
826 1567078746,
827 1596438986,
828 2120596954,
829 -17979942,
830 -22301702,
831 -22375687,
832 -22375688,
833 -22367576,
834 -1092050200,
835 -1087839512,
836 -1087835416,
837 -1121316184,
838 -1523698264,
839 -450618135,
840 -436991894,
841 -441382822,
842 1708268618,
843 1699884234,
844 1695687882,
845 1997743322,
846 930152618,
847 670105770,
848 665850043,
849 636498059,
850 628109515,
851 611324171,
852 877818427,
853 886205994,
854 884108074,
855 1957755706,
856 1973725450,
857 2011478282,
858 1998883146,
859 -13856806,
860 -26508390,
861 -22375430,
862 -22375815,
863 -22371736,
864 -559308184,
865 -555163028,
866 -567778716,
867 -29814176,
868 -29748640,
869 -29478812,
870 -143392667,
871 1978729534,
872 1957825550,
873 1962032142,
874 875703370,
875 875768907,
876 875834857,
877 905192681,
878 900989161,
879 632553977,
880 632558027,
881 610534155,
882 610583066,
883 610723626,
884 1021766954,
885 1017572650,
886 2108995866,
887 2142538058,
888 2138344394,
889 2117439114,
890 -29509990,
891 -25513030,
892 -21326918,
893 -4549720,
894 -4545880,
895 -21454168,
896 -25632092,
897 -29859088,
898 -163966240,
899 -163958172,
900 -147972060,
901 -144441305,
902 1973683262,
903 1906707470,
904 1889937418,
905 812001290,
906 807877706,
907 271859067,
908 905188587,
909 833880299,
910 832844011,
911 564408537,
912 820269129,
913 811979097,
914 887534459,
915 883340923,
916 884457082,
917 888446970,
918 888446938,
919 891591050,
920 1998953882,
921 1982315930,
922 1982247322,
923 1986433467,
924 1990628265,
925 1991701160,
926 1995858664,
927 1999905388,
928 1999905324,
929 -182050260,
930 1965175596,
931 1977812268,
932 1973421096,
933 1974469641,
934 1978807563,
935 1968316170,
936 890246922,
937 890250602,
938 894448874,
939 636486890,
940 615776442,
941 614731914,
942 618934474,
943 878989771,
944 879153945,
945 879142697,
946 887533355,
947 900054842,
948 1470413658,
949 1608825418,
950 1583651530,
951 2116914826,
952 -26507366,
953 -18181702,
954 -559246870,
955 -559238807,
956 -559242392,
957 -559357332,
958 -563551708,
959 -567746016,
960 -566312416,
961 -700517536,
962 -684269344,
963 2012664032,
964 1979106499,
965 1979108486,
966 1965476231,
967 1965542277,
968 1965391269,
969 1965319597,
970 1978671277,
971 1703948521,
972 1703948569,
973 609231113,
974 609231627,
975 609362730,
976 619851562,
977 1957828906,
978 1957693754,
979 1958005002,
980 1974769930,
981 2004126538,
982 2116849562,
983 -165050438,
984 -152399430,
985 -156593221,
986 -156585304,
987 -693460312,
988 -689380696,
989 -700947796,
990 -700964124,
991 -163704092,
992 -163700700,
993 -161214427,
994 2007237679,
995 1973816334,
996 1894131722,
997 812001290,
998 270994698,
999 270800235,
1000 812922091,
1001 821298347,
1002 816058539,
1003 564425883,
1004 551867787,
1005 618956683,
1006 619093691,
1007 1977788075,
1008 2012391082,
1009 2012260090,
1010 1987097434,
1011 -165637350,
1012 -433871046,
1013 -433936598,
1014 -433674950,
1015 -1486444753,
1016 -1514749396,
1017 -1246313940,
1018 -1245949380,
1019 -176397804,
1020 -180592108,
1021 -148037088,
1022 -147967455,
1023 -433848286,
1024 -404486942,
1025 -408664842,
1026 -442055546,
1027 1979120774,
1028 1966501262,
1029 1949727119,
1030 1949400493,
1031 1970300077,
1032 ];
1033
1034 let (_, converted, _) = unsafe { DATA.align_to::<u32>() };
1037 let hash = simhash32(converted);
1038 assert_eq!(1961926954, hash);
1039 }
1040}