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.