X-Git-Url: http://cvs.zerfleddert.de/cgi-bin/gitweb.cgi/proxmark3-svn/blobdiff_plain/49dc1d0a9eafdb1e369ead88c3c8882bc6959a17..ca3ed459283f056e713ab7fd5333ce2d79cc50b0:/client/nonce2key/crapto1.c

diff --git a/client/nonce2key/crapto1.c b/client/nonce2key/crapto1.c
index 1d7441c7..8754c3c9 100644
--- a/client/nonce2key/crapto1.c
+++ b/client/nonce2key/crapto1.c
@@ -15,7 +15,7 @@
     Foundation, Inc., 51 Franklin Street, Fifth Floor,
     Boston, MA  02110-1301, US$
 
-    Copyright (C) 2008-2008 bla <blapost@gmail.com>
+    Copyright (C) 2008-2014 bla <blapost@gmail.com>
 */
 #include "crapto1.h"
 #include <stdlib.h>
@@ -31,75 +31,33 @@ 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)
+static void quicksort(uint32_t* const start, uint32_t* const stop)
 {
-	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;
-		}
-	}
+	uint32_t *it = start + 1, *rit = stop, t;
 
-	// 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;
-		}
-	}
+	if(it > rit)
+		return;
 
+	while(it < rit)
+		if(*it <= *start)
+			++it;
+		else if(*rit > *start)
+			--rit;
+		else
+			t = *it,  *it = *rit, *rit = t;
 
-	// 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;
-		}
-}
+	if(*rit >= *start)
+		--rit;
+	if(rit != start)
+		t = *rit,  *rit = *start, *start = t;
 
+	quicksort(start, rit - 1);
+	quicksort(rit + 1, stop);
+}
 /** 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)
+static inline uint32_t* binsearch(uint32_t *start, uint32_t *stop)
 {
 	uint32_t mid, val = *stop & 0xff000000;
 	while(start != stop)
@@ -131,33 +89,25 @@ static inline void
 extend_table(uint32_t *tbl, uint32_t **end, int bit, int m1, int m2, uint32_t in)
 {
 	in <<= 24;
-
-	for(uint32_t *p = tbl; p <= *end; p++) {
-		*p <<= 1;
-		if(filter(*p) != filter(*p | 1)) {			 	// replace
-			*p |= filter(*p) ^ bit;
-			update_contribution(p, m1, m2);
-			*p ^= in;
-		} else if(filter(*p) == bit) {					// insert
-			*++*end = p[1];
-			p[1] = p[0] | 1;
-			update_contribution(p, m1, m2);
-			*p++ ^= in;
-			update_contribution(p, m1, m2);
-			*p ^= in;
-		} else {										// drop
-			*p-- = *(*end)--;
-	}
-	}
-
+	for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1)
+		if(filter(*tbl) ^ filter(*tbl | 1)) {
+			*tbl |= filter(*tbl) ^ bit;
+			update_contribution(tbl, m1, m2);
+			*tbl ^= in;
+		} else if(filter(*tbl) == bit) {
+			*++*end = tbl[1];
+			tbl[1] = tbl[0] | 1;
+			update_contribution(tbl, m1, m2);
+			*tbl++ ^= in;
+			update_contribution(tbl, m1, m2);
+			*tbl ^= in;
+		} else
+			*tbl-- = *(*end)--;
 }
-
-
 /** extend_table_simple
  * using a bit of the keystream extend the table of possible lfsr states
  */
-static inline void
-extend_table_simple(uint32_t *tbl, uint32_t **end, int bit)
+static inline void extend_table_simple(uint32_t *tbl, uint32_t **end, int bit)
 {
 	for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1)
 		if(filter(*tbl) ^ filter(*tbl | 1)) {	// replace
@@ -176,10 +126,9 @@ extend_table_simple(uint32_t *tbl, uint32_t **end, int bit)
 static struct Crypto1State*
 recover(uint32_t *o_head, uint32_t *o_tail, uint32_t oks,
 	uint32_t *e_head, uint32_t *e_tail, uint32_t eks, int rem,
-	struct Crypto1State *sl, uint32_t in, bucket_array_t bucket)
+	struct Crypto1State *sl, uint32_t in)
 {
-	uint32_t *o, *e;
-	bucket_info_t bucket_info;
+	uint32_t *o, *e, i;
 
 	if(rem == -1) {
 		for(e = e_head; e <= e_tail; ++e) {
@@ -187,31 +136,41 @@ recover(uint32_t *o_head, uint32_t *o_tail, uint32_t oks,
 			for(o = o_head; o <= o_tail; ++o, ++sl) {
 				sl->even = *o;
 				sl->odd = *e ^ parity(*o & LF_POLY_ODD);
+				sl[1].odd = sl[1].even = 0;
 			}
 		}
-		sl->odd = sl->even = 0;
 		return sl;
 	}
 
-	for(uint32_t i = 0; i < 4 && rem--; i++) {
-		extend_table(o_head, &o_tail, (oks >>= 1) & 1,
-			LF_POLY_EVEN << 1 | 1, LF_POLY_ODD << 1, 0);
+	for(i = 0; i < 4 && rem--; i++) {
+		oks >>= 1;
+		eks >>= 1;
+		in >>= 2;
+		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) & 1,
-			LF_POLY_ODD, LF_POLY_EVEN << 1 | 1, (in >>= 2) & 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;
 	}
 
-	bucket_sort_intersect(e_head, e_tail, o_head, o_tail, &bucket_info, bucket);
+	quicksort(o_head, o_tail);
+	quicksort(e_head, e_tail);
 
-	for (int i = bucket_info.numbuckets - 1; i >= 0; i--) {
-		sl = recover(bucket_info.bucket_info[1][i].head, bucket_info.bucket_info[1][i].tail, oks,
-				     bucket_info.bucket_info[0][i].head, bucket_info.bucket_info[0][i].tail, eks,
-					 rem, sl, in, bucket);
+	while(o_tail >= o_head && e_tail >= e_head)
+		if(((*o_tail ^ *e_tail) >> 24) == 0) {
+			o_tail = binsearch(o_head, o = o_tail);
+			e_tail = binsearch(e_head, e = e_tail);
+			sl = recover(o_tail--, o, oks,
+				     e_tail--, e, eks, rem, sl, in);
 	}
+		else if(*o_tail > *e_tail)
+			o_tail = binsearch(o_head, o_tail) - 1;
+		else
+			e_tail = binsearch(e_head, e_tail) - 1;
 
 	return sl;
 }
@@ -237,20 +196,12 @@ struct Crypto1State* lfsr_recovery32(uint32_t ks2, uint32_t in)
 	even_head = even_tail = malloc(sizeof(uint32_t) << 21);
 	statelist =  malloc(sizeof(struct Crypto1State) << 18);
 	if(!odd_tail-- || !even_tail-- || !statelist) {
+		free(statelist);
+		statelist = 0;
 		goto out;
 	}
-	statelist->odd = statelist->even = 0;
-
-	// 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;
-			}
-		}
 
+	statelist->odd = statelist->even = 0;
 
 	// initialize statelists: add all possible states which would result into the rightmost 2 bits of the keystream
 	for(i = 1 << 20; i >= 0; --i) {
@@ -269,20 +220,13 @@ struct Crypto1State* lfsr_recovery32(uint32_t ks2, uint32_t in)
 	// the statelists now contain all states which could have generated the last 10 Bits of the keystream.
 	// 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
-
+	in = (in >> 16 & 0xff) | (in << 16) | (in & 0xff00);
 	recover(odd_head, odd_tail, oks,
-		even_head, even_tail, eks, 11, statelist, in << 1, bucket);
-
+		even_head, even_tail, eks, 11, statelist, in << 1);
 
 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);
-
 	return statelist;
 }
 
@@ -323,12 +267,12 @@ struct Crypto1State* lfsr_recovery64(uint32_t ks2, uint32_t ks3)
 	sl->odd = sl->even = 0;
 
 	for(i = 30; i >= 0; i -= 2) {
-		oks[i >> 1] = BIT(ks2, i ^ 24);
-		oks[16 + (i >> 1)] = BIT(ks3, i ^ 24);
+		oks[i >> 1] = BEBIT(ks2, i);
+		oks[16 + (i >> 1)] = BEBIT(ks3, i);
 	}
 	for(i = 31; i >= 0; i -= 2) {
-		eks[i >> 1] = BIT(ks2, i ^ 24);
-		eks[16 + (i >> 1)] = BIT(ks3, i ^ 24);
+		eks[i >> 1] = BEBIT(ks2, i);
+		eks[16 + (i >> 1)] = BEBIT(ks3, i);
 	}
 
 	for(i = 0xfffff; i >= 0; --i) {
@@ -379,41 +323,95 @@ struct Crypto1State* lfsr_recovery64(uint32_t ks2, uint32_t ks3)
 /** lfsr_rollback_bit
  * Rollback the shift register in order to get previous states
  */
-void lfsr_rollback_bit(struct Crypto1State *s, uint32_t in, int fb)
+uint8_t lfsr_rollback_bit(struct Crypto1State *s, uint32_t in, int fb)
 {
 	int out;
-	uint32_t tmp;
+	uint8_t ret;
+	uint32_t t;
 
 	s->odd &= 0xffffff;
-	tmp = s->odd;
-	s->odd = s->even;
-	s->even = tmp;
+	t = s->odd, s->odd = s->even, s->even = t;
 
 	out = s->even & 1;
 	out ^= LF_POLY_EVEN & (s->even >>= 1);
 	out ^= LF_POLY_ODD & s->odd;
 	out ^= !!in;
-	out ^= filter(s->odd) & !!fb;
+	out ^= (ret = filter(s->odd)) & !!fb;
 
 	s->even |= parity(out) << 23;
+	return ret;
 }
 /** lfsr_rollback_byte
  * Rollback the shift register in order to get previous states
  */
-void lfsr_rollback_byte(struct Crypto1State *s, uint32_t in, int fb)
+uint8_t lfsr_rollback_byte(struct Crypto1State *s, uint32_t in, int fb)
 {
-	int i;
+	/*
+	int i, ret = 0;
 	for (i = 7; i >= 0; --i)
-		lfsr_rollback_bit(s, BEBIT(in, i), fb);
+		ret |= lfsr_rollback_bit(s, BIT(in, i), fb) << i;
+*/
+// unfold loop 20160112
+	uint8_t ret = 0;
+	ret |= lfsr_rollback_bit(s, BIT(in, 7), fb) << 7;
+	ret |= lfsr_rollback_bit(s, BIT(in, 6), fb) << 6;
+	ret |= lfsr_rollback_bit(s, BIT(in, 5), fb) << 5;
+	ret |= lfsr_rollback_bit(s, BIT(in, 4), fb) << 4;
+	ret |= lfsr_rollback_bit(s, BIT(in, 3), fb) << 3;
+	ret |= lfsr_rollback_bit(s, BIT(in, 2), fb) << 2;
+	ret |= lfsr_rollback_bit(s, BIT(in, 1), fb) << 1;
+	ret |= lfsr_rollback_bit(s, BIT(in, 0), fb) << 0;
+	return ret;
 }
 /** lfsr_rollback_word
  * Rollback the shift register in order to get previous states
  */
-void lfsr_rollback_word(struct Crypto1State *s, uint32_t in, int fb)
+uint32_t lfsr_rollback_word(struct Crypto1State *s, uint32_t in, int fb)
 {
+	/*
 	int i;
+	uint32_t ret = 0;
 	for (i = 31; i >= 0; --i)
-		lfsr_rollback_bit(s, BEBIT(in, i), fb);
+		ret |= lfsr_rollback_bit(s, BEBIT(in, i), fb) << (i ^ 24);
+*/
+// unfold loop 20160112
+	uint32_t ret = 0;
+	ret |= lfsr_rollback_bit(s, BEBIT(in, 31), fb) << (31 ^ 24);
+	ret |= lfsr_rollback_bit(s, BEBIT(in, 30), fb) << (30 ^ 24);
+	ret |= lfsr_rollback_bit(s, BEBIT(in, 29), fb) << (29 ^ 24);
+	ret |= lfsr_rollback_bit(s, BEBIT(in, 28), fb) << (28 ^ 24);
+	ret |= lfsr_rollback_bit(s, BEBIT(in, 27), fb) << (27 ^ 24);
+	ret |= lfsr_rollback_bit(s, BEBIT(in, 26), fb) << (26 ^ 24);
+	ret |= lfsr_rollback_bit(s, BEBIT(in, 25), fb) << (25 ^ 24);
+	ret |= lfsr_rollback_bit(s, BEBIT(in, 24), fb) << (24 ^ 24);
+
+	ret |= lfsr_rollback_bit(s, BEBIT(in, 23), fb) << (23 ^ 24);
+	ret |= lfsr_rollback_bit(s, BEBIT(in, 22), fb) << (22 ^ 24);
+	ret |= lfsr_rollback_bit(s, BEBIT(in, 21), fb) << (21 ^ 24);
+	ret |= lfsr_rollback_bit(s, BEBIT(in, 20), fb) << (20 ^ 24);
+	ret |= lfsr_rollback_bit(s, BEBIT(in, 19), fb) << (19 ^ 24);
+	ret |= lfsr_rollback_bit(s, BEBIT(in, 18), fb) << (18 ^ 24);
+	ret |= lfsr_rollback_bit(s, BEBIT(in, 17), fb) << (17 ^ 24);
+	ret |= lfsr_rollback_bit(s, BEBIT(in, 16), fb) << (16 ^ 24);
+	
+	ret |= lfsr_rollback_bit(s, BEBIT(in, 15), fb) << (15 ^ 24);
+	ret |= lfsr_rollback_bit(s, BEBIT(in, 14), fb) << (14 ^ 24);
+	ret |= lfsr_rollback_bit(s, BEBIT(in, 13), fb) << (13 ^ 24);
+	ret |= lfsr_rollback_bit(s, BEBIT(in, 12), fb) << (12 ^ 24);
+	ret |= lfsr_rollback_bit(s, BEBIT(in, 11), fb) << (11 ^ 24);
+	ret |= lfsr_rollback_bit(s, BEBIT(in, 10), fb) << (10 ^ 24);
+	ret |= lfsr_rollback_bit(s, BEBIT(in, 9), fb) << (9 ^ 24);
+	ret |= lfsr_rollback_bit(s, BEBIT(in, 8), fb) << (8 ^ 24);
+	
+	ret |= lfsr_rollback_bit(s, BEBIT(in, 7), fb) << (7 ^ 24);
+	ret |= lfsr_rollback_bit(s, BEBIT(in, 6), fb) << (6 ^ 24);
+	ret |= lfsr_rollback_bit(s, BEBIT(in, 5), fb) << (5 ^ 24);
+	ret |= lfsr_rollback_bit(s, BEBIT(in, 4), fb) << (4 ^ 24);
+	ret |= lfsr_rollback_bit(s, BEBIT(in, 3), fb) << (3 ^ 24);
+	ret |= lfsr_rollback_bit(s, BEBIT(in, 2), fb) << (2 ^ 24);
+	ret |= lfsr_rollback_bit(s, BEBIT(in, 1), fb) << (1 ^ 24);
+	ret |= lfsr_rollback_bit(s, BEBIT(in, 0), fb) << (0 ^ 24);
+	return ret;
 }
 
 /** nonce_distance
@@ -447,86 +445,63 @@ static uint32_t fastfwd[2][8] = {
  * Described in the "dark side" paper. It returns an -1 terminated array
  * of possible partial(21 bit) secret state.
  * The required keystream(ks) needs to contain the keystream that was used to
- * encrypt the NACK which is observed when varying only the 4 last bits of Nr
+ * encrypt the NACK which is observed when varying only the 3 last bits of Nr
  * only correct iff [NR_3] ^ NR_3 does not depend on Nr_3
  */
 uint32_t *lfsr_prefix_ks(uint8_t ks[8], int isodd)
 {
-	uint32_t *candidates = malloc(4 << 21);
+	uint32_t *candidates = malloc(4 << 10);
+	if(!candidates) return 0;
+	
 	uint32_t c,  entry;
-	int size, i;
-
-	if(!candidates)
-		return 0;
-
-	size = (1 << 21) - 1;
-	for(i = 0; i <= size; ++i)
-		candidates[i] = i;
+	int size = 0, i, good;
 
-	for(c = 0;  c < 8; ++c)
-		for(i = 0;i <= size; ++i) {
-			entry = candidates[i] ^ fastfwd[isodd][c];
-
-			if(filter(entry >> 1) == BIT(ks[c], isodd))
-				if(filter(entry) == BIT(ks[c], isodd + 2))
-					continue;
-
-			candidates[i--] = candidates[size--];
+	for(i = 0; i < 1 << 21; ++i) {
+		for(c = 0, good = 1; good && c < 8; ++c) {
+			entry = i ^ fastfwd[isodd][c];
+			good &= (BIT(ks[c], isodd) == filter(entry >> 1));
+			good &= (BIT(ks[c], isodd + 2) == filter(entry));
 		}
+		if(good)
+			candidates[size++] = i;
+	}
 
-	candidates[size + 1] = -1;
+	candidates[size] = -1;
 
 	return candidates;
 }
 
-/** brute_top
+/** check_pfx_parity
  * helper function which eliminates possible secret states using parity bits
  */
-static struct Crypto1State*
-brute_top(uint32_t prefix, uint32_t rresp, unsigned char parities[8][8],
-          uint32_t odd, uint32_t even, struct Crypto1State* sl, uint8_t no_chk)
+static struct Crypto1State* check_pfx_parity(uint32_t prefix, uint32_t rresp, uint8_t parities[8][8], uint32_t odd, uint32_t even, struct Crypto1State* sl)
 {
-	struct Crypto1State s;
-	uint32_t ks1, nr, ks2, rr, ks3, good, c;
+	uint32_t ks1, nr, ks2, rr, ks3, c, good = 1;
 
-	for(c = 0; c < 8; ++c) {
-		s.odd = odd ^ fastfwd[1][c];
-		s.even = even ^ fastfwd[0][c];
+	for(c = 0; good && c < 8; ++c) {
+		sl->odd = odd ^ fastfwd[1][c];
+		sl->even = even ^ fastfwd[0][c];
 
-		lfsr_rollback_bit(&s, 0, 0);
-		lfsr_rollback_bit(&s, 0, 0);
-		lfsr_rollback_bit(&s, 0, 0);
+		lfsr_rollback_bit(sl, 0, 0);
+		lfsr_rollback_bit(sl, 0, 0);
 
-		lfsr_rollback_word(&s, 0, 0);
-		lfsr_rollback_word(&s, prefix | c << 5, 1);
+		ks3 = lfsr_rollback_bit(sl, 0, 0);
+		ks2 = lfsr_rollback_word(sl, 0, 0);
+		ks1 = lfsr_rollback_word(sl, prefix | c << 5, 1);
 
-		sl->odd = s.odd;
-		sl->even = s.even;
-
-		if (no_chk)
-			break;
-
-		ks1 = crypto1_word(&s, prefix | c << 5, 1);
-		ks2 = crypto1_word(&s,0,0);
-		ks3 = crypto1_word(&s, 0,0);
 		nr = ks1 ^ (prefix | c << 5);
 		rr = ks2 ^ rresp;
 
-		good = 1;
 		good &= parity(nr & 0x000000ff) ^ parities[c][3] ^ BIT(ks2, 24);
 		good &= parity(rr & 0xff000000) ^ parities[c][4] ^ BIT(ks2, 16);
 		good &= parity(rr & 0x00ff0000) ^ parities[c][5] ^ BIT(ks2,  8);
 		good &= parity(rr & 0x0000ff00) ^ parities[c][6] ^ BIT(ks2,  0);
-		good &= parity(rr & 0x000000ff) ^ parities[c][7] ^ BIT(ks3, 24);
-
-		if(!good)
-			return sl;
+		good &= parity(rr & 0x000000ff) ^ parities[c][7] ^ ks3;
 	}
 
-	return ++sl;
+	return sl + good;
 }
 
-
 /** lfsr_common_prefix
  * Implentation of the common prefix attack.
  * Requires the 28 bit constant prefix used as reader nonce (pfx)
@@ -536,8 +511,8 @@ brute_top(uint32_t prefix, uint32_t rresp, unsigned char parities[8][8],
  * It returns a zero terminated list of possible cipher states after the
  * tag nonce was fed in
  */
-struct Crypto1State*
-lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8], uint8_t no_par)
+
+struct Crypto1State* lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8])
 {
 	struct Crypto1State *statelist, *s;
 	uint32_t *odd, *even, *o, *e, top;
@@ -545,29 +520,25 @@ lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8],
 	odd = lfsr_prefix_ks(ks, 1);
 	even = lfsr_prefix_ks(ks, 0);
 
-	statelist = malloc((sizeof *statelist) << 21);	//how large should be?
-	if(!statelist || !odd || !even)
-	{
-				free(statelist);
-				free(odd);
-				free(even);
-				return 0;
+	s = statelist = malloc((sizeof *statelist) << 21);
+	if(!s || !odd || !even) {
+		free(statelist);
+		free(odd);
+		free(even);
+		return 0;
 	}
 
-	s = statelist;
-	for(o = odd; *o != -1; ++o)
-		for(e = even; *e != -1; ++e)
+	for(o = odd; *o + 1; ++o)
+		for(e = even; *e + 1; ++e)
 			for(top = 0; top < 64; ++top) {
-				*o = (*o & 0x1fffff) | (top << 21);
-				*e = (*e & 0x1fffff) | (top >> 3) << 21;
-				s = brute_top(pfx, rr, par, *o, *e, s, no_par);
+				*o += 1 << 21;
+				*e += (!(top & 7) + 1) << 21;
+				s = check_pfx_parity(pfx, rr, par, *o, *e, s);
 			}
 
-	s->odd = s->even = -1;
-	//printf("state count = %d\n",s-statelist);
+	s->odd = s->even = 0;
 
 	free(odd);
 	free(even);
-
 	return statelist;
-}
+}
\ No newline at end of file