1 /** @file
2 *****************************************************************************
3 Implementation of misc math and serialization utility functions
4 *****************************************************************************
5 * @author This file is part of libff, developed by SCIPR Lab
6 * and contributors (see AUTHORS).
7 * @copyright MIT license (see LICENSE file)
8 *****************************************************************************/
9
10 #include <algorithm>
11 #include <cassert>
12 #include <cstdarg>
13 #include <cstdint>
14
15 #include <libff/common/utils.hpp>
16
17 namespace libff {
18
get_power_of_two(size_t n)19 size_t get_power_of_two(size_t n)
20 {
21 n--;
22 n |= n >> 1;
23 n |= n >> 2;
24 n |= n >> 4;
25 n |= n >> 8;
26 n |= n >> 16;
27 n++;
28
29 return n;
30 }
31
log2(size_t n)32 size_t log2(size_t n)
33 /* returns ceil(log2(n)), so 1ul<<log2(n) is the smallest power of 2,
34 that is not less than n. */
35 {
36 size_t r = ((n & (n-1)) == 0 ? 0 : 1); // add 1 if n is not power of 2
37
38 while (n > 1)
39 {
40 n >>= 1;
41 r++;
42 }
43
44 return r;
45 }
46
to_twos_complement(int i,size_t w)47 size_t to_twos_complement(int i, size_t w)
48 {
49 assert(i >= -(1l<<(w-1)));
50 assert(i < (1l<<(w-1)));
51 return (i >= 0) ? i : i + (1l<<w);
52 }
53
from_twos_complement(size_t i,size_t w)54 int from_twos_complement(size_t i, size_t w)
55 {
56 assert(i < (1ul<<w));
57 return (i < (1ul<<(w-1))) ? i : i - (1ul<<w);
58 }
59
bitreverse(size_t n,const size_t l)60 size_t bitreverse(size_t n, const size_t l)
61 {
62 size_t r = 0;
63 for (size_t k = 0; k < l; ++k)
64 {
65 r = (r << 1) | (n & 1);
66 n >>= 1;
67 }
68 return r;
69 }
70
int_list_to_bits(const std::initializer_list<unsigned long> & l,const size_t wordsize)71 bit_vector int_list_to_bits(const std::initializer_list<unsigned long> &l, const size_t wordsize)
72 {
73 bit_vector res(wordsize*l.size());
74 for (size_t i = 0; i < l.size(); ++i)
75 {
76 for (size_t j = 0; j < wordsize; ++j)
77 {
78 res[i*wordsize + j] = (*(l.begin()+i) & (1ul<<(wordsize-1-j)));
79 }
80 }
81 return res;
82 }
83
div_ceil(long long x,long long y)84 long long div_ceil(long long x, long long y)
85 {
86 return (x + (y-1)) / y;
87 }
88
is_little_endian()89 bool is_little_endian()
90 {
91 uint64_t a = 0x12345678;
92 unsigned char *c = (unsigned char*)(&a);
93 return (*c = 0x78);
94 }
95
FORMAT(const std::string & prefix,const char * format,...)96 std::string FORMAT(const std::string &prefix, const char* format, ...)
97 {
98 const static size_t MAX_FMT = 256;
99 char buf[MAX_FMT];
100 va_list args;
101 va_start(args, format);
102 vsnprintf(buf, MAX_FMT, format, args);
103 va_end(args);
104
105 return prefix + std::string(buf);
106 }
107
serialize_bit_vector(std::ostream & out,const bit_vector & v)108 void serialize_bit_vector(std::ostream &out, const bit_vector &v)
109 {
110 out << v.size() << "\n";
111 for (size_t i = 0; i < v.size(); ++i)
112 {
113 out << v[i] << "\n";
114 }
115 }
116
deserialize_bit_vector(std::istream & in,bit_vector & v)117 void deserialize_bit_vector(std::istream &in, bit_vector &v)
118 {
119 size_t size;
120 in >> size;
121 v.resize(size);
122 for (size_t i = 0; i < size; ++i)
123 {
124 bool b;
125 in >> b;
126 v[i] = b;
127 }
128 }
129 } // libff
130