diff options
Diffstat (limited to '')
-rw-r--r-- | security/nss/lib/ssl/sslbloom.c | 94 |
1 files changed, 94 insertions, 0 deletions
diff --git a/security/nss/lib/ssl/sslbloom.c b/security/nss/lib/ssl/sslbloom.c new file mode 100644 index 0000000000..3d5f9d1f17 --- /dev/null +++ b/security/nss/lib/ssl/sslbloom.c @@ -0,0 +1,94 @@ +/* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- */ +/* + * A bloom filter. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +#include "sslbloom.h" +#include "prnetdb.h" +#include "secport.h" + +static inline unsigned int +sslBloom_Size(unsigned int bits) +{ + return (bits >= 3) ? (1 << (bits - 3)) : 1; +} + +SECStatus +sslBloom_Init(sslBloomFilter *filter, unsigned int k, unsigned int bits) +{ + PORT_Assert(filter); + PORT_Assert(bits > 0); + PORT_Assert(bits <= sizeof(PRUint32) * 8); + PORT_Assert(k > 0); + + filter->filter = PORT_ZNewArray(PRUint8, sslBloom_Size(bits)); + if (!filter->filter) { + return SECFailure; /* Error code already set. */ + } + + filter->k = k; + filter->bits = bits; + return SECSuccess; +} + +void +sslBloom_Zero(sslBloomFilter *filter) +{ + PORT_Memset(filter->filter, 0, sslBloom_Size(filter->bits)); +} + +void +sslBloom_Fill(sslBloomFilter *filter) +{ + PORT_Memset(filter->filter, 0xff, sslBloom_Size(filter->bits)); +} + +static PRBool +sslBloom_AddOrCheck(sslBloomFilter *filter, const PRUint8 *hashes, PRBool add) +{ + unsigned int iteration; + unsigned int bitIndex; + PRUint32 tmp = 0; + PRUint8 mask; + unsigned int bytes = (filter->bits + 7) / 8; + unsigned int shift = (bytes * 8) - filter->bits; + PRBool found = PR_TRUE; + + PORT_Assert(bytes <= sizeof(unsigned int)); + + for (iteration = 0; iteration < filter->k; ++iteration) { + PORT_Memcpy(((PRUint8 *)&tmp) + (sizeof(tmp) - bytes), + hashes, bytes); + hashes += bytes; + bitIndex = PR_ntohl(tmp) >> shift; + + mask = 1 << (bitIndex % 8); + found = found && filter->filter[bitIndex / 8] & mask; + if (add) { + filter->filter[bitIndex / 8] |= mask; + } + } + return found; +} + +PRBool +sslBloom_Add(sslBloomFilter *filter, const PRUint8 *hashes) +{ + return sslBloom_AddOrCheck(filter, hashes, PR_TRUE); +} + +PRBool +sslBloom_Check(sslBloomFilter *filter, const PRUint8 *hashes) +{ + return sslBloom_AddOrCheck(filter, hashes, PR_FALSE); +} + +void +sslBloom_Destroy(sslBloomFilter *filter) +{ + PORT_Free(filter->filter); + PORT_Memset(filter, 0, sizeof(*filter)); +} |