Переделать контрольную сумму Флетчера с 32 бита на 8 - PullRequest
Новая
       45

Переделать контрольную сумму Флетчера с 32 бита на 8

2 голосов
/ 19 января 2012

Является ли это преобразование правильным из оригинала? 

uint8_t fletcher8( uint8_t *data, uint8_t len )
{
    uint8_t sum1 = 0xff, sum2 = 0xff;

    while (len) {
            unsigned tlen = len > 360 ? 360 : len;
            len -= tlen;
            do {
                    sum1 += *data++;
                    sum2 += sum1;
                    tlen -= sizeof( uint8_t );
            } while (tlen);
            sum1 = (sum1 & 0xff) + (sum1 >> 4);
            sum2 = (sum2 & 0xff) + (sum2 >> 4);
    }
    /* Second reduction step to reduce sums to 4 bits */
    sum1 = (sum1 & 0xff) + (sum1 >> 4);
    sum2 = (sum2 & 0xff) + (sum2 >> 4);
    return sum2 << 4 | sum1;
    }

Оригинал: 

uint32_t fletcher32( uint16_t *data, size_t len )
{
    uint32_t sum1 = 0xffff, sum2 = 0xffff;

    while (len) {
            unsigned tlen = len > 360 ? 360 : len;
            len -= tlen;
            do {
                    sum1 += *data++;
                    sum2 += sum1;
                    tlen -= sizeof( uint16_t );
            } while (tlen);
            sum1 = (sum1 & 0xffff) + (sum1 >> 16);
            sum2 = (sum2 & 0xffff) + (sum2 >> 16);
    }
    /* Second reduction step to reduce sums to 16 bits */
    sum1 = (sum1 & 0xffff) + (sum1 >> 16);
    sum2 = (sum2 & 0xffff) + (sum2 >> 16);
    return sum2 << 16 | sum1;
    }

длина будет 8.

данные будут иметь ввод данных [] (1 - 8)

На самом деле я не знаю, что делать со строкой: unsigned tlen = len> 360? 360: len;

Может быть -> int8_t tlen = len> 255? 255: лен;

Ответы [ 3 ]

2 голосов
/ 21 ноября 2012

Как вычислить это tlen значение

На самом деле я не знаю, что делать со строкой: unsigned tlen = len> 360?360: len;

Эта строка, похоже, взята из старой версии из этого раздела Википедии .К настоящему моменту оно было изменено на 359, объяснение объяснено на странице обсуждения .Число применяется только к суммированию 16-битных объектов, так как это наибольшее число n , удовлетворяющее

n ( n + 5) / 2 × (2 16 −1) <2 <sup>32

Другими словами, это наибольшее количество раз, когда вы можете добавлять блоки безвыполняя уменьшение по модулю, и по-прежнему избегайте переполнения uint32_t.Для 4-битных слов данных и 8-битного аккумулятора соответствующее значение будет 4, вычисленное с использованием

n ( n + 5) / 2 ×(2 4 -1) <2 <sup>8

Поэтому вам придется изменить эту строку, если вы измените размер данных.Вы также можете изменить код, чтобы использовать больший тип данных, чтобы сохранить его суммы, таким образом суммируя больше блоков перед сокращением.Но в этом случае вам может потребоваться более одного шага сокращения внутри цикла.

Например, если бы вы использовали uint32_t для sum1 и sum2, тогда вы могли бы суммировать 23927 клев до того, какопасность переполнения, но после этого вам потребуется до 7 сокращений формы sum1 = (sum1 & 0xf) + (sum1 >> 4), чтобы свести это к диапазону от 1 до 0x1e, как это делает ваш первоначальный агорифм.Может быть более эффективно написать это как (sum1 - 1)%0xf + 1.В этом случае вы можете даже изменить диапазон обратно с 1 до 15 на 0 до 14, инициализировать суммы до 0 и записать сокращение как sum1 %= 0xf.Если вам не требуется совместимость с реализацией, которая использует другой диапазон.

1 голос
/ 19 января 2012

Я думаю, вам нужны маски 0xF, а не 0xFF. 32-битный использует 16-битную маску, половину 32, ваш 8-битный использует 8-битную маску, которая не является половиной 8, 4 бита - половина 8. 

uint8_t fletcher8( uint8_t *data, uint8_t len )
{
    uint8_t sum1 = 0xf, sum2 = 0xf;

    while (len) {
        unsigned tlen = len > 360 ? 360 : len;
        len -= tlen;
        do {
                sum1 += *data++;
                sum2 += sum1;
                tlen -= sizeof( uint8_t );
        } while (tlen);
        sum1 = (sum1 & 0xf) + (sum1 >> 4);
        sum2 = (sum2 & 0xf) + (sum2 >> 4);
    }
    /* Second reduction step to reduce sums to 4 bits */
    sum1 = (sum1 & 0xf) + (sum1 >> 4);
    sum2 = (sum2 & 0xf) + (sum2 >> 4);
    return sum2 << 4 | sum1;
}

В противном случае вы создаете другую контрольную сумму, а не Fletcher. Например, sum1 выполняет контрольную сумму дополнения. В основном это 16-битный предыдущий и 4-битный в вашем случае, контрольная сумма, где биты переноса добавляются обратно. Использование в интернет-протоколах позволяет очень легко модифицировать пакет без необходимости вычисления контрольной суммы для всего пакета, вы можете складывать и вычитать только изменения из существующей контрольной суммы.

Дополнительный шаг уменьшения предназначен для углового случая, если в результате суммирования 1 + = * data = 0x1F с использованием четырехбитной схемы добавление бита переноса будет 0x01 + 0x0F = 0x10, вам необходимо добавить этот перенос бит обратно, так что вне цикла 0x01 + 0x00 = 0x01. В противном случае, что вне цикла сумма складывается в ноль. В зависимости от вашей архитектуры вы можете выполнить быстрее с чем-то вроде if (sum1 & 0x10) sum1 = 0x01; чем беглое сложение, которое может потребовать больше инструкций.

Когда это становится чем-то большим, чем просто контрольная сумма с добавленными битами переноса, это последний шаг, когда они объединяются. И если вы, например, используете только 32-битный fletcher в качестве 16-битной контрольной суммы, вы тратите впустую свое время, младшие 16 битов результата - это просто контрольная сумма запаса с добавленным битом переноса, ничего особенного. sum2 - интересное число, так как это накопление контрольных сумм sum1 (sum1 - накопление данных, sum2 - накопление контрольных сумм).

0 голосов
/ 19 января 2012

в оригинальной версии sum1, sum2 32-битные. вот почему бит сдвигается потом. В вашем случае вы объявляете sum1, sum2 равным 8 битам, поэтому сдвиг битов не имеет смысла.

...