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 int mpi_tdiv_qr(MPI quot, MPI rem, MPI num, MPI den); 18 19 int mpi_fdiv_r(MPI rem, MPI dividend, MPI divisor) 20 { 21 int divisor_sign = divisor->sign; 22 MPI temp_divisor = NULL; 23 int err; 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 if (!temp_divisor) 32 return -ENOMEM; 33 divisor = temp_divisor; 34 } 35 36 err = mpi_tdiv_r(rem, dividend, divisor); 37 if (err) 38 goto free_temp_divisor; 39 40 if (((divisor_sign?1:0) ^ (dividend->sign?1:0)) && rem->nlimbs) 41 err = mpi_add(rem, rem, divisor); 42 43 free_temp_divisor: 44 mpi_free(temp_divisor); 45 46 return err; 47 } 48 49 /* If den == quot, den needs temporary storage. 50 * If den == rem, den needs temporary storage. 51 * If num == quot, num needs temporary storage. 52 * If den has temporary storage, it can be normalized while being copied, 53 * i.e no extra storage should be allocated. 54 */ 55 56 int mpi_tdiv_r(MPI rem, MPI num, MPI den) 57 { 58 return mpi_tdiv_qr(NULL, rem, num, den); 59 } 60 61 int mpi_tdiv_qr(MPI quot, MPI rem, MPI num, MPI den) 62 { 63 mpi_ptr_t np, dp; 64 mpi_ptr_t qp, rp; 65 mpi_size_t nsize = num->nlimbs; 66 mpi_size_t dsize = den->nlimbs; 67 mpi_size_t qsize, rsize; 68 mpi_size_t sign_remainder = num->sign; 69 mpi_size_t sign_quotient = num->sign ^ den->sign; 70 unsigned int normalization_steps; 71 mpi_limb_t q_limb; 72 mpi_ptr_t marker[5]; 73 int markidx = 0; 74 int err; 75 76 /* Ensure space is enough for quotient and remainder. 77 * We need space for an extra limb in the remainder, because it's 78 * up-shifted (normalized) below. 79 */ 80 rsize = nsize + 1; 81 err = mpi_resize(rem, rsize); 82 if (err) 83 return err; 84 85 qsize = rsize - dsize; /* qsize cannot be bigger than this. */ 86 if (qsize <= 0) { 87 if (num != rem) { 88 rem->nlimbs = num->nlimbs; 89 rem->sign = num->sign; 90 MPN_COPY(rem->d, num->d, nsize); 91 } 92 if (quot) { 93 /* This needs to follow the assignment to rem, in case the 94 * numerator and quotient are the same. 95 */ 96 quot->nlimbs = 0; 97 quot->sign = 0; 98 } 99 return 0; 100 } 101 102 if (quot) { 103 err = mpi_resize(quot, qsize); 104 if (err) 105 return err; 106 } 107 108 /* Read pointers here, when reallocation is finished. */ 109 np = num->d; 110 dp = den->d; 111 rp = rem->d; 112 113 /* Optimize division by a single-limb divisor. */ 114 if (dsize == 1) { 115 mpi_limb_t rlimb; 116 if (quot) { 117 qp = quot->d; 118 rlimb = mpihelp_divmod_1(qp, np, nsize, dp[0]); 119 qsize -= qp[qsize - 1] == 0; 120 quot->nlimbs = qsize; 121 quot->sign = sign_quotient; 122 } else 123 rlimb = mpihelp_mod_1(np, nsize, dp[0]); 124 rp[0] = rlimb; 125 rsize = rlimb != 0?1:0; 126 rem->nlimbs = rsize; 127 rem->sign = sign_remainder; 128 return 0; 129 } 130 131 err = -ENOMEM; 132 if (quot) { 133 qp = quot->d; 134 /* Make sure QP and NP point to different objects. Otherwise the 135 * numerator would be gradually overwritten by the quotient limbs. 136 */ 137 if (qp == np) { /* Copy NP object to temporary space. */ 138 np = marker[markidx++] = mpi_alloc_limb_space(nsize); 139 if (!np) 140 goto out_free_marker; 141 MPN_COPY(np, qp, nsize); 142 } 143 } else /* Put quotient at top of remainder. */ 144 qp = rp + dsize; 145 146 normalization_steps = count_leading_zeros(dp[dsize - 1]); 147 148 /* Normalize the denominator, i.e. make its most significant bit set by 149 * shifting it NORMALIZATION_STEPS bits to the left. Also shift the 150 * numerator the same number of steps (to keep the quotient the same!). 151 */ 152 if (normalization_steps) { 153 mpi_ptr_t tp; 154 mpi_limb_t nlimb; 155 156 /* Shift up the denominator setting the most significant bit of 157 * the most significant word. Use temporary storage not to clobber 158 * the original contents of the denominator. 159 */ 160 tp = marker[markidx++] = mpi_alloc_limb_space(dsize); 161 if (!tp) 162 goto out_free_marker; 163 mpihelp_lshift(tp, dp, dsize, normalization_steps); 164 dp = tp; 165 166 /* Shift up the numerator, possibly introducing a new most 167 * significant word. Move the shifted numerator in the remainder 168 * meanwhile. 169 */ 170 nlimb = mpihelp_lshift(rp, np, nsize, normalization_steps); 171 if (nlimb) { 172 rp[nsize] = nlimb; 173 rsize = nsize + 1; 174 } else 175 rsize = nsize; 176 } else { 177 /* The denominator is already normalized, as required. Copy it to 178 * temporary space if it overlaps with the quotient or remainder. 179 */ 180 if (dp == rp || (quot && (dp == qp))) { 181 mpi_ptr_t tp; 182 183 tp = marker[markidx++] = mpi_alloc_limb_space(dsize); 184 if (!tp) 185 goto out_free_marker; 186 MPN_COPY(tp, dp, dsize); 187 dp = tp; 188 } 189 190 /* Move the numerator to the remainder. */ 191 if (rp != np) 192 MPN_COPY(rp, np, nsize); 193 194 rsize = nsize; 195 } 196 197 q_limb = mpihelp_divrem(qp, 0, rp, rsize, dp, dsize); 198 199 if (quot) { 200 qsize = rsize - dsize; 201 if (q_limb) { 202 qp[qsize] = q_limb; 203 qsize += 1; 204 } 205 206 quot->nlimbs = qsize; 207 quot->sign = sign_quotient; 208 } 209 210 rsize = dsize; 211 MPN_NORMALIZE(rp, rsize); 212 213 if (normalization_steps && rsize) { 214 mpihelp_rshift(rp, rp, rsize, normalization_steps); 215 rsize -= rp[rsize - 1] == 0?1:0; 216 } 217 218 rem->nlimbs = rsize; 219 rem->sign = sign_remainder; 220 221 err = 0; 222 223 out_free_marker: 224 while (markidx) { 225 markidx--; 226 mpi_free_limb_space(marker[markidx]); 227 } 228 229 return err; 230 } 231