← 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
 
/* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-
2
 
 *  vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
3
 
 *
4
 
 *  Copyright (C) 2008, 2009 Sun Microsystems
5
 
 *
6
 
 *  This program is free software; you can redistribute it and/or modify
7
 
 *  it under the terms of the GNU General Public License as published by
8
 
 *  the Free Software Foundation; version 2 of the License.
9
 
 *
10
 
 *  This program is distributed in the hope that it will be useful,
11
 
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
12
 
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13
 
 *  GNU General Public License for more details.
14
 
 *
15
 
 *  You should have received a copy of the GNU General Public License
16
 
 *  along with this program; if not, write to the Free Software
17
 
 *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
18
 
 */
19
 
 
20
1
/*
21
2
  Some useful bit functions
22
3
*/
23
4
 
24
 
#ifndef DRIZZLED_INTERNAL_MY_BIT_H
25
 
#define DRIZZLED_INTERNAL_MY_BIT_H
26
 
 
27
 
namespace drizzled
28
 
{
29
 
namespace internal
30
 
{
 
5
C_MODE_START
 
6
#ifdef HAVE_INLINE
31
7
 
32
8
extern const char _my_bits_nbits[256];
33
 
extern const unsigned char _my_bits_reverse_table[256];
 
9
extern const uchar _my_bits_reverse_table[256];
34
10
 
35
11
/*
36
12
  Find smallest X in 2^X >= value
37
13
  This can be used to divide a number with value by doing a shift instead
38
14
*/
39
15
 
40
 
static inline uint32_t my_bit_log2(uint32_t value)
 
16
STATIC_INLINE uint my_bit_log2(ulong value)
41
17
{
42
 
  uint32_t bit;
 
18
  uint bit;
43
19
  for (bit=0 ; value > 1 ; value>>=1, bit++) ;
44
20
  return bit;
45
21
}
46
22
 
47
 
static inline uint32_t my_count_bits(uint64_t v)
 
23
STATIC_INLINE uint my_count_bits(ulonglong v)
48
24
{
 
25
#if SIZEOF_LONG_LONG > 4
49
26
  /* The following code is a bit faster on 16 bit machines than if we would
50
27
     only shift v */
51
 
  uint32_t v2=(uint32_t) (v >> 32);
52
 
  return (uint32_t) (unsigned char) (_my_bits_nbits[(unsigned char)  v] +
53
 
                         _my_bits_nbits[(unsigned char) (v >> 8)] +
54
 
                         _my_bits_nbits[(unsigned char) (v >> 16)] +
55
 
                         _my_bits_nbits[(unsigned char) (v >> 24)] +
56
 
                         _my_bits_nbits[(unsigned char) (v2)] +
57
 
                         _my_bits_nbits[(unsigned char) (v2 >> 8)] +
58
 
                         _my_bits_nbits[(unsigned char) (v2 >> 16)] +
59
 
                         _my_bits_nbits[(unsigned char) (v2 >> 24)]);
 
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
60
43
}
61
44
 
62
 
static inline uint32_t my_count_bits_uint16(uint16_t v)
 
45
STATIC_INLINE uint my_count_bits_ushort(ushort v)
63
46
{
64
47
  return _my_bits_nbits[v];
65
48
}
66
49
 
67
50
 
68
 
static inline uint32_t my_clear_highest_bit(uint32_t v)
69
 
{
70
 
  uint32_t w=v >> 1;
 
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;
71
84
  w|= w >> 1;
72
85
  w|= w >> 2;
73
86
  w|= w >> 4;
76
89
  return v & w;
77
90
}
78
91
 
79
 
static inline uint32_t my_reverse_bits(uint32_t key)
 
92
STATIC_INLINE uint32 my_reverse_bits(uint32 key)
80
93
{
81
94
  return
82
95
    (_my_bits_reverse_table[ key      & 255] << 24) |
85
98
     _my_bits_reverse_table[(key>>24)      ];
86
99
}
87
100
 
88
 
} /* namespace internal */
89
 
} /* namespace drizzled */
90
 
 
91
 
#endif /* DRIZZLED_INTERNAL_MY_BIT_H */
 
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