[Rozw][ANSI C] kompresja

Problemy dotyczące programowania.

Moderatorzy: Moderatorzy, Administratorzy

Awatar użytkownika
rapid
Użytkownik
Posty: 323
Rejestracja: 2004-05-29, 11:21

[Rozw][ANSI C] kompresja

Post autor: rapid » 2008-06-04, 18:49

Kod: Zaznacz cały

while((fread(&litera, sizeof(unsigned char), 1, zrodlowy)) != 0)
   {
      for(i = 0; i < le; i++)
      {
         if(litera == tabkod[i].symbol)
            break; //wiem, ze brzydko ale kosmetyke zrobie pozniej
      }
      temp = tabkod[i].kod;
         if(wolne >= tabkod[i].dlugosc)
         {
            temp <<= (PACKET - (wolne - tabkod[i].dlugosc));
            paczka |= temp;
            wolne -= tabkod[i].dlugosc;
         }
         else
         {
            temp >>= (tabkod[i].dlugosc - wolne);
            paczka |= temp;
            fwrite(&paczka, sizeof(unsigned int), 1, docelowy);
            paczka ^= paczka;
            temp = tabkod[i].kod;
            temp <<= (PACKET - (tabkod[i].dlugosc + wolne));
            paczka |= temp;
            wolne += tabkod[i].dlugosc;
         }
         if (wolne == 0)
         {
            write (&paczka, sizeof(unsigned int), 1, docelowy);
            paczka = 0;
            wolne = PACKET;
         }
Idea: mamy juz wczytana tablice kodowa, czytamy z pliku znaki i za pomoca "paczek" o pojemnosci 32bitow i operatorow bitowych kompresujemy je i zapisujemy do pliku docelowego, oczywiscie przy okazji uwazajac aby czasem nie przepelnic paczki. Powyzszy kod nie daje rezultatu jaki powinien dawac - wydaje mi sie, ze moglem cos sknocic z przesunieciami bitowymi. Moze ktos bardziej doswiadczony dostrzeze blad/bledy.
Ostatnio zmieniony 2008-06-07, 09:12 przez rapid, łącznie zmieniany 2 razy.

kazek3018
Użytkownik
Posty: 181
Rejestracja: 2006-12-10, 14:27

Re: [Rozw][ANSI C] kompresja

Post autor: kazek3018 » 2008-06-04, 22:24

Ten algorytm działa bardzo podobnie do szyfru podstawieniowego.

Jest kilka błędów które zauważyłem. Po pierwsze nie wkleiłeś całej funkcji i nigdzie nie widzę deklaracji zmiennej temp. Ufam, że jest ona typu unsigned, gdyż ze znakiem może generować dodatkowe problemy z operatorem >>=. Ponadto musi ona być co najmniej równa długości PACKET. Przechodząc do kodu:

Kod: Zaznacz cały

            temp = tabkod[i].kod;
         if(wolne >= tabkod[i].dlugosc)
         {
            temp <<= (PACKET - (wolne - tabkod[i].dlugosc));
            paczka |= temp;
            wolne -= tabkod[i].dlugosc;
         } 
Proste obliczenia dla PACKET=32 wolne=32 dlugosc=8 (32/32/8)
(32/32/8)
daje wynik
tmp<<=8
//------------
(32/24/8)
daje wynik
tmp<<=16
//------------
(32/16/8)
daje wynik
tmp<<=24
//------------
(32/8/8)
daje wynik
tmp<<=32
//------------
Po tej operacji mamy (32/0/nieważne)
Czyli pierwsze 8 bitów nigdy nie zostanie wykorzystanych (dla tego przykładu, w innym przypadku będzie to długość zmiennej zapisanej do paczki jako pierwsza), natomiast ostatni znak zostanie całkowicie pominięty przy zapisie(dla innych danych będzie to inaczej, ale zawsze coś zniknie).
Jeżeli chodzi o else to:

Kod: Zaznacz cały

temp >>= (tabkod[i].dlugosc - wolne);
Może sprawiać problemy dla liczb ujemnych (patrz dokumentacja)

Kod: Zaznacz cały

temp = tabkod[i].kod;
            temp <<= (PACKET - (tabkod[i].dlugosc + wolne));
            paczka |= temp;
            wolne += tabkod[i].dlugosc;
Dla przykładu (32/3/5)
da nam temp<<=24
nie sądzę aby było to o co ci chodzi (zmienną paczka zaczynasz uzupełniać od prawej).
Ostatniej linijki w ogóle nie rozumiem, pomijając fakt braku ustawienia zmiennej wolne na 32. Po zapisaniu czegoś do bufora powinno być -=.

Popraw te błędy potem zobaczymy jak to będzie chodzić.

PS.
Dla tego sposobu kompresji powstaną znaczące problemy dla funkcji dekompresującej (przy założeniu, że zmienna tab[*].dlugosc może być różna dla różnych znaków).

Awatar użytkownika
rapid
Użytkownik
Posty: 323
Rejestracja: 2004-05-29, 11:21

Re: [Rozw][ANSI C] kompresja

Post autor: rapid » 2008-06-07, 09:11

Wielkie thx, posiedzialem troche, przeanalizowalem bledy, ktore mi wytknales i teraz juz dziala.
Ostatnio zmieniony 2008-06-07, 09:11 przez rapid, łącznie zmieniany 1 raz.

ODPOWIEDZ