source: trunk/libtransmission/bitfield.c @ 12096

Last change on this file since 12096 was 12096, checked in by jordan, 11 years ago

(trunk) copyediting: remove trailing spaces from source code lines in daemon/ gtk/ libtransmission/ and utils/

  • Property svn:keywords set to Date Rev Author Id
File size: 5.5 KB
Line 
1/*
2 * This file Copyright (C) Mnemosyne LLC
3 *
4 * This file is licensed by the GPL version 2. Works owned by the
5 * Transmission project are granted a special exemption to clause 2(b)
6 * so that the bulk of its code can remain under the MIT license.
7 * This exemption does not extend to derived works not owned by
8 * the Transmission project.
9 *
10 * $Id: bitfield.c 12096 2011-03-04 23:26:10Z jordan $
11 */
12
13#include <assert.h>
14#include <string.h> /* memset */
15
16#include "transmission.h"
17#include "bitfield.h"
18#include "bitset.h"
19#include "utils.h" /* tr_new0() */
20
21const tr_bitfield TR_BITFIELD_INIT = { NULL, 0, 0 };
22
23tr_bitfield*
24tr_bitfieldConstruct( tr_bitfield * b, size_t bitCount )
25{
26    b->bitCount = bitCount;
27    b->byteCount = ( bitCount + 7u ) / 8u;
28    b->bits = tr_new0( uint8_t, b->byteCount );
29    return b;
30}
31
32tr_bitfield*
33tr_bitfieldDestruct( tr_bitfield * b )
34{
35    if( b )
36        tr_free( b->bits );
37    return b;
38}
39
40tr_bitfield*
41tr_bitfieldNew( size_t bitCount )
42{
43    return tr_bitfieldConstruct( tr_new( tr_bitfield, 1 ), bitCount );
44}
45
46void
47tr_bitfieldFree( tr_bitfield * b )
48{
49    tr_free( tr_bitfieldDestruct( b ) );
50}
51
52void
53tr_bitfieldClear( tr_bitfield * bitfield )
54{
55    memset( bitfield->bits, 0, bitfield->byteCount );
56}
57
58int
59tr_bitfieldAdd( tr_bitfield * bitfield,
60                size_t        nth )
61{
62    assert( bitfield );
63    assert( bitfield->bits );
64
65    if( nth >= bitfield->bitCount )
66        return -1;
67
68    bitfield->bits[nth >> 3u] |= ( 0x80 >> ( nth & 7u ) );
69    return 0;
70}
71
72/* Sets bit range [begin, end) to 1 */
73int
74tr_bitfieldAddRange( tr_bitfield * b,
75                     size_t        begin,
76                     size_t        end )
77{
78    size_t        sb, eb;
79    unsigned char sm, em;
80
81    end--;
82
83    if( ( end >= b->bitCount ) || ( begin > end ) )
84        return -1;
85
86    sb = begin >> 3;
87    sm = ~( 0xff << ( 8 - ( begin & 7 ) ) );
88    eb = end >> 3;
89    em = 0xff << ( 7 - ( end & 7 ) );
90
91    if( sb == eb )
92    {
93        b->bits[sb] |= ( sm & em );
94    }
95    else
96    {
97        b->bits[sb] |= sm;
98        b->bits[eb] |= em;
99        if( ++sb < eb )
100            memset ( b->bits + sb, 0xff, eb - sb );
101    }
102
103    return 0;
104}
105
106int
107tr_bitfieldRem( tr_bitfield * bitfield,
108                size_t        nth )
109{
110    assert( bitfield );
111    assert( bitfield->bits );
112
113    if( nth >= bitfield->bitCount )
114        return -1;
115
116    bitfield->bits[nth >> 3u] &= ( 0xff7f >> ( nth & 7u ) );
117    return 0;
118}
119
120/* Clears bit range [begin, end) to 0 */
121int
122tr_bitfieldRemRange( tr_bitfield * b,
123                     size_t        begin,
124                     size_t        end )
125{
126    size_t        sb, eb;
127    unsigned char sm, em;
128
129    end--;
130
131    if( ( end >= b->bitCount ) || ( begin > end ) )
132        return -1;
133
134    sb = begin >> 3;
135    sm = 0xff << ( 8 - ( begin & 7 ) );
136    eb = end >> 3;
137    em = ~( 0xff << ( 7 - ( end & 7 ) ) );
138
139    if( sb == eb )
140    {
141        b->bits[sb] &= ( sm | em );
142    }
143    else
144    {
145        b->bits[sb] &= sm;
146        b->bits[eb] &= em;
147        if( ++sb < eb )
148            memset ( b->bits + sb, 0, eb - sb );
149    }
150
151    return 0;
152}
153
154tr_bitfield*
155tr_bitfieldOr( tr_bitfield * a, const tr_bitfield * b )
156{
157    uint8_t * ait = a->bits;
158    const uint8_t * aend = ait + a->byteCount;
159    const uint8_t * bit = b->bits;
160    const uint8_t * bend = bit + b->byteCount;
161
162    while( ait!=aend && bit!=bend )
163        *ait++ |= *bit++;
164
165    return a;
166}
167
168static const int trueBitCount[256] =
169{
170    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
171    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
172    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
173    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
174    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
175    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
176    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
177    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
178    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
179    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
180    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
181    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
182    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
183    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
184    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
185    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
186};
187
188size_t
189tr_bitfieldCountTrueBits( const tr_bitfield* b )
190{
191    size_t           ret = 0;
192    const uint8_t *  it, *end;
193
194    if( !b )
195        return 0;
196
197    for( it = b->bits, end = it + b->byteCount; it != end; ++it )
198        ret += trueBitCount[*it];
199
200    return ret;
201}
202
203size_t
204tr_bitfieldCountRange( const tr_bitfield * b, size_t begin, size_t end )
205{
206    size_t ret = 0;
207    const int first_byte = begin >> 3u;
208    const int last_byte = ( end - 1 ) >> 3u;
209
210    assert( begin < end );
211
212    if( first_byte == last_byte )
213    {
214        int i;
215        uint8_t val = b->bits[first_byte];
216
217        i = begin - (first_byte * 8);
218        val <<= i;
219        val >>= i;
220        i = (last_byte+1)*8 - end;
221        val >>= i;
222        val <<= i;
223
224        ret += trueBitCount[val];
225    }
226    else
227    {
228        int i;
229        uint8_t val;
230
231        /* first byte */
232        i = begin - (first_byte * 8);
233        val = b->bits[first_byte];
234        val <<= i;
235        val >>= i;
236        ret += trueBitCount[val];
237
238        /* middle bytes */
239        for( i=first_byte+1; i<last_byte; ++i )
240            ret += trueBitCount[b->bits[i]];
241
242        /* last byte */
243        i = (last_byte+1)*8 - end;
244        val = b->bits[last_byte];
245        val >>= i;
246        val <<= i;
247        ret += trueBitCount[val];
248    }
249
250    assert( ret <= ( begin - end ) );
251    return ret;
252}
Note: See TracBrowser for help on using the repository browser.