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

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

Этот код работает, глядя вперед на 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 бит, прежде чем начать сдвиг. Может быть, вы хотите круговой сдвиг, чтобы положить переполненные биты обратно на дно? Может быть, вы хотите перераспределить массив и сделать его больше? Вернуть переполнение вызывающему абоненту? Возвращает логическое значение, если ненулевые данные были переполнены? Вы должны были бы определить, что carry означает для вас.

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

Итак, мы

• обработайте общий случай, выполнив цикл для 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 = number of bits modulo 8, я полагаю, будет M оператора присваивания.

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

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

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

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

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

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

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

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

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

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

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

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