Line data    Source code

       1             : #include "tommath_private.h"
       2             : #ifdef BN_MP_DIV_3_C
       3             : /* LibTomMath, multiple-precision integer library -- Tom St Denis */
       4             : /* SPDX-License-Identifier: Unlicense */
       5             : 
       6             : /* divide by three (based on routine from MPI and the GMP manual) */
       7           0 : mp_err mp_div_3(const mp_int *a, mp_int *c, mp_digit *d)
       8             : {
       9           0 :    mp_int   q;
      10           0 :    mp_word  w, t;
      11           0 :    mp_digit b;
      12           0 :    mp_err   err;
      13           0 :    int      ix;
      14             : 
      15             :    /* b = 2**MP_DIGIT_BIT / 3 */
      16           0 :    b = ((mp_word)1 << (mp_word)MP_DIGIT_BIT) / (mp_word)3;
      17             : 
      18           0 :    if ((err = mp_init_size(&q, a->used)) != MP_OKAY) {
      19           0 :       return err;
      20             :    }
      21             : 
      22           0 :    q.used = a->used;
      23           0 :    q.sign = a->sign;
      24           0 :    w = 0;
      25           0 :    for (ix = a->used - 1; ix >= 0; ix--) {
      26           0 :       w = (w << (mp_word)MP_DIGIT_BIT) | (mp_word)a->dp[ix];
      27             : 
      28           0 :       if (w >= 3u) {
      29             :          /* multiply w by [1/3] */
      30           0 :          t = (w * (mp_word)b) >> (mp_word)MP_DIGIT_BIT;
      31             : 
      32             :          /* now subtract 3 * [w/3] from w, to get the remainder */
      33           0 :          w -= t+t+t;
      34             : 
      35             :          /* fixup the remainder as required since
      36             :           * the optimization is not exact.
      37             :           */
      38           0 :          while (w >= 3u) {
      39           0 :             t += 1u;
      40           0 :             w -= 3u;
      41             :          }
      42             :       } else {
      43           0 :          t = 0;
      44             :       }
      45           0 :       q.dp[ix] = (mp_digit)t;
      46             :    }
      47             : 
      48             :    /* [optional] store the remainder */
      49           0 :    if (d != NULL) {
      50           0 :       *d = (mp_digit)w;
      51             :    }
      52             : 
      53             :    /* [optional] store the quotient */
      54           0 :    if (c != NULL) {
      55           0 :       mp_clamp(&q);
      56           0 :       mp_exch(&q, c);
      57             :    }
      58           0 :    mp_clear(&q);
      59             : 
      60           0 :    return err;
      61             : }
      62             : 
      63             : #endif