Portable replacement

Discussion in 'C Programming' started by Noob, Apr 28, 2008.

  1. Noob

    Noob Guest

    Hello,

    I've rewritten a function (greater_or_equal) that relies on
    implementation-defined behavior and availability of exact-width
    integers, with the goal of making the new implementation
    (greater_or_equal2) portable across any platform.

    What do you think of the new implementation?
    (Suggestions and comments are welcome.)

    int greater_or_equal(uint16_t u, uint16_t v)
    {
    return (int16_t)(u-v) >= 0;
    }

    int greater_or_equal2(unsigned u, unsigned v)
    {
    return ((u-v) & 0xffffU) <= 0x7fffU;
    }

    <OT>
    GCC seems to "understand" the source as it outputs the following code.

    greater_or_equal2:
    movl 8(%esp), %edx
    cmpw %dx, 4(%esp)
    setns %al
    movzbl %al, %eax
    ret
    </OT>

    Regards.
     
    Noob, Apr 28, 2008
    #1
    1. Advertising

  2. On Apr 28, 10:38 am, Noob <root@localhost> wrote:
    > Hello,
    >
    > I've rewritten a function (greater_or_equal) that relies on
    > implementation-defined behavior and availability of exact-width
    > integers, with the goal of making the new implementation
    > (greater_or_equal2) portable across any platform.
    >
    > What do you think of the new implementation?
    > (Suggestions and comments are welcome.)
    >
    > int greater_or_equal(uint16_t u, uint16_t v)
    > {
    >    return (int16_t)(u-v) >= 0;
    >
    > }
    >
    > int greater_or_equal2(unsigned u, unsigned v)
    > {
    >    return ((u-v) & 0xffffU) <= 0x7fffU;
    >
    > }
    >
    > <OT>
    > GCC seems to "understand" the source as it outputs the following code.
    >
    > greater_or_equal2:
    >      movl    8(%esp), %edx
    >      cmpw    %dx, 4(%esp)
    >      setns   %al
    >      movzbl  %al, %eax
    >      ret
    > </OT>
    >
    > Regards.


    You still use a 2 byte mask, what if unsigned u represents 32 bits?

    Suresh M. Shenoy
     
    suresh shenoy, Apr 28, 2008
    #2
    1. Advertising

  3. Noob

    Guest

    On 28 Apr., 19:58, pete <> wrote:
    > Noob wrote:
    > > Hello,

    >
    > > I've rewritten a function (greater_or_equal) that relies on
    > > implementation-defined behavior and availability of exact-width
    > > integers, with the goal of making the new implementation
    > > (greater_or_equal2) portable across any platform.

    >
    > > What do you think of the new implementation?
    > > (Suggestions and comments are welcome.)

    >
    > > int greater_or_equal(uint16_t u, uint16_t v)
    > > {
    > > return (int16_t)(u-v) >= 0;
    > > }

    >
    > > int greater_or_equal2(unsigned u, unsigned v)
    > > {
    > > return ((u-v) & 0xffffU) <= 0x7fffU;
    > > }

    >
    > > <OT>
    > > GCC seems to "understand" the source as it outputs the following code.

    >
    > > greater_or_equal2:
    > > movl 8(%esp), %edx
    > > cmpw %dx, 4(%esp)
    > > setns %al
    > > movzbl %al, %eax
    > > ret
    > > </OT>

    >
    > I can't help but wonder, what code does it output for:
    >
    > int greater_or_equal3(unsigned u, unsigned v)
    > {
    > return u >= v;
    >
    > }


    Maybe the code of the OP will be used in a obfuscated
    C contest...

    Greetings Thomas Mertes

    Seed7 Homepage: http://seed7.sourceforge.net
    Seed7 - The extensible programming language: User defined statements
    and operators, abstract data types, templates without special
    syntax, OO with interfaces and multiple dispatch, statically typed,
    interpreted or compiled, portable, runs under linux/unix/windows.
     
    , Apr 28, 2008
    #3
  4. Noob

    Thad Smith Guest

    Noob wrote:
    > Hello,
    >
    > I've rewritten a function (greater_or_equal) that relies on
    > implementation-defined behavior and availability of exact-width
    > integers, with the goal of making the new implementation
    > (greater_or_equal2) portable across any platform.
    >
    > What do you think of the new implementation?
    > (Suggestions and comments are welcome.)
    >
    > int greater_or_equal(uint16_t u, uint16_t v)
    > {
    > return (int16_t)(u-v) >= 0;
    > }
    >
    > int greater_or_equal2(unsigned u, unsigned v)
    > {
    > return ((u-v) & 0xffffU) <= 0x7fffU;
    > }


    Neither implementation is correct without an exact definition of what it
    does. A function that evaluates greater_or_equal2(60000,0) as 0 would be
    surprising to me without a definition to the contrary.

    --
    Thad
     
    Thad Smith, Apr 29, 2008
    #4
  5. Noob

    Noob Guest

    Thad Smith wrote:

    > Noob wrote:
    >
    >> I've rewritten a function (greater_or_equal) that relies on
    >> implementation-defined behavior and availability of exact-width
    >> integers, with the goal of making the new implementation
    >> (greater_or_equal2) portable across any platform.
    >>
    >> What do you think of the new implementation?
    >> (Suggestions and comments are welcome.)
    >>
    >> int greater_or_equal(uint16_t u, uint16_t v)
    >> {
    >> return (int16_t)(u-v) >= 0;
    >> }
    >>
    >> int greater_or_equal2(unsigned u, unsigned v)
    >> {
    >> return ((u-v) & 0xffffU) <= 0x7fffU;
    >> }

    >
    > Neither implementation is correct without an exact definition of what it
    > does. A function that evaluates greater_or_equal2(60000,0) as 0 would
    > be surprising to me without a definition to the contrary.


    (I agree that I have given these functions unintuitive names, but
    I didn't ask whether the two implementations were correct.)

    What matters to me is whether the two implementations are equivalent.
    That is, given identical input, do they produce identical output?
    (The range of legal values for u and v is that of an uint16_t,
    i.e. 0 to 65535.)

    I should have named the two functions foo1 and foo2, and asked:
    "Are foo1 and foo2 equivalent? and is foo2 portable?"

    int foo1(uint16_t u, uint16_t v)
    {
    return (int16_t)(u-v) >= 0;
    }

    int foo2(unsigned u, unsigned v)
    {
    return ((u-v) & 0xffffU) <= 0x7fffU;
    }

    For those wondering what they're supposed to compute, I provided
    more details in an earlier thread.

    Message-ID: <480f0d58$0$5410$>
    http://groups.google.com/group/comp.lang.c/browse_frm/thread/dceeb7c981bf2113

    For example, 2 is considered "greater than" 65530, because there is
    a high probability that 2 is, in fact, 65538 in disguise.

    Regards.
     
    Noob, Apr 29, 2008
    #5
  6. Noob

    Noob Guest

    Suresh wrote:

    > Noob wrote:
    >
    >> I've rewritten a function (greater_or_equal) that relies on
    >> implementation-defined behavior and availability of exact-width
    >> integers, with the goal of making the new implementation
    >> (greater_or_equal2) portable across any platform.
    >>
    >> What do you think of the new implementation?
    >> (Suggestions and comments are welcome.)
    >>
    >> int greater_or_equal(uint16_t u, uint16_t v)
    >> {
    >> return (int16_t)(u-v) >= 0;
    >> }
    >>
    >> int greater_or_equal2(unsigned u, unsigned v)
    >> {
    >> return ((u-v) & 0xffffU) <= 0x7fffU;
    >> }

    >
    > You still use a 2 byte mask,


    I think you wrote "byte" where you meant "octet" :)

    > what if unsigned u represents 32 bits?


    I don't understand the question. What did you mean?

    The range of legal values for u and v is that of an uint16_t
    i.e. 0 to 65535.

    Regards.
     
    Noob, Apr 29, 2008
    #6
  7. Noob

    Noob Guest

    pete wrote:

    > Noob wrote:
    >
    >> I've rewritten a function (greater_or_equal) that relies on
    >> implementation-defined behavior and availability of exact-width
    >> integers, with the goal of making the new implementation
    >> (greater_or_equal2) portable across any platform.
    >>
    >> What do you think of the new implementation?
    >> (Suggestions and comments are welcome.)
    >>
    >> int greater_or_equal(uint16_t u, uint16_t v)
    >> {
    >> return (int16_t)(u-v) >= 0;
    >> }
    >>
    >> int greater_or_equal2(unsigned u, unsigned v)
    >> {
    >> return ((u-v) & 0xffffU) <= 0x7fffU;
    >> }
    >>
    >> <OT>
    >> GCC seems to "understand" the source as it outputs the following code.
    >>
    >> greater_or_equal2:
    >> movl 8(%esp), %edx
    >> cmpw %dx, 4(%esp)
    >> setns %al
    >> movzbl %al, %eax
    >> ret
    >> </OT>

    >
    > I can't help but wonder, what code does it output for:
    >
    > int greater_or_equal3(unsigned u, unsigned v)
    > {
    > return u >= v;
    > }


    Why are you wondering?

    greater_or_equal3:
    movl 8(%esp), %edx
    cmpl %edx, 4(%esp)
    setae %al
    movzbl %al, %eax
    ret

    But this is irrelevant, as greater_or_equal3 is /not/ equivalent
    to greater_or_equal2. (It doesn't deal with wrap-around.)

    Consider u=65000 and v=10

    greater_or_equal2(65000, 10) returns 0.
    greater_or_equal3(65000, 10) returns 1.

    Regards.
     
    Noob, Apr 29, 2008
    #7
  8. Noob

    Noob Guest

    Thomas Mertes wrote:

    > Maybe the code of the OP will be used in a obfuscated C contest...


    It is real code, used in a production environment.
     
    Noob, Apr 29, 2008
    #8
  9. Noob <root@localhost> writes:
    <snip>
    > I should have named the two functions foo1 and foo2, and asked:
    > "Are foo1 and foo2 equivalent? and is foo2 portable?"
    >
    > int foo1(uint16_t u, uint16_t v)
    > {
    > return (int16_t)(u-v) >= 0;
    > }
    >
    > int foo2(unsigned u, unsigned v)
    > {
    > return ((u-v) & 0xffffU) <= 0x7fffU;
    > }


    There is one difference (which I though had already been pointed out,
    but I may be miss-remembering) which is that in foo1, u-v may not be
    representable as in int16_t, so the conversion is either undefined or,
    implementation defined depending on which C standard one is using.

    --
    Ben.
     
    Ben Bacarisse, Apr 29, 2008
    #9
  10. Noob

    Noob Guest

    Ben Bacarisse wrote:

    > Noob wrote:
    >
    >> I should have named the two functions foo1 and foo2, and asked:
    >> "Are foo1 and foo2 equivalent? and is foo2 portable?"
    >>
    >> int foo1(uint16_t u, uint16_t v)
    >> {
    >> return (int16_t)(u-v) >= 0;
    >> }
    >>
    >> int foo2(unsigned u, unsigned v)
    >> {
    >> return ((u-v) & 0xffffU) <= 0x7fffU;
    >> }

    >
    > There is one difference (which I though had already been pointed out,
    > but I may be miss-remembering) which is that in foo1, u-v may not be
    > representable as in int16_t, so the conversion is either undefined or,
    > implementation defined depending on which C standard one is using.


    I've already pointed out that foo1 relies on impl-defined behavior.
    In fact, that is the very reason why I wrote foo2.

    The problem statement was:

    <quote>
    I've rewritten a function that relies on implementation-defined
    behavior and availability of exact-width integers, with the goal
    of making the new implementation portable across any platform.
    </quote>

    On a related subject, I don't think the conversion to int16_t is
    ever undefined. (AFAIU, both C89 and C99 say it is impl-defined.)

    Regards.
     
    Noob, Apr 29, 2008
    #10
  11. Noob

    Thad Smith Guest

    Noob wrote:
    > Thad Smith wrote:
    >
    >> Noob wrote:
    >>
    >>> I've rewritten a function (greater_or_equal) that relies on
    >>> implementation-defined behavior and availability of exact-width
    >>> integers, with the goal of making the new implementation
    >>> (greater_or_equal2) portable across any platform.
    >>>
    >>> What do you think of the new implementation?
    >>> (Suggestions and comments are welcome.)
    >>>
    >>> int greater_or_equal(uint16_t u, uint16_t v)
    >>> {
    >>> return (int16_t)(u-v) >= 0;
    >>> }
    >>>
    >>> int greater_or_equal2(unsigned u, unsigned v)
    >>> {
    >>> return ((u-v) & 0xffffU) <= 0x7fffU;
    >>> }

    >>
    >> Neither implementation is correct without an exact definition of what
    >> it does. A function that evaluates greater_or_equal2(60000,0) as 0
    >> would be surprising to me without a definition to the contrary.

    >
    > (I agree that I have given these functions unintuitive names, but
    > I didn't ask whether the two implementations were correct.)
    >
    > What matters to me is whether the two implementations are equivalent.
    > That is, given identical input, do they produce identical output?
    > (The range of legal values for u and v is that of an uint16_t,
    > i.e. 0 to 65535.)


    For the cases that are well-defined by the standard, the results appear
    identical. If they give the results you want for the
    implementation-defined situations, then you have a good replacement.

    --
    Thad
     
    Thad Smith, Apr 29, 2008
    #11
  12. Noob <root@localhost> writes:

    > Ben Bacarisse wrote:
    >
    >> Noob wrote:
    >>
    >>> I should have named the two functions foo1 and foo2, and asked:
    >>> "Are foo1 and foo2 equivalent? and is foo2 portable?"
    >>>
    >>> int foo1(uint16_t u, uint16_t v)
    >>> {
    >>> return (int16_t)(u-v) >= 0;
    >>> }
    >>>
    >>> int foo2(unsigned u, unsigned v)
    >>> {
    >>> return ((u-v) & 0xffffU) <= 0x7fffU;
    >>> }

    >>
    >> There is one difference (which I though had already been pointed out,
    >> but I may be miss-remembering) which is that in foo1, u-v may not be
    >> representable as in int16_t, so the conversion is either undefined or,
    >> implementation defined depending on which C standard one is using.

    >
    > I've already pointed out that foo1 relies on impl-defined behavior.
    > In fact, that is the very reason why I wrote foo2.


    Ah, right. I thought you were asking a new question.

    > On a related subject, I don't think the conversion to int16_t is
    > ever undefined. (AFAIU, both C89 and C99 say it is impl-defined.)


    Yes, you are right. For some reason, I though the conversion to int
    was undefined in C89 (as it is from floating types) but it is indeed
    only implementation defined.

    To address your question... I'd like to be definitive, but I have no
    "calculus" for covering all the possible options. It looks the same,
    (assuming one typical behaviour for the implementation-defined cases)
    but you know that already. I can't prove it.

    --
    Ben.
     
    Ben Bacarisse, Apr 29, 2008
    #12
  13. Noob

    Guest

    On 29 Apr., 11:10, Noob <root@localhost> wrote:
    > pete wrote:
    > > Noob wrote:

    >
    > >> I've rewritten a function (greater_or_equal) that relies on
    > >> implementation-defined behavior and availability of exact-width
    > >> integers, with the goal of making the new implementation
    > >> (greater_or_equal2) portable across any platform.

    >
    > >> What do you think of the new implementation?
    > >> (Suggestions and comments are welcome.)

    >
    > >> int greater_or_equal(uint16_t u, uint16_t v)
    > >> {
    > >> return (int16_t)(u-v) >= 0;
    > >> }

    >
    > >> int greater_or_equal2(unsigned u, unsigned v)
    > >> {
    > >> return ((u-v) & 0xffffU) <= 0x7fffU;
    > >> }

    >
    > >> <OT>
    > >> GCC seems to "understand" the source as it outputs the following code.

    >
    > >> greater_or_equal2:
    > >> movl 8(%esp), %edx
    > >> cmpw %dx, 4(%esp)
    > >> setns %al
    > >> movzbl %al, %eax
    > >> ret
    > >> </OT>

    >
    > > I can't help but wonder, what code does it output for:

    >
    > > int greater_or_equal3(unsigned u, unsigned v)
    > > {
    > > return u >= v;
    > > }

    >
    > Why are you wondering?
    >
    > greater_or_equal3:
    > movl 8(%esp), %edx
    > cmpl %edx, 4(%esp)
    > setae %al
    > movzbl %al, %eax
    > ret
    >
    > But this is irrelevant, as greater_or_equal3 is /not/ equivalent
    > to greater_or_equal2. (It doesn't deal with wrap-around.)
    >
    > Consider u=65000 and v=10
    >
    > greater_or_equal2(65000, 10) returns 0.
    > greater_or_equal3(65000, 10) returns 1.


    Maybe greater_or_equal3 returns 1 because 65000 is
    greater than or equal 10.

    Can it be that your function has unsigned parameters,
    but you really want to do a signed comparison.
    What about something like:

    int greater_or_equal4 (unsigned u, unsigned v)
    {
    return ((int) u) >= ((int) v);
    }

    that way greater_or_equal4(65000, 10) would return 0
    (at least when the size of int and unsigned is 2).

    Greetings Thomas Mertes

    Seed7 Homepage: http://seed7.sourceforge.net
    Seed7 - The extensible programming language: User defined statements
    and operators, abstract data types, templates without special
    syntax, OO with interfaces and multiple dispatch, statically typed,
    interpreted or compiled, portable, runs under linux/unix/windows.
     
    , Apr 29, 2008
    #13
  14. Noob

    Noob Guest

    Thomas Mertes wrote:

    > What about something like:
    >
    > int greater_or_equal4 (unsigned u, unsigned v)
    > {
    > return ((int) u) >= ((int) v);
    > }
    >
    > that way greater_or_equal4(65000, 10) would return 0
    > (at least when the size of int and unsigned is 2).


    For the record, the original functions, renamed foo1 and foo2
    to prevent people from focusing on their result.

    int foo1(uint16_t u, uint16_t v)
    {
    return (int16_t)(u-v) >= 0;
    }

    int foo2(unsigned u, unsigned v)
    {
    return ((u-v) & 0xffffU) <= 0x7fffU;
    }

    On my platform, foo1 and foo2 are equivalent.
    My claim is that foo2 is portable, while foo1 is not.

    greater_or_equal4 is not equivalent to foo2.
    (Consider u=32000 and v=33000)

    greater_or_equal4 has even worse shortcomings than foo1, as it
    requires int and unsigned int to be 16 bits wide, which is not
    true on my platform.
     
    Noob, Apr 30, 2008
    #14
  15. On Wed, 30 Apr 2008 10:49:47 +0200, Noob <root@localhost> wrote:

    >Thomas Mertes wrote:
    >
    >> What about something like:
    >>
    >> int greater_or_equal4 (unsigned u, unsigned v)
    >> {
    >> return ((int) u) >= ((int) v);
    >> }
    >>
    >> that way greater_or_equal4(65000, 10) would return 0
    >> (at least when the size of int and unsigned is 2).

    >
    >For the record, the original functions, renamed foo1 and foo2
    >to prevent people from focusing on their result.
    >
    >int foo1(uint16_t u, uint16_t v)
    >{
    > return (int16_t)(u-v) >= 0;


    What happens when u is 0, v is UINT16_MAX, and UINT16_MAX > INT16_MAX?

    >}
    >
    >int foo2(unsigned u, unsigned v)
    >{
    > return ((u-v) & 0xffffU) <= 0x7fffU;
    >}
    >
    >On my platform, foo1 and foo2 are equivalent.
    >My claim is that foo2 is portable, while foo1 is not.
    >
    >greater_or_equal4 is not equivalent to foo2.
    >(Consider u=32000 and v=33000)
    >
    >greater_or_equal4 has even worse shortcomings than foo1, as it
    >requires int and unsigned int to be 16 bits wide, which is not
    >true on my platform.



    Remove del for email
     
    Barry Schwarz, May 1, 2008
    #15
  16. Noob

    Noob Guest

    Barry Schwarz wrote:

    > Noob wrote:
    >
    >> For the record, the original functions, renamed foo1 and foo2
    >> to prevent people from focusing on their result.
    >>
    >> int foo1(uint16_t u, uint16_t v)
    >> {
    >> return (int16_t)(u-v) >= 0;
    >> }

    >
    > What happens when u is 0, v is UINT16_MAX, and UINT16_MAX > INT16_MAX?


    (NB: UINT16_MAX = 65535 and INT16_MAX = 32767)

    If u=0 and v=65535 then (int16_t)(u-v) evaluates to 1.
    And 1 >= 0 evaluates to 1. Therefore foo1 returns 1.

    The logic is: If we receive seqno 0 after seqno 65535, then, with high
    probability, seqno 0 is, in fact, seqno 65536 in disguise, which is
    newer than seqno 65535; which translates to : 0 "is greater than" 65535.

    http://groups.google.com/group/comp.lang.c/browse_frm/thread/dceeb7c981bf2113

    >> int foo2(unsigned u, unsigned v)
    >> {
    >> return ((u-v) & 0xffffU) <= 0x7fffU;
    >> }
    >>
    >> On my platform, foo1 and foo2 are equivalent.
    >> My claim is that foo2 is portable, while foo1 is not.


    foo2(0, 65535) also returns 1.

    Regards.
     
    Noob, May 1, 2008
    #16
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Youhanna Mounir
    Replies:
    3
    Views:
    560
  2. Praveen Pandey

    replacement for ActiveX in .NET

    Praveen Pandey, Dec 7, 2004, in forum: ASP .Net
    Replies:
    1
    Views:
    3,377
    smith
    Dec 8, 2004
  3. Eli Bendersky
    Replies:
    1
    Views:
    1,171
    Mike Treseler
    Mar 1, 2006
  4. Replies:
    7
    Views:
    921
  5. Freejack

    Portable alloca() replacement?

    Freejack, Jan 18, 2005, in forum: C Programming
    Replies:
    9
    Views:
    499
    Villy Kruse
    Jan 19, 2005
Loading...

Share This Page