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 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// ntz32 computes the number of trailing zeros for an unsigned 32-bit integer. 22func 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. 31func 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} 46