1 /* 2 * Copyright (C) 2006-2014 Chris Hamilton <chamilton@cs.dal.ca> 3 * 4 * This library is free software; you can redistribute it and/or 5 * modify it under the terms of the GNU Lesser General Public 6 * License as published by the Free Software Foundation; either 7 * version 2.1 of the License, or (at your option) any later version. 8 * 9 * This library is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 12 * Lesser General Public License for more details. 13 * 14 * You should have received a copy of the GNU Lesser General Public 15 * License along with this library; if not, write to the Free Software 16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 17 */ 18 19 #ifndef _FIXBITVEC_HPP_ 20 #define _FIXBITVEC_HPP_ 21 22 23 #include <inttypes.h> 24 #include "Hilbert/Common.hpp" 25 26 27 // This must be an unsigned integer that is either 28 // 32 or 64 bits. Otherwise, there are places in the 29 // code that simply will not work. 30 // For speed, this should be the native word size. 31 //typedef uint64_t FBV_UINT; 32 //#define FBV_BITS 64 33 typedef uint32_t FBV_UINT; 34 #define FBV_BITS 32 35 36 #define FBV0 ((FBV_UINT)0) 37 #define FBV1 ((FBV_UINT)1) 38 #define FBV1S (~FBV0) 39 #define FBVN1S(n) (n==FBV_BITS?FBV1S:(FBV1<<n)-1) 40 #define FBVMOD(i,m) if((i)>=(m))(i)-=(m)*((i)/(m)); 41 42 43 typedef enum 44 { 45 eFix, 46 eBig 47 } EBitVecType; 48 49 50 class CFixBitVec 51 { 52 public: 53 54 static 55 EBitVecType 56 type(); 57 58 // Default constructor. The bits parameter 59 // is completely ignored, but accepted in order 60 // to look and feel the same as a BigBitVec. 61 CFixBitVec( 62 int iBits = FBV_BITS 63 ); 64 65 // Copy constructor. 66 CFixBitVec( 67 const CFixBitVec &cFBV 68 ); 69 70 // Returns the current size in bits. 71 int 72 getSize(); 73 74 // Sets the size. This is a dummy 75 // function just for BigBitVec compatibility. 76 CFixBitVec & 77 setSize( 78 int iBits 79 ); 80 81 // Zeros the bit-vector. 82 CFixBitVec & 83 zero(); 84 85 // Truncates the bit-vector to a given precision in 86 // bits (zeroes MSBs without shrinking the vector) 87 CFixBitVec & 88 truncate( 89 int iBits 90 ); 91 92 // Assignment operator. 93 CFixBitVec & 94 operator=( 95 const CFixBitVec &cFBV 96 ); 97 98 // Assignment operator. 99 CFixBitVec & 100 operator=( 101 FBV_UINT i 102 ); 103 104 // Returns the value of the nth bit. 105 bool 106 getBit( 107 int iIndex 108 ) const; 109 110 // Sets the value of the nth bit. 111 CFixBitVec & 112 setBit( 113 int iIndex, 114 bool bBit 115 ); 116 117 // Toggles the value of the nth bit. 118 CFixBitVec & 119 toggleBit( 120 int iIndex 121 ); 122 123 // AND operation in place. 124 CFixBitVec & 125 operator&=( 126 const CFixBitVec &cFBV 127 ); 128 129 CFixBitVec & 130 operator&=( 131 FBV_UINT i 132 ); 133 134 // AND operation. 135 CFixBitVec 136 operator&( 137 const CFixBitVec &cFBV 138 ) const; 139 CFixBitVec 140 operator&( 141 FBV_UINT i 142 ); 143 144 // OR operation in place. 145 CFixBitVec & 146 operator|=( 147 const CFixBitVec &cFBV 148 ); 149 CFixBitVec & 150 operator|=( 151 FBV_UINT i 152 ); 153 154 // OR operation. 155 CFixBitVec 156 operator|( 157 const CFixBitVec &cFBV 158 ) const; 159 CFixBitVec 160 operator|( 161 FBV_UINT i 162 ); 163 164 // XOR operation in place. 165 CFixBitVec & 166 operator^=( 167 const CFixBitVec &cFBV 168 ); 169 CFixBitVec & 170 operator^=( 171 FBV_UINT i 172 ); 173 174 // XOR operation. 175 CFixBitVec 176 operator^( 177 const CFixBitVec &cFBV 178 ) const; 179 CFixBitVec 180 operator^( 181 FBV_UINT i 182 ); 183 184 // Shift left operation, in place. 185 CFixBitVec & 186 operator<<=( 187 int iBits 188 ); 189 190 // Shift left operation. 191 CFixBitVec 192 operator<<( 193 int iBits 194 ) const; 195 196 // Shift right operation, in place. 197 CFixBitVec & 198 operator>>=( 199 int iBits 200 ); 201 202 // Shift right operation. 203 CFixBitVec 204 operator>>( 205 int iBits 206 ) const; 207 208 // Right rotation, in place. 209 CFixBitVec & 210 rotr( 211 int iBits, 212 int iWidth = FBV_BITS 213 ); 214 215 // Right rotation. 216 CFixBitVec 217 rotrCopy( 218 int iBits, 219 int iWidth = FBV_BITS 220 ) const; 221 222 // Left rotation, in place. 223 CFixBitVec & 224 rotl( 225 int iBits, 226 int iWidth = FBV_BITS 227 ); 228 229 // Left rotation. 230 CFixBitVec 231 rotlCopy( 232 int iBits, 233 int iWidth = FBV_BITS 234 ) const; 235 236 // Is the bit rack zero valued? 237 bool 238 isZero() const; 239 240 // Returns the number of trailing set bits. 241 int 242 tsb() const; 243 244 // Returns the index of the most significant bit 245 int 246 msb() const; 247 248 // Returns the index of the first set bit, numbered from 249 // 1 to n. 0 means there were no set bits. 250 int 251 fsb() const; 252 253 // Prefix decrement. Returns true if a carry 254 // was generated. 255 bool 256 operator--(); 257 258 // Calculates the Gray Code. 259 CFixBitVec & 260 grayCode(); 261 262 // Calculates the Gray Code Inverse 263 CFixBitVec & 264 grayCodeInv(); 265 266 // Ones-complements the rack 267 CFixBitVec & 268 complement(); 269 270 // Returns the first rack. 271 FBV_UINT & 272 rack(); 273 FBV_UINT 274 rack() const; 275 276 // Return a pointer to the racks 277 FBV_UINT * 278 racks(); 279 const FBV_UINT * 280 racks() const; 281 282 // Returns the number of racks. 283 int 284 rackCount(); 285 286 // Comparison operator 287 bool operator <(const CFixBitVec & other) const288 operator<(const CFixBitVec& other) const 289 { return this->m_uiRack < other.m_uiRack; } 290 291 // Comparison operators 292 bool operator ==(const CFixBitVec & other) const293 operator==(const CFixBitVec& other) const 294 { return this->m_uiRack == other.m_uiRack; } 295 296 bool operator !=(const CFixBitVec & other) const297 operator!=(const CFixBitVec& other) const 298 { return !(*this == other); } 299 300 private: 301 302 static 303 void 304 compileTimeAssertions(); 305 306 FBV_UINT m_uiRack; 307 }; 308 309 310 #endif 311