113 lines · 3.3 KB
| 1 | /** |
| 2 | * Git delta encoding/decoding for pack files. |
| 3 | * |
| 4 | * Pack files use two delta types: |
| 5 | * - OFS_DELTA: base referenced by negative offset in pack |
| 6 | * - REF_DELTA: base referenced by SHA-1 |
| 7 | * |
| 8 | * Delta format: |
| 9 | * - Variable-length encoded source size |
| 10 | * - Variable-length encoded target size |
| 11 | * - Series of instructions: |
| 12 | * - Copy (bit 7 set): copy bytes from source |
| 13 | * - Insert (bit 7 clear): insert literal bytes |
| 14 | */ |
| 15 | |
| 16 | /** Apply a delta to a base object to produce the target object. */ |
| 17 | export function applyDelta(base: Uint8Array, delta: Uint8Array): Uint8Array { |
| 18 | let offset = 0; |
| 19 | |
| 20 | // Read source size (variable-length encoding) |
| 21 | const { value: sourceSize, bytesRead: srcBytes } = readDeltaSize(delta, offset); |
| 22 | offset += srcBytes; |
| 23 | |
| 24 | // Read target size |
| 25 | const { value: targetSize, bytesRead: tgtBytes } = readDeltaSize(delta, offset); |
| 26 | offset += tgtBytes; |
| 27 | |
| 28 | if (base.length !== sourceSize) { |
| 29 | throw new Error(`Delta source size mismatch: expected ${sourceSize}, got ${base.length}`); |
| 30 | } |
| 31 | |
| 32 | const target = new Uint8Array(targetSize); |
| 33 | let targetOffset = 0; |
| 34 | |
| 35 | while (offset < delta.length) { |
| 36 | const cmd = delta[offset++]; |
| 37 | |
| 38 | if (cmd === 0) { |
| 39 | // Reserved, invalid |
| 40 | throw new Error('Invalid delta: zero instruction byte'); |
| 41 | } |
| 42 | |
| 43 | if (cmd & 0x80) { |
| 44 | // Copy instruction: copy from source |
| 45 | let copyOffset = 0; |
| 46 | let copySize = 0; |
| 47 | |
| 48 | if (cmd & 0x01) copyOffset = delta[offset++]; |
| 49 | if (cmd & 0x02) copyOffset |= delta[offset++] << 8; |
| 50 | if (cmd & 0x04) copyOffset |= delta[offset++] << 16; |
| 51 | if (cmd & 0x08) copyOffset |= delta[offset++] << 24; |
| 52 | |
| 53 | if (cmd & 0x10) copySize = delta[offset++]; |
| 54 | if (cmd & 0x20) copySize |= delta[offset++] << 8; |
| 55 | if (cmd & 0x40) copySize |= delta[offset++] << 16; |
| 56 | |
| 57 | if (copySize === 0) copySize = 0x10000; |
| 58 | |
| 59 | target.set(base.slice(copyOffset, copyOffset + copySize), targetOffset); |
| 60 | targetOffset += copySize; |
| 61 | } else { |
| 62 | // Insert instruction: insert literal bytes |
| 63 | const insertSize = cmd; |
| 64 | target.set(delta.slice(offset, offset + insertSize), targetOffset); |
| 65 | offset += insertSize; |
| 66 | targetOffset += insertSize; |
| 67 | } |
| 68 | } |
| 69 | |
| 70 | if (targetOffset !== targetSize) { |
| 71 | throw new Error(`Delta target size mismatch: expected ${targetSize}, produced ${targetOffset}`); |
| 72 | } |
| 73 | |
| 74 | return target; |
| 75 | } |
| 76 | |
| 77 | /** Read a variable-length size from delta header. */ |
| 78 | function readDeltaSize(buf: Uint8Array, offset: number): { value: number; bytesRead: number } { |
| 79 | let value = 0; |
| 80 | let shift = 0; |
| 81 | let bytesRead = 0; |
| 82 | |
| 83 | // eslint-disable-next-line no-constant-condition |
| 84 | while (true) { |
| 85 | const byte = buf[offset + bytesRead]; |
| 86 | bytesRead++; |
| 87 | value |= (byte & 0x7f) << shift; |
| 88 | shift += 7; |
| 89 | if (!(byte & 0x80)) break; |
| 90 | } |
| 91 | |
| 92 | return { value, bytesRead }; |
| 93 | } |
| 94 | |
| 95 | /** |
| 96 | * Read a variable-length negative offset used by OFS_DELTA. |
| 97 | * The encoding uses the high bit as a continuation flag, but each |
| 98 | * subsequent byte adds 1 before shifting (to avoid ambiguity). |
| 99 | */ |
| 100 | export function readOfsOffset(buf: Uint8Array, offset: number): { value: number; bytesRead: number } { |
| 101 | let byte = buf[offset]; |
| 102 | let value = byte & 0x7f; |
| 103 | let bytesRead = 1; |
| 104 | |
| 105 | while (byte & 0x80) { |
| 106 | byte = buf[offset + bytesRead]; |
| 107 | bytesRead++; |
| 108 | value = ((value + 1) << 7) | (byte & 0x7f); |
| 109 | } |
| 110 | |
| 111 | return { value, bytesRead }; |
| 112 | } |
| 113 |