Here's a version of my previous algorithm with the checks added
back in to improve overall performance. This one runs about as
fast as the divide-and-compare algorithm for my test cases. :-)
OK, I'm done tweaking now...
#define FULL_BITS (sizeof(size_t) * 8U)
#define TOP_BIT (((size_t)1) << ((FULL_BITS)-1))
#define HALF_BITS (sizeof(size_t) * 4U)
#define MID_BIT (((size_t)1) << ((HALF_BITS)-1))
#define LO_MASK ((((size_t)1) << (HALF_BITS))-1)
#define HI_MASK (~(LO_MASK))
#define SAFE_MULTIPLY(dest,src1,src2,on_overflow)\
{\
size_t _x = src1;\
size_t _y = src2;\
size_t _dest = _x * _y;\
\
dest = _dest;\
\
if ((_x | _y) & HI_MASK)\
{\
size_t h;\
int hlog;\
size_t l;\
int llog;\
size_t mask;\
\
if (_x >= _y)\
{\
h = _x;\
l = _y;\
}\
else\
{\
h = _y;\
l = _x;\
}\
\
if ((h & HI_MASK) && (l))\
{\
if (l & HI_MASK)\
{\
hlog = llog = FULL_BITS;\
}\
else\
{\
for ((mask=TOP_BIT),(hlog=FULL_BITS-1);!(mask&h);mask>>=1)\
{\
--hlog;\
}\
for ((mask=MID_BIT),(llog=HALF_BITS-1);!(mask&l);mask>>=1)\
{\
--llog;\
}\
}\
if ((hlog + llog > FULL_BITS - 1) ||\
((hlog + llog == FULL_BITS - 1) && !(_dest & TOP_BIT)))\
{\
on_overflow;\
}\
}\
}\
}
-Jerry
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4