[coyotos-dev] BigNum issues
Jonathan S. Shapiro
shap at eros-os.com
Wed Nov 7 12:04:35 EST 2007
Thomas:
I have applied *some* of your repairs. It wasn't clear why you dropped
the "static" qualifiers on the const stuff, for example.
Concerning the shift operations, the only requirement I can think of is
that the shift amount not be negative.
I'm testing something else for this update, but this one is pushed into
the tree already. RPMS should release shortly.
On Mon, 2007-10-08 at 01:15 +0200, Thomas Stratmann wrote:
> There's a number of problems in the shifting functions.
>
> vu_rshift_digits has an off-by-some problem (see attached index.patch).
>
> vu_rshift_bits is broken. First it shifts n1 by nShift / 32 digits,
> result in n2, then puts n1 bitshifted by nShift %= 32 into n2.
> Similarly in vu_lshift_bits.
>
> ALL bit and digit shifting functions are lacking requirements, which is
> why I'm answering this thread... and the reason why I didn't bother
> fixing for now.
>
> vu_lshift_digits is not zeroing n2's leading digits in case n1 is too
> short (this may be just a missing requirement).
>
> /--/
>
> Additionally, have a look at BigNum::lshift_digits(size_t n):
> It depends on alloca zeroing the allocated memory (which I suspect it
> does, but failed to investigate). If this is the case, the rmemset calls
> in vu_mul (and I think I spotted this somewhere else...) are superfluous.
>
> /--/
>
> Finally, constructing an nvec from a BigNum should result in a constant
> since it borrows the BigNum's innerds. Also the global nvec 0's and 1's
> representation should be constant. See attached noclobber.patch.
>
> Thomas
> plain text document attachment (index.patch)
> # HG changeset patch
> # User Thomas Stratmann <thomas.stratmann at rub.de>
> # Date 1191796566 -7200
> # Node ID 43b209acb647d9db7e585636f65386e3016473c7
> # Parent 91b3be5fcd4f4784d40c964bc6e5587c33c36f74
> Fixed array-index bug in vu_rshift_digits.
>
> Fixed a typo in a comment as well.
>
> diff -r 91b3be5fcd4f -r 43b209acb647 coytools/src/libsherpa/BigNum.cxx
> --- a/coytools/src/libsherpa/BigNum.cxx Sun Sep 30 20:13:04 2007 -0400
> +++ b/coytools/src/libsherpa/BigNum.cxx Mon Oct 08 00:36:06 2007 +0200
> @@ -144,14 +144,14 @@ namespace sherpa {
> }
>
> for (size_t i = 0; i < min(n1.len - nShift, n2.len); i++)
> - n2.vec[i] = n1.vec[i];
> - for (size_t i = n1.len - nShift; i <n2.len; i++)
> + n2.vec[i] = n1.vec[i + nShift];
> + for (size_t i = n1.len - nShift; i < n2.len; i++)
> n2.vec[i] = 0;
>
> return;
> }
>
> - /// @brief n2 = n1 / (radix^nShift)
> + /// @brief n2 = n1 * (radix^nShift)
> static void
> vu_lshift_digits(const nvec n1, size_t nShift, nvec n2)
> {
> plain text document attachment (noclobber.patch)
> # HG changeset patch
> # User Thomas Stratmann <thomas.stratmann at rub.de>
> # Date 1191669953 -7200
> # Node ID 6d38028783c8386636b3fbce8512ba76794e938d
> # Parent 91b3be5fcd4f4784d40c964bc6e5587c33c36f74
> Constructing nvec from BigNum must give constant
>
> diff -r 91b3be5fcd4f -r 6d38028783c8 coytools/src/libsherpa/BigNum.cxx
> --- a/coytools/src/libsherpa/BigNum.cxx Sun Sep 30 20:13:04 2007 -0400
> +++ b/coytools/src/libsherpa/BigNum.cxx Sat Oct 06 13:25:53 2007 +0200
> @@ -85,6 +85,7 @@ namespace sherpa {
> vec = 0;
> }
>
> +// This aliases parameter's innerds
> inline nvec(const sherpa::BigNum& bn)
> {
> if (bn.nDigits == 1) {
> @@ -626,8 +627,8 @@ namespace sherpa {
> int BigNum::cmp(const BigNum& other) const
> {
> if (negative == other.negative) {
> - nvec n1(*this);
> - nvec n2(other);
> + const nvec n1(*this);
> + const nvec n2(other);
> int result= vu_cmp(n1, n2);
> return negative ? -result : result;
> }
> @@ -664,7 +665,7 @@ namespace sherpa {
> nv.len = nDigits + ((n+31)/32); // upper bound
> nv.vec = (uint32_t *) alloca(nv.len * sizeof(uint32_t));
>
> - nvec me(*this);
> + const nvec me(*this);
> vu_lshift_bits(me, n, nv);
>
> return BigNum(nv.len, nv.vec, negative);
> @@ -676,7 +677,7 @@ namespace sherpa {
> nv.len = nDigits - (n/32); // upper bound
> nv.vec = (uint32_t *) alloca(nv.len * sizeof(uint32_t));
>
> - nvec me(*this);
> + const nvec me(*this);
> vu_rshift_bits(me, n, nv);
>
> return BigNum(nv.len, nv.vec, negative);
> # HG changeset patch
> # User Thomas Stratmann <thomas.stratmann at rub.de>
> # Date 1191794154 -7200
> # Node ID 223bab93baa4b3283113c7d7e730873b9fe8a334
> # Parent 91b3be5fcd4f4784d40c964bc6e5587c33c36f74
> Make global nvecs representing zero and one constant.
>
> Static should only be used in classes and functions.
>
> diff -r 91b3be5fcd4f -r 223bab93baa4 coytools/src/libsherpa/BigNum.cxx
> --- a/coytools/src/libsherpa/BigNum.cxx Sun Sep 30 20:13:04 2007 -0400
> +++ b/coytools/src/libsherpa/BigNum.cxx Sun Oct 07 23:55:54 2007 +0200
> @@ -108,10 +108,10 @@ namespace sherpa {
> }
> } ;
>
> - static uint32_t u_zero = 0;
> - static nvec nv_zero(1, &u_zero);
> - static uint32_t u_one = 1;
> - static nvec nv_one(1, &u_one);
> + uint32_t u_zero = 0;
> + const nvec nv_zero(1, &u_zero);
> + uint32_t u_one = 1;
> + const nvec nv_one(1, &u_one);
>
> /// @brief compare two digit vectors for relative magnitude. Return
> /// -1, 0, 1 according to whether v1 is less than, equal to, or
> _______________________________________________
> coyotos-dev mailing list
> coyotos-dev at smtp.coyotos.org
> http://www.coyotos.org/mailman/listinfo/coyotos-dev
--
Jonathan S. Shapiro, Ph.D.
Managing Director
The EROS Group, LLC
www.coyotos.org, www.eros-os.org
More information about the coyotos-dev
mailing list