diff options
Diffstat (limited to 'vendor/github.com/ulikunitz/xz/lzma/bitops.go')
-rw-r--r-- | vendor/github.com/ulikunitz/xz/lzma/bitops.go | 45 |
1 files changed, 45 insertions, 0 deletions
diff --git a/vendor/github.com/ulikunitz/xz/lzma/bitops.go b/vendor/github.com/ulikunitz/xz/lzma/bitops.go new file mode 100644 index 0000000..e9bab01 --- /dev/null +++ b/vendor/github.com/ulikunitz/xz/lzma/bitops.go | |||
@@ -0,0 +1,45 @@ | |||
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 | } | ||