1 // Copyright 2022 Google LLC
2 // SPDX-License-Identifier: Apache-2.0
4 // Licensed under the Apache License, Version 2.0 (the "License");
5 // you may not use this file except in compliance with the License.
6 // You may obtain a copy of the License at
8 // http://www.apache.org/licenses/LICENSE-2.0
10 // Unless required by applicable law or agreed to in writing, software
11 // distributed under the License is distributed on an "AS IS" BASIS,
12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 // See the License for the specific language governing permissions and
14 // limitations under the License.
16 // Per-target include guard
17 #if defined(HIGHWAY_HWY_CONTRIB_ALGO_FIND_INL_H_) == \
18 defined(HWY_TARGET_TOGGLE)
19 #ifdef HIGHWAY_HWY_CONTRIB_ALGO_FIND_INL_H_
20 #undef HIGHWAY_HWY_CONTRIB_ALGO_FIND_INL_H_
22 #define HIGHWAY_HWY_CONTRIB_ALGO_FIND_INL_H_
25 #include "hwy/highway.h"
27 HWY_BEFORE_NAMESPACE();
29 namespace HWY_NAMESPACE {
31 // Returns index of the first element equal to `value` in `in[0, count)`, or
32 // `count` if not found.
33 template <class D, typename T = TFromD<D>>
34 size_t Find(D d, T value, const T* HWY_RESTRICT in, size_t count) {
35 const size_t N = Lanes(d);
36 const Vec<D> broadcasted = Set(d, value);
39 for (; i + N <= count; i += N) {
40 const intptr_t pos = FindFirstTrue(d, Eq(broadcasted, LoadU(d, in + i)));
41 if (pos >= 0) return i + static_cast<size_t>(pos);
45 #if HWY_MEM_OPS_MIGHT_FAULT
46 // Scan single elements.
47 const CappedTag<T, 1> d1;
48 using V1 = Vec<decltype(d1)>;
49 const V1 broadcasted1 = Set(d1, GetLane(broadcasted));
50 for (; i < count; ++i) {
51 if (AllTrue(d1, Eq(broadcasted1, LoadU(d1, in + i)))) {
56 const size_t remaining = count - i;
57 HWY_DASSERT(0 != remaining && remaining < N);
58 const Mask<D> mask = FirstN(d, remaining);
59 const Vec<D> v = MaskedLoad(mask, d, in + i);
60 // Apply mask so that we don't 'find' the zero-padding from MaskedLoad.
61 const intptr_t pos = FindFirstTrue(d, And(Eq(broadcasted, v), mask));
62 if (pos >= 0) return i + static_cast<size_t>(pos);
63 #endif // HWY_MEM_OPS_MIGHT_FAULT
66 return count; // not found
69 // Returns index of the first element in `in[0, count)` for which `func(d, vec)`
70 // returns true, otherwise `count`.
71 template <class D, class Func, typename T = TFromD<D>>
72 size_t FindIf(D d, const T* HWY_RESTRICT in, size_t count, const Func& func) {
73 const size_t N = Lanes(d);
76 for (; i + N <= count; i += N) {
77 const intptr_t pos = FindFirstTrue(d, func(d, LoadU(d, in + i)));
78 if (pos >= 0) return i + static_cast<size_t>(pos);
82 #if HWY_MEM_OPS_MIGHT_FAULT
83 // Scan single elements.
84 const CappedTag<T, 1> d1;
85 for (; i < count; ++i) {
86 if (AllTrue(d1, func(d1, LoadU(d1, in + i)))) {
91 const size_t remaining = count - i;
92 HWY_DASSERT(0 != remaining && remaining < N);
93 const Mask<D> mask = FirstN(d, remaining);
94 const Vec<D> v = MaskedLoad(mask, d, in + i);
95 // Apply mask so that we don't 'find' the zero-padding from MaskedLoad.
96 const intptr_t pos = FindFirstTrue(d, And(func(d, v), mask));
97 if (pos >= 0) return i + static_cast<size_t>(pos);
98 #endif // HWY_MEM_OPS_MIGHT_FAULT
101 return count; // not found
104 // NOLINTNEXTLINE(google-readability-namespace-comments)
105 } // namespace HWY_NAMESPACE
107 HWY_AFTER_NAMESPACE();
109 #endif // HIGHWAY_HWY_CONTRIB_ALGO_FIND_INL_H_