AVR-Assembler Suchroutine: Position einer 8-Byte-ID in einer Liste finden

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.

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.

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

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