source: trunk/libtransmission/bitfield.c @ 12252

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

(trunk libT) fix bitfield assertion failure due to invalid assumption in tr_bitfieldIsValid()

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