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