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] |= (1 << 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] & (1 << 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