[github/fretlink/terraform-provider-statuscake.git] / vendor / github.com / ulikunitz / xz / lzma / bitops.go

// Copyright 2014-2017 Ulrich Kunitz. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package lzma

/* Naming conventions follows the CodeReviewComments in the Go Wiki. */

// ntz32Const is used by the functions NTZ and NLZ.
const ntz32Const = 0x04d7651f

// ntz32Table is a helper table for de Bruijn algorithm by Danny Dubé.
// See Henry S. Warren, Jr. "Hacker's Delight" section 5-1 figure 5-26.
var ntz32Table = [32]int8{
	0, 1, 2, 24, 3, 19, 6, 25,
	22, 4, 20, 10, 16, 7, 12, 26,
	31, 23, 18, 5, 21, 9, 15, 11,
	30, 17, 8, 14, 29, 13, 28, 27,
}

// ntz32 computes the number of trailing zeros for an unsigned 32-bit integer.
func ntz32(x uint32) int {
	if x == 0 {
		return 32
	}
	x = (x & -x) * ntz32Const
	return int(ntz32Table[x>>27])
}

// nlz32 computes the number of leading zeros for an unsigned 32-bit integer.
func nlz32(x uint32) int {
	// Smear left most bit to the right
	x |= x >> 1
	x |= x >> 2
	x |= x >> 4
	x |= x >> 8
	x |= x >> 16
	// Use ntz mechanism to calculate nlz.
	x++
	if x == 0 {
		return 0
	}
	x *= ntz32Const
	return 32 - int(ntz32Table[x>>27])
}
Commit	Line	Data
15c0b25d AP	1	// Copyright 2014-2017 Ulrich Kunitz. All rights reserved.
	2	// Use of this source code is governed by a BSD-style
	3	// license that can be found in the LICENSE file.
	4
	5	package lzma
	6
	7	/* Naming conventions follows the CodeReviewComments in the Go Wiki. */
	8
	9	// ntz32Const is used by the functions NTZ and NLZ.
	10	const ntz32Const = 0x04d7651f
	11
	12	// ntz32Table is a helper table for de Bruijn algorithm by Danny Dubé.
	13	// See Henry S. Warren, Jr. "Hacker's Delight" section 5-1 figure 5-26.
	14	var ntz32Table = [32]int8{
	15	0, 1, 2, 24, 3, 19, 6, 25,
	16	22, 4, 20, 10, 16, 7, 12, 26,
	17	31, 23, 18, 5, 21, 9, 15, 11,
	18	30, 17, 8, 14, 29, 13, 28, 27,
	19	}
	20
	21	// ntz32 computes the number of trailing zeros for an unsigned 32-bit integer.
	22	func ntz32(x uint32) int {
	23	if x == 0 {
	24	return 32
	25	}
	26	x = (x & -x) * ntz32Const
	27	return int(ntz32Table[x>>27])
	28	}
	29
	30	// nlz32 computes the number of leading zeros for an unsigned 32-bit integer.
	31	func nlz32(x uint32) int {
	32	// Smear left most bit to the right
	33	x \|= x >> 1
	34	x \|= x >> 2
	35	x \|= x >> 4
	36	x \|= x >> 8
	37	x \|= x >> 16
	38	// Use ntz mechanism to calculate nlz.
	39	x++
	40	if x == 0 {
	41	return 0
	42	}
	43	x *= ntz32Const
	44	return 32 - int(ntz32Table[x>>27])
	45	}