🚀 go-pugleaf

Hallo!

Gestern abend gab es durch mlelstv angeregt auf #amigager im IRC eine
interessante Diskussion um die Codegenerierung für den ANSI-C-Modulo-
operator %.

Obwohl mein ursprünglicher Vorschlag sich in der Diskussion als nicht
praktikabel erwiesen hat, gibt es aber eine Abwandlung von ihm, die
durchaus sinnvoll ist:

Seien a und c WORDs (signed short). Sei b eine Konstante mit dem Wert
2 hoch n. So läßt sich für c = a%b statt

	move.w	a,d0
	divs	#b,d0
	swap	d0
	move.w	d0,c

besser

	move.w	a,d0
	tst.w	d0
	blt.s	negativ
	andi.w	#(b-1),d0
	bra.s	weiter
negativ	andi.w	#(b-1),d0
	sub.w	#b,d0
weiter	move.w	d0,c


Der offensichtliche Teil ist, daß man für positive a und 0 statt DIVS
ANDI.W nehmen kann. Der unoffensichtliche Teil ist, wie dies für nega-
tive a funktioniert. Man kann sich jedoch recht leicht klarmachen
(notfalls an Beispielen), daß aus der Tatsache, daß b-Bit-Zweierkom-
plementarithmetik eh Kongruenzklassenarithmetik modulo 2^b ist, folgt,
daß man zur Berechnung von x % 2-hoch-n vorzeichenlose und -behaftete
Zahlen x gleich behandeln kann. 

Das einzig verbleibende Problem ist, daß ANSI (bzw. sein Prophet K&R2
in A.7.6) fordert, daß (a/b)*b + a%b == a. Da / sinnvollerweise auf
DIVS zurückgreift, welches stets gen 0 rundet, muß also für a<0 auch
a%b < 0 sein, a%b also nicht den kanonischen, sondern den größten ne-
gativen Repräsentanten der Restklasse von a modulo b liefern. Deshalb
muß man das Modul b für negative a von a&(b-1) nocheinmal subtrahie-
ren.

Doch noch ein Beispiel:

	-69 % 8
	-------------
	-69 & 7 == 0xffffffbb & 0x7 == 3
	3 - 8 == -5
	-------------
	-69 % 8 == -5

Kontrolle:

	   (-69/8)*8 + -69%8
	== -8*8 + (-5)
	== -64 - 5
	== -69 [OK]

Lohn der Mühe? Ohne das initiale und terminale move.w braucht die obi-
ge Routine ohne DIVS auf einem 68000 ohne Waitstates 30 Zyklen, ein
DIVS allein braucht mal mehr, mal weniger, aber an die oder über 100.

-- __
__/// Arno Eigenwillig /\ <arno@yaps.rhein.de> \/  PGP key
\XX/   V+49-2225-5870  /\ <Arnooo @ #amigager> \/ available