lib/git/raw/internal/pack.rb

   1 #
   2 # converted from the gitrb project
   3 #
   4 # authors:
   5 #    Matthias Lederhofer <matled@gmx.net>
   6 #    Simon 'corecode' Schubert <corecode@fs.ei.tum.de>
   7 #
   8 # provides native ruby access to git objects and pack files
   9 #
  10
  11 require 'zlib'
  12 require 'git/raw/internal/object'
  13 require 'git/raw/internal/mmap'
  14
  15 module Git
  16   module Raw
  17     module Internal
  18       class PackFormatError < StandardError
  19       end
  20
  21       class PackStorage
  22         OBJ_OFS_DELTA = 6
  23         OBJ_REF_DELTA = 7
  24
  25         FanOutCount = 256
  26         SHA1Size = 20
  27         IdxOffsetSize = 4
  28         OffsetSize = 4
  29         OffsetStart = FanOutCount * IdxOffsetSize
  30         SHA1Start = OffsetStart + OffsetSize
  31         EntrySize = OffsetSize + SHA1Size
  32
  33         def initialize(file)
  34           if file =~ /\.idx$/
  35             file = file[0...-3] + 'pack'
  36           end
  37
  38           @name = file
  39           @packfile = File.open(file)
  40           @idxfile = File.open(file[0...-4]+'idx')
  41           @idx = Mmap.new(@idxfile)
  42
  43           @offsets = [0]
  44           FanOutCount.times do |i|
  45             pos = @idx[i * IdxOffsetSize,IdxOffsetSize].unpack('N')[0]
  46             if pos < @offsets[i]
  47               raise PackFormatError, "pack #@name has discontinuous index #{i}"
  48             end
  49             @offsets << pos
  50           end
  51
  52           @size = @offsets[-1]
  53         end
  54
  55         def name
  56           @name
  57         end
  58
  59         def close
  60           @packfile.close
  61           @idx.unmap
  62           @idxfile.close
  63         end
  64
  65         def [](sha1)
  66           offset = find_object(sha1)
  67           return nil if !offset
  68           return parse_object(offset)
  69         end
  70
  71         def each_entry
  72           pos = OffsetStart
  73           @size.times do
  74             offset = @idx[pos,OffsetSize].unpack('N')[0]
  75             sha1 = @idx[pos+OffsetSize,SHA1Size]
  76             pos += EntrySize
  77             yield sha1, offset
  78           end
  79         end
  80
  81         def each_sha1
  82           # unpacking the offset is quite expensive, so
  83           # we avoid using #each
  84           pos = SHA1Start
  85           @size.times do
  86             sha1 = @idx[pos,SHA1Size]
  87             pos += EntrySize
  88             yield sha1
  89           end
  90         end
  91
  92         def find_object(sha1)
  93           slot = sha1[0]
  94           first, last = @offsets[slot,2]
  95           while first < last
  96             mid = (first + last) / 2
  97             midsha1 = @idx[SHA1Start + mid * EntrySize,SHA1Size]
  98             cmp = midsha1 <=> sha1
  99
 100             if cmp < 0
 101               first = mid + 1
 102             elsif cmp > 0
 103               last = mid
 104             else
 105               pos = OffsetStart + mid * EntrySize
 106               offset = @idx[pos,OffsetSize].unpack('N')[0]
 107               return offset
 108             end
 109           end
 110
 111           nil
 112         end
 113         private :find_object
 114
 115         def parse_object(offset)
 116           data, type = unpack_object(offset)
 117           RawObject.new(OBJ_TYPES[type], data)
 118         end
 119         protected :parse_object
 120
 121         def unpack_object(offset)
 122           obj_offset = offset
 123           @packfile.seek(offset)
 124
 125           c = @packfile.read(1)[0]
 126           size = c & 0xf
 127           type = (c >> 4) & 7
 128           shift = 4
 129           offset += 1
 130           while c & 0x80 != 0
 131             c = @packfile.read(1)[0]
 132             size |= ((c & 0x7f) << shift)
 133             shift += 7
 134             offset += 1
 135           end
 136
 137           case type
 138           when OBJ_OFS_DELTA, OBJ_REF_DELTA
 139             data, type = unpack_deltified(type, offset, obj_offset, size)
 140           when OBJ_COMMIT, OBJ_TREE, OBJ_BLOB, OBJ_TAG
 141             data = unpack_compressed(offset, size)
 142           else
 143             raise PackFormatError, "invalid type #{type}"
 144           end
 145           [data, type]
 146         end
 147         private :unpack_object
 148
 149         def unpack_deltified(type, offset, obj_offset, size)
 150           @packfile.seek(offset)
 151           data = @packfile.read(SHA1Size)
 152
 153           if type == OBJ_OFS_DELTA
 154             i = 0
 155             c = data[i]
 156             base_offset = c & 0x7f
 157             while c & 0x80 != 0
 158               c = data[i += 1]
 159               base_offset += 1
 160               base_offset <<= 7
 161               base_offset |= c & 0x7f
 162             end
 163             base_offset = obj_offset - base_offset
 164             offset += i + 1
 165           else
 166             base_offset = find_object(data)
 167             offset += SHA1Size
 168           end
 169
 170           base, type = unpack_object(base_offset)
 171           delta = unpack_compressed(offset, size)
 172           [patch_delta(base, delta), type]
 173         end
 174         private :unpack_deltified
 175
 176         def unpack_compressed(offset, destsize)
 177           outdata = ""
 178           @packfile.seek(offset)
 179           zstr = Zlib::Inflate.new
 180           while outdata.size < destsize
 181             indata = @packfile.read(4096)
 182             if indata.size == 0
 183               raise PackFormatError, 'error reading pack data'
 184             end
 185             outdata += zstr.inflate(indata)
 186           end
 187           if outdata.size > destsize
 188             raise PackFormatError, 'error reading pack data'
 189           end
 190           zstr.close
 191           outdata
 192         end
 193         private :unpack_compressed
 194
 195         def patch_delta(base, delta)
 196           src_size, pos = patch_delta_header_size(delta, 0)
 197           if src_size != base.size
 198             raise PackFormatError, 'invalid delta data'
 199           end
 200
 201           dest_size, pos = patch_delta_header_size(delta, pos)
 202           dest = ""
 203           while pos < delta.size
 204             c = delta[pos]
 205             pos += 1
 206             if c & 0x80 != 0
 207               pos -= 1
 208               cp_off = cp_size = 0
 209               cp_off = delta[pos += 1] if c & 0x01 != 0
 210               cp_off |= delta[pos += 1] << 8 if c & 0x02 != 0
 211               cp_off |= delta[pos += 1] << 16 if c & 0x04 != 0
 212               cp_off |= delta[pos += 1] << 24 if c & 0x08 != 0
 213               cp_size = delta[pos += 1] if c & 0x10 != 0
 214               cp_size |= delta[pos += 1] << 8 if c & 0x20 != 0
 215               cp_size |= delta[pos += 1] << 16 if c & 0x40 != 0
 216               cp_size = 0x10000 if cp_size == 0
 217               pos += 1
 218               dest += base[cp_off,cp_size]
 219             elsif c != 0
 220               dest += delta[pos,c]
 221               pos += c
 222             else
 223               raise PackFormatError, 'invalid delta data'
 224             end
 225           end
 226           dest
 227         end
 228         private :patch_delta
 229
 230         def patch_delta_header_size(delta, pos)
 231           size = 0
 232           shift = 0
 233           begin
 234             c = delta[pos]
 235             if c == nil
 236               raise PackFormatError, 'invalid delta header'
 237             end
 238             pos += 1
 239             size |= (c & 0x7f) << shift
 240             shift += 7
 241           end while c & 0x80 != 0
 242           [size, pos]
 243         end
 244         private :patch_delta_header_size
 245       end
 246     end
 247   end
 248 end
 249
 250 if $0 == __FILE__
 251   ARGV.each do |path|
 252     storage = Git::Internal::PackStorage.new(path)
 253     storage.each_sha1 do |sha1|
 254       obj = storage[sha1]
 255       puts "%s %s" % [obj.sha1.unpack('H*'), obj.type]
 256     end
 257   end
 258 end