# Binary Bit Field Rotation and Display functions

Discussion in 'Advanced Programming Discussion' started by Lord KJWilliams, Jun 29, 2019.

Tags:
1. ### Lord KJWilliamsMember

Joined:
Jul 2, 2018
Posts:
138
Before I got interested in GML or GMS, I programmed in C ( in Linux and MS-DOS ) and created functions that I had a need for a program that I was building for a game that I was working on. The two functions, that I want to share with community, are used for binary field rotation and the other for displaying the bit field ( which you can use separately ), its merely for diagnostics to see what the result of a rotated bit-field.

The bit rotation function does what bit shifting does not do, it wraps the binary field to the other side when you shift it left or right. Normally when you use >> or << , anything that gets shifted off the bit field is lost forever. So I decided to wrap it to the other side. So the limit of how many bits a bit field can be rotated is dependent on the integer size. In C you have, char , short int, int, long ( double and float are not used due to IEEE's method of remembering the mantissa - its not the way you think it is for integers in base 2 ) , just to keep things simple.

The program that I want to port to GML from C uses this source code :

Code:
```#ifndef BITROT_H
#define BITROT_H

#include <stdio.h>
#include <math.h>
#include "p_bytes.h"

unsigned long rotate_bits(unsigned long, signed char, char);

//-------------------------------------------------------------------
/*
headers, functions, and global variables used:

stdio.h
math.h

print_bytes();

**

make note of this abreviation key:

orig = original value that will be rotated.
mask = marks the range of bits that will be pushed off.
copy = copy of the bit values, that will be pushed off.
_posA = copy value, shifted in the opposite direction.
_posB = is the result of shifting the original bit pattern.
_newv = _posA value + _posB value, creates the new rotated position.

rotate_bits() rotates the bits of a value, that is not zero, to
a desired position. The function will not promote or demote
values, to a greater or lesser variable of other number
ranges in the operation. This function uses print_bytes().

values:

1 - 255 ..........  will be treated as a unsigned char
256 - 65535 ........  will be treated as a unsigned short int
65535 - 4294967295 ...  will be treated as a unsigned long

rotate_bits uses three arguments,

The first arugument, a unsigned long, is the target value that will
be rotated around. The target value must be in the values from 2^0
to 2^31.

The second argument is the position setting, which rotates the
binary pattern around to. The position setting range depends on the
target variable.

note: rotate_bits will not accept a position setting of 0.

If the target value:
...  is a unsigned char, then the range is from -8 to 8.
...  is a unsigned short int, then the range is from -16 to 16.
...  is a unsigned long, then the range is from -32 to 32.

The third argument is a diagnostic display flag, which if is
1 then the operation of rotate_bits() will be displayed. Other
values turn off the diagnostic display.

rotate_bits returns a unsigned long that is the result of
the targets new rotated_bit setting.
*/
unsigned long rotate_bits(unsigned long a, signed char b, char y)
{
signed char m, j = 0, x, z, k = 0;//temp variables
unsigned long mask = 0, lost_part = 0, new_posA, new_posB, _newvar;

//test rotation position value before using it.
if(b > 31 || b < -31)
{
printf("ERROR: Rotation position value can only be (-31 to 31)\n");
printf("to rotate the target value left or right. Process aborted.\n");
return 0;
}

//check to see if the rotation value is 0
if(b == 0)
{
printf("ERROR: rotate_bits() requires a value for rotating the target value\n");
printf("       thats greater or less than 0. Process aborted.\n");
return 0;
}

//check variable a for 0 value
if(a == 0)
{
printf("ERROR: rotate_bits() requires a target value greater than 0.\n");
printf("       The target value must be from ( 1 - 4294967295 ).\n");
printf("       Process aborted.\n");
return 0;
}

// test the value to see how many bytes(of bits) it has
if(a > 65536) { m = 31; } // 4 bytes
if(a > 255 && a < 65536) { m = 15; k = 1; } // 2 bytes
if(a <= 255) { m = 7; k = 2; } // 1 byte

if(b < 0) j = b * -1;// create a positive value from the negative
// shifting value. -3 becomes 3

// test rotation value to see if it is greater than m
if(j > m || b > m)
{
printf("ERROR: The requested rotation position is greater than the\n");
printf("       number of bits of the value, process aborted.\n");
return 0;
}

// RIGHT SHIFTING
// if rotation value is (1 to 31) the rotation starts on 0th bit
if(b > 0)
{
if(y == 1) printf("RIGHT(%02d) >>\n",b);

j = b;
for(x = 0; x < (j); x++)
{
}
//copy the part that will be shoved off to the right
//reshift lost part
new_posA = lost_part << ((m+1)-j);
//shift over a
new_posB = a >> j;
}

// LEFT SHIFTING
// if rotation value is (-1 to -31) the rotation starts on the 31st bit
if(b < 0)
{
if(y == 1) printf("LEFT(%02d) <<\n",j);

z = m - j;// this is where z is used, so that j does not change
for(x = m; x > (z); x--)
{
}
//copy the part that will be shoved off to the left
//reshift lost_part
new_posA = lost_part >> ((m+1)-j);
//shift over a
new_posB = a << j;
}

//(unsigned long) new_posA + new_posB
_newvar = new_posA + new_posB;

//trim unsigned long into a unsigned int
if(k == 1)
{
new_posA = (unsigned short int)new_posA;
new_posB = (unsigned short int)new_posB;
_newvar = (unsigned short int)_newvar;
}

//trim unsigned long into a unsigned char
if(k == 2)
{
new_posA = (unsigned char)new_posA;
new_posB = (unsigned char)new_posB;
_newvar = (unsigned char)_newvar;
}

//diagnosis messages
if(y == 1)
{
printf(" orig:");print_bytes(a,-1);
printf(" copy:");print_bytes(lost_part,-1);
printf("_posA:");print_bytes(new_posA,-1);
printf("_posB:");print_bytes(new_posB,-1);
printf("_newv:");print_bytes(_newvar,-1);
}

return _newvar;
}
//-------------------------------------------------------------------

#endif
```

This is the function that displays the binary bit field

Code:
```/*
p_bytes.h (Print Bytes) by K.J. Williams
*/

#ifndef P_BYTES_H
#define P_BYTES_H

#include <stdio.h>
#include <math.h>

void print_bytes(unsigned long, signed char);

/*
headers, functions, or global variables used:

stdio.h
math.h

**

print_bytes() displays values in their binary representation,
but also in decimal and hexadecimal values. Any value from
0 - 4294967295 can be displayed in binary.

print_bytes has two arguments,

The first argument is a unsigned long, the value that will be
printed in a binary, hexadecimal, and/or integer representation.

The second argument is a signed char which determines how the
first argument's format will be displayed as well as it's bit length.

if the signed char is:
..-1* or 1 then the value will show the value in integer & hexadecimal
along with the binary format.

..-2* or 2 then the value will show the value in hexadecimal along
with the binary format.

..-3* or 3 then the value will show the value in integer display along with
with the binary format.

If the signed char is 0 or any other values greater than 3 or less
than -3 then only the binary format is printed.

* Note: negative values override the automatic formatted binary print,
in which four bytes of binary bits will be displayed no matter
what the value is.

print_bytes returns no value.

*/
void print_bytes(unsigned long a, signed char d)
{
// temp variables
unsigned char z = 1;// needed for printing a " ".
signed char x, m, tu = 0;
unsigned long y = 0, j = 4294967295;// highest int value

// if d is less than -3 or greater than 3 then set d to 0.
if(d < -3 || d > 3) d = 0;

if (d < 0) tu = d * -1;// test to see if d is a negative number

/* if the numbers are beyond the highest int value
set them to them to the highest long int value allowed */
if (a > j) a = j;

// hexadecimal or integer equivalence display
if (tu >= 1 && tu <= 3 || d >= 1 && d <= 3)
{
// hex & int.
if (tu == 1 || d == 1) printf(" [%08lX]:[%010lu] = ",a,a);

// hex display
if (tu == 2 || d == 2) printf(" [%08lX] = ",a);

// integer display
if (tu == 3 || d == 3) printf(" [%010lu] = ",a);
}
// determine range of bits to print

// if d is a positive number, tu will stay 0.
if (tu == 0)
{
if (a > 65536) m = 31;// 4 bytes
if (a > 255 && a < 65536) m = 15;// 2 bytes
if (a <= 255) m = 7;// 1 byte
}

// if d is a negative number, tu will equal the absolute
// value of d which is a positive number.

if (tu >= 1 && tu <= 3) m = 31;// default to 4 bytes

/* cycle from 2^x to 2^0 to show each bit */
for (x = m;x > -1; x--,z++)
{
y = (unsigned long)(pow(2,x));// where math.h is needed
// print a 1,0, or a space at every 8th count.
if ((a & y) == y) { printf("1"); }
if ((a & y) != y) { printf("0"); }
if (z == 8) { printf(" "); z = 0; }
}
printf("\n");
}

#endif
```
So the problem with importing this code to GML, is that my programs depend on integer sizes in bytes, which define the number of bits. In C if I want to know how many bytes a variable uses I use an expression where bytesn = ( sizeof ) myvar; , however GML does not have this. I have not found in the manual for GML, a means where you can check to see how many bytes your var is, because that's what I need to know. If I am not using a variable for text strings, or for decimal ( using IEEE mantissa ) - and I am just using the var for remembering a value ( e.g. 0xDEADBEEF ).

( Please note, I use hexadecimal for representing large integer numbers. )

So how does bit_rotation work?

Lets say you have a variable with the value : 0x0F and you want to rotate it 4 bits to the right, which is the same as rotating it 4 bits to the left..

( this is one byte )

00001111

you get :

11110000

and how has the value : 0xF0

You can take a value : 0xDEADBEEF ( 32-bits ) and you can rotate it to the left or the right by 16 bits and get the the same result , 0xBEEFDEAD .

If you shift a value by 1/2 the bits counted in the number of bytes, either left or right you get the same result.

It is possible to get :

Your not truncating or changing the size of the bytes used, your just shifting the bit-fields around while saving the byte size. I know the byte sizes because in C , there are defined integer sizes. I did not use ( sizeof ) or for that matter limits.h , because I didn't think would not need them if I knew already the possible sizes.

A few things that I did not implement in my function was to test the value being rotated has a maximum value that looks like 0xFF, 0xFFFF, or 0xFFFFFFFF , because rotating 11111111 ( or 00000000 ) alone will not produce any different result, not like 0x0F or 0xDEADBEEF ( shown above )

So the problem in GML is that I do not know how to determine how many bytes uses, and I do not want to promote my values to a new byte range accidentally ( e.g. a 1 byte rotated to the left now is represented as 2 bytes, which is wrong ).

The other reason that I posted it here is that I thought that it might be useful to someone who needs it. It does have a use, but thats for you to decide in the application that you need it for. You can also use the function that displays prints the variable in binary, print_bytes(), but it has the same problem as bit_rotation() .

So can this work in GML and what do I need to change or add ( I know its represented in user defined header for C, which you cant do in GML ) ?

Thanks

2. ### vdwellerMember

Joined:
Jun 24, 2016
Posts:
140
About the size of a variable:I believe that shifting any variable any way casts it into a 64 bit type. Also int64() may do the same.

Lord KJWilliams likes this.
3. ### HomunculusMember

Joined:
Jun 20, 2016
Posts:
855
Other than what @vdweller noted, all numeric variables are represented in game maker as double precision floating point values.

Also, there is no built in function comparable to sizeof that allows you determine how many bytes it would take to fit a value. Neither there are functions to rotate bits.

Knowing the above though, you can create yourself a couple of scripts that implement a sizeof and binary rotation like behavior, affecting only a chunk of the 64bit value.

Gml scripts ( https://www.gmlscripts.com/script/Computation/Bitwise/ ) has a couple of such scripts, not sure if they are still relevant or any good though.

Last edited: Jun 30, 2019
Lord KJWilliams and Bentley like this.
4. ### FrostyCatMember

Joined:
Jun 26, 2016
Posts:
4,806
There has been an alternative to that for a long time. Ever heard of the int64 type?

Bentley and Homunculus like this.
5. ### HomunculusMember

Joined:
Jun 20, 2016
Posts:
855
Of course, vdweller mentioned that right before my reply, l just phrased it wrong. I meant that excluding what vdweller said (and int32(), to be precise) that's how gm handles numeric values. I edited the reply, it was definitely confusing.

6. ### Lord KJWilliamsMember

Joined:
Jul 2, 2018
Posts:
138
Does GML have something like a limits.h where it defines the limits of how much information its variable types can use?

7. ### chamaeleonMember

Joined:
Jun 21, 2016
Posts:
1,079
No. int64 type is 8 bytes (not unsurprising), where operations treat it as a signed number, including right-shifting keeping the sign bit which can be an annoyance if you really just want to deal with bits. Unless I'm mistaken the floating point numbers are also 8 bytes with the usual limitations that apply to that per IEEE standards for doubles (but don't quote me).

bitstring script
Code:
```var n = argument0;
var bits = "";
for (var bit = 63; bit >= 0; bit--) {
bits += ((n & (1 << bit)) != 0) ? "1" : "0";
}
return bits;
```
Not shifting into negative
Code:
```var n = 1;
for (var i = 60; i < 63; i++) {
n = 1 << i;

show_debug_message(string_format(i, 2, 0) + ": " + bitstring(n) + " (" + string(n) + ")");
}
for (var i = 0; i < 4; i++)
{
n = n >> 1;
show_debug_message(string_format(i, 2, 0) + ": " + bitstring(n) + " (" + string(n) + ")");
}
```
Code:
```60: 0001000000000000000000000000000000000000000000000000000000000000 (1152921504606846976)
61: 0010000000000000000000000000000000000000000000000000000000000000 (2305843009213693952)
62: 0100000000000000000000000000000000000000000000000000000000000000 (4611686018427387904)
0: 0010000000000000000000000000000000000000000000000000000000000000 (2305843009213693952)
1: 0001000000000000000000000000000000000000000000000000000000000000 (1152921504606846976)
2: 0000100000000000000000000000000000000000000000000000000000000000 (576460752303423488)
3: 0000010000000000000000000000000000000000000000000000000000000000 (288230376151711744)
```
Shifting into negative
Code:
```var n = 1;
for (var i = 60; i < 64; i++) {
n = 1 << i;

show_debug_message(string_format(i, 2, 0) + ": " + bitstring(n) + " (" + string(n) + ")");
}
for (var i = 0; i < 4; i++)
{
n = n >> 1;
show_debug_message(string_format(i, 2, 0) + ": " + bitstring(n) + " (" + string(n) + ")");
}
```
Code:
```60: 0001000000000000000000000000000000000000000000000000000000000000 (1152921504606846976)
61: 0010000000000000000000000000000000000000000000000000000000000000 (2305843009213693952)
62: 0100000000000000000000000000000000000000000000000000000000000000 (4611686018427387904)
63: 1000000000000000000000000000000000000000000000000000000000000000 (-9223372036854775808)
0: 1100000000000000000000000000000000000000000000000000000000000000 (-4611686018427387904)
1: 1110000000000000000000000000000000000000000000000000000000000000 (-2305843009213693952)
2: 1111000000000000000000000000000000000000000000000000000000000000 (-1152921504606846976)
3: 1111100000000000000000000000000000000000000000000000000000000000 (-576460752303423488)

```

Bentley, RujiK and Lord KJWilliams like this.

Joined:
Jul 2, 2018
Posts:
138

9. ### JujuMember

Joined:
Jun 20, 2016
Posts:
415
Unfortunately, and this is going to drive you mad I can tell, "it depends". The variables that you define yourself are set up so that floats are doubles and ints are 64-bit. Strings I'm not sure about, but I've mucked around with some enormous JSON / base64-encoded stuff so I'm going to say "big enough".

Hooooweveeeeer, GameMaker's internal variables are stored at a different precision. The classic example are x and y - they're 32-bit floats. The alarm variables (alarm, alarm etc.) are integers, and I'd expect them to be 32-bit integers too though I've not explicitly checked that. 95% of the time we're dealing with 64-bit floats and ints but every now and again GameMaker is weird and does a weird thing. Why haven't they swapped over to something more sane? Time contraints probably, even though this does regularly catch people out.

Lord KJWilliams likes this.
10. ### TheouAegisMember

Joined:
Jul 3, 2016
Posts:
7,373
Edit: Whoops. A bit of a necro. I'll stop reading this forum tonight. lol

Finding significant bytes (as opposed to bits) can be done without strings.
Code:
```///get_hi_bit(val)
//returns highest significant bit on a byte-by-byte level
var n = argument0, i=8;
while n {
n = n >> 8;
i += 8;
}
return power(2,i) >> 1;```
If you want to keep it restricted to byte, word, double word, and quadruple word, then it could be slightly faster.
Code:
```///get_hi_bit(val)
//returns highest significant bit restricted to word size
var temp;
temp = \$FF00;
temp = \$FFFF0000;
temp = \$FFFFFFFF00000000;
temp = \$FFFFFFFFFFFFFFFF0000000000000000; //I forget if this is possible lol
temp = \$8000;
temp = \$80000000;
temp = \$8000000000000000;
temp = \$80000000000000000000000000000000; //ditto lol
for(var i=3; i>-1; i--;)
if argument0 & temp[i] return temp[i+4] else return \$80;```
If temp and temp are too many bits anyway, then remove them and you free up 3 steps of code! lol

When I handled rotations, i just picked a significant bit based on what kind of code I was writing anyway, which was usually limited to just 8 or 16 bits. I mean, if argument0 was '4', then the significant bit would always be \$80 even if the user wanted it to be \$80000000, so that's one drawback I see to this idea.

Last edited: Dec 12, 2019
Lord KJWilliams likes this.