Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > What does this code do?

Reply
Thread Tools

What does this code do?

 
 
Richard Heathfield
Guest
Posts: n/a
 
      02-07-2008
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
 
Reply With Quote
 
 
 
 
Kenny McCormack
Guest
Posts: n/a
 
      02-07-2008
In article <(E-Mail Removed)>,
CBFalconer <(E-Mail Removed)> 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.

 
Reply With Quote
 
 
 
 
James Dow Allen
Guest
Posts: n/a
 
      02-08-2008
On Feb 7, 4:00*pm, Richard Heathfield <(E-Mail Removed)> 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
 
Reply With Quote
 
Richard Harter
Guest
Posts: n/a
 
      02-08-2008
On Thu, 07 Feb 2008 09:00:51 +0000, Richard Heathfield
<(E-Mail Removed)> 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://www.velocityreviews.com/forums/(E-Mail Removed)
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.
 
Reply With Quote
 
Dave Hansen
Guest
Posts: n/a
 
      02-08-2008
On Feb 8, 3:12 am, James Dow Allen <(E-Mail Removed)> 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

 
Reply With Quote
 
Kaz Kylheku
Guest
Posts: n/a
 
      02-09-2008
On Feb 5, 8:58*pm, James Dow Allen <(E-Mail Removed)> 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.
 
Reply With Quote
 
Kaz Kylheku
Guest
Posts: n/a
 
      02-09-2008
On Feb 6, 10:22*pm, CBFalconer <(E-Mail Removed)> 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).
 
Reply With Quote
 
James Dow Allen
Guest
Posts: n/a
 
      02-11-2008
On Feb 9, 5:51 am, Dave Hansen <(E-Mail Removed)> wrote:
> On Feb 8, 3:12 am, James Dow Allen <(E-Mail Removed)> 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
 
Reply With Quote
 
James Dow Allen
Guest
Posts: n/a
 
      02-11-2008
On Feb 9, 8:47*am, Kaz Kylheku <(E-Mail Removed)> 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
 
Reply With Quote
 
Richard Bos
Guest
Posts: n/a
 
      02-12-2008
James Dow Allen <(E-Mail Removed)> wrote:

> On Feb 7, 4:00=A0pm, Richard Heathfield <(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
what is the difference between code inside a <script> tag and code in the code-behind file? keithb ASP .Net 1 03-29-2006 01:00 AM
Does no one else think microsoft does a poor job? =?Utf-8?B?SmVyZW15IEx1bmRncmVu?= Wireless Networking 2 11-20-2004 12:17 AM
Loop Does'nt Work, Hard code does Nick L C++ 10 08-31-2004 08:49 PM
Why does this (very simple piece of) code does not work? jblazi Python 5 08-16-2004 01:30 PM
Fire Code behind code AND Javascript code associated to a Button Click Event =?Utf-8?B?Q2FybG8gTWFyY2hlc29uaQ==?= ASP .Net 4 02-11-2004 07:31 AM



Advertisments