1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
// 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])
}
|
