dmmlib/src/bitmap/other.c

/*
 *   Copyright 2012 Institute of Communication and Computer Systems (ICCS) 
 *
 *   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.
 *
 */

/**
 * @file   bitmap/other.c
 * @author Ilias Pliotas, Ioannis Koutras
 * @date   September 2012
 * @brief  Helping functions for bitmap-organized raw blocks
 */

#include "bitmap/bitmap_other.h"

/** Copy the elements of one bitmap array to another.
 *
 * @param dest The destination bitmap array.
 * @param src  The source bitmap array.
 * @param elements The number of elements
 */
void copy_array(BMAP_EL_TYPE *dest, BMAP_EL_TYPE *src, size_t elements) {
    for(size_t i = 0; i < elements; ++i) {
        dest[i] = src[i];
    }
}

/** Shift right by n bits all the elements of a BMAP_EL_TYPE array
 *
 * @param array The array to be shifted right
 * @param n The number of bits to be shifted
 * @param elements The number of elements
 */
void shift_array(BMAP_EL_TYPE *array, size_t n, size_t elements) {
    int i;
    BMAP_EL_TYPE mask1, mask2, guard_mask;

    // Move element-wise at first
    while(n >= BMAP_EL_SIZE_BITS) {
        for(i = 1; i < (int) elements; i++) {
            array[i - 1] = array[i];
        }
        array[elements - 1] = 0;
        n -= BMAP_EL_SIZE_BITS;
    }

    // Check if there are still bits to be shifted
    if(n > 0) {
        mask1 = (BMAP_EL_TYPE) 0;
        guard_mask = ((BMAP_EL_TYPE) 1 << n) - 1;
        for(i = (int) elements - 1; i >= 0; --i) {
            mask2 = array[i] & guard_mask;
            array[i] >>= n;
            array[i] |= mask1 << (BMAP_EL_SIZE_BITS - n);
            mask1 = mask2;
        }
    }
}

/** Perform bitwsie add on every element of a BMAP_EL_TYPE arrays; store the
 *  result on the first array
 */
void add_arrays(BMAP_EL_TYPE *array1, BMAP_EL_TYPE *array2, size_t elements) {
    for(size_t i = 0; i < elements; i++) {
        array1[i] &= array2[i];
    }
}

/** Compute the previous power of 2 which is <= n */
size_t prev_pow2(size_t n) {
    unsigned int last_for_n_bits, i;

    /* size_t is the data type of the argument
     *
     * We multiply it by 8 to get the bits and then divide it by 2 to get the
     * previous size, ergo multiply by 4.
     */
    last_for_n_bits = sizeof(size_t) * 4;
    i = 1;

    while(i <= last_for_n_bits) {
        n |= n >> i;
        i <<= 1;
    }

    return ((n >> 1) + 1);
}

/** Makes a bit mask of 1's
 * @param start_pos The starting position of 1's
 * @param length    The amount of 1's
 */
BMAP_EL_TYPE make_bit_mask(size_t start_pos, size_t length) { 
    BMAP_EL_TYPE init;
    
    init = (BMAP_EL_TYPE) 1;	

    // length should be <= BMAP_EL_SIZE_BITS in any case
    if (length < BMAP_EL_SIZE_BITS) {	
        init <<= length ;
        init--;
        init <<= start_pos - 1;
        return init;
    } else {
        return ~((BMAP_EL_TYPE) 0);
    }

}