source: trunk/libtransmission/bitfield.c @ 9671

Last change on this file since 9671 was 9671, checked in by charles, 12 years ago

(trunk) update the copyright notices

File size: 5.8 KB
Line 
1/*
2 * This file Copyright (C) 2009 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: utils.c 8686 2009-06-14 01:01:46Z charles $
11 */
12
13#include <assert.h>
14#include <string.h> /* memset */
15
16#include "transmission.h"
17#include "bitfield.h"
18
19tr_bitfield*
20tr_bitfieldConstruct( tr_bitfield * b, size_t bitCount )
21{
22    b->bitCount = bitCount;
23    b->byteCount = ( bitCount + 7u ) / 8u;
24    b->bits = tr_new0( uint8_t, b->byteCount );
25    return b;
26}
27
28tr_bitfield*
29tr_bitfieldDestruct( tr_bitfield * b )
30{
31    if( b )
32        tr_free( b->bits );
33    return b;
34}
35
36tr_bitfield*
37tr_bitfieldDup( const tr_bitfield * in )
38{
39    tr_bitfield * ret = tr_new0( tr_bitfield, 1 );
40
41    ret->bitCount = in->bitCount;
42    ret->byteCount = in->byteCount;
43    ret->bits = tr_memdup( in->bits, in->byteCount );
44    return ret;
45}
46
47void
48tr_bitfieldClear( tr_bitfield * bitfield )
49{
50    memset( bitfield->bits, 0, bitfield->byteCount );
51}
52
53int
54tr_bitfieldIsEmpty( const tr_bitfield * bitfield )
55{
56    size_t i;
57
58    for( i = 0; i < bitfield->byteCount; ++i )
59        if( bitfield->bits[i] )
60            return 0;
61
62    return 1;
63}
64
65int
66tr_bitfieldAdd( tr_bitfield * bitfield,
67                size_t        nth )
68{
69    assert( bitfield );
70    assert( bitfield->bits );
71
72    if( nth >= bitfield->bitCount )
73        return -1;
74
75    bitfield->bits[nth >> 3u] |= ( 0x80 >> ( nth & 7u ) );
76    return 0;
77}
78
79/* Sets bit range [begin, end) to 1 */
80int
81tr_bitfieldAddRange( tr_bitfield * b,
82                     size_t        begin,
83                     size_t        end )
84{
85    size_t        sb, eb;
86    unsigned char sm, em;
87
88    end--;
89
90    if( ( end >= b->bitCount ) || ( begin > end ) )
91        return -1;
92
93    sb = begin >> 3;
94    sm = ~( 0xff << ( 8 - ( begin & 7 ) ) );
95    eb = end >> 3;
96    em = 0xff << ( 7 - ( end & 7 ) );
97
98    if( sb == eb )
99    {
100        b->bits[sb] |= ( sm & em );
101    }
102    else
103    {
104        b->bits[sb] |= sm;
105        b->bits[eb] |= em;
106        if( ++sb < eb )
107            memset ( b->bits + sb, 0xff, eb - sb );
108    }
109
110    return 0;
111}
112
113int
114tr_bitfieldRem( tr_bitfield * bitfield,
115                size_t        nth )
116{
117    assert( bitfield );
118    assert( bitfield->bits );
119
120    if( nth >= bitfield->bitCount )
121        return -1;
122
123    bitfield->bits[nth >> 3u] &= ( 0xff7f >> ( nth & 7u ) );
124    return 0;
125}
126
127/* Clears bit range [begin, end) to 0 */
128int
129tr_bitfieldRemRange( tr_bitfield * b,
130                     size_t        begin,
131                     size_t        end )
132{
133    size_t        sb, eb;
134    unsigned char sm, em;
135
136    end--;
137
138    if( ( end >= b->bitCount ) || ( begin > end ) )
139        return -1;
140
141    sb = begin >> 3;
142    sm = 0xff << ( 8 - ( begin & 7 ) );
143    eb = end >> 3;
144    em = ~( 0xff << ( 7 - ( end & 7 ) ) );
145
146    if( sb == eb )
147    {
148        b->bits[sb] &= ( sm | em );
149    }
150    else
151    {
152        b->bits[sb] &= sm;
153        b->bits[eb] &= em;
154        if( ++sb < eb )
155            memset ( b->bits + sb, 0, eb - sb );
156    }
157
158    return 0;
159}
160
161tr_bitfield*
162tr_bitfieldOr( tr_bitfield *       a,
163               const tr_bitfield * b )
164{
165    uint8_t * ait;
166    const uint8_t *aend, *bit, *bend;
167
168    for( ait = a->bits, aend = ait + a->byteCount,
169         bit = b->bits, bend = bit + b->byteCount;
170         ait != aend && bit != bend; )
171    {
172        *ait++ |= *bit++;
173    }
174
175    return a;
176}
177
178/* set 'a' to all the flags that were in 'a' but not 'b' */
179void
180tr_bitfieldDifference( tr_bitfield *       a,
181                       const tr_bitfield * b )
182{
183    uint8_t *      ait;
184    const uint8_t *aend, *bit;
185
186    assert( a->byteCount == b->byteCount );
187
188    for( ait = a->bits, bit = b->bits, aend = ait + a->byteCount;
189         ait != aend; )
190        *ait++ &= ~( *bit++ );
191}
192
193size_t
194tr_bitfieldCountTrueBits( const tr_bitfield* b )
195{
196    size_t           ret = 0;
197    const uint8_t *  it, *end;
198    static const int trueBitCount[512] = {
199        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
200        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
201        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
202        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
203        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
204        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
205        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
206        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
207        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
208        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
209        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
210        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
211        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
212        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
213        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
214        4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, 5, 6, 6, 7, 6, 7, 7, 8, 6, 7, 7, 8, 7, 8, 8, 9
215    };
216
217    if( !b )
218        return 0;
219
220    for( it = b->bits, end = it + b->byteCount; it != end; ++it )
221        ret += trueBitCount[*it];
222
223    return ret;
224}
Note: See TracBrowser for help on using the repository browser.