Aus RN-Wissen.de
Wechseln zu: Navigation, Suche
Rasenmaehroboter fuer schwierige und grosse Gaerten im Test

(→‎State Machine)
K (→‎Suchen und Finden)
Zeile 750: Zeile 750:
 
;Zugriff über den Index (Position): Damit findet man sehr schnell die Information. Aus der Tabelle der Zustände wird der Zustand mit der Nummer ''n'' gelesen, indem man auf das ''n''-te Element zugreift. Die Zustands-Nummer muss nicht im Zustand selber gespeichert werden. Diese Art des Findens eignet sich für dicht besetzte Tabellen, in denen es kaum/keine Lücken gibt. (Falls es welche gibt, muss man das erkennen können). Im Beispiel wird auf die Zustands-Tabelle so zugegriffen, auch wenn sie dort recht leer ist. In der Praxis sieht das aber oft anders aus.
 
;Zugriff über den Index (Position): Damit findet man sehr schnell die Information. Aus der Tabelle der Zustände wird der Zustand mit der Nummer ''n'' gelesen, indem man auf das ''n''-te Element zugreift. Die Zustands-Nummer muss nicht im Zustand selber gespeichert werden. Diese Art des Findens eignet sich für dicht besetzte Tabellen, in denen es kaum/keine Lücken gibt. (Falls es welche gibt, muss man das erkennen können). Im Beispiel wird auf die Zustands-Tabelle so zugegriffen, auch wenn sie dort recht leer ist. In der Praxis sieht das aber oft anders aus.
 
;Tabelle durchsuchen: Diese Herangehensweise eignet sich für Daten, die eine fast leere ("dünn besetzte") Tabelle zur Folge hätten. Im Beispiel wird die Tabelle mit den Übergangs-Beschreibungen durchsucht. Dazu braucht man einen ''Schlüssel''. Im Beispiel wird dieser gebildet aus dem aktuellen Zustand der Maschine und dem vom Band gelesenen Zeichen. Für jeden existierenden Übergang gibt es dann einen Eintrag in der Tabelle, allerdings ohne Lücken dazwischen.  
 
;Tabelle durchsuchen: Diese Herangehensweise eignet sich für Daten, die eine fast leere ("dünn besetzte") Tabelle zur Folge hätten. Im Beispiel wird die Tabelle mit den Übergangs-Beschreibungen durchsucht. Dazu braucht man einen ''Schlüssel''. Im Beispiel wird dieser gebildet aus dem aktuellen Zustand der Maschine und dem vom Band gelesenen Zeichen. Für jeden existierenden Übergang gibt es dann einen Eintrag in der Tabelle, allerdings ohne Lücken dazwischen.  
−
;Tabelle binär durchsuchen: Die beim Suchen verwendet Tabelle ist zwar kompakt weil sie keine Lücken hat, aber man muss sich im Zweifelsfalle jeden Eintrag anschauen, um den Gesuchten zu finden. Das geht ab einer bestimmten Tabellengröße wesentlich schneller, wenn man eine binäre Suche verwenden kann (im Beispiel nicht verwendet). Dadurch reduziert sich die Zeit zum Durchsuchen einer Tabelle mit ''M'' einträgen von der Größenordnung ''M'' zur Größenordnung log(''M''). Es ist jedoch etwas Programmierung zu leisten, und für sehr kleine Tabellen ist die binäre Suche unterlegen.
+
;Tabelle binär durchsuchen: Die beim Suchen verwendet Tabelle ist zwar kompakt weil sie keine Lücken hat, aber man muss sich im Zweifelsfalle jeden Eintrag anschauen, um einen Eintrag zu finden oder um zu Erkennen, daß es gar keinen Eintrag gibt. Das geht ab einer bestimmten Tabellengröße wesentlich schneller, wenn man eine binäre Suche verwenden kann (im Beispiel nicht verwendet). Dadurch reduziert sich die Zeit zum Durchsuchen einer Tabelle mit ''M'' Einträgen von der Größenordnung ''M'' zur Größenordnung log<sub>2</sub>(''M''). Es ist jedoch etwas Programmierung zu leisten, und für sehr kleine Tabellen ist die binäre Suche unterlegen. Bei einer Tabelle mit 100 Einträgen braucht man 100 Vergleiche ohne binäre Suche und ca 8 Vergleiche mit binärer Suche.
  
 
==GCC (State Machine)==
 
==GCC (State Machine)==

Version vom 17. Januar 2006, 15:59 Uhr

Es sollen hier einige Beispiele gebracht werden, wie einige Dinge in verschiedenen Sprachen gelöst werden können. Es sollte nicht als Wettbewerb der Compiler gesehen werden, welcher denn nun der "Bessere" sei. Über Vorzüge und Nachteile der verschiedenen Sprachen gibt es durchaus kontroversielle Ansichten. Daran will ich hier gar nicht rütteln, über Geschmack kann man nicht streiten.

Hello, world

Ein ganz einfaches Programm, oft auch das erste, ist, den Text "Hello, world !" auf dem Terminal erscheinen zu lassen.

Was so trivial klingt, hat den Zweck, mehrere Dinge zu überprüfen:

  • Komme ich mit der Entwicklungsoberfläche zurecht
  • funktioniert das Kompilieren und das Übertragen eines Programms auf den Microcontroller
  • stimmen die Einstellungen Quartz und Baudrate
  • funktioniert die RS232-Verbindung mit dem PC
Natürlich ist der Text vollkommen egal, er hat sich ganz einfach eingebürgert und fast jeder 
weiß, was damit gemeint ist.

BasCom (Hello, world)

Die folgenden vier Zeilen lassen ahnen, warum Bascom speziell für Einsteiger geradezu ein Segen ist: 

 $Crystal=8000000
 $Baud=9600

 Print "Hello, world !"

 End

GCC (Hello, world)

 #include <avr/io.h> 

 #define F_CPU 			8000000 
 #define USART_BAUD_RATE 	9600 
 #define USART_BAUD_SELECT 	(F_CPU/(USART_BAUD_RATE*16L)-1) 

 char cText[] = "Hello, world !\r\n";

 //-----------------------------------------------------
 void _writeChar (char c)
 {
     while (!(UCSRA & (1<<UDRE))) {} 
         UDR = c; 
 }
 //-----------------------------------------------------
 void _writeString (unsigned char *string) 
 { 
      while (*string) 
          _writeChar (*string++); 
 } 
 //-----------------------------------------------------
 void main()
 {
      UCSRB |= (1<<TXEN); 
      UCSRC = (1<<URSEL)|(1<<UCSZ1)|(1<<UCSZ0); 
      UBRRL = (unsigned char) USART_BAUD_SELECT; 
      _writeString(cText); 

      // Endlossschleife: nichts mehr tun 
      while (1)
      {}
  }

Wenn jemanden der Aufwand bei GCC erschrecken sollte:

GCC hat keine Standard-Annahme darüber, wie und wo eigentlich der Output stattfinden sollte. Es ist für ihn nicht selbstverständlich, die UART zu verwenden. Dadurch muß natürlich mehr definiert werden. Dem BasCom kommt zugute, daß er die ganze Konfiguration mit AVR, RS232 und PC-Terminal erstmal als gegeben nimmt.

AVRStudio Assembler ((Hello, world))

 .NOLIST                    ; List-Output unterdrücken
 .INCLUDE <m32def.inc>       ; das gibt es für jeden Controllertyp
 .LIST                      ; List-Output wieder aufdrehen
 .CSEG                      ; was nun folgt, gehört in den FLASH-Speicher

 #define F_CPU  		8000000 
 #define USART_BAUD_RATE 	9600 

 ;------------------------------------------------------
 ;     Start Adresse 0000
 ;------------------------------------------------------
 RESET:
     jmp INIT           ; springen nach "INIT"

 ;------------------------------------------------------
 ;     ISR VECTORS
 ;------------------------------------------------------
 ;    .....    hier kommen dann die Sprungadressen für die Interrupts rein
 ;             brauchen wir aber jetzt nicht
 .ORG INT_VECTORS_SIZE    ; dadurch haben wir aber trotzdem für die Vektoren Platz gelassen
 INIT:  
 ;------------------------------------------------------
 ;     INITIALIZE
 ;------------------------------------------------------
     ldi r24,high(RAMEND)     ; Stack Pointer setzen 
     out SPH,r24              ; "RAMEND" ist in m32def.inc (s.o.) festgelegt
     ldi r24,low(RAMEND)      ; 
     out SPL,r24              ;
 
        ldi	r24, (F_CPU/(USART_BAUD_RATE * 16)-1) 
	out	UBRRL,r24
	ldi	r24, (1<<URSEL)|(1<<UCSZ1)|(1<<UCSZ0)
	out	UCSRC,r24
	ldi	r24,(1<<TXEN) |(1<<RXEN)
	out	UCSRB,r24
 ;------------------------------------------------------
 ;   HAUPTSCHLEIFE
 ;------------------------------------------------------
 Hauptschleife: 
	ldi	ZL,low(Hello << 1)	; ZL:ZH ASCIZ String addr
	ldi	ZH,high(Hello << 1)	; ZL:ZH ASCIZ String addr
	call	printflash
	call	PrintCrLf
 ;------------------------------------------------------
 ;   ENDE
 ;------------------------------------------------------
 Ende:  
        rjmp Ende

 ;------------------------------------------------------
 ;   PRINT String from Flash
 ;------------------------------------------------------
Printflash:
	call	GetFlash	; get byte to R24
	breq	PrintXit	; zero  (string end) exit
	rcall	PrintR24	; send byte
	rjmp	Printflash	; loop
PrintXit:
	ret
; -----------------------------------------------------------------------
;  PRINT  CRLF
; -----------------------------------------------------------------------
PrintCrLf:
	ldi	r24,0x0D
	rcall	PrintR24
	ldi	r24,0x0A
; -----------------------------------------------------------------------
;  PRINT  R0
; -----------------------------------------------------------------------
PrintR24:
	sbis	UCSRA,UDRE
	rjmp	PrintR24
	out	UDR,r24
	ret
; -----------------------------------------------------------------------
;  Get one Flash Char
; -----------------------------------------------------------------------
GetFlash:
	lpm
	adiw	ZL,0x0001
	mov	r24, r0
	and	r24, r24
	ret
Hello:
	.db "Hello, world !", 0x00 , 0x00


Tastatur-Echo

Wenn das vorhergegangene Beispiel funktioniert hat, wird man natürlich auch überprüfen wollen, ob auch die umgekehrte Richtung VOM Terminal klappt. Die einfachste Methode ist es, ganz einfach jedes Zeichen, das eingegeben wird, sofort zurückzusenden.

BasCom (Tastatur-Echo)

 $Crystal=8000000
 $Baud=9600

 DIM Zeichen as Byte

 Do
   inputbin Zeichen
   Printbin Zeichen
 Loop
 End

GCC (Tastatur-Echo)

 #include <avr/io.h> 

 #define F_CPU 			8000000 
 #define USART_BAUD_RATE 	9600 
 #define USART_BAUD_SELECT 	(F_CPU/(USART_BAUD_RATE*16L)-1) 

 char bZeichen;
 
 //-----------------------------------------------------
 void main()
 {
      UCSRB = (1<<RXEN)|(1<<TXEN); 
      UCSRC = (1<<URSEL)|(1<<UCSZ1)|(1<<UCSZ0); 
      UBRRL = (unsigned char) USART_BAUD_SELECT; 
      while (1) 
      { 
         while ( !(UCSRA & (1<<RXC)) ) {}
         bZeichen = UDR; 
         while (!(UCSRA & (1<<UDRE)))  {} 
         UDR = bZeichen; 
      }
 }

AVRStudio Assembler (Tastatur-Echo)

 .NOLIST                    ; List-Output unterdrücken
 .INCLUDE <m32def.inc>       ; das gibt es für jeden Controllertyp
 .LIST                      ; List-Output wieder aufdrehen
 .CSEG                      ; was nun folgt, gehört in den FLASH-Speicher

 #define F_CPU  			8000000 
 #define USART_BAUD_RATE 	9600 

 ;------------------------------------------------------
 ;     Start Adresse 0000
 ;------------------------------------------------------
 RESET:
     jmp INIT           ; springen nach "INIT"


 .ORG INT_VECTORS_SIZE    ; dadurch haben wir für die Vektoren Platz gelassen
 INIT:  
 ;------------------------------------------------------
 ;     INITIALIZE
 ;------------------------------------------------------
     ldi r24,high(RAMEND)     ;Stack Pointer setzen 
     out SPH,r24              ; "RAMEND" ist in m32def.inc (s.o.) festgelegt
     ldi r24,low(RAMEND)      ; 
     out SPL,r24              ;


	ldi	r24, (F_CPU/(USART_BAUD_RATE * 16)-1) 
	out	UBRRL,r24
	ldi	r24, (1<<URSEL)|(1<<UCSZ1)|(1<<UCSZ0)
	out	UCSRC,r24
	ldi	r24,(1<<TXEN) |(1<<RXEN)
	out	UCSRB,r24
 
 ;------------------------------------------------------
 ;   HAUPTSCHLEIFE
 ;------------------------------------------------------
 Hauptschleife: 
	sbis	UCSRA,RXC
	rjmp	Hauptschleife
 WaitUDR:
	sbis	UCSRA,UDRE
	rjmp	WaitUDR
	out	UDR,r24
    rjmp 	Hauptschleife         ; immer wiederholen

Bemerkungen

Hier ist der Unterschied des Codes nicht mehr so groß. Ganz klar, hier konnte BasCom wegen der Aufgabenstellung nicht auf eine vorgefertigte komplexe Funktion zurückgreifen.
Bei Assembler und GCC fallen große Ähnlichkeiten auf, von den Befehlscodes mal abgesehen.

Signallänge messen

Sehr oft ist es bei Controllern nötig, die Länge eines kurzen Impulses zu messen. Zum Beispiel wenn man einen RC-Empfänger (Modellbauempfänger) an ein Controllerboard anschließt. Ein RC-Empfänger sendet alle 20 Millisekunden ein High-Impuls von 1 bis 2 Millisekunden Länge aus. Die Länge dieses Impules bestimmt die Position des Steuerknüppels. Man braucht also nur diese Impulsdauer zu messen, um ein Fernsteuersignal auszuwerten.

BasCom (Signallänge messen)

Bascom vefügt für diesen Zweck über den PULSEIN-Befehl, daher wird ein Programm extrem kurz. Die Messung erfolgt in etwa in 100 Abstufungen, da Pulsein in 10 µSek Schritten die Zeit ermittelt (läßt sich in Libary ändern) 

 $regfile = "m32def.dat"   
 $framesize = 32
 $swstack = 32
 $hwstack = 32
 $crystal = 16000000        'Quarzfrequenz
 $baud = 9600

 Dim Rckanal As Word

 Do
   Pulsein Rckanal , Pind , 2 , 1    'Messung Zeit zwischen 1 und 0 Pegel
   Print "RC Signal: " ; Rckanal ; "0 uS"
   Wait 2
 Loop
 End

GCC (Signallänge messen)

Das GCC-Beispiel, das die gleiche Aufgabe erfüllt:
Das ist nun nicht so einfach, da "pulsein" ja eine komplexe Library-Funktion von BasCom ist, die für andere Sprachen normalerweise nicht verfügbar ist. Da BasCom für die Zählung keinen Timer verwendet, sondern die Maschinencycles als Maßstab nimmt, ist es in vergleichbarer Form eigentlich nur mit "inline-assembler" zu lösen, in Abhängigkeit von der Quartz-Frequenz. Trotzdem soll zu Demonstration die Sache mit möglichst C-Style Mitteln durchgezogen werden
Im folgenden Beispiel ist aber nur die "PulseIn" Funktion ausgeführt, das "print" des Ergebnisses hatten wir ja schon. 

#define BAUD_RATE    9600 

#include <stdlib.h> 
#include <stdio.h> 
#include <avr/io.h> 


#define PULS_C_LEV_LOW	0          // Die "LOW" Zeit des Pins soll gemessen werden 
#define PULS_C_LEV_HIGH	0xFF       // Die "HIGH" Zeit des Pins soll gemessen werden 

typedef struct {
volatile unsigned char bPin;              // PINx Register
volatile unsigned char bDdr;              // DDRx Register
volatile unsigned char bPort;             // PORTx Register
} IO_REG;


unsigned short PulseIn(IO_REG* pPort, unsigned char PinNr, unsigned char Level);


int main (void) 
{ 
unsigned short RcKanal;

	RcKanal = PulseIn((IO_REG*)&PIND, 2, PULS_C_LEV_HIGH);
	return 0;
}

Hier ist ersteinmal die Verwendung der Funktion dargestellt. Es wird

  • das Port mit Adresse angegeben (PIND)
  • die Pin-Nummer als Zahl 0-7 (2)
  • Der Level, der gezählt werden soll (PULS_C_LEV_HIGH)
// -------------------------------------------------------------------------------------
// 
// -------------------------------------------------------------------------------------
unsigned short PulseIn(IO_REG* pPort, unsigned char PinNr, unsigned char Level)
{
unsigned char iX;				// temporärer Zähler
unsigned short wCounter = 0;			// Time Zähler
unsigned short wIdle;				// Zusätzliche NOP cycles für 10 µS 
unsigned char mMask = 1;	                // Die PIN-Maske  
unsigned char mLev = Level;	
	for (iX = 0; iX < PinNr; iX++)
		mMask <<= 1;		       // BitNr --> Bit-maske
	pPort->bDdr &= ~mMask;  	       // define PINx as Input
	mLev &= mMask;			       // Level (0 or 1)
	while (!((pPort->bPin & mMask) ^ mLev))	// Warten auf PIN != Level
	{
		wCounter++;
		if (!wCounter) return (0);	// overflow --> return 0
	}				
	wCounter = 0;				// reset
	while ( (pPort->bPin & mMask) ^ mLev)	// wait for starting edge PIN == Level
	{
		wCounter++;
		if (!wCounter) return (0);	// overflow --> return 0
	}				
	wCounter = 0;				// reset

Soweit alles klar. Bei dem folgenden Code muß man je nach verwendetem Optimizer die Verzögerung anpassen. Allerdings muß die gesamte Schleife berücksichtigt werden. Ziel war: 

(F_CPU / 100000) Anzahl der notwendigen cycles für 10 µS
Bei 8 MHZ ergibt das z.B. 80 Cycles

Das Schleifen-Grundmuster wurde erstmal übersetzt (der Optimizer war auf "Standard" gestellt), und die *.LSS-File wurde kontrolliert. Man konnte die Cycles nachzählen, die gesamte Schleife würde 16 Cylcles brauchen, + 6 Cycles für jede zusätzliche innere "Idle" Schleife. Dei erste Rechnung ergab also 

16 + (n - 1) * 6 = 80  cycles  also  6 * n = 70 --> n = 70 / 6

das wäre eine Dezimalzahl, die man nicht brauchen kann. Kürzer geht die Schleife nicht, aber länger, durch 4 zusätzlich "NOP" (4 * 1 Cycle). Das ergab dann 

20 + (n - 1) * 6 = 80  cycles  also  6 * n = 66 --> n = 66 / 6 --> 11

Somit das konkrete Endprodukt: 

20 + (n - 1) * 6 = F_CPU / 100000

// start counting -------------------------------------------------------
	while (!((pPort->bPin & mMask) ^ mLev))	// zählen bis PIN != Level
	{
		wIdle =  11;   // Idle cycles  für 10µS 8MHZ
		while (wIdle)
		{
			wIdle--;
			__asm__ __volatile ("; placeholder");
		}
		__asm__ __volatile ("nop");
		__asm__ __volatile ("nop");
		__asm__ __volatile ("nop");
		__asm__ __volatile ("nop");
		wCounter++;
		if (!wCounter) return (0);	// overflow (too long) --> return 0
	}
	return (wCounter);       // ergebnis (1 - 65535) 
}

Diese Rechnung läßt sich wahrscheinlich nicht wirklich gut zu einer einfachen Formel für jede CPU-Frequenz verallgemeinern. Aber es sollte gezeigt werden, wie man zum Ziel kommen könnte, ohne gleich ein Assembler-Programm zu schreiben. Die Cycles der Befehle findet man übrigens im Datasheet des Controllers.

GCC GNU-Assembler (Signallänge messen)

Das gleiche Beispiel, diesmal aber konsequenterweise gleich als GNU-Assembler-Modul. Beim Hauptprogramm ändert sich nur die Funktionsdefinition auf "extern" 

extern unsigned short PulseIn(IO_REG* pPort, unsigned char PinNr, 
                                                     unsigned char Level);

In die Makefile wird diese Assembler-Source dazugeschrieben. Der Filetyp MUSS entweder ".S" heissen, oder per Kommandozeilen-Option "--assembler-with-cpp" muss gesagt werden, um welchen Dateityp es sich handelt. Und diese Source sieht folgendermassen aus: 

#include <avr/io.h>


#ifndef F_CPU
#define F_CPU 8000000
#endif


#define wDiv1  (F_CPU / 100000)
#define wIdle  (wDiv1 - 9) / 3			// Idle cycles  für 10µS 8MHZ
#define wNop   (wDiv1 - 9 - wIdle * 3)		// addit. Nops für 10µS 8MHZ

Das ist wieder die Rechnerei mit den Cpu-Cycles. Der Vorteil in Assembler ist es, daß wir nun selbst die Anzahl bestimmen können. Weiter unten wird man sehen, daß die Zählschleife 9 Cycles benötigt, plus n * 3 Cycles für die zusätzliche Idle-Schleife. Das ergibt 

wIdle = (wDiv1 - 9) / 3

das ergibt einen Divisionsrest von 0, 1 oder zwei 

wNop =  (wDiv1 - 9 - wIdle * 3)

die werden unten dann mit "NOP" aufgefüllt


Für die Struktur IO_REG müssen wir nun ein Äquivalent schreiben 

#define bPin 	 	0
#define bDdr 	 	1
#define bPort 		2


 .global PulseIn
 .func	PulseIn
// r24:r25 R22:r23 r20:r21
  • .global macht die Funktions-Adresse allen anderen Projekt-Module bekannt (die schreiben dafür "extern" in den function-header
  • .func daß es eben eine Funktion mit diesem Namen ist
  • r24:r25 R22:r23 r20:r21 Die Übergabe der Argumente erfolgt immer mit dem Registerpaar r24:25, und dann absteigend für die weiteren Argumente 
PulseIn:
	movw	r30, r24	; Pointer-Reg '''Z''' für IO_REG*   

	in	r24, 0x3F			; SREG
	push 	r24
        cli

	clr	r18		; counter lo
	clr	r19		; counter hi
; Umwandeln der Pin-Nummer in eine Bit-Maske----------------------
	ldi	r21, 0x01	; 
Shift:  
	tst	r22		; Pin-# ?
	breq	ShiftX		;
	rol	r21		; shift left Mask
	dec	r22		; count
	rjmp	Shift           ; repeat
ShiftX:    
; setzen Pin auf Input 
	mov	r24, r21	; 
	com	r24		; 1-compl Maske
	ldd	r25, Z+bDdr 	; Register  DDRx
	and	r25, r24	; auf Input setzen
	std	Z+bDdr, r25	;

	and	r20, r21	; Level Argument (#3) & Maske
; warten auf Pin-Level <> Argument  
Wait_1:  			; wait for Pin state change
	ld	r24, Z		; bPin   (IO_REG* + 0)
	and	r24, r21	; mask pin
	cp	r24, r20	; argument ?
	brne	Wait_1X		; unequal, exit wait-1
	subi	r18, 0xFF	; Counter++, aber umgesetzt auf addieren low(-1)
	sbci	r19, 0xFF	;                                        high(-1)
	brne	Wait_1		; repeat
	rjmp	FuncExit	; overflow counter --> function Exit 
Wait_1X:  
	clr		r18				; counter reset lo
	clr		r19				; counter reset hi	

; warten auf Pin-Level = Argument  (startbedingung)
Wait_2: 			; wait for count-start edge
	ld	r24, Z		; bPin   (IO_REG* + 0)		
	and	r24, r21		
	cp	r24, r20		
	breq	Wait_2X		; gotcha ! 
	subi	r18, 0xFF	; s.o.	
	sbci	r19, 0xFF	; s.o.	
	brne	Wait_2		; repeat	
	rjmp	FuncExit	; overflow counter --> function Exit 
Wait_2X:  
	clr		r18				; counter reset lo
	clr		r19				; counter reset hi

Jetzt kommt wieder die Zählschleife, wo alle Cycles gezählt werden müssen 

;---------------------------------------------------------
; start counting loop 	 
;---------------------------------------------------------
Wait_C:  						 
	ld	r24, Z		; 2cyc
	and	r24, r21	; 1cyc
	cp	r24, r20	; 1cyc
	brne	FuncExit	; 1/2cyc 	Pin <> Argument
		
	ldi	r24, wIdle	; 1cyc
Idle:
	dec	r24		; 1cyc
	brne	Idle		; 2  / 1cyc 
#if (wNop > 0)          ; wenn divisionrest (s.o.)
	#if (wNop == 2) 
		nop		; 1cyc	 ein zweites nop einfügen
	#endif		
	nop			; 1cyc	 ein nop einfügen 	
#endif		
	subi	r18, 0xFF	; 1cyc
	sbci	r19, 0xFF	; 1cyc
	brne	Wait_C		; 2cyc	 
FuncExit:
	pop 	r24
	out	0x3F, r24 	; SREG

	movw	r24, r18	; return (counter)
	ret
.endfunc
.end
  • Ein Funktionsergebnis wird immer mit r24:r25 zurückgegeben
  • Anmerkung: das Umsetzen der Zähler-Inkrementierung (counter++) auf 
subi	r18, 0xFF
sbci	r19, 0xFF

ist notwendig, weil es für 16-Bit keine inkrement-Anweisung gibt. Nur für die Registerpaare r24:r25 - r30:r31 gibt es "ADIW". Daß dieser Befehl aber dann ebenso 2 Cycles braucht, hilft es im Grunde gar nichts.

  • Noch etwas: Da ja bei der Zählung keine Interrupts erwünscht sind, werden während der Funktion die Interrupt generell disabled. Vielleicht sind sie das aber garnicht.

Gängig ist der folgende Weg:

  • Wir sichern zu Beginn das Status-register (wo dieser enable-Flag ja drinnen steht)
  • dann machen wir so oder so CLI (disable Interrupts)
  • Am Ende sagen wir aber nicht "SEI", sondern stellen einfach nur das SREG wieder her, zusammen mit dem Global Interrupt enable-Flag. Dadurch wird der Zustand einfach wieder hergestellt.

Zu Beginn: 

        in	r24, 0x3F	; SREG
	push 	r24             ; sichern auf den Stack
        cli                     ; disablen Interrupts

Am Ende: 

	pop 	r24             ; holen vom Stack
	out	0x3F, r24 	; SREG wiederherstellen

Externe Interrupts

Dieses kleine Beispiel demonstriert, wie man in Bascom und GCC Interrupt-Routinen anlegt. Also Programmzeilen, die nur dann ausgeführt werden, wenn ein Low/High Pegel an einem bestimmten PIN eines Controllers wechselt. Bei einem solchen Wechsel wird das Hauptprogramm unterbrochen und die Interrupt-Routine aufgerufen. Anschließend wird das Hauptprogramm wieder weiter ausgeführt als sei nix gewesen. In diesem Beispiel macht das Hauptprogramm garnichts, es ist nur eine Endlosschleife. Die Interruptroutine schalten bei jedem Aufruf den Zustand einer LED um.

BasCom (Externe Interrupts)

  $regfile = "m32def.dat"  'z.B. rn-control 
  $framesize = 32 
  $swstack = 32 
  $hwstack = 32 
  $crystal = 16000000                 'Quarzfrequenz 
  $baud = 9600 

  Config Pinc.2 = Output  'An dem PIN sollte LED sein 
  Led3 Alias Portc.2 'Hier geben wir der Definition einen schöneren Namen 
  Config Int0 = RISING  'Interrupt bei steigender Flanke

  On Int0 Irq0  'Festlegen wo bei externem Interrupt hin gesprungen wird
  Enable Int0   'Diesen Interrupt aktivieren
  Enable Interrupts  'Alle aktivierten Interrupts einschalten
  Do  'Endlosschleife
  Loop 
  End 

  'Interrupt Routine wird immer ausgelöst wenn der Pegel von 0 auf 1 am
  'INT0 (Pin 18 PD2) Eingang wechselt 
  Irq0: 
    Toggle Led3 
  Return

GCC (Externe Interrupts)

Das GCC-Beispiel, das die gleiche Aufgabe erfüllt: 

#include <avr/io.h>
#include <avr/interrupt.h>
#include <avr/signal.h>

#define LED3 (1 << PC2)                         

/* Interrupt Routine wird immer ausgelöst wenn der Pegel von 0 auf 1 am
   INT0 (Pin 18 PD2) Eingang wechselt */
SIGNAL (SIG_INTERRUPT0)
{
  PORTC ^= LED3;				// Pin wechseln
}

//-----------------------------------------------------
int main()
{
  /* Ports und Interrupts initialisieren */
  DDRC |= LED3;					// PC2 als Ausgang
  DDRD &= ~(1 << DDD2);				// PD2 als Eingang (ext. Interrupt 0)
  MCUCR |= ((1 << ISC01) | (1 <<ISC00));	// steigende Flanke an INT0 erzeugt einen Interrupt  
  GICR  |= (1 << INT0);				// Diesen Interrupt aktivieren 

  sei();        				// Alle aktivierten Interrupts einschalten

  while(1);					// Endlosschleife 
}

AVRStudio Assembler (Externe Interrupts)

.NOLIST                    ; List-Output unterdrücken
 .INCLUDE <m32def.inc>       ; das gibt es für jeden Controllertyp
 .LIST                      ; List-Output wieder aufdrehen
 .CSEG                      ; was nun folgt, gehört in den FLASH-Speicher

 #define LED3 		PC2                         

 ;------------------------------------------------------
 ;     Start Adresse 0000
 ;------------------------------------------------------
 RESET:
 	jmp INIT           ; springen nach "INIT"

 .ORG  INT0ADDR			; Vector für INT0
	jmp		IsrInt0

 .ORG INT_VECTORS_SIZE    ; dadurch haben wir für die Vektoren Platz gelassen
 INIT:  
 ;------------------------------------------------------
 ;     INITIALIZE
 ;------------------------------------------------------
 	ldi 	r24,high(RAMEND)     ;Stack Pointer setzen 
 	out 	SPH,r24              ; "RAMEND" ist in m32def.inc (s.o.) festgelegt
 	ldi 	r24,low(RAMEND)      ; 
 	out 	SPL,r24              ;

	sbi	DDRC,  LED3			; PC2 als Ausgang
	cbi 	DDRD,  PD2			; PD2 als Eingang (ext. Interrupt 0)
	in	r24, MCUCR			; steigende Flanke an INT0 erzeugt einen Interrupt  
	ori	r24, (1 << ISC01) | (1 << ISC00) 
	in	r24, GICR
  	ori	r24,  INT0			; Diesen Interrupt aktivieren 
	out	GICR, r24

	sei        				// Alle aktivierten Interrupts einschalten

 ;------------------------------------------------------
 ;   HAUPTSCHLEIFE
 ;------------------------------------------------------
 Hauptschleife: 
    rjmp 	Hauptschleife         ; immer wiederholen 

 ;------------------------------------------------------
 ;   INTERRUPT
 ;------------------------------------------------------
IsrInt0:
	push	r22                   ; In diesem Beispiel eigentlich nicht notwendig
	push	r24                   ; In diesem Beispiel eigentlich nicht notwendig
	in	r24, SREG             ; In diesem Beispiel eigentlich nicht notwendig
	push	r24                   ; In diesem Beispiel eigentlich nicht notwendig

	ldi	r22, (1 << LED3)
	in	r24, PORTC
	eor	r24, r22
   	out	PORTC, r24

	pop	r24                   ; In diesem Beispiel eigentlich nicht notwendig
	out	SREG, r24             ; In diesem Beispiel eigentlich nicht notwendig
	pop	r24                   ; In diesem Beispiel eigentlich nicht notwendig
	pop	r22                   ; In diesem Beispiel eigentlich nicht notwendig
	reti

Bemerkung: die PUSH / POP Befehle sind in diesem Sonderfall, daß in der Hauptschleife nichts geschieht, überflüssig. Aber man sollte sich angewöhnen, in eine ISR-Routine den Status und die verwendeten Register zu sichern.

State Machine

Eine State Machine ist ein Programmier-Werkzeug.

Oft besteht ein Programmcode aus langwierigen if-then-else-Abfragen bzw switch-case oder select Anweisungen. Ein Beispiel für solchen Code ist die Menüsteuerung in einem Händi. Je nachdem, in welchem Menü-Punkt man sich befindet, sind unterschiedliche Aktionen möglich oder Tasten unterschiedlich belegt, oder eine Taste hat keine Funktion. Ein weiteres Beispiel kann ein Roboter sein, der zwischen verschiedenen Zuständen oder Aufgaben hin- und herwechselt: Gegenstand suchen, Gegenstand gefunden, Lichtquelle suchen, Akku muss geladen werden, Bedien-Modus (evtl. auch über Menu-Struktur), oder was auch immer denkbar ist. Und selbst Hardware wie die Zustände des TWI bei ATmega sind als State-Machine beschrieben.

Für kleinere Aufgaben kommt man mit dem if-else-Ansatz schnell voran. Bei kompexeren Dingen schreibt man aber immer einen fast gleichen Abfrage-Code, der sich nur durch Kleinigkeiten unterscheidet. Zum einen wuchert der Code schnell aus und wird unübersichtlich, zum anderen wünscht man sich, schnell und zentral die Struktur-Informationen zu bündeln, und von dem immer gleichen Code zu befreien.

Eine State-Machine löst dieses Problem.

Damit spart man nicht zuletzt auch deutlich Platz! Denn die Übergangs- und Zustands-Tabellen einer State-Machine enthalten die reinen Nutz-Informationen, die sonst quer verstreut im Code als Werte von Abfragen enthalten sind. Dadurch befreit man das Programm von jeglichem Ballast.

Zusätzlich trennen wir dadurch die Implementierung von den Funktionen, die jeweils ausgelöst werden. Das schafft Klarheit und Struktur, ohne ineffizient zu sein.

Die Aktionen, die auszuführen sind, können zugeordnet werden. Etwa

  • bei Zustandsänderung von A nach B
  • wenn man einen Zustand X betritt
  • während Zustand Y immer wieder eine Aktion ausführen lassen, evtl. in einem bestimmten Zeitraster

Weil das ganze sehr universell ist, soll als Code-Beispiel exemplarisch eine der bekanntesten und universellsten State-Machinen überhaupt gezeigt werden: Eine Turing-Maschine (TM).

Auch sie hat unterschiedliche Zustände, sowie eine Eingabe (das unendlich lange "Band"). Von dort liest sie ein Zeichen, und anhand ihres Zustands und des gelesenen Zeichens führt sie eine einfache Aktion aus:

  1. Sie schreibt ein Zeichen an die aktuelle Bandposition (oder schreibt nichts)
  2. verschiebt den Schreib-/Lese-Zeiger des Bands um maximal eine Position nach links/rechts (oder bleibt auf der Position stehen)
  3. und nimmt einen neuen Zustand an (oder bleibt eben im alten Zustand)

Das Beispiel implementiert eine kleine Turing-Maschine (TM), die eine Eingabe aus n Einsen 1 bekommt, die mit einem Ende-Zeichen (dargestellt als .) abgeschlossen ist. Die TM verdoppelt diese Eingabe, indem sie nochmal n Einsen und ein Ende-Zeichen rechts dranhängt. Nimmt man die Einsen als Repräsentation der Zahl n, kann das als Multiplikation mit 2 gedeutet werden. Im Beispiel bleibt aber noch ein Trennzeichen zwischen den Einser-Gruppen übrig.

Eine Eingabe könnte auch irgend etwas anderes sein: Ein Tastendruck, empfangenes Kommando über eine Schnittstelle, Sensor- oder Zähler-Wert, etc.

Unsere TM hat 7 Zustände: START (S), S1 bis S5, und END (E). Beobachten wir mal, wie sie arbeitet. Das Zeichen unter dem Schrei-/Lesekopf ist rot, und der Schnappschuss entstand, bevor die TM ihre Aktion gemacht hat. Falls der Bandzustand noch undefiniert ist, wird das als ? angezeigt.

Arbeitsschritte unserer Turing-Maschine
mit der Eingabe "11."

S:: 11.???
S1: .1.???
S1: .1.???
S2: .1.???
S3: .1.1??
S4: .1.1.?
S4: .1.1.?
S5: .1.1.?
S5: .1.1.?
S:: 11.1.?
S1: 1..1.?
S2: 1..1.?
S2: 1..1.?
S3: 1..11?
S4: 1..11.
S4: 1..11.
S4: 1..11.
S5: 1..11.
S:: 11.11.
E:: 11.11.
Lauf ausgeführt.

Die Ausgabe wurde übrigens mit dem C-Beispiel erstellt, das aus der gleichen Quelle für einen PC erzeugt und dort laufen gelassen wurde!

Suchen und Finden

In dem Beispiel wird mit Tabellen (Arrays) gearbeitet, in denen nach Informationen wie "Zustand" oder "Übergangsfunktion/Aktion" gesucht werden. Dafür gibt es verschiedene Möglichkeiten, die alle ihre Vor- und Nachteile haben.

Bei einer Maschine mit N Zuständen hat man schon rund N2 Möglichkeiten, von einem Zustand in einen anderen (evtl. den gleichen) Zustand zu gelangen. Es ist auch denkbar, daß es noch mehr Möglichkeiten für die Zstandswechsel gibt, wenn auf unterschiedlichen Wegen von X nach Y gelangt werden kann.

Zugriff über den Index (Position)
Damit findet man sehr schnell die Information. Aus der Tabelle der Zustände wird der Zustand mit der Nummer n gelesen, indem man auf das n-te Element zugreift. Die Zustands-Nummer muss nicht im Zustand selber gespeichert werden. Diese Art des Findens eignet sich für dicht besetzte Tabellen, in denen es kaum/keine Lücken gibt. (Falls es welche gibt, muss man das erkennen können). Im Beispiel wird auf die Zustands-Tabelle so zugegriffen, auch wenn sie dort recht leer ist. In der Praxis sieht das aber oft anders aus.
Tabelle durchsuchen
Diese Herangehensweise eignet sich für Daten, die eine fast leere ("dünn besetzte") Tabelle zur Folge hätten. Im Beispiel wird die Tabelle mit den Übergangs-Beschreibungen durchsucht. Dazu braucht man einen Schlüssel. Im Beispiel wird dieser gebildet aus dem aktuellen Zustand der Maschine und dem vom Band gelesenen Zeichen. Für jeden existierenden Übergang gibt es dann einen Eintrag in der Tabelle, allerdings ohne Lücken dazwischen.
Tabelle binär durchsuchen
Die beim Suchen verwendet Tabelle ist zwar kompakt weil sie keine Lücken hat, aber man muss sich im Zweifelsfalle jeden Eintrag anschauen, um einen Eintrag zu finden oder um zu Erkennen, daß es gar keinen Eintrag gibt. Das geht ab einer bestimmten Tabellengröße wesentlich schneller, wenn man eine binäre Suche verwenden kann (im Beispiel nicht verwendet). Dadurch reduziert sich die Zeit zum Durchsuchen einer Tabelle mit M Einträgen von der Größenordnung M zur Größenordnung log2(M). Es ist jedoch etwas Programmierung zu leisten, und für sehr kleine Tabellen ist die binäre Suche unterlegen. Bei einer Tabelle mit 100 Einträgen braucht man 100 Vergleiche ohne binäre Suche und ca 8 Vergleiche mit binärer Suche.

GCC (State Machine)

Der C-Code ist etwas länger, weil wir damit auch noch die Ausgabe erzeugen und den Code auf einem PC ausführen/testen können. Diese (relative) Plattform-Unabhängig ist typisch für C. Ausserdem machen wir einen kleinen Konsistenz-Test.

Besonders interessant ist die Möglichkeit, Funktionen indirekt aufzurufen. Dadurch können wir auch Funktions-Adressen in die Datenstrukturen aufnehmen und später aufrufen! In einer Objekt-orientierten Sprache würden diese Funktionen den Methoden eines Objektes entsprechen, während die "normalen" Daten das Analogon zu den Eigenschaften eines Objekts sind.

Tabelle: Flash-Verbrauch von avr-gcc in Byte
Funktion
turing_lauf() 136 Band erzeugen und Eingabe hinkopieren
turing() 144 TM laufen lassen
job_S2_write1() 16 ein Handler
job_S3_write0() 14 ein Handler
Tabelle
states[] 14 die Zustände
transits[] 54 die Übergänge
Lib-Funktion
strcpy() 14 Zeichenkette kopieren

Systemübergreifende Includes und Defines 

////////////////////////////////////////////////////////////
// Systemübergreifende Includes und Defines
////////////////////////////////////////////////////////////
#include <inttypes.h>
#include <string.h>

Systemabhängige Includes und Defines 

////////////////////////////////////////////////////////////
// Systemabhängige Includes und Defines
////////////////////////////////////////////////////////////
#ifdef __AVR__

// Für AVR machen wir Flash-Zugriff, denn die Tabellen unten
// werden niemals verändert.
// (falls das nötig scheint, hat man mit Sicherheit einen Design-Fehler) 
#include <avr/pgmspace.h>

#else // __AVR__

// Auf einem PC machen wir Ausgaben und bilden 
// AVR-spezifisches Zeug auf Standard-C ab.
#include <stdio.h>
#define PROGMEM
#define pgm_read_byte(addr)  (*(addr))
#define pgm_read_word(addr)  (*(addr))
#define pgm_read_dword(addr) (*(addr))

#endif // __AVR__

Verwendete Datenstrukturen definieren 

////////////////////////////////////////////////////////////
// Verwendete enums und Strukturen
////////////////////////////////////////////////////////////

// Zustände unserer Turing-Maschine
enum
{
    TM_FATAL = 0, // wir haben einen Fehler in der Beschreibung!
    TM_START,
    TM_S1, TM_S2, TM_S3, TM_S4, TM_S5,
    TM_END
};

// Die Aktion:
// Wir schreiben 'wert' auf das Band
// (oder nichts, falls wert == -1),
// verschieben den Schreib/Lesekopf um 'go' (-1, 0, 1)
// und setzen den neuen Zustand (state) auf 'state'
//
// Um effektiv auf den Flash zuzugreifen, ist action_t eine Union,
// die ein Doppelwort (32 Bit) überlagert.
typedef union
{
    struct
    {
        char    wert;
        char    go;
        uint8_t state;
    };
    uint32_t as_dword;
} action_t;

// Typ-Definition für eine Default-Aktion:
// Die Funktion bekommt als Parameter ein char (vom Band gelesener Wert)
// und einen Zeiger auf das action-Objekt
typedef void (*job_t)(char, action_t*);

// state_t fasst den Zustand der Turing-Maschine zusammen.
// Bei einem Beispiel aus der Praxis würde hier wahrscheinlich
// einiges mehr drin stehen.
// Die Zustands-Nummer muss für dieses Beispiel
// nicht gespeichert werden
typedef struct
{
    job_t job;
} state_t;

// Die Übergangsfunktion:
// Wenn wir in Zustand Nr. 'state' sind und 'wert' vom Band lesen,
// dann führen wir die Aktion 'action' aus.
// Ist kein Übergang definiert, liefert uns die job-Funktion
// in der state_t Struktur die Aktion.
typedef struct
{
    uint8_t  state;
    char     wert;
    action_t action;
} transit_t;


main-Funktion, Ausgaberoutine für den PC 

////////////////////////////////////////////////////////////
// (Modul-)Globale Variablen, Prototypen
////////////////////////////////////////////////////////////

int turing (char*);
int turing_lauf (char*);

// 'size' und 'band0' brauchen wir nur für die Ausgabe
// die TM braucht davon nichts zu wissen
size_t size;
char* band0;

void job_S2_write1 (char, action_t*);
void job_S3_write0 (char, action_t*);

////////////////////////////////////////////////////////////
// Das Hauptprogramm
////////////////////////////////////////////////////////////

#ifdef __AVR__

// Auf einem AVR machen wir nichts weiter,
// als die Turing-Maschine auf die Eingabe "11." loszulassen
int main (void)
{
    return turing_lauf ("11");
}

#define print_band(...)

#else // __AVR__

// Auf dem PC lesen wir die Eingabe von der Kommandozeile,
// füttern die Turing-Maschine damit und schreiben raus,
// was die Maschine so werkelt.

// Markiert die aktuelle Position als rot
// Systemabhängiger Zeilenumbruch
// Druckbares Zeichen '.' für Stringende (nur für die Ausgabe)
#define HEAD1_STR "<font color=\"red\">"
#define HEAD2_STR "</font>"
#define NEW_LINE  "<br/>\n"
#define ENDE_CHAR '.'

int main (int argc, char *argv[])
{
    int ok = 0;
    
    if (argc > 2)
    {
        printf ("Aufruf: %s 1111...11\n", argv[0]);
        return -1;
    }

    if (1 == argc)        ok = turing_lauf ("");
    if (2 == argc)        ok = turing_lauf (argv[1]);

    if (!ok)
    {
        printf ("Turing-Maschine ist unvollständig!" NEW_LINE);
        return -1;
    }
    
    printf ("Lauf ausgeführt." NEW_LINE);
    return 0;
}

// Schnappschuss des Bands ausdrucken.
// Ende-Zeichen '\0' muss für die Ausgabe durch ein druckbares Zeichen
// dargestellt werden.
void print_band (char *b0, char *b, uint8_t state)
{
    size_t i;

    if (TM_FATAL == state)       printf ("Fehler!: ");
    else if (TM_START == state)  printf ("S:: ");
    else if (TM_END == state)    printf ("E:: ");
    else                         printf ("S%d: ", state - TM_START);

    for (i=0; i<size; b0++, i++)
        printf ((b0 == b) ? HEAD1_STR "%c" HEAD2_STR: "%c", *b0 ?: ENDE_CHAR);
    
    printf (NEW_LINE);
}

#endif // __AVR__

Die eigentliche Turing-Maschine

Zuerst müssen wir anhand der Eingabe (input) einen hinreichend grossen Speicherbereich besorgen, denn bei der Implementierung wollen wir uns nicht auf eine bestimmte Größe festnageln. Eine Turing-Maschine selbst hat keine Vorstellung von der Größe des Bands, auf dem sie ihre Arbeit tut. Wir verwenden ein dynamisches Array, denn malloc ist der Overkill und wird auch nicht benötigt. 

////////////////////////////////////////////////////////////
// Die Turing-Maschine laufen lassen:
// Dazu müssen wir ihr ein ausreichend langes Band zur
// Verfüging stellen, da sie die Eingabe "verdoppelt".
////////////////////////////////////////////////////////////
int turing_lauf (char *input)
{
    // Doppelte Länge und 2 * '\0'
    size = 2 + 2*strlen (input);
    char band[size];

    // Wird eigentlich nur auf dem PC gebraucht, aber egal...
    // Undefnierte Zeichen als '?' anzeigen
    band0 = band;
    memset (band, '?', size); 

    // Eingabe aufs Band kopieren
    strncpy (band, input, size);

    // Und los geht's!
    return turing (band);
}

////////////////////////////////////////////////////////////
// Unsere Turing-Maschine (nicht ganz strikt,
// dafür unsere eigene!
////////////////////////////////////////////////////////////

action_t the_action;
action_t *paction = &the_action;

// return 0: Unsere Beschreibung ist unvollständig. Ergänzen/korrigieren!
// return 1: Alles ok und wir sind fertig.
int turing (char *band)
{
    // Die Zustände (für die wir default-Funktionen geschrieben haben)
    // In der Praxis wird dieses Array wohl komplett aufgefüllt sein
    static const state_t states[TM_END - TM_START +1] PROGMEM = {
        [TM_S2] = { job_S2_write1 },
        [TM_S3] = { job_S3_write0 }
    };

    // Die Übergänge:
    //       { status, wert (lies), {{ wert (schreib), go, status (neu) }}}
    // oder ausgetextet für bessere Lesbarkeit:
    //       { .status = **, .wert = **, {{ .wert = **, ...}}}
    // Falls wir einen Übergang nicht finden, schauen wir ein states[] nach,
    // was zu tun ist
    static const transit_t transits[] PROGMEM = {
        // Start: \0 -> fertig
        //        1  -> durch \0 ersetzen, rechts, S1
        { TM_START, '\0', {{ -1,   0, TM_END }}},
        { TM_START, '1',  {{ '\0', 1, TM_S1  }}},

        // \0 -> rechts, S2 (Ende-Zeichen gefunden)
        // 1 -> rechts (weitersuchen)
        { TM_S1, '\0', {{ -1,  1, TM_S2 }}},
        { TM_S1, '1',  {{ -1,  1, TM_S1 }}},

        // 1 -> rechts (weitersuchen) 
        { TM_S2, '1',  {{ -1,  1, TM_S2 }}},

        // nach links \0 suchen
        { TM_S4, '\0', {{ -1, -1, TM_S5 }}},
        { TM_S4, '1',  {{ -1, -1, TM_S4 }}},

        // nach links \0 suchen
        { TM_S5, '\0', {{ '1', 1, TM_START }}},
        { TM_S5, '1',  {{ -1, -1, TM_S5 }}}
    };

    // Initialisierungen
    // Auf 'the_action' indirekt zuzugreifen gibt noch kürzeren Code
    uint8_t state = TM_START;
    action_t *act = paction;

    // Nur für den PC
    print_band (band0, band, state);

    // Laufen, bis zum End-Zustand (TM_END)
    while (TM_END != state)
    {
        // Wert vom Band lesen
        char wert = *band;

        // Nach action in der Tabelle 'transits' suchen.
        // trans durchläuft das Array transits[]
        const transit_t *trans = & transits[0];
        char found = 0;
        uint8_t i;
        
        for (i=0; i < sizeof (transits) / sizeof (transit_t); i++)
        {
            // Zustand und Wert (Zeichen) lesen (aus dem Flash bei AVR)
            uint8_t trans_state = pgm_read_byte (& trans->state);
            char    trans_wert  = pgm_read_byte (& trans->wert);
            
            if (state == trans_state && wert == trans_wert)
            {
                // Falls gefunden:
                // 'the_action' lesen (aus dem Flash bei AVR) und fertig
                act->as_dword = pgm_read_dword (& trans->action.as_dword);

                found = 1;
                break;
            }

            // Nicht gefunden:
            // Eins weiter in der Tabelle und weitersuchen
            trans++;
        }

        // Kein Eintrag gefunden:
        // Wir führen statt dessen die default-Funktion aus
        if (!found)
        {
            job_t job = (job_t) pgm_read_word (& states[state].job);

            // Keine Aktion und keine Funktion definiert: Fataler Fehler!!!
            if (!job)
                return 0;

            // Funktion ausführen
            job (wert, act);
        }

        /////////////////////////////////////////

        // Wir haben die Aktion berechnet:
        // Wert aufs Band schreiben (falls ungleich -1)
        if (-1 != act->wert)
            *band = act->wert;

        // Schreib-/Lesezeiger verschieben
        band += act->go;

        // Zustand setzen
        state = act->state;
        
        // Nur für den PC
        print_band (band0, band, state);
    }

    // Alles paletti :-))
    return 1;
}

Indirekt aufgerufene Funktionen

Folgende Funktionen werden in der Tabelle gemerkt und gegebenenfalls aufgerufen.

Eine Zahl in die Tabelle zu schreiben, die jeweils für eine bestimmte Funktion codiert, würde die Effizienz wieder zunichte machen, weil wieder über eine lange if- oder switch/select Anweisung die richtige Funktion gefunden werden müsste.

Die Funktionen schreiben einen Wert auf Band unabhängig von dem gelesenen Wert, denn wir wissen nicht, was auf dem Band so rumsteht ausser der Eingabe.

Natürlich könnten hier auch Funktionen stehen, die Aufgaben erledigen, wenn eine Bestimmte Zustandsänderung gemacht werden soll. Als Beispiel wieder eine Menü-Struktur. Von Zustand A kommt man z.B. durch "Abbrechen" zurück nach B, oder durch "Änderungen übernehmen". Im ersten Falle würde man die Änderungen verwerfen, im zweiten Falle speichern. 

////////////////////////////////////////////////////////////
// Default-Handler, falls wir für einen Übergang (Transition)
// keine Aktion definiert haben
////////////////////////////////////////////////////////////

// Nicht alle Argumente werden benötigt,
// gleichwohl müssen (oder sollen) alle Funktionen den
// gleichen Prototyp haben. UNUSED verhindert eine GCC-Warnung.
#define UNUSED __attribute__((unused))

// Schreibt '1', nach rechts, S3
void job_S2_write1 (char wert UNUSED, action_t *ac)
{
    ac->wert  = '1';
    ac->go    = 1;
    ac->state = TM_S3;
}

// Schreibt '\0', nach links, S4
void job_S3_write0 (char wert UNUSED, action_t *ac)
{
    ac->wert  = '\0';
    ac->go    = -1;
    ac->state = TM_S4;
}

Compiler

Der Code wird übersetzt mit GCC. Falls der GCC ein avr-gcc ist, wird auf Ausgabefunktionen verzichtet und wir haben natürlich keine Übergabe-Parameter von der Kommandozeile/Shell. PC-seitig nimmt man einen "normalen" gcc. Bei Linux ist er dabei und für Windows etwa bei MinGW (Minimalistic GNU for Windows).


Bascom (State Machine)

Bei Bascom ist es leider nicht möglich, Speicherstrukturen in der Art wie bei GCC zu definieren.
Es ist weiters dem Bascom schwer auszureden, irgendeinen Wert in Hochkomma als String (mit trailing Zero) zu interpretieren. Deswegen wird, wenn notwendig, "1" als 49 (hex 0x31) und "." als 46 (hex 0x2E) geschrieben.
Und es gibt bei Bascom keine "signed bytes". Dort, wo bei GCC in den Tabellen -1 geschrieben werden kann, ist hier explizit der Wert 255 (hex 0xFF) angegeben.

Die übliche Programm-Einleitung, konkret wurde ein Atmega32 mit 8 MHZ verwendet. 

$regfile = "m32def.dat"
$crystal = 8000000
$baud = 9600
$hwstack = 32
$hwstack = 64
$framesize = 32

Hier werden konstante Werte für die Zustände festgelegt 

' ---------------------------------------------
'              states
' ---------------------------------------------
Const Tm_fatal = 0
Const Tm_start = 1
Const Tm_s1 = 2
Const Tm_s2 = 3
Const Tm_s3 = 4
Const Tm_s4 = 5
Const Tm_s5 = 6
Const Tm_end = 7

Der jeweils aktuelle Zustand wird in den folgenden Feldern geführt 

' ---------------------------------------------
'              Actual state
' ---------------------------------------------
Dim Actstate As Byte             ' einer der Zustände tm_fatal --> tm_end
Dim Actvalue As Byte             ' das aktuelle Zeichen vom "Band"
Dim Actpntr As Word              ' die "Band"-position
Dim Argument As String * 20      ' das "Band"

' ---------------------------------------------
'              Set Input
' ---------------------------------------------
 Argument = "11."

' ---------------------------------------------
'              Initial conditions
' ---------------------------------------------
 Actstate = Tm_start               ' der Anfangs-"State"
 Actpntr = Varptr(argument)        ' die "Band"position --> = erstes Zeichen


Die Hauptschleife wird solange durchlaufen, bis der Zustand entweder =Ende oder =Fehler 

   While Actstate <> Tm_end And Actstate <> Tm_fatal
      Gosub Showstate              ' Das zeigen der Situation VOR der Transition
      Actvalue = Inp(actpntr)      ' lesen vom Band
      Gosub Findsetstate           ' such state & value         
   Wend

   Print "END"                   
   Gosub Showstate                 ' Abschluß-Display
End

Eine Hilfsroutine, um den Zustand auf dem Terminal darzustellen, dem GCC-Vorbild nachempfunden: 

Showstate:
   Select Case Actstate
   Case Tm_fatal : Print "F:: ";
   Case Tm_start : Print "S:: ";
   Case Tm_s1 : Print "S1: ";
   Case Tm_s2 : Print "S2: ";
   Case Tm_s3 : Print "S3: ";
   Case Tm_s4 : Print "S4: ";
   Case Tm_s5 : Print "S5: ";
   Case Tm_end : Print "E:: ";
   End Select
   Print Argument
   Return


Hier ist die vordefinierte Tabelle. Um die Lesbarkeit zu gewährleisten, für jeden Zustand / Value eine Zeile 

' ---------------------------------------------
'  Table
' ---------------------------------------------
Statetab:
'---------stat------val---wrt--go----newsts
   Data Tm_start , 46 , 255 , 0 , Tm_end
   Data Tm_start , 49 , 46 , 1 , Tm_s1

   Data Tm_s1 , 46 , 255 , 1 , Tm_s2
   Data Tm_s1 , 49 , 255 , 1 , Tm_s1

   Data Tm_s2 , 49 , 255 , 1 , Tm_s2

   Data Tm_s4 , 46 , 255 , 255 , Tm_s5
   Data Tm_s4 , 49 , 255 , 255 , Tm_s4

   Data Tm_s5 , 46 , 49 , 1 , Tm_start
   Data Tm_s5 , 49 , 255 , 255 , Tm_s5

   Data Tm_fatal                                            ' table delimiter


Suchen State / Value in der Tabelle 

' ---------------------------------------------
'              Find Actual state & Value
' ---------------------------------------------
Findsetstate:
Dim Tabstate As Byte
Dim Tabvalue As Byte
Dim Tabwrite As Byte
Dim Tabgo As Byte
Dim Tabnewsts As Byte

   Restore Statetab                     ' setzen Tabellen-Beginn
   Do
' ----------------- Das Einlesen eines Tabelleneintrages ( = eine "data"-Zeile)
      Read Tabstate                     ' =status 
      Read Tabvalue                     ' =Value
      Read Tabwrite                     ' Schreib-Aktion (255 none, 46 (=".") oder 49 (="1")
      Read Tabgo                        ' Transport (255: -1 0:keine   1: +1)
      Read Tabnewsts                    ' der nächste Zustand

      If Tabstate = Actstate And Tabvalue = Actvalue Then        ' Vergleich state & Value
         Goto Setnewstate                                        ' In der Tabelle gefunden
      End If
   Loop Until Tabstate = Tm_fatal

Es werden solange die Tabelleeinträge gelesen, bis das Tabellenende erreicht wurde oder Zustand & Value gefunden wurden Anm: Da "Setnewstate" mit "return" endet, kann hier durchaus ein "goto" verwendet werden.

Hatte die Suche keinen Erfolg, gibt es für zwei Zustände einen Ersatz, der "Value" nicht berücksichtigen muß 

' not found---> get default:
   On Actstate Goto Dflt_dmy , Dflt_dmy , Dflt_dmy , Dflt_s2 , Dflt_s3 , Dflt_dmy , Dflt_dmy , Dflt_dmy
Dflt_dmy:
   Actstate = Tm_fatal
   Return
Dflt_s2:
   Tabwrite = 49
   Tabgo = 1
   Tabnewsts = Tm_s3
   Goto Setnewstate
Dflt_s3:
   Tabwrite = 46
   Tabgo = 255
   Tabnewsts = Tm_s4
   Goto Setnewstate

Die Übernahme der Tabellenwerte 

Setnewstate:
   If Tabwrite < 255 Then
         Out Actpntr , Tabwrite         ' nur, wenn "." oder "1" (s.o)
   End If
   If Tabgo = 255 Then                  ' negativ kann nicht gefragt werden (s.o), daher explizit
      Decr Actpntr
   Else
      Actpntr = Actpntr + Tabgo         ' 0 oder +1
   End If
   Actstate = Tabnewsts                 ' der neue Zustand
   Return

Das Programm muß garnicht auf einen realen Controller übertragen werden, auch im Bascom-Simulator ist ein tadelloser Ablauf möglich.

(Autor: PicNick)

Siehe auch

Von „https://rn-wissen.de/wiki/index.php?title=Sourcevergleich&oldid=5372“

LiFePO4 Speicher Test