-1

EDIT

I found the memcpy definition has told us about its undefined behavior when target and src has overlap:

The memcpy() function copies n bytes from memory area src to memory area dst. If dst and src overlap, behavior is undefined.Applications in which dst and src might overlap should use memmove(3) instead.

Original Question

I have a simple program that looks like this:

static void RotateLeft(bool *In, int len, int loop) {
    for(int i = 0;i< 28;i++) {
        LOGI("%d -> %d", i, In[i]);
    }
    bool Tmp[256] = {0};
    memcpy(Tmp, In, loop);
    memcpy(In, In + loop, len - loop);

    LOGI("len = %d, loop = %d", len, loop);  // <--- always 28 and 1

    for(int i = 0;i< 28;i++) {
        LOGI("%d -> %d", i, In[i]);  <----- broken
    }

    memcpy(In + len - loop, Tmp, loop);
}


RotateLeft(`bool array`, 28, 1)

It is weird that this program doesn't work right on the arm64-v8a platform (but works well on other platforms):

The input array is something like this:

0 0 0 1 1 1 1 0 1 0 0 1 0 1 ...

The rotated array should be:

0 0 1 1 1 1 0 1 0 0 1 0 1 0...

But it actually outputs:

0 0 1 1 1 1 0 1 0 0 1 1 0 0 ...

UPDATE

Here's how this program allocate array:

bool K[64], *KL=&K[0], *KR=&K[28];

// do something fill `K`

RotateLeft(KR, 28, 1);
WoooHaaaa
  • 19,732
  • 32
  • 90
  • 138
  • 5
    Why not use [`std::rotate`](http://en.cppreference.com/w/cpp/algorithm/rotate)? – NathanOliver May 18 '17 at 16:07
  • 1
    This is an existing project, I want to understand what is going on here, and why its broken. – WoooHaaaa May 18 '17 at 16:14
  • Is "bool array" a string? Or is there another array? – fileyfood500 May 18 '17 at 16:18
  • 1
    What you posted is incomplete, but in your second `memcpy` call source and destination potentially overlap which triggers undefined behavior, http://en.cppreference.com/w/cpp/string/byte/memcpy. – Benjamin Bannier May 18 '17 at 16:23
  • @MrROY *I have a simple program that looks like this:* -- Not so simple, if it were, there would be no issues. Plus `static_assert(sizeof(bool) == 1, "This won't work")` -- Try that anywhere in one of your functions and see if that code even compiles on the platform that it isn't working for. The algorithm functions such as `std::rotate` stops these corner cases and wrong assumptions from becoming an issue. – PaulMcKenzie May 18 '17 at 16:25
  • *Rotate a bool array in C++* -- Using `std::rotate` -- `static void RotateLeft(bool *In, int len, int loop) { std::rotate(In, In + loop, In + len); }` – PaulMcKenzie May 18 '17 at 16:33
  • Thanks guys, `std::rotate` works perfect, but I still don't understand why `memcpy` fails, I printed sizeof(bool), both platforms are `1`. – WoooHaaaa May 18 '17 at 16:40
  • @MrROY -- If the source and destination overlap, then `memcpy` has undefined behavior. – PaulMcKenzie May 18 '17 at 16:47
  • @PaulMcKenzie Yes they have some overlap, but the destination is expected to be overridden and it works on 32-bit platforms. – WoooHaaaa May 18 '17 at 16:55

1 Answers1

1

The underlying assumption for this code is that sizeof(bool) is 1. Unfortunately, this is not guaranteed by the C++ standard as explained in this answer. So your code is completely compiler dependent.

Therefore use std::copy() whenever you can instead of memcpy(). Or use std::rotate() as suggested by NathanOlivier in the comments.

By the way, it's unrelated, but you'd better make sure that loop>=0 && loop<256 && len>=loop if you want to avoid undefined behavior.

Community
  • 1
  • 1
Christophe
  • 68,716
  • 7
  • 72
  • 138
  • Thanks, `std::rotate` works perfect, but I still don't understand why `memcpy` fails, I printed sizeof(bool), both platforms are `1`. – WoooHaaaa May 18 '17 at 16:40
  • Can you show the values of len and loop that you are using, as well as the size of the array, and how you've allocated this array ? – Christophe May 18 '17 at 16:45
  • thanks for your help, I've updated these information. This is a pretty old program, I was just wondering the reason it fails. – WoooHaaaa May 18 '17 at 16:50
  • Don't be fooled by the "this is an old program" stuff. There are plenty of old programs with existing bugs which are either discovered by new, eagle-eyed C++ programmers, or during a port of the program to another platform / compiler and then things fall apart. – PaulMcKenzie May 18 '17 at 16:54
  • Yes, I am trying to port this one to Android, though `std:rotate` saved my life, I still can't understand that. Maybe its time to get over it... – WoooHaaaa May 18 '17 at 16:56
  • Ok, you start at KR, so you're working with K[28]..K[55]. As you don't show the full 28 bytes at that location, I can only guess, that the last digit that is memcopied appears twice because your LOGI display function is before the final memcpy that 't will write the char at the right place. Eg, if you have 0 0 1 and copy to the left the first len-1 bytes, you'll get 0 1 1 (the last 1 is still the original 1). Only after the final memcpy (there's no logging afterwards), will you get 0 1 0 as expected. – Christophe May 18 '17 at 18:00