Electroneum
int-util.h
Go to the documentation of this file.
1 // Copyrights(c) 2017-2021, The Electroneum Project
2 // Copyrights(c) 2014-2019, The Monero Project
3 //
4 // All rights reserved.
5 //
6 // Redistribution and use in source and binary forms, with or without modification, are
7 // permitted provided that the following conditions are met:
8 //
9 // 1. Redistributions of source code must retain the above copyright notice, this list of
10 // conditions and the following disclaimer.
11 //
12 // 2. Redistributions in binary form must reproduce the above copyright notice, this list
13 // of conditions and the following disclaimer in the documentation and/or other
14 // materials provided with the distribution.
15 //
16 // 3. Neither the name of the copyright holder nor the names of its contributors may be
17 // used to endorse or promote products derived from this software without specific
18 // prior written permission.
19 //
20 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY
21 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
22 // MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
23 // THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
25 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
27 // STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
28 // THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 //
30 // Parts of this file are originally copyright (c) 2012-2013 The Cryptonote developers
31 
32 #pragma once
33 
34 #include <assert.h>
35 #include <stdbool.h>
36 #include <stdint.h>
37 #include <string.h>
38 
39 #ifndef _MSC_VER
40 #include <sys/param.h>
41 #endif
42 
43 #if defined(__ANDROID__)
44 #include <byteswap.h>
45 #endif
46 
47 #if defined(__sun) && defined(__SVR4)
48 #include <endian.h>
49 #endif
50 
51 #if defined(_MSC_VER)
52 #include <stdlib.h>
53 
54 static inline uint32_t rol32(uint32_t x, int r) {
55  static_assert(sizeof(uint32_t) == sizeof(unsigned int), "this code assumes 32-bit integers");
56  return _rotl(x, r);
57 }
58 
59 static inline uint64_t rol64(uint64_t x, int r) {
60  return _rotl64(x, r);
61 }
62 
63 #else
64 
65 static inline uint32_t rol32(uint32_t x, int r) {
66  return (x << (r & 31)) | (x >> (-r & 31));
67 }
68 
69 static inline uint64_t rol64(uint64_t x, int r) {
70  return (x << (r & 63)) | (x >> (-r & 63));
71 }
72 
73 #endif
74 
75 static inline uint64_t hi_dword(uint64_t val) {
76  return val >> 32;
77 }
78 
79 static inline uint64_t lo_dword(uint64_t val) {
80  return val & 0xFFFFFFFF;
81 }
82 
83 static inline uint64_t mul128(uint64_t multiplier, uint64_t multiplicand, uint64_t* product_hi) {
84  // multiplier = ab = a * 2^32 + b
85  // multiplicand = cd = c * 2^32 + d
86  // ab * cd = a * c * 2^64 + (a * d + b * c) * 2^32 + b * d
87  uint64_t a = hi_dword(multiplier);
88  uint64_t b = lo_dword(multiplier);
89  uint64_t c = hi_dword(multiplicand);
90  uint64_t d = lo_dword(multiplicand);
91 
92  uint64_t ac = a * c;
93  uint64_t ad = a * d;
94  uint64_t bc = b * c;
95  uint64_t bd = b * d;
96 
97  uint64_t adbc = ad + bc;
98  uint64_t adbc_carry = adbc < ad ? 1 : 0;
99 
100  // multiplier * multiplicand = product_hi * 2^64 + product_lo
101  uint64_t product_lo = bd + (adbc << 32);
102  uint64_t product_lo_carry = product_lo < bd ? 1 : 0;
103  *product_hi = ac + (adbc >> 32) + (adbc_carry << 32) + product_lo_carry;
104  assert(ac <= *product_hi);
105 
106  return product_lo;
107 }
108 
109 static inline uint64_t div_with_reminder(uint64_t dividend, uint32_t divisor, uint32_t* remainder) {
110  dividend |= ((uint64_t)*remainder) << 32;
111  *remainder = dividend % divisor;
112  return dividend / divisor;
113 }
114 
115 // Long division with 2^32 base
116 static inline uint32_t div128_32(uint64_t dividend_hi, uint64_t dividend_lo, uint32_t divisor, uint64_t* quotient_hi, uint64_t* quotient_lo) {
117  uint64_t dividend_dwords[4];
118  uint32_t remainder = 0;
119 
120  dividend_dwords[3] = hi_dword(dividend_hi);
121  dividend_dwords[2] = lo_dword(dividend_hi);
122  dividend_dwords[1] = hi_dword(dividend_lo);
123  dividend_dwords[0] = lo_dword(dividend_lo);
124 
125  *quotient_hi = div_with_reminder(dividend_dwords[3], divisor, &remainder) << 32;
126  *quotient_hi |= div_with_reminder(dividend_dwords[2], divisor, &remainder);
127  *quotient_lo = div_with_reminder(dividend_dwords[1], divisor, &remainder) << 32;
128  *quotient_lo |= div_with_reminder(dividend_dwords[0], divisor, &remainder);
129 
130  return remainder;
131 }
132 
133 #define IDENT32(x) ((uint32_t) (x))
134 #define IDENT64(x) ((uint64_t) (x))
135 
136 #define SWAP32(x) ((((uint32_t) (x) & 0x000000ff) << 24) | \
137  (((uint32_t) (x) & 0x0000ff00) << 8) | \
138  (((uint32_t) (x) & 0x00ff0000) >> 8) | \
139  (((uint32_t) (x) & 0xff000000) >> 24))
140 #define SWAP64(x) ((((uint64_t) (x) & 0x00000000000000ff) << 56) | \
141  (((uint64_t) (x) & 0x000000000000ff00) << 40) | \
142  (((uint64_t) (x) & 0x0000000000ff0000) << 24) | \
143  (((uint64_t) (x) & 0x00000000ff000000) << 8) | \
144  (((uint64_t) (x) & 0x000000ff00000000) >> 8) | \
145  (((uint64_t) (x) & 0x0000ff0000000000) >> 24) | \
146  (((uint64_t) (x) & 0x00ff000000000000) >> 40) | \
147  (((uint64_t) (x) & 0xff00000000000000) >> 56))
148 
149 static inline uint32_t ident32(uint32_t x) { return x; }
150 static inline uint64_t ident64(uint64_t x) { return x; }
151 
152 #ifndef __OpenBSD__
153 # if defined(__ANDROID__) && defined(__swap32) && !defined(swap32)
154 # define swap32 __swap32
155 # elif !defined(swap32)
156 static inline uint32_t swap32(uint32_t x) {
157  x = ((x & 0x00ff00ff) << 8) | ((x & 0xff00ff00) >> 8);
158  return (x << 16) | (x >> 16);
159 }
160 # endif
161 # if defined(__ANDROID__) && defined(__swap64) && !defined(swap64)
162 # define swap64 __swap64
163 # elif !defined(swap64)
164 static inline uint64_t swap64(uint64_t x) {
165  x = ((x & 0x00ff00ff00ff00ff) << 8) | ((x & 0xff00ff00ff00ff00) >> 8);
166  x = ((x & 0x0000ffff0000ffff) << 16) | ((x & 0xffff0000ffff0000) >> 16);
167  return (x << 32) | (x >> 32);
168 }
169 # endif
170 #endif /* __OpenBSD__ */
171 
172 #if defined(__GNUC__)
173 #define UNUSED __attribute__((unused))
174 #else
175 #define UNUSED
176 #endif
177 static inline void mem_inplace_ident(void *mem UNUSED, size_t n UNUSED) { }
178 #undef UNUSED
179 
180 static inline void mem_inplace_swap32(void *mem, size_t n) {
181  size_t i;
182  for (i = 0; i < n; i++) {
183  ((uint32_t *) mem)[i] = swap32(((const uint32_t *) mem)[i]);
184  }
185 }
186 static inline void mem_inplace_swap64(void *mem, size_t n) {
187  size_t i;
188  for (i = 0; i < n; i++) {
189  ((uint64_t *) mem)[i] = swap64(((const uint64_t *) mem)[i]);
190  }
191 }
192 
193 static inline void memcpy_ident32(void *dst, const void *src, size_t n) {
194  memcpy(dst, src, 4 * n);
195 }
196 static inline void memcpy_ident64(void *dst, const void *src, size_t n) {
197  memcpy(dst, src, 8 * n);
198 }
199 
200 static inline void memcpy_swap32(void *dst, const void *src, size_t n) {
201  size_t i;
202  for (i = 0; i < n; i++) {
203  ((uint32_t *) dst)[i] = swap32(((const uint32_t *) src)[i]);
204  }
205 }
206 static inline void memcpy_swap64(void *dst, const void *src, size_t n) {
207  size_t i;
208  for (i = 0; i < n; i++) {
209  ((uint64_t *) dst)[i] = swap64(((const uint64_t *) src)[i]);
210  }
211 }
212 
213 #ifdef _MSC_VER
214 # define LITTLE_ENDIAN 1234
215 # define BIG_ENDIAN 4321
216 # define BYTE_ORDER LITTLE_ENDIAN
217 #endif
218 
219 #if !defined(BYTE_ORDER) || !defined(LITTLE_ENDIAN) || !defined(BIG_ENDIAN)
220 static_assert(false, "BYTE_ORDER is undefined. Perhaps, GNU extensions are not enabled");
221 #endif
222 
223 #if BYTE_ORDER == LITTLE_ENDIAN
224 #define SWAP32LE IDENT32
225 #define SWAP32BE SWAP32
226 #define swap32le ident32
227 #define swap32be swap32
228 #define mem_inplace_swap32le mem_inplace_ident
229 #define mem_inplace_swap32be mem_inplace_swap32
230 #define memcpy_swap32le memcpy_ident32
231 #define memcpy_swap32be memcpy_swap32
232 #define SWAP64LE IDENT64
233 #define SWAP64BE SWAP64
234 #define swap64le ident64
235 #define swap64be swap64
236 #define mem_inplace_swap64le mem_inplace_ident
237 #define mem_inplace_swap64be mem_inplace_swap64
238 #define memcpy_swap64le memcpy_ident64
239 #define memcpy_swap64be memcpy_swap64
240 #endif
241 
242 #if BYTE_ORDER == BIG_ENDIAN
243 #define SWAP32BE IDENT32
244 #define SWAP32LE SWAP32
245 #define swap32be ident32
246 #define swap32le swap32
247 #define mem_inplace_swap32be mem_inplace_ident
248 #define mem_inplace_swap32le mem_inplace_swap32
249 #define memcpy_swap32be memcpy_ident32
250 #define memcpy_swap32le memcpy_swap32
251 #define SWAP64BE IDENT64
252 #define SWAP64LE SWAP64
253 #define swap64be ident64
254 #define swap64le swap64
255 #define mem_inplace_swap64be mem_inplace_ident
256 #define mem_inplace_swap64le mem_inplace_swap64
257 #define memcpy_swap64be memcpy_ident64
258 #define memcpy_swap64le memcpy_swap64
259 #endif
unsigned int uint32_t
Definition: stdint.h:126
unsigned __int64 uint64_t
Definition: stdint.h:136
const GenericPointer< typename T::ValueType > T2 T::AllocatorType & a
Definition: pointer.h:1124
void * memcpy(void *a, const void *b, size_t c)
#define UNUSED
Definition: int-util.h:175