Thread: Endianness and bit shifting

  1. #1
    Registered User
    Join Date
    Jun 2009
    Posts
    101

    Endianness and bit shifting

    Hello, I'm new to C and am having trouble with bit shifting. I am working on an app that takes 10 bit RGB pixel values (packed into 32 bit words) and shifts them by two bits. I can get this to work (values are properly shifted) if I use the following code:

    temp = swap_e(temp);
    temp = (temp<<2);
    temp = swap_e(temp);

    swap_e() is a function that simply swaps the endian order. Example:

    b3420a23 //before swap_e()
    230a42b3 //after swap_e()

    However, I've read in more than one place that endianness shouldn't affect bit shifting. Why would this work if I swap the endian order before performing the bit shift? I aplogize if this is a really rudimentary question, but I'm still learning! Thanks in advance!

  2. #2
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    It should.

    Where did you read that from?

  3. #3
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    Actually, nevermind. What was I smoking .

    It shouldn't matter because shifting shifts the whole word (logically, the representation doesn't matter).

    It would matter if you try to emulate the word shift by shifting each byte separately, or something.

  4. #4
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    That's kind of the whole points. Bit shifting *isn't* affected by endianness. Meaning that:
    Code:
    a << 2
    Will always be equal to a*4 (ignoring overflows and negative numbers, but you'll catch my drift). No matter what endianness the computer is in.

    That is what the people meant when they said it isn't affected by endianness.

    Obviously, this does mean that if a is stored in another endianness than your processor's endianness, you will have to convert it first.

  5. #5
    Registered User
    Join Date
    Jun 2009
    Posts
    101
    Quote Originally Posted by EVOEx View Post
    Obviously, this does mean that if a is stored in another endianness than your processor's endianness, you will have to convert it first.
    That's what I'm assuming -- however, what is confusing is that I have to swap the endian order, perform the bit shift, then swap it BACK. It seems to me like there should be a way to perform the shift without converting it first. If not, ok -- but I am worried about the swapping back-and-forth causing performance issues. Clearly, the data needs to be arranged in its original endian order, otherwise I wouldn't have to swap it back.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Here are the bits as they are originally:
    abcdefgh ijklmnop qrstuvwx yz123456
    Here is the result you want (assuming you have a little endian machine):
    cdefgh00 abklmnop ijstuvwx qryz1234
    Do you see an easy way to get from the first one to the second one?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Flipping before shifting will cause a different set of bits to get shifted off the end, and the zero bits which are shifted in get shifted to a different position, than if you had not flipped the endianness.

    Endianness affects the LOADING or STORING of a multibyte value from/to a byte stream. Once the value is loaded into a variable of the correct type, the endianness no longer matters.

    The difference in result is not due to endianness, per se, but merely the swapping around of bytes within a multi-byte quantity.

    If you describe how you are attempting to process these 10-bit RGB values, maybe I can help with the actual problem...

    EDIT: Since these quantities are not an integral number of bytes, the term "endianness" isn't really the right term to use here. But byte order DOES matter. The smallest multiple of 8 which is also a multiple of 10 is 40, which means that you have 4 pixels for every 5 bytes of image data -- the ordering of the bits of these pixels within that 5 byte sequence has not been specified, so there are a large number of possibilities.

    Reminds me of the confusion when processing the 12-bit cluster numbers in FAT12.

    In other words, your problem is not a failure to understand, but an under-specified problem
    Last edited by brewbuck; 06-05-2009 at 02:56 PM.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  8. #8
    Registered User
    Join Date
    Jun 2009
    Posts
    101
    The goal is to take 10 bit RGB values (padded to 32 bit with zeros) and shift them over two bits. The reason is because one file format packs RGB with padding at one end, and the other format packs them at the other end. Here:

    32 bit word:
    BBBBBBBBBBGGGGGGGGGGRRRRRRRRRR00

    Let's take one pixel. Here's how it's stored: bfb4b209
    If I shift this as so:
    value<<2;
    I get this: fed2c824

    However, this is garbled when I open it in the reader.

    But, if I swap the ordering first and start with this: 09b2b4bf:
    swap_endian(value)<<2;
    I get this: 26cad2fc

    Then I have to swap it back to this in order for the reader to display it properly:
    fcd2ca26

    Only after swapping the order are the values packed in such a way that the bit shift works properly.

    I'm sorry if the explanation isn't the best! :-)
    Last edited by synthetix; 06-05-2009 at 03:52 PM.

  9. #9
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    So the real issue is simply that the format of the data is in a different endian than your machine. Obviously, before *any* transformations can be performed on the data in the normal way, it will have to be translated to the endian format of your machine. It may be a good idea then to convert the entire image to your native format, and then just convert it back when you're done working with it.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  10. #10
    Registered User
    Join Date
    Jun 2009
    Posts
    101
    Quote Originally Posted by Sebastiani View Post
    So the real issue is simply that the format of the data is in a different endian than your machine.
    It's an Intel Mac, 2x quad core Xeon (E5462). I'm pretty sure it's little-endian. Is there a way to perform the bit shift without swapping the order? I can't figure out a way to do it. Again, this conversion will probably come with a performance penalty.

    The resulting format must be big-endian, I can tell you that.

    By the way, my code is reading the file 32 bits at a time and then doing this conversion (i.e. per each pixel).
    Last edited by synthetix; 06-05-2009 at 04:13 PM.

  11. #11
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    >> Is there a way to perform the bit shift without swapping the order?

    Not really. Any way I can think of wouldn't be nearly as efficient.
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

  12. #12
    int x = *((int *) NULL); Cactus_Hugger's Avatar
    Join Date
    Jul 2003
    Location
    Banks of the River Styx
    Posts
    902
    Quote Originally Posted by synthetix
    Again, this conversion will probably come with a performance penalty.
    Not really. You're likely serializing to or deserializing from some medium such as a disk or network connection that is probably going to be a lot slower than your processor. Profile first, of course.

    Writing a very simple byte swap routine, I can perform swaps at 165MB/s. (On one 2GHz processor.) Neither my disk or my network could ever hope to keep up with that. (Especially the rather crappy wireless signal that this post is about to be posted over...)
    long time; /* know C? */
    Unprecedented performance: Nothing ever ran this slow before.
    Any sufficiently advanced bug is indistinguishable from a feature.
    Real Programmers confuse Halloween and Christmas, because dec 25 == oct 31.
    The best way to accelerate an IBM is at 9.8 m/s/s.
    recursion (re - cur' - zhun) n. 1. (see recursion)

  13. #13
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by synthetix View Post
    The goal is to take 10 bit RGB values (padded to 32 bit with zeros) and shift them over two bits. The reason is because one file format packs RGB with padding at one end, and the other format packs them at the other end. Here:
    Ah -- you mean 10 bits per COMPONENT, not 10 bits per PIXEL. Then the situation is not as dire. The other commenters are correct -- the simplest way to do this is byte-swap, shift, then byte-swap.

    I started working out how you might do this without byte-swapping up front, and it's obviously possible, but too messy and probably inefficient to show here...

    (Basically, you want to turn this: BBBBBB00 GGGGBBBB RRGGGGGG RRRRRRRR
    Into this: BBBBBBBB GGGGGGBB RRRRGGGG 00RRRRRR
    I leave it to you to see how that's going to really suck :-)
    Last edited by brewbuck; 06-05-2009 at 04:31 PM.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  14. #14
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,834
    I would think something like this might do it:
    Code:
    Q << 2 & 0xfcfcfcfc | Q >> 14 & 0x30303
    But I haven't had time to test it. Maybe later tonight.

  15. #15
    Registered User
    Join Date
    Jun 2009
    Posts
    101
    Quote Originally Posted by Cactus_Hugger View Post
    Writing a very simple byte swap routine, I can perform swaps at 165MB/s. (On one 2GHz processor.) Neither my disk or my network could ever hope to keep up with that.
    I don't know if this matters, but I am working with data from a SAN with probably up to around 500MB/sec throughput (4gbit fibre channel) and processing many thousands of files. Simple code tweaks may save hours of processing time, which is why I'm trying to do this as efficiently as possible.

    If the endian swap is the way to go, then that works for me. I guess if it's in the "wrong" format, then I have no choice.

    Thanks for all your help!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Float =>memory Representation
    By ganesh bala in forum Tech Board
    Replies: 3
    Last Post: 02-06-2009, 04:06 AM
  2. Formatting 64 bit integers
    By Dino in forum C++ Programming
    Replies: 6
    Last Post: 02-05-2008, 08:24 PM
  3. endianness and bit shifting
    By Dino in forum Tech Board
    Replies: 7
    Last Post: 01-30-2008, 11:53 PM
  4. endianness
    By DavidP in forum Tech Board
    Replies: 4
    Last Post: 06-13-2004, 04:44 PM