Update readme, sync with autoformatter
diff --git a/README.md b/README.md index 42c665d..5d2c6bc 100644 --- a/README.md +++ b/README.md
@@ -301,9 +301,9 @@ Given SipHash and HighwayHash provide high quality randomness, depending on expecting attack surface simple non-balancing binary search tree could perform reasonably well. [Wikipedia says](https://en.wikipedia.org/wiki/Binary_search_tree#Definition) -> After a long intermixed sequence of random insertion and deletion, the expected -> height of the tree approaches square root of the number of keys, √n, which grows -> much faster than log n. +> After a long intermixed sequence of random insertion and deletion, the +> expected height of the tree approaches square root of the number of keys, √n, +> which grows much faster than log n. While `O(√n)` is much larger than `O(log n)`, it is still much smaller than `O(n)`. And it will certainly complicate the timing attack, since the time of operation @@ -359,6 +359,9 @@ Frank Wessels & Andreas Auernhammer | Go and ARM assembly | https://github.com/minio/highwayhash Phil Demetriou | Python 3 bindings | https://github.com/kpdemetriou/highwayhash-cffi +> **_NOTE:_** For highwayhash-cffi, please note an [issue](https://github.com/kpdemetriou/highwayhash-cffi/issues/1) +has been reported ([merge request](https://github.com/kpdemetriou/highwayhash-cffi/pull/2)). + ## Modules ### Hashes
diff --git a/highwayhash/arch_specific.cc b/highwayhash/arch_specific.cc index 82d1574..9100c9e 100644 --- a/highwayhash/arch_specific.cc +++ b/highwayhash/arch_specific.cc
@@ -24,8 +24,8 @@ #if __GLIBC__ #include <sys/platform/ppc.h> // __ppc_get_timebase_freq #elif __FreeBSD__ -#include <sys/types.h> #include <sys/sysctl.h> +#include <sys/types.h> #endif #endif @@ -148,9 +148,9 @@ fclose(f); return freq; } - #elif __FreeBSD__ +#elif __FreeBSD__ size_t length = sizeof(freq); - sysctlbyname("dev.cpu.0.freq"), &freq, &length, NULL, 0); + sysctlbyname("dev.cpu.0.freq", &freq, &length, NULL, 0); freq *= 1E6; return freq; #endif @@ -169,12 +169,13 @@ double InvariantTicksPerSecond() { #if HH_ARCH_PPC -#if __GLIBC__ +#if __GLIBC__ static const double cycles_per_second = __ppc_get_timebase_freq(); #elif __FreeBSD__ static double cycles_per_second = 0; size_t length = sizeof(cycles_per_second); - sysctlbyname("kern.timecounter.tc.timebase.frequency", &cycles_per_second, &length, NULL, 0); + sysctlbyname("kern.timecounter.tc.timebase.frequency", &cycles_per_second, + &length, NULL, 0); #endif return cycles_per_second; #else
diff --git a/highwayhash/benchmark.cc b/highwayhash/benchmark.cc index 6b4d1f8..0e497ba 100644 --- a/highwayhash/benchmark.cc +++ b/highwayhash/benchmark.cc
@@ -185,7 +185,8 @@ input_map->num_items = 0; } -#if BENCHMARK_SIP || BENCHMARK_FARM || (BENCHMARK_SIP_TREE && defined(__AVX2__)) +#if BENCHMARK_SIP || BENCHMARK_FARM || BENCHMARK_FP2011 || \ + (BENCHMARK_SIP_TREE && defined(__AVX2__)) void MeasureAndAdd(DurationsForInputs* input_map, const char* caption, const Func func, Measurements* measurements) { @@ -250,6 +251,7 @@ #endif + void AddMeasurements(const std::vector<size_t>& in_sizes, Measurements* measurements) { DurationsForInputs input_map(in_sizes.data(), in_sizes.size(), 40); @@ -267,6 +269,7 @@ MeasureAndAdd(&input_map, "Farm", &RunFarm, measurements); #endif + #if BENCHMARK_HIGHWAY InstructionSets::RunAll<HighwayHashBenchmark>( &input_map, &AddMeasurementsWithPrefix, measurements);
diff --git a/highwayhash/hh_buffer.h b/highwayhash/hh_buffer.h index 8a60f00..7b1dad0 100644 --- a/highwayhash/hh_buffer.h +++ b/highwayhash/hh_buffer.h
@@ -87,7 +87,6 @@ // "prefix", and returns the merged/concatenated bytes. HH_INLINE V4x32U Concatenate(const V4x32U& prefix, const size_t prefix_len, const V4x32U& suffix) { - static const uint64_t table[V16x8U::N][V2x64U::N] = { {0x0706050403020100ull, 0x0F0E0D0C0B0A0908ull}, {0x06050403020100FFull, 0x0E0D0C0B0A090807ull},
diff --git a/highwayhash/hh_neon.cc b/highwayhash/hh_neon.cc index 4d6711b..981c094 100644 --- a/highwayhash/hh_neon.cc +++ b/highwayhash/hh_neon.cc
@@ -16,4 +16,7 @@ // unless they are also restricted. See arch_specific.h for details. #define HH_TARGET_NAME NEON +// GCC 4.5.4 only defines the former; 5.4 defines both. +#if defined(__ARM_NEON__) || defined(__ARM_NEON) #include "highwayhash/highwayhash_target.cc" +#endif
diff --git a/highwayhash/hh_neon.h b/highwayhash/hh_neon.h index ee0989e..9324e13 100644 --- a/highwayhash/hh_neon.h +++ b/highwayhash/hh_neon.h
@@ -33,7 +33,6 @@ namespace highwayhash { - // See vector_neon.h for why this namespace is necessary; matching it here makes // it easier use the vector_neon symbols, but requires textual inclusion. namespace HH_TARGET_NAME { @@ -79,24 +78,19 @@ // In order to do this right now, we would need a switch statement. const int32x4_t vsize_mod32(vdupq_n_s32(static_cast<int32_t>(size_mod32))); // -32 - size_mod32 - const int32x4_t shift_right_amt = vdupq_n_s32(static_cast<int32_t>(size_mod32) + (~32 + 1)); + const int32x4_t shift_right_amt = + vdupq_n_s32(static_cast<int32_t>(size_mod32) + (~32 + 1)); // Equivalent to storing size_mod32 in packet. v0L += V2x64U(vreinterpretq_u64_s32(vsize_mod32)); v0H += V2x64U(vreinterpretq_u64_s32(vsize_mod32)); // Boosts the avalanche effect of mod32. v1L = V2x64U(vreinterpretq_u64_u32( - vorrq_u32( - vshlq_u32(vreinterpretq_u32_u64(v1L), vsize_mod32), - vshlq_u32(vreinterpretq_u32_u64(v1L), shift_right_amt) - ) - )); + vorrq_u32(vshlq_u32(vreinterpretq_u32_u64(v1L), vsize_mod32), + vshlq_u32(vreinterpretq_u32_u64(v1L), shift_right_amt)))); v1H = V2x64U(vreinterpretq_u64_u32( - vorrq_u32( - vshlq_u32(vreinterpretq_u32_u64(v1H), vsize_mod32), - vshlq_u32(vreinterpretq_u32_u64(v1H), shift_right_amt) - ) - )); + vorrq_u32(vshlq_u32(vreinterpretq_u32_u64(v1H), vsize_mod32), + vshlq_u32(vreinterpretq_u32_u64(v1H), shift_right_amt)))); const size_t size_mod4 = size_mod32 & 3; const char* HH_RESTRICT remainder = bytes + (size_mod32 & ~3); @@ -111,11 +105,8 @@ Load3()(Load3::AllowReadBeforeAndReturn(), remainder, size_mod4); // The upper four bytes of packetH are zero, so insert there. - packetH = V2x64U( - vreinterpretq_u64_u32( - vsetq_lane_u32(last4, vreinterpretq_u32_u64(packetH), 3) - ) - ); + packetH = V2x64U(vreinterpretq_u64_u32( + vsetq_lane_u32(last4, vreinterpretq_u32_u64(packetH), 3))); Update(packetH, packetL); } else { // size_mod32 < 16 const V2x64U packetL = LoadMultipleOfFour(bytes, size_mod32); @@ -125,7 +116,7 @@ // Rather than insert into packetL[3], it is faster to initialize // the otherwise empty packetH. - HH_ALIGNAS(16) uint64_t tmp[2] = { last4, 0 }; + HH_ALIGNAS(16) uint64_t tmp[2] = {last4, 0}; const V2x64U packetH(vld1q_u64(tmp)); Update(packetH, packetL); } @@ -209,13 +200,7 @@ private: // Swap 32-bit halves of each lane (caller swaps 128-bit halves) static HH_INLINE V2x64U Rotate64By32(const V2x64U& v) { - return V2x64U( - vreinterpretq_u64_u32( - vrev64q_u32( - vreinterpretq_u32_u64(v) - ) - ) - ); + return V2x64U(vreinterpretq_u64_u32(vrev64q_u32(vreinterpretq_u32_u64(v)))); } static HH_INLINE V2x64U ZipperMerge(const V2x64U& v) { @@ -230,21 +215,13 @@ // be used in the next 32x32 multiplication. // The positions of each byte in the new vector. - const uint8_t shuffle_positions[] = { - 3, 12, 2, 5, 14, 1, 15, 0, - 11, 4, 10, 13, 9, 6, 8, 7 - }; + const uint8_t shuffle_positions[] = {3, 12, 2, 5, 14, 1, 15, 0, + 11, 4, 10, 13, 9, 6, 8, 7}; const uint8x16_t tbl = vld1q_u8(shuffle_positions); // Note: vqtbl1q_u8 is polyfilled for ARMv7a in vector_neon.h. return V2x64U( - vreinterpretq_u64_u8( - vqtbl1q_u8( - vreinterpretq_u8_u64(v), - tbl - ) - ) - ); + vreinterpretq_u64_u8(vqtbl1q_u8(vreinterpretq_u8_u64(v), tbl))); } HH_INLINE void Update(const V2x64U& packetH, const V2x64U& packetL) { @@ -280,7 +257,7 @@ const uint32_t* words = reinterpret_cast<const uint32_t*>(bytes); // Mask of 1-bits where the final 4 bytes should be inserted (replacement // for variable shift/insert using broadcast+blend). - alignas(16) const uint64_t mask_pattern[2] = { 0xFFFFFFFFULL, 0 }; + alignas(16) const uint64_t mask_pattern[2] = {0xFFFFFFFFULL, 0}; V2x64U mask4(vld1q_u64(mask_pattern)); // 'insert' into lane 0 V2x64U ret(vdupq_n_u64(0)); if (size & 8) { @@ -306,7 +283,8 @@ static HH_INLINE void XorByShift128Left12(const V2x64U& x, V2x64U* HH_RESTRICT out) { const V4x32U zero(vdupq_n_u32(0)); - const V2x64U sign_bit128(vreinterpretq_u64_u32(vsetq_lane_u32(0x80000000u, zero, 3))); + const V2x64U sign_bit128( + vreinterpretq_u64_u32(vsetq_lane_u32(0x80000000u, zero, 3))); const V2x64U top_bits2 = x >> (64 - 2); HH_COMPILER_FENCE; const V2x64U shifted1_unmasked = x + x; // (avoids needing port0)
diff --git a/highwayhash/highwayhash_fuzzer.cc b/highwayhash/highwayhash_fuzzer.cc new file mode 100644 index 0000000..af5931d --- /dev/null +++ b/highwayhash/highwayhash_fuzzer.cc
@@ -0,0 +1,25 @@ +#include "highwayhash/highwayhash_target.h" +#include "highwayhash/instruction_sets.h" + +using highwayhash::HHKey; +using highwayhash::HHResult64; +using highwayhash::HighwayHash; +using highwayhash::InstructionSets; + +extern "C" int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { + if (size < sizeof(uint64_t) * 4) { + return 0; + } + + // Generate the key. + const uint64_t *u64s = reinterpret_cast<const uint64_t*>(data); + const HHKey key HH_ALIGNAS(32) = {u64s[0], u64s[1], u64s[2], u64s[3]}; + data += sizeof(uint64_t) * 4; + size -= sizeof(uint64_t) * 4; + + // Compute the hash. + HHResult64 result; + InstructionSets::Run<HighwayHash>(key, reinterpret_cast<const char *>(data), + size, &result); + return 0; +}
diff --git a/highwayhash/highwayhash_test_neon.cc b/highwayhash/highwayhash_test_neon.cc index 2c714e0..df50588 100644 --- a/highwayhash/highwayhash_test_neon.cc +++ b/highwayhash/highwayhash_test_neon.cc
@@ -16,4 +16,7 @@ // unless they are also restricted. See arch_specific.h for details. #define HH_TARGET_NAME NEON +// GCC 4.5.4 only defines the former; 5.4 defines both. +#if defined(__ARM_NEON__) || defined(__ARM_NEON) #include "highwayhash/highwayhash_test_target.cc" +#endif
diff --git a/highwayhash/os_mac.cc b/highwayhash/os_mac.cc index 10d24e7..fd179d8 100644 --- a/highwayhash/os_mac.cc +++ b/highwayhash/os_mac.cc
@@ -14,15 +14,14 @@ // // Created by Alexander Gryanko on 16/09/2017. -#include "os_mac.h" +#include "highwayhash/os_mac.h" int mac_getaffinity(cpu_set_t* set) { int64_t core_count = 0; - size_t core_count_size = sizeof(core_count); // size is a pointer - const int err = sysctlbyname(SYSCTL_CORE_COUNT, &core_count, - &core_count_size, NULL, 0); - if (err != 0) - return err; + size_t core_count_size = sizeof(core_count); // size is a pointer + const int err = + sysctlbyname(SYSCTL_CORE_COUNT, &core_count, &core_count_size, NULL, 0); + if (err != 0) return err; CPU_ZERO(set); for (int64_t i = 0; i < core_count; ++i) { @@ -39,7 +38,7 @@ for (current_core = 0; current_core < NR_CPUS; ++current_core) { if (CPU_ISSET(current_core, set)) break; } - thread_affinity_policy_data_t policy = { current_core }; + thread_affinity_policy_data_t policy = {current_core}; return thread_policy_set(thread, THREAD_AFFINITY_POLICY, - (thread_policy_t)&policy, 1); + (thread_policy_t)&policy, 1); }
diff --git a/highwayhash/os_mac.h b/highwayhash/os_mac.h index 8d8862f..5658b91 100644 --- a/highwayhash/os_mac.h +++ b/highwayhash/os_mac.h
@@ -19,19 +19,19 @@ #ifndef HH_DISABLE_TARGET_SPECIFIC -#include <cstdint> -#include <cstdio> -#include <cstring> -#include <sys/sysctl.h> - #include <mach/mach_types.h> #include <mach/thread_act.h> #include <pthread.h> +#include <sys/sysctl.h> + +#include <cstdint> +#include <cstdio> +#include <cstring> typedef unsigned long int cpu_mask; #define SYSCTL_CORE_COUNT "machdep.cpu.thread_count" -#define NR_CPUS 512 // from the linux kernel limit +#define NR_CPUS 512 // from the linux kernel limit #define NR_CPUBITS (8 * sizeof(cpu_mask)) struct cpu_set_t { @@ -58,5 +58,5 @@ int mac_getaffinity(cpu_set_t* set); int mac_setaffinity(cpu_set_t* set); -#endif // !HH_DISABLE_TARGET_SPECIFIC -#endif // HIGHWAYHASH_OS_MAC_H_ +#endif // !HH_DISABLE_TARGET_SPECIFIC +#endif // HIGHWAYHASH_OS_MAC_H_
diff --git a/highwayhash/os_specific.cc b/highwayhash/os_specific.cc index 589f324..f4f5f66 100644 --- a/highwayhash/os_specific.cc +++ b/highwayhash/os_specific.cc
@@ -40,19 +40,21 @@ #define OS_LINUX 0 #endif -#if defined(__APPLE__) || defined(__MACH__) // __MACH__ also defined for GNU/Hurd +#if defined(__APPLE__) || \ + defined(__MACH__) // __MACH__ also defined for GNU/Hurd #define OS_MAC 1 -#include "os_mac.cc" #include <mach/mach.h> #include <mach/mach_time.h> +// +#include "highwayhash/os_mac.cc" #else #define OS_MAC 0 #endif #ifdef __FreeBSD__ #define OS_FREEBSD 1 -#include <sys/param.h> #include <sys/cpuset.h> +#include <sys/param.h> #include <unistd.h> #else #define OS_FREEBSD 0
diff --git a/highwayhash/sip_hash_fuzzer.cc b/highwayhash/sip_hash_fuzzer.cc new file mode 100644 index 0000000..94a6b1f --- /dev/null +++ b/highwayhash/sip_hash_fuzzer.cc
@@ -0,0 +1,20 @@ +#include "highwayhash/sip_hash.h" + +using highwayhash::HH_U64; +using highwayhash::SipHash; + +extern "C" int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) { + if (size < sizeof(HH_U64) * 2) { + return 0; + } + + // Generate the key. + const HH_U64 *hhU64s = reinterpret_cast<const HH_U64*>(data); + const HH_U64 key[2] HH_ALIGNAS(16) = {hhU64s[0], hhU64s[1]}; + data += sizeof(HH_U64) * 2; + size -= sizeof(HH_U64) * 2; + + // Compute the hash. + SipHash(key, reinterpret_cast<const char*>(data), size); + return 0; +}
diff --git a/highwayhash/vector_neon.h b/highwayhash/vector_neon.h index 02b2686..5b9061f 100644 --- a/highwayhash/vector_neon.h +++ b/highwayhash/vector_neon.h
@@ -33,6 +33,7 @@ #include "highwayhash/arch_specific.h" #include "highwayhash/compiler_specific.h" +#include "highwayhash/hh_types.h" // For auto-dependency generation, we need to include all headers but not their // contents.