11.11. Arbeiten mit Dateien

11.11.1. Endlicher Zustandsautomat

Das Problem wird einfach gelöst in dem man eine Technik benutzt die sich Endlicher Zustandsautomat nennt, ursprünglich wurde sie von den Designern digitaler elektronischer Schaltkreise entwickelt. Eine Endlicher Zustandsautomat ist ein digitaler Schaltkreis dessen Ausgabe nicht nur von der Eingabe abhängig ist sondern auch von der vorherigen Eingabe, d.h., von seinem Status. Der Mikroprozessor ist ein Beispiel für einen Endlichen Zustandsautomaten : Unser Assembler Sprach Code wird zu Maschinensprache übersetzt in der manche Assembler Sprach Codes ein einzelnes Byte produzieren, während andere mehrere Bytes produzieren. Da der Microprozessor die Bytes einzeln aus dem Speicher liest, ändern manche nur seinen Status anstatt eine Ausgabe zu produzieren. Wenn alle Bytes eines OP Codes gelesen wurden, produziert der Mikroprozessor eine Ausgabe, oder ändert den Wert eines Registers, etc.

Aus diesem Grund, ist jede Software eigentlich nur eine Sequenz von Status Anweisungen für den Mikroprozessor. Dennoch, ist das Konzept eines Endlichen Zustandsautomaten auch im Software Design sehr hilfreich.

Unser Text Datei Konvertierer kann als Endlicher Zustandsautomat mit 3 möglichen Stati desgined werden. Wir könnten diese von 0-2 benennen, aber es wird uns das Leben leichter machen wenn wir ihnen symbolische Namen geben:

• ordinary

• cr

• lf

Unser Programm wird in dem ordinary Status starten. Während dieses Status, hängt die Aktion des Programms von seiner Eingabe wie folgt ab:

• Wenn die Eingabe etwas anderes als ein Wagenrücklauf oder einem Zeilenvorschub ist, wird die Eingabe einfach nur an die Ausgabe geschickt. Der Status bleibt unverändert.

• Wenn die Eingabe ein Wagenrücklauf ist, wird der Status auf cr gesetzt. Die Eingabe wird dann verworfen, d.h., es entsteht keine Ausgabe.

• Wenn die Eingabe ein Zeilenvorschub ist, wird der Status auf lf gesetzt. Die Eingabe wird dann verworfen.

Wann immer wir in dem cr Status sind, ist das weil die letzte Eingabe ein Wagenrücklauf war, welcher nicht verarbeitet wurde. Was unsere Software in diesem Status macht hängt von der aktuellen Eingabe ab:

• Wenn die Eingabe irgendetwas anderes als ein Wagenrücklauf oder ein Zeilenvorschub ist, dann gib einen Zeilenvorschub aus, dann gib die Eingabe aus und dann ändere den Status zu ordinary.

• Wenn die Eingabe ein Wagenrücklauf ist, haben wir zwei (oder mehr) Wagenrückläufe in einer Reihe. Wir verwerfen die Eingabe, wir geben einen Zeilenvorschub aus und lassen den Status unverändert.

• Wenn die Eingabe ein Zeilenvorschub ist, geben wir den Zeilenvorschub aus und ändern den Status zu ordinary. Achte darauf, dass das nicht das gleiche wie in dem Fall oben drüber ist – würden wir versuchen beide zu kombinieren, würden wir zwei Zeilenvorschübe anstatt einen ausgeben.

Letztendlich, sind wir in dem lf Status nachdem wir einen Zeilenvorschub empfangen haben der nicht nach einem Wagenrücklauf kam. Das wird passieren wenn unsere Datei bereits im UNIX Format ist, oder jedesmal wenn mehrere Zeilen in einer Reihe durch einen einzigen Wagenrücklauf gefolgt von mehreren Zeilenvorschüben ausgedrückt wird, oder wenn die Zeile mit einer Zeilenvorschub / Wagenrücklauf Sequenz endet. Wir sollten mit unserer Eingabe in diesem Status folgendermaßen umgehen:

• Wenn die Eingabe irgendetwas anderes als ein Wagenrücklauf oder ein Zeilenvorschub ist, geben wir einen Zeilenvorschub aus, geben dann die Eingabe aus und ändern dann den Status zu ordinary. Das ist exakt die gleiche Aktion wie in dem cr Status nach dem Empfangen der selben Eingabe.

• Wenn die Eingabe ein Wagenrücklauf ist, verwerfen wir die Eingabe, geben einen Zeilenvorschub aus und ändern dann den Status zu ordinary.

• Wenn die Eingabe ein Zeilenvorschub ist, geben wir den Zeilenvorschub aus und lassen den Status unverändert.

11.11.2. Implementieren von EZ als Software

Der schwerste Teil beim arbeiten mit einer Endlichen Zustandsmaschine ist das analysieren des Problems und dem ausdrücken als eine Endliche Zustandsmaschine. That geschafft, schreibt sich die Software fast wie von selbst.

In eine höheren Sprache, wie etwa C, gibt es mehrere Hauptansätze. Einer wäre ein switch Angabe zu verwenden die auswählt welche Funktion genutzt werden soll. Zum Beispiel,

	switch (state) {
	default:
	case REGULAR:
		regular(inputchar);
		break;
	case CR:
		cr(inputchar);
		break;
	case LF:
		lf(inputchar);
		break;
	}
     

Ein anderer Ansatz ist es ein Array von Funktions Zeigern zu benutzen, etwa wie folgt:

	(output[state])(inputchar);
     

Noch ein anderer ist es aus state einen Funktions Zeiger zu machen und ihn zu der entsprechenden Funktion zeigen zu lassen:

	(*state)(inputchar);
     

Das ist der Ansatz den wir in unserem Programm verwenden werden, weil es in Assembler sehr einfach und schnell geht. Wir werden einfach die Adresse der Prozedur in EBX speichern und dann einfach das ausgeben:

	call	ebx
     

Das ist wahrscheinlich schneller als die Adresse im Code zu hardcoden weil der Mikroprozessor die Adresse nicht aus dem Speicher lesen muss—es ist bereits in einer der Register gespeichert. Ich sagte wahrscheinlich weil durch das Cachen neuerer Mikroprozessoren beide Varianten in etwa gleich schnell sind.

11.11.3. Speicher abgebildete Dateien

Weil unser Programm nur mit einzelnen Dateien funktioniert, können wir nicht den Ansatz verwedenden der zuvor funktioniert hat, d.h., von einer Eingabe Datei zu lesen und in eine Ausgabe Datei zu schreiben.

UNIX erlaubt es uns eine Datei, oder einen Bereich einer Datei, in den Speicher abzubilden. Um das zu tun, müssen wir zuerst eine Datei mit den entsprechenden Lese/Schreib Flags öffnen. Dann benutzen wir den mmap system call um sie in den Speicher abzubilden. Ein Vorteil von mmap ist, das es automatisch mit virtuellem Speicher arbeitet: Wir können mehr von der Datei im Speicher abbilden als wir überhaupt physikalischen Speicher zur Verfügung haben, noch immer haben wir aber durch normale OP Codes wie mov, lods, und stos Zugriff darauf. Egal welche Änderungen wir an dem Speicherabbild der Datei vornehmen, sie werden vom System in die Datei geschrieben. Wir müssen die Datei nicht offen lassen: So lange sie abgebildet bleibt, können wir von ihr lesen und in sie schreiben.

Ein 32-bit Intel Mikroprozessor kann auf bis zu vier Gigabyte Speicher zugreifen – physisch oder virtuell. Das FreeBSD System erlaubt es uns bis zu der Hälfte für die Datei Abbildung zu verwenden.

Zur Vereinfachung, werden wir in diesem Tutorial nur Dateien konvertieren die in ihrere Gesamtheit im Speicher abgebildet werden können. Es gibt wahrscheinlich nicht all zu viele Text Dateien die eine Grösse von zwei Gigabyte überschreiben. Falls unser Programm doch auf eine trifft, wird es einfach eine Meldung anzeigen mit dem Vorschlag das originale tuc statt dessen zu verwenden.

Wenn du deine Kopie von syscalls.master überprüfst, wirst du zwei verschiedene Systemaufrufe finden die sich mmap nennen. Das kommt von der Entwicklung von UNIX: Es gab das traditionelle BSD mmap, Systemaufruf 71. Dieses wurde durch das POSIX® mmap ersetzt, Systemaufruf 197. Das FreeBSD System unterstützt beide, weil ältere Programme mit der originalen BSD Version geschrieben wurden. Da neue Software die POSIX Version nutzt, werden wir diese auch verwenden.

Die syscalls.master Datei zeigt die POSIX Version wie folgt:

197	STD	BSD	{ caddr_t mmap(caddr_t addr, size_t len, int prot, \
			    int flags, int fd, long pad, off_t pos); }
     

Das weicht etwas von dem ab was mmap(2) sagt. Das ist weil mmap(2) die C Version beschreibt.

Der Unterschiede liegt in dem long pad Argument, welches in der C Version nicht vorhanden ist. Wie auch immer, der FreeBSD Systemaufruf fügt einen 32-bit Block ein nachdem es ein 64-Bit Argument auf den Stack gepusht hat. In diesem Fall, ist off_t ein 64-Bit Wert.

Wenn wir fertig sind mit dem Arbeiten einer im Speicher abgebildeten Datei, entfernen wir das Speicherabbild mit dem munmap Systemaufruf:

11.11.4. Feststellen der Datei Grösse

Weil wir mmap sagen müssen wie viele Bytes von Datei wir im Speicher abbilden wollen und wir außerdem die gesamte Datei abbilden wollen, müssen wir die Grösse der Datei feststellen.

Wir können den fstat Systemaufruf verwenden um alle Informationen über eine geöffnete Datei zu erhalten die uns das System geben kann. Das beinhaltet die Datei Grösse.

Und wieder, zeigt uns syscalls.master zwei Versionen von fstat, eine traditionelle (Systemaufruf 62), und eine POSIX (Systemaufruf 189) Variante. Natürlich, verwenden wir die POSIX Version:

189	STD	POSIX	{ int fstat(int fd, struct stat *sb); }
     

Das ist ein sehr unkomplizierter Aufruf: Wir übergeben ihm die Adresse einer stat Structure und den Deskriptor einer geöffneten Datei. Es wird den Inhalt der stat Struktur ausfüllen.

Ich muss allerdings sagen, das ich versucht habe die stat Struktur in dem .bss Bereich zu deklarieren, und fstat mochte es nicht: Es setzte das Carry Flag welches einen Fehler anzeigt. Nachdem ich den Code veränderte so dass er die Struktur auf dem Stack anlegt, hat alles gut funktioniert.

11.11.5. Ändern der Dateigrösse

Dadurch das unser Programm Wagenrücklauf/Zeilenvorschub-Sequenzen in einfache Zeilenvorschübe zusammenfassen könnte, könnte unsere Ausgabe kleiner sein als unsere Eingabe. Und da wir die Ausgabe in dieselbe Datei um, aus der wir unsere Eingabe erhalten, müssen wir eventuell die Dateigrösse anpassen.

Der Systemaufruf ftruncate erlaubt uns, dies zu tun. Abgesehen von dem etwas unglücklich gewählten Namen ftruncate können wir mit dieser Funktion eine Datei vergrössern, oder verkleinern.

Und ja, wir werden zwei Versionen von ftruncate in syscalls.master finden, eine ältere (130) und eine neuere (201). Wir werden die neuere Version verwenden:

201	STD	BSD	{ int ftruncate(int fd, int pad, off_t length); }
     

Beachten Sie bitte, dass hier wieder int pad verwendet wird.

11.11.6. ftuc

Wir wissen jetzt alles nötige, um ftuc zu schreiben. Wir beginnen, indem wir ein paar neue Zeilen der Datei system.inc hinzufügen. Als erstes definieren wir irgendwo am Anfang der Datei einige Konstanten und Strukturen:

;;;;;;; open flags
%define	O_RDONLY	0
%define	O_WRONLY	1
%define	O_RDWR	2

;;;;;;; mmap flags
%define	PROT_NONE	0
%define	PROT_READ	1
%define	PROT_WRITE	2
%define	PROT_EXEC	4
;;
%define	MAP_SHARED	0001h
%define	MAP_PRIVATE	0002h

;;;;;;; stat structure
struc	stat
st_dev		resd	1	; = 0
st_ino		resd	1	; = 4
st_mode		resw	1	; = 8, size is 16 bits
st_nlink	resw	1	; = 10, ditto
st_uid		resd	1	; = 12
st_gid		resd	1	; = 16
st_rdev		resd	1	; = 20
st_atime	resd	1	; = 24
st_atimensec	resd	1	; = 28
st_mtime	resd	1	; = 32
st_mtimensec	resd	1	; = 36
st_ctime	resd	1	; = 40
st_ctimensec	resd	1	; = 44
st_size		resd	2	; = 48, size is 64 bits
st_blocks	resd	2	; = 56, ditto
st_blksize	resd	1	; = 64
st_flags	resd	1	; = 68
st_gen		resd	1	; = 72
st_lspare	resd	1	; = 76
st_qspare	resd	4	; = 80
endstruc
     

Wir definieren die neuen Systemaufrufe:

%define	SYS_mmap	197
%define	SYS_munmap	73
%define	SYS_fstat	189
%define	SYS_ftruncate	201
     

Wir fügen die Makros hinzu:

%macro	sys.mmap	0
	system	SYS_mmap
%endmacro

%macro	sys.munmap	0
	system	SYS_munmap
%endmacro

%macro	sys.ftruncate	0
	system	SYS_ftruncate
%endmacro

%macro	sys.fstat	0
	system	SYS_fstat
%endmacro
     

Und hier ist unser Code:

;;;;;;; Fast Text-to-Unix Conversion (ftuc.asm) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; Started:	21-Dec-2000
;; Updated:	22-Dec-2000
;;
;; Copyright 2000 G. Adam Stanislav.
;; All rights reserved.
;;
;;;;;;; v.1 ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
%include	'system.inc'

section	.data
	db	'Copyright 2000 G. Adam Stanislav.', 0Ah
	db	'All rights reserved.', 0Ah
usg	db	'Usage: ftuc filename', 0Ah
usglen	equ	$-usg
co	db	"ftuc: Can't open file.", 0Ah
colen	equ	$-co
fae	db	'ftuc: File access error.', 0Ah
faelen	equ	$-fae
ftl	db	'ftuc: File too long, use regular tuc instead.', 0Ah
ftllen	equ	$-ftl
mae	db	'ftuc: Memory allocation error.', 0Ah
maelen	equ	$-mae

section	.text

align 4
memerr:
	push	dword maelen
	push	dword mae
	jmp	short error

align 4
toolong:
	push	dword ftllen
	push	dword ftl
	jmp	short error

align 4
facerr:
	push	dword faelen
	push	dword fae
	jmp	short error

align 4
cantopen:
	push	dword colen
	push	dword co
	jmp	short error

align 4
usage:
	push	dword usglen
	push	dword usg

error:
	push	dword stderr
	sys.write

	push	dword 1
	sys.exit

align 4
global	_start
_start:
	pop	eax		; argc
	pop	eax		; program name
	pop	ecx		; file to convert
	jecxz	usage

	pop	eax
	or	eax, eax	; Too many arguments?
	jne	usage

	; Open the file
	push	dword O_RDWR
	push	ecx
	sys.open
	jc	cantopen

	mov	ebp, eax	; Save fd

	sub	esp, byte stat_size
	mov	ebx, esp

	; Find file size
	push	ebx
	push	ebp		; fd
	sys.fstat
	jc	facerr

	mov	edx, [ebx + st_size + 4]

	; File is too long if EDX != 0 ...
	or	edx, edx
	jne	near toolong
	mov	ecx, [ebx + st_size]
	; ... or if it is above 2 GB
	or	ecx, ecx
	js	near toolong

	; Do nothing if the file is 0 bytes in size
	jecxz	.quit

	; Map the entire file in memory
	push	edx
	push	edx		; starting at offset 0
	push	edx		; pad
	push	ebp		; fd
	push	dword MAP_SHARED
	push	dword PROT_READ | PROT_WRITE
	push	ecx		; entire file size
	push	edx		; let system decide on the address
	sys.mmap
	jc	near memerr

	mov	edi, eax
	mov	esi, eax
	push	ecx		; for SYS_munmap
	push	edi

	; Use EBX for state machine
	mov	ebx, ordinary
	mov	ah, 0Ah
	cld

.loop:
	lodsb
	call	ebx
	loop	.loop

	cmp	ebx, ordinary
	je	.filesize

	; Output final lf
	mov	al, ah
	stosb
	inc	edx

.filesize:
	; truncate file to new size
	push	dword 0		; high dword
	push	edx		; low dword
	push	eax		; pad
	push	ebp
	sys.ftruncate

	; close it (ebp still pushed)
	sys.close

	add	esp, byte 16
	sys.munmap

.quit:
	push	dword 0
	sys.exit

align 4
ordinary:
	cmp	al, 0Dh
	je	.cr

	cmp	al, ah
	je	.lf

	stosb
	inc	edx
	ret

align 4
.cr:
	mov	ebx, cr
	ret

align 4
.lf:
	mov	ebx, lf
	ret

align 4
cr:
	cmp	al, 0Dh
	je	.cr

	cmp	al, ah
	je	.lf

	xchg	al, ah
	stosb
	inc	edx

	xchg	al, ah
	; fall through

.lf:
	stosb
	inc	edx
	mov	ebx, ordinary
	ret

align 4
.cr:
	mov	al, ah
	stosb
	inc	edx
	ret

align 4
lf:
	cmp	al, ah
	je	.lf

	cmp	al, 0Dh
	je	.cr

	xchg	al, ah
	stosb
	inc	edx

	xchg	al, ah
	stosb
	inc	edx
	mov	ebx, ordinary
	ret

align 4
.cr:
	mov	ebx, ordinary
	mov	al, ah
	; fall through

.lf:
	stosb
	inc	edx
	ret