Changeset 1117


Ignore:
Timestamp:
Jan 31, 2010, 7:01:00 PM (12 years ago)
Author:
Sven Rech
Message:

new splitting algorithm for KeyPatternPool, which is needed for peer2peer

Location:
trunk/CrypPlugins/KeySearcher
Files:
1 added
3 edited

Legend:

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

    r1069 r1117  
    2626    public class KeyPattern
    2727    {
    28         #region private Wildcard class
    29         private class Wildcard
    30         {
    31             private char[] values = new char[256];
    32             private int length;
    33             private int counter;
    34             public bool isSplit
    35             {
    36                 get;
    37                 private set;
    38             }
    39 
    40             public Wildcard(string valuePattern)
    41             {
    42                 isSplit = false;
    43                 counter = 0;
    44                 if (valuePattern.Length == 1)
    45                 {                   
    46                     length = 1;
    47                     values[0] = valuePattern[0];
    48                 }
    49                 else
    50                 {                   
    51                     length = 0;
    52                     int i = 1;
    53                     while (valuePattern[i] != ']')
    54                     {
    55                         if (valuePattern[i + 1] == '-')
    56                         {
    57                             for (char c = valuePattern[i]; c <= valuePattern[i + 2]; c++)
    58                                 values[length++] = c;
    59                             i += 2;
    60                         }
    61                         else
    62                             values[length++] = valuePattern[i];
    63                         i++;
    64                     }
    65                 }
    66             }
    67 
    68             public Wildcard(Wildcard wc)
    69             {
    70                 isSplit = wc.isSplit;
    71                 length = wc.length;
    72                 counter = wc.counter;
    73                 for (int i = 0; i < 256; i++)
    74                     values[i] = wc.values[i];
    75             }
    76 
    77             private Wildcard()
    78             {
    79             }
    80 
    81             public Wildcard[] split()
    82             {
    83                 if (length <= 1)
    84                     return null;
    85                 int length1 = this.length - this.counter;
    86                 Wildcard[] wcs = new Wildcard[2];
    87                 wcs[0] = new Wildcard();
    88                 wcs[0].counter = 0;
    89                 wcs[0].length = length1 / 2;
    90                 wcs[1] = new Wildcard();
    91                 wcs[1].counter = 0;
    92                 wcs[1].length = length1 - wcs[0].length;
    93                 for (int i = 0; i < wcs[0].length; i++)
    94                     wcs[0].values[i] = values[this.counter + i];
    95                 for (int i = 0; i < wcs[1].length; i++)
    96                     wcs[1].values[i] = values[i + this.counter + wcs[0].length];
    97                 wcs[0].isSplit = true;
    98                 wcs[1].isSplit = true;
    99                 return wcs;
    100             }
    101 
    102             public char getChar()
    103             {
    104                 return values[counter];
    105             }
    106 
    107             public char getChar(int add)
    108             {
    109                 return values[(counter + add) % length];
    110             }
    111 
    112             public bool succ()
    113             {
    114                 counter++;
    115                 if (counter >= length)
    116                 {
    117                     counter = 0;
    118                     return true;
    119                 }
    120                 return false;
    121             }
    122 
    123             public int size()
    124             {
    125                 return length;
    126             }
    127 
    128 
    129             public int count()
    130             {
    131                 return counter;
    132             }
    133 
    134             public void resetCounter()
    135             {
    136                 counter = 0;
    137             }
    138 
    139             public string getRepresentationString()
    140             {
    141                 if (length == 1)
    142                     return "" + values[0];
    143                 string res = "[";
    144                 int begin = 0;
    145                 for (int i = 1; i < length; i++)
    146                 {
    147                     if (values[i - 1] != values[i] - 1)
    148                     {
    149                         if (begin == i - 1)
    150                             res += values[begin];
    151                         else
    152                         {
    153                             if (i - 1 - begin == 1)
    154                                 res += values[begin] + "" + values[i - 1];
    155                             else
    156                                 res += values[begin] + "-" + values[i - 1];
    157                         }
    158                         begin = i;
    159                     }
    160                 }
    161                 if (begin == length - 1)
    162                     res += values[begin];
    163                 else
    164                 {
    165                     if (length - 1 - begin == 1)
    166                         res += values[begin] + "" + values[length - 1];
    167                     else
    168                         res += values[begin] + "-" + values[length - 1];
    169                 }
    170 
    171                 res += "]";
    172                 return res;
    173             }
    174 
    175             public bool contains(Wildcard wc)
    176             {
    177                 if (wc == null)
    178                     return false;
    179                 for (int i = 0; i < wc.length; i++)
    180                 {
    181                     bool contains = false;
    182                     for (int j = 0; j < this.length; j++)
    183                     {
    184                         if (this.values[j] == wc.values[i])
    185                         {
    186                             contains = true;
    187                             break;
    188                         }
    189                     }
    190                     if (!contains)
    191                         return false;
    192                 }
    193                 return true;
    194             }
    195         }
    196         #endregion
    197 
    19828        private string pattern;
    199         private ArrayList wildcardList;
     29        internal ArrayList wildcardList;
     30
    20031        /// <summary>
    20132        /// Property for the WildCardKey. Could return null, if the KeyPattern isn't initialized correctly.
     
    22051                throw new Exception("Invalid pattern!");
    22152            this.pattern = pattern;
    222         }
     53        }       
    22354
    22455        public KeyPattern[] split()
  • trunk/CrypPlugins/KeySearcher/KeyPatternPool.cs

    r1116 r1117  
    44using System.Text;
    55using Cryptool.PluginBase.Miscellaneous;
     6using System.Collections;
    67
    78namespace KeySearcher
    89{
     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     **/
    914    class KeyPatternPool
    1015    {
    1116        private BigInteger partsize;
    12         private Stack<KeyPattern> stack;
     17        private KeyPattern pattern;
     18        private Stack<KeyPattern> stack = new Stack<KeyPattern>();
     19        private int[] splittingQuotient;
     20        private int[] splittingCounter;
     21        private bool end = false;               
    1322
    14         private void makePool(KeyPattern pattern)
     23        /*private BigInteger calculateSplitting(int i)
    1524        {
    16             if (pattern.size() > partsize)
     25            //This method is better, but too slow :(
     26            if (i >= pattern.wildcardList.Count)           
     27                return getPartSize();
     28
     29            int best = 0;
     30            BigInteger bestval = -1;
     31            int c = ((Wildcard)pattern.wildcardList[i]).size();
     32            if (c == 1)
    1733            {
    18                 KeyPattern[] patterns = pattern.split();
    19                 stack.Push(patterns[1]);
    20                 makePool(patterns[0]);
     34                splittingQuotient[i] = 1;
     35                return calculateSplitting(i + 1);
    2136            }
    22             else
     37            for (int k = 1; k <= c; k++)
     38                if (c % k == 0)
     39                {
     40                    splittingQuotient[i] = k;
     41                    BigInteger res = calculateSplitting(i + 1);
     42                    if ((bestval == -1) || ((res-partsize).abs() < (bestval-partsize).abs()))
     43                    {
     44                        bestval = res;
     45                        best = k;
     46                    }
     47                }
     48            splittingQuotient[i] = best;
     49            calculateSplitting(i + 1);
     50            return bestval;
     51        }*/
     52
     53        private void calculateSplitting()
     54        {
     55            for (int c = pattern.wildcardList.Count - 1; c >= 0; c--)
     56                splittingQuotient[c] = 1;
     57
     58            BigInteger bestSize = getPartSize();
     59
     60            for (int c = pattern.wildcardList.Count - 1; c >= 0; c--)
    2361            {
    24                 stack.Push(pattern);               
     62                for (int k = 1; k <= c; k++)
     63                {
     64                    int d = ((Wildcard)pattern.wildcardList[c]).size();
     65                    if (d % k == 0)
     66                    {
     67                        int tmp = splittingQuotient[c];
     68                        splittingQuotient[c] = d;
     69                        BigInteger size = getPartSize();
     70                        if ((size - partsize).abs() < (bestSize - partsize).abs())                       
     71                            bestSize = size;                       
     72                        else
     73                            splittingQuotient[c] = tmp;
     74                    }
     75                }
    2576            }
    2677        }
     78               
     79        private bool succCounter()
     80        {
     81            for (int k = pattern.wildcardList.Count-1; k >= 0; k--)
     82            {
     83                Wildcard wc = ((Wildcard)pattern.wildcardList[k]);
     84                splittingCounter[k]++;
     85                if (splittingCounter[k] >= splittingQuotient[k])
     86                    splittingCounter[k] = 0;
     87                else
     88                    return true;
     89            }
     90            return false;
     91        }
    2792
    28         public KeyPattern getNext()
     93        public bool contains(KeyPattern pattern)
    2994        {
    30             if (stack.Count == 0)
     95            if (pattern.wildcardList.Count != this.pattern.wildcardList.Count)
     96                return false;
     97            if (pattern.GetPattern() != this.pattern.GetPattern())
     98                return false;
     99
     100            for (int k = 0; k < pattern.wildcardList.Count; k++)
     101            {
     102                Wildcard wc = ((Wildcard)pattern.wildcardList[k]);
     103                Wildcard thiswc = ((Wildcard)this.pattern.wildcardList[k]);
     104                if (wc.size() != (thiswc.size() / splittingQuotient[k]))
     105                    return false;
     106
     107                bool contains2 = true;
     108                for (int j = 0; j < splittingQuotient[k]; j++)
     109                {
     110                    bool contains = true;
     111                    for (int i = 0; i < wc.size(); i++)
     112                    {
     113                        if (wc.getChar(i - wc.count()) != thiswc.getChar(i + j * wc.size()))
     114                        {
     115                            contains = false;
     116                            break;
     117                        }
     118                    }
     119                    if (contains)
     120                    {
     121                        contains2 = true;
     122                        break;
     123                    }
     124                }
     125                if (!contains2)
     126                    return false;
     127
     128            }
     129            return true;
     130        }
     131
     132        public void push(KeyPattern pattern)
     133        {
     134            if (!contains(pattern))
     135                stack.Push(pattern);
     136            else
     137                throw new Exception("Pattern already given.");
     138        }
     139
     140        public KeyPattern pop()
     141        {
     142            if (stack.Count != 0)
     143                return (KeyPattern)stack.Pop();
     144
     145            if (end)
    31146                return null;
    32147
    33             KeyPattern top = stack.Pop();
    34             if (top.size() > partsize)
     148            KeyPattern part = new KeyPattern(pattern.GetPattern());
     149            part.wildcardList = new ArrayList();
     150            for (int k = 0; k < pattern.wildcardList.Count; k++)
     151            {               
     152                Wildcard wc = ((Wildcard)pattern.wildcardList[k]);
     153                char[] values = new char[256];
     154                int length = wc.size() / splittingQuotient[k];
     155                for (int i = 0; i < length; i++)
     156                    values[i] = wc.getChar(i + splittingCounter[k] * length);
     157                Wildcard newwc = new Wildcard(values, length);
     158                part.wildcardList.Add(newwc);
     159            }
     160
     161            if (!succCounter())
     162                end = true;
     163
     164            return part;
     165        }
     166
     167        public BigInteger getPartSize()
     168        {
     169            BigInteger res = 1;
     170            for (int k = 0; k < pattern.wildcardList.Count; k++)
    35171            {
    36                 KeyPattern[] patterns = top.split();
    37                 stack.Push(patterns[1]);
    38                 stack.Push(patterns[0]);
    39                 return getNext();
     172                Wildcard wc = ((Wildcard)pattern.wildcardList[k]);
     173                res *= wc.size() / splittingQuotient[k];
    40174            }
    41             else
    42                 return top;
     175            return res;
    43176        }
    44177
     
    46179        {
    47180            this.partsize = partsize;
    48             stack = new Stack<KeyPattern>();
    49             makePool(pattern);
     181            this.pattern = pattern;
     182            splittingQuotient = new int[pattern.wildcardList.Count];
     183            calculateSplitting();
     184            splittingCounter = new int[pattern.wildcardList.Count];
    50185        }
    51186    }
  • trunk/CrypPlugins/KeySearcher/KeySearcher.csproj

    r1116 r1117  
    6767    <Compile Include="KeySearcherSettings.cs" />
    6868    <Compile Include="Properties\AssemblyInfo.cs" />
     69    <Compile Include="Wildcard.cs" />
    6970  </ItemGroup>
    7071  <ItemGroup>
Note: See TracChangeset for help on using the changeset viewer.