-
-
Notifications
You must be signed in to change notification settings - Fork 1
Scratchpad: Nin receives a lesson in bit field arithmetic
Ninlilizi01/12/2018 Can someone who knows this stuff confirm the snippet I'm about to paste does what I intended it to do..... which is to update an occupancy bitfield containing the occupied state of the voxel at the given coord.? inline void setOccupancyBit(float3 coord, bool occupied) { // Get get bit and byte index uint indexByte = coord.z * (voxelResolution * voxelResolution) + (coord.y * voxelResolution) + coord.x; uint indexBit = indexByte % 8;
// Retrieve current index payload
uint currentValue = voxelOccupancyBuffer1[indexByte];
// Unpack payload
bool bitArray[32];
bitArray[0] = fmod(currentValue, 2) == 1;
bitArray[1] = fmod(currentValue, 4) >= 2;
bitArray[2] = fmod(currentValue, 8) >= 4;
bitArray[3] = fmod(currentValue, 16) >= 8;
bitArray[4] = fmod(currentValue, 32) >= 16;
bitArray[5] = fmod(currentValue, 64) >= 32;
bitArray[6] = fmod(currentValue, 128) >= 64;
bitArray[7] = fmod(currentValue, 256) >= 128;
// Update bit
bitArray[indexBit] = occupied;
// Repack payload
uint newValue =
(bitArray[0] ? 1 : 0) |
(bitArray[1] ? 2 : 0) |
(bitArray[2] ? 4 : 0) |
(bitArray[3] ? 8 : 0) |
(bitArray[4] ? 16 : 0) |
(bitArray[5] ? 32 : 0) |
(bitArray[6] ? 64 : 0) |
(bitArray[7] ? 128 : 0);
// Store new value
voxelOccupancyBuffer1[indexByte] = newValue;
} The idea is that I maintain a bitfield of occupancy state of each voxel in the grid..... So I appease the memory bandwidth bottlekneck by using this to avoid sampling empty voxels So instead of searching through 512MB of data for a hit...... your searching thru @138kB of data instead.... So a form of sparseish tracing obviously this example is only storing 8 bits .... when a uint is 32bit...... but I truncated... otherwise it would be a pointlessly long paste 😄
shinyclef01/12/2018 you have a bunch of uints, each storing 32 bits, where each bit represents one voxel being occupied or not?
Ninlilizi01/12/2018 yes
shinyclef01/12/2018 and this method sets the appropriate bit to 1 or 0
Ninlilizi01/12/2018 yes... hopefully
shinyclef01/12/2018 I have a feeling this is way more operations than needed
Ninlilizi01/12/2018 I wrote this myself.... wasn't a yoink from the web.... So verifying I did the right thing prob a far more optimum way of doing it
shinyclef01/12/2018 I'm unsure about CG, I have done this sort of thing in C# though Can I perhaps write c# syntax for how I might go about this...
Ninlilizi01/12/2018 sure converting to compute happy synatix is fairly easy for me at this point
shinyclef01/12/2018 uint bitMask; // some uint storing bits int bitPos = 5; // example
// set the bit to 1 bitMask = bitMask | (1 << bitPos);
// set the bit to 0 bitMask = bitMask & ~(1 << bitPos); this is the general principal it uses bitwise operations have you used them before?
Ninlilizi01/12/2018 No..... Time to go do some reading
shinyclef01/12/2018 they are very cool, I'm just not sure what's supported in CG but basically, it's like this: byte a = 00110011; byte b = 11001100; Here are two bytes You have bitwise AND and bitwise OR
Ninlilizi01/12/2018 I'm finding support of esotreric stuff kinda hit and miss..... And just because google says a thing is supported or not..... Doesn't mean that's actually the case in the target environment
shinyclef01/12/2018 '&' is the bitwise ANd operator (as opposed to '&&') '|' is the bitwise OR operator (as opposed to '||') a & b == 00000000 a | b == 11111111 the way it works is for example, the 'and' every bit is compared so bit 1 of a and bit 1 of b are compered with an AND 0 && 1 == 0 and same with the rest of the bits
Ninlilizi01/12/2018 right
shinyclef01/12/2018 each pair is a 0 and a 1 so the result is 00000000 and with with OR, each pair has a 1, so results in 11111111 byte a = 11110000; byte b = 00110011; a & b == ? homework question 😛
Ninlilizi01/12/2018 00000000?
shinyclef01/12/2018 compare each bit pair with an && operation, to get 8 new bits so the first pair is: 1 0
Ninlilizi01/12/2018 0
shinyclef01/12/2018 then the second par
Ninlilizi01/12/2018 oh
shinyclef01/12/2018 keep doing it for all 8 pairs
Ninlilizi01/12/2018 boolean logic
shinyclef01/12/2018 exactly just, 'for each bit'
Ninlilizi01/12/2018 brains feebly farts into motion
shinyclef01/12/2018 so what's the answer 😛
Ninlilizi01/12/2018 00110000
shinyclef01/12/2018 exactly, now what's a | b same thing, just do 'or' instead
Ninlilizi01/12/2018 11110011
shinyclef01/12/2018 cool
Ninlilizi01/12/2018 yay \o/
shinyclef01/12/2018 so that's step one to understanding the code uint bitMask; // some uint storing bits int bitPos = 5; // example
// set the bit to 1 bitMask = bitMask | (1 << bitPos);
// set the bit to 0 bitMask = bitMask & ~(1 << bitPos); you can see the bitwise AND and OR in there next step is the bitshift << bitshift is pretty easy 00000001 << 1 == 00000010
Ninlilizi01/12/2018 gotcha
shinyclef01/12/2018 it moves all the bits one to the left 00001010 << 4 == 10100000
Ninlilizi01/12/2018 awesome
shinyclef01/12/2018 overflow just overflows so 00001000 << 5 == 00000000 just lost the 5 ok so, so far so good?
Ninlilizi01/12/2018 yep sweet.... that's super helpful
shinyclef01/12/2018 so now put these two ideas together. "How can I set one bit to a 1?" well, which bit? let's say "the 3rd bit from the left" 00000100 that 1 is where I want the 1 to be I don't actually care what all the other bits are just want that one to be a 1
Ninlilizi01/12/2018 I get it
shinyclef01/12/2018 well, we can use a bitwise OR byte myByte = WHATEVER; int targetBit = 3; int bitShift = 1 << (targetBit - 1); // bitShift == 00000100 sorry wrong there we go we start with 1 (00000001), then move that bit into the correct position 00000100 next myByte = myByte | bitShift; now I just took myByte, and made sure that bit is 1 all the other bits will be unchanged so far so good?
Ninlilizi01/12/2018 yes
shinyclef01/12/2018 ok, so that's how you 'set a bit to 1' now how to 'set a bit to 0' 10101010 // original byte 00000100 // our mask 10101110 // result of OR operation ok now how to unset that same bit: 10101110 // original byte 11111011 // our mask 10101010 // result of AND operation so in that one, the byte we want to set to 0 is 0, everything else is 1, and we do an AND does that make sense?
Ninlilizi01/12/2018 yes... perfect
shinyclef01/12/2018 ok so the last piece of the puzzle is, how to get a byte looking like 11111011 start with 00000100 like this: 1 << 2 then INVERT it with ~ ~(1 << 2) == 11111011 all good there?
Ninlilizi01/12/2018 yes
shinyclef01/12/2018 uint bitField; // some uint storing bits int bitPos = 5; // example
// set the bit to 1 int bitMask = (1 << bitPos - 1); bitField = bitField | bitMask;
// set the bit to 0 int bitMask = ~(1 << bitPos - 1); bitField = bitField & bitMask; that's the final concept everything in that block should now be understandable
Ninlilizi01/12/2018 yes... Great
shinyclef01/12/2018 except I don't like the names
Ninlilizi01/12/2018 Totally excited now for all the optimization this new found power unlocks ^_^
shinyclef01/12/2018 ok so your last step is going to be figuring out which bit you want to be setting
Ninlilizi01/12/2018 is this not sufficient? // Get get bit and byte index uint indexByte = coord.z * (voxelResolution * voxelResolution) + (coord.y * voxelResolution) + coord.x; uint indexBit = indexByte % 32;
shinyclef01/12/2018 maybe the naming is confusing me uint indexByte = coord.z * (voxelResolution * voxelResolution) + (coord.y * voxelResolution) + coord.x; so with this line... we are getting the 'flat index' back? looks like it
Ninlilizi01/12/2018 yes.... I eventually want to read and write from a compute buffer so 3d to 1d
shinyclef01/12/2018 yes, then it looks like 'indexBit' will be the correct bit indexByte is not a byte though 😛
Ninlilizi01/12/2018 fair point
shinyclef01/12/2018 you still need to get the right byte so with values 0 to 127... if you are looking up... let's say, 55 55 will be in the second byte first byte == 0-31, second byte == 32-63 sorry no that's ints my bad so if you are storing an array of uints you need to pull out the second uint that uint is your bitfield ok so this is completely unchecked written in notepad... bool isOccupied = true;
// Get get bit and byte index uint voxelIndex = coord.z * (voxelResolution * voxelResolution) + (coord.y * voxelResolution) + coord.x; uint bitFieldIndex = Floor(voxelIndex / 32); uint targetBit = voxelIndex % 32;
uint bitField = MyUintArray[bitFieldIndex];
if (isOccupied) { // set the bit to 1 int bitMask = (1 << targetBit); bitField = bitField | bitMask; } else { // set the bit to 0 int bitMask = ~(1 << targetBit); bitField = bitField & bitMask; )
MyUintArray[bitFieldIndex] = bitField;
Ninlilizi01/12/2018 ah... I'd missed a step.. I see now
shinyclef01/12/2018 correction applied because 'targetBit ' is always going to be 0-31, it doesn't need the -1 so the name is prob's not the best anymore haha, maybe 'bitShift' is a better name now, but whatever you like 😃 ok, so, now you know how to SET a bit to 0 or 1 I assume you are at some point going to want to CHECK if the value is 0 or 1?
Ninlilizi01/12/2018 yes I take it there's a bitwise return a bit function?
shinyclef01/12/2018 yes, you need to be using bitwise operations for that too 😛 byte orig = 11001010 // example byte being checked byte mask = 00001000 // we're checking on 4th byte from the right (1 << 3) bool isOccupied == ... can you figure this part out?
Ninlilizi01/12/2018 Can I just shunt it along to the left? and do an and?
shinyclef01/12/2018 assuming you already did that step, so you have your mask already You want to know if that 4th bit in 'orig' is set, like it is in 'mask'. public bool IsOccupied(float3 coord) { // Get get bit and byte index uint voxelIndex = coord.z * (voxelResolution * voxelResolution) + (coord.y * voxelResolution) + coord.x; uint bitFieldIndex = Floor(voxelIndex / 32); uint targetBit = voxelIndex % 32;
uint bitField = MyUintArray[bitFieldIndex];
// IS IT SET?
int bitMask = (1 << targetBit);
bool isOccupied == ...
return isOccupied;
} 2nd last line is for homework 😄 brb while you think on that 😄 or I could just tell you? heh, it's not immediately apparent first time with bitwise
Ninlilizi01/12/2018 I'm sure I'll figure it out if I stare at it long enough
shinyclef01/12/2018 ok so the answer is
Ninlilizi01/12/2018 bool isOccupied == bitField & bitMask; ?
shinyclef01/12/2018 very cloosseee so what you have there is...
Ninlilizi01/12/2018 is it an or insteasd?
shinyclef01/12/2018 nope you tried to assign a byte to a bool
Ninlilizi01/12/2018 damn, lol
shinyclef01/12/2018 bitField & bitMask will give you a byte back, or a uint in your case because bitMast == 00001000, for example
Ninlilizi01/12/2018 do I need to subtract that from the original byte?
shinyclef01/12/2018 in other words, you're checking for a 1 in one of the bits, and all other bits are 0 right?
Ninlilizi01/12/2018 yes
shinyclef01/12/2018 so, the resuld of doing an & using bitMask will either be 00000000 (if the & did not match on the orig byte) or 00001000, if it did match right?
Ninlilizi01/12/2018 can you shunt bits in both directions?
shinyclef01/12/2018 so with our mask of 00001000
11111111 // Match 00000000 // No Match 10101010 // Match 01010101 // No Match that makes sense right?
Ninlilizi01/12/2018 nope oh. yes
shinyclef01/12/2018 cool, so if we are doing an & between our mask and each of those other bytes... match means that the bit we are actually looking for was there so, when there is a match, what will the resulting byte look like? taking the first byte as the example: 00001000 11111111 00001000 // RESULT
Ninlilizi01/12/2018 0?
shinyclef01/12/2018 00001000 00000000 00000000 // RESULT the result is ALWAYS either 00001000 or 00000000 the other bits are irrelevant, cause we're doing an AND with 0s there so they will ALWAYS be 0 the only bit that can change, is the 1 in the mask so > 0 will work but usually people will do... public bool IsOccupied(float3 coord) { // Get get bit and byte index uint voxelIndex = coord.z * (voxelResolution * voxelResolution) + (coord.y * voxelResolution) + coord.x; uint bitFieldIndex = Floor(voxelIndex / 32); uint targetBit = voxelIndex % 32;
uint bitField = MyUintArray[bitFieldIndex];
// IS IT SET?
int bitMask = (1 << targetBit);
bool isOccupied == bitMask & bitField == bitMask; // bitMask & bitField > 0 will also work
return isOccupied;
} if the result is the same as the bitmask, that means the 1 was present in the bitField. If it was converted to a 0, it was 0 in the bitField. I hope that makes sense but yes, a >0 will also work there heh
Ninlilizi01/12/2018 just about
shinyclef01/12/2018 you could even do `bitMask & bitField != 0' pick your flavour
Ninlilizi01/12/2018 != also floated thru my brain
byte a = 00000001; a & x = 00000000; bool bitSet = a & x != 0; // false byte b = 00000010; b & x = 00000000; bool bitSet = b & x != 0; // false byte c = 00000100; c & x = 00000100; bool bitSet = c & x != 0; // true byte d = 00001000; d & x = 00001000; bool bitSet = d & x != 0; // true byte e = 00010000; e & x = 00000000; bool bitSet = e & x != 0; // false byte f = 00100000; f & x = 00000000; bool bitSet = f & x != 0; // false byte g = 01000000; g & x = 01000000; bool bitSet = g & x != 0; // true byte h = 10000000; h & x = 10000000; bool bitSet = h & x != 0; // true I hope that drives the message home...
Ninlilizi01/12/2018 I'm saving this entire conversation to refer to during a less brain foggy moment
neoshaman01/12/2018
anyway just in case you want to deepen the bit fu :
https://bisqwit.iki.fi/story/howto/bitmath/
http://graphics.stanford.edu/~seander/bithacks.html
2 links full of awesome bit tricks