Coverage Report

Created: 2020-11-21 08:34

/src/botan/build/include/botan/bigint.h
Line
Count
Source (jump to first uncovered line)
1
/*
2
* BigInt
3
* (C) 1999-2008,2012,2018 Jack Lloyd
4
*     2007 FlexSecure
5
*
6
* Botan is released under the Simplified BSD License (see license.txt)
7
*/
8
9
#ifndef BOTAN_BIGINT_H_
10
#define BOTAN_BIGINT_H_
11
12
#include <botan/types.h>
13
#include <botan/secmem.h>
14
#include <botan/exceptn.h>
15
#include <iosfwd>
16
17
namespace Botan {
18
19
class RandomNumberGenerator;
20
21
/**
22
* Arbitrary precision integer
23
*/
24
class BOTAN_PUBLIC_API(2,0) BigInt final
25
   {
26
   public:
27
     /**
28
     * Base enumerator for encoding and decoding
29
     */
30
     enum Base { Decimal = 10, Hexadecimal = 16, Binary = 256 };
31
32
     /**
33
     * Sign symbol definitions for positive and negative numbers
34
     */
35
     enum Sign { Negative = 0, Positive = 1 };
36
37
     /**
38
     * Create empty BigInt
39
     */
40
28.7M
     BigInt() = default;
41
42
     /**
43
     * Create BigInt from 64 bit integer
44
     * @param n initial value of this BigInt
45
     */
46
     BigInt(uint64_t n);
47
48
     /**
49
     * Copy Constructor
50
     * @param other the BigInt to copy
51
     */
52
13.8M
     BigInt(const BigInt& other) = default;
53
54
     /**
55
     * Create BigInt from a string. If the string starts with 0x the
56
     * rest of the string will be interpreted as hexadecimal digits.
57
     * Otherwise, it will be interpreted as a decimal number.
58
     *
59
     * @param str the string to parse for an integer value
60
     */
61
     explicit BigInt(const std::string& str);
62
63
     /**
64
     * Create a BigInt from an integer in a byte array
65
     * @param buf the byte array holding the value
66
     * @param length size of buf
67
     */
68
     BigInt(const uint8_t buf[], size_t length);
69
70
     /**
71
     * Create a BigInt from an integer in a byte array
72
     * @param vec the byte vector holding the value
73
     */
74
     template<typename Alloc>
75
657
     explicit BigInt(const std::vector<uint8_t, Alloc>& vec) : BigInt(vec.data(), vec.size()) {}
Botan::BigInt::BigInt<std::__1::allocator<unsigned char> >(std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&)
Line
Count
Source
75
657
     explicit BigInt(const std::vector<uint8_t, Alloc>& vec) : BigInt(vec.data(), vec.size()) {}
Unexecuted instantiation: Botan::BigInt::BigInt<Botan::secure_allocator<unsigned char> >(std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > const&)
76
77
     /**
78
     * Create a BigInt from an integer in a byte array
79
     * @param buf the byte array holding the value
80
     * @param length size of buf
81
     * @param base is the number base of the integer in buf
82
     */
83
     BigInt(const uint8_t buf[], size_t length, Base base);
84
85
     /**
86
     * Create a BigInt from an integer in a byte array
87
     * @param buf the byte array holding the value
88
     * @param length size of buf
89
     * @param max_bits if the resulting integer is more than max_bits,
90
     *        it will be shifted so it is at most max_bits in length.
91
     */
92
     BigInt(const uint8_t buf[], size_t length, size_t max_bits);
93
94
     /**
95
     * Create a BigInt from an array of words
96
     * @param words the words
97
     * @param length number of words
98
     */
99
     BigInt(const word words[], size_t length);
100
101
     /**
102
     * \brief Create a random BigInt of the specified size
103
     *
104
     * @param rng random number generator
105
     * @param bits size in bits
106
     * @param set_high_bit if true, the highest bit is always set
107
     *
108
     * @see randomize
109
     */
110
     BigInt(RandomNumberGenerator& rng, size_t bits, bool set_high_bit = true);
111
112
     /**
113
     * Create BigInt of specified size, all zeros
114
     * @param sign the sign
115
     * @param n size of the internal register in words
116
     */
117
     BigInt(Sign sign, size_t n);
118
119
     /**
120
     * Move constructor
121
     */
122
     BigInt(BigInt&& other)
123
4.09M
        {
124
4.09M
        this->swap(other);
125
4.09M
        }
126
127
67.3M
     ~BigInt() { const_time_unpoison(); }
128
129
     /**
130
     * Move assignment
131
     */
132
     BigInt& operator=(BigInt&& other)
133
16.4M
        {
134
16.4M
        if(this != &other)
135
16.4M
           this->swap(other);
136
137
16.4M
        return (*this);
138
16.4M
        }
139
140
     /**
141
     * Copy assignment
142
     */
143
31.3M
     BigInt& operator=(const BigInt&) = default;
144
145
     /**
146
     * Swap this value with another
147
     * @param other BigInt to swap values with
148
     */
149
     void swap(BigInt& other)
150
135M
        {
151
135M
        m_data.swap(other.m_data);
152
135M
        std::swap(m_signedness, other.m_signedness);
153
135M
        }
154
155
     void swap_reg(secure_vector<word>& reg)
156
118M
        {
157
118M
        m_data.swap(reg);
158
        // sign left unchanged
159
118M
        }
160
161
     /**
162
     * += operator
163
     * @param y the BigInt to add to this
164
     */
165
     BigInt& operator+=(const BigInt& y)
166
3.32M
        {
167
3.32M
        return add(y.data(), y.sig_words(), y.sign());
168
3.32M
        }
169
170
     /**
171
     * += operator
172
     * @param y the word to add to this
173
     */
174
     BigInt& operator+=(word y)
175
2.82k
        {
176
2.82k
        return add(&y, 1, Positive);
177
2.82k
        }
178
179
     /**
180
     * -= operator
181
     * @param y the BigInt to subtract from this
182
     */
183
     BigInt& operator-=(const BigInt& y)
184
4.50M
        {
185
4.50M
        return sub(y.data(), y.sig_words(), y.sign());
186
4.50M
        }
187
188
     /**
189
     * -= operator
190
     * @param y the word to subtract from this
191
     */
192
     BigInt& operator-=(word y)
193
2.71k
        {
194
2.71k
        return sub(&y, 1, Positive);
195
2.71k
        }
196
197
     /**
198
     * *= operator
199
     * @param y the BigInt to multiply with this
200
     */
201
     BigInt& operator*=(const BigInt& y);
202
203
     /**
204
     * *= operator
205
     * @param y the word to multiply with this
206
     */
207
     BigInt& operator*=(word y);
208
209
     /**
210
     * /= operator
211
     * @param y the BigInt to divide this by
212
     */
213
     BigInt& operator/=(const BigInt& y);
214
215
     /**
216
     * Modulo operator
217
     * @param y the modulus to reduce this by
218
     */
219
     BigInt& operator%=(const BigInt& y);
220
221
     /**
222
     * Modulo operator
223
     * @param y the modulus (word) to reduce this by
224
     */
225
     word    operator%=(word y);
226
227
     /**
228
     * Left shift operator
229
     * @param shift the number of bits to shift this left by
230
     */
231
     BigInt& operator<<=(size_t shift);
232
233
     /**
234
     * Right shift operator
235
     * @param shift the number of bits to shift this right by
236
     */
237
     BigInt& operator>>=(size_t shift);
238
239
     /**
240
     * Increment operator
241
     */
242
0
     BigInt& operator++() { return (*this += 1); }
243
244
     /**
245
     * Decrement operator
246
     */
247
0
     BigInt& operator--() { return (*this -= 1); }
248
249
     /**
250
     * Postfix increment operator
251
     */
252
0
     BigInt  operator++(int) { BigInt x = (*this); ++(*this); return x; }
253
254
     /**
255
     * Postfix decrement operator
256
     */
257
0
     BigInt  operator--(int) { BigInt x = (*this); --(*this); return x; }
258
259
     /**
260
     * Unary negation operator
261
     * @return negative this
262
     */
263
     BigInt operator-() const;
264
265
     /**
266
     * ! operator
267
     * @return true iff this is zero, otherwise false
268
     */
269
0
     bool operator !() const { return (!is_nonzero()); }
270
271
     static BigInt add2(const BigInt& x, const word y[], size_t y_words, Sign y_sign);
272
273
     BigInt& add(const word y[], size_t y_words, Sign sign);
274
275
     BigInt& sub(const word y[], size_t y_words, Sign sign)
276
4.50M
        {
277
4.09M
        return add(y, y_words, sign == Positive ? Negative : Positive);
278
4.50M
        }
279
280
     /**
281
     * Multiply this with y
282
     * @param y the BigInt to multiply with this
283
     * @param ws a temp workspace
284
     */
285
     BigInt& mul(const BigInt& y, secure_vector<word>& ws);
286
287
     /**
288
     * Square value of *this
289
     * @param ws a temp workspace
290
     */
291
     BigInt& square(secure_vector<word>& ws);
292
293
     /**
294
     * Set *this to y - *this
295
     * @param y the BigInt to subtract from as a sequence of words
296
     * @param y_words length of y in words
297
     * @param ws a temp workspace
298
     */
299
     BigInt& rev_sub(const word y[], size_t y_words, secure_vector<word>& ws);
300
301
     /**
302
     * Set *this to (*this + y) % mod
303
     * This function assumes *this is >= 0 && < mod
304
     * @param y the BigInt to add - assumed y >= 0 and y < mod
305
     * @param mod the positive modulus
306
     * @param ws a temp workspace
307
     */
308
     BigInt& mod_add(const BigInt& y, const BigInt& mod, secure_vector<word>& ws);
309
310
     /**
311
     * Set *this to (*this - y) % mod
312
     * This function assumes *this is >= 0 && < mod
313
     * @param y the BigInt to subtract - assumed y >= 0 and y < mod
314
     * @param mod the positive modulus
315
     * @param ws a temp workspace
316
     */
317
     BigInt& mod_sub(const BigInt& y, const BigInt& mod, secure_vector<word>& ws);
318
319
     /**
320
     * Set *this to (*this * y) % mod
321
     * This function assumes *this is >= 0 && < mod
322
     * y should be small, less than 16
323
     * @param y the small integer to multiply by
324
     * @param mod the positive modulus
325
     * @param ws a temp workspace
326
     */
327
     BigInt& mod_mul(uint8_t y, const BigInt& mod, secure_vector<word>& ws);
328
329
     /**
330
     * Return *this % mod
331
     *
332
     * Assumes that *this is (if anything) only slightly larger than
333
     * mod and performs repeated subtractions. It should not be used if
334
     * *this is much larger than mod, instead use modulo operator.
335
     */
336
     size_t reduce_below(const BigInt& mod, secure_vector<word> &ws);
337
338
     /**
339
     * Return *this % mod
340
     *
341
     * Assumes that *this is (if anything) only slightly larger than mod and
342
     * performs repeated subtractions. It should not be used if *this is much
343
     * larger than mod, instead use modulo operator.
344
     *
345
     * Performs exactly bound subtractions, so if *this is >= bound*mod then the
346
     * result will not be fully reduced. If bound is zero, nothing happens.
347
     */
348
     void ct_reduce_below(const BigInt& mod, secure_vector<word> &ws, size_t bound);
349
350
     /**
351
     * Zeroize the BigInt. The size of the underlying register is not
352
     * modified.
353
     */
354
1.96M
     void clear() { m_data.set_to_zero(); m_signedness = Positive; }
355
356
     /**
357
     * Compare this to another BigInt
358
     * @param n the BigInt value to compare with
359
     * @param check_signs include sign in comparison?
360
     * @result if (this<n) return -1, if (this>n) return 1, if both
361
     * values are identical return 0 [like Perl's <=> operator]
362
     */
363
     int32_t cmp(const BigInt& n, bool check_signs = true) const;
364
365
     /**
366
     * Compare this to another BigInt
367
     * @param n the BigInt value to compare with
368
     * @result true if this == n or false otherwise
369
     */
370
     bool is_equal(const BigInt& n) const;
371
372
     /**
373
     * Compare this to another BigInt
374
     * @param n the BigInt value to compare with
375
     * @result true if this < n or false otherwise
376
     */
377
     bool is_less_than(const BigInt& n) const;
378
379
     /**
380
     * Compare this to an integer
381
     * @param n the value to compare with
382
     * @result if (this<n) return -1, if (this>n) return 1, if both
383
     * values are identical return 0 [like Perl's <=> operator]
384
     */
385
     int32_t cmp_word(word n) const;
386
387
     /**
388
     * Test if the integer has an even value
389
     * @result true if the integer is even, false otherwise
390
     */
391
251k
     bool is_even() const { return (get_bit(0) == 0); }
392
393
     /**
394
     * Test if the integer has an odd value
395
     * @result true if the integer is odd, false otherwise
396
     */
397
3.42M
     bool is_odd()  const { return (get_bit(0) == 1); }
398
399
     /**
400
     * Test if the integer is not zero
401
     * @result true if the integer is non-zero, false otherwise
402
     */
403
8.12M
     bool is_nonzero() const { return (!is_zero()); }
404
405
     /**
406
     * Test if the integer is zero
407
     * @result true if the integer is zero, false otherwise
408
     */
409
     bool is_zero() const
410
75.2M
        {
411
75.2M
        return (sig_words() == 0);
412
75.2M
        }
413
414
     /**
415
     * Set bit at specified position
416
     * @param n bit position to set
417
     */
418
     void set_bit(size_t n)
419
618k
        {
420
618k
        conditionally_set_bit(n, true);
421
618k
        }
422
423
     /**
424
     * Conditionally set bit at specified position. Note if set_it is
425
     * false, nothing happens, and if the bit is already set, it
426
     * remains set.
427
     *
428
     * @param n bit position to set
429
     * @param set_it if the bit should be set
430
     */
431
     void conditionally_set_bit(size_t n, bool set_it);
432
433
     /**
434
     * Clear bit at specified position
435
     * @param n bit position to clear
436
     */
437
     void clear_bit(size_t n);
438
439
     /**
440
     * Clear all but the lowest n bits
441
     * @param n amount of bits to keep
442
     */
443
     void mask_bits(size_t n)
444
271M
        {
445
271M
        m_data.mask_bits(n);
446
271M
        }
447
448
     /**
449
     * Return bit value at specified position
450
     * @param n the bit offset to test
451
     * @result true, if the bit at position n is set, false otherwise
452
     */
453
     bool get_bit(size_t n) const
454
177M
        {
455
177M
        return ((word_at(n / BOTAN_MP_WORD_BITS) >> (n % BOTAN_MP_WORD_BITS)) & 1);
456
177M
        }
457
458
     /**
459
     * Return (a maximum of) 32 bits of the complete value
460
     * @param offset the offset to start extracting
461
     * @param length amount of bits to extract (starting at offset)
462
     * @result the integer extracted from the register starting at
463
     * offset with specified length
464
     */
465
     uint32_t get_substring(size_t offset, size_t length) const;
466
467
     /**
468
     * Convert this value into a uint32_t, if it is in the range
469
     * [0 ... 2**32-1], or otherwise throw an exception.
470
     * @result the value as a uint32_t if conversion is possible
471
     */
472
     uint32_t to_u32bit() const;
473
474
     /**
475
     * Convert this value to a decimal string.
476
     * Warning: decimal conversions are relatively slow
477
     */
478
     std::string to_dec_string() const;
479
480
     /**
481
     * Convert this value to a hexadecimal string.
482
     */
483
     std::string to_hex_string() const;
484
485
     /**
486
     * @param n the offset to get a byte from
487
     * @result byte at offset n
488
     */
489
     uint8_t byte_at(size_t n) const;
490
491
     /**
492
     * Return the word at a specified position of the internal register
493
     * @param n position in the register
494
     * @return value at position n
495
     */
496
     word word_at(size_t n) const
497
2.18G
        {
498
2.18G
        return m_data.get_word_at(n);
499
2.18G
        }
500
501
     void set_word_at(size_t i, word w)
502
269M
        {
503
269M
        m_data.set_word_at(i, w);
504
269M
        }
505
506
     void set_words(const word w[], size_t len)
507
14.6M
        {
508
14.6M
        m_data.set_words(w, len);
509
14.6M
        }
510
511
     /**
512
     * Tests if the sign of the integer is negative
513
     * @result true, iff the integer has a negative sign
514
     */
515
745M
     bool is_negative() const { return (sign() == Negative); }
516
517
     /**
518
     * Tests if the sign of the integer is positive
519
     * @result true, iff the integer has a positive sign
520
     */
521
12.4M
     bool is_positive() const { return (sign() == Positive); }
522
523
     /**
524
     * Return the sign of the integer
525
     * @result the sign of the integer
526
     */
527
884M
     Sign sign() const { return (m_signedness); }
528
529
     /**
530
     * @result the opposite sign of the represented integer value
531
     */
532
     Sign reverse_sign() const
533
2.00M
        {
534
2.00M
        if(sign() == Positive)
535
2.00M
           return Negative;
536
753
        return Positive;
537
753
        }
538
539
     /**
540
     * Flip the sign of this BigInt
541
     */
542
     void flip_sign()
543
15.5k
        {
544
15.5k
        set_sign(reverse_sign());
545
15.5k
        }
546
547
     /**
548
     * Set sign of the integer
549
     * @param sign new Sign to set
550
     */
551
     void set_sign(Sign sign)
552
59.3M
        {
553
59.3M
        if(sign == Negative && is_zero())
554
1.01k
           sign = Positive;
555
556
59.3M
        m_signedness = sign;
557
59.3M
        }
558
559
     /**
560
     * @result absolute (positive) value of this
561
     */
562
     BigInt abs() const;
563
564
     /**
565
     * Give size of internal register
566
     * @result size of internal register in words
567
     */
568
2.86G
     size_t size() const { return m_data.size(); }
569
570
     /**
571
     * Return how many words we need to hold this value
572
     * @result significant words of the represented integer value
573
     */
574
     size_t sig_words() const
575
449M
        {
576
449M
        return m_data.sig_words();
577
449M
        }
578
579
     /**
580
     * Give byte length of the integer
581
     * @result byte length of the represented integer value
582
     */
583
     size_t bytes() const;
584
585
     /**
586
     * Get the bit length of the integer
587
     * @result bit length of the represented integer value
588
     */
589
     size_t bits() const;
590
591
     /**
592
     * Get the number of high bits unset in the top (allocated) word
593
     * of this integer. Returns BOTAN_MP_WORD_BITS only iff *this is
594
     * zero. Ignores sign.
595
     */
596
     size_t top_bits_free() const;
597
598
     /**
599
     * Return a mutable pointer to the register
600
     * @result a pointer to the start of the internal register
601
     */
602
1.97G
     word* mutable_data() { return m_data.mutable_data(); }
603
604
     /**
605
     * Return a const pointer to the register
606
     * @result a pointer to the start of the internal register
607
     */
608
2.11G
     const word* data() const { return m_data.const_data(); }
609
610
     /**
611
     * Don't use this function in application code
612
     */
613
64.9M
     secure_vector<word>& get_word_vector() { return m_data.mutable_vector(); }
614
615
     /**
616
     * Don't use this function in application code
617
     */
618
92.7M
     const secure_vector<word>& get_word_vector() const { return m_data.const_vector(); }
619
620
     /**
621
     * Increase internal register buffer to at least n words
622
     * @param n new size of register
623
     */
624
972M
     void grow_to(size_t n) const { m_data.grow_to(n); }
625
626
0
     void resize(size_t s) { m_data.resize(s); }
627
628
     /**
629
     * Fill BigInt with a random number with size of bitsize
630
     *
631
     * If \p set_high_bit is true, the highest bit will be set, which causes
632
     * the entropy to be \a bits-1. Otherwise the highest bit is randomly chosen
633
     * by the rng, causing the entropy to be \a bits.
634
     *
635
     * @param rng the random number generator to use
636
     * @param bitsize number of bits the created random value should have
637
     * @param set_high_bit if true, the highest bit is always set
638
     */
639
     void randomize(RandomNumberGenerator& rng, size_t bitsize, bool set_high_bit = true);
640
641
     /**
642
     * Store BigInt-value in a given byte array
643
     * @param buf destination byte array for the integer value
644
     */
645
     void binary_encode(uint8_t buf[]) const;
646
647
     /**
648
     * Store BigInt-value in a given byte array. If len is less than
649
     * the size of the value, then it will be truncated. If len is
650
     * greater than the size of the value, it will be zero-padded.
651
     * If len exactly equals this->bytes(), this function behaves identically
652
     * to binary_encode.
653
     *
654
     * @param buf destination byte array for the integer value
655
     * @param len how many bytes to write
656
     */
657
     void binary_encode(uint8_t buf[], size_t len) const;
658
659
     /**
660
     * Read integer value from a byte array with given size
661
     * @param buf byte array buffer containing the integer
662
     * @param length size of buf
663
     */
664
     void binary_decode(const uint8_t buf[], size_t length);
665
666
     /**
667
     * Read integer value from a byte vector
668
     * @param buf the vector to load from
669
     */
670
     template<typename Alloc>
671
     void binary_decode(const std::vector<uint8_t, Alloc>& buf)
672
515k
        {
673
515k
        binary_decode(buf.data(), buf.size());
674
515k
        }
675
676
     /**
677
     * Place the value into out, zero-padding up to size words
678
     * Throw if *this cannot be represented in size words
679
     */
680
     void encode_words(word out[], size_t size) const;
681
682
     /**
683
     * If predicate is true assign other to *this
684
     * Uses a masked operation to avoid side channels
685
     */
686
     void ct_cond_assign(bool predicate, const BigInt& other);
687
688
     /**
689
     * If predicate is true swap *this and other
690
     * Uses a masked operation to avoid side channels
691
     */
692
     void ct_cond_swap(bool predicate, BigInt& other);
693
694
     /**
695
     * If predicate is true add value to *this
696
     */
697
     void ct_cond_add(bool predicate, const BigInt& value);
698
699
     /**
700
     * If predicate is true flip the sign of *this
701
     */
702
     void cond_flip_sign(bool predicate);
703
704
#if defined(BOTAN_HAS_VALGRIND)
705
     void const_time_poison() const;
706
     void const_time_unpoison() const;
707
#else
708
1.61M
     void const_time_poison() const {}
709
67.4M
     void const_time_unpoison() const {}
710
#endif
711
712
     /**
713
     * @param rng a random number generator
714
     * @param min the minimum value (must be non-negative)
715
     * @param max the maximum value (must be non-negative and > min)
716
     * @return random integer in [min,max)
717
     */
718
     static BigInt random_integer(RandomNumberGenerator& rng,
719
                                  const BigInt& min,
720
                                  const BigInt& max);
721
722
     /**
723
     * Create a power of two
724
     * @param n the power of two to create
725
     * @return bigint representing 2^n
726
     */
727
     static BigInt power_of_2(size_t n)
728
156k
        {
729
156k
        BigInt b;
730
156k
        b.set_bit(n);
731
156k
        return b;
732
156k
        }
733
734
     /**
735
     * Encode the integer value from a BigInt to a std::vector of bytes
736
     * @param n the BigInt to use as integer source
737
     * @result secure_vector of bytes containing the bytes of the integer
738
     */
739
     static std::vector<uint8_t> encode(const BigInt& n)
740
42.9k
        {
741
42.9k
        std::vector<uint8_t> output(n.bytes());
742
42.9k
        n.binary_encode(output.data());
743
42.9k
        return output;
744
42.9k
        }
745
746
     /**
747
     * Encode the integer value from a BigInt to a secure_vector of bytes
748
     * @param n the BigInt to use as integer source
749
     * @result secure_vector of bytes containing the bytes of the integer
750
     */
751
     static secure_vector<uint8_t> encode_locked(const BigInt& n)
752
6.06k
        {
753
6.06k
        secure_vector<uint8_t> output(n.bytes());
754
6.06k
        n.binary_encode(output.data());
755
6.06k
        return output;
756
6.06k
        }
757
758
     /**
759
     * Create a BigInt from an integer in a byte array
760
     * @param buf the binary value to load
761
     * @param length size of buf
762
     * @result BigInt representing the integer in the byte array
763
     */
764
     static BigInt decode(const uint8_t buf[], size_t length)
765
45.3k
        {
766
45.3k
        return BigInt(buf, length);
767
45.3k
        }
768
769
     /**
770
     * Create a BigInt from an integer in a byte array
771
     * @param buf the binary value to load
772
     * @result BigInt representing the integer in the byte array
773
     */
774
     template<typename Alloc>
775
     static BigInt decode(const std::vector<uint8_t, Alloc>& buf)
776
657
        {
777
657
        return BigInt(buf);
778
657
        }
Botan::BigInt Botan::BigInt::decode<std::__1::allocator<unsigned char> >(std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&)
Line
Count
Source
776
657
        {
777
657
        return BigInt(buf);
778
657
        }
Unexecuted instantiation: Botan::BigInt Botan::BigInt::decode<Botan::secure_allocator<unsigned char> >(std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > const&)
779
780
     /**
781
     * Create a BigInt from an integer in a byte array
782
     * @param buf the binary value to load
783
     * @param length size of buf
784
     * @param base number-base of the integer in buf
785
     * @result BigInt representing the integer in the byte array
786
     */
787
     static BigInt decode(const uint8_t buf[], size_t length,
788
                          Base base);
789
790
     /**
791
     * Create a BigInt from an integer in a byte array
792
     * @param buf the binary value to load
793
     * @param base number-base of the integer in buf
794
     * @result BigInt representing the integer in the byte array
795
     */
796
     template<typename Alloc>
797
     static BigInt decode(const std::vector<uint8_t, Alloc>& buf, Base base)
798
        {
799
        if(base == Binary)
800
           return BigInt(buf);
801
        return BigInt::decode(buf.data(), buf.size(), base);
802
        }
803
804
     /**
805
     * Encode a BigInt to a byte array according to IEEE 1363
806
     * @param n the BigInt to encode
807
     * @param bytes the length of the resulting secure_vector<uint8_t>
808
     * @result a secure_vector<uint8_t> containing the encoded BigInt
809
     */
810
     static secure_vector<uint8_t> encode_1363(const BigInt& n, size_t bytes);
811
812
     static void encode_1363(uint8_t out[], size_t bytes, const BigInt& n);
813
814
     /**
815
     * Encode two BigInt to a byte array according to IEEE 1363
816
     * @param n1 the first BigInt to encode
817
     * @param n2 the second BigInt to encode
818
     * @param bytes the length of the encoding of each single BigInt
819
     * @result a secure_vector<uint8_t> containing the concatenation of the two encoded BigInt
820
     */
821
     static secure_vector<uint8_t> encode_fixed_length_int_pair(const BigInt& n1, const BigInt& n2, size_t bytes);
822
823
   private:
824
825
     class Data
826
        {
827
        public:
828
           word* mutable_data()
829
2.00G
              {
830
2.00G
              invalidate_sig_words();
831
2.00G
              return m_reg.data();
832
2.00G
              }
833
834
           const word* const_data() const
835
2.11G
              {
836
2.11G
              return m_reg.data();
837
2.11G
              }
838
839
           secure_vector<word>& mutable_vector()
840
64.9M
              {
841
64.9M
              invalidate_sig_words();
842
64.9M
              return m_reg;
843
64.9M
              }
844
845
           const secure_vector<word>& const_vector() const
846
92.7M
              {
847
92.7M
              return m_reg;
848
92.7M
              }
849
850
           word get_word_at(size_t n) const
851
2.18G
              {
852
2.18G
              if(n < m_reg.size())
853
2.18G
                 return m_reg[n];
854
3.55M
              return 0;
855
3.55M
              }
856
857
           void set_word_at(size_t i, word w)
858
612M
              {
859
612M
              invalidate_sig_words();
860
612M
              if(i >= m_reg.size())
861
233M
                 {
862
233M
                 if(w == 0)
863
232M
                    return;
864
869k
                 grow_to(i + 1);
865
869k
                 }
866
379M
              m_reg[i] = w;
867
379M
              }
868
869
           void set_words(const word w[], size_t len)
870
14.7M
              {
871
14.7M
              invalidate_sig_words();
872
14.7M
              m_reg.assign(w, w + len);
873
14.7M
              }
874
875
           void set_to_zero()
876
1.96M
              {
877
1.96M
              m_reg.resize(m_reg.capacity());
878
1.96M
              clear_mem(m_reg.data(), m_reg.size());
879
1.96M
              m_sig_words = 0;
880
1.96M
              }
881
882
           void set_size(size_t s)
883
17.2M
              {
884
17.2M
              invalidate_sig_words();
885
17.2M
              clear_mem(m_reg.data(), m_reg.size());
886
17.2M
              m_reg.resize(s + (8 - (s % 8)));
887
17.2M
              }
888
889
           void mask_bits(size_t n)
890
271M
              {
891
271M
              if(n == 0) { return set_to_zero(); }
892
893
271M
              const size_t top_word = n / BOTAN_MP_WORD_BITS;
894
895
              // if(top_word < sig_words()) ?
896
271M
              if(top_word < size())
897
271M
                 {
898
271M
                 const word mask = (static_cast<word>(1) << (n % BOTAN_MP_WORD_BITS)) - 1;
899
271M
                 const size_t len = size() - (top_word + 1);
900
271M
                 if(len > 0)
901
271M
                    {
902
271M
                    clear_mem(&m_reg[top_word+1], len);
903
271M
                    }
904
271M
                 m_reg[top_word] &= mask;
905
271M
                 invalidate_sig_words();
906
271M
                 }
907
271M
              }
908
909
           void grow_to(size_t n) const
910
978M
              {
911
978M
              if(n > size())
912
34.7M
                 {
913
34.7M
                 if(n <= m_reg.capacity())
914
22.0M
                    m_reg.resize(n);
915
12.6M
                 else
916
12.6M
                    m_reg.resize(n + (8 - (n % 8)));
917
34.7M
                 }
918
978M
              }
919
920
4.41G
           size_t size() const { return m_reg.size(); }
921
922
           void shrink_to_fit(size_t min_size = 0)
923
0
              {
924
0
              const size_t words = std::max(min_size, sig_words());
925
0
              m_reg.resize(words);
926
0
              }
927
928
           void resize(size_t s)
929
0
              {
930
0
              m_reg.resize(s);
931
0
              }
932
933
           void swap(Data& other)
934
135M
              {
935
135M
              m_reg.swap(other.m_reg);
936
135M
              std::swap(m_sig_words, other.m_sig_words);
937
135M
              }
938
939
           void swap(secure_vector<word>& reg)
940
119M
              {
941
119M
              m_reg.swap(reg);
942
119M
              invalidate_sig_words();
943
119M
              }
944
945
           void invalidate_sig_words() const
946
3.10G
              {
947
3.10G
              m_sig_words = sig_words_npos;
948
3.10G
              }
949
950
           size_t sig_words() const
951
449M
              {
952
449M
              if(m_sig_words == sig_words_npos)
953
144M
                 {
954
144M
                 m_sig_words = calc_sig_words();
955
144M
                 }
956
304M
              else
957
304M
                 {
958
304M
                 BOTAN_DEBUG_ASSERT(m_sig_words == calc_sig_words());
959
304M
                 }
960
449M
              return m_sig_words;
961
449M
              }
962
        private:
963
           static const size_t sig_words_npos = static_cast<size_t>(-1);
964
965
           size_t calc_sig_words() const;
966
967
           mutable secure_vector<word> m_reg;
968
           mutable size_t m_sig_words = sig_words_npos;
969
        };
970
971
      Data m_data;
972
      Sign m_signedness = Positive;
973
   };
974
975
/*
976
* Arithmetic Operators
977
*/
978
inline BigInt operator+(const BigInt& x, const BigInt& y)
979
1.03M
   {
980
1.03M
   return BigInt::add2(x, y.data(), y.sig_words(), y.sign());
981
1.03M
   }
982
983
inline BigInt operator+(const BigInt& x, word y)
984
19.7k
   {
985
19.7k
   return BigInt::add2(x, &y, 1, BigInt::Positive);
986
19.7k
   }
987
988
inline BigInt operator+(word x, const BigInt& y)
989
0
   {
990
0
   return y + x;
991
0
   }
992
993
inline BigInt operator-(const BigInt& x, const BigInt& y)
994
1.99M
   {
995
1.99M
   return BigInt::add2(x, y.data(), y.sig_words(), y.reverse_sign());
996
1.99M
   }
997
998
inline BigInt operator-(const BigInt& x, word y)
999
19.4k
   {
1000
19.4k
   return BigInt::add2(x, &y, 1, BigInt::Negative);
1001
19.4k
   }
1002
1003
BigInt BOTAN_PUBLIC_API(2,0) operator*(const BigInt& x, const BigInt& y);
1004
BigInt BOTAN_PUBLIC_API(2,8) operator*(const BigInt& x, word y);
1005
5.37M
inline BigInt operator*(word x, const BigInt& y) { return y*x; }
1006
1007
BigInt BOTAN_PUBLIC_API(2,0) operator/(const BigInt& x, const BigInt& d);
1008
BigInt BOTAN_PUBLIC_API(2,0) operator/(const BigInt& x, word m);
1009
BigInt BOTAN_PUBLIC_API(2,0) operator%(const BigInt& x, const BigInt& m);
1010
word   BOTAN_PUBLIC_API(2,0) operator%(const BigInt& x, word m);
1011
BigInt BOTAN_PUBLIC_API(2,0) operator<<(const BigInt& x, size_t n);
1012
BigInt BOTAN_PUBLIC_API(2,0) operator>>(const BigInt& x, size_t n);
1013
1014
/*
1015
* Comparison Operators
1016
*/
1017
inline bool operator==(const BigInt& a, const BigInt& b)
1018
351k
   { return a.is_equal(b); }
1019
inline bool operator!=(const BigInt& a, const BigInt& b)
1020
67.4k
   { return !a.is_equal(b); }
1021
inline bool operator<=(const BigInt& a, const BigInt& b)
1022
89.0k
   { return (a.cmp(b) <= 0); }
1023
inline bool operator>=(const BigInt& a, const BigInt& b)
1024
601k
   { return (a.cmp(b) >= 0); }
1025
inline bool operator<(const BigInt& a, const BigInt& b)
1026
3.23M
   { return a.is_less_than(b); }
1027
inline bool operator>(const BigInt& a, const BigInt& b)
1028
2.80M
   { return b.is_less_than(a); }
1029
1030
inline bool operator==(const BigInt& a, word b)
1031
516k
   { return (a.cmp_word(b) == 0); }
1032
inline bool operator!=(const BigInt& a, word b)
1033
3.20M
   { return (a.cmp_word(b) != 0); }
1034
inline bool operator<=(const BigInt& a, word b)
1035
30.3k
   { return (a.cmp_word(b) <= 0); }
1036
inline bool operator>=(const BigInt& a, word b)
1037
203
   { return (a.cmp_word(b) >= 0); }
1038
inline bool operator<(const BigInt& a, word b)
1039
338k
   { return (a.cmp_word(b) < 0); }
1040
inline bool operator>(const BigInt& a, word b)
1041
3.58M
   { return (a.cmp_word(b) > 0); }
1042
1043
/*
1044
* I/O Operators
1045
*/
1046
BOTAN_PUBLIC_API(2,0) std::ostream& operator<<(std::ostream&, const BigInt&);
1047
BOTAN_PUBLIC_API(2,0) std::istream& operator>>(std::istream&, BigInt&);
1048
1049
}
1050
1051
namespace std {
1052
1053
template<>
1054
inline void swap<Botan::BigInt>(Botan::BigInt& x, Botan::BigInt& y)
1055
2.80M
   {
1056
2.80M
   x.swap(y);
1057
2.80M
   }
1058
1059
}
1060
1061
#endif