186d7f5d3SJohn Marino /* mpn_scan1 -- Scan from a given bit position for the next set bit.
286d7f5d3SJohn Marino
386d7f5d3SJohn Marino Copyright 1994, 1996, 2001, 2002, 2004 Free Software Foundation, Inc.
486d7f5d3SJohn Marino
586d7f5d3SJohn Marino This file is part of the GNU MP Library.
686d7f5d3SJohn Marino
786d7f5d3SJohn Marino The GNU MP Library is free software; you can redistribute it and/or modify
886d7f5d3SJohn Marino it under the terms of the GNU Lesser General Public License as published by
986d7f5d3SJohn Marino the Free Software Foundation; either version 3 of the License, or (at your
1086d7f5d3SJohn Marino option) any later version.
1186d7f5d3SJohn Marino
1286d7f5d3SJohn Marino The GNU MP Library is distributed in the hope that it will be useful, but
1386d7f5d3SJohn Marino WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
1486d7f5d3SJohn Marino or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
1586d7f5d3SJohn Marino License for more details.
1686d7f5d3SJohn Marino
1786d7f5d3SJohn Marino You should have received a copy of the GNU Lesser General Public License
1886d7f5d3SJohn Marino along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */
1986d7f5d3SJohn Marino
2086d7f5d3SJohn Marino #include "gmp.h"
2186d7f5d3SJohn Marino #include "gmp-impl.h"
2286d7f5d3SJohn Marino #include "longlong.h"
2386d7f5d3SJohn Marino
2486d7f5d3SJohn Marino /* Argument constraints:
2586d7f5d3SJohn Marino 1. U must sooner or later have a limb != 0.
2686d7f5d3SJohn Marino */
2786d7f5d3SJohn Marino
2886d7f5d3SJohn Marino mp_bitcnt_t
mpn_scan1(mp_srcptr up,mp_bitcnt_t starting_bit)2986d7f5d3SJohn Marino mpn_scan1 (mp_srcptr up, mp_bitcnt_t starting_bit)
3086d7f5d3SJohn Marino {
3186d7f5d3SJohn Marino mp_size_t starting_word;
3286d7f5d3SJohn Marino mp_limb_t alimb;
3386d7f5d3SJohn Marino int cnt;
3486d7f5d3SJohn Marino mp_srcptr p;
3586d7f5d3SJohn Marino
3686d7f5d3SJohn Marino /* Start at the word implied by STARTING_BIT. */
3786d7f5d3SJohn Marino starting_word = starting_bit / GMP_NUMB_BITS;
3886d7f5d3SJohn Marino p = up + starting_word;
3986d7f5d3SJohn Marino alimb = *p++;
4086d7f5d3SJohn Marino
4186d7f5d3SJohn Marino /* Mask off any bits before STARTING_BIT in the first limb. */
4286d7f5d3SJohn Marino alimb &= - (mp_limb_t) 1 << (starting_bit % GMP_NUMB_BITS);
4386d7f5d3SJohn Marino
4486d7f5d3SJohn Marino while (alimb == 0)
4586d7f5d3SJohn Marino alimb = *p++;
4686d7f5d3SJohn Marino
4786d7f5d3SJohn Marino count_trailing_zeros (cnt, alimb);
4886d7f5d3SJohn Marino return (p - up - 1) * GMP_NUMB_BITS + cnt;
4986d7f5d3SJohn Marino }
50