CCITT-CRC16 Checksum

[wuf]

Eine Möglichkeit die CCITT-CRC16 Checksumme zu generieren.
Creation by wuf.
Suchte im Internet nach einer Python-Varianten , fand aber
nur Beispiele in C, BASIC und ASM. Habe schlussendlich
eine ASM-Variante nach Python konvertiert. Vielleicht gibt
es noch andere Python-Varianten?

Gruss wuf

Code: Alles auswählen

#!/usr/bin/env python
# -*- coding: UTF-8 -*-

# Funktion    : Generiert eine CRC16 Checksumme mit dem CCITT-Polynom
# Version     : 1.01
# Autor       : Fritz Wüst
# Datum       : 03.11.2003

def GenCCITT_CRC16(Buffer):
	#~~ Generierung der CCITT-CRC16 Checksumme
	numBytes = len(Buffer)
	numBits  = 8
	crcsum   = 0
	temp0    = 0
	temphigh = 0

	polynom = 0x1021 #CCITT Polynom

	for byte in range (numBytes):
		temp0  = ord(Buffer[byte])
		temp0  <<= 8
		crcsum ^= temp0

		for bit in range (numBits):
			crcsum   <<= 1
			temphigh =   crcsum
			temphigh &=  0xFFFF0000

			if temphigh > 0:
				#~~ Es gabe ein Übertrag ins Bit-16
				crcsum &= 0x0000FFFF
				crcsum ^= polynom
	return(crcsum)

Buffer = []

#~~ Datenliste
Buffer.append('A')
Buffer.append('B')
Buffer.append('C')
Buffer.append(chr(255))
Buffer.append(chr(255))
Buffer.append(chr(255))

CRC16 = GenCCITT_CRC16(Buffer)

#~~ Ausgabe der CCITT-CRC16 Checksumme
print "CRC16 (dezimal) = %d (hex) = %x" % (CRC16,CRC16)

[Dookie]

Hi wuf,

ich hab mal die Funktion zusammengekürzt und die typischen Assemblerteile in Python übersetzt

Code: Alles auswählen

def GenCCITT_CRC16(Buffer):
   #~~ Generierung der CCITT-CRC16 Checksumme
   bitrange = xrange(8) # 8 Bits
   crcsum   = 0
   polynom  = 0x1021 #CCITT Polynom

   for byte in Buffer:
      crcsum ^= ord(byte) << 8
      for bit in bitrange: # Schleife für 8 Bits 
         crcsum <<= 1
         if crcsum & 0x7FFF0000:
            #~~ Es gab einen Uebertrag ins Bit-16
            crcsum = (crcsum & 0x0000FFFF) ^ polynom
   return crcsum

dürfte jetzt noch etwas schneller laufen und gibt auch unter python2.3 kein Futurewarning mehr aus.


Gruß

Dookie

[wuf]

Hallo Dookie

Besten Dank für Deinen genialen Optimierungs-
Vorschlag. Deine CCITT-CRC16 Funktion sieht
wirklich sehr schlank aus. Ich nehme an, dass
Du nichts dagegen hast, wenn ich meine etwas
schwerfälligere Variante durch Deine optimierte
ersetze?
Noch eine Frage was die Ausführungsgeschwindigkeit
anbelangt. Gibt es in Python eine einfache
Möglichkeit um die Ausführgeschwindigkeit einer
Funktion z.B. dieser CCITT-CRC16 Funktion zu messen.
Klar wird eine solche Messung bei jedem PC je nach
seiner Performance anderst ausfallen aber es wäre
interessant zu sehen was den Zeitgewinn der Optimierung
brachte.
Vielleicht ist es auf den heutigen PC's mit > 1GHz
gar nicht möglich solch eine klein Zeitdifferenz zu
messen?

OK nochmals besten Dank Dookie.
Gruss Fritz

[Milan]

Du kannst Python die Zeit ja selber messen lassen. wichtig ist nur, dass er lange genug rechnet, damit de Messdaten genauer sind. Hintergrundprogramme können stören, weil die ja auch CPU Leistung haben wollen. Desto länger bzw öfter (dann halt mit Durchschnitt) das rechnet desto besser.

Messen tust du mit der Funktion clock aus dem Modul time

Code: Alles auswählen

import time
t1=time.clock()
...anweisungen...
t2=time.clock()
print t2 - t1

[Dookie]

Hi wuf,

Du kannst die Routine ja auch in einer Schleife aufrufen und dann die zeit mit der von Milan gezeigten Methode messen, die er für 10000 Durchläufe braucht.


Gruß

Dookie *derauchfritzheisst*

[wuf]

Hallo Milan & Dookie

Habe Deine Messmethode auf meine CCITT-CRC16
und Dookie's Variante angewandt. Dabei rufe
ich die Funktion 10'000 mal auf. Dookie's
Funktion bring auf meinem PC eine Ausführge-
schwindigkeitssteigerung von sage und schreibe
33%. Super! Es ist immer gut zu sehen wie es
andere machen. Das bringt einem automatisch
eine Verfeinerung bei der Anwendung der
Programmiersprache Python.

Besten Dank für Eure interessanten Tips!
Gruss Fritz

[Dookie]

Hallo nochmal wuf,

schön daß Dir mein Source so gefällt, wenn Du noch Fragen hast, warum ich was so und nicht anders gemacht hab, frag einfach. Jetzt jede einzelne Änderung zu erörtern würd wohl den Rahmen sprengen.
Du könntest auch noch in der Zeile

Code: Alles auswählen

crcsum <<= 1

Testen ob eine der folgenden Varianten schneller ist als der Bitshift.

Code: Alles auswählen

crcsum *= 2

oder

Code: Alles auswählen

crcsum += crcsum

grosse Unterschiede wird das zwar nicht mehr bringen, aber es könnte zeigen, wie gut Python von sich aus optimiert. Mit Assembler sollte, abhängig vom Prozessor, die Additonsvariante am schnellsten sein gefolgt vom Bitshift und weit abgeschlagen die Multiplikation.


Gruß

Dookie

[Beyond]

Zu Pyrthon und Profiling findet sich einiges im Internet --- und trivial scheint es nicht zu sein (wenn man's richtig machen will --- aber meist reichen wohl obere Vorschläge)

cu beyond