Как подписать расширение 9-разрядного значения при преобразовании из 8-разрядного значения?

Question

Я реализую функцию относительного ветвления в моей простой виртуальной машине.

По сути, мне дают 8-битное относительное значение. Затем я сдвигаю его влево на 1 бит, чтобы сделать его 9-битным значением. Так, например, если бы вы сказали "ветвь +127", это действительно означало бы 127 инструкций и, таким образом, добавило бы 256 к IP.

Мой текущий код выглядит так:

uint8_t argument = 0xFF; //-1 or whatever
int16_t difference = argument << 1;
*ip += difference; //ip is a uint16_t

Я не верю, что разница когда-либо будет обнаружена как меньше 0 с этим как бы то ни было. Я ржавый о том, как подписан на неподписанные работы. Кроме того, я не уверен, что разница будет правильно вычтена из IP в случае, если аргумент скажет -1 или -2 или что-то еще.

По сути, я хочу что-то, что удовлетворяло бы этим "тестам"

//case 1
argument = -5
difference -> -10
ip = 20 -> 10 //ip starts at 20, but becomes 10 after applying difference

//case 2
argument = 127 (must fit in a byte)
difference -> 254
ip = 20 -> 274

Надеюсь, это делает это немного более понятным.

Во всяком случае, как бы я сделал это дешево? Я видел одно "решение" подобной проблемы, но оно включало разделение. Я работаю с медленными встраиваемыми процессорами (предположительно без эффективных способов умножения и деления), так что я бы хотел этого избежать.

Answer 1

Все мои цитаты взяты из стандарта C, раздел 6.3.1.3. Неподписанный в подписанный хорошо определен, когда значение находится в пределах диапазона подписанного типа:

1 Когда значение с целочисленным типом преобразуется в другой целочисленный тип, отличный от _Bool, если значение может быть представлено новым типом, оно не изменяется.

Подпись к неподписанному четко определена:

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

Без знака на подпись, когда значение выходит за пределы диапазона, который не слишком хорошо определен:

3 В противном случае новый тип подписывается и значение не может быть представлено в нем; либо результат определяется реализацией, либо определяется сигнал реализации.

К сожалению, ваш вопрос лежит в области пункта 3. C не гарантирует какой-либо неявный механизм для преобразования значений вне диапазона, поэтому вам нужно явно указать его. Первый шаг - решить, какое представление вы намереваетесь использовать: дополнение к единице, дополнение к двум или знак и величина.

Используемое вами представление повлияет на используемый вами алгоритм перевода. В приведенном ниже примере я буду использовать дополнение к двум: если бит знака равен 1, а все биты значения равны 0, это соответствует вашему наименьшему значению. Ваше самое низкое значение - это еще один выбор, который вы должны сделать: в случае дополнения до двух, имеет смысл использовать любой из INT16_MIN (-32768) или INT8_MIN (-128). В случае двух других, имеет смысл использовать INT16_MIN - 1 или же INT8_MIN - 1 из-за наличия отрицательных нулей, которые, вероятно, следует переводить, чтобы они были неотличимы от обычных нулей. В этом примере я буду использовать INT8_MIN, так как это имеет смысл, что (uint8_t) -1 следует перевести на -1 как int16_t,

Отделяйте бит знака от битов значения. value должно быть абсолютным значением, за исключением случая, когда минимальное значение дополнения до двух sign будет 1 и value будет 0. Конечно, знаковый бит может быть там, где вам нравится, хотя обычно он находится в крайней левой части. Следовательно, сдвиг вправо на 7 позиций дает обычный бит знака:

uint8_t sign =  input >> 7;
uint8_t value = input & (UINT8_MAX >> 1);
int16_t result;

Если бит знака равен 1, мы назовем это отрицательным числом и добавим к INT8_MIN, чтобы построить знак, чтобы мы не оказались в той же загадке, с которой мы начали, или, что еще хуже: неопределенное поведение (какова судьба одного из других ответов).

if (sign == 1) {
    result = INT8_MIN + value;
}
else {
    result = value;
}

Это может быть сокращено до:

int16_t result = (input >> 7) ? INT8_MIN + (input & (UINT8_MAX >> 1)) : input;

... или еще лучше:

int16_t result = input <= INT8_MAX ? input
                                   : INT8_MIN + (int8_t)(input % (uint8_t) INT8_MIN);

Тест знака теперь включает проверку, находится ли он в положительном диапазоне. Если это так, значение остается неизменным. В противном случае мы используем сложение и модуль для получения правильного отрицательного значения. Это довольно согласуется с языком стандарта C выше. Это хорошо работает для двоих, потому что int16_t а также int8_t гарантированно использовать представление дополнения до двух внутри. Тем не менее, такие типы, как int не требуется использовать представление дополнения до двух внутри. При конвертации unsigned int в int например, должна быть еще одна проверка, чтобы мы рассматривали значения, меньшие или равные INT_MAX, как положительные, а значения, большие или равные (unsigned int) INT_MIN, как отрицательные. Любые другие значения должны быть обработаны как ошибки; В этом случае я рассматриваю их как нули.

/* Generate some random input */
srand(time(NULL));
unsigned int input = rand();
for (unsigned int x = UINT_MAX / ((unsigned int) RAND_MAX + 1); x > 1; x--) {
    input *= (unsigned int) RAND_MAX + 1;
    input += rand();
}


int result = /* Handle positives: */ input <= INT_MAX ? input
           : /* Handle negatives: */ input >= (unsigned int) INT_MIN ? INT_MIN + (int)(input % (unsigned int) INT_MIN)
           : /* Handle errors: */ 0;

Answer 2

Если смещение находится в представлении дополнения 2, то

преобразовать это

uint8_t argument = 0xFF; //-1
int16_t difference = argument << 1;
*ip += difference;

в это:

uint8_t argument = 0xFF; //-1
int8_t signed_argument;

signed_argument = argument; // this relies on implementation-defined
                            // conversion of unsigned to signed, usually it's
                            // just a bit-wise copy on 2's complement systems
// OR
// memcpy(&signed_argument, &argument, sizeof argument);

*ip += signed_argument + signed_argument;

Answer 3

Чтобы уточнить: вы беспокоитесь, что сдвиг влево отрицательного 8-битного числа сделает его похожим на положительное 9-битное число? Просто добавьте верхние 9 бит со знаковым битом начального числа перед сдвигом влево:

diff = 0xFF;
int16 diff16=(diff + (diff & 0x80)*0x01FE) << 1;

Теперь ваш diff16 подписано 2*diff

Как отметил Ричард Дж. Росс III, вы можете избежать умножения (если это дорого для вашей платформы) с условным переходом:

int16 diff16 = (diff + ((diff & 0x80)?0xFF00:0))<<1;

Если вы беспокоитесь о вещах, находящихся в пределах досягаемости и т. Д. ("Неопределенное поведение"), вы можете сделать

int16 diff16 = diff;
diff16 = (diff16 | ((diff16 & 0x80)?0x7F00:0))<<1;

Ни в коем случае это не производит числа, которые выходят за пределы диапазона.

Однако самое чистое решение, похоже, "бросить и сдвинуть":

diff16 = (signed char)diff; // recognizes and preserves the sign of diff
diff16 = (short int)((unsigned short)diff16)<<1; // left shift, preserving sign

Это дает ожидаемый результат, потому что компилятор автоматически заботится о знаковом бите (поэтому нет необходимости в маске) ​​в первой строке; а во второй строке выполняется сдвиг влево на целое число без знака (для которого переполнение четко определено в соответствии со стандартом); окончательное приведение к short int гарантирует, что число правильно интерпретируется как отрицательное. Я считаю, что в этой форме конструкция никогда не является "неопределенной".