BitArray kopieren

[mk-soft]

Hi,

suche eine schnelle Methode ein BitArray zu kopieren. Nicht Array of Bool.
Das Array kann mehrere Tausend Bit enthalten.
Es dürfen im Zielbereich die vorlaufende und nachlaufen Bits nicht beeinflusst werden.

Procedure CopyBitArray(*Quelle, StartBitQuelle, AnzahlBits, *Ziel, StartBitZiel, MaxGröße, Base=1)

Alle OS, X86 und X64

Danke.

[NicknameFJ]

Hi mk-soft,

nur zur Klarstellung:

Anzahl Bits: das ist die Anzahl der Bits die vom Quellzielfeld nach Ziel kopiert werden sollen.

Was soll der Parameter MaxGröße bedeuten? Ist das die Gesamtgröße des Zielbitfeldes? Könnte es dann sein dass das Zielbitfeld z.B. insgesamt 8000 Bit groß ist aber z.B. 10000 Bit zu kopieren sind? Soll dann nach 8000 Bit abgebrochen werden um nicht über das Ende des Zielbitfeldes hinaus zu schreiben? Oder kann die Zielbitfeld ab der Posision Startzielbit immer mind. AnzahlBits aufnehmen?

Angenommen ich definiere ein Bitfeld

*Quelle = allocatememory(3)

um Platz für 24 Bit zu haben.


Ich setze Bit 0 (Base = 0), Bit 8 und Bit 23 des Quellbitfeldes und würde die Bytes lesen.

Beim Auslesen erhalte ich die Bytewerte
*Quelle +0: 1 (Bit 1 gesetzt)
*Quelle +1: 1 (Bit 8 gesetzt)
*Quelle +2: 127 (Bit 23 gesetzt)

Oder ist Dein Bitfeld anders organisiert.

NicknameFJ

[NicknameFJ]

Hier der aktuelle Source mit den ganzen Verbesserungen der nachfolgenden Postings

Code: Alles auswählen

;-TOP

; CopyBitArray by NicknameFJ
; Do whatever you want with it
; 03.03.2015

; herzlichen Dank an mk-soft für die durchgeführten Test´s und für die Umstellung auf Direktzugriff



; Update by mk-soft
; Poke und Peek durch Direktzugriff ersetzt
; 04.03.2015


; Update by NicknameFJ
; Es werden jetzt auf einmal Anzahl Bytes entsprechend der nativen Registergröße ins Zielbitfeld kopiert
; Dies bewirkt eine Geschwindigkeitssteigerung von ca. Faktor 3 auf x86 und ca. Faktor 6 auf x64 Plattformen
; 10.03.2015


; sollte plattformunabhängig, x86 und x64, ASCII und UniCode lauffähig sein



; Aufruf: CopyBitArray(*Quelle,StartBitQuelle,AnzahlBits,*Ziel,StartBitZiel [,Base])

; *Quelle:        Zeiger auf den Buffer der das Quellbitfeldes beinhaltet
; StartBitQuelle: gibt das Bit (Position) an ab dem kopiert werden soll, Zählung beginnt bei 0 oder 1 je nach Einstellung des Parameters Base
; AnzahlBits:     Anzahl der Bits die ins Zielbitfeld kopiert werden sollen
; *Ziel:          Zeiger auf den Buffer der das Zielbitfeldes beinhaltet
; StartBitZiel:   gibt das Bit (Position) an wohin die Daten ins Zielbitfeld kopiert werden, Zählung beginnt bei 0 oder 1 je nach Einstellung des Parameters Base
; Base:           Optionaler Parameter: Kann den Wert 0 oder 1 annehmen und gibt an womit die Zählung des StartBitQuelle und des StartBitZiel beginnt. 
;                 wird der Parameter nicht angegeben wird Base auf 0 gesetzt


; Aufbau des Bitfeldes:

; Die Bits  0-7 des Bitfeldes sind im ersten Byte, Bit 0 des Bitfeldes in Bit 0 und Bit 7 des Bitfeldes in Bit 7 des ersten Bytes gespeichert
; Bit 8 - 15 sind im zweiten Byte, Bit 8 des Bitfeldes in Bit 0 und Bit 15 des Bitfeldes in Bit 7 des zweiten Bytes u.s.w.



; Achtung:

; Es können nur Bitfelder kopiert werden die sich nicht überlappen ansonsten werden falsche Daten ins Zielbitfeld geschrieben oder
; vom Quellbitfeld gelesen.

; Die Procedure führt keinerlei Sicherheitsüberprüfungen durch. Ist das Zielbitfeld zu klein wird über das Ende hinausgeschrieben.

; Die Verantwortung für gültige Parameter liegt bei der aufrufenden Routine !



EnableExplicit
DisableDebugger

CompilerIf #PB_Compiler_Processor = #PB_Processor_x86
  #RegisterSize = 32
CompilerElseIf #PB_Compiler_Processor = #PB_Processor_x64
  #RegisterSize = 64
CompilerElse
  CompilerError "Auf diesem Prozessortyp nicht getestet. Setzen Sie #RegisterSize auf die native Prozessorregistergröße und führen Sie Test´s durch ob das Programm zuverlässig arbeitet."
CompilerEndIf

#Faktor = #RegisterSize / 8


Structure ArrayOfUnsignedByte
  StructureUnion
    a.a[0]
    i.i[0]
  EndStructureUnion  
EndStructure



Procedure CopyBitArray(*Quelle,StartBitQuelle,AnzahlBits,*Ziel,StartBitZiel, Base = 0)
  
  Protected StartQuelleByte, StartQuelleBit, StartZielByte, StartZielBit, DiffBits, AnzahlVorlaufBits, AnzahlNachLaufBits
  Protected AnzahlByteMoves, AnzahlIntegerMoves, Shift, RealShift, LoopEnd, RealDiffBits, BytesGesamt
  Protected i, *ptrQ.ArrayOfUnsignedByte, *ptrZ.ArrayOfUnsignedByte, BitQ, BitZ
  
  Protected *CopyFromByte.ArrayOfUnsignedByte
  Protected *CopyToByte.ArrayOfUnsignedByte
  Protected *NextByte.ArrayOfUnsignedByte
  
  
  If Base
    StartBitQuelle -1
    StartBitZiel   -1
  EndIf
  
  
  StartQuelleByte = StartBitQuelle / 8
  StartQuelleBit  = StartBitQuelle % 8
  
  StartZielByte   = StartBitZiel / 8
  StartZielBit    = StartBitZiel % 8
  
  DiffBits        = StartZielBit - StartQuelleBit
  RealDiffBits    = (StartBitZiel % #RegisterSize) - (StartBitQuelle % #RegisterSize)
  
  
  AnzahlVorlaufBits   = 8 - StartZielBit
  If AnzahlVorlaufBits > AnzahlBits
    AnzahlVorlaufBits = AnzahlBits 
  EndIf
  
  BytesGesamt              = (AnzahlBits - AnzahlVorlaufBits) / 8  
  AnzahlIntegerMoves       = BytesGesamt / #Faktor
  AnzahlByteMoves          = BytesGesamt - AnzahlIntegerMoves * #Faktor
  
  AnzahlNachLaufBits       = AnzahlBits - 8 * BytesGesamt - AnzahlVorlaufBits
  
  
  If DiffBits > 0
    Shift = 8 - DiffBits 
    
    *CopyFromByte  = *Quelle + StartQuelleByte
    *CopyToByte    = *Ziel + StartZielByte + 1
    *NextByte      = *CopyFromByte + 1
    
    
    LoopEnd = AnzahlByteMoves -1
    
    For i = 0 To LoopEnd      
      *CopyToByte\a[i] = (*CopyFromByte\a[i] >> Shift) | (*NextByte\a[i] << DiffBits)
    Next
    
    *CopyFromByte + AnzahlByteMoves
    *CopyToByte   + AnzahlByteMoves
    *NextByte     = *CopyFromByte + #Faktor
    
    LoopEnd = AnzahlIntegerMoves - 1
    
    For i = 0 To LoopEnd      
      *CopyToByte\i[i] = (*CopyFromByte\i[i] >> Shift) | (*NextByte\i[i] << RealDiffBits)
    Next
    
    
    
  ElseIf DiffBits < 0
    
    DiffBits = -DiffBits
    Shift = 8 - DiffBits 
    RealShift = #RegisterSize - DiffBits
    
    *CopyFromByte  = *Quelle+StartQuelleByte + 1
    *CopyToByte    = *Ziel+StartZielByte + 1
    *NextByte      = *CopyFromByte + 1
    
    LoopEnd = AnzahlByteMoves - 1
    
    For i = 0 To LoopEnd
      *CopyToByte\a[i] = (*CopyFromByte\a[i] >> DiffBits) | (*NextByte\a[i] << Shift)
    Next
    
    *CopyFromByte + AnzahlByteMoves
    *CopyToByte   + AnzahlByteMoves
    *NextByte     = *CopyFromByte + #Faktor
    
    LoopEnd = AnzahlIntegerMoves - 1
    
    For i = 0 To LoopEnd    
      *CopyToByte\i[i] = (*CopyFromByte\i[i] >> DiffBits) | (*NextByte\i[i] << RealShift)
    Next
    
    
    
  Else ; DiffBits = 0
    
    *CopyFromByte = *Quelle+StartQuelleByte +1
    *CopyToByte   = *Ziel+StartZielByte     +1
    
    
    If BytesGesamt > 0
      CopyMemory(*CopyFromByte,*CopyToByte,BytesGesamt)
    EndIf
    
    
  EndIf
  
  
  ; vor- und nachlaufende Bits in den Zielbereich kopieren
  
  
  *PtrQ = *Quelle
  *PtrZ = *Ziel
  
  
  For i = 0 To AnzahlVorlaufBits -1
    
    BitQ = StartBitQuelle+i    
    BitZ = StartBitZiel  +i
    
    If *ptrQ\a[BitQ /8] & (1 << (BitQ %8))
      *ptrZ\a[BitZ /8] = *ptrZ\a[BitZ /8] | (1 << (BitZ %8))
    Else
      *ptrZ\a[BitZ /8] = *ptrZ\a[BitZ /8] & (~(1 << (BitZ %8)))
    EndIf
  Next i
  
  
  For i = AnzahlBits-AnzahlNachLaufBits To AnzahlBits-1
    
    BitQ = StartBitQuelle+i    
    BitZ = StartBitZiel  +i
    
    If *ptrQ\a[BitQ /8] & (1 << (BitQ %8))
      *ptrZ\a[BitZ /8] = *ptrZ\a[BitZ /8] | (1 << (BitZ %8))
    Else
      *ptrZ\a[BitZ /8] = *ptrZ\a[BitZ /8] & (~(1 << (BitZ %8)))
    EndIf
  Next
  
  
EndProcedure




; --------------------------------
; DEMO Code

Define *Quelle, *Ziel, StartTime, EndeTime, BitsToCopy

Procedure.s PeekBinA(*adr)
  
  Protected r1.s
  r1 = RSet(Bin(PeekA(*adr)), 8, "0")
  r1 = ReverseString(r1)
  ProcedureReturn r1
  
EndProcedure


BitsToCopy = 42  ; Anzahl der Bits die kopiert werden sollen


*Quelle = AllocateMemory(10000000)
*Ziel   = AllocateMemory(10000000)


;Quellbitfeld initialisieren

PokeB(*Quelle,131)   : PokeB(*Quelle+1,187) : PokeB(*Quelle+2,96)  : PokeB(*Quelle+3,193) : PokeB(*Quelle+4,148) : PokeB(*Quelle+5,112) : PokeB(*quelle+6,84)



; Zielbitfeld löschen / vorbelegen
#Wert = 255
PokeA(*Ziel,#Wert)   : PokeA(*Ziel+1,#Wert) : PokeA(*Ziel+2,#Wert) : PokeA(*Ziel+3,#Wert) : PokeA(*Ziel+4,#Wert) : PokeA(*Ziel+5,#Wert) : PokeA(*Ziel+6,#Wert) : PokeA(*Ziel+7,#Wert) : PokeA(*Ziel+8,#Wert)


StartTime = ElapsedMilliseconds()
CopyBitArray(*Quelle,0,BitsToCopy,*Ziel,7,0)
EndeTime = ElapsedMilliseconds()



EnableDebugger


Debug " Byte 0    Byte 1    Byte 2    Byte 3    Byte 4    Byte 5    Byte 6    Byte 7    Byte 8"
Debug "01234567  01234567  01234567  01234567  01234567  01234567  01234567  01234567  01234567"
Debug ""
Debug "Quellinhalt"
Debug ""
Debug PeekBinA(*Quelle + 0) + "  " + PeekBinA(*Quelle + 1) + "  " + PeekBinA(*Quelle + 2) + "  " + PeekBinA(*Quelle + 3) + "  " + PeekBinA(*Quelle + 4) + "  " + PeekBinA(*Quelle + 5)+ "  " + PeekBinA(*Quelle + 6)+ "  " + PeekBinA(*Quelle + 7)+ "  " + PeekBinA(*Quelle + 8)
Debug ""
Debug ""

Debug "Zielinhalt nach CopyArray"
Debug PeekBinA(*Ziel + 0) + "  " + PeekBinA(*Ziel + 1) + "  " + PeekBinA(*Ziel + 2) + "  " + PeekBinA(*Ziel + 3) + "  " + PeekBinA(*Ziel + 4) + "  " + PeekBinA(*Ziel + 5)+ "  " + PeekBinA(*Ziel + 6)+ "  " + PeekBinA(*Ziel + 7)+ "  " + PeekBinA(*Ziel + 8)

MessageRequester("","benötigte Zeit für "+Str(BitstoCopy) + " Bits"+#CRLF$+Str(EndeTime-StartTime)+ " ms.")


FreeMemory(*Quelle)
FreeMemory(*Ziel)

Zur freien Verwendung

NicknameFJ

[mk-soft]

Sehr großen Dank,
werde ich ausgiebig testen

[mk-soft]

Habe mal die Poke und Peek Funktionen durch Direktzugriffe ersetzt.
Ist dadurch etwa 50% schneller.

Danke noch mal an Nick für seine hervorragende Arbeit

Code: Alles auswählen

;-TOP

; CopyBitArray by NicknameFJ
; 
; Do whatever you want with it

; 03.03.2015

; Update by mk-soft

; Poke und Peek durch Direktzugriff ersetzt

; 04.03.2015

; Update by NicknameFJ ;-)

[NicknameFJ]

Source oben geändert

[NicknameFJ]

Neue Version:

Ich habe die Procedure so geändert, dass jetzt auf einmal Anzahl Bytes entsprechend der nativen Prozessorregistergröße auf einmal ins Zielbitfeld geschrieben werden.
Dies bewirkt eine Geschwindigkeitssteigerung von ca. Faktor 3 auf x86 und ca. Faktor 6 auf x64 Plattformen.

Weiterhin wurde der (optionale) Parameter Base mit eingeführt.

Die Verbesserungen von mk-soft hinsichtlich Direktzugriff sind selbstverständlich auch mit dabei.

Herzlichen Dank an mk-soft für diese Verbesserungen.

NicknameFJ


Ach ja, das wichtigste, der Source

Code: Alles auswählen

sh. mein obiges Posting

[mk-soft]

Sehr gut