src/compiler-rt/lib/builtins/i386/umoddi3.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 // du_int __umoddi3(du_int a, du_int b);
   7
   8 // result = remainder of a / b.
   9 // both inputs and the output are 64-bit unsigned 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(__umoddi3)
  25
  26         pushl           %ebx
  27         movl     20(%esp),                      %ebx    // Find the index i of the leading bit in b.
  28         bsrl            %ebx,                   %ecx    // If the high word of b is zero, jump to
  29         jz                      9f                                              // the code to handle that special case [9].
  30
  31         /* High word of b is known to be non-zero on this branch */
  32
  33         movl     16(%esp),                      %eax    // Construct bhi, containing bits [1+i:32+i] of b
  34
  35         shrl            %cl,                    %eax    // Practically, this means that bhi is given by:
  36         shrl            %eax                                    //
  37         notl            %ecx                                    //              bhi = (high word of b) << (31 - i) |
  38         shll            %cl,                    %ebx    //                        (low word of b) >> (1 + i)
  39         orl                     %eax,                   %ebx    //
  40         movl     12(%esp),                      %edx    // Load the high and low words of a, and jump
  41         movl      8(%esp),                      %eax    // to [2] if the high word is larger than bhi
  42         cmpl            %ebx,                   %edx    // to avoid overflowing the upcoming divide.
  43         jae                     2f
  44
  45         /* High word of a is greater than or equal to (b >> (1 + i)) on this branch */
  46
  47         divl            %ebx                                    // eax <-- qs, edx <-- r such that ahi:alo = bs*qs + r
  48
  49         pushl           %edi
  50         notl            %ecx
  51         shrl            %eax
  52         shrl            %cl,                    %eax    // q = qs >> (1 + i)
  53         movl            %eax,                   %edi
  54         mull     20(%esp)                                       // q*blo
  55         movl     12(%esp),                      %ebx
  56         movl     16(%esp),                      %ecx    // ECX:EBX = a
  57         subl            %eax,                   %ebx
  58         sbbl            %edx,                   %ecx    // ECX:EBX = a - q*blo
  59         movl     24(%esp),                      %eax
  60         imull           %edi,                   %eax    // q*bhi
  61         subl            %eax,                   %ecx    // ECX:EBX = a - q*b
  62
  63         jnc                     1f                                              // if positive, this is the result.
  64         addl     20(%esp),                      %ebx    // otherwise
  65         adcl     24(%esp),                      %ecx    // ECX:EBX = a - (q-1)*b = result
  66 1:      movl            %ebx,                   %eax
  67         movl            %ecx,                   %edx
  68
  69         popl            %edi
  70         popl            %ebx
  71         retl
  72
  73
  74 2:      /* High word of a is greater than or equal to (b >> (1 + i)) on this branch */
  75
  76         subl            %ebx,                   %edx    // subtract bhi from ahi so that divide will not
  77         divl            %ebx                                    // overflow, and find q and r such that
  78                                                                                 //
  79                                                                                 //              ahi:alo = (1:q)*bhi + r
  80                                                                                 //
  81                                                                                 // Note that q is a number in (31-i).(1+i)
  82                                                                                 // fix point.
  83
  84         pushl           %edi
  85         notl            %ecx
  86         shrl            %eax
  87         orl                     $0x80000000,    %eax
  88         shrl            %cl,                    %eax    // q = (1:qs) >> (1 + i)
  89         movl            %eax,                   %edi
  90         mull     20(%esp)                                       // q*blo
  91         movl     12(%esp),                      %ebx
  92         movl     16(%esp),                      %ecx    // ECX:EBX = a
  93         subl            %eax,                   %ebx
  94         sbbl            %edx,                   %ecx    // ECX:EBX = a - q*blo
  95         movl     24(%esp),                      %eax
  96         imull           %edi,                   %eax    // q*bhi
  97         subl            %eax,                   %ecx    // ECX:EBX = a - q*b
  98
  99         jnc                     3f                                              // if positive, this is the result.
 100         addl     20(%esp),                      %ebx    // otherwise
 101         adcl     24(%esp),                      %ecx    // ECX:EBX = a - (q-1)*b = result
 102 3:      movl            %ebx,                   %eax
 103         movl            %ecx,                   %edx
 104
 105         popl            %edi
 106         popl            %ebx
 107         retl
 108
 109
 110
 111 9:      /* High word of b is zero on this branch */
 112
 113         movl     12(%esp),                      %eax    // Find qhi and rhi such that
 114         movl     16(%esp),                      %ecx    //
 115         xorl            %edx,                   %edx    //              ahi = qhi*b + rhi       with    0 ≤ rhi < b
 116         divl            %ecx                                    //
 117         movl            %eax,                   %ebx    //
 118         movl      8(%esp),                      %eax    // Find rlo such that
 119         divl            %ecx                                    //
 120         movl            %edx,                   %eax    //              rhi:alo = qlo*b + rlo  with 0 ≤ rlo < b
 121         popl            %ebx                                    //
 122         xorl            %edx,                   %edx    // and return 0:rlo
 123         retl                                                            //
 124 END_COMPILERRT_FUNCTION(__umoddi3)
 125
 126 #endif // __i386__