Saturação subtrair / adicionar para bytes não assinados

83

Imagine que tenho dois bytes não assinados be x. Preciso calcular bsubcomo b - xe baddcomo b + x. No entanto, não quero que ocorra underflow / overflow durante essas operações. Por exemplo (pseudocódigo):

b = 3; x = 5;
bsub = b - x; // bsub must be 0, not 254

e

b = 250; x = 10;
badd = b + x; // badd must be 255, not 4

A maneira óbvia de fazer isso inclui ramificação:

bsub = b - min(b, x);
badd = b + min(255 - b, x);

Só me pergunto se há alguma maneira melhor de fazer isso, ou seja, por meio de algumas manipulações de bits?

ovk
fonte
13
y ^ ((x ^ y) & -(x < y))para inttipos avalia min(x, y)sem ramificação. Isso pode fazer parte de uma solução eventual, com base no que você tem até agora.
Bate
3
Talvez Inteiro Incremento Preso? é útil.
Shafik Yaghmour
8
Esta é uma pergunta C ou C ++? Escolha um.
fuz
9
@AlanCampbell é chamado de Aritmética de Saturação .
Shafik Yaghmour
7
Você precisa que seja portátil? Porque se você está olhando para uma arquitetura específica, provavelmente há uma única instrução interessante. Eu sei que o ARM tem adição e subtração de vetores de saturação para bytes. No X86, o _mm_adds_epi8intrínseco fará uma adição saturante de 16 bytes em uma única instrução.
porglezomp

Respostas:

86

O artigo Branchfree Saturating Arithmetic fornece estratégias para isso:

Sua solução de adição é a seguinte:

u32b sat_addu32b(u32b x, u32b y)
{
    u32b res = x + y;
    res |= -(res < x);

    return res;
}

modificado para uint8_t:

uint8_t  sat_addu8b(uint8_t x, uint8_t y)
{
    uint8_t res = x + y;
    res |= -(res < x);

    return res;
}

e sua solução de subtração é:

u32b sat_subu32b(u32b x, u32b y)
{
    u32b res = x - y;
    res &= -(res <= x);

    return res;
}

modificado para uint8_t:

uint8_t sat_subu8b(uint8_t x, uint8_t y)
{
    uint8_t res = x - y;
    res &= -(res <= x);

    return res;
}
Shafik Yaghmour
fonte
2
@ user1969104 pode ser esse o caso, mas como o comentário no artigo indica, isso é resolvido convertendo para não assinado antes de aplicar o menos unário. Na prática , é improvável que você tenha que lidar com qualquer outra coisa que não seja o complemento de dois .
Shafik Yaghmour
2
Esta pode ser uma boa resposta C, mas não é uma resposta C ++ muito boa.
Yakk - Adam Nevraumont
4
@Yakk O que torna esta resposta C ++ "ruim"? Essas são operações matemáticas básicas, e não vejo como seriam interpretadas como apenas C ou C ++ ruim.
JPhi1618
4
@ JPhi1618 Uma resposta C ++ melhor pode ser template<class T>struct sat{T t;};com operadores sobrecarregados que saturam? Uso adequado de namespaces. Principalmente açúcar.
Yakk - Adam Nevraumont
6
@Yakk, ah, ok. Eu apenas vi isso como um exemplo mínimo que o OP poderia adaptar conforme necessário. Eu não esperaria ver uma implementação tão completa. Agradeço por ter esclarecido.
JPhi1618
40

Um método simples é detectar o estouro e redefinir o valor conforme abaixo

bsub = b - x;
if (bsub > b)
{
    bsub = 0;
}

badd = b + x;
if (badd < b)
{
    badd = 255;
}

O GCC pode otimizar a verificação de estouro em uma atribuição condicional ao compilar com -O2.

Eu medi o quanto de otimização comparando com outras soluções. Com mais de 1.000.000 de operações no meu PC, esta solução e a de @ShafikYaghmour tiveram em média 4,2 segundos, e a de @chux em média 4,8 segundos. Esta solução também é mais legível.

user1969104
fonte
5
@ user694733 Não é totalmente otimizado, é otimizado para uma atribuição condicional dependendo do sinalizador de transporte.
fuz
2
Sim, user694733 está certo. Ele é otimizado para uma atribuição condicional.
user1969104
Isso não funcionaria para todos os casos, por exemplo badd: b = 155 x = 201, do que badd = 156, e isso é maior do que b. Você precisaria comparar o resultado com o min () ou max () das duas variáveis, dependendo da operação
Cristian F
@CristianF Como você calcula 155 + 201 = 156? Acho que precisa ser 155 + 201 = 356% 256 = 100. Não acho que min (), max () seja necessário em qualquer combinação de valores b, x.
user1969104
16

Para subtração:

diff = (a - b)*(a >= b);

Adição:

sum = (a + b) | -(a > (255 - b))

Evolução

// sum = (a + b)*(a <= (255-b)); this fails
// sum = (a + b) | -(a <= (255 - b)) falis too

Obrigado a @R_Kapp

Graças a @NathanOliver

Este exercício mostra o valor de simplesmente codificar.

sum = b + min(255 - b, a);
chux - Reintegrar Monica
fonte
Por sumtalvez (a + b) | -(a <= (255 - b))?
R_Kapp
Você poderia fazer sum = ((a + b) | (!!((a + b) & ~0xFF) * 0xFF)) & 0xFF, supondo sizeof(int) > sizeof(unsigned char), mas isso parece tão complexo que não sei se você ganharia alguma coisa com isso (além de dor de cabeça).
user694733
@ user694733 Sim e talvez até (a+b+1)*(a <= (255-b)) - 1.
chux - Reintegrar Monica em
@NathanOliver Obrigado pelo descuido - o aspecto revelador disso é que o subfoi tão fácil quanto o era 0. Mas outros limites apresentam complicações e seguem o comentário do usuário 2079303 .
chux - Reintegrar Monica
1
@ user1969104 OP não foi claro sobre "melhor" (espaço de código vs. desempenho de velocidade) nem plataforma de destino nem compilador. A avaliação da velocidade faz mais sentido no contexto do problema maior não publicado.
chux - Reintegrar Monica em
13

Se você estiver usando uma versão recente o suficiente do gcc ou clang (talvez também alguns outros), você pode usar embutidos para detectar estouro.

if (__builtin_add_overflow(a,b,&c))
{
  c = UINT_MAX;
}
erebos
fonte
Esta é a melhor resposta. Usar o compilador embutido em vez da mágica de bits não é apenas mais rápido, mas também mais claro e torna o código mais sustentável.
Cefalópode
Obrigado, @erebos. Definitivamente vou tentar isso em plataformas onde estiver disponível.
ovk
3
Não consigo fazer o gcc gerar código brachless com este, o que é um pouco decepcionante. O que é especialmente infeliz aqui é que o clang usa nomes diferentes para eles .
Shafik Yaghmour
1
@Cephalopod E é completamente não-plataforma cruzada, mas provavelmente nem funciona em outro compilador. Não é uma boa solução para o século 21.
Ela782
1
@ Ela782 É exatamente o contrário: os embutidos não são uma boa solução para o século XX. Bem vindo ao futuro!
Cefalópode
3

Para adição:

unsigned temp = a+b;  // temp>>8 will be 1 if overflow else 0
unsigned char c = temp | -(temp >> 8);

Para subtração:

unsigned temp = a-b;  // temp>>8 will be 0xFF if neg-overflow else 0
unsigned char c = temp & ~(temp >> 8);

Não são necessários operadores de comparação ou multiplicações.

supergato
fonte
3

Se você estiver disposto a usar assembly ou intrínseco, acho que tenho uma solução ideal.

Para subtração:

Podemos usar a sbbinstrução

No MSVC, podemos usar a função intrínseca _subborrow_u64 (também disponível em outros tamanhos de bits).

É assim que é usado:

// *c = a - (b + borrow)
// borrow_flag is set to 1 if (a < (b + borrow))
borrow_flag = _subborrow_u64(borrow_flag, a, b, c);

Aqui está como poderíamos aplicá-lo à sua situação

uint64_t sub_no_underflow(uint64_t a, uint64_t b){
    uint64_t result;
    borrow_flag = _subborrow_u64(0, a, b, &result);
    return result * !borrow_flag;
}

Para adição:

Podemos usar a adcxinstrução

No MSVC, podemos usar a função intrínseca _addcarry_u64 (também disponível em outros tamanhos de bits).

É assim que é usado:

// *c = a + b + carry
// carry_flag is set to 1 if there is a carry bit
carry_flag = _addcarry_u64(carry_flag, a, b, c);

Aqui está como poderíamos aplicá-lo à sua situação

uint64_t add_no_overflow(uint64_t a, uint64_t b){
    uint64_t result;
    carry_flag = _addcarry_u64(0, a, b, &result);
    return !carry_flag * result - carry_flag;
}

Eu não gosto deste tanto quanto do de subtração, mas acho que é bem bacana.

Se o add estourar carry_flag = 1,. Not-ing carry_flagresulta em 0, portanto, !carry_flag * result = 0quando há estouro. E uma vez 0 - 1que definirá o valor integral sem sinal para seu máximo, a função retornará o resultado da adição se não houver transporte e retornará o máximo do valor integral escolhido se houver transporte.

MichaelMitchell
fonte
1
Você pode querer mencionar que esta resposta é para uma arquitetura de conjunto de instruções específico (x86?) E exigirá a reimplementação para cada arquitetura de destino (SPARC, MIPS, ARM, etc)
Toby Speight
2

que tal isso:

bsum = a + b;
bsum = (bsum < a || bsum < b) ? 255 : bsum;

bsub = a - b;
bsub = (bsub > a || bsub > b) ? 0 : bsub;

fonte
Corrigi o erro de digitação (óbvio?), Mas ainda não acho que esteja correto.
Bate
Isso também inclui ramificação.
fuz
Vou deletar essa resposta apenas uma pergunta rápida na montagem sem otimização, qual é a diferença entre o operador ternário e a instrução if / else?
@GRC Não há diferença.
fuz
@GRC FUZxxl está certo, mas, como sempre, tente você mesmo. Mesmo que você não saiba assembly (você poderia fazer uma pergunta aqui no SO se algo não estiver claro para você), apenas verificando o comprimento / instruções você saberá.
edmz
2

Tudo pode ser feito em aritmética de bytes sem sinal

// Addition without overflow
return (b > 255 - a) ? 255 : a + b

// Subtraction without underflow
return (b > a) ? 0 : a - b;
Yves Daoust
fonte
1
Esta é realmente uma das melhores soluções. Todos os outros que fizeram a subtração ou adição antes estão na verdade criando um comportamento indefinido em C ++, resultando no compilador sendo capaz de fazer o que quiser. Na prática, você pode principalmente prever o que vai acontecer, mas ainda assim.
Adrien Hamelin
2

Se você quiser fazer isso com dois bytes, use o código mais simples possível.

Se você quiser fazer isso com 20 bilhões de bytes, verifique quais instruções vetoriais estão disponíveis em seu processador e se elas podem ser usadas. Você pode descobrir que seu processador pode fazer 32 dessas operações com uma única instrução.

gnasher729
fonte
2

Você também pode usar a biblioteca numérica segura no Boost Library Incubator . Ele fornece substitutos imediatos para int, long, etc ... que garantem que você nunca terá um estouro, estouro negativo, etc.

Robert Ramey
fonte
7
Fornecer um exemplo de como usar a biblioteca tornaria essa resposta melhor. Além disso, eles fornecem uma garantia sem braçadeira?
Shafik Yaghmour
A biblioteca possui ampla documentação e exemplos. Mas no final do dia é tão fácil quanto incluir o cabeçalho apropriado e substituir safe <int> por int.
Robert Ramey
sem ramos? Eu acho que você homem sem ramos. A biblioteca usa a metaprogramação de modelo para incluir verificações de tempo de execução apenas quando necessário. Por exemplo, unsigned char times unsigned char resultarão em unsigned int. Isso nunca pode estourar, portanto, nenhuma verificação precisa ser feita. Por outro lado, tempos não assinados não assinados podem estourar, portanto, devem ser verificados em tempo de execução.
Robert Ramey
1

Se você chamar muito esses métodos, a maneira mais rápida não seria a manipulação de bits, mas provavelmente uma tabela de consulta. Defina uma matriz de comprimento 511 para cada operação. Exemplo para menos (subtração)

static unsigned char   maxTable[511];
memset(maxTable, 0, 255);           // If smaller, emulates cutoff at zero
maxTable[255]=0;                    // If equal     - return zero
for (int i=0; i<256; i++)
    maxTable[255+i] = i;            // If greater   - return the difference

A matriz é estática e inicializada apenas uma vez. Agora sua subtração pode ser definida como método inline ou usando o pré-compilador:

#define MINUS(A,B)    maxTable[A-B+255];

Como funciona? Bem, você deseja pré-calcular todas as subtrações possíveis para caracteres não assinados. Os resultados variam de -255 a +255, total de 511 resultados diferentes. Definimos uma matriz de todos os resultados possíveis, mas como em C não podemos acessá-la a partir de índices negativos, usamos +255 (em [A-B + 255]). Você pode remover esta ação definindo um ponteiro para o centro da matriz.

const unsigned char *result = maxTable+255;
#define MINUS(A,B)    result[A-B];

use-o como:

bsub  = MINUS(13,15); // i.e 13-15 with zero cutoff as requested

Observe que a execução é extremamente rápida. Apenas uma subtração e uma deferência de ponteiro para obter o resultado. Sem ramificação. Os arrays estáticos são muito curtos, então eles serão totalmente carregados no cache da CPU para acelerar ainda mais o cálculo

O mesmo funcionaria para adição, mas com uma tabela um pouco diferente (os primeiros 256 elementos serão os índices e os últimos 255 elementos serão iguais a 255 para emular o corte além de 255.

Se você insiste na operação de bits, as respostas que usam (a> b) estão erradas. Isso ainda pode ser implementado como ramificação. Use a técnica do bit de sinal

// (num1>num2) ? 1 : 0
#define        is_int_biggerNotEqual( num1,num2) ((((__int32)((num2)-(num1)))&0x80000000)>>31)

Agora você pode usá-lo para cálculo de subtração e adição.

Se você quiser emular as funções max (), min () sem ramificação, use:

inline __int32 MIN_INT(__int32 x, __int32 y){   __int32 d=x-y; return y+(d&(d>>31)); }              

inline __int32 MAX_INT(__int32 x, __int32 y){   __int32 d=x-y; return x-(d&(d>>31)); }

Meus exemplos acima usam inteiros de 32 bits. Você pode alterá-lo para 64, embora eu acredite que os cálculos de 32 bits sejam um pouco mais rápidos. Você decide

DanielHsH
fonte
2
Provavelmente não vai, na verdade: primeiro, é claro, carregar a mesa é lento. As operações de bits levam 1 ciclo, o carregamento da memória leva aproximadamente 80 ns; mesmo com o cache L1, estamos na faixa de 20 ns, o que é quase 7 ciclos em uma CPU de 3GHz.
edmz
Você não está totalmente correto. O método LUT requer alguns símbolos, mas a manipulação de bits também não é um ciclo único. Existem algumas ações sequenciais. Por exemplo, apenas calcular o MAX () requer 2 subtrações e operação lógica e um deslocamento para a direita. E não se esqueça da promoção / rebaixamento de número inteiro
DanielHsH
1
Eu quis dizer que as operações bit a bit levam 1 ciclo, assumindo naturalmente operandos de registradores. Com o código que Shafik mostrou, o clang produz 4 instruções elementares. Além disso (x > y), não tem ramos.
edmz
Primeiro, (x> y) pode usar ramificação. Você não sabe em qual arquitetura está executando. Eu tendo a concordar que possivelmente não tem ramificações na arquitetura Intel. A maioria dos smartphones não é Intel. Essa também é a razão pela qual você não pode saber quantas instruções de montagem haverá. Experimente minha solução em seu PC. Estou interessado em ouvir os resultados.
DanielHsH
1
O cache L1 é muito mais rápido do que 20 ns, é da ordem de talvez 4 ciclos do processador. E provavelmente estará usando uma unidade de execução não utilizada de outra forma e será totalmente pipeline de qualquer maneira. Meça isto. E 20ns são 60 ciclos em uma CPU de 3 GHz.
gnasher729