forked from ~ljy/RK356X_SDK_RELEASE
blame | history | patch | commit | commitdiff
hc
2023-12-11 6778948f9de86c3cfaf36725a7c87dcff9ba247f 
 kernel/lib/mpi/mpih-div.c
....@@ -1,22 +1,9 @@
1
+// SPDX-License-Identifier: GPL-2.0-or-later
12 /* mpihelp-div.c  -  MPI helper functions
23  *	Copyright (C) 1994, 1996 Free Software Foundation, Inc.
34  *	Copyright (C) 1998, 1999 Free Software Foundation, Inc.
45  *
56  * This file is part of GnuPG.
6
- *
7
- * GnuPG is free software; you can redistribute it and/or modify
8
- * it under the terms of the GNU General Public License as published by
9
- * the Free Software Foundation; either version 2 of the License, or
10
- * (at your option) any later version.
11
- *
12
- * GnuPG is distributed in the hope that it will be useful,
13
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
14
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15
- * GNU General Public License for more details.
16
- *
17
- * You should have received a copy of the GNU General Public License
18
- * along with this program; if not, write to the Free Software
19
- * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
207  *
218  * Note: This code is heavily based on the GNU MP Library.
229  *	 Actually it's the same code with only minor changes in the
....@@ -36,6 +23,150 @@
3623 #ifndef UDIV_TIME
3724 #define UDIV_TIME UMUL_TIME
3825 #endif
26
+
27
+
28
+mpi_limb_t
29
+mpihelp_mod_1(mpi_ptr_t dividend_ptr, mpi_size_t dividend_size,
30
+			mpi_limb_t divisor_limb)
31
+{
32
+	mpi_size_t i;
33
+	mpi_limb_t n1, n0, r;
34
+	mpi_limb_t dummy __maybe_unused;
35
+
36
+	/* Botch: Should this be handled at all?  Rely on callers?	*/
37
+	if (!dividend_size)
38
+		return 0;
39
+
40
+	/* If multiplication is much faster than division, and the
41
+	 * dividend is large, pre-invert the divisor, and use
42
+	 * only multiplications in the inner loop.
43
+	 *
44
+	 * This test should be read:
45
+	 *	 Does it ever help to use udiv_qrnnd_preinv?
46
+	 *	   && Does what we save compensate for the inversion overhead?
47
+	 */
48
+	if (UDIV_TIME > (2 * UMUL_TIME + 6)
49
+			&& (UDIV_TIME - (2 * UMUL_TIME + 6)) * dividend_size > UDIV_TIME) {
50
+		int normalization_steps;
51
+
52
+		normalization_steps = count_leading_zeros(divisor_limb);
53
+		if (normalization_steps) {
54
+			mpi_limb_t divisor_limb_inverted;
55
+
56
+			divisor_limb <<= normalization_steps;
57
+
58
+			/* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB.  The
59
+			 * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
60
+			 * most significant bit (with weight 2**N) implicit.
61
+			 *
62
+			 * Special case for DIVISOR_LIMB == 100...000.
63
+			 */
64
+			if (!(divisor_limb << 1))
65
+				divisor_limb_inverted = ~(mpi_limb_t)0;
66
+			else
67
+				udiv_qrnnd(divisor_limb_inverted, dummy,
68
+						-divisor_limb, 0, divisor_limb);
69
+
70
+			n1 = dividend_ptr[dividend_size - 1];
71
+			r = n1 >> (BITS_PER_MPI_LIMB - normalization_steps);
72
+
73
+			/* Possible optimization:
74
+			 * if (r == 0
75
+			 * && divisor_limb > ((n1 << normalization_steps)
76
+			 *		       | (dividend_ptr[dividend_size - 2] >> ...)))
77
+			 * ...one division less...
78
+			 */
79
+			for (i = dividend_size - 2; i >= 0; i--) {
80
+				n0 = dividend_ptr[i];
81
+				UDIV_QRNND_PREINV(dummy, r, r,
82
+						((n1 << normalization_steps)
83
+						 | (n0 >> (BITS_PER_MPI_LIMB - normalization_steps))),
84
+						divisor_limb, divisor_limb_inverted);
85
+				n1 = n0;
86
+			}
87
+			UDIV_QRNND_PREINV(dummy, r, r,
88
+					n1 << normalization_steps,
89
+					divisor_limb, divisor_limb_inverted);
90
+			return r >> normalization_steps;
91
+		} else {
92
+			mpi_limb_t divisor_limb_inverted;
93
+
94
+			/* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB.  The
95
+			 * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
96
+			 * most significant bit (with weight 2**N) implicit.
97
+			 *
98
+			 * Special case for DIVISOR_LIMB == 100...000.
99
+			 */
100
+			if (!(divisor_limb << 1))
101
+				divisor_limb_inverted = ~(mpi_limb_t)0;
102
+			else
103
+				udiv_qrnnd(divisor_limb_inverted, dummy,
104
+						-divisor_limb, 0, divisor_limb);
105
+
106
+			i = dividend_size - 1;
107
+			r = dividend_ptr[i];
108
+
109
+			if (r >= divisor_limb)
110
+				r = 0;
111
+			else
112
+				i--;
113
+
114
+			for ( ; i >= 0; i--) {
115
+				n0 = dividend_ptr[i];
116
+				UDIV_QRNND_PREINV(dummy, r, r,
117
+						n0, divisor_limb, divisor_limb_inverted);
118
+			}
119
+			return r;
120
+		}
121
+	} else {
122
+		if (UDIV_NEEDS_NORMALIZATION) {
123
+			int normalization_steps;
124
+
125
+			normalization_steps = count_leading_zeros(divisor_limb);
126
+			if (normalization_steps) {
127
+				divisor_limb <<= normalization_steps;
128
+
129
+				n1 = dividend_ptr[dividend_size - 1];
130
+				r = n1 >> (BITS_PER_MPI_LIMB - normalization_steps);
131
+
132
+				/* Possible optimization:
133
+				 * if (r == 0
134
+				 * && divisor_limb > ((n1 << normalization_steps)
135
+				 *		   | (dividend_ptr[dividend_size - 2] >> ...)))
136
+				 * ...one division less...
137
+				 */
138
+				for (i = dividend_size - 2; i >= 0; i--) {
139
+					n0 = dividend_ptr[i];
140
+					udiv_qrnnd(dummy, r, r,
141
+						((n1 << normalization_steps)
142
+						 | (n0 >> (BITS_PER_MPI_LIMB - normalization_steps))),
143
+						divisor_limb);
144
+					n1 = n0;
145
+				}
146
+				udiv_qrnnd(dummy, r, r,
147
+						n1 << normalization_steps,
148
+						divisor_limb);
149
+				return r >> normalization_steps;
150
+			}
151
+		}
152
+		/* No normalization needed, either because udiv_qrnnd doesn't require
153
+		 * it, or because DIVISOR_LIMB is already normalized.
154
+		 */
155
+		i = dividend_size - 1;
156
+		r = dividend_ptr[i];
157
+
158
+		if (r >= divisor_limb)
159
+			r = 0;
160
+		else
161
+			i--;
162
+
163
+		for (; i >= 0; i--) {
164
+			n0 = dividend_ptr[i];
165
+			udiv_qrnnd(dummy, r, r, n0, divisor_limb);
166
+		}
167
+		return r;
168
+	}
169
+}
39170 
40171 /* Divide num (NP/NSIZE) by den (DP/DSIZE) and write
41172  * the NSIZE-DSIZE least significant quotient limbs at QP
....@@ -234,3 +365,153 @@
234365 
235366 	return most_significant_q_limb;
236367 }
368
+
369
+/****************
370
+ * Divide (DIVIDEND_PTR,,DIVIDEND_SIZE) by DIVISOR_LIMB.
371
+ * Write DIVIDEND_SIZE limbs of quotient at QUOT_PTR.
372
+ * Return the single-limb remainder.
373
+ * There are no constraints on the value of the divisor.
374
+ *
375
+ * QUOT_PTR and DIVIDEND_PTR might point to the same limb.
376
+ */
377
+
378
+mpi_limb_t
379
+mpihelp_divmod_1(mpi_ptr_t quot_ptr,
380
+		mpi_ptr_t dividend_ptr, mpi_size_t dividend_size,
381
+		mpi_limb_t divisor_limb)
382
+{
383
+	mpi_size_t i;
384
+	mpi_limb_t n1, n0, r;
385
+	mpi_limb_t dummy __maybe_unused;
386
+
387
+	if (!dividend_size)
388
+		return 0;
389
+
390
+	/* If multiplication is much faster than division, and the
391
+	 * dividend is large, pre-invert the divisor, and use
392
+	 * only multiplications in the inner loop.
393
+	 *
394
+	 * This test should be read:
395
+	 * Does it ever help to use udiv_qrnnd_preinv?
396
+	 * && Does what we save compensate for the inversion overhead?
397
+	 */
398
+	if (UDIV_TIME > (2 * UMUL_TIME + 6)
399
+			&& (UDIV_TIME - (2 * UMUL_TIME + 6)) * dividend_size > UDIV_TIME) {
400
+		int normalization_steps;
401
+
402
+		normalization_steps = count_leading_zeros(divisor_limb);
403
+		if (normalization_steps) {
404
+			mpi_limb_t divisor_limb_inverted;
405
+
406
+			divisor_limb <<= normalization_steps;
407
+
408
+			/* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB.  The
409
+			 * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
410
+			 * most significant bit (with weight 2**N) implicit.
411
+			 */
412
+			/* Special case for DIVISOR_LIMB == 100...000.  */
413
+			if (!(divisor_limb << 1))
414
+				divisor_limb_inverted = ~(mpi_limb_t)0;
415
+			else
416
+				udiv_qrnnd(divisor_limb_inverted, dummy,
417
+						-divisor_limb, 0, divisor_limb);
418
+
419
+			n1 = dividend_ptr[dividend_size - 1];
420
+			r = n1 >> (BITS_PER_MPI_LIMB - normalization_steps);
421
+
422
+			/* Possible optimization:
423
+			 * if (r == 0
424
+			 * && divisor_limb > ((n1 << normalization_steps)
425
+			 *		       | (dividend_ptr[dividend_size - 2] >> ...)))
426
+			 * ...one division less...
427
+			 */
428
+			for (i = dividend_size - 2; i >= 0; i--) {
429
+				n0 = dividend_ptr[i];
430
+				UDIV_QRNND_PREINV(quot_ptr[i + 1], r, r,
431
+						((n1 << normalization_steps)
432
+						 | (n0 >> (BITS_PER_MPI_LIMB - normalization_steps))),
433
+						divisor_limb, divisor_limb_inverted);
434
+				n1 = n0;
435
+			}
436
+			UDIV_QRNND_PREINV(quot_ptr[0], r, r,
437
+					n1 << normalization_steps,
438
+					divisor_limb, divisor_limb_inverted);
439
+			return r >> normalization_steps;
440
+		} else {
441
+			mpi_limb_t divisor_limb_inverted;
442
+
443
+			/* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB.  The
444
+			 * result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
445
+			 * most significant bit (with weight 2**N) implicit.
446
+			 */
447
+			/* Special case for DIVISOR_LIMB == 100...000.  */
448
+			if (!(divisor_limb << 1))
449
+				divisor_limb_inverted = ~(mpi_limb_t) 0;
450
+			else
451
+				udiv_qrnnd(divisor_limb_inverted, dummy,
452
+						-divisor_limb, 0, divisor_limb);
453
+
454
+			i = dividend_size - 1;
455
+			r = dividend_ptr[i];
456
+
457
+			if (r >= divisor_limb)
458
+				r = 0;
459
+			else
460
+				quot_ptr[i--] = 0;
461
+
462
+			for ( ; i >= 0; i--) {
463
+				n0 = dividend_ptr[i];
464
+				UDIV_QRNND_PREINV(quot_ptr[i], r, r,
465
+						n0, divisor_limb, divisor_limb_inverted);
466
+			}
467
+			return r;
468
+		}
469
+	} else {
470
+		if (UDIV_NEEDS_NORMALIZATION) {
471
+			int normalization_steps;
472
+
473
+			normalization_steps = count_leading_zeros(divisor_limb);
474
+			if (normalization_steps) {
475
+				divisor_limb <<= normalization_steps;
476
+
477
+				n1 = dividend_ptr[dividend_size - 1];
478
+				r = n1 >> (BITS_PER_MPI_LIMB - normalization_steps);
479
+
480
+				/* Possible optimization:
481
+				 * if (r == 0
482
+				 * && divisor_limb > ((n1 << normalization_steps)
483
+				 *		   | (dividend_ptr[dividend_size - 2] >> ...)))
484
+				 * ...one division less...
485
+				 */
486
+				for (i = dividend_size - 2; i >= 0; i--) {
487
+					n0 = dividend_ptr[i];
488
+					udiv_qrnnd(quot_ptr[i + 1], r, r,
489
+						((n1 << normalization_steps)
490
+						 | (n0 >> (BITS_PER_MPI_LIMB - normalization_steps))),
491
+						divisor_limb);
492
+					n1 = n0;
493
+				}
494
+				udiv_qrnnd(quot_ptr[0], r, r,
495
+						n1 << normalization_steps,
496
+						divisor_limb);
497
+				return r >> normalization_steps;
498
+			}
499
+		}
500
+		/* No normalization needed, either because udiv_qrnnd doesn't require
501
+		 * it, or because DIVISOR_LIMB is already normalized.
502
+		 */
503
+		i = dividend_size - 1;
504
+		r = dividend_ptr[i];
505
+
506
+		if (r >= divisor_limb)
507
+			r = 0;
508
+		else
509
+			quot_ptr[i--] = 0;
510
+
511
+		for (; i >= 0; i--) {
512
+			n0 = dividend_ptr[i];
513
+			udiv_qrnnd(quot_ptr[i], r, r, n0, divisor_limb);
514
+		}
515
+		return r;
516
+	}
517
+}