mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Fragment C-Code geschickter gestalten


Autor: imax (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Angefangen mit 4 commands, sind wir mittlerweile bei ca 25 Stk...
if (strncmp( (char*)buffer_, "request:ssid:all\n", 17 ) == 0 )  {}
else if(strncmp((char*)buffer_, "request:ssid:1\n", 15 ) == 0 ) {}
else if(strncmp((char*)buffer_, "config:end\n"), 11 == 0)  {}
...
...



Kann ich es geschickter gestalten? Ein switch case entfällt wohl, weil 
die Rückgaben von strncmp oder strstr nicht passend sind. Wie umgehe ich 
es?
Man könnte die substrings in einen integer umwandeln und dann per switch 
case abfragen. Dazu wäre dann ein #define notwendig. Klingt auch 
komisch..

evlt. habt ihr tolle Ideen?
Danke schon mal vorab!

Autor: Lothar Miller (lkmiller) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Du könntest die Kommandos in eine Stringtabelle ablegen und mit einem 
Index solange suchen, bis du das passende gefunden hast. Auf den Index 
kannst du dann den switch machen...

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Lothar Miller schrieb:
> Du könntest die Kommandos in eine Stringtabelle ablegen und mit einem
> Index solange suchen, bis du das passende gefunden hast. Auf den Index
> kannst du dann den switch machen...

um weiterzuführen:
Oder in einer Struktur und einem Array davon, einen String mit einem 
Funktionszeiger kombinieren und so bei einem bestimmten String eine 
Funktion aufrufen lassen.

Man könnte auch den String in seine Teilstrings zerlegen und diese Teile 
als Vorauswahl für eine oder mehrere Tabellen benutzen. Alle "request" 
in einer Tabelle, alle "config" in einer Tabelle.

Man könnte auch mit den Teilstrings eine Art Parsing veranstalten indem 
man Techiken aus dem Compilerbau (lexikalische Analyse) darauf anwendet.

Oder .....

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
enum COMMAND {
  A, B, C;
};

COMMAND getCommand(char* buffer) {
 if (strncmp(buffer, "request:ssid:all\n", 17 ) == 0 )  {
  return A;
 }
 if(strncmp(buffer, "request:ssid:1\n", 15 ) == 0 ) {
  return B;
 }
 if(strncmp((char*)buffer_, "config:end\n"), 11 == 0)  {
  return C;
 }
}
Wahrscheinlichere Commandos ganz oben in die Kette reduziert die 
Suchzeit, ggf. erst nach dem Prefix suchen:


COMMAND getCommand(char* buffer) {
 if (strncmp(buffer, "request:", 8 ) == 0 )  {
  if (strncmp(buffer, "ssid:all\n", 8, 17 ) == 0 )  {
   return A;
  }
  if(strncmp(buffer, "ssid:1\n", 8, 15 ) == 0 ) {
   return B;
  }
 }
 if(strncmp((char*)buffer_, "config:"), 7 == 0)  {
  return C;
 }
}[/c]
Achtung, Syntax ggf. anpassen...
Eventuell könnte man auch einfach ein Stringarray anlegen was durchsucht 
wird und dann den Index zurückgeben, dann müßten Index + Enum 
übereinstimmen...

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Läubi .. schrieb:
> Wahrscheinlichere Commandos ganz oben in die Kette reduziert die
> Suchzeit

Wenn die Suchzeit relevant wird, würde ich lieber das Feld mit
bsearch() sortieren und mit qsearch() suchen.
Auch wenn kaum einer die Funktionen nehmen mag, sind sie sehr hilfreich.

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Die Frage ist halt ob das
a) die Sortierzeit die verringerte Suchzeit nicht zunichte macht
b) geht das so gut auf einem uC?

Ich hatte eher daran gedacht das ein "exit" eventuell seltener 
aufgerufen wird (nämlich nur einmal beim beenden) als ggf. ein "set 
value" oder so ;)

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
imax schrieb:
> Kann ich es geschickter gestalten?

Ja.
Für sowas nimmt man ne Tabelle. Diese enthält den String und die 
Funktion, die dann aufgerufen werden soll.
Das Ende der Tabelle kennzeichnet ein leerer String.
Nachfolgend ein Codebeispiel für den 8051:

#include <stdlib.h>

typedef unsigned char   u8;

#define comm_data       u8 idata

u8 remote();
u8 local();
u8 status();


typedef struct{
  u8 code *name;
  u8 (code *func)(void);
}comm_struct;


comm_struct code comm_tab[] = {                 // command table
        "REM", remote,
        "LOC", local,
        "STAT", status,
        "", NULL                                // end of table
};


u8 execute( comm_data *buf )                    // command interpreter
{
  u8 i, j;                                      // up to 256 commands
  for( i = 0;; ){
    for( j = 0;; ){
      if( comm_tab[i].name[j] != 0 ){
        if( ((comm_tab[i].name[j] ^ buf[j]) & 0x5F) == 0 ){
          j++;
          continue;                             // next character
        }
        i++;
        break;                                  // next command
      }
      if( j == 0 )
        return 255;                             // error: command not found
      return comm_tab[i].func();                // execute command
    }
  }
}


Peter

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Läubi .. schrieb:
> Die Frage ist halt ob das
> a) die Sortierzeit die verringerte Suchzeit nicht zunichte macht

Sortiert wird ja nur einmal. Im Idealfall vom Programmierer :-)

> b) geht das so gut auf einem uC?
>
> Ich hatte eher daran gedacht das ein "exit" eventuell seltener
> aufgerufen wird (nämlich nur einmal beim beenden) als ggf. ein "set
> value" oder so ;)

Ein O(nlogn) Suchen ist schwer zu schlagen. Ich hab mich mal mit meinem 
Compilerbau Praktikumsleiter darüber gestritten. Ich war auf binärem 
Suchen, er auf Hashen. Er hatte die Nase ganz knapp vorne.

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Läubi .. schrieb:
> Die Frage ist halt ob das
> a) die Sortierzeit die verringerte Suchzeit nicht zunichte macht

Soertiert werden muß ja nur einmal beim Start (bzw. bei
evtl. Änderungen an der Tabelle, aber die hat man ja eher selten
bis gar nicht).

Das Sortieren kann man sich natürlich ganz sparen, wenn man das
Feld gleich im Quelltext sortiert hält.

> b) geht das so gut auf einem uC?

Warum nicht?
Ich habe das schon gelegentlich gemacht.

Auf einem uC kommt gelegentlich der Einwand, daß Rekursion
an sich und damit bsearch() gaaanz böse ist.

Das ist aber so pauschal wie falsch.
Rekursion ist nur dann gefährlich, wenn man keine Ahnung hat,
wann der Abbruch kommt und folglich mit einem Stackproblem
rechnen muß.

Bei bsearch() dagegen hat man im worst case eine Tiefe von
log2(n), also z.B. bei 1000 Elemente höchstens 10 und bei einer
Million Elemente höchstens 20 etc..

Wenn das aktuelle bsearch() nicht ohnehin iterativ arbeitet...

>
> Ich hatte eher daran gedacht das ein "exit" eventuell seltener
> aufgerufen wird (nämlich nur einmal beim beenden) als ggf. ein "set
> value" oder so ;)

Das ist wahr.
Aber bei den Mengen an Kommandos, wo die Suchzeit relevant wird,
hast du dann immer noch sehr viele im ersten Teil, die regelmäßig
linear durchgeforstet werden.
Daß exit() dann am Schluß steht, hilft etwas, aber nicht
grundlegend.

Bei dem Beispiel mit einer Mio Elementen:
Da wird man mit geschickter Vorsortierung nach Häufigkeit
vielleicht im Schnitt auf etliche Hundert oder ein paar Tausend
Vergleiche kommen bei linearer Suche.
Bei bsearch() im schlimmsten Fall wie gesagt auf 10.

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Karl heinz Buchegger schrieb:
> Ein O(nlogn) Suchen ist schwer zu schlagen. Ich hab mich mal mit meinem
> Compilerbau Praktikumsleiter darüber gestritten. Ich war auf binärem
> Suchen, er auf Hashen. Er hatte die Nase ganz knapp vorne.

Da muß man aber nur genug Daten nehmen, daß er die Nase weiter
vorn hat, abgesehen davon daß bsearch nicht O(n*log n)
hat, sondern O(log n) - sonst wäre lineare Suche schneller :-)
Hatten wir das Thema nicht neulich hier schon mal?

Aber es stimmt natürlich:
bsearch ist selbst bei mehr Daten, als in einen MC passen,
ziemlich fix.
Und das bei wenigen Byte Code.

Zudem kann man es ganz gut umfrisieren ("liefere gesuchtes
Element oder das nächstkleinere, falls nicht vorhanden" etc.).
Ist jetzt hier nicht gefragt, aber manchmal nett.

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Karl heinz Buchegger schrieb:
> Ein O(nlogn) Suchen ist schwer zu schlagen. Ich hab mich mal mit meinem
> Compilerbau Praktikumsleiter darüber gestritten. Ich war auf binärem
> Suchen, er auf Hashen. Er hatte die Nase ganz knapp vorne.
Das ist wohl wahr, ich hatte nur gedacht es sollte jedesmal sortiert 
werden, aber meinst du nicht eher O(log n)? Sonst wäre die lineare Suche 
ja schneller ;P


Klaus Wachtler schrieb:
> Bei dem Beispiel mit einer Mio Elementen:
Die Problemgröße ist wohl eher < 100...
imax schrieb:
> Angefangen mit 4 commands, sind wir mittlerweile bei ca 25 Stk
Das Problem wird sein das das sortieren hier irgenwie bewerten müßte wie 
"wichtig" ein Kommando ist, wobei hier fast der GNUPLOT Ansatz 
funktionieren könnte das ein Kommando aktzeptiert wird sobald es nicht 
mit einem anderem kollidiert, also

e = ec = ech = echo

solange es kein weiteres Kommandogit was mit e anfängt ;)

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Klaus Wachtler schrieb:
> Bei dem Beispiel mit einer Mio Elementen:
> Da wird man mit geschickter Vorsortierung nach Häufigkeit
> vielleicht im Schnitt auf etliche Hundert oder ein paar Tausend
> Vergleiche kommen bei linearer Suche.
> Bei bsearch() im schlimmsten Fall wie gesagt auf 10.

ach so:
Der worst case bei linearer Suche (z.B. Kommando wird gesucht,
das gar nicht enthalten ist) hätte man bei 1 Mio Elemente
dann entsprechend 1 Mio Vergleiche, bis man merkt daß es gar nicht da
ist.

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Läubi .. schrieb:
> Klaus Wachtler schrieb:
>> Bei dem Beispiel mit einer Mio Elementen:
> Die Problemgröße ist wohl eher < 100...

Ich glaube auch nicht, daß es hier nötig.
Meine Ausschweifungen bezogen sich auf den Fall, daß die Suchzeit
relevant wird.

Bei 4 oder 10 Kommandos ist es vollkommen wumpe.

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Klaus Wachtler schrieb:
> bis man merkt daß es gar nicht da
> ist.
Für den Fall sollte man außerdem eine mindestens 10 Sekündige 
Warteschleife einplanen damit der Nutzer mal sieht was er davon hat und 
beim nächastenmal den Kram besser gleich richtig eingibt, außerdem darf 
ja nicht der EIndruck entstehen der Controller hätte nicht gründlich 
genug gesucht ;P

Autor: Horst Hahn (horha)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

wenn man selbst bestimmen kann, wie die ankommenden Kommandos aussehen, 
dann sende doch nur eine ID.
Wenn es unbedingt leserlich sein  soll, versendet man  "ID"+"Text" oder 
"Text" + "ID".
Dann braucht man nur die passenden Zeichen der ID parsen und in integer 
wandeln.
"request:ssid:1\n" würde zum Beispiel zu "request:ssid:1\n01\n"
"01" stände für Einzelanfrage, die 1 aus ssid:1 könnte gesondert 
behandelt werden, wenn man flexibel bleiben will.

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Läubi .. schrieb:
> Warteschleife

An dir ist ein echter Pädagoge verloren gegangen :-)

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Klaus Wachtler schrieb:
> Läubi .. schrieb:
>> Warteschleife

Die Warteschleife ist wirklich unbedingt nötig, weil der Nutzer ja sein 
gewohntes Feeling vom 4-Kern 3GHz Windows-PC haben will.
Nicht daß der Nutzer noch nen Herzinfarkt kriegt.


Peter

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Klaus Wachtler schrieb:

> Da muß man aber nur genug Daten nehmen, daß er die Nase weiter
> vorn hat, abgesehen davon daß bsearch nicht O(n*log n)
> hat, sondern O(log n)

Nach dem ersten Kaffee seh ich es jetzt auch glasklar.

Genau das hab ich damals auch behauptet: Eine Programmiersprache hat 
zuwenig Schlüsselwörter, als das Hashen da noch grossartig was bringt. 
Ich denke er hat dann auch lange an der Hashfunktion gefeilt um alle 
Kollisionen loszuwerden.


Neuronale Netze fallen mir jetzt noch ein.
Man will ja schliesslich nicht nur PC Feeling sondern auch ein UI mit 
Hollywood-Touch :-)

Autor: imax (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sind diese funktionen standard C-Funktionen in der avr-lib C?

Ist es sowas wie das bubble-sort oder quick-sort, selection-sort, 
welches man in den Grundlagen lernt?

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
imax schrieb:
> Sind diese funktionen standard C-Funktionen in der avr-lib C?

Ja, sind Standard-Funktionen.

> Ist es sowas wie das bubble-sort oder quick-sort, selection-sort,
> welches man in den Grundlagen lernt?

qsort    -   Quick Sort
bsearch  -   Binäres Suchen

Einfach mal in das File stdlib.h reinschauen.

Autor: Oliver (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Karl heinz Buchegger schrieb:
> qsort    -   Quick Sort
> bsearch  -   Binäres Suchen
>
> Einfach mal in das File stdlib.h reinschauen.

Kann man machen. Aber:
Never, ever optimize prematurley!

Bei 25 Strings, die da verglichen werden müssen, würde ich erst einmal 
straightforward stumpf von vorne nach hinten linear suchen. Wenn es dann 
später mal nachweislich zu langsam ist, dann lässt sich das immer noch 
optimieren.

Oliver

Autor: Mr Obvious (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Und wenn schon optimieren, dann über eine State-Machine, die den 
Eingangsstring zeichenweise testet/abarbeitet. (Lexer)
So muss kein Buchstabe mehrfach angefast werden.

Autor: Schwiizer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sofern du nur statische Strings parsen musst, könntest du sie auch 
hashen, und dann mit dem Hash hantieren. Anstatt strcmp() reicht also 
eine Tabellensuche mit Vergleich auf den Integer deiner Wahl. Wenn du 
die Lookup-Tabelle vorsortierst, ist die Suche auch bei 100+ Elementen 
sehr effizient.

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mit vorberechneten Hashwerten geht wiederum dann auch ein switch.

Autor: Horst Hahn (horha)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

sortieren ist wohl auf dem MC nicht notwendig, ausser man kann Befehle 
und Funktionen nachträglich übertragen.Aber sortieren von Zeigern auf 
die Strings würde recht fix gehen, solange es kein bogo-sort ist ;-)
Binaere Suche sind nur ein paar Zeilen Code.bsearch ist also kompakt und 
schnell.
Bei 25 Strings mus man ja nur maximal 5 Stringvergleiche durchführen, 
bis man den richtigen gefunden oder als nicht vorhanden ausschliessen 
kann.

Meine Vorschlag mit einer zusätzlichen ID macht bei langsamer 
Übertragung wenig Sinn.
3 Byte extra brauchen bei 115200 Baud und bei 16 Mhz Takt minimal 4200 
oder so Takte, da ist eine binäre Suche längst fertig.

Eine gut Hash-Funktion muss man erst mal finden, bei solchen Daten?
"request:ssid:all\n","request:ssid:1\n"
Wenn der Puffer vor dem beschreiben mit der Kommandozeichenkette immer 
genullt ist,
kann man ja Zeichen 0,6,13 addieren && 31 und schauen, ob da keine 
Doppelten sind.

Aber jedesmal beim Hinzufügen eines neuen Kommandos testen, was da für 
ein hashwert raus kommt, nä, zuviel Aufwand und Fehler trächtig.

Ich würde eine alle n Kommandos sortiert als nullterminierte Strings 
hintereinander pappen und anschliessend eine konstante Tabelle mit 
Zeigern auf die einzelnen Strings.
http://www.mikrocontroller.net/articles/AVR-GCC-Tu...
In der Tabelle kann man dann binär  suchen und hat als Ergbenis eine 
Zahl von 0.. n-1
Dann ist switch optimal einzusetzen.

Autor: Anfänger (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo nochmal!

Der Code von PeDa gefällt mir schon!

Dort kommt immer das Wort 'code' drin vor. Dort wirft mir der GCC fehler 
raus:

typedef struct{
  u8 code *name;                <---- FEHLER
  u8 (code *func)(void);
}comm_struct;

../functions.c:33: error: expected ':', ',', ';', '}' or '__attribute__' 
before '*' token

ich kenne auch nur sowas:
u8 *name;

aber kein:
u8 code *name;  //hier weiß mein GCC nicht, was er anlegen soll :(

Wo ist mein Fehler?

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Anfänger schrieb:

> Dort kommt immer das Wort 'code' drin vor.

Das ist irgendeine Spezialität des verwendeten Compilers, die wohl dafür 
sorgt, dass die beschriebenen Daten ins Flash kommen.

Wirf fürs erste das 'code' einfach raus.

Autor: Timo P (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Also ist es quasi das Schlüsselwort, der Typqualifikator einer Variable.
Sinn macht es auf jeden Fall, die Tabelle in den Flash zu speichern.

Für den GCC mit der AVR-LibC nehme ich dann PROGMEM als Attribut.

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
code, idata sind die verschiedenen Speicherbereiche des 8051.
Laß sie einfach weg oder:
#define code
#define idata


Peter

Autor: Timo P (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo PeDa!(und ihr Anderen)

Ich habe mir den code mal genau zu Gemüte geführt. Mir ist allerdings 
nicht klar, was genau die folgende Zeile macht.

if( ((comm_tab[i].name[j] ^ buf[j]) & 0x5F) == 0 )

Verglichen wird hier ein einzelnes Zeichen des commands in der Tabelle 
mit den eingehenden daten. Wozu ist denn das exor? 0x5F ist die Bitfolge 
0101.1111. Wozu ist diese Maske notwendig?

Ich kann zwar die einzelnen bytes binär verknüpfen, via (x^y)&z wie es 
oben steht, aber der Sinn ist mir nicht ganz klar.

Vllt. hilfst du (oder jmd, der sich im stande fühlt) etwas auf die 
Sprünge.
Den code möchte ich nutzen, aber nicht stupide per copy paste ans laufen 
bringen, sondern verstehen!

Danke für kurze Hilfe!

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Timo P schrieb:
> Wozu ist denn das exor?

EXOR ist der Vergleich, es ergibt 0 bei Gleichheit.

> 0x5F ist die Bitfolge
> 0101.1111. Wozu ist diese Maske notwendig?

Damit ist Groß-/Kleinschreibung egal.


Peter

Autor: Timo P (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das ist ja schlau!

Habe gerade in der ASCII-Tabelle nachgeschaut!

Die Null, die wir erzwingen, ist die 32, die dann vom ASCII-Code 
abgezogen wird. (ist genau der Unterschied zwischen einem großen und dem 
gleichen Buchstaben in klein)

Darauf soll man erst mal kommen.....

THX!

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.