gistfile1.cpp

#include <cstdint>

#define S1(X)  ((X >> 5))
#define S2(X)  ((X >> 3) & 2)
#define S3(X)  ((X >> 1) & 4)
#define S4(X)  ((X << 1) & 8)
#define S5(X)  ((X << 3) & 16)
#define RBIT(X)  (S1(X) | S2(X) | S3(X) | S4(X) | S5(X))

#define T4(i)    T1(((i))),   T1(((i)+1)),     T1(((i)+2)),     T1(((i)+3))
#define T16(i)   T4(((i))),   T4(((i)+4)),     T4(((i)+8)),     T4(((i)+12))
#define T64(i)   T16(((i))),  T16(((i)+16)),   T16(((i)+32)),   T16(((i)+48))

static uint8_t const ReversedBitsTable_64B[64] = {
#define T1(X) RBIT(X)
    T64(0)
#undef T1
};


#define R2(n)     n,     n + 2*64,     n + 1*64,     n + 3*64
#define R4(n) R2(n), R2(n + 2*16), R2(n + 1*16), R2(n + 3*16)
#define R6(n) R4(n), R4(n + 2*4 ), R4(n + 1*4 ), R4(n + 3*4 )

static uint8_t const ReversedBitsTable_256B[256] = {
    R6(0), R6(2), R6(1), R6(3)
};


static inline
unsigned long long rdtsc()
{
    unsigned int hi;
    unsigned long long lo;
    __asm__ __volatile__ (
        "rdtsc"
        : "=a"(lo), "=d"(hi)
        : // no input
        : // no clobber
      );
    return (lo | (((unsigned long long) (hi)) << 32));
}


inline uint8_t ReverseBitsLookup_64 (uint8_t v) {
    uint8_t result = ReversedBitsTable_64B[v & 3];
    result <<= 2;
    result |= ReversedBitsTable_64B[v >> 2];
    return result;
}


inline uint8_t ReverseBitsLookup_256 (uint8_t v) {
    return ReversedBitsTable_256B[v];
}


#include <iostream>
#include <memory>
#include <cstdio>


int main() {
    auto const sz = 250 * 1000 * 1000;
    std::unique_ptr<uint8_t[]> data (new uint8_t[sz]);
    FILE* urnd = fopen ("/dev/urandom", "r");
    fread (data.get(), 1,  sz, urnd);
    fclose (urnd);

    auto start = rdtsc();
    for (auto i = 0; i < sz; ++i) {
        data[i] = ReverseBitsLookup_64(data[i]);           // change me
    }
    auto end = rdtsc();
    std::cout << double(end - start)/sz <<  std::endl;
}