From: iceman1001 Date: Wed, 10 Feb 2016 12:09:33 +0000 (+0100) Subject: CHG: Extracted @piwi's bucketsort into separate files under /common X-Git-Url: https://git.zerfleddert.de/cgi-bin/gitweb.cgi/proxmark3-svn/commitdiff_plain/089d061f2d8dd77840db5968992144474cb36b7c CHG: Extracted @piwi's bucketsort into separate files under /common --- diff --git a/client/Makefile b/client/Makefile index 61afaf59..e2533de3 100644 --- a/client/Makefile +++ b/client/Makefile @@ -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 diff --git a/client/nonce2key/crapto1.c b/client/nonce2key/crapto1.c index 0faeb1d1..36e21a1c 100644 --- a/client/nonce2key/crapto1.c +++ b/client/nonce2key/crapto1.c @@ -31,90 +31,10 @@ static void __attribute__((constructor)) fill_lut() #define filter(x) (filterlut[(x) & 0xfffff]) #endif - - -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; - - -static 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; - } -} - -/** binsearch - * Binary search for the first occurence of *stop's MSB in sorted [start,stop] - */ -static inline uint32_t* binsearch(uint32_t *start, uint32_t *stop) -{ - uint32_t mid, val = *stop & 0xff000000; - while(start != stop) - if(start[mid = (stop - start) >> 1] > val) - stop = &start[mid]; - else - start += mid + 1; - - return start; -} - /** update_contribution * helper, calculates the partial linear feedback contributions and puts in MSB */ -static inline void -update_contribution(uint32_t *item, const uint32_t mask1, const uint32_t mask2) +static inline void update_contribution(uint32_t *item, const uint32_t mask1, const uint32_t mask2) { uint32_t p = *item >> 25; @@ -126,8 +46,7 @@ update_contribution(uint32_t *item, const uint32_t mask1, const uint32_t mask2) /** extend_table * using a bit of the keystream extend the table of possible lfsr states */ -static inline void -extend_table(uint32_t *tbl, uint32_t **end, int bit, int m1, int m2, uint32_t in) +static inline void extend_table(uint32_t *tbl, uint32_t **end, int bit, int m1, int m2, uint32_t in) { in <<= 24; for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1) @@ -150,14 +69,16 @@ extend_table(uint32_t *tbl, uint32_t **end, int bit, int m1, int m2, uint32_t in */ static inline void extend_table_simple(uint32_t *tbl, uint32_t **end, int bit) { - for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1) + for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1) { if(filter(*tbl) ^ filter(*tbl | 1)) { // replace *tbl |= filter(*tbl) ^ bit; } else if(filter(*tbl) == bit) { // insert *++*end = *++tbl; *tbl = tbl[-1] | 1; - } else // drop + } else { // drop *tbl-- = *(*end)--; + } + } } /** recover * recursively narrow down the search space, 4 bits of keystream at a time @@ -186,13 +107,11 @@ recover(uint32_t *o_head, uint32_t *o_tail, uint32_t oks, oks >>= 1; eks >>= 1; in >>= 2; - extend_table(o_head, &o_tail, oks & 1, LF_POLY_EVEN << 1 | 1, - LF_POLY_ODD << 1, 0); + extend_table(o_head, &o_tail, oks & 1, LF_POLY_EVEN << 1 | 1, LF_POLY_ODD << 1, 0); if(o_head > o_tail) return sl; - extend_table(e_head, &e_tail, eks & 1, LF_POLY_ODD, - LF_POLY_EVEN << 1 | 1, in & 3); + extend_table(e_head, &e_tail, eks & 1, LF_POLY_ODD, LF_POLY_EVEN << 1 | 1, in & 3); if(e_head > e_tail) return sl; } @@ -238,14 +157,8 @@ struct Crypto1State* lfsr_recovery32(uint32_t ks2, uint32_t in) // allocate memory for out of place bucket_sort 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) { - goto out; - } - } - + + if ( !bucket_malloc(bucket) ) goto out; // initialize statelists: add all possible states which would result into the rightmost 2 bits of the keystream for(i = 1 << 20; i >= 0; --i) { @@ -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" // parameter into account. in = (in >> 16 & 0xff) | (in << 16) | (in & 0xff00); // Byte swapping - recover(odd_head, odd_tail, oks, - even_head, even_tail, eks, 11, statelist, in << 1, bucket); - + recover(odd_head, odd_tail, oks, even_head, even_tail, eks, 11, statelist, in << 1, bucket); out: free(odd_head); free(even_head); - for (uint32_t i = 0; i < 2; i++) - for (uint32_t j = 0; j <= 0xff; j++) - free(bucket[i][j].head); - + bucket_free(bucket); return statelist; } diff --git a/client/nonce2key/crapto1.h b/client/nonce2key/crapto1.h index a1094e3f..57102712 100644 --- a/client/nonce2key/crapto1.h +++ b/client/nonce2key/crapto1.h @@ -20,6 +20,7 @@ #ifndef CRAPTO1_H__ #define CRAPTO1_H__ #include +#include "bucketsort.h" #ifdef __cplusplus extern "C" { #endif diff --git a/common/bucketsort.c b/common/bucketsort.c new file mode 100644 index 00000000..c4199803 --- /dev/null +++ b/common/bucketsort.c @@ -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 index 00000000..399277c1 --- /dev/null +++ b/common/bucketsort.h @@ -0,0 +1,26 @@ +#ifndef BUCKETSORT_H__ +#define BUCKETSORT_H__ +#include +#include +#include +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 index 00000000..91495316 --- /dev/null +++ b/common/radixsort.c @@ -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 index 00000000..30a4ca0f --- /dev/null +++ b/common/radixsort.h @@ -0,0 +1,23 @@ +#ifndef RADIXSORT_H__ +#define RADIXSORT_H__ + +#include +#include +#include + +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