1.1 --- a/apps/sort.py	Sat Aug 09 15:09:19 2008 +0200
     1.2 +++ b/apps/sort.py	Tue Aug 19 17:35:42 2008 +0200
     1.3 @@ -40,10 +40,11 @@
     1.4  #
     1.5  # http://iti.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/bitonicen.htm
     1.6  #
     1.7 +# It requires ProgressBar v. 2.2 found on
     1.8 +# http://pypi.python.org/pypi/progressbar/
     1.9 +#
    1.10  # TODO: Predict the number of comparisons and support preprocessing.
    1.11  #
    1.12 -# TODO: With the number comparisons known we could provide a progress
    1.13 -# bar using this library: http://pypi.python.org/pypi/progressbar/
    1.14  
    1.15  # Give a player configuration file as a command line argument or run
    1.16  # the example with '--help' for help with the command line options.
    1.17 @@ -52,6 +53,8 @@
    1.18  from optparse import OptionParser
    1.19  from twisted.internet import reactor
    1.20  
    1.21 +from progressbar import ProgressBar, Percentage, Bar, ETA, ProgressBarWidget
    1.22 +
    1.23  from viff.field import GF
    1.24  from viff.runtime import Runtime, create_runtime, gather_shares
    1.25  from viff.comparison import Toft07Runtime
    1.26 @@ -66,6 +69,9 @@
    1.27                    help="array size")
    1.28  parser.add_option("-m", "--max", type="int",
    1.29                    help="maximum size of array numbers")
    1.30 +parser.add_option("-t", "--test", default=False, action="store_true",
    1.31 +                  help="run doctests on this file")
    1.32 +
    1.33  parser.set_defaults(modulus=2**65, size=8, max=100)
    1.34  
    1.35  Runtime.add_options(parser)
    1.36 @@ -77,9 +83,26 @@
    1.37  
    1.38  Zp = GF(find_prime(options.modulus, blum=True))
    1.39  
    1.40 +
    1.41  class Protocol:
    1.42  
    1.43 +    def setup_progress_bar(self):
    1.44 +
    1.45 +        class HowManyWidget(ProgressBarWidget):
    1.46 +            "Showing the number of finished comparisons/total number"
    1.47 +
    1.48 +            def update(self, pbar):
    1.49 +                return "Comparisons %s/%s" % (pbar.currval, pbar.maxval)
    1.50 +
    1.51 +        widgets = ['Sorting: ', Percentage(), ' ',
    1.52 +                   Bar(marker='0', left='[', right=']'),
    1.53 +                   ' ', ETA(), ' ', HowManyWidget()]
    1.54 +        return ProgressBar(
    1.55 +            widgets = widgets,
    1.56 +            maxval = Protocol.predict_sort(options.size))
    1.57 +
    1.58      def __init__(self, runtime):
    1.59 +        self.progressbar = self.setup_progress_bar()
    1.60          self.rt = runtime
    1.61          self.comparisons = 0
    1.62  
    1.63 @@ -89,19 +112,51 @@
    1.64          array = gather_shares(map(runtime.open, array))
    1.65          sorted = gather_shares(map(runtime.open, sorted))
    1.66  
    1.67 -        dprint("Original array: %s", array)
    1.68 -        dprint("Sorted array:   %s", sorted)
    1.69 +        self.progressbar.start()
    1.70  
    1.71 -        def finish(_):
    1.72 +        def finish(result):
    1.73 +            self.progressbar.finish()
    1.74 +            print # This line goes on top of the progressbar
    1.75 +            dprint("Original array: %s", array)
    1.76 +            dprint("Sorted array:   %s", result)
    1.77              print "Made %d comparisons" % self.comparisons
    1.78              runtime.shutdown()
    1.79 +
    1.80          sorted.addCallback(finish)
    1.81  
    1.82 +    @staticmethod
    1.83 +    def predict_sort(array_size):
    1.84 +        """ Calculate how many comparisons will be made by the bitonic
    1.85 +        sort
    1.86 +        >>> predict_sort(8)
    1.87 +        24
    1.88 +        >>> predict_sort(10)
    1.89 +        33
    1.90 +        """
    1.91 +
    1.92 +        def predict_bitonic_sort(n):
    1.93 +            if n > 1:
    1.94 +                m = n >> 1
    1.95 +                return predict_bitonic_sort(m) + \
    1.96 +                    predict_bitonic_sort(n - m) + predict_bitonic_merge(n)
    1.97 +            else:
    1.98 +                return 0
    1.99 +
   1.100 +        def predict_bitonic_merge(n):
   1.101 +            if n > 1:
   1.102 +                m = 1 << (int(floor(log(n-1, 2))))
   1.103 +                return n-m + predict_bitonic_merge(m) + \
   1.104 +                    predict_bitonic_merge(n - m)
   1.105 +            else:
   1.106 +                return 0
   1.107 +
   1.108 +        return predict_bitonic_sort(array_size)
   1.109 +
   1.110      def make_array(self):
   1.111          array = []
   1.112          for i in range(options.size):
   1.113              inputter = (i % 3) + 1
   1.114 -            if  inputter == self.rt.id:
   1.115 +            if inputter == self.rt.id:
   1.116                  number = rand.randint(1, options.max)
   1.117                  print "Sharing array[%d] = %s" % (i, number)
   1.118              else:
   1.119 @@ -132,13 +187,23 @@
   1.120                  bitonic_merge(low + m, n - m, ascending)
   1.121  
   1.122          def compare(i, j, ascending):
   1.123 -            self.comparisons += 1
   1.124 +
   1.125 +            def tick_progressbar(dummy):
   1.126 +                """This is added as a callback to the defered in le, and
   1.127 +                therefor must pass on the result of the comparison to
   1.128 +                where it is actually used"""
   1.129 +                self.comparisons += 1
   1.130 +                self.progressbar.update(self.comparisons)
   1.131 +                return dummy
   1.132  
   1.133              def xor(a, b):
   1.134                  # TODO: We use this simple xor until
   1.135                  # http://tracker.viff.dk/issue60 is fixed.
   1.136                  return a + b - 2*a*b
   1.137  
   1.138 +            le = array[i] <= array[j] # a deferred
   1.139 +            le.addCallback(tick_progressbar)
   1.140 +
   1.141              # We must swap array[i] and array[j] when they sort in the
   1.142              # wrong direction, that is, when ascending is True and
   1.143              # array[i] > array[j], or when ascending is False (meaning
   1.144 @@ -146,7 +211,7 @@
   1.145              #
   1.146              # Using array[i] <= array[j] in both cases we see that
   1.147              # this is the exclusive-or:
   1.148 -            b = xor(ascending, array[i] <= array[j])
   1.149 +            b = xor(ascending, le)
   1.150  
   1.151              # We now wish to calculate
   1.152              #
   1.153 @@ -164,15 +229,18 @@
   1.154          bitonic_sort(0, len(array), ascending=True)
   1.155          return array
   1.156  
   1.157 +# Run doctests
   1.158 +if options.test:
   1.159 +    import doctest                #pragma NO COVER
   1.160 +    doctest.testmod(verbose=True) #pragma NO COVER
   1.161  
   1.162  # Load configuration file.
   1.163  id, players = load_config(args[0])
   1.164  
   1.165  # Create a deferred Runtime and ask it to run our protocol when ready.
   1.166 -pre_runtime = create_runtime(id, players, 1, options, runtime_class=Toft07Runtime)
   1.167 +pre_runtime = create_runtime(id, players, 1,
   1.168 +                             options, runtime_class=Toft07Runtime)
   1.169  pre_runtime.addCallback(Protocol)
   1.170  
   1.171  # Start the Twisted event loop.
   1.172  reactor.run()
   1.173 -
   1.174 -