Add --stream-piece-selector=random

11 files changed, 196 insertions, 11 deletions

diff --git a/src/BitfieldMan.cc b/src/BitfieldMan.cc
index c1904205..4432253d 100644
--- a/src/BitfieldMan.cc
+++ b/src/BitfieldMan.cc
@@ -376,6 +376,8 @@ namespace {
 template<typename Array>
 bool getInorderMissingUnusedIndex
 (size_t& index,
+ size_t startIndex,
+ size_t lastIndex,
  int32_t minSplitSize,
  const Array& bitfield,
  const unsigned char* useBitfield,
@@ -383,12 +385,12 @@ bool getInorderMissingUnusedIndex
  size_t blocks)
 {
   // We always return first piece if it is available.
-  if(!bitfield::test(bitfield, blocks, 0) &&
-     !bitfield::test(useBitfield, blocks, 0)) {
-    index = 0;
+  if(!bitfield::test(bitfield, blocks, startIndex) &&
+     !bitfield::test(useBitfield, blocks, startIndex)) {
+    index = startIndex;
     return true;
   }
-  for(size_t i = 1; i < blocks;) {
+  for(size_t i = startIndex + 1; i < lastIndex;) {
     if(!bitfield::test(bitfield, blocks, i) &&
        !bitfield::test(useBitfield, blocks, i)) {
       // If previous piece has already been retrieved, we can download
@@ -398,7 +400,8 @@ bool getInorderMissingUnusedIndex
         index = i;
         return true;
       }
-      // Check free space of minSplitSize.
+      // Check free space of minSplitSize.  When checking this, we use
+      // blocks instead of lastIndex.
       size_t j;
       for(j = i; j < blocks; ++j) {
         if(bitfield::test(bitfield, blocks, j) ||
@@ -427,13 +430,36 @@ bool BitfieldMan::getInorderMissingUnusedIndex
 {
   if(filterEnabled_) {
     return aria2::getInorderMissingUnusedIndex
-      (index, minSplitSize,
+      (index, 0, blocks_, minSplitSize,
        array(ignoreBitfield)|~array(filterBitfield_)|
        array(bitfield_)|array(useBitfield_),
        useBitfield_, blockLength_, blocks_);
   } else {
     return aria2::getInorderMissingUnusedIndex
-      (index, minSplitSize,
+      (index, 0, blocks_,  minSplitSize,
+       array(ignoreBitfield)|array(bitfield_)|array(useBitfield_),
+       useBitfield_, blockLength_, blocks_);
+  }
+}
+
+bool BitfieldMan::getInorderMissingUnusedIndex
+(size_t& index,
+ size_t startIndex,
+ size_t endIndex,
+ int32_t minSplitSize,
+ const unsigned char* ignoreBitfield,
+ size_t ignoreBitfieldLength) const
+{
+  endIndex = std::min(endIndex, blocks_);
+  if(filterEnabled_) {
+    return aria2::getInorderMissingUnusedIndex
+      (index, startIndex, endIndex, minSplitSize,
+       array(ignoreBitfield)|~array(filterBitfield_)|
+       array(bitfield_)|array(useBitfield_),
+       useBitfield_, blockLength_, blocks_);
+  } else {
+    return aria2::getInorderMissingUnusedIndex
+      (index, startIndex, endIndex,  minSplitSize,
        array(ignoreBitfield)|array(bitfield_)|array(useBitfield_),
        useBitfield_, blockLength_, blocks_);
   }
diff --git a/src/BitfieldMan.h b/src/BitfieldMan.h
index 60e44547..8e33d118 100644
--- a/src/BitfieldMan.h
+++ b/src/BitfieldMan.h
@@ -171,8 +171,20 @@ public:
    const unsigned char* ignoreBitfield,
    size_t ignoreBitfieldLength) const;
 
+  // Just like getInorderMissingUnusedIndex() above, but limit the
+  // search area in [startIndex, endIndex).  |endIndex| is normalized
+  // to min(|endIndex|, blocks_)
+  //
+  // affected by filter
+  bool getInorderMissingUnusedIndex
+  (size_t& index,
+   size_t startIndex, size_t endIndex,
+   int32_t minSplitSize,
+   const unsigned char* ignoreBitfield,
+   size_t ignoreBitfieldLength) const;
+
   // affected by filter
-  bool getAllMissingIndexes(unsigned char* misbitfield, size_t mislen) const;
+  bool getAllMissingIndexes(unsigned char *misbitfield, size_t mislen) const;
 
   // affected by filter
   bool getAllMissingIndexes(unsigned char* misbitfield, size_t mislen,
diff --git a/src/DefaultPieceStorage.cc b/src/DefaultPieceStorage.cc
index 713e8365..1924e8ae 100644
--- a/src/DefaultPieceStorage.cc
+++ b/src/DefaultPieceStorage.cc
@@ -58,6 +58,7 @@
 #include "RarestPieceSelector.h"
 #include "DefaultStreamPieceSelector.h"
 #include "InorderStreamPieceSelector.h"
+#include "RandomStreamPieceSelector.h"
 #include "GeomStreamPieceSelector.h"
 #include "array_fun.h"
 #include "PieceStatMan.h"
@@ -96,6 +97,9 @@ DefaultPieceStorage::DefaultPieceStorage
   } else if(pieceSelectorOpt == V_INORDER) {
     streamPieceSelector_ = make_unique<InorderStreamPieceSelector>
       (bitfieldMan_.get());
+  } else if(pieceSelectorOpt == A2_V_RANDOM) {
+    streamPieceSelector_ = make_unique<RandomStreamPieceSelector>
+      (bitfieldMan_.get());
   } else if(pieceSelectorOpt == A2_V_GEOM) {
     streamPieceSelector_ = make_unique<GeomStreamPieceSelector>
       (bitfieldMan_.get(), 1.5);
diff --git a/src/Makefile.am b/src/Makefile.am
index 236a055e..fee0a6f9 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -140,6 +140,7 @@ SRCS =  \
 	InitiateConnectionCommand.cc InitiateConnectionCommand.h\
 	InitiateConnectionCommandFactory.cc InitiateConnectionCommandFactory.h\
 	InorderStreamPieceSelector.cc InorderStreamPieceSelector.h\
+	RandomStreamPieceSelector.cc RandomStreamPieceSelector.h\
 	InorderURISelector.cc InorderURISelector.h\
 	IOFile.cc IOFile.h\
 	IteratableChecksumValidator.cc IteratableChecksumValidator.h\
diff --git a/src/OptionHandlerFactory.cc b/src/OptionHandlerFactory.cc
index 8542900c..09562dc1 100644
--- a/src/OptionHandlerFactory.cc
+++ b/src/OptionHandlerFactory.cc
@@ -1171,7 +1171,7 @@ std::vector<OptionHandler*> OptionHandlerFactory::createOptionHandlers()
                       (PREF_STREAM_PIECE_SELECTOR,
                        TEXT_STREAM_PIECE_SELECTOR,
                        A2_V_DEFAULT,
-                       { A2_V_DEFAULT, V_INORDER, A2_V_GEOM }));
+                       { A2_V_DEFAULT, V_INORDER, A2_V_RANDOM, A2_V_GEOM }));
     op->addTag(TAG_FTP);
     op->addTag(TAG_HTTP);
     op->setInitialOption(true);
diff --git a/src/RandomStreamPieceSelector.cc b/src/RandomStreamPieceSelector.cc
new file mode 100644
index 00000000..a14c2c2b
--- /dev/null
+++ b/src/RandomStreamPieceSelector.cc
@@ -0,0 +1,76 @@
+/* <!-- copyright */
+/*
+ * aria2 - The high speed download utility
+ *
+ * Copyright (C) 2015 Tatsuhiro Tsujikawa
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ * In addition, as a special exception, the copyright holders give
+ * permission to link the code of portions of this program with the
+ * OpenSSL library under certain conditions as described in each
+ * individual source file, and distribute linked combinations
+ * including the two.
+ * You must obey the GNU General Public License in all respects
+ * for all of the code used other than OpenSSL.  If you modify
+ * file(s) with this exception, you may extend this exception to your
+ * version of the file(s), but you are not obligated to do so.  If you
+ * do not wish to do so, delete this exception statement from your
+ * version.  If you delete this exception statement from all source
+ * files in the program, then also delete it here.
+ */
+/* copyright --> */
+#include "RandomStreamPieceSelector.h"
+#include "BitfieldMan.h"
+#include "SimpleRandomizer.h"
+
+namespace aria2 {
+
+RandomStreamPieceSelector::RandomStreamPieceSelector
+(BitfieldMan* bitfieldMan)
+  : bitfieldMan_(bitfieldMan)
+{}
+
+RandomStreamPieceSelector::~RandomStreamPieceSelector() {}
+
+bool RandomStreamPieceSelector::select
+(size_t& index,
+ size_t minSplitSize,
+ const unsigned char* ignoreBitfield,
+ size_t length)
+{
+  size_t start = SimpleRandomizer::getInstance()->getRandomNumber
+    (bitfieldMan_->countBlock());
+
+  auto rv = bitfieldMan_->getInorderMissingUnusedIndex
+    (index, start, bitfieldMan_->countBlock(), minSplitSize, ignoreBitfield,
+     length);
+  if (rv) {
+    return true;
+  }
+  rv = bitfieldMan_->getInorderMissingUnusedIndex(index, 0, start, minSplitSize,
+                                                  ignoreBitfield, length);
+  if (rv) {
+    return true;
+  }
+  // Fall back to inorder search because randomized search may fail
+  // because of |minSplitSize| constraint.
+  return bitfieldMan_->getInorderMissingUnusedIndex(index, minSplitSize,
+                                                    ignoreBitfield, length);
+}
+
+void RandomStreamPieceSelector::onBitfieldInit() {}
+
+} // namespace aria2
diff --git a/src/RandomStreamPieceSelector.h b/src/RandomStreamPieceSelector.h
new file mode 100644
index 00000000..8b624131
--- /dev/null
+++ b/src/RandomStreamPieceSelector.h
@@ -0,0 +1,62 @@
+/* <!-- copyright */
+/*
+ * aria2 - The high speed download utility
+ *
+ * Copyright (C) 2015 Tatsuhiro Tsujikawa
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ *
+ * In addition, as a special exception, the copyright holders give
+ * permission to link the code of portions of this program with the
+ * OpenSSL library under certain conditions as described in each
+ * individual source file, and distribute linked combinations
+ * including the two.
+ * You must obey the GNU General Public License in all respects
+ * for all of the code used other than OpenSSL.  If you modify
+ * file(s) with this exception, you may extend this exception to your
+ * version of the file(s), but you are not obligated to do so.  If you
+ * do not wish to do so, delete this exception statement from your
+ * version.  If you delete this exception statement from all source
+ * files in the program, then also delete it here.
+ */
+/* copyright --> */
+#ifndef D_RANDOM_STREAM_PIECE_SELECTOR_H
+#define D_RANDOM_STREAM_PIECE_SELECTOR_H
+
+#include "StreamPieceSelector.h"
+
+namespace aria2 {
+
+class BitfieldMan;
+
+class RandomStreamPieceSelector:public StreamPieceSelector {
+public:
+  RandomStreamPieceSelector(BitfieldMan* bitfieldMan);
+  virtual ~RandomStreamPieceSelector();
+
+  virtual bool select
+  (size_t& index,
+   size_t minSplitSize,
+   const unsigned char* ignoreBitfield,
+   size_t length) CXX11_OVERRIDE;
+
+  virtual void onBitfieldInit() CXX11_OVERRIDE;
+private:
+  BitfieldMan* bitfieldMan_;
+};
+
+} // namespace aria2
+
+#endif // D_RANDOM_STREAM_PIECE_SELECTOR_H
diff --git a/src/RequestGroup.cc b/src/RequestGroup.cc
index e36dbdf3..748167f1 100644
--- a/src/RequestGroup.cc
+++ b/src/RequestGroup.cc
@@ -552,8 +552,7 @@ void RequestGroup::initPieceStorage()
           (downloadContext_->getFileEntries().begin(),
            downloadContext_->getFileEntries().end())) {
         // Use LongestSequencePieceSelector when HTTP/FTP/BitTorrent
-        // integrated downloads. Currently multi-file integrated
-        // download is not supported.
+        // integrated downloads.
         A2_LOG_DEBUG("Using LongestSequencePieceSelector");
         ps->setPieceSelector(make_unique<LongestSequencePieceSelector>());
 
diff --git a/src/prefs.cc b/src/prefs.cc
index 502cfe1d..3c307dd2 100644
--- a/src/prefs.cc
+++ b/src/prefs.cc
@@ -152,6 +152,7 @@ const std::string V_NOTICE("notice");
 const std::string V_WARN("warn");
 const std::string V_ERROR("error");
 const std::string V_INORDER("inorder");
+const std::string A2_V_RANDOM("random");
 const std::string V_FEEDBACK("feedback");
 const std::string V_ADAPTIVE("adaptive");
 const std::string V_LIBUV("libuv");
diff --git a/src/prefs.h b/src/prefs.h
index 3bcafe23..d631ce43 100644
--- a/src/prefs.h
+++ b/src/prefs.h
@@ -88,6 +88,7 @@ extern const std::string V_NOTICE;
 extern const std::string V_WARN;
 extern const std::string V_ERROR;
 extern const std::string V_INORDER;
+extern const std::string A2_V_RANDOM;
 extern const std::string V_FEEDBACK;
 extern const std::string V_ADAPTIVE;
 extern const std::string V_LIBUV;
diff --git a/src/usage_text.h b/src/usage_text.h
index 740cf8e5..08b4f7c6 100644
--- a/src/usage_text.h
+++ b/src/usage_text.h
@@ -823,6 +823,9 @@
     "                              --min-split-size option, so it will be necessary\n" \
     "                              to specify a reasonable value to\n"  \
     "                              --min-split-size option.\n"          \
+    "                              If 'random' is given, aria2 selects piece\n" \
+    "                              randomly. Like 'inorder', --min-split-size\n" \
+    "                              option is honored.\n"                \
     "                              If 'geom' is given, at the beginning aria2\n" \
     "                              selects piece which has minimum index like\n" \
     "                              'inorder', but it exponentially increasingly\n" \