|
Packit |
5c3484 |
/* mpn_mod_34lsub1 -- remainder modulo 2^(GMP_NUMB_BITS*3/4)-1.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
THE FUNCTIONS IN THIS FILE ARE FOR INTERNAL USE ONLY. THEY'RE ALMOST
|
|
Packit |
5c3484 |
CERTAIN TO BE SUBJECT TO INCOMPATIBLE CHANGES OR DISAPPEAR COMPLETELY IN
|
|
Packit |
5c3484 |
FUTURE GNU MP RELEASES.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
Copyright 2000-2002 Free Software Foundation, Inc.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
This file is part of the GNU MP Library.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
The GNU MP Library is free software; you can redistribute it and/or modify
|
|
Packit |
5c3484 |
it under the terms of either:
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
* the GNU Lesser General Public License as published by the Free
|
|
Packit |
5c3484 |
Software Foundation; either version 3 of the License, or (at your
|
|
Packit |
5c3484 |
option) any later version.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
or
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
* the GNU General Public License as published by the Free Software
|
|
Packit |
5c3484 |
Foundation; either version 2 of the License, or (at your option) any
|
|
Packit |
5c3484 |
later version.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
or both in parallel, as here.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
The GNU MP Library is distributed in the hope that it will be useful, but
|
|
Packit |
5c3484 |
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
|
|
Packit |
5c3484 |
or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
Packit |
5c3484 |
for more details.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
You should have received copies of the GNU General Public License and the
|
|
Packit |
5c3484 |
GNU Lesser General Public License along with the GNU MP Library. If not,
|
|
Packit |
5c3484 |
see https://www.gnu.org/licenses/. */
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#include "gmp.h"
|
|
Packit |
5c3484 |
#include "gmp-impl.h"
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* Calculate a remainder from {p,n} divided by 2^(GMP_NUMB_BITS*3/4)-1.
|
|
Packit |
5c3484 |
The remainder is not fully reduced, it's any limb value congruent to
|
|
Packit |
5c3484 |
{p,n} modulo that divisor.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
This implementation is only correct when GMP_NUMB_BITS is a multiple of
|
|
Packit |
5c3484 |
4.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
FIXME: If GMP_NAIL_BITS is some silly big value during development then
|
|
Packit |
5c3484 |
it's possible the carry accumulators c0,c1,c2 could overflow.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
General notes:
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
The basic idea is to use a set of N accumulators (N=3 in this case) to
|
|
Packit |
5c3484 |
effectively get a remainder mod 2^(GMP_NUMB_BITS*N)-1 followed at the end
|
|
Packit |
5c3484 |
by a reduction to GMP_NUMB_BITS*N/M bits (M=4 in this case) for a
|
|
Packit |
5c3484 |
remainder mod 2^(GMP_NUMB_BITS*N/M)-1. N and M are chosen to give a good
|
|
Packit |
5c3484 |
set of small prime factors in 2^(GMP_NUMB_BITS*N/M)-1.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
N=3 M=4 suits GMP_NUMB_BITS==32 and GMP_NUMB_BITS==64 quite well, giving
|
|
Packit |
5c3484 |
a few more primes than a single accumulator N=1 does, and for no extra
|
|
Packit |
5c3484 |
cost (assuming the processor has a decent number of registers).
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
For strange nailified values of GMP_NUMB_BITS the idea would be to look
|
|
Packit |
5c3484 |
for what N and M give good primes. With GMP_NUMB_BITS not a power of 2
|
|
Packit |
5c3484 |
the choices for M may be opened up a bit. But such things are probably
|
|
Packit |
5c3484 |
best done in separate code, not grafted on here. */
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#if GMP_NUMB_BITS % 4 == 0
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#define B1 (GMP_NUMB_BITS / 4)
|
|
Packit |
5c3484 |
#define B2 (B1 * 2)
|
|
Packit |
5c3484 |
#define B3 (B1 * 3)
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#define M1 ((CNST_LIMB(1) << B1) - 1)
|
|
Packit |
5c3484 |
#define M2 ((CNST_LIMB(1) << B2) - 1)
|
|
Packit |
5c3484 |
#define M3 ((CNST_LIMB(1) << B3) - 1)
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#define LOW0(n) ((n) & M3)
|
|
Packit |
5c3484 |
#define HIGH0(n) ((n) >> B3)
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#define LOW1(n) (((n) & M2) << B1)
|
|
Packit |
5c3484 |
#define HIGH1(n) ((n) >> B2)
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#define LOW2(n) (((n) & M1) << B2)
|
|
Packit |
5c3484 |
#define HIGH2(n) ((n) >> B1)
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#define PARTS0(n) (LOW0(n) + HIGH0(n))
|
|
Packit |
5c3484 |
#define PARTS1(n) (LOW1(n) + HIGH1(n))
|
|
Packit |
5c3484 |
#define PARTS2(n) (LOW2(n) + HIGH2(n))
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#define ADD(c,a,val) \
|
|
Packit |
5c3484 |
do { \
|
|
Packit |
5c3484 |
mp_limb_t new_c; \
|
|
Packit |
5c3484 |
ADDC_LIMB (new_c, a, a, val); \
|
|
Packit |
5c3484 |
(c) += new_c; \
|
|
Packit |
5c3484 |
} while (0)
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
mp_limb_t
|
|
Packit |
5c3484 |
mpn_mod_34lsub1 (mp_srcptr p, mp_size_t n)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mp_limb_t c0 = 0;
|
|
Packit |
5c3484 |
mp_limb_t c1 = 0;
|
|
Packit |
5c3484 |
mp_limb_t c2 = 0;
|
|
Packit |
5c3484 |
mp_limb_t a0, a1, a2;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
ASSERT (n >= 1);
|
|
Packit |
5c3484 |
ASSERT (n/3 < GMP_NUMB_MAX);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
a0 = a1 = a2 = 0;
|
|
Packit |
5c3484 |
c0 = c1 = c2 = 0;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
while ((n -= 3) >= 0)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
ADD (c0, a0, p[0]);
|
|
Packit |
5c3484 |
ADD (c1, a1, p[1]);
|
|
Packit |
5c3484 |
ADD (c2, a2, p[2]);
|
|
Packit |
5c3484 |
p += 3;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
if (n != -3)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
ADD (c0, a0, p[0]);
|
|
Packit |
5c3484 |
if (n != -2)
|
|
Packit |
5c3484 |
ADD (c1, a1, p[1]);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
return
|
|
Packit |
5c3484 |
PARTS0 (a0) + PARTS1 (a1) + PARTS2 (a2)
|
|
Packit |
5c3484 |
+ PARTS1 (c0) + PARTS2 (c1) + PARTS0 (c2);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#endif
|