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
|
// RUN: %target-build-swift -Xfrontend -disable-access-control -module-name a %s -o %t.out -O
// RUN: %target-codesign %t.out
// RUN: %target-run %t.out
// REQUIRES: executable_test
import SwiftPrivate
import StdlibUnittest
var HashingTestSuite = TestSuite("Hashing")
func avalancheTest<Input: FixedWidthInteger & UnsignedInteger>(
for type: Input.Type,
_ hashUnderTest: @escaping (Input) -> Int,
_ pValue: Double
) {
typealias Output = Int
let testsInBatch = 100000
let testData = (0 ..< testsInBatch).map { _ in Input.random(in: .min ... .max) }
let testDataHashed = testData.map { hashUnderTest($0) }
for inputBit in 0..<Input.bitWidth {
// Using an array here makes the test too slow.
let bitFlips = UnsafeMutablePointer<Int>.allocate(capacity: Output.bitWidth)
bitFlips.initialize(to: 0, count: Output.bitWidth)
for i in testData.indices {
let inputA = testData[i]
let outputA = testDataHashed[i]
let inputB = inputA ^ (1 << UInt64(inputBit))
let outputB = hashUnderTest(inputB)
var delta = outputA ^ outputB
for outputBit in 0..<Output.bitWidth {
if delta & 1 == 1 {
bitFlips[outputBit] += 1
}
delta = delta >> 1
}
}
for outputBit in 0..<Output.bitWidth {
expectTrue(
chiSquaredUniform2(testsInBatch, bitFlips[outputBit], pValue),
"inputBit: \(inputBit), outputBit: \(outputBit)")
}
bitFlips.deallocate()
}
}
// White-box testing: assume that the other N-bit to N-bit mixing functions
// just dispatch to these. (Avalanche test is relatively expensive.)
HashingTestSuite.test("Hasher.combine(UInt64)/avalanche") {
avalancheTest(for: UInt64.self, _hashValue(for:), 0.02)
}
HashingTestSuite.test("Hasher.combine(UInt32)/avalanche") {
avalancheTest(for: UInt32.self, _hashValue(for:), 0.02)
}
runAllTests()
|
