blob: d330fc7ddc75aea1340082e2aa74cae954bbd790 [file]
// Copyright 2026 Google LLC
// SPDX-License-Identifier: Apache-2.0
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>
#undef HWY_TARGET_INCLUDE
#define HWY_TARGET_INCLUDE "hwy/examples/sum_hex.cc"
#include "hwy/foreach_target.h" // IWYU pragma: keep
#include "hwy/highway.h"
#include "hwy/nanobenchmark.h"
#include "hwy/timer.h"
/*
Highway SIMD Tutorial: Hexadecimal String Summation (Table Lookups & Quad
Accumulate)
This example demonstrates how to efficiently decode a hexadecimal ASCII string
and sum the decoded integer values using SIMD table lookups and quad
accumulate.
Key SIMD techniques shown:
1. Table Lookups (Lookup32): Using a 32-byte lookup table to simultaneously map
ASCII characters ('0'-'9' and 'A'-'F') to their 4-bit nibble values across
vector lanes without conditional branching.
2. Saturated Subtraction (SaturatedSub): Efficiently computing the index into
the lookup table by subtracting the ASCII value of '0' from the input
characters without undederflows.
3. Quad Accumulate (SumOfMulQuadAccumulate): Efficiently accumulating 8-bit
integers into 32-bit integer sums by multiplying with ones and reducing
4x8-bit lanes into 32-bit accumulators to avoid 8-bit overflow.
*/
HWY_BEFORE_NAMESPACE();
namespace hwy {
namespace HWY_NAMESPACE {
namespace {
namespace hn = hwy::HWY_NAMESPACE;
// Sums hex-encoded string.
// Assumes input contains only valid uppercase hex characters ('0'-'9',
// 'A'-'F'). Other characters may produce undefined results (but will not
// crash).
HWY_INLINE int32_t SumHexSIMD(const char* HWY_RESTRICT hex_chars,
size_t count) {
using DI32 = hn::ScalableTag<int32_t>;
using DU8 = hn::Repartition<uint8_t, DI32>;
using DI8 = hn::Repartition<int8_t, DI32>;
const DI32 di32;
const DU8 du8;
const DI8 di8;
using VI32 = hn::Vec<DI32>;
using VU8 = hn::Vec<DU8>;
using VI8 = hn::Vec<DI8>;
const size_t N8 = hn::Lanes(du8);
VI32 sum = hn::Zero(di32);
const VI8 ones = hn::Set(di8, 1);
// Table for Lookup32. Align to 32 bytes for efficient loading.
// Maps indices 0-9 (from '0'-'9') to 0-9, and indices 17-22 (from 'A'-'F')
// to 10-15.
HWY_ALIGN static constexpr uint8_t kTable[32] = {
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 0, 0, 0, 0,
0, 10, 11, 12, 13, 14, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0};
const VU8 char_zero = hn::Set(du8, '0');
auto accumulate = [&](const VU8 v_ascii) HWY_ATTR {
// Saturated sub is available for UINT8 and UINT16 as dedicated instruction.
const VU8 v_idx = hn::SaturatedSub(v_ascii, char_zero);
// Will use either 1 or 2 lookup instructions.
const VU8 decoded = hn::Lookup32(du8, kTable, v_idx);
// This is dedicated instruction that performs
// i32 + i8 * u8 -> i32, allowing for efficient accumulation without
// overflow.
sum = hn::SumOfMulQuadAccumulate(di32, decoded, ones, sum);
};
size_t i = 0;
const uint8_t* HWY_RESTRICT hex_chars_as_int8 =
HWY_RCAST_ALIGNED(const uint8_t*, hex_chars + i);
// Process in blocks of N8
for (; i + N8 <= count; i += N8) {
const VU8 v_ascii =
hn::LoadU(du8, hex_chars_as_int8);
accumulate(v_ascii);
}
// Handle remainder
size_t remainder = count - i;
if (remainder > 0) {
// LoadN pads with 0.
// And thanks to saturated sub, padded elements safely decode as 0.
const VU8 v_ascii = hn::LoadN(
du8, hex_chars_as_int8 + i, remainder);
accumulate(v_ascii);
}
return hn::ReduceSum(di32, sum);
}
} // namespace
} // namespace HWY_NAMESPACE
} // namespace hwy
HWY_AFTER_NAMESPACE();
#if HWY_ONCE
namespace hwy {
HWY_EXPORT(SumHexSIMD);
int32_t CallSumHexSIMD(const char* HWY_RESTRICT hex_chars, size_t count) {
return HWY_DYNAMIC_DISPATCH(SumHexSIMD)(hex_chars, count);
}
int32_t SumHexScalar(const char* hex_chars, size_t count) {
int32_t sum = 0;
for (size_t i = 0; i < count; ++i) {
char c = hex_chars[i];
if (c >= '0' && c <= '9') {
sum += c - '0';
} else if (c >= 'A' && c <= 'F') {
sum += c - 'A' + 10;
}
}
return sum;
}
std::string GenerateHexString(size_t len, size_t offset = 0) {
std::string s;
s.reserve(len);
for (size_t i = 0; i < len; ++i) {
const int r = static_cast<int>((i + offset) % 16);
if (r < 10) {
s += static_cast<char>('0' + r);
} else {
s += static_cast<char>('A' + (r - 10));
}
}
return s;
}
bool TestOne(const std::string& test_str) {
int32_t expected = SumHexScalar(test_str.data(), test_str.length());
int32_t actual = CallSumHexSIMD(test_str.data(), test_str.length());
if (expected != actual) {
printf("Failed for \"%s\" (len %zu): expected %d, got %d\n",
test_str.c_str(), test_str.length(), expected, actual);
return false;
}
return true;
}
int RunTests() {
std::vector<std::string> test_cases;
// Generate some random hex strings of various lengths, including edge cases
for (size_t len :
{0, 2, 3, 7, 15, 16, 17, 31, 32, 33, 63, 64, 65, 1000, 1001}) {
test_cases.push_back(GenerateHexString(len));
}
bool all_passed = true;
for (const auto& tc : test_cases) {
if (!TestOne(tc)) {
all_passed = false;
}
}
if (!all_passed) {
printf("Validation FAILED!\n");
return 1;
}
printf("Validation PASSED.\n");
// Benchmark
const size_t bench_len = 10'000;
const int reps = 10'000;
// Use Unpredictable1 to ensure the string content is not known at compile
// time
const std::string bench_str =
GenerateHexString(bench_len, hwy::Unpredictable1());
printf("Benchmarking with string of length %zu (%d reps)...\n", bench_len,
reps);
const double t_scalar_0 = hwy::platform::Now();
int32_t scalar_sum = 0;
for (int r = 0; r < reps; ++r) {
scalar_sum += SumHexScalar(bench_str.data(), bench_len);
}
const double t_scalar_1 = hwy::platform::Now();
const double dt_scalar = t_scalar_1 - t_scalar_0;
const double t_simd_0 = hwy::platform::Now();
int32_t simd_sum = 0;
for (int r = 0; r < reps; ++r) {
simd_sum += CallSumHexSIMD(bench_str.data(), bench_len);
}
const double t_simd_1 = hwy::platform::Now();
const double dt_simd = t_simd_1 - t_simd_0;
// Print results to ensure they are not optimized away
printf("Scalar sum: %d (took %f seconds)\n", scalar_sum, dt_scalar);
printf("SIMD sum: %d (took %f seconds, speedup: %fx)\n", simd_sum, dt_simd,
dt_scalar / dt_simd);
return 0;
}
} // namespace hwy
int main() { return hwy::RunTests(); }
#endif // HWY_ONCE