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

StackOverflow https://stackoverflow.com/questions/29437

  •  09-06-2019
  •  | 
  •  

Вопрос

Я хочу сдвинуть содержимое массива байтов на 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}
Это было полезно?

Решение

Ура указателям!

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

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;

Другие советы

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

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

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

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

  • позволять 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], это влияет только на последние два байта

Итак, мы

  • обрабатывать общий случай, используя цикл for 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);
}

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

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

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

Вот рабочее решение с использованием временных переменных:

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

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top