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 (int i = 0; i < array_size; i++)
00073 key[i] = 0;
00074 isUnspec = false;
00075 trim();
00076 }
00077
00078 bool Identifier::setAddress(string address) {
00079
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[80];
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 }
00241
00242
00243
00244
00245
00246
00247 Identifier& Identifier::operator=(const Identifier& rhs) {
00248 isUnspec = rhs.isUnspec;
00249 memcpy(key, rhs.key, aSize * sizeof(mp_limb_t));
00250 return *this;
00251 }
00252
00253
00254 Identifier& Identifier::operator--() {
00255 return (*this -= ONE);
00256 }
00257
00258
00259 Identifier Identifier::operator--(int) {
00260 Identifier clone = *this;
00261 *this -= ONE;
00262 return clone;
00263 }
00264
00265
00266 Identifier& Identifier::operator++() {
00267 return (*this += ONE);
00268 }
00269
00270
00271 Identifier Identifier::operator++(int) {
00272 Identifier clone = *this;
00273 *this += ONE;
00274 return clone;
00275 }
00276
00277
00278 Identifier& Identifier::operator+=(const Identifier& rhs) {
00279 mpn_add_n((mp_limb_t*) key, (mp_limb_t*) key, (mp_limb_t*) rhs.key, aSize);
00280 trim();
00281 isUnspec = false;
00282 return *this;
00283 }
00284
00285
00286 Identifier& Identifier::operator-=(const Identifier& rhs) {
00287 mpn_sub_n((mp_limb_t*) key, (mp_limb_t*) key, (mp_limb_t*) rhs.key, aSize);
00288 trim();
00289 isUnspec = false;
00290 return *this;
00291 }
00292
00293
00294 Identifier Identifier::operator+(const Identifier& rhs) const {
00295 Identifier result = *this;
00296 result += rhs;
00297 return result;
00298 }
00299
00300
00301 Identifier Identifier::operator-(const Identifier& rhs) const {
00302 Identifier result = *this;
00303 result -= rhs;
00304 return result;
00305 }
00306
00307
00308 bool Identifier::operator<(const Identifier& compKey) const {
00309 return compareTo(compKey) < 0;
00310 }
00311 bool Identifier::operator>(const Identifier& compKey) const {
00312 return compareTo(compKey) > 0;
00313 }
00314 bool Identifier::operator<=(const Identifier& compKey) const {
00315 return compareTo(compKey) <= 0;
00316 }
00317 bool Identifier::operator>=(const Identifier& compKey) const {
00318 return compareTo(compKey) >= 0;
00319 }
00320 bool Identifier::operator==(const Identifier& compKey) const {
00321
00322 if( this->isUnspecified() && compKey.isUnspecified() )
00323 return true;
00324 else
00325 return compareTo(compKey) == 0;
00326 }
00327 bool Identifier::operator!=(const Identifier& compKey) const {
00328 return compareTo(compKey) != 0;
00329 }
00330
00331
00332 Identifier Identifier::operator^(const Identifier& rhs) const {
00333 Identifier result = *this;
00334 for (uint i = 0; i < aSize; i++) {
00335 result.key[i] ^= rhs.key[i];
00336 }
00337
00338 return result;
00339 }
00340
00341
00342 Identifier Identifier::operator|(const Identifier& rhs) const {
00343 Identifier result = *this;
00344 for (uint i = 0; i < aSize; i++) {
00345 result.key[i] |= rhs.key[i];
00346 }
00347
00348 return result;
00349 }
00350
00351
00352 Identifier Identifier::operator&(const Identifier& rhs) const {
00353 Identifier result = *this;
00354 for (uint i = 0; i < aSize; i++) {
00355 result.key[i] &= rhs.key[i];
00356 }
00357
00358 return result;
00359 }
00360
00361
00362 Identifier Identifier::operator~() const {
00363 Identifier result = *this;
00364 for (uint i = 0; i < aSize; i++) {
00365 result.key[i] = ~key[i];
00366 }
00367 result.trim();
00368
00369 return result;
00370 }
00371
00372
00373 Identifier Identifier::operator>>(uint num) const {
00374 Identifier result = ZERO;
00375 int i = num / GMP_LIMB_BITS;
00376
00377 num %= GMP_LIMB_BITS;
00378
00379 if (i >= (int) aSize) return result;
00380
00381 for (int j = 0; j < (int) aSize - i; j++) {
00382 result.key[j] = key[j + i];
00383 }
00384 mpn_rshift(result.key, result.key, aSize, num);
00385 result.isUnspec = false;
00386 result.trim();
00387
00388 return result;
00389 }
00390
00391
00392 Identifier Identifier::operator<<(uint num) const {
00393 Identifier result = ZERO;
00394 int i = num / GMP_LIMB_BITS;
00395
00396 num %= GMP_LIMB_BITS;
00397
00398 if (i >= (int) aSize) return result;
00399
00400 for (int j = 0; j < (int) aSize - i; j++) {
00401 result.key[j + i] = key[j];
00402 }
00403 mpn_lshift(result.key, result.key, aSize, num);
00404 result.isUnspec = false;
00405 result.trim();
00406
00407 return result;
00408 }
00409
00410
00411 IdentifierBit Identifier::operator[](uint n) {
00412 return IdentifierBit(get(n, 1), n, this);
00413 }
00414
00415 Identifier& Identifier::setBitAt(uint pos, bool value) {
00416 mp_limb_t digit = 1;
00417 digit = digit << (pos % GMP_LIMB_BITS);
00418
00419 if (value) {
00420 key[pos / GMP_LIMB_BITS] |= digit;
00421 } else {
00422
00423 key[pos / GMP_LIMB_BITS] &= ~digit;
00424 }
00425
00426 return *this;
00427 }
00428 ;
00429
00430
00431
00432
00433
00434
00435 uint32_t Identifier::get(uint p, uint n) const {
00436 int i = p / GMP_LIMB_BITS,
00437 f = p % GMP_LIMB_BITS,
00438 f2 = f + n - GMP_LIMB_BITS;
00439
00440 if (p + n > Identifier::keyLength) {
00441 logging_error( "Identifier::get: Invalid range (index too large!)" );
00442 return 0;
00443 }
00444
00445 return ((key[i] >> f) |
00446 (f2 > 0 ? (key[i + 1] << (GMP_LIMB_BITS - f)) : 0)) &
00447 (((uint32_t) (~0)) >> (GMP_LIMB_BITS - n));
00448 }
00449
00450
00451 Identifier Identifier::randomSuffix(uint pos) const {
00452 Identifier newKey = *this;
00453 int i = pos / GMP_LIMB_BITS, j = pos % GMP_LIMB_BITS;
00454 mp_limb_t m = ((mp_limb_t) 1 << j) - 1;
00455 mp_limb_t rnd;
00456
00457 mpn_random(&rnd, 1);
00458 newKey.key[i] &= ~m;
00459 newKey.key[i] |= (rnd & m);
00460 mpn_random(newKey.key, i);
00461 newKey.trim();
00462
00463 return newKey;
00464 }
00465
00466
00467 Identifier Identifier::randomPrefix(uint pos) const {
00468 Identifier newKey = *this;
00469 int i = pos / GMP_LIMB_BITS, j = pos % GMP_LIMB_BITS;
00470 mp_limb_t m = ((mp_limb_t) 1 << j) - 1;
00471 mp_limb_t rnd;
00472
00473 mpn_random(&rnd, 1);
00474
00475 newKey.key[i] &= m;
00476 newKey.key[i] |= (rnd & ~m);
00477 for (int k = aSize - 1; k != i; k--) {
00478 mpn_random(&newKey.key[k], 1);
00479 }
00480 newKey.trim();
00481
00482 return newKey;
00483 }
00484
00485
00486 uint Identifier::sharedPrefixLength(const Identifier& compKey) const {
00487 if (compareTo(compKey) == 0) return keyLength;
00488
00489 uint length = 0;
00490 int i;
00491 uint j;
00492 bool msb = true;
00493
00494
00495 for (i = aSize - 1; i >= 0; --i) {
00496 if (this->key[i] != compKey.key[i]) {
00497
00498 mp_limb_t d = this->key[i] ^ compKey.key[i];
00499 if (msb) d <<= (GMP_LIMB_BITS - (keyLength % GMP_LIMB_BITS));
00500 for (j = GMP_LIMB_BITS - 1; d >>= 1; --j)
00501 ;
00502 length += j;
00503 break;
00504 }
00505 length += GMP_LIMB_BITS;
00506 msb = false;
00507 }
00508
00509 return length;
00510 }
00511
00512
00513 int Identifier::log_2() const {
00514 int16_t i = aSize - 1;
00515
00516 while (i >= 0 && key[i] == 0) {
00517 i--;
00518 }
00519
00520 if (i < 0) {
00521 return -1;
00522 }
00523
00524 mp_limb_t j = key[i];
00525 i *= GMP_LIMB_BITS;
00526 while (j != 0) {
00527 j >>= 1;
00528 i++;
00529 }
00530
00531 return i - 1;
00532 }
00533
00534
00535 size_t Identifier::hash() const {
00536 return (size_t) key[0];
00537 }
00538
00539
00540 bool Identifier::isBetween(const Identifier& keyA, const Identifier& keyB) const {
00541 if (isUnspec || keyA.isUnspec || keyB.isUnspec) return false;
00542
00543 if (*this == keyA) return false;
00544 else if (keyA < keyB) return ((*this > keyA) && (*this < keyB));
00545 else return ((*this > keyA) || (*this < keyB));
00546 }
00547
00548
00549 bool Identifier::isBetweenR(const Identifier& keyA, const Identifier& keyB) const {
00550 if (isUnspec || keyA.isUnspec || keyB.isUnspec) return false;
00551
00552 if ((keyA == keyB) && (*this == keyA)) return true;
00553 else if (keyA <= keyB) return ((*this > keyA) && (*this <= keyB));
00554 else return ((*this > keyA) || (*this <= keyB));
00555 }
00556
00557
00558 bool Identifier::isBetweenL(const Identifier& keyA, const Identifier& keyB) const {
00559 if (isUnspec || keyA.isUnspec || keyB.isUnspec) return false;
00560
00561 if ((keyA == keyB) && (*this == keyA)) return true;
00562 else if (keyA <= keyB) return ((*this >= keyA) && (*this < keyB));
00563 else return ((*this >= keyA) || (*this < keyB));
00564 }
00565
00566
00567 bool Identifier::isBetweenLR(const Identifier& keyA, const Identifier& keyB) const {
00568 if (isUnspec || keyA.isUnspec || keyB.isUnspec) return false;
00569
00570 if ((keyA == keyB) && (*this == keyA)) return true;
00571 else if (keyA <= keyB) return ((*this >= keyA) && (*this <= keyB));
00572 else return ((*this >= keyA) || (*this <= keyB));
00573 }
00574
00575
00576
00577
00578
00579
00580 std::ostream& operator<<(std::ostream& os, const Identifier& c) {
00581 os << c.toString(16);
00582 return os;
00583 }
00584 ;
00585
00586
00587 Identifier Identifier::max() {
00588 Identifier newKey;
00589
00590 for (uint i = 0; i < aSize; i++) {
00591 newKey.key[i] = ~0;
00592 }
00593 newKey.isUnspec = false;
00594 newKey.trim();
00595
00596 return newKey;
00597 }
00598
00599
00600 Identifier Identifier::random() {
00601 Identifier newKey = ZERO;
00602
00603
00604
00605
00606
00607
00608 Identifier keyRandom = ZERO;
00609 mpn_random(keyRandom.key, aSize);
00610 Identifier keyrnd( rand() );
00611 mpn_mul_1( newKey.key, keyRandom.key, aSize, *keyrnd.key );
00612
00613 newKey.trim();
00614 return newKey;
00615 }
00616
00617 Identifier Identifier::sha1(const string& input) {
00618 Identifier newKey;
00619 newKey.clearAddress();
00620 uint8_t temp[40];
00621 for (int i=0; i<40; i++) temp[i] = 0;
00622 const char* c_str = input.c_str();
00623
00624 CSHA1 sha;
00625 sha.Reset();
00626 sha.Update( (uint8_t*)c_str, (uint32_t)input.size() );
00627 sha.Final();
00628 sha.GetHash(temp);
00629 mpn_set_str(newKey.key, (const uint8_t*)temp,
00630 (int)aSize * sizeof(mp_limb_t), 256);
00631 newKey.isUnspec = false;
00632 newKey.trim();
00633
00634 return newKey;
00635 }
00636
00637 Identifier Identifier::sha1(const uint8_t* value, size_t length ) {
00638 Identifier newKey;
00639 uint8_t temp[40];
00640 for (int i=0; i<40; i++) temp[i] = 0;
00641
00642 CSHA1 sha;
00643 sha.Reset();
00644 sha.Update( const_cast<uint8_t*>(value), (uint32_t)length );
00645 sha.Final();
00646 sha.GetHash(temp);
00647 mpn_set_str( newKey.key, (const uint8_t*)temp, (int)aSize * sizeof(mp_limb_t), 256);
00648 newKey.isUnspec = false;
00649 newKey.trim();
00650 return newKey;
00651 }
00652
00653
00654 Identifier Identifier::pow2(uint exponent) {
00655 Identifier newKey = ZERO;
00656
00657 newKey.key[exponent / GMP_LIMB_BITS] = (mp_limb_t) 1 << (exponent
00658 % GMP_LIMB_BITS);
00659
00660 return newKey;
00661 }
00662
00663
00664
00665
00666
00667
00668 inline void Identifier::trim() {
00669 key[array_size] = ~0;
00670 key[array_size - 1] &= GMP_MSB_MASK;
00671 }
00672
00673
00674 int Identifier::compareTo(const Identifier& compKey) const {
00675
00676 if( compKey.isUnspec == false && isUnspec == false )
00677 return mpn_cmp( key, compKey.key, aSize );
00678 else if( compKey.isUnspec == true && isUnspec == true )
00679 return 0;
00680 else
00681 return -1;
00682 }
00683
00684 }}