left shifts (rationale question)

Discussion in 'C Programming' started by Christopher Layne, Feb 3, 2007.

  1. 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).
    Christopher Layne, Feb 3, 2007
    #1
    1. Advertising

  2. 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.
    =?utf-8?B?SGFyYWxkIHZhbiBExLNr?=, Feb 3, 2007
    #2
    1. Advertising

  3. In article <>,
    Christopher Layne <> wrote:
    >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
    Walter Roberson, Feb 3, 2007
    #3
  4. Christopher Layne

    santosh Guest

    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.
    santosh, Feb 3, 2007
    #4
  5. Christopher Layne

    Chris Dollin Guest

    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/
    Chris Dollin, Feb 5, 2007
    #5
  6. Christopher Layne

    santosh Guest

    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.
    santosh, Feb 5, 2007
    #6
  7. Christopher Layne

    Stuart Guest

    "santosh" <> wrote in message
    news:...

    > 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
    Stuart, Feb 5, 2007
    #7
  8. Christopher Layne

    Chris Dollin Guest

    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.
    Chris Dollin, Feb 5, 2007
    #8
  9. Stuart wrote:
    > "santosh" <> wrote in message
    > news:...
    >
    > > 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?
    =?utf-8?B?SGFyYWxkIHZhbiBExLNr?=, Feb 5, 2007
    #9
  10. In article <>,
    santosh <> wrote:

    >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.
    Richard Tobin, Feb 5, 2007
    #10
  11. In article <45c71de3$> "Stuart" <stuart@0.0> writes:
    > "santosh" <> wrote in message
    > news:...
    >
    > > 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/
    Dik T. Winter, Feb 5, 2007
    #11
  12. Christopher Layne

    CBFalconer Guest

    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
    CBFalconer, Feb 5, 2007
    #12
  13. Christopher Layne

    Chris Dollin Guest

    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.
    Chris Dollin, Feb 5, 2007
    #13
  14. In article <45c71de3$>, Stuart <stuart@0.0> wrote:
    >"santosh" <> wrote in message
    >news:...


    >> 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
    Walter Roberson, Feb 5, 2007
    #14
  15. 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). :)
    Christopher Layne, Feb 5, 2007
    #15
  16. 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!
    Christopher Layne, Feb 5, 2007
    #16
    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. Guest

    Index Page Shifts Position

    Guest, Aug 8, 2004, in forum: HTML
    Replies:
    3
    Views:
    605
    Mark Parnell
    Aug 9, 2004
  2. Richard
    Replies:
    1
    Views:
    500
    Richard
    Dec 18, 2005
  3. =?iso-8859-1?q?Jean-Fran=E7ois_Michaud?=

    Help on table align on left of page vs left hanging indent

    =?iso-8859-1?q?Jean-Fran=E7ois_Michaud?=, Jul 10, 2007, in forum: XML
    Replies:
    2
    Views:
    999
    =?iso-8859-1?q?Jean-Fran=E7ois_Michaud?=
    Jul 16, 2007
  4. pc
    Replies:
    2
    Views:
    1,309
    crisgoogle
    Jun 8, 2011
  5. lawrence
    Replies:
    13
    Views:
    295
    Thomas 'PointedEars' Lahn
    Sep 4, 2004
Loading...

Share This Page