 Memory Copy
This function copies an area of memory. This function is passed two blocks of memory, a target and a source, defined as type char * in C. It is also passed the length of the block to copy.
The copying operation is simple if the source and target do not overlap. However, if they do overlap, the copy has to be done in the correct direction-either starting at the beginning and working forward, or starting at the end and working backward-depending on how they overlap. Otherwise, bytes of data will be copied into some memory locations before the bytes that are currently at those memory locations have been moved where they belong; when the algorithm reaches that point, it will copy the new data, not the old data.
Source Code
1. void
2. copy_memory(
3. char * target,
4. char * source,
5. int length) {
6.
7. char * source_ptr, * source_end, * target_ptr;
8. int step;
9. int done = 0;
10.
11. if (length < 1)
12. return; // nothing to copy, so exit
13.
14. //
15. // Normally copy forward, unless they overlap with
16. // the source being later, in which case we want to
17. // go backwards to avoid the copied bytes
18. // overwriting the source bytes before they are
19. // copied.
20. //
21. if ((target < source) &&
22. ((target + length) > source)) {
23. source_ptr = source + (length-1);
24. source_end = source;
25. target_ptr = target + (length-1);
26. step = -1;
27. } else {
28. source_ptr = source;
29. source_end = source + (length-1);
30. target_ptr = target;
31. step = 1;
32. }
33.
34. //
35. // Now do the copy.
36. //
37. while (1) {
38. if (source_ptr == source_end)
39. done = 1;
40. *target_ptr = *source_ptr;
41. if (done)
42. break;
43. source_ptr += step;
44. target_ptr += step;
45. }
46. }
Suggestions
Consider the local variable done. Where is it used? Is it used correctly? The if on lines 21 and 22 is the heart of the algorithm. Is it correctly calculating whether the buffers overlap? What are the empty, trivial, and already solved inputs to this program? Does the comment on lines 15-19 match the code that follows?
Hints
Walk through the code with the following parameters to the function:
The most basic test is a non-overlapping copy. An array test_buffer[] contains 6 bytes: test_buffer[0] == 0x01 test_buffer[1] == 0x02 test_buffer[2] == 0x03 test_buffer[0] == 0x04 test_buffer[1] == 0x05 test_buffer[2] == 0x06 The function is called as follows: copy_memory(test_buffer, test_buffer+3, 3)
Try an overlapping copy. An array test_buffer[] contains 6 bytes: test_buffer[0] == 0x01 test_buffer[1] == 0x02 test_buffer[2] == 0x03 test_buffer[0] == 0x04 test_buffer[1] == 0x05 test_buffer[2] == 0x06 The function is called as follows: copy_memory(test_buffer, test_buffer+2, 4)
Explanation of the Bug
The logic about when to copy going backward is wrong. The comment on lines 15-19 and the if on lines 21 and 22 are consistent with each other
//
// Normally copy forward, unless they overlap with
// the source being later, in which case we want to
// go backwards to avoid the copied bytes
// overwriting the source bytes before they are
// copied.
//
if ((target < source) &&
((target + length) > source)) {
but they are both incorrect; there is an A.logic error that causes overlapping moves to be incorrect. In fact, the situation in which the copy should be done backward is when the target is later, not the source; so, the code should be changed to swap target and source wherever they appear (and the comment should also be changed):
if ((source < target) &&
((source + length) > target)) {
With the first hint, source and target don't overlap, so the if on line 21 is false and falls through to the else with step set to 1 and the copy proceeding in the forward direction (although it would work fine in the reverse direction because there is no overlap).
With the second, however, source and target do overlap. target is passed as test_buffer, source is test_buffer+2, and length is 4, so the if on lines 21 and 22 is true, resulting in step being set to -1. However, if you unwind the loop on lines 37 to 45, you can see the copy is done wrong:
Iteration 1:
target is test_buffer+3, source is test_buffer+5.
Iteration 2:
target is test_buffer+2, source is test_buffer+4.
Iteration 3:
target is test_buffer+1, source is test_buffer+3.
This is where the bug happens: test_buffer+3 was overwritten in iteration 1, so it does not have its original value. This copy should be done in the forward direction; target later than source is the situation that should be copied in reverse.
| 
