UART Datenstrom mit Array vergleichen

Ich habe gerade einen Fehler entdeckt. Die durchgeführte Messung (7ms) 
stimmt nicht. Ich habe natürlich 7 Bytes auf dem UART Bus abgewartet, 
bis ich zu ende vergleichen habe.

Richtig ist:
Die Buffer Schieberei dauert 50µs und der Zeichenkettenvergleich dauert 
auch nochmal 55µs. Ist also alles im grünen bereich. Aber Euch fällt 
bestimmt eine schönere Vergleichvariante ein, oder?

Zusätzlich zu den 7 gespeicherten Daten könnte man noch ein Byte
spendieren, in dem der XOR-Wert aller eingetragenen Zeichen
hinterlegt ist (Parity-Byte).
Dieses Parity-Byte muß nicht bei jedem neuen Zeichen aus allen
7 neu berechnet werden, sondern es genügt mit dem alten
hinausgeworfenen Zeichen wieder einen XOR-Wert zu bilden, um
es auszutragen, ebenso mit dem neuen hinzugekommenen, um
dieses einzutragen.

Ebenfalls bildet man den XOR-Wert der Vergleichsfolge.
Wenn ich das richtig verstehe, ändert die sich ja nicht, also
muß deren Parity-Wert nur einmal bestimmt werden.

Durch diesen Mehraufwand hat man jederzeit das Parity-Byte
der Vergleichsfolge und das Parity-Byte der 7 Zeichen
aus dem Datenstrom.

Der Vorteil: es reicht als Vortest, diese beiden zu vergleichen.
Erst wenn die beiden Parity-Bytes gleich sind (was nur selten
vorkommen wird, genau genommen in 1/256 aller Fälle), könnte
ein Treffer vorliegen, und man vergleicht dann die Zeichen Byte
für Byte.

Unterm Strich (vermute ich) geht das deutlich schneller.

Die Idee ist genial, somit vergleicht man bei jedem ankommenden Byte nur 
2 Bytes... Jedoch könnte sich da wirklich ein Fehler einschleichen, 
weil:

Mein Datenstrom sieht z.B. so aus:


0x35, 0x56, 0x23, 0x67, 0x50, 0x23, 0x77  oder auch
0x35, 0x56, 0x23, 0x67, 0x23, 0x50, 0x77

Wenn ich die ersten 5 Bytes schon erfolgreich durch habe kommt beim 6ten 
Byte bei beiden Zeichenketten der gleiche XOR Wert heraus. Beim testen 
des 7ten Bytes würde ich dann gar nicht mehr wissen welche Zeichenkette 
von beiden es war.

Aber Deine Idee bleibt in meiner Sammlung als mögliche Methoden :c)

Noch eine Idee?

Bei einem solchen Dreher, bei dem zufällig der gleiche
XOR-Wert aus beiden Folgen kommt, käme dann der Notausgang
zum Zug und es müssten (wie ich bereits erwähnte) dann doch
alle 7 Bytes verglichen werden.
(Natürlich kann ich nicht in einem Byte die vollständige
Information von 7 Byte halten, das wäre eine tolle Kompression.)

Nur wird das halt nicht sehr häufig sein (bei zufälligen Daten
in weniger als 0.5% der Fälle).

Danke, Mmmh

Bei Deinem Link wird der Inhalt des Ringpuffers nicht verschoben, 
sondern mit IN und Out Pointern gearbeitet. Das würde das Abspeichern 
neuer Bytes etwas verkürzen, aber nicht das vergleichen.

Noch eine Idee?

Ahhh, verstehe... Am Schluss nochmal eine komplette Prüfung...

Danke, Klaus.

Kann man das Vergleichen vom Array irgendwie einzeilig lösen? z.B. so:?

if(memcmp(rx0_buffer, (0x35, 0x56, 0x23, 0x67, 0x50, 0x23, 0x77) , 6))

oder so:?

if(memcmp(rx0_buffer, "Test12" , 6))

Den Ringpuffer ständig zu rotieren, ist natürlich Verschwendung.
Eine Schleife von i=0...6 und Zugriff auf das Feld über
rx0_buffer(i+aktuellerOffset)%7 wäre in der Tat viel effizienter.

Außerdem legst du im Moment bei jedem Vergleich das lokale Feld
cmp_buffer neu an. Tut das Not?

mach das Feld mit den Vergleichswerten doch einfach static, dann
wird es nur einmal bei Programmstart angelegt.

Mmmh schrieb:
> Knuth-Morris-Pratt-Algorithmus

Hm, das ist ziemlich viel Code und lohnt sich vielleicht eher
bei längeren Texten?

>Außerdem legst du im Moment bei jedem Vergleich das lokale Feld
>cmp_buffer neu an. Tut das Not?


Ich werde ja 10 verschiedene Zeichenketten vergleichen. Im Moment weiss 
ich mir nicht anders zu helfen, als die erste Zeichekette in den 
cmp_buffer zu legen, vergleichen, dann die zweite Zeichenkette in den 
cmp_buffer zu legen und wieder vergleichen usw.

Das ist hier bei dem Beispielcode noch nicht sichtbar. Deshalb aber auch 
meine Frage, ob man den Vergleich von 10 verschiedenen Zeichenketten 
einzeilig lösen kann.

z.B.

if(memcmp(rx0_buffer, (0x35, 0x56, 0x23, 0x67, 0x50, 0x23, 0x77) , 
6))...
if(memcmp(rx0_buffer, (0x35, 0x78, 0x23, 0x67, 0x23, 0x50, 0x77) , 
6))...
if(memcmp(rx0_buffer, (0x66, 0x56, 0x23, 0x55, 0x50, 0x23, 0x87) , 
6))...
if(memcmp(rx0_buffer, (0x65, 0x56, 0x33, 0x67, 0x50, 0x10, 0x05) , 
6))...
.
.
.

>mach das Feld mit den Vergleichswerten doch einfach static, dann
>wird es nur einmal bei Programmstart angelegt.


Ja, ich habe die Puffer am Anfang deklariert:

unsigned char rx0_buffer[7];
unsigned char cmp_buffer[7];

Sie werden also nicht immer neu angelegt, sondern bei jedem Vergleich 
neu beschrieben.

>Knuth-Morris-Pratt-Algorithmus

Ja, in 6 Zeilen nur 6 Bytes zu verschieben ist schneller, als mit In und 
Out Pointern zu rechnen, das lohnt sich eher beim 128 Byte Puffer, wie 
in Peters Lib, aus der ich die Zeichen ja auch heraus hole.

Erstens: das mit memcmp macht eh keinen Sinn, weil du dafür
deinen Ringpuffer ingesamt rotieren müsstest, und das
ist wie mehrfach gesagt Unfug.
Sinnvoller wäre es, den Vergleich selbst zu schreiben; dann
kann man mit %7 in den Puffer fassen.

Zweitens: mach doch einmal ein Feld mit allen deinen
Vergleichsmustern, und vergleiche mal mit dem einen und mal
mit dem anderen Feldelement (was dann jeweils ein Zeiger auf
die 7 Zeichen ist).

Es geht hier übrigens nicht um eine Warteschlange mit
variabler Länge, sondern immer um 7 Byte.

Deshalb brauchst du nicht getrennt In- und Out-Pointer,
es reicht ein Index.
Je nach Laune kann der das letzte eingetragene Zeichen
indizieren oder das nächste.

BTW: wieso werden bei deinem memcmp nur 6 Byte verglichen?

Danke Klaus,

>dann kann man mit %7 in den Puffer fassen.
das mit %7 kenne ich noch nicht. Kannst Du mal ein paar Einzelheiten 
geben?


>mach doch einmal ein Feld mit allen deinen Vergleichsmustern
leuchtet ein, gute Idee. Das wird aber auch ein ganz schöner Code, nur 
für die 10*7 Bytes? Bei 100*7 Bytes wäre das bisher die effektivste 
Idee.

>BTW: wieso werden bei deinem memcmp nur 6 Byte verglichen?

Weil ich nicht wusste, ob er von 0-6 oder von 1-7 zählt :c)  Array geht 
nur von 0-6, deklariert ist es mit rx0_buffer[7]. Beim benutzen des 
rx_buffer[7] hat mit der GCC jedoch einen Fehler ausgespukt, dass der 
Wert höher ist, als das definierte Array. Beim memcmp wollte ich erst 
einmal kein Risiko eingehen und hätte es später durch testen erkannt, ob 
er die 6 oder 7 braucht :c)
Nach Deinem Kommentar gehe ich mal von der 7 aus :c)

es gibt auch Doku zu memcmp().
Probieren ist natürlich auch ein Weg.

Warte mal. ich mache ein Beispiel...

Ich habe gerade festgestellt, dass memcmp nicht alles vergleicht, 
sondern abbricht, wenn das erste Byte schon nicht stimmt. Somit 
vergleicht er eigentlich genau so schnell/effektiv, als das vergleichen 
des Arrays mit einem Pointer. Nur das herumschieben beim Emfang ist 
nicht schön. Aber mit 50µs kann ich voll leben.

Ich würde nur gerne den cmp_array schöner befüllen. Im Assember konnte 
ich die Zeichenketten einfach in eine db schreiben:

Zeichenkette 1:
.db 0x35, 0x56, 0x23, 0x67, 0x50, 0x23, 0x77)
Zeichenkette 2:
.db 0x35, 0x78, 0x23, 0x67, 0x23, 0x50, 0x77)
.
.


Um in C das memcmp damit zu füttern wäre ein zweidimensionales Array 
sinnvoll. Wie befülle ich das Array am schönsten mit diesen Werten?

Mir fällt nur das ein:
cmp_array[0][0] = 0x35;
cmp_array[0][1] = 0x56;
.
.
.

Da gibts doch bestimmt was schöneres oder?

So würde es ohne die XOR-Geschichte aussehen (inkl. kleinem
Testprogramm, 10 verschiedenen Tests und Ringpuffer ohne
verschieben):

1

#include <stdlib.h>

2

#include <stddef.h>

3

#include <stdio.h>

4

#include <string.h>

5

6

7

// nur zum Test: simuliert die Bytes von der UART:

8

static int     i = 0;

9

static char    simulationsdaten[] =

10

  {

11

    "hallo ich bin doof, aber gottseidank weiss ich es nicht, "

12

    "bin aber nicht der einzige."

13

    "Jedenfalls noch helle genug, um mein Geld ehrlich zu verdienen."

14

    "Noch muss ich nicht bei der FDP anheuern..."

15

  };

16

const int nSimulationsdaten = sizeof(simulationsdaten);

17

18

unsigned int uart_getc()

19

{

20

21

  return simulationsdaten[i++%nSimulationsdaten];

22

}

23

const int UART_NO_DATA = 0xff00;  // nie ein gültiges Zeichen, nur zum Testen

24

25

26

27

// Demo, wie ich mir das vorstelle:

28

29

30

31

// Der Index, wo im Ringpuffer das NÄCHSTE Zeichen abzulegen ist:

32

static int     ndx_RingpufferNext = 0;

33

static char    rx0_buffer[7] = { 0 };

34

35

// Die Vergleichsfolgen:

36

char          *cmp_buffer_arr[10] =

37

  {

38

    "\x35\x56\x23\x67\x50\x23\x77", // zum Testen 0 angehängt...

39

    "\x35\x78\x23\x67\x23\x50\x77", // zum Testen 0 angehängt...

40

    "\x66\x56\x23\x55\x50\x23\x87", // zum Testen 0 angehängt...

41

    "\x65\x56\x33\x67\x50\x10\x05", // zum Testen 0 angehängt...

42

    "Jedenfa",

43

    "nheuern",

44

    "einzige",

45

    "ich bin",

46

    "es nich",

47

    "Noch mu",

48

  };

49

50

51

52

// vergleicht 7 Zeichen aus rx0_buffer (ab Position

53

// (ndx_RingpufferNext+1) modulo 7) mit den 7 Zeichen ab cmp_buffer

54

// und liefert 0, wenn nicht gleich bzw. 1, wenn gleich:

55

int mmi_rx0_string_analyze ( const char *cmp_buffer )

56

{

57

  int iZeichen;

58

  for( iZeichen=0; iZeichen<7; ++iZeichen )

59

  {

60

    if( rx0_buffer[(ndx_RingpufferNext+iZeichen)%7]!=cmp_buffer[iZeichen] )

61

    {

62

      return 0;

63

    }

64

  }

65

  return 1;

66

}

67

68

69

70

void check_rx0_buffer()

71

{

72

  unsigned int c;

73

  c = uart_getc();                      //hier kommt das nächste Byte an

74

  if ( c & UART_NO_DATA )

75

  {                                     //Peters Lib

76

  }

77

  else

78

  {

79

    int iVergleich;

80

    rx0_buffer[ndx_RingpufferNext++] = c; // c eintragen,

81

                                          // ndx_RingpufferNext weiter setzen

82

    ndx_RingpufferNext %= 7;              // ndx_RingpufferNext auf

83

                                          // 0...6 begrenzen

84

85

    for( iVergleich=0; iVergleich<10; ++iVergleich )

86

    {

87

      if( mmi_rx0_string_analyze( cmp_buffer_arr[iVergleich] ) )

88

      {

89

        printf( "Text %s gefunden\n", cmp_buffer_arr[iVergleich] );

90

      }

91

    }

92

  }

93

}

94

95

96

97

int main( int nargs, char **args )

98

{

99

  int iGelesen;

100

  for( iGelesen=0; iGelesen<nSimulationsdaten; ++iGelesen )

101

  {

102

    check_rx0_buffer();

103

  }

104

  return 0;

105

}

Das %7 berechnet aus einem Wert dessen Divisionsrest beim Teilen
durch 7. D.h. der Wert in den Bereich 0 bis 6 verschoben und
der Index bleibt dadurch immer im Feld; anstatt hinten
rauszulaufen fängt man wieder vorne an.

Der Vollständigkeit halber hier noch die Variante mit XOR
(läuft auf meinem PC unter Linux mit gcc ohne Optimierung
um Faktor 3 schneller):

1

#include <stdlib.h>

2

#include <stddef.h>

3

#include <stdio.h>

4

#include <string.h>

5

6

#define   PARITY_BESCHLEUNIGUNG

7

8

9

// nur zum Test: simuliert die Bytes von der UART:

10

static int     i = 0;

11

static char    simulationsdaten[] =

12

  {

13

    "hallo ich bin doof, aber gottseidank weiss ich es nicht, "

14

    "bin aber nicht der einzige."

15

    "Jedenfalls noch helle genug, um mein Geld ehrlich zu verdienen."

16

    "Noch muss ich nicht bei der FDP anheuern..."

17

  };

18

const int nSimulationsdaten = sizeof(simulationsdaten);

19

20

unsigned int uart_getc()

21

{

22

23

  return simulationsdaten[i++%nSimulationsdaten];

24

}

25

const int UART_NO_DATA = 0xff00;  // nie ein gültiges Zeichen, nur zum Testen

26

27

28

29

// Demo, wie ich mir das vorstelle:

30

31

32

33

// Der Index, wo im Ringpuffer das NÄCHSTE Zeichen abzulegen ist:

34

static int     ndx_RingpufferNext = 0;

35

static char    rx0_buffer[7] = { 0 };

36

37

#ifdef  PARITY_BESCHLEUNIGUNG

38

// Parity-Byte des Ringpuffers:

39

static char    parity_rx0_buffer = 0;

40

#endif

41

42

43

// Die Vergleichsfolgen:

44

char          *cmp_buffer_arr[10] =

45

  {

46

    "\x35\x56\x23\x67\x50\x23\x77", // zum Testen 0 angehängt...

47

    "\x35\x78\x23\x67\x23\x50\x77", // zum Testen 0 angehängt...

48

    "\x66\x56\x23\x55\x50\x23\x87", // zum Testen 0 angehängt...

49

    "\x65\x56\x33\x67\x50\x10\x05", // zum Testen 0 angehängt...

50

    "Jedenfa",

51

    "nheuern",

52

    "einzige",

53

    "ich bin",

54

    "es nich",

55

    "Noch mu",

56

  };

57

58

#ifdef  PARITY_BESCHLEUNIGUNG

59

// Parity-Bytes der Vergleichsfolgen:

60

static char    parity_cmp_buffer_arr[10];

61

#endif

62

63

64

// vergleicht 7 Zeichen aus rx0_buffer (ab Position

65

// (ndx_RingpufferNext+1) modulo 7) mit den 7 Zeichen ab cmp_buffer

66

// und liefert 0, wenn nicht gleich bzw. 1, wenn gleich:

67

int mmi_rx0_string_analyze ( const char *cmp_buffer )

68

{

69

  int iZeichen;

70

  for( iZeichen=0; iZeichen<7; ++iZeichen )

71

  {

72

    if( rx0_buffer[(ndx_RingpufferNext+iZeichen)%7]!=cmp_buffer[iZeichen] )

73

    {

74

      return 0;

75

    }

76

  }

77

  return 1;

78

}

79

80

81

82

void check_rx0_buffer()

83

{

84

  unsigned int c;

85

  c = uart_getc();                      //hier kommt das nächste Byte an

86

  if ( c & UART_NO_DATA )

87

  {                                     //Peters Lib

88

  }

89

  else

90

  {

91

    int iVergleich;

92

#ifdef  PARITY_BESCHLEUNIGUNG

93

    // alten Wert austragen:

94

    parity_rx0_buffer ^= rx0_buffer[ndx_RingpufferNext];

95

#endif

96

    rx0_buffer[ndx_RingpufferNext++] = c; // c eintragen,

97

                                          // ndx_RingpufferNext weiter

98

                                          // setzen

99

    ndx_RingpufferNext %= 7;              // ndx_RingpufferNext auf

100

                                          // 0...6 begrenzen

101

#ifdef  PARITY_BESCHLEUNIGUNG

102

    // neuen Wert eintragen:

103

    parity_rx0_buffer ^= c;

104

#endif

105

106

    for( iVergleich=0; iVergleich<10; ++iVergleich )

107

    {

108

      if(

109

#ifdef  PARITY_BESCHLEUNIGUNG

110

          parity_rx0_buffer==parity_cmp_buffer_arr[iVergleich]

111

          &&

112

#endif

113

          mmi_rx0_string_analyze( cmp_buffer_arr[iVergleich] )

114

          )

115

      {

116

        //printf( "Text %s gefunden\n", cmp_buffer_arr[iVergleich] );

117

      }

118

    }

119

  }

120

}

121

122

123

124

int main( int nargs, char **args )

125

{

126

  int iGelesen;

127

128

#ifdef  PARITY_BESCHLEUNIGUNG

129

  // einmalig die Parity-Bytes der Vergleichsstrings intialisieren:

130

  int iVergleich;

131

  for( iVergleich=0; iVergleich<10; ++iVergleich )

132

  {

133

    int iByte;

134

    for( iByte=0; iByte<7; ++iByte )

135

    {

136

      parity_cmp_buffer_arr[iVergleich] ^= cmp_buffer_arr[iVergleich][iByte];

137

    }

138

  }

139

#endif

140

141

  size_t  i;

142

  for( i=0; i<500000; ++i )

143

  {

144

    for( iGelesen=0; iGelesen<nSimulationsdaten; ++iGelesen )

145

    {

146

      check_rx0_buffer();

147

    }

148

  }

149

  return 0;

150

}

Wow, danke, Klaus.

Das mit %7 ist eine geniale Funktion. Ich bereue es jetzt schon auf 
keinen Fall von Assembler auf C umgestiegen zu sein. Mit jeder Funktion, 
die man dazu lernt, eröffnen sich neue Welten :c)



>char          *cmp_buffer_arr[10] =
>  {
>    "\x35\x56\x23\x67\x50\x23\x77", // zum Testen 0 angehängt...
>    "\x35\x78\x23\x67\x23\x50\x77", // zum Testen 0 angehängt...
>    "\x66\x56\x23\x55\x50\x23\x87", // zum Testen 0 angehängt...
>    "\x65\x56\x33\x67\x50\x10\x05", // zum Testen 0 angehängt...
>    "Jedenfa",
>    "nheuern",
>    "einzige",
>    "ich bin",
>    "es nich",
>    "Noch mu",
>  };
>

Genau das brauche ich. Danke dafür. Was bedeutet eigentlich dieser Stern 
(*) vor dem cmp_buffer_arr[10] ?


ich werde mir jetzt mal die Arbeit machen und schauen welche 
Vergleichsmethode schneller ist :c)

Igor Ebner schrieb:
> Genau das brauche ich. Danke dafür. Was bedeutet eigentlich dieser Stern
> (*) vor dem cmp_buffer_arr[10] ?

weil cmp_buffer_arr ein Feld von 10 Zeigern auf char ist.
Jeder dieser Zeiger zeigt dann auf den Anfang eines der Teilfelder.

>
>
> ich werde mir jetzt mal die Arbeit machen und schauen welche
> Vergleichsmethode schneller ist :c)


Meine natürlich, weiß ich vorher :-)

So, als erstes mal Dein Messergebnis vom ersten code ohne XOR:

Das schieben in den Ringpuffer per %7 dauerte bei jedem ankomenden Byte 
100µs.
Das Auswerten dauerte dann 400µs.

Wenn ich meine Methode verwende und die Bytes im ir_buffer herum 
schiebe, dauert die Herumschieberei inkl laden des 7.ten Bytes 40µs. Und 
das Auswerten per memcmp nochmal 100µs.

Ich denke bei so wenig Zeichen macht die dumme Methode weniger 
Rechenaufwand. Deine Methode würde sich - rein theoretisch und 
rechnerisch, ab ca 20 Zeichen lohnen. Die XOR Methode habe ich nicht 
mehr ausprobiert, aber die wird vermutlich an 40/100µs nicht ran kommen 
:c)


Trotzdem vielen Dank an Dich, dass Du dir so viel Mühe gemacht hast. Du 
hast mir mehrere tolle Sachen beigebracht...

%7
XOR compression und
*cmp_buffer_arr

...und ich werde Dich heute in mein Nachtgebet mit Aufnehmen :c)

oh Gott, ich bin streng gläubiger Atheist!

Ich auch,

da bekommt die Aussage Dich ins Gebet mit aufzunehmen eine ganz neue 
Bedeutung :c)

In der Tat.

Um nicht zu sagen, das mit dem Gebet war doch irgendwie gelogen :-)

Hört er dann nicht auf, wenn der erste Buchstabe getestet wurde? Wie 
kommt er zu den weiteren cases?

Die Idee dieses Konstrukts ist es, dass nicht erst gewartet wird, bis 
der String komplett empfangen wurde, sondern jedes Zeichen, sobald es 
empfangen wurde, in dieses Konstrukt eingeleitet wird. Und so handelt 
sich dieses Konstrukt von einem case zum nächsten (bei jeweils dem 
nächsten Funktionsaufruf mit dem jeweils gültigen Zeichen).

Ahhhh, verstehe... :c)
Wenn man jedoch 10 verschiedene Zeichenketten zum überwachen hat, dann 
ist der Aufwand aber nicht mehr geringer, als mit einem Rollpuffer...