Неожиданное поведение во время неявного преобразования в C
Я помогал студенту с его заданием и столкнулся с очень неприятной «ошибкой», которую не мог объяснить, и мне было интересно, смогу ли я получить помощь в понимании того, что именно происходит.
Вопрос был в реализации следующего:
учитывая массив байтов (
buf) длины N, вычислите 16-битную контрольную сумму по формуле:checksum = ~(buf[0]) + ~(buf[1]) + ... + ~(buf[N-2]) + ~(buf[N-1])
Реализация, которую сделал студент, была довольно простой:
uint16_t calculate_checksum(uint8_t *msg_buf, size_t msg_length)
{
uint16_t checksum = 0;
for (size_t i = 0; i < msg_length; i++)
{
checksum += ~(msg_buf[i]);
}
return checksum;
}
Однако, к моему удивлению, эта реализация не дала ожидаемого результата.
Я попытался просмотреть переменную checksum, напечатав ее значение в цикле, что привело к неожиданной закономерности:
65471
65459
65449
65287
65276
65253
65166
65113
65094
...
Контрольная сумма начинается с 0, но после первого сложения значение находится где-то в верхнем диапазоне uint16_t и снижается. Я подозревал, что значение не достигает значения из-за того, что msg_buf[i] было неявно преобразовано в uint16_t перед его дополнением. Но я не понимаю, почему. Я ожидаю, что сначала msg_buf индексируется с помощью i, затем вычисляется дополнение байтов (что даст значение в пределах 0–255), и только затем оно (неявно) преобразуется в uint16_t.
Я попытался посмотреть на ассемблерный вывод оператора checksum += ~(msg_buf[i]), который, похоже, подтверждает эту теорию (с использованием ARM gcc 14.1.0). Обратите внимание, что [r7, #4] — это указатель msg_buf, [r7, #8] — это i, а [r7, #14] — это checksum. Сборка делает что-то странное с вычитанием, которое дает тот же результат, если вы преобразуете байт msg_buf[i] в uint16_t перед дополнением.
ldr r2, [r7, #4]
ldr r3, [r7, #8]
add r3, r3, r2
ldrb r3, [r3] @ zero_extendqisi2
mov r2, r3
ldrh r3, [r7, #14] @ movhi
subs r3, r3, r2
uxth r3, r3
subs r3, r3, #1
strh r3, [r7, #14] @ movhi
Зная это, решение, которое мы придумали, довольно простое. Мы решили просто AND использовать результаты правой части с 0xFF, чтобы избавиться от старших битов, что дало правильную контрольную сумму.
Итак, проблема по существу решена, но я до сих пор не понимаю, почему это проблема. Возможно, такое поведение ожидаемо, и я не знаю правильного порядка действий, или, возможно, происходит что-то еще. Я действительно не знаю.
Может кто-нибудь объяснить, почему это происходит?
~(buf[0]) преобразует buf[0] в int, а затем выполняет побитовое дополнение. Если контрольная сумма должна рассчитываться с восьмибитным дополнением, используйте (uint8_t) ~ (unsigned) buf[0]. (обычно достаточно (uint8_t) ~buf[0], но в реализации на C, использующей дополнение или знак и величину, есть гипотетический сбой.)
см. stackoverflow.com/q/46073295/1216776
@elialm, Совет: при отладке проблем, связанных с битами, распечатывайте отладочную информацию в шестнадцатеричном формате. FFBF, а не 65471.
@EricPostpischil: Обязательная поддержка uint_least64_t в C99 сделала его неподдерживаемым на аппаратном обеспечении со знаком и дополнением к единице. Для Univac с 1-дополнением был создан компилятор, почти совместимый с C99, но в нем отсутствует этот тип, и поэтому он не является полным компилятором C99. Более опасная проблема заключается в том, что если не указать флаг -fwrapv при использовании gcc, оценка uint16a*uint16b, когда uint16a превышает INT_MAX/uint16b, иногда будет нарушать поведение окружающего кода таким образом, что может произвольно повредить память.
Ответы 3
… Я ожидаю, что сначала
msg_bufиндексируется с помощьюi, затем вычисляется дополнение байтов (что даст значение в пределах 0–255), и только затем оно (неявно) преобразуется вuint16_t.
В C 2018 6.5.3.3 4 для оператора ~ указано: «Целое число
над операндом выполняются повышения…» Целочисленные повышения в uint8_t переводят его в int.
Итак, ~(msg_buf[i]) выполняет побитовое дополнение к int. Это установит старшие биты в единицы. Чтобы вычислить восьмибитное дополнение, вы можете использовать (uint8_t) ~msg_buf[i] или ~msg_buf[i] & 0xFF.
Для обычных ситуаций кода checksum += (uint8_t) ~msg_buf[i]; будет достаточно. Стандартом C разрешены в основном теоретические ситуации, в которых арифметика может переполниться или преобразование в uint8_t может дать значение, отличное от желаемого, но они не встречаются в обычных реализациях C.
То, что здесь произошло, является результатом целочисленных повышений.
В большинстве случаев, когда в выражении используется тип меньше int, он преобразуется в тип int. Это прописано в разделе 6.3.1.1p2 стандарта C:
Следующие выражения могут использоваться в выражениях, где есть
intилиunsigned intможно использовать:
- Объект или выражение целочисленного типа (отличного от
intилиunsigned int), чей целочисленный ранг преобразования меньше или равен рангintиunsigned int.- Битовое поле типа
_Bool,int,signed intилиunsigned int.Если
intможет представлять все значения исходного типа (как ограничено шириной битового поля), значение преобразуется в анint; в противном случае он преобразуется вunsigned int. Это называются целочисленными акциями.58) Все остальные типы не изменяется при целочисленном повышении
А в разделе 6.5.3.3p4, касающемся операторов унарной арифметики, относительно оператора ~ говорится следующее:
Результатом действия оператора
~является побитовое дополнение его (повышенный) операнд (т. е. каждый бит результата устанавливается тогда и только тогда, когда если соответствующий бит в преобразованном операнде не установлен). Над операндом выполняются целочисленные акции, и результат имеет продвигаемый тип. Если расширенный тип является беззнаковым типом, выражение ~E эквивалентно максимальному значению, которое можно представить в этом введите минус Е.
Итак, в этом заявлении:
checksum += ~(msg_buf[i]);
Значение msg_buf[i] преобразуется в int перед применением оператора ~. Предполагая, что int 32-битное, это значение int будет содержать все нули в старших 3 байтах. Таким образом, когда применяется оператор, все биты этих 3 байтов будут установлены на 1. Затем, когда это значение добавляется к checksum, имеющему тип uint16_t, младшие 16 бит сохраняются, тогда как все верхние 8 из этих бит установлены на 1.
Например, если значение msg_buf[i] было 0x33, оно сначала будет повышено до значения int 0x00000033. Тогда после применения оператора ~ результатом будет 0xffffff77. Это значение добавляется к текущему значению checksum как int, затем результат усекается до uint16_t перед присвоением.
После применения оператора ~ результат необходимо сначала уменьшить до 8-битного значения с помощью приведения:
checksum += (uint8_t)(~msg_buf[i]);
Или битовая маска:
checksum += ~msg_buf[i] & 0xff;
В дополнение к другим ответам можно отметить, что альтернативным решением является следующее:
checksum += msg_buf[i] ^ 0xFF;
Причина в том, что операция XOR с 0xFF переворачивает только младшие 8 бит, независимо от того, повышается ли msg_buf[i].
Подходит для игры в гольф, но скрывает намерение отрицать нормальное развитие.
@Руслан Спасибо - в данном случае, когда цель сформулирована отрицанием, возможно, вы правы, но также стоит учитывать, что это решение позволяет избежать ловушки, приводящей к этому вопросу. В целом я думаю, что конкретная конструкция ясна или неясна, во многом зависит от ситуации и привычек.
@Руслан Как насчет 0xFF - msg_buf[i]?
@Neil, используя что-либо, кроме побитового NOT, скроет намерение NOTting. Если вы пытаетесь инвертировать число и отрезать старшие байты, проще всего написать именно это: ~msg_buf[i] & 0xFF или в конце использовать приведение вместо оператора AND. Компилятор сможет оптимизировать это под тот же машинный код. И если вы просто выполняете вычитание или XOR Нильсена, не оставляя комментариев, вы не только используете странную конструкцию для простой операции, но и оставляете место для ошибки последующего сопровождающего, который не замечает ловушки расширения знака. .
Можете ли вы предоставить пример входных данных и ожидаемый результат?