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

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

converted msieve to VS2010

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