1 /* <!-- copyright */
2 /*
3 * aria2 - The high speed download utility
4 *
5 * Copyright (C) 2006 Tatsuhiro Tsujikawa
6 *
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20 *
21 * In addition, as a special exception, the copyright holders give
22 * permission to link the code of portions of this program with the
23 * OpenSSL library under certain conditions as described in each
24 * individual source file, and distribute linked combinations
25 * including the two.
26 * You must obey the GNU General Public License in all respects
27 * for all of the code used other than OpenSSL. If you modify
28 * file(s) with this exception, you may extend this exception to your
29 * version of the file(s), but you are not obligated to do so. If you
30 * do not wish to do so, delete this exception statement from your
31 * version. If you delete this exception statement from all source
32 * files in the program, then also delete it here.
33 */
34 /* copyright --> */
35 #include "BitfieldMan.h"
36
37 #include <cassert>
38 #include <cstring>
39
40 #include "array_fun.h"
41 #include "bitfield.h"
42
43 using namespace aria2::expr;
44
45 namespace aria2 {
46
BitfieldMan(int32_t blockLength,int64_t totalLength)47 BitfieldMan::BitfieldMan(int32_t blockLength, int64_t totalLength)
48 : totalLength_(totalLength),
49 cachedCompletedLength_(0),
50 cachedFilteredCompletedLength_(0),
51 cachedFilteredTotalLength_(0),
52 bitfield_(nullptr),
53 useBitfield_(nullptr),
54 filterBitfield_(nullptr),
55 bitfieldLength_(0),
56 cachedNumMissingBlock_(0),
57 cachedNumFilteredBlock_(0),
58 blocks_(0),
59 blockLength_(blockLength),
60 filterEnabled_(false)
61 {
62 if (blockLength_ > 0 && totalLength_ > 0) {
63 blocks_ = (totalLength_ + blockLength_ - 1) / blockLength_;
64 bitfieldLength_ = blocks_ / 8 + (blocks_ % 8 ? 1 : 0);
65 bitfield_ = new unsigned char[bitfieldLength_];
66 useBitfield_ = new unsigned char[bitfieldLength_];
67 memset(bitfield_, 0, bitfieldLength_);
68 memset(useBitfield_, 0, bitfieldLength_);
69 updateCache();
70 }
71 }
72
BitfieldMan(const BitfieldMan & bitfieldMan)73 BitfieldMan::BitfieldMan(const BitfieldMan& bitfieldMan)
74 : totalLength_(bitfieldMan.totalLength_),
75 cachedCompletedLength_(0),
76 cachedFilteredCompletedLength_(0),
77 cachedFilteredTotalLength_(0),
78 bitfield_(new unsigned char[bitfieldMan.bitfieldLength_]),
79 useBitfield_(new unsigned char[bitfieldMan.bitfieldLength_]),
80 filterBitfield_(nullptr),
81 bitfieldLength_(bitfieldMan.bitfieldLength_),
82 cachedNumMissingBlock_(0),
83 cachedNumFilteredBlock_(0),
84 blocks_(bitfieldMan.blocks_),
85 blockLength_(bitfieldMan.blockLength_),
86 filterEnabled_(bitfieldMan.filterEnabled_)
87 {
88 memcpy(bitfield_, bitfieldMan.bitfield_, bitfieldLength_);
89 memcpy(useBitfield_, bitfieldMan.useBitfield_, bitfieldLength_);
90 if (filterEnabled_) {
91 filterBitfield_ = new unsigned char[bitfieldLength_];
92 memcpy(filterBitfield_, bitfieldMan.filterBitfield_, bitfieldLength_);
93 }
94 updateCache();
95 }
96
operator =(const BitfieldMan & bitfieldMan)97 BitfieldMan& BitfieldMan::operator=(const BitfieldMan& bitfieldMan)
98 {
99 if (this != &bitfieldMan) {
100 totalLength_ = bitfieldMan.totalLength_;
101 blockLength_ = bitfieldMan.blockLength_;
102 blocks_ = bitfieldMan.blocks_;
103 bitfieldLength_ = bitfieldMan.bitfieldLength_;
104 filterEnabled_ = bitfieldMan.filterEnabled_;
105
106 delete[] bitfield_;
107 bitfield_ = new unsigned char[bitfieldLength_];
108 memcpy(bitfield_, bitfieldMan.bitfield_, bitfieldLength_);
109
110 delete[] useBitfield_;
111 useBitfield_ = new unsigned char[bitfieldLength_];
112 memcpy(useBitfield_, bitfieldMan.useBitfield_, bitfieldLength_);
113
114 delete[] filterBitfield_;
115 if (filterEnabled_) {
116 filterBitfield_ = new unsigned char[bitfieldLength_];
117 memcpy(filterBitfield_, bitfieldMan.filterBitfield_, bitfieldLength_);
118 }
119 else {
120 filterBitfield_ = nullptr;
121 }
122
123 updateCache();
124 }
125 return *this;
126 }
127
~BitfieldMan()128 BitfieldMan::~BitfieldMan()
129 {
130 delete[] bitfield_;
131 delete[] useBitfield_;
132 delete[] filterBitfield_;
133 }
134
getLastBlockLength() const135 int32_t BitfieldMan::getLastBlockLength() const
136 {
137 return totalLength_ - blockLength_ * (blocks_ - 1);
138 }
139
getBlockLength(size_t index) const140 int32_t BitfieldMan::getBlockLength(size_t index) const
141 {
142 if (index == blocks_ - 1) {
143 return getLastBlockLength();
144 }
145 else if (index < blocks_ - 1) {
146 return getBlockLength();
147 }
148 else {
149 return 0;
150 }
151 }
152
hasMissingPiece(const unsigned char * peerBitfield,size_t length) const153 bool BitfieldMan::hasMissingPiece(const unsigned char* peerBitfield,
154 size_t length) const
155 {
156 if (bitfieldLength_ != length) {
157 return false;
158 }
159 bool retval = false;
160 for (size_t i = 0; i < bitfieldLength_; ++i) {
161 unsigned char temp = peerBitfield[i] & ~bitfield_[i];
162 if (filterEnabled_) {
163 temp &= filterBitfield_[i];
164 }
165 if (temp & 0xffu) {
166 retval = true;
167 break;
168 }
169 }
170 return retval;
171 }
172
getFirstMissingUnusedIndex(size_t & index) const173 bool BitfieldMan::getFirstMissingUnusedIndex(size_t& index) const
174 {
175 if (filterEnabled_) {
176 return bitfield::getFirstSetBitIndex(
177 index,
178 ~array(bitfield_) & ~array(useBitfield_) & array(filterBitfield_),
179 blocks_);
180 }
181 else {
182 return bitfield::getFirstSetBitIndex(
183 index, ~array(bitfield_) & ~array(useBitfield_), blocks_);
184 }
185 }
186
getFirstNMissingUnusedIndex(std::vector<size_t> & out,size_t n) const187 size_t BitfieldMan::getFirstNMissingUnusedIndex(std::vector<size_t>& out,
188 size_t n) const
189 {
190 if (filterEnabled_) {
191 return bitfield::getFirstNSetBitIndex(
192 std::back_inserter(out), n,
193 ~array(bitfield_) & ~array(useBitfield_) & array(filterBitfield_),
194 blocks_);
195 }
196 else {
197 return bitfield::getFirstNSetBitIndex(
198 std::back_inserter(out), n, ~array(bitfield_) & ~array(useBitfield_),
199 blocks_);
200 }
201 }
202
getFirstMissingIndex(size_t & index) const203 bool BitfieldMan::getFirstMissingIndex(size_t& index) const
204 {
205 if (filterEnabled_) {
206 return bitfield::getFirstSetBitIndex(
207 index, ~array(bitfield_) & array(filterBitfield_), blocks_);
208 }
209 else {
210 return bitfield::getFirstSetBitIndex(index, ~array(bitfield_), blocks_);
211 }
212 }
213
214 namespace {
215 template <typename Array>
getStartIndex(size_t index,const Array & bitfield,size_t blocks)216 size_t getStartIndex(size_t index, const Array& bitfield, size_t blocks)
217 {
218 while (index < blocks && bitfield::test(bitfield, blocks, index)) {
219 ++index;
220 }
221 if (blocks <= index) {
222 return blocks;
223 }
224 else {
225 return index;
226 }
227 }
228 } // namespace
229
230 namespace {
231 template <typename Array>
getEndIndex(size_t index,const Array & bitfield,size_t blocks)232 size_t getEndIndex(size_t index, const Array& bitfield, size_t blocks)
233 {
234 while (index < blocks && !bitfield::test(bitfield, blocks, index)) {
235 ++index;
236 }
237 return index;
238 }
239 } // namespace
240
241 namespace {
242 template <typename Array>
getSparseMissingUnusedIndex(size_t & index,int32_t minSplitSize,const Array & bitfield,const unsigned char * useBitfield,int32_t blockLength,size_t blocks)243 bool getSparseMissingUnusedIndex(size_t& index, int32_t minSplitSize,
244 const Array& bitfield,
245 const unsigned char* useBitfield,
246 int32_t blockLength, size_t blocks)
247 {
248 BitfieldMan::Range maxRange;
249 BitfieldMan::Range currentRange;
250 size_t nextIndex = 0;
251 while (nextIndex < blocks) {
252 currentRange.startIndex = getStartIndex(nextIndex, bitfield, blocks);
253 if (currentRange.startIndex == blocks) {
254 break;
255 }
256 currentRange.endIndex =
257 getEndIndex(currentRange.startIndex, bitfield, blocks);
258
259 if (currentRange.startIndex > 0) {
260 if (bitfield::test(useBitfield, blocks, currentRange.startIndex - 1)) {
261 currentRange.startIndex = currentRange.getMidIndex();
262 }
263 }
264 // If range is equal, choose a range where its startIndex-1 is
265 // set.
266 if (maxRange < currentRange ||
267 (maxRange == currentRange && maxRange.startIndex > 0 &&
268 currentRange.startIndex > 0 &&
269 (!bitfield::test(bitfield, blocks, maxRange.startIndex - 1) ||
270 bitfield::test(useBitfield, blocks, maxRange.startIndex - 1)) &&
271 bitfield::test(bitfield, blocks, currentRange.startIndex - 1) &&
272 !bitfield::test(useBitfield, blocks, currentRange.startIndex - 1))) {
273 maxRange = currentRange;
274 }
275 nextIndex = currentRange.endIndex;
276 }
277 if (maxRange.getSize()) {
278 if (maxRange.startIndex == 0) {
279 index = 0;
280 return true;
281 }
282 else {
283 if ((!bitfield::test(useBitfield, blocks, maxRange.startIndex - 1) &&
284 bitfield::test(bitfield, blocks, maxRange.startIndex - 1)) ||
285 (static_cast<int64_t>(maxRange.endIndex - maxRange.startIndex) *
286 blockLength >=
287 minSplitSize)) {
288 index = maxRange.startIndex;
289 return true;
290 }
291 else {
292 return false;
293 }
294 }
295 }
296 else {
297 return false;
298 }
299 }
300 } // namespace
301
getSparseMissingUnusedIndex(size_t & index,int32_t minSplitSize,const unsigned char * ignoreBitfield,size_t ignoreBitfieldLength) const302 bool BitfieldMan::getSparseMissingUnusedIndex(
303 size_t& index, int32_t minSplitSize, const unsigned char* ignoreBitfield,
304 size_t ignoreBitfieldLength) const
305 {
306 if (filterEnabled_) {
307 return aria2::getSparseMissingUnusedIndex(
308 index, minSplitSize,
309 array(ignoreBitfield) | ~array(filterBitfield_) | array(bitfield_) |
310 array(useBitfield_),
311 useBitfield_, blockLength_, blocks_);
312 }
313 else {
314 return aria2::getSparseMissingUnusedIndex(
315 index, minSplitSize,
316 array(ignoreBitfield) | array(bitfield_) | array(useBitfield_),
317 useBitfield_, blockLength_, blocks_);
318 }
319 }
320
321 namespace {
322 template <typename Array>
getGeomMissingUnusedIndex(size_t & index,int32_t minSplitSize,const Array & bitfield,const unsigned char * useBitfield,int32_t blockLength,size_t blocks,double base,size_t offsetIndex)323 bool getGeomMissingUnusedIndex(size_t& index, int32_t minSplitSize,
324 const Array& bitfield,
325 const unsigned char* useBitfield,
326 int32_t blockLength, size_t blocks, double base,
327 size_t offsetIndex)
328 {
329 double start = 0;
330 double end = 1;
331 while (start + offsetIndex < blocks) {
332 index = blocks;
333 for (size_t i = start + offsetIndex,
334 eoi = std::min(blocks, static_cast<size_t>(end + offsetIndex));
335 i < eoi; ++i) {
336 if (bitfield::test(useBitfield, blocks, i)) {
337 break;
338 }
339 else if (!bitfield::test(bitfield, blocks, i)) {
340 index = i;
341 break;
342 }
343 }
344 if (index < blocks) {
345 return true;
346 }
347 else {
348 start = end;
349 end *= base;
350 }
351 }
352 return getSparseMissingUnusedIndex(index, minSplitSize, bitfield, useBitfield,
353 blockLength, blocks);
354 }
355 } // namespace
356
getGeomMissingUnusedIndex(size_t & index,int32_t minSplitSize,const unsigned char * ignoreBitfield,size_t ignoreBitfieldLength,double base,size_t offsetIndex) const357 bool BitfieldMan::getGeomMissingUnusedIndex(size_t& index, int32_t minSplitSize,
358 const unsigned char* ignoreBitfield,
359 size_t ignoreBitfieldLength,
360 double base,
361 size_t offsetIndex) const
362 {
363 if (filterEnabled_) {
364 return aria2::getGeomMissingUnusedIndex(
365 index, minSplitSize,
366 array(ignoreBitfield) | ~array(filterBitfield_) | array(bitfield_) |
367 array(useBitfield_),
368 useBitfield_, blockLength_, blocks_, base, offsetIndex);
369 }
370 else {
371 return aria2::getGeomMissingUnusedIndex(
372 index, minSplitSize,
373 array(ignoreBitfield) | array(bitfield_) | array(useBitfield_),
374 useBitfield_, blockLength_, blocks_, base, offsetIndex);
375 }
376 }
377
378 namespace {
379 template <typename Array>
getInorderMissingUnusedIndex(size_t & index,size_t startIndex,size_t lastIndex,int32_t minSplitSize,const Array & bitfield,const unsigned char * useBitfield,int32_t blockLength,size_t blocks)380 bool getInorderMissingUnusedIndex(size_t& index, size_t startIndex,
381 size_t lastIndex, int32_t minSplitSize,
382 const Array& bitfield,
383 const unsigned char* useBitfield,
384 int32_t blockLength, size_t blocks)
385 {
386 // We always return first piece if it is available.
387 if (!bitfield::test(bitfield, blocks, startIndex) &&
388 !bitfield::test(useBitfield, blocks, startIndex)) {
389 index = startIndex;
390 return true;
391 }
392 for (size_t i = startIndex + 1; i < lastIndex;) {
393 if (!bitfield::test(bitfield, blocks, i) &&
394 !bitfield::test(useBitfield, blocks, i)) {
395 // If previous piece has already been retrieved, we can download
396 // from this index.
397 if (!bitfield::test(useBitfield, blocks, i - 1) &&
398 bitfield::test(bitfield, blocks, i - 1)) {
399 index = i;
400 return true;
401 }
402 // Check free space of minSplitSize. When checking this, we use
403 // blocks instead of lastIndex.
404 size_t j;
405 for (j = i; j < blocks; ++j) {
406 if (bitfield::test(bitfield, blocks, j) ||
407 bitfield::test(useBitfield, blocks, j)) {
408 break;
409 }
410 if (static_cast<int64_t>(j - i + 1) * blockLength >= minSplitSize) {
411 index = j;
412 return true;
413 }
414 }
415 i = j + 1;
416 }
417 else {
418 ++i;
419 }
420 }
421 return false;
422 }
423 } // namespace
424
getInorderMissingUnusedIndex(size_t & index,int32_t minSplitSize,const unsigned char * ignoreBitfield,size_t ignoreBitfieldLength) const425 bool BitfieldMan::getInorderMissingUnusedIndex(
426 size_t& index, int32_t minSplitSize, const unsigned char* ignoreBitfield,
427 size_t ignoreBitfieldLength) const
428 {
429 if (filterEnabled_) {
430 return aria2::getInorderMissingUnusedIndex(
431 index, 0, blocks_, minSplitSize,
432 array(ignoreBitfield) | ~array(filterBitfield_) | array(bitfield_) |
433 array(useBitfield_),
434 useBitfield_, blockLength_, blocks_);
435 }
436 else {
437 return aria2::getInorderMissingUnusedIndex(
438 index, 0, blocks_, minSplitSize,
439 array(ignoreBitfield) | array(bitfield_) | array(useBitfield_),
440 useBitfield_, blockLength_, blocks_);
441 }
442 }
443
getInorderMissingUnusedIndex(size_t & index,size_t startIndex,size_t endIndex,int32_t minSplitSize,const unsigned char * ignoreBitfield,size_t ignoreBitfieldLength) const444 bool BitfieldMan::getInorderMissingUnusedIndex(
445 size_t& index, size_t startIndex, size_t endIndex, int32_t minSplitSize,
446 const unsigned char* ignoreBitfield, size_t ignoreBitfieldLength) const
447 {
448 endIndex = std::min(endIndex, blocks_);
449 if (filterEnabled_) {
450 return aria2::getInorderMissingUnusedIndex(
451 index, startIndex, endIndex, minSplitSize,
452 array(ignoreBitfield) | ~array(filterBitfield_) | array(bitfield_) |
453 array(useBitfield_),
454 useBitfield_, blockLength_, blocks_);
455 }
456 else {
457 return aria2::getInorderMissingUnusedIndex(
458 index, startIndex, endIndex, minSplitSize,
459 array(ignoreBitfield) | array(bitfield_) | array(useBitfield_),
460 useBitfield_, blockLength_, blocks_);
461 }
462 }
463
464 namespace {
465 template <typename Array>
copyBitfield(unsigned char * dst,const Array & src,size_t blocks)466 bool copyBitfield(unsigned char* dst, const Array& src, size_t blocks)
467 {
468 unsigned char bits = 0;
469 size_t len = (blocks + 7) / 8;
470 for (size_t i = 0; i < len - 1; ++i) {
471 dst[i] = src[i];
472 bits |= dst[i];
473 }
474 dst[len - 1] = src[len - 1] & bitfield::lastByteMask(blocks);
475 bits |= dst[len - 1];
476 return bits != 0;
477 }
478 } // namespace
479
getAllMissingIndexes(unsigned char * misbitfield,size_t len) const480 bool BitfieldMan::getAllMissingIndexes(unsigned char* misbitfield,
481 size_t len) const
482 {
483 assert(len == bitfieldLength_);
484 if (filterEnabled_) {
485 return copyBitfield(misbitfield, ~array(bitfield_) & array(filterBitfield_),
486 blocks_);
487 }
488 else {
489 return copyBitfield(misbitfield, ~array(bitfield_), blocks_);
490 }
491 }
492
getAllMissingIndexes(unsigned char * misbitfield,size_t len,const unsigned char * peerBitfield,size_t peerBitfieldLength) const493 bool BitfieldMan::getAllMissingIndexes(unsigned char* misbitfield, size_t len,
494 const unsigned char* peerBitfield,
495 size_t peerBitfieldLength) const
496 {
497 assert(len == bitfieldLength_);
498 if (bitfieldLength_ != peerBitfieldLength) {
499 return false;
500 }
501 if (filterEnabled_) {
502 return copyBitfield(misbitfield,
503 ~array(bitfield_) & array(peerBitfield) &
504 array(filterBitfield_),
505 blocks_);
506 }
507 else {
508 return copyBitfield(misbitfield, ~array(bitfield_) & array(peerBitfield),
509 blocks_);
510 }
511 }
512
getAllMissingUnusedIndexes(unsigned char * misbitfield,size_t len,const unsigned char * peerBitfield,size_t peerBitfieldLength) const513 bool BitfieldMan::getAllMissingUnusedIndexes(unsigned char* misbitfield,
514 size_t len,
515 const unsigned char* peerBitfield,
516 size_t peerBitfieldLength) const
517 {
518 assert(len == bitfieldLength_);
519 if (bitfieldLength_ != peerBitfieldLength) {
520 return false;
521 }
522 if (filterEnabled_) {
523 return copyBitfield(misbitfield,
524 ~array(bitfield_) & ~array(useBitfield_) &
525 array(peerBitfield) & array(filterBitfield_),
526 blocks_);
527 }
528 else {
529 return copyBitfield(misbitfield,
530 ~array(bitfield_) & ~array(useBitfield_) &
531 array(peerBitfield),
532 blocks_);
533 }
534 }
535
countMissingBlock() const536 size_t BitfieldMan::countMissingBlock() const { return cachedNumMissingBlock_; }
537
countMissingBlockNow() const538 size_t BitfieldMan::countMissingBlockNow() const
539 {
540 if (filterEnabled_) {
541 return bitfield::countSetBit(filterBitfield_, blocks_) -
542 bitfield::countSetBitSlow(array(bitfield_) & array(filterBitfield_),
543 blocks_);
544 }
545 else {
546 return blocks_ - bitfield::countSetBit(bitfield_, blocks_);
547 }
548 }
549
countFilteredBlockNow() const550 size_t BitfieldMan::countFilteredBlockNow() const
551 {
552 if (filterEnabled_) {
553 return bitfield::countSetBit(filterBitfield_, blocks_);
554 }
555 else {
556 return 0;
557 }
558 }
559
setBitInternal(unsigned char * bitfield,size_t index,bool on)560 bool BitfieldMan::setBitInternal(unsigned char* bitfield, size_t index, bool on)
561 {
562 if (blocks_ <= index) {
563 return false;
564 }
565 unsigned char mask = 128 >> (index % 8);
566 if (on) {
567 bitfield[index / 8] |= mask;
568 }
569 else {
570 bitfield[index / 8] &= ~mask;
571 }
572 return true;
573 }
574
setUseBit(size_t index)575 bool BitfieldMan::setUseBit(size_t index)
576 {
577 return setBitInternal(useBitfield_, index, true);
578 }
579
unsetUseBit(size_t index)580 bool BitfieldMan::unsetUseBit(size_t index)
581 {
582 return setBitInternal(useBitfield_, index, false);
583 }
584
setBit(size_t index)585 bool BitfieldMan::setBit(size_t index)
586 {
587 bool b = setBitInternal(bitfield_, index, true);
588 updateCache();
589 return b;
590 }
591
unsetBit(size_t index)592 bool BitfieldMan::unsetBit(size_t index)
593 {
594 bool b = setBitInternal(bitfield_, index, false);
595 updateCache();
596 return b;
597 }
598
isFilteredAllBitSet() const599 bool BitfieldMan::isFilteredAllBitSet() const
600 {
601 if (filterEnabled_) {
602 for (size_t i = 0; i < bitfieldLength_; ++i) {
603 if ((bitfield_[i] & filterBitfield_[i]) != filterBitfield_[i]) {
604 return false;
605 }
606 }
607 return true;
608 }
609 else {
610 return isAllBitSet();
611 }
612 }
613
614 namespace {
testAllBitSet(const unsigned char * bitfield,size_t length,size_t blocks)615 bool testAllBitSet(const unsigned char* bitfield, size_t length, size_t blocks)
616 {
617 if (length == 0) {
618 return true;
619 }
620 for (size_t i = 0; i < length - 1; ++i) {
621 if (bitfield[i] != 0xffu) {
622 return false;
623 }
624 }
625 return bitfield[length - 1] == bitfield::lastByteMask(blocks);
626 }
627 } // namespace
628
isAllBitSet() const629 bool BitfieldMan::isAllBitSet() const
630 {
631 return testAllBitSet(bitfield_, bitfieldLength_, blocks_);
632 }
633
isAllFilterBitSet() const634 bool BitfieldMan::isAllFilterBitSet() const
635 {
636 if (!filterBitfield_) {
637 return false;
638 }
639 return testAllBitSet(filterBitfield_, bitfieldLength_, blocks_);
640 }
641
isFilterBitSet(size_t index) const642 bool BitfieldMan::isFilterBitSet(size_t index) const
643 {
644 if (filterBitfield_) {
645 return bitfield::test(filterBitfield_, blocks_, index);
646 }
647 else {
648 return false;
649 }
650 }
651
isBitSet(size_t index) const652 bool BitfieldMan::isBitSet(size_t index) const
653 {
654 return bitfield::test(bitfield_, blocks_, index);
655 }
656
isUseBitSet(size_t index) const657 bool BitfieldMan::isUseBitSet(size_t index) const
658 {
659 return bitfield::test(useBitfield_, blocks_, index);
660 }
661
setBitfield(const unsigned char * bitfield,size_t bitfieldLength)662 void BitfieldMan::setBitfield(const unsigned char* bitfield,
663 size_t bitfieldLength)
664 {
665 if (bitfieldLength_ != bitfieldLength) {
666 return;
667 }
668 memcpy(bitfield_, bitfield, bitfieldLength_);
669 memset(useBitfield_, 0, bitfieldLength_);
670 updateCache();
671 }
672
clearAllBit()673 void BitfieldMan::clearAllBit()
674 {
675 memset(bitfield_, 0, bitfieldLength_);
676 updateCache();
677 }
678
setAllBit()679 void BitfieldMan::setAllBit()
680 {
681 for (size_t i = 0; i < blocks_; ++i) {
682 setBitInternal(bitfield_, i, true);
683 }
684 updateCache();
685 }
686
clearAllUseBit()687 void BitfieldMan::clearAllUseBit()
688 {
689 memset(useBitfield_, 0, bitfieldLength_);
690 updateCache();
691 }
692
setAllUseBit()693 void BitfieldMan::setAllUseBit()
694 {
695 for (size_t i = 0; i < blocks_; ++i) {
696 setBitInternal(useBitfield_, i, true);
697 }
698 }
699
setFilterBit(size_t index)700 bool BitfieldMan::setFilterBit(size_t index)
701 {
702 return setBitInternal(filterBitfield_, index, true);
703 }
704
ensureFilterBitfield()705 void BitfieldMan::ensureFilterBitfield()
706 {
707 if (!filterBitfield_) {
708 filterBitfield_ = new unsigned char[bitfieldLength_];
709 memset(filterBitfield_, 0, bitfieldLength_);
710 }
711 }
712
addFilter(int64_t offset,int64_t length)713 void BitfieldMan::addFilter(int64_t offset, int64_t length)
714 {
715 ensureFilterBitfield();
716 if (length > 0) {
717 size_t startBlock = offset / blockLength_;
718 size_t endBlock = (offset + length - 1) / blockLength_;
719 for (size_t i = startBlock; i <= endBlock && i < blocks_; i++) {
720 setFilterBit(i);
721 }
722 }
723 updateCache();
724 }
725
removeFilter(int64_t offset,int64_t length)726 void BitfieldMan::removeFilter(int64_t offset, int64_t length)
727 {
728 ensureFilterBitfield();
729 if (length > 0) {
730 size_t startBlock = offset / blockLength_;
731 size_t endBlock = (offset + length - 1) / blockLength_;
732 for (size_t i = startBlock; i <= endBlock && i < blocks_; i++) {
733 setBitInternal(filterBitfield_, i, false);
734 }
735 }
736 updateCache();
737 }
738
addNotFilter(int64_t offset,int64_t length)739 void BitfieldMan::addNotFilter(int64_t offset, int64_t length)
740 {
741 ensureFilterBitfield();
742 if (length > 0 && blocks_ > 0) {
743 size_t startBlock = offset / blockLength_;
744 if (blocks_ <= startBlock) {
745 startBlock = blocks_;
746 }
747 size_t endBlock = (offset + length - 1) / blockLength_;
748 for (size_t i = 0; i < startBlock; ++i) {
749 setFilterBit(i);
750 }
751 for (size_t i = endBlock + 1; i < blocks_; ++i) {
752 setFilterBit(i);
753 }
754 }
755 updateCache();
756 }
757
enableFilter()758 void BitfieldMan::enableFilter()
759 {
760 ensureFilterBitfield();
761 filterEnabled_ = true;
762 updateCache();
763 }
764
disableFilter()765 void BitfieldMan::disableFilter()
766 {
767 filterEnabled_ = false;
768 updateCache();
769 }
770
clearFilter()771 void BitfieldMan::clearFilter()
772 {
773 if (filterBitfield_) {
774 delete[] filterBitfield_;
775 filterBitfield_ = nullptr;
776 }
777 filterEnabled_ = false;
778 updateCache();
779 }
780
getFilteredTotalLengthNow() const781 int64_t BitfieldMan::getFilteredTotalLengthNow() const
782 {
783 if (!filterBitfield_) {
784 return 0;
785 }
786 size_t filteredBlocks = bitfield::countSetBit(filterBitfield_, blocks_);
787 if (filteredBlocks == 0) {
788 return 0;
789 }
790 if (bitfield::test(filterBitfield_, blocks_, blocks_ - 1)) {
791 return ((int64_t)filteredBlocks - 1) * blockLength_ + getLastBlockLength();
792 }
793 else {
794 return ((int64_t)filteredBlocks) * blockLength_;
795 }
796 }
797
798 namespace {
799 template <typename Array, typename CountFun>
computeCompletedLength(const Array & bitfield,const BitfieldMan * btman,CountFun cntfun)800 int64_t computeCompletedLength(const Array& bitfield, const BitfieldMan* btman,
801 CountFun cntfun)
802 {
803 size_t nbits = btman->countBlock();
804 size_t completedBlocks = cntfun(bitfield, nbits);
805 int64_t completedLength = 0;
806 if (completedBlocks == 0) {
807 completedLength = 0;
808 }
809 else {
810 if (bitfield::test(bitfield, nbits, nbits - 1)) {
811 completedLength =
812 ((int64_t)completedBlocks - 1) * btman->getBlockLength() +
813 btman->getLastBlockLength();
814 }
815 else {
816 completedLength = ((int64_t)completedBlocks) * btman->getBlockLength();
817 }
818 }
819 return completedLength;
820 }
821 } // namespace
822
getCompletedLength(bool useFilter) const823 int64_t BitfieldMan::getCompletedLength(bool useFilter) const
824 {
825 if (useFilter && filterEnabled_) {
826 auto arr = array(bitfield_) & array(filterBitfield_);
827 return computeCompletedLength(arr, this,
828 &bitfield::countSetBitSlow<decltype(arr)>);
829 }
830 else {
831 return computeCompletedLength(bitfield_, this, &bitfield::countSetBit);
832 }
833 }
834
getCompletedLengthNow() const835 int64_t BitfieldMan::getCompletedLengthNow() const
836 {
837 return getCompletedLength(false);
838 }
839
getFilteredCompletedLengthNow() const840 int64_t BitfieldMan::getFilteredCompletedLengthNow() const
841 {
842 return getCompletedLength(true);
843 }
844
updateCache()845 void BitfieldMan::updateCache()
846 {
847 cachedNumMissingBlock_ = countMissingBlockNow();
848 cachedNumFilteredBlock_ = countFilteredBlockNow();
849 cachedFilteredTotalLength_ = getFilteredTotalLengthNow();
850 cachedCompletedLength_ = getCompletedLengthNow();
851 cachedFilteredCompletedLength_ = getFilteredCompletedLengthNow();
852 }
853
isBitRangeSet(size_t startIndex,size_t endIndex) const854 bool BitfieldMan::isBitRangeSet(size_t startIndex, size_t endIndex) const
855 {
856 for (size_t i = startIndex; i <= endIndex; ++i) {
857 if (!isBitSet(i)) {
858 return false;
859 }
860 }
861 return true;
862 }
863
unsetBitRange(size_t startIndex,size_t endIndex)864 void BitfieldMan::unsetBitRange(size_t startIndex, size_t endIndex)
865 {
866 for (size_t i = startIndex; i <= endIndex; ++i) {
867 unsetBit(i);
868 }
869 updateCache();
870 }
871
setBitRange(size_t startIndex,size_t endIndex)872 void BitfieldMan::setBitRange(size_t startIndex, size_t endIndex)
873 {
874 for (size_t i = startIndex; i <= endIndex; ++i) {
875 setBit(i);
876 }
877 updateCache();
878 }
879
isBitSetOffsetRange(int64_t offset,int64_t length) const880 bool BitfieldMan::isBitSetOffsetRange(int64_t offset, int64_t length) const
881 {
882 if (length <= 0) {
883 return false;
884 }
885 if (totalLength_ <= offset) {
886 return false;
887 }
888 if (totalLength_ < offset + length) {
889 length = totalLength_ - offset;
890 }
891 size_t startBlock = offset / blockLength_;
892 size_t endBlock = (offset + length - 1) / blockLength_;
893 for (size_t i = startBlock; i <= endBlock; i++) {
894 if (!isBitSet(i)) {
895 return false;
896 }
897 }
898 return true;
899 }
900
getOffsetCompletedLength(int64_t offset,int64_t length) const901 int64_t BitfieldMan::getOffsetCompletedLength(int64_t offset,
902 int64_t length) const
903 {
904 int64_t res = 0;
905 if (length == 0 || totalLength_ <= offset) {
906 return 0;
907 }
908 if (totalLength_ < offset + length) {
909 length = totalLength_ - offset;
910 }
911 size_t start = offset / blockLength_;
912 size_t end = (offset + length - 1) / blockLength_;
913 if (start == end) {
914 if (isBitSet(start)) {
915 res = length;
916 }
917 }
918 else {
919 if (isBitSet(start)) {
920 res += static_cast<int64_t>(start + 1) * blockLength_ - offset;
921 }
922 for (size_t i = start + 1; i <= end - 1; ++i) {
923 if (isBitSet(i)) {
924 res += blockLength_;
925 }
926 }
927 if (isBitSet(end)) {
928 res += offset + length - static_cast<int64_t>(end) * blockLength_;
929 }
930 }
931 return res;
932 }
933
getMissingUnusedLength(size_t startingIndex) const934 int64_t BitfieldMan::getMissingUnusedLength(size_t startingIndex) const
935 {
936 if (blocks_ <= startingIndex) {
937 return 0;
938 }
939 int64_t length = 0;
940 for (size_t i = startingIndex; i < blocks_; ++i) {
941 if (isBitSet(i) || isUseBitSet(i)) {
942 break;
943 }
944 length += getBlockLength(i);
945 }
946 return length;
947 }
948
Range(size_t startIndex,size_t endIndex)949 BitfieldMan::Range::Range(size_t startIndex, size_t endIndex)
950 : startIndex(startIndex), endIndex(endIndex)
951 {
952 }
953
getSize() const954 size_t BitfieldMan::Range::getSize() const { return endIndex - startIndex; }
955
getMidIndex() const956 size_t BitfieldMan::Range::getMidIndex() const
957 {
958 return (endIndex - startIndex) / 2 + startIndex;
959 }
960
operator <(const Range & range) const961 bool BitfieldMan::Range::operator<(const Range& range) const
962 {
963 return getSize() < range.getSize();
964 }
965
operator ==(const Range & range) const966 bool BitfieldMan::Range::operator==(const Range& range) const
967 {
968 return getSize() == range.getSize();
969 }
970
971 } // namespace aria2
972