lib/git/raw/internal/pack.rb

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