home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / dcom / modems / 17170 < prev    next >
Encoding:
Text File  |  1992-11-22  |  1.8 KB  |  46 lines
  1. Newsgroups: comp.dcom.modems
  2. Path: sparky!uunet!indetech!wetware!wsrcc!wolfgang
  3. From: wolfgang@wsrcc.com (Wolfgang S. Rupprecht)
  4. Subject: Re: Efficient CRC routine?
  5. Message-ID: <By5Hrs.GI3@wsrcc.com>
  6. Keywords: CRC
  7. Organization: W S Rupprecht Computer Consulting, Fremont CA
  8. References: <1394@minya.UUCP>
  9. Date: Mon, 23 Nov 1992 03:59:51 GMT
  10. Lines: 34
  11.  
  12. jc@minya.UUCP (John Chambers) writes:
  13. >I've generally dismissed the use of CRCs in software, because the only
  14. >algorithm I'd seen to generate (or check) them were so incredibly slow
  15. >(shifting the bits out of each byte, plugging each into a  polynomial,
  16. >and all that) that the performance hit was totally out of the range of
  17. >acceptability.  This, if you implement the algorithm in McNamara on  a
  18. >386,  calculating  a  CRC  for  a 1Kbyte chunk takes a major part of a
  19. >second.  It might as well take a year.  CRCs seemed like something  of
  20. >interest  only  to  hardware  types,  who  could  implement  them with
  21. >parallel hardware and do it quickly.
  22.  
  23. Its only one or two lines of C depending on how you count it.  Any
  24. good compiler will render it into 10 or less instructions.  Basically
  25. the inner loop is:
  26.  
  27.     unsigned char *cp, *ep;  /* current and end pointer */
  28.     unsigned short crc, crctab[];
  29.  
  30.     [...]
  31.  
  32.     while (cp < ep)
  33.     crc = crctab[(unsigned char) crc ^ *cp++] ^ (crc >> 8);
  34.  
  35. Filling in the crctab is left as an exercise to the reader. ;-)
  36.  
  37. (The biggest trick is often re-writing the C and casting it enough
  38. that the compiler gets a clue and generates good code.  For a typical
  39. 68k compiler you want to entice it to generate a dbz loop.  For a
  40. typical RISC compiler you probably want to do a pointer loop.)
  41.  
  42. -wolfgang
  43. -- 
  44. Wolfgang Rupprecht    wolfgang@wsrcc.com (or) decwrl!wsrcc!wolfgang
  45. Snail Mail:           39469 Gallaudet Drive, Fremont, CA 94538-4511
  46.