source: trunk/libtransmission/bitfield.c @ 12255

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

(trunk libT) fix bitfield.c assertion failure reported by Rolcol

  • Property svn:keywords set to Date Rev Author Id
File size: 7.8 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 12255 2011-03-29 16:39:30Z jordan $
11 */
12
13#include <assert.h>
14#include <string.h> /* memset */
15
16#include "transmission.h"
17#include "bitfield.h"
18#include "utils.h" /* tr_new0() */
19
20const tr_bitfield TR_BITFIELD_INIT = { NULL, 0, 0, 0, false, false };
21
22/****
23*****
24****/
25
26static const int8_t trueBitCount[256] =
27{
28    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
29    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
30    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
31    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
32    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
33    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
34    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
35    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
36    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
37    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
38    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
39    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
40    2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
41    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
42    3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
43    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
44};
45
46static size_t
47countRange( const tr_bitfield * b, size_t begin, size_t end )
48{
49    size_t ret = 0;
50    const int first_byte = begin >> 3u;
51    const int last_byte = ( end - 1 ) >> 3u;
52
53    if( !b->bit_count )
54        return 0;
55
56    assert( begin < end );
57    assert( b->bits != NULL );
58
59    if( first_byte == last_byte )
60    {
61        int i;
62        uint8_t val = b->bits[first_byte];
63
64        i = begin - (first_byte * 8);
65        val <<= i;
66        val >>= i;
67        i = (last_byte+1)*8 - end;
68        val >>= i;
69        val <<= i;
70
71        ret += trueBitCount[val];
72    }
73    else
74    {
75        int i;
76        uint8_t val;
77
78        /* first byte */
79        i = begin - (first_byte * 8);
80        val = b->bits[first_byte];
81        val <<= i;
82        val >>= i;
83        ret += trueBitCount[val];
84
85        /* middle bytes */
86        for( i=first_byte+1; i<last_byte; ++i )
87            ret += trueBitCount[b->bits[i]];
88
89        /* last byte */
90        i = (last_byte+1)*8 - end;
91        val = b->bits[last_byte];
92        val >>= i;
93        val <<= i;
94        ret += trueBitCount[val];
95    }
96
97    assert( ret <= ( begin - end ) );
98    return ret;
99}
100
101size_t
102tr_bitfieldCountRange( const tr_bitfield * b, size_t begin, size_t end )
103{
104    if( tr_bitfieldHasAll( b ) )
105        return end - begin;
106
107    if( tr_bitfieldHasNone( b ) )
108        return 0;
109
110    return countRange( b, begin, end );
111}
112
113/***
114****
115***/
116
117static bool
118tr_bitfieldIsValid( const tr_bitfield * b )
119{
120    return ( b != NULL )
121        && ( b->byte_count <= b->bit_count )
122        && ( b->true_count <= b->bit_count )
123        && ( !b->bits || ( b->true_count == countRange( b, 0, b->bit_count )));
124}
125
126void*
127tr_bitfieldGetRaw( const tr_bitfield * b, size_t * byte_count )
128{
129    uint8_t * bits;
130
131    if( b->bits )
132    {
133        bits = tr_memdup( b->bits, b->byte_count );
134    }
135    else
136    {
137        assert( tr_bitfieldHasAll( b ) || tr_bitfieldHasNone( b ) );
138
139        bits = tr_new0( uint8_t, b->byte_count );
140
141        if( tr_bitfieldHasAll( b ) )
142        {
143            uint8_t val = 0xFF;
144            const int n = b->byte_count - 1;
145            memset( bits, val, n );
146            bits[n] = val << (b->byte_count*8 - b->bit_count);
147        }
148    }
149
150    *byte_count = b->byte_count;
151    return bits;
152}
153
154static void
155tr_bitfieldEnsureBitsAlloced( tr_bitfield * b )
156{
157    if( b->bits == NULL )
158        b->bits = tr_bitfieldGetRaw( b, &b->byte_count );
159
160    assert( tr_bitfieldIsValid( b ) );
161}
162
163static void
164tr_bitfieldSetTrueCount( tr_bitfield * b, size_t n )
165{
166    b->true_count = n;
167
168    if( tr_bitfieldHasAll( b ) || tr_bitfieldHasNone( b ) )
169    {
170        tr_free( b->bits );
171        b->bits = NULL;
172    }
173
174    assert( tr_bitfieldIsValid(  b ) );
175}
176
177static void
178tr_bitfieldRebuildTrueCount( tr_bitfield * b )
179{
180    tr_bitfieldSetTrueCount( b, countRange( b, 0, b->bit_count ) );
181}
182
183static void
184tr_bitfieldIncTrueCount( tr_bitfield * b, int i )
185{
186    tr_bitfieldSetTrueCount( b, b->true_count + i );
187}
188
189/****
190*****
191****/
192
193void
194tr_bitfieldConstruct( tr_bitfield * b, size_t bit_count )
195{
196    b->bit_count = bit_count;
197    b->byte_count = ( bit_count + 7u ) / 8u;
198    b->true_count = 0;
199    b->bits = NULL;
200    b->have_all_hint = false;
201    b->have_none_hint = false;
202
203    assert( tr_bitfieldIsValid( b ) );
204}
205
206static void
207tr_bitfieldClear( tr_bitfield * b )
208{
209    tr_free( b->bits );
210    b->bits = NULL;
211    b->true_count = 0;
212
213    assert( tr_bitfieldIsValid( b ) );
214}
215
216void
217tr_bitfieldSetHasNone( tr_bitfield * b )
218{
219    tr_bitfieldClear( b );
220    b->have_all_hint = false;
221    b->have_none_hint = true;
222}
223
224void
225tr_bitfieldSetHasAll( tr_bitfield * b )
226{
227    tr_bitfieldClear( b );
228    b->true_count = b->bit_count;
229    b->have_all_hint = true;
230    b->have_none_hint = false;
231}
232
233bool
234tr_bitfieldSetFromBitfield( tr_bitfield * b, const tr_bitfield * src )
235{
236    bool success = true;
237
238    if( tr_bitfieldHasAll( src ) )
239        tr_bitfieldSetHasAll( b );
240    else if( tr_bitfieldHasNone( src ) )
241        tr_bitfieldSetHasNone( b );
242    else
243        success = tr_bitfieldSetRaw( b, src->bits, src->byte_count );
244
245    return success;
246}
247
248bool
249tr_bitfieldSetRaw( tr_bitfield * b, const void * bits, size_t byte_count )
250{
251    const bool success = b->byte_count == byte_count;
252
253    if( success )
254    {
255        tr_bitfieldSetHasNone( b );
256        b->bits = tr_memdup( bits, byte_count );
257        tr_bitfieldRebuildTrueCount( b );
258    }
259
260    return success;
261}
262
263void
264tr_bitfieldAdd( tr_bitfield * b, size_t nth )
265{
266    assert( nth < b->bit_count );
267
268    if( !tr_bitfieldHas( b, nth ) )
269    {
270        tr_bitfieldEnsureBitsAlloced( b );
271        b->bits[nth >> 3u] |= ( 0x80 >> ( nth & 7u ) );
272        tr_bitfieldIncTrueCount( b, 1 );
273    }
274}
275
276/* Sets bit range [begin, end) to 1 */
277void
278tr_bitfieldAddRange( tr_bitfield * b, size_t begin, size_t end )
279{
280    size_t sb, eb;
281    unsigned char sm, em;
282    const size_t diff = (end-begin) - tr_bitfieldCountRange( b, begin, end );
283
284    if( diff == 0 )
285        return;
286
287    end--;
288    if( ( end >= b->bit_count ) || ( begin > end ) )
289        return;
290
291    sb = begin >> 3;
292    sm = ~( 0xff << ( 8 - ( begin & 7 ) ) );
293    eb = end >> 3;
294    em = 0xff << ( 7 - ( end & 7 ) );
295
296    tr_bitfieldEnsureBitsAlloced( b );
297    if( sb == eb )
298    {
299        b->bits[sb] |= ( sm & em );
300    }
301    else
302    {
303        b->bits[sb] |= sm;
304        b->bits[eb] |= em;
305        if( ++sb < eb )
306            memset ( b->bits + sb, 0xff, eb - sb );
307    }
308
309    tr_bitfieldIncTrueCount( b, diff );
310}
311
312void
313tr_bitfieldRem( tr_bitfield * b, size_t nth )
314{
315    assert( tr_bitfieldIsValid( b ) );
316
317    if( !tr_bitfieldHas( b, nth ) )
318    {
319        tr_bitfieldEnsureBitsAlloced( b );
320        b->bits[nth >> 3u] &= ( 0xff7f >> ( nth & 7u ) );
321        tr_bitfieldIncTrueCount( b, -1 );
322    }
323}
324
325/* Clears bit range [begin, end) to 0 */
326void
327tr_bitfieldRemRange( tr_bitfield * b, size_t begin, size_t end )
328{
329    size_t sb, eb;
330    unsigned char sm, em;
331    const size_t diff = tr_bitfieldCountRange( b, begin, end );
332
333    if( !diff )
334        return;
335
336    end--;
337
338    if( ( end >= b->bit_count ) || ( begin > end ) )
339        return;
340
341    sb = begin >> 3;
342    sm = 0xff << ( 8 - ( begin & 7 ) );
343    eb = end >> 3;
344    em = ~( 0xff << ( 7 - ( end & 7 ) ) );
345
346    tr_bitfieldEnsureBitsAlloced( b );
347    if( sb == eb )
348    {
349        b->bits[sb] &= ( sm | em );
350    }
351    else
352    {
353        b->bits[sb] &= sm;
354        b->bits[eb] &= em;
355        if( ++sb < eb )
356            memset ( b->bits + sb, 0, eb - sb );
357    }
358
359    tr_bitfieldIncTrueCount( b, -diff );
360}
Note: See TracBrowser for help on using the repository browser.