Como a mudança de uma matriz de bytes por 12 bits

Question

Eu quero mudar o conteúdo de uma matriz de bytes por 12 bits para a esquerda.

Por exemplo, a partir desta matriz do tipo uint8_t shift[10]:

{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x0A, 0xBC}

Eu gostaria de transferi-lo para a esquerda por 12 bits, resultando em:

{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xAB, 0xC0, 0x00}

Answer 1

Hurra para ponteiros!

Este código de obras, olhando para frente com 12 bits de cada byte e copiar os bits próprios para a frente.De 12 bits é a metade inferior (nybble) do próximo byte e a metade superior de 2 bytes de distância.

unsigned char length = 10;
unsigned char data[10] = {0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0A,0xBC};
unsigned char *shift = data;
while (shift < data+(length-2)) {
    *shift = (*(shift+1)&0x0F)<<4 | (*(shift+2)&0xF0)>>4;
    shift++;
}
*(data+length-2) = (*(data+length-1)&0x0F)<<4;
*(data+length-1) = 0x00;

Justin escreveu:
@Mike, sua solução funciona, mas não consigo.

Bem, eu diria que um normal de operação de deslocamento não é só isso (chamado overflow), e só permite que os bits extras cair a direita ou para a esquerda.É simples o suficiente para levar se você quiser - basta salvar a de 12 bits antes de você começar a mudar.Talvez você quer uma circular a tecla shift para colocar o transbordou bits de volta na parte inferior?Talvez você deseja realocar a matriz e torná-lo maior?Devolver o excesso para o chamador?Retornar um valor booleano se diferente de zero de dados foi excedida?Você teria que definir o que levar significa para você.

unsigned char overflow[2];
*overflow = (*data&0xF0)>>4;
*(overflow+1) = (*data&0x0F)<<4 | (*(data+1)&0xF0)>>4;
while (shift < data+(length-2)) {
    /* normal shifting */
}  
/* now would be the time to copy it back if you want to carry it somewhere */
*(data+length-2) = (*(data+length-1)&0x0F)<<4 | (*(overflow)&0x0F);
*(data+length-1) = *(overflow+1);  

/* You could return a 16-bit carry int, 
 * but endian-ness makes that look weird 
 * if you care about the physical layout */
unsigned short carry = *(overflow+1)<<8 | *overflow;

Answer 2

Aqui está a minha solução, mas ainda mais importante, a minha abordagem para a resolução do problema.

Aproximei-me da problema

• desenho as células de memória e o desenho de setas de destino para a fonte.
• fiz uma tabela mostrando o desenho acima.
• rotulagem de cada linha na tabela com a relativa byte de endereço.

Isso me mostrou o padrão:

• deixe iL ser o baixo nybble (meio byte) de a[i]
• deixe iH ser alto nybble de a[i]
• iH = (i+1)L
• iL = (i+2)H

Esse padrão vale para todos os bytes.

A tradução em C, isso significa que:

a[i] = (iH << 4) OR iL
a[i] = ((a[i+1] & 0x0f) << 4) | ((a[i+2] & 0xf0) >> 4)

Nós, agora, fazer três observações:

• desde que realizar as atribuições da esquerda para a direita, nós não precisamos de armazenamento de valores em variáveis temporárias.
• vamos ter um caso especial para a cauda:todos 12 bits no final será zero.
• nós devemos evitar a leitura de memória indefinido passado matriz.desde que nós nunca ler mais a[i+2], isso afeta somente os últimos dois bytes

Então, nós

• lidar com o caso geral pelo loop para N-2 bytes e realizando o cálculo geral acima
• lidar com o próximo até o último byte por ele, pela definição de iH = (i+1)L
• lidar com o último byte definindo-a 0

dado a com duração N, temos:

for (i = 0; i < N - 2; ++i) {
    a[i] = ((a[i+1] & 0x0f) << 4) | ((a[i+2] & 0xf0) >> 4);
}
a[N-2] = (a[N-1) & 0x0f) << 4;
a[N-1] = 0;

E aí você tem que...a matriz é deslocado para a esquerda por 12 bits.Ele pode ser facilmente generalizada para mudar N bits, observando que haverá M instruções de atribuição, onde M = number of bits modulo 8, Eu acredito.

O ciclo poderia ser mais eficiente, em algumas máquinas, através da tradução para ponteiros

for (p = a, p2=a+N-2; p != p2; ++p) {
    *p = ((*(p+1) & 0x0f) << 4) | (((*(p+2) & 0xf0) >> 4);
}

e usando o maior inteiro tipo de dados suportado pela CPU.

(Eu apenas digitei isso, então agora seria uma boa hora para alguém revisar o código, especialmente desde que o bit girando é muito fácil de errar.)

Answer 3

Permite que o torna o melhor caminho para a mudança N bits na matriz de números inteiros de 8 bits.

N            - Total number of bits to shift
F = (N / 8) - Full 8 bit integers shifted
R = (N % 8) - Remaining bits that need to be shifted

Eu acho que a partir daqui você teria que encontrar a melhor maneira de fazer uso deste dados para mover ao redor ints em uma matriz.Genérico algoritmos seria aplicar o total de número inteiro turnos, iniciando a partir da direita da matriz e movendo-se cada inteiro F índices.Zero preencher o recém-espaços vazios.Então, finalmente, realizar uma R deslocamento de bit em todos os índices, novamente começando pelo direito.

No caso de mudança 0xBC por R bits, você pode calcular o estouro fazendo um bit a bit, E a mudança usando o bitshift operador:

// 0xAB shifted 4 bits is:
(0xAB & 0x0F) >> 4   // is the overflow      (0x0A)
0xAB << 4            // is the shifted value (0xB0)

Tenha em mente que os 4 bits é apenas uma simples máscara:0x0F ou apenas 0b00001111.Isso é fácil de calcular, construir dinamicamente, ou você pode até mesmo usar uma estático simples de tabela de pesquisa.

Espero que seja genérico o suficiente.Eu não sou muito bom com C/C++ e por isso talvez alguém possa limpar a minha sintaxe ou para ser mais específico.

Bônus:Se você está esperto com o seu C você pode ser capaz de fudge vários índices de uma matriz em um único 16, 32, ou mesmo 64 bits inteiro e realizar as mudanças.Mas que é prabably não é muito portátil e eu gostaria de recomendar contra isso.Apenas uma possível otimização.

Answer 4

Aqui uma solução de trabalho, usando variáveis temporárias:

void shift_4bits_left(uint8_t* array, uint16_t size)
{
    int i;
    uint8_t shifted = 0x00;    
    uint8_t overflow = (0xF0 & array[0]) >> 4;

    for (i = (size - 1); i >= 0; i--)
    {
        shifted = (array[i] << 4) | overflow;
        overflow = (0xF0 & array[i]) >> 4;
        array[i] = shifted;
    }
}

Chamar esta função 3 vezes para um 12-deslocamento de bit.

Mike solução talvez mais rápido, devido ao uso de variáveis temporárias.

Answer 5

A versão de 32 bits...:-) Alças de 1 <= contagem <= num_words

#include <stdio.h>

unsigned int array[] = {0x12345678,0x9abcdef0,0x12345678,0x9abcdef0,0x66666666};

int main(void) {
  int count;
  unsigned int *from, *to;
  from = &array[0];
  to = &array[0];
  count = 5;

  while (count-- > 1) {
    *to++ = (*from<<12) | ((*++from>>20)&0xfff);
  };
  *to = (*from<<12);

  printf("%x\n", array[0]);
  printf("%x\n", array[1]);
  printf("%x\n", array[2]);
  printf("%x\n", array[3]);
  printf("%x\n", array[4]);

  return 0;
}

Answer 6

@José, observe que as variáveis são 8 bits de largura, enquanto a mudança é de 12 bits de largura.A sua solução só funciona para N <= tamanho variável.

Se você pode assumir sua matriz é um múltiplo de 4, você pode lançar a matriz em uma matriz de uint64_t e, em seguida, trabalhar sobre isso.Se não for um múltiplo de 4, você pode trabalhar em 64-bit em pedaços tanto quanto você pode e trabalho no restante um por um.Este pode ser um pouco mais de codificação, mas eu acho que é mais elegante do que no final.

Answer 7

Há um par de borda-casos, que fazem deste um puro problema:

• a matriz de entrada pode ser vazio
• o último e o penúltimo bits precisa ser tratado de forma especial, porque eles têm zero bits deslocados para eles

Aqui está uma solução simples que faz um loop sobre a matriz de copiar os de ordem inferior nibble do próximo byte de alta ordem nibble, e os de ordem elevada nibble de next-next (+2) byte para baixo, a fim de nibble.Para salvar desreferência de look-ahead ponteiro duas vezes, ele mantém um elemento de dois buffer com o "último" e "próximo" bytes:

void shl12(uint8_t *v, size_t length) {
  if (length == 0) {
    return; // nothing to do
  }

  if (length > 1) {
    uint8_t last_byte, next_byte;
    next_byte = *(v + 1);

    for (size_t i = 0; i + 2 < length; i++, v++) {
      last_byte = next_byte;
      next_byte = *(v + 2);
      *v = ((last_byte & 0x0f) << 4) | (((next_byte) & 0xf0) >> 4);
    }

    // the next-to-last byte is half-empty
    *(v++) = (next_byte & 0x0f) << 4;
  }

  // the last byte is always empty
  *v = 0;
}

Considere o limite casos, que ativam sucessivamente mais peças da função:

• Quando length é zero, podemos socorrer, sem tocar de memória.
• Quando length é um, vamos definir o único elemento a zero.
• Quando length é dois, vamos definir a ordem de alta nibble do primeiro byte de ordem inferior nibble do segundo byte (ou seja, bits 12-16), e o segundo byte zero.Nós não ativar o loop.
• Quando length é maior do que dois, que atingiu o loop, baralhar os bytes entre os dois elementos do buffer.

Se a eficiência é o seu objetivo, a resposta provavelmente depende em grande parte da sua máquina de arquitetura.Normalmente, deve-se manter a dois elementos de buffer, mas lidar com uma máquina de palavra (32/64 bit número inteiro não assinado) a um tempo.Se você está mudando um monte de dados que vai valer a pena tratar os primeiros bytes como um caso especial, de modo que você pode obter a sua máquina palavra ponteiros palavra-alinhados.A maioria das CPUs, memória de acesso de forma mais eficiente se os acessos caem na máquina, os limites da palavra.Claro, os bytes à direita tem que ser tratada de forma especial também para que você não toque a memória após o final da matriz.