crc.c
-
64 Bit Cyclic Redundant Code
-
XOR Long Division To Bytewise Table Lookup


Introduction | | Investigation | | C Implementation | | Conclusion | | Dense Boggle Board Solution - Full Disclosure | | Contact Information |


Introduction

    When a “DataMessage” is transmitted through potentially noisy channels, it makes sense to check for easily detectable errors.  While there are many ways to accomplish this goal, the crc standard wins because it maintains low false-positive probabilities, and at the same time, keeps computation confined to table lookups and single instruction “XOR”s .

    It is easy for an enthusiast, with a high-school education, to understand how a crc-digest is just the remainder when a bit-stream is treated as a single number and then long-divided by an engineered divisor using carry-less “XOR” subtraction.  This procedure is logical and clearly defined, but the seasoned computer programmer will anticipate optimizations, which transform a brute-force method into the high-level C-code used in production software.

    Looping to handle and shift each bit is possible, but slow.  Thus, a 256-value lookup-table is used to segment the calculation into 8-bits per loop.  A computer-machine with addressable Bytes will benefit from this chosen segmentation width.  Additionally, storing a 256 element table, each value consisting of “W” bits, is not costly when compared with the resources of modern computers.  The veteran programmer will understand how the X86-X64 architecture, with its Little-Endian Byte-Order, complicates the modification of a “DataMessage” to set its “CRC-Digest” to zero.

    Below, the reader will encounter some simple mathematics, and a proof, that when given the same “DataMessage”, modulo-2 long-division and the Bytewise lookup-table-procedure, generate the same “CRC-Digest”.  All of the information below is certainly available on the internet, but is not easily found on one web page.  This single web page will clarify the mathematics and C-code, which make CRC fast, and therefore very appealing.  Also, the C-code included was written to resemble textbook stock.

    Another important use for a CRC-digest is to easily identify small differences in long Byte strings, which are otherwise identical.  Skip forward to the Conclusion Section for the 17x17 Challenge prototype example.


Investigation

Modulo-2 XOR Mathematics:

    It should come as no surprise that a “CRC-Digest” is the remainder after some sort of division-like procedure.  When small changes are made to the digits of an enormous dividend, and that number is then divided by a reasonably-large divisor, the new calculated remainder will be garbled, and likely much different than the correct remainder.  Further, a method for carpentering a false-positive, although possible, is not immediately obvious.  Later, it will be shown that modulo-2 polynomial multiplication, where each bit represents the corresponding-power coefficient, can be used to generate false-positives.  This mathematical genre leads to naming the divisor, “Poly”.  Modulo-2 long-division is superior to actual long-division for CRC calculation, primarily because the only condition required to zero the Most Significant Bit(MSB) during a subtraction, is that both “MSB”s are “1”.  In actual long-division, when zeroing the “MSB” of the “CurrentRemainder”, the process of borrowing from higher columns demands additional comparisons, and often bit-width disparity.  Fortunately, there is no functional need for an actual valid remainder when checking the integrity of a “DataMessage”.  In conclusion, the modulo-2 remainder is a hard-to-plausible-false-positive, is easy to calculate, is manageable-in-size, and is a unique number to associate with a “DataMessage”.  It will be shown that a crude false-positive message is very easy to generate, knowing the size of “DataMessage”, the “Poly” being used, and the expected “CRC-Digest”.  A plausible false-positive, on the other hand, requires an intact “DataMessage”, the “Poly”, and computation based on solid knowledge of modulo-2 polynomial multiplication.  The knowledge needed can be learned on this web page.

    Prior to formalizing the steps involved in calculating the “CRC-Digest” of a “DataMessage”, it is useful to refine “modulo-2 XOR arithmetic” down to a set of rules that define its essence:

XORs In Succession
         0   0                   0 
     0   C6   A5   B4   A3   0   D1   B0 
     B7   A6   0   C4   B3   A2   C1   0 
     A7   B6   C5   A4   0   D2   A1   C0 
     C7   D6   D5   0   D3   C2   B1   D0 
 XOR   D7   0   B5   D4   C3   B2   0   A0 
----- ---- ---- ---- ---- ---- ---- ---- ----
     E7   E6   E5   E4   E3   E2   E1   E0 

Step 1 - Traditional Modulo-2 Bitwise Binary-Long-Division:

    The example calculation carried out below will generate an 8-bit-wide CRC remainder to keep it short.  A 3 Byte “DataMessage” is used, so as to clearly demonstrate the eventual “bitwise” to “Bytewise” transition.

  The following values are used in the worked example below:

Authentic Modulo-2 Bitwise Long-Division Example
Output Of Clear-CRC-8.c
---------------------------------------------------------------------------------

Behold the |3| Byte DataMessage - |11001010|00101101|10100110|

End Event #1
Behold TheDigest-|90|-|01011010|

---------------------------------------------------------------------------------

Append "W" zeros to the DataMessage - |11001010|00101101|10100110|00000000|

End Event #2
Behold TheDigest-|153|-|10011001|

---------------------------------------------------------------------------------

"TheDigest" of this DataMessage should be zero - |11001010|00101101|10100110|10011001|

End Event #2
Behold TheDigest-|0|-|00000000|

---------------------------------------------------------------------------------

Step 2 - Byte-Isolated Bitwise Modulo-2 Binary-Long-Division:

    The second calculation carried out by hand uses the same “DataMessage” and “Poly”.  The calculated “CRC-Digest” is the same, because each “XOR” column has an equal “1” bit-parity to the corresponding column in the first example.  The big transition is that each Byte in the “DataMessage” is isolated.  Token zeros are pulled into the “CurrentRemainder” register, and as a result, we can highlight the numbers, which will become the lookup-table index and return values.  The algorithm for lookup-table creation is now plain to see.

Authentic Transition To Byte-wise CRC-Calculation Example

Step 3 - Transition From Bitwise Long-Division To XOR Lookup-Table:

    The calculation above demonstrates and reinforces that the addition of extra “0”s to any column in the “XOR” cascade will have no effect on the final“CRC-Digest”.  Thus, as the most significant Byte is removed from the “WorkingRegister”, the next “DataMessage” Byte is drawn into “WorkingRegister” from the least-significant-side, and the new register value is “XOR”ed with the number returned from the lookup table.  This continues until the final “DataMessage” Byte has been pulled in, and then the value inside of “WorkingRegister” is the “CRC-Digest”.

Step 4 - Byte-Isolated Lookup-Table CRC-Digest Calculation:

    This algorithm is short, streamlined, and very appealing.  Just start with a “WorkingRegister” of width “W”, and fill it with “0”s.  Then pull out a Byte from the most-significant-side of the register, using it to index the lookup-table.  Pull the next “DataMessage” Byte into the least-significant-side of the register, and then “XOR” the “WorkingRegister” with the value returned by the lookup-table, back into the register.  When zero is used to index the lookup-table, a zero is returned, and thus the “XOR” has no effect; the next “DataMessage” Byte being pulled in from the least-significant-side is all that happens.  This loop continues until the final “DataMessage” Byte is pulled in and the last “XOR” operation is carried out.  Refer to crc.c for the working C-code.  Below, you will find the CRC-8 and CRC-64 lookup-tables.  Find the code used to create the tables here:  Compile-CRC-8-Lookup-Table.c, and here Compile-CRC-64-Lookup-Table.c.  Notice that the CRC-8 lookup-table represents a perfect and complete 1-to-1 function.  This will be explored in the next section.

CRC-8 Lookup-Table:  Divisor = (1|11010101|):
|  0|-|00|
|  1|-|D5|
|  2|-|7F|
|  3|-|AA|
|  4|-|FE|
|  5|-|2B|
|  6|-|81|
|  7|-|54|
|  8|-|29|
|  9|-|FC|
| 10|-|56|
| 11|-|83|
| 12|-|D7|
| 13|-|02|
| 14|-|A8|
| 15|-|7D|
| 16|-|52|
| 17|-|87|
| 18|-|2D|
| 19|-|F8|
| 20|-|AC|
| 21|-|79|
| 22|-|D3|
| 23|-|06|
| 24|-|7B|
| 25|-|AE|
| 26|-|04|
| 27|-|D1|
| 28|-|85|
| 29|-|50|
| 30|-|FA|
| 31|-|2F|
| 32|-|A4|
| 33|-|71|
| 34|-|DB|
| 35|-|0E|
| 36|-|5A|
| 37|-|8F|
| 38|-|25|
| 39|-|F0|
| 40|-|8D|
| 41|-|58|
| 42|-|F2|
| 43|-|27|
| 44|-|73|
| 45|-|A6|
| 46|-|0C|
| 47|-|D9|
| 48|-|F6|
| 49|-|23|
| 50|-|89|
| 51|-|5C|
| 52|-|08|
| 53|-|DD|
| 54|-|77|
| 55|-|A2|
| 56|-|DF|
| 57|-|0A|
| 58|-|A0|
| 59|-|75|
| 60|-|21|
| 61|-|F4|
| 62|-|5E|
| 63|-|8B|
| 64|-|9D|
| 65|-|48|
| 66|-|E2|
| 67|-|37|
| 68|-|63|
| 69|-|B6|
| 70|-|1C|
| 71|-|C9|
| 72|-|B4|
| 73|-|61|
| 74|-|CB|
| 75|-|1E|
| 76|-|4A|
| 77|-|9F|
| 78|-|35|
| 79|-|E0|
| 80|-|CF|
| 81|-|1A|
| 82|-|B0|
| 83|-|65|
| 84|-|31|
| 85|-|E4|
| 86|-|4E|
| 87|-|9B|
| 88|-|E6|
| 89|-|33|
| 90|-|99|
| 91|-|4C|
| 92|-|18|
| 93|-|CD|
| 94|-|67|
| 95|-|B2|
| 96|-|39|
| 97|-|EC|
| 98|-|46|
| 99|-|93|
|100|-|C7|
|101|-|12|
|102|-|B8|
|103|-|6D|
|104|-|10|
|105|-|C5|
|106|-|6F|
|107|-|BA|
|108|-|EE|
|109|-|3B|
|110|-|91|
|111|-|44|
|112|-|6B|
|113|-|BE|
|114|-|14|
|115|-|C1|
|116|-|95|
|117|-|40|
|118|-|EA|
|119|-|3F|
|120|-|42|
|121|-|97|
|122|-|3D|
|123|-|E8|
|124|-|BC|
|125|-|69|
|126|-|C3|
|127|-|16|
|128|-|EF|
|129|-|3A|
|130|-|90|
|131|-|45|
|132|-|11|
|133|-|C4|
|134|-|6E|
|135|-|BB|
|136|-|C6|
|137|-|13|
|138|-|B9|
|139|-|6C|
|140|-|38|
|141|-|ED|
|142|-|47|
|143|-|92|
|144|-|BD|
|145|-|68|
|146|-|C2|
|147|-|17|
|148|-|43|
|149|-|96|
|150|-|3C|
|151|-|E9|
|152|-|94|
|153|-|41|
|154|-|EB|
|155|-|3E|
|156|-|6A|
|157|-|BF|
|158|-|15|
|159|-|C0|
|160|-|4B|
|161|-|9E|
|162|-|34|
|163|-|E1|
|164|-|B5|
|165|-|60|
|166|-|CA|
|167|-|1F|
|168|-|62|
|169|-|B7|
|170|-|1D|
|171|-|C8|
|172|-|9C|
|173|-|49|
|174|-|E3|
|175|-|36|
|176|-|19|
|177|-|CC|
|178|-|66|
|179|-|B3|
|180|-|E7|
|181|-|32|
|182|-|98|
|183|-|4D|
|184|-|30|
|185|-|E5|
|186|-|4F|
|187|-|9A|
|188|-|CE|
|189|-|1B|
|190|-|B1|
|191|-|64|
|192|-|72|
|193|-|A7|
|194|-|0D|
|195|-|D8|
|196|-|8C|
|197|-|59|
|198|-|F3|
|199|-|26|
|200|-|5B|
|201|-|8E|
|202|-|24|
|203|-|F1|
|204|-|A5|
|205|-|70|
|206|-|DA|
|207|-|0F|
|208|-|20|
|209|-|F5|
|210|-|5F|
|211|-|8A|
|212|-|DE|
|213|-|0B|
|214|-|A1|
|215|-|74|
|216|-|09|
|217|-|DC|
|218|-|76|
|219|-|A3|
|220|-|F7|
|221|-|22|
|222|-|88|
|223|-|5D|
|224|-|D6|
|225|-|03|
|226|-|A9|
|227|-|7C|
|228|-|28|
|229|-|FD|
|230|-|57|
|231|-|82|
|232|-|FF|
|233|-|2A|
|234|-|80|
|235|-|55|
|236|-|01|
|237|-|D4|
|238|-|7E|
|239|-|AB|
|240|-|84|
|241|-|51|
|242|-|FB|
|243|-|2E|
|244|-|7A|
|245|-|AF|
|246|-|05|
|247|-|D0|
|248|-|AD|
|249|-|78|
|250|-|D2|
|251|-|07|
|252|-|53|
|253|-|86|
|254|-|2C|
|255|-|F9|


CRC-64 Lookup-Table:  Divisor = (1|01000010|11110000|11100001|11010111|01010011|11010100|01101101|0010011|):
|  0|-|0000000000000000|
|  1|-|42F0E1EBA9EA3693|
|  2|-|85E1C3D753D46D26|
|  3|-|C711223CFA3E5BB5|
|  4|-|493366450E42ECDF|
|  5|-|0BC387AEA7A8DA4C|
|  6|-|CCD2A5925D9681F9|
|  7|-|8E224479F47CB76A|
|  8|-|9266CC8A1C85D9BE|
|  9|-|D0962D61B56FEF2D|
| 10|-|17870F5D4F51B498|
| 11|-|5577EEB6E6BB820B|
| 12|-|DB55AACF12C73561|
| 13|-|99A54B24BB2D03F2|
| 14|-|5EB4691841135847|
| 15|-|1C4488F3E8F96ED4|
| 16|-|663D78FF90E185EF|
| 17|-|24CD9914390BB37C|
| 18|-|E3DCBB28C335E8C9|
| 19|-|A12C5AC36ADFDE5A|
| 20|-|2F0E1EBA9EA36930|
| 21|-|6DFEFF5137495FA3|
| 22|-|AAEFDD6DCD770416|
| 23|-|E81F3C86649D3285|
| 24|-|F45BB4758C645C51|
| 25|-|B6AB559E258E6AC2|
| 26|-|71BA77A2DFB03177|
| 27|-|334A9649765A07E4|
| 28|-|BD68D2308226B08E|
| 29|-|FF9833DB2BCC861D|
| 30|-|388911E7D1F2DDA8|
| 31|-|7A79F00C7818EB3B|
| 32|-|CC7AF1FF21C30BDE|
| 33|-|8E8A101488293D4D|
| 34|-|499B3228721766F8|
| 35|-|0B6BD3C3DBFD506B|
| 36|-|854997BA2F81E701|
| 37|-|C7B97651866BD192|
| 38|-|00A8546D7C558A27|
| 39|-|4258B586D5BFBCB4|
| 40|-|5E1C3D753D46D260|
| 41|-|1CECDC9E94ACE4F3|
| 42|-|DBFDFEA26E92BF46|
| 43|-|990D1F49C77889D5|
| 44|-|172F5B3033043EBF|
| 45|-|55DFBADB9AEE082C|
| 46|-|92CE98E760D05399|
| 47|-|D03E790CC93A650A|
| 48|-|AA478900B1228E31|
| 49|-|E8B768EB18C8B8A2|
| 50|-|2FA64AD7E2F6E317|
| 51|-|6D56AB3C4B1CD584|
| 52|-|E374EF45BF6062EE|
| 53|-|A1840EAE168A547D|
| 54|-|66952C92ECB40FC8|
| 55|-|2465CD79455E395B|
| 56|-|3821458AADA7578F|
| 57|-|7AD1A461044D611C|
| 58|-|BDC0865DFE733AA9|
| 59|-|FF3067B657990C3A|
| 60|-|711223CFA3E5BB50|
| 61|-|33E2C2240A0F8DC3|
| 62|-|F4F3E018F031D676|
| 63|-|B60301F359DBE0E5|
| 64|-|DA050215EA6C212F|
| 65|-|98F5E3FE438617BC|
| 66|-|5FE4C1C2B9B84C09|
| 67|-|1D14202910527A9A|
| 68|-|93366450E42ECDF0|
| 69|-|D1C685BB4DC4FB63|
| 70|-|16D7A787B7FAA0D6|
| 71|-|5427466C1E109645|
| 72|-|4863CE9FF6E9F891|
| 73|-|0A932F745F03CE02|
| 74|-|CD820D48A53D95B7|
| 75|-|8F72ECA30CD7A324|
| 76|-|0150A8DAF8AB144E|
| 77|-|43A04931514122DD|
| 78|-|84B16B0DAB7F7968|
| 79|-|C6418AE602954FFB|
| 80|-|BC387AEA7A8DA4C0|
| 81|-|FEC89B01D3679253|
| 82|-|39D9B93D2959C9E6|
| 83|-|7B2958D680B3FF75|
| 84|-|F50B1CAF74CF481F|
| 85|-|B7FBFD44DD257E8C|
| 86|-|70EADF78271B2539|
| 87|-|321A3E938EF113AA|
| 88|-|2E5EB66066087D7E|
| 89|-|6CAE578BCFE24BED|
| 90|-|ABBF75B735DC1058|
| 91|-|E94F945C9C3626CB|
| 92|-|676DD025684A91A1|
| 93|-|259D31CEC1A0A732|
| 94|-|E28C13F23B9EFC87|
| 95|-|A07CF2199274CA14|
| 96|-|167FF3EACBAF2AF1|
| 97|-|548F120162451C62|
| 98|-|939E303D987B47D7|
| 99|-|D16ED1D631917144|
|100|-|5F4C95AFC5EDC62E|
|101|-|1DBC74446C07F0BD|
|102|-|DAAD56789639AB08|
|103|-|985DB7933FD39D9B|
|104|-|84193F60D72AF34F|
|105|-|C6E9DE8B7EC0C5DC|
|106|-|01F8FCB784FE9E69|
|107|-|43081D5C2D14A8FA|
|108|-|CD2A5925D9681F90|
|109|-|8FDAB8CE70822903|
|110|-|48CB9AF28ABC72B6|
|111|-|0A3B7B1923564425|
|112|-|70428B155B4EAF1E|
|113|-|32B26AFEF2A4998D|
|114|-|F5A348C2089AC238|
|115|-|B753A929A170F4AB|
|116|-|3971ED50550C43C1|
|117|-|7B810CBBFCE67552|
|118|-|BC902E8706D82EE7|
|119|-|FE60CF6CAF321874|
|120|-|E224479F47CB76A0|
|121|-|A0D4A674EE214033|
|122|-|67C58448141F1B86|
|123|-|253565A3BDF52D15|
|124|-|AB1721DA49899A7F|
|125|-|E9E7C031E063ACEC|
|126|-|2EF6E20D1A5DF759|
|127|-|6C0603E6B3B7C1CA|
|128|-|F6FAE5C07D3274CD|
|129|-|B40A042BD4D8425E|
|130|-|731B26172EE619EB|
|131|-|31EBC7FC870C2F78|
|132|-|BFC9838573709812|
|133|-|FD39626EDA9AAE81|
|134|-|3A28405220A4F534|
|135|-|78D8A1B9894EC3A7|
|136|-|649C294A61B7AD73|
|137|-|266CC8A1C85D9BE0|
|138|-|E17DEA9D3263C055|
|139|-|A38D0B769B89F6C6|
|140|-|2DAF4F0F6FF541AC|
|141|-|6F5FAEE4C61F773F|
|142|-|A84E8CD83C212C8A|
|143|-|EABE6D3395CB1A19|
|144|-|90C79D3FEDD3F122|
|145|-|D2377CD44439C7B1|
|146|-|15265EE8BE079C04|
|147|-|57D6BF0317EDAA97|
|148|-|D9F4FB7AE3911DFD|
|149|-|9B041A914A7B2B6E|
|150|-|5C1538ADB04570DB|
|151|-|1EE5D94619AF4648|
|152|-|02A151B5F156289C|
|153|-|4051B05E58BC1E0F|
|154|-|87409262A28245BA|
|155|-|C5B073890B687329|
|156|-|4B9237F0FF14C443|
|157|-|0962D61B56FEF2D0|
|158|-|CE73F427ACC0A965|
|159|-|8C8315CC052A9FF6|
|160|-|3A80143F5CF17F13|
|161|-|7870F5D4F51B4980|
|162|-|BF61D7E80F251235|
|163|-|FD913603A6CF24A6|
|164|-|73B3727A52B393CC|
|165|-|31439391FB59A55F|
|166|-|F652B1AD0167FEEA|
|167|-|B4A25046A88DC879|
|168|-|A8E6D8B54074A6AD|
|169|-|EA16395EE99E903E|
|170|-|2D071B6213A0CB8B|
|171|-|6FF7FA89BA4AFD18|
|172|-|E1D5BEF04E364A72|
|173|-|A3255F1BE7DC7CE1|
|174|-|64347D271DE22754|
|175|-|26C49CCCB40811C7|
|176|-|5CBD6CC0CC10FAFC|
|177|-|1E4D8D2B65FACC6F|
|178|-|D95CAF179FC497DA|
|179|-|9BAC4EFC362EA149|
|180|-|158E0A85C2521623|
|181|-|577EEB6E6BB820B0|
|182|-|906FC95291867B05|
|183|-|D29F28B9386C4D96|
|184|-|CEDBA04AD0952342|
|185|-|8C2B41A1797F15D1|
|186|-|4B3A639D83414E64|
|187|-|09CA82762AAB78F7|
|188|-|87E8C60FDED7CF9D|
|189|-|C51827E4773DF90E|
|190|-|020905D88D03A2BB|
|191|-|40F9E43324E99428|
|192|-|2CFFE7D5975E55E2|
|193|-|6E0F063E3EB46371|
|194|-|A91E2402C48A38C4|
|195|-|EBEEC5E96D600E57|
|196|-|65CC8190991CB93D|
|197|-|273C607B30F68FAE|
|198|-|E02D4247CAC8D41B|
|199|-|A2DDA3AC6322E288|
|200|-|BE992B5F8BDB8C5C|
|201|-|FC69CAB42231BACF|
|202|-|3B78E888D80FE17A|
|203|-|7988096371E5D7E9|
|204|-|F7AA4D1A85996083|
|205|-|B55AACF12C735610|
|206|-|724B8ECDD64D0DA5|
|207|-|30BB6F267FA73B36|
|208|-|4AC29F2A07BFD00D|
|209|-|08327EC1AE55E69E|
|210|-|CF235CFD546BBD2B|
|211|-|8DD3BD16FD818BB8|
|212|-|03F1F96F09FD3CD2|
|213|-|41011884A0170A41|
|214|-|86103AB85A2951F4|
|215|-|C4E0DB53F3C36767|
|216|-|D8A453A01B3A09B3|
|217|-|9A54B24BB2D03F20|
|218|-|5D45907748EE6495|
|219|-|1FB5719CE1045206|
|220|-|919735E51578E56C|
|221|-|D367D40EBC92D3FF|
|222|-|1476F63246AC884A|
|223|-|568617D9EF46BED9|
|224|-|E085162AB69D5E3C|
|225|-|A275F7C11F7768AF|
|226|-|6564D5FDE549331A|
|227|-|279434164CA30589|
|228|-|A9B6706FB8DFB2E3|
|229|-|EB46918411358470|
|230|-|2C57B3B8EB0BDFC5|
|231|-|6EA7525342E1E956|
|232|-|72E3DAA0AA188782|
|233|-|30133B4B03F2B111|
|234|-|F7021977F9CCEAA4|
|235|-|B5F2F89C5026DC37|
|236|-|3BD0BCE5A45A6B5D|
|237|-|79205D0E0DB05DCE|
|238|-|BE317F32F78E067B|
|239|-|FCC19ED95E6430E8|
|240|-|86B86ED5267CDBD3|
|241|-|C4488F3E8F96ED40|
|242|-|0359AD0275A8B6F5|
|243|-|41A94CE9DC428066|
|244|-|CF8B0890283E370C|
|245|-|8D7BE97B81D4019F|
|246|-|4A6ACB477BEA5A2A|
|247|-|089A2AACD2006CB9|
|248|-|14DEA25F3AF9026D|
|249|-|562E43B4931334FE|
|250|-|913F6188692D6F4B|
|251|-|D3CF8063C0C759D8|
|252|-|5DEDC41A34BBEEB2|
|253|-|1F1D25F19D51D821|
|254|-|D80C07CD676F8394|
|255|-|9AFCE626CE85B507|


    Using lookup-tables, as presented above, is the key to fast CRC Calculation.  The “LookupTableCrc” method contained in Lookup-Table-CRC-8.c is easy on the eyes, and relies entirely on array indexing and single-instruction “XOR”s.  The only distinction between modulo-2-binary-long-division and CRC-table-lookup, is that a Byte-worth of extra zeros is pulled into the calculation per table-lookup.  Extra zeros were shown to have no effect on the final result in the Modulo-2 XOR Mathematics Section.  Notice how the lookup-table program arrives at the same “CRC-Digest”s:

Output Of Lookup-Table-CRC-8.c
---------------------------------------------------------------------------------

Behold the |3| Byte DataMessage - |11001010|00101101|10100110|

Behold TheDigest-|90|-|01011010|

---------------------------------------------------------------------------------

Append "W" zeros to the DataMessage - |11001010|00101101|10100110|00000000|

Behold TheDigest-|153|-|10011001|

---------------------------------------------------------------------------------

"TheDigest" of this DataMessage should be zero - |11001010|00101101|10100110|10011001|

Behold TheDigest-|0|-|00000000|

---------------------------------------------------------------------------------

Step 5 - Creating Plausible False-Positive “DataMessage”s:

    In order to generate a “FalsePositiveDataMessage” with minimal bit-alterations, one must first understand the mathematics that govern “CRC-Digest” calculation.  Binary polynomial coefficient multiplication is demonstrated in the hand calculation below, and as with modulo-2 “XOR” division, “1”-bit-parity determines each power-column result.  When “Poly” is multiplied by the “CalculatedQuotient”, followed by “XOR”ing the “CORRECT_CRC_DIGEST” to the end of the product, what do we get?  We get the original “DataMessage”.

Authentic Modulo-2 Polynomial Multiplication Example

    The calculation presented above may seem quite harmless to the casual observer, but upon closer inspection, it proves that “CRC-8” will not allow for “Quotient”-driven product-alterations confined to“W” bits.  This conclusion is reached, because the calculation above will yield every possible “FalsePositiveDataMessage” by altering the “Quotient”, and due to the “XOR” row offsets, altered bits in “TheProduct” will span at least “W + 1” bits.  This seemingly inane proof will lead to the important fact:

Every value in the “CRC-8” Lookup-Table is unique:

    Imagine that the numbers contained in the lookup-table are simply the remainders calculated when the corresponding index value “B” has “W” zeros tacked onto the end of it like this:  ( b7b6b5b4b3b2b1b000000000 ).  Now, since only “W” bits are subject to alteration, the remainder calculated using “CRC-8” will always be unique.  As a result, the CRC-8 lookup-table, presented in Step 4, appears to be a randomly shuffled, perfect and complete, “1-To-1 Function”.


The Straightforward False-Positive Generator Method:


The False-Positive Probability:

(Number of Valid “Remainder”s) = (Number of Valid “Poly”s) = 2W

First Run Of Clear-CRC-8-False-Positive.c [4 Error Bits]

Poly = |11010101|
CalculatedQuotient =|10110100|00001100|
TheProduct = |11001010|00101101|11111100|
End Event #1
CRC-Digest of TheProduct = |0| - |00000000|
(TheProduct XOR CORRECT_CRC_DIGEST) = DataMessage =|11001010|00101101|10100110|
End Event #1
The CRC-Digest of the original DataMessage = |90| - |01011010|


Poly = |11010101|
ModifiedQuotient = |10110100|00001001|
TheProduct = |11001010|00101011|01111101|
End Event #2
CRC-Digest of TheProduct = |0| - |00000000|
(TheProduct XOR CORRECT_CRC_DIGEST) = FalsePositiveDataMessage =|11001010|00101011|00100111|
End Event #2
The CRC-Digest of FalsePositiveDataMessage = |90| - |01011010|


Second Run Of Clear-CRC-8-False-Positive.c [10 Error Bits]

Poly = |11010101|
CalculatedQuotient =|10110100|00001100|
TheProduct = |11001010|00101101|11111100|
End Event #1
CRC-Digest of TheProduct = |0| - |00000000|
(TheProduct XOR CORRECT_CRC_DIGEST) = DataMessage =|11001010|00101101|10100110|
End Event #1
The CRC-Digest of the original DataMessage = |90| - |01011010|


Poly = |11010101|
ModifiedQuotient = |11001011|11110011|
TheProduct = |10010011|10101101|01001111|
End Event #2
CRC-Digest of TheProduct = |0| - |00000000|
(TheProduct XOR CORRECT_CRC_DIGEST) = FalsePositiveDataMessage =|10010011|10101101|00010101|
End Event #2
The CRC-Digest of FalsePositiveDataMessage = |90| - |01011010|



C Implementation

    In the spirit of full disclosure, untampered with versions of the C-Programs and the data-files required to run them are available below.  Any program using 64-bit unsigned long integers needs to be compiled and run with a 64-bit operating system and a 64-bit CPU.  These programs were tested with Ubuntu's GCC compiler.  Of course, to run the program, simply execute the command:  ./a.out

    When in Linux, put the ".c" files in your home folder and run this command:  gcc -O3 Clear-CRC-8.c


    * -O3:  Level 3 optimization typically adds a major performance boost.

Clear-CRC-8.c - Basic Bitwise Modulo-2 Long-Division
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define BYTE_WIDTH 8
#define REMAINDER_WIDTH 8
#define MESSAGE_LENGTH 3

// Define a boolean type as an enumeration.
typedef enum { FALSE = 0, TRUE = 1 } Bool;

const unsigned char PowersOfTwo[REMAINDER_WIDTH] = {1, 2, 4, 8, 16, 32, 64, 128};

// This truncated "Divisor", when displayed in binary, looks like this (11010101).
const unsigned char Poly = 213;

// This function performs the clearest type of modulo-2 bitwise long-division on "NumberOfBytes" Bytes, starting at "DataMessage".
// The divisor used is defined in the constant "Poly".
// The value returned by the function is the "FinalRemainder", or CRC-Digest.
unsigned char ClearCrc(const unsigned char *DataMessage, unsigned int NumberOfBytes){
  unsigned int X;
  unsigned char CurrentRemainder = 0;
  unsigned int NextMessageBit;
  unsigned int NextMessageByte;
  
  // Load the first Byte of "DataMessage" into the "CurrentRemainder".
  memcpy(&CurrentRemainder, DataMessage, sizeof(unsigned char));
  NextMessageByte = sizeof(unsigned char);
  NextMessageBit = (BYTE_WIDTH - 1);
  
  // This loop eliminates "1"s in the "MSB" position of "CurrentRemainder" using bit-shifting and the "XOR" operation with "Poly".
  while ( TRUE ) {
    // This loop left-shifts "0"s out of the "CurrentRemainder".
    // The process continues until a "1" is found, or the final message bit is pulled in from the right-hand-side.
    while ( !(CurrentRemainder & PowersOfTwo[REMAINDER_WIDTH - 1]) ) {
      CurrentRemainder <<= 1;
      CurrentRemainder += (DataMessage[NextMessageByte] & PowersOfTwo[NextMessageBit])? 1: 0;
      // Increment the "NextMessageByte" when we have just pulled bit zero into the "CurrentRemainder".
      // Exit when there are no more bytes left to process.
      if ( !NextMessageBit ) {
        NextMessageByte +=1;
        // End Event #1.
        if ( NextMessageByte == NumberOfBytes ) {
          printf("End Event #1\n");
          return CurrentRemainder;
        }
        NextMessageBit = (BYTE_WIDTH - 1);
      }
      else NextMessageBit -= 1;
    }
    CurrentRemainder <<= 1;
    CurrentRemainder += (DataMessage[NextMessageByte] & PowersOfTwo[NextMessageBit])? 1: 0;
    // The pivotal "XOR" operation.
    CurrentRemainder ^= Poly;
    if ( !NextMessageBit ) {
      NextMessageByte +=1;
      // End Event #2
      if ( NextMessageByte == NumberOfBytes ) {
        printf("End Event #2\n");
        return CurrentRemainder;
      }
      NextMessageBit = (BYTE_WIDTH - 1);
    }
    else NextMessageBit -= 1;
  }
  
}

// Simply print out "ThisByte" using "1"s and "0"s.
void PrintByteInBinary(unsigned char ThisByte){
  unsigned int X;
  char HoldOut[BYTE_WIDTH + 1];
  for ( X = 0; X < BYTE_WIDTH; X++ ) HoldOut[X] = (ThisByte & PowersOfTwo[BYTE_WIDTH - 1 - X])? '1': '0';
  HoldOut[BYTE_WIDTH] = '\0';
  printf("%s", HoldOut);
}

int main(){
  unsigned int X;
  // Include an extra Byte in the message to test the trailing-zeros CRC property.
  unsigned char DemonstrationMessage[MESSAGE_LENGTH + 1] = {202, 45, 166, 0};
  unsigned char TheDigest;
  
  printf("\n---------------------------------------------------------------------------------\n");
  
  printf("\nBehold the |%d| Byte DataMessage - |", MESSAGE_LENGTH);
  for ( X = 0; X < MESSAGE_LENGTH; X++ ) {
    PrintByteInBinary(DemonstrationMessage[X]);
    printf("|");
  }
  printf("\n\n");
  
  TheDigest = ClearCrc(DemonstrationMessage, MESSAGE_LENGTH*sizeof(unsigned char));
  printf("Behold TheDigest-|%d|-|", TheDigest);
  PrintByteInBinary(TheDigest);
  printf("|\n");
  
  printf("\n---------------------------------------------------------------------------------\n");
  
  // Calculate "TheDigest" with appended zeros, and then replace the trailing zeros with this number.
  // Recalculate "TheDigest", and this time the digest should compute to zero.
  
  printf("\nAppend \"W\" zeros to the DataMessage - |");
  for ( X = 0; X < (MESSAGE_LENGTH + 1); X++ ) {
    PrintByteInBinary(DemonstrationMessage[X]);
    printf("|");
  }
  printf("\n\n");
  
  TheDigest = ClearCrc(DemonstrationMessage, MESSAGE_LENGTH*sizeof(unsigned char) + 1);
  printf("Behold TheDigest-|%d|-|", TheDigest);
  PrintByteInBinary(TheDigest);
  printf("|\n");
  
  printf("\n---------------------------------------------------------------------------------\n");
  
  DemonstrationMessage[MESSAGE_LENGTH] = TheDigest;
  printf("\n\"TheDigest\" of this DataMessage should be zero - |");
  for ( X = 0; X < (MESSAGE_LENGTH + 1); X++ ) {
    PrintByteInBinary(DemonstrationMessage[X]);
    printf("|");
  }
  printf("\n\n");
  
  TheDigest = ClearCrc(DemonstrationMessage, MESSAGE_LENGTH*sizeof(unsigned char) + 1);
  printf("Behold TheDigest-|%d|-|", TheDigest);
  PrintByteInBinary(TheDigest);
  printf("|\n");
  
  printf("\n---------------------------------------------------------------------------------\n");
  printf("\n");
  
  return 0;
}


Compile-CRC-8-Lookup-Table.c - Create A 256-Byte CRC Lookup-Table Data File
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define BYTE_WIDTH 8
#define TWO_UP_EIGHT 256

// Store the computed table values in a data file to be used in the Bytewise CRC calculation program.
#define OUTPUT_FILE "CRC-8.dat"

const unsigned char Poly = 213;
const unsigned char MSB = 128;
const unsigned char PowersOfTwo[BYTE_WIDTH] = { 1, 2, 4, 8, 16, 32, 64, 128 };

// Feed this function "TableIndex" and it will return the corresponding Lookup-Value for CRC-8.
unsigned char GenerateLookupTableValue(unsigned char TableIndex){
  unsigned int X;
  unsigned char TheRegister = TableIndex;
  // Shift a Byte worth of zeros into the register, and when a "1" is shifted out, perform the required "XOR" operation with "Poly".
  for ( X = BYTE_WIDTH; X; X-- ) {
    if ( MSB & TheRegister ) TheRegister = (TheRegister << 1) ^ Poly;
    else TheRegister <<= 1;
  }
  return TheRegister;
}

// Simply print out "ThisByte" using "1"s and "0"s.
void PrintByteInBinary(unsigned char ThisByte){
  unsigned int X;
  char HoldOut[BYTE_WIDTH + 1];
  for ( X = 0; X < BYTE_WIDTH; X++ ) HoldOut[X] = (ThisByte & PowersOfTwo[BYTE_WIDTH - 1 - X])? '1': '0';
  HoldOut[BYTE_WIDTH] = '\0';
  printf("%s", HoldOut);
}

int main(){
  int X;
  int Y;
  unsigned char CalculatedValues[TWO_UP_EIGHT];
  FILE* DataOut;
  DataOut = fopen(OUTPUT_FILE, "wb");
  for ( X = 0; X < TWO_UP_EIGHT; X++ ) {
    CalculatedValues[X] = GenerateLookupTableValue((unsigned char)X);
    printf("|%3u| - Value-|%2X| - Binary|", X, CalculatedValues[X]);
    PrintByteInBinary(CalculatedValues[X]);
    printf("|\n");
  }
  
  // Verify that each value in the lookup table is unique.
  // Each value can be the seen as the remainder when a 2-Byte message is divided by "Poly".
  // The second Byte is always "W" zeros, so only the first byte changes, making it impossible for two remainders to be the same.
  for ( X = 1; X < TWO_UP_EIGHT; X++ ) {
    for ( Y = (X - 1); Y >= 0; Y-- ) {
      if ( CalculatedValues[X] == CalculatedValues[Y] ) printf("Duplicate values found at |%d|, and |%d|\n", X, Y);
    }
  }
  printf("The search for duplicate values in the table is complete.\n");
  
  fwrite(CalculatedValues, sizeof(unsigned char), TWO_UP_EIGHT, DataOut);
  fclose(DataOut);
  return 0;
}


Lookup-Table-CRC-8.c - Optimized Lookup-Table CRC-Calculation
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define BYTE_WIDTH 8
#define REMAINDER_WIDTH 8
#define MESSAGE_LENGTH 3
#define LOOKUP_TABLE_DATA "CRC-8.dat"
#define TWO_UP_EIGHT 256

// Define a boolean type as an enumeration.
typedef enum { FALSE = 0, TRUE = 1 } Bool;

const unsigned char PowersOfTwo[REMAINDER_WIDTH] = {1, 2, 4, 8, 16, 32, 64, 128};

// This truncated "Divisor", when displayed in binary, looks like this (11010101).
const unsigned char Poly = 213;

// This function performs a Byte-wise "LookupTable" CRC calculation on "NumberOfBytes" Bytes, starting at "DataMessage".
// The divisor used is defined in the constant "Poly".
// The value returned by the function is the "CRC-Digest".
unsigned char LookupTableCrc(const unsigned char *DataMessage, unsigned int NumberOfBytes, const unsigned char *LookupTable){
  int X;
  // Because looking up "0" in the table returns "0", it is safe to use a table lookup to fill the "WorkingRegister" with its initial "DataMessage" value.
  register unsigned char WorkingRegister = 0;
  // Query the "LookupTable" exactly "NumberOfBytes" times.  Perform lookups using the value inside of "WorkingRegister" as the index.
  // After each table query, "XOR" the value returned by "LookupTable" with the next most significant Byte in "DataMessage".
  // "X" is the location of the next data Byte to pull into the calculation.
  for ( X = 0; X < NumberOfBytes; X++ ) WorkingRegister = LookupTable[WorkingRegister] ^ DataMessage[X];
  return WorkingRegister;
}

// Simply print out "ThisByte" using "1"s and "0"s.
void PrintByteInBinary(unsigned char ThisByte){
  unsigned int X;
  char HoldOut[BYTE_WIDTH + 1];
  for ( X = 0; X < BYTE_WIDTH; X++ ) HoldOut[X] = (ThisByte & PowersOfTwo[BYTE_WIDTH - 1 - X])? '1': '0';
  HoldOut[BYTE_WIDTH] = '\0';
  printf("%s", HoldOut);
}

int main(){
  unsigned int X;
  // Include an extra Byte in the message to test the trailing-zeros CRC property.
  unsigned char DemonstrationMessage[MESSAGE_LENGTH + 1] = {202, 45, 166, 0};
  unsigned char TheDigest;
  unsigned char *TheLookupTable = (unsigned char*)malloc(TWO_UP_EIGHT*sizeof(unsigned char));
  FILE *TableFile;
  
  // Read the precompiled lookup-table from "CRC-8.dat" directly into "TheLookupTable".
  TableFile = fopen(LOOKUP_TABLE_DATA, "rb");
  fread(TheLookupTable, sizeof(unsigned char), TWO_UP_EIGHT, TableFile);
  fclose(TableFile);
  
  printf("\n---------------------------------------------------------------------------------\n");
  
  printf("\nBehold the |%d| Byte DataMessage - |", MESSAGE_LENGTH);
  for ( X = 0; X < MESSAGE_LENGTH; X++ ) {
    PrintByteInBinary(DemonstrationMessage[X]);
    printf("|");
  }
  printf("\n\n");
  
  TheDigest = LookupTableCrc(DemonstrationMessage, MESSAGE_LENGTH*sizeof(unsigned char), TheLookupTable);
  printf("Behold TheDigest-|%d|-|", TheDigest);
  PrintByteInBinary(TheDigest);
  printf("|\n");
  
  printf("\n---------------------------------------------------------------------------------\n");
  
  // Calculate "TheDigest" with appended zeros, and then replace the trailing zeros with this number.
  // Recalculate "TheDigest", and this time the digest should compute to zero.
  
  printf("\nAppend \"W\" zeros to the DataMessage - |");
  for ( X = 0; X < (MESSAGE_LENGTH + 1); X++ ) {
    PrintByteInBinary(DemonstrationMessage[X]);
    printf("|");
  }
  printf("\n\n");
  
  TheDigest = LookupTableCrc(DemonstrationMessage, MESSAGE_LENGTH*sizeof(unsigned char) + 1, TheLookupTable);
  printf("Behold TheDigest-|%d|-|", TheDigest);
  PrintByteInBinary(TheDigest);
  printf("|\n");
  
  printf("\n---------------------------------------------------------------------------------\n");
  
  DemonstrationMessage[MESSAGE_LENGTH] = TheDigest;
  printf("\n\"TheDigest\" of this DataMessage should be zero - |");
  for ( X = 0; X < (MESSAGE_LENGTH + 1); X++ ) {
    PrintByteInBinary(DemonstrationMessage[X]);
    printf("|");
  }
  printf("\n\n");
  
  TheDigest = LookupTableCrc(DemonstrationMessage, MESSAGE_LENGTH*sizeof(unsigned char) + 1, TheLookupTable);
  printf("Behold TheDigest-|%d|-|", TheDigest);
  PrintByteInBinary(TheDigest);
  printf("|\n");
  
  printf("\n---------------------------------------------------------------------------------\n");
  printf("\n");
  
  return 0;
}


Compile-CRC-64-Lookup-Table.c - Create A 2048-Byte CRC Lookup-Table Data File
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define BYTE_WIDTH 8
#define POLY_WIDTH 64
#define TWO_UP_EIGHT 256

// Store the computed table values in a data file to be used in the Bytewise CRC calculation program.
#define OUTPUT_FILE "CRC-64.dat"

// "Poly" is the binary representation of the CRC-64 polynomial listed below.
// x64 + x62 + x57 + x55 + x54 + x53 + x52 + x47 + x46 + x45 + x40 + x39 + x38 + x37 + x35 + x33 + x32 + x31 + x29 + x27 + x24 + x23 + x22 + x21 + x19 + x17 + x13 + x12 + x10 + x9 + x7 + x4 + x + 1
const unsigned long int Poly = 4823603603198064275;
const unsigned long int MSB = 9223372036854775808;
const unsigned long int PowersOfTwo[POLY_WIDTH] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152,
 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472,
 274877906944, 549755813888, 1099511627776, 2199023255552, 4398046511104, 8796093022208, 17592186044416, 35184372088832, 70368744177664, 140737488355328, 281474976710656,
 562949953421312, 1125899906842624, 2251799813685248, 4503599627370496, 9007199254740992, 18014398509481984, 36028797018963968, 72057594037927936, 144115188075855872,
 288230376151711744, 576460752303423488, 1152921504606846976, 2305843009213693952, 4611686018427387904, 9223372036854775808};

// Simply print out "ThisLong" using "1"s and "0"s.
void PrintUnsignedLongInBinary(unsigned long int ThisLong){
  unsigned int X;
  char HoldOut[POLY_WIDTH + 1];
  for ( X = 0; X < POLY_WIDTH; X++ ) HoldOut[X] = (ThisLong & PowersOfTwo[POLY_WIDTH - 1 - X])? '1': '0';
  HoldOut[POLY_WIDTH] = '\0';
  printf("%s", HoldOut);
}

// Feed this function "TableIndex" and it will return the corresponding Lookup-Value for CRC-64.
unsigned long int GenerateLookupTableValue(unsigned long int TableIndex){
  unsigned int X;
  unsigned long int TheRegister = TableIndex<<56;
  // Shift a Byte worth of zeros into the register, and when a "1" is shifted out, perform the required "XOR" operation with "Poly".
  for ( X = BYTE_WIDTH; X; X-- ) {
    if ( TheRegister & MSB ) TheRegister = (TheRegister << 1) ^ Poly;
    else TheRegister <<= 1;
  }
  return TheRegister;
}

int main(){
  unsigned long int X;
  int Y;
  unsigned long int CalculatedValues[TWO_UP_EIGHT];
  FILE* DataOut;
  DataOut = fopen(OUTPUT_FILE, "wb");
  for ( X = 0; X < TWO_UP_EIGHT; X++ ) {
    CalculatedValues[X] = GenerateLookupTableValue(X);
    printf("|%3lu| - Value-|%16lX| - Binary|", X, CalculatedValues[X]);
    PrintUnsignedLongInBinary(CalculatedValues[X]);
    printf("|\n");
  }
  
  // Verify that each value in the lookup table is unique.
  // Each value can be the seen as the remainder when a 9-Byte message is divided by "Poly".
  // The second-to-ninth Bytes are always "W" zeros, so only the first byte changes, making it impossible for two remainders to be the same.
  for ( X = 1; X < TWO_UP_EIGHT; X++ ) {
    for ( Y = (X - 1); Y >= 0; Y-- ) {
      if ( CalculatedValues[X] == CalculatedValues[Y] ) printf("Duplicate values found at |%lu|, and |%d|\n", X, Y);
    }
  }
  printf("The search for duplicate values in the table is complete.\n");
  
  fwrite(CalculatedValues, sizeof(unsigned long int), TWO_UP_EIGHT, DataOut);
  fclose(DataOut);
  return 0;
}


crc.c - Calculate 64-Bit CRC-Digests For Compressed 17x17 4-Colourings
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

// CRC Constants.
#define BYTE_WIDTH 8
#define POLY_WIDTH 64
#define TWO_UP_EIGHT 256
#define LEFT_BYTE_SHIFT 56
#define W_BYTES 8

// The pre-compiled CRC-64 lookup-table is stored in this file.
#define LOOKUP_TABLE_FILE "CRC-64.dat"

// 17x17 4-Colouring Constants.
#define POSITION_COUNT 289
#define CHAR_COUNT 73
#define COLOURS 4
#define POSITIONS_PER_NODE 4

// These values are used to decode unsigned long ints into binary format for output.
const unsigned long int PowersOfTwo[POLY_WIDTH] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304,
 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944,
 549755813888, 1099511627776, 2199023255552, 4398046511104, 8796093022208, 17592186044416, 35184372088832, 70368744177664, 140737488355328, 281474976710656, 562949953421312, 1125899906842624,
 2251799813685248, 4503599627370496, 9007199254740992, 18014398509481984, 36028797018963968, 72057594037927936, 144115188075855872, 288230376151711744, 576460752303423488, 1152921504606846976,
 2305843009213693952, 4611686018427387904, 9223372036854775808};

// This value is integrated into "CrcLookupTable", but it will not be needed explicitly.
const unsigned long int Poly = 4823603603198064275;

// The CRC-64 lookup-table will have global scope.
unsigned long int CrcLookupTable[TWO_UP_EIGHT];

const unsigned int Modulus[POSITIONS_PER_NODE + 1] = { 0, 1, 2, 3, 0 };

const char TheColours[COLOURS] = { '0', '1', '2', '3' };

const unsigned int PositionShift[POSITIONS_PER_NODE] = { 6, 4, 2, 0 };

// This function uses "NumberOfBytes" Bytes starting at "DataMessage" to compute the CRC-Digest, by way of a Byte-wise "CrcLookupTable" based on the CRC-64 "Poly".
unsigned long int LookupTableColouringCrc(const unsigned char *DataMessage, unsigned long int NumberOfBytes){
  int X;
  // Because looking up a "0" in the table returns "0", it is safe to use table-lookups for filling the "WorkingRegister" with its initial "DataMessage" values.
  register unsigned long int WorkingRegister = 0;
  // Query the "CrcLookupTable" exactly "NumberOfBytes" times.  Perform lookups using the leftmost Byte of "WorkingRegister" as the index.
  // After each table query, "XOR" the value returned by "CrcLookupTable" with the value inside "WorkingRegister" as soon as the next "DataMessage" Byte has been drawn in from the right-hand-side.
  // "X" represents the location of the next "DataMessage" Byte to pull into the calculation.
  for ( X = 0; X < NumberOfBytes; X++ ) WorkingRegister = CrcLookupTable[WorkingRegister >> LEFT_BYTE_SHIFT] ^ ((WorkingRegister << BYTE_WIDTH) ^ DataMessage[X]);
  return WorkingRegister;
}

// Read the "POSITION_COUNT" printable characters from "ThisImport" Colouring, and compress them into the "CHAR_COUNT" characters of "ThisColouringString".  Compression has a factor of 4.
void ImportMasterColouringSeedString(unsigned char *ThisColouringString, const char *ThisImport){
  unsigned int X;
  unsigned int CurrentPosition = 3;
  // Zero the destination Bytes.
  memset(ThisColouringString, 0, sizeof(unsigned char)*CHAR_COUNT);
  // Place the colour at position "X" of "ThisImport", into the correct two-bit slot within "ThisColouringString". Position shifting and modulus lookup-tables are used to speed this up.
  for ( X = 0; X < POSITION_COUNT; X++ ) ThisColouringString[X >> 2] += ((ThisImport[X] - TheColours[0]) << PositionShift[CurrentPosition = Modulus[CurrentPosition + 1]]);
}

// Simply print out "ThisLong" using "1"s and "0"s.
void PrintUnsignedLongInBinary(unsigned long int ThisLong){
  unsigned int X;
  char HoldOut[POLY_WIDTH + 1];
  for ( X = 0; X < POLY_WIDTH; X++ ) HoldOut[X] = (ThisLong & PowersOfTwo[POLY_WIDTH - 1 - X])? '1': '0';
  HoldOut[POLY_WIDTH] = '\0';
  printf("%s", HoldOut);
}

// Simply print out "ThisByte" using "1"s and "0"s.
void PrintByteInBinary(unsigned char ThisByte){
  unsigned int X;
  char HoldOut[BYTE_WIDTH + 1];
  for ( X = 0; X < BYTE_WIDTH; X++ ) HoldOut[X] = (ThisByte & PowersOfTwo[BYTE_WIDTH - 1 - X])? '1': '0';
  HoldOut[BYTE_WIDTH] = '\0';
  printf("%s", HoldOut);
}

int main(){
  int X;
  unsigned char *CompactString = (unsigned char*)calloc(CHAR_COUNT + W_BYTES, sizeof(unsigned char));
  unsigned char *TheFinalW = CompactString + CHAR_COUNT;
  unsigned long int TheDigest;
  
  // These 289-character strings are all different, but it is extremely tedious to find the differences, just by looking at them.  Hence we use CRC-64 to help us out.
  char *FirstImport =
  "11302023023013131"
  "20301312322310210"
  "23123320133011020"
  "32211100023332301"
  "00231221230301103"
  "03022131011312230"
  "20232030313120111"
  "31333021100223210"
  "01103201302122333"
  "22013233101030102"
  "33200110302101222"
  "01220012331233001"
  "12001332110123023"
  "30131322001132032"
  "10020303221021312"
  "32112103232200013"
  "13310211020230323\0";
  
  char *SecondImport =
  "11302023023013131"
  "20301312322310210"
  "23123320133011020"
  "32211100023332301"
  "00231221230301103"
  "03022131011312230"
  "20232030313120111"
  "31333001100223210"
  "01103201302122333"
  "22013233101030102"
  "33200110302101222"
  "01220012331233001"
  "12001332110123023"
  "30131322001232032"
  "10020303221021312"
  "32112103232200013"
  "13310211020230323\0";
  
  char *ThirdImport =
  "11302023023013131"
  "20301312322310210"
  "23123320133011020"
  "32211100023332301"
  "00231221230301103"
  "03022131011312230"
  "20232030313120111"
  "31333021100223210"
  "01103201302122333"
  "22013233101030102"
  "33200110302101222"
  "01220012331233001"
  "12001332110123023"
  "10131322001232032"
  "10020303221021312"
  "32112103232200013"
  "13310211020230323\0";
  
  FILE *LookupTableData;
  LookupTableData = fopen(LOOKUP_TABLE_FILE, "rb");
  fread(CrcLookupTable, sizeof(unsigned long int), TWO_UP_EIGHT, LookupTableData);
  fclose(LookupTableData);
  
  // Process the "FirstImport".
  printf("\n---------------------------------------------------------------------------------\n\n");
  
  ImportMasterColouringSeedString(CompactString, FirstImport);
  TheDigest = LookupTableColouringCrc(CompactString, CHAR_COUNT);
  printf("TheDigest for FirstImport over CHAR_COUNT Bytes -|%lu|\n", TheDigest);
  
  TheDigest = LookupTableColouringCrc(CompactString, CHAR_COUNT + W_BYTES);
  printf("TheDigest for FirstImport plus W zero bits -|%lu|\n", TheDigest);
  
  // Copy the (CRC-Digest with W extra zeros) into the extra positions in "CompactString".
  // It turns out that this is a rather tedious operation, because "unsigned long int"s are stored in "Little Endian Byte Order" in the X86-X64 architecture.
  // The statement below amounts to reversing the Byte order while copying, so that the most significant Bytes get processed first.
  for ( X = 0; X < W_BYTES; X++ ) *(TheFinalW + X) = ((unsigned char *)&TheDigest)[W_BYTES - X - 1];
  
  // Verify the the copied Bytes have arrived in the correct order.
  printf("From TheDigest    |");
  PrintUnsignedLongInBinary(TheDigest);
  printf("|\n");
  
  printf("From CompactString|");
  for( X = 0; X < W_BYTES; X++ ) {
    PrintByteInBinary(CompactString[CHAR_COUNT + X]);
    printf("|");
  }
  printf("\n");
  
  TheDigest = LookupTableColouringCrc(CompactString, CHAR_COUNT + W_BYTES);
  printf("TheDigest for FirstImport with previous digest appended -|%lu|\n", TheDigest);
  
  // Process the "SecondImport".
  printf("\n---------------------------------------------------------------------------------\n\n");
  
  ImportMasterColouringSeedString(CompactString, SecondImport);
  TheDigest = LookupTableColouringCrc(CompactString, CHAR_COUNT);
  printf("TheDigest for SecondImport over CHAR_COUNT Bytes -|%lu|\n", TheDigest);
  
  memset(CompactString + CHAR_COUNT, 0, W_BYTES);
  TheDigest = LookupTableColouringCrc(CompactString, CHAR_COUNT + W_BYTES);
  printf("TheDigest for SecondImport plus W zero bits -|%lu|\n", TheDigest);
  
  // Copy the (CRC-Digest with W extra zeros) into the extra positions in "CompactString".
  // It turns out that this is a rather tedious operation, because "unsigned long int"s are stored in "Little Endian Byte Order" in the X86-X64 architecture.
  // The statement below amounts to reversing the Byte order while copying, so that the most significant Bytes get processed first.
  for ( X = 0; X < W_BYTES; X++ ) *(TheFinalW + X) = ((unsigned char *)&TheDigest)[W_BYTES - X - 1];
  
  // Verify the the copied Bytes have arrived in the correct order.
  printf("From TheDigest    |");
  PrintUnsignedLongInBinary(TheDigest);
  printf("|\n");
  
  printf("From CompactString|");
  for( X = 0; X < W_BYTES; X++ ) {
    PrintByteInBinary(CompactString[CHAR_COUNT + X]);
    printf("|");
  }
  printf("\n");
  
  TheDigest = LookupTableColouringCrc(CompactString, CHAR_COUNT + W_BYTES);
  printf("TheDigest for SecondImport with previous digest appended -|%lu|\n", TheDigest);
  
  // Process the "ThirdImport".
  printf("\n---------------------------------------------------------------------------------\n\n");
  
  ImportMasterColouringSeedString(CompactString, ThirdImport);
  TheDigest = LookupTableColouringCrc(CompactString, CHAR_COUNT);
  printf("TheDigest for ThirdImport over CHAR_COUNT Bytes -|%lu|\n", TheDigest);
  
  memset(CompactString + CHAR_COUNT, 0, W_BYTES);
  TheDigest = LookupTableColouringCrc(CompactString, CHAR_COUNT + W_BYTES);
  printf("TheDigest for ThirdImport plus W zero bits -|%lu|\n", TheDigest);
  
  // Copy the (CRC-Digest with W extra zeros) into the extra positions in "CompactString".
  // It turns out that this is a rather tedious operation, because "unsigned long int"s are stored in "Little Endian Byte Order" in the X86-X64 architecture.
  // The statement below amounts to reversing the Byte order while copying, so that the most significant Bytes get processed first.
  for ( X = 0; X < W_BYTES; X++ ) *(TheFinalW + X) = ((unsigned char *)&TheDigest)[W_BYTES - X - 1];
  
  // Verify the the copied Bytes have arrived in the correct order.
  printf("From TheDigest    |");
  PrintUnsignedLongInBinary(TheDigest);
  printf("|\n");
  
  printf("From CompactString|");
  for( X = 0; X < W_BYTES; X++ ) {
    PrintByteInBinary(CompactString[CHAR_COUNT + X]);
    printf("|");
  }
  printf("\n");
  
  TheDigest = LookupTableColouringCrc(CompactString, CHAR_COUNT + W_BYTES);
  printf("TheDigest for ThirdImport with previous digest appended -|%lu|\n", TheDigest);
  
  printf("\n---------------------------------------------------------------------------------\n\n");
  
  return 0;
}


Clear-CRC-8-False-Positive.c - Generate Plausible-False-Positive Demonstration
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define BYTE_WIDTH 8
#define REMAINDER_WIDTH 8
#define MESSAGE_LENGTH 3
#define CORRECT_CRC_DIGEST 90

// Define a boolean type as an enumeration.
typedef enum { FALSE = 0, TRUE = 1 } Bool;

const unsigned char PowersOfTwo[REMAINDER_WIDTH] = {1, 2, 4, 8, 16, 32, 64, 128};

const unsigned char Poly = 213;

// Simply print out "ThisByte" using "1"s and "0"s.
void PrintByteInBinary(unsigned char ThisByte){
  unsigned int X;
  char HoldOut[BYTE_WIDTH + 1];
  for ( X = 0; X < BYTE_WIDTH; X++ ) HoldOut[X] = (ThisByte & PowersOfTwo[BYTE_WIDTH - 1 - X])? '1': '0';
  HoldOut[BYTE_WIDTH] = '\0';
  printf("%s", HoldOut);
}

// This function mod-2-polynomial-multiplies "TheQuotient" by "Poly" and stores the result into "TheProduct", which will be "MessageBytes" long.
void ModTwoPolyProduct(unsigned char *TheQuotient, unsigned char *TheProduct, unsigned int MessageBytes){
  unsigned int X;
  unsigned int Y;
  unsigned int PowerSum;
  // First zero the value of "TheProduct".
  memset(TheProduct, 0, MessageBytes);
  // X Keeps track of the position within "Poly".
  for ( X = 0; X <= BYTE_WIDTH; X++ ) {
    // This condition accounts for the token "1" ahead of "Poly".
    if ( BYTE_WIDTH - X ) if ( !(PowersOfTwo[X] & Poly) ) continue;
    // Y Keeps track of the position within "TheQuotient".
    for ( Y = 0; Y < (BYTE_WIDTH*(MessageBytes - 1)); Y++ ) {
      // If the Y position in "TheQuotient" is "0", then bounce.
      if ( !(TheQuotient[(MessageBytes - 1 - 1) - (Y>>3)] & PowersOfTwo[Y%BYTE_WIDTH]) ) continue;
      PowerSum = X + Y;
      TheProduct[(MessageBytes - 1) - (PowerSum>>3)] ^= PowersOfTwo[PowerSum%BYTE_WIDTH];
    }
  }
}

// This function performs the clearest type of modulo-2 bitwise long-division on "NumberOfBytes" Bytes, starting at "DataMessage".
// The divisor used is defined in the constant "Poly".
// The value returned by the function is the "FinalRemainder", or CRC-Digest.
unsigned char ClearCrc(const unsigned char *DataMessage, unsigned int NumberOfBytes){
  unsigned int X;
  unsigned char CurrentRemainder = 0;
  unsigned int NextMessageBit;
  unsigned int NextMessageByte;
  
  // Load the first Byte of "DataMessage" into the "CurrentRemainder".
  memcpy(&CurrentRemainder, DataMessage, sizeof(unsigned char));
  NextMessageByte = sizeof(unsigned char);
  NextMessageBit = (BYTE_WIDTH - 1);
  
  // This loop eliminates "1"s in the "MSB" position of "CurrentRemainder" using bit-shifting and the "XOR" operation with "Poly".
  while ( TRUE ) {
    // This loop left-shifts "0"s out of the "CurrentRemainder".
    // The process continues until a "1" is found, or the final message bit is pulled in from the right-hand-side.
    while ( !(CurrentRemainder & PowersOfTwo[REMAINDER_WIDTH - 1]) ) {
      CurrentRemainder <<= 1;
      CurrentRemainder += (DataMessage[NextMessageByte] & PowersOfTwo[NextMessageBit])? 1: 0;
      // Increment the "NextMessageByte" when we have just pulled bit zero into the "CurrentRemainder".
      // Exit when there are no more bytes left to process.
      if ( !NextMessageBit ) {
        NextMessageByte +=1;
        // End Event #1.
        if ( NextMessageByte == NumberOfBytes ) {
          printf("End Event #1\n");
          return CurrentRemainder;
        }
        NextMessageBit = (BYTE_WIDTH - 1);
      }
      else NextMessageBit -= 1;
    }
    CurrentRemainder <<= 1;
    CurrentRemainder += (DataMessage[NextMessageByte] & PowersOfTwo[NextMessageBit])? 1: 0;
    // The pivotal "XOR" operation.
    CurrentRemainder ^= Poly;
    if ( !NextMessageBit ) {
      NextMessageByte +=1;
      // End Event #2
      if ( NextMessageByte == NumberOfBytes ) {
        printf("End Event #2\n");
        return CurrentRemainder;
      }
      NextMessageBit = (BYTE_WIDTH - 1);
    }
    else NextMessageBit -= 1;
  }
  
}

int main(){
  unsigned int X;
  unsigned char DataMessage[MESSAGE_LENGTH];
  unsigned char FalsePositiveDataMessage[MESSAGE_LENGTH];
  unsigned char CalculatedQuotient[MESSAGE_LENGTH - 1] = { 180, 12 };
  // In order to keep the "FalsePositiveDataMessage" plausible, the "MSB" of the most significant Byte should be set to "1".
  // Further, changes made to the quotient should minimize the bits altered in the "DataMessage".  This requires knowledge of the "Poly" being used.
  // For CRC-8, a single bit flip in the "Quotient" results in a six-bit alteration of the "DataMessage".
  // It is possible to limits the incorrect bits in "FalsePositiveDataMessage" to four by altering 2 bits in "Quotient", seperated by one unchanged bit.
  // This particular modification of "CalculatedQuotient" results in ten bit-errors.
  unsigned char ModifiedQuotient[MESSAGE_LENGTH - 1] = { 203, 243 };
  unsigned char TheCrcDigest;
  
  // Display the chosen "Poly".
  printf("\nPoly =              |");
  PrintByteInBinary(Poly);
  printf("|\n");
  
  printf("CalculatedQuotient =|");
  for ( X = 0; X < (MESSAGE_LENGTH - 1); X++ ) {
    PrintByteInBinary(CalculatedQuotient[X]);
    printf("|");
  }
  printf("\n");
  
  ModTwoPolyProduct(CalculatedQuotient, DataMessage, MESSAGE_LENGTH);
  printf("TheProduct =        |");
  for ( X = 0; X < MESSAGE_LENGTH; X++ ) {
    PrintByteInBinary(DataMessage[X]);
    printf("|");
  }
  printf("\n");
  
  TheCrcDigest = ClearCrc(DataMessage, MESSAGE_LENGTH);
  
  printf("CRC-Digest of TheProduct = |%u| - |", TheCrcDigest);
  PrintByteInBinary(TheCrcDigest);
  printf("|\n");
  
  // XOR the "CORRECT_CRC_DIGEST" at the end of "DataMessage".
  DataMessage[MESSAGE_LENGTH - 1] ^= CORRECT_CRC_DIGEST;
  
  printf("(TheProduct XOR CORRECT_CRC_DIGEST) = DataMessage =|");
  for ( X = 0; X < MESSAGE_LENGTH; X++ ) {
    PrintByteInBinary(DataMessage[X]);
    printf("|");
  }
  printf("\n");
  
  TheCrcDigest = ClearCrc(DataMessage, MESSAGE_LENGTH);
  
  printf("The CRC-Digest of the original DataMessage = |%u| - |", TheCrcDigest);
  PrintByteInBinary(TheCrcDigest);
  printf("|\n\n");
  
  
  // Display the chosen "Poly".
  printf("\nPoly =              |");
  PrintByteInBinary(Poly);
  printf("|\n");
  
  printf("ModifiedQuotient =  |");
  for ( X = 0; X < (MESSAGE_LENGTH - 1); X++ ) {
    PrintByteInBinary(ModifiedQuotient[X]);
    printf("|");
  }
  printf("\n");
  
  ModTwoPolyProduct(ModifiedQuotient, FalsePositiveDataMessage, MESSAGE_LENGTH);
  printf("TheProduct =        |");
  for ( X = 0; X < MESSAGE_LENGTH; X++ ) {
    PrintByteInBinary(FalsePositiveDataMessage[X]);
    printf("|");
  }
  printf("\n");
  
  TheCrcDigest = ClearCrc(FalsePositiveDataMessage, MESSAGE_LENGTH);
  
  printf("CRC-Digest of TheProduct = |%u| - |", TheCrcDigest);
  PrintByteInBinary(TheCrcDigest);
  printf("|\n");
  
  // XOR the "CORRECT_CRC_DIGEST" at the end of "FalsePositiveDataMessage".
  FalsePositiveDataMessage[MESSAGE_LENGTH - 1] ^= CORRECT_CRC_DIGEST;
  
  printf("(TheProduct XOR CORRECT_CRC_DIGEST) = FalsePositiveDataMessage =|");
  for ( X = 0; X < MESSAGE_LENGTH; X++ ) {
    PrintByteInBinary(FalsePositiveDataMessage[X]);
    printf("|");
  }
  printf("\n");
  
  TheCrcDigest = ClearCrc(FalsePositiveDataMessage, MESSAGE_LENGTH);
  
  printf("The CRC-Digest of FalsePositiveDataMessage = |%u| - |", TheCrcDigest);
  PrintByteInBinary(TheCrcDigest);
  printf("|\n\n");
  
  return 0;
}



Conclusion


    Below, the input, and output of crc.c will be put on display.  Simply glance at the three input 17x17 4-Colourings; They are quite large, and look identical to the naked eye, but when they each produce a unique “CRC-Digest”, you will be looking for the subtle differences, just to make sure.

The Three Input 17x17 4-Colourings:
FirstImport
11302023023013131
20301312322310210
23123320133011020
32211100023332301
00231221230301103
03022131011312230
20232030313120111
31333021100223210
01103201302122333
22013233101030102
33200110302101222
01220012331233001
12001332110123023
30131322001132032
10020303221021312
32112103232200013
13310211020230323
SecondImport
11302023023013131
20301312322310210
23123320133011020
32211100023332301
00231221230301103
03022131011312230
20232030313120111
31333001100223210
01103201302122333
22013233101030102
33200110302101222
01220012331233001
12001332110123023
30131322001232032
10020303221021312
32112103232200013
13310211020230323
ThirdImport
11302023023013131
20301312322310210
23123320133011020
32211100023332301
00231221230301103
03022131011312230
20232030313120111
31333021100223210
01103201302122333
22013233101030102
33200110302101222
01220012331233001
12001332110123023
10131322001232032
10020303221021312
32112103232200013
13310211020230323

Output Of crc.c

---------------------------------------------------------------------------------

TheDigest for FirstImport over CHAR_COUNT Bytes -|2449492796987567755|
TheDigest for FirstImport plus W zero bits -|2693988645103658150|
From TheDigest |0010010101100010111110000110011000111100010101101110010010100110|
From CompactString|00100101|01100010|11111000|01100110|00111100|01010110|11100100|10100110|
TheDigest for FirstImport with previous digest appended -|0|

---------------------------------------------------------------------------------

TheDigest for SecondImport over CHAR_COUNT Bytes -|13695663649870972449|
TheDigest for SecondImport plus W zero bits -|14420216274443853120|
From TheDigest |1100100000011110111001100100110011001110100010000101110101000000|
From CompactString|11001000|00011110|11100110|01001100|11001110|10001000|01011101|01000000|
TheDigest for SecondImport with previous digest appended -|0|

---------------------------------------------------------------------------------

TheDigest for ThirdImport over CHAR_COUNT Bytes -|13202989161120760022|
TheDigest for ThirdImport plus W zero bits -|4279025832619793549|
From TheDigest |0011101101100010001001110101001011010010000001011101110010001101|
From CompactString|00111011|01100010|00100111|01010010|11010010|00000101|11011100|10001101|
TheDigest for ThirdImport with previous digest appended -|0|

---------------------------------------------------------------------------------



Contact Information



Contact: JohnPaul Adamovsky – ( logarithm69@hotmail.com ) - Please feel free to ask me questions.


Phone: (416) 231-7577


This is the mark of my trade...


All The Very Best,

JohnPaul Adamovsky

Hit Counter by Digits



Go Back to the Top |