473,322 Members | 1,523 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,322 software developers and data experts.

left shifts (rationale question)

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).
Feb 3 '07 #1
15 1750
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).
No, it's not okay for some common platforms, such as x86, and that's
why it's not allowed.

Feb 3 '07 #2
In article <11************@news-west.n>,
Christopher Layne <cl****@com.anodizedwrote:
>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...
--
Prototypes are supertypes of their clones. -- maplesoft
Feb 3 '07 #3
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.

Feb 3 '07 #4
santosh wrote:
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.

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"?

--
Chris "electric hedgehog" Dollin
"It took a very long time, much longer than the most generous estimates."
- James White, /Sector General/

Feb 5 '07 #5
Chris Dollin wrote:
santosh wrote:
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. 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.

Feb 5 '07 #6
"santosh" <sa*********@gmail.comwrote in message
news:11**********************@j27g2000cwj.googlegr oups.com...
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
--
Stuart
Feb 5 '07 #7
santosh wrote:
Chris Dollin wrote:
>santosh wrote:
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).
>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.
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.

--
Chris "electric hedgehog" Dollin
A rock is not a fact. A rock is a rock.

Feb 5 '07 #8
Stuart wrote:
"santosh" <sa*********@gmail.comwrote in message
news:11**********************@j27g2000cwj.googlegr oups.com...
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?

Feb 5 '07 #9
In article <11**********************@j27g2000cwj.googlegroups .com>,
santosh <sa*********@gmail.comwrote:
>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
--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.
Feb 5 '07 #10
In article <45**********@glkas0286.greenlnk.net"Stuart" <st****@0.0writes:
"santosh" <sa*********@gmail.comwrote in message
news:11**********************@j27g2000cwj.googlegr oups.com...
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.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Feb 5 '07 #11
Chris Dollin wrote:
>
.... 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
Feb 5 '07 #12
CBFalconer wrote:
Chris Dollin wrote:
>>
... 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;
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 ...

--
Chris "electric hedgehog" Dollin
Nit-picking is best done among friends.

Feb 5 '07 #13
In article <45**********@glkas0286.greenlnk.net>, Stuart <st****@0.0wrote:
>"santosh" <sa*********@gmail.comwrote in message
news:11**********************@j27g2000cwj.googleg roups.com...
>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.
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)"
--
"No one has the right to destroy another person's belief by
demanding empirical evidence." -- Ann Landers
Feb 5 '07 #14
santosh wrote:
Chris Dollin wrote:
>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). :)
Feb 5 '07 #15
Chris Dollin wrote:
CBFalconer wrote:
> 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 ...
Exactly!
Feb 5 '07 #16

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

24
by: Matt Feinstein | last post by:
Hi all-- I'm new to Python, and was somewhat taken aback to discover that the core language lacks some basic numerical types (e.g., single-precision float, short integers). I realize that there...
0
by: Alexander Grigoriev | last post by:
I hope Mr. Stroustrup can give an answer to this question: What was rationale behind the requirements to use an ampersand and a fully qualified name of a function, to form a pointer to a member...
2
by: Glen Able | last post by:
The behaviour of << and >> arithmetic operators (under VC++6, x86) seems rather odd to me. Shifts at runtime seem to only use the bottom 5 bits of the shift amount (an x86 issue I suppose), but...
8
by: Robert Latest | last post by:
Hello, I'm new in javascript programming (but am quite literate in HTML, CSS, and C). It's amazing what one can do with JS and fairly modern browsers. One thing that struck me as odd was that...
52
by: Christopher Benson-Manica | last post by:
gets() is universally acknowledged to be broken and useless; however, it is still part of the standard library. Why? Is there enough conforming code out there using gets() to justify retaining...
17
by: Janice | last post by:
char* line = "abcd"; How to convert the line to upper case and print? Any option for printf to do this? Thanx
19
by: Ross A. Finlayson | last post by:
Hi, I hope you can help me understand the varargs facility. Say I am programming in ISO C including stdarg.h and I declare a function as so: void log_printf(const char* logfilename, const...
11
by: Kenneth Lantrip | last post by:
Anyone got any ideas as to how this process could be improved for speed? this is what I have... Dim j, q As Integer Dim x(16), y(16) As Byte x.CopyTo(y, 0) ' shift left circular 24 bits
3
by: paul.denlinger | last post by:
I can't make the drop-cap work on this paragraph, and then get the paragraph to float left to align. Here is the code below; the URL is http://www.china-ready.com/colly/chapter04/text1.htm ...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.