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(a: divisor); |
31 | divisor = temp_divisor; |
32 | } |
33 | |
34 | mpi_tdiv_r(rem, num: dividend, den: divisor); |
35 | |
36 | if (((divisor_sign?1:0) ^ (dividend->sign?1:0)) && rem->nlimbs) |
37 | mpi_add(w: rem, u: rem, v: divisor); |
38 | |
39 | if (temp_divisor) |
40 | mpi_free(a: 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, rem: tmp, dividend, divisor); |
47 | mpi_free(a: 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(a: divisor); |
57 | divisor = temp_divisor; |
58 | } |
59 | |
60 | mpi_tdiv_qr(quot, rem, num: dividend, den: divisor); |
61 | |
62 | if ((divisor_sign ^ dividend->sign) && rem->nlimbs) { |
63 | mpi_sub_ui(w: quot, u: quot, vval: 1); |
64 | mpi_add(w: rem, u: rem, v: divisor); |
65 | } |
66 | |
67 | if (temp_divisor) |
68 | mpi_free(a: 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(a: rem, nlimbs: 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(a: quot, nlimbs: 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(quot_ptr: qp, dividend_ptr: np, dividend_size: nsize, divisor_limb: dp[0]); |
135 | qsize -= qp[qsize - 1] == 0; |
136 | quot->nlimbs = qsize; |
137 | quot->sign = sign_quotient; |
138 | } else |
139 | rlimb = mpihelp_mod_1(dividend_ptr: np, dividend_size: nsize, divisor_limb: 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(nlimbs: 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(x: 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(nlimbs: dsize); |
175 | mpihelp_lshift(wp: tp, up: dp, usize: dsize, cnt: 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(wp: rp, up: np, usize: nsize, cnt: 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(nlimbs: 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, qextra_limbs: 0, np: rp, nsize: 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(wp: rp, up: rp, usize: rsize, cnt: 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(a: marker[markidx]); |
233 | } |
234 | } |
235 | |