krot

CRC-64

Aug 26th, 2016
104
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // 64-bit CRC implementation - andrewl
  2. //
  3. // history:
  4. // Aug 02, 2009 - test inputs added, some explanations corrected
  5. // Jul 08, 2009 - created
  6.  
  7. #include <windows.h>
  8. #include <stdio.h>
  9.  
  10. // poly is: x^64 + x^62 + x^57 + x^55 + x^54 + x^53 + x^52 + x^47 + x^46 + x^45 + x^40 + x^39 +
  11. //          x^38 + x^37 + x^35 + x^33 + x^32 + x^31 + x^29 + x^27 + x^24 + x^23 + x^22 + x^21 +
  12. //          x^19 + x^17 + x^13 + x^12 + x^10 + x^9  + x^7  + x^4  + x^1  + 1
  13. //
  14. // represented here with lsb = highest degree term
  15. //
  16. // 1100100101101100010101111001010111010111100001110000111101000010_
  17. // ||  |  | || ||   | | ||||  | | ||| | ||||    |||    |||| |    | |
  18. // ||  |  | || ||   | | ||||  | | ||| | ||||    |||    |||| |    | +- x^64 (implied)
  19. // ||  |  | || ||   | | ||||  | | ||| | ||||    |||    |||| |    |
  20. // ||  |  | || ||   | | ||||  | | ||| | ||||    |||    |||| |    +--- x^62
  21. // ||  |  | || ||   | | ||||  | | ||| | ||||    |||    |||| +-------- x^57
  22. // .......................................................................
  23. // ||
  24. // |+---------------------------------------------------------------- x^1
  25. // +----------------------------------------------------------------- x^0 (1)
  26. UINT64 poly = 0xC96C5795D7870F42;
  27.  
  28. // input is dividend: as 0000000000000000000000000000000000000000000000000000000000000000<8-bit byte>
  29. // where the lsb of the 8-bit byte is the coefficient of the highest degree term (x^71) of the dividend
  30. // so division is really for input byte * x^64
  31.  
  32. // you may wonder how 72 bits will fit in 64-bit data type... well as the shift-right occurs, 0's are supplied
  33. // on the left (most significant) side ... when the 8 shifts are done, the right side (where the input
  34. // byte was placed) is discarded
  35.  
  36. // when done, table[XX] (where XX is a byte) is equal to the CRC of 00 00 00 00 00 00 00 00 XX
  37. //
  38. UINT64 table[256];
  39.  
  40. VOID generate_table()
  41. {
  42.     for(INT i=0; i<256; ++i)
  43.     {
  44.         UINT64 crc = i;
  45.  
  46.         for(UINT j=0; j<8; ++j)
  47.         {
  48.             // is current coefficient set?
  49.             if(crc & 1)
  50.             {
  51.                 // yes, then assume it gets zero'd (by implied x^64 coefficient of dividend)
  52.                 crc >>= 1;
  53.    
  54.                 // and add rest of the divisor
  55.                 crc ^= poly;
  56.             }
  57.             else
  58.             {
  59.                 // no? then move to next coefficient
  60.                 crc >>= 1;
  61.             }
  62.         }
  63.    
  64.         table[i] = crc;
  65.     }
  66. }
  67.  
  68. // will give an example CRC calculation for input array {0xDE, 0xAD}
  69. //
  70. // each byte represents a group of 8 coefficients for 8 dividend terms
  71. //
  72. // the actual polynomial dividend is:
  73. //
  74. // = DE       AD       00 00 00 00 00 00 00 00 (hex)
  75. // = 11011110 10101101 0000000000000000000...0 (binary)
  76. //   || ||||  | | || |
  77. //   || ||||  | | || +------------------------ x^71
  78. //   || ||||  | | |+-------------------------- x^69
  79. //   || ||||  | | +--------------------------- x^68
  80. //   || ||||  | +----------------------------- x^66
  81. //   || ||||  +------------------------------- x^64
  82. //   || ||||  
  83. //   || |||+---------------------------------- x^78
  84. //   || ||+----------------------------------- x^77
  85. //   || |+------------------------------------ x^76
  86. //   || +------------------------------------- x^75
  87. //   |+--------------------------------------- x^73
  88. //   +---------------------------------------- x^72
  89. //
  90.  
  91. // the basic idea behind how the table lookup results can be used with one
  92. // another is that:
  93. //
  94. // Mod(A * x^n, P(x)) = Mod(x^n * Mod(A, P(X)), P(X))
  95. //
  96. // in other words, an input data shifted towards the higher degree terms
  97. // changes the pre-computed crc of the input data by shifting it also
  98. // the same amount towards higher degree terms (mod the polynomial)
  99.  
  100. // here is an example:
  101. //
  102. // 1) input:
  103. //
  104. //    00 00 00 00 00 00 00 00 AD DE
  105. //          
  106. // 2) index crc table for byte DE (really for dividend 00 00 00 00 00 00 00 00 DE)
  107. //
  108. //    we get A8B4AFBDC5A6ACA4
  109. //
  110. // 3) apply that to the input stream:
  111. //
  112. //    00 00 00 00 00 00 00 00 AD DE
  113. //       A8 B4 AF BD C5 A6 AC A4
  114. //    -----------------------------
  115. //    00 A8 B4 AF BD C5 A6 AC 09
  116. //
  117. // 4) index crc table for byte 09 (really for dividend 00 00 00 00 00 00 00 00 09)
  118. //
  119. //    we get 448FCBB7FCB9E309
  120. //
  121. // 5) apply that to the input stream
  122. //
  123. //    00 A8 B4 AF BD C5 A6 AC 09
  124. //    44 8F CB B7 FC B9 E3 09
  125. //    --------------------------
  126. //    44 27 7F 18 41 7C 45 A5
  127. //
  128. //
  129. UINT64 calculate_crc(PBYTE stream, UINT n)
  130. {
  131.  
  132.     UINT64 crc = 0;
  133.  
  134.     for(INT i=0; i<n; ++i)
  135.     {
  136.         BYTE index = stream[i] ^ crc;
  137.         UINT64 lookup = table[index];
  138.  
  139.         crc >>= 8;
  140.         crc ^= lookup;
  141.     }
  142.  
  143.     return crc;
  144. }
  145.  
  146. VOID main(INT ac, PCHAR *av)
  147. {
  148.     generate_table();
  149.  
  150.     UINT64 result;
  151.  
  152.     printf("taking CRC64 of \"\x80\" (should be 0xC96C5795D7870F42)\n");
  153.     result = calculate_crc((PBYTE)"\x80", 1);
  154.     printf("result0: %016I64X\n", result);
  155.  
  156.     printf("taking CRC64 of \"\\xDE\\xAD\\xBE\\xEF\" (should be FC232C18806871AF)\n");
  157.     result = calculate_crc((PBYTE)"\xDE\xAD\xBE\xEF", 4);
  158.     printf("result: %016I64X\n", result);
  159.  
  160.     printf("taking CRC64 of \"99eb96dd94c88e975b585d2f28785e36\" (should be DB7AC38F63413C4E)\n");
  161.     result = calculate_crc((PBYTE)"\x99\xEB\x96\xDD\x94\xC8\x8E\x97\x5B\x58\x5D\x2F\x28\x78\x5E\x36", 16);
  162.     printf("result: %016I64X\n", result);
  163.  
  164.     printf("taking CRC64 of \"\\DE\\xAD\" (should be 44277F18417C45A5\n");
  165.     result = calculate_crc((PBYTE)"\xDE\xAD", 2);
  166.     printf("result: %016I64X\n", result);
  167.  
  168.     printf("ctrL+c to quit!\n");
  169.     while(1);
  170. }
RAW Paste Data