Простой алгоритм
На пальцАх...
Генерим первые хэши(по возрастанию паролей) до заполнения чанка.
Затем продолжаем генерить хэши, если попадается хэш меньше наибольшего в чанке - наибольший выбрасываем, вместо него вставляем текущий.
После полного прохода(2^48 хэшей) получаем чанк заполненный от минимального значения хэша(указанного в начале генерации чанка) подряд по возрастанию до заполнения чанка.
Наибольший хэш чанка+1 используем как минимальное значение для генерации следующего чанка.
В подробностях...
Код:
function make_chunk(min_hash){
i=0;
max_hash = 00 00 00 ... ;
//инициализация чанка
while(i<chunk_size){
if( (hash = next_hash()) >= min_hash) {
insert(hash);
if(hash > max_hash) max_hash = hash;
i++;
}
}
while( hash = next_hash() )
if( hash <= max_hash) max_hash = smart_insert(hash);
}
save_chunk();
return max_hash+1;
}
//тело
chunk_count = число чанков;
min_hash = 00 00 00 ...;
while(chunk_count--) min_hash = make_chunk(min_hash);
insert вставляет хэш в первое свободное место в чанке
smart_insert
если вставляемый хэш == наибольшему, возвращает его(в реализации с сохранением паролей сохраняет пароль соотв. вставляемому хэшу)
иначе текущий наибольший хэш отбрасывается, вместо него вставляемый. возвращаем наибольший хэш в чанке.
Таким образом для получения одного чанка необходимо сгенерить хэши от всех паролей(2^48 в нашем случае)
чанков при размере 2GB у нас 2048Pb/2Gb == 2048 *1024Gb/2Gb == 2048 * 512 - такое количество раз нам надо пройтись по всем паролям
Усложняем
Тот же алгоритм, но заполняем чанк от наибольшего по убыванию. Это позволит работать двум процессам независимо - один генерит чанки снизу вверх, другой сверху вниз.
Совсем усложняем
Запускаем первый процесс..
Функция smart_insert модифицирована - она не отбрасывает наибольший хэш при вставке а передает соседу. Сосед генерит соседний чанк. Это для генераторов по возрастанию. По убыванию передается наименьший хэш.
Передается функции smart_insert соседа. Если она видит что хэш ей не подходит - передает следующему соседу(слева/справа в зависимости от направления генерации)
Если соседа нет хэш отбрасывается...
Каждый следующий процесс сможет стартовать только после получения хэша от предыдущего соседа, так как это значение используется для стартового нижнего/верхнего порога. То есть после инициализации чанка предыдушим соседом, это недолго...
Первый процесс использует минимальное значение 00 00, максимальное ff ff ff
Чанк совсем необязательно хранить массивом, деревья подойдут лучше, алгоритмы быстрой вставки подробно расписаны, время вставки меньше времени генерации хэша...
ps скобочку в коде не закрыл... подправил...
Это все от слабости...