Сергей Борщ 141 2 марта, 2015 Опубликовано 2 марта, 2015 · Жалоба Я как раз для 0x1021 и знаю только ;)Ну да, у меня такая же: void crc::ccitt::calculate(uint8_t byte) { base Current_tmp = Current ^ byte; uint_fast8_t Tmp= (Current_tmp ^ (Current_tmp << 4)) & 0xff; Current = (Current_tmp >> 8) ^ (Tmp << 8) ^ ( Tmp << 3) ^ ( Tmp >> 4); } void crc::xmodem::calculate(uint8_t byte) { base Current_tmp = Current; uint_fast8_t Tmp = ((Current_tmp >> 8) ^ byte) & 0xFF; Tmp ^= Tmp >> 4; Current = (Current_tmp << 8) ^ (Tmp << 12) ^ (Tmp << 5) ^ Tmp; } Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
SM 0 2 марта, 2015 Опубликовано 2 марта, 2015 · Жалоба Для CRC-32 такие конструкции категорически не выгодны, так как там полиномы имеют кол-во бит, установленных в 1, больше чем 8 - следовательно и сдвигов с ксорами будет по кол-ву бит, что не выгодно по сравнению с реализацией в лоб, с циклом на 8 условных ксоров с полиномом. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Сергей Борщ 141 3 марта, 2015 Опубликовано 3 марта, 2015 · Жалоба Для CRC-32 такие конструкции категорически не выгодны,Существует куча других циклических контрольных сумм, 16- и 8-битных. Серега, ты можешь объяснить саму методику, как получаются такие формулы? В хозяйстве обязательно сгодится! Скажем, на примере полинома 0xA001 (modbus), обработка младшим битом вперед. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
SM 0 3 марта, 2015 Опубликовано 3 марта, 2015 · Жалоба обработка младшим битом вперед. Это что значит? Новый бит данных задвигается со старшего разряда сдвигом вправо, или с младшего, сдвигом влево? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Сергей Борщ 141 3 марта, 2015 Опубликовано 3 марта, 2015 · Жалоба Это что значит? Новый бит данных задвигается со старшего разряда сдвигом вправо,Да. Потихоньку начал сам разбираться с примером из приложенного мной выше примера применения: // обсчет одного байта "в лоб": void crc::ccitt:calculate(uint8_t byte) { uint_fast8_t Counter = 8; uint_fast16_t Tmp = Current; Tmp ^= byte; do { if (Tmp & (1<<0)) { Tmp >>= 1; Tmp ^= POLYNOME; } else Tmp >>= 1; } while(--Counter); Current = Tmp; } результат для байта с одним установленным битом: /* 0x01 -> 0x1189 0x02 -> 0x2312 0x04 -> 0x4624 0x08 -> 0x8C48 0x10 -> 0x1081 0x20 -> 0x2102 0x40 -> 0x4204 0x80 -> 0x8408 // то же в двоичном виде: 0: 0000 0001 -> 0001 0001 1000 1001 1: 0000 0010 -> 0010 0011 0001 0010 2: 0000 0100 -> 0100 0110 0010 0100 3: 0000 1000 -> 1000 1100 0100 1000 4: 0001 0000 -> 0001 0000 1000 0001 5: 0010 0000 -> 0010 0001 0000 0010 6: 0100 0000 -> 0100 0010 0000 0100 7: 1000 0000 -> 1000 0100 0000 1000 // зависимость каждого бита результата от входных: ^^ y15 = x3 ^ x7 --+| y14 = x2 ^ x6 ---+ y13 = x1 ^ x5 y12 = x0 ^ x4 y11 = x3 ..... */ Пока с примером совпадает. В принципе уже можно написать такой вариант: тут была фигня Каким образом заполнена таблица 7-1 в примере понятно. Осталось понять, как эти выражения для каждого бита свернуть в общую формулу. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
SM 0 3 марта, 2015 Опубликовано 3 марта, 2015 · Жалоба в общем, объясню на примере 0x8408: 1) byte ^= crc; // XOR младшего байта с входными данными. С этого начинается любой CRC (это "скрытый" бит полинома, который младше младшего, реверс от X^16) 2) byte ^= byte << 4; // XOR, обусловленный битом полинома 0x8408, для данных, которые выдвинутся за пределы 16 бит. 4 влево = номер бита 0x0008 (3) + 1 3) crc = (byte << 8) | (crc >> 8); // сдвиг 8 раз вправо, и задвиг свежих битов, обеспечиваемых битом полинома 0x8408 (15 - 8 + 1 = влево на +8) 4) crc ^= byte >> 4; // XOR, обусловленный битом 0x8408 для остатка данных, не выдвинутых за пределы 16 бит. 4 вправо = номер бита 0x0008 (3) - 8 + 1 = -4 5) crc ^= byte << 3; // XOR, обусловленный битом 0x8408 (3 влево = номер бита 0x0400 (это 10) - 8 + 1) Собственно, все. UPD: Вдогонку. Для 0xA001, подозреваю, что такое разложение на сдвиги и XORы невозможно, по причине слишком близкой обратной связи (в младшем бите регистра). То есть, для реализуемости такого подхода (для направления сдвига вправо), надо, чтобы в полиноме не было бит, установленных в 1, на позициях, меньших, чем половина ширины входного слова минус 1. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Сергей Борщ 141 3 марта, 2015 Опубликовано 3 марта, 2015 · Жалоба Такс. Я разобрался. 0x8408, сдвиг вправо. За время обработки одного байта у нас предыдущее значение CRC сдвинется на 8 бит вправо. При этим "выпавшие" вправо биты проXORятся с исходным байтом. Отсюда byte ^= CRC и CRC >>= 8. Получившийся byte ^ CRC даст после всех обратных связей некий результат f(byte ^ CRC), который будет проXORен с получившимся CRC >>= 8. Это нам дает X = byte ^ CRC и CRC = (CRC >>8) ^ f(X). f(X) получается следующим образом: 0: 0000 0001 -> 0001 0001 1000 1001 1: 0000 0010 -> 0010 0011 0001 0010 2: 0000 0100 -> 0100 0110 0010 0100 3: 0000 1000 -> 1000 1100 0100 1000 4: 0001 0000 -> 0001 0000 1000 0001 5: 0010 0000 -> 0010 0001 0000 0010 6: 0100 0000 -> 0100 0010 0000 0100 7: 1000 0000 -> 1000 0100 0000 1000 yy 11 54 y15 = x3 ^ x7 --+| y14 = x2 ^ x6 ---+ y13 = x1 ^ x5 y12 = x0 ^ x4 y11 = x3 y10 = x2 ^ x3 ^ x7 y9 = x1 ^ x2 ^ x6 y8 = x0 ^ x1 ^ x5 y7 = x0 ^ x4 y6 = x3 y5 = x2 y4 = x1 y3 = x0 ^ x3 ^ x7 y2 = x2 ^ x6 y1 = x1 ^ x5 y0 = x0 ^ x4 \-----/ \-----/ \-----/ A << 8 A << 3 A >> 4 A = (X ^ (X << 4)) & 0xFF f(x) = (A << 8) ^ (A << 3) ^ (A >> 4) Итого, на выходе имеем: byte ^= CRC; uint8_t Tmp = byte ^ (byte << 4); CRC = (CRC >> 8) ^ (Tmp << 8) ^ (Tmp << 3) ^ (Tmp >> 4); Сошлось. Аналогичным образом ищем f(X) для полинома 0xA001. Получается уже не так красиво: 0: 0000 0001 -> 1100 0000 1100 0001 1: 0000 0010 -> 1100 0001 1000 0001 2: 0000 0100 -> 1100 0011 0000 0001 3: 0000 1000 -> 1100 0110 0000 0000 4: 0001 0000 -> 1100 1100 0000 0001 5: 0010 0000 -> 1101 1000 0000 0001 6: 0100 0000 -> 1111 0000 0000 0001 7: 1000 0000 -> 1010 0000 0000 0001 y15 = x7 ^ x6 ^ x5 ^ x4 ^ x3 ^ x2 ^ x1 ^ x0 y14 = x7 ^ x6 ^ x5 ^ x4 ^ x3 ^ x2 ^ x1 y13 = x7 ^ x6 y12 = x6 ^ x5 y11 = x5 ^ x4 y10 = x4 ^ x3 y9 = x3 ^ x2 y8 = x2 ^ x1 y7 = x1 ^ x0 y6 = x0 y5 = 0 y4 = 0 y3 = 0 y2 = 0 y1 = 0 y0 = x7 ^ x6 ^ x5 ^ x4 ^ x2 ^ x1 ^ x0 То есть технически реализуемо, но сдвигов будет больше. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
SM 0 3 марта, 2015 Опубликовано 3 марта, 2015 · Жалоба То есть технически реализуемо, но сдвигов будет больше. Не реализуемо из-за единицы в A001. Эта единица дает близкую обратную связь (2^0 = 1) - таким образом такая схема реализуема, но только не для 8-битных входных данных, а лишь для двухбитных - а это никакой экономии не даст (для байта придется сделать 4 итерации). А вот в 8408 - младшая единица - 8 (2^3), что как раз разрешает такую реализацию для кусков данных до 8 бит включительно. Не надо эту F(x) ИСКАТЬ! Она составляется просто из позиций единичных бит в полиноме. В первой части, до основного сдвига вправо, в XOR-ах в количествах сдвигов участвуют биты полинома от самого младшего и до последнего, перекрываемого по ширине входного слова, а во второй части, после сдвига - все биты полинома. То есть, вот она, реализация для A001, но она не эффективна, из-за двухбитного ограничения, из-за этой самой A001 static USHORT crc; void update_CRC_A001_2bit(unsigned char byte) { USHORT t; byte ^= crc; byte ^= byte << 1; // bit 0 of poly (0 + 1) byte &= 0x3; t = crc >> 2; // shift for -2 bits t ^= byte << 14; // bit 15 of poly (15 - 2 + 1) t ^= byte << 12; // bit 13 of poly (13 - 2 + 1) t ^= byte >> 1; // bit 0 of poly (0 - 2 +1) crc = t; } void update_CRC_A001(unsigned char byte) { update_CRC_A001_2bit(byte); update_CRC_A001_2bit(byte>>2); update_CRC_A001_2bit(byte>>4); update_CRC_A001_2bit(byte>>6); } UPD: Короче, имея на входе 0xFF, как его не ксорь со сдвигами, 0x55 не получишь... Вот поэтому, и нельзя реализовать A001 с 8-битным входом. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Сергей Борщ 141 3 марта, 2015 Опубликовано 3 марта, 2015 · Жалоба Короче, имея на входе 0xFF, как его не ксорь со сдвигами, 0x55 не получишь... Вот поэтому, и нельзя реализовать A001 с 8-битным входом.Не, как говорит один коллега, "не вкуриваю". У 0x1021 тоже единица в младшем разряде, но для него формула есть и работает. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
SM 0 3 марта, 2015 Опубликовано 3 марта, 2015 · Жалоба Не, как говорит один коллега, "не вкуриваю". У 0x1021 тоже единица в младшем разряде, но для него формула есть и работает. А там вся хитрость в том, что сдвиг-то в обратную сторону. А если все привести к сдвигу вправо... Получим знакомый 0x8408! То есть, для влево двигающихся CRC, ограничение вводит близость самого старшего бита полинома, установленного в 1, к старшему разряду. А для вправо двигающихся - младшей 1 к младшему оазряду. То есть, 0x8408 - это 0x1021, но через зад. То есть, это один и тот же полином, реализации разные. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Сергей Борщ 141 3 марта, 2015 Опубликовано 3 марта, 2015 · Жалоба То есть, 0x8408 - это 0x1021, но через зад.Да, пока домой ехал сам понял. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
toweroff 1 11 марта, 2015 Опубликовано 11 марта, 2015 · Жалоба Подниму тему вот по какому вопросу Когда пользовался CRC16, вычислял для всего блока, вместе с контрольной суммой в конце. Если не ноль - ошибка С CRC32 такое не прокатывает, сама сумма получается верной, но расчет вместе с самой суммой ноль не выдает Это, я так понимаю, связано с инвертированием суммы до и после расчета. А есть алгоритмы расчета CRC32, которые бы и сумму давали верную, и ноль вместе с ней получался? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
SM 0 11 марта, 2015 Опубликовано 11 марта, 2015 · Жалоба но расчет вместе с самой суммой ноль не выдает Ну некую константу зато выдает. Разница совершенно не принципиальна, проверять на ноль, или на константу. Зато, снимается проблема, что, если после сообщения, в результате ошибки добавилось N нулевых бит, то, без инверсии, CRC останется нулем, и пройдет, как будто ошибок нет. С инверсией этого не произойдет. Для этого же инициализируют регистр в FFFFFFFF, только, защищаясь от добавленных нулевых бит в начале. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
toweroff 1 11 марта, 2015 Опубликовано 11 марта, 2015 · Жалоба Да суть-то не в этом - с нулем или константой сравнивать, просто если пакет вида: [sTART] [LEN] [bODY] [CRC] где LEN - общая длина, включая заголовок и сумму, расчитать все это дело и сравнить с нулем без лишних телодвижений Если же сравнивать конкретно с суммой, то нужно каждый раз корректировать длину на размер uint32_t, вычислять и сравнивать уже с тем, что в пакете Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
SM 0 11 марта, 2015 Опубликовано 11 марта, 2015 · Жалоба Если же сравнивать конкретно с суммой, то нужно каждый раз корректировать длину на размер uint32_t, вычислять и сравнивать уже с тем, что в пакете Зачем? Просчитывается весь пакет, вместе с инверсной CRC, только результат сравнивается с некой константой, а не с нулем. Эту константу можно получить, обсчитав один заведомо безошибочный пакет. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться