*: format/pack -> packfile; format/delta -> delta; delete format

3 files changed, 209 insertions, 0 deletions

diff --git a/delta/apply/apply.go b/delta/apply/apply.go
new file mode 100644
index 00000000..f5006e3c
--- /dev/null
+++ b/delta/apply/apply.go
@@ -0,0 +1,160 @@
+// Package apply applies Git delta instruction streams.
+package apply
+
+import "fmt"
+
+// Apply applies one Git delta instruction stream to base.
+func Apply(base, delta []byte) ([]byte, error) {
+	pos := 0
+
+	srcSize, err := readVarint(delta, &pos)
+	if err != nil {
+		return nil, err
+	}
+
+	dstSize, err := readVarint(delta, &pos)
+	if err != nil {
+		return nil, err
+	}
+
+	if srcSize != len(base) {
+		return nil, fmt.Errorf("delta/apply: delta source size mismatch: got %d want %d", srcSize, len(base))
+	}
+
+	out := make([]byte, dstSize)
+	outPos := 0
+
+	for pos < len(delta) {
+		op := delta[pos]
+		pos++
+
+		//nolint:nestif
+		if op&0x80 != 0 {
+			off := 0
+
+			if op&0x01 != 0 {
+				if pos >= len(delta) {
+					return nil, fmt.Errorf("delta/apply: malformed delta copy offset")
+				}
+
+				off |= int(delta[pos])
+				pos++
+			}
+
+			if op&0x02 != 0 {
+				if pos >= len(delta) {
+					return nil, fmt.Errorf("delta/apply: malformed delta copy offset")
+				}
+
+				off |= int(delta[pos]) << 8
+				pos++
+			}
+
+			if op&0x04 != 0 {
+				if pos >= len(delta) {
+					return nil, fmt.Errorf("delta/apply: malformed delta copy offset")
+				}
+
+				off |= int(delta[pos]) << 16
+				pos++
+			}
+
+			if op&0x08 != 0 {
+				if pos >= len(delta) {
+					return nil, fmt.Errorf("delta/apply: malformed delta copy offset")
+				}
+
+				off |= int(delta[pos]) << 24
+				pos++
+			}
+
+			n := 0
+
+			if op&0x10 != 0 {
+				if pos >= len(delta) {
+					return nil, fmt.Errorf("delta/apply: malformed delta copy size")
+				}
+
+				n |= int(delta[pos])
+				pos++
+			}
+
+			if op&0x20 != 0 {
+				if pos >= len(delta) {
+					return nil, fmt.Errorf("delta/apply: malformed delta copy size")
+				}
+
+				n |= int(delta[pos]) << 8
+				pos++
+			}
+
+			if op&0x40 != 0 {
+				if pos >= len(delta) {
+					return nil, fmt.Errorf("delta/apply: malformed delta copy size")
+				}
+
+				n |= int(delta[pos]) << 16
+				pos++
+			}
+
+			if n == 0 {
+				n = 0x10000
+			}
+
+			if off < 0 || n < 0 || off+n > len(base) || outPos+n > len(out) {
+				return nil, fmt.Errorf("delta/apply: delta copy out of bounds")
+			}
+
+			copy(out[outPos:outPos+n], base[off:off+n])
+			outPos += n
+
+			continue
+		}
+
+		if op == 0 {
+			return nil, fmt.Errorf("delta/apply: invalid delta opcode 0")
+		}
+
+		n := int(op)
+		if pos+n > len(delta) || outPos+n > len(out) {
+			return nil, fmt.Errorf("delta/apply: delta insert out of bounds")
+		}
+
+		copy(out[outPos:outPos+n], delta[pos:pos+n])
+		outPos += n
+		pos += n
+	}
+
+	if outPos != len(out) {
+		return nil, fmt.Errorf("delta/apply: delta output size mismatch: got %d want %d", outPos, len(out))
+	}
+
+	return out, nil
+}
+
+// readVarint parses one Git delta varint and advances pos.
+func readVarint(buf []byte, pos *int) (int, error) {
+	value := 0
+	shift := uint(0)
+
+	for {
+		if *pos >= len(buf) {
+			return 0, fmt.Errorf("delta/apply: malformed delta varint")
+		}
+
+		b := buf[*pos]
+		*pos++
+
+		value |= int(b&0x7f) << shift
+		if b&0x80 == 0 {
+			break
+		}
+
+		shift += 7
+		if shift > 63 {
+			return 0, fmt.Errorf("delta/apply: delta varint overflow")
+		}
+	}
+
+	return value, nil
+}
diff --git a/delta/apply/header.go b/delta/apply/header.go
new file mode 100644
index 00000000..69c9659a
--- /dev/null
+++ b/delta/apply/header.go
@@ -0,0 +1,47 @@
+package apply
+
+import (
+	"fmt"
+	"io"
+)
+
+// ReadHeaderSizes reads the first two varints in one inflated delta stream.
+//
+// Callers that continue reading the same stream should pass their own buffered
+// byte reader and keep using that same reader afterwards.
+func ReadHeaderSizes(reader io.ByteReader) (int, int, error) {
+	srcSize, err := readVarintFromByteReader(reader)
+	if err != nil {
+		return 0, 0, err
+	}
+
+	dstSize, err := readVarintFromByteReader(reader)
+	if err != nil {
+		return 0, 0, err
+	}
+
+	return srcSize, dstSize, nil
+}
+
+// readVarintFromByteReader parses one Git delta varint from reader.
+func readVarintFromByteReader(reader io.ByteReader) (int, error) {
+	value := 0
+	shift := uint(0)
+
+	for {
+		b, err := reader.ReadByte()
+		if err != nil {
+			return 0, fmt.Errorf("delta/apply: malformed delta varint: %w", err)
+		}
+
+		value |= int(b&0x7f) << shift
+		if b&0x80 == 0 {
+			return value, nil
+		}
+
+		shift += 7
+		if shift > 63 {
+			return 0, fmt.Errorf("delta/apply: delta varint overflow")
+		}
+	}
+}
diff --git a/delta/doc.go b/delta/doc.go
new file mode 100644
index 00000000..f63c96a8
--- /dev/null
+++ b/delta/doc.go
@@ -0,0 +1,2 @@
+// Package delta provides various routines to handle Git delta compression.
+package delta