Самый быстрый побитовый xor между двумя многобайтовыми двоичными переменными данных

Каков самый быстрый способ реализовать следующая логика:

def xor(data, key):
    l = len(key)

    buff = ""
    for i in range(0, len(data)):
        buff += chr(ord(data[i]) ^ ord(key[i % l]))
    return buff

В моем случае ключ - это 20-байтовый дайджест sha1, а данные - это некоторые двоичные данные длиной от 20 байтов до нескольких (1, 2, 3) мегабайт

ОБНОВЛЕНИЕ:

Хорошо, ребята. Вот реализация в 3,5 раза быстрее, которая разделяет данные и ключ на блоки по 4, 2 или 1 байту (в моем случае большую часть времени это целое число длиной 4 байта):

def xor(data, key):
    index = len(data) % 4
    size = (4, 1, 2, 1)[index]
    type = ('L', 'B', 'H', 'B')[index]
    key_len = len(key)/size
    data_len = len(data)/size
    key_fmt = "<" + str(key_len) + type;
    data_fmt = "<" + str(data_len) + type;

    key_list = struct.unpack(key_fmt, key)
    data_list = struct.unpack(data_fmt, data)

    result = []
    for i in range(data_len):
        result.append (key_list[i % key_len] ^ data_list[i])

    return struct.pack(data_fmt, *result)

Использует много памяти, но в моем случае случае это не имеет большого значения.

Есть идеи, как увеличить скорость еще в несколько раз? : -)

ОКОНЧАТЕЛЬНОЕ ОБНОВЛЕНИЕ:

Хорошо, хорошо ... numpy выполнил свою работу. Это просто невероятно быстро:

def xor(data, key):
    import numpy, math

    # key multiplication in order to match the data length
    key = (key*int(math.ceil(float(len(data))/float(len(key)))))[:len(data)]

    # Select the type size in bytes       
    for i in (8,4,2,1):
        if not len(data) % i: break

    if i == 8: dt = numpy.dtype('<Q8');
    elif i == 4: dt = numpy.dtype('<L4');
    elif i == 2: dt = numpy.dtype('<H2');
    else: dt = numpy.dtype('B');

    return numpy.bitwise_xor(numpy.fromstring(key, dtype=dt), numpy.fromstring(data, dtype=dt)).tostring()

Первоначальной реализации потребовалось 8 минут 50 секунд для обработки гигабайта, второй - около 2 минут 30 секунд, а последняя всего .... 0 минут 10 секунд.

Спасибо всем, кто внес идеи и код. Вы отличные ребята!

12
задан Nikolai Gorchilov 21 April 2011 в 13:15
поделиться