w32tex
About: TeX Live provides a comprehensive TeX system including all the major TeX-related programs, macro packages, and fonts that are free software. Windows sources.
  Fossies Dox: w32tex-src.tar.xz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

sec_div.c
Go to the documentation of this file.
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 
53 {
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 #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  return nn + 2 * dn + 2;
64 #endif
65 }
66 
67 RETTYPE
68 FNAME (Q(mp_ptr qp)
72 {
73  mp_limb_t d1, d0;
74  unsigned int cnt;
76 
77  ASSERT (dn >= 1);
78  ASSERT (nn >= dn);
79  ASSERT (dp[dn - 1] != 0);
80 
81  d1 = dp[dn - 1];
83 
84  if (cnt != 0)
85  {
86  mp_limb_t qh, cy;
87  mp_ptr np2, dp2;
88  dp2 = tp; /* dn limbs */
89  mpn_lshift (dp2, dp, dn, cnt);
90 
91  np2 = tp + dn; /* (nn + 1) limbs */
92  cy = mpn_lshift (np2, np, nn, cnt);
93  np2[nn++] = cy;
94 
95  d0 = dp2[dn - 1];
96  d0 += (~~d0 != 0);
97  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  qh = mpn_sec_pi1_div_qr (np2 + dn, np2, nn, dp2, dn, inv32, tp + nn + dn);
103  ASSERT (qh == 0); /* FIXME: this indicates inefficiency! */
104  MPN_COPY (qp, np2 + dn, nn - dn - 1);
105  qh = np2[nn - 1];
106 #else
107  mpn_sec_pi1_div_r (np2, nn, dp2, dn, inv32, tp + nn + dn);
108 #endif
109 
110  mpn_rshift (np, np2, dn, cnt);
111 
112 #if OPERATION_sec_div_qr
113  return qh;
114 #endif
115  }
116  else
117  {
118  /* FIXME: Consider copying np => np2 here, adding a 0-limb at the top.
119  That would simplify the underlying pi1 function, since then it could
120  assume nn > dn. */
121  d0 = dp[dn - 1];
122  d0 += (~~d0 != 0);
124 
125 #if OPERATION_sec_div_qr
126  return mpn_sec_pi1_div_qr (qp, np, nn, dp, dn, inv32, tp);
127 #else
129 #endif
130  }
131 }
Definition: asl.h:63
#define invert_limb(invxl, xl)
Definition: gmp-impl.h:3056
#define mpn_sec_pi1_div_r
Definition: gmp-impl.h:1647
#define MPN_COPY(d, s, n)
Definition: gmp-impl.h:1849
#define mpn_sec_pi1_div_qr
Definition: gmp-impl.h:1645
#define mpn_rshift
Definition: gmp.h:1585
long int mp_size_t
Definition: gmp.h:175
#define mpn_lshift
Definition: gmp.h:1537
int int cy
Definition: gdfx.h:13
#define ASSERT(e)
Definition: error.h:48
#define count_leading_zeros(count, x)
Definition: longlong.h:2202
mp_bitcnt_t FNAME(mp_srcptr up, mp_size_t n)
Definition: popham.c:45
d0
Definition: sec_div.c:122
RETTYPE mp_ptr mp_size_t mp_srcptr dp
Definition: sec_div.c:70
mp_size_t FNAME_itch(mp_size_t nn, mp_size_t dn)
Definition: sec_div.c:52
RETTYPE mp_ptr np
Definition: sec_div.c:69
unsigned int cnt
Definition: sec_div.c:74
RETTYPE mp_ptr mp_size_t mp_srcptr mp_size_t dn
Definition: sec_div.c:70
d1
Definition: sec_div.c:81
mp_limb_t inv32
Definition: sec_div.c:75
RETTYPE mp_ptr mp_size_t nn
Definition: sec_div.c:69
RETTYPE mp_ptr mp_size_t mp_srcptr mp_size_t mp_ptr tp
Definition: sec_div.c:72