/home/ntakagi/work/tcl8.5.1/libtommath/bn_mp_div_2d.c Source File

00001 #include <tommath.h>
00002 #ifdef BN_MP_DIV_2D_C
00003 /* LibTomMath, multiple-precision integer library -- Tom St Denis
00004  *
00005  * LibTomMath is a library that provides multiple-precision
00006  * integer arithmetic as well as number theoretic functionality.
00007  *
00008  * The library was designed directly after the MPI library by
00009  * Michael Fromberger but has been written from scratch with
00010  * additional optimizations in place.
00011  *
00012  * The library is free for all purposes without any express
00013  * guarantee it works.
00014  *
00015  * Tom St Denis, tomstdenis@gmail.com, http://math.libtomcrypt.com
00016  */
00017 
00018 /* shift right by a certain bit count (store quotient in c, optional remainder in d) */
00019 int mp_div_2d (mp_int * a, int b, mp_int * c, mp_int * d)
00020 {
00021   mp_digit D, r, rr;
00022   int     x, res;
00023   mp_int  t;
00024 
00025 
00026   /* if the shift count is <= 0 then we do no work */
00027   if (b <= 0) {
00028     res = mp_copy (a, c);
00029     if (d != NULL) {
00030       mp_zero (d);
00031     }
00032     return res;
00033   }
00034 
00035   if ((res = mp_init (&t)) != MP_OKAY) {
00036     return res;
00037   }
00038 
00039   /* get the remainder */
00040   if (d != NULL) {
00041     if ((res = mp_mod_2d (a, b, &t)) != MP_OKAY) {
00042       mp_clear (&t);
00043       return res;
00044     }
00045   }
00046 
00047   /* copy */
00048   if ((res = mp_copy (a, c)) != MP_OKAY) {
00049     mp_clear (&t);
00050     return res;
00051   }
00052 
00053   /* shift by as many digits in the bit count */
00054   if (b >= (int)DIGIT_BIT) {
00055     mp_rshd (c, b / DIGIT_BIT);
00056   }
00057 
00058   /* shift any bit count < DIGIT_BIT */
00059   D = (mp_digit) (b % DIGIT_BIT);
00060   if (D != 0) {
00061     register mp_digit *tmpc, mask, shift;
00062 
00063     /* mask */
00064     mask = (((mp_digit)1) << D) - 1;
00065 
00066     /* shift for lsb */
00067     shift = DIGIT_BIT - D;
00068 
00069     /* alias */
00070     tmpc = c->dp + (c->used - 1);
00071 
00072     /* carry */
00073     r = 0;
00074     for (x = c->used - 1; x >= 0; x--) {
00075       /* get the lower  bits of this word in a temp */
00076       rr = *tmpc & mask;
00077 
00078       /* shift the current word and mix in the carry bits from the previous word */
00079       *tmpc = (*tmpc >> D) | (r << shift);
00080       --tmpc;
00081 
00082       /* set the carry to the carry bits of the current word found above */
00083       r = rr;
00084     }
00085   }
00086   mp_clamp (c);
00087   if (d != NULL) {
00088     mp_exch (&t, d);
00089   }
00090   mp_clear (&t);
00091   return MP_OKAY;
00092 }
00093 #endif
00094 
00095 /* $Source: /cvsroot/tcl/libtommath/bn_mp_div_2d.c,v $ */
00096 /* $Revision: 1.1.1.3 $ */
00097 /* $Date: 2006/12/01 00:08:11 $ */