| 1 | // [Licence]
|
---|
| 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 | // [Licence]
|
---|
| 38 |
|
---|
| 39 | #include "Identifier.h"
|
---|
| 40 | #include "ariba/utility/misc/sha1.h"
|
---|
| 41 |
|
---|
| 42 | namespace ariba {
|
---|
| 43 | namespace utility {
|
---|
| 44 |
|
---|
| 45 | uint Identifier::keyLength = MAX_KEYLENGTH;
|
---|
| 46 |
|
---|
| 47 | uint Identifier::aSize = Identifier::keyLength / (8 * sizeof(mp_limb_t))
|
---|
| 48 | + (Identifier::keyLength % (8 * sizeof(mp_limb_t)) != 0 ? 1 : 0);
|
---|
| 49 |
|
---|
| 50 | mp_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 */
|
---|
| 55 | vsznDefault(Identifier);
|
---|
| 56 | use_logging_cpp( Identifier );
|
---|
| 57 |
|
---|
| 58 | //--------------------------------------------------------------------
|
---|
| 59 | // constants
|
---|
| 60 | //--------------------------------------------------------------------
|
---|
| 61 |
|
---|
| 62 | // predefined keys
|
---|
| 63 | const Identifier Identifier::UNSPECIFIED_KEY;
|
---|
| 64 | const Identifier Identifier::ZERO((uint32_t) 0);
|
---|
| 65 | const Identifier Identifier::ONE((uint32_t) 1);
|
---|
| 66 |
|
---|
| 67 | // hex crap
|
---|
| 68 | const char* HEX = "0123456789abcdef";
|
---|
| 69 | gmp_randstate_t randstate;
|
---|
| 70 |
|
---|
| 71 | void Identifier::clearAddress() {
|
---|
| 72 | for (int i = 0; i < array_size; i++)
|
---|
| 73 | key[i] = 0;
|
---|
| 74 | isUnspec = false;
|
---|
| 75 | trim();
|
---|
| 76 | }
|
---|
| 77 |
|
---|
| 78 | bool Identifier::setAddress(string address) {
|
---|
| 79 | // TODO
|
---|
| 80 | }
|
---|
| 81 |
|
---|
| 82 | string Identifier::getAddress() const {
|
---|
| 83 | return toString();
|
---|
| 84 | }
|
---|
| 85 |
|
---|
| 86 | //--------------------------------------------------------------------
|
---|
| 87 | // construction and destruction
|
---|
| 88 | //--------------------------------------------------------------------
|
---|
| 89 |
|
---|
| 90 | // default construction: create a unspecified node key
|
---|
| 91 | Identifier::Identifier() {
|
---|
| 92 | seed();
|
---|
| 93 | isUnspec = true;
|
---|
| 94 | trim();
|
---|
| 95 | }
|
---|
| 96 |
|
---|
| 97 | // create a key out of an normal integer
|
---|
| 98 | Identifier::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
|
---|
| 106 | Identifier::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
|
---|
| 117 | Identifier::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
|
---|
| 148 | Identifier::Identifier(const Identifier& rhs) {
|
---|
| 149 | seed();
|
---|
| 150 | (*this) = rhs;
|
---|
| 151 | }
|
---|
| 152 |
|
---|
| 153 | // default destructur
|
---|
| 154 | Identifier::~Identifier() {
|
---|
| 155 | }
|
---|
| 156 |
|
---|
| 157 | void 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 |
|
---|
| 171 | void 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
|
---|
| 190 | uint Identifier::getLength() {
|
---|
| 191 | return Identifier::keyLength;
|
---|
| 192 | }
|
---|
| 193 |
|
---|
| 194 | bool Identifier::isUnspecified() const {
|
---|
| 195 | return isUnspec;
|
---|
| 196 | }
|
---|
| 197 |
|
---|
| 198 | std::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
|
---|
| 247 | Identifier& 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
|
---|
| 254 | Identifier& Identifier::operator--() {
|
---|
| 255 | return (*this -= ONE);
|
---|
| 256 | }
|
---|
| 257 |
|
---|
| 258 | // sub one postfix operator
|
---|
| 259 | Identifier Identifier::operator--(int) {
|
---|
| 260 | Identifier clone = *this;
|
---|
| 261 | *this -= ONE;
|
---|
| 262 | return clone;
|
---|
| 263 | }
|
---|
| 264 |
|
---|
| 265 | // add one prefix operator
|
---|
| 266 | Identifier& Identifier::operator++() {
|
---|
| 267 | return (*this += ONE);
|
---|
| 268 | }
|
---|
| 269 |
|
---|
| 270 | // sub one postfix operator
|
---|
| 271 | Identifier Identifier::operator++(int) {
|
---|
| 272 | Identifier clone = *this;
|
---|
| 273 | *this += ONE;
|
---|
| 274 | return clone;
|
---|
| 275 | }
|
---|
| 276 |
|
---|
| 277 | // add assign operator
|
---|
| 278 | Identifier& 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
|
---|
| 286 | Identifier& 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
|
---|
| 294 | Identifier Identifier::operator+(const Identifier& rhs) const {
|
---|
| 295 | Identifier result = *this;
|
---|
| 296 | result += rhs;
|
---|
| 297 | return result;
|
---|
| 298 | }
|
---|
| 299 |
|
---|
| 300 | // sub operator
|
---|
| 301 | Identifier Identifier::operator-(const Identifier& rhs) const {
|
---|
| 302 | Identifier result = *this;
|
---|
| 303 | result -= rhs;
|
---|
| 304 | return result;
|
---|
| 305 | }
|
---|
| 306 |
|
---|
| 307 | // compare operators
|
---|
| 308 | bool Identifier::operator<(const Identifier& compKey) const {
|
---|
| 309 | return compareTo(compKey) < 0;
|
---|
| 310 | }
|
---|
| 311 | bool Identifier::operator>(const Identifier& compKey) const {
|
---|
| 312 | return compareTo(compKey) > 0;
|
---|
| 313 | }
|
---|
| 314 | bool Identifier::operator<=(const Identifier& compKey) const {
|
---|
| 315 | return compareTo(compKey) <= 0;
|
---|
| 316 | }
|
---|
| 317 | bool Identifier::operator>=(const Identifier& compKey) const {
|
---|
| 318 | return compareTo(compKey) >= 0;
|
---|
| 319 | }
|
---|
| 320 | bool Identifier::operator==(const Identifier& compKey) const {
|
---|
| 321 | return compareTo(compKey) == 0;
|
---|
| 322 | }
|
---|
| 323 | bool Identifier::operator!=(const Identifier& compKey) const {
|
---|
| 324 | return compareTo(compKey) != 0;
|
---|
| 325 | }
|
---|
| 326 |
|
---|
| 327 | // bitwise xor
|
---|
| 328 | Identifier Identifier::operator^(const Identifier& rhs) const {
|
---|
| 329 | Identifier result = *this;
|
---|
| 330 | for (uint i = 0; i < aSize; i++) {
|
---|
| 331 | result.key[i] ^= rhs.key[i];
|
---|
| 332 | }
|
---|
| 333 |
|
---|
| 334 | return result;
|
---|
| 335 | }
|
---|
| 336 |
|
---|
| 337 | // bitwise or
|
---|
| 338 | Identifier Identifier::operator|(const Identifier& rhs) const {
|
---|
| 339 | Identifier result = *this;
|
---|
| 340 | for (uint i = 0; i < aSize; i++) {
|
---|
| 341 | result.key[i] |= rhs.key[i];
|
---|
| 342 | }
|
---|
| 343 |
|
---|
| 344 | return result;
|
---|
| 345 | }
|
---|
| 346 |
|
---|
| 347 | // bitwise and
|
---|
| 348 | Identifier Identifier::operator&(const Identifier& rhs) const {
|
---|
| 349 | Identifier result = *this;
|
---|
| 350 | for (uint i = 0; i < aSize; i++) {
|
---|
| 351 | result.key[i] &= rhs.key[i];
|
---|
| 352 | }
|
---|
| 353 |
|
---|
| 354 | return result;
|
---|
| 355 | }
|
---|
| 356 |
|
---|
| 357 | // complement
|
---|
| 358 | Identifier Identifier::operator~() const {
|
---|
| 359 | Identifier result = *this;
|
---|
| 360 | for (uint i = 0; i < aSize; i++) {
|
---|
| 361 | result.key[i] = ~key[i];
|
---|
| 362 | }
|
---|
| 363 | result.trim();
|
---|
| 364 |
|
---|
| 365 | return result;
|
---|
| 366 | }
|
---|
| 367 |
|
---|
| 368 | // bitwise shift right
|
---|
| 369 | Identifier Identifier::operator>>(uint num) const {
|
---|
| 370 | Identifier result = ZERO;
|
---|
| 371 | int i = num / GMP_LIMB_BITS;
|
---|
| 372 |
|
---|
| 373 | num %= GMP_LIMB_BITS;
|
---|
| 374 |
|
---|
| 375 | if (i >= (int) aSize) return result;
|
---|
| 376 |
|
---|
| 377 | for (int j = 0; j < (int) aSize - i; j++) {
|
---|
| 378 | result.key[j] = key[j + i];
|
---|
| 379 | }
|
---|
| 380 | mpn_rshift(result.key, result.key, aSize, num);
|
---|
| 381 | result.isUnspec = false;
|
---|
| 382 | result.trim();
|
---|
| 383 |
|
---|
| 384 | return result;
|
---|
| 385 | }
|
---|
| 386 |
|
---|
| 387 | // bitwise shift left
|
---|
| 388 | Identifier Identifier::operator<<(uint num) const {
|
---|
| 389 | Identifier result = ZERO;
|
---|
| 390 | int i = num / GMP_LIMB_BITS;
|
---|
| 391 |
|
---|
| 392 | num %= GMP_LIMB_BITS;
|
---|
| 393 |
|
---|
| 394 | if (i >= (int) aSize) return result;
|
---|
| 395 |
|
---|
| 396 | for (int j = 0; j < (int) aSize - i; j++) {
|
---|
| 397 | result.key[j + i] = key[j];
|
---|
| 398 | }
|
---|
| 399 | mpn_lshift(result.key, result.key, aSize, num);
|
---|
| 400 | result.isUnspec = false;
|
---|
| 401 | result.trim();
|
---|
| 402 |
|
---|
| 403 | return result;
|
---|
| 404 | }
|
---|
| 405 |
|
---|
| 406 | // get bit
|
---|
| 407 | IdentifierBit Identifier::operator[](uint n) {
|
---|
| 408 | return IdentifierBit(get(n, 1), n, this);
|
---|
| 409 | }
|
---|
| 410 |
|
---|
| 411 | Identifier& Identifier::setBitAt(uint pos, bool value) {
|
---|
| 412 | mp_limb_t digit = 1;
|
---|
| 413 | digit = digit << (pos % GMP_LIMB_BITS);
|
---|
| 414 |
|
---|
| 415 | if (value) {
|
---|
| 416 | key[pos / GMP_LIMB_BITS] |= digit;
|
---|
| 417 | } else {
|
---|
| 418 | //key[pos / GMP_LIMB_BITS] = key[pos / GMP_LIMB_BITS] & ~digit;
|
---|
| 419 | key[pos / GMP_LIMB_BITS] &= ~digit;
|
---|
| 420 | }
|
---|
| 421 |
|
---|
| 422 | return *this;
|
---|
| 423 | }
|
---|
| 424 | ;
|
---|
| 425 |
|
---|
| 426 | //--------------------------------------------------------------------
|
---|
| 427 | // additional math
|
---|
| 428 | //--------------------------------------------------------------------
|
---|
| 429 |
|
---|
| 430 | // returns a sub integer
|
---|
| 431 | uint32_t Identifier::get(uint p, uint n) const {
|
---|
| 432 | int i = p / GMP_LIMB_BITS, // index of starting bit
|
---|
| 433 | f = p % GMP_LIMB_BITS, // position of starting bit
|
---|
| 434 | f2 = f + n - GMP_LIMB_BITS; // how many bits to take from next index
|
---|
| 435 |
|
---|
| 436 | if (p + n > Identifier::keyLength) {
|
---|
| 437 | logging_error( "Identifier::get: Invalid range (index too large!)" );
|
---|
| 438 | return 0;
|
---|
| 439 | }
|
---|
| 440 |
|
---|
| 441 | return ((key[i] >> f) | // get the bits of key[i]
|
---|
| 442 | (f2 > 0 ? (key[i + 1] << (GMP_LIMB_BITS - f)) : 0)) & // the extra bits from key[i+1]
|
---|
| 443 | (((uint32_t) (~0)) >> (GMP_LIMB_BITS - n)); // delete unused bits
|
---|
| 444 | }
|
---|
| 445 |
|
---|
| 446 | // fill suffix with random bits
|
---|
| 447 | Identifier Identifier::randomSuffix(uint pos) const {
|
---|
| 448 | Identifier newKey = *this;
|
---|
| 449 | int i = pos / GMP_LIMB_BITS, j = pos % GMP_LIMB_BITS;
|
---|
| 450 | mp_limb_t m = ((mp_limb_t) 1 << j) - 1;
|
---|
| 451 | mp_limb_t rnd;
|
---|
| 452 |
|
---|
| 453 | mpn_random(&rnd, 1);
|
---|
| 454 | newKey.key[i] &= ~m;
|
---|
| 455 | newKey.key[i] |= (rnd & m);
|
---|
| 456 | mpn_random(newKey.key, i);
|
---|
| 457 | newKey.trim();
|
---|
| 458 |
|
---|
| 459 | return newKey;
|
---|
| 460 | }
|
---|
| 461 |
|
---|
| 462 | // fill prefix with random bits
|
---|
| 463 | Identifier Identifier::randomPrefix(uint pos) const {
|
---|
| 464 | Identifier newKey = *this;
|
---|
| 465 | int i = pos / GMP_LIMB_BITS, j = pos % GMP_LIMB_BITS;
|
---|
| 466 | mp_limb_t m = ((mp_limb_t) 1 << j) - 1;
|
---|
| 467 | mp_limb_t rnd;
|
---|
| 468 |
|
---|
| 469 | mpn_random(&rnd, 1);
|
---|
| 470 |
|
---|
| 471 | newKey.key[i] &= m;
|
---|
| 472 | newKey.key[i] |= (rnd & ~m);
|
---|
| 473 | for (int k = aSize - 1; k != i; k--) {
|
---|
| 474 | mpn_random(&newKey.key[k], 1);
|
---|
| 475 | }
|
---|
| 476 | newKey.trim();
|
---|
| 477 |
|
---|
| 478 | return newKey;
|
---|
| 479 | }
|
---|
| 480 |
|
---|
| 481 | // calculate shared prefix length
|
---|
| 482 | uint Identifier::sharedPrefixLength(const Identifier& compKey) const {
|
---|
| 483 | if (compareTo(compKey) == 0) return keyLength;
|
---|
| 484 |
|
---|
| 485 | uint length = 0;
|
---|
| 486 | int i;
|
---|
| 487 | uint j;
|
---|
| 488 | bool msb = true;
|
---|
| 489 |
|
---|
| 490 | // count equal limbs first:
|
---|
| 491 | for (i = aSize - 1; i >= 0; --i) {
|
---|
| 492 | if (this->key[i] != compKey.key[i]) {
|
---|
| 493 | // XOR first differing limb for easy counting of the bits:
|
---|
| 494 | mp_limb_t d = this->key[i] ^ compKey.key[i];
|
---|
| 495 | if (msb) d <<= (GMP_LIMB_BITS - (keyLength % GMP_LIMB_BITS));
|
---|
| 496 | for (j = GMP_LIMB_BITS - 1; d >>= 1; --j)
|
---|
| 497 | ;
|
---|
| 498 | length += j;
|
---|
| 499 | break;
|
---|
| 500 | }
|
---|
| 501 | length += GMP_LIMB_BITS;
|
---|
| 502 | msb = false;
|
---|
| 503 | }
|
---|
| 504 |
|
---|
| 505 | return length;
|
---|
| 506 | }
|
---|
| 507 |
|
---|
| 508 | // calculate log of base 2
|
---|
| 509 | int Identifier::log_2() const {
|
---|
| 510 | int16_t i = aSize - 1;
|
---|
| 511 |
|
---|
| 512 | while (i >= 0 && key[i] == 0) {
|
---|
| 513 | i--;
|
---|
| 514 | }
|
---|
| 515 |
|
---|
| 516 | if (i < 0) {
|
---|
| 517 | return -1;
|
---|
| 518 | }
|
---|
| 519 |
|
---|
| 520 | mp_limb_t j = key[i];
|
---|
| 521 | i *= GMP_LIMB_BITS;
|
---|
| 522 | while (j != 0) {
|
---|
| 523 | j >>= 1;
|
---|
| 524 | i++;
|
---|
| 525 | }
|
---|
| 526 |
|
---|
| 527 | return i - 1;
|
---|
| 528 | }
|
---|
| 529 |
|
---|
| 530 | // returns a simple hash of the key
|
---|
| 531 | size_t Identifier::hash() const {
|
---|
| 532 | return (size_t) key[0];
|
---|
| 533 | }
|
---|
| 534 |
|
---|
| 535 | // returns true, if this key is element of the interval (keyA, keyB)
|
---|
| 536 | bool Identifier::isBetween(const Identifier& keyA, const Identifier& keyB) const {
|
---|
| 537 | if (isUnspec || keyA.isUnspec || keyB.isUnspec) return false;
|
---|
| 538 |
|
---|
| 539 | if (*this == keyA) return false;
|
---|
| 540 | else if (keyA < keyB) return ((*this > keyA) && (*this < keyB));
|
---|
| 541 | else return ((*this > keyA) || (*this < keyB));
|
---|
| 542 | }
|
---|
| 543 |
|
---|
| 544 | // returns true, if this key is element of the interval (keyA, keyB]
|
---|
| 545 | bool Identifier::isBetweenR(const Identifier& keyA, const Identifier& keyB) const {
|
---|
| 546 | if (isUnspec || keyA.isUnspec || keyB.isUnspec) return false;
|
---|
| 547 |
|
---|
| 548 | if ((keyA == keyB) && (*this == keyA)) return true;
|
---|
| 549 | else if (keyA <= keyB) return ((*this > keyA) && (*this <= keyB));
|
---|
| 550 | else return ((*this > keyA) || (*this <= keyB));
|
---|
| 551 | }
|
---|
| 552 |
|
---|
| 553 | // returns true, if this key is element of the interval [keyA, keyB)
|
---|
| 554 | bool Identifier::isBetweenL(const Identifier& keyA, const Identifier& keyB) const {
|
---|
| 555 | if (isUnspec || keyA.isUnspec || keyB.isUnspec) return false;
|
---|
| 556 |
|
---|
| 557 | if ((keyA == keyB) && (*this == keyA)) return true;
|
---|
| 558 | else if (keyA <= keyB) return ((*this >= keyA) && (*this < keyB));
|
---|
| 559 | else return ((*this >= keyA) || (*this < keyB));
|
---|
| 560 | }
|
---|
| 561 |
|
---|
| 562 | // returns true, if this key is element of the interval [keyA, keyB]
|
---|
| 563 | bool Identifier::isBetweenLR(const Identifier& keyA, const Identifier& keyB) const {
|
---|
| 564 | if (isUnspec || keyA.isUnspec || keyB.isUnspec) return false;
|
---|
| 565 |
|
---|
| 566 | if ((keyA == keyB) && (*this == keyA)) return true;
|
---|
| 567 | else if (keyA <= keyB) return ((*this >= keyA) && (*this <= keyB));
|
---|
| 568 | else return ((*this >= keyA) || (*this <= keyB));
|
---|
| 569 | }
|
---|
| 570 |
|
---|
| 571 | //----------------------------------------------------------------------
|
---|
| 572 | // statics and globals
|
---|
| 573 | //----------------------------------------------------------------------
|
---|
| 574 |
|
---|
| 575 | // default console output
|
---|
| 576 | std::ostream& operator<<(std::ostream& os, const Identifier& c) {
|
---|
| 577 | os << c.toString(16);
|
---|
| 578 | return os;
|
---|
| 579 | }
|
---|
| 580 | ;
|
---|
| 581 |
|
---|
| 582 | // returns a key filled with bit 1
|
---|
| 583 | Identifier Identifier::max() {
|
---|
| 584 | Identifier newKey;
|
---|
| 585 |
|
---|
| 586 | for (uint i = 0; i < aSize; i++) {
|
---|
| 587 | newKey.key[i] = ~0;
|
---|
| 588 | }
|
---|
| 589 | newKey.isUnspec = false;
|
---|
| 590 | newKey.trim();
|
---|
| 591 |
|
---|
| 592 | return newKey;
|
---|
| 593 | }
|
---|
| 594 |
|
---|
| 595 | // generate random number
|
---|
| 596 | Identifier Identifier::random() {
|
---|
| 597 | Identifier newKey = ZERO;
|
---|
| 598 |
|
---|
| 599 | //as mpn_random has no seeding function
|
---|
| 600 | // we mess aroung here a little to achive randomness
|
---|
| 601 | Identifier keyRandom = ZERO;
|
---|
| 602 | mpn_random(keyRandom.key, aSize);
|
---|
| 603 | Identifier keyTime( time(NULL) );
|
---|
| 604 | mpn_mul_1( newKey.key, keyRandom.key, aSize, *keyTime.key );
|
---|
| 605 |
|
---|
| 606 | newKey.trim();
|
---|
| 607 | return newKey;
|
---|
| 608 | }
|
---|
| 609 |
|
---|
| 610 |
|
---|
| 611 | // README: due to some problems with serialization the keylength
|
---|
| 612 | // was changed to 192 bit! As none of the hashing functions
|
---|
| 613 | // can provide 160 bit output, and we currently don't use any
|
---|
| 614 | // hashing for identifiers in the demo at all ... this is all commented out!!
|
---|
| 615 |
|
---|
| 616 |
|
---|
| 617 | // generate sha1 hash
|
---|
| 618 | Identifier Identifier::sha1(const string& input) {
|
---|
| 619 | Identifier newKey;
|
---|
| 620 | uint8_t temp[20];
|
---|
| 621 | const char* c_str = input.c_str();
|
---|
| 622 |
|
---|
| 623 | CSHA1 sha;
|
---|
| 624 | sha.Reset();
|
---|
| 625 | sha.Update( (uint8_t*)c_str, (uint32_t)input.size() );
|
---|
| 626 | sha.Final();
|
---|
| 627 | sha.GetHash(temp);
|
---|
| 628 | mpn_set_str(newKey.key, (const uint8_t*)temp,
|
---|
| 629 | (int)aSize * sizeof(mp_limb_t), 256);
|
---|
| 630 | newKey.isUnspec = false;
|
---|
| 631 | newKey.trim();
|
---|
| 632 |
|
---|
| 633 | return newKey;
|
---|
| 634 | }
|
---|
| 635 |
|
---|
| 636 | Identifier Identifier::sha1(const uint8_t* value, size_t length ) {
|
---|
| 637 | Identifier newKey;
|
---|
| 638 | uint8_t temp[20];
|
---|
| 639 |
|
---|
| 640 | CSHA1 sha;
|
---|
| 641 | sha.Reset();
|
---|
| 642 | sha.Update( const_cast<uint8_t*>(value), (uint32_t)length );
|
---|
| 643 | sha.Final();
|
---|
| 644 | sha.GetHash(temp);
|
---|
| 645 | mpn_set_str( newKey.key, (const uint8_t*)temp, (int)aSize * sizeof(mp_limb_t), 256);
|
---|
| 646 | newKey.isUnspec = false;
|
---|
| 647 | newKey.trim();
|
---|
| 648 | return newKey;
|
---|
| 649 | }
|
---|
| 650 |
|
---|
| 651 |
|
---|
| 652 |
|
---|
| 653 | // generate a key=2**exponent
|
---|
| 654 | Identifier 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
|
---|
| 668 | inline 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
|
---|
| 674 | int 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
|
---|