libs/libtommath/bn_mp_cnt_lsb.c

   1 #include <tommath.h>
   2 #ifdef BN_MP_CNT_LSB_C
   3 /* LibTomMath, multiple-precision integer library -- Tom St Denis
   4  *
   5  * LibTomMath is a library that provides multiple-precision
   6  * integer arithmetic as well as number theoretic functionality.
   7  *
   8  * The library was designed directly after the MPI library by
   9  * Michael Fromberger but has been written from scratch with
  10  * additional optimizations in place.
  11  *
  12  * The library is free for all purposes without any express
  13  * guarantee it works.
  14  *
  15  * Tom St Denis, tomstdenis@gmail.com, http://math.libtomcrypt.com
  16  */
  17
  18 static const int lnz[16] = {
  19    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
  20 };
  21
  22 /* Counts the number of lsbs which are zero before the first zero bit */
  23 int mp_cnt_lsb(mp_int *a)
  24 {
  25    int x;
  26    mp_digit q, qq;
  27
  28    /* easy out */
  29    if (mp_iszero(a) == 1) {
  30       return 0;
  31    }
  32
  33    /* scan lower digits until non-zero */
  34    for (x = 0; x < a->used && a->dp[x] == 0; x++);
  35    q = a->dp[x];
  36    x *= DIGIT_BIT;
  37
  38    /* now scan this digit until a 1 is found */
  39    if ((q & 1) == 0) {
  40       do {
  41          qq  = q & 15;
  42          x  += lnz[qq];
  43          q >>= 4;
  44       } while (qq == 0);
  45    }
  46    return x;
  47 }
  48
  49 #endif
  50
  51 /* $Source: /cvs/libtom/libtommath/bn_mp_cnt_lsb.c,v $ */
  52 /* $Revision: 1.3 $ */
  53 /* $Date: 2006/03/31 14:18:44 $ */