Andrew's git - gitweb.git/blob

3856c87c4e03a91ad0cea36e5a9d00676e80833a
   1#include "builtin.h"
   2#include "cache.h"
   3#include "object.h"
   4#include "blob.h"
   5#include "delta.h"
   6#include "pack.h"
   7#include "csum-file.h"
   8
   9struct object_entry
  10{
  11        struct object_entry *next;
  12        unsigned long offset;
  13        unsigned char sha1[20];
  14};
  15
  16struct object_entry_block
  17{
  18        struct object_entry_block *next_block;
  19        struct object_entry *next_free;
  20        struct object_entry *end;
  21        struct object_entry entries[0];
  22};
  23
  24static int max_depth = 10;
  25static unsigned long alloc_count;
  26static unsigned long object_count;
  27static unsigned long duplicate_count;
  28static unsigned long packoff;
  29static int packfd;
  30static int current_depth;
  31static void *lastdat;
  32static unsigned long lastdatlen;
  33static unsigned char lastsha1[20];
  34static unsigned char packsha1[20];
  35struct object_entry *object_table[1 << 16];
  36struct object_entry_block *blocks;
  37
  38static void alloc_objects(int cnt)
  39{
  40        struct object_entry_block *b;
  41
  42        b = xmalloc(sizeof(struct object_entry_block)
  43                + cnt * sizeof(struct object_entry));
  44        b->next_block = blocks;
  45        b->next_free = b->entries;
  46        b->end = b->entries + cnt;
  47        blocks = b;
  48        alloc_count += cnt;
  49}
  50
  51static struct object_entry* new_object(unsigned char *sha1)
  52{
  53        struct object_entry *e;
  54
  55        if (blocks->next_free == blocks->end)
  56                alloc_objects(1000);
  57
  58        e = blocks->next_free++;
  59        memcpy(e->sha1, sha1, sizeof(e->sha1));
  60        return e;
  61}
  62
  63static struct object_entry* insert_object(unsigned char *sha1)
  64{
  65        unsigned int h = sha1[0] << 8 | sha1[1];
  66        struct object_entry *e = object_table[h];
  67        struct object_entry *p = 0;
  68
  69        while (e) {
  70                if (!memcmp(sha1, e->sha1, sizeof(e->sha1)))
  71                        return e;
  72                p = e;
  73                e = e->next;
  74        }
  75
  76        e = new_object(sha1);
  77        e->next = 0;
  78        e->offset = 0;
  79        if (p)
  80                p->next = e;
  81        else
  82                object_table[h] = e;
  83        return e;
  84}
  85
  86static ssize_t yread(int fd, void *buffer, size_t length)
  87{
  88        ssize_t ret = 0;
  89        while (ret < length) {
  90                ssize_t size = xread(fd, (char *) buffer + ret, length - ret);
  91                if (size < 0) {
  92                        return size;
  93                }
  94                if (size == 0) {
  95                        return ret;
  96                }
  97                ret += size;
  98        }
  99        return ret;
 100}
 101
 102static ssize_t ywrite(int fd, void *buffer, size_t length)
 103{
 104        ssize_t ret = 0;
 105        while (ret < length) {
 106                ssize_t size = xwrite(fd, (char *) buffer + ret, length - ret);
 107                if (size < 0) {
 108                        return size;
 109                }
 110                if (size == 0) {
 111                        return ret;
 112                }
 113                ret += size;
 114        }
 115        return ret;
 116}
 117
 118static unsigned long encode_header(enum object_type type, unsigned long size, unsigned char *hdr)
 119{
 120        int n = 1;
 121        unsigned char c;
 122
 123        if (type < OBJ_COMMIT || type > OBJ_DELTA)
 124                die("bad type %d", type);
 125
 126        c = (type << 4) | (size & 15);
 127        size >>= 4;
 128        while (size) {
 129                *hdr++ = c | 0x80;
 130                c = size & 0x7f;
 131                size >>= 7;
 132                n++;
 133        }
 134        *hdr = c;
 135        return n;
 136}
 137
 138static void write_blob(void *dat, unsigned long datlen)
 139{
 140        z_stream s;
 141        void *out, *delta;
 142        unsigned char hdr[64];
 143        unsigned long hdrlen, deltalen;
 144
 145        if (lastdat && current_depth < max_depth) {
 146                delta = diff_delta(lastdat, lastdatlen,
 147                        dat, datlen,
 148                        &deltalen, 0);
 149        } else
 150                delta = 0;
 151
 152        memset(&s, 0, sizeof(s));
 153        deflateInit(&s, zlib_compression_level);
 154
 155        if (delta) {
 156                current_depth++;
 157                s.next_in = delta;
 158                s.avail_in = deltalen;
 159                hdrlen = encode_header(OBJ_DELTA, deltalen, hdr);
 160                if (ywrite(packfd, hdr, hdrlen) != hdrlen)
 161                        die("Can't write object header: %s", strerror(errno));
 162                if (ywrite(packfd, lastsha1, sizeof(lastsha1)) != sizeof(lastsha1))
 163                        die("Can't write object base: %s", strerror(errno));
 164                packoff += hdrlen + sizeof(lastsha1);
 165        } else {
 166                current_depth = 0;
 167                s.next_in = dat;
 168                s.avail_in = datlen;
 169                hdrlen = encode_header(OBJ_BLOB, datlen, hdr);
 170                if (ywrite(packfd, hdr, hdrlen) != hdrlen)
 171                        die("Can't write object header: %s", strerror(errno));
 172                packoff += hdrlen;
 173        }
 174
 175        s.avail_out = deflateBound(&s, s.avail_in);
 176        s.next_out = out = xmalloc(s.avail_out);
 177        while (deflate(&s, Z_FINISH) == Z_OK)
 178                /* nothing */;
 179        deflateEnd(&s);
 180
 181        if (ywrite(packfd, out, s.total_out) != s.total_out)
 182                die("Failed writing compressed data %s", strerror(errno));
 183        packoff += s.total_out;
 184
 185        free(out);
 186        if (delta)
 187                free(delta);
 188}
 189
 190static void init_pack_header()
 191{
 192        const char* magic = "PACK";
 193        unsigned long version = 2;
 194        unsigned long zero = 0;
 195
 196        version = htonl(version);
 197
 198        if (ywrite(packfd, (char*)magic, 4) != 4)
 199                die("Can't write pack magic: %s", strerror(errno));
 200        if (ywrite(packfd, &version, 4) != 4)
 201                die("Can't write pack version: %s", strerror(errno));
 202        if (ywrite(packfd, &zero, 4) != 4)
 203                die("Can't write 0 object count: %s", strerror(errno));
 204        packoff = 4 * 3;
 205}
 206
 207static void fixup_header_footer()
 208{
 209        SHA_CTX c;
 210        char hdr[8];
 211        unsigned long cnt;
 212        char *buf;
 213        size_t n;
 214
 215        if (lseek(packfd, 0, SEEK_SET) != 0)
 216                die("Failed seeking to start: %s", strerror(errno));
 217
 218        SHA1_Init(&c);
 219        if (yread(packfd, hdr, 8) != 8)
 220                die("Failed reading header: %s", strerror(errno));
 221        SHA1_Update(&c, hdr, 8);
 222
 223        cnt = htonl(object_count);
 224        SHA1_Update(&c, &cnt, 4);
 225        if (ywrite(packfd, &cnt, 4) != 4)
 226                die("Failed writing object count: %s", strerror(errno));
 227
 228        buf = xmalloc(128 * 1024);
 229        for (;;) {
 230                n = xread(packfd, buf, 128 * 1024);
 231                if (n <= 0)
 232                        break;
 233                SHA1_Update(&c, buf, n);
 234        }
 235        free(buf);
 236
 237        SHA1_Final(packsha1, &c);
 238        if (ywrite(packfd, packsha1, sizeof(packsha1)) != sizeof(packsha1))
 239                die("Failed writing pack checksum: %s", strerror(errno));
 240}
 241
 242static int oecmp (const void *_a, const void *_b)
 243{
 244        struct object_entry *a = *((struct object_entry**)_a);
 245        struct object_entry *b = *((struct object_entry**)_b);
 246        return memcmp(a->sha1, b->sha1, sizeof(a->sha1));
 247}
 248
 249static void write_index(const char *idx_name)
 250{
 251        struct sha1file *f;
 252        struct object_entry **idx, **c, **last;
 253        struct object_entry *e;
 254        struct object_entry_block *o;
 255        unsigned int array[256];
 256        int i;
 257
 258        /* Build the sorted table of object IDs. */
 259        idx = xmalloc(object_count * sizeof(struct object_entry*));
 260        c = idx;
 261        for (o = blocks; o; o = o->next_block)
 262                for (e = o->entries; e != o->next_free; e++)
 263                        *c++ = e;
 264        last = idx + object_count;
 265        qsort(idx, object_count, sizeof(struct object_entry*), oecmp);
 266
 267        /* Generate the fan-out array. */
 268        c = idx;
 269        for (i = 0; i < 256; i++) {
 270                struct object_entry **next = c;;
 271                while (next < last) {
 272                        if ((*next)->sha1[0] != i)
 273                                break;
 274                        next++;
 275                }
 276                array[i] = htonl(next - idx);
 277                c = next;
 278        }
 279
 280        f = sha1create("%s", idx_name);
 281        sha1write(f, array, 256 * sizeof(int));
 282        for (c = idx; c != last; c++) {
 283                unsigned int offset = htonl((*c)->offset);
 284                sha1write(f, &offset, 4);
 285                sha1write(f, (*c)->sha1, sizeof((*c)->sha1));
 286        }
 287        sha1write(f, packsha1, sizeof(packsha1));
 288        sha1close(f, NULL, 1);
 289        free(idx);
 290}
 291
 292int main(int argc, const char **argv)
 293{
 294        const char *base_name = argv[1];
 295        int est_obj_cnt = atoi(argv[2]);
 296        char *pack_name;
 297        char *idx_name;
 298
 299        pack_name = xmalloc(strlen(base_name) + 6);
 300        sprintf(pack_name, "%s.pack", base_name);
 301        idx_name = xmalloc(strlen(base_name) + 5);
 302        sprintf(idx_name, "%s.idx", base_name);
 303
 304        packfd = open(pack_name, O_RDWR|O_CREAT|O_EXCL, 0666);
 305        if (packfd < 0)
 306                die("Can't create pack file %s: %s", pack_name, strerror(errno));
 307
 308        alloc_objects(est_obj_cnt);
 309        init_pack_header();
 310        for (;;) {
 311                unsigned long datlen;
 312                int hdrlen;
 313                void *dat;
 314                char hdr[128];
 315                unsigned char sha1[20];
 316                SHA_CTX c;
 317                struct object_entry *e;
 318
 319                if (yread(0, &datlen, 4) != 4)
 320
 321                        break;
 322
 323                dat = xmalloc(datlen);
 324                if (yread(0, dat, datlen) != datlen)
 325                        break;
 326
 327                hdrlen = sprintf(hdr, "blob %lu", datlen) + 1;
 328                SHA1_Init(&c);
 329                SHA1_Update(&c, hdr, hdrlen);
 330                SHA1_Update(&c, dat, datlen);
 331                SHA1_Final(sha1, &c);
 332
 333                e = insert_object(sha1);
 334                if (!e->offset) {
 335                        e->offset = packoff;
 336                        write_blob(dat, datlen);
 337                        object_count++;
 338
 339                        if (lastdat)
 340                                free(lastdat);
 341                        lastdat = dat;
 342                        lastdatlen = datlen;
 343                        memcpy(lastsha1, sha1, sizeof(sha1));
 344                } else {
 345                        duplicate_count++;
 346                        free(dat);
 347                }
 348        }
 349        fixup_header_footer();
 350        close(packfd);
 351        write_index(idx_name);
 352
 353        fprintf(stderr, "%lu objects, %lu duplicates, %lu allocated (%lu overflow)\n",
 354                object_count, duplicate_count, alloc_count, alloc_count - est_obj_cnt);
 355
 356        return 0;
 357}