Idea polega na tym, że wskaźniki krążą po buforze w tym samym kierunku, tak jakby koniec bufora połączony był z początkiem, stąd nazwa "bufor cykliczny". Po dojściu do końca bufora wskaźnik przeskakuje na jego początek. Pierwszy zawsze jest wskaźnik zapisu, za nim podąża wskaźnik odczytu. Jeżeli oba wskazują na to samo miejsce to znaczy że bufor jest pusty (lub w szczególnym przypadku, wymagającym dodatkowej obsługi - bufor całkowicie pełny). Podstawowy warunek jest taki, że wskaźnik odczytu nie może "wyprzedzić" wskaźnika zapisu, bo odczytane zostały by śmieci z lokacji, które miały by być zapisane dopiero w przyszłości, ani też wskaźnik zapisu nie może "zdublować" (a w najprostszym przypadku również "dogonić") wskaźnika odczytu, zawsze musi go wyprzedzać, lub w wypadku pustego bufora, wskaźnik odczytu musi znajdować się tam gdzie wskaźnik zapisu.
Może tak w postaci kodu najprostszego i niepozbawionego wad:
#define BUF 64 /* dlugosc bufora */
char bufor[BUF];
char *wo=bufor; /* wskaznik odczytu */
char *wz=bufor; /* wskaznik zapisu */
/* funkcja wywolywana przez przerwanie po odebraniu znaku */
void zapisz_znak(char c) {
*wz = c;
wz = ((wz - bufor) & (BUF - 1)) + bufor);
}
int czytaj_znak(void) {
int c;
if(wo != wz) {
c = *wo;
wo = ((wo - bufor) & (BUF - 1)) + bufor);
return c;
}
return -1; /* bufor pusty */
}
(...)
#define LIN 32 /* dlugosc linii */
char linia[LIN];
unsigned char lp; /* aktualna pozycje w buforze linii */
int c;
(...)
/* gdzieś w glownej petli programu */
/* czyta kolejne znaki z bufora dopoki nie trafi na koniec lancucha (znak o kodzie 0), lub nie zapelni bufora */
lp = 0;
while((c = czytaj_znak()) != 0) {
if(c == -1) { /* odczytano wszystko z bufora */
continue; /* sprobuj odczytac znak ponownie */
}
linia[lp++] = c;
if(lp == (LIN-1)) { /* bufor linii pelny */
break;
}
}
linia[lp] = 0; /* dodaje znacznik konca lancucha na koncu odebranego lancucha */
Z tym AND to jest po prostu operacja modulo, można to na kilka sposobów zapisać:
1)
x++;
if(x == (KONIEC + 1)) {
x = POCZATEK;
}
2)
3)
Pierwszy przypadek - najprostszy, jeżeli x przekroczy koniec bufora, to wraca na początek. Czasem dobre, na niektórych architekturach wręcz świetnie działa (na przykład na ARM7, która to posiada instrukcje warunkowe, a nie tylko skoki). Skok warunkowy komplikuje też sprawę w systemach posiadających cache instrukcji, tu na szczęście z AVR nie ma problemu.
Przypadki 2 i 3 (a 2 przynajmniej z wyglądu) nie "psują" nic w cache i w odróżnieniu od pierwszego w postaci takiej jak tu służą raczej do operacji na indeksach tablicy zaczynających się od zera. Jeżeli miały by działać na wskaźnikach, to musiały by zostać zapisane tak jak w kodzie na początku, tak żeby z arytmetycznego punktu widzenia przesunąć najpierw wskaźnik tak, jakby początek obszaru danych zaczynał się od adresu zero, wykonać operację, a potem przywrócić wskaźnik do poprzedniego obszaru (w praktyce oznacza to najpierw odjęcie, a potem dodanie adresu pierwszego elementu tablicy).
Przypadek 2 jest niestety mało fajny z tego względu że używa dzielenia. Tam jest akurat operator modulo, ale nie zmienia to faktu, że przy okazji liczenia modulo wykonywane jest dzielenie. Jeżeli procesor potrafi je wykonać w sensownym czasie (max. kilka cykli), to może okazać się bardzo przydatny, ponieważ pozwala stosować bufory o dowolnej długości. Jeżeli procesor nie potrafi szybko dzielić, to przy długości bufora będącej potęgą dwójki kompilator
może, ale wcale nie musi zoptymalizować to do postaci takiej jak przypadek 3.
Przypadek 3 opiera sie na zależności:
a MOD b = a AND (b - 1) <=> b = 2^n
Dla przykładu:
a MOD 256 = a AND 255, a MOD 32 = a AND 31.
W kodzie na początku darowałem sobie rzutowanie, które powinno się tam znaleźć. Kompilator najprawdopodobniej "wypluje" ostrzeżenie o rzutowaniu wskaźnika na typ całkowity.
Funkcja
zapisz_znak() powinna sprawdzać czy jest jeszcze wolne miejsce w buforze. Można różnie, chyba najwydajniej będzie zrobić kopię wskaźnika (wz), zwiększyć ją o 1 (z zapętlaniem) tak jak tam jest, tylko przed zapisem znaku. Jeżeli kopia wz zwiększona i "zapętlona" jest różna od wskaźnika odczytu, to zapisać znak, a wartość kopii zapisać do wz, w przeciwnym wypadku zasygnalizować przepełnienie bufora.
Przypadek 1 można by też zastosować w kodzie który podałem na początku. gcc w wersji 4 (w najnowszym WinAVR) optymalizuje już dużo lepiej niż wersja 3, więc i może coś konkretnego z tego wyjdzie.
Po zastosowaniu reszty uwag kod mógłby wyglądać mniej więcej tak:
#define BUF 64 /* dlugosc bufora */
char bufor[BUF];
char *wo=bufor; /* wskaznik odczytu */
char *wz=bufor; /* wskaznik zapisu */
#define FLAGA_PRZEPELNIENIE 1
volatile unsigned char flagi = 0;
/* funkcja wywolywana przez przerwanie po odebraniu znaku */
void zapisz_znak(char c) {
char *kopia_wz;
kopia_wz = wz+1;
if(kopia_wz == bufor[BUF]) { /* jezeli wskaznik "wyjechal" za koniec bufora */
kopia_wz = bufor; /* przeskok na poczatek
}
if(kopia_wz == wo) { /* wskaznik zapisu pokryje sie ze wskaznikiem odczytu - przepelnienie bufora */
flagi |= FLAGA_PRZEPELNIENIE;
return;
}
wz = kopia_wz;
*wz = c;
}
int czytaj_znak(void) {
int c;
if(wo != wz) { /* wskazniki rozne - cos jest w buforze */
c = *wo;
cli(); /* patrz opis */
wo++;
if(wo == bufor[BUF]) { /* jezeli wskaznik "wyjechal" za koniec bufora, patrz opis */
wo = bufor; /* przeskok na poczatek */
}
flagi &= ~FLAGA_PRZEPELNIENIE; /* bufor juz nie jest przepelniony */
sei();
return c;
}
return -1 /* bufor pusty */
}
Pojawia się jeszcze jeden problem. Jeżeli procedura zapisu do bufora wywoływana jest z przerwania, a odczytu z głównego programu, to może dojść do paskudnej sytuacji w wypadku, gdy procedura odczytu odczyta bajt i zmieni wartość wskaźnika wo. Jeżeli w tym momencie miało nastąpić "zapętlenie" wskaźnika i w tym momencie zostanie wywołane przerwanie, to procedura zapisu otrzyma fałszywą informację o położeniu wskaźnik odczytu. Podobnie z flagą przepełnienia bufora, po uaktualnieniu wskaźnika odczytu może zostać wywołane przerwanie, które zapełni bufor i ustawi flagę, a po wyjściu z przerwania flaga ta zostanie wyzerowana przez dalszą część procedury odczytu. Dlatego koneiczne wykonanie jest tych operacji w sposób uniemożliwiający operowanie na niepełnych danych. Najprościej jest wyłączyć na moment przerwania, ale nie zawsze tak można i wtedy trzeba kombinować. Myślę że w Twoim przypadku wyłączenie przerwań w zupełności wystarczy.
Konstrukcja
if(wo == bufor[BUF]) mimo odwołania do nieistniejącego elementu tablicy, jest prawidłowa. Standard C gwarantuje poprawność arytmetyki na wskaźniku na taki element.
Ilość danych zgromadzonych w takim buforze można policzyć tak:
n = (wz - wo) % DLUGOSC;
Podobnie jak wcześniej, operację modulo można zastąpić operacją AND. Właściwie to nawet trzeba, bo efektem działania operatora '%' w C nie jest wynik operacji modulo, tylko reszta z dzielenia. Reszta ta ma znak taki sam jak operator po lewej stronie. Można też użyć konstrukcji warunkowych - zmienić znak na przeciwny jeżeli różnica będzie ujemna.
Wbrew pozorom, wielkość ta jest mało przydatna, w większości wypadków wygodniej i wydajniej robi się wszystko na wskaźnikach.
), bardziej interesuje mnie sam schemat działania. Nie wiem np. czy czekać na ramkę az przyjdzie w całości i dopiero wtedy ją przetwarzać, czy może przetwarzać ją w momencie kiedy przychodzi - "bajt by bajt". O ile nie będzie to problemem to proszę również o określenie wad i zalet poszczególnych algorytmów (rozwiązań).
