20120304-2330

3 files changed, 91 insertions, 0 deletions

diff --git a/appl/lib/mkfile b/appl/lib/mkfile
index 279ca1ac..50806482 100644
--- a/appl/lib/mkfile
+++ b/appl/lib/mkfile
@@ -91,6 +91,7 @@ TARG=\
 	profile.dis\
 	pslib.dis\
 	quicktime.dis\
+	rabin.dis\
 	rand.dis\
 	random.dis\
 	readdir.dis\
diff --git a/appl/lib/rabin.b b/appl/lib/rabin.b
new file mode 100644
index 00000000..6a33011a
--- /dev/null
+++ b/appl/lib/rabin.b
@@ -0,0 +1,85 @@
+implement Rabin;
+
+include "sys.m";
+	sys: Sys;
+include "bufio.m";
+	bufio: Bufio;
+	Iobuf, EOF, ERROR: import bufio;
+include "rabin.m";
+
+sprint: import sys;
+
+init(b: Bufio)
+{
+	sys = load Sys Sys->PATH;
+	bufio = b;
+}
+
+modpower(base, n, mod: int): int
+{
+	power := 1;
+	for(i := 0; i < n; i++)
+		power = (power * base) % mod;
+	return power;
+}
+
+Rcfg.mk(prime, width, mod: int): (ref Rcfg, string)
+{
+	rcfg := ref Rcfg(prime, width, mod, array[256] of int);
+	power := modpower(prime, width, mod);
+	for(i := 0; i < 256; i++)
+		rcfg.tab[i] = (i * power) % mod;
+	return (rcfg, nil);
+}
+
+
+open(rcfg: ref Rcfg, b: ref Iobuf, min, max: int): (ref Rfile, string)
+{
+	if(min > max)
+		return (nil, sprint("bad min/max"));
+	if(min < rcfg.width)
+		return (nil, "min < width");
+	r := ref Rfile(b, rcfg, min, max, array[max+rcfg.width] of byte, 0, 0, big 0);
+
+	(prime, width, mod) := (r.rcfg.prime, r.rcfg.width, r.rcfg.mod);
+	while(r.n < width) {
+		ch := r.b.getb();
+		if(ch == ERROR)
+			return (nil, sprint("reading: %r"));
+		if(ch == EOF)
+			break;
+		r.buf[r.n] = byte ch;
+		r.state = (prime*r.state + ch) % mod;
+		r.n++;
+	}
+	return (r, nil);
+}
+
+Rfile.read(r: self ref Rfile): (array of byte, big, string)
+{
+	(prime, width, mod) := (r.rcfg.prime, r.rcfg.width, r.rcfg.mod);
+	for(;;) {
+		ch := r.b.getb();
+		if(ch == ERROR)
+			return (nil, big 0, sprint("reading: %r"));
+		if(ch == EOF) {
+			d := r.buf[:r.n];
+			off := r.off;
+			r.n = 0;
+			r.off += big len d;
+			return (d, off, nil);
+		}
+		r.buf[r.n] = byte ch;
+		r.state = (mod+prime*r.state + ch - r.rcfg.tab[int r.buf[r.n-width]]) % mod;
+		r.n++;
+		if(r.n-width >= r.max || (r.n-width >= r.min && r.state == mod-1)) {
+			d := array[r.n-width] of byte;
+			d[:] = r.buf[:len d];
+			off := r.off;
+			r.buf[:] = r.buf[r.n-width:r.n];
+			r.n = width;
+			r.off += big len d;
+			return (d, off, nil);
+		}
+	}
+}
diff --git a/appl/lib/styxservers.b b/appl/lib/styxservers.b
index 034cd4b7..0f60699d 100644
--- a/appl/lib/styxservers.b
+++ b/appl/lib/styxservers.b
@@ -100,6 +100,11 @@ Fid.open(c: self ref Fid, mode: int, qid: Sys->Qid)
 	c.qtype = qid.qtype;
 }
 
+Styxserver.error(srv: self ref Styxserver, m: ref Tmsg, msg: string)
+{
+	srv.reply(ref Rmsg.Error(m.tag, msg));
+}
+
 Styxserver.reply(srv: self ref Styxserver, m: ref Rmsg): int
 {
 	if(debug)