source: source/ariba/utility/types/Identifier.h@ 5688

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

zurück auf 8bit, test

File size: 14.8 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#ifndef IDENTIFIER_H_
40#define IDENTIFIER_H_
41
42#include <memory>
43#include <string>
44#include <cassert>
45#include <iostream>
46#include <gmp.h>
47#include <boost/cstdint.hpp>
48#include "ariba/utility/logging/Logging.h"
49#include "ariba/utility/types/Address.h"
50#include "ariba/utility/serialization.h"
51
52/**< maximum length of the key */
53#define MAX_KEYLENGTH 192
54
55namespace ariba {
56namespace utility {
57
58using_serialization;
59
60class IdentifierBit;
61
62/**
63 * An abstract address class for identifier.<br/>
64 *
65 * This class is the base for all identifier classes.
66 */
67class Identifier: public Address {
68 VSERIALIZEABLE;
69 use_logging_h( Identifier );
70public:
71
72 //-------------------------------------------------------------------------
73 // virtual function from Address
74 //-------------------------------------------------------------------------
75
76 virtual void clearAddress();
77 virtual bool setAddress(string address);
78 virtual string getAddress() const;
79
80 //-------------------------------------------------------------------------
81 // constants
82 //-------------------------------------------------------------------------
83
84 static const Identifier UNSPECIFIED_KEY; /**< Identifier without defined key */
85 static const Identifier ZERO; /**< Identifier with key initialized as 0 */
86 static const Identifier ONE; /**< Identifier with key initialized as 1 */
87
88 //-------------------------------------------------------------------------
89 // construction and destruction
90 //-------------------------------------------------------------------------
91
92 /**
93 * Default constructor
94 *
95 * Contructs an unspecified overlay key
96 */
97 Identifier();
98
99 /**
100 * Constructs an overlay key initialized with a common integer
101 *
102 * @param num The integer to initialize this key with
103 */
104 Identifier(uint32_t num);
105
106 /**
107 * Constructs a key out of a buffer
108 * @param buffer Source buffer
109 * @param size Buffer size (in bytes)
110 */
111 Identifier(const unsigned char* buffer, uint size);
112
113 /**
114 * Constructs a key out of a string number.
115 */
116 Identifier(const std::string& str, uint base = 16);
117
118 /**
119 * Copy constructor.
120 *
121 * @param rhs The key to copy.
122 */
123 Identifier(const Identifier& rhs);
124
125 /**
126 * Default destructor.
127 *
128 * Does nothing ATM.
129 */
130 virtual ~Identifier();
131
132 //-------------------------------------------------------------------------
133 // string representations & node key attributes
134 //-------------------------------------------------------------------------
135
136 /**
137 * Returns a string representation of this key
138 *
139 * @return String representation of this key
140 */
141 virtual std::string toString(uint base = 16) const;
142
143 /**
144 * Common stdc++ console output method
145 */
146 friend std::ostream& operator<<(std::ostream& os, const Identifier& c);
147
148 /**
149 * Returns true, if the key is unspecified
150 *
151 * @return Returns true, if key is unspecified
152 */
153 bool isUnspecified() const;
154
155 //-------------------------------------------------------------------------
156 // operators
157 //-------------------------------------------------------------------------
158
159 /**
160 * compares this to a given Identifier
161 *
162 * @param compKey the the Identifier to compare this to
163 * @return true if compKey->key is smaller than this->key, else false
164 */
165 bool operator<(const Identifier& compKey) const;
166
167 /**
168 * compares this to a given Identifier
169 *
170 * @param compKey the the Identifier to compare this to
171 * @return true if compKey->key is greater than this->key, else false
172 */
173 bool operator>(const Identifier& compKey) const;
174
175 /**
176 * compares this to a given Identifier
177 *
178 * @param compKey the the Identifier to compare this to
179 * @return true if compKey->key is smaller than or equal to this->key, else false
180 */
181 bool operator<=(const Identifier& compKey) const;
182
183 /**
184 * compares this to a given Identifier
185 *
186 * @param compKey the the Identifier to compare this to
187 * @return true if compKey->key is greater than or equal to this->key, else false
188 */
189 bool operator>=(const Identifier& compKey) const;
190
191 /**
192 * compares this to a given Identifier
193 *
194 * @param compKey the the Identifier to compare this to
195 * @return true if compKey->key is equal to this->key, else false
196 */
197 bool operator==(const Identifier& compKey) const;
198
199 /**
200 * compares this to a given Identifier
201 *
202 * @param compKey the the Identifier to compare this to
203 * @return true if compKey->key is not equal to this->key, else false
204 */
205 bool operator!=(const Identifier& compKey) const;
206
207 /**
208 * Unifies all compare operations in one method
209 *
210 * @param compKey key to compare with
211 * @return int -1 if smaller, 0 if equal, 1 if greater
212 */
213 int compareTo(const Identifier& compKey) const;
214
215 /**
216 * assigns Identifier of rhs to this->key
217 *
218 * @param rhs the Identifier with the defined key
219 * @return this Identifier object
220 */
221 Identifier& operator=(const Identifier& rhs);
222
223 /**
224 * substracts 1 from this->key
225 *
226 * @return this Identifier object
227 */
228 Identifier& operator--();
229
230 /**
231 * adds 1 to this->key
232 *
233 * @return this Identifier object
234 */
235 Identifier& operator++();
236
237 /**
238 * adds rhs->key to this->key
239 *
240 * @param rhs the Identifier with the defined key
241 * @return this Identifier object
242 */
243 Identifier& operator+=(const Identifier& rhs);
244
245 /**
246 * substracts rhs->key from this->key
247 *
248 * @param rhs the Identifier with the defined key
249 * @return this Identifier object
250 */
251 Identifier& operator-=(const Identifier& rhs);
252
253 /**
254 * adds rhs->key to this->key
255 *
256 * @param rhs the Identifier with the defined key
257 * @return this Identifier object
258 */
259 Identifier operator+(const Identifier& rhs) const;
260
261 /**
262 * substracts rhs->key from this->key
263 *
264 * @param rhs the Identifier with the defined key
265 * @return this Identifier object
266 */
267 Identifier operator-(const Identifier& rhs) const;
268
269 /**
270 * substracts 1 from this->key
271 *
272 * @return this Identifier object
273 */
274 Identifier operator--(int);
275
276 /**
277 * adds 1 to this->key
278 *
279 * @return this Identifier object
280 */
281 Identifier operator++(int);
282
283 /**
284 * bitwise shift right
285 *
286 * @param num number of bits to shift
287 * @return this Identifier object
288 */
289 Identifier operator>>(uint num) const;
290
291 /**
292 * bitwise shift left
293 *
294 * @param num number of bits to shift
295 * @return this Identifier object
296 */
297 Identifier operator<<(uint num) const;
298
299 /**
300 * bitwise AND of rhs->key and this->key
301 *
302 * @param rhs the Identifier AND is calculated with
303 * @return this Identifier object
304 */
305 Identifier operator&(const Identifier& rhs) const;
306
307 /**
308 * bitwise OR of rhs->key and this->key
309 *
310 * @param rhs the Identifier OR is calculated with
311 * @return this Identifier object
312 */
313 Identifier operator|(const Identifier& rhs) const;
314
315 /**
316 * bitwise XOR of rhs->key and this->key
317 *
318 * @param rhs the Identifier XOR is calculated with
319 * @return this Identifier object
320 */
321 Identifier operator^(const Identifier& rhs) const;
322
323 /**
324 * bitwise NOT of this->key
325 *
326 * @return this Identifier object
327 */
328 Identifier operator~() const;
329
330 /**
331 * returns the n-th bit of this->key
332 *
333 * @param n the position of the returned bit
334 * @return the bit on position n in this->key
335 */
336 IdentifierBit operator[](uint n);
337
338 /**
339 * sets a bit of this->key
340 *
341 * @param pos the position of the bit to set
342 * @param value new value for bit at position pos
343 * @return *this
344 */
345 Identifier& setBitAt(uint pos, bool value);
346
347 //-------------------------------------------------------------------------
348 // additional math
349 //-------------------------------------------------------------------------
350
351 /**
352 * Returns a sub integer at position p with n-bits. p is counted starting
353 * from the least significant bit of the key as bit 0. Bit p of the key
354 * becomes bit 0 of the returned integer.
355 *
356 * @param p the position of the sub-integer
357 * @param n the number of bits to be returned (max.32)
358 * @return The sub-integer.
359 */
360 uint32_t get(uint p, uint n) const;
361
362 /**
363 * Returns a hash value for the key
364 *
365 * @return size_t The hash value
366 */
367 size_t hash() const;
368
369 /**
370 * Returns the position of the msb in this key, which represents
371 * just the logarithm to base 2.
372 *
373 * @return The logarithm to base 2 of this key.
374 */
375 int log_2() const;
376
377 /**
378 * Fills the suffix starting at pos with random bits to lsb.
379 *
380 * @param pos
381 * @return Identifier
382 */
383 Identifier randomSuffix(uint pos) const;
384
385 /**
386 * Fills the prefix starting at pos with random bits to msb.
387 *
388 * @param pos
389 * @return Identifier
390 */
391 Identifier randomPrefix(uint pos) const;
392
393 /**
394 * Calculates the number of equal bits from the left with another
395 * Key (shared prefix length)
396 *
397 * @param compKey the Key to compare with
398 * @return length of shared prefix
399 */
400 uint sharedPrefixLength(const Identifier& compKey) const;
401
402 /**
403 * Returns true, if this key is element of the interval (keyA, keyB)
404 * on the ring.
405 *
406 * @param keyA The left border of the interval
407 * @param keyB The right border of the interval
408 * @return True, if the key is element of the interval (keyA, keyB)
409 */
410 bool isBetween(const Identifier& keyA, const Identifier& keyB) const;
411
412 /**
413 * Returns true, if this key is element of the interval (keyA, keyB]
414 * on the ring.
415 *
416 * @param keyA The left border of the interval
417 * @param keyB The right border of the interval
418 * @return True, if the key is element of the interval (keyA, keyB]
419 */
420 bool isBetweenR(const Identifier& keyA, const Identifier& keyB) const;
421
422 /**
423 * Returns true, if this key is element of the interval [keyA, keyB)
424 * on the ring.
425 *
426 * @param keyA The left border of the interval
427 * @param keyB The right border of the interval
428 * @return True, if the key is element of the interval [keyA, keyB)
429 */
430 bool isBetweenL(const Identifier& keyA, const Identifier& keyB) const;
431
432 /**
433 * Returns true, if this key is element of the interval [keyA, keyB]
434 * on the ring.
435 *
436 * @param keyA The left border of the interval
437 * @param keyB The right border of the interval
438 * @return True, if the key is element of the interval [keyA, keyB]
439 */
440 bool isBetweenLR(const Identifier& keyA, const Identifier& keyB) const;
441
442 //-------------------------------------------------------------------------
443 // static methods
444 //-------------------------------------------------------------------------
445
446 /**
447 * Set the length of an Identifier
448 *
449 * @param length keylength in bits
450 */
451 static void setKeyLength(uint length);
452
453 /**
454 * Returns the length in number of bits.
455 *
456 * @return The length in number of bits.
457 */
458 static uint getLength();
459
460 /**
461 * Returns a random key.
462 *
463 * @return A random key.
464 */
465 static Identifier random();
466
467 /**
468 * Returns the maximum key, i.e. a key filled with bit 1
469 *
470 * @return The maximum key, i.e. a key filled with bit 1
471 */
472 static Identifier max();
473
474
475 // README: due to some problems with serialization the keylength
476 // was changed to 192 bit! As none of the hashing functions
477 // can provide 192 bit output, and we currently don't use any
478 // hashing for identifiers in the demo at all ... this is all commented out!!
479 /**
480 * Returns a key with the SHA1 cryptographic hash of a
481 * string
482 *
483 * @param value A string value.
484 * @return SHA1 of value
485 */
486 static Identifier sha1(const string& value);
487
488 static Identifier sha1(const uint8_t* value, size_t length );
489
490 /**
491 * Returns a key 2^exponent.
492 *
493 * @param exponent The exponent.
494 * @return Key=2^exponent.
495 */
496 static Identifier pow2(uint exponent);
497
498private:
499 // private constants
500
501 static uint keyLength; /**< actual length of the key */
502 static uint aSize; /**< number of needed machine words to hold the key*/
503 static mp_limb_t GMP_MSB_MASK; /**< bits to fill up if key does not
504 exactly fit in one or more machine words */
505
506 // private fields
507 bool isUnspec; /**< is this->key unspecified? */
508
509 void seed();
510
511 static const size_t array_size = MAX_KEYLENGTH / (8 * sizeof(mp_limb_t))
512 + (MAX_KEYLENGTH % (8 * sizeof(mp_limb_t)) != 0 ? 1 : 0);
513
514 /** the overlay key this object represents */
515 mp_limb_t key[array_size + 1];
516
517 // private "helper" methods
518 /**
519 * trims key after key operations
520 */
521 void trim();
522
523 /**
524 * set this->key to 0 and isUnspec to false
525 */
526 void clear();
527};
528
529/**
530 * An auxiliary class for single bits in OverlayKey
531 *
532 * Allows statements like "key[n] = true"
533 */
534class IdentifierBit {
535public:
536
537 IdentifierBit(bool value, uint pos, Identifier* key) :
538 bit(value), pos(pos), key(key) {
539 }
540
541 /** Converts to a boolean value */
542 inline operator bool() {
543 return bit;
544 }
545
546 /** Sets the corresponding bit to a boolean value
547 * @param value value to set to
548 */
549 inline IdentifierBit& operator=(bool value) {
550 key->setBitAt(pos, value);
551 return *this;
552 }
553
554 inline IdentifierBit& operator^=(bool value) {
555 key->setBitAt(pos, (*key)[pos] ^ value);
556 return *this;
557 }
558
559private:
560
561 bool bit;
562 uint pos;
563 Identifier* key;
564};
565
566}
567} // namespace ariba, common
568
569/* serializers */
570sznBeginDefault( ariba::utility::Identifier, X ) {
571
572 // calculate length of key
573 uint16_t len = array_size*sizeof(mp_limb_t);
574 uint8_t unspec = isUnspec;
575
576 // only serialize the lower 16 bits of keyLength
577 X && unspec && len;
578
579 // serialize the identifier
580 for (int i=array_size-1; i>=0; i--) X && key[i];
581
582 // when deserializing set unspec flag
583 if (X.isDeserializer()){
584 isUnspec = unspec;
585 }
586
587} sznEnd();
588
589#endif /* IDENTIFIER_H_ */
Note: See TracBrowser for help on using the repository browser.