Мастера DELPHI, Delphi programming community Рейтинг@Mail.ru Титульная страница Поиск, карта сайта Написать письмо 
| Новости |
Новости сайта
Поиск |
Поиск по лучшим сайтам о Delphi
FAQ |
Огромная база часто задаваемых вопросов и, конечно же, ответы к ним ;)
Статьи |
Подборка статей на самые разные темы. Все о DELPHI
Книги |
Новинки книжного рынка
Новости VCL
Обзор свежих компонент со всего мира, по-русски!
|
| Форумы
Здесь вы можете задать свой вопрос и наверняка получите ответ
| ЧАТ |
Место для общения :)
Орешник
Коллекция курьезных вопросов из форумов
Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / rsdn.org

 
Чтобы не потерять эту дискуссию, сделайте закладку « предыдущая ветвь | форум | следующая ветвь »

Сложение с насыщением? [D7, XP]


Вайрекс   (16.01.18 10:08

Как сделать в Делфи сложение с насыщением? Есть Д7 и Берлин.
Внезапно осознал что не знаю способов не использующих условных операторов...
Оно вообще такое умеет? Если нет, то из спортивного интереса - возможно ли сделать сей трюк булевыми операторами?


Dimka Maslov ©   (16.01.18 13:21[1]

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


Dimka Maslov ©   (16.01.18 13:21[2]

коррекция - степень двойки минус единица.


Вайрекс   (16.01.18 14:00[3]

Допустим Byte/Word/Cardinal. Для "не меньше минимально возможного значения" есть отдельный термин?
А может ли что завалялся чуть более наглядный пример? С:


Styx ©   (16.01.18 20:57[4]

Вот здесь есть пример на ассемблере: https://stackoverflow.com/questions/121240/how-to-do-saturating-addition-in-c
uint32_t sadd32(uint32_t a, uint32_t b)
{
#if defined IA32
 __asm
 {
   mov eax,a
   xor edx,edx
   add eax,b
   setnc dl
   dec edx
   or eax,edx
 }
#elif defined ARM
 // ARM code
#else
 // non-IA32/ARM way, copy from above
#endif
}


Вайрекс   (18.01.18 18:54[5]

Хорошая ссылка. Даже очень. Большое спасибо!
У меня такая что-то поисковиком не находилась...

Пишут что хороший компилятор должен преобразовывать условие "было ли переполнение" чуть ли не в полторы команды ассемблера. Надо потестить делает ли такое Делфи...

А крайне любопытный код для оперирования сразу с блоком массива (наподобие MMX) выглядит ваще круто, но подозреваю возможно что даже "вручную" вышло бы быстрее... Тоже тестить))


Sha ©   (19.01.18 11:05[6]


function SAdd(a, b: cardinal): cardinal;
begin
 Result:=a+b;
 Result:=-(((a or b) and not Result) shr (SizeOf(Result)*8-1)) or Result;
 end


не проверял


Игорь Шевченко ©   (19.01.18 13:05[7]

Sha ©   (19.01.18 11:05) [6]

Сопровождать такой код особенно приятно :)


Sha ©   (19.01.18 13:14[8]

ну, комментарии никто не отменял


kilkennycat ©   (19.01.18 15:25[9]

и никто не пишет :)


Sha ©   (19.01.18 15:32[10]

если бы никто захотел, он бы написал


kilkennycat ©   (19.01.18 16:38[11]

в [6] не захотел? ))


Sha ©   (19.01.18 17:48[12]

не захотел не из лени, а из уважения к автору,
дабы не портить ему удовольствие ))


kilkennycat ©   (19.01.18 18:12[13]

хитро... мне-то точно доставил удовольствие: я попробовал подумать, как там написать комментарий


Вайрекс   (19.01.18 21:02[14]

Да перевести-то на синтаксис Паскаля не проблема. Мне больше понравилась SatAddUnsigned8(). Истинно магия! ^_____^
Я об том что быстродействие под вопросом. И об том что хороший компилятор вроде как и так
function SAdd(a, b: cardinal): cardinal;
begin
Result:=a+b;
if (Result<a) then
   Result:=#FFFFFFFF;
end;

должен сам соптимизировать в вызов CMOVcc...

А вот если делать ассемблерными вставками... Они оптимизатор не сбивают? Нормально ли inline'ятся? Как писать чтоб результат получался оптимальным?
Кстати никогда не умел переводить код ассемблера в "DB $....." для более старых версий Делфи - может кто научить?

А чего комментарии? Там есть даже рыба для комментария. :) "There are C-tricks to do saturated arithmetic as well. This little code does saturated addition on ..."
Только не "C-tricks", а "Bitwise-tricks".


Sha ©   (20.01.18 01:14[15]

> Вайрекс   (19.01.18 21:02) [14]

Это другой little code,
но списать комментарий, конечно, можно, чтобы запутать себя, читающего.


Вайрекс   (20.01.18 06:21[16]

[OFF]
Чего путать-то? И то и то "Bitwise-tricks". И то и то хрен в уме представишь. Но это и не нужно, как не нужно представлять дополнительный код и прочие "низости". :)
Вроде в данной ситуации более чем достаточно знать что это trick который (пусть и с некими оговорками) делает saturated, не?
[/OFF]


Sha ©   (20.01.18 15:15[17]

ну, тут каждый сам для себя решает, не или не не )


Sha ©   (20.01.18 20:09[18]

посмотрел код по ссылке,
с учетом [6] можно побайтовое насыщение сделать проще,
в 12 команд ассемблера:

function SatAdd8Sha(a, b: cardinal): cardinal;
var
 c: cardinal;
begin;
 c:=a+b;
 a:=(a or b) and $80808080;
 b:=not c and a;
 a:=b;
 b:=b shr 7;
 c:=c-a or a;
 a:=a-b;
 a:=a or c;
 Result:=a;
 end;


без гарантий, особо не проверял


Sha ©   (21.01.18 10:30[19]

Аналогично можно реализовать побайтовое сложение без переноса
в 8 команд ассемблера:


function Add8Sha(a, b: cardinal): cardinal;
var
 c: cardinal;
begin;
 c:=a+b;
 a:=(a or b) and $80808080 and not c;
 Result:=c-a xor a;
 end;


опять без гарантий

Немного изменная функция [18] примерно в 1.4 раза быстрее той,
что приводится по ссылке, это к вопросу о не - не не )


Sha ©   (21.01.18 21:48[20]

При тестировании функций обнаружены ошибки, исправленные версии:

function SatAdd32Sha(a, b: cardinal): cardinal;
begin;
 Result:=a+b;
 Result:=-((a and b or (a or b) and not Result) shr 31) or Result;
 end;

function SatAdd8Sha(a, b: cardinal): cardinal;
var
 c: cardinal;
begin;
 c:=a+b;
 a:=(a and b or (a or b) and not c) and $80808080;
 b:=a shr 7;
 a:=a+a;
 Result:=(c-a) or (a-b);
 end;

function Add8Sha(a, b: cardinal): cardinal;
var
 c: cardinal;
begin;
 c:=a+b;
 a:=(a and b or (a or b) and not c) and $80808080 ;
 a:=a+a;
 Result:=c-a;
 end;


Время работы SatAdd8Sha практически совпало с временем SatAdd8 (есть по приведенной выше ссылке):

function SatAdd8(a, b: cardinal): cardinal;
const
 sign= $80808080;
var
 dif, same: cardinal;
begin;
 dif:=(a xor b) and sign;
 same:=a and b and sign;
 a:=a and not sign;
 b:=b and not sign;
 a:=a+b;
 same:=same or dif and a;
 same:=same + same - (same shr 7);
 Result:=a xor dif or same;
 end;


Можно немного докрутить и выиграть у нее несколько процентов, но это будут копейки. Так что извиняйте.


Z   (21.01.18 22:36[21]

мм... А как именно тестите и на какой версии компилятора? Опции оптимизатора?
А что с вариантом через просто if?


Sha ©   (21.01.18 23:37[22]

Тест простейший - полный перебор всех вариантов входных параметров для одного разряда (байта).

Компилятор - D7, оптимизация включена.

Можно немного ускорить, подглядывая в ассемблерный код.
Разбиваем составные операторы на более простые и переставляем их как хотим.

Автору темы был интересен вариант без ифа, в данном случае может оказаться быстрее с ифом, не проверял.


Sha ©   (22.01.18 00:12[23]

Вот же, блин, сегодня не мой день.

Ответ на вопрос о тестировании заставил задуматься и погрустнеть)
Из функций [20] верны только SatAdd32Sha и SatAdd8.

SatAdd8Sha и Add8Sha не верны. Они не учитывают, что перенос может распространиться на несколько разрядов. Тестирования одного разряда не достаточно.


версия для печати

Написать ответ

Ваше имя (регистрация  E-mail 







Разрешается использование тегов форматирования текста:
<b>жирный</b> <i>наклонный</i> <u>подчеркнутый</u>,
а для выделения текста программ, используйте <code> ... </code>
и не забывайте закрывать теги! </b></i></u></code> :)


Наверх

  Рейтинг@Mail.ru     Титульная страница Поиск, карта сайта Написать письмо