]> git.zerfleddert.de Git - proxmark3-svn/blame - common/radixsort.c
FIX: lf hitag : Mea culpa, simulation should not have reader_field on. thanks to...
[proxmark3-svn] / common / radixsort.c
CommitLineData
089d061f 1#include "radixsort.h"
2
3uint64_t * radixSort(uint64_t * array, uint32_t size) {
4 rscounts_t counts;
5 memset(&counts, 0, 256 * 8 * sizeof(uint32_t));
6 uint64_t * cpy = (uint64_t *)malloc(size * sizeof(uint64_t));
7 uint32_t o8=0, o7=0, o6=0, o5=0, o4=0, o3=0, o2=0, o1=0;
8 uint32_t t8, t7, t6, t5, t4, t3, t2, t1;
9 uint32_t x;
10 // calculate counts
11 for(x = 0; x < size; ++x) {
12 t8 = array[x] & 0xff;
13 t7 = (array[x] >> 8) & 0xff;
14 t6 = (array[x] >> 16) & 0xff;
15 t5 = (array[x] >> 24) & 0xff;
16 t4 = (array[x] >> 32) & 0xff;
17 t3 = (array[x] >> 40) & 0xff;
18 t2 = (array[x] >> 48) & 0xff;
19 t1 = (array[x] >> 56) & 0xff;
20 counts.c8[t8]++;
21 counts.c7[t7]++;
22 counts.c6[t6]++;
23 counts.c5[t5]++;
24 counts.c4[t4]++;
25 counts.c3[t3]++;
26 counts.c2[t2]++;
27 counts.c1[t1]++;
28 }
29 // convert counts to offsets
30 for(x = 0; x < 256; ++x) {
31 t8 = o8 + counts.c8[x];
32 t7 = o7 + counts.c7[x];
33 t6 = o6 + counts.c6[x];
34 t5 = o5 + counts.c5[x];
35 t4 = o4 + counts.c4[x];
36 t3 = o3 + counts.c3[x];
37 t2 = o2 + counts.c2[x];
38 t1 = o1 + counts.c1[x];
39 counts.c8[x] = o8;
40 counts.c7[x] = o7;
41 counts.c6[x] = o6;
42 counts.c5[x] = o5;
43 counts.c4[x] = o4;
44 counts.c3[x] = o3;
45 counts.c2[x] = o2;
46 counts.c1[x] = o1;
47 o8 = t8;
48 o7 = t7;
49 o6 = t6;
50 o5 = t5;
51 o4 = t4;
52 o3 = t3;
53 o2 = t2;
54 o1 = t1;
55 }
56 // radix
57 for(x = 0; x < size; ++x) {
58 t8 = array[x] & 0xff;
59 cpy[counts.c8[t8]] = array[x];
60 counts.c8[t8]++;
61 }
62 for(x = 0; x < size; ++x) {
63 t7 = (cpy[x] >> 8) & 0xff;
64 array[counts.c7[t7]] = cpy[x];
65 counts.c7[t7]++;
66 }
67 for(x = 0; x < size; ++x) {
68 t6 = (array[x] >> 16) & 0xff;
69 cpy[counts.c6[t6]] = array[x];
70 counts.c6[t6]++;
71 }
72 for(x = 0; x < size; ++x) {
73 t5 = (cpy[x] >> 24) & 0xff;
74 array[counts.c5[t5]] = cpy[x];
75 counts.c5[t5]++;
76 }
77 for(x = 0; x < size; ++x) {
78 t4 = (array[x] >> 32) & 0xff;
79 cpy[counts.c4[t4]] = array[x];
80 counts.c4[t4]++;
81 }
82 for(x = 0; x < size; ++x) {
83 t3 = (cpy[x] >> 40) & 0xff;
84 array[counts.c3[t3]] = cpy[x];
85 counts.c3[t3]++;
86 }
87 for(x = 0; x < size; ++x) {
88 t2 = (array[x] >> 48) & 0xff;
89 cpy[counts.c2[t2]] = array[x];
90 counts.c2[t2]++;
91 }
92 for(x = 0; x < size; ++x) {
93 t1 = (cpy[x] >> 56) & 0xff;
94 array[counts.c1[t1]] = cpy[x];
95 counts.c1[t1]++;
96 }
97 free(cpy);
98 return array;
99}
Impressum, Datenschutz