Frank's Technotes

64-bit divides on Intel 32-bit machines.

I recently had a need to perform a divide of a 64-bit signed integer by a 32-bit unsigned integer in an Pentium IV-based realtime system (running RTLinux and Linux 2.4.22). After some grubbing around on Google I came across John Eckerdal's Assembly Gems page, which features (among many other routines) a generalized routine for dividing 64-bit unsigned integers.

That routine is wonderful, but I needed to divide a signed 64-bit integer by an unsigned 32-bit integer. This is really just a special case of Eckerdal's routine, though, with a small wrapper to handle the sign of the dividend, viz:

if (dividend < 0) {
	neg = 1;
	dividend = -dividend;
}
__asm__ __volatile__(
"	movl	%2, %%eax\n"	/* Dividend low into eax.     */
"	movl	%3, %%edx\n"	/* Dividend high into edx.    */
"	movl	%4, %%ebx\n"	/* Divisor into ebx.          */
"	xorl	%%ecx, %%ecx\n"	/* Clear temp quotient high.  */
"	cmpl	%%ebx, %%edx\n"	/* If dividend high < divisor,*/
				/* result will fit in 32 bits,*/
				/* so we can use one divide.  */
"	jb	1f\n"		/* Yes, skip next divide.     */
"	movl	%%eax, %%ecx\n" /* Save dividend low in ecx.  */
/* Divide <dividend high>:<dividend low> by divisor.          */
"	divl	%%ebx\n"	/* Quotient in eax, remainder */
				/* in edx.                    */
"	xchgl	%%ecx, %%eax\n"	/* Quotient high to ecx,      */
				/* dividend low to eax.       */
/* Divide <high remainder>:<dividend low> by divisor.         */
"1:	divl	%%ebx\n"	/* Quotient low to eax,       */
				/* remainder to edx.          */
"	movl	%%ecx, %1\n"	/* Quotient high to result high. */
"	movl	%%eax, %0"	/* Quotient low to result low.   */
	: "=g" (ll_low(result)), "=g" (ll_high(result))
	: "g" (ll_low(dividend)), "g" (ll_high(dividend)),
	  "g" (divisor)
	: "memory", "eax", "ebx", "ecx", "edx", "cc");
if (neg)
	result = -result;

The commentary pretty much says it all. This is made a lot simpler by the constraints of my problem, in that I only have to divide by a 32-bit unsigned quantity, so I can skip most of the work Eckerdal does. My only extension is to convert the dividend to unsigned beforehand and then convert the result back to signed afterwards.

Simple, effective, and many times faster than the default Gnu C __divdi3() call to do the same thing.