Побитовая память

Question

Каков наилучший способ реализации побитового memmove? Метод должен принимать дополнительное назначение и исходное смещение битов, и количество должно быть также в битах.

• Я видел, что ARM предоставляет нестандартный _membitmove, который делает именно то, что мне нужно, но я не мог найти его источник.
• Бинт Bind включает в себя isc_bitstring_copy, но это не эффективно
• Я знаю, что стандартная библиотека C не предоставляет такой метод, но я также не смог найти какой-либо сторонний код, обеспечивающий подобный метод.

Answer 1

Вот частичная реализация (не проверено). Есть очевидные улучшения эффективности и удобства использования.

копия n байты из src в dest (не перекрывая src) и сдвинуть биты в dest прямо по bit биты, 0 <= bit <= 7. Это предполагает, что младшие значащие биты находятся справа от байтов

void memcpy_with_bitshift(unsigned char *dest, unsigned char *src, size_t n, int bit)
{
  int i;

  memcpy(dest, src, n);

  for (i = 0; i < n; i++) {
    dest[i] >> bit;
  }

  for (i = 0; i < n; i++) {
    dest[i+1] |= (src[i] << (8 - bit));
  }
}

Некоторые улучшения должны быть сделаны:

• Не перезаписывайте сначала bit биты в начале dest,
• Объединить петли
• Есть способ скопировать количество битов, не делимых на 8
• Исправление для>8 битов в символе

Answer 2

Предполагая, что "лучший" означает "самый простой", вы можете копировать биты один за другим. Концептуально, адрес бита - это объект (структура), который имеет указатель на байт в памяти и индекс бита в байте.

struct pointer_to_bit
{
    uint8_t* p;
    int b;
};

void membitmovebl(
    void *dest,
    const void *src,
    int dest_offset,
    int src_offset,
    size_t nbits)
{
    // Create pointers to bits
    struct pointer_to_bit d = {dest, dest_offset};
    struct pointer_to_bit s = {src, src_offset};

    // Bring the bit offsets to range (0...7)
    d.p += d.b / 8; // replace division by right-shift if bit offset can be negative 
    d.b %= 8; // replace "%=8" by "&=7" if bit offset can be negative
    s.p += s.b / 8;
    s.b %= 8;

    // Determine whether it's OK to loop forward
    if (d.p < s.p || d.p == s.p && d.b <= s.b)
    {
        // Copy bits one by one
        for (size_t i = 0; i < nbits; i++)
        {
            // Read 1 bit
            int bit = (*s.p >> s.b) & 1;

            // Write 1 bit
            *d.p &= ~(1 << d.b);
            *d.p |= bit << d.b;

            // Advance pointers
            if (++s.b == 8)
            {
                s.b = 0;
                ++s.p;
            }
            if (++d.b == 8)
            {
                d.b = 0;
                ++d.p;
            }
        }
    }
    else
    {
        // Copy stuff backwards - essentially the same code but ++ replaced by --
    }
}

Если вы хотите написать версию, оптимизированную для скорости, вам придется копировать байты (или, что лучше, словами), развертывать циклы и обрабатывать ряд особых случаев (memmove делает это; вам придется делать больше, потому что ваша функция более сложная).

PS О, видя, что ты звонишь isc_bitstring_copy неэффективно, вы, вероятно, хотите оптимизировать скорость. Вы можете использовать следующую идею:

Начните копировать биты по отдельности, пока адресат не будет выровнен по байту (d.b == 0). Затем можно легко скопировать 8 битов сразу, немного поигрывая. Делайте это, пока не останется меньше 8 бит для копирования; затем продолжайте копировать биты один за другим.

// Copy 8 bits from s to d and advance pointers
*d.p = *s.p++ >> s.b;
*d.p++ |= *s.p << (8 - s.b);

PPS О, и, увидев ваш комментарий о том, для чего вы собираетесь использовать код, вам не нужно реализовывать все версии (byte/halfword/word, big/little-endian); вам нужен только самый простой - тот, который работает со словами (uint32_t).

Answer 3

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