1 module tagion.hibon.BigNumber; 2 3 protected import std.bigint; 4 5 //import std.bigint; 6 import std.format; 7 import std.internal.math.biguintnoasm : BigDigit; 8 9 //import std.conv : emplace; 10 import std.range.primitives; 11 import std.system : Endian; 12 import std.traits; 13 import std.typecons : Tuple; 14 import std.base64; 15 16 //import std.stdio; 17 18 import tagion.hibon.HiBONException : check; 19 20 /++ 21 BigNumber used in the HiBON format 22 It is a wrapper of the std.bigint 23 +/ 24 25 @safe struct BigNumber { 26 private union { 27 BigInt x; 28 struct { 29 static assert(BigDigit.sizeof == uint.sizeof); 30 uint[] _data; 31 bool _sign; 32 } 33 } 34 35 /++ 36 Returns: 37 the BigNumber as BigDigit array 38 +/ 39 @trusted @nogc const(BigDigit[]) data() const pure nothrow { 40 return _data; 41 } 42 43 /++ 44 Returns: 45 the sign of the BigNumber 46 +/ 47 @trusted @nogc bool sign() const pure nothrow { 48 return _sign; 49 } 50 51 enum { 52 ZERO = BigNumber(0), /// BigNumber zero 53 ONE = BigNumber(1), /// BigNumber one 54 MINUSONE = BigNumber(-1) /// BigNumber negative one 55 } 56 57 /++ 58 Construct a BigNumber for an integer 59 +/ 60 @trusted this(T)(T x) pure nothrow if (isIntegral!T) { 61 this.x = BigInt(x); 62 } 63 64 /++ 65 Construct an number for a BigInt 66 +/ 67 @nogc @trusted this(const(BigInt) x) pure nothrow { 68 this.x = x; 69 } 70 71 /++ 72 Construct an number for a BigNumber 73 +/ 74 @trusted this(const(BigNumber) big) pure nothrow { 75 this.x = big.x; 76 } 77 78 @trusted protected this(scope const(BigDigit[]) data, const bool sign) pure nothrow { 79 this._data = data.dup; 80 this._sign = sign; 81 } 82 83 /++ 84 Constructor from a number-string range 85 +/ 86 @trusted this(Range)(Range s) 87 if (isBidirectionalRange!Range && isSomeChar!(ElementType!Range) 88 && !isInfinite!Range && !isSomeString!Range) { 89 this.x = BitInt(s); 90 } 91 92 /++ 93 Construct an BigNumber from a string of numbers 94 +/ 95 @trusted this(Range)(Range s) pure if (isSomeString!Range) { 96 this.x = BigInt(s); 97 } 98 99 // /++ 100 // Construct an BigNumber for explicit sign digit number array 101 // +/ 102 // @trusted 103 // this(const bool sign, const(BigDigit[]) dig) { 104 // _sign=sign; 105 // _data=dig.dup; 106 // } 107 108 /++ 109 constructor for BigNumber in LEB128+ formant 110 +/ 111 @trusted this(const(ubyte[]) buffer) pure nothrow { 112 auto result = decodeLEB128(buffer); 113 _data = result.value._data; 114 _sign = result.value._sign; 115 } 116 /++ 117 Binary operator of op 118 Params: 119 y = is the right side value 120 +/ 121 @trusted BigNumber opBinary(string op, T)(T y) pure nothrow const { 122 static if (is(T : const(BigNumber))) { 123 enum code = format(q{BigNumber result=x %s y.x;}, op); 124 } 125 else { 126 enum code = format(q{BigNumber result=x %s y;}, op); 127 } 128 mixin(code); 129 return result; 130 } 131 132 /++ 133 Assign of the value x 134 Params: 135 x = value to be assigned 136 Returns: 137 The assign value as a BigNumber 138 +/ 139 @trusted BigNumber opAssign(T)(T x) pure nothrow if (isIntegral!T) { 140 this.x = x; 141 return this; 142 } 143 144 /++ 145 Returns: 146 the result of the unitary operation op 147 +/ 148 @trusted BigNumber opUnary(string op)() pure nothrow const 149 if (op == "+" || op == "-" || op == "~") { 150 enum code = format(q{return BigNumber(%s this.x);}, op); 151 mixin(code); 152 } 153 154 /++ 155 Returns: 156 the result of the unitary operation op 157 +/ 158 @trusted BigNumber opUnary(string op)() pure nothrow if (op == "++" || op == "--") { 159 enum code = format(q{%s this.x;}, op); 160 mixin(code); 161 return BigNumber(this); 162 } 163 164 /++ 165 Operation assignment of the value y 166 Params: 167 y = value to be assigned 168 Returns: 169 The assign value as a BigNumber 170 +/ 171 @trusted BigNumber opOpAssign(string op, T)(T y) pure nothrow { 172 static if (is(T : const(BigNumber))) { 173 enum code = format("this.x %s= y.x;", op); 174 } 175 else { 176 enum code = format("this.x %s= y;", op); 177 } 178 mixin(code); 179 return this; 180 } 181 182 /++ 183 Check the BigNumber has the equal value to y 184 Params: 185 y = value to be compared 186 Returns: 187 true if the values are equal 188 +/ 189 @trusted @nogc bool opEquals()(auto ref const BigNumber y) const pure { 190 return x == y.x; 191 } 192 193 /// ditto 194 @trusted @nogc bool opEquals(T)(T y) const pure nothrow if (isIntegral!T) { 195 return x == y; 196 } 197 198 /++ 199 Compare the BigNumber to y 200 Params: 201 y = value to be compared 202 Returns: 203 true if the values are equal 204 +/ 205 @trusted @nogc int opCmp(ref const BigNumber y) pure nothrow const { 206 return x.opCmp(y.x); 207 } 208 209 /// ditto 210 @trusted @nogc int opCmp(T)(T y) pure nothrow const if (isIntegral!T) { 211 return x.opCmp(x); 212 } 213 214 /// ditto 215 @trusted @nogc int opCmp(T : BigNumber)(const T y) pure nothrow const { 216 return x.opCmp(y.x); 217 } 218 219 /// cast BigNumber to a bool 220 @trusted T opCast(T : bool)() pure nothrow const { 221 return x.opCast!bool; 222 } 223 224 /// cast BigNumber to a type T 225 @trusted T opCast(T : ulong)() pure const { 226 return cast(T) x; 227 } 228 229 @trusted @nogc @property size_t ulongLength() const pure nothrow { 230 return x.ulongLength; 231 } 232 233 /++ 234 Converts to type T 235 +/ 236 @trusted T convert(T)() const if (isIntegral!T) { 237 import std.conv : to; 238 239 240 241 .check((x >= T.min) && (x <= T.max), 242 format("Coversion range violation for type %s, value %s is outside the [%d..%d]", 243 T.stringof, x, T.min, T.max)); 244 return x.to!T; 245 } 246 247 /++ 248 Coverts to a number string as a format 249 +/ 250 @trusted void toString(scope void delegate(const(char)[]) sink, string formatString) const { 251 return x.toString(sink, formatString); 252 } 253 254 /// ditto 255 @trusted void toString(scope void delegate(const(char)[]) sink, const ref FormatSpec!char f) const { 256 return x.toString(sink, f); 257 } 258 259 /++ 260 Coverts to a hexa-decimal number as a string as 261 +/ 262 @trusted string toHex() const { 263 return x.toHex; 264 } 265 266 /++ 267 Coverts to a decimal number as a string as 268 +/ 269 @trusted string toDecimalString() const pure nothrow { 270 return x.toDecimalString; 271 } 272 273 /++ 274 Converts the BigNumber as a two complement representation 275 Returns: 276 Range of two complement 277 +/ 278 @nogc TwoComplementRange two_complement() pure const nothrow { 279 static assert(BigDigit.sizeof is int.sizeof); 280 return TwoComplementRange(this); 281 } 282 283 @trusted void check_minuz_zero() const pure { 284 version (none) 285 286 287 288 .check(sign && (_data.length is 1) && (_data[0] is 0), 289 "The number minus zero is not allowed"); 290 } 291 292 struct TwoComplementRange { 293 @nogc: 294 protected { 295 bool overflow; 296 const(BigDigit)[] data; 297 long current; 298 bool _empty; 299 } 300 immutable bool sign; 301 302 @disable this(); 303 @trusted this(const BigNumber num) pure nothrow { 304 sign = num._sign; 305 overflow = true; 306 data = num._data; 307 popFront; 308 } 309 310 @property pure nothrow { 311 const { 312 long front() { 313 return current; 314 } 315 316 bool empty() { 317 return _empty; 318 } 319 } 320 void popFront() { 321 if (data.length) { 322 //debug writefln("data[0]=%d sign=%s", data[0], sign); 323 if (sign) { 324 current = data[0]; 325 current = ~current; 326 if (overflow) { 327 overflow = (current == -1); 328 current++; 329 } 330 //debug writefln("data[0]=%08X current=%016X", data[0], current); 331 } 332 else { 333 current = data[0]; 334 } 335 //debug writefln("\tcurrent=%d front=%d", current, front); 336 data = data[1 .. $]; 337 } 338 else { 339 _empty = true; 340 } 341 } 342 } 343 } 344 345 unittest { // Test of Two complement 346 import std.algorithm.comparison : equal; 347 348 { 349 const x = BigNumber(0); 350 assert(equal(x.two_complement, [0])); 351 } 352 353 { 354 const x = BigNumber(uint.max); 355 assert(equal(x.two_complement, [uint.max])); 356 } 357 358 { 359 const x = BigNumber(-1); 360 assert(equal(x.two_complement, [ulong.max])); 361 } 362 363 { 364 const x = BigNumber(-2); 365 assert(equal(x.two_complement, [ulong.max - 1])); 366 } 367 368 { 369 const x = BigNumber(-0x2_0000_0000); 370 assert(equal(x.two_complement, [0, 0xFFFFFFFFFFFFFFFE])); 371 } 372 373 { 374 const x = BigNumber(long.min); 375 assert(equal(x.two_complement, [0, 0xFFFFFFFF80000000])); 376 } 377 378 { 379 BigNumber x; 380 x = long.min; 381 x *= 2; 382 x -= 2; 383 assert(equal(x.two_complement, [ 384 0xfffffffffffffffe, 0xffffffffffffffff, 0xfffffffffffffffe 385 ])); 386 } 387 388 { 389 const x = BigNumber("0xAB341234_6789ABCD_EF01AB34_12346789_ABCDEF01"); 390 assert(equal(x.two_complement, [ 391 0xABCDEF01, 0x12346789, 0xEF01AB34, 0x6789ABCD, 0xAB341234 392 ])); 393 } 394 395 { 396 const x = BigNumber("-0xAB341234_6789ABCD_EF01AB34_12346789_ABCDEF01"); 397 const(ulong[]) x_twoc = [ 398 ~0xABCDEF01UL + 1, ~0x12346789UL, ~0xEF01AB34UL, ~0x6789ABCDUL, 399 ~0xAB341234UL 400 ]; 401 assert(equal(x.two_complement, x_twoc)); 402 } 403 404 { 405 const x = BigNumber("-0xAB341234_6789ABCD_EF01AB34_12346789_00000000"); 406 const(ulong[]) x_twoc = [ 407 ~0x0000_0000UL + 1, ~0x12346789UL + 1, ~0xEF01AB34UL, 408 ~0x6789ABCDUL, ~0xAB341234UL 409 ]; 410 assert(equal(x.two_complement, x_twoc)); 411 } 412 413 { 414 const x = BigNumber("-0xAB341234_6789ABCD_EF01AB34_00000000_00000000"); 415 const(ulong[]) x_twoc = [ 416 ~0x0000_0000UL + 1, ~0x00000000UL + 1, ~0xEF01AB34UL + 1, 417 ~0x6789ABCDUL, ~0xAB341234UL 418 ]; 419 assert(equal(x.two_complement, x_twoc)); 420 } 421 422 { 423 const x = BigNumber("-0xAB341234_6789ABCD_00000000_00000000_00000000"); 424 const(ulong[]) x_twoc = [ 425 ~0x0000_0000UL + 1, ~0x00000000UL + 1, ~0x00000000UL + 1, 426 ~0x6789ABCDUL + 1, ~0xAB341234UL 427 ]; 428 assert(equal(x.two_complement, x_twoc)); 429 } 430 431 { 432 const x = BigNumber("-0xAB341234_00000000_00000000_00000000_00000000"); 433 const(ulong[]) x_twoc = [ 434 ~0x0000_0000UL + 1, ~0x00000000UL + 1, ~0x00000000UL + 1, 435 ~0x00000000UL + 1, ~0xAB341234UL + 1 436 ]; 437 assert(equal(x.two_complement, x_twoc)); 438 } 439 } 440 441 @nogc static size_t calc_size(const(ubyte[]) data) pure nothrow { 442 size_t result; 443 foreach (d; data) { 444 result++; 445 if ((d & 0x80) is 0) { 446 return result; 447 } 448 } 449 return 0; 450 } 451 452 alias serialize = encodeLEB128; 453 immutable(ubyte[]) encodeLEB128() const pure { 454 check_minuz_zero; 455 immutable DATA_SIZE = (BigDigit.sizeof * data.length * 8) / 7 + 2; 456 enum DIGITS_BIT_SIZE = BigDigit.sizeof * 8; 457 scope buffer = new ubyte[DATA_SIZE]; 458 auto range2c = two_complement; 459 460 long value = range2c.front; 461 range2c.popFront; 462 uint shift = DIGITS_BIT_SIZE; 463 foreach (i, ref d; buffer) { 464 if ((shift < 7) && (!range2c.empty)) { 465 //debug writefln("range2c.front=%08x 0x%08x %d", range2c.front, value, shift); 466 value &= ~(~0L << shift); 467 value |= (range2c.front << shift); 468 shift += DIGITS_BIT_SIZE; 469 range2c.popFront; 470 } 471 d = value & 0x7F; 472 shift -= 7; 473 value >>= 7; 474 if (range2c.empty && (((value == 0) && !(d & 0x40)) || ((value == -1) && (d & 0x40)))) { 475 return buffer[0 .. i + 1].idup; 476 } 477 d |= 0x80; 478 } 479 assert(0); 480 } 481 482 @nogc size_t calc_size() const pure { 483 immutable DATA_SIZE = (BigDigit.sizeof * data.length * 8) / 7 + 1; 484 enum DIGITS_BIT_SIZE = BigDigit.sizeof * 8; 485 size_t index; 486 auto range2c = two_complement; 487 488 long value = range2c.front; 489 range2c.popFront; 490 491 uint shift = DIGITS_BIT_SIZE; 492 //debug writefln("DATA_SIZE=%d", DATA_SIZE); 493 foreach (i; 0 .. DATA_SIZE) { 494 if ((shift < 7) && (!range2c.empty)) { 495 value &= ~(~0L << shift); 496 value |= (range2c.front << shift); 497 shift += DIGITS_BIT_SIZE; 498 version (none) 499 if (range2c.front & int.min) { 500 // Set sign bit 501 value |= (~0L) << shift; 502 } 503 range2c.popFront; 504 } 505 scope d = value & 0x7F; 506 //debug writefln("SIZE %d %02x %016x %s shift=%d", i, d, value, range2c.empty, shift); 507 shift -= 7; 508 value >>= 7; 509 510 if (range2c.empty && (((value == 0) && !(d & 0x40)) || ((value == -1) && (d & 0x40)))) { 511 return i + 1; 512 } 513 d |= 0x80; 514 } 515 assert(0); 516 } 517 518 alias DecodeLEB128 = Tuple!(BigNumber, "value", size_t, "size"); 519 520 static DecodeLEB128 decodeLEB128(const(ubyte[]) data) pure nothrow { 521 scope values = new uint[data.length / BigDigit.sizeof + 1]; 522 enum DIGITS_BIT_SIZE = uint.sizeof * 8; 523 ulong result; 524 uint shift; 525 bool sign; 526 size_t index; 527 size_t size; 528 foreach (i, d; data) { 529 size++; 530 result |= ulong(d & 0x7F) << shift; 531 shift += 7; 532 if (shift >= DIGITS_BIT_SIZE) { 533 values[index++] = result & uint.max; 534 result >>= DIGITS_BIT_SIZE; 535 shift -= DIGITS_BIT_SIZE; 536 } 537 if ((d & 0x80) == 0) { 538 if ((d & 0x40) != 0) { 539 result |= (~0L << shift); 540 sign = true; 541 } 542 const v = cast(int)(result & uint.max); 543 values[index++] = v; 544 //size=i; 545 break; 546 } 547 } 548 auto result_data = values[0 .. index]; 549 if (sign) { 550 // Takes the to complement of the result because BigInt 551 // is stored as a unsigned value and a sign 552 long current; 553 bool overflow = true; 554 foreach (i, ref r; result_data) { 555 current = r; 556 current = ~current; 557 if (overflow) { 558 overflow = (current == -1); 559 current++; 560 } 561 r = current & uint.max; 562 } 563 } 564 while ((index > 1) && (result_data[index - 1] is 0)) { 565 index--; 566 } 567 return DecodeLEB128(BigNumber(result_data[0 .. index], sign), size); 568 } 569 570 } 571 572 unittest { 573 import std.algorithm.comparison : equal; 574 import std.stdio; 575 import LEB128 = tagion.utils.LEB128; 576 577 void ok(BigNumber x, const(ubyte[]) expected) { 578 const encoded = x.encodeLEB128; 579 assert(encoded == expected); 580 assert(equal(encoded, expected)); 581 assert(x.calc_size == expected.length); 582 const size = BigNumber.calc_size(expected); 583 assert(size == expected.length); 584 const decoded = BigNumber.decodeLEB128(expected); 585 assert(decoded.value._data == x._data); 586 assert(decoded.value.sign == x.sign); 587 assert(decoded.size == size); 588 assert(decoded.value == x); 589 } 590 591 { // Small positive numbers 592 ok(BigNumber(0), [0]); 593 ok(BigNumber(1), [1]); 594 ok(BigNumber(100), LEB128.encode!long(100)); 595 ok(BigNumber(1000), LEB128.encode!long(1000)); 596 ok(BigNumber(int.max), LEB128.encode!long(int.max)); 597 ok(BigNumber(ulong(uint.max) << 1), LEB128.encode!ulong(ulong(uint.max) << 1)); 598 ok(BigNumber(long.max), LEB128.encode!long(long.max)); 599 ok(BigNumber(ulong.max), LEB128.encode!ulong(ulong.max)); 600 } 601 602 { // Small negative numbers 603 ok(BigNumber(-1), [127]); 604 ok(BigNumber(-100), LEB128.encode!long(-100)); 605 ok(BigNumber(-1000), LEB128.encode!long(-1000)); 606 ok(BigNumber(int.min), LEB128.encode!long(int.min)); 607 ok(BigNumber(long(int.min) * 2), LEB128.encode!long(long(int.min) * 2)); 608 ok(BigNumber(long.min), LEB128.encode!long(long.min)); 609 } 610 611 { // Big positive number 612 BigNumber x; 613 { 614 x = ulong.max; 615 x = x * 2; 616 ok(x, [254, 255, 255, 255, 255, 255, 255, 255, 255, 3]); 617 x++; 618 ok(x, [255, 255, 255, 255, 255, 255, 255, 255, 255, 3]); 619 } 620 621 { 622 x = BigNumber("0xAB341234_6789ABCD_EF01AB34_12346789_ABCDEF01"); 623 ok(x, [ 624 129, 222, 183, 222, 154, 241, 153, 154, 146, 232, 172, 141, 625 240, 189, 243, 213, 137, 207, 209, 145, 193, 230, 42 626 ]); 627 } 628 629 } 630 631 { // Big Negative number 632 BigNumber x; 633 { 634 x = long.min; 635 x *= 2; 636 ok(x, [128, 128, 128, 128, 128, 128, 128, 128, 128, 126]); 637 x--; 638 ok(x, [255, 255, 255, 255, 255, 255, 255, 255, 255, 125]); 639 x--; 640 ok(x, [254, 255, 255, 255, 255, 255, 255, 255, 255, 125]); 641 } 642 643 { 644 x = BigNumber("-0x1_0000_0000_0000_0000_0000_0000"); 645 ok(x, [ 646 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 647 128, 96 648 ]); 649 x--; 650 ok(x, [ 651 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 652 255, 95 653 ]); 654 x--; 655 ok(x, [ 656 254, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 657 255, 95 658 ]); 659 } 660 661 { 662 x = BigNumber("-0xAB341234_6789ABCD_EF01AB34_12346789_ABCDEF01"); 663 ok(x, [ 664 255, 161, 200, 161, 229, 142, 230, 229, 237, 151, 211, 242, 665 143, 194, 140, 170, 246, 176, 174, 238, 190, 153, 85 666 ]); 667 668 x = BigNumber("-0xAB341234_6789ABCD_EF01AB34_12346789_00000000"); 669 ok(x, [ 670 128, 128, 128, 128, 240, 142, 230, 229, 237, 151, 211, 242, 671 143, 194, 140, 170, 246, 176, 174, 238, 190, 153, 85 672 ]); 673 674 x = BigNumber("-0xAB341234_6789ABCD_EF01AB34_00000000_00000000"); 675 ok(x, [ 676 128, 128, 128, 128, 128, 128, 128, 128, 128, 152, 211, 242, 677 143, 194, 140, 170, 246, 176, 174, 238, 190, 153, 85 678 ]); 679 680 x = BigNumber("-0xAB341234_6789ABCD_00000000_00000000_00000000"); 681 ok(x, [ 682 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 683 128, 224, 140, 170, 246, 176, 174, 238, 190, 153, 85 684 ]); 685 686 x = BigNumber("-0xAB341234_00000000_00000000_00000000_00000000"); 687 ok(x, [ 688 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 689 128, 128, 128, 128, 128, 128, 176, 238, 190, 153, 85 690 ]); 691 } 692 } 693 }