/**
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package org.apache.lucene.util;

public class TestBitUtil extends LuceneTestCase {

  private static int slowNlz(long x) {
    if (x == 0L) return 64;
    int nlz = 0;
    while ( ((x << nlz) & (1L << 63)) == 0) {
      nlz++;
    }
    return nlz;
  }

  private void checkNlz(long x) {
    assertEquals(slowNlz(x), BitUtil.nlz(x));
    assertEquals(Long.numberOfLeadingZeros(x), BitUtil.nlz(x));
  }
  
  public void testNlz() {
    checkNlz(0L);
    checkNlz(1L);
    checkNlz(-1L);
    for (int i = 1; i <= 63; i++) {
      checkNlz(1L << i);
      checkNlz((1L << i) + (1L << (i>>1)));
    }
  }

  public void testBitUtils() {
    long num = 100000;
    assertEquals( 5, BitUtil.ntz(num) );
    assertEquals( 5, BitUtil.ntz2(num) );
    assertEquals( 5, BitUtil.ntz3(num) );
    
    num = 10;
    assertEquals( 1, BitUtil.ntz(num) );
    assertEquals( 1, BitUtil.ntz2(num) );
    assertEquals( 1, BitUtil.ntz3(num) );

    for (int i=0; i<64; i++) {
      num = 1L << i;
      assertEquals( i, BitUtil.ntz(num) );
      assertEquals( i, BitUtil.ntz2(num) );
      assertEquals( i, BitUtil.ntz3(num) );
    }
  }


  private long testArg(int shift) {
    return (1L << shift) + (1L << (shift>>1));
  }
  
  private long nlzBitUtilBasicLoop(int iters) {
    long sumRes = 0;
    while (iters-- >= 0) {
      for (int i = 1; i <= 63; i++) {
      	long a = testArg(i);
	sumRes += BitUtil.nlz(a);
	sumRes += BitUtil.nlz(a+1);
	sumRes += BitUtil.nlz(a-1);
	sumRes += BitUtil.nlz(a+10);
	sumRes += BitUtil.nlz(a-10);
      }
    }
    return sumRes;
  }
    
  private long nlzLongBasicLoop(int iters) {
    long sumRes = 0;
    while (iters-- >= 0) {
      for (int i = 1; i <= 63; i++) {
      	long a = testArg(i);
	sumRes += Long.numberOfLeadingZeros(a);
	sumRes += Long.numberOfLeadingZeros(a+1);
	sumRes += Long.numberOfLeadingZeros(a-1);
	sumRes += Long.numberOfLeadingZeros(a+10);
	sumRes += Long.numberOfLeadingZeros(a-10);
      }
    }
    return sumRes;
  }

  public void tstPerfNlz() { // See LUCENE-3197, prefer to use Long.numberOfLeadingZeros() over BitUtil.nlz().
    final long measureMilliSecs = 2000;
    final int basicIters = 100000;
    long startTime;
    long endTime;
    long curTime;
    long dummy = 0; // avoid optimizing away

    dummy = 0;
    int bitUtilLoops = 0;
    startTime = System.currentTimeMillis();
    endTime = startTime + measureMilliSecs;
    do {
      dummy += nlzBitUtilBasicLoop(basicIters);
      bitUtilLoops++;
      curTime = System.currentTimeMillis();
    } while (curTime < endTime);
    int bitUtilPsTime = (int) (1000000000 * (curTime - startTime) / (basicIters * 5 * 63 * (float) bitUtilLoops));
    System.out.println("BitUtil nlz time: " + (bitUtilPsTime/1) + " picosec/call, dummy: " + dummy);


    dummy = 0;
    int longLoops = 0;
    startTime = System.currentTimeMillis();
    endTime = startTime + measureMilliSecs;
    do {
      dummy += nlzLongBasicLoop(basicIters);
      longLoops++;
      curTime = System.currentTimeMillis();
    } while (curTime < endTime);
    int longPsTime = (int) (1000000000 * (curTime - startTime) / (basicIters * 5 * 63 * (float) longLoops));
    System.out.println("Long    nlz time: " + longPsTime + " picosec/call, dummy: " + dummy);
  }
}