[vJASS] Bitops

[Aniki]

Bitops is a fork of the Binary library by d07.RiV.

The Binary library implemented the functions NOT, SHL, SHR, AND, OR, XOR for integers wihch did not have their signed bit set.
This library implements the functions as if their arguments are unsigned 32-bit integers (Jass2 has only signed 32-bit integers), it also adds the pow2 and log2 functions.

library Bitops initializer bitops_init

//! novjass

// reference: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Bitwise_Operators

// bitwise not
function NOT takes integer a returns integer

// left shift (a << b)
function SHL takes integer a, integer b returns integer

// zero-fill right shift (a >>> b)
function SHR takes integer a, integer b returns integer

// NOTE: there is no sign-propagating right shift (arithmetic right shift) function

// bitwise AND
function AND takes integer a, integer b returns integer

// bitwise OR
function OR takes integer a, integer b returns integer

// bitwise XOR
function XOR takes integer a, integer b returns integer

// 2^x, x: 0 <= x <= 31
function pow2 takes integer x returns integer

// base 2 logarithm, e.g: log2(256) == 8 because 2^8 = 256
// NOTE: expects only numbers which are powers of two
function log2 takes integer x returns integer

// NOTE: binary operations use lookup tables for 4-bit blocks

//! endnovjass

globals
    // Offsets:
    // 0x000 = powers of 2 (up to 32)
    // 0x100 = AND
    // 0x200 = OR
    // 0x300 = XOR
    //
    private integer array bintable

    private integer array log2_table
endglobals

function NOT takes integer a returns integer
    return -1 - a
endfunction

function SHL takes integer a, integer b returns integer
    return a * bintable[b]
endfunction

function SHR takes integer a, integer b returns integer
    if a >= 0 then
        return  a / bintable[b]
    else
        // set a = a + 0x80000000
        // set a = a / bintable[b]
        // set a = a + bintable[31 - b]
        // return a
        return (a + 0x80000000) / bintable[b] + bintable[31 - b]
    endif
endfunction

private function SAND takes integer a, integer b returns integer
    local integer ta = a / 16
    local integer tb = b / 16
    local integer x = bintable[0x100 + (a - ta * 16) + (b - tb * 16) * 16]
    set a = ta / 16
    set b = tb / 16
    set x = x + bintable[0x100 + (ta - a * 16) + (tb - b * 16) * 16] * 0x00000010
    set ta = a / 16
    set tb = b / 16
    set x = x + bintable[0x100 + (a - ta * 16) + (b - tb * 16) * 16] * 0x00000100
    set a = ta / 16
    set b = tb / 16
    set x = x + bintable[0x100 + (ta - a * 16) + (tb - b * 16) * 16] * 0x00001000
    set ta = a / 16
    set tb = b / 16
    set x = x + bintable[0x100 + (a - ta * 16) + (b - tb * 16) * 16] * 0x00010000
    set a = ta / 16
    set b = tb / 16
    set x = x + bintable[0x100 + (ta - a * 16) + (tb - b * 16) * 16] * 0x00100000
    set ta = a / 16
    set tb = b / 16
    set x = x + bintable[0x100 + (a - ta * 16) + (b - tb * 16) * 16] * 0x01000000
    set a = ta / 16
    set b = tb / 16
    return x + bintable[0x100 + (ta - a * 16) + (tb - b * 16) * 16] * 0x10000000
endfunction

function AND takes integer a, integer b returns integer
    if a >= 0 and b >= 0 then
        return SAND(a, b)
    elseif a < 0 and b < 0 then
        return SAND(a + 0x80000000, b + 0x80000000) + 0x80000000
    else
        if a < 0 then
            set a = a + 0x80000000
        elseif b < 0 then
            set b = b + 0x80000000
        endif
        return SAND(a, b)
    endif
endfunction

private function SOR takes integer a, integer b returns integer
  local integer ta = a / 16
  local integer tb = b / 16
  local integer x = bintable[0x200 + (a - ta * 16) + (b - tb * 16) * 16]
  set a = ta / 16
  set b = tb / 16
  set x = x + bintable[0x200 + (ta - a * 16) + (tb - b * 16) * 16] * 0x00000010
  set ta = a / 16
  set tb = b / 16
  set x = x + bintable[0x200 + (a - ta * 16) + (b - tb * 16) * 16] * 0x00000100
  set a = ta / 16
  set b = tb / 16
  set x = x + bintable[0x200 + (ta - a * 16) + (tb - b * 16) * 16] * 0x00001000
  set ta = a / 16
  set tb = b / 16
  set x = x + bintable[0x200 + (a - ta * 16) + (b - tb * 16) * 16] * 0x00010000
  set a = ta / 16
  set b = tb / 16
  set x = x + bintable[0x200 + (ta - a * 16) + (tb - b * 16) * 16] * 0x00100000
  set ta = a / 16
  set tb = b / 16
  set x = x + bintable[0x200 + (a - ta * 16) + (b - tb * 16) * 16] * 0x01000000
  set a = ta / 16
  set b = tb / 16
  return x + bintable[0x200 + (ta - a * 16) + (tb - b * 16) * 16] * 0x10000000
endfunction

function OR takes integer a, integer b returns integer
    if a >= 0 and b >= 0 then
        return SOR(a, b)
    else
        if a < 0 then
            set a = a + 0x80000000
        endif
        if b < 0 then
            set b = b + 0x80000000
        endif
        return SOR(a, b) + 0x80000000
    endif
endfunction

private function SXOR takes integer a, integer b returns integer
    local integer ta = a / 16
    local integer tb = b / 16
    local integer x = bintable[0x300 + (a - ta * 16) + (b - tb * 16) * 16]
    set a = ta / 16
    set b = tb / 16
    set x = x + bintable[0x300 + (ta - a * 16) + (tb - b * 16) * 16] * 0x00000010
    set ta = a / 16
    set tb = b / 16
    set x = x + bintable[0x300 + (a - ta * 16) + (b - tb * 16) * 16] * 0x00000100
    set a = ta / 16
    set b = tb / 16
    set x = x + bintable[0x300 + (ta - a * 16) + (tb - b * 16) * 16] * 0x00001000
    set ta = a / 16
    set tb = b / 16
    set x = x + bintable[0x300 + (a - ta * 16) + (b - tb * 16) * 16] * 0x00010000
    set a = ta / 16
    set b = tb / 16
    set x = x + bintable[0x300 + (ta - a * 16) + (tb - b * 16) * 16] * 0x00100000
    set ta = a / 16
    set tb = b / 16
    set x = x + bintable[0x300 + (a - ta * 16) + (b - tb * 16) * 16] * 0x01000000
    set a = ta / 16
    set b = tb / 16
    return x + bintable[0x300 + (ta - a * 16) + (tb - b * 16) * 16] * 0x10000000
endfunction

function XOR takes integer a, integer b returns integer
    if a >= 0 and b >= 0 then
        return SXOR(a, b)
    elseif a < 0 and b < 0 then
        return SXOR(a + 0x80000000, b + 0x80000000)
    elseif a < 0 then
        return SXOR(a + 0x80000000, b) + 0x80000000
    else // if  b < 0 then
        return SXOR(a, b + 0x80000000) + 0x80000000
    endif
endfunction

function pow2 takes integer x returns integer
    return bintable[x]
endfunction

function log2 takes integer x returns integer
    if x < 0 then
        return 31
    endif

    if x < 0x00002000 then
        return log2_table[x]
    endif

    set x = x / 0x00002000

    if x < 0x00002000 then
        return 13 + log2_table[x]
    endif

    set x = x / 0x00002000
    return 26 + log2_table[x]
endfunction

private function bitops_init takes nothing returns nothing
    local integer i
    local integer a
    local integer b
    local integer ta
    local integer tb

    set bintable[0] = 1
    set i = 1
    loop
        exitwhen i > 31
        set bintable[i] = 2 * bintable[i - 1]
        set i = i + 1
    endloop

    set i = 0
    loop
        exitwhen i >= 256
        set a = i / 16
        set b = i - a * 16
        set ta = a - (a / 2) * 2
        set tb = b - (b / 2) * 2
        set bintable[0x100 + i] = ta * tb
        set bintable[0x200 + i] = ta + tb - ta * tb
        set bintable[0x300 + i] = ta + tb - 2 * ta * tb
        set a = a / 2
        set b = b / 2
        set ta = a - (a / 2) * 2
        set tb = b - (b / 2) * 2
        set bintable[0x100 + i] = bintable[0x100 + i] + 2 * (ta * tb)
        set bintable[0x200 + i] = bintable[0x200 + i] + 2 * (ta + tb - ta * tb)
        set bintable[0x300 + i] = bintable[0x300 + i] + 2 * (ta + tb - 2 * ta * tb)
        set a = a / 2
        set b = b / 2
        set ta = a - (a / 2) * 2
        set tb = b - (b / 2) * 2
        set bintable[0x100 + i] = bintable[0x100 + i] + 4 * (ta * tb)
        set bintable[0x200 + i] = bintable[0x200 + i] + 4 * (ta + tb - ta * tb)
        set bintable[0x300 + i] = bintable[0x300 + i] + 4 * (ta + tb - 2 * ta * tb)
        set ta = a / 2
        set tb = b / 2
        set bintable[0x100 + i] = bintable[0x100 + i] + 8 * (ta * tb)
        set bintable[0x200 + i] = bintable[0x200 + i] + 8 * (ta + tb - ta * tb)
        set bintable[0x300 + i] = bintable[0x300 + i] + 8 * (ta + tb - 2 * ta * tb)
        set i = i + 1
    endloop

    set log2_table[4096] = 12
    set log2_table[2048] = 11
    set log2_table[1024] = 10
    set log2_table[512] = 9
    set log2_table[256] = 8
    set log2_table[128] = 7
    set log2_table[64] = 6
    set log2_table[32] = 5
    set log2_table[16] = 4
    set log2_table[8] = 3
    set log2_table[4] = 2
    set log2_table[2] = 1
    set log2_table[1] = 0
endfunction

endlibrary

 

[pred1980]

Who need that? Just a question...

 

[Almia]

Who need that? Just a question...

encryption nowadays.

I use it for binary calculations for unsupported numbers.



BTW, for the OP, we already have Bitwise

voting for GY

 

[Aniki]

Bitwise.shiftr is wrong for negative numbers, and it's a bit more LOC.

 

[Kazeon]

Who needs encryption anyway? Does it have other uses other than for save load system?
We already have two save load systems (GUI and vJass) with their own encryption systems. And they are pretty much the last ones to be approved.

 

[Aniki]

Well, stuff like this I guess:

function int2hex takes integer i returns string
    local string hex_chars = "0123456789ABCDEF"
    local string result = ""
    local integer nybel

    set nybel = SHR(i, 28)
    set result = result + SubString(hex_chars, nybel, nybel + 1)

    set nybel = SHR(SHL(i, 4), 28)
    set result = result + SubString(hex_chars, nybel, nybel + 1)

    set nybel = SHR(SHL(i, 8), 28)
    set result = result + SubString(hex_chars, nybel, nybel + 1)

    set nybel = SHR(SHL(i, 12), 28)
    set result = result + SubString(hex_chars, nybel, nybel + 1)

    set nybel = SHR(SHL(i, 16), 28)
    set result = result + SubString(hex_chars, nybel, nybel + 1)

    set nybel = SHR(SHL(i, 20), 28)
    set result = result + SubString(hex_chars, nybel, nybel + 1)

    set nybel = SHR(SHL(i, 24), 28)
    set result = result + SubString(hex_chars, nybel, nybel + 1)

    set nybel = SHR(SHL(i, 28), 28)
    set result = result + SubString(hex_chars, nybel, nybel + 1)

    return result
endfunction

function foo takes integer color returns nothing
    local integer A = SHR(color, 24)
    local integer R = SHR(SHL(color, 8), 24)
    local integer G = SHR(SHL(color, 16), 24)
    local integer B = SHR(SHL(color, 24), 24)
    local integer c = 0

    set c = SHL(A, 24) + SHL(R, 16) + SHL(G, 8) + B

    if c == color then
        call BJDebugMsg(int2hex(c))
    endif
endfunction

globals
    constant integer FOO = 1
    constant integer BAR = 2
    constant integer BAZ = 4
endglobals

function foo_bar_baz takes integer flags returns string
    local string result = ""

    if AND(flags, FOO) != 0 then
        set result = result + "foo"
    endif

    if AND(flags, BAR) != 0 then
        set result = result + "bar"
    endif

    if AND(flags, BAZ) != 0 then
        set result = result + "baz"
    endif

    return result
endfunction

 

[edo494]

library initialization? thats a lot later than it should be realistically

 

[Almia]

library initialization? thats a lot later than it should be realistically

modules is the solution?

 

[edo494]

since this is general use library that does not tie to anything that could prevent it from running before library init, it should run at the soonest possible initializator(so yes module init), because what if I try to do some operation that relies on in inside struct initializer, boom it explodes

 

[edo494]

what I said 4 months ago. + I think you should add support for SSHL and USHL for completness sake, since when you have SXOR, SAND, SOR, SSHR then you reasonably expect there to be SSHL, but then you find out its compilation error, and then you have to go dig the code or the documentation and you find out there indeed is none.

It would obviously delegate to the already implemented version of SHL.

 

[Dr Super Good]

The only operation that should have separate signed and unsigned versions is bitwise right shift. The rest being bitwise operations should always work on both signed and unsigned integers. The only reason there are separate versions is to deal with the lack of bitwise support in JASS meaning it is part of the implementation, and not really the interface.

I would say with exception of USHR which 0 fills and SSHR which fills with the sign bit (should do at least, as is common for signed right shift) all other signed and unsigned functions should be made private to prevent confusion.

 

[edo494]

how do you go on and do unsigned or signed operations then? You would have hard time dispatching that, unless you take like a boolean in AND and that determines whether it is signed or unsigned operation, which could do actually

 

[Dr Super Good]

how do you go on and do unsigned or signed operations then? You would have hard time dispatching that, unless you take like a boolean in AND and that determines whether it is signed or unsigned operation, which could do actually

He does that already...

    if a < 0 or b < 0 then
         return UAND(a, b)
     else
         return SAND(a, b)
     endif

Although that logic seems a bit wrong? Maybe I misunderstanding something.

However as far as binary operations work logically there is no difference between signed and unsigned. Only reason there is a difference here is because JASS lacks native support for them and so has to simulate with lookup tables and arithmetic which is signed.

 

[IcemanBo]

So @edo494 , we approve this and send follwing to gy:

[Snippet] Byte Not
[Snippet] Byte Or
[Snippet] Byte And

?

 

[Cokemonkey11]

Who needs encryption anyway?

Crypto is a bad answer. It's useful for encoding.

 

[edo494]

So @edo494 , we approve this and send follwing to gy:

[Snippet] Byte Not
[Snippet] Byte Or
[Snippet] Byte And

?

Seems like a plan and Im inclined to this decision as well

 

[Cokemonkey11]

Should do some tests first to verify equivalence.

 

[Aniki]

Added some documentation/reference, cleaned up the implementation (I hope it's correct... =)) and added the pow2 and log2 functions.

 

[IcemanBo]

Nice. And also thanks for reference. Systems works well, and will be approved.

Aniki,

make this private:

function SOR takes integer a, integer b returns integer

and change also

function pow2 takes integer x returns integer
->
function Pow2 takes integer x returns integer

and

function log2 takes integer x returns integer
->
function Log2 takes integer x returns integer

to match standard conventions.

// zero-fill right shift (a >>> b)
->
// zero-fill right shift (a >> b)

 

[Aniki]

and change also

function pow2 takes integer x returns integer
->
function Pow2 takes integer x returns integer

and
function log2 takes integer x returns integer
->
function Log2 takes integer x returns integer

to match standard conventions.

Line 1234: error identifier "Log2" previously defined as struct

// zero-fill right shift (a >>> b)
->
// zero-fill right shift (a >> b)

I used the >>> operator (the zero-fill right shift in JavaScript [and Java?]), because the reference/documentation is for JavaScript.

PS: the standard is wrong =)

 

[IcemanBo]

I used the
>>>
operator (the zero-fill right shif

Ah, yes, okay.