Go Down

Topic: Byte mirroring (Read 3924 times) previous topic - next topic

gvi70000

Mar 04, 2011, 05:23 pm Last Edit: Mar 04, 2011, 05:26 pm by gvi70000 Reason: 1
Is there a function that can mirror a byte?

If i have 11111100 i want to obtain 00111111
i will try ~

gvi70000

what i have so far is

Code: [Select]

uint8_t S65Display::ReverseByteBits(uint8_t value)
        {
            uint8_t ret = 0;
            for (int i = 0; i < 8; i++)
                if ((value & (uint8_t)(1 << i)) != 0) ret += (uint8_t)(1 << (7 - i));
            return ret;
        }

is there a quicker way?

gardner

#2
Mar 04, 2011, 05:56 pm Last Edit: Mar 04, 2011, 06:20 pm by gardner Reason: 1
Shifts by more than one bit are slow on Arduino.  You should be able to do it with a total of 16.
If you are in a real hurry, use a lookup table in PROGMEM.

Code: [Select]
reverse(uint8_t in)
{
 uint8_t out;
 char i;

 out = 0;

 for (i = 0; i < 8; i++) {
     out <<= 1;
     if (in & 1)
       out |= 1;
     in >>= 1;
 }

 return out;
}



less compact, but faster

Code: [Select]
reverse(uint8_t in)
{
  uint8_t out;
  out = 0;
  if (in & 0x01) out |= 0x80;
  if (in & 0x02) out |= 0x40;
  if (in & 0x04) out |= 0x20;
  if (in & 0x08) out |= 0x10;
  if (in & 0x10) out |= 0x08;
  if (in & 0x20) out |= 0x04;
  if (in & 0x40) out |= 0x02;
  if (in & 0x80) out |= 0x01;

  return(out);
}

PaulS

There is no reason to perform the if test. The statement will write either a 0 or a 1 to the specified bit. It will be faster if you simply write the 0 than to test that the value would be 0 in order to avoid writing the 0.

robtillaart

#4
Mar 04, 2011, 07:21 pm Last Edit: Mar 04, 2011, 07:29 pm by robtillaart Reason: 1
this is a job for - http://www.amazon.com/Hackers-Delight-Henry-S-Warren/dp/0201914654/ref=sr_1_1?ie=UTF8&s=books&qid=1299262192&sr=1-1

I have the book on my wishlist but there is allways this site for bithacks: - http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious

(tested positive on Arduino)
Code: [Select]


b = ((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16;

or

b = (b * 0x0202020202ULL & 0x010884422010ULL) % 1023;  // 64 bit



there are more " bit beauties" there.
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

retrolefty

I recall several decades ago needing to 'flip' a byte in turbo pascal, so I wrote a function. It was ugly but it did work. I would think a nice class library function that would 'flip' any variable passed to it, byte, int, long, would be a neat function to have in one's toolbag? Any of you software gurus up to the challenge?

Lefty


Groove

I've worked on architectures (DSPs mostly) that do it in hardware because it is so useful for FFTs
Per Arduino ad Astra

retrolefty


I've worked on architectures (DSPs mostly) that do it in hardware because it is so useful for FFTs


Is that the so called barrel shifter function or hardware ?

Groove

No, that's a one cycle shifter - these were often simply switchable bus lines
Per Arduino ad Astra

retrolefty


No, that's a one cycle shifter - these were often simply switchable bus lines


Wow, that would be pretty fast, but I guess that's the reason/justification for such specialized hardware features frequently used in Dsp applications

robtillaart

@groove :
Hardware: 74HC595  (all lines crossed)   74HC165     shiftOut byte shiftIn reverse  is that possible (no IC at hand)

@lefty
According to - http://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel

this should be it:  (not tested)

Code: [Select]


unsigned int s = sizeof(v) * CHAR_BIT;   // bit size; must be power of 2
unsigned int mask = ~0;        
while ((s >>= 1) > 0)
{
 mask ^= (mask << s);
 v = ((v >> s) & mask) | ((v << s) & ~mask);
}

Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

cr0sh


this is a job for - http://www.amazon.com/Hackers-Delight-Henry-S-Warren/dp/0201914654/ref=sr_1_1?ie=UTF8&s=books&qid=1299262192&sr=1-1

I have the book on my wishlist but there is allways this site for bithacks: - http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious

(tested positive on Arduino)
Code: [Select]


b = ((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16;

or

b = (b * 0x0202020202ULL & 0x010884422010ULL) % 1023;  // 64 bit



there are more " bit beauties" there.



Thanks for posting that - I was pretty certain there had to be a way to do it algorithmically without needing a loop construct, and that it had to be something already invented (if not in the AVR libc!); something that always gets me is the vast amount of time we spend constantly re-inventing the wheel, thinking that somehow we'll be able to do it better (or that our technique is first), seemingly forgetting that computing has a fairly long history behind it.

Not to mention the fact that if your CPU uses "fewer bits" than your PC, likely someone in the past 40-odd years (or greater if you want to include the pre-personal computing era) has already run into the issue, and a solution already exists; the only trouble is finding it, which is why knowing that link you posted (which I've run across in the past), as well as that book (which I haven't, but is going on my "to purchase" list - though I have too many books as it is!) - are both items (among many) that people in this field should be aware of...

:)
I will not respond to Arduino help PM's from random forum users; if you have such a question, start a new topic thread.

robtillaart

Quote
likely someone in the past 40-odd years (or greater if you want to include the pre-personal computing era) has already run into the issue, and a solution already exists;

many interesting algorithms were invented/designed in the 60ies - most memorable Quicksort in 1960(!)
Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

retrolefty

#13
Mar 04, 2011, 08:00 pm Last Edit: Mar 04, 2011, 08:04 pm by retrolefty Reason: 1

@groove :
Hardware: 74HC595  (all lines crossed)   74HC165     shiftOut byte shiftIn reverse  is that possible (no IC at hand)

@lefty
According to - http://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel

this should be it:  (not tested)

Code: [Select]


unsigned int s = sizeof(v) * CHAR_BIT;   // bit size; must be power of 2
unsigned int mask = ~0;        
while ((s >>= 1) > 0)
{
 mask ^= (mask << s);
 v = ((v >> s) & mask) | ((v << s) & ~mask);
}




I tried it but got a compiler error " CHAR_BIT not declared in scope" ?
Is that just how many bits in a character for the machine it's running on, 8 for AVR?


gvi70000

Thank you all for the replays, i did learn something from them
The link provided by robtillaart i added to favorites  $)
This post is about using an array to draw chars on LCD's. i'm using LS020, LH88 and L2F50
the arrays looks like this, each line represents a character 8x8 bits
Code: [Select]
const prog_uint8_t font[] =
{
  0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00, // 0x20
  0x30,0x78,0x78,0x30,0x30,0x00,0x30,0x00, // 0x21
  0x6C,0x6C,0x6C,0x00,0x00,0x00,0x00,0x00, // 0x22
  0x6C,0x6C,0xFE,0x6C,0xFE,0x6C,0x6C,0x00, // 0x23
  0x30,0x7C,0xC0,0x78,0x0C,0xF8,0x30,0x00, // 0x24
  0x00,0xC6,0xCC,0x18,0x30,0x66,0xC6,0x00, // 0x25
  0x38,0x6C,0x38,0x76,0xDC,0xCC,0x76,0x00, // 0x26
  0x60,0x60,0xC0,0x00,0x00,0x00,0x00,0x00, // 0x27
  0x18,0x30,0x60,0x60,0x60,0x30,0x18,0x00, // 0x28
  0x60,0x30,0x18,0x18,0x18,0x30,0x60,0x00, // 0x29
  0x00,0x66,0x3C,0xFF,0x3C,0x66,0x00,0x00, // 0x2A
  0x00,0x30,0x30,0xFC,0x30,0x30,0x00,0x00, // 0x2B
.........................

The L2F50 has a different way of reading bits
"T" char for example is rotated with 90deg and mirrored, the last part i resolve it with your help
now i have to rotate so that "|-" (this is an approximation) will become "T"
Any idea how to start?

Go Up