CRC-32
ZXNet echo conference «code.zx»
Hello All
Give me a piece of code to calculate the subject! I still have a question, I’ll put it to you
I calculated the TRC for 16k pieces of the file! What should I do with these pieces?
[ZX][Sprinter owner][rw1p2][NedoPC]
Bye
Hello, Vladimir!
06 May 03 23:14, Vladimir Karpenko -> All:
VK> Give me a piece of code to calculate the subject!
Asm here is really x86, well, I hope you’ll figure it out
The algorithm is standard, it calculates WinRAR, HW, and indeed all others...
.code
;initialize crc32 value
mov eax, -1
mov d_cr32, eax
;here you can make a loop to process small blocks
lea esi, bufl ;block address
mov ebx, SRW ;block size
call cr_cal ; calculates crc for block
;finalize crc32, and return it
mov eax, d_cr32
xor eax, -1 ;finalization
ret
cr_cal: mov edx, d_cr32
lea edi, cr32t
cld
cr32: push ebx
lodsb
mov cx, dx
shr edx, 16
xor al, cl
mov bl, al
mov cl, ch
mov ch, dl
mov dl, dh
xor dh, dh
mov bh, dh
shl bx, 2
and ebx, 0ffffh
shl edx, 16
mov dx, cx
xor edx, [edi+ebx]
pop ebx
dec ebx
jz cr32e
jmp cr32
cr32e: mov d_cr32, edx
ret
.data
d_cr32 dd ?
cr32t dd 000000000h, 077073096h, 0ee0e612ch, 0990951bah, 0076dc419h dd 0706af48fh, 0e963a535h, 09e6495a3h, 00edb8832h, 079dcb8a4h
dd 0e0d5e91eh, 097d2d988h, 009b64c2bh, 07eb17cbdh, 0e7b82d07h
dd 090bf1d91h, 01db71064h, 06ab020f2h, 0f3b97148h, 084be41deh
dd 01adad47dh, 06ddde4ebh, 0f4d4b551h, 083d385c7h, 0136c9856h
dd 0646ba8c0h, 0fd62f97ah, 08a65c9ech, 014015c4fh, 063066cd9h
dd 0fa0f3d63h, 08d080df5h, 03b6e20c8h, 04c69105eh, 0d56041e4h
dd 0a2677172h, 03c03e4d1h, 04b04d447h, 0d20d85fdh, 0a50ab56bh
dd 035b5a8fah, 042b2986ch, 0dbbbc9d6h, 0acbcf940h, 032d86ce3h
dd 045df5c75h, 0dcd60dcfh, 0abd13d59h, 026d930ach, 051de003ah
dd 0c8d75180h, 0bfd06116h, 021b4f4b5h, 056b3c423h, 0cfba9599h
dd 0b8bda50fh, 02802b89eh, 05f058808h, 0c60cd9b2h, 0b10be924h
dd 02f6f7c87h, 058684c11h, 0c1611dabh, 0b6662d3dh, 076dc4190h
dd 001db7106h, 098d220bch, 0efd5102ah, 071b18589h, 006b6b51fh
dd 09fbfe4a5h, 0e8b8d433h, 07807c9a2h, 00f00f934h, 09609a88eh
dd 0e10e9818h, 07f6a0dbbh, 0086d3d2dh, 091646c97h, 0e6635c01h
dd 06b6b51f4h, 01c6c6162h, 0856530d8h, 0f262004eh, 06c0695edh
dd 01b01a57bh, 08208f4c1h, 0f50fc457h, 065b0d9c6h, 012b7e950h
dd 08bbeb8eah, 0fcb9887ch, 062dd1ddfh, 015da2d49h, 08cd37cf3h
dd 0fbd44c65h, 04db26158h, 03ab551ceh, 0a3bc0074h, 0d4bb30e2h
dd 04adfa541h, 03dd895d7h, 0a4d1c46dh, 0d3d6f4fbh, 04369e96ah
dd 0346ed9fch, 0ad678846h, 0da60b8d0h, 044042d73h, 033031de5h
dd 0aa0a4c5fh, 0dd0d7cc9h, 05005713ch, 0270241aah, 0be0b1010h
dd 0c90c2086h, 05768b525h, 0206f85b3h, 0b966d409h, 0ce61e49fh
dd 05edef90eh, 029d9c998h, 0b0d09822h, 0c7d7a8b4h, 059b33d17h
dd 02eb40d81h, 0b7bd5c3bh, 0c0ba6cadh, 0edb88320h, 09abfb3b6h
dd 003b6e20ch, 074b1d29ah, 0ead54739h, 09dd277afh, 004db2615h
dd 073dc1683h, 0e3630b12h, 094643b84h, 00d6d6a3eh, 07a6a5aa8h
dd 0e40ecf0bh, 09309ff9dh, 00a00ae27h, 07d079eb1h, 0f00f9344h
dd 08708a3d2h, 01e01f268h, 06906c2feh, 0f762575dh, 0806567cbh
dd 0196c3671h, 06e6b06e7h, 0fed41b76h, 089d32be0h, 010da7a5ah
dd 067dd4acch, 0f9b9df6fh, 08ebeeff9h, 017b7be43h, 060b08ed5h
dd 0d6d6a3e8h, 0a1d1937eh, 038d8c2c4h, 04fdff252h, 0d1bb67f1h
dd 0a6bc5767h, 03fb506ddh, 048b2364bh, 0d80d2bdah, 0af0a1b4ch
dd 036034af6h, 041047a60h, 0df60efc3h, 0a867df55h, 0316e8eefh
dd 04669be79h, 0cb61b38ch, 0bc66831ah, 0256fd2a0h, 05268e236h
dd 0cc0c7795h, 0bb0b4703h, 0220216b9h, 05505262fh, 0c5ba3bbeh
dd 0b2bd0b28h, 02bb45a92h, 05cb36a04h, 0c2d7ffa7h, 0b5d0cf31h
dd 02cd99e8bh, 05bdeae1dh, 09b64c2b0h, 0ec63f226h, 0756aa39ch
dd 0026d930ah, 09c0906a9h, 0eb0e363fh, 072076785h, 005005713h
dd 095bf4a82h, 0e2b87a14h, 07bb12baeh, 00cb61b38h, 092d28e9bh
dd 0e5d5be0dh, 07cdcefb7h, 00bdbdf21h, 086d3d2d4h, 0f1d4e242h
dd 068ddb3f8h, 01fda836eh, 081be16cdh, 0f6b9265bh, 06fb077e1h
dd 018b74777h, 088085ae6h, 0ff0f6a70h, 066063bcah, 011010b5ch
dd 08f659effh, 0f862ae69h, 0616bffd3h, 0166ccf45h, 0a00ae278h
dd 0d70dd2eeh, 04e048354h, 03903b3c2h, 0a7672661h, 0d06016f7h
dd 04969474dh, 03e6e77dbh, 0aed16a4ah, 0d9d65adch, 040df0b66h
dd 037d83bf0h, 0a9bcae53h, 0debb9ec5h, 047b2cf7fh, 030b5ffe9h
dd 0bdbdf21ch, 0cabac28ah, 053b39330h, 024b4a3a6h, 0bad03605h
dd 0cdd70693h, 054de5729h, 023d967bfh, 0b3667a2eh, 0c4614ab8h
dd 05d681b02h, 02a6f2b94h, 0b40bbe37h, 0c30c8ea1h, 05a05df1bh
dd 02d02ef8dh
VK> Ещё есть вопpос я вот пpедpоложим посчитал ЦРЦ для кусков файла
VK> по 16к! Что мне с этими кусками делать?
Hаверно, купить книжку по теории контрольных сумм... А вообще - crc32 это не
мешает... Просто не надо делать финализацию после каждого блока и всё... ;)PS I also have md5... I wrote the CRCControl program (on the website)...
Best regards, Evgeniy.
Hello Eugene
EP> Hello, Vladimir!
EP> 06 May 03 23:14, Vladimir Karpenko -> All:
VK>> Give me a piece of code to calculate the subject!
EP> Asm here is true x86, well, I hope you'll figure it out
EP> The algorithm is standard, it calculates WinRAR, HW, and indeed everything
EP> other...
This is cool but it's TableDrive CRC-32 and I would like a tableless one :)
Here is an example of TsRTs-16 with a table:
Input: HL = address of input data, BC = number of bytes to process
Output: DE = CRC
Note: CrcTab must be aligned to a 256 byte boundary. Table generator uses
reverse of 1021h, that is 8408h.
Crc16 ld d,FFh
ld a,e
Read xor (hl)
ex de,hl
ld l,a
ld a,h
ld h,CrcTab/256
xor (hl)
inc h
ld h,(hl)
ex de,hl
cpi
jppe,Read
ld e,a
ret
CRC table generator:
ld hl,CrcTab
CrcGen ld d,0
ld e,l
ld b,8
CrcByte srl d
rr e
jr nc,Next
ld a,d
xor 84h
ld d,a
ld a,e
xor 08h
ld e,a
Next djnz CrcByte
ld(hl),e
inc hld(hl),d
dec h
inc l
jr nz,CrcGen
ret
But without a table
Input: DE = address of input data, C = number of bytes to process
Output: HL = CRC
Crc16 ld hl,FFFFh
Read ld a,(de)
inc de
xor h
ld h,a
ld b,8
CrcByte add hl,hl
jr nc,Next
ld a,h
xor 10h
ld h,a
ld a,l
xor 21h
ld l,a
Next djnz CrcByte
dec c
jr nz,Read
ret
VK>> There is also a question, I’ll suggest calculating the TRC for pieces of the file
VK>> for 16k! What should I do with these pieces?
EP> Probably buy a book on checksum theory... But in general - crc32
EP> this doesn’t interfere... You just don’t need to do finalization after each block and
EP> that's it... ;)
I understand, if I wasn’t a fool I wouldn’t understand if I was a fool :)
EP> PS. I also have md5... I wrote the CRCControl program (on the website)...
Shabarshin (Shaos), my teammate also wrote MD2 and MD5 for PC on ASMA!
[ZX][Sprinter owner][rw1p2][NedoPC]
Bye
On Wed, 07 May 2003 00:17:58 +0400, Eugene Palenock wrote:
VK>> Give me a piece of code to calculate the subject!
EP> .data
EP> d_cr32 dd ?
EP> cr32t dd 000000000h, 077073096h, 0ee0e612ch, 0990951bah, 0076dc419h
EP> dd 0706af48fh, 0e963a535h, 09e6495a3h, 00edb8832h, 079dcb8a4h
The algorithm is terribly lame. You can count the plate.
--
[ZX]
Hello, Kirill!
May 10, 2003 (it was 6:18 pm then)
Kirill Frolov in his letter to Eugene Palenock wrote:
VK>>> Give me a piece of code to calculate the subject!
EP>>.data
EP>> d_cr32 dd ?
EP>> cr32t dd 000000000h, 077073096h, 0ee0e612ch, 0990951bah,
EP>> 0076dc419h dd 0706af48fh, 0e963a535h, 09e6495a3h,
EP>> 00edb8832h, 079dcb8a4h
KF> The algorithm is terribly lame. You can count the tablet.
But it's faster with a sign! (c) Valker. Although x.z. what does he need: speed or
free memory...
Vega/ex-Style Group.
FIDO: 2:5030/301.29 ZXNET: 500:812/19 E-mail: vega56@mail.ru
Let your enemies, Vlad, die without sons!
11 May 2003 at 04:54, Vlad Sotnikov => Kirill Frolov:
EP>>> cr32t dd 000000000h, 077073096h, 0ee0e612ch, 0990951bah,
EP>>> 0076dc419h dd 0706af48fh, 0e963a535h, 09e6495a3h,
EP>>> 00edb8832h, 079dcb8a4h
KF>> The algorithm is terribly lame. You can count the tablet.
VS> But it’s faster with a sign! (c) Valker. Although x.z. what does he need:
VS> speed or free memory...
You need to read the sign at the start - you will have both speed and memory.
WBR, Oleg.
On Sun, 11 May 2003 03:54:19 +0400, Vlad Sotnikov wrote:
VK>>>> Give me a piece of code to calculate the subject!
EP>>> .data
EP>>> d_cr32 dd ?
EP>>> cr32t dd 000000000h, 077073096h, 0ee0e612ch, 0990951bah,
EP>>> 0076dc419h dd 0706af48fh, 0e963a535h, 09e6495a3h,
EP>>> 00edb8832h, 079dcb8a4h
KF>> The algorithm is terribly lame. You can count the tablet.
VS> But it’s faster with a sign! (c) Valker.
THE PLATE CAN BE COUNTED IN PRELIMINARY, and not stored in the program. Them
Moreover, the plate is usually packaged poorly.
--
[ZX]
Hello Kirill!
05/12/2003 0:58:06, Kirill Frolov wrote to Vlad Sotnikov:
KF>>> The algorithm is terribly lame.
I wonder why? and what can you offer in return?
KF>>> You can count the plates.
VS>> But it’s faster with a sign! (c) Valker.
KF> THE PLATE CAN BE COUNTED IN PRELIMINARY, rather than stored in the program.
logical, but how to do it?
Bye, Oleg.
Glad to see you again, Oleg!
On Tuesday May 13, 2003, at exactly 11:26:36
connection was interrupted. I miraculously managed to detect only the half-strangled:
-"Re: CRC-32"...
KF>>>> The algorithm is terribly lame.
Unconditionally and objectively.
OG> I wonder why? and what can you offer in return?
KF>>>> You can count the plates.
VS>>> But it’s faster with a sign! (c) Valker.
KF>> THE PLATE CAN BE COUNTED IN PRELIMINARY, AND NOT STORE IN
KF>> program.
OG> logical, but how to do it?
Look at the sign and you will see a certain pattern.
Good luck!
Hello Vlad
VS> Hello, Kirill!
VS> May 10, 2003 (and it was 18:18 then)
VS> Kirill Frolov in his letter to Eugene Palenock wrote:
VK>>>> Give me a piece of code to calculate the subject!
EP>>> .data
EP>>> d_cr32 dd ?
EP>>> cr32t dd 000000000h, 077073096h, 0ee0e612ch, 0990951bah,
EP>>> 0076dc419h dd 0706af48fh, 0e963a535h, 09e6495a3h,
EP>>> 00edb8832h, 079dcb8a4h
KF>> The algorithm is terribly lame. You can count the tablet.
VS> But it’s faster with a sign! (c) Valker. Although x.z. what he needs:
VS> speed or free memory...
Yes, I have one black place each :) I write under Sprinter, there is a lot of memory, megahertz
too :) By the way, Vega, in your article on the screw, I saw the algorithm from MOA, as in it
should I remove the finalization? And who else has a thread for 32-bit arithmetic?
[ZX][Sprinter owner][rw1p2][NedoPC]
Bye
Hello, Vladimir!
Tuesday 6 May 2003 23:14:52, Vladimir Karpenko -> All:
VK> Give me a piece of code to calculate the subject! There are still
VK> question, I’ll suggest that I calculated the TRC for pieces of the file by
VK> 16k! What should I do with these pieces?
I have no idea what to do. Now I have a little time, I dug into the archives,
found something. Figure it out.
====Begin crc_1 .C====
==============================================================================
* Posted by Alexei Philippov (2:5004/45.33 3a6a709b) on Sunday 21 Jan 2001
05:13:20
* Region : RU.ALGORITHMS
* From: Alexei Philippov, 2:5004/45.33 MSGID 3a6a709b (Sunday 21 Jan 2001
05:13:20)
* To: Evgenij M. Baldin, sky.inp.nsk.su cf83832f
* Subject : Re: Recovery Record
==============================================================================
Delicious buns and sleepless nights to you, Evgenij!
Having written <19 Jan 01 at 19:35> a message for All,
Evgenij M. Baldin no longer hoped to receive
answer...
EB> TK: there is a binary file - you need to know this file
EB> restore
EB> with minor damage (that is, copying itself
EB> by yourself - EB> a good way to deal with damage, but I want to
EB> additional
EB> confidence)
You're not the first, you're not the last... hold on, maybe it will help.
part 1.
=== Start CRC.TXT ===
─ Algorithms in Russian :) (2:5004/45.33) ───────────────────────
RU.ALGORITHMS ─
From: Dmitry Tomashpolski 2:5030/163.167 06
Mar 00 18:21:06
Subject: CRC
─────────────────────────────── ────────────────────────────────
───────────────
M> What are CRC and CRC-32 and what algorithm can they be used
M> count?
Looks like I'll have to repeat it occasionally...
===============================================================================
========
Dmitry Tomashpolski, 2:5030/163.167@fidonet, toddy@mail.ru
04/03/1999
Calculation of various CRCs.
Briefly about the principle:
Method for checking the integrity of a bit array based on properties
operations
taking the remainder in polynomial arithmetic modulo 2 with
main
operations 0+0=0, 0+1=1, 1+0=1, 1+1=0, 0*0=0, 0*1=0, 1*0=0,
1*1=1.
[A detailed presentation of the theory can be found in the following
articles:
http://d1.ifmo.ru/up/crc/crc.htm
ftp://ftp.rocksoft.com/clients/rocksoft/papers/crc_v3.txt ]
CRC Cyclic Redundancy Check
control code)
the result of the operation of taking the remainder of the division of the thing being checked
bit array onsome divisor number that has specific
properties evenly
"smearing" a change in some bit of the array is not possible
more bits
result. This is a divisor number called a generator
polynomial, selected
so that it itself is polynomially simple - does not divide
polynomial
targets any numbers from 2 to itself.
In addition, there are other criteria for choosing a polynomial,
aimed at
reducing the likelihood of missing typical errors in channels
data transfer, so
that inventing polynomials on your own is not only difficult, but
and harmful.
The polynomial can be written as a sum of powers with
non-zero (and therefore
- unit) coefficients, coefficients, and a mask of these
one.
The order in which units are written in the mask is uniquely related to the order
bit processing
array being checked, because in the process of calculating the CRC
intermediate result
must be cyclically shifted in the same direction as the bits
being checked
array, and shift it so that the highest powers are displaced
polynomial The most
the highest degree in the mask is not taken into account, it only determines
number of mask bits.
Below, senior degrees are separated by spaces.
To implement checking using CRC, in addition to the mask
polynomial and
the order of the bits in the array (determining the direction
cyclical
shift), you need to know the initial CRC value and the method
finalmodification of the CRC calculation result.
Typical methods used to monitor data integrity
during transmission and
storage:
CCITT-CRC-32 [All common archivers and protocols with
CRC-32]
bits of the array are processed starting from the least significant bit in the byte -
L.S.B.
Generating polynomial:
X^0+X^1+X^2+X^4+X^5+X^7+X^8+X^10+X^11+X^12+X^16+X^22+X^23+X^26
+X^32
Mask = EDB88320h, in which the right digits correspond to the highest ones
degrees,
the shift is performed to the right.
The initial value is 0xFFFFFFFF.
The final modification is a bitwise inversion of all bits
result.
CCITT-DOS-16 [LHA archiver and probably some others with
CRC-16]
bits of the array are processed starting from the least significant bit in the byte -
L.S.B.
Generating polynomial: X^0+X^2+X^15 +X^16
Mask = A001h, in which the right digits correspond to the highest ones
degrees,
the shift is performed to the right.
The initial value is 0000.
There is no final modification.
CCITT-CRC-16 [Data transfer protocols with CRC-16, Control
EMSI]
bits of the array are processed starting from the most significant bit in the byte -
MSB.
Generating polynomial: X^16+ X^12+X^5+X^0
Mask = 0x1021, in which the left digits correspond to the highest ones
degrees,
the shift is performed to the left.
The initial value is 0x0000.
There is no final modification.
Now the actual description of the calculation:
Working variable W of the corresponding bit size, in which
will accumulate
The result is initialized with the initial value.Then for each bit m of the input array the following are executed:
actions:
W is shifted by 1 bit (for shift direction, see above)
A zero is placed in the freed bit W. Beat, just now
pushed out of W,
compares with bit m.
if they do not match, an exclusive OR operation is performed
over W and mask
polynomial, the result is entered in W.
And so on until all the bits of the array have been processed.
After which a final modification is made on W.
Hey here. And now we can say that this is how CRCs are usually considered
only in circuit diagrams
implementations. Because it is very slow - because the number of cycles
equal to the number of bits
array. When implemented at the program level, processing is carried out
bits in eights
- bytes.
A plate of 256 elements is started.
Each value is the result of calculating CRC over eight bits
element index:
for i := 0 to 255 do tab[i] := count_crc(i);
After this, the CRC for the array can be calculated in bytes.
The beginning and end of the calculation, as before. And the cycle goes on for everyone
byte Q:
W := W XOR Q;
W := shift(W, 8) XOR tab[ W ]
With LSB order Q, the XOR operation is performed on the least significant bits
W, and when
MSB order - above the elders. The index in the table is precisely
these bits.
The byte table method requires significant memory costs for
table. For
CRC-32 requires a kilobyte-sized table. If kilobyte
memory forimplementations with one cycle per byte of the array is overkill, you can
suggest
a compromise option is to count CRC, not in eights, but
in fours of bits.
A CRC-32 table of 16 values will take 64 bytes, but the speed
there will be several
lower than with a large table, although significantly higher than without
her at all.
How to count tables - in advance with a separate program, or on
execution stage
- it's a matter of your taste. What I strongly do not recommend doing is
take them whole
from dubious sources.
There is one subtlety in the implementation of CRC calculation for z-modem
moment. It's allowed there
deviation from the basic scheme. Two lines have been swapped:
W := shift(W, 8) XOR tab[ W ];
W := W XOR Q
The result is not a pure CRC: Control code
z-modem for
arrays of up to two bytes with a size “equal” to the array itself.
For example, for an array of
two bytes 3 and 8, the control code will be equal to 0308h.
[And finally, one small note. CRC calculation operation
reversible
Not in the sense, of course, that using CRC you can restore the entire
array, and
is that if a CRC of size N is given and some array is given,
in which
somewhere you can change N bits in a row, then adjust this
array under
given CRC is no more difficult than calculating CRC.
CRC is not a cryptographically strong hash function.]
The following is a program illustrating the calculation of CRC by all
above mentioned
methods:
#include
#include enum { CRC_32, CRC_ZMDM, CRC_LHA, CRC_CCITT };
char *tagcrc[] = {"CRC-32", "Z-modem CRC-16", "LHA CRC-16",
"CCITT CRC-16" };
unsigned long tb32[256];
unsigned short *tb16 = (unsigned short*)tb32;
#define POLY_32 0xEDB88320ul
#define LHA_POLY_16 0xA001u
#define CCITT_POLY_16 0x1021
void ilha(unsigned long *crcp) /* pасчет таблицы для LHA CRC-16
*/
{
unsigned short i, j, crc, v;
*crcp = 0;
for(crc = i = 0; i < 256; tb16[i++] = crc)
for(crc = i, j = 0; j < 8; j++)
v = -(crc & 1),
crc >>= 1,
crc ^= v & LHA_POLY_16;
};
void iccitt(unsigned long *crcp) /* pасчет таблицы для CCITT
CRC-16 */
{
unsigned short i, j, crc, v;
*crcp = 0;
for(crc = i = 0; i < 256; tb16[i++] = 0xFFFFu &
((crc<<8)^(crc>>8)) )
for(crc = i<<8, j = 0; j < 8; j++)
v = -((crc & 0x8000) !=0),
crc <<= 1,
crc ^= v & CCITT_POLY_16,
crc &= 0xFFFFu;
};
void i32(unsigned long *crcp) /* pасчет таблицы для CCITT
CRC-32 */
{
unsigned short i, j;
unsigned long crc, v;
*crcp = 0xFFFFFFFFul;
for(crc = i = 0; i < 256; tb32[i++] = crc)
for(crc = i, j = 0; j < 8; j++)
v = -(crc & 1),
crc >>= 1,
crc ^= v & POLY_32;
};
void t0(unsigned long *crc) { ++crc; };
void t32(unsigned long *crc) { *crc ^= 0xFFFFFFFFul; };void upd_32(unsigned long *crcp, unsigned size, char *buf)
{ /* обpабокта бyфеpа для CRC-32 */
unsigned i; unsigned long crc = *crcp;
for(i = 0; i < size; i++)
{
crc ^= *(unsigned char *)(buf+i);
crc = (crc >> 8) ^ tb32[(unsigned char)crc];
}
*crcp = crc;
}
void upd_lha(unsigned long *crcp, unsigned size, char *buf)
{ /* обpабокта бyфеpа для LHA CRC-16 */
unsigned i; unsigned crc = (unsigned)*crcp;
for(i = 0; i < size; i++)
{
crc ^= *(unsigned char *)(buf+i);
crc = (crc >> 8) ^ tb16[crc & 0xFF];
}
*crcp = crc;
}
void upd_zmdm(unsigned long *crcp, unsigned size, char *buf)
{ /* обpабокта бyфеpа для Z-modem CRC-16 */
unsigned i; unsigned crc = (unsigned)*crcp;
crc = 0xFFFFu & ((crc>>8)^(crc <<8));
for(i = 0; i < size; i++)
crc = (crc >> 8) ^ tb16[crc&0xFF],
crc ^= *(unsigned char *)(buf+i) << 8;
*crcp = 0xFFFFu & ((crc>>8)^(crc <<8));
}
void upd_ccitt(unsigned long *crcp, unsigned size, char *buf)
{ /* обpабокта бyфеpа для CCITT CRC-16 */
unsigned i; unsigned crc = (unsigned)*crcp;
crc = 0xFFFFu & ((crc>>8)^(crc <<8));
for(i = 0; i < size; i++)
crc ^= *(unsigned char *)(buf+i),
crc = (crc >> 8) ^ tb16[crc&0xFF];
*crcp = 0xFFFFu & ((crc>>8)^(crc <<8));
}
void (*initcrc[])(unsigned long *crcp) = { i32, iccitt, ilha,
iccitt };void (*termcrc[])(unsigned long *crcp) = { t32, t0, t0, t0 };
void (*updatecrc[])(unsigned long *crcp, unsigned size, char
*buffer)
= { upd_32, upd_zmdm, upd_lha,
upd_ccitt };
int main(int ac, char **av)
{ /* тестовая поделка */
FILE *f;
int method = 0;
unsigned long size, csize, crc;
unsigned psize, bs = 16384;
char *buffer;
if(ac < 2 || ac == 2 && *av[1] == '-')
return printf(
"CRC counter. Freeware. Version 0.01 03.04.1999
"
"Written By Dmitry Tomashpolski, 2:5030/163.167,
toddy@mail.ru
"
"Usage: %s [-option] file" "
"
"opions are:" "
"
"-Z - z-modem CRC-16" "
"
"-L - lha CRC-16" "
"
"-C - CCITT CRC-16" "
"
"-3 - CRC-32" "
", av[0]);
if(*av[1] == '-')
method = av[1][1], ++av;
switch(method)
{
case '3': default: method = CRC_32; break;
case 'Z': case 'z': method = CRC_ZMDM; break;
case 'L': case 'l': method = CRC_LHA; break;
case 'C': case 'c': method = CRC_CCITT; break;
}
if((f = fopen(av[1], "rb")) == 0)
return printf("Cannot open file '%s'
", av[1]);
fseek(f, 0l, SEEK_END);
size = ftell(f);
fseek(f, 0l, SEEK_SET);for(bs = 0x4000; (buffer = malloc(bs)) == 0; bs >>= 1) ;
initcrc[method](&crc); /* table calculation and initialization
states */
for(psize= 0, csize = size; csize != 0; csize -= psize)
{
psize = csize > bs ? bs : (unsigned) csize;
fread(buffer, psize, 1, f);
updatecrc[method](&crc, psize, buffer);
}
termcrc[method](&crc); /* final state modification
*/
printf("%s [%lu] %s = %0*lX
",
av[1], size, tagcrc[method], method ? 4:8,
crc);
return 0;
}
===============================================================================
====
─ Algorithms in Russian :) (2:5004/45.33) ───────────────────────
RU.ALGORITHMS ─
From: Konstantin Gilyov 2:5000/72 14
May 00 04:46:10
Topic: Checksum
─────────────────────────────── ────────────────────────────────
───────────────
KG>> whereas for CRC32 (within the constructive code length
KG>> - 2^31-1
KG>> bits) we have four, as a minimum (for short files
KG>> sometimes and also
KG>>more).
PK> Is it possible to change the data by adjusting the CRC32? Like
PK> somewhere
PK> used.Easily, with completely frivolous costs. That's why
linear codes
are fundamentally not suitable for constructing cryptographic
hash functions, and then
cyclic codes - even more so :)
KG>> distortion up to three bits (_any_), and in the case of one
KG>> distorted bit
KG>> also calculate exactly which bit is broken (and
KG>> fix it
KG>> accordingly),
PK> More details, how to localize?
Mm... Well, for example, the Meggita decoder definitely rules :)
features, its
A simplified version known as the error catching method.
For cyclic
equivalents of Hamming codes (which are CRC16 and CRC32, in
in particular), and
also
for constructions like Fire codes, nothing more significant
even better
not
invented for now, I guess.
The idea is simple: having received the syndrome (the value of the control digits
for accepted with
possible code word error), scroll through the same
kitchen, substituting
zeros instead of data until we see it in the register where we keep
control digits,
syndrome of any of the error configurations known to us. B
in particular for
single-bit errors are just a 1 in a bit,
corresponding erroneous with
taking into account the cyclic shift, and zeros in all others. For
cyclic packeterrors (in the case of Fire code or similar) - zeros in all
categories, except
the package itself, actually.
Considering the reversibility of all operations and the known length of the code,
you can scroll
both forward and backward. Where faster - depends on the ratio
this same length
code and data length. Usually it's faster to go back,
esssno :)
─ Algorithms in Russian :) (2:5004/45.33) ───────────────────────
RU.ALGORITHMS ─
From: Konstantin Gilyov 2:5000/72 14
May 00 06:03:16
Topic: Checksum
─────────────────────────────── ────────────────────────────────
───────────────
PK>> Is it possible to change the data while adjusting the CRC32? Like
PK>> somewhere
PK>> used.
IS> Naturally... You change the data, calculate crc32 again
IS> and none
IS> problem. I'm more interested in fitting the data to the crc rather than
IS> vice versa
IS> ;)
As I understand it, that’s exactly what Paul meant :) And
this is done before
It's just a disgrace. Any cyclic code, and CRC32 in this sense
no exception,
allows you to correct a package of so-called “erasures” (i.e.
possible errors with
known location) with a length equal to (or less than)
amount of excesscharacters in the code, within the length of the codeword (for CRC32, in
in particular, this
packet up to 32 bits in a codeword up to 2^31-1 bits).
That is, we change as we please the essential
data, "erase"
nafik 32 bits of something insignificant and then apply
correction procedure
"erasures". As a result, we get the set of data we need from that
same CRC :) This is
somewhat schematically, of course, in reality it may turn out to be
not really
a trivial task, to find these same 32 bits of “unnecessary” data,
but that's all
still remains somewhere in the same place ;)
─ Algorithms in Russian :) (2:5004/45.33) ───────────────────────
RU.ALGORITHMS ─
From: Max Alekseyev 2:5015/60 14
May 00 14:54:42
Topic: Checksum
─────────────────────────────── ────────────────────────────────
───────────────
IS> I am more interested in fitting the data to the crc and not vice versa
The following program uses the given CRC32 value to find 4
byte, value
CRC32 from which matches the specified one. For example:
Desired CRC32 = $12345678
Possible contents (hex): B2 07 1E B7
It is easy to check that CRC32 is from the sequence B2 07 1E B7
equals 12345678h.
===cut===
const nibble:array [0..15] of char='0123456789ABCDEF';
var crc,i:longint;
begin
writeln('Invert CRC32 (c) 2000 by RElf @ HHT/2');
write('Desired CRC32 = '); readln(crc);
crc:=not crc; for i:=1 to 32 do if crc<0 then crc:=(crc shl 1) xor
$DB710641
else crc:=crc shl 1;
crc:=not crc;
write('Possible contents (hex):');
for i:=0 to 3 do write('
Hello, Vladimir!
Tuesday 6 May 2003 23:14:52, Vladimir Karpenko -> All:
VK> Give me a piece of code to calculate the subject! There are still
VK> question, I’ll suggest that I calculated the TRC for pieces of the file by
VK> 16k! What should I do with these pieces?
I have no idea what to do. Now I have a little time, I dug into the archives,
found something. Figure it out.
====Begin crc_1 .C====
==============================================================================
* Posted by Alexei Philippov (2:5004/45.33 3a6a709b) on Sunday 21 Jan 2001
05:13:20
* Region : RU.ALGORITHMS
* From: Alexei Philippov, 2:5004/45.33 MSGID 3a6a709b (Sunday 21 Jan 2001
05:13:20)
* To: Evgenij M. Baldin, sky.inp.nsk.su cf83832f
* Subject : Re: Recovery Record
==============================================================================
Delicious buns and sleepless nights to you, Evgenij!
Having written <19 Jan 01 at 19:35> a message for All,
Evgenij M. Baldin no longer hoped to receive
answer...
EB> TK: there is a binary file - you need to know this file
EB> restore
EB> with minor damage (that is, copying itself
EB> by yourself - EB> a good way to deal with damage, but I want to
EB> additional
EB> confidence)
You're not the first, you're not the last... hold on, maybe it will help.
part 1.
=== Start CRC.TXT ===
─ Algorithms in Russian :) (2:5004/45.33) ───────────────────────
RU.ALGORITHMS ─
From: Dmitry Tomashpolski 2:5030/163.167 06
Mar 00 18:21:06
Subject: CRC
─────────────────────────────── ────────────────────────────────
───────────────
M> What are CRC and CRC-32 and what algorithm can they be used
M> count?
Looks like I'll have to repeat it occasionally...
===============================================================================
========
Dmitry Tomashpolski, 2:5030/163.167@fidonet, toddy@mail.ru
04/03/1999
Calculation of various CRCs.
Briefly about the principle:
Method for checking the integrity of a bit array based on properties
operations
taking the remainder in polynomial arithmetic modulo 2 with
main
operations 0+0=0, 0+1=1, 1+0=1, 1+1=0, 0*0=0, 0*1=0, 1*0=0,
1*1=1.
[A detailed presentation of the theory can be found in the following
articles:
http://d1.ifmo.ru/up/crc/crc.htm
ftp://ftp.rocksoft.com/clients/rocksoft/papers/crc_v3.txt ]
CRC Cyclic Redundancy Check
control code)
the result of the operation of taking the remainder of the division of the thing being checked
bit array onsome divisor number that has specific
properties evenly
"smearing" a change in some bit of the array is not possible
more bits
result. This is a divisor number called a generator
polynomial, selected
so that it itself is polynomially simple - does not divide
polynomial
targets any numbers from 2 to itself.
In addition, there are other criteria for choosing a polynomial,
aimed at
reducing the likelihood of missing typical errors in channels
data transfer, so
that inventing polynomials on your own is not only difficult, but
and harmful.
The polynomial can be written as a sum of powers with
non-zero (and therefore
- unit) coefficients, coefficients, and a mask of these
one.
The order in which units are written in the mask is uniquely related to the order
bit processing
array being checked, because in the process of calculating the CRC
intermediate result
must be cyclically shifted in the same direction as the bits
being checked
array, and shift it so that the highest powers are displaced
polynomial The most
the highest degree in the mask is not taken into account, it only determines
number of mask bits.
Below, senior degrees are separated by spaces.
To implement checking using CRC, in addition to the mask
polynomial and
the order of the bits in the array (determining the direction
cyclical
shift), you need to know the initial CRC value and the method
finalmodification of the CRC calculation result.
Typical methods used to monitor data integrity
during transmission and
storage:
CCITT-CRC-32 [All common archivers and protocols with
CRC-32]
bits of the array are processed starting from the least significant bit in the byte -
L.S.B.
Generating polynomial:
X^0+X^1+X^2+X^4+X^5+X^7+X^8+X^10+X^11+X^12+X^16+X^22+X^23+X^26
+X^32
Mask = EDB88320h, in which the right digits correspond to the highest ones
degrees,
the shift is performed to the right.
The initial value is 0xFFFFFFFF.
The final modification is a bitwise inversion of all bits
result.
CCITT-DOS-16 [LHA archiver and probably some others with
CRC-16]
bits of the array are processed starting from the least significant bit in the byte -
L.S.B.
Generating polynomial: X^0+X^2+X^15 +X^16
Mask = A001h, in which the right digits correspond to the highest ones
degrees,
the shift is performed to the right.
The initial value is 0000.
There is no final modification.
CCITT-CRC-16 [Data transfer protocols with CRC-16, Control
EMSI]
bits of the array are processed starting from the most significant bit in the byte -
MSB.
Generating polynomial: X^16+ X^12+X^5+X^0
Mask = 0x1021, in which the left digits correspond to the highest ones
degrees,
the shift is performed to the left.
The initial value is 0x0000.
There is no final modification.
Now the actual description of the calculation:
Working variable W of the corresponding bit size, in which
will accumulate
The result is initialized with the initial value.Then for each bit m of the input array the following are executed:
actions:
W is shifted by 1 bit (for shift direction, see above)
A zero is placed in the freed bit W. Beat, just now
pushed out of W,
compares with bit m.
if they do not match, an exclusive OR operation is performed
over W and mask
polynomial, the result is entered in W.
And so on until all the bits of the array have been processed.
After which a final modification is made on W.
Hey here. And now we can say that this is how CRCs are usually considered
only in circuit diagrams
implementations. Because it is very slow - because the number of cycles
equal to the number of bits
array. When implemented at the program level, processing is carried out
bits in eights
- bytes.
A plate of 256 elements is started.
Each value is the result of calculating CRC over eight bits
element index:
for i := 0 to 255 do tab[i] := count_crc(i);
After this, the CRC for the array can be calculated in bytes.
The beginning and end of the calculation, as before. And the cycle goes on for everyone
byte Q:
W := W XOR Q;
W := shift(W, 8) XOR tab[ W ]
With LSB order Q, the XOR operation is performed on the least significant bits
W, and when
MSB order - above the elders. The index in the table is precisely
these bits.
The byte table method requires significant memory costs for
table. For
CRC-32 requires a kilobyte-sized table. If kilobyte
memory forimplementations with one cycle per byte of the array is overkill, you can
suggest
a compromise option is to count CRC, not in eights, but
in fours of bits.
A CRC-32 table of 16 values will take 64 bytes, but the speed
there will be several
lower than with a large table, although significantly higher than without
her at all.
How to count tables - in advance with a separate program, or on
execution stage
- it's a matter of your taste. What I strongly do not recommend doing is
take them whole
from dubious sources.
There is one subtlety in the implementation of CRC calculation for z-modem
moment. It's allowed there
deviation from the basic scheme. Two lines have been swapped:
W := shift(W, 8) XOR tab[ W ];
W := W XOR Q
The result is not a pure CRC: Control code
z-modem for
arrays of up to two bytes with a size “equal” to the array itself.
For example, for an array of
two bytes 3 and 8, the control code will be equal to 0308h.
[And finally, one small note. CRC calculation operation
reversible
Not in the sense, of course, that using CRC you can restore the entire
array, and
is that if a CRC of size N is given and some array is given,
in which
somewhere you can change N bits in a row, then adjust this
array under
given CRC is no more difficult than calculating CRC.
CRC is not a cryptographically strong hash function.]
The following is a program illustrating the calculation of CRC by all
above mentioned
methods:
#include
#include enum { CRC_32, CRC_ZMDM, CRC_LHA, CRC_CCITT };
char *tagcrc[] = {"CRC-32", "Z-modem CRC-16", "LHA CRC-16",
"CCITT CRC-16" };
unsigned long tb32[256];
unsigned short *tb16 = (unsigned short*)tb32;
#define POLY_32 0xEDB88320ul
#define LHA_POLY_16 0xA001u
#define CCITT_POLY_16 0x1021
void ilha(unsigned long *crcp) /* pасчет таблицы для LHA CRC-16
*/
{
unsigned short i, j, crc, v;
*crcp = 0;
for(crc = i = 0; i < 256; tb16[i++] = crc)
for(crc = i, j = 0; j < 8; j++)
v = -(crc & 1),
crc >>= 1,
crc ^= v & LHA_POLY_16;
};
void iccitt(unsigned long *crcp) /* pасчет таблицы для CCITT
CRC-16 */
{
unsigned short i, j, crc, v;
*crcp = 0;
for(crc = i = 0; i < 256; tb16[i++] = 0xFFFFu &
((crc<<8)^(crc>>8)) )
for(crc = i<<8, j = 0; j < 8; j++)
v = -((crc & 0x8000) !=0),
crc <<= 1,
crc ^= v & CCITT_POLY_16,
crc &= 0xFFFFu;
};
void i32(unsigned long *crcp) /* pасчет таблицы для CCITT
CRC-32 */
{
unsigned short i, j;
unsigned long crc, v;
*crcp = 0xFFFFFFFFul;
for(crc = i = 0; i < 256; tb32[i++] = crc)
for(crc = i, j = 0; j < 8; j++)
v = -(crc & 1),
crc >>= 1,
crc ^= v & POLY_32;
};
void t0(unsigned long *crc) { ++crc; };
void t32(unsigned long *crc) { *crc ^= 0xFFFFFFFFul; };void upd_32(unsigned long *crcp, unsigned size, char *buf)
{ /* обpабокта бyфеpа для CRC-32 */
unsigned i; unsigned long crc = *crcp;
for(i = 0; i < size; i++)
{
crc ^= *(unsigned char *)(buf+i);
crc = (crc >> 8) ^ tb32[(unsigned char)crc];
}
*crcp = crc;
}
void upd_lha(unsigned long *crcp, unsigned size, char *buf)
{ /* обpабокта бyфеpа для LHA CRC-16 */
unsigned i; unsigned crc = (unsigned)*crcp;
for(i = 0; i < size; i++)
{
crc ^= *(unsigned char *)(buf+i);
crc = (crc >> 8) ^ tb16[crc & 0xFF];
}
*crcp = crc;
}
void upd_zmdm(unsigned long *crcp, unsigned size, char *buf)
{ /* обpабокта бyфеpа для Z-modem CRC-16 */
unsigned i; unsigned crc = (unsigned)*crcp;
crc = 0xFFFFu & ((crc>>8)^(crc <<8));
for(i = 0; i < size; i++)
crc = (crc >> 8) ^ tb16[crc&0xFF],
crc ^= *(unsigned char *)(buf+i) << 8;
*crcp = 0xFFFFu & ((crc>>8)^(crc <<8));
}
void upd_ccitt(unsigned long *crcp, unsigned size, char *buf)
{ /* обpабокта бyфеpа для CCITT CRC-16 */
unsigned i; unsigned crc = (unsigned)*crcp;
crc = 0xFFFFu & ((crc>>8)^(crc <<8));
for(i = 0; i < size; i++)
crc ^= *(unsigned char *)(buf+i),
crc = (crc >> 8) ^ tb16[crc&0xFF];
*crcp = 0xFFFFu & ((crc>>8)^(crc <<8));
}
void (*initcrc[])(unsigned long *crcp) = { i32, iccitt, ilha,
iccitt };void (*termcrc[])(unsigned long *crcp) = { t32, t0, t0, t0 };
void (*updatecrc[])(unsigned long *crcp, unsigned size, char
*buffer)
= { upd_32, upd_zmdm, upd_lha,
upd_ccitt };
int main(int ac, char **av)
{ /* тестовая поделка */
FILE *f;
int method = 0;
unsigned long size, csize, crc;
unsigned psize, bs = 16384;
char *buffer;
if(ac < 2 || ac == 2 && *av[1] == '-')
return printf(
"CRC counter. Freeware. Version 0.01 03.04.1999
"
"Written By Dmitry Tomashpolski, 2:5030/163.167,
toddy@mail.ru
"
"Usage: %s [-option] file" "
"
"opions are:" "
"
"-Z - z-modem CRC-16" "
"
"-L - lha CRC-16" "
"
"-C - CCITT CRC-16" "
"
"-3 - CRC-32" "
", av[0]);
if(*av[1] == '-')
method = av[1][1], ++av;
switch(method)
{
case '3': default: method = CRC_32; break;
case 'Z': case 'z': method = CRC_ZMDM; break;
case 'L': case 'l': method = CRC_LHA; break;
case 'C': case 'c': method = CRC_CCITT; break;
}
if((f = fopen(av[1], "rb")) == 0)
return printf("Cannot open file '%s'
", av[1]);
fseek(f, 0l, SEEK_END);
size = ftell(f);
fseek(f, 0l, SEEK_SET);for(bs = 0x4000; (buffer = malloc(bs)) == 0; bs >>= 1) ;
initcrc[method](&crc); /* table calculation and initialization
states */
for(psize= 0, csize = size; csize != 0; csize -= psize)
{
psize = csize > bs ? bs : (unsigned) csize;
fread(buffer, psize, 1, f);
updatecrc[method](&crc, psize, buffer);
}
termcrc[method](&crc); /* final state modification
*/
printf("%s [%lu] %s = %0*lX
",
av[1], size, tagcrc[method], method ? 4:8,
crc);
return 0;
}
===============================================================================
====
─ Algorithms in Russian :) (2:5004/45.33) ───────────────────────
RU.ALGORITHMS ─
From: Konstantin Gilyov 2:5000/72 14
May 00 04:46:10
Topic: Checksum
─────────────────────────────── ────────────────────────────────
───────────────
KG>> whereas for CRC32 (within the constructive code length
KG>> - 2^31-1
KG>> bits) we have four, as a minimum (for short files
KG>> sometimes and also
KG>>more).
PK> Is it possible to change the data by adjusting the CRC32? Like
PK> somewhere
PK> used.Easily, with completely frivolous costs. That's why
linear codes
are fundamentally not suitable for constructing cryptographic
hash functions, and then
cyclic codes - even more so :)
KG>> distortion up to three bits (_any_), and in the case of one
KG>> distorted bit
KG>> also calculate exactly which bit is broken (and
KG>> fix it
KG>> accordingly),
PK> More details, how to localize?
Mm... Well, for example, the Meggita decoder definitely rules :)
features, its
A simplified version known as the error catching method.
For cyclic
equivalents of Hamming codes (which are CRC16 and CRC32, in
in particular), and
also
for constructions like Fire codes, nothing more significant
even better
not
invented for now, I guess.
The idea is simple: having received the syndrome (the value of the control digits
for accepted with
possible code word error), scroll through the same
kitchen, substituting
zeros instead of data until we see it in the register where we keep
control digits,
syndrome of any of the error configurations known to us. B
in particular for
single-bit errors are just a 1 in a bit,
corresponding erroneous with
taking into account the cyclic shift, and zeros in all others. For
cyclic packeterrors (in the case of Fire code or similar) - zeros in all
categories, except
the package itself, actually.
Considering the reversibility of all operations and the known length of the code,
you can scroll
both forward and backward. Where faster - depends on the ratio
this same length
code and data length. Usually it's faster to go back,
esssno :)
─ Algorithms in Russian :) (2:5004/45.33) ───────────────────────
RU.ALGORITHMS ─
From: Konstantin Gilyov 2:5000/72 14
May 00 06:03:16
Topic: Checksum
─────────────────────────────── ────────────────────────────────
───────────────
PK>> Is it possible to change the data while adjusting the CRC32? Like
PK>> somewhere
PK>> used.
IS> Naturally... You change the data, calculate crc32 again
IS> and none
IS> problem. I'm more interested in fitting the data to the crc rather than
IS> vice versa
IS> ;)
As I understand it, that’s exactly what Paul meant :) And
this is done before
It's just a disgrace. Any cyclic code, and CRC32 in this sense
no exception,
allows you to correct a package of so-called “erasures” (i.e.
possible errors with
known location) with a length equal to (or less than)
amount of excesscharacters in the code, within the length of the code word (for CRC32, in
in particular, this
packet up to 32 bits in a codeword up to 2^31-1 bits).
That is, we change as we please the essential
data, "erase"
nafik 32 bits of something insignificant and then apply
correction procedure
"erasures". As a result, we get the set of data we need from that
same CRC :) This is
somewhat schematically, of course, in reality it may turn out to be
not really
a trivial task, to find these same 32 bits of “unnecessary” data,
but that's all
still remains somewhere in the same place ;)
─ Algorithms in Russian :) (2:5004/45.33) ───────────────────────
RU.ALGORITHMS ─
From: Max Alekseyev 2:5015/60 14
May 00 14:54:42
Topic: Checksum
─────────────────────────────── ────────────────────────────────
───────────────
IS> I am more interested in fitting the data to the crc and not vice versa
The following program uses the given CRC32 value to find 4
byte, value
CRC32 from which matches the specified one. For example:
Desired CRC32 = $12345678
Possible contents (hex): B2 07 1E B7
It is easy to check that CRC32 is from the sequence B2 07 1E B7
equals 12345678h.
===cut===
const nibble:array [0..15] of char='0123456789ABCDEF';
var crc,i:longint;
begin
writeln('Invert CRC32 (c) 2000 by RElf @ HHT/2');
write('Desired CRC32 = '); readln(crc);
crc:=not crc; for i:=1 to 32 do if crc<0 then crc:=(crc shl 1) xor
$DB710641
else crc:=crc shl 1;
crc:=not crc;
write('Possible contents (hex):');
for i:=0 to 3 do write('
Hello, Vladimir!
Tuesday 6 May 2003 23:14:52, Vladimir Karpenko -> All:
Catch the continuation:
====Begin crc_2 .C====
3:09:36
Subject : Re: Checksum
─────────────────────────────── ────────────────────────────────
───────────────
From: Vladimir Vassilevsky
> VV> The Meggit decoder is equivalent to brute force over all
> configurations
> VV> correctable
> VV> errors.
> This is not entirely true.
Meggitt's theorem allows you to beautifully get rid of the need
store
a complete table of all syndromes from correctable configurations
errors. However
the number of actions of the algorithm still turns out to be the same,
as with
searching through the table. And this, however, is a lot. For the same
binary code
Golay (23.12) will have to be done from zero to 2K iterations per code
word (in
depending on how the errors occurred). Ineffective.
> From what is in the canonical definition of the Meggit dekder
> the concept of a table of syndromes is present and implied
> search for it,
> at all
> does not mean that this table is physically obliged
> be present in
> implementations.Naturally. Everything is calculated along the way.
> There are many cases when the implementation of storing this table
> and search by
> with
> is easily replaced by trivial calculations.
And yet.
> VV> and only if no more than one is caught
> - two
> VV> errors,
> or a package from somewhere up to several dozen adjacent ones
> errors :)
The package is a simple case. Arbitrary configurations are much
more interesting.
> VV> and the code word is quite short.
> And it doesn’t matter, really. Catching errors with the decoder
> Meggita pri
> any
> the length of the word is comparable in complexity to calculating the syndrome
> from which
> all
> you can't get away with any decoding method.
If a block code of length n corrects k arbitrary errors, then
quantity
actions of the Meggit algorithm in the worst case will be equal to:
n + C(n,2) + C(n,3) + ....+ C(n,k). This is not interesting for
no matter how much
large n and k.
BTW, there are methods for decoding cyclic codes and without
calculationssyndromes, however, this does not make them any less
resource-intensive.
> And a separate question is how Berlekamp-Messi will help
> catching
> a bunch of bugs that Meggit copes with very well ;)
Counter question: build a Meggit decoder for the code
RS(255,233) ;)
Let's agree that each algorithm has its own area
applicability.
─ Algorithms in Russian :) (2:5004/45.33) ───────────────────────
RU.ALGORITHMS ─
From: Sergey Andrianov 2:5017/13.40 11
May 00 09:42:28
Topic: Checksum
─────────────────────────────── ────────────────────────────────
───────────────
MV> Explain, please, why XORka or a simple sum is worse than TsRTs32
MV> for
MV> detecting the fact of a file change.
The main idea is that it is ABSOLUTELY EXACTLY about the availability
mistakes are possible
you can only judge if you have an exact copy of the file (again, you need it
send by
communication lines, and where is the guarantee that a duplicate will not arise
same error
place itself), in the event of a reduction in the volume of verification
information probability
error detection is less than one. It's all about
maximize this
probability for a fixed test length
sequences.
Let's consider the simplest case - for control it is allocated
only 1 bit. Forcertainty, we also assume that the probability of correct
transfer one bit,
let's say 0.999, i.e. out of a thousand transmitted bits, on average one
comes with
mistake.
Let the peculiarity of our information transmission channel be as follows:
that every bit
transmitted independently of others. Then, if as
checksum we
Let's take the sum modulo 2 of all bits, we get that the probability
detection
unit error is equal to 1, the same applies to
odd number
errors. If there are an even number of errors, they will remain
undetected. But because
the probability of a double error is 1000 times less than a single one, we
catching
error with a probability of 99.9%. And this is with only one
check bit.
If the bits in the packet depend on the previous one, for example,
encoded by transition
from the bottom state to another, then in case of an error it will occur
phase reversal, in
As a result, all 1s become 0, and 0 - 1. We can make this error
catch at
this coding algorithm only in half of the cases, i.e.
probability
detection is already only 50%. But if we calculate
the control element is not
as the sum of all numbers, and as the number of transitions from 0 to 1 and
back,
probability
detection rate will increase again to 99.9%.
Thus, we found out that the method of calculating the control
code affects
the probability of detecting an error. Thus, it is necessary
find out the mainsource of errors and what type of errors it leads to, and already
after that
select an algorithm for generating a control code that
would
maximized the likelihood of detecting this type of error.
In other words, when transmitted over a telephone line, it may
turn out to be the most
the optimal way to calculate the control code when recording
to CD
- another, and on a magnetic medium - the third.
─ Algorithms in Russian :) (2:5004/45.33) ───────────────────────
RU.ALGORITHMS ─
From: Alexander Zigar' 2:5058/45.20 19
Jun 00 13:50:04
Subject: CRC 16 & 32
─────────────────────────────── ────────────────────────────────
───────────────
VG> People, what algorithms are used to calculate sayuzhi? Otherwise there are like
VG> a lot... Which
VG> standard?
dn.hlp:
How is CRC calculated?
────────────────────┘
CRC size is 16 bits. For each subsequent byte from point
tongue vision
In assembler it is calculated like this:
ror [word ptr ChkSum],1
movzx ax,[byte ptr CurrentByte]
add [word ptr ChkSum],ax
Before counting begins, [ChkSum] must be equal to zero.
- Start tape, then press any key. File CRC16.ASM --------
; Written by Chris Barrett (3:690/660.25)
; The following non table-based routine produces the same
CRC16's
; as required by the EMSI standard so I assume it's correct.; Released into the Public Domain
; Pass - DS:SI = pointer to the buffer
; - CX = length of the buffer
; Returns - DX = CRC16 of the buffer
CRC16 PROC NEAR
PUSH AX
PUSH BX
PUSHF
CLD ; Move forward through the
buffer
SUB DX,DX ; CRC := 0000h
C1: LODSB ; AL := byte at DS:SI
SUB AH,AH
XCHG AH,AL ; AX := 256 * AL
XOR DX,AX ; CRC := CRC xor AX
PUSH CX
MOV CX,8
C2: MOV BX,DX
SHL DX,1
AND BX,8000h
JZ C3
XOR DX,1021h
C3: LOOP C2
POP CX
LOOP C1
POPF
POP BX
POP AX
RET
CRC16 ENDP
--R Tape loading error 0:1 (file CRC16.ASM) -------------
- Start tape, then press any key. File CRC32.ASM --------
IDEAL
; This CRC-32 routine and tables were converted from code
discovered
; in the DEZIP.PAS V2.0 by R. P. Byrne. The comments there
are:
;
; Converted to Turbo Pascal (tm) V4.0 March, 1988 by J.R.Louvau
; COPYRIGHT (C) 1986 Gary S. Brown. You may use this program,
or
; code or tables extracted from it, as desired without
restriction.
;
; First, the polynomial itself and its table of feedback terms.
The
; polynomial is
;
X^32+X^26+X^23+X^22+X^16+X^12+X^11+X^10+X^8+X^7+X^5+X^4+X^2+X^1
X^0
;
; Note that we take it "backwards" and put the highest-order
term in
; the lowest-order bit. The X^32 term is "implied"; the LSB is
the
; X^31 term, etc. The X^0 term (usually shown as "+1") results
in
; the MSB being 1.
;
; Note that the usual hardware shift register implementation,
which
; is what we're using (we're merely optimizing it by doing
eight-bit
; chunks at a time) shifts bits into the lowest-order term. In
our
; implementation, that means shifting towards the right. Why
do we
; do it this way? Because the calculated CRC must be
transmitted in
; order from highest-order term to lowest-order term. UARTs
transmit
; characters in order from LSB to MSB. By storing the CRC this
way,
; we hand it to the UART in the order low-byte to high-byte;
the UART
; sends each low-bit to high-bit; and the result is
transmission bit
; by bit from highest- to lowest-order term without requiring
any bit
; shuffling on our part. Reception works similarly.
;
; The feedback terms table consists of 256, 32-bit entries.
Notes:
;
; The table can be generated at runtime if desired; code to
do so
; is shown later. It might not be obvious, but the
feedback
; terms simply represent the results of eight shift/xor
opera-
; tions for all combinations of data and CRC register
values.
;
; The values must be right-shifted by eight bits by the
"updcrc"
; logic; the shift must be unsigned (bring in zeroes). On
some
; hardware you could probably optimize the shift in
assembler by
; using byte-swap instructions.
; polynomial $edb88320
;
;
;
; The Pascal logic is:
;
; Function UpdC32(Octet: Byte; Crc: LongInt) : LongInt;
; Begin
;
; UpdC32 := CRC_32_TAB[Byte(Crc XOR LongInt(Octet))] XOR
((Crc SHR 8)
; AND $00FFFFFF);
;
; End {UpdC32};
;
; This routine computes the 32 bit CRC used by PKZIP and its
derivatives,
; and by Chuck Forsberg's "ZMODEM" protocol. The block CRC
computation
; should start with high-values (0ffffffffh), and finish by
inverting all
; bits.
;
; This TASM conversion done by:
;
; Edwin T. Floyd [76067,747]
; #9 Adams Park Ct.
; Columbus, GA 31909
; 404-576-3305 (work)
; 404-322-0076 (home)
;
; Borland's Turbo Assembler - TASM is required to assemble this
program.
;
SEGMENT code BYTE PUBLIC
ASSUME CS:code
; 0
crc32tab dd 000000000h, 077073096h, 0ee0e612ch, 0990951bah
dd 0076dc419h, 0706af48fh, 0e963a535h, 09e6495a3h
dd 00edb8832h, 079dcb8a4h, 0e0d5e91eh, 097d2d988h
dd 009b64c2bh, 07eb17cbdh, 0e7b82d07h, 090bf1d91h
; 1
dd 01db71064h, 06ab020f2h, 0f3b97148h, 084be41deh
dd 01adad47dh, 06ddde4ebh, 0f4d4b551h, 083d385c7h
dd 0136c9856h, 0646ba8c0h, 0fd62f97ah, 08a65c9ech
dd 014015c4fh, 063066cd9h, 0fa0f3d63h, 08d080df5h
; 2
dd 03b6e20c8h, 04c69105eh, 0d56041e4h, 0a2677172h
dd 03c03e4d1h, 04b04d447h, 0d20d85fdh, 0a50ab56bh
dd 035b5a8fah, 042b2986ch, 0dbbbc9d6h, 0acbcf940h
dd 032d86ce3h, 045df5c75h, 0dcd60dcfh, 0abd13d59h
; 3
dd 026d930ach, 051de003ah, 0c8d75180h, 0bfd06116h
dd 021b4f4b5h, 056b3c423h, 0cfba9599h, 0b8bda50fh
dd 02802b89eh, 05f058808h, 0c60cd9b2h, 0b10be924h
dd 02f6f7c87h, 058684c11h, 0c1611dabh, 0b6662d3dh
; 4
dd 076dc4190h, 001db7106h, 098d220bch, 0efd5102ah
dd 071b18589h, 006b6b51fh, 09fbfe4a5h, 0e8b8d433h
dd 07807c9a2h, 00f00f934h, 09609a88eh, 0e10e9818h
dd 07f6a0dbbh, 0086d3d2dh, 091646c97h, 0e6635c01h
; 5
dd 06b6b51f4h, 01c6c6162h, 0856530d8h, 0f262004eh
dd 06c0695edh, 01b01a57bh, 08208f4c1h, 0f50fc457h
dd 065b0d9c6h, 012b7e950h, 08bbeb8eah, 0fcb9887ch
dd 062dd1ddfh, 015da2d49h, 08cd37cf3h, 0fbd44c65h
; 6
dd 04db26158h, 03ab551ceh, 0a3bc0074h, 0d4bb30e2h
dd 04adfa541h, 03dd895d7h, 0a4d1c46dh, 0d3d6f4fbh
dd 04369e96ah, 0346ed9fch, 0ad678846h, 0da60b8d0h
dd 044042d73h, 033031de5h, 0aa0a4c5fh, 0dd0d7cc9h
; 7
dd 05005713ch, 0270241aah, 0be0b1010h, 0c90c2086h
dd 05768b525h, 0206f85b3h, 0b966d409h, 0ce61e49fh
dd 05edef90eh, 029d9c998h, 0b0d09822h, 0c7d7a8b4h
dd 059b33d17h, 02eb40d81h, 0b7bd5c3bh, 0c0ba6cadh
; 8
dd 0edb88320h, 09abfb3b6h, 003b6e20ch, 074b1d29ah
dd 0ead54739h, 09dd277afh, 004db2615h, 073dc1683h
dd 0e3630b12h, 094643b84h, 00d6d6a3eh, 07a6a5aa8h
dd 0e40ecf0bh, 09309ff9dh, 00a00ae27h, 07d079eb1h
; 9
dd 0f00f9344h, 08708a3d2h, 01e01f268h, 06906c2feh
dd 0f762575dh, 0806567cbh, 0196c3671h, 06e6b06e7h
dd 0fed41b76h, 089d32be0h, 010da7a5ah, 067dd4acch
dd 0f9b9df6fh, 08ebeeff9h, 017b7be43h, 060b08ed5h
; A
dd 0d6d6a3e8h, 0a1d1937eh, 038d8c2c4h, 04fdff252h
dd 0d1bb67f1h, 0a6bc5767h, 03fb506ddh, 048b2364bh
dd 0d80d2bdah, 0af0a1b4ch, 036034af6h, 041047a60h
dd 0df60efc3h, 0a867df55h, 0316e8eefh, 04669be79h
; B
dd 0cb61b38ch, 0bc66831ah, 0256fd2a0h, 05268e236h
dd 0cc0c7795h, 0bb0b4703h, 0220216b9h, 05505262fh
dd 0c5ba3bbeh, 0b2bd0b28h, 02bb45a92h, 05cb36a04h
dd 0c2d7ffa7h, 0b5d0cf31h, 02cd99e8bh, 05bdeae1dh
; C
dd 09b64c2b0h, 0ec63f226h, 0756aa39ch, 0026d930ah
dd 09c0906a9h, 0eb0e363fh, 072076785h, 005005713h
dd 095bf4a82h, 0e2b87a14h, 07bb12baeh, 00cb61b38h
dd 092d28e9bh, 0e5d5be0dh, 07cdcefb7h, 00bdbdf21h
; D
dd 086d3d2d4h, 0f1d4e242h, 068ddb3f8h, 01fda836eh
dd 081be16cdh, 0f6b9265bh, 06fb077e1h, 018b74777h
dd 088085ae6h, 0ff0f6a70h, 066063bcah, 011010b5ch
dd 08f659effh, 0f862ae69h, 0616bffd3h, 0166ccf45h
; E
dd 0a00ae278h, 0d70dd2eeh, 04e048354h, 03903b3c2h
dd 0a7672661h, 0d06016f7h, 04969474dh, 03e6e77dbh
dd 0aed16a4ah, 0d9d65adch, 040df0b66h, 037d83bf0h
dd 0a9bcae53h, 0debb9ec5h, 047b2cf7fh, 030b5ffe9h
; F
dd 0bdbdf21ch, 0cabac28ah, 053b39330h, 024b4a3a6h
dd 0bad03605h, 0cdd70693h, 054de5729h, 023d967bfh
dd 0b3667a2eh, 0c4614ab8h, 05d681b02h, 02a6f2b94h
dd 0b40bbe37h, 0c30c8ea1h, 05a05df1bh, 02d02ef8dh
MODEL TPASCAL
PUBLIC UpdateCRC32
PROC UpdateCRC32 FAR initcrc:DWORD,inbuf:DWORD,inlen:WORD
; UpdateCRC32 takes an initial CRC value and updates it with
inlen bytes from
; inbuf. The updated CRC is returned in DX:AX. The Pascal
declaration is:
; Function UpdateCRC32(InitCRC : LongInt; Var InBuf; InLen :
Word) : LongInt;
; Stomps registers: AX,BX,CX,DX,ES,SI
push DS
lds si,[inbuf] ; ds:si := ^inbuf
les ax,[initcrc] ; dx:ax := initcrc
mov dx,ES
mov cx,[inlen] ; cx := inlen
; or cx,cx
; jz @@done
jcxz @@done
@@loop:
xor bh,bh
mov bl,al
lodsb
xor bl,al
mov al,ah
mov ah,dl
mov dl,dh
xor dh,dh
shl bx,1
shl bx,1
les bx,[crc32tab+bx]
xor ax,bx
mov bx,ES
xor dx,bx
loop @@loop
@@done:
pop DS
ret
ENDP
ENDS
END
--R Tape loading error 0:1 (file CRC32.ASM) -------------
─ Алгоpитмы по-pyсски :) (2:5004/45.33) ───────────────────────
RU.ALGORITHMS ─
От : Slava Chernenko 2:4625/44.35 28
Дек 99 13:55:34
Тема : Коды с восстановлени ем инфоpмации
───────────────────────────────────────────────────────────────
───────────────
SC>> Код Рида-Соломона относится к классy циклических кодов. SC>> Allows you to identify and correct high-magnitude errors.
SC>> If I'm not mistaken, it has particularly good performance indicators
SC>> error packet correction, used for encoding
SC>> information in SD-roms.
KG>
KG> Not quite right. Reed-Solomon codes, like others
KG> related
KG> to the class of BCH codes, allow detection and correction
KG> _arbitrary_
KG> error configurations. For effective detection and
KG> corrections
KG> large _packets_ of errors in the CD-ROM are used
KG> on them
KG> based on a very non-trivial and interesting CIRC cascade code
KG> (Cross-Interleave Reed-Solomon Code).
Maybe the classifications of codes differ in different literature, but...
Information coding, binary codes. Directory. :
Cyclic codes are a type
systematic
codes and therefore have all their properties...
Cyclic Hamming codes Cyclic codes with
the minimum code distance Dmin = 3 are
a type of Hamming code. These codes are capable
correctsingle nightly errors or detect all single and
double
errors. Unlike group Hamming codes in cyclic
codes, check digits are placed at the end of the code
combinations...
Boyz-Chowdhury-Hocquenghem (BCH) codes These codes
are a type of cyclic codes...Kodi BCHH
have an odd value of the minimum code distance dmin...
Fire codes are the more famous cyclic code,
which
fixes single batches of errors...
Abramson codes require fewer check characters,
than
Fire codes... Abranson found a class of codes that allows
correct
batches of errors of length b=3 or less...
Reed-Solomon codes. Under _certain_conditions_ _cyclic_
codes
Reed-Solomon (RS) codes are a special case of BCH codes. RS codes
have
enormous corrective ability and allow you to correct
several
bunch of errors...
Thus, we find that the Reed-Solomon codes are
cyclic codes
and only when certain conditions are met are they classified as private
by chance
BCH codes. In addition to RS and BCHh, the cyclic class includes
cyclic codes
Hemming, Firey, Abramson codes and many others, more
exotic codes,
descriptions of which I did not provide.
KG> Richard E. Blahut, Theory and practice of error control
KG> codes, KG> Addison-Wesley, Amsterdam, 1984.
KG>
KG> There is a Russian translation:
KG>
KG> R. Bleykhyt, Theory and practice of error-control codes
KG> Moscow,
KG> "MIR", 1986.
KG>
KG> The book is truly magnificent in its own way
KG> content and
KG> quality of material presentation.
Since we were forced to delve into the archives, here’s another list
literature
1. Berezyuk H.T., Andryshchenko A.G. etc. "Encoding information
(binary
codes)" Kharkov: Vishcha School, 1978, 252 p.
2. Kuzmin I.V., Kedrys V.A. "Fundamentals of information theory and
coding"
K.: Vishcha School, 1986, 238 p.
3. Tsymbal V.P. “Information and coding theory” K.: Vishcha school,
1982, 304 p.
4. Zhyrakovsky Yu.P. "Transfer of information to the State Aviation Administration" K.: Vishcha school,
1991, 216 p.
5. Bleyhut Richard E "Theory and practice of codes that control
errors"
M.:Mir, 1986
6. Peterson W. Weldon E. “Error Correcting Codes” M.: Mir,
1976
7. McWilliams F.J. Sloan H.J. "The theory of stakes that correct
errors"
M.:Svyaz, 1979
8. Kolesnik V.D. Mironchikov E. "Decoding cyclic
codes"
M.:Svyaz, 1968, 252 p.
===End CRC.TXT ===
Alyoshka Filippov AKA
Filya
====End crc_2 .C====Best regards, Dmitriy.