diff options
Diffstat (limited to 'appl/lib/ida/ida.b')
| -rw-r--r-- | appl/lib/ida/ida.b | 228 |
1 files changed, 228 insertions, 0 deletions
diff --git a/appl/lib/ida/ida.b b/appl/lib/ida/ida.b new file mode 100644 index 00000000..c1430688 --- /dev/null +++ b/appl/lib/ida/ida.b @@ -0,0 +1,228 @@ +implement Ida; + +# +# M Rabin, ``Efficient Dispersal of Information for Security, +# Load Balancing, and Fault Tolerance'', JACM 36(2), April 1989, pp. 335-348 +# the scheme used below is that suggested at the top of page 340 +# + +include "sys.m"; + sys: Sys; + +include "rand.m"; + rand: Rand; + +include "ida.m"; + +invtab: array of int; + +init() +{ + sys = load Sys Sys->PATH; + rand = load Rand Rand->PATH; + rand->init(sys->pctl(0, nil)^(sys->millisec()<<8)); + # the table is in a separate module so that + # the copy in the module initialisation section is discarded + # after unloading, preventing twice the space being used + idatab := load Idatab Idatab->PATH; + invtab = idatab->init(); # the big fella + idatab = nil; +} + +Field: con 65537; +Fmax: con Field-1; + +div(a, b: int): int +{ + return mul(a, invtab[b]); +} + +mul(a, b: int): int +{ + if(a == Fmax && b == Fmax) # avoid overflow + return 1; + return int((big(a*b) & 16rFFFFFFFF) % big Field); +} + +sub(a, b: int): int +{ + return ((a-b)+Field)%Field; +} + +add(a, b: int): int +{ + return (a + b)%Field; +} + +# +# return a fragment representing the encoded version of data +# +fragment(data: array of byte, m: int): ref Frag +{ + nb := len data; + nw := (nb+1)/2; + a := array[m] of {* => rand->rand(Fmax)+1}; # no zero elements + f := array[(nw + m - 1)/m] of int; + o := 0; + i := 0; + for(k := 0; k < len f; k++){ + c := 0; + for(j := 0; j < m && i < nb; j++){ + b := int data[i++] << 8; + if(i < nb) + b |= int data[i++]; + c = add(c, mul(b, a[j])); + } + f[o++] = c; + } + return ref Frag(nb, m, a, f, nil); +} + +# +# return the data encoded by the given set of fragments +# +reconstruct(frags: array of ref Frag): (array of byte, string) +{ + if(len frags < 1 || len frags < (m := frags[0].m)) + return (nil, "too few fragments"); + fraglen := len frags[0].enc; + + a := array[m] of array of int; + for(j := 0; j < len a; j++){ + a[j] = frags[j].a; + if(len a[j] != m) + return (nil, "inconsistent encoding matrix"); + if(len frags[j].enc != fraglen) + return (nil, "inconsistent fragments"); + } + ainv := minvert(a); + out := array[fraglen*2*m] of byte; + o := 0; + for(k := 0; k < fraglen; k++){ + for(i := 0; i < m; i++){ + row := ainv[i]; + b := 0; + for(j = 0; j < m; j++) + b = add(b, mul(frags[j].enc[k], row[j])); + if((b>>16) != 0) + return (nil, "corrupt output"); + out[o++] = byte (b>>8); + out[o++] = byte b; + } + } + if(frags[0].dlen < len out) + out = out[0: frags[0].dlen]; + return (out, nil); +} + +# +# Rabin's paper gives a way of building an encoding matrix that can then +# be inverted in O(m^2) operations, compared to O(m^3) for the following, +# but m is small enough it doesn't seem worth the added complication, +# and it's only done once per set +# +minvert(a: array of array of int): array of array of int +{ + m := len a; # it's square + out := array[m] of {* => array[m*2] of {* => 0}}; + for(r := 0; r < m; r++){ + out[r][0:] = a[r]; + out[r][m+r] = 1; # identity matrix + } + for(r = 0; r < m; r++){ + x := out[r][r]; # by construction, cannot be zero, unless later corrupted + for(c := 0; c < 2*m; c++) + out[r][c] = div(out[r][c], x); + for(r1 := 0; r1 < m; r1++) + if(r1 != r){ + y := div(out[r1][r], out[r][r]); + for(c = 0; c < 2*m; c++) + out[r1][c] = sub(out[r1][c], mul(y, out[r][c])); + } + } + for(r = 0; r < m; r++) + out[r] = out[r][m:]; + return out; +} + +Val: adt { + v: int; + n: int; +}; + +addval(vl: list of ref Val, v: int): list of ref Val +{ + for(l := vl; l != nil; l = tl l) + if((hd l).v == v){ + (hd l).n++; + return vl; + } + return ref Val(v, 1) :: vl; +} + +mostly(vl: list of ref Val): ref Val +{ + if(len vl == 1) + return hd vl; + v: ref Val; + for(; vl != nil; vl = tl vl) + if(v == nil || (hd vl).n > v.n) + v = hd vl; + return v; +} + +# +# return a consistent set of Frags: all parameters agree with the majority, +# and obviously bad fragments have been discarded +# +# in the absence of error, they should all have the same value, so lists are fine; +# could separately return the discarded ones, out of interest +# +consistent(frags: array of ref Frag): array of ref Frag +{ + t := array[len frags] of ref Frag; + t[0:] = frags; + frags = t; + ds: list of ref Val; # data size + ms: list of ref Val; + fls: list of ref Val; + for(i := 0; i < len frags; i++){ + f := frags[i]; + if(f != nil){ + ds = addval(ds, f.dlen); + ms = addval(ms, f.m); + fls = addval(fls, len f.enc); + } + } + dv := mostly(ds); + mv := mostly(ms); + flv := mostly(fls); + if(mv == nil || flv == nil || dv == nil) + return nil; + for(i = 0; i < len frags; i++){ + f := frags[i]; + if(f == nil || f.m != mv.v || f.m != len f.a || len f.enc != flv.v || f.dlen != dv.v || badfrag(f)){ # inconsistent: drop it + if(i+1 < len frags) + frags[i:] = frags[i+1:]; + frags = frags[0:len frags-1]; + } + } + if(len frags == 0) + return nil; + return frags; +} + +badfrag(f: ref Frag): int +{ + for(i := 0; i < len f.a; i++){ + v := f.a[i]; + if(v <= 0 || v >= Field) + return 1; + } + for(i = 0; i < len f.a; i++){ + v := f.enc[i]; + if(v == 0 || v >= Field) + return 1; + } + return 0; +} |