source: source/ariba/utility/types/Identifier.cpp@ 9982

Last change on this file since 9982 was 6919, checked in by mies, 15 years ago

Fixed tons of warnings when using CXXFLAGS="-Wall"!
File size: 17.2 KB
Line 
1// [License]
2// The Ariba-Underlay Copyright
3//
4// Copyright (c) 2008-2009, Institute of Telematics, UniversitÀt Karlsruhe (TH)
5//
6// Institute of Telematics
7// UniversitÀt Karlsruhe (TH)
8// Zirkel 2, 76128 Karlsruhe
9// Germany
10//
11// Redistribution and use in source and binary forms, with or without
12// modification, are permitted provided that the following conditions are
13// met:
14//
15// 1. Redistributions of source code must retain the above copyright
16// notice, this list of conditions and the following disclaimer.
17// 2. Redistributions in binary form must reproduce the above copyright
18// notice, this list of conditions and the following disclaimer in the
19// documentation and/or other materials provided with the distribution.
20//
21// THIS SOFTWARE IS PROVIDED BY THE INSTITUTE OF TELEMATICS ``AS IS'' AND
22// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
24// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE ARIBA PROJECT OR
25// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
26// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
27// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32//
33// The views and conclusions contained in the software and documentation
34// are those of the authors and should not be interpreted as representing
35// official policies, either expressed or implied, of the Institute of
36// Telematics.
37// [License]
38
39#include "Identifier.h"
40#include "ariba/utility/misc/sha1.h"
41
42namespace ariba {
43namespace utility {
44
45uint Identifier::keyLength = MAX_KEYLENGTH;
46
47uint Identifier::aSize = Identifier::keyLength / (8 * sizeof(mp_limb_t))
48 + (Identifier::keyLength % (8 * sizeof(mp_limb_t)) != 0 ? 1 : 0);
49
50mp_limb_t Identifier::GMP_MSB_MASK = (Identifier::keyLength % GMP_LIMB_BITS)
51 != 0 ? (((mp_limb_t) 1 << (Identifier::keyLength % GMP_LIMB_BITS)) - 1)
52 : (mp_limb_t) -1;
53
54/* virtual serialization */
55vsznDefault(Identifier);
56use_logging_cpp( Identifier );
57
58//--------------------------------------------------------------------
59// constants
60//--------------------------------------------------------------------
61
62// predefined keys
63const Identifier Identifier::UNSPECIFIED_KEY;
64const Identifier Identifier::ZERO((uint32_t) 0);
65const Identifier Identifier::ONE((uint32_t) 1);
66
67// hex crap
68const char* HEX = "0123456789abcdef";
69gmp_randstate_t randstate;
70
71void Identifier::clearAddress() {
72 for (size_t i = 0; i < array_size; i++)
73 key[i] = 0;
74 isUnspec = false;
75 trim();
76}
77
78bool Identifier::setAddress(string address) {
79 return false;
80}
81
82string Identifier::getAddress() const {
83 return toString();
84}
85
86//--------------------------------------------------------------------
87// construction and destruction
88//--------------------------------------------------------------------
89
90// default construction: create a unspecified node key
91Identifier::Identifier() {
92 seed();
93 isUnspec = true;
94 trim();
95}
96
97// create a key out of an normal integer
98Identifier::Identifier(uint32_t num) {
99 seed();
100 clearAddress();
101 key[0] = (uint32_t) num;
102 trim();
103}
104
105// create a key out of a buffer
106Identifier::Identifier(const unsigned char* buf, uint size) {
107 seed();
108 int trimSize, offset;
109 clearAddress();
110 trimSize = (int) std::min((uint) (aSize * sizeof(mp_limb_t)), size);
111 offset = aSize * sizeof(mp_limb_t) - trimSize;
112 memcpy(((char*) key) + offset, buf, trimSize);
113 trim();
114}
115
116// create a key out of an string with the given base
117Identifier::Identifier(const std::string& str, uint base) {
118 seed();
119
120 if ((base < 2) || (base > 16)) {
121 logging_error( "Identifier::Identifier(): Invalid base!" );
122 return;
123 }
124
125 string s(str);
126 clearAddress();
127
128 for (uint i = 0; i < s.size(); i++) {
129 if ((s[i] >= '0') && (s[i] <= '9')) {
130 s[i] -= '0';
131 } else if ((s[i] >= 'a') && (s[i] <= 'f')) {
132 s[i] -= ('a' - 10);
133 } else if ((s[i] >= 'A') & (s[i] <= 'F')) {
134 s[i] -= ('A' - 10);
135 } else {
136 logging_error( "Identifier::Identifier(): "
137 "Invalid character in string!" );
138 return;
139 }
140 }
141
142 mpn_set_str((mp_limb_t*) this->key, (const unsigned char*) s.c_str(),
143 str.size(), base);
144 trim();
145}
146
147// copy constructor
148Identifier::Identifier(const Identifier& rhs) {
149 seed();
150 (*this) = rhs;
151}
152
153// default destructur
154Identifier::~Identifier() {
155}
156
157void Identifier::seed(){
158 static bool isSeeded = false;
159 if( isSeeded ) return;
160
161 gmp_randinit_default( randstate );
162 gmp_randseed_ui( randstate, time(NULL) );
163
164 isSeeded = true;
165}
166
167//--------------------------------------------------------------------
168// string representations & node key attributes
169//--------------------------------------------------------------------
170
171void Identifier::setKeyLength(uint length) {
172 if ((length < 1) || (length > Identifier::keyLength)) {
173
174 logging_error( "Identifier::setKeyLength(): length must be <= " <<
175 MAX_KEYLENGTH << " and setKeyLength() must not be " <<
176 "called twice with different length!" );
177 return;
178 }
179
180 keyLength = length;
181
182 aSize = keyLength / (8 * sizeof(mp_limb_t)) + (keyLength % (8
183 * sizeof(mp_limb_t)) != 0 ? 1 : 0);
184
185 GMP_MSB_MASK = (keyLength % GMP_LIMB_BITS) != 0 ? (((mp_limb_t) 1
186 << (keyLength % GMP_LIMB_BITS)) - 1) : (mp_limb_t) -1;
187}
188
189// returns the length in bits
190uint Identifier::getLength() {
191 return Identifier::keyLength;
192}
193
194bool Identifier::isUnspecified() const {
195 return isUnspec;
196}
197
198std::string Identifier::toString(uint base) const {
199 if ((base < 2) || (base > 16)) {
200 logging_error( "Identifier::Identifier(): Invalid base!" );
201 return "";
202 }
203
204 if (isUnspec) return std::string("<unspec>");
205
206 char temp[250];
207 if (base == 16) {
208 int k = 0;
209 for (int i = (keyLength - 1) / 4; i >= 0; i--, k++) {
210 temp[k] = HEX[this->get(4 * i, 4)];
211 }
212 temp[k] = 0;
213 return std::string((const char*) temp);
214 } else if (base == 2) {
215 int k = 0;
216 for (int i = MAX_KEYLENGTH - 1; i >= 0; i -= 1, k++)
217 temp[k] = HEX[this->get(i, 1)];
218 temp[k] = 0;
219 return std::string((const char*) temp);
220 }
221 //#endif
222#if 0
223 size_t log2[33] = {0};
224 log2[2] = 1;
225 log2[4] = 2;
226 log2[8] = 3;
227 log2[16] = 4;
228 log2[32] = 5;
229 size_t sh = (sizeof(mp_limb_t)*8/log2[base]);
230 // key[array_size] = ~0;
231 mp_size_t last = mpn_get_str((unsigned char*) temp, base,
232 (mp_limb_t*) this->key, aSize+1);
233 for (int i = 0; i < last-sh; i++) {
234 temp[i] = HEX[temp[i+sh]];
235 }
236 temp[last-sh] = 0;
237 return std::string((const char*) temp);
238}
239#endif
240 return "<not supported>";
241}
242
243//--------------------------------------------------------------------
244// operators
245//--------------------------------------------------------------------
246
247// assignment operator
248Identifier& Identifier::operator=(const Identifier& rhs) {
249 isUnspec = rhs.isUnspec;
250 memcpy(key, rhs.key, aSize * sizeof(mp_limb_t));
251 return *this;
252}
253
254// sub one prefix operator
255Identifier& Identifier::operator--() {
256 return (*this -= ONE);
257}
258
259// sub one postfix operator
260Identifier Identifier::operator--(int) {
261 Identifier clone = *this;
262 *this -= ONE;
263 return clone;
264}
265
266// add one prefix operator
267Identifier& Identifier::operator++() {
268 return (*this += ONE);
269}
270
271// sub one postfix operator
272Identifier Identifier::operator++(int) {
273 Identifier clone = *this;
274 *this += ONE;
275 return clone;
276}
277
278// add assign operator
279Identifier& Identifier::operator+=(const Identifier& rhs) {
280 mpn_add_n((mp_limb_t*) key, (mp_limb_t*) key, (mp_limb_t*) rhs.key, aSize);
281 trim();
282 isUnspec = false;
283 return *this;
284}
285
286// sub assign operator
287Identifier& Identifier::operator-=(const Identifier& rhs) {
288 mpn_sub_n((mp_limb_t*) key, (mp_limb_t*) key, (mp_limb_t*) rhs.key, aSize);
289 trim();
290 isUnspec = false;
291 return *this;
292}
293
294// add operator
295Identifier Identifier::operator+(const Identifier& rhs) const {
296 Identifier result = *this;
297 result += rhs;
298 return result;
299}
300
301// sub operator
302Identifier Identifier::operator-(const Identifier& rhs) const {
303 Identifier result = *this;
304 result -= rhs;
305 return result;
306}
307
308// compare operators
309bool Identifier::operator<(const Identifier& compKey) const {
310 return compareTo(compKey) < 0;
311}
312bool Identifier::operator>(const Identifier& compKey) const {
313 return compareTo(compKey) > 0;
314}
315bool Identifier::operator<=(const Identifier& compKey) const {
316 return compareTo(compKey) <= 0;
317}
318bool Identifier::operator>=(const Identifier& compKey) const {
319 return compareTo(compKey) >= 0;
320}
321bool Identifier::operator==(const Identifier& compKey) const {
322
323 if( this->isUnspecified() && compKey.isUnspecified() )
324 return true;
325 else
326 return compareTo(compKey) == 0;
327}
328bool Identifier::operator!=(const Identifier& compKey) const {
329 return compareTo(compKey) != 0;
330}
331
332// bitwise xor
333Identifier Identifier::operator^(const Identifier& rhs) const {
334 Identifier result = *this;
335 for (uint i = 0; i < aSize; i++) {
336 result.key[i] ^= rhs.key[i];
337 }
338
339 return result;
340}
341
342// bitwise or
343Identifier Identifier::operator|(const Identifier& rhs) const {
344 Identifier result = *this;
345 for (uint i = 0; i < aSize; i++) {
346 result.key[i] |= rhs.key[i];
347 }
348
349 return result;
350}
351
352// bitwise and
353Identifier Identifier::operator&(const Identifier& rhs) const {
354 Identifier result = *this;
355 for (uint i = 0; i < aSize; i++) {
356 result.key[i] &= rhs.key[i];
357 }
358
359 return result;
360}
361
362// complement
363Identifier Identifier::operator~() const {
364 Identifier result = *this;
365 for (uint i = 0; i < aSize; i++) {
366 result.key[i] = ~key[i];
367 }
368 result.trim();
369
370 return result;
371}
372
373// bitwise shift right
374Identifier Identifier::operator>>(uint num) const {
375 Identifier result = ZERO;
376 int i = num / GMP_LIMB_BITS;
377
378 num %= GMP_LIMB_BITS;
379
380 if (i >= (int) aSize) return result;
381
382 for (int j = 0; j < (int) aSize - i; j++) {
383 result.key[j] = key[j + i];
384 }
385 mpn_rshift(result.key, result.key, aSize, num);
386 result.isUnspec = false;
387 result.trim();
388
389 return result;
390}
391
392// bitwise shift left
393Identifier Identifier::operator<<(uint num) const {
394 Identifier result = ZERO;
395 int i = num / GMP_LIMB_BITS;
396
397 num %= GMP_LIMB_BITS;
398
399 if (i >= (int) aSize) return result;
400
401 for (int j = 0; j < (int) aSize - i; j++) {
402 result.key[j + i] = key[j];
403 }
404 mpn_lshift(result.key, result.key, aSize, num);
405 result.isUnspec = false;
406 result.trim();
407
408 return result;
409}
410
411// get bit
412IdentifierBit Identifier::operator[](uint n) {
413 return IdentifierBit(get(n, 1), n, this);
414}
415
416Identifier& Identifier::setBitAt(uint pos, bool value) {
417 mp_limb_t digit = 1;
418 digit = digit << (pos % GMP_LIMB_BITS);
419
420 if (value) {
421 key[pos / GMP_LIMB_BITS] |= digit;
422 } else {
423 //key[pos / GMP_LIMB_BITS] = key[pos / GMP_LIMB_BITS] & ~digit;
424 key[pos / GMP_LIMB_BITS] &= ~digit;
425 }
426
427 return *this;
428}
429;
430
431//--------------------------------------------------------------------
432// additional math
433//--------------------------------------------------------------------
434
435// returns a sub integer
436uint32_t Identifier::get(uint p, uint n) const {
437 int i = p / GMP_LIMB_BITS, // index of starting bit
438 f = p % GMP_LIMB_BITS, // position of starting bit
439 f2 = f + n - GMP_LIMB_BITS; // how many bits to take from next index
440
441 if (p + n > Identifier::keyLength) {
442 logging_error( "Identifier::get: Invalid range (index too large!)" );
443 return 0;
444 }
445
446 return ((key[i] >> f) | // get the bits of key[i]
447 (f2 > 0 ? (key[i + 1] << (GMP_LIMB_BITS - f)) : 0)) & // the extra bits from key[i+1]
448 (((uint32_t) (~0)) >> (GMP_LIMB_BITS - n)); // delete unused bits
449}
450
451// fill suffix with random bits
452Identifier Identifier::randomSuffix(uint pos) const {
453 Identifier newKey = *this;
454 int i = pos / GMP_LIMB_BITS, j = pos % GMP_LIMB_BITS;
455 mp_limb_t m = ((mp_limb_t) 1 << j) - 1;
456 mp_limb_t rnd;
457
458 mpn_random(&rnd, 1);
459 newKey.key[i] &= ~m;
460 newKey.key[i] |= (rnd & m);
461 mpn_random(newKey.key, i);
462 newKey.trim();
463
464 return newKey;
465}
466
467// fill prefix with random bits
468Identifier Identifier::randomPrefix(uint pos) const {
469 Identifier newKey = *this;
470 int i = pos / GMP_LIMB_BITS, j = pos % GMP_LIMB_BITS;
471 mp_limb_t m = ((mp_limb_t) 1 << j) - 1;
472 mp_limb_t rnd;
473
474 mpn_random(&rnd, 1);
475
476 newKey.key[i] &= m;
477 newKey.key[i] |= (rnd & ~m);
478 for (int k = aSize - 1; k != i; k--) {
479 mpn_random(&newKey.key[k], 1);
480 }
481 newKey.trim();
482
483 return newKey;
484}
485
486// calculate shared prefix length
487uint Identifier::sharedPrefixLength(const Identifier& compKey) const {
488 if (compareTo(compKey) == 0) return keyLength;
489
490 uint length = 0;
491 int i;
492 uint j;
493 bool msb = true;
494
495 // count equal limbs first:
496 for (i = aSize - 1; i >= 0; --i) {
497 if (this->key[i] != compKey.key[i]) {
498 // XOR first differing limb for easy counting of the bits:
499 mp_limb_t d = this->key[i] ^ compKey.key[i];
500 if (msb) d <<= (GMP_LIMB_BITS - (keyLength % GMP_LIMB_BITS));
501 for (j = GMP_LIMB_BITS - 1; d >>= 1; --j)
502 ;
503 length += j;
504 break;
505 }
506 length += GMP_LIMB_BITS;
507 msb = false;
508 }
509
510 return length;
511}
512
513// calculate log of base 2
514int Identifier::log_2() const {
515 int16_t i = aSize - 1;
516
517 while (i >= 0 && key[i] == 0) {
518 i--;
519 }
520
521 if (i < 0) {
522 return -1;
523 }
524
525 mp_limb_t j = key[i];
526 i *= GMP_LIMB_BITS;
527 while (j != 0) {
528 j >>= 1;
529 i++;
530 }
531
532 return i - 1;
533}
534
535// returns a simple hash of the key
536size_t Identifier::hash() const {
537 return (size_t) key[0];
538}
539
540// returns true, if this key is element of the interval (keyA, keyB)
541bool Identifier::isBetween(const Identifier& keyA, const Identifier& keyB) const {
542 if (isUnspec || keyA.isUnspec || keyB.isUnspec) return false;
543
544 if (*this == keyA) return false;
545 else if (keyA < keyB) return ((*this > keyA) && (*this < keyB));
546 else return ((*this > keyA) || (*this < keyB));
547}
548
549// returns true, if this key is element of the interval (keyA, keyB]
550bool Identifier::isBetweenR(const Identifier& keyA, const Identifier& keyB) const {
551 if (isUnspec || keyA.isUnspec || keyB.isUnspec) return false;
552
553 if ((keyA == keyB) && (*this == keyA)) return true;
554 else if (keyA <= keyB) return ((*this > keyA) && (*this <= keyB));
555 else return ((*this > keyA) || (*this <= keyB));
556}
557
558// returns true, if this key is element of the interval [keyA, keyB)
559bool Identifier::isBetweenL(const Identifier& keyA, const Identifier& keyB) const {
560 if (isUnspec || keyA.isUnspec || keyB.isUnspec) return false;
561
562 if ((keyA == keyB) && (*this == keyA)) return true;
563 else if (keyA <= keyB) return ((*this >= keyA) && (*this < keyB));
564 else return ((*this >= keyA) || (*this < keyB));
565}
566
567// returns true, if this key is element of the interval [keyA, keyB]
568bool Identifier::isBetweenLR(const Identifier& keyA, const Identifier& keyB) const {
569 if (isUnspec || keyA.isUnspec || keyB.isUnspec) return false;
570
571 if ((keyA == keyB) && (*this == keyA)) return true;
572 else if (keyA <= keyB) return ((*this >= keyA) && (*this <= keyB));
573 else return ((*this >= keyA) || (*this <= keyB));
574}
575
576//----------------------------------------------------------------------
577// statics and globals
578//----------------------------------------------------------------------
579
580// default console output
581std::ostream& operator<<(std::ostream& os, const Identifier& c) {
582 os << c.toString(16);
583 return os;
584}
585;
586
587// returns a key filled with bit 1
588Identifier Identifier::max() {
589 Identifier newKey;
590
591 for (uint i = 0; i < aSize; i++) {
592 newKey.key[i] = ~0;
593 }
594 newKey.isUnspec = false;
595 newKey.trim();
596
597 return newKey;
598}
599
600// generate random number
601Identifier Identifier::random() {
602 Identifier newKey = ZERO;
603 newKey.clearAddress();
604
605 //as mpn_random has no seeding function
606 // we mess aroung here a little to achive some randomness
607 // using the rand function that _is_ seeded in the
608 // StartupWrapper::initSystem function
609
610 Identifier keyRandom = ZERO;
611 mpn_random(keyRandom.key, aSize);
612 Identifier keyrnd( rand() );
613 mpn_mul_1( newKey.key, keyRandom.key, aSize, *keyrnd.key );
614
615 newKey.trim();
616 assert(!newKey.isUnspecified());
617
618 return newKey;
619}
620
621Identifier Identifier::sha1(const string& input) {
622 Identifier newKey;
623 newKey.clearAddress();
624 uint8_t temp[40];
625 for (int i=0; i<40; i++) temp[i] = 0;
626 const char* c_str = input.c_str();
627
628 CSHA1 sha;
629 sha.Reset();
630 sha.Update( (uint8_t*)c_str, (uint32_t)input.size() );
631 sha.Final();
632 sha.GetHash(temp);
633 mpn_set_str(newKey.key, (const uint8_t*)temp,
634 (int)aSize * sizeof(mp_limb_t), 256);
635 newKey.isUnspec = false;
636 newKey.trim();
637
638 return newKey;
639}
640
641Identifier Identifier::sha1(const uint8_t* value, size_t length ) {
642 Identifier newKey;
643 uint8_t temp[40];
644 for (int i=0; i<40; i++) temp[i] = 0;
645
646 CSHA1 sha;
647 sha.Reset();
648 sha.Update( const_cast<uint8_t*>(value), (uint32_t)length );
649 sha.Final();
650 sha.GetHash(temp);
651 mpn_set_str( newKey.key, (const uint8_t*)temp, (int)aSize * sizeof(mp_limb_t), 256);
652 newKey.isUnspec = false;
653 newKey.trim();
654 return newKey;
655}
656
657// generate a key=2**exponent
658Identifier Identifier::pow2(uint exponent) {
659 Identifier newKey = ZERO;
660
661 newKey.key[exponent / GMP_LIMB_BITS] = (mp_limb_t) 1 << (exponent
662 % GMP_LIMB_BITS);
663
664 return newKey;
665}
666
667//--------------------------------------------------------------------
668// private methods (mostly inlines)
669//--------------------------------------------------------------------
670
671// trims a key after each operation
672inline void Identifier::trim() {
673 key[array_size] = ~0;
674 key[array_size - 1] &= GMP_MSB_MASK;
675}
676
677// compares this key to any other
678int Identifier::compareTo(const Identifier& compKey) const {
679
680 if( compKey.isUnspec == false && isUnspec == false )
681 return mpn_cmp( key, compKey.key, aSize );
682 else if( compKey.isUnspec == true && isUnspec == true )
683 return 0;
684 else
685 return -1;
686}
687
688}} // namespace ariba, common
Note: See TracBrowser for help on using the repository browser.