// Copyright 2016 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

// Package bitops provides various utility functions and types for low level
// bit-twiddling.
package bitops

// FFS (Find First Set) returns the index of the least significant bit in x
// that is set to 1.  Calling FFS(0) is undefined behavior.
func FFS(x uint64) (n uint)

var ffsTable = []uint{0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0}

func ffs(x uint64) uint {
	var n uint

	if x&0x00000000FFFFFFFF == 0 {
		n += 32
		x >>= 32
	}
	if x&0x000000000000FFFF == 0 {
		n += 16
		x >>= 16
	}
	if x&0x00000000000000FF == 0 {
		n += 8
		x >>= 8
	}
	if x&0x000000000000000F == 0 {
		n += 4
		x >>= 4
	}
	n += ffsTable[x&0xf]

	return n
}

// CLZ (Count Leading Zeros) counts the number of leading zeroes before the
// most significant bit in x that is set to 1.  Calling CLZ(0) is undefined
// behavior.
func CLZ(x uint64) (n uint)

var clzTable = []uint{4, 3, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0}

func clz(x uint64) uint {
	var n uint

	if x&0xFFFFFFFF00000000 == 0 {
		n += 32
		x <<= 32
	}
	if x&0xFFFF000000000000 == 0 {
		n += 16
		x <<= 16
	}
	if x&0xFF00000000000000 == 0 {
		n += 8
		x <<= 8
	}
	if x&0xF000000000000000 == 0 {
		n += 4
		x <<= 4
	}
	n += clzTable[x>>60]

	return n
}