两个多字节二进制数据变量间的最快位异或方法

Question

实现以下逻辑的最快方法是什么：

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

在我的情况下，key 是一个20字节的sha1摘要，而data 是一些二进制数据，大小在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秒。

感谢所有提供想法和代码的人。你们真棒！

Answer 1

没有测试过

不知道这样做是否更快

假设我的字符串长度是4的倍数

def xor(hash,mystring):
    s = struct.Struct("<L")

    v1 = memoryview(hash)

    tab1 = []
    for i in range(5):
        tab1.append(s.unpack_from(v1,i*4)

    v2 = memoryview(mystring)
    tab2=[]
    for i in range(len(mystring)/4):
        tab2.append(s.unpack_from(v1,i*4))
    tab3 = []
    try:
        for i in range(len(mystring)/20):
            for j in range(5):
               tab3.append(s.pack(tab1[j]^tab2[5*i+j]))
    expect IndexError:
        pass
    return "".join(tab3)

Answer 2

如果 len(data) 的值很大，你可能会发现使用 xrange 会让速度明显变快。其实，你可以完全用 enumerate 来替代 range 函数。使用列表而不是在字符串上追加内容，也可能会让你受益。

def xor(data, key):
    l = len(key)
    buff = []
    for idx, val in enumerate(data):
        buff.append(chr(ord(val) ^ ord(key[idx % l]))
    return ''.join(buff)

我没有具体测过时间，但从我的经验来看，对于大量数据，这种方法应该会稍微快一些。记得每次改动后都要测一下速度。

如果分析显示 ord() 的调用真的耗时，你可以提前在 key 中的所有值上运行它，这样在循环中就可以省去一次调用。

你也可以把那个 for 循环改成普通的列表推导式，但这样可能会影响代码的可读性。不管怎样，试试看，看看速度是不是快了很多。

Answer 3

这段代码在Python 2.6及以上版本，包括Python 3.x，都可以正常运行。

from binascii import hexlify as _hexlify
from binascii import unhexlify as _unhexlify


def packl(lnum, padmultiple=0):
    """Packs the lnum (which must be convertable to a long) into a
    byte string 0 padded to a multiple of padmultiple bytes in size. 0
    means no padding whatsoever, so that packing 0 result in an empty
    string.  The resulting byte string is the big-endian two's
    complement representation of the passed in long."""

    if lnum == 0:
        return b'\0' * padmultiple
    elif lnum < 0:
        raise ValueError("Can only convert non-negative numbers.")
    s = hex(lnum)[2:]
    s = s.rstrip('L')
    if len(s) & 1:
        s = '0' + s
    s = _unhexlify(s)
    if (padmultiple != 1) and (padmultiple != 0):
        filled_so_far = len(s) % padmultiple
        if filled_so_far != 0:
            s = b'\0' * (padmultiple - filled_so_far) + s
    return s

def unpackl(bytestr):
    """Treats a byte string as a sequence of base 256 digits
    representing an unsigned integer in big-endian format and converts
    that representation into a Python integer."""

    return int(_hexlify(bytestr), 16) if len(bytestr) > 0 else 0

def xor(data, key):
    dlen = len(data)
    klen = len(key)
    if dlen > klen:
        key = key * ((dlen + klen - 1) // klen)
    key = key[:dlen]
    result = packl(unpackl(data) ^ unpackl(key))
    if len(result) < dlen:
         result = b'\0' * (dlen - len(result)) + result
    return result

这段代码同样适用于Python 2.7和3.x。它的好处是比之前的代码简单很多，同时基本上做的事情和之前的差不多，所需的时间也差不多：

from binascii import hexlify as _hexlify
from binascii import unhexlify as _unhexlify

def xor(data, key):
    dlen = len(data)
    klen = len(key)
    if dlen > klen:
        key = key * ((dlen + klen - 1) // klen)
    key = key[:dlen]
    data = int(_hexlify(data), 16)
    key = int(_hexlify(key), 16)
    result = (data ^ key) | (1 << (dlen * 8 + 7))
    # Python 2.6/2.7 only lines (comment out in Python 3.x)
    result = memoryview(hex(result))
    result = (result[4:-1] if result[-1] == 'L' else result[4:])
    # Python 3.x line
    #result = memoryview(hex(result).encode('ascii'))[4:]
    result = _unhexlify(result)
    return result