Vectorized · Vectorized · Jun 6, 2025 · Jun 6, 2025 · Jun 6, 2025 · Jun 6, 2025
diff --git a/docs/utils/libsort.md b/docs/utils/libsort.md
@@ -558,4 +558,39 @@ function groupSum(int256[] memory keys, uint256[] memory values)
     pure
 ```
 
-Sorts and uniquifies `keys`. Updates `values` with the grouped sums by key.
+Sorts and uniquifies `keys`. Updates `values` with the grouped sums by key.
+
+### hasDuplicate(uint256[])
+
+```solidity
+function hasDuplicate(uint256[] memory a)
+    internal
+    pure
+    returns (bool result)
+```
+
+Returns if `a` has any duplicate. Does NOT mutate `a`. `O(n)`.
+
+### hasDuplicate(address[])
+
+```solidity
+function hasDuplicate(address[] memory a) internal pure returns (bool)
+```
+
+Returns if `a` has any duplicate. Does NOT mutate `a`. `O(n)`.
+
+### hasDuplicate(bytes32[])
+
+```solidity
+function hasDuplicate(bytes32[] memory a) internal pure returns (bool)
+```
+
+Returns if `a` has any duplicate. Does NOT mutate `a`. `O(n)`.
+
+### hasDuplicate(int256[])
+
+```solidity
+function hasDuplicate(int256[] memory a) internal pure returns (bool)
+```
+
+Returns if `a` has any duplicate. Does NOT mutate `a`. `O(n)`.
diff --git a/src/utils/LibSort.sol b/src/utils/LibSort.sol
@@ -638,6 +638,58 @@ library LibSort {
         groupSum(_toUints(keys), values);
     }
 
+    /// @dev Returns if `a` has any duplicate. Does NOT mutate `a`. `O(n)`.
+    function hasDuplicate(uint256[] memory a) internal pure returns (bool result) {
+        /// @solidity memory-safe-assembly
+        assembly {
+            function p(i_, x_) -> _y {
+                _y := or(shr(i_, x_), x_)
+            }
+            let n := mload(a)
+            if iszero(lt(n, 2)) {
+                let m := mload(0x40) // Use free memory temporarily for hashmap.
+                let w := not(0x1f) // `-0x20`.
+                let c := and(w, p(16, p(8, p(4, p(2, p(1, mul(0x30, n)))))))
+                calldatacopy(m, calldatasize(), add(0x20, c)) // Zeroize hashmap.
+                for { let i := add(a, shl(5, n)) } 1 {} {
+                    // See LibPRNG for explanation of this formula.
+                    let r := mulmod(mload(i), 0x100000000000000000000000000000051, not(0xbc))
+                    // Linear probing.
+                    for {} 1 { r := add(0x20, r) } {
+                        let o := add(m, and(r, c)) // Non-zero pointer into hashmap.
+                        if iszero(mload(o)) {
+                            mstore(o, i) // Store non-zero pointer into hashmap.
+                            break
+                        }
+                        if eq(mload(mload(o)), mload(i)) {
+                            result := 1
+                            i := a // To break the outer loop.
+                            break
+                        }
+                    }
+                    i := add(i, w) // Iterate `a` backwards.
+                    if iszero(lt(a, i)) { break }
+                }
+                if shr(31, n) { invalid() } // Just in case.
+            }
+        }
+    }
+
+    /// @dev Returns if `a` has any duplicate. Does NOT mutate `a`. `O(n)`.
+    function hasDuplicate(address[] memory a) internal pure returns (bool) {
+        return hasDuplicate(_toUints(a));
+    }
+
+    /// @dev Returns if `a` has any duplicate. Does NOT mutate `a`. `O(n)`.
+    function hasDuplicate(bytes32[] memory a) internal pure returns (bool) {
+        return hasDuplicate(_toUints(a));
+    }
+
+    /// @dev Returns if `a` has any duplicate. Does NOT mutate `a`. `O(n)`.
+    function hasDuplicate(int256[] memory a) internal pure returns (bool) {
+        return hasDuplicate(_toUints(a));
+    }
+
     /*´:°•.°+.*•´.*:˚.°*.˚•´.°:°•.°•.*•´.*:˚.°*.˚•´.°:°•.°+.*•´.*:*/
     /*                      PRIVATE HELPERS                       */
     /*.•°:°.´+˚.*°.˚:*.´•*.+°.•°:´*.´•*.•°.•°:°.´:•˚°.*°.˚:*.´+°.•*/

diff --git a/test/LibSort.t.sol b/test/LibSort.t.sol
@@ -1357,4 +1357,94 @@ contract LibSortTest is SoladyTest {
             }
         }
     }
+
+    function testHasDuplicateGas() public {
+        for (uint256 i = 1; i < 1024; i = i * 2) {
+            this._testHasDuplicateGas(i - 1);
+            this._testHasDuplicateGas(i);
+        }
+    }
+
+    function testHasDuplicateOriginalGas() public {
+        for (uint256 i = 1; i < 1024; i = i * 2) {
+            this._testHasDuplicateOriginalGas(i - 1);
+            this._testHasDuplicateOriginalGas(i);
+        }
+    }
+
+    function _testHasDuplicateGas(uint256 n) public {
+        assertEq(LibSort.hasDuplicate(_getTestHasDuplicateGasArray(n)), false);
+    }
+
+    function _testHasDuplicateOriginalGas(uint256 n) public {
+        assertEq(_hasDuplicateOriginal(_getTestHasDuplicateGasArray(n)), false);
+    }
+
+    function _getTestHasDuplicateGasArray(uint256 n) internal returns (uint256[] memory a) {
+        vm.pauseGasMetering();
+        a = new uint256[](n);
+        for (uint256 i; i < n; ++i) {
+            a[i] = i;
+        }
+        vm.resumeGasMetering();
+    }
+
+    function testHasDuplicate(uint256[] memory a, uint256 r) public {
+        if (r & 1 != 0) _brutalizeMemory();
+        if (r & 2 != 0) _misalignFreeMemoryPointer();
+        bool computed = LibSort.hasDuplicate(a);
+        bool expected = _hasDuplicateOriginal(a);
+        assertEq(computed, expected);
+        if (r & 4 != 0) {
+            if (a.length >= 2) {
+                a[_randomUniform() % a.length] = a[_randomUniform() % a.length];
+            }
+            computed = LibSort.hasDuplicate(a);
+            expected = _hasDuplicateOriginal(a);
+            assertEq(computed, expected);
+        }
+    }
+
+    function testHasDuplicate(bytes32) public {
+        testHasDuplicate(_randomUints(_randomArrayLength()), _randomUniform());
+    }
+
+    function _hasDuplicateOriginal(uint256[] memory a) internal pure returns (bool) {
+        uint256[] memory b = LibSort.copy(a);
+        LibSort.sort(b);
+        LibSort.uniquifySorted(b);
+        return b.length != a.length;
+    }
+
+    function testHasDuplicateHashmapCapacityTrick(uint256 n) public pure {
+        n = n & 0x7fffffff;
+        uint256 c;
+        /// @solidity memory-safe-assembly
+        assembly {
+            let w := not(0x1f) // `-0x20`.
+            let t := mul(0x30, n)
+            c := or(shr(1, t), t)
+            c := or(shr(2, c), c)
+            c := or(shr(4, c), c)
+            c := or(shr(8, c), c)
+            c := and(w, or(shr(16, c), c))
+            c := add(0x20, c)
+        }
+        uint256 t = n + (n >> 1);
+        t |= t >> 1;
+        t |= t >> 2;
+        t |= t >> 4;
+        t |= t >> 8;
+        t |= t >> 16;
+        t |= t >> 32;
+        t |= t >> 64;
+        t |= t >> 128;
+        t += 1;
+        t = t << 5;
+        assert(c == t && n >> 31 == 0);
+    }
+
+    function check_HasDuplicateHashmapCapacityTrickEquivalence(uint256 n) public pure {
+        testHasDuplicateHashmapCapacityTrick(n);
+    }
 }