crc16

Earl Foster · 2009-04-16 15:25

Has anybody written code for crc16 (crc-ccitt)·and·is willing to share?

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
WWW.HAPB.NET

"Don't ask yourself what the world needs - ask yourself what makes you come alive, and then go do it." - H.T.Whitman

David B · 2009-04-16 16:42

I wrote this a long time ago to calculate the CRC for a sector of data read from a floppy disk, where a global byte array sectorbuffer[noparse]/noparse holds 0-511 bytes followed by two CRC values. It is hardcoded to the specific form of CCITT CRC used by floppies.

The routine calculates the CRC on all data plus the CRC values and returns zero if the data is OK, non-zero on error. I haven't run it for a long time but I believe it was working properly.

PUB doCRC | byteloop, bitloop, crc_value, ccitt, xorflag, mask, data_value

  crc_value := 14192
  ccitt := 4129

  repeat byteloop from 0 to 513
  
    data_value := sectorbuffer[noparse][[/noparse]byteloop]
    mask := 128
    
    repeat bitloop from 0 to 7

      xorflag := crc_value & 32768
      crc_value <<= 1
      if data_value & mask <> 0
        crc_value++
      mask >>= 1
      if xorflag <> 0
        crc_value ^= ccitt
    crc_value &= 65535

  return crc_value

jazzed · 2009-04-16 18:18

Table driven version if you have plenty of memory to spare [noparse]:)[/noparse]

{{
*************************************
* CRC16 - Uses CCITT polynomial
* Copyright (c) 2009, John Steven Denson
* See MIT license agreement terms at end of file
*************************************
}}
 

{ add comment tick before first char of this line for demo.
CON
   _clkmode = xtal1 + pll16x  
   _xinfreq = 5_000_000
   
var
   'byte value[noparse][[/noparse]3]
   long r
obj
   debug: "fullduplexserial"
   
pub main | i
   
   Debug.start(31, 30, 0, 115200)      'Start the debug terminal
   waitcnt(clkfreq*2+cnt)
   init(CCITT_POLY)
   r := get(@value,  strsize(@value), 0)
   debug.str(string($d,$d,"CCITT CRC16 INIT $0000 -> $"))
   debug.hex(r, 4)
   r := get(@value,  strsize(@value), CRC_INIT)
   debug.str(string($d,"CCITT CRC16 INIT $FFFF -> $"))
   debug.hex(r, 4)
   r := get(@value,  strsize(@value), $1d0f)
   debug.str(string($d,"CCITT CRC16 INIT $1D0F -> $"))
   debug.hex(r, 4)
dat
  value byte "000501",0
'}  

 
  
CON
{
  start with -1 to detect blank array
  mycrc := crc.get(dptr, bc#BIOS_DBASE_SIZE-2,CRC_INIT)
}
  CRC_INIT = $FFFF
  CCITT_POLY = $1021
  
DAT
  long
  crc_table word 0 [noparse][[/noparse]16*16]
 
PUB init(poly) | ii, jj, mcrc, c
{{
  initialize table using polynomial
  @param poly - bitstream representing polynomial ex: 0x8404
}}
  repeat ii from 0 to 255
    mcrc~
    c := (ii << 8) & CRC_INIT
    repeat jj from 0 to 7
      if ( (mcrc ^ c) & $8000 )
        mcrc := (mcrc << 1) ^ poly
      else
        mcrc <<= 1
      c <<= 1
      mcrc &= CRC_INIT       
    word[noparse][[/noparse]@crc_table+ii<<1] := mcrc
      
PUB get(msg, len, val) | ii
{{
  Get CRC for len msg with intial ival
  @param msg - byte array message
  @param len - number of bytes in msg array
  @param val - initial crc value ... normally $FFFF
  @returns CCITT CRC16
}}
  repeat ii from 0 to len-1
    val := CRC(val, byte[noparse][[/noparse]msg+ii])
  val &= CRC_INIT
  return val
PUB hash(key, mlen, mmask) | len
{{
  Get a CRC16 based hash of key of maximum length mlen key using mmask.
  This function will not create a perfect hash for all data.
  Other algorithms must be used in addition to guarantee uniqueness for keys. 
  @param key - key byte array string 
  @param mlen - maximum number of bytes in msg array
  @param mmask - mask used to defin 2^N hash table size
  @returns CCITT CRC16 based hash
}}
  len := strsize(key)
  if len => mlen  ' just calculate over the first VLEN bytes
    len := mlen
  result := get(key, len, CRC_INIT)
  result &= mmask
PRI CRC(crcval, ch) | ii
  ii := (crcval >> 8) ^ ch 
  result := ((crcval << 8) ^ word[noparse][[/noparse]@crc_table + ii<<1]) & CRC_INIT
 
 
{{
                             TERMS OF USE: MIT License

 
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights to
use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
of the Software, and to permit persons to whom the Software is furnished to do
so, subject to the following conditions:

 
The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.
 
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.

 
}}

Corrected version. Use your own polynomial for init if you like. Init must happen before CRC16 calculation. A demo is enclosed in { } above.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
--Steve

Propalyzer: Propeller PC Logic Analyzer
http://forums.parallax.com/showthread.php?p=788230

Post Edited (jazzed) : 4/17/2009 10:32:12 PM GMT

Earl Foster · 2009-04-16 19:40

Thanks guys. I will have to study both of these for a little while. Since I need to use XModem I assume I change the initial value to $0000

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
WWW.HAPB.NET

"Don't ask yourself what the world needs - ask yourself what makes you come alive, and then go do it." - H.T.Whitman

Earl Foster · 2009-04-17 14:11

Steve,
I think I am using your program incorrectly.· I am assiging "get(...)" to a variable and I am getting the incorrect CRC.· I modified the top to do a simple test and the r = $E415 when it should equal $2348 according to a·online CRC calculator. (http://www.lammertbies.nl/comm/info/crc-calculation.html?crc=000501&method=hex)

{{
*************************************
* CRC16 - Uses CCITT polynomial
*************************************
}}
CON
{
  start with -1 to detect blank array
  mycrc := crc.get(dptr, 1024, CRC_INIT)
}
   _clkmode = xtal1 + pll16x  
   _xinfreq = 5_000_000
   
   CRC_INIT = $FFFF
var
   byte value[noparse][[/noparse]3]
   long r
obj
   debug: "fullduplexserial"
   
pub main | i
   
   waitcnt(clkfreq+cnt)
   value[noparse][[/noparse]0] := $00
   value[noparse][[/noparse]1] := $05
   value[noparse][[/noparse]2] := $01
   Debug.start(31, 30, 0, 9600)      'Start the debug terminal
   r := get(value, 3, $FFFF)
   debug.hex(r, 4) 
  
DAT
{
   Rest of the code is exactly what you provided.
}

Can you set me straight?
Thanks

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
WWW.HAPB.NET

"Don't ask yourself what the world needs - ask yourself what makes you come alive, and then go do it." - H.T.Whitman

jazzed · 2009-04-17 17:12

Hmmm ... looking at it.
One thing to note is you would need to pass the value by reference as in: r := get(@value, 3, $ffff) .... still get the wrong value though.
I'll post a corrected and more flexible version sometime today.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
--Steve

Propalyzer: Propeller PC Logic Analyzer
http://forums.parallax.com/showthread.php?p=788230

Earl Foster · 2009-04-17 19:58

David,
I have tried playing with the code you provided and I am unable to get the correct CRC based on CRC site is use (http://www.lammertbies.nl/comm/info/crc-calculation.html?crc=000501&method=hex).· I am probably using it incorrectly.· I have made some assumptions and adjusted the code:

·- adjust byteloop to fit data size
·- crc_value is the initial value
·- ccitt is the poly

CON
   _clkmode = xtal1 + pll16x  
   _xinfreq = 5_000_000
var
   byte value[noparse][[/noparse]3]
   long r
obj
   debug: "fullduplexserial"
   
pub main | i
   
   waitcnt(clkfreq+cnt)
   value[noparse][[/noparse]0] := $00
   value[noparse][[/noparse]1] := $05
   value[noparse][[/noparse]2] := $01
   Debug.start(31, 30, 0, 9600)      'Start the debug terminal
   r := doCRC
   debug.hex(r, 4) 
  
PUB doCRC | byteloop, bitloop, crc_value, ccitt, xorflag, mask, data_value
  crc_value := $FFFF
  ccitt := $1021
  repeat byteloop from 0 to 2
  
    data_value := value[noparse][[/noparse]byteloop]
    mask := 128
    
    repeat bitloop from 0 to 7
      xorflag := crc_value & 32768
      crc_value <<= 1
      if data_value & mask <> 0
        crc_value++
      mask >>= 1
      if xorflag <> 0
        crc_value ^= ccitt
    crc_value &= 65535
  return crc_value

Can you provide guidance?

Thanks

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
WWW.HAPB.NET

"Don't ask yourself what the world needs - ask yourself what makes you come alive, and then go do it." - H.T.Whitman

jazzed · 2009-04-17 22:27

My post has been updated. It contains a demo that matches the results on the web site. I had been using a special polynomial and interpretation for a project ... pardon my mess.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
--Steve

Propalyzer: Propeller PC Logic Analyzer
http://forums.parallax.com/showthread.php?p=788230

David B · 2009-04-17 22:52

I'll try your test when I get a chance. I'm at work now, and don't have access to a propeller test platform, and my wife has made plans to go out for dinner tonight, so I probably won't get to it until this weekend sometime.

When I was learning how to get the floppy CRC to work, I found lots of variations in how CRCs are calculated. Some routines initialize the crc_value to 0, some to $FFFF, some to some other number. Some implementations invert results at some stage, some don't. And there are lots of different polynomials in use.

Floppy disks seem to initialize the crc_value to 14197 for the crc on the floppy header and to 14192 for the crc that follows the 512 bytes of data, but I've never found any documentation explaining why this is the case.

I'll hack around with your example and see if I can get it to work, and post what I find in a day or so.

David

Earl Foster · 2009-04-17 23:33

Steve,
This is great! You should post it in the obex since there has not been a CRC16 routine until now. Thanks

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
WWW.HAPB.NET

"Don't ask yourself what the world needs - ask yourself what makes you come alive, and then go do it." - H.T.Whitman

Rayman · 2009-04-18 11:46

I've posted a couple versions of a YMODEM (better than XMODEM) utility for the Prop that works with, e.g., hyperterminal.

It, of course, includes the crc16 code....

crc16

Comments