sys/src/cmd/git/pack.c

   1 #include <u.h>
   2 #include <libc.h>
   3 #include <ctype.h>
   4
   5 #include "git.h"
   6
   7 typedef struct Buf      Buf;
   8 typedef struct Metavec  Metavec;
   9 typedef struct Meta     Meta;
  10 typedef struct Compout  Compout;
  11 typedef struct Packf    Packf;
  12
  13 #define max(x, y) ((x) > (y) ? (x) : (y))
  14
  15 struct Metavec {
  16         Meta    **meta;
  17         int     nmeta;
  18         int     metasz;
  19 };
  20
  21 struct Meta {
  22         Object  *obj;
  23         char    *path;
  24         vlong   mtime;
  25
  26         /* The best delta we picked */
  27         Meta    *head;
  28         Meta    *prev;
  29         Delta   *delta;
  30         int     ndelta;
  31         int     nchain;
  32
  33         /* Only used for delta window */
  34         Dtab    dtab;
  35
  36         /* Only used for writing offset deltas */
  37         vlong   off;
  38 };
  39
  40 struct Compout {
  41         Biobuf *bfd;
  42         DigestState *st;
  43 };
  44
  45 struct Buf {
  46         int len;
  47         int sz;
  48         int off;
  49         char *data;
  50 };
  51
  52 struct Packf {
  53         char    path[128];
  54         char    *idx;
  55         vlong   nidx;
  56
  57         int     refs;
  58         Biobuf  *pack;
  59         vlong   opentm;
  60 };
  61
  62 static int      readpacked(Biobuf *, Object *, int);
  63 static Object   *readidxobject(Biobuf *, Hash, int);
  64
  65 Objset objcache;
  66 Object *lruhead;
  67 Object *lrutail;
  68 int     ncache;
  69 int     cachemax = 4096;
  70 Packf   *packf;
  71 int     npackf;
  72 int     openpacks;
  73 int     gitdirmode = -1;
  74
  75 static void
  76 clear(Object *o)
  77 {
  78         if(!o)
  79                 return;
  80
  81         assert(o->refs == 0);
  82         assert((o->flag & Ccache) == 0);
  83         assert(o->flag & Cloaded);
  84         switch(o->type){
  85         case GCommit:
  86                 if(!o->commit)
  87                         break;
  88                 free(o->commit->parent);
  89                 free(o->commit->author);
  90                 free(o->commit->committer);
  91                 free(o->commit);
  92                 o->commit = nil;
  93                 break;
  94         case GTree:
  95                 if(!o->tree)
  96                         break;
  97                 free(o->tree->ent);
  98                 free(o->tree);
  99                 o->tree = nil;
 100                 break;
 101         default:
 102                 break;
 103         }
 104
 105         free(o->all);
 106         o->all = nil;
 107         o->data = nil;
 108         o->flag &= ~(Cloaded|Cparsed);
 109 }
 110
 111 void
 112 unref(Object *o)
 113 {
 114         if(!o)
 115                 return;
 116         o->refs--;
 117         if(o->refs == 0)
 118                 clear(o);
 119 }
 120
 121 Object*
 122 ref(Object *o)
 123 {
 124         o->refs++;
 125         return o;
 126 }
 127
 128 void
 129 cache(Object *o)
 130 {
 131         Object *p;
 132
 133         if(o == lruhead)
 134                 return;
 135         if(o == lrutail)
 136                 lrutail = lrutail->prev;
 137         if(!(o->flag & Cexist)){
 138                 osadd(&objcache, o);
 139                 o->id = objcache.nobj;
 140                 o->flag |= Cexist;
 141         }
 142         if(o->prev != nil)
 143                 o->prev->next = o->next;
 144         if(o->next != nil)
 145                 o->next->prev = o->prev;
 146         if(lrutail == o){
 147                 lrutail = o->prev;
 148                 if(lrutail != nil)
 149                         lrutail->next = nil;
 150         }else if(lrutail == nil)
 151                 lrutail = o;
 152         if(lruhead)
 153                 lruhead->prev = o;
 154         o->next = lruhead;
 155         o->prev = nil;
 156         lruhead = o;
 157
 158         if(!(o->flag & Ccache)){
 159                 o->flag |= Ccache;
 160                 ref(o);
 161                 ncache++;
 162         }
 163         while(ncache > cachemax && lrutail != nil){
 164                 p = lrutail;
 165                 lrutail = p->prev;
 166                 if(lrutail != nil)
 167                         lrutail->next = nil;
 168                 p->flag &= ~Ccache;
 169                 p->prev = nil;
 170                 p->next = nil;
 171                 unref(p);
 172                 ncache--;
 173         }
 174 }
 175
 176 static int
 177 loadpack(Packf *pf, char *name)
 178 {
 179         char buf[128];
 180         int i, ifd;
 181         Dir *d;
 182
 183         memset(pf, 0, sizeof(Packf));
 184         snprint(buf, sizeof(buf), ".git/objects/pack/%s.idx", name);
 185         snprint(pf->path, sizeof(pf->path), ".git/objects/pack/%s.pack", name);
 186         /*
 187          * if we already have the pack open, just
 188          * steal the loaded info
 189          */
 190         for(i = 0; i < npackf; i++){
 191                 if(strcmp(pf->path, packf[i].path) == 0){
 192                         pf->pack = packf[i].pack;
 193                         pf->idx = packf[i].idx;
 194                         pf->nidx = packf[i].nidx;
 195                         packf[i].idx = nil;
 196                         packf[i].pack = nil;
 197                 }
 198         }
 199         if((ifd = open(buf, OREAD)) == -1)
 200                 goto error;
 201         if((d = dirfstat(ifd)) == nil)
 202                 goto error;
 203         pf->nidx = d->length;
 204         pf->idx = emalloc(pf->nidx);
 205         if(readn(ifd, pf->idx, pf->nidx) != pf->nidx){
 206                 free(pf->idx);
 207                 free(d);
 208                 goto error;
 209         }
 210         free(d);
 211         return 0;
 212
 213 error:
 214         if(ifd != -1)
 215                 close(ifd);
 216         return -1;
 217 }
 218
 219 static void
 220 refreshpacks(void)
 221 {
 222         Packf *pf, *new;
 223         int i, n, l, nnew;
 224         Dir *d;
 225
 226         if((n = slurpdir(".git/objects/pack", &d)) == -1)
 227                 return;
 228         nnew = 0;
 229         new = eamalloc(n, sizeof(Packf));
 230         for(i = 0; i < n; i++){
 231                 l = strlen(d[i].name);
 232                 if(l > 4 && strcmp(d[i].name + l - 4, ".idx") != 0)
 233                         continue;
 234                 d[i].name[l - 4] = 0;
 235                 if(loadpack(&new[nnew], d[i].name) != -1)
 236                         nnew++;
 237         }
 238         for(i = 0; i < npackf; i++){
 239                 pf = &packf[i];
 240                 free(pf->idx);
 241                 if(pf->pack != nil)
 242                         Bterm(pf->pack);
 243         }
 244         free(packf);
 245         packf = new;
 246         npackf = nnew;
 247         free(d);
 248 }
 249
 250 static Biobuf*
 251 openpack(Packf *pf)
 252 {
 253         vlong t;
 254         int i, best;
 255
 256         if(pf->pack == nil){
 257                 if((pf->pack = Bopen(pf->path, OREAD)) == nil)
 258                         return nil;
 259                 openpacks++;
 260         }
 261         if(openpacks == Npackcache){
 262                 t = pf->opentm;
 263                 best = -1;
 264                 for(i = 0; i < npackf; i++){
 265                         if(packf[i].opentm < t && packf[i].refs > 0){
 266                                 t = packf[i].opentm;
 267                                 best = i;
 268                         }
 269                 }
 270                 if(best != -1){
 271                         Bterm(packf[best].pack);
 272                         packf[best].pack = nil;
 273                         openpacks--;
 274                 }
 275         }
 276         pf->opentm = nsec();
 277         pf->refs++;
 278         return pf->pack;
 279 }
 280
 281 static void
 282 closepack(Packf *pf)
 283 {
 284         if(--pf->refs == 0){
 285                 Bterm(pf->pack);
 286                 pf->pack = nil;
 287         }
 288 }
 289
 290 static u32int
 291 crc32(u32int crc, char *b, int nb)
 292 {
 293         static u32int crctab[256] = {
 294                 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f, 0xe963a535,
 295                 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988, 0x09b64c2b, 0x7eb17cbd,
 296                 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de, 0x1adad47d,
 297                 0x6ddde4eb, 0xf4d4b551, 0x83d385c7, 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec,
 298                 0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4,
 299                 0xa2677172, 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c,
 300                 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59, 0x26d930ac,
 301                 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f,
 302                 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924, 0x2f6f7c87, 0x58684c11, 0xc1611dab,
 303                 0xb6662d3d, 0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f,
 304                 0x9fbfe4a5, 0xe8b8d433, 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb,
 305                 0x086d3d2d, 0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
 306                 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea,
 307                 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65, 0x4db26158, 0x3ab551ce,
 308                 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a,
 309                 0x346ed9fc, 0xad678846, 0xda60b8d0, 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9,
 310                 0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409,
 311                 0xce61e49f, 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
 312                 0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a, 0xead54739,
 313                 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8,
 314                 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1, 0xf00f9344, 0x8708a3d2, 0x1e01f268,
 315                 0x6906c2fe, 0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0,
 316                 0x10da7a5a, 0x67dd4acc, 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8,
 317                 0xa1d1937e, 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
 318                 0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55, 0x316e8eef,
 319                 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236, 0xcc0c7795, 0xbb0b4703,
 320                 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7,
 321                 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d, 0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a,
 322                 0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae,
 323                 0x0cb61b38, 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
 324                 0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777, 0x88085ae6,
 325                 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45,
 326                 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2, 0xa7672661, 0xd06016f7, 0x4969474d,
 327                 0x3e6e77db, 0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5,
 328                 0x47b2cf7f, 0x30b5ffe9, 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605,
 329                 0xcdd70693, 0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
 330                 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
 331         };
 332         int i;
 333
 334         crc ^=  0xFFFFFFFF;
 335         for(i = 0; i < nb; i++)
 336                 crc = (crc >> 8) ^ crctab[(crc ^ b[i]) & 0xFF];
 337         return crc ^ 0xFFFFFFFF;
 338 }
 339
 340 int
 341 bappend(void *p, void *src, int len)
 342 {
 343         Buf *b = p;
 344         char *n;
 345
 346         while(b->len + len >= b->sz){
 347                 b->sz = b->sz*2 + 64;
 348                 n = realloc(b->data, b->sz);
 349                 if(n == nil)
 350                         return -1;
 351                 b->data = n;
 352         }
 353         memmove(b->data + b->len, src, len);
 354         b->len += len;
 355         return len;
 356 }
 357
 358 int
 359 breadc(void *p)
 360 {
 361         return Bgetc(p);
 362 }
 363
 364 int
 365 bdecompress(Buf *d, Biobuf *b, vlong *csz)
 366 {
 367         vlong o;
 368
 369         o = Boffset(b);
 370         if(inflatezlib(d, bappend, b, breadc) == -1 || d->data == nil){
 371                 free(d->data);
 372                 return -1;
 373         }
 374         if (csz)
 375                 *csz = Boffset(b) - o;
 376         return d->len;
 377 }
 378
 379 int
 380 decompress(void **p, Biobuf *b, vlong *csz)
 381 {
 382         Buf d = {.len=0, .data=nil, .sz=0};
 383
 384         if(bdecompress(&d, b, csz) == -1){
 385                 free(d.data);
 386                 return -1;
 387         }
 388         *p = d.data;
 389         return d.len;
 390 }
 391
 392 static vlong
 393 readvint(char *p, char **pp)
 394 {
 395         int s, c;
 396         vlong n;
 397
 398         s = 0;
 399         n = 0;
 400         do {
 401                 c = *p++;
 402                 n |= (c & 0x7f) << s;
 403                 s += 7;
 404         } while (c & 0x80 && s < 63);
 405         *pp = p;
 406
 407         return n;
 408 }
 409
 410 static int
 411 applydelta(Object *dst, Object *base, char *d, int nd)
 412 {
 413         char *r, *b, *ed, *er;
 414         int n, nr, c;
 415         vlong o, l;
 416
 417         ed = d + nd;
 418         b = base->data;
 419         n = readvint(d, &d);
 420         if(n != base->size){
 421                 werrstr("mismatched source size");
 422                 return -1;
 423         }
 424
 425         nr = readvint(d, &d);
 426         r = emalloc(nr + 64);
 427         n = snprint(r, 64, "%T %d", base->type, nr) + 1;
 428         dst->all = r;
 429         dst->type = base->type;
 430         dst->data = r + n;
 431         dst->size = nr;
 432         er = dst->data + nr;
 433         r = dst->data;
 434
 435         while(d != ed){
 436                 c = *d++;
 437                 /* copy from base */
 438                 if(c & 0x80){
 439                         o = 0;
 440                         l = 0;
 441                         /* Offset in base */
 442                         if(d != ed && (c & 0x01)) o |= (*d++ <<  0) & 0x000000ff;
 443                         if(d != ed && (c & 0x02)) o |= (*d++ <<  8) & 0x0000ff00;
 444                         if(d != ed && (c & 0x04)) o |= (*d++ << 16) & 0x00ff0000;
 445                         if(d != ed && (c & 0x08)) o |= (*d++ << 24) & 0xff000000;
 446
 447                         /* Length to copy */
 448                         if(d != ed && (c & 0x10)) l |= (*d++ <<  0) & 0x0000ff;
 449                         if(d != ed && (c & 0x20)) l |= (*d++ <<  8) & 0x00ff00;
 450                         if(d != ed && (c & 0x40)) l |= (*d++ << 16) & 0xff0000;
 451                         if(l == 0) l = 0x10000;
 452
 453                         if(o + l > base->size){
 454                                 werrstr("garbled delta: out of bounds copy");
 455                                 return -1;
 456                         }
 457                         memmove(r, b + o, l);
 458                         r += l;
 459                 /* inline data */
 460                 }else{
 461                         if(c > ed - d){
 462                                 werrstr("garbled delta: write past object");
 463                                 return -1;
 464                         }
 465                         memmove(r, d, c);
 466                         d += c;
 467                         r += c;
 468                 }
 469         }
 470         if(r != er){
 471                 werrstr("truncated delta");
 472                 return -1;
 473         }
 474
 475         return nr;
 476 }
 477
 478 static int
 479 readrdelta(Biobuf *f, Object *o, int nd, int flag)
 480 {
 481         Object *b;
 482         Hash h;
 483         char *d;
 484         int n;
 485
 486         d = nil;
 487         if(Bread(f, h.h, sizeof(h.h)) != sizeof(h.h))
 488                 goto error;
 489         if(hasheq(&o->hash, &h))
 490                 goto error;
 491         if((n = decompress(&d, f, nil)) == -1)
 492                 goto error;
 493         o->len = Boffset(f) - o->off;
 494         if(d == nil || n != nd)
 495                 goto error;
 496         if((b = readidxobject(f, h, flag|Cthin)) == nil)
 497                 goto error;
 498         if(applydelta(o, b, d, n) == -1)
 499                 goto error;
 500         free(d);
 501         return 0;
 502 error:
 503         free(d);
 504         return -1;
 505 }
 506
 507 static int
 508 readodelta(Biobuf *f, Object *o, vlong nd, vlong p, int flag)
 509 {
 510         Object b;
 511         char *d;
 512         vlong r;
 513         int c, n;
 514
 515         d = nil;
 516         if((c = Bgetc(f)) == -1)
 517                 return -1;
 518         r = c & 0x7f;
 519         while(c & 0x80 && r < (1ULL<<56)){
 520                 if((c = Bgetc(f)) == -1)
 521                         return -1;
 522                 r = ((r + 1)<<7) | (c & 0x7f);
 523         }
 524
 525         if(r > p || r >= (1ULL<<56)){
 526                 werrstr("junk offset -%lld (from %lld)", r, p);
 527                 goto error;
 528         }
 529         if((n = decompress(&d, f, nil)) == -1)
 530                 goto error;
 531         o->len = Boffset(f) - o->off;
 532         if(d == nil || n != nd)
 533                 goto error;
 534         if(Bseek(f, p - r, 0) == -1)
 535                 goto error;
 536         memset(&b, 0, sizeof(Object));
 537         if(readpacked(f, &b, flag) == -1)
 538                 goto error;
 539         if(applydelta(o, &b, d, nd) == -1)
 540                 goto error;
 541         clear(&b);
 542         free(d);
 543         return 0;
 544 error:
 545         free(d);
 546         return -1;
 547 }
 548
 549 static int
 550 readpacked(Biobuf *f, Object *o, int flag)
 551 {
 552         int c, s, n;
 553         vlong l, p;
 554         int t;
 555         Buf b;
 556
 557         p = Boffset(f);
 558         c = Bgetc(f);
 559         if(c == -1)
 560                 return -1;
 561         l = c & 0xf;
 562         s = 4;
 563         t = (c >> 4) & 0x7;
 564         if(!t){
 565                 werrstr("unknown type for byte %x at %lld", c, p);
 566                 return -1;
 567         }
 568         while(c & 0x80){
 569                 if((c = Bgetc(f)) == -1)
 570                         return -1;
 571                 l |= (c & 0x7f) << s;
 572                 s += 7;
 573         }
 574         if(l >= (1ULL << 32)){
 575                 werrstr("object too big");
 576                 return -1;
 577         }
 578         switch(t){
 579         default:
 580                 werrstr("invalid object at %lld", Boffset(f));
 581                 return -1;
 582         case GCommit:
 583         case GTree:
 584         case GTag:
 585         case GBlob:
 586                 b.sz = 64 + l;
 587                 b.data = emalloc(b.sz);
 588                 n = snprint(b.data, 64, "%T %lld", t, l) + 1;
 589                 b.len = n;
 590                 if(bdecompress(&b, f, nil) == -1){
 591                         free(b.data);
 592                         return -1;
 593                 }
 594                 o->len = Boffset(f) - o->off;
 595                 o->type = t;
 596                 o->all = b.data;
 597                 o->data = b.data + n;
 598                 o->size = b.len - n;
 599                 break;
 600         case GOdelta:
 601                 if(readodelta(f, o, l, p, flag) == -1)
 602                         return -1;
 603                 break;
 604         case GRdelta:
 605                 if(readrdelta(f, o, l, flag) == -1)
 606                         return -1;
 607                 break;
 608         }
 609         o->flag |= Cloaded|flag;
 610         return 0;
 611 }
 612
 613 static int
 614 readloose(Biobuf *f, Object *o, int flag)
 615 {
 616         struct { char *tag; int type; } *p, types[] = {
 617                 {"blob", GBlob},
 618                 {"tree", GTree},
 619                 {"commit", GCommit},
 620                 {"tag", GTag},
 621                 {nil},
 622         };
 623         char *d, *s, *e;
 624         vlong sz, n;
 625         int l;
 626
 627         n = decompress(&d, f, nil);
 628         if(n == -1)
 629                 return -1;
 630
 631         s = d;
 632         o->type = GNone;
 633         for(p = types; p->tag; p++){
 634                 l = strlen(p->tag);
 635                 if(strncmp(s, p->tag, l) == 0){
 636                         s += l;
 637                         o->type = p->type;
 638                         while(!isspace(*s))
 639                                 s++;
 640                         break;
 641                 }
 642         }
 643         if(o->type == GNone){
 644                 free(o->data);
 645                 return -1;
 646         }
 647         sz = strtol(s, &e, 0);
 648         if(e == s || *e++ != 0){
 649                 werrstr("malformed object header");
 650                 goto error;
 651         }
 652         if(sz != n - (e - d)){
 653                 werrstr("mismatched sizes");
 654                 goto error;
 655         }
 656         o->size = sz;
 657         o->data = e;
 658         o->all = d;
 659         o->flag |= Cloaded|flag;
 660         return 0;
 661
 662 error:
 663         free(d);
 664         return -1;
 665 }
 666
 667 vlong
 668 searchindex(char *idx, int nidx, Hash h)
 669 {
 670         int lo, hi, hidx, i, r, nent;
 671         vlong o, oo;
 672         void *s;
 673
 674         o = 8;
 675         if(nidx < 8 + 256*4)
 676                 return -1;
 677         /*
 678          * Read the fanout table. The fanout table
 679          * contains 256 entries, corresponsding to
 680          * the first byte of the hash. Each entry
 681          * is a 4 byte big endian integer, containing
 682          * the total number of entries with a leading
 683          * byte <= the table index, allowing us to
 684          * rapidly do a binary search on them.
 685          */
 686         if (h.h[0] == 0){
 687                 lo = 0;
 688                 hi = GETBE32(idx + o);
 689         } else {
 690                 o += h.h[0]*4 - 4;
 691                 lo = GETBE32(idx + o);
 692                 hi = GETBE32(idx + o + 4);
 693         }
 694         if(hi == lo)
 695                 goto notfound;
 696         nent=GETBE32(idx + 8 + 255*4);
 697
 698         /*
 699          * Now that we know the range of hashes that the
 700          * entry may exist in, search them
 701          */
 702         r = -1;
 703         hidx = -1;
 704         o = 8 + 256*4;
 705         while(lo < hi){
 706                 hidx = (hi + lo)/2;
 707                 s = idx + o + hidx*sizeof(h.h);
 708                 r = memcmp(h.h, s, sizeof(h.h));
 709                 if(r < 0)
 710                         hi = hidx;
 711                 else if(r > 0)
 712                         lo = hidx + 1;
 713                 else
 714                         break;
 715         }
 716         if(r != 0)
 717                 goto notfound;
 718
 719         /*
 720          * We found the entry. If it's 32 bits, then we
 721          * can just return the oset, otherwise the 32
 722          * bit entry contains the oset to the 64 bit
 723          * entry.
 724          */
 725         oo = 8;                 /* Header */
 726         oo += 256*4;            /* Fanout table */
 727         oo += Hashsz*nent;      /* Hashes */
 728         oo += 4*nent;           /* Checksums */
 729         oo += 4*hidx;           /* Offset offset */
 730         if(oo < 0 || oo + 4 > nidx)
 731                 goto err;
 732         i = GETBE32(idx + oo);
 733         o = i & 0xffffffffULL;
 734         /*
 735          * Large offsets (i.e. 64-bit) are encoded as an index
 736          * into the next table with the MSB bit set.
 737          */
 738         if(o & (1ull << 31)){
 739                 o &= 0x7fffffffULL;
 740                 oo = 8;                         /* Header */
 741                 oo += 256*4;                    /* Fanout table */
 742                 oo += Hashsz*nent;              /* Hashes */
 743                 oo += 4*nent;                   /* Checksums */
 744                 oo += 4*nent;                   /* 32-bit Offsets */
 745                 oo += 8*o;                      /* 64-bit Offset offset */
 746                 if(oo < 0 || oo + 8 >= nidx)
 747                         goto err;
 748                 o = GETBE64(idx + oo);
 749         }
 750         return o;
 751
 752 err:
 753         werrstr("out of bounds read");
 754         return -1;
 755 notfound:
 756         werrstr("not present");
 757         return -1;
 758 }
 759
 760 /*
 761  * Scans for non-empty word, copying it into buf.
 762  * Strips off word, leading, and trailing space
 763  * from input.
 764  *
 765  * Returns -1 on empty string or error, leaving
 766  * input unmodified.
 767  */
 768 static int
 769 scanword(char **str, int *nstr, char *buf, int nbuf)
 770 {
 771         char *p;
 772         int n, r;
 773
 774         r = -1;
 775         p = *str;
 776         n = *nstr;
 777         while(n && isblank(*p)){
 778                 n--;
 779                 p++;
 780         }
 781
 782         for(; n && *p && !isspace(*p); p++, n--){
 783                 r = 0;
 784                 *buf++ = *p;
 785                 nbuf--;
 786                 if(nbuf == 0)
 787                         return -1;
 788         }
 789         while(n && isblank(*p)){
 790                 n--;
 791                 p++;
 792         }
 793         *buf = 0;
 794         *str = p;
 795         *nstr = n;
 796         return r;
 797 }
 798
 799 static void
 800 nextline(char **str, int *nstr)
 801 {
 802         char *s;
 803
 804         if((s = strchr(*str, '\n')) != nil){
 805                 *nstr -= s - *str + 1;
 806                 *str = s + 1;
 807         }
 808 }
 809
 810 static int
 811 parseauthor(char **str, int *nstr, char **name, vlong *time)
 812 {
 813         char buf[128];
 814         Resub m[4];
 815         char *p;
 816         int n, nm;
 817
 818         if((p = strchr(*str, '\n')) == nil)
 819                 sysfatal("malformed author line");
 820         n = p - *str;
 821         if(n >= sizeof(buf))
 822                 sysfatal("overlong author line");
 823         memset(m, 0, sizeof(m));
 824         snprint(buf, n + 1, *str);
 825         *str = p;
 826         *nstr -= n;
 827
 828         if(!regexec(authorpat, buf, m, nelem(m)))
 829                 sysfatal("invalid author line %s", buf);
 830         nm = m[1].ep - m[1].sp;
 831         *name = emalloc(nm + 1);
 832         memcpy(*name, m[1].sp, nm);
 833         buf[nm] = 0;
 834
 835         nm = m[2].ep - m[2].sp;
 836         memcpy(buf, m[2].sp, nm);
 837         buf[nm] = 0;
 838         *time = atoll(buf);
 839         return 0;
 840 }
 841
 842 static void
 843 parsecommit(Object *o)
 844 {
 845         char *p, *t, buf[128];
 846         int np;
 847
 848         p = o->data;
 849         np = o->size;
 850         o->commit = emalloc(sizeof(Cinfo));
 851         while(1){
 852                 if(scanword(&p, &np, buf, sizeof(buf)) == -1)
 853                         break;
 854                 if(strcmp(buf, "tree") == 0){
 855                         if(scanword(&p, &np, buf, sizeof(buf)) == -1)
 856                                 sysfatal("invalid commit: tree missing");
 857                         if(hparse(&o->commit->tree, buf) == -1)
 858                                 sysfatal("invalid commit: garbled tree");
 859                 }else if(strcmp(buf, "parent") == 0){
 860                         if(scanword(&p, &np, buf, sizeof(buf)) == -1)
 861                                 sysfatal("invalid commit: missing parent");
 862                         o->commit->parent = realloc(o->commit->parent, ++o->commit->nparent * sizeof(Hash));
 863                         if(!o->commit->parent)
 864                                 sysfatal("unable to malloc: %r");
 865                         if(hparse(&o->commit->parent[o->commit->nparent - 1], buf) == -1)
 866                                 sysfatal("invalid commit: garbled parent");
 867                 }else if(strcmp(buf, "author") == 0){
 868                         parseauthor(&p, &np, &o->commit->author, &o->commit->mtime);
 869                 }else if(strcmp(buf, "committer") == 0){
 870                         parseauthor(&p, &np, &o->commit->committer, &o->commit->ctime);
 871                 }else if(strcmp(buf, "gpgsig") == 0){
 872                         /* just drop it */
 873                         if((t = strstr(p, "-----END PGP SIGNATURE-----")) == nil)
 874                                 sysfatal("malformed gpg signature");
 875                         np -= t - p;
 876                         p = t;
 877                 }
 878                 nextline(&p, &np);
 879         }
 880         while (np && isspace(*p)) {
 881                 p++;
 882                 np--;
 883         }
 884         o->commit->msg = p;
 885         o->commit->nmsg = np;
 886 }
 887
 888 static void
 889 parsetree(Object *o)
 890 {
 891         int m, a, entsz, nent;
 892         Dirent *t, *ent;
 893         char *p, *ep;
 894
 895         p = o->data;
 896         ep = p + o->size;
 897
 898         nent = 0;
 899         entsz = 16;
 900         ent = eamalloc(entsz, sizeof(Dirent));
 901         o->tree = emalloc(sizeof(Tinfo));
 902         while(p != ep){
 903                 if(nent == entsz){
 904                         entsz *= 2;
 905                         ent = earealloc(ent, entsz, sizeof(Dirent));
 906                 }
 907                 t = &ent[nent++];
 908                 m = strtol(p, &p, 8);
 909                 if(*p != ' ')
 910                         sysfatal("malformed tree %H: *p=(%d) %c\n", o->hash, *p, *p);
 911                 p++;
 912                 /*
 913                  * only the stored permissions for the user
 914                  * are relevant; git fills group and world
 915                  * bits with whatever -- so to serve with
 916                  * useful permissions, replicate the mode
 917                  * of the git repo dir.
 918                  */
 919                 a = (m & 0777)>>6;
 920                 t->mode = ((a<<6)|(a<<3)|a) & gitdirmode;
 921                 t->ismod = 0;
 922                 t->islink = 0;
 923                 if(m == 0160000){
 924                         t->mode |= DMDIR;
 925                         t->ismod = 1;
 926                 }else if(m == 0120000){
 927                         t->mode = 0;
 928                         t->islink = 1;
 929                 }
 930                 if(m & 0040000)
 931                         t->mode |= DMDIR;
 932                 t->name = p;
 933                 p = memchr(p, 0, ep - p);
 934                 if(*p++ != 0 ||  ep - p < sizeof(t->h.h))
 935                         sysfatal("malformed tree %H, remaining %d (%s)", o->hash, (int)(ep - p), p);
 936                 memcpy(t->h.h, p, sizeof(t->h.h));
 937                 p += sizeof(t->h.h);
 938         }
 939         o->tree->ent = ent;
 940         o->tree->nent = nent;
 941 }
 942
 943 static void
 944 parsetag(Object *)
 945 {
 946 }
 947
 948 void
 949 parseobject(Object *o)
 950 {
 951         if(o->flag & Cparsed)
 952                 return;
 953         switch(o->type){
 954         case GTree:     parsetree(o);   break;
 955         case GCommit:   parsecommit(o); break;
 956         case GTag:      parsetag(o);    break;
 957         default:        break;
 958         }
 959         o->flag |= Cparsed;
 960 }
 961
 962 static Object*
 963 readidxobject(Biobuf *idx, Hash h, int flag)
 964 {
 965         char path[Pathmax], hbuf[41];
 966         Object *obj, *new;
 967         int i, r, retried;
 968         Biobuf *f;
 969         vlong o;
 970
 971         if((obj = osfind(&objcache, h)) != nil){
 972                 if(flag & Cidx){
 973                         /*
 974                          * If we're indexing, we need to be careful
 975                          * to only return objects within this pack,
 976                          * so if the objects exist outside the pack,
 977                          * we don't index the wrong copy.
 978                          */
 979                         if(!(obj->flag & Cidx))
 980                                 return nil;
 981                         if(obj->flag & Cloaded)
 982                                 return obj;
 983                         o = Boffset(idx);
 984                         if(Bseek(idx, obj->off, 0) == -1)
 985                                 return nil;
 986                         if(readpacked(idx, obj, flag) == -1)
 987                                 return nil;
 988                         if(Bseek(idx, o, 0) == -1)
 989                                 sysfatal("could not restore offset");
 990                         cache(obj);
 991                         return obj;
 992                 }
 993                 if(obj->flag & Cloaded)
 994                         return obj;
 995         }
 996         if(flag & Cthin)
 997                 flag &= ~Cidx;
 998         if(flag & Cidx)
 999                 return nil;
1000         new = nil;
1001         if(obj == nil){
1002                 new = emalloc(sizeof(Object));
1003                 new->id = objcache.nobj + 1;
1004                 new->hash = h;
1005                 obj = new;
1006         }
1007
1008         o = -1;
1009         retried = 0;
1010 retry:
1011         for(i = 0; i < npackf; i++){
1012                 o = searchindex(packf[i].idx, packf[i].nidx, h);
1013                 if(o != -1){
1014                         if((f = openpack(&packf[i])) == nil)
1015                                 goto error;
1016                         if((r = Bseek(f, o, 0)) != -1)
1017                                 r = readpacked(f, obj, flag);
1018                         closepack(&packf[i]);
1019                         if(r == -1)
1020                                 goto error;
1021                         parseobject(obj);
1022                         cache(obj);
1023                         return obj;
1024                 }
1025         }
1026
1027
1028         snprint(hbuf, sizeof(hbuf), "%H", h);
1029         snprint(path, sizeof(path), ".git/objects/%c%c/%s", hbuf[0], hbuf[1], hbuf + 2);
1030         if((f = Bopen(path, OREAD)) != nil){
1031                 if(readloose(f, obj, flag) == -1)
1032                         goto errorf;
1033                 Bterm(f);
1034                 parseobject(obj);
1035                 cache(obj);
1036                 return obj;
1037         }
1038
1039         if(o == -1){
1040                 if(retried)
1041                         goto error;
1042                 retried = 1;
1043                 refreshpacks();
1044                 goto retry;
1045         }
1046 errorf:
1047         Bterm(f);
1048 error:
1049         free(new);
1050         return nil;
1051 }
1052
1053 /*
1054  * Loads and returns a cached object.
1055  */
1056 Object*
1057 readobject(Hash h)
1058 {
1059         Object *o;
1060         Dir *d;
1061
1062         if(gitdirmode == -1){
1063                 if((d = dirstat(".git")) == nil)
1064                         sysfatal("stat .git: %r");
1065                 gitdirmode = d->mode & 0777;
1066                 free(d);
1067         }
1068         if((o = readidxobject(nil, h, 0)) == nil)
1069                 return nil;
1070         parseobject(o);
1071         ref(o);
1072         return o;
1073 }
1074
1075 /*
1076  * Creates and returns a cached, cleared object
1077  * that will get loaded some other time. Useful
1078  * for performance if need to mark that a blob
1079  * exists, but we don't care about its contents.
1080  *
1081  * The refcount of the returned object is 0, so
1082  * it doesn't need to be unrefed.
1083  */
1084 Object*
1085 clearedobject(Hash h, int type)
1086 {
1087         Object *o;
1088
1089         if((o = osfind(&objcache, h)) != nil)
1090                 return o;
1091
1092         o = emalloc(sizeof(Object));
1093         o->hash = h;
1094         o->type = type;
1095         osadd(&objcache, o);
1096         o->id = objcache.nobj;
1097         o->flag |= Cexist;
1098         return o;
1099 }
1100
1101 int
1102 objcmp(void *pa, void *pb)
1103 {
1104         Object *a, *b;
1105
1106         a = *(Object**)pa;
1107         b = *(Object**)pb;
1108         return memcmp(a->hash.h, b->hash.h, sizeof(a->hash.h));
1109 }
1110
1111 static int
1112 hwrite(Biobuf *b, void *buf, int len, DigestState **st)
1113 {
1114         *st = sha1(buf, len, nil, *st);
1115         return Bwrite(b, buf, len);
1116 }
1117
1118 static u32int
1119 objectcrc(Biobuf *f, Object *o)
1120 {
1121         char buf[8096];
1122         int n, r;
1123
1124         o->crc = 0;
1125         Bseek(f, o->off, 0);
1126         for(n = o->len; n > 0; n -= r){
1127                 r = Bread(f, buf, n > sizeof(buf) ? sizeof(buf) : n);
1128                 if(r == -1)
1129                         return -1;
1130                 if(r == 0)
1131                         return 0;
1132                 o->crc = crc32(o->crc, buf, r);
1133         }
1134         return 0;
1135 }
1136
1137 int
1138 indexpack(char *pack, char *idx, Hash ph)
1139 {
1140         char hdr[4*3], buf[8];
1141         int nobj, npct, nvalid, nbig;
1142         int i, n, pct;
1143         Object *o, **obj;
1144         DigestState *st;
1145         char *valid;
1146         Biobuf *f;
1147         Hash h;
1148         int c;
1149
1150         if((f = Bopen(pack, OREAD)) == nil)
1151                 return -1;
1152         if(Bread(f, hdr, sizeof(hdr)) != sizeof(hdr)){
1153                 werrstr("short read on header");
1154                 return -1;
1155         }
1156         if(memcmp(hdr, "PACK\0\0\0\2", 8) != 0){
1157                 werrstr("invalid header");
1158                 return -1;
1159         }
1160
1161         pct = 0;
1162         npct = 0;
1163         nvalid = 0;
1164         nobj = GETBE32(hdr + 8);
1165         obj = eamalloc(nobj, sizeof(Object*));
1166         valid = eamalloc(nobj, sizeof(char));
1167         if(interactive)
1168                 fprint(2, "indexing %d objects:   0%%", nobj);
1169         while(nvalid != nobj){
1170                 n = 0;
1171                 for(i = 0; i < nobj; i++){
1172                         if(valid[i]){
1173                                 n++;
1174                                 continue;
1175                         }
1176                         pct = showprogress((npct*100)/nobj, pct);
1177                         if(obj[i] == nil){
1178                                 o = emalloc(sizeof(Object));
1179                                 o->off = Boffset(f);
1180                                 obj[i] = o;
1181                         }
1182                         o = obj[i];
1183                         /*
1184                          * We can seek around when packing delta chains.
1185                          * Be extra careful while we don't know where all
1186                          * the objects start.
1187                          */
1188                         Bseek(f, o->off, 0);
1189                         if(readpacked(f, o, Cidx) == -1)
1190                                 continue;
1191                         sha1((uchar*)o->all, o->size + strlen(o->all) + 1, o->hash.h, nil);
1192                         valid[i] = 1;
1193                         cache(o);
1194                         npct++;
1195                         n++;
1196                         if(objectcrc(f, o) == -1)
1197                                 return -1;
1198                 }
1199                 if(n == nvalid){
1200                         sysfatal("fix point reached too early: %d/%d: %r", nvalid, nobj);
1201                         goto error;
1202                 }
1203                 nvalid = n;
1204         }
1205         if(interactive)
1206                 fprint(2, "\b\b\b\b100%%\n");
1207         Bterm(f);
1208
1209         st = nil;
1210         qsort(obj, nobj, sizeof(Object*), objcmp);
1211         if((f = Bopen(idx, OWRITE)) == nil)
1212                 return -1;
1213         if(hwrite(f, "\xfftOc\x00\x00\x00\x02", 8, &st) != 8)
1214                 goto error;
1215         /* fanout table */
1216         c = 0;
1217         for(i = 0; i < 256; i++){
1218                 while(c < nobj && (obj[c]->hash.h[0] & 0xff) <= i)
1219                         c++;
1220                 PUTBE32(buf, c);
1221                 if(hwrite(f, buf, 4, &st) == -1)
1222                         goto error;
1223         }
1224         for(i = 0; i < nobj; i++){
1225                 o = obj[i];
1226                 if(hwrite(f, o->hash.h, sizeof(o->hash.h), &st) == -1)
1227                         goto error;
1228         }
1229
1230         for(i = 0; i < nobj; i++){
1231                 PUTBE32(buf, obj[i]->crc);
1232                 if(hwrite(f, buf, 4, &st) == -1)
1233                         goto error;
1234         }
1235
1236         nbig = 0;
1237         for(i = 0; i < nobj; i++){
1238                 if(obj[i]->off < (1ull<<31))
1239                         PUTBE32(buf, obj[i]->off);
1240                 else{
1241                         PUTBE32(buf, (1ull << 31) | nbig);
1242                         nbig++;
1243                 }
1244                 if(hwrite(f, buf, 4, &st) == -1)
1245                         goto error;
1246         }
1247         for(i = 0; i < nobj; i++){
1248                 if(obj[i]->off >= (1ull<<31)){
1249                         PUTBE64(buf, obj[i]->off);
1250                         if(hwrite(f, buf, 8, &st) == -1)
1251                                 goto error;
1252                 }
1253         }
1254         if(hwrite(f, ph.h, sizeof(ph.h), &st) == -1)
1255                 goto error;
1256         sha1(nil, 0, h.h, st);
1257         Bwrite(f, h.h, sizeof(h.h));
1258
1259         free(obj);
1260         free(valid);
1261         Bterm(f);
1262         return 0;
1263
1264 error:
1265         free(obj);
1266         free(valid);
1267         Bterm(f);
1268         return -1;
1269 }
1270
1271 static int
1272 deltaordercmp(void *pa, void *pb)
1273 {
1274         Meta *a, *b;
1275         int cmp;
1276
1277         a = *(Meta**)pa;
1278         b = *(Meta**)pb;
1279         if(a->obj->type != b->obj->type)
1280                 return a->obj->type - b->obj->type;
1281         cmp = strcmp(a->path, b->path);
1282         if(cmp != 0)
1283                 return cmp;
1284         if(a->mtime != b->mtime)
1285                 return a->mtime - b->mtime;
1286         return memcmp(a->obj->hash.h, b->obj->hash.h, sizeof(a->obj->hash.h));
1287 }
1288
1289 static int
1290 writeordercmp(void *pa, void *pb)
1291 {
1292         Meta *a, *b, *ahd, *bhd;
1293
1294         a = *(Meta**)pa;
1295         b = *(Meta**)pb;
1296         ahd = (a->head == nil) ? a : a->head;
1297         bhd = (b->head == nil) ? b : b->head;
1298         if(ahd->mtime != bhd->mtime)
1299                 return bhd->mtime - ahd->mtime;
1300         if(ahd != bhd)
1301                 return (uintptr)bhd - (uintptr)ahd;
1302         if(a->nchain != b->nchain)
1303                 return a->nchain - b->nchain;
1304         return a->mtime - b->mtime;
1305 }
1306
1307 static void
1308 addmeta(Metavec *v, Objset *has, Object *o, char *path, vlong mtime)
1309 {
1310         Meta *m;
1311
1312         if(oshas(has, o->hash))
1313                 return;
1314         osadd(has, o);
1315         if(v == nil)
1316                 return;
1317         m = emalloc(sizeof(Meta));
1318         m->obj = o;
1319         m->path = estrdup(path);
1320         m->mtime = mtime;
1321
1322         if(v->nmeta == v->metasz){
1323                 v->metasz = 2*v->metasz;
1324                 v->meta = earealloc(v->meta, v->metasz, sizeof(Meta*));
1325         }
1326         v->meta[v->nmeta++] = m;
1327 }
1328
1329 static void
1330 freemeta(Meta *m)
1331 {
1332         free(m->delta);
1333         free(m->path);
1334         free(m);
1335 }
1336
1337 static int
1338 loadtree(Metavec *v, Objset *has, Hash tree, char *dpath, vlong mtime)
1339 {
1340         Object *t, *o;
1341         Dirent *e;
1342         char *p;
1343         int i, k;
1344
1345         if(oshas(has, tree))
1346                 return 0;
1347         if((t = readobject(tree)) == nil)
1348                 return -1;
1349         if(t->type != GTree){
1350                 fprint(2, "load: %H: not tree\n", t->hash);
1351                 unref(t);
1352                 return 0;
1353         }
1354         addmeta(v, has, t, dpath, mtime);
1355         for(i = 0; i < t->tree->nent; i++){
1356                 e = &t->tree->ent[i];
1357                 if(oshas(has, e->h))
1358                         continue;
1359                 if(e->ismod)
1360                         continue;
1361                 k = (e->mode & DMDIR) ? GTree : GBlob;
1362                 o = clearedobject(e->h, k);
1363                 p = smprint("%s/%s", dpath, e->name);
1364                 if(k == GBlob)
1365                         addmeta(v, has, o, p, mtime);
1366                 else if(loadtree(v, has, e->h, p, mtime) == -1){
1367                         free(p);
1368                         return -1;
1369                 }
1370                 free(p);
1371         }
1372         unref(t);
1373         return 0;
1374 }
1375
1376 static int
1377 loadcommit(Metavec *v, Objset *has, Hash h)
1378 {
1379         Object *c;
1380         int r;
1381
1382         if(osfind(has, h))
1383                 return 0;
1384         if((c = readobject(h)) == nil)
1385                 return -1;
1386         if(c->type != GCommit){
1387                 fprint(2, "load: %H: not commit\n", c->hash);
1388                 unref(c);
1389                 return 0;
1390         }
1391         addmeta(v, has, c, "", c->commit->ctime);
1392         r = loadtree(v, has, c->commit->tree, "", c->commit->ctime);
1393         unref(c);
1394         return r;
1395 }
1396
1397 static int
1398 readmeta(Hash *theirs, int ntheirs, Hash *ours, int nours, Meta ***m)
1399 {
1400         Object **obj;
1401         Objset has;
1402         int i, nobj;
1403         Metavec v;
1404
1405         *m = nil;
1406         osinit(&has);
1407         v.nmeta = 0;
1408         v.metasz = 64;
1409         v.meta = eamalloc(v.metasz, sizeof(Meta*));
1410         if(findtwixt(theirs, ntheirs, ours, nours, &obj, &nobj) == -1)
1411                 sysfatal("load twixt: %r");
1412
1413         if(nobj == 0)
1414                 return 0;
1415         for(i = 0; i < nours; i++)
1416                 if(!hasheq(&ours[i], &Zhash))
1417                         if(loadcommit(nil, &has, ours[i]) == -1)
1418                                 goto out;
1419         for(i = 0; i < nobj; i++)
1420                 if(loadcommit(&v, &has, obj[i]->hash) == -1)
1421                         goto out;
1422         osclear(&has);
1423         *m = v.meta;
1424         return v.nmeta;
1425 out:
1426         osclear(&has);
1427         free(v.meta);
1428         return -1;
1429 }
1430
1431 static int
1432 deltasz(Delta *d, int nd)
1433 {
1434         int i, sz;
1435         sz = 32;
1436         for(i = 0; i < nd; i++)
1437                 sz += d[i].cpy ? 7 : d[i].len + 1;
1438         return sz;
1439 }
1440
1441 static void
1442 pickdeltas(Meta **meta, int nmeta)
1443 {
1444         Meta *m, *p;
1445         Object *o;
1446         Delta *d;
1447         int i, j, nd, sz, pct, best;
1448
1449         pct = 0;
1450         dprint(1, "picking deltas\n");
1451         fprint(2, "deltifying %d objects:   0%%", nmeta);
1452         qsort(meta, nmeta, sizeof(Meta*), deltaordercmp);
1453         for(i = 0; i < nmeta; i++){
1454                 m = meta[i];
1455                 pct = showprogress((i*100) / nmeta, pct);
1456                 m->delta = nil;
1457                 m->ndelta = 0;
1458                 if(m->obj->type == GCommit || m->obj->type == GTag)
1459                         continue;
1460                 if((o = readobject(m->obj->hash)) == nil)
1461                         sysfatal("readobject %H: %r", m->obj->hash);
1462                 dtinit(&m->dtab, o);
1463                 if(i >= 11)
1464                         dtclear(&meta[i-11]->dtab);
1465                 best = o->size;
1466                 for(j = max(0, i - 10); j < i; j++){
1467                         p = meta[j];
1468                         /* long chains make unpacking slow */
1469                         if(p->nchain >= 128 || p->obj->type != o->type)
1470                                 continue;
1471                         d = deltify(o, &p->dtab, &nd);
1472                         sz = deltasz(d, nd);
1473                         if(sz + 32 < best){
1474                                 /*
1475                                  * if we already picked a best delta,
1476                                  * replace it.
1477                                  */
1478                                 free(m->delta);
1479                                 best = sz;
1480                                 m->delta = d;
1481                                 m->ndelta = nd;
1482                                 m->nchain = p->nchain + 1;
1483                                 m->prev = p;
1484                                 m->head = p->head;
1485                                 if(m->head == nil)
1486                                         m->head = p;
1487                         }else
1488                                 free(d);
1489                 }
1490                 unref(o);
1491         }
1492         for(i = max(0, nmeta - 10); i < nmeta; i++)
1493                 dtclear(&meta[i]->dtab);
1494         fprint(2, "\b\b\b\b100%%\n");
1495 }
1496
1497 static int
1498 compread(void *p, void *dst, int n)
1499 {
1500         Buf *b;
1501
1502         b = p;
1503         if(n > b->sz - b->off)
1504                 n = b->sz - b->off;
1505         memcpy(dst, b->data + b->off, n);
1506         b->off += n;
1507         return n;
1508 }
1509
1510 static int
1511 compwrite(void *p, void *buf, int n)
1512 {
1513         return hwrite(((Compout *)p)->bfd, buf, n, &((Compout*)p)->st);
1514 }
1515
1516 static int
1517 hcompress(Biobuf *bfd, void *buf, int sz, DigestState **st)
1518 {
1519         int r;
1520         Buf b ={
1521                 .off=0,
1522                 .data=buf,
1523                 .sz=sz,
1524         };
1525         Compout o = {
1526                 .bfd = bfd,
1527                 .st = *st,
1528         };
1529
1530         r = deflatezlib(&o, compwrite, &b, compread, 6, 0);
1531         *st = o.st;
1532         return r;
1533 }
1534
1535 static void
1536 append(char **p, int *len, int *sz, void *seg, int nseg)
1537 {
1538         if(*len + nseg >= *sz){
1539                 while(*len + nseg >= *sz)
1540                         *sz += *sz/2;
1541                 *p = erealloc(*p, *sz);
1542         }
1543         memcpy(*p + *len, seg, nseg);
1544         *len += nseg;
1545 }
1546
1547 static int
1548 encodedelta(Meta *m, Object *o, Object *b, void **pp)
1549 {
1550         char *p, *bp, buf[16];
1551         int len, sz, n, i, j;
1552         Delta *d;
1553
1554         sz = 128;
1555         len = 0;
1556         p = emalloc(sz);
1557
1558         /* base object size */
1559         buf[0] = b->size & 0x7f;
1560         n = b->size >> 7;
1561         for(i = 1; n > 0; i++){
1562                 buf[i - 1] |= 0x80;
1563                 buf[i] = n & 0x7f;
1564                 n >>= 7;
1565         }
1566         append(&p, &len, &sz, buf, i);
1567
1568         /* target object size */
1569         buf[0] = o->size & 0x7f;
1570         n = o->size >> 7;
1571         for(i = 1; n > 0; i++){
1572                 buf[i - 1] |= 0x80;
1573                 buf[i] = n & 0x7f;
1574                 n >>= 7;
1575         }
1576         append(&p, &len, &sz, buf, i);
1577         for(j = 0; j < m->ndelta; j++){
1578                 d = &m->delta[j];
1579                 if(d->cpy){
1580                         n = d->off;
1581                         bp = buf + 1;
1582                         buf[0] = 0x81;
1583                         buf[1] = 0x00;
1584                         for(i = 0; i < sizeof(buf); i++) {
1585                                 buf[0] |= 1<<i;
1586                                 *bp++ = n & 0xff;
1587                                 n >>= 8;
1588                                 if(n == 0)
1589                                         break;
1590                         }
1591
1592                         n = d->len;
1593                         if(n != 0x10000) {
1594                                 buf[0] |= 0x1<<4;
1595                                 for(i = 0; i < sizeof(buf)-4 && n > 0; i++){
1596                                         buf[0] |= 1<<(i + 4);
1597                                         *bp++ = n & 0xff;
1598                                         n >>= 8;
1599                                 }
1600                         }
1601                         append(&p, &len, &sz, buf, bp - buf);
1602                 }else{
1603                         n = 0;
1604                         while(n != d->len){
1605                                 buf[0] = (d->len - n < 127) ? d->len - n : 127;
1606                                 append(&p, &len, &sz, buf, 1);
1607                                 append(&p, &len, &sz, o->data + d->off + n, buf[0]);
1608                                 n += buf[0];
1609                         }
1610                 }
1611         }
1612         *pp = p;
1613         return len;
1614 }
1615
1616 static int
1617 packhdr(char *hdr, int ty, int len)
1618 {
1619         int i;
1620
1621         hdr[0] = ty << 4;
1622         hdr[0] |= len & 0xf;
1623         len >>= 4;
1624         for(i = 1; len != 0; i++){
1625                 hdr[i-1] |= 0x80;
1626                 hdr[i] = len & 0x7f;
1627                 len >>= 7;
1628         }
1629         return i;
1630 }
1631
1632 static int
1633 packoff(char *hdr, vlong off)
1634 {
1635         int i, j;
1636         char rbuf[8];
1637
1638         rbuf[0] = off & 0x7f;
1639         for(i = 1; (off >>= 7) != 0; i++)
1640                 rbuf[i] = (--off & 0x7f)|0x80;
1641
1642         j = 0;
1643         while(i > 0)
1644                 hdr[j++] = rbuf[--i];
1645         return j;
1646 }
1647
1648 static int
1649 genpack(int fd, Meta **meta, int nmeta, Hash *h, int odelta)
1650 {
1651         int i, nh, nd, res, pct, ret;
1652         DigestState *st;
1653         Biobuf *bfd;
1654         Meta *m;
1655         Object *o, *po, *b;
1656         char *p, buf[32];
1657
1658         st = nil;
1659         ret = -1;
1660         pct = 0;
1661         dprint(1, "generating pack\n");
1662         if((fd = dup(fd, -1)) == -1)
1663                 return -1;
1664         if((bfd = Bfdopen(fd, OWRITE)) == nil)
1665                 return -1;
1666         if(hwrite(bfd, "PACK", 4, &st) == -1)
1667                 return -1;
1668         PUTBE32(buf, 2);
1669         if(hwrite(bfd, buf, 4, &st) == -1)
1670                 return -1;
1671         PUTBE32(buf, nmeta);
1672         if(hwrite(bfd, buf, 4, &st) == -1)
1673                 return -1;
1674         qsort(meta, nmeta, sizeof(Meta*), writeordercmp);
1675         if(interactive)
1676                 fprint(2, "writing %d objects:   0%%", nmeta);
1677         for(i = 0; i < nmeta; i++){
1678                 pct = showprogress((i*100)/nmeta, pct);
1679                 m = meta[i];
1680                 if((m->off = Boffset(bfd)) == -1)
1681                         goto error;
1682                 if((o = readobject(m->obj->hash)) == nil)
1683                         return -1;
1684                 if(m->delta == nil){
1685                         nh = packhdr(buf, o->type, o->size);
1686                         if(hwrite(bfd, buf, nh, &st) == -1)
1687                                 goto error;
1688                         if(hcompress(bfd, o->data, o->size, &st) == -1)
1689                                 goto error;
1690                 }else{
1691                         if((b = readobject(m->prev->obj->hash)) == nil)
1692                                 goto error;
1693                         nd = encodedelta(m, o, b, &p);
1694                         unref(b);
1695                         if(odelta && m->prev->off != 0){
1696                                 nh = 0;
1697                                 nh += packhdr(buf, GOdelta, nd);
1698                                 nh += packoff(buf+nh, m->off - m->prev->off);
1699                                 if(hwrite(bfd, buf, nh, &st) == -1)
1700                                         goto error;
1701                         }else{
1702                                 nh = packhdr(buf, GRdelta, nd);
1703                                 po = m->prev->obj;
1704                                 if(hwrite(bfd, buf, nh, &st) == -1)
1705                                         goto error;
1706                                 if(hwrite(bfd, po->hash.h, sizeof(po->hash.h), &st) == -1)
1707                                         goto error;
1708                         }
1709                         res = hcompress(bfd, p, nd, &st);
1710                         free(p);
1711                         if(res == -1)
1712                                 goto error;
1713                 }
1714                 unref(o);
1715         }
1716         if(interactive)
1717                 fprint(2, "\b\b\b\b100%%\n");
1718         sha1(nil, 0, h->h, st);
1719         if(Bwrite(bfd, h->h, sizeof(h->h)) == -1)
1720                 goto error;
1721         ret = 0;
1722 error:
1723         if(Bterm(bfd) == -1)
1724                 return -1;
1725         return ret;
1726 }
1727
1728 int
1729 writepack(int fd, Hash *theirs, int ntheirs, Hash *ours, int nours, Hash *h)
1730 {
1731         Meta **meta;
1732         int i, r, nmeta;
1733
1734         if((nmeta = readmeta(theirs, ntheirs, ours, nours, &meta)) == -1)
1735                 return -1;
1736         pickdeltas(meta, nmeta);
1737         r = genpack(fd, meta, nmeta, h, 0);
1738         for(i = 0; i < nmeta; i++)
1739                 freemeta(meta[i]);
1740         free(meta);
1741         return r;
1742 }