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
00034
00035
00036
00037
00038
00039 #include "Identifier.h"
00040 #include "ariba/utility/misc/sha1.h"
00041
00042 namespace ariba {
00043 namespace utility {
00044
00045 uint Identifier::keyLength = MAX_KEYLENGTH;
00046
00047 uint Identifier::aSize = Identifier::keyLength / (8 * sizeof(mp_limb_t))
00048 + (Identifier::keyLength % (8 * sizeof(mp_limb_t)) != 0 ? 1 : 0);
00049
00050 mp_limb_t Identifier::GMP_MSB_MASK = (Identifier::keyLength % GMP_LIMB_BITS)
00051 != 0 ? (((mp_limb_t) 1 << (Identifier::keyLength % GMP_LIMB_BITS)) - 1)
00052 : (mp_limb_t) -1;
00053
00054
00055 vsznDefault(Identifier);
00056 use_logging_cpp( Identifier );
00057
00058
00059
00060
00061
00062
00063 const Identifier Identifier::UNSPECIFIED_KEY;
00064 const Identifier Identifier::ZERO((uint32_t) 0);
00065 const Identifier Identifier::ONE((uint32_t) 1);
00066
00067
00068 const char* HEX = "0123456789abcdef";
00069 gmp_randstate_t randstate;
00070
00071 void Identifier::clearAddress() {
00072 for (size_t i = 0; i < array_size; i++)
00073 key[i] = 0;
00074 isUnspec = false;
00075 trim();
00076 }
00077
00078 bool Identifier::setAddress(string address) {
00079 return false;
00080 }
00081
00082 string Identifier::getAddress() const {
00083 return toString();
00084 }
00085
00086
00087
00088
00089
00090
00091 Identifier::Identifier() {
00092 seed();
00093 isUnspec = true;
00094 trim();
00095 }
00096
00097
00098 Identifier::Identifier(uint32_t num) {
00099 seed();
00100 clearAddress();
00101 key[0] = (uint32_t) num;
00102 trim();
00103 }
00104
00105
00106 Identifier::Identifier(const unsigned char* buf, uint size) {
00107 seed();
00108 int trimSize, offset;
00109 clearAddress();
00110 trimSize = (int) std::min((uint) (aSize * sizeof(mp_limb_t)), size);
00111 offset = aSize * sizeof(mp_limb_t) - trimSize;
00112 memcpy(((char*) key) + offset, buf, trimSize);
00113 trim();
00114 }
00115
00116
00117 Identifier::Identifier(const std::string& str, uint base) {
00118 seed();
00119
00120 if ((base < 2) || (base > 16)) {
00121 logging_error( "Identifier::Identifier(): Invalid base!" );
00122 return;
00123 }
00124
00125 string s(str);
00126 clearAddress();
00127
00128 for (uint i = 0; i < s.size(); i++) {
00129 if ((s[i] >= '0') && (s[i] <= '9')) {
00130 s[i] -= '0';
00131 } else if ((s[i] >= 'a') && (s[i] <= 'f')) {
00132 s[i] -= ('a' - 10);
00133 } else if ((s[i] >= 'A') & (s[i] <= 'F')) {
00134 s[i] -= ('A' - 10);
00135 } else {
00136 logging_error( "Identifier::Identifier(): "
00137 "Invalid character in string!" );
00138 return;
00139 }
00140 }
00141
00142 mpn_set_str((mp_limb_t*) this->key, (const unsigned char*) s.c_str(),
00143 str.size(), base);
00144 trim();
00145 }
00146
00147
00148 Identifier::Identifier(const Identifier& rhs) {
00149 seed();
00150 (*this) = rhs;
00151 }
00152
00153
00154 Identifier::~Identifier() {
00155 }
00156
00157 void Identifier::seed(){
00158 static bool isSeeded = false;
00159 if( isSeeded ) return;
00160
00161 gmp_randinit_default( randstate );
00162 gmp_randseed_ui( randstate, time(NULL) );
00163
00164 isSeeded = true;
00165 }
00166
00167
00168
00169
00170
00171 void Identifier::setKeyLength(uint length) {
00172 if ((length < 1) || (length > Identifier::keyLength)) {
00173
00174 logging_error( "Identifier::setKeyLength(): length must be <= " <<
00175 MAX_KEYLENGTH << " and setKeyLength() must not be " <<
00176 "called twice with different length!" );
00177 return;
00178 }
00179
00180 keyLength = length;
00181
00182 aSize = keyLength / (8 * sizeof(mp_limb_t)) + (keyLength % (8
00183 * sizeof(mp_limb_t)) != 0 ? 1 : 0);
00184
00185 GMP_MSB_MASK = (keyLength % GMP_LIMB_BITS) != 0 ? (((mp_limb_t) 1
00186 << (keyLength % GMP_LIMB_BITS)) - 1) : (mp_limb_t) -1;
00187 }
00188
00189
00190 uint Identifier::getLength() {
00191 return Identifier::keyLength;
00192 }
00193
00194 bool Identifier::isUnspecified() const {
00195 return isUnspec;
00196 }
00197
00198 std::string Identifier::toString(uint base) const {
00199 if ((base < 2) || (base > 16)) {
00200 logging_error( "Identifier::Identifier(): Invalid base!" );
00201 return "";
00202 }
00203
00204 if (isUnspec) return std::string("<unspec>");
00205
00206 char temp[250];
00207 if (base == 16) {
00208 int k = 0;
00209 for (int i = (keyLength - 1) / 4; i >= 0; i--, k++) {
00210 temp[k] = HEX[this->get(4 * i, 4)];
00211 }
00212 temp[k] = 0;
00213 return std::string((const char*) temp);
00214 } else if (base == 2) {
00215 int k = 0;
00216 for (int i = MAX_KEYLENGTH - 1; i >= 0; i -= 1, k++)
00217 temp[k] = HEX[this->get(i, 1)];
00218 temp[k] = 0;
00219 return std::string((const char*) temp);
00220 }
00221
00222 #if 0
00223 size_t log2[33] = {0};
00224 log2[2] = 1;
00225 log2[4] = 2;
00226 log2[8] = 3;
00227 log2[16] = 4;
00228 log2[32] = 5;
00229 size_t sh = (sizeof(mp_limb_t)*8/log2[base]);
00230
00231 mp_size_t last = mpn_get_str((unsigned char*) temp, base,
00232 (mp_limb_t*) this->key, aSize+1);
00233 for (int i = 0; i < last-sh; i++) {
00234 temp[i] = HEX[temp[i+sh]];
00235 }
00236 temp[last-sh] = 0;
00237 return std::string((const char*) temp);
00238 }
00239 #endif
00240 return "<not supported>";
00241 }
00242
00243
00244
00245
00246
00247
00248 Identifier& Identifier::operator=(const Identifier& rhs) {
00249 isUnspec = rhs.isUnspec;
00250 memcpy(key, rhs.key, aSize * sizeof(mp_limb_t));
00251 return *this;
00252 }
00253
00254
00255 Identifier& Identifier::operator--() {
00256 return (*this -= ONE);
00257 }
00258
00259
00260 Identifier Identifier::operator--(int) {
00261 Identifier clone = *this;
00262 *this -= ONE;
00263 return clone;
00264 }
00265
00266
00267 Identifier& Identifier::operator++() {
00268 return (*this += ONE);
00269 }
00270
00271
00272 Identifier Identifier::operator++(int) {
00273 Identifier clone = *this;
00274 *this += ONE;
00275 return clone;
00276 }
00277
00278
00279 Identifier& Identifier::operator+=(const Identifier& rhs) {
00280 mpn_add_n((mp_limb_t*) key, (mp_limb_t*) key, (mp_limb_t*) rhs.key, aSize);
00281 trim();
00282 isUnspec = false;
00283 return *this;
00284 }
00285
00286
00287 Identifier& Identifier::operator-=(const Identifier& rhs) {
00288 mpn_sub_n((mp_limb_t*) key, (mp_limb_t*) key, (mp_limb_t*) rhs.key, aSize);
00289 trim();
00290 isUnspec = false;
00291 return *this;
00292 }
00293
00294
00295 Identifier Identifier::operator+(const Identifier& rhs) const {
00296 Identifier result = *this;
00297 result += rhs;
00298 return result;
00299 }
00300
00301
00302 Identifier Identifier::operator-(const Identifier& rhs) const {
00303 Identifier result = *this;
00304 result -= rhs;
00305 return result;
00306 }
00307
00308
00309 bool Identifier::operator<(const Identifier& compKey) const {
00310 return compareTo(compKey) < 0;
00311 }
00312 bool Identifier::operator>(const Identifier& compKey) const {
00313 return compareTo(compKey) > 0;
00314 }
00315 bool Identifier::operator<=(const Identifier& compKey) const {
00316 return compareTo(compKey) <= 0;
00317 }
00318 bool Identifier::operator>=(const Identifier& compKey) const {
00319 return compareTo(compKey) >= 0;
00320 }
00321 bool Identifier::operator==(const Identifier& compKey) const {
00322
00323 if( this->isUnspecified() && compKey.isUnspecified() )
00324 return true;
00325 else
00326 return compareTo(compKey) == 0;
00327 }
00328 bool Identifier::operator!=(const Identifier& compKey) const {
00329 return compareTo(compKey) != 0;
00330 }
00331
00332
00333 Identifier Identifier::operator^(const Identifier& rhs) const {
00334 Identifier result = *this;
00335 for (uint i = 0; i < aSize; i++) {
00336 result.key[i] ^= rhs.key[i];
00337 }
00338
00339 return result;
00340 }
00341
00342
00343 Identifier Identifier::operator|(const Identifier& rhs) const {
00344 Identifier result = *this;
00345 for (uint i = 0; i < aSize; i++) {
00346 result.key[i] |= rhs.key[i];
00347 }
00348
00349 return result;
00350 }
00351
00352
00353 Identifier Identifier::operator&(const Identifier& rhs) const {
00354 Identifier result = *this;
00355 for (uint i = 0; i < aSize; i++) {
00356 result.key[i] &= rhs.key[i];
00357 }
00358
00359 return result;
00360 }
00361
00362
00363 Identifier Identifier::operator~() const {
00364 Identifier result = *this;
00365 for (uint i = 0; i < aSize; i++) {
00366 result.key[i] = ~key[i];
00367 }
00368 result.trim();
00369
00370 return result;
00371 }
00372
00373
00374 Identifier Identifier::operator>>(uint num) const {
00375 Identifier result = ZERO;
00376 int i = num / GMP_LIMB_BITS;
00377
00378 num %= GMP_LIMB_BITS;
00379
00380 if (i >= (int) aSize) return result;
00381
00382 for (int j = 0; j < (int) aSize - i; j++) {
00383 result.key[j] = key[j + i];
00384 }
00385 mpn_rshift(result.key, result.key, aSize, num);
00386 result.isUnspec = false;
00387 result.trim();
00388
00389 return result;
00390 }
00391
00392
00393 Identifier Identifier::operator<<(uint num) const {
00394 Identifier result = ZERO;
00395 int i = num / GMP_LIMB_BITS;
00396
00397 num %= GMP_LIMB_BITS;
00398
00399 if (i >= (int) aSize) return result;
00400
00401 for (int j = 0; j < (int) aSize - i; j++) {
00402 result.key[j + i] = key[j];
00403 }
00404 mpn_lshift(result.key, result.key, aSize, num);
00405 result.isUnspec = false;
00406 result.trim();
00407
00408 return result;
00409 }
00410
00411
00412 IdentifierBit Identifier::operator[](uint n) {
00413 return IdentifierBit(get(n, 1), n, this);
00414 }
00415
00416 Identifier& Identifier::setBitAt(uint pos, bool value) {
00417 mp_limb_t digit = 1;
00418 digit = digit << (pos % GMP_LIMB_BITS);
00419
00420 if (value) {
00421 key[pos / GMP_LIMB_BITS] |= digit;
00422 } else {
00423
00424 key[pos / GMP_LIMB_BITS] &= ~digit;
00425 }
00426
00427 return *this;
00428 }
00429 ;
00430
00431
00432
00433
00434
00435
00436 uint32_t Identifier::get(uint p, uint n) const {
00437 int i = p / GMP_LIMB_BITS,
00438 f = p % GMP_LIMB_BITS,
00439 f2 = f + n - GMP_LIMB_BITS;
00440
00441 if (p + n > Identifier::keyLength) {
00442 logging_error( "Identifier::get: Invalid range (index too large!)" );
00443 return 0;
00444 }
00445
00446 return ((key[i] >> f) |
00447 (f2 > 0 ? (key[i + 1] << (GMP_LIMB_BITS - f)) : 0)) &
00448 (((uint32_t) (~0)) >> (GMP_LIMB_BITS - n));
00449 }
00450
00451
00452 Identifier Identifier::randomSuffix(uint pos) const {
00453 Identifier newKey = *this;
00454 int i = pos / GMP_LIMB_BITS, j = pos % GMP_LIMB_BITS;
00455 mp_limb_t m = ((mp_limb_t) 1 << j) - 1;
00456 mp_limb_t rnd;
00457
00458 mpn_random(&rnd, 1);
00459 newKey.key[i] &= ~m;
00460 newKey.key[i] |= (rnd & m);
00461 mpn_random(newKey.key, i);
00462 newKey.trim();
00463
00464 return newKey;
00465 }
00466
00467
00468 Identifier Identifier::randomPrefix(uint pos) const {
00469 Identifier newKey = *this;
00470 int i = pos / GMP_LIMB_BITS, j = pos % GMP_LIMB_BITS;
00471 mp_limb_t m = ((mp_limb_t) 1 << j) - 1;
00472 mp_limb_t rnd;
00473
00474 mpn_random(&rnd, 1);
00475
00476 newKey.key[i] &= m;
00477 newKey.key[i] |= (rnd & ~m);
00478 for (int k = aSize - 1; k != i; k--) {
00479 mpn_random(&newKey.key[k], 1);
00480 }
00481 newKey.trim();
00482
00483 return newKey;
00484 }
00485
00486
00487 uint Identifier::sharedPrefixLength(const Identifier& compKey) const {
00488 if (compareTo(compKey) == 0) return keyLength;
00489
00490 uint length = 0;
00491 int i;
00492 uint j;
00493 bool msb = true;
00494
00495
00496 for (i = aSize - 1; i >= 0; --i) {
00497 if (this->key[i] != compKey.key[i]) {
00498
00499 mp_limb_t d = this->key[i] ^ compKey.key[i];
00500 if (msb) d <<= (GMP_LIMB_BITS - (keyLength % GMP_LIMB_BITS));
00501 for (j = GMP_LIMB_BITS - 1; d >>= 1; --j)
00502 ;
00503 length += j;
00504 break;
00505 }
00506 length += GMP_LIMB_BITS;
00507 msb = false;
00508 }
00509
00510 return length;
00511 }
00512
00513
00514 int Identifier::log_2() const {
00515 int16_t i = aSize - 1;
00516
00517 while (i >= 0 && key[i] == 0) {
00518 i--;
00519 }
00520
00521 if (i < 0) {
00522 return -1;
00523 }
00524
00525 mp_limb_t j = key[i];
00526 i *= GMP_LIMB_BITS;
00527 while (j != 0) {
00528 j >>= 1;
00529 i++;
00530 }
00531
00532 return i - 1;
00533 }
00534
00535
00536 size_t Identifier::hash() const {
00537 return (size_t) key[0];
00538 }
00539
00540
00541 bool Identifier::isBetween(const Identifier& keyA, const Identifier& keyB) const {
00542 if (isUnspec || keyA.isUnspec || keyB.isUnspec) return false;
00543
00544 if (*this == keyA) return false;
00545 else if (keyA < keyB) return ((*this > keyA) && (*this < keyB));
00546 else return ((*this > keyA) || (*this < keyB));
00547 }
00548
00549
00550 bool Identifier::isBetweenR(const Identifier& keyA, const Identifier& keyB) const {
00551 if (isUnspec || keyA.isUnspec || keyB.isUnspec) return false;
00552
00553 if ((keyA == keyB) && (*this == keyA)) return true;
00554 else if (keyA <= keyB) return ((*this > keyA) && (*this <= keyB));
00555 else return ((*this > keyA) || (*this <= keyB));
00556 }
00557
00558
00559 bool Identifier::isBetweenL(const Identifier& keyA, const Identifier& keyB) const {
00560 if (isUnspec || keyA.isUnspec || keyB.isUnspec) return false;
00561
00562 if ((keyA == keyB) && (*this == keyA)) return true;
00563 else if (keyA <= keyB) return ((*this >= keyA) && (*this < keyB));
00564 else return ((*this >= keyA) || (*this < keyB));
00565 }
00566
00567
00568 bool Identifier::isBetweenLR(const Identifier& keyA, const Identifier& keyB) const {
00569 if (isUnspec || keyA.isUnspec || keyB.isUnspec) return false;
00570
00571 if ((keyA == keyB) && (*this == keyA)) return true;
00572 else if (keyA <= keyB) return ((*this >= keyA) && (*this <= keyB));
00573 else return ((*this >= keyA) || (*this <= keyB));
00574 }
00575
00576
00577
00578
00579
00580
00581 std::ostream& operator<<(std::ostream& os, const Identifier& c) {
00582 os << c.toString(16);
00583 return os;
00584 }
00585 ;
00586
00587
00588 Identifier Identifier::max() {
00589 Identifier newKey;
00590
00591 for (uint i = 0; i < aSize; i++) {
00592 newKey.key[i] = ~0;
00593 }
00594 newKey.isUnspec = false;
00595 newKey.trim();
00596
00597 return newKey;
00598 }
00599
00600
00601 Identifier Identifier::random() {
00602 Identifier newKey = ZERO;
00603 newKey.clearAddress();
00604
00605
00606
00607
00608
00609
00610 Identifier keyRandom = ZERO;
00611 mpn_random(keyRandom.key, aSize);
00612 Identifier keyrnd( rand() );
00613 mpn_mul_1( newKey.key, keyRandom.key, aSize, *keyrnd.key );
00614
00615 newKey.trim();
00616 assert(!newKey.isUnspecified());
00617
00618 return newKey;
00619 }
00620
00621 Identifier Identifier::sha1(const string& input) {
00622 Identifier newKey;
00623 newKey.clearAddress();
00624 uint8_t temp[40];
00625 for (int i=0; i<40; i++) temp[i] = 0;
00626 const char* c_str = input.c_str();
00627
00628 CSHA1 sha;
00629 sha.Reset();
00630 sha.Update( (uint8_t*)c_str, (uint32_t)input.size() );
00631 sha.Final();
00632 sha.GetHash(temp);
00633 mpn_set_str(newKey.key, (const uint8_t*)temp,
00634 (int)aSize * sizeof(mp_limb_t), 256);
00635 newKey.isUnspec = false;
00636 newKey.trim();
00637
00638 return newKey;
00639 }
00640
00641 Identifier Identifier::sha1(const uint8_t* value, size_t length ) {
00642 Identifier newKey;
00643 uint8_t temp[40];
00644 for (int i=0; i<40; i++) temp[i] = 0;
00645
00646 CSHA1 sha;
00647 sha.Reset();
00648 sha.Update( const_cast<uint8_t*>(value), (uint32_t)length );
00649 sha.Final();
00650 sha.GetHash(temp);
00651 mpn_set_str( newKey.key, (const uint8_t*)temp, (int)aSize * sizeof(mp_limb_t), 256);
00652 newKey.isUnspec = false;
00653 newKey.trim();
00654 return newKey;
00655 }
00656
00657
00658 Identifier Identifier::pow2(uint exponent) {
00659 Identifier newKey = ZERO;
00660
00661 newKey.key[exponent / GMP_LIMB_BITS] = (mp_limb_t) 1 << (exponent
00662 % GMP_LIMB_BITS);
00663
00664 return newKey;
00665 }
00666
00667
00668
00669
00670
00671
00672 inline void Identifier::trim() {
00673 key[array_size] = ~0;
00674 key[array_size - 1] &= GMP_MSB_MASK;
00675 }
00676
00677
00678 int Identifier::compareTo(const Identifier& compKey) const {
00679
00680 if( compKey.isUnspec == false && isUnspec == false )
00681 return mpn_cmp( key, compKey.key, aSize );
00682 else if( compKey.isUnspec == true && isUnspec == true )
00683 return 0;
00684 else
00685 return -1;
00686 }
00687
00688 }}