flat assembler
Message board for the users of flat assembler.

Index > Main > CRC16

Author
Thread Post new topic Reply to topic
zhak



Joined: 12 Apr 2005
Posts: 501
Location: Belarus
zhak 19 Aug 2012, 10:58
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!
Post 19 Aug 2012, 10:58
View user's profile Send private message Reply with quote
revolution
When all else fails, read the source


Joined: 24 Aug 2004
Posts: 19257
Location: In your JS exploiting you and your system
revolution 19 Aug 2012, 15:51
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.
Post 19 Aug 2012, 15:51
View user's profile Send private message Visit poster's website Reply with quote
zhak



Joined: 12 Apr 2005
Posts: 501
Location: Belarus
zhak 19 Aug 2012, 17:58
revolution wrote:
Can we assume you understand how the CRC works?

I hope so Smile

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?
Post 19 Aug 2012, 17:58
View user's profile Send private message Reply with quote
baldr



Joined: 19 Mar 2008
Posts: 1651
baldr 21 Aug 2012, 15:41
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).
Post 21 Aug 2012, 15:41
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2023, Tomasz Grysztar. Also on GitHub, YouTube, Twitter.

Website powered by rwasa.