C реализация strcmp с использованием вычитания символов

Я видел эту реализацию strcmp некоторое время назад, и у меня есть вопрос для чисто образовательных целей. Зачем нужно преобразовывать входные данные в 16-битные целые числа, выполнять математику, а затем преобразовывать обратно в 8 бит? Что не так с вычитанием в 8 бит?

int8_t strcmp (const uint8_t* s1, const uint8_t* s2)
{
  while ( *s1 && (*s1 == *s2) )
  {
    s1++; 
    s2++;
  }

  return (int8_t)( (int16_t)*s1 - (int16_t)*s2 );
}

Примечание: код предполагает 16-битный тип int.

EDIT: Было упомянуто, что C делает преобразование в int (предположим 32 бит) по умолчанию. Это тот случай, даже если код явно заявляет, что он должен передать на 16 бит int?

Ответы

Ответ 1

Ожидается, что функция strcmp (a, b) вернет

  • <0 if string a < string b
  • >0, если string a > string b
  • 0, если string a == string b

Тест фактически выполняется в первом char, который отличается от двух строк в одном и том же месте (0, ограничитель строк) также работает.

Здесь, поскольку функция принимает два uint8_t (unsigned char), разработчик, вероятно, беспокоился о том, что сравнение с двумя символами без знака даст число между 0 и 255, следовательно, отрицательное значение будет никогда не возвращаются. Например, 118 - 236 вернет -118, но на 8 бит он вернет 138.

Таким образом, программист решил использовать int_16, целое число со знаком (16 бит).

Это могло бы сработать и дать правильные отрицательные/положительные значения (при условии, что функция возвращает int_16 вместо int_8).

(* edit: комментарий от @zwol ниже, целая рекламная кампания неизбежна, поэтому это int16_t литье не требуется)

Однако окончательный int_8 бросок ломает логику. Поскольку возвращаемые значения могут быть от -255 до 255, некоторые из этих значений будут видеть, что их знак изменился после нажатия на int_8.

Например, выполнение 255 - 0 дает положительный 255 (по 16 бит, все младшие 8 бит до 1, от MSB до 0), но в мире int_8 (подписанный int из 8 бит) это отрицательно, -1, так как мы имеем только последние младшие 8 бит, установленные в двоичный 11111111 или десятичный -1.

Определенно не хороший пример программирования.

Эта рабочая функция от Apple лучше 
for ( ; *s1 == *s2; s1++, s2++)
    if (*s1 == '\0')
        return 0;
return ((*(unsigned char *)s1 < *(unsigned char *)s2) ? -1 : +1);

(Linux делает это в коде сборки...)

Ответ 2

Собственно, разница должна быть выполнена не менее 16 бит¹ по той очевидной причине, что диапазон результатов от -255 до 255 и не соответствует 8 битам. Тем не менее, sfstewman правильно отмечает, что это произойдет из-за неявного целого продвижения в любом случае.

Возможный сброс до 8 бит неверен, поскольку он может переполняться, поскольку диапазон по-прежнему не подходит в 8 бит. И вообще, strcmp действительно должен возвращать plain int.

¹ 9 было бы достаточно, но биты обычно бывают в партиях по 8.

Ответ 3

Входные данные являются неподписанными 8-битными, поэтому, чтобы избежать усечения и эффектов переполнения/недополнения, он должен быть преобразован как минимум в 9 бит, поэтому используется int16.

Ответ 4

return (int8_t)( (int16_t)*s1 - (int16_t)*s2 );

Это может означать один из этих двух вариантов:

  • Либо программист был смущен тем, как неявные промоции типа работают в C. Оба операнда будут неявно преобразованы в int независимо от приведения в int16_t. Поэтому, если int - это, например, 32 бита, то код вздор. Или иначе, если int эквивалентно int16_t для конкретной системы - тогда никакого преобразования вообще не происходит.

  • Или программист хорошо осведомлен о том, как работают промо-роли, и пишет код, который должен подтвердить стандарт, запрещающий неявные рекламные кампании типа MISRA-C. В этом случае, а в случае, если int - 16 бит в данной системе, код имеет смысл: он заставляет явное поощрение типа уклоняться от предупреждений от компилятора/статического анализатора.

Я бы предположил, что второй вариант наиболее вероятен, и что этот код предназначен для небольшой системы микроконтроллеров.

Ответ 5

Существуют определенные значения, которые могут привести к различию между этими двумя числами, если int16_t не существует из-за переполнения. В int8_t ваш диапазон от -128 до 127, в uint8_t ваш диапазон от 0 до 255, а в int16_t ваш диапазон будет -32,768 до 32,767.

Обтекание int8_t от a uint8_t приведет к изменению значений над 127 из-за переполнения, поэтому это не должно происходить, но выход должен быть int16_t из-за того, что у вас есть 255 - 0 результат, это будет усеченный возврат.