]> git.zerfleddert.de Git - proxmark3-svn/blame_incremental - common/bucketsort.c
Update README.md
[proxmark3-svn] / common / bucketsort.c
... / ...
CommitLineData
1#include "bucketsort.h"
2
3extern void bucket_sort_intersect(uint32_t* const estart, uint32_t* const estop,
4 uint32_t* const ostart, uint32_t* const ostop,
5 bucket_info_t *bucket_info, bucket_array_t bucket)
6{
7 uint32_t *p1, *p2;
8 uint32_t *start[2];
9 uint32_t *stop[2];
10
11 start[0] = estart;
12 stop[0] = estop;
13 start[1] = ostart;
14 stop[1] = ostop;
15
16 // init buckets to be empty
17 for (uint32_t i = 0; i < 2; i++) {
18 for (uint32_t j = 0x00; j <= 0xff; j++) {
19 bucket[i][j].bp = bucket[i][j].head;
20 }
21 }
22
23 // sort the lists into the buckets based on the MSB (contribution bits)
24 for (uint32_t i = 0; i < 2; i++) {
25 for (p1 = start[i]; p1 <= stop[i]; p1++) {
26 uint32_t bucket_index = (*p1 & 0xff000000) >> 24;
27 *(bucket[i][bucket_index].bp++) = *p1;
28 }
29 }
30
31 // write back intersecting buckets as sorted list.
32 // fill in bucket_info with head and tail of the bucket contents in the list and number of non-empty buckets.
33 uint32_t nonempty_bucket;
34 for (uint32_t i = 0; i < 2; i++) {
35 p1 = start[i];
36 nonempty_bucket = 0;
37 for (uint32_t j = 0x00; j <= 0xff; j++) {
38 if (bucket[0][j].bp != bucket[0][j].head && bucket[1][j].bp != bucket[1][j].head) { // non-empty intersecting buckets only
39 bucket_info->bucket_info[i][nonempty_bucket].head = p1;
40 for (p2 = bucket[i][j].head; p2 < bucket[i][j].bp; *p1++ = *p2++);
41 bucket_info->bucket_info[i][nonempty_bucket].tail = p1 - 1;
42 nonempty_bucket++;
43 }
44 }
45 bucket_info->numbuckets = nonempty_bucket;
46 }
47}
Impressum, Datenschutz