Wie dividiere ich ohne DIV?

In einem x86-Prozessor ist eine Aufgabe wie 237 : 10 leicht mit dem DIV-Befehl zu realisieren:

mov ax, 237
mov bl, 10
div bl

Danach stehen im Register AL das Ergebnis (der Quotient) und im Register AH der Rest.

Es gibt jedoch Prozessoren, die keinen Divisionsbefehl kennen. Man kann allerdings eine Division auch lediglich mit Subtraktion (SUB) und Vergleich (CMP) durchführen. Der einfachste Weg ist sicherlich, vom Dividenden so oft den Divisor abzuziehen, bis das Ergebnis negativ wird. Bei einem großen Dividenden und einem kleinen Divisor kann man den Prozessor aber damit in die Knie zwingen, insbesondere wenn die Berechnung nur die Grundlage einer Binär-Dezimal-Umwandlung ist.

Betrachten wir mal das schriftliche Dividieren zweier Dezimalzahlen:

Aufgabe: 237 : 10 = ?

Lösung:

Jeder hat es in der Schule gelernt, aber kann man die einzelnen Schritte auch verständlich beschreiben?

Schwarz:  Man bildet zuerst aus der ersten Ziffer der Zahl, die geteilt werden soll (Dividend), eine neue Zahl. Die erste Ziffer ist 2, die neue Zahl also 2. Dann prüft man, ob diese Zahl durch die Zahl teilbar ist, durch die man teilen will (Divisor) oder genauer: Ob die Teilung ein Ergebnis größer Null ergibt.
Kleiner Trick: Man subtrahiert zunächst den Divisor. Ist das Ergebnis größer 0, dann ist die Zahl auch durch den Divisor teilbar.

Rot:  2-10 ergibt kein Ergebnis größer Null, also nimmt man die nächste Ziffer des Dividenden und bildet daraus eine neue Zahl: 23. Ist diese Zahl durch den Divisor teilbar? Wenn nein, nimmt man die nächste Ziffer des Dividenden usw. In diesem Fall ergibt 23:10 aber eine Lösung, und zwar 2 (Rest 3). Der ganzzahlige Teil Lösung (2) wird an den Quotienten angeklebt. Für den nächsten Schritt nennen wir diese Ziffer mal 'roter Multiplikator'

Weiß:  Von der blauen Zahl wird nun das Produkt aus Divisor (10) roter Multiplikator (3) - also 20 - abgezogen. Das Ergebnis bildet den Stamm für die blaue Zahl im nächsten Schritt.

Blau:  An das Ergebnis der weißen Subtraktion (3) kleben wir hinten die nächste Ziffer des Dividenden (7) an und haben nun eine neue Zahl: 37. Wir suchen wie bei Rot oben eine Ziffer, diesmal einen 'blauen Multiplikator', kleben ihn an den Quotienten an und und führen mit ihm eine Subtraktion wie in Weiß oben durch.

Grau:  Es gibt keine Ziffern des Dividenden mehr, die wir hinten an die 7 ankleben können. Die 7 ist also der Rest aus der gesamten Division.

Nun machen wir das Ganze binär:

Auch eine binäre Zahl hat Ziffern. Diese werden auch Bits genannt und von hinten beginnend bei 0 durchnummeriert. Die 'erste Ziffer' oben entspricht hier also 'Bit 7', die zweite 'Bit 6' usw.:

Es geht weiter wie bei der Dezimaldivision: Man bildet aus Bit 7 eine neue Zahl. Das geht, indem man den Dividenden einmal nach links shiftet und das herausgeschobene Bitin ein anfangs leeres Register von rechts hineinschiebt:

    mov ah, 11101101b   ; Dividend ('b' steht für binär)
    mov bl, 1010b       ; Divisor = 1010b = 10d
    xor al, al          ; Quotient = 0 (Anfangswert)
    xor dl, dl          ; Zahl - dl = 0
    mov cx, 8           ; Schleifenzähler - for (cx=x; cx>0; cx--)
Schleife:
    shl ah, 1           ; Bit 7 von AH ...
    rcl dl, 1           ; ... nach Bit 1 von DL

Im Register AH steht der Dividend, im Register BL der Divisor, im Register AL der Quotient und im Register DL die Zahlen der Zwischenschritte, z.B. die schwarze Zahl. Was es mit CX und Schleife: auf sich hat, wird später erläutert.

    cmp bl, dl          ; Carry gesetzt, wenn dl > 10 (Fall Weiß)

Es wird geprüft, ob das Ergebnis einer Subtraktion von schwarzer Zahl (DL) und Divisor (BL) positiv wäre. Da wir das Ergebnis zunächst nicht brauchen, reicht ein Vergleich: Ist schwarze Zahl größer als Divisor?

    ja Sprungmarke      ; Sprung, wenn Carry=0 und Zero=0 (Ergebnis nicht Null)
    sub dl, bl          ; Fall Weiß: DL = DL - BL
    stc                 ; Carry setzen
Sprungmarke:

Da die schwarze Zahl nicht größer als der Divisor ist, wird zur 'Sprungmarke' verzweigt, also bleibt DL unverändert.

    rcl al, 1           ; Carry (0 oder 1) an Quotienten kleben.
    loop Schleife

Das Carryflag beinhaltet die Information, ob Fall Weiß angewandt wurde - dann 1 - oder ob die Zahl zu klein war - dann 0. In den Quotienten (AL) wird von rechts das Carryflag hineingeschoben. Was oben "ankleben" genannt wurde, ist hier "von rechts hineinschieben". Zum Schluss kommt ein Loop: Das Register CX wird um 1 dekrementiert und wenn CX nicht Null ist, wird gesprungen. Die Kombination 'mov cx,x - label - loop label' kann man C-mäßig mit einer For-Schleife erklären: for (cx=x; cx>0; cx--).

Da der Dividend aus 8 Bits besteht, müssen die Schritte zwischen 'Schleife:' und loop 8 Mal durchlaufen werden. In DL stehen also nacheinander die schwarze, rote, blaue, violette, grüne, orangene, gelbe, rosa und zum Schluss die graue Zahl, wobei Fall Weiß bei Bedarf dazwischengeschaltet wird.

Bei Fall Weiß kommt ein Trick des Binärsystems zum Tragen. Da es im Binärsystem nur 1 und 0 gibt, kann auch nur der ganze Divisor (1 * Divisor) oder "nichts" abgezogen werden. Es muss also nicht umständlich wie im Dezimalsystem durch Dividieren oder Probieren ein neuer Wert ermittelt werden. Deshalb sieht man in der Graphik als weiße Zahl immer nur den Divisor. Es wird also entweder der Divisor abgezogen oder nichts gemacht.

Wenn die Schleife verlassen wird, stehen im Register AL der Quotient und im Register DL der Rest.

Und so sieht das in einem Visual-C++-Programm aus:

#include <stdio.h>

unsigned char Dividend = 237;          // binär: 11101101
unsigned char Divisor = 10;            // binär: 00001010
unsigned char Quotient;

void main (void)
{
    __asm                              // al = ah / bl
    {
            mov ah, [Dividend]
            mov bl, [Divisor]
            xor al, al                 ; Quotient = 0 (Anfangswert)
            xor dl, dl                 ; Zahl (DL) = 0 (Anfangswert)
            mov cl, 8                  ; 8 Schleifendurchgänge: for (CL=8; CL>0; CL--)
        Schleife:
            shl ah, 1                  ; Bit 7 von AH ...
            rcl dl, 1                  ;     ... nach Bit 1 von DL
            cmp bl, dl                 ; Carry gesetzt, wenn DL > Divisor (Fall Weiß)
            ja Sprungmarke             ; Sprung, wenn Carry=0 und Zero=0 (Ergebnis nicht Null)
            sub dl, bl                 ; Fall Weiß: DL = DL - BL
            stc                        ; Carry setzen
        Sprungmarke:
            rcl al, 1                  ; Carry (0 oder 1) an Quotienten kleben.
            sub cl, 1
            jnz Schleife
            mov byte ptr [Quotient], al
    }

    printf ("%u div %u = %u\n", Dividend, Divisor, Quotient);
}

Der gleiche Algorithmus mit 16-Bit-Registern in AT&T-Syntax als GCC-Inline-Assembler:

#include <stdio.h>
#define T "\n\t"

unsigned short Dividend = 60721;       // binär: 1110110100110001
unsigned short Divisor = 1000;         // binär: 0000001111101000
unsigned short Quotient;

int main (void)
{
    asm volatile                       // di = ax / bx
    (
      T     "movw %[Dividend], %%ax"
      T     "movw %[Divisor], %%bx"
      T     "xorw %%di, %%di"          // Quotient = 0 (Anfangswert)
      T     "xorw %%dx, %%dx"          // Zahl (DX) = 0 (Anfangswert)
      T     "movb $16, %%cl"           // 16 Schleifendurchgänge: for (CL=16; CL>0; CL--)
      T   "1:"
      T     "shlw $1, %%ax"            // Bit 15 von AX ...
      T     "rclw $1, %%dx"            //     ... nach Bit 1 von DX
      T     "cmpw %%dx, %%bx"          // Carry gesetzt, wenn DX > Divisor (Fall Weiß)
      T     "ja 2f"                    // Sprung, wenn Carry=0 und Zero=0 (Ergebnis nicht Null)
      T     "subw %%bx, %%dx"          // Fall Weiß: DX = DX - BX
      T     "stc"                      // Carry setzen
      T   "2:"
      T     "rclw $1, %%di"            // Carry (0 oder 1) an Quotienten kleben.
      T     "subb $1, %%cl"
      T     "jnz 1b"
      T     "movw %%di, %[Quotient]"
      :[Quotient] "=m" (Quotient)
      :[Dividend] "m" (Dividend), [Divisor] "m" (Divisor)
    );

    printf ("%u div %u = %u\n", Dividend, Divisor, Quotient);
    return 0;
}

Der gleiche Algorithmus mit 32-Bit-Registern in einer NASM-GoLink-Kombination:

; Name:         div.asm
; Assemblieren: nasm.exe -fwin32 div.asm
; Linken:       golink.exe /console /entry _main div.obj crtdll.dll
;               (Linken mit msvcrt.dll stört Antivir und McAfee)
; Ergebnis:     div.exe

%MACRO writeln 1-*
EXTERN printf
    pushad
    jmp short %%SkipData
    %%fmt: db %1,10,0
    %%SkipData:
    %rep %0-1
      %rotate -1
      push %1
    %endrep
    push %%fmt
    call printf
    add esp, (%0*4)
    popad
%ENDMACRO

BITS 32

SEGMENT .data
    Dividend: dd 3979415386
    Divisor:  dd 100000

SEGMENT .bss
    Quotient resd 1

SEGMENT .text
GLOBAL _main
_main:                                 ; EDI = EAX / EBX
        mov eax, dword [Dividend]
        mov ebx, dword [Divisor]
        xor edi, edi                   ; Quotient = 0 (Anfangswert)
        xor edx, edx                   ; Zahl (dl) = 0 (Anfangswert)
        mov cl, 32                     ; 32 Schleifendurchgänge: for (CL=32; CL>0; CL--)
    Schleife:
        shl eax, 1                     ; Bit 31 von EAX ...
        rcl edx, 1                     ;     ... nach Bit 1 von EDX
        cmp ebx, edx                   ; Carry gesetzt, wenn EDX > Divisor (Fall Weiß)
        ja Sprungmarke                 ; Sprung, wenn Carry=0 und Zero=0 (Ergebnis nicht Null)
        sub edx, ebx                   ; Fall Weiß: EDX = EDX - EBX
        stc                            ; Carry setzen
    Sprungmarke:
        rcl edi, 1                     ; Carry (0 oder 1) an Quotienten kleben.
        sub cl, 1
        jnz Schleife
        mov dword [Quotient], edi

        writeln "%u div %u = %u", dword [Dividend], dword [Divisor], dword [Quotient]

        mov eax, 0                      ; Exitcode
        ret

Einige Antivirusprogramme (von Avira und McAfee) bereiten Schwierigkeiten, wenn ein Programm mit GoLink gegen MSVCRT.DLL gelinkt wurde. Da diese Programme aber eine Ausnahmeregel beinhalten, dass Assemblate von GoAsm unbehelligt bleiben, hier derselbe Algorithmus für eine GoAsm-GoLink-Kombination:

; Name:         div.asm
; Assemblieren: GoAsm.exe div.asm
; Linken:       GoLink.exe /console /entry _main div.obj msvcrt.dll
; Ergebnis:     div.exe

.DATA
    Dividend: dd 3979415386
    Divisor:  dd 100000
    fmt:      db "%u div %u = %u",10,0
    Quotient dd ?

.CODE
_main:                                 ; ; EDI = EAX / EBX
        mov eax, [Dividend]
        mov ebx, [Divisor]
        xor edi, edi                   ; Quotient = 0 (Anfangswert)
        xor edx, edx                   ; Zahl (dl) = 0 (Anfangswert)
        mov cl, 32                     ; 32 Schleifendurchgänge: for (CL=32; CL>0; CL--)
    Schleife:
        shl eax, 1                     ; Bit 31 von EAX ...
        rcl edx, 1                     ;     ... nach Bit 1 von EDX
        cmp ebx, edx                   ;  Carry gesetzt, wenn EDX > Divisor (Fall Weiß)
        ja >Sprungmarke                ; Sprung, wenn Carry=0 und Zero=0 (Ergebnis nicht Null)
        sub edx, ebx                   ; Fall Weiß: EDX = EDX - EBX
        stc                            ; Carry setzen
    Sprungmarke:
        rcl edi, 1                     ; Carry (0 oder 1) an Quotienten kleben.
        sub cl, 1
        jnz Schleife
        mov [Quotient], edi

        PUSH [Quotient], [Divisor], [Dividend], ADDR fmt
        call printf ; msvcrt.dll
        add     esp,16                 ; cdecl

        xor eax, eax                   ; Exitcode=0
        ret

Wenn der Divisor von vornherein feststeht, dann empfiehlt es sich, den DIV-Befehl durch eine geschickte Kombination von MUL, Shift- und Additionsbefehlen zu ersetzen. Eine umfangreiche Darstellung dieser Möglichkeit findet sich in Kapitel 8 (Integer Optimizations) des Software Optimization Guide for the AMD64 Processors. Die GCC-Kompilate (Eigenproduktion) der dort vorgestellten Programme idiv.exe und udiv.exe können hier heruntergeladen werden.

Ralph 'rkhb' Bauer Apr 2009