Deslocando uma string de bits

Eu falei, no post anterior, que precisei usar rotações para uma rotina que estou fazendo para o futuro (em breve, espero) artigo sobre BitBlt (Bit Block Transfers). A rotina será útil em manipulações de mapas de bits (ou em “superfícies” que tenham 1 bit por pixel – 1 bpp). Ficará mais claro quando chegarmos lá. Aqui eu quero apresentar a rotina de deslocamento de uma string de bits (não de “bytes”!), onde um conjunto de bits “no meio” de um conjunto de bytes, precisa ser alinhada com o bit 0 (ou a coordenada x=0)… O diagrama abaixo mostra como funciona:

Aqui temos uma string de 14 bits (que marquei com bolinhas vermelhas [1] e pretas [0]) que preciso deslocar 7 bits para a  “esquerda”. Acontece que todos os bits precisam sofrer esse deslocamento… Coloquei “esquerda” entre aspas porque, na realidade, o deslocamento será feito para a direita (node que representei o bit 0 à esquerda para coincidir com uma coordenada x, de uma “pixel”. Sabemos que o LSB, na verdade, encontra-se à direita…

A técnica é simples: O primeiro byte da string de bits é deslocada em 7 bits para a direita e os demais bytes são rotacionados em 7 bits, também para a direita… Cada byte central sofre dois mascaramentos para isolar os bits que serão copiados para o byte anterior e mantidos no próximo byte. Como o deslocamento foi de 7 bits, isso significa que só precisamos dos 7 bits superiores do 2º byte (no exemplo) e do primeiro bit, todos os demais bits são zerados para que, ao fazer um OR, eles sejam misturados corretamente. Isso é feito com todos os pares de bytes (o 1º com o 2º, o 2º com o 3º, etc… até chegamos ao byte n-1 e n).

Observe que, no final das contas, teremos apenas 2 bytes (porque temos apenas 13 bits que nos interessam) ou, se você quiser manter os 24 bits iniciais, os bits superiores deverão ser zerados! Claro que temos como saber, de antemão, que podemos alocar os bits deslocados em um número determinado de bytes: 14 bits é maior que 8 e menor que 17, então só pode caber em 2 bytes.

Não parece, mas a rotina é muito simples. Deixo pra você implementá-la. Só tome cuidado com uma coisa: zerar os bits superiores que não nos interessam! :)

“Ahhh! Eu sei de um jeito mais rápido, Fred!”

É mesmo… também sei! Afinal, mesmo que você esteja trabalhando no modo i386 (32 bits), pode também usar MMX (64 bits), SSE (128 bits), AVX (256 bits) ou, nos processadores mais modernos, AVX-512 (512 bits) de uma vez só, né? Perfeito! Mas imagine que tenha que manipular um bit string de 1920 bits (Full HD), ou 3840 (4k). A técnica acima, ainda assim, pode ser útil!

Anúncios