1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
|
// Copyright 2014 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "src/base/bits.h"
#include <limits>
#include "src/base/logging.h"
namespace v8 {
namespace base {
namespace bits {
uint32_t RoundUpToPowerOfTwo32(uint32_t value) {
DCHECK_LE(value, uint32_t{1} << 31);
if (value) --value;
// Use computation based on leading zeros if we have compiler support for that.
#if V8_HAS_BUILTIN_CLZ || V8_CC_MSVC
return 1u << (32 - CountLeadingZeros(value));
#else
value |= value >> 1;
value |= value >> 2;
value |= value >> 4;
value |= value >> 8;
value |= value >> 16;
return value + 1;
#endif
}
uint64_t RoundUpToPowerOfTwo64(uint64_t value) {
DCHECK_LE(value, uint64_t{1} << 63);
if (value) --value;
// Use computation based on leading zeros if we have compiler support for that.
#if V8_HAS_BUILTIN_CLZ
return uint64_t{1} << (64 - CountLeadingZeros(value));
#else
value |= value >> 1;
value |= value >> 2;
value |= value >> 4;
value |= value >> 8;
value |= value >> 16;
value |= value >> 32;
return value + 1;
#endif
}
int32_t SignedMulHigh32(int32_t lhs, int32_t rhs) {
int64_t const value = static_cast<int64_t>(lhs) * static_cast<int64_t>(rhs);
return base::bit_cast<int32_t, uint32_t>(base::bit_cast<uint64_t>(value) >>
32u);
}
// The algorithm used is described in section 8.2 of
// Hacker's Delight, by Henry S. Warren, Jr.
// It assumes that a right shift on a signed integer is an arithmetic shift.
int64_t SignedMulHigh64(int64_t u, int64_t v) {
uint64_t u0 = u & 0xFFFFFFFF;
int64_t u1 = u >> 32;
uint64_t v0 = v & 0xFFFFFFFF;
int64_t v1 = v >> 32;
uint64_t w0 = u0 * v0;
int64_t t = u1 * v0 + (w0 >> 32);
int64_t w1 = t & 0xFFFFFFFF;
int64_t w2 = t >> 32;
w1 = u0 * v1 + w1;
return u1 * v1 + w2 + (w1 >> 32);
}
// The algorithm used is described in section 8.2 of
// Hacker's Delight, by Henry S. Warren, Jr.
uint64_t UnsignedMulHigh64(uint64_t u, uint64_t v) {
uint64_t u0 = u & 0xFFFFFFFF;
uint64_t u1 = u >> 32;
uint64_t v0 = v & 0xFFFFFFFF;
uint64_t v1 = v >> 32;
uint64_t w0 = u0 * v0;
uint64_t t = u1 * v0 + (w0 >> 32);
uint64_t w1 = t & 0xFFFFFFFFLL;
uint64_t w2 = t >> 32;
w1 = u0 * v1 + w1;
return u1 * v1 + w2 + (w1 >> 32);
}
uint32_t UnsignedMulHigh32(uint32_t lhs, uint32_t rhs) {
uint64_t const value =
static_cast<uint64_t>(lhs) * static_cast<uint64_t>(rhs);
return static_cast<uint32_t>(value >> 32u);
}
int32_t SignedMulHighAndAdd32(int32_t lhs, int32_t rhs, int32_t acc) {
return base::bit_cast<int32_t>(
base::bit_cast<uint32_t>(acc) +
base::bit_cast<uint32_t>(SignedMulHigh32(lhs, rhs)));
}
int32_t SignedDiv32(int32_t lhs, int32_t rhs) {
if (rhs == 0) return 0;
if (rhs == -1) return lhs == std::numeric_limits<int32_t>::min() ? lhs : -lhs;
return lhs / rhs;
}
int64_t SignedDiv64(int64_t lhs, int64_t rhs) {
if (rhs == 0) return 0;
if (rhs == -1) return lhs == std::numeric_limits<int64_t>::min() ? lhs : -lhs;
return lhs / rhs;
}
int32_t SignedMod32(int32_t lhs, int32_t rhs) {
if (rhs == 0 || rhs == -1) return 0;
return lhs % rhs;
}
int64_t SignedMod64(int64_t lhs, int64_t rhs) {
if (rhs == 0 || rhs == -1) return 0;
return lhs % rhs;
}
int64_t SignedSaturatedAdd64(int64_t lhs, int64_t rhs) {
using limits = std::numeric_limits<int64_t>;
// Underflow if {lhs + rhs < min}. In that case, return {min}.
if (rhs < 0 && lhs < limits::min() - rhs) return limits::min();
// Overflow if {lhs + rhs > max}. In that case, return {max}.
if (rhs >= 0 && lhs > limits::max() - rhs) return limits::max();
return lhs + rhs;
}
int64_t SignedSaturatedSub64(int64_t lhs, int64_t rhs) {
using limits = std::numeric_limits<int64_t>;
// Underflow if {lhs - rhs < min}. In that case, return {min}.
if (rhs > 0 && lhs < limits::min() + rhs) return limits::min();
// Overflow if {lhs - rhs > max}. In that case, return {max}.
if (rhs <= 0 && lhs > limits::max() + rhs) return limits::max();
return lhs - rhs;
}
} // namespace bits
} // namespace base
} // namespace v8
|
