// Copyright 2008 Google Inc. All Rights Reserved.

//

// Fast memory copying and comparison routines.

//   strings::fastmemcmp_inlined() replaces memcmp()

//   strings::memcpy_inlined() replaces memcpy()

//   strings::memeq(a, b, n) replaces memcmp(a, b, n) == 0

//

// strings::*_inlined() routines are inline versions of the

// routines exported by this module.  Sometimes using the inlined

// versions is faster.  Measure before using the inlined versions.

//

// Performance measurement:

//   strings::fastmemcmp_inlined

//     Analysis: memcmp, fastmemcmp_inlined, fastmemcmp

//     2012-01-30

#pragma once

#include <stddef.h>

#include <stdint.h>

#include <stdio.h>

#include <string.h>

#include "gutil/integral_types.h"

#include "gutil/port.h"

namespace strings {

// Return true if the n bytes at a equal the n bytes at b.

// The regions are allowed to overlap.

//

// The performance is similar to the performance memcmp(), but faster for

// moderately-sized inputs, or inputs that share a common prefix and differ

// somewhere in their last 8 bytes. Further optimizations can be added later

// if it makes sense to do so.

inline bool memeq(const void* a_v, const void* b_v, size_t n) {

    const uint8_t* a = reinterpret_cast<const uint8_t*>(a_v);

    const uint8_t* b = reinterpret_cast<const uint8_t*>(b_v);

    size_t n_rounded_down = n & ~static_cast<size_t>(7);

    if (PREDICT_FALSE(n_rounded_down == 0)) { // n <= 7

        return memcmp(a, b, n) == 0;

    }

    // n >= 8

    uint64 u = UNALIGNED_LOAD64(a) ^ UNALIGNED_LOAD64(b);

    uint64 v = UNALIGNED_LOAD64(a + n - 8) ^ UNALIGNED_LOAD64(b + n - 8);

    if ((u | v) != 0) { // The first or last 8 bytes differ.

        return false;

    }

    a += 8;

    b += 8;

    n = n_rounded_down - 8;

    if (n > 128) {

        // As of 2012, memcmp on x86-64 uses a big unrolled loop with SSE2

        // instructions, and while we could try to do something faster, it

        // doesn't seem worth pursuing.

        return memcmp(a, b, n) == 0;

    }

    for (; n >= 16; n -= 16) {

        uint64 x = UNALIGNED_LOAD64(a) ^ UNALIGNED_LOAD64(b);

        uint64 y = UNALIGNED_LOAD64(a + 8) ^ UNALIGNED_LOAD64(b + 8);

        if ((x | y) != 0) {

            return false;

        }

        a += 16;

        b += 16;

    }

    // n must be 0 or 8 now because it was a multiple of 8 at the top of the loop.

    return n == 0 || UNALIGNED_LOAD64(a) == UNALIGNED_LOAD64(b);

}

inline int fastmemcmp_inlined(const void* a_void, const void* b_void, size_t n) {

    const uint8_t* a = reinterpret_cast<const uint8_t*>(a_void);

    const uint8_t* b = reinterpret_cast<const uint8_t*>(b_void);

    if (n >= 64) {

        return memcmp(a, b, n);

    }

    const void* a_limit = a + n;

    const size_t sizeof_uint64 = sizeof(uint64); // NOLINT(runtime/sizeof)

    while (a + sizeof_uint64 <= a_limit && UNALIGNED_LOAD64(a) == UNALIGNED_LOAD64(b)) {

        a += sizeof_uint64;

        b += sizeof_uint64;

    }

    const size_t sizeof_uint32 = sizeof(uint32); // NOLINT(runtime/sizeof)

    if (a + sizeof_uint32 <= a_limit && UNALIGNED_LOAD32(a) == UNALIGNED_LOAD32(b)) {

        a += sizeof_uint32;

        b += sizeof_uint32;

    }

    while (a < a_limit) {

        int d = static_cast<uint32>(*a++) - static_cast<uint32>(*b++);

        if (d) return d;

    }

    return 0;

}

// The standard memcpy operation is slow for variable small sizes.

// This implementation inlines the optimal realization for sizes 1 to 16.

// To avoid code bloat don't use it in case of not performance-critical spots,

// nor when you don't expect very frequent values of size <= 16.

inline void memcpy_inlined(void* dst, const void* src, size_t size) {

    // Compiler inlines code with minimal amount of data movement when third

    // parameter of memcpy is a constant.

    switch (size) {

    case 1:

        memcpy(dst, src, 1);

        break;

    case 2:

        memcpy(dst, src, 2);

        break;

    case 3:

        memcpy(dst, src, 3);

        break;

    case 4:

        memcpy(dst, src, 4);

        break;

    case 5:

        memcpy(dst, src, 5);

        break;

    case 6:

        memcpy(dst, src, 6);

        break;

    case 7:

        memcpy(dst, src, 7);

        break;

    case 8:

        memcpy(dst, src, 8);

        break;

    case 9:

        memcpy(dst, src, 9);

        break;

    case 10:

        memcpy(dst, src, 10);

        break;

    case 11:

        memcpy(dst, src, 11);

        break;

    case 12:

        memcpy(dst, src, 12);

        break;

    case 13:

        memcpy(dst, src, 13);

        break;

    case 14:

        memcpy(dst, src, 14);

        break;

    case 15:

        memcpy(dst, src, 15);

        break;

    case 16:

        memcpy(dst, src, 16);

        break;

    default:

        memcpy(dst, src, size);

        break;

    }

}

} // namespace strings