ZFX + Developia

Code: Alles auswählen

inline size_t memFindChar(std::string_view mem, size_t startPosition, char c)
{
    return mem.find(c, startPosition);
}
inline size_t memFindText(std::string_view mem, size_t startPosition, std::string_view txt)
{
    return mem.find(txt, startPosition);
}

*********** string_view::find(char) ******************
--> type_traits::find(char) --> memchr_sse2()

************ string_view::find(str) *******************
template<...> size_type basic_string_view::find(const _CharT* __str, size_type __pos, size_type __n) const noexcept
{
	for (; __pos <= this->_M_len - __n; ++__pos)
		if (traits_type::eq(_M_str_[__pos], __str[0]) && traits_type::compare(_M_str + __pos + 1, __str + 1, __n - 1) == 0)
			return __pos;
}

Code: Alles auswählen

inline size_t memFindChar(std::string_view mem, size_t startPosition, char c)
{
    auto txt = strchr(mem.data() + startPosition, c);
    return txt ? size_t(txt) - size_t(mem.data()) : SIZE_MAX;
}

inline size_t memFindText(std::string_view mem, size_t startPosition, std::string_view txt)
{
    size_t pos = startPosition;
    size_t endPosition = mem.size() - txt.size() + 1;
    while (true) {
        pos = memFindChar(mem, pos, txt[0]);
        if (pos >= endPosition) {
            return SIZE_MAX;
        }
        if (memcmp(mem.data() + pos, txt.data(), txt.size()) == 0) {
            return pos;
        }
        ++pos;
    }
}

Code: Alles auswählen

inline size_t memFindChar(std::string_view mem, size_t startPosition, char c)
{
    const char* readPtr = mem.data() + startPosition;
    const char* endPtr = mem.data() + mem.size();
    uint64_t needleMask = ~(uint64_t(uint8_t(c)) * 0x0101010101010101);
    do {
        uint64_t blob = *((const uint64_t*) readPtr);
        blob = blob ^ needleMask;
        blob = blob & ((blob & 0x7f7f7f7f7f7f7f7f) + 0x0101010101010101);
        blob = blob & 0x8080808080808080;
        if (blob) {
            return size_t(readPtr) - size_t(mem.data()) + _mm_tzcnt_64(blob) / 8;
        }
        readPtr += 8;
    } while (readPtr < endPtr);

    return SIZE_MAX;
}

Code: Alles auswählen

template<...>
pair boyer_moore_searcher<...>::operator()(_RandomAccessIterator2 __first, _RandomAccessIterator2 __last) const
{
	auto __patlen = _M_pat_end - _M_pat;
	const auto& __pred = this->_M_pred();
	__diff_type __i = __patlen - 1;
	auto __stringlen = __last - __first;
	while (__i < __stringlen)
	{
		__diff_type __j = __patlen - 1;
		while (__j >= 0 && __pred(__first[__i], _M_pat[__j]))
		{
			--__i;
		    --__j;
		}
		if (__j < 0)
		{
			const auto __match = __first + __i + 1;
		    return std::make_pair(__match, __match + __patlen);
		}
		__i += std::max(_M_bad_char_shift(__first[__i]),_M_good_suffix[__j]);
	}
    return std::make_pair(__last, __last);
}

Code: Alles auswählen

inline size_t memFindChar(std::string_view mem, size_t startPosition, char c)
{
    const char* readPtr = mem.data() + startPosition;
    const char* endPtr = mem.data() + mem.size();
    auto charMask = _mm_set1_epi8(c);

    do {
        auto blob = _mm_lddqu_si128((const __m128i*) readPtr);
        auto byteEqualityMask = _mm_cmpeq_epi8(blob, charMask);
        auto equalityBits = _mm_movemask_epi8(byteEqualityMask);
        if (equalityBits) {
            return size_t(readPtr) - size_t(mem.data()) + __builtin_ctz(equalityBits);
        }
        readPtr += 16;
    } while (readPtr < endPtr);

    return SIZE_MAX;
}

Code: Alles auswählen

Gesucht:  'f'
CharMask: "ffffffffffffffff"
Speicher: "fluffquifflboeff"
Ergebnis: "x00xx000xx0000xx"

Code: Alles auswählen

inline size_t memFindChar(std::string_view mem, size_t startPosition, char c)
{
	const char* readPtr = mem.data() + startPosition;
    auto endPtr = (size_t) mem.data() + mem.size();
    auto alignedReadPtr = (const __m256i*) (((size_t) readPtr) & ~0x1f);
    auto charMask = _mm256_set1_epi8(c);
    uint8_t misbits = ((size_t) readPtr) & 0x1f;
    uint32_t mismask = ~0u << misbits;

    auto firstChunk = _mm256_load_si256(alignedReadPtr);
    auto bytemask = _mm256_cmpeq_epi8(firstChunk, charMask);
    auto bitmask = _mm256_movemask_epi8(bytemask) & mismask;

    while (!bitmask && (size_t) ++alignedReadPtr < endPtr) {
    	auto chunk = _mm256_load_si256(alignedReadPtr);
    	bytemask = _mm256_cmpeq_epi8(chunk, charMask);
    	bitmask = _mm256_movemask_epi8(bytemask);
    }

    auto resultPos = (size_t) alignedReadPtr - (size_t) mem.data() + __builtin_ctz(bitmask);
    return resultPos >= mem.size() ? SIZE_MAX : resultPos;
}

Code: Alles auswählen

size_t memFindText(std::string_view mem, size_t startPosition, std::string_view txt)
{
    const char* readPtr = mem.data() + startPosition;
    const char* endPtr = mem.data() + mem.size() - txt.size() + 1;

    auto needleBytes = _mm_loadu_si128((const __m128i*) txt.data());
    auto needleLength = std::min(size_t{16}, txt.size());

    while (readPtr < endPtr) {
        auto chunk = _mm_loadu_si128((const __m128i*)readPtr);
        auto index = _mm_cmpestri(needleBytes, needleLength, chunk, 16, _SIDD_UBYTE_OPS | _SIDD_CMP_EQUAL_ORDERED);
        if (index < 16) {
            if (memcmp(readPtr + index, txt.data(), txt.size()) == 0) {
                return (size_t)readPtr - (size_t)mem.data() + index;
            }
            readPtr += index + 1;
        } else {
            readPtr += 16;
        }
    }

    return SIZE_MAX;
}

Code: Alles auswählen

Gesucht:   "</SomeTag>"
Heuhaufen: "8237</Foo> </Som"
Ergebnis:  "0000000000010000"

Code: Alles auswählen

inline size_t memFindText(std::string_view mem, size_t startPosition, std::string_view txt)
{
    static constexpr short MaxFoundIndex = 13; // one past highest position at which the needle can be found
    auto MaxFoundIndexVector = _mm_set1_pi16(MaxFoundIndex); // blown up to x4

    const char* readPtr = mem.data() + startPosition;
    const char* endPtr = mem.data() + mem.size() - txt.size() + 1;

    auto needleBytes = _mm_loadu_si128((const __m128i*) txt.data());
    auto needleLength = std::min(size_t{16}, txt.size());
    auto chunk0 = _mm_loadu_si128((const __m128i*)readPtr);

    while (readPtr < endPtr) {
        auto chunk1 = _mm_loadu_si128((const __m128i*)(readPtr + 16));
        auto chunk2 = _mm_loadu_si128((const __m128i*)(readPtr + 32));
        auto chunk3 = _mm_loadu_si128((const __m128i*)(readPtr + 48));

        // spread out 3x16 byte into 4x12 byte with upper 4 bytes overlapping
        auto chunk00 = chunk0;                              // C0³ C0² C0¹ C0⁰
        auto chunk01 = _mm_alignr_epi8(chunk1, chunk0, 12); // C1² C1¹ C1⁰ C0³
        auto chunk12 = _mm_alignr_epi8(chunk2, chunk1, 8);  // C2¹ C2⁰ C1³ C1²
        auto chunk23 = _mm_alignr_epi8(chunk3, chunk2, 4);  // C3⁰ C2³ C2² C2¹

        auto index0 = _mm_cmpestri(needleBytes, needleLength, chunk00, 16, _SIDD_UBYTE_OPS | _SIDD_CMP_EQUAL_ORDERED);
        auto index1 = _mm_cmpestri(needleBytes, needleLength, chunk01, 16, _SIDD_UBYTE_OPS | _SIDD_CMP_EQUAL_ORDERED);
        auto index2 = _mm_cmpestri(needleBytes, needleLength, chunk12, 16, _SIDD_UBYTE_OPS | _SIDD_CMP_EQUAL_ORDERED);
        auto index3 = _mm_cmpestri(needleBytes, needleLength, chunk23, 16, _SIDD_UBYTE_OPS | _SIDD_CMP_EQUAL_ORDERED);

        auto indexVector = _mm_set_pi16(index3, index2, index1, index0);
        auto compareResult = _mm_cmpgt_pi16(MaxFoundIndexVector, indexVector);
        auto compareMask = _mm_movemask_pi8(compareResult); // there's no _pi16 version, so we make do
        if (compareMask) {
            size_t foundChunkIndex = __builtin_ctz(compareMask) / 2;
            size_t foundChunkPos = ((_mm_cvtm64_si64(indexVector) >> (foundChunkIndex * 16)) & 0xffff);
            size_t foundOffset = foundChunkIndex * 12 + foundChunkPos;
            if (memcmp(readPtr + foundOffset, txt.data(), txt.size()) == 0) {
                return (size_t)readPtr - (size_t)mem.data() + foundOffset;
            }

            // we start searching one past the mismatch, so we need to reinit the first chunk
            readPtr += foundOffset + 1;
            chunk0 = _mm_loadu_si128((const __m128i*)readPtr);
        } else {
            readPtr += 48;
            chunk0 = chunk3;
        }
    }

    return SIZE_MAX;
}