uint128.go

     1  // Copyright 2020 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  package netip
     6  
     7  import "math/bits"
     8  
     9  // uint128 represents a uint128 using two uint64s.
    10  //
    11  // When the methods below mention a bit number, bit 0 is the most
    12  // significant bit (in hi) and bit 127 is the lowest (lo&1).
    13  type uint128 struct {
    14  	hi uint64
    15  	lo uint64
    16  }
    17  
    18  // mask6 returns a uint128 bitmask with the topmost n bits of a
    19  // 128-bit number.
    20  func mask6(n int) uint128 {
    21  	return uint128{^(^uint64(0) >> n), ^uint64(0) << (128 - n)}
    22  }
    23  
    24  // isZero reports whether u == 0.
    25  //
    26  // It's faster than u == (uint128{}) because the compiler (as of Go
    27  // 1.15/1.16b1) doesn't do this trick and instead inserts a branch in
    28  // its eq alg's generated code.
    29  func (u uint128) isZero() bool { return u.hi|u.lo == 0 }
    30  
    31  // and returns the bitwise AND of u and m (u&m).
    32  func (u uint128) and(m uint128) uint128 {
    33  	return uint128{u.hi & m.hi, u.lo & m.lo}
    34  }
    35  
    36  // xor returns the bitwise XOR of u and m (u^m).
    37  func (u uint128) xor(m uint128) uint128 {
    38  	return uint128{u.hi ^ m.hi, u.lo ^ m.lo}
    39  }
    40  
    41  // or returns the bitwise OR of u and m (u|m).
    42  func (u uint128) or(m uint128) uint128 {
    43  	return uint128{u.hi | m.hi, u.lo | m.lo}
    44  }
    45  
    46  // not returns the bitwise NOT of u.
    47  func (u uint128) not() uint128 {
    48  	return uint128{^u.hi, ^u.lo}
    49  }
    50  
    51  // subOne returns u - 1.
    52  func (u uint128) subOne() uint128 {
    53  	lo, borrow := bits.Sub64(u.lo, 1, 0)
    54  	return uint128{u.hi - borrow, lo}
    55  }
    56  
    57  // addOne returns u + 1.
    58  func (u uint128) addOne() uint128 {
    59  	lo, carry := bits.Add64(u.lo, 1, 0)
    60  	return uint128{u.hi + carry, lo}
    61  }
    62  
    63  func u64CommonPrefixLen(a, b uint64) uint8 {
    64  	return uint8(bits.LeadingZeros64(a ^ b))
    65  }
    66  
    67  func (u uint128) commonPrefixLen(v uint128) (n uint8) {
    68  	if n = u64CommonPrefixLen(u.hi, v.hi); n == 64 {
    69  		n += u64CommonPrefixLen(u.lo, v.lo)
    70  	}
    71  	return
    72  }
    73  
    74  // halves returns the two uint64 halves of the uint128.
    75  //
    76  // Logically, think of it as returning two uint64s.
    77  // It only returns pointers for inlining reasons on 32-bit platforms.
    78  func (u *uint128) halves() [2]*uint64 {
    79  	return [2]*uint64{&u.hi, &u.lo}
    80  }
    81  
    82  // bitsSetFrom returns a copy of u with the given bit
    83  // and all subsequent ones set.
    84  func (u uint128) bitsSetFrom(bit uint8) uint128 {
    85  	return u.or(mask6(int(bit)).not())
    86  }
    87  
    88  // bitsClearedFrom returns a copy of u with the given bit
    89  // and all subsequent ones cleared.
    90  func (u uint128) bitsClearedFrom(bit uint8) uint128 {
    91  	return u.and(mask6(int(bit)))
    92  }
    93
View as plain text