Как сдвинуть массив байтов на 12 бит

Question

Я хочу сместить содержимое массива байтов на 12 бит влево.

Например, начиная с этого массива типа uint8_t shift[10]:

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

Я бы хотел сдвинуть его влево на 12 битов, в результате чего:

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

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

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

Ну, я бы сказал, что обычная операция сдвига делает именно это (называется переполнением) и просто позволяет лишним битам падать вправо или влево. Это достаточно просто носить с собой, если вы хотите - просто сохраните 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;

Answer 2

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

Я подошел к проблеме

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

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

• пусть 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 в конце будут равны нулю.
• мы должны избегать чтения неопределенной памяти за массивом. поскольку мы никогда не читаем больше 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);
}

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

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

Answer 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

Полагаю, отсюда вам нужно было бы найти наиболее оптимальный способ использования этих данных для перемещения по целым числам в массиве. Универсальные алгоритмы должны были бы применять полные целочисленные сдвиги, начиная с правой части массива и перемещая каждое целое число F индексов. Ноль заполнить недавно пустые места. Затем, наконец, выполните 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 ++, так что, возможно, кто-то может очистить мой синтаксис или быть более конкретным.

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

Answer 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-битного сдвига.

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

Answer 5

32-битная версия ... :-) Обрабатывает 1 <= count <= num_words </p>

#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

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

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

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

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 битное целое число без знака) одновременно. Если вы перемещаете много данных, стоит рассмотреть первые несколько байтов в качестве особого случая, чтобы вы могли получить указатели слов в своей машине со слов. Большинство ЦП обращаются к памяти более эффективно, если доступы попадают за границы машинных слов. Конечно, завершающие байты также должны обрабатываться специально, чтобы вы не касались памяти за концом массива.

Answer 7

@ Джозеф, обратите внимание, что переменные имеют ширину 8 бит, а смещение - 12 бит. Ваше решение работает только для N <= переменный размер. </p>

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