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 #include "utils-vixl.h"
29
30 namespace vixl {
31
32
CountLeadingSignBitsFallBack(int64_t value,int width)33 int CountLeadingSignBitsFallBack(int64_t value, int width) {
34 VIXL_ASSERT(IsPowerOf2(width) && (width <= 64));
35 if (width < 64) VIXL_ASSERT(IsIntN(width, value));
36 if (value >= 0) {
37 return CountLeadingZeros(value, width) - 1;
38 } else {
39 return CountLeadingZeros(~value, width) - 1;
40 }
41 }
42
43
CountLeadingZerosFallBack(uint64_t value,int width)44 int CountLeadingZerosFallBack(uint64_t value, int width) {
45 VIXL_ASSERT(IsPowerOf2(width) && (width <= 64));
46 if (value == 0) {
47 return width;
48 }
49 int count = 0;
50 value = value << (64 - width);
51 if ((value & UINT64_C(0xffffffff00000000)) == 0) {
52 count += 32;
53 value = value << 32;
54 }
55 if ((value & UINT64_C(0xffff000000000000)) == 0) {
56 count += 16;
57 value = value << 16;
58 }
59 if ((value & UINT64_C(0xff00000000000000)) == 0) {
60 count += 8;
61 value = value << 8;
62 }
63 if ((value & UINT64_C(0xf000000000000000)) == 0) {
64 count += 4;
65 value = value << 4;
66 }
67 if ((value & UINT64_C(0xc000000000000000)) == 0) {
68 count += 2;
69 value = value << 2;
70 }
71 if ((value & UINT64_C(0x8000000000000000)) == 0) {
72 count += 1;
73 }
74 count += (value == 0);
75 return count;
76 }
77
78
CountSetBitsFallBack(uint64_t value,int width)79 int CountSetBitsFallBack(uint64_t value, int width) {
80 VIXL_ASSERT(IsPowerOf2(width) && (width <= 64));
81
82 // Mask out unused bits to ensure that they are not counted.
83 value &= (UINT64_C(0xffffffffffffffff) >> (64 - width));
84
85 // Add up the set bits.
86 // The algorithm works by adding pairs of bit fields together iteratively,
87 // where the size of each bit field doubles each time.
88 // An example for an 8-bit value:
89 // Bits: 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 // \ |
95 // value = h+g+f+e+d+c+b+a
96 const uint64_t kMasks[] = {
97 UINT64_C(0x5555555555555555),
98 UINT64_C(0x3333333333333333),
99 UINT64_C(0x0f0f0f0f0f0f0f0f),
100 UINT64_C(0x00ff00ff00ff00ff),
101 UINT64_C(0x0000ffff0000ffff),
102 UINT64_C(0x00000000ffffffff),
103 };
104
105 for (unsigned i = 0; i < (sizeof(kMasks) / sizeof(kMasks[0])); i++) {
106 int shift = 1 << i;
107 value = ((value >> shift) & kMasks[i]) + (value & kMasks[i]);
108 }
109
110 return static_cast<int>(value);
111 }
112
113
CountTrailingZerosFallBack(uint64_t value,int width)114 int CountTrailingZerosFallBack(uint64_t value, int width) {
115 VIXL_ASSERT(IsPowerOf2(width) && (width <= 64));
116 int count = 0;
117 value = value << (64 - width);
118 if ((value & UINT64_C(0xffffffff)) == 0) {
119 count += 32;
120 value = value >> 32;
121 }
122 if ((value & 0xffff) == 0) {
123 count += 16;
124 value = value >> 16;
125 }
126 if ((value & 0xff) == 0) {
127 count += 8;
128 value = value >> 8;
129 }
130 if ((value & 0xf) == 0) {
131 count += 4;
132 value = value >> 4;
133 }
134 if ((value & 0x3) == 0) {
135 count += 2;
136 value = value >> 2;
137 }
138 if ((value & 0x1) == 0) {
139 count += 1;
140 }
141 count += (value == 0);
142 return count - (64 - width);
143 }
144
145
146 } // namespace vixl
147