CRC

Hello everyone! Code geniuses, I come to you! Please rewrite this calculation routine subject from the shadow market so that it takes up a minimum of space, that is, not I would use a table (I know that the procedure will be slower): ;Cyclic Redundancy Check. ;Calculation of checksum. ;IN : [DE] - START, [BC] - LENGHT ;OUT: [DE] - CRC-SUMM. CRC LD HL,#FFFF PUSH IX PUSH DE POP IX EX DE,HL CRC_1 LD HL,CRC_TAB LD A,(IX) INC IX XOR E ADD A,L LD L,A JR NC,CRC_2 INC H CRC_2 LD A,D XOR (HL) LD E,A INC HL XOR A XOR (HL) LD D,A DEC B.C. LD A,C OR B JR NZ,CRC_1 POP IX RET CRC_TAB DEFW #0000,#1021,#2042,#3063 DEFW #4084,#50A5,#60C6,#70E7 DEFW #8108,#9129,#A14A,#B16B DEFW #C18C,#D1AD,#E1CE,#F1EF DEFW #1231,#0210,#3273,#2252 DEFW #52B5,#4294,#72F7,#62D6 DEFW #9339,#8318,#B37B,#A35A DEFW #D3BD,#C39C,#F3FF,#E3DE DEFW #2462,#3443,#0420,#1401 DEFW #64E6,#74C7,#44A4,#5485 DEFW #A56A,#B54B,#8528,#9509 DEFW #E5EE,#F5CF,#C5AC,#D58D DEFW #3653,#2672,#1611,#0630 DEFW #76D7,#66F6,#5695,#46B4 DEFW #B75B,#A77A,#9719,#8738 DEFW #F7DF,#E7FE,#D79D,#C7BC DEFW #48C4,#58E5,#6886,#78A7 DEFW #0840,#1861,#2802,#3823 DEFW #C9CC,#D9ED,#E98E,#F9AF DEFW #8948,#9969,#A90A,#B92B DEFW #5AF5,#4AD4,#7AB7,#6A96 DEFW #1A71,#0A50,#3A33,#2A12 DEFW #DBFD,#CBDC,#FBBF,#EB9E DEFW #9B79,#8B58,#BB3B,#AB1A DEFW #6CA6,#7C87,#4CE4,#5CC5 DEFW #2C22,#3C03,#0C60,#1C41 DEFW #EDAE,#FD8F,#CDEC,#DDCD DEFW #AD2A,#BD0B,#8D68,#9D49 DEFW #7E97,#6EB6,#5ED5,#4EF4 DEFW #3E13,#2E32,#1E51,#0E70 DEFW #FF9F,#EFBE,#DFDD,#CFFC DEFW #BF1B,#AF3A,#9F59,#8F78 DEFW #9188,#81A9,#B1CA,#A1EB DEFW #D10C,#C12D,#F14E,#E16F DEFW #1080,#00A1,#30C2,#20E3 DEFW #5004,#4025,#7046,#6067 DEFW #83B9,#9398,#A3FB,#B3DA DEFW #C33D,#D31C,#E37F,#F35E DEFW #02B1,#1290,#22F3,#32D2 DEFW #4235,#5214,#6277,#7256 DEFW #B5EA,#A5CB,#95A8,#8589 DEFW #F56E,#E54F,#D52C,#C50D DEFW #34E2,#24C3,#14A0,#0481 DEFW #7466,#6447,#5424,#4405 DEFW #A7DB,#B7FA,#8799,#97B8 DEFW #E75F,#F77E,#C71D,#D73C DEFW #26D3,#36F2,#0691,#16B0 DEFW #6657,#7676,#4615,#5634 DEFW #D94C,#C96D,#F90E,#E92F DEFW #99C8,#89E9,#B98A,#A9AB DEFW #5844,#4865,#7806,#6827 DEFW #18C0,#08E1,#3882,#28A3 DEFW #CB7D,#DB5C,#EB3F,#FB1E DEFW #8BF9,#9BD8,#ABBB,#BB9A DEFW #4A75,#5A54,#6A37,#7A16 DEFW #0AF1,#1AD0,#2AB3,#3A92 DEFW #FD2E,#ED0F,#DD6C,#CD4D DEFW #BDAA,#AD8B,#9DE8,#8DC9 DEFW #7C26,#6C07,#5C64,#4C45 DEFW #3CA2,#2C83,#1CE0,#0CC1 DEFW #EF1F,#FF3E,#CF5D,#DF7C DEFW #AF9B,#BFBA,#8FD9,#9FF8 DEFW #6E17,#7E36,#4E55,#5E74 DEFW #2E93,#3EB2,#0ED1,#1EF0 Stanislav

Press RESET immediately, Stanislav! 27 Jul 01 20:28, Stanislav Udin wrote to All: SU> Code geniuses, I turn to you! Please rewrite this subroutine SU> calculating the subject from the shadow so that it takes up a minimum of space, then SU> would not use the table (I know that the procedure will become SU> slower): There are 2 options: 1. Rewrite the algorithm without a table, but it will take longer work -- byte-by-byte XOR is replaced by scrolling each byte bitwise and XOR with polynomial. 2. Dynamically build a table as needed freely memory (for example, a buffer for working with a disk). More on the polynomial later. First, here is the program to generate your table: CRCPOLY equ 0x1021 ; for CCITT CRCINIT equ 0 crc_table ds 0x100*2 init_crctable: ldhl,0 add hl, sp exx di ld sp, 0x100*2+crc_table ld de, CRCPOLY ld c, 0 @@byte: ld l, 0 ld h, c dec h ld b, 8 @@nbit: add hl, hl jr c, @@nxor ld a, l xor e ld l, a ld a, h xor d ld h, a @@nxor: djnz @@nbit push hl dec c jr nz, @@byte exx ld sp, hl ei retBut CRCPOLY is the polynomial by which the code is calculated. Next is my program for calculating CRC from a table. CRCINIT is the initial value for the code, usually 0, and MOA has 0xFFFF. ; hl = data ptr, bc = size of block --> hl=crc crc_count: ld de, CRCINIT @@byte: ld a, b or c jr z, @@end ld a, d xor (hl) exx ld h, crc_table/256 scf adc a,crc_table256 jr nc, @@nc inc h @@nc: ld l, a ld a, (hl) exx xor e ld d,a exx dec hl ld a, (hl) exx ld e, a dec bc inc hl jr @@byte @@end: ex de, hl ret Here is a MOA program for comparison. Differs in CRCINIT and others in order bytes in the CRC code. SU> ;Cyclic Redundancy Check. SU> ;Calculating the checksum. SU> ;IN : [DE] - START, [BC] - LENGHT SU> ;OUT: [DE] - CRC-SUMM. SU> CRC LD HL,#FFFF SU> PUSH IX SU> PUSH DE SU> POP IX SU> EX DE,HL SU> CRC_1 LD HL,CRC_TAB SU> LD A,(IX) SU> INC IX SU> XOR E SU> ADD A,L SU> LD L,A SU> JR NC,CRC_2 SU> INC H SU> CRC_2 LD A,D SU> XOR (HL) SU> LD E,A SU> INC HL SU> XOR A SU> XOR (HL) SU> LD D,A SU> DEC BC SU> LD A,C SU> OR B SU> JR NZ,CRC_1 SU> POP IX SU> RET Собственно нужная тебе программа для медленного рассчёта без таблицы: CRCPOLY equ 0x1021 CRCINIT equ 0xffff CRCMOA equ 1 ; ix=data pointer, de=size --> hl=crc16 code crc16: ld hl, CRCINIT jr @@byteloop @@crcnext: dec de ld c, (ix) inc ix ld b, 8 @@bitloop: rl c adc hl, hl jr nz, @@bitzero ld a, l xor CRCPOLY/0x100 ld l, a ld a, h xor CRCPOLY%0x100ld h, a @@bitzero: djnz @@bitloop @@byteloop: ld a, d or e jr nz, @@crcnext .if CRCMOA .ne 0 ld a, l ld l, h ld h, a .endif ret p.s.: I haven’t checked, bugs can be present in any quantity! p.p.s.: if it works, make public the program for switching. (What is it switching there in Scorpio?)

Press RESET immediately, Stanislav! 28 Jul 01 20:13, Stanislav Udin wrote to Kirill Frolov: KF>> There are 2 options: KF>> 1. Rewrite the algorithm without a table, but it will be KF>> takes longer - byte-byte XOR is replaced KF>> by scrolling each byte bit by bit and XOR with KF>> polynomial. SU> This is what I need! I'm afraid it won't work. Lamerchenko (I'm not afraid of this word!) made a bug! KF>> 2. Dynamically build the table as needed KF>> free memory (for example, a buffer for working with KF>> disk). SU> In principle, this is also an acceptable option, if it does not work longer SU> than option No. 1 Probably... KF>> More about the polynomial further. First, here is the program for generating KF>> of your table: SU> [skip] SU> I entered your procedure into ALASM, launched it, but... the resulting table SU> is different from what MOA proposed :(If you looked at it more carefully, you would find that It's the same thing, only backwards. Reverse it (2 byte words) necessary. KF>> Next is my program for calculating CRC from a table. KF>> CRCINIT - the initial value for the code, usually 0, and MOA KF>> 0xFFFF. SU> I tried this procedure, but alas, the resulting CRC differs from the one SU> what the MOA algorithm calculates. Of course! And also Lamerchenko. Made the same mistake! And the CRC is different due to the fact that the table in memory is upside down. KF>> Actually the program you need for slow calculation without KF>> tables: SU> I entered it last, but no miracle happened and the resulting code was SU> is also different from what the MOA procedure calculates:((( And this is the correct program for calculating CRC... In general, MOA is considered to be simply a control code, not a CRC. But the whole point is a bug - addressing an element in an array of 2-byte words he forgot the index added to the address of the beginning of the array multiply by the size of the array element. In short, there are 512 bytes in the table in reality only the first 256 are used. Naturally no polynomial This option will not work. KF>> p.s.: I haven’t checked, bugs can be present in any KF>> quantities! SU> I don’t understand the essence of the algorithm at all, so I can’t catch bugs :( This is no longer an algorithm... There are still 2 options: 1. Dynamically build a 256-byte table. 2. When any element is required tables calculate it using the latter my program. Choose what suits you best in terms of memory space and speed. If you have a volume of data for which the control is calculated no more than 256 bytes, then building the entire table at once does not make sense. For some reason it seems to me that you have exactly 256 bytes... A hybrid of options 1 and 2 is possible, when each element of the table can may or may not be present in the table. The table is initially empty and the program works according to option 2, but after calculating each element enters it into the table. If there is an element in the table, then it is already calculated no need - the acceleration is obvious. Well, the fact is that in your data, for which the control code is considered, there will be repeated bytes often I have no doubt. In general, here is a progressive algorithm for you: static uchar crctab[256][2], b; ushort getcrctab(uchar byte) { ushort crc; int bit; if(!crctab[byte][0]) {crc=(byte>>1)<<8; for(bit=0; bit<8; bit++) crc=(crc<<1)^((crc&0x8000!=0)?0:CCPOLY); crctab[byte&0xfe][0]=crctab[byte|1][0]=1; crctab[byte&0xfe][1]=crc&0xff; crctab[byte|1][1]=crc>>8; } return crctab[byte][1]; } ushort ccode (void *data, int size) { ushort cc; cc=0xffff; if (!size) return cc; bzero(crctab, sizeof(crctab)); while (size--) { b= *((uchar*)data++)^(cc&0xff); cc=(cc>>8)^getcrctab(b); cc|=getcrctab(++b)<<8; } return cc; } /* of course there may be a number of errors in the program, but I hope the algorithm is clear */ KF>> p.s.: if it works, publish the program for switching. KF>> (what does it switch in Scorpio?) SU> I need this not to switch something, but to support the screw in mine SU> commander, who, among other things, you do not accept due to your convictions. Doesn't matter, will it switch disks? It will be useful to someone else. SU> P.P.S. For which assembler did you provide the source code? For no reason. The syntax is something compatible with M80, Ma80...

Hello Kirill! 29 Jul 01 06:31, Kirill Frolov -> Stanislav Udin: SU>> I entered your procedure into ALASM, launched it, but... the resulting table SU>> differs from the one proposed by MOA :( KF> If you looked at it more carefully, you would find that KF> this is the same thing, only backwards. Reverse it (2 bytes KF> in words) necessary. Hmm... I just looked again... you're right... But not double-byte, but that's all there goes byte byte backwards. SU>> I tried this procedure, but alas, the resulting CRC differs from SU>> the one that the MOA algorithm calculates. KF> Of course! And also Lamerchenko. I made the same mistake! KF> And the CRC is different due to the fact that the table in memory is upside down. I see. But why is it still impossible to write an algorithm without a table? Yes and a table As far as I understand, you can generate an inverted one like MOA. KF>>> Actually the program you need for slow calculation without KF>>> tables: SU>> I entered it last, but the miracle did not happen and the received one SU>> code is also different from what the MOA procedure calculates:((( KF> And this is the correct program for calculating CRC... And MOA said that he had neither CRC16 nor CRC32, but something in between. KF> In general, MOA is considered to be simply a control code, not a CRC. KF> And the whole point is a bug - addressing an element in an array of 2 byte words KF> he forgot the index added with the address of the beginning of the array to multiply KF> by the size of the array element. In short, there are 512 bytes in the table KF> only the first 256 are actually used. Naturally, no polynomial KF> will not fit this option. Well, it’s his problem that he forgot there... KF>>> p.s.: I haven’t checked, bugs can be present in any KF>>> quantities! SU>> I don’t understand the essence of the algorithm at all, so I can’t catch bugs SU>> :( KF> This is no longer an algorithm... Option 2 as before: KF> 1. Dynamically build a 256-byte table. I myself am not able to write such a program because I still don’t understand algorithm. KF> 2. When any element is required KF> tables calculate it using the last one KF> of my program. KF> Choose what suits you best in terms of memory footprint and speed KF> work. In principle, you can use a copy buffer under the table. So now the main thing is speed. KF> If you have a volume of data for which the control is calculated KF> no more than 256 bytes, then building the entire table at once does not make sense. KF> For some reason it seems to me that you have exactly 256 bytes... No, I have 508 bytes. KF> A hybrid of options 1 and 2 is possible, when each element of the table KF> may or may not be present in the table. In the beginning KF> the table is empty and the program works according to option 2, but after calculation KF> of each element enters it into the table. If there is an element in the table then KF> there is no need to calculate it - the acceleration is obvious. Well, what’s in yours KF> data for which the control code is considered will occur frequently KF> repeating bytes, I have no doubt.Only the space for the table will be as I wrote above in the copy buffer, so the table will crash every time. KF> In general, here is a progressive algorithm for you: [skip] KF> /* of course there may be a number of errors in the program KF> but I hope the algorithm is clear */ No, I don’t know “this” (or what this algorithm is based on), I’m only familiar with ZX-Basic and its asm. SU>> I need this not to switch something, but to support the screw in SU>> my commander, who, among other things, you do not accept due to your own SU>> beliefs. KF> It doesn’t matter, will it switch disks? Will it be useful to someone KF> more. In principle, everything has already been described by Vlad Sotnikov, I’m just doing it in relation to my personal goals. SU>> P.P.S. For which assembler did you provide the source code? KF> For what purpose. The syntax is something compatible with M80, Ma80... Oh, I was tormented while I had all this running in ALSMA, I had to Almost everything needs to be typed manually. Stanislav

Press RESET immediately, Stanislav! 29 Jul 01 20:30, Stanislav Udin wrote to Kirill Frolov: SU>>> the resulting table differs from the one proposed by MOA :( KF>> this is the same thing, only backwards. Turn it over (2 SU> Hmm... I just looked again... you're right... But not double-byte ones, but SU> everything there goes backwards, byte-by-byte. There's probably jr c confused with jr nc... KF>> Of course! And also Lamerchenko. I made the same mistake! KF>> And the CRC is different due to the fact that the table in memory is upside down. SU> I see. But why is it still impossible to write an algorithm without a table? It's possible. But this is not a CRC anymore. SU> Yes, and as far as I understand, the table can be generated inverted like y SU> MOA. It's possible. Today, or rather yesterday, I posted examples in C and ACMA here, It probably hasn't arrived yet. KF>> And this is the correct program for calculating CRC... SU> And MOA said that he had neither CRC16 nor CRC32, but something in between. Yes, this is not cyclic code at all. I don't know what to call it. KF>> 1. Dynamically build a 256-byte table. SU> I myself am not able to write such a program because I still don’t SU> I understand the algorithm. The table is taken for the program for calculating the 16-bit cyclic control code. For the table generation algorithm, see the example in C (already sent). Function This algorithm directly follows from the bitwise algorithm for calculating CRC. Well MOA the program is already a tabular algorithm with an error, it differs from the bitwise one in that what 8 shifts for each bit are replaced by 1 shift of 8 bits and XOR. SU> In principle, you can use a copy buffer under the table. So SU> now the main thing is speed. Option with dynamic table construction being rewritten in ASMA can take on quite a size. I just saw another one in REAL.SPECCY algorithm. I don’t understand how it works at all. :-( ) Maybe it will suit you because obviously faster than what I offer. [...] KF>> /* of course, a certain number is possible in the program KF>> errors, but I hope the algorithm is clear */ SU> No, I don’t know “this” (or what this algorithm is based on), I’m familiar with it SU> only ZX-Basic and its asm. Study, study and study again! KF>> It doesn’t matter, will it switch disks? Will come in handy KF>> to someone else. SU> In principle, everything has already been described by Vlad Sotnikov, I just do it This is a method with a table of monstrous size (and in this table half is not needed)? SU> Oh, I was tormented while I had all this running in ALSMA SU> I had to type almost everything manually. Search and replace doesn't work there?

Press RESET immediately, Vlad! 30 Jul 01 07:12, Vlad Sotnikov wrote to Kirill Frolov: KF>> after calculating each element, enters it into the table. If KF>> there is an element in the table, so there is no need to calculate it - acceleration VS> But this is stupid! The fastest option is to use VS> tables. I provided the results of running the test on an offtopic site... And for the table you need to statically allocate a piece of memory of 257 bytes. VS> Here a person needs just the smallest procedure for any VS> speed. So why bother with such speed? Well, that’s true, theoretical speculation... But in practice, the entire table store it is not included in the launched file (it is not even compressed by packers!). VS> Moreover, checking for the presence of a value will not be close VS> in its size to the size of the table? :) It won't, although the code will certainly be bloated. The sector for which it is necessary to calculate has 512 bytes long? Need to switch disks? Discs switch relatively rarely? Then why use high-speed methods at all?

Hello Stanislav! Saturday 28 July 2001 20:13:38 Stanislav Udin -> Kirill Frolov: [ ] KF>> There are 2 options: KF>> 1. Rewrite the algorithm without a table, but it KF>> will be longer KF>> work -- byte-byte XOR is replaced KF>> scrolling KF>> each byte KF>> by bits and XOR with a polynomial. SU> This is what I need! This will not work, since the MOA is not considered to have CRC, but It’s not clear what. There is a missing multiplication by 2 when calculating the address in the table. And of the entire table, 257 bytes are used. The rest you can throw it away. [...] SU> I entered your procedure into ALASM, launched it, but... received SU> table is different from SU> the one proposed by MOA :( Try this procedure: MakeTab ld ix,Tab ld c,127 ld de,1021h m1 ld a,c sub 127 ld h,a ld l,0 ld b,8 m2 add hl,hl jr nc,m3 ld a,h xor d ld h,a ld a,l xor e ld l,a m3 djnz m2 ld(ix),l inc ix ld(ix),h inc ix inc c jr nz,m1 ret Tab ds 258 Sergei.