pd.if.org Git - zpackage/blob - tomsfastmath/src/bit/fp_cnt_lsb.c

   1 /* TomsFastMath, a fast ISO C bignum library.
   2  *
   3  * This project is meant to fill in where LibTomMath
   4  * falls short.  That is speed ;-)
   5  *
   6  * This project is public domain and free for all purposes.
   7  *
   8  * Tom St Denis, tomstdenis@gmail.com
   9  */
  10 #include <tfm_private.h>
  11
  12 static const int lnz[16] = {
  13    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
  14 };
  15
  16 /* Counts the number of lsbs which are zero before the first zero bit */
  17 int fp_cnt_lsb(fp_int *a)
  18 {
  19    int x;
  20    fp_digit q, qq;
  21
  22    /* easy out */
  23    if (fp_iszero(a) == 1) {
  24       return 0;
  25    }
  26
  27    /* scan lower digits until non-zero */
  28    for (x = 0; x < a->used && a->dp[x] == 0; x++);
  29    q = a->dp[x];
  30    x *= DIGIT_BIT;
  31
  32    /* now scan this digit until a 1 is found */
  33    if ((q & 1) == 0) {
  34       do {
  35          qq  = q & 15;
  36          x  += lnz[qq];
  37          q >>= 4;
  38       } while (qq == 0);
  39    }
  40    return x;
  41 }
  42
  43
  44 /* $Source$ */
  45 /* $Revision$ */
  46 /* $Date$ */