pack-objects.c

   1 #include <ctype.h>
   2 #include "cache.h"
   3 #include "object.h"
   4 #include "delta.h"
   5 #include "pack.h"
   6 #include "csum-file.h"
   7
   8 static const char pack_usage[] = "git-pack-objects [--window=N] [--depth=N] {--stdout | base-name} < object-list";
   9
  10 struct object_entry {
  11         unsigned char sha1[20];
  12         unsigned long size;
  13         unsigned long offset;
  14         unsigned int depth;
  15         unsigned int hash;
  16         enum object_type type;
  17         unsigned long delta_size;
  18         struct object_entry *delta;
  19 };
  20
  21 static struct object_entry **sorted_by_sha, **sorted_by_type;
  22 static struct object_entry *objects = NULL;
  23 static int nr_objects = 0, nr_alloc = 0;
  24 static const char *base_name;
  25 static unsigned char pack_file_sha1[20];
  26
  27 static void *delta_against(void *buf, unsigned long size, struct object_entry *entry)
  28 {
  29         unsigned long othersize, delta_size;
  30         char type[10];
  31         void *otherbuf = read_sha1_file(entry->delta->sha1, type, &othersize);
  32         void *delta_buf;
  33
  34         if (!otherbuf)
  35                 die("unable to read %s", sha1_to_hex(entry->delta->sha1));
  36         delta_buf = diff_delta(otherbuf, othersize,
  37                                buf, size, &delta_size, ~0UL);
  38         if (!delta_buf || delta_size != entry->delta_size)
  39                 die("delta size changed");
  40         free(buf);
  41         free(otherbuf);
  42         return delta_buf;
  43 }
  44
  45 /*
  46  * The per-object header is a pretty dense thing, which is
  47  *  - first byte: low four bits are "size", then three bits of "type",
  48  *    and the high bit is "size continues".
  49  *  - each byte afterwards: low seven bits are size continuation,
  50  *    with the high bit being "size continues"
  51  */
  52 static int encode_header(enum object_type type, unsigned long size, unsigned char *hdr)
  53 {
  54         int n = 1, i;
  55         unsigned char c;
  56
  57         if (type < OBJ_COMMIT || type > OBJ_DELTA)
  58                 die("bad type %d", type);
  59
  60         /*
  61          * Shift the size up by 7 bits at a time,
  62          * until you get bits in the "high four".
  63          * That will be our beginning. We'll have
  64          * four size bits in 28..31, then groups
  65          * of seven in 21..27, 14..20, 7..13 and
  66          * finally 0..6.
  67          */
  68         if (size) {
  69                 n = 5;
  70                 while (!(size & 0xfe000000)) {
  71                         size <<= 7;
  72                         n--;
  73                 }
  74         }
  75         c = (type << 4) | (size >> 28);
  76         for (i = 1; i < n; i++) {
  77                 *hdr++ = c | 0x80;
  78                 c = (size >> 21) & 0x7f;
  79                 size <<= 7;
  80         }
  81         *hdr = c;
  82         return n;
  83 }
  84
  85 static unsigned long write_object(struct sha1file *f, struct object_entry *entry)
  86 {
  87         unsigned long size;
  88         char type[10];
  89         void *buf = read_sha1_file(entry->sha1, type, &size);
  90         unsigned char header[10];
  91         unsigned hdrlen, datalen;
  92         enum object_type obj_type;
  93
  94         if (!buf)
  95                 die("unable to read %s", sha1_to_hex(entry->sha1));
  96         if (size != entry->size)
  97                 die("object %s size inconsistency (%lu vs %lu)", sha1_to_hex(entry->sha1), size, entry->size);
  98
  99         /*
 100          * The object header is a byte of 'type' followed by zero or
 101          * more bytes of length.  For deltas, the 20 bytes of delta sha1
 102          * follows that.
 103          */
 104         obj_type = entry->type;
 105         if (entry->delta) {
 106                 buf = delta_against(buf, size, entry);
 107                 size = entry->delta_size;
 108                 obj_type = OBJ_DELTA;
 109         }
 110         hdrlen = encode_header(obj_type, size, header);
 111         sha1write(f, header, hdrlen);
 112         if (entry->delta) {
 113                 sha1write(f, entry->delta, 20);
 114                 hdrlen += 20;
 115         }
 116         datalen = sha1write_compressed(f, buf, size);
 117         free(buf);
 118         return hdrlen + datalen;
 119 }
 120
 121 static void write_pack_file(void)
 122 {
 123         int i;
 124         struct sha1file *f;
 125         unsigned long offset;
 126         unsigned long mb;
 127         struct pack_header hdr;
 128
 129         if (!base_name)
 130                 f = sha1fd(1, "<stdout>");
 131         else
 132                 f = sha1create("%s.%s", base_name, "pack");
 133         hdr.hdr_signature = htonl(PACK_SIGNATURE);
 134         hdr.hdr_version = htonl(1);
 135         hdr.hdr_entries = htonl(nr_objects);
 136         sha1write(f, &hdr, sizeof(hdr));
 137         offset = sizeof(hdr);
 138         for (i = 0; i < nr_objects; i++) {
 139                 struct object_entry *entry = objects + i;
 140                 entry->offset = offset;
 141                 offset += write_object(f, entry);
 142         }
 143         sha1close(f, pack_file_sha1, 1);
 144         mb = offset >> 20;
 145         offset &= 0xfffff;
 146 }
 147
 148 static void write_index_file(void)
 149 {
 150         int i;
 151         struct sha1file *f = sha1create("%s.%s", base_name, "idx");
 152         struct object_entry **list = sorted_by_sha;
 153         struct object_entry **last = list + nr_objects;
 154         unsigned int array[256];
 155
 156         /*
 157          * Write the first-level table (the list is sorted,
 158          * but we use a 256-entry lookup to be able to avoid
 159          * having to do eight extra binary search iterations).
 160          */
 161         for (i = 0; i < 256; i++) {
 162                 struct object_entry **next = list;
 163                 while (next < last) {
 164                         struct object_entry *entry = *next;
 165                         if (entry->sha1[0] != i)
 166                                 break;
 167                         next++;
 168                 }
 169                 array[i] = htonl(next - sorted_by_sha);
 170                 list = next;
 171         }
 172         sha1write(f, array, 256 * sizeof(int));
 173
 174         /*
 175          * Write the actual SHA1 entries..
 176          */
 177         list = sorted_by_sha;
 178         for (i = 0; i < nr_objects; i++) {
 179                 struct object_entry *entry = *list++;
 180                 unsigned int offset = htonl(entry->offset);
 181                 sha1write(f, &offset, 4);
 182                 sha1write(f, entry->sha1, 20);
 183         }
 184         sha1write(f, pack_file_sha1, 20);
 185         sha1close(f, NULL, 1);
 186 }
 187
 188 static void add_object_entry(unsigned char *sha1, unsigned int hash)
 189 {
 190         unsigned int idx = nr_objects;
 191         struct object_entry *entry;
 192
 193         if (idx >= nr_alloc) {
 194                 unsigned int needed = (idx + 1024) * 3 / 2;
 195                 objects = xrealloc(objects, needed * sizeof(*entry));
 196                 nr_alloc = needed;
 197         }
 198         entry = objects + idx;
 199         memset(entry, 0, sizeof(*entry));
 200         memcpy(entry->sha1, sha1, 20);
 201         entry->hash = hash;
 202         nr_objects = idx+1;
 203 }
 204
 205 static void check_object(struct object_entry *entry)
 206 {
 207         char type[20];
 208
 209         if (!sha1_object_info(entry->sha1, type, &entry->size)) {
 210                 if (!strcmp(type, "commit")) {
 211                         entry->type = OBJ_COMMIT;
 212                 } else if (!strcmp(type, "tree")) {
 213                         entry->type = OBJ_TREE;
 214                 } else if (!strcmp(type, "blob")) {
 215                         entry->type = OBJ_BLOB;
 216                 } else if (!strcmp(type, "tag")) {
 217                         entry->type = OBJ_TAG;
 218                 } else
 219                         die("unable to pack object %s of type %s",
 220                             sha1_to_hex(entry->sha1), type);
 221         }
 222         else
 223                 die("unable to get type of object %s",
 224                     sha1_to_hex(entry->sha1));
 225 }
 226
 227 static void get_object_details(void)
 228 {
 229         int i;
 230         struct object_entry *entry = objects;
 231
 232         for (i = 0; i < nr_objects; i++)
 233                 check_object(entry++);
 234 }
 235
 236 typedef int (*entry_sort_t)(const struct object_entry *, const struct object_entry *);
 237
 238 static entry_sort_t current_sort;
 239
 240 static int sort_comparator(const void *_a, const void *_b)
 241 {
 242         struct object_entry *a = *(struct object_entry **)_a;
 243         struct object_entry *b = *(struct object_entry **)_b;
 244         return current_sort(a,b);
 245 }
 246
 247 static struct object_entry **create_sorted_list(entry_sort_t sort)
 248 {
 249         struct object_entry **list = xmalloc(nr_objects * sizeof(struct object_entry *));
 250         int i;
 251
 252         for (i = 0; i < nr_objects; i++)
 253                 list[i] = objects + i;
 254         current_sort = sort;
 255         qsort(list, nr_objects, sizeof(struct object_entry *), sort_comparator);
 256         return list;
 257 }
 258
 259 static int sha1_sort(const struct object_entry *a, const struct object_entry *b)
 260 {
 261         return memcmp(a->sha1, b->sha1, 20);
 262 }
 263
 264 static int type_size_sort(const struct object_entry *a, const struct object_entry *b)
 265 {
 266         if (a->type < b->type)
 267                 return -1;
 268         if (a->type > b->type)
 269                 return 1;
 270         if (a->hash < b->hash)
 271                 return -1;
 272         if (a->hash > b->hash)
 273                 return 1;
 274         if (a->size < b->size)
 275                 return -1;
 276         if (a->size > b->size)
 277                 return 1;
 278         return a < b ? -1 : (a > b);
 279 }
 280
 281 struct unpacked {
 282         struct object_entry *entry;
 283         void *data;
 284 };
 285
 286 /*
 287  * We search for deltas _backwards_ in a list sorted by type and
 288  * by size, so that we see progressively smaller and smaller files.
 289  * That's because we prefer deltas to be from the bigger file
 290  * to the smaller - deletes are potentially cheaper, but perhaps
 291  * more importantly, the bigger file is likely the more recent
 292  * one.
 293  */
 294 static int try_delta(struct unpacked *cur, struct unpacked *old, unsigned max_depth)
 295 {
 296         struct object_entry *cur_entry = cur->entry;
 297         struct object_entry *old_entry = old->entry;
 298         unsigned long size, oldsize, delta_size, sizediff;
 299         long max_size;
 300         void *delta_buf;
 301
 302         /* Don't bother doing diffs between different types */
 303         if (cur_entry->type != old_entry->type)
 304                 return -1;
 305
 306         size = cur_entry->size;
 307         if (size < 50)
 308                 return -1;
 309         oldsize = old_entry->size;
 310         sizediff = oldsize > size ? oldsize - size : size - oldsize;
 311         if (sizediff > size / 8)
 312                 return -1;
 313         if (old_entry->depth >= max_depth)
 314                 return 0;
 315
 316         /*
 317          * NOTE!
 318          *
 319          * We always delta from the bigger to the smaller, since that's
 320          * more space-efficient (deletes don't have to say _what_ they
 321          * delete).
 322          */
 323         max_size = size / 2 - 20;
 324         if (cur_entry->delta)
 325                 max_size = cur_entry->delta_size-1;
 326         if (sizediff >= max_size)
 327                 return -1;
 328         delta_buf = diff_delta(old->data, oldsize,
 329                                cur->data, size, &delta_size, max_size);
 330         if (!delta_buf)
 331                 return 0;
 332         cur_entry->delta = old_entry;
 333         cur_entry->delta_size = delta_size;
 334         cur_entry->depth = old_entry->depth + 1;
 335         free(delta_buf);
 336         return 0;
 337 }
 338
 339 static void find_deltas(struct object_entry **list, int window, int depth)
 340 {
 341         int i, idx;
 342         unsigned int array_size = window * sizeof(struct unpacked);
 343         struct unpacked *array = xmalloc(array_size);
 344
 345         memset(array, 0, array_size);
 346         i = nr_objects;
 347         idx = 0;
 348         while (--i >= 0) {
 349                 struct object_entry *entry = list[i];
 350                 struct unpacked *n = array + idx;
 351                 unsigned long size;
 352                 char type[10];
 353                 int j;
 354
 355                 free(n->data);
 356                 n->entry = entry;
 357                 n->data = read_sha1_file(entry->sha1, type, &size);
 358                 if (size != entry->size)
 359                         die("object %s inconsistent object length (%lu vs %lu)", sha1_to_hex(entry->sha1), size, entry->size);
 360                 j = window;
 361                 while (--j > 0) {
 362                         unsigned int other_idx = idx + j;
 363                         struct unpacked *m;
 364                         if (other_idx >= window)
 365                                 other_idx -= window;
 366                         m = array + other_idx;
 367                         if (!m->entry)
 368                                 break;
 369                         if (try_delta(n, m, depth) < 0)
 370                                 break;
 371                 }
 372                 idx++;
 373                 if (idx >= window)
 374                         idx = 0;
 375         }
 376 }
 377
 378 int main(int argc, char **argv)
 379 {
 380         char line[PATH_MAX + 20];
 381         int window = 10, depth = 10, pack_to_stdout = 0;
 382         int i;
 383
 384         for (i = 1; i < argc; i++) {
 385                 const char *arg = argv[i];
 386
 387                 if (*arg == '-') {
 388                         if (!strncmp("--window=", arg, 9)) {
 389                                 char *end;
 390                                 window = strtoul(arg+9, &end, 0);
 391                                 if (!arg[9] || *end)
 392                                         usage(pack_usage);
 393                                 continue;
 394                         }
 395                         if (!strncmp("--depth=", arg, 8)) {
 396                                 char *end;
 397                                 depth = strtoul(arg+8, &end, 0);
 398                                 if (!arg[8] || *end)
 399                                         usage(pack_usage);
 400                                 continue;
 401                         }
 402                         if (!strcmp("--stdout", arg)) {
 403                                 pack_to_stdout = 1;
 404                                 continue;
 405                         }
 406                         usage(pack_usage);
 407                 }
 408                 if (base_name)
 409                         usage(pack_usage);
 410                 base_name = arg;
 411         }
 412
 413         if (pack_to_stdout != !base_name)
 414                 usage(pack_usage);
 415
 416         while (fgets(line, sizeof(line), stdin) != NULL) {
 417                 unsigned int hash;
 418                 char *p;
 419                 unsigned char sha1[20];
 420
 421                 if (get_sha1_hex(line, sha1))
 422                         die("expected sha1, got garbage");
 423                 hash = 0;
 424                 p = line+40;
 425                 while (*p) {
 426                         unsigned char c = *p++;
 427                         if (isspace(c))
 428                                 continue;
 429                         hash = hash * 11 + c;
 430                 }
 431                 add_object_entry(sha1, hash);
 432         }
 433         get_object_details();
 434
 435         fprintf(stderr, "Packing %d objects\n", nr_objects);
 436
 437         sorted_by_sha = create_sorted_list(sha1_sort);
 438         sorted_by_type = create_sorted_list(type_size_sort);
 439         if (window && depth)
 440                 find_deltas(sorted_by_type, window+1, depth);
 441
 442         write_pack_file();
 443         if (!pack_to_stdout)
 444                 write_index_file();
 445         return 0;
 446 }