Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.arch > #4049 > unrolled thread

Q: bit shifting

Back to article view | Back to comp.arch

Contents

  Q: bit shifting Mok-Kong Shen <mok-kong.shen@t-online.de> - 2011-10-07 13:31 +0200
    Re: Q: bit shifting nmm1@cam.ac.uk - 2011-10-07 12:17 +0100
      Re: Q: bit shifting Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-07 17:35 +0200
        Re: Q: bit shifting Stephen Fuld <SFuld@alumni.cmu.edu.invalid> - 2011-10-07 09:31 -0700
          Re: Q: bit shifting nmm1@cam.ac.uk - 2011-10-07 17:16 +0100
            Re: Q: bit shifting Stephen Fuld <SFuld@alumni.cmu.edu.invalid> - 2011-10-07 23:13 -0700
              Re: Q: bit shifting nmm1@cam.ac.uk - 2011-10-08 09:56 +0100
                Re: Q: bit shifting Andrew Reilly <areilly---@bigpond.net.au> - 2011-10-08 21:28 +0000
                Re: Q: bit shifting timcaffrey@aol.com (Tim McCaffrey) - 2011-10-11 15:05 +0000
                  Re: Q: bit shifting Sean Case <seancase@tpg.com.au> - 2011-10-16 23:15 +1000
                    Re: Q: bit shifting timcaffrey@aol.com (Tim McCaffrey) - 2011-10-19 20:12 +0000
        Re: Q: bit shifting Robert Wessel <robertwessel2@yahoo.com> - 2011-10-07 12:24 -0500
          Re: Q: bit shifting Kai Harrekilde-Petersen <khp@harrekilde.dk> - 2011-10-07 19:27 +0200
            Re: Q: bit shifting Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-08 10:41 +0200
              Re: Q: bit shifting Kai Harrekilde-Petersen <khp@harrekilde.dk> - 2011-10-08 11:28 +0200
                Re: Q: bit shifting Andrew Reilly <areilly---@bigpond.net.au> - 2011-10-08 21:38 +0000
              Re: Q: bit shifting Robert Wessel <robertwessel2@yahoo.com> - 2011-10-08 22:57 -0500
                Re: Q: bit shifting Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-09 08:18 +0200
                Re: Q: bit shifting Mok-Kong Shen <mok-kong.shen@t-online.de> - 2011-10-19 15:08 +0200
              Re: Q: bit shifting Michael S <already5chosen@yahoo.com> - 2011-10-11 16:41 -0700
                Re: Q: bit shifting Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-12 07:55 +0200
                  Re: Q: bit shifting MitchAlsup <MitchAlsup@aol.com> - 2011-10-12 10:21 -0700
                    Re: Q: bit shifting Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-12 21:22 +0200
                      Re: Q: bit shifting kenney@cix.compulink.co.uk - 2011-10-13 11:00 -0500
                        Re: Q: bit shifting Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-13 20:32 +0200
        Re: Q: bit shifting Mike Hore <mike_horeREM@OVE.invalid.aapt.net.au> - 2011-10-11 17:08 +1100
    Re: Q: bit shifting MitchAlsup <MitchAlsup@aol.com> - 2011-10-07 12:49 -0700
      Re: Q: bit shifting nmm1@cam.ac.uk - 2011-10-07 21:20 +0100
      The word is devolving into 3 architectures (NOT?) "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-10-07 19:48 -0700
        Re: The word is devolving into 3 architectures (NOT?) Mark Thorson <nospam@sonic.net> - 2011-10-07 19:56 -0800
        Re: The word is devolving into 3 architectures (NOT?) "Skybuck Flying" <Windows7IsOK@DreamPC2006.com> - 2011-10-08 04:53 +0200
        Re: The word is devolving into 3 architectures (NOT?) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-10-08 17:26 +0000
      Re: Q: bit shifting Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-08 10:47 +0200
        Re: Q: bit shifting MitchAlsup <MitchAlsup@aol.com> - 2011-10-08 12:27 -0700
          Re: Q: bit shifting Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-09 08:07 +0200
            Re: Q: bit shifting MitchAlsup <MitchAlsup@aol.com> - 2011-10-09 12:36 -0700
              Re: Q: bit shifting Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-10 09:06 +0200
                Re: Q: bit shifting timcaffrey@aol.com (Tim McCaffrey) - 2011-10-10 15:31 +0000
                  Re: Q: bit shifting Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-10 18:13 +0200
                    Re: Q: bit shifting timcaffrey@aol.com (Tim McCaffrey) - 2011-10-10 20:27 +0000
                      Re: Q: bit shifting Terje Mathisen <"terje.mathisen at tmsw.no"> - 2011-10-10 23:45 +0200
                        Re: Q: bit shifting Robert Wessel <robertwessel2@yahoo.com> - 2011-10-10 17:32 -0500
                          Re: Q: bit shifting timcaffrey@aol.com (Tim McCaffrey) - 2011-10-11 14:58 +0000
                            Re: Q: bit shifting Robert Wessel <robertwessel2@yahoo.com> - 2011-10-11 11:30 -0500
                              Re: Q: bit shifting "Andy \"Krazy\" Glew" <andy@SPAM.comp-arch.net> - 2011-10-11 10:05 -0700
                                Re: Q: bit shifting timcaffrey@aol.com (Tim McCaffrey) - 2011-10-11 17:59 +0000
                                Re: Q: bit shifting timcaffrey@aol.com (Tim McCaffrey) - 2011-10-11 18:00 +0000
                                  Re: Q: bit shifting Al Grant <algrant@myrealbox.com> - 2011-10-11 13:49 -0700
                                    Re: Q: bit shifting Al Grant <algrant@myrealbox.com> - 2011-10-11 14:18 -0700
                                Re: Q: bit shifting Robert Wessel <robertwessel2@yahoo.com> - 2011-10-11 16:03 -0500
                  Re: Q: bit shifting MitchAlsup <MitchAlsup@aol.com> - 2011-10-10 09:52 -0700
          Re: Q: bit shifting anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2011-10-09 12:24 +0000
            Re: Q: bit shifting nmm1@cam.ac.uk - 2011-10-09 13:13 +0100
    Re: Q: bit shifting Quadibloc <jsavard@ecn.ab.ca> - 2011-10-09 10:11 -0700

Page 3 of 3 — ← Prev page 1 2 [3]

#4132

Tim McCaffrey wrote:
> In article<28ibm8-6uo1.ln1@ntp6.tmsw.no>, "terje.mathisenattmsw.no" says...
>> With masking that gives you a count of 1, saturation gives you 32.
>>
>> With 64-bit regs the mask should not be lower than 127, at which point
>> the hw will almost certainly saturate the count at 64 anyway.
>
> Well, I'm thinking of this from a more generic model, where the saturation
> would be correct in all cases, and masking a bigger number would be correct
> in only the "closer to boundary" conditions.

We're probably in violent agreement, at least if you also believe the HW 
should do "The Right Thing" for any shift_by_M, i.e. return exactly the 
same result as M iterations of a loop doing a single bit shift.

The obvious way to implement this on a machine with N-bit registers is 
to saturate the input shift count at N, in which case you need a barrel 
shifter which can do [0-N] bit shifts, fronted by a fairly simple 
saturation circuit:

OR together all the bits from N and up, if at least one is set then the 
count is taken as N, otherwise the lower bits contain the normal/regular 
count.

The reason I advocated 2N-1 as the minimum mask value was because I've 
written a lot of bit twiddling code over the years, and quite often that 
code becomes simpler if I don't have to guard against counts that can go 
slightly over the register width limit.

In fact, just allowing 0-N inclusive instead of 0 to N-1 helps quite a 
bit...
>
> What if your definition of shift (not C's definition) says you need to
> implement saturation? (For some algorithmic reason).  Then no matter how big
> the mask is, it is still a mask and you have to add an explicit check into
> your code to do the saturate check (even only using CL (instead of ECX/RCX)
> is a possible problem.

See above, I agree with you. :-)
>
> Well, doesn't matter, nobody is going to change the instruction set now...

Nope.

Terje
-- 
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"

[toc] | [prev] | [next] | [standalone]

#4133

On Mon, 10 Oct 2011 23:45:57 +0200, Terje Mathisen <"terje.mathisen at
tmsw.no"> wrote:

>Tim McCaffrey wrote:
>> In article<28ibm8-6uo1.ln1@ntp6.tmsw.no>, "terje.mathisenattmsw.no" says...
>>> With masking that gives you a count of 1, saturation gives you 32.
>>>
>>> With 64-bit regs the mask should not be lower than 127, at which point
>>> the hw will almost certainly saturate the count at 64 anyway.
>>
>> Well, I'm thinking of this from a more generic model, where the saturation
>> would be correct in all cases, and masking a bigger number would be correct
>> in only the "closer to boundary" conditions.
>
>We're probably in violent agreement, at least if you also believe the HW 
>should do "The Right Thing" for any shift_by_M, i.e. return exactly the 
>same result as M iterations of a loop doing a single bit shift.
>
>The obvious way to implement this on a machine with N-bit registers is 
>to saturate the input shift count at N, in which case you need a barrel 
>shifter which can do [0-N] bit shifts, fronted by a fairly simple 
>saturation circuit:
>
>OR together all the bits from N and up, if at least one is set then the 
>count is taken as N, otherwise the lower bits contain the normal/regular 
>count.
>
>The reason I advocated 2N-1 as the minimum mask value was because I've 
>written a lot of bit twiddling code over the years, and quite often that 
>code becomes simpler if I don't have to guard against counts that can go 
>slightly over the register width limit.
>
>In fact, just allowing 0-N inclusive instead of 0 to N-1 helps quite a 
>bit...
>>
>> What if your definition of shift (not C's definition) says you need to
>> implement saturation? (For some algorithmic reason).  Then no matter how big
>> the mask is, it is still a mask and you have to add an explicit check into
>> your code to do the saturate check (even only using CL (instead of ECX/RCX)
>> is a possible problem.
>
>See above, I agree with you. :-)
>>
>> Well, doesn't matter, nobody is going to change the instruction set now...
>
>Nope.


There is perhaps some hope - consider that Intel did mostly replace
the x87 stuff (obviously it's still there, but it's certainly not the
preferred FP ISA for new stuff).  They also added LZCNT to replace the
messed up BSF.  Perhaps it's more than just an off chance given just
how badly shifts are messed up for 64 bit code now.

[toc] | [prev] | [next] | [standalone]

#4139

In article <92s697p3lu7f1ei913uipatg70ba6ip9dn@4ax.com>, 
robertwessel2@yahoo.com says...
>
>On Mon, 10 Oct 2011 23:45:57 +0200, Terje Mathisen <"terje.mathisen at
>tmsw.no"> wrote:
>
>>Tim McCaffrey wrote:
>>>
>>> Well, doesn't matter, nobody is going to change the instruction set 
now...
>>
>>Nope.
>
>
>There is perhaps some hope - consider that Intel did mostly replace
>the x87 stuff (obviously it's still there, but it's certainly not the
>preferred FP ISA for new stuff).  They also added LZCNT to replace the
>messed up BSF.  Perhaps it's more than just an off chance given just
>how badly shifts are messed up for 64 bit code now.

It is sometimes hard to track this, but I think AMD introduced that 
instruction....

		- Tim

[toc] | [prev] | [next] | [standalone]

#4142

On Tue, 11 Oct 2011 14:58:35 +0000 (UTC), timcaffrey@aol.com (Tim
McCaffrey) wrote:

>In article <92s697p3lu7f1ei913uipatg70ba6ip9dn@4ax.com>, 
>robertwessel2@yahoo.com says...
>>
>>On Mon, 10 Oct 2011 23:45:57 +0200, Terje Mathisen <"terje.mathisen at
>>tmsw.no"> wrote:
>>
>>>Tim McCaffrey wrote:
>>>>
>>>> Well, doesn't matter, nobody is going to change the instruction set 
>now...
>>>
>>>Nope.
>>
>>
>>There is perhaps some hope - consider that Intel did mostly replace
>>the x87 stuff (obviously it's still there, but it's certainly not the
>>preferred FP ISA for new stuff).  They also added LZCNT to replace the
>>messed up BSF.  Perhaps it's more than just an off chance given just
>>how badly shifts are messed up for 64 bit code now.
>
>It is sometimes hard to track this, but I think AMD introduced that 
>instruction....


Indeed they were.  And only recently adopted by Intel.  I was not
aware of that.

[toc] | [prev] | [next] | [standalone]

#4144

On 10/11/2011 9:30 AM, Robert Wessel wrote:
> On Tue, 11 Oct 2011 14:58:35 +0000 (UTC), timcaffrey@aol.com (Tim
> McCaffrey) wrote:
>
>> In article<92s697p3lu7f1ei913uipatg70ba6ip9dn@4ax.com>,
>> robertwessel2@yahoo.com says...
>>>
>>> On Mon, 10 Oct 2011 23:45:57 +0200, Terje Mathisen<"terje.mathisen at
>>> tmsw.no">  wrote:
>>>
>>>> Tim McCaffrey wrote:
>>>>>
>>>>> Well, doesn't matter, nobody is going to change the instruction set
>> now...
>>>>
>>>> Nope.
>>>
>>>
>>> There is perhaps some hope - consider that Intel did mostly replace
>>> the x87 stuff (obviously it's still there, but it's certainly not the
>>> preferred FP ISA for new stuff).  They also added LZCNT to replace the
>>> messed up BSF.  Perhaps it's more than just an off chance given just
>>> how badly shifts are messed up for 64 bit code now.
>>
>> It is sometimes hard to track this, but I think AMD introduced that
>> instruction....
>
>
> Indeed they were.  And only recently adopted by Intel.  I was not
> aware of that.


Would somebody like to summarize why BSF was messed up, and how LZCNT is 
better?

[toc] | [prev] | [next] | [standalone]

#4145

In article <4E947766.5000709@SPAM.comp-arch.net>, andy@SPAM.comp-arch.net 
says...
>
>On 10/11/2011 9:30 AM, Robert Wessel wrote:
>> On Tue, 11 Oct 2011 14:58:35 +0000 (UTC), timcaffrey@aol.com (Tim
>> McCaffrey) wrote:
>>
>>> In article<92s697p3lu7f1ei913uipatg70ba6ip9dn@4ax.com>,
>>> robertwessel2@yahoo.com says...
>>>>
>>>> On Mon, 10 Oct 2011 23:45:57 +0200, Terje Mathisen<"terje.mathisen at
>>>> tmsw.no">  wrote:
>>>>
>>>>> Tim McCaffrey wrote:
>>>>>>
>>>>>> Well, doesn't matter, nobody is going to change the instruction set
>>> now...
>>>>>
>>>>> Nope.
>>>>
>>>>
>>>> There is perhaps some hope - consider that Intel did mostly replace
>>>> the x87 stuff (obviously it's still there, but it's certainly not the
>>>> preferred FP ISA for new stuff).  They also added LZCNT to replace the
>>>> messed up BSF.  Perhaps it's more than just an off chance given just
>>>> how badly shifts are messed up for 64 bit code now.
>>>
>>> It is sometimes hard to track this, but I think AMD introduced that
>>> instruction....
>>
>>
>> Indeed they were.  And only recently adopted by Intel.  I was not
>> aware of that.
>
>
>Would somebody like to summarize why BSF was messed up, and how LZCNT is 
>better?

1 & 0 give the same answer?

	- Tim

[toc] | [prev] | [next] | [standalone]

#4146

In article <4E947766.5000709@SPAM.comp-arch.net>, andy@SPAM.comp-arch.net 
says...
>
>On 10/11/2011 9:30 AM, Robert Wessel wrote:
>> On Tue, 11 Oct 2011 14:58:35 +0000 (UTC), timcaffrey@aol.com (Tim
>> McCaffrey) wrote:
>>
>>> In article<92s697p3lu7f1ei913uipatg70ba6ip9dn@4ax.com>,
>>> robertwessel2@yahoo.com says...
>>>>
>>>> On Mon, 10 Oct 2011 23:45:57 +0200, Terje Mathisen<"terje.mathisen at
>>>> tmsw.no">  wrote:
>>>>
>>>>> Tim McCaffrey wrote:
>>>>>>
>>>>>> Well, doesn't matter, nobody is going to change the instruction set
>>> now...
>>>>>
>>>>> Nope.
>>>>
>>>>
>>>> There is perhaps some hope - consider that Intel did mostly replace
>>>> the x87 stuff (obviously it's still there, but it's certainly not the
>>>> preferred FP ISA for new stuff).  They also added LZCNT to replace the
>>>> messed up BSF.  Perhaps it's more than just an off chance given just
>>>> how badly shifts are messed up for 64 bit code now.
>>>
>>> It is sometimes hard to track this, but I think AMD introduced that
>>> instruction....
>>
>>
>> Indeed they were.  And only recently adopted by Intel.  I was not
>> aware of that.
>
>
>Would somebody like to summarize why BSF was messed up, and how LZCNT is 
>better?

Wrong. 1 and 0 give counter intuitive answers.

1 BSF == 0
0 BSF == 32? ( I think )

		- Tim

[toc] | [prev] | [next] | [standalone]

#4150

On Oct 11, 7:00 pm, timcaff...@aol.com (Tim McCaffrey) wrote:
> 0 BSF == 32? ( I think )

No, "if the content of the source operand is 0, the content
of the destination operand is undefined" (ZF is set instead).

Incidentally, Intel's pseudocode seems not to define the
result for any odd-valued input either:

  IF SRC = 0
    THEN
      ZF <- 1;
      DEST is undefined;
    ELSE
      ZF <- 0;
      temp <- 0;
      WHILE Bit(SRC,temp) = 0
      DO
        temp <- temp + 1;
        DEST <- temp;
      OD;
  FI;

So if Bit(SRC,0) is 1, you never go through the loop and
never assign to DEST.  (I guess that the assignment to
DEST should have gone after the OD.)

It's like that in my 2005 printout, and appears to be still
like that in the current (dated May 2011) edition.

[toc] | [prev] | [next] | [standalone]

#4151

On Oct 11, 9:49 pm, Al Grant <algr...@myrealbox.com> wrote:
> Incidentally, Intel's pseudocode seems not to define the
> result

(I should have said, the pseudocode defines the result to be
the destination register's original value.  Which is still not right.)

[toc] | [prev] | [next] | [standalone]

#4149

On Tue, 11 Oct 2011 10:05:42 -0700, "Andy \"Krazy\" Glew"
<andy@SPAM.comp-arch.net> wrote:

>On 10/11/2011 9:30 AM, Robert Wessel wrote:
>> On Tue, 11 Oct 2011 14:58:35 +0000 (UTC), timcaffrey@aol.com (Tim
>> McCaffrey) wrote:
>>
>>> In article<92s697p3lu7f1ei913uipatg70ba6ip9dn@4ax.com>,
>>> robertwessel2@yahoo.com says...
>>>>
>>>> On Mon, 10 Oct 2011 23:45:57 +0200, Terje Mathisen<"terje.mathisen at
>>>> tmsw.no">  wrote:
>>>>
>>>>> Tim McCaffrey wrote:
>>>>>>
>>>>>> Well, doesn't matter, nobody is going to change the instruction set
>>> now...
>>>>>
>>>>> Nope.
>>>>
>>>>
>>>> There is perhaps some hope - consider that Intel did mostly replace
>>>> the x87 stuff (obviously it's still there, but it's certainly not the
>>>> preferred FP ISA for new stuff).  They also added LZCNT to replace the
>>>> messed up BSF.  Perhaps it's more than just an off chance given just
>>>> how badly shifts are messed up for 64 bit code now.
>>>
>>> It is sometimes hard to track this, but I think AMD introduced that
>>> instruction....
>>
>>
>> Indeed they were.  And only recently adopted by Intel.  I was not
>> aware of that.
>
>
>Would somebody like to summarize why BSF was messed up, and how LZCNT is 
>better?


BSR (I wrote BSF by mistake, BSF basically counts trailing zeros)
leaves the destination register undefined if the input operand is zero
(no bits set).  That's the biggie (LZCNT just returns the number of
leading zero bits as 0-16/32/64). BSR does set ZF when there are no
set bits, but that then requires a painful branch to deal with the
condition.

BSR also returns the index of the bit from the wrong end of the
register, and provides a less useful set of flag settings (LZCNT sets
ZF if there were zero leading zero bits and sets CF if there were no
bits set - providing the same info as BSR does).

All of which can be fixed, but...

[toc] | [prev] | [next] | [standalone]

#4129

On Monday, October 10, 2011 10:31:18 AM UTC-5, Tim McCaffrey wrote:
> BTW, Burroughs B5000 started with the Bitfield extract/insert (and no shifts) 
> in the mid-60's.  The 88000 was neat, but it was late to the party (they 
> really should have architected 64 bits).

Had we targeted 1.2 microns instead of 1.5 microns, it would have been 64-bits (and even later; and possibly not survived at all due to internal politics).

Mitch

[toc] | [prev] | [next] | [standalone]

#4116

MitchAlsup <MitchAlsup@aol.com> writes:
>An arithmetic right shift of -1 yeilds -1 for any number of shifts either a=
>s one operation or as a loop of operations; whereas -1 / 2 =3D 0. Thus ASR =
>is not a cousin to integer divide by power of 2.

An arithmetic shift right performs a floored (round towards negative
infinity) division by a power of 2.  floor(-1/n)=-1 for any integer
n>0, so that works as it should.

Architectures that have a signed division instruction typically
implement symmetric division (round towards 0).

I am not sure what it would take for you to accept these two
operations as cousins.

- anton
-- 
M. Anton Ertl                    Some things have to be seen to be believed
anton@mips.complang.tuwien.ac.at Most things have to be believed to be seen
http://www.complang.tuwien.ac.at/anton/home.html

[toc] | [prev] | [next] | [standalone]

#4117

In article <2011Oct9.142423@mips.complang.tuwien.ac.at>,
Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>MitchAlsup <MitchAlsup@aol.com> writes:
>>An arithmetic right shift of -1 yeilds -1 for any number of shifts either a=
>>s one operation or as a loop of operations; whereas -1 / 2 =3D 0. Thus ASR =
>>is not a cousin to integer divide by power of 2.
>
>An arithmetic shift right performs a floored (round towards negative
>infinity) division by a power of 2.  floor(-1/n)=-1 for any integer
>n>0, so that works as it should.
>
>Architectures that have a signed division instruction typically
>implement symmetric division (round towards 0).

Nowadays.  It used to be fairly common for them to implement
floored division for a positive divisor, and a variety of options
for a negative one.  That is why most standards originating before
1990 permit both.

>I am not sure what it would take for you to accept these two
>operations as cousins.

Indeed.


Regards,
Nick Maclaren.

[toc] | [prev] | [next] | [standalone]

#4118

On Oct 7, 5:31 am, Mok-Kong Shen <mok-kong.s...@t-online.de> wrote:
> This is an ignorant's question: I remember having long ago read in
> a manual of a certain now non-existant hardware that a command to
> do bit shifts by an amount n (the hardware had word size of n bits)
> was undefined, i.e. the amount being shifted must be less than n.
> Could such ever be the case for the modern hardware?

It's entirely possible, since modern hardware is very unlikely to
implement a shift command by simply shifting one place at a time and
counting. Instead, barrel shifting circuitry or something equivalent,
where "shift 1", "shift 2", "shift 4", "shift 8", and so on circuits
are switched in is almost certain to be used - and so the possible
shifts would be limited to those considered to be useful.

John Savard

[toc] | [prev] | [standalone]

Page 3 of 3 — ← Prev page 1 2 [3]

Back to top | Article view | comp.arch

csiph-web