Skip to content

Latest commit

 

History

History
281 lines (177 loc) · 6.71 KB

op_rshift.md

File metadata and controls

281 lines (177 loc) · 6.71 KB

Bitwise Right Shift: OP_RSHIFT

Bitwise right shifts of 32-bit words.

Bitwise Right Shift by 3 Bits: OP_3RSHIFT


btcdeb "[

# Some random 32-bit word is on the stack 
0x88888888



# Nullify the sign, shift it, and memorize it for later
DUP 0 LESSTHAN 
IF 
 ABS
 268435456 TOALTSTACK
ELSE
 0 TOALTSTACK
ENDIF


# Nullify the highest bit, shift it, and memorize it for later
DUP 1073741824 GREATERTHANOREQUAL 
IF 
 1073741824 SUB
 134217728 TOALTSTACK
ELSE
 0 TOALTSTACK
ENDIF



# 27 doublings modulo 2**30 -1

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF




# If the 1st bit was odd we have to subtract 1/2 == 2**29  (mod N)
DUP 536870912 GREATERTHANOREQUAL IF 536870912 SUB ENDIF

# If the 2nd bit was odd we have to subtract 1/4 == 2**28  (mod N)
DUP 268435456 GREATERTHANOREQUAL IF 268435456 SUB ENDIF

# If the 3rd bit was odd we have to subtract 1/8 == 2**27  (mod N)
DUP 134217728 GREATERTHANOREQUAL IF 134217728 SUB ENDIF


# Add the sign and the highest bit
FROMALTSTACK
ADD
FROMALTSTACK
ADD


]"

Bitwise Right Shift by 7 Bits: OP_7RSHIFT

Instruction count: 290


0x88888888



DUP 0 LESSTHAN 
IF 
 ABS
 16777216 TOALTSTACK
ELSE
 0 TOALTSTACK
ENDIF

DUP 1073741824 GREATERTHANOREQUAL 
IF 
 1073741824 SUB
 8388608 TOALTSTACK
ELSE
 0 TOALTSTACK
ENDIF


# 23 doublings modulo 2**30 -1

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF

    DUP ADD
    DUP 1073741823 GREATERTHANOREQUAL IF 1073741823 SUB ENDIF





    # If the 1st bit was odd we have to subtract 1/2 mod N
    DUP 536870912 GREATERTHANOREQUAL IF 536870912 SUB ENDIF

    # If the 2nd bit was odd we have to subtract 1/4 mod N
    DUP 268435456 GREATERTHANOREQUAL IF 268435456 SUB ENDIF

    # If the 3rd bit was odd we have to subtract 1/8 mod N
    DUP 134217728 GREATERTHANOREQUAL IF 134217728 SUB ENDIF

    # If the 4rd bit was odd we have to subtract 1/16 mod N
    DUP 67108864 GREATERTHANOREQUAL IF 67108864 SUB ENDIF

    # If the 5rd bit was odd we have to subtract 1/32 mod N
    DUP 33554432 GREATERTHANOREQUAL IF 33554432 SUB ENDIF

    # If the 6rd bit was odd we have to subtract 1/64 mod N
    DUP 16777216 GREATERTHANOREQUAL IF 16777216 SUB ENDIF

    # If the 7rd bit was odd we have to subtract 1/128 mod N
    DUP 8388608 GREATERTHANOREQUAL IF 8388608 SUB ENDIF






FROMALTSTACK
ADD
FROMALTSTACK
ADD

Generic Implementation

Here's a generic implementation for any number of bits using templates