Here are two assembly language functions which perform division of 32-bit and 16-bit numbers by values in the range 1…16 inclusive. Although the range of the divisor is very limited, these functions are significantly faster than conventional division functions. The 32-bit division requires about 25% of the time required by C51's 32-bit division and the 16-bit division requires about 60% of the time required by C51's 16-bit division. (Even though the Keil division functions seem to be well optimised.) The 32-bit division function is sufficiently fast that it may called more than once to divide a 32-bit value by a large value that has convenient factors. For example, dividing by 60 by first dividing by ten and then by six. This will still be significantly faster than conventional division. The functions also return a remainder and may find useful application in radix conversion by repeated division by the radix. These functions use the interesting trick of deriving a pointer into the current register bank. This allows the functions to loop through the dividend making the code much more compact although at the slight cost of speed.
And a test harness:
extern unsigned int fast_int_divide( unsigned int dividend, unsigned char divisor ) small; extern unsigned long int fast_long_divide( unsigned long int dividend, unsigned char divisor ) small; unsigned int compiler_int_divide( unsigned int dividend, unsigned char divisor ) { return( dividend / divisor ); } unsigned int new_int_divide( unsigned int dividend, unsigned char divisor ) { return( fast_int_divide( dividend, divisor ) ); } unsigned long int compiler_long_divide( unsigned long int dividend, unsigned char divisor ) { return( dividend / divisor ); } unsigned long int new_long_divide( unsigned long int dividend, unsigned char divisor ) { return( fast_long_divide( dividend, divisor ) ); } unsigned long int random() { static unsigned int x; x = ( ( 31 * x ) + 123 ); if( x == 0xFFFF ) x = 0; return(x); } void main( void ) { unsigned int loop; unsigned int d; unsigned int sd; unsigned int i; unsigned long int l; unsigned long int lr; unsigned char dummy; dummy = 0; lr = new_long_divide( new_long_divide( 0x12345678, 6 ), 10 ); for( loop = 0; loop < 0xFFFF; loop++ ) { i = random(); d = random(); if( d == 0 ) d = 1; l = ( (unsigned long int) ( random() & 0xFF ) << ( random() % 24 ) ); sd = random() % 17; // small divisor always in range 1...16 if( sd == 0 ) sd = 1; if( new_int_divide( i, sd ) != compiler_int_divide( i, sd ) ) { dummy++; } if( new_long_divide( l, sd ) != compiler_long_divide( l, sd ) ) { dummy++; } } }
I have posted updated versions of these functions here: http://www.programmersheaven.com/zone5/cat27/32144.htm The versions posted on the Keil forum contain a minor bug in that the remainder is not returned correctly. The versions at Programmers Heaven are correct and include a radix conversion function. I have posted some other nuggets which can be found here: http://www.programmersheaven.com/zone5/cat27/index.htm Each of my contributions has the epithet fast.