release/src/router/transmission/libtransmission/bitfield.c

   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 12554 2011-07-17 14:34:33Z 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
  21 const tr_bitfield TR_BITFIELD_INIT = { NULL, 0, 0, 0, false, false };
  22
  23 /****
  24 *****
  25 ****/
  26
  27 static 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
  47 static size_t
  48 countArray( 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
  59 static size_t
  60 countRange( 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
 118 size_t
 119 tr_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
 134 static bool
 135 tr_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
 143 size_t
 144 tr_bitfieldCountTrueBits( const tr_bitfield * b )
 145 {
 146     tr_bitfieldIsValid( b );
 147     return b->true_count;
 148 }
 149
 150 static size_t
 151 get_bytes_needed( size_t bit_count )
 152 {
 153     return ( bit_count + 7u ) / 8u;
 154 }
 155
 156 static void
 157 set_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
 165 void*
 166 tr_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
 182 static void
 183 tr_bitfieldEnsureBitsAlloced( tr_bitfield * b, size_t nth )
 184 {
 185     size_t bytes_needed;
 186     const bool has_all = tr_bitfieldHasAll( b );
 187
 188     assert( tr_bitfieldIsValid( b ) );
 189
 190     if( has_all )
 191         bytes_needed = get_bytes_needed( MAX( nth, b->true_count ) + 1 );
 192     else
 193         bytes_needed = get_bytes_needed( nth + 1 );
 194
 195     if( b->alloc_count < bytes_needed )
 196     {
 197 #ifndef NDEBUG
 198         const size_t old_count = countArray( b );
 199 #endif
 200         b->bits = tr_renew( uint8_t, b->bits, bytes_needed );
 201         memset( b->bits + b->alloc_count, 0, bytes_needed - b->alloc_count );
 202         b->alloc_count = bytes_needed;
 203         assert( old_count == countArray( b ) );
 204
 205         if( has_all )
 206             set_all_true( b->bits, b->true_count );
 207     }
 208
 209     assert( tr_bitfieldIsValid( b ) );
 210 }
 211
 212 static void
 213 tr_bitfieldFreeArray( tr_bitfield * b )
 214 {
 215     tr_free( b->bits );
 216     b->bits = NULL;
 217     b->alloc_count = 0;
 218 }
 219
 220 static void
 221 tr_bitfieldSetTrueCount( tr_bitfield * b, size_t n )
 222 {
 223     b->true_count = n;
 224
 225     if( tr_bitfieldHasAll( b ) || tr_bitfieldHasNone( b ) )
 226         tr_bitfieldFreeArray( b );
 227
 228     assert( tr_bitfieldIsValid(  b ) );
 229 }
 230
 231 static void
 232 tr_bitfieldRebuildTrueCount( tr_bitfield * b )
 233 {
 234     tr_bitfieldSetTrueCount( b, countArray( b ) );
 235 }
 236
 237 static void
 238 tr_bitfieldIncTrueCount( tr_bitfield * b, int i )
 239 {
 240     tr_bitfieldSetTrueCount( b, b->true_count + i );
 241 }
 242
 243 /****
 244 *****
 245 ****/
 246
 247 void
 248 tr_bitfieldConstruct( tr_bitfield * b, size_t bit_count )
 249 {
 250     b->bit_count = bit_count;
 251     b->true_count = 0;
 252     b->bits = NULL;
 253     b->alloc_count = 0;
 254     b->have_all_hint = false;
 255     b->have_none_hint = false;
 256
 257     assert( tr_bitfieldIsValid( b ) );
 258 }
 259
 260 void
 261 tr_bitfieldSetHasNone( tr_bitfield * b )
 262 {
 263     tr_bitfieldFreeArray( b );
 264     b->true_count = 0;
 265     b->have_all_hint = false;
 266     b->have_none_hint = true;
 267
 268     assert( tr_bitfieldIsValid( b ) );
 269 }
 270
 271 void
 272 tr_bitfieldSetHasAll( tr_bitfield * b )
 273 {
 274     tr_bitfieldFreeArray( b );
 275     b->true_count = b->bit_count;
 276     b->have_all_hint = true;
 277     b->have_none_hint = false;
 278
 279     assert( tr_bitfieldIsValid( b ) );
 280 }
 281
 282 void
 283 tr_bitfieldSetFromBitfield( tr_bitfield * b, const tr_bitfield * src )
 284 {
 285     if( tr_bitfieldHasAll( src ) )
 286         tr_bitfieldSetHasAll( b );
 287     else if( tr_bitfieldHasNone( src ) )
 288         tr_bitfieldSetHasNone( b );
 289     else
 290         tr_bitfieldSetRaw( b, src->bits, src->alloc_count );
 291 }
 292
 293 void
 294 tr_bitfieldSetRaw( tr_bitfield * b, const void * bits, size_t byte_count )
 295 {
 296     tr_bitfieldFreeArray( b );
 297     b->true_count = 0;
 298     b->bits = tr_memdup( bits, byte_count );
 299     b->alloc_count = byte_count;
 300     tr_bitfieldRebuildTrueCount( b );
 301 }
 302
 303 void
 304 tr_bitfieldAdd( tr_bitfield * b, size_t nth )
 305 {
 306     if( !tr_bitfieldHas( b, nth ) )
 307     {
 308         tr_bitfieldEnsureBitsAlloced( b, nth );
 309         b->bits[nth >> 3u] |= ( 0x80 >> ( nth & 7u ) );
 310         tr_bitfieldIncTrueCount( b, 1 );
 311     }
 312 }
 313
 314 /* Sets bit range [begin, end) to 1 */
 315 void
 316 tr_bitfieldAddRange( tr_bitfield * b, size_t begin, size_t end )
 317 {
 318     size_t sb, eb;
 319     unsigned char sm, em;
 320     const size_t diff = (end-begin) - tr_bitfieldCountRange( b, begin, end );
 321
 322     if( diff == 0 )
 323         return;
 324
 325     end--;
 326     if( ( end >= b->bit_count ) || ( begin > end ) )
 327         return;
 328
 329     sb = begin >> 3;
 330     sm = ~( 0xff << ( 8 - ( begin & 7 ) ) );
 331     eb = end >> 3;
 332     em = 0xff << ( 7 - ( end & 7 ) );
 333
 334     tr_bitfieldEnsureBitsAlloced( b, end );
 335     if( sb == eb )
 336     {
 337         b->bits[sb] |= ( sm & em );
 338     }
 339     else
 340     {
 341         b->bits[sb] |= sm;
 342         b->bits[eb] |= em;
 343         if( ++sb < eb )
 344             memset ( b->bits + sb, 0xff, eb - sb );
 345     }
 346
 347     tr_bitfieldIncTrueCount( b, diff );
 348 }
 349
 350 void
 351 tr_bitfieldRem( tr_bitfield * b, size_t nth )
 352 {
 353     assert( tr_bitfieldIsValid( b ) );
 354
 355     if( !tr_bitfieldHas( b, nth ) )
 356     {
 357         tr_bitfieldEnsureBitsAlloced( b, nth );
 358         b->bits[nth >> 3u] &= ( 0xff7f >> ( nth & 7u ) );
 359         tr_bitfieldIncTrueCount( b, -1 );
 360     }
 361 }
 362
 363 /* Clears bit range [begin, end) to 0 */
 364 void
 365 tr_bitfieldRemRange( tr_bitfield * b, size_t begin, size_t end )
 366 {
 367     size_t sb, eb;
 368     unsigned char sm, em;
 369     const size_t diff = tr_bitfieldCountRange( b, begin, end );
 370
 371     if( !diff )
 372         return;
 373
 374     end--;
 375
 376     if( ( end >= b->bit_count ) || ( begin > end ) )
 377         return;
 378
 379     sb = begin >> 3;
 380     sm = 0xff << ( 8 - ( begin & 7 ) );
 381     eb = end >> 3;
 382     em = ~( 0xff << ( 7 - ( end & 7 ) ) );
 383
 384     tr_bitfieldEnsureBitsAlloced( b, end );
 385     if( sb == eb )
 386     {
 387         b->bits[sb] &= ( sm | em );
 388     }
 389     else
 390     {
 391         b->bits[sb] &= sm;
 392         b->bits[eb] &= em;
 393         if( ++sb < eb )
 394             memset ( b->bits + sb, 0, eb - sb );
 395     }
 396
 397     tr_bitfieldIncTrueCount( b, -diff );
 398 }