source: trunk/CrypPlugins/ComputeAnnihilators/ComputeAnnihilators.cs @ 2334

Last change on this file since 2334 was 2334, checked in by Matthäus Wander, 11 years ago

removed 1006 occurences of DisplayLevel in 218 files (see #122)

File size: 38.5 KB
Line 
1using System;
2using System.Collections;
3using System.Collections.Generic;
4using System.Linq;
5using System.Text;
6using Cryptool.PluginBase;
7using Cryptool.PluginBase.Analysis;
8using Cryptool.PluginBase.Cryptography;
9using Cryptool.PluginBase.Miscellaneous;
10using System.Text.RegularExpressions;
11using System.IO;
12using System.ComponentModel;
13using Cryptool.PluginBase.IO;
14using System.Windows.Controls;
15
16namespace Cryptool.ComputeAnnihilators
17{
18    [Author("Abdeljalil Bourbahh", "bourbahh@yahoo.de", "Ruhr-Universitaet Bochum, Chair for System Security", "http://www.trust.rub.de/")]
19    [PluginInfo(false, "Alg.Attack: Compute annihilators", "compute annihilators of Function, Set of bitsquence or a set XZ (Z-functions)", "ComputeAnnihilators/DetailedDescription/Description.xaml",
20 "ComputeAnnihilators/Images/ann.png")]
21    public class ComputeAnnihilators : IAnalysisMisc
22    {
23        #region Private variables
24        private ComputeAnnihilatorsSettings settings;
25        private Object input;
26        private Hashtable outputFZ;
27        private string outputstring;
28        private int dimention;
29        private bool stop = false;
30        private bool start = false;
31        #endregion
32        public ComputeAnnihilators()
33        {
34            this.settings = new ComputeAnnihilatorsSettings();
35
36            ((ComputeAnnihilatorsSettings)(this.settings)).LogMessage += ComputeAnnihilators_LogMessage;
37        }
38        public ISettings Settings
39        {
40            get { return (ISettings)this.settings; }
41            set { this.settings = (ComputeAnnihilatorsSettings)value; }
42        }
43        [PropertyInfo(Direction.InputData, "input as Object", "boolean function (string),set of bisequences(string)or Hashtable (Z,XZ) delivred from pluin copmute th sets XZ", "", false, false, QuickWatchFormat.Text, null)]
44        public Object Input
45        {
46            get { return this.input; }
47            set
48            {
49                if (value != input)
50                {
51                    this.input = value;
52                    OnPropertyChanged("Input");
53                }
54            }
55        }
56
57        [PropertyInfo(Direction.OutputData, "annihilators  as string", "to display annihilators or Z-functions in Textoutput", "", false, false, QuickWatchFormat.Text, null)]
58        public string OutputString
59        {
60            get { return this.outputstring; }
61            set
62            {
63                outputstring = value;
64                OnPropertyChanged("OutputString");
65            }
66
67        }
68        [PropertyInfo(Direction.OutputData, " annihilators as (Hashtable(Z,F_Z))", "to use as Input of Pugin System of equation", "", false, false, QuickWatchFormat.Text, null)]
69        public Hashtable OutputFZ
70        {
71            get { return this.outputFZ; }
72            set
73            {
74                outputFZ = value;
75                OnPropertyChanged("OutputFZ");
76            }
77        }
78        #region IPlugin members
79        public void Initialize()
80        {
81        }
82        public void Dispose()
83        {
84        }
85        public bool HasChanges
86        {
87            get { return settings.HasChanges; }
88            set { settings.HasChanges = value; }
89        }
90        public event PluginProgressChangedEventHandler OnPluginProgressChanged;
91        public event GuiLogNotificationEventHandler OnGuiLogNotificationOccured;
92        private void GuiLogMessage(string message, NotificationLevel logLevel)
93        {
94            EventsHelper.GuiLogMessage(OnGuiLogNotificationOccured, this, new GuiLogEventArgs(message, this, logLevel));
95        }
96        public UserControl Presentation
97        {
98            get { return null; }
99        }
100        public UserControl QuickWatchPresentation
101        {
102            get { return null; }
103        }
104        public void Stop()
105        {
106            if (start && !settings.ComputeEnded && settings.ActionSetting == 0) stop = true;
107        }
108        public void PostExecution()
109        {
110            Dispose();
111        }
112        public void Pause()
113        {
114        }
115        public void PreExecution()
116        {
117            Dispose();
118        }
119        #endregion
120        #region INotifyPropertyChanged Members
121        public event PropertyChangedEventHandler PropertyChanged;
122        public void OnPropertyChanged(string name)
123        {
124            if (PropertyChanged != null)
125            {
126                PropertyChanged(this, new PropertyChangedEventArgs(name));
127            }
128        }
129        private void ComputeAnnihilators_LogMessage(string msg, NotificationLevel logLevel)
130        {
131            if (OnGuiLogNotificationOccured != null)
132            {
133                OnGuiLogNotificationOccured(this, new GuiLogEventArgs(msg, this, logLevel));
134            }
135        }
136        private void ProgressChanged(double value, double max)
137        {
138            EventsHelper.ProgressChanged(OnPluginProgressChanged, this, new PluginProgressEventArgs(value, max));
139        }
140        #endregion
141        #region IPlugin Members
142
143#pragma warning disable 67
144        public event StatusChangedEventHandler OnPluginStatusChanged;
145#pragma warning restore
146        public void Execute()
147        {
148            try
149            {
150                switch (settings.ActionSetting)
151                {
152                    case 0:
153                        CombinerZFunctions();
154                        break;
155                    case 1:
156                        FunctionAnnihilators();
157                        break;
158                    case 2:
159                        BitsequencesetAnnihilators();
160                        break;
161                }
162            }
163            catch (Exception exception)
164            {
165                GuiLogMessage(exception.Message, NotificationLevel.Error);
166            }
167            finally
168            {
169                ProgressChanged(1, 1);
170            }
171        }
172        public void SaveParameter(Hashtable XZ)
173        {
174            ArrayList parameter = (ArrayList)XZ[XZ.Count - 1];
175            string outputfunc = (string)parameter[0];
176            string memUpdfunc = (string)parameter[1];
177            int runlenght = (int)parameter[2];
178            parameter.Remove(XZ.Count - 1);
179            if (IsParameterNew(outputfunc, memUpdfunc, runlenght))
180            {
181                settings.ComputeEnded = false;
182                settings.Savedoutputfunction = outputfunc;
183                settings.Savedmemoryupdatefunction = memUpdfunc;
184                settings.Savedrunlength = runlenght;
185                settings.Saveddegree = settings.Degree;
186            }
187            else
188            {
189                if ((settings.SavedZfunctions != null))
190                {
191                    foreach (DictionaryEntry dicEntry in settings.SavedZfunctions)
192                    {
193                        outputFZ.Add((int)dicEntry.Key, (ArrayList)dicEntry.Value);
194                    }
195                }
196            }
197        }
198        public void CombinerZFunctions()
199        {
200            if (input != null && input.GetType().Equals(typeof(Hashtable)) && settings.OutputSet != null)
201            {
202                if (IsOutputSetvalid(settings.OutputSet))
203                {
204                    Hashtable h = (Hashtable)input;
205                    int[] Zvalue = GetOutputs(settings.OutputSet);
206                    int Xlength = ((bool[])((ArrayList)h[0])[0]).Length;
207                    outputFZ = new Hashtable();
208                    start = true;
209                    stop = false;
210                    SaveParameter(h);
211                    for (int i = 0; i < Zvalue.Length; i++)
212                    {
213                        if (stop)
214                        {
215                            settings.SavedZfunctions = outputFZ;
216                            break;
217                        }
218                        int z = Zvalue[i];
219                        ArrayList Xi = (ArrayList)h[z];
220                        if (!outputFZ.Contains(z))
221                        {
222                            outputstring = "compute F_=" + Bitpresentation(z, settings.OutputSet.Length);
223                            OnPropertyChanged("OutputString");
224                            ArrayList Ahnilators = Computeannihilators(Xi, settings.Degree);
225                            outputFZ.Add(z, Ahnilators);
226                        }
227                    }
228                    if (!stop)
229                    {
230                        switch (settings.OutputSetting)
231                        {
232                            case 0:
233                                DisplayFZ(Zvalue);
234                                break;
235                            case 1:
236                                OnPropertyChanged("OutputFZ");
237                                break;
238                            case 2:
239                                OnPropertyChanged("OutputFZ");
240                                DisplayFZ(Zvalue);
241                                break;
242                        }
243                        settings.ComputeEnded = true;
244                        settings.SavedZfunctions = outputFZ;
245                    }
246                    start = false;
247                }
248            }
249            else
250            {
251                GuiLogMessage("not all mandatory parameters are provided", NotificationLevel.Error);
252            }
253        }
254        public void DisplayFZ(int[] Zvalues)
255        {
256            StringBuilder b = new StringBuilder();
257            b.AppendLine();
258            for (int i = 0; i < Zvalues.Length; i++)
259            {
260                int z = Zvalues[i];
261                b.AppendLine("F_" + Bitpresentation(z, settings.OutputSet.Length));
262                string s = (ToStringAnnihilators((ArrayList)outputFZ[z]));
263                if (s == "") b.AppendLine("F_" + Bitpresentation(z, settings.OutputSet.Length) + " of degree " + settings.Degree + " don't exist ");
264                else b.AppendLine(s);
265            }
266            outputstring = b.ToString();
267            OnPropertyChanged("OutputString");
268        }
269        public bool IsParameterNew(string outputfunction, string memoryupdatefunction, int outputlength)
270        {
271            if (memoryupdatefunction == "")
272            {
273                if (settings.Savedoutputfunction == outputfunction && settings.Savedrunlength == outputlength
274                    && settings.Saveddegree == settings.Degree)
275                    return false;
276            }
277            else
278            {
279                if (settings.Savedoutputfunction == outputfunction && settings.Savedmemoryupdatefunction ==
280                    memoryupdatefunction && settings.Savedrunlength == outputlength && settings.Saveddegree == settings.Degree)
281                    return false;
282            }
283            return true;
284        }
285        private void BitsequencesetAnnihilators()
286        {
287            if (input != null && input.GetType().Equals(typeof(String)))
288            {
289                string seqsetstring = (string)input;
290                if (IsBitSeqSetValid(seqsetstring))
291                {
292                    ArrayList bitseqlist = new ArrayList();
293                    string[] seqsetarray = seqsetstring.Split(',');
294                    int bitseq_length = seqsetarray[0].Length;
295                    for (int k = 0; k < seqsetarray.Length; k++)
296                    {
297                        bool[] bitseq = new bool[bitseq_length];
298                        for (int j = 0; j < bitseq.Length; j++)
299                        {
300                            if (seqsetarray[k].ToCharArray()[j] == '1') bitseq[j] = true;
301                            else bitseq[j] = false;
302                        }
303                        bitseqlist.Add(bitseq);
304                    }
305                    ArrayList annihilators = Computeannihilators(bitseqlist, settings.Degree);
306                    string s = ToStringAnnihilators(annihilators);
307                    if (s == "") outputstring = "no annihilator of degree <= " + settings.Degree + " is located";
308                    else outputstring = "annihilators of the given Set of degree =< " + settings.Degree + "\r\n" + s;
309                    OnPropertyChanged("OutputString");
310                }
311            }
312            else
313            {
314                GuiLogMessage("not all mandatory parameters are provided", NotificationLevel.Error);
315            }
316        }
317        private bool IsOutputSetvalid(string expression)
318        {
319            Regex regExpression1 = new Regex("^(1|[\\*]|0)+$");
320            Hashtable h = (Hashtable)input;
321            ArrayList parameter = (ArrayList)h[h.Count - 1];
322            int runlenght = (int)parameter[2];
323            if (runlenght != settings.OutputSet.Length)
324            {
325                GuiLogMessage("the runlength (considered clocks) must the same in both plugins", NotificationLevel.Error);
326                return false;
327            }
328            if (!regExpression1.IsMatch(expression))
329            {
330                GuiLogMessage("the expression of the set of outputs " + expression + " is not legal", NotificationLevel.Error);
331                return false;
332            }
333            return true;
334        }
335        private bool IsBitSeqSetValid(string bitseqset)
336        {
337            string[] bitseqs = bitseqset.Split(',');
338            int seqlength = bitseqs[0].Length;
339            Regex objBoolExpression = new Regex("^[0-1]+$");
340            for (int i = 0; i < bitseqs.Length; i++)
341            {
342                if (bitseqs[i].Length != seqlength)
343                {
344                    GuiLogMessage(" not all Bitsequence are  the same length ", NotificationLevel.Error);
345                    return false;
346                }
347                if (!objBoolExpression.IsMatch(bitseqs[i]))
348                {
349                    GuiLogMessage("The bitsquence expression is not legal ", NotificationLevel.Error);
350                    return false;
351                }
352            }
353            return true;
354        }
355        public ArrayList Computeannihilators(ArrayList S, int deg)
356        {
357            int Xlength = ((bool[])S[0]).Length;
358            ArrayList monomials = GenerateMonomials(Xlength, deg);
359            ArrayList F = monomials;
360            foreach (bool[] X in S)
361            {
362                ArrayList F0 = new ArrayList();
363                ArrayList F1 = new ArrayList();
364                foreach (ArrayList f in F)
365                {
366                    if (EvaluateFunction(f, X)) F1.Add(f);
367                    else F0.Add(f);
368                }
369                if (F1.Count > 1)
370                {
371                    ArrayList g = (ArrayList)F1[0];
372                    for (int i = 1; i < F1.Count; i++)
373                    {
374                        foreach (bool[] monomial in g)
375                        {
376                            if (((ArrayList)F1[i]).Contains(monomial))
377                                ((ArrayList)F1[i]).Remove(monomial);
378                            else ((ArrayList)F1[i]).Add(monomial);
379                        }
380                        if (!F0.Contains(((ArrayList)F1[i]))) F0.Add(((ArrayList)F1[i]));//G0 U F0
381                    }
382                }
383                F = F0;
384            }
385            return F;
386        }
387        public ArrayList GenerateMonomials(int dim, int deg)
388        {
389            ArrayList monomials = new ArrayList();
390            for (int i = 0; i < exp(2, dim); i++)//
391            {
392                bool[] monomial = ConstructBitsequence(i, dim);
393                int wight = 0;
394                for (int j = 0; j < monomial.Length; j++)
395                {
396                    if (monomial[j]) wight = wight + 1;
397                }
398                if (wight <= deg)
399                {
400                    ArrayList fmonomial = new ArrayList();
401                    fmonomial.Add(monomial);
402                    monomials.Add(fmonomial);
403                }
404            }
405            return monomials;
406        }
407        private void FunctionAnnihilators()
408        {
409            if (input != null && input.GetType().Equals(typeof(String)))
410            {
411                string function = (string)input;
412                if (IsFunctionExpValid(function))
413                {
414                    ArrayList suppf = new ArrayList();
415                    string simplef = SimplifyFunction(function);
416                    ArrayList convertf = ConvertSimpleFunction(simplef, dimention);
417                    for (int x = 0; x < exp(2, dimention); x++)
418                    {
419                        bool[] X = ConstructBitsequence(x, dimention);
420                        bool res = EvaluateFunction(convertf, X);
421                        if (res) suppf.Add(X);
422                    }
423                    ArrayList annihilators = Computeannihilators(suppf, settings.Degree);
424                    string s = ToStringAnnihilators(annihilators);
425                    if (s == "") outputstring = "no annihilator of degree  = " + settings.Degree + " is located";
426                    else outputstring = "annihilators of the given function of degree smaller or equal " + settings.Degree + "\r\n" + s;
427                    OnPropertyChanged("OutputString");
428                }
429            }
430            else
431            {
432                GuiLogMessage("not all mandatory parameters are provided", NotificationLevel.Error);
433            }
434        }
435        private bool EvaluteMonomial(bool[] monom, bool[] input)
436        {
437            for (int i = 0; i < input.Length; i++)
438            {
439                if (monom[i] && !input[i])
440                    return false;
441            }
442            return true;
443
444        }
445        public bool EvaluateFunction(ArrayList function, bool[] input)
446        {
447            bool res = EvaluteMonomial((bool[])function[0], input);
448            for (int j = 1; j < function.Count; j++)
449            {
450                res = res ^ (EvaluteMonomial((bool[])function[j], input));
451            }
452            return res;
453        }
454        public string ToStringAnnihilators(ArrayList annihilators)
455        {
456            StringBuilder strBuilder = new StringBuilder();
457            if (annihilators.Count == 0) return "";
458            else
459            {
460                int index = 1;
461                foreach (ArrayList annihilator in annihilators)
462                {
463                    string function = "";
464                    foreach (bool[] monomial in annihilator)
465                    {
466                        string s = "";
467                        for (int i = 0; i < monomial.Length; i++)
468                        {
469                            if (monomial[i]) s = s + "x" + (i + 1) + "*";
470                        }
471                        if (s == "") s = "" + 1;
472                        else s = s.Remove(s.LastIndexOf("*"));
473                        function = function + s + "+";
474                    }
475                    function = function.Remove(function.LastIndexOf("+"));
476                    function = index + "-  " + function;
477                    strBuilder.AppendLine(function);
478                    index++;
479                }
480            }
481            return strBuilder.ToString();
482        }
483
484
485
486
487
488
489        private ArrayList ConvertSimpleFunction(string function, int dim)
490        {
491            ArrayList convertfunction = new ArrayList();
492            string[] monomials = function.Split('+');
493            for (int i = 0; i < monomials.Length; i++)
494            {
495                string[] literals = monomials[i].Split('*');
496                bool[] monom = new bool[dim];
497                for (int j = 0; j < monom.Length; j++)
498                {
499                    monom[j] = false;
500                }
501                for (int j = 0; j < literals.Length; j++)
502                {
503                    string literal = literals[j];
504                    if (literal.StartsWith("x"))
505                    {
506                        if (literal.StartsWith("x"))
507                        {
508                            int index = Convert.ToInt16(literal.Substring(1, literal.Length - 1));
509                            if (index <= dim) monom[index - 1] = true;
510                            else GuiLogMessage("the indexes of variable must begin  from 1 and to be successiv ", NotificationLevel.Error);
511                        }
512                    }
513                    //monom[Convert.ToInt16(literal.Substring(1, literal.Length - 1)) - 1] = true;
514
515                }
516                convertfunction.Add(monom);
517            }
518            return convertfunction;
519        }
520
521
522
523        #endregion
524
525        //private int CountLFSROutputs(string function)
526        //{
527        //    ArrayList lfsrvar = new ArrayList();
528        //    string[] monom = function.Split('+');
529        //    for (int i = 0; i < monom.Length; i++)
530        //    {
531        //        string[] literals = monom[i].Split('*');
532        //        for (int j = 0; j < literals.Length; j++)
533        //        {
534        //            string literal = literals[j];
535        //            if (literal.StartsWith("x"))
536        //            {
537        //                if (!lfsrvar.Contains(literal)) lfsrvar.Add(literal);
538        //            }
539        //        }
540        //    }
541        //    return lfsrvar.Count;
542        //}
543
544        public int exp(int b, int e)
545        {
546            int res = 1;
547            for (int i = 1; i <= e; i++)
548            {
549                res = res * b;
550            }
551            return res;
552        }
553        public bool[] ConstructBitsequence(int value, int length)
554        {
555            bool[] bitseq = new bool[length];
556            if (value == 0)
557            {
558                for (int j = 0; j < length; j++)
559                {
560                    bitseq[j] = false;
561                }
562            }
563            else
564            {
565                int i = length;
566                while (value != 0)
567                {
568                    int div = value % 2;
569                    if (div == 0) bitseq[i - 1] = false;
570                    else bitseq[i - 1] = true;
571                    i = i - 1;
572                    value = value / 2;
573                }
574                if (i > 0)
575                {
576                    for (int j = 0; j < i; j++)
577                    {
578                        bitseq[j] = false;
579                    }
580                }
581            }
582            return bitseq;
583        }
584        //public int ComputeAI(ArrayList annihilators)
585        //{
586        //    if (annihilators.Count == 0) return 0;
587        //    else
588        //    {
589        //        int AI=1000;
590        //        foreach (ArrayList annihilator in annihilators)
591        //        {
592        //           int f_ai=0;
593        //           foreach (bool[] monomials in annihilator)
594        //           {
595        //                int monom_ai = 0;
596        //                for (int i = 0; i < monomials.Length; i++)
597        //                {
598        //                    if (monomials[i]) monom_ai++;
599        //                }
600        //                if (monom_ai>f_ai) f_ai = monom_ai;
601        //            }
602        //           if (f_ai<AI) AI=f_ai;
603        //        }
604        //        return AI;
605        //    } 
606        //}
607
608
609        #region function parser
610        private string SimplifyFunction(string function)
611        {
612            return ReduceFunction(SimplifyParentheses(NegateTerms(function)));
613        }
614        private string NegateTerms(string f)
615        {
616            int notindex = f.IndexOf("!");
617            while (notindex != -1)
618            {
619                string tonegate = f.Substring(notindex + 1, 1);
620                if (tonegate == "(")
621                {
622                    f = f.Remove(notindex, 1);
623                    f = f.Insert(notindex + 1, "1+");
624                }
625                else
626                {
627                    // die zu negierende Term selektieren
628                    string subf = f.Substring(notindex + 1);
629                    string[] subterms = subf.Split('+');
630                    string[] subliterals = subterms[0].Split('*');
631                    string tonegatliteral = subliterals[0];
632                    //die zu negierende Term selektieren löschen und ersetzen
633                    f = f.Remove(notindex, 1 + tonegatliteral.Length);
634                    f = f.Insert(notindex, "(1+" + tonegatliteral + ")");
635                }
636                notindex = f.IndexOf("!");
637            }
638            return f;
639        }
640        private string Expandproducts(string f)
641        {
642            while (f.IndexOf("(") != -1)
643            {
644                int p1 = f.IndexOf("(");
645                int p2 = f.IndexOf(")");
646                if (!f.Substring(p1, p2 - p1 + 1).Contains('+'))
647                {
648                    f = f.Remove(p1, 1);
649                    f = f.Remove(p2 - 1, 1);
650                }
651                else
652                {
653                    string topar = f.Substring(0, p1);//string bis die Parenthese
654                    int begin = topar.LastIndexOf("+") + 1;// index des Anfang des Termes ohne plus,
655                    int end = p1 + FindEndOfTerm(f.Substring(p1));// Ende des Termes:Index vom plus
656                    string Term = f.Substring(begin, end - begin);
657                    f = f.Remove(begin, Term.Length);
658                    Term = ExpandOneTerm(Term);
659                    f = f.Insert(begin, Term);
660                }
661            }
662            return f;
663        }
664        public int FindEndOfTerm(string f)
665        {
666            CharEnumerator f_char = f.GetEnumerator();
667            int index = 0;
668            bool overt = false;
669            while (f_char.MoveNext())
670            {
671                char c = f_char.Current;
672                if (c == '(') overt = true;
673                if (c == ')') overt = false;
674                if (c == '+' && !overt) return index;
675                index++;
676            }
677            return f.Length;
678        }
679        public string ExpandOneTerm(string term)//devlopet ein Term, das zwei oder mehr als zwei Faktoren enthält
680        {//func besteht aus Terme mit * verknüpft die Terme nur die Operator+ beinhalten (k+k+k)*(k+..+k)*..*(k+k+k)*(k+..+k)
681            int p1 = term.IndexOf('(');
682            int p2 = term.IndexOf(')');
683            ArrayList terms = new ArrayList();
684            while (p1 != -1)
685            {
686                string factor = term.Substring(p1, p2 - p1 + 1);
687                if (p2 != term.Length - 1) { term = term.Remove(p1, p2 - p1 + 2); }
688                else { term = term.Remove(p1, p2 - p1 + 1); }
689                terms.Add(factor);
690                p1 = term.IndexOf('(');
691                p2 = term.IndexOf(')');
692            }
693            string res = "";
694            if (terms.Count == 1) res = (string)terms[0];//mit ()
695            else
696            {
697                res = "(" + LiftRightExpand(terms[0] + "*" + terms[1]) + ")";//mit ()
698                for (int i = 2; i < terms.Count; i++)
699                {
700                    res = "(" + LiftRightExpand(res + "*" + terms[i]) + ")";
701                }
702            }
703            if (term != "")
704            {
705                if (term.EndsWith("*")) res = RightExpand(term + res);
706                else res = RightExpand(term + "*" + res);
707            }
708            else//(res)
709            {
710                res = res.Remove(0, 1);
711                res = res.Remove(res.Length - 1, 1);
712            }
713            return res;
714        }
715        public string RightExpand(string term)
716        {//k1*k2*(k1+..+k8)=>k1*k2*k1+..+k1*k2*k8
717            int p1 = term.IndexOf("(");
718            int p2 = term.IndexOf(")");
719            string fact1 = term.Substring(0, p1);
720            string fact2 = term.Substring(p1 + 1, p2 - p1 - 1);
721            string[] sumands = fact2.Split('+');
722            string s = "";
723            for (int i = 0; i < sumands.Length; i++)
724            {
725                s = s + fact1 + sumands[i] + "+";
726            }
727            s = s.Remove(s.Length - 1);
728            return s;
729        }
730        public string LiftExpand(string term)
731        {//(k1+..+k8)*k7*k8=>k1*k7*k8+..+k8*k7*k8
732            int p1 = term.IndexOf("(");
733            int p2 = term.IndexOf(")");
734            string fac1 = term.Substring(p2 + 1, term.Length - p2 - 1);//factor zu multipluzieren
735            string fac2 = term.Substring(p1 + 1, p2 - p1 - 1);
736            string[] sumands = fac2.Split('+');
737            string s = "";
738            for (int i = 0; i < sumands.Length; i++)
739            {
740                s = s + sumands[i] + fac1 + "+";
741            }
742            s = s.Remove(s.Length - 1);
743            return s;
744        }
745        public string LiftRightExpand(string term)
746        {// (k1..k6)*(k1...k12)=>(k1..k6)*k1+..+(k1..k6)*k12
747            int p1 = term.IndexOf("(");
748            int p2 = term.IndexOf(")");
749            string fac1 = term.Substring(0, p2 + 2);
750            string fac2 = term.Substring(p2 + 3, term.Length - p2 - 4);
751            string[] sumands = fac2.Split('+');
752            string s = "";
753            for (int i = 0; i < sumands.Length; i++)
754            {
755                s = s + LiftExpand(fac1 + sumands[i]) + "+";
756            }
757            s = s.Remove(s.Length - 1);
758            return s;
759        }
760        public static string ReduceFunction(string function)// alle Terme reduzieren
761        {
762            //1*X=X*1=X
763            int index = function.IndexOf("+1*");
764            while (index != -1)
765            {
766                function = function.Remove(index + 1, 2);
767                index = function.IndexOf("+1*");
768            }
769            index = function.IndexOf("1*");
770            if (index == 0) function = function.Remove(index + 1, 2);
771            index = function.IndexOf("*1");
772            while (index != -1)
773            {
774                function = function.Remove(index, 2);
775                index = function.IndexOf("*1");
776            }
777            //X*X=X
778            string[] monomials = function.Split('+');
779            string s = "";
780            for (int i = 0; i < monomials.Length; i++)
781            {
782                s = s + ReduceTerm(monomials[i]) + "+";
783            }
784            s = s.Remove(s.LastIndexOf("+"));
785            return s;
786        }
787        private static string ReduceTerm(string term)// wenn zwei literale eine wird gelöscht wenn xi und !xi exist Term wird gelöscht
788        {
789            string[] literals = term.Split('*');
790            string s = "";
791            for (int i = 0; i < literals.Length - 1; i++)
792            {
793                if (literals[i] != "")
794                {
795                    for (int j = i + 1; j < literals.Length; j++)
796                    {
797                        if (literals[i] == literals[j])//xi*xi=xi
798                        {
799                            literals[j] = "";
800                        }
801                    }
802                    s = s + literals[i] + "*";
803                }
804            }
805            s = s + literals[literals.Length - 1];
806            return s;
807        }
808        public string SimplifyParentheses(string f)//löst ein Schachtelung
809        {
810            CharEnumerator fchar = f.GetEnumerator();
811            int overt = 0;
812            int closed = 0;
813            int firstovert = 0;
814            int lastclosed = 0;
815            int index = 0;
816            if (!IsParenthesesNested(f)) return Expandproducts(f);
817            else
818            {
819                while (fchar.MoveNext())
820                {
821                    char c = fchar.Current;
822                    if (c == '(')
823                    {
824                        if (overt == 0)
825                        {
826                            firstovert = index;
827                            overt++;
828                        }
829                        else
830                        {
831                            overt++;
832                        }
833                    }
834                    if (c == ')')
835                    {
836                        if (overt == 1) overt = 0;
837                        else //es gibt Schachtelung
838                        {
839                            closed++;
840                            if (closed == overt)// Ende der Schachtelung
841                            {// löst die Schachtelung
842                                overt = 0;
843                                closed = 0;
844                                lastclosed = index;
845                                string toexpand = f.Substring(firstovert + 1, lastclosed - firstovert - 1);
846                                f = f.Remove(firstovert + 1, lastclosed - firstovert - 1);
847                                f = f.Insert(firstovert + 1, SimplifyParentheses(toexpand));
848                                f = SimplifyParentheses(f);
849                            }// löst die Schachtelung
850                        }
851                    }
852                    index++;
853                }
854                return f;
855            }
856        }
857        public bool IsParenthesesNested(string f)
858        {
859            CharEnumerator fchar = f.GetEnumerator();
860            bool overt = false;
861            while (fchar.MoveNext())
862            {
863                char c = fchar.Current;
864                if (c == '(')
865                {
866                    if (overt) return true;
867                    else overt = true;
868                }
869                if (c == ')' && overt) overt = false;
870            }
871            return false;
872
873        }
874        private string[] Splitfunction(string function)
875        {
876            string er = function;
877            int index = er.IndexOf("(");
878            while (index != -1)
879            {
880                er = er.Remove(index, 1);
881                index = er.IndexOf("(");
882            }
883            index = er.IndexOf(")");
884            while (index != -1)
885            {
886                er = er.Remove(index, 1);
887                index = er.IndexOf(")");
888            }
889            index = er.IndexOf("!");
890            while (index != -1)
891            {
892                er = er.Remove(index, 1);
893                index = er.IndexOf("!");
894            }
895            string[] monom = function.Split('+');
896            return monom;
897        }
898        private bool IsSimpleIndicesValid(string function)
899        {
900            ArrayList lfsrvar = new ArrayList();
901            string[] monomials = Splitfunction(function);
902            for (int i = 0; i < monomials.Length; i++)
903            {
904                string[] literals = monomials[i].Split('*');
905                for (int j = 0; j < literals.Length; j++)
906                {
907                    string literal = literals[j];
908                    if (literal.StartsWith("x"))
909                    {
910                        if (!lfsrvar.Contains(literal)) lfsrvar.Add(literal);
911
912                    }
913                }
914            }
915            dimention = lfsrvar.Count;// Anzahl der LFSRs-Ausgänge wird berechnet
916            foreach (string lit in lfsrvar)
917            {
918                int index = Convert.ToInt16(lit.Substring(1, lit.Length - 1));
919                if (!(1 <= index && index <= dimention))
920                {
921                    GuiLogMessage("the indexes of variable x_i must begin  from 1 and to be successiv ", NotificationLevel.Error);
922                    return false;
923                }
924            }
925            return true;
926        }
927        public bool IsFunctionExpValid(string fstring)
928        {
929            fstring = fstring.Replace(" ", "");
930            Regex objBoolExpression = new Regex("^(([\\!]?[\\(])*(((\\!?)(x))(\\d+)|1)[\\)]*(\\*|\\+))*(((\\!?)(x))(\\d+)|1)[\\)]*$");
931            if (!IsParenthesesvalid(fstring))
932            {
933                GuiLogMessage("the  Parentheses in " + fstring + " is not valid", NotificationLevel.Error);
934                return false;
935            }
936            if (!objBoolExpression.IsMatch(fstring))
937            {
938                GuiLogMessage(fstring + "is not a legal function", NotificationLevel.Error);
939                return false;
940            }
941            if (!IsSimpleIndicesValid(fstring)) return false;
942            return true;
943        }
944        private bool IsParenthesesvalid(string s)
945        {
946            CharEnumerator cn = s.GetEnumerator();
947            int overt = 0;
948            int closed = 0;
949            while (cn.MoveNext())
950            {
951                char c = cn.Current;
952                if (c == '(') overt++;
953                else
954                {
955                    if (c == ')') closed++;
956                    if (closed > overt) return false;
957                }
958            }
959            if (closed < overt) return false;
960            return true;
961        }
962        public int[] GetOutputs(string outputsexp)
963        {
964            char[] c = outputsexp.ToCharArray();
965            int[] Z;
966            int Zlength = 0;
967            int sum = 0;
968            ArrayList sumlist = new ArrayList();
969            for (int i = 0; i < c.Length; i++)
970            {
971                if (c[i] == '*')//*
972                {
973                    Zlength++;
974                    sumlist.Add(exp(2, c.Length - 1 - i));
975                }
976                else//0 oder 1
977                {
978                    if (c[i] == '1') sum = sum + exp(2, c.Length - 1 - i);
979                }
980            }
981            Z = new int[exp(2, Zlength)];
982            for (int i = 0; i < exp(2, Zlength); i++)
983            {
984                bool[] bitseq = ConstructBitsequence(i, Zlength);
985                int dez_v = 0;
986                for (int j = 0; j < bitseq.Length; j++)
987                {
988                    if (bitseq[j]) dez_v = dez_v + (int)sumlist[j];
989                }
990                Z[i] = dez_v + sum;
991            }
992            return Z;
993        }
994        public string Bitpresentation(int value, int length)
995        {
996            string s = "";
997            int i = length;
998            if (value == 0)
999            {
1000                for (int j = 0; j < length; j++)
1001                {
1002                    s = s + "0";
1003                }
1004            }
1005            else
1006            {
1007                while (value != 0)
1008                {
1009                    int div = value % 2;
1010                    if (div == 0) s = "0" + s;
1011                    else s = "1" + s;
1012                    i = i - 1;
1013                    value = value / 2;
1014                }
1015                if (i > 0)
1016                {
1017                    for (int j = 0; j < i; j++)
1018                    {
1019                        s = "0" + s;
1020                    }
1021                }
1022            }
1023            return s;
1024        }
1025
1026        #endregion
1027
1028
1029
1030
1031
1032    }// class ahnilatorscompute
1033
1034
1035}// namesspaces
1036
Note: See TracBrowser for help on using the repository browser.