Coverage Report

Created: 2024-06-28 06:39

/src/gmp-6.2.1/mpz/cong.c
Line
Count
Source (jump to first uncovered line)
1
/* mpz_congruent_p -- test congruence of two mpz's.
2
3
Copyright 2001, 2002, 2005 Free Software Foundation, Inc.
4
5
This file is part of the GNU MP Library.
6
7
The GNU MP Library is free software; you can redistribute it and/or modify
8
it under the terms of either:
9
10
  * the GNU Lesser General Public License as published by the Free
11
    Software Foundation; either version 3 of the License, or (at your
12
    option) any later version.
13
14
or
15
16
  * the GNU General Public License as published by the Free Software
17
    Foundation; either version 2 of the License, or (at your option) any
18
    later version.
19
20
or both in parallel, as here.
21
22
The GNU MP Library is distributed in the hope that it will be useful, but
23
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
24
or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
25
for more details.
26
27
You should have received copies of the GNU General Public License and the
28
GNU Lesser General Public License along with the GNU MP Library.  If not,
29
see https://www.gnu.org/licenses/.  */
30
31
#include "gmp-impl.h"
32
#include "longlong.h"
33
34
35
/* For big divisors this code is only very slightly better than the user
36
   doing a combination of mpz_sub and mpz_tdiv_r, but it's quite convenient,
37
   and perhaps in the future can be improved, in similar ways to
38
   mpn_divisible_p perhaps.
39
40
   The csize==1 / dsize==1 special case makes mpz_congruent_p as good as
41
   mpz_congruent_ui_p on relevant operands, though such a combination
42
   probably doesn't occur often.
43
44
   Alternatives:
45
46
   If c<d then it'd work to just form a%d and compare a and c (either as
47
   a==c or a+c==d depending on the signs), but the saving from avoiding the
48
   abs(a-c) calculation would be small compared to the division.
49
50
   Similarly if both a<d and c<d then it would work to just compare a and c
51
   (a==c or a+c==d), but this isn't considered a particularly important case
52
   and so isn't done for the moment.
53
54
   Low zero limbs on d could be stripped and the corresponding limbs of a
55
   and c tested and skipped, but doing so would introduce a borrow when a
56
   and c differ in sign and have non-zero skipped limbs.  It doesn't seem
57
   worth the complications to do this, since low zero limbs on d should
58
   occur only rarely.  */
59
60
int
61
mpz_congruent_p (mpz_srcptr a, mpz_srcptr c, mpz_srcptr d)
62
964
{
63
964
  mp_size_t  asize, csize, dsize, sign;
64
964
  mp_srcptr  ap, cp, dp;
65
964
  mp_ptr     xp;
66
964
  mp_limb_t  alow, clow, dlow, dmask, r;
67
964
  int        result;
68
964
  TMP_DECL;
69
70
964
  dsize = SIZ(d);
71
964
  if (UNLIKELY (dsize == 0))
72
0
    return (mpz_cmp (a, c) == 0);
73
74
964
  dsize = ABS(dsize);
75
964
  dp = PTR(d);
76
77
964
  if (ABSIZ(a) < ABSIZ(c))
78
806
    MPZ_SRCPTR_SWAP (a, c);
79
80
964
  asize = SIZ(a);
81
964
  csize = SIZ(c);
82
964
  sign = (asize ^ csize);
83
84
964
  asize = ABS(asize);
85
964
  ap = PTR(a);
86
87
964
  if (csize == 0)
88
70
    return mpn_divisible_p (ap, asize, dp, dsize);
89
90
894
  csize = ABS(csize);
91
894
  cp = PTR(c);
92
93
894
  alow = ap[0];
94
894
  clow = cp[0];
95
894
  dlow = dp[0];
96
97
  /* Check a==c mod low zero bits of dlow.  This might catch a few cases of
98
     a!=c quickly, and it helps the csize==1 special cases below.  */
99
894
  dmask = LOW_ZEROS_MASK (dlow) & GMP_NUMB_MASK;
100
894
  alow = (sign >= 0 ? alow : -alow);
101
894
  if (((alow-clow) & dmask) != 0)
102
0
    return 0;
103
104
894
  if (csize == 1)
105
84
    {
106
84
      if (dsize == 1)
107
0
  {
108
0
  cong_1:
109
0
    if (sign < 0)
110
0
      NEG_MOD (clow, clow, dlow);
111
112
0
    if (ABOVE_THRESHOLD (asize, BMOD_1_TO_MOD_1_THRESHOLD))
113
0
      {
114
0
        r = mpn_mod_1 (ap, asize, dlow);
115
0
        if (clow < dlow)
116
0
    return r == clow;
117
0
        else
118
0
    return r == (clow % dlow);
119
0
      }
120
121
0
    if ((dlow & 1) == 0)
122
0
      {
123
        /* Strip low zero bits to get odd d required by modexact.  If
124
     d==e*2^n then a==c mod d if and only if both a==c mod e and
125
     a==c mod 2^n, the latter having been done above.  */
126
0
        unsigned  twos;
127
0
        count_trailing_zeros (twos, dlow);
128
0
        dlow >>= twos;
129
0
      }
130
131
0
    r = mpn_modexact_1c_odd (ap, asize, dlow, clow);
132
0
    return r == 0 || r == dlow;
133
0
  }
134
135
      /* dlow==0 is avoided since we don't want to bother handling extra low
136
   zero bits if dsecond is even (would involve borrow if a,c differ in
137
   sign and alow,clow!=0).  */
138
84
      if (dsize == 2 && dlow != 0)
139
0
  {
140
0
    mp_limb_t  dsecond = dp[1];
141
142
0
    if (dsecond <= dmask)
143
0
      {
144
0
        unsigned   twos;
145
0
        count_trailing_zeros (twos, dlow);
146
0
        dlow = (dlow >> twos) | (dsecond << (GMP_NUMB_BITS-twos));
147
0
        ASSERT_LIMB (dlow);
148
149
        /* dlow will be odd here, so the test for it even under cong_1
150
     is unnecessary, but the rest of that code is wanted. */
151
0
        goto cong_1;
152
0
      }
153
0
  }
154
84
    }
155
156
894
  TMP_MARK;
157
894
  xp = TMP_ALLOC_LIMBS (asize+1);
158
159
  /* calculate abs(a-c) */
160
894
  if (sign >= 0)
161
894
    {
162
      /* same signs, subtract */
163
894
      if (asize > csize || mpn_cmp (ap, cp, asize) >= 0)
164
868
  ASSERT_NOCARRY (mpn_sub (xp, ap, asize, cp, csize));
165
26
      else
166
26
  ASSERT_NOCARRY (mpn_sub_n (xp, cp, ap, asize));
167
894
      MPN_NORMALIZE (xp, asize);
168
894
    }
169
0
  else
170
0
    {
171
      /* different signs, add */
172
0
      mp_limb_t  carry;
173
0
      carry = mpn_add (xp, ap, asize, cp, csize);
174
0
      xp[asize] = carry;
175
0
      asize += (carry != 0);
176
0
    }
177
178
894
  result = mpn_divisible_p (xp, asize, dp, dsize);
179
180
894
  TMP_FREE;
181
894
  return result;
182
894
}