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 // halves returns the two uint64 halves of the uint128.
64 //
65 // Logically, think of it as returning two uint64s.
66 // It only returns pointers for inlining reasons on 32-bit platforms.
67 func (u *uint128) halves() [2]*uint64 {
68 return [2]*uint64{&u.hi, &u.lo}
69 }
70 71 // bitsSetFrom returns a copy of u with the given bit
72 // and all subsequent ones set.
73 func (u uint128) bitsSetFrom(bit uint8) uint128 {
74 return u.or(mask6(int(bit)).not())
75 }
76 77 // bitsClearedFrom returns a copy of u with the given bit
78 // and all subsequent ones cleared.
79 func (u uint128) bitsClearedFrom(bit uint8) uint128 {
80 return u.and(mask6(int(bit)))
81 }
82