  Wc3C.net Binary integer operations
 Register Rules Get Hosted! Chat Pastebin FAQ and Rules Members List Calendar 08-05-2008, 08:48 AM #1 d07.RiV User   Join Date: May 2008 Posts: 241 Submissions (1)  Binary integer operations 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 = 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 = 1 loop exitwhen i > 31 set udg_bintable[i] = udg_bintable[i - 1] * 2 set i = i + 1 endloop endfunction ``` __________________ Last edited by d07.RiV : 08-08-2008 at 01:29 AM.   08-05-2008, 01:44 PM #2 DioD obey   Join Date: Feb 2006 Posts: 1,532 Submissions (4)     omg LOL but no, usefull for hash calculations.   08-05-2008, 02:07 PM #3 BlinkBoy User Respected User   Join Date: Dec 2003 Posts: 835 Submissions (4)      It's usefull, yet the functions are way too slow to give them a true use. __________________ Tools: NeoDex - a Gmax and 3ds Max modeling Toolset for Wc3! Learn to animate! check out my: Basic Animation Tutorial! Currently working at a sequel to my animation tutorial.   08-05-2008, 02:34 PM #4 d07.RiV User   Join Date: May 2008 Posts: 241 Submissions (1)  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, 02:36 PM   #5
Vexorian
Free Software Terrorist

Technical Director

Join Date: Apr 2003
Posts: 14,898

Submissions (37)         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.
__________________ Wc3 map optimizer 5.0 Someone should fix .wav sound in this thing. JassHelper 0.A.2.A Turns your simple code into something that is complicated enough to work.
 Wc3 map optimizer 5.0 JassHelper 0.A.2.A Xye 0.12.1 | Editor/Levels xe0.9 CS16.0 My spells jEdit modes for vJass&Zinc (v9) WarCiTy 0.2.0
Faster != more useful   08-05-2008, 02:44 PM #6 d07.RiV User   Join Date: May 2008 Posts: 241 Submissions (1)  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, 03:11 PM   #7
User from USSR

Join Date: Jan 2007
Posts: 127

Submissions (3)   imho only not and shr/l useful, all another to slow and big)
__________________ cJass   08-06-2008, 07:34 PM #8 d07.RiV User   Join Date: May 2008 Posts: 241 Submissions (1)  You wanted to use them in 0.04 timers? __________________ Last edited by d07.RiV : 08-06-2008 at 11:21 PM.   08-07-2008, 09:48 AM   #9
User from USSR

Join Date: Jan 2007
Posts: 127

Submissions (3)   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) ^^
__________________ cJass   08-07-2008, 11:04 PM   #10
Vexorian
Free Software Terrorist

Technical Director

Join Date: Apr 2003
Posts: 14,898

Submissions (37)         All right, I am liking the implementations, could you provide benchmarks about the naive "loop through all the bits" implementations?

Approved though.
__________________ Wc3 map optimizer 5.0 Someone should fix .wav sound in this thing. JassHelper 0.A.2.A Turns your simple code into something that is complicated enough to work.
 Wc3 map optimizer 5.0 JassHelper 0.A.2.A Xye 0.12.1 | Editor/Levels xe0.9 CS16.0 My spells jEdit modes for vJass&Zinc (v9) WarCiTy 0.2.0
Faster != more useful   08-08-2008, 01:36 AM #11 d07.RiV User   Join Date: May 2008 Posts: 241 Submissions (1)  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 ``` __________________   Thread Tools Search this Thread Show Printable Version Email this Page Search this Thread: Advanced Search Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts vB code is On Smilies are On [IMG] code is On HTML code is Off

All times are GMT. The time now is 03:38 PM.

 -- Night Elf -- Tauren -- Troll -- Pandaren -- Underworld -- Blood Elf -- Northrend -- Lightning ---- Light-ning -- Arcane -- Diablo III -- Protoss -- Mobile Version Wc3campaigns - Archive - Top 