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