# Packfiler

Packfiler är gits mekanism för effektiv lagring och överföring. I stället för att lagra varje objekt som en separat zlib-komprimerad fil samlar packfiler många objekt i en enda fil med valfri deltacomprimering. Nästan alla klonade förråd använder packfiler.

## Packfilens struktur

En packfil (`.git/objects/pack/pack-{hash}.pack`) innehåller:

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

Varje post inleds med ett heltal med variabel längd där typen och storleken är sammanflätade:

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

Typvärden:
| Värde | Typ |
|-------|------|
| 1 | Commit |
| 2 | Tree |
| 3 | Blob |
| 4 | Tag |
| 6 | OFS_DELTA (offsetbaserad delta) |
| 7 | REF_DELTA (hashbaserad delta) |

## Läsa packfiler

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

Klassen `PackFile`:
1. Validerar huvudet `PACK` och versionsnumret
2. Hittar offseten via filen `.idx` och tolkar postens varint för typ/storlek
3. Dekomprimerar de zlib-komprimerade data
4. För basobjekt: returnerar innehållet direkt
5. För deltaobjekt: löser upp basen (följer kedjor) och tillämpar deltan samt cachelagrar lösta objekt

## Packindexfiler

Varje fil av typen `.pack` har en motsvarande fil av typen `.idx` för snabba sökningar. Utan indexet krävs en genomsökning av hela packfilen för att hitta ett objekt.

### v2-indexformat

```
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 möjliggör O(log n) binärsökning: de 256 posterna anger hur många hashvärden som börjar med varje möjlig första byte.

### v1-indexformat

Äldre format utan CRC32-kontrollsummor. Pitmaster stöder båda: `PackIndex::open()` läser en fil av typen v1 när v2-magin saknas, så samma kod fungerar för båda.

## Deltaupplösning

Deltakodade objekt lagrar instruktioner för att återskapa innehåll från ett basobjekt i stället för att lagra hela innehållet. Det ger betydande komprimering för liknande objekt (e.g, till exempel flera versioner av samma fil efter varandra).

### Deltatyper

**OFS_DELTA** (typ 6): basobjektet identifieras med en negativ offset i samma packfil. Detta är vanligare eftersom basobjektets hash inte behöver vara känd.

**REF_DELTA** (typ 7): basobjektet identifieras med sin hash. I git kan basen finnas utanför paketet (tunna paket). Pitmaster söker endast efter REF_DELTA-baser i samma paket, så tunna paket stöds inte ([#16](https://github.com/inline0/pitmaster/issues/16)).

### Deltainstruktioner

Deltainnehåll är en sekvens av kopierings- och infogningsinstruktioner:

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

Kopieringsinstruktioner: de 7 X-bitarna anger vilka byte för offset och storlek som finns. Offseten är upp till 4 byte och storleken upp till 3 byte. Om storleken är noll betyder det 0x10000 (65536) byte.

Infogningsinstruktioner: de 7 L-bitarna anger längden på literaldata (1–127 byte). L=0 är reserverat/ogiltigt.

### DeltaApplier

```php
use Pitmaster\Pack\DeltaApplier;

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

`DeltaApplier`:
1. Läser förväntad basstorlek och resultatstorlek från deltahuvudet (LEB128-kodat)
2. Går igenom instruktionerna:
   - Kopiera: hämtar offset och storlek och kopierar byte från basinnehållet
   - Infoga: hämtar längden och kopierar bokstavliga byte från deltadatan
3. Verifierar att resultatstorleken motsvarar den förväntade storleken

### Deltakedjor

Basobjektet för ett deltakodat objekt kan i sin tur vara deltakodat. `PackFile::read()` och `readAtOffset()` följer kedjan:

1. Läs posten. Om den är av en bastyp (commit, tree, blob, tagg) returnerar du den.
2. Om OFS_DELTA: beräkna basens offset (aktuell offset minus den kodade negativa offseten), läs basposten och anropa rekursivt.
3. Om REF_DELTA: slå upp basen efter hash i samma packfils index och anropa rekursivt.
4. Tillämpa deltainstruktionerna på den upplösta basen.
5. Upprätthåll `PITMASTER_MAX_DELTA_CHAIN` (standardvärde 50) för att förhindra okontrollerat långa kedjor.

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

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

## PackWriter

Pitmaster kan skriva packfiler för nätverksåtgärder (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. Samlar objekten som ska ingå i packfilen
2. Serialiserar varje objekt med ett varint-huvud för typ/storlek
3. Komprimerar innehållet med zlib
4. Skriver PACK-huvudet, posterna och SHA-1-trailern

Skriver för närvarande bara basobjekt (ingen deltacomprimering). Deltacomprimering är en optimering som kan läggas till senare; låt `git gc` packa om för effektiv lagring.

## PackEnumerator

Iterera genom alla objekt i en packfil, i indexordning:

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

Varje post är ett upplöst `GitObject`.

## MultiPackIndex

För förråd med många packfiler ger multi-pack-indexet (MIDX) en enda sökning över alla packfiler.

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

MIDX-filen (`.git/objects/pack/multi-pack-index`) innehåller:
- En fanout-tabell (liknande packindex v2)
- Objekt-ID:n sorterade över alla packfiler
- Packfilnamn och packtilldelning per objekt
- Offsetar i de enskilda packfilerna

`MultiPackIndex::open($path)` tolkar en MIDX-fil och erbjuder `findObject($hex)` och `packNames()`. Objektuppslagningar i förrådet använder den inte: objektdatabasen läser alltid de enskilda `.idx`-filerna.

## CommitGraph

Commit-graph-filen snabbar upp genomgången av commit-historiken och beräkningen av gemensam förfader vid sammanslagning.

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

Den ligger i `.git/objects/info/commit-graph` och innehåller:
- Commit-OID:n i sorterad ordning
- Föräldrainformation (indexerad, utan att objekt behöver läsas)
- Generationsnummer (för snabbare nåbarhetsfrågor)
- Tidsstämplar för commits

När den finns läser beräkningen av gemensam förfader bakom `Repository::merge()`, `mergeBase()`, `isBranchMerged()` och pushens snabbspolningskontroll föräldralänkar från commit-graph-filen i stället för att läsa enskilda commit-objekt. `CommitWalker` (log) använder den inte.

## Heltal med variabel längd

Packfiler använder flera kodningar för heltal med variabel längd:

### Git-varint (huvuden för typ/storlek)

MSB-fortsättningskodning där den mest signifikanta biten anger att fler byte följer:

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

Används i deltans instruktionshuvuden för basstorlek och resultatstorlek:

```php
use Pitmaster\Encoding\Leb128;

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

### BinaryReader

Byte-ström på låg nivå med positionsspårning:

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