]> cvs.zerfleddert.de Git - proxmark3-svn/commitdiff
CHG: Extracted @piwi's bucketsort into separate files under /common
authoriceman1001 <iceman@iuse.se>
Wed, 10 Feb 2016 12:09:33 +0000 (13:09 +0100)
committericeman1001 <iceman@iuse.se>
Wed, 10 Feb 2016 12:09:33 +0000 (13:09 +0100)
client/Makefile
client/nonce2key/crapto1.c
client/nonce2key/crapto1.h
common/bucketsort.c [new file with mode: 0644]
common/bucketsort.h [new file with mode: 0644]
common/radixsort.c [new file with mode: 0644]
common/radixsort.h [new file with mode: 0644]

index 61afaf599475d1af9bfe1297a92c304b560f420b..e2533de333daeb33f428adf650d2bb61f7b9c8cc 100644 (file)
@@ -141,7 +141,9 @@ CMDSRCS =   nonce2key/crapto1.c\
                        reveng/poly.c\
                        reveng/getopt.c\
                        tea.c\
-                       prng.c
+                       prng.c\
+                       radixsort.c\
+                       bucketsort.c
 
 ZLIBSRCS = deflate.c adler32.c trees.c zutil.c inflate.c inffast.c inftrees.c
 ZLIB_FLAGS = -DZ_SOLO -DZ_PREFIX -DNO_GZIP -DZLIB_PM3_TUNED 
index 0faeb1d1cdccb124698f393f886b3e9380d5e7a3..36e21a1ce9b13ddccae09772c407c72c6095c007 100644 (file)
@@ -31,90 +31,10 @@ static void __attribute__((constructor)) fill_lut()
 #define filter(x) (filterlut[(x) & 0xfffff])\r
 #endif\r
 \r
-\r
-\r
-typedef struct bucket {\r
-       uint32_t *head;\r
-       uint32_t *bp;\r
-} bucket_t;\r
-\r
-typedef bucket_t bucket_array_t[2][0x100];\r
-\r
-typedef struct bucket_info {\r
-       struct {\r
-               uint32_t *head, *tail;\r
-               } bucket_info[2][0x100];\r
-               uint32_t numbuckets;\r
-       } bucket_info_t;\r
-\r
-\r
-static void bucket_sort_intersect(uint32_t* const estart, uint32_t* const estop,\r
-                                                                 uint32_t* const ostart, uint32_t* const ostop,\r
-                                                                 bucket_info_t *bucket_info, bucket_array_t bucket)\r
-{\r
-       uint32_t *p1, *p2;\r
-       uint32_t *start[2];\r
-       uint32_t *stop[2];\r
-\r
-       start[0] = estart;\r
-       stop[0] = estop;\r
-       start[1] = ostart;\r
-       stop[1] = ostop;\r
-\r
-       // init buckets to be empty\r
-       for (uint32_t i = 0; i < 2; i++) {\r
-               for (uint32_t j = 0x00; j <= 0xff; j++) {\r
-                       bucket[i][j].bp = bucket[i][j].head;\r
-               }\r
-       }\r
-\r
-       // sort the lists into the buckets based on the MSB (contribution bits)\r
-       for (uint32_t i = 0; i < 2; i++) {\r
-               for (p1 = start[i]; p1 <= stop[i]; p1++) {\r
-                       uint32_t bucket_index = (*p1 & 0xff000000) >> 24;\r
-                       *(bucket[i][bucket_index].bp++) = *p1;\r
-               }\r
-       }\r
-\r
-\r
-       // write back intersecting buckets as sorted list.\r
-       // fill in bucket_info with head and tail of the bucket contents in the list and number of non-empty buckets.\r
-       uint32_t nonempty_bucket;\r
-       for (uint32_t i = 0; i < 2; i++) {\r
-               p1 = start[i];\r
-               nonempty_bucket = 0;\r
-               for (uint32_t j = 0x00; j <= 0xff; j++) {\r
-                       if (bucket[0][j].bp != bucket[0][j].head && bucket[1][j].bp != bucket[1][j].head) { // non-empty intersecting buckets only\r
-                               bucket_info->bucket_info[i][nonempty_bucket].head = p1;\r
-                               for (p2 = bucket[i][j].head; p2 < bucket[i][j].bp; *p1++ = *p2++);\r
-                               bucket_info->bucket_info[i][nonempty_bucket].tail = p1 - 1;\r
-                               nonempty_bucket++;\r
-                       }\r
-               }\r
-               bucket_info->numbuckets = nonempty_bucket;\r
-               }\r
-}\r
-\r
-/** binsearch\r
- * Binary search for the first occurence of *stop's MSB in sorted [start,stop]\r
- */\r
-static inline uint32_t* binsearch(uint32_t *start, uint32_t *stop)\r
-{\r
-       uint32_t mid, val = *stop & 0xff000000;\r
-       while(start != stop)\r
-               if(start[mid = (stop - start) >> 1] > val)\r
-                       stop = &start[mid];\r
-               else\r
-                       start += mid + 1;\r
-\r
-       return start;\r
-}\r
-\r
 /** update_contribution\r
  * helper, calculates the partial linear feedback contributions and puts in MSB\r
  */\r
-static inline void\r
-update_contribution(uint32_t *item, const uint32_t mask1, const uint32_t mask2)\r
+static inline void update_contribution(uint32_t *item, const uint32_t mask1, const uint32_t mask2)\r
 {\r
        uint32_t p = *item >> 25;\r
 \r
@@ -126,8 +46,7 @@ update_contribution(uint32_t *item, const uint32_t mask1, const uint32_t mask2)
 /** extend_table\r
  * using a bit of the keystream extend the table of possible lfsr states\r
  */\r
-static inline void\r
-extend_table(uint32_t *tbl, uint32_t **end, int bit, int m1, int m2, uint32_t in)\r
+static inline void extend_table(uint32_t *tbl, uint32_t **end, int bit, int m1, int m2, uint32_t in)\r
 {\r
        in <<= 24;\r
        for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1)\r
@@ -150,14 +69,16 @@ extend_table(uint32_t *tbl, uint32_t **end, int bit, int m1, int m2, uint32_t in
  */\r
 static inline void extend_table_simple(uint32_t *tbl, uint32_t **end, int bit)\r
 {\r
-       for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1)\r
+       for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1) {\r
                if(filter(*tbl) ^ filter(*tbl | 1)) {   // replace\r
                        *tbl |= filter(*tbl) ^ bit;\r
                } else if(filter(*tbl) == bit) {                // insert\r
                        *++*end = *++tbl;\r
                        *tbl = tbl[-1] | 1;\r
-               } else                                                                  // drop\r
+               } else  {                                                               // drop\r
                        *tbl-- = *(*end)--;\r
+               }\r
+       }\r
 }\r
 /** recover\r
  * recursively narrow down the search space, 4 bits of keystream at a time\r
@@ -186,13 +107,11 @@ recover(uint32_t *o_head, uint32_t *o_tail, uint32_t oks,
                oks >>= 1;\r
                eks >>= 1;\r
                in >>= 2;\r
-               extend_table(o_head, &o_tail, oks & 1, LF_POLY_EVEN << 1 | 1,\r
-                            LF_POLY_ODD << 1, 0);\r
+               extend_table(o_head, &o_tail, oks & 1, LF_POLY_EVEN << 1 | 1, LF_POLY_ODD << 1, 0);\r
                if(o_head > o_tail)\r
                        return sl;\r
 \r
-               extend_table(e_head, &e_tail, eks & 1, LF_POLY_ODD,\r
-                            LF_POLY_EVEN << 1 | 1, in & 3);\r
+               extend_table(e_head, &e_tail, eks & 1, LF_POLY_ODD, LF_POLY_EVEN << 1 | 1, in & 3);\r
                if(e_head > e_tail)\r
                        return sl;\r
        }\r
@@ -238,14 +157,8 @@ struct Crypto1State* lfsr_recovery32(uint32_t ks2, uint32_t in)
 \r
        // allocate memory for out of place bucket_sort\r
        bucket_array_t bucket;\r
-       for (uint32_t i = 0; i < 2; i++)\r
-               for (uint32_t j = 0; j <= 0xff; j++) {\r
-                       bucket[i][j].head = malloc(sizeof(uint32_t)<<14);\r
-                       if (!bucket[i][j].head) {\r
-                               goto out;\r
-                       }\r
-               }\r
-\r
+       \r
+       if ( !bucket_malloc(bucket) ) goto out;\r
 \r
        // initialize statelists: add all possible states which would result into the rightmost 2 bits of the keystream\r
        for(i = 1 << 20; i >= 0; --i) {\r
@@ -265,17 +178,12 @@ struct Crypto1State* lfsr_recovery32(uint32_t ks2, uint32_t in)
        // 22 bits to go to recover 32 bits in total. From now on, we need to take the "in"\r
        // parameter into account.\r
        in = (in >> 16 & 0xff) | (in << 16) | (in & 0xff00);            // Byte swapping\r
-       recover(odd_head, odd_tail, oks,\r
-               even_head, even_tail, eks, 11, statelist, in << 1, bucket);\r
-\r
+       recover(odd_head, odd_tail, oks, even_head, even_tail, eks, 11, statelist, in << 1, bucket);\r
 \r
 out:\r
        free(odd_head);\r
        free(even_head);\r
-       for (uint32_t i = 0; i < 2; i++)\r
-               for (uint32_t j = 0; j <= 0xff; j++)\r
-                       free(bucket[i][j].head);\r
-\r
+       bucket_free(bucket);\r
        return statelist;\r
 }\r
 \r
index a1094e3f1af434e784dad5eeb8831bc13d3884ea..571027126bd969b6573e818b9b5c79590aa33d8f 100644 (file)
@@ -20,6 +20,7 @@
 #ifndef CRAPTO1_H__
 #define CRAPTO1_H__
 #include <stdint.h>
+#include "bucketsort.h"
 #ifdef __cplusplus
 extern "C" {
 #endif
diff --git a/common/bucketsort.c b/common/bucketsort.c
new file mode 100644 (file)
index 0000000..c419980
--- /dev/null
@@ -0,0 +1,65 @@
+#include "bucketsort.h"
+
+bool bucket_malloc(bucket_array_t bucket) {
+       for (uint32_t i = 0; i < 2; i++) {
+               for (uint32_t j = 0; j <= 0xff; j++) {
+                       bucket[i][j].head = malloc(sizeof(uint32_t)<<14);
+                       if (!bucket[i][j].head) {
+                               return false;
+                       }
+               }
+       }
+       return true;
+}
+
+void bucket_free(bucket_array_t bucket) {
+       for (uint8_t i = 0; i < 2; i++)
+               for (uint8_t j = 0; j <= 0xff; j++)
+                       free(bucket[i][j].head);
+}
+
+void bucket_sort_intersect(uint32_t* const estart, uint32_t* const estop,
+                                                                 uint32_t* const ostart, uint32_t* const ostop,
+                                                                 bucket_info_t *bucket_info, bucket_array_t bucket)
+{
+       uint32_t *p1, *p2;
+       uint32_t *start[2];
+       uint32_t *stop[2];
+
+       start[0] = estart;
+       stop[0] = estop;
+       start[1] = ostart;
+       stop[1] = ostop;
+
+       // init buckets to be empty
+       for (uint32_t i = 0; i < 2; i++) {
+               for (uint32_t j = 0x00; j <= 0xff; j++) {
+                       bucket[i][j].bp = bucket[i][j].head;
+               }
+       }
+
+       // sort the lists into the buckets based on the MSB (contribution bits)
+       for (uint32_t i = 0; i < 2; i++) {
+               for (p1 = start[i]; p1 <= stop[i]; p1++) {
+                       uint32_t bucket_index = (*p1 & 0xff000000) >> 24;
+                       *(bucket[i][bucket_index].bp++) = *p1;
+               }
+       }
+
+       // write back intersecting buckets as sorted list.
+       // fill in bucket_info with head and tail of the bucket contents in the list and number of non-empty buckets.
+       uint32_t nonempty_bucket;
+       for (uint32_t i = 0; i < 2; i++) {
+               p1 = start[i];
+               nonempty_bucket = 0;
+               for (uint32_t j = 0x00; j <= 0xff; j++) {
+                       if (bucket[0][j].bp != bucket[0][j].head && bucket[1][j].bp != bucket[1][j].head) { // non-empty intersecting buckets only
+                               bucket_info->bucket_info[i][nonempty_bucket].head = p1;
+                               for (p2 = bucket[i][j].head; p2 < bucket[i][j].bp; *p1++ = *p2++);
+                               bucket_info->bucket_info[i][nonempty_bucket].tail = p1 - 1;
+                               nonempty_bucket++;
+                       }
+               }
+               bucket_info->numbuckets = nonempty_bucket;
+       }
+}
diff --git a/common/bucketsort.h b/common/bucketsort.h
new file mode 100644 (file)
index 0000000..399277c
--- /dev/null
@@ -0,0 +1,26 @@
+#ifndef BUCKETSORT_H__
+#define BUCKETSORT_H__
+#include <stdint.h>
+#include <stdbool.h>
+#include <stdlib.h>
+typedef struct bucket {
+       uint32_t *head;
+       uint32_t *bp;
+} bucket_t;
+
+typedef bucket_t bucket_array_t[2][0x100];
+
+typedef struct bucket_info {
+       struct {
+               uint32_t *head, *tail;
+               } bucket_info[2][0x100];
+               uint32_t numbuckets;
+} bucket_info_t;
+
+
+bool bucket_malloc(bucket_array_t bucket);
+void bucket_free(bucket_array_t bucket);
+void bucket_sort_intersect(uint32_t* const estart, uint32_t* const estop,
+                                                                 uint32_t* const ostart, uint32_t* const ostop,
+                                                                 bucket_info_t *bucket_info, bucket_array_t bucket);
+#endif
\ No newline at end of file
diff --git a/common/radixsort.c b/common/radixsort.c
new file mode 100644 (file)
index 0000000..9149531
--- /dev/null
@@ -0,0 +1,99 @@
+#include "radixsort.h"
+
+uint64_t * radixSort(uint64_t * array, uint32_t size) {
+    rscounts_t counts;
+    memset(&counts, 0, 256 * 8 * sizeof(uint32_t));
+    uint64_t * cpy = (uint64_t *)malloc(size * sizeof(uint64_t));
+    uint32_t o8=0, o7=0, o6=0, o5=0, o4=0, o3=0, o2=0, o1=0;
+    uint32_t t8, t7, t6, t5, t4, t3, t2, t1;
+    uint32_t x;
+    // calculate counts
+    for(x = 0; x < size; ++x) {
+        t8 = array[x] & 0xff;
+        t7 = (array[x] >> 8) & 0xff;
+        t6 = (array[x] >> 16) & 0xff;
+        t5 = (array[x] >> 24) & 0xff;
+        t4 = (array[x] >> 32) & 0xff;
+        t3 = (array[x] >> 40) & 0xff;
+        t2 = (array[x] >> 48) & 0xff;
+        t1 = (array[x] >> 56) & 0xff;
+        counts.c8[t8]++;
+        counts.c7[t7]++;
+        counts.c6[t6]++;
+        counts.c5[t5]++;
+        counts.c4[t4]++;
+        counts.c3[t3]++;
+        counts.c2[t2]++;
+        counts.c1[t1]++;
+    }
+    // convert counts to offsets
+    for(x = 0; x < 256; ++x) {
+        t8 = o8 + counts.c8[x];
+        t7 = o7 + counts.c7[x];
+        t6 = o6 + counts.c6[x];
+        t5 = o5 + counts.c5[x];
+        t4 = o4 + counts.c4[x];
+        t3 = o3 + counts.c3[x];
+        t2 = o2 + counts.c2[x];
+        t1 = o1 + counts.c1[x];
+        counts.c8[x] = o8;
+        counts.c7[x] = o7;
+        counts.c6[x] = o6;
+        counts.c5[x] = o5;
+        counts.c4[x] = o4;
+        counts.c3[x] = o3;
+        counts.c2[x] = o2;
+        counts.c1[x] = o1;
+        o8 = t8; 
+        o7 = t7; 
+        o6 = t6; 
+        o5 = t5; 
+        o4 = t4; 
+        o3 = t3; 
+        o2 = t2; 
+        o1 = t1;
+    }
+    // radix
+    for(x = 0; x < size; ++x) {
+        t8 = array[x] & 0xff;
+        cpy[counts.c8[t8]] = array[x];
+        counts.c8[t8]++;
+    }
+    for(x = 0; x < size; ++x) {
+        t7 = (cpy[x] >> 8) & 0xff;
+        array[counts.c7[t7]] = cpy[x];
+        counts.c7[t7]++;
+    }
+    for(x = 0; x < size; ++x) {
+        t6 = (array[x] >> 16) & 0xff;
+        cpy[counts.c6[t6]] = array[x];
+        counts.c6[t6]++;
+    }
+    for(x = 0; x < size; ++x) {
+        t5 = (cpy[x] >> 24) & 0xff;
+        array[counts.c5[t5]] = cpy[x];
+        counts.c5[t5]++;
+    }
+    for(x = 0; x < size; ++x) {
+        t4 = (array[x] >> 32) & 0xff;
+        cpy[counts.c4[t4]] = array[x];
+        counts.c4[t4]++;
+    }
+    for(x = 0; x < size; ++x) {
+        t3 = (cpy[x] >> 40) & 0xff;
+        array[counts.c3[t3]] = cpy[x];
+        counts.c3[t3]++;
+    }
+    for(x = 0; x < size; ++x) {
+        t2 = (array[x] >> 48) & 0xff;
+        cpy[counts.c2[t2]] = array[x];
+        counts.c2[t2]++;
+    }
+    for(x = 0; x < size; ++x) {
+        t1 = (cpy[x] >> 56) & 0xff;
+        array[counts.c1[t1]] = cpy[x];
+        counts.c1[t1]++;
+    }
+    free(cpy);
+    return array;
+}
\ No newline at end of file
diff --git a/common/radixsort.h b/common/radixsort.h
new file mode 100644 (file)
index 0000000..30a4ca0
--- /dev/null
@@ -0,0 +1,23 @@
+#ifndef RADIXSORT_H__
+#define RADIXSORT_H__
+
+#include <string.h>
+#include <stdint.h>
+#include <stdlib.h>
+
+typedef union {
+    struct {
+        uint32_t c8[256];
+        uint32_t c7[256];
+        uint32_t c6[256];
+        uint32_t c5[256];
+        uint32_t c4[256];
+        uint32_t c3[256];
+        uint32_t c2[256];
+        uint32_t c1[256];
+    };
+    uint32_t counts[256 * 8];
+} rscounts_t;
+
+uint64_t * radixSort(uint64_t * array, uint32_t size);
+#endif // RADIXSORT_H__
\ No newline at end of file
Impressum, Datenschutz