In article <12************ *@corp.supernew s.com>
CptDondo <ya*@NsOeSiPnAe Mr.comwrote:
>This bit of code would fail occasionally until I changed the int to
unsigned int; now I see I really need to change it uint16_t..... I am
cross-compiling so I am striving for portability across multiple platforms.
Except for the use of "int n" (which may or may not be a problem
depending on the range supplied for n), and the question of whether
"byte" is a name for an unsigned type -- if it is "unsigned char"
things should be fine -- this code is itself fine:
>unsigned int crc(byte trame[],int n)
{
unsigned int crc,i,j,carry_f lag,a;
crc=0xffff;
This line might be better-written "crc = 0xffffU;", but it should
assign 65535U to crc in every case. (UINT_MAX is required to be
at least 65535U, although it may be greater.)
for (i=0;i<n;i++)
As someone else pointed out, comparing "unsigned int i" with
(signed) int n is not always wise. Fortunately, in this case,
the one "unsigned" will override so that the overall comparison
will be the same as:
i < (unsigned int)n
which will "do the right thing" in most cases. It would be better
to give both i and n the size_t type, though.
{
crc=crc^trame[i];
As long as both crc and trame[i] are bounded by the range 0..65535,
the result in "crc" at this point will also be in that range. The
initial value of "crc" is 65535 and hence is so bounded; we need
only verify that the rest of the loop maintains this invariant.
for (j=0;j<8;j++)
{
a=crc;
carry_flag=a&0x 0001;
Here "a" will be in the same range that "crc" had earlier, and
carry_flag will be either 0 or 1 depending on the least significant
bit of "a" (which is the same as the LSbit of "crc").
crc=crc>>1;
At this point, crc should be in the range [0..32767]. (The LSbit
has been discarded and the remaining value divided by 2.)
if (carry_flag==1)
crc=crc^0xa001;
}
Since "carry_flag " is either 0 or 1 (depending on the low bit of
"crc" before shifting, as saved in "a", which is not actually
needed -- carry_flag could be set based on "crc" instead of "a"),
the test for "== 1" is unnecessary but harmless. Since crc was
in the range 0..32767 [0..0x7fff], the result of the xor is in
the range [0..0xffff] or [0..65535].
Hence, the loop maintains the invariant that crc is in [0..65535],
and a type that holds at least that range (like "unsigned int")
always suffices.
}
trame[n+1]=crc>>8;
trame[n]=crc&255;
return crc;
}
This suggests that "byte" is a typedef-name for "unsigned char",
so my earlier guess that trame[i] is in the range [0..255] seems
reasonable.
It seems a bit odd to store the crc of the input data in the input
data, as well as returning it. The routine would be more generally
useful if the crc were not stored anywhere but just returned.
Alternatively, the output region could be given as a parameter.
(For source compatibility one might then:
#define COMPAT_CRC(arr, size) new_crc(arr, size, (arr) + (size))
and change calls to crc(x,y) to COMPAT_CRC(x,y) , verifying that
the parameters are OK when macro-ized like this.)
(The routine can be sped up enormously by performing the CRC
calculations one 8-bit-unit at a time, with a 256-entry table, but
that is a separate issue. This also makes the code somewhat harder
to eyeball as "obviously correct" -- here, only the magic xor value
need be inspected to make sure it has the right powers of two in
it.)
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: forget about it
http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.
