6
\$\begingroup\$

I've started learning C and as an exercise I decided to implement some basic functionality for a bloom filter. This is my first C project, so I wanted to see if I was doing things appropriately (project structure/organization wise). Also, I was wondering how to turn this into a shared/static library, since I tried initially with CMake, but I got a bit lost. The project is hosted on github here, but I have included the files below.

Questions relating to code:

  1. Code style/clarity/quality, I just tried to follow what I'd seen in the linux kernel
  2. Code security (No bounds/null checks in the inits)
  3. Code performance
  4. Any general ways to improve

bloom_filter.h

#ifndef BLOOM_FILTER_H
#define BLOOM_FILTER_H 

#include <stdint.h>
#include <stdbool.h>
#include <stdlib.h>
#include <math.h>

#define BLOOM_INIT(bf)                                                  \
        do {                                                            \
                bf = malloc(sizeof(struct bloom_filter));               \
                bf->nelems = 100;                                       \
                bf->mbits = 1600;                                       \
                bf->nhashes = 11;                                       \
                bf->buf = calloc(bf->nelems, sizeof(uint16_t));         \
        } while(0)
#define BLOOM_INIT_NELEMS(bf, nelems)                                   \
        do {                                                            \
                bf = malloc(sizeof(struct bloom_filter));               \
                bf->nelems = nelems;                                    \
                bf->mbits = bf->nelems * (sizeof(uint16_t) << 3);       \
                bf->nhashes = (bf->mbits / bf->nelems) * log(2);        \
                bf->buf = calloc(bf->nelems, sizeof(uint16_t));         \
        } while(0)
#define BLOOM_FREE(bf)          \
        do {                    \
                free(bf->buf);  \
                free(bf);       \
        } while(0)

struct bloom_filter {
        uint8_t nhashes; /* optimal number of hashes unless explicit (m / n * ln(2)) */
        uint16_t *buf; /* bits per element */ 
        uint32_t nelems; /* number of elements */
        uint32_t mbits; /* number of bits (16 * nelems) */
};

void bloom_insert_int(struct bloom_filter *bf, const int32_t data);
void bloom_insert_string(struct bloom_filter *bf, const char *data);
bool bloom_query_int(struct bloom_filter *bf, const int32_t data);
bool bloom_query_string(struct bloom_filter *bf, const char *data);

#endif

bloom_filter.c

#include <string.h>
#include "../include/bloom_filter.h"
#include "hashes.h"

#define SET_BIT(bf, k) (bf->buf[k >> 4] |= 1 << (k % 16))
#define TEST_BIT(bf, k) (bf->buf[k >> 4] & 1 << (k % 16))

#define H_a(pointer, bytes, out) (MurmurHash3_x86_32((void *)pointer, bytes, 0, out))
#define H_b(pointer, bytes) (FNV1A_Hash_WHIZ((void *)pointer, bytes))
#define G(in, scalar, pointer, bytes, size) (abs(in[0] + scalar * H_b(pointer, bytes)) % size)

void bloom_insert_int(struct bloom_filter *bf, const int32_t data)
{
        uint8_t i;
        uint32_t hash[4];

        H_a(&data, sizeof(data), hash);
        for(i = 0; i < bf->nhashes; ++i) 
                SET_BIT(bf, G(hash, i, &data, sizeof(data), bf->mbits));
}
void bloom_insert_string(struct bloom_filter *bf, const char *data)
{
        uint8_t i;
        uint32_t hash[4];
        uint64_t len = strlen(data);

        H_a(data, len, hash);
        for(i = 0; i < bf->nhashes; ++i)
                SET_BIT(bf, G(hash, i, data, len, bf->mbits));
}

bool bloom_query_int(struct bloom_filter *bf, const int32_t data)
{
        uint8_t i;
        uint32_t hash[4];

        H_a(&data, sizeof(data), hash);
        for(i = 0; i < bf->nhashes; ++i) 
                if(!TEST_BIT(bf, G(hash, i, &data, sizeof(data), bf->mbits)))
                        return false;
        return true;
}

bool bloom_query_string(struct bloom_filter *bf, const char *data)
{
        uint8_t i;
        uint32_t hash[4];
        uint64_t len = strlen(data);

        H_a(data, len, hash);
        for(i = 0; i < bf->nhashes; ++i) 
                if(!TEST_BIT(bf, G(hash, i, data, len, bf->mbits)))
                        return false;
        return true;
}

hashes.h

/* Murmur hash implementation: modified from - https://github.com/PeterScott */
/* FNV1A hash implementation: modified from - http://encode.ru/threads/612-Fastest-decompressor!?p=22184&viewfull=1#post22184 */

#ifndef HASHES_H
#define HASHES_H

#ifdef __GNUC__
#define FORCE_INLINE __attribute__((always_inline)) inline
#else
#define FORCE_INLINE inline
#endif

#include <stdint.h>

static FORCE_INLINE uint32_t rotl32(uint32_t x, int8_t r)
{
        return (x << r) | (x >> (32 - r));
}

#define ROTL32(x,y) rotl32(x,y)
#define getblock(p, i) (p[i])

static FORCE_INLINE uint32_t fmix32(uint32_t h)
{
        h ^= h >> 16;
        h *= 0x85ebca6b;
        h ^= h >> 13;
        h *= 0xc2b2ae35;
        h ^= h >> 16;

        return h;
}

void MurmurHash3_x86_32(const void *key, int len, uint32_t seed, void *out)
{
        int i;
        uint32_t h1 = seed;
        uint32_t c1 = 0xcc9e2d51;
        uint32_t c2 = 0x1b873593;
        const int nblocks = len / 4;
        const uint8_t *data = (const uint8_t *)key;
        const uint32_t *blocks = (const uint32_t *)(data + nblocks*4);

        for(i = -nblocks; i; i++) {
                uint32_t k1 = getblock(blocks,i);
                k1 *= c1;
                k1 = ROTL32(k1,15);
                k1 *= c2;
                h1 ^= k1;
                h1 = ROTL32(h1,13); 
                h1 = h1 * 5 + 0xe6546b64;
        }

        uint32_t k1 = 0;
        const uint8_t *tail = (const uint8_t *)(data + nblocks*4);

        switch(len & 3) {
                case 3: k1 ^= tail[2] << 16;
                case 2: k1 ^= tail[1] << 8;
                case 1: k1 ^= tail[0];
                k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1;
        };

        h1 ^= len;
        h1 = fmix32(h1);
        *(uint32_t *)out = h1;
}

uint32_t FNV1A_Hash_WHIZ(void *str, size_t wrdlen)
{
        char *p = (char *)str;
        uint32_t hash32 = 2166136261;
        const uint32_t prime = 1607;

        for(; wrdlen >= sizeof(uint32_t); wrdlen -= sizeof(uint32_t), p += sizeof(uint32_t)) {
                hash32 = (hash32 ^ *(uint32_t *)p) * prime;
        }
        if (wrdlen & sizeof(uint16_t)) {
                hash32 = (hash32 ^ *(uint16_t *)p) * prime;
                p += sizeof(uint16_t);
        }
        if (wrdlen & 1) hash32 = (hash32 ^ *p) * prime;

        return hash32 ^ (hash32 >> 16);
}

#endif
\$\endgroup\$
  • 1
    \$\begingroup\$ Why did you choose to provide those macros instead of writing functions for them as well? \$\endgroup\$ – D. Jurcau Aug 27 '16 at 14:27
2
\$\begingroup\$

Possible extra calls to hash functions

If you look at the SET_BIT macro, it uses k twice:

 #define SET_BIT(bf, k) (bf->buf[k >> 4] |= 1 << (k % 16))

The way you use SET_BIT is like this:

#define H_b(pointer, bytes) (FNV1A_Hash_WHIZ((void *)pointer, bytes))
#define G(in, scalar, pointer, bytes, size) (abs(in[0] + scalar * H_b(pointer, bytes)) % size)

SET_BIT(bf, G(hash, i, &data, sizeof(data), bf->mbits));

So in the final expansion of SET_BIT(), you will be calling FNV1A_Hash_WHIZ() twice. Now, your compiler may be smart enough to realize that FNV1A_Hash_WHIZ() has no side effects, so it can be called only once. When I tested your code, I found the following:

  • gcc was able to optimize the code to only call FNV1A_Hash_WHIZ() once.
  • However, when I took the hash function out of the header and put it in a separate .c file, then gcc was not able to optimize the extra call away, and it ended up with two calls instead.

To avoid depending on the compiler to fix things, you could just rewrite the macro like this:

#define SET_BIT(bf, k)  do {                                       \
                            uint32_t key = (k);                    \
                            bf->buf[key >> 4] |= 1 << (key & 0xf); \
                        } while(0)

Const keyword

For a function such as this:

bool bloom_query_int(struct bloom_filter *bf, const int32_t data)

the const keyword should be on bf to indicate that the bloom filter does not get modified from a query. Using const on data doesn't really do anything useful. So I would recommend:

bool bloom_query_int(const struct bloom_filter *bf, int32_t data)

Code in header file

I generally would not recommend putting code in a header file, except for static inline functions. Because you defined normal functions in hashes.h, that file can only be included from one .c file. If you tried to include it from another .c file, you would get a "multiply defined function" link error.

Macro problems

Your BLOOM_INIT_NELEMS() macro doesn't work:

#define BLOOM_INIT_NELEMS(bf, nelems)                                   \
        do {                                                            \
                bf = malloc(sizeof(struct bloom_filter));               \
                bf->nelems = nelems;                                    \

Notice the line bf->nelems = nelems;. If you passed 100 in for nelems, the line would expand to bf->100 = 100;.

Also, in your macros, I would recommend putting parentheses around each use of an input argument. For example, this macro:

#define SET_BIT(bf, k) (bf->buf[k >> 4] |= 1 << (k % 16))

is a bit unsafe as written. It could be improved like this:

#define SET_BIT(bf, k) ((bf)->buf[(k) >> 4] |= 1 << ((k) % 16))

(Although of course I recommended a different rewrite above).

\$\endgroup\$
2
\$\begingroup\$

For a C starter very well-written code!

There's not much to say about the code-style itself, though I've tried to improve it a bit. My code is on GitHub, too.

Let's go through the relevant commits.

  • code style: add braces, move decls:
    It's often frowned-upon to elide the braces even in cases like

    if (P)
      Q;
    

    better either use

    if (P) Q;
    

    or add the braces. Eliding the braces (without putting it in one line) has often produced bugs like this:

    if (P)
      Q;
      S;
    

    which will always execute S.

    The next thing I did was move the declaration of the iterating i into the for-loop. This will not pollute the current scope and makes it clear where the variable is used and what for.

  • remove unnecessary do-while:
    There's no need for the do-while(0) here -- a simple scope-block does the trick too, eg.:

    #define BLOOM_FREE(bf)          \
    {                               \
        free(bf->buf);              \
        free(bf);                   \
    }
    

    Also you could change BLOOM_INIT(bf) to:

    #define BLOOM_INIT(bf) BLOOM_INIT_NELEMS(bf, 100)
    

    This is a bit less optimized but makes it clear that it's just a shorthand.

  • add 'generic' insert_bytes function
    Only providing functionality for int32_t and 0-terminated strings is a bit limited. Either provide some kind of generic function (the caller must pass width of type and a void * to the value) or allow passing standard bytes (ie. char *) that do not need to be 0-terminated, I chose the latter way.
    Also you can reuse most of the code this way.

Other remarks:

  • sizeof(uint16_t) << 3 can be safely replaced by 16, since that's what you specified (16-bit unsigned int). If you want to expand your code later-on to different width, you could try using macros like described here

    #define PPCAT_NX(A, B, C) A ## B ## C
    #define PPCAT(A, B, C) PPCAT_NX(A, B, C)
    
    #define PRECISION 16
    #define BUF_TYPE PPCAT(uint, PRECISION, _t)
    
    int main() {
      BUF_TYPE x; /* declares a uint16_t */
    }
    

    Then you could edit sizeof(uint16_t) << 3 and (bf->mbits / bf->nelems) to just PRECISION which would be far easier to understand and possibly more portable too.

  • You might want to find better types for the filter as currently there are many conversions in the code that might change the values of the variables. Just remove the "no-" in the conversion warning flags in the CMakeLists.txt file to see what I mean. Much of it is probably harmless on standard Linux/GCC toolchains but I wouldn't rely too much on it. Better fix it up.

\$\endgroup\$
  • 1
    \$\begingroup\$ The do whiles are necessary for the macros to act as statements. For example: if (condition) BLOOM_FREE(bf); Without the do while, only the first line of the macro would be executed conditionally. \$\endgroup\$ – JS1 Aug 27 '16 at 16:47
  • \$\begingroup\$ Oh, but yes, that's clear. An empty scope-block should do the trick though, too. \$\endgroup\$ – larkey Aug 27 '16 at 18:56
  • 1
    \$\begingroup\$ An empty scope block doesn't work in this case: if (condition) BLOOM_FREE(bf); else return false; The extra semicolon at the end of the empty scope block will make the else clause not compile. See this stackoverflow question \$\endgroup\$ – JS1 Aug 27 '16 at 21:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.