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

   1 #include "bucketsort.h"
   2
   3 bool bucket_malloc(bucket_array_t bucket) {
   4         for (uint32_t i = 0; i < 2; i++) {
   5                 for (uint32_t j = 0; j <= 0xff; j++) {
   6                         bucket[i][j].head = malloc(sizeof(uint32_t)<<14);
   7                         if (!bucket[i][j].head) {
   8                                 return false;
   9                         }
  10                 }
  11         }
  12         return true;
  13 }
  14
  15 void bucket_free(bucket_array_t bucket) {
  16         for (uint8_t i = 0; i < 2; i++)
  17                 for (uint8_t j = 0; j <= 0xff; j++)
  18                         free(bucket[i][j].head);
  19 }
  20
  21 void bucket_sort_intersect(uint32_t* const estart, uint32_t* const estop,
  22                                                                   uint32_t* const ostart, uint32_t* const ostop,
  23                                                                   bucket_info_t *bucket_info, bucket_array_t bucket)
  24 {
  25         uint32_t *p1, *p2;
  26         uint32_t *start[2];
  27         uint32_t *stop[2];
  28
  29         start[0] = estart;
  30         stop[0] = estop;
  31         start[1] = ostart;
  32         stop[1] = ostop;
  33
  34         // init buckets to be empty
  35         for (uint32_t i = 0; i < 2; i++) {
  36                 for (uint32_t j = 0x00; j <= 0xff; j++) {
  37                         bucket[i][j].bp = bucket[i][j].head;
  38                 }
  39         }
  40
  41         // sort the lists into the buckets based on the MSB (contribution bits)
  42         for (uint32_t i = 0; i < 2; i++) {
  43                 for (p1 = start[i]; p1 <= stop[i]; p1++) {
  44                         uint32_t bucket_index = (*p1 & 0xff000000) >> 24;
  45                         *(bucket[i][bucket_index].bp++) = *p1;
  46                 }
  47         }
  48
  49         // write back intersecting buckets as sorted list.
  50         // fill in bucket_info with head and tail of the bucket contents in the list and number of non-empty buckets.
  51         uint32_t nonempty_bucket;
  52         for (uint32_t i = 0; i < 2; i++) {
  53                 p1 = start[i];
  54                 nonempty_bucket = 0;
  55                 for (uint32_t j = 0x00; j <= 0xff; j++) {
  56                         if (bucket[0][j].bp != bucket[0][j].head && bucket[1][j].bp != bucket[1][j].head) { // non-empty intersecting buckets only
  57                                 bucket_info->bucket_info[i][nonempty_bucket].head = p1;
  58                                 for (p2 = bucket[i][j].head; p2 < bucket[i][j].bp; *p1++ = *p2++);
  59                                 bucket_info->bucket_info[i][nonempty_bucket].tail = p1 - 1;
  60                                 nonempty_bucket++;
  61                         }
  62                 }
  63                 bucket_info->numbuckets = nonempty_bucket;
  64         }
  65 }