userapps/opensource/sshd/libtommath/bn_mp_div_3.c

   1 /* LibTomMath, multiple-precision integer library -- Tom St Denis\r
   2  *\r
   3  * LibTomMath is library that provides for multiple-precision\r
   4  * integer arithmetic as well as number theoretic functionality.\r
   5  *\r
   6  * The library is designed directly after the MPI library by\r
   7  * Michael Fromberger but has been written from scratch with\r
   8  * additional optimizations in place.\r
   9  *\r
  10  * The library is free for all purposes without any express\r
  11  * guarantee it works.\r
  12  *\r
  13  * Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org\r
  14  */\r
  15 #include <tommath.h>\r
  16 \r
  17 /* divide by three (based on routine from MPI and the GMP manual) */\r
  18 int\r
  19 mp_div_3 (mp_int * a, mp_int *c, mp_digit * d)\r
  20 {\r
  21   mp_int   q;\r
  22   mp_word  w, t;\r
  23   mp_digit b;\r
  24   int      res, ix;\r
  25   \r
  26   /* b = 2**DIGIT_BIT / 3 */\r
  27   b = (((mp_word)1) << ((mp_word)DIGIT_BIT)) / ((mp_word)3);\r
  28 \r
  29   if ((res = mp_init_size(&q, a->used)) != MP_OKAY) {\r
  30      return res;\r
  31   }\r
  32   \r
  33   q.used = a->used;\r
  34   q.sign = a->sign;\r
  35   w = 0;\r
  36   for (ix = a->used - 1; ix >= 0; ix--) {\r
  37      w = (w << ((mp_word)DIGIT_BIT)) | ((mp_word)a->dp[ix]);\r
  38      \r
  39      if (w >= 3) {\r
  40         t = (w * ((mp_word)b)) >> ((mp_word)DIGIT_BIT);\r
  41         w -= (t << ((mp_word)1)) + t;\r
  42         while (w >= 3) {\r
  43            t += 1;\r
  44            w -= 3;\r
  45         }\r
  46       } else {\r
  47         t = 0;\r
  48       }\r
  49       q.dp[ix] = (mp_digit)t;\r
  50   }\r
  51   \r
  52   if (d != NULL) {\r
  53      *d = (mp_digit)w;\r
  54   }\r
  55   \r
  56   if (c != NULL) {\r
  57      mp_clamp(&q);\r
  58      mp_exch(&q, c);\r
  59   }\r
  60   mp_clear(&q);\r
  61   \r
  62   return res;\r
  63 }\r
  64 \r