A
Alan Connor
Why do you talk to an obviously knowledgable man as if he was a member of
an inferior species who had never seen a computer before?
an inferior species who had never seen a computer before?
R
Richard Heathfield
Alan said:
It is far from obvious that Roose is knowledgeable, at least in areas of
knowledge that this newsgroup recognises as relevant.
J
Joona I Palaste
That's a mighty big "at least", Richard. For all we know, Roose could be
the world's leading authority on car engine maintenance or something.
What he clearly is *not* knowledgeable about is C. He knows some C, but
not nearly enough to make the claims that he's making even as we speak.
OTOH, having or not having seen a computer isn't that relevant. It could
be argued that one could become an expert on ISO standard C really
without ever seeing a computer. *Only* in ISO standard C, though, mind
you - not any platform-specific extensions. Understandably, because
there would *be* no platform to speak of. But ISO standard C is all
this newsgroup cares about, and all it should care about.
A
Arthur J. O'Dwyer
Apparently, it was "That is what I thought as well."
But when I looked at it, I figured
RH: "You recall incorrectly."
JP: "Then I will [something] take a walk."
-Arthur
J
Joona I Palaste
Whoa! That's certainly possible (although in this case untrue), but it
just so nonsensical I can hardly stop laughing at it. goose recalling
incorrectly causes me to take a walk? Because of what? It's true that
taking a walk can refresh one's memory, but to refresh someone else's
memory...
M
maniac
maniac said:
man this thing's still around, holy crap.
oh, well good I guess.
C
Chris Torek
Assuming there is no overflow -- and if "len" is at least
unsigned int, and c1 and c2 are in the range [0..255], then
we can make sure that there is none by replacing "256" with
"256U" in each case -- then writing either of:
len = (c1 << 8) + c2;
or len = c1 * 256 + c2;
makes no difference, as a left-shift is equivalent to a multiply.
Of course these should be expressed as:
len = ((unsigned int)c1 << 8) + c2;
and len = c1 * 256U + c2;
respectively.
As for whether one form or the other is "better", it depends on
what you intend to convey to a (human) reader. Any compiler worth
what you paid for it will optimize "c1 * 256U" (or even c1*256,
without the U) into a left shift, and -- in the absence of overflow
-- left shifts are defined in terms of multiplication. (In the
presence of overflow, neither is strictly defined by the C standards,
and a compiler can use the shift anyway on any typical modern CPU.)
Thus, whether you write "what you mean" or "how to do it" is in a
sense irrelevant, as they are isomorphic.
Even the division-by-shifting optimization is easy for compilers
to implement, although here it is more likely to occur for unsigned
operands, because a compiler must typically include some "compensation"
code for signed divison. This is because:
y = x >> 2;
vs y = x / 4;
is typically not the same when x is negative. For instance, (-1)
/ 4 is usually 0 (and I think is *required* to be 0 in C99), while
(-1) >> 2 is usually -1, on today's machines. Note, however, that
while left shift is *defined* in terms of multiplication -- in both
C89 and C99 -- right shift is not defined in terms of division
except for non-negative "x". Thus, in this case, you really *must*
write "what you mean" instead of "how to do it", as the two are
not necessarily synonymous.
<begin OT>
For the curious, the "compensation" code for a negative dividend
(and positive divisor) -- remember in x / y, x is the dividend and
y is the divisor -- works out to the following, all assuming 2s
complement and an arithmetic right-shift:
/* divide signed input "x" by divisor, whose log2 is d2 */
int divide_by_power_of_two(int x, int divisor, int d2) {
int adj;
/* required: (1 << d2) == divisor */
adj = (x & SIGNBIT) ? divisor - 1 : 0;
return (ux + adj) >> d2;
}
The idea here is that, e.g., when dividing by 4 (d2 == 2), we want
-1 to give 0, -2 to give 0, -3 to give 0, but -4 to give -1; -5
through -7 should also be -1, while -8 should be -2; and so on.
If x is nonnegative, x >> d2 gives the right answer, but if x is
negative, it gives the wrong answer unless x is an even multiple
of the divisor, otherwise it gives a value one too small (-1 instead
of 0, -2 instead of -1, and so on). Adding (positive) 3 gives the
right answer for -1 through -3 and leaves -4 at -1, which shifts
to -1; and so on. An equivalent trick is to add 1 to the result
if any "1" bits are shifted out during the right-shift operation,
but this is harder to test on typical machines -- the FPU has
hardware to collect such bits (in the "sticky bit" part of IEEE FP
processing), but the integer unit lacks it. The calculation of
the (x&SIGNBIT) adjustment value can, however, be done branchlessly
by shifting x the appropriate number of bits right, e.g., 31 for
32-bit x, to produce an all-ones mask for negative values and
all-zeros for nonnegative, then ANDing this mask with (divisor-1).
On a typical RISC we get something like:
mov x, reg # assuming x is already in a register
asr reg, 31, reg # where asr is arithmetic shift right
and reg, 3, reg # for divisor == 4
add reg, x, reg
asr reg, 2, reg # again for divisor == 4
# final result is now in "reg"
The constants (31, 3, and 2 here) are "number of bits in x that
are not the sign bit", "divisor - 1", and "log2 divisor". For
small divisors these usually fit in the instruction format -- most
RISCs have constant fields that go to at least 255, if not higher;
4095 is not unusual. All of this is only a win if the divide takes
more cycles than the four instructions above. Assuming a single
barrel or funnel shifter and two ALUs, the four instructions take
two cycles, while a typical integer divide is at least four cycles
and as long as 31 or 100 or so cycles, depending on the CPU, so
this is indeed a win, and the compiler should use it.
Of course, if the CPU has a single-cycle divide, or if the dividE
is "parallelizable" and there is other work to do before referring
to the result-value register, it is better just to do "idiv x, 4,
reg". On the (old-only?) MIPS, where you move the values into the
mul/div unit, it is something of a toss-up -- the divide runs in
parallel to any remaining work, but the extra moves consume extra
cycles.
<end OT>
M
Mark McIntyre
I'm sorry, I haven't a clue.
(well, ok then, 5th paragraph on this page....
http://news.bbc.co.uk/1/hi/uk/79273.stm
although a 30+ year steeping in British Comedy and a labyrinthine
knowledge of the london underground map is typically required to stand
a chance of winning, never mind understand Graeme's rules at the end
of the article)
M
Mark McIntyre
I must have either completely missed that post, or misunderstood it.
Could you paraphrase?
M
Mark McIntyre
Its highly likely you'll now have to explain "The Goodies". Good
luck...
Willie Rushton (decd)
Balderdash, you heretic !! Graeme provided the following rules for the
terminally confused ie those stuck at Aldwych, Barking or Edgware Road
(District Line).
-Boxing out the F, J, O and W placings draws the partner into an
elliptical progression north to south
-In weak positional play, it is vital to consolidate an already strong
outer square, eg Pentonville Road
-In a straight rules game, it's inadmissible to transfer inversely,
which is otherwise a powerful tactic
-Opening the triangle will block any of the three possible reverse
draws and is usually played early in the game (before the Central Line
has been quartered) so that the risk of a diagonal move is negligible,
as is the possibility of quartering
-The lateral shift decisively breaks opponents' horizontal and
vertical approaches.
-The A40 northbound used as a counter-play offers rear access to
suburban bidding
Be afraid, be very afraid.....
M
Mark McIntyre
Well, no actually.
It says
"An integer constant expression with the value 0, or such an
expression cast to type void *, is called a null pointer constant. If
a null pointer constant is converted to a pointer type, the resulting
pointer, called a null pointer, is guaranteed to compare unequal to a
pointer to any object or function." (6.3.2.3-1)
You will note the phrase "if .... converted to a pointer type". I
believe we agree that NULL is a macro with value either zero or
(void*)0. It is therefore a null pointer constant. And I read the
above as saying that its not a pointer until its converted to a
pointer type. My case rests. For now...
I disagree that it disagrees. In order to compare p to NULL, you must
convert p to a pointer type (see quote above, plus 6.3.2.3-4). I'm
doubtful that you could convert a null pointer constant to a pointer
type without storing it somewhere....
M
Mark McIntyre
BUAATOO, IR.
B
Ben Pfaff
Mark McIntyre said:
I quoted a paragraph from the standard that used the word
"pointer" several times to mean "value of pointer type". If the
standard doesn't always use "pointer" as meaning "object of
pointer type", then I don't think it's reasonable to define it
that way.
M
Mark McIntyre
Ah, so whats the difference between the stuff that comes out of a 1401
and goes into a 7094? Does it magically get transmogrified during the
technician's walk down the hall with the tape?*
Hmmmm. I find this distinction highly artificial.
* for anyone under about 60, a 1401 is an IBM computer which was
typically used to read punched cards and transfer the results to
tape, which was then fed into a larger IBM, such as a 7094.
S
Sheldon Simms
There was actually a really good example of this a few days ago
here in the thread about computing integer powers. The following
function was presented:
static int pow_a(int x, int y)
{
int t=1;
if (y < 0) return 0;
for(;
{
if (y%2) t*=x; /* if y is odd... */
if (!(y/=2))break; /* halve y and if result is zero... */
x*=x; /* square x */
}
return t;
}
While testing this and the other functions, I was read the output
of GCC for all of the functions because I was curious why some
functions seemed to run faster even though the C code was
apparently equivalent. The y/=2 in the second if conditional
is turned into the following x86 code by GCC 3.3.1:
movl %edx, %eax ; temp = y
shrl $31, %eax ; temp >>= 31
leal (%eax,%edx), %eax ; temp = temp + y
sarl %eax ; temp >>= 1;
movl %eax, %edx ; y = temp
-Sheldon
C
Chris Torek
Yes, this is a special case of the code I suggested. We want
"adj = (x & SIGNBIT) ? (2 - 1) : 0", and of course 2 - 1 is 1. I
had suggested the general case would use (for x86) "sarl $31, %eax"
and then "and $1, %eax", but note that if we use a logical shift
instead of an arithmetic shift, the values we get for "is signed"
and "is not signed" are 1 and 0 respectively, instead of -1 and 0.
In (nonportable) C this would be:
/* adj = (x >> 31) & (divisor - 1); -- general case */
adj = (unsigned)x >> 31; /* specific case when divisor==2 */
This allows the compiler to omit the "and" instruction. (The
nonportable parts are twofold: this assumes x is a 32 bit two's
complement value; and it assumes that signed ">>" sign-extends.
The first part is easy to parameterize, but the second is not.)
(The "leal" instead of "add" is another fairly disgusting trick that
avoids pipeline constraints in some cases, I believe.)
G
goose
"for what its worth", and then ?
??
goose,
tia
??
goose,
tia
R
Richard Heathfield
Mark said:
You make a better case than I thought existed. Lacking the time right now to
make a detailed study of the matter, so I hope someone else picks it up.
I'm not quite so doubtful as you are about the conversion. After all, on
some implementations it's a no-op. Would you suggest that, say, 0 is an
object?
R
Richard Heathfield
Mark said:
Think of them as being part of the same computer system, with the technician
being a rather slow, but high-capacity, data bus.
Data are the raw materials of information.
C
Christian Bau
Chris Torek said:
On a PowerPC, you get:
int test (int x) { return x / 4; }
00000000: 7C601670 srawi r0,r3,2 // r0 = r3 >> 2
00000004: 7C600194 addze r3,r0 // r3 = r0 + 0 + carry
00000008: 4E800020 blr // Return