src/compiler-rt/lib/builtins/i386/moddi3.S

   1 // This file is dual licensed under the MIT and the University of Illinois Open
   2 // Source Licenses. See LICENSE.TXT for details.
   3
   4 #include "../assembly.h"
   5
   6 // di_int __moddi3(di_int a, di_int b);
   7
   8 // result = remainder of a / b.
   9 // both inputs and the output are 64-bit signed integers.
  10 // This will do whatever the underlying hardware is set to do on division by zero.
  11 // No other exceptions are generated, as the divide cannot overflow.
  12 //
  13 // This is targeted at 32-bit x86 *only*, as this can be done directly in hardware
  14 // on x86_64.  The performance goal is ~40 cycles per divide, which is faster than
  15 // currently possible via simulation of integer divides on the x87 unit.
  16 //
  17
  18 // Stephen Canon, December 2008
  19
  20 #ifdef __i386__
  21
  22 .text
  23 .balign 4
  24 DEFINE_COMPILERRT_FUNCTION(__moddi3)
  25
  26 /* This is currently implemented by wrapping the unsigned modulus up in an absolute
  27    value.  This could certainly be improved upon. */
  28
  29         pushl           %esi
  30         movl     20(%esp),                      %edx    // high word of b
  31         movl     16(%esp),                      %eax    // low word of b
  32         movl            %edx,                   %ecx
  33         sarl            $31,                    %ecx    // (b < 0) ? -1 : 0
  34         xorl            %ecx,                   %eax
  35         xorl            %ecx,                   %edx    // EDX:EAX = (b < 0) ? not(b) : b
  36         subl            %ecx,                   %eax
  37         sbbl            %ecx,                   %edx    // EDX:EAX = abs(b)
  38         movl            %edx,            20(%esp)
  39         movl            %eax,            16(%esp)       // store abs(b) back to stack
  40
  41         movl     12(%esp),                      %edx    // high word of b
  42         movl      8(%esp),                      %eax    // low word of b
  43         movl            %edx,                   %ecx
  44         sarl            $31,                    %ecx    // (a < 0) ? -1 : 0
  45         xorl            %ecx,                   %eax
  46         xorl            %ecx,                   %edx    // EDX:EAX = (a < 0) ? not(a) : a
  47         subl            %ecx,                   %eax
  48         sbbl            %ecx,                   %edx    // EDX:EAX = abs(a)
  49         movl            %edx,            12(%esp)
  50         movl            %eax,             8(%esp)       // store abs(a) back to stack
  51         movl            %ecx,                   %esi    // set aside sign of a
  52
  53         pushl           %ebx
  54         movl     24(%esp),                      %ebx    // Find the index i of the leading bit in b.
  55         bsrl            %ebx,                   %ecx    // If the high word of b is zero, jump to
  56         jz                      9f                                              // the code to handle that special case [9].
  57
  58         /* High word of b is known to be non-zero on this branch */
  59
  60         movl     20(%esp),                      %eax    // Construct bhi, containing bits [1+i:32+i] of b
  61
  62         shrl            %cl,                    %eax    // Practically, this means that bhi is given by:
  63         shrl            %eax                                    //
  64         notl            %ecx                                    //              bhi = (high word of b) << (31 - i) |
  65         shll            %cl,                    %ebx    //                        (low word of b) >> (1 + i)
  66         orl                     %eax,                   %ebx    //
  67         movl     16(%esp),                      %edx    // Load the high and low words of a, and jump
  68         movl     12(%esp),                      %eax    // to [2] if the high word is larger than bhi
  69         cmpl            %ebx,                   %edx    // to avoid overflowing the upcoming divide.
  70         jae                     2f
  71
  72         /* High word of a is greater than or equal to (b >> (1 + i)) on this branch */
  73
  74         divl            %ebx                                    // eax <-- qs, edx <-- r such that ahi:alo = bs*qs + r
  75
  76         pushl           %edi
  77         notl            %ecx
  78         shrl            %eax
  79         shrl            %cl,                    %eax    // q = qs >> (1 + i)
  80         movl            %eax,                   %edi
  81         mull     24(%esp)                                       // q*blo
  82         movl     16(%esp),                      %ebx
  83         movl     20(%esp),                      %ecx    // ECX:EBX = a
  84         subl            %eax,                   %ebx
  85         sbbl            %edx,                   %ecx    // ECX:EBX = a - q*blo
  86         movl     28(%esp),                      %eax
  87         imull           %edi,                   %eax    // q*bhi
  88         subl            %eax,                   %ecx    // ECX:EBX = a - q*b
  89
  90         jnc                     1f                                              // if positive, this is the result.
  91         addl     24(%esp),                      %ebx    // otherwise
  92         adcl     28(%esp),                      %ecx    // ECX:EBX = a - (q-1)*b = result
  93 1:      movl            %ebx,                   %eax
  94         movl            %ecx,                   %edx
  95
  96         addl            %esi,                   %eax    // Restore correct sign to result
  97         adcl            %esi,                   %edx
  98         xorl            %esi,                   %eax
  99         xorl            %esi,                   %edx
 100         popl            %edi                                    // Restore callee-save registers
 101         popl            %ebx
 102         popl            %esi
 103         retl                                                            // Return
 104
 105 2:      /* High word of a is greater than or equal to (b >> (1 + i)) on this branch */
 106
 107         subl            %ebx,                   %edx    // subtract bhi from ahi so that divide will not
 108         divl            %ebx                                    // overflow, and find q and r such that
 109                                                                                 //
 110                                                                                 //              ahi:alo = (1:q)*bhi + r
 111                                                                                 //
 112                                                                                 // Note that q is a number in (31-i).(1+i)
 113                                                                                 // fix point.
 114
 115         pushl           %edi
 116         notl            %ecx
 117         shrl            %eax
 118         orl                     $0x80000000,    %eax
 119         shrl            %cl,                    %eax    // q = (1:qs) >> (1 + i)
 120         movl            %eax,                   %edi
 121         mull     24(%esp)                                       // q*blo
 122         movl     16(%esp),                      %ebx
 123         movl     20(%esp),                      %ecx    // ECX:EBX = a
 124         subl            %eax,                   %ebx
 125         sbbl            %edx,                   %ecx    // ECX:EBX = a - q*blo
 126         movl     28(%esp),                      %eax
 127         imull           %edi,                   %eax    // q*bhi
 128         subl            %eax,                   %ecx    // ECX:EBX = a - q*b
 129
 130         jnc                     3f                                              // if positive, this is the result.
 131         addl     24(%esp),                      %ebx    // otherwise
 132         adcl     28(%esp),                      %ecx    // ECX:EBX = a - (q-1)*b = result
 133 3:      movl            %ebx,                   %eax
 134         movl            %ecx,                   %edx
 135
 136         addl            %esi,                   %eax    // Restore correct sign to result
 137         adcl            %esi,                   %edx
 138         xorl            %esi,                   %eax
 139         xorl            %esi,                   %edx
 140         popl            %edi                                    // Restore callee-save registers
 141         popl            %ebx
 142         popl            %esi
 143         retl                                                            // Return
 144
 145 9:      /* High word of b is zero on this branch */
 146
 147         movl     16(%esp),                      %eax    // Find qhi and rhi such that
 148         movl     20(%esp),                      %ecx    //
 149         xorl            %edx,                   %edx    //              ahi = qhi*b + rhi       with    0 ≤ rhi < b
 150         divl            %ecx                                    //
 151         movl            %eax,                   %ebx    //
 152         movl     12(%esp),                      %eax    // Find rlo such that
 153         divl            %ecx                                    //
 154         movl            %edx,                   %eax    //              rhi:alo = qlo*b + rlo  with 0 ≤ rlo < b
 155         popl            %ebx                                    //
 156         xorl            %edx,                   %edx    // and return 0:rlo
 157
 158         addl            %esi,                   %eax    // Restore correct sign to result
 159         adcl            %esi,                   %edx
 160         xorl            %esi,                   %eax
 161         xorl            %esi,                   %edx
 162         popl            %esi
 163         retl                                                            // Return
 164 END_COMPILERRT_FUNCTION(__moddi3)
 165
 166 #endif // __i386__