Branch data Line data Source code
1 : : // SPDX-License-Identifier: GPL-2.0-or-later
2 : : /* mpihelp-div.c - MPI helper functions
3 : : * Copyright (C) 1994, 1996 Free Software Foundation, Inc.
4 : : * Copyright (C) 1998, 1999 Free Software Foundation, Inc.
5 : : *
6 : : * This file is part of GnuPG.
7 : : *
8 : : * Note: This code is heavily based on the GNU MP Library.
9 : : * Actually it's the same code with only minor changes in the
10 : : * way the data is stored; this is to support the abstraction
11 : : * of an optional secure memory allocation which may be used
12 : : * to avoid revealing of sensitive data due to paging etc.
13 : : * The GNU MP Library itself is published under the LGPL;
14 : : * however I decided to publish this code under the plain GPL.
15 : : */
16 : :
17 : : #include "mpi-internal.h"
18 : : #include "longlong.h"
19 : :
20 : : #ifndef UMUL_TIME
21 : : #define UMUL_TIME 1
22 : : #endif
23 : : #ifndef UDIV_TIME
24 : : #define UDIV_TIME UMUL_TIME
25 : : #endif
26 : :
27 : : /* Divide num (NP/NSIZE) by den (DP/DSIZE) and write
28 : : * the NSIZE-DSIZE least significant quotient limbs at QP
29 : : * and the DSIZE long remainder at NP. If QEXTRA_LIMBS is
30 : : * non-zero, generate that many fraction bits and append them after the
31 : : * other quotient limbs.
32 : : * Return the most significant limb of the quotient, this is always 0 or 1.
33 : : *
34 : : * Preconditions:
35 : : * 0. NSIZE >= DSIZE.
36 : : * 1. The most significant bit of the divisor must be set.
37 : : * 2. QP must either not overlap with the input operands at all, or
38 : : * QP + DSIZE >= NP must hold true. (This means that it's
39 : : * possible to put the quotient in the high part of NUM, right after the
40 : : * remainder in NUM.
41 : : * 3. NSIZE >= DSIZE, even if QEXTRA_LIMBS is non-zero.
42 : : */
43 : :
44 : : mpi_limb_t
45 : 29088 : mpihelp_divrem(mpi_ptr_t qp, mpi_size_t qextra_limbs,
46 : : mpi_ptr_t np, mpi_size_t nsize, mpi_ptr_t dp, mpi_size_t dsize)
47 : : {
48 : : mpi_limb_t most_significant_q_limb = 0;
49 : :
50 [ - - - + ]: 29088 : switch (dsize) {
51 : : case 0:
52 : : /* We are asked to divide by zero, so go ahead and do it! (To make
53 : : the compiler not remove this statement, return the value.) */
54 : : /*
55 : : * existing clients of this function have been modified
56 : : * not to call it with dsize == 0, so this should not happen
57 : : */
58 : 0 : return 1 / dsize;
59 : :
60 : : case 1:
61 : : {
62 : : mpi_size_t i;
63 : : mpi_limb_t n1;
64 : : mpi_limb_t d;
65 : :
66 : 0 : d = dp[0];
67 : 0 : n1 = np[nsize - 1];
68 : :
69 [ # # ]: 0 : if (n1 >= d) {
70 : 0 : n1 -= d;
71 : : most_significant_q_limb = 1;
72 : : }
73 : :
74 : 0 : qp += qextra_limbs;
75 [ # # ]: 0 : for (i = nsize - 2; i >= 0; i--)
76 [ # # # # : 0 : udiv_qrnnd(qp[i], n1, n1, np[i], d);
# # # # #
# # # ]
77 : : qp -= qextra_limbs;
78 : :
79 [ # # ]: 0 : for (i = qextra_limbs - 1; i >= 0; i--)
80 [ # # # # : 0 : udiv_qrnnd(qp[i], n1, n1, 0, d);
# # # # #
# # # ]
81 : :
82 : 0 : np[0] = n1;
83 : : }
84 : 0 : break;
85 : :
86 : : case 2:
87 : : {
88 : : mpi_size_t i;
89 : : mpi_limb_t n1, n0, n2;
90 : : mpi_limb_t d1, d0;
91 : :
92 : 0 : np += nsize - 2;
93 : 0 : d1 = dp[1];
94 : 0 : d0 = dp[0];
95 : 0 : n1 = np[1];
96 : 0 : n0 = np[0];
97 : :
98 [ # # # # ]: 0 : if (n1 >= d1 && (n1 > d1 || n0 >= d0)) {
99 : 0 : sub_ddmmss(n1, n0, n1, n0, d1, d0);
100 : : most_significant_q_limb = 1;
101 : : }
102 : :
103 [ # # ]: 0 : for (i = qextra_limbs + nsize - 2 - 1; i >= 0; i--) {
104 : : mpi_limb_t q;
105 : : mpi_limb_t r;
106 : :
107 [ # # ]: 0 : if (i >= qextra_limbs)
108 : 0 : np--;
109 : : else
110 : 0 : np[0] = 0;
111 : :
112 [ # # ]: 0 : if (n1 == d1) {
113 : : /* Q should be either 111..111 or 111..110. Need special
114 : : * treatment of this rare case as normal division would
115 : : * give overflow. */
116 : : q = ~(mpi_limb_t) 0;
117 : :
118 : 0 : r = n0 + d1;
119 [ # # ]: 0 : if (r < d1) { /* Carry in the addition? */
120 : 0 : add_ssaaaa(n1, n0, r - d0,
121 : : np[0], 0, d0);
122 : 0 : qp[i] = q;
123 : 0 : continue;
124 : : }
125 [ # # ]: 0 : n1 = d0 - (d0 != 0 ? 1 : 0);
126 : 0 : n0 = -d0;
127 : : } else {
128 [ # # # # : 0 : udiv_qrnnd(q, r, n1, n0, d1);
# # # # #
# # # ]
129 : 0 : umul_ppmm(n1, n0, d0, q);
130 : : }
131 : :
132 : 0 : n2 = np[0];
133 : : q_test:
134 [ # # # # ]: 0 : if (n1 > r || (n1 == r && n0 > n2)) {
135 : : /* The estimated Q was too large. */
136 : 0 : q--;
137 : 0 : sub_ddmmss(n1, n0, n1, n0, 0, d0);
138 : 0 : r += d1;
139 [ # # ]: 0 : if (r >= d1) /* If not carry, test Q again. */
140 : : goto q_test;
141 : : }
142 : :
143 : 0 : qp[i] = q;
144 : 0 : sub_ddmmss(n1, n0, r, n2, n1, n0);
145 : : }
146 : 0 : np[1] = n1;
147 : 0 : np[0] = n0;
148 : : }
149 : 0 : break;
150 : :
151 : : default:
152 : : {
153 : : mpi_size_t i;
154 : : mpi_limb_t dX, d1, n0;
155 : :
156 : 29088 : np += nsize - dsize;
157 : 29088 : dX = dp[dsize - 1];
158 : 29088 : d1 = dp[dsize - 2];
159 : 29088 : n0 = np[dsize - 1];
160 : :
161 [ - + ]: 29088 : if (n0 >= dX) {
162 [ # # ]: 0 : if (n0 > dX
163 [ # # ]: 0 : || mpihelp_cmp(np, dp, dsize - 1) >= 0) {
164 : 0 : mpihelp_sub_n(np, np, dp, dsize);
165 : 0 : n0 = np[dsize - 1];
166 : : most_significant_q_limb = 1;
167 : : }
168 : : }
169 : :
170 [ + + ]: 1787296 : for (i = qextra_limbs + nsize - dsize - 1; i >= 0; i--) {
171 : : mpi_limb_t q;
172 : : mpi_limb_t n1, n2;
173 : : mpi_limb_t cy_limb;
174 : :
175 [ + - ]: 1758208 : if (i >= qextra_limbs) {
176 : 1758208 : np--;
177 : 1758208 : n2 = np[dsize];
178 : : } else {
179 : 0 : n2 = np[dsize - 1];
180 [ # # ]: 0 : MPN_COPY_DECR(np + 1, np, dsize - 1);
181 : 0 : np[0] = 0;
182 : : }
183 : :
184 [ + - ]: 1758208 : if (n0 == dX) {
185 : : /* This might over-estimate q, but it's probably not worth
186 : : * the extra code here to find out. */
187 : : q = ~(mpi_limb_t) 0;
188 : : } else {
189 : : mpi_limb_t r;
190 : :
191 [ + + + + : 1758208 : udiv_qrnnd(q, r, n0, np[dsize - 1], dX);
+ + + + +
+ + + ]
192 : 1758208 : umul_ppmm(n1, n0, d1, q);
193 : :
194 [ + + ]: 3692560 : while (n1 > r
195 [ - + ]: 1758208 : || (n1 == r
196 [ # # ]: 0 : && n0 > np[dsize - 2])) {
197 : 176144 : q--;
198 : 176144 : r += dX;
199 [ + - ]: 176144 : if (r < dX) /* I.e. "carry in previous addition?" */
200 : : break;
201 : 176144 : n1 -= n0 < d1;
202 : 176144 : n0 -= d1;
203 : : }
204 : : }
205 : :
206 : : /* Possible optimization: We already have (q * n0) and (1 * n1)
207 : : * after the calculation of q. Taking advantage of that, we
208 : : * could make this loop make two iterations less. */
209 : 1758208 : cy_limb = mpihelp_submul_1(np, dp, dsize, q);
210 : :
211 [ - + ]: 1758208 : if (n2 != cy_limb) {
212 : 0 : mpihelp_add_n(np, np, dp, dsize);
213 : 0 : q--;
214 : : }
215 : :
216 : 1758208 : qp[i] = q;
217 : 1758208 : n0 = np[dsize - 1];
218 : : }
219 : : }
220 : : }
221 : :
222 : 29088 : return most_significant_q_limb;
223 : : }
|
