Język C - Zawijanie indeksu tablicy

ARTYKUŁ W TRAKCIE TWORZENIA

CZYTASZ NA WŁASNE RYZYKO

:-)

Autor: BlueDraco
Redakcja: Dondu

Kurs języka C: Tips & Tricks - Spis treści

Bardzo często mamy w programie potrzebę „zawinięcia” indeksu tablicy, czyli spowodowania, by po dojściu do końca tablicy indeks „przeskoczył" na jej początek. Korzystamy z tego m.in. przy obsłudze mulipleksowanych wyświetlaczy LED oraz przy realizacji wszelkich buforów cyklicznych.

Najbardziej ogólne i uniwersalne rozwiązanie programowe polega na zdefiniowaniu rozmiaru wektora jako stałej preprocesora i zadeklarowaniu bufora oraz indeksu, na przykład tak:

#define BUF_SIZE 8

unsigned int buf[BUF_SIZE];
unsigned int idx;

Musimy przy tym oczywiście zwrócić uwagę, by typ użyty dla indeksu umożliwiał zapisanie wartości z zakresu od 0 do BUF_SIZE – 1, czyli przy BUF_SIZE nie przekraczającym 256 wystarczy unsigned char, a dla większych rozmiarów powinniśmy użyć typu unsigned int.

Dostęp do kolejnego elementu wektora i modyfikacja indeksu mogą wyglądać np. tak:

x = buf[idx ++];

Po czym zaraz powinno nastąpić zawinięcie indeksu, co najprościej zapisać tak:

idx %= BUF_SIZE;

Zapis ten jest bardzo prosty i czytelny - idx zyskuje wartość będącą resztą z dzielenia bieżącej wartości przez BUF_SIZE, czyli wartość BUF_SIZE zostaje zamieniona w wartość 0.

Warto jednak  przyjrzeć się bliżej tej prościutkiej instrukcji i zdać sobie sprawę z konsekwencji jej użycia, które silnie zależą od wartości stałej BUF_SIZE.

Zacznijmy od zauważenia, że jeśli BUF_SIZE ma wartość 256, a idx jest typu unsigned char, to instrukcja „zawijająca” indeks staje się całkowicie zbędna, gdyż w wyniku samej inkrementacji 8-bitowej danej o wartości 255 uzyskujemy wartość 0.

Jeżeli BUF_SIZE jest potęgą dwójki (np. 4, 8, 16, 32 itd.), to dobry kompilator zamieni naszą instrukcję

idx %= BUF_SIZE;

na równoważny jej zapis

idx &= BUF_SIZE – 1;

Czyli np. zamiast

idx %= 4;

kompilator wykona operację

idx &= 3;

Jeśli nasze zaufanie do zdolności optymalizacyjnych kompilatora jest ograniczone, możemy wyręczyć kompilator zapisując instrukcję jawnie w postaci iloczynu logicznego.

Co się stanie, gdy rozmiar bufora nie będzie potęgą dwójki?
Po prostu kompilator nie zoptymalizuje operacji zawinięcia według pokazanego powyżej schematu i wykona dzielenie zgodnie z zapisem programu, przypisując do zmiennej idx wartość reszty z tego dzielenia.

Programista powinien zdawać sobie sprawę z kosztu tej operacji. Jeśli procesor nie ma instrukcji dzielenia, dzielenie jest realizowane przez procedurę programową, a jego czas jest porównywalny z czasem wykonania od kilkudziesięciu do nawet kilkuset dodawań. Z taką sytuacją mamy do czynienia w niemal wszystkich mikrokontrolerach 8-bitowych (w tym AVR i PIC), ale również w 32-bitowym rdzeniu Cortex-M0. Nawet w procesorach używanych w komputerach PC czas operacji dzielenia liczb całkowitych jest porównywalny z czasem kilkunastu dodawań.

Jeśli więc nie chcemy przeciążyć naszego mikrokontrolera zbędnym w tym przypadku dzieleniem, powinniśmy napisać:

if (idx == BUF_SIZE) idx = 0;

która to sekwencja na typowym mikrokontrolerze 8-bitowym, ale również na 32-bitowych Cortexach-M0 wykona się szybciej, niż np.

idx %= 23;

Co prawda nasza strona jest poświęcona mikrokontrolerom, ale wypada wspomnieć, że w przypadku procesorów x86 stosowanych w PC wcale nie jest oczywiste, które z tych rozwiązań jest szybsze – odgrywa tutaj rolę wiele złożonych czynników.

---

Przykłady

Poniżej kilka przykładów dostępnych w kompilatorze CManiak, który powinien być w tej chwili widoczny w lewym górnym rogu przeglądarki. Możesz uruchamiać oraz modyfikować przykłady we własnym zakresie, aby poćwiczyć zawijanie indeksów.

Przykład 1:

Obliczenie kwadratów liczb na bazie indeksu tablicy i zapisanie wyniku ich do tablicy pod odpowiadającym mu indeksem.

#include <stdio.h>
int main(void){
  
  #define BUF_SIZE 8 
  
  unsigned int buf[BUF_SIZE];  
  unsigned int idx; 
  
  //oblicz kwadraty kolejnych liczb i zapisz w tablicy
  idx = 0;
  while(idx < BUF_SIZE) buf[idx++] = idx * idx;  //idx do kwadratu

  //pokaż wyniki zapisane w tablicy  
  idx = 0;
  while(idx < BUF_SIZE) {
    printf("idx[%d] = %d \n", idx, buf[idx]);
    idx++;
  }
  
  return 0;
}

Przykład 2:

Przykład podobnie jak powyższy liczący kwadraty liczb, lecz wyświetlający wielokrotnie zawartość tablicy począwszy od wybranej komórki.

#include <stdio.h>
#include <stdio.h>

int main(void){
    
  #define BUF_SIZE   8 
  unsigned int buf[BUF_SIZE];  
  unsigned int idx; 

  //wypełniamy tablicę wartościami kwadratu idx
  //oraz pokaż wyniki zapisane w tablicy  
  printf("Tablica wypełniona - stan początkowy: \n");
  for(idx=0; idx<BUF_SIZE; idx++){
    buf[idx] = idx * idx;
    printf("tab[%d] = %d \n", idx, buf[idx]);
  }

  //Wyświetalmy tablicę począwszy od wybranej komórki 
  //wykonując X zadanych kroków
  //po natrafieniu na koniec tablicy zawijamy indeks, by kolejne
  //komórki tablicy pokazywać od jej poczatku
  printf("\nElementy pokazane począwszy od wybranego: \n");
  
  #define ILOSC_KROKOW    18
  #define KOMORKA_POCZATKOWA   3

  idx = KOMORKA_POCZATKOWA;
  unsigned int krok =  0;
  while(krok++ < ILOSC_KROKOW) {
    printf("krok=%-3d tab[%d]=%d \n", krok, idx, buf[idx]);
    idx++;
    idx %= BUF_SIZE;    //zawiń indeks
  }

  return 0;
}

Kurs języka C: Tips & Tricks - Spis treści

40