unsigned 64 bit % const

[Frank Klemm]

unsigned long long % const can be reduced for a lot of 'const'.
Note that the following code is not corect, but shows the principle.

----------------------------------------------------------------------------

#include <stdio.h>

typedef unsigned long       u32;
typedef unsigned long long  u64;


void 
error ( u64 x, u32 t )
{
    fprintf ( stderr, "BUG in %llu / %lu\n\a\n", x, t);
}

int
main ( void )
{
    u64  x;
    
    for ( x = 0xFFFFFF00; ; x++ ) {
        if ( (x %   2) != ((u32)x & 1) )                    error (x,   2);
        if ( (x %   3) != ((u32)x +   (u32)(x>>32)) %   3 ) error (x,   3);
        if ( (x %   4) != ((u32)x & 3) )                    error (x,   4);
        if ( (x %   5) != ((u32)x +   (u32)(x>>32)) %   5 ) error (x,   5);
        if ( (x %   6) != ((u32)x + 4*(u32)(x>>32)) %   6 ) error (x,   6);
        if ( (x %   7) != ((u32)x + 4*(u32)(x>>32)) %   7 ) error (x,   7);
        if ( (x %   8) != ((u32)x & 7) )                    error (x,   8);
        if ( (x %   9) != ((u32)x + 4*(u32)(x>>32)) %   9 ) error (x,   9);
        if ( (x %  11) != ((u32)x + 4*(u32)(x>>32)) %  11 ) error (x,  11);
        if ( (x %  17) != ((u32)x +   (u32)(x>>32)) %  17 ) error (x,  17);
        if ( (x %  19) != ((u32)x + 6*(u32)(x>>32)) %  19 ) error (x,  19);
        if ( (x %  31) != ((u32)x + 4*(u32)(x>>32)) %  31 ) error (x,  31);
        if ( (x %  37) != ((u32)x + 7*(u32)(x>>32)) %  37 ) error (x,  37);
        if ( (x % 151) != ((u32)x + 4*(u32)(x>>32)) % 151 ) error (x, 151);
        if ( (x % 167) != ((u32)x + 7*(u32)(x>>32)) % 167 ) error (x, 167);
        if ( (x % 257) != ((u32)x +   (u32)(x>>32)) % 257 ) error (x, 257);
        if ( (x % 331) != ((u32)x + 4*(u32)(x>>32)) % 331 ) error (x, 331);
    }
    
    return 0;
}

--------------------------------------------------------------------------------
You must reduce x in the following way:

	x' = x_low + x_high * k;	where k = 2^32 % divider

x' can have more than 32 bit !!!
But x' is always small than divider * 2^32.

Code to generate for  (var % cst):

--- cst is a power of 2 -----------------------------------------------------

This is trivial!

	movl	var, %eax
	andl	$(cst - 1), %eax

	... the upper 32 bit are 0
	
	xorl	%edx, %edx

--- cst is 3, 5, 17, 257, 65537 (prime factors of 2^32-1) -------------------

Here we're reducing x' to 33 bit and then we are using div

	movl	var, %eax
	xorl	%edx, %edx
	addl	var + 4, %eax
	adcl	%edx, %edx
	movl	$cst, %ecx
	divl	%ecx
	movl	%edx, %eax
	xorl	%edx, %edx

--- cst is 3, 5, 17, 257, 65537 (prime factors of 2^32-1) -------------------

Here we're reducing x' to 32 bit and then we can use other tricky uint32 % const code

        movl    var, %eax
        addl    var + 4, %eax
        adcl    $0, %eax

        ... now a simple (32 bit % cst) to get the lower 32 bit, the upper 32 bit are 0

        xorl    %edx, %edx
        movl    $cst, %ecx
        divl    %ecx            ; may be you have a better solution for uint32 % const
        movl    %edx, %eax
        xorl    %edx, %edx


--- all other with 2^32 % cst < 65536 ---------------------------------------

Here we'r reducing x' to 32 bit and then we can use other tricky uint32 % const code

	k = 0x100000000 % cst, must be < 65536

	movl	$k, %eax
	mull	var + 4		; edx < k
	addl	var, %eax
	adcl	$0, %edx	; edx <= k
	jz	lbl		; should be removed for larger k (what is a larger k???), depends on imul / mispredicted jump trade-off
	imul	$k, %edx	; edx <= k*k
	addl	%edx, %eax
	adcl	$0, %eax
lbl:
	... now a simple (32 bit % cst) to get the lower 32 bit, the upper 32 bit are 0
	
	xorl	%edx, %edx
	movl	$cst, %ecx
	divl	%ecx		; may be you have a better solution for uint32 % const
	movl	%edx, %eax
	xorl	%edx, %edx

--- all other ---------------------------------------------------------------

Here we'r reducing x' to more than 32 bit and then we can use div

	k = 0x100000000 % cst, must be < 65536

	movl	$k, %eax
	mull	var + 4		; edx < k
	addl	var, %eax
	adcl	$0, %edx	; edx <= k < div
	movl	$cst, %ecx
	divl	%ecx		
	movl	%edx, %eax
	xorl	%edx, %edx

-------------------------------------------------------------------------------

This is for uint64 % uint32_const

The other 7 cases are:
	    uint64 % -uint32_const	(is this allowed ???)
	    int64  %  uint32_const
	    int64  % -uint32_const
            uint64 / uint32_const
	    uint64 / -uint32_const	(is this allowed ???)
	    int64  /  uint32_const
	    int64  / -uint32_const

Interest or too tricky? Does someone find bugs ???
	    
-- 
Frank Klemm