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

    +2

    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
    20. 20
    21. 21
    22. 22
    23. 23
    24. 24
    25. 25
    26. 26
    27. 27
    28. 28
    29. 29
    30. 30
    31. 31
    32. 32
    33. 33
    34. 34
    35. 35
    36. 36
    37. 37
    38. 38
    39. 39
    40. 40
    41. 41
    42. 42
    43. 43
    44. 44
    45. 45
    46. 46
    47. 47
    48. 48
    49. 49
    50. 50
    51. 51
    52. 52
    53. 53
    54. 54
    55. 55
    56. 56
    57. 57
    58. 58
    59. 59
    60. 60
    61. 61
    62. 62
    63. 63
    64. 64
    65. 65
    66. 66
    67. 67
    68. 68
    69. 69
    70. 70
    71. 71
    72. 72
    73. 73
    74. 74
    75. 75
    76. 76
    77. 77
    78. 78
    79. 79
    80. 80
    81. 81
    #include <stdio.h>
    #include <stdlib.h>
    #include <inttypes.h>
    #include <limits.h>
    typedef unsigned __int128 uint128_t;
    typedef __int128 int128_t;
    
    // в чем тут по-вашему баг ?
    uint64_t add1bit_left_1_bug(const uint64_t a, int shift)
    {
      return ~(~(a << shift) >> shift);
    }
    
    uint64_t add1bit_left_1(const uint64_t a, int shift)
    {
      return ~((uint128_t)~(uint64_t)((uint128_t)a << shift) >> shift);
    }
    
    // или тут ?
    uint64_t add1bit_left_2_bug(const uint64_t a, int shift)
    {
      return a | (uint64_t)(UINT64_MAX << (CHAR_BIT * sizeof(uint64_t) - shift));
    }
    
    uint64_t add1bit_left_2(const uint64_t a, int shift)
    {
      return a | (uint64_t)((uint128_t)-1 << (CHAR_BIT * sizeof(uint64_t) - shift));
    }
    
    uint64_t add1bit_left_3(const uint64_t a, int shift)
    {
      if (shift == 0) return a;
      return (uint64_t)((int64_t)((a << (shift-1)) | ((uint64_t)1 << (CHAR_BIT * sizeof(uint64_t) - 1)) ) >> (shift-1)); // а тут вообще UB
    }
    
    
    int main(void)
    {
      // tests
      for (int i = 0; i <= 64; i++) // пробуем сдвигать от 0 до 64 включительно.
      {
        // for (uint128_t j = 0; j < UINT64_MAX+1; j++) - какая формальная верификация )))
        for (uint64_t j = 0; j < 100; j++)
        {
          if (add1bit_left_1(j,i) != add1bit_left_2(j,i))
          {
            printf("error1\n");
            printf("%" PRIu64 " %d\n", j,i);
            return EXIT_FAILURE;
          }
          if (add1bit_left_1(j,i) != add1bit_left_3(j,i))
            printf("error2\n");
          if (add1bit_left_2(j,i) != add1bit_left_3(j,i))
            printf("error3\n");
        }
      }
      printf("%" PRIX64 "\n", add1bit_left_1(0,0));
      printf("%" PRIX64 "\n", add1bit_left_2(0,0));
      printf("%" PRIX64 "\n", add1bit_left_3(0,0));
      printf("%" PRIX64 " - bug\n", add1bit_left_1_bug(0,0));
      printf("%" PRIX64 " - bug\n", add1bit_left_2_bug(0,0));
      puts("");
      printf("%" PRIX64 "\n", add1bit_left_1(0,1));
      printf("%" PRIX64 "\n", add1bit_left_2(0,1));
      printf("%" PRIX64 "\n", add1bit_left_3(0,1));
      printf("%" PRIX64 " - bug\n", add1bit_left_1_bug(0,1));
      printf("%" PRIX64 " - bug\n", add1bit_left_2_bug(0,1));
      puts("");
      printf("%" PRIX64 "\n", add1bit_left_1(0,2));
      printf("%" PRIX64 "\n", add1bit_left_2(0,2));
      printf("%" PRIX64 "\n", add1bit_left_3(0,2));
      printf("%" PRIX64 " - bug\n", add1bit_left_2_bug(0,2));
      printf("%" PRIX64 " - bug\n", add1bit_left_2_bug(0,2));
      puts("");
      printf("%" PRIX64 "\n", add1bit_left_1(0,64));
      printf("%" PRIX64 "\n", add1bit_left_2(0,64));
      printf("%" PRIX64 "\n", add1bit_left_3(0,64));
      printf("%" PRIX64 " - bug\n", add1bit_left_1_bug(0,64));
      printf("%" PRIX64 " - bug\n", add1bit_left_2_bug(0,64));
      return EXIT_SUCCESS;
    }

    Вореанты говнофункции, которая сдвигает влево uint64_t но набрасывает единички вместо ноликов.

    Запостил: j123123, 17 Ноября 2021

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

    • > Вореанты говнофункции, которая сдвигает влево uint64_t но набрасывает единички вместо ноликов.
      Ну т.е. не влево а вправо.

      Почему двоичные сдвиги в Си сделаны настолько по-дурацки?
      Ответить
    • > от 0 до 64 включительно

      Сложная задачка, да. От 1 до 64 или от 0 до 63 было бы намного легче...

      А всё интел со своей экономией транзисторов в barrel shifter'е. Хотя с другой стороны один фиг бы кто-то выебнулся и стандарт бы так и остался с UB/ID.
      Ответить
      • Упрощать задачку - всё равно, что упрощать переменную.
        Ответить
      • я думал двигать uint64_t на 65 бит можно, только signed нельзя
        Ответить
        • на 64 бита тоже нельзя.
          Ответить
          • unsigned??
            Ответить
            • Да, нельзя сдвигать uint64_t на 64 бита влево. Это UB
              И на 64 бита вправо тоже нельзя
              Ответить
              • Поясните пожалста для тупых следующую цитату из стандарта

                The value of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are zero-filled. If E1 has an unsigned type, the value of the result is E1 × 2E2, reduced modulo one more than the maximum value representable in the result type. Otherwise, if E1 has a signed type and non-negative value, and E1 × 2E2 is representable in the corresponding unsigned type of the result type, then that value, converted to the result type, is the resulting value; otherwise, the behavior is undefined.

                The value of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a non-negative value, the value of the result is the integral part of the quotient of E1/2E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.
                Ответить
              • а бля

                я слепошарый

                извините

                . The behavior is undefined if the right operand is negative, or greater than or equal to the length in bits of the promoted left operand.

                то есть можно сдвинуть 65 раз на 1, но 1 раз на 64 нельзя
                Ответить
                • Можно сделать такую хуйню:
                  uint64 safe_uint64_shift(const uint64_t a, const uint_fast8_t sh)
                  {
                    assert(sh <= 64);
                    if(sh == 0) return a;
                    return (a << (sh-1)) << 1;
                  }
                  Ответить
        • Изначальная проблема в том, что некоторые процы тупо не умеют "двигать на 65".

          Допустим при 32-битном регистре только 5 младших бит правого операнда разведены на barrel shifter (сдвиги на 1, 2, 4, 8 и 16), а остальные тупо идут в /dev/null. Из-за этого вместо сдвига на 65 у них получается сдвиг на 1.

          А "интуитивная" реализация с нулями при слишком большом сдвиге обойдется дороже.
          Ответить
          • То есть сначала была проблема в отсутствии машинки для быстрого сдвига, а потом это отлили в стандарте?
            Ответить
            • Ну стандарт же всегда пытается усидеть на джвух стульях и разрешить все реализации...
              Ответить
          • Неужели настолько дороже? По сравнению самим шифтером? Я, конечно, не очень разбираюсь, но вроде там нужно OR всех старших бит, NOT и AND на каждый бит результата... Или просто жесткая экономия?..
            Ответить
            • Пфу. О чем речь?
              Ответить
            • Ну да, лишний слой логики с этими or/and, который добавляется к толщине самого шифтера. Critical path для сдвигов удлиняется, можно уже в тайминги не уложиться, возможно придётся частоту скидывать...
              Ответить
              • Я до последнего предполагал, что пидоров на говнокоде нет. Но оказалось, что у кое-кого член таки потягивает говнецом...
                Ответить

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