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