home *** CD-ROM | disk | FTP | other *** search
/ PD ROM 1 / PD ROM Volume I - Macintosh Software from BMUG (1988).iso / Programming / Complete Applications / Telecom / MT Special 3 / CRC next >
Encoding:
Text File  |  1987-01-01  |  8.6 KB  |  231 lines  |  [TEXT/ttxt]
  1. #: 38344 S3/Mac Programming
  2.     27-Aug-86  21:42:45
  3. Sb: #38303-CRC's
  4. Fm: Bela Lubkin/Amiga Forum 73047,1112
  5. To: Jerry LeVan 76354,364
  6.  
  7. These functions were written by Wayne Davison 76703,615 for my AmigaBinary
  8. spec.  I don't know enough about Mac C or assembly to know how portable they
  9. will be to your application, but they look like decently generic C and 68K
  10. assembly.  They implement the DDJ algorithm, and they definitely work.  Use a
  11. starting CRC value of 0 to get the output you need for XMODEM...
  12. /*
  13.         In Lattice/Aztec C, by Wayne Davison:
  14. */
  15. #define UWORD unsigned short  /* 16 bits */
  16. UWORD compute_crc(crc,bufptr,len)
  17. UWORD crc;
  18. char *bufptr;
  19. short len;
  20. {
  21.         int     i;
  22.         while (len--) {
  23.                 crc ^= (UWORD)(*bufptr++) << 8;
  24.                 for (i = 0; i < 8; ++i) {
  25.                         if (crc & 0x8000)
  26.                                 crc = (crc << 1) ^ 0x1021;
  27.                         else
  28.                                 crc <<= 1;
  29.                 }
  30.         }
  31.         return(crc);
  32. }
  33.  
  34. *
  35. *       In 68000 assembly language, by Wayne Davison:
  36. *
  37. ************
  38. compute_crc:
  39. ************
  40. * Entry:
  41. *       A0  ->  data buffer
  42. *       D1  ==  length
  43. *       D0  ==  CRC value
  44. *       D0  ==  new CRC value
  45. * Changed:
  46. *       D0,D1,D2,A0
  47. *
  48.         bra     crc_entry
  49. crc_loop:
  50.         move.b  (a0)+,d2                ; put char into d2
  51.         asl.w   #8,d2                   ; shift it into high byte of word
  52.         eor.w   d2,d0                   ; eor result into crc
  53.         moveq   #7,d2                   ; set loop counter to 8 iters (7-0)
  54.  
  55. crc_inner_loop:
  56.         asl.w   #1,d0                   ; shift crc left 1 bit
  57.         bcc     next_crc                ; skip eor if no carry
  58.         eor.w   #$1021,d0               ; eor in the magic number
  59. next_crc:
  60.         dbf     d2,crc_inner_loop       ; loop for all 8 bits
  61. crc_entry:
  62.         dbf     d1,crc_loop             ; continue if more chars
  63.         rts
  64.  
  65.   -  Bela
  66.  
  67. *** Reading replies to 38303 ***
  68. *** More ***
  69.  
  70.  
  71. #: 38370 S3/Mac Programming
  72.     28-Aug-86  02:04:24
  73. Sb: #38303-CRC's
  74. Fm: Steve Brecher 70001,1011
  75. To: Jerry LeVan 76354,364
  76.  
  77. Shift and xor, but at least fast shift and xor -- (I don't have a table lookup
  78. routine coded)...
  79.  
  80. ; untested asm routines (MDS format local labels)
  81.  
  82. ; function xmttedCRC(theData: datablock): integer;
  83. ; *** theData must start on a word boundary ***
  84. ; returns CRC to be transmitted (transmit high byte first)
  85. xmttedCRC:
  86.         Move.L  (SP)+,A1        ;return address
  87.         Move.L  (SP)+,A0        ;pointer to data
  88.         Move.L  D3,-(SP)        ;preserve
  89.         Move.L  #$10210000,D0   ;constant in high word
  90.         MoveQ   #0,D1           ;init CRC result (in high word)
  91.         MoveQ   #128/2-1,D3     ;for Dbra outer loop
  92. @0      MoveQ   #16-1,D2        ;for Dbra inner loop
  93.         Move    (A0)+,D1        ;two data bytes
  94. @1      Add.L   D0,D0           ;shift data bytes and CRC left
  95.         Bcc.S   @2              ;br if bit shifted out of CRC was clear
  96.         Eor.L   D0,D1           ;was set: xor CRC with constant
  97. @2      Dbra    D2,@1           ;end inner loop
  98.         Dbra    D3,@0           ;end outer loop
  99.         Clr     D1              ;two 0 bytes
  100.         MoveQ   #16-1,D2        ;update for two 0 bytes...
  101. @3      Add.L   D1,D1           ;shift CRC left
  102.         Bcc.S   @4              ;br if bit shifted out of CRC was clear
  103.         Eor.L   D0,D1           ;was set: xor CRC with constant
  104. @4      Dbra    D2,@3           ;end loop
  105.         Move.L  (SP)+,D3        ;restore
  106.         Swap    D1
  107.         Move    D1,(SP)         ;result
  108.         Jmp     (A1)            ;return
  109.  
  110. *** Reading replies to 38303 ***
  111. *** More ***
  112.  
  113. #: 38371 S3/Mac Programming
  114.     28-Aug-86  02:04:50
  115. Sb: #38303-CRC's
  116. Fm: Steve Brecher 70001,1011
  117. To: Jerry LeVan 76354,364
  118.  
  119. ; function CheckCRC(rcvdCRC: integer; theData: datablock): boolean;
  120. ; *** theData must start on a word boundary ***
  121. ; returns true if rcvdCRC (high byte received first) is correct.
  122. CheckCRC:
  123.         Move.L  (SP)+,A1        ;return address
  124.         Move.L  (SP)+,A0        ;pointer to data
  125.         Move.L  D3,-(SP)        ;preserve
  126.         Move.L  #$10210000,D0   ;constant in high word
  127.         MoveQ   #0,D1           ;init calculated CRC result in high word
  128.         MoveQ   #128/2-1,D3     ;for Dbra outer loop
  129. @0      MoveQ   #16-1,D2        ;for Dbra inner loop
  130.         Move    (A0)+,D1        ;two data bytes
  131. @1      Add.L   D1,D1           ;shift CRC and data bytes left
  132.         Bcc.S   @2              ;br if bit shifted out of calc CRC was clear
  133.         Eor.L   D0,D1           ;was set: xor calc CRC with constant
  134. @2      Dbra    D2,@1           ;end inner loop
  135.         Dbra    D3,@0           ;end outer loop
  136.         Move.L  (SP)+,D3        ;restore
  137.         Move    (SP)+,D1        ;received CRC
  138.         MoveQ   #16-1,D2        ;update for two received CRC bytes...
  139. @3      Add.L   D1,D1           ;shift calc CRC and received CRC bytes left
  140.         Bcc.S   @4              ;br if bit shifted out of calc CRC was clear
  141.         Eor.L   D0,D1           ;was set: xor calc CRC with constant
  142. @4      Dbra    D2,@3           ;end loop
  143.         Seq     (SP)            ;return (calculated result = 0)
  144.         Jmp     (A1)            ;return
  145.  
  146. *** Reading replies to 38303 ***
  147. *** More ***
  148.  
  149. #: 38678 S3/Mac Programming
  150.     01-Sep-86  16:13:17
  151. Sb: #38658-CRC's
  152. Fm: Bela Lubkin/Amiga Forum 73047,1112
  153. To: Jerry LeVan 76354,364
  154.  
  155. Well, I haven't programmed seriously in C for over 5 years, but I wrote the
  156. table routine in Pascal and converted it to C.  This code compiles, but I
  157. don't
  158. guarantee that it'll run; also, it could probably be optimized a bit.  The
  159. idea
  160. is to call the bit-shifting CRC routine 256 times to build a table, then use
  161. the table later.  I call compute_crc with an "old CRC" of 0000...FF00, by
  162. 0100's, and tell it to CRC in a single byte (which is 0).  Looking at the
  163. compute_crc routine, you can see that once the buffer byte has been XOR'd in,
  164. the rest of the computation is effectively an XOR of the low byte of the old
  165. CRC, shifted left 8, with a 16 bit value that is determined by the old high
  166. byte XOR'd with the buffer value.  (whew).  So by getting the CRC's of
  167. 0000..FF00, I get a table of those 16 bit XOR values.
  168.   To compute a CRC using the table, I XOR the high byte of the old CRC with
  169. the
  170. buffer byte, as in the shifting method.  Then I get the array value
  171. corresponding to that byte.  XORing that with the old CRC's low byte, now
  172. moved
  173. into the high byte, gives the new CRC value.
  174.   Late news: I dug up an old C compiler and made sure my code worked (and
  175. optimized it as well as I could).  I can't be 100% sure because the compiler
  176. was really flaky, but I did get correct results out of it when I got anything
  177. at all...
  178.  
  179.   Code:
  180.  
  181. unsigned short crc_table[256];
  182.  
  183. setup_crc_tables()
  184. {
  185.   int count;
  186.   char zero=0;
  187.  
  188.   for (count=0; count<256; count++)
  189.     crc_table[count]=compute_crc(count<<8,&zero,1);
  190. }
  191.  
  192. unsigned short table_driven_crc(crc,bufptr,len)
  193. unsigned short crc;
  194. unsigned char *bufptr;
  195. short len;
  196. {
  197.   while (len--)
  198.     crc=crc_table[crc>>8^(*bufptr++)]|crc<<8;
  199.   return(crc);
  200. }
  201.  
  202.   -  Bela
  203.  
  204. #: 39184 S3/Mac Programming
  205.     10-Sep-86  00:37:12
  206. Sb: #39164-CRC's
  207. Fm: Bela Lubkin 73047,1112
  208. To: Jerry LeVan 76354,364
  209.  
  210. Draw a picture?  Hmmm...  Lemme try words.  We'll start out by looking at
  211. compute_crc (actually, the contents of the while loop inside of compute_crc). 
  212. Imagine that instead of "crc", there are two variables, crc_high and crc_low. 
  213. By the time the inner loop is done, crc_high has been shifted entirely out of
  214. the picture.  The new crc_high is the old crc_low, and the new crc_low is 0,
  215. both XORed up to 8 times in passing, by the polynomial value 0x1021.  In the
  216. inner loop, 0x1021 is either XORed in, or not, depending on the value of a bit
  217. that will be shifted out of the picture by the time the loop is finished. 
  218. Those 8 XORs can be "folded" into a single XOR, since XOR is transitive.  The
  219. folded value is determined by the old crc_high XORed with the byte that is
  220. being CRCed.  That value, the old crc_high XORed with the byte that's being
  221. CRCed, can only take 256 values (it's a byte, after all).  So if we build a
  222. table of 256 values, one for each possible (old crc_high XOR
  223. byte_being_CRCed),
  224. then we can later build CRCs by using crc_high XOR byte_being_CRCed as an
  225. index
  226. into that table.  That's what build_crc_table and table_driven_crc do.
  227.   I'm afraid that's not terribly clear, but I hope that it will become clear
  228. after you've synthesized it with the actual code and a bit of deep (?)
  229. thinking...  -  Bela
  230.  
  231.