idnits 2.17.1 draft-ietf-tsvwg-sctpcsum-04.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 79 instances of too long lines in the document, the longest one being 5 characters in excess of 72. ** There are 15 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 22, 2002) is 8070 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 345, but not defined ** Obsolete undefined reference: RFC 2960 (Obsoleted by RFC 4960) == Missing Reference: 'RFC2119' is mentioned on line 342, but not defined == Missing Reference: 'ITU32' is mentioned on line 350, but not defined == Missing Reference: 'Peterson 72' is mentioned on line 302, but not defined == Missing Reference: 'Castagnoli93' is mentioned on line 330, but not defined == Missing Reference: 'Blahut 94' is mentioned on line 408, but not defined == Missing Reference: 'McKee75' is mentioned on line 334, but not defined == Missing Reference: 'RFC2026' is mentioned on line 339, but not defined == Missing Reference: 'Prange 57' is mentioned on line 406, but not defined -- Looks like a reference, but probably isn't: '256' on line 621 == Unused Reference: 'Blahut 1994' is defined on line 363, but no explicit reference was found in the text == Unused Reference: 'Prange 1957' is defined on line 378, but no explicit reference was found in the text == Unused Reference: 'Peterson 1972' is defined on line 382, but no explicit reference was found in the text == Unused Reference: 'Sprachman2001' is defined on line 438, 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 22, 2002 10 SCTP Checksum Change 11 draft-ietf-tsvwg-sctpcsum-04.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......................................6 41 4 IANA Considerations..........................................6 42 5 Acknowledgments .............................................6 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 1s 186 and the CRC is computed with an algorithm that 187 simultaneously multiplies by x^32 and divides by the CRC 188 polynomial. 189 - the polynomial is multiplied by x^32 and divided by G(x), 190 the generator polynomial, producing a remainder R(x) of degree 191 less than or equal to 31. 192 - the coefficients of R(x) are considered a 32 bit sequence. 193 - the bit sequence is complemented. The resulting is the CRC 194 polynomial. 195 - The CRC polynomial is mapped back into SCTP transport-level 196 bytes. Coefficient of x^31 gives the value of bit 0 of 197 SCTP byte 0, the coefficient of x^24 gives the value of 198 bit 7 of byte 0. the coefficient of x^7 gives bit 0 of 199 bit 0 and the coefficient of x^0 0 gives bit 7 of byte 3. 200 The resulting four-byte transport-level sequence is the 201 32-bit SCTP checksum value. 203 IMPLEMENTATION NOTE: Standards documents, textbooks, and vendor 204 literature on CRCs often follow an alternative formulation, in which 205 the register used to hold the remainder of the long-division 206 algorithm is initialized to zero rather than all-1s, and instead the 207 first 32 bits of the message are complemented. The long-division 208 algorithm used in our formulation is specified such that the the 209 initial multiplication by 2^32 and the long-division, into one 210 simultaneous operation. For such algorithms, and for messages longer 211 than 64 bits, the two specifications are precisely equivalent. That 212 equivalence is the intent of this document. Implementors of SCTP are 213 warned that both specifications are to be found in the literature, 214 sometimes with no restriction on the long-division algorithm. 215 The choice of formulation in this document is to permit non-SCTP 216 usage, where the same CRC algorithm may be used to protect messages 217 shorter than 64 bits. 219 When an SCTP packet is transmitted, the sender MUST perform this 220 checksum procedure, using the preceding CRC computation: 222 1) Fill in the proper Verification Tag in the SCTP common header and 223 initialize the Checksum field to 0's. 225 2) Calculate the CRC-32c of the whole packet, including the SCTP common 226 header and all the chunks. 228 3) Put the resultant 32-bit SCTP checksum value into the Checksum field 229 in the common header, and leave the rest of the bits unchanged. 231 When an SCTP packet is received, the receiver MUST first perform the 232 following: 234 1) Store the received CRC-32c value, 236 2) Replace the 32 bits of the Checksum field in the received SCTP packet 237 with all '0's and calculate the SCTP CRC-32c checksum value of 238 the whole received packet. And, 240 3) Verify that the calculated CRC-32c value is the same as the received 241 CRC-32c value. If not, the receiver MUST treat the packet as an 242 invalid SCTP packet. 244 The default procedure for handling invalid SCTP packets is to silently 245 discard them. 247 If SCTP could follow link level CRC use, the CRC would be computed 248 over the link-level bit-stream. The first bit on the link 249 mapping to the highest-order coefficient, and so on down to the 250 last link-level bit as the lowest-order coefficient. The CRC value 251 would be transmitted immediately after the input message as a link-level 252 `trailer'. The resulting link-level bit-stream would be 253 (M(X)x) * x^32) + (M(X)*x^32))/ G(x), which is divisible by G(X). 254 There would thus be a constant CRC remainder for `good' packets. 255 However, given that implementations of RFC2960 have already 256 proliferated, the IETF discussions considered that the benefit of 257 a `trailer' CRC did not outweigh the cost of making a very large 258 change in the protocol processing. Further, packets accepted by 259 the SCTP `header' CRC are in one-to-one correspondence with 260 packets accepted by a modified procedure using a `trailer' 261 CRC value, and where the SCTP common checksum header is set to zero 262 on transmission and is received as zero. 264 There may be a computational advantage in validating the Association 265 against the Verification Tag prior to performing a checksum as 266 invalid tags will result in the same action as a bad checksum in 267 most cases. The exceptions for this technique would be INIT and some 268 SHUTDOWN-COMPLETE exchanges as well as a stale COOKIE-ECHO. These 269 special case exchanges must represent small packets and will 270 minimize the effect of the checksum calculation. 272 3 Security Considerations 274 In general, the security considerations of RFC2960 apply to 275 the protocol with the new checksum as well. 277 4 IANA Considerations 279 There are no IANA considerations required in this document. 281 5 Acknowledgments 283 The authors would like to thank the following people that have 284 provided comments and input on the checksum issue: 286 Mark Adler, Ran Atkinson, Stephen Bailey, David Black, Scott 287 Bradner, Mikael Degermark, Laurent Glaude, Klaus Gradischnig, Alf 288 Heidermark, Jacob Heitz, Gareth Kiely, David Lehmann, Allision 289 Mankin, Lyndon Ong, Craig Partridge, Vern Paxson, Kacheong Poon, 290 Michael Ramalho, David Reed, Ian Rytina, Hanns Juergen Schwarzbauer, 291 Chip Sharp, Bill Sommerfeld, Michael Tuexen, Jim Williams, Jim Wendt, 292 Michael Welzl, Jonathan Wood, Lloyd Wood, Qiaobing Xie, La Monte 293 Yarroll. 295 Special thanks to Dafna Scheinwald, Julian Satran Pat Thaler, Matt 296 Wakeley, and Vince Cavanna, for selection criteria of polynomials and 297 examination of CRC polynomials, particularly CRC-32c [Castagnoli93]. 299 Special thanks to Mr. Ross Williams and his document [Williams93]. 300 This non-formal perspective on software aspects of CRCs furthered 301 understanding of authors previously unfamiliar with CRC computation. 302 More formal treatments of [Blahut 94] or [Peterson 72], was 303 also essential. 305 6 Authors' Addresses 307 Randall R. Stewart 308 24 Burning Bush Trail. 309 Crystal Lake, IL 60012 310 USA 312 EMail: rrs@cisco.com 314 Jonathan Stone 315 Room 446, Mail code 9040 316 Gates building 4A 317 Stanford, Ca 94305 319 EMail: jonathan@dsg.stanford.edu 321 Douglas Otis 322 800 E. Middlefield 323 Mountain View, CA 94043 324 USA 326 Email dotis@sanlight.net 328 7 References 330 [Castagnoli93] G. Castagnoli, S. Braeuer and M. Herrman, 331 "Optimization of Cyclic Redundancy-Check Codes with 24 and 32 Parity 332 Bits", IEEE Transactions on Communications, Vol. 41, No. 6, June 1993 334 [McKee75] H. McKee, "Improved {CRC} techniques detects erroneous 335 leading and trailing 0's in transmitted data blocks", 336 Computer Design Volume 14 Number 10 Pages 102-4,106, 337 October 1975 339 [RFC2026] Bradner, S., "The Internet Standards Process -- Revision 340 3", BCP 9, RFC 2026, October 1996. 342 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 343 Requirement Levels", BCP 14, RFC 2119, March 1997. 345 [RFC2960] R. R. Stewart, Q. Xie, K. Morneault, C. Sharp, 346 H. J. Schwarzbauer, T. Taylor, I. Rytina, M. Kalla, L. Zhang, 347 and, V. Paxson, "Stream Control Transmission Protocol," RFC 348 2960, October 2000. 350 [ITU32] ITU-T Recommendation V.42, "Error-correcting 351 procedures for DCEs using asynchronous-to-synchronous 352 conversion", section 8.1.1.6.2, October 1996. 354 7.1 Informative References 356 [STONE] Stone, J., "Checksums in the Internet", Doctoral 357 dissertation - August 2001 359 [Williams93] Williams, R., "A PAINLESS GUIDE TO CRC ERROR DETECTION 360 ALGORITHMS" - Internet publication, August 1993, 361 http://www.geocities.com/SiliconValley/Pines/8659/crc.htm. 363 [Blahut 1994], R.E. Blahut, Theory and Practice of Error Control 364 Codes, Addison-Wesley, 1994. 366 [Easics 2001]. http://www.easics.be/webtools/crctool. Online tools 367 for synthesis of CRC Verilog and VHDL. 369 [Feldmeier 95], David C. Feldmeier, Fast software implementation of 370 error detection codes, IEEE Transactions on Networking, vol 3 no 6, 371 pp 640-651, December, 1995. 373 [Glaise 1997] R. J. Glaise, A two-step computation of cyclic 374 redundancy code CRC-32 for ATM networks, IBM Journal of Research and 375 Development} vol 41 no 6, 1997. URL= 376 http://www.research.ibm.com/journal/rd/416/glaise.html. 378 [Prange 1957], E. Prange, Cyclic Error-Correcting codes in two 379 symbols, Technical report AFCRC-TN-57-103, Air Force Cambridge 380 Research Center, Cambridge, Mass. 1957. 382 [Peterson 1972], W. W. Peterson and E.J Weldon, Error Correcting 383 Codes, 2nd. edition, MIT Press, Cambridge, Massachusetts. 385 [Shie2001] Ming-Der Shieh et. al, A Systematic Approach for Parallel 386 CRC Computations. Journal of Information Science and Engineering, 387 Vol.17 No.3, pp.445-461 389 [Sprachman2001] Michael Sprachman, Automatic Generation of Parallel 390 CRC Circuits, IEEE Design & Test May-June 2001 392 8 Appendix 394 This appendix is for information only and is NOT part of the 395 standard. 397 The anticipated deployment of SCTP ranges over several orders of 398 magnitude of link speed: from cellular-power telephony devices at 399 tens of kilobits, to local links at tens of gigabits. Implementors 400 of SCTP should consider their link speed and choose, from the wide 401 range of CRC implementations, one which matches their own design 402 point for size, cost, and throughput. Many techniques for computing 403 CRCs are known. This Appendix surveys just a few, to give a feel for 404 the range of techniques available. 406 CRCs are derived from early work by Prange in the 1950s [Prange 57]. 407 The theory underlying CRCs and choice of generator polynomial can be 408 introduced by either via the theory of Galois fields [Blahut 94] 409 or as ideals of an algebra over cyclic codes [cite Peterson 72]. 411 One of the simplest techniques is direct bit-serial hardware 412 implementations, using the generator polynomial as the taps of a 413 linear feedback shift register (LSFR). LSFR computation follows 414 directly from the mathematics, and is generally attributed to Prange. 415 Tools exist which, a CRC generator polynomial, will produce 416 synthesizable Verilog code for CRC hardware [Easics 2001]. 418 Since LSFRs do not scale well in speed, a variety of other 419 techniques have been explored. One technique exploits the fact that 420 the divisor of the polynomial long-division, G, is known in 421 advance. It is thus possible to pre-compute lookup tables giving the 422 polynomial remainder of multiple input bits --- typically 2, 4, or 8 423 bits of input at a time. This technique can be used either in 424 software or in hardware. Software to compute lookup tables yielding 425 2, 4, or 8 bits of result is freely available. [Williams93] 427 For multi-gigabit links, the above techniques may still not be fast 428 enough. One technique for computing CRCS at OC-48 rates is 429 `two-stage' CRC computation [Glaise 1997]. Here, some multiple 430 of G(x), G(x)H(x), is chosen so as to minimize the number of nonzero 431 coefficients, or weight, of the product G(x)H(x). The low weight of 432 the product polynomial makes it susceptible to efficient hardware 433 divide-by-constant implementations. This first stage gives M(x) / 434 (G(x)H(x)) as its result. The second stage then divides the result 435 of the first stage by H(x), yielding (M(x) / (G(x)H(x))) / H(x). If 436 H(x) is also relatively prime to G(x), this gives M(x)/G(x). 437 Further developments on this approach can be found in [Shie2001] and 438 [Sprachman2001]. 440 The literature also includes a variety of software CRC 441 implementations. One approach is to use carefully-tuned assembly 442 code for direct polynomial division. [Feldmeier 95] reports that for 443 low-weight polynomials, tuned polynomial arithmetic gives higher 444 throughput than table-lookup algorithms. Even within table-lookup 445 algorithms, the size of the table can be tuned, either for total 446 cache footprint, or (for space-restricted environments) to minimize 447 total size. 449 Implementors should keep in mind the bit ordering described in 450 Section 2: the ordering of bits within bytes for computing CRCs in 451 SCTP is the least significant bit of each byte is the 452 most-significant polynomial coefficient(and vice-versa). This 453 `reflected' SCTP CRC bit ordering matches on-the-wire bit order for 454 Ethernet and other serial media, but is the reverse of traditional 455 Internet bit ordering. 457 One technique to accommodate this bit-reversal can be explained as 458 follows: sketch out a hardware implementation assuming the bits are 459 in CRC bit order; then perform a left-to-right inversion (mirror 460 image) on the entire algorithm. (We defer for a moment the issue of 461 byte order within words.) Then compute that "mirror image" in 462 software. The CRC from the ``mirror image'' algorithm will be the 463 bit-reversal of a correct hardware implementation. When the 464 link-level media sends each byte, the byte is sent in the reverse of 465 the host CPU bit-order. Serialization of each byte of the 466 ``reflected'' CRC value re-reverses the bit order, so in the end, 467 each byte will be transmitted on-the-wire in the specified bit 468 order. 470 The following non-normative sample code is taken from an open-source 471 CRC generator [Williams93] using the ``mirroring'' technique 472 and yielding a lookup table for SCTP CRC32-c with 256 entries, each 473 32 bits wide. While neither especially slow nor especially fast, as 474 software table-lookup CRCs go, it has the advantage of working on 475 both big-endian and little-endian CPUs, using the same (host-order) 476 lookup tables, and using only the pre-defined ntohl() and htonl() 477 operations. The code is somewhat modified from [Williams93], to 478 ensure portability between big-endian and little-endian 479 architectures. (Note that if the byte endian-ness of the target 480 architecture is known to be little-endian the final bit-reversal and 481 byte-reversal steps can be folded into a single operation.) 482 /*************************************************************/ 483 /* Note Definition for Ross Williams table generator would */ 484 /* be: TB_WIDTH=4, TB_POLLY=0x1EDC6F41, TB_REVER=TRUE */ 485 /* For Mr. Williams direct calculation code use the settings */ 486 /* cm_width=32, cm_poly=0x1EDC6F41, cm_init=0xFFFFFFFF, */ 487 /* cm_refin=TRUE, cm_refot=TRUE, cm_xorort=0x00000000 */ 488 /*************************************************************/ 490 /* Example of the crc table file */ 491 #ifndef __crc32cr_table_h__ 492 #define __crc32cr_table_h__ 494 #define CRC32C_POLY 0x1EDC6F41 495 #define CRC32C(c,d) (c=(c>>8)^crc_c[(c^(d))&0xFF]) 497 unsigned long crc_c[256] = 498 { 499 0x00000000L, 0xF26B8303L, 0xE13B70F7L, 0x1350F3F4L, 500 0xC79A971FL, 0x35F1141CL, 0x26A1E7E8L, 0xD4CA64EBL, 501 0x8AD958CFL, 0x78B2DBCCL, 0x6BE22838L, 0x9989AB3BL, 502 0x4D43CFD0L, 0xBF284CD3L, 0xAC78BF27L, 0x5E133C24L, 503 0x105EC76FL, 0xE235446CL, 0xF165B798L, 0x030E349BL, 504 0xD7C45070L, 0x25AFD373L, 0x36FF2087L, 0xC494A384L, 505 0x9A879FA0L, 0x68EC1CA3L, 0x7BBCEF57L, 0x89D76C54L, 506 0x5D1D08BFL, 0xAF768BBCL, 0xBC267848L, 0x4E4DFB4BL, 507 0x20BD8EDEL, 0xD2D60DDDL, 0xC186FE29L, 0x33ED7D2AL, 508 0xE72719C1L, 0x154C9AC2L, 0x061C6936L, 0xF477EA35L, 509 0xAA64D611L, 0x580F5512L, 0x4B5FA6E6L, 0xB93425E5L, 510 0x6DFE410EL, 0x9F95C20DL, 0x8CC531F9L, 0x7EAEB2FAL, 511 0x30E349B1L, 0xC288CAB2L, 0xD1D83946L, 0x23B3BA45L, 512 0xF779DEAEL, 0x05125DADL, 0x1642AE59L, 0xE4292D5AL, 513 0xBA3A117EL, 0x4851927DL, 0x5B016189L, 0xA96AE28AL, 514 0x7DA08661L, 0x8FCB0562L, 0x9C9BF696L, 0x6EF07595L, 515 0x417B1DBCL, 0xB3109EBFL, 0xA0406D4BL, 0x522BEE48L, 516 0x86E18AA3L, 0x748A09A0L, 0x67DAFA54L, 0x95B17957L, 517 0xCBA24573L, 0x39C9C670L, 0x2A993584L, 0xD8F2B687L, 518 0x0C38D26CL, 0xFE53516FL, 0xED03A29BL, 0x1F682198L, 519 0x5125DAD3L, 0xA34E59D0L, 0xB01EAA24L, 0x42752927L, 520 0x96BF4DCCL, 0x64D4CECFL, 0x77843D3BL, 0x85EFBE38L, 521 0xDBFC821CL, 0x2997011FL, 0x3AC7F2EBL, 0xC8AC71E8L, 522 0x1C661503L, 0xEE0D9600L, 0xFD5D65F4L, 0x0F36E6F7L, 523 0x61C69362L, 0x93AD1061L, 0x80FDE395L, 0x72966096L, 524 0xA65C047DL, 0x5437877EL, 0x4767748AL, 0xB50CF789L, 525 0xEB1FCBADL, 0x197448AEL, 0x0A24BB5AL, 0xF84F3859L, 526 0x2C855CB2L, 0xDEEEDFB1L, 0xCDBE2C45L, 0x3FD5AF46L, 527 0x7198540DL, 0x83F3D70EL, 0x90A324FAL, 0x62C8A7F9L, 528 0xB602C312L, 0x44694011L, 0x5739B3E5L, 0xA55230E6L, 529 0xFB410CC2L, 0x092A8FC1L, 0x1A7A7C35L, 0xE811FF36L, 530 0x3CDB9BDDL, 0xCEB018DEL, 0xDDE0EB2AL, 0x2F8B6829L, 531 0x82F63B78L, 0x709DB87BL, 0x63CD4B8FL, 0x91A6C88CL, 532 0x456CAC67L, 0xB7072F64L, 0xA457DC90L, 0x563C5F93L, 533 0x082F63B7L, 0xFA44E0B4L, 0xE9141340L, 0x1B7F9043L, 534 0xCFB5F4A8L, 0x3DDE77ABL, 0x2E8E845FL, 0xDCE5075CL, 535 0x92A8FC17L, 0x60C37F14L, 0x73938CE0L, 0x81F80FE3L, 536 0x55326B08L, 0xA759E80BL, 0xB4091BFFL, 0x466298FCL, 537 0x1871A4D8L, 0xEA1A27DBL, 0xF94AD42FL, 0x0B21572CL, 538 0xDFEB33C7L, 0x2D80B0C4L, 0x3ED04330L, 0xCCBBC033L, 539 0xA24BB5A6L, 0x502036A5L, 0x4370C551L, 0xB11B4652L, 540 0x65D122B9L, 0x97BAA1BAL, 0x84EA524EL, 0x7681D14DL, 541 0x2892ED69L, 0xDAF96E6AL, 0xC9A99D9EL, 0x3BC21E9DL, 542 0xEF087A76L, 0x1D63F975L, 0x0E330A81L, 0xFC588982L, 543 0xB21572C9L, 0x407EF1CAL, 0x532E023EL, 0xA145813DL, 544 0x758FE5D6L, 0x87E466D5L, 0x94B49521L, 0x66DF1622L, 545 0x38CC2A06L, 0xCAA7A905L, 0xD9F75AF1L, 0x2B9CD9F2L, 546 0xFF56BD19L, 0x0D3D3E1AL, 0x1E6DCDEEL, 0xEC064EEDL, 547 0xC38D26C4L, 0x31E6A5C7L, 0x22B65633L, 0xD0DDD530L, 548 0x0417B1DBL, 0xF67C32D8L, 0xE52CC12CL, 0x1747422FL, 549 0x49547E0BL, 0xBB3FFD08L, 0xA86F0EFCL, 0x5A048DFFL, 550 0x8ECEE914L, 0x7CA56A17L, 0x6FF599E3L, 0x9D9E1AE0L, 551 0xD3D3E1ABL, 0x21B862A8L, 0x32E8915CL, 0xC083125FL, 552 0x144976B4L, 0xE622F5B7L, 0xF5720643L, 0x07198540L, 553 0x590AB964L, 0xAB613A67L, 0xB831C993L, 0x4A5A4A90L, 554 0x9E902E7BL, 0x6CFBAD78L, 0x7FAB5E8CL, 0x8DC0DD8FL, 555 0xE330A81AL, 0x115B2B19L, 0x020BD8EDL, 0xF0605BEEL, 556 0x24AA3F05L, 0xD6C1BC06L, 0xC5914FF2L, 0x37FACCF1L, 557 0x69E9F0D5L, 0x9B8273D6L, 0x88D28022L, 0x7AB90321L, 558 0xAE7367CAL, 0x5C18E4C9L, 0x4F48173DL, 0xBD23943EL, 559 0xF36E6F75L, 0x0105EC76L, 0x12551F82L, 0xE03E9C81L, 560 0x34F4F86AL, 0xC69F7B69L, 0xD5CF889DL, 0x27A40B9EL, 561 0x79B737BAL, 0x8BDCB4B9L, 0x988C474DL, 0x6AE7C44EL, 562 0xBE2DA0A5L, 0x4C4623A6L, 0x5F16D052L, 0xAD7D5351L, 563 }; 565 #endif 567 /* Example of table build routine */ 569 #include 570 #include 572 #define OUTPUT_FILE "crc32cr.h" 573 #define CRC32C_POLY 0x1EDC6F41L 574 FILE *tf; 576 unsigned long 577 reflect_32 (unsigned long b) 578 { 579 int i; 580 unsigned long rw = 0L; 582 for (i = 0; i < 32; i++){ 583 if (b & 1) 584 rw |= 1 << (31 - i); 585 b >>= 1; 586 } 587 return (rw); 589 } 591 unsigned long 592 build_crc_table (int index) 593 { 594 int i; 595 unsigned long rb; 597 rb = reflect_32 (index); 599 for (i = 0; i < 8; i++){ 600 if (rb & 0x80000000L) 601 rb = (rb << 1) ^ CRC32C_POLY; 602 else 603 rb <<= 1; 604 } 605 return (reflect_32 (rb)); 606 } 608 main () 609 { 610 int i; 612 printf ("\nGenerating CRC-32c table file <%s>\n", OUTPUT_FILE); 613 if ((tf = fopen (OUTPUT_FILE, "w")) == NULL){ 614 printf ("Unable to open %s\n", OUTPUT_FILE); 615 exit (1); 616 } 617 fprintf (tf, "#ifndef __crc32cr_table_h__\n"); 618 fprintf (tf, "#define __crc32cr_table_h__\n\n"); 619 fprintf (tf, "#define CRC32C_POLY 0x%08lX\n", CRC32C_POLY); 620 fprintf (tf, "#define CRC32C(c,d) (c=(c>>8)^crc_c[(c^(d))&0xFF])\n"); 621 fprintf (tf, "\nunsigned long crc_c[256] =\n{\n"); 622 for (i = 0; i < 256; i++){ 623 fprintf (tf, "0x%08lXL, ", build_crc_table (i)); 624 if ((i & 3) == 3) 625 fprintf (tf, "\n"); 626 } 627 fprintf (tf, "};\n\n#endif\n"); 629 if (fclose (tf) != 0) 630 printf ("Unable to close <%s>." OUTPUT_FILE); 631 else 632 printf ("\nThe CRC-32c table has been written to <%s>.\n", 633 OUTPUT_FILE); 634 } 636 /* Example of crc insertion */ 638 #include "crc32cr.h" 640 unsigned long 641 generate_crc32c(unsigned char *buffer, unsigned int length) 642 { 643 unsigned int i; 644 unsigned long crc32 = ~0L; 645 unsigned long result; 646 unsigned char byte0,byte1,byte2,byte3; 648 for (i = 0; i < length; i++){ 649 CRC32C(crc32, buffer[i]); 650 } 651 result = ~crc32; 653 /* result now holds the negated polynomial remainder; 654 * since the table and algorithm is "reflected" [williams95]. 655 * That is, result has the same value as if we mapped the message 656 * to a polynomial, computed the host-bit-order polynomial 657 * remainder, performed final negation, then did an end-for-end 658 * bit-reversal. 659 * Note that a 32-bit bit-reversal is identical to four inplace 660 * 8-bit reversals followed by an end-for-end byteswap. 661 * In other words, the bytes of each bit are in the right order, 662 * but the bytes have been byteswapped. So we now do an explicit 663 * byteswap. On a little-endian machine, this byteswap and 664 * the final ntohl cancel out and could be elided. 665 */ 666 byte0 = result & 0xff; 667 byte1 = (result>>8) & 0xff; 668 byte2 = (result>>16) & 0xff; 669 byte3 = (result>>24) & 0xff; 671 crc32 = ((byte0 << 24) | 672 (byte1 << 16) | 673 (byte2 << 8) | 674 byte3); 675 return ( crc32 ); 676 } 678 int 679 insert_crc32(unsigned char *buffer, unsigned int length) 680 { 681 SCTP_message *message; 682 unsigned long crc32; 683 message = (SCTP_message *) buffer; 684 message->common_header.checksum = 0L; 685 crc32 = generate_crc32c(buffer,length); 686 /* and insert it into the message */ 687 message->common_header.checksum = htonl(crc32); 688 return 1; 689 } 691 int 692 validate_crc32(unsigned char *buffer, unsigned int length) 693 { 694 SCTP_message *message; 695 unsigned int i; 696 unsigned long original_crc32; 697 unsigned long crc32 = ~0L; 699 /* save and zero checksum */ 700 message = (SCTP_message *) buffer; 701 original_crc32 = ntohl(message->common_header.checksum); 702 message->common_header.checksum = 0L; 703 crc32 = generate_crc32c(buffer,length); 704 return ((original_crc32 == crc32)? 1 : -1); 705 } 707 Full Copyright Statement 709 Copyright (C) The Internet Society (2001). All Rights Reserved. 711 This document and translations of it may be copied and furnished to 712 others, and derivative works that comment on or otherwise explain it or 713 assist in its implementation may be prepared, copied, published and 714 distributed, in whole or in part, without restriction of any kind, 715 provided that the above copyright notice and this paragraph are included 716 on all such copies and derivative works. However, this document itself 717 may not be modified in any way, such as by removing the copyright notice 718 or references to the Internet Society or other Internet organizations, 719 except as needed for the purpose of developing Internet standards in 720 which case the procedures for copyrights defined in the Internet 721 Standards process must be followed, or as required to translate it into 722 languages other than English. 724 The limited permissions granted above are perpetual and will not be 725 revoked by the Internet Society or its successors or assigns. 727 This document and the information contained herein is provided on an "AS 728 IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK 729 FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT 730 LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT 731 INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR 732 FITNESS FOR A PARTICULAR PURPOSE. 734 Funding for the RFC Editor function is currently provided by the 735 Internet Society.