]> git.zerfleddert.de Git - proxmark3-svn/blame_incremental - client/nonce2key/crapto1.c
Merge pull request #80 from marshmellow42/master
[proxmark3-svn] / client / nonce2key / crapto1.c
... / ...
CommitLineData
1/* crapto1.c\r
2\r
3 This program is free software; you can redistribute it and/or\r
4 modify it under the terms of the GNU General Public License\r
5 as published by the Free Software Foundation; either version 2\r
6 of the License, or (at your option) any later version.\r
7\r
8 This program is distributed in the hope that it will be useful,\r
9 but WITHOUT ANY WARRANTY; without even the implied warranty of\r
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\r
11 GNU General Public License for more details.\r
12\r
13 You should have received a copy of the GNU General Public License\r
14 along with this program; if not, write to the Free Software\r
15 Foundation, Inc., 51 Franklin Street, Fifth Floor,\r
16 Boston, MA 02110-1301, US$\r
17\r
18 Copyright (C) 2008-2008 bla <blapost@gmail.com>\r
19*/\r
20#include "crapto1.h"\r
21#include <stdlib.h>\r
22\r
23#if !defined LOWMEM && defined __GNUC__\r
24static uint8_t filterlut[1 << 20];\r
25static void __attribute__((constructor)) fill_lut()\r
26{\r
27 uint32_t i;\r
28 for(i = 0; i < 1 << 20; ++i)\r
29 filterlut[i] = filter(i);\r
30}\r
31#define filter(x) (filterlut[(x) & 0xfffff])\r
32#endif\r
33\r
34\r
35\r
36typedef struct bucket {\r
37 uint32_t *head;\r
38 uint32_t *bp;\r
39} bucket_t;\r
40\r
41typedef bucket_t bucket_array_t[2][0x100];\r
42\r
43typedef struct bucket_info {\r
44 struct {\r
45 uint32_t *head, *tail;\r
46 } bucket_info[2][0x100];\r
47 uint32_t numbuckets;\r
48 } bucket_info_t;\r
49\r
50\r
51static void bucket_sort_intersect(uint32_t* const estart, uint32_t* const estop,\r
52 uint32_t* const ostart, uint32_t* const ostop,\r
53 bucket_info_t *bucket_info, bucket_array_t bucket)\r
54{\r
55 uint32_t *p1, *p2;\r
56 uint32_t *start[2];\r
57 uint32_t *stop[2];\r
58\r
59 start[0] = estart;\r
60 stop[0] = estop;\r
61 start[1] = ostart;\r
62 stop[1] = ostop;\r
63\r
64 // init buckets to be empty\r
65 for (uint32_t i = 0; i < 2; i++) {\r
66 for (uint32_t j = 0x00; j <= 0xff; j++) {\r
67 bucket[i][j].bp = bucket[i][j].head;\r
68 }\r
69 }\r
70\r
71 // sort the lists into the buckets based on the MSB (contribution bits)\r
72 for (uint32_t i = 0; i < 2; i++) {\r
73 for (p1 = start[i]; p1 <= stop[i]; p1++) {\r
74 uint32_t bucket_index = (*p1 & 0xff000000) >> 24;\r
75 *(bucket[i][bucket_index].bp++) = *p1;\r
76 }\r
77 }\r
78\r
79\r
80 // write back intersecting buckets as sorted list.\r
81 // fill in bucket_info with head and tail of the bucket contents in the list and number of non-empty buckets.\r
82 uint32_t nonempty_bucket;\r
83 for (uint32_t i = 0; i < 2; i++) {\r
84 p1 = start[i];\r
85 nonempty_bucket = 0;\r
86 for (uint32_t j = 0x00; j <= 0xff; j++) {\r
87 if (bucket[0][j].bp != bucket[0][j].head && bucket[1][j].bp != bucket[1][j].head) { // non-empty intersecting buckets only\r
88 bucket_info->bucket_info[i][nonempty_bucket].head = p1;\r
89 for (p2 = bucket[i][j].head; p2 < bucket[i][j].bp; *p1++ = *p2++);\r
90 bucket_info->bucket_info[i][nonempty_bucket].tail = p1 - 1;\r
91 nonempty_bucket++;\r
92 }\r
93 }\r
94 bucket_info->numbuckets = nonempty_bucket;\r
95 }\r
96}\r
97\r
98/** binsearch\r
99 * Binary search for the first occurence of *stop's MSB in sorted [start,stop]\r
100 */\r
101static inline uint32_t*\r
102binsearch(uint32_t *start, uint32_t *stop)\r
103{\r
104 uint32_t mid, val = *stop & 0xff000000;\r
105 while(start != stop)\r
106 if(start[mid = (stop - start) >> 1] > val)\r
107 stop = &start[mid];\r
108 else\r
109 start += mid + 1;\r
110\r
111 return start;\r
112}\r
113\r
114/** update_contribution\r
115 * helper, calculates the partial linear feedback contributions and puts in MSB\r
116 */\r
117static inline void\r
118update_contribution(uint32_t *item, const uint32_t mask1, const uint32_t mask2)\r
119{\r
120 uint32_t p = *item >> 25;\r
121\r
122 p = p << 1 | parity(*item & mask1);\r
123 p = p << 1 | parity(*item & mask2);\r
124 *item = p << 24 | (*item & 0xffffff);\r
125}\r
126\r
127/** extend_table\r
128 * using a bit of the keystream extend the table of possible lfsr states\r
129 */\r
130static inline void\r
131extend_table(uint32_t *tbl, uint32_t **end, int bit, int m1, int m2, uint32_t in)\r
132{\r
133 in <<= 24;\r
134\r
135 for(uint32_t *p = tbl; p <= *end; p++) {\r
136 *p <<= 1;\r
137 if(filter(*p) != filter(*p | 1)) { // replace\r
138 *p |= filter(*p) ^ bit;\r
139 update_contribution(p, m1, m2);\r
140 *p ^= in;\r
141 } else if(filter(*p) == bit) { // insert\r
142 *++*end = p[1];\r
143 p[1] = p[0] | 1;\r
144 update_contribution(p, m1, m2);\r
145 *p++ ^= in;\r
146 update_contribution(p, m1, m2);\r
147 *p ^= in;\r
148 } else { // drop\r
149 *p-- = *(*end)--;\r
150 }\r
151 }\r
152\r
153}\r
154\r
155\r
156/** extend_table_simple\r
157 * using a bit of the keystream extend the table of possible lfsr states\r
158 */\r
159static inline void\r
160extend_table_simple(uint32_t *tbl, uint32_t **end, int bit)\r
161{\r
162 for(*tbl <<= 1; tbl <= *end; *++tbl <<= 1)\r
163 if(filter(*tbl) ^ filter(*tbl | 1)) { // replace\r
164 *tbl |= filter(*tbl) ^ bit;\r
165 } else if(filter(*tbl) == bit) { // insert\r
166 *++*end = *++tbl;\r
167 *tbl = tbl[-1] | 1;\r
168 } else // drop\r
169 *tbl-- = *(*end)--;\r
170}\r
171\r
172\r
173/** recover\r
174 * recursively narrow down the search space, 4 bits of keystream at a time\r
175 */\r
176static struct Crypto1State*\r
177recover(uint32_t *o_head, uint32_t *o_tail, uint32_t oks,\r
178 uint32_t *e_head, uint32_t *e_tail, uint32_t eks, int rem,\r
179 struct Crypto1State *sl, uint32_t in, bucket_array_t bucket)\r
180{\r
181 uint32_t *o, *e;\r
182 bucket_info_t bucket_info;\r
183\r
184 if(rem == -1) {\r
185 for(e = e_head; e <= e_tail; ++e) {\r
186 *e = *e << 1 ^ parity(*e & LF_POLY_EVEN) ^ !!(in & 4);\r
187 for(o = o_head; o <= o_tail; ++o, ++sl) {\r
188 sl->even = *o;\r
189 sl->odd = *e ^ parity(*o & LF_POLY_ODD);\r
190 }\r
191 }\r
192 sl->odd = sl->even = 0;\r
193 return sl;\r
194 }\r
195\r
196 for(uint32_t i = 0; i < 4 && rem--; i++) {\r
197 extend_table(o_head, &o_tail, (oks >>= 1) & 1,\r
198 LF_POLY_EVEN << 1 | 1, LF_POLY_ODD << 1, 0);\r
199 if(o_head > o_tail)\r
200 return sl;\r
201\r
202 extend_table(e_head, &e_tail, (eks >>= 1) & 1,\r
203 LF_POLY_ODD, LF_POLY_EVEN << 1 | 1, (in >>= 2) & 3);\r
204 if(e_head > e_tail)\r
205 return sl;\r
206 }\r
207\r
208 bucket_sort_intersect(e_head, e_tail, o_head, o_tail, &bucket_info, bucket);\r
209\r
210 for (int i = bucket_info.numbuckets - 1; i >= 0; i--) {\r
211 sl = recover(bucket_info.bucket_info[1][i].head, bucket_info.bucket_info[1][i].tail, oks,\r
212 bucket_info.bucket_info[0][i].head, bucket_info.bucket_info[0][i].tail, eks,\r
213 rem, sl, in, bucket);\r
214 }\r
215\r
216 return sl;\r
217}\r
218/** lfsr_recovery\r
219 * recover the state of the lfsr given 32 bits of the keystream\r
220 * additionally you can use the in parameter to specify the value\r
221 * that was fed into the lfsr at the time the keystream was generated\r
222 */\r
223struct Crypto1State* lfsr_recovery32(uint32_t ks2, uint32_t in)\r
224{\r
225 struct Crypto1State *statelist;\r
226 uint32_t *odd_head = 0, *odd_tail = 0, oks = 0;\r
227 uint32_t *even_head = 0, *even_tail = 0, eks = 0;\r
228 int i;\r
229\r
230 // split the keystream into an odd and even part\r
231 for(i = 31; i >= 0; i -= 2)\r
232 oks = oks << 1 | BEBIT(ks2, i);\r
233 for(i = 30; i >= 0; i -= 2)\r
234 eks = eks << 1 | BEBIT(ks2, i);\r
235\r
236 odd_head = odd_tail = malloc(sizeof(uint32_t) << 21);\r
237 even_head = even_tail = malloc(sizeof(uint32_t) << 21);\r
238 statelist = malloc(sizeof(struct Crypto1State) << 18);\r
239 if(!odd_tail-- || !even_tail-- || !statelist) {\r
240 goto out;\r
241 }\r
242 statelist->odd = statelist->even = 0;\r
243\r
244 // allocate memory for out of place bucket_sort\r
245 bucket_array_t bucket;\r
246 for (uint32_t i = 0; i < 2; i++)\r
247 for (uint32_t j = 0; j <= 0xff; j++) {\r
248 bucket[i][j].head = malloc(sizeof(uint32_t)<<14);\r
249 if (!bucket[i][j].head) {\r
250 goto out;\r
251 }\r
252 }\r
253\r
254\r
255 // initialize statelists: add all possible states which would result into the rightmost 2 bits of the keystream\r
256 for(i = 1 << 20; i >= 0; --i) {\r
257 if(filter(i) == (oks & 1))\r
258 *++odd_tail = i;\r
259 if(filter(i) == (eks & 1))\r
260 *++even_tail = i;\r
261 }\r
262\r
263 // extend the statelists. Look at the next 8 Bits of the keystream (4 Bit each odd and even):\r
264 for(i = 0; i < 4; i++) {\r
265 extend_table_simple(odd_head, &odd_tail, (oks >>= 1) & 1);\r
266 extend_table_simple(even_head, &even_tail, (eks >>= 1) & 1);\r
267 }\r
268\r
269 // the statelists now contain all states which could have generated the last 10 Bits of the keystream.\r
270 // 22 bits to go to recover 32 bits in total. From now on, we need to take the "in"\r
271 // parameter into account.\r
272\r
273 in = (in >> 16 & 0xff) | (in << 16) | (in & 0xff00); // Byte swapping\r
274\r
275 recover(odd_head, odd_tail, oks,\r
276 even_head, even_tail, eks, 11, statelist, in << 1, bucket);\r
277\r
278\r
279out:\r
280 free(odd_head);\r
281 free(even_head);\r
282 for (uint32_t i = 0; i < 2; i++)\r
283 for (uint32_t j = 0; j <= 0xff; j++)\r
284 free(bucket[i][j].head);\r
285\r
286 return statelist;\r
287}\r
288\r
289static const uint32_t S1[] = { 0x62141, 0x310A0, 0x18850, 0x0C428, 0x06214,\r
290 0x0310A, 0x85E30, 0xC69AD, 0x634D6, 0xB5CDE, 0xDE8DA, 0x6F46D, 0xB3C83,\r
291 0x59E41, 0xA8995, 0xD027F, 0x6813F, 0x3409F, 0x9E6FA};\r
292static const uint32_t S2[] = { 0x3A557B00, 0x5D2ABD80, 0x2E955EC0, 0x174AAF60,\r
293 0x0BA557B0, 0x05D2ABD8, 0x0449DE68, 0x048464B0, 0x42423258, 0x278192A8,\r
294 0x156042D0, 0x0AB02168, 0x43F89B30, 0x61FC4D98, 0x765EAD48, 0x7D8FDD20,\r
295 0x7EC7EE90, 0x7F63F748, 0x79117020};\r
296static const uint32_t T1[] = {\r
297 0x4F37D, 0x279BE, 0x97A6A, 0x4BD35, 0x25E9A, 0x12F4D, 0x097A6, 0x80D66,\r
298 0xC4006, 0x62003, 0xB56B4, 0x5AB5A, 0xA9318, 0xD0F39, 0x6879C, 0xB057B,\r
299 0x582BD, 0x2C15E, 0x160AF, 0x8F6E2, 0xC3DC4, 0xE5857, 0x72C2B, 0x39615,\r
300 0x98DBF, 0xC806A, 0xE0680, 0x70340, 0x381A0, 0x98665, 0x4C332, 0xA272C};\r
301static const uint32_t T2[] = { 0x3C88B810, 0x5E445C08, 0x2982A580, 0x14C152C0,\r
302 0x4A60A960, 0x253054B0, 0x52982A58, 0x2FEC9EA8, 0x1156C4D0, 0x08AB6268,\r
303 0x42F53AB0, 0x217A9D58, 0x161DC528, 0x0DAE6910, 0x46D73488, 0x25CB11C0,\r
304 0x52E588E0, 0x6972C470, 0x34B96238, 0x5CFC3A98, 0x28DE96C8, 0x12CFC0E0,\r
305 0x4967E070, 0x64B3F038, 0x74F97398, 0x7CDC3248, 0x38CE92A0, 0x1C674950,\r
306 0x0E33A4A8, 0x01B959D0, 0x40DCACE8, 0x26CEDDF0};\r
307static const uint32_t C1[] = { 0x846B5, 0x4235A, 0x211AD};\r
308static const uint32_t C2[] = { 0x1A822E0, 0x21A822E0, 0x21A822E0};\r
309/** Reverse 64 bits of keystream into possible cipher states\r
310 * Variation mentioned in the paper. Somewhat optimized version\r
311 */\r
312struct Crypto1State* lfsr_recovery64(uint32_t ks2, uint32_t ks3)\r
313{\r
314 struct Crypto1State *statelist, *sl;\r
315 uint8_t oks[32], eks[32], hi[32];\r
316 uint32_t low = 0, win = 0;\r
317 uint32_t *tail, table[1 << 16];\r
318 int i, j;\r
319\r
320 sl = statelist = malloc(sizeof(struct Crypto1State) << 4);\r
321 if(!sl)\r
322 return 0;\r
323 sl->odd = sl->even = 0;\r
324\r
325 for(i = 30; i >= 0; i -= 2) {\r
326 oks[i >> 1] = BIT(ks2, i ^ 24);\r
327 oks[16 + (i >> 1)] = BIT(ks3, i ^ 24);\r
328 }\r
329 for(i = 31; i >= 0; i -= 2) {\r
330 eks[i >> 1] = BIT(ks2, i ^ 24);\r
331 eks[16 + (i >> 1)] = BIT(ks3, i ^ 24);\r
332 }\r
333\r
334 for(i = 0xfffff; i >= 0; --i) {\r
335 if (filter(i) != oks[0])\r
336 continue;\r
337\r
338 *(tail = table) = i;\r
339 for(j = 1; tail >= table && j < 29; ++j)\r
340 extend_table_simple(table, &tail, oks[j]);\r
341\r
342 if(tail < table)\r
343 continue;\r
344\r
345 for(j = 0; j < 19; ++j)\r
346 low = low << 1 | parity(i & S1[j]);\r
347 for(j = 0; j < 32; ++j)\r
348 hi[j] = parity(i & T1[j]);\r
349\r
350 for(; tail >= table; --tail) {\r
351 for(j = 0; j < 3; ++j) {\r
352 *tail = *tail << 1;\r
353 *tail |= parity((i & C1[j]) ^ (*tail & C2[j]));\r
354 if(filter(*tail) != oks[29 + j])\r
355 goto continue2;\r
356 }\r
357\r
358 for(j = 0; j < 19; ++j)\r
359 win = win << 1 | parity(*tail & S2[j]);\r
360\r
361 win ^= low;\r
362 for(j = 0; j < 32; ++j) {\r
363 win = win << 1 ^ hi[j] ^ parity(*tail & T2[j]);\r
364 if(filter(win) != eks[j])\r
365 goto continue2;\r
366 }\r
367\r
368 *tail = *tail << 1 | parity(LF_POLY_EVEN & *tail);\r
369 sl->odd = *tail ^ parity(LF_POLY_ODD & win);\r
370 sl->even = win;\r
371 ++sl;\r
372 sl->odd = sl->even = 0;\r
373 continue2:;\r
374 }\r
375 }\r
376 return statelist;\r
377}\r
378\r
379/** lfsr_rollback_bit\r
380 * Rollback the shift register in order to get previous states\r
381 */\r
382void lfsr_rollback_bit(struct Crypto1State *s, uint32_t in, int fb)\r
383{\r
384 int out;\r
385 uint32_t tmp;\r
386\r
387 s->odd &= 0xffffff;\r
388 tmp = s->odd;\r
389 s->odd = s->even;\r
390 s->even = tmp;\r
391\r
392 out = s->even & 1;\r
393 out ^= LF_POLY_EVEN & (s->even >>= 1);\r
394 out ^= LF_POLY_ODD & s->odd;\r
395 out ^= !!in;\r
396 out ^= filter(s->odd) & !!fb;\r
397\r
398 s->even |= parity(out) << 23;\r
399}\r
400/** lfsr_rollback_byte\r
401 * Rollback the shift register in order to get previous states\r
402 */\r
403void lfsr_rollback_byte(struct Crypto1State *s, uint32_t in, int fb)\r
404{\r
405 int i;\r
406 for (i = 7; i >= 0; --i)\r
407 lfsr_rollback_bit(s, BEBIT(in, i), fb);\r
408}\r
409/** lfsr_rollback_word\r
410 * Rollback the shift register in order to get previous states\r
411 */\r
412void lfsr_rollback_word(struct Crypto1State *s, uint32_t in, int fb)\r
413{\r
414 int i;\r
415 for (i = 31; i >= 0; --i)\r
416 lfsr_rollback_bit(s, BEBIT(in, i), fb);\r
417}\r
418\r
419/** nonce_distance\r
420 * x,y valid tag nonces, then prng_successor(x, nonce_distance(x, y)) = y\r
421 */\r
422static uint16_t *dist = 0;\r
423int nonce_distance(uint32_t from, uint32_t to)\r
424{\r
425 uint16_t x, i;\r
426 if(!dist) {\r
427 dist = malloc(2 << 16);\r
428 if(!dist)\r
429 return -1;\r
430 for (x = i = 1; i; ++i) {\r
431 dist[(x & 0xff) << 8 | x >> 8] = i;\r
432 x = x >> 1 | (x ^ x >> 2 ^ x >> 3 ^ x >> 5) << 15;\r
433 }\r
434 }\r
435 return (65535 + dist[to >> 16] - dist[from >> 16]) % 65535;\r
436}\r
437\r
438\r
439static uint32_t fastfwd[2][8] = {\r
440 { 0, 0x4BC53, 0xECB1, 0x450E2, 0x25E29, 0x6E27A, 0x2B298, 0x60ECB},\r
441 { 0, 0x1D962, 0x4BC53, 0x56531, 0xECB1, 0x135D3, 0x450E2, 0x58980}};\r
442\r
443\r
444/** lfsr_prefix_ks\r
445 *\r
446 * Is an exported helper function from the common prefix attack\r
447 * Described in the "dark side" paper. It returns an -1 terminated array\r
448 * of possible partial(21 bit) secret state.\r
449 * The required keystream(ks) needs to contain the keystream that was used to\r
450 * encrypt the NACK which is observed when varying only the 4 last bits of Nr\r
451 * only correct iff [NR_3] ^ NR_3 does not depend on Nr_3\r
452 */\r
453uint32_t *lfsr_prefix_ks(uint8_t ks[8], int isodd)\r
454{\r
455 uint32_t *candidates = malloc(4 << 21);\r
456 uint32_t c, entry;\r
457 int size, i;\r
458\r
459 if(!candidates)\r
460 return 0;\r
461\r
462 size = (1 << 21) - 1;\r
463 for(i = 0; i <= size; ++i)\r
464 candidates[i] = i;\r
465\r
466 for(c = 0; c < 8; ++c)\r
467 for(i = 0;i <= size; ++i) {\r
468 entry = candidates[i] ^ fastfwd[isodd][c];\r
469\r
470 if(filter(entry >> 1) == BIT(ks[c], isodd))\r
471 if(filter(entry) == BIT(ks[c], isodd + 2))\r
472 continue;\r
473\r
474 candidates[i--] = candidates[size--];\r
475 }\r
476\r
477 candidates[size + 1] = -1;\r
478\r
479 return candidates;\r
480}\r
481\r
482/** brute_top\r
483 * helper function which eliminates possible secret states using parity bits\r
484 */\r
485static struct Crypto1State*\r
486brute_top(uint32_t prefix, uint32_t rresp, unsigned char parities[8][8],\r
487 uint32_t odd, uint32_t even, struct Crypto1State* sl, uint8_t no_chk)\r
488{\r
489 struct Crypto1State s;\r
490 uint32_t ks1, nr, ks2, rr, ks3, good, c;\r
491\r
492 for(c = 0; c < 8; ++c) {\r
493 s.odd = odd ^ fastfwd[1][c];\r
494 s.even = even ^ fastfwd[0][c];\r
495\r
496 lfsr_rollback_bit(&s, 0, 0);\r
497 lfsr_rollback_bit(&s, 0, 0);\r
498 lfsr_rollback_bit(&s, 0, 0);\r
499\r
500 lfsr_rollback_word(&s, 0, 0);\r
501 lfsr_rollback_word(&s, prefix | c << 5, 1);\r
502\r
503 sl->odd = s.odd;\r
504 sl->even = s.even;\r
505\r
506 if (no_chk)\r
507 break;\r
508\r
509 ks1 = crypto1_word(&s, prefix | c << 5, 1);\r
510 ks2 = crypto1_word(&s,0,0);\r
511 ks3 = crypto1_word(&s, 0,0);\r
512 nr = ks1 ^ (prefix | c << 5);\r
513 rr = ks2 ^ rresp;\r
514\r
515 good = 1;\r
516 good &= parity(nr & 0x000000ff) ^ parities[c][3] ^ BIT(ks2, 24);\r
517 good &= parity(rr & 0xff000000) ^ parities[c][4] ^ BIT(ks2, 16);\r
518 good &= parity(rr & 0x00ff0000) ^ parities[c][5] ^ BIT(ks2, 8);\r
519 good &= parity(rr & 0x0000ff00) ^ parities[c][6] ^ BIT(ks2, 0);\r
520 good &= parity(rr & 0x000000ff) ^ parities[c][7] ^ BIT(ks3, 24);\r
521\r
522 if(!good)\r
523 return sl;\r
524 }\r
525\r
526 return ++sl;\r
527}\r
528\r
529\r
530/** lfsr_common_prefix\r
531 * Implentation of the common prefix attack.\r
532 * Requires the 28 bit constant prefix used as reader nonce (pfx)\r
533 * The reader response used (rr)\r
534 * The keystream used to encrypt the observed NACK's (ks)\r
535 * The parity bits (par)\r
536 * It returns a zero terminated list of possible cipher states after the\r
537 * tag nonce was fed in\r
538 */\r
539struct Crypto1State*\r
540lfsr_common_prefix(uint32_t pfx, uint32_t rr, uint8_t ks[8], uint8_t par[8][8], uint8_t no_par)\r
541{\r
542 struct Crypto1State *statelist, *s;\r
543 uint32_t *odd, *even, *o, *e, top;\r
544\r
545 odd = lfsr_prefix_ks(ks, 1);\r
546 even = lfsr_prefix_ks(ks, 0);\r
547\r
548 statelist = malloc((sizeof *statelist) << 21); //how large should be?\r
549 if(!statelist || !odd || !even)\r
550 {\r
551 free(statelist);\r
552 free(odd);\r
553 free(even);\r
554 return 0;\r
555 }\r
556\r
557 s = statelist;\r
558 for(o = odd; *o != -1; ++o)\r
559 for(e = even; *e != -1; ++e)\r
560 for(top = 0; top < 64; ++top) {\r
561 *o = (*o & 0x1fffff) | (top << 21);\r
562 *e = (*e & 0x1fffff) | (top >> 3) << 21;\r
563 s = brute_top(pfx, rr, par, *o, *e, s, no_par);\r
564 }\r
565\r
566 s->odd = s->even = -1;\r
567 //printf("state count = %d\n",s-statelist);\r
568\r
569 free(odd);\r
570 free(even);\r
571\r
572 return statelist;\r
573}\r
Impressum, Datenschutz