source: trunk/CrypPlugins/QuadraticSieve/QuadraticSieve.cs @ 1448

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

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

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

File size: 23.8 KB
Line 
1/*                             
2   Copyright 2009 Team CrypTool (Sven Rech,Dennis Nolte,Raoul Falk,Nils Kopal), Uni Duisburg-Essen
3
4   Licensed under the Apache License, Version 2.0 (the "License");
5   you may not use this file except in compliance with the License.
6   You may obtain a copy of the License at
7
8       http://www.apache.org/licenses/LICENSE-2.0
9
10   Unless required by applicable law or agreed to in writing, software
11   distributed under the License is distributed on an "AS IS" BASIS,
12   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   See the License for the specific language governing permissions and
14   limitations under the License.
15*/
16
17using System;
18using System.Collections;
19using System.Linq;
20using System.Text;
21using Cryptool.PluginBase;
22using Cryptool.PluginBase.IO;
23using QuadraticSieve;
24using Cryptool.PluginBase.Miscellaneous;
25using System.ComponentModel;
26using System.Threading;
27using System.IO;
28using System.Windows.Controls;
29using System.Windows.Threading;
30using System.Windows;
31using System.Reflection;
32using System.Numerics;
33
34namespace Cryptool.Plugins.QuadraticSieve
35{
36    /// <summary>
37    /// This class wraps the msieve algorithm in version 1.42 which you can find at http://www.boo.net/~jasonp/qs.html
38    /// It also extends the msieve functionality to multi threading
39    /// Many thanks to the author of msieve "jasonp_sf"
40    ///
41    /// For further information on quadratic sieve or msieve please have a look at the above mentioned URL
42    /// </summary>
43    [Author("Sven Rech", "rech@cryptool.org", "Uni Duisburg-Essen", "http://www.uni-due.de")]
44    [PluginInfo(false, "Quadratic Sieve", "Sieving Primes", "QuadraticSieve/DetailedDescription/Description.xaml", "QuadraticSieve/iconqs.png")]
45    class QuadraticSieve : DependencyObject, IThroughput
46    {
47        #region private variables
48
49        private readonly string directoryName;
50        private QuadraticSieveSettings settings = new QuadraticSieveSettings();
51        private BigInteger inputNumber;
52        private BigInteger[] outputFactors;
53        private bool running;
54        private Queue yieldqueue;
55        private IntPtr obj = IntPtr.Zero;
56        private volatile int threadcount = 0;
57        private DateTime start_sieving_time;
58        private bool sieving_started;
59        private int start_relations;
60        private ArrayList conf_list;
61        private static Assembly msieveDLL;
62        private static Type msieve;
63        private bool userStopped = false;
64        private IntPtr factorList;
65        private ArrayList factors;
66
67        #endregion
68
69        #region events
70
71        public event StatusChangedEventHandler OnPluginStatusChanged;
72        public event GuiLogNotificationEventHandler OnGuiLogNotificationOccured;
73        public event PluginProgressChangedEventHandler OnPluginProgressChanged;
74        public event System.ComponentModel.PropertyChangedEventHandler PropertyChanged;
75        public event PluginProgressChangedEventHandler OnPluginProcessChanged;
76
77        #endregion
78
79        /// <summary>
80        /// Static constructor
81        ///
82        /// loads the msieve / msieve64 dll
83        /// </summary>
84        static QuadraticSieve()
85        {
86            //Load msieve.dll:
87            string s = Directory.GetCurrentDirectory();
88            string dllname;
89            if (IntPtr.Size == 4)
90                dllname = "msieve.dll";
91            else
92                dllname = "msieve64.dll";
93            msieveDLL = Assembly.LoadFile(Directory.GetCurrentDirectory() + "\\" + dllname);
94            msieve = msieveDLL.GetType("Msieve.msieve");
95        }
96       
97        #region public
98
99        /// <summary>
100        /// Constructor
101        ///
102        /// constructs a new QuadraticSieve plugin
103        /// </summary>
104        public QuadraticSieve()
105        {
106            directoryName = Path.Combine(DirectoryHelper.DirectoryLocalTemp, "msieve");
107            if (!Directory.Exists(directoryName)) Directory.CreateDirectory(directoryName);
108
109            QuickWatchPresentation = new QuadraticSievePresentation();
110           
111            quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
112            {
113                quadraticSieveQuickWatchPresentation.timeLeft.Text = "?";
114                quadraticSieveQuickWatchPresentation.endTime.Text = "?";
115                quadraticSieveQuickWatchPresentation.logging.Text = "Currently not sieving.";
116            }
117            , null);
118        }               
119
120        /// <summary>
121        /// Getter / Setter for the settings of this plugin
122        /// </summary>
123        public Cryptool.PluginBase.ISettings Settings
124        {
125            get { return this.settings; }
126            set { this.settings = (QuadraticSieveSettings)value; } 
127        }           
128
129        /// <summary>
130        /// Called by the environment before executing this plugin
131        /// </summary>
132        public void PreExecution()
133        { 
134        }
135       
136        /// <summary>
137        /// Called by the environment to execute this plugin
138        /// </summary>
139        public void Execute()
140        {
141            userStopped = false;
142
143            if (InputNumber is Object)
144            {
145                if (InputNumber.ToString().Length >= 275)
146                {
147                    GuiLogMessage("Input too big.", NotificationLevel.Error);
148                    return;
149                }
150
151                String timeLeft_message = "?";
152                String endtime_message = "?";
153                String logging_message = "Starting quadratic sieve, please wait!";
154
155                GuiLogMessage(logging_message, NotificationLevel.Info);
156                quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
157                {
158                    quadraticSieveQuickWatchPresentation.logging.Text = logging_message;
159                    quadraticSieveQuickWatchPresentation.endTime.Text = endtime_message;
160                    quadraticSieveQuickWatchPresentation.timeLeft.Text = timeLeft_message;
161                }
162                , null);   
163
164                DateTime start_time = DateTime.Now;
165
166                //init msieve with callbacks:
167                MethodInfo initMsieve = msieve.GetMethod("initMsieve");
168                Object callback_struct = Activator.CreateInstance(msieveDLL.GetType("Msieve.callback_struct"));
169                FieldInfo showProgressField = msieveDLL.GetType("Msieve.callback_struct").GetField("showProgress");
170                FieldInfo prepareSievingField = msieveDLL.GetType("Msieve.callback_struct").GetField("prepareSieving");
171                FieldInfo getTrivialFactorlistField = msieveDLL.GetType("Msieve.callback_struct").GetField("getTrivialFactorlist");
172                Delegate showProgressDel = MulticastDelegate.CreateDelegate(msieveDLL.GetType("Msieve.showProgressDelegate"), this, "showProgress");
173                Delegate prepareSievingDel = MulticastDelegate.CreateDelegate(msieveDLL.GetType("Msieve.prepareSievingDelegate"), this, "prepareSieving");
174                Delegate getTrivialFactorlistDel = MulticastDelegate.CreateDelegate(msieveDLL.GetType("Msieve.getTrivialFactorlistDelegate"), this, "getTrivialFactorlist");
175                showProgressField.SetValue(callback_struct, showProgressDel);
176                prepareSievingField.SetValue(callback_struct, prepareSievingDel);
177                getTrivialFactorlistField.SetValue(callback_struct, getTrivialFactorlistDel);
178                initMsieve.Invoke(null, new object[1] { callback_struct });
179
180                //Now factorize:               
181                try
182                {
183                    string file = Path.Combine(directoryName, "" + InputNumber + ".dat");
184                    if (settings.DeleteCache && File.Exists(file))
185                        File.Delete(file);
186                    MethodInfo factorize = msieve.GetMethod("start");
187                    factorize.Invoke(null, new object[] { InputNumber.ToString(), file });
188                    obj = IntPtr.Zero;
189                }
190                catch (Exception ex)
191                {
192                    GuiLogMessage("Error using msieve. " + ex.Message, NotificationLevel.Error);
193                    stopThreads();
194                    return;
195                }
196
197                if (factors != null && !userStopped)
198                {
199                    timeLeft_message = "0 seconds left";
200                    endtime_message = "" + (DateTime.Now);
201                    logging_message = "Sieving finished in " + (DateTime.Now - start_time) + "!";
202
203                    GuiLogMessage(logging_message, NotificationLevel.Info);
204                    quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
205                    {
206                        quadraticSieveQuickWatchPresentation.logging.Text = logging_message;
207                        quadraticSieveQuickWatchPresentation.endTime.Text = endtime_message;
208                        quadraticSieveQuickWatchPresentation.timeLeft.Text = timeLeft_message;
209                    }
210                    , null);
211                    BigInteger[] outs = new BigInteger[factors.Count];
212                    for (int i = 0; i < factors.Count; i++)
213                    {
214                        outs[i] = BigInteger.Parse((string)factors[i]);
215                    }
216                    OutputFactors = outs;
217                }
218                else
219                {
220                    timeLeft_message = "0 sec left";
221                    endtime_message = "Stopped";
222                    logging_message = "Stopped by user!";
223
224                    GuiLogMessage(logging_message, NotificationLevel.Info);
225                    quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
226                    {
227                        quadraticSieveQuickWatchPresentation.logging.Text = logging_message;
228                        quadraticSieveQuickWatchPresentation.endTime.Text = endtime_message;
229                        quadraticSieveQuickWatchPresentation.timeLeft.Text = timeLeft_message;
230                    }
231                    , null);
232                }
233                   
234                ProgressChanged(1, 1);
235               
236            }
237        }
238       
239        /// <summary>
240        /// Called by the environment after execution
241        /// </summary>
242        public void PostExecution()
243        {
244        }
245
246        /// <summary>
247        /// Called by the environment to pause execution
248        /// </summary>
249        public void Pause()
250        {
251        }
252
253        /// <summary>
254        /// Called by the environment to stop execution
255        /// </summary>
256        public void Stop()
257        {
258            this.userStopped = true;
259            if (obj != IntPtr.Zero)
260            {
261                stopThreads();
262                MethodInfo stop = msieve.GetMethod("stop");
263                stop.Invoke(null, new object[] { obj });
264            }
265
266        }
267
268        /// <summary>
269        /// Called by the environment to initialize this plugin
270        /// </summary>
271        public void Initialize()
272        {
273        }
274
275        /// <summary>
276        /// Called by the environment to dispose this plugin
277        /// </summary>
278        public void Dispose()
279        {
280        }
281
282        /// <summary>
283        /// Getter / Setter for the input number which should be factorized
284        /// </summary>
285        [PropertyInfo(Direction.InputData, "Number input", "Enter the number you want to factorize", "", DisplayLevel.Beginner)]
286        public BigInteger InputNumber
287        {
288            get
289            {
290                return inputNumber;
291            }
292            set
293            {
294                this.inputNumber = value;
295                OnPropertyChanged("InputNumber");
296            }
297        }
298
299        /// <summary>
300        /// Getter / Setter for the factors calculated by msieve
301        /// </summary>
302        [PropertyInfo(Direction.OutputData, "Factors output", "Your factors will be sent here", "", DisplayLevel.Beginner)]
303        public BigInteger[] OutputFactors
304        {
305            get
306            {
307                return outputFactors;
308            }
309            set
310            {
311                this.outputFactors = value;
312                OnPropertyChanged("OutputFactors");
313            }
314        }
315       
316        /// <summary>
317        /// Called when a property of this plugin changes
318        /// </summary>
319        /// <param name="name">name</param>
320        public void OnPropertyChanged(string name)
321        {
322            EventsHelper.PropertyChanged(PropertyChanged, this, new PropertyChangedEventArgs(name));
323        }
324
325        /// <summary>
326        /// Getter / Setter for the presentation of this plugin
327        /// </summary>
328        public UserControl Presentation { get; private set; }
329
330        /// <summary>
331        /// Getter / Setter for the QuickWatchPresentation of this plugin
332        /// </summary>
333        public UserControl QuickWatchPresentation
334        {
335            get;
336            private set;
337        }
338
339        #endregion
340
341        #region private
342
343        /// <summary>
344        /// calculate a String which shows the timespan
345        ///
346        /// example
347        ///
348        ///     4 days
349        /// or
350        ///     2 minutes
351        /// </summary>
352        /// <param name="ts"></param>
353        /// <returns></returns>
354        private String showTimeSpan(TimeSpan ts)
355        {
356            String res = "";
357            if (ts.Days != 0)
358                res = ts.Days + " days ";
359            if (ts.Hours != 0 || res.Length != 0)
360                res += ts.Hours + " hours ";
361            if (ts.Minutes != 0)
362                res += ts.Minutes + " minutes";
363            if (res.Length == 0)
364                res += ts.Seconds + " seconds";
365            return res;
366        }   
367
368        /// <summary>
369        /// Actualize the progress
370        /// </summary>
371        /// <param name="conf"></param>
372        /// <param name="num_relations"></param>
373        /// <param name="max_relations"></param>
374        private void showProgress(IntPtr conf, int num_relations, int max_relations)
375        {
376            if (num_relations == -1)    //sieving finished
377            {
378                showFactorList();
379                ProgressChanged(0.9, 1.0);
380                GuiLogMessage("Sieving finished", NotificationLevel.Info);
381                stopThreads();
382                yieldqueue.Clear();               
383            }
384            else
385            {
386                if (sieving_started)
387                {
388                    TimeSpan diff = DateTime.Now - start_sieving_time;
389                    double msleft = (diff.TotalMilliseconds / (num_relations - start_relations)) * (max_relations - num_relations);
390                    if (msleft > 0)
391                    {
392                        TimeSpan ts = new TimeSpan(0, 0, 0, 0, (int)msleft);
393                        String logging_message = "Found " + num_relations + " of " + max_relations + " relations!";
394                        String timeLeft_message = showTimeSpan(ts) + " left";
395                        String endtime_message = "" + DateTime.Now.AddMilliseconds((long)msleft);
396                       
397                        GuiLogMessage(logging_message + " " + timeLeft_message + ".", NotificationLevel.Debug);
398                        quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
399                        {
400                            quadraticSieveQuickWatchPresentation.logging.Text = logging_message;
401                            quadraticSieveQuickWatchPresentation.timeLeft.Text = timeLeft_message;
402                            quadraticSieveQuickWatchPresentation.endTime.Text = endtime_message;
403                        }
404                        , null);
405
406                    }
407                }
408
409                if (!sieving_started)
410                {
411                    showFactorList();
412
413                    MethodInfo getCurrentFactor = msieve.GetMethod("getCurrentFactor");
414                    //GuiLogMessage((String)(getCurrentFactor.Invoke(null, new object[] { conf })), NotificationLevel.Debug);
415
416                    start_relations = num_relations;
417                    start_sieving_time = DateTime.Now;
418                    sieving_started = true;
419                }
420
421                ProgressChanged((double)num_relations / max_relations * 0.8 + 0.1, 1.0);               
422
423                while (yieldqueue.Count != 0)       //get all the results from the helper threads, and store them
424                {
425                    MethodInfo saveYield = msieve.GetMethod("saveYield");
426                    saveYield.Invoke(null, new object[] { conf, (IntPtr)yieldqueue.Dequeue() });                   
427                }               
428            }
429        }
430
431        private void showFactorList()
432        {
433            MethodInfo getPrimeFactors = msieve.GetMethod("getPrimeFactors");
434            ArrayList fl = (ArrayList)(getPrimeFactors.Invoke(null, new object[] { factorList }));
435            foreach (Object o in fl)
436                GuiLogMessage("Prim Faktoren: " + (String)o, NotificationLevel.Debug);
437
438            MethodInfo getCompositeFactors = msieve.GetMethod("getCompositeFactors");
439            ArrayList fl2 = (ArrayList)(getCompositeFactors.Invoke(null, new object[] { factorList }));
440            foreach (Object o in fl2)
441                GuiLogMessage("Zusammengesetzte Faktoren: " + (String)o, NotificationLevel.Debug);
442        }
443
444        /// <summary>
445        /// Callback method to prepare sieving
446        /// Called by msieve
447        ///
448        /// </summary>
449        /// <param name="conf">pointer to configuration</param>
450        /// <param name="update">number of relations found</param>
451        /// <param name="core_sieve_fcn">pointer to internal sieve function of msieve</param>
452        private void prepareSieving (IntPtr conf, int update, IntPtr core_sieve_fcn)
453        {
454            int threads = Math.Min(settings.CoresUsed, Environment.ProcessorCount-1);
455            MethodInfo getObjFromConf = msieve.GetMethod("getObjFromConf");
456            this.obj = (IntPtr)getObjFromConf.Invoke(null, new object[] { conf });           
457            yieldqueue = Queue.Synchronized(new Queue());
458            sieving_started = false;
459            conf_list = new ArrayList();
460
461            String message = "Start sieving using " + (threads + 1) + " cores!";
462            GuiLogMessage(message, NotificationLevel.Info);
463            quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
464            {
465                quadraticSieveQuickWatchPresentation.logging.Text = message;
466            }
467            , null);         
468
469            ProgressChanged(0.1, 1.0);
470
471            running = true;
472            //start helper threads:
473            for (int i = 0; i < threads; i++)
474            {
475                MethodInfo cloneSieveConf = msieve.GetMethod("cloneSieveConf");
476                IntPtr clone = (IntPtr)cloneSieveConf.Invoke(null, new object[] { conf });               
477                conf_list.Add(clone);
478                WaitCallback worker = new WaitCallback(MSieveJob);
479                ThreadPool.QueueUserWorkItem(worker, new object[] { clone, update, core_sieve_fcn, yieldqueue });
480            }
481        }
482
483        private void getTrivialFactorlist(IntPtr list, IntPtr obj)
484        {
485            factorList = list;
486            MethodInfo getPrimeFactors = msieve.GetMethod("getPrimeFactors");
487            factors = (ArrayList)(getPrimeFactors.Invoke(null, new object[] { factorList }));
488            GuiLogMessage("TEST", NotificationLevel.Debug);
489
490            //showFactorList();
491        }
492
493        /// <summary>
494        /// Helper Thread for msieve, which sieves for relations:
495        /// </summary>
496        /// <param name="param">params</param>
497        private void MSieveJob(object param)
498        {
499            threadcount++;
500            object[] parameters = (object[])param;
501            IntPtr clone = (IntPtr)parameters[0];
502            int update = (int)parameters[1];
503            IntPtr core_sieve_fcn = (IntPtr)parameters[2];
504            Queue yieldqueue = (Queue)parameters[3];
505
506            while (running)
507            {
508                try
509                {
510                    MethodInfo collectRelations = msieve.GetMethod("collectRelations");
511                    collectRelations.Invoke(null, new object[] { clone, update, core_sieve_fcn });
512                    MethodInfo getYield = msieve.GetMethod("getYield");
513                    IntPtr yield = (IntPtr)getYield.Invoke(null, new object[] { clone });
514
515                    //Just for testing the serialize mechanism:
516                    MethodInfo serializeYield = msieve.GetMethod("serializeYield");
517                    byte[] serializedYield = (byte[])serializeYield.Invoke(null, new object[] { yield });
518                    /*MethodInfo deserializeYield = msieve.GetMethod("deserializeYield");
519                    yield = (IntPtr)deserializeYield.Invoke(null, new object[] { serializedYield });*/
520
521                    yieldqueue.Enqueue(yield);
522                }
523                catch (Exception ex)
524                {
525                    GuiLogMessage("Error using msieve." + ex.Message, NotificationLevel.Error);
526                    threadcount = 0;
527                    return;
528                }               
529            }
530            MethodInfo freeSieveConf = msieve.GetMethod("freeSieveConf");
531            freeSieveConf.Invoke(null, new object[] { clone });           
532            threadcount--;
533        }       
534
535        /// <summary>
536        /// Stop all running threads
537        /// </summary>
538        private void stopThreads()
539        {
540            if (conf_list != null)
541            {
542                running = false;
543                MethodInfo stop = msieve.GetMethod("stop");
544                MethodInfo getObjFromConf = msieve.GetMethod("getObjFromConf");
545                foreach (IntPtr conf in conf_list)
546                    stop.Invoke(null, new object[] { getObjFromConf.Invoke(null, new object[] { conf }) });
547                GuiLogMessage("Waiting for threads to stop!", NotificationLevel.Debug);
548                while (threadcount > 0)
549                {
550                    Thread.Sleep(0);
551                }
552                GuiLogMessage("Threads stopped!", NotificationLevel.Debug);
553                conf_list.Clear();
554            }
555        }   
556
557        /// <summary>
558        /// Change the progress of this plugin
559        /// </summary>
560        /// <param name="value">value</param>
561        /// <param name="max">max</param>
562        private void ProgressChanged(double value, double max)
563        {
564            EventsHelper.ProgressChanged(OnPluginProgressChanged, this, new PluginProgressEventArgs(value, max));
565        }
566
567        /// <summary>
568        /// Logs a message to the CrypTool gui
569        /// </summary>
570        /// <param name="p">p</param>
571        /// <param name="notificationLevel">notificationLevel</param>
572        private void GuiLogMessage(string p, NotificationLevel notificationLevel)
573        {
574            EventsHelper.GuiLogMessage(OnGuiLogNotificationOccured, this, new GuiLogEventArgs(p, this, notificationLevel));
575        }
576
577        /// <summary>
578        /// Getter / Setter for the QuickWatchPresentation
579        /// </summary>
580        private QuadraticSievePresentation quadraticSieveQuickWatchPresentation
581        {
582            get { return QuickWatchPresentation as QuadraticSievePresentation; }
583        }
584
585        #endregion
586
587    }
588}
Note: See TracBrowser for help on using the repository browser.