| /* -*- 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)); |
| } |