GML Bit shifting, need some help if possible.

[IGameArt]

Hey guys, I need some help translating some code I found online for a new feature being implemented into DopeFish, my Doom wad loader for GM.

I'm trying to utilize the gl_pvs format created originally for the Vavoom source port, however low level code like this is something I'm fairly inexperienced with.

In the buffer loaded from the wad file is a chunk of data called a lump. There are several lumps that represent several different types of data, like sprites, textures, maps, or helper nodes. GL_PVS is one of those helper nodes.

glVIS is a PVS (Potentially Visible Set) builder specially designed to be used with OpenGL ports of the DOOM game engine. It extends the “GL-Friendly Nodes” with a new lump named “GL_PVS”. Basically it’s a subsector accept table designed for rendering engine to skip the subsectors that can’t be visible from viewer’s subsector.

So the GL_PVS lump is essentially a buffer copied to memory from within the wad file. It contains a sort of lookup table of all of the visibility states of any part of the map from any other part of the map. Having access to this table would make it so the renderer could skip over rendering any parts of the map that aren't visible from the camera's current location.

The format for finding where to look in the buffer for the results of your current subsector (chunk of the level) are all follows:
((numsubsectors + 7) / 8) * i

The example for how to find the visibility of a subsector i is as follows:

     byte *vis_data;    // PVS lump
     int view_sub;      // Num of subsector, where the player is
     byte *vis;
     vis = vis_data + (((numsubsectors + 7) / 8) * view_sub);
     ...
     if (vis[i >> 3] & (1 << (i & 7)))
     {
         // Subsector is visible
         ...
     }
     else
     {
         // Subsector is not visible
         ...
     }

However, being that I am not really sure what the bitshifting operators in here are accomplishing, or how the variable vis seems to be accessed as if it were an array are unfortunately kinda confusing to me.

Does anyone mind pointing me in the right direction? Or have any questions that I've not already answered above?

More information on the format can be found here!

Spoiler: Original Post

It appears as though the smallest amount of data I can read from a buffer is a single byte, or 8 bits.

However, for my current project I need to be able to read 1 bit of data. I'm not entirely sure how to go about doing that if the smallest GM allows is a byte.

Do I have to use buffer_bool, then use bit shifting to get the individual values of each bit? I'm not entirely sure how to go about doing that. Any pointers?

 

[GMWolf]

You could read a byte of memory, and then use bitwise logic to extract bits.

// get Nth bit in byte 
var bit = byte & (1 << N);

//make it into a bool:
var b = (bit != 0);

I included the bit into bool conversion part because the first part will keep the bit in the same position (So 5 & (1<<2) will be 4, not 1)

 

[nacho_chicken]

It appears as though the smallest amount of data I can read from a buffer is a single byte, or 8 bits.

However, for my current project I need to be able to read 1 bit of data. I'm not entirely sure how to go about doing that if the smallest GM allows is a byte.

Do I have to use buffer_bool, then use bit shifting to get the individual values of each bit? I'm not entirely sure how to go about doing that. Any pointers?

Yes, you would use simple bitshifting and masking. Here are my functions for bit handling:

function bit_get(_val, _bit) {
  return ((_val & (1 << _bit)) != 0);
}

function bit_set(_val, _bit) {
  return (_val | (1 << _bit));
}

function bit_clear(_val, _bit) {
  return (_val & ~(1 << _bit));
}

function bit_toggle(_val, _bit) {
  return (_val ^ (1 << _bit));
}

Those are all simple functions that use almost all the major operators. If you don't understand any particular part of them, I highly recommend this explanation of bitwise operators. https://code.tutsplus.com/articles/understanding-bitwise-operators--active-11301 (NOTE: GM lacks a few of the operators shown. Specifically the unsigned shifts and shift assignments.)
Pay close attention to the truth tables. Once you understand those, you're set!

 

[IGameArt]

Thanks, these are very helpful!

 

[IGameArt]

Bump* Changed original post to reflect new but related issue, in an attempt to not flood the programming forum with new questions every 3 minutes.

 

[Juju]

Yes, you would use simple bitshifting and masking. Here are my functions for bit handling:

function bit_get(_val, _bit) {
  return ((_val & (1 << _bit)) != 0);
}

function bit_set(_val, _bit) {
  return (_val | (1 << _bit));
}

function bit_clear(_val, _bit) {
  return (_val & ~(1 << _bit));
}

function bit_toggle(_val, _bit) {
  return (_val ^ (1 << _bit));
}

Defo plop these into a library and share it around/put on GMLscripts.com. Great way to teach people basic bitwhacking.

 

[nacho_chicken]

Hey guys, I need some help translating some code I found online for a new feature being implemented into DopeFish, my Doom wad loader for GM.

I'm trying to utilize the gl_pvs format created originally for the Vavoom source port, however low level code like this is something I'm fairly inexperienced with.

In the buffer loaded from the wad file is a chunk of data called a lump. There are several lumps that represent several different types of data, like sprites, textures, maps, or helper nodes. GL_PVS is one of those helper nodes.



So the GL_PVS lump is essentially a buffer copied to memory from within the wad file. It contains a sort of lookup table of all of the visibility states of any part of the map from any other part of the map. Having access to this table would make it so the renderer could skip over rendering any parts of the map that aren't visible from the camera's current location.

The format for finding where to look in the buffer for the results of your current subsector (chunk of the level) are all follows:
((numsubsectors + 7) / 8) * i

The example for how to find the visibility of a subsector i is as follows:

     byte *vis_data;    // PVS lump
     int view_sub;      // Num of subsector, where the player is
     byte *vis;
     vis = vis_data + (((numsubsectors + 7) / 8) * view_sub);
     ...
     if (vis[i >> 3] & (1 << (i & 7)))
     {
         // Subsector is visible
         ...
     }
     else
     {
         // Subsector is not visible
         ...
     }

However, being that I am not really sure what the bitshifting operators in here are accomplishing, or how the variable vis seems to be accessed as if it were an array are unfortunately kinda confusing to me.

Does anyone mind pointing me in the right direction? Or have any questions that I've not already answered above?

More information on the format can be found here!

vis and vis_data are both pointers. They're used in C++ to access the contents of data addresses directly. The data located at the address vis is pointing to is an array. You can access pointers like an array, because arrays in C++ are effectively pointers. If all this sounds a bit complicated, that's because it is. Googling "C++ pointers" should give plenty of reading material to get enough of a basic understanding. In any case, the array appears to contain one byte per element, all consisting of bitmasked boolean flags for checking visibility.

I don't know exactly what your code is doing since it's very obviously a snippet. vis = vis_data + (((numsubsectors + 7) / 8) * view_sub); looks like it's finding the location of the sector the player is at in memory. No idea what numsubsectors, view_sub, or vis_data are set to, so I can't really tell exactly what it's doing. As for the next part if (vis[i >> 3] & (1 << (i & 7))), a trick to understanding bit shifts is that in practice, they're equivalent to doing multiplication or division by powers of 2. i >> n can be read as "floor(i / 2 ⁿ )". It's likely done because it was much faster than doing a division operation. It looks like it's done in a for loop (hence the i). i >> 3 tells me this bit of code runs quite a number of times, since it's increasing the index of the array every 8 loops. (1 << (i & 7)) loops through every bit of the byte located at vis[i>>3]. The AND operator is used to check if the subsector is visible. You'll notice it's identical to how my bit_get() function worked. That's pretty much all I can tell from that piece of code.

EDIT:

Defo plop these into a library and share it around/put on GMLscripts.com. Great way to teach people basic bitwhacking.

I'll probably add a few more functions, comment it up, throw it on GitHub, and make a tutorial here on the GMC. Looks like there's equivalents to all my functions already on GMLscripts, haha!

 

[Bart]

However, being that I am not really sure what the bitshifting operators in here are accomplishing, or how the variable vis seems to be accessed as if it were an array are unfortunately kinda confusing to me.

Does anyone mind pointing me in the right direction? Or have any questions that I've not already answered above?

It's C/C++ pointer arithmetic at work. The variable vis_data points to the address of an array of bytes. In C, you can get the actual value in that location in memory in two ways:

byte value = *vis_data;    // "De-reference" the pointer
byte value = vis_data[0];  // Use the equivalent array syntax
// Both result in the same value

More important is what happens when pointers are added/subtracted. It's equivalent to moving the index in an array:

byte value = *(vis_data+1);// "De-reference" the pointer
byte value = vis_data[1];  // Use the equivalent array syntax

So if you want to convert that code into gml, all that needs to be done is use that value as the array index, since it's essentially an offset:

// (vis_data is an existing array)
var index = (((numsubsectors + 7) / 8) * view_sub);
vis = vis_data[index];

This piece of code seems to be doing quite a bit of bitwise trickery:

(vis[i >> 3] & (1 << (i & 7)))

Not sure if it's useful to explain, but I'll give it a try
The (1 << (i & 7)) part shifts a one (i.e. only the lowest bit at index 0 set) (i & 7) to the left. A single bit shift to the left multiplies by 2.
The (i & 7) does a logical AND of every two bits. A 7 (111 in binary (1*4+1*2+1*1)) means the lowest 3 bits are equal to 1. So this part lets through the first three bits of i and forces all others to 0 because of the AND &.
vis[i >> 3] looks up the value at index i >> 3, which means a shift to the right of 3 (thereby dropping the information in the three lowest bits).
Those two results are AND'ed once more to end up with some value.
Not sure what logic is represented by the formula but that's more or less the bitwise things going on.

 

[GMWolf]

(vis[i >> 3] & (1 << (i & 7)))

This is getting the i th bit in vis.

vis[i >> 3] is the same as vis[i / 8].
In other words, get the byte that contains the ith bit.

i & 7 is the same as i % 8. In other words, find the bit position of the ith bit.

I read the whole thing as

var byte = vis[i >> 3]; //get byte that contains ith bit

var bitPos = i & 7; // get bit poison in byte of ith bit in array

var bit = byte  & (1<<bitPos) // get ith bit

If (bit) //test ith bit

vis = vis_data + (((numsubsectors + 7) / 8) * view_sub);

This is getting the position of the vis array in the buffer.

(numsectors + 7) /8 this is integer arithmetic to divide by 8 and round up.
In GML that would be ceil(numsectors / 8);

My guess here is that you have a bit of visibility for each sector. So this calculates how many bytes are needed. (Divide by 8, because A byte has 8 bits, but round up because We cannot have partial bytes).

I'm guessing view_sub is the index of the current view.
So each view has numsectors bits to represent visibility. You want the get the visibility for view number view_sub, you have to jump over (ceil(numsector/ 8) * view_sub) bytes.