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

[Gonzalo Monzón]

Hi all!

I have been translating some Python custom C extension code into Python,
as I need these modules to be portable and run on a PocketPC without the
need of compile (for the purpose its a must 2.4 as it is the last
PythonCE release with great improvements).

But I've been stuck with a script wich does not work as expected once
translated to python, 2.4

In the meantime, I thought I could test it with an old 2.3 version I
have installed too on my computer, and found it run as expected, but see
the FutureWarning, so googled a bit and found PEP 237 and long integer
integration issue, but then can't find any workaround to fix the code
for Python 2.4

Hope somebody could point some suggestion, or perhaps, the solution is
pretty simple, but I missed it.

As I said, the code works fine on 2.3. I attach the code below.

The trouble is on the CalcCRC16 function, as you can see on the
FutureWarning message.

InitCRC16 function does some bitwise xor's too, but I checked it and
works as expected. Thought because only happen to be with small values
there.

Thanks in advance for any help,
Gonzalo

##############################
Python 2.3.2:

pytest1.py:90: FutureWarning: x<<y losing bits or changing sign will
return a long in Python 2.4 and up
crc = gCRC16Table[((crc >> 8) & 255)] ^ (crc << 8) ^ ord(str[x])
67560050

##############################
Python 2.4.2:

22002496167782427386022437441624938050682666541682
*Expected result is 67560050*
# #############################
# pytest1.py

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
gCRC16Table.append(crc)

def CalcCRC16(str):
global gCRC16Table

crc = 0xFFFF
for x in xrange(0,len(str)):
crc = gCRC16Table[((crc >> 8) & 255)] ^ (crc << 8) ^ ord(str[x])

return crc

test = "123456asdfg12345123"
InitCRC16()
print CalcCRC16(test)

[John Machin]

For a start,

22002496167782427386022437441624938050682666541682 & 0xffffffffL 67560050L

so you could just do that at the end.
But you don't really want to be carrying all that rubbish around,
getting longer and longer each time around the loop. And let's further
the translation into Python by getting rid of the xrange gizmoid and a
few other undesirables:

# tested on your 1 test value
def CalcCRC16v2(astr): # don't shadow str()
# global gCRC16Table # don't need this
crc = 0xFFFFL # start as a long
for c in astr:
crc = gCRC16Table[((crc >> 8) & 255)] ^ ((crc & 0xFFFFFF) << 8)
^ ord(c)
return crc

That should get you going. Although the whole calculation will be done
with longs instead of ints, the longs will never exceed 32 bits so it
shouldn't be too slow.

HTH,
John

[Gonzalo Monzón]

Thank you very much John,

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. I did expected a big gap, as this does a lot
of lookups to the crc table (a typical call gets 20-250 characters long)
so the C extension version with a simple array and pointers perform
really a lot better. The C code was glued with pyrex.

Fortunately I don't need a great performance for this code in the PocketPC!

C CalcCRC16
1 loops -> 4.75e-006 secs
210562 loops -> 0.133 secs
1580403 loops -> 0.973 secs
1580403 loops -> 0.973 secs 0.971 secs 1.12 secs
1580403 loops, best of 3 trials: 0.614 usec per loop

Python CalcCRC16
1 loops -> 0.000102 secs
9834 loops -> 0.832 secs
11824 loops -> 1.01 secs
11824 loops -> 1.01 secs 1.02 secs 1.01 secs
11824 loops, best of 3 trials: 85.1 usec per loop

Tested with: CalcCRC16('klldjs@ajsdla#kjfdsfj32389293rhcnacak12 932842fjos')

C Version:

long CalcCRC16(char *str)
{
long crc;

for(crc = 0xFFFF; *str != 0; str++) {
crc = CRC16Table [(( crc >> 8 ) & 255 )] ^ ( crc << 8 ) ^ *str;
}

return crc;
}
John Machin escribió:

For a start,

2200249616778242738602243744162493805068266654 1682 & 0xffffffffL

67560050L
so you could just do that at the end.
But you don't really want to be carrying all that rubbish around,
getting longer and longer each time around the loop. And let's further
the translation into Python by getting rid of the xrange gizmoid and a
few other undesirables:

# tested on your 1 test value
def CalcCRC16v2(astr): # don't shadow str()
# global gCRC16Table # don't need this
crc = 0xFFFFL # start as a long
for c in astr:
crc = gCRC16Table[((crc >> 8) & 255)] ^ ((crc & 0xFFFFFF) << 8)
^ ord(c)
return crc

That should get you going. Although the whole calculation will be done
with longs instead of ints, the longs will never exceed 32 bits so it
shouldn't be too slow.

HTH,
John

[John Machin]

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)
======

[Gonzalo Monzón]

Thank you for all the suggestions! :-)

The C routine is almost -changing data type long for word- a copy of the
function given by a hardware manufacturer, the same code used in their
firmware to calc the checksum of every piece of data sent or received,
and that data is somewhat special: it does not contain only plain ascii
character data (only 0x01 - 0x09 as delimiters) and every data set ends
with a 0x00 null byte so its fine to calculating checksum until "\x00"
is reached. And I must get the same crc calculations. That C routine
(and a very similar PHP one too) are tested for months and work smoothly.

And of course I should use integer not long!!... we aren't anymore in
the 8 bit computer era... ;-) original code from hardware manufacturer
use words by the way. And now really don't know why I used long. I
thought I did that way 'cause see pyrex C generated glue code always
using PyInt_FromLong so thought would use the same type.

I changed the C function to use integer, and it is performing a little
bit slowly than using longs (best with long: 0.614us, best with int:
0.629us), that is maybe as I said due pyrex glueing always the return
values with PyObject* PyInt_FromLong for all kind of short int to long
data types? Anyway both results are fine, and the timming gap is
insignificant (int: 1580403 loops -> 0.973 secs, long: 1601902 loops ->
1.01 secs) as i usually never have to call more than 100,000 times when
loading a full file data backup.

As a note for the checksum algorithm used here, I thought the hardware
manufacturer implemented this some years ago for serial data
transmission, but later attached some ethernet ports and they wanted to
have the protocol compatible. Anyway as I see in the link you reply, it
seems to be based in CCITT CRC-16, but they adapted to their own
requirements -performace issues for the hardware unit?- (never 0x00, etc.)

Regards,
Gonzalo.

John Machin escribió:

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)
======

[John Machin]

On 22/05/2006 5:22 AM, Gonzalo Monzón wrote:

Thank you for all the suggestions! :-)

The C routine is almost -changing data type long for word- a copy of the
function given by a hardware manufacturer, the same code used in their
firmware to calc the checksum of every piece of data sent or received,
and that data is somewhat special: it does not contain only plain ascii
character data (only 0x01 - 0x09 as delimiters) and every data set ends
with a 0x00 null byte so its fine to calculating checksum until "\x00"
is reached. And I must get the same crc calculations. That C routine
(and a very similar PHP one too) are tested for months and work smoothly.

And of course I should use integer not long!!... we aren't anymore in
the 8 bit computer era... ;-) original code from hardware manufacturer
use words by the way. And now really don't know why I used long. I
thought I did that way 'cause see pyrex C generated glue code always
using PyInt_FromLong so thought would use the same type.
Perhaps we need some amplification of "of course I should use integer
not long" :-)

Is the transmitted checksum (which your routine must create and/or
verify) 2 bytes long or 4 bytes long??? This is the most important
thing; once that is established, then you choose the C and/or Python
types and the mask (0xFFFF or 0xFFFFFFFF) as/if necessary. In that
original specification from the manufacturer, how wide was a "word"?

Note that in most/many C compilers at the moment, "int" and "long"
*both* mean 32 bits, to get 64 bits you need "long long" [or "_int64" or
whatever in realms under the sway of the dark tower], and "short" may
get you 16 bits if you are lucky. In a typical Python environment at the
moment, "int" uses the C "long", and thus typically will be 32 bits.
Python "long" is a variable-length data type.

Also note that even if the "checksum" is 32 bits wide, the high-order 16
bits are not verifiably useful, so you could use a [faster] 16-bit
version when receiving.

I changed the C function to use integer, and it is performing a little
bit slowly than using longs (best with long: 0.614us, best with int:
0.629us), that is maybe as I said due pyrex glueing always the return
values with PyObject* PyInt_FromLong for all kind of short int to long
data types? Anyway both results are fine, and the timming gap is
insignificant (int: 1580403 loops -> 0.973 secs, long: 1601902 loops ->
1.01 secs) as i usually never have to call more than 100,000 times when
loading a full file data backup.

I'm somewhat puzzled: Do you have the facility to cross-compile C to run
on the Pocket PC? If NO, why do you continue to mention fast versions
coded in C and glued with Pyrex? If YES, why did you include a Python
version in your initial question?

Cheers,

John

[Gonzalo Monzón]

Hi John!

John Machin escribió:

On 22/05/2006 5:22 AM, Gonzalo Monzón wrote:

Thank you for all the suggestions! :-)

The C routine is almost -changing data type long for word- a copy of the
function given by a hardware manufacturer, the same code used in their
firmware to calc the checksum of every piece of data sent or received,
and that data is somewhat special: it does not contain only plain ascii
character data (only 0x01 - 0x09 as delimiters) and every data set ends
with a 0x00 null byte so its fine to calculating checksum until "\x00"
is reached. And I must get the same crc calculations. That C routine
(and a very similar PHP one too) are tested for months and work smoothly.

And of course I should use integer not long!!... we aren't anymore in
the 8 bit computer era... ;-) original code from hardware manufacturer
use words by the way. And now really don't know why I used long. I
thought I did that way 'cause see pyrex C generated glue code always
using PyInt_FromLong so thought would use the same type.
Perhaps we need some amplification of "of course I should use integer
not long" :-)

Is the transmitted checksum (which your routine must create and/or
verify) 2 bytes long or 4 bytes long??? This is the most important
thing; once that is established, then you choose the C and/or Python
types and the mask (0xFFFF or 0xFFFFFFFF) as/if necessary. In that
original specification from the manufacturer, how wide was a "word"?

Is only 2 bytes long (0x0 to 0xFFFF). I really don't know how wide is a
"word" but I guess its 2 bytes long.
Note that in most/many C compilers at the moment, "int" and "long"
*both* mean 32 bits, to get 64 bits you need "long long" [or "_int64" or
whatever in realms under the sway of the dark tower], and "short" may
get you 16 bits if you are lucky. In a typical Python environment at the
moment, "int" uses the C "long", and thus typically will be 32 bits.
Python "long" is a variable-length data type.

Also note that even if the "checksum" is 32 bits wide, the high-order 16
bits are not verifiably useful, so you could use a [faster] 16-bit
version when receiving.

I changed the C function to use integer, and it is performing a little
bit slowly than using longs (best with long: 0.614us, best with int:
0.629us), that is maybe as I said due pyrex glueing always the return
values with PyObject* PyInt_FromLong for all kind of short int to long
data types? Anyway both results are fine, and the timming gap is
insignificant (int: 1580403 loops -> 0.973 secs, long: 1601902 loops ->
1.01 secs) as i usually never have to call more than 100,000 times when
loading a full file data backup.
I'm somewhat puzzled: Do you have the facility to cross-compile C to run
on the Pocket PC? If NO, why do you continue to mention fast versions
coded in C and glued with Pyrex? If YES, why did you include a Python
version in your initial question?

That is just because I have some modules for common communication tasks
with that hardware interface, and I use them in some PC applications,
but now I'm coding a similar application that runs on PocketPC, so I use
both versions of crc calculation in different applications: C/Pyrex on
the PC -compiled with distutils/gcc- , and the Python one I was having
trouble, only intended for PocketPC.

I still have to setup a ms.evc compiling environment for the new
PythonCE 2.4.3 release, but now haven't got the time so far, I'm in
hurry to finish a first demo release for the PocketPC app, so as I had
few C dependencies -modules in C/Pyrex for what I haven't got a working
Python version yet like that crc calc.- I thought would be a better idea
to re-code them in Python.

If you are curious about, I'm glad to show some screenshots of the
PocketPC app. -well, it runs fine both on the PC & PPC-. It is a sports
timing "remote point" application, it connects to timing hardware, send
data to main timing software via Internet and in the meanwhile gets
other point data and race results so you can have that info live on
every timing point while the race goes:
http://serveisw3.net/temp/ppc_preview/ppc_preview.html
Cheers,

John

Regards,
Gonzalo.