Forum: Mikrocontroller und Digitale Elektronik FIFO Implementierung (Array vs Pointer)


von Felix (Gast)


Lesenswert?

Hi

Ich möchte einen FIFO für den UART bauen. Habe das auch mit Arrays 
hinbekommen, bin aber am Grübeln, ob das "optimal" ist, oder ihr eher 
vorschlagt mit Pointern & Co zu hantieren. Wenn, wieso? Oder ganz anders 
und viel schneller?

Hier die relavanten Codeschnipsel meiner Implementierung:



uart.h:

BYTE FIFO_UART[SIZE_UART_SENDBUFFER];
BYTE UART_GET_INDEX;  //need to be global
BYTE UART_PUT_INDEX;  //need to be global

...

//Funktionsprototypen
void PUT_UART(BYTE);
BYTE GET_UART(void);



uart.c:

#include "uart.h"

...

void PUT_UART(BYTE Sendbyte){
  //write data to fifo
  FIFO_UART[UART_PUT_INDEX]=Sendbyte;
  //increment index for next wite access
  if (UART_PUT_INDEX < SIZE_UART_SENDBUFFER)  UART_PUT_INDEX++;
  else  UART_PUT_INDEX = 0;
};


BYTE GET_UART(){
  BYTE temp;  //will be lost after function execution
  //save data for return:
  temp = FIFO_UART[UART_GET_INDEX];
  //increment index for new read access
  if (UART_GET_INDEX < SIZE_UART_SENDBUFFER)  UART_GET_INDEX++;
  else  UART_GET_INDEX = 0;
  return temp;
};



Mich stört dass immer eine Funktion aufgerufen werden muss, in der eine 
oder 2 lokale Variablen angelegt werden müssen. Das kostet 
wahrscheinlich recht viel Zeit!?

Vielen Dank schonmal für eure Tips
Felix

von Karl H. (kbuchegg)


Lesenswert?

> Das kostet wahrscheinlich recht viel Zeit!?

Nicht wirklich.
lokale Variablen anlegen geschieht dadurch, dass der
Stackpointer manipuliert wird. Ob das eine oder zwei
oder hundert sind, spielt keine Rolle.

Pointer würden deinen Code weder wesentlich kleiner noch
schneller machen. Alles was du dir sparst, ist bei der
Indizierung

  FIFO_UART[UART_PUT_INDEX]

eine Addition. Allerdings erkauft man sich die durch eine
aufwändigere Pointer Inkrementierung bzw. Erkennung des
ArrayEndes. In Summe: Ich denke nicht, dass das schneller wäre.


BYTE FIFO_UART[SIZE_UART_SENDBUFFER];
BYTE* EndOfFifo = FIFO_UART + SIZE_UART_SENDBUFFER;
BYTE* NextPut;

void PUT_UART(BYTE Sendbyte){
  //write data to fifo
  *NextPut = Sendbyte;

  //increment index for next wite access
  NextPut++;
  if( NextPut == EndOfFifo )
    NextPut = FIFO_UART;
}

Du siehst: Da ändert sich nichts wesentliches.

An deiner Stelle würde ich mich lieber darum kümmern,
dass der FIFO abgesichert wird:
* PUT kann nicht Daten, die noch nicht von einem GET gelesen
  wurden, einfach überschreiben
* GET kann nicht Daten lesen, die noch nicht von einem PUT
  geschrieben wurden

Im Moment ist bei deinen Routinen beides möglich.

von Ale (Gast)


Lesenswert?

Etwas wie ?

(Warum nicht 2 buffers ?)

BYTE fifo_putbuff[SIZE_UART_SENDBUFFER];
BYTE fifo_getbuff[SIZE_UART_SENDBUFFER];
BYTE *fifo_putptr = fifo_putbuff;  //need to be global
BYTE *fifo_getptr = fifo_getbuff;  //need to be global

...

//Funktionsprototypen
void put_uart(BYTE);
BYTE GET_UART(void);

uart.c:

#include "uart.h"

...

void put_uart(BYTE sendbyte){
  //write data to fifo
  *fifo_putptr++ = sendbyte;
  if (fifo_putptr >= (fifo_pubuff + SIZE_UART_SENDBUFFER))
    fifo_putptr = fifo_pubuff;
};

****

Variables im Groß es ist keine gute Idee (nur Konstanten, Macros), auch 
Funktionennamen,

von Karl H. (kbuchegg)


Lesenswert?

Deine lokale Variable im Get kannst du übrigens loswerden,
indem du die Rolle des GetIndex umdefinierst:

GetIndex enthält nicht mehr den Index von dem als nächstes
gelesen werden soll, sondern von dem zuletzt gelesen wurde.
Damit ist die erste Aktion in der Get Funktion das Erhöhen
des Index

BYTE GET_UART(){
  //increment index for new read access
  if (UART_GET_INDEX < SIZE_UART_SENDBUFFER)
    UART_GET_INDEX++;
  else
    UART_GET_INDEX = 0;

  return FIFO_UART[UART_GET_INDEX];
};

Ale hat übrigens recht. Alles in Grossbuchstaben ist wirklich
keine gute Idee. Namen in Grossbuchstaben werden praktisch
ausschliesslich für Makros verwendet. Das ist zwar nur eine
Konvention, allerdings ist es eine Konvention an die sich
seltsamerweise praktisch alle C-Programmierer halten.
Davon abzuweichen heist: Konfusion heraufbeschwören.

von Peter D. (peda)


Lesenswert?

Felix wrote:

> Ich möchte einen FIFO für den UART bauen. Habe das auch mit Arrays
> hinbekommen, bin aber am Grübeln, ob das "optimal" ist, oder ihr eher
> vorschlagt mit Pointern & Co zu hantieren.

Kommt drauf an.

Wenn die Feldgröße 256 Byte nicht überschreitet, braucht ein Index 
weniger Speicher und ist schneller als ein Pointer, da ja nur ein Byte 
belegt wird.

Sonderfall, wenn die Größe genau 256 Byte ist, brauchst Du nicht mal nen 
Array-Ende-Test, das mach das Index-Byte vollautomatisch.

Bzw. bei Größen von 128, 64, 32 Byte usw., AND-iert man einfach die 
oberen Bits weg.


Peter

von Andreas S. (andreas) (Admin) Benutzerseite


Lesenswert?

Solche Tricks sollte man aber nur verwenden wenn es wirklich nötig ist - 
sonst sitzt man am Ende mit einem Haufen Code da der viel zu schnell, 
aber völlig undurchsichtig ist.

von A.K. (Gast)


Lesenswert?

Wenn die Index-Rechnung "unsigned" erfolgt, dann sollte jeder brauchbare 
Compiler aus einer Modulo-Operation mit 2^N schon selber eine einfache 
AND-Operation machen, die manuelle Optimierung ist dann überflüssig. 
Ähnlich ist es mit 256 Bytes, auch hier sollte man die Optimierung eher 
dem Compiler überlassen.

Wobei Rechnungen mit "unsigned char" als "int", also mit Vorzeichen 
durchgeführt werden, und diese AND-Optimierung dann nicht so einfach 
ist. Es kann also sinnvoll sein, explizit nach "unsigned" zu casten:
   index = (unsigned)(index + 1) % BUFSIZE;

Optimierung von Datentypen lässt sich recht ubersichtlich 
bewerkstelligen, indem man dort wo die Grösse des Puffers festgelegt 
wird, auch gleich den passenden "typedef" für die Index-Variablen 
unterbringt:
  #define UART_BUFSIZE 100
  typedef unsigned char uart_index_t;
Man vermeidet so spätere Probleme.

von Felix (Gast)


Lesenswert?

Hej Jungs ihr seid super

Viele Gute Tips - danke. Hab das mal soweit ich konnte umgesetzt. Diese 
verunderei mit den Indexvariablen habe ich genutzt, um schön den Inhalt 
des FIFOs zu berechnen. Allerdings scheint die Optimierung, wie A.K. sie 
vorschlägt nicht zu funktionieren (BYTE ist unsigned und gecastet hab 
ich, wo's nur geht), denn ob ich als SIZE_UART_SENDBUFFER eine Potenz 
von 2 eingebe oder nicht, ist der Codegröße völlig egal! Dabei sollte ja 
bei einer zweierpotenz als Größe des Buffers ein kleinerer Code 
rauskommen, weil, wie Peter schrieb, dann der "Array-Ende-Test" 
optimiert werden kann. Muss ich dafür im AVR Studio eine bestimmte 
Optimierung eingeben (O0, O1... oder Os??) Bei mir hat das zwar extremen 
Einfluss auf die Codegröße im Allgemeinen, sie ist aber in jedem Fall 
unabhängig von SIZE_UART_SENDBUFFER.

Hier kommt stolz mein neuer Code für die beiden Routinen. Kommentare 
sind natürlich nochmal erwünscht!



void put_uart(BYTE sendbyte){
  cli();
  //write payload to send_fifo
  fifo_uart[uart_put_index]=sendbyte;
  //increment index for next wite access
  if (uart_put_index < SIZE_UART_SENDBUFFER-1) 
(unsigned)uart_put_index++;
  else  uart_put_index = 0;
  content_uart_fifo=(unsigned)(uart_put_index-uart_get_index-1)&(SIZE_UART 
_SENDBUFFER-1);
  if (content_uart_fifo==0) content_uart_fifo=SIZE_UART_SENDBUFFER; 
//FIFO is full!!!
  sei();
};


BYTE get_uart(){
  cli();
  //increment index before read access
  if (uart_get_index < SIZE_UART_SENDBUFFER-1) 
(unsigned)uart_get_index++;
  else  uart_get_index = 0;
  content_uart_fifo=(unsigned)(uart_put_index-uart_get_index-1)&(SIZE_UART 
_SENDBUFFER-1);
  sei();
  return fifo_uart[uart_get_index];
};

von A.K. (Gast)


Lesenswert?

Compiler?

unsigned f(unsigned x)
{
    return (x + 1) % 64;
}

unsigned g(unsigned x)
{
    return (x + 1) % 100;
}

GCC:

f:  adiw r24,1
  andi r24,lo8(63)
  andi r25,hi8(63)
  ret

g:  adiw r24,1
  ldi r22,lo8(100)
  ldi r23,hi8(100)
  rcall __udivmodhi4
  ret

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.