Unbekannte Anzahl an kodierten Daten aus Stream lesen -> Schleife vermeiden



  • Ich hab nen Stream (ist einfach ein uint8_t* array) in wobei in jeder 8bit,16bit,32bit-etc. Einheit eine unbekannte Anzahl an kodierten Zahlen drinstehen. Das dekodieren funktioniert ganz einfach:

    - Lese Anzahl aus aufeinanderfolgenden einzen aus Stream und speicher sie in "einser"
    - Lese noch "k" mehr bits aus dem Stream und speicher das Ergebnis in "m". K ist variable und ändert sich auch zur Laufzeit

    Die Zahl die rauskommt ist dann einfach:

    zahl = (einser << k) + m;
    

    Wem es schon aufgefallen ist: Das ist ein Decoder für einen Golomb Rice Entropy-Encoder.

    Eine triviale Lösung um diese Zahlen aus nem Stream zu holen ist aber elendig langsam: Man muss in einer Schleife einzeln durch die Bits wandern und bei der ersten 0 dann eben abbrechen, und sich zudem merken wie viele bits man vom aktuellen Byte schon gelesen hat. In der Praxis kommt es dadurch relativ häufig dazu, dass 10-16 Schleifendurchgänge nötig sind (wobei jeder Schleifendurchgang mit ~5 Operationen und einem Branch verbunden ist) um eine einzige dieser kodierten Zahlen rauszulesen.

    Konkret:

    uint8 leseBit() //liest von links
    {
       uint8 val = ((*m_buffer)<<m_bits_read) & 0x80; //m_buffer ist das uint8 array
       ++m_bits_read; //speichert, wie viele bits aus dem momentanen byte schon gelesen sind
       if(m_bits_read == 8)
       {
          m_buffer +=1;
          m_bits_read = 0;
       }
    
       return val;
    }
    
    uint8 leseEinser()
    {
       uint32 count = 0;
       while(leseBit())
          count++;
    
       return count;
    }
    

    Wie bekommt man das schneller hin?





  • Michael E. schrieb:

    Du kannst die folgenden Methoden verwenden: http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightLinear

    Hmm... ich erkenn leider nicht, dass mir das etwas bringt. Problem: Es ist nicht immer gegeben, dass ich zwischen Byte-aligned Grenzen suche, sondern es kann z.B. auch sein, dass ich vom 5. Bit im 1. Byte zum 3. Bit im 3. Byte suchen muss (die kodierten Koeffizienten sind nicht byte-aligned). In einem 32-Bit int können 10 Kodierte Koeffizienten sein.

    Außerdem zählt was er macht doch 0en von rechts. Das was bei mir nach den aufeinanderfolgenden 1en kommt, müssen aber nicht durchgehend Nuller sein. Z.B. 111110101011 ist möglich.



  • @unbekannte_daten
    Du kannst hier einiges über Lookup-Tables rausholen.



  • unbekannte_daten schrieb:

    Problem: Es ist nicht immer gegeben, dass ich zwischen Byte-aligned Grenzen suche, sondern es kann z.B. auch sein, dass ich vom 5. Bit im 1. Byte zum 3. Bit im 3. Byte suchen muss (die kodierten Koeffizienten sind nicht byte-aligned). In einem 32-Bit int können 10 Kodierte Koeffizienten sein.

    Shifte das erste Byte bis zur passenden Position. Bei den darauffolgenden Bytes eines Blocks passt dann die Position.

    Außerdem zählt was er macht doch 0en von rechts. Das was bei mir nach den aufeinanderfolgenden 1en kommt, müssen aber nicht durchgehend Nuller sein. Z.B. 111110101011 ist möglich.

    Invertiere die Zahl.



  • Hi nochmal.

    Für x86 gibt es bsf und bsr. Mein Problem ist also geloest durch:

    uint16 shifted = ...; //16 bit aus stream extrahieren
    shifted = ~shifted;
    
    __asm
    {
       bsr ax,shifted
       mov shifted, ax
    }
    
    shifted = 16 - shifted;
    //shifted enthaelt nun die anzahl der 1en
    

Anmelden zum Antworten