home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / C / Applications / Moscow ML 1.31 / source code / mosml / src / compiler / Crc.sml < prev    next >
Encoding:
Text File  |  1996-07-03  |  4.3 KB  |  126 lines  |  [TEXT/R*ch]
  1. (* CRC.sml -- written by Andrew Appel for SML/NJ, modified by PS 1994-10-24 *)
  2.  
  3.   (* 128-bit CRC.
  4.      The call `append crc c' corresponds to eight steps of a shift register
  5.      circuit, shifting in one bit of character c from the left in each step.
  6.      See Figure 2.16 in Bertsekas and Gallager: Data Networks (1987),
  7.      or  Figure 3-32 in Siewiorek and Swarz: The Theory and Practice
  8.                         of Reliable System Design (Digital Press, 1982).
  9.   *)
  10.  
  11. local
  12.   open Fnlib;
  13.  
  14. type crc = int ref * int Array.array * int ref;
  15.  
  16.   (* The prime generator polynomial is 1 + x + x^2 + x^7 + x^128.
  17.      Reversing the low coefficient bits we have 1110.0001 = 225 *)
  18.  
  19. val poly = 225;
  20.  
  21.  
  22.   prim_val andb_      : int -> int -> int = 2 "and";
  23.   prim_val xorb_      : int -> int -> int = 2 "xor";
  24.   prim_val lshift_    : int -> int -> int = 2 "shift_left";
  25.   prim_val rshiftsig_ : int -> int -> int = 2 "shift_right_signed";
  26.   prim_val rshiftuns_ : int -> int -> int = 2 "shift_right_unsigned";
  27.  
  28. (*
  29. fun init n =
  30.   let fun f 0 _ r = r
  31.         | f i p r = if (andb_ i 1) <> 0 then
  32.                       f (rshiftsig_ i 1) (p+p) (xorb_ p r)
  33.                     else
  34.                       f (rshiftsig_ i 1) (p+p) r
  35.   in f n poly 0 end
  36. ;
  37.  
  38. val table = Vector.tabulate(256, init);
  39. *)
  40.  
  41. val table =
  42. #[
  43.     0,   225,   450,   291,   900,   869,   582,   679,
  44.  1800,  2025,  1738,  1579,  1164,  1133,  1358,  1455,
  45.  3600,  3825,  4050,  3891,  3476,  3445,  3158,  3255,
  46.  2328,  2553,  2266,  2107,  2716,  2685,  2910,  3007,
  47.  7200,  7361,  7650,  7427,  8100,  8005,  7782,  7815,
  48.  6952,  7113,  6890,  6667,  6316,  6221,  6510,  6543,
  49.  4656,  4817,  5106,  4883,  4532,  4437,  4214,  4247,
  50.  5432,  5593,  5370,  5147,  5820,  5725,  6014,  6047,
  51. 14400, 14497, 14722, 14691, 15300, 15141, 14854, 15079,
  52. 16200, 16297, 16010, 15979, 15564, 15405, 15630, 15855,
  53. 13904, 14001, 14226, 14195, 13780, 13621, 13334, 13559,
  54. 12632, 12729, 12442, 12411, 13020, 12861, 13086, 13311,
  55.  9312,  9345,  9634,  9539, 10212,  9989,  9766,  9927,
  56.  9064,  9097,  8874,  8779,  8428,  8205,  8494,  8655,
  57. 10864, 10897, 11186, 11091, 10740, 10517, 10294, 10455,
  58. 11640, 11673, 11450, 11355, 12028, 11805, 12094, 12255,
  59. 28800, 28769, 28994, 29091, 29444, 29669, 29382, 29223,
  60. 30600, 30569, 30282, 30379, 29708, 29933, 30158, 29999,
  61. 32400, 32369, 32594, 32691, 32020, 32245, 31958, 31799,
  62. 31128, 31097, 30810, 30907, 31260, 31485, 31710, 31551,
  63. 27808, 27713, 28002, 28035, 28452, 28613, 28390, 28167,
  64. 27560, 27465, 27242, 27275, 26668, 26829, 27118, 26895,
  65. 25264, 25169, 25458, 25491, 24884, 25045, 24822, 24599,
  66. 26040, 25945, 25722, 25755, 26172, 26333, 26622, 26399,
  67. 18624, 18465, 18690, 18915, 19268, 19365, 19078, 19047,
  68. 20424, 20265, 19978, 20203, 19532, 19629, 19854, 19823,
  69. 18128, 17969, 18194, 18419, 17748, 17845, 17558, 17527,
  70. 16856, 16697, 16410, 16635, 16988, 17085, 17310, 17279,
  71. 21728, 21505, 21794, 21955, 22372, 22405, 22182, 22087,
  72. 21480, 21257, 21034, 21195, 20588, 20621, 20910, 20815,
  73. 23280, 23057, 23346, 23507, 22900, 22933, 22710, 22615,
  74. 24056, 23833, 23610, 23771, 24188, 24221, 24510, 24415
  75. ];
  76.  
  77. fun crc_new() = (ref 0, Array.array(16, 0), ref 0);
  78.  
  79. fun crc_extract(ref len, a, ref i) =
  80.   let open CharArray
  81.       val i' = i+1
  82.       val s = array(20, #"*")
  83.   in
  84.     update(s, 0, Char.chr (andb_ len 255));
  85.     update(s, 1, Char.chr (andb_ (rshiftsig_ len 8) 255));
  86.     update(s, 2, Char.chr (andb_ (rshiftsig_ len 16) 255));
  87.     update(s, 3, Char.chr (andb_ (rshiftsig_ len 24) 255));
  88.     for (fn k => update(s, 19-k, Char.chr(Array.sub(a, (i'+k) mod 16))))
  89.         0 15;
  90.     extract(s, 0, SOME 20)
  91.   end;
  92.  
  93. fun crc_append (rlen , a, (ri as ref i)) c =
  94.   let open Array
  95.       val rmbyte = sub(a, i)                (* rightmost byte *)
  96.       val hilo = Vector.sub(table, rmbyte)
  97.       val hi = rshiftsig_ hilo 8
  98.       val lo = andb_ hilo 255
  99.       val i' = (i+15) mod 16                (* leftmost byte  *)
  100.   in
  101.     ignore (Char.chr c);
  102.     update(a, i, xorb_ c hi);
  103.     update(a, i', xorb_ (sub(a, i')) lo);
  104.     ri := (i+1) mod 16;
  105.     incr rlen
  106.   end;
  107.  
  108. in
  109.  
  110. fun crcOfString s =
  111.   let val arr = crc_new ()
  112.       val len = size s
  113.   in
  114.     for (fn i => crc_append arr (Char.ord (CharVector.sub(s, i))))
  115.         0 (len-1);
  116.     crc_extract arr
  117.   end;
  118.  
  119. (* crcOfString "abcdefghijklmnopqrstuvwxyz"  -->
  120.       "kX\240\2109\151tV\178\020\247\241onml" *)
  121.  
  122. (* - crc "abcdefghijklmnopqrstuvwxyz";
  123.    > val it = "kX\240\2109\151tV\178\020\247\241onml" : string *)
  124.  
  125. end;
  126.