1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
|
cksum(P) cksum(P)
NAME
cksum - write file checksums and sizes
SYNOPSIS
cksum [file ...]
DESCRIPTION
The cksum utility shall calculate and write to standard
output a cyclic redundancy check (CRC) for each input
file, and also write to standard output the number of
octets in each file. The CRC used is based on the poly-
nomial used for CRC error checking in the
ISO/IEC 8802-3:1996 standard (Ethernet).
The encoding for the CRC checksum is defined by the gen-
erating polynomial:
G(x)=x+x+x+x+x+x+x+x+x+x+x+x+x+x+1
Mathematically, the CRC value corresponding to a given
file shall be defined by the following procedure:
The n bits to be evaluated are considered to be the
coefficients of a mod 2 polynomial M( x) of degree n-1.
These n bits are the bits from the file, with the most
significant bit being the most significant bit of the
first octet of the file and the last bit being the least
significant bit of the last octet, padded with zero bits
(if necessary) to achieve an integral number of octets,
followed by one or more octets representing the length
of the file as a binary value, least significant octet
first. The smallest number of octets capable of repre-
senting this integer shall be used.
M( x) is multiplied by x (that is, shifted left 32 bits)
and divided by G( x) using mod 2 division, producing a
remainder R( x) of degree <= 31.
The coefficients of R( x) are considered to be a 32-bit
sequence.
The bit sequence is complemented and the result is the
CRC.
OPTIONS
None.
OPERANDS
The following operand shall be supported:
file A pathname of a file to be checked. If no file
operands are specified, the standard input shall
be used.
STDIN
The standard input shall be used only if no file oper-
ands are specified. See the INPUT FILES section.
INPUT FILES
The input files can be any file type.
ENVIRONMENT VARIABLES
The following environment variables shall affect the
execution of cksum:
LANG Provide a default value for the internationaliza-
tion variables that are unset or null. (See the
Base Definitions volume of IEEE Std 1003.1-2001,
Section 8.2, Internationalization Variables for
the precedence of internationalization variables
used to determine the values of locale cate-
gories.)
LC_ALL If set to a non-empty string value, override the
values of all the other internationalization
variables.
LC_CTYPE
Determine the locale for the interpretation of
sequences of bytes of text data as characters
(for example, single-byte as opposed to multi-
byte characters in arguments).
LC_MESSAGES
Determine the locale that should be used to
affect the format and contents of diagnostic mes-
sages written to standard error.
NLSPATH
Determine the location of message catalogs for
the processing of LC_MESSAGES .
ASYNCHRONOUS EVENTS
Default.
STDOUT
For each file processed successfully, the cksum utility
shall write in the following format:
"%u %d %s\n", <checksum>, <# of octets>, <pathname>
If no file operand was specified, the pathname and its
leading <space> shall be omitted.
STDERR
The standard error shall be used only for diagnostic
messages.
OUTPUT FILES
None.
EXTENDED DESCRIPTION
None.
EXIT STATUS
The following exit values shall be returned:
0 All files were processed successfully.
>0 An error occurred.
CONSEQUENCES OF ERRORS
Default.
The following sections are informative.
APPLICATION USAGE
The cksum utility is typically used to quickly compare a
suspect file against a trusted version of the same, such
as to ensure that files transmitted over noisy media
arrive intact. However, this comparison cannot be con-
sidered cryptographically secure. The chances of a dam-
aged file producing the same CRC as the original are
small; deliberate deception is difficult, but probably
not impossible.
Although input files to cksum can be any type, the
results need not be what would be expected on character
special device files or on file types not described by
the System Interfaces volume of IEEE Std 1003.1-2001.
Since this volume of IEEE Std 1003.1-2001 does not spec-
ify the block size used when doing input, checksums of
character special files need not process all of the data
in those files.
The algorithm is expressed in terms of a bitstream
divided into octets. If a file is transmitted between
two systems and undergoes any data transformation (such
as changing little-endian byte ordering to big-endian),
identical CRC values cannot be expected. Implementations
performing such transformations may extend cksum to han-
dle such situations.
EXAMPLES
None.
RATIONALE
The following C-language program can be used as a model
to describe the algorithm. It assumes that a char is one
octet. It also assumes that the entire file is avail-
able for one pass through the function. This was done
for simplicity in demonstrating the algorithm, rather
than as an implementation model.
static unsigned long crctab[] = {
0x00000000,
0x04c11db7, 0x09823b6e, 0x0d4326d9, 0x130476dc, 0x17c56b6b,
0x1a864db2, 0x1e475005, 0x2608edb8, 0x22c9f00f, 0x2f8ad6d6,
0x2b4bcb61, 0x350c9b64, 0x31cd86d3, 0x3c8ea00a, 0x384fbdbd,
0x4c11db70, 0x48d0c6c7, 0x4593e01e, 0x4152fda9, 0x5f15adac,
0x5bd4b01b, 0x569796c2, 0x52568b75, 0x6a1936c8, 0x6ed82b7f,
0x639b0da6, 0x675a1011, 0x791d4014, 0x7ddc5da3, 0x709f7b7a,
0x745e66cd, 0x9823b6e0, 0x9ce2ab57, 0x91a18d8e, 0x95609039,
0x8b27c03c, 0x8fe6dd8b, 0x82a5fb52, 0x8664e6e5, 0xbe2b5b58,
0xbaea46ef, 0xb7a96036, 0xb3687d81, 0xad2f2d84, 0xa9ee3033,
0xa4ad16ea, 0xa06c0b5d, 0xd4326d90, 0xd0f37027, 0xddb056fe,
0xd9714b49, 0xc7361b4c, 0xc3f706fb, 0xceb42022, 0xca753d95,
0xf23a8028, 0xf6fb9d9f, 0xfbb8bb46, 0xff79a6f1, 0xe13ef6f4,
0xe5ffeb43, 0xe8bccd9a, 0xec7dd02d, 0x34867077, 0x30476dc0,
0x3d044b19, 0x39c556ae, 0x278206ab, 0x23431b1c, 0x2e003dc5,
0x2ac12072, 0x128e9dcf, 0x164f8078, 0x1b0ca6a1, 0x1fcdbb16,
0x018aeb13, 0x054bf6a4, 0x0808d07d, 0x0cc9cdca, 0x7897ab07,
0x7c56b6b0, 0x71159069, 0x75d48dde, 0x6b93dddb, 0x6f52c06c,
0x6211e6b5, 0x66d0fb02, 0x5e9f46bf, 0x5a5e5b08, 0x571d7dd1,
0x53dc6066, 0x4d9b3063, 0x495a2dd4, 0x44190b0d, 0x40d816ba,
0xaca5c697, 0xa864db20, 0xa527fdf9, 0xa1e6e04e, 0xbfa1b04b,
0xbb60adfc, 0xb6238b25, 0xb2e29692, 0x8aad2b2f, 0x8e6c3698,
0x832f1041, 0x87ee0df6, 0x99a95df3, 0x9d684044, 0x902b669d,
0x94ea7b2a, 0xe0b41de7, 0xe4750050, 0xe9362689, 0xedf73b3e,
0xf3b06b3b, 0xf771768c, 0xfa325055, 0xfef34de2, 0xc6bcf05f,
0xc27dede8, 0xcf3ecb31, 0xcbffd686, 0xd5b88683, 0xd1799b34,
0xdc3abded, 0xd8fba05a, 0x690ce0ee, 0x6dcdfd59, 0x608edb80,
0x644fc637, 0x7a089632, 0x7ec98b85, 0x738aad5c, 0x774bb0eb,
0x4f040d56, 0x4bc510e1, 0x46863638, 0x42472b8f, 0x5c007b8a,
0x58c1663d, 0x558240e4, 0x51435d53, 0x251d3b9e, 0x21dc2629,
0x2c9f00f0, 0x285e1d47, 0x36194d42, 0x32d850f5, 0x3f9b762c,
0x3b5a6b9b, 0x0315d626, 0x07d4cb91, 0x0a97ed48, 0x0e56f0ff,
0x1011a0fa, 0x14d0bd4d, 0x19939b94, 0x1d528623, 0xf12f560e,
0xf5ee4bb9, 0xf8ad6d60, 0xfc6c70d7, 0xe22b20d2, 0xe6ea3d65,
0xeba91bbc, 0xef68060b, 0xd727bbb6, 0xd3e6a601, 0xdea580d8,
0xda649d6f, 0xc423cd6a, 0xc0e2d0dd, 0xcda1f604, 0xc960ebb3,
0xbd3e8d7e, 0xb9ff90c9, 0xb4bcb610, 0xb07daba7, 0xae3afba2,
0xaafbe615, 0xa7b8c0cc, 0xa379dd7b, 0x9b3660c6, 0x9ff77d71,
0x92b45ba8, 0x9675461f, 0x8832161a, 0x8cf30bad, 0x81b02d74,
0x857130c3, 0x5d8a9099, 0x594b8d2e, 0x5408abf7, 0x50c9b640,
0x4e8ee645, 0x4a4ffbf2, 0x470cdd2b, 0x43cdc09c, 0x7b827d21,
0x7f436096, 0x7200464f, 0x76c15bf8, 0x68860bfd, 0x6c47164a,
0x61043093, 0x65c52d24, 0x119b4be9, 0x155a565e, 0x18197087,
0x1cd86d30, 0x029f3d35, 0x065e2082, 0x0b1d065b, 0x0fdc1bec,
0x3793a651, 0x3352bbe6, 0x3e119d3f, 0x3ad08088, 0x2497d08d,
0x2056cd3a, 0x2d15ebe3, 0x29d4f654, 0xc5a92679, 0xc1683bce,
0xcc2b1d17, 0xc8ea00a0, 0xd6ad50a5, 0xd26c4d12, 0xdf2f6bcb,
0xdbee767c, 0xe3a1cbc1, 0xe760d676, 0xea23f0af, 0xeee2ed18,
0xf0a5bd1d, 0xf464a0aa, 0xf9278673, 0xfde69bc4, 0x89b8fd09,
0x8d79e0be, 0x803ac667, 0x84fbdbd0, 0x9abc8bd5, 0x9e7d9662,
0x933eb0bb, 0x97ffad0c, 0xafb010b1, 0xab710d06, 0xa6322bdf,
0xa2f33668, 0xbcb4666d, 0xb8757bda, 0xb5365d03, 0xb1f740b4
};
unsigned long memcrc(const unsigned char *b, size_t n)
{
/* Input arguments:
* const char* b == byte sequence to checksum
* size_t n == length of sequence
*/
register unsigned i, c, s = 0;
for (i = n; i > 0; --i) {
c = (unsigned)(*b++);
s = (s << 8) ^ crctab[(s >> 24) ^ c];
}
/* Extend with the length of the string. */
while (n != 0) {
c = n & 0377;
n >>= 8;
s = (s << 8) ^ crctab[(s >> 24) ^ c];
}
return ~s;
}
The historical practice of writing the number of
"blocks" has been changed to writing the number of
octets, since the latter is not only more useful, but
also since historical implementations have not been con-
sistent in defining what a "block" meant. Octets are
used instead of bytes because bytes can differ in size
between systems.
The algorithm used was selected to increase the opera-
tional robustness of cksum. Neither the System V nor BSD
sum algorithm was selected. Since each of these was dif-
ferent and each was the default behavior on those sys-
tems, no realistic compromise was available if either
were selected-some set of historical applications would
break. Therefore, the name was changed to cksum.
Although the historical sum commands will probably con-
tinue to be provided for many years, programs designed
for portability across systems should use the new name.
The algorithm selected is based on that used by the
ISO/IEC 8802-3:1996 standard (Ethernet) for the frame
check sequence field. The algorithm used does not match
the technical definition of a checksum; the term is used
for historical reasons. The length of the file is
included in the CRC calculation because this parallels
inclusion of a length field by Ethernet in its CRC, but
also because it guards against inadvertent collisions
between files that begin with different series of zero
octets. The chance that two different files produce
identical CRCs is much greater when their lengths are
not considered. Keeping the length and the checksum of
the file itself separate would yield a slightly more
robust algorithm, but historical usage has always been
that a single number (the checksum as printed) repre-
sents the signature of the file. It was decided that
historical usage was the more important consideration.
Early proposals contained modifications to the Ethernet
algorithm that involved extracting table values whenever
an intermediate result became zero. This was demon-
strated to be less robust than the current method and
mathematically difficult to describe or justify.
The calculation used is identical to that given in
pseudo-code in the referenced Sarwate article. The
pseudo-code rendition is:
X <- 0; Y <- 0;
for i <- m -1 step -1 until 0 do
begin
T <- X(1) ^ A[i];
X(1) <- X(0); X(0) <- Y(1); Y(1) <- Y(0); Y(0) <- 0;
comment: f[T] and f'[T] denote the T-th words in the
table f and f' ;
X <- X ^ f[T]; Y <- Y ^ f'[T];
end
The pseudo-code is reproduced exactly as given; however,
note that in the case of cksum, A[i] represents a byte
of the file, the words X and Y are treated as a single
32-bit value, and the tables f and f' are a single table
containing 32-bit values.
The referenced Sarwate article also discusses generating
the table.
FUTURE DIRECTIONS
None.
SEE ALSO
None.
COPYRIGHT
Portions of this text are reprinted and reproduced in
electronic form from IEEE Std 1003.1, 2003 Edition,
Standard for Information Technology -- Portable Operat-
ing System Interface (POSIX), The Open Group Base Speci-
fications Issue 6, Copyright (C) 2001-2003 by the Insti-
tute of Electrical and Electronics Engineers, Inc and
The Open Group. In the event of any discrepancy between
this version and the original IEEE and The Open Group
Standard, the original IEEE and The Open Group Standard
is the referee document. The original Standard can be
obtained online at http://www.open-
group.org/unix/online.html .
POSIX 2003 cksum(P)
|
