Re: Implement memcmp function with help from gcc's inline asm

On Tue, 28 Jun 2005 19:04:03 +0000, Netocrat wrote:
> On Tue, 28 Jun 2005 03:36:53 +0000, Matt wrote:
>> Netocrat wrote:
>>> On Mon, 27 Jun 2005 07:35:36 +0000, Matt wrote:

>>>> My indexing trick works regardless of sign so long as the index is
>>>> the same size as a pointer, and with size_t it is.
>>>
>>> No it doesn't work regardless of sign: it _only_ works when the
>>> variable in question can represent a negative value. The size of
>>> index is irrelevant; only the sign is relevant. I've looked at your
>>> new function and it's still wrong (I haven't compiled or tested it,
>>> but there's no point because it's broken).
>>>
>>> The relevant lines are:
>>> const unsigned int *pia = ((const unsigned int *) a) + ilen; ...
>>> size_t ilen = len / sizeof(int);
>>> ...
>>> for(ilen = 0 - ilen; ilen != 0; ilen++) {
>>> int ia = pia[ilen];
>>>
>>> Consider: ilen is unsigned - we both agree on that. Now your
>>> assignment in the for loop initialiser attempts to reverse the sign of
>>> ilen so that it is now negative. But this is impossible as it is
>>> unsigned, so instead of being set to negative ilen it will be set to a
>>> very large positive number. Now when you index pia with this variable
>>> you are in fact not indexing with a negative value as you intended,
>>> but with a very large postive value. This has nothing to do with
>>> assembly or machine-specific interpretations - it is purely due to how
>>> the C compiler interprets unsigned vs signed integers.
>>
>> It is no coincidence that x86 add & subtract instructions are agnostic
>> to sign. Two's complement forms the basis of x86 processors (and
>> obviously all others)
>
> Minor nit: not all others.
>
>> because the same adder which does unsigned arithmetic does signed
>> arithmetic too. Subtracting 0 - 1 produces the same result whether
>> signed or unsigned. Adding -1*4 to the pointer value likewise produces
>> the same result whether -1 is -1 or 4294957295 (0xFFFFFFFF). Due to
>> arithmatic wrap-around, adding 0x100000000 is the same as adding 0
>> since the result has only 32-bits. Therefore adding 0xFFFFFFFF and then
>> adding 1 should be a no-op. That makes 0xFFFFFFFF semantically
>> identical to -1 which is why they are the same value.
>
> You are correct about the result - I have checked on my machine - but I
> suspect that the reasoning you have provided - which as an explanation
> of the hardware I don't find fault with - is only half the story. The
> compiler interpretation is the other more important part.
>
> I've looked at the C standard and all that it says about signedness is
> that the index must be of integer type. I interpret this to mean that
> the index won't be cast but will be treated as signed or unsigned
> according to its type. Then it is multiplied by the member size of the
> array. In this case as I understand the rules, C is required to convert
> your unsigned llen's -1 value to 49294957295 based on its size of 4
> bytes, regardless of the hardware - although for x86 the hardware does
> the same. When this is used as an index into the array, according to the
> rules of C, it should dereference the memory at address: pia +
> 49294957295 * 4. Obviously though, this results in an overflow of some
> sort since by any rules - compiler or hardware - the result of
> 49294957295 * 4 is too large to fit into either an unsigned int or a
> pointer. So we are encountering overflow behaviour here and I'm not
> sure what the standard requires, but I will take it to comp.lang.c and
> see if anyone knows the answer.
>
> My intuition is that due to the overflow, behaviour can't be predicted
> by the rules of the C and that it just happens to be easiest in such a
> situation for the compiler to leave it to the hardware - in which case
> the reasoning you have given applies.

Quick correction: you have mistyped the 6th digit in the decimal
representation of 0xFFFFFFFF - it is 4294967295 whereas you have
4294957295.

I posted my interpretation to comp.lang.c:
subject: Array subscripting overflow behaviour
message-id: <pan.2005.06.28.19.20.08.239619@xxxxxxxxxxx>

>>From the replies so far it seems that my interpretation is correct -
according to standard C this overflow invokes "undefined behaviour". Of
course the behaviour that actually does occur in this case is exactly as
you described - or to put it another way as Eric Sosman did, conceptually
each overflow "wraps around".

So from a viewpoint of standard C, what you are doing is invalid or at the
least not guaranteed to be portable. From the viewpoint of this
newsgroup, that's probably largely irrelevant because it works on the
hardware that this group deals with. Nevertheless I wanted to document
what led me to my initial incorrect conclusion that your function would
not work as desired, which in retrospect was overly restrictive and should
rather have been that your function was not _guaranteed_ to work as
desired.

.

Relevant Pages

  • Re: signed int overflow
    ... >>How much hardware like that is there? ... and all they have to do is to remember to use a compiler switch ... > hardware that generates an exception on overflow? ... Well such hardware would already have to deal an exception on unsigned ...
    (comp.lang.cpp)
  • Re: Inside an FBI Computer Forensics Lab
    ... properly reproduce or validate a piece of hardware. ... open source tools and well established procedures and methods are used ... like me could trivially design a black box which satisfied every ... possible to create a compiler that will recognizes your code during ...
    (alt.privacy)
  • Re: interesting use of NEXT SENTENCE vs. CONTINUE
    ... ANSI X3.23-1985 has USAGE BINARY. ... If J can be made an independent item which the compiler can put wherever it ... has to be associated with a hardware device in SPECIAL-NAMES. ... the same object code file to share the same instantiations of its code ...
    (comp.lang.cobol)
  • Re: C to Java Byte Code
    ... The actual topic is about creating a Java equivalent for a C program. ... as well have argued that a byte, int, long, float, double can all be ... The values of the compiler depend on the underlying hardware. ...
    (comp.programming)
  • Re: interesting use of NEXT SENTENCE vs. CONTINUE
    ... Program name in quotes (allowed in '02 Standard) ... > If J can be made an independent item which the compiler can put wherever it ... > has to be associated with a hardware device in SPECIAL-NAMES. ... > that ALTER *always* modifies the address parameter of the hardware branch ...
    (comp.lang.cobol)