source: trunk/libtransmission/bitfield.c @ 9559

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

(trunk libT) fix another edge case for magnet links

File size: 5.8 KB
Line 
1/*
2 * This file Copyright (C) 2009 Charles Kerr <charles@transmissionbt.com>
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;
167
168    assert( a->byteCount == b->byteCount );
169
170    for( ait = a->bits, bit = b->bits, aend = ait + a->byteCount;
171         ait != aend; )
172        *ait++ |= *bit++;
173
174    return a;
175}
176
177/* set 'a' to all the flags that were in 'a' but not 'b' */
178void
179tr_bitfieldDifference( tr_bitfield *       a,
180                       const tr_bitfield * b )
181{
182    uint8_t *      ait;
183    const uint8_t *aend, *bit;
184
185    assert( a->byteCount == b->byteCount );
186
187    for( ait = a->bits, bit = b->bits, aend = ait + a->byteCount;
188         ait != aend; )
189        *ait++ &= ~( *bit++ );
190}
191
192size_t
193tr_bitfieldCountTrueBits( const tr_bitfield* b )
194{
195    size_t           ret = 0;
196    const uint8_t *  it, *end;
197    static const int trueBitCount[512] = {
198        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,
199        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,
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        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,
202        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,
203        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,
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        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,
206        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,
207        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,
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        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,
210        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,
211        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,
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        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
214    };
215
216    if( !b )
217        return 0;
218
219    for( it = b->bits, end = it + b->byteCount; it != end; ++it )
220        ret += trueBitCount[*it];
221
222    return ret;
223}
Note: See TracBrowser for help on using the repository browser.