[Python-Dev] Memory size overflows

2002年10月17日 12:06:28 -0400

Armin Rigo wrote:
> We might be running into code bloats thought. If we go for such big
> macros, I believe we should design them so that they run fast in the
> common case and call a helper function otherwise. 

Easily done, but first you have to ask yourself if it's
really ever more efficient than this:
#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)\
 {\
 if ((_dest / _x) != _y)\
 {\
 on_overflow;\
 }\
 }\
 }
If so, here's a macro/helper version:
#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)\
 {\
 if (_safe_multiply_check_for_overflow(_x,_y,_dest))\
 {\
 on_overflow;\
 }\
 }\
 }
int
_safe_multiply_check_for_overflow(
 size_t x,
 size_t y,
 size_t dest)
{
 size_t h;
 size_t l;
 if (x >= y)
 {
 h = x;
 l = y;
 }
 else
 {
 h = y;
 l = x;
 }
 if ((h & HI_MASK) && (l))
 {
 int hlog;
 int llog;
 if (l & HI_MASK)
 {
 hlog = llog = FULL_BITS;
 }
 else
 {
 size_t mask;
 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)))
 {
 return 1;
 }
 }
 return 0;
}
Of course there are also the alternatives of using floating point
numbers (assuming the mantissa has as many bits as size_t), or a
double-width intermediate representation, if available.
There are also some other tricks that can be used to optimize this
solution. The time-consuming part is finding out if the sum of the
log2's of the multiplicands (i.e., highest bit positions) is less
than, greater than, or equal to <bits in size_t> - 1. But I said I
was done tweaking for now. :-)
-Jerry