20120304-2330

28 files changed, 242 insertions, 5 deletions

diff --git a/CHANGES b/CHANGES
index d8c51e46..62ea9fc7 100644
--- a/CHANGES
+++ b/CHANGES
@@ -1,3 +1,11 @@
+20120304
+	rabin(2) added (preliminary)
+20120213
+	styxservers: add .error operation (preliminary)
+20120116
+	lib9.h: internally rename qsort as infqsort to avoid C library clash
+	lib9/qsort.c: include lib9.h
+	lib9/mkfile: move qsort to IMPORTFILES from COMMONFILES
 20120103
 	avoid re-defining isnan; use isNaN instead
 20111231
diff --git a/DragonFly/386/include/lib9.h b/DragonFly/386/include/lib9.h
index c36541e5..dc94cf2c 100644
--- a/DragonFly/386/include/lib9.h
+++ b/DragonFly/386/include/lib9.h
@@ -278,6 +278,8 @@ extern	double	modf(double, double*);
 #define	pow10	infpow10
 extern	double	pow10(int);
 extern	vlong	strtoll(const char*, char**, int);
+#define	qsort	infqsort
+extern	void	qsort(void*, long, long, int (*)(void*, void*));
 extern	uvlong	strtoull(const char*, char**, int);
 extern	void	sysfatal(char*, ...);
 extern	int	dec64(uchar*, int, char*, int);
diff --git a/FreeBSD/386/include/lib9.h b/FreeBSD/386/include/lib9.h
index b78c1eb7..075978fe 100644
--- a/FreeBSD/386/include/lib9.h
+++ b/FreeBSD/386/include/lib9.h
@@ -279,6 +279,8 @@ extern	double	modf(double, double*);
 #define	pow10	infpow10
 extern	double	pow10(int);
 extern	vlong	strtoll(const char*, char**, int);
+#define	qsort	infqsort
+extern	void	qsort(void*, long, long, int (*)(void*, void*));
 extern	uvlong	strtoull(const char*, char**, int);
 extern	void	sysfatal(char*, ...);
 extern	int	dec64(uchar*, int, char*, int);
diff --git a/Irix/mips/include/lib9.h b/Irix/mips/include/lib9.h
index 010777be..9881a3a7 100644
--- a/Irix/mips/include/lib9.h
+++ b/Irix/mips/include/lib9.h
@@ -36,6 +36,15 @@ typedef unsigned short u16int;
 typedef unsigned char u8int;
 typedef unsigned long uintptr;
 
+typedef signed char	int8;
+typedef unsigned char	uint8;
+typedef short	int16;
+typedef unsigned short	uint16;
+typedef int	int32;
+typedef unsigned int	uint32;
+typedef long long	int64;
+typedef unsigned long long	uint64;
+
 #define	USED(x)		if(x){}else{}
 #define	SET(x)
 
@@ -252,6 +261,8 @@ extern	double	ipow10(int);
 #define	pow10	infpow10
 extern	double	pow10(int);
 extern	vlong	strtoll(const char*, char**, int);
+#define	qsort	infqsort
+extern	void	qsort(void*, long, long, int (*)(void*, void*));
 extern	uvlong	strtoull(const char*, char**, int);
 extern	void	sysfatal(char*, ...);
 extern	int	dec64(uchar*, int, char*, int);
diff --git a/Linux/386/include/lib9.h b/Linux/386/include/lib9.h
index 00e5864d..14205872 100644
--- a/Linux/386/include/lib9.h
+++ b/Linux/386/include/lib9.h
@@ -268,6 +268,8 @@ extern	double	ipow10(int);
 #define	pow10	infpow10
 extern	double	pow10(int);
 extern	vlong	strtoll(const char*, char**, int);
+#define	qsort	infqsort
+extern	void	qsort(void*, long, long, int (*)(void*, void*));
 extern	uvlong	strtoull(const char*, char**, int);
 extern	void	sysfatal(char*, ...);
 extern	int	dec64(uchar*, int, char*, int);
diff --git a/Linux/arm/include/lib9.h b/Linux/arm/include/lib9.h
index 5ab0acd8..1a6628b1 100644
--- a/Linux/arm/include/lib9.h
+++ b/Linux/arm/include/lib9.h
@@ -268,6 +268,8 @@ extern	double	ipow10(int);
 #define	pow10	infpow10
 extern	double	pow10(int);
 extern	vlong	strtoll(const char*, char**, int);
+#define	qsort	infqsort
+extern	void	qsort(void*, long, long, int (*)(void*, void*));
 extern	uvlong	strtoull(const char*, char**, int);
 extern	void	sysfatal(char*, ...);
 extern	int	dec64(uchar*, int, char*, int);
diff --git a/Linux/power/include/lib9.h b/Linux/power/include/lib9.h
index f751321b..a9b9dab8 100644
--- a/Linux/power/include/lib9.h
+++ b/Linux/power/include/lib9.h
@@ -269,6 +269,8 @@ extern	double	ipow10(int);
 #define	pow10	infpow10
 extern	double	pow10(int);
 extern	vlong	strtoll(const char*, char**, int);
+#define	qsort	infqsort
+extern	void	qsort(void*, long, long, int (*)(void*, void*));
 extern	uvlong	strtoull(const char*, char**, int);
 extern	void	sysfatal(char*, ...);
 extern	int	dec64(uchar*, int, char*, int);
diff --git a/Linux/spim/include/lib9.h b/Linux/spim/include/lib9.h
index 0812517d..5a1b36bf 100644
--- a/Linux/spim/include/lib9.h
+++ b/Linux/spim/include/lib9.h
@@ -270,6 +270,8 @@ extern	double	ipow10(int);
 #define	pow10	infpow10
 extern	double	pow10(int);
 extern	vlong	strtoll(const char*, char**, int);
+#define	qsort	infqsort
+extern	void	qsort(void*, long, long, int (*)(void*, void*));
 extern	uvlong	strtoull(const char*, char**, int);
 extern	void	sysfatal(char*, ...);
 extern	int	dec64(uchar*, int, char*, int);
diff --git a/MacOSX/386/include/lib9.h b/MacOSX/386/include/lib9.h
index 4716eea0..11194063 100644
--- a/MacOSX/386/include/lib9.h
+++ b/MacOSX/386/include/lib9.h
@@ -91,6 +91,8 @@ extern	int	cistrcmp(char*, char*);
 extern	char*	cistrstr(char*, char*);
 extern	int	tokenize(char*, char**, int);
 extern	vlong	strtoll(const char*, char**, int);
+#define	qsort	infqsort
+extern	void	qsort(void*, long, long, int (*)(void*, void*));
 
 enum
 {
diff --git a/MacOSX/power/include/lib9.h b/MacOSX/power/include/lib9.h
index ff396e78..be609a54 100644
--- a/MacOSX/power/include/lib9.h
+++ b/MacOSX/power/include/lib9.h
@@ -91,6 +91,8 @@ extern	int	cistrcmp(char*, char*);
 extern	char*	cistrstr(char*, char*);
 extern	int	tokenize(char*, char**, int);
 extern	vlong	strtoll(const char*, char**, int);
+#define	qsort	infqsort
+extern	void	qsort(void*, long, long, int (*)(void*, void*));
 
 enum
 {
diff --git a/NetBSD/386/include/lib9.h b/NetBSD/386/include/lib9.h
index 168af335..763128fd 100644
--- a/NetBSD/386/include/lib9.h
+++ b/NetBSD/386/include/lib9.h
@@ -282,6 +282,8 @@ extern	double	modf(double, double*);
 #define	pow10	infpow10
 extern	double	pow10(int);
 extern	vlong	strtoll(const char*, char**, int);
+#define	qsort	infqsort
+extern	void	qsort(void*, long, long, int (*)(void*, void*));
 extern	uvlong	strtoull(const char*, char**, int);
 extern	void	sysfatal(char*, ...);
 extern	int	dec64(uchar*, int, char*, int);
diff --git a/Nt/386/include/lib9.h b/Nt/386/include/lib9.h
index 9700a135..1485e0c6 100755
--- a/Nt/386/include/lib9.h
+++ b/Nt/386/include/lib9.h
@@ -94,6 +94,8 @@ extern	int	cistrcmp(char*, char*);
 extern	char*	cistrstr(char*, char*);
 extern	int	tokenize(char*, char**, int);
 extern	vlong	strtoll(const char*, char**, int);
+#define	qsort	infqsort
+extern	void	qsort(void*, long, long, int (*)(void*, void*));
 extern	uvlong	strtoull(const char*, char**, int);
 
 enum
diff --git a/OpenBSD/386/include/lib9.h b/OpenBSD/386/include/lib9.h
index 66856f03..db77f784 100644
--- a/OpenBSD/386/include/lib9.h
+++ b/OpenBSD/386/include/lib9.h
@@ -279,6 +279,8 @@ extern	double	modf(double, double*);
 #define	pow10	infpow10
 extern	double	pow10(int);
 extern	vlong	strtoll(const char*, char**, int);
+#define	qsort	infqsort
+extern	void	qsort(void*, long, long, int (*)(void*, void*));
 extern	uvlong	strtoull(const char*, char**, int);
 extern	void	sysfatal(char*, ...);
 extern	int	dec64(uchar*, int, char*, int);
diff --git a/Solaris/386/include/lib9.h b/Solaris/386/include/lib9.h
index 57b69801..3e12aa8b 100644
--- a/Solaris/386/include/lib9.h
+++ b/Solaris/386/include/lib9.h
@@ -33,6 +33,15 @@ typedef unsigned short u16int;
 typedef unsigned char u8int;
 typedef unsigned long uintptr;
 
+typedef signed char	int8;
+typedef unsigned char	uint8;
+typedef short	int16;
+typedef unsigned short	uint16;
+typedef int	int32;
+typedef unsigned int	uint32;
+typedef long long	int64;
+typedef unsigned long long	uint64;
+
 #define	USED(x)		if(x);else
 #define	SET(x)
 
@@ -197,6 +206,8 @@ extern	int	(*doquote)(int);
 extern	char*	strdup(const char*);
 extern	int	tokenize(char*, char**, int);
 extern	vlong	strtoll(const char*, char**, int);
+#define	qsort	infqsort
+extern	void	qsort(void*, long, long, int (*)(void*, void*));
 
 extern	int	isNaN(double);
 extern	int	isInf(double, int);
diff --git a/Solaris/sparc/include/lib9.h b/Solaris/sparc/include/lib9.h
index a79cd72b..7f93cdad 100644
--- a/Solaris/sparc/include/lib9.h
+++ b/Solaris/sparc/include/lib9.h
@@ -40,6 +40,15 @@ typedef unsigned short u16int;
 typedef unsigned char u8int;
 typedef unsigned long uintptr;
 
+typedef signed char	int8;
+typedef unsigned char	uint8;
+typedef short	int16;
+typedef unsigned short	uint16;
+typedef int	int32;
+typedef unsigned int	uint32;
+typedef long long	int64;
+typedef unsigned long long	uint64;
+
 #define	USED(x)		if(x){}else{}
 #define	SET(x)
 
@@ -265,6 +274,8 @@ extern	double	modf(double, double*);
 #define	pow10	infpow10
 extern	double	pow10(int);
 extern	vlong	strtoll(const char*, char**, int);
+#define	qsort	infqsort
+extern	void	qsort(void*, long, long, int (*)(void*, void*));
 extern	uvlong	strtoull(const char*, char**, int);
 extern	void	sysfatal(char*, ...);
 extern	int	dec64(uchar*, int, char*, int);
diff --git a/appl/cmd/rawdbfs.b b/appl/cmd/rawdbfs.b
index cb2daf2c..0b59167e 100644
--- a/appl/cmd/rawdbfs.b
+++ b/appl/cmd/rawdbfs.b
@@ -179,7 +179,7 @@ init(ctxt: ref Draw->Context, args: list of string)
 
 	df := bufio->open(file, Sys->ORDWR);
 	if(df == nil && empty){
-		(rc, d) := sys->stat(file);
+		(rc, nil) := sys->stat(file);
 		if(rc < 0)
 			df = bufio->create(file, Sys->ORDWR, 8r600);
 	}
@@ -246,7 +246,6 @@ Serve:
 			sys->fprint(stderr, "dbfs: fatal read error: %s\n", m.error);
 			break Serve;
 		Open =>
-			c := srv.getfid(m.fid);
 			open(srv, m);
 		Read =>
 			(c, err) := srv.canread(m);
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)
diff --git a/dis/lib/rabin.dis b/dis/lib/rabin.dis
new file mode 100644
index 00000000..dce69d0b
--- /dev/null
+++ b/dis/lib/rabin.dis
diff --git a/dis/lib/styxservers.dis b/dis/lib/styxservers.dis
index 052d3e0f..c715e3b2 100644
--- a/dis/lib/styxservers.dis
+++ b/dis/lib/styxservers.dis
diff --git a/dis/rawdbfs.dis b/dis/rawdbfs.dis
index e951bff6..22a22d31 100644
--- a/dis/rawdbfs.dis
+++ b/dis/rawdbfs.dis
diff --git a/include/version.h b/include/version.h
index 21360dce..12f27b76 100644
--- a/include/version.h
+++ b/include/version.h
@@ -1 +1 @@
-#define VERSION	"Fourth Edition (20120114)"
+#define VERSION	"Fourth Edition (20120304)"
diff --git a/lib9/mkfile b/lib9/mkfile
index 4166196e..ea1948fc 100644
--- a/lib9/mkfile
+++ b/lib9/mkfile
@@ -11,7 +11,6 @@ COMMONFILES=\
 	convM2S.$O\
 	convS2M.$O\
 	fcallfmt.$O\
-	qsort.$O\
 	runestrlen.$O\
 	strtoll.$O\
 	strtoull.$O\
@@ -46,6 +45,7 @@ IMPORTFILES=\
 	nulldir.$O\
 	pow10.$O\
 	print.$O\
+	qsort.$O\
 	readn.$O\
 	rerrstr.$O\
 	runeseprint.$O\
diff --git a/lib9/qsort.c b/lib9/qsort.c
index 3388891c..922538de 100644
--- a/lib9/qsort.c
+++ b/lib9/qsort.c
@@ -2,6 +2,7 @@
  * qsort -- simple quicksort
  */
 
+#include "lib9.h"
 typedef
 struct
 {
@@ -116,7 +117,7 @@ qsort(void *va, long n, long es, int (*cmp)(void*, void*))
 	s.cmp = cmp;
 	s.es = es;
 	s.swap = swapi;
-	if(((long)va | es) % sizeof(long))
+	if(((uintptr)va | es) % sizeof(long))
 		s.swap = swapb;
 	qsorts((char*)va, n, &s);
 }
diff --git a/man/2/rabin b/man/2/rabin
new file mode 100644
index 00000000..daceeaaf
--- /dev/null
+++ b/man/2/rabin
@@ -0,0 +1,54 @@
+.TH RABIN 2
+.SH NAME
+rabin \- rabin fingerprinting
+.SH SYNOPSIS
+.EX
+include "rabin.m";
+rabin := load Rabin Rabin->PATH;
+Rcfg, Rfile: import rabin;
+
+init:	fn(bufio: Bufio);
+open:	fn(rcfg: ref Rcfg, b: ref Iobuf, min, max: int): (ref Rfile, string);
+
+Rcfg: adt {
+	mk:	fn(prime, width, mod: int): (ref Rcfg, string);
+};
+
+Rfile: adt {
+	read:	fn(r: self ref Rfile): (array of byte, big, string);
+};
+.EE
+.SH DESCRIPTION
+.B Rabin
+implements a data fingerprinting algorithm.  A rolling checksum is calculated while reading data.  Certain checksum values are taken to be data boundaries and used to split the data into chunks.
+.PP
+.B Rcfg
+represents the parameters to the algorithm;
+.B Rcfg.mk
+creates a new instance.
+.I Prime
+should be a prime number.
+.I Width
+is the width of the rolling checksum window in bytes.  A wider window results in more diverse boundary patterns.  A window of 30 bytes should be reasonable for most uses.
+.I Mod
+effectively sets the mean desired chunk size.  The rolling checksum is calculated modulo
+.IR mod .
+All three parameters influence where chunk boundaries will be found.
+.PP
+.B Rfile
+represents a file to read chunks from.
+.B Open 
+returns an initialised Rfile or an error string.
+.I Min
+and
+.I max
+are the minimum and maximum size in bytes of chunks that will be returned.  Only the last chunk in a file can be smaller than the minimum chunk size.  Note that the mean chunk size may be off due to these parameters.
+Data is read from
+.B Iobuf
+.IR b .
+.B Rfile.read
+returns subsequent chunks of data and the file offset at which they were found, or an error message.  After end of file, the returned chunks are zero bytes long.
+.SH SOURCE
+.B /appl/lib/rabin.b
+.SH AUTHOR
+Mechiel Lukkien, during GSoC 2007
diff --git a/module/rabin.m b/module/rabin.m
new file mode 100644
index 00000000..ba613fab
--- /dev/null
+++ b/module/rabin.m
@@ -0,0 +1,28 @@
+Rabin: module
+{
+	PATH:	con "/dis/lib/rabin.dis";
+	init:	fn(bufio: Bufio);
+
+	debug:	int;
+
+	open:	fn(rcfg: ref Rcfg, b: ref Iobuf, min, max: int): (ref Rfile, string);
+
+	Rcfg: adt {
+		prime, width, mod: int;
+		tab:	array of int;
+
+		mk:	fn(prime, width, mod: int): (ref Rcfg, string);
+	};
+
+	Rfile: adt {
+		b:	ref Iobuf;
+		rcfg:	ref Rcfg;
+		min, max:	int;
+		buf:	array of byte;
+		n:	int;
+		state:	int;
+		off:	big;
+
+		read:	fn(r: self ref Rfile): (array of byte, big, string);
+	};
+};
diff --git a/module/styxservers.m b/module/styxservers.m
index b9b47cf7..28831bfa 100644
--- a/module/styxservers.m
+++ b/module/styxservers.m
@@ -53,6 +53,7 @@ Styxservers: module
 		new:		fn(fd: ref Sys->FD, t: ref Navigator, rootpath: big): (chan of ref Styx->Tmsg, ref Styxserver);
 		reply:	fn(srv: self ref Styxserver, m: ref Styx->Rmsg): int;
 		replydirect:	fn(srv: self ref Styxserver, m: ref Styx->Rmsg): int;
+		error:	fn(srv: self ref Styxserver, m: ref Styx->Tmsg, msg: string);
 
 		# protocol operations
 		attach:	fn(srv: self ref Styxserver, m: ref Styx->Tmsg.Attach): ref Fid;