Frage zu "Ringpuffer"

[Janiiix3]

Hallo,

Kurze Frage : tmphead = ( UART_RxHead + 1) & UART_RX_BUFFER_MASK(32);

Kann doch nur den Wert "32" enthalten oder sehe ich das falsch?



CodeBox C

ISR (UART0_RECEIVE_INTERRUPT)   
/*************************************************************************
Function: UART Receive Complete interrupt
Purpose:  called when the UART has received a character
**************************************************************************/
{
  unsigned char tmphead;
  unsigned char data;
  unsigned char usr;
  unsigned char lastRxError;
  /* read UART status register and UART data register */
  usr  = UART0_STATUS;
  data = UART0_DATA;
   
  /* */
#if defined( AT90_UART )
  lastRxError = (usr & (_BV(FE)|_BV(DOR)) );
#elif defined( ATMEGA_USART )
  lastRxError = (usr & (_BV(FE)|_BV(DOR)) );
#elif defined( ATMEGA_USART0 )
  lastRxError = (usr & (_BV(FE0)|_BV(DOR0)) );
#elif defined ( ATMEGA_UART )
  lastRxError = (usr & (_BV(FE)|_BV(DOR)) );
#elif defined( AT90USB_USART )
  lastRxError = (usr & (_BV(FE1)|_BV(DOR1)) );
#endif
   
  /* calculate buffer index */
[B]  tmphead = ( UART_RxHead + 1) & UART_RX_BUFFER_MASK(32);[/B]
   
  if ( tmphead == UART_RxTail ) {
  /* error: receive buffer overflow */
  lastRxError = UART_BUFFER_OVERFLOW >> 8;
  }else{
  /* store new index */
  UART_RxHead = tmphead;
  /* store received data in buffer */
  UART_RxBuf[tmphead] = data;
  }
  UART_LastRxError |= lastRxError;   
}

CodeBox C

unsigned int uart_getc (void)
{   
  unsigned char tmptail;
  unsigned char data;


  if ( UART_RxHead == UART_RxTail ) {
  return UART_NO_DATA;  /* no data available */
  }
   
  /* calculate /store buffer index */
  tmptail = (UART_RxTail + 1) & UART_RX_BUFFER_MASK;
  UART_RxTail = tmptail;
   
  /* get data from receive buffer */
  data = UART_RxBuf[tmptail];
   
  data = (UART_LastRxError << 8) + data;
  UART_LastRxError = 0;

  return data;

}/* uart_getc */

 

[Dirk]

Kurze Frage : tmphead = ( UART_RxHead + 1) & UART_RX_BUFFER_MASK(32);

Kann doch nur den Wert "32" enthalten oder sehe ich das falsch?

Wieso?

Wir müssten wissen, wie UART_RX_BUFFER_MASK definiert ist, so kann man kaum was dazu sagen.

Hier gehts anscheinend um den Buffer-Index und dieser wird durch die UND-Verknüpfung begrenzt, so dass der Index nicht die Größe-1 des Buffer-Arrays überschreiten kann. Die Maske müsste also Größe-1 sein. Ich vermute mal 32 Byte Größe-> Maske 32-1=31 = 0x1F = 0b11111.

 

[Janiiix3]

Ja genau, ist mit "32" deklariert.

Wenn ich jetzt aber "1" und "32" VERUNDE... Komme ich auf "0" Wie kann das dann eine Art "Begrenzung" sein?

 

[Dirk]

Wenn ich jetzt aber "1" und "32" VERUNDE... Komme ich auf "0" Wie kann das dann eine Art "Begrenzung" sein?

Wo wird denn mit 32 "verundet"? Warum wird dann nicht einfach geschrieben ergegbis = sonstwas & 32?

Es wird sicherlich mit (32-1) "verundet" 31 ist 0x1F, "verunde" damit mal. Und das Makro (welches ich wir noch nicht kennen) wird wahrscheinlich als Parameter Buffer-Size bekommen und zieht davon 1 ab.

 

[Janiiix3]

Warum so kompliziert?
Reicht da nicht eine "if Abfrage"?

 

[Dirk]

Warum so kompliziert?
Reicht da nicht eine "if Abfrage"?

Es nicht kompliziert, der erzeugte Code wird auch sehr kurz sein, ggf. genauso aussehen wie mit If-Abfrage und da müsstest du eigentlich auch den Autor des Sourcecodes fragen, warum er eine & Verknüpfung mit der Maske (konstanter Wert) verwendet und nicht eine if-Abfrage. Ich habe den Sourcecode nicht genau angesehen, es könnte sein, dass die Zeile nicht nur den Index nach oben begrenzt, sondern es kommt hier zum Überlauf des Index, dieser fängt wieder von unten an, was ja bei einem Ringbuffer eventuell sinnvoll ist ... insofern eleganter als mit if-Abfrage zu arbeiten

 

[TommyB]

/sign.

Ich würds genau so machen, zumindest wenn nur einzelne Bytes verarbeitet werden, da man sich so viele Abfragen einspart. Bei einem Ringpuffer brauchst du eine Schreib- und eine Leseposition, und natürlich einen Buffer von x Bytes. Daher ist es Clever ein ^2 Wert wie 16, 32, 64, … Bytes zu nehmen da man eben mit dem AND sich die Abfrage des Überlaufes erspart (weniger CPU Instruktionen -> schnellerer und kleinerer Code). Weil was passiert? Beispiel mit 4 Byte:
Addr: 00000000 + 1
Addr: 00000001 + 1
Addr: 00000010 + 1
Addr: 00000011 + 1
Addr: 00000100

Das rote wird weg gerechnet durch das AND, der Überlauf passiert somit automatisch. Keine Abfragen benötigt. Voraussetzung hierfür ist aber dass der Puffer 2, 4, 8, 16, 32, 64, 128, … Bytes groß ist, mit Zwischenwerten geht das nicht. Dann nur per If Abfragen.

 

[Janiiix3]

/sign.

Ich würds genau so machen, zumindest wenn nur einzelne Bytes verarbeitet werden, da man sich so viele Abfragen einspart. Bei einem Ringpuffer brauchst du eine Schreib- und eine Leseposition, und natürlich einen Buffer von x Bytes. Daher ist es Clever ein ^2 Wert wie 16, 32, 64, … Bytes zu nehmen da man eben mit dem AND sich die Abfrage des Überlaufes erspart (weniger CPU Instruktionen -> schnellerer und kleinerer Code). Weil was passiert? Beispiel mit 4 Byte:
Addr: 00000000 + 1
Addr: 00000001 + 1
Addr: 00000010 + 1
Addr: 00000011 + 1
Addr: 00000100

Das rote wird weg gerechnet durch das AND, der Überlauf passiert somit automatisch. Keine Abfragen benötigt. Voraussetzung hierfür ist aber dass der Puffer 2, 4, 8, 16, 32, 64, 128, … Bytes groß ist, mit Zwischenwerten geht das nicht. Dann nur per If Abfragen.

@TommyB

Vielen Dank. Super erklärt.
Das war auch noch ein großes "Rätzel" wie man es dann mit "krummen" Werten machen sollte, in der (fertigen) Library steht davon kein Wort erwähnt das man nur ^2 Werte nehmen kann / darf.

Also wenn man den Quellcode nicht liest und irgendeinen krummen Wert einträgt, wird es nicht klappen.

Vielen dank an euch.

Macht es bei einer Seriellen Kommunikation wie z.B "RS232", Sinn einen Ringbuffer zu programmieren?

 

[Dirk]

Macht es bei einer Seriellen Kommunikation wie z.B "RS232", Sinn einen Ringbuffer zu programmieren?

Es macht zum Beispiel dann Sinn, wenn du die Daten nicht schnell genug bearbeiten kannst (geht nur begrenzte Zeit, da der Buffer sonst überläuft) oder auf mehrere Daten warten musst, um diese erst sinnvoll verarbeiten zu können.

 

[Janiiix3]

Wie baut man solch einen "Puffer" sinnvoll auf? Mehre Funktionen? Globale Variablen?

 

[TommyB]

Macht es bei einer Seriellen Kommunikation wie z.B "RS232", Sinn einen Ringbuffer zu programmieren?

Das kommt auf den Anwendungsfall an, prinzipiell aber ja. Wenn du die Kommunikation in einem Byte abarbeiten kannst brauchst du das garnicht, sonst lohnt es sich schon, grade wenn du Befehle mit unterschiedlicher Länge hast. Beispiel: Empfang per UART, Ausgabe auf LCD, nehmen wir übertrieben mal 4x80 Zeichen, macht 321 Bytes (320 für den String, 1 für Befehl) die du als festen Buffer reservieren müsstest. Oder du nutzt einen Ring Puffer von sagen wir 16 Bytes. Byte 1 sagt auf LCD schreiben, die folgenden Bytes sagen was geschrieben werden soll. So kannst du während des Empfangens schon die Daten an das LCD schicken.

Anderes und womöglich besseres Beispiel, allerdings aus der PC Welt. Es gibt ja diese RS232-zu-USB Wandler. Wenn man von denen Daten liest bekommt man mal 1 Byte, mal 3, dann vielleicht 4 und wieder 1… obwohl 64 Bytes auf ein mal gesendet wurden. Sprich: Du musst die Daten erst sammeln bevor du sie komplett verarbeiten kannst. Da die Anzahl der Bytes aber variieren kann (pro Paket) muss der Buffer nur so groß sein wie das was du zum Arbeiten brauchst. Außerdem, was viele falsch (oder besser verbesserungsfähig) machen: Dynamische Buffer zu verwenden (hab ich selber auch gemacht, Schande über mich). Was passiert?
3 Bytes empfangen -> Windows reserviert 3 Bytes Arbeitsspeicher und kopiert die Daten hinein
1 Byte empfangen -> Buffer zu klein, Windows reserviert 4 Bytes Speicher, kopiert die 3 Bytes hinein, fügt das neue Byte hinzu, gibt den 3 Bytes Speicher wieder frei
…
Jetzt haste genug Daten, also
Die ersten 14 Bytes verarbeiten und aus dem Puffer löschen -> Windows reserviert x-14 Bytes Arbeitsspeicher und kopiert den Überschuss aus dem alten Buffer in den Neuen und gibt den alten Speicher frei.

Wie du siehst, jede Menge an Operationen die „under the hood“ ablaufen und unnötig CPU (und somit auch Strom) kosten. Bei einem AVR könnte das möglicherweise zu einer Orgie von rumgepoppe und rumgepushe führen.

Bei einem Ringpuffer musst du nur drauf achten dass er mindestens so groß ist dass du die Daten verarbeiten kannst, bissl mehr schadet nie. Der Speicher bleibt immer der Selbe, du hast nur Cursor / Pointer für Lese- und Schreibposition. So in der Art funktioniert auch jede Soundkarte. WinAmp2 hat das damals auch angezeigt in den Optionen irgendwo. Zu lange her dass ich das verwendet habe.

 

[Janiiix3]

Ich glaube da ist noch ein grober Denkfehler drinn was den letzten Eintrag angeht?!



CodeBox C

#define MAX_BUFFER_VALUE   32

#define MAX_BUFFER_VALUE_MASK (MAX_BUFFER_VALUE - 1)

#define BUFFER_OVERFLOW     1
#define STORE_SUCCESSFULLY   0

typedef struct  
{
   static volatile uint8_t Last_Index;
   volatile     uint8_t Buffer[16];
   static volatile uint8_t   Index_Cnt;
}circle_Buffer;


uint8_t circle_buffer_write(uint8_t data)
{
   if (circle_Buffer.Index_Cnt > MAX_BUFFER_VALUE_MASK)
   {
     return BUFFER_OVERFLOW;
   }
   circle_Buffer.Buffer[circle_Buffer.Index_Cnt++] = data;
   
   return STORE_SUCCESSFULLY;
}

uint8_t circle_buffer_read(void)
{
   circle_Buffer.Last_Index = circle_Buffer.Index_Cnt;
   return (circle_Buffer.Buffer[circle_Buffer.Last_Index]);
}

 

[TommyB]

Wenn ich das jetzt richtig deute ist das definitiv kein circle buffer. Bin aber bei C nicht so bewandert. @Dirk?
Und wo ist das AND?
Und warum mal 32 Byte, mal 16?

 

[Dirk]

@Dirk?

Ja, da kann ich leider nicht so helfen.

 

[LotadaC]

Also für mich sieht das eher nach einem LiFo-Stack aus. Ein Ringpuffer wäre ja hingegen ein FiFo-Stack. Allerdings C...

Macht es bei einer Seriellen Kommunikation wie z.B "RS232", Sinn einen Ringbuffer zu programmieren?

Das ist 'ne typische "Das kommt darauf an"-Frage, wie bereits angedeutet wurde.
In welcher Häufigkeit und Menge Bytes eintreffen, und wie oft und schnell Deine Programm die wegbearbeitet bekommt.
Letzteres hängt dann wiederum davon ab, ob der UART-Empfang über ein integriertes, weitgehend autarkes, Hardware-Modul läuft, oder ob die Software ein Bein im Auge behalten muß.
Die Software müßte auf jedes Bit reagieren, Die Hardware schaufelt ein komplettes "Byte" (kann 5, 6, 7, 8 oder 9 Datenbits) Byte weg, und setzt ein Signal.
Dann ist in der Hardware bereits FiFo-Puffer enthalten, drei "Bytes" groß (zwei "Bytes" UART Data Recieve Register, ein "Byte" Reciever Shift Register)

Das erste Byte wird ins Empfangs-Schieberegister eingeschoben/lesen.
Nach dem Stopbit wird es ins UART-Datenregister übertragen (wenn dieses nicht voll ist), währenddessen...
Das zweite Byte wird ins Empfangs-Schieberegister eingeschoben/lesen.
Nach dem Stopbit wird es ins UART-Datenregister übertragen (wie gesagt, zwei "Bytes" groß - stehen jetzt also zwei drin), währenddessen...
Das dritte Byte wird ins Empfangs-Schieberegister eingeschoben/lesen, kann aber nicht in's Datenregister übertragen werden, solange dieses voll ist.
Das Startbit des vierten "Bytes" würde das Data Overrun-Flag setzen.
Solange der Empfangspuffer nicht leer ist, ist das RecieveComplete-Flag gesetzt, welches den RecieveComplete-Interrupt triggern kann. Alternativ kannst Du das Flag auch selbst pollen.

Edit @TommyB : nach dem verANDen muß noch mit der Startadresse des Puffers verORt werden - 0x0000 darf es logischerweise nicht sein, da dort die Rechenregister und danach die I/O-Register kommen. Sinnvoll ist die Verwendung von Load/Store mit post-increment. Sofern man dabei kein(e) Pointerregister reservieren will, kann man 'ne feste Startadresse über das Highbyte ... ähm ... festlegen und immediate laden, wenn der Buffer 256 Bytes groß ist, entfällt das AND.
Reservierst Du Pointerregister, mußt die Adresse also selbst nicht aus dem SRAM laden, spuckt Dir das post-incremment beim Überlauf des Lowbytes des Adresszeigers in die ... Adresse. Genauer gesagt ins Highbyte, das wird nämlich mitincrementiert. wäre also dort ein LDI fällig.
AFAIK (!) wird das RAMPX/Y/Z-Register dabei nicht mitincrementiert, könnte man also ggf auch nutzen - allerdings hab ich mit derlei... opulenten Controllern noch nix gemacht -> mehr als 64kBytes SRAM... (jaja, jetzt würgste mir gleich einen rein, daß es dann kein Tiny mehr wär, oder so...)

 

[Dirk]

nach dem verANDen muß noch mit der Startadresse des Puffers verORt werden - 0x0000 darf es logischerweise nicht sein, da dort die Rechenregister und danach die I/O-Register kommen. Sinnvoll ist die Verwendung von Load/Store mit post-increment ...

?
Die UND Operation wird hier verwendet, um ein Überlauf zu erreichen für einen Wert des Index kleiner als 8Bit. Der Index adressiert das Array, dieser läuft in C von 0 bis ArraySize-1. Abgesehen von dem Softwareteil (ein paar Zeilen) für das UART Modul eines AVR Mikrocontrollers läuft der Code des RingBuffers auch auf anderen Controllerfamilien, auch auf dem PC. Dank der Hochsprache muss man sich keine Gedanken über Rechenregister und IO Register oder lds/sts, indirekte Adressierung mit x,y,z Registern und sowas machen. Der Compiler verwaltet auch den Speicherbereich von Variablen, also auch vom Array, wo das im SRAM liegt, ist normalerweise unwichtig.

 

[TommyB]

@LotadaC du denkst zu sehr Hardwarenah / in ASM
Bei Hochsprachen adressiert man ja Arrays von 0 bis Größe - 1, nicht nach Speicheradresse.
Daher war das schon so richtig wie ich das geschrieben hatte.

Pseudocode:

Do
    Buffer(Pos) = NewByte
    Pos += 1
    Pos = Pos AND 0b00001111
Loop

Das AND legt quasi bitweise die Überlaufsgrenze fest.

Es ging mir im letztem Post auch eher darum dass der Code für mich definitiv nicht nach einem Ringpuffer aussieht.

Und nö, mein momentaner Lieblingsspruch ist es immer noch dass du es auch schaffen würdest 2 Bytes im SREG zu speichern ^^

 

[LotadaC]

Ja Dirk, war schon richtig so. Mit diesem "Trick" läßt man den Array-Index in Zweierpotenzen überlaufen. In der Hochsprache wars das, die kümmert sich selbst drum, die Tatsächliche Startadresse des Arrays draufzuaddieren. Aus Performance-Sicht kann es aber durchaus 'n Unterschied machen, wo so ein Array im Speicher beginnt. Und da lassen sich garantiert Beispiele finden, die auch ein guter Compiler nicht optimiert. Im Prinzip war "AND" statt "IF" ja schon 'ne Optimierung, ich hab lediglich noch was dazugepackt. Aber das wird unter Hochsprachen keine Rolle spielen.

Thomas, eigentlich ist das mit den Arrays in ASM und Hochsprachen gleich. Der Arrayname ist die Startadresse, und dann eben soundso viele Einträge weiter (wobei man sich eben in ASM selbst ums ausrechnen der Adresse und die Beachtung der "Breite" eines Eintrages kümmern muß).

Egal...
zu Beitrag #12/#13:
da hab ich mich doch voll hinter Dich gestellt - beim Schreiben wird der Index inkrementiert, und das Datum(?) dahingeschrieben (mit Kontrolle auf Pufferübarlauf, aber mMn eins zu spät).
Beim Lesen wird das letzte Datum (größter Index) geladen. Wäre da noch ein decrement des Index, sähe das eben wie ein klassischer Stack aus. LiFo. Last In First Out.
'n Ringpuffer müßte aber FiFo sein - eben mit zwei (internen) Zeigern. First In, First Out.
Aber vielleicht sehen wir zwei beide das bloß im Code da oben nicht.
@Dirk ??

 

[Dirk]

Also ich finde Assembler ja selber gut. Aber möglicherweise irritiert es jemand, wenn es um eine Hochsprache geht und jemand anderes von assembler-spezifischen Sachen erzählt. Übrigens, der GCC Compiler optimiert schon sehr gut, besser als du wahrscheinlich denkst.

Und wegen dem RingBuffer, da habe ich jetzt doch mal etwas rausgesucht.

Hier ist ein RingBuffer, den ich in der Vergangenheit in mehreren Projekte eingesetzt habe.

Damit der RingBuffer "interrupt-sicher" ist, greife ich auf das Statusregister SREG des AVR zu (ich verändere das I Flag, Global Interrupt Enable). Hier ist er also speziell für AVR Mikrocontroller, das lässt sich aber ganz schnell verallgemeinern.

In einem Projekt habe ich den RingBuffer zum Beispiel doppelt verwendet, für die Datenkanäle RXD und TXD zwischen einem USB CDC Device (virtueller COM port) und USART Modul (praktisch eine USB UART Bridge in einem AVR Mikrocontroller realisiert).

Die Funktion _InitBuffer muss zunächst ausgeführt werden, alle anderen Funktionen dürften selbsterklärend sein.

Die Größe in Byte stellt man mit RBUFSIZE ein.

Dirk



CodeBox C

#include <avr/interrupt.h>
#include <stdbool.h>

#define RBUFSIZE 128

typedef struct
{
   uint8_t In;  /**< Current storage location in the circular buffer. */
   uint8_t Out;  /**< Current retrieval location in the circular buffer. */
   uint16_t Size;  /**< Size of the buffer's underlying storage array. */
   uint16_t Count;  /**< Number of bytes currently stored in the buffer. */
} RingBuffer_t;

RingBuffer_t RingBufferInfo1;

uint8_t RingBuffer1[RBUFSIZE];

void RingBuffer1_InitBuffer(void)
{

   uint8_t int_reg = SREG;
   cli();

   RingBufferInfo1.In  = 0;
   RingBufferInfo1.Out = 0;
   RingBufferInfo1.Size = RBUFSIZE;
   RingBufferInfo1.Count = 0;

   SREG = int_reg;

}

uint16_t RingBuffer1_GetCount(void)
{

   uint8_t Count;

   uint8_t int_reg = SREG;
   cli();

   Count = RingBufferInfo1.Count;

   SREG = int_reg;

   return Count;
}

uint16_t RingBuffer1_GetFreeCount(void)
{

   return (RingBufferInfo1.Size - RingBuffer1_GetCount());

}

bool RingBuffer1_IsEmpty(void)
{

   return (RingBuffer1_GetCount() == 0);

}


bool RingBuffer1_IsFull(void)
{

   return (RingBuffer1_GetCount() == RingBufferInfo1.Size);

}

void RingBuffer1_Insert(uint8_t data)
{

   RingBuffer1[RingBufferInfo1.In] = data;

   RingBufferInfo1.In++;

   if (RingBufferInfo1.In == RingBufferInfo1.Size)
   RingBufferInfo1.In = 0;
 
   uint8_t int_reg = SREG;
   cli();

   RingBufferInfo1.Count++;

   SREG = int_reg;

}

uint8_t RingBuffer1_Remove(void)
{

   uint8_t data;

   data = RingBuffer1[RingBufferInfo1.Out];

   RingBufferInfo1.Out++;

   if (RingBufferInfo1.Out == RingBufferInfo1.Size)
   RingBufferInfo1.Out = 0;

   uint8_t int_reg = SREG;
   cli();

   RingBufferInfo1.Count--;

   SREG = int_reg;

   return data;

}

uint8_t RingBuffer1_Peek(void)
{

   return (RingBuffer1[RingBufferInfo1.Out]);

}

 

[Janiiix3]

Hallo Dirk,

deine Lösung ist ganz verständlich.
Es sei ja angeblich viel besser mit einem & zu arbeiten, was dass überlaufen anbetrifft. Hattest du da einfach nicht dran gedacht, dass das effektiver ist oder hat das einen besoderen Grund?

Was das Thema "Interrupt" angeht, reicht es nicht wenn man die Variable mit static & volatile betitelt?

Und was deine Routinen anbelangt...

Hiermit schreibe ich den Buffer rein, das ist soweit klar



CodeBox C

void RingBuffer1_Insert(uint8_t data)

Und mit der Routine lese ich immer den ältesten Eintrag aus?



CodeBox C

uint8_t RingBuffer1_Remove(void)