Binary integer operations

08-05-2008, 07:48 AM

Implements NOT, AND, OR, XOR, SHL and SHR binary operations (bitwise not, and, or, xor, shift left, shift right)
It find it hard coming up with a real use for it except implementing standard hash methods like crc32 if you ever need them.

To use the non-vjass version, create an integer array called bintable and then either place the system code in trigger called Binary (but there is no way to make sure it can be used by other triggers) or put it in custom script and call InitTrig_Binary from any initialization function.
vJass users probably know what to do, just create a trigger, convert it to text and paste the code.

It builds a table of powers of 2 for shifts, and tables of AND/OR/XOR for all pairs of integers 0..15.
If anyone can think of a way to optimize it significantly (removing an operation or so doesn't count), it would be great.

vJass version

JASS:

library Binary initializer InitBinary

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

// just hope it gets inlined in future
function NOT takes integer a returns integer
  return -1 - a
endfunction
// binary operations use lookup tables for 4-bit blocks
function AND 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 OR 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 XOR 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
// shift left/right. DO NOT use negative values, this should get inlined as well
function SHL takes integer a, integer b returns integer
  return a * bintable[b]
endfunction
function SHR takes integer a, integer b returns integer
  return a / bintable[b]
endfunction

private function InitBinary takes nothing returns nothing
  local integer i = 0
  local integer a
  local integer b
  local integer ta
  local integer tb
  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 i = 1
  set bintable[0] = 1
  loop
    exitwhen i > 31
    set bintable[i] = bintable[i - 1] * 2
    set i = i + 1
  endloop
endfunction
endlibrary

Non-vJass version

JASS:

// Offsets into udg_bintable:
// 0x000 = powers of 2 (up to 32)
// 0x100 = AND
// 0x200 = OR
// 0x300 = XOR

// just hope it gets inlined in future
function NOT takes integer a returns integer
  return -1 - a
endfunction
// binary operations use lookup tables for 4-bit blocks
function AND takes integer a, integer b returns integer
  local integer ta = a / 16
  local integer tb = b / 16
  local integer x = udg_bintable[0x100 + (a - ta * 16) + (b - tb * 16) * 16]
  set a = ta / 16
  set b = tb / 16
  set x = x + udg_bintable[0x100 + (ta - a * 16) + (tb - b * 16) * 16] * 0x00000010
  set ta = a / 16
  set tb = b / 16
  set x = x + udg_bintable[0x100 + (a - ta * 16) + (b - tb * 16) * 16] * 0x00000100
  set a = ta / 16
  set b = tb / 16
  set x = x + udg_bintable[0x100 + (ta - a * 16) + (tb - b * 16) * 16] * 0x00001000
  set ta = a / 16
  set tb = b / 16
  set x = x + udg_bintable[0x100 + (a - ta * 16) + (b - tb * 16) * 16] * 0x00010000
  set a = ta / 16
  set b = tb / 16
  set x = x + udg_bintable[0x100 + (ta - a * 16) + (tb - b * 16) * 16] * 0x00100000
  set ta = a / 16
  set tb = b / 16
  set x = x + udg_bintable[0x100 + (a - ta * 16) + (b - tb * 16) * 16] * 0x01000000
  set a = ta / 16
  set b = tb / 16
  return x + udg_bintable[0x100 + (ta - a * 16) + (tb - b * 16) * 16] * 0x10000000
endfunction
function OR takes integer a, integer b returns integer
  local integer ta = a / 16
  local integer tb = b / 16
  local integer x = udg_bintable[0x200 + (a - ta * 16) + (b - tb * 16) * 16]
  set a = ta / 16
  set b = tb / 16
  set x = x + udg_bintable[0x200 + (ta - a * 16) + (tb - b * 16) * 16] * 0x00000010
  set ta = a / 16
  set tb = b / 16
  set x = x + udg_bintable[0x200 + (a - ta * 16) + (b - tb * 16) * 16] * 0x00000100
  set a = ta / 16
  set b = tb / 16
  set x = x + udg_bintable[0x200 + (ta - a * 16) + (tb - b * 16) * 16] * 0x00001000
  set ta = a / 16
  set tb = b / 16
  set x = x + udg_bintable[0x200 + (a - ta * 16) + (b - tb * 16) * 16] * 0x00010000
  set a = ta / 16
  set b = tb / 16
  set x = x + udg_bintable[0x200 + (ta - a * 16) + (tb - b * 16) * 16] * 0x00100000
  set ta = a / 16
  set tb = b / 16
  set x = x + udg_bintable[0x200 + (a - ta * 16) + (b - tb * 16) * 16] * 0x01000000
  set a = ta / 16
  set b = tb / 16
  return x + udg_bintable[0x200 + (ta - a * 16) + (tb - b * 16) * 16] * 0x10000000
endfunction
function XOR takes integer a, integer b returns integer
  local integer ta = a / 16
  local integer tb = b / 16
  local integer x = udg_bintable[0x300 + (a - ta * 16) + (b - tb * 16) * 16]
  set a = ta / 16
  set b = tb / 16
  set x = x + udg_bintable[0x300 + (ta - a * 16) + (tb - b * 16) * 16] * 0x00000010
  set ta = a / 16
  set tb = b / 16
  set x = x + udg_bintable[0x300 + (a - ta * 16) + (b - tb * 16) * 16] * 0x00000100
  set a = ta / 16
  set b = tb / 16
  set x = x + udg_bintable[0x300 + (ta - a * 16) + (tb - b * 16) * 16] * 0x00001000
  set ta = a / 16
  set tb = b / 16
  set x = x + udg_bintable[0x300 + (a - ta * 16) + (b - tb * 16) * 16] * 0x00010000
  set a = ta / 16
  set b = tb / 16
  set x = x + udg_bintable[0x300 + (ta - a * 16) + (tb - b * 16) * 16] * 0x00100000
  set ta = a / 16
  set tb = b / 16
  set x = x + udg_bintable[0x300 + (a - ta * 16) + (b - tb * 16) * 16] * 0x01000000
  set a = ta / 16
  set b = tb / 16
  return x + udg_bintable[0x300 + (ta - a * 16) + (tb - b * 16) * 16] * 0x10000000
endfunction
// shift left/right. DO NOT use negative values, this should get inlined as well
function SHL takes integer a, integer b returns integer
  return a * udg_bintable[b]
endfunction
function SHR takes integer a, integer b returns integer
  return a / udg_bintable[b]
endfunction

function InitTrig_Binary takes nothing returns nothing
  local integer i = 0
  local integer a
  local integer b
  local integer ta
  local integer tb
  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 udg_bintable[0x100 + i] = ta * tb
    set udg_bintable[0x200 + i] = ta + tb - ta * tb
    set udg_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 udg_bintable[0x100 + i] = udg_bintable[0x100 + i] + 2 * (ta * tb)
    set udg_bintable[0x200 + i] = udg_bintable[0x200 + i] + 2 * (ta + tb - ta * tb)
    set udg_bintable[0x300 + i] = udg_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 udg_bintable[0x100 + i] = udg_bintable[0x100 + i] + 4 * (ta * tb)
    set udg_bintable[0x200 + i] = udg_bintable[0x200 + i] + 4 * (ta + tb - ta * tb)
    set udg_bintable[0x300 + i] = udg_bintable[0x300 + i] + 4 * (ta + tb - 2 * ta * tb)
    set ta = a / 2
    set tb = b / 2
    set udg_bintable[0x100 + i] = udg_bintable[0x100 + i] + 8 * (ta * tb)
    set udg_bintable[0x200 + i] = udg_bintable[0x200 + i] + 8 * (ta + tb - ta * tb)
    set udg_bintable[0x300 + i] = udg_bintable[0x300 + i] + 8 * (ta + tb - 2 * ta * tb)
    set i = i + 1
  endloop
  set i = 1
  set udg_bintable[0] = 1
  loop
    exitwhen i > 31
    set udg_bintable[i] = udg_bintable[i - 1] * 2
    set i = i + 1
  endloop
endfunction

08-05-2008, 12:44 PM	#2
DioD	omg LOL but no, usefull for hash calculations.

08-05-2008, 01:07 PM	#3
BlinkBoy	It's usefull, yet the functions are way too slow to give them a true use.

08-05-2008, 01:34 PM	#4
d07.RiV	I cant think of a faster way to do it and its all because blizzards forgot to make these functions .. But this should be enough for computing crc32 or storm-like hash.

08-05-2008, 01:36 PM	#5
Vexorian	I might end up banning stuff using udg_ prefixes. Or at least make the vJass version that uses udg_ require to be scoped and the udg_ stuff to be private. It is a huge regression to use that prefix.

08-05-2008, 01:44 PM	#6
d07.RiV	It is for compatibility with non-vjass users. Just put library..endlibrary and private keyword. Ok I'll split it in 2.

08-06-2008, 02:11 PM	#7
ADOLF	imho only not and shr/l useful, all another to slow and big)

08-06-2008, 06:34 PM	#8
d07.RiV	You wanted to use them in 0.04 timers?

08-07-2008, 08:48 AM

ADOLF

Quote:

You wanted to use them in 0.04 timers

no, but in .025 - maybe)

Quote:

If anyone can think of a way to optimize it significantly

in shifts it is possible to use at once values directly, instead of to take from a array (if it is known at once) ^^

08-07-2008, 10:04 PM	#10
Vexorian	All right, I am liking the implementations, could you provide benchmarks about the naive "loop through all the bits" implementations? Approved though.

08-08-2008, 12:36 AM

#11

d07.RiV

Ok 4x difference between this and AND of medium sillyness:

JASS:

scope Test

globals
  integer sw = StopWatchCreate ()
endglobals

function SILLYAND takes integer a, integer b returns integer
  local integer r = 0
  local integer p = 1
  local integer a2
  local integer b2
  loop
    exitwhen a == 0 or b == 0
    set a2 = a / 2
    set b2 = b / 2
    set r = r + (a - a2 * 2) * (b - b2 * 2) * p
    set p = p * 2
    set a = a2 / 2
    set b = b2 / 2
    set r = r + (a2 - a * 2) * (b2 - b * 2) * p
    set p = p * 2
  endloop
  return r
endfunction

function Test takes nothing returns nothing
  local real r = StopWatchMark (sw)
  local integer i = 0
  loop
    exitwhen i >= 100
//    call SILLYAND (0x12345678, 0x87654321)
    call AND (0x12345678, 0x87654321)
    set i = i + 1
  endloop
  set r = StopWatchMark (sw) - r
  call BJDebugMsg ("Time: " + R2S (r))
endfunction

public function InitTrig takes nothing returns nothing
  call ExecuteFunc ("Test")
endfunction

endscope