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