www.mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik AVR-Assembler Suchroutine: Position einer 8-Byte-ID in einer Liste finden


Autor: Chris O. (lupin_iii)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nachdem eine Suche nach "Suchfunktion" immer nur Beiträge findet, dass 
man doch die Suchfunktion verwenden soll (auch bei Google nicht besser), 
muss ich doch einen neuen Beitrag anfangen.

Also: ich habe nach einem 1W-ROM-Search eine Liste von IDs (DS18B20 
Temperatursensoren, 8 Byte pro Eintrag) im SRAM eines ATmega8. Einer der 
Sensoren ist wichtig und deswegen merke ich mir dessen ID im EEPROM, 
sodass man auch nach einem Reset noch weiß, welcher es war. Allerdings 
muss ich nach einem Neustart überhaupt erst einmal herausfinden, ob er 
noch da ist bzw. ob sich seine Position in der Liste geändert hat (kann 
ja sein, dass was ausgetauscht wurde). Jede Idee, das zu implementieren, 
die ich habe, kommt mir extrem ineffizient vor. Hat jemand schonmal 
sowas in AVRASM2 gemacht?

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wo kommt denn die Liste her? Wer baut die auf und wie?
Wenn es eine lineare Liste ist, wird nur lineare Suche helfen.
Wenn das zu langsam ist (bei wie vielen Einträgen eigentlich),
muß man keine lineare Liste aufbauen, sondern halt was anderes
(Binärbaum, Hashtabelle).

Falls du das Aufbauen der Liste in der Hand hast, kannst du doch
gleich nebenbei den interessanten Eintrag merken, anstatt
zum Schluß nochmal die Liste durch zu ackern.

Autor: Stefan Ernst (sternst)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Chris O. schrieb:
> Nachdem eine Suche nach "Suchfunktion" immer nur Beiträge findet, dass
> man doch die Suchfunktion verwenden soll (auch bei Google nicht besser),
> muss ich doch einen neuen Beitrag anfangen.

"Suchalgorithmus" wäre der bessere Begriff.

Autor: eh (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Da die Liste auf einem AVR ja nicht allzu lang sein kann, wahrscheinlich 
in einem statischen Array, wuerd ich jeden Eintrag vergleichen. Auf 
einem PC hingegen, mit tausenden bis Millione Eintraegen wuerd ich einen 
balancierten Binaerbau nehmen.

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich weiß ja nicht, wie lang Deine Liste ist, aber z.B. 20*7Byte zu 
vergleichen, kostet kaum Zeit. Da lohnt sich ein aufwendigerer 
Algorithmus nicht.

Du kannst auch zuerst nur die CRC vergleichen und dann den Rest.


Peter

Autor: Chris O. (lupin_iii)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
An dem Tag bin ich wohl einfach schon zu lange davor gesessen und hatte 
eine Blockade. Alles was ich hingeschrieben habe, war immer voll von 
JMPs und breaks und ich habe jede Menge Register gebraucht. Jetzt wo ich 
wieder etwas länger Zeit gehabt habe, habe ich's nochmal versucht und 
bin mit dem Ergebnis eigentlich ganz zufrieden. Dass die IDs genau 8 
Byte lang sind, macht das ganze natürlich um einiges praktischer (bei 
kürzeren könnte man natürlich ein padding machen). So nebenbei hat sich 
bei dem Algorithmus auch noch ergeben, dass ich die IDs jeweils vom 
niedrigsten Byte an vergleiche, wo die Chance am größten ist, dass sie 
sich unterscheiden (die ersten Bytes geben ja Gerätetyp u.ä. an und sind 
bei allen gleich) und ich so schneller zum nächsten springe, falls ein 
Byte nicht passt.

spärlich kommentiert das Ergebnis:
  lds  counter, ow_devices   ; Anzahl der Geräte
  lsl  counter    ; x8 Byte pro ID
  lsl  counter
  lsl  counter

load_settings_core_sensor_search:
  ldi  XH, HIGH(ow_device_id_temp+8)    ; zu suchender Sensor
  ldi  XL, LOW(ow_device_id_temp+8)
  ldi  YH, HIGH(ow_device_ids)      ; Sensor-Liste
  ldi  YL, LOW(ow_device_ids)
  add  YL, counter    ; Speicher-Position hinter letzter ID
  clr  data
  adc  YH, data

load_settings_core_sensor_search_next_byte:
  dec  counter
  ld  data, -X
  ld  temp3, -Y
  cp  data, temp3
  brne  load_settings_core_sensor_search_next_sensor  ; ID unterschiedlich -> nächster Sensor

  mov  temp3, counter
  andi  temp3, 0b00000111
  brne  load_settings_core_sensor_search_next_byte  ; noch nicht beim letzten Byte der ID

  lsr  counter    ; 8 Bytes gleich, Sensor gefunden
  lsr  counter    ; /8
  lsr  counter
  inc  counter    ; counter enthält nun Position des Geräts
  rjmp  load_settings_core_sensor_search_done

load_settings_core_sensor_search_next_sensor:
  andi  counter, 0b11111000      ; restliche Bytes des Sensors überspringen
  brne  load_settings_core_sensor_search  ; Zähler noch nicht null

load_settings_core_sensor_search_done:
  sts  core_sensor, counter

Für Anmerkungen bin ich immer noch dankbar.

Sonst für die Suchfunktion ;-) : Suchroutine, Suchalgorithmus, 
Search-Funktion

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.