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

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

fixed dll path in quadratic sieve

File size: 25.9 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 AutoResetEvent yieldEvent = new AutoResetEvent(false);
58        private IntPtr obj = IntPtr.Zero;
59        private volatile int threadcount = 0;
60        private ArrayList conf_list;
61        private bool userStopped = false;
62        private FactorManager factorManager;
63        private PeerToPeer peerToPeer = new PeerToPeer();
64        private BigInteger sumSize = 0;
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            sumSize = 0;
126            userStopped = false;
127
128            if (InputNumber != 0)
129            {
130                if (InputNumber.ToString().Length >= 275)
131                {
132                    GuiLogMessage("Input too big.", NotificationLevel.Error);
133                    return;
134                }
135
136                String timeLeft_message = "?";
137                String endtime_message = "?";
138                String logging_message = "Starting quadratic sieve, please wait!";
139
140                GuiLogMessage(logging_message, NotificationLevel.Info);
141                quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
142                {
143                    quadraticSieveQuickWatchPresentation.logging.Text = logging_message;
144                    quadraticSieveQuickWatchPresentation.endTime.Text = endtime_message;
145                    quadraticSieveQuickWatchPresentation.timeLeft.Text = timeLeft_message;
146                    quadraticSieveQuickWatchPresentation.factorList.Items.Clear();
147                    quadraticSieveQuickWatchPresentation.factorInfo.Content = "Searching trivial factors!";                   
148                }
149                , null);   
150
151                DateTime start_time = DateTime.Now;
152
153                initMsieveDLL();
154                factorManager = new FactorManager(msieve.GetMethod("getPrimeFactors"), msieve.GetMethod("getCompositeFactors"));
155                factorManager.FactorsChanged += this.FactorsChanged;
156
157                //Now factorize:               
158                try
159                {
160                    string file = Path.Combine(directoryName, "" + InputNumber + ".dat");
161                    if (settings.DeleteCache && File.Exists(file))
162                        File.Delete(file);
163                    MethodInfo start = msieve.GetMethod("start");
164                    start.Invoke(null, new object[] { InputNumber.ToString(), file });
165                    obj = IntPtr.Zero;
166                }
167                catch (Exception ex)
168                {
169                    GuiLogMessage("Error using msieve. " + ex.Message, NotificationLevel.Error);
170                    stopThreads();
171                    return;
172                }
173
174                if (!userStopped)
175                {
176                    timeLeft_message = "0 seconds left";
177                    endtime_message = "" + (DateTime.Now);
178                    logging_message = "Sieving finished in " + (DateTime.Now - start_time) + "!";
179
180                    GuiLogMessage(logging_message, NotificationLevel.Info);
181                    quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
182                    {
183                        quadraticSieveQuickWatchPresentation.logging.Text = logging_message;
184                        quadraticSieveQuickWatchPresentation.endTime.Text = endtime_message;
185                        quadraticSieveQuickWatchPresentation.timeLeft.Text = timeLeft_message;
186                        quadraticSieveQuickWatchPresentation.factorInfo.Content = "";
187                    }
188                    , null);
189
190                    Debug.Assert(factorManager.CalculateNumber() == InputNumber);
191                    OutputFactors = factorManager.getPrimeFactors();
192                }
193                else
194                {
195                    timeLeft_message = "0 sec left";
196                    endtime_message = "Stopped";
197                    logging_message = "Stopped by user!";
198
199                    GuiLogMessage(logging_message, NotificationLevel.Info);
200                    quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
201                    {
202                        quadraticSieveQuickWatchPresentation.logging.Text = logging_message;
203                        quadraticSieveQuickWatchPresentation.endTime.Text = endtime_message;
204                        quadraticSieveQuickWatchPresentation.timeLeft.Text = timeLeft_message;
205                        quadraticSieveQuickWatchPresentation.factorInfo.Content = "";
206                    }
207                    , null);
208                }
209                   
210                ProgressChanged(1, 1);
211               
212            }
213        }
214       
215        /// <summary>
216        /// Called by the environment after execution
217        /// </summary>
218        public void PostExecution()
219        {
220        }
221
222        /// <summary>
223        /// Called by the environment to pause execution
224        /// </summary>
225        public void Pause()
226        {
227        }
228
229        /// <summary>
230        /// Called by the environment to stop execution
231        /// </summary>
232        public void Stop()
233        {
234            this.userStopped = true;
235            if (obj != IntPtr.Zero)
236            {
237                stopThreads();
238                MethodInfo stop = msieve.GetMethod("stop");
239                stop.Invoke(null, new object[] { obj });
240            }
241
242        }
243
244        /// <summary>
245        /// Called by the environment to initialize this plugin
246        /// </summary>
247        public void Initialize()
248        {
249        }
250
251        /// <summary>
252        /// Called by the environment to dispose this plugin
253        /// </summary>
254        public void Dispose()
255        {
256        }
257
258        /// <summary>
259        /// Getter / Setter for the input number which should be factorized
260        /// </summary>
261        [PropertyInfo(Direction.InputData, "Number input", "Enter the number you want to factorize", "", DisplayLevel.Beginner)]
262        public BigInteger InputNumber
263        {
264            get
265            {
266                return inputNumber;
267            }
268            set
269            {
270                this.inputNumber = value;
271                OnPropertyChanged("InputNumber");
272            }
273        }
274
275        /// <summary>
276        /// Getter / Setter for the factors calculated by msieve
277        /// </summary>
278        [PropertyInfo(Direction.OutputData, "Factors output", "Your factors will be sent here", "", DisplayLevel.Beginner)]
279        public BigInteger[] OutputFactors
280        {
281            get
282            {
283                return outputFactors;
284            }
285            set
286            {
287                this.outputFactors = value;
288                OnPropertyChanged("OutputFactors");
289            }
290        }
291       
292        /// <summary>
293        /// Called when a property of this plugin changes
294        /// </summary>
295        /// <param name="name">name</param>
296        public void OnPropertyChanged(string name)
297        {
298            EventsHelper.PropertyChanged(PropertyChanged, this, new PropertyChangedEventArgs(name));
299        }
300
301        /// <summary>
302        /// Getter / Setter for the presentation of this plugin
303        /// </summary>
304        public UserControl Presentation { get; private set; }
305
306        /// <summary>
307        /// Getter / Setter for the QuickWatchPresentation of this plugin
308        /// </summary>
309        public UserControl QuickWatchPresentation
310        {
311            get;
312            private set;
313        }
314
315        #endregion
316
317        #region private
318
319        /// <summary>
320        /// calculate a String which shows the timespan
321        ///
322        /// example
323        ///
324        ///     4 days
325        /// or
326        ///     2 minutes
327        /// </summary>
328        /// <param name="ts"></param>
329        /// <returns></returns>
330        private String showTimeSpan(TimeSpan ts)
331        {
332            String res = "";
333            if (ts.Days != 0)
334                res = ts.Days + " days ";
335            if (ts.Hours != 0 || res.Length != 0)
336                res += ts.Hours + " hours ";
337            if (ts.Minutes != 0)
338                res += ts.Minutes + " minutes";
339            if (res.Length == 0)
340                res += ts.Seconds + " seconds";
341            return res;
342        }
343
344        /// <summary>
345        /// Callback method to prepare sieving
346        /// Called by msieve
347        ///
348        /// </summary>
349        /// <param name="conf">pointer to configuration</param>
350        /// <param name="update">number of relations found</param>
351        /// <param name="core_sieve_fcn">pointer to internal sieve function of msieve</param>
352        private void prepareSieving(IntPtr conf, int update, IntPtr core_sieve_fcn, int max_relations)
353        {
354            int threads = Math.Min(settings.CoresUsed, Environment.ProcessorCount-1);
355            MethodInfo getObjFromConf = msieve.GetMethod("getObjFromConf");
356            this.obj = (IntPtr)getObjFromConf.Invoke(null, new object[] { conf });           
357            yieldqueue = Queue.Synchronized(new Queue());
358            conf_list = new ArrayList();
359
360            String message = "Start sieving using " + (threads + 1) + " cores!";
361            GuiLogMessage(message, NotificationLevel.Info);
362            quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
363            {
364                quadraticSieveQuickWatchPresentation.logging.Text = message;
365            }
366            , null);         
367
368            ProgressChanged(0.1, 1.0);
369
370            running = true;
371            //start helper threads:
372            for (int i = 0; i < threads+1; i++)
373            {
374                MethodInfo cloneSieveConf = msieve.GetMethod("cloneSieveConf");
375                IntPtr clone = (IntPtr)cloneSieveConf.Invoke(null, new object[] { conf });               
376                conf_list.Add(clone);
377                WaitCallback worker = new WaitCallback(MSieveJob);
378                ThreadPool.QueueUserWorkItem(worker, new object[] { clone, update, core_sieve_fcn, yieldqueue });
379            }
380
381            //manage the yields of the other threads:
382            manageYields(conf, max_relations);  //this method returns as soon as there are enough relations found
383            if (userStopped)
384                return;
385
386            //sieving is finished now, so give some informations and stop threads:
387            GuiLogMessage("Data size: " + (sumSize / 1024) / 1024 + " MB!", NotificationLevel.Debug);
388            ProgressChanged(0.9, 1.0);
389            GuiLogMessage("Sieving finished", NotificationLevel.Info);
390            quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
391            {
392                quadraticSieveQuickWatchPresentation.factorInfo.Content = "Found enough relations! Please wait...";
393            }, null);
394            stopThreads();
395            if (yieldqueue != null)
396                yieldqueue.Clear();
397        }
398
399        private void manageYields(IntPtr conf, int max_relations)
400        {
401            MethodInfo serializeYield = msieve.GetMethod("serializeYield");
402            MethodInfo getNumRelations = msieve.GetMethod("getNumRelations");
403            int num_relations = (int)getNumRelations.Invoke(null, new object[] { conf });
404            int start_relations = num_relations;
405            DateTime start_sieving_time = DateTime.Now;
406            MethodInfo saveYield = msieve.GetMethod("saveYield");
407
408            while (num_relations < max_relations)
409            {
410                ProgressChanged((double)num_relations / max_relations * 0.8 + 0.1, 1.0);
411               
412                yieldEvent.WaitOne();               //wait until queue is not empty
413                if (userStopped)
414                    return;
415                while (yieldqueue.Count != 0)       //get all the results from the helper threads, and store them
416                {
417                    IntPtr yield = (IntPtr)yieldqueue.Dequeue();
418                    byte[] serializedYield = (byte[])serializeYield.Invoke(null, new object[] { yield });                   
419
420                    int compressedSize = peerToPeer.put(serializedYield);
421                    sumSize += compressedSize;
422
423                    saveYield.Invoke(null, new object[] { conf, yield });
424                }
425                num_relations = (int)getNumRelations.Invoke(null, new object[] { conf });
426                showProgressPresentation(max_relations, num_relations, start_relations, start_sieving_time);
427            }           
428        }
429
430        private void showProgressPresentation(int max_relations, int num_relations, int start_relations, DateTime start_sieving_time)
431        {
432            TimeSpan diff = DateTime.Now - start_sieving_time;
433            double msleft = (diff.TotalMilliseconds / (num_relations - start_relations)) * (max_relations - num_relations);
434            if (msleft > 0)
435            {
436                TimeSpan ts = new TimeSpan(0, 0, 0, 0, (int)msleft);
437                String logging_message = "Found " + num_relations + " of " + max_relations + " relations!";
438                String timeLeft_message = showTimeSpan(ts) + " left";
439                String endtime_message = "" + DateTime.Now.AddMilliseconds((long)msleft);
440
441                GuiLogMessage(logging_message + " " + timeLeft_message + ".", NotificationLevel.Debug);
442                quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
443                {
444                    quadraticSieveQuickWatchPresentation.logging.Text = logging_message;
445                    quadraticSieveQuickWatchPresentation.timeLeft.Text = timeLeft_message;
446                    quadraticSieveQuickWatchPresentation.endTime.Text = endtime_message;
447                }
448                , null);
449            }
450        }
451
452        /// <summary>
453        /// 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
454        /// using the quadratic sieve algorithm).
455        /// The method then factors all the factors that are still composite by using the quadratic sieve.
456        /// </summary>
457        private void getTrivialFactorlist(IntPtr list, IntPtr obj)
458        {
459            //add the trivial factors to the factor list:
460            factorManager.AddFactors(list);
461
462            MethodInfo msieve_run_core = msieve.GetMethod("msieve_run_core");
463
464            //Now factorize as often as needed:
465            while (!factorManager.OnlyPrimes())
466            {
467                //get one composite factor, which we want to sieve now:
468                BigInteger compositeFactor = factorManager.GetCompositeFactor();
469                quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
470                {
471                    quadraticSieveQuickWatchPresentation.factorInfo.Content = "Now sieving first composite factor!";
472                }, null);
473
474                //now start quadratic sieve on it:               
475                IntPtr resultList = (IntPtr)msieve_run_core.Invoke(null, new object[2] { obj, compositeFactor.ToString() });
476                if (userStopped)
477                    return;
478                factorManager.ReplaceCompositeByFactors(compositeFactor, resultList);
479            }
480        }
481
482        /// <summary>
483        /// Helper Thread for msieve, which sieves for relations:
484        /// </summary>
485        /// <param name="param">params</param>
486        private void MSieveJob(object param)
487        {
488            threadcount++;
489            object[] parameters = (object[])param;
490            IntPtr clone = (IntPtr)parameters[0];
491            int update = (int)parameters[1];
492            IntPtr core_sieve_fcn = (IntPtr)parameters[2];
493            Queue yieldqueue = (Queue)parameters[3];
494
495            while (running)
496            {
497                try
498                {
499                    MethodInfo collectRelations = msieve.GetMethod("collectRelations");
500                    collectRelations.Invoke(null, new object[] { clone, update, core_sieve_fcn });
501                    MethodInfo getYield = msieve.GetMethod("getYield");
502                    IntPtr yield = (IntPtr)getYield.Invoke(null, new object[] { clone });
503
504                    yieldqueue.Enqueue(yield);
505                    yieldEvent.Set();
506                }
507                catch (Exception ex)
508                {
509                    GuiLogMessage("Error using msieve." + ex.Message, NotificationLevel.Error);
510                    threadcount = 0;
511                    return;
512                }               
513            }
514
515            MethodInfo freeSieveConf = msieve.GetMethod("freeSieveConf");
516            freeSieveConf.Invoke(null, new object[] { clone });           
517            threadcount--;
518        }       
519
520        /// <summary>
521        /// Stop all running threads
522        /// </summary>
523        private void stopThreads()
524        {
525            if (conf_list != null)
526            {
527                running = false;
528                MethodInfo stop = msieve.GetMethod("stop");
529                MethodInfo getObjFromConf = msieve.GetMethod("getObjFromConf");
530                foreach (IntPtr conf in conf_list)
531                    stop.Invoke(null, new object[] { getObjFromConf.Invoke(null, new object[] { conf }) });
532                GuiLogMessage("Waiting for threads to stop!", NotificationLevel.Debug);
533                while (threadcount > 0)
534                {
535                    Thread.Sleep(0);
536                }
537                GuiLogMessage("Threads stopped!", NotificationLevel.Debug);
538                conf_list.Clear();
539            }
540        }   
541
542        /// <summary>
543        /// Change the progress of this plugin
544        /// </summary>
545        /// <param name="value">value</param>
546        /// <param name="max">max</param>
547        private void ProgressChanged(double value, double max)
548        {
549            EventsHelper.ProgressChanged(OnPluginProgressChanged, this, new PluginProgressEventArgs(value, max));
550        }
551
552        private void FactorsChanged(List<BigInteger> primeFactors, List<BigInteger> compositeFactors)
553        {
554            quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
555            {
556                quadraticSieveQuickWatchPresentation.factorList.Items.Clear();
557
558                foreach (BigInteger pf in primeFactors)         
559                    quadraticSieveQuickWatchPresentation.factorList.Items.Add("Prime Factor: " + pf.ToString());           
560
561                foreach (BigInteger cf in compositeFactors)
562                    quadraticSieveQuickWatchPresentation.factorList.Items.Add("Composite Factor: " + cf.ToString());
563            }, null);
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        /// <summary>
585        /// dynamically loads the msieve dll file and sets the callbacks
586        /// </summary>
587        private void initMsieveDLL()
588        {
589            //Load msieve.dll (if necessary):
590            if (msieve == null || msieveDLL == null)
591            {
592                string s = Directory.GetCurrentDirectory();
593                string dllname;
594                string relPath;
595                if (IntPtr.Size == 4)
596                {
597                    dllname = "msieve.dll";
598                    relPath = "x86";
599                }
600                else
601                {
602                    dllname = "msieve64.dll";
603                    relPath = "x64";
604                }
605                msieveDLL = Assembly.LoadFile(Directory.GetCurrentDirectory() + "\\AppReferences\\"  + relPath + "\\" + dllname);
606                msieve = msieveDLL.GetType("Msieve.msieve");
607            }
608
609            //init msieve with callbacks:
610            MethodInfo initMsieve = msieve.GetMethod("initMsieve");
611            Object callback_struct = Activator.CreateInstance(msieveDLL.GetType("Msieve.callback_struct"));           
612            FieldInfo prepareSievingField = msieveDLL.GetType("Msieve.callback_struct").GetField("prepareSieving");
613            FieldInfo getTrivialFactorlistField = msieveDLL.GetType("Msieve.callback_struct").GetField("getTrivialFactorlist");           
614            Delegate prepareSievingDel = MulticastDelegate.CreateDelegate(msieveDLL.GetType("Msieve.prepareSievingDelegate"), this, "prepareSieving");
615            Delegate getTrivialFactorlistDel = MulticastDelegate.CreateDelegate(msieveDLL.GetType("Msieve.getTrivialFactorlistDelegate"), this, "getTrivialFactorlist");           
616            prepareSievingField.SetValue(callback_struct, prepareSievingDel);
617            getTrivialFactorlistField.SetValue(callback_struct, getTrivialFactorlistDel);
618            initMsieve.Invoke(null, new object[1] { callback_struct });
619        }
620        #endregion
621
622    }
623}
Note: See TracBrowser for help on using the repository browser.