# Datoteke Pack

Datoteke pack so mehanizem za učinkovito shranjevanje in prenos v git. Namesto da bi vsak objekt shranili kot ločeno datoteko, stisnjeno z zlib, datoteke pack združijo več objektov v eno datoteko z možnostjo delta stiskanja. Skoraj vsak kloniran repozitorij uporablja datoteke pack.

## Struktura datoteke pack

Datoteka pack (`.git/objects/pack/pack-{hash}.pack`) vsebuje:

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

### Kodiranje vrste objekta

Vsak vnos se začne s celoštevilskim zapisom spremenljive dolžine, v katerem se prepletata vrsta in velikost:

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

Vrednosti vrst:
| Vrednost | Vrsta |
|-------|------|
| 1 | Commit |
| 2 | Tree |
| 3 | Blob |
| 4 | Oznaka |
| 6 | OFS_DELTA (delta na podlagi odmika) |
| 7 | REF_DELTA (delta na podlagi zgoščene vrednosti) |

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

Razred `PackFile`:
1. Preveri glavo `PACK` in številko različice
2. V datoteki `.idx` poišče odmik ter razčleni zapis spremenljive dolžine za vrsto in velikost
3. Razširi podatke, stisnjene z zlib
4. Pri osnovnih objektih neposredno vrne vsebino
5. Pri delta objektih razreši osnovo (po potrebi sledi verigam) in uporabi delto; razrešene objekte predpomni

## Indeksne datoteke pack

Vsaka datoteka `.pack` ima ustrezno datoteko `.idx` za hitra iskanja. Brez indeksa je treba za iskanje objekta pregledati celotno datoteko pack.

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

Tabela fanout omogoča binarno iskanje v O(log n): vnosi 256 povedo, koliko zgoščenih vrednosti se začne z vsakim možnim prvim bajtom.

### Oblika indeksa v1

Starejša oblika brez kontrolnih vsot CRC32. Pitmaster podpira obe obliki: `PackIndex::open()` prebere datoteko v1, če manjka čarobna vrednost v2, zato ista koda deluje za obe.

## Razreševanje delt

Objekti, zapisani z delto, hranijo navodila za obnovitev vsebine iz osnovnega objekta namesto celotne vsebine. To omogoča znatno stiskanje podobnih objektov (e.g, na primer zaporednih različic iste datoteke).

### Vrste delt

**OFS_DELTA** (vrsta 6): osnovni objekt je določen z negativnim odmikom znotraj iste datoteke pack. Ta oblika je pogostejša, ker ni treba poznati zgoščene vrednosti osnovnega objekta.

**REF_DELTA** (vrsta 7): osnovni objekt je določen z njegovo zgoščeno vrednostjo. V git je lahko osnova zunaj datoteke pack (tanke datoteke pack). Pitmaster išče REF_DELTA osnove samo znotraj iste datoteke pack, zato tanke datoteke pack niso podprte ([#16](https://github.com/inline0/pitmaster/issues/16)).

### Navodila delte

Vsebina delte je zaporedje navodil za kopiranje in vstavljanje:

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

Navodila za kopiranje: 7 bitov X označuje, kateri bajti odmika in velikosti so prisotni. Odmik je dolg največ 4 bajte, velikost pa največ 3 bajte. Če je velikost nič, to pomeni 0x10000 (65536) bajtov.

Navodila za vstavljanje: 7 bitov L podaja dolžino dobesednih podatkov (1–127 bajtov). L=0 je rezervirano oziroma neveljavno.

### DeltaApplier

```php
use Pitmaster\Pack\DeltaApplier;

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

`DeltaApplier`:
1. Iz glave delte (kodirane z LEB128) prebere pričakovano velikost osnove in velikost rezultata
2. Ponavlja navodila:
   - Kopiranje: pridobi odmik in velikost ter kopira bajte iz vsebine osnove
   - Vstavljanje: pridobi dolžino ter kopira dobesedne bajte iz podatkov delte
3. Preveri, ali se velikost rezultata ujema s pričakovano velikostjo

### Verige delt

Osnovni objekt, zapisan z delto, je lahko sam zapisan z delto. `PackFile::read()` in `readAtOffset()` sledita verigi:

1. Prebere vnos. Če gre za osnovno vrsto (commit, tree, blob, tag), ga vrne.
2. Če je OFS_DELTA: izračuna odmik osnove (trenutni odmik minus kodirani negativni odmik), prebere osnovni vnos in rekurzivno nadaljuje.
3. Če je REF_DELTA: v indeksu iste datoteke pack poišče osnovo po zgoščeni vrednosti in rekurzivno nadaljuje.
4. Navodila delte uporabi za razrešeno osnovo.
5. Uveljavi `PITMASTER_MAX_DELTA_CHAIN` (privzeto 50), da prepreči predolge verige.

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

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

## PackWriter

Pitmaster lahko zapisuje datoteke pack za omrežne operacije (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. Zbere objekte za vključitev v datoteko pack
2. Serializira vsak objekt z glavo za vrsto in velikost v zapisu spremenljive dolžine
3. Stisne vsebino z zlib
4. Zapiše glavo PACK, vnose in zaključni podatek SHA-1

Trenutno zapisuje samo osnovne objekte (brez delta stiskanja). Delta stiskanje je optimizacija, ki jo je mogoče dodati pozneje; za učinkovitejše shranjevanje naj objekte preuredi `git gc`.

## PackEnumerator

Pojdi skozi vse objekte v datoteki pack po vrstnem redu indeksa:

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

Vsak element je razrešen `GitObject`.

## MultiPackIndex

Za repozitorije z veliko datotekami pack večkratni indeks paketov (MIDX) omogoča skupno iskanje v vseh datotekah pack.

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

Datoteka MIDX (`.git/objects/pack/multi-pack-index`) vsebuje:
- Tabelo fanout (podobno indeksu pack v2)
- ID-je objektov, razvrščene med vsemi datotekami pack
- Imena datotek pack in dodelitve datotek pack posameznim objektom
- Odmike v posamezne datoteke pack

`MultiPackIndex::open($path)` razčleni datoteko MIDX ter omogoča `findObject($hex)` in `packNames()`. Iskanje objektov v repozitoriju je ne uporablja: zbirka objektov vedno bere posamezne datoteke `.idx`.

## CommitGraph

Datoteka grafa commit pospeši pregledovanje zgodovine commitov in izračun osnovne točke za združevanje.

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

Datoteka je na lokaciji `.git/objects/info/commit-graph` in vsebuje:
- ID-je commitov v razvrščenem vrstnem redu
- Podatke o nadrejenih commitih (indeksirane, brez branja objektov)
- Generacijske številke (za hitrejša preverjanja dosegljivosti)
- Časovne oznake commitov

Če je datoteka prisotna, izračun osnovne točke za združevanje v ozadju `Repository::merge()`, `mergeBase()`, `isBranchMerged()` in preverjanja hitrega pomika pri pošiljanju bere povezave do nadrejenih commitov iz grafa commitov namesto posameznih objektov commit. `CommitWalker` (log) je ne uporablja.

## Celoštevilski zapisi spremenljive dolžine

Datoteke pack uporabljajo več kodiranj celoštevilskih vrednosti spremenljive dolžine:

### Zapis varint Git (glave vrste in velikosti)

Kodiranje MSB-continue, pri katerem najpomembnejši bit označuje, da sledijo dodatni bajti:

```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 (glave delt)

Uporablja se v glavah navodil delte za velikost osnove in rezultata:

```php
use Pitmaster\Encoding\Leb128;

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

### BinaryReader

Nizkobitni tok bajtov s sledenjem položaju:

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