1/**
2 * Git delta application (gitformat-pack §delta payload).
3 *
4 * A delta payload (after inflation) is:
5 *
6 * ```
7 * varint(base_size) varint(result_size) — plain 7-bit little-endian
8 * instructions...
9 * ```
10 *
11 * Instructions:
12 *
13 * - **Copy** (`1xxxxxxx`): bits 0–3 select which of 4 little-endian offset
14 * bytes follow; bits 4–6 which of 3 size bytes. Absent bytes are zero.
15 * **`size == 0` means `0x10000`** (the classic special case). Copies
16 * `size` bytes from `offset` in the base into the output.
17 * - **Insert** (`0xxxxxxx`, x ≠ 0): the low 7 bits are the count (1–127) of
18 * literal bytes that follow; append them.
19 * - `0x00` is reserved/invalid.
20 *
21 * Applying all instructions must produce exactly `result_size` bytes.
22 *
23 * Algorithm ported with attribution from isomorphic-git's `applyDelta`
24 * (MIT), cross-checked against ripgit's `apply_git_delta`.
25 */
26import * as Effect from "effect/Effect";
27import * as Schema from "effect/Schema";
28import { decodeSizeVarint, ObjectParseError } from "./ObjectCodec.ts";
29
30/**
31 * Error raised on malformed delta payloads: truncated headers/instructions,
32 * out-of-bounds copies, base size mismatch, or a result that does not match
33 * the declared `result_size`.
34 */
35export class DeltaFormatError extends Schema.TaggedError<DeltaFormatError>()(
36 "DeltaFormatError",
37 { reason: Schema.String },
38) {}
39
40/**
41 * The two size varints at the head of a delta payload, plus the offset of
42 * the first instruction byte.
43 */
44export interface DeltaHeader {
45 readonly baseSize: number;
46 readonly resultSize: number;
47 /** Offset of the first instruction byte. */
48 readonly offset: number;
49}
50
51/**
52 * Reads the `base_size`/`result_size` varint header of a delta payload.
53 * Throws {@link DeltaFormatError} on truncation (pure function; use
54 * {@link applyDelta} for the Effect-typed path).
55 */
56export const readDeltaHeader = (delta: Uint8Array): DeltaHeader => {
57 try {
58 const base = decodeSizeVarint(delta, 0);
59 const result = decodeSizeVarint(delta, base.next);
60 return {
61 baseSize: base.value,
62 resultSize: result.value,
63 offset: result.next,
64 };
65 } catch (error) {
66 throw error instanceof ObjectParseError
67 ? new DeltaFormatError({
68 reason: `truncated delta header: ${error.reason}`,
69 })
70 : error;
71 }
72};
73
74/**
75 * Applies a delta payload to its base, verifying the declared base size and
76 * that the output is exactly `result_size` bytes.
77 */
78export const applyDelta = (
79 base: Uint8Array,
80 delta: Uint8Array,
81): Effect.Effect<Uint8Array, DeltaFormatError> =>
82 Effect.suspend(() => {
83 let header: DeltaHeader;
84 try {
85 header = readDeltaHeader(delta);
86 } catch (error) {
87 return Effect.fail(
88 error instanceof DeltaFormatError
89 ? error
90 : new DeltaFormatError({ reason: String(error) }),
91 );
92 }
93 if (header.baseSize !== base.length) {
94 return Effect.fail(
95 new DeltaFormatError({
96 reason: `delta base size ${header.baseSize} != actual base ${base.length}`,
97 }),
98 );
99 }
100 const out = new Uint8Array(header.resultSize);
101 let outPos = 0;
102 let pos = header.offset;
103 while (pos < delta.length) {
104 const opcode = delta[pos]!;
105 pos += 1;
106 if (opcode === 0) {
107 return Effect.fail(
108 new DeltaFormatError({ reason: "reserved delta opcode 0x00" }),
109 );
110 }
111 if ((opcode & 0x80) !== 0) {
112 // copy instruction
113 let offset = 0;
114 let size = 0;
115 for (let bit = 0; bit < 4; bit++) {
116 if ((opcode & (1 << bit)) !== 0) {
117 if (pos >= delta.length) {
118 return Effect.fail(
119 new DeltaFormatError({ reason: "truncated copy offset" }),
120 );
121 }
122 offset += delta[pos]! * 2 ** (8 * bit);
123 pos += 1;
124 }
125 }
126 for (let bit = 0; bit < 3; bit++) {
127 if ((opcode & (1 << (4 + bit))) !== 0) {
128 if (pos >= delta.length) {
129 return Effect.fail(
130 new DeltaFormatError({ reason: "truncated copy size" }),
131 );
132 }
133 size += delta[pos]! * 2 ** (8 * bit);
134 pos += 1;
135 }
136 }
137 if (size === 0) size = 0x10000;
138 if (offset + size > base.length) {
139 return Effect.fail(
140 new DeltaFormatError({
141 reason: `copy out of bounds: ${offset}+${size} > base ${base.length}`,
142 }),
143 );
144 }
145 if (outPos + size > out.length) {
146 return Effect.fail(
147 new DeltaFormatError({
148 reason: `delta output overflows declared result size ${out.length}`,
149 }),
150 );
151 }
152 out.set(base.subarray(offset, offset + size), outPos);
153 outPos += size;
154 } else {
155 // insert instruction: opcode = literal byte count (1–127)
156 const size = opcode;
157 if (pos + size > delta.length) {
158 return Effect.fail(
159 new DeltaFormatError({ reason: "truncated insert data" }),
160 );
161 }
162 if (outPos + size > out.length) {
163 return Effect.fail(
164 new DeltaFormatError({
165 reason: `delta output overflows declared result size ${out.length}`,
166 }),
167 );
168 }
169 out.set(delta.subarray(pos, pos + size), outPos);
170 outPos += size;
171 pos += size;
172 }
173 }
174 if (outPos !== out.length) {
175 return Effect.fail(
176 new DeltaFormatError({
177 reason: `delta produced ${outPos} bytes, expected ${out.length}`,
178 }),
179 );
180 }
181 return Effect.succeed(out);
182 });