1132718Skan// This file is dual licensed under the MIT and the University of Illinois Open 290075Sobrien// Source Licenses. See LICENSE.TXT for details. 390075Sobrien 490075Sobrien#include "../assembly.h" 590075Sobrien 690075Sobrien// du_int __udivdi3(du_int a, du_int b); 790075Sobrien 890075Sobrien// result = a / b. 990075Sobrien// both inputs and the output are 64-bit unsigned integers. 1090075Sobrien// This will do whatever the underlying hardware is set to do on division by zero. 1190075Sobrien// No other exceptions are generated, as the divide cannot overflow. 1290075Sobrien// 1390075Sobrien// This is targeted at 32-bit x86 *only*, as this can be done directly in hardware 1490075Sobrien// on x86_64. The performance goal is ~40 cycles per divide, which is faster than 1590075Sobrien// currently possible via simulation of integer divides on the x87 unit. 1690075Sobrien// 1790075Sobrien// Stephen Canon, December 2008 1890075Sobrien 1990075Sobrien#ifdef __i386__ 2090075Sobrien 2190075Sobrien.text 2290075Sobrien.balign 4 2390075SobrienDEFINE_COMPILERRT_FUNCTION(__udivdi3) 2490075Sobrien 2590075Sobrien pushl %ebx 26132718Skan movl 20(%esp), %ebx // Find the index i of the leading bit in b. 2790075Sobrien bsrl %ebx, %ecx // If the high word of b is zero, jump to 2890075Sobrien jz 9f // the code to handle that special case [9]. 2990075Sobrien 3090075Sobrien /* High word of b is known to be non-zero on this branch */ 3190075Sobrien 3290075Sobrien movl 16(%esp), %eax // Construct bhi, containing bits [1+i:32+i] of b 3390075Sobrien 3490075Sobrien shrl %cl, %eax // Practically, this means that bhi is given by: 3590075Sobrien shrl %eax // 3690075Sobrien notl %ecx // bhi = (high word of b) << (31 - i) | 3790075Sobrien shll %cl, %ebx // (low word of b) >> (1 + i) 3890075Sobrien orl %eax, %ebx // 3990075Sobrien movl 12(%esp), %edx // Load the high and low words of a, and jump 4090075Sobrien movl 8(%esp), %eax // to [1] if the high word is larger than bhi 4190075Sobrien cmpl %ebx, %edx // to avoid overflowing the upcoming divide. 4290075Sobrien jae 1f 4390075Sobrien 4490075Sobrien /* High word of a is greater than or equal to (b >> (1 + i)) on this branch */ 4590075Sobrien 4690075Sobrien divl %ebx // eax <-- qs, edx <-- r such that ahi:alo = bs*qs + r 4790075Sobrien 4890075Sobrien pushl %edi 4990075Sobrien notl %ecx 5090075Sobrien shrl %eax 5190075Sobrien shrl %cl, %eax // q = qs >> (1 + i) 5290075Sobrien movl %eax, %edi 5390075Sobrien mull 20(%esp) // q*blo 5490075Sobrien movl 12(%esp), %ebx 5590075Sobrien movl 16(%esp), %ecx // ECX:EBX = a 5690075Sobrien subl %eax, %ebx 5790075Sobrien sbbl %edx, %ecx // ECX:EBX = a - q*blo 5890075Sobrien movl 24(%esp), %eax 5990075Sobrien imull %edi, %eax // q*bhi 6090075Sobrien subl %eax, %ecx // ECX:EBX = a - q*b 6190075Sobrien sbbl $0, %edi // decrement q if remainder is negative 6290075Sobrien xorl %edx, %edx 6390075Sobrien movl %edi, %eax 6490075Sobrien popl %edi 6590075Sobrien popl %ebx 6690075Sobrien retl 6790075Sobrien 6890075Sobrien 6990075Sobrien1: /* High word of a is greater than or equal to (b >> (1 + i)) on this branch */ 7090075Sobrien 7190075Sobrien subl %ebx, %edx // subtract bhi from ahi so that divide will not 7290075Sobrien divl %ebx // overflow, and find q and r such that 7390075Sobrien // 7490075Sobrien // ahi:alo = (1:q)*bhi + r 7590075Sobrien // 7690075Sobrien // Note that q is a number in (31-i).(1+i) 7790075Sobrien // fix point. 7890075Sobrien 7990075Sobrien pushl %edi 8090075Sobrien notl %ecx 8190075Sobrien shrl %eax 8290075Sobrien orl $0x80000000, %eax 8390075Sobrien shrl %cl, %eax // q = (1:qs) >> (1 + i) 8490075Sobrien movl %eax, %edi 8590075Sobrien mull 20(%esp) // q*blo 8690075Sobrien movl 12(%esp), %ebx 8790075Sobrien movl 16(%esp), %ecx // ECX:EBX = a 8890075Sobrien subl %eax, %ebx 8990075Sobrien sbbl %edx, %ecx // ECX:EBX = a - q*blo 9090075Sobrien movl 24(%esp), %eax 9190075Sobrien imull %edi, %eax // q*bhi 9290075Sobrien subl %eax, %ecx // ECX:EBX = a - q*b 9390075Sobrien sbbl $0, %edi // decrement q if remainder is negative 9490075Sobrien xorl %edx, %edx 9590075Sobrien movl %edi, %eax 9690075Sobrien popl %edi 9790075Sobrien popl %ebx 9890075Sobrien retl 9990075Sobrien 10090075Sobrien 10190075Sobrien9: /* High word of b is zero on this branch */ 102132718Skan 10390075Sobrien movl 12(%esp), %eax // Find qhi and rhi such that 10490075Sobrien movl 16(%esp), %ecx // 10590075Sobrien xorl %edx, %edx // ahi = qhi*b + rhi with 0 ��� rhi < b 10690075Sobrien divl %ecx // 10790075Sobrien movl %eax, %ebx // 10890075Sobrien movl 8(%esp), %eax // Find qlo such that 10990075Sobrien divl %ecx // 11090075Sobrien movl %ebx, %edx // rhi:alo = qlo*b + rlo with 0 ��� rlo < b 11190075Sobrien popl %ebx // 11290075Sobrien retl // and return qhi:qlo 11390075SobrienEND_COMPILERRT_FUNCTION(__udivdi3) 11490075Sobrien 11590075Sobrien#endif // __i386__ 11690075Sobrien