From 42ff39c8d340dabce79c4057a07a3932da295772 Mon Sep 17 00:00:00 2001 From: Runxi Yu Date: Sat, 21 Feb 2026 18:44:45 +0800 Subject: format/delta/apply: Move core delta apply algorithm here --- format/delta/apply/apply.go | 127 ++++++++++++++++++++++++++++++++++++++ format/delta/apply/header.go | 49 +++++++++++++++ objectstore/packed/delta_apply.go | 126 +------------------------------------ objectstore/packed/delta_plan.go | 47 +------------- 4 files changed, 180 insertions(+), 169 deletions(-) create mode 100644 format/delta/apply/apply.go create mode 100644 format/delta/apply/header.go diff --git a/format/delta/apply/apply.go b/format/delta/apply/apply.go new file mode 100644 index 00000000..f9f2fbaf --- /dev/null +++ b/format/delta/apply/apply.go @@ -0,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 +} diff --git a/format/delta/apply/header.go b/format/delta/apply/header.go new file mode 100644 index 00000000..f6aadea3 --- /dev/null +++ b/format/delta/apply/header.go @@ -0,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 +} diff --git a/objectstore/packed/delta_apply.go b/objectstore/packed/delta_apply.go index 9d34c245..a067525d 100644 --- a/objectstore/packed/delta_apply.go +++ b/objectstore/packed/delta_apply.go @@ -3,6 +3,7 @@ package packed import ( "fmt" + deltaapply "codeberg.org/lindenii/furgit/format/delta/apply" "codeberg.org/lindenii/furgit/objecttype" ) @@ -27,7 +28,7 @@ func (store *Store) deltaResolveContent(start location) (objecttype.Type, []byte 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 } @@ -41,126 +42,3 @@ func (store *Store) deltaResolveContent(start location) (objecttype.Type, []byte } 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 -} diff --git a/objectstore/packed/delta_plan.go b/objectstore/packed/delta_plan.go index 2fca7c0e..58e0fc0c 100644 --- a/objectstore/packed/delta_plan.go +++ b/objectstore/packed/delta_plan.go @@ -2,8 +2,8 @@ package packed import ( "fmt" - "io" + deltaapply "codeberg.org/lindenii/furgit/format/delta/apply" "codeberg.org/lindenii/furgit/objecttype" ) @@ -102,52 +102,9 @@ func deltaDeclaredSizeAt(pack *packFile, dataOffset int) (int64, error) { } 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 -} -- cgit v1.3.1-10-gc9f91