Coverage Report

Created: 2024-11-21 07:03

/src/libgmp/mpn/sec_div_r.c
Line
Count
Source (jump to first uncovered line)
1
/* mpn_sec_div_qr, mpn_sec_div_r -- Compute Q = floor(U / V), U = U mod V.
2
   Side-channel silent under the assumption that the used instructions are
3
   side-channel silent.
4
5
   Contributed to the GNU project by Torbjörn Granlund.
6
7
Copyright 2011-2015 Free Software Foundation, Inc.
8
9
This file is part of the GNU MP Library.
10
11
The GNU MP Library is free software; you can redistribute it and/or modify
12
it under the terms of either:
13
14
  * the GNU Lesser General Public License as published by the Free
15
    Software Foundation; either version 3 of the License, or (at your
16
    option) any later version.
17
18
or
19
20
  * the GNU General Public License as published by the Free Software
21
    Foundation; either version 2 of the License, or (at your option) any
22
    later version.
23
24
or both in parallel, as here.
25
26
The GNU MP Library is distributed in the hope that it will be useful, but
27
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
28
or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
29
for more details.
30
31
You should have received copies of the GNU General Public License and the
32
GNU Lesser General Public License along with the GNU MP Library.  If not,
33
see https://www.gnu.org/licenses/.  */
34
35
#include "gmp-impl.h"
36
#include "longlong.h"
37
38
#if OPERATION_sec_div_qr
39
#define FNAME mpn_sec_div_qr
40
#define FNAME_itch mpn_sec_div_qr_itch
41
#define Q(q) q,
42
#define RETTYPE mp_limb_t
43
#endif
44
#if OPERATION_sec_div_r
45
#define FNAME mpn_sec_div_r
46
#define FNAME_itch mpn_sec_div_r_itch
47
#define Q(q)
48
#define RETTYPE void
49
#endif
50
51
mp_size_t
52
FNAME_itch (mp_size_t nn, mp_size_t dn)
53
0
{
54
#if OPERATION_sec_div_qr
55
/* Needs (nn + dn + 1) + mpn_sec_pi1_div_qr's needs of (2nn' - dn + 1) for a
56
   total of 3nn + 4 limbs at tp.  Note that mpn_sec_pi1_div_qr's nn is one
57
   greater than ours, therefore +4 and not just +2.  */
58
  return 3 * nn + 4;
59
#endif
60
0
#if OPERATION_sec_div_r
61
/* Needs (nn + dn + 1) + mpn_sec_pi1_div_r's needs of (dn + 1) for a total of
62
   nn + 2dn + 2 limbs at tp.  */
63
0
  return nn + 2 * dn + 2;
64
0
#endif
65
0
}
66
67
RETTYPE
68
FNAME (Q(mp_ptr qp)
69
       mp_ptr np, mp_size_t nn,
70
       mp_srcptr dp, mp_size_t dn,
71
       mp_ptr tp)
72
654
{
73
654
  mp_limb_t d1, d0;
74
654
  unsigned int cnt;
75
654
  mp_limb_t inv32;
76
77
654
  ASSERT (dn >= 1);
78
654
  ASSERT (nn >= dn);
79
654
  ASSERT (dp[dn - 1] != 0);
80
81
654
  d1 = dp[dn - 1];
82
654
  count_leading_zeros (cnt, d1);
83
84
654
  if (cnt != 0)
85
504
    {
86
504
      mp_limb_t cy;
87
504
      mp_ptr np2, dp2;
88
504
      dp2 = tp;         /* dn limbs */
89
504
      mpn_lshift (dp2, dp, dn, cnt);
90
91
504
      np2 = tp + dn;        /* (nn + 1) limbs */
92
504
      cy = mpn_lshift (np2, np, nn, cnt);
93
504
      np2[nn++] = cy;
94
95
504
      d0 = dp2[dn - 1];
96
504
      d0 += (~d0 != 0);
97
504
      invert_limb (inv32, d0);
98
99
      /* We add nn + dn to tp here, not nn + 1 + dn, as expected.  This is
100
   since nn here will have been incremented.  */
101
#if OPERATION_sec_div_qr
102
      mp_limb_t qh;
103
      qh = mpn_sec_pi1_div_qr (np2 + dn, np2, nn, dp2, dn, inv32, tp + nn + dn);
104
      ASSERT (qh == 0);   /* FIXME: this indicates inefficiency! */
105
      MPN_COPY (qp, np2 + dn, nn - dn - 1);
106
      qh = np2[nn - 1];
107
#else
108
504
      mpn_sec_pi1_div_r (np2, nn, dp2, dn, inv32, tp + nn + dn);
109
504
#endif
110
111
504
      mpn_rshift (np, np2, dn, cnt);
112
113
#if OPERATION_sec_div_qr
114
      return qh;
115
#endif
116
504
    }
117
150
  else
118
150
    {
119
      /* FIXME: Consider copying np => np2 here, adding a 0-limb at the top.
120
   That would simplify the underlying pi1 function, since then it could
121
   assume nn > dn.  */
122
150
      d0 = dp[dn - 1];
123
150
      d0 += (~d0 != 0);
124
150
      invert_limb (inv32, d0);
125
126
#if OPERATION_sec_div_qr
127
      return mpn_sec_pi1_div_qr (qp, np, nn, dp, dn, inv32, tp);
128
#else
129
150
      mpn_sec_pi1_div_r (np, nn, dp, dn, inv32, tp);
130
150
#endif
131
150
    }
132
654
}