#******************************************************************************#*                                                                            *#* Functions for arithmetic and number theory with large integers in C        *#* Software supplement to the book "Cryptography in C and C++"                *#* by Michael Welschenbach                                                    *#*                                                                            *#* Module div.s            Revision: 15.06.2002                               *#*                                                                            *#*  Copyright (C) 1998-2005 by Michael Welschenbach                           *#*  Copyright (C) 2001-2005 by Springer-Verlag Berlin, Heidelberg             *#*  Copyright (C) 2001-2005 by Apress L.P., Berkeley, CA                      *#*  Copyright (C) 2002-2005 by Wydawnictwa MIKOM, Poland                      *#*  Copyright (C) 2002-2005 by PHEI, P.R.China                                *#*  Copyright (C) 2002-2005 by InfoBook, Korea                                *#*  Copyright (C) 2002-2005 by Triumph Publishing, Russia                     *#*                                                                            *#*  All Rights Reserved                                                       *#*                                                                            *#*  The software may be used for noncommercial purposes and may be altered,   *#*  as long as the following conditions are accepted without any              *#*  qualification:                                                            *#*                                                                            *#*  (1) All changes to the sources must be identified in such a way that the  *#*      changed software cannot be misinterpreted as the original software.   *#*                                                                            *#*  (2) The statements of copyright may not be removed or altered.            *#*                                                                            *#*  (3) The following DISCLAIMER is accepted:                                 *#*                                                                            *#*  DISCLAIMER:                                                               *#*                                                                            *#*  There is no warranty for the software contained in this distribution, to  *#*  the extent permitted by applicable law. The copyright holders provide the *#*  software `as is' without warranty of any kind, either expressed or        *#*  implied, including, but not limited to, the implied warranty of fitness   *#*  for a particular purpose. The entire risk as to the quality and           *#*  performance of the program is with you.                                   *#*                                                                            *#*  In no event unless required by applicable law or agreed to in writing     *#*  will the copyright holders, or any of the individual authors named in     *#*  the source files, be liable to you for damages, including any general,    *#*  special, incidental or consequential damages arising out of any use of    *#*  the software or out of inability to use the software (including but not   *#*  limited to any financial losses, loss of data or data being rendered      *#*  inaccurate or losses sustained by you or by third parties as a result of  *#*  a failure of the software to operate with any other programs), even if    *#*  such holder or other party has been advised of the possibility of such    *#*  damages.                                                                  *#*                                                                            *#******************************************************************************#*                                                                            *#*      Division, interface compatible with C-function div_l()                *#*                                                                            *#*      Quotient := Dividend div Divisor                                      *#*      Remainder := Dividend mod Divisor                                     *#*                                                                            *#*      Stack on calling of div_l:        SP+16 ---> Offset remainder         *#*                                        SP+12 ---> Offset quotient          *#*                                        SP+ 8 ---> Offset divisor           *#*                                        SP+ 4 ---> Offset dividend          *#*                                        SP    ---> Return address           *#*                                                                            *#*      Return Value: ax = -1 if divisor = 0                                  *#*                    ax =  0 else                                            *#*                                                                            *#******************************************************************************#.equ    a,      0		# Dividend (working copy)                  .equ    b,      1030		# Divisor  (working copy)                  .equ    q,      1546		# Quotient qhat (working memory)           .equ    q1,     2566		# High-order digit of divisor (normalized) .equ    v1,     2570		# 2nd digit of divisor (normalized)        .equ    v2,     2574		.equ    d,      2578		# Exponent for normalization.equ    uj1,    2582		# uj+1 (normalized)                        .equ    uj2,    2586            # uj+2 (normalized)                        #.equ    WORKSP, 2600		# Working memory in stack area#.text.globl  _div_l_div_l: pushl   %ebp		# Store value for calling procedure        movl    %esp,%ebp        subl    $WORKSP,%esp    # lokal working memory        movl    %esp,%eax        pushl   %ebx        pushl   %edi        pushl   %esi        movl    %eax,%ebx       # Store start address of working memory#        movl    8(%ebp),%esi    # Offset of variable a        movl    12(%ebp),%edi   # Offset of variable b        movw    (%esi),%ax      # l(a)        movw    (%edi),%dx      # l(b)        cmpw    $0,%dx		# b = 0 ?        jne     .l1        jmp     .divbyz		# Division by zero!##>>>>>> Lade Operanden#.l1:    pushl   %edi		# Store offset b        leal    a(%ebx),%edi    # Destination offset is a[bx]        xorl    %ecx,%ecx        movw    %ax,%cx		# l(a) in cx        shrw    $1,%cx        jnc     .l2        incw    %cx.l2:    cld     	rep     	movsl			# Load a as ULONG        movsw			#  plus one USHORT        movw    %ax,%cx        shlw    $1,%cx        leal    a+2(%ebx,%ecx),%edi        movw    $0,(%edi)#        popl    %esi		# Hole Seg:Offs von b        leal    b(%ebx),%edi    # Zieloffset ist b[bx]        xorl    %ecx,%ecx        movw    %dx,%cx		# l(b) in cx        shrw    $1,%cx        jnc     .l3        incw    %cx.l3:    cld             rep     	movsl			# Load b as ULONG        movsw			#  plus one USHORT        movw    %dx,%cx        shlw    $1,%cx        leal    b+2(%ebx,%ecx),%edi        movl    $0,(%edi)##>>>>>> Prepare access to local memory#        pushl   %ebp		# Store ebp        movl    %ebx,%ebp       # Indexed addressing based on ss##>>>>>> Remove leading zeros from operands#        xorl    %eax,%eax        xorl    %ecx,%ecx        movw    a(%ebp),%ax     # #USHORTs into ax        cmpw    $0,%ax        je      .next1        shll    $1,%eax		# Index to low-order byte                                # of high-order digit        movl    %eax,%esi.l4:    cmpw    $0,a(%ebp,%esi) # USHORT = 0 ?        jne     .l5		# If not we're done        subl    $2,%esi		# Else:	 Step back one digit        cmpl    $0,%esi		# Index = 0?        je      .mazer1		# Then argument = 0        jmp     .l4		# Next comparison    .l5:				# Length determined.mazer1:	shrl    $1,%esi		# #Digits        movl    %esi,%eax       # Basisadresse des Operanden holen        movw    %ax,a(%ebp)     # Store number of digits#Operand2.next1: movw    b(%ebp),%ax     # #USHORTs in ax        cmpw    $0,%ax        je      .end1        shll    $1,%eax		# #Bytes, index to low-order byte                                # of high-order digit        movl    %eax,%esi.l6:    cmpw    $0,b(%ebp,%esi) # Digit = 0 ?        jne     .l7		# If not we're done        subl    $2,%esi		# Else: Step back one digit        cmpl    $0,%esi		# Index = 0?                    je      .mazer2		# Then argument = 0             jmp     .l6		# Next comparison       .l7:				# Length found          .mazer2:	shrl    $1,%esi		# Number of digits        movl    %esi,%eax       # Store number of digits        movw    %ax,b(%ebp)     .end1:  cmpw    $0,%ax        jne     .l8        popl    %ebp        jmp     .divbyz.l8:    cmpw    $0,a(%ebp)        jne     .l9        popl    %ebp        jmp     .divz##>>>>>> Test a < b ?#.l9:    movl    $0,%ecx        movw    a(%ebp),%cx        cmpw    b(%ebp),%cx     # l(a) - l(b)        jnc     .div03        jmp     .dra.div03: jne     .div05          # If lengths are equal compare digits        movl    %ecx,%eax       # cl = l(a) = l(b)        shll    $1,%eax        leal    a(%ebp),%esi        leal    b(%ebp),%edi        addl    %eax,%edi       # si points to high-order digit of a        addl    %eax,%esi       # di points to high-order digit of b        std             repe    	cmpsw   #	xchg    %esi,%edi        cld             jnc     .div05		# If no carry occurs, q is positive        jmp     .dra		# Else q := 0 and r := a.div05: movw    b(%ebp),%ax        shrw    $1,%ax        jnc     .div05a        incw    %ax.div05a:	cmpw    $1,%ax		# Test if length l(b) = 1        jne     .dstart        jmp     .dshort		# If so go to short division##>>>>>> Start division#.dstart:	movl    $0,%eax        movw    b(%ebp),%ax        shrw    $1,%ax        jnc     .dm0        incw    %ax.dm0:   movl    %eax,%esi        shll    $2,%esi        subl    $2,%esi		# Pointer to low byte of b[l(b)]    				# (pointer to high-order ULONG)             cmpl    $10,%esi	# Does divisor have 3 or more digits?        jb      .dm1a		# Two digits are present at mininum!        movl    b(%ebp,%esi),%ebx       # b[l(b)] in bx        movl    b-4(%ebp,%esi),%eax        movl    b-8(%ebp,%esi),%edx#        movl    $0,%ecx		# Prepare counter#.l10:   cmpl    $0x080000000,%ebx       # v1 >= 2^31 ?        jae     .dm2		# If not ...        incw    %cx        clc             rcll    $1,%edx        rcll    $1,%eax        rcll    $1,%ebx		# v1 = v1 * 2        jmp     .l10		# until v1 >= 2^31.dm1a:  movl    b(%ebp,%esi),%ebx       # b[l(b)] in bx        movl    b-4(%ebp,%esi),%eax#        movl    $0,%ecx		# Prepare counter#.l11:   cmpl    $0x080000000,%ebx       # v1 >= 2^31 ?        jae     .dm2		# If not ...        incw    %cx        clc             rcll    $1,%eax        rcll    $1,%ebx		# v1 = v1 * 2        jmp     .l11		# until v1 >= 2^31#.dm2:   movw    %cx,d(%ebp)     # Store exponent        movl    %ebx,v1(%ebp)   # v1        movl    %eax,v2(%ebp)   # v2.dm3:   incw    a(%ebp)		# l(a) = l(a) + 2        incw    a(%ebp)        movl    $0,%eax        movw    a(%ebp),%ax        shrw    $1,%ax        jnc     .dm3a        incw    %ax.dm3a:  movl    %eax,%esi        shll    $2,%esi        subl    $2,%esi        movl    $0,a(%ebp,%esi) # a[l(a)] = 0#.d2:    movl    $0,%eax        movw    b(%ebp),%ax        shrw    $1,%ax        jnc     .d2a        incw    %ax.d2a:   movl    %eax,%esi        shll    $2,%esi        subl    $2,%esi		# si points to loByte of b[l(b)]#        movl    $0,%ecx        movw    a(%ebp),%cx        shrw    $1,%cx        jnc     .d2b        incw    %cx.d2b:   movl    %ecx,%edi        shll    $2,%edi        subl    $2,%edi		# di points to loByte of a[l(a)]        pushl   %edi        subl    %esi,%edi        incl    %edi		# di points to hiByte of a[l(a)-l(b)]        movl    %edi,%ecx        shrl    $2,%ecx		# Counter in cx        popl    %esi		# si points to loByte of a[l(a)] (j+l(b))        subl    $3,%edi		# di points to loByte of a[l(a)-l(b)] (j)        pushl   %edi		# Possible length of q##-----> Main loop of division