What does this code do?

Discussion in 'C Programming' started by James Dow Allen, Feb 6, 2008.

  1. How about this idea? Post fragments of C code which
    seem fun, interesting or instructive. Puzzles can
    be posed in various ways. (What does this do? Can you
    see the bug? How to code this for better efficiency?
    Code for better readability, etc.) Best, perhaps, would
    be fragments from another's admirable application.

    "What does this do?" puzzles might need comments removed
    and symbols obfuscated, as I've done in both of the
    following fragments.

    Fragments #1 and #2 are unrelated to each other.
    Please "reverse-engineer" them before Googl'ing for
    exact provenance.

    Fragment #1
    int hw(uint64 x)
    {
    uint64 y;

    y = x & (x >> H0);
    if (y & (y >> 2 * H0))
    return 1;
    y = x & (x >> H1);
    if (y & (y >> 2 * H1))
    return 1;
    y = x & (x >> H2);
    if (y & (y >> 2 * H2))
    return 1;
    y = x & (x >> 1);
    return (y & (y >> 2));
    }


    Fragment #2
    void baz(int b, int c)
    {
    int a, d, e, f, g;

    if (e = b, g = a = -1, c)
    while (d = b) {
    b = c-1, f = c = d;
    while (f--)
    foo(g -= a);
    d = -e, e = a, a = d;
    }
    }


    What does each of these fragments do?

    James Dow Allen
     
    James Dow Allen, Feb 6, 2008
    #1
    1. Advertising

  2. James Dow Allen

    CBFalconer Guest

    James Dow Allen wrote:
    >

    .... snip ...
    >
    > Fragment #1
    > int hw(uint64 x) {
    > uint64 y;
    >
    > y = x & (x >> H0);


    nothing. H0 is undefined.

    .... snip ...
    >
    > Fragment #2
    > void baz(int b, int c) {
    > int a, d, e, f, g;
    >
    > if (e = b, g = a = -1, c)
    > while (d = b) {


    nothing. d is uninitialized.

    --
    [mail]: Chuck F (cbfalconer at maineline dot net)
    [page]: <http://cbfalconer.home.att.net>
    Try the download section.


    --
    Posted via a free Usenet account from http://www.teranews.com
     
    CBFalconer, Feb 6, 2008
    #2
    1. Advertising

  3. On Wed, 06 Feb 2008 00:20:17 -0500, CBFalconer wrote:

    > James Dow Allen wrote:
    >>

    (...)
    >>
    >> Fragment #2
    >> void baz(int b, int c) {
    >> int a, d, e, f, g;
    >>
    >> if (e = b, g = a = -1, c)
    >> while (d = b) {

    >
    > nothing. d is uninitialized.
    >


    'd' is initialised using input argument 'b' (it is not a comparison to 'b').

    - Anand

    --
    ROT-13 email address to reply.
     
    Anand Hariharan, Feb 6, 2008
    #3
  4. CBFalconer said:

    > James Dow Allen wrote:
    >>

    > ... snip ...
    >>
    >> Fragment #1
    >> int hw(uint64 x) {
    >> uint64 y;
    >>
    >> y = x & (x >> H0);

    >
    > nothing. H0 is undefined.


    Chuck, don't you think James *knows* he hasn't defined H0? He's not exactly
    J Random Newbie.

    --
    Richard Heathfield <http://www.cpax.org.uk>
    Email: -http://www. +rjh@
    Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
    "Usenet is a strange place" - dmr 29 July 1999
     
    Richard Heathfield, Feb 6, 2008
    #4
  5. James Dow Allen

    Richard Bos Guest

    James Dow Allen <> wrote:

    > Fragment #1
    > int hw(uint64 x)
    > {
    > uint64 y;
    >
    > y = x & (x >> H0);
    > if (y & (y >> 2 * H0))
    > return 1;


    Checks whether certain groups of 4 bits are all set. Which 4 bits
    exactly depends on the values of H0/1/2, but the lowest 4 bits are
    always involved because of the literal 1 and 2.

    > Fragment #2
    > void baz(int b, int c)
    > {
    > int a, d, e, f, g;
    >
    > if (e = b, g = a = -1, c)
    > while (d = b) {
    > b = c-1, f = c = d;
    > while (f--)
    > foo(g -= a);
    > d = -e, e = a, a = d;
    > }
    > }


    Outputs all numbers N from 0 <= N < b*c, in some shuffled order that I
    can't be bothered to figure out.

    > What does each of these fragments do?


    I'll tell you what both of them would do if I encountered them in real
    code, though. They'd make me tell off their coders. There may be some
    justification for the first, if H0/1/2 are given proper names and some
    comments are added. There can be no justification for the latter,
    outside the IOCCC.

    Richard
     
    Richard Bos, Feb 6, 2008
    #5
  6. James Dow Allen

    CBFalconer Guest

    Anand Hariharan wrote:
    > CBFalconer wrote:
    >> James Dow Allen wrote:
    >>>

    > (...)
    >>>
    >>> Fragment #2
    >>> void baz(int b, int c) {
    >>> int a, d, e, f, g;
    >>>
    >>> if (e = b, g = a = -1, c)
    >>> while (d = b) {

    >>
    >> nothing. d is uninitialized.

    >
    > 'd' is initialised using input argument 'b' (it is not a
    > comparison to 'b').


    Woops - you're right.

    --
    [mail]: Chuck F (cbfalconer at maineline dot net)
    [page]: <http://cbfalconer.home.att.net>
    Try the download section.



    --
    Posted via a free Usenet account from http://www.teranews.com
     
    CBFalconer, Feb 6, 2008
    #6
  7. In article <>,
    Richard Heathfield <> wrote:
    >CBFalconer said:
    >
    >> James Dow Allen wrote:
    >>>

    >> ... snip ...
    >>>
    >>> Fragment #1
    >>> int hw(uint64 x) {
    >>> uint64 y;
    >>>
    >>> y = x & (x >> H0);

    >>
    >> nothing. H0 is undefined.

    >
    >Chuck, don't you think James *knows* he hasn't defined H0? He's not exactly
    >J Random Newbie.


    Oh. The. Irony.

    Note that recently the regs are getting more and more open (and openness
    is a good thing - don't get me wrong!) about the fact that there are
    different rules for the Clique than for, as RH so quaintly puts it, J
    Random Newbie.

    Note also that CBF's Clique membership seems to be in a probationary
    status these days...
     
    Kenny McCormack, Feb 6, 2008
    #7
  8. James Dow Allen

    Richard Guest

    (Kenny McCormack) writes:

    > In article <>,
    > Richard Heathfield <> wrote:
    >>CBFalconer said:
    >>
    >>> James Dow Allen wrote:
    >>>>
    >>> ... snip ...
    >>>>
    >>>> Fragment #1
    >>>> int hw(uint64 x) {
    >>>> uint64 y;
    >>>>
    >>>> y = x & (x >> H0);
    >>>
    >>> nothing. H0 is undefined.

    >>
    >>Chuck, don't you think James *knows* he hasn't defined H0? He's not exactly
    >>J Random Newbie.

    >
    > Oh. The. Irony.
    >
    > Note that recently the regs are getting more and more open (and openness
    > is a good thing - don't get me wrong!) about the fact that there are
    > different rules for the Clique than for, as RH so quaintly puts it, J
    > Random Newbie.
    >
    > Note also that CBF's Clique membership seems to be in a probationary
    > status these days...


    "Chuck" is probably one of the most useless posters to a Usenet
    technical group I have ever witnessed. No wonder his code is so awful -
    I doubt if he was ever allowed to post in a real team as I have rarely
    seen anyone so antisocial and up themselves. Better to killfile him,
    much as a I abhor doing so.
     
    Richard, Feb 6, 2008
    #8
  9. James Dow Allen

    Guest

    Re: What does this code do?

    Decrease productivity of newsgroup readers ? :)
     
    , Feb 6, 2008
    #9
  10. James Dow Allen

    CBFalconer Guest

    Richard Heathfield wrote:
    > CBFalconer said:
    >> James Dow Allen wrote:
    >>>

    >> ... snip ...
    >>>
    >>> Fragment #1
    >>> int hw(uint64 x) {
    >>> uint64 y;
    >>>
    >>> y = x & (x >> H0);

    >>
    >> nothing. H0 is undefined.

    >
    > Chuck, don't you think James *knows* he hasn't defined H0? He's
    > not exactly J Random Newbie.


    I rarely pay any great attention to the writers identity. It's
    still undefined.

    --
    [mail]: Chuck F (cbfalconer at maineline dot net)
    [page]: <http://cbfalconer.home.att.net>
    Try the download section.



    --
    Posted via a free Usenet account from http://www.teranews.com
     
    CBFalconer, Feb 7, 2008
    #10
  11. CBFalconer said:

    > Richard Heathfield wrote:
    >> CBFalconer said:
    >>> James Dow Allen wrote:
    >>>>
    >>> ... snip ...
    >>>>
    >>>> Fragment #1
    >>>> int hw(uint64 x) {
    >>>> uint64 y;
    >>>>
    >>>> y = x & (x >> H0);
    >>>
    >>> nothing. H0 is undefined.

    >>
    >> Chuck, don't you think James *knows* he hasn't defined H0? He's
    >> not exactly J Random Newbie.

    >
    > I rarely pay any great attention to the writers identity. It's
    > still undefined.


    Do you pay any great attention to the writer's article? Here's what he
    wrote:

    'How about this idea? Post fragments of C code which
    seem fun, interesting or instructive. Puzzles can
    be posed in various ways. (What does this do? Can you
    see the bug? How to code this for better efficiency?
    Code for better readability, etc.) Best, perhaps, would
    be fragments from another's admirable application.

    '"What does this do?" puzzles might need comments removed
    and symbols obfuscated, as I've done in both of the
    following fragments.'

    Given the above, it is hardly surprising that some information was removed.
    Note especially the phrase "fragments of C code".

    --
    Richard Heathfield <http://www.cpax.org.uk>
    Email: -http://www. +rjh@
    Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
    "Usenet is a strange place" - dmr 29 July 1999
     
    Richard Heathfield, Feb 7, 2008
    #11
  12. In article <>,
    CBFalconer <> tries desperately to re-assert
    his position in the Clique thusly:
    ....
    >> Chuck, don't you think James *knows* he hasn't defined H0? He's
    >> not exactly J Random Newbie.

    >
    >I rarely pay any great attention to the writers identity. It's
    >still undefined.


    Oh. The. Irony.
     
    Kenny McCormack, Feb 7, 2008
    #12
  13. On Feb 7, 4:00 pm, Richard Heathfield <> wrote:
    > CBFalconer said:
    > >>> nothing.  H0 is undefined.

    >
    > Do you pay any great attention to the writer's article?
    > Here's what he wrote:
    >
    >> 'How about this idea?  Post fragments of C code which
    >> seem fun, interesting or instructive.  Puzzles can
    >> be posed in various ways.  (What does this do?  Can you
    >> see the bug?  How to code this for better efficiency?
    >> Code for better readability, etc.)  Best, perhaps, would
    >> be fragments from another's admirable application.
    >>
    >> '"What does this do?" puzzles might need comments removed
    >> and symbols obfuscated, as I've done in both of the
    >> following fragments.'


    Perhaps it was unwise to start with comment-less
    "What does this do?" puzzles. Still, it seems
    bizarre that responders complained about slight
    obfuscation when the preface explained why
    comments were removed!

    > Note especially the phrase "fragments of C code".


    I suppose "fragment" isn't defined in the standard.
    "Not-necessarily self-sufficient excerpt" is my
    intent. Might be interesting to hear how Chuck
    defines "fragment", if he can do so civilly.

    Fragment #2 is "self-sufficient" in the sense
    that "cc -c" won't complain, but needs the reader
    to supply *very* trivial main() and foo() to
    experiment. I'd expect this to be a 1 or 2
    minute task.

    Richard Bos wrote:
    > [Fragment #2] Outputs all numbers N
    > from 0 <= N < b*c, in some shuffled order
    > that I can't be bothered to figure out.


    No, it doesn't output; it visits with 'foo()'.
    This lapse, and the fact that Bos got this
    far, means he did indeed write the trivial
    main() and foo() with the latter based on
    printf(). Hard to believe no one else could
    do this.

    > that I can't be bothered to figure out.


    I don't want to impugn Bos -- we all have our
    limitations -- but for a programmer he must
    be peculiarly poor at arithmetic for the
    order to be unclear. And, frankly, a bit
    of a sore loser to blame his own inadequacy
    on my puzzle!

    Best wishes to all!
    James
     
    James Dow Allen, Feb 8, 2008
    #13
  14. On Thu, 07 Feb 2008 09:00:51 +0000, Richard Heathfield
    <> wrote:

    >CBFalconer said:


    >> I rarely pay any great attention to the writers identity. It's
    >> still undefined.

    >
    >Do you pay any great attention to the writer's article? Here's what he
    >wrote:


    On the evidence I've seen, CBF seldom pays any great attention to
    the articles he is commenting on. There is no point in
    mentioning this to him; he clearly isn't going to change.

    Richard Harter,
    http://home.tiac.net/~cri, http://www.varinoma.com
    Save the Earth now!!
    It's the only planet with chocolate.
     
    Richard Harter, Feb 8, 2008
    #14
  15. James Dow Allen

    Dave Hansen Guest

    On Feb 8, 3:12 am, James Dow Allen <> wrote:
    [...]
    > Richard Bos wrote:
    > > [Fragment #2] Outputs all numbers N
    > > from 0 <= N < b*c, in some shuffled order
    > > that I can't be bothered to figure out.

    >
    > No, it doesn't output; it visits with 'foo()'.
    > This lapse, and the fact that Bos got this
    > far, means he did indeed write the trivial
    > main() and foo() with the latter based on
    > printf(). Hard to believe no one else could
    > do this.
    >
    > > that I can't be bothered to figure out.

    >
    > I don't want to impugn Bos -- we all have our
    > limitations -- but for a programmer he must
    > be peculiarly poor at arithmetic for the
    > order to be unclear. And, frankly, a bit
    > of a sore loser to blame his own inadequacy
    > on my puzzle!


    He didn't say he couldn't, but that he couldn't be bothered.
    Apparently he's decided it's beneath him.

    But I like a puzzle. I'm thinking "spiral..."

    Regards,

    -=Dave
     
    Dave Hansen, Feb 8, 2008
    #15
  16. James Dow Allen

    Kaz Kylheku Guest

    On Feb 5, 8:58 pm, James Dow Allen <> wrote:
    > Fragments #1 and #2 are unrelated to each other.
    > Please "reverse-engineer" them before Googl'ing for
    > exact provenance.
    >
    > Fragment #1
    > int hw(uint64 x)
    > {
    >     uint64    y;
    >
    >     y = x & (x >> H0);


    Regard x is a bitmask representing a set of integers ranging from 0 to
    63. If a bit is on in a position, the corresponding integer is in the
    set.

    This first step means ``find all integers j in x, such that j + H0 is
    also in j''. This set is called y.

    Thus every integer which has a counterpart that is H0 greater is
    retained.

    >     if (y & (y >> 2 * H0))
    >         return 1;


    This step means ``find all integers j in y, such that j + 2*H0 is also
    in y''.

    So now out of these integers which have a counterpart at H1, integers
    which have a counterpart at 2*H1 are retained. If this set is non-
    empty, we return 1.

    In other words, if any integer in the set has a counterpart offset by
    H0, and also another counterpart at twice that distance in the same
    direction, 1 is returned, otherwise the test continues with other
    constants in place of H0.

    The test looks for the presence of triplets of equally spaced
    integers, where the spacing is H0.

    >     y = x & (x >> H1);
    >     if (y & (y >> 2 * H1))
    >         return 1;
    >     y = x & (x >> H2);
    >     if (y & (y >> 2 * H2))
    >         return 1;
    >     y = x & (x >> 1);
    >     return (y & (y >> 2));
    >
    > }


    The last test is the same, but with the constant 1. This effectively
    detects whether there are any consecutive triplets in the set.

    The result of y & (y >> 2) is itself a set, which gives the root
    position of each triplet: an integer i is in the set if it is the root
    of a triplet of consecutive integers.

    However, this set doesn't necessarily fit into the return type
    (assuming that the uint64 typedef name, in good faith, represents some
    kind of 64 bit or perhaps wider type). This is a bug; perhaps the
    intent was: return (y & (y >> 2)) != 0;

    The last test would then be consistent with the others: return a 1
    indication if there are triplets. And so zero is returned if there are
    no triplets present with any of the spacings.

    How would this triplet finding be applied in some algorithm? No clue
    there. Error detection? A zero is returned if the word is free of
    triplets at the given spacings. Could this constitute some kind of
    error detection?

    Suppose the words are used to communicate or store data. The bits of
    data are encoded into the codeword such that straight triplets of 1
    bits do not exist anywhere (but there can be arbitrary runs of 0).
    Triplets at the two other spacings don't exist either. If the data is
    retrieved or received containing triplets, it is erroneous.

    But that's quite dumb since it doesn't treat 0's and 1's equally. Any
    erasure of 1 to a 0 goes undetected.

    However, this is just one function, and not necessarily the whole
    scheme. The function could also be tried on a bitwise-inversion of the
    input to test for triplets of 0 bits: the encoding scheme would be
    that triplet runs of the same bit value are not allowed at various
    spacings.

    So for instance the data cannot be 000111000111. It must transition
    between 0 and 1 more rapidly than every three.

    Hmm.
     
    Kaz Kylheku, Feb 9, 2008
    #16
  17. James Dow Allen

    Kaz Kylheku Guest

    On Feb 6, 10:22 pm, CBFalconer <> wrote:
    > Richard Heathfield wrote:
    > > Chuck, don't you think James *knows* he hasn't defined H0?  He's
    > > not exactly J Random Newbie.

    >
    > I rarely pay any great attention to the writers identity.  It's
    > still undefined.


    Unknown quantities named by symbols do not block thought.

    (See mathematics and logic for instance).
     
    Kaz Kylheku, Feb 9, 2008
    #17
  18. On Feb 9, 5:51 am, Dave Hansen <> wrote:
    > On Feb 8, 3:12 am, James Dow Allen <> wrote:
    > [...]
    > > Richard Bos wrote:
    > > > that I can't be bothered to figure out.

    > He didn't say he couldn't, but that he couldn't be bothered.
    > Apparently he's decided it's beneath him.
    >
    > But I like a puzzle. I'm thinking "spiral..."


    Yes, with a nearby spiralling thread I'm surprised
    only Dave got this. It would be interesting to
    know why Bos disliked the code so much. (Omission
    of comments was deliberate.) I don't generally pack
    multiple statements onto one line, but did so
    almost whimsically in the fragment. Avoiding
    new lines seems not too egregious in simple idioms like
    d = e, e = a, a = d; /* swap */

    All other things being equal (though of course
    they never are!) the succincter code is the better
    code: one FOR is better than four FOR's. For this
    reason, my spiraller seems OK.

    James
     
    James Dow Allen, Feb 11, 2008
    #18
  19. On Feb 9, 8:47 am, Kaz Kylheku <> wrote:
    > > y = x & (x >> H0);
    > > if (y & (y >> 2 * H0))
    > > return 1;

    > The test looks for the presence of triplets of equally spaced
    > integers, where the spacing is H0.


    Check again! First y finds pairs;
    second y finds ... quadruplets!

    In the original source code (from a famous benchmark)
    each
    if (R)
    actually has the form
    if ((R) != 0)
    At the last moment before posting I deleted the
    "unnecessary" ( ... != 0)
    to reduce clutter. I was overzealous :-(

    > However, this set doesn't necessarily fit into the return type
    > (assuming that the uint64 typedef name, in good faith, represents some
    > kind of 64 bit or perhaps wider type). This is a bug; perhaps the
    > intent was: return (y & (y >> 2)) != 0;


    Good catch, Kaz! I've been running this routine a lot
    lately; but fortunately the real bug-free code, not
    the zealously decluttered version I posted.

    Thus the code checks for quadruplets aligned along
    any of four axes. This could be a 4-D modelling but
    in fact is a 2-D structure with diagonals, rows
    and columns producing 4 axes. Application?
    Hasbro's game Connect Four.

    James
     
    James Dow Allen, Feb 11, 2008
    #19
  20. James Dow Allen

    Richard Bos Guest

    James Dow Allen <> wrote:

    > On Feb 7, 4:00=A0pm, Richard Heathfield <> wrote:
    > > CBFalconer said:
    > > >>> nothing. =A0H0 is undefined.

    > >
    > > Do you pay any great attention to the writer's article?
    > > Here's what he wrote:
    > >
    > >> 'How about this idea? =A0Post fragments of C code which
    > >> seem fun, interesting or instructive. =A0Puzzles can
    > >> be posed in various ways. =A0(What does this do? =A0Can you
    > >> see the bug? =A0How to code this for better efficiency?
    > >> Code for better readability, etc.) =A0Best, perhaps, would
    > >> be fragments from another's admirable application.
    > >>
    > >> '"What does this do?" puzzles might need comments removed
    > >> and symbols obfuscated, as I've done in both of the
    > >> following fragments.'

    >
    > Perhaps it was unwise to start with comment-less
    > "What does this do?" puzzles. Still, it seems
    > bizarre that responders complained about slight
    > obfuscation when the preface explained why
    > comments were removed!


    Slight?

    > > Note especially the phrase "fragments of C code".

    >
    > I suppose "fragment" isn't defined in the standard.


    Oh, come off it. You're not Kenny.

    > Richard Bos wrote:
    > > [Fragment #2] Outputs all numbers N
    > > from 0 <=3D N < b*c, in some shuffled order
    > > that I can't be bothered to figure out.

    >
    > No, it doesn't output; it visits with 'foo()'.
    > This lapse, and the fact that Bos got this
    > far, means he did indeed write the trivial
    > main() and foo() with the latter based on
    > printf(). Hard to believe no one else could
    > do this.


    Caught. Actually, I did a dry run first, on paper, thought that it
    probably called foo() with a shuffled list of 0..b*c-1, and decided to
    let the computer do the busy-work of checking that for larger b and c.

    > > that I can't be bothered to figure out.

    >
    > I don't want to impugn Bos -- we all have our
    > limitations -- but for a programmer he must
    > be peculiarly poor at arithmetic for the
    > order to be unclear. And, frankly, a bit
    > of a sore loser to blame his own inadequacy
    > on my puzzle!


    Get off your friggin' high horse, mister perfect-maths-wizard. You have
    not the slightest idea how I tested your program wand why I could not be
    arsed to do more of an effort. But since you asked for it, I'll tell you
    now: I couldn't be arsed because it was crappy code, used in a crappy
    puzzle, by a crappy programmer who should have known better than to
    consider that crap even remotely acceptable. And in the future, I won't
    even be making what little effort I have this time; your programming
    inadequacy is not worth it.

    Richard
     
    Richard Bos, Feb 12, 2008
    #20
    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. =?Utf-8?B?Q2FybG8gTWFyY2hlc29uaQ==?=

    Fire Code behind code AND Javascript code associated to a Button Click Event

    =?Utf-8?B?Q2FybG8gTWFyY2hlc29uaQ==?=, Feb 10, 2004, in forum: ASP .Net
    Replies:
    4
    Views:
    21,373
    =?Utf-8?B?Q2FybG8gTWFyY2hlc29uaQ==?=
    Feb 11, 2004
  2. Bill Johnson
    Replies:
    0
    Views:
    1,256
    Bill Johnson
    Jul 8, 2005
  3. keithb
    Replies:
    1
    Views:
    959
    Bruce Barker
    Mar 29, 2006
  4. Nick L
    Replies:
    10
    Views:
    618
    Jerry Coffin
    Aug 31, 2004
  5. jblazi
    Replies:
    5
    Views:
    458
    jblazi
    Aug 16, 2004
Loading...

Share This Page