Como fazer além de saturação não assinado em C?
https://stackoverflow.com/questions/121240
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
O que é a melhor maneira (mais limpo, mais eficiente) a escrever saturando disso em C?
A função ou macro deve adicionar duas entradas não assinados (necessidade ambos os 16 e 32 bits versões) e retornar todos os bits de um (0xFFFF ou 0xFFFFFFFF), se a soma transborda.
Target é x86 e ARM usando gcc (4.1.2) e Visual Studio (apenas para simulação, assim que uma implementação de fallback é OK lá).
Solução
Você provavelmente quer código C portátil aqui, que seu compilador vai se transformar em ARM adequada montagem. ARM tem movimentos condicionais, e estes podem ser condicionada ao transbordamento. O algoritmo torna-se então add, e condicionalmente definir o destino para unsigned (-1) se foi detectado excesso.
uint16_t add16(uint16_t a, uint16_t b)
{
uint16_t c = a + b;
if (c<a) /* Can only happen due to overflow */
c = -1;
return c;
}
Note que isso difere de outros algoritmos em que ele corrige excesso, em vez de confiar em um outro cálculo de detectar estouro.
x86-64 tinido 3,7 -O3 saída para adds32 : significativamente melhor do que qualquer outra resposta:
add edi, esi
mov eax, -1
cmovae eax, edi
ret
ARMv7: gcc 4.8 -O3 -mcpu=cortex-a15 -fverbose-asm saída para adds32 :
adds r0, r0, r1 @ c, a, b
it cs
movcs r0, #-1 @ conditional-move
bx lr
16bit: ainda não usa instruções add unsigned-saturando da ARM (UADD16)
add r1, r1, r0 @ tmp114, a
movw r3, #65535 @ tmp116,
uxth r1, r1 @ c, tmp114
cmp r0, r1 @ a, c
ite ls @
movls r0, r1 @,, c
movhi r0, r3 @,, tmp116
bx lr @
Outras dicas
Em C simples:
uint16_t sadd16(uint16_t a, uint16_t b)
{ return (a > 0xFFFF - b) ? 0xFFFF : a + b; }
uint32_t sadd32(uint32_t a, uint32_t b)
{ return (a > 0xFFFFFFFF - b) ? 0xFFFFFFFF : a + b;}
que é quase macro-ized e directamente transmite o significado.
Na IA32 sem saltos condicionais:
uint32_t sadd32(uint32_t a, uint32_t b)
{
#if defined IA32
__asm
{
mov eax,a
xor edx,edx
add eax,b
setnc dl
dec edx
or eax,edx
}
#elif defined ARM
// ARM code
#else
// non-IA32/ARM way, copy from above
#endif
}
aritmética Em ARM você pode já ter saturado embutido. Os ARMv5 DSP-extensões podem saturar registradores para qualquer bit de comprimento. Também na saturação ARM é geralmente mais barato porque você pode excute a maioria das instruções condicional.
ARMv6 mesmo saturou adição, subtracção e todas as outras coisas para 32 bits e números embalados.
No x86 você ficar saturado aritmética, quer através MMX ou SSE.
Tudo isso necessidades assembler, por isso não é o que você pediu.
Existem C-truques para não saturadas aritmética bem. Este código não pouco além em quatro bytes de um DWORD saturado. É baseado na idéia de calcular 32 meio-somadores em paralelo, por exemplo, adicionando números sem carry estouro.
Isto é feito em primeiro lugar. Então o transporta são calculados, adicionado e substituído com uma máscara se a adição iria transbordar.
uint32_t SatAddUnsigned8(uint32_t x, uint32_t y)
{
uint32_t signmask = 0x80808080;
uint32_t t0 = (y ^ x) & signmask;
uint32_t t1 = (y & x) & signmask;
x &= ~signmask;
y &= ~signmask;
x += y;
t1 |= t0 & x;
t1 = (t1 << 1) - (t1 >> 7);
return (x ^ t0) | t1;
}
Você pode obter o mesmo para 16 bits (ou qualquer tipo de bit-campo), alterando a constante signmask e as mudanças na parte inferior como esta:
uint32_t SatAddUnsigned16(uint32_t x, uint32_t y)
{
uint32_t signmask = 0x80008000;
uint32_t t0 = (y ^ x) & signmask;
uint32_t t1 = (y & x) & signmask;
x &= ~signmask;
y &= ~signmask;
x += y;
t1 |= t0 & x;
t1 = (t1 << 1) - (t1 >> 15);
return (x ^ t0) | t1;
}
uint32_t SatAddUnsigned32 (uint32_t x, uint32_t y)
{
uint32_t signmask = 0x80000000;
uint32_t t0 = (y ^ x) & signmask;
uint32_t t1 = (y & x) & signmask;
x &= ~signmask;
y &= ~signmask;
x += y;
t1 |= t0 & x;
t1 = (t1 << 1) - (t1 >> 31);
return (x ^ t0) | t1;
}
Acima faz o mesmo para 16 e 32 bit valores.
Se você não precisar do recurso que as funções de adicionar e saturar vários valores em paralelo apenas mascarar os bits que você precisa. Em ARM você também deseja alterar a constante signmask porque ARM não pode carregar todas as possíveis constantes de 32 bits em um único ciclo.
Editar: As versões paralelas são mais prováveis ??mais lento do que os métodos para a frente em linha reta, mas eles são mais rápidos se você tem que saturar mais de um valor de cada vez
.Se você se preocupa com o desempenho, você realmente quer fazer esse tipo de coisa em SIMD, onde x86 tem aritmética de saturação nativa.
Devido a esta falta de saturar aritmética em matemática escalar, pode-se obter casos em que as operações feitas on-wide de 4 variáveis ??SIMD é mais de 4 vezes mais rápido do que o equivalente C (e, correspondentemente verdadeiro com-wide 8-variável SIMD):
sub8x8_dct8_c: 1332 clocks
sub8x8_dct8_mmx: 182 clocks
sub8x8_dct8_sse2: 127 clocks
solução ramo Zero:
uint32_t sadd32(uint32_t a, uint32_t b)
{
uint64_t s = (uint64_t)a+b;
return -(s>>32) | (uint32_t)s;
}
Um bom compilador irá otimizar isso para evitar fazer qualquer aritmética de 64 bits real (s>>32 será apenas a bandeira de transporte, e -(s>>32) é o resultado de sbb %eax,%eax).
Em asm x86 (AT & T sintaxe, a e b em eax e ebx, resultado em eax):
add %eax,%ebx
sbb %eax,%eax
or %ebx,%eax
8 e 16 bits deveria ser óbvio. versão assinada pode exigir um pouco mais de trabalho.
uint32_t saturate_add32(uint32_t a, uint32_t b)
{
uint32_t sum = a + b;
if ((sum < a) || (sum < b))
return ~((uint32_t)0);
else
return sum;
} /* saturate_add32 */
uint16_t saturate_add16(uint16_t a, uint16_t b)
{
uint16_t sum = a + b;
if ((sum < a) || (sum < b))
return ~((uint16_t)0);
else
return sum;
} /* saturate_add16 */
Editar:. Agora que você postou sua versão, eu não tenho certeza meu é qualquer produto de limpeza / melhor / mais eficiente / mais studly
Eu não tenho certeza se este é mais rápido do que a solução da Skizz (sempre perfil), mas aqui está uma solução de montagem alternativa no-galho. Note que isto requer a instrução de movimentação condicional (CMOV), que eu não tenho certeza está disponível em seu alvo.
uint32_t sadd32(uint32_t a, uint32_t b)
{
__asm
{
movl eax, a
addl eax, b
movl edx, 0xffffffff
cmovc eax, edx
}
}
A implementação atual que estamos usando é:
#define sadd16(a, b) (uint16_t)( ((uint32_t)(a)+(uint32_t)(b)) > 0xffff ? 0xffff : ((a)+(b)))
#define sadd32(a, b) (uint32_t)( ((uint64_t)(a)+(uint64_t)(b)) > 0xffffffff ? 0xffffffff : ((a)+(b)))
O melhor desempenho geralmente envolvem linha de montagem (como alguns já disse).
Mas para C portátil, estas funções envolvem apenas uma comparação e nenhum tipo de fundição (e, portanto, eu acredito ideal):
unsigned saturate_add_uint(unsigned x, unsigned y)
{
if (y>UINT_MAX-x) return UINT_MAX;
return x+y;
}
unsigned short saturate_add_ushort(unsigned short x, unsigned short y)
{
if (y>USHRT_MAX-x) return USHRT_MAX;
return x+y;
}
Como macros, tornam-se:
SATURATE_ADD_UINT(x, y) (((y)>UINT_MAX-(x)) ? UINT_MAX : ((x)+(y)))
SATURATE_ADD_USHORT(x, y) (((y)>SHRT_MAX-(x)) ? USHRT_MAX : ((x)+(y)))
Deixo versões para 'unsigned long' e 'unsigned long long' como um exercício para o leitor. ; -)
Apenas no caso de alguém quiser saber uma implementação sem ramificação usando 2 de inteiros complemento de 32 bits.
Warning! Esse código usa a operação indefinido: "deslocamento para a direita por -1" e, portanto, explora a propriedade do Intel Pentium SAL instrução para mascarar a contagem operando para 5 bits.
int32_t sadd(int32_t a, int32_t b){
int32_t sum = a+b;
int32_t overflow = ((a^sum)&(b^sum))>>31;
return (overflow<<31)^(sum>>overflow);
}
É a melhor implementação conhecido por mim
suponho, a melhor maneira para x86 é usar inline assembler para verificar bandeira estouro depois disso. Algo como:
add eax, ebx
jno @@1
or eax, 0FFFFFFFFh
@@1:
.......
Não é muito portátil, mas IMHO a forma mais eficiente.
Uma alternativa para a solução ramo livre x86 asm é (sintaxe AT & T, a e b em EAX e EBX, resultado em EAX):
add %eax,%ebx
sbb $0,%ebx
Usando C ++, você pode escrever uma variante mais flexível do Remo.D 's solução:
template<typename T>
T sadd(T first, T second)
{
static_assert(std::is_integral<T>::value, "sadd is not defined for non-integral types");
return first > std::numeric_limits<T>::max() - second ? std::numeric_limits<T>::max() : first + second;
}
Isto pode ser facilmente traduzidos para C - usando os limites definidos em limits.h. Observe também que a Largura fixa tipos inteiros pode não estiveram disponíveis em seu sistema.
//function-like macro to add signed vals,
//then test for overlow and clamp to max if required
#define SATURATE_ADD(a,b,val) ( {\
if( (a>=0) && (b>=0) )\
{\
val = a + b;\
if (val < 0) {val=0x7fffffff;}\
}\
else if( (a<=0) && (b<=0) )\
{\
val = a + b;\
if (val > 0) {val=-1*0x7fffffff;}\
}\
else\
{\
val = a + b;\
}\
})
Eu fiz um teste rápido e parece trabalho, mas não extensivamente bateu ainda! Isso funciona com sinal de 32 bit. op: o editor usado na página web não me deixa postar uma macro ou seja, a sua não compreensão não-recuado sintaxe etc
!int saturating_add(int x, int y)
{
int w = sizeof(int) << 3;
int msb = 1 << (w-1);
int s = x + y;
int sign_x = msb & x;
int sign_y = msb & y;
int sign_s = msb & s;
int nflow = sign_x && sign_y && !sign_s;
int pflow = !sign_x && !sign_y && sign_s;
int nmask = (~!nflow + 1);
int pmask = (~!pflow + 1);
return (nmask & ((pmask & s) | (~pmask & ~msb))) | (~nmask & msb);
}
Esta implementação não usar o controle de fluxos, operadores campare (==, !=) eo operador ?:. Ele só usa operadores bit a bit e operadores lógicos.
Saturação aritmética não é padrão para C, mas é muitas vezes implementada via intrínsecos do compilador, então a forma mais eficiente não será o mais limpo. Você deve adicionar blocos #ifdef para selecionar a maneira correta. resposta das MSalters é o mais rápido para a arquitetura x86. Para ARM você precisa usar a função __qadd16 (compilador ARM) de _arm_qadd16 (Microsoft Visual Studio) para a versão de 16 bits e __qadd para a versão de 32 bits. Eles vão ser automaticamente traduzidos para uma instrução ARM.
Links:
