source: proiecte/swift/trunk/lib/hoard-371/src/heaplayers/util/bitindex.h @ 176

Last change on this file since 176 was 176, checked in by (none), 14 years ago
  • imported repo from "guagal"
File size: 1.8 KB
Line 
1/* -*- C++ -*- */
2
3/**
4 * @file bitindex.h
5 *
6 * Bit-access operations, including msb and lsb.
7 * @author Emery Berger (emery@cs.umass.edu)
8*/
9
10// lsb is due to Leiserson, Prokop, Randall (MIT).
11// msb is also a fast implementation of floor(lg_2).
12
13#ifndef _BITINDEX_H_
14#define _BITINDEX_H_
15
16#include <assert.h>
17
18namespace HL {
19
20class BitIndex {
21private:
22 
23  enum { debruijn32 = 0x077CB531UL };
24  static int index32[32];
25  static unsigned long lgtable[16];
26  static unsigned long on[32];
27  static unsigned long off[32];
28
29  void setup (void);
30
31public:
32
33  BitIndex (void);
34  ~BitIndex (void) {}
35
36  // Set bit_index in b (to 1).
37  static void set (unsigned long &b, int index)
38    {
39      assert (index >= 0);
40      assert (index < 32);
41      b |= on[index];
42    }
43
44  // Reset bit_index in b (set it to 0).
45  static void reset (unsigned long &b, int index)
46    {
47      assert (index >= 0);
48      assert (index < 32);
49      b &= off[index];
50    }
51
52  // Find the least-significant bit.
53  static int lsb (unsigned long b)
54    {
55      //#if 0
56#if 0 // i386
57      // Intel x86 code.
58      register unsigned long index = 0;
59      if (b > 0) {
60        asm ("bsfl %1, %0" : "=r" (index) : "r" (b));
61      }
62      return index;
63#else
64      b &= (unsigned long) -((signed long) b);
65      b *= debruijn32;
66      b >>= 27;
67      return index32[b];
68#endif
69    }
70
71  // Find the most-significant bit.
72  static int msb (unsigned long b)
73    {
74#if 0 // i386
75      // Intel x86 code.
76      register unsigned long index = 0;
77      if (b > 0) {
78        asm ("bsrl %1, %0" : "=r" (index) : "r" (b));
79      }
80      return index;
81#else
82      int l = 0;
83      // b < 2^32
84      if (b >= 65536) {
85        l += 16;
86        b >>= 16;
87      }
88      // b < 2^16
89      if (b >= 256) {
90        l += 8;
91        b >>= 8;
92      }
93      // b < 2^8
94      if (b >= 16) {
95        l += 4;
96        b >>= 4;
97      }
98      return l + lgtable[b];
99#endif
100    }
101
102 
103};
104
105};
106
107#endif
Note: See TracBrowser for help on using the repository browser.