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} 435