tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

sslbloom.c (2344B)

      1 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
      2 /*
      3 * A bloom filter.
      4 *
      5 * This Source Code Form is subject to the terms of the Mozilla Public
      6 * License, v. 2.0. If a copy of the MPL was not distributed with this
      7 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
      8 
      9 #include "sslbloom.h"
     10 #include "prnetdb.h"
     11 #include "secport.h"
     12 
     13 static inline unsigned int
     14 sslBloom_Size(unsigned int bits)
     15 {
     16    return (bits >= 3) ? (1 << (bits - 3)) : 1;
     17 }
     18 
     19 SECStatus
     20 sslBloom_Init(sslBloomFilter *filter, unsigned int k, unsigned int bits)
     21 {
     22    PORT_Assert(filter);
     23    PORT_Assert(bits > 0);
     24    PORT_Assert(bits <= sizeof(PRUint32) * 8);
     25    PORT_Assert(k > 0);
     26 
     27    filter->filter = PORT_ZNewArray(PRUint8, sslBloom_Size(bits));
     28    if (!filter->filter) {
     29        return SECFailure; /* Error code already set. */
     30    }
     31 
     32    filter->k = k;
     33    filter->bits = bits;
     34    return SECSuccess;
     35 }
     36 
     37 void
     38 sslBloom_Zero(sslBloomFilter *filter)
     39 {
     40    PORT_Memset(filter->filter, 0, sslBloom_Size(filter->bits));
     41 }
     42 
     43 void
     44 sslBloom_Fill(sslBloomFilter *filter)
     45 {
     46    PORT_Memset(filter->filter, 0xff, sslBloom_Size(filter->bits));
     47 }
     48 
     49 static PRBool
     50 sslBloom_AddOrCheck(sslBloomFilter *filter, const PRUint8 *hashes, PRBool add)
     51 {
     52    unsigned int iteration;
     53    unsigned int bitIndex;
     54    PRUint32 tmp = 0;
     55    PRUint8 mask;
     56    unsigned int bytes = (filter->bits + 7) / 8;
     57    unsigned int shift = (bytes * 8) - filter->bits;
     58    PRBool found = PR_TRUE;
     59 
     60    PORT_Assert(bytes <= sizeof(unsigned int));
     61 
     62    for (iteration = 0; iteration < filter->k; ++iteration) {
     63        PORT_Memcpy(((PRUint8 *)&tmp) + (sizeof(tmp) - bytes),
     64                    hashes, bytes);
     65        hashes += bytes;
     66        bitIndex = PR_ntohl(tmp) >> shift;
     67 
     68        mask = 1 << (bitIndex % 8);
     69        found = found && filter->filter[bitIndex / 8] & mask;
     70        if (add) {
     71            filter->filter[bitIndex / 8] |= mask;
     72        }
     73    }
     74    return found;
     75 }
     76 
     77 PRBool
     78 sslBloom_Add(sslBloomFilter *filter, const PRUint8 *hashes)
     79 {
     80    return sslBloom_AddOrCheck(filter, hashes, PR_TRUE);
     81 }
     82 
     83 PRBool
     84 sslBloom_Check(sslBloomFilter *filter, const PRUint8 *hashes)
     85 {
     86    return sslBloom_AddOrCheck(filter, hashes, PR_FALSE);
     87 }
     88 
     89 void
     90 sslBloom_Destroy(sslBloomFilter *filter)
     91 {
     92    PORT_Free(filter->filter);
     93    PORT_Memset(filter, 0, sizeof(*filter));
     94 }