Ignore:
Timestamp:
Nov 27, 2009, 4:19:42 PM (12 years ago)
Author:
Sven Rech
Message:

sourced out KeyPattern class

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/CrypPlugins/KeySearcher/KeySearcher.cs

    r866 r905  
    1515namespace KeySearcher
    1616{
    17     public class KeyPattern
    18     {
    19         private class Wildcard
    20         {
    21             private char[] values = new char[256];
    22             private int length;
    23             private int counter;
    24             public bool isSplit
    25             {
    26                 get;
    27                 private set;
    28             }
    29            
    30             public Wildcard(string valuePattern)
    31             {
    32                 isSplit = false;
    33                 counter = 0;
    34                 length = 0;
    35                 int i = 1;
    36                 while (valuePattern[i] != ']')
    37                 {
    38                     if (valuePattern[i + 1] == '-')
    39                     {
    40                         for (char c = valuePattern[i]; c <= valuePattern[i + 2]; c++)
    41                             values[length++] = c;
    42                         i += 2;
    43                     }
    44                     else
    45                         values[length++] = valuePattern[i];
    46                     i++;
    47                 }
    48             }
    49 
    50             public Wildcard(Wildcard wc)
    51             {
    52                 isSplit = wc.isSplit;
    53                 length = wc.length;
    54                 counter = wc.counter;
    55                 for (int i = 0; i < 256; i++)
    56                     values[i] = wc.values[i];
    57             }
    58 
    59             private Wildcard()
    60             {
    61             }
    62 
    63             public Wildcard[] split()
    64             {
    65                 int length = this.length - this.counter;
    66                 Wildcard[] wcs = new Wildcard[2];
    67                 wcs[0] = new Wildcard();
    68                 wcs[0].counter = 0;
    69                 wcs[0].length = length / 2;
    70                 wcs[1] = new Wildcard();
    71                 wcs[1].counter = 0;
    72                 wcs[1].length = length - wcs[0].length;
    73                 for (int i = 0; i < wcs[0].length; i++)
    74                     wcs[0].values[i] = values[this.counter + i];
    75                 for (int i = 0; i < wcs[1].length; i++)
    76                     wcs[1].values[i] = values[i + this.counter + wcs[0].length];
    77                 wcs[0].isSplit = true;
    78                 wcs[1].isSplit = true;
    79                 return wcs;
    80             }
    81 
    82             public char getChar()
    83             {
    84                 return values[counter];
    85             }
    86 
    87             public char getChar(int add)
    88             {
    89                 return values[(counter+add)%length];
    90             }
    91 
    92             public bool succ()
    93             {
    94                 counter++;
    95                 if (counter >= length)
    96                 {
    97                     counter = 0;
    98                     return true;
    99                 }
    100                 return false;
    101             }
    102 
    103             public int size()
    104             {
    105                 return length;
    106             }
    107 
    108 
    109             public int count()
    110             {
    111                 return counter;
    112             }
    113 
    114             public void resetCounter()
    115             {
    116                 counter = 0;
    117             }
    118         }
    119 
    120         private string pattern;
    121         private string key;       
    122         private ArrayList wildcardList;
    123 
    124         public KeyPattern(string pattern)
    125         {
    126             this.pattern = pattern;
    127         }
    128 
    129         public KeyPattern[] split()
    130         {
    131             KeyPattern[] patterns = new KeyPattern[2];
    132             for (int i = 0; i < 2; i++)
    133             {
    134                 patterns[i] = new KeyPattern(pattern);
    135                 patterns[i].key = key;
    136                 patterns[i].wildcardList = new ArrayList();
    137             }
    138             bool s = false;
    139             for (int i = 0; i < wildcardList.Count; i++)
    140             {
    141                 Wildcard wc = ((Wildcard)wildcardList[i]);
    142                 if (!s && (wc.size() - wc.count()) > 1)
    143                 {
    144                     Wildcard[] wcs = wc.split();
    145                     patterns[0].wildcardList.Add(wcs[0]);
    146                     patterns[1].wildcardList.Add(wcs[1]);
    147                     s = true;
    148                 }
    149                 else
    150                 {
    151                     patterns[0].wildcardList.Add(new Wildcard(wc));
    152                     Wildcard copy = new Wildcard(wc);
    153                     if (s)
    154                         copy.resetCounter();
    155                     patterns[1].wildcardList.Add(copy);
    156                 }
    157             }
    158             if (!s)
    159                 throw new Exception("Can't be split!");
    160             return patterns;
    161         }
    162 
    163         public string giveWildcardKey()
    164         {
    165             string res = "";
    166             int i = 0;
    167             while (i < pattern.Length)
    168             {
    169                 if (pattern[i] != '[')
    170                     res += pattern[i];
    171                 else
    172                 {
    173                     res += '*';
    174                     while (pattern[i] != ']')
    175                         i++;
    176                 }
    177                 i++;
    178             }
    179             return res;
    180         }
    181 
    182         public bool testKey(string key)
    183         {
    184             int kcount = 0;
    185             int pcount = 0;
    186             while (kcount < key.Length && pcount < pattern.Length)
    187             {
    188                 if (pattern[pcount] != '[')
    189                 {
    190                     if (key[kcount] != '*' && pattern[pcount] != key[kcount])
    191                         return false;
    192                     kcount++;
    193                     pcount++;
    194                 }
    195                 else
    196                 {
    197                     bool contains = false;
    198                     pcount++;
    199                     while (pattern[pcount] != ']')
    200                     {
    201                         if (key[kcount] != '*')
    202                         {
    203                             if (pattern[pcount + 1] == '-')
    204                             {
    205                                 if (key[kcount] >= pattern[pcount] && key[kcount] <= pattern[pcount + 2])
    206                                     contains = true;
    207                                 pcount += 2;
    208                             }
    209                             else
    210                                 if (pattern[pcount] == key[kcount])
    211                                     contains = true;
    212                         }
    213                         pcount++;
    214                     }
    215                     if (!contains && !(key[kcount] == '*'))
    216                         return false;
    217                     kcount++;
    218                     pcount++;
    219                 }               
    220             }
    221             if (pcount != pattern.Length || kcount != key.Length)
    222                 return false;
    223             return true;
    224         }
    225 
    226         public BigInteger initKeyIteration(string key)
    227         {
    228             BigInteger counter = 1;
    229             this.key = key;
    230             int pcount = 0;
    231             wildcardList = new ArrayList();
    232             for (int i = 0; i < key.Length; i++)
    233             {
    234                 if (key[i] == '*')
    235                 {
    236                     Wildcard wc = new Wildcard(pattern.Substring(pcount, pattern.IndexOf(']', pcount) + 1 - pcount));
    237                     wildcardList.Add(wc);
    238                     counter *= wc.size();
    239                 }
    240 
    241                 if (pattern[pcount] == '[')
    242                     while (pattern[pcount] != ']')
    243                         pcount++;
    244                 pcount++;
    245             }
    246             return counter;
    247         }
    248 
    249         public BigInteger size()
    250         {
    251             if (wildcardList == null)
    252                 return 0;
    253             BigInteger counter = 1;
    254             foreach (Wildcard wc in wildcardList)
    255                     counter *= wc.size();
    256             return counter;
    257         }
    258 
    259         /** used to jump to the next Key.         
    260          * if nextWildcard == -1, we return false
    261          * if nextWildcard == -2, we return true
    262          * if nextWildcard == -3, we increase the rightmost wildcard
    263          * if nextWildcard >= 0, we increase the wildcard on the position 'nextWildcard'
    264          * returns false if there is no key left.
    265          */
    266         public bool nextKey(int nextWildcard)
    267         {
    268             if (nextWildcard == -2)
    269                 return true;
    270             if (nextWildcard == -1)
    271                 return false;
    272 
    273             int wildcardCount;
    274             if (nextWildcard == -3)
    275                 wildcardCount = wildcardList.Count - 1;
    276             else
    277                 wildcardCount = nextWildcard;
    278             bool overflow = ((Wildcard)wildcardList[wildcardCount]).succ();
    279             wildcardCount--;
    280             while (overflow && (wildcardCount >= 0))
    281                 overflow = ((Wildcard)wildcardList[wildcardCount--]).succ();
    282             return !overflow;
    283         }
    284 
    285         public string getKey()
    286         {
    287             string res = "";
    288             int wildcardCount = 0;
    289             for (int i = 0; i < key.Length; i++)
    290             {
    291                 if (key[i] != '*')
    292                     res += key[i];
    293                 else
    294                 {
    295                     Wildcard wc = (Wildcard)wildcardList[wildcardCount++];
    296                     res += wc.getChar();
    297                 }
    298             }
    299             return res;
    300         }
    301 
    302         public string getKey(int add)
    303         {
    304             string res = "";
    305             int div = 1;
    306             int wildcardCount = wildcardList.Count-1;
    307             for (int i = key.Length-1; i >= 0; i--)
    308             {
    309                 if (key[i] != '*')
    310                     res += key[i];
    311                 else
    312                 {
    313                     Wildcard wc = (Wildcard)wildcardList[wildcardCount--];
    314                     if (add < div)
    315                         res += wc.getChar();
    316                     else
    317                     {
    318                         res += wc.getChar((add / div) % wc.size());
    319                         div *= wc.size();
    320                     }
    321                 }
    322             }
    323             char[] r = res.ToCharArray();
    324             Array.Reverse(r);
    325             return new string(r);
    326         }
    327 
    328         public string getKeyBlock(ref int blocksize, ref int nextWildcard)
    329         {
    330             const int MAXSIZE = 65536;
    331             //find out how many wildcards we can group together:
    332             blocksize = 1;
    333             int pointer;
    334             for (pointer = wildcardList.Count - 1; pointer >= 0; pointer--)
    335             {
    336                 Wildcard wc = (Wildcard)wildcardList[pointer];
    337                 if (wc.isSplit || wc.count() != 0 || blocksize*wc.size() > MAXSIZE)               
    338                     break;
    339                 else
    340                     blocksize *= wc.size();
    341             }           
    342 
    343             if (pointer >= wildcardList.Count)
    344                 return null;
    345 
    346             nextWildcard = pointer;           
    347 
    348             //generate key:
    349             string res = "";
    350             int wildcardCount = 0;
    351             for (int i = 0; i < key.Length; i++)
    352             {
    353                 if (key[i] != '*')
    354                     res += key[i];
    355                 else
    356                 {
    357                     if (pointer < wildcardCount)
    358                         res += "*";
    359                     else
    360                     {
    361                         Wildcard wc = (Wildcard)wildcardList[wildcardCount++];
    362                         res += wc.getChar();
    363                     }
    364                 }
    365             }
    366             return res;
    367         }
    368 
    369     }
    370    
    37117    [Author("Thomas Schmid", "thomas.schmid@cryptool.org", "Uni Siegen", "http://www.uni-siegen.de")]
    37218    //[Author("Sven Rech", "rech@cryptool.org", "Uni Duisburg-Essen", "http://www.uni-due.de")]
Note: See TracChangeset for help on using the changeset viewer.