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