📄 crcset.doc
字号:
register are the bit numbers of the register.
The CRC is calculated as follows:
1. Initialize the CRC register to 0.
2. Add the incoming bit of the data stream to the outgoing bit (bit 3) of the
CRC register.
3. Send the result of step 1 into the polynomial feedback loop.
4. Add the value in the feedback loop to the bits in the CRC register as it is
shifted left. The bits affected are determined by the CRC polynomial (i.e.
there is an addition for every bit in the polynomial that is equal to 1; if
the bit is 0, it is not fed back into the register). In this case, the
polynomial represented is 1011.
5. Repeat steps 2-4 for every bit in the data stream.
6. The CRC is the value in the register.
Let's try this with the data stream 11010111 and the polynomial 1011. The
result will be a 4-bit CRC.
The output stream to the left is the result of each addition operation
at the left-most gate. This is the value that is fed into the polynomial
feedback loop during the left shift.
------------1-----------0-----------1-----------1
| 3 | 2 1 | 0 |
| ----- v ----- ----- v ----- v
+ <-| 0 |<- + <-| 0 |<------| 0 |<- + <-| 0 |<- +
^ ----- ----- ----- -----
|
---- 11010111
------------1-----------0-----------1-----------1
| 3 | 2 1 | 0 |
| ----- v ----- ----- v ----- v
1 <- + <-| 1 |<- + <-| 0 |<------| 1 |<- + <-| 1 |<- +
^ ----- ----- ----- -----
|
---- 1010111
- Page 5 -
------------1-----------0-----------1-----------1
| 3 | 2 1 | 0 |
| ----- v ----- ----- v ----- v
10 <- + <-| 0 |<- + <-| 1 |<------| 1 |<- + <-| 0 |<- +
^ ----- ----- ----- -----
|
---- 010111
------------1-----------0-----------1-----------1
| 3 | 2 1 | 0 |
| ----- v ----- ----- v ----- v
100 <- + <-| 1 |<- + <-| 1 |<------| 0 |<- + <-| 0 |<- +
^ ----- ----- ----- -----
|
---- 10111
------------1-----------0-----------1-----------1
| 3 | 2 1 | 0 |
| ----- v ----- ----- v ----- v
1000 <- + <-| 1 |<- + <-| 0 |<------| 0 |<- + <-| 0 |<- +
^ ----- ----- ----- -----
|
---- 0111
------------1-----------0-----------1-----------1
| 3 | 2 1 | 0 |
| ----- v ----- ----- v ----- v
10001 <- + <-| 1 |<- + <-| 0 |<------| 1 |<- + <-| 1 |<- +
^ ----- ----- ----- -----
|
---- 111
------------1-----------0-----------1-----------1
| 3 | 2 1 | 0 |
| ----- v ----- ----- v ----- v
100010 <- + <-| 0 |<- + <-| 1 |<------| 1 |<- + <-| 0 |<- +
^ ----- ----- ----- -----
|
---- 11
------------1-----------0-----------1-----------1
| 3 | 2 1 | 0 |
| ----- v ----- ----- v ----- v
1000101 <- + <-| 0 |<- + <-| 1 |<------| 1 |<- + <-| 1 |<- +
^ ----- ----- ----- -----
|
---- 1
------------1-----------0-----------1-----------1
| 3 | 2 1 | 0 |
| ----- v ----- ----- v ----- v
10001011 <- + <-| 0 |<- + <-| 1 |<------| 0 |<- + <-| 1 |<- +
^ ----- ----- ----- -----
|
----
The CRC is 0101.
- Page 6 -
What should be obvious at this point is that if a single bit in the
data stream is changed, the value in the CRC register is corrupted completely.
The feedback loop ensures that the error is propagated throughout the entire
calculation.
Most CRC algorithms use either a 16- or 32-bit polynomial. The longer
the polynomial, the more effective it is at catching errors; a 16-bit CRC, for
example, algorithm catches more than 99.99% of all errors in a data stream.
All other CRC algorithms are analogous to the 4-bit algorithm
presented here. There are some optimizations that can process several bits at
a time; the source code included with this program uses a lookup table that
can process 8 bits at once. For further discussion of the CRC algorithm and
its variations, I recommend "C Programmer's Guide to Serial Communications" by
Joe Campbell, published by Howard W. Sams & Company.
- Page 7 -
How CRCSET Works
The idea of storing a program's CRC in the executable file itself has
one drawback: since the CRC is part of the program, it becomes part of the
data stream that is used to calculate itself. In other words, you have to
know what the CRC of the program is in order to calculate it! At compile and
link time, this is downright impossible; changing the slightest thing in your
code will change the CRC the next time you recompile.
Most algorithms that store the CRC in the program itself get around
this drawback by breaking up the program into three chunks:
+------------------------+-----+------------------------+
| <-- Program part 1 --> | CRC | <-- Program part 2 --> |
+------------------------+-----+------------------------+
The CRC is then calculated as the concatenation of parts 1 and 2, i.e. when
the CRC is calculated, it skips over itself completely in the calculation.
What it sees is this:
+------------------------+------------------------+
| <-- Program part 1 --> | <-- Program part 2 --> |
+------------------------+------------------------+
In order for a virus to infect any program that uses this method, it
must somehow find the location of the CRC within the file and recalculate the
CRC using the following data stream:
+------------------------+------------------------+---------------+
| <-- Program part 1 --> | <-- Program part 2 --> | <-- Virus --> |
+------------------------+------------------------+---------------+
It must then overwrite the old CRC with the new one.
I won't explain how (I don't want to give any virus-writers any
ideas), but with the right technique the CRC can be found, recalculated, and
rewritten in under 30 seconds.
CRCSET overcomes this limitation by making the polynomial and the CRC
part of the data stream. In order to calculate the CRC, CRCSET looks for a
predefined string in the program (the default is DEAN_CRC), replaces the first
four bytes with a 32-bit polynomial, sets the next four bytes (the true CRC)
to 0, and calculates the intermediate CRC assuming that the true CRC is 0.
Then, through the magic of matrix algebra, CRCSET calculates what the true CRC
should have been in order to yield itself instead of the intermediate CRC at
the end. Let's take a look at a 4-bit CRC calculation as an example.
Let's assume that the polynomial in use is 1011, that the CRC
calculated up to the point where we reach the search string (represented by
the bit pattern STUVWXYZ) is 0010, and that the bit pattern 1100 follows the
search string:
- Page 8 -
------------1-----------0-----------1-----------1
| 3 | 2 1 | 0 |
| ----- v ----- ----- v ----- v
+ <-| 0 |<- + <-| 0 |<------| 1 |<- + <-| 0 |<- +
^ ----- ----- ----- -----
|
---- STUVWXYZ1100
1. Replace the first four bits (STUV) with the CRC polynomial (1011):
------------1-----------0-----------1-----------1
| 3 | 2 1 | 0 |
| ----- v ----- ----- v ----- v
+ <-| 0 |<- + <-| 0 |<------| 1 |<- + <-| 0 |<- +
^ ----- ----- ----- -----
|
---- 1011WXYZ1100
2. Calculate the value of the CRC register with the polynomial in the data
stream:
------------1-----------0-----------1-----------1
| 3 | 2 1 | 0 |
| ----- v ----- ----- v ----- v
+ <-| 1 |<- + <-| 0 |<------| 0 |<- + <-| 1 |<- +
^ ----- ----- ----- -----
|
---- WXYZ1100
3. Replace the next four bits (WXYZ) with simple variables (X3, X2, X1, X0):
------------1-----------0-----------1-----------1
| 3 | 2 1 | 0 |
| ----- v ----- ----- v ----- v
+ <-| 1 |<- + <-| 0 |<------| 0 |<- + <-| 1 |<- +
^ ----- ----- ----- -----
|
---- (X3)(X2)(X1)(X0)1100
4. Propagate X3+(bit 3) through the feedback loop:
---------------1-----------0------------1--------------1
| 3 | 2 1 | 0 |
| -------- v ----- ------ v -------- v
+ <-| X3+1 |<- + <-| 0 |<------| X3 |<- + <-| X3+1 |<- +
^ -------- ----- ------ --------
|
---- (X2)(X1)(X0)1100
- Page 9 -
5. Propagate X2+(bit 3) through the feedback loop:
------------------1------------0------------1-----------------1
| 3 | 2 1 | 0 |
| ----------- v ------ ------ v ----------- v
+ <-| X3+X2+1 |<- + <-| X3 |<------| X2 |<- + <-| X3+X2+1 |<- +
^ ----------- ------ ------ -----------
|
---- (X1)(X0)1100
In bit 1, for example, we have (X2+(bit 3))+(bit 0) = (X2+X3+1)+(X3+1) = X2
since the X3 terms cancel, no matter what the value of X3 is.
6. Propagate X1+(bit 3) through the feedback loop:
------------------1------------0------------1--------------------1
| 3 | 2 1 | 0 |
| ----------- v ------ ------ v -------------- v
+ <-| X2+X1+1 |<- + <-| X2 |<------| X1 |<- + <-| X3+X2+X1+1 |<- +
^ ----------- ------ ------ --------------
|
---- (X0)1100
7. Propagate X0+(bit 3) through the feedback loop:
------------------1------------0---------------1--------------------1
| 3 | 2 1 | 0 |
| ----------- v ------ --------- v -------------- v
+ <-| X1+X0+1 |<- + <-| X1 |<------| X3+X0 |<- + <-| X2+X1+X0+1 |<- +
^ ----------- ------ --------- --------------
|
---- 1100
8. Propagate the next bit through the feedback loop:
-------------1---------------0--------------1---------------1
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -