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
29namespace vixl {
30
31
32int 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
42int 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
77int 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
112int 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