Tuesday, May 6, 2014

Shifts? We don't need no stinking Shifts!

 [The code previously given for "algebraic right shift: does not work for a shift of more than one bit, and has been replaced using a different approach. Apologies to anyone who was confused by the previous version.]

A previous post ("Op Codes?  We don't need no stinking Op Codes!") showed how to do common operations on a computer that always performed the same operation (subtract and branch if not positive) on different operands.  In that post, the operations performed treated the operands as integer values.  There are situations in which it is convenient to treat the operands as bit strings (or Boolean vectors) where the bits are shifted or individual bits are manipulated; multiplication, division, and extraction of substrings are among these situations.  Individual bits can be isolated by a combination of left and right shifts, so shifts are the basic operations for bit string manipulation. 



In the previous post, the representation of values inside the computer was not specified:  the values could be twos complement binary or tens complement decimal; ones complement binary, nines complement decimal, and sign-magnitude (either binary or decimal) introduce the complication of negative zero.  Other representations such as excess-3 have been used in some computers.  In this post, we will assume twos complement binary is being used.

There are several kinds of shifts  Circular shifts can be accomplished by a right shift, a left shift of the original value by the complementary amount, and an add.  Shifts among multiple locations can also be accomplished by a combination of left shifts, right shifts, and adds.  Algebraic shifts extend the sign bit to replace bits that are shifted out.  Unsigned or ordinary shifts insert zeros to replace bits that are shifted out.

These examples use additional work areas

WORKLOC3: +0
WORKLOC4: +0

A left shift of one bit can be obtained by

          WORKLOC,WORKLOC              * WORKLOC = 0
          WORKLOC,A                    * WORKLOC = -#A
          A,WORKLOC                    * A = #A + #A

A left shift of more than one bit can be obtained by

LSHFTPRM:                              * PARMLIST
A:        +0                           * VALUE TO BE SHIFTED
LSHFTCNT: +0                           * NUMBER OF BITS SHIFTED OUT
SHIFTLFT: +0                           * RETURN ADDRESS
* BEGINNING OF SUBROUTINE
          WORKLOC2,WORKLOC2            * WORKLOC2 = 0
          WORKLOC2,A                   * WORKLOC2 = -#A
          WORKLOC,WORKLOC              * WORKLOC = 0
          WORKLOC,WORKLOC2             * WORKLOC = #A
LSFTLOOP:
          WORKLOC2,WORKLOC2            * WORKLOC2 = 0
          WORKLOC2,WORKLOC             * WORKLOC2 = -#WORKLOC
          WORKLOC,WORKLOC2             * WORKLOC = #WORKLOC + #WORKLOC
          LSHFTCNT,ONE,SHIFTLFT        * BITS LEFT = BITS LEFT - 1
          ZERO,ZERO,LSFTLOOP           * REPEAT UNTIL BITS LEFT = 0

A right shift can be obtained by

RSHFTPRM:                              * PARMLIST

B:        +0                           * VALUE TO BE SHIFTED
RSHFTCNT: +0                           * NUMBER OF BITS SHIFTED OUT
SHIFTRGT: +0                           * RETURN ADDRESS
* BEGINNING OF SUBROUTINE
          WORKLOC,WORKLOC              * WORKLOC = 0
          WORKLOC,WORDLEN              * WORKLOC = -#WORDLEN
          SHIFTCNT,SHIFTCNT            * BITS SHIFTED = 0
          SHIFTCNT,WORKLOC             * BITS SHIFTED = #WORDLEN
          SHIFTCNT,RSHFTCNT            * BITS SHIFTED = #WORDLEN - #RSHFTCNT
          WORKLOC,WORKLOC              * RESULT = 0
          WORKLOC2,WORKLOC2            * WORKLOC2 = 0
          WORKLOC2,B                   * WORKLOC2 = -#B
          WORKLOC3,WORKLOC3            * WORKLOC3 = 0
          WORKLOC3,WORKLOC2,MINUSORZ   * WORKLOC3 = #B
* IF NOT POSITIVE CHECK FOR OTHER CASES

RSHFTLUP:                              * LOOP UNTIL NO BITS LEFT
          WORKLOC2,WORKLOC2            * WORKLOC2 = 0
          ZERO,ZERO,GOTVALUE           * BIT VALUE = 0

MINUSORZ:                              * VALUE LESS THAN OR EQUAL TO 0
          WORKLOC2,WORKLOC2            * WORKLOC2 = 0
          WORKLOC2,B                   * WORKLOC2 = -#B
          WORKLOC3,WORKLOC3            * WORKLOC3 = 0
          WORKLOC3,WORKLOC2            * WORKLOC3 = #B
          WORKLOC3,MOSTNEG,MINCASE     * SMALLEST VALUE IS SPECIAL CASE
          WORKLOC2,ZERO,ZEROCASE       * IF -#WORKLOC IS 0 SPECIAL CASE
          WORKLOC2,WORKLOC2            * WORKLOC2 = 0
          WORKLOC2,ONE                 * WORKLOC2 = -1
                                       * BIT VALUE = 1

GOTVALUE:                              * PLACE BIT VALUE ONTO RESULT
          WORKLOC2,WORKLOC             * IF BIT VALUE IS 1
                                       * WORKLOC2 = -#WORKLOC - 1
                                       * ELSE WORKLOC2 = -#WORKLOC
          WORKLOC,WORKLOC2             * IF BIT VALUE IS 1
                                       * WORKLOC = (2 * #WORKLOC) + 1
                                       * ELSE WORKLOC = 2 * #WORKLOC
          SHIFTCNT,ONE,RSHFTFIN        * BITS LEFT = BITS LEFT - 1
                                       * IF BITS LEFT LESS THAN 1 FINISH
          WORKLOC2,WORKLOC2            * WORKLOC2 = 0
          WORKLOC2,B                   * WORKLOC2 = -#B
          B,WORKLOC2                   * B = 2 * #B
          B,ZERO,MINUSORZ        * IF NOT POSITIVE CHECK FOR OTHER CASES
          ZERO,ZERO,RSHFTLUP           * REPEAT LOOP IF BITS LEFT

MINCASE:                               * SPECIAL CASE: SMALLEST VALUE
          WORKLOC2,WORKLOC2            * WORKLOC2 = 0
          WORKLOC2,ONE                 * WORKLOC2 = -1
          ZERO,ZERO,SPECCASE           * MERGE WITH ZERO CASE

ZEROCASE:                              * SPECIAL CASE: ZERO
          WORKLOC2,WORKLOC2            * WORKLOC2 = 0

SPECCASE:                              * SPECIAL CASES MERGED
          WORKLOC2,WORKLOC             * IF BIT VALUE IS 1
                                       * WORKLOC2 = -#WORKLOC - 1
                                       * ELSE WORKLOC2 = -#WORKLOC
          WORKLOC,WORKLOC2             * IF BIT VALUE IS 1
                                       * WORKLOC = (2 * #WORKLOC) + 1
                                       * ELSE WORKLOC = 2 * #WORKLOC
          SHIFTCNT,ONE,RSHFTFIN        * BITS LEFT = BITS LEFT - 1
          WORKLOC2,WORKLOC2            * WORKLOC2 = 0
          ZERO,ZERO,SPECCASE           * REPEAT SPECIAL CASE

RSHFTFIN:                              * PUT RESULT BACK
          WORKLOC3,WORKLOC3            * WORKLOC3 = 0
          WORKLOC3,WORKLOC             * WORKLOC3 = -#WORKLOC
          B,B                          * B = 0
          B,WORKLOC3                   * B = #WORKLOC
          ZERO,ZERO,SHIFTRGT           * RETURN TO CALLING ROUTINE

SHIFTCNT: +0                           * NUMBER OF BITS RETAINED
WORDLEN:  +(NUMBER OF BITS IN A WORD)
MOSTNEG:  -(2^(WORDLEN-1))             * SMALLEST VALUE

An algebraic right shift (divide by 2 and round down) can be obtained by

SFTRGTAL: +0                           * RETURN ADDRESS

* BEGINNING OF SUBROUTINE
          WORKLOC2,WORKLOC2            * WORKLOC2 = 0
          WORKLOC2,B                   * WORKLOC2 = -#B
          WORKLOC,WORKLOC              * WORKLOC = 0
          WORKLOC,WORKLOC2,NOTPLUS     * WORKLOC = #B

                                 * IF LESS THAN 1 CHECK FOR OTHER CASES
          WORKLOC,WORKLOC              * WORKLOC = 0
          WORKLOC,SFTRGTAL             * WORKLOC = -#(RETURN ADDRESS)
          SHIFTRGT,SHIFTRGT      * BIT STRING SHIFT RETURN ADDRESS = 0
          SHIFTRGT,WORKLOC       * BIT STRING RETURN ADDRESS = #SFTRGTAL
          ZERO,ZERO,SHIFTRGT+1         * MERGE WITH ORDINARY SHIFT

NOTPLUS:                               * VALUE NOT POSITIVE
          WORKLOC2,WORKLOC2            * WORKLOC2 = 0
          WORKLOC2,WORKLOC             * WORKLOC2 = -#A
          WORKLOC2,ZERO,RSFTZERO       * IF 0 RESULT IS 0
          WORKLOC4,WORKLOC4            * WORKLOC4 = 0
          WORKLOC4,RSHFTCNT            * WORKLOC4 = -(DROP COUNT)
          SHIFTRGT,SHIFTRGT      * RETURN ADDRESS FOR ORDINARY SHIFT = 0
          SHIFTRGT,RSFTARET      * SET RETURN ADDRESS FOR ORDINARY SHIFT
          ZERO,ZERO,SHIFTRGT+1         * DO ORDINARY SHIFT

RSFTAFIN:                              * CONTINUE ALGEBRAIC SHIFT
          WORKLOC,WORKLOC              * WORKLOC = 0
          WORKLOC,WORDLEN              * WORKLOC = -#WORDLEN
          LSHFTCNT,LSHFTCNT            * LSHFTCNT = 0
          LSHFTCNT,WORKLOC             * LSHFTCNT = #WORDLEN
          LSHFTCNT,WORKLOC4      * LSHFTCNT = #WORDLEN - (DROP COUNT)
          WORKLOC,WORKLOC              * WORKLOC = 0
          WORKLOC,B                    * WORKLOC = -#B
          B,B                          * B = 0
          B,ONE                        * B = -1
          SHIFTLFT,SHIFTLFT      * RETURN ADDRESS FOR LEFT SHIFT = 0
          SHIFTLFT,RSFTCRET      * SET RETURN ADDRESS FOR LEFT SHIFT
          ZERO,ZERO,SHIFTLFT+1         * DO LEFT SHIFT

RSFTCOMB:                        * COMBINE SIGN BITS + SHIFTED VALUE
          B,WORKLOC4             * B = (SIGN BITS) + (SHIFTED VALUE)
          ZERO,ZERO,SFTRGTAL           * RETURN TO CALLING ROUTINE

RSFTZERO:                              * VALUE IS ZERO
          B,B                          * B = 0
          ZERO,ZERO,SFTRGTAL           * RETURN TO CALLING ROUTINE

RSFTARET: -RSFTAFIN                    * ADDRESS OF CONTINUATION OF SHIFT
RSFTCRET: -RSFTCOMB                    * ADDRESS OF COMBINATION WITH SIGN


0 Comments:

Post a Comment

Please enter your comment here. Comments wil be reviewed before being published.

Subscribe to Post Comments [Atom]

<< Home