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