Using Shift on Binary

In wrestling with an older file format, it's notable how entrenched 32-bit numbers are (for bit fiddling purposes) within big specifications. JavaScript itself (I believe) converts its numbers to 32-bit for the purposes of its <<, >> and >>> operators.

As R3 Alpha and Ren-C shifts on 64-bit signed integers, it is not then compatible with some of those older specification. Thus I was trying to twist my brain into figuring out how bridge the gap. In short, I gave up and went with this approach which, while appalling, works as intended:

bits-zero: enbase/base #{0000000000000000} 2
bits-one: enbase/base #{FFFFFFFFFFFFFFFF} 2

brute-force-shift: func [
    value [binary!]
    bits [integer!]
    /logical
    <local> length is-negative
][
    length: 8 * length-of value
    not-negative: zero? 128 and+ value/1
    value: enbase/base value 2

    case [
        not negative? bits [
            insert reverse value skip bits-zero 64 - bits
            reverse head clear skip value length
        ]

        any [
            logical
            not-negative
        ][
            insert value skip tail bits-zero bits
            head clear skip value length
        ]

        <else> [
            insert value skip tail bits-one bits
            head clear skip value length
        ]
    ]

    debase/base value 2
]

It works on binary! values up to 8 bytes and operates based on whatever the width of the input binary is, thus can be used along with enbin/debin to operate on integer! values at any desired width.

While it'd be useful to have a native version that operated on integer! with enbin/debin-like paramaters, my case use only needed the op on a binary! value without the round trip.

1 Like

Some tests (all assume [be +/- 4] conversion):

[expected mode value bits]
[-8 arithmetic -2 2]
[402653184 arithmetic 3 27]
[3 arithmetic 402653184 -27]
[-37 arithmetic -1184 -5]
[37 arithmetic 1184 -5]
[-8388608 arithmetic -2147483648 -8]
[1 arithmetic 2 -1]
[16 arithmetic 2 3]
[-2 arithmetic -4 -1]
[2147483646 logical -4 -1]
[8388608 logical -2147483648 -8]
[1073741820 logical -16 -2]
[-64 logical -16 2]
[-37888 logical -1184 5]
[134217691 logical -1184 -5]

Since there is a binary type, defining SHIFT on BINARY! makes the most sense.

Platform-integer-sized shifts are most efficient, but I don't think it's the kind of efficiency we should be hung up on. I'll also point out that platform signed shifts have issues with defined/undefinedness.

I'm not a fan of SHIFT not labeled by a direction. It would seem to me to be better to define SHIFT-RIGHT and SHIFT-LEFT ... where if you use the negative sign, that goes the opposite direction of what the name says. LSHIFT and RSHIFT could be shorthands, and << and >> perhaps in the BITWISE dialect (if that ever gets figured out).

(Maybe SHIFT could take a quoted WORD! and be cleanly written as shift left xxx or shift right xxx?)

Rotating bits is something that comes up sometimes--where the bits you shift out one side come back in on the other. Though I've not really had it come up lately.

Even putting together tests, it was not intuitive thinking of direction in terms of positive/negative.

I figure that's because they go straight to the metal? I fear though that 32-bit integer ops are going to be with us for a looong time. That they are standard for bitwise operations in JavaScript alone means that they will persist :scream:

What would they typically be used for?

A version atop existing SHIFT. Should be faster. Changed interface to
shift-binary <value> [left | right | logical] <bits>

shift-binary: func [
    value [binary!]
    'mode [word!]
    bits [integer!]
    <local> width carry-bits mask next-carry-bits
][
    assert [find [left right logical] mode]

    either mode = 'left [
        while [bits >= 8] [
            bits: me - 8
            append remove value 0
        ]

        carry-bits: 0
        mask: shift (-1 + shift 1 bits) 8 - bits

        if not zero? bits [
            for-back offset tail value [
                next-carry-bits: shift offset/1 and+ mask bits - 8
                offset/1: 255 and+ (shift offset/1 bits) or+ carry-bits
                carry-bits: next-carry-bits
            ]
        ]
    ][
        either any [
            mode = 'logical
            zero? 128 and+ value/1
        ][
            while [bits >= 8] [
                bits: me - 8
                remove back tail insert value 0
            ]

            carry-bits: 0
        ][
            while [bits >= 8][
                bits: me - 8
                remove back tail insert value 255
            ]

            carry-bits: shift (-1 + shift 1 bits) 8 - bits
        ]

        mask: -1 + shift 1 bits

        if not zero? bits [
            for-next offset value [
                next-carry-bits: shift offset/1 and+ mask 8 - bits
                offset/1: 255 and+ (shift offset/1 negate bits) or+ carry-bits
                carry-bits: next-carry-bits
            ]
        ]
    ]

    value
]

Tests for this updated function:

[         expected      result mode  bits width]

[               -8          -2 left     2 4]
[               16           2 left     3 4]
[           -37888       -1184 left     5 4]
[                0   134217728 left     5 4]
[       -536870912   251658240 left     5 4]
[       8053063680   251658240 left     5 8]
[        402653184           3 left    27 4]
[                1           2 right    1 4]
[               -2          -4 right    1 4]
[               37        1184 right    5 4]
[              -37       -1184 right    5 4]
[         -8388608 -2147483648 right    8 4]
[           707912  5799218898 right   13 8]
[                3   402653184 right   27 4]
[       2147483646          -4 logical  1 4]
[       1073741820         -16 logical  2 4]
[        134217691       -1184 logical  5 4]
[          8388608 -2147483648 logical  8 4]
[72057594029539328 -2147483648 logical  8 8]

; languages using 32-bit bitwise ops truncate a large number;
; would need to actively truncate the number here before passing to enbin
; in order to emulate
; [183624 5799218898 right 13 4]

A wee wrapper for when you need that 32-bit itch scratched:

shift-32: func [
    value [integer!]
    'mode [word!]
    bits [integer!]
][
    debin [be +/- 4] shift-binary enbin [be +/- 4] value :mode bits
]

Usage:

>> shift-32 2 left 2  ; <<
== 8

>> shift-32 8 right 2  ; >>
== 2

>> shift-32 -8 logical 24  ; >>>
== 255