;******************************************************************************
;*                                                                            *
;*  Arithmetik und Zahlentheorie-Funktionen fuer grosse Zahlen in C           *
;*  Software zum Buch "Kryptographie in C und C++"                            *
;*  Autor: Michael Welschenbach                                               *
;*                                                                            *
;*  Quelldatei div.asm    Stand: 27.05.2000                                   *
;*                                                                            *
;*  Copyright (C) 1998-2001 by Michael Welschenbach                           *
;*  Copyright (C) 1998-2001 by Springer-Verlag Berlin, Heidelberg             *
;*                                                                            *
;*  All Rights Reserved                                                       *
;*                                                                            *
;*  Die Software darf fuer nichtkommerzielle Zwecke frei verwendet und        *
;*  veraendert werden, solange die folgenden Bedingungen anerkannt werden:    *
;*                                                                            *
;*  (1) Alle Aenderungen muessen als solche kenntlich gemacht werden, so dass *
;*      nicht der Eindruck erweckt wird, es handle sich um die Original-      *
;*      Software.                                                             *
;*                                                                            *
;*  (2) Die Copyright-Hinweise und die uebrigen Angaben in diesem Feld        *
;*      duerfen weder entfernt noch veraendert werden.                        *
;*                                                                            *
;*  (3) Weder der Verlag noch der Autor uebernehmen irgendeine Haftung fuer   *
;*      eventuelle Schaeden, die aus der Verwendung oder aus der Nicht-       *
;*      verwendbarkeit der Software, gleich fuer welchen Zweck, entstehen     *
;*      sollten, selbst dann nicht, wenn diese Schaeden durch Fehler verur-   *
;*      sacht wurden, die in der Software enthalten sein sollten.             *
;*                                                                            *
;******************************************************************************
;******************************************************************************
;*                                                                            *
;*      Division, Schnittstelle wie bei C-Funktion div_l()                    *
;*                                                                            *
;*      Quotient:=Dividend div Divisor                                        *
;*      Rest    :=Dividend mod Divisor                                        *
;*                                                                            *
;*      Stack bei Aufruf von  div_l:      SP+16 ---> Offset   Rest            *
;*                                        SP+12 ---> Offset   Quotient        *
;*                                        SP+ 8 ---> Offset   Divisor         *
;*                                        SP+ 4 ---> Offset   Dividend        *
;*                                        SP    ---> Return Adresse           *
;*                                                                            *
;*      Return Value: ax = -1 falls Divisor = 0                               *
;*                    ax =  0 sonst                                           *
;*                                                                            *
;******************************************************************************
PUBLIC div_l
.386
.MODEL FLAT
.CODE
div_l  proc near
;
a       equ     0                       ; Dividend (Arbeitskopie)
b       equ     1030                    ; Divisor  (Arbeitskopie)
q       equ     1546                    ; Quotient qdach (Arbeitsspeicher)
q1      equ     2566                    ; hoechstwertige Divisorstelle (normalisiert)
v1      equ     2570                    ; 2. Divisorstelle (normalisiert)
v2      equ     2574                    ; Exponent fuer Normalisierung
d       equ     2578                    ; uj+1 (normalisiert)
uj1     equ     2582                    ; uj+2 (normalisiert)
uj2     equ     2586
;
_dvd    equ     [ebp+8]                 ; Dividend (Parameter)
_dvs    equ     [ebp+12]                ; Divisor  (Parameter)
_qot    equ     [ebp+16]                ; Quotient (Parameter)
_rst    equ     [ebp+20]                ; Rest     (Parameter)
;
WORKSP  equ     2600                    ; Arbeitsspeicher auf dem Stack
;
divs:   push    ebp                     ; Sichern fuer aufrufende Prozedur
        mov     ebp,esp
        sub     esp,WORKSP              ; Lokaler Speicher
        mov     eax,esp
        push    ebx
        push    edi
        push    esi
        mov     ebx,eax                 ; Startadresse sichern
;
        mov     esi,_dvd                ; Offset von Var a
        mov     edi,_dvs                ; Offset von Var b
        mov     ax,[esi]                ; l(a)
        mov     dx,[edi]                ; l(b)
        cmp     dx,0                    ; b = 0 ?
        jne     @F
        jmp     divbyz                  ; Division durch Null!
;
;>>>>>> Lade Operanden
;
@@:     push    edi                     ; Rette Seg:Offs b
        lea     edi,a[ebx]              ; Zieloffset ist a[bx]
        xor     ecx,ecx
        mov     cx,ax                   ; l(a) in cx
        shr     cx,1
        jnc     @F
        inc     cx
@@:     cld
rep     movsd                           ; Lade a als ULONG
        movsw                           ;  plus ein USHORT
        mov     cx,ax
        shl     cx,1
        lea     edi,a[ebx+ecx+2]
        mov     word ptr [edi],0
;
        pop     esi                     ; Hole Seg:Offs von b
        lea     edi,b[ebx]              ; Zieloffset ist b[bx]
        xor     ecx,ecx
        mov     cx,dx                   ; l(b) in cx
        shr     cx,1
        jnc     @F
        inc     cx
@@:     cld
rep     movsd                           ; Lade b als ULONG
        movsw                           ;  plus ein USHORT
        mov     cx,dx
        shl     cx,1
        lea     edi,b[ebx+ecx+2]
        mov     word ptr [edi],0
;
;>>>>>> Adressierung des lokalen Arbeitsspeichers vorbereiten
;
        push    ebp                     ; bp retten
        mov     ebp,ebx                 ; Basisind. Adr. in ss
;
;>>>>>> Reduziere Darstellung der Operanden um fhrende Nullen
;
        xor     eax,eax
        xor     ecx,ecx
        mov     ax,a[ebp]               ; #USHORTs in ax
        cmp     ax,0
        je      next1
        shl     eax,1                   ; Index auf niederstwertiges Byte
                                        ; der hoechstwertigen Stelle
        mov     esi,eax
@@:     cmp     word ptr a[ebp][esi],0  ; USHORT = 0 ?
        jne     @F                      ; Nein, dann fertig
        sub     esi,2                   ; Sonst: eine Stelle zurueck
        cmp     esi,0                   ; Index = 0?
        je      mazer1                  ; Dann Zahl = 0
        jmp     @B                      ; Naechster Vergleich
@@:                                     ; Laenge gefunden
mazer1: shr     esi,1                   ; #Stellen
        mov     eax,esi                 ; Basisadresse des Operanden holen
        mov     word ptr a[ebp],ax      ; #Stellen speichern

;Operand2
next1:  mov     ax,b[ebp]               ; #USHORTs in ax
        cmp     ax,0
        je      end1
        shl     eax,1                   ; #Bytes, Index auf niederstwertiges Byte
                                        ; der hoechstwertigen Stelle
        mov     esi,eax
@@:     cmp     word ptr b[ebp][esi],0  ; Stelle = 0 ?
        jne     @F                      ; Nein, dann fertig
        sub     esi,2                   ; Sonst: eine Stelle zurueck
        cmp     esi,0                   ; Index schon = 0?
        je      mazer2                  ; Dann Zahl = 0
        jmp     @B                      ; Naechster Vergleich
@@:                                     ; Laenge gefunden
mazer2: shr     esi,1                   ; #Stellen
        mov     eax,esi                 ; Basisadresse des Operanden holen
        mov     b[ebp],ax               ; #Stellen speichern

end1:   cmp     ax,0
        jne     @F
        pop     ebp
        jmp     divbyz
@@:     cmp     word ptr a[ebp],0
        jne     @F
        pop     ebp
        jmp     divz
;
;>>>>>> Test a < b ?
;
@@:     mov     ecx,0
        mov     cx,a[ebp]
        cmp     cx,b[ebp]               ; l(a) - l(b)
        jnc     div03
        jmp     dra
div03:  jne     div05                   ; Bei Gleichheit Stellen vergleichen
        mov     eax,ecx                 ; cl = l(a) = l(b)
        shl     eax,1
        lea     esi,a[ebp]
        lea     edi,b[ebp]
        add     esi,eax                 ; si zeigt auf hoechste Stelle von a
        add     edi,eax                 ; di zeigt auf hoechste Stelle von b
        std
repe    cmpsw
        cld
        jnc     div05                   ; Falls kein carry ist q positiv
        jmp     dra                     ; Sonst q := 0 und r := a
div05:  mov     ax,b[ebp]
        shr     ax,1
        jnc     div05a
        inc     ax
div05a: cmp     ax,1                    ; Test ob l(b) = 1
        jne     dstart
        jmp     dshort                  ; Dann kuerzere Variante
;
;>>>>>> Beginn der Division
;
dstart: mov     eax,0
        mov     ax,b[ebp]
        shr     ax,1
        jnc     dm0
        inc     ax
dm0:    mov     esi,eax
        shl     esi,2
        sub     esi,2                   ; Zeiger auf loByte von b[l(b)] (hoechstes ULONG)
        cmp     esi,10                  ; Hat Divisor 3 oder mehr ULONG-Stellen?
        jb      dm1a                    ; Zwei Stellen hat er mindestens!

        mov     ebx,b[ebp][esi]         ; b[l(b)] in bx
        mov     eax,b[ebp][esi-4]
        mov     edx,b[ebp][esi-8]
;
        mov     ecx,0                   ; Zaehler vorbereiten
;
@@:     cmp     ebx,080000000h          ; v1 >= 2^31 ?
        jae     dm2                     ; Falls nicht...
        inc     cx
        clc
        rcl     edx,1
        rcl     eax,1
        rcl     ebx,1                   ; v1 = v1 * 2
        jmp     short @B                ; bis v1 >= 2^31

dm1a:   mov     ebx,b[ebp][esi]         ; b[l(b)] in bx
        mov     eax,b[ebp][esi-4]
;
        mov     ecx,0                   ; Zaehler vorbereiten
;
@@:     cmp     ebx,080000000h          ; v1 >= 2^31 ?
        jae     dm2                     ; Falls nicht...
        inc     cx
        clc
        rcl     eax,1
        rcl     ebx,1                   ; v1 = v1 * 2
        jmp     short @B                ; bis v1 >= 2^31
;
dm2:    mov     d[ebp],cx               ; Exponenten speichern
        mov     v1[ebp],ebx             ; v1
        mov     v2[ebp],eax             ; v2

dm3:    inc     word ptr a[ebp]         ; l(a) = l(a) + 2
        inc     word ptr a[ebp]
        mov     eax,0
        mov     ax,a[ebp]
        shr     ax,1
        jnc     dm3a
        inc     ax
dm3a:   mov     esi,eax
        shl     esi,2
        sub     esi,2
        mov     dword ptr a[ebp][esi],0 ; a[l(a)] = 0
;
d2:     mov     eax,0
        mov     ax,b[ebp]
        shr     ax,1
        jnc     d2a
        inc     ax
d2a:    mov     esi,eax
        shl     esi,2
        sub     esi,2                   ; si zeigt auf loByte von b[l(b)]
;
        mov     ecx,0
        mov     cx,a[ebp]
        shr     cx,1
        jnc     d2b
        inc     cx
d2b:    mov     edi,ecx
        shl     edi,2
        sub     edi,2                   ; di zeigt auf loByte von a[l(a)]
        push    edi
        sub     edi,esi
        inc     edi                     ; di zeigt auf hiByte von a[l(a)-l(b)]
        mov     ecx,edi
        shr     ecx,2                   ; Zaehler in cx
        pop     esi                     ; si zeigt auf loByte von a[l(a)] (j+l(b))
        sub     edi,3                   ; di zeigt auf loByte von a[l(a)-l(b)] (j)
        push    edi                     ; moegliche Laenge von q
;
;-----> Divisionsschleife
;
d3:     cmp     esi,14
        jb      d3a
        push    edi
        mov     edx,a[ebp][esi]         ; uj   ungeshifet in dx (hiWord)
        mov     eax,a[ebp][esi-4]       ; uj+1 ungeshiftet
        mov     ebx,a[ebp][esi-8]       ; uj+2 ungeshiftet
        mov     edi,a[ebp][esi-12]      ; uj+3 ungeshiftet
        push    ecx
        mov     cx,d[ebp]
@@:     cmp     cx,0
        je      @F
        rcl     edi,1
        rcl     ebx,1
        rcl     eax,1
        rcl     edx,1
        dec     cx
        jmp     @B
@@:     pop     ecx
        pop     edi
        jmp     qdach
;
d3a:    mov     edx,a[ebp][esi]         ; uj   ungeshiftet
        mov     eax,a[ebp][esi-4]       ; uj+1 ungeschiftet
        mov     ebx,a[ebp][esi-8]       ; uj+2 ungeshiftet
        push    ecx
        mov     cx,d[ebp]
@@:     cmp     cx,0
        je      @F
        rcl     ebx,1
        rcl     eax,1
        rcl     edx,1
        dec     cx
        jmp     @B
@@:     pop     ecx
;
;-----> qdach berechnen und testen
;
qdach:  mov uj1[ebp],eax       ;  geshiftetes uj+1 speichern
        mov uj2[ebp],ebx       ;  geshiftetes uj+2 speichern
        mov ebx,v1[ebp]        ;  v1 in bx
        cmp ebx,edx
        je bm1                 ; Falls v1 = uj q = b - 1
;
        div ebx                ; eax <- qdach
;                              ; edx <- rdach: = uj*b + uj+1 -qdach*v1 = (uj*b + uj+1) mod v1
        mov q1[ebp],eax        ; qdach zwischenspeichern
        cmp eax,0
        jne @F
        jmp dml                ; Falls q=0 naechste Stelle
;
bm1:    mov eax,0ffffffffh     ; eax <- qdach
        mov q1[ebp],eax        ; qdach zwischenspeichern
        mov edx,uj1[ebp]       ; edx <- uj+1
        add edx,v1[ebp]        ; edx <- uj+1 + v1 =: rdach
        jc d4                  ; rdach >= b => v2 * qdach < rdach * b
;
@@:     mov ebx,edx            ; ebx <- rdach
        mul dword ptr v2[ebp]  ; eax <- low(qdach * v2), edx <- high(qdach * v2)
        cmp edx,ebx            ; rdach >= high(qdach * v2) ?
        jb  d4                 ; CF == 1?  Dann fertig
        ja  @F                 ; rdach < high(qdach * v2) => reduziere qdach
        cmp eax,uj2[ebp]       ; uj+2 >= low(qdach * v2) ?
        jbe d4                 ; CF == 1 OR ZF == 1? Dann fertig
;
@@:     dec dword ptr q1[ebp]  ; Korrektur qdach--
        add ebx,v1[ebp]        ; ebx <- rdach + v1
        jc d4                  ; rdach >= b => v2 * qdach < rdach * b
        sub eax,v2[ebp]        ; (qdach * v2) - v2
        sbb edx,0
;
        cmp edx,ebx            ; rdach >= high(qdach * v2) ?
        jb  d4                 ; CF == 1?  Dann fertig
        ja  @B                 ; rdach < high(qdach * v2) => reduziere qdach
        cmp eax,uj2[ebp]       ; uj+2 >= low(qdach * v2) ?
        ja  @B                 ; CF==0 + ZF==0? => Reduktion von qdach wiederholen
;
d4:     push    ecx            ; Hauptzaehler retten
        push    esi            ; j + l(b) retten
        push    edi            ; j retten
        mov     cx,b[ebp]      ; Zaehler mit l(b) laden
        shr     cx,1
        jnc     d4a
        inc     cx
d4a:    mov     ebx,q1[ebp]    ; q in bx
        mov     esi,2
        mov     edx,0          ; Dummy bertrag
;
;-----> Multiplikation und Subtraktion
;
dms:    push    edx
        mov     eax,ebx                 ; q in ax
        mul     dword ptr b[ebp][esi]   ; hi:dx lo:ax
        sub     a[ebp][edi],eax
        adc     edx,0                   ; Carry zum naechsten Subtrahenden
        pop     eax
        sub     a[ebp][edi],eax
        adc     edx,0                   ; Carry zum naechsten Subtrahenden
        inc     edi
        inc     edi
        inc     edi
        inc     edi
        inc     esi
        inc     esi
        inc     esi
        inc     esi
        loop    dms
        sub     a[ebp][edi],edx
        jnc     dnc                     ; Korrektur falls bertrag
;
;-----> Korrektur
;
        pop     edi
        push    edi
        xor     ecx,ecx
        mov     cx,b[ebp]               ; Zaehler mit l(b) laden
        shr     cx,1
        jnc     d4b
        inc     cx
d4b:    mov     esi,2
        clc
d5:     mov     eax,b[ebp][esi]         ; b[i]
        adc     a[ebp][edi],eax         ; a[j+i] + b[i]
        inc     edi
        inc     edi
        inc     edi
        inc     edi
        inc     esi
        inc     esi
        inc     esi
        inc     esi
        loop    d5                      ; Aeussere Schleife
        jnc     d51
        inc     dword ptr a[ebp][edi]
d51:    dec     dword ptr q1[ebp]       ; q = q - 1
;
;
dnc:    pop     edi                     ; Zeiger und Zaehler holen
        pop     esi
        pop     ecx
dml:    mov     eax,q1[ebp]             ; q holen
        mov     q[ebp][edi],eax         ; q[j] = q
        sub     edi,4
        sub     esi,4
        dec     ecx                     ; Innere Schleife
        jz      d6
        jmp     d3
;
d6:     pop     edi                     ; l(a)-l(b)-1 in ULONGs holen
        add     edi,2                   ; di zeigt auf loByte des letzten USHORT
        mov     eax,0
@@:     cmp     ax,q[ebp][edi]          ; q[l(a)-l(b)]=0 ?
        jne     d7                      ; Falls ja ...
        dec     edi
        dec     edi                     ; ... l(q) = l(a) - l(b) - 1
        cmp     edi,0
        jne     short @B
d7:     mov     edx,edi
        shr     edx,1                   ; l(q) (#USHORTs) in dx
        mov     q[ebp],dx               ; l(q) speichern
;
;-----> Laenge des Restes finden
;
        mov     eax,0
        mov     ax,b[ebp]
        mov     ecx,eax
        shl     ax,1
        mov     edi,eax
        mov     ebx,0
        inc     edi
        inc     edi
d8:     dec     edi
        dec     edi                     ; di zeigt auf loByte von a[l(b)]
        cmp     a[ebp][edi],bx
        loope   d8
        jz      d9                      ; Falls a[bp][di]!= 0 muss ...
        inc     cx                      ; ... l korrigiert werden
d9:     mov     a[ebp],cx               ; l(r) speichern
;
;-----> Ergebnisse speichern
;
dstore: mov     esi,ebp
        mov     ebx,ebp
        pop     ebp
        push    esi
        add     esi,q
        mov     edi,_qot                ; Ziel-Offset des Quotienten
        mov     ecx,0
        mov     cx,[esi]
        shr     cx,1
        jnc     @F
        inc     cx
@@:     cld
        cmp     cx,0
        je      qzero
rep     movsd
qzero:  movsw
;
;-----> Rest speichern
;
        pop     esi
drs:
        mov     edi,_rst
        add     esi,a
        mov     ecx,0
        mov     cx,[esi]
        shr     cx,1
        jnc     @F
        inc     cx
@@:     cld
        cmp     cx,0
        je      rzero
rep     movsd
rzero:  movsw
        mov     eax,0                   ; Return-Value = 0: alles OK
;
;*******************************************************************************
;       Security: Stack lschen

divret: mov     edi,ebx
        mov     ecx,(WORKSP-4)/4
        cld
rep     stosd                           ; Ueberschreiben mit 0 oder -1
;*******************************************************************************
;
        pop     esi
        pop     edi
        pop     ebx
        mov     esp,ebp
        pop     ebp
        ret
;
;
divz:   mov     eax,0                   ; Return-Value = 0: alles OK
        mov     edi,_rst                ; Offset des Restparameters
        mov     esi,_qot                ; Offset des Quotientenparameters
        mov     [edi],ax                ; Rest = 0
        mov     [esi],ax                ; Quotient = 0
        jmp     short divret
;
divbyz: mov     eax,-1
        jmp     short divret            ; Return-Value = -1: Division durch Null
;
;-----> Behandlung des Falles q = 0 und r = a
;
dra:    mov     esi,ebp
        mov     ebx,ebp
        pop     ebp
        mov     edi,_qot
        mov     word ptr [edi],0        ; q = 0
        jmp     short drs               ; Restparameter belegen
;
;
;>>>>>> Kurze Division
;
;
dshort: mov     ecx,0
        mov     cx,a[ebp]
        shr     cx,1
        jnc     dsh0
        inc     cx
dsh0:   mov     edi,ecx
        shl     edi,2
        sub     edi,2
        mov     edx,0
        mov     ebx,b[ebp+2]
dsh1:   mov     eax,a[ebp][edi]
        div     ebx
        mov     q[ebp][edi],eax
        sub     edi,4
        loop    dsh1
dsh2:   mov     ecx,0
        mov     cx,a[ebp]
        mov     esi,ecx
        shl     esi,1
@@:     mov     bx,q[ebp][esi]
        cmp     bx,0
        jne     dsh3
        dec     esi
        dec     esi
        dec     ecx
        cmp     cx,0
        jne     short @B
dsh3:   mov     q[ebp],cx
        mov     a[ebp+2],edx
        mov     word ptr a[ebp],2
        cmp     word ptr a[ebp+4],0
        jne     dst
        mov     word ptr a[ebp],1
        cmp     word ptr a[ebp+2],0
        jne     dst
        mov     word ptr a[ebp],0
dst:    jmp     dstore
;
div_l  endp
END

