ActiveState Code

Recipe 259177: CRC64 - Calculate the cyclic redundancy check.

The algorithm to compute the CRC is described in the ISO 3309 standard. The generator polynomial is x64 + x4 + x3 + x + 1. Reference: W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, "Numerical recipes in C", 2nd ed., Cambridge University Press. Pages 896ff.

Python 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
# Initialisation
# 32 first bits of generator polynomial for CRC64
# the 32 lower bits are assumed to be zero

POLY64REVh = 0xd8000000L
CRCTableh = [0] * 256
CRCTablel = [0] * 256
isInitialized = False

def CRC64(aString):
    global isInitialized
    crcl = 0
    crch = 0
    if (isInitialized is not True):
        isInitialized = True
        for i in xrange(256): 
            partl = i
            parth = 0L
            for j in xrange(8):
                rflag = partl & 1L                
                partl >>= 1L               
                if (parth & 1):
                    partl |= (1L << 31L)
                parth >>= 1L
                if rflag:
	                parth ^= POLY64REVh
            CRCTableh[i] = parth;
            CRCTablel[i] = partl;

    for item in aString:
        shr = 0L
        shr = (crch & 0xFF) << 24
        temp1h = crch >> 8L
        temp1l = (crcl >> 8L) | shr                        
        tableindex = (crcl ^ ord(item)) & 0xFF
        
        crch = temp1h ^ CRCTableh[tableindex]
        crcl = temp1l ^ CRCTablel[tableindex]
    return (crch, crcl)

def CRC64digest(aString):
    return "%08X%08X" % (CRC64(aString))

if __name__ == '__main__':
    assert CRC64("IHATEMATH") == (3822890454, 2600578513)
    assert CRC64digest("IHATEMATH") == "E3DCADD69B01ADD1"
    print 'CRC64: dumb test successful'

Discussion

I've not found a CRC64 implementation for python, only a CRC32 from zlib, so I've shamelessly converted a perl one (from SWISS::CRC64, found at http://swissknife.sourceforge.net/CRC64.html). Any improvement/suggestion will be appreciated, as usual. /gp

Comments

  1. 1. At 3:07 p.m. on 28 sep 2004, Greg Czajkowski said:

    This one might be faster. I converted this version from

    http://lists.boost.org/MailArchives/boost/msg27062.php

    Its a one liner with a list of data values as input. I'm in the process of checking for correctness. If there is a faster way to write this please comment

    def CRC64(data):
    CRC64_Table = (0x0000000000000000L, 0x42F0E1EBA9EA3693L, 0x85E1C3D753D46D26L, 0xC711223CFA3E5BB5L,
               0x493366450E42ECDFL, 0x0BC387AEA7A8DA4CL, 0xCCD2A5925D9681F9L, 0x8E224479F47CB76AL,
               0x9266CC8A1C85D9BEL, 0xD0962D61B56FEF2DL, 0x17870F5D4F51B498L, 0x5577EEB6E6BB820BL,
               0xDB55AACF12C73561L, 0x99A54B24BB2D03F2L, 0x5EB4691841135847L, 0x1C4488F3E8F96ED4L,
               0x663D78FF90E185EFL, 0x24CD9914390BB37CL, 0xE3DCBB28C335E8C9L, 0xA12C5AC36ADFDE5AL,
               0x2F0E1EBA9EA36930L, 0x6DFEFF5137495FA3L, 0xAAEFDD6DCD770416L, 0xE81F3C86649D3285L,
               0xF45BB4758C645C51L, 0xB6AB559E258E6AC2L, 0x71BA77A2DFB03177L, 0x334A9649765A07E4L,
               0xBD68D2308226B08EL, 0xFF9833DB2BCC861DL, 0x388911E7D1F2DDA8L, 0x7A79F00C7818EB3BL,
               0xCC7AF1FF21C30BDEL, 0x8E8A101488293D4DL, 0x499B3228721766F8L, 0x0B6BD3C3DBFD506BL,
               0x854997BA2F81E701L, 0xC7B97651866BD192L, 0x00A8546D7C558A27L, 0x4258B586D5BFBCB4L,
               0x5E1C3D753D46D260L, 0x1CECDC9E94ACE4F3L, 0xDBFDFEA26E92BF46L, 0x990D1F49C77889D5L,
               0x172F5B3033043EBFL, 0x55DFBADB9AEE082CL, 0x92CE98E760D05399L, 0xD03E790CC93A650AL,
               0xAA478900B1228E31L, 0xE8B768EB18C8B8A2L, 0x2FA64AD7E2F6E317L, 0x6D56AB3C4B1CD584L,
               0xE374EF45BF6062EEL, 0xA1840EAE168A547DL, 0x66952C92ECB40FC8L, 0x2465CD79455E395BL,
               0x3821458AADA7578FL, 0x7AD1A461044D611CL, 0xBDC0865DFE733AA9L, 0xFF3067B657990C3AL,
               0x711223CFA3E5BB50L, 0x33E2C2240A0F8DC3L, 0xF4F3E018F031D676L, 0xB60301F359DBE0E5L,
               0xDA050215EA6C212FL, 0x98F5E3FE438617BCL, 0x5FE4C1C2B9B84C09L, 0x1D14202910527A9AL,
               0x93366450E42ECDF0L, 0xD1C685BB4DC4FB63L, 0x16D7A787B7FAA0D6L, 0x5427466C1E109645L,
               0x4863CE9FF6E9F891L, 0x0A932F745F03CE02L, 0xCD820D48A53D95B7L, 0x8F72ECA30CD7A324L,
               0x0150A8DAF8AB144EL, 0x43A04931514122DDL, 0x84B16B0DAB7F7968L, 0xC6418AE602954FFBL,
               0xBC387AEA7A8DA4C0L, 0xFEC89B01D3679253L, 0x39D9B93D2959C9E6L, 0x7B2958D680B3FF75L,
               0xF50B1CAF74CF481FL, 0xB7FBFD44DD257E8CL, 0x70EADF78271B2539L, 0x321A3E938EF113AAL,
               0x2E5EB66066087D7EL, 0x6CAE578BCFE24BEDL, 0xABBF75B735DC1058L, 0xE94F945C9C3626CBL,
               0x676DD025684A91A1L, 0x259D31CEC1A0A732L, 0xE28C13F23B9EFC87L, 0xA07CF2199274CA14L,
               0x167FF3EACBAF2AF1L, 0x548F120162451C62L, 0x939E303D987B47D7L, 0xD16ED1D631917144L,

    (comment continued...)

  2. 2. At 3:07 p.m. on 28 sep 2004, Greg Czajkowski said:

    (...continued from previous comment)

                   0x5F4C95AFC5EDC62EL, 0x1DBC74446C07F0BDL, 0xDAAD56789639AB08L, 0x985DB7933FD39D9BL,
               0x84193F60D72AF34FL, 0xC6E9DE8B7EC0C5DCL, 0x01F8FCB784FE9E69L, 0x43081D5C2D14A8FAL,
               0xCD2A5925D9681F90L, 0x8FDAB8CE70822903L, 0x48CB9AF28ABC72B6L, 0x0A3B7B1923564425L,
               0x70428B155B4EAF1EL, 0x32B26AFEF2A4998DL, 0xF5A348C2089AC238L, 0xB753A929A170F4ABL,
               0x3971ED50550C43C1L, 0x7B810CBBFCE67552L, 0xBC902E8706D82EE7L, 0xFE60CF6CAF321874L,
               0xE224479F47CB76A0L, 0xA0D4A674EE214033L, 0x67C58448141F1B86L, 0x253565A3BDF52D15L,
               0xAB1721DA49899A7FL, 0xE9E7C031E063ACECL, 0x2EF6E20D1A5DF759L, 0x6C0603E6B3B7C1CAL,
               0xF6FAE5C07D3274CDL, 0xB40A042BD4D8425EL, 0x731B26172EE619EBL, 0x31EBC7FC870C2F78L,
               0xBFC9838573709812L, 0xFD39626EDA9AAE81L, 0x3A28405220A4F534L, 0x78D8A1B9894EC3A7L,
               0x649C294A61B7AD73L, 0x266CC8A1C85D9BE0L, 0xE17DEA9D3263C055L, 0xA38D0B769B89F6C6L,
               0x2DAF4F0F6FF541ACL, 0x6F5FAEE4C61F773FL, 0xA84E8CD83C212C8AL, 0xEABE6D3395CB1A19L,
               0x90C79D3FEDD3F122L, 0xD2377CD44439C7B1L, 0x15265EE8BE079C04L, 0x57D6BF0317EDAA97L,
               0xD9F4FB7AE3911DFDL, 0x9B041A914A7B2B6EL, 0x5C1538ADB04570DBL, 0x1EE5D94619AF4648L,
               0x02A151B5F156289CL, 0x4051B05E58BC1E0FL, 0x87409262A28245BAL, 0xC5B073890B687329L,
               0x4B9237F0FF14C443L, 0x0962D61B56FEF2D0L, 0xCE73F427ACC0A965L, 0x8C8315CC052A9FF6L,
               0x3A80143F5CF17F13L, 0x7870F5D4F51B4980L, 0xBF61D7E80F251235L, 0xFD913603A6CF24A6L,
               0x73B3727A52B393CCL, 0x31439391FB59A55FL, 0xF652B1AD0167FEEAL, 0xB4A25046A88DC879L,
               0xA8E6D8B54074A6ADL, 0xEA16395EE99E903EL, 0x2D071B6213A0CB8BL, 0x6FF7FA89BA4AFD18L,
               0xE1D5BEF04E364A72L, 0xA3255F1BE7DC7CE1L, 0x64347D271DE22754L, 0x26C49CCCB40811C7L,
               0x5CBD6CC0CC10FAFCL, 0x1E4D8D2B65FACC6FL, 0xD95CAF179FC497DAL, 0x9BAC4EFC362EA149L,
               0x158E0A85C2521623L, 0x577EEB6E6BB820B0L, 0x906FC95291867B05L, 0xD29F28B9386C4D96L,
               0xCEDBA04AD0952342L, 0x8C2B41A1797F15D1L, 0x4B3A639D83414E64L, 0x09CA82762AAB78F7L,
               0x87E8C60FDED7CF9DL, 0xC51827E4773DF90EL, 0x020905D88D03A2BBL, 0x40F9E43324E99428L,
               0x2CFFE7D5975E55E2L, 0x6E0F063E3EB46371L, 0xA91E2402C48A38C4L, 0xEBEEC5E96D600E57L,
               0x65CC8190991CB93DL, 0x273C607B30F68FAEL, 0xE02D4247CAC8D41BL, 0xA2DDA3AC6322E288L,
               0xBE992B5F8BDB8C5CL, 0xFC69CAB42231BACFL, 0x3B78E888D80FE17AL, 0x7988096371E5D7E9L,
               0xF7AA4D1A85996083L, 0xB55AACF12C735610L, 0x724B8ECDD64D0DA5L, 0x30BB6F267FA73B36L,
               0x4AC29F2A07BFD00DL, 0x08327EC1AE55E69EL, 0xCF235CFD546BBD2BL, 0x8DD3BD16FD818BB8L,

    (comment continued...)

  3. 3. At 3:07 p.m. on 28 sep 2004, Greg Czajkowski said:

    (...continued from previous comment)

                   0x03F1F96F09FD3CD2L, 0x41011884A0170A41L, 0x86103AB85A2951F4L, 0xC4E0DB53F3C36767L,
               0xD8A453A01B3A09B3L, 0x9A54B24BB2D03F20L, 0x5D45907748EE6495L, 0x1FB5719CE1045206L,
               0x919735E51578E56CL, 0xD367D40EBC92D3FFL, 0x1476F63246AC884AL, 0x568617D9EF46BED9L,
               0xE085162AB69D5E3CL, 0xA275F7C11F7768AFL, 0x6564D5FDE549331AL, 0x279434164CA30589L,
               0xA9B6706FB8DFB2E3L, 0xEB46918411358470L, 0x2C57B3B8EB0BDFC5L, 0x6EA7525342E1E956L,
               0x72E3DAA0AA188782L, 0x30133B4B03F2B111L, 0xF7021977F9CCEAA4L, 0xB5F2F89C5026DC37L,
               0x3BD0BCE5A45A6B5DL, 0x79205D0E0DB05DCEL, 0xBE317F32F78E067BL, 0xFCC19ED95E6430E8L,
               0x86B86ED5267CDBD3L, 0xC4488F3E8F96ED40L, 0x0359AD0275A8B6F5L, 0x41A94CE9DC428066L,
               0xCF8B0890283E370CL, 0x8D7BE97B81D4019FL, 0x4A6ACB477BEA5A2AL, 0x089A2AACD2006CB9L,
               0x14DEA25F3AF9026DL, 0x562E43B4931334FEL, 0x913F6188692D6F4BL, 0xD3CF8063C0C759D8L,
               0x5DEDC41A34BBEEB2L, 0x1F1D25F19D51D821L, 0xD80C07CD676F8394L, 0x9AFCE626CE85B507L)

    return reduce(lambda x,y, t=CRC64_Table: t[((x>>56) ^ y) I converted this version from

http://lists.boost.org/MailArchives/boost/msg27062.php

Its a one liner with a list of data values as input. I'm in the process of checking for correctness. If there is a faster way to write this please comment
<pre>
def CRC64(data):
    CRC64_Table = (0x0000000000000000L, 0x42F0E1EBA9EA3693L, 0x85E1C3D753D46D26L, 0xC711223CFA3E5BB5L,
               0x493366450E42ECDFL, 0x0BC387AEA7A8DA4CL, 0xCCD2A5925D9681F9L, 0x8E224479F47CB76AL,
               0x9266CC8A1C85D9BEL, 0xD0962D61B56FEF2DL, 0x17870F5D4F51B498L, 0x5577EEB6E6BB820BL,
               0xDB55AACF12C73561L, 0x99A54B24BB2D03F2L, 0x5EB4691841135847L, 0x1C4488F3E8F96ED4L,
               0x663D78FF90E185EFL, 0x24CD9914390BB37CL, 0xE3DCBB28C335E8C9L, 0xA12C5AC36ADFDE5AL,
               0x2F0E1EBA9EA36930L, 0x6DFEFF5137495FA3L, 0xAAEFDD6DCD770416L, 0xE81F3C86649D3285L,
               0xF45BB4758C645C51L, 0xB6AB559E258E6AC2L, 0x71BA77A2DFB03177L, 0x334A9649765A07E4L,
               0xBD68D2308226B08EL, 0xFF9833DB2BCC861DL, 0x388911E7D1F2DDA8L, 0x7A79F00C7818EB3BL,
               0xCC7AF1FF21C30BDEL, 0x8E8A101488293D4DL, 0x499B3228721766F8L, 0x0B6BD3C3DBFD506BL,
               0x854997BA2F81E701L, 0xC7B97651866BD192L, 0x00A8546D7C558A27L, 0x4258B586D5BFBCB4L,
               0x5E1C3D753D46D260L, 0x1CECDC9E94ACE4F3L, 0xDBFDFEA26E92BF46L, 0x990D1F49C77889D5L,
               0x172F5B3033043EBFL, 0x55DFBADB9AEE082CL, 0x92CE98E760D05399L, 0xD03E790CC93A650AL,
               0xAA478900B1228E31L, 0xE8B768EB18C8B8A2L, 0x2FA64AD7E2F6E317L, 0x6D56AB3C4B1CD584L,

    (comment continued...)

  4. 4. At 3:07 p.m. on 28 sep 2004, Greg Czajkowski said:

    (...continued from previous comment)

                   0xE374EF45BF6062EEL, 0xA1840EAE168A547DL, 0x66952C92ECB40FC8L, 0x2465CD79455E395BL,
               0x3821458AADA7578FL, 0x7AD1A461044D611CL, 0xBDC0865DFE733AA9L, 0xFF3067B657990C3AL,
               0x711223CFA3E5BB50L, 0x33E2C2240A0F8DC3L, 0xF4F3E018F031D676L, 0xB60301F359DBE0E5L,
               0xDA050215EA6C212FL, 0x98F5E3FE438617BCL, 0x5FE4C1C2B9B84C09L, 0x1D14202910527A9AL,
               0x93366450E42ECDF0L, 0xD1C685BB4DC4FB63L, 0x16D7A787B7FAA0D6L, 0x5427466C1E109645L,
               0x4863CE9FF6E9F891L, 0x0A932F745F03CE02L, 0xCD820D48A53D95B7L, 0x8F72ECA30CD7A324L,
               0x0150A8DAF8AB144EL, 0x43A04931514122DDL, 0x84B16B0DAB7F7968L, 0xC6418AE602954FFBL,
               0xBC387AEA7A8DA4C0L, 0xFEC89B01D3679253L, 0x39D9B93D2959C9E6L, 0x7B2958D680B3FF75L,
               0xF50B1CAF74CF481FL, 0xB7FBFD44DD257E8CL, 0x70EADF78271B2539L, 0x321A3E938EF113AAL,
               0x2E5EB66066087D7EL, 0x6CAE578BCFE24BEDL, 0xABBF75B735DC1058L, 0xE94F945C9C3626CBL,
               0x676DD025684A91A1L, 0x259D31CEC1A0A732L, 0xE28C13F23B9EFC87L, 0xA07CF2199274CA14L,
               0x167FF3EACBAF2AF1L, 0x548F120162451C62L, 0x939E303D987B47D7L, 0xD16ED1D631917144L,
               0x5F4C95AFC5EDC62EL, 0x1DBC74446C07F0BDL, 0xDAAD56789639AB08L, 0x985DB7933FD39D9BL,
               0x84193F60D72AF34FL, 0xC6E9DE8B7EC0C5DCL, 0x01F8FCB784FE9E69L, 0x43081D5C2D14A8FAL,
               0xCD2A5925D9681F90L, 0x8FDAB8CE70822903L, 0x48CB9AF28ABC72B6L, 0x0A3B7B1923564425L,
               0x70428B155B4EAF1EL, 0x32B26AFEF2A4998DL, 0xF5A348C2089AC238L, 0xB753A929A170F4ABL,
               0x3971ED50550C43C1L, 0x7B810CBBFCE67552L, 0xBC902E8706D82EE7L, 0xFE60CF6CAF321874L,
               0xE224479F47CB76A0L, 0xA0D4A674EE214033L, 0x67C58448141F1B86L, 0x253565A3BDF52D15L,
               0xAB1721DA49899A7FL, 0xE9E7C031E063ACECL, 0x2EF6E20D1A5DF759L, 0x6C0603E6B3B7C1CAL,
               0xF6FAE5C07D3274CDL, 0xB40A042BD4D8425EL, 0x731B26172EE619EBL, 0x31EBC7FC870C2F78L,
               0xBFC9838573709812L, 0xFD39626EDA9AAE81L, 0x3A28405220A4F534L, 0x78D8A1B9894EC3A7L,
               0x649C294A61B7AD73L, 0x266CC8A1C85D9BE0L, 0xE17DEA9D3263C055L, 0xA38D0B769B89F6C6L,
               0x2DAF4F0F6FF541ACL, 0x6F5FAEE4C61F773FL, 0xA84E8CD83C212C8AL, 0xEABE6D3395CB1A19L,
               0x90C79D3FEDD3F122L, 0xD2377CD44439C7B1L, 0x15265EE8BE079C04L, 0x57D6BF0317EDAA97L,
               0xD9F4FB7AE3911DFDL, 0x9B041A914A7B2B6EL, 0x5C1538ADB04570DBL, 0x1EE5D94619AF4648L,
               0x02A151B5F156289CL, 0x4051B05E58BC1E0FL, 0x87409262A28245BAL, 0xC5B073890B687329L,
               0x4B9237F0FF14C443L, 0x0962D61B56FEF2D0L, 0xCE73F427ACC0A965L, 0x8C8315CC052A9FF6L,
               0x3A80143F5CF17F13L, 0x7870F5D4F51B4980L, 0xBF61D7E80F251235L, 0xFD913603A6CF24A6L,

    (comment continued...)

  5. 5. At 3:07 p.m. on 28 sep 2004, Greg Czajkowski said:

    (...continued from previous comment)

                   0x73B3727A52B393CCL, 0x31439391FB59A55FL, 0xF652B1AD0167FEEAL, 0xB4A25046A88DC879L,
               0xA8E6D8B54074A6ADL, 0xEA16395EE99E903EL, 0x2D071B6213A0CB8BL, 0x6FF7FA89BA4AFD18L,
               0xE1D5BEF04E364A72L, 0xA3255F1BE7DC7CE1L, 0x64347D271DE22754L, 0x26C49CCCB40811C7L,
               0x5CBD6CC0CC10FAFCL, 0x1E4D8D2B65FACC6FL, 0xD95CAF179FC497DAL, 0x9BAC4EFC362EA149L,
               0x158E0A85C2521623L, 0x577EEB6E6BB820B0L, 0x906FC95291867B05L, 0xD29F28B9386C4D96L,
               0xCEDBA04AD0952342L, 0x8C2B41A1797F15D1L, 0x4B3A639D83414E64L, 0x09CA82762AAB78F7L,
               0x87E8C60FDED7CF9DL, 0xC51827E4773DF90EL, 0x020905D88D03A2BBL, 0x40F9E43324E99428L,
               0x2CFFE7D5975E55E2L, 0x6E0F063E3EB46371L, 0xA91E2402C48A38C4L, 0xEBEEC5E96D600E57L,
               0x65CC8190991CB93DL, 0x273C607B30F68FAEL, 0xE02D4247CAC8D41BL, 0xA2DDA3AC6322E288L,
               0xBE992B5F8BDB8C5CL, 0xFC69CAB42231BACFL, 0x3B78E888D80FE17AL, 0x7988096371E5D7E9L,
               0xF7AA4D1A85996083L, 0xB55AACF12C735610L, 0x724B8ECDD64D0DA5L, 0x30BB6F267FA73B36L,
               0x4AC29F2A07BFD00DL, 0x08327EC1AE55E69EL, 0xCF235CFD546BBD2BL, 0x8DD3BD16FD818BB8L,
               0x03F1F96F09FD3CD2L, 0x41011884A0170A41L, 0x86103AB85A2951F4L, 0xC4E0DB53F3C36767L,
               0xD8A453A01B3A09B3L, 0x9A54B24BB2D03F20L, 0x5D45907748EE6495L, 0x1FB5719CE1045206L,
               0x919735E51578E56CL, 0xD367D40EBC92D3FFL, 0x1476F63246AC884AL, 0x568617D9EF46BED9L,
               0xE085162AB69D5E3CL, 0xA275F7C11F7768AFL, 0x6564D5FDE549331AL, 0x279434164CA30589L,
               0xA9B6706FB8DFB2E3L, 0xEB46918411358470L, 0x2C57B3B8EB0BDFC5L, 0x6EA7525342E1E956L,
               0x72E3DAA0AA188782L, 0x30133B4B03F2B111L, 0xF7021977F9CCEAA4L, 0xB5F2F89C5026DC37L,
               0x3BD0BCE5A45A6B5DL, 0x79205D0E0DB05DCEL, 0xBE317F32F78E067BL, 0xFCC19ED95E6430E8L,
               0x86B86ED5267CDBD3L, 0xC4488F3E8F96ED40L, 0x0359AD0275A8B6F5L, 0x41A94CE9DC428066L,
               0xCF8B0890283E370CL, 0x8D7BE97B81D4019FL, 0x4A6ACB477BEA5A2AL, 0x089A2AACD2006CB9L,
               0x14DEA25F3AF9026DL, 0x562E43B4931334FEL, 0x913F6188692D6F4BL, 0xD3CF8063C0C759D8L,
               0x5DEDC41A34BBEEB2L, 0x1F1D25F19D51D821L, 0xD80C07CD676F8394L, 0x9AFCE626CE85B507L)

    return reduce(lambda x,y, t=CRC64_Table: t[((x>>56) ^ y)

    </pre>

  6. 6. At 3:14 p.m. on 28 sep 2004, Greg Czajkowski said:

    Comment too long. The above comment doesn't show right. Here is the rest of the code

    return reduce(lambda x,y, t=CRC64_Table: t[((x>>56) ^ y) &amp; 0xFF] ^ (x &lt;&lt; 8), data, 0xffffffffffffffffL) ^ 0xffffffffffffffffL

Sign in to comment