libgo/go/runtime/fastlog2.go

   1 // Copyright 2015 The Go Authors. 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 // +build ignore
   6
   7 package runtime
   8
   9 import "unsafe"
  10
  11 // fastlog2 implements a fast approximation to the base 2 log of a
  12 // float64. This is used to compute a geometric distribution for heap
  13 // sampling, without introducing dependencies into package math. This
  14 // uses a very rough approximation using the float64 exponent and the
  15 // first 25 bits of the mantissa. The top 5 bits of the mantissa are
  16 // used to load limits from a table of constants and the rest are used
  17 // to scale linearly between them.
  18 func fastlog2(x float64) float64 {
  19         const fastlogScaleBits = 20
  20         const fastlogScaleRatio = 1.0 / (1 << fastlogScaleBits)
  21
  22         xBits := float64bits(x)
  23         // Extract the exponent from the IEEE float64, and index a constant
  24         // table with the first 10 bits from the mantissa.
  25         xExp := int64((xBits>>52)&0x7FF) - 1023
  26         xManIndex := (xBits >> (52 - fastlogNumBits)) % (1 << fastlogNumBits)
  27         xManScale := (xBits >> (52 - fastlogNumBits - fastlogScaleBits)) % (1 << fastlogScaleBits)
  28
  29         low, high := fastlog2Table[xManIndex], fastlog2Table[xManIndex+1]
  30         return float64(xExp) + low + (high-low)*float64(xManScale)*fastlogScaleRatio
  31 }
  32
  33 // float64bits returns the IEEE 754 binary representation of f.
  34 // Taken from math.Float64bits to avoid dependencies into package math.
  35 func float64bits(f float64) uint64 { return *(*uint64)(unsafe.Pointer(&f)) }