Как перенести массив байтов на 12 бит

Ответ 1

Ура для указателей!

Этот код работает, просматривая 12 бит для каждого байта и копируя правильные биты вперед. 12 бит - нижняя половина (nybble) следующего байта и верхняя половина из 2 байтов.

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;

Джастин написал:
@Mike, ваше решение работает, но не несет.

Хорошо, я бы сказал, что нормальная операция сдвига делает только это (называемое переполнением) и просто позволяет лишним битам падать вправо или влево. Это достаточно просто, чтобы носить, если вы хотели - просто сохраните 12 бит, прежде чем начинать смены. Может быть, вам нужен круговой сдвиг, чтобы положить переполненные биты назад? Возможно, вы хотите перераспределить массив и сделать его более крупным? Вернуть переполнение для вызывающего? Вернуть логическое значение, если ненулевые данные были переполнены? Вам нужно будет определить, какие средства переноса вам доступны.

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;

Ответ 2

Здесь мое решение, но что еще более важно, мой подход к решению проблемы.

Я подошел к проблеме с помощью

• рисование ячеек памяти и рисование стрелок от адресата до источника.
• сделал таблицу, изображающую приведенный выше рисунок.
• маркировка каждой строки в таблице с относительным байтовым адресом.

Это показало мне шаблон:

• let iL - низкий уровень (половина байта) a[i]
• пусть iH будет высокий уровень шума a[i]
• iH = (i+1)L
• iL = (i+2)H

Этот шаблон сохраняется для всех байтов.

Перейдя на C, это означает:

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

Теперь сделаем еще три наблюдения:

• поскольку мы выполняем задания слева направо, нам не нужно хранить какие-либо значения во временных переменных.
• у нас будет специальный случай для хвоста: все 12 bits в конце будут равны нулю.
• мы должны избегать чтения undefined памяти за массивом. поскольку мы никогда не читаем больше, чем a[i+2], это влияет только на последние два байта

Итак, мы

• обрабатывает общий случай путем циклирования для N-2 bytes и выполнения общего вычисления выше
• обработайте его последним байтом, установив iH = (i+1)L
• обработать последний байт, установив его на 0

при заданном a с длиной N, получим:

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;

И там у вас есть... массив смещается влево на 12 bits. Его можно было бы легко обобщить на перенос N bits, отметив, что будут предложения M присваивания, где M = number of bits modulo 8, я считаю.

Цикл может быть более эффективным на некоторых машинах, переведя на указатели

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

и используя самый большой целочисленный тип данных, поддерживаемый ЦП.

(Я только что набрал это, так что теперь было бы хорошим временем для кого-то, чтобы просмотреть код, тем более, что бит twiddling, как известно, легко ошибиться.)

Ответ 3

Позволяет наилучшим образом сдвинуть бит N в массив из 8 битовых целых чисел.

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

Я предполагаю, что отсюда вам нужно будет найти наиболее оптимальный способ использования этих данных для перемещения по ints в массиве. Общие алгоритмы состоят в том, чтобы применить полные целые сдвиги, начиная с правого массива и перемещая индексы целых чисел F. Zero заполнить новые пустые места. Затем, наконец, выполните сдвиг бит R по всем индексам, снова начиная с правого.

В случае сдвига 0xBC на R бит вы можете рассчитать переполнение, выполнив побитовое И, а сдвиг с помощью оператора битовой смены:

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

Имейте в виду, что 4 бита - это просто маска: 0x0F или всего 0b00001111. Это легко вычислить, динамически построить, или вы даже можете использовать простую статическую таблицу поиска.

Я надеюсь, что это достаточно общий. Я не очень хорошо разбираюсь в C/С++, поэтому, возможно, кто-то может очистить мой синтаксис или быть более конкретным.

Бонус: если вы лукавый со своим C, вы можете переманивать несколько индексов массивов в одно целое число 16, 32 или даже 64 бит и выполнять смены. Но это возможно не очень портативно, и я бы рекомендовал против этого. Просто возможная оптимизация.

Ответ 4

Здесь рабочее решение, использующее временные переменные:

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;
    }
}

Вызов этой функции 3 раза для 12-битного сдвига.

Решение Майка может быть быстрее, из-за использования временных переменных.

Ответ 5

32-разрядная версия...:-) Ручки 1 <= count <= 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;
}

Ответ 6

@Joseph, обратите внимание, что переменные имеют ширину 8 бит, а сдвиг - 12 бит. Ваше решение работает только для N <= переменной размер.

Если вы можете предположить, что ваш массив кратен 4, вы можете передать массив в массив uint64_t, а затем работать над этим. Если он не кратен 4, вы можете работать в 64-битных кусках столько, сколько сможете, и работать над остатком один за другим. Это может быть немного больше кодирования, но я думаю, что это более элегантно в конце.

Ответ 7

Есть несколько краев, которые делают эту проблему чистой:

• входной массив может быть пустым
• последний и следующий-последние бит нужно обрабатывать специально, потому что они имеют нулевые биты, смещенные в них

Здесь простое решение, которое петляет над массивом, копируя низкоуровневый полубайт следующего байта в его высокий порядок полубайта, а верхний кусок следующего следующего (+2) байта в его младший порядок клев. Чтобы сохранить разыменование указателя на перспективу дважды, он поддерживает двухэлементный буфер с "последним" и "следующим" байтами:

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;
}

Рассмотрим граничные случаи, которые последовательно активируют больше частей функции:

• Когда length равно нулю, мы выходим, не касаясь памяти.
• Когда length равно единице, мы устанавливаем один и тот же элемент равным нулю.
• Когда length равно двум, мы устанавливаем верхний кусок первого байта на младший кусок второго байта (то есть биты 12-16), а второй байт равен нулю. Мы не активируем цикл.
• Когда length больше двух, мы попадаем в цикл, перетасовывая байты в двухэлементном буфере.

Если эффективность является вашей целью, ответ, вероятно, во многом зависит от вашей машинной архитектуры. Обычно вы должны поддерживать двухэлементный буфер, но одновременно обрабатывать машинное слово (32/64 бит без знака). Если вы перекладываете большое количество данных, будет полезно обрабатывать первые несколько байтов как особый случай, чтобы вы могли вывести указатели машинных слов по словам. Большинство процессоров получают доступ к памяти более эффективно, если доступ падает на границы машинного слова. Конечно, задние байты должны обрабатываться специально, чтобы вы не касались памяти за концом массива.