1// Copyright 2014-2022 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
 5package lzma
 6
 7/* Naming conventions follows the CodeReviewComments in the Go Wiki. */
 8
 9// ntz32Const is used by the functions NTZ and NLZ.
10const 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.
14var 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/*
22// ntz32 computes the number of trailing zeros for an unsigned 32-bit integer.
23func ntz32(x uint32) int {
24	if x == 0 {
25		return 32
26	}
27	x = (x & -x) * ntz32Const
28	return int(ntz32Table[x>>27])
29}
30*/
31
32// nlz32 computes the number of leading zeros for an unsigned 32-bit integer.
33func nlz32(x uint32) int {
34	// Smear left most bit to the right
35	x |= x >> 1
36	x |= x >> 2
37	x |= x >> 4
38	x |= x >> 8
39	x |= x >> 16
40	// Use ntz mechanism to calculate nlz.
41	x++
42	if x == 0 {
43		return 0
44	}
45	x *= ntz32Const
46	return 32 - int(ntz32Table[x>>27])
47}