# Pack-filer

Pack-filer er gits mekanisme til effektiv lagring og overførsel. I stedet for at gemme hvert objekt som en separat zlib-komprimeret fil samler pack-filer mange objekter i én fil med valgfri deltakomprimering. Næsten alle klonede repositories bruger pack-filer.

## Pack-filstruktur

En pack-fil (`.git/objects/pack/pack-{hash}.pack`) indeholder:

```
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)
```

### Kodning af objekttyper

Hver post begynder med et heltal med variabel længde, hvor type og størrelse er flettet sammen:

```
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
```

Typeværdier:
| Værdi | Type |
|-------|------|
| 1 | Commit |
| 2 | Tree |
| 3 | Blob |
| 4 | Tag |
| 6 | OFS_DELTA (offsetbaseret delta) |
| 7 | REF_DELTA (hashbaseret delta) |

## Læsning af pack-filer

```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`-klassen:
1. Validerer `PACK`-headeren og versionsnummeret
2. Finder offsettet via `.idx`-filen og analyserer postens type/størrelse-varint
3. Dekomprimerer de zlib-komprimerede data
4. For basisobjekter: returnerer indholdet direkte
5. For deltaobjekter: løser basisobjektet (følger kæder) og anvender deltaet, mens løste objekter caches

## Pack-indeksfiler

Hver `.pack`-fil har en tilhørende `.idx`-fil til hurtige opslag. Uden indekset kræver det en scanning af hele pack-filen at finde et objekt.

### Indeksformat for 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();
```

Fanout-tabellen muliggør binær søgning i O(log n): 256-posterne angiver, hvor mange hasher der begynder med hver mulig første byte.

### Indeksformat for v1

Ældre format uden CRC32-kontrolsummer. Pitmaster understøtter begge: `PackIndex::open()` læser en v1-fil, når v2-magien mangler, så den samme kode virker til begge.

## Deltaopløsning

Delta-kodede objekter gemmer instruktioner til at genskabe indholdet fra et basisobjekt i stedet for at gemme hele indholdet. Det giver betydelig komprimering for lignende objekter (e.g., fortløbende versioner af samme fil).

### Deltatyper

**OFS_DELTA** (type 6): Basisobjektet identificeres med et negativt offset i den samme pack-fil. Det er mere almindeligt, fordi det ikke kræver kendskab til basisobjektets hash.

**REF_DELTA** (type 7): Basisobjektet identificeres med dets hash. I git kan basisobjektet ligge uden for pack-filen (tynde packs). Pitmaster søger kun efter REF_DELTA-basisobjekter i den samme pack, så tynde packs understøttes ikke ([#16](https://github.com/inline0/pitmaster/issues/16)).

### Deltainstruktioner

Deltaindhold er en sekvens af kopierings- og indsætningsinstruktioner:

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

Kopieringsinstruktioner: De 7 X-bit angiver, hvilke offset- og størrelsesbyte der er til stede. Offset er op til 4 byte, størrelse op til 3 byte. Hvis størrelsen er nul, betyder det 0x10000 (65536) byte.

Indsætningsinstruktioner: De 7 L-bit angiver længden af de bogstavelige data (1-127 byte). L=0 er reserveret/ugyldigt.

### DeltaApplier

```php
use Pitmaster\Pack\DeltaApplier;

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

`DeltaApplier`:
1. Læser den forventede basisstørrelse og resultatstørrelsen fra delta-headeren (LEB128-kodet)
2. Gennemløber instruktionerne:
   - Kopiér: udtrækker offset og størrelse og kopierer byte fra basisindholdet
   - Indsæt: udtrækker længden og kopierer bogstavelige byte fra deltadataene
3. Kontrollerer, at resultatstørrelsen svarer til den forventede størrelse

### Deltakæder

Et delta-kodet objekts basis kan selv være delta-kodet. `PackFile::read()` og `readAtOffset()` følger kæden:

1. Læs posten. Hvis den er af basistype (commit, tree, blob, tag), returneres den.
2. Hvis OFS_DELTA: beregn basis-offsettet (aktuelt offset minus det kodede negative offset), læs basisposten, og kald rekursivt.
3. Hvis REF_DELTA: slå basisobjektet op efter hash i indekset for samme pack, og kald rekursivt.
4. Anvend deltainstruktionerne på den løste basis.
5. Håndhæv `PITMASTER_MAX_DELTA_CHAIN` (standard 50) for at forhindre kæder, der løber løbsk.

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

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

## PackWriter

Pitmaster kan skrive pack-filer til netværkshandlinger (push).

```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. Samler de objekter, der skal med i pack-filen
2. Serialiserer hvert objekt med en type/størrelse-varint-header
3. Komprimerer indholdet med zlib
4. Skriver PACK-headeren, posterne og traileren SHA-1

Skriver i øjeblikket kun basisobjekter (uden deltakomprimering). Deltakomprimering er en optimering, der kan tilføjes senere; lad `git gc` pakke om til mere effektiv lagring.

## PackEnumerator

Gennemløb alle objekter i en pack i indeksrækkefølge:

```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";
}
```

Hvert element er et løst `GitObject`.

## MultiPackIndex

For repositories med mange pack-filer giver multi-pack-indekset (MIDX) ét samlet opslag på tværs af alle packs.

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

MIDX-filen (`.git/objects/pack/multi-pack-index`) indeholder:
- En fanout-tabel (som pack-indeks v2)
- Objekt-id'er sorteret på tværs af alle packs
- Pack-filnavne og pack-tildeling for hvert objekt
- Offsets i de enkelte pack-filer

`MultiPackIndex::open($path)` analyserer en MIDX-fil og tilbyder `findObject($hex)` og `packNames()`. Objektopslag i repositoryet bruger den ikke: objektdatabasen læser altid de enkelte `.idx`-filer.

## CommitGraph

Commit-graph-filen fremskynder gennemløb af commit-historik og beregning af merge-basis.

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

Placeret på `.git/objects/info/commit-graph` indeholder den:
- Commit-OID'er i sorteret rækkefølge
- Forældreoplysninger (indekseret, kræver ikke objektlæsninger)
- Generationsnumre (til hurtigere forespørgsler om nåbarhed)
- Commit-tidsstempler

Når det er relevant, henter beregningen af merge-base bag `Repository::merge()`, `mergeBase()`, `isBranchMerged()` og push-kontrollen for fast-forward parent-links fra commit-grafen i stedet for at læse individuelle commit-objekter. `CommitWalker` (log) bruger den ikke.

## Heltal med variabel længde

Pack-filer bruger flere kodninger af heltal med variabel længde:

### Git varint (type-/størrelsesheadere)

MSB-continue-kodning, hvor den mest betydende bit angiver, at der følger flere bytes:

```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 (delta-headere)

Bruges i delta-instruktionsheadere til basestørrelse og resultatstørrelse:

```php
use Pitmaster\Encoding\Leb128;

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

### BinaryReader

Byte-strøm på lavt niveau med positionssporing:

```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);
```