Binary Bit Field Rotation and Display functions

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

  1. Lord KJWilliams

    Lord KJWilliams Member

    Joined:
    Jul 2, 2018
    Posts:
    107
    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++)
           {
             mask += (unsigned long)(pow(2,x));
           }
           //copy the part that will be shoved off to the right
           lost_part = (mask & a);
           //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--)
           {
              mask += (unsigned long)(pow(2,x));
           }
           //copy the part that will be shoved off to the left
           lost_part = (mask & a);
           //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(" mask:");print_bytes(mask,-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 :

    0xEFDEADBE
    0xADBEEFDE

    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. vdweller

    vdweller Member

    Joined:
    Jun 24, 2016
    Posts:
    135
    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. Catan

    Catan Member

    Joined:
    Jun 20, 2016
    Posts:
    738
    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
  4. FrostyCat

    FrostyCat Member

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

    Catan Member

    Joined:
    Jun 20, 2016
    Posts:
    738
    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 KJWilliams

    Lord KJWilliams Member

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

    chamaeleon Member

    Joined:
    Jun 21, 2016
    Posts:
    975
    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)
    
    
     
    RujiK and Lord KJWilliams like this.
  8. Lord KJWilliams

    Lord KJWilliams Member

    Joined:
    Jul 2, 2018
    Posts:
    107
     
  9. Juju

    Juju Member

    Joined:
    Jun 20, 2016
    Posts:
    412
    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[0], alarm[1] 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.

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice