Annotation of OpenXM_contrib/gmp/mpz/scan1.c, Revision 1.1.1.3
1.1.1.3 ! ohara 1: /* mpz_scan1 -- search for a 1 bit.
1.1 maekawa 2:
1.1.1.3 ! ohara 3: Copyright 2000, 2001, 2002 Free Software Foundation, Inc.
1.1 maekawa 4:
5: This file is part of the GNU MP Library.
6:
7: The GNU MP Library is free software; you can redistribute it and/or modify
1.1.1.2 maekawa 8: it under the terms of the GNU Lesser General Public License as published by
9: the Free Software Foundation; either version 2.1 of the License, or (at your
1.1 maekawa 10: option) any later version.
11:
12: The GNU MP Library is distributed in the hope that it will be useful, but
13: WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
1.1.1.2 maekawa 14: or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
1.1 maekawa 15: License for more details.
16:
1.1.1.2 maekawa 17: You should have received a copy of the GNU Lesser General Public License
1.1 maekawa 18: along with the GNU MP Library; see the file COPYING.LIB. If not, write to
19: the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
20: MA 02111-1307, USA. */
21:
22: #include "gmp.h"
23: #include "gmp-impl.h"
1.1.1.3 ! ohara 24: #include "longlong.h"
1.1 maekawa 25:
1.1.1.3 ! ohara 26:
! 27: /* mpn_scan0 can't be used for the inverted u<0 search since there might not
! 28: be a 0 bit before the end of the data. mpn_scan1 could be used under u>0
! 29: (except when in the high limb), but usually the search won't go very far
! 30: so it seems reasonable to inline that code. */
! 31:
! 32: unsigned long
! 33: mpz_scan1 (mpz_srcptr u, unsigned long starting_bit)
1.1 maekawa 34: {
1.1.1.3 ! ohara 35: mp_srcptr u_ptr = PTR(u);
! 36: mp_size_t size = SIZ(u);
! 37: mp_size_t abs_size = ABS(size);
! 38: mp_srcptr u_end = u_ptr + abs_size;
! 39: unsigned long starting_limb = starting_bit / GMP_NUMB_BITS;
! 40: mp_srcptr p = u_ptr + starting_limb;
! 41: mp_limb_t limb;
! 42: int cnt;
! 43:
! 44: /* Past the end there's no 1 bits for u>=0, or an immediate 1 bit for u<0.
! 45: Notice this test picks up any u==0 too. */
! 46: if (starting_limb >= abs_size)
! 47: return (size >= 0 ? ULONG_MAX : starting_bit);
! 48:
! 49: limb = *p;
! 50:
! 51: if (size >= 0)
! 52: {
! 53: /* Mask to 0 all bits before starting_bit, thus ignoring them. */
! 54: limb &= (MP_LIMB_T_MAX << (starting_bit % GMP_NUMB_BITS));
! 55:
! 56: if (limb == 0)
! 57: {
! 58: /* If it's the high limb which is zero after masking, then there's
! 59: no 1 bits after starting_bit. */
! 60: p++;
! 61: if (p == u_end)
! 62: return ULONG_MAX;
! 63:
! 64: /* Otherwise search further for a non-zero limb. The high limb is
! 65: non-zero, if nothing else. */
! 66: for (;;)
! 67: {
! 68: limb = *p;
! 69: if (limb != 0)
! 70: break;
! 71: p++;
! 72: ASSERT (p < u_end);
! 73: }
! 74: }
! 75: }
! 76: else
! 77: {
! 78: mp_srcptr q;
! 79:
! 80: /* If there's a non-zero limb before ours then we're in the ones
! 81: complement region. Search from *(p-1) downwards since that might
! 82: give better cache locality, and since a non-zero in the middle of a
! 83: number is perhaps a touch more likely than at the end. */
! 84: q = p;
! 85: while (q != u_ptr)
! 86: {
! 87: q--;
! 88: if (*q != 0)
! 89: goto inverted;
! 90: }
! 91:
! 92: if (limb == 0)
! 93: {
! 94: /* Skip zero limbs, to find the start of twos complement. The
! 95: high limb is non-zero, if nothing else. This search is
! 96: necessary so the -limb is applied at the right spot. */
! 97: do
! 98: {
! 99: p++;
! 100: ASSERT (p < u_end);
! 101: limb = *p;
! 102: }
! 103: while (limb == 0);
! 104:
! 105: /* Apply twos complement, and look for a 1 bit in that. Since
! 106: limb!=0 here, also have (-limb)!=0 so there's certainly a 1
! 107: bit. */
! 108: limb = -limb;
! 109: goto got_limb;
! 110: }
! 111:
! 112: /* Adjust so ~limb implied by searching for 0 bit becomes -limb. */
! 113: limb--;
! 114:
! 115: inverted:
! 116: /* Now seeking a 0 bit. */
! 117:
! 118: /* Mask to 1 all bits before starting_bit, thus ignoring them. */
! 119: limb |= (CNST_LIMB(1) << (starting_bit % GMP_NUMB_BITS)) - 1;
! 120:
! 121: /* Search for a limb which is not all ones. If the end is reached
! 122: then the zero immediately past the end is the result. */
! 123: while (limb == GMP_NUMB_MAX)
! 124: {
! 125: p++;
! 126: if (p == u_end)
! 127: return abs_size * GMP_NUMB_BITS;
! 128: limb = *p;
! 129: }
! 130:
! 131: /* Now seeking low 1 bit. */
! 132: limb = ~limb;
! 133: }
! 134:
! 135: got_limb:
! 136: /* Mask to 0 all bits above the lowest 1 bit. */
! 137: ASSERT (limb != 0);
! 138: limb &= -limb;
! 139:
! 140: count_leading_zeros (cnt, limb);
! 141: return (p - u_ptr) * GMP_NUMB_BITS + GMP_LIMB_BITS - 1 - cnt;
1.1 maekawa 142: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>