Home | History | Annotate | Line # | Download | only in libtommath 
      1 /*	$NetBSD: bn_mp_div_2d.c,v 1.2 2017/01/28 21:31:47 christos Exp $	*/
      2 
      3 #include <tommath.h>
      4 #ifdef BN_MP_DIV_2D_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 (at) gmail.com, http://libtom.org
     18  */
     19 
     20 /* shift right by a certain bit count (store quotient in c, optional remainder in d) */
     21 int mp_div_2d (mp_int * a, int b, mp_int * c, mp_int * d)
     22 {
     23   mp_digit D, r, rr;
     24   int     x, res;
     25   mp_int  t;
     26 
     27 
     28   /* if the shift count is <= 0 then we do no work */
     29   if (b <= 0) {
     30     res = mp_copy (a, c);
     31     if (d != NULL) {
     32       mp_zero (d);
     33     }
     34     return res;
     35   }
     36 
     37   if ((res = mp_init (&t)) != MP_OKAY) {
     38     return res;
     39   }
     40 
     41   /* get the remainder */
     42   if (d != NULL) {
     43     if ((res = mp_mod_2d (a, b, &t)) != MP_OKAY) {
     44       mp_clear (&t);
     45       return res;
     46     }
     47   }
     48 
     49   /* copy */
     50   if ((res = mp_copy (a, c)) != MP_OKAY) {
     51     mp_clear (&t);
     52     return res;
     53   }
     54 
     55   /* shift by as many digits in the bit count */
     56   if (b >= (int)DIGIT_BIT) {
     57     mp_rshd (c, b / DIGIT_BIT);
     58   }
     59 
     60   /* shift any bit count < DIGIT_BIT */
     61   D = (mp_digit) (b % DIGIT_BIT);
     62   if (D != 0) {
     63     register mp_digit *tmpc, mask, shift;
     64 
     65     /* mask */
     66     mask = (((mp_digit)1) << D) - 1;
     67 
     68     /* shift for lsb */
     69     shift = DIGIT_BIT - D;
     70 
     71     /* alias */
     72     tmpc = c->dp + (c->used - 1);
     73 
     74     /* carry */
     75     r = 0;
     76     for (x = c->used - 1; x >= 0; x--) {
     77       /* get the lower  bits of this word in a temp */
     78       rr = *tmpc & mask;
     79 
     80       /* shift the current word and mix in the carry bits from the previous word */
     81       *tmpc = (*tmpc >> D) | (r << shift);
     82       --tmpc;
     83 
     84       /* set the carry to the carry bits of the current word found above */
     85       r = rr;
     86     }
     87   }
     88   mp_clamp (c);
     89   if (d != NULL) {
     90     mp_exch (&t, d);
     91   }
     92   mp_clear (&t);
     93   return MP_OKAY;
     94 }
     95 #endif
     96 
     97 /* Source: /cvs/libtom/libtommath/bn_mp_div_2d.c,v  */
     98 /* Revision: 1.4  */
     99 /* Date: 2006/12/28 01:25:13  */
    100