История изменений
Исправление V1KT0P, (текущая версия) :
Заинтересовался какой код сгенерировд clang под RISC-V. Решил привести результат компиляции в псевдокод:
Для понимания того что происходит в коде накидал себе визуально процесс умножения столбиком:
D*B=EF
D*A=GH
C*B=IJ
C*A=KL
A B
C D
-----------------------------
G H+E F
K L+I J
_____________________________
K G+L+I H+E+J F
Упрощенный псевдокод (стало интересно почему нету умножения L = C * A, это переполнение как-то косвенно определяется?):
A = a.h
B = a.l
C = b.h
D = b.l
struct {
uint64 h;
uint64 l;
} u128
bool mul_128_overflow(u128 a, u128 b, u128* c)
{
u64 A = a.h;
u64 B = a.l;
u64 C = b.h;
u64 D = b.l
u64 F = D * B;
u64 H = D * A;
u64 E = D * B;
u64 J = C * B;
u64 G = D * A;
u64 I = C * B;
u64 HEJ = H + J + E;
u64 E_overflow = HEJ < E;
u64 C_exists = C != 0;
u64 A_exists = A != 0;
u64 C_A_exists = A_exists & C_exists;
u64 G_exists = G != 0;
u64 I_exists = I != 0;
u64 overflow = E_overflow | C_A_exists | G_exists | I_exists;
c->l = F;
c->h = HEJ;
return overflow;
}
Полный псевдокод соответствующий ассемблеру:
bool mul_128_overflow(u128 a, u128 b, u128* c)
{
u64 A = a.h;
u64 B = a.l;
u64 C = b.h;
u64 D = b.l
u64 J = C * B; //mul a6, a3, a0
u64 H = D * A; //mul a5, a1, a2
u64 HJ = H + J; //add a6, a6, a5
u64 E = D * B; //mulhu a5, a0, a2
u64 HEJ = HJ + E; //add a6, a6, a5
u64 E_overflow = HEJ < E; //sltu a7, a6, a5
u64 C_exists = C != 0; //snez t0, a3
u64 A_exists = A != 0; //snez a5, a1
u64 C_A_exists = A_exists & C_exists; //and a5, a5, t0
u64 G = D * A; //mulhu a1, a1, a2
u64 G_exists = G != 0; //snez a1, a1
u64 G_C_A_exists = G_exists | C_A_exists; //or a1, a1, a5
u64 I = C * B; //mulhu a3, a3, a0
u64 I_exists = I != 0; //snez a3, a3
u64 G_I_C_A_exists = G_C_A_exists | I_exists; //or a1, a1, a3
u64 overflow = G_I_C_A_exists | E_overflow; //or a1, a1, a7
u64 F = D * B; //mul a0, a0, a2
c->l = F; //sd a0, 0(a4)
c->h = HEJ; //sd a6, 8(a4)
return overflow; //mv a0, a1 //ret
}
Исходная версия V1KT0P, :
Заинтересовался какой код сгенерировд clang под RISC-V. Решил привести результат компиляции в псевдокод:
Для понимания того что происходит в коде накидал себе визуально процесс умножения столбиком:
D*B=EF
D*A=GH
C*B=IJ
C*A=KL
A B
C D
-----------------------------
G H+E F
K L+I J
_____________________________
K G+L+I H+E+J F
Упрощенный псевдокод (стало интересно почему нету умножения L = C * A, это переполнение как-то косвенно определяется?):
A = a.h
B = a.l
C = b.h
D = b.l
struct {
uint64 h;
uint64 l;
} u128
bool mul_128_overflow(u128 a, u128 b, u128* c)
{
u64 A = a.h;
u64 B = a.l;
u64 C = b.h;
u64 D = b.l
u64 F = D * B;
u64 H = D * A;
u64 E = D * B;
u64 J = C * B;
u64 G = D * A;
u64 I = C * B;
u64 HEJ = H + J + E;
u64 E_overflow = HEJ < E;
u64 C_A_exists = A & C;
u64 C_exists = C != 0;
u64 A_exists = A != 0;
u64 G_exists = G != 0;
u64 I_exists = I != 0;
u64 overflow = E_overflow | C_A_exists | G_exists | I_exists;
c->l = F;
c->h = HEJ;
return overflow;
}
Полный псевдокод соответствующий ассемблеру:
bool mul_128_overflow(u128 a, u128 b, u128* c)
{
u64 A = a.h;
u64 B = a.l;
u64 C = b.h;
u64 D = b.l
u64 J = C * B; //mul a6, a3, a0
u64 H = D * A; //mul a5, a1, a2
u64 HJ = H + J; //add a6, a6, a5
u64 E = D * B; //mulhu a5, a0, a2
u64 HEJ = HJ + E; //add a6, a6, a5
u64 E_overflow = HEJ < E; //sltu a7, a6, a5
u64 C_exists = C != 0; //snez t0, a3
u64 A_exists = A != 0; //snez a5, a1
u64 C_A_exists = A & C; //and a5, a5, t0
u64 G = D * A; //mulhu a1, a1, a2
u64 G_exists = G != 0; //snez a1, a1
u64 G_C_A_exists = G_exists | C_A_exists; //or a1, a1, a5
u64 I = C * B; //mulhu a3, a3, a0
u64 I_exists = I != 0; //snez a3, a3
u64 G_I_C_A_exists = G_C_A_exists | I_exists; //or a1, a1, a3
u64 overflow = G_I_C_A_exists | E_overflow; //or a1, a1, a7
u64 F = D * B; //mul a0, a0, a2
c->l = F; //sd a0, 0(a4)
c->h = HEJ; //sd a6, 8(a4)
return overflow; //mv a0, a1 //ret
}