In article <(E-Mail Removed)>

CptDondo <(E-Mail Removed)> wrote:

>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_flag,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&0x0001;
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.