[minion-cvs] Make FEC wrappers work; add tests and benchmarks.

[nickm@seul.org (Nick Mathewson)]

Update of /home/minion/cvsroot/src/minion/lib/mixminion
In directory moria.mit.edu:/tmp/cvs-serv17806/lib/mixminion

Modified Files:
	benchmark.py test.py 
Log Message:
Make FEC wrappers work; add tests and benchmarks.

The new code jumps through some hoops to never allocate more string
than we need - it makes the wrapper code a little hairier, but it
speeds up the runtime by up to a factor of 4.



Index: benchmark.py
===================================================================
RCS file: /home/minion/cvsroot/src/minion/lib/mixminion/benchmark.py,v
retrieving revision 1.42
retrieving revision 1.43
diff -u -d -r1.42 -r1.43
--- benchmark.py	6 Jun 2003 07:54:46 -0000	1.42
+++ benchmark.py	8 Jul 2003 18:38:24 -0000	1.43
@@ -724,7 +724,30 @@
     t = time()-t1
     print "          (sync)", timestr(t/100)
 
+#----------------------------------------------------------------------
+def fecTiming():
+    print "#================= FEC =========================="
 
+    r = getCommonPRNG()
+    for k,n,it in [(5,10,1000),
+                   (20,25,300),
+                   (30,40,100),
+                   (40,50,100)
+                   ]:
+        print "FEC (%s/%s)"%(k,n)
+        msg = [ r.getBytes(28*1024) for i in xrange(k) ]
+        fec = _ml.FEC_generate(k,n)
+        tm = timeit_(lambda f=fec, m=msg,k=k: f.encode(k+1,m), it)
+        print "Encode a single 28KB check block:", timestr(tm)
+        print "                (time/(k*28KB)) =", timestr(tm/(k*28)), "/ KB"
+        missing_1 = [ (i, fec.encode(i,msg)) for i in xrange(1,k+1) ]
+        missing_max = [ (i, fec.encode(i,msg)) for i in xrange(n-k,n) ]
+        tm = timeit_(lambda f=fec, m=missing_1: f.decode(m), it)
+        print "              Decode (1 missing):", timestr(tm)
+        print "              (time/(k*28KB*1)) =", timestr(tm/(k*28)), "/ KB"
+        tm = timeit_(lambda f=fec, m=missing_max: f.decode(m), it)
+        print "            Decode (k-n missing):", timestr(tm)
+        print "          (time/(k*28KB*(n-k))) =", timestr(tm/(k*28*(n-k))), "/ KB"
 #----------------------------------------------------------------------
 def testLeaks1():
     print "Trying to leak (sha1,aes,xor,seed,oaep)"
@@ -968,12 +991,20 @@
         tls.shutdown()
         sock.close()
 
+def testLeaks_FEC():
+    inp = [ "aaaaa"*1024, "bbbbb"*1024, "ccccc"*1024 ]
+    while 1:
+        fec = _ml.FEC_generate(3,5)
+        chunks = [ fec.encode(i, inp) for i in xrange(5) ]
+        dec = fec.decode([(i, chunks[i]) for i in xrange(2,5) ])
+
 #----------------------------------------------------------------------
 def timeAll(name, args):
     if 0:
-        testLeaks5_send()
+        testLeaks_FEC()
         return
-    
+
+    fecTiming()    
     cryptoTiming()
     rsaTiming()
     buildMessageTiming()

Index: test.py
===================================================================
RCS file: /home/minion/cvsroot/src/minion/lib/mixminion/test.py,v
retrieving revision 1.131
retrieving revision 1.132
diff -u -d -r1.131 -r1.132
--- test.py	7 Jul 2003 23:46:51 -0000	1.131
+++ test.py	8 Jul 2003 18:38:25 -0000	1.132
@@ -842,29 +842,36 @@
 
 #----------------------------------------------------------------------
 class MinionlibFECTests(unittest.TestCase):
-    def test_good_fec(self):
-        eq = self.assertEquals
-        f3_5 = _ml.FEC_generate(3,5)
-        eq((3,5), f3_5.getParameters())
-        inp = [ "Amidst the mists   ",
-                "and coolests frosts",
-                "with barest wrists " ]
+    def do_fec_test(self, k, n, sz):
+        r = getCommonPRNG()
 
-        eq(inp[0], f3_5.encode(0, inp))
-        eq(inp[1], f3_5.encode(1, inp))
-        eq(inp[2], f3_5.encode(2, inp))
-                
-        ch1 = f3_5.encode(3, inp)
-        ch2 = f3_5.encode(4, inp)
-        
-        print inp
+        eq = self.assertEquals
+        fec = _ml.FEC_generate(k,n)
+        eq((k,n), fec.getParameters())
 
-        eq("".join(inp), f3_5.decode([(0, inp[0]), (1, inp[1]), (2, inp[2])]))
-        print inp
-        eq("".join(inp), f3_5.decode([(0, inp[0]), (1, inp[1]), (3, ch1)]))
+        inpChunks = [ r.getBytes(sz) for i in xrange(k) ]
+        inp = "".join(inpChunks)
+        outChunks = [ fec.encode(i, inpChunks) for i in xrange(n) ]
+        for i in xrange(n):
+            if n < k:
+                eq(outChunks[i], inChunks[i])
+            eq(len(outChunks[i]), sz)
 
-        print "HERE"
+        numberedChunks = [ (i, outChunks[i]) for i in xrange(n) ]
 
+        for i in xrange(200):
+            chk = r.shuffle(numberedChunks, k)
+            #print [ i for i,_ in chk ]
+            out = fec.decode(chk)
+            eq(out, inpChunks)
+            eq("".join(out), inp)
+          
+    def test_good_fec(self):
+        self.do_fec_test(3,5,10)
+        self.do_fec_test(10,20,1024)
+        self.do_fec_test(30,40,1024)
+        self.do_fec_test(3,4,128)
+        self.do_fec_test(3,3,2048)
 
 #----------------------------------------------------------------------