git.zerfleddert.de Git - proxmark3-svn/blob - common/bucketsort.c

   1 #include "bucketsort.h"
   2
   3 extern 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 }