AVR-Tipps & Tricks

 

In dieser Rubrik sollen einige AVR-Stolperfallen beschrieben werden - in die insbesondere der Anfänger auch im Zusammenhang mit s’AVR gerne reintritt - und wie man diese vermeidet.

Außerdem werden an dieser Stelle s’AVR-Code-Schnipsel hinterlegt, die vielleicht hier oder dort brauchbar sind.

Der kurze Weg geht hier entlang:


Inkrement und Dekrement (9.12.2019)

Die meisten CPUs beeinflussen bei INC und DEC wenig oder keine Flags, insbesondere nicht das Carry-Flag. Letzteres hat einen besonderen Grund.

Der 68k-Befehlssatz (CISC) z. B. unterstützt zwar kein INC und kein DEC, dafür ein DBcc, das gleich alle nötigen Branch-Bedingungen perfekt abgedeckt hat (sogar True und False), obwohl es eigentlich ein "DScc" = Decrement and Skip if cc" ist (wobei cc sogar vor dem DEC abgefragt und ggf. ausgeführt wird), was für den Anfänger vielleicht etwas verwirrend ist. Bei diesem BDcc werden überhaupt keine Flags verändert.

Bei Z80 (CISC) z. B. ist der vergleichbare Befehl DJNZ etwas einfacher ausgeführt (genau genommen ist es ein Branch = relativer Sprung bei <> 0, so wie man es sich vorstellt). Auch er beeinflusst keine Flags, auch nicht das Carry bei INC und DEC.

Manche CPUs haben ein separates Auxiliary-Flag AC, das bei einem INC- oder DEC-Überlauf gesetzt wird.

Bei den 8-bit-AVR (RISC) werden bei INC und DEC nur die Flags Z,N,V und S beeinflusst, das Carry bleibt auch hier bewusst außen vor.

Man darf deshalb nicht in Versuchung geraten, bei einem 8-bit-AVR-µC folgenden einfachen s’AVR-Code zu schreiben, wenn COUNT alle Werte von 0 bis 255 aufsteigend durchlaufen soll:

    clr COUNT

    REPEAT

      .

      .

      .

      .

      inc COUNT    ; INC does not generate a carry!

    UNTIL C

denn diese REPEAT-Schleife wird entweder nur einmal durchlaufen (falls vorher oder zwischendurch das Carry anderweitig gesetzt wird) oder sie wird überhaupt kein Ende finden.

Einen solchen Programmierfehler zu entdecken, kann Zeit und Nerven kosten ...

Statt dem INC-Befehl jedesmal die Konstante +1 zu addieren, wäre dagegen eine denkbare Lösung.

Allerdings gibt es bei den 8-bit-AVR keinen "ADDI"-Befehl, sondern man muss sich in diesem Falle mit SUBI COUNT,-1 behelfen, jedoch mit der Einschränkung, dass man dann für COUNT nur die "oberen" AVR-Register R16 bis R31 verwenden kann.

Damit folgt auch gleich der nächste Fallstrick, nämlich dass das Carry beim Subtrahieren von -1 genau entgegengesetzt behandelt wird (im Vergleich zum Addieren von +1).

Mit anderen Worten:

  • Bei allen aufsteigenden Werten COUNT = 0 bis 254 entsteht bei jeder Subtraktion von -1 = 0xff immer ein Übertrag.
     
  • Erst bei der letzten Subtraktion bei Zählerstand COUNT = 255 = 0xff ensteht beim Ergebnis von 0xff-0xff = 0 kein Übertrag.

Mit dieser Erkenntnis schaut der korrekte Code schließlich so aus:

     clr COUNT

     REPEAT

      .

      .

      .

      .

      subi COUNT,-1    ; SUBI -1 must be used instead of INC

     UNTIL NOT C       ; however, the carry is handled the opposite way!

NOT C, NC und !C werden von s’AVR als gleichwertig behandelt.

Man kann beim Tippen sogar etwas länger nachdenken und zur besonderen Betonung schreiben ;-)

     UNTIL NOT NOT NOT C

Dann aber unbedingt eine ungerade Zahl von NOT oder gleich !C nehmen ...

Die umgekehrte Reihenfolge, nämlich COUNT = 255 bis 0, wird mit diesem Wissen nun besonders einfach:

     ldi COUNT,255

     REPEAT

      .

      .

      .

      subi COUNT,1

     UNTIL C        ; = -1, here the carry works the regular way

Der Vollständigkeit halber soll erwähnt werden, dass man dennoch INC und DEC nehmen kann, dann aber für einen Überlauf nicht das Carry, sondern den Wert von COUNT abfragen muss, also bei aufsteigender Zählfolge per INC:

     clr COUNT

     REPEAT

      .

      .

      .

      inc COUNT

     UNTIL COUNT == #0   ; = 256

Für diesen Fall kann man wieder alle AVR-Register R0 bis R31 verwenden, denn die Abfrage auf 0 erfolgt bei s’AVR per TST-Befehl und nicht per CPI-Befehl.

Spätestens jetzt stellt man fest, dass man das Ganze hätte einfach auch wie folgt schreiben können, denn der INC-Befehl beeinflusst zwar nicht das Carry, aber das Z-Flag:

     clr COUNT

     REPEAT

      .

      .

      .

      inc COUNT

     UNTIL Z             ; = 256

Deshalb kann hier der abschließende TST-Befehl durch s’AVR entfallen.

Bei absteigender Zählfolge per DEC schaut es für 256 Werte COUNT = 255 bis 0 mit der abschließenden Registerabfrage so aus:

     ldi COUNT,255

     REPEAT

      .

      .

      .

      dec COUNT

     UNTIL COUNT == #255 ; = -1

Hier gilt wieder die Einschränkung für COUNT nur die "oberen" AVR-Register R16 bis R31.

Für die absteigende Zählfolge hätte man ganz ohne Abfrage und ohne Register-Einschränkung wie folgt programmieren können:

     FOR COUNT := #256

      .

      .

      .

     ENDF

Allerdings durchläuft COUNT hier nacheinander die Werte 0, 255 ... 1 (dann Vorsicht beim Verwenden von COUNT innerhalb der FOR-Schleife), denn diese s’AVR-spezielle FOR-Schleife mit der Konstanten #256 ist nichts anderes als:

     clr COUNT

     FOR COUNT

      .

      .

      .

     ENDF

Bei den FOR-Schleifen wird übrigens durch s’AVR bei ENDF das FOR-Register (hier COUNT) per DEC dekrementiert, aber per BRNE an den Anfang der Schleife gesprungen (insgesamt ähnlich dem DJNZ bei Z80), denn das Z-Flag wird bei DEC bedient und das Carry eben nicht.

Für diese spezielle FOR-Schleife mit COUNT := #256 ist der von s’AVR erzeugte flache Assembler-Code sogar identisch mit REPEAT-UNTIL Z:

     clr COUNT

     REPEAT

      .

      .

      .

      dec COUNT

     UNTIL Z             ; = 256

Der Unterschied ist, dass bei der REPEAT-Schleife sowohl

    clr COUNT

als auch

    dec COUNT

im Programm getippt werden müssen, wogegen diese beiden Befehle bei dieser FOR-Schleife automatisch von s’AVR erzeugt werden.

Das fehlende Carry ist für etwas gut

Bei Betrachten der FOR-Schleife mit dem DEC-Befehl am Ende (bei ENDF) wird nun klar, warum INC und DEC das Carry gar nicht beeinflussen sollen, denn damit kann man innerhalb einer FOR-Schleife ungestraft Operationen verwenden, die das Carry beeinflussen und mit jedem Schleifendurchgang weiterverwenden, z. B. wiederholte Schiebe- und Rotationsbefehle, Arithmetik mit größereren Zahlen, die wiederholt durchgeführt wird, u. v. m.

Also:

  • Aufpassen bei Status-Abfragen nach INC und DEC.
    Lediglich die Flags Z, N , V und S werden beeinflusst und können nach INC und DEC per BRcc abgefragt werden, also nicht per BRCS bzw. BRLO und BCC bzw. BRSH.
     
  • Beim Subtrahieren mit negativen Zahlen (z. B. als Ersatz für eine bei AVR nicht verfügbare Addition einer Konstanten) wird das Carry umgekehrt behandelt.
     
  • FOR-Schleifen erlauben normalerweise, dass man das Carry innerhalb der FOR-Schleife für andere Zwecke verwenden kann, ohne dass das Carry (und nur das Carry!) durch den Schleifenzähler in Mitleidenschaft gezogen wird.
     
  • Ohne Beispiele sei noch erwähnt, dass die AVR-Befehle CPC, SBC, SBCI (also Vergleich und Subtraktion mit Carry) für das Z-Bit auch den Zustand des Z-Bits vor dem Vergleichen bzw. vor dem Subtrahieren berücksichtigen, womit man beim Vergleichen und Subtrahieren mehrerer Bytes nacheinander ohne Zusatzaufwand feststellen kann, ob aus mehreren Bytes bestehende Zahlen gleich sind bzw. ob das aus mehreren Bytes bestehende Ergebnis der Subtraktion 0 ist.

    Warum das bei ADC nicht so ist, erschließt sich mir momentan nicht, denn aus der Tatsache, dass das Ergebnis der letzten Teiladdition (per ADC) 0 ist, kann man nicht schließen, dass das Ergebnis der gesamten Kettenaddition 0 ist (was nur der Fall sein kann, wenn alle Summanden 0 sind).

nach oben

 


Kleiner oder gleich, und größer (9.12.2019)

Dass die 8-bit-AVR nur einen ziemlich reduzierten Satz von Skip-Befehlen haben, wurde ja schon erwähnt.

Aber auch an anderen Stellen des Befehlssatzes musste man offensichtlich sparen, denn es gibt leider keine Assembler-Sprünge bei "<=" und ">" (sowohl mit als auch ohne Vorzeichen), sondern nur bei "<", ">=" und "=".

Deshalb müssen sich Compiler für AVR - und somit auch s’AVR[1] - in diesen Fällen etwas anderes einfallen lassen, besonders wenn mit Konstanten verglichen wird.

Kleiner oder gleich

Eine Abfrage auf "<=" kostet zunächst nur einen weiteren Branch-Befehl, indem man stattdessen nacheinander bezüglich "<" und "=" abfrägt (egal in welcher Reihenfolge):

    BRLO

    BREQ

Bei größer ist der Aufwand größer

Nun, wenn man zwei Register auf ">" vergleichen möchte, kann man für die Abfrage zunächst die beiden Register vertauschen und dann auf "<=" abfragen, wofür es die Ersatzlösung gibt.

Ein Register und eine Konstante für die Abfrage zu tauschen, geht natürlich nicht. Die mögliche Lösung findet man anhand eines Beispiels in C-Sprache, dessen Listing man analysiert.

Mangels eines Assembler-Sprungbefehls bei ">" (um die geschweifte Klammer zu überspringen) wird GCC z. B. diesen C-Code:

     if (a <= 200)

     {

       .

       .

       .

     }

wie folgt kompilieren:

     if (a <= 200)

     a4: 89 3c        cpi r24, 0xC9  ; 201

     a6: 18 f4        brcc .+6       ; 0xae <main+0x1e>

     {

      .

      .

      .

     }

Wie man sieht, hat GCC mit der um 1 größeren Konstanten 201 verglichen, nämlich um BRCC statt einem nicht vorhandenen Assembler-Befehl "BRHI" verwenden zu können.

s’AVR wendet genau denselben Trick an, denn aus:

     IF COUNT <= #200

      .

      .

      .

     ENDI

wird dieses flache AVR-Assembler-Programm:

     ;01// IF COUNT <= #200

     CPI COUNT,200+1

     BRSH _P29

      .

      .

      .

     ;01// ENDI

    _P31:

    _P29:

Nur hat s’AVR statt dem BRCC des GCC den gleichwertigen Assembler-Befehl BRSH verwendet (der in diesem Zusammenhang sogar naheliegender ist).

Spannend wird dieser C-Code (mit uint8_t  count):

    while (count <= 255)

      {

       .

       .

       .

      }

den ein C-Compiler normalerweise wegoptimiert (also ohne extra Assembler-Befehle für die Abfrage zu generieren [und sonst einen Assembler-Fehler zu provozieren], nur die Befehle in der geschweiften Klammer werden ausgeführt, und zwar in einer versteckten Endlosschleife), da diese Abfrage bei 8 Bit ohne Vorzeichen immer wahr ist.

Man könnte also genau so gut

    while (1)

      {

       .

       .

       .

      }

schreiben.

Bei s’AVR wird es mit diesem vergleichbaren Code:

    WHILE COUNT <= #255

     .

     .

     .

    ENDW

durch den +1-Trick etwas schwieriger, denn s’AVR möchte (ohne Optimierung des Vergleichs) zunächst richtig rechnen, stellt dabei aber ein Problem[2] fest (das GCC durch die Optimierung vermieden hat):

    ;01// WHILE COUNT <= #255

    _P32:

     CPI COUNT,255+1

    .ERROR "in s'AVR line 381: This case comparing with constant 255

     will generate Assembler troubles! Use an AVR register instead."

     BRSH _P33

     .

     .

     .

     ;01// ENDW

     RJMP _P32

    _P33:

Dieser Code wird sich also nicht assemblieren lassen, denn der Programmentwickler muss das Problem nach der Fehlermeldung erst selbst erkennen (nämlich WHILE-Struktur ist immer wahr) und beseitigen.

Oder wollte er statt einer Endlosschleife (bei s’AVR normalerweise LOOP-ENDL) gar eine Abfrage auf Überlauf (siehe REPEAT-Schleife weiter oben)?

Dann war die Fehlermeldung von s’AVR  sogar hilfreich.

Falls er aber (wie per Fehlermeldung empfohlen) ein Register zum Vergleichen verwendet, findet s’AVR prompt einen anderen trickreichen Weg, der allgemein gültig und immer assemblierbar ist, im Falle LIMIT=255 aber nicht wegoptimiert[3] wird:

     ;01// WHILE COUNT <= LIMIT

    _P33:

     SEC

     CPC COUNT,LIMIT

     BRSH _P35

     .

     .

     .

     ;01// ENDW

     RJMP _P33

    _P35:

Und jetzt ist es wie bei GCC im Falle von LIMIT=255 eine versteckte Endlosschleife, allerdings mit drei extra Befehlen ausprogrammiert.

 

Also:

  • Keine ungewollten Endlosschleifen programmieren, die nicht so schnell entdeckt werden.

Nur gut, dass C-Compiler und s’AVR dem Programmentwickler Überlegungen bezüglich Flags meistens abnehmen (manchmal auch mit einer versteckten Falle) - wenn er nicht ausschließlich in AVR-Assembler-Sprache programmiert und dann immer wieder selbst über zulässige Abfragen und Sprünge nachdenken muss ...

 

nach oben

 


FOR ... DOWNTO (26.5.2021)

 

Die in einigen höheren Programmiersprachen vorkommende FOR-DOWNTO-Struktur wird zwar von s’AVR nicht direkt unterstützt, aber man kann sie einfach per EXITIF emulieren, sprich statt:

 

    FOR count := #100 DOWNTO #10 ; DOWNTO wird nicht von s’AVR unterstützt

       .

       .

       .

    ENDF

 

schreibt man einfach:

 

    FOR count := #100      ; Anfangswert 100

       EXITIF count < #10  ; Endwert 10 (DOWNTO)

       .

       .

       .

    ENDF                   ; Schrittweite -1

 

Natürlich kann man eine solche DOWNTO-Schleife nach der Initialisierung mit dem Anfangswert auch per WHILE realisieren, dann sogar mit anderer Schrittweite (auch aufsteigend).

 

Hier die WHILE-Version, ebenfalls mit Schrittweite -1 (absteigend):

 

    ldi count, 100         ; Anfangswert 100

    WHILE count >= #10     ; Endwert 10 (DOWNTO)

       .

       .

       .

       dec count           ; Schrittweite -1

    ENDW           

 

Bei einer Zeile mehr Tipparbeit zeigt das compilierte s’AVR-Programm exakt dasselbe Verhalten, wenn auch bei geringfügig anderen AVR-Assembler-Befehlen, zunächst per abgebrochener FOR-Schleife:

     ;01// FOR count := #100  ; Anfangswert 100

     LDI count,100

    _L1:

     ;01// EXITIF count < #10 ; Endwert 10 (DOWNTO)

     CPI count,10

     BRLO _L4

     .

     .

     .

     ;01// ENDF                ; Schrittweite -1

     DEC count

     BRNE _L1

    _L4:

und hier per WHILE-Schleife:

     ldi count, 100            ; Anfangswert 100

     ;01// WHILE count >= #10  ; Endwert 10 (DOWNTO)

    _L5:

     CPI count,10

     BRLO _L7

     .

     .

     .

     dec count                 ; Schrittweite -1

     ;01// ENDW

     RJMP _L5

    _L7:

Der einzige Unterschied ist der jeweils letzte Assembler-Befehl.

Speicherbedarf und Laufzeit der beiden Versionen sind identisch.

 

CONTINUE - vorzeitig weitermachen

 

Am Rande sei bei dieser Gelegenheit verraten:

 

Für alle Schleifen (also FOR, LOOP, REPEAT und WHILE) wird in einer neueren s’AVR-Version inzwischen auch CONTINUE unterstützt, ab dem vorzeitig die nächste Schleifen-Iteration durchgeführt wird, noch bevor das eigentliche Ende der jeweiligen Schleife erreicht ist.

 

s’AVR verwendet dafür die verkürzten Anweisungen CONT und CONTIF, wobei letztere ein bedingtes CONTINUE ist, welches sonst umständlich und weniger übersichtlich in einer zusätzlichen IF-Struktur untergebracht sein muss.

 

Bei s’AVR sind CONT und CONTIF also nur in den genannten Schleifen-Strukturen zugelassen, nicht aber in IF-Strukturen. Deshalb kommt bei s’AVR-Programmen im Normalfall bei Bedarf fast ausschließlich CONTIF zum Einsatz (und CONT nur sehr selten).

 

Hier eine einfache Anwendung für CONTIF bei einer schnellen Ganzzahldivision:

 

; Dividend64 / Divisor32 = Quotient64 + Rest32

;   DD7:DD6:DD5:DD4:DD3:DD2:DD1:DD0 / DS3:DS2:DS1:DS0

; = Q7:Q6:Q5:Q4:Q3:Q2:Q1:Q0 + RE3:RE2:RE1:RE0

 

; Hierfür können beliebige AVR-Register verwendet werden:

;   r15:r14:r13:r12:r11:r10:r9:r8 / r7:r6:r5:r4

; = r15:r14:r13:r12:r11:r10:r9:r8 Rest r3:r2:r1:r0

 

DIV64_32:

    clr r0          ; Rest32 löschen und für Quotienten vorbereiten

    clr r1

    clr r2

    clr r3

    FOR r16 := #64

        lsl r8      ; Dividend << 1

        rol r9

        rol r10

        rol r11

        rol r12

        rol r13

        rol r14

        rol r15

        rol r0      ; MSBit von Dividend zur Berechnung des Quotienten nach Rest32

        rol r1

        rol r2

        rol r3

        cp  r0, r4  ; Dividend ? Divisor

        cpc r1, r5

        cpc r2, r6

        cpc r3, r7

        CONTIF C    ; Divisor ist > Dividend (in Rest), deshalb nächste Bitstelle

        sub r0, r4  ; sonst Divisor von Dividend (in Rest) abziehen

        sbc r1, r5

        sbc r2, r6

        sbc r3, r7

        inc r8         

    ENDF            ; Quotient r15:r14:r13:r12:r11:r10:r9:r8, Rest r3:r2:r1:r0

    ret

 

Das ist sauber und übersichtlich strukturiert programmiert.

Mit einem Original-CONTINUE müsste man etwas aufwendiger z. B. so schreiben:

 

    FOR r16 := #64

        .

        .

        cp  r0, r4  ; Dividend ? Divisor

        cpc r1, r5

        cpc r2, r6

        cpc r3, r7

        IF C        ; Divisor ist > Dividend (in Rest), deshalb nächste Bitstelle

           CONTINUE ; von s’AVR nicht in dieser Form unterstützt

        ENDI

        sub r0, r4  ; sonst Divisor von Dividend (in Rest) abziehen

        sbc r1, r5

        sbc r2, r6

        sbc r3, r7

        inc r8

    ENDF            ; Quotient r15:r14:r13:r12:r11:r10:r9:r8, Rest r3:r2:r1:r0

 

Genau genommen macht dieses komplexer geschriebene CONTINUE in der nächst höheren Struktur-Ebene FOR ... ENDF weiter, was den Anfänger schon etwas irritieren kann.

 

Das einfachere CONTIF ist ähnlich wie EXITIF, nur dass es nicht die aktuelle Struktur in die nächst höhere Ebene verlässt, sondern die aktuelle Schleife (hier FOR) mit der nächsten Iteration fortsetzt und dabei einige restliche Befehle dieser Schleife (hier sub r0, r4 etc.) überspringt.

 

Alternativ könnte man bei der gezeigten FOR-Schleife statt dem äußerst kompakten CONTIF C auch ein IF NC ... ENDI über den Rest der Schleife verwenden. Das wäre zumindest für den Anfänger verständlicher als das Original-CONTINUE.

 

nach oben

 


Größere FOR-Schleifen (30.6.2019)

Falls die 8 Bit eines FOR-Registers nicht ausreichen, lassen sich größere FOR-Schleifen ersatzweise sehr einfach mit einer REPEAT-UNTIL-Struktur und einem Doppelregister lösen.

Hier ein Beispiel, das die Endnullen aus dem Ergebnis einer sehr großen Fakultät bestimmt:

czeros:       ; count # of zeros and print in line 2
   clr yh     ; count # of zeros in yh:yl
   clr yl
   ldi zh,HIGH(FArray)    ; Z register is increasing pointer to FArray
   ldi zl,LOW(FArray)
   ldi CNTH,HIGH(Array)   ; REPEAT loop counter (counting down)
   ldi CNTL,LOW(Array)
   REPEAT

       ld AKKU, z
       EXITIF AKKU <> #0 ; first digit <> 0 found
       adiw YH:YL,1      ; trailing 0 detected
       adiw ZH:ZL,5      ; point to next higher entry
       sbiw CNTH:CNTL,1  ; loop counter
   UNTIL Z

   mov AKKU3,yh
   mov AKKU2,yl
   rcall TM1640_PRINT_DEC_2   ; print decimal, 4 digits, 2nd line, 2nd half
   ret

Die nötigen Befehle sind rot markiert.

Als Doppelregister können paarweise die AVR-Register R24 bis R31 verwendet werden.

Mit dieser Methode sind im Unterschied zu FOR-ENDF auch Schrittweiten ungleich -1 möglich, nämlich Schrittweiten -0 ... -63.

Aufsteigend

Auch für große aufsteigende FOR-Schleifen lässt sich REPEAT-UNTIL verwenden.

Dann wird vorher der Anfangswert in das Doppelregister geladen, vor dem UNTIL Z per ADIW die gewünschte Schrittweite +0 ... +63 zum Doppelregister addiert und durch einen Vergleich mit dem Endwert beendet.

Eine 16-bit-Abfrage erfolgt vorteilhaft per CP gefolgt von CPC mit zwei zusätzlichen Registern, die den Vergleichswert beinhalten.

Per CPI mit dem LOW-Wert und nachfolgend per CPC mit einem Register, das den HIGH-Wert beinhaltet, kann man wenigstens ein Register einsparen, denn ein "CPIC" gibt es leider nicht.

Fazit: Wenn möglich, für 16-Bit-Schleifen die einfachere und Register sparende absteigende Methode verwenden.

nach oben

 


 

SQRT16 - Schnell die (Quadrat-) Wurzel gezogen (3.8.2021)

Auf der Suche nach einer Quadratwurzel per AVR ist mir zunächst eine relativ schnelle Routine für die SX-Controller (von Scenix/Ubicom, später Parallax) in den Sinn gekommen. Da diese für meinen Precompiler SXp geschrieben war (aber ursprünglich nicht auf meinem Mist[4] gewachsen ist), wäre ein Umschreiben auf s’AVR nicht allzu schwierig geworden.

Leider ist das bei der SX-Routine angewandte Konzept nicht so einfach durchschaubar (mehrseitige Beschreibung des Verfahrens mit ausschließlich Bit-Setzen, Rotieren, Subtrahieren und Addieren), so dass ich noch etwas weiter zurückgeblickt habe, nämlich auf ein Assembler-Programm, das ich bereits 1985 für den sehr schönen 16-bit-CISC-µC MK68200[5] von Mostek geschrieben hatte.

Und damit wird das Wurzelziehen denkbar einfach und sogar deutlich schneller - sofern der verwendete µC einen Hardwaremultiplizierer hat bzw. Multiplizierbefehle unterstützt.

Da meine Programme meist auf den ATmegas laufen, war das natürlich kein Problem.

Sukzessive Approximation

Das Stichwort für das dabei angewandte Wurzelziehen heißt sukzessive Approximation, die u. a. auch für schnelle A/D-Wandler verwendet wird.

Um eine Wurzel einer 16-bit-Zahl ganzzahlig darzustellen, benötigt man wenigstens 8 Bit, genaugenommen sogar 9 Bit, falls der Radikand größer als 65.280 (0xFF00) ist, denn dann ist das Ergebnis bei korrektem Runden 256 (0x01FF).

Zunächst sollen aber 8 Bit für das Ergebnis genügen, da sich das 9. Bit erst beim Runden ergibt.

Erklärt mit wenigen Worten

Für die Wurzelberechnung tastet man sich durch versuchsweises Setzen von einzelnen Ergebnis-Bits (beginnend mit dem höchstwertigen), Quadrieren dieser damit gebildeten 8-bit-Zahl und Vergleichen mit dem Radikand bitweise an die richtige Lösung heran: Ist das Quadrat zu groß, wird das jeweilige Bit zurückgenommen und das nächst niederwertigere Bit gesetzt. Passt das Ergebnis exakt, hat man bereits die Lösung und kann die Prozedur eigentlich mit diesem Ergebnis beenden. Sonst muss man weitere Bits setzen bzw. rücksetzen, bis das niederwertigste Bit erreicht ist.

Eine runde Sache

Spätestens nach bis zu 8 Versuchen hat man schon fast das korrekte Ergebnis. Es muss nur noch richtig (auf-) gerundet werden.

Für diese SQRT-Berechnungsmethode gibt es inzwischen zuhauf Vorschläge. Erstaunlicherweise wird das richtige Runden dabei meist unterschlagen.

Bestenfalls wird noch der ganzzahlige Rest zum Radikanden angegeben. Dieser Rest liegt im Bereich 0 ... 2*Quadratwurzel, kann unter Umständen also ganz schön groß sein.

Damit kann man vermuten, dass fast die Hälfte (nämlich 49,8%) aller Ergebnisse nicht korrekt gerundet ist.

Sofern man den ganzzahligen Rest hat, ist der Weg zur richtig gerundeten Lösung aber gar nicht mehr so weit, denn zieht man diesen vom gefundenen vorläufigen Ergebnis ab und das Ergebnis der Subtraktion ist negativ, dann muss man die Wurzel aufrunden, sprich inkrementieren. Ansonsten hat man bereits die richtig (ab-) gerundete Wurzel. So einfach ist das!

Übersichtlich

Und so schaut das kleine und feine SQRT16-Programm in strukturierter AVR-Assemblersprache s’AVR aus (mit vielen Kommentaren versehen, falls jemand tiefer einsteigen möchte):

; SQRT16: This subroutine calculates the 9 bit square root y of a 16 bit value x: y = SQRT(x)

 

; (c) Eberhard Haug 03-AUG-2021

 

; Registers RADHI:RADLO = x are kept unmodified. RADHI:RADLO = XH:XL would be a good choice.

; But instead of XH:XL any other AVR registers (or register pairs) can be used.

 

; The 9 bit result y resides in YH:YL.

; YH is also used as bit position register until the 9th bit is required.

; Instead of YH and YL any other double registers can be used (which allow addiw).

 

; PHI:PLO = R1:R0 are used to calculate both the square and the integer remainder of the result

; (2's complement). In total only 6 AVR registers are used.

 

; Method being used: Successive approximation.

; SQRT16 can be expanded to SQRT24, SQRT32 etc.

 

SQRT16:

  ldi  YH, 0x80      ; start with MSB

  clr  YL            ; clear result y (8 bits so far)

  REPEAT

    or  YL, YH       ; set next bit position

    mul  YL, YL      ; result y^2 in PHI:PLO

    sub  PLO, RADLO  ; subtracting needs same time as comparing, but simplifies rounding

    sbc  PHI, RADHI  ; now PHI:PLO = y^2 - x

    ;EXITIF Z        ; exact result

    breq done        ; optional faster code if already exact result (skip extra MUL and round-up)

    IF NC            ; result y too big

      eor  YL, YH    ; undo current bit

    ENDI

    lsr  YH          ; next bit position

  UNTIL C

 

  IF !YL,0           ; LSB has been reset, therefore a new MUL is required

    mul  YL, YL      ; result y^2 in PHI:PLO

    sub  PLO, RADLO  ; subtracting needs same time as comparing, but simplifies rounding

    sbc  PHI, RADHI  ; now PHI:PLO = y^2 - x

  ENDI

                     ; Up to here y = INT(SQRT(x)) is completed, but rounding is not yet correct,

                     ; registers PHI:PLO hold the 2's complement of the remainder

 

; The 16 bit remainder of y = INT(SQRT(x)) is always in the range of 0 to 2*y,

; which means that almost 50% of the results are not correctly rounded.

 

; To do so, the result y should be rounded up if the remainder is > y.

; Just for x > 65280, y would then be 256, which is 9 bits, so 2 registers are required.

 

; The remainder of the rounded y then would be in the range  -(y-1) to +(y).

; And the accuracy of the rounded y would be in the range -0,49... through +0,49...,

; which is approximately -+remainder/(2*y).

 

; Instead of calculating the true remainder and comparing against y,

; simply adding the 2's complement of the remainder and y is a few CPU cycles faster.

; Then rounding up must be done when the 16 bit sum of both is negative.

 

  clr     YH         ; up to here there is no 9th bit

  add     PLO, YL

  adc     PHI, YH    ; YH = 0 is helpful to add the carry

  IF N               ; the sum of y and the 2’s complement of the remainder is negative

    adiw    YH:YL, 1 ; round up = increment y (16 bit, so YH can become 1, otherwise YH stays 0)

  ENDI

done:

  ret

 

Nun muss ich zugeben, dass das nicht 100% strukturiert geschrieben ist, denn für kürzeste Rechenzeit wird die REPEAT-Schleife per BREQ (statt per EXITIF Z) direkt zum Ende verlassen. Das ist eben der Vorteil der strukturierten Assembler-Programmierung, denn man programmiert immer noch maschinennah.

An Übersichtlichkeit hat das aber nicht verloren, ganz im Gegenteil.

Ansonsten geht das Programm sehr sparsam (und trickreich) mit Registern um.

Falls man das wertvolle Y-Doppelregister anderweitig benötigt, kann man es durch zwei andere AVR-Register ersetzen, muss dann aber die Rundung geringfügig aufwendiger durchführen.

Vertrauen ist gut, Kontrolle ist besser

Damit mein s’AVR-Programm auch Hand und Fuß hat und die Rundungen alle exakt stimmen, habe ich es natürlich gründlich getestet, und zwar auf einem Arduino-UNO-Board mit einer 16-bit-REPEAT-Schleife für alle 2^16 Radikanden XH:XL von 0x0000 bis 0xFFFF.

Dieses Testprogramm gibt zeilenweise jeweils den Radikand und die zugehörige Quadratwurzel auf einem Terminal-Window aus, und zwar gleich per Tabulator getrennt, so dass man die Werte direkt in eine Excel-Tabelle[6] kopieren (Spalten wegen der HEX-Darstellung vorher als Text formatieren!) und mit eigenen Excel-Berechnungen vergleichen kann.

Bei allen Wurzelwerten wird korrekt gerundet, sprich die Genauigkeit liegt immer im Bereich -0,49... bis +0,49...

Ziemlich flott

Die per Scope gemessenen Rechenzeiten für die Quadratwurzeln liegen im Bereich von 1,12 µsec bis 6,87 µsec @16 MHz. Und das schaut als Hüllkurve auf dem Scope dann so aus:

Envelope SQRT16

Die tatsächliche Rechenzeit ist 9 CPU-Zyklen weniger (1x I/O-Pin für das Scope + RCALL + RET).

"Netto" gerechnet sind es minimal 9 CPU-Zyklen (z. B. SQRT(16384)) bis maximal 2 + 7*11 + 10 + 12 = 101 CPU-Zyklen, also jeweils ohne RCALL- und RET-Befehl, aber korrekt gerundet.

Bei genauem Hinschauen kann man auf dem Screenshot die 8 Bitstellen und ggf. die zusätzliche Multiplikation beim zurückgesetzten LSB erkennen, nämlich immer dann, wenn ein exaktes Ergebnis gefunden und per BREQ direkt ans Programmende gesprungen oder abschließend eine weitere Multiplikation für den richtigen Rest nötig wurde.

Da sich die Anzahl der verkürzten Zyklen aber in Grenzen hält, wird eine durchschnittliche Wurzel nach der beschriebenen Methode statt 101 kaum weniger, nämlich 97 CPU-Zyklen benötigen.

Beschleunigt

Nimmt man den BREQ heraus, werden zwar einige (wenige) Wurzelberechnungen etwas langsamer, aber es sind nur noch maximal 93 CPU-Zyklen (was etwa auch dem Durchschnitt bei allen 2^16 Quadratwurzeln entspricht).

Maximal 62 CPU-Zyklen, und noch weniger

Und wenn der Programmspeicher-Bedarf keine Rolle spielt, kann man die REPEAT-UNTIL-Schleife noch entrollen und dabei das Bit-Setzen/Rücksetzen nicht per Schieben und EOR, sondern direkt per SUBI erledigen. Dann können dafür allerdings nur "obere" AVR-Register verwendet werden.

Damit erreicht man dann weiter verkürzte Rechenzeiten, und zwar (wiederum ohne BREQ) maximal gerade einmal 62 AVR-CPU-Zyklen bzw. 3,875 µsec @16 MHz - wohlgemerkt mit sauber gerundetem Ergebnis und die Wurzel mit 9 Bit dargestellt.

Für dieses entrollte Programm sind allerdings 52 Worte (104 Byte) nötig (RET nicht mitgezählt).

Unter Berücksichtigung einiger Spezialfälle ließen sich beim entrollten Programm weitere Befehle einsparen und etwas Rechenzeit gewinnen, aber die Übersichtlichkeit verliert dabei.

Zum Beispiel solange die unteren 4 Bits des Ergebnisses alle 0 sind (sprich beim Abfragen der Bits 7 bis 4), muss man beim Vergleichen nur das High-Byte des Quadrats (bei mir PHI) berücksichtigen, was ich bei den maximal 62 CPU-Zyklen bereits gemacht habe.

Desweiteren könnte man wenigstens die oberen beiden Bits 7 und 6 einfach durch Abfragen des Radikanden-High-Bytes und und geschicktes Setzen der Ergebnis-Bits ohne tatsächliche Multiplikation abhandeln (das Programm ist jetzt aber trotz strukturierter Programmierung nur noch mit reichlich Kommentaren zu verstehen) und dann wie gehabt mit Bit 5 weitermachen.

Mit dieser Methode bin ich bei maximal 56 AVR-CPU-Zyklen bzw. 3,5 µsec @16 MHz und 49 Programmspeicherworten angelangt (ohne RET), wiederum mit gerundetem Ergebnis und die Wurzel mit 9 Bit dargestellt.

Wenn korrektes Runden und der ganzzahlige Rest nicht interessieren, kann man 10 CPU-Zyklen und 8 Programmspeicherworte einsparen.

Kaum noch Scharm

Auch wenn das getunte Programm 1,8-fach schneller (und der Programmspeicherbedarf nur 1,4-fach größer) ist, hat es im Vergleich zur vorgestellten Schleife mit acht Durchläufen mächtig an Übersichtlichkeit und Scharm verloren.

nach oben


Die C-Wurzel (21.8.2021)

Es hat mich nun doch noch interessiert, wie C-Programme das Wurzelziehen nebst korrektem Runden für einen AVR-µC umsetzen.

Dazu habe ich mir ein kleines Arduino-Programm (C++) geschrieben und auf einem Arduino-UNO laufen lassen:

    uint16_t  radikand;

    uint16_t  wurzel;

 

    Serial.println("Wurzel-Berechnung ...");

    for (radikand = 0; radikand <= 65535; radikand++)

   

      digitalWrite(LED_BUILTIN, HIGH);

      wurzel = round(sqrt(radikand));

      digitalWrite(LED_BUILTIN, LOW);

      printf("%6u\t%3u\n", radikand, wurzel);

    }

 

Verblüfft war ich zunächst über den Speicherbedarf von 6.580 Byte für das Programm (wohl wegen der eingebundenen printf-Library) und zusätzlichen 222 Byte SRAM.

Die Rechenzeit pro Quadratwurzel beträgt typisch ca. 50 µsec bis knapp über 60 µsec @16 MHz. Im Schnitt liegt das weit über dem Zehnfachen meiner obigen s’AVR-Programme!

Endlosschleife

Dann hat mich überrascht, dass das Programm nach dem Abarbeiten der FOR-Schleife nicht wie vorgesehen stoppte, sondern die Schleife immer wieder von vorne begann.

Schließlich ist mir eingefallen, was ich bei den Tipps ganz oben bezüglich der Abfrage auf "<=" beschrieben hatte.

Demnach wird im vorliegenden Fall bei C mangels eines entsprechenden AVR-Assembler-Befehls eine Abfrage auf "radikand <= 65535" mittels "radikand < 65535+1” realisiert, sprich einem 17-bit-Wert 65.536.

Für den C-Compiler ist der abgefragte Endwert mit uint16_t offensichtlich immer wahr, so dass es einer Endlosschleife[7] gleichkommt. Eine Compiler-Warnung gibt es nicht.

Auch eine schlichte WHILE-Schleife endet bei demselben Endekriterium in derselben Endlosschleife.

Erst per DO-WHILE und einem anderen Endekriterium (nämlich dem 16-bit-Überlauf auf den Wert 0):

    radikand = 0;                                                  

    do

   

      digitalWrite(LED_BUILTIN, HIGH);

      wurzel = round(sqrt(radikand));

      digitalWrite(LED_BUILTIN, LOW);

      printf("%6u\t%3u\n", radikand, wurzel);

      radikand++;

    }

    while(radikand != 0);
 

klappt die Schleife wie angedacht genau einmal über alle 2^16 möglichen Werte. Diese abschließende Abfrage erst nach dem Inkrementieren entspricht bei s’AVR einer REPEAT-UNTIL-Schleife.

Der Programmspeicherbedarf ist mit der DO-WHILE-Schleife sogar knapp weniger, nämlich 6.574 Byte und der SRAM-Bedarf beträgt wie zuvor 222 Byte.

GCC unter Atmel-Studio 7

GCC hat genau dasselbe Problem mit den genannten FOR- und WHILE-Schleifen. Aber per DO-WHILE klappt es auch bei GCC, sogar mit deutlich weniger Speicherbedarf, obwohl auch hier Routinen für printf eingebunden sind:

    Program Memory Usage: 2678 bytes 8,2 % Full
    Data Memory Usage: 70 bytes 3,4 % Full

Im Vergleich zu C++ sind die Rechenzeiten einiges kürzer. Sie liegen im Bereich von 40 µsec bis 50 µsec @16 MHz.

Die Unterschiede im Code zwischen C++ und GCC habe ich nicht weiter analysiert. Lediglich zwei GCC-Unterprogramme habe ich näher angeschaut:

Die Routine "sqrt" arbeitet überraschenderweise komplett ohne MUL-Befehle (bei beiden C-Compilern) und benötigt bei GCC dafür 252 Byte zzgl. zwei aufgerufenen Unterprogrammen à 100 Byte und 24 Byte.

Und die Routine "round" benötigt weitere 160 Byte, also zusammen 536 Byte. Kein Wunder, dass die Rechenzeiten gegenüber s’AVR so viel größer sind.

nach oben


Inkrementale Wurzel-Approximation (23.8.2021)

Die doch relativ langsame Quadratwurzel-Berechnung per GCC und C++ hat mich dazu inspiriert, einen weiteren Lösungsansatz vorzustellen, der im Mittel nicht viel langsamer ist, aber ausgesprochen wenig Resourcen benötigt und dabei ganz auf Multiplikationen verzichtet (weder per Hardware, noch per Software).

Dieser Algorithmus - ich will ihn inkrementale Wurzel-Approximation nennen - bestimmt die Quadratwurzel aus einem gegebenen Radikanden, in dem die gesuchte Wurzel (die Radix) beginnend mit 0 durch Inkrementieren gesucht und gefunden wird, und zwar auf Anhieb mit korrekter Rundung.

Nun, das könnte man zunächst einfach durch Quadrieren der Radix (zwangsläufig eine Multiplikation, die vermieden werden sollte) und Vergleichen mit dem Radikanden finden, dann allerdings noch ohne die korrekte Rundung.

Es gibt aber auch einen ganz anderen Weg, der mir beiläufig in den Sinn gekommen ist, als ich nach einer schnellen (Auf-) Rundungsmethode für meine obige s’AVR-basierende Wurzelberechnung gesucht habe.

Hierzu habe ich in einer Tabelle die Schwellen markiert, bei welchen das Aufrunden nötig wird. Und dabei ist mir aufgefallen, dass die Anzahl gleicher Wurzelwerte bzw. der Abstand der Rundungsschwellen gemäß einer arithmetischen Reihe 2. Ordnung ansteigt, nämlich:

1, 3, 7, 13, ..., 64771, 65281

Nun könnte man die einzelnen Glieder dieser Reihe zwar aufwendig per Formel berechnen, was aber überflüssig ist, wenn man die Abstände der einzelnen Glieder dieser arithmetischen Reihe[8] betrachtet, nämlich:

2, 4, 6, 8, ... 508, 510

Das sind also lauter stetig ansteigende gerade Zahlen.

Mit dieser Erkenntnis kann für die "Wurzelfindung" die Berechnung der Rundungsschwellen während dem Inkrementieren der Radix einfach durch Akkumulieren von geraden Zahlen (nämlich dem Doppelten der laufenden Radix) geschehen, beginnend mit dem Startwert 1.

Anhand dieser Reihe mit insgesamt 257 Gliedern kann man schließlich die gesuchte und korrekt gerundete Radix 0...256 finden, indem man den gegebenen Radikanden mit den akkumulierten Schwellenwerten (beginnend mit 1) vergleicht.

Das waren jetzt viele Worte für ein ausgesprochen einfaches s’AVR-Programm:

; Square root by incremental approximation, (c) 23-AUG-2021 Eberhard Haug

 

SQRT16ia:                           ; find yh:yl = rounded SQRT(xh:xl)

    clr     cnth

    clr     cntl                    ; clear even number counter

    clr     acch

    ldi     accl, 1                 ; set limit accumulator to 0x0001

    movw    yh:yl, cnth:cntl        ; clr result counter

    LOOP                            ; even number cnth:cntl = 0, 2, 4, 6, ...

                                    ; limit accumulator acch:accl = 1, 3, 7, 13, ...

        cp      xl, accl            ; xl

        cpc     xh, acch            ; xh

        EXITIF C                    ; radicand below limit acch:accl, correctly rounded radix found

        adiw    yh:yl, 1            ; next y

        adiw    cnth:cntl, 2        ; next even number 2, 4, 6, 8, ...

        add     accl, cntl          ; next limit 3, 7, 13, ...

        adc     acch, cnth

        EXITIF C                    ; last step if x > 65.280 (+512 = 65.782)

                                    ; final radix = 0x100 (256)

    ENDL

    ret
 

Das sind gerade einmal 28 Byte für das ganze Programm (ohne RET), wiederum mit dem Hinweis, dass das Ergebnis für die Quadratwurzel 9 Bit genau und korrekt gerundet ist.

Dieses Programm benötigt keine Multiplikationen, sondern ausschließlich Additionen und Vergleiche. Zusätzlich zum Radikanden im Doppelregister XH:XL, werden nur 6 weitere AVR-Register (4 davon zwei Doppelregister) verwendet (die bei Bedarf gerettet werden müssen).

Im Vergleich zum ursprünglichen Lösungsansatz mit sukzessiver Approximation (benötigt 36 Byte Programmspeicher und insgesamt nur 6 AVR-Register) ist jenes mit inkrementaler Approximation jedoch deutlich langsamer, nämlich von ca. 1 µsec bis ca. 193 µsec mit dem Radikanden linear ansteigend, sprich im Mittel ca. 86 µsec @16 MHz.

Damit ist es im Mittel etwa halb so schnell wie die C++/GCC-Programme.

Aber es ist ein sehr einfaches und übersichtliches s’AVR-Programm mit wenigen Lines-of-Code.

Man könnte beinahe in Versuchung geraten, nach diesem Prinzip einen "Wurzelzieher" per Standard-CMOS-Logik aufzubauen.

nach oben


Die Kubikwurzel (26.8.2021)

Die eher nicht so häufig benötigte dritte Wurzel aus einer Zahl (die Kubikwurzel) lässt sich sinngemäß mit den oben beschriebenen Verfahren berechnen.

Zunächst muss man jedoch klären, wie groß der Radikand sein darf.

Für ein 8-bit-Ergebnis bieten sich 24 Bit als Radikand an. Dann wird der Aufwand für die Berechnung doch einiges größer.

Falls es aber bei 16 Bit bleiben soll, ist das Ergebnis maximal 40. Dann wird es besonders bei der sukzessiven Approximation sehr einfach, denn statt der Quadratbildung muss man nur ein weiteres mal multiplizieren und man beginnt beim Bit-Setzen eben bei Bit 5 statt bei Bit 7.

Bei der inkrementalen Approximation muss man doch erst einmal etwas genauer hinschauen, denn Kubikzahlen werden durch die Summe einer arithmetische Reihe 3. Ordnung gebildet:

1, 8, 27, 64, 125, 216, ...

Das bedeutet, dass man im Unterschied zur Quadratwurzel eine weitere Akkumulation benötigt.

Die 2. Differenzreihe schaut wie folgt aus:

12, 18, 24, 30, ...

Die zum Akkumulieren ebenfalls interessierende 3. Differenzreihe ist zwar konstant (bei den Quadratzahlen ist es die 2. Differenzreihe mit der konstanten Differenz 2):

6, 6, 6, ...

Aber leider sind die für die Rundungsschwellen nötigen Differenzen nicht immer dieselben (wie bei der Quadratwurzel) sondern etwas holprig, nämlich:

6, 7, 4, 7, 6, 7, 4, 7, ... (Mittelwert 6)

Das lässt sich wegen der Periodizität sicher auch programmiertechnisch umsetzen, schneller wird es jedoch durch entrollen, also viermal hintereinander mit den verschiedenen Differenzen 6, 7, 4 und 7 akkumulieren etc. und den Radikanden auf die so erzeugten Rundungsschwellen

1, 4, 16, 43, 92, 167 ...

für die gesuchte und korrekt gerundete Kubikwurzel abfragen.

Falls der Radikand nur 16 Bit groß ist, reichen für den "Even Counter" obigen Programms (der hier aber statt 2 abwechselnd 6, 7, 4 und 7 aufaddiert) auch 8 Bit, denn das 41. Glied der 2. Differenzreihe hat den Wert 252 und ist wegen dem größeren Startwert von 12 größer als der größte Wert dieses "Even Counters". Register YH wird nicht benötigt, da die gesuchte Kubikwurzel bei einem 16-bit-Radikanden maximal 40 ist.

nach oben

 


[1] s’AVR führt nur 8-bit-Vergleiche und diese generell ohne Vorzeichen aus, siehe Handbuch.

[2] Fehlermeldung ab Version 2.26, allerdings nicht bei einer symbolischen Konstanten, sondern nur bei einer Konstanten 255.

[3] Der Wert von LIMIT ist s’AVR nicht bekannt, nur dem AVR-Assembler, der aber erst recht nicht optimiert.

[4] Ivan Flores: "The logic of Computer Arithmetic".

[5] Der MK68200 hat eine ähnliche Architektur wie der 68000, aber nur 16 Bit breite Register (8 Datenregister, 6 Adressregister, PC, Stackpointer und Statusregister).

Allerdings hat er noch 128x16 SRAM, 2Kx16 ROM, gemultiplexten externen 16-bit-Adress/Daten-Bus, 3x 16-bit-Timer, eine serielle Schnittstelle (USART), Parallel-I/O-Ports (16/8 Bit), einen Interrupt-Controller und einen Quarzoszillator dazu bekommen. Der MK68200 ist also ein echter Single-Chip-µC.

Der Befehlssatz ist für Embedded-Applikationen ausgelegt (einschließlich MULU/MULS, DIV, BCD-Arithmetik, umfangreiche Bit-Manipulation und u. a. außer NEG auch ein NEGC für ein schnelles 2er-Komplement über mehrere Worte). Die meisten Befehle zur Datenmanipulation können wahlweise für 8 oder 16 Bit Datenbreite ausgeführt werden.

Allerdings sind die Ausführungszeiten wie bei jeder CISC-CPU deutlich länger als z. B. bei den AVR-RISC-CPUs. So benötigen alle "einfachen" Befehle (ADD, MOV ...) meist 3 CPU-Zyklen und z. B. eine 16x16-Multiplikation bereits 21 CPU-Zyklen. Der CPU-Takt der ersten Generation betrug 4 MHz oder 6 MHz (mit einem 8MHz-Quarz bzw. 12MHz-Quarz).

Es gab zwei Chip-Versionen MK68201 und MK68211 im 48-Pin-DIP mit unterschiedlichen Bus-Steuersignalen, nämlich UPC (68000-kompatible Signale) und GP (General Purpose) für Master/Slave-Anwendungen. Per MODE und einem weiteren Pin konnte man während Reset zwischen internem Programmspeicher (ROM) und jeweiligem externem Bus mit unterschiedlichem Speicher-Mapping umschalten.

Kundenspezifische ROM-Ausführungen erhielten die Bezeichnung MK41xxx (MK68201) bzw. MK42xxx (MK68211).

In einem 84-Pin-LCC gab es die entsprechenden Emulator-Chips als MK68E201/MK68E211, die den internen Adress/Datenbus und die zugehörigen Steuersignale an separaten Pins herausgeführt hatten. Diese Chips wurden auch auf Evalboards eingesetzt.

Falls jemand ein MK68200-Evalboard "übrig" hat: Ich hätte Interesse daran. Das Handbuch habe ich noch.

Hier ein Chip-Foto des MK68200 aus meiner Sammlung:

MK68200_1982

Rechts oben erkennt man eine Markierung UTC MOSTEK MK68200 RAINBOW ©1982.

[6] Bis einschließlich Excel 2006 lassen sich bis zu 2^16 Tabellen-Zeilen bearbeiten. Das ist also gerade noch für den SQRT16-Test ausreichend, aber für eine Kopfzeile (ggf. mit Filter) reicht es nicht mehr. :-(

[7] Zu allem Überfluss beginnen alle weiteren FOR-Schleifen mit 0, selbst wenn der ursprüngliche Startwert ungleich 0 ist.

[8] Bekanntermaßen gilt für das Quadrat diese Summenformel: 1 + 3 + 5 + 7 + ... + (2*x - 1) = x2

Interessant ist, dass die Reihe der Differenzschritte der Rundungsschwellen der Summenformel für die Quadratbildung sehr ähnlich sind, nämlich:

2 + 4 + 6 + ... + (2*x-2) + 2*x = 1+1 + 3+1 + 5+1 + 7+1 + ... + 2*x = x*(x+1) = x2 + x

Diese Formel bestätigt auch obige Feststellung im ersten s’AVR-Quellprogramm, dass der Rest bis zum Zweifachen von INT(SQRT(x)) betragen kann (letztes Glied der Reihe), also z. B. 65535 - 2552 = 510 = 2*256.