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

    +131

    1. 1
    2. 2
    3. 3
    int rotate(int a, int k) {
        return (a << k) | (a >> (32-k));
    }

    Вращение на k бит влево.

    Запостил: bormand, 10 Июля 2013

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

    • а разве rotate(x, 0) не будет UB?
      Ответить
      • Ну это не самый главный баг... далеко не самый главный...
        Ответить
      • В гэцэцэ в режиме C99 всё работает, а остальные компиляторы для неосиляторов: http://ideone.com/XgGYVd
        Ответить
        • А оно и будет работать. Реализаций этого UB'а всего две - либо взять величину сдвига по модулю разрядности (емнип, на интелах будет так), либо ничего не двигать, либо просто занулить регистр (как должно было быть по логике). Я не думаю, что кто-то придумает еще одну альтернативу ;)

          Так вот. В обоих случаях код будет работать корректно, несмотря на UB.

          P.S. Да и кому в здравом уме надо вертеть регистр на 0 бит?
          Ответить
          • Точно! В нормальных программах все данные отфильтрованы заранее, поэтому ноль в качестве второго аргумента в функцию прийти не может.
            Ответить
            • Ну там где это "юзалось" - k вообще было константой (2, 5 или 30 в разных местах). Поэтому передавать туда 0 или нечто >= разрядности - ССЗБ.
              Ответить
    • Исправил:
      int rotate(uint64_t a, uint64_t k) {
          return (a << k) | (a >> (64-k));
      }
      Единственная вменяемая платформа — AMD64, остальные для питухов.
      Ответить
      • Да этот код устранит баг ;) Только еще тип результата стоит пофиксить на uint64_t, а то странная получается функция.
        Ответить
      • Заказчик просит перенести на спарк :(
        Ответить
        • На спарках sha1 не нужен, очевидно же. Он должен работать только на x86.
          Ответить
      • Иканус, тебе +1000 - это правда.
        Ответить
    • Я всегда говорил что в С/С++ не хватает операторов циклического битового сдвига, хоть через _asm ror/_asm rol пиши.
      Ответить
      • Ну гцц подобную питушню превращает в rol/ror. Если она, конечно, написана правильно, а не забагована как в топике.
        Ответить
        • Только с -O2 (но Царь только с этим ключом и компилирует) и только если первый аргумент unsigned.
          Ответить
          • > и только если первый аргумент unsigned.
            А если он signed - то это и не вращение, а НЁХ из-за знакового расширения в >>.
            Ответить
      • показать все, что скрытоЦиклический сдвиг не нужен.

        Обычный сдвиг — это умножение/деление на степени двойки. Сдвиг с расширением знака — для питухов, которым зачем-то нужны отрицательные числа.

        А зачем нужен циклический сдвиг? Для доступа к разрядом битовых полей? Но ведь у нас есть bt/bsf/bsr.
        Ответить
        • > Для доступа к разрядом битовых полей?
          Для криптовалок. Там почти в каждом алгоритме циклические сдвиги.
          Ответить
          • Вот даже обьяснение почему http://crypto.stackexchange.com/questions/8533/why-are-bitwise-rotations-used-in-cryptography
            Ответить
            • Циклическому сдвигу отдаётся предпочтение перед произвольным биективным перемешиванием битов только потому, что на процессорах такой сдвиг выполняется в одну инструкцию?
              Ответить
              • Предложи аналог.

                Во первых, одну, во вторых, константное время -> противодействие тайминговым атакам.
                Ответить
              • Довольно действенно, кстати. Вменяемой атаки на это нет.
                Ответить
        • Да есть алгоритмы паковки, есть графические файлы с укуренным кодированием цветовых каналов.
          Ответить
    • Кэп, в чем говнокод? В том, что int не unsigned?
      Ответить
      • >32-k
        Это не жаба и не шарп. int в сишке может принимать любой размер.
        Ответить
        • Все-таки прежде всего в том, что int не unsigned.
          Ответить
        • Тогда в принципе неправильно применять его для MDx, т.к. там предполагаются 32-битные регистры. Наверно было сделано "реально удобно реально падсибя"
          Ответить
          • Да оно вообще не будет работать, на любой архитектуре. Хоть 32 хоть 64 туда напиши :)
            Ответить
            • А всё потому, что на сишечке пишут те, кто не осилил ассемблер. У них в порядке вещей не знать знаковость операндов и использовать тип int по дефолту (в реализации K&R можно было вообще тип в таких случаях не писать, подо что и заточена стандартная библиотека).

              Ну разве нормально, что > и >> могут обозначать как знаковые (jg, sar), так и беззнаковые (ja, shr) операции?
              Ответить
              • Ну разве нормально, что > и >> могут быть как операциями, так и закрывающей скобкой шаблона.
                Ответить
                • Ну кресты-то вообще не нужны, потому что весь их функционал можно реализовать сишечкой (для совсем уж анскильных питухов есть cfront), а со знаками сравнения проблема серьёзная.

                  Скажете, что операция выбирается исходя из типа аргументов?
                  int x;
                  unsigned int y;
                  ...
                  if (x < y)...
                  Во что скомпилируется?
                  Ответить
                  • if (x << y) означает "x намного больше y"?
                    Ответить
                  • В беззнаковое, из-за того что разрядность ансайнед инта >= разрядности инта.
                    Ответить
                  • Вот потому я и не люблю низкоуровневые языки: за недостаток абстракции. Какого черта я должен сам в "шестеренки в процессоре вертеть"?
                    Ответить
                    • Вайндика, жжещ
                      Ответить
                    • показать все, что скрытоVindicar, + 1000. Мы с тобой мыслим одинаково, я тебя люблю и уважаю!

                      На низких языках хорошо кодить в группе; одна голова хорошо, а несколько -лучше, если одна ошибется, другие исправят. А если кодишь один, то можно сильно извращаться(( это угнетает.
                      Ответить
                      • И тем не менее, -3 +0. Нихуя не понимаю.
                        Ответить
                      • Вы никогда не работали в команде!
                        Одна голова ошиблась, остальные подхватили ошибку и понесли дальше. Им есть чем занятся, а не ваш гк править.
                        Ответить
                        • показать все, что скрытоЯ не работал. Но очевидно, Вы работали -и весьма продуктивно, исходя из этой фразы:

                          >>остальные подхватили ошибку и понесли дальше

                          Вот, может, пригодится.
                          http://ekowc.ru/assenization
                          Ответить
                          • Ооо, так вы выдергиваете из контекста. Все с вами ясно. Отныне я вас игнорю.
                            Ответить
                            • >>Все с вами ясно. Отныне я вас игнорю.
                              Поменяю местами все двери дома )

                              Если бы ты игнорил меня с самого начала, а не кидал быдлореплики, было бы куда лучше, на будущее тебе.
                              Ответить
                            • показать все, что скрытоЕсли, как ты выразился, "остальные подхватили ошибку" - то это не команда, а всего-навсего, группа быдлокодеров. Вот что я хотел до тебя донести.
                              Ответить
                              • показать все, что скрытоКак ты до сих пор не понял, тут тролли буквально душат друг друга за еду. Игнорить кого-то - страшное кощунство. Очень благоразумно с твоей стороны будет кормить меня, а не остальных троллей. Я много не ем.
                                Ответить
                      • Вы мыслите одинаково: как долбоёбы ;)
                        Пардон, не удержался.
                        Ответить
                        • Ты тоже мыслишь как мы.
                          Ответить
                          • Если честно, так и тянет забить весь топик флудом. Банальный пиздеж ни о чем.
                            Ответить
                            • Если тебе не хватает ума, чтобы понять комментарии - это лично твои проблемы ;)
                              Ответить
                    • В яве все числа - знаковые. При десериализации и бинарной хуйне типа реализации того же sha1 сильно раздражает.
                      Ответить
                    • > недостаток абстракции
                      Даже сишка поддерживает основные виды абстракций:
                      - абстракция данных (forward declaration + функции-акцессоры)
                      - абстракция процедур (функции, принимающие на вход функции? пожалуйста. С возвратом функций сложнее, ибо замыканий нема, царские методы в продакшене не катят).
                      - разделение интерфейса и реализации (яркий пример - ядрёный vfs)

                      Синтаксическая абстракция в попе, но её вообще мало кто поддерживает. Тут у сишки скорее плюс, ибо богомерзкий препроцессор.

                      Ну а что руками писать приходится, это да. Зато можно выточить в точности такой велик, какой хочется. И контроля над производительностью больше.
                      Впрочем, немного утомляет.
                      Ответить
                      • >- абстракция процедур (функции, принимающие на вход функции? пожалуйста. С возвратом функций сложнее, ибо замыканий нема, царские методы в продакшене не катят).
                        А чем указатели не замыкания?

                        > И контроля над производительностью больше.
                        Дык никто не говорит, что это не нужно вообще никогда, просто очень редко. Меньшее количество граблей важнее.
                        Ответить
                        • Наверное имеется ввиду возврат локальных функций.
                          Ответить
                          • Чет такое?
                            def a():
                                def b():
                                    ...
                                return b

                            Так это уже проблемы работы с памятью, я б сказал.
                            Ответить
                      • >>Впрочем, немного утомляет.

                        Из протокола:
                        Программист не сдал вовремя заказ, потому, что умер посреди разработки.
                        Ответить
                • показать все, что скрытоСовершеннейшим образом ненормально.
                  P/S.
                  Чего вы его минусуете? Он прав.
                  Ответить
              • Жаваебы тоже не осилили ассемблер, это только у сишки такие требования?
                Ответить
    • x86intrin.h

      __rold(); Питухи О5 не осилили сишку. stdint.h - uint32_t.
      Ответить
      • <stdlib.h>
        unsigned long _lrotl(unsigned long, int);

        И да, ни в C99, ни в C11 нет.
        Ответить
        • показать все, что скрытоИ я не говорил, что он есть в либц.

          Такие же штуки в гцц есть для всех нормальных архитектур. Суть в том, что 95% их не юзают, да и не знают о них - вот я пролил свет на них.

          Основной посыл был в stdint, а не __rold();
          Ответить
          • Да, познавательно. Обо многих функциях гцц не все знают.

            Да, в либц перечисленных функций нет, потому что они встроены в компилятор. Оно и логично: зачем линковать такую короткую функцию, когда её можно сделать инлайном?

            _rotl, _rotr, _lrotl, _lrotr есть и у Микрософта, и у Борланда, и у Ваткома... Только одна проблема: при циклическом сдвиге нужно точно знать размер операнда, а в разных версиях сишки размер инта разный. Где восьми- и шестнадцатибитный циклический сдвиг, например? Можно, конечно, написать _rotl(x | (uint32_t)x << 16, k) & 0xffff, но такой код похож на говно, поэтому лучше будет (a << k) | (a >> (16-k)) в надежде, что gcc -O2 автоматически подставит ROL при правильном типе аргумента.

            P.S. А как у гцц с поддержкой _rotl/_rotr на неинтеловских процессорах?
            Ответить
            • >Да, познавательно. Обо многих функциях гцц не все знают.
              Это даже не функция гцц, а интринсики, которые должны быть к каждой архитектуре, которую держит конпелятор.

              >Да, в либц перечисленных функций нет, потому что они встроены в компилятор. Оно и логично: зачем линковать такую короткую функцию, когда её можно сделать инлайном?
              Щито ты несёшь - хедеры тоже часть либц - иди кури либц. Там половина функций инлайновые.

              >Только одна проблема: при циклическом сдвиге нужно точно знать размер операнда, а в разных версиях сишки размер инта разный.
              Если у тебя на x86( ты видишь там написанно x86intrin) инт 8байтный - твой конпелятор говно и выкинь его в форточку. Да и вообще, есть stdint, который маздайщики не осилили по причинет того, что их говноконпелятор не запилил с99.

              >Где восьми- и шестнадцатибитный циклический сдвиг, например?
              В питухе. Ты думаешь там просто так написанно __rold()? Там есть __rolb(), __rolw(), __rolq().

              >Можно, конечно, написать _rotl(x | (uint32_t)x << 16, k) & 0xffff, но такой код похож на говно, поэтому лучше будет (a << k) | (a >> (16-k)) в надежде
              Ты несёшь херню.

              >что gcc -O2 автоматически подставит ROL при правильном типе аргумента.
              Он итак подставит. На все из __rol*();

              >P.S. А как у гцц с поддержкой _rotl/_rotr на неинтеловских процессорах?
              #define _lrotl(a,b) __rolq((a), (b))
              #define _lrotr(a,b) __rorq((a), (b))

              Это тебе не питух.
              Ответить
    • Да вы просто увязли в сарказме.
      Ответить

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