go.temporal.io/server/common/number/compact8.go

98 LOC · 56 covered · 42 uncovered · 21 ranges · 73 concepts · 15 introducers · 40 tests

File neighbourhood

The centred file is linked to every concept that introduces one of its ranges, every test that runs code from the file, and the gray connector concepts standing between those tests and the file's own introducer concepts. Undirected links join concepts to every file where they introduce source and concepts to the tests they introduce; arrows show specialization between the displayed concepts and bridge only concepts omitted from this view. Concept colors match the source ranges below; connector concepts have no source color and are shown in gray.

Focused file, its introducer and connector concepts, their introduced files, and tests that run code from the file

In the embedded map, ordinary wheel input scrolls the page; use the visible controls to zoom and drag to pan. Open the full-screen map for canvas navigation: wheel pans, Ctrl/Command plus wheel zooms, and arrow keys pan when this region is focused. On touch screens, open the full-screen map to pan or pinch. If JavaScript or WebGL is unavailable, use the related-file, concept, and source links on this page.

  1
  
  package number
  
  2
  
  3
  
  import "math/bits"
  
  4
  
  5
  
  // Compact8 is an unsigned 8-bit compact integer encoding with 12 mantissa
  
  6
  
  // values per exponent level (instead of the standard power-of-2 split).
  
  7
  
  //
  
  8
  
  // For a byte value b, let e = b / 12 and m = b % 12:
  
  9
  
  //
  
  10
  
  //	b=0:          0                        (zero)
  
  11
  
  //	e=0, m>=1:    m << (offset+1)          (subnormal)
  
  12
  
  //	e>=1:         (12+m) << (e+offset)     (normalized)
  
  13
  
  //
  
  14
  
  // This gives approximately 8.3% relative precision (12 values per octave)
  
  15
  
  // and a representable range from 32 to 503316480 with offset 4.
  
  16
  
  type Compact8 = uint8
  
  17
  
  18
  
  const compact8offset = 4
  
  19
  
  20
  
  // DecodeCompact8 converts a Compact8 value to an int64.
  
  21
  >
  func DecodeCompact8(b Compact8) int64 {
  
compact8.go ×2

  22
  >
  	if b == 0 {
  
  23
  >
  		return 0
  
compact8.go ×1

  24
  >
  	}
  
  25
  >
  	e := int(b / 12)
  
compact8.go ×2

  26
  >
  	m := int(b % 12)
  
  27
  >
  	if e == 0 {
  
  28
  >
  		return int64(m) << (compact8offset + 1)
  
compact8.go ×1

  29
  >
  	}
  
  30
  >
  	return int64(12+m) << (e + compact8offset)
  
compact8.go ×1

  31
  
  }
  
  32
  
  33
  
  // EncodeCompact8 encodes a non-negative int64 into Compact8 representation.
  
  34
  
  // The value is rounded down to the nearest representable value.
  
  35
  
  // Negative values go to 0 and values above the maximum representable go to 255.
  
  36
  >
  func EncodeCompact8(value int64) Compact8 {
  
compact8.go ×1

  37
  >
  	if value <= 0 {
  
  38
  >
  		return 0
  
compact8.go ×1

  39
  >
  	}
  
  40
  
  41
  >
  	uval := uint64(value)
  
compact8.go ×2

  42
  >
  	bitLen := bits.Len64(uval)
  
  43
  >
  
  44
  >
  	// Find shift such that uval >> shift is in [12, 23].
  
  45
  >
  	// This extracts the significand for the normalized representation.
  
  46
  >
  	shift := max(bitLen-5, 0)
  
  47
  >
  	sig := int(uval >> uint(shift))
  
  48
  >
  	if sig >= 24 {
  
  49
  >
  		shift++
  
  50
  >
  		sig = int(uval >> uint(shift))
  
  51
  >
  	}
  
  52
  
  53
  >
  	e := shift - compact8offset
  
compact8.go ×2

  54
  >
  
  55
  >
  	if e >= 1 {
  
  56
  >
  		m := sig - 12
  
compact8.go ×2

  57
  >
  		b := e*12 + m
  
  58
  >
  		if b > 255 {
  
  59
  >
  			return 255
  
compact8.go ×1

  60
  >
  		}
  
  61
  >
  		return Compact8(b)
  
compact8.go ×2

  62
  
  	}
  
  63
  
  64
  
  	// Subnormal: value = m << (offset + 1), m in [1, 11]
  
  65
  >
  	m := int(uval >> (compact8offset + 1))
  
compact8.go ×3

  66
  >
  	if m < 1 {
  
  67
  >
  		return 0
  
compact8.go ×1

  68
  >
  	}
  
  69
  >
  	if m > 11 {
  
compact8.go ×3

  70
  
  		m = 11
  
  71
  
  	}
  
  72
  >
  	return Compact8(m)
  
compact8.go ×3

  73
  
  }
  
  74
  
  75
  
  // UpdateCompact8 returns the Compact8 encoding of value, but with hysteresis:
  
  76
  
  // it sticks to prev unless the new code is significantly closer. This prevents
  
  77
  
  // oscillation when the underlying value fluctuates near a bucket boundary.
  
  78
  >
  func UpdateCompact8(value int64, prev Compact8) Compact8 {
  
compact8.go ×1

  79
  >
  	newCode := EncodeCompact8(value)
  
  80
  >
  	if newCode == prev {
  
  81
  >
  		return prev
  
compact8.go ×1

  82
  >
  	}
  
  83
  >
  	newDist := value - DecodeCompact8(newCode) // always >= 0 (round-down)
  
compact8.go ×2

  84
  >
  	oldDist := DecodeCompact8(prev) - value
  
  85
  >
  	if oldDist < 0 {
  
  86
  >
  		oldDist = -oldDist
  
  87
  >
  	}
  
  88
  
  	// Require the new code to be closer by at least half a bucket width
  
  89
  
  	// (at the smaller of the two exponent levels). This shifts the
  
  90
  
  	// transition point from the midpoint to the 3/4 mark of the gap,
  
  91
  
  	// creating a dead zone that prevents chatter.
  
  92
  >
  	e := max(1, min(int(prev/12), int(newCode/12)))
  
compact8.go ×2

  93
  >
  	margin := int64(1) << (e + compact8offset - 1)
  
  94
  >
  	if newDist < oldDist-margin {
  
  95
  >
  		return newCode
  
  96
  >
  	}
  
  97
  >
  	return prev
  
compact8.go ×1

  98
  
  }