1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.15;
import "src/libraries/DisputeTypes.sol";
/// @title LibPosition
/// @notice This library contains helper functions for working with the `Position` type.
library LibPosition {
/// @notice Computes a generalized index (2^{depth} + indexAtDepth).
/// @param _depth The depth of the position.
/// @param _indexAtDepth The index at the depth of the position.
/// @return position_ The computed generalized index.
function wrap(uint64 _depth, uint64 _indexAtDepth) internal pure returns (Position position_) {
assembly {
// gindex = 2^{_depth} + _indexAtDepth
position_ := add(shl(_depth, 1), _indexAtDepth)
}
}
/// @notice Pulls the `depth` out of a `Position` type.
/// @param _position The generalized index to get the `depth` of.
/// @return depth_ The `depth` of the `position` gindex.
/// @custom:attribution Solady <https://github.com/Vectorized/Solady>
function depth(Position _position) internal pure returns (uint64 depth_) {
// Return the most significant bit offset, which signifies the depth of the gindex.
assembly {
depth_ := or(depth_, shl(6, lt(0xffffffffffffffff, shr(depth_, _position))))
depth_ := or(depth_, shl(5, lt(0xffffffff, shr(depth_, _position))))
// For the remaining 32 bits, use a De Bruijn lookup.
_position := shr(depth_, _position)
_position := or(_position, shr(1, _position))
_position := or(_position, shr(2, _position))
_position := or(_position, shr(4, _position))
_position := or(_position, shr(8, _position))
_position := or(_position, shr(16, _position))
depth_ :=
or(
depth_,
byte(
shr(251, mul(_position, shl(224, 0x07c4acdd))),
0x0009010a0d15021d0b0e10121619031e080c141c0f111807131b17061a05041f
)
)
}
}
/// @notice Pulls the `indexAtDepth` out of a `Position` type.
/// The `indexAtDepth` is the left/right index of a position at a specific depth within
/// the binary tree, starting from index 0. For example, at gindex 2, the `depth` = 1
/// and the `indexAtDepth` = 0.
/// @param _position The generalized index to get the `indexAtDepth` of.
/// @return indexAtDepth_ The `indexAtDepth` of the `position` gindex.
function indexAtDepth(Position _position) internal pure returns (uint64 indexAtDepth_) {
// Return bits p_{msb-1}...p_{0}. This effectively pulls the 2^{depth} out of the gindex,
// leaving only the `indexAtDepth`.
uint256 msb = depth(_position);
assembly {
indexAtDepth_ := sub(_position, shl(msb, 1))
}
}
/// @notice Get the left child of `_position`.
/// @param _position The position to get the left position of.
/// @return left_ The position to the left of `position`.
function left(Position _position) internal pure returns (Position left_) {
assembly {
left_ := shl(1, _position)
}
}
/// @notice Get the right child of `_position`
/// @param _position The position to get the right position of.
/// @return right_ The position to the right of `position`.
function right(Position _position) internal pure returns (Position right_) {
assembly {
right_ := or(1, shl(1, _position))
}
}
/// @notice Get the parent position of `_position`.
/// @param _position The position to get the parent position of.
/// @return parent_ The parent position of `position`.
function parent(Position _position) internal pure returns (Position parent_) {
assembly {
parent_ := shr(1, _position)
}
}
/// @notice Get the deepest, right most gindex relative to the `position`. This is equivalent to
/// calling `right` on a position until the maximum depth is reached.
/// @param _position The position to get the relative deepest, right most gindex of.
/// @param _maxDepth The maximum depth of the game.
/// @return rightIndex_ The deepest, right most gindex relative to the `position`.
function rightIndex(Position _position, uint256 _maxDepth) internal pure returns (Position rightIndex_) {
uint256 msb = depth(_position);
assembly {
let remaining := sub(_maxDepth, msb)
rightIndex_ := or(shl(remaining, _position), sub(shl(remaining, 1), 1))
}
}
/// @notice Get the deepest, right most trace index relative to the `position`. This is
/// equivalent to calling `right` on a position until the maximum depth is reached and
/// then finding its index at depth.
/// @param _position The position to get the relative trace index of.
/// @param _maxDepth The maximum depth of the game.
/// @return traceIndex_ The trace index relative to the `position`.
function traceIndex(Position _position, uint256 _maxDepth) internal pure returns (uint256 traceIndex_) {
uint256 msb = depth(_position);
assembly {
let remaining := sub(_maxDepth, msb)
traceIndex_ := sub(or(shl(remaining, _position), sub(shl(remaining, 1), 1)), shl(_maxDepth, 1))
}
}
/// @notice Gets the position of the highest ancestor of `_position` that commits to the same
/// trace index.
/// @param _position The position to get the highest ancestor of.
/// @return ancestor_ The highest ancestor of `position` that commits to the same trace index.
function traceAncestor(Position _position) internal pure returns (Position ancestor_) {
// Create a field with only the lowest unset bit of `_position` set.
Position lsb;
assembly {
lsb := and(not(_position), add(_position, 1))
}
// Find the index of the lowest unset bit within the field.
uint256 msb = depth(lsb);
// The highest ancestor that commits to the same trace index is the original position
// shifted right by the index of the lowest unset bit.
assembly {
let a := shr(msb, _position)
// Bound the ancestor to the minimum gindex, 1.
ancestor_ := or(a, iszero(a))
}
}
/// @notice Get the move position of `_position`, which is the left child of:
/// 1. `_position + 1` if `_isAttack` is true.
/// 1. `_position` if `_isAttack` is false.
/// @param _position The position to get the relative attack/defense position of.
/// @param _isAttack Whether or not the move is an attack move.
/// @return move_ The move position relative to `position`.
function move(Position _position, bool _isAttack) internal pure returns (Position move_) {
assembly {
move_ := shl(1, or(iszero(_isAttack), _position))
}
}
}