3
\$\begingroup\$

The idea is to convert first 8 character from the C string to uint64_t or uint32_t, then to convert to Big Endian.

The value can be stored and compared with same values and result will be compatible with memcmp or strcmp.

The only exception is if both "strings" are 8 bytes long or 4 bytes long for uint32_t and are equal, the function must return sentinel value, e.g. std::numeric_limits<int>::max(), so caller to know he will need to compare the real strings in order to find the result.

For simplicity, I assume code runs on Little Endian machine and convert to Big Endian is done by __builtin_bswap64 (available on gcc and clang).

Here is the code + some tests

#include <cstdint>
#include <cstring>
#include <limits>

namespace sshhash_implementation{
    constexpr auto bswap(uint64_t x){
        return __builtin_bswap64(x);
    }

    constexpr auto bswap(uint32_t x){
        return __builtin_bswap32(x);
    }

    template<typename T>
    T hash(const char *src){
        constexpr auto capacity = sizeof(T);

        union{
            char    s[capacity];
            T   u = 0;
        };

        strncpy(s, src, capacity);
        return bswap(u);
    }

    template<typename T>
    constexpr T mask(){
        return bswap(T{ 0xFF } << (sizeof(T) - 1) * 8);
    }

    template<typename T>
    int sscmp(T const a, T const b){
        if (a > b)
            return +1;

        if (a < b)
            return -1;

        // equal, check size

        constexpr auto m = mask<T>();

        if ( (a | b) & m )
            return std::numeric_limits<int>::max();

        return 0;
    }
}


template<typename T>
auto sshash(const char *s){
    return sshhash_implementation::hash<T>(s);
}

auto sshash8(const char *s){
    return sshash<uint64_t>(s);
}


auto sshash4(const char *s){
    return sshash<uint32_t>(s);
}

template<typename T>
auto sscmp(T a, T b){
    return sshhash_implementation::sscmp(a, b);
}

auto sscmp8(uint64_t a, uint64_t b){
    return sscmp(a, b);
}

auto sscmp4(uint32_t a, uint32_t b){
    return sscmp(a, b);
}

#include <cstdio>

template<typename T = uint32_t>
void testC(const char *sa, const char *sb, bool const overflow){
    auto const a = sshash<T>(sa);
    auto const b = sshash<T>(sb);

    int const  x = strncmp(sa, sb, sizeof(T));
    int const  y = sscmp(a, b);

    bool const ok = [=](){
        if (overflow)
            return x == 0 && y == std::numeric_limits<int>::max();
        else
            return x == y;
    }();

    printf(
        "%-8s | %-8s | %2d | %2d | %-8s\n",
        sa,
        sb,
        x,
        y,
        ok ? "OK" : "Error"
    );
}

template<typename T = uint32_t>
void test(const char *sa, const char *sb, bool const overflow = false){
    testC(sa, sb, overflow);
    testC(sb, sa, overflow);
}

int main(){
    test("aaa"  , "aaa"     );

    test("aaa"  , "b"       );
    test("aaaa" , "b"       );
    test("aaa"  , "bbbb"    );
    test("aaaa" , "bbbb"    );

    test("aaaa" , "aaaa", true  );
}
\$\endgroup\$
2
\$\begingroup\$

Since we assume GCC or Clang, we can easily make the code adapt to the target's endianness:

#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
    constexpr auto hton(std::uint64_t x){
        return __builtin_bswap64(x);
    }

    constexpr auto hton(std::uint32_t x){
        return __builtin_bswap32(x);
    }
#elif __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
    constexpr auto hton(std::uint64_t x){
        return x;
    }

    constexpr auto hton(std::uint32_t x){
        return x;
    }
#else
#error Unsupported byte order
#endif

I've used the conventional "host to net" name for the function, to be clearer.


Some identifiers are misspelt: std::uint32_t, std::uint64_t, std::strncpy, std::strncmp, std::printf.


This function is unnecessary:

template<typename T>
auto sscmp(T a, T b){
    return sshhash_implementation::sscmp(a, b);
}

Much simpler to write

using sshhash_implementation::sscmp;


No need for the immediately-executed lambda in testC():

bool const ok = [=](){
    if (overflow)
        return x == 0 && y == std::numeric_limits<int>::max();
    else
        return x == y;
}();

That can be written as a simple expression:

bool const ok = overflow
    ? x == 0 && y == std::numeric_limits<int>::max()
    : x == y;

In mask(), I think the constant 8 was intended to be CHAR_BIT, since it's converting a count of char to number of bits.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.