checksum algorithm

Все что связано с программированием на Амиге.

Модераторы: striimii, Vinnny

checksum algorithm

Сообщение Ryan 31 июл 2016, 06:17

Кто на пальцах пояснит как работают эти два алгоритма подсчета чек-суммы. Не думаю что тут чтото сложное. Очень надо для восстановления RDB и партишинов. Сам асм 68к никогда толком не кодил :crazy: , а Си вообще не знаю :bash: . Но буковки некоторые знакомы :bis:
=====================================================
Итак, первый.
The Bootblock checksum algorithm follows :

* in 68000 assembler :
Код: Выделить всё
        lea       bootbuffer,a0
        move.l  a0,a1
        clr.l   4(a1)                        ;clear the checksum
        move.w  #(BOOTBLOCKSIZE/4)-1,d1        ;for floppy disks = 1024
                                        ;for hd = (DosEnvVec->Bootblocks * BSIZE)
        moveq   #0,d0
lpchk:  add.l   (a0)+,d0                ;accumulation
        bcc.s   jump                    ;if carry set, add 1 to checksum
        add.l   #1,d0
jump:   dbf     d1,lpchk                ;next long word

        not.l   d0
        move.l  d0,4(a1)                ;new checksum

* in C (version 1):
Код: Выделить всё
#include<limits.h>
#define Short(p) ((p)[0]<<8 | (p)[1])
#define Long(p) (Short(p)<<16 | Short(p+2))

unsigned long newsum,d;
unsigned char buf[BOOTBLOCKSIZE];        /* contains bootblock */
                                        /* for floppy disks = 1024, */
                                        /* for hard disks = (DosEnvVec->Bootblocks * BSIZE) */
int i;

memset(buf+4,0,4);                        /* clear old checksum */
newsum=0L;
for(i=0; i<BOOTBLOCKSIZE/4; i++) {
        d=Long(buf+i*4);
        if ( (ULONG_MAX-newsum) < d )        /* overflow */
                newsum++;
        newsum+=d;
}

newsum=~newsum;                /* not */

* version 2 (From Ralph Babel's 'Install2.c', sent by Hans-Joachim)
Код: Выделить всё
unsigned long checksum, precsum;
checksum = 0;
for(i=0; i<BOOTBLOCKSIZE/sizeof(unsigned long); i++) {
    precsum = checksum;
    if ( (checksum+=Long(buf+i*4)) < precsum)   /* better 68000 to C translation of 'bcc' */
        ++checksum;
}
checksum = ~checksum;

=========================================================
Второй.
4.2.3 How to compute the checksum ?
Код: Выделить всё
#define Short(p) ((p)[0]<<8 | (p)[1])
#define Long(p) (Short(p)<<16 | Short(p+2))

unsigned long newsum;
unsigned char buf[BSIZE];   /* contains rootblock */
int i;

memset(buf+20,0,4);      /* clear old checksum */
newsum=0L;
for(i=0; i<(BSIZE/4); i++)
   newsum+=Long(buf+i*4);
newsum=-newsum;         /* negation */

This checksum algorithm works for most block types except for Bootblock.

The bitmap table ('bm_pages[]') stores one or several pointers to Bitmap blocks. The first pointer is at index 0.

=======================
Ryan
Юный Амигофренд
Юный Амигофренд
 
Сообщения: 9
Зарегистрирован: 30 июл 2016, 02:19

checksum algorithm

Сообщение Ryan 31 июл 2016, 21:16

Чтото программеров совсем не осталось )) Дайте угадаю - обленились либо, ушли на пенсию либо, в мир иной либо не читают этот форум.
Однако алгоритм прост. Его смысл стал мне понятен.

В первом алгоритме напрягает только вот этот момент, пока не понятен мне: в качесте счетчика длины блока где мы считаем контрольную сумму указан операнд #(BOOTBLOCKSIZE/4)-1 . Собственно это и есть длина искомого блока RDB, где мы должны определись контрольную сумму. И ноги растут от вот этого (DosEnvVec->Bootblocks * BSIZE), в гайдах отсылают смотреть структуры 'devices/hardblocks.h и dos/filehandler.h
Не понятно мне зачем делить на 4
Ryan
Юный Амигофренд
Юный Амигофренд
 
Сообщения: 9
Зарегистрирован: 30 июл 2016, 02:19

Re: checksum algorithm

Сообщение da-nie 01 авг 2016, 21:33

RDB и партишинов.


Это из файловой системы амиги? (это я увидел знакомое слово "партишинов"). :)
Но это точно тогда не из дискет - там ксорка была.

Не понятно мне зачем делить на 4


Потому что читают сразу по 4 байта (тип long).

Однако алгоритм прост. Его смысл стал мне понятен.


Это обычная сумма с инверсией в конце. Для контроля целостности данных лучше не применять (перестановки 4 байт не будут замечены) - тут лучше либо CRC считать, либо всякие хэши (MD5 и т.д.).
Мой репозиторий: https://github.com/da-nie
Мои статьи: https://habr.com/ru/users/da-nie/posts/
Моё видео: https://www.youtube.com/channel/UCUroi3D5Kf1WxDzg3ON852g/videos
Аватара пользователя
da-nie
Престарелый Амигодум
Престарелый Амигодум
 
Сообщения: 240
Зарегистрирован: 23 сен 2011, 17:25
Откуда: Ленинградская область

Re: checksum algorithm

Сообщение Ryan 02 авг 2016, 21:23

Для контроля целостности данных лучше не применять (перестановки 4 байт не будут замечены) - тут лучше либо CRC считать, либо всякие хэши (MD5 и т.д.).
Мне как раз такой нужен.
Это из файловой системы амиги?

Ну да. Восстанвливаю покоцанный писюком RDB и партишины. Проблемка обсуждается в этой теме http://www.amiga.org.ru/forum/viewtopic.php?f=15&t=3622

И чета пока не сходится нифига.
В доке на структуру DosEnvec {} пишут присвоение переменных и комментарий
ULONG de_BootBlocks; /* Number of blocks containing boot code */
#define DE_BOOTBLOCKS 19 /* Number of blocks containing boot code */
чтобы узнать значения выражения (BOOTBLOCKSIZE/4)-1 надо значение DE_BOOTBLOCKS умножить на 512 (BSIZE=512)
ВОт если на винте юзались партишины с PFS и SFS - это значит на винте существовало 2 записи содержащие bootcode ? количество ф.с связано с количеством Number of blocks containing boot code ? или нет ? Как понять сколько было на винте bootcode ?
Ryan
Юный Амигофренд
Юный Амигофренд
 
Сообщения: 9
Зарегистрирован: 30 июл 2016, 02:19

Re: checksum algorithm

Сообщение aGGreSSor 25 авг 2016, 21:51

Ryan писал(а):Ну да. Восстанвливаю покоцанный писюком RDB и партишины.

Я бы сделал физическую копию диска и над ней издевался всем подряд до победного конца, а не умножал сущности. И только когда остальные решения "в лоб" гарантированно не сработали, полез бы смотреть "а что оно там делает вообще".
Jedem das Seine

A1230@50MHz/32M/80G, Mediator PCI (S3 ViRGE/DX 4M, RTL8139), GBS-8200;
A2000@7,14MHz without all ;)
Аватара пользователя
aGGreSSor
Надоедливый Амигодух
Надоедливый Амигодух
 
Сообщения: 365
Зарегистрирован: 10 фев 2004, 12:41
Откуда: Saint-Petersburg, Russia


Вернуться в Программирование

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 7

cron