← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/internal/my_bit.h

  • Committer: Brian Aker
  • Date: 2010-02-10 18:04:24 UTC
  • mfrom: (1286.1.5 build)
  • Revision ID: brian@gaz-20100210180424-03ypoyifmlc2lgcp
Merge of Brian/Padraig

Show diffs side-by-side

added added

removed removed

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