source: trunk/libtransmission/bitfield.c @ 12921

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

(trunk libt) in tr_bitfieldSetRaw(), add a `bounded' argument for cases where we know how large the final bitfield will be. This can be used ensure that the excess bits at the end of the array are zeroed out and safe for bitfield.c's countArray() function.

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