Root/monav/utils/bithelpers.h

1/*
2Copyright 2010 Christian Vetter veaac.fdirct@gmail.com
3
4This file is part of MoNav.
5
6MoNav is free software: you can redistribute it and/or modify
7it under the terms of the GNU General Public License as published by
8the Free Software Foundation, either version 3 of the License, or
9(at your option) any later version.
10
11MoNav is distributed in the hope that it will be useful,
12but WITHOUT ANY WARRANTY; without even the implied warranty of
13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14GNU General Public License for more details.
15
16You should have received a copy of the GNU General Public License
17along with MoNav. If not, see <http://www.gnu.org/licenses/>.
18*/
19
20#ifndef BITHELPERS_H
21#define BITHELPERS_H
22
23#include <cstring>
24#include <algorithm>
25
26template< class T >
27static inline T readUnaligned( const char* buffer ) {
28    T temp;
29    memcpy( &temp, buffer, sizeof( T ) );
30    return temp;
31}
32
33// reads first bits to a max of 31 bits ( 31 because 1u << 32 is undefined )
34// offset has to be <8
35// safe with unaligned memory access
36static inline unsigned read_unaligned_unsigned( const unsigned char* buffer, int offset ){
37    assert ( offset <= 7 );
38
39    const int diff = ( ( size_t ) buffer ) & 3;
40    buffer -= diff;
41    offset += 8 * diff;
42
43    unsigned temp = * ( unsigned * ) buffer;
44    if ( offset == 0 )
45        return temp;
46    unsigned temp2 = * ( ( ( unsigned * ) buffer ) + 1);
47    return ( temp >> offset ) | ( temp2 << ( 32 - offset ) );
48}
49
50static inline unsigned read_unaligned_unsigned( const unsigned char** buffer, int bits, int* offset ){
51    assert ( *offset <= 7 );
52
53    const int diff = ( ( size_t ) *buffer ) & 3;
54    const unsigned char* alignedBuffer = *buffer - diff;
55    int alignedOffset = *offset + 8 * diff;
56    unsigned temp = * ( unsigned * ) alignedBuffer;
57    unsigned temp2 = * ( ( ( unsigned * ) alignedBuffer ) + 1);
58    unsigned result;
59    if ( alignedOffset == 0 )
60        result = temp;
61    else
62        result = ( temp >> alignedOffset ) | ( temp2 << ( 32 - alignedOffset ) );
63
64    *offset += bits;
65    *buffer += ( *offset ) >> 3;
66    *offset &= 7;
67
68    if ( bits == 32 )
69        return result;
70
71    return result & ( ( 1u << bits ) - 1 );
72}
73
74static inline unsigned read_unaligned_unsigned( const unsigned char* buffer, int bits, int offset ){
75    assert ( offset <= 7 );
76
77    const int diff = ( ( size_t ) buffer ) & 3;
78    const unsigned char* alignedBuffer = buffer - diff;
79    int alignedOffset = offset + 8 * diff;
80    unsigned temp = * ( unsigned * ) alignedBuffer;
81    unsigned temp2 = * ( ( ( unsigned * ) alignedBuffer ) + 1);
82    unsigned result;
83    if ( alignedOffset == 0 )
84        result = temp;
85    else
86        result = ( temp >> alignedOffset ) | ( temp2 << ( 32 - alignedOffset ) );
87
88    if ( bits == 32 )
89        return result;
90
91    return result & ( ( 1u << bits ) - 1 );
92}
93
94// writes #bits bits of data into the buffer at the offset
95// offset has to be <8, **buffer has to be zeroed
96// modifies buffer and offset to point after the inserted data
97static inline void write_unaligned_unsigned( unsigned char** buffer, unsigned data, int bits, int* offset ) {
98    ( ( unsigned* ) *buffer )[0] |= ( data << ( *offset ) );
99    ( ( unsigned* ) ( *buffer + 1 ) )[0] |= ( data >> ( 8 - *offset ) );
100
101#ifndef NDEBUG
102    const unsigned char* tempBuffer = *buffer;
103    int tempOffset = *offset;
104    unsigned tempData = read_unaligned_unsigned( &tempBuffer, bits, &tempOffset );
105    assert( tempData == data );
106#endif
107
108    *offset += bits;
109    *buffer += ( *offset ) >> 3;
110    *offset &= 7;
111}
112
113static inline unsigned read_bits ( unsigned data, char bits ) {
114    if ( bits == 32 )
115        return data;
116
117    return data & ( ( 1u << bits ) - 1 );
118}
119
120static inline unsigned log2_rounded ( unsigned x ) {
121    static const unsigned bit_position[32] = {
122        0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
123        31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
124    };
125
126    //round up
127    --x;
128    x |= x >> 1;
129    x |= x >> 2;
130    x |= x >> 4;
131    x |= x >> 8;
132    x |= x >> 16;
133    ++x;
134
135    return bit_position[ ( x * 0x077CB531u ) >> 27];
136}
137
138// computes log2_rounded( x + 1 ), works even up to x = 2^32 - 1
139static inline unsigned bits_needed( unsigned x )
140{
141    static const unsigned bit_position[32] = {
142        32, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
143        31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
144    };
145    //slower, maybe think of a better workaround
146    if ( x == 0 )
147        return 0;
148
149    //+1 and round up
150    x |= x >> 1;
151    x |= x >> 2;
152    x |= x >> 4;
153    x |= x >> 8;
154    x |= x >> 16;
155    ++x;
156
157    return bit_position[ ( x * 0x077CB531u ) >> 27];
158}
159
160template< int exponentBits, int significantBits >
161static unsigned decode_integer( unsigned x )
162{
163    if ( x == ( ( 1u << ( exponentBits + significantBits ) ) - 1 ) )
164        return 0;
165    unsigned exponent = x >> significantBits;
166    unsigned significant = x & ( ( 1u << significantBits ) - 1 );
167    significant = ( significant << 1 ) | 1; // implicit 1
168    return significant << exponent;
169}
170
171template< int exponentBits, int significantBits >
172static unsigned encode_integer( unsigned x )
173{
174    assert ( exponentBits > 0 );
175    assert( significantBits > 0 );
176
177    static bool initialized = false;
178    static const unsigned numEncoded = 1u << ( exponentBits + significantBits );
179    typedef std::pair< unsigned, unsigned > Lookup;
180    static Lookup lookup[numEncoded];
181
182    if ( !initialized ) {
183        for ( unsigned value = 0; value < numEncoded; value++ )
184            lookup[value] = Lookup( decode_integer< exponentBits, significantBits >( value ), value );
185        std::sort( lookup, lookup + numEncoded );
186        initialized = true;
187    }
188
189    Lookup* value = std::lower_bound( lookup, lookup + numEncoded, Lookup( x, 0 ) );
190
191    if ( value >= lookup + numEncoded - 1 )
192        return lookup[numEncoded - 1].second;
193
194    unsigned diffFirst = x - value->first;
195    unsigned diffSecond = ( value + 1 )->first - x;
196
197    if ( diffFirst < diffSecond )
198        return value->second;
199    else
200        return ( value + 1 )->second;
201}
202
203#endif // BITHELPERS_H
204

Archive Download this file

Branches:
master



interactive