Как перенести массив байтов на 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; 

Джастин написал:
@ 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; 

Answer 2

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

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

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

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

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

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

Answer 3

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

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

Answer 4

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

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

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

Это показало мне закономерность:

• позволить iL быть низким Nybble (половина байт) a[i]
• пусть iH быть высокой Nybble из 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 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; 
} 

Answer 6

Здесь рабочий раствор, используя временные переменные:

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

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

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