Last active
May 5, 2021 01:55
-
-
Save nmoinvaz/ac30fc08f19488e4efa38707d5004291 to your computer and use it in GitHub Desktop.
zlib-ng bi-reverse table
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <cstdlib> | |
#include <map> | |
unsigned bi_reverse(unsigned code, int len) { | |
/* code: the value to invert */ | |
/* len: its bit length */ | |
unsigned long res = 0; | |
do { | |
res |= code & 1; | |
code >>= 1, res <<= 1; | |
} while (--len > 0); | |
return (unsigned)(res >> 1); | |
} | |
static const unsigned char bi_reverse_table[256] = { | |
0x00,0x80,0x40,0xc0,0x20,0xa0,0x60,0xe0, | |
0x10,0x90,0x50,0xd0,0x30,0xb0,0x70,0xf0, | |
0x08,0x88,0x48,0xc8,0x28,0xa8,0x68,0xe8, | |
0x18,0x98,0x58,0xd8,0x38,0xb8,0x78,0xf8, | |
0x04,0x84,0x44,0xc4,0x24,0xa4,0x64,0xe4, | |
0x14,0x94,0x54,0xd4,0x34,0xb4,0x74,0xf4, | |
0x0c,0x8c,0x4c,0xcc,0x2c,0xac,0x6c,0xec, | |
0x1c,0x9c,0x5c,0xdc,0x3c,0xbc,0x7c,0xfc, | |
0x02,0x82,0x42,0xc2,0x22,0xa2,0x62,0xe2, | |
0x12,0x92,0x52,0xd2,0x32,0xb2,0x72,0xf2, | |
0x0a,0x8a,0x4a,0xca,0x2a,0xaa,0x6a,0xea, | |
0x1a,0x9a,0x5a,0xda,0x3a,0xba,0x7a,0xfa, | |
0x06,0x86,0x46,0xc6,0x26,0xa6,0x66,0xe6, | |
0x16,0x96,0x56,0xd6,0x36,0xb6,0x76,0xf6, | |
0x0e,0x8e,0x4e,0xce,0x2e,0xae,0x6e,0xee, | |
0x1e,0x9e,0x5e,0xde,0x3e,0xbe,0x7e,0xfe, | |
0x01,0x81,0x41,0xc1,0x21,0xa1,0x61,0xe1, | |
0x11,0x91,0x51,0xd1,0x31,0xb1,0x71,0xf1, | |
0x09,0x89,0x49,0xc9,0x29,0xa9,0x69,0xe9, | |
0x19,0x99,0x59,0xd9,0x39,0xb9,0x79,0xf9, | |
0x05,0x85,0x45,0xc5,0x25,0xa5,0x65,0xe5, | |
0x15,0x95,0x55,0xd5,0x35,0xb5,0x75,0xf5, | |
0x0d,0x8d,0x4d,0xcd,0x2d,0xad,0x6d,0xed, | |
0x1d,0x9d,0x5d,0xdd,0x3d,0xbd,0x7d,0xfd, | |
0x03,0x83,0x43,0xc3,0x23,0xa3,0x63,0xe3, | |
0x13,0x93,0x53,0xd3,0x33,0xb3,0x73,0xf3, | |
0x0b,0x8b,0x4b,0xcb,0x2b,0xab,0x6b,0xeb, | |
0x1b,0x9b,0x5b,0xdb,0x3b,0xbb,0x7b,0xfb, | |
0x07,0x87,0x47,0xc7,0x27,0xa7,0x67,0xe7, | |
0x17,0x97,0x57,0xd7,0x37,0xb7,0x77,0xf7, | |
0x0f,0x8f,0x4f,0xcf,0x2f,0xaf,0x6f,0xef, | |
0x1f,0x9f,0x5f,0xdf,0x3f,0xbf,0x7f,0xff | |
}; | |
static unsigned bi_reverse2(unsigned code, int len) { | |
return ((unsigned)bi_reverse_table[code & 0xff] << 24 | | |
(unsigned)bi_reverse_table[(code >> 8) & 0xff] << 16 | | |
(unsigned)bi_reverse_table[(code >> 16) & 0xff] << 8 | | |
bi_reverse_table[(code >> 24) & 0xff]) >> (32 - len); | |
} | |
int main() | |
{ | |
unsigned int code = 0x66881045; | |
printf("original %08x reverse (%02x%02x%02x%02x)\n", code, | |
code & 0xff, code >> 8 & 0xff, code >> 16 & 0xff, code >> 24 & 0xff); | |
printf("%08x\n", (unsigned)bi_reverse_table[code & 0xff] << 24); | |
printf("%08x\n", (unsigned)bi_reverse_table[(code >> 8) & 0xff] << 16); | |
printf("%08x\n", (unsigned)bi_reverse_table[code & 0xff] << 24 | |
| (unsigned)bi_reverse_table[(code >> 8) & 0xff] << 16); | |
printf("%08x\n", (unsigned)bi_reverse_table[(code >> 16) & 0xff] << 8); | |
printf("%08x\n", (unsigned)bi_reverse_table[(code >> 24) & 0xff]); | |
printf("bi_reverse %08x\n", bi_reverse(code,12)); | |
printf("bi_reverse2 %08x\n", bi_reverse2(code,12)); | |
printf("static const char bi_reverse_table = {\n "); | |
for (int i = 0; i < 256; i++) { | |
printf("0x%02x", bi_reverse(i, 8)); | |
if (i < 255) { | |
printf(","); | |
} | |
if ((i+1) % 16 == 0) { | |
printf("\n "); | |
} | |
} | |
printf("};"); | |
return 0; | |
} | |
std::map<int, int> ConstructRandomMap(int size) { | |
std::map<int, int> m; | |
for (int i = 0; i < size; ++i) { | |
m.insert(std::make_pair(std::rand() % size, std::rand() % size)); | |
} | |
return m; | |
} | |
class MapFixture : public ::benchmark::Fixture { | |
public: | |
void SetUp(const ::benchmark::State& st) { | |
m = ConstructRandomMap(10 * 1024); | |
} | |
void TearDown(const ::benchmark::State&) { m.clear(); } | |
std::map<int, int> m; | |
}; | |
BENCHMARK_DEFINE_F(MapFixture, bireverse1)(benchmark::State& state) { | |
for (auto _ : state) { | |
for (std::pair<int, int> e : m) { | |
unsigned reversed = bi_reverse((unsigned)e.first, e.second); | |
benchmark::DoNotOptimize(reversed); | |
} | |
} | |
} | |
BENCHMARK_REGISTER_F(MapFixture, bireverse1); | |
BENCHMARK_DEFINE_F(MapFixture, bireverse2)(benchmark::State& state) { | |
for (auto _ : state) { | |
for (std::pair<int, int> e : m) { | |
unsigned reversed = bi_reverse2((unsigned)e.first, e.second); | |
benchmark::DoNotOptimize(reversed); | |
} | |
} | |
} | |
BENCHMARK_REGISTER_F(MapFixture, bireverse2); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment