Python update trouble (2.3 to 2.4): x<<y

John Machin sjmachin at lexicon.net
Sun May 21 13:08:11 CEST 2006


Gonzalo wrote:
"""
I missed the point to add the *and* to workaround the long result
issue!
I think I understand it now.

I am timing the code once translated, so here are the results for the
crc calculation function.
"""

Yes, and both of us were missing the point that the "16" means 16 bits
wide!! It is carrying an extra 16 redundant bits that don't contribute
to the checking ability.

If your software *needs* to generate/check the exact same 32-bit-wide
CRC as calculated by that C routine, then what I gave you should be OK.
 Do you have any more test values? In particular test an empty string
and say "\x00" * 8 -- sometimes a CRC specification will do something
special with short strings e.g. pad them put with null bytes.

That C routine is actually, on further reading,  mind-boggling!! It
stops on a null byte, rather than working on a given length. A CRC is
normally expected to work on any data (including binary data) whether
it contains \x00 or not. What are you using it for??

If you don't have to interface with other software, AND a 16-bit check
is adequate, then at the end of this message is a 16-bit version which
will use only ints and therefore may run faster.

However you may wish to use a CRC32 which is supplied with Python (in
the binascii module).

A further note: what we have so far seems not to be the CCITT aka X.25
standard CRC-16 , but a reflection. See
http://www.joegeluso.com/software/articles/ccitt.htm
and also if you have the time and the determination, the article by
Ross Williams that it refers to.

Cheers,
John

=== 16-bit version ===
gCRC16Table = []

def InitCRC16():
    global gCRC16Table
    for i in xrange(0,256):
        crc = i << 8
        for j in xrange(0,8):
            if (crc & 0x8000) != 0:
                tmp = 0x1021
            else:
                tmp = 0
            crc = (crc << 1) ^ tmp
            crc &= 0xFFFF
        gCRC16Table.append(crc)

def CalcCRC16(astr):
    crc = 0xFFFF
    for c in astr:
        crc = gCRC16Table[((crc >> 8) & 255)] ^ ((crc & 0xFF) << 8) ^
ord(c)
        assert 0 <= crc <= 0xffff # remove when doing timings :-)
    return crc

test = "123456asdfg12345123"
InitCRC16()
result = CalcCRC16(test)
print result, hex(result)
======




More information about the Python-list mailing list