- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 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 но набрасывает единички вместо ноликов.
Follow us!
Ну т.е. не влево а вправо.
Почему двоичные сдвиги в Си сделаны настолько по-дурацки?
Сложная задачка, да. От 1 до 64 или от 0 до 63 было бы намного легче...
А всё интел со своей экономией транзисторов в barrel shifter'е. Хотя с другой стороны один фиг бы кто-то выебнулся и стандарт бы так и остался с UB/ID.
И на 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 нельзя
Не?
Допустим при 32-битном регистре только 5 младших бит правого операнда разведены на barrel shifter (сдвиги на 1, 2, 4, 8 и 16), а остальные тупо идут в /dev/null. Из-за этого вместо сдвига на 65 у них получается сдвиг на 1.
А "интуитивная" реализация с нулями при слишком большом сдвиге обойдется дороже.
нашел
https://govnokod.xyz/_27825/#comment-772191
Ну да.
Уже лет 10 большую часть жопен-сорца фуззят и вылавливают такое UB говно.