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


von Chris O. (lupin_iii)


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?

von Klaus W. (mfgkw)


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.

von Stefan E. (sternst)


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.

von eh (Gast)


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.

von Peter D. (peda)


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

von Chris O. (lupin_iii)


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:
1
  lds  counter, ow_devices   ; Anzahl der Geräte
2
  lsl  counter    ; x8 Byte pro ID
3
  lsl  counter
4
  lsl  counter
5
6
load_settings_core_sensor_search:
7
  ldi  XH, HIGH(ow_device_id_temp+8)    ; zu suchender Sensor
8
  ldi  XL, LOW(ow_device_id_temp+8)
9
  ldi  YH, HIGH(ow_device_ids)      ; Sensor-Liste
10
  ldi  YL, LOW(ow_device_ids)
11
  add  YL, counter    ; Speicher-Position hinter letzter ID
12
  clr  data
13
  adc  YH, data
14
15
load_settings_core_sensor_search_next_byte:
16
  dec  counter
17
  ld  data, -X
18
  ld  temp3, -Y
19
  cp  data, temp3
20
  brne  load_settings_core_sensor_search_next_sensor  ; ID unterschiedlich -> nächster Sensor
21
22
  mov  temp3, counter
23
  andi  temp3, 0b00000111
24
  brne  load_settings_core_sensor_search_next_byte  ; noch nicht beim letzten Byte der ID
25
26
  lsr  counter    ; 8 Bytes gleich, Sensor gefunden
27
  lsr  counter    ; /8
28
  lsr  counter
29
  inc  counter    ; counter enthält nun Position des Geräts
30
  rjmp  load_settings_core_sensor_search_done
31
32
load_settings_core_sensor_search_next_sensor:
33
  andi  counter, 0b11111000      ; restliche Bytes des Sensors überspringen
34
  brne  load_settings_core_sensor_search  ; Zähler noch nicht null
35
36
load_settings_core_sensor_search_done:
37
  sts  core_sensor, counter

Für Anmerkungen bin ich immer noch dankbar.

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

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.