CRC64 checksum
Jeannot
je suis à la recherche d'un moyen de traiter les CRC64, en fait d'en
recalculer. Un petit tour sur le wiki et autres... et il y a du CRC16
et 32 bits dans tcllib mais pas 64... Quelqu'un à une idée? J'ai déjà
posté sur le comp.lang.tcl mais je n'ai pas encore trop eu de retour.
Merci d'avance.
Jeannot
Kevin Kenny
L'algorithme CRC64 n'est pas unique; on a adopté plusieurs polynômes
pour générer les codes. Est-ce qu'il s'agit des communications HDLC
(ISO3309) ou des bandes magnetiques DLT1 (ECMA-182)? Ou une autre
application avel laquelle il faut communiquer? Sinon, il vaudrait
mieux utiliser une fonction cryptographique comme MD5, SHA ou RIPEMD,
ou un code correcteur comme Reed-Solomon.
Dans Tcl 8.5, on peut utiliser les entiers de précision arbitraire.
Les modifications de tcllib (étant donné du polynôme!) pour CRC64
ne me semblent pas fort difficiles.
--
73 de ke9tv/2, Kevin
Jeannot
> pour générer les codes. Est-ce qu'il s'agit des communications HDLC
> (ISO3309) ou des bandes magnetiques DLT1 (ECMA-182)? Ou une autre
> application avel laquelle il faut communiquer?
Ok merci pour les informations, je ne connais pas trop ce type de
données. Je n'ai jamais eu affaire à des checksums ou autres
précedemment.
Ce sont des séquences de protéines qui sont codées en CRC64 pour un
accès plus rapide et transparente. Les contraintes de mon
environnement ne peuvent pas me faire choisir autre chose que CRC64 .
> Dans Tcl 8.5, on peut utiliser les entiers de précision arbitraire.
> Les modifications de tcllib (étant donné du polynôme!) pour CRC64
> ne me semblent pas fort difficiles.
je vais voir ce que je peux faire.
Merci
Jeannot
Eric Hassold
>> L'algorithme CRC64 n'est pas unique; on a adopté plusieurs polynômes
>> pour générer les codes. Est-ce qu'il s'agit des communications HDLC
>> (ISO3309) ou des bandes magnetiques DLT1 (ECMA-182)? Ou une autre
>> application avel laquelle il faut communiquer?
>
> Ok merci pour les informations, je ne connais pas trop ce type de
> données. Je n'ai jamais eu affaire à des checksums ou autres
> précedemment.
> Ce sont des séquences de protéines qui sont codées en CRC64 pour un
> accès plus rapide et transparente. Les contraintes de mon
> environnement ne peuvent pas me faire choisir autre chose que CRC64 .
Bonjour,
Si tu n'as pas une specification (ou une implementation de reference en
C ou autre) du CRC64 utilise, donne nous un exemple du CRC64 attendu
pour une donnee simple (genre "123456789" ou "hello"), et on pourra
tester si il s'agit bien d'un des deux (ISO ou ECMA) standards. Une fois
le polynome (et autres constantes) connu(es), l'implementation est assez
directe, completement similaire a celle du CRC32 (des lors que ton
interprete Tcl supporte bien les wide, c-a-d entiers 64 bits, ce qui est
tres tres probablement le cas si pas trop obsolete, et que le CRC en
question fonctionne sur des entrees de 8 bits, et non 16, 32 ou 64).
Si la performance importe (i.e. si la sequence sur laquelle il faut
calculer le CRC est longue), alors l'implementation en C, par dessus
critcl ou Odyce, peut etre plus pertinente, et guere plus complexe.
Eric
-----
Eric Hassold
Evolane - http://www.evolane.com/
Jeannot
merci de ton attention. La personne qui a calculé les CRC64 avant moi
utilisait une version en perl (:-)) ' Swiss_CRC64'. Je pencherai donc
pour la version ISO.
Voici quelques exemples:
7C7F42F76A6C3D90 -> MSGFELRASLFKSMNNSSSHDVQPWLSQEKARESTRAV
4E4400C8554CA2CB ->
MTLSHQRIDFSSSLAYSSSLISPPGTSVVGSSVGGATTVLPESSQPTTTPISKQPEKNKANVFLVIVCT
Question release de Tcl, je suis en 8.5.0 de ActiveState sans
extension (depuis hier ca me gonfle pas mal cf tcllib non inclus)...
je sais je sais Eric... David m'a presque convaincu pour eTcl :-). Je
vais devoir bientôt voir mon admin pour ca.
Concernant les performances, je ne sais pas trop encore. Il peut y
avoir beaucoup de séquences à traiter mais ce n'est pas onthefly. De
plus, j'imagine qu'entre la version perl et tcl on devrait être
équivalent en temps de calcul, non ?
Quel est la marche à suivre? je récupère les sources de tcllib et
essaie de modifier?
Merci d'avance?
Jeannot
Jeannot
merci de ton attention. La personne qui a calculé les CRC64 avant moi
utilisait une version en perl (:-)) ' Swiss_CRC64'. Je pencherai donc
pour la version ISO.
Voici quelques exemples:
7C7F42F76A6C3D90 -> MSGFELRASLFKSMNNSSSHDVQPWLSQEKARESTRAV
4E4400C8554CA2CB ->
MTLSHQRIDFSSSLAYSSSLISPPGTSVVGSSVGGATTVLPESSQPTTTPISKQPEKNKANVFLVIVCT
Question release de Tcl, je suis en 8.5.0 de ActiveState sans
extension (depuis hier ca me gonfle pas mal cf tcllib non inclus)...
je sais je sais Eric... David m'a presque convaincu pour eTcl :-). Je
vais devoir bientôt voir mon admin pour ca.
Concernant les performances, je ne sais pas trop encore. Il peut y
avoir beaucoup de séquences à traiter mais ce n'est pas onthefly. De
plus, j'imagine qu'entre la version perl et tcl on devrait être
équivalent en temps de calcul, non ?
Quel est la marche à suivre? je récupère les sources de tcllib et
essaie de modifier?
Merci d'avance?
Jeannot
>
Jeannot
merci de ton attention. La personne qui a calculé les CRC64 avant moi
utilisait une version en perl (:-)) ' Swiss_CRC64'. Je pencherai donc
pour la version ISO.
Voici quelques exemples:
7C7F42F76A6C3D90 -> MSGFELRASLFKSMNNSSSHDVQPWLSQEKARESTRAV
4E4400C8554CA2CB ->
MTLSHQRIDFSSSLAYSSSLISPPGTSVVGSSVGGATTVLPESSQPTTTPISKQPEKNKANVFLVIVCT
Question release de Tcl, je suis en 8.5.0 de ActiveState sans
extension (depuis hier ca me gonfle pas mal cf tcllib non inclus)...
je sais je sais Eric... David m'a presque convaincu pour eTcl :-). Je
vais devoir bientôt voir mon admin pour ca.
Concernant les performances, je ne sais pas trop encore. Il peut y
avoir beaucoup de séquences à traiter mais ce n'est pas onthefly. De
plus, j'imagine qu'entre la version perl et tcl on devrait être
équivalent en temps de calcul, non ?
Quel est la marche à suivre? je récupère les sources de tcllib et
essaie de modifier?
Merci d'avance?
Jeannot
>
Jeannot
page et a priori cela a eu pour conséquence la resoumission du
message...;-)
Jeannot
Kevin Kenny
> Bonjour Eric,
> merci de ton attention. La personne qui a calculé les CRC64 avant moi
> utilisait une version en perl (:-)) ' Swiss_CRC64'. Je pencherai donc
> pour la version ISO.
>
> Voici quelques exemples:
> 7C7F42F76A6C3D90 -> MSGFELRASLFKSMNNSSSHDVQPWLSQEKARESTRAV
> 4E4400C8554CA2CB ->
> MTLSHQRIDFSSSLAYSSSLISPPGTSVVGSSVGGATTVLPESSQPTTTPISKQPEKNKANVFLVIVCT
>
> Question release de Tcl, je suis en 8.5.0 de ActiveState sans
> extension (depuis hier ca me gonfle pas mal cf tcllib non inclus)...
> je sais je sais Eric... David m'a presque convaincu pour eTcl :-). Je
> vais devoir bientôt voir mon admin pour ca.
>
> Concernant les performances, je ne sais pas trop encore. Il peut y
> avoir beaucoup de séquences à traiter mais ce n'est pas onthefly. De
> plus, j'imagine qu'entre la version perl et tcl on devrait être
> équivalent en temps de calcul, non ?
>
> Quel est la marche à suivre? je récupère les sources de tcllib et
> essaie de modifier?
Swiss_CRC64 n'est que quarante lignes en Perl:
http://lists.open-bio.org/pipermail/biosql-l/2005-August/000907.html
Voilà le point de départ: les traduire dans Tcl.
Jeannot
encore eu le temps de me jeter dans quelque doc que ce soit...), je me
demandais quel est la différence entre l'algo du crc32 et 16 et 64?
est ce que c'est simplement quelques éléments à changer et la
structure est la même ou c'est un algo totalement différent?
Jeannot
Kevin Kenny
> Merci je vais voir ca. N'étant pas spécialiste des CRC (je n'ai pas
> encore eu le temps de me jeter dans quelque doc que ce soit...), je me
> demandais quel est la différence entre l'algo du crc32 et 16 et 64?
> est ce que c'est simplement quelques éléments à changer et la
> structure est la même ou c'est un algo totalement différent?
La structure grosse n'est pas totalement différent. Même dans les
algorithmes qui s'appellent «CRC16» ou «CRC32», il y a des différences.
Les algorithmes CRC marchent par des bits. Les règles d'interprétation
(par exemple, est-ce que le bit le plus ou le moins significant
est le premier?) diffèrent.
Eric Hassold
Bonjour,
Suite a ton post, j'ai ajoute la definition de CRC64-ISO a la liste des
CRC supportes dans le calculateur de digest de EvoTcl, et j'obtiens bien
le digest souhaite pour tes echantillons.
Normalement, le tout est un module utilise par une API OO de plus haut
niveau du module evolane::transform, mais j'ai defini une API simplifiee
pour le cas simple qui t'interesse (chaine->CRC64). Pas de dependance
donc, le code ci-dessous fait tout ce que tu souhaites (plus quelques
autres CRC, mais prennent pas tant de place que ca).
Pour calculer le CRC64 d'une chaine:
set crc64 [::crc::crc64 123456789]
(retourne en hexa, a mettre en majuscules pour correspondre strictement
a ton exemple).
Si interesse par la version complete, a venir dans release a jour de la
collection de modules EvoTcl, j'ai mis un snapshot du sous-ensemble
concerne dispo au telechargement depuis:
http://www.evolane.com/download/devel/evotcl-transform-20080617.zip
Sont inclus les supports des sommes crc64, crc32, crc16, crc16-usb,
ccitt, xmodem, hdlc, smbus,crc24, crc15, crc32c, bsd, sysv, adler32,
tclhash and jenkins, et des transformations yenc, uuencode et quoted.
Documentation...on y travaille.
Eric
-----
Eric Hassold
Evolane - http://www.evolane.com/
##################################################################
#
# Cyclic Redundancy Check (CRC) in Tcl
#
# Version : 0.2 (October 8, 2006)
#
# Author : Eric Hassold
# Email : has...@evolane.com
# Company : Evolane
# Web : http://www.evolane.com
#
##################################################################
namespace eval crc {
variable crc
set crc(ready) 0
set crc(ctxid) 0
}
proc crc::Init {} {
variable crc
if {$crc(ready)} {
return
}
# Common polynomials for supported CRC
variable poly
set poly(crc5-usb) {5 2 0}
set poly(smbus) {8 2 1 0}
set poly(crc15) {15 14 10 8 7 4 3 0}
set poly(crc16) {16 15 2 0}
set poly(ccitt) {16 12 5 0}
set poly(crc24) {24 23 18 17 14 11 10 7 6 5 4 3 1 0}
set poly(crc32) {32 26 23 22 16 12 11 10 8 7 5 4 2 1 0}
set poly(crc32c) {32 28 27 26 25 23 22 20 19 18 14 13 11 10 9 8 6 0}
# CRC-64-ISO
set poly(crc64) {64 4 3 1 0}
# CRC-64-ECMA-182
set poly(ecma) {
64 62 57 55 54 53 52 47 46 45 40 39 38 37 35 33
32 31 29 27 24 23 22 21 19 17 13 12 10 9 7 4 1 0
}
# For each polynomial (and reflection option), a CRC table is
# generated once, and saved in memory
variable crctable
array set crctable {}
}
# Generic helper for Bit reflection
proc crc::reflect {val {nbbits 32}} {
set r [expr {($val >> $nbbits) << $nbbits}]
for {set i 0} {$i < $nbbits} {incr i} {
if {$val & (1<<$i)} {
set r [expr {$r | (1<<(($nbbits-1)-$i))}]
}
}
return $r
}
# Create CRC lookup table from polynomial exponents
proc crc::CRCTable {poly {reflectin 0}} {
set width [lindex $poly 0]
# Convert list of exponents into a polynomial mask
if {$width<=32} {
set polymask 0
foreach b $poly {
if {$b==32} {
continue
}
set polymask [expr {int($polymask | (1<<$b))}]
}
set msbmask [expr {int(1 << ($width - 1))}]
set mask [expr {int(($msbmask-1)<<1 | 1)}]
set shiftmask [expr {int($mask ^ $msbmask)}]
} elseif {$width == 64} {
set polymask [expr {wide(0)}]
foreach b $poly {
if {$b==64} {
continue
}
set polymask [expr {wide($polymask | wide(1<<$b))}]
}
set msbmask [expr {wide(1 << ($width - 1))}]
set mask [expr {wide(($msbmask-1)<<1 | 1)}]
set shiftmask [expr {wide($mask ^ $msbmask)}]
} else {
error "invalid width"
}
set tablewidth 8
set tbl {}
for {set i 0} {$i < (1<<$tablewidth)} {incr i} {
if {$reflectin} {
set r [reflect $i $tablewidth]
} else {
set r $i
}
if {$width<=32} {
set r [expr { int($r) << ($width - $tablewidth)}]
} else {
set r [expr {wide($r) << ($width - $tablewidth)}]
}
for {set k 0} {$k < 8} {incr k} {
if {$r & $msbmask} {
set r [expr {(($r & $shiftmask) << 1) ^ $polymask}]
} else {
set r [expr {($r & $shiftmask) << 1}]
}
}
if {$reflectin} {
set r [reflect $r $width]
}
if {$width<=32} {
lappend tbl [expr {int($r & $mask)}]
} else {
lappend tbl [expr {wide($r & $mask)}]
}
}
return $tbl
}
# API for evolane::transform
proc crc::Create {this args} {
upvar \#0 $this ctx
variable crctable
variable poly
# Init package
Init
# Create table
set codec $ctx(codec)
switch -exact -- $codec {
"crc64" {
# ISO 3309
set polyname crc64
set seed 0
set reflect 1
set xor 0
}
"crc32" {
set polyname crc32
set seed 0xffffffff
set reflect 1
set xor 0xffffffff
}
"crc16" {
set polyname crc16
set seed 0
set reflect 1
set xor 0
}
"crc16-usb" {
set polyname crc16
set seed 0xffff
set reflect 1
set xor 0xffff
}
"ccitt" {
set polyname ccitt
set seed 0xffff
set reflect 0
set xor 0
}
"xmodem" {
set polyname ccitt
set seed 0
set reflect 0
set xor 0
}
"hdlc" {
# Used in X.25 and for the HDLC 2-byte FCS.
set polyname ccitt
set seed 0xffff
set reflect 1
set xor 0xffff
}
"smbus" {
# Used in ATM HEC and SMBus
set polyname smbus
set seed 0
set reflect 0
set xor 0
}
"crc24" {
set polyname crc24
set seed 0xb704ce
set reflect 0
set xor 0
}
"crc15" {
# Used in CAN (Controller Area Network) protocols
set polyname crc15
set seed 0
set reflect 0
set xor 0
}
"crc32c" {
# Used in iSCSI (RFC-3385)
set polyname crc32c
set seed 0xffffffff
set reflect 1
set xor 0xffffffff
}
"crc5-usb" {
# Used in USB Token and Start-Of-Frame packets
set polyname crc5-usb
set seed 0x1f
set reflect 1
set xor 0x1f
}
default {
error "Unsupported CRC mode \"$ctx(codec)\""
}
}
# Generate table if it doesn't already exist
if {![info exists crctable($codec)]} {
set crctable($codec) [CRCTable $poly($polyname) $reflect]
}
# Fill context members
set ctx(format) {c}
set ctx(crctable) $codec
set ctx(width) [lindex $poly($polyname) 0]
set ctx(reflectin) $reflect
set ctx(reflectout) $reflect
if {$ctx(width)<=32} {
set ctx(seed) [expr {int($seed)}]
set ctx(xor) [expr {int($xor)}]
} else {
set ctx(seed) [expr {wide($seed)}]
set ctx(xor) [expr {wide($xor)}]
}
if {$ctx(width) <= 32} {
set msbmask [expr {int(1 << ($ctx(width) - 1))}]
set mask [expr {int(($msbmask-1)<<1 | 1)}]
} elseif {$ctx(width) == 64} {
set msbmask [expr {wide(1 << ($ctx(width) - 1))}]
set mask [expr {wide(($msbmask-1)<<1 | 1)}]
} else {
error "unsupported width"
}
if {!$ctx(reflectin)} {
if {$ctx(width) <= 32} {
set smask [expr {int(($mask << 8) & $mask)}]
} else {
set smask [expr {wide(($mask << 8) & $mask)}]
}
} else {
if {$ctx(width) <= 32} {
set smask [expr {int((1<<($ctx(width)-8))-1)}]
} else {
set smask [expr {wide((1<<($ctx(width)-8))-1)}]
}
}
set ctx(msbmask) $msbmask
set ctx(mask) $mask
set ctx(smask) $smask
return
}
proc crc::Process {this bytes} {
upvar \#0 $this ctx
variable crctable
set mask $ctx(mask)
set smask $ctx(smask)
set rot [expr {$ctx(width) - 8}]
set crc $ctx(seed)
set tbl [set crctable($ctx(crctable))]
if {!$ctx(reflectin)} {
foreach b $bytes {
set ndx [expr {(($crc >> $rot) ^ $b) & 0xff}]
set lkp [lindex $tbl $ndx]
set crc [expr {($lkp ^ (($crc << 8) & $smask)) & $mask}]
}
} else {
foreach b $bytes {
set ndx [expr {($crc ^ $b) & 0xff}]
set lkp [lindex $tbl $ndx]
set crc [expr {($lkp ^ (($crc >> 8) & $smask)) & $mask}]
}
}
if {$ctx(width)<=32} {
set ctx(seed) [expr {int($crc)}]
} else {
set ctx(seed) [expr {wide($crc)}]
}
return
}
proc crc::Close {this} {
upvar \#0 $this ctx
set s $ctx(seed)
if {$ctx(reflectout)} {
# set s [reflect $s $ctx(width)]
}
if {$ctx(xor) != 0} {
set s [expr {$s ^ $ctx(xor)}]
}
return $s
}
# Standalone version
# This CRC code is designed to be used as a codec module for
# evolane::transform package. However, one may use this simplified
# API, with no external dependencies
proc crc::crc {method buffer} {
variable crc
set this "[namespace current]::ctx[incr crc(ctxid)]"
upvar \#0 $this ctx
set ctx(codec) $method
Create $this
set width $ctx(width)
binary scan $buffer c* bytes
Process $this $bytes
set r [Close $this]
unset $this
if {$width<=32} {
return [format %x $r]
} else {
return [format %lx $r]
}
}
proc crc::crc32 {buffer} {
return [crc crc32 $buffer]
}
proc crc::crc64 {buffer} {
return [crc crc64 $buffer]
}
Jeannot
David m'avait dit que tu étais un sacré développeur, bon ben le
biologiste que je suis reste sur le cul! :-)
je teste tout ca mais ca me parait nickel.
Jean
> Evolane -http://www.evolane.com/
>
> ##################################################################
> #
> # Cyclic Redundancy Check (CRC) in Tcl
> #
> # Version : 0.2 (October 8, 2006)
> #
> # Author : Eric Hassold
> # Email : hass...@evolane.com