← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to include/my_bit.h

  • Committer: brian
  • Date: 2008-06-25 05:29:13 UTC
  • Revision ID: brian@localhost.localdomain-20080625052913-6upwo0jsrl4lnapl
clean slate

Show diffs side-by-side

added added

removed removed

Lines of Context:
include/my_bit.h
 
1
/*
 
2
  Some useful bit functions
 
3
*/
 
4
 
 
5
C_MODE_START
 
6
#ifdef HAVE_INLINE
 
7
 
 
8
extern const char _my_bits_nbits[256];
 
9
extern const uchar _my_bits_reverse_table[256];
 
10
 
 
11
/*
 
12
  Find smallest X in 2^X >= value
 
13
  This can be used to divide a number with value by doing a shift instead
 
14
*/
 
15
 
 
16
STATIC_INLINE uint my_bit_log2(ulong value)
 
17
{
 
18
  uint bit;
 
19
  for (bit=0 ; value > 1 ; value>>=1, bit++) ;
 
20
  return bit;
 
21
}
 
22
 
 
23
STATIC_INLINE uint my_count_bits(ulonglong v)
 
24
{
 
25
#if SIZEOF_LONG_LONG > 4
 
26
  /* The following code is a bit faster on 16 bit machines than if we would
 
27
     only shift v */
 
28
  ulong v2=(ulong) (v >> 32);
 
29
  return (uint) (uchar) (_my_bits_nbits[(uchar)  v] +
 
30
                         _my_bits_nbits[(uchar) (v >> 8)] +
 
31
                         _my_bits_nbits[(uchar) (v >> 16)] +
 
32
                         _my_bits_nbits[(uchar) (v >> 24)] +
 
33
                         _my_bits_nbits[(uchar) (v2)] +
 
34
                         _my_bits_nbits[(uchar) (v2 >> 8)] +
 
35
                         _my_bits_nbits[(uchar) (v2 >> 16)] +
 
36
                         _my_bits_nbits[(uchar) (v2 >> 24)]);
 
37
#else
 
38
  return (uint) (uchar) (_my_bits_nbits[(uchar)  v] +
 
39
                         _my_bits_nbits[(uchar) (v >> 8)] +
 
40
                         _my_bits_nbits[(uchar) (v >> 16)] +
 
41
                         _my_bits_nbits[(uchar) (v >> 24)]);
 
42
#endif
 
43
}
 
44
 
 
45
STATIC_INLINE uint my_count_bits_ushort(ushort v)
 
46
{
 
47
  return _my_bits_nbits[v];
 
48
}
 
49
 
 
50
 
 
51
/*
 
52
  Next highest power of two
 
53
 
 
54
  SYNOPSIS
 
55
    my_round_up_to_next_power()
 
56
    v           Value to check
 
57
 
 
58
  RETURN
 
59
    Next or equal power of 2
 
60
    Note: 0 will return 0
 
61
 
 
62
  NOTES
 
63
    Algorithm by Sean Anderson, according to:
 
64
    http://graphics.stanford.edu/~seander/bithacks.html
 
65
    (Orignal code public domain)
 
66
 
 
67
    Comments shows how this works with 01100000000000000000000000001011
 
68
*/
 
69
 
 
70
STATIC_INLINE uint32 my_round_up_to_next_power(uint32 v)
 
71
{
 
72
  v--;                  /* 01100000000000000000000000001010 */
 
73
  v|= v >> 1;           /* 01110000000000000000000000001111 */
 
74
  v|= v >> 2;           /* 01111100000000000000000000001111 */
 
75
  v|= v >> 4;           /* 01111111110000000000000000001111 */
 
76
  v|= v >> 8;           /* 01111111111111111100000000001111 */
 
77
  v|= v >> 16;          /* 01111111111111111111111111111111 */
 
78
  return v+1;           /* 10000000000000000000000000000000 */
 
79
}
 
80
 
 
81
STATIC_INLINE uint32 my_clear_highest_bit(uint32 v)
 
82
{
 
83
  uint32 w=v >> 1;
 
84
  w|= w >> 1;
 
85
  w|= w >> 2;
 
86
  w|= w >> 4;
 
87
  w|= w >> 8;
 
88
  w|= w >> 16;
 
89
  return v & w;
 
90
}
 
91
 
 
92
STATIC_INLINE uint32 my_reverse_bits(uint32 key)
 
93
{
 
94
  return
 
95
    (_my_bits_reverse_table[ key      & 255] << 24) |
 
96
    (_my_bits_reverse_table[(key>> 8) & 255] << 16) |
 
97
    (_my_bits_reverse_table[(key>>16) & 255] <<  8) |
 
98
     _my_bits_reverse_table[(key>>24)      ];
 
99
}
 
100
 
 
101
#else  /* HAVE_INLINE */
 
102
extern uint my_bit_log2(ulong value);
 
103
extern uint32 my_round_up_to_next_power(uint32 v);
 
104
uint32 my_clear_highest_bit(uint32 v);
 
105
uint32 my_reverse_bits(uint32 key);
 
106
extern uint my_count_bits(ulonglong v);
 
107
extern uint my_count_bits_ushort(ushort v);
 
108
#endif /* HAVE_INLINE */
 
109
C_MODE_END