LINUX.ORG.RU

Подскажите описание алгоритма вычисления контрольной суммы

 


0

1

Есть функция на C, вычисляющая контрольную сумму флэша:

unsigned boardMemSum(unsigned* ptr, int nLongs)
{
    unsigned sum, ix;

    for(sum = nLongs, ix = 0; ix < nLongs; ix++)
	sum += ptr[ix];

    return ~sum;
}

где ptr - указатель на начало памяти флэша, nLongs - длина данных в 4-х байтных словах.

Если вызвать эту функцию для всего флэша, а результат (4 байта) сохранить в любом свободном месте флэша(область флэша считается свободной, если биты равны 1), то при последующем вызове boardMemSum для всего флэша она вернёт 0xffffffff.

Если после этого записать во флэш пользовательские данные(не важно, в свободное место, или нет), вызвать boardMemSum для пользовательских данных и сохранить результат в свободное место флэша, то результат вызова boardMemSum для всего флэша не изменится и будет равен 0xffffffff.

На практике это не работает, у начальника нет описания алгоритма. Дайте пожалуйста ссылку на описание алгоритма, в частности, интересует как реализовать этот алгоритм для длины не кратной 4 байт.


Ответ на: комментарий от unC0Rr

В стеке функции переменные по умолчанию равны 0, к тому же в цикле присваевается sum = nLongs, так что не в этом дело.

Мне бы описание самого алгоритма, как реализовать его для длины, не кратной 4 байт.

IOne ()
Ответ на: комментарий от unC0Rr

Не знаю, это написано задолго до меня :)

Надеюсь тот, кто это писал, не изобретал велосипед и я найду описание этого алгоритма :)

IOne ()
Ответ на: комментарий от IOne

Да вроде всё же очевидно: когда ты складываешь все числа, то получаешь сумму s. Когда ты запишешь её вместо 0xffffffff, ты уменьшишь общую сумму на (0xffffffff - s). Т.о. получится новая сумма

s2 = s - (0xffffffff - s) = 0xffffffff
.

В случае некратного четырём размера, думается, просто добивается до четырёх байт нулевыми байтами или 0xff.

unC0Rr ★★★★★ ()
Ответ на: комментарий от IOne

Надеюсь тот, кто это писал, не изобретал велосипед и я найду описание этого алгоритма :)

это даже не велосипед, а самокат. Это просто тупая сумма 4х битных слов. Что-бы получить ~0 (0xffffffff) тебе нужно получить сумму 0, а это возможно тогда, и только тогда, когда ты начал считать с -SUM(отрицательной суммой). Ну или тогда, когда ты эту отрицательную сумму записал на флешку. SUM + -SUM == 0.

IRL такая сумма мало где применяется, ибо «abc»==«cba»==«cab»... Т.е. от перестановок не спасает.

drBatty ★★ ()
Ответ на: комментарий от drBatty

Да, я чего-то в арифметике уже весь запутался :) Всё правильно, сумма уменьшается на s и увеличивается на 0xffffffff. ~s == 0xffffffff - s

unC0Rr ★★★★★ ()
Ответ на: комментарий от IOne

Мне бы описание самого алгоритма

Что конкретно в алгоритме тебе не ясно из исходного кода?

как реализовать его для длины, не кратной 4 байт

Можно вместо «unsigned» использовать «unsigned char». Либо последние байты, если их меньше чем 4, дополнять нулями.

Manhunt ★★★★★ ()

результат вызова boardMemSum для всего флэша не изменится и будет равен 0xffffffff. На практике это не работает

Конечно не работает! Из-за «sum = nLongs».

Manhunt ★★★★★ ()
Ответ на: комментарий от IOne

В стеке функции переменные по умолчанию равны 0

Да ну?

$ gcc -O0 a.c 
$ ./a.out 
x = 0; y = 0
$ gcc -O3 a.c 
$ ./a.out 
x = 1548702712; y = 1548702728
$ cat a.c
#include <stdio.h>

void f()
{
    int x;
    int y;

    printf("x = %d; y = %d\n", x, y);
}

int main(int argc, char* argv[])
{
    f();
    return 0;
}
ebantrop ()
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
unsigned int board[16];
unsigned int boardMemSum(unsigned int* ptr, unsigned int nLongs) {
    unsigned int sum, ix;
    for(sum = nLongs, ix = 0; ix < nLongs; ix++)
    sum += ptr[ix];
    return ~sum;
}
unsigned int rand4() { return (rand()<<16)|rand(); }
int main() {
  int i;
  srand(time(NULL));
  // есть некоторая область флеш:
  for(i=0;i<16;i++)
    board[i] = rand4();
  // пользовательские данные:
  for(i=5;i<10;i++)
    board[i] = 0xffffffff;
  // в ней пустая область:
  board[11] = 0xffffffff;
  board[12] = 0xffffffff;
  // заполнили её:
  board[11] = boardMemSum(board,16);
  // показали результат:
  printf("0x%x===0xffffffff\n",boardMemSum(board,16));
  for(i=0;i<16;i++) printf("%i) %x\n",i,board[i]);
  // поменяли пользовательские данные:
  for(i=5;i<10;i++)
    board[i] = rand4();
  // посчитали контрольную сумму пользовательских данных.
  //и записали её в другую свободную ячейку:
  board[12] = boardMemSum(&board[5],5);
  printf("0x%x===0xffffffff\n",boardMemSum(board,16));
  for(i=0;i<16;i++) printf("%i) %x\n",i,board[i]);
  return 0;
}

а результат (4 байта) сохранить в любом свободном месте флэша

не в любое, а в любое кратное 4-м байтам

sum = nLongs

действительно так надо, иначе не работало бы добавление и подпись в область называемой «свободным местом» (заполненную -1).

после этого записать во флэш пользовательские данные (не важно, в свободное место, или нет)

важно, должно быть свободным, иначе пересчитывать контрольную сумму. Примерно так:

  // поменяли пользовательские данные:
  int crc = boardMemSum(&board[5],5);
  for(i=5;i<10;i++)
    board[i] = rand4();
  // посчитали контрольную сумму пользовательских данных.
  //и записали её в другую свободную ячейку:
  board[12] = boardMemSum(&board[5],5)-(crc+1);
в этом варианте кода не имеет значение чему равно начальное значение sum в функции boardMemSum, лишь бы всегда инициализировалось одинаково.

anonymous ()
Ответ на: комментарий от IOne

В стеке функции переменные по умолчанию равны 0

Простите, щито? Не путаете с сегментом данных (глобальные переменные)?

mix_mix ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.