Add initial support for multi pack indexes

3 files changed, 331 insertions, 0 deletions

diff --git a/pack_midx.go b/pack_midx.go
new file mode 100644
index 00000000..f37badbf
--- /dev/null
+++ b/pack_midx.go
@@ -0,0 +1,308 @@
+package furgit
+
+import (
+	"os"
+	"path/filepath"
+	"strings"
+	"sync"
+	"syscall"
+)
+
+const (
+	midxMagic   = 0x4d494458 // MIDX
+	midxVersion = 1
+
+	midxOIDVersionSHA1   = 1
+	midxOIDVersionSHA256 = 2
+
+	chunkPNAM = 0x504e414d // PNAM
+	chunkOIDF = 0x4f494446 // OIDF
+	chunkOIDL = 0x4f49444c // OIDL
+	chunkOOFF = 0x4f4f4646 // OOFF
+	chunkLOFF = 0x4c4f4646 // LOFF
+)
+
+type multiPackIndex struct {
+	repo *Repository
+
+	loadOnce sync.Once
+	loadErr  error
+
+	numPacks   int
+	numObjects int
+	packNames  []string
+	fanout     []byte
+	oids       []byte
+	offsets    []byte
+	largeOffs  []byte
+	data       []byte
+
+	closeOnce sync.Once
+}
+
+func (midx *multiPackIndex) Close() error {
+	if midx == nil {
+		return nil
+	}
+	var closeErr error
+	midx.closeOnce.Do(func() {
+		if len(midx.data) > 0 {
+			if err := syscall.Munmap(midx.data); closeErr == nil {
+				closeErr = err
+			}
+			midx.data = nil
+			midx.fanout = nil
+			midx.oids = nil
+			midx.offsets = nil
+			midx.largeOffs = nil
+			midx.packNames = nil
+			midx.numObjects = 0
+			midx.numPacks = 0
+		}
+	})
+	return closeErr
+}
+
+func (midx *multiPackIndex) ensureLoaded() error {
+	midx.loadOnce.Do(func() {
+		midx.loadErr = midx.load()
+	})
+	return midx.loadErr
+}
+
+func (midx *multiPackIndex) load() error {
+	if midx.repo == nil {
+		return ErrInvalidObject
+	}
+	path := midx.repo.repoPath(filepath.Join("objects", "pack", "multi-pack-index"))
+	f, err := os.Open(path)
+	if err != nil {
+		return err
+	}
+	stat, err := f.Stat()
+	if err != nil {
+		_ = f.Close()
+		return err
+	}
+	if stat.Size() < 12 {
+		_ = f.Close()
+		return ErrInvalidObject
+	}
+	region, err := syscall.Mmap(
+		int(f.Fd()),
+		0,
+		int(stat.Size()),
+		syscall.PROT_READ,
+		syscall.MAP_PRIVATE,
+	)
+	if err != nil {
+		_ = f.Close()
+		return err
+	}
+	err = f.Close()
+	if err != nil {
+		_ = syscall.Munmap(region)
+		return err
+	}
+	err = midx.parse(region)
+	if err != nil {
+		_ = syscall.Munmap(region)
+		return err
+	}
+	midx.data = region
+	return nil
+}
+
+func (midx *multiPackIndex) parse(buf []byte) error {
+	if len(buf) < 12 {
+		return ErrInvalidObject
+	}
+
+	if readBE32(buf[0:4]) != midxMagic {
+		return ErrInvalidObject
+	}
+	if buf[4] != midxVersion {
+		return ErrInvalidObject
+	}
+	oidVersion := buf[5]
+	if oidVersion != midxOIDVersionSHA1 && oidVersion != midxOIDVersionSHA256 {
+		return ErrInvalidObject
+	}
+	numChunks := int(buf[6])
+	numBaseMIDX := int(buf[7])
+	if numBaseMIDX != 0 {
+		return ErrInvalidObject
+	}
+	numPacks := int(readBE32(buf[8:12]))
+
+	chunkTableStart := 12
+	chunkTableSize := (numChunks + 1) * 12
+	if len(buf) < chunkTableStart+chunkTableSize {
+		return ErrInvalidObject
+	}
+
+	chunks := make(map[uint32]int64)
+	for i := 0; i < numChunks; i++ {
+		chunkStart := chunkTableStart + i*12
+		chunkID := readBE32(buf[chunkStart : chunkStart+4])
+		chunkOffset := int64(readBE64(buf[chunkStart+4 : chunkStart+12]))
+		chunks[chunkID] = chunkOffset
+	}
+
+	pnamOffset, ok := chunks[chunkPNAM]
+	if !ok {
+		return ErrInvalidObject
+	}
+	if pnamOffset < 0 || pnamOffset >= int64(len(buf)) {
+		return ErrInvalidObject
+	}
+
+	nextOffset := int64(len(buf))
+	for _, offset := range chunks {
+		if offset > pnamOffset && offset < nextOffset {
+			nextOffset = offset
+		}
+	}
+
+	pnamData := buf[pnamOffset:nextOffset]
+	packNames := make([]string, 0, numPacks)
+	start := 0
+	for i := 0; i < numPacks; i++ {
+		end := start
+		for end < len(pnamData) && pnamData[end] != 0 {
+			end++
+		}
+		if end >= len(pnamData) {
+			return ErrInvalidObject
+		}
+		name := string(pnamData[start:end])
+		if strings.HasSuffix(name, ".idx") { // why...
+			name = name[:len(name)-4] + ".pack"
+		}
+		packNames = append(packNames, name)
+		start = end + 1
+	}
+
+	oidfOffset, ok := chunks[chunkOIDF]
+	if !ok {
+		return ErrInvalidObject
+	}
+	if oidfOffset < 0 || oidfOffset+256*4 > int64(len(buf)) {
+		return ErrInvalidObject
+	}
+	fanout := buf[oidfOffset : oidfOffset+256*4]
+	numObjects := int(readBE32(fanout[len(fanout)-4:]))
+
+	oidlOffset, ok := chunks[chunkOIDL]
+	if !ok {
+		return ErrInvalidObject
+	}
+	oidlSize := int64(numObjects) * int64(HashSize)
+	if oidlOffset < 0 || oidlOffset+oidlSize > int64(len(buf)) {
+		return ErrInvalidObject
+	}
+	oids := buf[oidlOffset : oidlOffset+oidlSize]
+
+	ooffOffset, ok := chunks[chunkOOFF]
+	if !ok {
+		return ErrInvalidObject
+	}
+	ooffSize := int64(numObjects) * 8
+	if ooffOffset < 0 || ooffOffset+ooffSize > int64(len(buf)) {
+		return ErrInvalidObject
+	}
+	offsets := buf[ooffOffset : ooffOffset+ooffSize]
+
+	var largeOffs []byte
+	if loffOffset, ok := chunks[chunkLOFF]; ok {
+		loffEnd := int64(len(buf))
+		for _, offset := range chunks {
+			if offset > loffOffset && offset < loffEnd {
+				loffEnd = offset
+			}
+		}
+		if loffOffset < 0 || loffOffset > int64(len(buf)) {
+			return ErrInvalidObject
+		}
+		largeOffs = buf[loffOffset:loffEnd]
+	}
+
+	midx.numPacks = numPacks
+	midx.numObjects = numObjects
+	midx.packNames = packNames
+	midx.fanout = fanout
+	midx.oids = oids
+	midx.offsets = offsets
+	midx.largeOffs = largeOffs
+	return nil
+}
+
+func (midx *multiPackIndex) lookup(id Hash) (packlocation, error) {
+	if len(midx.data) == 0 {
+		err := midx.ensureLoaded()
+		if err != nil {
+			return packlocation{}, err
+		}
+	}
+
+	first := int(id[0])
+	var lo int
+	if first > 0 {
+		lo = int(readBE32(midx.fanout[(first-1)*4 : first*4]))
+	}
+	hi := int(readBE32(midx.fanout[first*4 : (first+1)*4]))
+
+	idx, found := bsearchHash(midx.oids, HashSize, lo, hi, id)
+	if !found {
+		return packlocation{}, ErrNotFound
+	}
+
+	offsetEntry := midx.offsets[idx*8 : (idx+1)*8]
+	packIntID := readBE32(offsetEntry[0:4])
+	offset := readBE32(offsetEntry[4:8])
+
+	if int(packIntID) >= len(midx.packNames) {
+		return packlocation{}, ErrInvalidObject
+	}
+
+	var finalOffset uint64
+	if offset&0x80000000 != 0 {
+		if len(midx.largeOffs) == 0 {
+			return packlocation{}, ErrInvalidObject
+		}
+		largeIdx := int(offset & 0x7fffffff)
+		if largeIdx*8+8 > len(midx.largeOffs) {
+			return packlocation{}, ErrInvalidObject
+		}
+		finalOffset = readBE64(midx.largeOffs[largeIdx*8 : largeIdx*8+8])
+	} else {
+		finalOffset = uint64(offset)
+	}
+
+	packName := midx.packNames[packIntID]
+	packPath := filepath.Join("objects", "pack", packName)
+
+	return packlocation{
+		PackPath: packPath,
+		Offset:   finalOffset,
+	}, nil
+}
+
+func (repo *Repository) multiPackIndex() (*multiPackIndex, error) {
+	repo.midxOnce.Do(func() {
+		repo.midx, repo.midxErr = repo.loadMultiPackIndex()
+	})
+	return repo.midx, repo.midxErr
+}
+
+func (repo *Repository) loadMultiPackIndex() (*multiPackIndex, error) {
+	midx := &multiPackIndex{repo: repo}
+	err := midx.ensureLoaded()
+	if err != nil {
+		if os.IsNotExist(err) {
+			return nil, ErrNotFound
+		}
+		return nil, err
+	}
+	return midx, nil
+}
diff --git a/pack_pack.go b/pack_pack.go
index 285431d8..eed3a4af 100644
--- a/pack_pack.go
+++ b/pack_pack.go
@@ -33,6 +33,19 @@ func (repo *Repository) packRead(id Hash) (Object, error) {
 }
 
 func (repo *Repository) packIndexFind(id Hash) (packlocation, error) {
+	midx, err := repo.multiPackIndex()
+	if err == nil {
+		loc, err := midx.lookup(id)
+		if err == nil {
+			return loc, nil
+		}
+		if !errors.Is(err, ErrNotFound) {
+			return packlocation{}, err
+		}
+	} else if !errors.Is(err, ErrNotFound) {
+		return packlocation{}, err
+	}
+
 	idxs, err := repo.packIndexes()
 	if err != nil {
 		return packlocation{}, err
diff --git a/repo.go b/repo.go
index 6560c2b0..c0d056bc 100644
--- a/repo.go
+++ b/repo.go
@@ -14,6 +14,10 @@ type Repository struct {
 	packIdx     []*packIndex
 	packIdxErr  error
 
+	midxOnce sync.Once
+	midx     *multiPackIndex
+	midxErr  error
+
 	packFiles sync.Map // string, *packFile
 	closeOnce sync.Once
 }
@@ -51,6 +55,12 @@ func (r *Repository) Close() error {
 				}
 			}
 		}
+		if r.midx != nil {
+			err := r.midx.Close()
+			if err != nil && closeErr == nil {
+				closeErr = err
+			}
+		}
 	})
 	return closeErr
 }