Arranging bits in specific order

Dev Shed Forums Sponsor:

September 21st, 2004, 08:10 AM

kubicon

pogremar

Join Date: Jul 2003

Location: At Work

Posts: 958

Time spent in forums: 3 Days 18 h 21 m 50 sec
Reputation Power: 11

Arranging bits in specific order

I have two bytes that I would like to make into a word, but I want the bits to be in a specific order.

R = red
G = green
B = blue

the first byte, which I'll call blueGreen, looks like this:

BBBB BGGG

The bold in the green bits are to differenciate them from the green next to the red. The second byte, greenRed, looks like this:

GGGR RRRR

I would like the word to be in this format:

RRRR RGGG GGGB BBBB

I don't know how to shift the bits in a way that they end up this way.

Thanks

__________________
Some day I'll create a smart quote to put here.

September 21st, 2004, 09:08 AM

clifford

Contributing User

Join Date: Aug 2003

Location: UK

Posts: 4,824

Time spent in forums: 1 Month 2 Days 21 h 1 m
Reputation Power: 1800

One solution:

PHP Code:


		
			
 short buildRGB16( unsigned char blueGreen, unsigned char greenRed )

{

    const unsigned char BLUEGREEN_BLUE_MASK  = 0xf8 ;

    const unsigned char BLUEGREEN_GREEN_MASK = 0x07 ;

    const unsigned char GREENRED_GREEN_MASK  = 0xe0 ;

    const unsigned char BLUEGREEN_RED_MASK   = 0x1f ;

    

    const int BLUEGREEN_BLUE_DOWN_SHIFT  = 3 ;

    const int BLUEGREEN_GREEN_DOWN_SHIFT = 0 ;

    const int GREENRED_GREEN_DOWN_SHIFT  = 5 ;

    const int BLUEGREEN_RED_DOWN_SHIFT   = 0 ;



    const int BLUEGREEN_BLUE_UP_SHIFT  = 0 ;

    const int BLUEGREEN_GREEN_UP_SHIFT = 5 ;

    const int GREENRED_GREEN_UP_SHIFT  = 8 ;

    const int BLUEGREEN_RED_UP_SHIFT   = 11 ;



    short rgb = (((blueGreen & BLUEGREEN_BLUE_MASK) >> BLUEGREEN_BLUE_DOWN_SHIFT) << BLUEGREEN_BLUE_UP_SHIFT) |

                (((blueGreen & BLUEGREEN_GREEN_MASK) >> BLUEGREEN_GREEN_DOWN_SHIFT) << BLUEGREEN_GREEN_UP_SHIFT) |

                (((greenRed & GREENRED_GREEN_MASK) >> GREENRED_GREEN_DOWN_SHIFT) << GREENRED_GREEN_UP_SHIFT) |

                (((greenRed & BLUEGREEN_RED_MASK) >> BLUEGREEN_RED_DOWN_SHIFT) << BLUEGREEN_RED_UP_SHIFT) ;

                

    return( rgb ) ;

}

This down-shifts each sub-field in the source bytes so the least significant but is right-most, then up-shifts each field to its destination position before or'ing it to the destination.

This is sub-optimal. You could workout the resultant over all shift and left or right shift accordingly. But this is probably clearer.

The use if unsigned types is critical since the behavour of >> on signed types that are negative is undefined.

You will probably want to change the return type from short to a platform independent size specific type, or define your own such as:

Code:

typedef short RGB16_t ;

Clifford

September 21st, 2004, 09:56 AM

kubicon

pogremar

Join Date: Jul 2003

Location: At Work

Posts: 958

Time spent in forums: 3 Days 18 h 21 m 50 sec
Reputation Power: 11

Wow! that looks very computation heavy.

I'll need to run that function a couple of thousand times per sencond. My other option is to work out the problem a different way. Which one is more computational heavy, the top or this one:

Code:

UCHAR blue  = (bitmap.getContents()[index_y*SCREEN_WIDTH*3 + index_x*3 + 0]) >> 3,
              green = (bitmap.getContents()[index_y*SCREEN_WIDTH*3 + index_x*3 + 1]) >> 3,
              red   = (bitmap.getContents()[index_y*SCREEN_WIDTH*3 + index_x*3 + 2]) >> 3;

Edit:
Also, what does shifting by 0 accomplishes?

Last edited by kubicon : September 21st, 2004 at 09:58 AM.

September 21st, 2004, 10:00 AM

mitakeet

I'm Baaaaaaack!

Dev Shed God 1st Plane (5500 - 5999 posts)

Join Date: Jul 2003

Location: Maryland

Posts: 5,538

Time spent in forums: 2 Weeks 4 Days 2 h 38 m 46 sec
Reputation Power: 242

Bitshifting is not very expensive, it all happens in the registers. Besides, there is no other way to make this happen. Either you encapsulate the the code so your main body is easier to read (risking a couple of thousand of function call overhead per second) or you place the relatively easy to read and follow code that clifford posted. If you are looking at getting performance (if you are updating in 'real time', or about 33 frames per second, the perforamance may not matter on modern CPUs) you may have to play lots of games that make the code more complex and difficult to maintain. See if it is a performance bottle neck before you spend any time worrying about tweaking the code.

__________________

My blog, The Fount of Useless Information http://sol-biotech.com/wordpress/
Free code: http://sol-biotech.com/code/.
Secure Programming: http://sol-biotech.com/code/SecProgFAQ.html.
Performance Programming: http://sol-biotech.com/code/PerformanceProgramming.html.
LinkedIn Profile: http://www.linkedin.com/in/keithoxenrider

It is not that old programmers are any smarter or code better, it is just that they have made the same stupid mistake so many times that it is second nature to fix it.
--Me, I just made it up

The reasonable man adapts himself to the world; the unreasonable one persists in trying to adapt the world to himself. Therefore, all progress depends on the unreasonable man.
--George Bernard Shaw

September 21st, 2004, 11:35 AM

kubicon

pogremar

Join Date: Jul 2003

Location: At Work

Posts: 958

Time spent in forums: 3 Days 18 h 21 m 50 sec
Reputation Power: 11

Not very expensive, that's pretty cool. I thought this was going to make the program crawl to a halt.

I'm really trying to understand bitwise manipulation. I broke apart Cliff's code, and tried making sense of how the code works, but it just doesn't make sense in my head. I'm sure the code works very good, it's just that I'm not learned in the art bit manipulation, so I'm not sure of how the function is accomplishing the task.

Code:


The 4 statements are OR’ed


1) (((blueGreen & BLUEGREEN_BLUE_MASK) >> BLUEGREEN_BLUE_DOWN_SHIFT) << BLUEGREEN_BLUE_UP_SHIFT) 
BBBB BGGG  &  1111 1000	   >>  3			    << 0



2) (((blueGreen & BLUEGREEN_GREEN_MASK) >> BLUEGREEN_GREEN_DOWN_SHIFT) << BLUEGREEN_GREEN_UP_SHIFT)
BBBB BGGG  &  0000 0111	    >> 0				<< 5


3) (((greenRed & GREENRED_GREEN_MASK) >> GREENRED_GREEN_DOWN_SHIFT) << GREENRED_GREEN_UP_SHIFT)
GGGR RRRR &  1110 0000	  >>  5			   <<  8


4) (((greenRed & BLUEGREEN_RED_MASK) >> BLUEGREEN_RED_DOWN_SHIFT) << BLUEGREEN_RED_UP_SHIFT)
GGGR RRRR &  0001 1111	 >> 0				  << 11

For instance, This is how I'm breaking this apart:

First, in section 1, blueGreen is AND'ed with BLUEGREEN_BLUE_MASK (BBBB BGGG & 1111 1000). Let's say that the blue bit's are all ones. It would end up being this "1111 1000". Then shift right by 3, 0001 1111. Since we're shifting, I don't see the point of the ANDing. Then we shift back 0. In my head, that does nothing.

In the second section, blueGreen is ANDed with BLUEGREEN_GREEN_MASK (BBBB BGGG & 0000 0111) and then shifted right by 0, then left by 5 -- yielding GGG0 000. Again, my head tells me that AND'ng and the shifting right by 0 pointless.

In the third section, Green red is AND'ed, right shifted by 5 then left shifted by 8, yielding: 0000 0000

Now, I'm sure that I'm wrong, but you can see how I'm comming to this wrong conclussion.

September 21st, 2004, 12:44 PM

mitakeet

I'm Baaaaaaack!

Join Date: Jul 2003

Location: Maryland

Posts: 5,538

Time spent in forums: 2 Weeks 4 Days 2 h 38 m 46 sec
Reputation Power: 242

Perhaps this is more clear?

Code:

#include <limits.h>
#include <stdio.h>

void dumpBits(char *bits, int length){
    int idx = 0, i, test;

    while (idx < length){
        test=1;
        for (i=0; i<8; i++){
            if (bits[idx] & test)
                printf("1");
            else
                printf("0");
            test <<= 1;
        }
        idx++;
    }
    printf("\n");
}

inline unsigned short addRGB(unsigned char red, unsigned char green, unsigned char blue){
    unsigned short retVal = 0;
    
    retVal |= red;
    retVal <<= 5;

    retVal |= green;
    retVal <<= 6;

    retVal |= blue;

    return retVal;
}

int main(){
    unsigned short rgb;
    char *testPtr = (char *)&rgb;

    rgb = addRGB(0x1E, 0x1E, 0x1E);
    testPtr = (char *)&rgb;
    dumpBits(testPtr, 2);

    return 0;
}

September 21st, 2004, 05:17 PM

clifford

Contributing User

Join Date: Aug 2003

Location: UK

Posts: 4,824

Time spent in forums: 1 Month 2 Days 21 h 1 m
Reputation Power: 1800

Shifting by zero is pointless (or at least has no affect). I wrote it that way to make it generic and configurable. If the fields were to be packed differently, or the spec was incorrect, or mis-intepreted by me, it can be changed simply by changing the constants. Most compilers will simply remove the zero shift even without any optimization settings.

Shifting the unsigned char parameters by 8 does not result in a value that is always zero in this case, because there is an implicit type conversion to short since that is teh type of the assignment.

Shifting is inexpensive (nanoseconds on a modern processor). However, it probably worth optimizing it. Simply subtract the up-shift from the down-shift; if the value is less than zero, use a left shift of that magnitude, if it is positive use a right shift and if zero, do no shift:

PHP Code:


		
			
 short buildRGB16( unsigned char blueGreen, unsigned char greenRed )

{

    const unsigned char BLUEGREEN_BLUE_MASK  = 0xf8 ;

    const unsigned char BLUEGREEN_GREEN_MASK = 0x07 ;

    const unsigned char GREENRED_GREEN_MASK  = 0xe0 ;

    const unsigned char BLUEGREEN_RED_MASK   = 0x1f ;

    

    short rgb = ((blueGreen & BLUEGREEN_BLUE_MASK) >> 3) |

                ((blueGreen & BLUEGREEN_GREEN_MASK) << 5) |

                ((greenRed & GREENRED_GREEN_MASK) << 3) |

                ((greenRed & BLUEGREEN_RED_MASK) << 11) ;



    return( rgb ) ;

}

I have tested this code!

Clifford

September 21st, 2004, 05:34 PM

DaWei_M

Lord of Dorkness

Dev Shed God 8th Plane (8500 - 8999 posts)

Join Date: Jan 2004

Location: Central New York. Texan via Arizona, out of his element!

Posts: 8,515

Time spent in forums: 4 Weeks 18 h 59 m 31 sec
Warnings Level: 20
Number of bans: 3
Reputation Power: 3268

If I were you, I'd pause for a moment and ask why the code you're working from derived the 5.6.5 color information in the way that it did if the bit order needs to be reversed. The typical endianess problems don't require bit reversal, just byte (and somethimes, at least in the olden days, 'word') reordering. If I were sure they needed reversed, and time were an issue, I'd drop into asm and shift (or rotate) from the source into the carry, then shift (or rotate) the other direction from the carry to the destination. It would also be possible to use bitsets and just transfer the information, although I'm not sure that would turn out to be more effective than Clifford's or Mitakeet's examples. Mainly, I'd want to be very sure the operation is necessary.

__________________
Functionality rules and clarity matters; if you can work a little elegance in there, you're stylin'.
If you can't spell "u", "ur", and "ne1", why would I hire you? 300 baud modem? Forget I mentioned it.
DaWei on Pointers Politically Incorrect.

September 21st, 2004, 08:10 PM

kubicon

pogremar

Join Date: Jul 2003

Location: At Work

Posts: 958

Time spent in forums: 3 Days 18 h 21 m 50 sec
Reputation Power: 11

Quote:

If I were you, I'd pause for a moment and ask why the code you're working from derived the 5.6.5 color information in the way that it did if the bit order needs to be reversed.

I don't know for sure. I'm trying to extract information from a bitmap which is stored in an unsigned char array. After reading some code, I'm pretty sure that for a 24 bit bitmap the information is stored Like so: eg BGRBGRBGRBGRBGRBGR Where B, G, R is one byte for blue, one byte for green and one byte for red, repectively. I assumed then that the 16bit information would be stored as as combo of two bytes. I read that most programs don't create 16bit bitmaps. I figured that this weird arrangement was the reason. However, even if this were not the case, I can still learn from this post.

I'm pretty familiar with the order of operations when working with decimals, after all I've used it all my live. I'm starting to get familiar with the order of operation for bits. Advance stuff such as the one cliff showed me still confuses me, but I'm going to keep at it. Today I learned, all on my own, how to see if particular bits where on or off in a variable. Well, actually, I couldn't help glancing over mitakeet's post a couple of times, but I tried my hardest to do as much as possible myself. I still gave myself a cookie for that one!

Thanks alot clifford, mitakeet.

Last edited by kubicon : September 21st, 2004 at 08:12 PM.

Arranging bits in specific order

Developer Shed Advertisers and Affiliates