fp_cnt_lsb.c

00001 /* TomsFastMath, a fast ISO C bignum library.
00002  * 
00003  * This project is meant to fill in where LibTomMath
00004  * falls short.  That is speed ;-)
00005  *
00006  * This project is public domain and free for all purposes.
00007  * 
00008  * Tom St Denis, tomstdenis@gmail.com
00009  */
00010 #include <tfm.h>
00011 
00012 static const int lnz[16] = {
00013    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
00014 };
00015 
00016 /* Counts the number of lsbs which are zero before the first zero bit */
00017 int fp_cnt_lsb(fp_int *a)
00018 {
00019    int x;
00020    fp_digit q, qq;
00021 
00022    /* easy out */
00023    if (fp_iszero(a) == 1) {
00024       return 0;
00025    }
00026 
00027    /* scan lower digits until non-zero */
00028    for (x = 0; x < a->used && a->dp[x] == 0; x++);
00029    q = a->dp[x];
00030    x *= DIGIT_BIT;
00031 
00032    /* now scan this digit until a 1 is found */
00033    if ((q & 1) == 0) {
00034       do {
00035          qq  = q & 15;
00036          x  += lnz[qq];
00037          q >>= 4;
00038       } while (qq == 0);
00039    }
00040    return x;
00041 }
00042 
00043 
00044 /* $Source: /cvs/libtom/tomsfastmath/src/bit/fp_cnt_lsb.c,v $ */
00045 /* $Revision: 1.1 $ */
00046 /* $Date: 2006/12/31 21:25:53 $ */