ref: 42ff39c8d340dabce79c4057a07a3932da295772
parent: 7b121523cf385c03366f42fca89692d3199d4190
author: Runxi Yu <me@runxiyu.org>
date: Sat Feb 21 13:44:45 EST 2026
format/delta/apply: Move core delta apply algorithm here
--- /dev/null
+++ b/format/delta/apply/apply.go
@@ -1,0 +1,127 @@
+// 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("format/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++
+ if op&0x80 != 0 {+ off := 0
+ if op&0x01 != 0 {+ if pos >= len(delta) {+ return nil, fmt.Errorf("format/delta/apply: malformed delta copy offset")+ }
+ off |= int(delta[pos])
+ pos++
+ }
+ if op&0x02 != 0 {+ if pos >= len(delta) {+ return nil, fmt.Errorf("format/delta/apply: malformed delta copy offset")+ }
+ off |= int(delta[pos]) << 8
+ pos++
+ }
+ if op&0x04 != 0 {+ if pos >= len(delta) {+ return nil, fmt.Errorf("format/delta/apply: malformed delta copy offset")+ }
+ off |= int(delta[pos]) << 16
+ pos++
+ }
+ if op&0x08 != 0 {+ if pos >= len(delta) {+ return nil, fmt.Errorf("format/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("format/delta/apply: malformed delta copy size")+ }
+ n |= int(delta[pos])
+ pos++
+ }
+ if op&0x20 != 0 {+ if pos >= len(delta) {+ return nil, fmt.Errorf("format/delta/apply: malformed delta copy size")+ }
+ n |= int(delta[pos]) << 8
+ pos++
+ }
+ if op&0x40 != 0 {+ if pos >= len(delta) {+ return nil, fmt.Errorf("format/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("format/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("format/delta/apply: invalid delta opcode 0")+ }
+ n := int(op)
+ if pos+n > len(delta) || outPos+n > len(out) {+ return nil, fmt.Errorf("format/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("format/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("format/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("format/delta/apply: delta varint overflow")+ }
+ }
+ return value, nil
+}
--- /dev/null
+++ b/format/delta/apply/header.go
@@ -1,0 +1,49 @@
+package apply
+
+import (
+ "fmt"
+ "io"
+)
+
+// ReadHeaderSizes reads the first two varints in one inflated delta stream.
+func ReadHeaderSizes(reader io.Reader) (int, int, error) {+ // Two Git varints are read here. Each can take up to 10 bytes.
+ var buf [20]byte
+ n := 0
+
+ for {+ if n >= len(buf) {+ return 0, 0, fmt.Errorf("format/delta/apply: malformed delta varint")+ }
+ if _, err := io.ReadFull(reader, buf[n:n+1]); err != nil {+ return 0, 0, fmt.Errorf("format/delta/apply: malformed delta varint: %w", err)+ }
+ n++
+ if buf[n-1]&0x80 == 0 {+ break
+ }
+ }
+ pos := 0
+ srcSize, err := readVarint(buf[:n], &pos)
+ if err != nil {+ return 0, 0, err
+ }
+
+ for {+ if n >= len(buf) {+ return 0, 0, fmt.Errorf("format/delta/apply: malformed delta varint")+ }
+ if _, err := io.ReadFull(reader, buf[n:n+1]); err != nil {+ return 0, 0, fmt.Errorf("format/delta/apply: malformed delta varint: %w", err)+ }
+ n++
+ if buf[n-1]&0x80 == 0 {+ break
+ }
+ }
+ dstSize, err := readVarint(buf[:n], &pos)
+ if err != nil {+ return 0, 0, err
+ }
+ return srcSize, dstSize, nil
+}
--- a/objectstore/packed/delta_apply.go
+++ b/objectstore/packed/delta_apply.go
@@ -3,6 +3,7 @@
import (
"fmt"
+ deltaapply "codeberg.org/lindenii/furgit/format/delta/apply"
"codeberg.org/lindenii/furgit/objecttype"
)
@@ -27,7 +28,7 @@
if err != nil {return objecttype.TypeInvalid, nil, err
}
- out, err = applyDelta(out, delta)
+ out, err = deltaapply.Apply(out, delta)
if err != nil {return objecttype.TypeInvalid, nil, err
}
@@ -40,127 +41,4 @@
)
}
return baseType, out, nil
-}
-
-// applyDelta applies one Git delta instruction stream to base.
-func applyDelta(base, delta []byte) ([]byte, error) {- pos := 0
- srcSize, err := readDeltaVarint(delta, &pos)
- if err != nil {- return nil, err
- }
- dstSize, err := readDeltaVarint(delta, &pos)
- if err != nil {- return nil, err
- }
- if srcSize != len(base) {- return nil, fmt.Errorf("objectstore/packed: 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++
- if op&0x80 != 0 {- off := 0
- if op&0x01 != 0 {- if pos >= len(delta) {- return nil, fmt.Errorf("objectstore/packed: malformed delta copy offset")- }
- off |= int(delta[pos])
- pos++
- }
- if op&0x02 != 0 {- if pos >= len(delta) {- return nil, fmt.Errorf("objectstore/packed: malformed delta copy offset")- }
- off |= int(delta[pos]) << 8
- pos++
- }
- if op&0x04 != 0 {- if pos >= len(delta) {- return nil, fmt.Errorf("objectstore/packed: malformed delta copy offset")- }
- off |= int(delta[pos]) << 16
- pos++
- }
- if op&0x08 != 0 {- if pos >= len(delta) {- return nil, fmt.Errorf("objectstore/packed: malformed delta copy offset")- }
- off |= int(delta[pos]) << 24
- pos++
- }
-
- n := 0
- if op&0x10 != 0 {- if pos >= len(delta) {- return nil, fmt.Errorf("objectstore/packed: malformed delta copy size")- }
- n |= int(delta[pos])
- pos++
- }
- if op&0x20 != 0 {- if pos >= len(delta) {- return nil, fmt.Errorf("objectstore/packed: malformed delta copy size")- }
- n |= int(delta[pos]) << 8
- pos++
- }
- if op&0x40 != 0 {- if pos >= len(delta) {- return nil, fmt.Errorf("objectstore/packed: 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("objectstore/packed: delta copy out of bounds")- }
- copy(out[outPos:outPos+n], base[off:off+n])
- outPos += n
- continue
- }
-
- if op == 0 {- return nil, fmt.Errorf("objectstore/packed: invalid delta opcode 0")- }
- n := int(op)
- if pos+n > len(delta) || outPos+n > len(out) {- return nil, fmt.Errorf("objectstore/packed: 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("objectstore/packed: delta output size mismatch: got %d want %d", outPos, len(out))- }
- return out, nil
-}
-
-// readDeltaVarint parses one Git delta varint and advances pos.
-func readDeltaVarint(buf []byte, pos *int) (int, error) {- value := 0
- shift := uint(0)
- for {- if *pos >= len(buf) {- return 0, fmt.Errorf("objectstore/packed: 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("objectstore/packed: delta varint overflow")- }
- }
- return value, nil
}
--- a/objectstore/packed/delta_plan.go
+++ b/objectstore/packed/delta_plan.go
@@ -2,8 +2,8 @@
import (
"fmt"
- "io"
+ deltaapply "codeberg.org/lindenii/furgit/format/delta/apply"
"codeberg.org/lindenii/furgit/objecttype"
)
@@ -102,52 +102,9 @@
}
defer func() { _ = reader.Close() }()- _, size, err := readDeltaHeaderSizes(reader)
+ _, size, err := deltaapply.ReadHeaderSizes(reader)
if err != nil {return 0, err
}
return int64(size), nil
-}
-
-// readDeltaHeaderSizes reads the first two varints in one inflated delta stream.
-func readDeltaHeaderSizes(reader io.Reader) (int, int, error) {- // Two Git varints are read here. Each can take up to 10 bytes.
- var buf [20]byte
- n := 0
-
- for {- if n >= len(buf) {- return 0, 0, fmt.Errorf("objectstore/packed: malformed delta varint")- }
- if _, err := io.ReadFull(reader, buf[n:n+1]); err != nil {- return 0, 0, fmt.Errorf("objectstore/packed: malformed delta varint: %w", err)- }
- n++
- if buf[n-1]&0x80 == 0 {- break
- }
- }
- pos := 0
- srcSize, err := readDeltaVarint(buf[:n], &pos)
- if err != nil {- return 0, 0, err
- }
-
- for {- if n >= len(buf) {- return 0, 0, fmt.Errorf("objectstore/packed: malformed delta varint")- }
- if _, err := io.ReadFull(reader, buf[n:n+1]); err != nil {- return 0, 0, fmt.Errorf("objectstore/packed: malformed delta varint: %w", err)- }
- n++
- if buf[n-1]&0x80 == 0 {- break
- }
- }
- dstSize, err := readDeltaVarint(buf[:n], &pos)
- if err != nil {- return 0, 0, err
- }
- return srcSize, dstSize, nil
}
--
⑨