13

I'm working with some legacy code and I came across a function which is apparently used to perform network byte order conversions on an arbitrarily long field (bigger than ntohl can handle).

I can't understand it well enough to tell if it's doing anything more than reversing the byte order over the msg buffer range though (or even if it will do that reliably). Can someone help me break this down and analyze it so I can replace it with something that's more intelligible (or at least comment it well)!?

void swapit(unsigned char *msg, int length) {
  for(;length>0;length--, msg++) {
    *msg = ((*msg * 0x0802LU & 0x22110LU) |
            (*msg * 0x8020LU & 0x88440LU)) *
           0x10101LU >> 16;
  }
}
John Humphreys
  • 37,047
  • 37
  • 155
  • 255
  • 3
    See http://stackoverflow.com/a/746203/367273 where this function appears along with numerous alternatives. Voting to close on that basis. – NPE Dec 13 '11 at 15:52
  • Erm... should I take that as a "it's perfectly safe and don't worry about it?" – John Humphreys Dec 13 '11 at 15:55
  • 1
    That's up to you. It clearly deserves a comment (and perhaps a link to that other SO question? :-)) – NPE Dec 13 '11 at 15:56
  • 1
    Oh I found it in there now :) Thanks man. I feel a lot better knowing whoever wrote this probably looked it up, haha. – John Humphreys Dec 13 '11 at 15:57
  • 7
    Hehe, make you sure comment it with a link for the next maintainer :) – John Carter Dec 13 '11 at 15:58
  • Definitely. This was making my head split :p – John Humphreys Dec 13 '11 at 15:59
  • Voted to reopen... would be very interested to see this broken down and explained as requested. – Graham Borland Dec 13 '11 at 16:01
  • I'd actually appreciate that. Since it is a very fast way to achieve this in a 32-bit system, I'd like to keep it in the code - but I'd feel better leaving a comment or explaining the magic numbers/ >>16 and all that (which I'm having trouble doing admittedly :( ) – John Humphreys Dec 13 '11 at 16:04
  • 2
    Beware that reversing *bit* order (which this does) isn't the same as reversing *byte* order. Sending data from a big-endian to a little-endian system doesn't require bit reversal. – Steve Jessop Dec 13 '11 at 16:55
  • Someone certainly hated a person who was supposed to read the code after it's been written. – ScarletAmaranth Dec 17 '11 at 22:47

3 Answers3

20

To see how it works, consider applying the operations to the bit pattern abcdefgh. I'll represent binary numbers with . for 0, so the non-zero bits stand out.

The first subexpression is:

  ........ ........ abcdefgh
* ........ ....1... ......1. (0x0802)
= .....abc defgh..a bcdefgh.
& ......1. ..1....1 ...1.... (0x22110)
= ......b. ..f....a ...e....

The second is:

  ........ ........ abcdefgh
* ........ 1....... ..1..... (0x8020)
= .abcdefg h..abcde fgh.....
& ....1... 1....1.. .1...... (0x88440)
= ....d... h....c.. .g......

Combining them and multiplying by the final constant gives:

  ......b. ..f....a ...e....
| ....d... h....c.. .g......
= ....d.b. h.f..c.a .g.e....
* .......1 .......1 .......1 (0x10101)
= ....d.b. h.f..c.a .g.e....
 +h.f..c.a .g.e.... ........
 +.g.e.... ........ ........
= hgfedcba hgfe.c.a .g.e....

Finally shifting down by 16 bits gives hgfedcba, the reverse of the original pattern.

Mike Seymour
  • 249,747
  • 28
  • 448
  • 644
6

From this question: Best Algorithm for Bit Reversal ( from MSB->LSB to LSB->MSB) in C

It appears to be reversing bits.

0010 0000 => 0000 0100
Community
  • 1
  • 1
Pubby
  • 51,882
  • 13
  • 139
  • 180
3

It's mentioned in bit twiddling hacks as Reverse the bits in a byte with 7 operations (no 64-bit).

John Carter
  • 53,924
  • 26
  • 111
  • 144