L'algoritmo Diff Binary Diff Git è standardizzato?

Question

Git utilizza una compressione delta per archiviare oggetti simili a ciascuno.

Questo algoritmo è standardizzato e utilizzato anche in altri strumenti? C'è documentazione che descrive il formato? È compatibile con XDELTA/VCDIFF/RFC 3284?

Answer 1

Penso che l'algo diffuso File pack era collegato a uno dei codifica delta là fuori: Inizialmente (2005) xdelta, poi libxdiff.
Ma poi, come dettagliato di seguito, si è spostato su un'implementazione personalizzata.

Comunque, come menzionato qui:

Git fa deltificazione solo in pacchetti.
Ma quando si spinge tramite SSH GIT genererebbe un file di pacchetto con commetti che l'altro lato non ha e quei pacchetti sono pacchi sottili, quindi hanno anche delta ... ma il lato remoto aggiunge quindi basi a quei pacchi sottili che li rendono indipendente, autonomo.

(Nota: creare molti file di pacchetti o recuperare informazioni in enormi packfile è costoso, e spiega perché Git non gestisce file ben enormi o enormi repository.
Vedi di più a "git con file di grandi dimensioni")

Questo thread Ci ricorda anche:

In realtà pacchetti e deltification (Libxdiff, non xdelta) era, da quello che ricordo e capisco, Originariamente a causa della larghezza di banda della rete (che è molto più costoso dello spazio su disco) e Performance I/O di utilizzare un singolo file MMMAPPED invece di un numero molto elevato di oggetti sciolti.

Libxdiff è menzionato in questo Discussione 2008.

Tuttavia, da allora, l'algo si è evoluto, probabilmente in una personalizzata, così come questo Il thread 2011 illustra, e come intestazione di diff-delta.c sottolinea:

Quindi, a rigor di termini, l'attuale codice in Git non assomiglia affatto al codice Libxdiff.
Tuttavia l'algoritmo di base dietro entrambe le implementazioni è lo stesso.
Studiare la versione di Libxdiff è probabilmente più semplice per comprendere come funziona.

/*
 * diff-delta.c: generate a delta between two buffers
 *
 * This code was greatly inspired by parts of LibXDiff from Davide Libenzi
 * http://www.xmailserver.org/xdiff-lib.html
 *
 * Rewritten for GIT by Nicolas Pitre <nico@fluxnic.net>, (C) 2005-2007
 */

Di più sul packfiles il libro git:

---

Git 2.18 aggiunge alla descrizione delta In questo nuovo sezione documentazione, che ora (Q2 2018) afferma:

Tipi di oggetti

I tipi di oggetti validi sono:

• OBJ_COMMIT (1)
• OBJ_TREE (2)
• OBJ_BLOB (3)
• OBJ_TAG (4)
• OBJ_OFS_DELTA (6)
• OBJ_REF_DELTA (7)

Il tipo 5 è riservato per l'espansione futura. Il tipo 0 non è valido.

Rappresentazione deltificata

Concettualmente ci sono solo quattro tipi di oggetti: commit, albero, tag e blob.
Tuttavia, per risparmiare spazio, un oggetto potrebbe essere archiviato come un "delta" di un altro oggetto "base".
A queste rappresentazioni vengono assegnati nuovi tipi di Delta e Ref-Delta, che è valido solo in un file di pacchetto.

Tutti e due ofs-delta e ref-delta Conservare il "delta" da applicare a un altro oggetto (chiamato "oggetto base") per ricostruire l'oggetto.
La differenza tra loro è,

• Ref-Delta codifica direttamente il nome dell'oggetto di base a 20 byte.
  • Se l'oggetto base è nello stesso pacchetto, OFS-DELTA codifica invece l'offset dell'oggetto base nel pacchetto.

L'oggetto base potrebbe anche essere deltificato se si trova nella stessa confezione.
Ref-Delta può anche fare riferimento a un oggetto al di fuori del pacchetto (cioè il cosiddetto "pacchetto sottile"). Se conservato sul disco, tuttavia, il pacchetto dovrebbe essere autonomo per evitare la dipendenza ciclica.

Il dati delta è una sequenza di istruzioni per ricostruire un oggetto dall'oggetto base.
Se l'oggetto base viene deltificato, deve essere convertito prima in forma canonica. Ogni istruzione aggiunge sempre più dati all'oggetto target fino al completamento.
Finora ci sono due istruzioni supportate:

• uno per copiare una gamma di byte dall'oggetto sorgente e
• uno per inserire nuovi dati incorporati nell'istruzione stessa.

Ogni istruzione ha una lunghezza variabile. Il tipo di istruzione è determinato dal settimo pezzo del primo ottetto. I seguenti diagrammi seguono la convenzione in RFC 1951 (formato dati compresso deflate).

Answer 2

La codifica Git Delta è basata su copie/insert.

Ciò significa che il file derivato è codificato come una sequenza di codici operativi che possono rappresentare le istruzioni di copia (ad esempio: copia dal file di base y byte a partire dall'offset x nel buffer di destinazione) o inserire istruzioni (ad esempio: inserire i successivi x byte in tampone target).

Come esempio molto semplice (prelevato dal supporto del file system di carta per la compressione delta "), considera che vogliamo creare un buffer Delta per trasformare il testo" Proxy Cache "in" Proxy cache ". Le istruzioni risultanti dovrebbero essere:

1. Copia 5 byte da offset 7 (copia 'cache' dal buffer di base)
2. Inserire due spazi
3. Copia 5 byte da offset 0 (copia 'proxy' da base buffer)

Che si traduce nella codifica di Git diventa:

(byte 1-3 rappresentano la prima istruzione)

• 0x91 (10010001), che è diviso in
  • 0x80 (10000000) (il set di bit più significativo rende questa una copia da un'istruzione "Base to Output")
  • 0x01 (00000001) (significa "anticipare un byte e usarlo come offset di base)
  • 0x10 (00010000) (avanzare un byte e usarlo come lunghezza)
• 0x07 (offset)
• 0x05 (lunghezza)

(byte 4-6 rappresentano la seconda istruzione)

• 0x02 (poiché MSB non è impostato, ciò significa "inserire i due byte successivi nell'output")
• 0x20 (spazio)
• 0x20 (spazio)

(byte 7-8 rappresentano l'ultima istruzione)

• 0x90 (10010000), che è diviso in
  • 0x80 (10000000) (significa 'copia')
  • 0x10 (00010000) (avanzare un byte e usarlo come lunghezza)
• 0x05 (lunghezza)

Si noti che nell'ultima istruzione di copia non specifica un offset che significa offset 0. Altri bit nel codice Op copia possono anche essere impostati quando sono necessari offset/lunghezze più grandi.

Il buffer Delta del risultato ha in questo esempio 8 byte, il che non è molto una compressione poiché il buffer target ha 12 byte, ma quando questa codifica applicata a file di testo di grandi dimensioni può fare una differenza enorme.

Ho recentemente spinto a Libreria Node.js a github che implementa entrambe le funzioni diff/patch usando la codifica Git Delta. Ilcodice dovrebbe essere più leggibile e commentato di quello nella fonte Git, che è fortemente ottimizzato.

Ne ho anche scritti alcuniTest che spiegano i codi di output utilizzati in ciascun esempio con un formato simile a quello sopra.

Answer 3

Questo algoritmo è standardizzato e utilizzato anche in altri strumenti?

Il formato del pacchetto fa parte di un'API pubblica: i protocolli di trasferimento utilizzati per le operazioni push e recupero lo utilizzano per inviare meno dati sulla rete.

Sono implementati in almeno altre due importanti implementazioni GIT oltre al riferimento: Jgit e libgit2.

Pertanto, è molto improbabile che ci siano cambiamenti incompatibili al formato e possano essere considerati "standardizzati" in questo senso.

Questo fantastico file dai documenti descrive l'euristica utilizzata nell'algoritmo del pacchetto come commento divertente su un'e -mail di Linus: https://github.com/git/git/blob/v2.9.1/documentation/technical/pack-heuristics.txt