contrib/compiler-rt/lib/builtins/i386/umoddi3.S

   1 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   2 // See https://llvm.org/LICENSE.txt for license information.
   3 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   4
   5 #include "../assembly.h"
   6
   7 // du_int __umoddi3(du_int a, du_int b);
   8
   9 // result = remainder of a / b.
  10 // both inputs and the output are 64-bit unsigned integers.
  11 // This will do whatever the underlying hardware is set to do on division by zero.
  12 // No other exceptions are generated, as the divide cannot overflow.
  13 //
  14 // This is targeted at 32-bit x86 *only*, as this can be done directly in hardware
  15 // on x86_64.  The performance goal is ~40 cycles per divide, which is faster than
  16 // currently possible via simulation of integer divides on the x87 unit.
  17 //
  18
  19 // Stephen Canon, December 2008
  20
  21 #ifdef __i386__
  22
  23 .text
  24 .balign 4
  25 DEFINE_COMPILERRT_FUNCTION(__umoddi3)
  26
  27         pushl           %ebx
  28         movl     20(%esp),                      %ebx    // Find the index i of the leading bit in b.
  29         bsrl            %ebx,                   %ecx    // If the high word of b is zero, jump to
  30         jz                      9f                                              // the code to handle that special case [9].
  31
  32         // High word of b is known to be non-zero on this branch
  33
  34         movl     16(%esp),                      %eax    // Construct bhi, containing bits [1+i:32+i] of b
  35
  36         shrl            %cl,                    %eax    // Practically, this means that bhi is given by:
  37         shrl            %eax                                    //
  38         notl            %ecx                                    //              bhi = (high word of b) << (31 - i) |
  39         shll            %cl,                    %ebx    //                        (low word of b) >> (1 + i)
  40         orl                     %eax,                   %ebx    //
  41         movl     12(%esp),                      %edx    // Load the high and low words of a, and jump
  42         movl      8(%esp),                      %eax    // to [2] if the high word is larger than bhi
  43         cmpl            %ebx,                   %edx    // to avoid overflowing the upcoming divide.
  44         jae                     2f
  45
  46         // High word of a is greater than or equal to (b >> (1 + i)) on this branch
  47
  48         divl            %ebx                                    // eax <-- qs, edx <-- r such that ahi:alo = bs*qs + r
  49
  50         pushl           %edi
  51         notl            %ecx
  52         shrl            %eax
  53         shrl            %cl,                    %eax    // q = qs >> (1 + i)
  54         movl            %eax,                   %edi
  55         mull     20(%esp)                                       // q*blo
  56         movl     12(%esp),                      %ebx
  57         movl     16(%esp),                      %ecx    // ECX:EBX = a
  58         subl            %eax,                   %ebx
  59         sbbl            %edx,                   %ecx    // ECX:EBX = a - q*blo
  60         movl     24(%esp),                      %eax
  61         imull           %edi,                   %eax    // q*bhi
  62         subl            %eax,                   %ecx    // ECX:EBX = a - q*b
  63
  64         jnc                     1f                                              // if positive, this is the result.
  65         addl     20(%esp),                      %ebx    // otherwise
  66         adcl     24(%esp),                      %ecx    // ECX:EBX = a - (q-1)*b = result
  67 1:      movl            %ebx,                   %eax
  68         movl            %ecx,                   %edx
  69
  70         popl            %edi
  71         popl            %ebx
  72         retl
  73
  74
  75 2:      // High word of a is greater than or equal to (b >> (1 + i)) on this branch
  76
  77         subl            %ebx,                   %edx    // subtract bhi from ahi so that divide will not
  78         divl            %ebx                                    // overflow, and find q and r such that
  79                                                                                 //
  80                                                                                 //              ahi:alo = (1:q)*bhi + r
  81                                                                                 //
  82                                                                                 // Note that q is a number in (31-i).(1+i)
  83                                                                                 // fix point.
  84
  85         pushl           %edi
  86         notl            %ecx
  87         shrl            %eax
  88         orl                     $0x80000000,    %eax
  89         shrl            %cl,                    %eax    // q = (1:qs) >> (1 + i)
  90         movl            %eax,                   %edi
  91         mull     20(%esp)                                       // q*blo
  92         movl     12(%esp),                      %ebx
  93         movl     16(%esp),                      %ecx    // ECX:EBX = a
  94         subl            %eax,                   %ebx
  95         sbbl            %edx,                   %ecx    // ECX:EBX = a - q*blo
  96         movl     24(%esp),                      %eax
  97         imull           %edi,                   %eax    // q*bhi
  98         subl            %eax,                   %ecx    // ECX:EBX = a - q*b
  99
 100         jnc                     3f                                              // if positive, this is the result.
 101         addl     20(%esp),                      %ebx    // otherwise
 102         adcl     24(%esp),                      %ecx    // ECX:EBX = a - (q-1)*b = result
 103 3:      movl            %ebx,                   %eax
 104         movl            %ecx,                   %edx
 105
 106         popl            %edi
 107         popl            %ebx
 108         retl
 109
 110
 111
 112 9:      // High word of b is zero on this branch
 113
 114         movl     12(%esp),                      %eax    // Find qhi and rhi such that
 115         movl     16(%esp),                      %ecx    //
 116         xorl            %edx,                   %edx    //              ahi = qhi*b + rhi       with    0 ≤ rhi < b
 117         divl            %ecx                                    //
 118         movl            %eax,                   %ebx    //
 119         movl      8(%esp),                      %eax    // Find rlo such that
 120         divl            %ecx                                    //
 121         movl            %edx,                   %eax    //              rhi:alo = qlo*b + rlo  with 0 ≤ rlo < b
 122         popl            %ebx                                    //
 123         xorl            %edx,                   %edx    // and return 0:rlo
 124         retl                                                            //
 125 END_COMPILERRT_FUNCTION(__umoddi3)
 126
 127 #endif // __i386__
 128
 129 NO_EXEC_STACK_DIRECTIVE
 130