Hi Yonik, I wrote atestcase that checks how prevSetBit behaves, if I add you patch with optimization. It still had a bug, if the index is beyond last word but not at a multiple of bitsPerWord. The following code is correct:
public int prevSetBit(int index) { int i = index >> 6; final int subIndex; if (i >= wlen) { i = wlen - 1; if (i < 0) return -1; subIndex = 0x3f; // last possible bit } else { if (i < 0) return -1; subIndex = index & 0x3f; // index within the word } long word = (bits[i] << (63-subIndex)); // skip all the bits to the left of index if (word != 0) { return (i << 6) + subIndex - Long.numberOfLeadingZeros(word); // See LUCENE-3197 } while (--i >= 0) { word = bits[i]; if (word !=0 ) { return (i << 6) + 63 - Long.numberOfLeadingZeros(word); } } return -1; } Your additional optimization with negative indexes is invalid, because on negative indexes prevSetBit() must be negative. If we dont do this, a typical loop like would AIOOBE: for (int i = bs.prevSetBit(0); i >= 0; i = bs.prevSetBit(i-1)) { // operate on index i here } Uwe ----- Uwe Schindler H.-H.-Meier-Allee 63, D-28213 Bremen http://www.thetaphi.de eMail: u...@thetaphi.de > -----Original Message----- > From: ysee...@gmail.com [mailto:ysee...@gmail.com] On Behalf Of Yonik > Seeley > Sent: Friday, June 24, 2011 6:29 PM > To: dev@lucene.apache.org > Subject: Re: [VOTE] release 3.3 > > On Fri, Jun 24, 2011 at 12:14 PM, Yonik Seeley <yo...@lucidimagination.com> > wrote: > > All that needs to be done is to move the negative index check to the > > bottom (the first index<0 is not needed since we do a signed shift). > > > > public int prevSetBit(int index) { > > int i = index>>6; > > if (i >= wlen) { > > i = wlen - 1; > > } > > if (i < 0) return -1; > > final int subIndex = index & 0x3f; // index within the word > > long word = (bits[i] << (63-subIndex)); // skip all the bits to > > the left of index > > And a further minor optimization, if we assume that negative indexes are not > legal, is to move the (i<0) check inside the if (i>=wlen) block (and just let a > negative index passed by the user to cause a natural AIOOB). > > -Yonik > http://www.lucidimagination.com > > --------------------------------------------------------------------- > To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org For additional > commands, e-mail: dev-h...@lucene.apache.org --------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org For additional commands, e-mail: dev-h...@lucene.apache.org