00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033 #include "MaceKey.h"
00034 #include "KeyRange.h"
00035 #include "Util.h"
00036 #include "SockUtil.h"
00037 #include "params.h"
00038 #include "Log.h"
00039 #include "mace-macros.h"
00040
00041 namespace mace {
00042 bool SockAddr::isNull() const {
00043 return *this == SockUtil::NULL_MSOCKADDR;
00044 }
00045
00046 void SockAddr::print(std::ostream& out) const {
00047 Util::printAddrString(out, *this);
00048 }
00049
00050 void SockAddr::print(PrintNode& pr, const std::string& name) const {
00051 pr.addChild(PrintNode(name, "SockAddr", toString()));
00052 }
00053
00054 void MaceAddr::print(std::ostream& out) const {
00055 Util::printAddrString(out, *this);
00056 }
00057
00058 void MaceAddr::print(PrintNode& pr, const std::string& name) const {
00059 pr.addChild(PrintNode(name, "MaceAddr", toString()));
00060 }
00061
00062 bool MaceAddr::isNull() const {
00063 return *this == SockUtil::NULL_MACEADDR;
00064 }
00065
00066 MaceKey::ipv4_MaceKey::ipv4_MaceKey(uint32_t ipaddr, uint16_t port,
00067 uint32_t proxyIp, uint16_t proxyPort) {
00068 addr.local.addr = ipaddr;
00069 if (port) {
00070 addr.local.port = port;
00071 }
00072 else {
00073 addr.local.port = Util::getPort();
00074 }
00075 if(proxyIp == INADDR_NONE) {
00076 addr.proxy = SockUtil::NULL_MSOCKADDR;
00077 } else {
00078 addr.proxy.addr = proxyIp;
00079 addr.proxy.port = proxyPort;
00080 if (proxyPort == 0) {
00081 addr.proxy.port = Util::getPort();
00082 }
00083 }
00084 }
00085
00086 void MaceKey::ipv4_MaceKey::serializeXML_RPC(std::string& str) const throw(SerializationException){
00087 ASSERT(str.empty());
00088 str = Util::getAddrString(addr);
00089 }
00090
00091 int MaceKey::ipv4_MaceKey::deserializeXML_RPC(std::istream& in) throw(SerializationException) {
00092 mace::string s;
00093 in >> s;
00094 ASSERT(in.eof());
00095 addr = Util::getMaceAddr(s);
00096 return s.size();
00097 }
00098
00099 std::string MaceKey::ipv4_MaceKey::addressString() const {
00100 return Util::getAddrString(addr, false);
00101 }
00102
00103 void MaceKey::ipv4_MaceKey::print(std::ostream& out) const {
00104 Util::printAddrString(out, addr);
00105 }
00106
00107 MaceKey::ipv4_MaceKey::ipv4_MaceKey(const std::string& address) { addr = Util::getMaceAddr(address); }
00108
00109 bool MaceKey::getHostnameOnly() {
00110 static bool hostnameOnly = (params::containsKey(params::MACE_PRINT_HOSTNAME_ONLY) && params::get<int>(params::MACE_PRINT_HOSTNAME_ONLY));
00111 return hostnameOnly;
00112 }
00113
00125 MaceKeyDiff operator-(const MaceKey& to, const MaceKey& from) throw(InvalidMaceKeyException)
00126 {
00127 if(from.isNullAddress() || to.isNullAddress()) { throw(InvalidMaceKeyException("arc_distance not valid on null mace keys")); }
00128 if(!from.isBitArrMaceKey() || !to.isBitArrMaceKey()) { throw(InvalidMaceKeyException("arc_distance not valid on non-bitarr mace keys")); }
00129 if(from.bitLength() != to.bitLength()) { throw(InvalidMaceKeyException("bit lengths must be the same when computing distance")); }
00130 if (from==to)
00131 return MaceKeyDiff();
00132
00133 if(from.bitLength() % 8*sizeof(uint32_t)) {
00134 ABORT("Exception: MaceKeyDiff presently only supports bit arrays which are divisible in length by 32 bits");
00135 }
00136
00137 int ints = from.bitLength() / (8*sizeof(uint32_t));
00138 uint32_t* data = new uint32_t[ints];
00139 memset(data, 0, ints*sizeof(uint32_t));
00140
00141 for(int i = 0; i < ints; i++) {
00142 uint32_t a = to.getNthDigit(i,32);
00143 uint32_t b = from.getNthDigit(i,32);
00144 if( a >= b ) {
00145 data[i] = a - b;
00146 } else {
00147 int j = i;
00148 do { data[j]--; } while(data[j--] == UINT_MAX && j>=0);
00149 data[i] = a - b;
00150 }
00151 }
00152 return MaceKeyDiff(MaceKeyDiff::___UNSIGNED, ints, data);
00153 }
00154 MaceKeyDiff MaceKeyDiff::operator-(const MaceKeyDiff& from) const
00155 {
00156 ADD_FUNC_SELECTORS;
00157 if (*this==from)
00158 return MaceKeyDiff();
00159
00160 if(type == _INFINITY) { return *this; }
00161 if(type == _NEG_INFINITY) { return *this; }
00162 if(from.type == _INFINITY) { return NEG_INF; }
00163 if(from.type == _NEG_INFINITY) { return INF; }
00164 if(from.type == ZERO) { return *this; }
00165 if(size != from.size && type != ZERO) {
00166 ABORT("Mismatched sizes of MaceKeyDiff. Returning 0");
00167 return MaceKeyDiff();
00168 }
00169
00170
00171
00172
00173
00174 uint32_t* diffdata = new uint32_t[from.size];
00175 memset(diffdata, 0, from.size*sizeof(uint32_t));
00176
00177 for(int i = 0; i < from.size; i++) {
00178 uint32_t a = (type == ZERO ? 0 : data[i]);
00179 uint32_t b = from.data[i];
00180
00181 if( a >= b ) {
00182 diffdata[i] = a - b;
00183 } else {
00184 int j = i;
00185 do { diffdata[j]--; } while(diffdata[j--] == UINT_MAX && j>=0);
00186 diffdata[i] = a - b;
00187 }
00188 }
00189
00190 return MaceKeyDiff((type==ZERO?___SIGNED:type), from.size, diffdata);
00191 }
00192 MaceKeyDiff MaceKeyDiff::operator+(const MaceKeyDiff& from) const
00193 {
00194 ADD_FUNC_SELECTORS;
00195 if(type == _INFINITY) { return *this; }
00196 if(type == _NEG_INFINITY) { return *this; }
00197 if(from.type == _INFINITY) { return INF; }
00198 if(from.type == _NEG_INFINITY) { return NEG_INF; }
00199 if(from.type == ZERO) { return *this; }
00200 if(type == ZERO) { return from; }
00201 if(size != from.size) {
00202 ABORT("Mismatched sizes of MaceKeyDiff. Returning 0");
00203 return MaceKeyDiff();
00204 }
00205
00206
00207
00208 uint32_t* adddata = new uint32_t[size];
00209 memset(adddata, 0, size*sizeof(uint32_t));
00210
00211 int carry = 0;
00212 for(int i = size-1; i >= 0; i--) {
00213 adddata[i] = from.data[i]+data[i]+carry;
00214 if(from.data[i] > UINT_MAX-data[i] || (carry == 1 && (data[i] + from.data[i] == UINT_MAX))) {
00215 carry = 1;
00216 } else {
00217 carry = 0;
00218 }
00219 }
00220 return MaceKeyDiff(type, size, adddata);
00221 }
00222 MaceKeyDiff MaceKeyDiff::operator+(uint32_t from) const
00223 {
00224 if(type == _INFINITY) { return *this; }
00225 if(type == _NEG_INFINITY) { return *this; }
00226 if(from == 0) { return *this; }
00227 if(type == ZERO) { ABORT("Exception: ERROR -- don't know how to set 'size' adding ZERO to an int. Report if this occurs"); }
00228
00229 if(size == 0) { return *this; }
00230
00231
00232
00233 uint32_t* adddata = new uint32_t[size];
00234 memcpy(adddata, data, size*sizeof(uint32_t));
00235 adddata[size-1] += from;
00236
00237 if(data[size-1] > UINT_MAX - from) {
00238 int j = size-2;
00239 do { data[j]++; } while(data[j--]==0 && j>=0);
00240 }
00241 return MaceKeyDiff(type, size, adddata);
00242 }
00243 MaceKeyDiff MaceKeyDiff::operator-(uint32_t from) const
00244 {
00245 if(type == _INFINITY) { return *this; }
00246 if(type == _NEG_INFINITY) { return *this; }
00247 if(from == 0) { return *this; }
00248 if(type == ZERO) { ABORT("Exception: ERROR -- don't know how to set 'size' adding ZERO to an int. Report if this occurs"); }
00249
00250 if(size == 0) { return *this; }
00251
00252
00253
00254 uint32_t* adddata = new uint32_t[size];
00255 memcpy(adddata, data, size*sizeof(uint32_t));
00256 adddata[size-1] -= from;
00257
00258 if(data[size-1] < from) {
00259 int j = size-2;
00260 do { data[j]--; } while(data[j--] == UINT_MAX && j>=0);
00261 }
00262 return MaceKeyDiff(type, size, adddata);
00263 }
00264 MaceKeyDiff& MaceKeyDiff::operator=(const MaceKeyDiff& d)
00265 {
00266 if(this == &d) { return *this; }
00267 this->type = d.type;
00268 this->size = d.size;
00269 if(this->size > 0) {
00270 delete[] data;
00271 this->data = new uint32_t[this->size];
00272 memcpy(this->data, d.data, d.size*sizeof(uint32_t));
00273 } else {
00274 delete[] data;
00275 this->data = NULL;
00276 }
00277 return *this;
00278 }
00279 MaceKeyDiff::MaceKeyDiff(const MaceKeyDiff& d) : type(d.type), size(d.size), data(NULL)
00280 {
00281 if(this->size > 0) {
00282 this->data = new uint32_t[this->size];
00283 memcpy(this->data, d.data, d.size*sizeof(uint32_t));
00284 }
00285 }
00286 int MaceKeyDiff::sign()
00287 {
00288 if(type == ZERO) { return 0; }
00289 if(type == _INFINITY) { return 1; }
00290 if(type == _NEG_INFINITY) { return -1; }
00291
00292 int i;
00293 for(i = 0; i < size && !data[i]; i++);
00294 if(i == size) { return 0; }
00295 if(type == ___UNSIGNED) { return 1; }
00296 if((int)data[0] < 0) { return -1; }
00297 return 1;
00298 }
00299 MaceKeyDiff& MaceKeyDiff::abs()
00300 {
00301 switch(type) {
00302 case ZERO:
00303 case _INFINITY:
00304 case ___UNSIGNED: break;
00305 case _NEG_INFINITY: type=_INFINITY; break;
00306 case ___SIGNED: {
00307 if(sign() >= 0) { break; }
00308 for(int i = 0; i < size; i++) {
00309 data[i] = ~data[i];
00310 }
00311 int j = size-1;
00312 do { data[j]++; } while(data[j--]==0 && j>=0);
00313 }
00314 }
00315 return *this;
00316 }
00317 bool MaceKeyDiff::operator==(const MaceKeyDiff& right) const
00318 {
00319
00320 if(right.type == _INFINITY) { return false; }
00321 if(type == _NEG_INFINITY) { return false; }
00322 if(type == _INFINITY) { return false; }
00323 if(right.type == _NEG_INFINITY) { return false; }
00324
00325 if(type == ZERO || right.type == ZERO) { return type == right.type; }
00326 if(size != right.size) { return false; }
00327
00328 for(int i=0; i<size; i++) {
00329 if(data[i] != right.data[i]) {
00330 return false;
00331 }
00332 }
00333 return true;
00334 }
00335 bool MaceKeyDiff::operator<(const MaceKeyDiff& right) const
00336 {
00337 if(right.type == _INFINITY) { return true; }
00338 if(type == _NEG_INFINITY) { return true; }
00339 if(type == _INFINITY) { return false; }
00340 if(right.type == _NEG_INFINITY) { return false; }
00341 if(type == ___UNSIGNED && right.type == ___UNSIGNED) {
00342 for(int i=0; i < size; i++) {
00343 if(data[i] < right.data[i]) { return true; }
00344 else if(data[i] > right.data[i]) { return false; }
00345 }
00346 return false;
00347 }
00348 MaceKeyDiff diff = *this - right;
00349 diff.toSigned();
00350
00351 return diff.sign() < 0;
00352 }
00353 bool MaceKeyDiff::operator<=(const MaceKeyDiff& right) const
00354 {
00355 if(right.type == _INFINITY) { return true; }
00356 if(type == _NEG_INFINITY) { return true; }
00357 if(type == _INFINITY) { return false; }
00358 if(right.type == _NEG_INFINITY) { return false; }
00359 if(type == ___UNSIGNED && right.type == ___UNSIGNED) {
00360 for(int i=0; i < size; i++) {
00361 if(data[i] < right.data[i]) { return true; }
00362 else if(data[i] > right.data[i]) { return false; }
00363 }
00364 return true;
00365 }
00366 MaceKeyDiff diff = *this - right;
00367
00368 return diff.toSigned().sign() <= 0;
00369 }
00370 MaceKeyDiff MaceKeyDiff::operator>>(int bits) const
00371 {
00372 uint32_t* adddata = new uint32_t[size];
00373 memcpy(adddata, data, size*sizeof(uint32_t));
00374 while(bits > 0) {
00375 for(int i=size-1; i>0; i--) {
00376 int shift = adddata[i-1]%2;
00377 shift = shift << (8*sizeof(uint32_t)-1);
00378 adddata[i] = adddata[i] >> 1;
00379 adddata[i] += shift;
00380 }
00381 if(size > 0) {
00382 adddata[0] = adddata[0]>>1;
00383 }
00384 bits--;
00385 }
00386 return MaceKeyDiff(type, size, adddata);
00387 }
00388 MaceKey operator-(const MaceKey& to, const MaceKeyDiff& from) throw(InvalidMaceKeyException)
00389 {
00390 if(!to.isBitArrMaceKey()) { throw(InvalidMaceKeyException("Diff subtraction only valid on BitArr MaceKeys")); }
00391 if(from.type == MaceKeyDiff::_NEG_INFINITY || from.type == MaceKeyDiff::_INFINITY) {
00392 throw(InvalidMaceKeyException("Cannot add inf or -inf to a mace key"));
00393 }
00394 if(from.type == MaceKeyDiff::ZERO) { return to; }
00395
00396 if(to.bitLength() != (int)(from.size*8*sizeof(uint32_t))) {
00397 throw(InvalidMaceKeyException("Cannot add diff to mace key of different size"));
00398 }
00399
00400
00401 uint32_t* diffdata = new uint32_t[from.size];
00402 memset(diffdata, 0, from.size*sizeof(uint32_t));
00403
00404 for(int i = 0; i < from.size; i++) {
00405 uint32_t a = to.getNthDigit(i,32);
00406 uint32_t b = from.data[i];
00407 if( a >= b ) {
00408 diffdata[i] = a - b;
00409 } else {
00410 int j = i;
00411 do { diffdata[j]--; } while(diffdata[j--] == UINT_MAX && j>=0);
00412 diffdata[i] = a - b;
00413 }
00414 }
00415 switch(to.addressFamily()) {
00416 case SHA32: { MaceKey m(sha32, diffdata); delete[] diffdata; return m; }
00417 case SHA160: { MaceKey m(sha160, diffdata); delete[] diffdata; return m; }
00418 default: ABORT("Exception: need to update MaceKey operators to handle new address families");
00419 }
00420 }
00421 MaceKey operator+(const MaceKey& from, const MaceKeyDiff& to) throw(InvalidMaceKeyException)
00422 {
00423 if(!from.isBitArrMaceKey()) { throw(InvalidMaceKeyException("Diff addition only valid on BitArr MaceKeys")); }
00424 if(to.type == MaceKeyDiff::_NEG_INFINITY || to.type == MaceKeyDiff::_INFINITY) {
00425 throw(InvalidMaceKeyException("Cannot add inf or -inf to a mace key"));
00426 }
00427 if(to.type == MaceKeyDiff::ZERO) { return from; }
00428
00429 if(from.bitLength() != (int)(to.size*8*sizeof(uint32_t))) {
00430 throw(InvalidMaceKeyException("Cannot add diff to mace key of different size"));
00431 }
00432
00433
00434 uint32_t* adddata = new uint32_t[to.size];
00435
00436 int carry = 0;
00437 for(int i = to.size-1; i >= 0; i--) {
00438 adddata[i] = from.getNthDigit(i,32)+to.data[i]+carry;
00439 if(to.data[i] > UINT_MAX-from.getNthDigit(i,32) || (carry == 1 && (from.getNthDigit(i,32) + to.data[i] == UINT_MAX))) {
00440 carry = 1;
00441 } else {
00442 carry = 0;
00443 }
00444 }
00445 switch(from.addressFamily()) {
00446 case SHA32: { MaceKey m(sha32, adddata); delete[] adddata; return m; }
00447 case SHA160: { MaceKey m(sha160, adddata); delete[] adddata; return m; }
00448 default: ABORT("Exception: need to update MaceKey operators to handle new address families");
00449 }
00450 }
00451 MaceKey operator+(const MaceKey& from, uint32_t to) throw(InvalidMaceKeyException)
00452 {
00453 if(!from.isBitArrMaceKey()) { throw(InvalidMaceKeyException("uint32_t addition only valid on BitArr MaceKeys")); }
00454 if(to == 0) { return from; }
00455
00456
00457 int size = from.bitLength()/32;
00458 ASSERT(size > 0);
00459 uint32_t* adddata = new uint32_t[size];
00460 for(int i=0; i<size; i++) {
00461 adddata[i] = from.getNthDigit(i, 32);
00462 }
00463 adddata[size-1] += to;
00464 if(from.getNthDigit(size-1,32) > UINT_MAX - to) {
00465 int j = size-2;
00466 do { adddata[j]++; } while(adddata[j--]==0 && j>=0);
00467 }
00468
00469 switch(from.addressFamily()) {
00470 case SHA32: { MaceKey m(sha32, adddata); delete[] adddata; return m; }
00471 case SHA160: { MaceKey m(sha160, adddata); delete[] adddata; return m; }
00472 default: ABORT("Exception: need to update MaceKey operators to handle new address families");
00473 }
00474 }
00475 MaceKey operator-(const MaceKey& from, uint32_t to) throw(InvalidMaceKeyException)
00476 {
00477 if(!from.isBitArrMaceKey()) { throw(InvalidMaceKeyException("uint32_t addition only valid on BitArr MaceKeys")); }
00478 if(to == 0) { return from; }
00479
00480
00481 int size = from.bitLength()/32;
00482 uint32_t* diffdata = new uint32_t[size];
00483 for(int i=0; i<size; i++) {
00484 diffdata[i] = from.getNthDigit(i, 32);
00485 }
00486 diffdata[size-1] -= to;
00487
00488 if(from.getNthDigit(size-1,32) < to) {
00489 int j = size-2;
00490 do { diffdata[j]--; } while(diffdata[j--] == UINT_MAX && j>=0);
00491 }
00492 switch(from.addressFamily()) {
00493 case SHA32: { MaceKey m(sha32, diffdata); delete[] diffdata; return m; }
00494 case SHA160: { MaceKey m(sha160, diffdata); delete[] diffdata; return m; }
00495 default: ABORT("Exception: need to update MaceKey operators to handle new address families");
00496 }
00497 }
00498 void MaceKeyDiff::print(std::ostream& out) const {
00499 switch(type) {
00500 case ZERO: out << "ZERO"; return;
00501 case _INFINITY: out << "INF"; return;
00502 case _NEG_INFINITY: out << "-INF"; return;
00503 case ___SIGNED: out << "(signed)"; break;
00504 case ___UNSIGNED: out << "(unsigned)"; break;
00505 }
00506 std::ios::fmtflags f(out.flags());
00507 out << std::hex << std::setfill('0');
00508 for(int i = 0; i < size; i++) {
00509 out << std::setw(8) << data[i];
00510 }
00511 out.flags(f);
00512 }
00513 }
00514
00515 mace::MaceKeyDiff mace::MaceKeyDiff::NEG_INF = mace::MaceKeyDiff(_NEG_INFINITY);
00516 mace::MaceKeyDiff mace::MaceKeyDiff::INF = mace::MaceKeyDiff(_INFINITY);
00517 const mace::MaceKey mace::MaceKey::null = mace::MaceKey();
00518 const mace::KeyRange mace::KeyRange::null = mace::KeyRange();