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

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

Я приблизился к проблеме

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

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

• позволить 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);
}

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

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

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

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-разрядного сдвига.

Решение Mike's, возможно, быстрее, должное к использованию временных переменных.

Позволяет делают лучшим способом сместиться 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 биты можно вычислить переполнение путем выполнения поразрядного И, и сдвиг с помощью оператора сдвига разряда:

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

Версия на 32 бита... :-) Дескрипторы 1 <= количество <= 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-разрядных блоках над так, как Вы можете и работать над остатком один за другим. Это может немного больше кодировать, но я думаю, что это более изящно в конце.

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

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

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