klee
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Bits.h
Go to the documentation of this file.
1 //===-- Bits.h --------------------------------------------------*- C++ -*-===//
2 //
3 // The KLEE Symbolic Virtual Machine
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #ifndef KLEE_UTIL_BITS_H
11 #define KLEE_UTIL_BITS_H
12 
13 #include "klee/Config/Version.h"
14 #include "llvm/Support/DataTypes.h"
15 
16 namespace klee {
17  namespace bits32 {
18  // @pre(0 <= N <= 32)
19  // @post(retval = max([truncateToNBits(i,N) for i in naturals()]))
20  inline unsigned maxValueOfNBits(unsigned N) {
21  if (N==0)
22  return 0;
23  return ((unsigned) -1) >> (32 - N);
24  }
25 
26  // @pre(0 < N <= 32)
27  inline unsigned truncateToNBits(unsigned x, unsigned N) {
28  return x&(((unsigned) -1) >> (32 - N));
29  }
30 
31  inline unsigned withoutRightmostBit(unsigned x) {
32  return x&(x-1);
33  }
34 
35  inline unsigned isolateRightmostBit(unsigned x) {
36  return x&-x;
37  }
38 
39  inline unsigned isPowerOfTwo(unsigned x) {
40  if (x==0) return 0;
41  return !(x&(x-1));
42  }
43 
44  // @pre(withoutRightmostBit(x) == 0)
45  // @post((1 << retval) == x)
46  inline unsigned indexOfSingleBit(unsigned x) {
47  unsigned res = 0;
48  if (x&0xFFFF0000) res += 16;
49  if (x&0xFF00FF00) res += 8;
50  if (x&0xF0F0F0F0) res += 4;
51  if (x&0xCCCCCCCC) res += 2;
52  if (x&0xAAAAAAAA) res += 1;
53  return res;
54  }
55 
56  inline unsigned indexOfRightmostBit(unsigned x) {
58  }
59  }
60 
61  namespace bits64 {
62  // @pre(0 <= N <= 32)
63  // @post(retval = max([truncateToNBits(i,N) for i in naturals()]))
64  inline uint64_t maxValueOfNBits(unsigned N) {
65  if (N==0)
66  return 0;
67  return ((uint64_t) (int64_t) -1) >> (64 - N);
68  }
69 
70  // @pre(0 < N <= 64)
71  inline uint64_t truncateToNBits(uint64_t x, unsigned N) {
72  return x&(((uint64_t) (int64_t) -1) >> (64 - N));
73  }
74 
75  inline uint64_t withoutRightmostBit(uint64_t x) {
76  return x&(x-1);
77  }
78 
79  inline uint64_t isolateRightmostBit(uint64_t x) {
80  return x&-x;
81  }
82 
83  inline uint64_t isPowerOfTwo(uint64_t x) {
84  if (x==0) return 0;
85  return !(x&(x-1));
86  }
87 
88  // @pre((x&(x-1)) == 0)
89  // @post((1 << retval) == x)
90  inline unsigned indexOfSingleBit(uint64_t x) {
91  unsigned res = bits32::indexOfSingleBit((unsigned) (x | (x>>32)));
92  if (x&((uint64_t) 0xFFFFFFFF << 32))
93  res += 32;
94  return res;
95  }
96 
97  inline uint64_t indexOfRightmostBit(uint64_t x) {
99  }
100  }
101 } // End klee namespace
102 
103 #endif
unsigned withoutRightmostBit(unsigned x)
Definition: Bits.h:31
uint64_t maxValueOfNBits(unsigned N)
Definition: Bits.h:64
unsigned isPowerOfTwo(unsigned x)
Definition: Bits.h:39
unsigned maxValueOfNBits(unsigned N)
Definition: Bits.h:20
unsigned truncateToNBits(unsigned x, unsigned N)
Definition: Bits.h:27
uint64_t isPowerOfTwo(uint64_t x)
Definition: Bits.h:83
unsigned indexOfSingleBit(unsigned x)
Definition: Bits.h:46
uint64_t isolateRightmostBit(uint64_t x)
Definition: Bits.h:79
unsigned indexOfSingleBit(uint64_t x)
Definition: Bits.h:90
uint64_t truncateToNBits(uint64_t x, unsigned N)
Definition: Bits.h:71
unsigned isolateRightmostBit(unsigned x)
Definition: Bits.h:35
uint64_t withoutRightmostBit(uint64_t x)
Definition: Bits.h:75
uint64_t indexOfRightmostBit(uint64_t x)
Definition: Bits.h:97
unsigned indexOfRightmostBit(unsigned x)
Definition: Bits.h:56