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

Last change on this file since 1932 was 1932, checked in by Sven Rech, 11 years ago

removed an optimization in keysearcher plugin, that didn't worked anymore and wasn't used anymore.
code is now more readable.

I will replace this by a much better optimization approach later (master project)

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