Возвращаемся на раздачу или как сделать невозможное

Предыстория

Не так давно, а именно 5 июня хабрачеловек по имени alan008 задал вопрос. Чтобы не заставлять ходить за подробностями, приведу его здесь:

Нужна помощь!

За несколько лет с разных трекеров (преимущественно c rutracker'а) разными клиентами (преимущественно uTorrent'ом) скачано много гигабайт разного полезного контента. Скачанные файлы впоследствии вручную перемещались с одного диска на другой, uTorrent их соответственно не видит. Многие .torrent файлы устарели сами по себе (например, велась раздача сериала путем добавления новых серий заменой .torrent файла).

Теперь сам вопрос: есть ли способ автоматически (не вручную) установить соответствие между имеющимися на компьютере .torrent файлами и содержимым, раскиданным по разным логическим дискам компьютера? Цель: удалить лишние (неактуальные) .torrent файлы, а для актуальных — поставить всё на раздачу. У кого какие идеи? :)

При необходимости (если это требуется) можно снова поместить все файлы данных в один каталог на одном логическом диске.

В обсуждениях сошлись на том, что если это и можно сделать, то только ручками. Мне же этот вопрос показался интересным, и после возвращения из отпуска я нашел время, чтобы в нем разобраться.

Потратив в общей сложности неделю на разбор формата .torrent-файла, поиск нормально работающей библиотеки для его парсинга, я приступил к написанию программы, которая позволит решить проблему затронутую в упомянутом вопросе.

Прежде чем начать, стоит отметить несколько моментов:

1. Получилось много, но не все.
2. По формату файла .torrent будут даны лишь необходимые пояснения.
3. Людей, чувствительных к временами некачественному коду, прошу меня заранее простить — я знаю, что многое можно было написать лучше, оптимальнее и безглючнее.

Для тех, кому интересно, что из этого получилось, технические подробности и подводные камни — прошу под кат.


В данном случае имеется отличный способ решения — перекачать заново. Но мы же не ищем легких путей, да и предлагался такой вариант! Итак, будем решать задачу по сложному — не скачивать.

Приступая к написанию любой программы, необходимо сначала продумать хотябы базовый алгоритм ее работы. В нашем случае алгоритм, по сути, состоит из двух шагов:

1. Найти и прочитать все .torrent-файлы;
2. Найти в куче файлов тот, который соответствует описанному в .torrent, и переместить его в папку, соответствующую пути в .torrent.

Для реализации своей идеи, я использовал C#, однако для этого подойдет любой язык, на котором есть библиотеки для чтения файлов в формате bencode и реализована возможность считать SHA-1 хеш.

Ну что же, приступим к решению поставленной задачи.

Ищем торренты и читаем их

После того, как я разобрался с устройством .torrent-файлов, передо мной встал вопрос парсинга всего этого чуда. Прошерстив интернет по данному вопросу, я обнаружил несколько .NET-библиотек под это дело. Выбор свой я остановил на, более-менее понятной и работающей из коробки библиотеке BencodeLibrary, однако впоследствии пришлось ее немного дополнить под свои нужды, но об этом позже.

Начнем с самого простого момента — чтения .torrent.

Строение .torrent-файла довольно простое — он представляет из себя словарь в формате bencode. В данном словаре нас интересует только пара с ключом info — блок описания файлов. Этот тоже является словарем и содержит в себе информацию об имени файлов, их размере. Кроме того, как многим известно, торрент хеширует файлы не целиком, а по кускам определенной длины, которая зависит от размера этих файлов. Информация о размере этого куска также содержится в словаре info.

Для хранения информации из прочитанного файла будем использовать такой класс Torrent:

Здесь поля хранят следующую информацию:

* Name — имя торрента (вообще говоря — имя папки или имя файла)
* Files — список файлов, которые нам надо будет в дальнейшем искать
* PieceLength — размер тех самых кусочков, хеш которых нам предстоит считать
* Hash — хеш строка всех файлов
* FileName — имя .torrent-файла на диске

Теперь стоит заострить внимание на строке хеша. Она составляется очень просто. Все файлы склеиваются в один (виртуально конечно) друг за другом, образуя при этом один БОЛЬШОООООООЙ воображаемый файл. В этом воображаемом файле берем кусок длины PieceLength, считаем SHA1 хеш, кладем хеш в строку, берем следующий кусок, считаем хеш, дописываем к концу строки с хешем предыдущего куска. Т. е. это обычная конкатенация хешей всех кусков.



Как мог заметить внимательный читатель, файл внутри класса — это не просто файл, а особый тип данных, в котором файл описывается некой конструкцией типа LostFile. Вот она:

Здесь все просто: имя файла и его размер. Кроме того этот класс содержит еще одно поле — BeginFrom. Оно описывает начало этого файла в том БОЛЛЬШОООООМ воображаемом файле. Он нужен, чтобы взять правильную часть файла для подсчета хеша — ведь длина файла очень редко кратна длине куска.



Подготовив структуры для хранения необходимой информации, можно приступать к их заполнению.

С помощью найденной на просторах интернета библиотеки BencodeLibrary мы читаем наш .torrent-файл и выкорчевываем из него блок info:

List<LostFile> files = new List<LostFile>(); // список файлов, понадобится позднее
BDict torrent = (BDict)BencodingUtils.DecodeFile(filename, Encoding.UTF8);
BDict fileInfo = (BDict)torrent["info"];

Далее из этого блока необходимо забрать данные об имени торрента, размере куска.

string name = ((BString)fileInfo["name"]).Value;
int pieceLength = (int)((BInt)fileInfo["piece length"]).Value;

С чтением хеша возникла проблема, решение которой мне не очень нравится, но оно работает. Дело в том, что по спецификации все строки в .torrent-файле должны быть в UFT8. Если читать хеш, который по спецификации записан в формате bencode-строки, как UTF8-строку, то возникнет проблема сравнения — хеши одинаковых кусков не совпадут. Читая же торрент в предлагаемой кодировке codepage-437, мы получим проблемы с русскими буквами в путях. Выход из такой ситуации, которая меня тормознула на два дня, я нашел не лучший, но работающий — читать два раза в разных кодировках.

torrent = (BDict)BencodingUtils.DecodeFile(filename, Encoding.GetEncoding(437));
char[] pieces = ((BString)((BDict)torrent["info"])["pieces"]).Value.ToCharArray();

В этом месте мы передаем в метод `BencodingUtils.DecodeFile` вторым параметром информацию о кодировке. Это как раз тот момент, когда пришлось добавлять один метод в библиотеку — изначально codepage-437 была вшита в код.

Мы добрались до самого интересного момента в этой части — чтение информации о файлах. Торрент файлы бывают двух типов. Эти типы различаются тем, сколько файлов в них описано. При описании только одного файла в .torrent пишется его имя и размер.

Сначала разберем .torrent с описанием одного файла.

long Length = ((BInt)fileInfo["length"]).Value;
files.Add(new LostFile(name, Length, 0)); // files - список файлов

Тут все просто — имя торрента совпадает с именем файла. В случае, когда файлов в раздаче много, то в поле name пишется имя папки, в которую их надо положить (на самом деле может быть что угодно, но почему-то все пишут имя папки в которой эти файлы лежали при создании). Кроме того появляется список files в котором содержится информация о каждом файле: путь к нему и размер. Если размер — просто целое число, то путь к файлу представляет собой список из строк (имен директорий), пройдя по которым мы увидим этот файл.

Такое лучше пояснять на примере. Для файлов level_1\level_2_1\file_1.txt и level_1\level_2_2\file_2.txt, если мы захотим их раздавать, поле name будет содержать имя папки верхнего уровня ("level_1"), а список path для одного из файлов будет следующего вида: {"level_2_1", "file_1.txt"} и {"level_2_2", "file_2.txt"} для другого.

Нам для .torrent с несколькими файлами надо путь до каждого файла собрать в одну строку. Кроме того, надо хранить начало каждого файла в том БОЛЬШООООМ (не забыли, правда же?!):

BList filesData = (BList)fileInfo["files"];
long begin = 0;

foreach (BDict file in filesData)
{
	BList filePaths = (BList)file["path"];
	long length = ((BInt)file["length"]).Value;

	string fullPath = name;
	foreach (BString partOfPath in filePaths)
	{
		fullPath += @"\" + partOfPath.Value;
	}
	files.Add(new LostFile(fullPath, length, begin)); // files - список файлов

	begin += length;
}

Очень важно отметить, что порядок следования файлов в БОЛЬШОООООМ файле может быть любым, не обязательно по алфавиту или по размеру. Но порядок файлов в списке files будет точно таким же. Это ключевой момент для понимания принципа хеширования. Для примера, в ситуации, изображенной на первом рисунке, список файлов будет следующим: {"file_3","file_1", ..., "file_2"}. Таким образом, считая хеш одного файла, мы знаем какой файл надо будет брать следующим.

Когда мы все это дело прочитали и посчитали — давайте создадим и вернем экземпляр Torrent:

new Torrent(name, files, pieceLength, pieces, filename);

Собирая теперь все чтение и разбор .torrent-файла воедино, получаем:

Теперь, когда у нас есть все необходимые данные, мы готовы к самому интересному — поиску наших файлов.

Ищем файлы

Мы вплотную подошли к реализации второго шага нашего алгоритма. Для этого будем использовать метод FindFiles такого вида:

void FindFiles(Torrent torrent, List<FileInfo> files, string destinationPath) {}

Здесь files — список файлов, среди которых мы будем искать, destinationPath — путь до папки назначения, в которую будут помещаться найденные файлы.

Для каждого файла в .torrent мы будем перебирать все файлы из кучи и их сверять. Так как проверка хеша довольно затратна, то надо сначала отсеять явно левые файлы. Ну посудите сами: если я качал дискографию в .mp3 и переместил ее, то явно не менял расширения файлов. Имя мог поменять, а вот расширение вряд ли.

FileInfo fileOnDisk = files[j];
if (fileOnDisk.Extension != Path.GetExtension(fileInTorrent.Name))
	continue;

Также стоит проверять длину файла, но это уже сомнительно и иногда может давать ложные срабатывания. Только после того, как мы отсеяли по расширению явно левые файлы, можно приступать к проверке хеша.

if (!torrent.CheckHash(i, fileOnDisk))
	continue;

После того как проверка завершена, и мы удостоверились в соответствии файла искомому — перемещаем его в папку назначения с правильным путем. Перед перемещением будем естественно проверять наличие директории, а также проверим есть ли уже такой файл или нет. copyFile — переменная передаваемая с формы пользователем, ее назначение, я думаю, понятно всем.

			
FileInfo fileToMove = new FileInfo(destinationPath + @"\" + fileInTorrent.Name);

if (!Directory.Exists(fileToMove.DirectoryName))
	Directory.CreateDirectory(fileToMove.DirectoryName);

if (!fileToMove.Exists)
{
	// Перемещаем-копируем файл
	if (copyFile)
		File.Copy(fileOnDisk.FullName, fileToMove.FullName);
	else
		File.Move(fileOnDisk.FullName, fileToMove.FullName);
		// Убираем из списка рассматириваемых
	files.Remove(fileOnDisk);
	// Убираем из описания торрента
	torrent.Files.RemoveAt(i--);
	break; //Больше искать файл в дереве не надо, можно переходить к следующему в torrent
}

Есть в коде выше три важных для пояснения момента. Начну с двух последних — вот эти строки:

	
files.Remove(fileOnDisk);
torrent.Files.RemoveAt(i--);

Я посчитал вполне логичным убирать уже отсортированные файлы из рассмотрения, что позволит несколько сократить время выполнения поиска. Во второй строке есть конструкция .RemoveAt(i--); так как из коллекции убирается текущий элемент, то указатель надо сдвинуть назад, чтобы на следующей итерации цикла брался следующий элемент, а не через один.

Теперь про первый момент. Я знаю про наличие foreach для списка, но его при использовании нельзя модифицировать этот спикок, то есть мы не сможем удалять уже ненужные более элементы. Итак, собирая все выше описанное в один метод, имеем:

Ну вот! Самое вкусное.

Проверка хеша

Как видно из кода выше, для проверки хеша мы передаем имя файла на диске и номер файла в списке файлов торрента. Это надо для того, чтобы не запускать поиск в списке файлов, а сразу взять его по номеру, раз он известен (еще одно "+1" циклу for).

public class Torrent
{
	public string Name;
	public int PieceLength;
	public char[] Hash;
	public List<LostFile> Files;
	public string FileName;
		
	public bool CheckHash(int index, FileInfo fileOnDisk) {}
}

Теперь приступим к реализации нашего метода проверки хеша. На данном этапе мы знаем номер в списке файлов торрента и путь до файла на диске

LostFile checkingFile = this.Files[index];

if (checkingFile.Length < this.PieceLength * 2 - 1)
	return false;

В принципе, мы можем считать хеш любого файла, но давайте немного упростим себе задачу. Мы будем браться только за файлы, длина которых больше или равна PieceLength * 2 - 1. Такое ограничение даст нам возможность вычленить хотя бы один кусок для проверки, полность находящийся в файле. У такого подхода есть несколько существенных плюсов:

1. Нет необходимости дополнительно искать на диске соседние файлы;
2. Длина куска для хеширования очень редко превышает 2-4 МБ, что дает нам еще один плюс — с точки зрения производительности и времени, докачать такие файлы намного проще, чем искать их на диске.

На этом этапе мы подошли к самому сложному из всего, что нам надо было сделать — поиску нужного куска для проверки. Давайте немного отдалимся от программирования и обратимся к математике, сформулировав вспомогательную задачку.

Когда торрент-клиент проводит хеширование файлов, он считает хеш по порядку, однако бывает так, что нет одного или нескольких файлов. Тогда торрент-клиенту надо знать какой следующий кусок брать и откуда он будет начинаться в следующем имеющемся файле. Для вычисления двух этих цифр будем использовать следующий код, в котором переменная firstChunkNumber содержит номер первого куска, который полностью содержится в данном файле, а bytesOverhead — количество байт от начала файла до начала этого куска. Для лучшего понимания этого момента взгляните на поясняющий рисунок после кода.

long start = 0;
long firstChunkNumber = 0;
            
long bytesOveload = checkingFile.BeginFrom % this.PieceLength;

if (bytesOveload == 0) // Если кусок начинается с первого байта файла
{
	start = checkingFile.BeginFrom;
	firstChunkNumber = checkingFile.BeginFrom / this.PieceLength;
}
else
{
	firstChunkNumber = checkingFile.BeginFrom / this.PieceLength + 1;
	start = firstChunkNumber * this.PieceLength - checkingFile.BeginFrom;
}

Ответить на вопрос «Почему номер куска разный для случая, когда его начало совпадает с началом файла, и для случая, когда кусок лежит внутри?» предлагается самостоятельно.

Сейчас, зная номер куска мы должны взять его хеш из торрента с помощью такой конструкции:

char[] hashInTorrent = new char[20]; // 20 - длина хеша SHA1 в байтах
Array.Copy(this.Hash, firstChunkNumber * 20, hashInTorrent, 0, 20);

После этого, надо прочитать кусок из файла и посчитать его хеш:

char[] fileHash = new char[this.PieceLength];

using (BinaryReader fs = new BinaryReader(new FileStream(fileOnDisk.FullName, FileMode.Open)))
{
	using (SHA1CryptoServiceProvider sha1 = new SHA1CryptoServiceProvider())
	{
		byte[] piece = new byte[this.PieceLength];

		fs.BaseStream.Position = start;
		fs.Read(piece, 0, this.PieceLength);

		fileHash = Encoding.GetEncoding(437).GetString(sha1.ComputeHash(piece)).ToCharArray();
	}
}

Ну и самое важное — его проверить. У меня, почему-то не захотел работать ни один из методов Equals(), которые я смог найти, поэтому проверяем так:

for (int i = 0; i < fileHash.Length; i++)
{
	if (fileHash[i] != hashInTorrent[i])
		return false;
}

Собирая воедино сие творение возбужденного мозга, получим метод следующего содержания:

На этой прекрасной ноте, рассказ о методах и алгоритмах заканчивается, и мы переходим к рассказу о реализации в реальной жизни данного творения. Вполне понятно, что данная задача мной решалась не для того, чтобы решить, а для того, чтобы реализовать. Поэтому привожу на суд общественности мое творение, которое реализует все то, о чем написано выше.

Программа

Программа написана, как уже упоминалось на C#. При работе не сильно прихотлива, требует только .NET 2.0. Есть однако одно ограничение на использование: торрент файлы и коллекцию лучше убрать из корня логического диска. Причина этого ограничения — использование при сканировании директорий параметра `SearchOption.AllDirectories`, что приводит к вылету при попытке прочитать закрытые директории типа корзины или `System Volume Information` (если знающие люди подскажут как это обойти, то буду весьма признателен). Для папки назначения особых ограничений естественно нет, главное чтобы влезло, и можно было в нее писать, иначе вылетит с ошибкой (не моделировал, но логично).

В процессе работы, после окончания обработки очередного файла, выводится результат — имя .torrent-файла на диске и количество обработанных файлов.



Чтобы запустить сканирование, необходимо выбрать три директории (с файлами .torrent, с файлами для сортировки и папку для отсортированного), по желанию указать две опции и запустить сканирование.

По поводу производительности. Она пока что низкая: обработка 10 больших torrent-файлов заняла около 5 минут.

Так как работает приложение в один поток, то во время выполнения интерфейс подвисает, но я над этим работаю. Также хочу напомнить, что файлы малого размера (меньше 2-х мегабайт) не будут перемещены по причине отсутствия возможности проверки хеша. Вполне вероятны ложные срабатывания из-за того, что проверяется только один кусок под номером firstChunkNumber. Пока что проверять все куски слишком затратно, но в планах есть.

Не ищите торренты рекурсивно, если они собраны в корне диска.
Копирование может занять много времени, поэтому интерфейс может подвиснуть — не пугайтесь.

Так как писалась эта программа 4fun, то качество кода там немного не то, которое хотелось бы, но у меня оно работает. Данная программа не тестировалась, исправлялись только очевидные ошибки, поэтому могут быть, да что скрывать-то, есть скрытые баги. ИСПОЛЬЗУЯ ДАННУЮ ПРОГРАММУ, ВЫ ИСПОЛЬЗУЕТЕ ЕЕ НА СВОЙ СТРАХ И РИСК.

Взять исходники можно на github. Распространяется по GPLv2. Там есть архив с исполняемым файлом. Для работы требуется библиотека Bencode Library, но не оригинальная, а модифицированная мною (есть у меня в репозитарии, подключена субмодулем).

Спасибо всем, кто проявил терпение и дочитал эту статью до конца. Рад услышать ваши вопросы, приветствуется всевозможная помощь в совершенствовании алгоритма и, в особенности, кода.

Источники: BitTorrentSpecification.

UPD1. По результатам обсуждения мне стало понятно, что правильней будет не ломать существующие коллекции выдергиванием файлов на раздачу, а наоборот — создавать хардлинки в нужном для раздачи месте на файлы внутри упорядоченных коллекций (фильмо и дискографий, например). В дальнейшем программа будет работать именно так.

UPD2. Если у тех, кто пользовался этой утилитой, есть еще какие-то пожелания по функционалу или баг репорты, то прошу оставлять их на github в issue-трекере.