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 }