; ------------------------------------------------------------------------ ; :Program. STRING.asm ; :Contents. Implementation des Abstrakten Datentyps "STRING" ; :Author. Uwe Zaeh ; :Address. Steiner Str. 17 ; :Address. D-(W)8543 Hilpoltstein ; :History. 10.10.91, V1.0 ; :Copyright. PD, siehe auch Dokumentation ; :Language. Assembler ; :Translator. A68k ; :Support. Algorithmus für 'ShiftRight' übernommen von "StringOps" ; :Support. AMOK #39 ; ------------------------------------------------------------------------ ; Typen / Sorten: ; INTEGER (Importiert) ; CHAR (Importiert) ; STRING ; Cross-Reference-Definitionen / Operationen: XDEF _Create ;(size{d0}: INTEGER): STRING XDEF _Forget ;(string{a0}: STRING) XDEF _Enter ;(string{a0}: STRING; stelle{d0}: INTEGER, zeichen{d1}: CHAR) XDEF _Entry ;(string{a0}: STRING; stelle{d0}: INTEGER): CHAR XDEF _Copy ;(to_string{a0}, from_string{a1}: STRING) XDEF _Compare ;(string1{a0}, string2{a1}: STRING): INTEGER XDEF _Length ;(string{a0}: STRING): INTEGER XDEF _MaxLen ;(string{a0}: STRING): INTEGER XDEF _Erase ;(string{a0}: STRING) XDEF _Append ;(target_string{a0}, from_string{a1}: STRING) XDEF _Prepend ;(target_string{a0}, from_string{a1}: STRING) XDEF _AppendChar ;(target_string{a0}: STRING; char{d0}: CHAR) XDEF _PrependChar ;(target_string{a0}: STRING; char{d0}: CHAR) ; Invarianten / Axiome / Regeln: ; ; ; seien ; s,t,u: STRING ; c: CHAR ; n,m,k: INTEGER ; ; ; (0) (s # 0 nach s := Create(n)) ==> MaxLen(s) = n-1 und Length(s) = 0 ; ; ; (I) 0 < MaxLen(s) ; 0 <= Length(s) und Length(s) <= MaxLen(s) ; Length(s) = n <==> für alle m, 0 <= m <= n-1, gilt: ; Entry(s, m) # '\0' ; und ; Entry(s,n) = '\0' ; ; ; (II) sei 0 <= n <= MaxLen(s) ; Enter(s, n, c) ==> Entry(s, n) = c ; Entry(s, Length(s)) = '\0' ; ; ; (III) Compare(s,t) = 0 <==> Length(s) = Length(t) ; für alle n, 0 <= n <= Length(s), gilt: ; Entry(s, n) = Entry(t, n) ; Compare(s,t) = 0 ==> Compare(t,s) = 0 ; Compare(s,t) > 0 <==> es gibt ein n, 0 <= n <= Minimum(Length(s), ; Length(t)), für das gilt: ; 1. für alle m, 0 <= m <= n-1, gilt: ; ORD(Entry(s,m)) = ORD(Entry(t,m)) ; 2. und es gilt: ; ORD(Entry(s,n)) > ORD(Entry(t,n)) ; Compare(s,t) > 0 ==> Compare(t,s) < 0 ; Copy(t,s) ==> Compare(t,s) = 0 ; ; ; (IV) seien zunächst n := Length(s), m := Length(t), n+m < MaxLen(t) ; Append(t,s) ==> Length(t) = n+m ; Prepend(t,s) ==> Length(t) = n+m ; ; sei zunächst Compare(t,t') = 0 ; Append(t',s) ==> für alle n, 0 <= n < Length(t), gilt: ; Entry(t', n) = Entry(t, n) ; und ; für alle m, 0 <= m <= Length(s), gilt: ; Entry(t',m+Length(t)) = Entry(s,m) ; Prepend(t',s) ==> für alle n, 0 <= n < Length(s), gilt: ; Entry(t', n) = Entry(s, n) ; und ; für alle m, 0 <= m <= Length(s), gilt: ; Entry(t', m+Length(s)) = Entry(t, m) ; ; sei zunächst Length(t) = 0 ; Append(t,s) <==> Copy(t,s) ; Prepend(t,s) <==> Copy(t,s) ; ; ; (V) sei zunächst n := Length(s), n < MaxLen(s) ; AppendChar(s,c) ==> Length(s) = n+1, falls c # '\0' ; PrependChar(s,c) ==> Length(s) = n+1, falls c # '\0' ; ; sei zunächst Compare(s,s') = 0, Length(s') < MaxLen(s') ; AppendChar(s',c) ==> für alle n, 0 <= n < Length(s), gilt: ; Entry(s', n) = Entry(s, n) ; und ; für m = Length(s) gilt: ; Entry(s', m) = c ; Entry(s', m+1) = '\0' ; PrependChar(s',c) ==> Entry(s', 0) = c ; und ; für n, 0 <= n < Length(s), gilt: ; Entry(s', n+1) = Entry(s, n) ; ; Assembler - Implementation ; ========================== ; ; ; Darstellung im Speicher: ; ; ; ------------- Speicherbereich untere Grenze (ArrayBasis - 2) -------------- ; ; Offset -2 : MaxLen: INTEGER; (2 BYTE) ; Offset 0 : -- ArrayBasis und 1. ArrayElement -- <-- Array - Zeiger ; Offset 1 : 2. ArrayElement ; Offset 2 : 3. ArrayElement ; : : ; : : ; : : ; Offset (n-2) : n-1. ArrayElement ; Offset (n-1) : n. ArrayElement ; ; -- Speicherbereich obere Grenze (ArrayBasis + Maxlen) ---------------------- Exec = 4 AllocMem = -198 FreeMem = -210 speichertype = 1 MaxLen = -2 NEGSIZE = -MaxLen speicherbelegen: ; d0: Speichergröße in Bytes move.l a6,-(sp) move.l Exec,a6 move.l #speichertype,d1 jsr AllocMem(a6) move.l (sp)+,a6 ; d0 enthält Adresse vom Speicherblock, falls Belegung geklappt hat ; sonst d0 = 0 rts speicherfreigeben: ; a0: Adresse Speicherblock ; d0: Größe Speicherblock in Bytes move.l a0,a1 move.l a6,-(sp) move.l Exec,a6 jsr FreeMem(a6) move.l (sp)+,a6 rts _Create: ; d0: Size: MaxLen+1 (16-Bit Wort) (= POSSIZE) ; Retur: d0: (Adresse vom) neuen String ; d0 = 0, falls Fehler move.w d0,-(sp) ; Arraysize retten ext.l d0 add.l #NEGSIZE,d0 ; Gesamt = POSSIZE + NEGSIZE jsr speicherbelegen move.l d0,a0 beq fehler add.l #NEGSIZE,a0 ; Basis berechnen move.w (sp)+,d0 subq.w #1,d0 ; eins runter für Maxlen (wegen '\0') move.w d0,MaxLen(a0) move.b #0,(a0) ; Length = 0 move.l a0,d0 fehler: rts _Forget: ; a0: Zeiger auf String move.w MaxLen(a0),d0 ; (= POSSIZE-1) addq.w #1,d0 ; eins hoch ... ext.l d0 add.l #NEGSIZE,d0 ; GESAMT = POSSIZE + NEGSIZE sub.l #NEGSIZE,a0 ; untere Speicherbereichs-Grenze ermitteln jsr speicherfreigeben rts _Enter: ; a0: String ; d0: Stelle ( 0 ... Maxlen ) (16-Bit Wort) ; d1: Char-Element (8-Bit Wort) move.b d1,0(a0,d0.w) rts _Entry: ; a0: String ; d0: Stelle ( 0 ... Maxlen ) (16-Bit Wort) ; Retur: Element in d0 (8-Bit Wort) move.b 0(a0,d0.w),d0 rts _MaxLen: ; a0: String ; Retur: Maxlen in d0 (16-Bit Wort) move.w MaxLen(a0),d0 rts _Copy: ; a0: Zeiger auf String (Dest: to) ; a1: " " " (Source: from) (Vor.: Length # 0) move.w MaxLen(a0),d0 ; es dürfen maximal MaxLen(Dest)+1 Zeichen kopiert werden strcpy1: move.b (a1)+,(a0)+ beq strcpy2 ; falls (a1).b = 0 dbf d0,strcpy1 move.b #0,-1(a0) ; falls schon, auf jeden Fall erzwungener Abschluß strcpy2: rts _Compare: ; a0: Zeiger auf String #1 ; a1: " " " #2 ; Retur: d0 = 0, falls String1 = String2 ; d0 < 0, falls String1 < String2 ; d0 > 0, falls String1 > String2 strcmp1: cmp.b (a0)+,(a1)+ ; Inhalte nicht gleich ? bne strcmp2 ; nein .... cmp.b #0,-1(a0) ; Stringende ? bne strcmp1 ; nein, weiter vergleichen moveq.l #0,d0 ; sonst "Strings sind gleich" rts strcmp2: ble strcmp3 ; (a0) < (a1) ? moveq.l #1,d0 ; nein, dann "String1 > String2" rts strcmp3: moveq.l #-1,d0 ; (a0) < (a1) ==> "String1 < String2" rts _Length: ; a0: Zeiger auf String move.l a0,d0 length1: tst.b (a0)+ bne length1 sub.l d0,a0 move.l a0,d0 subq.l #1,d0 rts _Erase: ; a0: Zeiger auf String move.b #0,0(a0) rts ShiftRight: ; "Geheime" Prozedur ; Algorithmus von Nicolas Benezan ; a0: Zeiger auf String ; d0: Offset ; d1: Distance movem.l d2-d3/a2,-(sp) move.l a0,a2 ; a2 : Zeiger auf String move.w d0,d2 ; d2 : offset move.w d1,d3 ; d3 : Distance jsr _Length add.w d3,d0 ;Distance addieren / d0 = end cmp.w MaxLen(a2),d0 bls kannbleiben move.w MaxLen(a2),d0 kannbleiben: ; d0 = end move.w d0,d1 sub.w d3,d1 ; start = d1 = end-distance lea.l 1(a2,d1.w),a1 ; Source in a1 (+1 wegen Predecrement) lea.l 1(a2,d0.w),a0 ; Dest in a0 "" "" sub.w d2,d1 ; Position von start abziehen beq srnixkopieren srloop: move.b -(a1),-(a0) dbf d1,srloop move.b #0,0(a2,d0.w) ; auf jeden Fall einen Schlußpunkt setzen srnixkopieren: movem.l (sp)+,d2-d3/a2 rts _Prepend: ; a0: target_string ; a1: from_string movem.l a2-a3,-(sp) move.l a0,a2 move.l a1,a3 move.l a1,a0 jsr _Length ; Länge von from_string holen move.w d0,-(sp) ; und retten move.w d0,d1 move.w #0,d0 ; Offset move.l a2,a0 jsr ShiftRight move.w (sp)+,d0 beq ppnixkopieren subq.w #1,d0 pploop: move.b (a3)+,(a2)+ ; kein Offset für target_string dbf d0,pploop ppnixkopieren: movem.l (sp)+,a2-a3 rts _Append: ; a0: target_string ; a1: from_string movem.l a2-a3,-(sp) move.l a0,a2 move.l a1,a3 jsr _Length ; von target_string lea.l 0(a2,d0.w),a0 ; a0 auf Length(target_string) (Inhalt: '\0') move.w MaxLen(a2),d1 sub.w d0,d1 ; Maximale Anzahl kopierbarer Zeichen ermitteln (-1) aploop: ; die '\0' darf auf jeden Fall kopiert werden move.b (a3)+,(a0)+ beq apende ; '\0' noch mitkopieren, dann Ende dbf d1,aploop move.b #0,-1(a0) ; falls erzwungenes Ende ==> mit '\0' abschließen apnixkopieren: apende: movem.l (sp)+,a2-a3 rts _PrependChar: ; a0: target_string (32-Bit-Wort) ; d0: char (16-Bit-Wort) movem.l d2/a2,-(sp) move.l a0,a2 move.w d0,d2 move.w #0,d0 ; Offset 0 move.w #1,d1 ; Distance 1 jsr ShiftRight move.b d2,0(a2) movem.l (sp)+,d2/a2 rts _AppendChar: ; a0: target_string (32-Bit-Wort) ; d0: char (16-Bit-Wort) movem.l d2/a2,-(sp) move.l a0,a2 move.w d0,d2 jsr _Length cmp.w MaxLen(a2),d0 beq cantappend move.b d2,0(a2,d0.w) move.b #0,1(a2,d0.w) cantappend: movem.l (sp)+,d2/a2 rts END