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

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

changed quadratic sieve presentation a litte bit

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