bloomfliter.ex

defmodule GoGal.BloomFilter do
  # Seed values for hash functions
  @seed {9_881_409, 7_740_287, 1_822_091, 6_436_985, 6_108_165, 9_294_15, 1_815_555, 1_670_246,
         7_190_510, 1_923_245}

  # The number of elements to store in the bloom filter
  @n 1024
  # Bloom filter bit string size (1024*4 = 4096 bit = 512 byte)
  @m @n * 4
  # The number of hash functions to use given by Kernel.ceil(m / n * Math.log(Math.e(), 2))
  @k 6
  def new, do: <<0::size(@m)>>

  def get_mask(element) do
    mask = <<0::size(@m)>>

    1..@k
    |> Enum.reduce(mask, fn i, mask ->
      index =
        element
        |> Murmur.hash_x86_32(elem(@seed, i))
        |> rem(@m)

      set_bit(mask, index)
    end)
  end

  def member?(bit_string, element) when is_bitstring(bit_string) do
    Enum.all?(1..@k, fn i ->
      pos = rem(Murmur.hash_x86_32(element, elem(@seed, i)), @m)

      bit_set?(bit_string, pos)
    end)
  end

  def bor(
        <<bit_string_prefix::size(1), bit_string_rest::bits>>,
        <<mask_prefix::size(1), mask_rest::bits>>
      ) do
    bit =
      if(bit_string_prefix == 1 || mask_prefix == 1,
        do: 1,
        else: 0
      )

    <<bit::size(1), bor(bit_string_rest, mask_rest)::bits>>
  end

  def bor(<<>>, <<>>), do: <<>>
  def bits(<<prefix::size(1), rest::bits>>), do: [prefix | bits(rest)]

  def bits(<<>>), do: []

  def set_bit(bit_string, pos) when is_bitstring(bit_string) do
    <<prefix::size(pos), val::size(1), rest::bits>> = bit_string
    # set the bit only if its not set
    if val != 1 do
      <<prefix::size(pos), 1::size(1), rest::bits>>
    else
      bit_string
    end
  end

  defp bit_set?(bit_string, pos) when is_bitstring(bit_string) do
    <<_prefix::size(pos), val::size(1), _rest::bits>> = bit_string
    val == 1
  end
end