Solved

Reversing bytes

Posted on 2004-09-21
14
343 Views
Last Modified: 2011-10-03
Hi ALL,

I would like to know how a byte coming into a port of a device
can be quickly reversed and sent on another port quickly using
a lookup mechanism (array).

Assumption:  Memory is abundant

Thanks,
Arut
0
Comment
Question by:arut
  • 5
  • 3
  • 2
  • +2
14 Comments
 
LVL 45

Expert Comment

by:Kdo
ID: 12111283

Hi Arut,

I'm not sure what you're asking here.  Is the port management giving you trouble or the byte reversal?  (And what do you mean by byte reversal?  Send the bytes in reverse order of the way that the arrive or reverse the bits within the byte?)


Kent
0
 

Author Comment

by:arut
ID: 12111436
Hi Kent,

Sorry about that. I meant bits to be reversed LSB becomes MSB bit. This is a question someone asked me and I had no idea.

Thanks,
Arut
0
 
LVL 45

Expert Comment

by:Kdo
ID: 12111517

There are quite a few ways to reverse bits in a byte.  The most "obvious" way is just brite force:

int ReverseBits (int Source)
{
  int idx;
  int Result;

  Result = 0;
  for (idx = 0; idx < 8; idx++)
    if (Source & (1 << idx))
      Result |= (1 << (7 - idx));
  return (Result);
}

You can also reverse the bits with some clever math, but it's a lot tougher to understand.

Good Luck,
Kent
0
NAS Cloud Backup Strategies

This article explains backup scenarios when using network storage. We review the so-called “3-2-1 strategy” and summarize the methods you can use to send NAS data to the cloud

 
LVL 2

Accepted Solution

by:
sneeuw_chan earned 63 total points
ID: 12111605
You mean something like having an array like so:

char reverse_lut[256];

With the values filled in so that reverse_lut[N] is N with its bits in reverse order ?

Anyway, an easy way to reverse the bits in a byte, without a LUT, is in three steps, as follows:

First step:  swap bits 0123 with bits 4567  { byte = ((byte & 0x0F) << 4) | ((byte & 0xF0) >> 4); }
Second step: swap bits 01 with 23 and 45 with 67 simultaneously   { byte = ((byte & 0x33) << 2) | ((byte & 0xCC) >> 2)); }
Last step: swap bits 0 and 1, 2 and 3, 4 and 4, 6 and 7 simult.   { byte = ((byte & 0x55) << 1) | ((byte & 0xAA) >> 1)); }
NB: You can do those steps in any order you like, you can do them on 4 bytes simultaneously without speed loss (just change the ANDing values), and if you want to do some MMX assembly, should be doable on 8 bytes simultaneously as well.
0
 
LVL 2

Expert Comment

by:sneeuw_chan
ID: 12111637
Additional note: The MMX bit is assuming you're on intel, you can probably do it similarly on other architectures with as many bytes as you can fit into a machine register.

In any case, the code I proposed should be faster than a LUT, assuming you're able to work on multiple bytes.  A LUT is probably faster than doing it on single bytes or two bytes at a time, and could be comparable to four at a time, dunno.  You'd have to test that.
0
 
LVL 45

Assisted Solution

by:Kdo
Kdo earned 62 total points
ID: 12111818

Hi sneeuw_chan,

The performance of an LUT can be tricky to predict.  It does, after all, require memory fetches and the speed of the fetch is contingent on where in memory/cache the table lies.  The first one might be pretty expensive, but subsequent fetches should be very fast as the table will have been moved to the closest cache.

Looping is effective for a single byte, but only because these processors are so fast when not referencing memory.  I certainly wouldn't build a length swap algorithm on it though.

The algorithm that you suggested is what I refered to earlier.  It's a little tough for newcomers to understand, but lightening fast.  The instruction count (and ultimately execution speed) increases incrementally while the data length increases exponentially.  (3 steps to swap 8 bits, 4 steps for 16, 5 steps fo 32.)  Past the register size (32 or 64 bits) the algorithm timing synchronizes with the size increase of the data.

Swapping bits on large data block is kinda fun, too.  :)

Kent
0
 
LVL 2

Expert Comment

by:sneeuw_chan
ID: 12112924
Yeah, I know, caching is a pain, performance wise.  But I don't want to assume the OP is working on a PC-type processor, who knows, maybe he's on an embedded system with an ARM or whatever.  Easiest is to write it both ways and to compare performance in typical usage, and add a big fudge factor.

If you really want optimal performance, you should probably also take care of parralelizing instructions, modern CPUs don't like it if the data from one instruction is needed by the very next instruction.  Doing two machine-words at once should take care of that adequately, although you may run out of registers then, dunno.  Long time since I spent hand-tuning MMX instructions.  Was fun though.. ^_^

But I digress, the OP probably got his answer already, and if not, he'll come up with more pointed questions, one would assume.
0
 
LVL 45

Expert Comment

by:Kdo
ID: 12112980

A lot of these threads get more interesting once the original question is answered.  :)

0
 

Expert Comment

by:aakash_mandhar
ID: 12121185
If i have understood the question right , he just wants to reverse a byte.. and byte according to its definition is just 8bits and shud be platform independent...

so have an array like

int a[256]={
0,    //reverse of 0 is still 0
128, //since reverse of 1 is 128 in bytes
64,//reverse of 2 is 64
..
...
.
.
255//Reverse of 255 is 255 only
};
and so on

and when u receive a byte x from port y and have to write it to port z ur algo is only

read x,y  //read x from port y
x=lut[x]; // reversing
write x,z //write x to port z

It saves u a lot of time.. Moreover if u are lazy to find out all the values and hard code them into the c file..
Write a function which calculates them and stores them into the table when the program first starts...

Eg..

calc_lut(); //reverses and stores the values in lut

while(read x,y)
{
x=lut[x];
write x,z;
}


Regards
Aakash

PS> Hope this answers your Q
0
 
LVL 8

Expert Comment

by:ssnkumar
ID: 12121206
Hi Arut,

   Can you explain by giving a small example, so that we can suggest better solutions!?

-ssnkumar
0
 
LVL 45

Expert Comment

by:Kdo
ID: 12121935

Hi aakash,

I agree with you -- his question suggests that he wants to reverse the bits in a byte.  But the Post Script (memory is abundant) suggests that he's got more in mind than just reversing the bits in a byte.


Kent
0
 
LVL 8

Expert Comment

by:ssnkumar
ID: 12122019
Does he wants to swap 1st and 8th bit, or 1st and 4th bit?

-ssnkumar
0

Featured Post

ScreenConnect 6.0 Free Trial

At ScreenConnect, partner feedback doesn't fall on deaf ears. We collected partner suggestions off of their virtual wish list and transformed them into one game-changing release: ScreenConnect 6.0. Explore all of the extras and enhancements for yourself!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
How do I test for current date? 9 103
memory mapped I/O query 6 147
Why this code doesn't work? 8 101
rhel6 C system() call to zip to archive has problems 25 242
An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
Examines three attack vectors, specifically, the different types of malware used in malicious attacks, web application attacks, and finally, network based attacks.  Concludes by examining the means of securing and protecting critical systems and inf…
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.

810 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question