#!/bin/sh
# FreeBSD-kompatibler Bloom-Filter in /bin/sh
#
# Kommandos:
#   ./bloom.sh init <datei> <groesse_in_bytes>
#   ./bloom.sh add <datei> <wert>
#   ./bloom.sh check <datei> <wert>
#
# WICHTIG:
#   <groesse_in_bytes> ist die Dateigroesse in BYTES.
#   Intern nutzt der Filter aber BITS.
#   Beispiel: 10 Bytes = 80 Bitpositionen.
#
# Dieses Skript implementiert einen echten bitweisen Bloom-Filter:
#   - jeder Hash wird auf eine Bitposition gemappt
#   - daraus werden Byte-Index und Bit-Offset berechnet
#   - gesetzt/geprueft wird nur das konkrete Bit
#
# Faustregeln:
#   - m = Anzahl Bits im Filter
#   - n = erwartete Anzahl Eintraege
#   - optimale Hashanzahl k ~= (m/n) * ln(2)
#
# Beispiel:
#   ./bloom.sh init /tmp/test.bloom 10000
#   ./bloom.sh add /tmp/test.bloom fabian
#   ./bloom.sh check /tmp/test.bloom fabian
#   ./bloom.sh check /tmp/test.bloom gasnetz

set -u

# Anzahl der Hashfunktionen.
# 7 ist ein gaengiger Wert fuer viele praktische Bloom-Filter-Setups.
HASH_COUNT=7

usage() {
    echo "Verwendung:"
    echo "  $0 init <datei> <groesse_in_bytes>"
    echo "  $0 add <datei> <wert>"
    echo "  $0 check <datei> <wert>"
    exit 1
}

die() {
    echo "Fehler: $*" >&2
    exit 1
}

require_file() {
    [ $# -eq 1 ] || die "interner Fehler in require_file"
    [ -f "$1" ] || die "Datei nicht gefunden: $1"
}

get_size() {
    stat -f %z "$1" 2>/dev/null || die "Konnte Dateigroesse nicht lesen: $1"
}

hash_hex() {
    # $1 = Seed
    # $2 = Wert
    #
    # Trenner ":" verhindert triviale Zweideutigkeiten.
    # Es werden nur die ersten 7 Hex-Zeichen verwendet:
    #   0x0000000 bis 0x0FFFFFFF
    # Das bleibt in /bin/sh-Arithmetik handhabbar.
    seed=$1
    value=$2
    printf "%s:%s" "$seed" "$value" | md5 -q | cut -c1-7
}

bit_index_for() {
    # $1 = Dateigroesse in Bytes
    # $2 = Wert
    # $3 = Seed
    #
    # Liefert eine Bitposition im Bereich 0 .. (size*8 - 1)
    size_bytes=$1
    value=$2
    seed=$3

    total_bits=$(( size_bytes * 8 ))
    [ "$total_bits" -gt 0 ] 2>/dev/null || die "ungueltige Filtergroesse"

    hex=$(hash_hex "$seed" "$value") || die "Hashing fehlgeschlagen"
    echo $(( 0x$hex % total_bits ))
}

read_byte() {
    # $1 = Datei
    # $2 = Byte-Index
    #
    # Liest genau ein Byte und gibt seinen Dezimalwert 0..255 aus.
    file=$1
    byte_index=$2

    byte=$(dd if="$file" bs=1 skip="$byte_index" count=1 2>/dev/null \
        | od -An -t u1 | tr -d '[:space:]')

    [ -n "$byte" ] || byte=0
    echo "$byte"
}

write_byte() {
    # $1 = Datei
    # $2 = Byte-Index
    # $3 = Byte-Wert 0..255
    #
    # Schreibt genau ein Byte an die angegebene Position.
    file=$1
    byte_index=$2
    byte_value=$3

    case "$byte_value" in
        ''|*[!0-9]*)
            die "ungueltiger Byte-Wert: $byte_value"
            ;;
    esac

    [ "$byte_value" -ge 0 ] 2>/dev/null || die "Byte-Wert < 0"
    [ "$byte_value" -le 255 ] 2>/dev/null || die "Byte-Wert > 255"

    # In dreistellige Oktalnotation wandeln und genau dieses Byte schreiben.
    oct=$(printf '%03o' "$byte_value") || die "Oktalwandlung fehlgeschlagen"

    # shellcheck disable=SC2059
    printf "\\$oct" | dd of="$file" bs=1 seek="$byte_index" count=1 conv=notrunc 2>/dev/null \
        || die "Schreiben fehlgeschlagen bei Byte-Index $byte_index"
}

cmd_init() {
    [ $# -eq 2 ] || usage
    file=$1
    size=$2

    case "$size" in
        ''|*[!0-9]*)
            die "Groesse muss eine positive ganze Zahl sein"
            ;;
    esac

    [ "$size" -gt 0 ] 2>/dev/null || die "Groesse muss groesser als 0 sein"

    dd if=/dev/zero of="$file" bs=1 count="$size" 2>/dev/null \
        || die "Init fehlgeschlagen"

    echo "OK: Bloom-Filter initialisiert: $file ($size Bytes = $(( size * 8 )) Bits)"
}

cmd_add() {
    [ $# -eq 2 ] || usage
    file=$1
    value=$2

    require_file "$file"
    size=$(get_size "$file")

    i=1
    while [ "$i" -le "$HASH_COUNT" ]; do
        bit_index=$(bit_index_for "$size" "$value" "$i") || exit 1

        # Bitposition in Byte-Index und Bit-Offset zerlegen.
        byte_index=$(( bit_index / 8 ))
        bit_offset=$(( bit_index % 8 ))
        mask=$(( 1 << bit_offset ))

        # Zielbyte lesen, Bit setzen, Byte zurueckschreiben.
        old_byte=$(read_byte "$file" "$byte_index") || exit 1
        new_byte=$(( old_byte | mask ))

        write_byte "$file" "$byte_index" "$new_byte" || exit 1

        i=$(( i + 1 ))
    done

    echo "OK: hinzugefuegt"
}

cmd_check() {
    [ $# -eq 2 ] || usage
    file=$1
    value=$2

    require_file "$file"
    size=$(get_size "$file")

    i=1
    while [ "$i" -le "$HASH_COUNT" ]; do
        bit_index=$(bit_index_for "$size" "$value" "$i") || exit 1

        # Dieselbe Bitposition wie beim add berechnen.
        byte_index=$(( bit_index / 8 ))
        bit_offset=$(( bit_index % 8 ))
        mask=$(( 1 << bit_offset ))

        # Byte lesen und nur das relevante Bit pruefen.
        byte=$(read_byte "$file" "$byte_index") || exit 1

        if [ $(( byte & mask )) -eq 0 ] 2>/dev/null; then
            echo "NO"
            exit 0
        fi

        i=$(( i + 1 ))
    done

    echo "YES"
    exit 0
}

[ $# -ge 1 ] || usage
cmd=$1
shift

case "$cmd" in
    init)  cmd_init  "$@" ;;
    add)   cmd_add   "$@" ;;
    check) cmd_check "$@" ;;
    *)     usage ;;
esac