|
Below are examples for computing CRC's in (Turbo) PASCAL. Although
some of the routines are written in assembler, the comments should
be sufficient for you to create the appropriate C version. Each
implementation is a bit different, trading off table size for
processor speed. The speeds below may not scale directly from
an Intel 8088 to the VAX processor.
Hint: when your C version is complete, double check it with
the VAX/VMS Lib$CRC routine.
David
Program CRC;
{
Here are some sample timing results. These were obtained using TURBO 3.0
under DOS 2.0 on a SEEQUA Chameleon. (Your mileage may vary.)
(Note that the CRC is printed to assure that all implementations
are working properly.)
The unit for the numbers in the table is approximately a 1 second.
D a t a S t r e a m L e n g t h
Routine 512 1024 2048 4096 32767
No table 0.33 0.65 1.31 2.62 20.93 CRC = -31717
Nybble table 0.10 0.18 0.38 0.76 6.03 CRC = -31717
Two Nybble tables 0.10 0.18 0.36 0.74 5.88 CRC = -31717
Byte table 0.08 0.16 0.32 0.64 5.12 CRC = -31717
Nybble string 0.03 0.05 0.09 0.18 1.50 CRC = -31717
Byte string 0.01 0.03 0.05 0.09 0.73 CRC = -31717
}
Const
max = 32767;
Type
Bytes = Array [1..max] of Byte;
Var
time : Integer Absolute $0040:$006c; { TIMER_LOW
IBM PC ROM BIOS location }
initial_clock, stop, j, i : Integer;
length : Array [1..5] of Integer;
{
Here are the four types of tables used
}
table_16 : Array [0..15] of Integer;
table_32a : Array [0..16] of Integer;
table_32b : Array [0..16] of Integer;
table_256 : Array [0 .. 255] of Integer;
CRC_value : Integer;
byte_string : Bytes;
POLY : Integer;
Procedure set_timer(count : Integer);
{
This routine sets the clock (timer) count-down value to
count. The DOS value is 0 (this is the maximum value ...
it really means 65536). This routine is used to obtain
better resolution in timing.
WARNING : The setting of count to too small a value will
HANG your system. Please study interrupts in
real time systems before using this routine.
WARNING : This routine was written to run on an IBM PC or
compatible. Disable this routine when this
program is run on other machines.
}
Begin
inline($b0/$36/ { mov al,36 }
$e6/$43/ { out 43,al }
$8b/$86/count/ { mov ax,bp[count] }
$e6/$40/ { out 40,al }
$88/$e0/ { mov al,ah }
$e6/$40); { out 40,al }
End;
Procedure simple_crc(b:byte);
{
This routine computes the CRC value bit by bit. The initial value
is assumed to be in a global variable CRC_value and the global variable
POLY contains the representation of the polynomial be used. The routine
is called for each byte. The result is placed in the global CRC_value.
}
Var
i : Integer;
Begin
CRC_value := b xor CRC_value;
For i := 1 to 8 Do
Begin
If (CRC_value and 1) = 1
then CRC_value := (CRC_value shr 1) xor POLY
else CRC_value := CRC_value shr 1;
End;
End;
Procedure generate_table_16(POLY : Integer);
{
This routine computes the remainder values of 0 through 15 divided
by the polynomial represented by POLY. These values are placed in a
table and used to compute the CRC of a block of data efficiently.
This implementation only permits polynomials up to degree 16.
}
Var
val, i, result : Integer;
Begin
For val := 0 to 15 Do
Begin
result := val;
For i := 1 to 4 Do
Begin
If (result and 1) = 1
then result := (result shr 1) xor POLY
else result := result shr 1;
End;
table_16[val] := result;
End
End;
Procedure generate_table_32(POLY : Integer);
{
This routine computes the remainder values of 0 through 15 divided
by the polynomial represented by POLY. These values are placed in two
tables and used to compute the CRC of a block of data efficiently.
This implementation only permits polynomials up to degree 16.
}
Var
val, i, result, divide : Integer;
Begin
{
Table_32a divides the number for eight bits (not four).
Note that Table_32b is identical to Table_16.
}
For val := 0 to 15 Do
Begin
result := val;
For i := 1 to 4 Do
Begin
If (result and 1) = 1
then result := (result shr 1) xor POLY
else result := result shr 1;
End;
table_32b[val] := result;
End;
For val := 0 to 15 Do
Begin
result := table_32b[val];
For i := 1 to 4 Do
Begin
If (result and 1) = 1
then result := (result shr 1) xor POLY
else result := result shr 1;
End;
table_32a[val] := result;
End;
End;
Procedure generate_table_256(POLY : Integer);
{
This routine computes the remainder values of 0 through 255 divided
by the polynomial represented by POLY. These values are placed in a
table and used to compute the CRC of a block of data efficiently.
More space is used, but the CRC computation will be faster.
This implementation only permits polynomials up to degree 16.
}
Var
val, i, result, divide : Integer;
Begin
For val := 0 to 255 Do
Begin
result := val;
For i := 1 to 8 Do
Begin
If (result and 1) = 1
then result := (result shr 1) xor POLY
else result := result shr 1;
End;
table_256[val] := result;
End
End;
Procedure Compute_crc_16(next_byte : byte);
{
This routine calculates the CRC and stores the result in a global
variable CRC_value. You must first initialize CRC_value to 0 or the
proper initial value for the CRC and then call this routine with
each byte.
This routine uses table_16.
}
Begin
inline(
$8b/$16/CRC_value/ {mov dx,CRC_value }
$32/$56/<next_byte/ {xor dl,next_byte[bp] CRC = CRC XOR Next_byte }
$be/table_16/ {mov si,offset table_16 (table address) }
$30/$ff/ {xor bh,bh (bh <- 0) }
$88/$d3/ {mov bl,dl }
$80/$e3/$0f/ {and bl,0f }
$d0/$e3/ {shl bl,1 }
$b1/$04/ {mov cl,4 }
$d3/$ea/ {shr dx,cl }
$33/$10/ {xor dx,[bx+si] CRC = (CRC shr 4) XOR
table[CRC and 0F] }
$88/$d3/ {mov bl,dl }
$80/$e3/$0f/ {and bl,0f }
$d0/$e3/ {shl bl,1 }
$b1/$04/ {mov cl,4 }
$d3/$ea/ {shr dx,cl }
$33/$10/ {xor dx,[bx+si] CRC = (CRC shr 4) XOR
table[CRC and 0F] }
$89/$16/CRC_value); {mov CRC_value,dx Update CRC in memory }
{ basic algorithm expressed above
temp := crc XOR next_byte;
For i := 1 to 2 Do
temp := (temp shr 4) XOR table [temp and $0F];
CRC_value := temp;
}
End;
Procedure Compute_crc_32(next_byte : byte);
{
This is the algorithm used in KERMIT.
The code here completely new. This routine uses table_32a and
table_32b.
}
Begin
inline(
$8b/$16/CRC_value/ {mov dx,CRC_value }
$32/$56/<next_byte/ {xor dl,next_byte[bp] CRC = CRC XOR Next_byte }
{ intermediate steps, see comments for overall effect }
$31/$db/ {xor bx,bx (bx <- 0) }
$86/$d3/ {xchg bl,dl (bx <- dx and 0FF) }
$86/$f2/ {xchg dl,dh (dx <- dx shr 8) }
$88/$d8/ {mov al,bl }
$80/$e3/$0f/ {and bl,0fh }
$d0/$e3/ {shl bl,1 (bx <- bx+bx) }
$be/table_32a/ {mov si,offset table_32a (table address) }
$33/$10/ {xor dx,[bx+si] }
$88/$c3/ {mov bl,al }
$80/$e3/$f0/ {and bl,0f0h }
$b1/$03/ {mov cl,3 }
$d2/$eb/ {shr bl,cl }
$be/table_32b/ {mov si,offset table_32b (table address) }
$33/$10/ {xor dx,[bx+si] }
$89/$16/CRC_value); {mov CRC_value,dx Update CRC in memory }
End;
Procedure Compute_crc_256(next_byte : byte);
{
This routine calculates the CRC and stores the result in a global
variable CRC_value. You must first initialize CRC_value to 0 or the
proper initial value for the CRC and then call this routine with
each byte.
This routine uses table_256.
}
Begin
inline(
$8b/$16/CRC_value/ {mov dx,CRC_value }
$be/table_256/ {mov si,offset table_256 (table address) }
$32/$56/<next_byte/ {xor dl,next_byte[bp] CRC = CRC XOR Next_byte }
{ intermediate steps, see comments for overall effect }
$31/$db/ {xor bx,bx (bx <- 0) }
$86/$d3/ {xchg bl,dl (bx <- dx and 0FF) }
$86/$f2/ {xchg dl,dh (dx <- dx shr 8) }
$d1/$e3/ {shl bx,1 (bx <- bx+bx) }
$33/$10/ {xor dx,[bx+si] CRC = (CRC shr 8) XOR
table[CRC and 0FF] }
$89/$16/CRC_value); {mov CRC_value,dx Update CRC in memory }
{ basic algorithm expressed above
temp := crc XOR next_byte;
temp := (temp shr 8) XOR table_256 [temp and $FF];
CRC_value := temp;
}
End;
Function crc_string_16(Var s : Bytes; length, initial_crc : Integer) : Integer;
{
This routine computes the CRC value and returns it as the function
value. The routine takes an array of Bytes, a length and an initial
value for the CRC. The routine requires that a table of 16 values
be set up by a previous call to Generate_table_16.
This routine uses table_16.
}
Begin
inline(
$c4/$7e/<s/ {les di,s[bp] (es:di points to array) }
$8b/$46/<initial_crc/ {mov ax,initial_crc[bp] (initial CRC value) }
$8b/$56/<length/ {mov dx,length[bp] (count) }
$be/table_16/ {mov si,offset table_16 (table address) }
$30/$ff/ {xor bh,bh (bh <- 0) }
{ next: }
$26/$32/$05/ {xor al,es:[di] CRC = CRC XOR next byte }
$47/ {inc di (point to next byte) }
$88/$c3/ {mov bl,al }
$80/$e3/$0f/ {and bl,0f }
$d0/$e3/ {shl bl,1 }
$b1/$04/ {mov cl,4 }
$d3/$e8/ {shr ax,cl }
$33/$00/ {xor ax,[bx+si] CRC = (CRC shr 4) XOR
table[CRC and 0F] }
$88/$c3/ {mov bl,al }
$80/$e3/$0f/ {and bl,0f }
$d0/$e3/ {shl bl,1 }
$b1/$04/ {mov cl,4 }
$d3/$e8/ {shr ax,cl }
$33/$00/ {xor ax,[bx+si] CRC = (CRC shr 4) XOR
table[CRC and 0F] }
$4a/ {dec dx (count <- count -1) }
$75/$df/ {jnz next }
$89/$46/<s+4); {mov s+4[bp],ax (crc_string_16 := CRC) }
{ basic algorithm expressed above
temp := initial_crc;
For each byte Do
Begin
temp := temp XOR next_byte;
For i := 1 to 2 Do
temp := (temp shr 4) XOR table [temp and $0F];
End;
Crc_string_16 := temp;
}
End;
Function crc_string_256(Var s : Bytes; length, initial_crc : Integer) : Integer;
{
This routine computes the CRC value and returns it as the function
value. The routine takes an array of Bytes, a length and an initial
value for the CRC. The routine requires that a table of 256 values
be set up by a previous call to Generate_table_256.
This routine uses table_256.
}
Begin
inline(
$c4/$7e/<s/ {les di,s[bp] (es:di points to array) }
$8b/$46/<initial_crc/ {mov ax,initial_crc[bp] (initial CRC value) }
$8b/$4e/<length/ {mov cx,length[bp] (count) }
$be/table_256/ {mov si,offset table_256 (table address) }
{ next: }
$26/$32/$05/ {xor al,es:[di] CRC = CRC XOR next byte }
$47/ {inc di (point to next byte) }
{ intermediate steps, see comments for overall effect }
$31/$db/ {xor bx,bx (bx <- 0) }
$86/$d8/ {xchg al,bl (bx <- ax and 0FF) }
$86/$e0/ {xchg al,ah (ax <- ax shr 8) }
$d1/$e3/ {shl bx,1 (bx <- bx+bx) }
$33/$00/ {xor ax,[bx+si] CRC = (CRC shr 8) XOR
table[CRC and 0FF] }
$e2/$f0/ {loop next (count <- count -1) }
$89/$46/<s+4); {mov s+4[bp],ax (crc_string_256 := CRC) }
{ basic algorithm expressed above
crc := initial_crc
For each byte Do
Begin
crc := crc XOR next_byte;
crc := (crc shr 8) XOR table_256 [crc and $FF];
End;
crc_string_256 := crc;
}
End;
Begin
Writeln('Generating the data string, please wait ...');
Writeln;
Writeln;
Generate_table_16($8404);
Generate_table_32($8404);
Generate_table_256($8404);
For j := 1 to max Do
byte_string[j] := trunc(random*256); { Create a data string }
length[1] := 512;
length[2] := 1024;
length[3] := 2048;
length[4] := 4096;
length[5] := 32767;
Writeln;
Writeln(' D a t a S t r e a m L e n g t h');
Writeln;
Write(' ');
For j := 1 to 5 Do
Write(' ', length[j]:8);
Writeln;
Writeln;
Initial_clock := time;
Set_timer(5964); { each tick = ~0.005 seconds }
{-----------------------------------------------------------------------------}
CRC_value := 0;
POLY := $8404;
Write('No table ');
For j := 1 to 5 Do
Begin
time := 0;
For i := 1 to length[j] Do
simple_crc(byte_string[i]);
stop := time;
Write(stop/200:5:2, ' ');
End;
Writeln('CRC = ', CRC_value);
{-----------------------------------------------------------------------------}
CRC_value := 0;
Write('Nybble table ');
For j := 1 to 5 Do
Begin
time := 0;
For i := 1 to length[j] Do
compute_crc_16(byte_string[i]);
stop := time;
Write(stop/200:5:2, ' ');
End;
Writeln('CRC = ', CRC_value);
{-----------------------------------------------------------------------------}
CRC_value := 0;
Write('Two Nybble tables ');
For j := 1 to 5 Do
Begin
time := 0;
For i := 1 to length[j] Do
compute_crc_32(byte_string[i]);
stop := time;
Write(stop/200:5:2, ' ');
End;
Writeln('CRC = ', CRC_value);
{-----------------------------------------------------------------------------}
CRC_value := 0;
Write('Byte table ');
For j := 1 to 5 Do
Begin
time := 0;
For i := 1 to length[j] Do
compute_crc_256(byte_string[i]);
stop := time;
Write(stop/200:5:2, ' ');
End;
Writeln('CRC = ', CRC_value);
{-----------------------------------------------------------------------------}
CRC_value := 0;
Write('Nybble string ');
For j := 1 to 5 Do
Begin
time := 0;
CRC_value := crc_string_16(byte_string, length[j], CRC_value);
stop := time;
Write(stop/200:5:2, ' ');
End;
Writeln('CRC = ', CRC_value);
{-----------------------------------------------------------------------------}
CRC_value := 0;
Write('Byte string ');
For j := 1 to 5 Do
Begin
time := 0;
CRC_value := crc_string_256(byte_string, length[j], CRC_value);
stop := time;
Write(stop/200:5:2, ' ');
End;
Writeln('CRC = ', CRC_value);
{-----------------------------------------------------------------------------}
set_timer(0); { restore the clock to the normal DOS value }
time := initial_clock; { we may have lost a few minutes ... }
End.
|
| I'm not sure what "using only one table lookup" means. I have played with
several algorithms, all based on table lookup. I also have the byte-wide
algorithm in VAX assembler, as well as some timings. If you're interested
in more details, send me mail (I am not a regular reader of this
conference). I also have some 80186 assembly code for the truly perverse.
The program below has been hacked quite a few times to improve performance,
so it's not entirely readable. Some routines were stolen from other code,
and thus I'm afraid that all the comments don't make sense. In the edc_8
and edc_16 routines I have used pointer arithmetic to speed things up, but
the original code is in comments.
Which routine you use depends upon your machine's native word size, and how
big a lookup table you can afford. The 8-bit seems a reasonable compromise,
though the "fast_8" (assembly code not included) runs noticibly faster for 4
times the table size.
I would also suggest that if you are going to use this routine much at all,
that you should hand optimize it in assembler. It's usually worth the
effort.
I just re-ran this code, and for some reason (left as an exercise to the
reader) the Edc_4 routine gives the wrong answer. All of the other routines
are correct, however.
#include <stdio.h>
#include <descrip.h>
#define array_size 2048
#define table_bits 16
#define table_size (1<<table_bits)
#define high_word(value) (*(((unsigned short *) &(value))+1))
#define low_word(value) (* (unsigned short *) &(value))
#define high_byte(value) (*(((unsigned char *) &(value))+1))
#define low_byte(value) (* (unsigned char *) &(value))
unsigned long Data[array_size];
unsigned long Edc[table_size];
unsigned long Residue,Residue1=0;
unsigned long gen_edc();
unsigned long edc_4();
unsigned long edc_8();
unsigned long edc_16();
extern unsigned long fast_8();
extern unsigned long LIB$CRC();
/* ************************************************************************* */
/* TITLE - EDC.C */
/* ABSTRACT - Program to calculate EDC on a byte stream and time it. */
/* INPUTS - none */
/* OUTPUTS - none */
/* ************************************************************************* */
main()
{
unsigned long Temp1,Temp2;
unsigned int Index,Iter;
struct dsc$descriptor Data_desc;
srand(1);
for (Index = 0;Index < array_size;Index++)
{
Data[Index] = Index;
}
/* First, one bit at a time in HLL. */
timer();
Temp1 = gen_edc(Data,array_size);
printf("Time = %f\n",((float) timer())*10);
/* 4 bits at a time in HLL. */
edc_table(Edc,4);
Temp2 = edc_4(Data,array_size);
if (Temp1 != Temp2) printf("Edc_4 %x:%x\n",Temp1,Temp2);
timer();
#define loop 10000
for (Iter = 0;Iter < loop;Iter++)
{
Temp2 = edc_4(Data,0);
}
printf("4 bits, 0 length %f\n",(float)timer()*10/loop);
timer();
#define loop 100
for (Iter = 0;Iter < loop;Iter++)
{
Temp2 = edc_4(Data,array_size);
}
printf("4 bits, full length %f\n",(float) timer()*10/loop);
/* 8 bits at a time in HLL. */
edc_table(Edc,8);
Temp2 = edc_8(Data,array_size);
if (Temp1 != Temp2) printf("Edc_8 %x:%x\n",Temp1,Temp2);
timer();
for (Iter = 0;Iter < loop;Iter++)
{
Temp2 = edc_8(Data,array_size);
}
printf("8 bits, full length %f\n",(float) timer()*10/loop);
/* 8 bits at a time, fast algorithm. */
edc_table(&Edc[768],8); /* Non-rotated table is last table. */
for(Iter = 0;Iter < 256;Iter++)
{
Edc[Iter + 768] ^= Iter << 24;
Edc[Iter] = (Edc[Iter + 768] << 8) + (Edc[Iter + 768] >> 24);
Edc[Iter + 256] = (Edc[Iter + 768] << 16) + (Edc[Iter + 768] >> 16);
Edc[Iter + 512] = (Edc[Iter + 768] << 24) + (Edc[Iter + 768] >> 8);
}
Temp2 = fast_8(Data,array_size,Edc,0);
if (Temp1 != Temp2) printf("Fast_8 %x:%x\n",Temp1,Temp2);
timer();
for (Iter = 0;Iter < loop;Iter++)
{
Temp2 = fast_8(Data,array_size,Edc,0);
}
printf("8 bits fast, full length %f\n",(float) timer()*10/loop);
/* 16 bits at a time in HLL. */
edc_table(Edc,16);
Temp2 = edc_16(Data,array_size);
if (Temp1 != Temp2) printf("Edc_16 %x:%x\n",Temp1,Temp2);
timer();
for (Iter = 0;Iter < loop;Iter++)
{
Temp2 = edc_16(Data,array_size);
}
printf("16 bits, full length %f\n",(float) timer()*10/loop);
/* Using the VAX instruction (4 bits at a time). */
Data_desc.dsc$w_length = 0;
Data_desc.dsc$b_dtype = DSC$K_DTYPE_NU;
Data_desc.dsc$b_class = DSC$K_CLASS_S;
Data_desc.dsc$a_pointer = Data;
edc_table(Edc,4);
timer();
#define loop 10000
for (Iter = 0;Iter < loop;Iter++)
{
Temp2 = LIB$CRC(Edc,&0,&Data_desc);
}
printf("VAX, 0 length %f\n",(float) timer()*10/loop);
#define loop 100
Data_desc.dsc$w_length = array_size * 4;
timer();
for (Iter = 0;Iter < loop;Iter++)
{
Temp2 = LIB$CRC(Edc,&0,&Data_desc);
}
printf("VAX, full length %f\n",(float) timer()*10/loop);
}
/* ************************************************************************* */
/* TITLE - timer() */
/* ABSTRACT - Returns delta time between calls in 10 ms chunks. */
/* INPUTS - none */
/* OUTPUTS - int Time in 10 ms chunks. */
/* ************************************************************************* */
struct tbuffer
{
int proc_user_time;
int proc_system_time;
int child_user_time;
int child_system_time;
};
static int Last;
timer()
{
struct tbuffer buffer;
int Temp;
times(&buffer);
Temp = buffer.proc_user_time - Last;
Last = buffer.proc_user_time;
return(Temp);
}
/* ************************************************************************* */
/* TITLE - gen_edc(Data,Size) */
/* ABSTRACT - Function to generate the EDC on a sector. It does this by */
/* calculating with a linear feedback shift register, one bit */
/* at a time. The data is considered as a collection of 516 */
/* long integers (32 bits) (2064 bytes). The calculated EDC is */
/* 32 bits long, and goes into long word 516, just after the */
/* data. */
/* INPUTS - unsigned long Data[],Size */
/* OUTPUTS - undigned long Calculated EDC. */
/* ************************************************************************* */
#define EDC_VALUE 0xD8018001L
/* */
/* 32 31 16 15 4 3 */
/* X + X + X + X + X + X + X + 1 */
/* */
unsigned long gen_edc(Data,Size)
unsigned long Data[],Size;
{
register unsigned long Data_long;
unsigned short Long_count,Bit_count;
Residue = 0;
for (Long_count = 0;Long_count < Size;Long_count++)
{
Data_long = Data[Long_count];
for (Bit_count = 0;Bit_count < 32;Bit_count++)
{
if ((Data_long ^ Residue) & 0x01)
{
Residue >>= 1;
Residue ^= EDC_VALUE;
}
else
{
Residue >>= 1;
}
Data_long >>= 1;
}
}
return(Residue);
}
/* ************************************************************************* */
/* TITLE - edc_4(Data,Size) */
/* ABSTRACT - Function to generate the EDC on a sector. It does this by */
/* XORing a long word with the 32 bit residue, and then */
/* performing the following action 32/Numbits times. The low */
/* byte of the residue is saved as a table index, The residue */
/* is then rotated right Numbits bits. A long word is looked */
/* up from a table using the saved index, and this value is */
/* XORed with the rotated residue. The Edc table generation */
/* is described in edc_table. This function, given the proper */
/* table, performs the same function as the gen_edc routine, */
/* only faster. */
/* INPUTS - unsigned long Data[],Size */
/* OUTPUTS - unsigned long Calculated EDC. */
/* ************************************************************************* */
unsigned long edc_4(Data,Size)
unsigned long Data[],Size;
{
unsigned short Index,Long_count;
#define Numbits 4
#define Bitmask 0x0f
Residue = 0;
for (Long_count = 0;Long_count < Size;Long_count++)
{
Residue ^= Data[Long_count];
Index = Residue & Bitmask;
Residue >>= Numbits;
Residue ^= Edc[Index];
Index = Residue & Bitmask;
Residue >>= Numbits;
Residue ^= Edc[Index];
Index = Residue & Bitmask;
Residue >>= Numbits;
Residue ^= Edc[Index];
Index = Residue & Bitmask;
Residue >>= Numbits;
Residue ^= Edc[Index];
Residue ^= Data[Long_count];
Index = Residue & Bitmask;
Residue >>= Numbits;
Residue ^= Edc[Index];
Index = Residue & Bitmask;
Residue >>= Numbits;
Residue ^= Edc[Index];
Index = Residue & Bitmask;
Residue >>= Numbits;
Residue ^= Edc[Index];
Index = Residue & Bitmask;
Residue >>= Numbits;
Residue ^= Edc[Index];
}
return(Residue);
}
/* ************************************************************************* */
/* TITLE - edc_8(Data,Size) */
/* ABSTRACT - Function to generate the EDC on a sector. It does this by */
/* XORing a long word with the 32 bit residue, and then */
/* performing the following action 32/Numbits times. The low */
/* byte of the residue is saved as a table index, The residue */
/* is then rotated right Numbits bits. A long word is looked */
/* up from a table using the saved index, and this value is */
/* XORed with the rotated residue. The Edc table generation */
/* is described in edc_table. This function, given the proper */
/* table, performs the same function as the gen_edc routine, */
/* only faster. */
/* INPUTS - unsigned long Data[],Size */
/* OUTPUTS - unsigned long Calculated EDC. */
/* ************************************************************************* */
unsigned long edc_8(Data,Size)
unsigned long Data[],Size;
{
unsigned long *Resptr,Long_count;
unsigned char Index;
#define Numbits 8
#define Bitmask ((1 << Numbits) -1)
Resptr = &Residue;
*Resptr = 0;
for (Long_count = 0;Long_count < Size;Long_count++)
{
*Resptr ^= Data[Long_count];
/* Index = Residue & Bitmask; */
Index = *Resptr;
/* Residue >>= Numbits; */
*Resptr = (* (unsigned long *) (((unsigned char *) Resptr)+1));
*Resptr ^= Edc[Index];
/* Index = Residue & Bitmask; */
Index = *Resptr;
/* Residue >>= Numbits; */
*Resptr = (* (unsigned long *) (((unsigned char *) Resptr)+1));
*Resptr ^= Edc[Index];
/* Index = Residue & Bitmask; */
Index = *Resptr;
/* Residue >>= Numbits; */
*Resptr = (* (unsigned long *) (((unsigned char *) Resptr)+1));
*Resptr ^= Edc[Index];
/* Index = Residue & Bitmask; */
Index = *Resptr;
/* Residue >>= Numbits; */
*Resptr = (* (unsigned long *) (((unsigned char *) Resptr)+1));
*Resptr ^= Edc[Index];
}
return(Residue);
}
/* ************************************************************************* */
/* TITLE - edc_16(Data,Size) */
/* ABSTRACT - Function to generate the EDC on a sector. It does this by */
/* XORing a long word with the 32 bit residue, and then */
/* performing the following action 32/Numbits times. The low */
/* byte of the residue is saved as a table index, The residue */
/* is then rotated right Numbits bits. A long word is looked */
/* up from a table using the saved index, and this value is */
/* XORed with the rotated residue. The Edc table generation */
/* is described in edc_table. This function, given the proper */
/* table, performs the same function as the gen_edc routine, */
/* only faster. */
/* INPUTS - unsigned long Data[],Size */
/* OUTPUTS - unsigned long Calculated EDC. */
/* ************************************************************************* */
unsigned long edc_16(Data,Size)
unsigned long Data[],Size;
{
unsigned long *Resptr,Long_count;
unsigned short Index;
#define Numbits 16
#define Bitmask ((1 << Numbits) -1)
Resptr = &Residue;
*Resptr = 0;
for (Long_count = 0;Long_count < Size;Long_count++)
{
*Resptr ^= Data[Long_count];
/* Index = Residue & Bitmask; */
Index = *Resptr;
/* Residue >>= Numbits; */
*Resptr = (*(((unsigned short *) Resptr)+1));
Residue ^= Edc[Index];
/* Index = Residue & Bitmask; */
Index = *Resptr;
/* Residue >>= Numbits; */
*Resptr = (*(((unsigned short *) Resptr)+1));
Residue ^= Edc[Index];
}
return(Residue);
#undef Numbits
}
/* ************************************************************************* */
/* TITLE - edc_table(Edc,Numbits) */
/* ABSTRACT - Generates the lookup table required by par_gen_edc. The */
/* algorithm was derived from the description of the CRC */
/* instruction in the VAX Architecture Handbook. */
/* INPUTS - unsigned long Edc[],Numbits */
/* OUTPUTS - none. */
/* ************************************************************************* */
#define POLY 0xD8018001L
/* */
/* 32 31 16 15 4 3 */
/* X + X + X + X + X + X + X + 1 */
/* */
edc_table(Edc,Numbits)
unsigned long Edc[],Numbits;
{
register unsigned long Iter,Iter2,Bit,Value,Size;
Size = 1 << Numbits;
for (Iter = 0;Iter < Size;Iter++)
{
Value = Iter;
for (Iter2 = 0;Iter2 < Numbits;Iter2++)
{
Bit = Value & 0x01;
Value >>= 1;
if (Bit == 1)
Value ^= POLY;
}
Edc[Iter] = Value;
}
}
|