1 // Copyright 2015, VIXL authors
2 // All rights reserved.
3 //
4 // Redistribution and use in source and binary forms, with or without
5 // modification, are permitted provided that the following conditions are met:
6 //
7 // * Redistributions of source code must retain the above copyright notice,
8 // this list of conditions and the following disclaimer.
9 // * Redistributions in binary form must reproduce the above copyright notice,
10 // this list of conditions and the following disclaimer in the documentation
11 // and/or other materials provided with the distribution.
12 // * Neither the name of ARM Limited nor the names of its contributors may be
13 // used to endorse or promote products derived from this software without
14 // specific prior written permission.
15 //
16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS CONTRIBUTORS "AS IS" AND
17 // ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18 // WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19 // DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
20 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
22 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
23 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
24 // OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
25 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26
27 #include "compiler-intrinsics-vixl.h"
28
29 namespace vixl {
30
31
CountLeadingSignBitsFallBack(int64_t value,int width)32 int CountLeadingSignBitsFallBack(int64_t value, int width) {
33 VIXL_ASSERT(IsPowerOf2(width) && (width <= 64));
34 if (value >= 0) {
35 return CountLeadingZeros(value, width) - 1;
36 } else {
37 return CountLeadingZeros(~value, width) - 1;
38 }
39 }
40
41
CountLeadingZerosFallBack(uint64_t value,int width)42 int CountLeadingZerosFallBack(uint64_t value, int width) {
43 VIXL_ASSERT(IsPowerOf2(width) && (width <= 64));
44 if (value == 0) {
45 return width;
46 }
47 int count = 0;
48 value = value << (64 - width);
49 if ((value & UINT64_C(0xffffffff00000000)) == 0) {
50 count += 32;
51 value = value << 32;
52 }
53 if ((value & UINT64_C(0xffff000000000000)) == 0) {
54 count += 16;
55 value = value << 16;
56 }
57 if ((value & UINT64_C(0xff00000000000000)) == 0) {
58 count += 8;
59 value = value << 8;
60 }
61 if ((value & UINT64_C(0xf000000000000000)) == 0) {
62 count += 4;
63 value = value << 4;
64 }
65 if ((value & UINT64_C(0xc000000000000000)) == 0) {
66 count += 2;
67 value = value << 2;
68 }
69 if ((value & UINT64_C(0x8000000000000000)) == 0) {
70 count += 1;
71 }
72 count += (value == 0);
73 return count;
74 }
75
76
CountSetBitsFallBack(uint64_t value,int width)77 int CountSetBitsFallBack(uint64_t value, int width) {
78 VIXL_ASSERT(IsPowerOf2(width) && (width <= 64));
79
80 // Mask out unused bits to ensure that they are not counted.
81 value &= (UINT64_C(0xffffffffffffffff) >> (64 - width));
82
83 // Add up the set bits.
84 // The algorithm works by adding pairs of bit fields together iteratively,
85 // where the size of each bit field doubles each time.
86 // An example for an 8-bit value:
87 // Bits: h g f e d c b a
88 // \ | \ | \ | \ |
89 // value = h+g f+e d+c b+a
90 // \ | \ |
91 // value = h+g+f+e d+c+b+a
92 // \ |
93 // value = h+g+f+e+d+c+b+a
94 const uint64_t kMasks[] = {
95 UINT64_C(0x5555555555555555),
96 UINT64_C(0x3333333333333333),
97 UINT64_C(0x0f0f0f0f0f0f0f0f),
98 UINT64_C(0x00ff00ff00ff00ff),
99 UINT64_C(0x0000ffff0000ffff),
100 UINT64_C(0x00000000ffffffff),
101 };
102
103 for (unsigned i = 0; i < (sizeof(kMasks) / sizeof(kMasks[0])); i++) {
104 int shift = 1 << i;
105 value = ((value >> shift) & kMasks[i]) + (value & kMasks[i]);
106 }
107
108 return static_cast<int>(value);
109 }
110
111
CountTrailingZerosFallBack(uint64_t value,int width)112 int CountTrailingZerosFallBack(uint64_t value, int width) {
113 VIXL_ASSERT(IsPowerOf2(width) && (width <= 64));
114 int count = 0;
115 value = value << (64 - width);
116 if ((value & UINT64_C(0xffffffff)) == 0) {
117 count += 32;
118 value = value >> 32;
119 }
120 if ((value & 0xffff) == 0) {
121 count += 16;
122 value = value >> 16;
123 }
124 if ((value & 0xff) == 0) {
125 count += 8;
126 value = value >> 8;
127 }
128 if ((value & 0xf) == 0) {
129 count += 4;
130 value = value >> 4;
131 }
132 if ((value & 0x3) == 0) {
133 count += 2;
134 value = value >> 2;
135 }
136 if ((value & 0x1) == 0) {
137 count += 1;
138 }
139 count += (value == 0);
140 return count - (64 - width);
141 }
142
143
144 } // namespace vixl
145