Implementace algoritmu ACB je rozdělena na dvě části: knihovnu libacb (standardně překládanou jako sdílená i statická), která obsahuje pět základních tříd, a samostatné ukázkové programy azip a aunzip demonstrující jejich použití (ty se standardně linkují staticky, aby nebyly závislé na přítomnosti sdílené knihovny libacb v systému).
Úroveň implementace algoritmu by se dala nejlépe ohodnotit jako proof-of-concept — třídy knihovny libacb provedou korektní kompresi a dekompresi libovolných dat, ovšem pro praktické nasazení algoritmu je potřeba jej ještě vylepšit o tyto důležité vlastnosti:
Pro zkoumání vlastností algoritmu a porovnávání různých variant implementace je knihovna libacb navržena maximálně modulárně, všechny metody tříd jsou virtuální pro snadnou náhradu jejich kódu alternativním. Přes omezení uvedená výše je však předkládané zpracování algoritmu plně funkční a na mnoha druzích vstupních dat (především delší textové soubory) skutečně dosahuje rozumné (byť suboptimální) míry komprese.
Adresářový strom projektu vypadá takto:
Kořenový adresář obsahuje především konfigurační skript configure (vygenerovaný pomocí utility Autoconf) a po jeho provedení také hlavní soubor Makefile. Projekt se překládá a instaluje běžným způsobem:
./configure make make install
Adresář doc obsahuje dokumentaci projektu, include po překladu hlavičkové soubory potřebné pro používání knihovny libacb cílovými programy, adresář lib po překladu sdílenou a statickou podobu knihovny libacb (libacb.so, libacb.a), adresář sample obsahuje zdrojové soubory ukázkových programů azip a aunzip a po překladu také jejich spustitelné tvary (ty jsou přeloženy staticky, aby je bylo možné použít i bez nainstalování sdílené libacb.so do systému) a konečně adresář src obsahuje samotné zdrojové soubory knihovny libacb.
Příkaz make install (pod uživatelem root) nainstaluje soubory z adresářů include a lib do systému (tedy typicky do /usr/local/include a /usr/local/lib).
Knihovna implementuje pět tříd. Třída Vocabulary je struktura reprezentující aktuální stav algoritmu komprese nebo dekomprese, třídy Encoder a TripletEncoder slouží pro kompresi a třídy Decoder a TripletDecoder pro dekompresi.
Aktuální stav komprese a dekomprese je definován obsahem slovníku, obsahem search bufferu a look-ahead bufferu. Třída Vocabulary spravuje tyto datové struktury a implementuje metody pro jejich manipulaci.
class Vocabulary {
public:
Vocabulary();
virtual ~Vocabulary();
virtual bool Exhausted(void) const;
virtual void Input(const char * input, const size_t cnt);
virtual void Compare(size_t & distance, bool & sign, size_t & match, char & next, bool & complete);
virtual char * GetContent(const size_t distance, const bool sign, const size_t match, const char next,
const bool complete, size_t & size);
}
Search a look-ahead buffer jsou uvnitř třídy reprezentovány jako jediné dynamicky alokované pole znaků (rozhraní mezi search a look-ahead oblastí určuje délka search bufferu). Při přidávání znaků pomocí Vocabulary::Input() se toto pole zvětšuje pomocí funkce realloc().
Slovník je reprezentován jako seznam (pomocí STL šablony list) obsahující index v bufferu, ktery určuje rozhraní mezi částí kontextu a contentu.
Privátní metody třídy implementují výše uvedené operace, tedy nalezení předpokládané pozice search bufferu v kontextové části slovníku, určení shody look-ahead bufferu s contentovou částí slovníku a obohacení slovníku o nové znaky (přesunutí znaku z look-ahead do search bufferu). Jedna metoda slouží pro výpis aktuálního slovníku na chybový výstup v případě ladění.
Třída ukládající data po kompresi do výstupního streamu. Zkomprimovaná data představují posloupnost trojic [(s)d, m, n], přičemž d je rozdíl nalezeného kontextu a contentu (s je znaménko), m je délka shody look-ahead bufferu a contentu a n je první neshodující se znak.
Trojice se do výstupního streamu ukládají za sebou po jednotlivých bitech a další úspory se dosahuje tím, že je-li m=0 (žádná shoda), potom se místo hodnot d a m ukládá jen jednobitový příznak. Analogicky pokud je shoda look-ahead bufferu a a contentu úplná, neukládá se do streamu neshodující se znak. To dává celkem tři možnosti uložení trojice (čtvrtá možnost bez shody a bez znaku nastat nemůže):
| 1 | s | d | m | 0 | n | |||||||||||||||||
| 1 | s | d | m | 1 | ||||||||||||||||||
| 0 | 0 | n | ||||||||||||||||||||
class TripletEncoder {
public:
TripletEncoder(std::ostream & _outs);
virtual ~TripletEncoder();
virtual void Encode(const size_t distance, const bool sign, const size_t match, const char next,
const bool complete);
virtual void Flush(void);
}
Třída má doplnkovou funkci k třídě TripletDecoder, tedy ze vstupního streamu čte bitově jednotlivé trojice a dekóduje je do uspořádání [(s)d, m, n], které lze poté přímo použít pro dekompresi.
class TripletDecoder {
public:
TripletDecoder(std::istream & _ins);
virtual ~TripletDecoder();
virtual bool Decode(size_t & distance, bool & sign, size_t & match, char & next, bool & complete);
virtual void Fill(void);
}
Třída provádějící s použitím Vocabulary a TripletEncoder samotný algoritmus komprese ACB.
class Encoder {
public:
Encoder(Vocabulary & _voc, TripletEncoder & _trip, std::istream & _ins);
virtual ~Encoder();
virtual const Encoder & operator+=(const size_t cnt);
}
Třída provádějící s použitím Vocabulary a TripletDecoder algoritmus dekomprese ACB.
class Decoder {
public:
Decoder(Vocabulary & _voc, TripletDecoder & _trip, std::ostream & _outs);
virtual ~Decoder();
virtual const Decoder & operator+=(const size_t cnt);
}
Ukázkové programy zcela přímočaře využívají knihovnu libacb. Původní (resp. komprimovaná) data jsou čtena ze standardního vstupu a na standardní výstup jsou posílana data komprimovaná (resp. dekomprimovaná).
Zdrojový kód obou ukázkových programů je téměř samovysvětlující:
#include <iostream>
#include <acb/acb.h>
int main(int argc, char * argv[]) {
ACB::Vocabulary vocabulary;
ACB::TripletEncoder tenc(std::cout);
ACB::Encoder encoder(vocabulary, tenc, std::cin);
while (!std::cin.eof())
encoder += 10240;
return 0;
}