/* Implement division / modulus as 64x64 bit
* for 32-bit CPUs.
*
* *** Code has been verified ***
*
* Assumes a Little-Endian CPU, such as
* i386 or Android-ARMs.
*
* Assumes that 64-bit by 32-bit multiply
* is nevertheless defined natively.
* If 64x64 multiply is not defined on the CPU,
* then a long multiplication must be defined,
* which the simple divisions
* can both rely on:
*
* Divide64by32()
* Divide48by24()
*
* by Dirk Mittler
* June 2, 2018
*
* April 13, 2021:
* Replaced 'unsigned long int' and 'unsigned short int'
* declarations with 'uint64_t' and 'uint16_t'.
*
*/
#include
#include
//#include
//#include
//#include
//#include
using std::cout;
using std::endl;
//using std::fixed;
//using std::setprecision;
//using std::numeric_limits;
//using std::sqrt;
//using std::pow;
//using std::strtoul;
//using std::min;
int Divide64by32(uint64_t a, uint64_t b,
uint64_t *q, uint64_t *mod) {
// We know that b has at least a 33-bit value
unsigned int q_temp = 0;
unsigned int q_cum = 0;
uint64_t remaind = 0L;
unsigned int remaind_word = 0;
unsigned int b_word = *( (unsigned int *) ( (char*) ( &b ) + 4 ) ) + 1 ;
do {
remaind = a - (q_cum * b);
if (!b_word) break;
remaind_word = *( (unsigned int *) ( (char*) ( &remaind ) + 4 ) ) ;
q_temp = remaind_word / b_word; // 32-bit !
q_cum += q_temp;
} while (q_temp > 0) ;
if (remaind >= b) {
remaind -= b;
q_cum++;
}
*q = 0L;
*q = q_cum;
*mod = remaind;
return 0;
}
int Mod64by32(uint64_t a, unsigned int b,
unsigned int *mod) {
// Just for curiosity's sake
// We know that b has at least a 32-bit value
uint64_t remaind = 0L;
unsigned int remaind_word = 0;
uint64_t b_temp = 0L;
if ( (unsigned int) ( b ) < 0x80000000 ) return -1;
b_temp = ( uint64_t ) ( b ) ;
remaind = a;
remaind_word = *( (unsigned int *) ( (char*) ( &remaind ) + 4 ) ) ;
for ( ; remaind_word > 0 ; ) {
// In C or C++ something needs to signal that
// we want a 64-bit product, from the parameter-types .
// This is why I made (b_temp) an unsigned long int .
remaind -= remaind_word * b_temp;
remaind_word = *( (unsigned int *) ( (char*) ( &remaind ) + 4 ) ) ;
}
if (remaind >= b_temp) {
remaind -= b_temp;
}
*mod = ( unsigned int ) ( remaind ) ;
return 0;
}
int Divide48by24(uint64_t a, uint64_t b,
uint64_t *q, uint64_t *mod) {
// We know that a has 48 LSBs
// b has from 17 to 32 LSBs
unsigned int q_temp = 0;
unsigned int q_cum = 0;
uint64_t remaind = 0L;
unsigned int remaind_word = 0;
unsigned int b_word = *( (unsigned int *) ( (char*) ( &b ) + 2 ) ) + 1 ;
do {
remaind = a - (q_cum * b);
if (!b_word) break;
remaind_word = *( (unsigned int *) ( (char*) ( &remaind ) + 2 ) ) ;
q_temp = remaind_word / b_word; // 32-bit !
q_cum += q_temp;
} while (q_temp > 0) ;
if (remaind >= b) {
remaind -= b;
q_cum++;
}
*q = 0L;
*q = q_cum;
*mod = remaind;
return 0;
}
int Divide64by24(uint64_t a, uint64_t b,
uint64_t *q, uint64_t *mod) {
// We know that b has from 17 to 32 LSBs
uint64_t small_a = 0L;
uint64_t remaind = 0L;
uint64_t q_temp = 0L;
uint64_t q_cum = 0L;
small_a = *( (uint64_t *) ( (char*) ( &a ) + 2 ) ) ;
*( ( uint16_t *) ( (char*) ( &small_a ) + 6 ) ) =
(uint16_t) ( 0 ) ;
Divide48by24(small_a, b, &q_temp, &remaind);
*( (unsigned int *) ( (char*) ( &q_cum ) + 2 ) ) =
(unsigned int) ( q_temp );
// q_cum = (uint16_t) ( 0 ) ;
small_a = 0L;
*( (unsigned int *) ( (char*) ( &small_a ) + 2 ) ) =
(unsigned int) ( remaind );
*( (uint16_t *) ( &small_a ) ) = (uint16_t) ( a ) ;
Divide48by24(small_a, b, &q_temp, &remaind);
*q = q_cum + q_temp;
*mod = remaind;
return 0;
}
inline int Divide32by16(uint64_t a, uint64_t b,
uint64_t *q, uint64_t *mod) {
// As the name says
*q = 0L;
*q = (unsigned int) ( a ) / (unsigned int) ( b ) ;
*mod = 0L;
*mod = (unsigned int) ( a ) % (unsigned int) ( b ) ;
return 0;
}
int Divide64by16(uint64_t a, uint64_t b,
uint64_t *q, uint64_t *mod) {
// We know that b has 16 or fewer LSBs
uint64_t small_a = 0L;
uint64_t remaind = 0L;
uint64_t q_temp = 0L;
uint64_t q_cum = 0L;
small_a = *( (unsigned int *) ( (char*) ( &a ) + 4) ) ;
Divide32by16(small_a, b, &q_temp, &remaind);
*( (unsigned int *) ( (char*) ( &q_cum) + 4 ) ) =
(unsigned int) ( q_temp );
// q_cum = (unsigned int) ( 0 ) ;
small_a = 0L;
*( (uint16_t *) ( (char *) ( &small_a ) + 2 ) ) =
(uint16_t) ( remaind );
*( (uint16_t *) ( &small_a ) ) =
*( (uint16_t *) ( (char*) ( &a ) + 2 ) );
Divide32by16(small_a, b, &q_temp, &remaind);
*( (uint16_t *) ( (char*) ( &q_cum ) + 2 ) ) =
(uint16_t) ( q_temp );
small_a = 0L;
*( (uint16_t *) ( (char*) ( &small_a ) + 2 ) ) =
(uint16_t) ( remaind );
*( (uint16_t *) ( &small_a ) ) =
(uint16_t) ( a );
Divide32by16(small_a, b, &q_temp, &remaind);
*q = q_cum + q_temp;
*mod = remaind;
return 0;
}
int Divide64by64(uint64_t a, uint64_t b,
uint64_t *q, uint64_t *mod) {
/* Accepts as input 64-bit unsigned long ints a and b ,
* divides a by b ,
* leaves quotient in 64-bit *q ,
* leaves modulus in 64-bit *mod .
* */
if ( *( ( unsigned int *) ( (char*) ( &b ) + 4 ) ) ) {
return Divide64by32(a, b, q, mod);
} else if ( ( unsigned int ) ( b ) >= 0x00010000 ) {
return Divide64by24(a, b, q, mod);
} else if ( ( unsigned int ) ( b ) >= 0x00000001 ) {
return Divide64by16(a, b, q, mod);
}
return -1;
}
int main(int argc, char* argv[]) {
// Divide64by32()
cout << "Let us test the 64-by-64-bit division routine." << endl;
cout << endl;
uint64_t dividend = 0x1234567812345678;
uint64_t divisor = 0x00000000FFFFFFFF;
cout << dividend << endl;
cout << "Divided by " << divisor << endl;
cout << endl;
uint64_t quotient = 0L;
uint64_t remainder = 0L;
Divide64by64(dividend, divisor, "ient, &remainder);
cout << "Equals " << quotient << "R" << remainder << endl;
cout << endl;
if (quotient * divisor + remainder == dividend) {
cout << "Verified!" << endl;
} else {
cout << "Fail!" << endl;
if ((dividend < ((quotient + 1L) * divisor) &&
(dividend > (quotient * divisor)))) {
cout << "The quotient seems correct, but" << endl;
cout << "The remainder was wrong." << endl;
} else {
cout << "Not even the quotient is correct!" << endl;
}
}
cout << endl;
// Divide64by24
divisor = 0x0000000000FFFFFF;
cout << dividend << endl;
cout << "Divided by " << divisor << endl;
cout << endl;
quotient = 0L;
remainder = 0L;
Divide64by64(dividend, divisor, "ient, &remainder);
cout << "Equals " << quotient << "R" << remainder << endl;
cout << endl;
if (quotient * divisor + remainder == dividend) {
cout << "Verified!" << endl;
} else {
cout << "Fail!" << endl;
if ((dividend < ((quotient + 1L) * divisor) &&
(dividend > (quotient * divisor)))) {
cout << "The quotient seems correct, but" << endl;
cout << "The remainder was wrong." << endl;
} else {
cout << "Not even the quotient is correct!" << endl;
}
}
// Divide64by32
divisor = 0x0123456701234567;
cout << dividend << endl;
cout << "Divided by " << divisor << endl;
cout << endl;
quotient = 0L;
remainder = 0L;
Divide64by64(dividend, divisor, "ient, &remainder);
cout << "Equals " << quotient << "R" << remainder << endl;
cout << endl;
if (quotient * divisor + remainder == dividend) {
cout << "Verified!" << endl;
} else {
cout << "Fail!" << endl;
if ((dividend < ((quotient + 1L) * divisor) &&
(dividend > (quotient * divisor)))) {
cout << "The quotient seems correct, but" << endl;
cout << "The remainder was wrong." << endl;
} else {
cout << "Not even the quotient is correct!" << endl;
}
}
cout << endl;
// Divide64by24
divisor = 0x0000000000123456;
cout << dividend << endl;
cout << "Divided by " << divisor << endl;
cout << endl;
quotient = 0L;
remainder = 0L;
Divide64by64(dividend, divisor, "ient, &remainder);
cout << "Equals " << quotient << "R" << remainder << endl;
cout << endl;
if (quotient * divisor + remainder == dividend) {
cout << "Verified!" << endl;
} else {
cout << "Fail!" << endl;
if ((dividend < ((quotient + 1L) * divisor) &&
(dividend > (quotient * divisor)))) {
cout << "The quotient seems correct, but" << endl;
cout << "The remainder was wrong." << endl;
} else {
cout << "Not even the quotient is correct!" << endl;
}
}
cout << endl;
// Divide64by16
divisor = 0x0000000000000FFF;
cout << dividend << endl;
cout << "Divided by " << divisor << endl;
cout << endl;
quotient = 0L;
remainder = 0L;
Divide64by64(dividend, divisor, "ient, &remainder);
cout << "Equals " << quotient << "R" << remainder << endl;
cout << endl;
if (quotient * divisor + remainder == dividend) {
cout << "Verified!" << endl;
} else {
cout << "Fail!" << endl;
if ((dividend < ((quotient + 1L) * divisor) &&
(dividend > (quotient * divisor)))) {
cout << "The quotient seems correct, but" << endl;
cout << "The remainder was wrong." << endl;
} else {
cout << "Not even the quotient is correct!" << endl;
}
}
cout << endl;
return 0;
}