What does this actually do? - Crazy C++ function

Question

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;
  }
}

Answer 1

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.

Answer 2

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

Answer 3

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