changelog shortlog tags branches files raw gz bz2 help

Mercurial > hg > ventivac / changeset: better rabin params. prevent rabin.b from generating some bad patterns (mostly all zeros except last byte, which is a \x01).

changeset 92: 643f8b37e8c6
parent 91: e5c65c1a6221
child 93: e90e73b6c2e7
author: Mechiel Lukkien <mechiel@ueber.net>
date: Thu, 26 Jul 2007 11:28:58 +0200
files: appl/cmd/rabinparams.b appl/cmd/testrabin.b appl/cmd/vacput.b appl/cmd/venti/put.b appl/lib/rabin.b
description: better rabin params. prevent rabin.b from generating some bad patterns (mostly all zeros except last byte, which is a \x01).
     1.1--- a/appl/cmd/rabinparams.b	Thu Jul 26 10:16:14 2007 +0200
     1.2+++ b/appl/cmd/rabinparams.b	Thu Jul 26 11:28:58 2007 +0200
     1.3@@ -37,8 +37,8 @@
     1.4 	rabin->init(bufio);
     1.5 
     1.6 	prime = 269;
     1.7-	mod = 1<<10;
     1.8-	width = 3;
     1.9+	mod = 8*1024;
    1.10+	width = 31;
    1.11 	min = 1024;
    1.12 	max = 32*1024;
    1.13 
     2.1--- a/appl/cmd/testrabin.b	Thu Jul 26 10:16:14 2007 +0200
     2.2+++ b/appl/cmd/testrabin.b	Thu Jul 26 11:28:58 2007 +0200
     2.3@@ -33,8 +33,8 @@
     2.4 	rabin->init(bufio);
     2.5 
     2.6 	p := 269;
     2.7-	m := 1<<13;
     2.8-	n := 3;
     2.9+	m := 8*1024;
    2.10+	n := 31;
    2.11 	min := 1024;
    2.12 	max := 32*1024;
    2.13 
     3.1--- a/appl/cmd/vacput.b	Thu Jul 26 10:16:14 2007 +0200
     3.2+++ b/appl/cmd/vacput.b	Thu Jul 26 11:28:58 2007 +0200
     3.3@@ -56,8 +56,8 @@
     3.4 
     3.5 	# xxx hardcoded for now
     3.6 	prime := 269;
     3.7-	mod := 1<<10;
     3.8-	width := 3;
     3.9+	mod := 8*1024;
    3.10+	width := 31;
    3.11 	blockmin = 1024;
    3.12 	blockmax = 32*1024;
    3.13 
     4.1--- a/appl/cmd/venti/put.b	Thu Jul 26 10:16:14 2007 +0200
     4.2+++ b/appl/cmd/venti/put.b	Thu Jul 26 11:28:58 2007 +0200
     4.3@@ -47,8 +47,8 @@
     4.4 
     4.5 	# xxx hardcoded for now
     4.6 	prime := 269;
     4.7-	mod := 1<<10;
     4.8-	width := 3;
     4.9+	mod := 8*1024;
    4.10+	width := 31;
    4.11 	blockmin := 1024;
    4.12 	blockmax := 32*1024;
    4.13 
     5.1--- a/appl/lib/rabin.b	Thu Jul 26 10:16:14 2007 +0200
     5.2+++ b/appl/lib/rabin.b	Thu Jul 26 11:28:58 2007 +0200
     5.3@@ -30,13 +30,13 @@
     5.4 		return (nil, "mod is not power of 2");
     5.5 
     5.6 	power := modpower(prime, width, mod);
     5.7-say(sprint("power=%d", power));
     5.8+if(debug) say(sprint("power=%d", power));
     5.9 
    5.10 	for(i := 0; i < 256; i++) {
    5.11 		rcfg.tab[i] = (i * power) & (mod-1);
    5.12-say(sprint("tab[%d] = %d", i, rcfg.tab[i]));
    5.13+if(debug) say(sprint("tab[%d] = %d", i, rcfg.tab[i]));
    5.14 	}
    5.15-say(sprint("mod=%d prime=%d width=%d", rcfg.mod, rcfg.prime, rcfg.width));
    5.16+if(debug) say(sprint("mod=%d prime=%d width=%d", rcfg.mod, rcfg.prime, rcfg.width));
    5.17 	return (rcfg, nil);
    5.18 }
    5.19 
    5.20@@ -49,7 +49,7 @@
    5.21 		return (nil, "min < width");
    5.22 	c := ref Rfile(b, rcfg, min, max, array[max+rcfg.width] of byte, 0, 0, big 0);
    5.23 
    5.24-say(sprint("min=%d max=%d", min, max));
    5.25+if(debug) say(sprint("min=%d max=%d", min, max));
    5.26 
    5.27 	(prime, width, mod) := (c.rcfg.prime, c.rcfg.width, c.rcfg.mod);
    5.28 	while(c.n < width) {
    5.29@@ -59,11 +59,11 @@
    5.30 		if(ch == EOF)
    5.31 			break;
    5.32 		c.buf[c.n] = byte ch;
    5.33-say(sprint("i=%d prev=%d width=%d data[i]=%d prime=%d mod=%d", c.n, c.state, width, int c.buf[c.n], prime, mod));
    5.34+if(debug) say(sprint("i=%d prev=%d width=%d data[i]=%d prime=%d mod=%d", c.n, c.state, width, int c.buf[c.n], prime, mod));
    5.35 		c.state = (prime*c.state + ch) & (mod-1);
    5.36 		c.n++;
    5.37 	}
    5.38-say(sprint("initial state=%d", c.state));
    5.39+if(debug) say(sprint("initial state=%d", c.state));
    5.40 	return (c, nil);
    5.41 }
    5.42 
    5.43@@ -82,13 +82,9 @@
    5.44 			return (d, off, nil);
    5.45 		}
    5.46 		c.buf[c.n] = byte ch;
    5.47-		new := (mod+prime*c.state + ch - c.rcfg.tab[int c.buf[c.n-width]]) & (mod-1);
    5.48-		blah := mod+prime*c.state + ch - c.rcfg.tab[int c.buf[c.n-width]];
    5.49-		if(blah < 0)
    5.50-			raise sprint("fail:blah=%d", blah);
    5.51+		c.state = (mod+prime*c.state + ch - c.rcfg.tab[int c.buf[c.n-width]]) & (mod-1);
    5.52 		c.n++;
    5.53-		c.state = new;
    5.54-		if(c.n-width >= c.max || (c.n-width >= c.min && new == 1)) {
    5.55+		if(c.n-width >= c.max || (c.n-width >= c.min && c.state == mod-1)) {
    5.56 			d := array[c.n-width] of byte;
    5.57 			d[:] = c.buf[:len d];
    5.58 			off := c.off;