Números binários: o que você precisa saber

Nos anos 1980, a programação de sistemas embarcados em Assembly era a regra; não havia compiladores C/C++ para sistemas embarcados e o programador era obrigado a conhecer o processador no nível mais básico (registradores, instruções no nível da máquina etc.) para implementar uma aplicação embarcada. Alguns anos depois, o quadro havia mudado um pouco, havia compiladores C para alguns processadores, mas em muitos casos o código binário gerado pelos compiladores ainda era de baixa qualidade. 

Atualmente o quadro é totalmente diferente, a tecnologia evoluiu bastante e os compiladores em geral fazem um trabalho melhor do que humanos para gerar códigos otimizados e, juntamente com microcontroladores ou processadores mais rápidos, permitiu praticamente aposentar a programação em Assembly, com raras exceções. É possível focar no desenvolvimento de algoritmos a maior parte do tempo, sem preocupação com detalhes sobre o funcionamento do processador ou da arquitetura subjacente. Entretanto, ainda existem casos em que o conhecimento básico de como computadores funcionam pode ser útil  para gerar código de melhor qualidade e evitar bugs.

Objetivo

Este artigo vai apresentar uma pequena função para determinar se um determinado intervalo de tempo previamente programado já expirou; ela pode ser usada para implementar temporizações em um sistema embarcado “bare metal” (isto é, que não usa um sistema operacional ou RTOS). As tarefas nesse sistema são codificadas para funcionar de forma cooperativa, executando sua função o mais rapidamente possível e cedendo o processador para permitir que outras tarefas executem.

Serão apresentadas duas implementações dessa função para demonstrar como a aplicação de conceitos básicos dos números binários pode levar a um código mais simples e eficiente.

Os Melhores Treinamentos sobre Sistemas embarcados e IoT

Cursos com professores qualificados para acelerar sua carreira e projetos

MATRÍCULE-SE AGORA

Conceitos

Este artigo não vai tratar dos conceitos básicos de números binários nem de sua aritmética. Recomenda-se ao leitor interessado fazer uma busca por “aritmética de binários” para obter materiais que se aprofundem no assunto.

No próprio portal Embarcados há alguns artigos sobre o tema que vale a pena consultar (alguns deles listados no final do artigo). Em particular, recomendo a leitura  do artigo da Elaine Cecília Gatto.

Para os exemplos a seguir, serão usados números de quatro bits por uma questão de simplicidade, mas o conceito pode ser estendido para dimensões maiores. 

A tabela abaixo apresenta números binários de 4 bits sem sinal com a representação correspondente de números inteiros na base decimal.

A tabela abaixo apresenta números binários de quatro bits com sinal, com a representação correspondentes em números inteiros na base decimal. Os números negativos são o complemento de dois (ou a dois) dos números positivos correspondentes.

Aplicação usando números de quatro bits

Suponhamos que temos um contador interno de quatro bits, sem sinal, que é incrementado a cada segundo. Esse contador conta de 0 a 15 e volta a zero, repetindo o ciclo indefinidamente. Em um dado momento obtemos o valor do contador e nossa tarefa no sistema embarcado “bare metal” decide se está na hora de executar suas funções. O pseudocódigo dessa tarefa seria:

if time_to_do_something() then
    do_something()
    set_next_do_something_time (delay)
return

Após a execução de do_something(), a função  set_next_do_something_time() obtém o valor atual do nosso contador interno, soma o valor delay e guarda o resultado em uma variável interna que será usada por time_to_do_something() posteriormente para determinar quando executar as funções dessa tarefa novamente.

O que a função time_to_do_something() precisa fazer para determinar que o intervalo de tempo programado passou? Ela pode, por exemplo, verificar se o valor do contador interno (vamos chamá-lo de now) é maior que o valor previamente armazenado (vamos chamá-lo de timeout) por set_next_do_something_time(). Infelizmente isso não funciona, porque nosso contador now conta até 15 e volta para zero e o teste vai falhar se, por exemplo, now é igual a 0 e timeout é igual a 15, quando de fato o teste deveria passar. 

Outra possibilidade é verificar se now é igual a timeout. Entretanto, digamos que timeout seja igual a 8 e now seja igual a 7 quando time_to_do_something() é executada: a tarefa retorna porque ainda não é hora de executar sua função. Digamos então que as demais tarefas que executam antes dessa tarefa ser chamada novamente demoram muito para executar e, quando esta tarefa é chamada, o valor de now é 9: ela não executará sua função porque o teste falhará.

A solução para esse problema é calcular a distância em ticks entre now e timeout: se a distância for negativa, o intervalo programado ainda não passou, caso contrário, a tarefa pode executar suas funções. Veremos a seguir como calcular essa distância usando nossos números quatro bits.

Digamos que now seja 7 e timeout também seja 7 (lembre-se que essas variáveis são números inteiros sem sinal):

0111 – 0111 = 0111 + 1001 = 0000

Notar que transformamos a diferença em uma soma com o complemento a 2 de 0111₂. O bit mais significativo da soma (carry out) é desconsiderado em nosso resultado de quatro bits. O resultado é zero, conforme esperado.

Com now 8 e timeout 7:

1000 – 0111 = 1000 + 1001 = 0001

Até aqui, tudo bem. Mas e se now for igual a 7 e timeout for igual a 8?

0111 – 1000 = 0111 + 1000 = 1111

Então, a diferença é igual a +15 (decimal), o resultado positivo poderia ser interpretado como o teste em time_to_do_something()  ter passado quando não deveria.

Agora, observe a Tabela 2 acima. Note que a representação decimal do valor 1111₂ com sinal é -1, que é a diferença entre 7 e 8 (7 – 8 = -1). Ou seja, falta um segundo para now e timeout serem iguais.

Outro exemplo: now é igual a 15 e timeout é igual a 0:

1111 – 0000 = 1111 + 0000 = 1111

Então, parece que, se fizermos a subtração como números inteiros sem sinal e tratarmos o resultado como inteiro com sinal, resolvemos nosso problema. Será que funciona com diferenças maiores do que 1 (decimal)?

Com now igual a 6 e timeout igual a 8:

0110 – 1000 = 0110 + 1000 = 1110

O resultado corresponde a +14 (inteiro sem sinal) e a -2 (inteiro com sinal).

Com now igual a 15 e timeout = 1:

1111 – 0001 = 1111 + 1111 = 1110

O resultado é igual ao caso anterior.

Com now igual a 1 e timeout igual 15:

0001 – 1111 = 0001 + 0001 = 0010

O resultado corresponde a +2, ou seja, 1 ocorre dois segundos depois de 15 em nosso exemplo. Se repetirmos essa aritmética com diferenças maiores, até 7, vai funcionar. Acima de 7, os sinais dos resultados se invertem e essa estratégia não funciona. Vamos falar mais sobre isso na próxima seção.

Implementação real

O conceito exposto na seção anterior foi aplicado em um sistema embarcado baseado em um microcontrolador ARM Cortex M0. O timer systick foi programado para gerar interrupções a uma taxa de 1000 por segundo (portanto, resolução temporal de 1ms) e a única coisa que a rotina de interrupção (ISR) do systick faz é incrementar um contador de 32 bits.

O código a seguir apresenta duas funções, timeout_set() e timeout(), que correspondem, respectivamente, às funções set_next_do_something_time() e time_to_do_something() do pseudocódigo da seção anterior. O primeiro argumento de timeout_set(), tout, é um ponteiro para um objeto timeout_t e o segundo argumento é um número inteiro  sem sinal com o intervalo em milissegundos que é somado ao valor corrente do contador de systicks e armazenado no objeto tout. A função timeout() verifica se o intervalo previamente programado com timeout_set() passou, retornando true se afirmativo. As duas funções usam a função systick_get() para obter o valor corrente do contador de systicks (o nome da função pode variar de acordo com a implementação da infraestrutura de software do processador selecionado).

typedef struct {
    uint32_t tout;
} timeout_t;

bool timeout(timeout_t *tout)
{
    uint32_t t1, t2;
    int32_t d;

    t1 = systick_get();
    t2 = tout->tout;
    d = t_delta(t1, t2);
    return d <= 0;
}

void timeout_set(timeout_t *tout, uint32_t delay)
{
    tout->tout = systick_get() + delay;
}

O código a seguir apresenta uma versão da função t_delta() em linguagem C que não usa as propriedades discutidas na seção anterior (esse código é uma adaptação do código que inicialmente implementou a função t_delta() em uma aplicação real). Em vez disso, a função compara os dois argumentos t1 e t2 para ver qual é o maior deles é o maior e ajusta variáveis auxiliares, uma delas indicando o sinal da comparação, para no final retornar o resultado através de uma conta complexa (a diferença entre as variáveis auxiliares multiplicada pela variável auxiliar de sinal.

int32_t t_delta(uint32_t t1, uint32_t t2)
{
    uint32_t r1, r2, d;
    int32_t s;

    d = t2 - t1;
    if (d < UINT32_MAX / 2) {
        r1 = t1;
        r2 = t2;
        s = 1;
    } else {
        r1 = t2;
        r2 = t1;
        s = -1;
    }
    return s * (int32_t)(r2 - r1);
}

O código a seguir apresenta a versão que usa o conceito anteriormente exposto. Uma linha de código, simples e eficiente.

int32_t t_delta(uint32_t t1, uint32_t t2)
{
    return (int32_t) (t2 - t1);
}

A função mais complexa tem um bug em potencial (fica como exercício ao leitor identificar qual), mas ela funciona corretamente, exatamente igual à segunda versão: ironicamente, apesar de toda complexidade, ela funciona porque a propriedade de aritmética de binários que estamos discutindo foi involuntariamente usada.Um requisito importante dos argumentos t1 e t2 é que a diferença entre eles nunca seja maior do que 2³¹-1 (UINT32_MAX/2), caso contrário, o resultado terá o sinal invertido, quebrando a lógica de timeout(). Entretanto, 2³¹-1 milissegundos correspondem a 24,85 dias: é muito improvável que uma tarefa em um sistema embarcado precise de um atraso dessa ordem ou maior, mas é preciso ter isso em mente para evitar bugs no código que usar essas funções. De fato, uma implementação mais robusta de timeout_set() evita esse problema em potencial limitando o atraso a um valor seguro:

void timeout_set(timeout_t *tout, uint32_t delay)
{
    if (delay > UINT32_MAX / 2)
        delay = UINT32_MAX / 2;
    tout->tout = systick_get() + delay;
}

Conclusão

O artigo apresentou algumas propriedades de números binários e sua aritmética e como essas propriedades pode ser usado para implementar um software de melhor qualidade.

Além da utilidade do código em si, espero que o artigo chame a atenção de programadores de sistema embarcados (especialmente os “deeply embedded”) para a necessidade de conhecer melhor os detalhes da arquitetura que está sendo usada em seus projetos, a fim de implementar firmware de melhor qualidade.

O código-fonte em C pode ser encontrado em https://github.com/cve2022/timeout.

Referências