Entfernen Sie das n-te Bit aus dem Puffer, und verschieben Sie den Rest

Question

Geben Sie einen uint8_t Puffer von x Länge, ich versuche, mit einer Funktion oder einem Makro, die nth Bit (oder n zu n + i) entfernen können, dann links verschiebe die restlichen Bits.

Beispiel # 1:

eingabe 0b0b... dann ausgegeben 0b76543217 0b654321 ...

Beispiel # 2 sein soll: Wenn die Eingabe:

uint8_t input[8] = { 
    0b00110011, 
    0b00110011, 
    ... 
}; 

der Ausgang ohne das erste Bit sollte

sein,

uint8_t output[8] = { 
    0b00110010, 
    0b01100100, 
    ... 
}; 

Ich habe folgendes t ausprobiert o entferne das erste Bit, aber es funktionierte nicht für die zweite Gruppe von Bits.

/* A macro to extract (a-b) range of bits without shifting */ 
#define BIT_RANGE(N,x,y) ((N) & ((0xff >> (7 - (y) + (x))) << ((x)))) 
void removeBit0(uint8_t *n) { 
    for (int i=0; i < 7; i++) { 
     n[i] = (BIT_RANGE(n[i], i + 1, 7)) << (i + 1) | 
       (BIT_RANGE(n[i + 1], 1, i + 1)) << (7 - i); /* This does not extract the next element bits */ 
    } 
    n[7] = 0; 
} 

Update # 1 In meinem Fall wird die Eingabe uint64_t Nummer wird, dann werde ich memmov es nach links einem Ort zu verschieben verwenden.

Update # 2 Die Lösung kann in C/C++, Assembly (x86-64) oder Inline Assembly sein.

Answer 1

Das ist wirklich 2 Teilprobleme: Entfernen Sie Bits aus jedem Byte und packen Sie die Ergebnisse. Dies ist der Ablauf des folgenden Codes. Ich würde dafür kein Makro verwenden. Zu viel los. Fügen Sie die Funktion einfach hinzu, wenn Sie sich Sorgen um die Leistung auf dieser Ebene machen.

#include <stdio.h> 
#include <stdint.h> 

// Remove bits n to n+k-1 from x. 
unsigned scrunch_1(unsigned x, int n, int k) { 
    unsigned hi_bits = ~0u << n; 
    return (x & ~hi_bits) | ((x >> k) & hi_bits); 
} 

// Remove bits n to n+k-1 from each byte in the buffer, 
// then pack left. Return number of packed bytes. 
size_t scrunch(uint8_t *buf, size_t size, int n, int k) { 
    size_t i_src = 0, i_dst = 0; 
    unsigned src_bits = 0; // Scrunched source bit buffer. 
    int n_src_bits = 0; // Initially it's empty. 
    for (;;) { 
    // Get scrunched bits until the buffer has at least 8. 
    while (n_src_bits < 8) { 
     if (i_src >= size) { // Done when source bytes exhausted. 
     // If there are left-over bits, add one more byte to output. 
     if (n_src_bits > 0) buf[i_dst++] = src_bits << (8 - n_src_bits); 
     return i_dst; 
     } 
     // Pack 'em in. 
     src_bits = (src_bits << (8 - k)) | scrunch_1(buf[i_src++], n, k); 
     n_src_bits += 8 - k; 
    } 
    // Write the highest 8 bits of the buffer to the destination byte. 
    n_src_bits -= 8; 
    buf[i_dst++] = src_bits >> n_src_bits; 
    } 
} 

int main(void) { 
    uint8_t x[] = { 0xaa, 0xaa, 0xaa, 0xaa }; 
    size_t n = scrunch(x, 4, 2, 3); 
    for (size_t i = 0; i < n; i++) { 
    printf("%x ", x[i]); 
    } 
    printf("\n"); 
    return 0; 
} 

Dies schreibt b5 ad 60, die von meiner Rechnung korrekt ist. Einige andere Testfälle funktionieren auch.

Oops Ich habe es das erste Mal falsch verschoben, aber das hier für den Fall, dass es für jemanden nützlich ist.

#include <stdio.h> 
#include <stdint.h> 

// Remove bits n to n+k-1 from x. 
unsigned scrunch_1(unsigned x, int n, int k) { 
    unsigned hi_bits = 0xffu << n; 
    return (x & ~hi_bits) | ((x >> k) & hi_bits); 
} 

// Remove bits n to n+k-1 from each byte in the buffer, 
// then pack right. Return number of packed bytes. 
size_t scrunch(uint8_t *buf, size_t size, int n, int k) { 
    size_t i_src = 0, i_dst = 0; 
    unsigned src_bits = 0; // Scrunched source bit buffer. 
    int n_src_bits = 0; // Initially it's empty. 
    for (;;) { 
    // Get scrunched bits until the buffer has at least 8. 
    while (n_src_bits < 8) { 
     if (i_src >= size) { // Done when source bytes exhausted. 
     // If there are left-over bits, add one more byte to output. 
     if (n_src_bits > 0) buf[i_dst++] = src_bits; 
     return i_dst; 
     } 
     // Pack 'em in. 
     src_bits |= scrunch_1(buf[i_src++], n, k) << n_src_bits; 
     n_src_bits += 8 - k; 
    } 
    // Write the lower 8 bits of the buffer to the destination byte. 
    buf[i_dst++] = src_bits; 
    src_bits >>= 8; 
    n_src_bits -= 8; 
    } 
} 

int main(void) { 
    uint8_t x[] = { 0xaa, 0xaa, 0xaa, 0xaa }; 
    size_t n = scrunch(x, 4, 2, 3); 
    for (size_t i = 0; i < n; i++) { 
    printf("%x ", x[i]); 
    } 
    printf("\n"); 
    return 0; 
} 

Dies schreibt d6 5a b. Einige andere Testfälle funktionieren auch.

Answer 2

Etwas ähnliches wie dies funktionieren soll:

template<typename S> void removeBit(S* buffer, size_t length, size_t index) 
{ 
    const size_t BITS_PER_UNIT = sizeof(S)*8; 

    // first we find which data unit contains the desired bit 
    const size_t unit = index/BITS_PER_UNIT; 
    // and which index has the bit inside the specified unit, starting counting from most significant bit 
    const size_t relativeIndex = (BITS_PER_UNIT - 1) - index % BITS_PER_UNIT; 

    // then we unset that bit 
    buffer[unit] &= ~(1 << relativeIndex); 

    // now we have to shift what's on the right by 1 position 
    // we create a mask such that if 0b00100000 is the bit removed we use 0b00011111 as mask to shift the rest 
    const S partialShiftMask = (1 << relativeIndex) - 1; 

    // now we keep all bits left to the removed one and we shift left all the others 
    buffer[unit] = (buffer[unit] & ~partialShiftMask) | ((buffer[unit] & partialShiftMask) << 1); 

    for (int i = unit+1; i < length; ++i) 
    { 
    //we set rightmost bit of previous unit according to last bit of current unit 
    buffer[i-1] |= buffer[i] >> (BITS_PER_UNIT-1); 
    // then we shift current unit by one 
    buffer[i] <<= 1; 
    } 
} 

Getestet habe ich es nur auf einigen grundlegenden Fällen so vielleicht ist etwas nicht ganz richtig, aber das sollten Sie auf die richtige Spur bewegen.