left shifts (rationale question)

[Christopher Layne]

So I recently ran into a situation where I invoked UB without specifically
knowing I did it. Yes, human, I know.

What exactly is/was the rationale for not allowing shifts to be the same width
of the datatype one is shifting? Also, for most common platforms (oh,
alright, x86), it's okay to do at the assembly level, isn't it? (provided the
opcodes allow it, I guess that's my question as well).

 

[Guest]

So I recently ran into a situation where I invoked UB without specifically
knowing I did it. Yes, human, I know.

What exactly is/was the rationale for not allowing shifts to be the same width
of the datatype one is shifting? Also, for most common platforms (oh,
alright, x86), it's okay to do at the assembly level, isn't it? (provided the
opcodes allow it, I guess that's my question as well).

No, it's not okay for some common platforms, such as x86, and that's
why it's not allowed.

 

[Walter Roberson]

What exactly is/was the rationale for not allowing shifts to be the same width
of the datatype one is shifting?

We went through this pretty recently, last week or so:

There are a number of common processors where the upper bits of the
shift count are ignored, so using a shift count equal to the word
width is equivilent to using a shift count of 0 on those processors.

If things were otherwise, it could take a long time for a processor
to finish shifting by 0x7fffffff bits...

 

[santosh]

So I recently ran into a situation where I invoked UB without specifically
knowing I did it. Yes, human, I know.

What exactly is/was the rationale for not allowing shifts to be the same width
of the datatype one is shifting? Also, for most common platforms (oh,
alright, x86), it's okay to do at the assembly level, isn't it? (provided the
opcodes allow it, I guess that's my question as well).

Particularly the 32 bit x86 processors ignore the upper 27 bits during
shift operations. Only the lower 5 bits are taken into consideration
since the maximum sane value for shifting a 32 bit value is 31.

 

[Chris Dollin]

Particularly the 32 bit x86 processors ignore the upper 27 bits during
shift operations. Only the lower 5 bits are taken into consideration
since the maximum sane value for shifting a 32 bit value is 31.

Um ... I dispute the "sane" bit. It's perfectly /sane/ to shift a 32-bit
quantity right by 32, or 61, or 9763; one would [1] expect to get 0.

It's a shame that processors don't respect that, but I assume -- my stars,
I really do hope strongly -- that there are good hardware reasons why doing
the right thing would be too expensive.

Given the existence of such hardware, and C's design goals, C's definition
for shifting seems like the only available answer. Deep gloom.

[1] "one'd"?

 

[santosh]

Particularly the 32 bit x86 processors ignore the upper 27 bits during
shift operations. Only the lower 5 bits are taken into consideration
since the maximum sane value for shifting a 32 bit value is 31.

Um ... I dispute the "sane" bit. It's perfectly /sane/ to shift a 32-bit
quantity right by 32, or 61, or 9763; one would [1] expect to get 0.

I can't think of a realistic reason to shift a N bit value by more
than N bits. In fact, from the point of view of standard C, that would
be N - 1 bits. Maybe it makes sense in some exotic implementation, but
I struggle to imagine how.

It's a shame that processors don't respect that, but I assume -- my stars,
I really do hope strongly -- that there are good hardware reasons why doing
the right thing would be too expensive.

I don't know much about hardware, but Walter Roberson did mention that
ridiculously large shift values like 0x7fffffff would take a long time
to complete, and achieve nothing.

 

[Stuart]

I can't think of a realistic reason to shift a N bit value by more
than N bits. In fact, from the point of view of standard C, that would
be N - 1 bits. Maybe it makes sense in some exotic implementation, but
I struggle to imagine how.

In low-level (machine) code it can be a useful way of setting a whole
register to the same as the sign bit without making a branch. (Arithmetic
right shifting usually propagates the sign bit - so you get 0 for positive
starting values and all '1's [aka -1] for a negative starting value).

This could of course be directly incorporated into other bit-twiddling logic
expressions!

I don't know much about hardware, but Walter Roberson did mention that
ridiculously large shift values like 0x7fffffff would take a long time
to complete, and achieve nothing.

Perhaps on some [generally] older technologies; many current generation
processors have barrel-shifters which means it all takes 1-clock no matter
how many places you are shifting.

HTH

 

[Chris Dollin]

Christopher Layne wrote:
So I recently ran into a situation where I invoked UB without specifically
knowing I did it. Yes, human, I know.

What exactly is/was the rationale for not allowing shifts to be the same width
of the datatype one is shifting? Also, for most common platforms (oh,
alright, x86), it's okay to do at the assembly level, isn't it? (provided the
opcodes allow it, I guess that's my question as well).

Particularly the 32 bit x86 processors ignore the upper 27 bits during
shift operations. Only the lower 5 bits are taken into consideration
since the maximum sane value for shifting a 32 bit value is 31.

Um ... I dispute the "sane" bit. It's perfectly /sane/ to shift a 32-bit
quantity right by 32, or 61, or 9763; one would [1] expect to get 0.

I can't think of a realistic reason to shift a N bit value by more
than N bits.

Correctness.

Edge cases (where a shift by N+1 arises as a natural conseqence of
the algorithm being used).

Interpreters (where the shift count isn't known until run-time and
the language requires the result to be zero).

I don't know much about hardware, but Walter Roberson did mention that
ridiculously large shift values like 0x7fffffff would take a long time
to complete, and achieve nothing.

If the shift count has bits set outside the non-trivial shift range, the
result is 0. So I can imagine or-gating all those bits together and using
that bit to control whether the shifter shifts or delivers 0. Of course,
since I'm not a hardware person, I can imagine that this is cheap; but
perhaps it isn't.

 

[Guest]

I can't think of a realistic reason to shift a N bit value by more
than N bits. In fact, from the point of view of standard C, that would
be N - 1 bits. Maybe it makes sense in some exotic implementation, but
I struggle to imagine how.

In low-level (machine) code it can be a useful way of setting a whole
register to the same as the sign bit without making a branch. (Arithmetic
right shifting usually propagates the sign bit - so you get 0 for positive
starting values and all '1's [aka -1] for a negative starting value).

For that, you can right-shift by N-1 bits, can you not?

This could of course be directly incorporated into other bit-twiddling logic
expressions!

I don't know much about hardware, but Walter Roberson did mention that
ridiculously large shift values like 0x7fffffff would take a long time
to complete, and achieve nothing.

Perhaps on some [generally] older technologies; many current generation
processors have barrel-shifters which means it all takes 1-clock no matter
how many places you are shifting.

Do modern x86 processors provide an instruction that shifts by the
specified amount without discarding any bits in the shift count?

 

[Richard Tobin]

I can't think of a realistic reason to shift a N bit value by more
than N bits.

A right shift of k bits can be interpreted as integer division by 2^k;
it's still correct when k is greater than the word size (returning
zero, or possibly -1 for signed shifts).

I don't know much about hardware, but Walter Roberson did mention that
ridiculously large shift values like 0x7fffffff would take a long time
to complete, and achieve nothing.

That's a quality-of-implementation issue for the processor - it could
short-circuit shifts of >=N. But given that processors don't do this,
it would be expensive for C to implement.

-- Richard

 

[Dik T. Winter]

> >

> > I can't think of a realistic reason to shift a N bit value by more
> > than N bits. In fact, from the point of view of standard C, that would
> > be N - 1 bits. Maybe it makes sense in some exotic implementation, but
> > I struggle to imagine how.

>
> In low-level (machine) code it can be a useful way of setting a whole
> register to the same as the sign bit without making a branch. (Arithmetic
> right shifting usually propagates the sign bit - so you get 0 for positive
> starting values and all '1's [aka -1] for a negative starting value).

For that you need to shift only N-1 bits.

 

[CBFalconer]

.... snip ...

If the shift count has bits set outside the non-trivial shift
range, the result is 0. So I can imagine or-gating all those bits
together and using that bit to control whether the shifter shifts
or delivers 0. Of course, since I'm not a hardware person, I can
imagine that this is cheap; but perhaps it isn't.

if ((ct < 0) || (ct >= N)) d = 0;
else d = d >> N;

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>

"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews

 

[Chris Dollin]

if ((ct < 0) || (ct >= N)) d = 0;
else d = d >> N;

Yes, that's what I'd like the hardware to do. I know how to do it
if I'm writing C. Just because I can write it myself doesn't mean
I /want/ to write it myself ...

 

[Walter Roberson]

Perhaps on some [generally] older technologies; many current generation
processors have barrel-shifters which means it all takes 1-clock no matter
how many places you are shifting.

However, those barrel-shifters are not dealing with shifts of
0x7fffffff bits, only of shifts no bigger than the word length.

http://www.everything2.com/index.pl?node_id=1256239

So, what does a barrel shifter actually look like, and how do we
build one?
[...]
If this is what you're thinking, you may well have followed that up
with "Ah, but for an n-bit input/output word, this requires of the
order of n2 gates, which is a hell of a lot of gates for a 32-bit or,
heaven help us, 64-bit input word" and abandoned your line of
reasoning in the expectation that you're about to be told not to be
so silly, and that a barrel shifter implementation is actually a lot
smaller and more efficient than that.

Except of course, you would have been absolutely right. A barrel
shifter is essentially that: an array of multiplexors, with a size
(in terms of gates and silicon area) related to the product of the
number of bits in the input and output words. Additional logic on the
inputs and outputs of the barrel shifter extends the basic
functionality of the barrel shifter to implement the full range of
shifts provided by a processor's instruction set by masking off low
or high bits in the output, sign-extending the result, and selecting
between left and right shifts.

http://citeseer.ist.psu.edu/pillmeier02design.html
"Design Alternatives for Barrel Shifters (ResearchIndex)"

 

[Christopher Layne]

Um ... I dispute the "sane" bit. It's perfectly /sane/ to shift a 32-bit
quantity right by 32, or 61, or 9763; one would [1] expect to get 0.

I can't think of a realistic reason to shift a N bit value by more
than N bits. In fact, from the point of view of standard C, that would
be N - 1 bits. Maybe it makes sense in some exotic implementation, but
I struggle to imagine how.

Basically, in my case I was processing a uint32_t as individual bytes summing
them individually, etc), but I was using previous logic to determine how many
bytes to process as well. I thought things would be fine by constructing a
mask based off the remainder of bytes I was interested in and shifting this
amount left to arrive at the mask:

l &= (0xffffffff << bits_i_care_about_shift_amount);

Didn't work so well when I cared about 0 bytes (aka << 32).

 

[Christopher Layne]

Yes, that's what I'd like the hardware to do. I know how to do it
if I'm writing C. Just because I can write it myself doesn't mean
I /want/ to write it myself ...

Exactly!