Basic Shift Right

Anything QL Software or Programming Related.
Derek_Stewart
Font of All Knowledge
Posts: 3928
Joined: Mon Dec 20, 2010 11:40 am
Location: Sunny Runcorn, Cheshire, UK

Basic Shift Right

Post by Derek_Stewart »

Hi,

I have been reading the manual of BlitzMax, which is a LInux/WIndows adaption of the Amiga Blitz2 Basic Compiler system. I hoped that maybe some Blitz2 source code could be adapted for a modern QL system.

I came across a Blitz2 Function: SHR - Bitwise 'Shift right' binary operator

Shr is a binary operator that performs the shift to right function.

Which does not exist in SBASIC, so I thought maybe a FuNction would solve this, my feable attempt:

Code: Select all

100 DEFine FuNction SHR (num)
110   LOCal num$
120   num$=BIN$(num,8)
130   RETurn "0" & num$( TO LEN(num$)-1)
140 END DEFine SHR
Which seems to give the correct Right Shift, can this be refined or is there an existing solution.


Regards,

Derek
User avatar
tofro
Font of All Knowledge
Posts: 2685
Joined: Sun Feb 13, 2011 10:53 pm
Location: SW Germany

Re: Basic Shift Right

Post by tofro »

Derek,

your solution seems to use a valid attempt, although I am missing the conversion back from binary to decimal, but is maybe not the most performant one - transforming to a binary string representation and back to a number looks a bit expensive.

SHR can be directly implemented using integer division by 2, which is essentially the same thing:

Code: Select all

1000 DEFine FuNction Shr% (num%)
1010   LOCal n%
1020   n% = num% DIV 2
1030   RETurn n%
1040 END DEFine Shr%
If written as above, compilers can revert to integer math completely, which makes the whole function quite a bit faster.

Tobias


ʎɐqǝ ɯoɹɟ ǝq oʇ ƃuᴉoƃ ʇou sᴉ pɹɐoqʎǝʞ ʇxǝu ʎɯ 'ɹɐǝp ɥO
martyn_hill
Aurora
Posts: 909
Joined: Sat Oct 25, 2014 9:53 am

Re: Basic Shift Right

Post by martyn_hill »

Hi Derek and Tobias

Both approaches seem sound as far as they go.

One limitation in Tobias' more efficient approach is the limit on SBasic integers - 16-bit signed, which may or may not prove problematic for the use-case.

A while ago, I wrote a simple set of routines in m/c as SBasic functions to do the 16-bit Shift (LSHIFT% & RSHIFT%) and also some basic Boolean functions in 32-bits (AND_L, OR_L, XOR_L & NOT_L), to mimic the 16-bit operators already in SBasic.

One small advantage in the L/RSHIFT% routines over the integer arithmetic approach is that you don't need to care about the signage of the operand as unsigned arithmetic (logical-shift) is used inside the routine - the result will of course be interpreted as a signed integer by SBasic on return, however.

It would be trivial to add a 32-bit version of these.

The 32-bit Long Boolean operators clearly have to return the result as normalised FP (normalisation routine was nicked from SNG's DIYTK...)

I'd happily attach the assembler files here - but for some reason the Attachment feature won't accept the .txt file extension... When I work-out how to overcome that, I'll post again - in case you find the routines useful.

Regards,
M.


Derek_Stewart
Font of All Knowledge
Posts: 3928
Joined: Mon Dec 20, 2010 11:40 am
Location: Sunny Runcorn, Cheshire, UK

Re: Basic Shift Right

Post by Derek_Stewart »

Hi,

I had realised the Shift Right or ROR in assembler is divding by 2, I was looking at too many trees, and not the wood...

So the SHR FuNction reduces to:

Code: Select all

100 DEFine FuNction SHR (num)
110   RETurn INT(num/2)
120 END DEFine SHR
This assuming the number is not negative


Regards,

Derek
User avatar
janbredenbeek
Super Gold Card
Posts: 629
Joined: Wed Jan 21, 2015 4:54 pm
Location: Hilversum, The Netherlands

Re: Basic Shift Right

Post by janbredenbeek »

Derek_Stewart wrote:Hi,

I had realised the Shift Right or ROR in assembler is divding by 2, I was looking at too many trees, and not the wood...

So the SHR FuNction reduces to:

Code: Select all

100 DEFine FuNction SHR (num)
110   RETurn INT(num/2)
120 END DEFine SHR
This assuming the number is not negative
Actually in 68000 assembler there are two 'shift right' instructions: ASR and LSR, which stand for Arithmetic Shift Right and Logical Shift Right respectively. The difference is that LSR always shifts in a '0' bit to the left, and ASR shifts in the same bit as the MSB was before the shift (ie bit 7, 15 or 31 for B, W and L respectively). The latter is effectively an integer division by 2 which also caters for negative numbers.
(Note that ROR also shifts right but inserts the bit that was shifted out to the right - a 'rotate').

Jan.


Derek_Stewart
Font of All Knowledge
Posts: 3928
Joined: Mon Dec 20, 2010 11:40 am
Location: Sunny Runcorn, Cheshire, UK

Re: Basic Shift Right

Post by Derek_Stewart »

Hi Jan,

I was looking at porting over Manic Miner that has been re-written in BlitzMaz, which has keyword to perform a binary shift left or right:

shift = number SHR times

Where:

number = the vlaue to be "shifted"
times = the number of shift operations

If assembler this would be, as you suggested, but in SBASIC the solution that fits the BlitzMax keyword is integer divde by 2.


Regards,

Derek
tcat
Super Gold Card
Posts: 633
Joined: Fri Jan 18, 2013 5:27 pm
Location: Prague, Czech Republic

Re: Basic Shift Right

Post by tcat »

Code: Select all

100 DEFine FuNction SHNR (num, times)
110   RETurn INT(num/(2*times))
120 END DEFine SHNR


User avatar
janbredenbeek
Super Gold Card
Posts: 629
Joined: Wed Jan 21, 2015 4:54 pm
Location: Hilversum, The Netherlands

Re: Basic Shift Right

Post by janbredenbeek »

tcat wrote:

Code: Select all

100 DEFine FuNction SHNR (num, times)
110   RETurn INT(num/(2*times))
120 END DEFine SHNR
No it should be INT(num/2^times). A shift right 3 times is division by 8, 4 times is division by 16 etc.
This of course with all the limitations SB has on integers. Also it would be much slower than MC due to the power function (which probably evaluates as EXP(y*LN(x))).
It won't be too much work to write such a function as MC extension (the most difficult part perhaps the code to convert a 32-bit integer to FP since SB functions cannot return a long int).

Jan.


Derek_Stewart
Font of All Knowledge
Posts: 3928
Joined: Mon Dec 20, 2010 11:40 am
Location: Sunny Runcorn, Cheshire, UK

Re: Basic Shift Right

Post by Derek_Stewart »

Hi Jan,

Thank you for the correction.

TCAT's change to SHNR ??? not what that means.

I am trying to keep the same keywords in SBASIC and BlitzMax.


Regards,

Derek
tcat
Super Gold Card
Posts: 633
Joined: Fri Jan 18, 2013 5:27 pm
Location: Prague, Czech Republic

Re: Basic Shift Right

Post by tcat »

Hi,

Yes, a mistake, division should be 2 power times.

`SHift N-times Right' = SHNR

Tomas


Post Reply