Copying bytes to the same array at different intervals with possible overlap.

[Todd_65536]

How would one write a memmove-like function that copies bytes from one location to another, but at different intervals with either positive or negative values, and... without using a temporary buffer.

For example:

char *my_memmove(char *dst, char *src, size_t num, int dst_interval, int src_interval);

char str[11] = " A B C D E";

my_memmove(src + 9, src + 1, 5, -1, 2);

would result in the contents of str to be

"     EDCBA"

I'm not asking anyone to write me a complete function (although that would be very kind of you,) just a link to a page or a basic idea that'll at least get me started into the right direction.

Thank you.

[grumpy]

Why would you want to?

In any event, the technique would involve a loop. Before entering the loop, check for overlap. If there is overlap then (depending on the manner of overlap) you may need to loop in reverse order.

[Todd_65536]

Yes, detecting for overlap would be the first check, however even during an overlap characters may occupy all, some or none of the overlapping array indexes.

str[11] = "A  B  C   ";

my_memmove(str + 2, str, 3, 2, 2); 

printf("\"%s\"\n", str)

"  A  B  C "

[stahta01]

Why is this the result of your example.

"     EDCBA"

Since following the directions you stated should have gotten this

" A B EDCBA"

Tim S.

[Todd_65536]

Why is this the result of your example.

"     EDCBA"

Since following the directions you stated should have gotten this

" A B EDCBA"

Tim S.

Sorry, Tim. Thanks.

I should also mention that the contents of src may be destroyed, if need be.

[anduril462]

You and Tim agree that the answer should be

" A B EDCBA"

but if this copy is supposed to happen in-place, you would overwrite 'D' in the original string with 'C', on the third character you copy, then when you try to copy the fourth, you would be copying that new 'C' and end up with:

" A B ACCBA"

If, however, you don't want that behavior, you simply need to use a temp array.

[Todd_65536]

If, however, you don't want that behavior, you simply need to use a temp array.

With intervals of -1 and 2, a source string that has four spaces in between five characters is nearly twice as wide as the destination. Could one copy just those characters which do not have similar locations first, then use the copied character's locations (what's already been copied to src) as a temporary buffer in itself?

Again, I'm not concerned about the original contents of the source data. It can be totally mangled. What's important is the final product.

[laserlight]

Just checking: is this a homework assignment?

[Todd_65536]

Just checking: is this a homework assignment?

No... The project involves microcontrollers with 4K RAM.

[anduril462]

With an interval of -1 and 2, a string that has four spaces in between five characters is nearly twice as wide as the destination. Could one copy just those characters which do not have common addresses first, then use the copied character's locations (what's already been copied to src) as a temporary buffer in itself?

Yes, one could, but one would not want to add that much complexity in address calculations, etc, simply to avoid using a temp array. Memory is cheap, make a temp array. It only needs to have room for num bytes.

Again, I'm not concerned about the original contents of the source data. It can be totally mangled. What's important is the final product.

I understand your implementation can alter src. My point was that, given the overlapping condition, you may alter parts of src before they're copied so that dst will no longer appear to contain a copy of src at the specified interval, but instead some arbitrary combination of src characters. So, what should the final product really be in your example?

" A B EDCBA"

or

" A B ACCBA"

You must pick one. It will determine how you implement this.

[laserlight]

No... The project involves microcontrollers with 4K RAM.

Ah. I asked this as an indirect way of asking "has someone solved, or purportedly solved, this problem?"

This is what the C standard has to say about memmove:

The memmove function copies n characters from the object pointed to by s2 into the object pointed to by s1. Copying takes place as if the n characters from the object pointed to by s2 are first copied into a temporary array of n characters that does not overlap the objects pointed to by s1 and s2, and then the n characters from the temporary array are copied into the object pointed to by s1.

My interpretation of "as if" is that while the standard does not mandate the implementation, what it describes is the expected implementation. Consequently, I wonder if this problem actually cannot be solved within the given constraints and with well defined behaviour.

Consider even grumpy's suggestion from post #2: how would you check for overlap? This would require pointer comparison, but pointer comparison results in undefined behaviour if the pointers point to elements in different arrays. Thus, you can only safely do pointer comparison if you define this memmove substutite as valid for moving bytes within an array, not between arrays.

[Todd_65536]

Yes, one could, but one would not want to add that much complexity in address calculations, etc, simply to avoid using a temp array. Memory is cheap, make a temp array. It only needs to have room for num bytes.


I understand your implementation can alter src. My point was that, given the overlapping condition, you may alter parts of src before they're copied so that dst will no longer appear to contain a copy of src at the specified interval, but instead some arbitrary combination of src characters. So, what should the final product really be in your example?

" A B EDCBA"

or

" A B ACCBA"

You must pick one. It will determine how you implement this.

The final contents of str should be this:

"? ? EDCBA"

Where '?' can be anything. Free RAM is not cheap, whether we're dealing with microcontrollers with very limited space or, large individual objects. Memory is cheap until it isn't.

I'm not asking for a replacement to memmove, I'm asking for help with an algorithm that can shuffle data without a temporary buffer. I'll accept a large number of pointer comparisons (or index comparisons) even if it means a drastic reduction in execution speed.

[quzah]

I'm asking for help with an algorithm that can shuffle data without a temporary buffer.

How much space are you talking about here? What is your expected "biggest overlap"? Two pointers is say eight bytes. Can you just use an eight byte buffer instead for segments that over lap?


Quzah.

[Todd_65536]

Thus, you can only safely do pointer comparison if you define this memmove substutite as valid for moving bytes within an array, not between arrays.

For the sake of clarity, my_memmove results in undefined behavior if *dst and *src are in different arrays. For now, I'm only concerned with manipulating a lone series of bytes.

[Todd_65536]

How much space are you talking about here? What is your expected "biggest overlap"? Two pointers is say eight bytes.

The worst case biggest overlap scenario would equal the size of source and destination, for example, reversing a series of a billion bytes in a machine with large available RAM...

my_memmove(str, str + (1 << 30) - 1, (1 << 30), 1, -1);

I would imagine, too, that if this condition were to indeed occur with perhaps src_interval and dst_interval being equal, then the algorithm might resemble that of memmove().

Can you just use an eight byte buffer instead for segments that over lap?

Quzah.

An eight byte buffer doesn't sound like much, does it?