kendall@wjh12.harvard.edu (Samuel C Kendall) (03/09/89)
Consider the following function call:
memcpy(p, p + M, N)
where p is a char*, M is nonnegative, N is positive, and M < N. This
is an overlapping copy, where the bytes are being copied to the left (M
> 0) or onto themselves (M == 0). I am interested in finding out if
this call to memcpy, and similar calls to memccpy, strcpy, and strncpy,
are portable.
I'm interested in practical portability, not theoretical. This call is
obviously illegal, since overlapping copies are forbidden by ANSI and
by the Unix man pages I've seen. However, the copy succeeds in all the
implementations I've tested (Sun, Vax), and it makes sense -- you have
to go out of your way to make this kind of overlap fail. If someone
knows of an implementation where it does fail, please let me know which
implementation it is and how it fails BY MAIL. I'll summarize to the
net if anyone shows interest.
Details: how could this call fail to copy correctly? The
implementations I know copy left-to-right. An implementation that
copied right-to-left would definitely fail. Also, an implementation
that copied in larger-than-byte units, and which couldn't handle
overlapping units, would fail for small M. Finally, an implementation
with run-time checking for this condition would fail.
Our latest version of Saber-C (a C environment with lots of run-time
checking) checks for overlapping copies to the right, but purposely
omits checks for the above cases. I'm trying to figure out if a
"portability mode" should be more stringent.
Sam Kendall kendall%saber@harvard.harvard.edu
Saber Software, Inc. harvard!saber!kendallgwyn@smoke.BRL.MIL (Doug Gwyn ) (03/10/89)
In article <338@wjh12.harvard.edu> kendall%saber@harvard.harvard.edu (Samuel C. Kendall) writes: > memcpy(p, p + M, N) >... overlapping copy, ... >I'm interested in practical portability, not theoretical. There are reasonable implementations of memcpy() for which this will not work as you seems to expect that it should. There are also implemenations for which it will. The answer must be that it isn't practically portable. As to how it could fail, consider the use of vector registers to transfer large chunks in parallel. >Our latest version of Saber-C (a C environment with lots of run-time >checking) checks for overlapping copies to the right, but purposely >omits checks for the above cases. I'm trying to figure out if a >"portability mode" should be more stringent. If the goal is to detect practical portability problems, then I'd say that this is an obvious case to check. But it may be difficult to do the check on some C implementations (e.g. those on segmented architectures), because the two pointers passed to memcpy() need not be comparable.
mark@jhereg.Jhereg.MN.ORG (Mark H. Colburn) (03/10/89)
In article <338@wjh12.harvard.edu> kendall%saber@harvard.harvard.edu (Samuel C. Kendall) writes: >Consider the following function call: > > memcpy(p, p + M, N) > >where p is a char*, M is nonnegative, N is positive, and M < N. This >is an overlapping copy, where the bytes are being copied to the left (M >> 0) or onto themselves (M == 0). I am interested in finding out if >this call to memcpy, and similar calls to memccpy, strcpy, and strncpy, >are portable. This is not particularly portable. There are some problems with overlapping on some impementations. >I'm interested in practical portability, not theoretical. This call is >obviously illegal, since overlapping copies are forbidden by ANSI and >by the Unix man pages I've seen. However, the copy succeeds in all the >implementations I've tested (Sun, Vax), and it makes sense -- you have >to go out of your way to make this kind of overlap fail. If someone >knows of an implementation where it does fail, please let me know which >implementation it is and how it fails BY MAIL. I'll summarize to the >net if anyone shows interest. The ANSI standard does not forbid the call, it just says that the results of the operation on overlapping strings is undefined (read non-portable). The reason for this, obviously, is that some implementation do not support overlapping data on these calls. There is however, another function which is garaunteed to work with overlapping data: memmove(). >Details: how could this call fail to copy correctly? The >implementations I know copy left-to-right. An implementation that >copied right-to-left would definitely fail. Also, an implementation >that copied in larger-than-byte units, and which couldn't handle >overlapping units, would fail for small M. Finally, an implementation >with run-time checking for this condition would fail. It would failt to copy correctly if it copies left to right and the strings look like this in memory (string 1 is the source, string 2 the destination): [----- string 1 -------] [------- string 2 -------] As you could see, the first character of the string, when moved would destroy other stuff in at by the string. Conversely, if it copies right to left: [----- string 1 -------] [------ string 2 -----] Overlapping copies must check to see if there is a possibility that the data would collide when copied, and then choose the correct direction to copy. It is not all that hard, but it takes time. It also may make things slightly more obtuse, but standards generally do, in the name of portability. Attempting to find that all impementations really support a strcpy or memcpy which handles overlapping data is, quite honestly, a waste of time. It is not portable, why bother finding out that most all implementations support it? Would you then use it? It will break on some machine, most likely during your most important demo... Why bother? -- Mark H. Colburn "Look into a child's eye; Minnetech Consulting, Inc. there's no hate and there's no lie; mark@jhereg.mn.org there's no black and there's no white."
david@dhw68k.cts.com (David H. Wolfskill) (03/10/89)
In article <338@wjh12.harvard.edu> kendall%saber@harvard.harvard.edu (Samuel C. Kendall) writes: >[describes an overlapping memcpy() call....] >I am interested in finding out if this call to memcpy, and similar >calls to memccpy, strcpy, and strncpy, are portable. >I'm interested in practical portability, not theoretical. This call is >obviously illegal.... >Details: how could this call fail to copy correctly? The >implementations I know copy left-to-right. An implementation that >copied right-to-left would definitely fail. Well, there exists at least one machine I know of that is designed so the hardware *does* move right-to-left: the IBM System/3 and its descendants (such as the s/36). Furthermore, fields are addressed by their right-most bytes (except for one instruction involving (I think -- it's been several years since I had anything to do with the braindamaged boxes) "editing" numeric quantities for output. Certainly a C compiler (and I have heard reports that a C compiler exists for the s/36 -- though the compiler runs on an IBM-PC, and generates code for the s/36... that probably says something about trying to do anything useful with a s/36....) could mask that behavior from the programmer, but it certainly would not be able to transform such a call to a single "MVC" ("move characters") machine instruction -- and have it do what (I presume) you want. op 1 |||||||||| abcdefghijkl ===> klklklklklkl |||||||||| op 2 is what it *would* do... and if that's what you wanted, that would seem to be OK (if slightly peculiar). (If the difference between the addresses is 1, it is a method of clearing a field so each character has the same value.) The call, as Samuel pointed out, is not legal [p?]ANS C; that was hashed out some time ago. (No, I don't want to go into the discussion again. Suffice it to say that I wanted the compiler/machine's behavior *documented*, rather than just outlawing the call. memmove() supports what you want.) Hope I haven't stirred to many embers up.... :-), david -- David H. Wolfskill uucp: ...{spsd,zardoz,felix}!dhw68k!david InterNet: david@dhw68k.cts.com
meissner@xyzzy.UUCP (Michael Meissner) (03/13/89)
In article <338@wjh12.harvard.edu> kendall%saber@harvard.harvard.edu (Samuel C. Kendall) writes: | Consider the following function call: | | memcpy(p, p + M, N) | | where p is a char*, M is nonnegative, N is positive, and M < N. This | is an overlapping copy, where the bytes are being copied to the left (M | > 0) or onto themselves (M == 0). I am interested in finding out if | this call to memcpy, and similar calls to memccpy, strcpy, and strncpy, | are portable. Ok, if you want a real world example, consider systems based on the Motorola 88000. The chip has multiple functional units, pipelines, and hardware interlocks. When you access memory, there is a minimum of 3 clock periods after the instruction starts before either the register is loaded or memory is stored to. Thus, it is better to do multiple loads, followed by multiple stores to avoid stalling the processor. Thus the inner loop of memcpy would be something like: loop: ld r5,r3,0 ; r5 <- *src ld r6,r3,0x4 ; r6 <- *(src+4) ld r7,r3,0x8 ; r7 <- *(src+8) st r5,r2,0 ; store *src into *dest st r6,r2,0x4 ; store *(src+4) into *(dest+4) st r7,r2,0x8 ; store *(src+8) into *(dest+8) addu r3,r3,0xc ; bump src pointer subu r4,r4,0xc ; decrement length bcnd.n ge0,r4,loop ; loop back if more data to move addu r2,r2,0xc ; bump dest pointer (in delay slot) Thus if M were 4 or 8, and word aligned moves were done, you would lose, since the loads and stores are pipelined three deep. I haven't looked at the library routine for memcpy recently, but I know the authors did go out of their way to exploit the parallelism of the machine. The above code is roughly what the GNU 88k compiler currently produces when it knows word alignment is valid, and that the count is fixed. I would expect even more striking results on machines with vector units, since you should be able to make memcpy use the vector instructions of the machine. -- Michael Meissner, Data General. Uucp: ...!mcnc!rti!xyzzy!meissner Arpa: meissner@dg-rtp.DG.COM (or) meissner%dg-rtp.DG.COM@relay.cs.net