Предыстория
Не так давно, а именно 5 июня читатель по имени alan008 задал вопрос. Чтобы не заставлять ходить за подробностями, приведу его здесь:
Нужна помощь!
За несколько лет с разных трекеров (преимущественно c rutracker'а) разными клиентами (преимущественно uTorrent'ом) скачано много гигабайт разного полезного контента. Скачанные файлы впоследствии вручную перемещались с одного диска на другой, uTorrent их соответственно не видит. Многие .torrent файлы устарели сами по себе (например, велась раздача сериала путем добавления новых серий заменой .torrent файла).
Теперь сам вопрос: есть ли способ автоматически (не вручную) установить соответствие между имеющимися на компьютере .torrent файлами и содержимым, раскиданным по разным логическим дискам компьютера? Цель: удалить лишние (неактуальные) .torrent файлы, а для актуальных — поставить всё на раздачу. У кого какие идеи? :)
При необходимости (если это требуется) можно снова поместить все файлы данных в один каталог на одном логическом диске.
В обсуждениях сошлись на том, что если это и можно сделать, то только ручками. Мне же этот вопрос показался интересным, и после возвращения из отпуска я нашел время, чтобы в нем разобраться.
Потратив в общей сложности неделю на разбор формата .torrent-файла, поиск нормально работающей библиотеки для его парсинга, я приступил к написанию программы, которая позволит решить проблему затронутую в упомянутом вопросе.
Прежде чем начать, стоит отметить несколько моментов:
- Получилось много, но не все.
- По формату файла .torrent будут даны лишь необходимые пояснения.
- Людей, чувствительных к временами некачественному коду, прошу меня заранее простить — я знаю, что многое можно было написать лучше, оптимальнее и безглючнее.
Для тех, кому интересно, что из этого получилось, технические подробности и подводные камни — прошу под кат.
В данном случае имеется отличный способ решения — перекачать заново. Но мы же не ищем легких путей, да и предлагался такой вариант! Итак, будем решать задачу по сложному — не скачивать.
Приступая к написанию любой программы, необходимо сначала продумать хотябы базовый алгоритм ее работы. В нашем случае алгоритм, по сути, состоит из двух шагов:
- Найти и прочитать все .torrent-файлы;
- Найти в куче файлов тот, который соответствует описанному в .torrent, и переместить его в папку, соответствующую пути в .torrent.
Для реализации своей идеи, я использовал C#, однако для этого подойдет любой язык, на котором есть библиотеки для чтения файлов в формате bencode и реализована возможность считать SHA-1 хеш.
Ну что же, приступим к решению поставленной задачи.
Ищем торренты и читаем их
После того, как я разобрался с устройством .torrent-файлов, передо мной встал вопрос парсинга всего этого чуда. Прошерстив интернет по данному вопросу, я обнаружил несколько .NET-библиотек под это дело. Выбор свой я остановил на, более-менее понятной и работающей из коробки библиотеке BencodeLibrary, однако впоследствии пришлось ее немного дополнить под свои нужды, но об этом позже.
Начнем с самого простого момента — чтения .torrent.
Строение .torrent-файла довольно простое — он представляет из себя словарь в формате bencode. В данном словаре нас интересует только пара с ключом info — блок описания файлов. Этот тоже является словарем и содержит в себе информацию об имени файлов, их размере. Кроме того, как многим известно, торрент хеширует файлы не целиком, а по кускам определенной длины, которая зависит от размера этих файлов. Информация о размере этого куска также содержится в словаре info.
Для хранения информации из прочитанного файла будем использовать такой класс Torrent:
public class Torrent
{
public Torrent(string name, List<LostFile> files, int pieceLength, char[] hash, string fileName)
{
Name = name;
Files = files;
PieceLength = pieceLength;
Hash = hash;
FileName= fileName;
}
public string Name;
public int PieceLength;
public char[] Hash;
public List<LostFile> Files;
public string FileName;
...
}Здесь поля хранят следующую информацию:
* Name — имя торрента (вообще говоря — имя папки или имя файла)
* Files — список файлов, которые нам надо будет в дальнейшем искать
* PieceLength — размер тех самых кусочков, хеш которых нам предстоит считать
* Hash — хеш строка всех файлов
* FileName — имя .torrent-файла на диске
Теперь стоит заострить внимание на строке хеша. Она составляется очень просто. Все файлы склеиваются в один (виртуально конечно) друг за другом, образуя при этом один БОЛЬШОООООООЙ воображаемый файл. В этом воображаемом файле берем кусок длины PieceLength, считаем SHA1 хеш, кладем хеш в строку, берем следующий кусок, считаем хеш, дописываем к концу строки с хешем предыдущего куска. Т. е. это обычная конкатенация хешей всех кусков.
Как мог заметить внимательный читатель, файл внутри класса — это не просто файл, а особый тип данных, в котором файл описывается некой конструкцией типа LostFile. Вот она:
public class LostFile
{
public LostFile(string name, long length, long beginFrom)
{
Name = name;
Length = length;
BeginFrom = beginFrom;
}
public string Name;
public long Length;
public long BeginFrom;
. . .
}
Здесь все просто: имя файла и его размер. Кроме того этот класс содержит еще одно поле — 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_1level_2_1file_1.txt и level_1level_2_2file_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-файла воедино, получаем:
static Torrent ReadTorrent(string filename)
{
List<LostFile> files = new List<LostFile>();
BDict torrent = (BDict)BencodingUtils.DecodeFile(filename);
BDict fileInfo = (BDict)torrent["info"];
string name = ((BString)fileInfo["name"]).Value;
int pieceLength = (int)((BInt)fileInfo["piece length"]).Value;
torrent = (BDict)BencodingUtils.DecodeFile(filename, Encoding.GetEncoding(437));
char[] pieces = ((BString)((BDict)torrent["info"])["pieces"]).Value.ToCharArray();
if (fileInfo.ContainsKey("files")) // Multifile 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));
begin += length;
}
}
else // Singlefile torrent
{
long Length = ((BInt)fileInfo["length"]).Value;
files.Add(new LostFile(name, Length, 1));
}
return new Torrent(name, files, pieceLength, pieces, filename);
}
Теперь, когда у нас есть все необходимые данные, мы готовы к самому интересному — поиску наших файлов.
Ищем файлы
Мы вплотную подошли к реализации второго шага нашего алгоритма. Для этого будем использовать метод 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 для списка, но его при использовании нельзя модифицировать этот спикок, то есть мы не сможем удалять уже ненужные более элементы. Итак, собирая все выше описанное в один метод, имеем:
public static void FindFiles(Torrent torrent, List<FileInfo> files, string destinationPath, bool copyFile)
{
for (int i = 0; i < torrent.Files.Count; i++)// (LostFile fileInTorrent in torrent.Files)
{
LostFile fileInTorrent = torrent.Files[i];
for (int j = 0; j < files.Count; j++)
{
FileInfo fileOnDisk = files[j];
// Ищем файл с таким же разширением
if (fileOnDisk.Extension != Path.GetExtension(fileInTorrent.Name))
continue;
// Проверяем размер
if (fileOnDisk.Length != fileInTorrent.Length)
continue;
// Проверяем хэш
if (!torrent.CheckHash(i, fileOnDisk))
continue;
// Все проверки пройдены. перед нами искомый файл
// Перемещаем его
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;
}
}
}
}
Ну вот! Самое вкусное.
Проверка хеша
Как видно из кода выше, для проверки хеша мы передаем имя файла на диске и номер файла в списке файлов торрента. Это надо для того, чтобы не запускать поиск в списке файлов, а сразу взять его по номеру, раз он известен (еще одно "+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. Такое ограничение даст нам возможность вычленить хотя бы один кусок для проверки, полность находящийся в файле. У такого подхода есть несколько существенных плюсов:
- Нет необходимости дополнительно искать на диске соседние файлы;
- Длина куска для хеширования очень редко превышает 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;
}
Собирая воедино сие творение возбужденного , получим метод следующего содержания:
public bool CheckHash(int index, FileInfo fileOnDisk)
{
LostFile checkingFile = this.Files[index];
if (checkingFile.Length < this.PieceLength * 2 - 1)
return false;
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];
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();
}
}
for (int i = 0; i < fileHash.Length; i++)
if (fileHash[i] != hashInTorrent[i])
return false;
return true;
}
На этой прекрасной ноте, рассказ о методах и алгоритмах заканчивается, и мы переходим к рассказу о реализации в реальной жизни данного творения. Вполне понятно, что данная задача мной решалась не для того, чтобы решить, а для того, чтобы реализовать. Поэтому привожу на суд общественности мое творение, которое реализует все то, о чем написано выше.
Программа
Программа написана, как уже упоминалось на C#. При работе не сильно прихотлива, требует только .NET 2.0. Есть однако одно ограничение на использование: торрент файлы и коллекцию лучше убрать из корня логического диска. Причина этого ограничения — использование при сканировании директорий параметра `SearchOption.AllDirectories`, что приводит к вылету при попытке прочитать закрытые директории типа корзины или `System Volume Information` (если знающие люди подскажут как это обойти, то буду весьма признателен). Для папки назначения особых ограничений естественно нет, главное чтобы влезло, и можно было в нее писать, иначе вылетит с ошибкой (не моделировал, но логично).
В процессе работы, после окончания обработки очередного файла, выводится результат — имя .torrent-файла на диске и количество обработанных файлов.
Чтобы запустить сканирование, необходимо выбрать три директории (с файлами .torrent, с файлами для сортировки и папку для отсортированного), по желанию указать две опции и запустить сканирование.
По поводу производительности. Она пока что низкая: обработка 10 больших torrent-файлов заняла около 5 минут.
Так как работает приложение в один поток, то во время выполнения интерфейс подвисает, но я над этим работаю. Также хочу напомнить, что файлы малого размера (меньше 2-х мегабайт) не будут перемещены по причине отсутствия возможности проверки хеша. Вполне вероятны ложные срабатывания из-за того, что проверяется только один кусок под номером firstChunkNumber. Пока что проверять все куски слишком затратно, но в планах есть.
Не ищите торренты рекурсивно, если они собраны в корне диска.
Копирование может занять много времени, поэтому интерфейс может подвиснуть — не пугайтесь.
Так как писалась эта программа 4fun, то качество кода там немного не то, которое хотелось бы, но у меня оно работает. Данная программа не тестировалась, исправлялись только очевидные ошибки, поэтому могут быть, да что скрывать-то, есть скрытые баги. ИСПОЛЬЗУЯ ДАННУЮ ПРОГРАММУ, ВЫ ИСПОЛЬЗУЕТЕ ЕЕ НА СВОЙ СТРАХ И РИСК.
Взять исходники можно на github. Распространяется по GPLv2. Там есть архив с исполняемым файлом. Для работы требуется библиотека Bencode Library, но не оригинальная, а модифицированная мною (есть у меня в репозитарии, подключена субмодулем).
Спасибо всем, кто проявил терпение и дочитал эту статью до конца. Рад услышать ваши вопросы, приветствуется всевозможная помощь в совершенствовании алгоритма и, в особенности, кода.
Источники: BitTorrentSpecification.
Автор: difiso
