source: trunk/CrypPlugins/KeySearcher/KeyPatternPool.cs @ 1169

Last change on this file since 1169 was 1169, checked in by Sven Rech, 12 years ago

fixed keypatternpool

File size: 6.5 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4using System.Text;
5using Cryptool.PluginBase.Miscellaneous;
6using System.Collections;
7using Cryptool.Plugins.PeerToPeer.Jobs;
8
9namespace KeySearcher
10{
11    /**
12     * This class is able to split a KeyPattern into several disjunct parts, which are guaranteed to have equal size.
13     * It tries to split the pattern in such a way, that the parts have nearly the given partsize.
14     **/
15    public class KeyPatternPool
16    {
17        private BigInteger partsize;
18        private BigInteger counter = 0;
19        private KeyPattern pattern;
20        private Stack<KeyPattern> stack = new Stack<KeyPattern>();
21        private int[] splittingQuotient;
22        private int[] splittingCounter;
23        private bool end = false;
24
25        private void CalculateSplitting()
26        {
27            for (int c = pattern.wildcardList.Count - 1; c >= 0; c--)
28                splittingQuotient[c] = 1;
29
30            BigInteger bestSize = GetPartSize();
31
32            for (int c = pattern.wildcardList.Count - 1; c >= 0; c--)
33            {
34                int d = ((Wildcard)pattern.wildcardList[c]).size();
35                for (int k = 1; k <= d; k++)
36                {                   
37                    if (d % k == 0)
38                    {
39                        int tmp = splittingQuotient[c];
40                        splittingQuotient[c] = k;
41                        BigInteger size = GetPartSize();
42                        if ((size - partsize).abs() < (bestSize - partsize).abs())                       
43                            bestSize = size;                       
44                        else
45                            splittingQuotient[c] = tmp;
46                    }
47                }
48            }
49        }
50               
51        private bool SuccCounter()
52        {
53            for (int k = pattern.wildcardList.Count-1; k >= 0; k--)
54            {
55                Wildcard wc = ((Wildcard)pattern.wildcardList[k]);
56                splittingCounter[k]++;
57                if (splittingCounter[k] >= splittingQuotient[k])
58                    splittingCounter[k] = 0;
59                else
60                    return true;
61            }
62            return false;
63        }
64
65        // added by Arnie - 2010.02.04
66        public bool Contains(byte[] serializedJob)
67        {
68            KeyPattern deserializedPattern = new KeyPattern(serializedJob);
69            return Contains(deserializedPattern);
70        }
71
72        public bool Contains(KeyPattern pattern)
73        {
74            if (pattern.wildcardList.Count != this.pattern.wildcardList.Count)
75                return false;
76            if (pattern.GetPattern() != this.pattern.GetPattern())
77                return false;
78
79            bool equal = true;
80            for (int k = 0; k < pattern.wildcardList.Count; k++)
81            {
82                Wildcard wc = ((Wildcard)pattern.wildcardList[k]);
83                Wildcard thiswc = ((Wildcard)this.pattern.wildcardList[k]);
84                if (wc.size() != (thiswc.size() / splittingQuotient[k]))
85                    return false;
86               
87                bool bolContains2 = true;
88                int begin = equal ? splittingCounter[k] : 0;
89                for (int j = begin; j < splittingQuotient[k]; j++)
90                {
91                    bool bolContains = true;
92                    for (int i = 0; i < wc.size(); i++)
93                    {
94                        if (wc.getChar(i - wc.count()) != thiswc.getChar(i + j * wc.size()))
95                        {
96                            bolContains = false;
97                            break;
98                        }
99                    }
100                    if (bolContains)
101                    {                       
102                        equal = (j == splittingCounter[k]);
103                        bolContains2 = true;
104                        break;
105                    }
106                }
107                if (!bolContains2)
108                    return false;
109
110            }
111            return !equal;
112        }
113
114        public void Push(KeyPattern pattern)
115        {
116            counter--;
117            if (!Contains(pattern))
118                stack.Push(pattern);
119            else
120                throw new Exception("Pattern already given.");
121        }
122
123        public KeyPattern Pop()
124        {
125            if (stack.Count != 0)
126            {
127                counter++;
128                return (KeyPattern)stack.Pop();
129            }
130
131            if (end)
132                return null;           
133
134            KeyPattern part = new KeyPattern(pattern.GetPattern());
135            part.wildcardList = new ArrayList();
136            for (int k = 0; k < pattern.wildcardList.Count; k++)
137            {               
138                Wildcard wc = ((Wildcard)pattern.wildcardList[k]);
139                char[] values = new char[256];
140                int length = wc.size() / splittingQuotient[k];
141                for (int i = 0; i < length; i++)
142                    values[i] = wc.getChar(i + splittingCounter[k] * length);
143                Wildcard newwc = new Wildcard(values, length);
144                part.wildcardList.Add(newwc);
145            }
146
147            if (!SuccCounter())
148                end = true;
149
150            counter++;
151            return part;
152        }
153
154        public BigInteger GetPartSize()
155        {
156            BigInteger res = 1;
157            for (int k = 0; k < pattern.wildcardList.Count; k++)
158            {
159                Wildcard wc = ((Wildcard)pattern.wildcardList[k]);
160                res *= wc.size() / splittingQuotient[k];
161            }
162            return res;
163        }
164
165        public long Count()
166        {
167            return (TotalAmount() + stack.Count - counter).LongValue();
168        }
169
170        public BigInteger TotalAmount()
171        {
172            BigInteger res = 1;
173            for (int k = 0; k < pattern.wildcardList.Count; k++)
174            {
175                Wildcard wc = ((Wildcard)pattern.wildcardList[k]);
176                res *= splittingQuotient[k];
177            }
178            return res;
179        }
180
181        public KeyPatternPool(KeyPattern pattern, BigInteger partsize)
182        {
183            this.partsize = partsize;
184            this.pattern = pattern;
185            splittingQuotient = new int[pattern.wildcardList.Count];
186            CalculateSplitting();
187            splittingCounter = new int[pattern.wildcardList.Count];
188        }
189    }
190}
Note: See TracBrowser for help on using the repository browser.