ctrump/common/bitmap.c

Go to the documentation of this file.

/* -*- coding:utf-8 -*- 
 Copyright (c) 2009, Fixstars Corporation
 All rights reserved.
 
 Redistribution and use in source and binary forms, with or without modification, 
 are permitted provided that the following conditions are met:
 
   * Redistributions of source code must retain the above copyright notice,
     this list of conditions and the following disclaimer.
 
   * Redistributions in binary form must reproduce the above copyright notice,
     this list of conditions and the following disclaimer in the documentation
     and/or other materials provided with the distribution.
 
   * Neither the name of Fixstars Corporation nor the names of its contributors
     may be used to endorse or promote products derived from this software
     without specific prior written permission.
 
 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
 INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
 AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
 THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

#include "ctrump/common/bitmap.h"
#include "ctrump/common/mempool.h"
#include <string.h>
#include <stdio.h>

static void
clear_unused_bit(ctrump_bitmap_t bmp,
                 unsigned int length)
{
    unsigned int idx = length/BITMAP_NUM_BITS;
    unsigned int mod = length%BITMAP_NUM_BITS;
    ctrump_bitmap_bits_t mask = (((ctrump_bitmap_bits_t)1) << mod)-1;
    bmp[idx] = bmp[idx] & mask;
}

#define GEN_OP2(name,OP)                                \
void                                                    \
name(ctrump_bitmap_t dest,                              \
     ctrump_bitmap_t src0,                              \
     ctrump_bitmap_t src1,                              \
     unsigned int length)                               \
{                                                       \
    unsigned int n = WORDSIZE_OF_BITMAP(length);        \
    unsigned int i;                                     \
    for (i=0; i<n; i++) {                               \
        OP(dest[i],src0[i],src1[i]);                    \
    }                                                   \
}


void
ctrump_bitmap_copy(ctrump_bitmap_t dest,
                   ctrump_bitmap_t src0,
                   unsigned int length)
{
    unsigned int n = WORDSIZE_OF_BITMAP(length);
    unsigned int i;
    for (i=0; i<n; i++) {
        dest[i] = src0[i];
    }
}


#define OR(d,l,r) (d) = (l) | (r)
#define NOR(d,l,r) (d) = (l) | ~(r)
#define NAND(d,l,r) (d) = (l) & ~(r)
#define AND(d,l,r) (d) = (l) & (r)

GEN_OP2(ctrump_bitmap_or, OR)
GEN_OP2(ctrump_bitmap_nor, NOR)
GEN_OP2(ctrump_bitmap_nand, NAND)
GEN_OP2(ctrump_bitmap_and, AND)

#define GEN_OP3(name,OP)                                \
void                                                    \
name(ctrump_bitmap_t dest,                              \
     ctrump_bitmap_t src0,                              \
     ctrump_bitmap_t src1,                              \
     ctrump_bitmap_t src2,                              \
     unsigned int length)                               \
{                                                       \
    unsigned int n = WORDSIZE_OF_BITMAP(length);        \
    unsigned int i;                                     \
    for (i=0; i<n; i++) {                               \
        OP(dest[i],src0[i],src1[i],src2[i]);            \
    }                                                   \
}

#define NAND_OR(d,s0,s1,s2) (d) = (((s0)&~(s1)) | (s2))

GEN_OP3(ctrump_bitmap_nand_or,NAND_OR)

int 
ctrump_bitmap_eq(ctrump_bitmap_t x,
                 ctrump_bitmap_t y,
                 unsigned int length)
{
    unsigned int n = WORDSIZE_OF_BITMAP(length);
    ctrump_bitmap_bits_t mask = (1<<(length % sizeof(ctrump_bitmap_bits_t)))-1;
    unsigned int b;
    unsigned int ret = 1;

    if (n) {
        while (n > 0) {
            n--;

            ret = ret & (x[n] == y[n]);
        }

        b = (x[n]&mask) == (y[n]&mask);

        return ret & b;
    } else {
        return 1;
    }
}

void
ctrump_bitmap_tostr(char *buf,
                    ctrump_bitmap_t x,
                    unsigned int length)
{
    int i;
    for (i=0; i<length; i++) {
        if (ctrump_bitmap_p(x,i)) {
            buf[i] = '1';
        } else {
            buf[i] = '0';
        }
    }
}

int
ctrump_print_bitmap_stderr(ctrump_bitmap_t x, unsigned int length)
{
    char strbuf[length];
    int r;
    ctrump_bitmap_tostr(strbuf, x, length);
    r = fwrite(strbuf, 1, length, stderr);
    if (r < 0)
        return -1;
    fputc('\n', stderr);
    return 0;
}

ctrump_bitmap_t
ctrump_bmp_zero(unsigned int nbits, struct ctrump_mempool *pool)
{
    ctrump_bitmap_t ret;
    int wsize = WORDSIZE_OF_BITMAP(nbits);
    int bsize = BYTESIZE_OF_BITMAP(nbits);
    int i;
    ret = ctrump_mempool_alloc(pool, bsize);

    for (i=0; i<wsize; i++) {
        ret[i] = (ctrump_bitmap_bits_t)0;
    }

    return ret;
}

ctrump_bitmap_t
ctrump_bmp_fill(unsigned int nbits, struct ctrump_mempool *pool)
{
    ctrump_bitmap_t ret;
    int wsize = WORDSIZE_OF_BITMAP(nbits);
    int bsize = BYTESIZE_OF_BITMAP(nbits);
    int i;
    ret = ctrump_mempool_alloc(pool, bsize);

    for (i=0; i<wsize; i++) {
        ret[i] = ~(ctrump_bitmap_bits_t)0;
    }

    return ret;
}

ctrump_bitmap_t
ctrump_bmp_alloc(unsigned int nbits, struct ctrump_mempool *pool)
{
    int size = BYTESIZE_OF_BITMAP(nbits);
    return ctrump_mempool_alloc(pool, size);
}


int
ctrump_bitmap_popcnt(ctrump_bitmap_t bmp,
                     unsigned int length)
{
    unsigned int n = WORDSIZE_OF_BITMAP(length);
    int i;
    int cnt = 0;

    clear_unused_bit(bmp, length);

    for (i=0; i<n; i++) {
#ifndef __GNUC__
#error "require __builtin_popcount"
#endif
        cnt += __builtin_popcount(bmp[i]);
    }

    return cnt;
}

---