Há algum tempo atrás, escrevi aqui algumas curiosidades sobre Ponto Flutuante, bits afins. Semana passada, tive que corrigir alguns pequenos bugs no meu código de leitura de buffers de bytes, e descobri outra curiosidade com operação de bits em Java. Resolvi compartilhar com vocês, apesar de saber que a grande maioria dos programadores hoje em dia considera este tipo de conhecimento inútil, já que raramente se trabalha diretamente com bits. Verdade, raramente. Mas se aconteceu comigo, pode acontecer com qualquer um. E conhecimento nunca é demais.

Vamos lá!

Em Java, todo tipo primitivo de dados (byte, short, int, long, float e double) é sinalizado, o que significa que seus valores podem ser positivos ou negativos. Um byte pode ter valor de -128 a 127, um short varia de -32768 a 32767, e assim por diante.

Já em C, tipos primitivos podem ser sinalizados ou não sinalizados. Um byte sinalizado em C pode assumir os mesmos valores que um byte em Java, mas um byte não sinalizado pode assumir valores entre 0 e 255.

Assim sendo, quando se escreve um programa em Java que deve ler dados gerados por um programa em C, é importante saber se estes dados são sinalizados ou não. O mais divertido disso tudo é que não existe forma de saber isso apenas analizando os dados, porque eles são idênticos: um byte sinalizado continua tendo 8bits e podendo armazenar 255 valores.

Neste ponto me parece interessante explicar como um número negativo é armazenado em um tipo básico. Primeiro conceito: em tipos sinalizados, o bit mais a esquerda indica o sinal: 0 positivo, 1 negativo. Mas para se obter o inverso de um número, não basta apenas mexer no bit mais a esquerda. É necessário usar um segundo conceito: complemento de 2! Para se obter o complemento de 2 de um número, basta inverter os bits e somar 1. Por exemplo, se N = 7 = 00000111, o seu complemento de 2 será 11111000+1 = 11111001. Para se obter a representação binária de um número negativo, basta gerar o complemento de 2 da representação binária do seu valor positivo! Assim sendo, -7 em binário é representado por 11111001.

Este mecanismo foi criado para facilitar as operações aritméticas nos processadores, pois elimina a necessidade de um circuito específico para subtração: o processador precisa calcular apenas o complemento de 2 do subtraendo, e efetuar a soma. Por exemplo

7 - 2 = 0111 - 0010 = 0111 + 1110 = 0101 .

Muito bem, voltemos portanto ao problema original…

Quando passamos um valor sinalizado de C para Java, não há problemas. Se eu leio um byte gerado pelo programa em C em um byte em Java, ou em um short (16 bits), ou em um int (32 bits), ou em um long (64 bits), o resultado será exatamente o esperado. Agora, se queremos ler um valor não sinalizado gerado por um código em C em um programa Java, é necessário escrever os bits em um tipo primitivo de tamanho maior.

Para escrever bits em um tipo primitivo, existem dois mecanismos: ou fazemos um AND binário com o endereço de destino contendo somente bits com valor 1, ou fazemos um OR binário com o endereço de destino contendo apenas bits com valor 0.

00000000 | 0110 = 00000110
11111111111 & 0110 =11110110

Por exemplo, supondo byte 11111001. Já vimos anteriormente que esta sequência de bits corresponde ao valor -7, mas também correspondeao valor 249 em um byte não sinalizado. Se quisermos obter o valor 249 em Java, teremos que gerar uma variável igual ou maior que um short.

E agora vem a curiosidade que motivou este texto (sim, todo o resto era apenas preparação, espero que tenha sido proveitoso) .

Pelo o que eu disse acima, para gerar o short com o valor 249, ambos os códigos abaixo seriam equivalentes:

short s1 = 0×0000 | 0xF9

ou

short s2 = 0×00FF & 0xF9

correto?

Errado!

Se eu mandar imprimir s2, o resultado será 249, mas se eu mandar imprimir s1, verei que o resultado será -7. Porque???

Simples: antes de efetuar uma operação binária, a JVM efetua um casting implícito de todas as variáveis para int. Como Java não entende tipo não sinalizado, ele faz casting do nosso byte levando em conta o valor -7, que em um int de 32 bits fica sendo 0xFFFFFFF9. O short 0×0000 passa a ser 0×00000000, e o short 0×00FF passa a ser 0×000000FF. Assim sendo, as operações descritas acima na verdade são:

short s1 = 0×00000000 | 0xFFFFFFF9 = 0xFFFFFFF9 = -7

e

short s2 = 0×000000FF & 0xFFFFFFF9 = 0×000000F9 = 249

——————————————————-

Adendo do autor:

Para aqueles que tenham dificuldades de entender notação hexadecimal, e como converter isso para binário e vice-ver, eis uma dica:  um símbolo em hexa pode assumir 16 valores (0,1,2,3,4,5,6,7,8,9,A,B,C,D,F,). Sendo assim, cada símbolo em hexa corresponde exatamente ao valor de 4 bits, e portanto são necessários dois símbolos em hexadecimal para descrever um byte.

Nas últimas semanas tenho trabalhado em um projeto de integração entre um sistema em C e um sistema em Java: o sistema original, legado, é completamente em C, e a equipe na qual eu trabalho está reescrevendo algumas partes em Java, e eu tenho que fazer o sistema antigo conversar com o novo. O sistema em C utiliza um sistema de comunicação interna que consiste basicamente em serializar bytes e mandar via UDP. Isso torna o processo bem rápido e eficiente, mas torna a comunicação entre plataformas bem complicada, por causa de problemas como alinhamento de bytes, padding, little endian, big endian, ponto flutuante, e por aí vai.

Por isso tive que rever vários conceitos, além de relembrar várias coisas em C. Não trabalhava com C desde 2002, quando participei do projeto AURORA, organizado pelo CenPRA. O objetivo do Aurora era de construir um dirigível capaz de voar sozinho, usando dados de sensores, GPS e de câmeras de vídeo. Minha missão dentro do projeto foi de desenvolver a infraestrutura para captação de imagens através de barramento IEEE 1394 (firewire), processamento e extração de certos parâmetros em tempo real e envio de alguns frames para uma estação de controle em terra. Foi C na veia, e ainda tive que estudar IEEE1394, drivers para linux, formatos de vídeo, processamento de imagens, envio de pacotes via UDP, e muitos outros conceitos básicos. Me diverti muito nesta época.

Voltando ao projeto atual, uma das tarefas necessárias era de receber um fluxo de bytes e extrair informações seguindo um descritor da mensagem. Como meus campos de informação dentro do fluxo de bytes tinham posições e tamanhos pouco convencionais (12 bits, 3 bits começando no bit 4 do byte 2, e por aí vai), não consegui encontrar nenhuma lib que resolvesse meu problema de forma adequada (em particular, nenhuma lib de extração de dados trabalha corretamente com campos de bits). Por isso resolvi extrair os bits na mão, escrevendo algumas operações binárias: o resultado final ficou bastante bom e conciso. Mas várias pessoas me perguntaram porque eu fiz a loucura de implementar isso na mão. Segundo eles, deveria ter pesquisado mais, porque provavelmente algum engenheiro da Sun havia feito algo melhor e mais robusto.

Concordo que seja possível que eu não tenha procurado o suficiente. Mas escrever algumas poucas linhas de operações binárias não me parece ser tarefa do outro mundo. Talvez eu seja arrogante o suficiente para me achar melhor do que os engenheiros da Sun (ou pelo menos tão competente quanto). Mas talvez também os programadores estejam criando tabus em relação a alguns tópicos de computação, chamados por muitos de baixarias.

A evolução na computação se faz por meio de criação de camadas de abstração, que nos permitem trabalhar sem nos preocuparmos com certos problemas. Hoje em dia, quem programa em Java, Python, Ruby e outras linguagens similares não se preocupa mais em gerenciar memória, em perder ponteiros. ORMs permitem que a base de dados seja vista como um conjunto de objetos. RMI e RPC enviam objetos e estruturas de dados de uma máquina para a outra. E acreditem: eu adoro estas abstrações! Adoro trabalhar com dicionários, listas e tuplas em Python, adoro não ter que gerenciar ponteiros em Java. Mas duas ressalvas precisam ser feitas.

A primeira já foi feita pelo Joel, no artigo The Law of Leaky Abstractions: estas abstrações são ótimas, mas não são perfeitas e muitas vezes falham. E quando falham, é preciso conhecer os fundamentos daquilo que está por baixo. Quando sistemas de ORM retornam resultados esdrúxulos, é preciso entender que o sistema subjacente não trabalha com objetos, mas com tabelas. Quando struts não da conta de tratar uma requisição, é preciso entender que no fundo no fundo, um form é uma string de requisição HTTP. Pode parecer bobo, mas é incrível perceber a quantidade de programadores que simplesmente não entendem o que se passa por debaixo do pano. Tudo é mágico.

A segunda ressalva é o ponto que eu quero ressaltar neste texto: estas camadas de abstração criam tabus. Hoje as pessoas tem receio de escovar bits, ou processar um UDP na mão. Muito em breve, SQL será algo de outro mundo, uma vez que Hibernate, RoR e Django permitem que objetos sejam criados de forma direta. HTTP e CGI já são conceitos do passado: hoje temos forms, event handlers e componentes. Para tudo, se busca um framework, uma lib. Para tudo, se acha que o que é feito pelos engenheiros da Sun é melhor. Eu tive esta nítida impressão conversando com um colega de trabalho que já tem muiiiiitos anos de estrada. Ele tem uma boa experiência em programação de microcontroladores, e ele é da época em que C era novidade no mercado. E segundo ele, mexer com bits era algo trivial e corriqueiro naquela época.

Que fique bem claro: eu adoro não ter que mexer nestas coisas. Mas sei que problemas deste tipo podem aparecer na nossa frente de vez em quando, e quando aparecerem nós temos que poder resolve-los. E para isso, não podemos ter medo de passar por cima das abstrações. Por isso, eu defendo que todo programador deveria mexer em algum projetinho em C de tempos em tempos (um ou dois meses a cada 5 anos por exemplo). Isso já seria suficiente para lembrar que o mundo computacional não é tão alto nível quando gostaríamos. E o prazer de voltar para nossas caixas pretas é incomensurável.

Nos últimos tempos tenho trabalhado na integração de dois sistemas, um em C (legado) e um e Java. A integração consiste em em ler mensagens enviadas pelo programa em C através de um socket e gerar objetos e ações correspondentes do lado Java. Nada de muito excepcional, é um cenário bastante comum. O divertido da coisa é que eu estou tendo que descer bem baixo na manipulação dos bits, e estou tendo que relembrar vários conceitos que aprendemos algum dia na faculdade e que consideramos como sendo inúteis pro resto da nossa vida, já que boa parte é resolvida por alguma API.

Ontem acabei de me deparando com um probleminha interessante, e que me fez relembrar o conceito de representação de números em ponto flutuante. Vou tentar explicar aqui a parte teórica da coisa, e no final apresento o problema e a solução. Se você não gosta de teoria, pode pular pro último parágrafo.

Muito bem. Suponha que você tenha o seguinte código em Java:

int i = 15;
float f = (float)i;
System.out.println(i+”, “+f);

O resultado da impressão será 15, 15.0.

Até aí nenhum novidade. O casting faz com que o número passe a ser tratado como ponto flutuante, mas mantém o valor inteiro. OK. Alguém aí já parou pra olhar como estes números são representados binariamente, por baixo do pano?


15 inteiro = 00000000 00000000 00000000 00001111
15 float = 01000001 01110000 00000000 00000000


Para alguns talvez isto não seja novidade, e para outros uma descoberta. E para alguns como eu era algo que eu já imaginava, mas nunca olhei a fundo.

No caso do 15 inteiro, nenhuma novidade: 15 = 2^3 + 2^2 + 2^1 + 2^0 = 8 + 4 + 2 + 1 = 15.

No caso do 15 float, é necessário entendermos o padrão que rege a representação dos números de ponto flutuante: IEEE 754. Resumindo: segundo o padrão, um número de ponto flutuante pode ser representado com precisão simples (32 bits, float em Java) ou precisão dupla (64 bits, double em Java). A IEEE define apenas a precisão de 32 bits como obrigatória, as outras sendo opcionais.

No caso da representação simples, o layout dos bits é o seguinte: o primeiro bit representa o sinal (0 positivo, 1 negativo), os 8 bits subsequentes representam o expoente e o restante (23 bits), a parte fracionária (chamada de mantissa). O desenho abaixo, obtido da wikipedia, ilustra este layout:

O expoente pode mapear valores entre -127 a 127 (no caso de um expoente de 8 bits). Para evitar o uso de bit de sinal, que pode dificultar certas operações, foi definido que o valor armazenado seria e + 127, onde e é o real valor a ser considerado.

A mantissa armazena um valor fracionario, e pode ser traduzido como 1.<padão de bits da mantissa>. Se a nossa mantissa for 1000000 00000000 00000000, é equivalente a 1.1000000 00000000 00000000. Aqui vale ressaltar mais um ponto: estamos considerando números binários, portanto os valores após às virgulas podem ser considerados como potências negativas de 2 (assim como números fracionários na base 10). No caso do exemplo, 1.1 é equivalente à 1 + 2^(-1) = 1 + 0.5 = 1.5.

Tendo estes elementos em mão é fácil calcular o resultado final: f = (sinal) * 2^(e -127) * 1.<mantissa>.

No caso do número 15, vamos ver como fica a coisa:

• sinal = 0 = +1
• expoente = 10000010 = 130. Portanto e = 130 - 127 = 3.
• mantissa = 1110000 00000000 00000000, portanto 1.111 = 1 + 2^(-1) + 2^(-2) + 2^(-3)  = 15/8
• Resultado = +1 * 2^3 * 15/8 = 8 * 15/8 = 15.

Muito bem. Mas a pergunta: porquê eu estou me preocupando com isso???

Simples: eu tenho que ler um fluxo de bytes, seguindo um descritor de mensagem, e reconstituir certos tipos de dados (ints, booleanos, campos de bits, etc…). Como eu tenho que ler e extrair alguns campos de bits perdidos no meio de bytes, resolvi implementar uma estratégia de baixo nível, lendo byte a byte e concatenando quando necessário em tipos de dados maiores. Além disso, estou usando como repositório temporário destes bits uma variável do tipo long, que possui 64bits, o que é mais do que necessário para armazenar qualquer dado que eu receba. A operação é simples: recebo um byte, e “colo” ele no long usando operações SHIFT e OR binários.

Agora suponha que o programa em C me mande o número 15 em ponto flutuante de 32 bits, como definido acima, e que eu armazene os bits recebidos em um long. Se ao final da leitura, eu pegar a variável temporária  e fizer um casting para float direto, a JVM vai pegar o valor do long (no caso 1097859072) e simplesmente converter para o padrão IEEE 754 correspondente, o que me resultaria num float com valor 1097859072.0, o que definitivamente não me interessa. O que eu preciso é de uma função que receba um long ou um int, seja capaz de olhar para o dado apenas como um repositório de bits e gere o float o double correspondente. No caso, os métodos Float.intBitsToFloat(int) e Double.longBitsToDouble(lont).

PS: Quem estiver interessado em ter uma leitura mais teórica e aprofundada sobre o tema pode ler o artigo What Every Computer Scientist Should Know About Floating-Point Arithmetic.

Aproveitando os dois últimos posts sobre expressões regulares, Regexp Nossa de Cada Dia! (de minha autoria) e Usando Regexp (do Leo), encontrei o link do artigo “How Regexes Work“, que explica de forma bem clara o funcionamento de um algoritmo de regexp. Bom para saciar a curiosidade daqueles que gostam de saber como as coisas funcionam.

Hoje descobri este artigo do Joel Spolsky sobre codificação de caracteres e UNICODE.

Bem didático e interessante, sobretudo quando se desenvolve interfaces pra Web.