1/* $NetBSD: bn_mp_div_d.c,v 1.2 2017/01/28 21:31:47 christos Exp $ */ 2 3#include <tommath.h> 4#ifdef BN_MP_DIV_D_C 5/* LibTomMath, multiple-precision integer library -- Tom St Denis 6 * 7 * LibTomMath is a library that provides multiple-precision 8 * integer arithmetic as well as number theoretic functionality. 9 * 10 * The library was designed directly after the MPI library by 11 * Michael Fromberger but has been written from scratch with 12 * additional optimizations in place. 13 * 14 * The library is free for all purposes without any express 15 * guarantee it works. 16 * 17 * Tom St Denis, tomstdenis@gmail.com, http://libtom.org 18 */ 19 20static int s_is_power_of_two(mp_digit b, int *p) 21{ 22 int x; 23 24 /* fast return if no power of two */ 25 if ((b==0) || (b & (b-1))) { 26 return 0; 27 } 28 29 for (x = 0; x < DIGIT_BIT; x++) { 30 if (b == (((mp_digit)1)<<x)) { 31 *p = x; 32 return 1; 33 } 34 } 35 return 0; 36} 37 38/* single digit division (based on routine from MPI) */ 39int mp_div_d (mp_int * a, mp_digit b, mp_int * c, mp_digit * d) 40{ 41 mp_int q; 42 mp_word w; 43 mp_digit t; 44 int res, ix; 45 46 /* cannot divide by zero */ 47 if (b == 0) { 48 return MP_VAL; 49 } 50 51 /* quick outs */ 52 if (b == 1 || mp_iszero(a) == 1) { 53 if (d != NULL) { 54 *d = 0; 55 } 56 if (c != NULL) { 57 return mp_copy(a, c); 58 } 59 return MP_OKAY; 60 } 61 62 /* power of two ? */ 63 if (s_is_power_of_two(b, &ix) == 1) { 64 if (d != NULL) { 65 *d = a->dp[0] & ((((mp_digit)1)<<ix) - 1); 66 } 67 if (c != NULL) { 68 return mp_div_2d(a, ix, c, NULL); 69 } 70 return MP_OKAY; 71 } 72 73#ifdef BN_MP_DIV_3_C 74 /* three? */ 75 if (b == 3) { 76 return mp_div_3(a, c, d); 77 } 78#endif 79 80 /* no easy answer [c'est la vie]. Just division */ 81 if ((res = mp_init_size(&q, a->used)) != MP_OKAY) { 82 return res; 83 } 84 85 q.used = a->used; 86 q.sign = a->sign; 87 w = 0; 88 for (ix = a->used - 1; ix >= 0; ix--) { 89 w = (w << ((mp_word)DIGIT_BIT)) | ((mp_word)a->dp[ix]); 90 91 if (w >= b) { 92 t = (mp_digit)(w / b); 93 w -= ((mp_word)t) * ((mp_word)b); 94 } else { 95 t = 0; 96 } 97 q.dp[ix] = (mp_digit)t; 98 } 99 100 if (d != NULL) { 101 *d = (mp_digit)w; 102 } 103 104 if (c != NULL) { 105 mp_clamp(&q); 106 mp_exch(&q, c); 107 } 108 mp_clear(&q); 109 110 return res; 111} 112 113#endif 114 115/* Source: /cvs/libtom/libtommath/bn_mp_div_d.c,v */ 116/* Revision: 1.5 */ 117/* Date: 2007/01/09 04:44:32 */ 118