How to do reverse memcmp?

Question

How can I do reverse memory comparison? As in, I give the ends of two sequences and I want the pointer to be decremented towards the beginning, not incremented towards the end.

Chemulpo

@VladLazarenko even though this is about comparison and not copying, I guess the answer is the same - hence this could be regarded as a dupe. – Tasman

I actually made a little mistake, I take my vote back, sorry guys – Ustkamenogorsk

Answer 1

There's no built-in function in the C standard library to do it. Here's a simple way to roll your own:

int memrcmp(const void *s1, const void *s2, size_t n)
{
    if(n == 0)
        return 0;

    // Grab pointers to the end and walk backwards
    const unsigned char *p1 = (const unsigned char*)s1 + n - 1;
    const unsigned char *p2 = (const unsigned char*)s2 + n - 1;

    while(n > 0)
    {
        // If the current characters differ, return an appropriately signed
        // value; otherwise, keep searching backwards
        if(*p1 != *p2)
            return *p1 - *p2;
        p1--;
        p2--;
        n--;
    }

    return 0;
}

If you something high-performance, you should compare 4-byte words at a time instead of individual bytes, since memory latency will be the bottleneck; however, that solution is significantly more complex and not really worth it.

Aeniah

should be const unsigned char p1 = (const unsigned char)s1 + n - 1; const unsigned char p2 = (const unsigned char)s2 + n - 1; for example consider n=1. – Tevis

In case someone wants to reverse memcmp for speed-concerns - above loop will likely be only faster for large arrays, because of the optimized machine instructions the non-reversed memcmp may provide. See also: https://mcmap.net/q/226310/-why-is-memcmp-so-much-faster-than-a-for-loop-check – Hescock

Answer 2

Much like in a post (C memcpy in reverse) originally linked by Vlad Lazarenko, here is a solution based on that, that I haven't yet tested but should get you started.

int reverse_memcmp(const void *s1, const void *s2, size_t n)
{
    unsigned char *a, *b;
    a = s1;
    b = s2;
    size_t i = 0;

    // subtracting i from last position and comparing
    for (i = 0; i < n; i++) {
        if (a[n-1-i] != b[n-1-i]) {
            // return differences between different byte, strcmp()-style
            return (a[n-1-i] - b[n-1-i]);
        }
    }

    return 0;
}

Avila

This doesn't compile -- void* pointers cannot be dereferenced. You should instead cast to unsigned char* before dereferencing. – Aeniah

Answer 3

All you need to do is specify your two ends and the size that you'd like to compare, as well as a step size. Please note especially that the step size may be the most important part for getting the expected results. It will greatly ease the implementation if you restrict the sizes. For the size of a char you could do something like:

int compare (void *one, void *two, size_t size)
  {
  char *one_char = (char *)one;
  char *two_char = (char *)two;
  size_t i;

  for (i = 0; i < size; i++)
    {
    if (*(one_char - i) != *(two_char - i))
       return(NOT_EQUAL);
    }  

  return(EQUAL);
  }

Colene

Answer 4

shorter code (C code doesn't need force pointer type cast):

int reverse_memcmp(const void *end1, const void *end2, size_t n) {
    const unsigned char *a = end1, *b = end2;
    for (; n; --n)
        if (*--a != *--b) return *a - *b;
    return 0;
}

Swiftlet