1 /* mpi-div.c - MPI functions 2 * Copyright (C) 1994, 1996, 1998, 2001, 2002, 3 * 2003 Free Software Foundation, Inc. 4 * 5 * This file is part of Libgcrypt. 6 * 7 * Note: This code is heavily based on the GNU MP Library. 8 * Actually it's the same code with only minor changes in the 9 * way the data is stored; this is to support the abstraction 10 * of an optional secure memory allocation which may be used 11 * to avoid revealing of sensitive data due to paging etc. 12 */ 13 14 #include "mpi-internal.h" 15 #include "longlong.h" 16 17 void mpi_tdiv_qr(MPI quot, MPI rem, MPI num, MPI den); 18 void mpi_fdiv_qr(MPI quot, MPI rem, MPI dividend, MPI divisor); 19 20 void mpi_fdiv_r(MPI rem, MPI dividend, MPI divisor) 21 { 22 int divisor_sign = divisor->sign; 23 MPI temp_divisor = NULL; 24 25 /* We need the original value of the divisor after the remainder has been 26 * preliminary calculated. We have to copy it to temporary space if it's 27 * the same variable as REM. 28 */ 29 if (rem == divisor) { 30 temp_divisor = mpi_copy(divisor); 31 divisor = temp_divisor; 32 } 33 34 mpi_tdiv_r(rem, dividend, divisor); 35 36 if (((divisor_sign?1:0) ^ (dividend->sign?1:0)) && rem->nlimbs) 37 mpi_add(rem, rem, divisor); 38 39 if (temp_divisor) 40 mpi_free(temp_divisor); 41 } 42 43 void mpi_fdiv_q(MPI quot, MPI dividend, MPI divisor) 44 { 45 MPI tmp = mpi_alloc(mpi_get_nlimbs(quot)); 46 mpi_fdiv_qr(quot, tmp, dividend, divisor); 47 mpi_free(tmp); 48 } 49 50 void mpi_fdiv_qr(MPI quot, MPI rem, MPI dividend, MPI divisor) 51 { 52 int divisor_sign = divisor->sign; 53 MPI temp_divisor = NULL; 54 55 if (quot == divisor || rem == divisor) { 56 temp_divisor = mpi_copy(divisor); 57 divisor = temp_divisor; 58 } 59 60 mpi_tdiv_qr(quot, rem, dividend, divisor); 61 62 if ((divisor_sign ^ dividend->sign) && rem->nlimbs) { 63 mpi_sub_ui(quot, quot, 1); 64 mpi_add(rem, rem, divisor); 65 } 66 67 if (temp_divisor) 68 mpi_free(temp_divisor); 69 } 70 71 /* If den == quot, den needs temporary storage. 72 * If den == rem, den needs temporary storage. 73 * If num == quot, num needs temporary storage. 74 * If den has temporary storage, it can be normalized while being copied, 75 * i.e no extra storage should be allocated. 76 */ 77 78 void mpi_tdiv_r(MPI rem, MPI num, MPI den) 79 { 80 mpi_tdiv_qr(NULL, rem, num, den); 81 } 82 83 void mpi_tdiv_qr(MPI quot, MPI rem, MPI num, MPI den) 84 { 85 mpi_ptr_t np, dp; 86 mpi_ptr_t qp, rp; 87 mpi_size_t nsize = num->nlimbs; 88 mpi_size_t dsize = den->nlimbs; 89 mpi_size_t qsize, rsize; 90 mpi_size_t sign_remainder = num->sign; 91 mpi_size_t sign_quotient = num->sign ^ den->sign; 92 unsigned int normalization_steps; 93 mpi_limb_t q_limb; 94 mpi_ptr_t marker[5]; 95 int markidx = 0; 96 97 /* Ensure space is enough for quotient and remainder. 98 * We need space for an extra limb in the remainder, because it's 99 * up-shifted (normalized) below. 100 */ 101 rsize = nsize + 1; 102 mpi_resize(rem, rsize); 103 104 qsize = rsize - dsize; /* qsize cannot be bigger than this. */ 105 if (qsize <= 0) { 106 if (num != rem) { 107 rem->nlimbs = num->nlimbs; 108 rem->sign = num->sign; 109 MPN_COPY(rem->d, num->d, nsize); 110 } 111 if (quot) { 112 /* This needs to follow the assignment to rem, in case the 113 * numerator and quotient are the same. 114 */ 115 quot->nlimbs = 0; 116 quot->sign = 0; 117 } 118 return; 119 } 120 121 if (quot) 122 mpi_resize(quot, qsize); 123 124 /* Read pointers here, when reallocation is finished. */ 125 np = num->d; 126 dp = den->d; 127 rp = rem->d; 128 129 /* Optimize division by a single-limb divisor. */ 130 if (dsize == 1) { 131 mpi_limb_t rlimb; 132 if (quot) { 133 qp = quot->d; 134 rlimb = mpihelp_divmod_1(qp, np, nsize, dp[0]); 135 qsize -= qp[qsize - 1] == 0; 136 quot->nlimbs = qsize; 137 quot->sign = sign_quotient; 138 } else 139 rlimb = mpihelp_mod_1(np, nsize, dp[0]); 140 rp[0] = rlimb; 141 rsize = rlimb != 0?1:0; 142 rem->nlimbs = rsize; 143 rem->sign = sign_remainder; 144 return; 145 } 146 147 148 if (quot) { 149 qp = quot->d; 150 /* Make sure QP and NP point to different objects. Otherwise the 151 * numerator would be gradually overwritten by the quotient limbs. 152 */ 153 if (qp == np) { /* Copy NP object to temporary space. */ 154 np = marker[markidx++] = mpi_alloc_limb_space(nsize); 155 MPN_COPY(np, qp, nsize); 156 } 157 } else /* Put quotient at top of remainder. */ 158 qp = rp + dsize; 159 160 normalization_steps = count_leading_zeros(dp[dsize - 1]); 161 162 /* Normalize the denominator, i.e. make its most significant bit set by 163 * shifting it NORMALIZATION_STEPS bits to the left. Also shift the 164 * numerator the same number of steps (to keep the quotient the same!). 165 */ 166 if (normalization_steps) { 167 mpi_ptr_t tp; 168 mpi_limb_t nlimb; 169 170 /* Shift up the denominator setting the most significant bit of 171 * the most significant word. Use temporary storage not to clobber 172 * the original contents of the denominator. 173 */ 174 tp = marker[markidx++] = mpi_alloc_limb_space(dsize); 175 mpihelp_lshift(tp, dp, dsize, normalization_steps); 176 dp = tp; 177 178 /* Shift up the numerator, possibly introducing a new most 179 * significant word. Move the shifted numerator in the remainder 180 * meanwhile. 181 */ 182 nlimb = mpihelp_lshift(rp, np, nsize, normalization_steps); 183 if (nlimb) { 184 rp[nsize] = nlimb; 185 rsize = nsize + 1; 186 } else 187 rsize = nsize; 188 } else { 189 /* The denominator is already normalized, as required. Copy it to 190 * temporary space if it overlaps with the quotient or remainder. 191 */ 192 if (dp == rp || (quot && (dp == qp))) { 193 mpi_ptr_t tp; 194 195 tp = marker[markidx++] = mpi_alloc_limb_space(dsize); 196 MPN_COPY(tp, dp, dsize); 197 dp = tp; 198 } 199 200 /* Move the numerator to the remainder. */ 201 if (rp != np) 202 MPN_COPY(rp, np, nsize); 203 204 rsize = nsize; 205 } 206 207 q_limb = mpihelp_divrem(qp, 0, rp, rsize, dp, dsize); 208 209 if (quot) { 210 qsize = rsize - dsize; 211 if (q_limb) { 212 qp[qsize] = q_limb; 213 qsize += 1; 214 } 215 216 quot->nlimbs = qsize; 217 quot->sign = sign_quotient; 218 } 219 220 rsize = dsize; 221 MPN_NORMALIZE(rp, rsize); 222 223 if (normalization_steps && rsize) { 224 mpihelp_rshift(rp, rp, rsize, normalization_steps); 225 rsize -= rp[rsize - 1] == 0?1:0; 226 } 227 228 rem->nlimbs = rsize; 229 rem->sign = sign_remainder; 230 while (markidx) { 231 markidx--; 232 mpi_free_limb_space(marker[markidx]); 233 } 234 } 235