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-2014 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.h" 36 #include "gmp-impl.h" 37 #include "longlong.h" 38 39 #if OPERATION_sec_div_qr 40 #define FNAME mpn_sec_div_qr 41 #define FNAME_itch mpn_sec_div_qr_itch 42 #define Q(q) q, 43 #define RETTYPE mp_limb_t 44 #endif 45 #if OPERATION_sec_div_r 46 #define FNAME mpn_sec_div_r 47 #define FNAME_itch mpn_sec_div_r_itch 48 #define Q(q) 49 #define RETTYPE void 50 #endif 51 52 mp_size_t 53 FNAME_itch (mp_size_t nn, mp_size_t dn) 54 { 55 #if OPERATION_sec_div_qr 56 /* Needs (nn + dn + 1) + mpn_sec_pi1_div_qr's needs of (2nn' - dn + 1) for a 57 total of 3nn + 4 limbs at tp. Note that mpn_sec_pi1_div_qr's nn is one 58 greater than ours, therefore +4 and not just +2. */ 59 return 3 * nn + 4; 60 #endif 61 #if OPERATION_sec_div_r 62 /* Needs (nn + dn + 1) + mpn_sec_pi1_div_r's needs of (dn + 1) for a total of 63 nn + 2dn + 2 limbs at tp. */ 64 return nn + 2 * dn + 2; 65 #endif 66 } 67 68 RETTYPE 69 FNAME (Q(mp_ptr qp) 70 mp_ptr np, mp_size_t nn, 71 mp_srcptr dp, mp_size_t dn, 72 mp_ptr tp) 73 { 74 mp_limb_t d1, d0; 75 unsigned int cnt; 76 gmp_pi1_t dinv; 77 mp_limb_t inv32; 78 79 ASSERT (dn >= 1); 80 ASSERT (nn >= dn); 81 ASSERT (dp[dn - 1] != 0); 82 83 d1 = dp[dn - 1]; 84 count_leading_zeros (cnt, d1); 85 86 if (cnt != 0) 87 { 88 mp_limb_t qh, cy; 89 mp_ptr np2, dp2; 90 dp2 = tp; /* dn limbs */ 91 mpn_lshift (dp2, dp, dn, cnt); 92 93 np2 = tp + dn; /* (nn + 1) limbs */ 94 cy = mpn_lshift (np2, np, nn, cnt); 95 np2[nn++] = cy; 96 97 d0 = dp2[dn - 1]; 98 d0 += (~d0 != 0); 99 invert_limb (inv32, d0); 100 101 /* We add nn + dn to tp here, not nn + 1 + dn, as expected. This is 102 since nn here will have been incremented. */ 103 #if OPERATION_sec_div_qr 104 qh = mpn_sec_pi1_div_qr (np2 + dn, np2, nn, dp2, dn, inv32, tp + nn + dn); 105 ASSERT (qh == 0); /* FIXME: this indicates inefficiency! */ 106 MPN_COPY (qp, np2 + dn, nn - dn - 1); 107 qh = np2[nn - 1]; 108 #else 109 mpn_sec_pi1_div_r (np2, nn, dp2, dn, inv32, tp + nn + dn); 110 #endif 111 112 mpn_rshift (np, np2, dn, cnt); 113 114 #if OPERATION_sec_div_qr 115 return qh; 116 #endif 117 } 118 else 119 { 120 /* FIXME: Consider copying np => np2 here, adding a 0-limb at the top. 121 That would simplify the underlying pi1 function, since then it could 122 assume nn > dn. */ 123 d0 = dp[dn - 1]; 124 d0 += (~d0 != 0); 125 invert_limb (inv32, d0); 126 127 #if OPERATION_sec_div_qr 128 return mpn_sec_pi1_div_qr (qp, np, nn, dp, dn, inv32, tp); 129 #else 130 mpn_sec_pi1_div_r (np, nn, dp, dn, inv32, tp); 131 #endif 132 } 133 } 134