# Pack 파일

Pack 파일은 효율적인 저장과 전송을 위한 git의 방식입니다. 각 객체를 별도의 zlib 압축 파일로 저장하는 대신, pack 파일 하나에 여러 객체를 합치고 선택적으로 델타 압축을 적용합니다. 복제한 저장소는 거의 모두 pack 파일을 사용합니다.

## Pack 파일 구조

Pack 파일(`.git/objects/pack/pack-{hash}.pack`)에는 다음이 들어 있습니다.

```
Header:   PACK (4 bytes) + version (4 bytes, big-endian) + count (4 bytes, big-endian)
Entries:  [type+size varint] [delta-base] [zlib-compressed data] ...
Trailer:  checksum of the pack (20 bytes SHA-1, 32 bytes SHA-256)
```

### 객체 유형 인코딩

각 항목은 유형과 크기가 서로 섞여 인코딩된 가변 길이 정수로 시작합니다.

```
First byte: 1TTTSSSS
  TTT  = object type (1-4 for base objects, 6 for OFS_DELTA, 7 for REF_DELTA)
  SSSS = first 4 bits of uncompressed size
  MSB  = 1 means more size bytes follow
```

유형 값:
| 값 | 유형 |
|-------|------|
| 1 | Commit |
| 2 | Tree |
| 3 | Blob |
| 4 | Tag |
| 6 | OFS_DELTA(오프셋 기반 델타) |
| 7 | REF_DELTA(해시 기반 델타) |

## Pack 파일 읽기

```php
use Pitmaster\Pack\PackFile;

$pack = PackFile::open(
    '/path/to/.git/objects/pack/pack-abc123.pack',
    '/path/to/.git/objects/pack/pack-abc123.idx',
);

$pack->has($hex);               // Is the object in this pack?
$object = $pack->read($hex);    // Resolved GitObject, or null
$object = $pack->readAtOffset($offset);
$hashes = $pack->allHashes();
```

`PackFile` 클래스는 다음 작업을 수행합니다.
1. `PACK` 헤더와 버전 번호를 검증합니다.
2. `.idx` 파일에서 오프셋을 찾고 항목의 유형/크기 varint를 파싱합니다.
3. zlib 압축 데이터를 풉니다.
4. 기본 객체라면 콘텐츠를 그대로 반환합니다.
5. 델타 객체라면 기본 객체를 찾고(연쇄 참조를 따라가며) 델타를 적용한 다음 해석된 객체를 캐시합니다.

## Pack 인덱스 파일

모든 `.pack` 파일에는 빠른 조회를 위한 `.idx` 파일이 하나씩 대응됩니다. 인덱스가 없으면 객체를 찾기 위해 pack 전체를 검색해야 합니다.

### v2 인덱스 형식

```
Magic:    FF 74 4F 63 (identifies v2)
Version:  00 00 00 02
Fanout:   256 x 4-byte big-endian counts (cumulative)
Names:    N x 20-byte SHA-1 hashes, sorted (32 bytes for SHA-256)
CRC32s:   N x 4-byte CRC32 checksums
Offsets:  N x 4-byte pack offsets (MSB=1 means large offset table)
Large:    M x 8-byte offsets (for packs > 2GB)
Checksums: pack checksum + index checksum (20 bytes each for SHA-1)
```

```php
use Pitmaster\Pack\PackIndex;

$index = PackIndex::open('/path/to/pack-abc123.idx');

// Look up an object
$offset = $index->findOffset($hex);  // Pack file offset, or null

// List all objects in the pack
$hashes = $index->allHashes();
$count = $index->objectCount();
```

팬아웃 테이블을 사용하면 O(log n) 이진 검색이 가능합니다. 256 항목은 각 가능한 첫 번째 바이트로 시작하는 해시의 개수를 나타냅니다.

### v1 인덱스 형식

CRC32 체크섬이 없는 이전 형식입니다. Pitmaster은 두 형식을 모두 지원합니다. v2 매직 값이 없으면 `PackIndex::open()`이 v1 파일을 읽으므로 같은 코드로 어느 형식이든 처리할 수 있습니다.

## 델타 해석

델타로 저장된 객체는 전체 콘텐츠 대신 기본 객체에서 콘텐츠를 재구성하는 명령을 저장합니다. 이를 통해 비슷한 객체(e.g, 같은 파일의 연속 버전 등)를 크게 압축할 수 있습니다.

### 델타 유형

**OFS_DELTA**(유형 6): 기본 객체는 같은 pack 파일 내에서 음수 오프셋으로 식별합니다. 기본 객체의 해시를 몰라도 되므로 더 흔히 사용됩니다.

**REF_DELTA** (유형 7): 기본 객체는 해시로 식별됩니다. Git에서는 기본 객체가 팩 외부에 있을 수 있습니다(얇은 팩). Pitmaster은 같은 팩 안에서만 REF_DELTA 기본 객체를 찾으므로 얇은 팩은 지원되지 않습니다([#16](https://github.com/inline0/pitmaster/issues/16)).

### 델타 명령

델타 콘텐츠는 복사 및 삽입 명령의 연속입니다.

```
Copy:   1XXXXXXX [offset bytes] [size bytes]   (copy from base)
Insert: 0LLLLLLL <L bytes of literal data>       (insert new data)
```

복사 명령: 7개의 X 비트는 오프셋 및 크기 바이트 중 어떤 것이 있는지 나타냅니다. 오프셋은 최대 4바이트, 크기는 최대 3바이트입니다. 크기가 0이면 0x10000(65536)바이트를 뜻합니다.

삽입 명령: 7개의 L 비트는 리터럴 데이터 길이(1~127바이트)를 나타냅니다. L=0은 예약된 값이며 유효하지 않습니다.

### DeltaApplier

```php
use Pitmaster\Pack\DeltaApplier;

$result = DeltaApplier::apply($baseContent, $deltaInstructions);
```

`DeltaApplier`은 다음 작업을 수행합니다.
1. 델타 헤더(LEB128 인코딩)에서 예상 기본 크기와 결과 크기를 읽습니다.
2. 명령을 순회합니다.
   - 복사: 오프셋과 크기를 추출하고 기본 콘텐츠에서 바이트를 복사합니다.
   - 삽입: 길이를 추출하고 델타 데이터에서 리터럴 바이트를 복사합니다.
3. 결과 크기가 예상 크기와 일치하는지 확인합니다.

### 델타 연쇄

델타로 저장된 객체의 기본 객체도 델타로 저장되었을 수 있습니다. `PackFile::read()`와 `readAtOffset()`은 다음과 같이 연쇄를 따라갑니다.

1. 항목을 읽습니다. 기본 유형(commit, tree, blob, tag)이면 반환합니다.
2. OFS_DELTA인 경우: 현재 오프셋에서 인코딩된 음수 오프셋을 빼 기본 오프셋을 계산하고, 기본 항목을 읽은 뒤 재귀적으로 처리합니다.
3. REF_DELTA인 경우: 같은 pack의 인덱스에서 해시로 기본 객체를 찾아 재귀적으로 처리합니다.
4. 해석된 기본 객체에 델타 명령을 적용합니다.
5. 무한정 길어지는 연쇄를 막기 위해 `PITMASTER_MAX_DELTA_CHAIN`(기본값 50)을 적용합니다.

```php
// Configure max chain depth (integer)
define('PITMASTER_MAX_DELTA_CHAIN', 50);

// Read the effective limit
$max = \Pitmaster\Pack\DeltaResolver::maxChainDepth();
```

## PackWriter

Pitmaster은 네트워크 작업(push)을 위해 pack 파일을 쓸 수 있습니다.

```php
use Pitmaster\Pack\PackWriter;
use Pitmaster\Pack\PackIndexer;

$packData = PackWriter::encode($objects);           // GitObject[] to pack bytes
$paths = PackWriter::write($packDir, $objects);     // ['packPath' => ..., 'idxPath' => ..., 'hash' => ...]

$idxPath = PackIndexer::writeIndex($packPath);      // Build the .idx for a received pack
```

`PackWriter`은 다음 작업을 수행합니다.
1. pack에 포함할 객체를 모읍니다.
2. 각 객체를 유형/크기 varint 헤더와 함께 직렬화합니다.
3. 콘텐츠를 zlib으로 압축합니다.
4. PACK 헤더, 항목, SHA-1 트레일러를 씁니다.

현재는 기본 객체만 씁니다(델타 압축 없음). 델타 압축은 나중에 추가할 수 있는 최적화입니다. 저장 공간을 효율적으로 쓰도록 `git gc`이 다시 패킹하게 하세요.

## PackEnumerator

인덱스 순서대로 pack의 모든 객체를 순회합니다.

```php
use Pitmaster\Pack\PackEnumerator;

$enumerator = new PackEnumerator($packFile); // a PackFile opened with its .idx

foreach ($enumerator->enumerate() as $object) {
    echo "{$object->type->value} {$object->id->hex} {$object->size()}\n";
}
```

각 항목은 해석된 `GitObject`입니다.

## MultiPackIndex

pack 파일이 많은 저장소에서는 멀티 pack 인덱스(MIDX)가 모든 pack에 걸친 단일 조회 기능을 제공합니다.

```php
use Pitmaster\Pack\MultiPackIndex;
```

MIDX 파일(`.git/objects/pack/multi-pack-index`)에는 다음이 들어 있습니다.
- 팬아웃 테이블(pack 인덱스 v2과 유사)
- 모든 pack에 걸쳐 정렬된 객체 ID
- pack 파일 이름과 객체별 pack 할당 정보
- 개별 pack 파일의 오프셋

`MultiPackIndex::open($path)`은 MIDX 파일을 파싱해 `findObject($hex)`과 `packNames()`를 제공합니다. 저장소의 객체 조회는 이를 사용하지 않습니다. 객체 데이터베이스는 항상 개별 `.idx` 파일을 읽습니다.

## CommitGraph

commit-graph 파일은 commit 기록 순회와 병합 기반 계산을 빠르게 합니다.

```php
use Pitmaster\Pack\CommitGraph;
```

`.git/objects/info/commit-graph`에 있으며 다음이 들어 있습니다.
- 정렬된 commit OID
- 상위 commit 정보(객체를 읽지 않고 인덱스로 조회)
- 세대 번호(도달 가능성 조회를 더 빠르게 함)
- commit 타임스탬프

commit-graph가 있으면 `Repository::merge()`, `mergeBase()`, `isBranchMerged()` 뒤에서 수행되는 병합 기반 계산과 push의 fast-forward 검사는 개별 commit 객체를 읽는 대신 commit-graph에서 상위 commit 링크를 읽습니다. `CommitWalker`(log)은 이를 사용하지 않습니다.

## 가변 길이 정수

Pack 파일은 여러 가변 길이 정수 인코딩을 사용합니다.

### Git varint(유형/크기 헤더)

최상위 비트가 뒤에 바이트가 더 있는지를 나타내는 MSB 연속 인코딩입니다.

```php
use Pitmaster\Encoding\VarInt;

$size = VarInt::decodePackSize($reader, $initialBits);  // continues the size from the first header byte
$offset = VarInt::decodeOfsOffset($reader);             // OFS_DELTA base distance
$header = VarInt::encodePackSize($type, $size);
```

### LEB128(델타 헤더)

기본 크기와 결과 크기를 위한 델타 명령 헤더에 사용됩니다.

```php
use Pitmaster\Encoding\Leb128;

$value = Leb128::decodeUnsigned($reader);   // a BinaryReader
$bytes = Leb128::encodeUnsigned($value);
```

### BinaryReader

위치 추적 기능이 있는 저수준 바이트 스트림입니다.

```php
use Pitmaster\Encoding\BinaryReader;

$reader = new BinaryReader($data);
$byte = $reader->readByte();
$int = $reader->readUint32();   // big-endian
$bytes = $reader->read(20);
$hash = $reader->readHash(20);
$reader->position();  // Current offset
$reader->seek(0);
```