On Sunday 04 January 2009 06:07:35 Alan Cox wrote: > > I note that sed and printf and such are all susv3. I have an explicit > > test for 32 bit math in the script that cares, and this worked in Red Hat > > 9 circa 2003. > > If you are trying to do arbitary precision maths using standard posix > tools just use dc. That way the standard is explicit about what you will > get. I looked at that, but: A) the Open Group Base Specifications (which I normally go by, since they're roughly synonymous with SUSv3 and Posix and available free on the web; they just released version 7 a week or so back) don't list dc as one of their utilities. (They mention bc, but not dc.) B) The busybox implementation of dc is crap. I got 'em to fix the bug where the output defaulted to binary instead of decimal, but the math is all done as floating point rather than arbitrary precision, and they don't implement the << operator. C) The only calculation which can overflow 64 bits (the ADJ32 one) turns out not to need arbitrary precision math, just 72 bits, and if it ever uses more than 32 then bottom 32 are all zero before the divide so you can do it in three lines. Essentially, the ADJ32 calculation is "(($NUMBER-1)<<$SHIFT)/$NUMBER". $SHIFT maxes out at 51 and the largest interesting $NUMBER is 1000000. (That's the pathological case of HZ=1, calculating the USEC_TO_HZ direction. A larger $HZ results in a smaller $SHIFT by the number of bits needed to store $HZ, by the way, so a $HZ of 17 would have a shift of 47. So even a HZ bigger than a million should have a small enough $SHIFT not to cause trouble here, although that's probably an _insane_ input to this script.) 1 million needs 20 bits to store, so the above calculation has to cope with an intermediate value of 999999<<51 which takes a little over 70 bits to store, hence the potential to overflow 63 bits of signed math. But this calculation has two special properties: 1) The number you start with before the shift is divided back out at the end (more or less), so the _result_ has to be less than 1<<$SHIFT and thus only takes $SHIFT bits to store. With a maximum $SHIFT of 51 it has to fit in a 64 bit result with about a dozen bits to spare. 2) The bottom $SHIFT many bits are all zero before the divide. We can use these two properties to easily break the math into chunks that can't overflow by: a) Chopping off the bottom X bits and dividing what's left by $NUMBER, keeping both the dividend and the remainder. Choose any X that's big enough that this step won't overflow. (I chose X=32, leaving at most 40-ish bits here). b) Shift that dividend X bits to the left. This can't overflow because of special property 1 above. c) Shift the remainder X bits to the left. The remainder can't be larger than the $NUMBER you started with, so if X+bits($NUMBER)<64 this has to fit too. With X=32 and bits=20 we again have a dozen bits to spare. d) Add the results of (b) and (c) together. Since the bottom X bits were all zero, this is equivalent to having done the full divide. (Easy enough to mask those bottom bits off and add them to the remainder before the divide if they weren't, but we didn't need to do that because we know they were zero.) So no arbitrary precision math is actually required here, and yes there's a comment in the source about this. :) Rob -- To unsubscribe from this list: send the line "unsubscribe linux-embedded" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
