1*aca3beaaSApple OSS Distributions /* 2*aca3beaaSApple OSS Distributions * Copyright (c) 2021 Apple Inc. All rights reserved. 3*aca3beaaSApple OSS Distributions * 4*aca3beaaSApple OSS Distributions * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ 5*aca3beaaSApple OSS Distributions * 6*aca3beaaSApple OSS Distributions * This file contains Original Code and/or Modifications of Original Code 7*aca3beaaSApple OSS Distributions * as defined in and that are subject to the Apple Public Source License 8*aca3beaaSApple OSS Distributions * Version 2.0 (the 'License'). You may not use this file except in 9*aca3beaaSApple OSS Distributions * compliance with the License. The rights granted to you under the License 10*aca3beaaSApple OSS Distributions * may not be used to create, or enable the creation or redistribution of, 11*aca3beaaSApple OSS Distributions * unlawful or unlicensed copies of an Apple operating system, or to 12*aca3beaaSApple OSS Distributions * circumvent, violate, or enable the circumvention or violation of, any 13*aca3beaaSApple OSS Distributions * terms of an Apple operating system software license agreement. 14*aca3beaaSApple OSS Distributions * 15*aca3beaaSApple OSS Distributions * Please obtain a copy of the License at 16*aca3beaaSApple OSS Distributions * http://www.opensource.apple.com/apsl/ and read it before using this file. 17*aca3beaaSApple OSS Distributions * 18*aca3beaaSApple OSS Distributions * The Original Code and all software distributed under the License are 19*aca3beaaSApple OSS Distributions * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 20*aca3beaaSApple OSS Distributions * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 21*aca3beaaSApple OSS Distributions * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 22*aca3beaaSApple OSS Distributions * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 23*aca3beaaSApple OSS Distributions * Please see the License for the specific language governing rights and 24*aca3beaaSApple OSS Distributions * limitations under the License. 25*aca3beaaSApple OSS Distributions * 26*aca3beaaSApple OSS Distributions * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ 27*aca3beaaSApple OSS Distributions */ 28*aca3beaaSApple OSS Distributions 29*aca3beaaSApple OSS Distributions #ifndef _NET_BLOOM_FILTER_H_ 30*aca3beaaSApple OSS Distributions #define _NET_BLOOM_FILTER_H_ 31*aca3beaaSApple OSS Distributions 32*aca3beaaSApple OSS Distributions #include <sys/types.h> 33*aca3beaaSApple OSS Distributions 34*aca3beaaSApple OSS Distributions #ifdef __cplusplus 35*aca3beaaSApple OSS Distributions extern "C" { 36*aca3beaaSApple OSS Distributions #endif 37*aca3beaaSApple OSS Distributions 38*aca3beaaSApple OSS Distributions // A Bloom Filter is a space-efficient probabilistic data structure 39*aca3beaaSApple OSS Distributions // that is used to test whether an element is a member of a set. It has a small 40*aca3beaaSApple OSS Distributions // rate of false positives, but it is guaranteed to have no false negatives. 41*aca3beaaSApple OSS Distributions // 42*aca3beaaSApple OSS Distributions // net_bloom_filter is a minimal implementation for use in kernel networking 43*aca3beaaSApple OSS Distributions // that uses three hash functions: net_flowhash_jhash, net_flowhash_mh3_x64_128, 44*aca3beaaSApple OSS Distributions // and net_flowhash_mh3_x86_32. This is optimal for a 10% false positive rate. 45*aca3beaaSApple OSS Distributions // The optimal number of bits should be calculated as: 46*aca3beaaSApple OSS Distributions // num_bits = ((2.3 * ELEMENT_COUNT) / 0.48) 47*aca3beaaSApple OSS Distributions 48*aca3beaaSApple OSS Distributions struct net_bloom_filter { 49*aca3beaaSApple OSS Distributions uint32_t b_table_num_bits; 50*aca3beaaSApple OSS Distributions uint32_t b_table[0]; 51*aca3beaaSApple OSS Distributions }; 52*aca3beaaSApple OSS Distributions 53*aca3beaaSApple OSS Distributions struct net_bloom_filter * 54*aca3beaaSApple OSS Distributions net_bloom_filter_create(uint32_t num_bits); 55*aca3beaaSApple OSS Distributions 56*aca3beaaSApple OSS Distributions size_t 57*aca3beaaSApple OSS Distributions net_bloom_filter_get_size(uint32_t num_bits); 58*aca3beaaSApple OSS Distributions 59*aca3beaaSApple OSS Distributions void 60*aca3beaaSApple OSS Distributions net_bloom_filter_destroy(struct net_bloom_filter *filter); 61*aca3beaaSApple OSS Distributions 62*aca3beaaSApple OSS Distributions void 63*aca3beaaSApple OSS Distributions net_bloom_filter_insert(struct net_bloom_filter *filter, 64*aca3beaaSApple OSS Distributions const void *buffer, 65*aca3beaaSApple OSS Distributions uint32_t length); 66*aca3beaaSApple OSS Distributions 67*aca3beaaSApple OSS Distributions bool 68*aca3beaaSApple OSS Distributions net_bloom_filter_contains(struct net_bloom_filter *filter, 69*aca3beaaSApple OSS Distributions const void *buffer, 70*aca3beaaSApple OSS Distributions uint32_t length); 71*aca3beaaSApple OSS Distributions 72*aca3beaaSApple OSS Distributions #ifdef __cplusplus 73*aca3beaaSApple OSS Distributions } 74*aca3beaaSApple OSS Distributions #endif 75*aca3beaaSApple OSS Distributions 76*aca3beaaSApple OSS Distributions #endif /* _NET_BLOOM_FILTER_H_ */ 77