bitreversal.c

/*Copyright 2014 Keldon Alleyne

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

    http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.*/

/* This file contains a fast method for creating bit reversal lookups
in O(N) time using little more than N adds in the process
(and 2 log N bit shifts).

Another method is provided that takes a 256 entry bit reversal table,
and calculates the bit reversal in 6 bit shifts, and 6 logical operations.
*/

/*** bitreversal.h ***/
void CreateBitReverseTable(int *table,int size);
unsigned int ReverseBitsWithTable(unsigned int n,
        const unsigned int *table);
unsigned int ReverseBits(unsigned int n);
int ReverseBitsAndShift(unsigned int n, int right_shift);

/*** bitreversal.c ***/
void ReverseBitsHelper(int *table, int size,
    int build_size, int next_bit);

unsigned int ReverseBitsWithTable(unsigned int n,
        const unsigned int *table)
{
    unsigned int n0 = n & 0xffU;
    unsigned int n1 = (n >> 8) & 0xffU;
    unsigned int n2 = (n >> 16) & 0xffU;
    unsigned int n3 = (n >> 24);
    unsigned int reversed =
        reverse_table[n0] << 24 |
        reverse_table[n1] << 16 |
        reverse_table[n2] << 8 |
        reverse_table[n3];
    return reversed;

}

unsigned int ReverseBits(unsigned int n) {
    unsigned int reverse_table[256];
    CreateBitReverseTable((int*)reverse_table,256);
}

int ReverseBitsAndShift(unsigned int n, int right_shift) {
    return ReverseBits(n) >> right_shift;
}

void CreateBitReverseTable(int *table,int size) {
    int build_size;
    int next_bit;
    build_size = 1;
    next_bit = size >> 1;

    table[0] = 0;
    while(build_size <= size) {
        ReverseBitsHelper(table, size, build_size, next_bit);
        build_size <<= 1;
        next_bit >>= 1;
    }
}
void ReverseBitsHelper(int *table, int size, int build_size, int next_bit) {
    int write_index;
    int end;
    int read_index;

    int shifted_source;
    int msb;
    int next_value;

    if(build_size >= size) {
        return;
    }
    read_index = 0;
    end = build_size << 1;
    for(write_index = build_size;
        write_index < end;
        ++write_index, ++read_index)
    {
        next_value = table[read_index] + next_bit;
        table[write_index] = next_value;
    }
}


/*** bitreversal_test.c ***/
#include <stdio.h>

int main() {
    const int kNBits = 3;
    const int N = 1 << kNBits;
    int i;
    int table[N];
    CreateBitReverseTable(table,N);
    for(i = 0; i < N; ++i) {
        // printf("%d:%d\n", i, table[i]);
        printf("%d:%d\n", i, ReverseBitsAndShift(i,32-kNBits));
    }
    return 0;
}