Aktuelle Version vom 21. Juli 2011, 20:37 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 Quarz 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) 

//-----------------------------------------------------
void _writeString (const char *string) 
{ 
     while (*string) 
     {
         while (!(UCSRA & (1<<UDRE)))
         {} 

         UDR = *string++; 
     }
} 

//-----------------------------------------------------
void main()
{
     UCSRB = (1<<TXEN); 
     UCSRC = (1<<URSEL) | (1<<UCSZ1) | (1<<UCSZ0); 
     UBRRL = (unsigned char) USART_BAUD_SELECT; 

     _writeString ("Hallo, Welt!\n"); 

     // Endlossschleife nach Verlassen von main
  }

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) 

//-----------------------------------------------------
void main()
{
	char bZeichen;
	
	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
        in      r24, UDR
 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.

Zur Zeitmessung selbst gibt es prinzipiell mehrere Möglichkeiten, etwa unter Verwendung eines Timers oder indem man eine bestimmte Ahnzahl von Maschinenzyklen wartet, und so eine Zeitbasis erhält. Man sollte aber nicht dem Irrtum aufsitzen, der zweite Ansatz belege keine Systemressourcen: der Ansatz schliesst die Verwendung von Interrupts, welche evtl. für andere Zwecke aktiv sein müssen, aus bzw. es werden falsche Ergebnisse geliefert. Zudem "hängt" die Applikation während des Messvorgangs.

BasCom (Signallänge messen)

Bascom verfü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" 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 Maschinenzyklen als Maßstab nimmt, ist es in vergleichbarer Form eigentlich nur mit Inline-Assembler in Abhängigkeit von der Quarz-Frequenz zu lösen. 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.

#include <avr/io.h> 
#include <avr/delay.h> 

#define BAUD_RATE    9600 

#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 

#define NOP __asm__ __volatile ("nop")

// !!! Dieses Konstrukt ist nur für PORTA bis PORTD anwendbar.
// !!! Für PORTE bis PORTG wird es so nicht funktionieren, und man muss sich etwas
// !!! anderes überlegen, weil die Portregister für diese Ports anders angeordnet sind.
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 short wCounter = 0;			// Time Zähler
unsigned char mMask;	 	                // Die PIN-Maske  

	mMask = 1 << PinNr;		        // BitNr --> Bit-maske
	pPort->bDdr &= ~mMask;  	        // define PINx as Input
	Level &= mMask;			        // Level (0 oder mMask)

	while (Level == (pPort->bPin & mMask))	// Warten auf PIN != Level
	{
		if (0 == ++wCounter) return (0);	// overflow --> return 0
	}				

	wCounter = 0;				// reset
	while (Level != (pPort->bPin & mMask))	// warten auf PIN == Level (Startflanke)
	{
		if (0 == ++wCounter) return (0);	// Überlauf --> return 0
	}

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. In 10 µs vergehen F_CPU/100000 Zyklen, bei einen Takt von 8 MHz geschehen in 10 µs also 80 Zyklen.

Das Schleifen-Grundmuster wurde erstmal übersetzt (der Optimizer war auf "Standard" gestellt), und die *.LSS-File wurde kontrolliert. Man konnte die Zyklen nachzählen, die gesamte Schleife würde 16 Taktzyklen brauchen. Um pro Scheifendurchlauf auf 10 µs zu kommen, bauen wir noch eine innere Warteschleife mit _delay_loop_1 ein. Das Ausführen von _delay_loop_1(i) dauert 3·i-1 Zyklen. Zusätzlich sehen wir zum Verzögen noch n NOP-Operationen vor, die jeweils einen Takt dauern. Die 80 Zyklen setzen sich also folgendermassen zusammen:

80 = 16 + 3*i-1 + n

was gleichbedeutend ist mit

i = (80 - 16 + 1 -n) / 3 = (65-n)/3

Damit das beim Teilen durch 3 aufgeht und kein Rest bleibt, wählen wir n = 2 = 65 mod 3 und i ergibt sich zu i = 63/3 = 21.

	// Zeitmessung starten -------------------------------------------------------
	wCounter = 0;				// reset
	while (Level == (pPort->bPin & mMask))  // zählen bis PIN != Level
	{
		_delay_loop_1 (21);
		NOP;
		NOP;

		if (0 == ++wCounter) return (0);	// Überlauf (too long) --> return 0
	}
	return (wCounter);       // Ergebnis (0...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 "-x 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, _SFR_IO_ADDR (SREG)	; SREG sichern
	push 	r24
        cli

	clr	r18		; counter lo
	clr	r19		; counter hi
; Umwandeln der Pin-Nummer in eine Bit-Maske----------------------
	ldi	r21, 0x01	; 
	tst	r22		; Pin-# ?
	breq	ShiftX		;
Shift:  
	add	r21, r21	; shift left Mask
	dec	r22		; count
	brne	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 >= 1)         	; wenn divisionrest (s.o.)
	nop			; 1cyc	 ein nop einfügen 	
#endif		
#if (wNop >= 2) 
	nop			; 1cyc	 ein zweites nop einfügen
#endif		
	subi	r18, 0xFF	; 1cyc
	sbci	r19, 0xFF	; 1cyc
	brne	Wait_C		; 2cyc	 
FuncExit:
	pop 	r24
	out	_SFR_IO_ADDR (SREG), 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)
        out     MCUCR, R24
	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.

Für die ISR gibt es noch eine etwas ungewöhnliche Alternative, ganz ohne die Benutzung von Arbeitsregistern, und beeinflussen des Status Registers:

IsrInt0:
	sbic PORTC, (1 << LED3)  ; alten Wert testen
	rjmp LED_an
	nop                      ; Verzögerung für gleiche Laufzeit
	sbi  PORTC, (1 << LED3)  ; Port war 0, neu auf 1 setzen
	reti
LED_an:                          ; Portbit war 1 
	cbi  PORTC, (1 << LED3)  ; Portbit löschen 
	reti

Assembler-Schnippsel

In einer Hochsprache will man sich nicht mit Assembler rumbalgen. Schliesslich hat man sich für einen Compiler entschieden, damit dieser die Register-Verwaltung übernimmt, die Werte von Funktionsaufrufen verwaltet, den Code beim Betreten und Beenden einer Funktion oder Interrupt Service Routine erzeugt, etc.

Jedoch kann nicht alles, was auf der untersten Ebene möglich ist, auf Hochsprachen-Ebene dargestellt werden. Eine Bibliotheksfunktion muss eine bestimmten Ansatz wählen, und eine Sprache wie C für jeden der tausenden von Controllertypen zu erweitern und "aufzubohren", würde lediglich zu einer babylonischen Verwirrung führen.

In speziellen Fällen wird man dann Lösungen auf der untersten Ebene formulieren wollen/müssen und ist froh, die Möglichkeit der Hochsprache nutzen zu können, um Assembler-Schnippsel in den Code einzufügen.

Dabei soll hier nicht interessieren, wie der entsprechende Schnippsel in der Hochsprache nachgebildet werden könnte, sondern wie ein vorgegebener Schnippsel – teilweise auch als "Inline Assembler" bezeichnet – in den Code eingefügt wird, und wie das Interface zwischen Hochsprache und Assembler aussieht.

GNU Assembler (Assembler einfügen)

Der Schnippsel, der eingefügt werden soll, berechnet die Anzahl der gesetzten Bits in einem Byte. Der Eingabe-Wert, dessen Bits gezählt werden sollen, steht in Register r26 und wird zerstört, das Ergebnis steht in r25, der Inhalt von r24 wird zudem zersört:

   clc                  ; das Carry-Flag auf 0 setzen
   ldi r24, 0           ; Konstante 0 in Register 24 laden 
   ldi r25, 0           ; Das Ergebnis auf 0 initialisieren
bitcount_loop:
   adc r25, r24         ; 0 und Carry auf r25 addieren
   lsr r26              ; die Eingabe 1 nach rechts ins Carry schieben
   brne bitcount_loop   ; Loop, bis in der Eingabe keine Bits mehr gesetzt sind
   adc r25, r24         ; das letzte Bit nicht vergessen

GCC (Assembler einfügen)

Der einzufügende Assembler-Schnippsel ist für gcc lediglich ein String, der in die Ausgabe eingefügt wird. gcc hat keine Vorstellung davon, was innerhalb des Inline-Assembler-Schnippsels abgeht. Deshalb muss man selbst eine Verbindung zwischen Eingaberegister und -wert bzw. Ausgeberegister und -wert herstellen, und sagen, welche Register sich auf unkontrollerte Art und Weise ändern.

Bereits dieses einfache Beispiel ist tückisch. Hier erst mal der Code:

static inline unsigned char bitcount (unsigned char eingabe)
{
   uint8_t count;
   __asm__ __volatile (
      "   clc          \n"
      "   ldi r24, 0   \n"
      "   ldi %0, 0    \n"
      "0:              \n"
      "   adc %0, r24  \n"
      "   lsr %1       \n"
      "   brne 0b      \n"
      "   adc %0, r24"
         : "=&r" (count), "=r" (eingabe)
         : "1" (eingabe)
         : "r24"
   );

   return count;
}

Die einzelnen Argumente des Inline Assembler-Kommandos werden durch einen Doppelpunkt : abgetrennt, und nicht wie von C gewohnt mit einem Komma.

Argument 1: Assembler-Code: Der Text, der in die Ausgabe eingefügt werden soll (das template (die Schablone)). Dieser String wird genau so in den Ausgabestrom eingefügt, nachdem die %-Platzhalter ersetzt wurden. Die Registerzuordnungen kann man teilweise selbst wählen, indem man wie hier r24 verwendet wie im Assembler auch. Für die Variablen gibt es die Platzhalter %0, %1 und %2, denn es folgen drei Operanden (count ist Ausgabe, eingabe ist auch Ausgabe (es wird verändert!), eingabe ist Eingabe). Für die Variablen trifft gcc die Entscheidung, welche Register verwendet werden.; Weil der Schnippsel mehrfach vorkommen kann, ist es nicht möglich, der Sprungmarke in der Schleife einen festen Namen zu geben, denn das würde bei Mehrfachverwendung einen Fehler beim Assemblieren geben. Statt dessen wird in der Schleife zum nächsten auffindbaren "Wegwerf-Label" 0: gesprungen, wobei der Sprung nach rückwärts erfolgt (angegeben durch das 0b für "backward" im Sprungbefehl. Ein vorwärts wäre übrigens ein 0f für "forward". Verwendbar sind die Ziffern 0 bis 9).
Argument 2: Die Ausgabe-Operanden: Das = kennzeichnet einen Operanden als Ausgabe-Operand, und das r legt die Registerklasse fest. Die Registerklasse r umfasst alle 32 Register, denn die verwendeten Befehle sind auf alle 32 Register anwendbar. (Das gilt nicht für alle AVR-Instruktionen, so ist ldd nur mit Y- und Z-Register anwendbar.) Hinter der Registerklasse steht in Klammern der C-Ausdruck, der dem Register entspricht. Mehrere Operanden werden durch ein , voneinander getrennt.
Argument 3: Die Eingabe-Operanden: So aufgebaut wie die Ausgabe-Operanden, allerdings ohne =. Die "1" bedeutet, daß dieser Operand (Nummer 2) mit Operand 1 übereinstimmt, und sich im selben Register befindet. Daher gibt es im Assembler-String auch kein Platzhalter %2. Ausser C-Variablen sind auch komplexe Ausdrücke und Funktionsaufrufe erlaubt (je nach Constraint).
Argument 4: Die überschriebenen Register: gibt an, welche Register nach der Assembler-Sequenz keinen definierten Zustand haben (bzw. deren Zustand wertlos ist). Anstatt r24 selbst auszuwählen, hätte man auch eine C-Variable anlegen und übergeben können. Mit einer C-Variablen hätte gcc die Freiheit der Entscheidung, welches Register verwendet wird.

Der ganze Code steht innerhalb einer Inline-Funktion, wird also wie angegeben an die jeweilige Aufrufstelle von bitcount eingefügt. Dies begrenzt den Seiteneffekt, daß eingabe zerstört wird, auf die (Inline-)Funktion.

Für dieses Beispiel könnte man auch ausnutzen, dass GCC ein Register (__zero_reg__) vorsieht das immer den Wert 0 hat. Statt R24 könnte man auch also __zero_reg__ nutzen, sogar ohne es auf 0 zu setzen. Der Eintrag bei überschriebene Register würde entsprechend wegfallen.

BASCOM (Assembler einfügen)

Durch die relativ starre Registernutzung ist das Einfügen von Assembler in BASCOM vergleichsweise einfach. Der Code kann in diesem Beispiel 1:1 übernommen werden. Der Datenaustauch erfolgt in der Regel über die SRAM Addressen zu Variablen. Da die Register aus diesem Beispiel bei BASCOM zwischen den Befehlen nicht genutzt werden, kann man sie frei als temporäre Register nutzen. Siehe : Assembler_Einführung_für_Bascom-User

  $ASM
   lds r26,{Wert}       ; Datenaustausch: r26 aus Variable Wert laden
   clc                  ; das Carry-Flag auf 0 setzen   
   ldi r24, 0           ; Konstante 0 in Register 24 laden 
   ldi r25, 0           ; Das Ergebnis auf 0 initialisieren
bitcount_loop:
   adc r25, r24         ; 0 und Carry auf r25 addieren
   lsr r26              ; die Eingabe 1 nach rechts ins Carry schieben
   brne bitcount_loop   ; Loop, bis in der Eingabe keine Bits mehr gesetzt sind
   adc r25, r24         ; das letzte Bit nicht vergessen
   sts {bitzahl},r25    ; Datenaustausch: Ergebnis in Variable bitzahl speichern
  $end Asm

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 Handy. 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:

Sie schreibt ein Zeichen an die aktuelle Bandposition (oder schreibt nichts)
verschiebt den Schreib-/Lese-Zeiger des Bands um maximal eine Position nach links/rechts (oder bleibt auf der Position stehen)
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.

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 und E verschiedenen Ereignissen, die einem Zustandswechsel verursachen, hat man schon N·E Möglichkeiten für einen Zustandswechsel.

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 log₂(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

Wie oben erwähnt wurde dieses Programm auch dazu verwendet, die Ausgabe der TM zu erzeugen, und zwar auf einem PC. Der Grund, den Code direkt auf einem PC laufen zu lassen, hat mehrere Motivationen: Einerseits soll gezeigt werden, wie Plattformabhängigkeiten aus den Code herausparametrisiert werden können. Wie zu erwarten, sieht der TM-Teil des C-Codes für den PC genauso aus wie der C-Code für AVR. Zum anderen ist die Laufzeitungebung "PC" sowieso vorhanden (jedoch nicht unbedingt die Umgebung, um den C-Code für einen PC zu übersetzen, siehe dazu weiter unten).

////////////////////////////////////////////////////////////
// (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
    strcpy (band, input);

    // 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)
        {
            // Funktionszeiger 'job' aus der Struktur lesen
            job_t job = (job_t) pgm_read_word (& states[state].job);

            // Keine Aktion und keine Funktion definiert: Fataler Fehler!!!
            if (0 == 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);
    } // while (TM_END != 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 aufs 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, bzw Funktionen in die Übergangs-Tabelle eintragen, die die jeweilige Aufgabe erledigen.

////////////////////////////////////////////////////////////
// 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', geht nach rechts, wechselt zu S3
void job_S2_write1 (char wert UNUSED, action_t *ac)
{
    ac->wert  = '1';
    ac->go    = 1;
    ac->state = TM_S3;
}

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

Verwendung von Labels

Will man nicht mit Funktionen arbeiten sondern mit Sprungmarken (Labels), dann geht das ebenfalls. In der betreffenden Struktur/Union macht man ein Feld für das Label:

void **label;

und weist diesem im Initializer das Label zu:

.label = &&ein_label, ...

Das Label springt man indirekt an mit

void **alabel = ... // Wert aus Struktur besorgen
goto *alabel;
label_done:;

Und das Label selbst definiert man wie gewohnt:

ein_label:
   // mach was (evtl ein ganzer Block)
goto label_done; // oder sonst ein Label

Die Strukt muss dann eine lokale, statische Konstante sein (wie die Tabellen im Beispiel auch). Gesprungen werden kann nur innerhalb der gleichen Funktion. Der Unterschied zu Funktionen ist, daß andere Optimierungsstrategien angewandt werden können (common/dead code elimination, common subexpression elimination, kein Overhead durch Funktionsaufruf, andere Register-Verwendung, ...)

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).

Natürlich kann der Code auch von jedem AVR-Simulator ausgeführt werden: AVR-Studio, avarice, simulavr, ...

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

Sourcevergleich: Unterschied zwischen den Versionen

Ansichten