0

I am uncompressing some data from double words. 

unsigned char * current_word = [address of most significant byte]

My first 14 MSB are an int value. I plan to extract them using a bitwise AND with 0xFFFC.

int value = (int)( (uint_16)current_word & 0xFFFC );

My next 6 bits are a fractional value. Here I am stuck on an efficient implementation. I could extract one bit at a time, and build the fraction 1/2*bit + 1/4+bit + 1/8*bit etc ... but that's not efficient.

float fractional = ?

The last 12 LSB are another int value, which I feel I can pull out using bitwise AND again.

int other_value = (int) ( (uint_16)current_word[2] & 0x0FFF );

This operation will be done on 16348 double words and needs to be finished within 0.05 ms to run at least 20Hz.

I am very new to bit operations, but I'm excited to learn. Reading material and/or examples would be greatly appreciated!

Edit: I wrote OR when I meant AND

Constantin
  • 16,812
  • 9
  • 34
  • 52
  • You're converting pointers to integers, don't do that. Instead convert `char*` to `unsigned*` and dereference it. Also, depending on the processor you're using, it looks like you have reversed byte order. In that case you'll need to grab each byte (or part thereof) individually, and shift them into the right places. – Ben Voigt Jan 30 '12 at 22:04
  • I am confused, how do your approach of static casts differ from mine? – Constantin Jan 30 '12 at 22:08
  • Your second line of code evaluates `(uint_16)current_word`. `current_word` is an address (see first line of code), you're grabbing 14 bits from the address, not from the data. You need `*(uint_16*)current_word`. Except that leaves the byte order wrong. – Ben Voigt Jan 30 '12 at 22:09
  • =D Wooops, thank you. Why is the byte order wrong? Every 4 bytes is a new word. Byte[0] contains the 8 MSB of the double word and Byte[3] containts the 8 LSB of the double word? Or am I confused again? – Constantin Jan 30 '12 at 22:12
  • That's most certainly Big-Endian. Most processors are Little-Endian, where the 8 MSB are in byte 3 and the 8 LSB are in byte 0. – Ben Voigt Jan 30 '12 at 22:21
  • TIL I've been imagining memory wrong. Thanks Ben! – Constantin Jan 30 '12 at 22:28

4 Answers4

2

Firstly you'd be more efficient getting the double-word all at once into an int and masking/shifting from there.

Getting the fractional part from that is easy: mask and shift to get an integer, then divide by a float to scale the result.

float fractional = ((current_int >> 12) & 0x3f) / 64.;
Mark Ransom
  • 299,747
  • 42
  • 398
  • 622
  • You're completely right! Let me edit my examples. Is my form of using an unsigned char * to point to the first Most Significant BYTE of each double word, then static casting to my intended representation bad form? I feel in this case I will know the data being passed. Is there a better approach? – Constantin Jan 30 '12 at 22:10
  • @Constantin, Ben Voigt had it right in the comments - use `uint_32 *` unless there's an endian mismatch, otherwise go char by char. I can't see any advantage to `uint_16`. – Mark Ransom Jan 30 '12 at 22:20
2

Since you're starting with [address of most significant byte] and using increasing addresses from there, your data is apparently in Big-Endian byte order. Casting pointers will therefore fail on nearly all desktop machines, which use Little-Endian byte order.

The following code will work, regardless of native byte order:

int value = (current_word[0] << 6) | (current_word[1] >> 2);
double fractional = (current_word[1] & 0x03) / 4.0 + (current_word[2] & 0xF0) / 1024.0;
int other_value = (current_word[2] & 0x0F) << 8 | current_word[3];
Ben Voigt
  • 277,958
  • 43
  • 419
  • 720
  • Wow Ben this is great. I am confused on the byte order though, but I can google that. – Constantin Jan 30 '12 at 22:19
  • I like the way you adjusted the constants to avoid a shift. – Mark Ransom Jan 30 '12 at 22:23
  • @Mark: Yeah, but I'd been picking the wrong 2 bits out of byte 1 for the fractional part. – Ben Voigt Jan 30 '12 at 22:32
  • Hey Ben, current_word[0] is 8 bits, if I shift 6 of them to the left won't I lose 6 of those bits? Or has the compiler already converted it a 32 bit representation? Also, for the fractional part if I shift current_word[1] 6 bits to the right, I am losing the 2 LSB bits from word(1) that represent the fractional part? – Constantin Jan 30 '12 at 22:34
  • 1
    @Constantin: The left operand of a shift operator is promoted. `unsigned char` becomes (signed) `int` before the shift. From the standard, section 5.8 `[expr.shift]`: "The operands shall be of integral or unscoped enumeration type and integral promotions are performed. The type of the result is that of the promoted left operand." – Ben Voigt Jan 30 '12 at 22:35
  • One last thing, I just tried to google it, but a quick google didn't show it, ... where can I find the c++ standard? – Constantin Jan 30 '12 at 22:38
  • 1
    @Constantin: http://stackoverflow.com/questions/81656/where-do-i-find-the-current-c-or-c-standard-documents – Ben Voigt Jan 30 '12 at 22:39
  • And about that right shift by 6, it was wrong, I fixed it before your comment. – Ben Voigt Jan 30 '12 at 22:40
0

there are 5 kinds of shift instructions:

  1. Shift right with sign extend: It will copy your current leftmost bit as the new bit to the leftmost after shifting all the bits to the right. Rightmost one gets dropped.
  2. Shift right with zero extend: Same as (1) but assume that your new leftmost bit is always zero.
  3. Shift left: replace right in (1) and (2) with left , left with right and read (2) again.
  4. Roll right: Shift your bits to the right, instead of rightmost one dropping, it becomes your leftmost.
  5. Roll left: Replace right in (4) with left , left with right and read (4) again.

You can shift as many times you want. In C, more than the amount of bits in your datatype is undefined. Unsigned and signed types shift differently although the syntax is same.

artificialidiot
  • 5,309
  • 29
  • 27
0

If you are reading your data as unsigned char *, you are not going to be able to get more than 8-bits at a time of data and your example needs to change. If your address is aligned, or your platform allows, you should read your data in as an int *, but then that also begs the question of just how your data is stored. Is it stored 20-bits per integer with 12-bits of other info, or is it a 20-bit stream where you need to keep track of your bit pointer. If the second, it's even more complex than you realize. I'll post further once I have a feel for how your data is laid out in RAM.

Michael Dorgan
  • 12,453
  • 3
  • 31
  • 61