idnits 2.17.1 draft-ietf-tsvwg-sctpcsum-03.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing document type: Expected "INTERNET-DRAFT" in the upper left hand corner of the first page ** Missing expiration date. The document expiration date should appear on the first and last page. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. (A line matching the expected section header was found, but with an unexpected indentation: ' 3 Security Considerations' ) ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) (A line matching the expected section header was found, but with an unexpected indentation: ' 4 IANA Considerations' ) ** The document seems to lack an Authors' Addresses Section. ** There are 80 instances of too long lines in the document, the longest one being 5 characters in excess of 72. ** There are 16 instances of lines with control characters in the document. ** The abstract seems to contain references ([RFC2960]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 100: '... The keywords MUST, MUST NOT, REQUI...' RFC 2119 keyword, line 101: '... NOT, RECOMMENDED, NOT RECOMMENDED,...' RFC 2119 keyword, line 106: '...n section 2.1 of this document MUST be...' RFC 2119 keyword, line 108: '... Furthermore any references within [RFC2960] to Adler-32 MUST be treated...' RFC 2119 keyword, line 110: '...tion procedures that MUST be followed....' (7 more instances...) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == Line 160 has weird spacing: '... it cannot...' == Line 165 has weird spacing: '...ages to polyn...' == Line 169 has weird spacing: '...in each byte,...' == Line 181 has weird spacing: '...N-1, is consi...' == Line 183 has weird spacing: '...it 7 of byte...' == (6 more instances...) == Unrecognized Status in '', assuming Proposed Standard (Expected one of 'Standards Track', 'Full Standard', 'Draft Standard', 'Proposed Standard', 'Best Current Practice', 'Informational', 'Experimental', 'Informational', 'Historic'.) -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (March 1, 2002) is 8092 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: 'RFC2960' is mentioned on line 327, but not defined ** Obsolete undefined reference: RFC 2960 (Obsoleted by RFC 4960) == Missing Reference: 'RFC2119' is mentioned on line 324, but not defined == Missing Reference: 'ITU32' is mentioned on line 332, but not defined == Missing Reference: 'Peterson 72' is mentioned on line 284, but not defined == Missing Reference: 'Castagnoli93' is mentioned on line 312, but not defined == Missing Reference: 'Blahut 94' is mentioned on line 389, but not defined == Missing Reference: 'McKee75' is mentioned on line 316, but not defined == Missing Reference: 'RFC2026' is mentioned on line 321, but not defined == Missing Reference: 'Prange 57' is mentioned on line 387, but not defined -- Looks like a reference, but probably isn't: '256' on line 602 == Unused Reference: 'Blahut 1994' is defined on line 345, but no explicit reference was found in the text == Unused Reference: 'Prange 1957' is defined on line 360, but no explicit reference was found in the text == Unused Reference: 'Peterson 1972' is defined on line 364, but no explicit reference was found in the text == Unused Reference: 'Sprachman2001' is defined on line 419, but no explicit reference was found in the text Summary: 11 errors (**), 0 flaws (~~), 21 warnings (==), 4 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Network Working Group R. Stewart 2 Category: Internet Draft Cisco Systems 3 J. Stone 4 Stanford 5 D. Otis 6 SANlight 8 March 1, 2002 10 SCTP Checksum Change 11 draft-ietf-tsvwg-sctpcsum-03.txt 13 Status of this Memo 15 This document is an internet-draft and is in full conformance with all 16 provisions of Section 10 of RFC2026. 18 Internet-Drafts are working documents of the Internet Engineering Task 19 Force (IETF), its areas, and its working groups. Note that other groups 20 may also distribute working documents as Internet-Drafts. Internet- 21 Drafts are draft documents valid for a maximum of six months and may be 22 updated, replaced, or obsoleted by other documents at any time. It is 23 inappropriate to use Internet-Drafts as reference material or to cite 24 them other than as "work in progress." 25 The list of current Internet-Drafts can be accessed at 26 http://www.ietf.org/ietf/1id-abstracts.txt 27 The list of Internet-Draft Shadow Directories can be accessed at 28 http://www.ietf.org/shadow.html. 30 Abstract 32 SCTP [RFC2960] currently uses an Adler-32 checksum. For small packets 33 Adler-32 provides weak detection of errors. This document changes that 34 checksum and updates SCTP to use a 32 bit CRC checksum. 36 Table of Contents 38 1 Introduction ................................................ 1 39 2 Checksum Procedures ......................................... 2 40 3 Security Considerations...................................... 5 41 4 IANA Considerations.......................................... 5 42 5 Acknowledgments ............................................. 5 43 6 Authors' Addresses .......................................... 6 44 7 References .................................................. 7 45 8 Appendix .................................................... 8 47 1 Introduction 49 A fundamental weakness has been detected in SCTP's current Adler-32 50 checksum algorithm [STONE]. One requirement of an effective checksum is 51 that it evenly and smoothly spreads its input packets over the available 52 check bits. 54 From an email from Jonathan Stone, who analyzed the Adler-32 as part 55 of his doctoral thesis: 57 "Briefly, the problem is that, for very short packets, Adler32 is 58 guaranteed to give poor coverage of the available bits. Don't take my 59 word for it, ask Mark Adler. :-). 61 Adler-32 uses two 16-bit counters, s1 and s2. s1 is the sum of the 62 input, taken as 8-bit bytes. s2 is a running sum of each value of s1. 63 Both s1 and s2 are computed mod-65521 (the largest prime less than 2^16). 64 Consider a packet of 128 bytes. The *most* that each byte can be is 255. 65 There are only 128 bytes of input, so the greatest value which the s1 66 accumulator can have is 255 * 128 = 32640. So for 128-byte packets, s1 67 never wraps. That is critical. Why? 69 The key is to consider the distribution of the s1 values, over some 70 distribution of the values of the individual input bytes in each packet. 71 Because s1 never wraps, s1 is simply the sum of the individual input 72 bytes. (even Doug's trick of adding 0x5555 doesn't help here, and an even 73 larger value doesn't really help: we can get at most one mod-65521 74 reduction). 76 Given the further assumption that the input bytes are drawn independently 77 from some distribution (they probably aren't: for file system data, it's 78 even worse than that!), the Central Limit Theorem tells us that that s1 79 will tend to have a normal distribution. That's bad: it tells us that 80 the value of s1 will have hot-spots at around 128 times the mean of the 81 input distribution: around 16k, assuming a uniform distribution. That's 82 bad. We want the accumulator to wrap as many times as possible, so that 83 the resulting sum has as close to a uniform distribution as possible. (I 84 call this "fairness"). 86 So, for short packets, the Adler-32 s1 sum is guaranteed to be unfair. 87 Why is that bad? It's bad because the space of valid packets-- input 88 data, plus checksum values -- is also small. If all packets have 89 checksum values very close to 32640, then the likelihood of even a 90 'small' error leaving a damaged packet with a valid checksum is higher 91 than if all checksum values are equally likely." 93 Due to this inherent weakness, exacerbated by the fact that SCTP will 94 first be used as a signaling transport protocol where signaling messages 95 are usually less than 128 bytes, a new checksum algorithm is specified by 96 this document, replacing the current Adler-32 algorithm with CRC-32c. 98 1.1 Conventions 100 The keywords MUST, MUST NOT, REQUIRED, SHALL, SHALL NOT, SHOULD,SHOULD 101 NOT, RECOMMENDED, NOT RECOMMENDED, MAY, and OPTIONAL, when they appear in 102 this document, are to be interpreted as described in [RFC2119]. 104 2 Checksum Procedures 106 The procedures described in section 2.1 of this document MUST be 107 followed, replacing the current checksum defined in [RFC2960]. 108 Furthermore any references within [RFC2960] to Adler-32 MUST be treated 109 as a reference to CRC-32c. Section 2.1 of this document describes the 110 new calculation and verification procedures that MUST be followed. 112 2.1 Checksum Calculation 114 When sending an SCTP packet, the endpoint MUST include in the checksum 115 field the CRC-32c value calculated on the packet, as described below. 117 After the packet is constructed (containing the SCTP common header and 118 one or more control or DATA chunks), the transmitter MUST do the 119 following: 121 1) Fill in the proper Verification Tag in the SCTP common header and 122 initialize the Checksum field to 0's. 124 2) Calculate the CRC-32c of the whole packet, including the SCTP common 125 header and all the chunks. 127 3) Put the resultant value into the Checksum field in the common header, 128 and leave the rest of the bits unchanged. 130 When an SCTP packet is received, the receiver MUST first perform the 131 following: 133 1) Store the received CRC-32c value, 135 2) Replace the 32 bits of the Checksum field in the received SCTP packet 136 with all '0's and calculate a CRC-32c value of the whole received 137 packet. And, 139 3) Verify that the calculated CRC-32c value is the same as the received 140 CRC-32c value. If not, the receiver MUST treat the packet as an 141 invalid SCTP packet. 143 The default procedure for handling invalid SCTP packets is to silently 144 discard them. 146 We define a 'reflected value' as one that is the opposite of the 147 normal bit order of the machine. The 32 bit CRC is 148 calculated as described for CRC-32c and uses the polynomial code 149 0x11EDC6F41 (Castagnoli93) or x^32+x^28+x^27+x^26+x^25 150 +x^23+x^22+x^20+x^19+x^18+x^14+x^13+x^11+x^10+x^9+x^8+x^6+x^0. 151 The CRC is computed using a procedure similar to ETHERNET CRC [ITU32], 152 modified to reflect transport level usage. 154 CRC computation uses polynomial division. A message bit-string M 155 is transformed to a polynomial, M(X), and the CRC is calculated 156 from M(X) using polynomial arithmetic [Peterson 72]. 157 When CRCs are used at the link layer, the polynomial is derived from 158 on-the-wire bit ordering: the first bit `on the wire' is 159 the high-order coefficient. Since SCTP is a transport-level protocol, 160 it cannot know the actual serial-media bit ordering. Moreover, 161 different links in the path between SCTP endpoints may use 162 different link-level bit orders) 163 A convention must therefore be established for mapping SCTP transport 164 messages to polynomials for purposes of CRC computation. 165 The bit-ordering for mapping SCTP messages to polynomials is 166 that bytes are taken most-significant first; but within each byte, 167 bits are taken least-significant first. The first byte of the 168 message provides the eight highest coefficients. 169 Within each byte, the least-significant SCTP bit gives the 170 most significant polynomial coefficient within that byte, and 171 the most-significant SCTP bit is the most significant polynomial 172 coefficient in that byte. (This bit ordering is sometimes 173 called `mirrored' or `reflected' [Williams93].) CRC polynomials 174 are to be transformed back into SCTP transport-level byte values 175 using a consistent mapping. 177 The SCTP transport-level CRC value should be calculated as follows: 178 - CRC input data are assumed to a byte stream numbered from 0 179 to N-1. 180 - the transport-level byte-stream is mapped to a polynomial value. 181 An N-byte PDU with bytes 0 to N-1, is considered as 182 coefficients of a polynomial M(x) of order 8N-1, with 183 bit 0 of byte j being coefficient x^(8j-1), bit 7 of byte 184 0 being coefficient x(8j^-8). 185 - the CRC remainder register is initialized with all 186 1s (equivalent to complementing the first 32 bits of the message) 187 - the polynomial is multiplied by x^32 and divided by G(x), 188 the generator polynomial, producing a remainder R(x) of degree 189 less than or equal to 31. 190 - the coefficients of R(x) are considered a 32 bit sequence. 191 - the bit sequence is complemented. The resulting is the CRC 192 polynomial. 193 - The CRC polynomial is mapped back into SCTP transport-level 194 bytes. Coefficient of x^31 gives the value of bit 0 of 195 SCTP byte 0, the coefficient of x^24 gives the value of 196 bit 7 of byte 0. the coefficient of x^7 gives bit 0 of 197 bit 0 and the coefficient of x^0 0 gives bit 7 of byte 3. 198 The resulting four-byte transport-level sequence is the 199 32-bit SCTP checksum value. 201 When an SCTP packet is transmitted, the sender MUST perform this 202 checksum procedure, using the preceding CRC computation: 204 1) Fill in the proper Verification Tag in the SCTP common header and 205 initialize the Checksum field to 0's. 207 2) Calculate the CRC-32c of the whole packet, including the SCTP common 208 header and all the chunks. 210 3) Put the resultant 32-bit SCTP checksum value into the Checksum field 211 in the common header, and leave the rest of the bits unchanged. 213 When an SCTP packet is received, the receiver MUST first perform the 214 following: 216 1) Store the received CRC-32c value, 218 2) Replace the 32 bits of the Checksum field in the received SCTP packet 219 with all '0's and calculate the SCTP CRC-32c checksum value of 220 the whole received packet. And, 222 3) Verify that the calculated CRC-32c value is the same as the received 223 CRC-32c value. If not, the receiver MUST treat the packet as an 224 invalid SCTP packet. 226 The default procedure for handling invalid SCTP packets is to silently 227 discard them. 229 If SCTP could follow link level CRC use, the CRC would be computed 230 over the link-level bit-stream. The first bit on the link 231 mapping to the highest-order coefficient, and so on down to the 232 last link-level bit as the lowest-order coefficient. The CRC value 233 would be transmitted immediately after the input message as a link-level 234 `trailer'. The resulting link-level bit-stream would be 235 (M(X)x) * x^32) + (M(X)*x^32))/ G(x), which is divisible by G(X). 236 There would thus be a constant CRC remainder for `good' packets. 237 However, given that implementations of RFC2960 have already 238 proliferated, the IETF discussions considered that the benefit of 239 a `trailer' CRC did not outweigh the cost of making a very large 240 change in the protocol processing. Further, packets accepted by 241 the SCTP `header' CRC are in one-to-one correspondence with 242 packets accepted by a modified procedure using a `trailer' 243 CRC value, and where the SCTP common checksum header is set to zero 244 on transmission and is received as zero. 246 There may be a computational advantage in validating the Association 247 against the Verification Tag prior to performing a checksum as 248 invalid tags will result in the same action as a bad checksum in 249 most cases. The exceptions for this technique would be INIT and some 250 SHUTDOWN-COMPLETE exchanges as well as a stale COOKIE-ECHO. These 251 special case exchanges must represent small packets and will 252 minimize the effect of the checksum calculation. 254 3 Security Considerations 256 In general, the security considerations of RFC2960 apply to 257 the protocol with the new checksum as well. 259 4 IANA Considerations 261 There are no IANA considerations required in this document. 263 5 Acknowledgments 265 The authors would like to thank the following people that have 266 provided comments and input on the checksum issue: 268 Mark Adler, Ran Atkinson, Stephen Bailey, David Black, Scott 269 Bradner, Mikael Degermark, Laurent Glaude, Klaus Gradischnig, Alf 270 Heidermark, Jacob Heitz, Gareth Kiely, David Lehmann, Allision 271 Mankin, Lyndon Ong, Craig Partridge, Vern Paxson, Kacheong Poon, 272 Michael Ramalho, David Reed, Ian Rytina, Hanns Juergen Schwarzbauer, 273 Chip Sharp, Bill Sommerfeld, Michael Tuexen, Jim Williams, Jim Wendt, 274 Michael Welzl, Jonathan Wood, Lloyd Wood, Qiaobing Xie, La Monte 275 Yarroll. 277 Special thanks to Dafna Scheinwald, Julian Satran Pat Thaler, Matt 278 Wakeley, and Vince Cavanna, for selection criteria of polynomials and 279 examination of CRC polynomials, particularly CRC-32c [Castagnoli93]. 281 Special thanks to Mr. Ross Williams and his document [Williams93]. 282 This non-formal perspective on software aspects of CRCs furthered 283 understanding of authors previously unfamiliar with CRC computation. 284 More formal treatments of [Blahut 94] or [Peterson 72], was 285 also essential. 287 6 Authors' Addresses 289 Randall R. Stewart 290 24 Burning Bush Trail. 291 Crystal Lake, IL 60012 292 USA 294 EMail: rrs@cisco.com 296 Jonathan Stone 297 Room 446, Mail code 9040 298 Gates building 4A 299 Stanford, Ca 94305 301 EMail: jonathan@dsg.stanford.edu 303 Douglas Otis 304 800 E. Middlefield 305 Mountain View, CA 94043 306 USA 308 Email dotis@sanlight.net 310 7 References 312 [Castagnoli93] G. Castagnoli, S. Braeuer and M. Herrman, 313 "Optimization of Cyclic Redundancy-Check Codes with 24 and 32 Parity 314 Bits", IEEE Transactions on Communications, Vol. 41, No. 6, June 1993 316 [McKee75] H. McKee, "Improved {CRC} techniques detects erroneous 317 leading and trailing 0's in transmitted data blocks", 318 Computer Design Volume 14 Number 10 Pages 102-4,106, 319 October 1975 321 [RFC2026] Bradner, S., "The Internet Standards Process -- Revision 322 3", BCP 9, RFC 2026, October 1996. 324 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 325 Requirement Levels", BCP 14, RFC 2119, March 1997. 327 [RFC2960] R. R. Stewart, Q. Xie, K. Morneault, C. Sharp, 328 H. J. Schwarzbauer, T. Taylor, I. Rytina, M. Kalla, L. Zhang, 329 and, V. Paxson, "Stream Control Transmission Protocol," RFC 330 2960, October 2000. 332 [ITU32] ITU-T Recommendation V.42, "Error-correcting 333 procedures for DCEs using asynchronous-to-synchronous 334 conversion", section 8.1.1.6.2, October 1996. 336 7.1 Informative References 338 [STONE] Stone, J., "Checksums in the Internet", Doctoral 339 dissertation - August 2001 341 [Williams93] Williams, R., "A PAINLESS GUIDE TO CRC ERROR DETECTION 342 ALGORITHMS" - Internet publication, August 1993, 343 http://www.geocities.com/SiliconValley/Pines/8659/crc.htm. 345 [Blahut 1994], R.E. Blahut, Theory and Practice of Error Control 346 Codes, Addison-Wesley, 1994. 348 [Easics 2001]. http://www.easics.be/webtools/crctool. Online tools 349 for synthesis of CRC Verilog and VHDL. 351 [Feldmeier 95], David C. Feldmeier, Fast software implementation of 352 error detection codes, IEEE Transactions on Networking, vol 3 no 6, 353 pp 640-651, December, 1995. 355 [Glaise 1997] R. J. Glaise, A two-step computation of cyclic 356 redundancy code CRC-32 for ATM networks, IBM Journal of Research and 357 Development} vol 41 no 6, 1997. URL= 358 http://www.research.ibm.com/journal/rd/416/glaise.html. 360 [Prange 1957], E. Prange, Cyclic Error-Correcting codes in two 361 symbols, Technical report AFCRC-TN-57-103, Air Force Cambridge 362 Research Center, Cambridge, Mass. 1957. 364 [Peterson 1972], W. W. Peterson and E.J Weldon, Error Correcting 365 Codes, 2nd. edition, MIT Press, Cambridge, Massachusetts. 367 [Shie2001] Ming-Der Shieh et. al, A Systematic Approach for Parallel 368 CRC Computations. Journal of Information Science and Engineering, 369 Vol.17 No.3, pp.445-461 371 [Sprachman2001] Michael Sprachman, Automatic Generation of Parallel 372 CRC Circuits, IEEE Design & Test May-June 2001 374 8 Appendix 375 This appendix is for information only and is NOT part of the 376 standard. 378 The anticipated deployment of SCTP ranges over several orders of 379 magnitude of link speed: from cellular-power telephony devices at 380 tens of kilobits, to local links at tens of gigabits. Implementors 381 of SCTP should consider their link speed and choose, from the wide 382 range of CRC implementations, one which matches their own design 383 point for size, cost, and throughput. Many techniques for computing 384 CRCs are known. This Appendix surveys just a few, to give a feel for 385 the range of techniques available. 387 CRCs are derived from early work by Prange in the 1950s [Prange 57]. 388 The theory underlying CRCs and choice of generator polynomial can be 389 introduced by either via the theory of Galois fields [Blahut 94] 390 or as ideals of an algebra over cyclic codes [cite Peterson 72]. 392 One of the simplest techniques is direct bit-serial hardware 393 implementations, using the generator polynomial as the taps of a 394 linear feedback shift register (LSFR). LSFR computation follows 395 directly from the mathematics, and is generally attributed to Prange. 396 Tools exist which, a CRC generator polynomial, will produce 397 synthesizable Verilog code for CRC hardware [Easics 2001]. 399 Since LSFRs do not scale well in speed, a variety of other 400 techniques have been explored. One technique exploits the fact that 401 the divisor of the polynomial long-division, G, is known in 402 advance. It is thus possible to pre-compute lookup tables giving the 403 polynomial remainder of multiple input bits --- typically 2, 4, or 8 404 bits of input at a time. This technique can be used either in 405 software or in hardware. Software to compute lookup tables yielding 406 2, 4, or 8 bits of result is freely available. [Williams93] 408 For multi-gigabit links, the above techniques may still not be fast 409 enough. One technique for computing CRCS at OC-48 rates is 410 `two-stage' CRC computation [Glaise 1997]. Here, some multiple 411 of G(x), G(x)H(x), is chosen so as to minimize the number of nonzero 412 coefficients, or weight, of the product G(x)H(x). The low weight of 413 the product polynomial makes it susceptible to efficient hardware 414 divide-by-constant implementations. This first stage gives M(x) / 415 (G(x)H(x)) as its result. The second stage then divides the result 416 of the first stage by H(x), yielding (M(x) / (G(x)H(x))) / H(x). If 417 H(x) is also relatively prime to G(x), this gives M(x)/G(x). 418 Further developments on this approach can be found in [Shie2001] and 419 [Sprachman2001]. 421 The literature also includes a variety of software CRC 422 implementations. One approach is to use carefully-tuned assembly 423 code for direct polynomial division. [Feldmeier 95] reports that for 424 low-weight polynomials, tuned polynomial arithmetic gives higher 425 throughput than table-lookup algorithms. Even within table-lookup 426 algorithms, the size of the table can be tuned, either for total 427 cache footprint, or (for space-restricted environments) to minimize 428 total size. 430 Implementors should keep in mind the bit ordering described in 431 Section 2: the ordering of bits within bytes for computing CRCs in 432 SCTP is the least significant bit of each byte is the 433 most-significant polynomial coefficient(and vice-versa). This 434 `reflected' SCTP CRC bit ordering matches on-the-wire bit order for 435 Ethernet and other serial media, but is the reverse of traditional 436 Internet bit ordering. 438 One technique to accommodate this bit-reversal can be explained as 439 follows: sketch out a hardware implementation assuming the bits are 440 in CRC bit order; then perform a left-to-right inversion (mirror 441 image) on the entire algorithm. (We defer for a moment the issue of 442 byte order within words.) Then compute that "mirror image" in 443 software. The CRC from the ``mirror image'' algorithm will be the 444 bit-reversal of a correct hardware implementation. When the 445 link-level media sends each byte, the byte is sent in the reverse of 446 the host CPU bit-order. Serialization of each byte of the 447 ``reflected'' CRC value re-reverses the bit order, so in the end, 448 each byte will be transmitted on-the-wire in the specified bit 449 order. 451 The following non-normative sample code is taken from an open-source 452 CRC generator [Williams93] using the ``mirroring'' technique 453 and yielding a lookup table for SCTP CRC32-c with 256 entries, each 454 32 bits wide. While neither especially slow nor especially fast, as 455 software table-lookup CRCs go, it has the advantage of working on 456 both big-endian and little-endian CPUs, using the same (host-order) 457 lookup tables, and using only the pre-defined ntohl() and htonl() 458 operations. The code is somewhat modified from [Williams93], to 459 ensure portability between big-endian and little-endian 460 architectures. (Note that if the byte endian-ness of the target 461 architecture is known to be little-endian the final bit-reversal and 462 byte-reversal steps can be folded into a single operation.) 464 /*************************************************************/ 465 /* Note Definition for Ross Williams table generator would */ 466 /* be: TB_WIDTH=4, TB_POLLY=0x1EDC6F41, TB_REVER=TRUE */ 467 /* For Mr. Williams direct calculation code use the settings */ 468 /* cm_width=32, cm_poly=0x1EDC6F41, cm_init=0xFFFFFFFF, */ 469 /* cm_refin=TRUE, cm_refot=TRUE, cm_xorort=0x00000000 */ 470 /*************************************************************/ 472 /* Example of the crc table file */ 473 #ifndef __crc32cr_table_h__ 474 #define __crc32cr_table_h__ 476 #define CRC32C_POLY 0x1EDC6F41 477 #define CRC32C(c,d) (c=(c>>8)^crc_c[(c^(d))&0xFF]) 479 unsigned long crc_c[256] = 480 { 481 0x00000000L, 0xF26B8303L, 0xE13B70F7L, 0x1350F3F4L, 482 0xC79A971FL, 0x35F1141CL, 0x26A1E7E8L, 0xD4CA64EBL, 483 0x8AD958CFL, 0x78B2DBCCL, 0x6BE22838L, 0x9989AB3BL, 484 0x4D43CFD0L, 0xBF284CD3L, 0xAC78BF27L, 0x5E133C24L, 485 0x105EC76FL, 0xE235446CL, 0xF165B798L, 0x030E349BL, 486 0xD7C45070L, 0x25AFD373L, 0x36FF2087L, 0xC494A384L, 487 0x9A879FA0L, 0x68EC1CA3L, 0x7BBCEF57L, 0x89D76C54L, 488 0x5D1D08BFL, 0xAF768BBCL, 0xBC267848L, 0x4E4DFB4BL, 489 0x20BD8EDEL, 0xD2D60DDDL, 0xC186FE29L, 0x33ED7D2AL, 490 0xE72719C1L, 0x154C9AC2L, 0x061C6936L, 0xF477EA35L, 491 0xAA64D611L, 0x580F5512L, 0x4B5FA6E6L, 0xB93425E5L, 492 0x6DFE410EL, 0x9F95C20DL, 0x8CC531F9L, 0x7EAEB2FAL, 493 0x30E349B1L, 0xC288CAB2L, 0xD1D83946L, 0x23B3BA45L, 494 0xF779DEAEL, 0x05125DADL, 0x1642AE59L, 0xE4292D5AL, 495 0xBA3A117EL, 0x4851927DL, 0x5B016189L, 0xA96AE28AL, 496 0x7DA08661L, 0x8FCB0562L, 0x9C9BF696L, 0x6EF07595L, 497 0x417B1DBCL, 0xB3109EBFL, 0xA0406D4BL, 0x522BEE48L, 498 0x86E18AA3L, 0x748A09A0L, 0x67DAFA54L, 0x95B17957L, 499 0xCBA24573L, 0x39C9C670L, 0x2A993584L, 0xD8F2B687L, 500 0x0C38D26CL, 0xFE53516FL, 0xED03A29BL, 0x1F682198L, 501 0x5125DAD3L, 0xA34E59D0L, 0xB01EAA24L, 0x42752927L, 502 0x96BF4DCCL, 0x64D4CECFL, 0x77843D3BL, 0x85EFBE38L, 503 0xDBFC821CL, 0x2997011FL, 0x3AC7F2EBL, 0xC8AC71E8L, 504 0x1C661503L, 0xEE0D9600L, 0xFD5D65F4L, 0x0F36E6F7L, 505 0x61C69362L, 0x93AD1061L, 0x80FDE395L, 0x72966096L, 506 0xA65C047DL, 0x5437877EL, 0x4767748AL, 0xB50CF789L, 507 0xEB1FCBADL, 0x197448AEL, 0x0A24BB5AL, 0xF84F3859L, 508 0x2C855CB2L, 0xDEEEDFB1L, 0xCDBE2C45L, 0x3FD5AF46L, 509 0x7198540DL, 0x83F3D70EL, 0x90A324FAL, 0x62C8A7F9L, 510 0xB602C312L, 0x44694011L, 0x5739B3E5L, 0xA55230E6L, 511 0xFB410CC2L, 0x092A8FC1L, 0x1A7A7C35L, 0xE811FF36L, 512 0x3CDB9BDDL, 0xCEB018DEL, 0xDDE0EB2AL, 0x2F8B6829L, 513 0x82F63B78L, 0x709DB87BL, 0x63CD4B8FL, 0x91A6C88CL, 514 0x456CAC67L, 0xB7072F64L, 0xA457DC90L, 0x563C5F93L, 515 0x082F63B7L, 0xFA44E0B4L, 0xE9141340L, 0x1B7F9043L, 516 0xCFB5F4A8L, 0x3DDE77ABL, 0x2E8E845FL, 0xDCE5075CL, 517 0x92A8FC17L, 0x60C37F14L, 0x73938CE0L, 0x81F80FE3L, 518 0x55326B08L, 0xA759E80BL, 0xB4091BFFL, 0x466298FCL, 519 0x1871A4D8L, 0xEA1A27DBL, 0xF94AD42FL, 0x0B21572CL, 520 0xDFEB33C7L, 0x2D80B0C4L, 0x3ED04330L, 0xCCBBC033L, 521 0xA24BB5A6L, 0x502036A5L, 0x4370C551L, 0xB11B4652L, 522 0x65D122B9L, 0x97BAA1BAL, 0x84EA524EL, 0x7681D14DL, 523 0x2892ED69L, 0xDAF96E6AL, 0xC9A99D9EL, 0x3BC21E9DL, 524 0xEF087A76L, 0x1D63F975L, 0x0E330A81L, 0xFC588982L, 525 0xB21572C9L, 0x407EF1CAL, 0x532E023EL, 0xA145813DL, 526 0x758FE5D6L, 0x87E466D5L, 0x94B49521L, 0x66DF1622L, 527 0x38CC2A06L, 0xCAA7A905L, 0xD9F75AF1L, 0x2B9CD9F2L, 528 0xFF56BD19L, 0x0D3D3E1AL, 0x1E6DCDEEL, 0xEC064EEDL, 529 0xC38D26C4L, 0x31E6A5C7L, 0x22B65633L, 0xD0DDD530L, 530 0x0417B1DBL, 0xF67C32D8L, 0xE52CC12CL, 0x1747422FL, 531 0x49547E0BL, 0xBB3FFD08L, 0xA86F0EFCL, 0x5A048DFFL, 532 0x8ECEE914L, 0x7CA56A17L, 0x6FF599E3L, 0x9D9E1AE0L, 533 0xD3D3E1ABL, 0x21B862A8L, 0x32E8915CL, 0xC083125FL, 534 0x144976B4L, 0xE622F5B7L, 0xF5720643L, 0x07198540L, 535 0x590AB964L, 0xAB613A67L, 0xB831C993L, 0x4A5A4A90L, 536 0x9E902E7BL, 0x6CFBAD78L, 0x7FAB5E8CL, 0x8DC0DD8FL, 537 0xE330A81AL, 0x115B2B19L, 0x020BD8EDL, 0xF0605BEEL, 538 0x24AA3F05L, 0xD6C1BC06L, 0xC5914FF2L, 0x37FACCF1L, 539 0x69E9F0D5L, 0x9B8273D6L, 0x88D28022L, 0x7AB90321L, 540 0xAE7367CAL, 0x5C18E4C9L, 0x4F48173DL, 0xBD23943EL, 541 0xF36E6F75L, 0x0105EC76L, 0x12551F82L, 0xE03E9C81L, 542 0x34F4F86AL, 0xC69F7B69L, 0xD5CF889DL, 0x27A40B9EL, 543 0x79B737BAL, 0x8BDCB4B9L, 0x988C474DL, 0x6AE7C44EL, 544 0xBE2DA0A5L, 0x4C4623A6L, 0x5F16D052L, 0xAD7D5351L, 545 }; 547 #endif 549 /* Example of table build routine */ 551 #include 552 #include 554 #define OUTPUT_FILE "crc32cr.h" 555 #define CRC32C_POLY 0x1EDC6F41L 556 FILE *tf; 558 unsigned long 559 reflect_32 (unsigned long b) 560 { 561 int i; 562 unsigned long rw = 0L; 564 for (i = 0; i < 32; i++){ 565 if (b & 1) 566 rw |= 1 << (31 - i); 567 b >>= 1; 568 } 569 return (rw); 570 } 572 unsigned long 573 build_crc_table (int index) 574 { 575 int i; 576 unsigned long rb; 578 rb = reflect_32 (index); 580 for (i = 0; i < 8; i++){ 581 if (rb & 0x80000000L) 582 rb = (rb << 1) ^ CRC32C_POLY; 583 else 584 rb <<= 1; 585 } 586 return (reflect_32 (rb)); 587 } 589 main () 590 { 591 int i; 593 printf ("\nGenerating CRC-32c table file <%s>\n", OUTPUT_FILE); 594 if ((tf = fopen (OUTPUT_FILE, "w")) == NULL){ 595 printf ("Unable to open %s\n", OUTPUT_FILE); 596 exit (1); 597 } 598 fprintf (tf, "#ifndef __crc32cr_table_h__\n"); 599 fprintf (tf, "#define __crc32cr_table_h__\n\n"); 600 fprintf (tf, "#define CRC32C_POLY 0x%08lX\n", CRC32C_POLY); 601 fprintf (tf, "#define CRC32C(c,d) (c=(c>>8)^crc_c[(c^(d))&0xFF])\n"); 602 fprintf (tf, "\nunsigned long crc_c[256] =\n{\n"); 603 for (i = 0; i < 256; i++){ 604 fprintf (tf, "0x%08lXL, ", build_crc_table (i)); 605 if ((i & 3) == 3) 606 fprintf (tf, "\n"); 607 } 608 fprintf (tf, "};\n\n#endif\n"); 610 if (fclose (tf) != 0) 611 printf ("Unable to close <%s>." OUTPUT_FILE); 612 else 613 printf ("\nThe CRC-32c table has been written to <%s>.\n", 614 OUTPUT_FILE); 615 } 617 /* Example of crc insertion */ 619 #include "crc32cr.h" 621 unsigned long 622 generate_crc32c(unsigned char *buffer, unsigned int length) 623 { 624 unsigned int i; 625 unsigned long crc32 = ~0L; 626 unsigned long result; 627 unsigned char byte0,byte1,byte2,byte3; 629 for (i = 0; i < length; i++){ 630 CRC32C(crc32, buffer[i]); 631 } 632 result = ~crc32; 634 /* result now holds the negated polynomial remainder; 635 * since the table and algorithm is "reflected" [williams95]. 636 * That is, result has the same value as if we mapped the message 637 * to a polyomial, computed the host-bit-order polynomial 638 * remainder, performed final negation, then did an end-for-end 639 * bit-reversal. 640 * Note that a 32-bit bit-reversal is identical to four inplace 641 * 8-bit reversals followed by an end-for-end byteswap. 643 * In other words, the bytes of each bit are in the right order, 644 * but the bytes have been byteswapped. So we now do an explicit 645 * byteswap. On a little-endian machine, this byteswap and 646 * the final ntohl cancel out and could be elided. 647 */ 648 byte0 = result & 0xff; 649 byte1 = (result>>8) & 0xff; 650 byte2 = (result>>16) & 0xff; 651 byte3 = (result>>24) & 0xff; 653 crc32 = ((byte0 << 24) | 654 (byte1 << 16) | 655 (byte2 << 8) | 656 byte3); 657 return ( crc32 ); 658 } 660 int 661 insert_crc32(unsigned char *buffer, unsigned int length) 662 { 663 SCTP_message *message; 664 unsigned long crc32; 665 message = (SCTP_message *) buffer; 666 message->common_header.checksum = 0L; 667 crc32 = generate_crc32c(buffer,length); 668 /* and insert it into the message */ 669 message->common_header.checksum = htonl(crc32); 670 return 1; 671 } 673 /* Example of crc validation */ 674 /* Test of 32 zeros should yield 0x756EC955 placed in network order */ 675 /* 13 zeros followed by byte values of 1 - 0x1f should yield 676 /* 0x5b988D47 */ 678 int 679 validate_crc32(unsigned char *buffer, unsigned int length) 680 { 681 SCTP_message *message; 682 unsigned int i; 683 unsigned long original_crc32; 684 unsigned long crc32 = ~0L; 686 /* save and zero checksum */ 687 message = (SCTP_message *) buffer; 688 original_crc32 = ntohl(message->common_header.checksum); 689 message->common_header.checksum = 0L; 690 crc32 = generate_crc32c(buffer,length); 691 return ((original_crc32 == crc32)? 1 : -1); 692 } 694 Full Copyright Statement 696 Copyright (C) The Internet Society (2001). All Rights Reserved. 698 This document and translations of it may be copied and furnished to 699 others, and derivative works that comment on or otherwise explain it or 700 assist in its implementation may be prepared, copied, published and 701 distributed, in whole or in part, without restriction of any kind, 702 provided that the above copyright notice and this paragraph are included 703 on all such copies and derivative works. However, this document itself 704 may not be modified in any way, such as by removing the copyright notice 705 or references to the Internet Society or other Internet organizations, 706 except as needed for the purpose of developing Internet standards in 707 which case the procedures for copyrights defined in the Internet 708 Standards process must be followed, or as required to translate it into 709 languages other than English. 711 The limited permissions granted above are perpetual and will not be 712 revoked by the Internet Society or its successors or assigns. 714 This document and the information contained herein is provided on an "AS 715 IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK 716 FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT 717 LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT 718 INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR 719 FITNESS FOR A PARTICULAR PURPOSE. 721 Funding for the RFC Editor function is currently provided by the 722 Internet Society.