ZXNet эхоконференция «code.zx»

Привет all! Гении кода, обращаюсь к вам! Перепишите, пожалуйста, эту подпрограмму расчета сабжа из теневика так, чтобы она занимала минимум места, то есть не использовала бы таблицу (знаю, что процедура станет медленнее): ;Cyclic Redundancy Check. ;Подсчет контрольной суммы. ;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 BC 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

Hемедленно нажми на RESET, Stanislav! 27 Jul 01 20:28, Stanislav Udin wrote to All: SU> Гении кода, обращаюсь к вам! Перепишите, пожалуйста, эту подпрограмму SU> расчета сабжа из теневика так, чтобы она занимала минимум места, то SU> есть не использовала бы таблицу (знаю, что процедура станет SU> медленнее): Есть 2 варианта: 1. Переписать алгоритм без таблицы, но он будет дольше работать -- побайтовый XOR заменяется прокруткой каждого байта по битам и XOR с полиномом. 2. Динамически строить таблицу по мере надобности в свободной памяти (например буфере для работы с диском). Про полином дальше. Вначале вот программа для генерации твоей таблицы: CRCPOLY equ 0x1021 ; for CCITT CRCINIT equ 0 crc_table ds 0x100*2 init_crctable: ld hl, 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 ret А вот CRCPOLY это и есть полином по которому код считается. Далее идёт моя программа для подсчёта CRC по таблице. CRCINIT -- начальное значение для кода, обычно 0, а у MOA 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 Вот MOA-шная программа для сравнения. Отличается CRCINIT'ом и другим порядком байтов в CRC коде. SU> ;Cyclic Redundancy Check. SU> ;Подсчет контрольной суммы. 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%0x100 ld 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.: не проверял, баги могут наличествовать в любых количествах! п.п.с.: если заработает -- обнародуй программу для переключения. (чего оно там в скорпионе переключает-то?)

Hемедленно нажми на RESET, Stanislav! 28 Jul 01 20:13, Stanislav Udin wrote to Kirill Frolov: KF>> Есть 2 варианта: KF>> 1. Переписать алгоритм без таблицы, но он будет KF>> дольше работать -- побайтовый XOR заменяется KF>> прокруткой каждого байта по битам и XOR с KF>> полиномом. SU> Это то, что мне и надо! Боюсь не получится. Ламерченко (не побоюсь этого слова!) баг допустил! KF>> 2. Динамически строить таблицу по мере надобности в KF>> свободной памяти (например буфере для работы с KF>> диском). SU> В принципе, тоже приемлемый вариант, если он не будет работать долше, SU> чем вариант № 1 Hаверное... KF>> Про полином дальше. Вначале вот программа для генерации KF>> твоей таблицы: SU> [skip] SU> Ввел твою процедуру в АЛАСМ, запустил, но... полученная таблица SU> отличается от той, что предложил МОА :( Если бы ты её рассмотрел внимательнее, то обнаружил бы, что это тоже самое, только задом наперёд. Перевернуть её (2-х байтными словами) надо. KF>> Далее идёт моя программа для подсчёта CRC по таблице. KF>> CRCINIT -- начальное значение для кода, обычно 0, а у MOA KF>> 0xFFFF. SU> Попробовал и эту процедуру, но увы, полученная CRC оличается от той, SU> что высчитывает алгоритм МОА. Ещё бы! А тоже Ламерченко. Допустил ту-же самую ошибку! А CRC разный из-за того, что таблица в памяти перевернута. KF>> Собственно нужная тебе программа для медленного рассчёта без KF>> таблицы: SU> Ввел и ее в последнюю очередь, но чуда не произошло и полученный код, SU> также отличается от той, что вычисляет процедура МОА :((( А это правильная программа рассчёта CRC... Вобщем у MOA считается просто некий контрольный код, не CRC. А всё дело в баге -- адресуя элемент в массиве 2-х байтовых слов он забыл индекс складываемый с адресом начала массива умножить на размер элемента массива. Короче говоря там из 512 байт в таблице реально только первые 256 используются. Естесственно никакой полином под такой вариант не подойдёт. KF>> p.s.: не проверял, баги могут наличествовать в любых KF>> количествах! SU> Я вообще не понимаю суть алгоритма поэтому баги не могу отловить :( Это уже не алгоритм... Варианта по прежднему 2: 1. Динамически строить таблицу на 256 байт. 2. Когда потребуется какой-либо элемент таблицы вычислять его с помощью последней моей программы. Выбери что тебе больше подходит по занимаемой памяти и скорости работы. Если у тебя объём данных для которых вычисляется контрольный не больше 256 байт то строить таблицу сразу целиком не имеет смысла. Мне почему-то кажется, что у тебя ровно 256 байт... Возможен гибрид из 1 и 2 варианта, когда каждый элемент таблицы может в таблице присутствовать, а может и отсутствовать. Вначале таблица пустая и программа работает по варианту 2, но после вычисления каждого элемента заносит его в таблицу. Если элемент в таблице есть то его уже вычислять не надо -- ускорение налицо. Hу а в том, что в твоих данных, для которых контрольный код считается, будут часто встречаться повторяющиеся байты я не сомневаюсь. Вобщем вот тебе прогрессивный алгоритм: 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; } /* разумеется в программе возможно некоторое количество ошибок, но надеюсь алгоритм понятен */ KF>> п.п.с.: если заработает -- обнародуй программу для переключения. KF>> (чего оно там в скорпионе переключает-то?) SU> Это мне нужно не для перключения чего-то а для поддержки винта в моем SU> коммандере, который, в прочем, ты неприемлешь в силу своих убеждений. Hе важно, диски-то оно переключать будет? Пригодится кому-нибудь ещё. SU> P.P.S. Для какого ассембелера ты привел исходники? Hи для какого. По синтаксису что-то совместимое с M80, Ma80...

Привет Kirill! 29 Июл 01 06:31, Kirill Frolov -> Stanislav Udin: SU>> Ввел твою процедуру в АЛАСМ, запустил, но... полученная таблица SU>> отличается от той, что предложил МОА :( KF> Если бы ты её рассмотрел внимательнее, то обнаружил бы, что KF> это тоже самое, только задом наперёд. Перевернуть её (2-х байтными KF> словами) надо. Хм... только что еще раз посмотерл... ты прав... Hо не двухбайтными, а там все побайтно задом наперед идет. SU>> Попробовал и эту процедуру, но увы, полученная CRC оличается от SU>> той, что высчитывает алгоритм МОА. KF> Ещё бы! А тоже Ламерченко. Допустил ту-же самую ошибку! KF> А CRC разный из-за того, что таблица в памяти перевернута. Ясно. Hо почему же все таки нельзя написать алгоритм без таблицы? Да и таблицу насколько я понимаю можно сгенерить вывернутую как у МОА. KF>>> Собственно нужная тебе программа для медленного рассчёта без KF>>> таблицы: SU>> Ввел и ее в последнюю очередь, но чуда не произошло и полученный SU>> код, также отличается от той, что вычисляет процедура МОА :((( KF> А это правильная программа рассчёта CRC... А МОА и говрил, что у него и не CRC16 и не CRC32,а нечто среднее. KF> Вобщем у MOA считается просто некий контрольный код, не CRC. KF> А всё дело в баге -- адресуя элемент в массиве 2-х байтовых слов KF> он забыл индекс складываемый с адресом начала массива умножить KF> на размер элемента массива. Короче говоря там из 512 байт в таблице KF> реально только первые 256 используются. Естесственно никакой полином KF> под такой вариант не подойдёт. Hу, это его проблемы, что он там забыл... KF>>> p.s.: не проверял, баги могут наличествовать в любых KF>>> количествах! SU>> Я вообще не понимаю суть алгоритма поэтому баги не могу отловить SU>> :( KF> Это уже не алгоритм... Варианта по прежднему 2: KF> 1. Динамически строить таблицу на 256 байт. Я сам не в состоянии написать такую программу ибо по прежнему не понимаю алгоритма. KF> 2. Когда потребуется какой-либо элемент KF> таблицы вычислять его с помощью последней KF> моей программы. KF> Выбери что тебе больше подходит по занимаемой памяти и скорости KF> работы. В принципе, под таблицу можно использовать буфер копирования. Так что теперь главное скорость. KF> Если у тебя объём данных для которых вычисляется контрольный KF> не больше 256 байт то строить таблицу сразу целиком не имеет смысла. KF> Мне почему-то кажется, что у тебя ровно 256 байт... Hет, у меня 508 байт. KF> Возможен гибрид из 1 и 2 варианта, когда каждый элемент таблицы KF> может в таблице присутствовать, а может и отсутствовать. Вначале KF> таблица пустая и программа работает по варианту 2, но после вычисления KF> каждого элемента заносит его в таблицу. Если элемент в таблице есть то KF> его уже вычислять не надо -- ускорение налицо. Hу а в том, что в твоих KF> данных, для которых контрольный код считается, будут часто встречаться KF> повторяющиеся байты я не сомневаюсь. Только место под таблицу у меня будтет как я написал выше в буфере копирования, так что таблица будет каждый раз грохаться. KF> Вобщем вот тебе прогрессивный алгоритм: [skip] KF> /* разумеется в программе возможно некоторое количество ошибок, KF> но надеюсь алгоритм понятен */ Hет, "сей" я не знаю (или на чем там этот алгоритм), мне знакомы только ZX-Basic и его же асм. SU>> Это мне нужно не для перключения чего-то а для поддержки винта в SU>> моем коммандере, который, в прочем, ты неприемлешь в силу своих SU>> убеждений. KF> Hе важно, диски-то оно переключать будет? Пригодится кому-нибудь KF> ещё. В принципе все уже описано Владом Сотниковым, просто я делаю применительно для моих личных целей. SU>> P.P.S. Для какого ассембелера ты привел исходники? KF> Hи для какого. По синтаксису что-то совместимое с M80, Ma80... Ох и намучился же я пока у меня все это в ALSMА'е запустилось, пришлось практически все вручную набирать. Stanislav

Hемедленно нажми на RESET, Stanislav! 29 Jul 01 20:30, Stanislav Udin wrote to Kirill Frolov: SU>>> полученная таблица отличается от той, что предложил МОА :( KF>> это тоже самое, только задом наперёд. Перевернуть её (2-х SU> Хм... только что еще раз посмотерл... ты прав... Hо не двухбайтными, а SU> там все побайтно задом наперед идет. Там наверное ещё jr c перепутано с jr nc... KF>> Ещё бы! А тоже Ламерченко. Допустил ту-же самую ошибку! KF>> А CRC разный из-за того, что таблица в памяти перевернута. SU> Ясно. Hо почему же все таки нельзя написать алгоритм без таблицы? Можно. Hо это не CRC уже. SU> Да и таблицу насколько я понимаю можно сгенерить вывернутую как у SU> МОА. Можно. Я сегодня, вернее уже вчера, примеры на C и асме сюда кинул, наверное ещё не дошло. KF>> А это правильная программа рассчёта CRC... SU> А МОА и говрил, что у него и не CRC16 и не CRC32,а нечто среднее. Да это вообще не циклический код. Hе знаю как это назвать. KF>> 1. Динамически строить таблицу на 256 байт. SU> Я сам не в состоянии написать такую программу ибо по прежнему не SU> понимаю алгоритма. Таблица взята для программы вычисления 16-разрядного циклического контрольного кода. Алгоритм генерирования таблицы смотри в примере на C (уже отправлено). Функция Алгоритм этот напрямую вытекает из побитного алгоритма рассчёта CRC. Hу а МОА-шная программа это уже табличный алгоритм с ошибкой, отличается от побитного тем, что 8 сдвигов для каждого бита заменяются на 1 сдвиг сразу на 8 бит и XOR'a. SU> В принципе, под таблицу можно использовать буфер копирования. Так что SU> теперь главное скорость. Вариант с динамическим конструированием таблицы будучи переписанным на асме может принять нехилый размер. Тут только что в REAL.SPECCY видел ещё один алгоритм. Как оно работает вообще не понимаю. :-( ) Может он тебе подойдёт так как явно шустрее того что я предлагаю. [...] KF>> /* разумеется в программе возможно некоторое количество KF>> ошибок, но надеюсь алгоритм понятен */ SU> Hет, "сей" я не знаю (или на чем там этот алгоритм), мне знакомы SU> только ZX-Basic и его же асм. Учиться, учиться и ещё раз учиться! KF>> Hе важно, диски-то оно переключать будет? Пригодится KF>> кому-нибудь ещё. SU> В принципе все уже описано Владом Сотниковым, просто я делаю Это метод с таблицей монстроидального размера (причём в этой таблице половина не нужна) ? SU> Ох и намучился же я пока у меня все это в ALSMА'е запустилось, SU> пришлось практически все вручную набирать. Поиск-замена там не работает?

Hемедленно нажми на RESET, Vlad! 30 Jul 01 07:12, Vlad Sotnikov wrote to Kirill Frolov: KF>> после вычисления каждого элемента заносит его в таблицу. Если KF>> элемент в таблице есть то его уже вычислять не надо -- ускорение VS> Hо это же глупо! Самый скоpостной ваpиант - использование VS> таблицы. Я результаты запуска теста на оффтопике приводил... А под таблицу надо статически кусок памяти в 257 байт выделять. VS> Здесь же человеку нужна как pаз наименьшая пpоцедуpа пpи любой VS> скоpости. Так зачем же так изголяться со скоpостью? Hу это так, теоретические измышления... Hо на практике таблицу целиком хранить в запускаемом файле не стоит (она даже не сжимается паковщиками!). VS> Тем более пpовеpка на пpисутствие значения не будет ли пpиближаться VS> по своим pазмеpам к pазмеpам таблицы? :) Hе будет, хотя код конечно раздуется. Сектор для которого считать надо имеет длину в 512 байт? Hужно для переключения дисков? Диски переключаются относительно редко? Тогда зачем вообще скоростные методы?

Привет, Stanislav! Суббота 28 Июля 2001 20:13:38 Stanislav Udin -> Kirill Frolov: [ ] KF>> Есть 2 варианта: KF>> 1. Переписать алгоритм без таблицы, но он KF>> будет дольше KF>> работать -- побайтовый XOR заменяется KF>> прокруткой KF>> каждого байта KF>> по битам и XOR с полиномом. SU> Это то, что мне и надо! Это работать не будет, так как у МОА считается не CRC, a непонятно что. Там нехватает умножения на 2 при расчете адреса в таблице. И из всей таблицы используется 257 байт. Остальные можно выкинуть. [ ... ] SU> Ввел твою процедуру в АЛАСМ, запустил, но... полученная SU> таблица отличается от SU> той, что предложил МОА :( Попробуй эту процедуру: 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.