diff options
author | Yorhel <git@yorhel.nl> | 2012-10-11 17:24:36 +0200 |
---|---|---|
committer | Yorhel <git@yorhel.nl> | 2012-10-11 17:25:04 +0200 |
commit | 5e91e5245e60b1df4fb168d21e0a01a3e8431e8f (patch) | |
tree | 4629547b4f6d40362dbd32c7664d1f27125bbc2e /src/bloom.c | |
parent | 77112dc8f4ed6dd9f2324b376bf52706a08e0033 (diff) |
Added ADC BLOM support and 'adc_blom' option to enable it
This bloom filter implementation is slightly different from DC++ and
Jucy, and I believe this one to be correct. See my blog post for the
details:
http://www.dcbase.org/forums/viewtopic.php?f=18&t=787
Diffstat (limited to 'src/bloom.c')
-rw-r--r-- | src/bloom.c | 74 |
1 files changed, 74 insertions, 0 deletions
diff --git a/src/bloom.c b/src/bloom.c new file mode 100644 index 0000000..4af2865 --- /dev/null +++ b/src/bloom.c @@ -0,0 +1,74 @@ +/* ncdc - NCurses Direct Connect client + + Copyright (c) 2011-2012 Yoran Heling + + Permission is hereby granted, free of charge, to any person obtaining + a copy of this software and associated documentation files (the + "Software"), to deal in the Software without restriction, including + without limitation the rights to use, copy, modify, merge, publish, + distribute, sublicense, and/or sell copies of the Software, and to + permit persons to whom the Software is furnished to do so, subject to + the following conditions: + + The above copyright notice and this permission notice shall be included + in all copies or substantial portions of the Software. + + THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. + IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY + CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, + TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE + SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + +*/ + +/* This bloom filter implementation assumes a hash size of 192 bits */ + +#include "ncdc.h" +#include "bloom.h" + + +#if INTERFACE + +typedef struct { + int m; /* Size of the bloom filter in _bytes_ */ + int k; /* Number of sub-hashes */ + int h; /* Number of bits for each sub-hash */ + unsigned char *d; +} bloom_t; + +#endif + + +/* Returns -1 if m,k,h are not valid, 0 on success */ +int bloom_init(bloom_t *b, int m, int k, int h) { + /* Restrictions, as defined by the ADC BLOM spec */ + if(m <= 0 || k <= 0 || h <= 0 || (m & 7) != 0 || k*h > 192 || h > 64 || ((guint64)1)<<(h-3) <= ((guint64)m)>>3) + return -1; + b->m = m; + b->k = k; + b->h = h; + b->d = g_malloc0(m); + return 0; +} + + +void bloom_add(bloom_t *b, const char *hash) { + int i, j, pos = 0; + guint64 tmp; + for(i=0; i<b->k; i++) { + tmp = 0; + for(j=0; j<b->h; j++) { + tmp |= ((guint64)((((const unsigned char *)hash)[pos>>3] >> (pos&7)) & 1)) << j; + pos++; + } + j = tmp % (b->m<<3); + b->d[j>>3] |= 1<<(j&7); + } +} + + +void bloom_free(bloom_t *b) { + g_free(b->d); +} |