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

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