source: trunk/CrypPlugins/KeySearcher/KeyPattern.cs @ 1448

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

replaced all BigInteger stuff with the new BigInteger class from .net 4.0

But there are still problems with some plugins (Keysearcher, BigInteger Operations...)

File size: 20.4 KB
Line 
1/*                             
2   Copyright 2009 Team CrypTool (Sven Rech,Dennis Nolte,Raoul Falk,Nils Kopal), Uni Duisburg-Essen
3
4   Licensed under the Apache License, Version 2.0 (the "License");
5   you may not use this file except in compliance with the License.
6   You may obtain a copy of the License at
7
8       http://www.apache.org/licenses/LICENSE-2.0
9
10   Unless required by applicable law or agreed to in writing, software
11   distributed under the License is distributed on an "AS IS" BASIS,
12   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   See the License for the specific language governing permissions and
14   limitations under the License.
15*/
16
17using System;
18using System.Collections.Generic;
19using System.Linq;
20using System.Text;
21using Cryptool.PluginBase.Miscellaneous;
22using System.Collections;
23using Cryptool.Plugins.PeerToPeer.Jobs;
24using System.IO;
25using System.Numerics;
26
27namespace KeySearcher
28{
29    public class KeyPattern
30    {       
31        private string pattern;
32        internal ArrayList wildcardList;
33
34        /// <summary>
35        /// Property for the WildCardKey. Could return null, if the KeyPattern isn't initialized correctly.
36        /// </summary>
37        public string WildcardKey
38        {
39            get
40            {
41                return getWildcardKey();
42            }
43            set
44            {
45                if (!testWildcardKey(value))
46                    throw new Exception("Invalid wildcard key!");
47                setWildcardKey(value);
48            }
49        }
50
51        public KeyPattern(string pattern)
52        {
53            if (!testPattern(pattern))
54                throw new Exception("Invalid pattern!");
55            this.pattern = pattern;
56        }       
57
58        public KeyPattern[] split()
59        {
60            KeyPattern[] patterns = new KeyPattern[2];
61            for (int i = 0; i < 2; i++)
62            {
63                patterns[i] = new KeyPattern(pattern);               
64                patterns[i].wildcardList = new ArrayList();
65            }
66            bool s = false;
67            for (int i = 0; i < wildcardList.Count; i++)
68            {
69                Wildcard wc = ((Wildcard)wildcardList[i]);
70                if (!s && (wc.size() - wc.count()) > 1)
71                {
72                    Wildcard[] wcs = wc.split();
73                    patterns[0].wildcardList.Add(wcs[0]);
74                    patterns[1].wildcardList.Add(wcs[1]);                   
75                    s = true;
76                }
77                else
78                {
79                    patterns[0].wildcardList.Add(new Wildcard(wc));
80                    Wildcard copy = new Wildcard(wc);
81                    if (s)
82                        copy.resetCounter();
83                    patterns[1].wildcardList.Add(copy);
84                }
85            }
86            if (!s)
87                return null;
88            return patterns;
89        }
90
91        public string giveInputPattern()
92        {
93            string res = "";
94            int i = 0;
95            while (i < pattern.Length)
96            {
97                if (pattern[i] != '[')
98                    res += pattern[i];
99                else
100                {
101                    res += '*';
102                    while (pattern[i] != ']')
103                        i++;
104                }
105                i++;
106            }
107            return res;
108        }
109
110        /**
111         * tests, if 'pattern' is a valid pattern.
112         **/
113        public static bool testPattern(string pattern)
114        {
115            int i = 0;
116            while (i < pattern.Length)
117            {
118                if (pattern[i] == '[')
119                {
120                    i++;
121                    while (pattern[i] != ']')
122                    {
123                        if (specialChar(pattern[i]))
124                            return false;
125                        if (pattern[i + 1] == '-')
126                        {
127                            if (specialChar(pattern[i]) || specialChar(pattern[i + 2]))
128                                return false;
129                            i += 2;
130                        }
131                        i++;
132                    }
133                }
134                i++;
135            }
136            return true;
137        }
138
139        private static bool specialChar(char p)
140        {
141            if (p == '-' || p == '[' || p == ']' || p == '*')
142                return true;
143            return false;
144        }
145
146        /**
147         * tests, if 'wildcardKey' matches 'pattern'.
148         **/
149        public static bool testWildcardKey(string wildcardKey, string pattern)
150        {
151            try
152            {
153                int kcount = 0;
154                int pcount = 0;
155                while (kcount < wildcardKey.Length && pcount < pattern.Length)
156                {
157                    if (pattern[pcount] != '[')
158                    {
159                        if (pattern[pcount] != wildcardKey[kcount])
160                            return false;
161                        kcount++;
162                        pcount++;
163                    }
164                    else
165                    {
166                        Wildcard wc1 = new Wildcard(pattern.Substring(pcount, pattern.IndexOf(']', pcount) + 1 - pcount));
167                        while (pattern[pcount++] != ']') ;
168                        Wildcard wc2 = null;
169                        if (wildcardKey[kcount] == '[')
170                        {
171                            wc2 = new Wildcard(wildcardKey.Substring(kcount, wildcardKey.IndexOf(']', kcount) + 1 - kcount));
172                            while (wildcardKey[++kcount] != ']') ;
173                        }
174                        else if (wildcardKey[kcount] != '*')
175                            wc2 = new Wildcard("" + wildcardKey[kcount]);
176
177                        if (!wc1.contains(wc2) && !(wildcardKey[kcount] == '*'))
178                            return false;
179                        kcount++;
180                    }
181                }
182                if (pcount != pattern.Length || kcount != wildcardKey.Length)
183                    return false;
184                return true;
185            }
186            catch (Exception)
187            {
188                return false;
189            }
190        }
191
192        public bool testWildcardKey(string wildcardKey)
193        {
194            return testWildcardKey(wildcardKey, pattern);
195        }
196
197        private void setWildcardKey(string wildcardKey)
198        {         
199            int pcount = 0;
200            wildcardList = new ArrayList();
201            int i = 0;
202            while (i < wildcardKey.Length)           
203            {
204                if (pattern[pcount] == '[')
205                {
206                    if (wildcardKey[i] == '*')
207                    {
208                        Wildcard wc = new Wildcard(pattern.Substring(pcount, pattern.IndexOf(']', pcount) + 1 - pcount));
209                        wildcardList.Add(wc);
210                      }
211                    else if (wildcardKey[i] == '[')
212                    {
213                        Wildcard wc = new Wildcard(wildcardKey.Substring(i, wildcardKey.IndexOf(']', i) + 1 - i));
214                        wildcardList.Add(wc);
215                        while (wildcardKey[++i] != ']') ;
216                    }
217                    else
218                    {
219                        Wildcard wc = new Wildcard("" + wildcardKey[i]);
220                        wildcardList.Add(wc);
221                    }
222                    while (pattern[++pcount] != ']') ;
223                }
224                pcount++;
225                i++;
226            }
227        }
228
229        private string getWildcardKey()
230        {
231            string res = "";
232            int pcount = 0;
233            int wccount = 0;
234
235            // error handling
236            if (wildcardList != null)
237            {
238                while (pcount < pattern.Length)
239                {
240                    if (pattern[pcount] != '[')
241                        res += pattern[pcount];
242                    else
243                    {
244                        res += ((Wildcard)wildcardList[wccount++]).getRepresentationString();
245                        while (pattern[++pcount] != ']') ;
246                    }
247                    pcount++;
248                }
249                return res;
250            }
251            else
252                return null;
253        }
254
255        public BigInteger size()
256        {
257            if (wildcardList == null)
258                return 0;
259            BigInteger counter = 1;
260            foreach (Wildcard wc in wildcardList)
261                counter *= wc.size();
262            return counter;
263        }
264
265        /** used to jump to the next Key.         
266         * if nextWildcard == -1, we return false
267         * if nextWildcard == -2, we return true
268         * if nextWildcard == -3, we increase the rightmost wildcard
269         * if nextWildcard >= 0, we increase the wildcard on the position 'nextWildcard'
270         * returns false if there is no key left.
271         */
272        public bool nextKey(int nextWildcard)
273        {
274            if (nextWildcard == -2)
275                return true;
276            if (nextWildcard == -1)
277                return false;
278
279            int wildcardCount;
280            if (nextWildcard == -3)
281                wildcardCount = wildcardList.Count - 1;
282            else
283                wildcardCount = nextWildcard;
284            bool overflow = ((Wildcard)wildcardList[wildcardCount--]).succ();           
285            while (overflow && (wildcardCount >= 0))
286                overflow = ((Wildcard)wildcardList[wildcardCount--]).succ();
287            return !overflow;
288        }
289
290        public string getKey()
291        {
292            string res = "";
293            int wildcardCount = 0;
294            int i = 0;
295            while (i < pattern.Length)           
296            {
297                if (pattern[i] != '[')
298                    res += pattern[i++];
299                else
300                {
301                    Wildcard wc = (Wildcard)wildcardList[wildcardCount++];
302                    res += wc.getChar();
303                    while (pattern[i++] != ']') ;
304                }               
305            }
306            return res;
307        }
308
309        public string getKey(int add)
310        {
311            string res = "";
312            int div = 1;
313            int wildcardCount = wildcardList.Count - 1;
314            int i = pattern.Length - 1;
315            while (i >= 0)           
316            {
317                if (pattern[i] != ']')
318                    res += pattern[i--];
319                else
320                {
321                    Wildcard wc = (Wildcard)wildcardList[wildcardCount--];
322                    if (add < div)
323                        res += wc.getChar();
324                    else
325                    {
326                        res += wc.getChar((add / div) % wc.size());
327                        div *= wc.size();
328                    }
329                    while (pattern[i--] != '[') ;
330                }
331            }
332            char[] r = res.ToCharArray();
333            Array.Reverse(r);
334            return new string(r);
335        }
336
337        public string getKeyBlock(ref int blocksize, ref int nextWildcard)
338        {
339            const int MAXSIZE = 65536;
340            //find out how many wildcards we can group together:
341            blocksize = 1;
342            int pointer;
343            for (pointer = wildcardList.Count - 1; pointer >= 0; pointer--)
344            {
345                Wildcard wc = (Wildcard)wildcardList[pointer];
346                if (wc.isSplit || wc.count() != 0 || blocksize * wc.size() > MAXSIZE)
347                    break;
348                else
349                    blocksize *= wc.size();
350            }
351
352            if (pointer >= wildcardList.Count)
353                return null;
354
355            nextWildcard = pointer;
356
357            //generate key:
358            string res = "";
359            int wildcardCount = 0;
360            int i = 0;
361            while (i < pattern.Length)
362            {
363                if (pattern[i] != '[')
364                    res += pattern[i++];
365                else
366                {
367                    if (pointer < wildcardCount)
368                        res += "*";
369                    else
370                    {
371                        Wildcard wc = (Wildcard)wildcardList[wildcardCount++];
372                        res += wc.getChar();
373                    }
374                    while (pattern[i++] != ']') ;
375                }
376            }
377            return res;
378        }       
379
380         /*
381         * ARNIES SANDKASTEN - ALLE FOLGENDEN METHODEN SIND FÜR DIE VERTEILTE VERWENDUNG
382         * DES KEYPATTERNS NOTWENDIG ODER ABER EINFACH UM DAS KEYPATTERN SCHÖN ALS
383         * GUILOGMESSAGE AUSGEBEN ZU KÖNNEN ;-)
384         */
385
386        // Added by Arnold - 2010.02.04
387        public KeyPattern(byte[] serializedPattern)
388        {
389            KeyPattern deserializedPattern = Deserialize(serializedPattern);
390            // set deserialized Pattern to actual pattern
391            this.pattern = deserializedPattern.pattern;
392            this.WildcardKey = deserializedPattern.WildcardKey;
393            //this.wildcardList = deserializedPattern.wildcardList;
394            if (deserializedPattern == null)
395                throw new Exception("Invalid byte[] representation of KeyPattern!");
396        }
397
398        //added by Christian Arnold - 2009.12.02
399        /// <summary>
400        /// returns type, key and pattern. If you want to get only the pattern for processing use GetPattern-method!
401        /// </summary>
402        /// <returns></returns>
403        public override string ToString()
404        {
405            if(this.WildcardKey != null)
406                return "Type: KeySearcher.KeyPattern. WildcardKey: '" + this.WildcardKey + "', Pattern: '" + this.pattern + "'";
407            else
408                return "Type: KeySearcher.KeyPattern. KeyPattern isn't initialized correctly, Pattern: '" + this.pattern + "'";
409        }
410
411        //added by Christian Arnold - 2009.12.03
412        /// <summary>
413        /// returns ONLY the pattern as a string!
414        /// </summary>
415        /// <returns></returns>
416        public string GetPattern()
417        {
418            return this.pattern;
419        }
420
421        #region Serialization methods and auxiliary variables
422
423        /* Serialization information:
424         * 1st byte: Byte-Length of the WildCardKey
425         * 2nd - wildcardLen: WildCardKey Byte representation
426         * wildcardLen + 1: Byte-Length of the Pattern
427         * wildcardLen + 2 - wildcardLen+2+patternLen: Pattern Byte representation
428         *  -------------------------------------------------------------
429         * | wildcardkey length | wildcardkey | pattern length | pattern |
430         *  -------------------------------------------------------------  */
431        private Encoding encoder = UTF8Encoding.UTF8;
432
433        /// <summary>
434        /// Serialize all needful information to rebuild the existing pattern elsewhere
435        /// </summary>
436        /// <returns>byte representation of all the needful information of the actual KeyPattern</returns>
437        public byte[] Serialize()
438        {
439            byte[] retByte;
440            string wildcardKey = this.WildcardKey;
441            if (wildcardKey != null && this.pattern != null)
442            {
443                if (testWildcardKey(wildcardKey))
444                {
445                    byte[] byteWildCard = encoder.GetBytes(wildcardKey);
446                    byte[] bytePattern = encoder.GetBytes(pattern);
447                    byte[] byteWildCardLen = BitConverter.GetBytes(byteWildCard.Length);
448                    byte[] bytePatternLen = BitConverter.GetBytes(bytePattern.Length);
449                    MemoryStream memStream = new MemoryStream();
450                    try
451                    {
452                        memStream.Write(byteWildCardLen, 0, byteWildCardLen.Length);
453                        memStream.Write(byteWildCard, 0, byteWildCard.Length);
454                        memStream.Write(bytePatternLen, 0, bytePatternLen.Length);
455                        memStream.Write(bytePattern, 0, bytePattern.Length);
456                        retByte = memStream.ToArray();
457                    }
458                    catch (Exception ex)
459                    {
460                        throw ex;
461                    }
462                    finally
463                    {
464                        memStream.Flush();
465                        memStream.Close();
466                        memStream.Dispose();
467                    }
468                    //retByte = new byte[byteWildCardLen.Length + byteWildCard.Length + bytePatternLen.Length + bytePattern.Length];
469                    //Buffer.BlockCopy(byteWildCardLen, 0, retByte, 0, byteWildCardLen.Length);
470                    //Buffer.BlockCopy(byteWildCard, 0, retByte, byteWildCard.Length, byteWildCard.Length);
471                    //retByte[byteWildCard.Length + 1] = (byte)bytePattern.Length;
472                    //Buffer.BlockCopy(bytePattern, 0, retByte, byteWildCard.Length + 2, bytePattern.Length);
473                }
474                else
475                {
476                    throw (new Exception("Serializing KeyPattern canceled, because WildcardKey and/or Pattern aren't valid. "
477                        + "WildcardKey: '" + wildcardKey + "', Pattern: '" + pattern + "'.\n"));
478                }
479            }
480            else
481            {
482                throw (new Exception("Serializing KeyPattern canceled, because Key and/or Pattern are NULL. WildcardKey: '" + wildcardKey + "'. Pattern: '" + pattern + "'."));
483            }
484            return retByte;
485        }
486
487        /// <summary>
488        /// Deserialize a byte-representation of an KeyPattern object. Returns a full-initialized KeyPattern object.
489        /// </summary>
490        /// <param name="serializedPattern">byte-representation of an keypattern object</param>
491        /// <returns>a full-initialized KeyPattern object</returns>
492        public KeyPattern Deserialize(byte[] serializedPattern)
493        {
494            KeyPattern keyPatternToReturn;
495            string wildcardKey_temp;
496            string pattern_temp;
497
498            MemoryStream memStream = new MemoryStream(serializedPattern);
499            try
500            {
501                /* So i always have the same byte length for int32 values */
502                int iTest = 500;
503                int int32ByteLen = BitConverter.GetBytes(iTest).Length;
504
505                // Wildcard length and value
506                byte[] byteLen = new byte[int32ByteLen];
507                memStream.Read(byteLen, 0, byteLen.Length);
508                byte[] byteWildcard = new byte[BitConverter.ToInt32(byteLen, 0)];
509                memStream.Read(byteWildcard, 0, byteWildcard.Length);
510
511                wildcardKey_temp = encoder.GetString(byteWildcard, 0, byteWildcard.Length);
512
513
514                // Pattern length and value
515                memStream.Read(byteLen, 0, byteLen.Length);
516                byte[] bytePattern = new byte[BitConverter.ToInt32(byteLen, 0)];
517                memStream.Read(bytePattern, 0, bytePattern.Length);
518
519                pattern_temp = encoder.GetString(bytePattern, 0, bytePattern.Length);
520
521            }
522            catch (Exception ex)
523            {
524                throw ex;
525            }
526            finally
527            {
528                memStream.Flush();
529                memStream.Close();
530                memStream.Dispose();
531            }
532
533            //int iWildCardLen = serializedPattern[0];
534            //wildcardKey_temp = encoder.GetString(serializedPattern, 1, iWildCardLen);
535            //int iPatternLen = serializedPattern[iWildCardLen + 1];
536            //pattern_temp = encoder.GetString(serializedPattern, iWildCardLen + 2, iPatternLen);
537
538            keyPatternToReturn = new KeyPattern(pattern_temp);
539            // test extracted pattern and wildcardKey!
540            if (keyPatternToReturn.testWildcardKey(wildcardKey_temp))
541            {
542                keyPatternToReturn.WildcardKey = wildcardKey_temp;
543                return keyPatternToReturn;
544            }
545            else
546            {
547                throw (new Exception("Deserializing KeyPattern canceled, because WildcardKey or Pattern aren't valid. "
548                    + "WildcardKey: '" + wildcardKey_temp + "', Pattern: '" + pattern_temp + "'.\n"));
549            }
550        }
551
552        #endregion
553
554    }
555}
Note: See TracBrowser for help on using the repository browser.