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

Last change on this file since 1916 was 1916, checked in by Sven Rech, 11 years ago

fixed quadratic sieve thread problem

File size: 39.1 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 Cryptool.PluginBase.Miscellaneous;
24using System.ComponentModel;
25using System.Threading;
26using System.IO;
27using System.Windows.Controls;
28using System.Windows.Threading;
29using System.Windows;
30using System.Reflection;
31using System.Numerics;
32using System.Collections.Generic;
33using System.Diagnostics;
34using Cryptool.P2P;
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;
53        private BigInteger inputNumber;
54        private BigInteger[] outputFactors;
55        private bool running;
56        private Queue relationPackageQueue;
57        private AutoResetEvent newRelationPackageEvent = new AutoResetEvent(false);
58        private IntPtr obj = IntPtr.Zero;
59        private volatile int threadcount = 0;
60        private ArrayList conf_list;
61        private Mutex conf_listMutex = new Mutex();
62        private bool userStopped = false;
63        private FactorManager factorManager;
64        private PeerToPeer peerToPeer;
65        private PeerToPeerStatusUpdater peerToPeerStatusUpdater;
66        private bool usePeer2Peer;
67        private bool otherPeerFinished;
68        private bool useGnuplot = false;
69        private StreamWriter gnuplotFile;
70        private double[] relationsPerMS;
71        private DateTime start_time;
72
73        private static Assembly msieveDLL = null;
74        private static Type msieve = null;
75        private static bool alreadyInUse = false;
76        private static Mutex alreadyInUseMutex = new Mutex();
77        private AutoResetEvent waitForConnection = new AutoResetEvent(false);
78
79        #endregion
80
81        #region events
82
83        public event StatusChangedEventHandler OnPluginStatusChanged;
84        public event GuiLogNotificationEventHandler OnGuiLogNotificationOccured;
85        public event PluginProgressChangedEventHandler OnPluginProgressChanged;
86        public event System.ComponentModel.PropertyChangedEventHandler PropertyChanged;
87        public event PluginProgressChangedEventHandler OnPluginProcessChanged;
88
89        #endregion
90
91        #region public
92
93        /// <summary>
94        /// Constructor
95        ///
96        /// constructs a new QuadraticSieve plugin
97        /// </summary>
98        public QuadraticSieve()
99        {
100            Settings = new QuadraticSieveSettings(this);
101
102            directoryName = Path.Combine(DirectoryHelper.DirectoryLocalTemp, "msieve");
103            if (!Directory.Exists(directoryName)) Directory.CreateDirectory(directoryName);
104
105            QuickWatchPresentation = new QuadraticSievePresentation();
106
107            peerToPeer = new PeerToPeer(quadraticSieveQuickWatchPresentation, newRelationPackageEvent);
108            peerToPeerStatusUpdater = new PeerToPeerStatusUpdater(peerToPeer);
109            peerToPeer.P2PWarning += new PeerToPeer.P2PWarningHandler(peerToPeer_P2PWarning);
110           
111            quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
112            {
113                quadraticSieveQuickWatchPresentation.peer2peer.Visibility = settings.UsePeer2Peer ? Visibility.Visible : Visibility.Collapsed;               
114                quadraticSieveQuickWatchPresentation.timeLeft.Content = "-";
115                quadraticSieveQuickWatchPresentation.endTime.Content = "-";
116                quadraticSieveQuickWatchPresentation.coresUsed.Content = "-";
117            }
118            , null);
119        }
120
121        /// <summary>
122        /// Getter / Setter for the settings of this plugin
123        /// </summary>
124        public Cryptool.PluginBase.ISettings Settings
125        {
126            get { return this.settings; }
127            set
128            {
129                this.settings = (QuadraticSieveSettings)value;
130                this.settings.PropertyChanged += new PropertyChangedEventHandler(settings_PropertyChanged);
131            }
132        }
133
134        private void settings_PropertyChanged(object sender, PropertyChangedEventArgs e)
135        {
136            if (e.PropertyName == "UsePeer2Peer")
137            {
138                if (quadraticSieveQuickWatchPresentation != null)
139                {
140                    quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
141                    {
142                        quadraticSieveQuickWatchPresentation.peer2peer.Visibility = settings.UsePeer2Peer ? Visibility.Visible : Visibility.Collapsed;                       
143                    }, null);
144                }
145            }
146        }
147
148        /// <summary>
149        /// Called by the environment before executing this plugin
150        /// </summary>
151        public void PreExecution()
152        { 
153        }
154       
155        /// <summary>
156        /// Called by the environment to execute this plugin
157        /// </summary>
158        public void Execute()
159        {
160            if (checkInUse())
161                return;
162           
163            try
164            {
165                usePeer2Peer = settings.UsePeer2Peer;
166                if (usePeer2Peer && !P2PManager.IsConnected && P2PManager.IsConnecting)
167                {
168                    P2PManager.ConnectionManager.OnP2PConnectionStateChangeOccurred += HandleConnectionStateChange;
169                    GuiLogMessage("Connecting to Peer2Peer network... Please wait!", NotificationLevel.Info);
170                    waitForConnection.WaitOne();                   
171                    P2PManager.ConnectionManager.OnP2PConnectionStateChangeOccurred -= HandleConnectionStateChange;
172                }
173                else if (usePeer2Peer && !P2PManager.IsConnected)
174                {
175                    GuiLogMessage("No connection to Peer2Peer network. Sieving locally now but waiting for connection...", NotificationLevel.Warning);
176                    P2PManager.ConnectionManager.OnP2PConnectionStateChangeOccurred += OnP2PConnectionStateChangeOccurred;
177                    usePeer2Peer = false;
178                }
179
180                if (usePeer2Peer && (settings.Channel == null ||settings.Channel.Trim() == ""))
181                {
182                    GuiLogMessage("No channel for Peer2Peer network specified. Sieving locally now!", NotificationLevel.Warning);
183                    usePeer2Peer = false;
184                }
185                if (settings.UsePeer2Peer)
186                {
187                    peerToPeer.SetChannel(settings.Channel);
188                    peerToPeer.SetNumber(InputNumber);
189                }
190
191                if (useGnuplot)
192                    gnuplotFile = new StreamWriter(Path.Combine(directoryName, "gnuplot.dat"), false);
193
194                userStopped = false;
195                otherPeerFinished = false;
196
197                if (InputNumber != 0)
198                {
199                    if (InputNumber.ToString().Length >= 275)
200                    {
201                        GuiLogMessage("Input too big.", NotificationLevel.Error);
202                        return;
203                    }
204
205                    String info_message = "Starting quadratic sieve, please wait!";
206
207                    start_time = DateTime.Now;
208
209                    GuiLogMessage(info_message, NotificationLevel.Info);
210                    quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
211                    {
212                        quadraticSieveQuickWatchPresentation.ProgressRelationPackages.Clear();
213                        quadraticSieveQuickWatchPresentation.information.Content = info_message;
214                        quadraticSieveQuickWatchPresentation.endTime.Content = "-";
215                        quadraticSieveQuickWatchPresentation.timeLeft.Content = "-";
216                        quadraticSieveQuickWatchPresentation.elapsedTime.Content = "-";
217                        quadraticSieveQuickWatchPresentation.startTime.Content = ""+start_time;
218                        quadraticSieveQuickWatchPresentation.factorList.Items.Clear();
219                        quadraticSieveQuickWatchPresentation.factorInfo.Content = "Searching trivial factors!";
220                        if (usePeer2Peer)
221                            quadraticSieveQuickWatchPresentation.localSieving.Visibility = Visibility.Hidden;
222                        else
223                            quadraticSieveQuickWatchPresentation.localSieving.Visibility = Visibility.Visible;
224                    }
225                    , null);
226
227                    initMsieveDLL();
228                    factorManager = new FactorManager(msieve.GetMethod("getPrimeFactors"), msieve.GetMethod("getCompositeFactors"), InputNumber);
229                    factorManager.FactorsChanged += this.FactorsChanged;
230
231                    //Now factorize:               
232                    try
233                    {
234                        string file = Path.Combine(directoryName, "" + InputNumber + ".dat");
235                        if (settings.DeleteCache && File.Exists(file))
236                            File.Delete(file);
237                        MethodInfo start = msieve.GetMethod("start");
238                        start.Invoke(null, new object[] { InputNumber.ToString(), file });
239                        obj = IntPtr.Zero;
240                    }
241                    catch (Exception ex)
242                    {
243                        GuiLogMessage("Error using msieve. " + ex.Message, NotificationLevel.Error);
244                        stopThreads();
245                        return;
246                    }
247
248                    if (!userStopped)
249                    {
250                        String timeLeft_message = "0 seconds left";
251                        String endtime_message = "" + (DateTime.Now);
252
253                        GuiLogMessage(info_message, NotificationLevel.Info);
254                        quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
255                        {
256                            quadraticSieveQuickWatchPresentation.information.Content = "Sieving finished!";
257                            quadraticSieveQuickWatchPresentation.endTime.Content = endtime_message;
258                            quadraticSieveQuickWatchPresentation.timeLeft.Content = timeLeft_message;
259                            quadraticSieveQuickWatchPresentation.factorInfo.Content = "";
260                        }
261                        , null);
262
263                        Debug.Assert(factorManager.CalculateNumber() == InputNumber);
264                        OutputFactors = factorManager.getPrimeFactors();
265
266                        ProgressChanged(1, 1);
267                    }
268                    else
269                    {                       
270                        info_message = "Stopped by user!";
271
272                        GuiLogMessage(info_message, NotificationLevel.Info);
273                        quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
274                        {
275                            quadraticSieveQuickWatchPresentation.information.Content = info_message;
276                            quadraticSieveQuickWatchPresentation.endTime.Content = "-";
277                            quadraticSieveQuickWatchPresentation.timeLeft.Content = "-";
278                            quadraticSieveQuickWatchPresentation.startTime.Content = "-";
279                            quadraticSieveQuickWatchPresentation.elapsedTime.Content = "-";
280                            quadraticSieveQuickWatchPresentation.factorInfo.Content = "";
281                        }
282                        , null);
283                    }
284                }
285                if (useGnuplot)
286                    gnuplotFile.Close();
287            }
288            finally
289            {
290                alreadyInUse = false;
291                P2PManager.ConnectionManager.OnP2PConnectionStateChangeOccurred -= OnP2PConnectionStateChangeOccurred;
292            }
293        }
294
295        private void OnP2PConnectionStateChangeOccurred(object sender, bool newState)
296        {
297            usePeer2Peer = newState;
298            if (usePeer2Peer)
299                GuiLogMessage("Using Peer2Peer network now!", NotificationLevel.Info);
300            else
301                GuiLogMessage("Lost Peer2Peer network connection... Sieving locally now!", NotificationLevel.Info);
302        }
303
304        private void HandleConnectionStateChange(object sender, bool newState)
305        {
306            waitForConnection.Set();
307        }
308
309        private bool checkInUse()
310        {
311            try
312            {
313                alreadyInUseMutex.WaitOne();
314                if (alreadyInUse)
315                {
316                    GuiLogMessage("QuadraticSieve plugin is only allowed to execute ones at a time due to technical restrictions.", NotificationLevel.Error);
317                    return true;
318                }
319                else
320                {
321                    alreadyInUse = true;
322                    return false;
323                }
324            }
325            finally
326            {
327                alreadyInUseMutex.ReleaseMutex();
328            }
329        }
330       
331        /// <summary>
332        /// Called by the environment after execution
333        /// </summary>
334        public void PostExecution()
335        {
336        }
337
338        /// <summary>
339        /// Called by the environment to pause execution
340        /// </summary>
341        public void Pause()
342        {
343        }
344
345        /// <summary>
346        /// Called by the environment to stop execution
347        /// </summary>
348        public void Stop()
349        {           
350            if (obj != IntPtr.Zero)
351            {
352                stopThreads();
353                MethodInfo stop = msieve.GetMethod("stop");
354                stop.Invoke(null, new object[] { obj });
355            }
356            this.userStopped = true;
357            newRelationPackageEvent.Set();
358        }
359
360        /// <summary>
361        /// Called by the environment to initialize this plugin
362        /// </summary>
363        public void Initialize()
364        {
365            settings.Initialize();
366        }
367
368        /// <summary>
369        /// Called by the environment to dispose this plugin
370        /// </summary>
371        public void Dispose()
372        {
373        }
374
375        /// <summary>
376        /// Getter / Setter for the input number which should be factorized
377        /// </summary>
378        [PropertyInfo(Direction.InputData, "Number input", "Enter the number you want to factorize", "", DisplayLevel.Beginner)]
379        public BigInteger InputNumber
380        {
381            get
382            {
383                return inputNumber;
384            }
385            set
386            {
387                this.inputNumber = value;
388                OnPropertyChanged("InputNumber");
389            }
390        }
391
392        /// <summary>
393        /// Getter / Setter for the factors calculated by msieve
394        /// </summary>
395        [PropertyInfo(Direction.OutputData, "Factors output", "Your factors will be sent here", "", DisplayLevel.Beginner)]
396        public BigInteger[] OutputFactors
397        {
398            get
399            {
400                return outputFactors;
401            }
402            set
403            {
404                this.outputFactors = value;
405                OnPropertyChanged("OutputFactors");
406            }
407        }
408       
409        /// <summary>
410        /// Called when a property of this plugin changes
411        /// </summary>
412        /// <param name="name">name</param>
413        public void OnPropertyChanged(string name)
414        {
415            EventsHelper.PropertyChanged(PropertyChanged, this, new PropertyChangedEventArgs(name));
416        }
417
418        /// <summary>
419        /// Getter / Setter for the presentation of this plugin
420        /// </summary>
421        public UserControl Presentation { get; private set; }
422
423        /// <summary>
424        /// Getter / Setter for the QuickWatchPresentation of this plugin
425        /// </summary>
426        public UserControl QuickWatchPresentation
427        {
428            get;
429            private set;
430        }
431
432        #endregion
433
434        #region private
435
436        /// <summary>
437        /// calculate a String which shows the timespan
438        ///
439        /// example
440        ///
441        ///     4 days
442        /// or
443        ///     2 minutes
444        /// </summary>
445        /// <param name="ts"></param>
446        /// <returns></returns>
447        private String timeSpanString(TimeSpan ts)
448        {
449            String res = "";
450            if (ts.Days != 0)
451                res = ts.Days + " days ";
452            if (ts.Hours != 0 || res.Length != 0)
453                res += ts.Hours + " hours ";
454            if (ts.Minutes != 0)
455                res += ts.Minutes + " minutes";
456            if (res.Length == 0)
457                res += ts.Seconds + " seconds";
458            return res;
459        }
460
461        /// <summary>
462        /// Callback method to prepare sieving
463        /// Called by msieve
464        ///
465        /// </summary>       
466        /// <param name="conf">pointer to configuration</param>
467        /// <param name="update">number of relations found</param>
468        /// <param name="core_sieve_fcn">pointer to internal sieve function of msieve</param>
469        /// <returns>true if enough relations found, false if not</returns>
470        private bool prepareSieving(IntPtr conf, int update, IntPtr core_sieve_fcn, int max_relations)
471        {
472            try
473            {
474                int threads = Math.Min(settings.CoresUsed, Environment.ProcessorCount - 1);
475                MethodInfo getObjFromConf = msieve.GetMethod("getObjFromConf");
476                this.obj = (IntPtr)getObjFromConf.Invoke(null, new object[] { conf });
477                relationPackageQueue = Queue.Synchronized(new Queue());
478                conf_list = new ArrayList();
479
480                String message = "Sieving now!";
481                GuiLogMessage(message, NotificationLevel.Info);
482                quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
483                {
484                    quadraticSieveQuickWatchPresentation.coresUsed.Content = (threads+1);
485                    quadraticSieveQuickWatchPresentation.information.Content = message;
486                    if (usePeer2Peer)
487                        quadraticSieveQuickWatchPresentation.localSieving.Visibility = Visibility.Hidden;
488                }
489                , null);
490
491                ProgressChanged(0.1, 1.0);
492
493                running = true;
494                //start helper threads:
495                relationsPerMS = new double[threads + 1];
496                for (int i = 0; i < threads + 1; i++)
497                {
498                    MethodInfo cloneSieveConf = msieve.GetMethod("cloneSieveConf");
499                    IntPtr clone = (IntPtr)cloneSieveConf.Invoke(null, new object[] { conf });
500                    conf_list.Add(clone);
501                    WaitCallback worker = new WaitCallback(MSieveJob);
502                    ThreadPool.QueueUserWorkItem(worker, new object[] { clone, update, core_sieve_fcn, relationPackageQueue, i });
503                }
504
505                //manage the relation packages of the other threads:
506                manageRelationPackages(conf, max_relations);  //this method returns as soon as there are enough relations found
507                if (userStopped)
508                    return false;
509
510                //sieving is finished now, so give some informations and stop threads:
511                ProgressChanged(0.9, 1.0);
512                GuiLogMessage("Sieving finished", NotificationLevel.Info);
513                quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
514                {
515                    quadraticSieveQuickWatchPresentation.timeLeft.Content = "-";
516                    quadraticSieveQuickWatchPresentation.endTime.Content = "-";
517                    quadraticSieveQuickWatchPresentation.factorInfo.Content = "Found enough relations! Please wait...";
518                }, null);
519
520                if (relationPackageQueue != null)
521                    relationPackageQueue.Clear();
522            }
523            catch (AlreadySievedException)
524            {
525                ProgressChanged(0.9, 1.0);
526                GuiLogMessage("Another peer already finished factorization of composite factor. Sieving next one...", NotificationLevel.Info);
527                quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
528                {
529                    quadraticSieveQuickWatchPresentation.timeLeft.Content = "-";
530                    quadraticSieveQuickWatchPresentation.endTime.Content = "-";
531                    quadraticSieveQuickWatchPresentation.factorInfo.Content = "Other peer finished sieving!";
532                }, null);
533                otherPeerFinished = true;
534                return false;
535            }
536            finally
537            {
538                stopThreads();
539            }
540            return true;
541        }
542
543        /// <summary>
544        /// Manages the whole relation packages that are created during the sieving process by the other threads (and other peers).
545        /// Returns true, if enough relations have been found.
546        /// </summary>
547        private void manageRelationPackages(IntPtr conf, int max_relations)
548        {
549            MethodInfo serializeRelationPackage = msieve.GetMethod("serializeRelationPackage");
550            MethodInfo deserializeRelationPackage = msieve.GetMethod("deserializeRelationPackage");
551            MethodInfo getNumRelations = msieve.GetMethod("getNumRelations");
552            int num_relations = (int)getNumRelations.Invoke(null, new object[] { conf });
553            int start_relations = num_relations;
554            DateTime start_sieving_time = DateTime.Now;
555            MethodInfo saveRelationPackage = msieve.GetMethod("saveRelationPackage");
556
557            while (num_relations < max_relations)
558            {
559                double progress = (double)num_relations / max_relations * 0.8 + 0.1;
560                ProgressChanged(progress, 1.0);               
561               
562                newRelationPackageEvent.WaitOne();               //wait until there is a new relation package in the queue
563                if (userStopped)
564                    return;
565
566                while (relationPackageQueue.Count != 0)       //get all the results from the helper threads, and store them
567                {
568                    IntPtr relationPackage = (IntPtr)relationPackageQueue.Dequeue();
569
570                    if (settings.UsePeer2Peer)
571                    {
572                        byte[] serializedRelationPackage = (byte[])serializeRelationPackage.Invoke(null, new object[] { relationPackage });
573                        peerToPeer.Put(serializedRelationPackage);
574                    }
575
576                    saveRelationPackage.Invoke(null, new object[] { conf, relationPackage });
577                }
578
579                if (usePeer2Peer)
580                {
581                    Queue dhtqueue = peerToPeer.GetLoadedRelationPackagesQueue();
582                    while (dhtqueue.Count != 0)       //get all the loaded results from the DHT, and store them
583                    {
584                        byte[] relationPackage = (byte[])dhtqueue.Dequeue();
585                        IntPtr deserializedRelationPackage = (IntPtr)deserializeRelationPackage.Invoke(null, new object[] { relationPackage });
586                        saveRelationPackage.Invoke(null, new object[] { conf, deserializedRelationPackage });
587                    }
588                }
589
590                num_relations = (int)getNumRelations.Invoke(null, new object[] { conf });
591                showProgressPresentation(max_relations, num_relations, start_relations, start_sieving_time);
592
593                if (usePeer2Peer && !peerToPeer.SyncFactorManager(factorManager))   //another peer already finished sieving
594                {
595                    throw new AlreadySievedException();
596                }
597            }           
598        }
599
600        private void showProgressPresentation(int max_relations, int num_relations, int start_relations, DateTime start_sieving_time)
601        {
602            double msleft = 0;
603
604            //calculate global performance in relations per ms:
605            double globalPerformance = 0;
606            foreach (double r in relationsPerMS)
607                globalPerformance += r;
608            if (usePeer2Peer)
609                globalPerformance += peerToPeer.GetP2PPerformance();
610
611            //Calculate the total time assuming that we can sieve 1 minute with the same performance:
612            double relationsCalculatableIn1Minute = 1000 * 60 * 1 * globalPerformance;
613            if (relationsCalculatableIn1Minute <= max_relations)
614            {
615                double p = ApproximatedPolynom(relationsCalculatableIn1Minute / max_relations);
616                double estimatedTotalTime = 1000 * 60 * 1 / p;
617
618                //Calculate the elapsed time assuming that we sieved with the same performance the whole time:
619                p = ApproximatedPolynom((double)num_relations / max_relations);
620                double estimatedElapsedTime = estimatedTotalTime * p;
621
622                //Calculate time left:
623                msleft = estimatedTotalTime - estimatedElapsedTime;
624            }           
625           
626            String timeLeft_message = "very soon";
627            String endtime_message = "very soon";
628            DateTime now = DateTime.Now;
629            if (msleft > 0 && !double.IsInfinity(msleft))
630            {
631                TimeSpan ts = new TimeSpan(0, 0, 0, 0, (int)msleft);
632                timeLeft_message = timeSpanString(ts) + " left";
633                endtime_message = "" + now.AddMilliseconds((long)msleft);
634            }
635
636            if (globalPerformance == 0 || double.IsInfinity(msleft))
637            {
638                timeLeft_message = "-";
639                endtime_message = "-";
640            }
641
642            quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
643            {
644                quadraticSieveQuickWatchPresentation.foundRelations.Content = num_relations;
645                quadraticSieveQuickWatchPresentation.maxRelations.Content = max_relations;
646                quadraticSieveQuickWatchPresentation.timeLeft.Content = timeLeft_message;
647                quadraticSieveQuickWatchPresentation.endTime.Content = endtime_message;
648                quadraticSieveQuickWatchPresentation.elapsedTime.Content = timeSpanString(now.Subtract(start_time));
649            }, null);
650
651            if (useGnuplot)
652            {
653                double percentage = (double)num_relations / max_relations;
654                double time = (DateTime.Now - start_sieving_time).TotalSeconds;
655                gnuplotFile.WriteLine("" + time + "\t\t" + percentage);
656            }
657        }
658
659        private static double ApproximatedPolynom(double x)
660        {
661            double a = -3.55504;
662            double b = 8.62296;
663            double c = -7.75103;
664            double d = 3.65871;
665            double progress = a * x * x * x * x + b * x * x * x + c * x * x + d * x;
666            return progress;
667        }
668
669        /// <summary>
670        /// 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
671        /// using the quadratic sieve algorithm).
672        /// The method then factors all the factors that are still composite by using the quadratic sieve.
673        /// </summary>
674        private void putTrivialFactorlist(IntPtr list, IntPtr obj)
675        {
676            if (userStopped)
677                return;
678
679            //add the trivial factors to the factor list:
680            factorManager.AddFactors(list);
681
682            if (usePeer2Peer)
683                peerToPeer.SyncFactorManager(factorManager);
684           
685            MethodInfo msieve_run_core = msieve.GetMethod("msieve_run_core");
686
687            try
688            {
689                //Now factorize as often as needed:
690                while (!factorManager.OnlyPrimes())
691                {
692                    //get one composite factor, which we want to sieve now:
693                    BigInteger compositeFactor = factorManager.GetCompositeFactor();
694                    showFactorInformations(compositeFactor);
695                    if (settings.UsePeer2Peer)
696                        peerToPeer.SetFactor(compositeFactor);
697
698                    //now start quadratic sieve on it:               
699                    IntPtr resultList = (IntPtr)msieve_run_core.Invoke(null, new object[2] { obj, compositeFactor.ToString() });
700                    if (otherPeerFinished)
701                    {
702                        otherPeerFinished = false;
703                        continue;
704                    }
705
706                    if (resultList == IntPtr.Zero)
707                        throw new NotSievableException();
708
709                    if (userStopped)
710                        return;
711
712                    factorManager.ReplaceCompositeByFactors(compositeFactor, resultList);   //add the result list to factorManager
713
714                    if (usePeer2Peer)
715                        peerToPeer.SyncFactorManager(factorManager);
716                }
717            }
718            catch (NotSievableException)
719            {
720                GuiLogMessage("This number is not sievable by msieve (maybe input too long?)", NotificationLevel.Error);
721            }
722        }
723
724        private void showFactorInformations(BigInteger compositeFactor)
725        {
726            quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
727            {
728                String compRep;
729                if (compositeFactor.ToString().Length < 50)
730                    compRep = compositeFactor.ToString();
731                else
732                    compRep = compositeFactor.ToString().Substring(0, 48) + "...";
733                quadraticSieveQuickWatchPresentation.factorInfo.Content = "Now sieving first composite factor! (" + compRep + ")";
734            }, null);
735        }
736
737        /// <summary>
738        /// Helper Thread for msieve, which sieves for relations:
739        /// </summary>
740        /// <param name="param">params</param>
741        private void MSieveJob(object param)
742        {
743            threadcount++;
744            object[] parameters = (object[])param;
745            IntPtr clone = (IntPtr)parameters[0];
746            int update = (int)parameters[1];
747            IntPtr core_sieve_fcn = (IntPtr)parameters[2];
748            Queue relationPackageQueue = (Queue)parameters[3];
749            int threadNR = (int)parameters[4];
750
751            try
752            {
753                MethodInfo collectRelations = msieve.GetMethod("collectRelations");
754                MethodInfo getRelationPackage = msieve.GetMethod("getRelationPackage");
755                MethodInfo getAmountOfRelationsInRelationPackage = msieve.GetMethod("getAmountOfRelationsInRelationPackage");
756
757                Thread.CurrentThread.Priority = ThreadPriority.BelowNormal;
758
759                while (running)
760                {
761                    try
762                    {
763                        //Calculate the performance of this thread:
764                        DateTime beginning = DateTime.Now;
765                        collectRelations.Invoke(null, new object[] { clone, update, core_sieve_fcn });
766                        IntPtr relationPackage = (IntPtr)getRelationPackage.Invoke(null, new object[] { clone });
767
768                        int amountOfFullRelations = (int)getAmountOfRelationsInRelationPackage.Invoke(null, new object[] { relationPackage });
769                        relationsPerMS[threadNR] = amountOfFullRelations / (DateTime.Now - beginning).TotalMilliseconds;
770
771                        if (usePeer2Peer)
772                            peerToPeer.SetOurPerformance(relationsPerMS);
773
774                        relationPackageQueue.Enqueue(relationPackage);
775                        newRelationPackageEvent.Set();
776                    }
777                    catch (Exception ex)
778                    {
779                        GuiLogMessage("Error using msieve." + ex.Message, NotificationLevel.Error);
780                        threadcount = 0;
781                        return;
782                    }
783                }
784
785                conf_listMutex.WaitOne();
786                if (conf_list != null)
787                    conf_list[threadNR] = null;
788                MethodInfo freeSieveConf = msieve.GetMethod("freeSieveConf");
789                freeSieveConf.Invoke(null, new object[] { clone });
790                conf_listMutex.ReleaseMutex();
791            }
792            finally
793            {
794                threadcount--;
795            }
796        }       
797
798        /// <summary>
799        /// Stop all running threads
800        /// </summary>
801        private void stopThreads()
802        {
803            if (settings.UsePeer2Peer)
804                peerToPeer.StopLoadStoreThread();
805
806            if (conf_list != null)
807            {
808                MethodInfo stop = msieve.GetMethod("stop");
809                MethodInfo getObjFromConf = msieve.GetMethod("getObjFromConf");
810
811                conf_listMutex.WaitOne();
812                foreach (Object conf in conf_list)
813                    if (conf != null)
814                        stop.Invoke(null, new object[] { getObjFromConf.Invoke(null, new object[] { (IntPtr)conf }) });
815               
816                running = false;
817
818                conf_list = null;
819                conf_listMutex.ReleaseMutex();
820
821                GuiLogMessage("Waiting for threads to stop!", NotificationLevel.Debug);
822                while (threadcount > 0)
823                {
824                    Thread.Sleep(0);
825                }
826                GuiLogMessage("Threads stopped!", NotificationLevel.Debug);
827            }
828        }   
829
830        /// <summary>
831        /// Change the progress of this plugin
832        /// </summary>
833        /// <param name="value">value</param>
834        /// <param name="max">max</param>
835        private void ProgressChanged(double value, double max)
836        {
837            EventsHelper.ProgressChanged(OnPluginProgressChanged, this, new PluginProgressEventArgs(value, max));
838            if (usePeer2Peer)
839                peerToPeerStatusUpdater.UpdateStatus(value/max);
840        }
841
842        private void FactorsChanged(List<BigInteger> primeFactors, List<BigInteger> compositeFactors)
843        {
844            quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
845            {
846                quadraticSieveQuickWatchPresentation.factorList.Items.Clear();
847
848                foreach (BigInteger pf in primeFactors)         
849                    quadraticSieveQuickWatchPresentation.factorList.Items.Add("Prime Factor: " + pf.ToString());           
850
851                foreach (BigInteger cf in compositeFactors)
852                    quadraticSieveQuickWatchPresentation.factorList.Items.Add("Composite Factor: " + cf.ToString());
853                quadraticSieveQuickWatchPresentation.SelectFirstComposite();
854            }, null);
855        }
856
857        /// <summary>
858        /// Getter / Setter for the QuickWatchPresentation
859        /// </summary>
860        private QuadraticSievePresentation quadraticSieveQuickWatchPresentation
861        {
862            get { return QuickWatchPresentation as QuadraticSievePresentation; }
863        }
864
865        /// <summary>
866        /// dynamically loads the msieve dll file and sets the callbacks
867        /// </summary>
868        private void initMsieveDLL()
869        {
870            msieveDLL = Msieve.GetMsieveDLL();
871            msieve = msieveDLL.GetType("Msieve.msieve");
872
873            //init msieve with callbacks:
874            MethodInfo initMsieve = msieve.GetMethod("initMsieve");
875            Object callback_struct = Activator.CreateInstance(msieveDLL.GetType("Msieve.callback_struct"));           
876            FieldInfo prepareSievingField = msieveDLL.GetType("Msieve.callback_struct").GetField("prepareSieving");
877            FieldInfo putTrivialFactorlistField = msieveDLL.GetType("Msieve.callback_struct").GetField("putTrivialFactorlist");           
878            Delegate prepareSievingDel = MulticastDelegate.CreateDelegate(msieveDLL.GetType("Msieve.prepareSievingDelegate"), this, "prepareSieving");
879            Delegate putTrivialFactorlistDel = MulticastDelegate.CreateDelegate(msieveDLL.GetType("Msieve.putTrivialFactorlistDelegate"), this, "putTrivialFactorlist");           
880            prepareSievingField.SetValue(callback_struct, prepareSievingDel);
881            putTrivialFactorlistField.SetValue(callback_struct, putTrivialFactorlistDel);
882            initMsieve.Invoke(null, new object[1] { callback_struct });
883        }
884
885        private void peerToPeer_P2PWarning(string warning)
886        {
887            GuiLogMessage(warning, NotificationLevel.Warning);
888        }
889
890        #endregion
891
892        #region internal
893
894        internal PeerToPeer PeerToPeer
895        {
896            get { return peerToPeer; }
897        }
898
899        internal bool Running
900        {
901            get { return running; }
902        }
903
904        /// <summary>
905        /// Logs a message to the CrypTool gui
906        /// </summary>
907        /// <param name="p">p</param>
908        /// <param name="notificationLevel">notificationLevel</param>
909        internal void GuiLogMessage(string p, NotificationLevel notificationLevel)
910        {
911            EventsHelper.GuiLogMessage(OnGuiLogNotificationOccured, this, new GuiLogEventArgs(p, this, notificationLevel));
912        }
913
914        #endregion
915
916    }
917}
Note: See TracBrowser for help on using the repository browser.