Napisać w asemblerze NASM program do kompresji i dekompresji plików z użyciem kodu Huffmana. Opis algorytmu tworzenia kodu Huffmana znajduje się w książce [1]. Kompresowany plik traktujemy jako ciąg bitów podzielony na N-bitowe słowa. Pierwszym bitem rozważanego ciągu jest najmłodszy bit pierwszego bajtu. Ostatnim bitem tego ciągu jest najstarszy bit ostatniego bajtu. Jeśli ostatnie słowo pliku jest krótsze niż N bitów, to uzupełniamy go w dowolny sposób. Program powinien obsługiwać wartości N z przedziału przynajmniej od 4 do 17.
Program wywołany z trzema argumentami wykonuje kompresję. Pierwszy argument to nazwa pliku kompresowanego, drugi to nazwa pliku skompresowanego, a trzeci to liczba bitów N. Program wywołany z dwoma argumentami wykonuje dekompresję. Pierwszy argument to nazwa pliku skompresowanego, a drugi to nazwa pliku po dekompresji.
Kompresja może przebiegać w czterech etapach. W pierszym etapie analizujemy częstotliwość występowania poszczególnych słów. W drugim etapie tworzymy drzewo kodu Huffmana. W trzecim etapie zapisujemy do pliku wynikowego informacje niezbędne do odtworzenia pliku źródłowego. W czwartym etapie komresujemy zawartość pliku źródłowego i zapisujemy w pliku wynikowym.
Można najpierw wykonać implementację naiwną, a potem zastanowić się nad poprawieniem jej efektywności. Aby czytanie z pliku i zapisywanie do pliku były efektywne, należy zaimplementować procedury buforowanego czytania i zapisu. Efektywne tworzenie kodu Huffmana można zrobić np. za pomocą kopca [1]. Można się też zastanowić nad możliwie efektywnym zakodowaniem drzewa kodu w skompresowanym pliku.
Program powinien obsługiwać duże pliki, niemieszczące się w całości w pamięci operacyjnej. Struktury danych do przechowywania drzewa kodu mogą być statyczne i globalne.
Program będzie oceniany w skali od 0 do 6 punktów. Aby dostać dodatnią liczbę punktów, należy przedstawić do oceny program, który działa poprawnie dla poprawnych danych wejściowych. Punkty będą przyznawane w następujący sposób:
[1] T. H. Cormen, Ch. E. Leiserson, R. L. Rivest, Wprowadzenie do algorytmów.
Drugie zadanie będzie oceniane w skali punktowej od 0 do nieskończoności. Przy czym uzyskanie za nie więcej niż 6 punktów będzie prawdopodobnie wymagało pewnego wysiłku. Aby zaliczyć laboratorium, należy zgromadzić łącznie z obu zadań ostro więcej niż 7 punktów. Ocena bardzo dobra (czyli premia na egzaminie) będzie przyznawana za oddanie obu zadań do ostatniego dnia dydaktycznego semestru i uzyskanie łącznie ostro więcej niż 11 punktów.