bloom.h

Go to the documentation of this file.

/*
 * This file is part of LibCSS.
 * Licensed under the MIT License,
 *                http://www.opensource.org/licenses/mit-license.php
 * Copyright 2013 Michael Drake <tlsa@netsurf-browser.org>
 */
 
#ifndef libcss_bloom_h_
#define libcss_bloom_h_
 
#include <stdint.h>
#include <string.h>
 
/* Size of bloom filter as multiple of 32 bits.
 * Has to be 4, 8, or 16.
 * Larger increases optimisation of style selection engine but uses more memory.
 */
#define CSS_BLOOM_SIZE 4
 
 
 
/* Check valid bloom filter size */
#if !(CSS_BLOOM_SIZE == 4 || CSS_BLOOM_SIZE == 8 || CSS_BLOOM_SIZE == 16)
# error Unsupported bloom filter size.  Size must be {4|8|16}.
#endif
 
/* Setup index bit mask */
#define INDEX_BITS_N (CSS_BLOOM_SIZE - 1)
 
 
 
/* type for bloom */
typedef uint32_t css_bloom;
 
 
static inline void css_bloom_add_hash(css_bloom bloom[CSS_BLOOM_SIZE],
                lwc_hash hash)
{
        unsigned int bit = hash & 0x1f; /* Top 5 bits */
        unsigned int index = (hash >> 5) & INDEX_BITS_N; /* Next N bits */
 
        bloom[index] |= (1u << bit);
}
 
 
static inline bool css_bloom_has_hash(const css_bloom bloom[CSS_BLOOM_SIZE],
                lwc_hash hash)
{
        unsigned int bit = hash & 0x1f; /* Top 5 bits */
        unsigned int index = (hash >> 5) & INDEX_BITS_N; /* Next N bits */
 
        return (bloom[index] & (1u << bit));
}
 
 
static inline bool css_bloom_in_bloom(
                const css_bloom a[CSS_BLOOM_SIZE],
                const css_bloom b[CSS_BLOOM_SIZE])
{
        if ((a[0] & b[0]) != a[0])
                return false;
        if ((a[1] & b[1]) != a[1])
                return false;
        if ((a[2] & b[2]) != a[2])
                return false;
        if ((a[3] & b[3]) != a[3])
                return false;
#if (CSS_BLOOM_SIZE > 4)
        if ((a[4] & b[4]) != a[4])
                return false;
        if ((a[5] & b[5]) != a[5])
                return false;
        if ((a[6] & b[6]) != a[6])
                return false;
        if ((a[7] & b[7]) != a[7])
                return false;
#endif
#if (CSS_BLOOM_SIZE > 8)
        if ((a[8] & b[8]) != a[8])
                return false;
        if ((a[9] & b[9]) != a[9])
                return false;
        if ((a[10] & b[10]) != a[10])
                return false;
        if ((a[11] & b[11]) != a[11])
                return false;
        if ((a[12] & b[12]) != a[12])
                return false;
        if ((a[13] & b[13]) != a[13])
                return false;
        if ((a[14] & b[14]) != a[14])
                return false;
        if ((a[15] & b[15]) != a[15])
                return false;
#endif
        return true;
}
 
 
static inline void css_bloom_merge(
                const css_bloom a[restrict CSS_BLOOM_SIZE],
                      css_bloom b[restrict CSS_BLOOM_SIZE])
{
        b[0] |= a[0];
        b[1] |= a[1];
        b[2] |= a[2];
        b[3] |= a[3];
#if (CSS_BLOOM_SIZE > 4)
        b[4] |= a[4];
        b[5] |= a[5];
        b[6] |= a[6];
        b[7] |= a[7];
#endif
#if (CSS_BLOOM_SIZE > 8)
        b[8] |= a[8];
        b[9] |= a[9];
        b[10] |= a[10];
        b[11] |= a[11];
        b[12] |= a[12];
        b[13] |= a[13];
        b[14] |= a[14];
        b[15] |= a[15];
#endif
}
 
 
static inline void css_bloom_init(css_bloom bloom[CSS_BLOOM_SIZE])
{
        memset(bloom, 0, sizeof(*bloom) * CSS_BLOOM_SIZE);
}
 
#endif