An Overlay-based
Virtual Network Substrate
SpoVNet

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

Last change on this file since 3705 was 3705, checked in by Christoph Mayer, 15 years ago

-einige fixed bzgl. link management, fehlerhafte serialisierer, etc.

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 (int i = 0; i < array_size; i++)
73                key[i] = 0;
74        isUnspec = false;
75        trim();
76}
77
78bool Identifier::setAddress(string address) {
79        // TODO
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[80];
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}
241
242//--------------------------------------------------------------------
243// operators
244//--------------------------------------------------------------------
245
246// assignment operator
247Identifier& Identifier::operator=(const Identifier& rhs) {
248        isUnspec = rhs.isUnspec;
249        memcpy(key, rhs.key, aSize * sizeof(mp_limb_t));
250        return *this;
251}
252
253// sub one prefix operator
254Identifier& Identifier::operator--() {
255        return (*this -= ONE);
256}
257
258// sub one postfix operator
259Identifier Identifier::operator--(int) {
260        Identifier clone = *this;
261        *this -= ONE;
262        return clone;
263}
264
265// add one prefix operator
266Identifier& Identifier::operator++() {
267        return (*this += ONE);
268}
269
270// sub one postfix operator
271Identifier Identifier::operator++(int) {
272        Identifier clone = *this;
273        *this += ONE;
274        return clone;
275}
276
277// add assign operator
278Identifier& Identifier::operator+=(const Identifier& rhs) {
279        mpn_add_n((mp_limb_t*) key, (mp_limb_t*) key, (mp_limb_t*) rhs.key, aSize);
280        trim();
281        isUnspec = false;
282        return *this;
283}
284
285// sub assign operator
286Identifier& Identifier::operator-=(const Identifier& rhs) {
287        mpn_sub_n((mp_limb_t*) key, (mp_limb_t*) key, (mp_limb_t*) rhs.key, aSize);
288        trim();
289        isUnspec = false;
290        return *this;
291}
292
293// add operator
294Identifier Identifier::operator+(const Identifier& rhs) const {
295        Identifier result = *this;
296        result += rhs;
297        return result;
298}
299
300// sub operator
301Identifier Identifier::operator-(const Identifier& rhs) const {
302        Identifier result = *this;
303        result -= rhs;
304        return result;
305}
306
307// compare operators
308bool Identifier::operator<(const Identifier& compKey) const {
309        return compareTo(compKey) < 0;
310}
311bool Identifier::operator>(const Identifier& compKey) const {
312        return compareTo(compKey) > 0;
313}
314bool Identifier::operator<=(const Identifier& compKey) const {
315        return compareTo(compKey) <= 0;
316}
317bool Identifier::operator>=(const Identifier& compKey) const {
318        return compareTo(compKey) >= 0;
319}
320bool Identifier::operator==(const Identifier& compKey) const {
321
322        if( this->isUnspecified() && compKey.isUnspecified() )
323                return true;
324        else
325                return compareTo(compKey) == 0;
326}
327bool Identifier::operator!=(const Identifier& compKey) const {
328        return compareTo(compKey) != 0;
329}
330
331// bitwise xor
332Identifier Identifier::operator^(const Identifier& rhs) const {
333        Identifier result = *this;
334        for (uint i = 0; i < aSize; i++) {
335                result.key[i] ^= rhs.key[i];
336        }
337
338        return result;
339}
340
341// bitwise or
342Identifier Identifier::operator|(const Identifier& rhs) const {
343        Identifier result = *this;
344        for (uint i = 0; i < aSize; i++) {
345                result.key[i] |= rhs.key[i];
346        }
347
348        return result;
349}
350
351// bitwise and
352Identifier Identifier::operator&(const Identifier& rhs) const {
353        Identifier result = *this;
354        for (uint i = 0; i < aSize; i++) {
355                result.key[i] &= rhs.key[i];
356        }
357
358        return result;
359}
360
361// complement
362Identifier Identifier::operator~() const {
363        Identifier result = *this;
364        for (uint i = 0; i < aSize; i++) {
365                result.key[i] = ~key[i];
366        }
367        result.trim();
368
369        return result;
370}
371
372// bitwise shift right
373Identifier Identifier::operator>>(uint num) const {
374        Identifier result = ZERO;
375        int i = num / GMP_LIMB_BITS;
376
377        num %= GMP_LIMB_BITS;
378
379        if (i >= (int) aSize) return result;
380
381        for (int j = 0; j < (int) aSize - i; j++) {
382                result.key[j] = key[j + i];
383        }
384        mpn_rshift(result.key, result.key, aSize, num);
385        result.isUnspec = false;
386        result.trim();
387
388        return result;
389}
390
391// bitwise shift left
392Identifier Identifier::operator<<(uint num) const {
393        Identifier result = ZERO;
394        int i = num / GMP_LIMB_BITS;
395
396        num %= GMP_LIMB_BITS;
397
398        if (i >= (int) aSize) return result;
399
400        for (int j = 0; j < (int) aSize - i; j++) {
401                result.key[j + i] = key[j];
402        }
403        mpn_lshift(result.key, result.key, aSize, num);
404        result.isUnspec = false;
405        result.trim();
406
407        return result;
408}
409
410// get bit
411IdentifierBit Identifier::operator[](uint n) {
412        return IdentifierBit(get(n, 1), n, this);
413}
414
415Identifier& Identifier::setBitAt(uint pos, bool value) {
416        mp_limb_t digit = 1;
417        digit = digit << (pos % GMP_LIMB_BITS);
418
419        if (value) {
420                key[pos / GMP_LIMB_BITS] |= digit;
421        } else {
422                //key[pos / GMP_LIMB_BITS] = key[pos / GMP_LIMB_BITS] & ~digit;
423                key[pos / GMP_LIMB_BITS] &= ~digit;
424        }
425
426        return *this;
427}
428;
429
430//--------------------------------------------------------------------
431// additional math
432//--------------------------------------------------------------------
433
434// returns a sub integer
435uint32_t Identifier::get(uint p, uint n) const {
436        int i = p / GMP_LIMB_BITS, // index of starting bit
437                        f = p % GMP_LIMB_BITS, // position of starting bit
438                        f2 = f + n - GMP_LIMB_BITS; // how many bits to take from next index
439
440        if (p + n > Identifier::keyLength) {
441                logging_error( "Identifier::get: Invalid range (index too large!)" );
442                return 0;
443        }
444
445        return ((key[i] >> f) | // get the bits of key[i]
446                        (f2 > 0 ? (key[i + 1] << (GMP_LIMB_BITS - f)) : 0)) & // the extra bits from key[i+1]
447                        (((uint32_t) (~0)) >> (GMP_LIMB_BITS - n)); // delete unused bits
448}
449
450// fill suffix with random bits
451Identifier Identifier::randomSuffix(uint pos) const {
452        Identifier newKey = *this;
453        int i = pos / GMP_LIMB_BITS, j = pos % GMP_LIMB_BITS;
454        mp_limb_t m = ((mp_limb_t) 1 << j) - 1;
455        mp_limb_t rnd;
456
457        mpn_random(&rnd, 1);
458        newKey.key[i] &= ~m;
459        newKey.key[i] |= (rnd & m);
460        mpn_random(newKey.key, i);
461        newKey.trim();
462
463        return newKey;
464}
465
466// fill prefix with random bits
467Identifier Identifier::randomPrefix(uint pos) const {
468        Identifier newKey = *this;
469        int i = pos / GMP_LIMB_BITS, j = pos % GMP_LIMB_BITS;
470        mp_limb_t m = ((mp_limb_t) 1 << j) - 1;
471        mp_limb_t rnd;
472
473        mpn_random(&rnd, 1);
474
475        newKey.key[i] &= m;
476        newKey.key[i] |= (rnd & ~m);
477        for (int k = aSize - 1; k != i; k--) {
478                mpn_random(&newKey.key[k], 1);
479        }
480        newKey.trim();
481
482        return newKey;
483}
484
485// calculate shared prefix length
486uint Identifier::sharedPrefixLength(const Identifier& compKey) const {
487        if (compareTo(compKey) == 0) return keyLength;
488
489        uint length = 0;
490        int i;
491        uint j;
492        bool msb = true;
493
494        // count equal limbs first:
495        for (i = aSize - 1; i >= 0; --i) {
496                if (this->key[i] != compKey.key[i]) {
497                        // XOR first differing limb for easy counting of the bits:
498                        mp_limb_t d = this->key[i] ^ compKey.key[i];
499                        if (msb) d <<= (GMP_LIMB_BITS - (keyLength % GMP_LIMB_BITS));
500                        for (j = GMP_LIMB_BITS - 1; d >>= 1; --j)
501                                ;
502                        length += j;
503                        break;
504                }
505                length += GMP_LIMB_BITS;
506                msb = false;
507        }
508
509        return length;
510}
511
512// calculate log of base 2
513int Identifier::log_2() const {
514        int16_t i = aSize - 1;
515
516        while (i >= 0 && key[i] == 0) {
517                i--;
518        }
519
520        if (i < 0) {
521                return -1;
522        }
523
524        mp_limb_t j = key[i];
525        i *= GMP_LIMB_BITS;
526        while (j != 0) {
527                j >>= 1;
528                i++;
529        }
530
531        return i - 1;
532}
533
534// returns a simple hash of the key
535size_t Identifier::hash() const {
536        return (size_t) key[0];
537}
538
539// returns true, if this key is element of the interval (keyA, keyB)
540bool Identifier::isBetween(const Identifier& keyA, const Identifier& keyB) const {
541        if (isUnspec || keyA.isUnspec || keyB.isUnspec) return false;
542
543        if (*this == keyA) return false;
544        else if (keyA < keyB) return ((*this > keyA) && (*this < keyB));
545        else return ((*this > keyA) || (*this < keyB));
546}
547
548// returns true, if this key is element of the interval (keyA, keyB]
549bool Identifier::isBetweenR(const Identifier& keyA, const Identifier& keyB) const {
550        if (isUnspec || keyA.isUnspec || keyB.isUnspec) return false;
551
552        if ((keyA == keyB) && (*this == keyA)) return true;
553        else if (keyA <= keyB) return ((*this > keyA) && (*this <= keyB));
554        else return ((*this > keyA) || (*this <= keyB));
555}
556
557// returns true, if this key is element of the interval [keyA, keyB)
558bool Identifier::isBetweenL(const Identifier& keyA, const Identifier& keyB) const {
559        if (isUnspec || keyA.isUnspec || keyB.isUnspec) return false;
560
561        if ((keyA == keyB) && (*this == keyA)) return true;
562        else if (keyA <= keyB) return ((*this >= keyA) && (*this < keyB));
563        else return ((*this >= keyA) || (*this < keyB));
564}
565
566// returns true, if this key is element of the interval [keyA, keyB]
567bool Identifier::isBetweenLR(const Identifier& keyA, const Identifier& keyB) const {
568        if (isUnspec || keyA.isUnspec || keyB.isUnspec) return false;
569
570        if ((keyA == keyB) && (*this == keyA)) return true;
571        else if (keyA <= keyB) return ((*this >= keyA) && (*this <= keyB));
572        else return ((*this >= keyA) || (*this <= keyB));
573}
574
575//----------------------------------------------------------------------
576// statics and globals
577//----------------------------------------------------------------------
578
579// default console output
580std::ostream& operator<<(std::ostream& os, const Identifier& c) {
581        os << c.toString(16);
582        return os;
583}
584;
585
586// returns a key filled with bit 1
587Identifier Identifier::max() {
588        Identifier newKey;
589
590        for (uint i = 0; i < aSize; i++) {
591                newKey.key[i] = ~0;
592        }
593        newKey.isUnspec = false;
594        newKey.trim();
595
596        return newKey;
597}
598
599// generate random number
600Identifier Identifier::random() {
601        Identifier newKey = ZERO;
602
603        //as mpn_random has no seeding function
604        // we mess aroung here a little to achive some randomness
605        // using the rand function that _is_ seeded in the
606        // StartupWrapper::initSystem function
607
608        Identifier keyRandom = ZERO;
609        mpn_random(keyRandom.key, aSize);
610        Identifier keyrnd( rand() );
611        mpn_mul_1( newKey.key, keyRandom.key, aSize, *keyrnd.key );
612
613        newKey.trim();
614        return newKey;
615}
616
617Identifier Identifier::sha1(const string& input) {
618        Identifier newKey;
619        newKey.clearAddress();
620        uint8_t temp[40];
621        for (int i=0; i<40; i++) temp[i] = 0;
622        const char* c_str = input.c_str();
623
624        CSHA1 sha;
625        sha.Reset();
626        sha.Update( (uint8_t*)c_str, (uint32_t)input.size() );
627        sha.Final();
628        sha.GetHash(temp);
629        mpn_set_str(newKey.key, (const uint8_t*)temp,
630                                 (int)aSize * sizeof(mp_limb_t), 256);
631        newKey.isUnspec = false;
632        newKey.trim();
633
634        return newKey;
635}
636
637Identifier Identifier::sha1(const uint8_t* value, size_t length ) {
638        Identifier newKey;
639        uint8_t temp[40];
640        for (int i=0; i<40; i++) temp[i] = 0;
641
642        CSHA1 sha;
643        sha.Reset();
644        sha.Update( const_cast<uint8_t*>(value), (uint32_t)length );
645        sha.Final();
646        sha.GetHash(temp);
647        mpn_set_str( newKey.key, (const uint8_t*)temp, (int)aSize * sizeof(mp_limb_t), 256);
648        newKey.isUnspec = false;
649        newKey.trim();
650        return newKey;
651}
652
653// generate a key=2**exponent
654Identifier Identifier::pow2(uint exponent) {
655        Identifier newKey = ZERO;
656
657        newKey.key[exponent / GMP_LIMB_BITS] = (mp_limb_t) 1 << (exponent
658                        % GMP_LIMB_BITS);
659
660        return newKey;
661}
662
663//--------------------------------------------------------------------
664// private methods (mostly inlines)
665//--------------------------------------------------------------------
666
667// trims a key after each operation
668inline void Identifier::trim() {
669        key[array_size] = ~0;
670        key[array_size - 1] &= GMP_MSB_MASK;
671}
672
673// compares this key to any other
674int Identifier::compareTo(const Identifier& compKey) const {
675
676        if( compKey.isUnspec == false && isUnspec == false )
677                return mpn_cmp( key, compKey.key, aSize );
678        else if( compKey.isUnspec == true && isUnspec == true )
679                return 0;
680        else
681                return -1;
682}
683
684}} // namespace ariba, common
Note: See TracBrowser for help on using the repository browser.