Re: PATCH [0/3]: Simplify the kernel build by removing perl.

Rob Landley
2009-01-04T06:29:19Z

On Saturday 03 January 2009 20:14:44 H. Peter Anvin wrote:
> Rob Landley wrote:
> >> The new patches have *more* environmental
> >> dependencies than that ever did.
> >
> > Could you please be a little more specific?
>
> In this case, you're assuming that every version of every shell this is
> going to get involved with is going to do math correctly with the
> requisite precision, which is nowhere guaranteed, I'm pretty sure.

Well, SUSv3 requires that the shell support signed long arithmetic:
http://www.opengroup.org/onlinepubs/9699919799/utilities/V3_chap02.html#tag_18_06_04

And the LP64 standard says that on 64 bit systems, long must be 64 bit:
http://www.unix.org/whitepapers/64bit.html

Now the potential weakness there is that on 32 bit systems, shells might only
support 32 bit math instead of 64 bit math. (You'll notice I have a test for
that.) However, bash has supported 64 bit math on 32 bit systems since at
least 2003. (I keep a Red Hat 9 test image around because it had 50% market
share when it shipped, so the majority of "old" Linux systems still in use
_are_ RH9 or similar. It also has the oldest gcc version the kernel still
claims to build under.) Busybox ash can also support 64 bit math on 32 bit
hosts, and I just confirmed that the dash in the 32 bit xubuntu 8.10 supports
64 bit math as well.

(It would also be possible to do a similar overflow avoiding trick to do the
lot entirely in 32 bit math, but given that the three main shells in use on
Linux _do_ support 64 bit math on 32 bit hosts and are _required_ to support
it on 64 bit hosts according to SUSv3, the extra complexity really doesn't
seem worth it.)

> >> Third, if someone actually cares to do it right, I have a smallish
> >> bignum library at http://git.zytor.com/?p=lib/pbn.git;a=summary that
> >> might be a starting point.
> >
> > This doesn't _need_ bignum support. It maxes out around 72 bits and the
> > _result_ can't use more than about $SHIFT bits because you're dividing by
> > the amount you shifted, so just chop off the bottom 32 bits, do a normal
> > 64 bit division on the top (it has to fit), and then do the same division
> > on the appropriate shifted remainder, and combine the results. This is
> > easy because when the shift _is_ 32 bits or more, the bottom 32 bits all
> > have to be zeroes so you don't even have to mask and add, just shift the
> > remainder left 32 bits so you can continue the divide.
> >
> > Pulling out perl isn't always a good alternative to thinking about the
> > problem.
>
> Neither is open-coding a bignum operation instead of relying on an
> existing, validated implementation.

Implementing something by hand isn't _always_ a good alternative, sure. That
would be the "thinking about the problem" part. In this instance, avoiding
overflow is trivial. (If 1<<-1 didn't wrap around, it wouldn't even need the
if statement.)

I'm curious, would the "existing, validated implementation" in this instance
be the perl implementation, or the library you wrote and pointed me to above
as a potential replacement for it?

I suppose there's a certain amount of style in accusing me of reinventing the
wheel while pointing me at your reinvention of the wheel. (Are you aiming to
replace Gnu's gmplib.org, the perhaps the BSD licensed one in openssh?
Dropbear uses Libtommath. A quick google for C open source big number
libraries also found Libimath, MPI, NTL, BigDigits, decNumber, and MPI. The
last time I personally wrote my own arbitrary precision math package from
scratch was in 1998, and that was in Java, so I'm a little rusty...) But I
don't personally consider avoiding the need for an arbitrary precision math
library to be the same as reimplementing one.

> -hpa

Rob