In data Mon, 15 Oct 2007 18:23:54 -0700, Peter Nilsson scrisse:
>Tor Rustad <tor_rus...@hotmail.com> wrote:
>> Richard Heathfield wrote:
>> > > What about the non-trivial case, where buffers overlap?
>> >
>> > I'm not entirely sure this can be done in standard C, at
>> > least not the obvious way, although I'd be glad to be proved
>> > wrong.
>>
>> Hmm.. haven't written it before, my first try would be:
>>
>> /* pre-condition: checking for overlapped objects */
>> N = strlen(s);
>> for (i=0; i<N; i++) {
>> for (j=0; j<N; j++)
>> assert(t + i != s + j);
>>
>> }
>
>Slightly less Grossly InEfficient ...
>
> /* test: if n bytes starting at s
> // overlaps n bytes starting at t
> */
> int mem_overlap(const void *s, const void *t, size_t n)
> {
> const char *u, *v;
> size_t m = n;
> if (n == 0) return (s == t);
> for (u = t; m--; u++) if (u == s) return 1;
> for (v = s; n--; v++) if (v == t) return 1;
> return 0;
> }


/* test: if n bytes starting at s
// overlaps n bytes starting at t
*/
/* assume a pointer has the same size of an int and one unsigned */
/* return 1 if error or overlap 0 otherwise */
int mem_overlap123(char* s, int n, char* t, int m)
{if(s==0|| t==0 || n<0 || m<0) return 0;

/* no array can have the address 0
if( ((int)s)>=0 &&((int)(s+n-1))<= 0) return 1;
if( ((int)t)>=0 &&((int)(t+n-1))<= 0) return 1;

if( ((int)s)<=0 &&((int)(s+n-1))>= 0) return 1;
if( ((int)t)<=0 &&((int)(t+n-1))>= 0) return 1;

/* s----- t------ || t----- s------*/
if( (unsigned)(s+n-1) < (unsigned) t) return 0;
if( (unsigned)(t+m-1) < (unsigned) s) return 0;
return 1;
}

not tested
how many errors do you see?

>
> /* test: if destination s
> // overlaps source string t
> */
> int str_overlap(const char *s, const char *t)
> {
> const char *u = t;
> do { if (u == s) return 1; } while (*u++);
> while (--u != t) if (++s == t) return 1;
> return 0;
> }

¬a/b wrote:
....
> /* test: if n bytes starting at s
> // overlaps n bytes starting at t
> */
> /* assume a pointer has the same size of an int and one unsigned */
> /* return 1 if error or overlap 0 otherwise */
> int mem_overlap123(char* s, int n, char* t, int m)
> {if(s==0|| t==0 || n<0 || m<0) return 0;
>
> /* no array can have the address 0
> if( ((int)s)>=0 &&((int)(s+n-1))<= 0) return 1;
> if( ((int)t)>=0 &&((int)(t+n-1))<= 0) return 1;
>
> if( ((int)s)<=0 &&((int)(s+n-1))>= 0) return 1;
> if( ((int)t)<=0 &&((int)(t+n-1))>= 0) return 1;
>
> /* s----- t------ || t----- s------*/
> if( (unsigned)(s+n-1) < (unsigned) t) return 0;
> if( (unsigned)(t+m-1) < (unsigned) s) return 0;
> return 1;
> }
>
> not tested
> how many errors do you see?


You use 'n' in every location where I would have expected you to use
'm'. Why have a fourth argument if you're going to ignore it?

I'd recommend const-qualifying the pointer arguments, using size_t for
the integer arguments, and I find your coding style hard to read and
hard to debug, but those aren't errors.

This code is based upon two non-portable assumptions that you document
in the comments, but it also depends upon some additional unportable
assumptions that you don't document. You assume that because an
integer type has the same size as a pointer, a pointer will converted
to a unique value of that type; while it is certainly possible to
implement pointer->int conversions that way, and indeed likely,
tthere's no obligation for an implementation to do so. This is what
intptr_t and uintptr_t are for - use them, and do compile-time
checking with #error to verify that they exist.

You assume that it is possible to convert a pointer into an integer,
and then derive meaningful information about that pointer by examining
the integer's value. In particular, you seem to be assuming that a
null pointer will convert to an integer with a value of 0, and that
the order of two such integers tells you something useful about the
order of the positions in memory pointed at by the corresponding
pointers.

There are probably implementations where all of the non-portable
assumptions you make are true, but there are also ones where they are
not.

In data Wed, 17 Oct 2007 17:00:13 +0200, ¬a\/b scrisse:

> /* test: if n bytes starting at s
> // overlaps n bytes starting at t
> */
>/* assume a pointer has the same size of an int and one unsigned */
>/* return 1 if error or overlap 0 otherwise */
>int mem_overlap123(char* s, int n, char* t, int m)
>{if(s==0|| t==0 || n<0 || m<0) return 0;
^^^^^^^^^^^^^

return 1

> /* no array can have the address 0
> if( ((int)s)>=0 &&((int)(s+n-1))<= 0) return 1;

> if( ((int)t)>=0 &&((int)(t+n-1))<= 0) return 1;
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

if( ((int)t)>=0 &&((int)(t+m-1))<= 0) return 1;

> if( ((int)s)<=0 &&((int)(s+n-1))>= 0) return 1;
> if( ((int)t)<=0 &&((int)(t+n-1))>= 0) return 1;
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

if( ((int)t)<=0 &&((int)(t+m-1))>= 0) return 1;

> /* s----- t------ || t----- s------*/
> if( (unsigned)(s+n-1) < (unsigned) t) return 0;
> if( (unsigned)(t+m-1) < (unsigned) s) return 0;
> return 1;
>}
>
>not tested
>how many errors do you see?

In data 17 Oct 2007 13:56:19 -0700, jameskuyper@verizon.net scrisse:
>¬a/b wrote:
>...
>> /* test: if n bytes starting at s
>> // overlaps n bytes starting at t
>> */

/* test: if n bytes starting at s
// overlaps m bytes starting at t
*/

>> /* assume a pointer has the same size of an int and one unsigned */
>> /* return 1 if error or overlap 0 otherwise */
>> int mem_overlap123(char* s, int n, char* t, int m)
>> {if(s==0|| t==0 || n<0 || m<0) return 0;
>>
>> /* no array can have the address 0
>> if( ((int)s)>=0 &&((int)(s+n-1))<= 0) return 1;
>> if( ((int)t)>=0 &&((int)(t+n-1))<= 0) return 1;
>>
>> if( ((int)s)<=0 &&((int)(s+n-1))>= 0) return 1;
>> if( ((int)t)<=0 &&((int)(t+n-1))>= 0) return 1;
>>
>> /* s----- t------ || t----- s------*/
>> if( (unsigned)(s+n-1) < (unsigned) t) return 0;
>> if( (unsigned)(t+m-1) < (unsigned) s) return 0;
>> return 1;
>> }
>>
>> not tested
>> how many errors do you see?
>
>
>You use 'n' in every location where I would have expected you to use
>'m'. Why have a fourth argument if you're going to ignore it?
>
>I'd recommend const-qualifying the pointer arguments, using size_t for
>the integer arguments, and I find your coding style hard to read and
>hard to debug, but those aren't errors.

i do not use const because it make difficult the language

>This code is based upon two non-portable assumptions that you document
>in the comments, but it also depends upon some additional unportable
>assumptions that you don't document. You assume that because an
>integer type has the same size as a pointer, a pointer will converted
>to a unique value of that type; while it is certainly possible to
>implement pointer->int conversions that way, and indeed likely,
>tthere's no obligation for an implementation to do so. This is what
>intptr_t and uintptr_t are for - use them, and do compile-time
>checking with #error to verify that they exist.

yes. why the standard not say that sizeof(unsigned int) == sizeof(int)
== sizeof(char*)?
for me one memory object can not be > INT_MAX chars

>You assume that it is possible to convert a pointer into an integer,
>and then derive meaningful information about that pointer by examining
>the integer's value. In particular, you seem to be assuming that a
>null pointer will convert to an integer with a value of 0, and that
>the order of two such integers tells you something useful about the
>order of the positions in memory pointed at by the corresponding
>pointers.

yes i assume they are all numbers in the same integer type seen like a
circumference

>There are probably implementations where all of the non-portable
>assumptions you make are true, but there are also ones where they are
>not.

¬a\/b wrote:
> In data 17 Oct 2007 13:56:19 -0700, jameskuyper@verizon.net scrisse:
....
> yes. why the standard not say that sizeof(unsigned int) == sizeof(int)
> == sizeof(char*)?

Section 6.2.5p6 requires sizeof(unsigned int) == sizeof(int). It's only
sizeof(char*) which is not required to match.

> for me one memory object can not be > INT_MAX chars

It's arguable (and has frequently been argued) whether the standard's
description of sizeof() implicitly guarantees that you cannot statically
or automatically allocate an object whose size is greater than SIZE_MAX.
It's far less clear whether you can apply the same argument to objects
dynamically allocated using calloc(). In any event, the standard says
nothing that limits the size to INT_MAX. On every implementation I've
ever used, SIZE_MAX (or the pre-C99 equivalent, ((size_t)-1) ) has been
at least twice as big as INT_MAX. That's not a C standard requirement,
just an observation.

One of the key goals of the C standard is to define the language
sufficiently loosely that it can be efficiently implemented on just
about any hardware. As a result, C has been implemented (often with
fairly good efficiency) on just about everything.

Imposing the requirements you suggest would make efficient
implementation of C on many platforms more difficult. I've used machines
where 16 bits was the most reasonable size for 'int', which had a LOT
more than 65536 bytes of memory installed. I'm certain that there will
be machines in the future (I wouldn't be surprised if they already
exist) where the natural size for an integer is 32 bits, which have far
more than 4GB of memory installed.

Other languages have different goals. In Java, efficiency of
implementation (and even implementability itself), is sacrificed, if
need be, to make it easier to write portable code. There's a place for
both types of languages, but C is, by design, a language where programs
are efficiently portable, rather than easily portable.

....
>> You assume that it is possible to convert a pointer into an integer,
>> and then derive meaningful information about that pointer by examining
>> the integer's value. In particular, you seem to be assuming that a
>> null pointer will convert to an integer with a value of 0, and that
>> the order of two such integers tells you something useful about the
>> order of the positions in memory pointed at by the corresponding
>> pointers.
>
> yes i assume they are all numbers in the same integer type seen like a
> circumference

Obviously they are numbers, and they all have the same integer type,
since you cast them to that type. It's the other assumptions you've made
that are unportable. I have no idea what the word "circumference" is
doing in that sentence, and therefore have no idea what that part of the
sentence means. I can assure you that each of the assumptions I referred
to is seriously non-portable.

¬a\/b wrote:
> In data Wed, 17 Oct 2007 17:00:13 +0200, ¬a\/b scrisse:
>
>> /* test: if n bytes starting at s
>> // overlaps n bytes starting at t

// overlaps m bytes starting at t

This is why I prefer to put each parameter on a separate line, and to
add a short comment describing that parameter on the same line. That
makes it easier to keep the comments consistent with the parameters.

In data Thu, 18 Oct 2007 08:07:58 +0200, ¬a\/b scrisse:

>In data Wed, 17 Oct 2007 17:00:13 +0200, ¬a\/b scrisse:
>
>> /* test: if n bytes starting at s
>> // overlaps n bytes starting at t

// overlaps m bytes starting at t


>> */

>>/* assume a pointer has the same size of an int and one unsigned */
>>/* return 1 if error or overlap 0 otherwise */
>>int mem_overlap123(char* s, int n, char* t, int m)
>>{if(s==0|| t==0 || n<0 || m<0) return 0;
> ^^^^^^^^^^^^^
>
>return 1
>
>> /* no array can have the address 0
>> if( ((int)s)>=0 &&((int)(s+n-1))<= 0) return 1;
>
>> if( ((int)t)>=0 &&((int)(t+n-1))<= 0) return 1;
>^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^
>
>if( ((int)t)>=0 &&((int)(t+m-1))<= 0) return 1;
>
>> if( ((int)s)<=0 &&((int)(s+n-1))>= 0) return 1;
>> if( ((int)t)<=0 &&((int)(t+n-1))>= 0) return 1;
>^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^
>
>if( ((int)t)<=0 &&((int)(t+m-1))>= 0) return 1;

there is anhother error
the 'singular' points are two 0 and INT_MAX
--0 == -1 ++INT_MAX!=0

>> /* s----- t------ || t----- s------*/
>> if( (unsigned)(s+n-1) < (unsigned) t) return 0;
>> if( (unsigned)(t+m-1) < (unsigned) s) return 0;
>> return 1;
>>}
>>
>>not tested
>>how many errors do you see?

In data Fri, 19 Oct 2007 08:49:43 +0200, ¬a\/b scrisse:

/* test: if n bytes starting at s
// overlaps m bytes starting at t
*/

#define uns unsigned

/* assume a pointer has the same size of one unsigned */
/* return 1 if error or overlap 0 otherwise
if you like uns == size_t
*/
int mem_overlap123(char* s, int n, char* t, int m)
{if(s==0|| t==0) return 1;

/* s and t can not go trhu 0 address */
/* s----- t------- */
if((uns)(s+n-1) < (uns) s) return 1;
if((uns)(t+m-1) < (uns) t) return 1;


/* overlap */
/* s----- t------ || t----- s------*/
if( (uns)(s+n-1) < (uns) t) return 0;
if( (uns)(t+m-1) < (uns) s) return 0;

return 1;
}