QueryRoutingTable.cpp

Go to the documentation of this file.

/*

Copyright (C) 2005-2007 by Peter Dimov.

This file is part of Calitko (http://www.calitko.org).

Calitko is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

Calitko is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with Calitko; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

*/

#include "Qt.h"
#include "QueryRoutingTable.h"
#include <math.h>
#include "Imports.cpp"

using namespace Gnutella::PacketProcessing::QueryRouting;

namespace Gnutella {
namespace PacketProcessing {
namespace QueryRouting {

static const int A_INT=0x4F1BBCDC;
static const quint8 EntryMask [8]  = { 0x80, 0x40, 0x20, 0x10,
                                       0x08, 0x04, 0x02, 0x01};
static const quint8 ValueShift [8] = { 7, 6, 5, 4, 3, 2, 1};

static bool isPowerOf2 (quint32 size)
{
    if( size == 0 ) return false;
    return ( (size & size-1) == 0 );
}

quint8 leftNibbleNonZero (quint8 ch)
{
    return ch & 0xF0 != 0;
}

quint8 rightNibbleNonZero (quint8 ch)
{
    return ch & 0x0F != 0;
}

quint8 checkTwoNibbles(quint8 ch)
{
    quint8 changed = 0;
    changed |= leftNibbleNonZero (ch);
    changed <<= 1;
    changed |= rightNibbleNonZero (ch);
    return changed;
}

/* Atul: If entryBits == 1, there is no point
   checking each bit ;-). If entryBits == 8,
   we can check simply for null char, else
   we check the nibbles
 */
quint8 getBitsToOr (quint8 ch, quint8 entryBits)
{
    Q_ASSERT (entryBits == 1 || entryBits == 4 || entryBits == 8);
    if (entryBits == 1)
        return ch;
    else if (entryBits == 4)
        return checkTwoNibbles (ch);
    else if (entryBits == 8)
        return ch != 0;
    return 0; // Must never come here (see precondition) but provide a fallback.
}

} // QueryRouting
} // PacketProcessing
} // Gnutella

QueryRoutingTable::QueryRoutingTable()
 :  rawTable_(), size_ (0), sizeBits_ (0)
{
}

QueryRoutingTable::~QueryRoutingTable()
{
}

void QueryRoutingTable::reset (quint32 size)
{
    Q_ASSERT (size >= 8 && isPowerOf2 (size));

    if (size_ != size) {
        size_ = size;
        rawTable_ = QByteArray (size / 8, 0);
        double sizeAsDouble = size;
        sizeBits_ = static_cast <quint32> (log (sizeAsDouble) / log (2.0));
    } else {
        rawTable_.fill (0);
    }
}

/* Atul: applyPatch takes a group of entryBits bits
         and checks if any bit is 1 (or the group as a whole
         does not evaluate to 0). It collects these flags into
         variable changed and XOR's with the source
 */
void QueryRoutingTable::applyPatch (QByteArray &patchBuffer, quint8 entryBits)
{
    Q_ASSERT (patchBuffer.size() == qint32 (size_ * entryBits / 8));
    Q_ASSERT (entryBits == 1 || entryBits == 4 || entryBits == 8);

    int k = 0; /* iterates over all bytes of patchBuffer */
    for( int i = 0; i < rawTable_.size(); ++i ) {
        quint8 changed = 0;
        for (int j = 0; j < entryBits; ++j, ++k) {
            int numBits = 8/entryBits;
            changed <<= numBits;
            changed |= getBitsToOr (patchBuffer[k], entryBits);
        }
        rawTable_[i] = rawTable_[i] ^ changed;
    }
}

QByteArray QueryRoutingTable::makePatchTo (const QueryRoutingTable &other,
                                           quint8 entryBits) const
{
    Q_ASSERT (other.size_ == size_);
    Q_ASSERT (entryBits == 1 || entryBits == 4 || entryBits == 8);

    QByteArray patchBuffer (size_ * entryBits / 8, 0);

    const quint8 *oldTable = reinterpret_cast <const quint8 *>
                                                (rawTable_.data());
    const quint8 *oldTableEnd = oldTable + rawTable_.size();
    const quint8 *newTable = reinterpret_cast <const quint8 *>
                                                (other.rawTable_.data());
    quint8 *patch = reinterpret_cast <quint8 *> (patchBuffer.data());
    quint8 *patchEnd = patch + patchBuffer.size();

    quint8 tmp, set, reset;
    quint8 setMask1, setMask2, resetMask1, resetMask2;
    quint8 *end;
    if (entryBits == 0x01) {
        while (oldTable != oldTableEnd)
            *patch++ = *oldTable++ ^ *newTable++;
    }
    if (entryBits == 0x04) {
        setMask1 = 0xF0; // -1 => infinity(=2) + -1 = 1 => has entry
        resetMask1 = 0x10; // +1 => 1 + 1 = 2(=infinity) => no entry
        setMask2 = 0x0F; // -1 => infinity(=2) + -1 = 1 => has entry
        resetMask2 = 0x01; // +1 => 1 + 1 = 2(=infinity) => no entry
        while (oldTable != oldTableEnd) {
            tmp = *oldTable ^ *newTable;
            set = tmp & *newTable++;
            reset = tmp & *oldTable++;
            for (end = patch + 4; patch < end; patch++) {
                *patch |= (set & 0x80) ? setMask1 : 0x00;
                *patch |= (reset & 0x80) ? resetMask1 :0x00;
                *patch |= (set & 0x40) ? setMask2 : 0x00;
                *patch |= (reset & 0x40) ? resetMask2 :0x00;
                set <<= 2; reset <<= 2;
            }
        }
    }
    if (entryBits == 0x08) {
        setMask1 = 0xFF; // -1 => infinity(=2) + -1 = 1 => has entry
        resetMask1 = 0x01; // +1 => 1 + 1 = 2(=infinity) => no entry
        while (oldTable != oldTableEnd) {
            tmp = *oldTable ^ *newTable;
            set = tmp & *newTable++;
            reset = tmp & *oldTable++;
            for (end = patch + 8; patch < end; patch++) {
                *patch |= (set & 0x80) ? setMask1 : 0x00;
                *patch |= (reset & 0x80) ? resetMask1 :0x00;
                set <<= 1; reset <<= 1;
            }
        }
    }
    Q_ASSERT (patch == patchEnd);
    return patchBuffer;
}

void QueryRoutingTable::scaledCopy (const QueryRoutingTable &other)
{
    Q_ASSERT (size_ > 1 && other.size_ > 1);

    // ei -> Entry Index => current index in current byte
    // ec -> Entry Count => how many entries are grouped together
    quint8 *p1 = reinterpret_cast <quint8 *> (rawTable_.data());
    const quint8 *e1 = p1 + rawTable_.size();
    quint8 ei1 = 0; // Entry index (inside/relative to a byte).
    quint32 ec1 = (size_ > other.size_) ? (size_ / other.size_) : (1);

    const quint8 *p2 = reinterpret_cast <const quint8 *>
                                            (other.rawTable_.data());
    const quint8 *e2 = p2 + other.rawTable_.size();
    quint8 ei2 = 0; // Entry index (inside/relative to a byte).
    quint32 ec2 = (other.size_ > size_) ? (other.size_ / size_) : (1);

    quint32 i;
    quint8 mv; // Minimal value.
    while (p1 < e1 && p2 < e2) {
        // Take the minimal value in the group from source.
        for (mv = 0, i = 0; i < ec2; i++) {
            mv |= (*p2 & EntryMask [ei2]) != 0;
            ++ei2 %= 8;
            if (ei2 == 0) p2++;
        }
        // Set the value to all entries in the destination group.
        for (i = 0; i < ec1; i++) {
            *p1 &= ~EntryMask [ei1];
            *p1 |= mv << ValueShift [ei1];
            ++ei1 %= 8;
            if (ei1 == 0) p1++;
        }
    }
    // Both tables must have been comletely iterated:
    Q_ASSERT (p1 == e1 && p2 == e2);
}

void QueryRoutingTable::addTable (const QueryRoutingTable &other)
{
    Q_ASSERT (size_ > 1 && other.size_ > 1);

    quint8 *p1 = reinterpret_cast <quint8 *> (rawTable_.data());
    const quint8 *e1 = p1 + rawTable_.size();
    const quint8 *p2 = reinterpret_cast <const quint8 *>
                                            (other.rawTable_.data());
    const quint8 *e2 = p2 + other.rawTable_.size();

    if (rawTable_.size() == other.rawTable_.size()) {
        while (p1 != e1)
            *p1++ |= *p2++;
    } else {
        // ei -> Entry Index => current index in current byte
        // ec -> Entry Count => how many entries are grouped together
        quint8 ei1 = 0;
        quint32 ec1 = (size_ > other.size_) ? (size_ / other.size_) : (1);
        quint8 ei2 = 0;
        quint32 ec2 = (other.size_ > size_) ? (other.size_ / size_) : (1);

        quint32 i;
        quint8 mv; // Minimal value.
        while (p1 < e1 && p2 < e2) {
            // Take the minimal value in the group from source.
            for (mv = 0, i = 0; i < ec2; i++) {
                mv |= (*p2 & EntryMask [ei2]) != 0;
                ++ei2 %= 8;
                if (ei2 == 0) p2++;
            }
            // Or the value to all entries in the destination group.
            for (i = 0; i < ec1; i++) {
                *p1 |= mv << ValueShift [ei1];
                ++ei1 %= 8;
                if (ei1 == 0) p1++;
            }
        }
    }
    // Both tables must have been comletely iterated:
    Q_ASSERT (p1 == e1 && p2 == e2);
}

bool QueryRoutingTable::isEntrySet (quint32 index) const
{
    Q_ASSERT (index < size_);

    quint32 byteIndex = index / 8;
    quint32 bitIndex = index % 8;
    quint8 byte = static_cast <quint8> (rawTable_.at (byteIndex));

    return (byte & (0x80 >> bitIndex)) != 0;
}

void QueryRoutingTable::setEntry (quint32 index)
{
    Q_ASSERT (index < size_);

    quint32 byteIndex = index / 8;
    quint32 bitIndex = index % 8;
    quint8 *byte = reinterpret_cast <quint8 *> (rawTable_.data()) + byteIndex;

    *byte |= (0x80 >> bitIndex);
}

void QueryRoutingTable::resetEntry (quint32 index)
{
    Q_ASSERT (index < size_);

    quint32 byteIndex = index / 8;
    quint32 bitIndex = index % 8;
    quint8 *byte = reinterpret_cast <quint8 *> (rawTable_.data()) + byteIndex;

    *byte &= ~(0x80 >> bitIndex);
}

bool QueryRoutingTable::hasString (QString x) const
{
    Q_ASSERT (size_ > 0);
    quint32 index = hash (x,0,x.length(), sizeBits_);
    return isEntrySet (index);
}

void QueryRoutingTable::add (QString x)
{
    Q_ASSERT (size_ > 0);
    quint32 index = hash (x, 0, x.length(), sizeBits_); // % p.tableSize;
    setEntry (index);
}

void QueryRoutingTable::remove (QString x)
{
    Q_ASSERT (size_ > 0);
    quint32 index = hash (x, 0, x.length(), sizeBits_); // % p.tableSize;
    resetEntry (index);
}

int QueryRoutingTable::hash(QString x, int start, int end, quint8 bits) const
{

    //1. First turn x[start...end-1] into a number by treating all 4-byte
    //chunks as a little-endian quadword, and XOR'ing the result together.
    //We pad x with zeroes as needed.
    //    To avoid having do deal with special cases, we do this by XOR'ing
    //a rolling value one byte at a time, taking advantage of the fact that
    //x XOR 0==x.

    int _xor=0;  //the running total
    int j=0;    //the byte position in xor.  INVARIANT: j==(i-start)%4
    for (int i=start; i<end; i++) {
//        int b=Character.toLowerCase(x.charAt(i)) & 0xFF;
        int b = x.at(i).toLower().toAscii() & 0xFF;
        b=b<<(j*8);
        _xor=_xor^b;
        j=(j+1)%4;
    }
    //2. Now map number to range 0 - (2^bits-1).
    return hashFast(_xor, bits);
//    return xor % (0x00000001 << (bits-1));
}

int QueryRoutingTable::hashFast(int x, quint8 bits) const
{
    //Multiplication-based hash function.  See Chapter 12.3.2. of CLR.
    quint64 prod = static_cast <quint64> (x) * static_cast <quint64> (A_INT);
    quint64 ret = prod << 32;
    ret = ret >> (32 + (32 - bits));
    return static_cast <int> (ret);
}

Copyright © 2006 Peter Dimov.
Powered by Doxygen.