source: trunk/libtransmission/bitfield.c @ 12932

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

#4506 'crash from memory corruption somewhere called from tr_handshakeDone()' -- possible fix.

  • Property svn:keywords set to Date Rev Author Id
File size: 9.7 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 12932 2011-09-28 16:07:35Z 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        assert( b->alloc_count <= n );
175        memcpy( bits, b->bits, b->alloc_count );
176    } else if( tr_bitfieldHasAll( b ) ) {
177        set_all_true( bits, b->bit_count );
178    }
179
180    *byte_count = n;
181    return bits;
182}
183
184static void
185tr_bitfieldEnsureBitsAlloced( tr_bitfield * b, size_t n )
186{
187    size_t bytes_needed;
188    const bool has_all = tr_bitfieldHasAll( b );
189
190    if( has_all )
191        bytes_needed = get_bytes_needed( MAX( n, b->true_count ) );
192    else
193        bytes_needed = get_bytes_needed( n );
194
195    if( b->alloc_count < bytes_needed )
196    {
197        b->bits = tr_renew( uint8_t, b->bits, bytes_needed );
198        memset( b->bits + b->alloc_count, 0, bytes_needed - b->alloc_count );
199        b->alloc_count = bytes_needed;
200
201        if( has_all )
202            set_all_true( b->bits, b->true_count );
203    }
204}
205
206static void
207tr_bitfieldEnsureNthBitAlloced( tr_bitfield * b, size_t nth )
208{
209    /* count is zero-based, so we need to allocate nth+1 bits before setting the nth */
210    tr_bitfieldEnsureBitsAlloced( b, nth + 1 );
211}
212
213static void
214tr_bitfieldFreeArray( tr_bitfield * b )
215{
216    tr_free( b->bits );
217    b->bits = NULL;
218    b->alloc_count = 0;
219}
220
221static void
222tr_bitfieldSetTrueCount( tr_bitfield * b, size_t n )
223{
224    b->true_count = n;
225
226    if( tr_bitfieldHasAll( b ) || tr_bitfieldHasNone( b ) )
227        tr_bitfieldFreeArray( b );
228
229    assert( tr_bitfieldIsValid(  b ) );
230}
231
232static void
233tr_bitfieldRebuildTrueCount( tr_bitfield * b )
234{
235    tr_bitfieldSetTrueCount( b, countArray( b ) );
236}
237
238static void
239tr_bitfieldIncTrueCount( tr_bitfield * b, int i )
240{
241    tr_bitfieldSetTrueCount( b, b->true_count + i );
242}
243
244/****
245*****
246****/
247
248void
249tr_bitfieldConstruct( tr_bitfield * b, size_t bit_count )
250{
251    b->bit_count = bit_count;
252    b->true_count = 0;
253    b->bits = NULL;
254    b->alloc_count = 0;
255    b->have_all_hint = false;
256    b->have_none_hint = false;
257
258    assert( tr_bitfieldIsValid( b ) );
259}
260
261void
262tr_bitfieldSetHasNone( tr_bitfield * b )
263{
264    tr_bitfieldFreeArray( b );
265    b->true_count = 0;
266    b->have_all_hint = false;
267    b->have_none_hint = true;
268
269    assert( tr_bitfieldIsValid( b ) );
270}
271
272void
273tr_bitfieldSetHasAll( tr_bitfield * b )
274{
275    tr_bitfieldFreeArray( b );
276    b->true_count = b->bit_count;
277    b->have_all_hint = true;
278    b->have_none_hint = false;
279
280    assert( tr_bitfieldIsValid( b ) );
281}
282
283void
284tr_bitfieldSetFromBitfield( tr_bitfield * b, const tr_bitfield * src )
285{
286    if( tr_bitfieldHasAll( src ) )
287        tr_bitfieldSetHasAll( b );
288    else if( tr_bitfieldHasNone( src ) )
289        tr_bitfieldSetHasNone( b );
290    else
291        tr_bitfieldSetRaw( b, src->bits, src->alloc_count, true );
292}
293
294void
295tr_bitfieldSetRaw( tr_bitfield * b, const void * bits, size_t byte_count, bool bounded )
296{
297    tr_bitfieldFreeArray( b );
298    b->true_count = 0;
299
300    if( bounded )
301        byte_count = MIN( byte_count, get_bytes_needed( b->bit_count ) );
302
303    b->bits = tr_memdup( bits, byte_count );
304    b->alloc_count = byte_count;
305
306    if( bounded ) {
307        /* ensure the excess bits are set to '0' */
308        const int excess_bit_count = byte_count*8 - b->bit_count;
309        assert( excess_bit_count >= 0 );
310        assert( excess_bit_count <= 7 );
311        if( excess_bit_count )
312            b->bits[b->alloc_count-1] &= ((0xff) << excess_bit_count);
313    }
314
315    tr_bitfieldRebuildTrueCount( b );
316}
317
318void
319tr_bitfieldSetFromFlags( tr_bitfield * b, const bool * flags, size_t n )
320{
321    size_t i;
322    size_t trueCount = 0;
323
324    tr_bitfieldFreeArray( b );
325    tr_bitfieldEnsureBitsAlloced( b, n );
326
327    for( i=0; i<n; ++i )
328    {
329        if( flags[i] )
330        {
331            ++trueCount;
332            b->bits[i >> 3u] |= ( 0x80 >> ( i & 7u ) );
333        }
334    }
335
336    tr_bitfieldSetTrueCount( b, trueCount );
337}
338
339void
340tr_bitfieldAdd( tr_bitfield * b, size_t nth )
341{
342    if( !tr_bitfieldHas( b, nth ) )
343    {
344        tr_bitfieldEnsureNthBitAlloced( b, nth );
345        b->bits[nth >> 3u] |= ( 0x80 >> ( nth & 7u ) );
346        tr_bitfieldIncTrueCount( b, 1 );
347    }
348}
349
350/* Sets bit range [begin, end) to 1 */
351void
352tr_bitfieldAddRange( tr_bitfield * b, size_t begin, size_t end )
353{
354    size_t sb, eb;
355    unsigned char sm, em;
356    const size_t diff = (end-begin) - tr_bitfieldCountRange( b, begin, end );
357
358    if( diff == 0 )
359        return;
360
361    end--;
362    if( ( end >= b->bit_count ) || ( begin > end ) )
363        return;
364
365    sb = begin >> 3;
366    sm = ~( 0xff << ( 8 - ( begin & 7 ) ) );
367    eb = end >> 3;
368    em = 0xff << ( 7 - ( end & 7 ) );
369
370    tr_bitfieldEnsureNthBitAlloced( b, end );
371    if( sb == eb )
372    {
373        b->bits[sb] |= ( sm & em );
374    }
375    else
376    {
377        b->bits[sb] |= sm;
378        b->bits[eb] |= em;
379        if( ++sb < eb )
380            memset ( b->bits + sb, 0xff, eb - sb );
381    }
382
383    tr_bitfieldIncTrueCount( b, diff );
384}
385
386void
387tr_bitfieldRem( tr_bitfield * b, size_t nth )
388{
389    assert( tr_bitfieldIsValid( b ) );
390
391    if( !tr_bitfieldHas( b, nth ) )
392    {
393        tr_bitfieldEnsureNthBitAlloced( b, nth );
394        b->bits[nth >> 3u] &= ( 0xff7f >> ( nth & 7u ) );
395        tr_bitfieldIncTrueCount( b, -1 );
396    }
397}
398
399/* Clears bit range [begin, end) to 0 */
400void
401tr_bitfieldRemRange( tr_bitfield * b, size_t begin, size_t end )
402{
403    size_t sb, eb;
404    unsigned char sm, em;
405    const size_t diff = tr_bitfieldCountRange( b, begin, end );
406
407    if( !diff )
408        return;
409
410    end--;
411
412    if( ( end >= b->bit_count ) || ( begin > end ) )
413        return;
414
415    sb = begin >> 3;
416    sm = 0xff << ( 8 - ( begin & 7 ) );
417    eb = end >> 3;
418    em = ~( 0xff << ( 7 - ( end & 7 ) ) );
419
420    tr_bitfieldEnsureNthBitAlloced( b, end );
421    if( sb == eb )
422    {
423        b->bits[sb] &= ( sm | em );
424    }
425    else
426    {
427        b->bits[sb] &= sm;
428        b->bits[eb] &= em;
429        if( ++sb < eb )
430            memset ( b->bits + sb, 0, eb - sb );
431    }
432
433    tr_bitfieldIncTrueCount( b, -diff );
434}
Note: See TracBrowser for help on using the repository browser.