Annotation of OpenXM_contrib/gmp/mpz/scan0.c, Revision 1.1.1.3
1.1.1.3 ! ohara 1: /* mpz_scan0 -- search for a 0 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 u>0 search since there might not be a 0
! 28: bit before the end of the data. mpn_scan1 could be used for the inverted
! 29: search under u<0, but usually the search won't go very far so it seems
! 30: reasonable to inline that code. */
! 31:
! 32: unsigned long
! 33: mpz_scan0 (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: /* When past end, there's an immediate 0 bit for u>=0, or no 0 bits for
! 45: u<0. Notice this test picks up all cases of u==0 too. */
! 46: if (starting_limb >= abs_size)
! 47: return (size >= 0 ? starting_bit : ULONG_MAX);
! 48:
! 49: limb = *p;
! 50:
! 51: if (size >= 0)
! 52: {
! 53: /* Mask to 1 all bits before starting_bit, thus ignoring them. */
! 54: limb |= (CNST_LIMB(1) << (starting_bit % GMP_NUMB_BITS)) - 1;
! 55:
! 56: /* Search for a limb which isn't all ones. If the end is reached then
! 57: the zero bit immediately past the end is returned. */
! 58: while (limb == GMP_NUMB_MAX)
! 59: {
! 60: p++;
! 61: if (p == u_end)
! 62: return (unsigned long) abs_size * GMP_NUMB_BITS;
! 63: limb = *p;
! 64: }
! 65:
! 66: /* Now seek low 1 bit. */
! 67: limb = ~limb;
! 68: }
! 69: else
! 70: {
! 71: mp_srcptr q;
! 72:
! 73: /* If there's a non-zero limb before ours then we're in the ones
! 74: complement region. Search from *(p-1) downwards since that might
! 75: give better cache locality, and since a non-zero in the middle of a
! 76: number is perhaps a touch more likely than at the end. */
! 77: q = p;
! 78: while (q != u_ptr)
! 79: {
! 80: q--;
! 81: if (*q != 0)
! 82: goto inverted;
! 83: }
! 84:
! 85: /* Adjust so ~limb implied by searching for 1 bit below becomes -limb.
! 86: If limb==0 here then this isn't the beginning of twos complement
! 87: inversion, but that doesn't matter because limb==0 is a zero bit
! 88: immediately (-1 is all ones for below). */
! 89: limb--;
! 90:
! 91: inverted:
! 92: /* Now seeking a 1 bit. */
! 93:
! 94: /* Mask to 0 all bits before starting_bit, thus ignoring them. */
! 95: limb &= (MP_LIMB_T_MAX << (starting_bit % GMP_NUMB_BITS));
! 96:
! 97: if (limb == 0)
! 98: {
! 99: /* If the high limb is zero after masking, then no 1 bits past
! 100: starting_bit. */
! 101: p++;
! 102: if (p == u_end)
! 103: return ULONG_MAX;
! 104:
! 105: /* Search further for a non-zero limb. The high limb is non-zero,
! 106: if nothing else. */
! 107: for (;;)
! 108: {
! 109: limb = *p;
! 110: if (limb != 0)
! 111: break;
! 112: p++;
! 113: ASSERT (p < u_end);
! 114: }
! 115: }
! 116: }
! 117:
! 118: /* Mask to 0 all bits above the lowest 1 bit. */
! 119: ASSERT (limb != 0);
! 120: limb &= -limb;
! 121:
! 122: count_leading_zeros (cnt, limb);
! 123: return (p - u_ptr) * GMP_NUMB_BITS + GMP_LIMB_BITS - 1 - cnt;
1.1 maekawa 124: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>