Re: mpn_set_str_bits
Marco Bodrato writes:
> static mp_size_t
> mpn_set_str_bits (mp_ptr rp, const unsigned char *sp, size_t sn,
> unsigned bits)
> {
> mp_size_t rn;
> mp_limb_t limb;
> unsigned shift;
>
> for (limb = 0, rn = 0, shift = 0; sn-- > 0; )
> {
> limb |= (mp_limb_t) sp[sn] << shift;
> shift += bits;
> if (shift >= GMP_LIMB_BITS)
> {
> shift -= GMP_LIMB_BITS;
> rp[rn++] = limb;
> /* Next line is correct also if shift == 0,
> bits == 8, and mp_limb_t == unsigned char. */
> limb = (unsigned int) sp[sn] >> (bits - shift);
> }
> }
> if (limb != 0)
> rp[rn++] = limb;
> else
> rn = mpn_normalized_size (rp, rn);
> return rn;
> }
>
> It seems simple enough. Any further comment?
Looks nice!
Regards,
/Niels
--
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpn_set_str_bits
Ciao,
Il 2020-09-30 19:37 ni...@lysator.liu.se ha scritto:
Marco Bodrato writes:
limb = (unsigned int) sp[sn] >> (bits - shift);
That's easier to read than what I proposed.
Maybe worth a comment mentioning the problem case: mp_limb_t
Thanks Niels!
So, here is the current proposed rewrite:
static mp_size_t
mpn_set_str_bits (mp_ptr rp, const unsigned char *sp, size_t sn,
unsigned bits)
{
mp_size_t rn;
mp_limb_t limb;
unsigned shift;
for (limb = 0, rn = 0, shift = 0; sn-- > 0; )
{
limb |= (mp_limb_t) sp[sn] << shift;
shift += bits;
if (shift >= GMP_LIMB_BITS)
{
shift -= GMP_LIMB_BITS;
rp[rn++] = limb;
/* Next line is correct also if shift == 0,
bits == 8, and mp_limb_t == unsigned char. */
limb = (unsigned int) sp[sn] >> (bits - shift);
}
}
if (limb != 0)
rp[rn++] = limb;
else
rn = mpn_normalized_size (rp, rn);
return rn;
}
It seems simple enough. Any further comment?
Ĝis,
m
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpn_set_str_bits
Marco Bodrato writes: > limb = (unsigned int) sp[sn] >> (bits - shift); That's easier to read than what I proposed. > Maybe the cast is unnecessary, because the C standard says that the > left operand of a shift operation is always promoted to (unsigned) int > if it is smaller, correct? I think so, but it's a bit subtle, so I'd prefer the explicit cast. Maybe worth a comment mentioning the problem case: mp_limb_t == unsigned char, bits == 8, shift == 0 Regards, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677. Internet email is subject to wholesale government surveillance. ___ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpn_set_str_bits
Ciao! Il 2020-09-30 09:03 ni...@lysator.liu.se ha scritto: Marco Bodrato writes: limb = sp[sn]; if (GMP_LIMB_BITS > CHAR_BIT || shift > 0) limb >>= bits - shift; else limb = 0; Do we really need to support bits == GMP_LIMB_BITS here? If not, the About mpn_set_str, the manual reads "base can vary from 2 to 256". Moreover we are fool enough to (unofficially) support "typedef unsigned char mp_limb_t;" in mini-gmp... above 5 lines could be simplified to just limb = (sp[sn] >> 1) >> (bits - 1 - shift); it should be safe in all cases. I agree. Anyway, there may be a problem only if we shift sp[sn] (unsigned char) or limb (possibly the same type) by 8 bits (if bits=8 and shift=0). An even simpler solution could be to cast to unsigned int (at least 16 bits, right?) so: limb = (unsigned int) sp[sn] >> (bits - shift); Maybe the cast is unnecessary, because the C standard says that the left operand of a shift operation is always promoted to (unsigned) int if it is smaller, correct? But it shouldn't be dangerous. Ĝis, m ___ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpn_set_str_bits
Marco Bodrato writes:
> The loop in mpz_import uses another strategy, a temporary limb.
> This reduces the number of write operations into memory.
And it postpones writing the top limb. Another simplification I tried
failed because it sometimes wrote an extra zero limb.
> static mp_size_t
> mpn_set_str_bits (mp_ptr rp, const unsigned char *sp, size_t sn,
> unsigned bits)
> {
> mp_size_t rn;
> mp_limb_t limb;
> unsigned shift;
>
> for (limb = 0, rn = 0, shift = 0; sn-- > 0; )
> {
> limb |= (mp_limb_t) sp[sn] << shift;
> shift += bits;
> if (shift >= GMP_LIMB_BITS)
> {
> rp[rn++] = limb;
> shift -= GMP_LIMB_BITS;
> limb = sp[sn];
> if (GMP_LIMB_BITS > CHAR_BIT || shift > 0)
> limb >>= bits - shift;
> else
> limb = 0;
Do we really need to support bits == GMP_LIMB_BITS here? If not, the
above 5 lines could be simplified to just
limb = sp[sn] >> (bits - shift);
Hmm, at this point, we always have shift < bits, right? So if we write
it as
limb = (sp[sn] >> 1) >> (bits - 1 - shift);
it should be safe in all cases.
Regards,
/Niels
--
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
Re: mpn_set_str_bits
Ciao,
Il 2020-09-29 12:15 Raphael Rieu-Helft ha scritto:
The attached patch slightly improves the mini-gmp function
mpn_set_str_bits. The invariants are also a bit clearer (shift is the
The loop in mpz_import uses another strategy, a temporary limb.
This reduces the number of write operations into memory.
May I propose an alternative rewrite?
What do you think about it?
static mp_size_t
mpn_set_str_bits (mp_ptr rp, const unsigned char *sp, size_t sn,
unsigned bits)
{
mp_size_t rn;
mp_limb_t limb;
unsigned shift;
for (limb = 0, rn = 0, shift = 0; sn-- > 0; )
{
limb |= (mp_limb_t) sp[sn] << shift;
shift += bits;
if (shift >= GMP_LIMB_BITS)
{
rp[rn++] = limb;
shift -= GMP_LIMB_BITS;
limb = sp[sn];
if (GMP_LIMB_BITS > CHAR_BIT || shift > 0)
limb >>= bits - shift;
else
limb = 0;
}
}
if (limb != 0)
rp[rn++] = limb;
else
rn = mpn_normalized_size (rp, rn);
return rn;
}
Ĝis,
m
___
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
