Estoy tratando de copiar n bits desde cualquier posición de una matriz de uint8_ts en un solo entero de 64 bits. Aquí hay una solución de trabajo que puede copiar una cantidad arbitraria de bits en un entero de 64 bits que comienza en el comienzo de la matriz, pero quiero poder comenzar en cualquier posición de la matriz.

Por ejemplo, podría querer copiar los bits 2 a 11 de la matriz: {7, 128, 7}

En binario sería: 00000111 1000000 00000111

Y quiero un número entero con valor: 0001111000

std::uint64_t key_reg(std::uint8_t* bytes, std::size_t n)
{
  std::uint64_t reg = 0;
  // The amount of bits that fit into an entire element of an array
  // ex, if I'm copying 17 bits, even_bytes == 2
  std::size_t even_bytes = (n - (n % 8)) / 8;
  // what's left over after the even bytes
  // in this case, remainder == 1
  std::size_t remainder = n - even_bytes * 8;

  // copy each byte into the integer
  for(std::size_t i = 0; i < even_bytes; ++i)
    if(remainder)
      reg |= (std::uint64_t)bytes[i] << (8 * (even_bytes - i));
    else
      reg |= (std::uint64_t)bytes[i] << (8 * (even_bytes - i - 1));

  // if there is an uneven number of bits, copy them in
  if(remainder) 
    reg |= (std::uint64_t)bytes[even_bytes];

  return reg;
}

¿Tienes alguna idea de cómo implementar

std::uint64_t key_reg(std::uint8_t* bytes, std::size_t pos, std::size_t n);

No pensé que alguien respondería tan rápido, así que aquí había una solución que se me ocurrió con el mismo estilo. Encontré esta función de bitfieldmask en stackoverflow, pero no puedo encontrar la pregunta para dar crédito al autor.

template<typename R>
static constexpr R bitfieldmask(unsigned int const a, unsigned int const b)
{
  return ((static_cast<R>(-1) >> (((sizeof(R) * CHAR_BIT) - 1) - (b)))
      & ~((1 << (a)) - 1));  
}

std::uint64_t key_reg(std::uint8_t* bytes, std::size_t pos, std::size_t n)
{
  std::uint64_t reg = 0;
  std::size_t starting_byte = (pos < 8) ? 0 : ((pos - (pos % 8)) / 8);
  std::size_t even_bytes = (n - (n % 8)) / 8;
  std::size_t remainder = n - even_bytes * 8;

  for(std::size_t i = 0; i < even_bytes; ++i)
    if(remainder)
      reg |= (std::uint64_t)bytes[starting_byte + i] << (8 * (even_bytes - i));
    else
      reg |= (std::uint64_t)bytes[starting_byte + i] << (8 * (even_bytes - i - 1));

  if(remainder) 
    reg |= (std::uint64_t)bytes[even_bytes];

  // mask out anything before the first bit
  if(pos % 8 != 0) {
    std::size_t a = n - pos;
    std::size_t b = n;
    auto mask = bitfieldmask<std::uint64_t>(a, b);

    reg = (reg & ~mask);
  }

  return reg;
}
1
Sam G 18 ene. 2018 a las 00:28

3 respuestas

La mejor respuesta

Su enfoque básico se ve bien. Para manejar las compensaciones de bits que no son múltiplos de 8, solo necesita leer primero en un solo byte parcial y luego continuar con el resto:

uint64_t key_reg(const uint8_t* bytes, size_t pos, size_t n) {
    const uint8_t* ptr = bytes + pos / 8;
    uint64_t result = 0;

    if (pos % 8 > 0) {
        /* read the first partial byte, masking off unwanted bits */
        result = *(ptr++) & (0xFF >> (pos % 8));

        if (n <= 8 - pos % 8) {
            /* we need no more bits; shift off any excess and return early */
            return result >> (8 - pos % 8 - n);
        } else {
            /* reduce the requested bit count by the number we got from this byte */
            n -= 8 - pos % 8;
        }
    }

    /* read and shift in as many whole bytes as we need */
    while (n >= 8) {
        result = (result << 8) + *(ptr++);
        n -= 8;
    }

    /* finally read and shift in the last partial byte */
    if (n > 0) {
        result = (result << n) + (*ptr >> (8-n));
    }
    return result;
}

Aquí hay una demostración en línea con un arnés de prueba simple, que demuestra que este código funciona correctamente en todos los casos extremos que pude encontrar, como leer 64 bits completos a partir de la mitad de un byte o la lectura de solo una parte de un solo byte (que en realidad es un caso especial no trivial, manejado en una rama separada con su propia declaración return en el código anterior).

(Tenga en cuenta que escribí el código anterior en C simple ya que, al igual que su código original, en realidad no utiliza ninguna característica específica de C ++. Siéntase libre de "C ++ ify" agregando std:: cuando corresponda .)

Una característica que el arnés de prueba no comprueba, pero que creo que este código debería poseer, es que nunca lee más bytes de la matriz de entrada de los necesarios. En particular, no se accede a la matriz bytes en absoluto si n == 0 (aunque todavía se calcula un puntero a pos / 8 bytes después del inicio de la matriz).

0
Ilmari Karonen 17 ene. 2018 a las 22:46

Creo que es más simple copiar todos los bytes necesarios y luego enmascarar bits adicionales:

std::uint64_t key_reg(std::uint8_t* bytes, std::size_t n)
{
   std::uint64_t reg = 0;
   std::reverse_copy( bytes, bytes + n / 8 + ( n % 8 != 0 ), 
                      reinterpret_cast<char *>( &reg ) );
   reg >>= n % 8;
   reg &= ~( -1UL << n );
   return reg;
}

Usar pos sería un poco más complejo:

std::uint64_t key_reg(std::uint8_t* bytes, std::size_t pos, std::size_t n)
{
   std::uint64_t reg = 0;
   auto endpos = pos + n;
   auto start = bytes + pos / 8;
   auto end = bytes + endpos / 8 + ( endpos % 8 != 0 );
   std::reverse_copy( start,  end, reinterpret_cast<char *>( &reg ) );
   reg >>= endpos % 8;
   reg &= ~( -1UL << n );
   return reg;
}

ejemplo en vivo

2
Slava 18 ene. 2018 a las 14:27

Tengo lo siguiente

struct MyType
{
std::array<uint8_t, 892> m_rguID;
    uint16_t m_bitLength;


void GetBits(uint16_t startBit, uint16_t nBits, uint64_t & bits) const
};


void MyType::GetBits(uint16_t startBit, uint16_t nBits, uint64_t & bits) const
{
    if(startBit + nBits > m_bitLength)
        throw std::runtime_error("Index is out of range");
    uint32_t num1 = startBit % 8U;
    uint32_t num2 = 8U - num1;
    uint32_t num3 = nBits >= num2 ? num2 : nBits;
    uint32_t num4 = startBit >> 3;
    bits = (uint64_t)(((int64_t)((uint64_t)m_rguID[num4] >> (8 - num3 - num1)) & (int64_t)((1 << num3) - 1)) << (nBits - num3));
    uint32_t num5 = num4 + 1U;
    int num6 = nBits - num3;
    if(num6 <= 0)
        return;
    int num7 = num6 - 8;
    int num8 = 8 - num6;
    do
    {
        if(num6 >= 8)
        {
            bits |= (uint64_t)m_rguID[num5] << num7;
            ++num5;
        }
        else
        {
            bits |= (uint64_t)m_rguID[num5] >> num8;
            ++num5;
        }
        num6 += -8;
        num7 += -8;
        num8 += 8;
    } while(num6 > 0);
}
0
SoronelHaetir 17 ene. 2018 a las 21:44
48310288