1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
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);
}
}
}
|
