1. Си / Говнокод #13443

    +138

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    uint32_t multiply (uint16_t a, uint16_t b)
{
  return ((a &  ( (int16_t)( ( b & (1 << 0) ) << 15 ) ) / ( 1 << 15) ) << 0 ) +
         ((a &  ( (int16_t)( ( b & (1 << 1) ) << 14 ) ) / ( 1 << 15) ) << 1 ) +
         ((a &  ( (int16_t)( ( b & (1 << 2) ) << 13 ) ) / ( 1 << 15) ) << 2 ) +
         ((a &  ( (int16_t)( ( b & (1 << 3) ) << 12 ) ) / ( 1 << 15) ) << 3 ) +
         ((a &  ( (int16_t)( ( b & (1 << 4) ) << 11 ) ) / ( 1 << 15) ) << 4 ) +
         ((a &  ( (int16_t)( ( b & (1 << 5) ) << 10 ) ) / ( 1 << 15) ) << 5 ) +
         ((a &  ( (int16_t)( ( b & (1 << 6) ) << 9  ) ) / ( 1 << 15) ) << 6 ) +
         ((a &  ( (int16_t)( ( b & (1 << 7) ) << 8  ) ) / ( 1 << 15) ) << 7 ) +
         ((a &  ( (int16_t)( ( b & (1 << 8) ) << 7  ) ) / ( 1 << 15) ) << 8 ) +
         ((a &  ( (int16_t)( ( b & (1 << 9) ) << 6  ) ) / ( 1 << 15) ) << 9 ) +
         ((a &  ( (int16_t)( ( b & (1 <<10) ) << 5  ) ) / ( 1 << 15) ) << 10) +
         ((a &  ( (int16_t)( ( b & (1 <<11) ) << 4  ) ) / ( 1 << 15) ) << 11) +
         ((a &  ( (int16_t)( ( b & (1 <<12) ) << 3  ) ) / ( 1 << 15) ) << 12) +
         ((a &  ( (int16_t)( ( b & (1 <<13) ) << 2  ) ) / ( 1 << 15) ) << 13) +
         ((a &  ( (int16_t)( ( b & (1 <<14) ) << 1  ) ) / ( 1 << 15) ) << 14) +
         ((a &  ( (int16_t)( ( b & (1 <<15) ) << 0  ) ) / ( 1 << 15) ) << 15);
}

    Умножение двух чисел через битовые маски и сдвиги без условных переходов. Компилятор переведет деление инта на сдвинутую единчку в арифметический сдвиг
    Использование ">>" применительно к signed типам - implementation defined http://stackoverflow.com/questions/4009885/arithmetic-bit-shift-on-a-signed-integer/4009922

    Запостил: j123123, 18 Июля 2013

    Комментарии (18) RSS

    • ava someone 18.07.2013 06:22 # +1

      Тут же нет >>, тут только <<.
      Ответить

      • ava bormand 18.07.2013 07:24 # +2

        Так о том и написано в коменте к коду. Автор юзает / вместо >> чтобы не нарваться на implementation defined поведение. Поэтому >> и нет.
        Ответить

    • ava ctm 18.07.2013 07:09 # 0

      ну круто, mul сэмулировали. а нафига?
      Ответить

      • ava j123123 18.07.2013 08:18 # 0

        Это я на сишке напрототипировал, просто решил вспомнить. Когда-то я такую штуку под i8085 на ассемблере делал.
        Вот кстати, какими макросредствами лучше всего убрать копипаст? Встроенный в Си препроцессор тут явно не катит
        Ответить

        • ava bormand 18.07.2013 10:07 # +3

          Кстати код, имхо, не самый удачный. Тут 32 битные сложения и сдвиги на каждом шагу. 8 или 16 битному процу будет очень тяжко это считать.
          Ответить

        • ava Dummy00001 20.07.2013 18:04 # 0

          никакими средствами ты его не уберешь. препроцессор С туп как пробка - по дезайну.

          вот только недавно прикольную штуку откапал. в "Bit Twiddling Hacks" (сервак лежит, но страница еще в кэше гугля) - "Counting bits set by lookup table" - глянь как там таблица количества битов заполняется. помедитируй пару минут как эти B2/B4/B6 работают. я этот трюк в голове уже давно держу, но в практике помучать еще не приходилось.

          демо, не тестировал, через cpp прогнал выглядит ОК вроде:

          #define X( n )  \
        ((a &  ( (int16_t)( ( b & (1 << (15 - n)) ) << (n) ) ) / ( 1 << (15 - n)) ) << 0 )

#define A( x )  B( (x)*2 + 0 ) + B( (x)*2 + 1 )
#define B( x )  C( (x)*2 + 0 ) + C( (x)*2 + 1 )
#define C( x )  D( (x)*2 + 0 ) + D( (x)*2 + 1 )
#define D( x )  X( (x)*2 + 0 ) + X( (x)*2 + 1 )

uint32_t multiply (uint16_t a, uint16_t b)
{
    return A(0);
}
          Ответить

    • ava bormand 18.07.2013 07:11 # +4

      Нифига не понимаю. Аргументы на входе беззнаковые, возвращаемое значение - беззнаковое, умножение судя по траблам со сдвигами - знаковое. Какого хрена тут происходит?

      > ((int16_t)(( b & (1 << 0)) << 15)) / ( 1 << 15)
      Я так понимаю генерация маски - 0 если бит нулевой, ~0 если не нулевой?
      Вот так можно попроще (для беззнаковых b): 1 - (b >> 0) & 1. Только b нужно заранее инвертировать.

      P.S. А вообще зачем это понадобилось? Что-то для микроконтроллеров, не умеющих в умножение, типа AVR?
      Ответить

      • ava bormand 18.07.2013 07:35 # +5

        P.S. А ну да, умножение беззнаковое. Геморрой со знаками автор выдумал себе сам, когда запиливал генерацию масок.
        Ответить

    • ava bormand 18.07.2013 07:44 # +3

      > Компилятор переведет деление инта на сдвинутую единчку в арифметический сдвиг
      А еще забавно будет, если случится то, чего боялся автор, и на данном процессоре >> и / будут выдавать разный результат. В этом случае компилятор либо сфейлится вообще, либо высрет ужасный код, использующий настоящее деление. А судя по тому, что на данной платформе нету даже умножения (иначе зачем бы его запиливали?), то туда вставится софтовая эмуляция оного...
      Ответить

      • ava TarasB 18.07.2013 09:50 # +1

        > и на данном процессоре >> и / будут выдавать разный результат
        А они и так выдают разный результат.
        Ответить

    • ava TarasB 18.07.2013 09:49 # +3

      > Компилятор переведет деление инта на сдвинутую единчку в арифметический сдвиг

      Хуюшки. Для signed типов компилятор переведёт деление инта на сдвинутую единичку в говнище, которое сначала проверяет знак, потом для отрицательных прибавляет делитель минус один, и всё это потому, что в блядских пиндосовских процессорах вместо нормального деления - тупая пендосовская хуйня, у которой (-1)/3 = 0 (и остаток -1 лол), а не как у нормальных людей, когда частное -1, а остаток 2 (как и положено - остаток должен быть положительным).
      Ответить

      • ava bormand 18.07.2013 10:01 # +3

        Угу. Знаковое деление на 2 gcc раскрывает вот в такое (3 команды для коррекции отрицательной хуйни на единичку и собственно знаковый сдвиг):
        movl    %ebx, %eax
shrl    $31, %eax
addl    %ebx, %eax
sarl    %eax
        Вообще меня что в сишке убивает - она позиционируется как низкоуровневый байтоебский язык, но соблюдая стандарты побайтоебить то и не получится! Хотя в то же самое время в сраной высокоуровневой жабе есть оператор >>> для знакового сдвига вправо.
        Ответить

        • ava inkanus-gray 18.07.2013 12:13 # +8

          Сейчас придёт superhackkiller1997 и скажет, что в сишечке байтоёбство есть с помощью какой-нибудь __builtin_ia32_XXX, а то, что в стандарте такого нет, не его проблемы: юзайте вменяемый компилятор.
          Ответить

        • ava dwarf_with_beer 19.07.2013 05:25 # +2

          надо чтобы в очередном стандарте сишечки ввели этот оператор, то есть пофиг как но сдвиг делать арифметический
          Ответить

    • ava j123123 18.07.2013 12:12 # +2

      Вообще, кое-какие интринсики для сдвигов имеются:
      Циклические сдвиги http://software.intel.com/sites/products/documentation/studio/composer/en-us/2011Update/compiler_c/intref_cls/common/intref_allia_integer_arithmetic.htm

      SSE2 http://software.intel.com/sites/products/documentation/studio/composer/en-us/2011Update/compiler_c/intref_cls/common/intref_sse2_int_shift.htm

      Но обычного арифметического сдвига там нет, увы

      Тут http://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs тоже int сдвигается вправо
      Более того, там сказано следующее:
      I've read that ANSI C does not require values to be represented as two's complement, so it may not work for that reason as well (on a diminishingly small number of old machines that still use one's complement).
      Ответить

    Добавить комментарий