Конференция "Начинающим" » Сложение с насыщением? [D7, XP]
 
  • Вайрекс (16.01.18 10:08) [0]
    Как сделать в Делфи сложение с насыщением? Есть Д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 не верны. Они не учитывают, что перенос может распространиться на несколько разрядов. Тестирования одного разряда не достаточно.
 
Конференция "Начинающим" » Сложение с насыщением? [D7, XP]
Есть новые Нет новых   [118241   +25][b:0][p:0.001]