flat assembler
Message board for the users of flat assembler.

 Index > Main > CRC16
Author
zhak

Joined: 12 Apr 2005
Posts: 501
Location: Belarus
zhak
Hi guys,
I've read a dozen of essays about calculating CRC16 and still cannot figure out step-by-step algoritm how to do the calculation. All resources seem to provide different steps and I'm completely lost. Moreover, different online calculators give me different results for the same input data (given the same algo is used). What is the correct algoritm to calculate CRC16? Please, help.
I want to use CRC16-CCITT with reverse polynom: 0x8408. Not using pre-computed tables. Thanks in advance!
19 Aug 2012, 10:58
revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 18450
revolution
Can we assume you understand how the CRC works?

http://en.wikipedia.org/wiki/Cyclic_redundancy_check

If we don't understand how algorithms work then we can't know where or when our code is failing.
19 Aug 2012, 15:51
zhak

Joined: 12 Apr 2005
Posts: 501
Location: Belarus
zhak
revolution wrote:
Can we assume you understand how the CRC works?

I hope so

Finally, it seems that I managed to build a working CRC-16 algo, which gives me the same results as online calc for CRC-16 (if pre-initialized with 0x0000) and CRC-16 Modbus (if preinitialized with 0xFFFF).

Code:
```crc16:
mov si, data
mov cx, data_length
mov bx, 0
.l1:
lodsw
xor bx, ax
mov dx, 16
.l2:
shr bx, 1
jnc short .l3
xor bx, 0xa001
.l3:
dec dx
jnz short .l2
dec cx
jnz short .l1
```

It is word-aligned since my data message is 512-bytes aligned.

However, I do not completely understand the following:
Quote:

Post-invert
The same sort of error can occur at the end of a message. Appending 0 bits to a message is equivalent to multiplying its polynomial by x, and if it was previously a multiple of the CRC polynomial, the result of that multiplication will be, as well. This is equivalent to the fact that, since 726 is a multiple of 11, so is 7260.
A similar solution can be applied at the end of the message, inverting the CRC register before it is appended to the message. Again, any non-zero change will do; inverting all the bits is simply the most common.
This has an effect on one-pass CRC checking; instead of producing a result of zero when the message is correct, it produces a fixed non-zero result. (To be precise, the result is the non-inverted CRC of the inversion pattern.) This is still straightforward to verify.
(from Wiki)

So, if I calculate CRC for 512 bytes, but I have only 396 bytes of data, and the rest are just zeroes, then I need to invert final CRC value?
19 Aug 2012, 17:58
baldr

Joined: 19 Mar 2008
Posts: 1651
baldr
zhak,

You really should attempt to understand what CRC algorithm calculates, not how.

Those 396 bytes, with 116 zeros appended afterwards, represent 4Ki coefficients for polynomial over GF(2). That polynomial is divided (over GF(2)) by some other polynomial (over GF(2), often carefully chosen ;-).

The gist of your quote is that if N is divisible by M, then N*K is divisible too, and in this case K == x**116.

Post-conditioning (i.e. inversion after calculation) allows chunking: you may calculate CRC for some chunk, then use it as a seed for another CRC calculation (probably for another chunk ;-), provided that two inversions cancel each other.

Pre-conditioning serves two purposes: it's crucial for chunking and it detects leading zeros: 0*x**n+a[n-1]*x**(n-1)+...+a[0] has exactly the same remainder as a[n-1]*x**(n-1)+...+a[0], when divided by anything (cf. 1 and 1.(0), as I don't know proper notation for unsignificant leading zeroes).
21 Aug 2012, 15:41
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainTutorials and ExamplesDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsOS ConstructionIDE DevelopmentProjects and IdeasNon-x86 architecturesHigh Level LanguagesProgramming Language DesignCompiler Internals Other----------------FeedbackHeapTest Area

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou cannot attach files in this forumYou can download files in this forum