mirror of
https://github.com/apple/swift.git
synced 2025-12-14 20:36:38 +01:00
97 lines
2.5 KiB
Swift
97 lines
2.5 KiB
Swift
//===--- Walsh.swift ------------------------------------------------------===//
|
|
//
|
|
// This source file is part of the Swift.org open source project
|
|
//
|
|
// Copyright (c) 2014 - 2021 Apple Inc. and the Swift project authors
|
|
// Licensed under Apache License v2.0 with Runtime Library Exception
|
|
//
|
|
// See https://swift.org/LICENSE.txt for license information
|
|
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
import TestsUtils
|
|
#if canImport(Glibc)
|
|
import Glibc
|
|
#elseif canImport(Musl)
|
|
import Musl
|
|
#elseif os(Windows)
|
|
import MSVCRT
|
|
#else
|
|
import Darwin
|
|
#endif
|
|
|
|
public let benchmarks =
|
|
BenchmarkInfo(
|
|
name: "Walsh",
|
|
runFunction: run_Walsh,
|
|
tags: [.validation, .algorithm])
|
|
|
|
func isPowerOfTwo(_ x: Int) -> Bool { return (x & (x - 1)) == 0 }
|
|
|
|
// Fast Walsh Hadamard Transform
|
|
func walshTransform(_ data: inout [Double]) {
|
|
assert(isPowerOfTwo(data.count), "Not a power of two")
|
|
var temp = [Double](repeating: 0, count: data.count)
|
|
let ret = walshImpl(&data, &temp, 0, data.count)
|
|
for i in 0..<data.count {
|
|
data[i] = ret[i]
|
|
}
|
|
}
|
|
|
|
func scale(_ data: inout [Double], _ scalar : Double) {
|
|
for i in 0..<data.count {
|
|
data[i] = data[i] * scalar
|
|
}
|
|
}
|
|
|
|
func inverseWalshTransform(_ data: inout [Double]) {
|
|
walshTransform(&data)
|
|
scale(&data, Double(1)/Double(data.count))
|
|
}
|
|
|
|
func walshImpl(_ data: inout [Double], _ temp: inout [Double], _ start: Int, _ size: Int) -> [Double] {
|
|
if (size == 1) { return data }
|
|
|
|
let stride = size/2
|
|
for i in 0..<stride {
|
|
temp[start + i] = data[start + i + stride] + data[start + i]
|
|
temp[start + i + stride] = data[start + i] - data[start + i + stride]
|
|
}
|
|
|
|
_ = walshImpl(&temp, &data, start, stride)
|
|
return walshImpl(&temp, &data, start + stride, stride)
|
|
}
|
|
|
|
func checkCorrectness() {
|
|
let input: [Double] = [1,0,1,0,0,1,1,0]
|
|
let output: [Double] = [4,2,0,-2,0,2,0,2]
|
|
var data: [Double] = input
|
|
walshTransform(&data)
|
|
let mid = data
|
|
inverseWalshTransform(&data)
|
|
for i in 0..<input.count {
|
|
// Check encode.
|
|
check(abs(data[i] - input[i]) < 0.0001)
|
|
// Check decode.
|
|
check(abs(mid[i] - output[i]) < 0.0001)
|
|
}
|
|
}
|
|
|
|
@inline(never)
|
|
public func run_Walsh(_ n: Int) {
|
|
checkCorrectness()
|
|
|
|
// Generate data.
|
|
var data2 : [Double] = []
|
|
for i in 0..<1024 {
|
|
data2.append(Double(sin(Float(i))))
|
|
}
|
|
|
|
// Transform back and forth.
|
|
for _ in 1...10*n {
|
|
walshTransform(&data2)
|
|
inverseWalshTransform(&data2)
|
|
}
|
|
}
|