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

Last change on this file since 1122 was 1122, checked in by arnold, 12 years ago

Special problem fixed

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