changelog shortlog tags branches changeset files revisions annotate raw help

Mercurial > hg > ventivac / appl/lib/vac.b

changeset 140: 237e0bba7234
parent: 260aaad09159
child: a81c5fb2810f
author: Mechiel Lukkien <mechiel@ueber.net>
date: Mon, 20 Aug 2007 18:00:30 +0200
permissions: -rw-r--r--
description: remove Rootversion from vac.b, not needed and was in wrong place.
1 implement Vac;
2 
3 include "sys.m";
4 include "string.m";
5 include "venti.m";
6 include "vac.m";
7 
8 sys: Sys;
9 str: String;
10 venti: Venti;
11 
12 werrstr, sprint, fprint, fildes: import sys;
13 Root, Rootsize, Entry, Entrysize, Roottype, Dirtype, Pointertype0, Datatype: import venti;
14 Pointervarmask, Entryactive, Entrydir, Entrydepthshift, Entrydepthmask, Entrylocal, Entryvarblocks: import venti;
15 Score, Session, Scoresize: import venti;
16 
17 debug := 0;
18 
19 BIT8SZ: con 1;
20 BIT16SZ: con 2;
21 BIT32SZ: con 4;
22 BIT48SZ: con 6;
23 BIT64SZ: con 8;
24 
25 Rootnamelen: con 128;
26 Maxstringsize: con 1000;
27 
28 blankroot: Root;
29 blankentry: Entry;
30 blankdirentry: Direntry;
31 blankmetablock: Metablock;
32 blankmetaentry: Metaentry;
33 
34 
35 init()
36 {
37  sys = load Sys Sys->PATH;
38  str = load String String->PATH;
39  venti = load Venti Venti->PATH;
40  venti->init();
41 }
42 
43 vread(session: ref Session, s: Score, t: int, maxsize: int): array of byte
44 {
45  d := session.read(s, t, maxsize);
46  blocksread++;
47  bytesread += big len d;
48  return d;
49 }
50 
51 vwrite(session: ref Session, t: int, d: array of byte): (int, Score)
52 {
53  (ok, score) := session.write(t, d);
54  blockswritten++;
55  byteswritten += big len d;
56  return (ok, score);
57 }
58 
59 pstring(a: array of byte, o: int, s: string): int
60 {
61  sa := array of byte s; # could do conversion ourselves
62  n := len sa;
63  a[o] = byte (n >> 8);
64  a[o+1] = byte n;
65  a[o+2:] = sa;
66  return o+BIT16SZ+n;
67 }
68 
69 gstring(a: array of byte, o: int): (string, int)
70 {
71  if(o < 0 || o+BIT16SZ > len a)
72  return (nil, -1);
73  l := (int a[o] << 8) | int a[o+1];
74  if(l > Maxstringsize)
75  return (nil, -1);
76  o += BIT16SZ;
77  e := o+l;
78  if(e > len a)
79  return (nil, -1);
80  return (string a[o:e], e);
81 }
82 
83 Direntry.new(): ref Direntry
84 {
85  return ref Direntry(9, "", 0, 0, 0, 0, big 0, "", "", "", 0, 0, 0, 0, 0, 0);
86 }
87 
88 Direntry.mk(d: Sys->Dir): ref Direntry
89 {
90  atime := 0; # d.atime;
91  mode := d.mode&Modeperm;
92  if(d.mode&sys->DMAPPEND)
93  mode |= Modeappend;
94  if(d.mode&sys->DMEXCL)
95  mode |= Modeexcl;
96  if(d.mode&sys->DMDIR)
97  mode |= Modedir;
98  if(d.mode&sys->DMTMP)
99  mode |= Modetemp;
100  return ref Direntry(9, d.name, 0, 0, 0, 0, d.qid.path, d.uid, d.gid, d.muid, d.mtime, d.qid.vers, 0, atime, mode, d.mode);
101 }
102 
103 Direntry.mkdir(de: self ref Direntry): ref Sys->Dir
104 {
105  d := ref sys->nulldir;
106  d.name = de.elem;
107  d.uid = de.uid;
108  d.gid = de.gid;
109  d.muid = de.mid;
110  d.qid.path = de.qid;
111  d.qid.vers = 0;
112  d.qid.qtype = de.emode>>24;
113  d.mode = de.emode;
114  d.atime = de.atime;
115  d.mtime = de.mtime;
116  d.length = big 0;
117  return d;
118 }
119 
120 strlen(s: string): int
121 {
122  return 2+len array of byte s;
123 }
124 
125 Direntry.pack(de: self ref Direntry): array of byte
126 {
127  # assume version 9
128  length := 4+2+strlen(de.elem)+4+4+4+4+8+strlen(de.uid)+strlen(de.gid)+strlen(de.mid)+4+4+4+4+4; # + qidspace?
129 
130  d := array[length] of byte;
131  i := 0;
132  i = p32(d, i, Direntrymagic);
133  i = p16(d, i, de.version);
134  i = pstring(d, i, de.elem);
135  i = p32(d, i, de.entry);
136  if(de.version == 9) {
137  i = p32(d, i, de.gen);
138  i = p32(d, i, de.mentry);
139  i = p32(d, i, de.mgen);
140  }
141  i = p64(d, i, de.qid);
142  i = pstring(d, i, de.uid);
143  i = pstring(d, i, de.gid);
144  i = pstring(d, i, de.mid);
145  i = p32(d, i, de.mtime);
146  i = p32(d, i, de.mcount);
147  i = p32(d, i, de.ctime);
148  i = p32(d, i, de.atime);
149  i = p32(d, i, de.mode);
150  if(i != len d) {
151  werrstr(sprint("bad length for direntry (expected %d, have %d)", len d, i));
152  return nil;
153  }
154  return d;
155 }
156 
157 Direntry.unpack(d: array of byte): ref Direntry
158 {
159  {
160  de := ref blankdirentry;
161  i := 0;
162  magic: int;
163  (magic, i) = eg32(d, i);
164  if(magic != Direntrymagic) {
165  werrstr(sprint("bad magic (%x, want %x)", magic, Direntrymagic));
166  return nil;
167  }
168  (de.version, i) = eg16(d, i);
169  if(de.version != 8 && de.version != 9) {
170  werrstr(sprint("bad version (%d)", de.version));
171  return nil;
172  }
173  (de.elem, i) = egstring(d, i);
174  (de.entry, i) = eg32(d, i);
175  case de.version {
176  8 =>
177  de.gen = 0;
178  de.mentry = de.entry+1;
179  de.mgen = 0;
180  9 =>
181  (de.gen, i) = eg32(d, i);
182  (de.mentry, i) = eg32(d, i);
183  (de.mgen, i) = eg32(d, i);
184  }
185  (de.qid, i) = eg64(d, i);
186  (de.uid, i) = egstring(d, i);
187  (de.gid, i) = egstring(d, i);
188  (de.mid, i) = egstring(d, i);
189  (de.mtime, i) = eg32(d, i);
190  (de.mcount, i) = eg32(d, i);
191  (de.ctime, i) = eg32(d, i);
192  (de.atime, i) = eg32(d, i);
193  (de.mode, i) = eg32(d, i);
194  de.emode = de.mode&Modeperm;
195  if(de.mode&Modeappend)
196  de.emode |= sys->DMAPPEND;
197  if(de.mode&Modeexcl)
198  de.emode |= sys->DMEXCL;
199  if(de.mode&Modedir)
200  de.emode |= sys->DMDIR;
201  if(de.mode&Modetemp)
202  de.emode |= sys->DMTMP;
203  if(de.version == 9)
204  ; # xxx handle qid space?, can be in here
205  return de;
206  } exception e {
207  "too small:*" =>
208  werrstr("direntry "+e);
209  return nil;
210  * =>
211  raise e;
212  }
213 }
214 
215 
216 Metablock.new(): ref Metablock
217 {
218  return ref Metablock(0, 0, 0, 0);
219 }
220 
221 Metablock.pack(mb: self ref Metablock, d: array of byte)
222 {
223  i := 0;
224  i = p32(d, i, Metablockmagic);
225  i = p16(d, i, mb.size);
226  i = p16(d, i, mb.free);
227  i = p16(d, i, mb.maxindex);
228  i = p16(d, i, mb.nindex);
229 }
230 
231 Metablock.unpack(d: array of byte): ref Metablock
232 {
233  if(len d < Metablocksize) {
234  werrstr(sprint("bad length for metablock (%d, want %d)", len d, Metablocksize));
235  return nil;
236  }
237  i := 0;
238  magic := g32(d, i);
239  if(magic != Metablockmagic && magic != Metablockmagic+1) {
240  werrstr(sprint("bad magic for metablock (%x, need %x)", magic, Metablockmagic));
241  return nil;
242  }
243  i += BIT32SZ;
244 
245  mb := ref blankmetablock;
246  mb.size = g16(d, i);
247  i += BIT16SZ;
248  mb.free = g16(d, i);
249  i += BIT16SZ;
250  mb.maxindex = g16(d, i);
251  i += BIT16SZ;
252  mb.nindex = g16(d, i);
253  i += BIT16SZ;
254  if(mb.nindex == 0) {
255  werrstr("bad metablock, nindex=0");
256  return nil;
257  }
258  return mb;
259 }
260 
261 Metaentry.pack(me: self ref Metaentry, d: array of byte)
262 {
263  i := 0;
264  i = p16(d, i, me.offset);
265  i = p16(d, i, me.size);
266 }
267 
268 Metaentry.unpack(d: array of byte, i: int): ref Metaentry
269 {
270  o := Metablocksize+i*Metaentrysize;
271  if(o+Metaentrysize > len d) {
272  werrstr(sprint("meta entry lies outside meta block, i=%d", i));
273  return nil;
274  }
275 
276  me := ref blankmetaentry;
277  me.offset = g16(d, o);
278  o += BIT16SZ;
279  me.size = g16(d, o);
280  o += BIT16SZ;
281  if(me.offset+me.size > len d) {
282  werrstr(sprint("meta entry points outside meta block, i=%d", i));
283  return nil;
284  }
285  return me;
286 }
287 
288 
289 Page.new(dsize: int, varblocks: int): ref Page
290 {
291  esize := Scoresize;
292  treesize := big 0;
293  if(varblocks)
294  esize += BIT64SZ;
295  else
296  treesize = ~big 0;
297  psize := (dsize/esize)*esize;
298  return ref Page(array[psize] of byte, 0, esize, treesize);
299 }
300 
301 Page.npointers(p: self ref Page): int
302 {
303  return p.o/p.esize;
304 }
305 
306 Page.add(p: self ref Page, s: Score, size: big)
307 {
308  p.d[p.o:] = s.a;
309  p.o += Scoresize;
310  if(p.treesize != ~big 0) {
311  p64(p.d, p.o, size);
312  p.o += BIT64SZ;
313  p.treesize += size;
314  }
315 }
316 
317 Page.full(p: self ref Page): int
318 {
319  return p.o+p.esize> len p.d;
320 }
321 
322 Page.data(p: self ref Page): array of byte
323 {
324  if(p.treesize != ~big 0)
325  return p.d[:p.o];
326  for(i := p.o; i >= Scoresize; i -= Scoresize)
327  if(!Score(p.d[i-Scoresize:i]).eq(Score.zero()))
328  break;
329  return p.d[:i];
330 }
331 
332 
333 File.new(s: ref Session, dtype, dsize, varblocks: int): ref File
334 {
335  p := array[1] of ref Page;
336  p[0] = Page.new(dsize, varblocks);
337  return ref File(p, dtype, dsize, big 0, s, varblocks);
338 }
339 
340 fflush(f: ref File, last: int): (int, ref Entry)
341 {
342  for(i := 0; i < len f.p; i++) {
343  if(!last && !f.p[i].full())
344  return (0, nil);
345  if(last && f.p[i].npointers() == 1) {
346  flags := Entryactive;
347  flags |= i<<Entrydepthshift;
348  if(f.dtype & Dirtype)
349  flags |= Entrydir;
350  if(f.varblocks)
351  flags |= Entryvarblocks;
352  d := f.p[i].data();
353  if(len d == 0)
354  d = Score.zero().a;
355  d = d[:Scoresize];
356  score := Score(d);
357  dsize := f.dsize;
358  if(f.varblocks)
359  dsize = 0;
360  return (0, Entry.new(len f.p[i].d, dsize, flags, f.size, score));
361  }
362  t := Pointertype0+i;
363  if(f.varblocks)
364  t |= Pointervarmask;
365  (ok, score) := vwrite(f.s, t, f.p[i].data());
366  if(ok < 0)
367  return (-1, nil);
368  treesize := f.p[i].treesize;
369  f.p[i] = Page.new(f.dsize, f.varblocks);
370  if(i+1 == len f.p) {
371  newp := array[len f.p+1] of ref Page;
372  newp[:] = f.p;
373  newp[len newp-1] = Page.new(f.dsize, f.varblocks);
374  f.p = newp;
375  }
376  f.p[i+1].add(score, treesize);
377  }
378  werrstr("internal error in fflush");
379  return (-1, nil);
380 }
381 
382 File.write(f: self ref File, d: array of byte): int
383 {
384  (fok, nil) := fflush(f, 0);
385  if(fok < 0)
386  return -1;
387  length := len d;
388  for(i := len d; i > 0; i--)
389  if(d[i-1] != byte 0)
390  break;
391  d = d[:i];
392  (ok, score) := vwrite(f.s, f.dtype, d);
393  if(ok < 0)
394  return -1;
395  f.size += big length;
396  f.p[0].add(score, big length);
397  return 0;
398 }
399 
400 File.finish(f: self ref File): ref Entry
401 {
402  (ok, e) := fflush(f, 1);
403  if(ok < 0)
404  return nil;
405  return e;
406 }
407 
408 File.mkstate(session: ref Venti->Session, e: ref Entry, varblocks: int): ref File
409 {
410  s := e.score;
411  dsize := e.dsize;
412  if(dsize == 0)
413  dsize = Venti->Dsize; # xxx make configurable? pointer block size is currently assumed to be Dsize everywhere
414  if(e.depth == 0) {
415  p := Page.new(dsize, varblocks);
416  return ref File(array[1] of {p}, Datatype, dsize, big 0, session, varblocks);
417  }
418  f := ref File(array[e.depth] of ref Page, Datatype, dsize, big 0, session, varblocks);
419  for(i := 0; i < e.depth; i++) {
420  t := Pointertype0+e.depth-1-i;
421  if(f.varblocks)
422  t |= Pointervarmask;
423  d := vread(session, s, t, Venti->Maxlumpsize);
424  if(d == nil)
425  return nil;
426  p := Page.new(dsize, varblocks);
427  p.d[:] = d;
428  p.o = len d-p.esize;
429  s = Score(p.d[p.o:p.o+Scoresize]);
430  f.p[i] = p;
431  }
432  if(varblocks) {
433  lp := f.p[len f.p-1];
434  bsize := g64(lp.d, lp.o+Scoresize);
435  f.size = e.size-bsize;
436  for(i = 0; i < len f.p; i++)
437  f.p[i].treesize -= bsize;
438  } else {
439  ls := e.size % big e.dsize;
440  if(ls == big 0)
441  ls = big e.dsize;
442  f.size = e.size-ls;
443  }
444  return f;
445 }
446 
447 
448 Sink.new(s: ref Venti->Session, dsize: int): ref Sink
449 {
450  dirdsize := (dsize/Entrysize)*Entrysize;
451  return ref Sink(File.new(s, Dirtype, dsize, 0), array[dirdsize] of byte, 0, 0);
452 }
453 
454 Sink.add(m: self ref Sink, e: ref Entry): int
455 {
456  ed := e.pack();
457  if(ed == nil)
458  return -1;
459  n := len m.d - m.nd;
460  if(n > len ed)
461  n = len ed;
462  m.d[m.nd:] = ed[:n];
463  m.nd += n;
464  if(n < len ed) {
465  if(m.f.write(m.d) < 0)
466  return -1;
467  m.nd = len ed - n;
468  m.d[:] = ed[n:];
469  }
470  return m.ne++;
471 }
472 
473 Sink.finish(m: self ref Sink): ref Entry
474 {
475  if(m.nd > 0)
476  if(m.f.write(m.d[:m.nd]) < 0)
477  return nil;
478  e := m.f.finish();
479  e.dsize = len m.d;
480  return e;
481 }
482 
483 
484 elemcmp(a, b: array of byte, fossil: int): int
485 {
486  for(i := 0; i < len a && i < len b; i++)
487  if(a[i] != b[i])
488  return (int a[i] - int b[i]);
489  if(fossil)
490  return len a - len b;
491  return len b - len a;
492 }
493 
494 Mentry.cmp(a, b: ref Mentry): int
495 {
496  return elemcmp(array of byte a.elem, array of byte b.elem, 0);
497 }
498 
499 MSink.new(s: ref Venti->Session, dsize: int): ref MSink
500 {
501  return ref MSink(File.new(s, Datatype, dsize, 0), array[dsize] of byte, 0, nil);
502 }
503 
504 l2a[T](l: list of T): array of T
505 {
506  a := array[len l] of T;
507  i := 0;
508  for(; l != nil; l = tl l)
509  a[i++] = hd l;
510  return a;
511 }
512 
513 insertsort[T](a: array of T)
514  for { T => cmp: fn(a, b: T): int; }
515 {
516  for(i := 1; i < len a; i++) {
517  tmp := a[i];
518  for(j := i; j > 0 && T.cmp(a[j-1], tmp) > 0; j--)
519  a[j] = a[j-1];
520  a[j] = tmp;
521  }
522 }
523 
524 mflush(m: ref MSink, last: int): int
525 {
526  d := array[len m.de] of byte;
527 
528  me := l2a(m.l);
529  insertsort(me);
530  o := Metablocksize;
531  deo := o+len m.l*Metaentrysize;
532  for(i := 0; i < len me; i++) {
533  me[i].me.offset += deo;
534  me[i].me.pack(d[o:]);
535  o += Metaentrysize;
536  }
537  d[o:] = m.de[:m.nde];
538  o += m.nde;
539  if(!last)
540  while(o < len d)
541  d[o++] = byte 0;
542 
543  mb := Metablock.new();
544  mb.nindex = len m.l;
545  mb.maxindex = mb.nindex;
546  mb.free = 0;
547  mb.size = o;
548  mb.pack(d);
549 
550  if(m.f.write(d[:o]) < 0)
551  return -1;
552  m.nde = 0;
553  m.l = nil;
554  return 0;
555 }
556 
557 MSink.add(m: self ref MSink, de: ref Direntry): int
558 {
559  d := de.pack();
560  if(d == nil)
561  return -1;
562  if(Metablocksize+len m.l*Metaentrysize+m.nde + Metaentrysize+len d > len m.de)
563  if(mflush(m, 0) < 0)
564  return -1;
565  m.de[m.nde:] = d;
566  m.l = ref Mentry(de.elem, ref Metaentry(m.nde, len d))::m.l;
567  m.nde += len d;
568  return 0;
569 }
570 
571 MSink.finish(m: self ref MSink): ref Entry
572 {
573  if(m.nde > 0)
574  mflush(m, 1);
575  return m.f.finish();
576 }
577 
578 Source.new(s: ref Session, e: ref Entry): ref Source
579 {
580  return ref Source(s, e);
581 }
582 
583 power(b, e: int): big
584 {
585  r := big 1;
586  while(e-- > 0)
587  r *= big b;
588  return r;
589 }
590 
591 blocksize(e: ref Entry): int
592 {
593  if(e.psize > e.dsize)
594  return e.psize;
595  return e.dsize;
596 }
597 
598 Source.get(s: self ref Source, i: big, d: array of byte): int
599 {
600  npages := (s.e.size+big (s.e.dsize-1))/big s.e.dsize;
601  if(i*big s.e.dsize >= s.e.size)
602  return 0;
603 
604  want := s.e.dsize;
605  if(i == npages-big 1)
606  want = int (s.e.size - i*big s.e.dsize);
607  last := s.e.score;
608  bsize := blocksize(s.e);
609  buf: array of byte;
610 
611  npp := s.e.psize/Scoresize; # scores per pointer block
612  np := power(npp, s.e.depth-1); # blocks referenced by score at this depth
613  for(depth := s.e.depth; depth >= 0; depth--) {
614  dtype := Pointertype0+depth-1;
615  if(depth == 0) {
616  dtype = Datatype;
617  if(s.e.flags & Entrydir)
618  dtype = Dirtype;
619  bsize = want;
620  }
621  buf = vread(s.session, last, dtype, bsize);
622  if(buf == nil)
623  return -1;
624  if(depth > 0) {
625  pi := int (i / np);
626  i %= np;
627  np /= big npp;
628  o := (pi+1)*Scoresize;
629  if(o <= len buf)
630  last = Score(buf[o-Scoresize:o]);
631  else
632  last = Score.zero();
633  }
634  }
635  for(j := len buf; j < want; j++)
636  d[j] = byte 0;
637  d[:] = buf;
638  return want;
639 }
640 
641 Source.oget(s: self ref Source, offset: big): array of byte
642 {
643  if(offset >= s.e.size)
644  return array[0] of byte;
645 
646  coffset := big 0;
647  esize := Scoresize;
648  if(s.e.flags&Entryvarblocks)
649  esize += 8;
650  last := s.e.score;
651  tlen := s.e.size;
652 
653  for(depth := s.e.depth; depth > 0; depth--) {
654  dtype := Pointertype0+depth-1;
655  dtype |= Pointervarmask;
656  buf := vread(s.session, last, dtype, s.e.psize);
657  if(buf == nil)
658  return nil;
659 
660  (last, tlen) = (Score(buf[:Scoresize]), g64(buf, Scoresize));
661  for(o := esize; o+esize <= len buf; o += esize) {
662  if(offset < coffset+tlen)
663  break;
664  coffset += tlen;
665  tlen = g64(buf, o+Scoresize);
666  last = Score(buf[o:o+Scoresize]);
667  }
668  if(coffset+tlen < offset || coffset > offset) {
669  sys->werrstr("bad source.oget");
670  return nil;
671  }
672  }
673  buf := vread(s.session, last, Datatype, int tlen);
674  if(buf == nil)
675  return nil;
676  if(len buf != int tlen) {
677  sys->werrstr(sprint("unexpected block size, score=%s, want=%d have=%d", last.text(), int tlen, len buf));
678  return nil;
679  }
680  return buf[int (offset-coffset):];
681 }
682 
683 
684 Vacfile.mk(s: ref Source): ref Vacfile
685 {
686  return ref Vacfile(s, big 0);
687 }
688 
689 Vacfile.new(s: ref Session, e: ref Entry): ref Vacfile
690 {
691  return Vacfile.mk(Source.new(s, e));
692 }
693 
694 Vacfile.seek(v: self ref Vacfile, offset: big): big
695 {
696  v.o += offset;
697  if(v.o > v.s.e.size)
698  v.o = v.s.e.size;
699  return v.o;
700 }
701 
702 Vacfile.read(v: self ref Vacfile, d: array of byte, n: int): int
703 {
704  have := v.pread(d, n, v.o);
705  if(have > 0)
706  v.o += big have;
707  return have;
708 }
709 
710 Vacfile.pread(v: self ref Vacfile, d: array of byte, n: int, offset: big): int
711 {
712  if(v.s.e.flags&Entryvarblocks) {
713  buf := v.s.oget(offset);
714  if(buf == nil)
715  return -1;
716  if(len buf < n)
717  n = len buf;
718  d[:] = buf[:n];
719  return n;
720  } else {
721  dsize := v.s.e.dsize;
722  have := v.s.get(big (offset/big dsize), buf := array[dsize] of byte);
723  if(have <= 0)
724  return have;
725  o := int (offset % big dsize);
726  have -= o;
727  if(have > n)
728  have = n;
729  if(have <= 0)
730  return 0;
731  d[:] = buf[o:o+have];
732  return have;
733  }
734 }
735 
736 
737 Vacdir.mk(vf: ref Vacfile, ms: ref Source): ref Vacdir
738 {
739  return ref Vacdir(vf, ms, big 0, 0);
740 }
741 
742 Vacdir.new(session: ref Session, e, me: ref Entry): ref Vacdir
743 {
744  vf := Vacfile.new(session, e);
745  ms := Source.new(session, me);
746  return Vacdir.mk(vf, ms);
747 
748 }
749 
750 mecmp(d: array of byte, i: int, elem: string, fromfossil: int): (int, int)
751 {
752  me := Metaentry.unpack(d, i);
753  if(me == nil)
754  return (0, 1);
755  o := me.offset+6;
756  n := g16(d, o);
757  o += BIT16SZ;
758  if(o+n > len d) {
759  werrstr("bad elem in direntry");
760  return (0, 1);
761  }
762  return (elemcmp(d[o:o+n], array of byte elem, fromfossil), 0);
763 }
764 
765 finddirentry(d: array of byte, elem: string): (int, ref Direntry)
766 {
767  mb := Metablock.unpack(d);
768  if(mb == nil)
769  return (-1, nil);
770  fromfossil := g32(d, 0) == Metablockmagic+1;
771 
772  left := 0;
773  right := mb.nindex;
774  while(left+1 != right) {
775  mid := (left+right)/2;
776  (c, err) := mecmp(d, mid, elem, fromfossil);
777  if(err)
778  return (-1, nil);
779  if(c <= 0)
780  left = mid;
781  else
782  right = mid;
783  if(c == 0)
784  break;
785  }
786  de := readdirentry(d, left);
787  if(de != nil && de.elem == elem)
788  return (1, de);
789  return (0, nil);
790 }
791 
792 Vacdir.walk(v: self ref Vacdir, elem: string): ref Direntry
793 {
794  i := big 0;
795  for(;;) {
796  n := v.ms.get(i, buf := array[v.ms.e.dsize] of byte);
797  if(n < 0)
798  return nil;
799  if(n == 0)
800  break;
801  (ok, de) := finddirentry(buf[:n], elem);
802  if(ok < 0)
803  return nil;
804  if(de != nil)
805  return de;
806  i++;
807  }
808  werrstr(sprint("no such file or directory"));
809  return nil;
810 }
811 
812 vfreadentry(vf: ref Vacfile, entry: int): ref Entry
813 {
814  ebuf := array[Entrysize] of byte;
815  n := vf.pread(ebuf, len ebuf, big entry*big Entrysize);
816  if(n < 0)
817  return nil;
818  if(n != len ebuf) {
819  werrstr(sprint("bad archive, entry=%d not present", entry));
820  return nil;
821  }
822  e := Entry.unpack(ebuf);
823  if(~e.flags&Entryactive) {
824  werrstr("entry not active");
825  return nil;
826  }
827  if(e.flags&Entrylocal) {
828  werrstr("entry is local");
829  return nil;
830  }
831  return e;
832 }
833 
834 Vacdir.open(vd: self ref Vacdir, de: ref Direntry): (ref Entry, ref Entry)
835 {
836  e := vfreadentry(vd.vf, de.entry);
837  if(e == nil)
838  return (nil, nil);
839  isdir1 := de.mode & Modedir;
840  isdir2 := e.flags & Entrydir;
841  if(isdir1 && !isdir2 || !isdir1 && isdir2) {
842  werrstr("direntry directory bit does not match entry directory bit");
843  return (nil, nil);
844  }
845  me: ref Entry;
846  if(de.mode&Modedir) {
847  me = vfreadentry(vd.vf, de.mentry);
848  if(me == nil)
849  return (nil, nil);
850  }
851  return (e, me);
852 }
853 
854 readdirentry(buf: array of byte, i: int): ref Direntry
855 {
856  me := Metaentry.unpack(buf, i);
857  if(me == nil)
858  return nil;
859  o := me.offset;
860  de := Direntry.unpack(buf[o:o+me.size]);
861  if(badelem(de.elem)) {
862  werrstr(sprint("bad direntry: %s", de.elem));
863  return nil;
864  }
865  return de;
866 }
867 
868 has(c: int, s: string): int
869 {
870  for(i := 0; i < len s; i++)
871  if(s[i] == c)
872  return 1;
873  return 0;
874 }
875 
876 badelem(elem: string): int
877 {
878  return elem == "" || elem == "." || elem == ".." || has('/', elem) || has(0, elem);
879 }
880 
881 Vacdir.readdir(vd: self ref Vacdir): (int, ref Direntry)
882 {
883  dsize := vd.ms.e.dsize;
884  n := vd.ms.get(vd.p, buf := array[dsize] of byte);
885  if(n <= 0)
886  return (n, nil);
887  mb := Metablock.unpack(buf);
888  if(mb == nil)
889  return (-1, nil);
890  de := readdirentry(buf, vd.i);
891  if(de == nil)
892  return (-1, nil);
893  vd.i++;
894  if(vd.i >= mb.nindex) {
895  vd.p++;
896  vd.i = 0;
897  }
898  return (1, de);
899 }
900 
901 Vacdir.rewind(vd: self ref Vacdir)
902 {
903  vd.p = big 0;
904  vd.i = 0;
905 }
906 
907 
908 openroot(session: ref Session, score: Venti->Score): (ref Vacdir, ref Direntry, string)
909 {
910  d := vread(session, score, Roottype, Rootsize);
911  if(d == nil)
912  return (nil, nil, sprint("reading vac score: %r"));
913  r := Root.unpack(d);
914  if(r == nil)
915  return (nil, nil, sprint("bad vac root block: %r"));
916  say("have root");
917  topscore := r.score;
918 
919  d = vread(session, topscore, Dirtype, 3*Entrysize);
920  if(d == nil)
921  return (nil, nil, sprint("reading rootdir score: %r"));
922  if(len d != 3*Entrysize) {
923  say("top entries not in directory of 3 elements, assuming it's from fossil");
924  if(len d % Entrysize != 0 && len d == 2*Entrysize != 0) # what's in the second 40 bytes? looks like 2nd 20 bytes of it is zero score
925  return (nil, nil, sprint("bad fossil rootdir, have %d bytes, need %d or %d", len d, Entrysize, 2*Entrysize));
926  e := Entry.unpack(d[:Entrysize]);
927  if(e == nil)
928  return (nil, nil, sprint("unpacking fossil top-level entry: %r"));
929  topscore = e.score;
930  d = vread(session, topscore, Dirtype, 3*Entrysize);
931  if(d == nil)
932  return (nil, nil, sprint("reading fossil rootdir block: %r"));
933  say("have fossil top entries");
934  }
935  say("have top entries");
936 
937  e := array[3] of ref Entry;
938  j := 0;
939  for(i := 0; i+Entrysize <= len d; i += Entrysize) {
940  e[j] = Entry.unpack(d[i:i+Entrysize]);
941  if(e[j] == nil)
942  return (nil, nil, sprint("reading root entry %d: %r", j));
943  j++;
944  }
945  say("top entries unpacked");
946 
947  mroot := Vacdir.new(session, nil, e[2]);
948  (ok, de) := mroot.readdir();
949  if(ok <= 0)
950  return (nil, nil, sprint("reading root meta entry: %r"));
951 
952 say(sprint("openroot: new score=%s", score.text()));
953  return (Vacdir.new(session, e[0], e[1]), de, nil);
954 }
955 
956 readscore(path: string): (string, ref Venti->Score, string)
957 {
958  f := sys->open(path, Sys->OREAD);
959  if(f == nil)
960  return (nil, nil, sprint("open: %r"));
961  n := sys->read(f, d := array[Rootnamelen+1+2*Scoresize+1] of byte, len d);
962  if(n < 0)
963  return (nil, nil, sprint("read: %r"));
964 
965  (tag, scorestr) := str->splitstrr(string d[:n], ":");
966  if(tag != nil)
967  tag = tag[:len tag-1];
968  if(tag != "vac")
969  return (nil, nil, "unknown score type: "+tag);
970  if(len scorestr == 2*Scoresize+1)
971  scorestr = scorestr[:len scorestr-1];
972  (ok, s) := Score.parse(scorestr);
973  if(ok != 0)
974  return (nil, nil, "bad score: "+scorestr);
975  return (tag, ref s, nil);
976 }
977 
978 g16(f: array of byte, i: int): int
979 {
980  return (int f[i] << 8) | int f[i+1];
981 }
982 
983 g32(f: array of byte, i: int): int
984 {
985  return (((((int f[i+0] << 8) | int f[i+1]) << 8) | int f[i+2]) << 8) | int f[i+3];
986 }
987 
988 g48(f: array of byte, i: int): big
989 {
990  b1 := (((((int f[i+0] << 8) | int f[i+1]) << 8) | int f[i+2]) << 8) | int f[i+3];
991  b0 := (int f[i+4] << 8) | int f[i+5];
992  return (big b1 << 16) | big b0;
993 }
994 
995 g64(f: array of byte, i: int): big
996 {
997  b0 := (((((int f[i+0] << 8) | int f[i+1]) << 8) | int f[i+2]) << 8) | int f[i+3];
998  b1 := (((((int f[i+4] << 8) | int f[i+5]) << 8) | int f[i+6]) << 8) | int f[i+7];
999  return (big b0 << 32) | (big b1 & 16rFFFFFFFF);
1000 }
1001 
1002 p16(d: array of byte, i: int, v: int): int
1003 {
1004  d[i+0] = byte (v>>8);
1005  d[i+1] = byte v;
1006  return i+BIT16SZ;
1007 }
1008 
1009 p32(d: array of byte, i: int, v: int): int
1010 {
1011  p16(d, i+0, v>>16);
1012  p16(d, i+2, v);
1013  return i+BIT32SZ;
1014 }
1015 
1016 p48(d: array of byte, i: int, v: big): int
1017 {
1018  p16(d, i+0, int (v>>32));
1019  p32(d, i+2, int v);
1020  return i+BIT48SZ;
1021 }
1022 
1023 p64(d: array of byte, i: int, v: big): int
1024 {
1025  p32(d, i+0, int (v>>32));
1026  p32(d, i+4, int v);
1027  return i+BIT64SZ;
1028 }
1029 
1030 echeck(f: array of byte, i: int, l: int)
1031 {
1032  if(i+l > len f)
1033  raise sprint("too small: buffer length is %d, requested %d bytes starting at offset %d", len f, l, i);
1034 }
1035 
1036 egstring(a: array of byte, o: int): (string, int)
1037 {
1038  (s, no) := gstring(a, o);
1039  if(no == -1)
1040  raise sprint("too small: string runs outside buffer (length %d)", len a);
1041  return (s, no);
1042 }
1043 
1044 eg16(f: array of byte, i: int): (int, int)
1045 {
1046  echeck(f, i, BIT16SZ);
1047  return (g16(f, i), i+BIT16SZ);
1048 }
1049 
1050 eg32(f: array of byte, i: int): (int, int)
1051 {
1052  echeck(f, i, BIT32SZ);
1053  return (g32(f, i), i+BIT32SZ);
1054 }
1055 
1056 eg48(f: array of byte, i: int): (big, int)
1057 {
1058  echeck(f, i, BIT48SZ);
1059  return (g48(f, i), i+BIT48SZ);
1060 }
1061 
1062 eg64(f: array of byte, i: int): (big, int)
1063 {
1064  echeck(f, i, BIT64SZ);
1065  return (g64(f, i), i+BIT64SZ);
1066 }
1067 
1068 say(s: string)
1069 {
1070  if(debug)
1071  fprint(fildes(2), "%s\n", s);
1072 }